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(); 76280031Sdim assert(pred_empty(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 85296417Sdim CastInst *AllocaInsertionPoint = new BitCastInst( 86296417Sdim Constant::getNullValue(Type::getInt32Ty(F.getContext())), 87296417Sdim Type::getInt32Ty(F.getContext()), "reg2mem alloca point", &*I); 88239462Sdim 89198090Srdivacky // Find the escaped instructions. But don't create stack slots for 90198090Srdivacky // allocas in entry block. 91198090Srdivacky std::list<Instruction*> WorkList; 92198090Srdivacky for (Function::iterator ibb = F.begin(), ibe = F.end(); 93198090Srdivacky ibb != ibe; ++ibb) 94198090Srdivacky for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 95198090Srdivacky iib != iie; ++iib) { 96198090Srdivacky if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) && 97296417Sdim valueEscapes(&*iib)) { 98198090Srdivacky WorkList.push_front(&*iib); 99198090Srdivacky } 100198090Srdivacky } 101239462Sdim 102198090Srdivacky // Demote escaped instructions 103198090Srdivacky NumRegsDemoted += WorkList.size(); 104239462Sdim for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 105198090Srdivacky ile = WorkList.end(); ilb != ile; ++ilb) 106198090Srdivacky DemoteRegToStack(**ilb, false, AllocaInsertionPoint); 107239462Sdim 108198090Srdivacky WorkList.clear(); 109239462Sdim 110198090Srdivacky // Find all phi's 111198090Srdivacky for (Function::iterator ibb = F.begin(), ibe = F.end(); 112198090Srdivacky ibb != ibe; ++ibb) 113198090Srdivacky for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 114198090Srdivacky iib != iie; ++iib) 115198090Srdivacky if (isa<PHINode>(iib)) 116198090Srdivacky WorkList.push_front(&*iib); 117239462Sdim 118198090Srdivacky // Demote phi nodes 119198090Srdivacky NumPhisDemoted += WorkList.size(); 120239462Sdim for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 121198090Srdivacky ile = WorkList.end(); ilb != ile; ++ilb) 122198090Srdivacky DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint); 123239462Sdim 124198090Srdivacky return true; 125198090Srdivacky} 126198090Srdivacky 127198090Srdivacky 128193323Sed// createDemoteRegisterToMemory - Provide an entry point to create this pass. 129212904Sdimchar &llvm::DemoteRegisterToMemoryID = RegToMem::ID; 130193323SedFunctionPass *llvm::createDemoteRegisterToMemoryPass() { 131193323Sed return new RegToMem(); 132193323Sed} 133