Index: llvm/include/llvm/Transforms/Utils/LoopUtils.h
===================================================================
--- llvm/include/llvm/Transforms/Utils/LoopUtils.h
+++ llvm/include/llvm/Transforms/Utils/LoopUtils.h
@@ -76,10 +76,14 @@
 /// This function may introduce unused PHI nodes. If \p PHIsToRemove is not
 /// nullptr, those are added to it (before removing, the caller has to check if
 /// they still do not have any uses). Otherwise the PHIs are directly removed.
+///
+/// If \p InsertedPHIs is not nullptr, phis inserted without using Builder (and
+/// thus not executing the insertion callback) will be added to this vector.
 bool formLCSSAForInstructions(
     SmallVectorImpl<Instruction *> &Worklist, const DominatorTree &DT,
     const LoopInfo &LI, IRBuilderBase &Builder,
-    SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr);
+    SmallVectorImpl<PHINode *> *PHIsToRemove = nullptr,
+    SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
 
 /// Put loop into LCSSA form.
 ///
Index: llvm/lib/Transforms/Utils/LCSSA.cpp
===================================================================
--- llvm/lib/Transforms/Utils/LCSSA.cpp
+++ llvm/lib/Transforms/Utils/LCSSA.cpp
@@ -78,7 +78,8 @@
 bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
                                     const DominatorTree &DT, const LoopInfo &LI,
                                     IRBuilderBase &Builder,
-                                    SmallVectorImpl<PHINode *> *PHIsToRemove) {
+                                    SmallVectorImpl<PHINode *> *PHIsToRemove,
+                                    SmallVectorImpl<PHINode *> *InsertedPHIs) {
   SmallVector<Use *, 16> UsesToRewrite;
   SmallSetVector<PHINode *, 16> LocalPHIsToRemove;
   PredIteratorCache PredCache;
@@ -146,8 +147,8 @@
     SmallVector<PHINode *, 16> AddedPHIs;
     SmallVector<PHINode *, 8> PostProcessPHIs;
 
-    SmallVector<PHINode *, 4> InsertedPHIs;
-    SSAUpdater SSAUpdate(&InsertedPHIs);
+    SmallVector<PHINode *, 4> LocalInsertedPHIs;
+    SSAUpdater SSAUpdate(&LocalInsertedPHIs);
     SSAUpdate.Initialize(I->getType(), I->getName());
 
     // Insert the LCSSA phi's into all of the exit blocks dominated by the
@@ -251,10 +252,12 @@
 
     // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
     // to post-process them to keep LCSSA form.
-    for (PHINode *InsertedPN : InsertedPHIs) {
+    for (PHINode *InsertedPN : LocalInsertedPHIs) {
       if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
         if (!L->contains(OtherLoop))
           PostProcessPHIs.push_back(InsertedPN);
+      if (InsertedPHIs)
+        InsertedPHIs->push_back(InsertedPN);
     }
 
     // Post process PHI instructions that were inserted into another disjoint
Index: llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
===================================================================
--- llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
+++ llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
@@ -2558,7 +2558,11 @@
   SmallVector<Instruction *, 1> ToUpdate;
   ToUpdate.push_back(DefI);
   SmallVector<PHINode *, 16> PHIsToRemove;
-  formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, Builder, &PHIsToRemove);
+  SmallVector<PHINode *, 16> InsertedPHIs;
+  formLCSSAForInstructions(ToUpdate, SE.DT, SE.LI, Builder, &PHIsToRemove,
+                           &InsertedPHIs);
+  for (PHINode *PN : InsertedPHIs)
+    rememberInstruction(PN);
   for (PHINode *PN : PHIsToRemove) {
     if (!PN->use_empty())
       continue;
Index: llvm/test/Transforms/LoopIdiom/remove-inserted-lcssa.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/LoopIdiom/remove-inserted-lcssa.ll
@@ -0,0 +1,76 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -S -passes=loop-idiom < %s | FileCheck %s
+
+; Make sure that any inserted LCSSA phi nodes are removed if the transform
+; is aborted.
+
+define void @test() {
+; CHECK-LABEL: define void @test() {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ALLOCA:%.*]] = alloca [64 x i8], align 16
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ 1, [[LOOP_LATCH:%.*]] ]
+; CHECK-NEXT:    br i1 false, label [[LOOP_EXIT2:%.*]], label [[LOOP_LATCH]]
+; CHECK:       loop.latch:
+; CHECK-NEXT:    [[OR:%.*]] = or i64 [[PHI]], 4
+; CHECK-NEXT:    br i1 false, label [[LOOP_EXIT:%.*]], label [[LOOP]]
+; CHECK:       loop.exit:
+; CHECK-NEXT:    [[OR_LCSSA:%.*]] = phi i64 [ [[OR]], [[LOOP_LATCH]] ]
+; CHECK-NEXT:    br label [[LOOP2_PREHEADER:%.*]]
+; CHECK:       loop.exit2:
+; CHECK-NEXT:    br label [[LOOP2_PREHEADER]]
+; CHECK:       loop2.preheader:
+; CHECK-NEXT:    [[PHI5_PH:%.*]] = phi ptr [ null, [[LOOP_EXIT2]] ], [ [[ALLOCA]], [[LOOP_EXIT]] ]
+; CHECK-NEXT:    [[PHI6_PH:%.*]] = phi i64 [ 0, [[LOOP_EXIT2]] ], [ [[OR_LCSSA]], [[LOOP_EXIT]] ]
+; CHECK-NEXT:    br label [[LOOP2:%.*]]
+; CHECK:       loop2:
+; CHECK-NEXT:    [[PHI5:%.*]] = phi ptr [ [[GETELEMENTPTR7:%.*]], [[LOOP2]] ], [ [[PHI5_PH]], [[LOOP2_PREHEADER]] ]
+; CHECK-NEXT:    [[PHI6:%.*]] = phi i64 [ [[ADD:%.*]], [[LOOP2]] ], [ [[PHI6_PH]], [[LOOP2_PREHEADER]] ]
+; CHECK-NEXT:    [[GETELEMENTPTR:%.*]] = getelementptr i8, ptr [[ALLOCA]], i64 [[PHI6]]
+; CHECK-NEXT:    [[LOAD:%.*]] = load i8, ptr [[GETELEMENTPTR]], align 1
+; CHECK-NEXT:    store i8 [[LOAD]], ptr [[PHI5]], align 1
+; CHECK-NEXT:    [[GETELEMENTPTR7]] = getelementptr i8, ptr [[PHI5]], i64 1
+; CHECK-NEXT:    [[ADD]] = add i64 [[PHI6]], 1
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq i64 [[PHI6]], 0
+; CHECK-NEXT:    br i1 [[ICMP]], label [[LOOP2_EXIT:%.*]], label [[LOOP2]]
+; CHECK:       loop2.exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %alloca = alloca [64 x i8], align 16
+  br label %loop
+
+loop:
+  %phi = phi i64 [ 0, %entry ], [ 1, %loop.latch ]
+  br i1 false, label %loop.exit2, label %loop.latch
+
+loop.latch:
+  %or = or i64 %phi, 4
+  br i1 false, label %loop.exit, label %loop
+
+loop.exit:
+  br label %loop2.preheader
+
+loop.exit2:
+  br label %loop2.preheader
+
+loop2.preheader:
+  %phi5.ph = phi ptr [ null, %loop.exit2 ], [ %alloca, %loop.exit ]
+  %phi6.ph = phi i64 [ 0, %loop.exit2 ], [ %or, %loop.exit ]
+  br label %loop2
+
+loop2:
+  %phi5 = phi ptr [ %getelementptr7, %loop2 ], [ %phi5.ph, %loop2.preheader ]
+  %phi6 = phi i64 [ %add, %loop2 ], [ %phi6.ph, %loop2.preheader ]
+  %getelementptr = getelementptr i8, ptr %alloca, i64 %phi6
+  %load = load i8, ptr %getelementptr, align 1
+  store i8 %load, ptr %phi5, align 1
+  %getelementptr7 = getelementptr i8, ptr %phi5, i64 1
+  %add = add i64 %phi6, 1
+  %icmp = icmp eq i64 %phi6, 0
+  br i1 %icmp, label %loop2.exit, label %loop2
+
+loop2.exit:
+  ret void
+}