第十二章代碼生成-展示頁
2024-08-16 13:38本頁面
【正文】 干擾，將 sj的使用替換為 si的使用，并將代碼中的 sj去 掉。 一個(gè)簡(jiǎn)單的代碼生成程序 一 .計(jì)算機(jī)模型 ?假定一臺(tái) M計(jì)算機(jī)具有 n+1個(gè)通用寄存器為 R0,R1,?,R n， 它們既可作為累加器又可作為變址器 ?如果用 op表示運(yùn)算符，用 M表示內(nèi)存單元，用變量名表示 該變量所在的單元， C表示常量， *表示間址方式存取 18 ?指令形式可包含以下四種類型，見表 ： ?若 op是一目運(yùn)算符，則 op Ri,M的意義為： op(M) Ri ?以上指令中的 op包括一般計(jì)算機(jī)上常見的一些運(yùn)算符 j 19 ?某些指令的意義說明如表 ： 20 二 .待用信息鏈表法 ?若在一個(gè)基本塊中，變量 A在四元式 i中被定值，在 i后面 的四元式 j中要引用 A值，且從 i到 j之間沒有其他對(duì) A的定 值點(diǎn)，這時(shí)稱 j是四元式 i中對(duì)變量 A的 待用信息 或稱 下次 引用信息 ，同時(shí)也 稱 A是活躍的 ，若 A被多處引用則可構(gòu) 成 待用信息鏈 與 活躍信息鏈 ?為了得到在一個(gè)基本塊內(nèi)每個(gè)變量的待用信息和活躍信 息，可以從基本塊出口的四元式開始 由后向前 掃描，為 每個(gè)變量名建立相應(yīng)的待用信息鏈和活躍變量信息鏈 21 ?考慮到處理的方便，假定對(duì)基本塊中的變量 在出口處都是 活躍 的，而 對(duì)基本塊內(nèi)的臨時(shí)變量可分為兩種情況處理： ①對(duì)于沒有經(jīng)過數(shù)據(jù)流分析，且中間代碼生成的算法中不允 許在基本塊外引用的臨時(shí)變量，則這些臨時(shí)變量在基本塊 出口處都認(rèn)為是不活躍的 ②如果中間代碼生成時(shí)的算法允許某些臨時(shí)變量在基本塊外 引用時(shí)，則假定這些臨時(shí)變量被認(rèn)為是活躍的 22 ?在變量的符號(hào)表的記錄項(xiàng)中設(shè)定了待用信息和活躍信息的 欄目，其算法步驟如下： （ 1）對(duì)各基本塊的符號(hào)表中的“ 待用信息 ”欄置“ 非待用”， 對(duì)“ 活躍信息 ”欄，按在基本塊出中處是否為活躍而置成“活 躍”或“非活躍”，假定 外部變量 都是 活躍 的， 臨時(shí)變量 都是 非活躍 的 23 （ 2） 從后向前 依次處理每個(gè)四元式 i ： A:=B op C，在符號(hào) 表中依次執(zhí)行下述步驟： ① A的待用信息和活躍信息附加到 i上 ② 把 A置成 非待用 F和 非活躍 F ③ B和 C的待用信息和活躍信息附加到 i上 ④ 把 B和 C待用信息 置為 i， 活躍信息 置成 活躍 L 24 ?例如，四元式如下： (A,B,C,D是變量， T,U,V是中間變量 ) (1)T:=AB (2)U:=AC (3)V:=T+U (4)D:=V+U 25 變量 待用信息 活躍信息 初值 待用信息鏈 初值 活躍信息鏈 A B C D T U V 表 待用信息鏈和活躍信息鏈 L L F F F F F F F F F L L (4) (4) F (3) (3) F (2) (2) F (1) (1) F L F F F L L L F L L L L F (4)DFL:=VFF+UFF (3)V(4)L:=TFF+U(4)L (2)U(3)L:=AFLCFL (1)T(3)L:=A(2)LBFL (4)D:=V+U (3)V:=T+U (2)U:=AC (1)T:=AB 26 ?表 “待用信息鏈”與“活躍信息鏈”的 每列 ， 從左至右 為每當(dāng) 從后向前 掃描一個(gè)四元式時(shí) 相應(yīng)變量 的信息變化情 況， 空白處為沒變化 V U T D C B A 活躍信息鏈 初值 待用信息鏈 初值 活躍信息 待用信息 變量 L L F F F F F F F F F L L (4) (4) F (3) (3) F (2) (2) F (1) (1) F L F F F L L L F L L L L F ① ② ③ ④ ① ② ③ ④ (4)(3)(2)(1) ④ ③ ② ① DVUVTUUACTAB 27 三 .代碼生成算法 ?寄存器和內(nèi)存地址的描述： ?RVALUE[Ri]={A,C} 表示 Ri的現(xiàn)行值是變量 A， C的值 ?AVALUE[A]={A} 表示 A的值在內(nèi)存中 ?AVALUE[A]={Ri,A} 表示 A的值在 Ri中又在內(nèi)存中 ?AVALUE[A]={Ri} 表示變量 A的值在寄存器 Ri中 28 ?寄存器分配和代碼生成的具體算法： ?設(shè) RETREG是一個(gè)函數(shù)過程，它的參數(shù)是一個(gè)形如 i: A:=B op C的四元式，每次調(diào)用 GETREG(i: A:=B op C)則返回 一個(gè)寄存器 R，用以存放 A的結(jié)果值 ?對(duì)如何給出寄存器 R，要用到四元式 i上的待用信息，以使 寄存器分配合理，對(duì)每個(gè)四元式的代碼生成都要調(diào)用函數(shù) GETREG 29 ?GETREG分配寄存器的算法為： （ 1）如果 B的現(xiàn)行值在某寄存器 Ri中，且該寄存器只包含 B 的值，或者 B與 A是同一標(biāo)識(shí)符，或 B在該四元式后不會(huì)再被 引用，則可選擇 Ri為所需的寄存器 R，并轉(zhuǎn)（ 4） 30 （ 2）如果有尚未分配的寄存器，則從中選用一個(gè) Ri為所需的 寄存器 R，并轉(zhuǎn)（ 4） 31 （ 3）從已分配的寄存器中選取一個(gè) Ri作為所需寄存器 R， 其 選擇原則為： 占用該寄存器的變量值同時(shí)在主存中，或在基 本塊中引用的位置最遠(yuǎn)，這樣對(duì)寄存器 Ri所含的變量和變量 在主存中的情況必須先做如下調(diào)整：即對(duì) RVALUE[Ri]中的 每一變量 M，如果 M不是 A且 AVALUE[M]不包含 M， 則需完 成以下處理： ①生成目標(biāo)代碼 ST Ri， M；即把不是 A的變量值由 Ri中送 入內(nèi)存中 ②如果 M不是 B，則令 AVALUE[M]={M}，否則，令 AVALUE[M]={M,Ri} ③ 刪除 RVALUE[Ri]中的 M 32 （ 4）給出 R，返回 33 ?這樣，一旦得到一個(gè)為四元式運(yùn)算的操作寄存器 R，就可 以進(jìn)行代碼生成，而當(dāng)目標(biāo)代碼生成完成后，則又需修改 寄存器的使用信息和地址信息 ?用圖 ： 34 35 36 167。1 第十二章 代碼生成 ?第一節(jié) 代碼生成概述 ?第二節(jié) 一個(gè)簡(jiǎn)單的代碼生成程序 ?第三節(jié) 幾種常用
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1