[問題] division-by-constant 非實作在LLVM IR

[shane87123 (陽光大肥宅)]

如標題

我發現一個優化演算法為 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://www.ptt.cc/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
推 LPH66: 我猜數制問題? 實際乘和移的數字應該跟目標是二補還是其他
→ LPH66: 有關, 所以無法貿然在 IR 上直接轉換
其實經過轉換後都是一些 magic number，
如果 IR 階段能拿到一些硬體資訊然後做轉換，應該還行吧？
→ Lipraxde: IR 表示語意，codegen 的時候決定怎麼生不是嗎？
→ Lipraxde: 你問為什麼不是實作在 LLVM IR 上，我猜是指 InstCombi
→ Lipraxde: ne？理論上有拿到 target 資訊當然都可以做，可是提前
不一定是 InstCombine(?
可以是另一個 Pass 之類的
→ Lipraxde: 做有特別的好處？進到 codegen 階段時在做順理成章的拿
→ Lipraxde: 資訊，也只需要看是不是 div by const，做在後面應該是
→ Lipraxde: 蠻合理的選擇
我的想法是，如果所有硬體都會因此提升效能的話
做在 LLVM IR 不是有更好的模組性嗎？
※ 編輯: shane87123 (1.160.190.187 臺灣), 04/11/2022 11:15:56
※ 編輯: shane87123 (1.160.190.187 臺灣), 04/11/2022 11:20:35
→ Lipraxde: 有更好嗎，我不確定XD，不過看你回說會乘 magic number
→ Lipraxde: ，我想到有沒有可能是因為會有 poison value 的關係？
我想那應該跟硬體資訊有關？
多少位元會 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
→ Lipraxde: #1U-Edzwa (CompilerDev)、#1V0N0xoL (CompilerDev) 恩
→ Lipraxde: ...優化是有分 target-dependent/independent，有各自
→ Lipraxde: 的分類，不過我是覺得不必那麼考究，在哪方便做就在哪
→ Lipraxde: 做。像是你這篇的例子，如果不會遇到些數值計算上的問
→ Lipraxde: 題，要當 peephole 來做應該也沒什麼不行
好吧～ 可能我太刁鑽於實作在哪塊了

謝謝大大解惑
※ 編輯: shane87123 (114.43.60.48 臺灣), 04/12/2022 16:02:20
推 eopXD: 推推 好問題