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

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

3、=B，稱為把B值復寫到A。如果其后有引用A的地方，且其間A、B的值都未改變，則可把對A的引用改為對B引用，稱為復寫傳播。,例： （1）I:=1 （2）T1:=4*I （3）T4:=T1 （4）T6:=T5T4,I是已知量,把T1的值復寫到T4,3. 刪除無用賦值 有些變量的賦值從未被引用，稱為無用賦值，應刪除。 無用賦值分三種情況： 變量被賦值，但在程序中從未被引用（在局部范圍內(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)化技術 以下優(yōu)化技術將在循環(huán)優(yōu)化中介紹： 代碼外提 強度削弱 變換循環(huán)控制條件（刪除歸納變量）,11.2 局部優(yōu)化,局部優(yōu)化是指基本塊內(nèi)的優(yōu)化 基本塊是指程序中一順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句。執(zhí)行時只能從入口語句進入，從其出口語句退出,11.2.1 基本塊的劃分,把程序（中間代碼形成）劃分成基本塊的算法： 1.求基本塊的入口

5、語句，它們是： 程序的第一個語句；或者 條件轉移或無條件轉移語句的轉移目標語句；或者 緊跟在條件轉移語句后面的語句。,2對每一入口語句，構造其所屬的基本塊: 它是由該入口語句到下一入口語句(不包括下一入口語句); 或到一轉移語句(包括該轉移語句); 或到一停止語句(包括該停止語句) 之間的語句序列組成的。 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ù)每個入口語句分別構成基本塊 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)就是程序中那些可能反復執(zhí)行的代碼序列。 因為循環(huán)中的代碼要反復執(zhí)行，所以循環(huán)的代碼優(yōu)化對提高目標代碼的效率將起更大的作用。,11.3.1 程序流圖,把控制流的信息加到基本塊集合上構成的有向圖稱為表示程序的流圖，簡稱流圖。 流圖的構造方法： 點集：以基本塊為結點，含程序第一條語句的結點為首結點。 邊集：從基本塊Bi向基本塊Bj引有向邊

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