Index: lib/Transforms/Utils/LCSSA.cpp
===================================================================
--- lib/Transforms/Utils/LCSSA.cpp
+++ lib/Transforms/Utils/LCSSA.cpp
@@ -66,11 +66,10 @@
   return is_contained(ExitBlocks, BB);
 }
 
-/// For every instruction from the worklist, check to see if it has any uses
-/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
-/// rewrite the uses.
-bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
-                                    DominatorTree &DT, LoopInfo &LI) {
+/// For instruction I, check to see if it has any uses that are outside the
+/// current loop.  If so, insert LCSSA PHI nodes and rewrite the uses.
+static bool formLCSSAForOneInstruction(Instruction *I, DominatorTree &DT,
+                                       LoopInfo &LI) {
   SmallVector<Use *, 16> UsesToRewrite;
   SmallSetVector<PHINode *, 16> PHIsToRemove;
   PredIteratorCache PredCache;
@@ -81,6 +80,13 @@
   // expensive, and we're not mutating the loop structure.
   SmallDenseMap<Loop*, SmallVector<BasicBlock *,1>> LoopExitBlocks;
 
+  SmallVector<Instruction *, 4> Worklist;
+  Worklist.push_back(I);
+
+  SmallVector<PHINode *, 4> InsertedPHIs;
+  SSAUpdater SSAUpdate(&InsertedPHIs);
+  SSAUpdate.Initialize(I->getType(), I->getName());
+
   while (!Worklist.empty()) {
     UsesToRewrite.clear();
 
@@ -131,10 +137,6 @@
     SmallVector<PHINode *, 16> AddedPHIs;
     SmallVector<PHINode *, 8> PostProcessPHIs;
 
-    SmallVector<PHINode *, 4> InsertedPHIs;
-    SSAUpdater SSAUpdate(&InsertedPHIs);
-    SSAUpdate.Initialize(I->getType(), I->getName());
-
     // Insert the LCSSA phi's into all of the exit blocks dominated by the
     // value, and add them to the Phi's map.
     for (BasicBlock *ExitBB : ExitBlocks) {
@@ -142,8 +144,11 @@
         continue;
 
       // If we already inserted something for this BB, don't reprocess it.
-      if (SSAUpdate.HasValueForBlock(ExitBB))
-        continue;
+      if (SSAUpdate.HasValueForBlock(ExitBB)) {
+        Value *AV = SSAUpdate.GetValueAtEndOfBlock(ExitBB);
+        if (isa<PHINode>(AV) && cast<Instruction>(AV)->getParent() == ExitBB)
+          continue;
+      }
 
       PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
                                     I->getName() + ".lcssa", &ExitBB->front());
@@ -237,6 +242,19 @@
   return Changed;
 }
 
+/// For every instruction from the worklist, check to see if it has any uses
+/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
+/// rewrite the uses.
+bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
+                                    DominatorTree &DT, LoopInfo &LI) {
+  bool Changed = false;
+  while (!Worklist.empty()) {
+    Instruction *I = Worklist.pop_back_val();
+    Changed |= formLCSSAForOneInstruction(I, DT, LI);
+  }
+  return Changed;
+}
+
 /// Return true if the specified block dominates at least
 /// one of the blocks in the specified list.
 static bool
Index: test/Transforms/LCSSA/pr28424.ll
===================================================================
--- test/Transforms/LCSSA/pr28424.ll
+++ test/Transforms/LCSSA/pr28424.ll
@@ -85,3 +85,71 @@
 exit:
   ret i32 %x
 }
+
+; This test failed at some point when invoked with '-lcssa -licm'. The problem
+; was that SSAUpdater didn't try to preserve LCSSA and happened to insert a
+; phi-node, which broke LCSSA (it inserted one more phi-node to if.end block).
+; Here we check that we inserted no more than one phi-node where needed.
+; CHECK-LABEL: @foo3
+define void @foo3() {
+entry:
+  br label %loop.A
+entry2:
+  br label %inner.loop.B
+entry3:
+  br label %inner.loop.C
+
+loop.A:
+  %c.0 = phi i32 [ 0, %entry ], [ 0, %loop.A ]
+  br i1 false, label %loop.A.end, label %loop.A
+; CHECK: loop.A.end:
+; CHECK:     phi
+; CHECK-NOT: phi
+loop.A.end:
+  br label %outer.loop
+
+; CHECK: outer.loop:
+; CHECK:     phi
+; CHECK-NOT: phi
+outer.loop:
+  br label %inner.loop.B
+
+; CHECK: inner.loop.B:
+; CHECK:     phi
+; CHECK-NOT: phi
+inner.loop.B:
+  br i1 false, label %inner.loop.B.latch, label %outer.loop.latch
+inner.loop.B.latch:
+  br i1 false, label %if.then, label %inner.loop.B
+
+; CHECK: if.then:
+; CHECK:     phi
+; CHECK-NOT: phi
+if.then:
+  br i1 false, label %inner.loop.C, label %if.end
+
+; CHECK: inner.loop.C:
+; CHECK:     phi
+; CHECK-NOT: phi
+inner.loop.C:
+  %tobool9 = icmp ne i32 %c.0, 0
+  br i1 false, label %inner.loop.C, label %inner.loop.C.end
+
+; CHECK: inner.loop.C.end:
+; CHECK:     phi
+; CHECK-NOT: phi
+inner.loop.C.end:
+  br label %if.end
+
+; CHECK: if.end:
+; CHECK:     phi
+; CHECK-NOT: phi
+if.end:
+  br label %outer.loop.latch
+
+; CHECK: outer.loop.latch:
+; CHECK:     phi
+; CHECK-NOT: phi
+outer.loop.latch:
+  br label %outer.loop
+}