[問題] 取得llvm IR RAW等等 資料相依

看板CompilerDev作者 (陽光大肥宅)時間4年前 (2021/12/01 15:27), 4年前編輯推噓1(1推 0噓 35→)
留言36則, 3人參與, 4年前最新討論串1/1
先謝謝這個版，讓我有機會問問題QQ 最近苦惱了許久，考量一下範例程式碼： 1. %div = sdiv i32 %add, %36 2. %38 = trunc i64 %indvars.iv.next18 to i32 3. %mul11 = mul nsw i32 %div, %38 %div 先是被計算，並在 3. 使用，%38 也是 不知道有沒有工具能夠找出這種關係？ 我有參考這個 Developers’ Meeting: https://www.youtube.com/watch?v=1e5y6WDbXCQ
裡面有 slides，有提到這個問題 (RAW, WAR, WAW) 而我自己嘗試使用以下 command opt -enable-new-pm=0 -da -analyze source_ir.ll 得到一大串資訊，但沒有提到我上面的程式碼（沒有被掃到？） opt -enable-new-pm=0 aa-eval -stats source_ir.ll (感謝 Lipraxde 在上一篇題點） 出來的資訊似乎也掃不到上述程式碼 opt -enable-new-pm=0 -memdep -analyze source_ir.ll 得不到資訊，( 得到：:print not implemented for pass: 'Memory Dependence Analys is'!） opt -enable-new-pm=0 -print-memdeps source_ir.ll 會直接出現 Error XDD 找不太到有人在討論RAW WAW WAR 這塊 dependency 拿去餵 google 只找得到 llvm-mca 有相關資訊， 不過那是要在分析 Assembly code，並不是我要的 不過我開始在思考，這類的 dependency 只能在 assembly code 被分析？ 畢竟跟 底層 cpu 的 pipeline stage 數量有關。（依照我記憶力薄弱的計算機組織知識 ） 手機排版，請見諒～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.177.10 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/CompilerDev/M.1638343674.A.C39.html ※ 編輯: shane87123 (49.216.177.10 臺灣), 12/01/2021 15:28:41
推
12/01 19:12, 4年前 , 1F
所以你是想要找出 use-def chain ?
12/01 19:12, 1F
→
12/01 19:13, 4年前 , 2F
LLVM 的 Value 有個 member 叫 UseList。
12/01 19:13, 2F
→
12/01 19:14, 4年前 , 3F
那個應該可以滿足你的需要？
12/01 19:14, 3F
→
12/01 19:14, 4年前 , 4F
寫個 pass 分析一下應該不難
12/01 19:14, 4F
→
12/01 19:45, 4年前 , 5F
LLVM 最為一個 SSA form 的 IR，value 「只能被賦值一
12/01 19:45, 5F
→
12/01 19:45, 4年前 , 6F
次」，def-use chain 就是你要找的「value 的關係」了
12/01 19:45, 6F
→
12/01 19:45, 4年前 , 7F
。由於 SSA 的 value 只能被賦值一次的關係，宣告變數
12/01 19:45, 7F
→
12/01 19:45, 4年前 , 8F
的一種替代方式就是先 allocate 一塊空間，對其做 load
12/01 19:45, 8F
→
12/01 19:45, 4年前 , 9F
/store，一般 dependency analysis 是在分析這些 alloc
12/01 19:45, 9F
→
12/01 19:45, 4年前 , 10F
ate 出來的空間。
12/01 19:45, 10F
那 dependency 的 distance多遠，是不是根據硬體的 pipeline 等多種因素決定？ 假如我有一個variable def 了，但到很後面才用到，感覺上 dependency 不大， 反之，如我範例程式碼， 這樣就有dependency了 ※ 編輯: shane87123 (49.216.177.10 臺灣), 12/01/2021 20:09:51
→
12/01 23:32, 4年前 , 11F
應該是 compiler 要依 backend pipeline 來決定 instru
12/01 23:32, 11F
→
12/01 23:32, 4年前 , 12F
ction scheduling，dependency 是用來避免 schedule 排
12/01 23:32, 12F
→
12/01 23:32, 4年前 , 13F
錯的 (例如本來是 RAW，結果你把 R 排到 W 前面，那 R
12/01 23:32, 13F
→
12/01 23:32, 4年前 , 14F
讀到的值就跟沒排前不同)。
12/01 23:32, 14F
→
12/01 23:32, 4年前 , 15F
至於 variable def 後到很後面才用到，代表的是這個 va
12/01 23:32, 15F
→
12/01 23:32, 4年前 , 16F
riable 的 lifetime 很長，不代表它們之間沒有 depende
12/01 23:32, 16F
→
12/01 23:32, 4年前 , 17F
ncy。
12/01 23:32, 17F
→
12/01 23:34, 4年前 , 18F
更正一下：「compiler 要依 backend pipeline...」-> c
12/01 23:34, 18F
→
12/01 23:34, 4年前 , 19F
ompiler 要參考 backend pipeline...，這樣比較精確
12/01 23:34, 19F
→ sonicyang: 怎麼覺得元po把ir跟後端還有機械碼拉成一坨了... 12/02 01:33 我也不是很想拉成一坨XDD，但我感覺他們就是如此相輔相成 我會有這疑問，是因為我的實驗室這樣： 我有一份source code (C 檔) 然後根據不同的 pass order 優化後產生兩種不同的 ir c ode 第一份： div .... . . . br A: A: mul ...... 第二份： . . . . . br A: A: div ..... mul ..... 其中div 和 mul 的內容如同原文打的範例程式 br 並非每次都跳到 A，因此第二份程式碼理論上應該比較少執行到 div ，但 run time 卻慢 10%， 我有自己把第二份的 div 往上搬，run time 就跟第一份一樣了 我有檢查過兩份 IR ，基本上邏輯是一樣的，就只差在 div 和 mul 的距離， 因此我想做採集這種關係的靜態分析，但卡在兩者程式碼距離多遠才會互相牽制到。 然後，我有把這兩份 IR 轉成 Assembly code，用的指令是： llc source_ir1.ll -O0 ; llc source_ir2.ll -O0 (用 O0 主要是想看 llc 不經過優化地把 IR 轉成 Assembly code) 確實 兩份的 div 和 mul 距離不一樣。 我才會根據我的知識，回推並下一個結論：RAW 導致拖慢 run time。 ※ 編輯: shane87123 (49.216.177.10 臺灣), 12/02/2021 09:10:30
→
12/02 12:24, 4年前 , 20F
第一份跑得比較快是因為 br 和 div 可以同時做，而第二
12/02 12:24, 20F
→
12/02 12:24, 4年前 , 21F
份要等到 br 做完 (或是 branch predict 有對) 才能跑
12/02 12:24, 21F
→
12/02 12:24, 4年前 , 22F
，又因為 mul 需要 div 的結果，mul 不能偷跑。
12/02 12:24, 22F
→
12/02 12:33, 4年前 , 23F
Data dependency 跟 instruction scheduling 有關，但
12/02 12:33, 23F
→
12/02 12:33, 4年前 , 24F
這不代表它就是這個 case 的原因。兩份 binary 的 data
12/02 12:33, 24F
→
12/02 12:33, 4年前 , 25F
dependency 都一樣，你下的結論從何而來？
12/02 12:33, 25F
我好像可以理解 就是說他們的dependency關係是一樣的，兩份code只差在能不能偷跑。 那假如今天 div和 mul在同一個basic block內， 但div中間隔很遠才遇到mul 是不是有機會可以偷跑？ 那中間隔多遠可以偷跑是不是取決於底下的硬體？ 例如，pipeline一次可以做5個inst 那我code長這樣 div Inst 1 Inst 2 Inst 3 Inst 4 Inst 5 mul 代表說我要做mul 時，div值已經知道了 但如果是這樣： inst 1 Inst 2 Inst 3 Inst 4 Inst 5 div Mul 這樣還要等div做完 mul才能做 是不是會慢許多？ ※ 編輯: shane87123 (49.216.177.10 臺灣), 12/02/2021 13:23:18
→
12/02 20:05, 4年前 , 26F
是啊，原因是你的「pipeline一次可以做5個inst」，div
12/02 20:05, 26F
→
12/02 20:05, 4年前 , 27F
、mul 間隔的遠只是一種現象。
12/02 20:05, 27F
→
12/03 19:52, 4年前 , 28F
pipeline可能有bypass沒有必要等register profile upda
12/03 19:52, 28F
→
12/03 19:52, 4年前 , 29F
te。這題是後端問題，根據不同的架構有不一樣的最佳sch
12/03 19:52, 29F
→
12/03 19:52, 4年前 , 30F
eduling跟不一樣的執行結果是正常的。現在除非你是什麼
12/03 19:52, 30F
→
12/03 19:52, 4年前 , 31F
很簡單的微處理器，滿街superscalar每個都有很多細節不
12/03 19:52, 31F
→
12/03 19:52, 4年前 , 32F
是單純教科書講的完的。你這個case 是 ir level branch
12/03 19:52, 32F
→
12/03 19:52, 4年前 , 33F
換位置間接影響到了後端的codegen再加上你benchmark的
12/03 19:52, 33F
→
12/03 19:52, 4年前 , 34F
架構會有效能差異，你要分析需要完整的分析不是單純在o
12/03 19:52, 34F
→
12/03 19:52, 4年前 , 35F
r level。然後有branch不代表不能偷跑不然spectre/melt
12/03 19:52, 35F
→
12/03 19:52, 4年前 , 36F
down怎麼來的？
12/03 19:52, 36F
‣ 更多 shane87123 的文章
文章代碼(AID): #1XfoFwmv (CompilerDev)