[LLVMdev] some superoptimizer results

[Duncan Sands]

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