北京航空航天大學(xué)編譯原理代碼優(yōu)化(編輯修改稿)
2024-07-23 08:21 本頁面
【文章內(nèi)容簡介】 而減少計算次數(shù)——也稱為頻度削弱 北京航空航天大學(xué)計算機(jī)學(xué)院 b) 循環(huán)展開 循環(huán)展開是一種優(yōu)化技術(shù) 。它將構(gòu)成循環(huán)體的代碼（不包括控制 循環(huán)的測試和轉(zhuǎn)移部分），重復(fù)產(chǎn)生許多次（這可在編譯時確 定），而不僅僅是一次，以空間換時間。 例 PL/1中的初始化循環(huán) DO END I=1 A[ I ] = TO 30 展開 A[1] A[1]= = A[2] A[2]= = …… …… A[30] A[30]= = 30 條語句 30 條語句 （指令）執(zhí)行 （指令）執(zhí)行 也是 30 條語句 也是 30 條語句 II:= :=11 L1: L1: IF IF II 30 30 THEN THEN GOTO GOTO II= =I+1 I+1 GOTO GOTO L2: L2: L1 L1 北京航空航天大學(xué)計算機(jī)學(xué)院 代碼 55 條語句 代碼 條語句 共執(zhí)行 5*30 共執(zhí)行 5*30 條語句 條語句 L2 L2 A[ A[II]]= = ? 循環(huán)一次執(zhí)行5條語句才給一個變量賦初值。展開后，一條語句就能賦一 個值，運行效率高。 ? ? 優(yōu)化在生成代碼時進(jìn)行，并不是修改源程序。 必須知道循環(huán)的終值，初值及步長。 ? 但并不是所有展開都是合適的。如上例中循環(huán)展開后節(jié)省執(zhí)行了轉(zhuǎn)移和 測試語句：2*30=60語句 (其實，還不止節(jié)省60條）。 ∴增加29條省60條 但若循環(huán)體中不是一條而是40條語句，則展開后將有40*30條=1200，但省 的仍是60條，就不算優(yōu)化了。 ∴判斷準(zhǔn)則：1. 主存資源豐富 處理機(jī)時間昂貴 2. 循環(huán)體語句越少越好 循環(huán)展開有利 （大型 機(jī)） 北京航空航天大學(xué)計算機(jī)學(xué)院 DO I = 1 TO 30 A[ I ] = 實現(xiàn)步驟： END 1. 識別循環(huán)結(jié)構(gòu)，確定循環(huán)的初值，終值和步長。 2. 判斷。以空間換時間是否合算來決定是否展開。 3. 展開。重復(fù)產(chǎn)生循環(huán)體所需的代碼個數(shù)。 比較復(fù)雜： ∵在對空間與時間進(jìn)行權(quán)衡時，還可以考慮一種折衷的辦法，即部分展開循 環(huán)。如上例展為： DO I = 1 TO A[I] = A[I+1] = A[I+2] = END。 北京航空航天大學(xué)計算機(jī)學(xué)院 30 BY 3 空間只多二條， 但省了20次測 試時間 （只循環(huán)10次） c) 歸納變量的優(yōu)化和條件判斷的替換 歸納變量(induction varable): 在每一次執(zhí)行循環(huán)迭代的 過程中，若某變量的值固定增加（或減少）一個常量 值，則稱該變量為歸納變量(induction variable)。即若 當(dāng)前執(zhí)行循環(huán)的第j次迭代。歸納變量的值應(yīng)為c*j+c’, 這里c和c’都循環(huán)不變式。 例： for i := 1 to 10 do a[i] := b[i] + c[i] 北京航空航天大學(xué)計算機(jī)學(xué)院 1) 1) 2) 2) 3) 3) 4) 4) 5) 5) 6) 6) ii:= :=11 labb: labb: if if ii 10 10 tt := 11 := 4*i 4*i tt := ]] 22 11 := b b[[tt tt := 33 := 4*i 4*i tt 4 := 3]] := cc[[tt 4 3 for for i:= i:=11 to to 10 10 do do a[i] a[i]:= :=b[i] b[i] + + c[i] c[i] goto goto labe labe 1) 1) 2) 2) 優(yōu)化： 3) 3) 4) 4) 5) 5) 6) 6) 7) 7) 8) 8) 9) 9) 10) 10) u u:= :=4 4 labb: labb: if ifu u40 40 goto goto labe labe tt bb:= :=b b[u] [u] tt cc:= :=cc[u] [u] tt := := tt bb+ +tt cc a a[[u] u]:= :=tt u u:= :=u+4 u+4 goto got
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1