computeKnownBitsFromContext

https://die4taoam.tistory.com/147

computeKnownBits & KnownBits 관련 예제

 

 

computeKnownBits

ㄴ computeKnownBitsFromContext

    ㄴ computeKnwonBitsFromCond

 

 

computeKnownBitsFromContext 는 문맥상에서 비트를 추론해내는 함수이며, computeKnownBits 에서 가장 마지막에 시도되는 KnownBits 추론 기능을 담당한다.

 

computeKnownBitsFromContext 는 위 그림처럼, 추론에 사용되는 데이터에 따라 DomConditionCache 를 활용하는 방법과 AssumptionCache를 활용하는 방법으로 나뉜다.

 

1. DomConditionCache 활용 방법

 

DomConditionCache 에 대한 설명은 다음 글을 참고 바랍니다.

https://die4taoam.tistory.com/150

[TODO] DomConditionCache

 

  if (Q.DC && Q.DT) {
    // Handle dominating conditions.
    LLVM_DEBUG(dbgs() << "condition \n");
    for (BranchInst *BI : Q.DC->conditionsFor(V)) {
      LLVM_DEBUG(dbgs() << "condition 0\n");
      BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0));
      if (Q.DT->dominates(Edge0, Q.CxtI->getParent())) {
        LLVM_DEBUG(dbgs() << "condition 1\n");
        computeKnownBitsFromCond(V, BI->getCondition(), Known, Depth, Q,
                                 /*Invert*/ false);
      }

      BasicBlockEdge Edge1(BI->getParent(), BI->getSuccessor(1));
      if (Q.DT->dominates(Edge1, Q.CxtI->getParent())) {
        LLVM_DEBUG(dbgs() << "condition 2\n");
        computeKnownBitsFromCond(V, BI->getCondition(), Known, Depth, Q,
                                 /*Invert*/ true);
      }
    }

 

KnownBits를 찾고자 하는 대상 V 에 대해 DomConditionCache에 등록된 BranchInst 이 존재하는지 확인하여, BranchInst 의 Condition을 통해 KnownBit를 찾는다.

 

예를 들어, 다음과 같은 IR 이 있다고 할 때,

; Function Attrs: nounwind uwtable
define dso_local i32 @test(i32 noundef %x, i32 noundef %y) #0 {
entry:
  %and = and i32 %x, %y
  %cmp = icmp eq i32 %and, -1
  br i1 %cmp, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
  %or = or i32 %x, %y
  br label %cond.end

cond.false:                                       ; preds = %entry
  %xor = xor i32 %x, %y
  br label %cond.end

cond.end:                                         ; preds = %cond.false, %cond.true
  %cond = phi i32 [ %or, %cond.true ], [ %xor, %cond.false ]
  ret i32 %cond
}

 

%or = or i32 %x, %y 에 대한 최적화 수행 과정 중에 하나는,

X와 Y의 KnownBits를 추산해 X | Y 연산을 최적화 하는 시도한다.

 

여기서 X와 Y는 AND 연산의 피연산자들이고,

BranchInst 을 DomConditionCache에 등록할 때, Condition이 AND 연산인 경우 X, Y에 대한 Affected 로 등록되게 된다.

 

이 과정을 하는 코드는 다음과 같다.

      if (ICmpInst::isEquality(Pred)) {
        if (match(B, m_ConstantInt())) {
          LLVM_DEBUG(dbgs() << "ConstantInt : ";B->dump()); 
          Value *Y;
          // (X & C) or (X | C) or (X ^ C).
          // (X << C) or (X >>_s C) or (X >>_u C).
          if (match(A, m_BitwiseLogic(m_Value(X), m_ConstantInt())) ||
              match(A, m_Shift(m_Value(X), m_ConstantInt())))
            AddAffected(X);
          else if (match(A, m_And(m_Value(X), m_Value(Y))) ||
                   match(A, m_Or(m_Value(X), m_Value(Y))) ||
                   (match(A, m_Xor(m_Value(X), m_Value(Y))) &&
                    match(B, m_AllOnes()))) { 
            LLVM_DEBUG(dbgs() << "register : "; A->dump();B->dump()); 
            AddAffected(X);
            AddAffected(Y);

 

이를 통해 Q.DT.ConditionFor(V) 를 호출하면 이 때 등록해 둔 AND 포함 등록된 BranchInst 의 Condition들을 순환탐색 할 수 있다. %or = or i32 %x, %y  로 돌아가면, %or 피연산자 X, Y 에 영향을 미치는 Condition으로 AND가 등록되게 될 것이다.

 

X & Y == -1 일 때 X의 KnownBits를 알아내고자 하는 과정이 computeKnownBitsFromCond 의 호출을 통해 이뤄지게 된다.

 

computeKnownBitFromCond 에 대해서는 여기서 더 자세한 내용을 다룬다.

https://die4taoam.tistory.com/170

computeKnownBitsFromCond

 

 

결과적으로 X&Y == -1 일 때는, X = -1, Y = -1 이 성립하므로 (*아직 안됨. 패치 예정.)

X에 대한 KnownBits는 Known.One 은 AllOnes(), Known.Zero 는 0이 될 것이며 Y 도 마찬가지다.

둘의 KnownBits 가 확보되면 이는 KnownBits 간의 연산을 통해 OR의 KnownBits를 산출할 수 있으므로, X | Y 를 치환 = 최적화 할 수 있게 된다.

 

 

2. AssumptionCache

(TBD)