[Verifier] Reject PHIs using definitions from own block.

[Meinersbur]

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.

[kparzysz]

Looks good to me.

[sanjoy]

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]

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

[Meinersbur]

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]

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!

llvm/trunk/lib/IR/Verifier.cpp

void Verifier::verifyDominatesUse(Instruction &I, unsigned i) {
   // If the we have an invalid invoke, don't try to compute the dominance.
   // We already reject it in the invoke specific checks and the dominance
   // computation doesn't handle multiple edges.
   if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
     if (II->getNormalDest() == II->getUnwindDest())
       return;
   }
 
+  // Quick check whether the def has already been encountered in the same block.
+  // PHI nodes are not checked to prevent accepting preceeding PHIs, because PHI
+  // uses are defined to happen on the incoming edge, not at the instruction.
+  if (!isa<PHINode>(I) && InstsInThisBlock.count(Op))
+    return;
+
   const Use &U = I.getOperandUse(i);
-  Assert(InstsInThisBlock.count(Op) || DT.dominates(Op, U),
+  Assert(DT.dominates(Op, U),
          "Instruction does not dominate all uses!", Op, &I);
 }
 
 void Verifier::visitDereferenceableMetadata(Instruction& I, MDNode* MD) {
   Assert(I.getType()->isPointerTy(), "dereferenceable, dereferenceable_or_null "
          "apply only to pointer types", &I);
   Assert(isa<LoadInst>(I),
          "dereferenceable, dereferenceable_or_null apply only to load"

llvm/trunk/test/Transforms/LoopVectorize/phi-hang.ll

 bb3:                                              ; preds = %bb1
   br label %bb4
 
 bb4:                                              ; preds = %bb3
   br label %bb5
 
 bb5:                                              ; preds = %bb4, %bb1
   %tmp6 = phi i32 [ 0, %bb4 ], [ %tmp, %bb1 ]
-  %tmp7 = phi i32 [ 0, %bb4 ], [ %tmp6, %bb1 ]
+  %tmp7 = phi i32 [ 0, %bb4 ], [ %tmp, %bb1 ]
   %tmp8 = phi i32 [ 0, %bb4 ], [ %tmp, %bb1 ]
   %tmp9 = add nsw i32 %tmp2, 1
   %tmp10 = icmp eq i32 %tmp9, 0
   br i1 %tmp10, label %bb11, label %bb1
 
 bb11:                                             ; preds = %bb5
   ret void
 }

llvm/trunk/test/Verifier/dominates.ll

 bb1:
   %y3 = phi i32 [%y1, %bb0]
   %y1 = add i32 %x, 1
   ret void
 ; CHECK: Instruction does not dominate all uses!
 ; CHECK-NEXT:  %y1 = add i32 %x, 1
 ; CHECK-NEXT:  %y3 = phi i32 [ %y1, %bb0 ]
 }
+
+define void @f5() {
+entry:
+  br label %next
+
+next:
+  %y = phi i32 [ 0, %entry ]
+  %x = phi i32 [ %y, %entry ]
+  ret void
+; CHECK: Instruction does not dominate all uses!
+; CHECK-NEXT:  %y = phi i32 [ 0, %entry ]
+; CHECK-NEXT:  %x = phi i32 [ %y, %entry ]
+}