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

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.

 >> Author: baldrick
 >> Date: Tue Jan 18 03:24:58 2011
 >> New Revision: 123754
 >>
 >> URL: http://llvm.org/viewvc/llvm-project?rev=123754&view=rev
 >> Log:
 >> Simplify (X<<1)-X into X. According to my auto-simplier this is
the most
 >> common missed
 >> simplification in fully optimized code. It occurs sporadically in the
 >> testsuite, and
 >> many times in 403.gcc: the final bitcode has 131 fewer subtractions
after this
 >> change.
 >> The reason that the multiplies are not eliminated is the same reason
that
 >> instcombine
 >> did not catch this: they are used by other instructions (instcombine
catches
 >> this with
 >> a more general transform which in general is only profitable if the
operands
 >> have only
 >> one use).

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.