Replace the SSA update code in LCSSA with a bottom-up approach instead of a top

down approach, inspired by discussions with Tanya.

This approach is significantly faster, because it does not need dominator
frontiers and it does not insert extraneous unused PHI nodes.  For example, on
252.eon, in a release-asserts build, this speeds up LCSSA (which is the slowest
pass in gccas) from 9.14s to 0.74s on my G5.  This code is also slightly smaller
and significantly simpler than the old code.

Amusingly, in a normal Release build (which includes the
"assert(L->isLCSSAForm());" assertion), asserting that the result of LCSSA
is in LCSSA form is actually slower than the LCSSA transformation pass
itself on 252.eon.  I will see if Loop::isLCSSAForm can be sped up next.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29463 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 95 insertions, 125 deletions

diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index 51e8454095..43c9678cd0 100644
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -46,18 +46,15 @@ namespace {
   static Statistic<> NumLCSSA("lcssa",
                               "Number of live out of a loop variables");
   
-  class LCSSA : public FunctionPass {
-  public:
-    
-  
-    LoopInfo *LI;  // Loop information
-    DominatorTree *DT;       // Dominator Tree for the current Function...
-    DominanceFrontier *DF;   // Current Dominance Frontier
+  struct LCSSA : public FunctionPass {
+    // Cached analysis information for the current function.
+    LoopInfo *LI;
+    DominatorTree *DT;
     std::vector<BasicBlock*> LoopBlocks;
     
     virtual bool runOnFunction(Function &F);
     bool visitSubloop(Loop* L);
-    void processInstruction(Instruction* Instr,
+    void ProcessInstruction(Instruction* Instr,
                             const std::vector<BasicBlock*>& exitBlocks);
     
     /// This transformation requires natural loop information & requires that
@@ -70,17 +67,13 @@ namespace {
       AU.addPreservedID(LoopSimplifyID);
       AU.addRequired<LoopInfo>();
       AU.addRequired<DominatorTree>();
-      AU.addRequired<DominanceFrontier>();
     }
   private:
     SetVector<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L);
-    Value *getValueDominatingBlock(BasicBlock *BB,
-                                 std::map<BasicBlock*, Value*>& PotDoms) {
-      return getValueDominatingDTNode(DT->getNode(BB), PotDoms);
-    }
-    Value *getValueDominatingDTNode(DominatorTree::Node *Node,
-                                  std::map<BasicBlock*, Value*>& PotDoms);
-                                      
+
+    PHINode *GetValueForBlock(DominatorTree::Node *BB, Instruction *OrigInst,
+                              std::map<DominatorTree::Node*, PHINode*> &Phis);
+
     /// inLoop - returns true if the given block is within the current loop
     const bool inLoop(BasicBlock* B) {
       return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B);
@@ -98,12 +91,10 @@ bool LCSSA::runOnFunction(Function &F) {
   bool changed = false;
   
   LI = &getAnalysis<LoopInfo>();
-  DF = &getAnalysis<DominanceFrontier>();
   DT = &getAnalysis<DominatorTree>();
     
-  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
+  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
     changed |= visitSubloop(*I);
-  }
       
   return changed;
 }
@@ -134,9 +125,8 @@ bool LCSSA::visitSubloop(Loop* L) {
   // for them in the appropriate exit blocks
   
   for (SetVector<Instruction*>::iterator I = AffectedValues.begin(),
-       E = AffectedValues.end(); I != E; ++I) {
-    processInstruction(*I, exitBlocks);
-  }
+       E = AffectedValues.end(); I != E; ++I)
+    ProcessInstruction(*I, exitBlocks);
   
   assert(L->isLCSSAForm());
   
@@ -145,105 +135,62 @@ bool LCSSA::visitSubloop(Loop* L) {
 
 /// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes,
 /// eliminate all out-of-loop uses.
-void LCSSA::processInstruction(Instruction* Instr,
-                               const std::vector<BasicBlock*>& exitBlocks)
-{
+void LCSSA::ProcessInstruction(Instruction *Instr,
+                               const std::vector<BasicBlock*>& exitBlocks) {
   ++NumLCSSA; // We are applying the transformation
-  
-  std::map<BasicBlock*, Value*> Phis;
-  
-  // Add the base instruction to the Phis list.  This makes tracking down
-  // the dominating values easier when we're filling in Phi nodes.  This will
-  // be removed later, before we perform use replacement.
-  Phis[Instr->getParent()] = Instr;
-  
-  // Phi nodes that need to be IDF-processed
-  std::vector<PHINode*> workList;
-  
+
+  // Keep track of the blocks that have the value available already.
+  std::map<DominatorTree::Node*, PHINode*> Phis;
+
+  DominatorTree::Node *InstrNode = DT->getNode(Instr->getParent());
+
+  // Insert the LCSSA phi's into the exit blocks (dominated by the value), and
+  // add them to the Phi's map.
   for (std::vector<BasicBlock*>::const_iterator BBI = exitBlocks.begin(),
       BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
-    Value*& phi = Phis[*BBI];
-    if (phi == 0 &&
-        DT->getNode(Instr->getParent())->dominates(DT->getNode(*BBI))) {
-      phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa",
-                                 (*BBI)->begin());
-      workList.push_back(cast<PHINode>(phi));
-    }
-  }
-  
-  // Phi nodes that need to have their incoming values filled.
-  std::vector<PHINode*> needIncomingValues;
-  
-  // Calculate the IDF of these LCSSA Phi nodes, inserting new Phi's where
-  // necessary.  Keep track of these new Phi's in the "Phis" map.
-  while (!workList.empty()) {
-    PHINode *CurPHI = workList.back();
-    workList.pop_back();
-    
-    // Even though we've removed this Phi from the work list, we still need
-    // to fill in its incoming values.
-    needIncomingValues.push_back(CurPHI);
-    
-    // Get the current Phi's DF, and insert Phi nodes.  Add these new
-    // nodes to our worklist.
-    DominanceFrontier::const_iterator it = DF->find(CurPHI->getParent());
-    if (it != DF->end()) {
-      const DominanceFrontier::DomSetType &S = it->second;
-      for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
-           PE = S.end(); P != PE; ++P) {
-        if (DT->getNode(Instr->getParent())->dominates(DT->getNode(*P))) {
-          Value *&Phi = Phis[*P];
-          if (Phi == 0) {
-            // Still doesn't have operands...
-            Phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa",
-                              (*P)->begin());
-          
-            workList.push_back(cast<PHINode>(Phi));
-          }
-        }
-      }
+    BasicBlock *BB = *BBI;
+    DominatorTree::Node *ExitBBNode = DT->getNode(BB);
+    PHINode *&Phi = Phis[ExitBBNode];
+    if (!Phi && InstrNode->dominates(ExitBBNode)) {
+      Phi = new PHINode(Instr->getType(), Instr->getName()+".lcssa",
+                        BB->begin());
+      Phi->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
+
+      // Add inputs from inside the loop for this PHI.
+      for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+        Phi->addIncoming(Instr, *PI);
+      
+      // Remember that this phi makes the value alive in this block.
+      Phis[ExitBBNode] = Phi;
     }
   }
   
-  // Fill in all Phis we've inserted that need their incoming values filled in.
-  for (std::vector<PHINode*>::iterator IVI = needIncomingValues.begin(),
-       IVE = needIncomingValues.end(); IVI != IVE; ++IVI)
-    for (pred_iterator PI = pred_begin((*IVI)->getParent()),
-         E = pred_end((*IVI)->getParent()); PI != E; ++PI)
-      (*IVI)->addIncoming(getValueDominatingBlock(*PI, Phis),
-                          *PI);
   
-  // Find all uses of the affected value, and replace them with the
-  // appropriate Phi.
-  std::vector<Instruction*> Uses;
-  for (Instruction::use_iterator UI = Instr->use_begin(), UE = Instr->use_end();
-       UI != UE; ++UI) {
-    Instruction* use = cast<Instruction>(*UI);
-    BasicBlock* UserBB = use->getParent();
-    if (PHINode* p = dyn_cast<PHINode>(use)) {
+  // Record all uses of Instr outside the loop.  We need to rewrite these.  The
+  // LCSSA phis won't be included because they use the value in the loop.
+  for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end();
+       UI != E;) {
+    BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
+    if (PHINode *P = dyn_cast<PHINode>(*UI)) {
       unsigned OperandNo = UI.getOperandNo();
-      UserBB = p->getIncomingBlock(OperandNo/2);
+      UserBB = P->getIncomingBlock(OperandNo/2);
     }
     
-    // Don't need to update uses within the loop body.
-    if (!inLoop(use->getParent()))
-      Uses.push_back(use);
-  }
-  
-  for (std::vector<Instruction*>::iterator II = Uses.begin(), IE = Uses.end();
-       II != IE; ++II) {
-    if (PHINode* phi = dyn_cast<PHINode>(*II)) {
-      for (unsigned int i = 0; i < phi->getNumIncomingValues(); ++i) {
-        if (phi->getIncomingValue(i) == Instr) {
-          Value* dominator = 
-                        getValueDominatingBlock(phi->getIncomingBlock(i), Phis);
-          phi->setIncomingValue(i, dominator);
-        }
-      }
-    } else {
-      Value *NewVal = getValueDominatingBlock((*II)->getParent(), Phis);
-      (*II)->replaceUsesOfWith(Instr, NewVal);
+    // If the user is in the loop, don't rewrite it!
+    if (inLoop(UserBB)) {
+      ++UI;
+      continue;
     }
+    
+    // Otherwise, patch up uses of the value with the appropriate LCSSA Phi,
+    // inserting PHI nodes into join points where needed.
+    Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis);
+    
+    // Preincrement the iterator to avoid invalidating it when we change the
+    // value.
+    Use &U = UI.getUse();
+    ++UI;
+    U.set(Val);
   }
 }
 
@@ -277,21 +224,44 @@ SetVector<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L) {
   return AffectedValues;
 }
 
-/// getValueDominatingBlock - Return the value within the potential dominators
-/// map that dominates the given block.
-Value *LCSSA::getValueDominatingDTNode(DominatorTree::Node *Node,
-                              std::map<BasicBlock*, Value*>& PotDoms) {
-  // FIXME: The following assertion should be in place rather than the if
-  // statement.  Currently, this is due to the fact that LCSSA isn't smart 
-  // enough to avoid inserting IDF Phis that don't dominate any uses.  In some 
-  // of those cases, it could ask us to provide a dominating value for a block
-  // that has none, so we need to return undef.
-  //assert(Node != 0 && "Didn't find dom value?");
-  if (Node == 0) return UndefValue::get(PotDoms.begin()->second->getType());
+/// GetValueForBlock - Get the value to use within the specified basic block.
+/// available values are in Phis.
+PHINode *LCSSA::GetValueForBlock(DominatorTree::Node *BB, Instruction *OrigInst,
+                               std::map<DominatorTree::Node*, PHINode*> &Phis) {
+  // If we have already computed this value, return the previously computed val.
+  PHINode *&V = Phis[BB];
+  if (V) return V;
+
+  DominatorTree::Node *IDom = BB->getIDom();
+
+  // Otherwise, there are two cases: we either have to insert a PHI node or we
+  // don't.  We need to insert a PHI node if this block is not dominated by one
+  // of the exit nodes from the loop (the loop could have multiple exits, and
+  // though the value defined *inside* the loop dominated all its uses, each
+  // exit by itself may not dominate all the uses).
+  //
+  // The simplest way to check for this condition is by checking to see if the
+  // idom is in the loop.  If so, we *know* that none of the exit blocks
+  // dominate this block.  Note that we *know* that the block defining the
+  // original instruction is in the idom chain, because if it weren't, then the
+  // original value didn't dominate this use.
+  if (!inLoop(IDom->getBlock())) {
+    // Idom is not in the loop, we must still be "below" the exit block and must
+    // be fully dominated by the value live in the idom.
+    return V = GetValueForBlock(IDom, OrigInst, Phis);
+  }
   
-  Value *&CacheSlot = PotDoms[Node->getBlock()];
-  if (CacheSlot) return CacheSlot;
+  BasicBlock *BBN = BB->getBlock();
   
-  // Otherwise, return the value of the idom and remember this for next time.
-  return CacheSlot = getValueDominatingDTNode(Node->getIDom(), PotDoms);
+  // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
+  // now, then get values to fill in the incoming values for the PHI.
+  V = new PHINode(OrigInst->getType(), OrigInst->getName()+".lcssa",
+                  BBN->begin());
+  V->reserveOperandSpace(std::distance(pred_begin(BBN), pred_end(BBN)));
+
+  // Fill in the incoming values for the block.
+  for (pred_iterator PI = pred_begin(BBN), E = pred_end(BBN); PI != E; ++PI)
+    V->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI);
+  return V;
 }
+