版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
第11章代碼優(yōu)化學習目標:掌握:基本塊的劃分、基本塊的DAG優(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)化:在只有一個入口、一個出口的基 本塊上進行優(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:=T2[T1]T4:=4*I
(5)……(4)變換成T4
:=T12.合并已知量與復寫傳播如果運算量都是已知量,則在編譯時就算出它的值,稱為合并已知量若有A:=B,稱為把B值復寫到A。如果其后有引用A的地方,且其間A、B的值都未改變,則可把對A的引用改為對B引用,稱為復寫傳播。例:(1)I:=1 (2)T1:=4*I (3)T4:=T1 (4)T6:=T5[T4]I是已知量把T1的值復寫到T4(4)T6:=T5[T1]復寫傳播(2)T1:=4
合并已知量3.刪除無用賦值有些變量的賦值從未被引用,稱為無用賦值,應刪除。無用賦值分三種情況:變量被賦值,但在程序中從未被引用(在局部范圍內(nèi)難判定)
變量賦值后未被引用又重新賦值,則前面賦值是無用的
變量的賦值只被計算變量自己引用,其他變量都不引用它例(1)I:=1(2)T1:=4(3)T3:=T2[T1](4)T4:=T1
(5)I:=I+1(6)T1:=T1+4(7)ifT1≤80goto(3)(4)中對T4賦值,但T4未被引用;(1)和(5)對I賦值,但只有(5)中計算I時引用I如果程序其他地方不需要引用T4和I,則(4)、(1)和(5)是無用賦值,可刪除。(2)T1:=4(3)T3:=T2[T1](6)T1:=T1+4(7)ifT1≤80goto(3)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.
求基本塊的入口語句,它們是:程序的第一個語句;或者條件轉移或無條件轉移語句的轉移目標語句;或者緊跟在條件轉移語句后面的語句。2.對每一入口語句,構造其所屬的基本塊:它是由該入口語句到下一入口語句(不包括下一入口語句);或到一轉移語句(包括該轉移語句);或到一停止語句(包括該停止語句) 之間的語句序列組成的。3.凡未被納入某一基本塊的語句,是不會被執(zhí)行到的語句,可以把它們刪除。例:
readXreadYR:=XmodYifR=0goto
(8)X:=YY:=Rgoto
(3)writeYhalt(1)、(3)、(5)和(8)是入口語句,分別構成基本塊B1 {(1)、(2)}B2 {(3)、(4)}B3 {(5)、(6)、(7)}B4 {(8)、(9)}readXR:=XmodY
X:=YwriteY11.3
循環(huán)優(yōu)化簡介循環(huán)就是程序中那些可能反復執(zhí)行的代碼序列。因為循環(huán)中的代碼要反復執(zhí)行,所以循環(huán)的代碼優(yōu)化對提高目標代碼的效率將起更大的作用。11.3.1程序流圖把控制流的信息加到基本塊集合上構成的有向圖稱為表示程序的流圖,簡稱流圖。流圖的構造方法:點集:以基本塊為結點,含程序第一條語句的結點為首結點。邊集:從基本塊Bi向基本塊Bj引有向邊,僅當Bj在程序中的位置緊跟在Bi之后,
且Bi的出口語句不是無條件轉移語句或停止語句?;蛘連i的出口是轉移語句(goto(s)或if…goto(s)),并且轉移目標(s)是Bj的入口語句。例:構造以下程序的流圖(1)readX(2)readY(3)R:=XmodY
(4)ifR=0goto
(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt11.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)時其值不變的運算。(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=T1(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI≤20goto(3)中間代碼段B1B2(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI≤20goto(3)代碼外提后B1B2(4)中的運算量addr(A)是分配的數(shù)組A的首地址,是個常量,4也是常量,因而(4)是循環(huán)不變運算,同樣(7)也是循環(huán)不變運算,(4)、(7)都可提到循環(huán)前2.強度削弱強度削弱是指把程序中強度大的運算替換成強度小的運算。例如把乘法運算換成加法運算等(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)IfI≤20goto(3)中間代碼段(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4
(12)ifI≤20goto(5)強度削弱I和T1始終保持T1:=4*I的線性關系這樣把(12)的循環(huán)控制條件I≤20變換成T1≤80,程序的運行結果不變這種變換稱為變換循環(huán)控制條件經(jīng)過這一變換,循環(huán)中I的值不被引用,四元式(11)可被刪去,這是變換的目的所在。(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI≤20
goto(5)變換循環(huán)控制條件(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1≤80
goto(5)變換循環(huán)控制條件中間代碼段(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 單片機原理及應用(C51版)第7章課后題答案
- 2023-2024學年黑龍江省佳木斯市撫遠市八年級(上)期中數(shù)學試卷
- 人教版 英語七年級上 重要語法項目專項練習
- 企業(yè)倫理學(原書第5版) 課件 第1章 倫理和商業(yè)
- 《財經(jīng)法規(guī)與會計職業(yè)道德》高職財經(jīng)類專業(yè)全套教學課件
- 河北省邯鄲市聯(lián)考2024-2025學年高三上學期10月月考試題 化學 含解析
- 化 學元素:元素及元素符號課件 2024-2025學年九年級化學人教版(2024)上冊
- 化 學二氧化碳的實驗室制取課件-2024-2025學年九年級化學人教版上冊
- 2024-2025學年初三物理上冊復習題(四)含答案
- 精裝櫥柜工程合同模板
- 肖申克的救贖讀書分享會
- 新疆2024年新疆第三人民醫(yī)院(自治區(qū)職業(yè)病醫(yī)院)招聘136人筆試歷年典型考題及考點附答案解析
- 2024年吉林省通化梅河口市公安局招錄工作人員100人(高頻重點提升專題訓練)共500題附帶答案詳解
- 2023-2024學年廣東省揭陽市高一下學期期末教學質量測試數(shù)學試卷(含解析)
- 鋼結構工程施工(第五版) 課件 2項目三 普通螺栓
- 小兒感冒的診治課件
- 構建水利安全生產(chǎn)風險管控六項機制工作指導手冊2023版
- JT∕T 795-2023 事故汽車修復技術規(guī)范
- 2024年廣西職業(yè)院校技能大賽高職組《英語口語》賽項賽題(Presentation)
- 作文稿紙A4打印模板
- 大學生創(chuàng)新創(chuàng)業(yè)項目計劃書醫(yī)療
評論
0/150
提交評論