https://developers.redhat.com/articles/2022/12/20/how-contribute-llvm#implementing_the_transform

 

LLVM에 패치 보내는 튜터리얼은, Nikita Popov 가 작성한 글을 기반으로 작성됐습니다. 현재는 이 글에 포함되어 있는 리뷰과정은 모두 완전 github로 옮겨간 점 등이 달라졌으며, github 환경에 익숙한 사람들에게는 오히려 더 쉽게 LLVM에 기여할 수 있는 기회가 될 수 있을 것 같습니다.

 

이런저런 경험을 하면서, 당시에 가장 적합한 경험과 지식을 기반으로 비슷한 입장에 있는 사람들에게 도움이 되는 글을 남기고자 하는 목적으로 기록을 남깁니다.

 

1. middle-end 최적화에 참여하는 방법?

 

가장 쉬운 방법은 github llvm issue에 등록된 이슈 중에 뒤지는 것 입니다.

https://github.com/llvm/llvm-project/issues/71792

이 이슈처럼 이런 최적화가 가능할 것 같다. 라는 식으로 이슈를 올리는 사람이 있으니 이런걸 뒤져서 할만한걸 찾으시면 되고, 아니면 good first issue 로 라벨링 된 이슈 중에 찾으셔도 됩니다.

 

https://github.com/llvm/llvm-project/issues/33874

 

2. middle-end 최적화 만들고 검증하기

middle-end 최적화는 우리가 아는 방식으로도 만들 수 있습니다.

 

예를 들어 위에서 소개한 이슈인 Simplification Comparison for (a | b) ? (a ^ b) : (a & b) etc. (Clang13 vs Clang trunk) 는 이슈 내용에도 나와있지만, 다음과 같은 최적화 되지 않는 사례에 대한 이슈를 제기합니다.

bool test3(bool a, bool b)
{
    return (a & b) ? (a | b) : (a ^ b);
}

bool test4(bool a, bool b)
{
    return (a & b) ? (a ^ b) : (a | b);
}

 

이슈에서는 이전 버전과의 차이를 말하고 있기 때문에 그 차이를 살펴보겠습니다.

 

// CLANG 13 
define dso_local zeroext i1 @test3(bool, bool)(i1 zeroext %0, i1 zeroext %1) local_unnamed_addr #0 !dbg !24 {
  call void @llvm.dbg.value(metadata i1 %0, metadata !26, metadata !DIExpression(DW_OP_LLVM_convert, 1, DW_ATE_unsigned, DW_OP_LLVM_convert, 8, DW_ATE_unsigned, DW_OP_stack_value)), !dbg !28
  call void @llvm.dbg.value(metadata i1 %1, metadata !27, metadata !DIExpression(DW_OP_LLVM_convert, 1, DW_ATE_unsigned, DW_OP_LLVM_convert, 8, DW_ATE_unsigned, DW_OP_stack_value)), !dbg !28
  %3 = or i1 %0, %1, !dbg !29
  ret i1 %3, !dbg !30
}

// CLANG 13+
define dso_local noundef zeroext i1 @test3(bool, bool)(i1 noundef zeroext %0, i1 noundef zeroext %1) local_unnamed_addr #0 !dbg !34 {
  tail call void @llvm.dbg.value(metadata i1 %0, metadata !36, metadata !DIExpression(DW_OP_LLVM_convert, 1, DW_ATE_unsigned, DW_OP_LLVM_convert, 8, DW_ATE_unsigned, DW_OP_stack_value)), !dbg !38
  tail call void @llvm.dbg.value(metadata i1 %1, metadata !37, metadata !DIExpression(DW_OP_LLVM_convert, 1, DW_ATE_unsigned, DW_OP_LLVM_convert, 8, DW_ATE_unsigned, DW_OP_stack_value)), !dbg !38
  %3 = zext i1 %0 to i32, !dbg !39
  %4 = zext i1 %1 to i32, !dbg !40
  %5 = and i32 %4, %3, !dbg !41
  %6 = icmp eq i32 %5, 0, !dbg !42
  %7 = or i32 %4, %3, !dbg !42
  %8 = xor i32 %4, %3, !dbg !42
  %9 = select i1 %6, i32 %8, i32 %7, !dbg !42
  %10 = icmp ne i32 %9, 0, !dbg !42
  ret i1 %10, !dbg !43
}

https://godbolt.org/z/cTsd43jhh

 

이슈에 걸린 링크를 통해 두 컴파일러간의 차이를 확인할 수 있습니다.
위처럼 IR보려면 컴파일 옵션에 '-O2' 로 되어 있는데 '-S -emit-llvm' 을 추가해야 합니다.

 

이 이슈에서 삼항연산자의 최적화 결과물인 select 명령문은, 조건문이 참/거짓 항에 영향을 줄 수 있습니다.

예를 들어 A&B가 true이면 A=1, B=1 이고, false이면 A=1, B=1 이 아닌 조건이 소거되죠. 

때문에 test3인 (a & b) ? (a | b) : (a ^ b); 의 진리표는, or 과 일치하고, or로 변경해도 됩니다.

 

이것을 어떻게 확인할 수 있냐? 바로 ALIVE2 입니다.

 

bool src(bool a, bool b)
{
  return (a&b)?(a|b):(a^b);
}
bool tgt(bool a, bool b)
{
  return a|b;
}

 

위처럼 최적화 하고자하는 대상과 최적화 될 결과값을 각기 src/tgt 란 이름의 C 함수로 만듭니다.

그리고 이를 컴파일하여 LLVM IR을 생성합니다.

clang-17 blog.cpp -S -emit-llvm -O2

cat blog.ll 

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local noundef zeroext i1 @_Z3srcbb(i1 noundef zeroext %0, i1 noundef zeroext %1) local_unnamed_addr #0 {
  %3 = zext i1 %0 to i32
  %4 = zext i1 %1 to i32
  %5 = and i32 %4, %3
  %6 = icmp eq i32 %5, 0
  %7 = or i32 %4, %3
  %8 = xor i32 %4, %3
  %9 = select i1 %6, i32 %8, i32 %7
  %10 = icmp ne i32 %9, 0
  ret i1 %10
}

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local noundef zeroext i1 @_Z3tgtbb(i1 noundef zeroext %0, i1 noundef zeroext %1) local_unnamed_addr #0 {
  %3 = or i1 %0, %1
  ret i1 %3
}

 

위처럼 생성된 IR을 ALIVE2에 접속해서 입력합니다.

https://alive2.llvm.org/ce/z/bKLUtw

결과는 다음과 같습니다.

 
Summary:
2 correct transformations
0 incorrect transformations
0 failed-to-prove transformations
0 Alive2 errors

 

여기까지 진행됐다면, 최적화 대상을 찾고 본인이 만든 최적화 공식에 대한 증명이 된 것이므로 검증을 받을 최소한의 준비가 끝난 것 입니다. 만약 ALIVE2 가 없었다면, 본인이 만든 최적화 공식을 입증하기 위해 꽤 노력이 필요했을 겁니다 !!!

 

 

 

3. 코드 작성 tip

 

본인이 해결할 수 있는 최적화 방식에 대한 입증이 끝난 뒤라도 어떻게 기여할지는 막막한 일 입니다.

이럴때 가장 좋은 방법은 test 를 뒤져서 가장 유사한 케이스를 찾아보는 방법입니다.

 

위에서 살펴본 최적화는 select instruction에서 이뤄지게 되므로 select 관련 test를 찾아봅니다.

특히 위와 같은 Instruction 을 특정 Instruction으로 조합하거나 최소화 시키는 방식을 peephole 최적화라 부르고 주로 InstCombine 이나 InstructionSimplify 과정에서 진행하게 되므로 이에 한정해서 검색하면 됩니다.

 

https://github.com/ParkHanbum/llvm-project/commit/222bf3ffbc8419570fc2266a2e7d1c5f58cedaa7

위처럼 select instruction의 condition에 기초한 최적화 방식을 여럿 찾을 수 있고, 교차 참조해서 코드를 작성하시면 됩니다.

 

 

 

4. PR 보내기 전 알아야 할 것.

 

코드를 작성하셨으면 PR을 보내기 전에 반드시 다음의 순서를 지키셔야 합니다.

A. test 를 먼저 작성하여 커밋.

B. 코드를 작성한 뒤 컴파일하고 생성된 바이너리(clang) 을 통해 test를 업데이트.

 

먼저 A에 대해 알아보겠습니다.

이 코드는 select instruction 과 관련된 최적화 이므로 llvm/test/Transforms/InstCombine/select.ll 에 테스트를 작성합니다.

 

테스트는 위에서 작성한 src/tgt 중에 src 로 작성된 IR을 사용하시면 됩니다.

여기서부터는 제가 작성했던 테스트를 예시로 들겠습니다.

 

; Select icmp and/or/xor
; https://alive2.llvm.org/ce/z/QXQDwF
; X&Y==C?X|Y:X^Y, X&Y==C?X^Y:X|Y
define i32 @src_and_eq_0_or_xor(i32 %x, i32 %y) {
  %and = and i32 %y, %x
  %cmp = icmp eq i32 %and, 0
  %or = or i32 %y, %x
  %xor = xor i32 %y, %x
  %cond = select i1 %cmp, i32 %or, i32 %xor
  ret i32 %cond
}

 

위처럼 자신의 테스트가 무엇을 위한 것인지를 이름을 짓습니다.

src 접두어는 alive2에서 증명했던걸 그대로 가져와서 남았고 필수가 아닙니다.

 

여기서 update_test_checks.py 를 돌리면 되는데 예제는 다음과 같습니다.

./llvm/utils/update_test_checks.py --opt-bin ../i71792/bin/opt llvm/test/Transforms/InstCombine/select.ll

 

update_test_checks.py는 llvm-project에 포함되어 있으므로 llvm-project root 에서 실행하면 위와 같은 명령어가 나옵니다.

../i71792/bin/opt 은 되도록 최신 버전의 llvm 바이너리 중 하나인 opt 의 경로를, llvm/test/Transforms/InstCombine/select.ll 은 방금 작성한 테스트 파일의 경로를 넣어주면 됩니다.

 

위의 명령을 실행하면 우리가 작성한 테스트 IR에는 주석이 붙습니다.

; Select icmp and/or/xor
; https://alive2.llvm.org/ce/z/QXQDwF
; X&Y==C?X|Y:X^Y, X&Y==C?X^Y:X|Y
define i32 @src_and_eq_0_or_xor(i32 %x, i32 %y) {
; CHECK-LABEL: @src_and_eq_0_or_xor(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[Y:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y]], [[X]]
; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y]], [[X]]
; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[OR]], i32 [[XOR]]
; CHECK-NEXT:    ret i32 [[COND]]
;
entry:
  %and = and i32 %y, %x
  %cmp = icmp eq i32 %and, 0
  %or = or i32 %y, %x
  %xor = xor i32 %y, %x
  %cond = select i1 %cmp, i32 %or, i32 %xor
  ret i32 %cond
}

 

이런 구조가 됩니다.

주석으로 붙은 IR 이 인자로 넣어준 opt가 생성한 최적화 된 IR 입니다. 만약 해당 IR이 우리가 작성한 테스트와 일치하지 않는다면, 우리가 작성한 IR에는 최적화가 가능한 코드 구문이 존재한다는 뜻 입니다. 그러므로 이를 반영해서 IR을 수정하던가 아니면 최적화가 되지 않도록 만드는 기법을 사용해야 합니다.

 

보통 InstCombine은 모든 최적화가 명령을 합치거나 치환하는 과정이므로 다른 곳에서 명령을 참조하면 최적화가 진행되지 않습니다. 이를 응용해 use()같은 함수를 하나 만들어 최적화가 되버리는 IR을 인자로 넣어주면 최적화가 되지 않습니다.

  %m = mul i32 %x, %y
  call void @use_i32(i32 %m)

이런 식 입니다.

 

자, 이제 test를 commit 합니다.

 

https://github.com/llvm/llvm-project/pull/73362/commits/edeaf1cf4fa58f88d4061634bd9514dab07d4484

그럼 위 커밋처럼 온전히 현재 LLVM버전에서 최적화가 되지 않는 IR에 대한 케이스만 담겨있게 됩니다.

이제 A는 끝났습니다.

 

B. 코드를 작성한 뒤 컴파일하고 생성된 바이너리(clang) 을 통해 test를 업데이트.

 

이제는 코드를 작성후 컴파일을 합니다. 그리고 A 때와 마찬가지로 update_test_checks.py 를 돌립니다.

그러면 이번에는 최적화가 된 IR로 주석이 교체되게 될 겁니다.

 

 

img.png

 

위처럼 git 을 통해 보면 확실히 변경 사항을 확인할 수 있습니다.

 

첫 번째 커밋으로 *아직* 최적화가 되지 않는 IR과 실제 opt 를 통해 최적화가 되지 않는 IR을 주석으로 남긴 테스트를 추가했다면,

 

두 번째 커밋에는 최적화 되지 않는 IR 이 내가 작성한 코드를 컴파일 한 opt를 통해 최적화 된 결과로 기존 최적화되지 않은 주석 IR 을 최적화 된 IR로 교체한 내용과 그 최적화를 가능케 한 코드가 담기게 됩니다.

 

아래 링크처럼요.

https://github.com/llvm/llvm-project/pull/73362/commits

 

여기까지 왔다면 거의 PR 준비가 끝난 겁니다.

 

마지막으로 ninja 혹은 make 에 check-all 을 붙여 다른 테스트들도 통과하는지 확인하고 PR을 보내면 됩니다.

해당 과정은 하단의 LLVM에 패치보니기 튜토리얼 링크를 참조해주세요.

 

 

How to contribute to LLVM

https://developers.redhat.com/articles/2022/12/20/how-contribute-llvm#implementing_the_transform

 

 

번호 제목 글쓴이 날짜 조회 수
공지 [공지] 컴파일러 및 가상머신 스터디 관련 Q&A 게시판 입니다. woos 2016.04.09 279
» LLVM 최적화 패치 제출까지의 순서 정리 marcII 2024.03.19 113
67 simplify 에 대해 ChatGPT에게 물어봤습니다. [7] marcII 2023.03.19 717
66 혹시 이 책 보신분 계신지 궁금합니다. [1] marc 2023.02.22 323
65 [컴파일러] 170721 스터디 내용 pororo 2017.07.23 387
64 [컴파일러/VM] 170707 스터디 내용 pororo 2017.07.10 154
63 [컴파일러/VM] 170623 오늘 모임은 취소되었습니다. [3] pororo 2017.06.23 174
62 2017년 06/16일 스터디 컴파일러 VM스터디 [1] June 2017.06.16 137
61 [컴파일러/가상머신] 170602 진도 [3] pororo 2017.06.03 153
60 [컴파일러/가상머신] 170526 진도 [4] pororo 2017.05.27 157
59 [컴파일러/가상머신] 2회차 진행내용 공유 [8] spike 2017.05.20 209
58 llvm IR 자이 2017.05.19 1143
57 https://www.slideshare.net/Hybrid0/llvm-28276305 woos 2017.05.19 18835
56 이번 컴파일러 스터디와 관련해서 LLVM에 대해 찾아보았습니다 [1] 자이 2017.05.19 739
55 05/12 컴파일러 스터디 진도 pororo 2017.05.13 183
54 조언 구합니다. 백창우씨 외 많은 선배님들께 [5] 슈민 2016.06.06 874
53 스터디 장소 슈민 2016.04.30 116
52 Compiler (LLVM) 교재 선정 [7] 슈민 2016.04.27 908
51 스터디 공간 정리 [3] Kyoo 2016.04.24 265
50 스터디 교재 관련 의견 취합 [23] 남현우 2016.04.24 1114
XE Login