LLVM 에 기여하기 (feat.UFTRACE)

1. 배경지식

OPT PASS 몇 개의 코드를 보면서, OPT PASS라는 것은 '최적화 할 수 있는 CASE를 만들고, 해당 CASE에서 코드를 단축시키는 등의 최적화를 하는 것.' 이라는 정리를 했는데 설명하자면 다음과 같다.

 

IR chunk는 각 opt pass 를 순회하며 최적화 케이스에 적합하면 변형되어 최적화 된 IR을 결과로 만들게 된다.

[IR chunk] -> A case 

                  -> B case

                  -> C case

                  -> [Optimized IR chunk]

 

각 case 별로 조건을 검사하고 조건을 만족할때 IR을 변형하는 식으로 진행된다는 뜻

 

 

2. 적합한 케이스 탐색

grep 으로 TODO 목록을 검색해 그 중 만만해 보이는 경우를 찾아본다.

(저의 경우 공부했던 경험과 또 만만해보이는 이유로 InstSimplify 에서 검색했습니다.)

$ grep TODO -nR llvm-project/llvm/test/Transforms/InstSimplify/

 

그래서 찾은 TODO

llvm-project/llvm/test/Transforms/InstSimplify/compare.ll:2781:; TODO: Never equal

; TODO: Never equal
define i1 @globals_offset_inequal() {
; CHECK-LABEL: @globals_offset_inequal(
; CHECK-NEXT:    ret i1 icmp ne (ptr getelementptr (i8, ptr @A, i32 1), ptr getelementptr (i8, ptr @B, i32 1))
;
  %a.off = getelementptr i8, ptr @A, i32 1
  %b.off = getelementptr i8, ptr @B, i32 1
  %res = icmp ne ptr %a.off, %b.off
  ret i1 %res
}

'같지 않게만 만들면 되는것인가??' 라면 이건 쉽게 수정할 수 있겠다는 생각이 들었다.

근데 더 중요한 이유는 바로 이 테스트의 바로 위에 있는 테스트 였는데

define i1 @globals_inequal() {
; CHECK-LABEL: @globals_inequal(
; CHECK-NEXT:    ret i1 true
;
  %res = icmp ne ptr @A, @B
  ret i1 %res
}

바로 위의 테스트와 TODO 가 표시된 테스트가 유사한 케이스였고 단지 GEP=getelementptr 유무의 차이가 있었다.
이미 pass가 있었으므로 단순히 생각해서 GEP만 계산하면 @globals_inequal() 과 거의 대동소이한 로직일 것으로 생각했던 것.

그러니 이미 존재하는 로직을 참조해서 일부 수정하는 것으로 소기 목적을 달성할 수 있겠다는 생각이 들었다.

 

그래서 각각의 테스트 케이스를 떼어내 파일로 만들고 경로를 uftrace로 추적 & 기록.

다음은 @globals_inequal() 테스트의 추적 경로를 기록하는 명령이다.

m@n2:~$ uftrace record -F simplifyICmpInst --no-libcall build/bin/opt -passes=instsimplify -S compare.ll

이 테스트 케이스에서 최적화 하는 instruction 대상은 icmp 이기 때문에 Uftrace에 simplifyICmpInst 함수를 지정했다.

opt에 준 인자는 compare.ll 같은 llvm-project의 테스트케이스 상단에 해당 pass를 테스트 할 수 있는 opt 명령이 기재되어 있고, 그를 그대로 가져온 것 입니다.

 

동일하게  @globals_offset_inequal 을 최적화 하는 경로를 기록하고 비교해봅니다.

기대했던 것처럼, 둘의 실행 경로에는 거의 차이가 없었습니다.

evaluateICmpRelation 내에서 차이가 있는 것을 확인할 수 있죠.
즉, evaluateICmpRelation 내에서 특정 조건을 검사할 때 GEP가 있는 경우는 최적화를 하지 않는다는 것을 알 수 있습니다.

 

이제 evaluateICmpRelation 내에서 차이가 있고 어떤 차이인지 코드를 살펴보면 됩니다.

 

찾은 주요 로직은 다음에 있습니다.

      } else if (const auto *CE2GEP = dyn_cast<GEPOperator>(V2)) {
        // By far the most common case to handle is when the base pointers are
        // obviously to the same global.
        const Constant *CE2Op0 = cast<Constant>(CE2GEP->getPointerOperand());
        if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
          // Don't know relative ordering, but check for inequality.
          if (CE1Op0 != CE2Op0) {
            if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices())
              return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0),
                                                cast<GlobalValue>(CE2Op0));
            return ICmpInst::BAD_ICMP_PREDICATE;
          }
        }
      }
      break;

비교하는 대상이 오직 indices 가 없는 경우에만 두 포인터 간의 동일성을 확인하는  areGlobalsPotentiallyEqual 을 호출하도록 되어 있는 고로

  %x = getelementptr i32, ptr @opte_a, i32 1
  %y = getelementptr i32, ptr @opte_b, i32 1

위와 같은 두 포인터에 대해서는 indices 가 존재하기 때문에 애초에 동일성 자체를 확인하지 않는다.

그리고 이렇게 된 이유가 있다.

 

A라는 변수에 대해 Pointer가 가르키는 입장이라고 하면

B - A 혹은 A - B 순서로 메모리에 위치할수도 있고 아니면 B - C - A, B - A - C, A - C - B 처럼 위치할 수 있다.
애초에 메모리 순서는 middle-end에서 정해지지 않기 때문이다.

 

그러므로 이전에는 정확히 동일한 변수를 가르키는 경우가 아닌 indice 가 붙어 상대주소참조를 하게 되는 경우를 배제하였던 것이다.

 

 

하지만, 정확한 메모리 위치를 알 수 없더라도 절대로 두 포인터가 동일 주소를 가르치지 않을 경우는 계산할 수 있는데
거두절미하고 코드부터 보면,

     } else if (const auto *CE2GEP = dyn_cast<GEPOperator>(V2)) {
        // By far the most common case to handle is when the base pointers are
        // obviously to the same global.
        const Constant *CE2Op0 = cast<Constant>(CE2GEP->getPointerOperand());
        if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
          // Don't know relative ordering, but check for inequality.
          if (CE1Op0 != CE2Op0) {
            DataLayout DL(cast<GlobalValue>(CE1Op0)->getParent());
            auto CE1Op0Size = DL.getTypeAllocSize(CE1Op0->getType());
            auto CE2Op0Size = DL.getTypeAllocSize(CE2Op0->getType());
            unsigned BitWidth = DL.getIndexTypeSizeInBits(CE1Op0->getType());
            APInt CE1GEPOffset(BitWidth, 0);
            BitWidth = DL.getIndexTypeSizeInBits(CE2Op0->getType());
            APInt CE2GEPOffset(BitWidth, 0);
            CE1GEP->accumulateConstantOffset(DL, CE1GEPOffset);
            CE2GEP->accumulateConstantOffset(DL, CE2GEPOffset);
            APInt Dist = CE1GEPOffset - CE2GEPOffset;
            if (Dist.isNonNegative() ? Dist.ult(CE1Op0Size) : (-Dist).ult(CE2Op0Size))
              return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0),
                                                cast<GlobalValue>(CE2Op0));

            return ICmpInst::BAD_ICMP_PREDICATE;
          }
        }
      }
      break;
    }
    default:

Pointer가 상대주소참조를 하기 위해 기준으로 삼는 변수의 크기를 계산하는데 차이가 있다.

 

예를들어 A 라는 변수가 4바이트인 경우, A + 0 부터 A + 3 까지는 A 라는 변수의 내부 메모리 공간을 참조하게 된다.
그러므로 A - B 순으로 메모리에 배치되더라도 A + 0 과 B - X 에서 X < 3 인 경우 두 포인터는 같을 수 없다.

A 주소를 0 B 주소를 3이라고 생각해보면 더 쉽게 이해할 수 있을 것이다.

 

다음은 이를 테스트하는 코드로 이해를 돕기 위해 올린다.

define i1 @negative_in_other() {
; CHECK-LABEL: @negative_in_other(
; CHECK-NEXT:    ret i1 true
;
  %a = alloca i8, i32 4
  %b = alloca i8, i32 4
  %a.off = getelementptr i8, ptr %a, i64 -3
  %b.off = getelementptr i8, ptr %b, i64 -2
  %res = icmp ne ptr %a.off, %b.off
  ret i1 %res
}

define i1 @mixed_alloca_size1() {
; CHECK-LABEL: @mixed_alloca_size1(
; CHECK-NEXT:    ret i1 true
;
  %a = alloca i8, i32 2
  %b = alloca i8, i32 4
  %a.off = getelementptr i8, ptr %a, i64 1
  %b.off = getelementptr i8, ptr %b, i64 3
  %res = icmp ne ptr %a.off, %b.off
  ret i1 %res
}

 

- 끗 -

 

 

 

패치 후 테스트 및 PR하는 방법은 다음 글 참고해주시면 되겠습니다.

 

LLVM에 패치보내기 튜토리얼

https://die4taoam.tistory.com/122

LLVM 에 패치 보내기 튜토리얼