Index: llvm/lib/Transforms/Utils/LoopUtils.cpp
===================================================================
--- llvm/lib/Transforms/Utils/LoopUtils.cpp
+++ llvm/lib/Transforms/Utils/LoopUtils.cpp
@@ -1212,11 +1212,11 @@
 struct RewritePhi {
   PHINode *PN;
   unsigned Ith;   // Ith incoming value.
+  BasicBlock *BB; // Basic block for this value.
   Value *Val;     // Exit value after expansion.
-  bool HighCost;  // High Cost when expansion.
 
-  RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
-      : PN(P), Ith(I), Val(V), HighCost(H) {}
+  RewritePhi(PHINode *P, unsigned I, BasicBlock *B, Value *V)
+      : PN(P), Ith(I), BB(B), Val(V) {}
 };
 
 // Check whether it is possible to delete the loop after rewriting exit
@@ -1287,6 +1287,8 @@
   L->getUniqueExitBlocks(ExitBlocks);
 
   SmallVector<RewritePhi, 8> RewritePhiSet;
+  SmallSet<std::pair<PHINode*, BasicBlock*>, 8> HighCostPhiPreds;
+
   // Find all values that are computed inside the loop, but used outside of it.
   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
   // the exit blocks of the loop to find them.
@@ -1322,8 +1324,10 @@
         if (!isa<Instruction>(InVal))
           continue;
 
+        BasicBlock *BB = PN->getIncomingBlock(i);
+
         // If this pred is for a subloop, not L itself, skip it.
-        if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
+        if (LI->getLoopFor(BB) != L)
           continue; // The Block is in a subloop, skip it.
 
         // Check that InVal is defined in the loop.
@@ -1390,7 +1394,9 @@
 #endif
 
         // Collect all the candidate PHINodes to be rewritten.
-        RewritePhiSet.emplace_back(PN, i, ExitVal, HighCost);
+        RewritePhiSet.emplace_back(PN, i, BB, ExitVal);
+        if (HighCost)
+          HighCostPhiPreds.insert(std::make_pair(PN, BB));
       }
     }
   }
@@ -1402,10 +1408,12 @@
   for (const RewritePhi &Phi : RewritePhiSet) {
     PHINode *PN = Phi.PN;
     Value *ExitVal = Phi.Val;
+    BasicBlock *BB = Phi.BB;
 
     // Only do the rewrite when the ExitValue can be expanded cheaply.
     // If LoopCanBeDel is true, rewrite exit value aggressively.
-    if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
+    if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel &&
+        HighCostPhiPreds.count(std::make_pair(PN, BB))) {
       DeadInsts.push_back(ExitVal);
       continue;
     }
Index: llvm/test/Transforms/IndVarSimplify/pr45835.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/IndVarSimplify/pr45835.ll
@@ -0,0 +1,39 @@
+; RUN: opt < %s -indvars -replexitval=always -S | FileCheck %s --check-prefix=ALWAYS
+; RUN: opt < %s -indvars -replexitval=never -S | FileCheck %s --check-prefix=NEVER
+; RUN: opt < %s -indvars -replexitval=cheap -S | FileCheck %s --check-prefix=CHEAP
+; rewriteLoopExitValues must rewrite all or none of a PHI's values from a given
+; block, even if they have different costs.
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+@a = common global i8 0, align 1
+
+define internal fastcc void @d(i8* %c) unnamed_addr #0 {
+entry:
+  %cmp = icmp ule i8* %c, getelementptr inbounds (i8, i8* @a, i64 65535)
+  %add.ptr = getelementptr inbounds i8, i8* %c, i64 -65535
+  br label %while.cond
+
+while.cond:
+  br i1 icmp ne (i8 0, i8 0), label %cont, label %while.end
+
+cont:
+  %a.mux = select i1 %cmp, i8* @a, i8* %add.ptr
+  switch i64 0, label %while.cond [
+    i64 -1, label %handler.pointer_overflow.i
+    i64 0, label %handler.pointer_overflow.i
+  ]
+
+handler.pointer_overflow.i:
+  %a.mux.lcssa4 = phi i8* [ %a.mux, %cont ], [ %a.mux, %cont ]
+; ALWAYS: [ %scevgep, %cont ], [ %scevgep, %cont ]
+; NEVER: [ %a.mux, %cont ], [ %a.mux, %cont ]
+; In cheap mode, use either one as long as it's consistent.
+; CHEAP: [ %[[VAL:.*]], %cont ], [ %[[VAL]], %cont ]
+  %x5 = ptrtoint i8* %a.mux.lcssa4 to i64
+  br label %while.end
+
+while.end:
+  ret void
+}
+