第7章代碼優(yōu)化-文庫吧資料
2025-07-26 12:27本頁面
【正文】 A n A p 例：構(gòu)造以下基本塊的 DAG (1) T0:= (2) T1:=2*T0 (3) T2:=R+r (4) A:=T1*T2 (5) B:=A (6) T3:=2*T0 (7) T4:=R+r (8) T5:=T3*T4 (9) T6:=R－ r (10) B:=T5*T6 T6 ,T5 ,T3 T0 ,T4 n2 R n3 r n4 n1 B * n6 * n8 － n7 + n5 2 T1 T2 A ,B 2 DAG的應(yīng)用 在一個基本塊被構(gòu)造成相應(yīng)的 DAG的過程中 ，進行了如下基本的優(yōu)化工作： 1) 合并已知量 在 DAG構(gòu)造算法中 ， 如果運算量都是已知量，則不生成計算該結(jié)點值的內(nèi)部結(jié)點，而執(zhí)行該運算，將計算結(jié)果生成一個葉結(jié)點，實現(xiàn)了合并已知量優(yōu)化 2) 刪除多余運算 對具有公共子表達式的所有四元式，只生成一個計算該表達式的內(nèi)部結(jié)點，所有被賦值的變量都作為該結(jié)點的附加標識符，實現(xiàn)了刪除多余運算的優(yōu)化 3) 刪除無用賦值 如果變量被賦值后，在它被引用前又被重新賦值，則變量被從具有前一個值的結(jié)點上刪除 － + r T6 A, T5 * T1,T3 T0 R T2,T4 n5 n7 n2 n3 n4 n1 B * n6 n8 (1) T0 := (2) T1 := (3) T3 := (4) T2 :=R+r (5) T4 :=T2 (6) A :=*T2 (7) T5 :=A (8) T6 :=R－ r (9) B :=A*T6 由 DAG重新生成原基本塊的一個優(yōu)化的代碼序列： 原基本塊的四元式序列 G (1) T0:= (2) T1:=2*T0 (3) T2:=R+r (4) A:=T1*T2 (5) B:=A (6) T3:=2*T0 (7) T4:=R+r (8) T5:=T3*T4 (9) T6:=R－ r (10) B:=T5*T6 按 DAG重新寫成的四元式序列 G’ (1) T0 := (2) T1 := (3) T3 := (4) T2 :=R+r (5) T4 :=T2 (6) A :=*T2 (7) T5 :=A (8) T6 :=R－ r (9) B :=A*T6 ?G中 (2)(6)的已知量已 合并 ?G中 (5)的無用賦值已 刪除 ?G中 (3)(7)的公共子表達式 R+r 只計算一次 ，刪除了多余運算 利用 DAG進行優(yōu)化 刪除在基本塊后不被引用變量的賦值 r R － + T6 A, T5 * T1,T3 T0 T2,T4 n5 n7 n2 n3 n4 n1 B * n6 n8 假如 T0， T1， … ， T6在基本塊后都不被引用 ， 則這些符號可在DAG附加標識符中刪去，重寫四元式得到進一步的優(yōu)化： （ 1） S1:=R+r （ 2） A:=*S1 （ 3） S2:=R－ r （ 4） B:=A*S2 其中 S1和 S2是臨時變量。 例： (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1