LLVM Optimization study - DCE

Facebook의 Redex 라는 프로젝트 코드를 참조하기 위해 보는 중 난해했던 코드를 만났습니다.

 

void LocalDce::dce(IRCode* code,
                   bool normalize_new_instances,
                   DexType* declaring_type) {
  cfg::ScopedCFG cfg(code);
  dce(*cfg, normalize_new_instances, declaring_type);
}

 

DCE 옵티마이징 과정 중에 이런 코드가 있던거죠.

 

bliveness |= liveness.at(s->target()->id());

 

이게 무슨 코드인가? 했는데 dataflow analysis 에서 live analysis(?) 를 DCE에서 같이하는걸로 보이네요.

capture from Engineering a compiler 2/E

이에 대해선 차후 포스팅 할 기회가 있을 것 같습니다.

 

DCE란 Dead Code Elimination 의 약자로 죽은 코드를 제거하는 최적화 과정입니다.

LLVM에는 다음과 같이 구현이 되어 있습니다.

 

 88 static bool DCEInstruction(Instruction *I,
 89                            SmallSetVector<Instruction *, 16> &WorkList
 90                            const TargetLibraryInfo *TLI) {
 91   if (isInstructionTriviallyDead(I, TLI)) {
 92     if (!DebugCounter::shouldExecute(DCECounter))
 93       return false;
 94
 95     salvageDebugInfo(*I);
 96     salvageKnowledge(I);
 97
 98     // Null out all of the instruction's operands to see if any operan
 99     // dead as we go.
100     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
101       Value *OpV = I->getOperand(i);
102       I->setOperand(i, nullptr);
103
104       if (!OpV->use_empty() || I == OpV)
105         continue;
106
107       // If the operand is an instruction that became dead as we nulle
108       // operand, and if it is 'trivially' dead, delete it in a future
109       // iteration.
110       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
111         if (isInstructionTriviallyDead(OpI, TLI))
112           WorkList.insert(OpI);
113     }
114
115     I->eraseFromParent();
116     ++DCEEliminated;
117     return true;
118   }
119   return false;
120 }

 

구현은 꽤나 직관적이고 간단했습니다.

 

LLVM에 존재하는 아래 테스트코드를 긁어와서 먼저 코드 플로우를 확인해보겠습니다.

 

; RUN: opt -passes='module(debugify),function(dce)' -S < %s

; CHECK-LABEL: @test
define void @test() {
  %add = add i32 1, 2
  %sub = sub i32 %add, 1
  ret void
}

 

Uftrace를 이용해 런타임 플로우를 분석해보면

 

$ uftrace record /build/bin/opt -passes='function(dce)' -S  basic.ll

 

# DURATION     TID     FUNCTION
            [ 63776] |                   eliminateDeadCode() {
   0.042 us [ 63776] |                     llvm::make_early_inc_range();
   0.041 us [ 63776] |                     llvm::isInstructionTriviallyDead();
            [ 63776] |                     llvm::isInstructionTriviallyDead() {
            [ 63776] |                       llvm::wouldInstructionBeTriviallyDead() {
   0.041 us [ 63776] |                         llvm::Instruction::willReturn();
            [ 63776] |                         llvm::Instruction::mayHaveSideEffects() {
   0.042 us [ 63776] |                           llvm::Instruction::willReturn();
   0.208 us [ 63776] |                         } /* llvm::Instruction::mayHaveSideEffects */
   0.584 us [ 63776] |                       } /* llvm::wouldInstructionBeTriviallyDead */
   0.708 us [ 63776] |                     } /* llvm::isInstructionTriviallyDead */
            [ 63776] |                     DCEInstruction() {
            [ 63776] |                       llvm::isInstructionTriviallyDead() {
            [ 63776] |                         llvm::wouldInstructionBeTriviallyDead() {
   0.041 us [ 63776] |                           llvm::Instruction::willReturn();
            [ 63776] |                           llvm::Instruction::mayHaveSideEffects() {
   0.042 us [ 63776] |                             llvm::Instruction::willReturn();
   0.125 us [ 63776] |                           } /* llvm::Instruction::mayHaveSideEffects */
   0.333 us [ 63776] |                         } /* llvm::wouldInstructionBeTriviallyDead */
   0.417 us [ 63776] |                       } /* llvm::isInstructionTriviallyDead */
            [ 63776] |                       llvm::Instruction::eraseFromParent() {
   2.708 us [ 63776] |                       } /* llvm::Instruction::eraseFromParent */
   4.875 us [ 63776] |                     } /* DCEInstruction */
            [ 63776] |                     llvm::isInstructionTriviallyDead() {
   0.083 us [ 63776] |                       llvm::wouldInstructionBeTriviallyDead();
   0.125 us [ 63776] |                     } /* llvm::isInstructionTriviallyDead */
            [ 63776] |                     llvm::isInstructionTriviallyDead() {
            [ 63776] |                       llvm::wouldInstructionBeTriviallyDead() {
   0.041 us [ 63776] |                         llvm::Instruction::willReturn();
            [ 63776] |                         llvm::Instruction::mayHaveSideEffects() {
   0.041 us [ 63776] |                           llvm::Instruction::willReturn();
   0.125 us [ 63776] |                         } /* llvm::Instruction::mayHaveSideEffects */
   0.333 us [ 63776] |                       } /* llvm::wouldInstructionBeTriviallyDead */
   0.417 us [ 63776] |                     } /* llvm::isInstructionTriviallyDead */
            [ 63776] |                     DCEInstruction() {
            [ 63776] |                       llvm::Instruction::eraseFromParent() {
   1.959 us [ 63776] |                       } /* llvm::Instruction::eraseFromParent */
   3.250 us [ 63776] |                     } /* DCEInstruction */
  10.667 us [ 63776] |                   } /* eliminateDeadCode */
  15.917 us [ 63776] |                 } /* llvm::DCEPass::run */
  16.708 us [ 63776] |               } /* llvm::detail::PassModel::run */

 

DCEPass는 두 번의 DCEInstruction 를 수행하는걸 알 수 있습니다.

어떤 과정으로 진행되는지 디버거를 붙여 확인해봅시다.

 

$ gdb --args /build/bin/opt -passes='function(dce)' -S  basic.ll

 

Breakpoint 2, DCEInstruction (I=0x55555c71e5f0, WorkList=..., TLI=0x55555c721188)
    at /home/m/llvm-project/llvm/lib/Transforms/Scalar/DCE.cpp:115
115         I->eraseFromParent();
(gdb) p I->dump()
  %sub = sub
$5 = void
(gdb) c
Continuing.

 

우선 제거되는 것은 다음의 IR로 표현된 instruction 입니다.

%sub = sub i32 %add, 1

 

그리고 sub 의 op1 에 대한 처리가 다음라인에서 이뤄지게 되죠

110       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
111         if (isInstructionTriviallyDead(OpI, TLI))
112           WorkList.insert(OpI);

 

그리고 이게 DCEInstruction 함수를 호출하는 함수 eliminateDeadCode에서 다음처럼 처리가 됩니다.

  while (!WorkList.empty()) {
    Instruction *I = WorkList.pop_back_val();
    MadeChange |= DCEInstruction(I, WorkList, TLI);
  }

 

그래서 다음에 제거되는 Instruction이 다음처럼 표현되는 IR 입니다.

  %add = add i32 1, 2

 

Breakpoint 2, DCEInstruction (I=0x55555c71e460, WorkList=..., TLI=0x55555c721188)
    at /home/m/llvm-project/llvm/lib/Transforms/Scalar/DCE.cpp:115
115         I->eraseFromParent();
(gdb) p I->dump()
  %add = add
$6 = void
(gdb) c
Continuing.

Breakpoint 5, eliminateDeadCode (F=..., TLI=0x55555c721188) at /home/m/llvm-project/llvm/lib/Transforms/Scalar/DCE.cpp:142
142     t, TLI);
(gdb) p MadeChange
$7 = true

 

 

제 오랜 숙원중에 하나가 LLVM의 각 PASS를 시각화 할 수 있는 툴을 만드는 것인데 DCE부터 시작하면 딱이겠다는 생각은 드네요.

 

DCE는 다음 조건에 해당하지 않는 경우 Instruction을 제거하는 로직입니다.

  if (isInstructionTriviallyDead(I, TLI)) {
    if (!DebugCounter::shouldExecute(DCECounter))
      return false;

 

isInstructionTriviallyDead 는 다음처럼 구현되어 있구요.

bool llvm::isInstructionTriviallyDead(Instruction *I,
                                      const TargetLibraryInfo *TLI) {
  if (!I->use_empty())
    return false;
  return wouldInstructionBeTriviallyDead(I, TLI);
}

 

wouldInstructionBeTriviallyDead 은 굉장히 깁니다.

어떤 경우에 죽은 코드로 판명할지에 대한 서술이기 때문이죠. 일부만 발췌해보겠습니다.

 

  return false;
} // wouldInstructionBeTriviallyDead end

 

먼저 wouldInstructionBeTriviallyDead 은 기본 false 반환으로 지정 경우에만 제거되도록 하고 있습니다..

 

  if (!I->willReturn())
    return false;

  if (!I->mayHaveSideEffects())
    return true;

 

 

크게 mayHaveSideEffects() 호출 전후로 나눌 수 있는데, mayHaveSideEffects() 전에 해당하는 몇 특수 경우를 먼저 제외하고 mayHaveSideEffects() 를 통해 사이드이펙트가 없는 경우는 true를 반환하게 됩니다.

 

bool Instruction::mayHaveSideEffects() const {
  return mayWriteToMemory() || mayThrow() || !willReturn();
}

 

** !willReturn() 이 겹치는게 이상해서 확인해보니 2016년에 제거됐다. 아쉽다 한줄패치라도 할 기회였는데 ㅎㅎ! **

commit 0f45572761388f418dc2c95034416f01eec6bc94
Author: David Majnemer <david.majnemer@gmail.com>
Date:   Sat Jun 25 00:55:12 2016 +0000

    The absence of noreturn doesn't ensure mayReturn

 

어쨋든 경우의 수는 둘 중 하나입니다.

mayWriteToMemory() || mayThrow()

 

mayThrow()는 throw로 짐작이 가고 실제로도 그렇습니다.

mayWriteToMemory() 를 살펴보면,

 

bool Instruction::mayWriteToMemory() const {
  switch (getOpcode()) {
  default: return false;
  case Instruction::Fence: // FIXME: refine definition of mayWriteToMemory
  case Instruction::Store:
  case Instruction::VAArg:
  case Instruction::AtomicCmpXchg:
  case Instruction::AtomicRMW:
  case Instruction::CatchPad:
  case Instruction::CatchRet:
    return true;
  case Instruction::Call:
  case Instruction::Invoke:
  case Instruction::CallBr:
    return !cast<CallBase>(this)->onlyReadsMemory();
  case Instruction::Load:
    return !cast<LoadInst>(this)->isUnordered();
  }
}

 

기본적으로 false이고 특수한 경우에만 true를 반환하는 사이드이펙트가 있을 수 있는 인스트럭션 입니다.

 

1. Fence이하 Atomic instruction 류, Catch 류

2. Call/Invoke/CallBr 인데 메모리를 읽기만 하지 않는 경우 (아직 미확인 영역)

3. Load 인데 Unordered() 가 아닌 경우 = ATOMIC 이 아니고 동시에 Volatile 이 아닌 경우.

 

아마 대부분의 instruction이 사이드이펙트가 없기에 여기서 제거가 되겠고,

여길 지나가면 특수하게 제거될 수 있는 몇 가지 경우의 수에 해당하지 않는 경우 기본적으로 false 를 반환하게 됩니다.

 

예를 들면 이런 경우인데요.

  // Non-volatile atomic loads from constants can be removed.
  if (auto *LI = dyn_cast<LoadInst>(I))
    if (auto *GV = dyn_cast<GlobalVariable>(
            LI->getPointerOperand()->stripPointerCasts()))
      if (!LI->isVolatile() && GV->isConstant())
        return true;

 

주석처럼, volatile 로 지정된 LoadInst이라도 Load 대상이 전역 변수일 때
해당 전역 변수가 volatile이 아닌 상수인 경우에는 제거될 수 있는 특수한 경우가 되겠습니다.