編譯原理之代碼生成-文庫(kù)吧
2025-04-23 04:33 本頁(yè)面
【正文】 ea表示 ?call callee的實(shí)現(xiàn) ? ST , here+20 ?//保存返回地址 ? BR ... ?callee中的語(yǔ)句 return ? BR * *為突出重點(diǎn)，經(jīng)常將活動(dòng)記錄中其它的部分忽略。 常量 1字長(zhǎng) 實(shí)際為一個(gè)常量 1字長(zhǎng) 常量 1字長(zhǎng) 一個(gè)指令 1字長(zhǎng) 一個(gè)指令 1字長(zhǎng) 返回地址 例子 ?三地址代碼 ? action1 ? call p ? action 2 ? halt //p的代碼 ? action3 ? return 活動(dòng)記錄棧式分配 ?寄存器 SP指向棧頂 ?第一個(gè)過(guò)程（ main）初始化棧區(qū) ?過(guò)程調(diào)用指令序列 ? ADD SP, SP, //增加棧指針 ,越過(guò)調(diào)用者自身的活動(dòng)記錄 ? ST 0(SP), here+16 //保存返回地址 ? BR //轉(zhuǎn)移到被調(diào)用者 ?返回指令序列 ? BR *0(SP) //被調(diào)用者最后執(zhí)行，返回調(diào)用者 ? SUP SP, SP, //調(diào)用者中減低棧指針 34 例：快速排序 未完，轉(zhuǎn)下頁(yè) 例 :快速排序 接上頁(yè) 名字的運(yùn)行時(shí)刻地址 ?在三地址語(yǔ)句中使用名字（實(shí)際上是按符號(hào)表?xiàng)l目提供的信息）來(lái)引用變量 ?三地址語(yǔ)句 x=0 ? 如果 x分配在開(kāi)始位置為 static靜態(tài)區(qū)域，且符號(hào)表中保存的相對(duì)地址為 12，則可以譯為： ?static[12] = 0 ?設(shè)靜態(tài)區(qū)從 100開(kāi)始，則也可譯為 LD 112 0 ? 如果 x分配在棧區(qū)，且相對(duì)地址為 12，則 ?LD 12(SP) 0 基本塊和流圖 ?中間代碼的流圖表示法 ? 中間代碼劃分成為 基本塊 (basic block)，其特點(diǎn)是單入口單出口，即： ?控制流只能從第一個(gè)指令進(jìn)入 ?除了基本塊最后一個(gè)指令，控制流不會(huì)跳轉(zhuǎn) /停機(jī) ? 流圖中結(jié)點(diǎn)是基本塊，邊指明了哪些基本塊可以跟在一個(gè)基本塊之后運(yùn)行 ?流圖可作為優(yōu)化的基礎(chǔ) ? 它指出了基本塊之間的控制流 ? 可根據(jù)流圖了解一個(gè)值是否會(huì)被使用等信息 劃分基本塊的算法 ?輸入：三地址指令序列 ?輸出：基本塊的列表 ?方法： ? 確定 leader指令（基本塊的第一個(gè)指令）符合以下任一條： ?中間代碼的第一個(gè)三地址指令 ?任意一個(gè)條件或無(wú)條件轉(zhuǎn)移指令的目標(biāo)指令 ?緊跟在一個(gè)條件 /無(wú)條件轉(zhuǎn)移指令之后的指令 ? 確定基本塊 ?每個(gè)首指令對(duì)應(yīng)于一個(gè)基本塊：從首指令（包含）開(kāi)始到下一個(gè)首指令（不含） 基本塊劃分舉例 ?第一個(gè)指令 ? 1 ?跳轉(zhuǎn)指令的目標(biāo) ? 13 ?跳轉(zhuǎn)指令的下一條指令 ? 12 ?基本塊： 11； 22； 39(包括跳轉(zhuǎn)語(yǔ)句 )； 1011(包括跳轉(zhuǎn)語(yǔ)句 ) ； 1212； 1317 (包括跳轉(zhuǎn)語(yǔ)句 ) 下次引用信息 ?變量值的使用 ? 如果三地址語(yǔ)句 i對(duì) x賦值、三地址語(yǔ)句 j的運(yùn)算分量含 x，且從 i到 j有一條路徑，且路徑上無(wú)對(duì) x的重新賦值，則稱 j使用 了語(yǔ)句 i計(jì)算得到的 x值，稱 x在語(yǔ)句 i處 活躍 （以后有用 ）x(i)=y或 n。 ?下次引用和活躍信息可用于代碼生成 ? 如果 x在 i處不活躍，且 x占用了一個(gè)寄存器，則該寄存器在 i后可用于其它目的。 活躍變量與非活躍變量 ?⒈ 變量的定值點(diǎn)和使用點(diǎn)： ? 設(shè)有四元式： q(w B C A ) ? B,C的使用點(diǎn) (q) ? A的定值點(diǎn) (q) ?⒉ 活躍變量與非活躍變量 ? 【 活躍變量 】 一個(gè)變量從某時(shí)刻 (q)起 ,到下一個(gè)定義點(diǎn)止，其間若有使用點(diǎn)，則稱該變量在 q是活躍的 (y),否則稱該變量在 q是非活躍的 (n)。 ? 簡(jiǎn)單的說(shuō)， Q活躍就是指 Q定義的值被使用過(guò)。 ? q一般為各個(gè)行號(hào) 確定基本塊中的活躍性、下次引用 ?輸入：基本塊 B，開(kāi)始時(shí) B的所有非臨時(shí)變量都是活躍的； ?輸出：每個(gè)語(yǔ)句 i中變量的活躍性、下次使用信息 ?方法： ? 所有的非臨時(shí)變量初始化為活躍的，從 B的最后一個(gè)語(yǔ)句開(kāi)始 反向掃描 , ? 對(duì)于每個(gè)語(yǔ)句 i： x=y+z。 ? 令語(yǔ)句 i和 x、 y、 z的當(dāng)前活躍性信息 /使用信息關(guān)聯(lián) ? 設(shè)置 x為不活躍、無(wú)下次引用 ? 設(shè)置 y和 z為活躍，并指明它們的下一次使用為語(yǔ)句 i 注意二和三順序不能錯(cuò)， ? 查看基本塊 a=a+b,a最終是活躍還是？ 流圖的構(gòu)造 ?流圖的頂點(diǎn)是基本塊 ?兩個(gè)頂點(diǎn) B和 C之間有一條有向邊
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1