第十一章代碼優(yōu)化.ppt

1、第11章 代碼優(yōu)化,學(xué)習(xí)目標(biāo)： 掌握：基本塊的劃分 理解：什么是局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化 了解：循環(huán)優(yōu)化技術(shù),11.1優(yōu)化技術(shù)簡介 11.2局部優(yōu)化 11.3循環(huán)優(yōu)化簡介,11.1 優(yōu)化技術(shù)簡介,什么是優(yōu)化： 所謂優(yōu)化是對代碼進(jìn)行等價變換，使得變換后的代碼的效率更高（節(jié)省運(yùn)行時間、存儲空間或兩者兼而有之） 優(yōu)化可在編譯的不同階段進(jìn)行，最主要的優(yōu)化有 中間代碼優(yōu)化（不依賴具體計算機(jī)） 目標(biāo)代碼優(yōu)化（依賴于具體計算機(jī)）,中間代碼優(yōu)化,中間代碼,源代碼,編譯前端,代碼生成,目標(biāo)代碼,目標(biāo)代碼優(yōu)化,編譯的優(yōu)化工作階段,優(yōu)化的分類： 根據(jù)優(yōu)化涉及的程序范圍，分為： 局部優(yōu)化：在只有一個入口、一個出口

2、的基 本塊上進(jìn)行優(yōu)化 循環(huán)優(yōu)化：對循環(huán)中的代碼進(jìn)行優(yōu)化 全局優(yōu)化：在整個程序范圍內(nèi)進(jìn)行的優(yōu)化,中間代碼優(yōu)化常用技術(shù) 1. 刪除多余運(yùn)算（刪除公共子表達(dá)式） 如果子表達(dá)式E在前面計算過，且之后E中的變量值都未改變，那么E的重復(fù)出現(xiàn)稱為公共子表達(dá)式，可避免重復(fù)計算,(1)和(4)中都有4*I的運(yùn)算， (1)到(4)之間無對I的賦值，顯然兩次計算的值是相等的， (4)的運(yùn)算是多余的,例 (1) T1 :=4*I (2) T2 :=addr(A)4 (3) T3 :=T2T1 T4 :=4*I (5) ,2. 合并已知量與復(fù)寫傳播 如果運(yùn)算量都是已知量，則在編譯時就算出它的值，稱為合并已知量 若有A:

3、=B，稱為把B值復(fù)寫到A。如果其后有引用A的地方，且其間A、B的值都未改變，則可把對A的引用改為對B引用，稱為復(fù)寫傳播。,例： （1）I:=1 （2）T1:=4*I （3）T4:=T1 （4）T6:=T5T4,I是已知量,把T1的值復(fù)寫到T4,3. 刪除無用賦值 有些變量的賦值從未被引用，稱為無用賦值，應(yīng)刪除。 無用賦值分三種情況： 變量被賦值，但在程序中從未被引用（在局部范圍內(nèi)難判定） 變量賦值后未被引用又重新賦值，則前面賦值是無用的 變量的賦值只被計算變量自己引用，其他變量都不引用它,例 （1） I:=1 （2）T1:=4 （3）T3:=T2T1 （4）T4:=T1 （5）I:=I+1 （

4、6）T1:=T1+4 （7）if T180 goto (3),(4)中對T4賦值，但T4未被引用； (1)和(5)對I賦值，但只有(5)中計算I時引用I 如果程序其他地方不需要引用T4和I，則(4)、(1)和(5)是無用賦值，可刪除。,4. 其他優(yōu)化技術(shù) 以下優(yōu)化技術(shù)將在循環(huán)優(yōu)化中介紹： 代碼外提 強(qiáng)度削弱 變換循環(huán)控制條件（刪除歸納變量）,11.2 局部優(yōu)化,局部優(yōu)化是指基本塊內(nèi)的優(yōu)化 基本塊是指程序中一順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句。執(zhí)行時只能從入口語句進(jìn)入，從其出口語句退出,11.2.1 基本塊的劃分,把程序（中間代碼形成）劃分成基本塊的算法： 1.求基本塊的入口

5、語句，它們是： 程序的第一個語句；或者 條件轉(zhuǎn)移或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句；或者 緊跟在條件轉(zhuǎn)移語句后面的語句。,2對每一入口語句，構(gòu)造其所屬的基本塊: 它是由該入口語句到下一入口語句(不包括下一入口語句); 或到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句); 或到一停止語句(包括該停止語句) 之間的語句序列組成的。 3凡未被納入某一基本塊的語句，是不會被執(zhí)行到的語句，可以把它們刪除。,例： read X read Y R:=X mod Y if R=0 goto (9) X:=Y Y:=R goto (3) write X write Y halt,首先找出基本塊的入口語句 (1)、(3)、(5)和(8

6、)是入口語句； 根據(jù)每個入口語句分別構(gòu)成基本塊 B1 (1)、(2) B2 (3)、(4) B3 (5)、(6)、(7) B4 (9)、(10) 刪除所有基本塊外的語句(8),read X,R:=X mod Y,X:=Y,write Y,11.3 循環(huán)優(yōu)化簡介,循環(huán)就是程序中那些可能反復(fù)執(zhí)行的代碼序列。 因?yàn)檠h(huán)中的代碼要反復(fù)執(zhí)行，所以循環(huán)的代碼優(yōu)化對提高目標(biāo)代碼的效率將起更大的作用。,11.3.1 程序流圖,把控制流的信息加到基本塊集合上構(gòu)成的有向圖稱為表示程序的流圖，簡稱流圖。 流圖的構(gòu)造方法： 點(diǎn)集：以基本塊為結(jié)點(diǎn)，含程序第一條語句的結(jié)點(diǎn)為首結(jié)點(diǎn)。 邊集：從基本塊Bi向基本塊Bj引有向邊

7、，僅當(dāng) Bj在程序中的位置緊跟在Bi之后, 且Bi的出口語句不是無條件轉(zhuǎn)移語句或停止語句。或者 Bi的出口是轉(zhuǎn)移語句 (goto (s)或ifgoto (s)，并且轉(zhuǎn)移目標(biāo)(s)是Bj的入口語句。,例：構(gòu)造以下程序的流圖 (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (9) (5) X:=Y (6) Y:=R goto (3) Write X (9) write Y (10) halt,11.3.2 循環(huán)優(yōu)化,1. 代碼外提 把循環(huán)不變運(yùn)算，即其結(jié)果獨(dú)立于循環(huán)執(zhí)行次數(shù)的表達(dá)式，提到循環(huán)的前面，使之只在循環(huán)外計算一次，這種優(yōu)化稱為代碼外提。 循環(huán)不變運(yùn)算：運(yùn)算量為常量或在循環(huán)外定值，每次循環(huán)時其值不變的運(yùn)算。,(4)中的運(yùn)算量addr(A)是分配的數(shù)組A的首地址，是個常量，4也是常量，因而(4)是循環(huán)不變運(yùn)算，同樣(7)也是循環(huán)不變運(yùn)算，(4)、(7) 都可提到循環(huán)前,2. 強(qiáng)度削弱 強(qiáng)度削弱是指把程序中強(qiáng)度大的運(yùn)算替換成強(qiáng)度小的運(yùn)算。例如把乘法運(yùn)算換成加法運(yùn)算等,I和T1始終保持T1:=4*I的線性關(guān)系 這樣把(12)的循環(huán)控制條件 I20變換成T180，程序的運(yùn)行結(jié)果不變 這種變換稱為變換循環(huán)控制條件 經(jīng)過這一變換，循環(huán)中I的值不被引用，四元式(11)可被刪去