代碼優(yōu)化
- 代碼優(yōu)化的含義是：對代碼進行等價變換，使得變換后的代碼具有更高的時間效率和空間效率。代碼優(yōu)化的目的是提高目標程序的質量媒怯。
- 優(yōu)化分為局部優(yōu)化鸽嫂、循環(huán)優(yōu)化和全局優(yōu)化
1纵装、局部優(yōu)化
1、基本塊的劃分方法：
基本塊指程序中一順序執(zhí)行的語句序列据某，其中只有一個入口（該序列的第一個語句）和一個出口（該序列的最后一個語句）
在各個基本塊范圍內(nèi)進行的優(yōu)化叫局部優(yōu)化橡娄。
-
基本塊的劃分：
從四元式序列確定滿足以下條件的入口語句：- 四元式序列的第一個語句
- 能由條件轉移語句或無條件轉移語句轉移到的語句
- 緊跟在條件轉移語句后面的語句
出口
- 下一個入口語句的前導語句
- 轉移語句（包括轉移語句自身）
- 停語句（包括停語句自身）
695206989.jpg
2、DAG圖的構建
DAG是一種有向圖癣籽，常用于基本塊的優(yōu)化挽唉，圖的葉節(jié)點（無后繼的節(jié)點）以標識符（變量名）或常數(shù)作為標記，圖的內(nèi)部節(jié)點（有后繼的節(jié)點）以一運算符作為標記筷狼。
-
為了DAG算法的需要瓶籽，將四元式分成四類，算法只用0埂材，1塑顺，2型四元式。
2074825103.jpg
（1）是0型四元式俏险，后繼節(jié)點數(shù)為0严拒，（2）是1型四元式，有一個后繼竖独，（3）裤唠、（4）、（5）是2型四元式莹痢，有兩個后繼 （6）是3型四元式种蘸，有三個后繼。大寫字母表示四元式中的變量名（或常數(shù)）竞膳，Node（A）表示A在DAG中相應的節(jié)點航瞭。
算法：
580404903.jpg1218775985.jpg
自己總結：352022156.jpg
練習：1706012149.jpg
3、DAG圖實現(xiàn)基本塊的優(yōu)化
- 首先根據(jù)DAG圖寫出四元式序列：注意立即數(shù)是最優(yōu)的坦辟，賦值比計算賦值優(yōu)沧奴。
- 注意T是臨時變量，A长窄、B這些都是普通變量滔吠。
2纲菌、循環(huán)優(yōu)化
1、程序流圖與循環(huán)
控制流程圖就是有唯一首節(jié)點的有向圖疮绷，用三元組G=（N翰舌，E，n0）表示（節(jié)點集冬骚，邊集椅贱，首節(jié)點）節(jié)點集就是基本塊集，有向邊表示如下：基本塊i出口語句不是轉向語句或停語句只冻，i與緊隨其后的基本塊j有有向邊庇麦。或者i出口轉向j入口語句喜德。
2山橄、循環(huán)：程序流圖里的一個節(jié)點序列強連通，任意兩個節(jié)點都有至少一條通路舍悯，它們中有且只有一個入口節(jié)點航棱。（從序列外某節(jié)點有一條有向邊引導它，或他是程序流圖的首節(jié)點萌衬。
3饮醇、找循環(huán)：
必經(jīng)節(jié)點集：從流圖首節(jié)點出發(fā)，到n的任意通路都要經(jīng)過m秕豫，m是n的必經(jīng)節(jié)點朴艰，記為mDOMn；流圖中結點n的所有必經(jīng)節(jié)點的集合稱為節(jié)點n的必經(jīng)結點集混移，極為D(n)祠墅。
DOM的性質：自反性：流圖中任意節(jié)點a，都有aDOMa沫屡。傳遞性：aDOMb，bDOMc則aDOMc撮珠。反對稱性：aDOMb,bDOMa,a=b沮脖。DOM是一個偏序關系，任何節(jié)點n的必經(jīng)節(jié)點集是一個有序集芯急。
必經(jīng)節(jié)點的求法：一定包括自己好吧勺届。。娶耍。免姿。。榕酒。必經(jīng)節(jié)點集就是前驅節(jié)點必經(jīng)節(jié)點集的交集加自己沒準胚膊。
找回邊：假設ab是流圖中的一條有向邊故俐，如果bDOMa，則a
b是流圖中的一條回邊紊婉。已知有向邊n
d是一條回邊药版，則由它組成的循環(huán)就是由結點d、結點n以及有通路到達n但該通路不經(jīng)過d的所有結點組成的喻犁。
4槽片、可規(guī)約流圖：當且僅當一個流圖除去回邊后，其余邊構成一個無環(huán)路流圖肢础。性質：1. 圖中任何直觀環(huán)路都是循環(huán)还栓。2. 找到所有回邊可以對應找出所有循環(huán)。3. 循環(huán)或嵌套或不相交（可能有公共入口節(jié)點）传轰，goto語句不可跳入循環(huán)剩盒。
練習：
5、循環(huán)優(yōu)化
- 代碼外題：對于一個循環(huán)L路召，存在循環(huán)不變運算S（不隨循環(huán)次數(shù)變化）：A=BopC或A=opB或A=B勃刨，要滿足下述條件：
1. S所在節(jié)點是L所有出口節(jié)點的必經(jīng)節(jié)點。
2. A在L中其它地方未在定值
3. L中所有A引用只有S中A定值才可達
算法如下：
- 看L中各基本塊的每個四元式股淡，他的每個運算對象為常數(shù)或者在定值點L外身隐，將此四元式標為不變運算。
- 依次查看尚未標記的四元式唯灵，如果.......贾铝，或者只有一個到達一定值點且該點上的四元式標記為不變運算，比如A=3,X=A+2埠帕，循環(huán)中A=3定值定值點可唯一到達的X=A+2也標記為不變運算垢揩。
- 不變運算提到L之外，（滿足三條件敛瓷，或者出循環(huán)后不活躍的話滿足后倆就可以）
練習：
- 強度削弱：乘法外提里面換為加法叁巨，或者加法外提里面換成加一
練習：
- 刪除歸納變量：循環(huán)中對變量I只有形如I=I
C的賦值，其中C為循環(huán)不變量呐籽，稱I為基本歸納變量锋勺。J=C1*I
-
基本歸納變量：給自己定值泉孩，給其他歸納變量賦值，控制循環(huán)（給其他歸納變量賦值在強度削弱時已經(jīng)撇清了）撑瞧，出循環(huán)不活躍可刪棵譬。刪除歸納變量就是變換循環(huán)控制條件。選一個M预伺，盡量在循環(huán)中引用订咸，出了循環(huán)活躍，有M和B關系酬诀。
刪除歸納變量.jpg
參考171頁例題脏嚷。
