學(xué)習(xí)編譯原理ch09-optimization

1、例 基本塊劃分和流圖:第9章代碼優(yōu)化與目標(biāo)代碼生成2代碼優(yōu)化與目標(biāo)代碼生成碼優(yōu)化 代碼優(yōu)化代與碼目優(yōu)標(biāo)化代碼生成在編譯程序中的位置詞法分析詞法分析詞法分析從中間表示獲取的流圖字 字符符流語流法分析語法分析語法分析改進(jìn)的流圖單詞流單詞流單詞流 語義分析和中間代碼生成指令調(diào)度指令指調(diào)令度調(diào)度寄存器分配語法分析樹機(jī)器無關(guān)的代碼優(yōu)化窺孔優(yōu)化窺孔窺優(yōu)孔化優(yōu)化中間表示中間表示中間表示目標(biāo)代碼生成優(yōu)化的中間表示針對機(jī)器的代碼優(yōu)化目標(biāo)代碼目標(biāo)代碼目標(biāo)代碼優(yōu)化的目標(biāo)代碼3代碼優(yōu)化與目標(biāo)代碼生成 (2)代碼優(yōu)化的任務(wù)通過 通過通等過價(jià)的程序變獲換得, 獲得獲執(zhí)得行速度快占、用占用占用空間少空的間間程少少序空的間程

2、少序的程序代碼生成的任務(wù)針目對標(biāo) 針語對言針目的對標(biāo)特語殊言性目的標(biāo)特語殊言性,機(jī)器相碼關(guān)(機(jī)器相關(guān)機(jī)) 器相關(guān)4不同階段的優(yōu)化法優(yōu)化 算法優(yōu)化算法優(yōu)化有效的數(shù) 有據(jù)效結(jié)的構(gòu)有數(shù)效據(jù)的結(jié)構(gòu)算領(lǐng)數(shù)和法域據(jù)算問結(jié)法題構(gòu)算(領(lǐng)法域問題領(lǐng)) 域問題譯優(yōu)化 編譯優(yōu)化編譯優(yōu)化中間代碼 中間代優(yōu)機(jī)碼化器中優(yōu)無間化關(guān)代優(yōu): 機(jī)碼化器無關(guān)機(jī)器無關(guān)常數(shù)合如并: 常數(shù)合并常、數(shù)公合共并子表達(dá)式刪除目標(biāo)代碼 目標(biāo)代優(yōu)機(jī)碼化器目優(yōu)相標(biāo)化關(guān)代優(yōu): 機(jī)碼化器相關(guān)機(jī)器相關(guān)特殊指如令: 特殊特指殊令結(jié)特、構(gòu)殊特指殊令結(jié)構(gòu)特殊結(jié)構(gòu)5中間代碼優(yōu)化部優(yōu)化 局部優(yōu)化局部優(yōu)化基本塊 基括各種轉(zhuǎn)移控制)局優(yōu)化 全局優(yōu)化全局優(yōu)化循環(huán)優(yōu)化 循

3、環(huán)優(yōu)化循、環(huán)控優(yōu)制化流分析與化簡、數(shù)據(jù)流分析8控制流圖的構(gòu)造基本 以塊基本塊結(jié)基為點(diǎn)本結(jié)控塊點(diǎn)制結(jié), 以流點(diǎn)控制有流流向控為邊制有流向邊有向邊流圖 流圖流(fl圖ow graph)G N, E, n0 基本塊N集: 基本塊集基本塊集初始結(jié)n0點(diǎn): 初始結(jié)點(diǎn)初始含結(jié)首點(diǎn)語句的基本塊E : 有向邊集合 A BA 的出口為轉(zhuǎn)移語轉(zhuǎn)句向, 轉(zhuǎn)的向的的緊 跟B 緊跟之緊后A跟之后之, 且且且后A 的出口不是 goto 或或或 return69.1 基本塊和流圖基本塊 基本塊基本塊(1) i := m - 1控制流 控制只流能控只制能流只從能第一語句進(jìn)(2) j := n入入、從最后一條語句離開(3) t

4、1 := 4 * n;(4) v := a t1 最的的長最長最的長指令序列(5) i := i + 1語句序列中間沒有停止或(6) t2 := 4 * i;分支分支分支(7) t3 := a t2 ;關(guān)鍵 關(guān)鍵關(guān): 確鍵定每個(gè)基本塊的(8) if t3 v goto (9)7基本塊的劃分三地址語句基序本列塊表基本塊表基本塊表(1) i := m - 1定義語句(2) j := n代碼序列的第一語句(3) t1 := 4 * n; (4) v := a t1 轉(zhuǎn)移語句的目標(biāo)語句(5) i := i + 1轉(zhuǎn)移語句的下一條語句(6) t2 := 4 * i;基本塊 基本塊基本塊(7) t3 :=

5、 a t2 ;一語句到下一語句(8) if t3 v goto (9)9 10三地址序列 11程序流圖129.2 局部優(yōu)化合并已知量常數(shù)表達(dá)式計(jì)算重新命名臨時(shí)變量t1 代替 t2, t4, t6, t7, t10, t11, t12, t15、t3 代替 t5, t8, t13刪除公共子表達(dá)式公共子表達(dá)式表達(dá)式E在某次出現(xiàn)之前已經(jīng)被計(jì)算過, 且E變量的值從那次計(jì)算到本次出現(xiàn)一直未被改變過(14)(16)、(17)(20)、(23)(25)、(26)(29)13局部優(yōu)化 (2)刪除死代碼未出現(xiàn)在程序流圖中的代碼賦值未的指令交換語句次序?qū)ο嗷オ?dú)立的語句進(jìn)行重新排序, 可以降低一個(gè)臨時(shí)值需要保持在寄

6、存器中的時(shí)間149.3 循環(huán)優(yōu)化循環(huán)體是優(yōu)化的重點(diǎn)反復(fù)執(zhí)行循環(huán)的定義有唯一點(diǎn)的強(qiáng)連通子圖強(qiáng)連通子圖任意兩結(jié)點(diǎn)間的通各結(jié)點(diǎn)屬于子圖15方法 1: 代碼外提將循環(huán)不變運(yùn)算移到循環(huán)外例i = 0;while( i = 76 goto (7)令種類 指令種類指令種類(4) x : = x + 4賦值 賦值賦M值OV(5) y : = t1 + x比較 比較比C較MP條件轉(zhuǎn)移 條件轉(zhuǎn)移條J件LE轉(zhuǎn)移(6) goto (3)轉(zhuǎn)移 轉(zhuǎn)移轉(zhuǎn)J移MP累加 累加累A加DD24生成目標(biāo)代碼三地址代碼:(1) MOV R0, Z(1) t1 : = z * 6(2) ADD R0, 6(2) x : = -4(3) MOV R3, R0(3) if x = 76 goto (7)(4) MOV R2, -4(4) x : = x + 4(5) CMP R2, 76(5) y : = t1 + x(6) JGE (12)(6) goto (3)(7) ADD R2, 4一般寄存