[LLVMdev] some superoptimizer results (original) (raw)

Duncan Sands duncan.sands at deepbluecap.com
Mon Jul 27 04:15:56 PDT 2015

Hi John,

On 24/07/15 18:43, John Regehr wrote:

example (x+y)-x -> y. Here the right-hand side "y" is a particularly simple subexpression of the original :) Yeah. We have not found a lot of this kind of thing-- it looks like you and others scooped up a lot of the low-hanging fruit!

yeah, sorry about that :) It means you are directly confronted with issues of cost, which I managed to sidestep.

I do have a suggestion though for how you might also sidestep it, at least a little bit: stick to "invertible" transformations, i.e. those that can be undone. For example, suppose your superoptimizer finds the transformation E1 -> E2. That means that you have proved that replacing E1 with E2 is correct. "Invertibility" means that replacing E2 with E1 should also be (proved to be) correct.

If you stick to invertible transformations then you are really doing normalization rather than simplification. The big advantage of invertible transformations is that you aren't throwing anything away, so if some target doesn't like it then it can always undo the transform in the back-end, at least in theory.

You still need a cost model. Since LLVM IR is very far away from the target machine I reckon you should stick to the simplest one: minimizing the number of IR instructions.

Ciao, Duncan.

More information about the llvm-dev mailing list