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

[Duncan Sands]

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).