研究生院第十章.ppt

第十章代碼生成,代碼生成器設計中的問題 目標機器 下次引用信息 一個簡單的代碼生成器 指令調度 寄存器優(yōu)化,代碼生成器的位置,各種代碼的形式 中間代碼: 后綴式，三地址代碼，語法樹 符號表中的項：名字，類型，嵌套深度，偏移量 目標代碼：絕對機器代碼，可再定位代碼，匯編 代碼生成器的輸出必須是正確和高質量的 產(chǎn)生最優(yōu)化代碼的問題是不可判定的,代碼生成器設計中的問題,代碼生成器 依賴于目標機器和操作系統(tǒng) 要充分發(fā)揮目標機器的能力：充分利用目標機器的資源 代碼生成器固有的問題 存儲管理 指令選擇 寄存器分配 計算次序選擇 可移植的代碼生成器 機器描述,代碼生成器的輸入,符號表信息 決定中間表示中名字所代表的數(shù)據(jù)對象的運行地址 偏移量 作用域 可能在動態(tài)時刻作為調試信息存在 中間表示 代碼生成的很多技術是可以用于不同的中間表示的 代碼生成前，中間表示記錄了足夠詳細的程序信息 名字的值可以表示為目標機器能夠直接操作的數(shù) 類型檢查已經(jīng)完成 明顯的語義錯誤已經(jīng)發(fā)現(xiàn),目標程序,代碼生成器的輸出：目標程序 絕對機器語言 可以放在內存中固定地方，并立即執(zhí)行 小程序、需要迅速編譯和執(zhí)行 可重定位的機器語言 程序可以分為多個目標模塊，分別編譯 需要連接裝配器將一組可重定位模塊一起裝入執(zhí)行 需要額外的開銷，但靈活：可分別編譯子程序和從目標模塊中調用其它先前編譯好的程序模塊 如果目標機器不能自動處理重定位，則編譯器必須提供顯式的重定位信息給裝配程序 匯編語言 代碼生成的過程容易：可以產(chǎn)生符號指令和利用匯編器的宏 避免了重復匯編器的工作,存儲管理,把程序中的名字映射到運行時的目標對象的地址是由前端和代碼生成器共同完成的 語言中過程的語義決定了運行時刻名字如何與存儲空間相聯(lián)系 對名字的引用通過符號表 記錄了名字在過程數(shù)據(jù)區(qū)的相對地址 所需要的存儲空間 運行時活動記錄的管理 運行時活動記錄的分配和釋放作為過程調用和返回序列的一部分 call（調用） return（返回） halt（暫停） action（動作），為其它語句占有位置,一個代碼生成器的輸入,其中，arr，i，j是過程s中定義的數(shù)據(jù)；buf和n是過程p定義的數(shù)據(jù),靜態(tài)分配管理,call調用語句用兩條目標機器指令實現(xiàn) MOV #here + 20 , callee. static-area GOTO callee. Code-area mov指令存放返回地址（#here + 20是一個字面常數(shù)，指向goto后的那條指令的地址） goto指令將控制轉移到被調用過程的目標代碼 過程的返回 過程的返回指令表明一個過程的結束 第一個過程沒有調用者，以halt指令結束 GOTO * callee. static-area 按照活動記錄中記錄的返回地址返回,靜態(tài)存儲管理：目標代碼的例子,/* s的代碼 */ 100:ACTION1; 120:MOV140 , 364/* 保存返回地址140 */ 132:GOTO200/* 調用p */ 140:ACTION2; 160:HALT /* p的代碼 */ 200:ACTION3; 220:GOTO * 364/* 返回到364單元里存放的地址 */ /* 300-363保留著s的活動記錄 */ 300:/* 返回地址 */ 304:/* s的局部數(shù)據(jù) */ /* 364-451保留著p的活動記錄 */ 364:/* 返回地址 */ 368:/* p的局部數(shù)據(jù) */,棧式分配管理,活動記錄的存儲單元采用相對地址 SP：指向棧頂活動記錄開始的指針 過程調用的處理 第一個過程的代碼通過將SP置為存儲器中棧區(qū)的開始位置來初始化棧： MOV#stackstart, SP/* 初始化棧 */ 第一個過程的代碼 HALT/* 終止過程運行 */ 過程調用序列給SP一個增量，并存儲返回地址及將控制轉移到被調用過程 ADD#caller, recordsize, SP/* 增加SP */ MOV#here + 16 , * SP/*存返回地址*/ GOTOcallee. code-area/*將控制轉移到被調用過程*/,棧式分配管理（續(xù)）,過程返回的處理 在被調用過程中 GOTO * 0 ( SP )/* 返回到調用過程 */ 在調用過程中，恢復SP SUB #caller. recordsize , 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/* 調用序列開始 */ 136:MOV152 , * SP/* 壓入返回地址 */ 144:GOTO300/* 調用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/* 調用p */ 344:SUB#qsize , SP 600:/* 棧的開始*/,棧式分配管理（續(xù)）,名字的運行地址 靜態(tài)存儲策略 staticoffset 動態(tài)存儲策略 局部名字 非局部名字 使用display表 這個指針在編譯時刻不能確定，因此要在動態(tài)時刻實現(xiàn)地址的最終確定 MOV#0 , 12(R3) R3是存放display表指針的寄存器,指令地址的決定,通過一個計數(shù)器決定每個指令的地址 標號的處理：j: goto i/*j是當前語句的號碼*/ 如果i小于j i出現(xiàn)在j之前，目標地址是i對應的三地址代碼的第一條指令地址 如果i大于j i出現(xiàn)在j之后，目標地址此時不可知，可以利用回填的技術解決,指令選擇,目標機器指令系統(tǒng)的性質決定了指令選擇的難易程度 指令系統(tǒng)的一致性和完整性是重要因素 如果目標機器不能以一致的方式支持各種數(shù)據(jù)類型，則每種例外都要專門的處理 指令的速度和機器的特點是另一些重要的因素 如果不考慮目標程序的效率，則指令選擇是直截了當?shù)?代碼的質量取決于它的執(zhí)行速度和長度 可以從多種指令中選擇合適的：a=a+1 MOVa , R0 ADD#1 , R0INCa MOVR0 , a 時間信息對代碼序列是重要的，但不是任何時候都精確的,指令選擇的例子,逐條語句地產(chǎn)生代碼的方法常常產(chǎn)生低質量的代碼 a := b + c d := a + e MOVb , R0 ADDc , R0 MOVR0 , a MOVa , R0 ADDe , R0 MOVR0 , d,寄存器分配,快速的寄存器 通常，利用寄存器放置運算對象的指令比運算對象在內存中的指令短些 執(zhí)行也快些 充分利用寄存器對高質量的代碼生成是重要的,寄存器 片內CACHE 片外CACHE 主存 外存,寄存器優(yōu)化 局部性優(yōu)化,寄存器分配（續(xù)）,寄存器使用的兩個子問題 寄存器分配：為程序的某一點選擇駐留在寄存器中的一組變量 寄存器指派：挑出變量將要駐留的具體寄存器 寄存器分配的最優(yōu)化是NP完全的 特定要求的滿足,計算次序選擇,計算執(zhí)行的次序會影響目標代碼的效率 選擇最佳次序是一個NP完全問題 ld r1 , t:無，非,無,非,3,活,活,3,u:3,活；a,c:無，活,無,非,2,2,活,活,a:2,活；b:無，活,無,非,1,1,活,活,t:3,活；,下次引用信息（4）,臨時名字的存儲分配 在需要臨時變量時申請一個新的名字是簡單有效的，但浪費空間 如果兩個臨時變量不是同時活躍的，則可以壓縮在同一單元中 臨時變量存儲單元的分配： 依次檢查臨時變量區(qū)域的單元，找到第一個不含活躍臨時變量的單元，指派給待分配的臨時變量 如果沒有合適的單元，則在活動記錄的臨時變量區(qū)域中增加一個單元,下次引用信息（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,一個簡單的代碼生成器（1）,這個代碼生成器的假設條件： 三地址語句的每種算符都有對應的目標機器算符 計算結果留在寄存器中盡可能長的時間。只有在以下兩種情況才把它存入主存 此寄存器要用于其它計算 正好在過程調用、轉移或標號語句之前 在基本塊的結尾，所有的寄存器都將保存，使得代碼生成算法簡單,一個簡單的代碼生成器（2）,后續(xù)的代碼盡可能引用變量在寄存器中的值，而不訪問主存，如對a := b + c 如果b在Ri中，c在Rj中，b在此語句后不活躍，則可以為它生成代價為1的代碼ADD Rj , Ri，結果a存在Ri中 如果b在Ri中，c在內存單元中，b仍然不再活躍，則有： ADD c , Ri 或： MOV c , Rj ADD Rj , Ri 如果c的值以后還要用，則第二種方式更好一些，因為可以直接從寄存器Rj中取得它的值 由于語義的復雜性，上述代碼生成可能要更為復雜,一個簡單的代碼生成器（3）,寄存器描述和地址描述 代碼生成算法使用寄存器和名字的描述來跟蹤寄存器的內容和名字的地址 寄存器描述記住每個寄存器當前存的是什么 在每個塊的開始，寄存器描述顯示所有寄存器為空（如果寄存器指派可以穿越塊的邊界，則此假設不成立） 塊的代碼生成過程中，每個寄存器保存零個或若干個名字的值 地址描述記住運行時每個名字的當前值可以在那個場所找到 這個場所可以是寄存器、棧單元、內存地址或它們的集合等 這些信息可以存于符號表中，在決定名字的訪問方式時使用,一個簡單的代碼生成器（4）,代碼生成算法 輸入：一個基本塊的三地址語句序列 輸出：指令序列 方法：對每個三地址語句x := y op z完成下列動作 1調用函數(shù)getreg決定存放y op z計算結果的場所L，L通常是寄存器，也可以是內存單元 2查看y的地址描述，確定y值當前的一個場所y。如果y值當前既在內存單元又在寄存器中，選擇寄存器作為y。如果y的值還不在L中，則產(chǎn)生指令MOV y , L 3產(chǎn)生指令op z , L，其中z是z的當前場所之一（同2一樣優(yōu)先選擇寄存器），修改x的地址描述，以表示x在場所L。如果L是寄存器，修改它的描述，以表示它含x的值 4如果y和（或）z的當前值不再引用，在塊的出口也不活躍，并且在寄存器中，則修改寄存器描述，以表示在執(zhí)行了x := y op z后，這些寄存器分別不再含y和（或）z的值,一個簡單的代碼生成器（5）,基本塊結束的處理 在基本塊的出口，用MOV指令把在寄存器中的活躍變量的值保存 值在寄存器中 這個值在出口活躍 復寫語句的處理：x := y y在寄存器中 改變寄存器和地址的描述，記住x的值出現(xiàn)在該寄存器中 如果y不再引用，且在塊的出口不活躍，該寄存器不再保存y的值 y的值僅在內存中 若記住x的值在y的內存單元中，但如果更新y的值復雜；可以用getreg找到一個存放y的寄存器，并記住該寄存器是存放x的場所 或產(chǎn)生指令MOV y , x，如果x在塊中不再引用，此法較好,一個簡單的代碼生成器（6）,函數(shù)getreg 返回保存語句x := y op z的x值的場所L 簡單的實現(xiàn)方法：基于下次引用信息 1如果名字y在寄存器中，此寄存器不含其它名字的值，并且y不活躍，且在執(zhí)行x := y op z后沒有下次引用，則返回y的這個寄存器作為L 21失敗時，如果有的話，返回一個空閑寄存器 32不成功時，如果x在塊中有下次引用，或op是必須使用寄存器的算符（如變址），則找一個已被占用的寄存器R 將R中的值根據(jù)存有的變量（可能不止一個）保存到內存單元中，并修改相關的地址描述 R的選擇要考慮spill的代價 4如果x在本塊中不再引用，或者找不到適當?shù)谋徽加眉拇嫫?，則選擇x的內存單元作為L,一個簡單的代碼生成器（7）,例子： 賦值語句d := ( a b ) + ( a c ) + ( a c )可以翻譯成下面的三地址代碼序列 t := a b ; u := a c ; v := t + u ; d := v + u d在出口活躍，產(chǎn)生的代碼序列： 語 句生成的代碼寄存器描述地址描述 寄存器空 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 R1 , R0 R0含vu在R1中 R1含uv在R0中 d := v + uADD R1 , R0 R0含dd在R0中 MOV R0 , dd在R0和內存中,一個簡單的代碼生成器（8）,例子的討論 上述代碼的代價為12 可以在第一個指令后增加MOV R0 , R1，從而將代價減少為11（刪去了MOV a , R1）,一個簡單的代碼生成器（9）,為其它類型的語句產(chǎn)生代碼 變址語句的處理，其中： 偏移為Si 活動記錄的指針在寄存器A 寄存器R是調用函數(shù)getreg時返回的寄存器 對于第一個賦值，如果a在塊中有下次引用，且寄存器R是可用的，則a留在寄存器R中 在第二個語句中，假定a靜態(tài)分配 語 句 i在寄存器Ri中 i在內存Mi中 i在棧中 代 碼 代價 代 碼 代價 代 碼 代價 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),一個簡單的代碼生成器（10）,指針語句的處理，其中： 偏移為Sp 活動記錄的指針在寄存器A 寄存器R是調用函數(shù)getreg時返回的寄存器 對于第一個賦值，如果a在塊中有下次引用，且寄存器R是可用的，則a留在寄存器R中 在第二個語句中，假定a靜態(tài)分配 語 句 p在寄存器Rp中 p在內存Mp中 p在棧中 代 碼 代價 代 碼 代價 代 碼 代價 a := * p MOV * Rp , a 2 MOV Mp , R 3 MOV Sp(A) , R 3 MOV * R , R MOV * R , R * p := a MOV a , * Rp 2 MOV Mp , R 4 MOV a , R 5 MOV a , * R MOV R , *Sp(A),一個簡單的代碼生成器（11）,條件語句：兩種實現(xiàn)方式，以if x y，則CMP x , y置條件碼為正等 條件轉移機器指令根據(jù)指定的條件（ , , =）是否滿足來決定是否轉移，如果用指令CJ<= z表示如果條件碼是負或零則轉到z，所以有 CMP x , y CJ< z,一個簡單的代碼生成器（12）,條件碼的描述的記錄 這個描述告訴我們上次設置條件碼的名字和比較的名字對 x := y + zMOV y , R0 if x < 0 goto zADD z , R0 MOV R0 , x CJ< z 根據(jù)條件碼描述可以知道，在ADD z , R0之后，條件碼是由x設置的,程序的依賴關系,依賴關系是什么？ 依賴關系表明了兩個語句（或操作、計算）之間在執(zhí)行順序上存在的限制 如果兩個語句（或操作、計算）間存在著依賴關系，則這兩個語句（或操作、計算）的執(zhí)行必須滿足依賴關系的要求 如果兩個語句（或操作、計算）間沒有依賴關系，則這兩個語句（或操作、計算）可以被并行執(zhí)行或調整執(zhí)行的順序。 依賴分析是分析語句（或操作、計算）間的依賴關系，從而確定它們是否可以并行執(zhí)行 依賴關系的分類 數(shù)據(jù)依賴關系 控制依賴關系 控制流分析的結果 計算的執(zhí)行與否取決于控制條件是否滿足,數(shù)據(jù)依賴關系的定義,定義：如果語句S在語句S之前執(zhí)行，且兩個語句訪問相同變量V,其中至少有一個語句是對V賦值，則我們說這兩個語句之間存在數(shù)據(jù)依賴關系，記為ss： 如果V在S中定義，在S中使用，稱為真依賴，或流依賴，記為s ts 如果V在S中使用，在S中定義，稱為反依賴，記為sas 如果V在S和S中定義，稱為輸出依賴，記為SoS 如果V在S和S中使用，稱為輸入依賴，記為SiS 例子 S1: A=1.0 S2: B=A+3.14159 S3: A=1/3*(C-D) (無對A,B,C,D賦值） S4: A=(B*3.8)/1.78,依賴圖,以語句為節(jié)點，依賴關系為邊，上例的依賴圖為：,面向指令調度的依賴圖,無環(huán)區(qū)域的依賴圖是一個有向無環(huán)圖G(V, E)， 其中節(jié)點表示操作，邊表示兩個操作的執(zhí)行時刻必須滿足的約束。 依賴邊的分類 流依賴、反依賴、輸出依賴 由訪問寄存器導致的依賴 vs 由訪問內存導致的依賴 投機依賴邊 邊上通常記有所需的延遲，這個延遲與操作及依賴邊的類型有關 偽依賴所需的延遲通常不大于1。 內存取數(shù)操作的延遲通常難于在編譯時刻確定。 延遲的具體值由機器模型提供。,依賴圖的構造,構造依賴圖通?？赏ㄟ^對基本塊內的所有操作的一次或多次遍歷完成，以構造流依賴邊為例，算法如下：,void Build_DAG_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; 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 count; ; dyn-array *p; If( n count ) (*log)+; return p-xn; else return 0; ,Y,N,依賴圖的例子,指令調度,在滿足依賴關系、資源約束及硬件施加的其它約束條件的前提下，重新排定指令執(zhí)行的順序，提高資源利用率，使多個操作能夠并行執(zhí)行，同時減少因相關引起的處理器停頓，以縮短程序的執(zhí)行時間。 NP完全問題 指令調度的復雜性來自于程序控制流和數(shù)據(jù)流的復雜性，以及硬件平臺的復雜性。 處理上述復雜性的方法： 限制指令調度的范圍，將流圖劃分為若干具有良好性質的、規(guī)?？煽氐膮^(qū)域。 將機器相關部分從指令調度中分離出來。,指令調度的一般步驟,構造區(qū)域 (Region) 構造區(qū)域上的依賴圖 根據(jù)依賴圖進行調度 代碼的修正 若有未調度的代碼，重復上述步驟。,指令調度,依據(jù)區(qū)域流圖的性質，可如下分類：,指令調度,Trace 調度,選擇調度,Superblock/Hyperblock,SEME區(qū)域調度,無環(huán)調度,核心識別,模調度,軟件流水,全局調度,局部調度,局部指令調度算法表調度,void Schedule_BB(BB* bb) Build dependence graph for bb; Compute ready candidates for current cycle; 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 model 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. ,就緒隊列,一般而言，在某一時刻的就緒操作應滿足下列條件： op在依賴圖上的所有依賴前驅均已調度過。 若op引用了某個操作op的結果，op于第i拍發(fā)出，且兩者之間的延遲為l，則op的發(fā)出時刻不得早于i+l。 若硬件有記分牌，則條件 2 可以去掉，這樣在調度過程中就緒隊列不會為空，但隊列中的操作地位不同。 給每個就緒操作加一個等待時間，每次調度總是選取等待時間最小的操作。 比較當前時刻與每個操作的最早開始時間。 就緒隊列在調度開始前計算一次，以后每調度一個操作，只需檢查其在依賴圖上的后繼。,操作的調度優(yōu)先序,決定調度操作的先后順序時使用的啟發(fā)式信息： 執(zhí)行頻率 關鍵路徑 投機性 所需補償代碼數(shù)量 依賴圖上的后繼個數(shù) 寄存器的使用情況 是否在調度過程中動態(tài)更新上述信息需在代碼質量與編譯時間之間作出折中。,A,B,C,D,E,F,G,E,NR,F,B,G,A,C,D a nested region as NR,全局的情形：構造區(qū)域,調度區(qū)域一般是無環(huán)的。依據(jù)流圖的結構，基本塊的執(zhí)行頻率，以及區(qū)域的預期大小等啟發(fā)式信息構造。,Trace 調度,Trace: 執(zhí)行過程中可能經(jīng)過的一個基本塊的線性序列 Trace 的選擇： 根據(jù)分支概率及是否需要插入補償代碼等啟發(fā)式規(guī)則選擇執(zhí)行路徑，代碼移動局限于該路徑 局部調度方法的延伸：以執(zhí)行頻率較低的路徑上代碼執(zhí)行時間的增加為代價，換取頻繁執(zhí)行的路徑上代碼執(zhí)行時間的縮減,Trace 調度：算法,步驟： 估算每個操作的執(zhí)行頻率 挑選Trace 使用某種局部指令調度方法如表調度對形成的Trace進行調度 用調度完的代碼替換流圖中原來的Trace，必要時在Trace之外插入相應的補償代碼 遍歷調度后的流圖并釋放代碼 Trace 調度的問題： 插入補償代碼的過程在實現(xiàn)上復雜，且可能產(chǎn)生冗余 在Trace 內作的一些優(yōu)化，如復寫傳播，死代碼刪除等，由于split和join節(jié)點的存在而受到限制 若分支概率相近，Trace 難于選擇。,Superblock 調度,A,B,C,F,E,D,A,B,C,F,E,D,F,Z,Z,Y,Y,尾復制,Hyperblock 調度,條件執(zhí)行 體系結構提供64個1位的謂詞寄存器(predicate registers) 帶有謂詞的指令僅當謂詞為真時改變機器狀態(tài)，否則相當于一條NOP指令 編譯器為分支兩側的指令分配不同的謂詞寄存器，由比較 (cmp) 指令在執(zhí)行時刻為謂詞賦值。 條件執(zhí)行可消除分支 將控制依賴轉化為數(shù)據(jù)依賴 減少由于分支預測錯誤帶來的開銷 有可能增加關鍵路徑長度,寄存器分配,決定程序中哪些變量的值應該存放在寄存器中。 減少訪存和復寫操作。 最重要的編譯優(yōu)化之一： 訪問寄存器和存儲器的代價相差在一個數(shù)量級以上。 寄存器的數(shù)目雖已大為增加，但仍是十分稀缺的資源。 許多優(yōu)化的效果依賴寄存器分配的結果。 寄存器分配與寄存器指派 寄存器分配：決定哪些變量該占用寄存器。 寄存器指派：決定變量該使用哪個寄存器。 Caller-Save與Callee-Save寄存器 傳遞參數(shù)與返回值的寄存器 葉過程與非葉過程,活躍區(qū)間與干涉,一個變量的活躍區(qū)間： 一個變量的（極小化）活躍區(qū)間是變量的定值與引用的一個子集，對于此集合中的任意定值dm和引用un，或者un在dm的du鏈上，或者存在一個由此集合中的定值與引用組成的交錯序列dm=d0、u0、d1、u1、dk、uk= un，其中的任何一個ui、同時在di和di+1的du鏈上。 直觀上，變量的活躍區(qū)間對應于流圖上聯(lián)結變量的定值點和引用點的一個連通區(qū)域。 干涉： 兩個變量的活躍區(qū)間干涉（簡稱兩個變量干涉），若在其中某個變量的定值處，另一個變量是定值到達和活躍的。,圖的著色與寄存器分配,當前占統(tǒng)治地位的寄存器分配方法是圖著色方法。 圖的k著色問題 寄存器分配歸結為圖著色問題： 首先構造干涉圖，圖中每個結點代表一個變量的活躍區(qū)間，如果兩個變量干涉，則在相應的結點vi和vj之間用邊eij連接。 假設目標機有k個寄存器可用，則寄存器分配的問題就變成對這個圖找一個k著色的方案。,x = . y = . = . x z = . = y = z,y,z,x,Requires Two Colors,y,z,x,干涉圖的例子,x,z,y,有控制流的情形,x,y,z,需要兩種顏色,圖著色寄存器分配Chaitins,判斷一個圖是否k可著色是一個NP完全問題。 注意到圖中度不大于k的節(jié)點總可以被著色，Chaitin提出了一種啟發(fā)式方法：持續(xù)地從圖中刪掉度小于k的節(jié)點，若此過程一直進行到所有的節(jié)點均被刪除，則圖是k可著色的。若此過程阻塞，即圖中所有節(jié)點的度均不小于k，則依據(jù)溢出代價大小，從圖中選擇某個節(jié)點，刪除該節(jié)點及其相連的邊。然后重復上述過程。,極小化活躍區(qū)間,Rename(CFG) for each (var) lrsvar = ; for each (d in dd_chain(var) lr = new_a_lr(du_chain(d); lrsvar += lr; endfor do for each (lr1 in lrsvar) for each (lr2 in lrsvar ,首先每個變量的每個du鏈都被初始化為一個活躍區(qū)間。 其次，若同一個變量的兩個du鏈包含公共的引用點，則將相應的兩個活躍區(qū)間合并成一個活躍區(qū)間。 疊代直到活躍區(qū)間的集合穩(wěn)定。,極小化活躍區(qū)間,活躍區(qū)間的極小化有利于減輕變量間的干涉，減小干涉圖的顏色數(shù)。,for ( i=0; i<n; i+ ) a = b + d; b = a + d; a = c + d; c = a + d; ,for ( i=0; i<n; i+ ) a1 = b + d; b = a1 + d; a2 = c + d; c = a2 + d; ,a,b,c,d,a1,b,c,d,a2,建干涉圖,Build_Interference_Graph_For_BB(block) live_var = var | var is live at the end of block ; for each statements S, from tail to the head of block live_var = 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; ,計算溢出代價,最小化被溢出變量的代價值的和 溢出代價： 分配的優(yōu)先序： 代價較大的變量的優(yōu)先級也較大 干涉圖上度較大的變量的優(yōu)先級較低,Cost(lr) = LOAD_COST x LoadTimes + STORE_COST x StoreTimes + MOVECOST x MoveTimes,Priority(lr) = Cost(lr) / Deg(lr),圖著色寄存器分配Priority-Based,Chow和Hennessy提出按活躍區(qū)間的優(yōu)先級從高到低的順序對圖進行著色 假定變量原本在內存中 全局與局部兩遍寄存器分配，GRA為LRA預留寄存器 粗粒度：以基本塊為分配單位 優(yōu)先級根據(jù)為變量分配寄存器能夠減少的訪存操作決定 一遍著色，沒有Chaitin式的先化簡后回溯 提出活躍區(qū)間分割（Live Range Splitting），即當著色過程阻塞時，把活躍區(qū)間分成若干較小的活躍區(qū)間。這樣可以產(chǎn)生較少的溢出,寄存器分配：有謂詞的情形,x,z,y,x,z,需要三個寄存器,y,(p2),(p1),(p2),(p1),謂詞分析,p0,p2,p1,x,y,z,P1與p2不可能同時為真,(p2),(p1),(p1),(p2),考慮謂詞的寄存器分配,x,z,y,根據(jù)謂詞分析的結果構造干涉圖,x,y,z,只需要兩個寄存器,(p2),(p1),(p1),(p2),指令調度和寄存器優(yōu)化的時序問題,先做寄存器分配，再作指令調度 先做寄存器分配的優(yōu)點在指令級并行度低、寄存器又少的處理機上得以體現(xiàn) 從指令調度的觀點看該順序的最主要問題是：寄存器分配會帶來反依賴和輸出依賴，這將在一定程度上影響指令調度的效果 先做指令調度，再作寄存器分配 雖然更好的指令調度是人們所期望的，但如果代碼需要的寄存器比能獲得的寄存器還要多的話，則這個事實是不能令人接受的 指令調度會增大寄存器分配的壓力，再好的指令調度所獲得的性能的提高也無法彌補由于較差的寄存器分配所帶來的損失,指令調度和寄存器優(yōu)化的時序問題的例子,1) Val3 <= val1 * 3假設乘法指令需要4拍 2) addr1 <= val3 3) Val4 <= val1 * 2 4) addr2 <= val4 若先做寄存器分配，再作指令調度 由于val3和val4此后不再被繼續(xù)引用，所以可以分在一個寄存器中 發(fā)射時間指令 0r3 <= r1 * 3 4store addr1 , r3 5r3 <= r1 * 2 9store addr2 , r3共需要10拍,指令調度和寄存器優(yōu)化的時序問題的例子,若先做指令調度，再作寄存器分配 此時，由于val3和val4活躍區(qū)間重疊，所以不可以分在一個寄存器中 發(fā)射時間指令 0r3 <= r1 * 3 1r4 <= r1 * 2 4store addr1 , r3 5store addr2 , r4共需要6拍 而且如果處理機能同時發(fā)射兩條定點乘法和兩條store指令的話，這一組指令可以在5拍完成,指令調度和寄存器優(yōu)化的時序問題（續(xù)）,協(xié)作式指令調度和寄存器分配 避免的分裂考慮上述兩個問題引起的缺乏通訊的問題 但算法過于復雜，難于實現(xiàn)，具有理論意義 一種實際的時序 先做指令調度（由于寄存器較多，所以可以忍受） 再作寄存器分配，但為了獲得較好的效果，可能會移動基本塊中的指令位置或由于寄存器溢出和恢復增加了基本塊中的指令 在基本塊內，對已經(jīng)更改過的基本塊重新進行指令調度,