1193323Sed//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed 10252723Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 11193323Sed#include "llvm/Transforms/Utils/Local.h" 12235633Sdim#include "llvm/ADT/DenseMap.h" 13263509Sdim#include "llvm/Analysis/CFG.h" 14252723Sdim#include "llvm/IR/Function.h" 15252723Sdim#include "llvm/IR/Instructions.h" 16252723Sdim#include "llvm/IR/Type.h" 17193323Sedusing namespace llvm; 18193323Sed 19193323Sed/// DemoteRegToStack - This function takes a virtual register computed by an 20193323Sed/// Instruction and replaces it with a slot in the stack frame, allocated via 21193323Sed/// alloca. This allows the CFG to be changed around without fear of 22193323Sed/// invalidating the SSA information for the value. It returns the pointer to 23193323Sed/// the alloca inserted to create a stack slot for I. 24235633SdimAllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, 25193323Sed Instruction *AllocaPoint) { 26193323Sed if (I.use_empty()) { 27193323Sed I.eraseFromParent(); 28193323Sed return 0; 29193323Sed } 30210299Sed 31193323Sed // Create a stack slot to hold the value. 32193323Sed AllocaInst *Slot; 33193323Sed if (AllocaPoint) { 34198090Srdivacky Slot = new AllocaInst(I.getType(), 0, 35198090Srdivacky I.getName()+".reg2mem", AllocaPoint); 36193323Sed } else { 37193323Sed Function *F = I.getParent()->getParent(); 38193323Sed Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", 39193323Sed F->getEntryBlock().begin()); 40193323Sed } 41210299Sed 42235633Sdim // Change all of the users of the instruction to read from the stack slot. 43193323Sed while (!I.use_empty()) { 44193323Sed Instruction *U = cast<Instruction>(I.use_back()); 45193323Sed if (PHINode *PN = dyn_cast<PHINode>(U)) { 46193323Sed // If this is a PHI node, we can't insert a load of the value before the 47235633Sdim // use. Instead insert the load in the predecessor block corresponding 48193323Sed // to the incoming value. 49193323Sed // 50193323Sed // Note that if there are multiple edges from a basic block to this PHI 51235633Sdim // node that we cannot have multiple loads. The problem is that the 52235633Sdim // resulting PHI node will have multiple values (from each load) coming in 53235633Sdim // from the same block, which is illegal SSA form. For this reason, we 54235633Sdim // keep track of and reuse loads we insert. 55235633Sdim DenseMap<BasicBlock*, Value*> Loads; 56193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 57193323Sed if (PN->getIncomingValue(i) == &I) { 58193323Sed Value *&V = Loads[PN->getIncomingBlock(i)]; 59193323Sed if (V == 0) { 60193323Sed // Insert the load into the predecessor block 61210299Sed V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, 62193323Sed PN->getIncomingBlock(i)->getTerminator()); 63193323Sed } 64193323Sed PN->setIncomingValue(i, V); 65193323Sed } 66193323Sed 67193323Sed } else { 68193323Sed // If this is a normal instruction, just insert a load. 69193323Sed Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U); 70193323Sed U->replaceUsesOfWith(&I, V); 71193323Sed } 72193323Sed } 73193323Sed 74193323Sed 75235633Sdim // Insert stores of the computed value into the stack slot. We have to be 76235633Sdim // careful if I is an invoke instruction, because we can't insert the store 77235633Sdim // AFTER the terminator instruction. 78193323Sed BasicBlock::iterator InsertPt; 79193323Sed if (!isa<TerminatorInst>(I)) { 80193323Sed InsertPt = &I; 81193323Sed ++InsertPt; 82193323Sed } else { 83193323Sed InvokeInst &II = cast<InvokeInst>(I); 84252723Sdim if (II.getNormalDest()->getSinglePredecessor()) 85252723Sdim InsertPt = II.getNormalDest()->getFirstInsertionPt(); 86252723Sdim else { 87252723Sdim // We cannot demote invoke instructions to the stack if their normal edge 88252723Sdim // is critical. Therefore, split the critical edge and insert the store 89252723Sdim // in the newly created basic block. 90252723Sdim unsigned SuccNum = GetSuccessorNumber(I.getParent(), II.getNormalDest()); 91252723Sdim TerminatorInst *TI = &cast<TerminatorInst>(I); 92252723Sdim assert (isCriticalEdge(TI, SuccNum) && 93252723Sdim "Expected a critical edge!"); 94252723Sdim BasicBlock *BB = SplitCriticalEdge(TI, SuccNum); 95252723Sdim assert (BB && "Unable to split critical edge."); 96252723Sdim InsertPt = BB->getFirstInsertionPt(); 97252723Sdim } 98193323Sed } 99193323Sed 100235633Sdim for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt) 101235633Sdim /* empty */; // Don't insert before PHI nodes or landingpad instrs. 102235633Sdim 103193323Sed new StoreInst(&I, Slot, InsertPt); 104193323Sed return Slot; 105193323Sed} 106193323Sed 107235633Sdim/// DemotePHIToStack - This function takes a virtual register computed by a PHI 108235633Sdim/// node and replaces it with a slot in the stack frame allocated via alloca. 109235633Sdim/// The PHI node is deleted. It returns the pointer to the alloca inserted. 110235633SdimAllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 111193323Sed if (P->use_empty()) { 112210299Sed P->eraseFromParent(); 113210299Sed return 0; 114193323Sed } 115193323Sed 116193323Sed // Create a stack slot to hold the value. 117193323Sed AllocaInst *Slot; 118193323Sed if (AllocaPoint) { 119198090Srdivacky Slot = new AllocaInst(P->getType(), 0, 120198090Srdivacky P->getName()+".reg2mem", AllocaPoint); 121193323Sed } else { 122193323Sed Function *F = P->getParent()->getParent(); 123193323Sed Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", 124193323Sed F->getEntryBlock().begin()); 125193323Sed } 126210299Sed 127235633Sdim // Iterate over each operand inserting a store in each predecessor. 128193323Sed for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 129193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) { 130210299Sed assert(II->getParent() != P->getIncomingBlock(i) && 131218893Sdim "Invoke edge not supported yet"); (void)II; 132193323Sed } 133210299Sed new StoreInst(P->getIncomingValue(i), Slot, 134193323Sed P->getIncomingBlock(i)->getTerminator()); 135193323Sed } 136210299Sed 137235633Sdim // Insert a load in place of the PHI and replace all uses. 138252723Sdim BasicBlock::iterator InsertPt = P; 139252723Sdim 140252723Sdim for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt) 141252723Sdim /* empty */; // Don't insert before PHI nodes or landingpad instrs. 142252723Sdim 143252723Sdim Value *V = new LoadInst(Slot, P->getName()+".reload", InsertPt); 144193323Sed P->replaceAllUsesWith(V); 145210299Sed 146235633Sdim // Delete PHI. 147193323Sed P->eraseFromParent(); 148193323Sed return Slot; 149193323Sed} 150