研究生院第十章.ppt

《研究生院第十章.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《研究生院第十章.ppt（80頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第十章代碼生成,代碼生成器設(shè)計(jì)中的問(wèn)題 目標(biāo)機(jī)器 下次引用信息 一個(gè)簡(jiǎn)單的代碼生成器 指令調(diào)度 寄存器優(yōu)化,代碼生成器的位置,各種代碼的形式 中間代碼: 后綴式，三地址代碼，語(yǔ)法樹(shù) 符號(hào)表中的項(xiàng)：名字，類(lèi)型，嵌套深度，偏移量 目標(biāo)代碼：絕對(duì)機(jī)器代碼，可再定位代碼，匯編 代碼生成器的輸出必須是正確和高質(zhì)量的 產(chǎn)生最優(yōu)化代碼的問(wèn)題是不可判定的,代碼生成器設(shè)計(jì)中的問(wèn)題,代碼生成器 依賴(lài)于目標(biāo)機(jī)器和操作系統(tǒng) 要充分發(fā)揮目標(biāo)機(jī)器的能力：充分利用目標(biāo)機(jī)器的資源 代碼生成器固有的問(wèn)題 存儲(chǔ)管理 指令選擇 寄存器分配 計(jì)算次序選擇 可移植的代碼生成器 機(jī)器描述,代碼生成器的輸入,符號(hào)表信息 決定中間表示中名字

2、所代表的數(shù)據(jù)對(duì)象的運(yùn)行地址 偏移量 作用域 可能在動(dòng)態(tài)時(shí)刻作為調(diào)試信息存在 中間表示 代碼生成的很多技術(shù)是可以用于不同的中間表示的 代碼生成前，中間表示記錄了足夠詳細(xì)的程序信息 名字的值可以表示為目標(biāo)機(jī)器能夠直接操作的數(shù) 類(lèi)型檢查已經(jīng)完成 明顯的語(yǔ)義錯(cuò)誤已經(jīng)發(fā)現(xiàn),目標(biāo)程序,代碼生成器的輸出：目標(biāo)程序 絕對(duì)機(jī)器語(yǔ)言 可以放在內(nèi)存中固定地方，并立即執(zhí)行 小程序、需要迅速編譯和執(zhí)行 可重定位的機(jī)器語(yǔ)言 程序可以分為多個(gè)目標(biāo)模塊，分別編譯 需要連接裝配器將一組可重定位模塊一起裝入執(zhí)行 需要額外的開(kāi)銷(xiāo)，但靈活：可分別編譯子程序和從目標(biāo)模塊中調(diào)用其它先前編譯好的程序模塊 如果目標(biāo)機(jī)器不能自動(dòng)處理重定位，則

3、編譯器必須提供顯式的重定位信息給裝配程序 匯編語(yǔ)言 代碼生成的過(guò)程容易：可以產(chǎn)生符號(hào)指令和利用匯編器的宏 避免了重復(fù)匯編器的工作,存儲(chǔ)管理,把程序中的名字映射到運(yùn)行時(shí)的目標(biāo)對(duì)象的地址是由前端和代碼生成器共同完成的 語(yǔ)言中過(guò)程的語(yǔ)義決定了運(yùn)行時(shí)刻名字如何與存儲(chǔ)空間相聯(lián)系 對(duì)名字的引用通過(guò)符號(hào)表 記錄了名字在過(guò)程數(shù)據(jù)區(qū)的相對(duì)地址 所需要的存儲(chǔ)空間 運(yùn)行時(shí)活動(dòng)記錄的管理 運(yùn)行時(shí)活動(dòng)記錄的分配和釋放作為過(guò)程調(diào)用和返回序列的一部分 call（調(diào)用） return（返回） halt（暫停） action（動(dòng)作），為其它語(yǔ)句占有位置,一個(gè)代碼生成器的輸入,其中，arr，i，j是過(guò)程s中定義的數(shù)據(jù)；buf和n

4、是過(guò)程p定義的數(shù)據(jù),靜態(tài)分配管理,call調(diào)用語(yǔ)句用兩條目標(biāo)機(jī)器指令實(shí)現(xiàn) MOV #here + 20 , callee. static-area GOTO callee. Code-area mov指令存放返回地址（#here + 20是一個(gè)字面常數(shù)，指向goto后的那條指令的地址） goto指令將控制轉(zhuǎn)移到被調(diào)用過(guò)程的目標(biāo)代碼 過(guò)程的返回 過(guò)程的返回指令表明一個(gè)過(guò)程的結(jié)束 第一個(gè)過(guò)程沒(méi)有調(diào)用者，以halt指令結(jié)束 GOTO * callee. static-area 按照活動(dòng)記錄中記錄的返回地址返回,靜態(tài)存儲(chǔ)管理：目標(biāo)代碼的例子,/* s的代碼 */ 100:ACTION1; 120:M

5、OV140 , 364/* 保存返回地址140 */ 132:GOTO200/* 調(diào)用p */ 140:ACTION2; 160:HALT /* p的代碼 */ 200:ACTION3; 220:GOTO * 364/* 返回到364單元里存放的地址 */ /* 300-363保留著s的活動(dòng)記錄 */ 300:/* 返回地址 */ 304:/* s的局部數(shù)據(jù) */ /* 364-451保留著p的活動(dòng)記錄 */ 364:/* 返回地址 */ 368:/* p的局部數(shù)據(jù) */,棧式分配管理,活動(dòng)記錄的存儲(chǔ)單元采用相對(duì)地址 SP：指向棧頂活動(dòng)記錄開(kāi)始的指針 過(guò)程調(diào)用的處理 第一個(gè)過(guò)程的代碼通過(guò)

6、將SP置為存儲(chǔ)器中棧區(qū)的開(kāi)始位置來(lái)初始化棧： MOV#stackstart, SP/* 初始化棧 */ 第一個(gè)過(guò)程的代碼 HALT/* 終止過(guò)程運(yùn)行 */ 過(guò)程調(diào)用序列給SP一個(gè)增量，并存儲(chǔ)返回地址及將控制轉(zhuǎn)移到被調(diào)用過(guò)程 ADD#caller, recordsize, SP/* 增加SP */ MOV#here + 16 , * SP/*存返回地址*/ GOTOcallee. code-area/*將控制轉(zhuǎn)移到被調(diào)用過(guò)程*/,棧式分配管理（續(xù)）,過(guò)程返回的處理 在被調(diào)用過(guò)程中 GOTO * 0 ( SP )/* 返回到調(diào)用過(guò)程 */ 在調(diào)用過(guò)程中，恢復(fù)SP SUB #caller. rec

7、ordsize , SP,棧式分配管理的例子,三地址代碼 /* s的代碼 */ action1 call q action2 Halt /* p的代碼 */ action3 return /* q的代碼 */ action4 call p action5 call q action6 call q return,,,,棧式分配管理的例子（續(xù)）,/* s的代碼 */ 100:MOV#600 , SP/* 初始化棧 */ 108:ACTION1 128:ADD#ssize , SP/* 調(diào)用序列開(kāi)始 */ 136:MOV152 , * SP/* 壓入返回地址 */ 144:GOTO300/* 調(diào)用

8、q */ 152:SUB#ssize , SP 160:ACTION2 180:HALT /* p的代碼 */ 200:ACTION3 220:GOTO* 0 (SP)/* 返回 */ /* q的代碼 */ 300:ACTION3 320:ADD#qsize , SP 328:MOV344 , * SP/* 壓入返回地址 */ 336:GOTO200/* 調(diào)用p */ 344:SUB#qsize , SP 600:/* 棧的開(kāi)始*/,棧式分配管理（續(xù)）,名字的運(yùn)行地址 靜態(tài)存儲(chǔ)策略 staticoffset 動(dòng)態(tài)存儲(chǔ)策略 局部名字 非局部名字 使用display表 這個(gè)指針在編譯時(shí)刻不能

9、確定，因此要在動(dòng)態(tài)時(shí)刻實(shí)現(xiàn)地址的最終確定 MOV#0 , 12(R3) R3是存放display表指針的寄存器,指令地址的決定,通過(guò)一個(gè)計(jì)數(shù)器決定每個(gè)指令的地址 標(biāo)號(hào)的處理：j: goto i/*j是當(dāng)前語(yǔ)句的號(hào)碼*/ 如果i小于j i出現(xiàn)在j之前，目標(biāo)地址是i對(duì)應(yīng)的三地址代碼的第一條指令地址 如果i大于j i出現(xiàn)在j之后，目標(biāo)地址此時(shí)不可知，可以利用回填的技術(shù)解決,指令選擇,目標(biāo)機(jī)器指令系統(tǒng)的性質(zhì)決定了指令選擇的難易程度 指令系統(tǒng)的一致性和完整性是重要因素 如果目標(biāo)機(jī)器不能以一致的方式支持各種數(shù)據(jù)類(lèi)型，則每種例外都要專(zhuān)門(mén)的處理 指令的速度和機(jī)器的特點(diǎn)是另一些重要的因素 如果不考慮目標(biāo)程序的效

10、率，則指令選擇是直截了當(dāng)?shù)?代碼的質(zhì)量取決于它的執(zhí)行速度和長(zhǎng)度 可以從多種指令中選擇合適的：a=a+1 MOVa , R0 ADD#1 , R0INCa MOVR0 , a 時(shí)間信息對(duì)代碼序列是重要的，但不是任何時(shí)候都精確的,指令選擇的例子,逐條語(yǔ)句地產(chǎn)生代碼的方法常常產(chǎn)生低質(zhì)量的代碼 a := b + c d := a + e MOVb , R0 ADDc , R0 MOVR0 , a MOVa , R0 ADDe , R0 MOVR0 , d,寄存器分配,快速的寄存器 通常，利用寄存器放置運(yùn)算對(duì)象的指令比運(yùn)算對(duì)象在內(nèi)存中的指令短些 執(zhí)行也快些 充分利用寄存器對(duì)高質(zhì)量的代碼生成是重要的,寄存

11、器 片內(nèi)CACHE 片外CACHE 主存 外存,,,,,,寄存器優(yōu)化 局部性?xún)?yōu)化,,寄存器分配（續(xù)）,寄存器使用的兩個(gè)子問(wèn)題 寄存器分配：為程序的某一點(diǎn)選擇駐留在寄存器中的一組變量 寄存器指派：挑出變量將要駐留的具體寄存器 寄存器分配的最優(yōu)化是NP完全的 特定要求的滿(mǎn)足,計(jì)算次序選擇,計(jì)算執(zhí)行的次序會(huì)影響目標(biāo)代碼的效率 選擇最佳次序是一個(gè)NP完全問(wèn)題 ld r1 , t:無(wú)，非,無(wú),非,3,活,活,3,,u:3,活；a,c:無(wú)，活,,無(wú),非,2,2,活,活,,a:2,活；b:無(wú)，活,無(wú),非,1,1,活,活,t:3,活；,,下次引用信息（4）,臨時(shí)名字的存儲(chǔ)分配 在需要臨時(shí)變量時(shí)申請(qǐng)一個(gè)新的名

12、字是簡(jiǎn)單有效的，但浪費(fèi)空間 如果兩個(gè)臨時(shí)變量不是同時(shí)活躍的，則可以壓縮在同一單元中 臨時(shí)變量存儲(chǔ)單元的分配： 依次檢查臨時(shí)變量區(qū)域的單元，找到第一個(gè)不含活躍臨時(shí)變量的單元，指派給待分配的臨時(shí)變量 如果沒(méi)有合適的單元，則在活動(dòng)記錄的臨時(shí)變量區(qū)域中增加一個(gè)單元,下次引用信息（5）,例子： t1 := a * at1 := a * a t2 := a * bt2 := a * b t3 := 2 * t2t2 := 2 * t2 t4 := t1 + t3t1 := t1 + t2 t5 := b * bt2 := b * b t6 := t4 + t5t1 := t1 + t2,一個(gè)簡(jiǎn)單的代碼生成

13、器（1）,這個(gè)代碼生成器的假設(shè)條件： 三地址語(yǔ)句的每種算符都有對(duì)應(yīng)的目標(biāo)機(jī)器算符 計(jì)算結(jié)果留在寄存器中盡可能長(zhǎng)的時(shí)間。只有在以下兩種情況才把它存入主存 此寄存器要用于其它計(jì)算 正好在過(guò)程調(diào)用、轉(zhuǎn)移或標(biāo)號(hào)語(yǔ)句之前 在基本塊的結(jié)尾，所有的寄存器都將保存，使得代碼生成算法簡(jiǎn)單,一個(gè)簡(jiǎn)單的代碼生成器（2）,后續(xù)的代碼盡可能引用變量在寄存器中的值，而不訪問(wèn)主存，如對(duì)a := b + c 如果b在Ri中，c在Rj中，b在此語(yǔ)句后不活躍，則可以為它生成代價(jià)為1的代碼ADD Rj , Ri，結(jié)果a存在Ri中 如果b在Ri中，c在內(nèi)存單元中，b仍然不再活躍，則有： ADD c , Ri 或： MOV c , R

14、j ADD Rj , Ri 如果c的值以后還要用，則第二種方式更好一些，因?yàn)榭梢灾苯訌募拇嫫鱎j中取得它的值 由于語(yǔ)義的復(fù)雜性，上述代碼生成可能要更為復(fù)雜,一個(gè)簡(jiǎn)單的代碼生成器（3）,寄存器描述和地址描述 代碼生成算法使用寄存器和名字的描述來(lái)跟蹤寄存器的內(nèi)容和名字的地址 寄存器描述記住每個(gè)寄存器當(dāng)前存的是什么 在每個(gè)塊的開(kāi)始，寄存器描述顯示所有寄存器為空（如果寄存器指派可以穿越塊的邊界，則此假設(shè)不成立） 塊的代碼生成過(guò)程中，每個(gè)寄存器保存零個(gè)或若干個(gè)名字的值 地址描述記住運(yùn)行時(shí)每個(gè)名字的當(dāng)前值可以在那個(gè)場(chǎng)所找到 這個(gè)場(chǎng)所可以是寄存器、棧單元、內(nèi)存地址或它們的集合等 這些信息可以存于符號(hào)表中，在

15、決定名字的訪問(wèn)方式時(shí)使用,一個(gè)簡(jiǎn)單的代碼生成器（4）,代碼生成算法 輸入：一個(gè)基本塊的三地址語(yǔ)句序列 輸出：指令序列 方法：對(duì)每個(gè)三地址語(yǔ)句x := y op z完成下列動(dòng)作 1調(diào)用函數(shù)getreg決定存放y op z計(jì)算結(jié)果的場(chǎng)所L，L通常是寄存器，也可以是內(nèi)存單元 2查看y的地址描述，確定y值當(dāng)前的一個(gè)場(chǎng)所y。如果y值當(dāng)前既在內(nèi)存單元又在寄存器中，選擇寄存器作為y。如果y的值還不在L中，則產(chǎn)生指令MOV y , L 3產(chǎn)生指令op z , L，其中z是z的當(dāng)前場(chǎng)所之一（同2一樣優(yōu)先選擇寄存器），修改x的地址描述，以表示x在場(chǎng)所L。如果L是寄存器，修改它的描述，以表示它含x的值 4如果y和（

16、或）z的當(dāng)前值不再引用，在塊的出口也不活躍，并且在寄存器中，則修改寄存器描述，以表示在執(zhí)行了x := y op z后，這些寄存器分別不再含y和（或）z的值,一個(gè)簡(jiǎn)單的代碼生成器（5）,基本塊結(jié)束的處理 在基本塊的出口，用MOV指令把在寄存器中的活躍變量的值保存 值在寄存器中 這個(gè)值在出口活躍 復(fù)寫(xiě)語(yǔ)句的處理：x := y y在寄存器中 改變寄存器和地址的描述，記住x的值出現(xiàn)在該寄存器中 如果y不再引用，且在塊的出口不活躍，該寄存器不再保存y的值 y的值僅在內(nèi)存中 若記住x的值在y的內(nèi)存單元中，但如果更新y的值復(fù)雜；可以用getreg找到一個(gè)存放y的寄存器，并記住該寄存器是存放x的場(chǎng)所 或產(chǎn)生指

17、令MOV y , x，如果x在塊中不再引用，此法較好,一個(gè)簡(jiǎn)單的代碼生成器（6）,函數(shù)getreg 返回保存語(yǔ)句x := y op z的x值的場(chǎng)所L 簡(jiǎn)單的實(shí)現(xiàn)方法：基于下次引用信息 1如果名字y在寄存器中，此寄存器不含其它名字的值，并且y不活躍，且在執(zhí)行x := y op z后沒(méi)有下次引用，則返回y的這個(gè)寄存器作為L(zhǎng) 21失敗時(shí)，如果有的話(huà)，返回一個(gè)空閑寄存器 32不成功時(shí)，如果x在塊中有下次引用，或op是必須使用寄存器的算符（如變址），則找一個(gè)已被占用的寄存器R 將R中的值根據(jù)存有的變量（可能不止一個(gè)）保存到內(nèi)存單元中，并修改相關(guān)的地址描述 R的選擇要考慮spill的代價(jià) 4如果x在本塊中

18、不再引用，或者找不到適當(dāng)?shù)谋徽加眉拇嫫鳎瑒t選擇x的內(nèi)存單元作為L(zhǎng),一個(gè)簡(jiǎn)單的代碼生成器（7）,例子： 賦值語(yǔ)句d := ( a b ) + ( a c ) + ( a c )可以翻譯成下面的三地址代碼序列 t := a b ; u := a c ; v := t + u ; d := v + u d在出口活躍，產(chǎn)生的代碼序列： 語(yǔ) 句生成的代碼寄存器描述地址描述 寄存器空 t := a bMOV a , R0 R0含t SUB b , R0t在R0中 u := a c MOV a , R1 R0含tt在R0中 SUB c , R1 R1含uu在R1中 v := t + u ADD

19、 R1 , R0 R0含vu在R1中 R1含uv在R0中 d := v + uADD R1 , R0 R0含dd在R0中 MOV R0 , dd在R0和內(nèi)存中,,,,,,,一個(gè)簡(jiǎn)單的代碼生成器（8）,例子的討論 上述代碼的代價(jià)為12 可以在第一個(gè)指令后增加MOV R0 , R1，從而將代價(jià)減少為11（刪去了MOV a , R1）,一個(gè)簡(jiǎn)單的代碼生成器（9）,為其它類(lèi)型的語(yǔ)句產(chǎn)生代碼 變址語(yǔ)句的處理，其中： 偏移為Si 活動(dòng)記錄的指針在寄存器A 寄存器R是調(diào)用函數(shù)getreg時(shí)返回的寄存器 對(duì)于第一個(gè)賦值，如果a在塊中有下次引用，且寄存器R是可用的，則a留在寄存器R中 在第二個(gè)語(yǔ)句中，假定

20、a靜態(tài)分配 語(yǔ) 句 i在寄存器Ri中 i在內(nèi)存Mi中 i在棧中 代 碼 代價(jià) 代 碼 代價(jià) 代 碼 代價(jià) a := bi MOV b(Ri) , R 2 MOV Mi , R 4 MOV Si(A) , R 4 MOV b(R) , R MOV b(R) , R ai := b MOV b , a(Ri) 3 MOV Mi , R 5 MOV Si(A) , R 5 MOV b , a(R) MOV b , a(R),,,,,,,,,,,,一個(gè)簡(jiǎn)

21、單的代碼生成器（10）,指針語(yǔ)句的處理，其中： 偏移為Sp 活動(dòng)記錄的指針在寄存器A 寄存器R是調(diào)用函數(shù)getreg時(shí)返回的寄存器 對(duì)于第一個(gè)賦值，如果a在塊中有下次引用，且寄存器R是可用的，則a留在寄存器R中 在第二個(gè)語(yǔ)句中，假定a靜態(tài)分配 語(yǔ) 句 p在寄存器Rp中 p在內(nèi)存Mp中 p在棧中 代 碼 代價(jià) 代 碼 代價(jià) 代 碼 代價(jià) a := * p MOV * Rp , a 2 MOV Mp , R 3 MOV Sp(A) , R 3 MOV * R , R MOV * R , R * p := a

22、 MOV a , * Rp 2 MOV Mp , R 4 MOV a , R 5 MOV a , * R MOV R , *Sp(A),,,,,,,,,,,,一個(gè)簡(jiǎn)單的代碼生成器（11）,條件語(yǔ)句：兩種實(shí)現(xiàn)方式，以if x y，則CMP x , y置條件碼為正等 條件轉(zhuǎn)移機(jī)器指令根據(jù)指定的條件（ , , =）是否滿(mǎn)足來(lái)決定是否轉(zhuǎn)移，如果用指令CJ<= z表示如果條件碼是負(fù)或零則轉(zhuǎn)到z，所以有 CMP x , y CJ< z,一個(gè)簡(jiǎn)單的代碼生成器（12）,條件碼的描述的記錄 這個(gè)描述告訴我們上次設(shè)置條件碼的名字和比較的名字對(duì) x := y

23、 + zMOV y , R0 if x < 0 goto zADD z , R0 MOV R0 , x CJ< z 根據(jù)條件碼描述可以知道，在ADD z , R0之后，條件碼是由x設(shè)置的,程序的依賴(lài)關(guān)系,依賴(lài)關(guān)系是什么？ 依賴(lài)關(guān)系表明了兩個(gè)語(yǔ)句（或操作、計(jì)算）之間在執(zhí)行順序上存在的限制 如果兩個(gè)語(yǔ)句（或操作、計(jì)算）間存在著依賴(lài)關(guān)系，則這兩個(gè)語(yǔ)句（或操作、計(jì)算）的執(zhí)行必須滿(mǎn)足依賴(lài)關(guān)系的要求 如果兩個(gè)語(yǔ)句（或操作、計(jì)算）間沒(méi)有依賴(lài)關(guān)系，則這兩個(gè)語(yǔ)句（或操作、計(jì)算）可以被并行執(zhí)行或調(diào)整執(zhí)行的順序。 依賴(lài)分析是分析語(yǔ)句（或操作、計(jì)算）間的依賴(lài)關(guān)系，從而確定它們是否可以并行執(zhí)行 依賴(lài)關(guān)系的分類(lèi) 數(shù)據(jù)依賴(lài)

24、關(guān)系 控制依賴(lài)關(guān)系 控制流分析的結(jié)果 計(jì)算的執(zhí)行與否取決于控制條件是否滿(mǎn)足,數(shù)據(jù)依賴(lài)關(guān)系的定義,定義：如果語(yǔ)句S在語(yǔ)句S之前執(zhí)行，且兩個(gè)語(yǔ)句訪問(wèn)相同變量V,其中至少有一個(gè)語(yǔ)句是對(duì)V賦值，則我們說(shuō)這兩個(gè)語(yǔ)句之間存在數(shù)據(jù)依賴(lài)關(guān)系，記為ss： 如果V在S中定義，在S中使用，稱(chēng)為真依賴(lài)，或流依賴(lài)，記為s ts 如果V在S中使用，在S中定義，稱(chēng)為反依賴(lài)，記為sas 如果V在S和S中定義，稱(chēng)為輸出依賴(lài)，記為SoS 如果V在S和S中使用，稱(chēng)為輸入依賴(lài)，記為SiS 例子 S1: A=1.0 S2: B=A+3.14159 S3: A=1/3*(C-D) (無(wú)對(duì)A,B,C,D賦值） S4: A=(B*3.8)

25、/1.78,依賴(lài)圖,以語(yǔ)句為節(jié)點(diǎn)，依賴(lài)關(guān)系為邊，上例的依賴(lài)圖為：,,面向指令調(diào)度的依賴(lài)圖,無(wú)環(huán)區(qū)域的依賴(lài)圖是一個(gè)有向無(wú)環(huán)圖G(V, E)， 其中節(jié)點(diǎn)表示操作，邊表示兩個(gè)操作的執(zhí)行時(shí)刻必須滿(mǎn)足的約束。 依賴(lài)邊的分類(lèi) 流依賴(lài)、反依賴(lài)、輸出依賴(lài) 由訪問(wèn)寄存器導(dǎo)致的依賴(lài) vs 由訪問(wèn)內(nèi)存導(dǎo)致的依賴(lài) 投機(jī)依賴(lài)邊 邊上通常記有所需的延遲，這個(gè)延遲與操作及依賴(lài)邊的類(lèi)型有關(guān) 偽依賴(lài)所需的延遲通常不大于1。 內(nèi)存取數(shù)操作的延遲通常難于在編譯時(shí)刻確定。 延遲的具體值由機(jī)器模型提供。,依賴(lài)圖的構(gòu)造,構(gòu)造依賴(lài)圖通常可通過(guò)對(duì)基本塊內(nèi)的所有操作的一次或多次遍歷完成，以構(gòu)造流依賴(lài)邊為例，算法如下：,void Build_D

26、AG_For_BB(BB* bb) For each op in bb, from head to tail For each operand of op Let def_op_list be the defining ops list of operand ; while (def_op_list != NULL) Get an def_op from def_op_list; If (dependence exists between def_op and op) Build an edge between def_op and op;

27、 Add op to the defining ops list of ops results. Remove those ops in the list that shadowed by op. ,add t1 = 8,p,ld4 t2 = log,add t2 = 1,t2,mov out0 = 0,br.ret rp,ld4 out0 = t4,shladd t4 = n,2,t3,ld4 t3 = p,st4 log = t2,ld4 count = t1,cmp4.ge p1,p2=n,count,struct dyn-array int *x; int co

28、unt; ; dyn-array *p; If( n count ) (*log)++; return p-xn; else return 0; ,,,,,,,,,,,,Y,N,依賴(lài)圖的例子,指令調(diào)度,在滿(mǎn)足依賴(lài)關(guān)系、資源約束及硬件施加的其它約束條件的前提下，重新排定指令執(zhí)行的順序，提高資源利用率，使多個(gè)操作能夠并行執(zhí)行，同時(shí)減少因相關(guān)引起的處理器停頓，以縮短程序的執(zhí)行時(shí)間。 NP完全問(wèn)題 指令調(diào)度的復(fù)雜性來(lái)自于程序控制流和數(shù)據(jù)流的復(fù)雜性，以及硬件平臺(tái)的復(fù)雜性。 處理上述復(fù)雜性的方法： 限制指令調(diào)度的范圍，將流圖劃分為若干具有良好性質(zhì)的、規(guī)模可控的區(qū)域。 將機(jī)器相關(guān)部分從指令調(diào)度中分

29、離出來(lái)。,指令調(diào)度的一般步驟,構(gòu)造區(qū)域 (Region) 構(gòu)造區(qū)域上的依賴(lài)圖 根據(jù)依賴(lài)圖進(jìn)行調(diào)度 代碼的修正 若有未調(diào)度的代碼，重復(fù)上述步驟。,指令調(diào)度,依據(jù)區(qū)域流圖的性質(zhì)，可如下分類(lèi)：,指令調(diào)度,,,Trace 調(diào)度,選擇調(diào)度,Superblock/Hyperblock,SEME區(qū)域調(diào)度,,無(wú)環(huán)調(diào)度,,,核心識(shí)別,模調(diào)度,軟件流水,,全局調(diào)度,局部調(diào)度,,,,,,,,,,,,,局部指令調(diào)度算法表調(diào)度,void Schedule_BB(BB* bb) Build dependence graph for bb; Compute ready candidates for current cycl

30、e; while (candidate list not empty) If (theres no empty slot in current cycle or all candidates tried) Advance to next cycle. Reset all candidates untried. Update micro-schedulers internal states. Pick an op with highest priority from the candidate list to schedule; Query machine mode

31、l whether the selected op can be commited. if (machine model answers NO) set the op tried so that it will not be tried in current cycle. else commit the code motion. Update DAG, Candidate list, and Micro-Scheduler internal states, etc. ,就緒隊(duì)列,一般而言，在某一時(shí)刻的就緒操作應(yīng)滿(mǎn)足下列條件： op在依賴(lài)圖上的所有依賴(lài)前驅(qū)均已調(diào)度過(guò)。 若op引

32、用了某個(gè)操作op的結(jié)果，op于第i拍發(fā)出，且兩者之間的延遲為l，則op的發(fā)出時(shí)刻不得早于i+l。 若硬件有記分牌，則條件 2 可以去掉，這樣在調(diào)度過(guò)程中就緒隊(duì)列不會(huì)為空，但隊(duì)列中的操作地位不同。 給每個(gè)就緒操作加一個(gè)等待時(shí)間，每次調(diào)度總是選取等待時(shí)間最小的操作。 比較當(dāng)前時(shí)刻與每個(gè)操作的最早開(kāi)始時(shí)間。 就緒隊(duì)列在調(diào)度開(kāi)始前計(jì)算一次，以后每調(diào)度一個(gè)操作，只需檢查其在依賴(lài)圖上的后繼。,操作的調(diào)度優(yōu)先序,決定調(diào)度操作的先后順序時(shí)使用的啟發(fā)式信息： 執(zhí)行頻率 關(guān)鍵路徑 投機(jī)性 所需補(bǔ)償代碼數(shù)量 依賴(lài)圖上的后繼個(gè)數(shù) 寄存器的使用情況 是否在調(diào)度過(guò)程中動(dòng)態(tài)更新上述信息需在代碼質(zhì)量與編譯時(shí)間之間作出折中。,

33、,,,,,,,,,,,,,,,A,B,C,D,E,F,G,,,,,,,,,,E,NR,F,B,G,,A,C,D a nested region as NR,全局的情形：構(gòu)造區(qū)域,調(diào)度區(qū)域一般是無(wú)環(huán)的。依據(jù)流圖的結(jié)構(gòu)，基本塊的執(zhí)行頻率，以及區(qū)域的預(yù)期大小等啟發(fā)式信息構(gòu)造。,Trace 調(diào)度,Trace: 執(zhí)行過(guò)程中可能經(jīng)過(guò)的一個(gè)基本塊的線(xiàn)性序列 Trace 的選擇： 根據(jù)分支概率及是否需要插入補(bǔ)償代碼等啟發(fā)式規(guī)則選擇執(zhí)行路徑，代碼移動(dòng)局限于該路徑 局部調(diào)度方法的延伸：以執(zhí)行頻率較低的路徑上代碼執(zhí)行時(shí)間的增加為代價(jià)，換取頻繁執(zhí)行的路徑上代碼執(zhí)行時(shí)間的縮減,Trace 調(diào)度：算法,步驟： 估算每個(gè)操

34、作的執(zhí)行頻率 挑選Trace 使用某種局部指令調(diào)度方法如表調(diào)度對(duì)形成的Trace進(jìn)行調(diào)度 用調(diào)度完的代碼替換流圖中原來(lái)的Trace，必要時(shí)在Trace之外插入相應(yīng)的補(bǔ)償代碼 遍歷調(diào)度后的流圖并釋放代碼 Trace 調(diào)度的問(wèn)題： 插入補(bǔ)償代碼的過(guò)程在實(shí)現(xiàn)上復(fù)雜，且可能產(chǎn)生冗余 在Trace 內(nèi)作的一些優(yōu)化，如復(fù)寫(xiě)傳播，死代碼刪除等，由于split和join節(jié)點(diǎn)的存在而受到限制 若分支概率相近，Trace 難于選擇。,Superblock 調(diào)度,A,B,C,F,,,,,,,E,D,,,,,,,,A,B,C,F,,,,,,,E,D,,,,,,,,F,Z,Z,Y,Y,,,,,,尾復(fù)制,Hyperblo

35、ck 調(diào)度,條件執(zhí)行 體系結(jié)構(gòu)提供64個(gè)1位的謂詞寄存器(predicate registers) 帶有謂詞的指令僅當(dāng)謂詞為真時(shí)改變機(jī)器狀態(tài)，否則相當(dāng)于一條NOP指令 編譯器為分支兩側(cè)的指令分配不同的謂詞寄存器，由比較 (cmp) 指令在執(zhí)行時(shí)刻為謂詞賦值。 條件執(zhí)行可消除分支 將控制依賴(lài)轉(zhuǎn)化為數(shù)據(jù)依賴(lài) 減少由于分支預(yù)測(cè)錯(cuò)誤帶來(lái)的開(kāi)銷(xiāo) 有可能增加關(guān)鍵路徑長(zhǎng)度,寄存器分配,決定程序中哪些變量的值應(yīng)該存放在寄存器中。 減少訪存和復(fù)寫(xiě)操作。 最重要的編譯優(yōu)化之一： 訪問(wèn)寄存器和存儲(chǔ)器的代價(jià)相差在一個(gè)數(shù)量級(jí)以上。 寄存器的數(shù)目雖已大為增加，但仍是十分稀缺的資源。 許多優(yōu)化的效果依賴(lài)寄存器分配的結(jié)果。

36、寄存器分配與寄存器指派 寄存器分配：決定哪些變量該占用寄存器。 寄存器指派：決定變量該使用哪個(gè)寄存器。 Caller-Save與Callee-Save寄存器 傳遞參數(shù)與返回值的寄存器 葉過(guò)程與非葉過(guò)程,活躍區(qū)間與干涉,一個(gè)變量的活躍區(qū)間： 一個(gè)變量的（極小化）活躍區(qū)間是變量的定值與引用的一個(gè)子集，對(duì)于此集合中的任意定值dm和引用un，或者un在dm的du鏈上，或者存在一個(gè)由此集合中的定值與引用組成的交錯(cuò)序列dm=d0、u0、d1、u1、、、dk、uk= un，其中的任何一個(gè)ui、同時(shí)在di和di+1的du鏈上。 直觀上，變量的活躍區(qū)間對(duì)應(yīng)于流圖上聯(lián)結(jié)變量的定值點(diǎn)和引用點(diǎn)的一個(gè)連通區(qū)域。 干涉：

37、 兩個(gè)變量的活躍區(qū)間干涉（簡(jiǎn)稱(chēng)兩個(gè)變量干涉），若在其中某個(gè)變量的定值處，另一個(gè)變量是定值到達(dá)和活躍的。,圖的著色與寄存器分配,當(dāng)前占統(tǒng)治地位的寄存器分配方法是圖著色方法。 圖的k著色問(wèn)題 寄存器分配歸結(jié)為圖著色問(wèn)題： 首先構(gòu)造干涉圖，圖中每個(gè)結(jié)點(diǎn)代表一個(gè)變量的活躍區(qū)間，如果兩個(gè)變量干涉，則在相應(yīng)的結(jié)點(diǎn)vi和vj之間用邊eij連接。 假設(shè)目標(biāo)機(jī)有k個(gè)寄存器可用，則寄存器分配的問(wèn)題就變成對(duì)這個(gè)圖找一個(gè)k著色的方案。,x = ... y = ... = ... x z = ... = y = z,y,,,,,,,,,,z,x,,,Requires Two Colors,y,z,x,干涉圖的例子,

38、x,,,,,,,,,z,y,,,有控制流的情形,,,,,,,,,x,y,z,需要兩種顏色,,圖著色寄存器分配Chaitins,判斷一個(gè)圖是否k可著色是一個(gè)NP完全問(wèn)題。 注意到圖中度不大于k的節(jié)點(diǎn)總可以被著色，Chaitin提出了一種啟發(fā)式方法：持續(xù)地從圖中刪掉度小于k的節(jié)點(diǎn)，若此過(guò)程一直進(jìn)行到所有的節(jié)點(diǎn)均被刪除，則圖是k可著色的。若此過(guò)程阻塞，即圖中所有節(jié)點(diǎn)的度均不小于k，則依據(jù)溢出代價(jià)大小，從圖中選擇某個(gè)節(jié)點(diǎn)，刪除該節(jié)點(diǎn)及其相連的邊。然后重復(fù)上述過(guò)程。,極小化活躍區(qū)間,Rename(CFG) for each (var) lrsvar = ; for each (d in dd_

39、chain(var)) lr = new_a_lr(du_chain(d)); lrsvar += lr; endfor do for each (lr1 in lrsvar) for each (lr2 in lrsvar ,首先每個(gè)變量的每個(gè)du鏈都被初始化為一個(gè)活躍區(qū)間。 其次，若同一個(gè)變量的兩個(gè)du鏈包含公共的引用點(diǎn)，則將相應(yīng)的兩個(gè)活躍區(qū)間合并成一個(gè)活躍區(qū)間。 疊代直到活躍區(qū)間的集合穩(wěn)定。,,極小化活躍區(qū)間,活躍區(qū)間的極小化有利于減輕變量間的干涉，減小干涉圖的顏色數(shù)。,for ( i=0; i

40、 d; a = c + d; c = a + d; ,for ( i=0; i

41、 live_var - variable used by definition in S ; if S is not of the form a = b; make every var in live_var interfere with the variables defined in S; live_var = live_var all the variables used by reference in S; ,計(jì)算溢出代價(jià),最小化被溢出變量的代價(jià)值的和 溢出代價(jià)： 分配的優(yōu)先序： 代價(jià)較大的變量的優(yōu)先級(jí)也較大 干涉圖上度較大的變量的優(yōu)先級(jí)較低,Cost(lr)

42、= LOAD_COST x LoadTimes + STORE_COST x StoreTimes + MOVECOST x MoveTimes,Priority(lr) = Cost(lr) / Deg(lr),圖著色寄存器分配Priority-Based,Chow和Hennessy提出按活躍區(qū)間的優(yōu)先級(jí)從高到低的順序?qū)D進(jìn)行著色 假定變量原本在內(nèi)存中 全局與局部?jī)杀榧拇嫫鞣峙洌珿RA為L(zhǎng)RA預(yù)留寄存器 粗粒度：以基本塊為分配單位 優(yōu)先級(jí)根據(jù)為變量分配寄存器能夠減少的訪存操作決定 一遍著色，沒(méi)有Chaitin式的先化簡(jiǎn)后回溯 提出活躍區(qū)間分割（Live Range Splitting），即當(dāng)

43、著色過(guò)程阻塞時(shí)，把活躍區(qū)間分成若干較小的活躍區(qū)間。這樣可以產(chǎn)生較少的溢出,寄存器分配：有謂詞的情形,x,,z,y,,,,,x,,,z,,,,,,需要三個(gè)寄存器,y,,(p2),(p1),(p2),(p1),謂詞分析,p0,,p2,p1,,,,,x,,y,,,z,,,,,P1與p2不可能同時(shí)為真,(p2),(p1),(p1),(p2),,,,考慮謂詞的寄存器分配,x,,z,y,,,根據(jù)謂詞分析的結(jié)果構(gòu)造干涉圖,,,x,,y,,,z,,,,,只需要兩個(gè)寄存器,(p2),(p1),(p1),(p2),指令調(diào)度和寄存器優(yōu)化的時(shí)序問(wèn)題,先做寄存器分配，再作指令調(diào)度 先做寄存器分配的優(yōu)點(diǎn)在指令級(jí)并行度低、

44、寄存器又少的處理機(jī)上得以體現(xiàn) 從指令調(diào)度的觀點(diǎn)看該順序的最主要問(wèn)題是：寄存器分配會(huì)帶來(lái)反依賴(lài)和輸出依賴(lài)，這將在一定程度上影響指令調(diào)度的效果 先做指令調(diào)度，再作寄存器分配 雖然更好的指令調(diào)度是人們所期望的，但如果代碼需要的寄存器比能獲得的寄存器還要多的話(huà)，則這個(gè)事實(shí)是不能令人接受的 指令調(diào)度會(huì)增大寄存器分配的壓力，再好的指令調(diào)度所獲得的性能的提高也無(wú)法彌補(bǔ)由于較差的寄存器分配所帶來(lái)的損失,指令調(diào)度和寄存器優(yōu)化的時(shí)序問(wèn)題的例子,1) Val3 <= val1 * 3假設(shè)乘法指令需要4拍 2) addr1 <= val3 3) Val4 <= val1 * 2 4) addr2 <= val4 若先

45、做寄存器分配，再作指令調(diào)度 由于val3和val4此后不再被繼續(xù)引用，所以可以分在一個(gè)寄存器中 發(fā)射時(shí)間指令 0r3 <= r1 * 3 4store addr1 , r3 5r3 <= r1 * 2 9store addr2 , r3共需要10拍,指令調(diào)度和寄存器優(yōu)化的時(shí)序問(wèn)題的例子,若先做指令調(diào)度，再作寄存器分配 此時(shí)，由于val3和val4活躍區(qū)間重疊，所以不可以分在一個(gè)寄存器中 發(fā)射時(shí)間指令 0r3 <= r1 * 3 1r4 <= r1 * 2 4store addr1 , r3 5store addr2 , r4共需要6拍 而且如果處理機(jī)能同時(shí)發(fā)射兩條定點(diǎn)乘法和兩條store指令的話(huà)，這一組指令可以在5拍完成,指令調(diào)度和寄存器優(yōu)化的時(shí)序問(wèn)題（續(xù)）,協(xié)作式指令調(diào)度和寄存器分配 避免的分裂考慮上述兩個(gè)問(wèn)題引起的缺乏通訊的問(wèn)題 但算法過(guò)于復(fù)雜，難于實(shí)現(xiàn)，具有理論意義 一種實(shí)際的時(shí)序 先做指令調(diào)度（由于寄存器較多，所以可以忍受） 再作寄存器分配，但為了獲得較好的效果，可能會(huì)移動(dòng)基本塊中的指令位置或由于寄存器溢出和恢復(fù)增加了基本塊中的指令 在基本塊內(nèi)，對(duì)已經(jīng)更改過(guò)的基本塊重新進(jìn)行指令調(diào)度,