LLVM Optimization study - LoopInstSimplify

https://github.com/ParkHanbum/mystudy/tree/master/llvm-study

GitHub - ParkHanbum/mystudy

이 글의 실행결과는 위 리포지터리를 통해 직접 확인해보실 수 있습니다.

 

LoopInstSimplify 는 -loop-simplify 옵션으로 실행되는 최적화 pass 입니다.

https://llvm.org/docs/Passes.html#loop-simplify-canonicalize-natural-loops

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

 

 

이 패스는 몇 가지 변환을 수행하여 자연 루프를 더 단순한 형태로 변환하여 후속 분석 및 변환을 더 간단하고 효과적으로 만듭니다. 이에 대한 요약은 루프 용어, 루프 단순화 양식에서 확인할 수 있습니다. 루프 사전 헤더 삽입은 루프 외부에서 루프 헤더까지 중요하지 않은 단일 엔트리 에지가 있음을 보장합니다. 이를 통해 LICM과 같은 여러 분석 및 변환이 간소화됩니다. 루프 종료 블록 삽입은 루프의 모든 종료 블록(루프 내부에 선행자가 있는 루프 외부에 있는 블록)이 루프 내부의 선행자(따라서 루프 헤더에 의해 지배됨)만 갖도록 보장합니다. 이렇게 하면 LICM에 내장된 스토어 싱킹과 같은 변환이 단순화됩니다. 또한 이 패스는 루프가 정확히 하나의 백엣지를 갖도록 보장합니다. 단순화cfg 패스는 분할되었지만 결국 불필요한 블록을 정리하므로 이 패스를 사용한다고 해서 생성된 코드가 비관적으로 변해서는 안 됩니다. 이 패스는 분명히 CFG를 수정하지만 루프 정보와 도미네이터 정보를 업데이트합니다.
Translated with www.DeepL.com/Translator (free version)

 

테스트 예제) loop-simplify4.ll

define i32 @test4(i32 %n, i32 %m, i32 %x) { ... }

 

 

LoopInstSimplify Pass는 InstSimplify을 Loop에서 진행하는 과정입니다.
해서 주요 로직이 다음처럼 두 부분으로 나뉩니다.

1. Loop를 순환하며  로직

2. Simplify

 

이 중 2는 아마 -inst-combine에서 다루거나 혹은 별도로 다뤄야 할 것 같습니다. 많은 Pass에서 이 로직을 활용하기 때문입니다.
그 외에는 그렇게 어렵지 않습니다.

 

핵심 로직은 다음과 같습니다.

// local-study.cpp

  for (BasicBlock *BB : RPOT) {
    LLVM_DEBUG(dbgs() << "BB : "; BB->dump());
    for (Instruction &I : *BB) {
      LLVM_DEBUG(dbgs() << "inst : "; I.dump());
      if (_isInstructionTriviallyDead(&I, &TLI))
        LLVM_DEBUG(dbgs() << "Found Dead Instruction : "; I.dump());
      
      Value *V = simplifyInstruction(&I, SQ.getWithInstruction(&I));
      if (!V || !LI.replacementPreservesLCSSAForm(&I, V))
        continue;

      LLVM_DEBUG(dbgs() << "Simplified :"; V->dump());
      for (Use &U : llvm::make_early_inc_range(I.uses())) {
        auto *UserI = cast<Instruction>(U.getUser());
        U.set(V);

        if (!DT.isReachableFromEntry(UserI->getParent()))
          continue;
        if (auto *UserPI = dyn_cast<PHINode>(UserI))
          if (VisitedPHIs.count(UserPI)) {
            Next->insert(UserPI);
            continue;
          }
        assert((L->contains(UserI) || isa<PHINode>(UserI)) &&
               "Uses outside the loop should be PHI nodes due to LCSSA!");
        if (L->contains(UserI))
          ToSimplify->insert(UserI);
      }
      assert(I.use_empty() && "Should always have replaced all uses!");
      if (_isInstructionTriviallyDead(&I, &TLI)) {
        LLVM_DEBUG(dbgs() << "Found Dead Instruction : "; I.dump());
      }
    }
  }
}

 

1. BasicBlock의 Instruction을 순환하며 _isInstructionTriviallyDead 확인합니다.

_isInstructionTriviallyDead 는 DCE에서도 다뤘듯, 제거될 수 있는 Instruction인지 확인하는 과정입니다.

2. _isInstructionTriviallyDead 이 아닌 경우, Instruction을 Simplify 되는지 확인합니다.

 

3. Instruction의 Use의 값을 Simplify 된 값으로 교체합니다.

 

4. 재차 _isInstructionTriviallyDead 을 진행합니다.

-> 3의 영향으로 2와 4의 결과가 달라집니다.

 

예시) 다음은 실행 로그 일부입니다.

 

A. 대상 BasicBlock

[local-study]TestBody:542       BB : 
loop.inner:                                       ; preds = %loop.inner, %loop
  %j = phi i32 [ 0, %loop ], [ %j.next, %loop.inner ]
  %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ]
  %x.inner.add = add nsw i32 %x.inner.loop, 0
  %j.next = add nsw i32 %j, 1
  %j.cmp = icmp slt i32 %j.next, %m
  br i1 %j.cmp, label %loop.inner, label %loop.latch

                                                                   

[local-study]TestBody:544       inst :   %x.inner.add = add nsw i32 %x.inner.loop, 0

B. use_empty() 가 아니기에 첫 _isInstructionTriviallyDead 에서 False가 반환됩니다.
[local-study]_isInstructionTriviallyDead:493    use_empty :   %x.inner.add = add nsw i32 %x.inner.loop, 0

 

C. simplify 해봅니다.

[local-study]TestBody:554       Simplified :  %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ]

 

D. 현재 instruction의 Use 정보 입니다.

[local-study]TestBody:557       User I :  %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ]
[local-study]TestBody:558       Use :  %x.inner.add = add nsw i32 %x.inner.loop, 0
[local-study]TestBody:565       Visited :  %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.loop, %loop.inner ]

 

E. 여기까지 오면 이제 %x.inner.add = add nsw i32 %x.inner.loop, 0 는 Simplified Instruction %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ] 으로 바뀌었을 겁니다.

 

F. 이제 _isInstructionTriviallyDead 를 재차 돌려보면 side effect가 없는 명령이므로
[local-study]_wouldInstructionBeTriviallyDead:359       _wouldInstructionBeTriviallyDead :   %x.inner.add = add nsw i32 %x.inner.loop, 0
[local-study]_wouldInstructionBeTriviallyDead:402       mayHaveSideEffects :   %x.inner.add = add nsw i32 %x.inner.loop, 0

 

G. 다음처럼 제거 가능해집니다.
[local-study]TestBody:580       Found Dead Instruction :   %x.inner.add = add nsw i32 %x.inner.loop, 0

 

이후 실제 instruction이 제거되는 코드는 다음에 있습니다.

    // Delete any dead instructions found thus far now that we've finished an
    // iteration over all instructions in all the loop blocks.
    if (!DeadInsts.empty()) {
      Changed = true;
      RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, &TLI, MSSAU);
    }

 

 

LoopSimplify 분석은 이것으로 마치고, 다음의 주제에 대하 글을 추가하고 덧붙이도록 하겠습니다.

- Loop를 순환하며 탐색하는 방식

- Simplify 분석

 

 

opt -enable-new-pm=0 -load /work/mystudy/llvm-study/loop-simplify.so --loop-instsimplify-study loop-simplify.bc -o loop-simplify-passed.bin
[loop-instsimplify]runOnLoop:202        runOnLoop
[loop-instsimplify]simplifyLoopInst:89  Current :   %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
[loop-instsimplify]simplifyLoopInst:89  Current :   %x.add = add nsw i32 %x, 0
[loop-instsimplify]simplifyLoopInst:112 Simplified :i32 %x
[loop-instsimplify]simplifyLoopInst:89  Current :   %x.sub = sub i32 %x, 0
[loop-instsimplify]simplifyLoopInst:112 Simplified :i32 %x
[loop-instsimplify]simplifyLoopInst:89  Current :   %x.and = and i32 %x, -1
[loop-instsimplify]simplifyLoopInst:112 Simplified :i32 %x
[loop-instsimplify]simplifyLoopInst:89  Current :   %i.next = add nsw i32 %i, 1
[loop-instsimplify]simplifyLoopInst:89  Current :   %i.cmp = icmp slt i32 %i.next, %n
[loop-instsimplify]simplifyLoopInst:89  Current :   br i1 %i.cmp, label %loop, label %exit
[loop-instsimplify]simplifyLoopInst:94  use_empty:   br i1 %i.cmp, label %loop, label %exit
[loop-instsimplify]simplifyLoopInst:165 DeadInsts :   %x.add = add nsw i32 %x, 0
[loop-instsimplify]simplifyLoopInst:165 DeadInsts :   %x.sub = sub i32 %x, 0
[loop-instsimplify]simplifyLoopInst:165 DeadInsts :   %x.and = and i32 %x, -1
llvm-dis loop-simplify-passed.bin

 

[ RUN      ] LOCAL.wouldInstructionBeTriviallyDead1
[local-study]TestBody:542       BB :

loop:                                             ; preds = %loop.latch, %entry
  %i = phi i32 [ 0, %entry ], [ %i.next, %loop.latch ]
  %x.loop = phi i32 [ %x, %entry ], [ %x.inner.lcssa, %loop.latch ]
  %x.add = add nsw i32 %x.loop, 0
  br label %loop.inner

[local-study]TestBody:544       inst :   %i = phi i32 [ 0, %entry ], [ %i.next, %loop.latch ]
[local-study]_isInstructionTriviallyDead:493    use_empty :   %i = phi i32 [ 0, %entry ], [ %i.next, %loop.latch ]
[local-study]TestBody:544       inst :   %x.loop = phi i32 [ %x, %entry ], [ %x.inner.lcssa, %loop.latch ]
[local-study]_isInstructionTriviallyDead:493    use_empty :   %x.loop = phi i32 [ %x, %entry ], [ %x.inner.lcssa, %loop.latch ]
[local-study]TestBody:544       inst :   %x.add = add nsw i32 %x.loop, 0
[local-study]_isInstructionTriviallyDead:493    use_empty :   %x.add = add nsw i32 %x.loop, 0
[local-study]TestBody:552       Simplified :  %x.loop = phi i32 [ %x, %entry ], [ %x.inner.lcssa, %loop.latch ]
[local-study]_wouldInstructionBeTriviallyDead:359       _wouldInstructionBeTriviallyDead :   %x.add = add nsw i32 %x.loop, 0
[local-study]_wouldInstructionBeTriviallyDead:402       mayHaveSideEffects :   %x.add = add nsw i32 %x.loop, 0
[local-study]TestBody:575       Found Dead Instruction :   %x.add = add nsw i32 %x.loop, 0
[local-study]TestBody:544       inst :   br label %loop.inner
[local-study]_wouldInstructionBeTriviallyDead:359       _wouldInstructionBeTriviallyDead :   br label %loop.inner
[local-study]_wouldInstructionBeTriviallyDead:361       I->isTerminator() :   br label %loop.inner
[local-study]TestBody:542       BB :
loop.inner:                                       ; preds = %loop.inner, %loop
  %j = phi i32 [ 0, %loop ], [ %j.next, %loop.inner ]
  %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ]
  %x.inner.add = add nsw i32 %x.inner.loop, 0
  %j.next = add nsw i32 %j, 1

  %j.cmp = icmp slt i32 %j.next, %m
  br i1 %j.cmp, label %loop.inner, label %loop.latch

[local-study]TestBody:544       inst :   %j = phi i32 [ 0, %loop ], [ %j.next, %loop.inner ]
[local-study]_isInstructionTriviallyDead:493    use_empty :   %j = phi i32 [ 0, %loop ], [ %j.next, %loop.inner ]
[local-study]TestBody:544       inst :   %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ]
[local-study]_isInstructionTriviallyDead:493    use_empty :   %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ]
[local-study]TestBody:544       inst :   %x.inner.add = add nsw i32 %x.inner.loop, 0
[local-study]_isInstructionTriviallyDead:493    use_empty :   %x.inner.add = add nsw i32 %x.inner.loop, 0
[local-study]TestBody:552       Simplified :  %x.inner.loop = phi i32 [ %x.loop, %loop ], [ %x.inner.add, %loop.inner ]
[local-study]_wouldInstructionBeTriviallyDead:359       _wouldInstructionBeTriviallyDead :   %x.inner.add = add nsw i32 %x.inner.loop, 0
[local-study]_wouldInstructionBeTriviallyDead:402       mayHaveSideEffects :   %x.inner.add = add nsw i32 %x.inner.loop, 0
[local-study]TestBody:575       Found Dead Instruction :   %x.inner.add = add nsw i32 %x.inner.loop, 0
[local-study]TestBody:544       inst :   %j.next = add nsw i32 %j, 1
[local-study]_isInstructionTriviallyDead:493    use_empty :   %j.next = add nsw i32 %j, 1
[local-study]TestBody:544       inst :   %j.cmp = icmp slt i32 %j.next, %m
[local-study]_isInstructionTriviallyDead:493    use_empty :   %j.cmp = icmp slt i32 %j.next, %m
[local-study]TestBody:544       inst :   br i1 %j.cmp, label %loop.inner, label %loop.latch

[local-study]_wouldInstructionBeTriviallyDead:359       _wouldInstructionBeTriviallyDead :   br i1 %j.cmp, label %loop.inner, label %loop.latch
[local-study]_wouldInstructionBeTriviallyDead:361       I->isTerminator() :   br i1 %j.cmp, label %loop.inner, label %loop.latch
[local-study]TestBody:542       BB :
loop.latch:                                       ; preds = %loop.inner
  %x.inner.lcssa = phi i32 [ %x.inner.loop, %loop.inner ]
  %i.next = add nsw i32 %i, 1
  %i.cmp = icmp slt i32 %i.next, %n
  br i1 %i.cmp, label %loop, label %exit

[local-study]TestBody:544       inst :   %x.inner.lcssa = phi i32 [ %x.inner.loop, %loop.inner ]
[local-study]_isInstructionTriviallyDead:493    use_empty :   %x.inner.lcssa = phi i32 [ %x.inner.loop, %loop.inner ]
[local-study]TestBody:544       inst :   %i.next = add nsw i32 %i, 1
[local-study]_isInstructionTriviallyDead:493    use_empty :   %i.next = add nsw i32 %i, 1
[local-study]TestBody:544       inst :   %i.cmp = icmp slt i32 %i.next, %n
[local-study]_isInstructionTriviallyDead:493    use_empty :   %i.cmp = icmp slt i32 %i.next, %n
[local-study]TestBody:544       inst :   br i1 %i.cmp, label %loop, label %exit
[local-study]_wouldInstructionBeTriviallyDead:359       _wouldInstructionBeTriviallyDead :   br i1 %i.cmp, label %loop, label %exit
[local-study]_wouldInstructionBeTriviallyDead:361       I->isTerminator() :   br i1 %i.cmp, label %loop, label %exit
[       OK ] LOCAL.wouldInstructionBeTriviallyDead1 (1188 ms)
[----------] 1 test from LOCAL (1190 ms total)