lib/Transforms/Utils/DemoteRegToStack.cpp

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