llvm dev - Jul 2015 - [LLVMdev] some superoptimizer results

Hi,

On 23/07/15 19:11, Philip Reames wrote:
>
>
> On 07/23/2015 07:24 AM, John Regehr wrote:
>>> I guess another way to select interesting transformations could be
to look
>>> for sequences where the
>>> result uses a "subset" of the input instruction sequence.
>>
>> Yeah, I had been noticing those subsets too.  It sounds like it's
worth a try
>> doing a run that looks only for those.
>>
>> One nice thing is that if we're just looking for subsets, we will
not even
>> give the syntehsizer the option to use instructions that aren't in
the subset
>> -- this should give a nice speedup, and probably will even make
synthesis more
>> likely to succeed (assuming that an optimization exists within the
subset).
> +1 - This sounds like a very interesting approach.  I suspect it might also
find
> cases which are easier to hand generalize, but that's just a guess.
this sounds like what my LLVM superoptimizer did: simplified expressions to 
subexpressions that were already present in the original expression, for example
(x+y)-x -> y.  Here the right-hand side "y" is a particularly
simple
subexpression of the original :)

One big advantage is that you can process expressions very fast, typically 
hundreds per second.  The other advantage is that optimizations you find are 
unlikely to make things worse (but they can increase register pressure).  The 
big disadvantage is of course that it misses many interesting optimizations, for
example it will miss x-(x+y) -> -y because -y wasn't in the original
expression.

Another simple trick for finding optimizations is to detect inputs that have no 
effect on outputs.  For example, in x-(x+y), the result of the expression 
doesn't depend on the value of x.  Thus you can replace x with whatever you
like
without changing anything, for example replacing x with 0 you get 0-(0+y) which 
simplifies down to 0-y, i.e. -y.  You have found x-(x+y) -> -y.

Ciao, Duncan.
>
> Another option would be exclude extensions of i1 and non cmov-like selects
from
> the candidate set.  A lot of the examples in this set end up converting
> conditional codes to register values which is non-ideal. I saw a couple of
> examples which had obvious cmov implementations which just weren't
expressed
> that way in the output.
>
> A couple of small suggestions on the output formatting:
> - Give each entry a unique ID (result set 3 #25 would be fine). That would
make
> them much easier to discuss.
> - Exclude examples where only a prefix changes.  There were several
instances
> where the last instruction in the sequence was duplicated exactly.  This is
> essentially an instance of synthesizing the subproblem and results in
duplicates
> in the output.
> - Group all inputs at the beginning.  Follow with an instructions which are
> shared between input and output.  This'll make it easier to scan the
output.
>>
>> John
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

> 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!

John

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.