[Reassociate] : Make sure when we are optimizing an instruction, it's operands have already been canonicalized

[aditya_nandakumar]

Summary

This is a continuation (I couldn't update the phab review) from http://reviews.llvm.org/D6995 (Original Patch by Mehdi)

Before we Optimize instruction, make sure all instructions that are in the redo list and are before the current instruction have been optimized.

[mcrosier]

Hi Aditya,
If at all possible we should continue the review in D6995. At the bottom of D6995 you should see an Action pull down. Select the 'Commandeer Revision' to take ownership of Mehdi's patch. From there you should be able to upload a new diff.

HTH,

Chad

[aditya_nandakumar]

Thanks Updated. Closing this one.

lib/Transforms/Scalar/Reassociate.cpp

public:
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addPreserved<GlobalsAAWrapperPass>();
     }
   private:
-    void BuildRankMap(Function &F);
+    void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
+
     unsigned getRank(Value *V);
     void canonicalizeOperands(Instruction *I);
     void ReassociateExpression(BinaryOperator *I);
     void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
     Value *OptimizeExpression(BinaryOperator *I,
                               SmallVectorImpl<ValueEntry> &Ops);
     Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
     Value *OptimizeXor(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
if (V->hasOneUse() && isa<Instruction>(V) &&
       (cast<Instruction>(V)->getOpcode() == Opcode1 ||
        cast<Instruction>(V)->getOpcode() == Opcode2) &&
       (!isa<FPMathOperator>(V) ||
        cast<Instruction>(V)->hasUnsafeAlgebra()))
     return cast<BinaryOperator>(V);
   return nullptr;
 }
 
-void Reassociate::BuildRankMap(Function &F) {
+void Reassociate::BuildRankMap(Function &F,
+                               ReversePostOrderTraversal<Function *> &RPOT) {
   unsigned i = 2;
 
   // Assign distinct ranks to function arguments.
   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
     ValueRankMap[&*I] = ++i;
     DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
   }
 
-  ReversePostOrderTraversal<Function*> RPOT(&F);
   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
          E = RPOT.end(); I != E; ++I) {
     BasicBlock *BB = *I;
     unsigned BBRank = RankMap[BB] = ++i << 16;
 
     // Walk the basic block, adding precomputed ranks for any instructions that
     // we cannot move.  This ensures that the ranks for these instructions are
     // all different in the block.
void Reassociate::ReassociateExpression(BinaryOperator *I) {
   // the expression tree, removing any unneeded nodes.
   RewriteExprTree(I, Ops);
 }
 
 bool Reassociate::runOnFunction(Function &F) {
   if (skipOptnoneFunction(F))
     return false;
 
-  // Calculate the rank map for F
-  BuildRankMap(F);
+  // 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 ben processed
+  // before.
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  BuildRankMap(F, RPOT);
 
   MadeChange = false;
-  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
+  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);
+
     // Optimize every instruction in the basic block.
-    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; )
+    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;) {
+      // This instruction has been processed.
+      Worklist.erase(&*II);
       if (isInstructionTriviallyDead(&*II)) {
         EraseInst(&*II++);
       } else {
         OptimizeInst(&*II);
         assert(II->getParent() == BI && "Moved to a different block!");
         ++II;
       }
 
-    // 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.
+      // 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 != II && (I->getParent() != BI || !Worklist.count(I)) &&
+            RankMap[I->getParent()] <= RankMap[BI]) {
           if (isInstructionTriviallyDead(I))
             EraseInst(I);
           else
             OptimizeInst(I);
         }
       }
+    }
+  }
 
   // We are done with the rank map.
   RankMap.clear();
   ValueRankMap.clear();
 
   return MadeChange;
 }

test/Transforms/Reassociate/prev_insts_canonicalized.ll

+; RUN: opt -reassociate -o - -S %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
+}

test/Transforms/Reassociate/reassoc-intermediate-fnegs.ll

 ; RUN: opt < %s -reassociate -S | FileCheck %s
 ; CHECK-LABEL: faddsubAssoc1
-; CHECK: [[TMP1:%tmp.*]] = fmul fast half %a, 0xH4500
-; CHECK: [[TMP2:%tmp.*]] = fmul fast half %b, 0xH4500
-; CHECK: fsub fast half [[TMP2]], [[TMP1]]
+; CHECK: [[TMP1:%.*]] = fsub fast half 0xH8000, %a
+; CHECK: [[TMP2:%.*]] = fadd fast half %b, [[TMP1]]
+; CHECK: fmul fast half [[TMP2]], 0xH4500
 ; CHECK: ret
 ; Input is A op (B op C)
 define half @faddsubAssoc1(half %a, half %b) {
   %tmp1 = fmul fast half %b, 0xH4200 ; 3*b
   %tmp2 = fmul fast half %a, 0xH4500 ; 5*a
   %tmp3 = fmul fast half %b, 0xH4000 ; 2*b
   %tmp4 = fsub fast half %tmp2, %tmp1 ; 5 * a - 3 * b
   %tmp5 = fsub fast half %tmp3, %tmp4 ; 2 * b - ( 5 * a - 3 * b)

test/Transforms/Reassociate/xor_reassoc.ll

 ;  (x | c1) ^ (x & c1) = x ^ c1
 define i32 @xor_special2(i32 %x, i32 %y) {
   %or = or i32 %x, 123
   %xor = xor i32 %or, %y
   %and = and i32 %x, 123
   %xor1 = xor i32 %xor, %and
   ret i32 %xor1
 ; CHECK-LABEL: @xor_special2(
-; CHECK: %xor = xor i32 %x, 123
-; CHECK: %xor1 = xor i32 %xor, %y
+; CHECK: %xor = xor i32 %y, 123
+; CHECK: %xor1 = xor i32 %xor, %x
 ; CHECK: ret i32 %xor1
 }
 
 ; (x | c1) ^ (x | c1) => 0
 define i32 @xor_special3(i32 %x) {
   %or = or i32 %x, 123
   %or1 = or i32 %x, 123
   %xor = xor i32 %or, %or1