作者mshockwave (夏克維夫)
看板C_and_CPP
標題Re: [問題] llvm 有API可以求得PDF嗎？
時間Tue Dec 25 20:52:35 2018
非常感動有人研究 LLVM 的原始碼
但有點可惜的事 DominanceFrontier 目前已經(建議) deprecated 了：
https://goo.gl/7Ag9je
原因我不太清楚 但有一個類似的替代選項：IteratedDominanceFrontier
include/include/llvm/Analysis/IteratedDominaceFrontier.h 裡面的
class Forward/ReverseIDFCalculator
iterated dominance frontier(IDF) 跟 dominance frontier(DF) 有些不一樣
根據 DF 的定義，每個 DF block 也是可能需要插入 Phi node 的 block
而 Phi node 基本上也是一個 definition，所以也可以找到他的 DF block
IDF 就是基於這個概念，延伸 DF 的演算法：在找到一個 DF block 後
會以該 block 為起點 繼續找該 block 的 DF
以這個例子來看：
https://i.imgur.com/oTyD5OM.png
以下是 definition BB 以及 IDFCalculator 計算出的對應結果
| Definition Block | IDF(s) |
--------------------------------
| %3 | %11 |
| %4 | %11 |
| %6 |
%10,%11 |
| %8 |
%10,%11 |
會發現 %3 和 %4 都跟教科書上對於 DF 的定義相符
但 %6 和 %8 的部分 如果是 DF 的話應該只有 %10
那就是因為 IDF 會不斷地以每個新計算的 DF block (i.e. %10)當起點
找下一個對應的 DF block (i.e. %11)
目前 LLVM middle-end(i.e. target-independent optimizations/analysis)
基本上都已經換裝成 IDFCalculator(除了 RegionInfo 以外)
目前還有在用 (deprecated)DominanceFrontier 的主要是 Machine IR 的 pass
但我倒覺得 LLVM codebase 換裝 IDFCalculator 單純只是現有的 middle-end
optimization/analysis 使用者大多是處理 Phi node 相關，才會想要一次算出
「整串」的 dominance frontier block
而舊版的 DominaceFrontier 可能在一次算出整串 DF block 方面比較沒效率
: 同樣去 trace DominanceFrontier 的話, 應該也可以發現他也是基於
: DominanceFrontierBase 的 IsPostDom=flase,
: 所以你應該可以參考原本的做法, 加一個 IsPostDom=true 就是你要的
: PostDominanceFrontier了
: class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
: template <class BlockT>
: class ForwardDominanceFrontierBase
: : public DominanceFrontierBase<BlockT, false> {
: template <class BlockT, bool IsPostDom>
: class DominanceFrontierBase;
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.116.240
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1545742360.A.C6D.html