[SCEV] Fix crash in checking the identical of PHI nodes

[Allen]

Summary

With the commit 20d798b, we generate the node %val_i1_62.lcssa1, which has different
incoming values for the same basic block. But in fact, the two incoming values are equal,
so they should be allowed, eg:

  %val_i1_62.lcssa1 = phi i1 [ %val_i1_52.lcssa2, %bb_3 ], [ %val_i1_52.lcssa3, %bb_3 ]
label %bb_3
  %val_i1_52.lcssa3 = phi i1 [ %val_i1_52, %bb_2 ]
  %val_i1_52.lcssa2 = phi i1 [ %val_i1_52, %bb_2 ]

Fixes https://github.com/llvm/llvm-project/issues/57000

[fhahn]

Unfortunately I don't think this is the right fix, as we might end up with scenarios where we end up with chains of phis we need to look through. Indvars shouldn't create those redundant phi nodes if possible.

llvm/lib/IR/Verifier.cpp

for (auto &I : BB) {
       if (auto MD = I.getMetadata(LLVMContext::MD_loop))
         for (unsigned i = 1; i < MD->getNumOperands(); ++i)
           VisitDebugLoc(I, dyn_cast_or_null<MDNode>(MD->getOperand(i)));
       if (BrokenDebugInfo)
         return;
     }
 }
 
+bool isEqualValue(Value *S1, Value *S2) {
+  if (S1 == S2)
+    return true;
+
+  if (isa<PHINode>(S1) && isa<PHINode>(S2)) {
+    const PHINode *PN1 = cast<PHINode>(S1);
+    const PHINode *PN2 = cast<PHINode>(S2);
+    if (PN1->getNumIncomingValues() == PN2->getNumIncomingValues()) {
+      for (unsigned i = 0; i < PN1->getNumIncomingValues(); i++) {
+        if ((PN1->getIncomingValue(i) != PN2->getIncomingValue(i)) ||
+            (PN1->getIncomingBlock(i) != PN2->getIncomingBlock(i)))
+          return false;
+      }
+      return true;
+    }
+  }
+
+  return false;
+}
+
 // verifyBasicBlock - Verify that a basic block is well formed...
 //
 void Verifier::visitBasicBlock(BasicBlock &BB) {
   InstsInThisBlock.clear();
 
   // Ensure that basic blocks have terminators!
   Check(BB.getTerminator(), "Basic Block does not have terminator!", &BB);
 
for (const PHINode &PN : BB.phis()) {
       llvm::sort(Values);
 
       for (unsigned i = 0, e = Values.size(); i != e; ++i) {
         // Check to make sure that if there is more than one entry for a
         // particular basic block in this PHI node, that the incoming values are
         // all identical.
         //
         Check(i == 0 || Values[i].first != Values[i - 1].first ||
-                  Values[i].second == Values[i - 1].second,
+                  isEqualValue(Values[i].second, Values[i - 1].second),
               "PHI node has multiple entries for the same basic block with "
               "different incoming values!",
               &PN, Values[i].first, Values[i].second, Values[i - 1].second);
 
         // Check to make sure that the predecessors and PHI node entries are
         // matched up.
         Check(Values[i].first == Preds[i],
               "PHI node entries do not match predecessors!", &PN,

llvm/test/Analysis/ScalarEvolution/pr57000.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -indvars -S | FileCheck %s
+
+; Check that it does not crash because the incoming values are equal.
+
+define void @pr57000() {
+; CHECK-LABEL: @pr57000(
+; CHECK-NEXT:  entry_1:
+; CHECK-NEXT:    br label [[BB_2_OUTER:%.*]]
+; CHECK:       bb_2.loopexit:
+; CHECK-NEXT:    br label [[BB_2_OUTER]]
+; CHECK:       bb_2.outer:
+; CHECK-NEXT:    br label [[BB_2:%.*]]
+; CHECK:       bb_2:
+; CHECK-NEXT:    [[VAL_I1_52:%.*]] = icmp sle i64 undef, 2546175499358690212
+; CHECK-NEXT:    br i1 false, label [[BB_2]], label [[BB_3_PREHEADER:%.*]]
+; CHECK:       bb_3.preheader:
+; CHECK-NEXT:    [[VAL_I1_52_LCSSA3:%.*]] = phi i1 [ [[VAL_I1_52]], [[BB_2]] ]
+; CHECK-NEXT:    [[VAL_I1_52_LCSSA2:%.*]] = phi i1 [ [[VAL_I1_52]], [[BB_2]] ]
+; CHECK-NEXT:    br label [[BB_3_OUTER:%.*]]
+; CHECK:       bb_3.outer:
+; CHECK-NEXT:    br label [[BB_3:%.*]]
+; CHECK:       bb_3:
+; CHECK-NEXT:    switch i16 undef, label [[BB_2_LOOPEXIT:%.*]] [
+; CHECK-NEXT:    i16 -1, label [[BB_4:%.*]]
+; CHECK-NEXT:    i16 1, label [[BB_4]]
+; CHECK-NEXT:    i16 4, label [[BB_3]]
+; CHECK-NEXT:    ]
+; CHECK:       bb_4:
+; CHECK-NEXT:    [[VAL_I1_62_LCSSA1:%.*]] = phi i1 [ [[VAL_I1_52_LCSSA2]], [[BB_3]] ], [ [[VAL_I1_52_LCSSA3]], [[BB_3]] ]
+; CHECK-NEXT:    [[VAL_I1_77:%.*]] = icmp ult i1 [[VAL_I1_62_LCSSA1]], undef
+; CHECK-NEXT:    br label [[BB_3_OUTER]]
+;
+entry_1:
+  br label %bb_2
+
+bb_2:                                             ; preds = %bb_3, %bb_2, %entry_1
+  %ptr_i1_13.0 = phi i1 [ undef, %entry_1 ], [ %ptr_i1_13.0, %bb_2 ], [ %ptr_i1_13.1, %bb_3 ]
+  %val_i1_52 = icmp sle i64 undef, 2546175499358690212
+  %val_i8_56 = zext i1 %val_i1_52 to i8
+  br i1 undef, label %bb_2, label %bb_3
+
+bb_3:                                             ; preds = %bb_4, %bb_3, %bb_2
+  %ptr_i1_13.1 = phi i1 [ %ptr_i1_13.0, %bb_2 ], [ %ptr_i1_13.1, %bb_3 ], [ %val_i1_52, %bb_4 ]
+  %val_i1_62 = trunc i8 %val_i8_56 to i1
+  switch i16 undef, label %bb_2 [
+  i16 -1, label %bb_4
+  i16 1, label %bb_4
+  i16 4, label %bb_3
+  ]
+
+bb_4:                                             ; preds = %bb_3, %bb_3
+  %val_i1_77 = icmp ult i1 %val_i1_62, undef
+  br label %bb_3
+}