[LLVMdev] some superoptimizer results

[Duncan Sands]

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.