[LLVM] KnownBits를 활용한 최적화 패치 기록 남기기

https://github.com/llvm/llvm-project/pull/91762

 

(기억을 보존하기 위한) 패치 내용 정리.

패치 동기

LLVM에서는 AND/OR/XOR 연산을 BitwiseLogic 이라고 부른다. 해당 로직들은 특정 상황에서 최적화 될 수 있다.

다음의 경우를 보자.

define i32 @src_no_trans_select_or_eq0_and_or(i32 %x, i32 %y) {
; CHECK-LABEL: @src_no_trans_select_or_eq0_and_or(
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[OR]]
;
  %or = or i32 %x, %y
  %or0 = icmp eq i32 %or, 0
  %and = and i32 %x, %y
  %cond = select i1 %or0, i32 %and, i32 %or
  ret i32 %cond
}

Select 구문에서 True 항인 %and 입장에서 보면 x | y == 0 이다. x | y 이 0이려면 x = 0, y = 0 이어야 한다. 그렇기에 and는 0 이 되는 것이고, x = 0, y = 0 이면 x&y = 0 이고, x|y = 0이다. 그러므로 select 구문은 통채로 %or 로 최종 최적화가 되게 된다. 때문에 최초 작성했던 패치는 BitwiseLogic 이 특정 경우에 x, y 의 값을 특정할 수 있게 되는 특성을 활용해 select 구문을 최적화 하는 패치였다.

 

제출된 패치의 코드 리뷰 과정에서, x | y == 0 인 경우, 단순히 BitwiseLogic 인 True 항 뿐 아니라, 보다 범용적인 상황에 적용할 수 있다는 지적이 됐다. 예를 들어, x | y == 0 이란 조건을 갖는 select 구문인 경우 True 항이 X를 포함하고 있다면 X를 0으로 대입한 최적화를 수행할 수 있다는 것이다.

 

문제 정의

위의 패치 동기에서 말한 케이스는 실제 코드를 작성해보면 최적화가 수행되는 것을 알 수 있다.

 

다음을 보자

int test_and(int x, int y)
{
  return (x|y)==0?(x&y):(x^y);
}

int test_xor(int x, int y)
{
  return (x|y)==0? (x^y):(x&y);
}

$ recently/bin/clang -O2 testoreq0.c -S -emit-llvm

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local noundef i32 @test_and(i32 noundef %x, i32 noundef %y) local_unnamed_addr #0 {
entry:
  %or = or i32 %y, %x
  %cmp = icmp eq i32 %or, 0
  %xor = xor i32 %y, %x
  %cond = select i1 %cmp, i32 0, i32 %xor
  ret i32 %cond
}

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local noundef i32 @test_xor(i32 noundef %x, i32 noundef %y) local_unnamed_addr #0 {
entry:
  %and = and i32 %y, %x
  ret i32 %and
}

 

위의 IR을 보면 의도했던 최적화가 수행되고 있음을 확인할 수 있다.

 

이런 차이가 발생하는 이유는,

1. x | y == 0 인 경우의 최적화는 기존에 최적화에서 활용된다는 것,

2. SelectInst 에서 수행되지 않는 이유는 1이 SelectInst에서는 적용되지 않는 문제가 있다는 것.

으로 정리할 수 있다.

 

문제 원인 파악

아래는 testoreq0.c 를 최적화 하지 않은 IR이다.

  %0 = load i32, ptr %x.addr, align 4, !tbaa !5
  %1 = load i32, ptr %y.addr, align 4, !tbaa !5
  %or = or i32 %0, %1
  %cmp = icmp eq i32 %or, 0
  br i1 %cmp, label %cond.true, label %cond.false

cond.true:                                        ; preds = %entry
  %2 = load i32, ptr %x.addr, align 4, !tbaa !5
  %3 = load i32, ptr %y.addr, align 4, !tbaa !5
  %and = and i32 %2, %3
  br label %cond.end

cond.false:                                       ; preds = %entry
  %4 = load i32, ptr %x.addr, align 4, !tbaa !5
  %5 = load i32, ptr %y.addr, align 4, !tbaa !5
  %xor = xor i32 %4, %5
  br label %cond.end

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

 

위와 같이 SelectInst 는 최초 생성되는 명령은 아니다 두 개의 Branch 를 단순화 할 수 있을 때 생성되게 된다.

여기서 차이가 생기게 된다.

 

LLVM의 최적화 과정에서는 변수의 활성화 된 Bits 를 추정하여 최적화를 지원하는 과정이 있다.

문제는 이 추정된 Bits 인 KnownBits 를 산출하는 computeKnownBits 라는 API가 내부적으로 DomConditionCache를 활용하게 되어 있으며 DomConditionCache는 또 Branch instruction만 지원한다.

 

이에 대한 더 자세한 설명은, 다음 글 타래를 참고하시길 바라며 생략.

https://die4taoam.tistory.com/search/knownbits

문제 해결

문제 해결 방안은 아주 간단하다, 본래 Branch Instruction을 최적화 하는 과정에서 Cond를 통해 KnownBits를 추산하는 로직을 SelectInst에서 사용할 수 있도록 하면 된다.

      KnownBits XKnown, YKnown, Temp;
      KnownBits TValBop0KB, TValBop1KB;
      XKnown = IC.computeKnownBits(X, 0, &SI);
      IC.computeKnownBitsFromCond(X, ICI, XKnown, 0, &SI, false);
      YKnown = IC.computeKnownBits(Y, 0, &SI);
      IC.computeKnownBitsFromCond(Y, ICI, YKnown, 0, &SI, false);

 

패치 내용중 위의 구문에 해당하는 로직이고 computeKnownBitsFromCond는 앞서 설명한 Branch Instruction의 Cond를 통해 KnownBits를 추산하는 API이다. 이를 Export 시켜 SelectInst의 Cond에 적용하는 코드가 되겠다.

 

X op Y == Constant  로 구성된 연산이 있을 때, X와 Y의 KnownBits를 Cond를 통해 추산하는 것인데, 이를 앞선 예를 통해 설명하자면, X | Y == 0 일 경우, X = 0, Y = 0 으로 KnownBits를 추가하게 된다.

 

 

그리고 여기에 지적사항인, KnownBits를 보다 범용적으로 활용하는 방안이 있는데, 

예시는 다음과 같다.

int src_and(int x, int y, int z)
{
  return (((x&3)&y) == 2) ? x&2 : 1;
}

$ recently/bin/clang -O2 testand.c -S -emit-llvm

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local noundef i32 @src_and(i32 noundef %x, i32 noundef %y, i32 noundef %z) local_unnamed_addr #0 {
entry:
  %and = and i32 %x, 3
  %and1 = and i32 %and, %y
  %cmp = icmp eq i32 %and1, 2
  %and2 = and i32 %x, 2
  %cond = select i1 %cmp, i32 %and2, i32 1
  ret i32 %cond
}

 

위 C 코드는 아래 IR에서 볼 수 있듯 최적화가 수행되지 않는다.

 

먼저 위 코드가 어떻게 최적화가 될 수 있는지 AI (Actually Ingan) 로 풀어보자.

%and:   000000??
%y  :   ????????

%and & %y == 2
%and:   0000001?
%y  :   ??????1?

 

위는 select의 cond가 true일 때, 계산되는 knownbits 이다.

그러면 select true 항은 어떤가 보면, %x & 2 이다.

 

다시 정리해서, 이 코드에서 조건은 (x&3)&y == 2 이며, 이게 True일 경우 %x와 %y 는 2에 해당하는 bit가 활성화 된다. 그렇다면 True항에 위치한 %x & 2는 반드시 2가 된다. 그러므로 이 코드는 %x & 2 가 2로 치환되는 방식으로 최적화가 될 수 있다.

 

다음은 설명한 과정이 수행되는 로그이다.

IC: Visiting:   %cond = select i1 %cmp, i8 %and1, i8 1
ENTER:   %and = and i8 %x, 3
i8 2
  %and1 = and i8 %x, 2
 X : 1 ??????10	i8 %x
 Y : 0 00000011	i8 3
 X : 1 ??????10	i8 %x
 Y : 0 00000011	i8 3
Get KB : 1
Get KB : 00000010
Get KB : 00000010
compute  000000?0
knownBits : 00000010
 Op0 : ??????10i8 %x
 Op1 : 00000010i8 2
ADD DEFERRED:   %and1 = and i8 %x, 2
IC: Mod =   %cond = select i1 %cmp, i8 %and1, i8 1
    New =   %cond = select i1 %cmp, i8 2, i8 1

 

 

마지막으로, 이와 같은 방식으로 정의할 수 없는 아주 특정한 경우가 있다.

아래와 같은 경우를 보자.

define i32 @src_select_xor_max_negative_int(i32 %x, i32 %y) {
  %xor = xor i32 %x, %y
  %xor0 = icmp eq i32 %xor, -1
  %and = and i32 %x, %y
  %or = or i32 %x, %y
  %cond = select i1 %xor0, i32 %and, i32 %or
  ret i32 %cond
}

 

x^y == -1 ? x&y : x|y  코드에서 생성되는 IR인데, 우리는 여기서 %x나 %y 에 대해 유효한 KnownBits를 추산해낼 수 없다. 다만, X와 Y의 특수한 비트 관계에 대해서만 확인할 수 있다. X^Y == -1 이라는 것은, "같은 비트는 하나도 존재하지 않고 모든 비트는 활성화 되어 있어야 한다"는 조건이 성립한다.

 

이 조건의 특수성을 통해 아래처럼, KnownBits를 추산하는 로직을 추가할 수 있고,

        if (CmpLHSBop->getOpcode() == Instruction::Xor) {
          XKnown.One |= *C & YKnown.Zero;
          XKnown.Zero |= *C & YKnown.One;
          YKnown.One |= *C & XKnown.Zero;
          YKnown.Zero |= *C & XKnown.One;

          XKnown.Zero |= ~*C & YKnown.Zero;
          XKnown.One |= ~*C & YKnown.One;
          YKnown.Zero |= ~*C & XKnown.Zero;
          YKnown.One |= ~*C & XKnown.One;
        }

 

아래 로직을 통해 제한적인 최적화를 수행할 수 있다.

      if (SKB & SpecialKnownBits::NO_COMMON_BITS) {
        if (SKB & (SpecialKnownBits::ALL_BITS_ENABLED)) {
          if (TValBop->getOpcode() == Instruction::Xor)
            Known = KnownBits::makeConstant(APInt(BitWidth, -1));
        }
        if (TValBop->getOpcode() == Instruction::And)
          Known = KnownBits::makeConstant(APInt(BitWidth, 0));

 

말 그대로, KnownBits는 알 수 없지만 NO_COMMON_BITS이고 ALL_BITS_ENABLE이면 AND X, Y는 0이다.

 

이 패치의 결말은 비극이었습니다.

https://die4taoam.tistory.com/186

아쉬운 패치