[llvm-bugs] [Bug 32403] New: NewGVN will fail to fixpoint on some phis with undef

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=32403

            Bug ID: 32403
           Summary: NewGVN will fail to fixpoint on some phis with undef
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: dberlin at dberlin.org
                CC: llvm-bugs at lists.llvm.org

Created attachment 18162
  --> https://bugs.llvm.org/attachment.cgi?id=18162&action=edit
undef strikes again.ll

The attached will cause newgvn to infinite loop due to undef in a phi.

It requires a very unfortunate series of events.

We use the same check for whether we can use undef in a phi node as simplify*,
and we need to extend it, it turns out.

Here is what happens:

We have a dom tree that looks like this:

  A
 / \
B   C
| 
..

Note that the first requirement is that B not dominate C and C not dominate B.
We also must visit C before B in RPO (note that here, either could be chosen as
the second block in RPO)

Next, in B and C there are two instructions that end up in the same congruence
class.
We visit C first, so the one in C becomes the leader.

The phi nodes eventually resolve to the instruction in B, which, if you look up
the leader, you get the one in C.

On the next iteration:
    // We also special case undef, so that if we have an undef, we can't use
the
    // common value unless it dominates the phi block.
  if (HasUndef) {
      // Only have to check for instructions
      if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
        if (!DT->dominates(AllSameInst, I))
           return E;

The instruction  in B dominates the phis, but the instruction in C does not.

So we dutily say "whoops, can't value number this phi to this value"
Which resets the resolution of the phi node cycles.
Which starts again, and gets the same result.

I believe the correct check here is in fact, "does any member of the class of
AllSameInst dominate I"
Since we only would replace it with a member that dominates that phis anyway,
this should be correct.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20170324/5ec47f74/attachment.html>