lib/Transforms/Utils/DemoteRegToStack.cpp

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