1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file provide the function DemoteRegToStack(). This function takes a 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// virtual register computed by an Instruction and replaces it with a slot in 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// the stack frame, allocated via alloca. It returns the pointer to the 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// AllocaInst inserted. After this function is called on an instruction, we are 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// guaranteed that the only user of the instruction is a store that is 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// immediately after it. 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/Local.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Function.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Type.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <map> 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// DemoteRegToStack - This function takes a virtual register computed by an 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Instruction and replaces it with a slot in the stack frame, allocated via 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// alloca. This allows the CFG to be changed around without fear of 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// invalidating the SSA information for the value. It returns the pointer to 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the alloca inserted to create a stack slot for I. 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAllocaInst* llvm::DemoteRegToStack(Instruction &I, bool VolatileLoads, 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *AllocaPoint) { 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I.use_empty()) { 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I.eraseFromParent(); 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create a stack slot to hold the value. 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocaInst *Slot; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AllocaPoint) { 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Slot = new AllocaInst(I.getType(), 0, 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I.getName()+".reg2mem", AllocaPoint); 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *F = I.getParent()->getParent(); 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Slot = new AllocaInst(I.getType(), 0, I.getName()+".reg2mem", 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman F->getEntryBlock().begin()); 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Change all of the users of the instruction to read from the stack slot 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instead. 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (!I.use_empty()) { 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *U = cast<Instruction>(I.use_back()); 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PHINode *PN = dyn_cast<PHINode>(U)) { 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a PHI node, we can't insert a load of the value before the 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // use. Instead, insert the load in the predecessor block corresponding 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to the incoming value. 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that if there are multiple edges from a basic block to this PHI 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // node that we cannot multiple loads. The problem is that the resultant 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // PHI node will have multiple values (from each load) coming in from the 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // same block, which is illegal SSA form. For this reason, we keep track 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and reuse loads we insert. 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::map<BasicBlock*, Value*> Loads; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PN->getIncomingValue(i) == &I) { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *&V = Loads[PN->getIncomingBlock(i)]; 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V == 0) { 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert the load into the predecessor block 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->getIncomingBlock(i)->getTerminator()); 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PN->setIncomingValue(i, V); 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a normal instruction, just insert a load. 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *V = new LoadInst(Slot, I.getName()+".reload", VolatileLoads, U); 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman U->replaceUsesOfWith(&I, V); 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert stores of the computed value into the stack slot. We have to be 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // careful is I is an invoke instruction though, because we can't insert the 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // store AFTER the terminator instruction. 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator InsertPt; 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isa<TerminatorInst>(I)) { 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertPt = &I; 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++InsertPt; 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We cannot demote invoke instructions to the stack if their normal edge 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // is critical. 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InvokeInst &II = cast<InvokeInst>(I); 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(II.getNormalDest()->getSinglePredecessor() && 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Cannot demote invoke with a critical successor!"); 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertPt = II.getNormalDest()->begin(); 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (; isa<PHINode>(InsertPt); ++InsertPt) 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /* empty */; // Don't insert before any PHI nodes. 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new StoreInst(&I, Slot, InsertPt); 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Slot; 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// DemotePHIToStack - This function takes a virtual register computed by a phi 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// node and replaces it with a slot in the stack frame, allocated via alloca. 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The phi node is deleted and it returns the pointer to the alloca inserted. 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAllocaInst* llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (P->use_empty()) { 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->eraseFromParent(); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create a stack slot to hold the value. 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocaInst *Slot; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AllocaPoint) { 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Slot = new AllocaInst(P->getType(), 0, 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P->getName()+".reg2mem", AllocaPoint); 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *F = P->getParent()->getParent(); 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Slot = new AllocaInst(P->getType(), 0, P->getName()+".reg2mem", 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman F->getEntryBlock().begin()); 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Iterate over each operand, insert store in each predecessor. 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (InvokeInst *II = dyn_cast<InvokeInst>(P->getIncomingValue(i))) { 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(II->getParent() != P->getIncomingBlock(i) && 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Invoke edge not supported yet"); (void)II; 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new StoreInst(P->getIncomingValue(i), Slot, 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->getIncomingBlock(i)->getTerminator()); 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert load in place of the phi and replace all uses. 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Value *V = new LoadInst(Slot, P->getName()+".reload", P); 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->replaceAllUsesWith(V); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Delete phi. 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->eraseFromParent(); 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Slot; 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 147