Reg2Mem.cpp revision 276479
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// 10239462Sdim// This file demotes all registers to memory references. It is intended to be 11193323Sed// the inverse of PromoteMemoryToRegister. By converting to loads, the only 12221345Sdim// values live across 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#include "llvm/Transforms/Scalar.h" 20249423Sdim#include "llvm/ADT/Statistic.h" 21249423Sdim#include "llvm/IR/BasicBlock.h" 22276479Sdim#include "llvm/IR/CFG.h" 23249423Sdim#include "llvm/IR/Function.h" 24249423Sdim#include "llvm/IR/Instructions.h" 25249423Sdim#include "llvm/IR/LLVMContext.h" 26249423Sdim#include "llvm/IR/Module.h" 27193323Sed#include "llvm/Pass.h" 28249423Sdim#include "llvm/Transforms/Utils/Local.h" 29193323Sed#include <list> 30193323Sedusing namespace llvm; 31193323Sed 32276479Sdim#define DEBUG_TYPE "reg2mem" 33276479Sdim 34193323SedSTATISTIC(NumRegsDemoted, "Number of registers demoted"); 35193323SedSTATISTIC(NumPhisDemoted, "Number of phi-nodes demoted"); 36193323Sed 37193323Sednamespace { 38198090Srdivacky struct RegToMem : public FunctionPass { 39193323Sed static char ID; // Pass identification, replacement for typeid 40218893Sdim RegToMem() : FunctionPass(ID) { 41218893Sdim initializeRegToMemPass(*PassRegistry::getPassRegistry()); 42218893Sdim } 43193323Sed 44276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 45193323Sed AU.addRequiredID(BreakCriticalEdgesID); 46193323Sed AU.addPreservedID(BreakCriticalEdgesID); 47193323Sed } 48193323Sed 49276479Sdim bool valueEscapes(const Instruction *Inst) const { 50276479Sdim const BasicBlock *BB = Inst->getParent(); 51276479Sdim for (const User *U : Inst->users()) { 52276479Sdim const Instruction *UI = cast<Instruction>(U); 53276479Sdim if (UI->getParent() != BB || isa<PHINode>(UI)) 54193323Sed return true; 55207618Srdivacky } 56193323Sed return false; 57193323Sed } 58193323Sed 59276479Sdim bool runOnFunction(Function &F) override; 60193323Sed }; 61193323Sed} 62239462Sdim 63193323Sedchar RegToMem::ID = 0; 64218893SdimINITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots", 65218893Sdim false, false) 66218893SdimINITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) 67218893SdimINITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots", 68218893Sdim false, false) 69193323Sed 70198090Srdivackybool RegToMem::runOnFunction(Function &F) { 71239462Sdim if (F.isDeclaration()) 72198090Srdivacky return false; 73239462Sdim 74198090Srdivacky // Insert all new allocas into entry block. 75198090Srdivacky BasicBlock *BBEntry = &F.getEntryBlock(); 76198090Srdivacky assert(pred_begin(BBEntry) == pred_end(BBEntry) && 77198090Srdivacky "Entry block to function must not have predecessors!"); 78239462Sdim 79198090Srdivacky // Find first non-alloca instruction and create insertion point. This is 80198090Srdivacky // safe if block is well-formed: it always have terminator, otherwise 81198090Srdivacky // we'll get and assertion. 82198090Srdivacky BasicBlock::iterator I = BBEntry->begin(); 83198090Srdivacky while (isa<AllocaInst>(I)) ++I; 84239462Sdim 85198090Srdivacky CastInst *AllocaInsertionPoint = 86198090Srdivacky new BitCastInst(Constant::getNullValue(Type::getInt32Ty(F.getContext())), 87198090Srdivacky Type::getInt32Ty(F.getContext()), 88198090Srdivacky "reg2mem alloca point", I); 89239462Sdim 90198090Srdivacky // Find the escaped instructions. But don't create stack slots for 91198090Srdivacky // allocas in entry block. 92198090Srdivacky std::list<Instruction*> WorkList; 93198090Srdivacky for (Function::iterator ibb = F.begin(), ibe = F.end(); 94198090Srdivacky ibb != ibe; ++ibb) 95198090Srdivacky for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 96198090Srdivacky iib != iie; ++iib) { 97198090Srdivacky if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) && 98198090Srdivacky valueEscapes(iib)) { 99198090Srdivacky WorkList.push_front(&*iib); 100198090Srdivacky } 101198090Srdivacky } 102239462Sdim 103198090Srdivacky // Demote escaped instructions 104198090Srdivacky NumRegsDemoted += WorkList.size(); 105239462Sdim for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 106198090Srdivacky ile = WorkList.end(); ilb != ile; ++ilb) 107198090Srdivacky DemoteRegToStack(**ilb, false, AllocaInsertionPoint); 108239462Sdim 109198090Srdivacky WorkList.clear(); 110239462Sdim 111198090Srdivacky // Find all phi's 112198090Srdivacky for (Function::iterator ibb = F.begin(), ibe = F.end(); 113198090Srdivacky ibb != ibe; ++ibb) 114198090Srdivacky for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 115198090Srdivacky iib != iie; ++iib) 116198090Srdivacky if (isa<PHINode>(iib)) 117198090Srdivacky WorkList.push_front(&*iib); 118239462Sdim 119198090Srdivacky // Demote phi nodes 120198090Srdivacky NumPhisDemoted += WorkList.size(); 121239462Sdim for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 122198090Srdivacky ile = WorkList.end(); ilb != ile; ++ilb) 123198090Srdivacky DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint); 124239462Sdim 125198090Srdivacky return true; 126198090Srdivacky} 127198090Srdivacky 128198090Srdivacky 129193323Sed// createDemoteRegisterToMemory - Provide an entry point to create this pass. 130212904Sdimchar &llvm::DemoteRegisterToMemoryID = RegToMem::ID; 131193323SedFunctionPass *llvm::createDemoteRegisterToMemoryPass() { 132193323Sed return new RegToMem(); 133193323Sed} 134