周知cpu為方便亂序執行，內部會使用重命名寄存器技術消除數據依賴（war和waw）。編譯器在如下場景也會用到重命名
1. 靜態單賦值。過程內的每個變量唯一定義一次，原有相同的則會重命名，包括phi結點的定值
2. bb表調度。為消除反相關依賴即war，可以重命名讀操作使用或寫操作定義的值，這樣能調度產生總時鐘周期更少的指令序列，但可能增加寄存器壓力導致溢出而新增了長延遲操作（內存加載/存儲）并迫使另一輪調度
3. ebb表調度。對于某一ebb的一條路徑p，p存在過早退出路徑pe，p和pe的公共前綴是基本塊b，當調度p時，如果某個操作i向后移動到b，且i定義的值殺死了pe上的同名值，那么需要重命名i的定值。若i的定值被重命名，且其在p的出口處是活躍的，則調度器需要在出口處復制回原來的名字
4. trace表調度。蹤跡不同于ebb路徑，它允許中間存在多個前驅即入口的基本塊，而后者不能。當調度存在多入口的塊b的某蹤跡t時，t上的某操作i可能前向移動跨越b（t外的代碼路徑需作補償），若i殺死了一個活躍范圍跨越b的值，則需要重命名i的定值；同理，若i向后移動跨越b且殺死了t上的某值，則需重命名i的定值，這時t外的代碼路徑補償可以使用同一名字
posted @
2023-09-06 23:35 春秋十二月 閱讀(82) |
評論 (0) |
編輯 收藏1. 不可達代碼是指無論輸入什么都不會執行的代碼，對過程而言，即是從入口基本塊到不了（沒有路徑可達）的那些基本塊；死代碼是指可達但計算了后面任何可執行路徑都不會使用其計算結果的代碼，比如死變量和死指令
2. 不可達代碼的識別本質是有向圖的可達性判定與傳遞閉包計算問題，一般用DFS法處理。先找到從入口基本塊不可達的基本塊，再刪除（同時改變其前驅和后繼基本塊的指向），直到找不到為止。死代碼的識別可用活躍分析或必要指令標記法，對于活躍分析，刪除基本塊出口不活躍的變量定值，以及它所使用不活躍操作數的定值；對于標記法，從必要指令出發，根據def-use鏈和use-def鏈，不斷標記對其操作數有貢獻的指令，最后刪除沒被標記的那些指令
3. 不可達代碼和死代碼可能來源于程序員，更可能源于編譯器的其它一些優化產生，刪除優化它們能顯著減小代碼體積，對執行速度有間接的影響，因為可能改善指令高速緩層的利用率
posted @
2023-09-06 23:33 春秋十二月 閱讀(155) |
評論 (0) |
編輯 收藏1. 目的是識別循環中那種在每個迭代都產生相同值的計算，并將它們移到循環之外。注意，如果一個計算出現在嵌套循環內，對外循環的特定迭代而言，內循環的每個迭代都產生相同的值，但外循環的不同迭代產生不同的值，那么這種計算將移到內循環外，而非外循環外
2. 識別循環不變量可以基于數據流分析求得的use-def鏈，一條指令是循環不變的，當它的每個操作數滿足以下條件之一
a）該操作數是常數
b）該操作數的所有到達定值在循環之外。因為若有一個在循環內，則該指令就可能是循環變化的，除非那個定值是循環不變量
c）該操作數只存在一個為循環不變量的到達定值，且該指令之前沒有對其左部變量（若有）的使用。因為若有多個這樣的定值，則該指令就可能是循環變化的，除非多個定值結果都一樣；因為若前面有對其左部變量的使用，則該指令的賦值就殺死了左部變量的初值，這樣外提后左部變量第一次迭代就會使用錯誤的定值
3. 由于以上條件沒考慮到控制流分析，不能保證循環不變量在每個迭代中執行，以及循環不變量之左部變量的所有使用都是相同的值。因此為了保證外提后的代碼行為正確，還需要滿足條件：循環不變量所在基本塊必須是循環中所有使用了其左部變量的基本塊和所有出口基本塊的必經結點。當外提循環不變量后，考慮到循環有可能執行0次即一開始就不滿足循環進入條件，可以用是否進入循環的測試條件來保護前置塊，即識別終止條件是否一開始就為false，來保護它。這種方法總是安全的，但增加了代碼體積。不過若終止條件恒為true或false，則常數傳播分析會刪除這個冗余測試，如果為false，那么還會刪除前置塊
posted @
2023-09-06 23:30 春秋十二月 閱讀(84) |
評論 (0) |
編輯 收藏葉調用優化與收縮包裝
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 春秋十二月 閱讀(82) |
評論 (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 春秋十二月 閱讀(106) |
評論 (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 春秋十二月 閱讀(76) |
評論 (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 春秋十二月 閱讀(157) |
評論 (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 春秋十二月 閱讀(96) |
評論 (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 春秋十二月 閱讀(138) |
評論 (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 春秋十二月 閱讀(94) |
評論 (0) |
編輯 收藏