PromoteMemoryToRegister.cpp revision 63cdcaa3d6c33cc1923797259bb8e5d9d9a899b1
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" 26d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner#include "llvm/ADT/DenseMap.h" 27c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner#include "llvm/ADT/SmallPtrSet.h" 2840b6555561f083930a40c5c9e8b1023c81910402Chris Lattner#include "llvm/ADT/SmallVector.h" 2962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/ADT/StringExtras.h" 30393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner#include "llvm/Support/CFG.h" 31a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 3220aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 33f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 34d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 35dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner// Provide DenseMapKeyInfo for all pointers. 36dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattnernamespace llvm { 37dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattnertemplate<> 38dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattnerstruct DenseMapKeyInfo<std::pair<BasicBlock*, unsigned> > { 39dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner static inline std::pair<BasicBlock*, unsigned> getEmptyKey() { 40dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner return std::make_pair((BasicBlock*)-1, ~0U); 41dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 42dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner static inline std::pair<BasicBlock*, unsigned> getTombstoneKey() { 43dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner return std::make_pair((BasicBlock*)-2, 0U); 44dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 45dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) { 46dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner return DenseMapKeyInfo<void*>::getHashValue(Val.first) + Val.second*2; 47dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 48dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner static bool isPod() { return true; } 49dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner}; 50dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner} 51dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 52d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// isAllocaPromotable - Return true if this alloca is legal for promotion. 53a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner/// This is true if there are only loads and stores to the alloca. 54d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 5541968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patelbool llvm::isAllocaPromotable(const AllocaInst *AI) { 56fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // FIXME: If the memory unit is of pointer or integer type, we can permit 57fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // assignments to subsections of the memory unit. 58fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner 59d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner // Only allow direct loads and stores... 60d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); 61d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner UI != UE; ++UI) // Loop over all of the uses of the alloca 622d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner if (isa<LoadInst>(*UI)) { 632d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner // noop 642d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 652d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner if (SI->getOperand(0) == AI) 662d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner return false; // Don't allow a store OF the AI, only INTO the AI. 672d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } else { 68a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner return false; // Not a load or store. 692d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } 70fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 71d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner return true; 72d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner} 73d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner 74b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardtnamespace { 75a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 76a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel // Data package used by RenamePass() 77a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel class VISIBILITY_HIDDEN RenamePassData { 78a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel public: 7963cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner RenamePassData() {} 80a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel RenamePassData(BasicBlock *B, BasicBlock *P, 81d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel const std::vector<Value *> &V) : BB(B), Pred(P), Values(V) {} 82a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel BasicBlock *BB; 83a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel BasicBlock *Pred; 84a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel std::vector<Value *> Values; 8563cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner 8663cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner void swap(RenamePassData &RHS) { 8763cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner std::swap(BB, RHS.BB); 8863cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner std::swap(Pred, RHS.Pred); 8963cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner Values.swap(RHS.Values); 9063cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner } 91a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel }; 92a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 939525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN PromoteMem2Reg { 9462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Allocas - The alloca instructions being promoted. 9562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 9624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner std::vector<AllocaInst*> Allocas; 9740b6555561f083930a40c5c9e8b1023c81910402Chris Lattner SmallVector<AllocaInst*, 16> &RetryList; 98326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DominatorTree &DT; 99d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner DominanceFrontier &DF; 100a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 10162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AST - An AliasSetTracker object to update. If null, don't update it. 10262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 10362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AliasSetTracker *AST; 10462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 10562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AllocaLookup - Reverse mapping of Allocas. 10662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 1079e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner std::map<AllocaInst*, unsigned> AllocaLookup; 1089e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 10962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// NewPhiNodes - The PhiNodes we're adding. 11062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 111dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes; 112dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 113dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas 114dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner /// it corresponds to. 115dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner DenseMap<PHINode*, unsigned> PhiToAllocaMap; 116dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 11762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 11862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// each alloca that is of pointer type, we keep track of what to copyValue 11962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// to the inserted PHI nodes here. 12062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 12162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner std::vector<Value*> PointerAllocaValues; 12262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 12362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Visited - The set of basic blocks the renamer has already visited. 12462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 125c670f3da72a14d10eeca7ee88abb875b57eaa6a7Chris Lattner SmallPtrSet<BasicBlock*, 16> Visited; 12698a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 12762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// BBNumbers - Contains a stable numbering of basic blocks to avoid 12862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// non-determinstic behavior. 129d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner DenseMap<BasicBlock*, unsigned> BBNumbers; 13063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 131b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner public: 1326cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner PromoteMem2Reg(const std::vector<AllocaInst*> &A, 133326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel SmallVector<AllocaInst*, 16> &Retry, DominatorTree &dt, 13468c01b3cf35bb7ed2d3a3f63053e304e092bcfddDevang Patel DominanceFrontier &df, AliasSetTracker *ast) 135326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel : Allocas(A), RetryList(Retry), DT(dt), DF(df), AST(ast) {} 136b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 137d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner void run(); 138b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 139fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner /// properlyDominates - Return true if I1 properly dominates I2. 1407e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner /// 141fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner bool properlyDominates(Instruction *I1, Instruction *I2) const { 14228e792c2323a878e6a4661f043f10affc804cca2Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I1)) 14328e792c2323a878e6a4661f043f10affc804cca2Chris Lattner I1 = II->getNormalDest()->begin(); 144326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel return DT.properlyDominates(I1->getParent(), I2->getParent()); 145fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner } 146fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner 147326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel /// dominates - Return true if BB1 dominates BB2 using the DominatorTree. 148fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner /// 149fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner bool dominates(BasicBlock *BB1, BasicBlock *BB2) const { 150326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel return DT.dominates(BB1, BB2); 1517e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner } 1527e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner 153b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner private: 15469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 1556a1a28dedde99b2d939c8290d1268cb4938c8183Chris Lattner SmallPtrSet<PHINode*, 16> &DeadPHINodes); 1566cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner bool PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI); 157fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman void PromoteLocallyUsedAllocas(BasicBlock *BB, 158e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner const std::vector<AllocaInst*> &AIs); 15924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 160cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner void RenamePass(BasicBlock *BB, BasicBlock *Pred, 161ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<Value*> &IncVals, 162ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> &Worklist); 16369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version, 1646a1a28dedde99b2d939c8290d1268cb4938c8183Chris Lattner SmallPtrSet<PHINode*, 16> &InsertedPHINodes); 165b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner }; 166a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 167b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} // end of anonymous namespace 168d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner 169d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::run() { 170d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner Function &F = *DF.getRoot()->getParent(); 1710fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner 172e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // LocallyUsedAllocas - Keep track of all of the alloca instructions which are 173e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // only used in a single basic block. These instructions can be efficiently 174e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // promoted by performing a single linear scan over that one block. Since 175e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // individual basic blocks are sometimes large, we group together all allocas 176e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // that are live in a single basic block by the basic block they are live in. 177e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<BasicBlock*, std::vector<AllocaInst*> > LocallyUsedAllocas; 178e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 17962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) PointerAllocaValues.resize(Allocas.size()); 18063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 18169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 18269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaInst *AI = Allocas[AllocaNum]; 1839e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 18441968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patel assert(isAllocaPromotable(AI) && 185d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "Cannot promote non-promotable alloca!"); 18669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner assert(AI->getParent()->getParent() == &F && 187d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "All allocas should be in the same function, which is same as DF!"); 1889157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner 18924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (AI->use_empty()) { 19024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // If there are no uses of the alloca, just delete it now. 19162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(AI); 192634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner AI->eraseFromParent(); 19324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 19424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // Remove the alloca from the Allocas list, since it has been processed 19569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner Allocas[AllocaNum] = Allocas.back(); 19624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner Allocas.pop_back(); 19769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner --AllocaNum; 19824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner continue; 19924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 20024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 20169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Calculate the set of read and write-locations for each alloca. This is 2022d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner // analogous to finding the 'uses' and 'definitions' of each variable. 20392581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner std::vector<BasicBlock*> DefiningBlocks; 20469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner std::vector<BasicBlock*> UsingBlocks; 20524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 20636ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner StoreInst *OnlyStore = 0; 20724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner BasicBlock *OnlyBlock = 0; 20824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner bool OnlyUsedInOneBlock = true; 20924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 21024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // As we scan the uses of the alloca instruction, keep track of stores, and 21124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // decide whether all of the loads and stores to the alloca are within the 21224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // same basic block. 21362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner Value *AllocaPointerVal = 0; 21424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E;++U){ 21524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner Instruction *User = cast<Instruction>(*U); 21624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 21724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // Remember the basic blocks which define new values for the alloca 21892581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner DefiningBlocks.push_back(SI->getParent()); 21962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AllocaPointerVal = SI->getOperand(0); 22036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner OnlyStore = SI; 221fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner } else { 222fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner LoadInst *LI = cast<LoadInst>(User); 22369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Otherwise it must be a load instruction, keep track of variable reads 2242d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner UsingBlocks.push_back(LI->getParent()); 22562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AllocaPointerVal = LI; 22624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 22724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 22824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (OnlyUsedInOneBlock) { 22924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (OnlyBlock == 0) 23024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner OnlyBlock = User->getParent(); 23124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner else if (OnlyBlock != User->getParent()) 23224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner OnlyUsedInOneBlock = false; 23324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 23424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 23524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 23624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // If the alloca is only read and written in one basic block, just perform a 23724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // linear sweep over the block to eliminate it. 23824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (OnlyUsedInOneBlock) { 239e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner LocallyUsedAllocas[OnlyBlock].push_back(AI); 24024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 241e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Remove the alloca from the Allocas list, since it will be processed. 24269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner Allocas[AllocaNum] = Allocas.back(); 24324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner Allocas.pop_back(); 24469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner --AllocaNum; 24524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner continue; 24624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 2479e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 24836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // If there is only a single store to this value, replace any loads of 24936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // it that are directly dominated by the definition with the value stored. 25036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (DefiningBlocks.size() == 1) { 25136ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // Be aware of loads before the store. 25236ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner std::set<BasicBlock*> ProcessedBlocks; 25336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i) 25436ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // If the store dominates the block and if we haven't processed it yet, 25536ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // do so now. 25636ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (dominates(OnlyStore->getParent(), UsingBlocks[i])) 25736ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (ProcessedBlocks.insert(UsingBlocks[i]).second) { 25836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner BasicBlock *UseBlock = UsingBlocks[i]; 25936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 26036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // If the use and store are in the same block, do a quick scan to 26136ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // verify that there are no uses before the store. 26236ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (UseBlock == OnlyStore->getParent()) { 26336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner BasicBlock::iterator I = UseBlock->begin(); 26436ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner for (; &*I != OnlyStore; ++I) { // scan block for store. 26536ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (isa<LoadInst>(I) && I->getOperand(0) == AI) 26636ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner break; 26736ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 26836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (&*I != OnlyStore) break; // Do not handle this case. 26936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 27036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 27136ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // Otherwise, if this is a different block or if all uses happen 27236ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // after the store, do a simple linear scan to replace loads with 27336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // the stored value. 27436ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner for (BasicBlock::iterator I = UseBlock->begin(),E = UseBlock->end(); 27536ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner I != E; ) { 27636ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I++)) { 27736ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (LI->getOperand(0) == AI) { 27836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner LI->replaceAllUsesWith(OnlyStore->getOperand(0)); 27936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (AST && isa<PointerType>(LI->getType())) 28036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner AST->deleteValue(LI); 28136ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner LI->eraseFromParent(); 28236ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 28336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 28436ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 28536ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 28636ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // Finally, remove this block from the UsingBlock set. 28736ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner UsingBlocks[i] = UsingBlocks.back(); 28836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner --i; --e; 28936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 29036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 29136ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // Finally, after the scan, check to see if the store is all that is left. 29236ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner if (UsingBlocks.empty()) { 29336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // The alloca has been processed, move on. 29436ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner Allocas[AllocaNum] = Allocas.back(); 29536ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner Allocas.pop_back(); 29636ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner --AllocaNum; 29736ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner continue; 29836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 29936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 30036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 301fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner 30262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) 30362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner PointerAllocaValues[AllocaNum] = AllocaPointerVal; 30462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 30563168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // If we haven't computed a numbering for the BB's in the function, do so 30663168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // now. 307d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner if (BBNumbers.empty()) { 308d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner unsigned ID = 0; 309d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 310d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner BBNumbers[I] = ID++; 311d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner } 31263168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 3139157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // Compute the locations where PhiNodes need to be inserted. Look at the 3149157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // dominance frontier of EACH basic-block we have a write in. 3159157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner // 3163c881cb4ce4adc1765378360ba6383bdd64287f3Chris Lattner unsigned CurrentVersion = 0; 3176a1a28dedde99b2d939c8290d1268cb4938c8183Chris Lattner SmallPtrSet<PHINode*, 16> InsertedPHINodes; 318a0d1548d0db3bb2893cd04f4d92c066c7d1cdf5fChris Lattner std::vector<std::pair<unsigned, BasicBlock*> > DFBlocks; 31992581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner while (!DefiningBlocks.empty()) { 32092581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner BasicBlock *BB = DefiningBlocks.back(); 32192581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner DefiningBlocks.pop_back(); 32292581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner 3239f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // Look up the DF for this write, add it to PhiNodes 32492581c24a3b9c4ec2c31ae1985eb5980c5f5c86fChris Lattner DominanceFrontier::const_iterator it = DF.find(BB); 325d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner if (it != DF.end()) { 326d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner const DominanceFrontier::DomSetType &S = it->second; 32763168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 32863168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // In theory we don't need the indirection through the DFBlocks vector. 32963168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // In practice, the order of calling QueuePhiNode would depend on the 33063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // (unspecified) ordering of basic blocks in the dominance frontier, 33163168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // which would give PHI nodes non-determinstic subscripts. Fix this by 33263168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // processing blocks in order of the occurance in the function. 33317e6e44298d8da4cd97ba0be66225cdad4670276Reid Spencer for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 33417e6e44298d8da4cd97ba0be66225cdad4670276Reid Spencer PE = S.end(); P != PE; ++P) 335d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner DFBlocks.push_back(std::make_pair(BBNumbers[*P], *P)); 33663168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 33763168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // Sort by which the block ordering in the function. 33863168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner std::sort(DFBlocks.begin(), DFBlocks.end()); 33963168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 34063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) { 341a0d1548d0db3bb2893cd04f4d92c066c7d1cdf5fChris Lattner BasicBlock *BB = DFBlocks[i].second; 34263168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes)) 34363168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner DefiningBlocks.push_back(BB); 34463168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner } 34563168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner DFBlocks.clear(); 346d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner } 3479f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 34869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 34969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Now that we have inserted PHI nodes along the Iterated Dominance Frontier 35069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // of the writes to the variable, scan through the reads of the variable, 35169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // marking PHI nodes which are actually necessary as alive (by removing them 35269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // from the InsertedPHINodes set). This is not perfect: there may PHI 35369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // marked alive because of loads which are dominated by stores, but there 35469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // will be no unmarked PHI nodes which are actually used. 35569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // 35669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i) 35769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner MarkDominatingPHILive(UsingBlocks[i], AllocaNum, InsertedPHINodes); 35869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner UsingBlocks.clear(); 35969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 36069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // If there are any PHI nodes which are now known to be dead, remove them! 3616a1a28dedde99b2d939c8290d1268cb4938c8183Chris Lattner for (SmallPtrSet<PHINode*, 16>::iterator I = InsertedPHINodes.begin(), 36269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner E = InsertedPHINodes.end(); I != E; ++I) { 36369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner PHINode *PN = *I; 364dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner bool Erased=NewPhiNodes.erase(std::make_pair(PN->getParent(), AllocaNum)); 365dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner Erased=Erased; 366dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner assert(Erased && "PHI already removed?"); 367dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 36862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(PN->getType())) 36962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(PN); 370634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner PN->eraseFromParent(); 371dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PhiToAllocaMap.erase(PN); 37269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 37369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 374fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // Keep the reverse mapping of the 'Allocas' array. 37569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 3769f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 377fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 378e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Process all allocas which are only used in a single basic block. 379e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner for (std::map<BasicBlock*, std::vector<AllocaInst*> >::iterator I = 380e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner LocallyUsedAllocas.begin(), E = LocallyUsedAllocas.end(); I != E; ++I){ 3816cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner const std::vector<AllocaInst*> &LocAllocas = I->second; 3826cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner assert(!LocAllocas.empty() && "empty alloca list??"); 383e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 384e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // It's common for there to only be one alloca in the list. Handle it 385e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // efficiently. 3866cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (LocAllocas.size() == 1) { 3876cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // If we can do the quick promotion pass, do so now. 3886cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (PromoteLocallyUsedAlloca(I->first, LocAllocas[0])) 3896cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner RetryList.push_back(LocAllocas[0]); // Failed, retry later. 3906cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } else { 3916cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // Locally promote anything possible. Note that if this is unable to 3926cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // promote a particular alloca, it puts the alloca onto the Allocas vector 3936cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // for global processing. 3946cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner PromoteLocallyUsedAllocas(I->first, LocAllocas); 3956cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 396e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 397e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 39824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (Allocas.empty()) 39924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner return; // All of the allocas must have been trivial! 4009f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 4015b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // Set the incoming values for the basic block to be null values for all of 4025b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // the alloca's. We do this in case there is a load of a value that has not 4035b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // been stored yet. In this case, it will get this null value. 4045b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // 405cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner std::vector<Value *> Values(Allocas.size()); 4065b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 407b20724dff4485de5381b578f840df61c4cb31867Chris Lattner Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 4085b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner 4099f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // Walks all basic blocks in the function performing the SSA rename algorithm 4109f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // and inserting the phi nodes we marked as necessary 4119f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // 412ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner 413ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> RenamePassWorkList; 414d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values)); 415a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel while(!RenamePassWorkList.empty()) { 41663cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner RenamePassData RPD; 41763cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner RPD.swap(RenamePassWorkList.back()); 418d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel RenamePassWorkList.pop_back(); 419a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel // RenamePass may add new worklist entries. 420ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList); 421a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel } 422a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 423afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // The renamer uses the Visited set to avoid infinite loops. Clear it now. 4240fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Visited.clear(); 4259f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 426634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // Remove the allocas themselves from the function. 4270fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 4280fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *A = Allocas[i]; 4299f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 4300fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there are any uses of the alloca instructions left, they must be in 431d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // sections of dead code that were not processed on the dominance frontier. 432d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // Just delete the users now. 433d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // 4340fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (!A->use_empty()) 435b20724dff4485de5381b578f840df61c4cb31867Chris Lattner A->replaceAllUsesWith(UndefValue::get(A->getType())); 43662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(A); 437634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner A->eraseFromParent(); 4389f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 439afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 440634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner 441634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // Loop over all of the PHI nodes and see if there are any that we can get 442634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // rid of because they merge all of the same incoming values. This can 443634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // happen due to undef values coming into the PHI nodes. This process is 444634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // iterative, because eliminating one PHI node can cause others to be removed. 445634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner bool EliminatedAPHI = true; 446634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner while (EliminatedAPHI) { 447634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner EliminatedAPHI = false; 448634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner 449dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 450dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) { 451dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *PN = I->second; 452dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 453dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If this PHI node merges one value and/or undefs, get the value. 454dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (Value *V = PN->hasConstantValue(true)) { 455dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (!isa<Instruction>(V) || 456dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner properlyDominates(cast<Instruction>(V), PN)) { 457dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (AST && isa<PointerType>(PN->getType())) 458dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner AST->deleteValue(PN); 459dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PN->replaceAllUsesWith(V); 460dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PN->eraseFromParent(); 461dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner NewPhiNodes.erase(I++); 462dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner EliminatedAPHI = true; 463dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner continue; 464634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 465634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 466dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++I; 467634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 468634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 469634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner 470afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // At this point, the renamer has added entries to PHI nodes for all reachable 471c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // code. Unfortunately, there may be unreachable blocks which the renamer 472c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // hasn't traversed. If this is the case, the PHI nodes may not 473afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // have incoming values for all predecessors. Loop over all PHI nodes we have 4747e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // created, inserting undef values if they are missing any incoming values. 475afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // 476dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 477afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 478dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // We want to do this once per basic block. As such, only process a block 479dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // when we find the PHI that is the first entry in the block. 480dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *SomePHI = I->second; 481dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock *BB = SomePHI->getParent(); 482dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (&BB->front() != SomePHI) 483dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner continue; 484afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 485dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Count the number of preds for BB. 486dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 4877e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner 488afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // Only do work here if there the PHI nodes are missing incoming values. We 489afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // know that all PHI nodes that were inserted in a block will have the same 490dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // number of incoming values, so we can just check any of them. 491dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (SomePHI->getNumIncomingValues() == Preds.size()) 492dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner continue; 493dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 494dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Ok, now we know that all of the PHI nodes are missing entries for some 495dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // basic blocks. Start by sorting the incoming predecessors for efficient 496dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // access. 497dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner std::sort(Preds.begin(), Preds.end()); 498dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 499dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Now we loop through all BB's which have entries in SomePHI and remove 500dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // them from the Preds list. 501dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 502dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Do a log(n) search of the Preds list for the entry we want. 503dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SmallVector<BasicBlock*, 16>::iterator EntIt = 504dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner std::lower_bound(Preds.begin(), Preds.end(), 505dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->getIncomingBlock(i)); 506dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 507dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner "PHI node has entry for a block which is not a predecessor!"); 508dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 509dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Remove the entry 510dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner Preds.erase(EntIt); 511dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 512afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 513dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // At this point, the blocks left in the preds list must have dummy 514dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // entries inserted into every PHI nodes for the block. Update all the phi 515dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // nodes in this block that we are inserting (there could be phis before 516dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // mem2reg runs). 517dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned NumBadPreds = SomePHI->getNumIncomingValues(); 518dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock::iterator BBI = BB->begin(); 519dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner while ((SomePHI = dyn_cast<PHINode>(BBI++)) && 520dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->getNumIncomingValues() == NumBadPreds) { 521dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner Value *UndefVal = UndefValue::get(SomePHI->getType()); 522dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 523dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->addIncoming(UndefVal, Preds[pred]); 524afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 525afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 526dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 527dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner NewPhiNodes.clear(); 5289f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 52998a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 53069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// MarkDominatingPHILive - Mem2Reg wants to construct "pruned" SSA form, not 53169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// "minimal" SSA form. To do this, it inserts all of the PHI nodes on the IDF 53269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// as usual (inserting the PHI nodes in the DeadPHINodes set), then processes 53369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// each read of the variable. For each block that reads the variable, this 53469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// function is called, which removes used PHI nodes from the DeadPHINodes set. 53569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// After all of the reads have been processed, any PHI nodes left in the 53669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// DeadPHINodes set are removed. 53769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// 53869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattnervoid PromoteMem2Reg::MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 5396a1a28dedde99b2d939c8290d1268cb4938c8183Chris Lattner SmallPtrSet<PHINode*, 16> &DeadPHINodes) { 54069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Scan the immediate dominators of this block looking for a block which has a 54169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // PHI node for Alloca num. If we find it, mark the PHI node as being alive! 542326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DomTreeNode *IDomNode = DT.getNode(BB); 543326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel for (DomTreeNode *IDom = IDomNode; IDom; IDom = IDom->getIDom()) { 544326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel BasicBlock *DomBB = IDom->getBlock(); 545dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator 546dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner I = NewPhiNodes.find(std::make_pair(DomBB, AllocaNum)); 547dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (I != NewPhiNodes.end()) { 54869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Ok, we found an inserted PHI node which dominates this value. 549dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *DominatingPHI = I->second; 55069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 551c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // Find out if we previously thought it was dead. If so, mark it as being 552c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // live by removing it from the DeadPHINodes set. 553c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner if (DeadPHINodes.erase(DominatingPHI)) { 55469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Now that we have marked the PHI node alive, also mark any PHI nodes 55569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // which it might use as being alive as well. 55669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (pred_iterator PI = pred_begin(DomBB), PE = pred_end(DomBB); 55769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner PI != PE; ++PI) 55869091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner MarkDominatingPHILive(*PI, AllocaNum, DeadPHINodes); 55969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 56069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 56169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner } 56269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner} 56369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 564e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// PromoteLocallyUsedAlloca - Many allocas are only used within a single basic 565e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// block. If this is the case, avoid traversing the CFG and inserting a lot of 566e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// potentially useless PHI nodes by just performing a single linear pass over 567e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// the basic block using the Alloca. 568e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// 5696cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// If we cannot promote this alloca (because it is read before it is written), 5706cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// return true. This is necessary in cases where, due to control flow, the 5716cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// alloca is potentially undefined on some control flow paths. e.g. code like 5726cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// this is potentially correct: 5736cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 5746cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// for (...) { if (c) { A = undef; undef = B; } } 5756cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 5766cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// ... so long as A is not used before undef is set. 5776cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 5786cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattnerbool PromoteMem2Reg::PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI) { 57924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner assert(!AI->use_empty() && "There are no uses of the alloca!"); 5807fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner 5817fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner // Handle degenerate cases quickly. 5827fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (AI->hasOneUse()) { 5837fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner Instruction *U = cast<Instruction>(AI->use_back()); 5847fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 5857fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner // Must be a load of uninitialized value. 586b20724dff4485de5381b578f840df61c4cb31867Chris Lattner LI->replaceAllUsesWith(UndefValue::get(AI->getAllocatedType())); 58762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(LI->getType())) 58862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(LI); 5897fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } else { 5907fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner // Otherwise it must be a store which is never read. 5917fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner assert(isa<StoreInst>(U)); 5927fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } 5937fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner BB->getInstList().erase(U); 5947fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } else { 595b20724dff4485de5381b578f840df61c4cb31867Chris Lattner // Uses of the uninitialized memory location shall get undef. 5966cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner Value *CurVal = 0; 597fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 5987fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 5997fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner Instruction *Inst = I++; 6007fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 6017fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (LI->getOperand(0) == AI) { 6026cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (!CurVal) return true; // Could not locally promote! 6036cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 604e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Loads just returns the "current value"... 6057fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner LI->replaceAllUsesWith(CurVal); 60662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(LI->getType())) 60762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(LI); 6087fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner BB->getInstList().erase(LI); 6097fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } 6107fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 6117fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner if (SI->getOperand(1) == AI) { 612e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Store updates the "current value"... 6137fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner CurVal = SI->getOperand(0); 6147fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner BB->getInstList().erase(SI); 6157fecc2e5e28fa223b16280a5e434d7d0e03e9c52Chris Lattner } 61624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 61724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 61824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 61924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 62024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // After traversing the basic block, there should be no more uses of the 62124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // alloca, remove it now. 62224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner assert(AI->use_empty() && "Uses of alloca from more than one BB??"); 62362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(AI); 62424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner AI->getParent()->getInstList().erase(AI); 6256cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner return false; 62624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner} 62798a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 628e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// PromoteLocallyUsedAllocas - This method is just like 629e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// PromoteLocallyUsedAlloca, except that it processes multiple alloca 630e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// instructions in parallel. This is important in cases where we have large 631e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// basic blocks, as we don't want to rescan the entire basic block for each 632e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// alloca which is locally used in it (which might be a lot). 633e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattnervoid PromoteMem2Reg:: 634e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris LattnerPromoteLocallyUsedAllocas(BasicBlock *BB, const std::vector<AllocaInst*> &AIs) { 635e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<AllocaInst*, Value*> CurValues; 636e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner for (unsigned i = 0, e = AIs.size(); i != e; ++i) 637e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner CurValues[AIs[i]] = 0; // Insert with null value 638e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 639e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 640e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner Instruction *Inst = I++; 641e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 642e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Is this a load of an alloca we are tracking? 643e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(LI->getOperand(0))) { 644e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 645e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AIt != CurValues.end()) { 6466cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // If loading an uninitialized value, allow the inter-block case to 6476cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // handle it. Due to control flow, this might actually be ok. 6486cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (AIt->second == 0) { // Use of locally uninitialized value?? 6496cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner RetryList.push_back(AI); // Retry elsewhere. 6506cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner CurValues.erase(AIt); // Stop tracking this here. 6516cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (CurValues.empty()) return; 6526cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } else { 6536cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // Loads just returns the "current value"... 6546cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner LI->replaceAllUsesWith(AIt->second); 6556cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner if (AST && isa<PointerType>(LI->getType())) 6566cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner AST->deleteValue(LI); 6576cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner BB->getInstList().erase(LI); 6586cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 659e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 660e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 661e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 662e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(SI->getOperand(1))) { 663e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 664e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner if (AIt != CurValues.end()) { 665e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner // Store updates the "current value"... 666e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner AIt->second = SI->getOperand(0); 667e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner BB->getInstList().erase(SI); 668e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 669e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 670e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 671e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 672e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner} 673e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 674e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 675e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 6769f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 6779f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// Alloca returns true if there wasn't already a phi-node for that variable 6789f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// 6793c881cb4ce4adc1765378360ba6383bdd64287f3Chris Lattnerbool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 68069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner unsigned &Version, 6816a1a28dedde99b2d939c8290d1268cb4938c8183Chris Lattner SmallPtrSet<PHINode*, 16> &InsertedPHINodes) { 68262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner // Look up the basic-block in question. 683dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *&PN = NewPhiNodes[std::make_pair(BB, AllocaNo)]; 68498a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 6859f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // If the BB already has a phi node added for the i'th alloca then we're done! 686dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (PN) return false; 68798a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 6881d608abbc07bbc7c78c20da6b305ef14c6c30e8eChris Lattner // Create a PhiNode using the dereferenced type... and add the phi-node to the 689393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner // BasicBlock. 690dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PN = new PHINode(Allocas[AllocaNo]->getAllocatedType(), 691dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner Allocas[AllocaNo]->getName() + "." + 692dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner utostr(Version++), BB->begin()); 693dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PhiToAllocaMap[PN] = AllocaNo; 694dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 69562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner InsertedPHINodes.insert(PN); 69662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 69762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(PN->getType())) 69862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->copyValue(PointerAllocaValues[AllocaNo], PN); 69962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 7009f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner return true; 7019f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 70298a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 70369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner 70469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// RenamePass - Recursively traverse the CFG of the function, renaming loads and 70569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// stores to the allocas which we are promoting. IncomingVals indicates what 70669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// value each Alloca contains on exit from the predecessor block Pred. 70769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// 708d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 709ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<Value*> &IncomingVals, 710ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> &Worklist) { 711dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If we are inserting any phi nodes into this BB, they will already be in the 712dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // block. 713dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) { 714dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Pred may have multiple edges to BB. If so, we want to add N incoming 715dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // values to each PHI we are inserting on the first time we see the edge. 716dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Check to see if APN already has incoming values from Pred. This also 717dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // prevents us from modifying PHI nodes that are not currently being 718dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // inserted. 719dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner bool HasPredEntries = false; 720dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0, e = APN->getNumIncomingValues(); i != e; ++i) { 721dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (APN->getIncomingBlock(i) == Pred) { 722dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner HasPredEntries = true; 723dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner break; 724c8789cb40b81d032b79e02023e025d3ca7711365Chris Lattner } 725dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 726dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 727dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If we have PHI nodes to update, compute the number of edges from Pred to 728dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // BB. 729dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (!HasPredEntries) { 730dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner TerminatorInst *PredTerm = Pred->getTerminator(); 731dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned NumEdges = 0; 732dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) { 733dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (PredTerm->getSuccessor(i) == BB) 734dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++NumEdges; 735dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 736dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner assert(NumEdges && "Must be at least one edge from Pred to BB!"); 737dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 738dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Add entries for all the phis. 739dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock::iterator PNI = BB->begin(); 740dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner do { 741dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned AllocaNo = PhiToAllocaMap[APN]; 742dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 743dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Add N incoming values to the PHI node. 744dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0; i != NumEdges; ++i) 745dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner APN->addIncoming(IncomingVals[AllocaNo], Pred); 746dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 747dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // The currently active variable for this block is now the PHI. 748dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner IncomingVals[AllocaNo] = APN; 749dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 750dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Get the next phi node. 751dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++PNI; 752dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner APN = dyn_cast<PHINode>(PNI); 753dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (APN == 0) break; 754dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 755dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Verify it doesn't already have entries for Pred. If it does, it is 756dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // not being inserted by this mem2reg invocation. 757dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner HasPredEntries = false; 758dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0, e = APN->getNumIncomingValues(); i != e; ++i) { 759dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (APN->getIncomingBlock(i) == Pred) { 760dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner HasPredEntries = true; 761dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner break; 762dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 763dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 764dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } while (!HasPredEntries); 765dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 7669157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner } 767dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 768dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Don't revisit blocks. 769dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (!Visited.insert(BB)) return; 77098a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 771521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 7720fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *I = II++; // get the instruction, increment iterator 77398a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 7749f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 775cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner if (AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand())) { 7769e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 7770adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner if (AI != AllocaLookup.end()) { 7780adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner Value *V = IncomingVals[AI->second]; 77998a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 7809f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // walk the use list of this load and replace all uses with r 7819f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner LI->replaceAllUsesWith(V); 78262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST && isa<PointerType>(LI->getType())) 78362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->deleteValue(LI); 7840fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner BB->getInstList().erase(LI); 7859f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 7869f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 7879f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 788cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner // Delete this instruction and mark the name as the current holder of the 7899f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // value 790cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner if (AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand())) { 7919e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 7929f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner if (ai != AllocaLookup.end()) { 7939f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // what value were we writing? 7940adb9f95eaceda29c2de42fbe7a32cbc2f875a0aChris Lattner IncomingVals[ai->second] = SI->getOperand(0); 7950fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner BB->getInstList().erase(SI); 7969f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 7979f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 7989f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 7999f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 800521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner 80169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Recurse to our successors. 802521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner TerminatorInst *TI = BB->getTerminator(); 803d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel for (unsigned i = 0; i != TI->getNumSuccessors(); i++) 804ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner Worklist.push_back(RenamePassData(TI->getSuccessor(i), BB, IncomingVals)); 805d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner} 806b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt 807d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// PromoteMemToReg - Promote the specified list of alloca instructions into 808d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// scalar registers, inserting PHI nodes as appropriate. This function makes 809d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// use of DominanceFrontier information. This function does not modify the CFG 810d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// of the function at all. All allocas must be from the same function. 811d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 81262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// If AST is specified, the specified tracker is updated to reflect changes 81362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// made to the IR. 81462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// 815f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 816326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DominatorTree &DT, DominanceFrontier &DF, 81768c01b3cf35bb7ed2d3a3f63053e304e092bcfddDevang Patel AliasSetTracker *AST) { 8180fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there is nothing to do, bail out... 8190fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (Allocas.empty()) return; 8206cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 82140b6555561f083930a40c5c9e8b1023c81910402Chris Lattner SmallVector<AllocaInst*, 16> RetryList; 822326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel PromoteMem2Reg(Allocas, RetryList, DT, DF, AST).run(); 8236cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 8246cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // PromoteMem2Reg may not have been able to promote all of the allocas in one 8256cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // pass, run it again if needed. 82640b6555561f083930a40c5c9e8b1023c81910402Chris Lattner std::vector<AllocaInst*> NewAllocas; 8276cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner while (!RetryList.empty()) { 8286cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // If we need to retry some allocas, this is due to there being no store 8296cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // before a read in a local block. To counteract this, insert a store of 8306cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner // undef into the alloca right after the alloca itself. 8316cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner for (unsigned i = 0, e = RetryList.size(); i != e; ++i) { 8326cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner BasicBlock::iterator BBI = RetryList[i]; 83300b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen 8346cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner new StoreInst(UndefValue::get(RetryList[i]->getAllocatedType()), 8356cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner RetryList[i], ++BBI); 8366cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 8376cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 83840b6555561f083930a40c5c9e8b1023c81910402Chris Lattner NewAllocas.assign(RetryList.begin(), RetryList.end()); 83940b6555561f083930a40c5c9e8b1023c81910402Chris Lattner RetryList.clear(); 840326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel PromoteMem2Reg(NewAllocas, RetryList, DT, DF, AST).run(); 84140b6555561f083930a40c5c9e8b1023c81910402Chris Lattner NewAllocas.clear(); 8426cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner } 843b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} 844