編譯原理第七章代碼優(yōu)化.ppt

《編譯原理第七章代碼優(yōu)化.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理第七章代碼優(yōu)化.ppt（40頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第 七 章 代 碼 優(yōu) 化 7.1 優(yōu) 化 概 述 1 目 的 提 高 代 碼 質(zhì) 量 ， 產(chǎn) 生 更 高 效 (時(shí) 、 空 )的 代 碼 。 2 原 則 等 價(jià) 原 則 有 效 原 則 合 算 原 則 7.1 優(yōu) 化 概 述 3 階 段源 代 碼 前 端 中 間 代 碼 代 碼 生 成 目 標(biāo) 代 碼中 間 代 碼 優(yōu) 化 目 標(biāo) 代 碼 優(yōu) 化中 間 代 碼 優(yōu) 化 7.1 優(yōu) 化 概 述 4 優(yōu) 化 分 類 根 據(jù) 階 段 分 類 (1)與 機(jī) 器 無 關(guān) 的 優(yōu) 化 (2)與 機(jī) 器 有 關(guān) 的 優(yōu) 化 根 據(jù) 優(yōu) 化 涉 及 的 范 圍 分 類 (1)局 部 優(yōu) 化 (2)循 環(huán) 優(yōu)

2、 化 (3)全 局 優(yōu) 化局 部 優(yōu) 化 基 本 塊 內(nèi) 的 優(yōu) 化 7.1 優(yōu) 化 概 述 5 優(yōu) 化 技 術(shù) 刪 除 公 共 子 表 達(dá) 式 代 碼 外 提 強(qiáng) 度 削 弱 變 換 循 環(huán) 控 制 條 件 合 并 已 知 量 復(fù) 寫 傳 播 刪 除 無 用 賦 值刪 除 公 共 子 表 達(dá) 式合 并 已 知 量刪 除 無 用 賦 值 局 部 優(yōu) 化 7.1 優(yōu) 化 概 述 6 本 章 重 點(diǎn) 局 部 優(yōu) 化相 關(guān) 技 術(shù) 四 元 式 序 列 基 本 塊 的 劃 分基 本 塊 的優(yōu) 化 技 術(shù) 刪 除 公 共 子 表 達(dá) 式合 并 已 知 量刪 除 無 用 賦 值 刪 除 公 共 子 表 達(dá)

3、 式 在 同 一 個(gè) 基 本 塊 內(nèi) ， 計(jì) 算 結(jié) 果 相 同 的 表 達(dá) 式 只計(jì) 算 一 次 ， 以 后 重 復(fù) 出 現(xiàn) 時(shí) 直 接 引 用 結(jié) 果 。(1) T1=4*i(2) T2=addr(A)-4(3) T3=T2T1(4) T4=4*i(5) T5=addr(B)-4(6) T6=T5T4 (1) T1=4*i(2) T2=addr(A)-4(3) T3=T2T1(4) T4=T1(5) T5=addr(B)-4(6) T6=T5T4 合 并 已 知 量 常 數(shù) 或 能 確 定 其 值 的 已 知 量 ， 在 編 譯 時(shí) 直 接 計(jì)算 出 來 ， 不 等 到 運(yùn) 行 時(shí) 再 計(jì)

4、 算 。(1) i=1(2) T1=4*i(3) T2=addr(A)-4(4) T3=T2T1(5) T4=T1(6) T5=addr(B)-4(7) T6=T5T4 (1) i=1(2) T1=4(3) T2=addr(A)-4(4) T3=T2T1(5) T4=4(6) T5=addr(B)-4(7) T6=T5T4 刪 除 無 用 賦 值 賦 值 以 后 ， 在 程 序 其 他 地 方 不 再 引 用 ， 可 以 刪掉 。(1) i=1(2) T1=4(3) T2=addr(A)-4(4) T3=T2T1(5) T4=4(6) T5=addr(B)-4(7) T6=T5T4 (1) T

5、1=4(2) T2=addr(A)-4(3) T3=T2T1(4) T4=4(5) T5=addr(B)-4(6) T6=T5T4 7.2 局 部 優(yōu) 化 基 本 塊定 義 ： 基 本 塊 是 程 序 中 一 段 順 序 執(zhí) 行 的 語 句 序 列 。 只 有 一 個(gè) 入 口 語 句 、 一 個(gè) 出 口 語 句 。 入 口 是 第 一 個(gè) 語 句 ， 出 口 是 最 后 一 個(gè) 語 句 。 7.2.1 為 四 元 式 程 序 劃 分 基 本 塊 (1)找 到 入 口 語 句 ; (2)找 到 出 口 語 句 ; (3)構(gòu) 造 基 本 塊 。 程 序 的 第 一 條 語 句 能 由 條 件 轉(zhuǎn)

6、移 語 句 和 無 條 件 轉(zhuǎn) 移 語 句 到 達(dá) 的 語 句 緊 跟 在 條 件 轉(zhuǎn) 移 語 句 后 面 的 語 句 下 一 入 口 語 句 的 前 導(dǎo) 語 句 轉(zhuǎn) 移 語 句 本 身 停 語 句 (halt)本 身 刪 去 不 屬 于 任 何 基 本 塊 的 語 句 。 例 7.2 給 以 下 四 元 式 序 列 劃 分 基 本 塊 ， 并 作 出 程 序 流 圖 。(1) read C(2) A=0(3) B=1(4) L1: A=A+B(5) if B C goto L2(6) B=B+1(7) goto L1(8) L2: write A(9) halt (1) read C(2)

7、A=0(3) B=1(4) L1: A=A+B (5) if BC goto L2(6) B=B+1 (7) goto L1 (8) L2: write A(9) halt 程 序 流 圖 ： Homework:(P165) 7.5 Homework 7.5把 以 下 程 序 段 劃 分 為 基 本 塊 ， 并 作 出 其 程 序 流 圖 。 int C A=0 B=1L1: A=A+B if BC goto L2 B=B+1 goto L1L2: print A haltint 1: = +2: print B=B+1if BC goto L2goto L1halt int CA=0B=1L

8、1: A=A+B if BC goto L2B=B+1goto L1 L2: print A halt程 序 流 圖 ：B=1 7.2.2 基 本 塊 的 DAG表 示 1 DAG特 征 葉 子 結(jié) 點(diǎn) 以 一 標(biāo) 識 符 或 常 數(shù) 作 標(biāo) 記 ， 結(jié) 點(diǎn) 代 表 其 值 。 內(nèi) 部 結(jié) 點(diǎn) 以 一 運(yùn) 算 符 作 標(biāo) 記 ， 結(jié) 點(diǎn) 的 附 加 信 息 代 表 運(yùn) 算結(jié) 果 。 無 環(huán) 路 有 向 圖注 ： DAG圖 中 弧 省 去 箭 頭 ; 結(jié) 點(diǎn) 編 號 為 n i; 結(jié) 點(diǎn) 下 面 符 號 為 標(biāo) 記 ; 結(jié) 點(diǎn) 右 邊 標(biāo) 識 符 為 附 加 信 息 。ni標(biāo) 記 附 加 信 息

9、 7.2.2 基 本 塊 的 DAG表 示 2 DAG圖 類 型0型 ： 無 后 繼 結(jié) 點(diǎn) A=B1型 ： 一 個(gè) 后 繼 結(jié) 點(diǎn) A=op B2型 ： 二 個(gè) 后 繼 結(jié) 點(diǎn) A=B op C n1B A n2 An 1opB n3 An1 n2opB C 基 本 塊 四 元 式 序 列 的 DAG表 示 。四 元 式 序 列 為 ： (1)A=B+C (2)B=2*A (3)D=A n 1 n2B Cn3+ A,D n42n5* B DAG圖 為 ： 7.2.2 基 本 塊 的 DAG表 示 3 由 基 本 塊 構(gòu) 造 DAG圖 方 法(1) 設(shè) DAG為 空(2)順 序 對 基 本 塊

10、 內(nèi) 每 個(gè) 四 元 式 進(jìn) 行 如 下 操 作 ： (a)查 找 有 無 結(jié) 點(diǎn) B， 無 則 建 立 該 結(jié) 點(diǎn) ， 有 則 繼 續(xù) ; (b)若 四 元 式 類 型 為 0型 ， 跳 到 (3); 若 四 元 式 類 型 為 1型 ， 跳 到 “ 1型 處 理 ” ; 若 四 元 式 類 型 為 2型 ， 跳 到 “ 2型 處 理 ” ;(3)查 找 有 無 結(jié) 點(diǎn) A， 無 則 把 A附 加 在 當(dāng) 前 結(jié) 點(diǎn) 上 ; 否 則 ， 從 node(A)結(jié) 點(diǎn) 的 附 標(biāo) 中 刪 去 標(biāo) 記 A， 并 把 A附加 在 當(dāng) 前 結(jié) 點(diǎn) 上 。 A BA op BA B op C注 ： 作 為

11、 葉 結(jié) 點(diǎn) 標(biāo) 記 的 A不 刪 除 。 刪 除 無 用 賦 值 1型 處 理 (A= op B) if node(B) 標(biāo) 記 為 常 量 then 執(zhí) 行 op B得 值 P; 若 node(B)是 當(dāng) 前 四 元 式 建 立 的 ， 則 刪 去 ; 查 看 有 無 node(P)， 沒 有 就 建 立 ; 跳 到 (3) else 查 看 DAG圖 中 是 否 有 一 結(jié) 點(diǎn) ， 其 后 繼 結(jié) 點(diǎn) 為 node(B)， 標(biāo) 記 為 op， 沒 有 就 建 立 ; 跳 到 (3); / *合 并 已 知 量 */ *刪 除 公 共 子 表 達(dá) 式 */ 2型 處 理 (A=B op C

12、) 查 看 DAG圖 中 有 無 結(jié) 點(diǎn) node(C),沒 有 就 建 立 ; if ( node(B)標(biāo) 記 為 常 量 AND node(C)標(biāo) 記 為 常 量 ) then 執(zhí) 行 B op C 得 值 P; 若 node(B)和 node(C)是 當(dāng) 前 四 元 式 建 立 的 ， 就 刪 去 ; 查 有 無 結(jié) 點(diǎn) node(P)， 沒 有 就 建 立 ; 跳 到 (3); else 查 DAG圖 中 是 否 有 一 結(jié) 點(diǎn) ， 其 左 后 繼 為 node(B), 右 后 繼 為 node(C),標(biāo) 記 為 op,沒 有 就 建 立 ; 跳 到 (3); /*合 并 已 知 量

13、*/*刪 除 公 共 子 表 達(dá) 式 */ 例 7.3 構(gòu) 造 以 下 基 本 塊 的 DAG圖 。 (1) T0=3.14 (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 n 1 n2 n3 n43.14T0 T1,T36.28 R rn5 n7n6 n8T2,T4 T6A,T5 BDAG圖 為 ： + * * 7.2.3 利 用 DAG進(jìn) 行 基 本 塊 優(yōu) 化 1 基 本 思 想 （ 1） 首 先 構(gòu) 造 基 本 塊 的 DAG圖

14、; （ 2） 然 后 按 構(gòu) 造 還 原 成 四 元 式 。 7.2.3 利 用 DAG進(jìn) 行 基 本 塊 優(yōu) 化 2 DAG圖 生 成 過 程 中 的 優(yōu) 化 處 理 對 于 運(yùn) 算 對 象 都 是 常 量 的 四 元 式 ， 若 參 與 運(yùn) 算 的 已 知量 結(jié) 點(diǎn) 是 當(dāng) 前 四 元 式 建 立 的 ， 可 刪 除 。 對 公 共 子 表 達(dá) 式 ， 算 法 只 產(chǎn) 生 一 個(gè) 計(jì) 算 該 表 達(dá) 式 值 的 內(nèi)部 結(jié) 點(diǎn) ， 其 他 都 為 附 加 變 量 。 某 變 量 賦 值 后 ， 又 重 新 賦 值 ， 算 法 刪 除 對 變 量 前 一 個(gè)賦 值 ， 即 刪 除 該 變 量

15、的 前 一 個(gè) 附 標(biāo) 。 7.2.3 利 用 DAG進(jìn) 行 基 本 塊 優(yōu) 化 3 由 DAG圖 還 原 成 四 元 式 序 列 無 附 標(biāo) ， 不 生 成 四 元 式 ; 有 附 標(biāo) A， 標(biāo) 記 為 B， 生 成 A=B; 多 個(gè) 附 標(biāo) A1,A2,An,生 成 A1=B,A2=B,.,An=B; 有 附 標(biāo) A， 根 據(jù) 標(biāo) 記 op， 生 成 ： A=op B A=B op C 多 個(gè) 附 標(biāo) A1,A2,An， 除 第 一 個(gè) 附 標(biāo) A1計(jì) 算 外 ， 其 他 附 標(biāo) 生 成 A2=A1,An=A1。 對 例 7.3得 到 的 DAG圖 ， 生 成 四 元 式 。 生 成 的

16、四 元 式 為 ：(1)T0=3.14(2)T1=6.28(3)T3=6.28(4)T2=R+r(5)T4=T2(6)A=6.28*T2(7)T5=A(8)T6=R-r(9)B=A*T6n 1 n2 n3 n4T0 T1,T36.28 R rn5 n7n6 n8T2,T4 T6A,T5 B+ * *3.14 對 比 原 四 元 式 序 列 ：代 碼 總 數(shù) 減 少 ;T1,T3變 為 常 量T2,T4少 了 一 次 加 法B A少 了 一 次 賦 值 7.3 循 環(huán) 優(yōu) 化 知 識 點(diǎn) 總 結(jié) 7.3.1 程 序 流 圖 與 循 環(huán) 1 程 序 流 圖 定 義 ： 以 基 本 塊 作 為 結(jié)

17、點(diǎn) ， 控 制 程 序 流 向 作 為有 向 弧 ， 畫 出 的 圖 。 例 7.4 為 以 下 程 序 構(gòu) 造 一 個(gè) 程 序 流 圖 。(1) read x(2) read y(3) c=x mod y(4) if c=0 goto (8)(5) x=y(6) y=c(7) goto (3)(8) write y(9) halt (1) read x(2) read y(3) c=x mod y(4) if c=0 goto (8)(5) x=y(6) y=c(7) goto (3) (8) write y(9) haltB1 B2B3B4程 序 流 圖 ： 7.3.2 循 環(huán) 查 找 1

18、 步 驟 (1)確 定 每 個(gè) 結(jié) 點(diǎn) (基 本 塊 )的 必 經(jīng) 結(jié) 點(diǎn) 集 ; (2)通 過 必 經(jīng) 結(jié) 點(diǎn) 集 找 出 回 邊 ; (3)通 過 回 邊 確 定 循 環(huán) 。 必 經(jīng) 結(jié) 點(diǎn) 集 1 定 義 從 首 結(jié) 點(diǎn) 出 發(fā) 到 達(dá) a結(jié) 點(diǎn) 的 通 路 都 必 須 經(jīng) 過 結(jié) 點(diǎn)b， 稱 b是 a的 必 經(jīng) 結(jié) 點(diǎn) ， 記 作 ： b DOM a。 結(jié) 點(diǎn) a所 有 必 經(jīng) 結(jié) 點(diǎn) 的 集 合 ， 記 作 D(a)。 必 經(jīng) 結(jié) 點(diǎn) 集 2 求 必 經(jīng) 結(jié) 點(diǎn) 的 算 法 (1)賦 初 值 D(n1)=n1 D(ni)=N 其 中 1i N (2)求 n的 必 經(jīng) 結(jié) 點(diǎn) 集 D(

19、n)=n (D(Pi)的 交 集 ) 其 中 P i為 n所 有 的 父 結(jié) 點(diǎn) 。 例 7.5 求 下 圖 各 結(jié) 點(diǎn) 的 必 經(jīng) 結(jié) 點(diǎn) 集 D(n)。124 36 57 D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7 回 邊 1 定 義 設(shè) a b 是 流 圖 中 的 一 條 有 向 邊 ， 若 b D(a), 則 a b 是 流 圖 中 的 一 條 回 邊 。 例 利 用 必 經(jīng) 結(jié) 點(diǎn) 集 找 到 回 邊 。124 36 57 D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2

20、,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7各 結(jié) 點(diǎn) 的必 經(jīng) 結(jié) 點(diǎn) 集 ：回 邊 為 ： 667442 利 用 回 邊 確 定 循 環(huán) 算 法 ： (1)回 邊 nd組 成 的 循 環(huán) 設(shè) 為 L,則 L=n,d; (2)若 nd,且 n的 父 結(jié) 點(diǎn) n不 在 L中 ， 則 將 它 添加 至 L中 ， 即 L=n,d n (3)對 新 加 入 的 父 結(jié) 點(diǎn) n重 復(fù) 執(zhí) 行 (2)， 直 至 不再 有 新 結(jié) 點(diǎn) 加 入 L為 止 。 例 利 用 回 邊 確 定 循 環(huán) 。124 36 57 回 邊 為 ： 667442對 回 邊 66 L=6對 回

21、邊 74 L=4,5,6,7對 回 邊 42 L=2,3,4,5,6,7Homework:(P166) 7.6 本 章 小 結(jié) Homework5.1 給 出 下 面 表 達(dá) 式 的 逆 波 蘭 式 。 (1) a*(-b+c) (2) a+b*(c+d/e) (3) a+b*(-c+d) 5.2 (1)SE printf E.val (2)EE(1)+E(2) E.val=E(1).val+ E(2).val (3)EE(1)* E(2) E.val=E(1).val* E(2).val (4)E(E(1) E.val=E(1).val (5)En E.val=n.LEXVAL 給 出 表 達(dá) 式 (5*4+8)*2的 語 法 樹 ， 并 標(biāo) 注語 義 值 。 補(bǔ) 充 while (AD) then X=Y+Z 翻 譯 成 四 元 式 。（ 假 定 四 元 式 序 列 從 100開 始 ） 7.5 把 以 下 程 序 段 劃 分 為 基 本 塊 ， 作 出 程 序 流 圖 。 int C; A=0; B=1;L1:A=A+B; if B C goto L2; B=B+1; goto L1;L2:print A; halt; 7.6 B1B2B3B4 B5B6B 7B8求 各 結(jié) 點(diǎn) 的 ：必 經(jīng) 結(jié) 點(diǎn) 集 D(n)、流 圖 中 的 回 邊 、流 圖 中 的 循 環(huán) 。