作者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/cn.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