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

[Daniel Berlin]

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)

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

and skipping insertion when NumWithout == 0

testcase included.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150128/cde0a5ae/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pre-no-cost-phi.diff
Type: application/octet-stream
Size: 6657 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150128/cde0a5ae/attachment.obj>