1//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "llvm/Transforms/Utils/Local.h" 11#include "llvm/Function.h" 12#include "llvm/Instructions.h" 13#include "llvm/Type.h" 14#include "llvm/ADT/DenseMap.h" 15using namespace llvm; 16 17/// DemoteRegToStack - This function takes a virtual register computed by an 18/// Instruction and replaces it with a slot in the stack frame, allocated via 19/// alloca. This allows the CFG to be changed around without fear of 20/// invalidating the SSA information for the value. It returns the pointer to 21/// the alloca inserted to create a stack slot for I. 22AllocaInst *llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, 23 Instruction *AllocaPoint) { 24 if (I.use_empty()) { 25 I.eraseFromParent(); 26 return 0; 27 } 28 29 // Create a stack slot to hold the value. 30 AllocaInst *Slot; 31 if (AllocaPoint) { 32 Slot = new AllocaInst(I.getType(), 0, 33 I.getName()+".reg2mem", AllocaPoint); 34 } else { 35 Function *F = I.getParent()->getParent(); 36 Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", 37 F->getEntryBlock().begin()); 38 } 39 40 // Change all of the users of the instruction to read from the stack slot. 41 while (!I.use_empty()) { 42 Instruction *U = cast<Instruction>(I.use_back()); 43 if (PHINode *PN = dyn_cast<PHINode>(U)) { 44 // If this is a PHI node, we can't insert a load of the value before the 45 // use. Instead insert the load in the predecessor block corresponding 46 // to the incoming value. 47 // 48 // Note that if there are multiple edges from a basic block to this PHI 49 // node that we cannot have multiple loads. The problem is that the 50 // resulting PHI node will have multiple values (from each load) coming in 51 // from the same block, which is illegal SSA form. For this reason, we 52 // keep track of and reuse loads we insert. 53 DenseMap<BasicBlock*, Value*> Loads; 54 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 55 if (PN->getIncomingValue(i) == &I) { 56 Value *&V = Loads[PN->getIncomingBlock(i)]; 57 if (V == 0) { 58 // Insert the load into the predecessor block 59 V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, 60 PN->getIncomingBlock(i)->getTerminator()); 61 } 62 PN->setIncomingValue(i, V); 63 } 64 65 } else { 66 // If this is a normal instruction, just insert a load. 67 Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U); 68 U->replaceUsesOfWith(&I, V); 69 } 70 } 71 72 73 // Insert stores of the computed value into the stack slot. We have to be 74 // careful if I is an invoke instruction, because we can't insert the store 75 // AFTER the terminator instruction. 76 BasicBlock::iterator InsertPt; 77 if (!isa<TerminatorInst>(I)) { 78 InsertPt = &I; 79 ++InsertPt; 80 } else { 81 // We cannot demote invoke instructions to the stack if their normal edge 82 // is critical. 83 InvokeInst &II = cast<InvokeInst>(I); 84 assert(II.getNormalDest()->getSinglePredecessor() && 85 "Cannot demote invoke with a critical successor!"); 86 InsertPt = II.getNormalDest()->begin(); 87 } 88 89 for (; isa<PHINode>(InsertPt) || isa<LandingPadInst>(InsertPt); ++InsertPt) 90 /* empty */; // Don't insert before PHI nodes or landingpad instrs. 91 92 new StoreInst(&I, Slot, InsertPt); 93 return Slot; 94} 95 96/// DemotePHIToStack - This function takes a virtual register computed by a PHI 97/// node and replaces it with a slot in the stack frame allocated via alloca. 98/// The PHI node is deleted. It returns the pointer to the alloca inserted. 99AllocaInst *llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 100 if (P->use_empty()) { 101 P->eraseFromParent(); 102 return 0; 103 } 104 105 // Create a stack slot to hold the value. 106 AllocaInst *Slot; 107 if (AllocaPoint) { 108 Slot = new AllocaInst(P->getType(), 0, 109 P->getName()+".reg2mem", AllocaPoint); 110 } else { 111 Function *F = P->getParent()->getParent(); 112 Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", 113 F->getEntryBlock().begin()); 114 } 115 116 // Iterate over each operand inserting a store in each predecessor. 117 for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 118 if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) { 119 assert(II->getParent() != P->getIncomingBlock(i) && 120 "Invoke edge not supported yet"); (void)II; 121 } 122 new StoreInst(P->getIncomingValue(i), Slot, 123 P->getIncomingBlock(i)->getTerminator()); 124 } 125 126 // Insert a load in place of the PHI and replace all uses. 127 Value *V = new LoadInst(Slot, P->getName()+".reload", P); 128 P->replaceAllUsesWith(V); 129 130 // Delete PHI. 131 P->eraseFromParent(); 132 return Slot; 133} 134