Fast integer division by constants #9786
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.