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

[Philip Reames]

LGTM.  Nice find.

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

Philip

On 01/28/2015 03:15 PM, Daniel Berlin 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.
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150128/95f8a9be/attachment.html>