LLVM API Documentation

DemoteRegToStack.cpp

Go to the documentation of this file.
00001 //===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file provide the function DemoteRegToStack().  This function takes a
00011 // virtual register computed by an Instruction and replaces it with a slot in
00012 // the stack frame, allocated via alloca. It returns the pointer to the
00013 // AllocaInst inserted.  After this function is called on an instruction, we are
00014 // guaranteed that the only user of the instruction is a store that is
00015 // immediately after it.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #include "llvm/Transforms/Utils/Local.h"
00020 #include "llvm/Function.h"
00021 #include "llvm/Instructions.h"
00022 #include "llvm/Type.h"
00023 #include <map>
00024 using namespace llvm;
00025 
00026 /// DemoteRegToStack - This function takes a virtual register computed by an
00027 /// Instruction and replaces it with a slot in the stack frame, allocated via
00028 /// alloca.  This allows the CFG to be changed around without fear of
00029 /// invalidating the SSA information for the value.  It returns the pointer to
00030 /// the alloca inserted to create a stack slot for I.
00031 ///
00032 AllocaInst* llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads,
00033                                    Instruction *AllocaPoint) {
00034   if (I.use_empty()) {
00035     I.eraseFromParent();
00036     return 0;
00037   }
00038   
00039   // Create a stack slot to hold the value.
00040   AllocaInst *Slot;
00041   if (AllocaPoint) {
00042     Slot = new AllocaInst(I.getType(), 0,
00043                           I.getName()+".reg2mem", AllocaPoint);
00044   } else {
00045     Function *F = I.getParent()->getParent();
00046     Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem",
00047                           F->getEntryBlock().begin());
00048   }
00049   
00050   // Change all of the users of the instruction to read from the stack slot
00051   // instead.
00052   while (!I.use_empty()) {
00053     Instruction *U = cast<Instruction>(I.use_back());
00054     if (PHINode *PN = dyn_cast<PHINode>(U)) {
00055       // If this is a PHI node, we can't insert a load of the value before the
00056       // use.  Instead, insert the load in the predecessor block corresponding
00057       // to the incoming value.
00058       //
00059       // Note that if there are multiple edges from a basic block to this PHI
00060       // node that we cannot multiple loads.  The problem is that the resultant
00061       // PHI node will have multiple values (from each load) coming in from the
00062       // same block, which is illegal SSA form.  For this reason, we keep track
00063       // and reuse loads we insert.
00064       std::map<BasicBlock*, Value*> Loads;
00065       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00066         if (PN->getIncomingValue(i) == &I) {
00067           Value *&V = Loads[PN->getIncomingBlock(i)];
00068           if (V == 0) {
00069             // Insert the load into the predecessor block
00070             V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, 
00071                              PN->getIncomingBlock(i)->getTerminator());
00072           }
00073           PN->setIncomingValue(i, V);
00074         }
00075 
00076     } else {
00077       // If this is a normal instruction, just insert a load.
00078       Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U);
00079       U->replaceUsesOfWith(&I, V);
00080     }
00081   }
00082 
00083 
00084   // Insert stores of the computed value into the stack slot.  We have to be
00085   // careful is I is an invoke instruction though, because we can't insert the
00086   // store AFTER the terminator instruction.
00087   BasicBlock::iterator InsertPt;
00088   if (!isa<TerminatorInst>(I)) {
00089     InsertPt = &I;
00090     ++InsertPt;
00091   } else {
00092     // We cannot demote invoke instructions to the stack if their normal edge
00093     // is critical.
00094     InvokeInst &II = cast<InvokeInst>(I);
00095     assert(II.getNormalDest()->getSinglePredecessor() &&
00096            "Cannot demote invoke with a critical successor!");
00097     InsertPt = II.getNormalDest()->begin();
00098   }
00099 
00100   for (; isa<PHINode>(InsertPt); ++InsertPt)
00101   /* empty */;   // Don't insert before any PHI nodes.
00102   new StoreInst(&I, Slot, InsertPt);
00103 
00104   return Slot;
00105 }
00106 
00107 
00108 /// DemotePHIToStack - This function takes a virtual register computed by a phi
00109 /// node and replaces it with a slot in the stack frame, allocated via alloca.
00110 /// The phi node is deleted and it returns the pointer to the alloca inserted.
00111 AllocaInst* llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) {
00112   if (P->use_empty()) {
00113     P->eraseFromParent();    
00114     return 0;                
00115   }
00116 
00117   // Create a stack slot to hold the value.
00118   AllocaInst *Slot;
00119   if (AllocaPoint) {
00120     Slot = new AllocaInst(P->getType(), 0,
00121                           P->getName()+".reg2mem", AllocaPoint);
00122   } else {
00123     Function *F = P->getParent()->getParent();
00124     Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem",
00125                           F->getEntryBlock().begin());
00126   }
00127   
00128   // Iterate over each operand, insert store in each predecessor.
00129   for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) {
00130     if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) {
00131       assert(II->getParent() != P->getIncomingBlock(i) && 
00132              "Invoke edge not supported yet"); II=II;
00133     }
00134     new StoreInst(P->getIncomingValue(i), Slot, 
00135                   P->getIncomingBlock(i)->getTerminator());
00136   }
00137   
00138   // Insert load in place of the phi and replace all uses.
00139   Value *V = new LoadInst(Slot, P->getName()+".reload", P);
00140   P->replaceAllUsesWith(V);
00141   
00142   // Delete phi.
00143   P->eraseFromParent();
00144   
00145   return Slot;
00146 }