[InstSimplify] Fold (a != 0) ? abs(a) : 0

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

[InstSimplify] Fold (a != 0) ? abs(a) : 0 by Pierre-vh · Pull Request #70305 · llvm/llvm-project

 

문제가 발생하는 경우를 추적해 봅시다.

# cat pp.c
int f(int a)
{
  if (a)
  return a > 0 ? a : -a;
  return 0;
}

 

# opt -O2 -S f.ll -print-after-all > log 2>&1

 

1회차

; *** IR Dump After InstCombinePass on f ***
; Function Attrs: nounwind uwtable
define dso_local i32 @f(i32 noundef %a) local_unnamed_addr #0 {
entry:
  %tobool.not = icmp eq i32 %a, 0
  br i1 %tobool.not, label %if.end, label %if.then

if.then:                                          ; preds = %entry
  %cond = call i32 @llvm.abs.i32(i32 %a, i1 true)
  br label %return

if.end:                                           ; preds = %entry
  br label %return

return:                                           ; preds = %if.end, %if.then
  %retval.0 = phi i32 [ %cond, %if.then ], [ 0, %if.end ]
  ret i32 %retval.0
}

; *** IR Dump After SimplifyCFGPass on f ***
; Function Attrs: nounwind uwtable
define dso_local i32 @f(i32 noundef %a) local_unnamed_addr #0 {
entry:
  %tobool.not = icmp eq i32 %a, 0
  %cond = call i32 @llvm.abs.i32(i32 %a, i1 true)
  %retval.0 = select i1 %tobool.not, i32 0, i32 %cond
  ret i32 %retval.0
}

 

2회차

; *** IR Dump After InstCombinePass on f ***
; Function Attrs: nounwind uwtable
define dso_local i32 @f(i32 noundef %a) local_unnamed_addr #0 {
entry:
  %tobool.not = icmp eq i32 %a, 0
  %cond = call i32 @llvm.abs.i32(i32 %a, i1 true)
  %retval.0 = select i1 %tobool.not, i32 0, i32 %cond
  ret i32 %retval.0
}

여기서 더 최적화가 되지 않네?

 

 

대조군을 만들어 봅시당.

define i32 @select_abs_of_abs_ne(i32 %x) {
  %abs = call i32 @llvm.abs.i32(i32 %x, i1 true)
  %neg = sub i32 0, %abs
  %cmp = icmp ne i32 %x, 0
  %sel = select i1 %cmp, i32 %abs, i32 %neg
  ret i32 %sel
}

대조군은 해당 패치가 버그픽스 격이기 때문에 기존의 테스트 코드에서 발췌했습니다.

경로는 /llvm/lib/test/Transform/InstSimplify/abs_intrinsic.ll

 

테스트 해보면 결과는 다음과 같습니다.

define i32 @select_abs_of_abs_ne(i32 %x) local_unnamed_addr #0 {
  %abs = tail call i32 @llvm.abs.i32(i32 %x, i1 false)
  ret i32 %abs
}

 

** 그렇다면 InstCombinePass 에서 발생하는 문제네요 **

 

UFTRACE를 통해 실행흐름 비교분석하기

InstCombinePass 에서의 문제 발생을 감지하였다면 다음처럼 명령어를 특정 pass에 국한해서 실행할 수 있습니다.

# opt -passes='instcombine' ss.ll

 

위 명령을 통해 실행되는 흐름을 비교군과 함께 살펴보기 위해 다음 명령을 실행합니다.

 

# uftrace record --libmcount-path=uftrace/libmcount --no-libcall -d ss_record opt -passes='instcombine' ss.ll

# uftrace record --libmcount-path=uftrace/libmcount --no-libcall -d s_record opt -passes='instcombine' s.ll

 

위처럼 uftrace를 통해 실행 흐름이 어떻게 달라지는지 확인해보고자 합니다.

 

대충 Uftrace report 명령으로 포인트 잡을 만한 곳을 찾아봅니다.

 

$ uftrace report

  Total time   Self time       Calls  Function
  ==========  ==========  ==========  ====================

    7.788 ms   15.760 us          25  llvm::InstVisitor::visit

    5.062 ms    1.690 us           1  llvm::InstCombinePass::run

    3.965 ms    3.430 us           1  combineInstructionsOverFunction

 

두 개 정도 함수가 눈에 띄네요. `  llvm::InstCombinerImpl::run ` 를 살펴봅시다.

 

 

 

LLVM의 최적화 PASS를 추적하면 종종 이런 경우가 나옵니다.

 

LLVM의 최적화, 특히 피프홀 최적화인 경우 다음과 같은 패턴을 갖는데

(1) 현재 Instruction이 특정 조건에 맞을 경우 (2) 정해진 규칙대로 코드를 변경한다.

Uftrace같은 툴로 실행흐름을 비교 분석하면, 특정 조건에 맞는 경우와 아닌 경우로 실행흐름이 분리되게 됩니다.

 

이런 경우에는 Uftrace를 통해 실행흐름을 분석하는 것으로 문제의 발생 지점 등을 파악하는게
좀더 용이해진다고 할 수 있습니다. 분기가 생기는 부분은 다음 코드입니다.

 

최적화가 된 친구는 simplifySelectInst 에서 변화시킨다음 변화한 코드를 리턴해줘서 replaceInstUsesWith 가 호출됐고 최적화되지 않은 친구는 여기서 뭔가 결격이 있어 그냥 넘어간 뒤로 계속 적합한 경우가 없어 최적화되지 못했습니다.

 

simplifySelectInst 내에서는 비교군이 PatternMatch로 최적화가 되어버린 이유로,
이후부터는 직접 코드 리딩을 해야 합니다.

굳이 억지로 유용함을 찾자면 패턴매치가 아닌 지점까지는 찾을 수 있습니다.

 

이후 패치는 링크의 내용대로... (-_- ;)

앞서 simplifySelectInst 함수 호출에서 nullptr이 반환됐기 때문에 최적화가 되지 않았던 것이므로 nullptr을 반환하는 케이스들을 모두 추적해가면 위 지점에 도달할 수 있습니다.

 

canCreatePoision 에 %cond = call i32 @llvm.abs.i32(i32 %a, i1 true) 를 인자로 넣으면

 

  case Instruction::Call:
    if (auto *II = dyn_cast<IntrinsicInst>(Op)) {
      switch (II->getIntrinsicID()) {
      // TODO: Add more intrinsics.
      case Intrinsic::ctlz:
      case Intrinsic::cttz:
      case Intrinsic::abs:
        if (cast<ConstantInt>(II->getArgOperand(1))->isNullValue())
          return false;
        break;

}

 

여기서 검사하는 것은

(gdb) p II->getArgOperand(1)->dump()
i1 true

 

아직 여기서 왜 true/false 가 들어가는지 어디서 넣어주는지는 모르겠네요.

이후 여기서 리턴되게 됩니다.

 

  case Instruction::Invoke: {
    const auto *CB = cast<CallBase>(Op);
    return !CB->hasRetAttr(Attribute::NoUndef);
  }

 

리턴의 속성에 NoUndef 이 있는지 검사하는데 llvm.abs.i32는 Undef인 경우가 있습니다?!
그래서 아마 NoUndef 속성이 없는 것 같고 때문에 여기서 true가 리턴됩니다.

 

 

마지막으로 패치 내용은, 소스코드 위에 주석으로도 달려있는데요

  // Consider:
  //   %cmp = icmp eq i32 %x, 2147483647
  //   %add = add nsw i32 %x, 1
  //   %sel = select i1 %cmp, i32 -2147483648, i32 %add
  //
  // We can't replace %sel with %add unless we strip away the flags (which
  // will be done in InstCombine).
  // TODO: This may be unsound, because it only catches some forms of
  // refinement.

 

위 주석과 코드를 함께 보면 이해가 쉽습니다.

if (auto *II = dyn_cast<IntrinsicInst>(I);
    II && II->getIntrinsicID() == Intrinsic::abs) {
  if (!ConstOps[0]->isNotMinSignedValue())
    return nullptr;
}

즉, 내장함수 abs() 를 사용하게 될 경우, 최소값 = 부호비트 포함 모든 비트가 1로 세팅된 값.
이 아닌 경우는 poison 될 경우가 없으므로 이를 예외처리 해준 겁니다. 

 

 

이상으로 분석을 마칩니다.

 

 

그리고 사족.

  case Instruction::Call:
    if (auto *II = dyn_cast<IntrinsicInst>(Op)) {
      switch (II->getIntrinsicID()) {
      // TODO: Add more intrinsics.
      case Intrinsic::ctlz:
      case Intrinsic::cttz:
      case Intrinsic::abs:
        if (cast<ConstantInt>(II->getArgOperand(1))->isNullValue())
          return false;
        break;

왜 여기서 처리를 해주지 않았을까도 궁금하네요.

 

 

https://discourse.llvm.org/t/can-i-question-for-patch-instsimplify-fold-a-0-abs-a-0/74557/2

Can I question for patch `[InstSimplify] Fold (a != 0) ? abs(a) : 0`?

 

그래서 질문해봤습니다.