作者shane87123 (阳光大肥宅)
看板CompilerDev
标题[问题] division-by-constant 非实作在LLVM IR
时间Sun Apr 10 19:41:51 2022
如标题
我发现一个优化演算法为 division-by-constant
当除数为常数时
他可以把除法转换成乘法+算数右移
但他却是在 backend 阶段才应用的
为什麽他不是在 LLVM IR 阶段实作？
我猜可能是乘法的 cost 根据硬体可能不一定比除法 cheap
因此我在猜应该能在 LLVM IR 阶段拿到相关资讯
如 TargetTransforminfo 之类的分析 Pass
但我查一查发现都没有
但是在 DAGCombiner.cpp 有找到类似的 function
叫做 `isIntDivCheap`，结果里面判定是否比较 "Cheap" 的方法是根据优化目的
若以 code size 为优化目的，则 division 比 mul+shr还便宜没错
前者只要一个指令，後者两个，明显便宜一点
但是如果是以速度为目的的话，mul+shr比较便宜（该 function 只做这些判断）
我自己推导成->不论何种硬体，後者速度比前者（除法）快
那为什麽该优化演算法不是实作在 LLVM IR 上？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.160.190.187 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/CompilerDev/M.1649590913.A.8C4.html
※ 编辑: shane87123 (1.160.190.187 台湾), 04/10/2022 22:05:55
※ 编辑: shane87123 (1.160.190.187 台湾), 04/10/2022 22:06:22
1F：推 LPH66: 我猜数制问题? 实际乘和移的数字应该跟目标是二补还是其他 04/11 06:55
2F：→ LPH66: 有关, 所以无法贸然在 IR 上直接转换 04/11 06:55
其实经过转换後都是一些 magic number，
如果 IR 阶段能拿到一些硬体资讯然後做转换，应该还行吧？
3F：→ Lipraxde: IR 表示语意，codegen 的时候决定怎麽生不是吗？ 04/11 09:05
4F：→ Lipraxde: 你问为什麽不是实作在 LLVM IR 上，我猜是指 InstCombi 04/11 09:14
5F：→ Lipraxde: ne？理论上有拿到 target 资讯当然都可以做，可是提前 04/11 09:14
不一定是 InstCombine(?
可以是另一个 Pass 之类的
6F：→ Lipraxde: 做有特别的好处？进到 codegen 阶段时在做顺理成章的拿 04/11 09:14
7F：→ Lipraxde: 资讯，也只需要看是不是 div by const，做在後面应该是 04/11 09:14
8F：→ Lipraxde: 蛮合理的选择 04/11 09:14
我的想法是，如果所有硬体都会因此提升效能的话
做在 LLVM IR 不是有更好的模组性吗？
※ 编辑: shane87123 (1.160.190.187 台湾), 04/11/2022 11:15:56
※ 编辑: shane87123 (1.160.190.187 台湾), 04/11/2022 11:20:35
9F：→ Lipraxde: 有更好吗，我不确定XD，不过看你回说会乘 magic number 04/11 12:27
10F：→ Lipraxde: ，我想到有没有可能是因为会有 poison value 的关系？ 04/11 12:27
我想那应该跟硬体资讯有关？
多少位元会 overflow 之类的
但这些资讯 IR 应该是得的到的
经过这番思考後，我觉得我对 LLVM IR 的出现有很深的误会（？
我以为对所有硬体都有优化效果的都会实作在 LLVM IR 上
如：peephole, constant folding, loop unroll, loop vectorize 之类的
但似乎不是
有看过一个说法是一个 division 比较好分析和优化，比起multiplication+bitwise
※ 编辑: shane87123 (1.160.190.187 台湾), 04/11/2022 19:08:14
12F：→ Lipraxde: ...优化是有分 target-dependent/independent，有各自 04/12 13:39
13F：→ Lipraxde: 的分类，不过我是觉得不必那麽考究，在哪方便做就在哪 04/12 13:39
14F：→ Lipraxde: 做。像是你这篇的例子，如果不会遇到些数值计算上的问 04/12 13:39
15F：→ Lipraxde: 题，要当 peephole 来做应该也没什麽不行 04/12 13:39
好吧～ 可能我太刁钻於实作在哪块了
谢谢大大解惑
※ 编辑: shane87123 (114.43.60.48 台湾), 04/12/2022 16:02:20
16F：推 eopXD: 推推 好问题 04/13 15:13