Skip to content

Fast integer division by constants #9786

Jannis requested to merge 1Jajen1/ghc:wip/constDivision into master

This optimizes integer division by constants (#9786) into multiplication, bitshifts and addition, which is much faster than performing the actual division. The algorithms are derived from Hackers Delight Edition 2, which has an entire chapter dedicated to this.

This sadly does a lot more than "just" rewriting a specific CmmExpr because it needs temporary variables and instructions such as Mul2.

So to solve this I made constantFoldNode able to expand into multiple nodes. By doing so I probably messed up some implicit rules about how cmmSink works. Also this probably did hurt performance a bit.

This added complexity comes with some nice bits as well: Since we can expand a node during constant folding into multiple ones, we can fold CallishMachOp's, which I already partially added for QuotRem and Mul2.

So apart from that, there is one deviation from Hacker's delight, which is to avoid the expensive case in the unsigned division using an additional shift.

Edited by Jannis

Merge request reports