Index: lib/Transforms/Scalar/Reassociate.cpp
===================================================================
--- lib/Transforms/Scalar/Reassociate.cpp
+++ lib/Transforms/Scalar/Reassociate.cpp
@@ -23,6 +23,7 @@
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -1954,7 +1955,8 @@
   ValueRankMap.erase(I);
   RedoInsts.remove(I);
   I->eraseFromParent();
-  // Optimize its operands.
+  // Optimize its operands unless it is a PHI node.
+  if(isa<PHINode>(I)) return;
   SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes.
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
@@ -2262,9 +2264,31 @@
   BuildRankMap(F);
 
   MadeChange = false;
-  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
-    // Optimize every instruction in the basic block.
-    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; )
+
+  // Reassociate needs for each instruction to have its operands already
+  // processed, so we first perform a "Topological" of the basic blocks so that
+  // when we process a basic block, all its dominators were processed before
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  for (BasicBlock *BI : RPOT) {
+
+    // After processing each instruction, we need to reprocess some instructions
+    // that were affected by the reassociation. However some instructions that
+    // are coming later in the basic block may have been added to the reprocess
+    // list and we do not want to process them now, but only when all the ones
+    // in between are processed. So we need to know which instructions are still
+    // scheduled for later processing in this basic block. The following set
+    // answer this question.
+    SmallSet<Instruction *, 8> Worklist;
+    for (Instruction &I : *BI) {
+      Worklist.insert(&I);
+    }
+
+    // Optimize every instructions in the basic block.
+    // The instruction can be removed from the basic block
+    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;) {
+      // Remove the instruction from the worklist
+      Worklist.erase(II);
+
       if (isInstructionTriviallyDead(II)) {
         EraseInst(II++);
       } else {
@@ -2273,13 +2297,21 @@
         ++II;
       }
 
-    // If this produced extra instructions to optimize, handle them now.
-    while (!RedoInsts.empty()) {
-      Instruction *I = RedoInsts.pop_back_val();
-      if (isInstructionTriviallyDead(I))
-        EraseInst(I);
-      else
-        OptimizeInst(I);
+      // If this produced extra instructions to optimize, or set already
+      // processed instructions to reprocess, handle them now.
+      while (!RedoInsts.empty()) {
+        Instruction *I = RedoInsts.pop_back_val();
+        // We only process instructions that are not existing later in the
+        // block, since these will be processing in a subsequent iteration on
+        // the basic block.
+        if (!Worklist.count(I) && &*II != I) {
+          if (isInstructionTriviallyDead(I)) {
+            EraseInst(I);
+          } else {
+            OptimizeInst(I);
+          }
+        }
+      }
     }
   }
 
Index: test/Transforms/Reassociate/crash3.ll
===================================================================
--- /dev/null
+++ test/Transforms/Reassociate/crash3.ll
@@ -0,0 +1,13 @@
+; RUN: opt -reassociate -o - -S %s | FileCheck %s
+
+define i32 @foo(i32 %in) {
+; CHECK-LABEL: @foo
+; CHECK: %factor = mul i32 %in, -4
+  %_0 = add i32 %in, 1
+  %_1 = mul i32 %in, -2
+  %_2 = add i32 %_0, %_1
+  %_3 = add i32 %_1, %_2
+  %_4 = add i32 %_3, 1
+  %_5 = add i32 %in, %_3
+  ret i32 %_5
+}
Index: test/Transforms/Reassociate/crash4.ll
===================================================================
--- /dev/null
+++ test/Transforms/Reassociate/crash4.ll
@@ -0,0 +1,22 @@
+; RUN: opt -reassociate -o - -S %s | FileCheck %s
+
+
+define void @foo(float %in) {
+wrapper_entry:
+  br label %for.body
+
+for.body:
+  %0 = phi float [ %7, %for.body ], [ %in, %wrapper_entry ]
+  %1 = fadd fast float %0, %in
+  %2 = fadd fast float %1, 3.000000e+00
+  %3 = fsub fast float %1, %2
+  %4 = fmul fast float %3, 3.000000e+00
+  %5 = fadd fast float %3, %4
+  %6 = fmul fast float %5, %5
+  %7 = fsub fast float %5, %5
+  br label %for.body
+}
+
+; CHECK:      for.body:
+; CHECK-NEXT:   br label %for.body
+; CHECK-NEXT: }
Index: test/Transforms/Reassociate/crash5.ll
===================================================================
--- /dev/null
+++ test/Transforms/Reassociate/crash5.ll
@@ -0,0 +1,20 @@
+; RUN: opt -reassociate -o - -S %s
+
+
+define void @foo(float %in, i1 %cmp) {
+wrapper_entry:
+  br label %foo1
+
+for.body:
+  %0 = fadd float %in1, %in1
+  br label %foo1
+
+foo1:
+  %_0 = fmul fast float %in, -3.000000e+00
+  %_1 = fmul fast float %_0, 3.000000e+00
+  %in1 = fadd fast float -3.000000e+00, %_1
+  %in1use = fadd fast float %in1, %in1
+  br label %for.body
+
+
+}
Index: test/Transforms/Reassociate/crash6.ll
===================================================================
--- /dev/null
+++ test/Transforms/Reassociate/crash6.ll
@@ -0,0 +1,13 @@
+; RUN: opt -reassociate -o - -S %s
+
+
+define float @foo(float %in,float %in1,float %in2, i1 %cmp) {
+  %_0 = fmul fast float %in, 3.000000e+00
+  %_1 = fmul fast float %in1, 1.000000e+00
+  %_2 = fmul fast float %in2, 3.000000e+00
+  %_3 = fmul fast float %in2, -1.000000e+00
+  %_4 = fmul fast float %_0, %_1
+  %_5 = fmul fast float %_3, %_2
+  %out = fadd fast float %_5, %_4
+  ret float %out
+}