lib/Transforms/Utils/DemoteRegToStack.cpp

   1 //===- DemoteRegToStack.cpp - Move a virtual reg. to stack ----------------===//
   2 //
   3 // This file provide the function DemoteRegToStack().  This function takes a
   4 // virtual register computed by an Instruction& X and replaces it with a slot in
   5 // the stack frame, allocated via alloca. It returns the pointer to the
   6 // AllocaInst inserted.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Transforms/Utils/DemoteRegToStack.h"
  11 #include "llvm/Function.h"
  12 #include "llvm/iMemory.h"
  13 #include "llvm/iPHINode.h"
  14 #include "llvm/iTerminators.h"
  15 #include "llvm/Type.h"
  16 #include "Support/hash_set"
  17 #include <stack>
  18
  19 typedef hash_set<PHINode*>           PhiSet;
  20 typedef hash_set<PHINode*>::iterator PhiSetIterator;
  21
  22 // Helper function to push a phi *and* all its operands to the worklist!
  23 // Do not push an instruction if it is already in the result set of Phis to go.
  24 inline void PushOperandsOnWorkList(std::stack<Instruction*>& workList,
  25                                    PhiSet& phisToGo, PHINode* phiN) {
  26   for (User::op_iterator OI = phiN->op_begin(), OE = phiN->op_end();
  27        OI != OE; ++OI)
  28     if (Instruction* opI = dyn_cast<Instruction>(OI))
  29       if (!isa<PHINode>(opI) ||
  30           phisToGo.find(cast<PHINode>(opI)) == phisToGo.end())
  31         workList.push(opI);
  32 }
  33
  34 static void FindPhis(Instruction& X, PhiSet& phisToGo) {
  35   std::stack<Instruction*> workList;
  36   workList.push(&X);
  37
  38   // Handle the case that X itself is a Phi!
  39   if (PHINode* phiX = dyn_cast<PHINode>(&X)) {
  40     phisToGo.insert(phiX);
  41     PushOperandsOnWorkList(workList, phisToGo, phiX);
  42   }
  43
  44   // Now use a worklist to find all phis reachable from X, and
  45   // (recursively) all phis reachable from operands of such phis.
  46   for (Instruction* workI; !workList.empty(); workList.pop()) {
  47     workI = workList.top();
  48     for (Value::use_iterator UI=workI->use_begin(), UE=workI->use_end();
  49          UI != UE; ++UI)
  50       if (PHINode* phiN = dyn_cast<PHINode>(*UI))
  51         if (phisToGo.find(phiN) == phisToGo.end()) {
  52           // Seeing this phi for the first time: it must go!
  53           phisToGo.insert(phiN);
  54           workList.push(phiN);
  55           PushOperandsOnWorkList(workList, phisToGo, phiN);
  56         }
  57   }
  58 }
  59
  60
  61 // Create the Alloca for X
  62 static AllocaInst* CreateAllocaForX(Instruction& X) {
  63   Function* parentFunc = X.getParent()->getParent();
  64   Instruction* entryInst = parentFunc->getEntryBlock().begin();
  65   return new AllocaInst(X.getType(), /*arraySize*/ NULL,
  66                         X.hasName()? X.getName()+std::string("OnStack")
  67                                    : "DemotedTmp",
  68                         entryInst);
  69 }
  70
  71 // Insert loads before all uses of I, except uses in Phis
  72 // since all such Phis *must* be deleted.
  73 static void LoadBeforeUses(Instruction* def, AllocaInst* XSlot) {
  74   for (unsigned nPhis = 0; def->use_size() - nPhis > 0; ) {
  75       Instruction* useI = cast<Instruction>(def->use_back());
  76       if (!isa<PHINode>(useI)) {
  77         LoadInst* loadI =
  78           new LoadInst(XSlot, std::string("Load")+XSlot->getName(), useI);
  79         useI->replaceUsesOfWith(def, loadI);
  80       } else
  81         ++nPhis;
  82   }
  83 }
  84
  85 static void AddLoadsAndStores(AllocaInst* XSlot, Instruction& X,
  86                               PhiSet& phisToGo) {
  87   for (PhiSetIterator PI=phisToGo.begin(), PE=phisToGo.end(); PI != PE; ++PI) {
  88     PHINode* pn = *PI;
  89
  90     // First, insert loads before all uses except uses in Phis.
  91     // Do this first because new stores will appear as uses also!
  92     LoadBeforeUses(pn, XSlot);
  93
  94     // For every incoming operand of the Phi, insert a store either
  95     // just after the instruction defining the value or just before the
  96     // predecessor of the Phi if the value is a formal, not an instruction.
  97     //
  98     for (unsigned i=0, N=pn->getNumIncomingValues(); i < N; ++i) {
  99       Value* phiOp = pn->getIncomingValue(i);
 100       if (phiOp != &X &&
 101           (!isa<PHINode>(phiOp) ||
 102            phisToGo.find(cast<PHINode>(phiOp)) == phisToGo.end())) {
 103         // This operand is not a phi that will be deleted: need to store.
 104         assert(!isa<TerminatorInst>(phiOp));
 105
 106         Instruction* storeBefore;
 107         if (Instruction* I = dyn_cast<Instruction>(phiOp)) {
 108           // phiOp is an instruction, store its result right after it.
 109           assert(I->getNext() && "Non-terminator without successor?");
 110           storeBefore = I->getNext();
 111         } else {
 112           // If not, it must be a formal: store it at the end of the
 113           // predecessor block of the Phi (*not* at function entry!).
 114           storeBefore = pn->getIncomingBlock(i)->getTerminator();
 115         }
 116
 117         // Create instr. to store the value of phiOp before `insertBefore'
 118         StoreInst* storeI = new StoreInst(phiOp, XSlot, storeBefore);
 119       }
 120     }
 121   }
 122 }
 123
 124 static void DeletePhis(PhiSet& phisToGo) {
 125   for (PhiSetIterator PI = phisToGo.begin(), PE =phisToGo.end(); PI != PE; ++PI)
 126     (*PI)->getParent()->getInstList().erase(*PI);
 127   phisToGo.clear();
 128 }
 129
 130 //----------------------------------------------------------------------------
 131 // function DemoteRegToStack()
 132 //
 133 // This function takes a virtual register computed by an
 134 // Instruction& X and replaces it with a slot in the stack frame,
 135 // allocated via alloca.  It has to:
 136 // (1) Identify all Phi operations that have X as an operand and
 137 //     transitively other Phis that use such Phis;
 138 // (2) Store all values merged with X via Phi operations to the stack slot;
 139 // (3) Load the value from the stack slot just before any use of X or any
 140 //     of the Phis that were eliminated; and
 141 // (4) Delete all the Phis, which should all now be dead.
 142 //
 143 // Returns the pointer to the alloca inserted to create a stack slot for X.
 144 //----------------------------------------------------------------------------
 145
 146 AllocaInst* DemoteRegToStack(Instruction& X) {
 147   if (X.getType() == Type::VoidTy)
 148     return NULL;                             // nothing to do!
 149
 150   // Find all Phis involving X or recursively using such Phis or Phis
 151   // involving operands of such Phis (essentially all Phis in the "web" of X)
 152   PhiSet phisToGo;
 153   FindPhis(X, phisToGo);
 154
 155   // Create a stack slot to hold X
 156   AllocaInst* XSlot = CreateAllocaForX(X);
 157
 158   // Insert loads before all uses of X and (*only then*) insert store after X
 159   assert(X.getNext() && "Non-terminator (since non-void) with no successor?");
 160   LoadBeforeUses(&X, XSlot);
 161   StoreInst* storeI = new StoreInst(&X, XSlot, X.getNext());
 162
 163   // Do the same for all the phis that will be deleted
 164   AddLoadsAndStores(XSlot, X, phisToGo);
 165
 166   // Delete the phis and return the alloca instruction
 167   DeletePhis(phisToGo);
 168   return XSlot;
 169 }