Как LLVM делает О2

Question

оптимального качества

Я пытаюсь увидеть IR очень простой петли

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

во время компиляции, используя -O0 и погружения в .ll файл, я могу видеть инструкции, написанные шаг за шагом в define i32 @main() функция. Однако при компиляции с использованием -O2 и просмотре файла .ll в функции define i32 @main() есть только ret i32 0. И некоторая команда call, представленная в файле .ll, скомпилированном -O0, изменена на tail call в файле .ll, скомпилированном -O2.

Может ли кто-нибудь дать достаточно подробное объяснение того, как llvm выполняет компиляцию -O2? Благодарю.

T

Answer 1

Мы можем использовать компилятор Проводник на godbolt.org смотреть на вашем примере. Мы будем использовать следующий код TestBench:

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

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

    return 0; 
} 

Godbolt показывает сборку x86, а не 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 

Clang теперь использует inc инструкция (полезный), заметил, что это можно использовать eax регистр для счетчика i петли (в чистом виде) , и переместил проверку состояния на дно петли (возможно, лучше). Тем не менее, мы все еще можем распознать наш оригинальный код. Теперь давайте попробуем с -O2 -m32 -march=i386:

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

Это все? Да.

clang обнаружил, что массив a никогда не может использоваться вне функции. Это означает, что приращение никогда не повлияет на какую-либо другую часть программы, а также что никто не упустит ее, когда она исчезнет.

Снятие приращения оставляет петлю for с пустым телом и без побочных эффектов, которые также можно удалить. В свою очередь, удаление цикла оставляет пустую функцию (для всех целей и задач).

Эта пустая функция, скорее всего, вы видели в байт-коде LLVM (ret i32 0).

---

Это не очень научное описание, и шаги clang принимает могут быть разными, но я надеюсь, что пример очищает его немного. Если вы хотите, вы можете прочитать на as-if rule. Я также рекомендую поиграть по телефону : посмотрите, что происходит, когда вы перемещаете a и b вне функции, например.

Answer 2

Различные коммутаторы определяют разные наборы преобразований, которые выполняются на LLVM IR. Вы можете просмотреть список проходов с помощью переключателя --debug-pass=Structure на инструменте opt.

Например, на моей машине opt -O0 test.ll --debug-pass=Structure >> /dev/null/ печатает на стандартный вывод:

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.

Имена пропусков являются самоописательными, но вы можете просмотреть исходный код онлайн, если хотите знать, как они работают подробно.