llvm dev - Jan 2015 - [LLVMdev] [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)

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>

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>

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>