PromoteMemoryToRegister.cpp revision 6cfd1ebcd3d4c3b886b6b41b49806142ceb6275a
1afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner// 10afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner// This file promote memory references to be register references. It promotes 11a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner// alloca instructions which only have loads and stores as uses. An alloca is 12a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner// transformed by using dominator frontiers to place PHI nodes, then traversing 13a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner// the function in depth-first order to rewrite loads and stores as appropriate. 14a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner// This is just the standard SSA construction algorithm to construct "pruned" 15a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner// SSA form. 16d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner// 17d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner//===----------------------------------------------------------------------===// 18d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner 19d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 20b20724dff4485de5381b578f840df61c4cb31867Chris Lattner#include "llvm/Constants.h" 2162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/DerivedTypes.h" 2262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/Function.h" 2362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/Instructions.h" 2462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/Analysis/Dominators.h" 2562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/Analysis/AliasSetTracker.h" 2662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/ADT/StringExtras.h" 277e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner#include "llvm/Transforms/Utils/Local.h" 28393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner#include "llvm/Support/CFG.h" 29abc35bcad3011d582bad3717e14c7398c8c51282Chris Lattner#include "llvm/Support/StableBasicBlockNumbering.h" 3020aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 31f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 33d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// isAllocaPromotable - Return true if this alloca is legal for promotion. 34a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner/// This is true if there are only loads and stores to the alloca. 35d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 36f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) { 37fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // FIXME: If the memory unit is of pointer or integer type, we can permit 38fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // assignments to subsections of the memory unit. 39fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner 40d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner // Only allow direct loads and stores... 41d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); 42d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner UI != UE; ++UI) // Loop over all of the uses of the alloca 432d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner if (isa<LoadInst>(*UI)) { 442d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner // noop 452d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 462d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner if (SI->getOperand(0) == AI) 472d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner return false; // Don't allow a store OF the AI, only INTO the AI. 482d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } else { 49a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner return false; // Not a load or store. 502d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } 51fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 52d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner return true; 53d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner} 54d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner 55b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardtnamespace { 56d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner struct PromoteMem2Reg { 5762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Allocas - The alloca instructions being promoted. 5862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 5924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner std::vector<AllocaInst*> Allocas; 606cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner std::vector<AllocaInst*> &RetryList; 6169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner DominatorTree &DT; 62d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner DominanceFrontier &DF; 63fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner const TargetData &TD; 64a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 6562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AST - An AliasSetTracker object to update. If null, don't update it. 6662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 6762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AliasSetTracker *AST; 6862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 6962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AllocaLookup - Reverse mapping of Allocas. 7062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 719e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner std::map<AllocaInst*, unsigned> AllocaLookup; 729e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 7362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// NewPhiNodes - The PhiNodes we're adding. 7462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 750fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes; 760fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner 7762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 7862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// each alloca that is of pointer type, we keep track of what to copyValue 7962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// to the inserted PHI nodes here. 8062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 8162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner std::vector<Value*> PointerAllocaValues; 8262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 8362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Visited - The set of basic blocks the renamer has already visited. 8462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 850fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner std::set<BasicBlock*> Visited; 8698a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 8762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// BBNumbers - Contains a stable numbering of basic blocks to avoid 8862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// non-determinstic behavior. 89abc35bcad3011d582bad3717e14c7398c8c51282Chris Lattner StableBasicBlockNumbering BBNumbers; 9063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 91b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner public: 926cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner PromoteMem2Reg(const std::vector<AllocaInst*> &A, 936cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner std::vector<AllocaInst*> &Retry, DominatorTree &dt, 9462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner DominanceFrontier &df, const TargetData &td, 9562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AliasSetTracker *ast) 966cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner : Allocas(A), RetryList(Retry), DT(dt), DF(df), TD(td), AST(ast) {} 97b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 98d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner void run(); 99b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 10028e792c2323a878e6a4661f043f10affc804cca2Chris Lattner /// dominates - Return true if I1 dominates I2 using the DominatorTree. 1017e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner /// 10228e792c2323a878e6a4661f043f10affc804cca2Chris Lattner bool dominates(Instruction *I1, Instruction *I2) const { 10328e792c2323a878e6a4661f043f10affc804cca2Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I1)) 10428e792c2323a878e6a4661f043f10affc804cca2Chris Lattner I1 = II->getNormalDest()->begin(); 10528e792c2323a878e6a4661f043f10affc804cca2Chris Lattner return DT[I1->getParent()]->dominates(DT[I2->getParent()]); 1067e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner } 1077e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner 108b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner private: 10969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 11069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::set<PHINode*> &DeadPHINodes); 1116cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner bool PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI); 112fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman void PromoteLocallyUsedAllocas(BasicBlock *BB, 113e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner const std::vector<AllocaInst*> &AIs); 11424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 115cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner void RenamePass(BasicBlock *BB, BasicBlock *Pred, 1160fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner std::vector<Value*> &IncVals); 11769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version, 11869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::set<PHINode*> &InsertedPHINodes); 119b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner }; 120b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} // end of anonymous namespace 121d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner 122d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::run() { 123d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner Function &F = *DF.getRoot()->getParent(); 1240fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner 125e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // LocallyUsedAllocas - Keep track of all of the alloca instructions which are 126e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // only used in a single basic block. These instructions can be efficiently 127e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // promoted by performing a single linear scan over that one block. Since 128e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // individual basic blocks are sometimes large, we group together all allocas 129e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // that are live in a single basic block by the basic block they are live in. 130e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<BasicBlock*, std::vector<AllocaInst*> > LocallyUsedAllocas; 131e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 13262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) PointerAllocaValues.resize(Allocas.size()); 13363168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 13469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 13569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaInst *AI = Allocas[AllocaNum]; 1369e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 1379e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner assert(isAllocaPromotable(AI, TD) && 138d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "Cannot promote non-promotable alloca!"); 13969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner assert(AI->getParent()->getParent() == &F && 140d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "All allocas should be in the same function, which is same as DF!"); 1419157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner 14224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (AI->use_empty()) { 14324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // If there are no uses of the alloca, just delete it now. 14462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(AI); 14524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner AI->getParent()->getInstList().erase(AI); 14624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 14724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // Remove the alloca from the Allocas list, since it has been processed 14869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner Allocas[AllocaNum] = Allocas.back(); 14924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner Allocas.pop_back(); 15069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner --AllocaNum; 15124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner continue; 15224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 15324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 15469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Calculate the set of read and write-locations for each alloca. This is 1552d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner // analogous to finding the 'uses' and 'definitions' of each variable. 15692581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner std::vector<BasicBlock*> DefiningBlocks; 15769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::vector<BasicBlock*> UsingBlocks; 15824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 15924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner BasicBlock *OnlyBlock = 0; 16024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner bool OnlyUsedInOneBlock = true; 16124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 16224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // As we scan the uses of the alloca instruction, keep track of stores, and 16324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // decide whether all of the loads and stores to the alloca are within the 16424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // same basic block. 16562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner Value *AllocaPointerVal = 0; 16624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E;++U){ 16724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner Instruction *User = cast<Instruction>(*U); 16824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 16924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // Remember the basic blocks which define new values for the alloca 17092581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner DefiningBlocks.push_back(SI->getParent()); 17162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AllocaPointerVal = SI->getOperand(0); 1722d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 17369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Otherwise it must be a load instruction, keep track of variable reads 1742d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner UsingBlocks.push_back(LI->getParent()); 17562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AllocaPointerVal = LI; 17624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 17724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 17824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (OnlyUsedInOneBlock) { 17924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (OnlyBlock == 0) 18024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner OnlyBlock = User->getParent(); 18124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner else if (OnlyBlock != User->getParent()) 18224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner OnlyUsedInOneBlock = false; 18324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 18424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 18524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 18624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // If the alloca is only read and written in one basic block, just perform a 18724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // linear sweep over the block to eliminate it. 18824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (OnlyUsedInOneBlock) { 189e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner LocallyUsedAllocas[OnlyBlock].push_back(AI); 19024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 191e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Remove the alloca from the Allocas list, since it will be processed. 19269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner Allocas[AllocaNum] = Allocas.back(); 19324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner Allocas.pop_back(); 19469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner --AllocaNum; 19524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner continue; 19624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 1979e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 19862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) 19962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner PointerAllocaValues[AllocaNum] = AllocaPointerVal; 20062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 20163168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // If we haven't computed a numbering for the BB's in the function, do so 20263168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // now. 203abc35bcad3011d582bad3717e14c7398c8c51282Chris Lattner BBNumbers.compute(F); 20463168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 2059157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // Compute the locations where PhiNodes need to be inserted. Look at the 2069157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // dominance frontier of EACH basic-block we have a write in. 2079157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // 2083c881cb4ce4adc1765378360ba6383bdd64287f3Chris Lattner unsigned CurrentVersion = 0; 20969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::set<PHINode*> InsertedPHINodes; 21063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner std::vector<unsigned> DFBlocks; 21192581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner while (!DefiningBlocks.empty()) { 21292581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner BasicBlock *BB = DefiningBlocks.back(); 21392581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner DefiningBlocks.pop_back(); 21492581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner 2159f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // Look up the DF for this write, add it to PhiNodes 21692581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner DominanceFrontier::const_iterator it = DF.find(BB); 217d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner if (it != DF.end()) { 218d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner const DominanceFrontier::DomSetType &S = it->second; 21963168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 22063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // In theory we don't need the indirection through the DFBlocks vector. 22163168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // In practice, the order of calling QueuePhiNode would depend on the 22263168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // (unspecified) ordering of basic blocks in the dominance frontier, 22363168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // which would give PHI nodes non-determinstic subscripts. Fix this by 22463168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // processing blocks in order of the occurance in the function. 22517e6e44298d8da4cd97ba0be66225cdad4670276Reid Spencer for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 22617e6e44298d8da4cd97ba0be66225cdad4670276Reid Spencer PE = S.end(); P != PE; ++P) 227abc35bcad3011d582bad3717e14c7398c8c51282Chris Lattner DFBlocks.push_back(BBNumbers.getNumber(*P)); 22863168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 22963168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // Sort by which the block ordering in the function. 23063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner std::sort(DFBlocks.begin(), DFBlocks.end()); 23163168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 23263168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) { 233abc35bcad3011d582bad3717e14c7398c8c51282Chris Lattner BasicBlock *BB = BBNumbers.getBlock(DFBlocks[i]); 23463168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes)) 23563168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner DefiningBlocks.push_back(BB); 23663168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner } 23763168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner DFBlocks.clear(); 238d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner } 2399f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 24069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 24169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Now that we have inserted PHI nodes along the Iterated Dominance Frontier 24269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // of the writes to the variable, scan through the reads of the variable, 24369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // marking PHI nodes which are actually necessary as alive (by removing them 24469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // from the InsertedPHINodes set). This is not perfect: there may PHI 24569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // marked alive because of loads which are dominated by stores, but there 24669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // will be no unmarked PHI nodes which are actually used. 24769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // 24869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i) 24969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner MarkDominatingPHILive(UsingBlocks[i], AllocaNum, InsertedPHINodes); 25069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner UsingBlocks.clear(); 25169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 25269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // If there are any PHI nodes which are now known to be dead, remove them! 25369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (std::set<PHINode*>::iterator I = InsertedPHINodes.begin(), 25469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner E = InsertedPHINodes.end(); I != E; ++I) { 25569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner PHINode *PN = *I; 25669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::vector<PHINode*> &BBPNs = NewPhiNodes[PN->getParent()]; 25769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner BBPNs[AllocaNum] = 0; 25869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 25969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Check to see if we just removed the last inserted PHI node from this 26069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // basic block. If so, remove the entry for the basic block. 26169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner bool HasOtherPHIs = false; 26269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (unsigned i = 0, e = BBPNs.size(); i != e; ++i) 26369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner if (BBPNs[i]) { 26469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner HasOtherPHIs = true; 26569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner break; 26669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 26769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner if (!HasOtherPHIs) 26869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner NewPhiNodes.erase(PN->getParent()); 26969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 27062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(PN->getType())) 27162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(PN); 272fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman PN->getParent()->getInstList().erase(PN); 27369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 27469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 275fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // Keep the reverse mapping of the 'Allocas' array. 27669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 2779f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 278fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 279e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Process all allocas which are only used in a single basic block. 280e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner for (std::map<BasicBlock*, std::vector<AllocaInst*> >::iterator I = 281e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner LocallyUsedAllocas.begin(), E = LocallyUsedAllocas.end(); I != E; ++I){ 2826cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner const std::vector<AllocaInst*> &LocAllocas = I->second; 2836cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner assert(!LocAllocas.empty() && "empty alloca list??"); 284e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 285e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // It's common for there to only be one alloca in the list. Handle it 286e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // efficiently. 2876cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (LocAllocas.size() == 1) { 2886cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // If we can do the quick promotion pass, do so now. 2896cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (PromoteLocallyUsedAlloca(I->first, LocAllocas[0])) 2906cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner RetryList.push_back(LocAllocas[0]); // Failed, retry later. 2916cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } else { 2926cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // Locally promote anything possible. Note that if this is unable to 2936cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // promote a particular alloca, it puts the alloca onto the Allocas vector 2946cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // for global processing. 2956cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner PromoteLocallyUsedAllocas(I->first, LocAllocas); 2966cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 297e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 298e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 29924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (Allocas.empty()) 30024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner return; // All of the allocas must have been trivial! 3019f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 3025b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // Set the incoming values for the basic block to be null values for all of 3035b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // the alloca's. We do this in case there is a load of a value that has not 3045b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // been stored yet. In this case, it will get this null value. 3055b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // 306cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner std::vector<Value *> Values(Allocas.size()); 3075b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 308b20724dff4485de5381b578f840df61c4cb31867Chris Lattner Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 3095b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner 3109f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // Walks all basic blocks in the function performing the SSA rename algorithm 3119f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // and inserting the phi nodes we marked as necessary 3129f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // 3130fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner RenamePass(F.begin(), 0, Values); 314afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 315afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // The renamer uses the Visited set to avoid infinite loops. Clear it now. 3160fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Visited.clear(); 3179f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 3180fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // Remove the allocas themselves from the function... 3190fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 3200fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *A = Allocas[i]; 3219f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 3220fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there are any uses of the alloca instructions left, they must be in 323d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // sections of dead code that were not processed on the dominance frontier. 324d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // Just delete the users now. 325d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // 3260fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (!A->use_empty()) 327b20724dff4485de5381b578f840df61c4cb31867Chris Lattner A->replaceAllUsesWith(UndefValue::get(A->getType())); 32862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(A); 3290fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner A->getParent()->getInstList().erase(A); 3309f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 331afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 332afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // At this point, the renamer has added entries to PHI nodes for all reachable 333afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // code. Unfortunately, there may be blocks which are not reachable, which 334afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // the renamer hasn't traversed. If this is the case, the PHI nodes may not 335afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // have incoming values for all predecessors. Loop over all PHI nodes we have 3367e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // created, inserting undef values if they are missing any incoming values. 337afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // 338fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I = 339afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 340afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 341afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner std::vector<BasicBlock*> Preds(pred_begin(I->first), pred_end(I->first)); 342afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner std::vector<PHINode*> &PNs = I->second; 343afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner assert(!PNs.empty() && "Empty PHI node list??"); 344afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 3457e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // Loop over all of the PHI nodes and see if there are any that we can get 3467e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // rid of because they merge all of the same incoming values. This can 3477e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // happen due to undef values coming into the PHI nodes. 3487e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner PHINode *SomePHI = 0; 3497e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner for (unsigned i = 0, e = PNs.size(); i != e; ++i) 3507e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner if (PNs[i]) { 3517e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner if (Value *V = hasConstantValue(PNs[i])) { 35228e792c2323a878e6a4661f043f10affc804cca2Chris Lattner if (!isa<Instruction>(V) || dominates(cast<Instruction>(V), PNs[i])) { 3535a85d9c664f0687b4fc89f3b38594b9555a9f193Chris Lattner if (AST && isa<PointerType>(PNs[i]->getType())) 3545a85d9c664f0687b4fc89f3b38594b9555a9f193Chris Lattner AST->deleteValue(PNs[i]); 3557e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner PNs[i]->replaceAllUsesWith(V); 3567e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner PNs[i]->eraseFromParent(); 3577e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner PNs[i] = 0; 3587e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner } 3597e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner } 3607e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner if (PNs[i]) 3617e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner SomePHI = PNs[i]; 3627e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner } 3637e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner 364afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // Only do work here if there the PHI nodes are missing incoming values. We 365afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // know that all PHI nodes that were inserted in a block will have the same 366afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // number of incoming values, so we can just check any PHI node. 3677e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner if (SomePHI && Preds.size() != SomePHI->getNumIncomingValues()) { 368afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // Ok, now we know that all of the PHI nodes are missing entries for some 369afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // basic blocks. Start by sorting the incoming predecessors for efficient 370afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // access. 371afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner std::sort(Preds.begin(), Preds.end()); 372afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 3737e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // Now we loop through all BB's which have entries in SomePHI and remove 374afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // them from the Preds list. 3757e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 37669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Do a log(n) search of the Preds list for the entry we want. 377afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner std::vector<BasicBlock*>::iterator EntIt = 378afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner std::lower_bound(Preds.begin(), Preds.end(), 3797e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner SomePHI->getIncomingBlock(i)); 3807e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 381afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner "PHI node has entry for a block which is not a predecessor!"); 382afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 383afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // Remove the entry 384afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner Preds.erase(EntIt); 385afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 386afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 387afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // At this point, the blocks left in the preds list must have dummy 388afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // entries inserted into every PHI nodes for the block. 3893c4a34e8db5057458d7590b85e9819b7b4c4a7b8Chris Lattner for (unsigned i = 0, e = PNs.size(); i != e; ++i) 3903c4a34e8db5057458d7590b85e9819b7b4c4a7b8Chris Lattner if (PHINode *PN = PNs[i]) { 391b20724dff4485de5381b578f840df61c4cb31867Chris Lattner Value *UndefVal = UndefValue::get(PN->getType()); 3923c4a34e8db5057458d7590b85e9819b7b4c4a7b8Chris Lattner for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 393b20724dff4485de5381b578f840df61c4cb31867Chris Lattner PN->addIncoming(UndefVal, Preds[pred]); 3943c4a34e8db5057458d7590b85e9819b7b4c4a7b8Chris Lattner } 395afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 396afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 3979f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 39898a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 39969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// MarkDominatingPHILive - Mem2Reg wants to construct "pruned" SSA form, not 40069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// "minimal" SSA form. To do this, it inserts all of the PHI nodes on the IDF 40169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// as usual (inserting the PHI nodes in the DeadPHINodes set), then processes 40269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// each read of the variable. For each block that reads the variable, this 40369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// function is called, which removes used PHI nodes from the DeadPHINodes set. 40469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// After all of the reads have been processed, any PHI nodes left in the 40569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// DeadPHINodes set are removed. 40669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// 40769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattnervoid PromoteMem2Reg::MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 40869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::set<PHINode*> &DeadPHINodes) { 40969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Scan the immediate dominators of this block looking for a block which has a 41069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // PHI node for Alloca num. If we find it, mark the PHI node as being alive! 41169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (DominatorTree::Node *N = DT[BB]; N; N = N->getIDom()) { 41269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner BasicBlock *DomBB = N->getBlock(); 41369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::map<BasicBlock*, std::vector<PHINode*> >::iterator 41469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner I = NewPhiNodes.find(DomBB); 41569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner if (I != NewPhiNodes.end() && I->second[AllocaNum]) { 41669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Ok, we found an inserted PHI node which dominates this value. 41769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner PHINode *DominatingPHI = I->second[AllocaNum]; 41869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 41969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Find out if we previously thought it was dead. 42069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::set<PHINode*>::iterator DPNI = DeadPHINodes.find(DominatingPHI); 42169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner if (DPNI != DeadPHINodes.end()) { 42269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Ok, until now, we thought this PHI node was dead. Mark it as being 42369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // alive/needed. 42469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner DeadPHINodes.erase(DPNI); 42569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 42669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Now that we have marked the PHI node alive, also mark any PHI nodes 42769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // which it might use as being alive as well. 42869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (pred_iterator PI = pred_begin(DomBB), PE = pred_end(DomBB); 42969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner PI != PE; ++PI) 43069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner MarkDominatingPHILive(*PI, AllocaNum, DeadPHINodes); 43169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 43269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 43369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 43469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner} 43569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 436e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// PromoteLocallyUsedAlloca - Many allocas are only used within a single basic 437e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// block. If this is the case, avoid traversing the CFG and inserting a lot of 438e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// potentially useless PHI nodes by just performing a single linear pass over 439e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// the basic block using the Alloca. 440e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// 4416cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// If we cannot promote this alloca (because it is read before it is written), 4426cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// return true. This is necessary in cases where, due to control flow, the 4436cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// alloca is potentially undefined on some control flow paths. e.g. code like 4446cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// this is potentially correct: 4456cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 4466cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// for (...) { if (c) { A = undef; undef = B; } } 4476cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 4486cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// ... so long as A is not used before undef is set. 4496cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 4506cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattnerbool PromoteMem2Reg::PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI) { 45124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner assert(!AI->use_empty() && "There are no uses of the alloca!"); 4527fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner 4537fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner // Handle degenerate cases quickly. 4547fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (AI->hasOneUse()) { 4557fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner Instruction *U = cast<Instruction>(AI->use_back()); 4567fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 4577fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner // Must be a load of uninitialized value. 458b20724dff4485de5381b578f840df61c4cb31867Chris Lattner LI->replaceAllUsesWith(UndefValue::get(AI->getAllocatedType())); 45962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(LI->getType())) 46062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(LI); 4617fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } else { 4627fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner // Otherwise it must be a store which is never read. 4637fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner assert(isa<StoreInst>(U)); 4647fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } 4657fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner BB->getInstList().erase(U); 4667fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } else { 467b20724dff4485de5381b578f840df61c4cb31867Chris Lattner // Uses of the uninitialized memory location shall get undef. 4686cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner Value *CurVal = 0; 469fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 4707fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 4717fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner Instruction *Inst = I++; 4727fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 4737fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (LI->getOperand(0) == AI) { 4746cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (!CurVal) return true; // Could not locally promote! 4756cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 476e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Loads just returns the "current value"... 4777fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner LI->replaceAllUsesWith(CurVal); 47862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(LI->getType())) 47962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(LI); 4807fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner BB->getInstList().erase(LI); 4817fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } 4827fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 4837fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (SI->getOperand(1) == AI) { 484e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Store updates the "current value"... 4857fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner CurVal = SI->getOperand(0); 4867fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner BB->getInstList().erase(SI); 4877fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } 48824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 48924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 49024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 49124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 49224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // After traversing the basic block, there should be no more uses of the 49324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // alloca, remove it now. 49424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner assert(AI->use_empty() && "Uses of alloca from more than one BB??"); 49562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(AI); 49624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner AI->getParent()->getInstList().erase(AI); 4976cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner return false; 49824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner} 49998a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 500e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// PromoteLocallyUsedAllocas - This method is just like 501e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// PromoteLocallyUsedAlloca, except that it processes multiple alloca 502e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// instructions in parallel. This is important in cases where we have large 503e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// basic blocks, as we don't want to rescan the entire basic block for each 504e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// alloca which is locally used in it (which might be a lot). 505e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattnervoid PromoteMem2Reg:: 506e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris LattnerPromoteLocallyUsedAllocas(BasicBlock *BB, const std::vector<AllocaInst*> &AIs) { 507e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<AllocaInst*, Value*> CurValues; 508e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner for (unsigned i = 0, e = AIs.size(); i != e; ++i) 509e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner CurValues[AIs[i]] = 0; // Insert with null value 510e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 511e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 512e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner Instruction *Inst = I++; 513e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 514e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Is this a load of an alloca we are tracking? 515e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(LI->getOperand(0))) { 516e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 517e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AIt != CurValues.end()) { 5186cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // If loading an uninitialized value, allow the inter-block case to 5196cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // handle it. Due to control flow, this might actually be ok. 5206cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (AIt->second == 0) { // Use of locally uninitialized value?? 5216cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner RetryList.push_back(AI); // Retry elsewhere. 5226cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner CurValues.erase(AIt); // Stop tracking this here. 5236cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (CurValues.empty()) return; 5246cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } else { 5256cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // Loads just returns the "current value"... 5266cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner LI->replaceAllUsesWith(AIt->second); 5276cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (AST && isa<PointerType>(LI->getType())) 5286cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner AST->deleteValue(LI); 5296cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner BB->getInstList().erase(LI); 5306cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 531e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 532e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 533e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 534e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(SI->getOperand(1))) { 535e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 536e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AIt != CurValues.end()) { 537e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Store updates the "current value"... 538e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner AIt->second = SI->getOperand(0); 539e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner BB->getInstList().erase(SI); 540e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 541e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 542e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 543e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 544e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner} 545e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 546e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 547e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 5489f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 5499f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// Alloca returns true if there wasn't already a phi-node for that variable 5509f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// 5513c881cb4ce4adc1765378360ba6383bdd64287f3Chris Lattnerbool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 55269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner unsigned &Version, 55369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::set<PHINode*> &InsertedPHINodes) { 55462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner // Look up the basic-block in question. 555cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner std::vector<PHINode*> &BBPNs = NewPhiNodes[BB]; 5569f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner if (BBPNs.empty()) BBPNs.resize(Allocas.size()); 55798a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 5589f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // If the BB already has a phi node added for the i'th alloca then we're done! 5590adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner if (BBPNs[AllocaNo]) return false; 56098a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 5611d608abbc07bbc7c78c20da6b305ef14c6c30e8eChris Lattner // Create a PhiNode using the dereferenced type... and add the phi-node to the 562393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner // BasicBlock. 56362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner PHINode *PN = new PHINode(Allocas[AllocaNo]->getAllocatedType(), 56462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner Allocas[AllocaNo]->getName() + "." + 5653c881cb4ce4adc1765378360ba6383bdd64287f3Chris Lattner utostr(Version++), BB->begin()); 56662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner BBPNs[AllocaNo] = PN; 56762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner InsertedPHINodes.insert(PN); 56862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 56962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(PN->getType())) 57062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->copyValue(PointerAllocaValues[AllocaNo], PN); 57162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 5729f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner return true; 5739f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 57498a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 57569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 57669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// RenamePass - Recursively traverse the CFG of the function, renaming loads and 57769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// stores to the allocas which we are promoting. IncomingVals indicates what 57869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// value each Alloca contains on exit from the predecessor block Pred. 57969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// 580d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 5810fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner std::vector<Value*> &IncomingVals) { 582521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner 5839157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // If this BB needs a PHI node, update the PHI node for each variable we need 5849157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // PHI nodes for. 5859157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner std::map<BasicBlock*, std::vector<PHINode *> >::iterator 5869157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner BBPNI = NewPhiNodes.find(BB); 5879157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner if (BBPNI != NewPhiNodes.end()) { 5889157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner std::vector<PHINode *> &BBPNs = BBPNI->second; 5899157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner for (unsigned k = 0; k != BBPNs.size(); ++k) 5909157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner if (PHINode *PN = BBPNs[k]) { 591afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // Add this incoming value to the PHI node. 592afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner PN->addIncoming(IncomingVals[k], Pred); 593afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 594afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // The currently active variable for this block is now the PHI. 5959157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner IncomingVals[k] = PN; 596c8789cb40b81d032b79e02023e025d3ca7711365Chris Lattner } 5979157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner } 59898a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 5999f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // don't revisit nodes 6000adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner if (Visited.count(BB)) return; 601fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 6029f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // mark as visited 6030adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner Visited.insert(BB); 60498a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 605521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 6060fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *I = II++; // get the instruction, increment iterator 60798a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 6089f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 609cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner if (AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand())) { 6109e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 6110adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner if (AI != AllocaLookup.end()) { 6120adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner Value *V = IncomingVals[AI->second]; 61398a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 6149f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // walk the use list of this load and replace all uses with r 6159f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner LI->replaceAllUsesWith(V); 61662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(LI->getType())) 61762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(LI); 6180fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner BB->getInstList().erase(LI); 6199f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 6209f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 6219f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 622cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner // Delete this instruction and mark the name as the current holder of the 6239f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // value 624cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner if (AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand())) { 6259e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 6269f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner if (ai != AllocaLookup.end()) { 6279f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // what value were we writing? 6280adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner IncomingVals[ai->second] = SI->getOperand(0); 6290fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner BB->getInstList().erase(SI); 6309f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 6319f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 6329f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 6339f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 634521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner 63569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Recurse to our successors. 636521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner TerminatorInst *TI = BB->getTerminator(); 637521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner for (unsigned i = 0; i != TI->getNumSuccessors(); i++) { 638521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner std::vector<Value*> OutgoingVals(IncomingVals); 639521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner RenamePass(TI->getSuccessor(i), BB, OutgoingVals); 640521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner } 641d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner} 642b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt 643d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// PromoteMemToReg - Promote the specified list of alloca instructions into 644d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// scalar registers, inserting PHI nodes as appropriate. This function makes 645d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// use of DominanceFrontier information. This function does not modify the CFG 646d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// of the function at all. All allocas must be from the same function. 647d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 64862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// If AST is specified, the specified tracker is updated to reflect changes 64962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// made to the IR. 65062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// 651f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 652f7703df4968084c18c248c1feea9961c19a32e6aChris Lattner DominatorTree &DT, DominanceFrontier &DF, 65362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner const TargetData &TD, AliasSetTracker *AST) { 6540fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there is nothing to do, bail out... 6550fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (Allocas.empty()) return; 6566cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 6576cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner std::vector<AllocaInst*> RetryList; 6586cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner PromoteMem2Reg(Allocas, RetryList, DT, DF, TD, AST).run(); 6596cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 6606cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // PromoteMem2Reg may not have been able to promote all of the allocas in one 6616cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // pass, run it again if needed. 6626cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner while (!RetryList.empty()) { 6636cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // If we need to retry some allocas, this is due to there being no store 6646cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // before a read in a local block. To counteract this, insert a store of 6656cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // undef into the alloca right after the alloca itself. 6666cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner for (unsigned i = 0, e = RetryList.size(); i != e; ++i) { 6676cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner BasicBlock::iterator BBI = RetryList[i]; 6686cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 6696cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner new StoreInst(UndefValue::get(RetryList[i]->getAllocatedType()), 6706cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner RetryList[i], ++BBI); 6716cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 6726cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 6736cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner std::vector<AllocaInst*> NewAllocas; 6746cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner std::swap(NewAllocas, RetryList); 6756cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner PromoteMem2Reg(NewAllocas, RetryList, DT, DF, TD, AST).run(); 6766cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 677b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} 678