LLVM API Documentation
00001 //===- Reg2Mem.cpp - Convert registers to allocas -------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file demotes all registers to memory references. It is intented to be 00011 // the inverse of PromoteMemoryToRegister. By converting to loads, the only 00012 // values live accross basic blocks are allocas and loads before phi nodes. 00013 // It is intended that this should make CFG hacking much easier. 00014 // To make later hacking easier, the entry block is split into two, such that 00015 // all introduced allocas and nothing else are in the entry block. 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #define DEBUG_TYPE "reg2mem" 00020 #include "llvm/Transforms/Scalar.h" 00021 #include "llvm/Transforms/Utils/Local.h" 00022 #include "llvm/Pass.h" 00023 #include "llvm/Function.h" 00024 #include "llvm/LLVMContext.h" 00025 #include "llvm/Module.h" 00026 #include "llvm/BasicBlock.h" 00027 #include "llvm/Instructions.h" 00028 #include "llvm/ADT/Statistic.h" 00029 #include "llvm/Support/Compiler.h" 00030 #include "llvm/Support/CFG.h" 00031 #include <list> 00032 using namespace llvm; 00033 00034 STATISTIC(NumRegsDemoted, "Number of registers demoted"); 00035 STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted"); 00036 00037 namespace { 00038 struct VISIBILITY_HIDDEN RegToMem : public FunctionPass { 00039 static char ID; // Pass identification, replacement for typeid 00040 RegToMem() : FunctionPass(&ID) {} 00041 00042 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00043 AU.addRequiredID(BreakCriticalEdgesID); 00044 AU.addPreservedID(BreakCriticalEdgesID); 00045 } 00046 00047 bool valueEscapes(Instruction* i) { 00048 BasicBlock* bb = i->getParent(); 00049 for (Value::use_iterator ii = i->use_begin(), ie = i->use_end(); 00050 ii != ie; ++ii) 00051 if (cast<Instruction>(*ii)->getParent() != bb || 00052 isa<PHINode>(*ii)) 00053 return true; 00054 return false; 00055 } 00056 00057 virtual bool runOnFunction(Function &F) { 00058 if (!F.isDeclaration()) { 00059 // Insert all new allocas into entry block. 00060 BasicBlock* BBEntry = &F.getEntryBlock(); 00061 assert(pred_begin(BBEntry) == pred_end(BBEntry) && 00062 "Entry block to function must not have predecessors!"); 00063 00064 // Find first non-alloca instruction and create insertion point. This is 00065 // safe if block is well-formed: it always have terminator, otherwise 00066 // we'll get and assertion. 00067 BasicBlock::iterator I = BBEntry->begin(); 00068 while (isa<AllocaInst>(I)) ++I; 00069 00070 CastInst *AllocaInsertionPoint = 00071 CastInst::Create(Instruction::BitCast, 00072 Constant::getNullValue(Type::getInt32Ty(F.getContext())), 00073 Type::getInt32Ty(F.getContext()), 00074 "reg2mem alloca point", I); 00075 00076 // Find the escaped instructions. But don't create stack slots for 00077 // allocas in entry block. 00078 std::list<Instruction*> worklist; 00079 for (Function::iterator ibb = F.begin(), ibe = F.end(); 00080 ibb != ibe; ++ibb) 00081 for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 00082 iib != iie; ++iib) { 00083 if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) && 00084 valueEscapes(iib)) { 00085 worklist.push_front(&*iib); 00086 } 00087 } 00088 00089 // Demote escaped instructions 00090 NumRegsDemoted += worklist.size(); 00091 for (std::list<Instruction*>::iterator ilb = worklist.begin(), 00092 ile = worklist.end(); ilb != ile; ++ilb) 00093 DemoteRegToStack(**ilb, false, AllocaInsertionPoint); 00094 00095 worklist.clear(); 00096 00097 // Find all phi's 00098 for (Function::iterator ibb = F.begin(), ibe = F.end(); 00099 ibb != ibe; ++ibb) 00100 for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 00101 iib != iie; ++iib) 00102 if (isa<PHINode>(iib)) 00103 worklist.push_front(&*iib); 00104 00105 // Demote phi nodes 00106 NumPhisDemoted += worklist.size(); 00107 for (std::list<Instruction*>::iterator ilb = worklist.begin(), 00108 ile = worklist.end(); ilb != ile; ++ilb) 00109 DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint); 00110 00111 return true; 00112 } 00113 return false; 00114 } 00115 }; 00116 } 00117 00118 char RegToMem::ID = 0; 00119 static RegisterPass<RegToMem> 00120 X("reg2mem", "Demote all values to stack slots"); 00121 00122 // createDemoteRegisterToMemory - Provide an entry point to create this pass. 00123 // 00124 const PassInfo *const llvm::DemoteRegisterToMemoryID = &X; 00125 FunctionPass *llvm::createDemoteRegisterToMemoryPass() { 00126 return new RegToMem(); 00127 }