This is an archive of the discontinued LLVM Phabricator instance.

[Verifier] Reject PHIs using definitions from own block.
ClosedPublic

Authored by Meinersbur on Mar 24 2016, 5:42 AM.

Details

Summary

Reject the following IR as malformed (assuming that %entry, %next are not in a loop):

next:
  %y = phi i32 [ 0, %entry ]
  %x = phi i32 [ %y, %entry ]

Such PHI nodes came up in PR26718. While there was no consensus on whether or not this is valid IR, most opinions on that bug and in a discussion on the llvm-dev mailing list tended towards a "strict interpretation" (term by Joseph Tremoulet) of PHI node uses. Also, the language reference explicitly states that "the use of each incoming value is deemed to occur on the edge from the corresponding predecessor block to the current block" and DominatorTree::dominates(Instruction*, Use&) uses this definition as well.

For the code mentioned in PR15384, clang does not compile to such PHIs (anymore?). The test case still hangs when replacing %tmp6 with %tmp in revisions before r176366 (where PR15384 has been fixed). The occurrence of %tmp6 therefore was probably unintentional. Its value is not used except in other PHIs.

Diff Detail

Repository
rL LLVM

Event Timeline

Meinersbur updated this revision to Diff 51542.Mar 24 2016, 5:42 AM
Meinersbur retitled this revision from to [Verifier] Reject PHIs using definitions from own block..
Meinersbur updated this object.
Meinersbur set the repository for this revision to rL LLVM.
Meinersbur added a subscriber: llvm-commits.
kparzysz edited edge metadata.Mar 24 2016, 8:54 AM

Looks good to me.

sanjoy added inline comments.Mar 24 2016, 1:37 PM
lib/IR/Verifier.cpp
3401 ↗(On Diff #51542)

I'd phrase this check a little differently, as:

bool FastDominanceCheck /* perhaps use a better name here */ = !isa<PHINode> && InstsInThisBlock.count(Op)
if (!FastDominanceCheck)
  Assert(DT.dominates(...));

to make it explicit that the lookup in InstsInThisBlock is a compile-time optimization.

test/Transforms/LoopVectorize/phi-hang.ll
3 ↗(On Diff #51542)

Was this test checking that loop vectorizer can deal with non-strict PHI nodes, or something else? If the latter, perhaps we should rewrite this test to check that?

Meinersbur updated this revision to Diff 51711.Mar 26 2016, 1:16 AM
Meinersbur updated this object.
Meinersbur edited edge metadata.
Meinersbur removed rL LLVM as the repository for this revision.

Restructured InstsInThisBlock as early exit; Reinserted the test case for PR15384 as it was probably just a typo.

Meinersbur added inline comments.Mar 26 2016, 1:24 AM
lib/IR/Verifier.cpp
3408 ↗(On Diff #51711)

I wasn't aware that InstsInThisBlock is just a speed optimization. I modeled it as an early exit without additional variable and explicit comment. Is that OK?

test/Transforms/LoopVectorize/phi-hang.ll
3 ↗(On Diff #51711)

I assumed it would be a test for non-strict phi nodes, the PR doesn't mention anything specific. So I looked up the commit message of r176366 which says:

LoopVectorize: Don't hang forever if a PHI only has skipped PHI uses.

so I changed %tmp6 to %tmp to see whether it still hangs in 176365 and it does. I am therefore assuming the %tmp6 was unintentional.

sanjoy accepted this revision.Mar 26 2016, 11:44 AM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/IR/Verifier.cpp
3402 ↗(On Diff #51711)

Nit: missing period.

test/Transforms/LoopVectorize/phi-hang.ll
3 ↗(On Diff #51711)

Great, thanks for doing all this!

This revision is now accepted and ready to land.Mar 26 2016, 11:44 AM
This revision was automatically updated to reflect the committed changes.