There's some interest in my "auto-simplifier", which is nice :), so let me

explain a bit about it.

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

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