computeKnownBits & KnownBits 관련 예제

 

computeKnownBits 

https://llvm.org/doxygen/ValueTracking_8cpp.html#a903bd19e9d31beff55b22fe86111639e

 

Determine which bits of V are known to be either zero or one and return them.

void	computeKnownBits (const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
	Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOne bit sets.
KnownBits	computeKnownBits (const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
	Returns the known bits rather than passing by reference.
KnownBits	computeKnownBits (const Value *V, const APInt &DemandedElts, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
	Returns the known bits rather than passing by reference.
KnownBits	computeKnownBits (const Value *V, const APInt &DemandedElts, unsigned Depth, const SimplifyQuery &Q)
	Determine which bits of V are known to be either zero or one and return them.
KnownBits	computeKnownBits (const Value *V, unsigned Depth, const SimplifyQuery &Q)
	Determine which bits of V are known to be either zero or one and return them.
void	computeKnownBits (const Value *V, KnownBits &Known, unsigned Depth, const SimplifyQuery &Q)

 

 

 

예1)

define i1 @test_and1(i32 %x, i32 %n) {
; CHECK-LABEL: @test_and1(
; CHECK-NEXT:    [[NN:%.*]] = and i32 [[N:%.*]], 2147483647
; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[NN]], [[X:%.*]]
; CHECK-NEXT:    ret i1 [[C]]
;
  %nn = and i32 %n, 2147483647
  %a = icmp sge i32 %x, 0
  %b = icmp slt i32 %x, %nn
  %c = and i1 %a, %b
  ret i1 %c
}

 

(X s>= 0) & (X s< (Y & MAX_VALUE_SIGNED(Y))  --> (Y & MAX_VALUE_SIGNED(Y)) u< X

요렇게 최적화를 할 수 있으려면 조건이 (X s< (Y & MAX_VALUE_SIGNED(Y)) 에서 음수가 아니여야 한다.

 

이걸 체크하고자 한다면, %nn 의 KnownBit를 구해서, 음수 비트가 세팅되어 있는지 확인해야 한다.

 

// X s< 0 | X s>= (Y & SIGNED_MAX(Y)) -> (Y & SIGNED_MAX(Y)) u=< X
    // 
    if (match(&I, m_CombineOr(m_c_Or(m_Value(X), m_Value(Y)),
                              m_c_And(m_Value(X), m_Value(Y))))) {
      LLVM_DEBUG(dbgs() << "Match or/and\n");

      Value *A, *B, *RangeEnd;
      const APInt *RangeStart;
      if (match(X, m_c_ICmp(Pred0, m_Value(A), m_APInt(RangeStart))) &&
          match(Y, m_c_ICmp(Pred1, m_Specific(A), m_Value(RangeEnd)))) {
        LLVM_DEBUG(dbgs() << "RangeStart : " << *RangeStart << "\n");
        KnownBits Known =
            computeKnownBits(RangeEnd, DL, /*Depth=*/0, &AC, &I, &DT);
        LLVM_DEBUG(dbgs() << "RangeEnd bits :"; Known.print(errs()); dbgs() << Known.isNonNegative() << "\n");
      }
    }

 

단순화 한 예제 코드를 음수비트가 세팅됐는지 확인하는 코드이다.

 

[simplify-study]TestBody:1128	test_and1
[simplify-study]knownBitTest:1101	Match or/and
[simplify-study]knownBitTest:1107	RangeStart : 0
[simplify-study]knownBitTest:1110	RangeEnd bits :{Zero=-2147483648, One=0}1
[simplify-study]TestBody:1128	test_or1
[simplify-study]knownBitTest:1101	Match or/and
[simplify-study]knownBitTest:1107	RangeStart : 0
[simplify-study]knownBitTest:1110	RangeEnd bits :{Zero=-2147483648, One=0}1
[simplify-study]TestBody:1128	test_or2
[simplify-study]knownBitTest:1101	Match or/and
[simplify-study]knownBitTest:1107	RangeStart : -1
[simplify-study]knownBitTest:1110	RangeEnd bits :{Zero=-2147483648, One=0}1

 

KnownBits는 둘로 구성되어 있는데, Zero와 One이다. 각기 0인 비트와 One인 비트로 구성되어 있다.

여기서 Zero가 -2147483648로 된 이유는, 테스트에서 2147483647과 And 연산을 했기 때문이다.
결과로 오직 SIGN BIT 만이 0으로 세팅될 수 있어서 Zero의 Signbit를 검사하는 isNonNegative() 함수는 True 가 된다.

 

 

 

computeKnownBitsFromContext

이름 그대로 Context에서 computeKnownBits를 찾는 함수.

최상단에는 최근에 추가된 DomConditionCache 가 활용된다.

if (!Q.CxtI)

return;

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();

 

 

https://die4taoam.tistory.com/150

[TODO] DomConditionCache

 

 

// ; 00001011 ; 11

// ; 00010100 ; 20

// ; 01101011 ; 107

// ; 10010100 ; 108

// opt1 opt2 검사

// 1. opt1 를 l 부터 (최상위 1) +1 까지 비트가 1인지 체크

// 2. 1에서 0을 만날때 같은 위치에 opt2의 비트가 1인지 체크

// -> 1에 not하고 2의 1이 나올때까지 비트를 제거하고 같은지 비교.

LLVM_DEBUGM("test : " << Op0KB.countMaxTrailingZeros());

LLVM_DEBUGM("test : " << Op1KB.countMaxTrailingZeros());

LLVM_DEBUGM("test : " << Op0KB.countMaxTrailingOnes());

LLVM_DEBUGM("test : " << Op1KB.countMaxTrailingOnes());

LLVM_DEBUGM("test : " << Op0KB.countMaxLeadingZeros());

LLVM_DEBUGM("test : " << Op1KB.countMaxLeadingZeros());

LLVM_DEBUGM("test : " << Op0KB.countMaxLeadingOnes());

LLVM_DEBUGM("test : " << Op1KB.countMaxLeadingOnes());

 

	countMaxTrailingZeros	countMaxTrailingOnes	countMaxLeadingZeros	countMaxLeadingOnes
00001011	0	2	4	0
00010100	2	0	3	0

 

구현내용

/// Returns the maximum number of trailing zero bits possible.

unsigned countMaxTrailingZeros() const { return One.countr_zero(); }

/// Returns the maximum number of trailing one bits possible.

unsigned countMaxTrailingOnes() const { return Zero.countr_zero(); }

/// Returns the maximum number of leading zero bits possible.

unsigned countMaxLeadingZeros() const { return One.countl_zero(); }

/// Returns the maximum number of leading one bits possible.

unsigned countMaxLeadingOnes() const { return Zero.countl_zero(); }

 

TrailingsZeros = One.countr_zero  -> One의 오른쪽에서 "0" 카운팅 -> One은 1로 세팅된 비트.

-> 0로 세팅된 비트를 오른쪽부터 카운팅

TrailingsOnes = Zero.countr_zero -> Zero의 오른쪽부터 "0" 카운팅 -> Zero는 0로 세팅 가능성 있는 비트.

-> 1로 세팅된 비트를 오른쪽부터 카운팅

 

Trailings == countr_zero

 

LeadingZeros = One.countl_zero  -> One의 왼쪽에서 "0" 카운팅 -> One은 1로 세팅 가능성 있는 비트.

-> 0로 세팅된 비트를 왼쪽부터 카운팅

LeadingOnes = Zero.countl_zero -> Zero의 왼쪽부터 "0" 카운팅 -> Zero는 0로 세팅 가능성 있는 비트.

-> 1로 세팅된 비트를 왼쪽부터 카운팅

 

Leading == countl_zero

 

 

	countMinTrailingZeros	countMinTrailingOnes	countMinLeadingZeros	countMinLeadingOnes
00001011	0	2	4	0
00010100	2	0	3	0

 

구현내용

/// Returns the minimum number of trailing zero bits.

unsigned countMinTrailingZeros() const { return Zero.countr_one(); }

/// Returns the minimum number of trailing one bits.

unsigned countMinTrailingOnes() const { return One.countr_one(); }

/// Returns the minimum number of leading zero bits.

unsigned countMinLeadingZeros() const { return Zero.countl_one(); }

/// Returns the minimum number of leading one bits.

unsigned countMinLeadingOnes() const { return One.countl_one(); }

 

<아직 작성중>