119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===- Reg2Mem.cpp - Convert registers to allocas -------------------------===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file demotes all registers to memory references. It is intented to be 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// the inverse of PromoteMemoryToRegister. By converting to loads, the only 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// values live across basic blocks are allocas and loads before phi nodes. 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// It is intended that this should make CFG hacking much easier. 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// To make later hacking easier, the entry block is split into two, such that 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// all introduced allocas and nothing else are in the entry block. 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define DEBUG_TYPE "reg2mem" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Transforms/Scalar.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Transforms/Utils/Local.h" 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Pass.h" 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Function.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/LLVMContext.h" 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Module.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/BasicBlock.h" 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Instructions.h" 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/Statistic.h" 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/CFG.h" 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <list> 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanusing namespace llvm; 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumRegsDemoted, "Number of registers demoted"); 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumPhisDemoted, "Number of phi-nodes demoted"); 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct RegToMem : public FunctionPass { 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static char ID; // Pass identification, replacement for typeid 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegToMem() : FunctionPass(ID) { 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeRegToMemPass(*PassRegistry::getPassRegistry()); 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequiredID(BreakCriticalEdgesID); 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreservedID(BreakCriticalEdgesID); 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool valueEscapes(const Instruction *Inst) const { 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const BasicBlock *BB = Inst->getParent(); 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Value::const_use_iterator UI = Inst->use_begin(),E = Inst->use_end(); 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UI != E; ++UI) { 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const Instruction *I = cast<Instruction>(*UI); 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->getParent() != BB || isa<PHINode>(I)) 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool runOnFunction(Function &F); 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar RegToMem::ID = 0; 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots", 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman false, false) 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots", 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman false, false) 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegToMem::runOnFunction(Function &F) { 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (F.isDeclaration()) 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert all new allocas into entry block. 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BBEntry = &F.getEntryBlock(); 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(pred_begin(BBEntry) == pred_end(BBEntry) && 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Entry block to function must not have predecessors!"); 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Find first non-alloca instruction and create insertion point. This is 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // safe if block is well-formed: it always have terminator, otherwise 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // we'll get and assertion. 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock::iterator I = BBEntry->begin(); 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (isa<AllocaInst>(I)) ++I; 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CastInst *AllocaInsertionPoint = 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new BitCastInst(Constant::getNullValue(Type::getInt32Ty(F.getContext())), 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type::getInt32Ty(F.getContext()), 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "reg2mem alloca point", I); 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Find the escaped instructions. But don't create stack slots for 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // allocas in entry block. 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::list<Instruction*> WorkList; 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator ibb = F.begin(), ibe = F.end(); 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ibb != ibe; ++ibb) 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iib != iie; ++iib) { 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) && 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman valueEscapes(iib)) { 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman WorkList.push_front(&*iib); 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Demote escaped instructions 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumRegsDemoted += WorkList.size(); 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ile = WorkList.end(); ilb != ile; ++ilb) 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DemoteRegToStack(**ilb, false, AllocaInsertionPoint); 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman WorkList.clear(); 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Find all phi's 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator ibb = F.begin(), ibe = F.end(); 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ibb != ibe; ++ibb) 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iib != iie; ++iib) 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isa<PHINode>(iib)) 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman WorkList.push_front(&*iib); 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Demote phi nodes 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumPhisDemoted += WorkList.size(); 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ile = WorkList.end(); ilb != ile; ++ilb) 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint); 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// createDemoteRegisterToMemory - Provide an entry point to create this pass. 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar &llvm::DemoteRegisterToMemoryID = RegToMem::ID; 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanFunctionPass *llvm::createDemoteRegisterToMemoryPass() { 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return new RegToMem(); 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 135