LoopOptimization Pass Tutorial

https://llvm.org/devmtg/2018-10/slides/Kruse-LoopTransforms.pdf

https://www.youtube.com/watch?v=3pRhvQi7Z10&ab_channel=LLVM 

 

https://github.com/kitbarton/llvm-project/pull/1

LoopOptTutorial: Basic loop optimization template [STEP1] by etiotto · Pull Request #1 · kitbarton/llvm-project

각 PR마다 마지막에 멘션 되어 있는 링크를 따라가면 1->2->3->4->5 따라갈 수 있다.

 

 

# LLVM 과 분리되어 있는 튜토리얼 프로젝트

https://github.com/ParkHanbum/mystudy/commit/d61bce8b0c9389bba5804026103d11a256334465

Merge pull request #1 from ParkHanbum/LoopOptimization_study · ParkHanbum/mystudy@d61bce8

위 튜토리얼은 LLVM 내부 opt pass 로 기능하여, 분리된 프로젝트로 만들면서 몇가지 덧붙여놨습니다.

 

 

 

# LOOP CLONNING

< Loop 복붙 후 >	< Loop 원본 >

LoopOptimizationTutorial 의 두 번째 커밋은 Loop를 복붙하는 내용이다.

LLVM 문서에 나와있는 문서를 참고 : https://llvm.org/docs/LoopTerminology.html

LLVM Loop Terminology (and Canonical Forms) — LLVM 18.0.0git documentation

LoopLatch 관련 글을 적어놓은게 있는데 지금 내용을 보니 크게 도움이 될 것 같진 않다(...)

https://die4taoam.tistory.com/100

LoopLatch

 

각 코드의 역할은, 로그 메시지를 통해 어떤 변화가 있었는지 비교하는 것으로 확인 가능할 것이므로 생략.

Predecessor에 대한 설명은 다음 링크를 참고 : [TBD]

 

이번 커밋 :

https://github.com/ParkHanbum/mystudy/commit/b79b944a95e33faea260b1e2f0b33fce74b1295e

 

*. SplitBlock을 사용하여 변한 부분.

j_header.preheader:                               ; preds = %i_header   br label %j_header

j_header.preheader:                               ; preds = %i_header   br label %j_header.preheader.split j_header.preheader.split:                         ; preds = %j_header.preheader   br label %j_header

 

다음 부분이 정상 수행되지 않고 에러 메시지를 보여준다.

 

opt: /work/llvm-project/llvm/include/llvm/Support/GenericLoopInfoImpl.h:334: void llvm::LoopBase<N, M>::verifyLoop() const [with BlockT = llvm::BasicBlock; LoopT = llvm::Loop]: Assertion `std::any_of(GraphTraits<BlockT *>::child_begin(BB), GraphTraits<BlockT *>::child_end(BB), [&](BlockT *B) { return contains(B); }) && "Loop block has no in-loop successors!"' failed.

 

추가해 놓은 로그 메시지를 확인하면 다음 같은 구문이 보일 것이다.

i_header:                                         ; preds = %i_latch, %entry   %i = phi i64 [ %inci, %i_latch ], [ 0, %entry ]   %exitcond5 = icmp ne i64 %i, 100   br i1 %exitcond5, label %j_header.preheader, label %exit j_header.preheader:                               ; preds = %i_header   br label %j_header.preheader.split j_header.preheader.split:                         ; preds = %j_header.preheader   br label %j_header

i_header:                                         ; preds = %i_latch, %entry   %i = phi i64 [ %inci, %i_latch ], [ 0, %entry ]   %exitcond5 = icmp ne i64 %i, 100   br i1 %exitcond5, label %j_header.preheader, label %exit j_header.preheader:                               ; preds = %i_header   br label %j_header.preheader.split    j_header.preheader.splitClonedLoop:               ; No predecessors!   br label %j_headerClonedLoop

[loop-opt-tutorial]cloneLoopInHalf:213 Create new loop: j_headerClonedLoop After cloning loop:

[loop-opt-tutorial]cloneLoopInHalf:219 After instruction remapping:

j_header.preheader.splitClonedLoop:               ; No predecessors!
  br label %j_headerClonedLoop

 

이 부분에 문제가 있다.

일단 문제가 수정된 코드로 생성한 도면을 보자, 훨씬 이해하기 쉽다.

 

이번에 추가된 코드는 전과 다르게 SplitBlock을 사용하였고 때문에 preheader - preheader.split으로 구조가 바뀐다. 또한 이번에 루프를 복사할 곳은 preheader.split 앞부분이다. 그래서 전에는 preheader의 predecessor 인 i_header에 존재하는 preheader를 변경하는 것이 아니라, preheader에 존재하는 preheader.split을 복사한 루프의 preheader인  preheader.splitedClone으로 변경해야 한다.

 

 

 

처음 보는 LoopBounds 라는 API 가 눈에 띄어서 어떤 연유로 추가됐는지 링크를 첨부합니다.

LoopBounds : 2d0896c1cb90243f12df698e84458016c0c121dc

https://reviews.llvm.org/D60565

⚙ D60565 [LOOPINFO] Extend Loop object to add utilities to get the loop bounds, step, and loop induction variable.

 

 

# Loop Split and Manipulation

loop_nest origin	loop_nest after

LoopOptTutorial 에서는 Loop에 한해 주요한 로직을 다루는 방식을 보여준다.

 

Instruction *LoopSplit::computeSplitPoint(const Loop &L,
                                          Instruction *InsertBefore) const {
  std::optional<Loop::LoopBounds> Bounds = L.getBounds(SE);
  assert(Bounds.has_value() && "Unable to retrieve the loop bounds");

  Value &IVInitialVal = Bounds->getInitialIVValue();
  Value &IVFinalVal = Bounds->getFinalIVValue();
  auto *Sub =
    BinaryOperator::Create(Instruction::Sub, &IVFinalVal, &IVInitialVal, "", InsertBefore);

  return BinaryOperator::Create(Instruction::UDiv, Sub,
                                ConstantInt::get(IVFinalVal.getType(), 2),
                                "", InsertBefore);
}

위에서 소개한 Loop의 getBounds를 통해 얻은 루프의 중요 정보를 통해 다음 IR을 추가하는 코드이다.

%0 = sub i64 100, 0
%1 = udiv i64 %0, 2

루프는 반복문이지 않은가? 반복 횟수보다 중요한 건 없을 것이다.
%1은 100을 2로 나눈 50 이 저장된다.

 

  Loop *ClonedLoop = cloneLoopInHalf(L, *InsertBefore, *Preheader);
  Preheader = ClonedLoop->getLoopPreheader();

  // Modify the upper bound of the cloned loop.
  ICmpInst *LatchCmpInst = getLatchCmpInst(*ClonedLoop);
  LatchCmpInst->setOperand(1, Split);

위에서 추가한 IR은 Instruction Split 이고 이를 LatchCmpInst 의 1번째 operand 100과 교체한다.

%exitcond = icmp ne 164 incj, 100

%exitcondClonedLoop = icmp ne i64 %incjClonedLoop, %1

이렇게 되어, 첫 번째 루프이자 우리가 Split 하고 Clone 해서 만든 블록은 50까지 반복하게 된다.

 

다음 순서는 Original Block의 InductionVariable을 찾아 변경하는 것이다.

  // Modify the lower bound of the original loop.
  PHINode *IndVar = L.getInductionVariable(SE);
  IndVar->setIncomingValueForBlock(L.getLoopPreheader(), Split);

다음으로 Loop의 InductionVariable을 찾아서 incoming block을 우리가 Split으로 추가한 LoopHeader로 바꿔준다.

%j1 = phi i64 [ %1, %j_header.preheader.split ], [ %incj, %j_latch ]

우리가 복사한 원본 Loop의 InductionVariable 인  PHI 노드의 Incoming block인 [ %1, %j_header.preheader.split ] 에서 %1이 원래는 0이 존재하던 것을 Instruction Split으로 바꾸는 것을 통해 %1로 바꾸는 작업이 되겠다.

 

이렇게 함으로써 우리는 0~100까지 반복하는 루프문을 쪼개서 0~50 그리고 50~100까지 반복하는 루프문을 만들었다.

1. 루프문의 반복 횟수를 다루고

2. 루프를 쪼개는 방법을 다뤘다.

 

 

# DominatorTree

https://github.com/ParkHanbum/mystudy/commit/0a96c886931550a8aa59cbf56321a40cef9efdc2

LoopOptTutorial: Update detail usage of domtree · ParkHanbum/mystudy@0a96c88

 

다음은 루프를 만졌을 때, DOMTREE를 업데이트하는 방식에 대한 커밋이다.

https://die4taoam.tistory.com/134

[TODO] DominatorTree

DominatorTree에 대한 상세한 글은 위 링크를 참고(아직 작성예정).

 

이번 커밋부터 make로 DOMTREE_DETAIL_LEVEL 값을 지정할 수 있으며 레벨 별 설명은 다음과 같다.

0 : Domtree 재계산 -> DT.recalculate(F)

1 : Domtree 국지적 갱신

2 : Domtree 국지적 & 지연 갱신

 

먼저 DOMTREE 를 간략하게 살펴보자.
간단한 DOMTREE 변화를 살펴보기 위해 예제는 simple.ll 을 사용했다.

Simple.ll CFG & Domtree
Simple.ll LoopOptTutorial CFG & Domtree

오리지널과 우리가 최적화를 한 DOMTREE는 5가지 변화가 생긴다.
이는 DOMTREE_DETAIL_LEVEL=3 옵션으로 실행해보면 확인할 수 있으며 다음과 같다.

 

[loop-opt-tutorial]cloneLoop:393 DETAIL LEVEL : 3
[loop-opt-tutorial]updateDominatorTree:246 KIT: DomTree Updates: 
  Insert %entry -> %entry.splitClonedLoop
  Insert %entry.splitClonedLoop -> %bodyClonedLoop
  Insert %bodyClonedLoop -> %latchClonedLoop
  Delete %entry -> %entry.split
  Insert %latchClonedLoop -> %entry.split

 

 

이 중, 원래 Loop에 split Clone Loop 가 추가되어 변경된 부분은 이 두 부분이다.

1. 원본의 %entry->%entry.split 을 %entry->%entry.splitCloneLoop 로 변경

  Insert %entry -> %entry.splitClonedLoop

  Delete %entry -> %entry.split

 

2. 원본의 %entry -> %entry.split 을 복사한 %latchClonedLoop -> %entry.split 로 변경

  Insert %latchClonedLoop -> %entry.split

 

나머지는 복사한 내부 블록들에 대한 Domtree를 변경하는 부분이다.

  Insert %entry.splitClonedLoop -> %bodyClonedLoop
  Insert %bodyClonedLoop -> %latchClonedLoop

 

 

이번 커밋에서 다루고자 하는 것은 DominatorTree를 '효율적'으로 업데이트 하는 방식인데, 2019년에 소개한 영상을 보면 이 시기에 DOMTREE를 업데이트 하기 위한 인터페이스들이 추가된 것 같다. 즉, 앞으로는 이런 방식으로 DOMTREE를 업데이트 하지 않으면 '야 너 돔트리 그런식으로 갱신하지말고 이렇게 좀 해.' 라는 커멘트가 달리게 될 것이라는 뜻이다.

 

돔트리를 지연 갱신하는 코드는 다음과 같이 정형화된 방식이므로, 이해하고 이후에는 복붙하면 될 것이다.

 

1. 잘못된 돔 트리 업데이트 방식

  for (BasicBlock *BB : ClonedLoop.getBlocks())
    TreeUpdates.emplace_back(
      DominatorTree::UpdateType(DominatorTree::Insert, NewPH, BB));

[loop-opt-tutorial]updateDominatorTree:246 KIT: DomTree Updates: 
  Insert %entry -> %entry.splitClonedLoop
  Insert %entry.splitClonedLoop -> %bodyClonedLoop
  Insert %entry.splitClonedLoop -> %latchClonedLoop

 

[loop-opt-tutorial]cloneLoop:396 Dominator Tree: =============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 3 slow queries.
  [1] %entry {4294967295,4294967295} [0]
    [2] %i_header {4294967295,4294967295} [1]
      [3] %exit {4294967295,4294967295} [2]
      [3] %j_header.preheader {4294967295,4294967295} [2]
        [4] %j_header.preheader.splitClonedLoop {4294967295,4294967295} [3]
          [5] %j_bodyClonedLoop {4294967295,4294967295} [4]
          [5] %j_latchClonedLoop {4294967295,4294967295} [4]
            [6] %j_header.preheader.split {4294967295,4294967295} [5]
              [7] %j_body {4294967295,4294967295} [6]
                [8] %j_latch {4294967295,4294967295} [7]
                  [9] %i_latch {4294967295,4294967295} [8]

 

2. 잘된 돔 트리 업데이트 방식

  for (BasicBlock *BB : OrigLoop.getBlocks()) {
    BasicBlock *IDomBB = DT.getNode(BB)->getIDom()->getBlock();
    assert(VMap[IDomBB] && "Expecting immediate dominator of loop block to have been mapped.");
    TreeUpdates.emplace_back(DominatorTree::UpdateType(
        DominatorTree::Insert, cast<BasicBlock>(VMap[IDomBB]), cast<BasicBlock>(VMap[BB])));
  }

 

[loop-opt-tutorial]updateDominatorTree:246 KIT: DomTree Updates: 
  Insert %entry -> %entry.splitClonedLoop
  Insert %entry.splitClonedLoop -> %bodyClonedLoop
  Insert %bodyClonedLoop -> %latchClonedLoop

[loop-opt-tutorial]cloneLoop:396 Dominator Tree: =============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 3 slow queries.
  [1] %entry {4294967295,4294967295} [0]
    [2] %i_header {4294967295,4294967295} [1]
      [3] %exit {4294967295,4294967295} [2]
      [3] %j_header.preheader {4294967295,4294967295} [2]
        [4] %j_header.preheader.splitClonedLoop {4294967295,4294967295} [3]
          [5] %j_bodyClonedLoop {4294967295,4294967295} [4]
            [6] %j_latchClonedLoop {4294967295,4294967295} [5]
              [7] %j_header.preheader.split {4294967295,4294967295} [6]
                [8] %j_body {4294967295,4294967295} [7]
                  [9] %j_latch {4294967295,4294967295} [8]
                    [10] %i_latch {4294967295,4294967295} [9]
Roots: %entry 

이후 갱신해주면 된다.

  DTU.applyUpdates(TreeUpdates);
  DTU.flush();

검증 또한 필수...려나?

  L.verifyLoop();
  NewLoop->verifyLoop();
  if (L.getParentLoop())
    L.getParentLoop()->verifyLoop();

  LI.verify(DT);