[LLVMdev] [llvm-commits] [llvm] r123754 - in /llvm/trunk: lib/Analysis/InstructionSimplify.cpp test/Transforms/InstSimplify/2010-12-20-Distribute.ll

[Nuno Lopes]

Thanks for the nice explanation and for making the code available!
Nuno

----- Original Message -----
> There's some interest in my "auto-simplifier", which is nice :), so let me
> explain a bit about it.
>
> On 19/01/11 19:35, Sandeep Patel wrote:
> > You've mentioned your auto-simplifier a few times now and curiosity is
> > getting the better of me. Can you explain it a bit more?
>
> On 20/01/11 00:32, Nuno Lopes wrote:
> > Just out of curiosity, what's this auto-simplifier? Have you built some
> > superoptimizer or something similar?
> > I'm just asking because building a tool to generate the instruction 
> > simplifier
> > automatically is relatively high on my TODO list and I don't want to 
> > duplicate
> > work :)
>
> The auto-simplifier is a very simple kind of super-optimizer.  It tries to 
> find
> optimizations suitable for InstructionSimplify [instsimplify].  The 
> difference
> between instsimplify and instcombine is that instcombine is allowed to 
> create
> new instructions while instsimplify needs to simplify expressions to 
> already
> existing subexpressions present inside the existing expression.  For 
> example
> instsimplify can turn this
>   (X + Y) - X
> into
>   Y
> because Y was already present inside the original expression, but it can't 
> turn
>   X - (X + Y)
> into
>   -Y
> because -Y was not present inside the original expression.  Instcombine 
> will
> happily do the second transform because it doesn't have this limitation.
> Instsimplify is allowed to produce constants that were original present, 
> for
> example it is allowed to turn
>   X & X
> into
>   0
>
> Given an expression the auto-simplifier finds subexpressions that always 
> compute
> the same result as the original expression (beware: it may sometimes get 
> this
> wrong, especially for large expressions, and say that it simplifies when 
> it
> doesn't;  on the other hand it should never say that an expression doesn't
> simplify when it does - that's would be a bug).
>
> You can get it like this: svn co svn://topo.math.u-psud.fr/harvest
> As explained in the README there are two main parts: (1) harvesting 
> expressions
> from IR (currently only side-effect free integer expressions are 
> supported), and
> (2) looking for simplifications.
>
> You can use it something like this to harvest IR sequences from the 
> optimized
> clang output for a file, sort them by order of popularity, and look for 
> ones
> that simplify:
>
>   clang -c -emit-llvm -O2 file.c -o - | 
> opt -load=./harvest.so -harvest -disable-output | sort | uniq -c | 
> sort -n -r | grep -o "[^ ]*$" | ./solve
>
> For example, doing this on gcc-as-one-big-file finds some simplifications:
>
> Input: 06:07:06:07:07:0e:16:18:0e:09:01:00:-0004:1b:25
> x = (((X + Y) >>l ..1.) & Z) + ..1.
> Root: (x == 0) ? 1 : (zext x)
> PASS:
> x = (((X + Y) >>l ..1.) & Z) + ..1.
> x == 0
> constant folds to 0 01.1 11.0
>
> Here the first three lines describe input expression.  The first line 
> prints it
> in its encoded normalized form (good for sorting on etc), the next two 
> pretty
> print it.  The expression is "(x == 0) ? 1 : (zext x)" where x is 
> short-hand for
> "(((X + Y) >>l ..1.) & Z) + ..1." as explained in the second line.  Here 
> "..1."
> stands for a constant which is not known but is known to be a power of two 
> (it
> is supposed to represent a single bit set to 1 in a sea of bits ....). 
> Anyway,
> you see that the root of the expression is a select ("?") conditioned on 
> x==0.
> PASS means that it found a simplification.  The simplification is that 
> "x==0"
> is always false, i.e. constant folds to zero.  It prints that it constant 
> folds
> to one of the constants 0 (zero), 01.1 (max positive value, i.e. all bits 
> one
> except for the top bit), 11.0 (minus 2, i.e. all bits one except for the 
> bottom
> bit).  The reason it prints them all is that the result of the compare has 
> i1
> type and for a one bit type these three constants are all equal so it 
> can't
> distinguish between them.  Exercise: is this simplification correct (it 
> is)? :)
>
> Here's another one:
>
> Input: 07:06:0f:-0002:00:-0005:1b:25
> x = ..1.
> Root: (X == 0) ? x : (x - X)
> PASS:
> x = ..1.
> (X == 0) ? x : (x - X)
> simplifies to
> x = ..1.
> x - X
>
> It says that the select "(X == 0) ? x : (x - X)" simplifies to "x - X".
> Well this is true, since if X is zero then x equals x-X.
>
> Ciao, Duncan.