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