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" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Hashing.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasSetTracker.h" 37d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 38d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 39d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/ValueTracking.h" 40d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/DIBuilder.h" 410bcbd1df7a204e1e512f1a27066d725309de1b13Bill Wendling#include "llvm/DebugInfo.h" 420b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 430b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 440b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 450b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 460b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 470b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 48393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner#include "llvm/Support/CFG.h" 49d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 5020aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 51419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich#include <queue> 52f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 53d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 54bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris LattnerSTATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block"); 55bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris LattnerSTATISTIC(NumSingleStore, "Number of alloca's promoted with a single store"); 56bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris LattnerSTATISTIC(NumDeadAlloca, "Number of dead alloca's removed"); 57f12f8def399c80aa283783ca406434ee2f80b49fChris LattnerSTATISTIC(NumPHIInsert, "Number of PHI nodes inserted"); 58bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 59dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattnernamespace llvm { 60dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattnertemplate<> 6176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo<std::pair<BasicBlock*, unsigned> > { 6276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typedef std::pair<BasicBlock*, unsigned> EltTy; 6376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static inline EltTy getEmptyKey() { 6476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U); 65dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 6676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static inline EltTy getTombstoneKey() { 6776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U); 68dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 69dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) { 70e5121f2e22919349350599c528aeae242b5db601Chandler Carruth using llvm::hash_value; 71e5121f2e22919349350599c528aeae242b5db601Chandler Carruth return static_cast<unsigned>(hash_value(Val)); 7276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner } 7376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static bool isEqual(const EltTy &LHS, const EltTy &RHS) { 7476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner return LHS == RHS; 75dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 76dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner}; 77dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner} 78dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 79d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// isAllocaPromotable - Return true if this alloca is legal for promotion. 80a744b77e11a375927ffe6b807b99cd91cb55e2baChris Lattner/// This is true if there are only loads and stores to the alloca. 81d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 8241968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patelbool llvm::isAllocaPromotable(const AllocaInst *AI) { 83fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // FIXME: If the memory unit is of pointer or integer type, we can permit 84fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner // assignments to subsections of the memory unit. 85fb743a937f6856e3ab1f8ed599677038750a550eChris Lattner 869f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov // Only allow direct and non-volatile loads and stores... 8760ad781c61815ca5b8dc2a45a102e1c8af65992fGabor Greif for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end(); 885417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif UI != UE; ++UI) { // Loop over all of the uses of the alloca 895417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif const User *U = *UI; 905417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { 91fd06b3cfa184a357f5f37625f50be104c8573fc3Eli Friedman // Note that atomic loads can be transformed; atomic semantics do 92fd06b3cfa184a357f5f37625f50be104c8573fc3Eli Friedman // not have any meaning for a local alloca. 939f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov if (LI->isVolatile()) 949f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov return false; 955417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 962d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner if (SI->getOperand(0) == AI) 972d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner return false; // Don't allow a store OF the AI, only INTO the AI. 98fd06b3cfa184a357f5f37625f50be104c8573fc3Eli Friedman // Note that atomic stores can be transformed; atomic semantics do 99fd06b3cfa184a357f5f37625f50be104c8573fc3Eli Friedman // not have any meaning for a local alloca. 1009f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov if (SI->isVolatile()) 1019f528e628090ee0ffca35d4577c23b6544f9a119Anton Korobeynikov return false; 1021d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) { 1031d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (II->getIntrinsicID() != Intrinsic::lifetime_start && 1041d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky II->getIntrinsicID() != Intrinsic::lifetime_end) 1051d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky return false; 1061d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 1071d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (BCI->getType() != Type::getInt8PtrTy(U->getContext())) 1081d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky return false; 1091d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (!onlyUsedByLifetimeMarkers(BCI)) 1101d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky return false; 1111d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 1121d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (GEPI->getType() != Type::getInt8PtrTy(U->getContext())) 1131d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky return false; 1141d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (!GEPI->hasAllZeroIndices()) 1151d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky return false; 1161d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (!onlyUsedByLifetimeMarkers(GEPI)) 1171d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky return false; 1182d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } else { 119746867c8b6ded86e450131852d0949644f54927cDaniel Dunbar return false; 1202d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner } 1215417a03b55e90cbd7e8ac5e8eed4ab45890af7c3Gabor Greif } 122fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 123d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner return true; 124d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner} 125d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner 126b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardtnamespace { 1275dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner struct AllocaInfo; 128a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 129a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel // Data package used by RenamePass() 1306726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class RenamePassData { 131a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel public: 132483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner typedef std::vector<Value *> ValVector; 133483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner 1340daf77e8034cfb70fbffbfa77d138b78b55af303Chandler Carruth RenamePassData() : BB(NULL), Pred(NULL), Values() {} 135a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel RenamePassData(BasicBlock *B, BasicBlock *P, 136483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner const ValVector &V) : BB(B), Pred(P), Values(V) {} 137a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel BasicBlock *BB; 138a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel BasicBlock *Pred; 139483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner ValVector Values; 14063cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner 14163cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner void swap(RenamePassData &RHS) { 14263cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner std::swap(BB, RHS.BB); 14363cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner std::swap(Pred, RHS.Pred); 14463cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner Values.swap(RHS.Values); 14563cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner } 146a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel }; 14733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 14833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of 14933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// load/store instructions in the block that directly load or store an alloca. 15033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// 15133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// This functionality is important because it avoids scanning large basic 15233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// blocks multiple times when promoting many allocas in the same block. 1536726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class LargeBlockInfo { 15433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// InstNumbers - For each instruction that we track, keep the index of the 15533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// instruction. The index starts out as the number of the instruction from 15633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// the start of the block. 15733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner DenseMap<const Instruction *, unsigned> InstNumbers; 15833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner public: 15933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 16033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// isInterestingInstruction - This code only looks at accesses to allocas. 16133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner static bool isInterestingInstruction(const Instruction *I) { 16233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) || 16333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1))); 16433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 16533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 16633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// getInstructionIndex - Get or calculate the index of the specified 16733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner /// instruction. 16833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner unsigned getInstructionIndex(const Instruction *I) { 16933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner assert(isInterestingInstruction(I) && 17033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner "Not a load/store to/from an alloca?"); 17133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 17233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // If we already have this instruction number, return it. 17333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I); 17433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (It != InstNumbers.end()) return It->second; 17533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 17633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Scan the whole block to get the instruction. This accumulates 17733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // information for every interesting instruction in the block, in order to 17833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // avoid gratuitus rescans. 17933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner const BasicBlock *BB = I->getParent(); 18033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner unsigned InstNo = 0; 18133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner for (BasicBlock::const_iterator BBI = BB->begin(), E = BB->end(); 18233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner BBI != E; ++BBI) 18333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (isInterestingInstruction(BBI)) 18433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner InstNumbers[BBI] = InstNo++; 18533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner It = InstNumbers.find(I); 18633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 18733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner assert(It != InstNumbers.end() && "Didn't insert instruction?"); 18833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner return It->second; 18933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 19033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 19133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner void deleteValue(const Instruction *I) { 19233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner InstNumbers.erase(I); 19333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 19433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 19533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner void clear() { 19633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner InstNumbers.clear(); 19733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } 19833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner }; 199a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 2006726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct PromoteMem2Reg { 20162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Allocas - The alloca instructions being promoted. 20262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 20324011be956e80e43d111d29cd53ca40e242e53dfChris Lattner std::vector<AllocaInst*> Allocas; 204326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DominatorTree &DT; 205afd0d0e8a751ff07dc5ac3f1862bb7697de31d2aDevang Patel DIBuilder *DIB; 206a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 20762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AST - An AliasSetTracker object to update. If null, don't update it. 20862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 20962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AliasSetTracker *AST; 2100a205a459884ec745df1c529396dd921f029dafdOwen Anderson 21162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// AllocaLookup - Reverse mapping of Allocas. 21262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 21359f5319719dd66570dc48d8415936a06c67672ffCameron Zwarich DenseMap<AllocaInst*, unsigned> AllocaLookup; 2149e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 2156ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge /// NewPhiNodes - The PhiNodes we're adding. That map is used to simplify 2166ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge /// some Phi nodes as we iterate over it, so it should have deterministic 2176ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge /// iterators. We could use a MapVector, but since we already maintain a 2186ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge /// map from BasicBlock* to a stable numbering (BBNumbers), the DenseMap is 2196ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge /// more efficient (also supports removal). 22062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 2216a02bbcdae9996a984ccb2497cb89719a69413efJulien Lerouge DenseMap<std::pair<unsigned, unsigned>, PHINode*> NewPhiNodes; 222dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 223dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas 224dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner /// it corresponds to. 225dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner DenseMap<PHINode*, unsigned> PhiToAllocaMap; 226dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 22762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 22862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// each alloca that is of pointer type, we keep track of what to copyValue 22962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// to the inserted PHI nodes here. 23062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 23162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner std::vector<Value*> PointerAllocaValues; 23262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 233b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez /// AllocaDbgDeclares - For each alloca, we keep track of the dbg.declare 234b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez /// intrinsic that describes it, if any, so that we can convert it to a 235b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez /// dbg.value intrinsic if the alloca gets promoted. 236d044612489c567b9ba35dc0f6fa0d3b12d78bc59Victor Hernandez SmallVector<DbgDeclareInst*, 8> AllocaDbgDeclares; 237b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 23862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// Visited - The set of basic blocks the renamer has already visited. 23962e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// 240c670f3da72a14d10eeca7ee88abb875b57eaa6a7Chris Lattner SmallPtrSet<BasicBlock*, 16> Visited; 24198a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 24262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// BBNumbers - Contains a stable numbering of basic blocks to avoid 24362e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner /// non-determinstic behavior. 244d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner DenseMap<BasicBlock*, unsigned> BBNumbers; 24563168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 246419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich /// DomLevels - Maps DomTreeNodes to their level in the dominator tree. 247419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DenseMap<DomTreeNode*, unsigned> DomLevels; 248419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 249e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner /// BBNumPreds - Lazily compute the number of predecessors a block has. 250e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner DenseMap<const BasicBlock*, unsigned> BBNumPreds; 251b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner public: 2520fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt, 253419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich AliasSetTracker *ast) 254afd0d0e8a751ff07dc5ac3f1862bb7697de31d2aDevang Patel : Allocas(A), DT(dt), DIB(0), AST(ast) {} 255d044612489c567b9ba35dc0f6fa0d3b12d78bc59Victor Hernandez ~PromoteMem2Reg() { 256afd0d0e8a751ff07dc5ac3f1862bb7697de31d2aDevang Patel delete DIB; 257d044612489c567b9ba35dc0f6fa0d3b12d78bc59Victor Hernandez } 258b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 259d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner void run(); 260b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner 261326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel /// dominates - Return true if BB1 dominates BB2 using the DominatorTree. 262fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner /// 263fed40df846438356d9edd5f6bd5191cd900e3c59Chris Lattner bool dominates(BasicBlock *BB1, BasicBlock *BB2) const { 264326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel return DT.dominates(BB1, BB2); 2657e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner } 2667e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner 267b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner private: 268bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner void RemoveFromAllocasList(unsigned &AllocaIdx) { 269bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Allocas[AllocaIdx] = Allocas.back(); 270bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Allocas.pop_back(); 271bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner --AllocaIdx; 272bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 273e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner 274e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner unsigned getNumPreds(const BasicBlock *BB) { 275e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner unsigned &NP = BBNumPreds[BB]; 276e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner if (NP == 0) 277e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner NP = std::distance(pred_begin(BB), pred_end(BB))+1; 278e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner return NP-1; 279e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner } 280e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner 2810ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 2820ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner AllocaInfo &Info); 283f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 284f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 285f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> &LiveInBlocks); 286bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 28733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, 28833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI); 2890fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 29033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI); 291aee6a656e84956a2e3c9d7436f68a4a3cfa64feeVictor Hernandez 292cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner void RenamePass(BasicBlock *BB, BasicBlock *Pred, 293483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner RenamePassData::ValVector &IncVals, 294ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> &Worklist); 295b05099bf42d54838f0648569d4ae1a98dfa7da7bDuncan Sands bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version); 296b9ddce65c281f023780d2b6578e7ed6d2913a2cbChris Lattner }; 297bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 298bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner struct AllocaInfo { 299491d8d43702a76b6d73ffbd85c368a4be51c44aeCameron Zwarich SmallVector<BasicBlock*, 32> DefiningBlocks; 300491d8d43702a76b6d73ffbd85c368a4be51c44aeCameron Zwarich SmallVector<BasicBlock*, 32> UsingBlocks; 301bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 302bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner StoreInst *OnlyStore; 303bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner BasicBlock *OnlyBlock; 304bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner bool OnlyUsedInOneBlock; 305bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 306bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Value *AllocaPointerVal; 307b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez DbgDeclareInst *DbgDeclare; 308bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 309bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner void clear() { 310bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner DefiningBlocks.clear(); 311bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner UsingBlocks.clear(); 312bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyStore = 0; 313bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyBlock = 0; 314bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyUsedInOneBlock = true; 315bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaPointerVal = 0; 316b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez DbgDeclare = 0; 317bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 318bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 319bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our 320bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner /// ivars. 321bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner void AnalyzeAlloca(AllocaInst *AI) { 322bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner clear(); 323180ffaef18bdd0b1b972657b949c67cf96a20a48Devang Patel 324bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // As we scan the uses of the alloca instruction, keep track of stores, 325bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // and decide whether all of the loads and stores to the alloca are within 326bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // the same basic block. 3272b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 3282b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner UI != E;) { 3292b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner Instruction *User = cast<Instruction>(*UI++); 330e31dc355b264b0956789d47534c779b943c85216Victor Hernandez 3312b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 332bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner // Remember the basic blocks which define new values for the alloca 333bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner DefiningBlocks.push_back(SI->getParent()); 334bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaPointerVal = SI->getOperand(0); 335bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyStore = SI; 336bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } else { 337bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner LoadInst *LI = cast<LoadInst>(User); 338e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner // Otherwise it must be a load instruction, keep track of variable 339e7b653dabe83546c2c13e4595c3ed068eccb88bdChris Lattner // reads. 340bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner UsingBlocks.push_back(LI->getParent()); 341bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaPointerVal = LI; 342bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 343bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 344bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (OnlyUsedInOneBlock) { 345bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (OnlyBlock == 0) 346bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyBlock = User->getParent(); 347bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner else if (OnlyBlock != User->getParent()) 348bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner OnlyUsedInOneBlock = false; 349bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 350bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 351b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 3523511c70d180f662c8b2b8506d9c6b45a24720098Chris Lattner DbgDeclare = FindAllocaDbgDeclare(AI); 353bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner } 354bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner }; 355419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 356419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich typedef std::pair<DomTreeNode*, unsigned> DomTreeNodePair; 357419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 358419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich struct DomTreeNodeCompare { 359419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich bool operator()(const DomTreeNodePair &LHS, const DomTreeNodePair &RHS) { 360419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich return LHS.second < RHS.second; 361419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 362419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich }; 363b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} // end of anonymous namespace 364d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner 3651d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewyckystatic void removeLifetimeIntrinsicUsers(AllocaInst *AI) { 3661d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky // Knowing that this alloca is promotable, we know that it's safe to kill all 3671d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky // instructions except for load and store. 3681d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky 3691d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end(); 3701d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky UI != UE;) { 3711d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky Instruction *I = cast<Instruction>(*UI); 3721d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky ++UI; 3731d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (isa<LoadInst>(I) || isa<StoreInst>(I)) 3741d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky continue; 3751d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky 3761d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky if (!I->getType()->isVoidTy()) { 3771d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky // The only users of this bitcast/GEP instruction are lifetime intrinsics. 3781d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky // Follow the use/def chain to erase them now instead of leaving it for 3791d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky // dead code elimination later. 3801d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 3811d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky UI != UE;) { 3821d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky Instruction *Inst = cast<Instruction>(*UI); 3831d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky ++UI; 3841d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky Inst->eraseFromParent(); 3851d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky } 3861d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky } 3871d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky I->eraseFromParent(); 3881d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky } 3891d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky} 3905dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 391d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::run() { 392419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Function &F = *DT.getRoot()->getParent(); 3930fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner 39462e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) PointerAllocaValues.resize(Allocas.size()); 395b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez AllocaDbgDeclares.resize(Allocas.size()); 39663168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 397bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner AllocaInfo Info; 39833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo LBI; 399bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 40069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 40169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaInst *AI = Allocas[AllocaNum]; 4029e38fbf57feef1e6680c0aed64b1d919b4e01626Chris Lattner 40341968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patel assert(isAllocaPromotable(AI) && 404d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "Cannot promote non-promotable alloca!"); 40569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner assert(AI->getParent()->getParent() == &F && 406d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner "All allocas should be in the same function, which is same as DF!"); 4079157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner 4081d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky removeLifetimeIntrinsicUsers(AI); 4091d665c9a9fb32c3d6483fa146ba85d03b1e9d97fNick Lewycky 41024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (AI->use_empty()) { 41124011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // If there are no uses of the alloca, just delete it now. 41262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(AI); 413634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner AI->eraseFromParent(); 41424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 41524011be956e80e43d111d29cd53ca40e242e53dfChris Lattner // Remove the alloca from the Allocas list, since it has been processed 416bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner RemoveFromAllocasList(AllocaNum); 417bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner ++NumDeadAlloca; 41824011be956e80e43d111d29cd53ca40e242e53dfChris Lattner continue; 41924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner } 420bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner 42169091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner // Calculate the set of read and write-locations for each alloca. This is 4222d11f167e69c9668ff6c6b86451fb124c8af7bccChris Lattner // analogous to finding the 'uses' and 'definitions' of each variable. 423bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner Info.AnalyzeAlloca(AI); 42424011be956e80e43d111d29cd53ca40e242e53dfChris Lattner 42536ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // If there is only a single store to this value, replace any loads of 42636ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // it that are directly dominated by the definition with the value stored. 427bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (Info.DefiningBlocks.size() == 1) { 42833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner RewriteSingleStoreAlloca(AI, Info, LBI); 42936ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 43036ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // Finally, after the scan, check to see if the store is all that is left. 431bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner if (Info.UsingBlocks.empty()) { 432acb6f5096f566cb9ed41226c8dd95368209cc892Chad Rosier // Record debuginfo for the store and remove the declaration's 433acb6f5096f566cb9ed41226c8dd95368209cc892Chad Rosier // debuginfo. 4341897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez if (DbgDeclareInst *DDI = Info.DbgDeclare) { 4355ee20680c7ebc765950983633e19fafab5235245Devang Patel if (!DIB) 4365ee20680c7ebc765950983633e19fafab5235245Devang Patel DIB = new DIBuilder(*DDI->getParent()->getParent()->getParent()); 4375ee20680c7ebc765950983633e19fafab5235245Devang Patel ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore, *DIB); 4381897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez DDI->eraseFromParent(); 4391897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez } 4404f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner // Remove the (now dead) store and alloca. 4414f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner Info.OnlyStore->eraseFromParent(); 44233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.deleteValue(Info.OnlyStore); 44333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 4444f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner if (AST) AST->deleteValue(AI); 4454f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner AI->eraseFromParent(); 44633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.deleteValue(AI); 4474f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner 44836ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner // The alloca has been processed, move on. 449bbe104002fe7398bbde5d5ec2c2e5e324cf72305Chris Lattner RemoveFromAllocasList(AllocaNum); 4504f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner 4514f63e76cda86b676e4f0e31fd35b812e2f8dd57fChris Lattner ++NumSingleStore; 45236ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner continue; 45336ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 45436ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner } 45536ba5006df1dee8bb8789ee817f169af022ae239Chris Lattner 456fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner // If the alloca is only read and written in one basic block, just perform a 457fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner // linear sweep over the block to eliminate it. 458fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner if (Info.OnlyUsedInOneBlock) { 4590fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner PromoteSingleBlockAlloca(AI, Info, LBI); 460fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner 4610fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Finally, after the scan, check to see if the stores are all that is 4620fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // left. 4630fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (Info.UsingBlocks.empty()) { 4640fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4650fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Remove the (now dead) stores and alloca. 4660fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner while (!AI->use_empty()) { 4670fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoreInst *SI = cast<StoreInst>(AI->use_back()); 468b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez // Record debuginfo for the store before removing it. 4695ee20680c7ebc765950983633e19fafab5235245Devang Patel if (DbgDeclareInst *DDI = Info.DbgDeclare) { 4705ee20680c7ebc765950983633e19fafab5235245Devang Patel if (!DIB) 4715ee20680c7ebc765950983633e19fafab5235245Devang Patel DIB = new DIBuilder(*SI->getParent()->getParent()->getParent()); 4725ee20680c7ebc765950983633e19fafab5235245Devang Patel ConvertDebugDeclareToDebugValue(DDI, SI, *DIB); 4735ee20680c7ebc765950983633e19fafab5235245Devang Patel } 4740fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner SI->eraseFromParent(); 4750fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(SI); 4760fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 4770fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4780fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (AST) AST->deleteValue(AI); 4790fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner AI->eraseFromParent(); 4800fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(AI); 4810fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4820fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // The alloca has been processed, move on. 4830fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner RemoveFromAllocasList(AllocaNum); 4840fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 4851897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez // The alloca's debuginfo can be removed as well. 4861897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez if (DbgDeclareInst *DDI = Info.DbgDeclare) 4871897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez DDI->eraseFromParent(); 4881897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez 4890fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner ++NumLocalPromoted; 4900fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner continue; 4910fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 492fb312c7e449bbb8b780603bf44620be91d6a65bbChris Lattner } 493419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 494419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // If we haven't computed dominator tree levels, do so now. 495419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (DomLevels.empty()) { 496419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich SmallVector<DomTreeNode*, 32> Worklist; 497419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 498419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Root = DT.getRootNode(); 499419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomLevels[Root] = 0; 500419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(Root); 501419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 502419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich while (!Worklist.empty()) { 503419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Node = Worklist.pop_back_val(); 504419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned ChildLevel = DomLevels[Node] + 1; 505419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); 506419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich CI != CE; ++CI) { 507419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomLevels[*CI] = ChildLevel; 508419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(*CI); 509419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 510419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 511419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 512419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 51363168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // If we haven't computed a numbering for the BB's in the function, do so 51463168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner // now. 515d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner if (BBNumbers.empty()) { 516d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner unsigned ID = 0; 517d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 518d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner BBNumbers[I] = ID++; 519d3874049a55fe1af515c4f0d8f5a4040803567cbChris Lattner } 52063168d2244d754b084bc107b3a1929b8abbd4dbdChris Lattner 5210ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // If we have an AST to keep updated, remember some pointer value that is 5220ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // stored into the alloca. 5230ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner if (AST) 5240ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal; 525b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez 526b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez // Remember the dbg.declare intrinsic describing this alloca, if any. 527b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez if (Info.DbgDeclare) AllocaDbgDeclares[AllocaNum] = Info.DbgDeclare; 5280ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner 5290ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // Keep the reverse mapping of the 'Allocas' array for the rename pass. 53069091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 5310ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner 5320ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // At this point, we're committed to promoting the alloca using IDF's, and 53333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // the standard SSA construction algorithm. Determine which blocks need PHI 5340ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // nodes and see if we can optimize out some work by avoiding insertion of 5350ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner // dead phi nodes. 5360ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner DetermineInsertionPoint(AI, AllocaNum, Info); 5379f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 538fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 53924011be956e80e43d111d29cd53ca40e242e53dfChris Lattner if (Allocas.empty()) 54024011be956e80e43d111d29cd53ca40e242e53dfChris Lattner return; // All of the allocas must have been trivial! 5419f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 54233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.clear(); 54333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 54433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 5455b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // Set the incoming values for the basic block to be null values for all of 5465b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // the alloca's. We do this in case there is a load of a value that has not 5475b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // been stored yet. In this case, it will get this null value. 5485b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner // 549483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner RenamePassData::ValVector Values(Allocas.size()); 5505b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 5519e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 5525b5df1747feac197fd839c956952fd4d79c58e79Chris Lattner 5539f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // Walks all basic blocks in the function performing the SSA rename algorithm 5549f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // and inserting the phi nodes we marked as necessary 5559f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // 556ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> RenamePassWorkList; 557d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values)); 558321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman do { 55963cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner RenamePassData RPD; 56063cdcaa3d6c33cc1923797259bb8e5d9d9a899b1Chris Lattner RPD.swap(RenamePassWorkList.back()); 561d64d3a1d283df31625b7616982a575db4734f6e5Devang Patel RenamePassWorkList.pop_back(); 562a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel // RenamePass may add new worklist entries. 563ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList); 564321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman } while (!RenamePassWorkList.empty()); 565a5b7dc5ef8cc8ed5a07fef247328ea53c32f542cDevang Patel 566afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // The renamer uses the Visited set to avoid infinite loops. Clear it now. 5670fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Visited.clear(); 5689f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 569634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // Remove the allocas themselves from the function. 5700fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 5710fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *A = Allocas[i]; 5729f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner 5730fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there are any uses of the alloca instructions left, they must be in 574b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich // unreachable basic blocks that were not processed by walking the dominator 575b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich // tree. Just delete the users now. 5760fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (!A->use_empty()) 5779e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson A->replaceAllUsesWith(UndefValue::get(A->getType())); 57862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner if (AST) AST->deleteValue(A); 579634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner A->eraseFromParent(); 5809f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 581afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 5821897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez // Remove alloca's dbg.declare instrinsics from the function. 5831897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez for (unsigned i = 0, e = AllocaDbgDeclares.size(); i != e; ++i) 5841897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez if (DbgDeclareInst *DDI = AllocaDbgDeclares[i]) 5851897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez DDI->eraseFromParent(); 5861897ed3d37141e590781d983adbbeca937b3ccfcVictor Hernandez 587634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // Loop over all of the PHI nodes and see if there are any that we can get 588634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // rid of because they merge all of the same incoming values. This can 589634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // happen due to undef values coming into the PHI nodes. This process is 590634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner // iterative, because eliminating one PHI node can cause others to be removed. 591634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner bool EliminatedAPHI = true; 592634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner while (EliminatedAPHI) { 593634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner EliminatedAPHI = false; 594634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner 5956ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge // Iterating over NewPhiNodes is deterministic, so it is safe to try to 5968245a17a14e44df02c4488563d3ab50bee91c349Julien Lerouge // simplify and RAUW them as we go. If it was not, we could add uses to 5976ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge // the values we replace with in a non deterministic order, thus creating 5986ecdd0e8247b526521ab12124d157ca58c5de22fJulien Lerouge // non deterministic def->use chains. 5996a02bbcdae9996a984ccb2497cb89719a69413efJulien Lerouge for (DenseMap<std::pair<unsigned, unsigned>, PHINode*>::iterator I = 600dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) { 601dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *PN = I->second; 602cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands 603dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If this PHI node merges one value and/or undefs, get the value. 604618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier if (Value *V = SimplifyInstruction(PN, 0, 0, &DT)) { 6051df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && PN->getType()->isPointerTy()) 606bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman AST->deleteValue(PN); 607bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman PN->replaceAllUsesWith(V); 608bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman PN->eraseFromParent(); 609bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman NewPhiNodes.erase(I++); 610bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman EliminatedAPHI = true; 611bccfc24c4e8092e1ee18746dd4cee01247728faaDan Gohman continue; 612634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 613dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++I; 614634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 615634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner } 616634c76c08c34e5fb475527a4e91927a142dd9c46Chris Lattner 617afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // At this point, the renamer has added entries to PHI nodes for all reachable 618c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // code. Unfortunately, there may be unreachable blocks which the renamer 619c837615cf0bfef743f98bb7101f27c23f6f21ba1Chris Lattner // hasn't traversed. If this is the case, the PHI nodes may not 620afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // have incoming values for all predecessors. Loop over all PHI nodes we have 6217e40f63428fbdf64fdea5aa84459d7b3072a9a65Chris Lattner // created, inserting undef values if they are missing any incoming values. 622afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // 6236a02bbcdae9996a984ccb2497cb89719a69413efJulien Lerouge for (DenseMap<std::pair<unsigned, unsigned>, PHINode*>::iterator I = 624afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 625dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // We want to do this once per basic block. As such, only process a block 626dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // when we find the PHI that is the first entry in the block. 627dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PHINode *SomePHI = I->second; 628dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock *BB = SomePHI->getParent(); 629dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (&BB->front() != SomePHI) 630dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner continue; 631afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 632afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // Only do work here if there the PHI nodes are missing incoming values. We 633afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner // know that all PHI nodes that were inserted in a block will have the same 634dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // number of incoming values, so we can just check any of them. 635127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner if (SomePHI->getNumIncomingValues() == getNumPreds(BB)) 636dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner continue; 637127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner 638127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner // Get the preds for BB. 639127ed3c9299d8315723ffd470b598867fb49c972Chris Lattner SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 640dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 641dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Ok, now we know that all of the PHI nodes are missing entries for some 642dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // basic blocks. Start by sorting the incoming predecessors for efficient 643dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // access. 644dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner std::sort(Preds.begin(), Preds.end()); 645dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 646dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Now we loop through all BB's which have entries in SomePHI and remove 647dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // them from the Preds list. 648dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 649dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Do a log(n) search of the Preds list for the entry we want. 650dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SmallVector<BasicBlock*, 16>::iterator EntIt = 651dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner std::lower_bound(Preds.begin(), Preds.end(), 652dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->getIncomingBlock(i)); 653dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 654dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner "PHI node has entry for a block which is not a predecessor!"); 655dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 656dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Remove the entry 657dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner Preds.erase(EntIt); 658dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 659afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner 660dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // At this point, the blocks left in the preds list must have dummy 661dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // entries inserted into every PHI nodes for the block. Update all the phi 662dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // nodes in this block that we are inserting (there could be phis before 663dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // mem2reg runs). 664dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned NumBadPreds = SomePHI->getNumIncomingValues(); 665dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock::iterator BBI = BB->begin(); 666dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner while ((SomePHI = dyn_cast<PHINode>(BBI++)) && 667dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->getNumIncomingValues() == NumBadPreds) { 6689e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *UndefVal = UndefValue::get(SomePHI->getType()); 669dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 670dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner SomePHI->addIncoming(UndefVal, Preds[pred]); 671afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 672afa060ea3ff93eb99bafd41e593707cee3b9afa3Chris Lattner } 673dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 674dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner NewPhiNodes.clear(); 6759f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 67698a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 6775dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 678f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// ComputeLiveInBlocks - Determine which blocks the value is live in. These 679f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// are blocks which lead to uses. Knowing this allows us to avoid inserting 680f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// PHI nodes into blocks which don't lead to uses (thus, the inserted phi nodes 681f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner/// would be dead). 682f12f8def399c80aa283783ca406434ee2f80b49fChris Lattnervoid PromoteMem2Reg:: 683f12f8def399c80aa283783ca406434ee2f80b49fChris LattnerComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 684f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 685f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> &LiveInBlocks) { 686f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 687f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // To determine liveness, we must iterate through the predecessors of blocks 688f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // where the def is live. Blocks are added to the worklist if we need to 689f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // check their predecessors. Start with all the using blocks. 690403a8cdda5e76ea689693de16474650b4b0df818Dan Gohman SmallVector<BasicBlock*, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(), 691403a8cdda5e76ea689693de16474650b4b0df818Dan Gohman Info.UsingBlocks.end()); 692f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 693f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // If any of the using blocks is also a definition block, check to see if the 694f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // definition occurs before or after the use. If it happens before the use, 695f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // the value isn't really live-in. 696f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) { 697f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner BasicBlock *BB = LiveInBlockWorklist[i]; 698f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (!DefBlocks.count(BB)) continue; 699f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 700f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Okay, this is a block that both uses and defines the value. If the first 701f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // reference to the alloca is a def (store), then we know it isn't live-in. 702f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner for (BasicBlock::iterator I = BB->begin(); ; ++I) { 703f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 704f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (SI->getOperand(1) != AI) continue; 705f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 706f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // We found a store to the alloca before a load. The alloca is not 707f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // actually live-in here. 708f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner LiveInBlockWorklist[i] = LiveInBlockWorklist.back(); 709f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner LiveInBlockWorklist.pop_back(); 710f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner --i, --e; 711f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner break; 7122b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner } 7132b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner 7142b723a5e3d671197ec8f956261b95d4b57f7b0beChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 715f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (LI->getOperand(0) != AI) continue; 716f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 717f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Okay, we found a load before a store to the alloca. It is actually 718f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // live into this block. 719f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner break; 720f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 721f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 722f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 723f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 724f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Now that we have a set of blocks where the phi is live-in, recursively add 725f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // their predecessors until we find the full region the value is live. 726f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner while (!LiveInBlockWorklist.empty()) { 727e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); 728f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 729f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // The block really is live in here, insert it into the set. If already in 730f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // the set, then it has already been processed. 731f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (!LiveInBlocks.insert(BB)) 732f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner continue; 733f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 734f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Since the value is live into BB, it is either defined in a predecessor or 735f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // live into it to. Add the preds to the worklist unless they are a 736f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // defining block. 737f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 738f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner BasicBlock *P = *PI; 739f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 740f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // The value is not live into a predecessor if it defines the value. 741f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner if (DefBlocks.count(P)) 742f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner continue; 743f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 744f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Otherwise it is, add to the worklist. 745f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner LiveInBlockWorklist.push_back(P); 746f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 747f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 748f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner} 749f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 7500ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// DetermineInsertionPoint - At this point, we're committed to promoting the 7510ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// alloca using IDF's, and the standard SSA construction algorithm. Determine 7520ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// which blocks need phi nodes and see if we can optimize out some work by 7530ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner/// avoiding insertion of dead phi nodes. 7540ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattnervoid PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 7550ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner AllocaInfo &Info) { 756f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Unique the set of defining blocks for efficient lookup. 757f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> DefBlocks; 758f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); 759f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 760f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // Determine which blocks the value is live in. These are blocks which lead 761f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner // to uses. 762f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner SmallPtrSet<BasicBlock*, 32> LiveInBlocks; 763f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); 764f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner 765419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // Use a priority queue keyed on dominator tree level so that inserted nodes 766419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // are handled from the bottom of the dominator tree upwards. 767419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, 768419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNodeCompare> IDFPriorityQueue; 769419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich IDFPriorityQueue PQ; 770419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 771419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (SmallPtrSet<BasicBlock*, 32>::const_iterator I = DefBlocks.begin(), 772419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich E = DefBlocks.end(); I != E; ++I) { 773419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (DomTreeNode *Node = DT.getNode(*I)) 774419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PQ.push(std::make_pair(Node, DomLevels[Node])); 775419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 776419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 777443997de8b0eb538aac833390358f30c952f85fcCameron Zwarich SmallVector<std::pair<unsigned, BasicBlock*>, 32> DFBlocks; 778419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich SmallPtrSet<DomTreeNode*, 32> Visited; 779419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich SmallVector<DomTreeNode*, 32> Worklist; 780419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich while (!PQ.empty()) { 781419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNodePair RootPair = PQ.top(); 782419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PQ.pop(); 783419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Root = RootPair.first; 784419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned RootLevel = RootPair.second; 785419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 786419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // Walk all dominator tree children of Root, inspecting their CFG edges with 787419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // targets elsewhere on the dominator tree. Only targets whose level is at 788419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // most Root's level are added to the iterated dominance frontier of the 789419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // definition set. 790419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 791419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.clear(); 792419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(Root); 793419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 794419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich while (!Worklist.empty()) { 795419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *Node = Worklist.pop_back_val(); 796419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich BasicBlock *BB = Node->getBlock(); 797419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 798419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 799419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich ++SI) { 800419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DomTreeNode *SuccNode = DT.getNode(*SI); 801419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 802419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // Quickly skip all CFG edges that are also dominator tree edges instead 803419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich // of catching them below. 804419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (SuccNode->getIDom() == Node) 805419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 806419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 807419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned SuccLevel = DomLevels[SuccNode]; 808419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (SuccLevel > RootLevel) 809419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 810419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 811419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!Visited.insert(SuccNode)) 812419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 813419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 814419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich BasicBlock *SuccBB = SuccNode->getBlock(); 815419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!LiveInBlocks.count(SuccBB)) 816419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich continue; 817419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 818419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB)); 819419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!DefBlocks.count(SuccBB)) 820419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PQ.push(std::make_pair(SuccNode, SuccLevel)); 821419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 822419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 823419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE; 824419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich ++CI) { 825419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (!Visited.count(*CI)) 826419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich Worklist.push_back(*CI); 827419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich } 828f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner } 8290ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner } 830419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 831419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich if (DFBlocks.size() > 1) 832419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich std::sort(DFBlocks.begin(), DFBlocks.end()); 833419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich 834419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich unsigned CurrentVersion = 0; 835419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) 836419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion); 8370ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner} 8380ec8df3d5fa526cf460d7c60c515f181de28ac95Chris Lattner 8395dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner/// RewriteSingleStoreAlloca - If there is only a single store to this value, 8405dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner/// replace any loads of it that are directly dominated by the definition with 8415dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner/// the value stored. 8425dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattnervoid PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI, 84333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner AllocaInfo &Info, 84433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI) { 845b776a335b1a3260c27555db31f7ea0bee605de04Chris Lattner StoreInst *OnlyStore = Info.OnlyStore; 846d0458e5d4f29ce1e9ba1def22d06b362ae2c1999Chris Lattner bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0)); 84733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner BasicBlock *StoreBB = OnlyStore->getParent(); 84833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner int StoreIndex = -1; 84933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 85033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Clear out UsingBlocks. We will reconstruct it here if needed. 85133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Info.UsingBlocks.clear(); 852b776a335b1a3260c27555db31f7ea0bee605de04Chris Lattner 85333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) { 85433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Instruction *UserInst = cast<Instruction>(*UI++); 85533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (!isa<LoadInst>(UserInst)) { 85633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner assert(UserInst == OnlyStore && "Should only have load/stores"); 8575dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner continue; 858d0458e5d4f29ce1e9ba1def22d06b362ae2c1999Chris Lattner } 85933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LoadInst *LI = cast<LoadInst>(UserInst); 8605dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 86133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Okay, if we have a load from the alloca, we want to replace it with the 86233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // only value stored to the alloca. We can do this if the value is 86333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // dominated by the store. If not, we use the rest of the mem2reg machinery 86433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // to insert the phi nodes as needed. 86533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (!StoringGlobalVal) { // Non-instructions are always dominated. 86633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (LI->getParent() == StoreBB) { 86733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // If we have a use that is in the same block as the store, compare the 86833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // indices of the two instructions to see which one came first. If the 86933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // load came before the store, we can't handle it. 87033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (StoreIndex == -1) 87133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner StoreIndex = LBI.getInstructionIndex(OnlyStore); 87233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 87333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) { 87433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Can't handle this load, bail out. 87533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Info.UsingBlocks.push_back(StoreBB); 87633210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner continue; 8775dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 87833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner 87933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner } else if (LI->getParent() != StoreBB && 88033210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner !dominates(StoreBB, LI->getParent())) { 88133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // If the load and store are in different blocks, use BB dominance to 88233210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // check their relationships. If the store doesn't dom the use, bail 88333210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // out. 88433210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner Info.UsingBlocks.push_back(LI->getParent()); 88533210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner continue; 8865dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 8875dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 8885dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 88933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner // Otherwise, we *can* safely rewrite this load. 890794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner Value *ReplVal = OnlyStore->getOperand(0); 891794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner // If the replacement value is the load, this must occur in unreachable 892794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner // code. 893794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner if (ReplVal == LI) 894794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner ReplVal = UndefValue::get(LI->getType()); 895794c15dc71061d7c3cc6028fbe64eb30d0cdbb66Chris Lattner LI->replaceAllUsesWith(ReplVal); 8961df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 89733210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner AST->deleteValue(LI); 89833210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LI->eraseFromParent(); 89933210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LBI.deleteValue(LI); 9005dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner } 9015dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner} 9025dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 9037db949df789383acce98ef072f08794fdd5bd04eDan Gohmannamespace { 9045dd75b4ca7e582f44da2f50362e8ab4c59972b5fChris Lattner 9050fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner/// StoreIndexSearchPredicate - This is a helper predicate used to search by the 9060fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner/// first element of a pair. 9070fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattnerstruct StoreIndexSearchPredicate { 9080fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner bool operator()(const std::pair<unsigned, StoreInst*> &LHS, 9090fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner const std::pair<unsigned, StoreInst*> &RHS) { 9100fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner return LHS.first < RHS.first; 9110fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 9120fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner}; 9130fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9147db949df789383acce98ef072f08794fdd5bd04eDan Gohman} 9157db949df789383acce98ef072f08794fdd5bd04eDan Gohman 9160fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner/// PromoteSingleBlockAlloca - Many allocas are only used within a single basic 917e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// block. If this is the case, avoid traversing the CFG and inserting a lot of 918e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// potentially useless PHI nodes by just performing a single linear pass over 919e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// the basic block using the Alloca. 920e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner/// 9216cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// If we cannot promote this alloca (because it is read before it is written), 9226cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// return true. This is necessary in cases where, due to control flow, the 9236cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// alloca is potentially undefined on some control flow paths. e.g. code like 9246cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// this is potentially correct: 9256cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 9266cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// for (...) { if (c) { A = undef; undef = B; } } 9276cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 9286cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// ... so long as A is not used before undef is set. 9296cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner/// 9300fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattnervoid PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 93133210608bee7d28029febc0b835ebd0f760a7bc0Chris Lattner LargeBlockInfo &LBI) { 9320fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // The trickiest case to handle is when we have large blocks. Because of this, 9330fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // this code is optimized assuming that large blocks happen. This does not 9340fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // significantly pessimize the small block case. This uses LargeBlockInfo to 9350fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // make it efficient to get the index of various operations in the block. 9360fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9370fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Clear out UsingBlocks. We will reconstruct it here if needed. 9380fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner Info.UsingBlocks.clear(); 9390fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9400fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Walk the use-def list of the alloca, getting the locations of all stores. 9410fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner typedef SmallVector<std::pair<unsigned, StoreInst*>, 64> StoresByIndexTy; 9420fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoresByIndexTy StoresByIndex; 9430fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9440fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 9450fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner UI != E; ++UI) 9460fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 9470fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI)); 9480fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9490fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // If there are no stores to the alloca, just replace any loads with undef. 9500fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (StoresByIndex.empty()) { 9510fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) 9520fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) { 9539e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson LI->replaceAllUsesWith(UndefValue::get(LI->getType())); 9541df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 9550fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner AST->deleteValue(LI); 9560fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(LI); 9570fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LI->eraseFromParent(); 958e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 9590fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner return; 960e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner } 9617a5745b38ccdf2794a6f04f01a1c8115ec223ad8Chris Lattner 9620fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Sort the stores by their index, making it efficient to do a lookup with a 9630fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // binary search. 9640fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner std::sort(StoresByIndex.begin(), StoresByIndex.end()); 9650fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9660fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Walk all of the loads from this alloca, replacing them with the nearest 9670fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // store above them, if any. 9680fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) { 9690fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LoadInst *LI = dyn_cast<LoadInst>(*UI++); 9700fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (!LI) continue; 9710fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9720fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner unsigned LoadIdx = LBI.getInstructionIndex(LI); 9730fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9740fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Find the nearest store that has a lower than this load. 9750fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoresByIndexTy::iterator I = 9760fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(), 9777d9663c70b3300070298d716dba6e6f6ce2d1e3eDouglas Gregor std::pair<unsigned, StoreInst*>(LoadIdx, static_cast<StoreInst*>(0)), 9780fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner StoreIndexSearchPredicate()); 9790fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9800fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // If there is no store before this load, then we can't promote this load. 9810fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner if (I == StoresByIndex.begin()) { 9820fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Can't handle this load, bail out. 9830fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner Info.UsingBlocks.push_back(LI->getParent()); 9840fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner continue; 9850fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner } 9860fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner 9870fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner // Otherwise, there was a store before this load, the load takes its value. 9880fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner --I; 9890fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LI->replaceAllUsesWith(I->second->getOperand(0)); 9901df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 9910fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner AST->deleteValue(LI); 9920fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LI->eraseFromParent(); 9930fd77a579bbed0fa06720474f1c5b2e3cd75004fChris Lattner LBI.deleteValue(LI); 9947a5745b38ccdf2794a6f04f01a1c8115ec223ad8Chris Lattner } 995e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner} 996e47f78ed124b35dbd03df9b1471bbc3c7b88898fChris Lattner 9979f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 9989f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// Alloca returns true if there wasn't already a phi-node for that variable 9999f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner// 10003c881cb4ce4adc1765378360ba6383bdd64287f3Chris Lattnerbool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 1001b05099bf42d54838f0648569d4ae1a98dfa7da7bDuncan Sands unsigned &Version) { 100262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner // Look up the basic-block in question. 10036a02bbcdae9996a984ccb2497cb89719a69413efJulien Lerouge PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)]; 100498a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 10059f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // If the BB already has a phi node added for the i'th alloca then we're done! 1006dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (PN) return false; 100798a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 10081d608abbc07bbc7c78c20da6b305ef14c6c30e8eChris Lattner // Create a PhiNode using the dereferenced type... and add the phi-node to the 1009393689afa92c2ae3ccf7d40841f2dde3fc7f9784Chris Lattner // BasicBlock. 10103ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB), 1011fe09b2098ac483f6d6ce6ea4ab237a9539bdb6b9Daniel Dunbar Allocas[AllocaNo]->getName() + "." + Twine(Version++), 10127f93dc8345fb33652973e35cae4c3b58addf4f87Daniel Dunbar BB->begin()); 1013f12f8def399c80aa283783ca406434ee2f80b49fChris Lattner ++NumPHIInsert; 1014dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner PhiToAllocaMap[PN] = AllocaNo; 101562e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 10161df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && PN->getType()->isPointerTy()) 101762e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner AST->copyValue(PointerAllocaValues[AllocaNo], PN); 101862e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner 10199f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner return true; 10209f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner} 102198a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 102269091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// RenamePass - Recursively traverse the CFG of the function, renaming loads and 102369091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// stores to the allocas which we are promoting. IncomingVals indicates what 102469091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// value each Alloca contains on exit from the predecessor block Pred. 102569091be83bfcfcf52f9d0b1faba94675826607dbChris Lattner// 1026d99bf49a53d170112c0241a4393ab374666b04bdChris Lattnervoid PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 1027483ce14bf4746d8078d65a14f61319528e1a00f1Chris Lattner RenamePassData::ValVector &IncomingVals, 1028ac4aa4be9b25ca40e131bb30c2f8e5fd6fbd2615Chris Lattner std::vector<RenamePassData> &Worklist) { 10291e76af30116f4554fcf02c0f95705af1504b9645Chris LattnerNextIteration: 1030dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If we are inserting any phi nodes into this BB, they will already be in the 1031dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // block. 1032dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) { 1033dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // If we have PHI nodes to update, compute the number of edges from Pred to 1034dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // BB. 1035bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman if (PhiToAllocaMap.count(APN)) { 10362663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // We want to be able to distinguish between PHI nodes being inserted by 10372663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // this invocation of mem2reg from those phi nodes that already existed in 10382663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // the IR before mem2reg was run. We determine that APN is being inserted 10392663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // because it is missing incoming edges. All other PHI nodes being 10402663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // inserted by this pass of mem2reg will have the same number of incoming 10412663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // operands so far. Remember this count. 10422663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner unsigned NewPHINumOperands = APN->getNumOperands(); 10432663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner 1044dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned NumEdges = 0; 10456e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I) 10466e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky if (*I == BB) 1047dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++NumEdges; 1048dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner assert(NumEdges && "Must be at least one edge from Pred to BB!"); 1049dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1050dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Add entries for all the phis. 1051dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner BasicBlock::iterator PNI = BB->begin(); 1052dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner do { 1053dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner unsigned AllocaNo = PhiToAllocaMap[APN]; 1054dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1055dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Add N incoming values to the PHI node. 1056dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner for (unsigned i = 0; i != NumEdges; ++i) 1057dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner APN->addIncoming(IncomingVals[AllocaNo], Pred); 1058dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1059dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // The currently active variable for this block is now the PHI. 1060dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner IncomingVals[AllocaNo] = APN; 1061dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1062dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Get the next phi node. 1063dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner ++PNI; 1064dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner APN = dyn_cast<PHINode>(PNI); 1065dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (APN == 0) break; 1066dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 10672663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // Verify that it is missing entries. If not, it is not being inserted 10682663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner // by this mem2reg invocation so we want to ignore it. 10692663ffe7512ccd50ca246d5c8d9ee7a87b33883cChris Lattner } while (APN->getNumOperands() == NewPHINumOperands); 1070dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner } 10719157f041abcd0d3bf55dd09bfe85238b6626cf19Chris Lattner } 1072dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner 1073dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner // Don't revisit blocks. 1074dfb22c35215521e8ae9f27863b554949558bc4c1Chris Lattner if (!Visited.insert(BB)) return; 107598a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 1076521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 10770fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner Instruction *I = II++; // get the instruction, increment iterator 107898a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 10799f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 10801e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand()); 10811e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (!Src) continue; 10821e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 108359f5319719dd66570dc48d8415936a06c67672ffCameron Zwarich DenseMap<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 10841e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (AI == AllocaLookup.end()) continue; 108598a37c2b9c9c7f2791e0a8abda33b9a2eb36ad8eCameron Buschardt 10861e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner Value *V = IncomingVals[AI->second]; 10871e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 10881e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner // Anything using the load now uses the current value. 10891e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner LI->replaceAllUsesWith(V); 10901df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (AST && LI->getType()->isPointerTy()) 10911e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner AST->deleteValue(LI); 10921e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner BB->getInstList().erase(LI); 10939f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1094cc139de15a24d576fd98ef4599558016c86b64d6Chris Lattner // Delete this instruction and mark the name as the current holder of the 10959f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner // value 10961e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand()); 10971e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (!Dest) continue; 10981e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 109959f5319719dd66570dc48d8415936a06c67672ffCameron Zwarich DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 11001e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner if (ai == AllocaLookup.end()) 11011e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner continue; 11021e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner 11031e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner // what value were we writing? 11041e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner IncomingVals[ai->second] = SI->getOperand(0); 1105b9768b0731f8b9a10fd2ee6bd1699ae8c02fc78cVictor Hernandez // Record debuginfo for the store before removing it. 11065ee20680c7ebc765950983633e19fafab5235245Devang Patel if (DbgDeclareInst *DDI = AllocaDbgDeclares[ai->second]) { 11075ee20680c7ebc765950983633e19fafab5235245Devang Patel if (!DIB) 11085ee20680c7ebc765950983633e19fafab5235245Devang Patel DIB = new DIBuilder(*SI->getParent()->getParent()->getParent()); 11095ee20680c7ebc765950983633e19fafab5235245Devang Patel ConvertDebugDeclareToDebugValue(DDI, SI, *DIB); 11105ee20680c7ebc765950983633e19fafab5235245Devang Patel } 11111e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner BB->getInstList().erase(SI); 11129f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 11139f4eb01dd4cdf267f0b5aac40e78e262890b6aa5Chris Lattner } 1114521c16aadd56503320f61ec0a78ca7fda130ee8fChris Lattner 11151e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner // 'Recurse' to our successors. 11166e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky succ_iterator I = succ_begin(BB), E = succ_end(BB); 11176e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky if (I == E) return; 11186e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky 1119bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman // Keep track of the successors so we don't visit the same successor twice 1120bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman SmallPtrSet<BasicBlock*, 8> VisitedSuccs; 11216e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky 1122bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman // Handle the first successor without using the worklist. 1123bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman VisitedSuccs.insert(*I); 11241e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner Pred = BB; 11256e7aeb16faddb3c5648d0f5b6aaff37f1dcfb5dbNick Lewycky BB = *I; 1126bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman ++I; 1127bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman 1128bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman for (; I != E; ++I) 1129bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman if (VisitedSuccs.insert(*I)) 1130bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman Worklist.push_back(RenamePassData(*I, Pred, IncomingVals)); 1131bde6fda7292e23b2f5db77dc302338022558dcb8Eli Friedman 11321e76af30116f4554fcf02c0f95705af1504b9645Chris Lattner goto NextIteration; 1133d3db02248264b3ede56753cbb28df9d4ae45a1ddChris Lattner} 1134b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt 1135d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// PromoteMemToReg - Promote the specified list of alloca instructions into 1136b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich/// scalar registers, inserting PHI nodes as appropriate. This function does 1137b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich/// not modify the CFG of the function at all. All allocas must be from the 1138b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich/// same function. 1139d99bf49a53d170112c0241a4393ab374666b04bdChris Lattner/// 114062e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// If AST is specified, the specified tracker is updated to reflect changes 114162e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// made to the IR. 114262e29b59f50f573d0351f0cc6a5ba29ac59d8139Chris Lattner/// 1143f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnervoid llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 1144419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich DominatorTree &DT, AliasSetTracker *AST) { 11450fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner // If there is nothing to do, bail out... 11460fa157127f1e58d0acfa6fbd687617629e6ebf43Chris Lattner if (Allocas.empty()) return; 11476cfd1ebcd3d4c3b886b6b41b49806142ceb6275aChris Lattner 1148419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PromoteMem2Reg(Allocas, DT, AST).run(); 1149b1be061a76b47fe3f87596afb59674cc0c88a9b4Cameron Buschardt} 1150