The current gvn equality propagation is not powerful enough to get this

because it doesn't try to infer values in predicates based on other

predicates, so it never realizes a>b -> a !=b in a useful way.

It otherwise would get this

Sorry if this is a bit of a stupid question, but what exactly is the scope

of what a GVN pass does?

Depends on who you ask. The most general correct answer i can give is:

prove whatever things it can to be equivalent by computing their value.

If you could prove everything equivalent that is possible, you would,

subject to compile time

Think of GVN as an analysis whose goal is to prove what things in the

domain of the program have equivalent values.

I've read various "textbook" definitions of GVN but they all seem to

revolve around proving that different expressions in the program are

equivalent.

Most textboox definitions ignore conditionals.

For example, "complete" value numbering would be discovery of all herbrand

equivalences.

This ignores conditionals and what equivalences they can be used to prove

(they treat conditionals as always non-deterministic).

Predicated GVN algorithms instead try to take predicates into account, in

order to infer the equality of more values. If you were, for example, to

drop the predicate support current GVN has, you'd heavily decrease it's

effectiveness.

Note that a lot of research papers have to be read very carefully to

discover what their domain is.

If you read, http://arxiv.org/pdf/1302.6325.pdf, they point out most of the

papers restrict the problem to discovering the equality of variables in the

program, and not discovering the equality of *expressions*.

What you're talking about here seems to go outside that; e.g. being more

like what one would expect CorrelatedValuePropagation to do.

You are just thinking about it in terms of existing program expressions.

Necula proves (here:

http://people.eecs.berkeley.edu/~necula/Papers/gvndet_sas04.pdf) that there

is a significant distinction to be made between computing all herbrand

equivalences and computing all herbrand equivalences among sub-expressions

of the program.

In this case, GVN would just be proving n1 == n2 is equivalent to the

expression false.

If it has some form of redundancy elimination built on top of it, it

usually then replaces it with that value.

It would then do nothing else.

It's possible to unify gvn with dead code elimination and constant

propagation (pretty easily in fact).

In such a formulation, it will discover that n1 == n2 is equivalent to

false, and thus that the block it leads to is unreachable.

Again, the new gvn itself does nothing with this info other than use it to

further prove things about values (IE for example, that only one edge of a

phi is live and thus the phi has the same value as that live edge's

incoming value).

Elimination can, of course, trivially just delete all the unreachable

blocks (or mark them unreachable if it wants).

Our current GVN already does predication, just not in a very

algorithmically complete way.

Doing it in a complete way would eliminate most of

correlatedValuePropagation. You could eliminate the rest of it by

integrating proper range analysis as you want. That's just "another source

of predicates".

In *practice*, what i care about is getting good enough results quickly,

and making GVN a real analysis used by other things (PRE, etc) while making

it fast.

(If i ever finish, i'll then likely move on to replacing LVI with some

extended SSA + range analysis :P)