[PATCH]: Allow PRE to insert no-cost phi nodes

Current PRE tries to not increase code size.
It does this with a check whether or not the number of places it would have to insert is 1 or not.

The problem with this is that the answer could also be “we have to insert in zero places” in the case it’s available in all predecessors.

Normal dominator based elimination in GVN will not catch these cases because the branches do not dominate the merge point.

A simple example
int c;

int d;
int pre(int foo, int a, int b)
int g;
if (foo) {
c = a+b;
} else {
d = a+ b;
g = a+b;
return g;

Without this patch, PRE (and GVN) will not eliminate g = a+b.
With this patch, PRE will create phi(c, d) and eliminate g = a + b.

(It is tremendously more difficult to make current GVN understand the problem, and GCC solves this the same way i’m about to).

The patch looks large because of code movement, but it basically all boils down to changing this check:

if (NumWithout != 1 || NumWith == 0)

if (NumWithout > 1 || NumWith == 0)

and skipping insertion when NumWithout == 0

testcase included.

pre-no-cost-phi.diff (6.5 KB)

For the curious

On clang as a bytecode file, just running mem2reg, basicaa, and gvn

Before we had:
561 gvn - Number of instructions PRE’d

After this patch we have:

1517 gvn - Number of instructions PRE’d

LGTM. Nice find.

For anyone curious, this case applies to PRE, but not LoadPRE. We do handle full redundancy for loads today.