diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h
--- a/llvm/include/llvm/InitializePasses.h
+++ b/llvm/include/llvm/InitializePasses.h
@@ -90,6 +90,7 @@
 void initializeBreakCriticalEdgesPass(PassRegistry&);
 void initializeBreakFalseDepsPass(PassRegistry&);
 void initializeCanonicalizeAliasesLegacyPassPass(PassRegistry &);
+void initializeCanonicalizeFreezeInLoopsPass(PassRegistry&);
 void initializeCFGOnlyPrinterLegacyPassPass(PassRegistry&);
 void initializeCFGOnlyViewerLegacyPassPass(PassRegistry&);
 void initializeCFGPrinterLegacyPassPass(PassRegistry&);
diff --git a/llvm/include/llvm/Transforms/Utils.h b/llvm/include/llvm/Transforms/Utils.h
--- a/llvm/include/llvm/Transforms/Utils.h
+++ b/llvm/include/llvm/Transforms/Utils.h
@@ -134,6 +134,14 @@
 // exit blocks.
 //
 FunctionPass *createUnifyLoopExitsPass();
+
+//===----------------------------------------------------------------------===//
+//
+// CanonicalizeFreezeInLoops - Canonicalize freeze instructions in loops so they
+// don't block SCEV.
+//
+Pass *createCanonicalizeFreezeInLoopsPass();
+
 }
 
 #endif
diff --git a/llvm/include/llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h b/llvm/include/llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h
new file mode 100644
--- /dev/null
+++ b/llvm/include/llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h
@@ -0,0 +1,32 @@
+//==- CanonicalizeFreezeInLoop.h - Canonicalize freezes in a loop-*- C++ -*-==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file canonicalizes freeze instructions in a loop.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CANONICALIZE_FREEZES_IN_LOOPS_H
+#define LLVM_TRANSFORMS_UTILS_CANONICALIZE_FREEZES_IN_LOOPS_H
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+
+namespace llvm {
+
+/// A pass that canonicalizes freeze instructions in a loop.
+class CanonicalizeFreezeInLoopsPass
+    : public PassInfoMixin<CanonicalizeFreezeInLoopsPass> {
+public:
+  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CANONICALIZE_FREEZES_IN_LOOPS_H
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/lib/Passes/PassBuilder.cpp
@@ -178,6 +178,7 @@
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
+#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
 #include "llvm/Transforms/Utils/InjectTLIMappings.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -311,6 +311,7 @@
 #ifndef LOOP_PASS
 #define LOOP_PASS(NAME, CREATE_PASS)
 #endif
+LOOP_PASS("canon-freeze", CanonicalizeFreezeInLoopsPass())
 LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 LOOP_PASS("licm", LICMPass())
 LOOP_PASS("loop-idiom", LoopIdiomRecognizePass())
diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt
--- a/llvm/lib/Transforms/Utils/CMakeLists.txt
+++ b/llvm/lib/Transforms/Utils/CMakeLists.txt
@@ -10,6 +10,7 @@
   CallPromotionUtils.cpp
   CallGraphUpdater.cpp
   CanonicalizeAliases.cpp
+  CanonicalizeFreezeInLoops.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CodeExtractor.cpp
diff --git a/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp b/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/lib/Transforms/Utils/CanonicalizeFreezeInLoops.cpp
@@ -0,0 +1,420 @@
+//==- CanonicalizeFreezeInLoops - Canonicalize freezes in a loop-*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass canonicalizes freeze instructions in a loop by pushing them out to
+// the preheader.
+//
+//   loop:
+//     i = phi init, i.next
+//     i.next = add nsw i, 1
+//     i.add2 = add nsw i, 2
+//     i.add2.fr = freeze i.add2 // push this out of this loop
+//     br i1 (i.add2.fr <= N), loop, exit
+//   =>
+//     init.fr = freeze init
+//   loop:
+//     i = phi init.fr, i.next
+//     i.next = add i, 1         // nsw is dropped here
+//     i.add2 = add i, 2         // nsw is dropped here, too
+//     br i1 (i.add2 <= N), loop, exit
+//
+// Removing freezes from these chains help scalar evolution successfully analyze
+// expressions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/IVUsers.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils.h"
+#include <map>
+#include <queue>
+
+using namespace llvm;
+using namespace PatternMatch;
+
+#define DEBUG_TYPE "canon-freeze"
+
+namespace {
+
+class CanonicalizeFreezeInLoops : public LoopPass {
+public:
+  static char ID;
+
+  CanonicalizeFreezeInLoops();
+
+private:
+  bool runOnLoop(Loop *L, LPPassManager &LPM) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+class CanonicalizeFreezeInLoopsImpl {
+private:
+  Loop *L;
+  ScalarEvolution &SE;
+  DominatorTree &DT;
+  const unsigned MaxDepth = 6;
+
+  bool isKnownHowToDropFlags(Instruction *I) {
+    auto Opc = I->getOpcode();
+    // If add/sub/mul, drop nsw/nuw flags.
+    // TODO: support more instructions
+    return Opc == Instruction::Add || Opc == Instruction::Sub ||
+           Opc == Instruction::Mul;
+  }
+
+  // Returns <step instruction, step value operand idx>
+  std::pair<BinaryOperator *, unsigned> getStepInstFrom(PHINode *PHI) {
+    auto *StepInst = dyn_cast<BinaryOperator>(
+        PHI->getIncomingValueForBlock(L->getLoopLatch()));
+    if (!StepInst ||
+        !(StepInst->getOperand(0) == PHI || StepInst->getOperand(1) == PHI) ||
+        !isKnownHowToDropFlags(StepInst)) {
+      // Don't know how to push freeze into this step instruction.
+      return {nullptr, 0};
+    }
+    return {StepInst, StepInst->getOperand(0) == PHI};
+  }
+
+  void getReachableInstsInsideLoop(
+      Instruction *I,
+      std::map<Instruction *, SmallSet<Instruction *, 4>> &ReachableInsts,
+      unsigned CurDepth = 0);
+
+  void getInstsReachableFromPHI(
+      PHINode &PHI, std::map<Instruction *, SmallSet<Instruction *, 4>> &FIs);
+
+  bool CollectUsesToFreezeAndInstsToDropFlags(
+      const std::map<Instruction *, SmallSet<Instruction *, 4>> &InstsFromPHIs,
+      const SmallSet<PHINode *, 4> &PHIs, FreezeInst *FI,
+      SmallVector<Use *, 4> &UsesToInsertFreeze,
+      SmallSet<Instruction *, 4> &InstsToDropFlags);
+
+  void InsertFreezeAndForgetFromSCEV(Use &U);
+
+public:
+  CanonicalizeFreezeInLoopsImpl(Loop *L, ScalarEvolution &SE, DominatorTree &DT)
+      : L(L), SE(SE), DT(DT) {}
+  bool run();
+};
+
+} // anonymous namespace
+
+// Given I, find instructions in L that are reachable from I and known how to
+// drop flags.
+void CanonicalizeFreezeInLoopsImpl::getReachableInstsInsideLoop(
+    Instruction *I,
+    std::map<Instruction *, SmallSet<Instruction *, 4>> &Visited,
+    unsigned CurDepth) {
+  for (auto U = I->user_begin(), E = I->user_end(); U != E; ++U) {
+    Instruction *I2 = dyn_cast<Instruction>(*U);
+    // Ignore I2 if it is not in the loop or it is not known how to be dealt
+    // with
+    if (!I2 || !L->contains(I2->getParent()))
+      continue;
+    else if (!isKnownHowToDropFlags(I2) && !isa<FreezeInst>(I2))
+      continue;
+
+    auto Itr = Visited.find(I2);
+    if (Itr != Visited.end()) {
+      // I2 is reachable from I.
+      Itr->second.insert(I);
+      continue;
+    }
+    Visited[I2].insert(I);
+
+    if (CurDepth < MaxDepth)
+      getReachableInstsInsideLoop(I2, Visited, CurDepth + 1);
+  }
+}
+
+void CanonicalizeFreezeInLoopsImpl::getInstsReachableFromPHI(
+    PHINode &PHI, std::map<Instruction *, SmallSet<Instruction *, 4>> &Insts) {
+  assert(Insts.count(&PHI) == 0);
+  Insts[&PHI] = {};
+  // The collected reachable instructions should drop their flags like nsw/nuw,
+  // so only visit instructions that are known how to be dealt with
+  getReachableInstsInsideLoop(&PHI, Insts, true);
+}
+
+// Visit all instructions that are on possible paths from PHI to FI, and
+// check whether it is possible to push FI out of this loop.
+bool CanonicalizeFreezeInLoopsImpl::CollectUsesToFreezeAndInstsToDropFlags(
+    const std::map<Instruction *, SmallSet<Instruction *, 4>> &InstsFromPHIs,
+    const SmallSet<PHINode *, 4> &IndPHIs, FreezeInst *FI,
+    SmallVector<Use *, 4> &UsesToInsertFreeze,
+    SmallSet<Instruction *, 4> &InstsToDropFlags) {
+
+  auto *PH = L->getLoopPreheader();
+
+  // Start from FI, traverse in a backward direction
+  SmallSet<Instruction *, 8> Visited;
+  std::queue<Instruction *> Queue;
+  Queue.push(FI);
+  bool Stop = false;
+
+  while (!Queue.empty()) {
+    auto *I = Queue.front();
+    Queue.pop();
+
+    auto *PHI = dyn_cast<PHINode>(I);
+    if (PHI && IndPHIs.count(PHI)) {
+      // The initial value should be frozen.
+      bool InitValueInserted = false;
+      for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
+        if (PHI->getIncomingBlock(i) != PH)
+          continue;
+
+        auto &InitUse =
+            PHI->getOperandUse(PHINode::getOperandNumForIncomingValue(i));
+        UsesToInsertFreeze.push_back(&InitUse);
+        InitValueInserted = true;
+        break;
+      }
+      assert(InitValueInserted);
+
+      // Flags of a step instruction should be dropped
+      auto StepPair = getStepInstFrom(PHI);
+      BinaryOperator *StepInst = StepPair.first;
+      InstsToDropFlags.insert(StepInst);
+
+      // Step value should be frozen
+      UsesToInsertFreeze.push_back(&StepInst->getOperandUse(StepPair.second));
+
+      continue;
+    }
+
+    if (I != FI) {
+      assert(isKnownHowToDropFlags(I));
+      InstsToDropFlags.insert(I);
+    }
+
+    // Try to push freeze into I's operands.
+    for (auto &U : I->operands()) {
+      auto *UI = dyn_cast<Instruction>(U.get());
+      if (!UI) {
+        // It should be a constant. Unconditionally put it into
+        // UsesToInsertFreeze.
+        UsesToInsertFreeze.push_back(&U);
+        continue;
+      }
+
+      bool OnThePathsFromPHIs = InstsFromPHIs.count(UI);
+      if (L->contains(UI->getParent()) && !OnThePathsFromPHIs) {
+        // The operand is not on any path from PHI to FI, but still in the
+        // loop. This causes insertion of new freeze in L.
+        LLVM_DEBUG(dbgs() << "canonfr: inst " << *I << "\n"
+                          << "\t" << *UI << " is in the loop!");
+        Stop = true;
+        break;
+      }
+
+      if (OnThePathsFromPHIs) {
+        // Push further
+        if (!Visited.count(UI)) {
+          Visited.insert(UI);
+          Queue.push(UI);
+        }
+      } else {
+        assert(!L->contains(UI->getParent()));
+        UsesToInsertFreeze.push_back(&U);
+      }
+    }
+    if (Stop)
+      break;
+  }
+
+  return !Stop;
+}
+
+// Given U = (value, user), replace value with freeze(value), and let
+// SCEV forget user. The inserted freeze is placed at the preheader.
+void CanonicalizeFreezeInLoopsImpl::InsertFreezeAndForgetFromSCEV(Use &U) {
+  auto *PH = L->getLoopPreheader();
+
+  auto *UserI = dyn_cast<Instruction>(U.getUser());
+  auto *ValueToFr = U.get();
+  assert(UserI && L->contains(UserI->getParent()));
+  if (isGuaranteedNotToBeUndefOrPoison(ValueToFr, UserI, &DT))
+    return;
+
+  LLVM_DEBUG(dbgs() << "canonfr: inserting freeze:\n");
+  LLVM_DEBUG(dbgs() << "\tUser: " << *U.getUser() << "\n");
+  LLVM_DEBUG(dbgs() << "\tOperand: " << *U.get() << "\n");
+
+  U.set(new FreezeInst(ValueToFr, ValueToFr->getName() + ".frozen",
+                       PH->getTerminator()));
+
+  SE.forgetValue(UserI);
+}
+
+bool CanonicalizeFreezeInLoopsImpl::run() {
+  // The loop should be in LoopSimplify form.
+  if (!L->isLoopSimplifyForm())
+    return false;
+
+  // InstsFromPHIs' keys are instructions that are reachable from (auxiliary)
+  // induction PHIs.
+  // InstsFromPHIs[I] maintains a set of instructions that are I's operands and
+  // they're on paths from any of (auxiliary) induction PHIs to I.
+  std::map<Instruction *, SmallSet<Instruction *, 4>> InstsFromPHIs;
+
+  // To push freezes out of L, find
+  // (1) instructions to drop flags like nsw/nuw
+  // (2) the old freeze instructions to remove
+  // (3) uses that will be replaced with frozen values
+  SmallSet<Instruction *, 4> InstsToDropFlags;
+  SmallVector<FreezeInst *, 4> FIsToRemove;
+  SmallVector<Use *, 4> UsesToInsertFr;
+
+  SmallSet<PHINode *, 4> AuxIndPHIs;
+  for (auto &PHI : L->getHeader()->phis()) {
+    if (!L->isAuxiliaryInductionVariable(PHI, SE))
+      continue;
+
+    auto StepPair = getStepInstFrom(&PHI);
+    BinaryOperator *StepInst = StepPair.first;
+    if (!StepInst) {
+      // The stepping instruction has unknown form.
+      // Ignore this PHI.
+      continue;
+    }
+
+    Use &Step = StepInst->getOperandUse(StepPair.second);
+    if (auto *StepI = dyn_cast<Instruction>(Step.get())) {
+      if (StepI && L->contains(StepI->getParent()))
+        // The step value is inside the loop. Freezing step value will introduce
+        // another freeze into the loop, so skip this PHI.
+        continue;
+    }
+
+    LLVM_DEBUG(dbgs() << "canonfr: AuxIndPHI found: " << PHI << "\n");
+    AuxIndPHIs.insert(&PHI);
+
+    getInstsReachableFromPHI(PHI, InstsFromPHIs);
+  }
+
+  // For each freeze inst that is reached from PHI, check whether it can be
+  // pushed out of the loop.
+  for (auto Pair : InstsFromPHIs) {
+    auto *FI = dyn_cast<FreezeInst>(Pair.first);
+    if (!FI)
+      continue;
+
+    LLVM_DEBUG(dbgs() << "canonfr: Freeze found: " << *FI << "\n");
+
+    // Traverse from FI to phis, and collect values to freeze & instructions to
+    // drop flags like nsw.
+    SmallVector<Use *, 4> ToInsertFr;
+    SmallSet<Instruction *, 4> DropFlags;
+    if (!CollectUsesToFreezeAndInstsToDropFlags(InstsFromPHIs, AuxIndPHIs, FI,
+                                                ToInsertFr, DropFlags)) {
+      // FI cannot be hoisted.
+      LLVM_DEBUG(dbgs() << "canonfr: cannot be hoisted: " << *FI << "\n");
+      continue;
+    }
+
+    FIsToRemove.push_back(FI);
+    for (auto *U : ToInsertFr)
+      UsesToInsertFr.push_back(U);
+    for (auto *I : DropFlags)
+      InstsToDropFlags.insert(I);
+  }
+
+  if (FIsToRemove.empty()) {
+    // Nothing to do.
+    assert(!AuxIndPHIs.empty() ||
+           (UsesToInsertFr.empty() && InstsToDropFlags.empty()));
+    return false;
+  }
+
+  assert(!AuxIndPHIs.empty() && !UsesToInsertFr.empty() &&
+         !InstsToDropFlags.empty());
+
+  // Drop flags like nsw/nuw.
+  for (auto *Inst : InstsToDropFlags) {
+    if (isGuaranteedNotToBeUndefOrPoison(Inst, Inst, &DT))
+      continue;
+    // Drop any flag from the instruction.
+    // NOTE: if isKnownHowToDropFlags is expanded to support more ops,
+    // this part should be updated as well.
+    LLVM_DEBUG(dbgs() << "canonfr: drop flags: " << *Inst << "\n");
+    Inst->dropPoisonGeneratingFlags();
+    SE.forgetValue(Inst);
+  }
+
+  // Freeze values. This includes initial value of ind PHI.
+  for (auto *U : UsesToInsertFr)
+    InsertFreezeAndForgetFromSCEV(*U);
+
+  // Finally, remove the old freeze instructions.
+  for (auto *FI : FIsToRemove) {
+    LLVM_DEBUG(dbgs() << "canonfr: removing " << *FI << "\n");
+    SE.forgetValue(FI);
+    FI->replaceAllUsesWith(FI->getOperand(0));
+    FI->eraseFromParent();
+  }
+
+  return true;
+}
+
+CanonicalizeFreezeInLoops::CanonicalizeFreezeInLoops() : LoopPass(ID) {
+  initializeCanonicalizeFreezeInLoopsPass(*PassRegistry::getPassRegistry());
+}
+
+void CanonicalizeFreezeInLoops::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addPreservedID(LoopSimplifyID);
+  AU.addRequired<LoopInfoWrapperPass>();
+  AU.addPreserved<LoopInfoWrapperPass>();
+  AU.addRequiredID(LoopSimplifyID);
+  AU.addRequired<ScalarEvolutionWrapperPass>();
+  AU.addPreserved<ScalarEvolutionWrapperPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addPreserved<DominatorTreeWrapperPass>();
+}
+
+bool CanonicalizeFreezeInLoops::runOnLoop(Loop *L, LPPassManager &) {
+  if (skipLoop(L))
+    return false;
+
+  auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  return CanonicalizeFreezeInLoopsImpl(L, SE, DT).run();
+}
+
+PreservedAnalyses
+CanonicalizeFreezeInLoopsPass::run(Loop &L, LoopAnalysisManager &AM,
+                                   LoopStandardAnalysisResults &AR,
+                                   LPMUpdater &U) {
+  if (!CanonicalizeFreezeInLoopsImpl(&L, AR.SE, AR.DT).run())
+    return PreservedAnalyses::all();
+
+  return getLoopPassPreservedAnalyses();
+}
+
+INITIALIZE_PASS_BEGIN(CanonicalizeFreezeInLoops, "canon-freeze",
+                      "Canonicalize Freeze Instructions in Loops", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
+INITIALIZE_PASS_END(CanonicalizeFreezeInLoops, "canon-freeze",
+                    "Canonicalize Freeze Instructions in Loops", false, false)
+
+Pass *llvm::createCanonicalizeFreezeInLoopsPass() {
+  return new CanonicalizeFreezeInLoops();
+}
+
+char CanonicalizeFreezeInLoops::ID = 0;
\ No newline at end of file
diff --git a/llvm/lib/Transforms/Utils/Utils.cpp b/llvm/lib/Transforms/Utils/Utils.cpp
--- a/llvm/lib/Transforms/Utils/Utils.cpp
+++ b/llvm/lib/Transforms/Utils/Utils.cpp
@@ -26,6 +26,7 @@
   initializeAddDiscriminatorsLegacyPassPass(Registry);
   initializeBreakCriticalEdgesPass(Registry);
   initializeCanonicalizeAliasesLegacyPassPass(Registry);
+  initializeCanonicalizeFreezeInLoopsPass(Registry);
   initializeInstNamerPass(Registry);
   initializeLCSSAWrapperPassPass(Registry);
   initializeLibCallsShrinkWrapLegacyPassPass(Registry);
diff --git a/llvm/test/Transforms/CanonicalizeFreezeInLoops/onephi.ll b/llvm/test/Transforms/CanonicalizeFreezeInLoops/onephi.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/CanonicalizeFreezeInLoops/onephi.ll
@@ -0,0 +1,454 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -canon-freeze -S | FileCheck %s
+; A set of tests that have one phi node
+target triple = "aarch64-unknown-linux-gnu"
+declare void @call(i32)
+declare i32 @get_step()
+
+define void @add(i32 %init, i32 %n) {
+; CHECK-LABEL: @add(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry], [%i.next, %loop ]
+  %i.next = add i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @add_comm(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_comm(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 1, [[I]]
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next, %loop ]
+  %i.next = add i32 1, %i
+  %i.next.fr = freeze i32 %i.next
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @add_multiuses(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_multiuses(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next, %loop ]
+  %i.next = add i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @add_multiuses2(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_multiuses2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next, %loop ]
+  %i.next = add i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %i.next.fr2 = freeze i32 %i.next
+  call void @call(i32 %i.next.fr2)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @add_flags(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_flags(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @add_ind(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_ind(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    [[I_FR_NEXT:%.*]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_FR_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_FR_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %i.fr = freeze i32 %i
+  %i.fr.next = add nuw nsw i32 %i.fr, 1
+  call void @call(i32 %i.fr.next)
+  %cond = icmp eq i32 %i.fr.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Negative test
+define void @add_ind_frozen(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_ind_frozen(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT:%.*]], [[ENTRY:%.*]] ], [ [[I_NEXT_FR:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_FR:%.*]] = freeze i32 [[I]]
+; CHECK-NEXT:    [[I_NEXT_FR]] = add nuw nsw i32 [[I_FR]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT_FR]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT_FR]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [%init, %entry], [%i.next.fr, %loop]
+  %i.fr = freeze i32 %i
+  %i.next.fr = add nuw nsw i32 %i.fr, 1
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @add_flags_not_compared(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_flags_not_compared(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Negative test
+define void @add_flags_not_compared_stepinst(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_flags_not_compared_stepinst(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT:%.*]], [[ENTRY:%.*]] ], [ [[I_NEXT_FR:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT:%.*]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    [[I_NEXT_FR]] = freeze i32 [[I_NEXT]]
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT_FR]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next.fr, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Negative test
+; If pushing freeze through icmp is needed, this should be enabled.
+; There is no correctness issue in pushing freeze into icmp here, just it's
+; being conservative right now.
+define void @add_flags_stepinst_frozen(i32 %init, i32 %n) {
+; CHECK-LABEL: @add_flags_stepinst_frozen(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT:%.*]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[COND]]
+; CHECK-NEXT:    br i1 [[COND_FR]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %init, %entry ], [ %i.next, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  call void @call(i32 %i.next)
+  %cond = icmp eq i32 %i.next, %n
+  %cond.fr = freeze i1 %cond
+  br i1 %cond.fr, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @sub(i32 %init, i32 %n) {
+; CHECK-LABEL: @sub(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = sub i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [%init, %entry], [%i.next, %loop]
+  %i.next = sub nuw nsw i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @init_const(i32 %n) {
+; CHECK-LABEL: @init_const(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @step_init_arg(i32 %init, i32 %n, i32 %step) {
+; CHECK-LABEL: @step_init_arg(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[STEP_FROZEN:%.*]] = freeze i32 [[STEP:%.*]]
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], [[STEP_FROZEN]]
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [%init, %entry], [%i.next, %loop]
+  %i.next = add nuw nsw i32 %i, %step
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @step_init_inst(i32 %n) {
+; CHECK-LABEL: @step_init_inst(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[STEP:%.*]] = call i32 @get_step()
+; CHECK-NEXT:    [[INIT:%.*]] = call i32 @get_step()
+; CHECK-NEXT:    [[STEP_FROZEN:%.*]] = freeze i32 [[STEP]]
+; CHECK-NEXT:    [[INIT_FROZEN:%.*]] = freeze i32 [[INIT]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], [[STEP_FROZEN]]
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %step = call i32 @get_step()
+  %init = call i32 @get_step()
+  br label %loop
+
+loop:
+  %i = phi i32 [%init, %entry], [%i.next, %loop]
+  %i.next = add nuw nsw i32 %i, %step
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Negative test
+define void @step_inst(i32 %init, i32 %n) {
+; CHECK-LABEL: @step_inst(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[INIT:%.*]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], [[I]]
+; CHECK-NEXT:    [[I_NEXT_FR:%.*]] = freeze i32 [[I_NEXT]]
+; CHECK-NEXT:    call void @call(i32 [[I_NEXT_FR]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT_FR]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [%init, %entry], [%i.next, %loop]
+  %i.next = add nuw nsw i32 %i, %i
+  %i.next.fr = freeze i32 %i.next
+  call void @call(i32 %i.next.fr)
+  %cond = icmp eq i32 %i.next.fr, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
diff --git a/llvm/test/Transforms/CanonicalizeFreezeInLoops/phis.ll b/llvm/test/Transforms/CanonicalizeFreezeInLoops/phis.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/CanonicalizeFreezeInLoops/phis.ll
@@ -0,0 +1,115 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -canon-freeze -S | FileCheck %s
+; A set of tests that have several phi nodes
+target triple = "aarch64-unknown-linux-gnu"
+declare void @call(i32)
+declare i32 @call2()
+
+define void @onephi_used(i32 %n, i32 %i.init, i32 %j.init) {
+; CHECK-LABEL: @onephi_used(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[I_INIT_FROZEN:%.*]] = freeze i32 [[I_INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[J_INIT:%.*]], [[ENTRY]] ], [ [[J_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    [[J_NEXT]] = add nuw nsw i32 [[J]], -2
+; CHECK-NEXT:    call void @call(i32 [[I]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %i.init, %entry ], [ %i.next, %loop ]
+  %j = phi i32 [ %j.init, %entry ], [ %j.next, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %j.next = add nuw nsw i32 %j, -2
+  %i.fr = freeze i32 %i
+  call void @call(i32 %i.fr)
+  %cond = icmp eq i32 %i.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @twophis_used(i32 %n, i32 %i.init, i32 %j.init) {
+; CHECK-LABEL: @twophis_used(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[I_INIT_FROZEN:%.*]] = freeze i32 [[I_INIT:%.*]]
+; CHECK-NEXT:    [[J_INIT_FROZEN:%.*]] = freeze i32 [[J_INIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_INIT_FROZEN]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[J_INIT_FROZEN]], [[ENTRY]] ], [ [[J_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
+; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], -2
+; CHECK-NEXT:    [[IJ:%.*]] = add i32 [[I]], [[J]]
+; CHECK-NEXT:    call void @call(i32 [[IJ]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %i.init, %entry ], [ %i.next, %loop ]
+  %j = phi i32 [ %j.init, %entry ], [ %j.next, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %j.next = add nuw nsw i32 %j, -2
+  %ij = add i32 %i, %j
+  %ij.fr = freeze i32 %ij
+  call void @call(i32 %ij.fr)
+  %cond = icmp eq i32 %i.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Negative test
+define void @nonindphi_used(i32 %n, i32 %i.init, i32 %j.init, i32 %k.init) {
+; CHECK-LABEL: @nonindphi_used(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_INIT:%.*]], [[ENTRY:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ [[J_INIT:%.*]], [[ENTRY]] ], [ [[J_NEXT:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[K:%.*]] = phi i32 [ [[K_INIT:%.*]], [[ENTRY]] ], [ [[ANY:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
+; CHECK-NEXT:    [[J_NEXT]] = add nuw nsw i32 [[J]], -2
+; CHECK-NEXT:    [[IJ:%.*]] = add i32 [[I]], [[J]]
+; CHECK-NEXT:    [[IJK:%.*]] = add i32 [[IJ]], [[K]]
+; CHECK-NEXT:    [[IJK_FR:%.*]] = freeze i32 [[IJK]]
+; CHECK-NEXT:    call void @call(i32 [[IJK_FR]])
+; CHECK-NEXT:    [[ANY]] = call i32 @call2()
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[I_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %i = phi i32 [ %i.init, %entry ], [ %i.next, %loop ]
+  %j = phi i32 [ %j.init, %entry ], [ %j.next, %loop ]
+  %k = phi i32 [ %k.init, %entry ], [ %any, %loop ]
+  %i.next = add nuw nsw i32 %i, 1
+  %j.next = add nuw nsw i32 %j, -2
+  %ij = add i32 %i, %j
+  %ijk = add i32 %ij, %k
+  %ijk.fr = freeze i32 %ijk
+  call void @call(i32 %ijk.fr)
+  %any = call i32 @call2()
+  %cond = icmp eq i32 %i.next, %n
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}