1183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth//===- Reg2Mem.cpp - Convert registers to allocas -------------------------===// 2183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// 3183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// The LLVM Compiler Infrastructure 4183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// 8183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth//===----------------------------------------------------------------------===// 9183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// 10d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer// This file demotes all registers to memory references. It is intended to be 11183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// the inverse of PromoteMemoryToRegister. By converting to loads, the only 127a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// values live across basic blocks are allocas and loads before phi nodes. 13183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// It is intended that this should make CFG hacking much easier. 14183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// To make later hacking easier, the entry block is split into two, such that 15183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// all introduced allocas and nothing else are in the entry block. 16183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// 17183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth//===----------------------------------------------------------------------===// 18183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth 19183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth#include "llvm/Transforms/Scalar.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 29183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth#include <list> 30183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharthusing namespace llvm; 31183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "reg2mem" 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 34a024e8cedab928403818ac79e899cdae2a356c56Anton KorobeynikovSTATISTIC(NumRegsDemoted, "Number of registers demoted"); 35a024e8cedab928403818ac79e899cdae2a356c56Anton KorobeynikovSTATISTIC(NumPhisDemoted, "Number of phi-nodes demoted"); 360e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner 37183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharthnamespace { 383e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct RegToMem : public FunctionPass { 39ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson RegToMem() : FunctionPass(ID) { 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeRegToMemPass(*PassRegistry::getPassRegistry()); 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 43183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 457045f6c56e60329408e775573b24af0893557b0eAndrew Lenharth AU.addRequiredID(BreakCriticalEdgesID); 46b0826529f87befb8424c437acbd1e61d6f383fc0Andrew Lenharth AU.addPreservedID(BreakCriticalEdgesID); 477045f6c56e60329408e775573b24af0893557b0eAndrew Lenharth } 487045f6c56e60329408e775573b24af0893557b0eAndrew Lenharth 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool valueEscapes(const Instruction *Inst) const { 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BasicBlock *BB = Inst->getParent(); 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (const User *U : Inst->users()) { 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Instruction *UI = cast<Instruction>(U); 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UI->getParent() != BB || isa<PHINode>(UI)) 54183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth return true; 5567894a3d02caa0b4628a942bef923907bbd97c47Gabor Greif } 56183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth return false; 57183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth } 58183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 60183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth }; 61183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth} 62a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 63844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar RegToMem::ID = 0; 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots", 652ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson false, false) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) 672ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots", 68ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson false, false) 6920a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner 7020a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattnerbool RegToMem::runOnFunction(Function &F) { 71a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem if (F.isDeclaration()) 7220a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner return false; 73a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 7420a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // Insert all new allocas into entry block. 7520a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner BasicBlock *BBEntry = &F.getEntryBlock(); 7620a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner assert(pred_begin(BBEntry) == pred_end(BBEntry) && 7720a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner "Entry block to function must not have predecessors!"); 78a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 7920a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // Find first non-alloca instruction and create insertion point. This is 8020a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // safe if block is well-formed: it always have terminator, otherwise 8120a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // we'll get and assertion. 8220a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner BasicBlock::iterator I = BBEntry->begin(); 8320a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner while (isa<AllocaInst>(I)) ++I; 84a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 8520a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner CastInst *AllocaInsertionPoint = 8620a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner new BitCastInst(Constant::getNullValue(Type::getInt32Ty(F.getContext())), 8720a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner Type::getInt32Ty(F.getContext()), 8820a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner "reg2mem alloca point", I); 89a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 9020a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // Find the escaped instructions. But don't create stack slots for 9120a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // allocas in entry block. 9220a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner std::list<Instruction*> WorkList; 9320a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner for (Function::iterator ibb = F.begin(), ibe = F.end(); 9420a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner ibb != ibe; ++ibb) 9520a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 9620a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner iib != iie; ++iib) { 9720a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) && 9820a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner valueEscapes(iib)) { 9920a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner WorkList.push_front(&*iib); 10020a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner } 10120a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner } 102a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 10320a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // Demote escaped instructions 10420a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner NumRegsDemoted += WorkList.size(); 105a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 10620a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner ile = WorkList.end(); ilb != ile; ++ilb) 10720a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner DemoteRegToStack(**ilb, false, AllocaInsertionPoint); 108a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 10920a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner WorkList.clear(); 110a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 11120a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // Find all phi's 11220a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner for (Function::iterator ibb = F.begin(), ibe = F.end(); 11320a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner ibb != ibe; ++ibb) 11420a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end(); 11520a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner iib != iie; ++iib) 11620a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner if (isa<PHINode>(iib)) 11720a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner WorkList.push_front(&*iib); 118a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 11920a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner // Demote phi nodes 12020a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner NumPhisDemoted += WorkList.size(); 121a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem for (std::list<Instruction*>::iterator ilb = WorkList.begin(), 12220a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner ile = WorkList.end(); ilb != ile; ++ilb) 12320a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint); 124a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 12520a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner return true; 12620a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner} 12720a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner 12820a2faa980293534da366a59b5cd9cd00588b1b7Chris Lattner 129183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth// createDemoteRegisterToMemory - Provide an entry point to create this pass. 13090c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::DemoteRegisterToMemoryID = RegToMem::ID; 131183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew LenharthFunctionPass *llvm::createDemoteRegisterToMemoryPass() { 132183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth return new RegToMem(); 133183119cdf6b4c448170bfdd2d30ac32f9ee20e31Andrew Lenharth} 134