程式分析與優化 - 8 寄存器分配

来源:https://www.cnblogs.com/zhouronghua/archive/2022/06/26/16413471.html
-Advertisement-
Play Games

本章是系列文章的第八章,用著色演算法進行寄存器的分配過程。 本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技 寄存器分配 寄存器分配是為程式處理的值找到存儲位置的問題 這些值可以存放到寄存器,也可以存放在記憶體中 寄存器更快,但數量有限 記憶體很多,但 ...


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

本文中的所有內容來自學習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),將線性掃描引入寄存器分配

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 效果圖先附上: 首先 這是我是參考 教程:使用 SignalR 2 和 MVC 5 實時聊天 | Microsoft Docs 先附上教程: 在“添加新項 - SignalRChat”中,選擇 InstalledVisual> C#>WebSignalR>,然後選擇 SignalR Hub 類 (v ...
  • 這次iNeuOS升級主要升級圖形渲染引擎和增加豐富的圖元信息,可以很快的方案應用。總共增加41個通用和行業領域的圖元應用,增加2154個圖元信息,現在iNeuOS視圖建模功能模塊總共包括5894個行業圖元信息。現在完全支持製作高保真的工藝流程和大屏展示效果。 ...
  • 什麼是工廠模式 工廠模式是最常用的設計模式之一,屬於創建型模式。 有點: 解耦,可以把對象的創建和過程分開 減少代碼量,易於維護 什麼時候用? 當一個抽象類有多個實現的時候,需要多次實例化的時候,就要考慮使用工廠模式。 比如:登錄的抽象類ILoginBusiness,它有2個實現,一個用用戶名密碼登 ...
  • 遠程連接ubuntu 提前準備: 在Ubuntu中安裝好ssh 安裝步驟:1.安裝openssh-server 😒udo apt-get install openssh-server ​ (過程中會確認是否希望繼續執行,按y就可) ​ 2.查看是否安裝成功:ps -e |grep ssh ​ 3. ...
  • 1 學習參考 MySQL官方文檔 https://dev.mysql.com/doc/refman/8.0/en/delete.html 節選自 MySQL 8.0 Reference Manual_SQL Statements_Data Manipulation Statements_DELETE ...
  • 第一章 緒論 1.1 資料庫系統概述 1.1.1 資料庫的4個基本概念 數據:描述事物的符號記錄,數據的含義稱為數據的語義,二者是不可分的。 資料庫:資料庫是長期存儲在電腦內、有組織的、可共用的大量數據的集合。 資料庫數據基本特點:永久存儲、有組織、可共用。 資料庫管理系統(DBMS):是電腦的 ...
  • SpringBoot使用Redis教程 應用環境: 存放Token、.... 第一步: 添加Redis依賴 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-re ...
  • 📄前言 這個小項目源於github項目:✨50 projects 50 days, 這個項目包含了50個小型前端項目,適合學習了Html+Css+JavaScript但是還沒有學習框架的前端新手作為練習。 這裡是原項目的代碼實現👉擴展卡片 Expanding Cards 📝分析 📍佈局 卡片 ...
一周排行
    -Advertisement-
    Play Games
  • 一:背景 準備開個系列來聊一下 PerfView 這款工具,熟悉我的朋友都知道我喜歡用 WinDbg,這東西雖然很牛,但也不是萬能的,也有一些場景他解決不了或者很難解決,這時候藉助一些其他的工具來輔助,是一個很不錯的主意。 很多朋友喜歡在項目中以記錄日誌的方式來監控項目的流轉情況,其實 CoreCL ...
  • 本來閑來無事,準備看看Dapper擴展的源碼學習學習其中的編程思想,同時整理一下自己代碼的單元測試,為以後的進一步改進打下基礎。 突然就發現問題了,源碼也不看了,開始改代碼,改了好久。 測試Dapper.LiteSql數據批量插入的時候,耗時20秒,感覺不正常,於是我測試了非Dapper版的Lite ...
  • 需求如下,在DEV框架項目中,需要在表格中增加一列顯示圖片,並且能編輯該列圖片,然後進行保存等操作,最終效果如下 這裡使用的是PictureEdit控制項來實現,打開DEV GridControl設計器,在ColumnEdit選擇PictureEdit: 綁定圖片代碼如下: DataTable dtO ...
  • 前兩天微軟偷偷更新了Visual Studio 2022 正式版版本 17.3 發佈,發佈摘要: MAUI 工作負荷 GA 生成 MAUI/Blazor CSS 熱重載支持 現在,你將能夠使用我們的新增功能在 Visual Studio 中使用每個更新試用一系列新功能。 選擇每個功能以瞭解有關特定功 ...
  • 航天和軍工領域的數字化轉型和建設正在積極推進,在與航天二院、航天三院、航天六院、航天九院、無線電廠、兵工廠等單位交流的過程中,用戶更聚焦試驗和生產過程中的痛點,迫切需要解決軟體平臺統一監測和控制設備及軟體與設備協同的問題。 ...
  • .NET 項目預設情況下 日誌是使用的 ILogger 介面,預設提供一下四種日誌記錄程式: 控制台 調試 EventSource EventLog 這四種記錄程式都是預設包含在 .NET 運行時庫中。關於這四種記錄程式的詳細介紹可以直接查看微軟的官方文檔 https://docs.microsof ...
  • 一:背景 上一篇我們聊到瞭如何去找 熱點函數,這一篇我們來看下當你的程式出現了 非托管記憶體泄漏 時如何去尋找可疑的代碼源頭,其實思路很簡單,就是在 HeapAlloc 或者 VirtualAlloc 時做 Hook 攔截,記錄它的調用棧以及分配的記憶體量, PerfView 會將這個 分配量 做成一個 ...
  • 背景 在 CI/CD 流程當中,測試是 CI 中很重要的部分。跟開發人員關係最大的就是單元測試,單元測試編寫完成之後,我們可以使用 IDE 或者 dot cover 等工具獲得單元測試對於業務代碼的覆蓋率。不過我們需要一個獨立的 CLI 工具,這樣我們才能夠在 Jenkins 的 CI 流程集成。 ...
  • 一、應用場景 大家在使用Mybatis進行開發的時候,經常會遇到一種情況:按照月份month將數據放在不同的表裡面,查詢數據的時候需要跟不同的月份month去查詢不同的表。 但是我們都知道,Mybatis是ORM持久層框架,即:實體關係映射,實體Object與資料庫表之間是存在一一對應的映射關係。比 ...
  • 我國目前並未出台專門針對網路爬蟲技術的法律規範,但在司法實踐中,相關判決已屢見不鮮,K 哥特設了“K哥爬蟲普法”專欄,本欄目通過對真實案例的分析,旨在提高廣大爬蟲工程師的法律意識,知曉如何合法合規利用爬蟲技術,警鐘長鳴,做一個守法、護法、有原則的技術人員。 案情介紹 深圳市快鴿互聯網科技有限公司 2 ...