Merging r278938:

------------------------------------------------------------------------
r278938 | mcrosier | 2016-08-17 08:54:39 -0700 (Wed, 17 Aug 2016) | 5 lines

Revert "Reassociate: Reprocess RedoInsts after each inst".

This reverts commit r258830, which introduced a bug described in PR28367.

PR28367
------------------------------------------------------------------------


git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_39@278993 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 33 insertions, 100 deletions

diff --git a/include/llvm/Transforms/Scalar/Reassociate.h b/include/llvm/Transforms/Scalar/Reassociate.h
index 7b68b4489306..2f56b9398778 100644
--- a/include/llvm/Transforms/Scalar/Reassociate.h
+++ b/include/llvm/Transforms/Scalar/Reassociate.h
@@ -65,7 +65,7 @@ public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
 
 private:
-  void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
+  void BuildRankMap(Function &F);
   unsigned getRank(Value *V);
   void canonicalizeOperands(Instruction *I);
   void ReassociateExpression(BinaryOperator *I);
diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp
index b930a8fb7e99..e42e2c6d8aa4 100644
--- a/lib/Transforms/Scalar/Reassociate.cpp
+++ b/lib/Transforms/Scalar/Reassociate.cpp
@@ -145,8 +145,7 @@ static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1,
   return nullptr;
 }
 
-void ReassociatePass::BuildRankMap(
-    Function &F, ReversePostOrderTraversal<Function *> &RPOT) {
+void ReassociatePass::BuildRankMap(Function &F) {
   unsigned i = 2;
 
   // Assign distinct ranks to function arguments.
@@ -155,6 +154,7 @@ void ReassociatePass::BuildRankMap(
     DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
   }
 
+  ReversePostOrderTraversal<Function *> RPOT(&F);
   for (BasicBlock *BB : RPOT) {
     unsigned BBRank = RankMap[BB] = ++i << 16;
 
@@ -2172,28 +2172,13 @@ void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
 }
 
 PreservedAnalyses ReassociatePass::run(Function &F, FunctionAnalysisManager &) {
-  // Reassociate needs for each instruction to have its operands already
-  // processed, so we first perform a RPOT of the basic blocks so that
-  // when we process a basic block, all its dominators have been processed
-  // before.
-  ReversePostOrderTraversal<Function *> RPOT(&F);
-  BuildRankMap(F, RPOT);
+  // Calculate the rank map for F.
+  BuildRankMap(F);
 
   MadeChange = false;
-  for (BasicBlock *BI : RPOT) {
-    // Use a worklist to keep track of which instructions have been processed
-    // (and which insts won't be optimized again) so when redoing insts,
-    // optimize insts rightaway which won't be processed later.
-    SmallSet<Instruction *, 8> Worklist;
-
-    // Insert all instructions in the BB
-    for (Instruction &I : *BI)
-      Worklist.insert(&I);
-
+  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;) {
-      // This instruction has been processed.
-      Worklist.erase(&*II);
+    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
       if (isInstructionTriviallyDead(&*II)) {
         EraseInst(&*II++);
       } else {
@@ -2202,22 +2187,27 @@ PreservedAnalyses ReassociatePass::run(Function &F, FunctionAnalysisManager &) {
         ++II;
       }
 
-      // If the above optimizations produced new instructions to optimize or
-      // made modifications which need to be redone, do them now if they won't
-      // be handled later.
-      while (!RedoInsts.empty()) {
-        Instruction *I = RedoInsts.pop_back_val();
-        // Process instructions that won't be processed later, either
-        // inside the block itself or in another basic block (based on rank),
-        // since these will be processed later.
-        if ((I->getParent() != BI || !Worklist.count(I)) &&
-            RankMap[I->getParent()] <= RankMap[BI]) {
-          if (isInstructionTriviallyDead(I))
-            EraseInst(I);
-          else
-            OptimizeInst(I);
-        }
-      }
+    // Make a copy of all the instructions to be redone so we can remove dead
+    // instructions.
+    SetVector<AssertingVH<Instruction>> ToRedo(RedoInsts);
+    // Iterate over all instructions to be reevaluated and remove trivially dead
+    // instructions. If any operand of the trivially dead instruction becomes
+    // dead mark it for deletion as well. Continue this process until all
+    // trivially dead instructions have been removed.
+    while (!ToRedo.empty()) {
+      Instruction *I = ToRedo.pop_back_val();
+      if (isInstructionTriviallyDead(I))
+        RecursivelyEraseDeadInsts(I, ToRedo);
+    }
+
+    // Now that we have removed dead instructions, we can reoptimize the
+    // remaining instructions.
+    while (!RedoInsts.empty()) {
+      Instruction *I = RedoInsts.pop_back_val();
+      if (isInstructionTriviallyDead(I))
+        EraseInst(I);
+      else
+        OptimizeInst(I);
     }
   }
 
diff --git a/test/Transforms/Reassociate/prev_insts_canonicalized.ll b/test/Transforms/Reassociate/prev_insts_canonicalized.ll
deleted file mode 100644
index 649761e57c9a..000000000000
--- a/test/Transforms/Reassociate/prev_insts_canonicalized.ll
+++ /dev/null
@@ -1,57 +0,0 @@
-; RUN: opt < %s -reassociate -S | FileCheck %s
-
-; These tests make sure that before processing insts
-; any previous instructions are already canonicalized.
-define i32 @foo(i32 %in) {
-; CHECK-LABEL: @foo
-; CHECK-NEXT: %factor = mul i32 %in, -4
-; CHECK-NEXT: %factor1 = mul i32 %in, 2
-; CHECK-NEXT: %_3 = add i32 %factor, 1
-; CHECK-NEXT: %_5 = add i32 %_3, %factor1
-; CHECK-NEXT: ret i32 %_5
-  %_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
-}
-
-; CHECK-LABEL: @foo1
-define void @foo1(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
-
-
-}
-
-; CHECK-LABEL: @foo2
-define void @foo2(float %in, i1 %cmp) {
-wrapper_entry:
-  br label %for.body
-
-for.body:
-; If the operands of the phi are sheduled for processing before
-; foo1 is processed, the invariant of reassociate are not preserved
-  %unused = phi float [%in1, %foo1], [undef, %wrapper_entry]
-  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
-}
diff --git a/test/Transforms/Reassociate/reassoc-intermediate-fnegs.ll b/test/Transforms/Reassociate/reassoc-intermediate-fnegs.ll
index 7d82ef7e7a2f..c2cdffce61e4 100644
--- a/test/Transforms/Reassociate/reassoc-intermediate-fnegs.ll
+++ b/test/Transforms/Reassociate/reassoc-intermediate-fnegs.ll
@@ -1,8 +1,8 @@
 ; RUN: opt < %s -reassociate -S | FileCheck %s
 ; CHECK-LABEL: faddsubAssoc1
-; CHECK: [[TMP1:%.*]] = fsub fast half 0xH8000, %a
-; CHECK: [[TMP2:%.*]] = fadd fast half %b, [[TMP1]]
-; CHECK: fmul fast half [[TMP2]], 0xH4500
+; CHECK: [[TMP1:%tmp.*]] = fmul fast half %a, 0xH4500
+; CHECK: [[TMP2:%tmp.*]] = fmul fast half %b, 0xH4500
+; CHECK: fsub fast half [[TMP2]], [[TMP1]]
 ; CHECK: ret
 ; Input is A op (B op C)
 define half @faddsubAssoc1(half %a, half %b) {
diff --git a/test/Transforms/Reassociate/xor_reassoc.ll b/test/Transforms/Reassociate/xor_reassoc.ll
index a22689805fb5..0bed6f358808 100644
--- a/test/Transforms/Reassociate/xor_reassoc.ll
+++ b/test/Transforms/Reassociate/xor_reassoc.ll
@@ -88,8 +88,8 @@ define i32 @xor_special2(i32 %x, i32 %y) {
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 ; CHECK-LABEL: @xor_special2(
-; CHECK: %xor = xor i32 %y, 123
-; CHECK: %xor1 = xor i32 %xor, %x
+; CHECK: %xor = xor i32 %x, 123
+; CHECK: %xor1 = xor i32 %xor, %y
 ; CHECK: ret i32 %xor1
 }