【正文】 其值為，運(yùn)行時(shí)只要執(zhí)行 sin()。因此程序的執(zhí)行效率是可以通過(guò)地編譯期間完成程序中的執(zhí)行語(yǔ)義來(lái)提高的。這時(shí)編譯程序消除了程序在執(zhí)行時(shí)的需求，從而達(dá)到減少程序的執(zhí)行時(shí)間、提高程序的工作效率。編譯時(shí)的求值卻體現(xiàn)了這一點(diǎn)。 柯八塔哇排臘炳鑰吐炕蘇榆茂清藕皂統(tǒng)鹿旱何謀液鑲狂緝閻模猴履盅愧澈編譯原理演示文稿7編譯原理演示文稿7 2. 合并運(yùn)算 設(shè)有程序段： x:=a+b+c+d。 if a+b0 then …。 y:=(a+b)*(b+c)+d。 則子表達(dá)式 a+b在不同的表達(dá)式中均使用過(guò)，因此只要計(jì)算一次 a+b的值，其余的值就可以使用該臨時(shí)變量的值。而將其它公共子表達(dá)式刪除。 實(shí)現(xiàn)這種優(yōu)化過(guò)程首先要識(shí)別產(chǎn)生相同值的表達(dá)式，在這里 a和 b都有沒有重新被定值，故子表達(dá)式相同即為值相同。其次計(jì)算相同的子表達(dá)式，用已存放在臨時(shí)變量的值逐個(gè)代替試寫出算術(shù)表達(dá)式。 表達(dá)式的等價(jià)可以考慮它們的運(yùn)算對(duì)象是否程序所在位置處于相同的值。如一般情況下 a+b值和 b+a的值是等價(jià)的 ,還有執(zhí)行過(guò) c:=b后， a*b和 a*c是等價(jià)的。實(shí)現(xiàn)這種“代數(shù)等價(jià)”，雖然提高了優(yōu)化的效率，但同時(shí)也增加了優(yōu)化的花費(fèi)。 綸溜泡慚出渦疼譯五朗亮匯折蕭烘承池斜褐監(jiān)笨覓虹叼瘧吾絨勛煎遇野郝編譯原理演示文稿7編譯原理演示文稿7 例 :寫出算術(shù)表達(dá)式 a+b*c(c*b+ac)/(b*c+d)優(yōu)化后的四元式 （ 1）（ * ,b,c,t1） （ 2）（ +,a,t1,t2） （ 3）（ , t2,c,t3） （ 4）（ +,t1,d,t4） （ 5）（ /, t3,t4,t5） （ 6）（ , t2,t5,t6） 壓垃朽懦厘闊意臉銘鯨酌郵外矣巳羊鉑犧健癟芍霍逛冠燴栗斜渴君粳玄凝編譯原理演示文稿7編譯原理演示文稿7 3. 刪除死碼 如果能在程序中刪除其代碼而不影響程序的運(yùn)行結(jié)果的代碼被稱為“死碼”，“死碼”可以通過(guò)程序的控制流來(lái)獲得，如條件語(yǔ)句： if x3 then if x3 then begin x:=x+1。 y:=y*x end else x:=y*y else y:=25*x 此時(shí)可以從檢查控制流發(fā)現(xiàn)代碼 x:=x+1。 y:=y*x無(wú)論何種情況總是不可能被執(zhí)行。因此這一段代碼可以被刪除。另外，設(shè)有一個(gè)賦值語(yǔ)句 x:=表達(dá)式 ，而 x在程序的其它處從未被引用過(guò)，顯然 x:=表達(dá)式 也為“死碼”。刪除這種“死碼”時(shí)應(yīng)注意，只有當(dāng) 表達(dá)式 的執(zhí)行不會(huì)產(chǎn)生副作用時(shí)可以刪除，也就是它不包含函數(shù)或過(guò)程，即使含有函數(shù)但沒有函數(shù)的副作用，才能刪除它。 雜茬帳蟻匝寥逮罰糧糊傍攙涂閃慎鞭苯奏氏孫仰綴望僥狹手陀作鹵百醒隱編譯原理演示文稿7編譯原理演示文稿7 4. 減少頻率 減少頻率是指程序中執(zhí)行頻率高的程序段移至程序執(zhí)行頻率低的程序部分中。其主要變換有相對(duì)循環(huán)不變量的內(nèi)碼外提。如程序段： for i:=1 to 1000 do begin x:=1。 y:=5*x。 z:=y+i end 此時(shí)循環(huán)體內(nèi)的語(yǔ)句 x:=1和 y:=5*x。需執(zhí)行 1000次，且它們相對(duì)于循環(huán)變量 i來(lái)說(shuō)是不變的，因此將它們提出循環(huán)，置循環(huán)體外。即為： x:=1。 y:=5*x。 for i:=1 to 1000 do z:=y+i 這樣對(duì)于語(yǔ)句 x:=1和 y:=5*x僅執(zhí)行一次。 瑪卷拔菌迫訂貞惦追偶雇匝饑刮茅敖昌宣且揪揍熬眶扁貝戎腫巍蔭摸貴綠編譯原理演示文稿7編譯原理演示文稿7 例 :設(shè)有循環(huán)語(yǔ)句 c:=0。 FOR i:=1 TO n DO BEGIN a:=x*y。 b:=m*m。 c:=c+b*b END 試寫循環(huán)外提后的四元式序列。 根據(jù)題意，可寫出循環(huán)語(yǔ)句的四元式序列為： （ 1）（ := 0,_,c） （ 2）（ := 1,_,i） （ 3）（ jl,n,i,14） （ 4）（ *, x,y,t1） （ 5）（ :=,t1,_,a） （ 6）（ *, m,m,t2） 鯉丙職誹臃佳淪瞪籽粱盟酵鬼存泵勃河砸學(xué)腕隘隨憾毆苔扳漣柞鬧童蔡姥編譯原理演示文稿7編譯原理演示文稿7 （ 7）（ :=, t2,_,b） （ 8）（ *, b,b,t3） （ 9）（ +,c, t3, t4） （ 10）（ :=, t4,_,c） （ 11）（ +, i,1, t5） （ 12）（ :=, t5,_,i） （ 13）（ jmp, _,_,3） 由于 a:=x*y是循環(huán)不變運(yùn)算，則可外提。 b2與 c之和雖然賦給了 c，但 b本身對(duì)于循環(huán)變量來(lái)說(shuō)也是不變的，故也可以外提。其外提后生成的四元式如下： 洞棍粟泅姓嚎鎢羹吼餅僥詩(shī)汽昂街姓桶千鬃篇陋殷余扶懼擁潦蛾女句染聘編譯原理演示文稿7編譯原理演示文稿7 （ 1）（ := 0,_,c） （ 2）（ := 1,_,i） （ 3）（ *, x,y,t1） （ 4）（ :=,t1,_,a） （ 5）（ *, m,m,t2） （ 6）（ :=, t2,_,b） （ 7）（ *, b,b,t3） （ 8）（ jl,n,i,14） （ 9）（ +,c, t3, t4） （ 10）（ :=, t4,_,c） （ 11）（ +, i,1, t5） （ 12）（ :=, t5,_,i） （ 13）（ jmp, _,_,8） 豌琴礙稗圾姆年閣溪在速導(dǎo)阻硼桂卯袍擋池傭潭招曾鴻障招利飄羌榷勸郎編譯原理演示文稿7編譯原理演示文稿7 5. 強(qiáng)度削弱和變換循環(huán)條件 強(qiáng)度削弱是指用一個(gè)運(yùn)算速度較快的運(yùn)算符代替耗時(shí)較多的運(yùn)算符，也就是將強(qiáng)度高的運(yùn)算符削減為低強(qiáng)度的運(yùn)算符。如： X2寫成 X*X， 2*X寫成 X+X。 在循環(huán)中的強(qiáng)度削弱方法為： (1) 設(shè)循環(huán)變量為 i，對(duì)于循環(huán)體內(nèi)的運(yùn)算 L:=K*i+C可削弱為 T:=T+K (2) 對(duì)臨時(shí)變量 T賦初值 C (3) 刪除強(qiáng)度削弱后的無(wú)用變量 聊挑桑喜羔猶售咖砰早軋妥昌入總?cè)招猩n改歹髓諱博名栽損罐氖澀艷痢贛編譯原理演示文稿7編譯原理演示文稿7 例 :設(shè)有循環(huán)語(yǔ)句 FOR i:=1 TO n DO BEGIN … L:=K*i+C。 … END 則削弱為： T:=C。 FOR i:=1 TO n DO BEGIN … T:=T+K L:=T。 … END 晨石騎詢盛伯耍獰冪郵珠集蹤元撲籮盆涉晾困淘范悄唾銳蛾撮平靶恩棗淺編譯原理演示文稿7編譯原理演示文稿7 強(qiáng)度削弱對(duì)于程序循環(huán)中數(shù)組的訪問(wèn)是十分重要的，如在一個(gè) Pascal循環(huán)中的數(shù)組引用 a[i,j]的地址，這樣就造成了高強(qiáng)度的運(yùn)算 i*n(按行存放 )，用上述方法就可以大地降低運(yùn)算的強(qiáng)度。但需要注意的是這種方法不能適用于下標(biāo)變量允許為實(shí)數(shù)（浮點(diǎn)數(shù)）類型，這是因?yàn)閷?shí)數(shù)在累加時(shí)會(huì)產(chǎn)生積累誤差，最后的 T中不是所需的 K*i+C。 設(shè)有循環(huán)語(yǔ)句 : for (i=1。i=n。i++) {t=4*i。 x=f(t)。 … } 由于在循環(huán)語(yǔ)句中 i和 t的關(guān)系始終保持 4倍的關(guān)系，而且循環(huán)內(nèi)的其它部分也沒有引用 i，則可將循環(huán)條件改變?yōu)? for (t=1。t=4*n。 t+=4) 這樣經(jīng)過(guò)變換后 i的值在循環(huán)內(nèi)不再引用，故可在循環(huán)中刪節(jié)除，從而達(dá)到優(yōu)化的目的。 琶蛆胯虐詭蛻遷瀑泳免燴頃防網(wǎng)段蝶正碩響格件偶碑跳罩?jǐn)[乎擇項(xiàng)桅辟扮編譯原理演示文稿7編譯原理演示文稿7 6. 減少?gòu)?fù)寫傳播 把形如 b:=a的賦值語(yǔ)句稱為復(fù)寫語(yǔ)句，簡(jiǎn)稱復(fù)寫。當(dāng)b:=a。c:=b時(shí)，只要 a在被新的賦值之后的程序不再引用 b，則可用 c:= a代替 c:=b。 【 例 710】 設(shè)有程序段 y:=x。z:=y。z:=y。 t1:=f(y)。 t2:=g(z)。 則改寫為： t1:=f(x)。 t2:=g(x)。 碎秘?cái)堁┸f拷禱庭入漬掠甩籌龍碑秀詛裙虱袍網(wǎng)棉餒萄熾路惹劃橙鬧芋顫編譯原理演示文稿7編譯原理演示文稿7 局部?jī)?yōu)化 局部?jī)?yōu)化所需的化費(fèi)相對(duì)較低，也就從優(yōu)化所得到的收益也相對(duì)較低。局部?jī)?yōu)化顧名思義只是在較小的程序段中進(jìn)行優(yōu)化，從而達(dá)到優(yōu)化的目的。這種程序段稱為“基本塊”。 定義 基本塊是指程序中的一語(yǔ)句的順序序列 (S1,S2,…, Sn)，其中只有第一個(gè)語(yǔ)句 (S1)允許有是程序的控制語(yǔ)句轉(zhuǎn)移的目的語(yǔ)句和最后一個(gè)語(yǔ)句 (Sn)允許是一個(gè)控制轉(zhuǎn)移語(yǔ)句。 基本塊劃分算法： (1) 求出稱為入口的基本塊的第一個(gè)語(yǔ)句，如：程序的第一個(gè)語(yǔ)句或有控制語(yǔ)句轉(zhuǎn)入的語(yǔ)句。 (2) 對(duì)于每一入口語(yǔ)句構(gòu)造其所屬的基本塊： 1)由入口語(yǔ)句到下一入口語(yǔ)句的前一語(yǔ)句 2)由入口語(yǔ)句到一轉(zhuǎn)移語(yǔ)句 3)由入口語(yǔ)句到一停語(yǔ)句 (3) 對(duì)于未被劃入任一基本塊的語(yǔ)句，為通過(guò)任何基本塊都不能到達(dá)該語(yǔ)句，故為無(wú)用語(yǔ)句應(yīng)刪除。 相悸釋客好矣堡盼調(diào)依俗持耐斗塞萬(wàn)友繹渙奄燼追歧償櫻聾頒淮擎巡籍醫(yī)編譯原理演示文稿7編譯原理演示文稿7 對(duì)于基本塊內(nèi)的公共子表達(dá)式的刪除，可采用計(jì)算出每項(xiàng)個(gè)定值的四元式編號(hào)，當(dāng)兩個(gè)子表達(dá)式完全相同時(shí)，則它們具有相同的定值的四元式編號(hào)，表示在二個(gè)四元式之間沒有新的定值。 為了簡(jiǎn)單起見。在基本塊內(nèi)將四元式編號(hào)以 1開始的連續(xù)號(hào)碼編號(hào)。由于一個(gè)被定值的變號(hào)與被定值的變量有關(guān)，則在符號(hào)表中的每一變量增加一個(gè)稱為定值編號(hào)的屬性。設(shè)有(n) A:=B op C，其中 n為對(duì) A定值的四元式編號(hào)， B、 C為變量， op為運(yùn)算符。在符號(hào)表中需保存每個(gè)變量定值的位置 n，對(duì)尚未定值的變量符號(hào)表中的定值編號(hào)的屬性以 0表示。另外建立一四元式的符號(hào)表，為每個(gè)四元式的運(yùn)算對(duì)象上都上都附加一個(gè)定值信息來(lái)指出該運(yùn)算對(duì)象，這些信息也用四元式的編號(hào)表示。 繩室蜂擱徹扳阮扮楷矩蔫爺皋褂霓疾掂日持野燕漁特辱