[TODO] ConstantRange

1. 정의

2. 주요 기능

3. 활용 예제

 

 

 

1.

ConstantRange 는 ConstantRange.h 에 선언되어 있다.

/// This class represents a range of values.

 

 

생성자 셋

ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)

: Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),

Upper(Lower) {}

ConstantRange::ConstantRange(APInt V)

: Lower(std::move(V)), Upper(Lower + 1) {}

ConstantRange::ConstantRange(APInt L, APInt U)

: Lower(std::move(L)), Upper(std::move(U)) {

assert(Lower.getBitWidth() == Upper.getBitWidth() &&

"ConstantRange with unequal bit widths");

assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&

"Lower == Upper, but they aren't min or max value!");

}

 

ConstantRange는 상수의 범위에 관련된 행위를 담당하는 만큼,

Lower < Constant < Upper 로 구성된다.

 

-. BitWidth 로 생성하면 비트가 Full인지 여부를 나타내는 Flag에 따라 bit의 MAX : LOWER 밸류로 범위가 정해진다.

-. APInt 로 생성되면, Lower는 APInt 값, Upper는 Lower+1 이다.

-. APInt, APInt 로 생성되면 Lower, Upper가 각기 지정된다.

 

 

2.

 

 

 

 

3.

https://github.com/ParkHanbum/llvm-project/commit/5515263e4462b4bf39184f6a0e24964b4519eae4

[InstCombine] Fold and of two ranges differing by mask · ParkHanbum/llvm-project@5515263

/// Fold (icmp Pred1 V1, C1) & (icmp Pred2 V2, C2)

/// or (icmp Pred1 V1, C1) | (icmp Pred2 V2, C2)

/// into a single comparison using range-based reasoning.

/// NOTE: This is also used for logical and/or, must be poison-safe!

Value *InstCombinerImpl::foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2, bool IsAnd) {

 

 

위의 함수의 기능은 IR로 옅볼 수 있습니다.

define i1 @and_two_ranges_to_mask_and_range(i8 %c)  {
; CHECK-LABEL: @and_two_ranges_to_mask_and_range(
; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[C:%.*]], -33
; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], -91
; CHECK-NEXT:    [[AND:%.*]] = icmp ult i8 [[TMP2]], -26
; CHECK-NEXT:    ret i1 [[AND]]
;
  %c.off = add i8 %c, -97
  %cmp1 = icmp ugt i8 %c.off, 25
  %c.off2 = add i8 %c, -65
  %cmp2 = icmp ugt i8 %c.off2, 25
  %and = and i1 %cmp1, %cmp2
  ret i1 %and
}

 

두 ICmp 에 대한 비트 연산 결과를 ConstantRange로 압축하는 것.

 

ConstantRange를 활용하는 코드

ConstantRange CR1 = ConstantRange::makeExactICmpRegion(

IsAnd ? ICmpInst::getInversePredicate(Pred1) : Pred1, *C1);

if (Offset1)

CR1 = CR1.subtract(*Offset1);

ConstantRange CR2 = ConstantRange::makeExactICmpRegion(

IsAnd ? ICmpInst::getInversePredicate(Pred2) : Pred2, *C2);

if (Offset2)

CR2 = CR2.subtract(*Offset2);

 

위 식의 ConstantRange 계산

 

std::optional<ConstantRange> CR = CR1.exactUnionWith(CR2);

 

 

아래는 unionWith 함수. 주석으로 설명 달아논게 재밌어서 풀로 첨부합니다.

ConstantRange ConstantRange::unionWith(const ConstantRange &CR,
                                       PreferredRangeType Type) const {
  assert(getBitWidth() == CR.getBitWidth() &&
         "ConstantRange types don't agree!");

  if (   isFullSet() || CR.isEmptySet()) return *this;
  if (CR.isFullSet() ||    isEmptySet()) return CR;

  if (!isUpperWrapped() && CR.isUpperWrapped())
    return CR.unionWith(*this, Type);

  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
    //        L---U  and  L---U        : this
    //  L---U                   L---U  : CR
    // result in one of
    //  L---------U
    // -----U L-----
    if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
      return getPreferredRange(
          ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);

    APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
    APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;

    if (L.isZero() && U.isZero())
      return getFull();

    return ConstantRange(std::move(L), std::move(U));
  }

  if (!CR.isUpperWrapped()) {
    // ------U   L-----  and  ------U   L----- : this
    //   L--U                            L--U  : CR
    if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
      return *this;

    // ------U   L----- : this
    //    L---------U   : CR
    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
      return getFull();

    // ----U       L---- : this
    //       L---U       : CR
    // results in one of
    // ----------U L----
    // ----U L----------
    if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
      return getPreferredRange(
          ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);

    // ----U     L----- : this
    //        L----U    : CR
    if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
      return ConstantRange(CR.Lower, Upper);

    // ------U    L---- : this
    //    L-----U       : CR
    assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
           "ConstantRange::unionWith missed a case with one range wrapped");
    return ConstantRange(Lower, CR.Upper);
  }

  // ------U    L----  and  ------U    L---- : this
  // -U  L-----------  and  ------------U  L : CR
  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
    return getFull();

  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
  APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;

  return ConstantRange(std::move(L), std::move(U));
}

 

 

C1 u> 25 && C2 u> 25 의 연산은 아래처럼 변환할 수 있다.

ConstantRange CR1 = ConstantRange::makeExactICmpRegion(

IsAnd ? ICmpInst::getInversePredicate(Pred1) : Pred1, *C1);

if (Offset1)

CR1 = CR1.subtract(*Offset1);

 

 

C1 u< 26, C2 u < 26 으로 바꿨을 때,

C1과 C2의 범위는 아래와 같다.

C1:           L------U

C2:      L------U

C1: 97 < C < 123

C2: 65 < C < 91

// Check whether we have equal-size ranges that only differ by one bit.

// In that case we can apply a mask to map one range onto the other.

APInt LowerDiff = CR1.getLower() ^ CR2.getLower();

APInt UpperDiff = (CR1.getUpper() - 1) ^ (CR2.getUpper() - 1);

APInt CR1Size = CR1.getUpper() - CR1.getLower();

if (!LowerDiff.isPowerOf2() || LowerDiff != UpperDiff ||

CR1Size != CR2.getUpper() - CR2.getLower())

return nullptr;

CR = CR1.getLower().ult(CR2.getLower()) ? CR1 : CR2;

NewV = Builder.CreateAnd(NewV, ConstantInt::get(Ty, ~LowerDiff));

 

C1 C2 의 Lower 값들을 XOR하면 32,  NOT 하면 -33, 즉 -33을 C와 And연산하면

C-97 과 C-65 의 공통 값만 확보.

 

CR = CR1.getLower().ult(CR2.getLower()) ? CR1 : CR2;

 

 

if (IsAnd)

CR = CR->inverse();

 

 

C2Lower값이 더 작으므로 CR은 CR

CR Lower:Upper를 바꿔주는 inverse()

 

현재까지의 CR을 ICmp로 표현하면

} else {

Pred = CmpInst::ICMP_ULT;

RHS = getUpper() - getLower();

Offset = -getLower();

}

 

 

C - 91 u< -26 이 된다.

 

 

 

PS

 

A.

C-97, C-65. 97 = 0110 0001, 65 = 0100 0001 로 0010 0000 만 다릅니다.

즉, C & 1101 1111 -> 0010 0000 제외한 값 입니다.

 

B.

A+B -> ㄱA * ㄱB

 

C.

ㄱC1: 97 > C > 123

ㄱC2: 65 > C > 91

C2.Lower < C2.Lower

C - C2.Lower < Lower-Upper  = C - 91 < -26

 

너무 헤깔리고 있다 (@__@ ;;;; )

 

다시 정리.

X-97 > 25 & X-65 > 25

X > 122 & X > 90

 

C1:       L-------U(MAX)

C2:   L----------U(MAX)

CR:  L----------U(MAX)   << union

C2.Lower ^ C1.Lower = 32, NOT(32) = -33

 

NC: L-------=---U(MAX)

=은 존재하지 않는 구간. (And연산으로 걸러지는 구간)

(C-97>25) + (C-65>25) 연산의 NOT은,

(C-97 < ~25(-26)) * (C-65<~25(-26))

전자 CR ------ -123

후자 CR ------------- -91

-123 u< -91 : -123 : -91 하면 -91이 작다 (슬슬 열받는다.)

 

그러므로, C-91 < -26 이 최종적으로  X-97>25 & X-65>25 의  NOT.