DemoteRegToStack.cpp revision 894018228b0e0bdbd7aa7e8f47d4a9458789ca82
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, 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocaPoint); 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *F = I.getParent()->getParent(); 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Slot = new AllocaInst(I.getType(), 0, 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 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V = new LoadInst(Slot, 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. 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V = new LoadInst(Slot, VolatileLoads, U); 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman U->replaceUsesOfWith(&I, V); 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert stores of the computed value into the stack slot. 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock::iterator InsertPt = &I; 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++InsertPt; 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (; isa<PHINode>(InsertPt); ++InsertPt) 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /* empty */; // Don't insert before any PHI nodes. 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new StoreInst(&I, Slot, InsertPt); 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Slot; 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// DemotePHIToStack - This function takes a virtual register computed by a phi 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// node and replaces it with a slot in the stack frame, allocated via alloca. 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The phi node is deleted and it returns the pointer to the alloca inserted. 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanAllocaInst* llvm::DemotePHIToStack(PHINode *P, Instruction *AllocaPoint) { 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (P->use_empty()) { 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->eraseFromParent(); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create a stack slot to hold the value. 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocaInst *Slot; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AllocaPoint) { 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Slot = new AllocaInst(P->getType(), 0, 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllocaPoint); 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *F = P->getParent()->getParent(); 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Slot = new AllocaInst(P->getType(), 0, 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman F->getEntryBlock().begin()); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Iterate over each operand, insert store in each predecessor. 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = P->getNumIncomingValues(); i < e; ++i) { 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new StoreInst(P->getIncomingValue(i), Slot, 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->getIncomingBlock(i)->getTerminator()); 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert load in place of the phi and replace all uses. 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *V = new LoadInst(Slot, P); 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->replaceAllUsesWith(V); 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Delete phi. 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->eraseFromParent(); 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Slot; 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 131