Reg2Mem.cpp revision 218893
1169691Skan//===- Reg2Mem.cpp - Convert registers to allocas -------------------------===// 2169691Skan// 3169691Skan// The LLVM Compiler Infrastructure 4169691Skan// 5169691Skan// This file is distributed under the University of Illinois Open Source 6169691Skan// License. See LICENSE.TXT for details. 7169691Skan// 8169691Skan//===----------------------------------------------------------------------===// 9169691Skan// 10169691Skan// This file demotes all registers to memory references. It is intented to be 11169691Skan// the inverse of PromoteMemoryToRegister. By converting to loads, the only 12169691Skan// values live accross basic blocks are allocas and loads before phi nodes. 13169691Skan// It is intended that this should make CFG hacking much easier. 14169691Skan// To make later hacking easier, the entry block is split into two, such that 15169691Skan// all introduced allocas and nothing else are in the entry block. 16169691Skan// 17169691Skan//===----------------------------------------------------------------------===// 18169691Skan 19169691Skan#define DEBUG_TYPE "reg2mem" 20169691Skan#include "llvm/Transforms/Scalar.h" 21169691Skan#include "llvm/Transforms/Utils/Local.h" 22169691Skan#include "llvm/Pass.h" 23169691Skan#include "llvm/Function.h" 24169691Skan#include "llvm/LLVMContext.h" 25169691Skan#include "llvm/Module.h" 26169691Skan#include "llvm/BasicBlock.h" 27169691Skan#include "llvm/Instructions.h" 28169691Skan#include "llvm/ADT/Statistic.h" 29169691Skan#include "llvm/Support/CFG.h" 30169691Skan#include <list> 31169691Skanusing namespace llvm; 32169691Skan 33169691SkanSTATISTIC(NumRegsDemoted, "Number of registers demoted"); 34169691SkanSTATISTIC(NumPhisDemoted, "Number of phi-nodes demoted"); 35169691Skan 36169691Skannamespace { 37169691Skan struct RegToMem : public FunctionPass { 38169691Skan static char ID; // Pass identification, replacement for typeid 39169691Skan RegToMem() : FunctionPass(ID) { 40169691Skan initializeRegToMemPass(*PassRegistry::getPassRegistry()); 41169691Skan } 42169691Skan 43169691Skan virtual void getAnalysisUsage(AnalysisUsage &AU) const { 44169691Skan AU.addRequiredID(BreakCriticalEdgesID); 45169691Skan AU.addPreservedID(BreakCriticalEdgesID); 46169691Skan } 47169691Skan 48169691Skan bool valueEscapes(const Instruction *Inst) const { 49169691Skan const BasicBlock *BB = Inst->getParent(); 50169691Skan for (Value::const_use_iterator UI = Inst->use_begin(),E = Inst->use_end(); 51169691Skan UI != E; ++UI) { 52169691Skan const Instruction *I = cast<Instruction>(*UI); 53169691Skan if (I->getParent() != BB || isa<PHINode>(I)) 54169691Skan return true; 55169691Skan } 56169691Skan return false; 57169691Skan } 58169691Skan 59169691Skan virtual bool runOnFunction(Function &F); 60169691Skan }; 61169691Skan} 62169691Skan 63169691Skanchar RegToMem::ID = 0; 64169691SkanINITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots", 65169691Skan false, false) 66169691SkanINITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) 67169691SkanINITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots", 68169691Skan false, false) 69169691Skan 70169691Skanbool RegToMem::runOnFunction(Function &F) { 71169691Skan if (F.isDeclaration()) 72169691Skan return false; 73169691Skan 74169691Skan // Insert all new allocas into entry block. 75169691Skan BasicBlock *BBEntry = &F.getEntryBlock(); 76169691Skan assert(pred_begin(BBEntry) == pred_end(BBEntry) && 77169691Skan "Entry block to function must not have predecessors!"); 78169691Skan 79169691Skan // Find first non-alloca instruction and create insertion point. This is 80169691Skan // safe if block is well-formed: it always have terminator, otherwise 81169691Skan // we'll get and assertion. 82169691Skan BasicBlock::iterator I = BBEntry->begin(); 83169691Skan while (isa<AllocaInst>(I)) ++I; 84169691Skan 85169691Skan CastInst *AllocaInsertionPoint = 86169691Skan new BitCastInst(Constant::getNullValue(Type::getInt32Ty(F.getContext())), 87169691Skan Type::getInt32Ty(F.getContext()), 88169691Skan "reg2mem alloca point", I); 89169691Skan 90169691Skan // Find the escaped instructions. But don't create stack slots for 91169691Skan // allocas in entry block. 92169691Skan std::list<Instruction*> WorkList; 93169691Skan for (Function::iterator ibb = F.begin(), ibe = F.end(); 94169691Skan ibb != ibe; ++ibb) 95169691Skan for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 96169691Skan iib != iie; ++iib) { 97169691Skan if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) && 98169691Skan valueEscapes(iib)) { 99169691Skan WorkList.push_front(&*iib); 100169691Skan } 101169691Skan } 102169691Skan 103169691Skan // Demote escaped instructions 104169691Skan NumRegsDemoted += WorkList.size(); 105169691Skan for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 106169691Skan ile = WorkList.end(); ilb != ile; ++ilb) 107169691Skan DemoteRegToStack(**ilb, false, AllocaInsertionPoint); 108169691Skan 109169691Skan WorkList.clear(); 110169691Skan 111169691Skan // Find all phi's 112169691Skan for (Function::iterator ibb = F.begin(), ibe = F.end(); 113169691Skan ibb != ibe; ++ibb) 114169691Skan for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 115169691Skan iib != iie; ++iib) 116169691Skan if (isa<PHINode>(iib)) 117169691Skan WorkList.push_front(&*iib); 118169691Skan 119169691Skan // Demote phi nodes 120169691Skan NumPhisDemoted += WorkList.size(); 121169691Skan for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 122169691Skan ile = WorkList.end(); ilb != ile; ++ilb) 123169691Skan DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint); 124169691Skan 125169691Skan return true; 126169691Skan} 127169691Skan 128169691Skan 129169691Skan// createDemoteRegisterToMemory - Provide an entry point to create this pass. 130169691Skan// 131169691Skanchar &llvm::DemoteRegisterToMemoryID = RegToMem::ID; 132169691SkanFunctionPass *llvm::createDemoteRegisterToMemoryPass() { 133169691Skan return new RegToMem(); 134169691Skan} 135169691Skan