LLVM 내가</p> <pre><code>for (int i = 0; i < 15; i++){ a[b[i]]++; } </code></pre> <p>는 동안 -O0와 .ll 파일로 다이빙을 사용하여 컴파일, 나는 단계에 의해 단계를 작성 지침을 볼 수있는 아주 간단한 루프의 IR를 참조하려고

Question

O2 최적화를 수행하는 방법 define i32 @main() 기능. 그러나 -O2를 사용하여 컴파일하고 .ll 파일을 조사하는 동안 define i32 @main() 함수에는 ret i32 0 만 있습니다. 그리고 -O02로 컴파일 된 .ll 파일에 제시된 일부 call 명령어는 -O2로 컴파일 된 .ll 파일에서 tail call으로 변경됩니다.

누구나 llvm이 -O2 컴파일을 수행하는 방법에 대한 자세한 설명을 제공 할 수 있습니까? 감사.

T

Answer 1

우리는 당신의 예를 보면 godbolt.org에서 컴파일러 탐색기를 사용할 수 있습니다. 우리는 다음과 같은 테스트 벤치 코드를 사용합니다 :

int test() { 
    int a[15] = {0}; 
    int b[15] = {0}; 

    for (int i = 0; i < 15; i++){ 
    a[b[i]]++; 
    } 

    return 0; 
} 

Godbolt는 86 어셈블리가 아닌 LLVM 바이트 코드를 보여줍니다,하지만 난 무슨 일이 일어나고 있는지 보여 그것을 조금 정리했습니다. 여기가 -O0 -m32에 있습니다 :

test():        
     # set up stack 
.LBB0_1:         
     cmp  dword ptr [ebp - 128], 15   # i < 15? 
     jge  .LBB0_4        # no? then jump out of loop 
     mov  eax, dword ptr [ebp - 128]   # load i 
     mov  eax, dword ptr [ebp + 4*eax - 124] # load b[i] 
     mov  ecx, dword ptr [ebp + 4*eax - 64] # load a[b[i]] 
     add  ecx, 1        # increment it 
     mov  dword ptr [ebp + 4*eax - 64], ecx # store it back 
     mov  eax, dword ptr [ebp - 128] 
     add  eax, 1        # increment i 
     mov  dword ptr [ebp - 128], eax 
     jmp  .LBB0_1        # repeat 
.LBB0_4: 
     # tear down stack 
     ret 

우리가 기대하는 것처럼이 보인다 : 루프가 명확하게 볼 수 있습니다 그리고 우리가 나열된 모든 단계를 수행합니다. 우리가 에서 컴파일 할 경우, 우리는 루프가 여전히 볼 수 있지만 훨씬 간단 :

이

test():        # @test() 
     # set up stack 
.LBB0_1:        
     mov  ecx, dword ptr [esp + 4*eax] # load b[i] 
     inc  dword ptr [esp + 4*ecx + 60] # increment a[b[i]] 
     inc  eax        # increment i 
     cmp  eax, 15       # compare == 15 
     jne  .LBB0_1       # no? then loop 
     # tear down stack 
     ret 

연타 지금 inc 명령 (유용) 사용주의는 루프 카운터 i의 eax 레지스터를 사용할 수있다 (스트레이트) , 조건 검사를 루프의 맨 아래로 옮겼습니다 (아마도 더 좋을 것입니다). 그래도 우리는 원래 코드를 인식 할 수 있습니다. 이제 -O2 -m32 -march=i386으로 시도해 보겠습니다.

test():        
     xor  eax, eax # does nothing 
     ret 

그래? 예.

clang은 a 배열을 함수 밖에서 절대 사용할 수 없다는 것을 감지했습니다. 즉, 증분 작업을 수행하면 프로그램의 다른 부분에는 아무런 영향을 미치지 않으며, 사라지면 아무도 그 프로그램을 놓치지 않습니다.

증가를 제거하면 빈 몸체와 부작용이없는 루프가 나타납니다. 제거 할 수도 있습니다. 차례로 루프를 제거하면 (모든 의도와 목적으로) 빈 함수가 남습니다.

이 빈 함수는 LLVM 바이트 코드 (ret i32 0)에서 보았을 가능성이 큽니다.

---

이것은 매우 과학적인 설명과 다를 수 있습니다 소요 clang 단계는 아니지만 나는 예는 비트를 지 웁니다 바랍니다. 원하는 경우 as-if rule에서 읽을 수 있습니다. https://godbolt.org/을 조금만 돌아 보는 것이 좋습니다. 예를 들어, a 및 b을이 기능 외부로 이동하면 어떻게되는지보십시오.

Answer 2

다른 스위치는 LLVM IR에서 실행되는 여러 변형 패스 집합을 지정합니다. opt 도구의 스위치 --debug-pass=Structure을 사용하여 패스 목록을 볼 수 있습니다.

예를 들어, 내 컴퓨터에서 opt -O0 test.ll --debug-pass=Structure >> /dev/null/ 인쇄는 stderr로 :

Pass Arguments: -tti -verify Target Transform Information FunctionPass Manager Module Verifier Pass Arguments: -targetlibinfo -tti -assumption-cache-tracker -profile-summary-info -forceattrs -basiccg -always-inline -barrier -verify -print-module Target Library Information Target Transform Information Assumption Cache Tracker Profile summary info ModulePass Manager Force set function attributes CallGraph Construction Call Graph SCC Pass Manager Inliner for always_inline functions A No-Op Barrier Pass FunctionPass Manager Module Verifier Print module to stderr

opt -O3 test.ll --debug-pass=Structure >> /dev/null/ 반면 :

Pass Arguments: -tti -tbaa -scoped-noalias -assumption-cache-tracker -targetlibinfo -verify -simplifycfg -domtree -sroa -early-cse -basicaa -aa -memdep -memoryssa -gvn-hoist -lower-expect Target Transform Information Type-Based Alias Analysis Scoped NoAlias Alias Analysis Assumption Cache Tracker Target Library Information FunctionPass Manager Module Verifier Simplify the CFG Dominator Tree Construction SROA Early CSE Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Memory Dependence Analysis Memory SSA Early GVN Hoisting of Expressions Lower 'expect' Intrinsics Pass Arguments: -targetlibinfo -tti -tbaa -scoped-noalias -assumption-cache-tracker -profile-summary-info -forceattrs -inferattrs -ipsccp -globalopt -domtree -mem2reg -deadargelim -domtree -basicaa -aa -instcombine -simplifycfg -pgo-icall-prom -basiccg -globals-aa -prune-eh -inline -functionattrs -domtree -sroa -early-cse -speculative-execution -lazy-value-info -jump-threading -correlated-propagation -simplifycfg -domtree -basicaa -aa -instcombine -libcalls-shrinkwrap -tailcallelim -simplifycfg -reassociate -domtree -loops -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -loop-rotate -licm -loop-unswitch -simplifycfg -domtree -basicaa -aa -instcombine -loops -loop-simplify -lcssa-verification -lcssa -scalar-evolution -indvars -loop-idiom -loop-deletion -loop-unroll -mldst-motion -aa -memdep -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -gvn -basicaa -aa -memdep -memcpyopt -sccp -domtree -demanded-bits -bdce -basicaa -aa -instcombine -lazy-value-info -jump-threading -correlated-propagation -domtree -basicaa -aa -memdep -dse -loops -loop-simplify -lcssa-verification -lcssa -aa -scalar-evolution -licm -postdomtree -adce -simplifycfg -domtree -basicaa -aa -instcombine -barrier -elim-avail-extern -basiccg -rpo-functionattrs -globals-aa -float2int -domtree -loops -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -loop-rotate -loop-accesses -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -loop-distribute -loop-simplify -lcssa-verification -lcssa -branch-prob -block-freq -scalar-evolution -basicaa -aa -loop-accesses -demanded-bits -lazy-branch-prob -lazy-block-freq -opt-remark-emitter -loop-vectorize -loop-simplify -scalar-evolution -aa -loop-accesses -loop-load-elim -basicaa -aa -instcombine -scalar-evolution -demanded-bits -slp-vectorizer -simplifycfg -domtree -basicaa -aa -instcombine -loops -loop-simplify -lcssa-verification -lcssa -scalar-evolution -loop-unroll -instcombine -loop-simplify -lcssa-verification -lcssa -scalar-evolution -licm -alignment-from-assumptions -strip-dead-prototypes -globaldce -constmerge -domtree -loops -branch-prob -block-freq -loop-simplify -lcssa-verification -lcssa -basicaa -aa -scalar-evolution -branch-prob -block-freq -loop-sink -instsimplify -verify -write-bitcode Target Library Information Target Transform Information Type-Based Alias Analysis Scoped NoAlias Alias Analysis Assumption Cache Tracker Profile summary info ModulePass Manager Force set function attributes Infer set function attributes Interprocedural Sparse Conditional Constant Propagation Global Variable Optimizer Unnamed pass: implement Pass::getPassName() FunctionPass Manager Dominator Tree Construction Promote Memory to Register Dead Argument Elimination FunctionPass Manager Dominator Tree Construction Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Combine redundant instructions Simplify the CFG PGOIndirectCallPromotion CallGraph Construction Globals Alias Analysis Call Graph SCC Pass Manager Remove unused exception handling info Function Integration/Inlining Deduce function attributes FunctionPass Manager Dominator Tree Construction SROA Early CSE Speculatively execute instructions if target has divergent branches Lazy Value Information Analysis Jump Threading Value Propagation Simplify the CFG Dominator Tree Construction Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Combine redundant instructions Conditionally eliminate dead library calls Tail Call Elimination Simplify the CFG Reassociate expressions Dominator Tree Construction Natural Loop Information Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Scalar Evolution Analysis Loop Pass Manager Rotate Loops Loop Invariant Code Motion Unswitch loops Simplify the CFG Dominator Tree Construction Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Combine redundant instructions Natural Loop Information Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Scalar Evolution Analysis Loop Pass Manager Induction Variable Simplification Recognize loop idioms Delete dead loops Unroll loops MergedLoadStoreMotion Function Alias Analysis Results Memory Dependence Analysis Lazy Branch Probability Analysis Lazy Block Frequency Analysis Optimization Remark Emitter Global Value Numbering Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Memory Dependence Analysis MemCpy Optimization Sparse Conditional Constant Propagation Dominator Tree Construction Demanded bits analysis Bit-Tracking Dead Code Elimination Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Combine redundant instructions Lazy Value Information Analysis Jump Threading Value Propagation Dominator Tree Construction Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Memory Dependence Analysis Dead Store Elimination Natural Loop Information Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Function Alias Analysis Results Scalar Evolution Analysis Loop Pass Manager Loop Invariant Code Motion Post-Dominator Tree Construction Aggressive Dead Code Elimination Simplify the CFG Dominator Tree Construction Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Combine redundant instructions A No-Op Barrier Pass Eliminate Available Externally Globals CallGraph Construction Deduce function attributes in RPO Globals Alias Analysis FunctionPass Manager Float to int Dominator Tree Construction Natural Loop Information Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Scalar Evolution Analysis Loop Pass Manager Rotate Loops Loop Access Analysis Lazy Branch Probability Analysis Lazy Block Frequency Analysis Optimization Remark Emitter Loop Distribution Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Branch Probability Analysis Block Frequency Analysis Scalar Evolution Analysis Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Loop Access Analysis Demanded bits analysis Lazy Branch Probability Analysis Lazy Block Frequency Analysis Optimization Remark Emitter Loop Vectorization Canonicalize natural loops Scalar Evolution Analysis Function Alias Analysis Results Loop Access Analysis Loop Load Elimination Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Combine redundant instructions Scalar Evolution Analysis Demanded bits analysis SLP Vectorizer Simplify the CFG Dominator Tree Construction Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Combine redundant instructions Natural Loop Information Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Scalar Evolution Analysis Loop Pass Manager Unroll loops Combine redundant instructions Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Scalar Evolution Analysis Loop Pass Manager Loop Invariant Code Motion Alignment from assumptions Strip Unused Function Prototypes Dead Global Elimination Merge Duplicate Global Constants FunctionPass Manager Dominator Tree Construction Natural Loop Information Branch Probability Analysis Block Frequency Analysis Canonicalize natural loops LCSSA Verifier Loop-Closed SSA Form Pass Basic Alias Analysis (stateless AA impl) Function Alias Analysis Results Scalar Evolution Analysis Branch Probability Analysis Block Frequency Analysis Loop Pass Manager Loop Sink Remove redundant instructions Module Verifier Bitcode Writer Pass Arguments: -domtree FunctionPass Manager Dominator Tree Construction합니다.

패스 이름은 자기 설명 적이지만 작동 방식을 자세히 알고 싶으면 온라인으로 소스 코드를 볼 수 있습니다.