[TODO] DomConditionCache

1. 기능 설명

2. 내부 함수 설명

3. 활용 설명

 

 

https://github.com/ParkHanbum/llvm-project/commit/d77067d08a3f56dc2d0e6c95bd2852c943df743a

[ValueTracking] Add dominating condition support in computeKnownBits(… · ParkHanbum/llvm-project@d77067d

 

LLVM 최근 패치로 DomConditionCache가 최근 추가되었습니다.

이에 대한 분석 입니다.

 

DC(DomConditionCache) 는 InstructionCombining에서 visitBranchInst를 통해 BranchInst를 등록합니다.

// InstructionCombining.cpp:3110

DC.registerBranch(&BI);

return nullptr;

}

 

내부 구현은 DomConditionCache.cpp에 등록되어 있습니다.

 

BranchInst으로 인해 영향을 받을 수 있는 변수들에 BranchInst를 등록합니다.

registerBranch에서는 영향을 받는 변수들에 해당 Branch를 추가합니다.

void DomConditionCache::registerBranch(BranchInst *BI) {

assert(BI->isConditional() && "Must be conditional branch");

SmallVector<Value *, 16> Affected;

findAffectedValues(BI->getCondition(), Affected);

for (Value *V : Affected) {

auto &AV = AffectedValues[V];

if (!is_contained(AV, BI))

AV.push_back(BI);

}

}

 

영향을 받는 변수를 골라내는 과정은 다음과 같습니다.

Value *A;

if (match(Cond, m_ICmp(Pred, m_Value(A), m_Constant()))) {

AddAffected(A);

 

변수를 상수와 비교하는 경우, 변수는 무조건 영향을 받는 변수입니다.

 

if (ICmpInst::isEquality(Pred)) {

Value *X;

// (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 {

Value *X;

// Handle (A + C1) u< C2, which is the canonical form of A > C3 && A < C4.

if (match(A, m_Add(m_Value(X), m_ConstantInt())))

AddAffected(X);

}

 

- 변수 A가 변수와 상수의 비트 연산, 쉬프트 연산 인 경우 변수 X는 영향받는 변수에 포함됩니다.

- 변수 A가 변수와 상수의 덧셈인 경우 변수 X는 영향을 받는 변수에 포함됩니다.

 

 

DC는 다음과 같이 활용됩니다.

 

ValueTracking.cpp : computeKnownBitsFromContext

if (Q.DC && Q.DT) {

// Handle dominating conditions.

for (BranchInst *BI : Q.DC->conditionsFor(V)) {

auto *Cmp = dyn_cast<ICmpInst>(BI->getCondition());

if (!Cmp)

continue;

BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0));

if (Q.DT->dominates(Edge0, Q.CxtI->getParent()))

computeKnownBitsFromCmp(V, Cmp->getPredicate(), Cmp->getOperand(0),

Cmp->getOperand(1), Known, Q);

BasicBlockEdge Edge1(BI->getParent(), BI->getSuccessor(1));

if (Q.DT->dominates(Edge1, Q.CxtI->getParent()))

computeKnownBitsFromCmp(V, Cmp->getInversePredicate(),

Cmp->getOperand(0), Cmp->getOperand(1), Known,

Q);

}

if (Known.hasConflict())

Known.resetAll();

}

 

1. 변수 V에 영향을 주는 BranchInst 들을 순차탐색하면서

2. computeKnownBitsFromCmp 를 통해 KnownBit 를 구성합니다.

 

예를 들어, BranchInst를 등록할 때 조건을 보면, BI의 조건을 보고 등록하니까

X < 100 같은 비교문일 경우 X가 영향을 받는 변수로, X < 100 를 조건으로 갖는 BI 가 등록됩니다.

그러면 X < 100 이란 조건을 가지고 X의 KnownBit 를 구성할 수 있습니다.

 

 

KnownBits에 대해서는 다음 글 참고 바랍니다. (작성중)

https://die4taoam.tistory.com/147

computeKnownBits & KnownBits 관련 예제