[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

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

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

3401–3406

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

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

Nit: missing period.

test/Transforms/LoopVectorize/phi-hang.ll

3

Great, thanks for doing all this!

lib/IR/Verifier.cpp

void Verifier::verifyDominatesUse(Instruction &I, unsigned i) {
   // 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;
   }
 
   const Use &U = I.getOperandUse(i);
+  if (isa<PHINode>(I))
+    Assert(DT.dominates(Op, U),
+           "Instruction does not dominate PHI node's incoming edge!", Op, &I);
+  else
     Assert(InstsInThisBlock.count(Op) || 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"
          " instructions, use attributes for calls or invokes", &I);

test/Transforms/LoopVectorize/phi-hang.ll

 ; RUN: opt -S -loop-vectorize < %s
 
-; PR15384
-define void @test1(i32 %arg) {
-bb:
-  br label %bb1
-
-bb1:                                              ; preds = %bb5, %bb
-  %tmp = phi i32 [ 1, %bb ], [ %tmp7, %bb5 ]
-  %tmp2 = phi i32 [ %arg, %bb ], [ %tmp9, %bb5 ]
-  br i1 true, label %bb5, label %bb3
-
-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 ]
-  %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
-}
-
 ; PR15748
 define void @test2() {
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb1, %bb
   %tmp = phi i32 [ 0, %bb ], [ %tmp5, %bb1 ]
   %tmp2 = phi i32 [ 0, %bb ], [ 1, %bb1 ]

test/Verifier/dominates.ll

bb0:
   %y1 = invoke i32 @g() to label %bb1 unwind label %bb2
 bb1:
   ret void
 bb2:
   %y2 = phi i32 [%y1, %bb0]
   %y3 = landingpad i32
           cleanup
   ret void
-; CHECK: Instruction does not dominate all uses!
+; CHECK: Instruction does not dominate PHI node's incoming edge!
 ; CHECK-NEXT:  %y1 = invoke i32 @g()
 ; CHECK-NEXT:        to label %bb1 unwind label %bb2
 ; CHECK-NEXT:  %y2 = phi i32 [ %y1, %bb0 ]
 }
 
 define void @f3(i32 %x) personality i32 ()* @g {
 bb0:
   %y1 = invoke i32 @g() to label %bb1 unwind label %bb2
 bb1:
   ret void
 bb2:
   %y2 = landingpad i32
           cleanup
   br label %bb3
 bb3:
   %y3 = phi i32 [%y1, %bb2]
   ret void
-; CHECK: Instruction does not dominate all uses!
+; CHECK: Instruction does not dominate PHI node's incoming edge!
 ; CHECK-NEXT:  %y1 = invoke i32 @g()
 ; CHECK-NEXT:          to label %bb1 unwind label %bb2
 ; CHECK-NEXT:  %y3 = phi i32 [ %y1, %bb2 ]
 }
 
 define void @f4(i32 %x) {
 bb0:
   br label %bb1
 bb1:
   %y3 = phi i32 [%y1, %bb0]
   %y1 = add i32 %x, 1
   ret void
-; CHECK: Instruction does not dominate all uses!
+; CHECK: Instruction does not dominate PHI node's incoming edge!
 ; 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 PHI node's incoming edge!
+; CHECK-NEXT:  %y = phi i32 [ 0, %entry ]
+; CHECK-NEXT:  %x = phi i32 [ %y, %entry ]
+}