[LLVMdev] [PATCH]: Allow PRE to insert no-cost phi nodes (original) (raw)

Daniel Berlin dberlin at dberlin.org
Wed Jan 28 15:15:20 PST 2015

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>