GCC4優(yōu)化技術(shù)匯總

1、GCC的優(yōu)化編譯過程（version4）GCC的編譯過程可分為4個(gè)子過程，包括Parsing pass、Gimplifcation pass、Tree SSA passes、RTL passes 。在這四個(gè)子過程中，GCC優(yōu)化主要在Tree SSA passes和RTL passes中進(jìn)行。1、SSA 優(yōu)化(1)刪除無用語句（Remove useless statements） 該過程對(duì)gimple代碼進(jìn)行非常簡(jiǎn)單的掃描，識(shí)別出明顯的死代碼并刪除。我們?cè)谶@里做的一些事情包括，簡(jiǎn)化具有不變條件的if語句，刪除對(duì)顯然不會(huì)拋出異常的代碼所做的異常處理，刪除不含有變量的詞法綁定（lexical bin

2、dings），以及其它各種簡(jiǎn)單的清除。這是為了能夠快速的去掉一些顯而易見的東西，而不是等到后面去花費(fèi)更多的功夫。該過程在tree-cfg.c中，并且由pass_remove_useless_stmts來描述。(2)死代碼消除（Dead code elimination） 該過程掃描函數(shù)來尋找沒有副作用，且結(jié)果沒有被使用的語句。它不進(jìn)行內(nèi)存活躍分析，所以任何存儲(chǔ)在內(nèi)存中值都被認(rèn)為是被使用的。該過程在整個(gè)優(yōu)化處理中被運(yùn)行多次。它位于tree-ssa-dce.c中，并由pass_dce來描述。(3)dominator優(yōu)化（Dominator optimizations） 該過程執(zhí)行平凡的基于domi

3、nator的復(fù)制和常量傳播，表達(dá)式簡(jiǎn)化，以及跳轉(zhuǎn)線程化。它在整個(gè)優(yōu)化處理中被運(yùn)行多次。它位于tree-ssa-dom.c中，并由pass_dominator來描述。(4)單用變量向前傳播（Forward propagation of single-use variables） 該過程嘗試移除冗余計(jì)算，通過將只使用一次的變量替換為使用它們的表達(dá)式，并查看是否得到的結(jié)果可以被簡(jiǎn)化。它位于tree-ssa-forwprop.c中，并由pass_forwprop來描述。(5)可能別名優(yōu)化（May-alias optimization） 該過程執(zhí)行一個(gè)流敏感基于SSA指向的分析。所得的may-alias

4、, must-alias和escape分析信息用來將變量從內(nèi)存中可尋址的對(duì)象提升為可以被重命名為SSA形式的無別名變量。過程位于tree-ssa-alias.c中，并由pass_may_alias來描述。(6)死存儲(chǔ)消除（Dead store elimination） 該過程消除死存儲(chǔ)，即存儲(chǔ)到內(nèi)存中，而該內(nèi)存被隨后的另一個(gè)存儲(chǔ)操作重新寫入，并且之間沒有加載操作。過程位于tree-ssa-dse.c中，并由pass_dse來描述。(7)尾遞歸消除（Tail recursion elimination） 該過程將所有的尾遞歸轉(zhuǎn)換到一個(gè)循環(huán)中。它位于tree-tailcall.c中，并由pass_

5、tail_recursion來描述。(8)部分冗余消除（Partial redundancy elimination） 該過程消除部分冗余計(jì)算，同時(shí)執(zhí)行加載移動(dòng)。過程位于tree-ssa-pre.c中，并由pass_pre來描述。如果設(shè)置了-funsafe-math-optimizations，則在部分冗余消除前，GCC嘗試通過倒數(shù)方式將除法轉(zhuǎn)換為乘法。過程位于tree-ssa-math-opts.c中，并由pass_cse_reciprocal來描述。(9)完全冗余消除（Full redundancy elimination） 這是一個(gè)較簡(jiǎn)單的PRE形式，只消除在所有路徑上產(chǎn)生的冗余。它位于

6、tree-ssa-pre.c中，并由pass_fre來描述。(10)循環(huán)優(yōu)化（Loop optimization） 該過程的主驅(qū)動(dòng)程序位于tree-ssa-loop.c中，并且由pass_loop來描述。該過程執(zhí)行的優(yōu)化為：循環(huán)不變量移動(dòng)。該過程只移動(dòng)在rtl級(jí)難以處理的不變量（函數(shù)調(diào)用，擴(kuò)展成非平凡insn序列的操作）。使用-funswitch-loops時(shí)，它還將不變的條件操作數(shù)移到循環(huán)外面，使得我們能夠在循環(huán)外提過程中只需要進(jìn)行平凡不變量分析。該過程還包括存儲(chǔ)移動(dòng)。該過程在tree-ssa-loop-im.c中實(shí)現(xiàn)。規(guī)約變量優(yōu)化。該過程執(zhí)行標(biāo)準(zhǔn)的規(guī)約變量優(yōu)化，包括強(qiáng)度縮減，規(guī)約變量合并，

7、以及規(guī)約變量消除。該過程在tree-ssa-loop-ivopts.c中實(shí)現(xiàn)。循環(huán)外提。該過程將不變的條件跳轉(zhuǎn)移到循環(huán)外面。為了達(dá)到這一點(diǎn)，對(duì)于每種可能的條件跳轉(zhuǎn)結(jié)果都會(huì)創(chuàng)建一個(gè)循環(huán)副本。該過程在tree-ssa-loop-unswitch.c中實(shí)現(xiàn)。該過程應(yīng)該最終替代在loop-unswitch.c中的rtl級(jí)的循環(huán)外提，但是目前rtl級(jí)的過程還不是完全多余的，是因?yàn)檫€缺少tree級(jí)的別名分析。這些優(yōu)化還用到了tree-ssa-loop-manip.c，cfgloop.c，cfgloopanal.c和cfgloopmanip.c中的各種函數(shù)。(11)用于向量化的Tree級(jí)if轉(zhuǎn)換 （Tree

8、 level if-conversion for vectorizer） 該過程應(yīng)用if轉(zhuǎn)換來簡(jiǎn)化循環(huán)，以助于向量化。我們識(shí)別可以if轉(zhuǎn)換的循環(huán)，并將基本塊合并到一個(gè)大塊中。想法是將循環(huán)表現(xiàn)為這樣的形式，使得向量化能夠?qū)φZ句和可用的向量操作進(jìn)行一一映射。該過程位于tree-if-conv.c中，并由pass_if_conversion來描述。(12)條件常量傳播（Conditional constant propagation） 該過程松弛一個(gè)點(diǎn)陣值用于識(shí)別那些即使在條件分支中也肯定是常數(shù)的。該過程位于tree-ssa-ccp.c中，并由pass_ccp來描述。(13)條件復(fù)制傳播（Condi

9、tional copy propagation） 這類似于常量傳播，它消除代碼中的冗余復(fù)制。該過程位于tree-ssa-copy.c中，并由pass_copy_prop來描述。(14) 控制依賴死代碼消除（Control dependence dead code elimination） 該過程是死代碼消除的較強(qiáng)形式，能夠消除不必要的控制流程語句。它位于tree-ssa-dce.c中，并由pass_cd_dce來描述。(15) 尾調(diào)用消除（Tail call elimination） 該過程識(shí)別可以被重寫為跳轉(zhuǎn)的函數(shù)調(diào)用。這里沒有進(jìn)行實(shí)際的代碼轉(zhuǎn)換，不過卻解決了數(shù)據(jù)流和控制流的問題。代碼轉(zhuǎn)換需

10、要目標(biāo)機(jī)支持，因此被推遲到RTL級(jí)。該過程位于tree-tailcall.c中，并且由pass_tail_calls來描述。RTL轉(zhuǎn)換由calls.c中的fixup_tail_calls來處理。(16) 返回值優(yōu)化（Return value optimization） 如果函數(shù)總是返回同一局部變量，并且那個(gè)局部變量是一個(gè)聚合類型，則變量將由函數(shù)返回值來替換。這相當(dāng)于作用于GIMPLE的C+命名返回值優(yōu)化。該過程位于tree-nrv.c中，并且由pass_nrv來描述。(17) 返回槽優(yōu)化（Return slot optimization） 如果函數(shù)返回一個(gè)內(nèi)存對(duì)象，并且像var=foo()這樣

11、被調(diào)用，該過程嘗試改變調(diào)用，使得var的地址傳送給調(diào)用者，以避免一次額外的內(nèi)存復(fù)制。該過程位于tree_nrv.c中，并由pass_return_slot來描述。(18) 循環(huán)不變量移動(dòng)（Loop invariant motion） 該過程將昂貴的循環(huán)不變量計(jì)算移出循環(huán)。該過程位于tree-ssa-loop.c中，并由pass_lim來描述。(19) 循環(huán)嵌套優(yōu)化（Loop nest optimizations） 這是一類工作于循環(huán)嵌套的循環(huán)轉(zhuǎn)換。它包括循環(huán)變換（loop interchange），scaling，skewing和逆轉(zhuǎn)（reversal），并且它們用來配合。該過程位于tree-

12、loop-linear.c中，并由pass_linear_transform來描述。(20) 空循環(huán)移除（Removal of empty loops） 該過程移除不含代碼的循環(huán)。該過程位于tree-ssa-loop-ivcanon.c中，并由pass_empty_loop來描述。(21) 小循環(huán)展開（Unrolling of small loops） 該過程將迭代次數(shù)很少的循環(huán)完全展開。該過程位于tree-ssa-loop-ivcanon.c中，并由pass_complete_unroll來描述。(22) 預(yù)測(cè)公約（Predictive commoning） 該過程使代碼可以重用先前循環(huán)迭代

13、的計(jì)算，特別是對(duì)內(nèi)存的加載和存貯。該過程位于tree-predcom.c中，并由pass_predcom來描述。(23) 重組（Reassociation） 該過程將算術(shù)表達(dá)式重寫為可以進(jìn)行優(yōu)化的形式，例如冗余消除和向量化。過程位于tree-ssa-reassoc.c中，并由pass_reassoc來描述。2、RTL優(yōu)化(24) 單定義值的向前傳播（Forward propagation of single-def values） 該過程嘗試通過替換來自單一定義的變量，并觀察結(jié)果是否能夠被簡(jiǎn)化的方式，來去除冗余計(jì)算。它執(zhí)行了復(fù)制傳播和尋址模式選擇。該過程運(yùn)行兩次，并只在第二次的時(shí)候?qū)⒅祩鞑サ窖?/p>

14、環(huán)中。它位于fwprop.c中。(25)公共子表達(dá)式消除（Common subexpression elimination） 該過程去除基本塊中的冗余計(jì)算，并且根據(jù)代價(jià)來優(yōu)化尋址模式。該過程運(yùn)行兩次。源代碼位于cse.c中。(26)全局公共子表達(dá)式消除（Global common subexpression elimination） 該過程執(zhí)行兩種不同類型的GCSE，取決于你是否在優(yōu)化代碼大小（基于LCM的GCSE趨向于通過增加代碼大小來獲得速度，而基于Morel-Renvoise的GCSE則不是）。當(dāng)優(yōu)化代碼大小時(shí)，使用Morel-Renvoise Partial Redundancy El

15、imination（部分冗余消除）來做GCSE，并不嘗試將不變量移到循環(huán)之外這留到循環(huán)優(yōu)化過程。如果進(jìn)行MR PRE，則還會(huì)進(jìn)行代碼提升（code hoisting），（也稱為code unification），還有加載移動(dòng)（load motion）。如果你在優(yōu)化速度，則會(huì)進(jìn)行基于LCM（lazy code motion）的GCSE。LCM是基于Knoop, Ruthing和Steffen的工作?；贚CM的GCSE也會(huì)進(jìn)行循環(huán)不變量代碼移動(dòng)。當(dāng)優(yōu)化速度時(shí)，我們還執(zhí)行加載和存儲(chǔ)移動(dòng)。不管使用哪一種類型的GCSE，該過程都還執(zhí)行全局常量傳播和復(fù)制傳播。該過程的源代碼為gcse.c，LCM程序在l

16、cm.c中。(27)循環(huán)優(yōu)化（Loop optimization） 該過程執(zhí)行幾個(gè)循環(huán)相關(guān)的優(yōu)化。源文件cfgloopanal.c和cfgloopmanip.c包含了通用的循環(huán)分析和操作代碼。循環(huán)結(jié)構(gòu)體的初始化和完成（finalization）由loop-init.c處理。循環(huán)不變量移動(dòng)過程在loop-invariant.c中實(shí)現(xiàn)。基本塊級(jí)的優(yōu)化unrolling,peeling和unswitching在loop-unswitch.c和loop-unroll.c中實(shí)現(xiàn)。loop-doloop.c是關(guān)于使用特定的機(jī)器相關(guān)結(jié)構(gòu)來替代循環(huán)退出條件的處理。(28)If轉(zhuǎn)換（If conversion）

17、 該過程嘗試使用This pass attempts to replace conditional branches and surrounding assignments with arithmetic, boolean value producing comparison instructions, and conditional move instructions.。如果目標(biāo)機(jī)支持，則在reload之后的最近的一次調(diào)用中，會(huì)生成預(yù)測(cè)指令（predicated instructions）。該過程位于ifcvt.c。(29)指令合并（Instruction combination） 該過程嘗

18、試去將數(shù)據(jù)流相關(guān)的兩條或者三條指令組合并為單一指令。它通過替代，使用代數(shù)簡(jiǎn)化結(jié)果的方式來為指令合并RTL表達(dá)式，然后嘗試去將結(jié)果跟機(jī)器描述匹配。該過程位于combine.c。(30) 寄存器移動(dòng)（Register movement） 該過程尋找這樣的情況，即當(dāng)匹配約束條件時(shí)會(huì)迫使指令需要重載，并且這個(gè)重載為一個(gè)寄存器到寄存器的move操作。然后它嘗試改變指令使用的寄存器來避免move指令。該過程位于regmove.c中。(31) 優(yōu)化模式轉(zhuǎn)換（Optimize mode switching） 該過程尋找這樣的指令，即需要處理器處于特定的模式（mode），然后將模式改變的數(shù)目減到最少。這些模式是

19、什么以及應(yīng)用于什么完全是目標(biāo)機(jī)特定的。源代碼位于mode-switching.c中。(32) 模調(diào)度（Modulo scheduling） 該過程查看內(nèi)部循環(huán)并且通過復(fù)合不同的迭代來重排它們的指令。模調(diào)度在指令調(diào)度之后立即被執(zhí)行。該過程位于modulo-sched.c。(33)指令調(diào)度（Instruction scheduling） 該過程尋找這樣的指令，其輸出在后來的指令中不會(huì)用到。在RISC機(jī)器上，內(nèi)存加載和浮點(diǎn)指令經(jīng)常會(huì)有這樣的特征。它重新排序基本塊中的指令以嘗試將定義和使用分開，從而避免引起流水線阻塞。該過程執(zhí)行兩次，分別在寄存器分配之前和之后。該過程位于haifa-sched.c, sched-deps.c, sched-ebb.c, sched-rgn.c和sched-vis.c中。(34) 寄存器分配（Register allocation） 這些過程確保所有偽寄存器都被去除，或者通過給它們分配硬件寄存器，或者使用等價(jià)表達(dá)式來替換（例如常數(shù)），或者將它們放在棧中。這由幾個(gè)子過程來完成：寄存器類別選擇。掃描RTL代碼來找出哪一種寄存器類別是最適合于每個(gè)偽寄存器。源文件為 regclass.c. 局部寄存器分配。該過程為只在基本塊里使用的偽寄存器分配硬件寄存器。因?yàn)榛緣K是線性的，所以能夠使用快速高效的技術(shù)來做好這