[IndVars] Fix corner case with unreachable Phi inputs. PR40454

[mkazantsev]

Summary

Logic in getInsertPointForUses doesn't account for a corner case when Def only
comes to a Phi user from unreachable blocks. In this case, the incoming value may
be arbitrary (and not even available in the input block) and break the loop-related
invariants that are asserted below.

In fact, if we encounter this situation, no IR modification is needed. This Phi will be
simplified away with nearest cleanup.

[spatel]

I'm not familiar with this code, but the change is strictly safer, so LGTM.
You may want to wait a bit before committing in case there are any other comments.

[mkazantsev]

Moved print after check.

llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp

if (FromPtr != FromVal || ToPtr != ToVal) {
     return false;
   }
   return true;
 }
 
 /// Determine the insertion point for this user. By default, insert immediately
 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
-/// common dominator for the incoming blocks.
+/// common dominator for the incoming blocks. A nullptr can be returned if no
+/// viable location is found: it may happen if User is a PHI and Def only comes
+/// to this PHI from unreachable blocks.
 static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
                                           DominatorTree *DT, LoopInfo *LI) {
   PHINode *PHI = dyn_cast<PHINode>(User);
   if (!PHI)
     return User;
 
   Instruction *InsertPt = nullptr;
   for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
     if (PHI->getIncomingValue(i) != Def)
       continue;
 
     BasicBlock *InsertBB = PHI->getIncomingBlock(i);
+
+    if (!DT->isReachableFromEntry(InsertBB))
+      continue;
+
     if (!InsertPt) {
       InsertPt = InsertBB->getTerminator();
       continue;
     }
     InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
     InsertPt = InsertBB->getTerminator();
   }
-  assert(InsertPt && "Missing phi operand");
+
+  // If we have skipped all inputs, it means that Def only comes to Phi from
+  // unreachable blocks.
+  if (!InsertPt)
+    return nullptr;
 
   auto *DefI = dyn_cast<Instruction>(Def);
   if (!DefI)
     return InsertPt;
 
   assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
 
   auto *L = LI->getLoopFor(DefI->getParent());
WidenIV::WidenedRecTy WidenIV::getWideRecurrence(NarrowIVDefUse DU) {
   if (!AddRec || AddRec->getLoop() != L)
     return {nullptr, Unknown};
   return {AddRec, ExtKind};
 }
 
 /// This IV user cannot be widen. Replace this use of the original narrow IV
 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
 static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI) {
+  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
+  if (!InsertPt)
+    return;
   LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
                     << *DU.NarrowUse << "\n");
-  IRBuilder<> Builder(
-      getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
+  IRBuilder<> Builder(InsertPt);
   Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
   DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
 }
 
 /// If the narrow use is a compare instruction, then widen the compare
 //  (and possibly the other operand).  The extend operation is hoisted into the
 // loop preheader as far as possible.
 bool WidenIV::widenLoopCompare(NarrowIVDefUse DU) {
if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
     return false;
 
   Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
   unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
   unsigned IVWidth = SE->getTypeSizeInBits(WideType);
   assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
 
   // Widen the compare instruction.
-  IRBuilder<> Builder(
-      getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
+  auto *InsertPt = getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI);
+  if (!InsertPt)
+    return false;
+  IRBuilder<> Builder(InsertPt);
   DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
 
   // Widen the other operand of the compare, if necessary.
   if (CastWidth < IVWidth) {
     Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
     DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
   }
   return true;

llvm/trunk/test/Transforms/IndVarSimplify/pr40454.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -indvars  < %s | FileCheck %s
-; REQUIRES: asserts
-; XFAIL: *
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @test() {
-; CHECK-LABEL: @test
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ -9, [[BB:%.*]] ], [ [[TMP6:%.*]], [[BB1:%.*]] ]
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ -9, [[BB2]] ], [ [[TMP6]], [[BB10:%.*]] ]
+; CHECK-NEXT:    br i1 false, label [[BB5:%.*]], label [[BB12:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[TMP6]] = add nsw i32 [[TMP4]], -1
+; CHECK-NEXT:    br i1 undef, label [[BB8:%.*]], label [[BB9:%.*]]
+; CHECK:       bb8:
+; CHECK-NEXT:    br label [[BB10]]
+; CHECK:       bb9:
+; CHECK-NEXT:    br label [[BB10]]
+; CHECK:       bb10:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb12:
+; CHECK-NEXT:    ret void
+;
 
 bb:
   br label %bb2
 
 bb1:                                              ; No predecessors!
   br label %bb2
 
 bb2:                                              ; preds = %bb1, %bb