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

[Daniel Berlin]

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


On Wed Jan 28 2015 at 3:15:20 PM Daniel Berlin <dberlin at dberlin.org> wrote:

> 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/1e8a626b/attachment.html>