作者shane87123 (陽光大肥宅)
看板CompilerDev
標題[問題] 取得llvm IR RAW等等 資料相依
時間Wed Dec 1 15:27:52 2021
先謝謝這個版，讓我有機會問問題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://webptt.com/m.aspx?n=bbs/CompilerDev/M.1638343674.A.C39.html
※ 編輯: shane87123 (49.216.177.10 臺灣), 12/01/2021 15:28:41
1F：推 VF84: 所以你是想要找出 use-def chain ?12/01 19:12
2F：→ VF84: LLVM 的 Value 有個 member 叫 UseList。 12/01 19:13
3F：→ VF84: 那個應該可以滿足你的需要？12/01 19:14
4F：→ VF84: 寫個 pass 分析一下應該不難12/01 19:14
5F：→ Lipraxde: LLVM 最為一個 SSA form 的 IR，value 「只能被賦值一12/01 19:45
6F：→ Lipraxde: 次」，def-use chain 就是你要找的「value 的關係」了12/01 19:45
7F：→ Lipraxde: 。由於 SSA 的 value 只能被賦值一次的關係，宣告變數12/01 19:45
8F：→ Lipraxde: 的一種替代方式就是先 allocate 一塊空間，對其做 load12/01 19:45
9F：→ Lipraxde: /store，一般 dependency analysis 是在分析這些 alloc12/01 19:45
10F：→ Lipraxde: ate 出來的空間。12/01 19:45
那 dependency 的 distance多遠，是不是根據硬體的 pipeline 等多種因素決定？
假如我有一個variable def 了，但到很後面才用到，感覺上 dependency 不大，
反之，如我範例程式碼，
這樣就有dependency了
※ 編輯: shane87123 (49.216.177.10 臺灣), 12/01/2021 20:09:51
11F：→ Lipraxde: 應該是 compiler 要依 backend pipeline 來決定 instru12/01 23:32
12F：→ Lipraxde: ction scheduling，dependency 是用來避免 schedule 排12/01 23:32
13F：→ Lipraxde: 錯的 (例如本來是 RAW，結果你把 R 排到 W 前面，那 R12/01 23:32
14F：→ Lipraxde: 讀到的值就跟沒排前不同)。 12/01 23:32
15F：→ Lipraxde: 至於 variable def 後到很後面才用到，代表的是這個 va12/01 23:32
16F：→ Lipraxde: riable 的 lifetime 很長，不代表它們之間沒有 depende 12/01 23:32
17F：→ Lipraxde: ncy。 12/01 23:32
18F：→ Lipraxde: 更正一下：「compiler 要依 backend pipeline...」-> c 12/01 23:34
19F：→ Lipraxde: ompiler 要參考 backend pipeline...，這樣比較精確 12/01 23:34
→ 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
20F：→ Lipraxde: 第一份跑得比較快是因為 br 和 div 可以同時做，而第二12/02 12:24
21F：→ Lipraxde: 份要等到 br 做完 (或是 branch predict 有對) 才能跑12/02 12:24
22F：→ Lipraxde: ，又因為 mul 需要 div 的結果，mul 不能偷跑。12/02 12:24
23F：→ Lipraxde: Data dependency 跟 instruction scheduling 有關，但12/02 12:33
24F：→ Lipraxde: 這不代表它就是這個 case 的原因。兩份 binary 的 data12/02 12:33
25F：→ Lipraxde: dependency 都一樣，你下的結論從何而來？12/02 12:33
我好像可以理解
就是說他們的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
26F：→ Lipraxde: 是啊，原因是你的「pipeline一次可以做5個inst」，div 12/02 20:05
27F：→ Lipraxde: 、mul 間隔的遠只是一種現象。 12/02 20:05
28F：→ sonicyang: pipeline可能有bypass沒有必要等register profile upda 12/03 19:52
29F：→ sonicyang: te。這題是後端問題，根據不同的架構有不一樣的最佳sch 12/03 19:52
30F：→ sonicyang: eduling跟不一樣的執行結果是正常的。現在除非你是什麼 12/03 19:52
31F：→ sonicyang: 很簡單的微處理器，滿街superscalar每個都有很多細節不 12/03 19:52
32F：→ sonicyang: 是單純教科書講的完的。你這個case 是 ir level branch 12/03 19:52
33F：→ sonicyang: 換位置間接影響到了後端的codegen再加上你benchmark的 12/03 19:52
34F：→ sonicyang: 架構會有效能差異，你要分析需要完整的分析不是單純在o 12/03 19:52
35F：→ sonicyang: r level。然後有branch不代表不能偷跑不然spectre/melt 12/03 19:52
36F：→ sonicyang: down怎麼來的？ 12/03 19:52