[TODO] GVN

 

 

* 다른 이슈 스터디 차원에서 먼저 일부 GVN 로직을 다룹니다.

;*** IR Dump After MergedLoadStoreMotionPass on test1 ***
; Function Attrs: mustprogress nofree norecurse nosync nounwind readnone uwtable willreturn
define dso_local zeroext i1 @test1(i1 noundef zeroext %a, i1 noundef zeroext %b) local_unnamed_addr #0 {
entry:
  %or5 = or i1 %a, %b
  br i1 %or5, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
  %xor7 = xor i1 %a, %b
  br label %cond.end

cond.false:                                       ; preds = %entry
  %and6 = and i1 %a, %b
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %cond.in = phi i1 [ %xor7, %cond.true ], [ %and6, %cond.false ]
  ret i1 %cond.in
}

 

위의 IR 을 GVN pass를 돌리면 다음같은 메시지를 확인할 수 있습니다.

 

$ build-llvm-trunk/bin/opt --passes=gvn gvn.ll -debug
Args: build-llvm-trunk/bin/opt --passes=gvn gvn.ll -debug 
WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

GVN iteration: 0
Replace dominated use of 'i1 %b' with i1 false in   %and6 = and i1 %a, %b
Replace dominated use of 'i1 %a' with i1 false in   %and6 = and i1 %a, false
GVN removed:   %and6 = and i1 false, false
GVN iteration: 1

 

 

여기서 주목할 곳은 다음의 메시지입니다.

Replace dominated use of 'i1 %b' with i1 false in   %and6 = and i1 %a, %b
Replace dominated use of 'i1 %a' with i1 false in   %and6 = and i1 %a, false

 

해당 로직과 관련있는 코드는 다음과 같습니다.

 

1. GVN.cpp 2466

    // If "A && B" is known true then both A and B are known true.  If "A || B"
    // is known false then both A and B are known false.
    Value *A, *B;
    if ((isKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
        (isKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
      Worklist.push_back(std::make_pair(A, RHS));
      Worklist.push_back(std::make_pair(B, RHS));
      continue;
    }

 

익히 잘 알려진 비트연산인 A&B==1, A|B==0 입니다.
이 두 비트연산은 A&B==1 일 경우 A=1, B=1 이고 A|B==0 일 경우 A=0, B=0 입니다.
이 경우, Worklist 에 추가합니다.

 

우리가 타겟한 코드에서는 %or5 = or i1 %a, %b 이므로 처럼 <%a, 0>, <%b, 0> 이 추가됩니다.

(gdb) p A->dump()
i1 %a
$1 = void
(gdb) p RHS->dump()
i1 false
$2 = void

(gdb) p B->dump()
i1 %b
$3 = void

 

2. GVN.cpp 2449

    // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope.  As
    // LHS always has at least one use that is not dominated by Root, this will
    // never do anything if LHS has only oneLHS use.
    if (!LHS->hasOneUse()) {
      unsigned NumReplacements =
          DominatesByEdge
              ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
              : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());

      Changed |= NumReplacements > 0;
      NumGVNEqProp += NumReplacements;
      // Cached information for anything that uses LHS will be invalid.
      if (MD)
        MD->invalidateCachedPointerInfo(LHS);
    }

 

그리고 worklist 를 처리하다보면, 위에서 추가했던 Pair 에 대한 처리를 이곳에서 해주게 됩니다.

 

Breakpoint 2, llvm::GVNPass::propagateEquality (this=0x555562912fe8, LHS=0x555562914998, RHS=0x555562919aa0, Root=..., DominatesByEdge=true) at /home/m/llvm-trunk/llvm/lib/Transforms/Scalar/GVN.cpp:2455
2455               ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
(gdb) p LHS->dump() 
i1 %b
$5 = void
(gdb) p RHS->dump()
i1 false
$6 = void

 

여기가 중요합니다.

propagation 용어의 뜻은, 논리를 푸는 과정에서 명제로 밝혀진 값을 데이터 전반에 반영시키는 과정을 말합니다.
컴파일러 뿐 아니라, 논리로직을 구성할때 propagation은 자주 등장하는 용어입니다.

 

코드는 다음과 같습니다.

template <typename RootType, typename DominatesFn>
static unsigned replaceDominatedUsesWith(Value *From, Value *To,
                                         const RootType &Root,
                                         const DominatesFn &Dominates) {
  assert(From->getType() == To->getType());

  unsigned Count = 0;
  for (Use &U : llvm::make_early_inc_range(From->uses())) {
    if (!Dominates(Root, U))
      continue;
    LLVM_DEBUG(dbgs() << "Replace dominated use of '";
               From->printAsOperand(dbgs());
               dbgs() << "' with " << *To << " in " << *U.getUser() << "\n");
    U.set(To);
    ++Count;
  }
  return Count;
}

 

DominateByEdge라고 표현된 DominateTree의 Edge까지 Uses들에 대한 propagation을 하는 것 입니다.

 

샘플의 Domtree 입니다.