From 2351abaeab89ef0a0df5a715d0794ed5dec48bb3 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 3 Aug 2005 22:51:21 +0000
Subject: [PATCH] Move from Stage 0 to Stage 1.

Only emit one PHI node for IV uses with identical bases and strides (after
moving foldable immediates to the load/store instruction).

This implements LoopStrengthReduce/dont_insert_redundant_ops.ll, allowing
us to generate this PPC code for test1:

        or r30, r3, r3
.LBB_test1_1:   ; Loop
        li r2, 0
        stw r2, 0(r30)
        stw r2, 4(r30)
        bl L_pred$stub
        addi r30, r30, 8
        cmplwi cr0, r3, 0
        bne .LBB_test1_1        ; Loop

instead of this code:

        or r30, r3, r3
        or r29, r3, r3
.LBB_test1_1:   ; Loop
        li r2, 0
        stw r2, 0(r29)
        stw r2, 4(r30)
        bl L_pred$stub
        addi r30, r30, 8        ;; Two iv's with step of 8
        addi r29, r29, 8
        cmplwi cr0, r3, 0
        bne .LBB_test1_1        ; Loop


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@22635 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/LoopStrengthReduce.cpp | 66 +++++++++++---------
 1 file changed, 35 insertions(+), 31 deletions(-)

diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index fd2a52148ee..27d0e5c667d 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -554,24 +554,25 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(Value *Stride,
    SomeLoopPHI->getIncomingBlock(SomeLoopPHI->getIncomingBlock(0) == Preheader);
 
   // FIXME: This loop needs increasing levels of intelligence.
-  // STAGE 0: just emit everything as its own base.  <-- We are here
+  // STAGE 0: just emit everything as its own base.
   // STAGE 1: factor out common vars from bases, and try and push resulting
-  //          constants into Imm field.
+  //          constants into Imm field.  <-- We are here
   // STAGE 2: factor out large constants to try and make more constants
   //          acceptable for target loads and stores.
-  std::sort(UsersToProcess.begin(), UsersToProcess.end());
 
+  // Sort by the base value, so that all IVs with identical bases are next to
+  // each other.  
+  std::sort(UsersToProcess.begin(), UsersToProcess.end());
   while (!UsersToProcess.empty()) {
+    SCEVHandle Base = UsersToProcess.front().first;
+    
     // Create a new Phi for this base, and stick it in the loop header.
-    Value *Replaced = UsersToProcess.front().second.OperandValToReplace;
-    const Type *ReplacedTy = Replaced->getType();
-    PHINode *NewPHI = new PHINode(ReplacedTy, Replaced->getName()+".str",
-                                  PhiInsertBefore);
+    const Type *ReplacedTy = Base->getType();
+    PHINode *NewPHI = new PHINode(ReplacedTy, "iv.", PhiInsertBefore);
 
     // Emit the initial base value into the loop preheader, and add it to the
     // Phi node.
-    Value *BaseV = Rewriter.expandCodeFor(UsersToProcess.front().first,
-                                          PreInsertPt, ReplacedTy);
+    Value *BaseV = Rewriter.expandCodeFor(Base, PreInsertPt, ReplacedTy);
     NewPHI->addIncoming(BaseV, Preheader);
 
     // Emit the increment of the base value before the terminator of the loop
@@ -585,28 +586,31 @@ void LoopStrengthReduce::StrengthReduceStridedIVUsers(Value *Stride,
     NewPHI->addIncoming(IncV, LatchBlock);
 
     // Emit the code to add the immediate offset to the Phi value, just before
-    // the instruction that we identified as using this stride and base.
-    // First, empty the SCEVExpander's expression map  so that we are guaranteed
-    // to have the code emitted where we expect it.
-    Rewriter.clear();
-    SCEVHandle NewValSCEV = SCEVAddExpr::get(SCEVUnknown::get(NewPHI),
-                                             UsersToProcess.front().second.Imm);
-    Value *newVal = Rewriter.expandCodeFor(NewValSCEV,
-                                           UsersToProcess.front().second.Inst,
-                                           ReplacedTy);
-
-    // Replace the use of the operand Value with the new Phi we just created.
-    DEBUG(std::cerr << "REPLACING: " << *Replaced << "IN: " <<
-          *UsersToProcess.front().second.Inst << "WITH: "<< *newVal << '\n');
-    UsersToProcess.front().second.Inst->replaceUsesOfWith(Replaced, newVal);
-
-    // Mark old value we replaced as possibly dead, so that it is elminated
-    // if we just replaced the last use of that value.
-    DeadInsts.insert(cast<Instruction>(Replaced));
-
-    UsersToProcess.erase(UsersToProcess.begin());
-    ++NumReduced;
-
+    // the instructions that we identified as using this stride and base.
+    while (!UsersToProcess.empty() && UsersToProcess.front().first == Base) {
+      BasedUser &User = UsersToProcess.front().second;
+
+      // Clear the SCEVExpander's expression map so that we are guaranteed
+      // to have the code emitted where we expect it.
+      Rewriter.clear();
+      SCEVHandle NewValSCEV = SCEVAddExpr::get(SCEVUnknown::get(NewPHI),
+                                               User.Imm);
+      Value *Replaced = UsersToProcess.front().second.OperandValToReplace;
+      Value *newVal = Rewriter.expandCodeFor(NewValSCEV, User.Inst,
+                                             Replaced->getType());
+
+      // Replace the use of the operand Value with the new Phi we just created.
+      DEBUG(std::cerr << "REPLACING: " << *Replaced << "IN: " <<
+            *User.Inst << "WITH: "<< *newVal << '\n');
+      User.Inst->replaceUsesOfWith(Replaced, newVal);
+
+      // Mark old value we replaced as possibly dead, so that it is elminated
+      // if we just replaced the last use of that value.
+      DeadInsts.insert(cast<Instruction>(Replaced));
+
+      UsersToProcess.erase(UsersToProcess.begin());
+      ++NumReduced;
+    }
     // TODO: Next, find out which base index is the most common, pull it out.
   }
 
-- 
2.34.1