LLVM에서 IR을 단순화하는 방법 설명하기


LLVM에서 프로그램의 중간 표현(IR)을 단순화하려면 IR 코드를 보다 효율적이고 간소화된 형태로 변환하는 일련의 최적화 패스를 적용해야 합니다. 다음은 LLVM에서 IR을 단순화하는 일반적인 단계입니다:

최적화 수준을 선택합니다: LLVM은 코드를 최적화하는 데 걸리는 시간과 달성한 최적화 정도 간에 균형을 맞추는 여러 최적화 수준을 제공합니다. 예를 들어, -O1 최적화 수준은 비교적 빠른 중간 수준의 최적화를 수행하는 반면, -O3 수준은 훨씬 더 오래 걸릴 수 있는 높은 수준의 최적화를 수행합니다.

최적화 패스를 실행합니다: LLVM은 IR 코드에서 실행할 수 있는 대규모 최적화 패스 모음을 제공합니다. 이러한 패스는 상수 폴딩 및 데드 코드 제거와 같은 간단한 변환부터 루프 언롤링 및 함수 인라이닝과 같은 보다 복잡한 최적화까지 다양합니다. 몇 가지 일반적인 최적화 패스는 다음과 같습니다:

데드 코드 제거: 이 패스는 사용되지 않는 함수, 도달할 수 없는 명령어 등 실행되지 않는 코드를 제거합니다.
상수 전파: 이 패스는 코드 전체에서 변수를 상수 값으로 대체하여 메모리 액세스 횟수 및 기타 필요한 연산 횟수를 줄일 수 있습니다.
루프 최적화: 이 패스는 루프를 언롤링하거나 루프 유도 변수를 최적화하는 등 루프를 변형하여 성능을 개선합니다.
함수 인라이닝: 이 패스는 함수 호출을 실제 함수 본문으로 대체하여 함수 호출의 오버헤드를 줄임으로써 성능을 향상시킬 수 있습니다.
결과를 측정합니다: 최적화 패스를 실행한 후에는 결과 코드의 성능과 크기를 측정하여 최적화가 원하는 효과를 달성했는지 확인하는 것이 중요합니다. 이 작업은 LLVM에 내장된 프로파일링 및 벤치마킹 툴을 사용하여 수행할 수 있습니다.

필요에 따라 반복합니다: 원하는 수준의 성능과 코드 크기를 달성할 때까지 여러 번의 패스를 실행하고 최적화 수준을 조정하면서 최적화 프로세스를 반복해야 하는 경우가 종종 있습니다. 전반적으로 LLVM에서 IR을 간소화하려면 달성한 최적화 수준과 코드 최적화에 소요되는 시간 간의 신중한 균형이 필요합니다. 일련의 최적화 패스를 실행하고 결과를 측정함으로써 개발자는 보다 효율적이고 간소화된 코드 버전을 얻을 수 있습니다.

다음은 simplify를 사용하는 간단한 예제입니다.

1. 더하기 연산을 수행하는 간단한 C++ 프로그램을 생성하고 -emit-llvm 플래그를 사용하여 컴파일하여 LLVM IR 코드를 생성합니다:

// add.cpp
int main() {
    int a = 1;
    int b = 2;
    int c = a + b;
    return 0;
}

clang++ -emit-llvm add.cpp -o add.ll

2. 생성된 LLVM IR 코드를 검사하여 관련 추가 명령어를 찾습니다. 이 경우 추가 인스트럭션은 메인 함수에 있으며 다음과 같은 형식을 갖습니다:

%add = add i32 %a, %b

3. 최적화 실행은 옵트 도구를 사용하여 IR 코드에 최적화 패스를 전달합니다. 비교적 빠른 중간 수준의 최적화를 수행하는 -O1 최적화 수준을 실행할 수 있습니다. 또한 -S 플래그를 지정하여 사람이 읽을 수 있는 어셈블리 형식으로 최적화된 IR 코드를 출력해야 합니다.

opt -O1 -S add.ll -o add_opt.ll

4. 최적화된 IR 코드를 검사하여 최적화 패스의 효과를 확인합니다. 이 경우 추가 명령이 더하기의 결과인 상수 값으로 대체되었습니다:

%c = add i32 3, 0

5. 선택적으로 최적화 패스를 추가로 실행하여 더 높은 수준의 최적화를 달성할 수 있습니다. 예를 들어, -O3 최적화 수준을 실행하여 더 높은 수준의 최적화를 수행하거나 instcombine 또는 simplifycfg와 같은 특정 최적화 패스를 실행할 수 있습니다.

opt -O3 -S add.ll -o add_opt.ll

최적화된 IR 코드를 검사하여 최적화 패스의 효과를 확인합니다. 이 경우 추가 명령이 완전히 제거되었으며 결과는 단순히 상수 값으로 반환됩니다:

ret i32 0

전반적으로 LLVM에서 IR 코드를 간소화하려면 관련 지침을 식별하고, 코드에 대한 최적화 패스를 실행하고, 결과를 검사하여 원하는 수준의 최적화가 달성되었는지 확인해야 합니다.

다음은 위의 과정을 구현한 예제입니다.

앞서 설명한 프로세스에는 각각 clang 및 opt와 같은 LLVM 도구를 사용하여 LLVM IR 코드를 생성하고 최적화하는 과정이 포함됩니다. 그러나 원하는 최적화를 수행하는 커스텀 패스를 작성하여 LLVM 자체 내에서 동일한 결과를 얻을 수 있습니다.

예를 들어, 덧셈 인스트럭션을 상수 값으로 대체하여 LLVM IR 모듈을 단순화하려면 다음 단계를 수행하는 커스텀 패스를 작성할 수 있습니다:

    모듈을 가로지르며 모든 더하기 명령어를 식별합니다.
    더하기 명령의 피연산자가 모두 상수 값인지 확인합니다.
    두 피연산자가 모두 상수이면 더하기 결과를 계산하고 더하기 명령을 새로운 상수 값 명령으로 바꿉니다.
    더 이상 더하기 명령어를 단순화할 수 없을 때까지 이 과정을 반복합니다.

다음은 LLVM의 C++ API를 사용하여 이 패스를 구현한 예제입니다:

#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Pass.h"

using namespace llvm;

struct SimplifyAdd : public FunctionPass {
  static char ID;
  SimplifyAdd() : FunctionPass(ID) {}

  bool runOnFunction(Function &F) override {
    bool Changed = false;
    for (BasicBlock &BB : F) {
      for (Instruction &I : BB) {
        if (auto *Add = dyn_cast<BinaryOperator>(&I)) {
          if (Add->getOpcode() == Instruction::Add &&
              isa<ConstantInt>(Add->getOperand(0)) &&
              isa<ConstantInt>(Add->getOperand(1))) {
            int64_t Op0 = cast<ConstantInt>(Add->getOperand(0))->getSExtValue();
            int64_t Op1 = cast<ConstantInt>(Add->getOperand(1))->getSExtValue();
            ConstantInt *Result = ConstantInt::get(Add->getType(), Op0 + Op1);
            Add->replaceAllUsesWith(Result);
            Add->eraseFromParent();
            Changed = true;
          }
        }
      }
    }
    return Changed;
  }
};

char SimplifyAdd::ID = 0;
static RegisterPass<SimplifyAdd> X("simplify-add", "Simplify add instructions");

이 패스는 LLVM의 패스 관리자를 사용하여 등록하고 실행하거나 -passes 플래그와 함께 opt를 호출하여 실행할 수 있습니다:

opt -passes=simplify-add -S add.ll -o add_opt.ll

이렇게 하면 add.ll 파일의 모든 추가 인스트럭션을 상수 값 인스트럭션으로 대체하여 단순화할 수 있습니다. 결과적으로 최적화된 IR 코드가 add_opt.ll 파일에 출력됩니다.

========================================================================================================

(-_-;;; ) ChatGPT 에게 물어보세요 !! ㄷㄷㄷ!

내부 구현은 훨씬 복잡하고 경우의 수가 다양해서 지금 하고 있는 작업 - 각 PASS 들이 공통적으로 사용하는 주요 로직을 추출해 예제로 만드는 - 에 약간 장벽을 만났습니다만, 처음보는 용어나 기능을 이해하는데 가이드가 되줄 수 있을 것 같습니다.