Reg2Mem.cpp revision 193323
1193323Sed//===- Reg2Mem.cpp - Convert registers to allocas -------------------------===// 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// 10193323Sed// This file demotes all registers to memory references. It is intented to be 11193323Sed// the inverse of PromoteMemoryToRegister. By converting to loads, the only 12193323Sed// values live accross basic blocks are allocas and loads before phi nodes. 13193323Sed// It is intended that this should make CFG hacking much easier. 14193323Sed// To make later hacking easier, the entry block is split into two, such that 15193323Sed// all introduced allocas and nothing else are in the entry block. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19193323Sed#define DEBUG_TYPE "reg2mem" 20193323Sed#include "llvm/Transforms/Scalar.h" 21193323Sed#include "llvm/Transforms/Utils/Local.h" 22193323Sed#include "llvm/Pass.h" 23193323Sed#include "llvm/Function.h" 24193323Sed#include "llvm/Module.h" 25193323Sed#include "llvm/BasicBlock.h" 26193323Sed#include "llvm/Instructions.h" 27193323Sed#include "llvm/ADT/Statistic.h" 28193323Sed#include "llvm/Support/Compiler.h" 29193323Sed#include "llvm/Support/CFG.h" 30193323Sed#include <list> 31193323Sedusing namespace llvm; 32193323Sed 33193323SedSTATISTIC(NumRegsDemoted, "Number of registers demoted"); 34193323SedSTATISTIC(NumPhisDemoted, "Number of phi-nodes demoted"); 35193323Sed 36193323Sednamespace { 37193323Sed struct VISIBILITY_HIDDEN RegToMem : public FunctionPass { 38193323Sed static char ID; // Pass identification, replacement for typeid 39193323Sed RegToMem() : FunctionPass(&ID) {} 40193323Sed 41193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 42193323Sed AU.addRequiredID(BreakCriticalEdgesID); 43193323Sed AU.addPreservedID(BreakCriticalEdgesID); 44193323Sed } 45193323Sed 46193323Sed bool valueEscapes(Instruction* i) { 47193323Sed BasicBlock* bb = i->getParent(); 48193323Sed for (Value::use_iterator ii = i->use_begin(), ie = i->use_end(); 49193323Sed ii != ie; ++ii) 50193323Sed if (cast<Instruction>(*ii)->getParent() != bb || 51193323Sed isa<PHINode>(*ii)) 52193323Sed return true; 53193323Sed return false; 54193323Sed } 55193323Sed 56193323Sed virtual bool runOnFunction(Function &F) { 57193323Sed if (!F.isDeclaration()) { 58193323Sed // Insert all new allocas into entry block. 59193323Sed BasicBlock* BBEntry = &F.getEntryBlock(); 60193323Sed assert(pred_begin(BBEntry) == pred_end(BBEntry) && 61193323Sed "Entry block to function must not have predecessors!"); 62193323Sed 63193323Sed // Find first non-alloca instruction and create insertion point. This is 64193323Sed // safe if block is well-formed: it always have terminator, otherwise 65193323Sed // we'll get and assertion. 66193323Sed BasicBlock::iterator I = BBEntry->begin(); 67193323Sed while (isa<AllocaInst>(I)) ++I; 68193323Sed 69193323Sed CastInst *AllocaInsertionPoint = 70193323Sed CastInst::Create(Instruction::BitCast, 71193323Sed Constant::getNullValue(Type::Int32Ty), Type::Int32Ty, 72193323Sed "reg2mem alloca point", I); 73193323Sed 74193323Sed // Find the escaped instructions. But don't create stack slots for 75193323Sed // allocas in entry block. 76193323Sed std::list<Instruction*> worklist; 77193323Sed for (Function::iterator ibb = F.begin(), ibe = F.end(); 78193323Sed ibb != ibe; ++ibb) 79193323Sed for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 80193323Sed iib != iie; ++iib) { 81193323Sed if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) && 82193323Sed valueEscapes(iib)) { 83193323Sed worklist.push_front(&*iib); 84193323Sed } 85193323Sed } 86193323Sed 87193323Sed // Demote escaped instructions 88193323Sed NumRegsDemoted += worklist.size(); 89193323Sed for (std::list<Instruction*>::iterator ilb = worklist.begin(), 90193323Sed ile = worklist.end(); ilb != ile; ++ilb) 91193323Sed DemoteRegToStack(**ilb, false, AllocaInsertionPoint); 92193323Sed 93193323Sed worklist.clear(); 94193323Sed 95193323Sed // Find all phi's 96193323Sed for (Function::iterator ibb = F.begin(), ibe = F.end(); 97193323Sed ibb != ibe; ++ibb) 98193323Sed for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 99193323Sed iib != iie; ++iib) 100193323Sed if (isa<PHINode>(iib)) 101193323Sed worklist.push_front(&*iib); 102193323Sed 103193323Sed // Demote phi nodes 104193323Sed NumPhisDemoted += worklist.size(); 105193323Sed for (std::list<Instruction*>::iterator ilb = worklist.begin(), 106193323Sed ile = worklist.end(); ilb != ile; ++ilb) 107193323Sed DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint); 108193323Sed 109193323Sed return true; 110193323Sed } 111193323Sed return false; 112193323Sed } 113193323Sed }; 114193323Sed} 115193323Sed 116193323Sedchar RegToMem::ID = 0; 117193323Sedstatic RegisterPass<RegToMem> 118193323SedX("reg2mem", "Demote all values to stack slots"); 119193323Sed 120193323Sed// createDemoteRegisterToMemory - Provide an entry point to create this pass. 121193323Sed// 122193323Sedconst PassInfo *const llvm::DemoteRegisterToMemoryID = &X; 123193323SedFunctionPass *llvm::createDemoteRegisterToMemoryPass() { 124193323Sed return new RegToMem(); 125193323Sed} 126