LLVM Optimization study - instcombine with ChatGPT

* 이 글은 아직 검증되지 않은 내용을 답고 있습니다. *

 

instcombine 은 -instcombine 옵션으로 실행되는 최적화 pass 입니다.

https://llvm.org/docs/Passes.html#instcombine-combine-redundant-instructions

LLVM’s Analysis and Transform Passes — LLVM 17.0.0git documentation

Instcombine

인스턴트 결합 패스는 LLVM의 최적화 패스 중 하나로, LLVM IR(중간 표현)에서 명령어 수준의 연산 결합을 수행하여 코드를 간소화하고 최적화합니다.

인스트컴바인 패스의 주요 목표는 중복되거나 불필요한 명령어를 식별하여 제거하고 더 간단하고 효율적인 코드로 대체하는 것입니다. 이를 위해 일련의 대수적 및 논리적 단순화를 LLVM IR의 명령어에 적용하여 이를 달성합니다.

예를 들어 인스턴트 결합 패스는 다음과 같은 종류의 변환을 수행할 수 있습니다:

    상수 접기: 상수가 포함된 산술 표현식을 그 결과로 대체합니다(예: 3 + 5가 8이 됨).
    대수 단순화: 대수 동일성을 사용하여 표현식을 단순화합니다(예: x * 1이 x가 됨).
    강도 감소: 비싼 연산을 더 저렴한 연산으로 대체합니다(예: 곱셈을 2의 거듭제곱으로 대체하는 것을 비트 시프트 연산으로 대체).
    데드 코드 제거: 프로그램 출력에 영향을 주지 않는 명령어(예: 값이 할당되었지만 사용되지 않는 변수)를 제거합니다.

이러한 최적화 및 기타 최적화를 적용하면 instcombine 패스를 통해 LLVM IR 코드의 크기와 복잡성을 크게 줄이고 결과 바이너리의 성능을 개선할 수 있습니다.

 

다음은 인스턴스 결합 패스를 C++로 작성된 LLVM 패스로 구현한 것입니다:

#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/InstrTypes.h"

using namespace llvm;

namespace {
  class InstCombinePass : public FunctionPass, public InstVisitor<InstCombinePass> {
  public:
    static char ID;
    InstCombinePass() : FunctionPass(ID) {}

    virtual bool runOnFunction(Function &F) {
      visit(F);
      return true;
    }

    void visitBinaryOperator(BinaryOperator &I) {
      // Constant folding
      if (ConstantInt *CI1 = dyn_cast<ConstantInt>(I.getOperand(0))) {
        if (ConstantInt *CI2 = dyn_cast<ConstantInt>(I.getOperand(1))) {
          APInt Result = CI1->getValue() + CI2->getValue();
          I.replaceAllUsesWith(ConstantInt::get(I.getContext(), Result));
        }
      }
      // Algebraic simplification
      if (I.getOpcode() == Instruction::Mul) {
        if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1))) {
          if (CI->isOne()) {
            I.replaceAllUsesWith(I.getOperand(0));
          }
        }
      }
      // Strength reduction
      if (I.getOpcode() == Instruction::Mul) {
        if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1))) {
          APInt Result = I.getOperand(0)->getType()->getScalarSizeInBits() == 32
              ? CI->getValue().countTrailingZeros()
              : CI->getValue().countTrailingOnes();
          if (Result > 0) {
            BinaryOperator *Shl = BinaryOperator::CreateShl(
              I.getOperand(0), ConstantInt::get(I.getContext(), Result));
            I.replaceAllUsesWith(Shl);
          }
        }
      }
      // Dead code elimination
      if (I.use_empty()) {
        I.eraseFromParent();
      }
    }
  };
}

char InstCombinePass::ID = 0;
static RegisterPass<InstCombinePass> X("instcombine", "Instruction Combining Pass");

이 패스는 FunctionPass와 InstVisitor를 모두 상속하여 함수의 모든 인스트럭션을 방문하고 적절한 단순화를 수행할 수 있습니다. 방문BinaryOperator 메서드는 함수의 각 이진 연산자 명령어에 대해 호출되며 앞서 설명한 상수 폴딩, 대수적 단순화, 강도 감소 및 데드 코드 제거 최적화를 수행합니다.

이 패스를 사용하려면 LLVM 패스 매니저에 다음 코드를 추가하면 됩니다:

legacy::PassManager PM;
PM.add(createInstCombinePass());
PM.run(*M);

 

example:

 

define i32 @foo(i32 %x, i32 %y) {
  %mul = mul i32 %x, 1
  %add = add i32 %mul, %y
  %shr = lshr i32 %x, 2
  %shl = shl i32 %shr, 3
  %sub = sub i32 %shl, 4
  %or = or i32 %sub, %y
  %cmp = icmp eq i32 %or, %x
  %sel = select i1 %cmp, i32 1, i32 0
  ret i32 %sel
}

 

> instcombine 처리 후

define i32 @foo(i32 %x, i32 %y) {
  %add = add i32 %x, %y
  %shl = shl i32 %x, 1
  %sub = sub i32 %shl, 4
  %or = or i32 %sub, %y
  %cmp = icmp eq i32 %or, %x
  %sel = select i1 %cmp, i32 1, i32 0
  ret i32 %sel
}