<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • 程序分析與優化 - 8 寄存器分配

    本章是系列文章的第八章,用著色算法進行寄存器的分配過程。

    本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請注明出處。周榮華@燧原科技

    寄存器分配

    • 寄存器分配是為程序處理的值找到存儲位置的問題
    • 這些值可以存放到寄存器,也可以存放在內存中
    • 寄存器更快,但數量有限
    • 內存很多,但訪問速度慢
    • 好的寄存器分配算法盡量將使用更頻繁的變量保存的寄存器中

     

    8.1.1 寄存器分配的主要工作

    • 寄存器指派
    • 寄存器溢出處理
    • 寄存器使用合并

    8.1.2 寄存器的約束

    硬盤硬件或者編譯器的限制,某些值只能保存在特定的寄存器中

    虛擬寄存器(程序中的變量)和物理寄存器(實際的寄存器)

    calling convention(調用約定)

    同一個程序點alive的多個變量必須指派不同的寄存器

    8.1.3 寄存器分配與生命周期管理

    最小寄存器數量 ≥ 最大生命周期變量集合

    不過DCC888課程膠片里面給的這個例子,我不太認同:

     

     

    這樣分配下來雖然MaxLive是2個,但MinReg需要3個。

    為什么不能這樣分配?因為最后輸出是e和c,如果多個分支使用的e和c的寄存器不一樣,那到匯聚點的時候,就沒法直接用,還要做一次轉移,這個轉移也是需要額外的寄存器的,或者至少需要額外的計算。如果不做轉移,就要插入一條store和一條load指令,這個成本更高。

     

     

    8.1.4 寄存器分配是個NP完成問題

    它的復雜度和邏輯等同于圖的著色問題。

    同樣的,對于這樣的CFG,同樣匯聚點上輸出的變量往上的多個分支中,同一個變量需要使用同樣的寄存器:

     

     

    轉換成著色問題的邏輯變成這樣,對下面的k種顏色,需要k+1個寄存器:

     

     

    8.2 線性掃描

    線性掃描基于區間圖的貪婪著色算法:

    • 給定一個區間序列,重疊的區間必須給定不同的顏色,求最小顏色數。
    • 貪婪著色有最優算法
    • 但線性掃描不是貪婪著色的最優算法,而是最優算法的一個近似解。

    8.2.1 基本塊的線性化

    通常用逆后根排序對CFG做排序生成線性化的BB塊序列(前面worklist算法也用了逆后根排序,看來這個排序和程序執行之間的關系非常密切)。

     

     

    8.2.2 生成區間線

    變量v的區間線Iv從v的生命期開始的程序點開始,到v的生命期結束的程序點結束。

    為什么b和e的區間線要到第二個BB塊最后,而不是在最后一次使用后就結束?因為后面還有分支,根據條件不同,第二個BB塊還有可能從L6繼續執行。

     

     

    8.2.3 區間線的線性掃描算法

     

    算法描述如下

     1 LINEARSCANREGISTERALLOCATION?
     2   active = {}
     3   foreach interval i, in order of increasing start point
     4     EXPIREOLDINTERVALS(i)
     5     if length(active) = R then
     6       SPILLATINTERVAL(i)
     7     else
     8       register[i] = a register removed from the pool of free registers.
     9       Add i to active, sorted by increasing end point
    10  
    11 EXPIREOLDINTERVALS(i)
    12   foreach interval j in active, in order of increasing end point
    13     if endpoint[j] ≥ startpoint[i] then
    14       return
    15     remove j from active
    16     add register[j] to pool of free registers
    17  
    18 SPILLATINTERVAL(i)
    19   spill = last interval in active
    20   register[i] = register[spill]
    21   location[spill] = new stack location
    22   remove spill from active
    23   add i to active, sorted by increasing end point

     

     

    上面的例程經過算法處理之后的寄存器分配結果如下:

     

     

    8.2.4 合并

    上面的結果還不是最優解,需要經過合并

    帶合并過程的線性掃描算法如下:

     1 LINEARSCANREGISTERALLOCATIONWITHCOALESCING
     2   active = {}
     3   foreach interval i, in order of increasing start point
     4     EXPIREOLDINTERVALS(i)
     5     if length(active) = R then
     6       SPILLATINTERVAL(i)
     7     else
     8       if definition of i is "a = b" and register[b] ∈ free registers
     9         register[i] = register[i(b)]
    10         remove register[i(b)] from the list of free registers
    11       else
    12         register[i] = a register removed from the list of free registers
    13       add i to active, sorted by increasing end point

     

     

    合并之后的結果如下:

     

     

    8.2.5 生命周期黑洞

    線性掃描不是最優解,在一些場景下,和最優解相差還非差大,例如多個分支之間存在生命周期黑洞的情況。

    例如對下面的CFG:

     

     

    線性掃描處理的結果如下:

     

     

    按線性掃描的結果x和a是不能共寄存器的。但如果看生命周期分析結果:

     

     

    x出現后,a和b都不會再使用,也就是說x肯定是可以和a或者b共用一個寄存器的。

     

    8.3 基于圖著色的寄存器分配

    8.3.1 干涉圖(The Interference Graph)

    最常見的寄存器分配算法家族是基于干涉圖的理念推演出來的。

    干涉圖是基于控制流圖中變量的生命周期范圍的網絡圖:

    • 每個變量是圖的一個結點;
    • 如果兩個變量的生命周期存在重疊,則這2個節點在圖上鄰接,也就是存在一條邊將2個節點連接起來,這樣的邊也稱為干涉邊(interference edges)。
    • 除了干涉邊,如果2個變量存在且僅存在一條move指令將2個變量關聯起來,則在2個變量之間畫一條虛線,稱為合并邊(coalescing edges)

    8.3.2 肯普簡化算法(Kempe's Simplification)

    如果圖中存在一個節點m,它的鄰接節點小于k,設G' = G \ {m},如果G'能被k種顏色著色,那么G也能被k種顏色著色。

    通過肯普簡化算法,可以將圖簡化到只有一個節點,或者簡化到只剩下一些高階節點,這樣方便求出圖的最小可著色的顏色數。

    下面是簡化過程:

     

     

    8.3.3 貪婪著色算法(Greedy Coloring)

    貪婪著色的順序是肯普簡化算法刪除節點的順序的逆序,每次著色都要找一個鄰接節點中不存在的顏色進行著色。

    針對上面的簡化過程,著色過程是這樣的:

     

     

     

     

     

    注意,上面的算法只是為了證明一個圖是否能被K種顏色進行著色,但不關心是否可以用更少的顏色來著色。

    8.4 循環進行寄存器合并

     

     

    8.4.1 build

    就是基于生命周期生成干涉圖的過程:

     

     

    8.4.2 simplify

    使用肯普算法刪除非move相關節點:

     

     

    8.4.3 Coalesce

    合并過程是將move關聯節點合并成一個:

     

     

    保守合并算法:

    Briggs:節點a和b能合并當且僅當ab有更少的高階(≥k)鄰接節點

    George:節點a和b能合并,當且僅當,所有a的鄰接節點要么和b相互干涉,要么是一個低階節點

    8.4.4 freeze

    如果前面的的簡化和合并都沒有影響干涉圖,嘗試刪除一條move干涉關系。

     

     

    8.4.5 潛在溢出

    如果找不到低階節點,就要選擇一個節點作為潛在的溢出節點,并將它加入到簡化節點棧中。

    現在還沒有確定會溢出,有可能著色時,發現很多標記了溢出的節點,能夠有效著色。

    8.4.6 溢出算法(Spilling Heuristics)

    溢出算法的核心是找到一個溢出代價最小的節點,我們給循環內的節點一個更高的代價因子:

    1 SPILLCOST(v)
    2   cost = 0
    3   foreach definition at block B, or use at block B
    4     cost += 10^N/D, where
    5       N is B's loop nesting factor
    6       D is v's degree in the interference graph

     

     

    8.4.7 select

    將棧中的節點出棧,并嘗試用貪婪著色算法進行著色

     

     

    8.4.8 溢出

    如果確定需要溢出,在變量前后增加load和store指令,并重新走一遍從build開始的整個迭代過程。

    在只有3個寄存器的情況下,通過上面的計算,應該溢出c,將兩次c的使用改成c0和c1,重新進行計算:

     

     

     

     

     

    8.4.9 根據最終寄存器分配結果重寫程序

     

     

    8.4.10 刪除冗余的copy操作

     

     

    8.5 寄存器分配簡史

    1. Chaitin, G., Auslander, M., Chandra, A., Cocke, J., Hopkins, M., and Markstein, P. "Register allocation via coloring", Computer Languages, p 47-57 (1981),首次將圖著色引入寄存器分配 
    2. George, L., and Appel, A., "Iterated Register Coalescing", North Holland, TOPLAS, p 300-324 (1996),引入寄存器合并的迭代過程
    3. Poletto, M., and Sarkar, V., "Linear Scan Register Allocation", TOPLAS, p895-913 (1999),將線性掃描引入寄存器分配

     

    posted @ 2022-06-26 14:25  周榮華  閱讀(0)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看