[問題] division-by-constant 非實作在LLVMI R

看板CompilerDev作者 (陽光大肥宅)時間3年前 (2022/04/10 19:41), 3年前編輯推噓2(2推 0噓 14→)
留言16則, 3人參與, 3年前最新討論串1/1
如標題 我發現一個優化演算法為 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
推
04/11 06:55, 3年前 , 1F
我猜數制問題? 實際乘和移的數字應該跟目標是二補還是其他
04/11 06:55, 1F
→
04/11 06:55, 3年前 , 2F
有關, 所以無法貿然在 IR 上直接轉換
04/11 06:55, 2F
其實經過轉換後都是一些 magic number， 如果 IR 階段能拿到一些硬體資訊然後做轉換，應該還行吧？
→
04/11 09:05, 3年前 , 3F
IR 表示語意，codegen 的時候決定怎麼生不是嗎？
04/11 09:05, 3F
→
04/11 09:14, 3年前 , 4F
你問為什麼不是實作在 LLVM IR 上，我猜是指 InstCombi
04/11 09:14, 4F
→
04/11 09:14, 3年前 , 5F
ne？理論上有拿到 target 資訊當然都可以做，可是提前
04/11 09:14, 5F
不一定是 InstCombine(? 可以是另一個 Pass 之類的
→
04/11 09:14, 3年前 , 6F
做有特別的好處？進到 codegen 階段時在做順理成章的拿
04/11 09:14, 6F
→
04/11 09:14, 3年前 , 7F
資訊，也只需要看是不是 div by const，做在後面應該是
04/11 09:14, 7F
→
04/11 09:14, 3年前 , 8F
蠻合理的選擇
04/11 09:14, 8F
我的想法是，如果所有硬體都會因此提升效能的話 做在 LLVM IR 不是有更好的模組性嗎？ ※ 編輯: shane87123 (1.160.190.187 臺灣), 04/11/2022 11:15:56 ※ 編輯: shane87123 (1.160.190.187 臺灣), 04/11/2022 11:20:35
→
04/11 12:27, 3年前 , 9F
有更好嗎，我不確定XD，不過看你回說會乘 magic number
04/11 12:27, 9F
→
04/11 12:27, 3年前 , 10F
，我想到有沒有可能是因為會有 poison value 的關係？
04/11 12:27, 10F
我想那應該跟硬體資訊有關？ 多少位元會 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
→
04/12 13:39, 3年前 , 11F
04/12 13:39, 11F
→
04/12 13:39, 3年前 , 12F
...優化是有分 target-dependent/independent，有各自
04/12 13:39, 12F
→
04/12 13:39, 3年前 , 13F
的分類，不過我是覺得不必那麼考究，在哪方便做就在哪
04/12 13:39, 13F
→
04/12 13:39, 3年前 , 14F
做。像是你這篇的例子，如果不會遇到些數值計算上的問
04/12 13:39, 14F
→
04/12 13:39, 3年前 , 15F
題，要當 peephole 來做應該也沒什麼不行
04/12 13:39, 15F
好吧～ 可能我太刁鑽於實作在哪塊了 謝謝大大解惑 ※ 編輯: shane87123 (114.43.60.48 臺灣), 04/12/2022 16:02:20
推
04/13 15:13, 3年前 , 16F
推推 好問題
04/13 15:13, 16F
‣ 更多 shane87123 的文章
文章代碼(AID): #1YKiA1Z4 (CompilerDev)