PromoteMemoryToRegister.cpp revision 419e8a62997987e0509efe721c1ea81ac29f09f3
1afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner// 10c86b67742a3298c0a5a715b57a64f11107b8a3f2Gordon Henriksen// This file promotes memory references to be register references. It promotes 11a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner// alloca instructions which only have loads and stores as uses. An alloca is 12419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// transformed by using iterated dominator frontiers to place PHI nodes, then 13419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// traversing the function in depth-first order to rewrite loads and stores as 14419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// appropriate. 15419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// 16419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// The algorithm used here is based on: 17419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// 18419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. 19419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of 20419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// Programming Languages 21419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// POPL '95. ACM, New York, NY, 62-73. 22419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// 23419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// It has been modified to not explicitly use the DJ graph data structure and to 24419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich// directly compute pruned SSA using per-variable liveness information. 25d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner// 26d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner//===----------------------------------------------------------------------===// 27d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner 28bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner#define DEBUG_TYPE "mem2reg" 29d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 30b20724dff4485de5381b578f840df61c4cb31867Chris Lattner#include "llvm/Constants.h" 3162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/DerivedTypes.h" 3262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/Function.h" 3362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner#include "llvm/Instructions.h" 34180ffaef18bdd0b1b972657b949c67cf96a20a48Devang Patel#include "llvm/IntrinsicInst.h" 35b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez#include "llvm/Metadata.h" 36cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/Analysis/AliasSetTracker.h" 37b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez#include "llvm/Analysis/DebugInfo.h" 389fc5cdf77c812aaa80419036de27576d45894d0dChris Lattner#include "llvm/Analysis/DominanceFrontier.h" 39cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/Analysis/InstructionSimplify.h" 40d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner#include "llvm/ADT/DenseMap.h" 41c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner#include "llvm/ADT/SmallPtrSet.h" 4240b6555561f083930a40c5c9e8b1023c81910402Chris Lattner#include "llvm/ADT/SmallVector.h" 43bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner#include "llvm/ADT/Statistic.h" 44068a795b33115da0c3bf00140804ef222ec2197bBill Wendling#include "llvm/ADT/STLExtras.h" 45393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner#include "llvm/Support/CFG.h" 4620aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 47419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich#include <queue> 48f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 49d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 50bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris LattnerSTATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block"); 51bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris LattnerSTATISTIC(NumSingleStore, "Number of alloca's promoted with a single store"); 52bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris LattnerSTATISTIC(NumDeadAlloca, "Number of dead alloca's removed"); 53f12f8def399c80aa283783ca406434ee2f80b49fChris LattnerSTATISTIC(NumPHIInsert, "Number of PHI nodes inserted"); 54bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 55dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattnernamespace llvm { 56dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattnertemplate<> 5776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo<std::pair<BasicBlock*, unsigned> > { 5876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typedef std::pair<BasicBlock*, unsigned> EltTy; 5976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static inline EltTy getEmptyKey() { 6076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U); 61dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 6276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static inline EltTy getTombstoneKey() { 6376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U); 64dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 65dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) { 6676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner return DenseMapInfo<void*>::getHashValue(Val.first) + Val.second*2; 6776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner } 6876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static bool isEqual(const EltTy &LHS, const EltTy &RHS) { 6976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner return LHS == RHS; 70dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 71dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner}; 72dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner} 73dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 74d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// isAllocaPromotable - Return true if this alloca is legal for promotion. 75a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner/// This is true if there are only loads and stores to the alloca. 76d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 7741968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patelbool llvm::isAllocaPromotable(const AllocaInst *AI) { 78fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // FIXME: If the memory unit is of pointer or integer type, we can permit 79fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // assignments to subsections of the memory unit. 80fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner 819f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov // Only allow direct and non-volatile loads and stores... 8260ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end(); 835417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif UI != UE; ++UI) { // Loop over all of the uses of the alloca 845417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif const User *U = *UI; 855417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { 869f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov if (LI->isVolatile()) 879f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov return false; 885417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 892d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner if (SI->getOperand(0) == AI) 902d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner return false; // Don't allow a store OF the AI, only INTO the AI. 919f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov if (SI->isVolatile()) 929f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov return false; 932d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } else { 94746867c8b6ded86e450131852d0949644f54927cDaniel Dunbar return false; 952d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } 965417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif } 97fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 98d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner return true; 99d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner} 100d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner 1013511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner/// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the 1023511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner/// alloca 'V', if any. 1033511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattnerstatic DbgDeclareInst *FindAllocaDbgDeclare(Value *V) { 104b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), &V, 1)) 105b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez for (Value::use_iterator UI = DebugNode->use_begin(), 106b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez E = DebugNode->use_end(); UI != E; ++UI) 107b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI)) 108b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez return DDI; 109b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 110b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez return 0; 111b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez} 112b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 113b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardtnamespace { 1145dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner struct AllocaInfo; 115a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 116a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel // Data package used by RenamePass() 1176726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class RenamePassData { 118a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel public: 119483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner typedef std::vector<Value *> ValVector; 120483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner 1210daf77e8034cfb70fbffbfa77d138b78b55af303Chandler Carruth RenamePassData() : BB(NULL), Pred(NULL), Values() {} 122a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel RenamePassData(BasicBlock *B, BasicBlock *P, 123483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner const ValVector &V) : BB(B), Pred(P), Values(V) {} 124a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel BasicBlock *BB; 125a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel BasicBlock *Pred; 126483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner ValVector Values; 12763cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner 12863cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner void swap(RenamePassData &RHS) { 12963cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner std::swap(BB, RHS.BB); 13063cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner std::swap(Pred, RHS.Pred); 13163cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner Values.swap(RHS.Values); 13263cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner } 133a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel }; 13433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 13533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of 13633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// load/store instructions in the block that directly load or store an alloca. 13733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// 13833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// This functionality is important because it avoids scanning large basic 13933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// blocks multiple times when promoting many allocas in the same block. 1406726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class LargeBlockInfo { 14133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// InstNumbers - For each instruction that we track, keep the index of the 14233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// instruction. The index starts out as the number of the instruction from 14333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// the start of the block. 14433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner DenseMap<const Instruction *, unsigned> InstNumbers; 14533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner public: 14633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 14733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// isInterestingInstruction - This code only looks at accesses to allocas. 14833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner static bool isInterestingInstruction(const Instruction *I) { 14933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) || 15033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1))); 15133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 15233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 15333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// getInstructionIndex - Get or calculate the index of the specified 15433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// instruction. 15533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner unsigned getInstructionIndex(const Instruction *I) { 15633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner assert(isInterestingInstruction(I) && 15733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner "Not a load/store to/from an alloca?"); 15833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 15933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // If we already have this instruction number, return it. 16033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I); 16133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (It != InstNumbers.end()) return It->second; 16233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 16333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Scan the whole block to get the instruction. This accumulates 16433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // information for every interesting instruction in the block, in order to 16533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // avoid gratuitus rescans. 16633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner const BasicBlock *BB = I->getParent(); 16733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner unsigned InstNo = 0; 16833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner for (BasicBlock::const_iterator BBI = BB->begin(), E = BB->end(); 16933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner BBI != E; ++BBI) 17033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (isInterestingInstruction(BBI)) 17133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner InstNumbers[BBI] = InstNo++; 17233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner It = InstNumbers.find(I); 17333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 17433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner assert(It != InstNumbers.end() && "Didn't insert instruction?"); 17533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner return It->second; 17633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 17733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 17833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner void deleteValue(const Instruction *I) { 17933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner InstNumbers.erase(I); 18033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 18133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 18233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner void clear() { 18333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner InstNumbers.clear(); 18433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 18533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner }; 186a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 1876726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct PromoteMem2Reg { 18862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Allocas - The alloca instructions being promoted. 18962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 19024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner std::vector<AllocaInst*> Allocas; 191326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DominatorTree &DT; 192b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez DIFactory *DIF; 193a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 19462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AST - An AliasSetTracker object to update. If null, don't update it. 19562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 19662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AliasSetTracker *AST; 1970a205a459884ec745df1c529396dd921f029dafdOwen Anderson 19862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AllocaLookup - Reverse mapping of Allocas. 19962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 2009e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner std::map<AllocaInst*, unsigned> AllocaLookup; 2019e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 20262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// NewPhiNodes - The PhiNodes we're adding. 20362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 204dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes; 205dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 206dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas 207dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner /// it corresponds to. 208dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner DenseMap<PHINode*, unsigned> PhiToAllocaMap; 209dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 21062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 21162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// each alloca that is of pointer type, we keep track of what to copyValue 21262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// to the inserted PHI nodes here. 21362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 21462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner std::vector<Value*> PointerAllocaValues; 21562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 216b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez /// AllocaDbgDeclares - For each alloca, we keep track of the dbg.declare 217b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez /// intrinsic that describes it, if any, so that we can convert it to a 218b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez /// dbg.value intrinsic if the alloca gets promoted. 219d044612489c567b9ba35dc0f6fa0d3b12d78bc59Victor Hernandez SmallVector<DbgDeclareInst*, 8> AllocaDbgDeclares; 220b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 22162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Visited - The set of basic blocks the renamer has already visited. 22262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 223c670f3da72a14d10eeca7ee88abb875b57eaa6a7Chris Lattner SmallPtrSet<BasicBlock*, 16> Visited; 22498a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 22562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// BBNumbers - Contains a stable numbering of basic blocks to avoid 22662e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// non-determinstic behavior. 227d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner DenseMap<BasicBlock*, unsigned> BBNumbers; 22863168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 229419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich /// DomLevels - Maps DomTreeNodes to their level in the dominator tree. 230419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DenseMap<DomTreeNode*, unsigned> DomLevels; 231419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 232e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner /// BBNumPreds - Lazily compute the number of predecessors a block has. 233e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner DenseMap<const BasicBlock*, unsigned> BBNumPreds; 234b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner public: 2350fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt, 236419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich AliasSetTracker *ast) 237419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich : Allocas(A), DT(dt), DIF(0), AST(ast) {} 238d044612489c567b9ba35dc0f6fa0d3b12d78bc59Victor Hernandez ~PromoteMem2Reg() { 2395b718e3e4d0512c5099a079b1ad59de1cde21babChris Lattner delete DIF; 240d044612489c567b9ba35dc0f6fa0d3b12d78bc59Victor Hernandez } 241b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 242d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner void run(); 243b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 244326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel /// dominates - Return true if BB1 dominates BB2 using the DominatorTree. 245fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner /// 246fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner bool dominates(BasicBlock *BB1, BasicBlock *BB2) const { 247326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel return DT.dominates(BB1, BB2); 2487e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner } 2497e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner 250b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner private: 251bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner void RemoveFromAllocasList(unsigned &AllocaIdx) { 252bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Allocas[AllocaIdx] = Allocas.back(); 253bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Allocas.pop_back(); 254bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner --AllocaIdx; 255bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 256e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner 257e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner unsigned getNumPreds(const BasicBlock *BB) { 258e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner unsigned &NP = BBNumPreds[BB]; 259e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner if (NP == 0) 260e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner NP = std::distance(pred_begin(BB), pred_end(BB))+1; 261e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner return NP-1; 262e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner } 263e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner 2640ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 2650ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner AllocaInfo &Info); 266f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 267f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 268f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> &LiveInBlocks); 269bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 27033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, 27133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI); 2720fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 27333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI); 2743511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, StoreInst *SI); 275aee6a656e84956a2e3c9d7436f68a4a3cfa64feeVictor Hernandez 276aee6a656e84956a2e3c9d7436f68a4a3cfa64feeVictor Hernandez 277cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner void RenamePass(BasicBlock *BB, BasicBlock *Pred, 278483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner RenamePassData::ValVector &IncVals, 279ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> &Worklist); 280b05099bf42d54838f0648569d4ae1a98dfa7da7bDuncan Sands bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version); 281b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner }; 282bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 283bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner struct AllocaInfo { 284bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner std::vector<BasicBlock*> DefiningBlocks; 285bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner std::vector<BasicBlock*> UsingBlocks; 286bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 287bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner StoreInst *OnlyStore; 288bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner BasicBlock *OnlyBlock; 289bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner bool OnlyUsedInOneBlock; 290bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 291bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Value *AllocaPointerVal; 292b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez DbgDeclareInst *DbgDeclare; 293bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 294bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner void clear() { 295bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner DefiningBlocks.clear(); 296bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner UsingBlocks.clear(); 297bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyStore = 0; 298bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyBlock = 0; 299bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyUsedInOneBlock = true; 300bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaPointerVal = 0; 301b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez DbgDeclare = 0; 302bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 303bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 304bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our 305bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner /// ivars. 306bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner void AnalyzeAlloca(AllocaInst *AI) { 307bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner clear(); 308180ffaef18bdd0b1b972657b949c67cf96a20a48Devang Patel 309bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // As we scan the uses of the alloca instruction, keep track of stores, 310bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // and decide whether all of the loads and stores to the alloca are within 311bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // the same basic block. 3122b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 3132b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner UI != E;) { 3142b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner Instruction *User = cast<Instruction>(*UI++); 315e31dc355b264b0956789d47534c779b943c85216Victor Hernandez 3162b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 317bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // Remember the basic blocks which define new values for the alloca 318bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner DefiningBlocks.push_back(SI->getParent()); 319bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaPointerVal = SI->getOperand(0); 320bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyStore = SI; 321bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } else { 322bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner LoadInst *LI = cast<LoadInst>(User); 323e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner // Otherwise it must be a load instruction, keep track of variable 324e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner // reads. 325bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner UsingBlocks.push_back(LI->getParent()); 326bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaPointerVal = LI; 327bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 328bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 329bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (OnlyUsedInOneBlock) { 330bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (OnlyBlock == 0) 331bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyBlock = User->getParent(); 332bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner else if (OnlyBlock != User->getParent()) 333bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyUsedInOneBlock = false; 334bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 335bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 336b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 3373511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner DbgDeclare = FindAllocaDbgDeclare(AI); 338bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 339bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner }; 340419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 341419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich typedef std::pair<DomTreeNode*, unsigned> DomTreeNodePair; 342419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 343419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich struct DomTreeNodeCompare { 344419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich bool operator()(const DomTreeNodePair &LHS, const DomTreeNodePair &RHS) { 345419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich return LHS.second < RHS.second; 346419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 347419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich }; 348b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} // end of anonymous namespace 349d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner 3505dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 351d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::run() { 352419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Function &F = *DT.getRoot()->getParent(); 3530fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner 35462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) PointerAllocaValues.resize(Allocas.size()); 355b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez AllocaDbgDeclares.resize(Allocas.size()); 35663168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 357bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaInfo Info; 35833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo LBI; 359bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 36069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 36169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaInst *AI = Allocas[AllocaNum]; 3629e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 36341968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patel assert(isAllocaPromotable(AI) && 364d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "Cannot promote non-promotable alloca!"); 36569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner assert(AI->getParent()->getParent() == &F && 366d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "All allocas should be in the same function, which is same as DF!"); 3679157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner 36824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (AI->use_empty()) { 36924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // If there are no uses of the alloca, just delete it now. 37062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(AI); 371634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner AI->eraseFromParent(); 37224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 37324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // Remove the alloca from the Allocas list, since it has been processed 374bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner RemoveFromAllocasList(AllocaNum); 375bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner ++NumDeadAlloca; 37624011be956e80e43d111d29cd53ca40e242e53dfChris Lattner continue; 37724011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 378bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 37969091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Calculate the set of read and write-locations for each alloca. This is 3802d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner // analogous to finding the 'uses' and 'definitions' of each variable. 381bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Info.AnalyzeAlloca(AI); 38224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 38336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // If there is only a single store to this value, replace any loads of 38436ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // it that are directly dominated by the definition with the value stored. 385bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (Info.DefiningBlocks.size() == 1) { 38633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner RewriteSingleStoreAlloca(AI, Info, LBI); 38736ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 38836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // Finally, after the scan, check to see if the store is all that is left. 389bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (Info.UsingBlocks.empty()) { 3901897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez // Record debuginfo for the store and remove the declaration's debuginfo. 3911897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez if (DbgDeclareInst *DDI = Info.DbgDeclare) { 3923511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore); 3931897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez DDI->eraseFromParent(); 3941897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez } 3954f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner // Remove the (now dead) store and alloca. 3964f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner Info.OnlyStore->eraseFromParent(); 39733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.deleteValue(Info.OnlyStore); 39833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 3994f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner if (AST) AST->deleteValue(AI); 4004f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner AI->eraseFromParent(); 40133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.deleteValue(AI); 4024f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner 40336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // The alloca has been processed, move on. 404bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner RemoveFromAllocasList(AllocaNum); 4054f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner 4064f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner ++NumSingleStore; 40736ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner continue; 40836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 40936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 41036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 411fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner // If the alloca is only read and written in one basic block, just perform a 412fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner // linear sweep over the block to eliminate it. 413fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner if (Info.OnlyUsedInOneBlock) { 4140fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner PromoteSingleBlockAlloca(AI, Info, LBI); 415fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner 4160fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Finally, after the scan, check to see if the stores are all that is 4170fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // left. 4180fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (Info.UsingBlocks.empty()) { 4190fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4200fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Remove the (now dead) stores and alloca. 4210fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner while (!AI->use_empty()) { 4220fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoreInst *SI = cast<StoreInst>(AI->use_back()); 423b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez // Record debuginfo for the store before removing it. 4243511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner if (DbgDeclareInst *DDI = Info.DbgDeclare) 4253511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner ConvertDebugDeclareToDebugValue(DDI, SI); 4260fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner SI->eraseFromParent(); 4270fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(SI); 4280fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 4290fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4300fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (AST) AST->deleteValue(AI); 4310fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner AI->eraseFromParent(); 4320fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(AI); 4330fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4340fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // The alloca has been processed, move on. 4350fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner RemoveFromAllocasList(AllocaNum); 4360fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4371897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez // The alloca's debuginfo can be removed as well. 4381897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez if (DbgDeclareInst *DDI = Info.DbgDeclare) 4391897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez DDI->eraseFromParent(); 4401897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez 4410fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner ++NumLocalPromoted; 4420fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner continue; 4430fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 444fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner } 445419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 446419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // If we haven't computed dominator tree levels, do so now. 447419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (DomLevels.empty()) { 448419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich SmallVector<DomTreeNode*, 32> Worklist; 449419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 450419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Root = DT.getRootNode(); 451419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomLevels[Root] = 0; 452419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(Root); 453419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 454419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich while (!Worklist.empty()) { 455419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Node = Worklist.pop_back_val(); 456419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned ChildLevel = DomLevels[Node] + 1; 457419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); 458419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich CI != CE; ++CI) { 459419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomLevels[*CI] = ChildLevel; 460419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(*CI); 461419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 462419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 463419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 464419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 46563168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // If we haven't computed a numbering for the BB's in the function, do so 46663168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // now. 467d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner if (BBNumbers.empty()) { 468d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner unsigned ID = 0; 469d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 470d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner BBNumbers[I] = ID++; 471d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner } 47263168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 4730ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // If we have an AST to keep updated, remember some pointer value that is 4740ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // stored into the alloca. 4750ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner if (AST) 4760ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal; 477b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 478b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez // Remember the dbg.declare intrinsic describing this alloca, if any. 479b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez if (Info.DbgDeclare) AllocaDbgDeclares[AllocaNum] = Info.DbgDeclare; 4800ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner 4810ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // Keep the reverse mapping of the 'Allocas' array for the rename pass. 48269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 4830ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner 4840ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // At this point, we're committed to promoting the alloca using IDF's, and 48533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // the standard SSA construction algorithm. Determine which blocks need PHI 4860ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // nodes and see if we can optimize out some work by avoiding insertion of 4870ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // dead phi nodes. 4880ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner DetermineInsertionPoint(AI, AllocaNum, Info); 4899f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 490fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 49124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (Allocas.empty()) 49224011be956e80e43d111d29cd53ca40e242e53dfChris Lattner return; // All of the allocas must have been trivial! 4939f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 49433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.clear(); 49533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 49633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 4975b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // Set the incoming values for the basic block to be null values for all of 4985b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // the alloca's. We do this in case there is a load of a value that has not 4995b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // been stored yet. In this case, it will get this null value. 5005b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // 501483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner RenamePassData::ValVector Values(Allocas.size()); 5025b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 5039e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 5045b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner 5059f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // Walks all basic blocks in the function performing the SSA rename algorithm 5069f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // and inserting the phi nodes we marked as necessary 5079f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // 508ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> RenamePassWorkList; 509d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values)); 510321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman do { 51163cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner RenamePassData RPD; 51263cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner RPD.swap(RenamePassWorkList.back()); 513d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel RenamePassWorkList.pop_back(); 514a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel // RenamePass may add new worklist entries. 515ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList); 516321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman } while (!RenamePassWorkList.empty()); 517a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 518afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // The renamer uses the Visited set to avoid infinite loops. Clear it now. 5190fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Visited.clear(); 5209f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 521634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // Remove the allocas themselves from the function. 5220fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 5230fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *A = Allocas[i]; 5249f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 5250fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there are any uses of the alloca instructions left, they must be in 526d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // sections of dead code that were not processed on the dominance frontier. 527d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // Just delete the users now. 528d4bd3eba5d42356823730fe34418a563a2a2ffd9Chris Lattner // 5290fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (!A->use_empty()) 5309e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson A->replaceAllUsesWith(UndefValue::get(A->getType())); 53162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(A); 532634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner A->eraseFromParent(); 5339f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 534afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 5351897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez // Remove alloca's dbg.declare instrinsics from the function. 5361897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez for (unsigned i = 0, e = AllocaDbgDeclares.size(); i != e; ++i) 5371897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez if (DbgDeclareInst *DDI = AllocaDbgDeclares[i]) 5381897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez DDI->eraseFromParent(); 5391897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez 540634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // Loop over all of the PHI nodes and see if there are any that we can get 541634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // rid of because they merge all of the same incoming values. This can 542634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // happen due to undef values coming into the PHI nodes. This process is 543634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // iterative, because eliminating one PHI node can cause others to be removed. 544634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner bool EliminatedAPHI = true; 545634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner while (EliminatedAPHI) { 546634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner EliminatedAPHI = false; 547634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner 548dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 549dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) { 550dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *PN = I->second; 551cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands 552dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If this PHI node merges one value and/or undefs, get the value. 553cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands if (Value *V = SimplifyInstruction(PN, 0, &DT)) { 5541df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && PN->getType()->isPointerTy()) 555bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman AST->deleteValue(PN); 556bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman PN->replaceAllUsesWith(V); 557bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman PN->eraseFromParent(); 558bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman NewPhiNodes.erase(I++); 559bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman EliminatedAPHI = true; 560bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman continue; 561634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 562dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++I; 563634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 564634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 565634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner 566afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // At this point, the renamer has added entries to PHI nodes for all reachable 567c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // code. Unfortunately, there may be unreachable blocks which the renamer 568c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // hasn't traversed. If this is the case, the PHI nodes may not 569afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // have incoming values for all predecessors. Loop over all PHI nodes we have 5707e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // created, inserting undef values if they are missing any incoming values. 571afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // 572dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 573afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 574dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // We want to do this once per basic block. As such, only process a block 575dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // when we find the PHI that is the first entry in the block. 576dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *SomePHI = I->second; 577dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock *BB = SomePHI->getParent(); 578dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (&BB->front() != SomePHI) 579dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner continue; 580afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 581afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // Only do work here if there the PHI nodes are missing incoming values. We 582afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // know that all PHI nodes that were inserted in a block will have the same 583dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // number of incoming values, so we can just check any of them. 584127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner if (SomePHI->getNumIncomingValues() == getNumPreds(BB)) 585dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner continue; 586127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner 587127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner // Get the preds for BB. 588127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 589dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 590dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Ok, now we know that all of the PHI nodes are missing entries for some 591dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // basic blocks. Start by sorting the incoming predecessors for efficient 592dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // access. 593dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner std::sort(Preds.begin(), Preds.end()); 594dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 595dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Now we loop through all BB's which have entries in SomePHI and remove 596dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // them from the Preds list. 597dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 598dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Do a log(n) search of the Preds list for the entry we want. 599dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SmallVector<BasicBlock*, 16>::iterator EntIt = 600dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner std::lower_bound(Preds.begin(), Preds.end(), 601dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->getIncomingBlock(i)); 602dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 603dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner "PHI node has entry for a block which is not a predecessor!"); 604dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 605dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Remove the entry 606dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner Preds.erase(EntIt); 607dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 608afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 609dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // At this point, the blocks left in the preds list must have dummy 610dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // entries inserted into every PHI nodes for the block. Update all the phi 611dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // nodes in this block that we are inserting (there could be phis before 612dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // mem2reg runs). 613dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned NumBadPreds = SomePHI->getNumIncomingValues(); 614dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock::iterator BBI = BB->begin(); 615dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner while ((SomePHI = dyn_cast<PHINode>(BBI++)) && 616dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->getNumIncomingValues() == NumBadPreds) { 6179e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *UndefVal = UndefValue::get(SomePHI->getType()); 618dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 619dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->addIncoming(UndefVal, Preds[pred]); 620afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 621afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 622dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 623dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner NewPhiNodes.clear(); 6249f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 62598a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 6265dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 627f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// ComputeLiveInBlocks - Determine which blocks the value is live in. These 628f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// are blocks which lead to uses. Knowing this allows us to avoid inserting 629f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// PHI nodes into blocks which don't lead to uses (thus, the inserted phi nodes 630f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// would be dead). 631f12f8def399c80aa283783ca406434ee2f80b49fChris Lattnervoid PromoteMem2Reg:: 632f12f8def399c80aa283783ca406434ee2f80b49fChris LattnerComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 633f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 634f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> &LiveInBlocks) { 635f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 636f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // To determine liveness, we must iterate through the predecessors of blocks 637f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // where the def is live. Blocks are added to the worklist if we need to 638f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // check their predecessors. Start with all the using blocks. 639403a8cdda5e76ea689693de16474650b4b0df818Dan Gohman SmallVector<BasicBlock*, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(), 640403a8cdda5e76ea689693de16474650b4b0df818Dan Gohman Info.UsingBlocks.end()); 641f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 642f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // If any of the using blocks is also a definition block, check to see if the 643f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // definition occurs before or after the use. If it happens before the use, 644f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // the value isn't really live-in. 645f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) { 646f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner BasicBlock *BB = LiveInBlockWorklist[i]; 647f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (!DefBlocks.count(BB)) continue; 648f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 649f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Okay, this is a block that both uses and defines the value. If the first 650f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // reference to the alloca is a def (store), then we know it isn't live-in. 651f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner for (BasicBlock::iterator I = BB->begin(); ; ++I) { 652f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 653f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (SI->getOperand(1) != AI) continue; 654f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 655f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // We found a store to the alloca before a load. The alloca is not 656f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // actually live-in here. 657f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner LiveInBlockWorklist[i] = LiveInBlockWorklist.back(); 658f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner LiveInBlockWorklist.pop_back(); 659f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner --i, --e; 660f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner break; 6612b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner } 6622b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner 6632b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 664f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (LI->getOperand(0) != AI) continue; 665f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 666f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Okay, we found a load before a store to the alloca. It is actually 667f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // live into this block. 668f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner break; 669f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 670f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 671f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 672f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 673f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Now that we have a set of blocks where the phi is live-in, recursively add 674f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // their predecessors until we find the full region the value is live. 675f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner while (!LiveInBlockWorklist.empty()) { 676e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); 677f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 678f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // The block really is live in here, insert it into the set. If already in 679f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // the set, then it has already been processed. 680f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (!LiveInBlocks.insert(BB)) 681f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner continue; 682f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 683f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Since the value is live into BB, it is either defined in a predecessor or 684f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // live into it to. Add the preds to the worklist unless they are a 685f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // defining block. 686f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 687f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner BasicBlock *P = *PI; 688f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 689f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // The value is not live into a predecessor if it defines the value. 690f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (DefBlocks.count(P)) 691f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner continue; 692f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 693f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Otherwise it is, add to the worklist. 694f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner LiveInBlockWorklist.push_back(P); 695f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 696f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 697f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner} 698f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 6990ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// DetermineInsertionPoint - At this point, we're committed to promoting the 7000ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// alloca using IDF's, and the standard SSA construction algorithm. Determine 7010ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// which blocks need phi nodes and see if we can optimize out some work by 7020ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// avoiding insertion of dead phi nodes. 7030ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattnervoid PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 7040ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner AllocaInfo &Info) { 705f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Unique the set of defining blocks for efficient lookup. 706f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> DefBlocks; 707f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); 708f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 709f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Determine which blocks the value is live in. These are blocks which lead 710f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // to uses. 711f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> LiveInBlocks; 712f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); 713f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 714419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // Use a priority queue keyed on dominator tree level so that inserted nodes 715419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // are handled from the bottom of the dominator tree upwards. 716419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, 717419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNodeCompare> IDFPriorityQueue; 718419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich IDFPriorityQueue PQ; 719419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 720419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (SmallPtrSet<BasicBlock*, 32>::const_iterator I = DefBlocks.begin(), 721419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich E = DefBlocks.end(); I != E; ++I) { 722419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (DomTreeNode *Node = DT.getNode(*I)) 723419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PQ.push(std::make_pair(Node, DomLevels[Node])); 724419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 725419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 7260ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner std::vector<std::pair<unsigned, BasicBlock*> > DFBlocks; 727419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich SmallPtrSet<DomTreeNode*, 32> Visited; 728419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich SmallVector<DomTreeNode*, 32> Worklist; 729419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich while (!PQ.empty()) { 730419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNodePair RootPair = PQ.top(); 731419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PQ.pop(); 732419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Root = RootPair.first; 733419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned RootLevel = RootPair.second; 734419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 735419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // Walk all dominator tree children of Root, inspecting their CFG edges with 736419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // targets elsewhere on the dominator tree. Only targets whose level is at 737419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // most Root's level are added to the iterated dominance frontier of the 738419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // definition set. 739419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 740419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.clear(); 741419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(Root); 742419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 743419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich while (!Worklist.empty()) { 744419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Node = Worklist.pop_back_val(); 745419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich BasicBlock *BB = Node->getBlock(); 746419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 747419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 748419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich ++SI) { 749419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *SuccNode = DT.getNode(*SI); 750419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 751419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // Quickly skip all CFG edges that are also dominator tree edges instead 752419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // of catching them below. 753419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (SuccNode->getIDom() == Node) 754419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 755419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 756419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned SuccLevel = DomLevels[SuccNode]; 757419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (SuccLevel > RootLevel) 758419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 759419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 760419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!Visited.insert(SuccNode)) 761419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 762419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 763419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich BasicBlock *SuccBB = SuccNode->getBlock(); 764419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!LiveInBlocks.count(SuccBB)) 765419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 766419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 767419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB)); 768419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!DefBlocks.count(SuccBB)) 769419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PQ.push(std::make_pair(SuccNode, SuccLevel)); 770419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 771419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 772419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE; 773419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich ++CI) { 774419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!Visited.count(*CI)) 775419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(*CI); 776419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 777f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 7780ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner } 779419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 780419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (DFBlocks.size() > 1) 781419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich std::sort(DFBlocks.begin(), DFBlocks.end()); 782419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 783419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned CurrentVersion = 0; 784419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) 785419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion); 7860ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner} 7870ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner 7885dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner/// RewriteSingleStoreAlloca - If there is only a single store to this value, 7895dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner/// replace any loads of it that are directly dominated by the definition with 7905dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner/// the value stored. 7915dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattnervoid PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI, 79233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner AllocaInfo &Info, 79333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI) { 794b776a335b1a3260c27555db31f7ea0bee605de04Chris Lattner StoreInst *OnlyStore = Info.OnlyStore; 795d0458e5d4f29ce1e9ba1def22d06b362ae2c1999Chris Lattner bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0)); 79633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner BasicBlock *StoreBB = OnlyStore->getParent(); 79733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner int StoreIndex = -1; 79833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 79933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Clear out UsingBlocks. We will reconstruct it here if needed. 80033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Info.UsingBlocks.clear(); 801b776a335b1a3260c27555db31f7ea0bee605de04Chris Lattner 80233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) { 80333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Instruction *UserInst = cast<Instruction>(*UI++); 80433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (!isa<LoadInst>(UserInst)) { 80533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner assert(UserInst == OnlyStore && "Should only have load/stores"); 8065dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner continue; 807d0458e5d4f29ce1e9ba1def22d06b362ae2c1999Chris Lattner } 80833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LoadInst *LI = cast<LoadInst>(UserInst); 8095dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 81033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Okay, if we have a load from the alloca, we want to replace it with the 81133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // only value stored to the alloca. We can do this if the value is 81233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // dominated by the store. If not, we use the rest of the mem2reg machinery 81333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // to insert the phi nodes as needed. 81433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (!StoringGlobalVal) { // Non-instructions are always dominated. 81533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (LI->getParent() == StoreBB) { 81633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // If we have a use that is in the same block as the store, compare the 81733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // indices of the two instructions to see which one came first. If the 81833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // load came before the store, we can't handle it. 81933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (StoreIndex == -1) 82033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner StoreIndex = LBI.getInstructionIndex(OnlyStore); 82133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 82233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) { 82333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Can't handle this load, bail out. 82433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Info.UsingBlocks.push_back(StoreBB); 82533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner continue; 8265dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 82733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 82833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } else if (LI->getParent() != StoreBB && 82933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner !dominates(StoreBB, LI->getParent())) { 83033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // If the load and store are in different blocks, use BB dominance to 83133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // check their relationships. If the store doesn't dom the use, bail 83233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // out. 83333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Info.UsingBlocks.push_back(LI->getParent()); 83433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner continue; 8355dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 8365dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 8375dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 83833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Otherwise, we *can* safely rewrite this load. 839794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner Value *ReplVal = OnlyStore->getOperand(0); 840794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner // If the replacement value is the load, this must occur in unreachable 841794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner // code. 842794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner if (ReplVal == LI) 843794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner ReplVal = UndefValue::get(LI->getType()); 844794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner LI->replaceAllUsesWith(ReplVal); 8451df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 84633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner AST->deleteValue(LI); 84733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LI->eraseFromParent(); 84833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.deleteValue(LI); 8495dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 8505dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner} 8515dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 8527db949df789383acce98ef072f08794fdd5bd04eDan Gohmannamespace { 8535dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 8540fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner/// StoreIndexSearchPredicate - This is a helper predicate used to search by the 8550fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner/// first element of a pair. 8560fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattnerstruct StoreIndexSearchPredicate { 8570fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner bool operator()(const std::pair<unsigned, StoreInst*> &LHS, 8580fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner const std::pair<unsigned, StoreInst*> &RHS) { 8590fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner return LHS.first < RHS.first; 8600fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 8610fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner}; 8620fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 8637db949df789383acce98ef072f08794fdd5bd04eDan Gohman} 8647db949df789383acce98ef072f08794fdd5bd04eDan Gohman 8650fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner/// PromoteSingleBlockAlloca - Many allocas are only used within a single basic 866e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// block. If this is the case, avoid traversing the CFG and inserting a lot of 867e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// potentially useless PHI nodes by just performing a single linear pass over 868e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// the basic block using the Alloca. 869e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// 8706cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// If we cannot promote this alloca (because it is read before it is written), 8716cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// return true. This is necessary in cases where, due to control flow, the 8726cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// alloca is potentially undefined on some control flow paths. e.g. code like 8736cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// this is potentially correct: 8746cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 8756cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// for (...) { if (c) { A = undef; undef = B; } } 8766cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 8776cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// ... so long as A is not used before undef is set. 8786cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 8790fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattnervoid PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 88033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI) { 8810fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // The trickiest case to handle is when we have large blocks. Because of this, 8820fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // this code is optimized assuming that large blocks happen. This does not 8830fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // significantly pessimize the small block case. This uses LargeBlockInfo to 8840fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // make it efficient to get the index of various operations in the block. 8850fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 8860fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Clear out UsingBlocks. We will reconstruct it here if needed. 8870fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner Info.UsingBlocks.clear(); 8880fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 8890fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Walk the use-def list of the alloca, getting the locations of all stores. 8900fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner typedef SmallVector<std::pair<unsigned, StoreInst*>, 64> StoresByIndexTy; 8910fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoresByIndexTy StoresByIndex; 8920fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 8930fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 8940fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner UI != E; ++UI) 8950fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 8960fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI)); 8970fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 8980fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // If there are no stores to the alloca, just replace any loads with undef. 8990fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (StoresByIndex.empty()) { 9000fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) 9010fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) { 9029e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson LI->replaceAllUsesWith(UndefValue::get(LI->getType())); 9031df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 9040fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner AST->deleteValue(LI); 9050fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(LI); 9060fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LI->eraseFromParent(); 907e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 9080fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner return; 909e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 9107a5745b38ccdf2794a6f04f01a1c8115ec223ad8Chris Lattner 9110fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Sort the stores by their index, making it efficient to do a lookup with a 9120fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // binary search. 9130fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner std::sort(StoresByIndex.begin(), StoresByIndex.end()); 9140fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9150fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Walk all of the loads from this alloca, replacing them with the nearest 9160fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // store above them, if any. 9170fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) { 9180fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LoadInst *LI = dyn_cast<LoadInst>(*UI++); 9190fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (!LI) continue; 9200fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9210fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner unsigned LoadIdx = LBI.getInstructionIndex(LI); 9220fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9230fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Find the nearest store that has a lower than this load. 9240fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoresByIndexTy::iterator I = 9250fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(), 9267d9663c70b3300070298d716dba6e6f6ce2d1e3eDouglas Gregor std::pair<unsigned, StoreInst*>(LoadIdx, static_cast<StoreInst*>(0)), 9270fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoreIndexSearchPredicate()); 9280fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9290fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // If there is no store before this load, then we can't promote this load. 9300fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (I == StoresByIndex.begin()) { 9310fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Can't handle this load, bail out. 9320fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner Info.UsingBlocks.push_back(LI->getParent()); 9330fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner continue; 9340fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 9350fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9360fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Otherwise, there was a store before this load, the load takes its value. 9370fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner --I; 9380fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LI->replaceAllUsesWith(I->second->getOperand(0)); 9391df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 9400fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner AST->deleteValue(LI); 9410fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LI->eraseFromParent(); 9420fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(LI); 9437a5745b38ccdf2794a6f04f01a1c8115ec223ad8Chris Lattner } 944e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner} 945e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 946b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez// Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value 947b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez// that has an associated llvm.dbg.decl intrinsic. 948b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandezvoid PromoteMem2Reg::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, 9493511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner StoreInst *SI) { 950b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez DIVariable DIVar(DDI->getVariable()); 951e9f8f5e6004fd49f2aff4dd23db8e9b0e4454fc6Devang Patel if (!DIVar.Verify()) 952b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez return; 953b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 954b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez if (!DIF) 955b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez DIF = new DIFactory(*SI->getParent()->getParent()->getParent()); 9563511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner Instruction *DbgVal = DIF->InsertDbgValueIntrinsic(SI->getOperand(0), 0, 957b7ae53f035e7f9e90bd837b546ea516c00381b51Victor Hernandez DIVar, SI); 9583511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner 9593511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner // Propagate any debug metadata from the store onto the dbg.value. 9607bc230ec6aad867333db43636f7beda68bb628aeDan Gohman DebugLoc SIDL = SI->getDebugLoc(); 9617bc230ec6aad867333db43636f7beda68bb628aeDan Gohman if (!SIDL.isUnknown()) 9627bc230ec6aad867333db43636f7beda68bb628aeDan Gohman DbgVal->setDebugLoc(SIDL); 96393031ac032219c2200de2df1c73e594a0496ecefDevang Patel // Otherwise propagate debug metadata from dbg.declare. 9647bc230ec6aad867333db43636f7beda68bb628aeDan Gohman else 9657bc230ec6aad867333db43636f7beda68bb628aeDan Gohman DbgVal->setDebugLoc(DDI->getDebugLoc()); 966b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez} 967e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 9689f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 9699f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// Alloca returns true if there wasn't already a phi-node for that variable 9709f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// 9713c881cb4ce4adc1765378360ba6383bdd64287f3Chris Lattnerbool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 972b05099bf42d54838f0648569d4ae1a98dfa7da7bDuncan Sands unsigned &Version) { 97362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner // Look up the basic-block in question. 974dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *&PN = NewPhiNodes[std::make_pair(BB, AllocaNo)]; 97598a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 9769f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // If the BB already has a phi node added for the i'th alloca then we're done! 977dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (PN) return false; 97898a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 9791d608abbc07bbc7c78c20da6b305ef14c6c30e8eChris Lattner // Create a PhiNode using the dereferenced type... and add the phi-node to the 980393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner // BasicBlock. 981051a950000e21935165db56695e35bade668193bGabor Greif PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), 982fe09b2098ac483f6d6ce6ea4ab237a9539bdb6b9Daniel Dunbar Allocas[AllocaNo]->getName() + "." + Twine(Version++), 9837f93dc8345fb33652973e35cae4c3b58addf4f87Daniel Dunbar BB->begin()); 984f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner ++NumPHIInsert; 985dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PhiToAllocaMap[PN] = AllocaNo; 986e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner PN->reserveOperandSpace(getNumPreds(BB)); 98762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 9881df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && PN->getType()->isPointerTy()) 98962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->copyValue(PointerAllocaValues[AllocaNo], PN); 99062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 9919f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner return true; 9929f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 99398a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 99469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// RenamePass - Recursively traverse the CFG of the function, renaming loads and 99569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// stores to the allocas which we are promoting. IncomingVals indicates what 99669091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// value each Alloca contains on exit from the predecessor block Pred. 99769091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// 998d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 999483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner RenamePassData::ValVector &IncomingVals, 1000ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> &Worklist) { 10011e76af30116f4554fcf02c0f95705af1504b9645Chris LattnerNextIteration: 1002dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If we are inserting any phi nodes into this BB, they will already be in the 1003dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // block. 1004dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) { 1005dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If we have PHI nodes to update, compute the number of edges from Pred to 1006dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // BB. 1007bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman if (PhiToAllocaMap.count(APN)) { 10082663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // We want to be able to distinguish between PHI nodes being inserted by 10092663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // this invocation of mem2reg from those phi nodes that already existed in 10102663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // the IR before mem2reg was run. We determine that APN is being inserted 10112663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // because it is missing incoming edges. All other PHI nodes being 10122663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // inserted by this pass of mem2reg will have the same number of incoming 10132663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // operands so far. Remember this count. 10142663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner unsigned NewPHINumOperands = APN->getNumOperands(); 10152663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner 1016dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned NumEdges = 0; 10176e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I) 10186e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky if (*I == BB) 1019dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++NumEdges; 1020dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner assert(NumEdges && "Must be at least one edge from Pred to BB!"); 1021dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1022dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Add entries for all the phis. 1023dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock::iterator PNI = BB->begin(); 1024dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner do { 1025dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned AllocaNo = PhiToAllocaMap[APN]; 1026dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1027dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Add N incoming values to the PHI node. 1028dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0; i != NumEdges; ++i) 1029dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner APN->addIncoming(IncomingVals[AllocaNo], Pred); 1030dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1031dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // The currently active variable for this block is now the PHI. 1032dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner IncomingVals[AllocaNo] = APN; 1033dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1034dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Get the next phi node. 1035dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++PNI; 1036dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner APN = dyn_cast<PHINode>(PNI); 1037dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (APN == 0) break; 1038dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 10392663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // Verify that it is missing entries. If not, it is not being inserted 10402663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // by this mem2reg invocation so we want to ignore it. 10412663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner } while (APN->getNumOperands() == NewPHINumOperands); 1042dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 10439157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner } 1044dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1045dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Don't revisit blocks. 1046dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (!Visited.insert(BB)) return; 104798a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 1048521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 10490fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *I = II++; // get the instruction, increment iterator 105098a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 10519f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 10521e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand()); 10531e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (!Src) continue; 10541e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 10551e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 10561e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (AI == AllocaLookup.end()) continue; 105798a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 10581e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner Value *V = IncomingVals[AI->second]; 10591e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 10601e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner // Anything using the load now uses the current value. 10611e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner LI->replaceAllUsesWith(V); 10621df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 10631e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner AST->deleteValue(LI); 10641e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner BB->getInstList().erase(LI); 10659f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1066cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner // Delete this instruction and mark the name as the current holder of the 10679f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // value 10681e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand()); 10691e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (!Dest) continue; 10701e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 10711e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 10721e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (ai == AllocaLookup.end()) 10731e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner continue; 10741e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 10751e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner // what value were we writing? 10761e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner IncomingVals[ai->second] = SI->getOperand(0); 1077b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez // Record debuginfo for the store before removing it. 10783511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner if (DbgDeclareInst *DDI = AllocaDbgDeclares[ai->second]) 10793511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner ConvertDebugDeclareToDebugValue(DDI, SI); 10801e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner BB->getInstList().erase(SI); 10819f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 10829f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 1083521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner 10841e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner // 'Recurse' to our successors. 10856e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky succ_iterator I = succ_begin(BB), E = succ_end(BB); 10866e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky if (I == E) return; 10876e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky 1088bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman // Keep track of the successors so we don't visit the same successor twice 1089bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman SmallPtrSet<BasicBlock*, 8> VisitedSuccs; 10906e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky 1091bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman // Handle the first successor without using the worklist. 1092bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman VisitedSuccs.insert(*I); 10931e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner Pred = BB; 10946e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky BB = *I; 1095bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman ++I; 1096bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman 1097bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman for (; I != E; ++I) 1098bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman if (VisitedSuccs.insert(*I)) 1099bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman Worklist.push_back(RenamePassData(*I, Pred, IncomingVals)); 1100bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman 11011e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner goto NextIteration; 1102d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner} 1103b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt 1104d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// PromoteMemToReg - Promote the specified list of alloca instructions into 1105d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// scalar registers, inserting PHI nodes as appropriate. This function makes 1106d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// use of DominanceFrontier information. This function does not modify the CFG 1107d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// of the function at all. All allocas must be from the same function. 1108d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 110962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// If AST is specified, the specified tracker is updated to reflect changes 111062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// made to the IR. 111162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// 1112f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 1113419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DominatorTree &DT, AliasSetTracker *AST) { 11140fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there is nothing to do, bail out... 11150fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (Allocas.empty()) return; 11166cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 1117419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PromoteMem2Reg(Allocas, DT, AST).run(); 1118b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} 1119