Index: include/llvm/ADT/STLExtras.h
===================================================================
--- include/llvm/ADT/STLExtras.h
+++ include/llvm/ADT/STLExtras.h
@@ -859,6 +859,17 @@
          std::end(Range);
 }
 
+/// Wrapper function around std::lower_bound to detect if an element
+/// exists in a container via binary search.  The same requirements as
+/// for std::lower_bound (that is: Range must be partially ordered,
+/// with respect to the expression Element < Value for Value in Range)
+/// applies here.
+template <typename R, typename E>
+bool binary_search(R &&Range, const E &Element) {
+  auto It = std::lower_bound(std::begin(Range), std::end(Range), Element);
+  return It != std::end(Range) && *It == Element;
+}
+
 /// Wrapper function around std::count to count the number of times an element
 /// \p Element occurs in the given range \p Range.
 template <typename R, typename E>
Index: lib/Transforms/Scalar/IndVarSimplify.cpp
===================================================================
--- lib/Transforms/Scalar/IndVarSimplify.cpp
+++ lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -30,6 +30,7 @@
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
@@ -2136,6 +2137,67 @@
   }
 }
 
+/// We want to insert a branch on IV on the backedge of L.  Return true if we
+/// can legally do that (branching on poison is undefined behavior), modifying
+/// instructions if necessary.
+static bool makeValueNonPoisonOnBackEdge(Instruction *IV, Loop *L) {
+  auto IVNeverPoison = isIVNeverPoison(IV, L);
+  if (IVNeverPoison.first)
+    return true;
+
+  Instruction *PoisonGenerator =
+      const_cast<Instruction *>(IVNeverPoison.second);
+
+  // If PoisonGenerator is non-null then we can call
+  // dropPoisonGeneratingFlags on it to make IV not poison.  However,
+  // let's first check if we can avoid dropping no-wrap flags at all.
+
+  Value *BECond = nullptr;
+  auto *LatchTerminator = L->getLoopLatch()->getTerminator();
+  if (auto *BI = dyn_cast<BranchInst>(LatchTerminator)) {
+    if (BI->isConditional())
+      BECond = dyn_cast<Instruction>(BI->getCondition());
+  } else if (auto *SI = dyn_cast<SwitchInst>(LatchTerminator)) {
+    BECond = dyn_cast<Instruction>(SI->getCondition());
+  }
+
+  if (BECond) {
+    auto InLoop = [&](const Value *V) {
+      auto *I = dyn_cast<Instruction>(V);
+      return I && L->contains(I);
+    };
+
+    // We know that at the backedge we will branch on BECond, which in turn
+    // means that BECond itself is not poison.  See if that knowledge amounts to
+    // something.
+    SmallVector<const Value *, 8> NotPoison;
+    propagateKnownNonPoison(BECond, NotPoison, InLoop);
+
+    array_pod_sort(NotPoison.begin(), NotPoison.end());
+
+    if (binary_search(NotPoison, IV))
+      return true;
+
+    auto IsNonPoison = [&](Value *V) {
+      return isa<ConstantInt>(V) || binary_search(NotPoison, V);
+    };
+
+    if (all_of(IV->operands(), IsNonPoison)) {
+      // All of the inputs to IV are non-poison.  This means I can make IV
+      // non-poison by preventing it from generating *new* poison.
+      IV->dropPoisonGeneratingFlags();
+      return true;
+    }
+  }
+
+  if (PoisonGenerator) {
+    PoisonGenerator->dropPoisonGeneratingFlags();
+    return true;
+  }
+
+  return false;
+}
+
 /// This method rewrites the exit condition of the loop to be a canonical !=
 /// comparison against the incremented loop induction variable.  This pass is
 /// able to rewrite the exit tests of any loop where the SCEV analysis can
@@ -2149,7 +2211,7 @@
   assert(canExpandBackedgeTakenCount(L, SE, Rewriter) && "precondition");
 
   // Initialize CmpIndVar and IVCount to their preincremented values.
-  Value *CmpIndVar = IndVar;
+  Instruction *CmpIndVar = IndVar;
   const SCEV *IVCount = BackedgeTakenCount;
 
   assert(L->getLoopLatch() && "Loop no longer in simplified form?");
@@ -2166,9 +2228,16 @@
     // The BackedgeTaken expression contains the number of times that the
     // backedge branches to the loop header.  This is one less than the
     // number of times the loop executes, so use the incremented indvar.
-    CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock());
+    CmpIndVar = cast<Instruction>(
+        IndVar->getIncomingValueForBlock(L->getExitingBlock()));
   }
 
+  // In general, we cannot introduce a branch on poison where there
+  // wasn't one before.  Try a variety of tricks to see if branching
+  // on CmpIndVar can be made legal.
+  if (!makeValueNonPoisonOnBackEdge(CmpIndVar, L))
+    return nullptr;
+
   Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE);
   assert(ExitCnt->getType()->isPointerTy() ==
              IndVar->getType()->isPointerTy() &&
@@ -2253,8 +2322,8 @@
       }
 
       if (!Extended)
-        CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(),
-                                        "lftr.wideiv");
+        CmpIndVar = cast<Instruction>(
+            Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(), "lftr.wideiv"));
     }
   }
   Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond");
Index: test/Transforms/IndVarSimplify/PR31181.ll
===================================================================
--- /dev/null
+++ test/Transforms/IndVarSimplify/PR31181.ll
@@ -0,0 +1,114 @@
+; RUN: opt -S -indvars < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @f_0(i32* %ptr) {
+; CHECK-LABEL: @f_0(
+; CHECK: for.cond:
+; CHECK:    %iv = phi i32 [ -2, %entry ], [ %iv.inc, %for.cond ]
+; CHECK:    %iv.inc = add i32 %iv, 1
+; CHECK:    %exitcond = icmp ne i32 %iv.inc, 0
+; CHECK:    br i1 %exitcond, label %for.cond, label %for.end
+;
+entry:
+  br label %for.cond
+
+for.cond:
+  %iv = phi i32 [ -2, %entry ], [ %iv.inc, %for.cond ]
+  store i32 %iv, i32* %ptr
+  %cmp = icmp slt i32 %iv, -1
+  %iv.inc = add nuw nsw i32 %iv, 1
+  br i1 %cmp, label %for.cond, label %for.end
+
+for.end:
+  ret i32 0
+}
+
+define i32 @f_1(i32* %ptr, i1 %always_false) {
+; CHECK-LABEL: @f_1(
+; CHECK: always_taken:
+; CHECK:   %iv.inc = add nsw i32 %iv, 1
+; CHECK:   %iv2.inc = add i32 %iv2, 1
+; CHECK:   %exitcond = icmp ne i32 %iv2.inc, -2147483627
+; CHECK:   br i1 %exitcond, label %for.cond, label %for.end
+
+entry:
+  br label %for.cond
+
+for.cond:
+  %iv = phi i32 [ -2147483648, %entry ], [ %iv.inc, %always_taken ]
+  %iv2 = phi i32 [ 0, %entry ], [ %iv2.inc, %always_taken ]
+  store i32 %iv, i32* %ptr
+  br i1 %always_false, label %never_taken, label %always_taken
+
+never_taken:
+  store volatile i32 %iv2, i32* %ptr
+  br label %always_taken
+
+always_taken:
+  %iv.inc = add nsw i32 %iv, 1
+  %iv2.inc = add nsw i32 %iv2, 1
+  %cmp = icmp slt i32 %iv, 20
+  br i1 %cmp, label %for.cond, label %for.end
+
+for.end:
+  ret i32 0
+}
+
+define i32 @f_2(i32* %ptr, i1 %always_false) {
+; CHECK-LABEL: @f_2(
+; CHECK: always_taken:
+; CHECK:  %iv.inc = add nuw nsw i32 %iv, 1
+; CHECK:  %exitcond = icmp ne i32 %iv.inc, 25
+; CHECK:  br i1 %exitcond, label %for.cond, label %for.end
+
+entry:
+  br label %for.cond
+
+for.cond:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %always_taken ]
+  store i32 %iv, i32* %ptr
+  br i1 %always_false, label %never_taken, label %always_taken
+
+never_taken:
+  store volatile i32 %iv, i32* %ptr
+  br label %always_taken
+
+always_taken:
+  %iv.inc = add nuw nsw i32 %iv, 1
+  %iv.offset = add i32 %iv.inc, -5
+  %cmp = icmp slt i32 %iv.offset, 20
+  br i1 %cmp, label %for.cond, label %for.end
+
+for.end:
+  ret i32 0
+}
+
+define i32 @f_3(i32* %ptr, i1 %always_false) {
+; CHECK-LABEL: @f_3(
+; CHECK: always_taken:
+; CHECK:   %iv.inc = add i32 %iv, 1
+; CHECK:   %exitcond = icmp ne i32 %iv.inc, 21
+; CHECK:   br i1 %exitcond, label %for.cond, label %for.end
+
+entry:
+  br label %for.cond
+
+for.cond:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %always_taken ]
+  store i32 %iv, i32* %ptr
+  br i1 %always_false, label %never_taken, label %always_taken
+
+never_taken:
+  store volatile i32 %iv, i32* %ptr
+  br label %always_taken
+
+always_taken:
+  %iv.inc = add nuw nsw i32 %iv, 1
+  %cmp = icmp slt i32 %iv, 20
+  br i1 %cmp, label %for.cond, label %for.end
+
+for.end:
+  ret i32 0
+}
Index: test/Transforms/IndVarSimplify/widen-nsw.ll
===================================================================
--- test/Transforms/IndVarSimplify/widen-nsw.ll
+++ test/Transforms/IndVarSimplify/widen-nsw.ll
@@ -3,7 +3,7 @@
 target triple = "x86_64-apple-macosx"
 
 ; CHECK-LABEL: @test1
-; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+; CHECK: %indvars.iv.next = add i64 %indvars.iv, 1
 define i32 @test1(i32* %a) #0 {
 entry:
   br label %for.cond