葉調用優化與收縮包裝
1. 葉調用優化適用于被調者是不調用任何過程的過程之場景，這種過程叫葉過程
2. 有幾種可能的優化
a）如果過程的實現使用display數組來尋址非局部變量，那么葉過程可避免在起始代碼序列中更新display數組
b）如果葉過程內不使用由被調者保存的寄存器（寄存器分配器應設法優先使用由調用者保存的寄存器），那么可避免起始代碼序列中保存代碼和收尾代碼序列中恢復代碼。很小的葉過程很可能不使用到被調者保存的寄存器，只使用部分調用者保存的寄存器的葉過程，那么調用者也可以避免一部分寄存器保存與恢復代碼
c）如果調用者有很多次調用葉過程，而且兩者代碼同時可見，那么葉過程不必自己分配棧幀，由調用者一次性分配好
3. 收縮包裝是葉調用優化的一種推廣，目的是盡可能去掉過程起始代碼序列和收尾代碼序列中實際沒用的寄存器保存恢復代碼。可以先用數據流分析來計算每個基本塊的保存寄存器集合（基本塊入口可預見但其前驅不可預見且入口不可達的那些寄存器）與恢復寄存器集合（基本塊出口可達但其后繼不可達且出口不可預見的那些寄存器），再在保存寄存器集合非空的基本塊入口處插入save指令（插入點已是最早的合適的位置），恢復寄存器集合非空的基本塊出口處插入restore指令（插入點已是最晚的合適的位置）
尾調用優化與尾遞歸刪除
1. 尾調用優化的條件是兩個（不同）過程編譯時同時可見，比如處于同一編譯單元，或調用者有足夠多的、使得優化可能發生的關于被調用者的信息
2. 尾調用優化的實現，因為被調者返回后代碼序列到調用者收尾代碼序列之間不存在有用計算，所以原來標準鏈接處理要保存的那些寄存器不可能活躍，首先要裁剪調用前代碼序列即不保存由調用者保存的寄存器和不壓棧返回地址，以及裁剪被調過程的起始代碼序列即不保存由被調者保存的寄存器和不分配新棧幀（借用調用者的棧幀，若被調者的棧幀比調用者的大，則需按兩者之差擴展棧幀），然后轉移到被調者裁剪過的起始代碼序列，最后修改被調過程的收尾代碼序列：正確釋放棧幀，比如用幀指針賦給棧指針，使之直接返回到調用者的調用者（比如o調用p，p調用q，q是尾調用，那么優化后q實際返回到o）。綜上可得，尾調用優化減免了壓棧返回地址與保存寄存器的開銷
3. 尾遞歸刪除是尾調用優化的一種特例，由于調用者和被調者是同一過程，因此不存在擴展棧幀和額外釋放棧幀，只須改變參數及跳轉到過程入口處即可
posted @
2023-09-06 23:23 春秋十二月 閱讀(64) |
評論 (0) |
編輯 收藏1. 數學基礎：兩者的共同點是都基于數據流值的半格和對組合運算封閉的傳遞函數，不同點是區域分析算法還要求傳遞函數是一個半格，不僅支持組合運算，而且支持交匯運算和閉包運算，交匯運算用于把有相同后繼的不同執行路徑組合起來，閉包運算用于環上（比如循環）執行零到多次的效果
2. 流程：迭代算法由初始化和循環求不動解組成，以前向數據流為例，其中初始化包括初始化入口基本塊的out集合為合適值，其它基本塊的out集合為半格的頂元素；循環求不動解遍歷除入口外（因為入口的out不會變）的每個基本塊，計算其out集合，直至所有基本塊的out不再改變。區域分析算法由計算層次區域序列、構造區域傳遞函數和計算各區域入口值組成，計算層次區域序列自底向上，基本塊為葉子區域，自然循環分為循環體區域和循環區域，都是內部區域，不是自然循環的整個流圖為根區域；區域傳遞函數有2個，一是R區域入口到其直接子區域S的入口的數據流值傳遞，記作Fin(R,S)，另一是R區域入口到其直接子區域出口基本塊B（可能有多個）出口處的數據流值傳遞，記作Fout(R,B)，區域傳遞函數的計算自底向上，對于葉子區域，Fin是恒等函數，Fout和迭代算法的傳遞函數一樣，取決于具體數據流問題；對于更大的區域（非葉子區域），遍歷每個子區域，Fin由所有Fout(R,B)交匯而成，B為S在R中的前驅，若R為循環區域，則再求Fout的閉包，遍歷S的每個出口基本塊B，Fout由Fout(S,B)和Fin(R,S)組合而成。計算各區域入口值自頂向下，根區域的In值等于流圖入口的In值，其它區域S的In值等于Fin(R,S)，R為父區域，所有Fin在前一環節已構造好
3. 結果：對同一數據流問題比如到達定值，兩種算法求得的數據流值是一樣的。為什么區域分析算法是正確的？因為它實際是按照程序控制流來構造傳遞函數的，包含了所有可能執行路徑數據流值傳遞的效果，這相當于迭代算法求不動解的過程，所以最后只要一個流圖的入口值，就能算出各區域的入口值。為什么迭代算法是收斂的？因為半格是單調的且高度有窮。收斂速度取決于遍歷基本塊的順序，如果按基本塊深度優先排序（逆后序）遍歷，那么迭代輪數不超過流圖的深度（各條無環路徑后退邊的最大數）加2
4. 區別：迭代算法用于可歸約流圖和不可歸約流圖，區域分析算法僅能用于可歸約流圖
posted @
2023-09-06 23:18 春秋十二月 閱讀(80) |
評論 (0) |
編輯 收藏1. 作為指令高速緩層優化的一種重要技術，它根據CFG流圖邊的執行頻率將頻繁執行的基本塊排列在一起，并布局那些基本塊在下降分支路徑，而不在一起的也就是很少執行的基本塊布局在轉移分支路徑。這樣做一來可以使取到I-cache中的指令實際被執行的比例較高，二來對于某些體系結構上轉移和下降路徑延遲不等的分支指令，可以降低跳轉延遲
2. 實現過程內代碼置放有以下幾個環節：
a）獲取剖析數據：編譯器可以先在基本塊出口處插入代碼以統計到其后繼基本塊的執行次數，作為CFG流圖邊的權重，然后編譯生成可執行文件，輸入代表性數據運行它，結果輸出一個數據文件，用于第二次編譯，這次編譯實施過程內代碼置放優化
b）以鏈的形式構建熱路徑：熱路徑是CFG路徑的一個集合，其中包括頻繁執行的那些邊，每條路徑是一個或多個基本塊按邊的方向構成的鏈，每個鏈關聯一個優先級，用于布局代碼的先后順序。初始時，每個基本塊構成一個只有它本身的鏈，其優先級為CFG流圖邊的數量或者更大值；接下來，在CFG中按權重降序遍歷每條邊<x,y>（x不等于y），若x是某個鏈a的尾結點且y是某鏈b的頭結點，則把b合并到a后面，更新a的優先級為a原來優先級、b優先級、P三者的最小值，同時遞增P，其中P為鏈合并操作的計數器，用于決定鏈的相對次序由低到高排列，初值為0。當遍歷結束時，所有熱路徑構建完成
c）進行代碼布局：經過前一環節，就得到了鏈的集合。首先從鏈集合找出含有入口基本塊的鏈t，將t加入工作表WL；然后從WL移出一個優先級最低的鏈c，按序（構建鏈時加入基本塊的順序）遍歷c的每個基本塊x，把x放在過程可執行代碼體的末端，對于邊<x,y>，將包含y的鏈t加入WL（若t不在WL中），重復該過程直至WL為空
posted @
2023-09-06 23:15 春秋十二月 閱讀(56) |
評論 (0) |
編輯 收藏【輸入輸出】
一個過程的所有基本塊，除entry和exit外的每個基本塊包含指令序列
【流程】
由前向數據流分析、局部復寫傳播和遍歷基本塊構成
1. 前向數據流分析：目標是計算出每個基本塊入口處有效的復寫賦值集合，這里定義為CPin(i)，i為基本塊，其元素為表示復寫賦值的四元組<u,v,blk,pos>，u為左變量，v為右變量，blk為基本塊，pos為在blk中的位置。另外定義COPY(i)為基本塊i中出現且到達了出口的那些復寫賦值集合，即u和v在i中pos后沒被賦值；KILL(i)為被基本塊i殺死的那些賦值集合，即i中存在對其它基本塊復寫賦值右變量的賦值；CPout(i)為基本塊i出口處有效的復寫賦值集合。以上四種集合的數據流方程為：CPin(i)等于i的每個前驅p的CPout的交集，CPout(i)等于COPY(i)與CPin(i)減去KILL(i)之差的并集。CPout(entry)初值為空集，其它基本塊的CPout初值為全集U，U為過程所有復寫賦值的集合即所有基本塊的COPY之并集，根據迭代求不動點法可算出每個基本塊最終的CPin值
2. 局部復寫傳播：作為被全局復寫傳播調用的例程，有兩個參數，一個為輸入輸出參數單個基本塊，另一個為輸入參數CPin，即前向數據流分析求得的結果。該例程內部維護一個有效復寫賦值的表，稱作ACP，其元素為二元組<u,v>，u是復寫賦值的左變量，v是右變量。首先初始化ACP即將CPin中的復寫賦值加入到ACP，再遍歷基本塊的每條指令，針對指令類別做對應的處理，有以下幾種情況
a）對于一元/二元表達式及過程調用，將表達式的操作數或調用參數替換為ACP中對應元組的第二分量，若不存在這樣的元組則不用替換
b）對于賦值語句（包括復寫賦值），從ACP中刪除第一或第二分量為賦值語句左變量的元組，這是為了刪除被殺死的復寫賦值
c）對于復寫賦值且左變量u不等于右變量v，將元組<u,v>加入到ACP
當遍歷結束后，局部復寫傳播就完成了
3. 遍歷基本塊：對每個基本塊調用局部復寫傳播，當遍歷結束后，全局復寫傳播就完成了
【分析】
數據流分析的復雜度取決于基本塊總數及指令總數，局部復寫傳播的復雜度取決于基本塊的指令總數，遍歷基本塊復雜度取決于基本塊數量。全局復寫傳播會造成無用的賦值指令，但是這正給死代碼刪除和強度削減（比如兩個相同的整型變量加法用移位代替）提供了機會
posted @
2023-09-06 23:13 春秋十二月 閱讀(128) |
評論 (0) |
編輯 收藏【輸入】
ssa控制流圖。結點為一個phi函數或一條運算指令，邊包含控制流邊和ssa邊
【輸出】
所有ssa變量的最終LatCell（常量半格值）
【流程】
1. 算法維護兩個工作表，一是流圖邊FlowWL，用于跟蹤控制流的執行，二是ssa邊SSAWL，用于單賦值變量的傳播。還有一個ExecFlag映射，用于確保僅有控制流邊導向的運算結點最多執行一次，多次執行是沒必要的，因為運算涉及的分量不會變（沒有ssa前驅邊），ExecFlag(a,b)為true表示邊a->b導向的結點b已執行，否則未執行
2. 兩種結點的分析：
a) 對于phi結點，不管被哪種邊導向，都先計算其LatCell（phi結果與各個phi參數的交），若與舊值不同，則將它的ssa后繼邊加入SSAWL，若控制流后繼邊尚未執行即對應ExecFlag為false，則將它的控制流后繼邊加入FlowWL
b) 對于運算結點，若是控制流邊導向且未被執行過（到結點的所有邊的ExecFlag為false）或ssa邊導向且以前執行過（存在至少一條邊的ExecFlag為true），則執行其運算，計算左值變量的LatCell（解釋執行整數運算），若與舊值不同，則將ssa后繼邊加入SSAWL，若LatCell是常量且為條件運算，則將滿足條件的Y或N邊加入FlowWL，否則將所有控制流后繼邊加入FlowWL
3. 算法初始時，設置所有控制流邊的ExecFlag為false，設置所有ssa變量的LatCell為未知（半格頂元素），將流圖入口到第1個結點的邊加入FlowWL。然后進行主循環，先從FlowWL移出一條邊，若邊的ExecFlag為false則設為true，判斷尾結點類型，若為phi則轉到上述2-a處理，若為運算則轉到2-b處理；再從SSAWL移出一條邊，若邊尾結點為phi類型則轉到2-a處理，否則為運算類型轉到2-b處理，以上過程直至FlowWL和SSAWL皆為空
【分析】
該算法思想是符號執行，對于運算x=y或x=y+z（這里+泛指對整型有意義的操作），在常量半格中，x、y、z初值為未知，y和z單調降低，導致x也單調降低，它們最多降低2次，故當格值不變后，SSAWL終為空，另外由于ExecFlag的作用導致所有僅控制流邊導向的結點最多執行一次，因此FlowWL終為空，算法是收斂的，復雜度取決于控制流邊和ssa邊的總數
posted @
2023-09-06 23:10 春秋十二月 閱讀(72) |
評論 (0) |
編輯 收藏【輸入】
程序控制流圖CFG
【輸出】
帶區域結點的控制依賴圖CDG
【流程】
1. 為CFG添加一個虛構謂詞結點start，它的Y邊指向入口結點entry，出邊指向出口結點exit，得到CFG+。添加start是因為entry到第1個基本塊沒有條件判斷
2. 為CFG+構建后必經結點樹PDOMTree，將CFG+中所有n不是m的后必經結點的邊m->n加入集合S，邊的標號來自CFG為Y或N
3. 遍歷S，對每條邊m->n，先在PDOMTree中找到最低公共祖先p（如果m為根結點則為m，否則為m的父結點），再將PDOMTree中p到n路徑上每個結點（p和entry除外）x加入CDG，并添加邊m->x，其邊標號同m->n
4. 對CDG的每個內部結點，若存在Y邊，則新建一個區域結點，連接所有Y邊對應的子結點；若存在N結點，則新建一個區域結點，連接所有N邊對應的子結點
【應用】
對于控制依賴于同一結點的所有結點，只要它們之間沒有數據依賴關系，就可以并行執行
posted @
2023-09-06 23:07 春秋十二月 閱讀(109) |
評論 (0) |
編輯 收藏【輸入】
根過程，及每個過程（含根過程）的指令序列
【輸出】
調用圖，由過程點集和調用邊（形如<p,i,q>，p在位置i調用q）集構成
【全局結構】
PVVs：過程值變量集合
PVVals：過程值變量到過程常數集合的映射
PVBinds：過程值變量到過程值變量集合的映射
PVCalls：調用邊的集合
【流程核心】
1. 分析過程p內指令，要處理調用指令和賦值指令兩種類型。對于調用指令，若被調過程q是過程常數，則將q和<p,i,q>加入調用圖，先解析q的過程值形參與傳入實參的關系，有4種情況
a）過程常數cp傳入過程值形參fp，將偶對<fp,cp>加入PVVals，fp加入PVVs
b）過程值變量vp傳入過程值形參fp，將<fp,vp>加入PVBinds，fp和vp加入PVVs
c）過程值形參fp傳出過程值變量vp，將<vp,fp>加入PVBinds，vp和fp加入PVVs
d）過程值形參fp傳出過程常數cp，將<fp,cp>加入PVVals，fp加入PVVs
若q不是常數而是過程值變量，則將q加入PVVs，<p,i,q>加入PVCalls。再解析q的返回與p的關系，有2種情況
e）返回一個過程值變量vp1賦給另一過程值變量vp2，將<vp2,vp1>加入PVBinds，vp2和vp1加入PVVs
f）返回一個過程常數cp賦給一個過程值變量vp，將<vp,cp>加入PVVals，vp加入PVVs
對于賦值指令，其實情況和上述返回賦值一樣
----------------------------------------------------------------
2. 遍歷PVVs，傳播各過程值變量的PVBinds，直至不再改變（迭代求不動解），本質是計算過程值變量的傳遞閉包
3. 遍歷PVCalls，對每個<p,i,q>，先遍歷它的每個PVVals u，將u和<p,i,u>加入調用圖；再遍歷它的每個PVBinds u及u的每個PVVals v，將v和<p,i,v>加入調用圖
----------------------------------------------------------------
以上三環節可使用工作表w來驅動，w初始只有根過程，不斷從w移出一個過程p、分析p，每當在環節1或環節3發現一個新過程（過程常數）就加入w，直至w為空，這時所有過程都已分析，調用圖構建完成
posted @
2023-09-06 23:04 春秋十二月 閱讀(76) |
評論 (0) |
編輯 收藏【輸入】
調用圖，其頂端是根過程
【輸出】
每個過程每個參數的icp值
【算法步驟】
1. 將根過程加入工作表，遍歷調用圖，構建每個過程的形參集合，初始化每個形參的icp值為未知（icp格的頂元素）
2. 從工作表移出一個過程p，若工作表為空則終止
3. 遍歷p的指令序列，對每個調用點遍歷被調過程q的形參，對每個形參x，若對應的傳入實參是p的一個形參，則計算x的icp值（等于x舊值和傳入實參的icp值之交）
4. 若x的icp值比舊值小，則將q加入工作表，轉到步驟2繼續
【算法分析】
數學基礎是icp半格，高度為3，所以必定收斂（因為半格是單調偏序的，icp最多變小2次：未知->常量，常量->非常量）。步驟1復雜度取決于過程數及其參數數量，步驟2～4之外循環次數取決于調用圖的深度，內循環取決于調用點數、被調過程的參數數量。該算法是位置無關的，不能處理特定調用點的特定過程之常量傳播，另外過程的形參集合不能有交集
【應用】
可以計算出每個過程入口形參對應的常量實參集合，進而可以運用全局常數傳播使結果更精確。如果確定了一個過程的哪些參數是常量，那么可以克隆出一個副本，對副本進行優化，比如裁剪調用和起始代碼序列，使之不傳遞常數參數，再運用過程內優化
posted @
2023-09-06 23:02 春秋十二月 閱讀(53) |
評論 (0) |
編輯 收藏【輸入】控制流圖<N, E> G，回邊m—>n
【輸出】循環子圖<N, E> loop
【流程】
1. 將m、n加入loop的結點集合，及m—>n加入loop的邊集合，若m不等于n即不為自環，則加入m到queue（先進先出隊列）
2. 若queue非空，則其從頭出隊得結點q；否則結束
3. 在G中遍歷q的每一個前驅結點p，將p加入queue尾，若p不在loop結點集合中，則加入到loop結點集合，及邊p—>q加入loop的邊集合。轉到步驟2繼續
【分析】
正確性：檢驗最終loop中的結點集合是否滿足自然循環的定義，注意到輸入指定了回邊，這說明n是m的支配結點，當為自環時只有一個結點而滿足支配自反性，當不為自環時，加入的結點是m的所有直接與間接前驅，所以n也是它們的支配結點（假設不是，則必有m的一個前驅p，從入口結點經過p到m但不經過n，這與n是m的支配結點矛盾），且回邊已在第1步加入loop，故滿足了自然循環的定義。由于m在loop中的前驅數量是有限的，因此算法必然終止
復雜度：第3步判斷p是否在loop結點集合中，取決于圖的具體結構，設n為循環子圖的結點數，若是鄰接矩陣，則只需O(1)時間檢測邊是否存在，因此總耗時為O(n)。若為鄰接表，檢測邊是否存在與結點數成正比，則總耗時為O(n^2)
其它算法：從m開始，標記n為visited，在G的反向流圖中深度優先搜索，將訪問到的結點及邊加入loop，遇到n就回溯
posted @
2023-09-06 22:59 春秋十二月 閱讀(48) |
評論 (0) |
編輯 收藏【命題1】控制流圖G中若a dom n，且b dom n，則a dom b 或b dom a
【證明】設G入口為s，假設結論不成立，即a 不dom b且b 不dom a，或a dom b且b dom a。根據支配結點定義，如果是前者，則從s有全部路徑經a（或b）到n但不經過b（或a），這與題設b（或a）dom n矛盾；如果是后者，則從s有全部路徑經a，然后經b，再經a，構成了無限循環a->b->a->•••，永遠到不了n，這也與題設矛盾。故結論成立
【命題2】控制流圖G中若m idom n，則m是唯一的，若d ≠ n 且d dom n ，則d dom m
【證明】設G入口為s，假設不唯一，G中有另一個結點m'且m' idom n，根據支配結點定義，從s經m到n的路徑上必有m' dom m，從s經m'到n的路徑上必有m dom m'，根據支配關系的反對稱性，有m'=m，故唯一。假設d 不dom m，則從s到m的路徑上不必然經過d，又m是n的唯一直接支配結點，則從s到n的路徑上不必然經過d，即d 不dom n，這與題設矛盾，故d dom m。可以看到用反證法證明后一個結論時，直接支配結點的唯一性很關鍵
posted @
2023-09-06 22:57 春秋十二月 閱讀(445) |
評論 (0) |
編輯 收藏