Index: lib/Transforms/Utils/PromoteMemoryToRegister.cpp =================================================================== --- lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -65,102 +65,139 @@ bool llvm::isAllocaPromotable(const AllocaInst *AI) { // FIXME: If the memory unit is of pointer or integer type, we can permit // assignments to subsections of the memory unit. - unsigned AS = AI->getType()->getAddressSpace(); - - // Only allow direct and non-volatile loads and stores... - for (const User *U : AI->users()) { - if (const LoadInst *LI = dyn_cast(U)) { - // Note that atomic loads can be transformed; atomic semantics do - // not have any meaning for a local alloca. - if (LI->isVolatile()) - return false; - } else if (const StoreInst *SI = dyn_cast(U)) { - if (SI->getOperand(0) == AI) - return false; // Don't allow a store OF the AI, only INTO the AI. - // Note that atomic stores can be transformed; atomic semantics do - // not have any meaning for a local alloca. - if (SI->isVolatile()) - return false; - } else if (const IntrinsicInst *II = dyn_cast(U)) { - if (!II->isLifetimeStartOrEnd()) - return false; - } else if (const BitCastInst *BCI = dyn_cast(U)) { - if (BCI->getType() != Type::getInt8PtrTy(U->getContext(), AS)) - return false; - if (!onlyUsedByLifetimeMarkers(BCI)) - return false; - } else if (const GetElementPtrInst *GEPI = dyn_cast(U)) { - if (GEPI->getType() != Type::getInt8PtrTy(U->getContext(), AS)) - return false; - if (!GEPI->hasAllZeroIndices()) - return false; - if (!onlyUsedByLifetimeMarkers(GEPI)) + SmallVector Worklist({AI}); + while (!Worklist.empty()) { + const auto *I = Worklist.pop_back_val(); + for (const User *U : I->users()) { + if (const LoadInst *LI = dyn_cast(U)) { + // Note that atomic loads can be transformed; atomic semantics do + // not have any meaning for a local alloca. + if (LI->isVolatile()) + return false; + if (!CastInst::isBitCastable(AI->getAllocatedType(), LI->getType())) + return false; + } else if (const StoreInst *SI = dyn_cast(U)) { + if (SI->getOperand(0) == I) + return false; // Don't allow a store OF the AI, only INTO the AI. + // Note that atomic stores can be transformed; atomic semantics do + // not have any meaning for a local alloca. + if (SI->isVolatile()) + return false; + if (!CastInst::isBitCastable(AI->getAllocatedType(), + SI->getValueOperand()->getType())) + return false; + } else if (const IntrinsicInst *II = dyn_cast(U)) { + if (!II->isLifetimeStartOrEnd()) + return false; + } else if (const BitCastInst *BCI = dyn_cast(U)) { + Worklist.push_back(BCI); + } else if (const GetElementPtrInst *GEPI = + dyn_cast(U)) { + if (!GEPI->hasAllZeroIndices()) + return false; + Worklist.push_back(GEPI); + } else { return false; - } else { - return false; + } } } - return true; } namespace { +struct PromoteMem2Reg; + struct AllocaInfo { - SmallVector DefiningBlocks; - SmallVector UsingBlocks; + using DbgDeclaresVector = TinyPtrVector; - StoreInst *OnlyStore; - BasicBlock *OnlyBlock; - bool OnlyUsedInOneBlock; - - Value *AllocaPointerVal; - TinyPtrVector DbgDeclares; - - void clear() { - DefiningBlocks.clear(); - UsingBlocks.clear(); - OnlyStore = nullptr; - OnlyBlock = nullptr; - OnlyUsedInOneBlock = true; - AllocaPointerVal = nullptr; - DbgDeclares.clear(); - } +private: + /// Alloca instruction that is being promoted. + AllocaInst *AI = nullptr; - /// Scan the uses of the specified alloca, filling in the AllocaInfo used - /// by the rest of the pass to reason about the uses of this alloca. - void AnalyzeAlloca(AllocaInst *AI) { - clear(); - - // As we scan the uses of the alloca instruction, keep track of stores, - // and decide whether all of the loads and stores to the alloca are within - // the same basic block. - for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) { - Instruction *User = cast(*UI++); - - if (StoreInst *SI = dyn_cast(User)) { - // Remember the basic blocks which define new values for the alloca - DefiningBlocks.push_back(SI->getParent()); - AllocaPointerVal = SI->getOperand(0); - OnlyStore = SI; - } else { - LoadInst *LI = cast(User); - // Otherwise it must be a load instruction, keep track of variable - // reads. - UsingBlocks.push_back(LI->getParent()); - AllocaPointerVal = LI; - } + /// Pointer to the parent instance to access its DT, AC, DIB, LBI, etc. + PromoteMem2Reg *PM; + + /// Alloca's use/def chain partinioned into loads, stores and all other + /// instructions. + SmallPtrSet Loads; + SmallPtrSet Stores; + SmallPtrSet Other; + + /// Set of blocks there the Alloca's memory is defined (i.e. stored) and + /// used (loaded). + SmallPtrSet DefiningBlocks; + SmallPtrSet UsingBlocks; + + DbgDeclaresVector DbgDeclares; - if (OnlyUsedInOneBlock) { - if (!OnlyBlock) - OnlyBlock = User->getParent(); - else if (OnlyBlock != User->getParent()) - OnlyUsedInOneBlock = false; +public: + AllocaInfo(AllocaInst *AI, PromoteMem2Reg *PM) : AI(AI), PM(PM) { + assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!"); + // Partition alloca's use/def chain into loads, stores and all other uses. + SmallVector Worklist({AI}); + while (!Worklist.empty()) { + auto *I = Worklist.pop_back_val(); + for (auto *U : I->users()) { + if (auto *LI = dyn_cast(U)) { + Loads.insert(LI); + UsingBlocks.insert(LI->getParent()); + continue; + } + if (auto *SI = dyn_cast(U)) { + Stores.insert(SI); + DefiningBlocks.insert(SI->getParent()); + continue; + } + if (isa(U) || isa(U)) + Worklist.push_back(U); + Other.insert(cast(U)); } } - DbgDeclares = FindDbgAddrUses(AI); } + + operator AllocaInst *() const { return AI; } + AllocaInst *operator->() const { return AI; } + + /// Returns true if use/def chain for the alloca has no load and store + /// instructions. + bool emptyUsers() const { return Loads.empty() && Stores.empty(); } + + /// Getters for the Alloca's loads, stores and debug declarations. + const SmallPtrSetImpl &getLoads() const { return Loads; } + const SmallPtrSetImpl &getStores() const { return Stores; } + const DbgDeclaresVector &getDbgDeclares() const { return DbgDeclares; } + + /// Replaces uses of the load instruction from this use/def chain with the + /// given value. The value is bitcasted to the load's type if necessary. + void replaceLoadWith(LoadInst *LI, Value *V); + + /// Erases store instruction belonging to this use/def chain. + void eraseStore(StoreInst *SI); + + /// Erases alloca and its whole use/def chain. + void erase(); + + /// Special handling for the use/def chain with single store. In this case we + /// can use the domtree to trivially replace all of the dominated loads with + /// the stored value. Returns true if the entire alloca use/def chain was + /// successfully promoted. Otherwise false is returned and the standard alloca + /// promotion algorithm is supposed to be used. + bool rewriteSingleStoreAlloca(); + + /// Special handling for the use/def chain with all loads and stores in one + /// basic block. In this case we can avoid traversing the CFG and inserting a + /// lot of potentially useless PHI nodes by just performing a single linear + /// pass over the use/def basic block. Returns true if the entire use/def + /// chain was successfully promoted. Otherwise false is returned and the + /// standard alloca promotion algorithm is supposed to be used. + bool promoteSingleBlockAlloca(); + + /// Builds a set of defining and live-in blocks for the alloca's use/def + /// chain. + void ComputeDefAndLiveInBlocks(SmallPtrSetImpl &DefBlocks, + SmallPtrSetImpl &LiveInBlocks); }; /// Data package used by RenamePass(). @@ -178,7 +215,7 @@ }; /// This assigns and keeps a per-bb relative ordering of load/store -/// instructions in the block that directly load or store an alloca. +/// instructions in the block that load or store from/to an alloca. /// /// This functionality is important because it avoids scanning large basic /// blocks multiple times when promoting many allocas in the same block. @@ -191,16 +228,16 @@ DenseMap InstNumbers; public: - /// This code only looks at accesses to allocas. - static bool isInterestingInstruction(const Instruction *I) { - return (isa(I) && isa(I->getOperand(0))) || - (isa(I) && isa(I->getOperand(1))); + static bool isInterestingInstruction(const Instruction *I, + const AllocaInfo &AI) { + return (isa(I) && AI.getLoads().count(cast(I))) || + (isa(I) && AI.getStores().count(cast(I))); } /// Get or calculate the index of the specified instruction. - unsigned getInstructionIndex(const Instruction *I) { - assert(isInterestingInstruction(I) && + unsigned getInstructionIndex(const Instruction *I, const AllocaInfo &AI) { + assert(isInterestingInstruction(I, AI) && "Not a load/store to/from an alloca?"); // If we already have this instruction number, return it. @@ -214,7 +251,7 @@ const BasicBlock *BB = I->getParent(); unsigned InstNo = 0; for (const Instruction &BBI : *BB) - if (isInterestingInstruction(&BBI)) + if (isInterestingInstruction(&BBI, AI)) InstNumbers[&BBI] = InstNo++; It = InstNumbers.find(I); @@ -229,7 +266,7 @@ struct PromoteMem2Reg { /// The alloca instructions being promoted. - std::vector Allocas; + SmallVector Allocas; DominatorTree &DT; DIBuilder DIB; @@ -239,8 +276,11 @@ const SimplifyQuery SQ; - /// Reverse mapping of Allocas. - DenseMap AllocaLookup; + LargeBlockInfo LBI; + + /// Reverse mapping of Allocas loads and stores. + DenseMap LoadLookup; + DenseMap StoreLookup; /// The PhiNodes we're adding. /// @@ -254,16 +294,6 @@ /// to. DenseMap PhiToAllocaMap; - /// If we are updating an AliasSetTracker, then for each alloca that is of - /// pointer type, we keep track of what to copyValue to the inserted PHI - /// nodes here. - std::vector PointerAllocaValues; - - /// For each alloca, we keep track of the dbg.declare intrinsic that - /// describes it, if any, so that we can convert it to a dbg.value - /// intrinsic if the alloca gets promoted. - SmallVector, 8> AllocaDbgDeclares; - /// The set of basic blocks the renamer has already visited. SmallPtrSet Visited; @@ -275,18 +305,22 @@ DenseMap BBNumPreds; public: - PromoteMem2Reg(ArrayRef Allocas, DominatorTree &DT, + PromoteMem2Reg(ArrayRef AllocaInsts, DominatorTree &DT, AssumptionCache *AC) - : Allocas(Allocas.begin(), Allocas.end()), DT(DT), - DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false), + : DT(DT), DIB(*DT.getRoot()->getModule(), /*AllowUnresolved*/ false), AC(AC), SQ(DT.getRoot()->getParent()->getParent()->getDataLayout(), - nullptr, &DT, AC) {} + nullptr, &DT, AC) { + Allocas.reserve(AllocaInsts.size()); + for (auto *I : AllocaInsts) + Allocas.emplace_back(I, this); + } void run(); private: void RemoveFromAllocasList(unsigned &AllocaIdx) { - Allocas[AllocaIdx] = Allocas.back(); + Allocas[AllocaIdx].erase(); + Allocas[AllocaIdx] = std::move(Allocas.back()); Allocas.pop_back(); --AllocaIdx; } @@ -298,9 +332,6 @@ return NP - 1; } - void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, - const SmallPtrSetImpl &DefBlocks, - SmallPtrSetImpl &LiveInBlocks); void RenamePass(BasicBlock *BB, BasicBlock *Pred, RenamePassData::ValVector &IncVals, RenamePassData::LocationVector &IncLocs, @@ -322,28 +353,76 @@ AC->registerAssumption(CI); } -static void removeLifetimeIntrinsicUsers(AllocaInst *AI) { - // Knowing that this alloca is promotable, we know that it's safe to kill all - // instructions except for load and store. - - for (auto UI = AI->user_begin(), UE = AI->user_end(); UI != UE;) { - Instruction *I = cast(*UI); - ++UI; - if (isa(I) || isa(I)) - continue; - - if (!I->getType()->isVoidTy()) { - // The only users of this bitcast/GEP instruction are lifetime intrinsics. - // Follow the use/def chain to erase them now instead of leaving it for - // dead code elimination later. - for (auto UUI = I->user_begin(), UUE = I->user_end(); UUI != UUE;) { - Instruction *Inst = cast(*UUI); - ++UUI; - Inst->eraseFromParent(); - } - } +/// Optionally insert bitcast instruction for value V to type Ty which is +/// inserted before InsPt if V's type differs from Ty. +static Value* bitcastValue(Value *V, Type *Ty, Instruction *InsPt) { + if (V->getType() != Ty) { + if (isa(V)) + V = UndefValue::get(Ty); + else + V = new BitCastInst(V, Ty, "", InsPt); + } + return V; +} + +void AllocaInfo::replaceLoadWith(LoadInst *LI, Value *V) { + // If the load was marked as nonnull we don't want to lose + // that information when we erase this Load. So we preserve + // it with an assume. + if (PM->AC && LI->getMetadata(LLVMContext::MD_nonnull) && + !isKnownNonZero(V, PM->SQ.DL, 0, PM->AC, LI, &PM->DT)) + addAssumeNonNull(PM->AC, LI); + + // If the replacement value is the load, this must occur in unreachable code. + if (V == LI) + V = UndefValue::get(LI->getType()); + V = bitcastValue(V, LI->getType(), LI); + LI->replaceAllUsesWith(V); + + PM->LBI.deleteValue(LI); + Loads.erase(LI); + LI->eraseFromParent(); +} + +void AllocaInfo::eraseStore(StoreInst *SI) { + for (auto *DII : DbgDeclares) + ConvertDebugDeclareToDebugValue(DII, SI, PM->DIB); + PM->LBI.deleteValue(SI); + Stores.erase(SI); + SI->eraseFromParent(); +} + +void AllocaInfo::erase() { + auto && eraseInst = [](Instruction *I, LargeBlockInfo *LBI) { + if (LBI) + LBI->deleteValue(I); + if (!I->user_empty()) + I->replaceAllUsesWith(UndefValue::get(I->getType())); I->eraseFromParent(); + }; + + for (auto *I : Stores) { + // Record debuginfo for the store before removing it. + for (auto *DII : DbgDeclares) + ConvertDebugDeclareToDebugValue(DII, I, PM->DIB); + eraseInst(I, &PM->LBI); + } + Stores.clear(); + + for (auto *I : Loads) + eraseInst(I, &PM->LBI); + Loads.clear(); + + for (auto *I : Other) + eraseInst(I, nullptr); + Other.clear(); + + // The alloca's debuginfo can be removed as well. + for (DbgVariableIntrinsic *DII : DbgDeclares) { + PM->LBI.deleteValue(DII); + DII->eraseFromParent(); } + eraseInst(AI, nullptr); } /// Rewrite as many loads as possible given a single store. @@ -354,24 +433,19 @@ /// false there were some loads which were not dominated by the single store /// and thus must be phi-ed with undef. We fall back to the standard alloca /// promotion algorithm in that case. -static bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, - LargeBlockInfo &LBI, const DataLayout &DL, - DominatorTree &DT, AssumptionCache *AC) { - StoreInst *OnlyStore = Info.OnlyStore; +bool AllocaInfo::rewriteSingleStoreAlloca() { + if (Stores.size() != 1u) + return false; + StoreInst *OnlyStore = *Stores.begin(); bool StoringGlobalVal = !isa(OnlyStore->getOperand(0)); BasicBlock *StoreBB = OnlyStore->getParent(); int StoreIndex = -1; // Clear out UsingBlocks. We will reconstruct it here if needed. - Info.UsingBlocks.clear(); + UsingBlocks.clear(); - for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) { - Instruction *UserInst = cast(*UI++); - if (!isa(UserInst)) { - assert(UserInst == OnlyStore && "Should only have load/stores"); - continue; - } - LoadInst *LI = cast(UserInst); + for (auto UI = Loads.begin(), E = Loads.end(); UI != E;) { + LoadInst *LI = *UI++; // Okay, if we have a load from the alloca, we want to replace it with the // only value stored to the alloca. We can do this if the value is @@ -383,61 +457,29 @@ // indices of the two instructions to see which one came first. If the // load came before the store, we can't handle it. if (StoreIndex == -1) - StoreIndex = LBI.getInstructionIndex(OnlyStore); + StoreIndex = PM->LBI.getInstructionIndex(OnlyStore, *this); - if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) { + if (unsigned(StoreIndex) > PM->LBI.getInstructionIndex(LI, *this)) { // Can't handle this load, bail out. - Info.UsingBlocks.push_back(StoreBB); + UsingBlocks.insert(StoreBB); continue; } - } else if (LI->getParent() != StoreBB && - !DT.dominates(StoreBB, LI->getParent())) { + } else if (!PM->DT.dominates(StoreBB, LI->getParent())) { // If the load and store are in different blocks, use BB dominance to // check their relationships. If the store doesn't dom the use, bail // out. - Info.UsingBlocks.push_back(LI->getParent()); + UsingBlocks.insert(LI->getParent()); continue; } } // Otherwise, we *can* safely rewrite this load. - Value *ReplVal = OnlyStore->getOperand(0); - // If the replacement value is the load, this must occur in unreachable - // code. - if (ReplVal == LI) - ReplVal = UndefValue::get(LI->getType()); - - // If the load was marked as nonnull we don't want to lose - // that information when we erase this Load. So we preserve - // it with an assume. - if (AC && LI->getMetadata(LLVMContext::MD_nonnull) && - !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT)) - addAssumeNonNull(AC, LI); - - LI->replaceAllUsesWith(ReplVal); - LI->eraseFromParent(); - LBI.deleteValue(LI); + replaceLoadWith(LI, OnlyStore->getOperand(0)); } // Finally, after the scan, check to see if the store is all that is left. - if (!Info.UsingBlocks.empty()) - return false; // If not, we'll have to fall back for the remainder. - - // Record debuginfo for the store and remove the declaration's - // debuginfo. - for (DbgVariableIntrinsic *DII : Info.DbgDeclares) { - DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false); - ConvertDebugDeclareToDebugValue(DII, Info.OnlyStore, DIB); - DII->eraseFromParent(); - LBI.deleteValue(DII); - } - // Remove the (now dead) store and alloca. - Info.OnlyStore->eraseFromParent(); - LBI.deleteValue(Info.OnlyStore); - - AI->eraseFromParent(); - LBI.deleteValue(AI); - return true; + // If not, we'll have to fall back for the remainder. + return UsingBlocks.empty(); } /// Many allocas are only used within a single basic block. If this is the @@ -456,11 +498,11 @@ /// use(t); /// *A = 42; /// } -static bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info, - LargeBlockInfo &LBI, - const DataLayout &DL, - DominatorTree &DT, - AssumptionCache *AC) { +bool AllocaInfo::promoteSingleBlockAlloca() { + if (DefiningBlocks.size() != 1u || UsingBlocks.size() != 1u || + *DefiningBlocks.begin() != *UsingBlocks.begin()) + return false; + // The trickiest case to handle is when we have large blocks. Because of this, // this code is optimized assuming that large blocks happen. This does not // significantly pessimize the small block case. This uses LargeBlockInfo to @@ -470,22 +512,22 @@ using StoresByIndexTy = SmallVector, 64>; StoresByIndexTy StoresByIndex; - for (User *U : AI->users()) - if (StoreInst *SI = dyn_cast(U)) - StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI)); + for (auto *SI : Stores) + StoresByIndex.push_back( + std::make_pair(PM->LBI.getInstructionIndex(SI, *this), SI)); // Sort the stores by their index, making it efficient to do a lookup with a // binary search. llvm::sort(StoresByIndex, less_first()); + // Clear out UsingBlocks. We will reconstruct it here if needed. + UsingBlocks.clear(); + // Walk all of the loads from this alloca, replacing them with the nearest // store above them, if any. - for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) { - LoadInst *LI = dyn_cast(*UI++); - if (!LI) - continue; - - unsigned LoadIdx = LBI.getInstructionIndex(LI); + for (auto UI = Loads.begin(), E = Loads.end(); UI != E;) { + LoadInst *LI = *UI++; + unsigned LoadIdx = PM->LBI.getInstructionIndex(LI, *this); // Find the nearest store that has a lower index than this load. StoresByIndexTy::iterator I = @@ -494,108 +536,51 @@ static_cast(nullptr)), less_first()); if (I == StoresByIndex.begin()) { - if (StoresByIndex.empty()) - // If there are no stores, the load takes the undef value. - LI->replaceAllUsesWith(UndefValue::get(LI->getType())); - else - // There is no store before this load, bail out (load may be affected - // by the following stores - see main comment). - return false; - } else { - // Otherwise, there was a store before this load, the load takes its value. - // Note, if the load was marked as nonnull we don't want to lose that - // information when we erase it. So we preserve it with an assume. - Value *ReplVal = std::prev(I)->second->getOperand(0); - if (AC && LI->getMetadata(LLVMContext::MD_nonnull) && - !isKnownNonZero(ReplVal, DL, 0, AC, LI, &DT)) - addAssumeNonNull(AC, LI); - - // If the replacement value is the load, this must occur in unreachable - // code. - if (ReplVal == LI) - ReplVal = UndefValue::get(LI->getType()); - - LI->replaceAllUsesWith(ReplVal); + // There is no store before this load, bail out (load may be affected + // by the following stores - see main comment). + UsingBlocks.insert(LI->getParent()); + continue; } - LI->eraseFromParent(); - LBI.deleteValue(LI); - } - - // Remove the (now dead) stores and alloca. - while (!AI->use_empty()) { - StoreInst *SI = cast(AI->user_back()); - // Record debuginfo for the store before removing it. - for (DbgVariableIntrinsic *DII : Info.DbgDeclares) { - DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false); - ConvertDebugDeclareToDebugValue(DII, SI, DIB); - } - SI->eraseFromParent(); - LBI.deleteValue(SI); + // Otherwise, there was a store before this load, the load takes its value. + replaceLoadWith(LI, std::prev(I)->second->getOperand(0)); } - - AI->eraseFromParent(); - LBI.deleteValue(AI); - - // The alloca's debuginfo can be removed as well. - for (DbgVariableIntrinsic *DII : Info.DbgDeclares) { - DII->eraseFromParent(); - LBI.deleteValue(DII); - } - - ++NumLocalPromoted; - return true; + return UsingBlocks.empty(); } void PromoteMem2Reg::run() { Function &F = *DT.getRoot()->getParent(); - AllocaDbgDeclares.resize(Allocas.size()); - - AllocaInfo Info; - LargeBlockInfo LBI; ForwardIDFCalculator IDF(DT); for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { - AllocaInst *AI = Allocas[AllocaNum]; + AllocaInfo &AI = Allocas[AllocaNum]; - assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!"); assert(AI->getParent()->getParent() == &F && "All allocas should be in the same function, which is same as DF!"); - removeLifetimeIntrinsicUsers(AI); - - if (AI->use_empty()) { - // If there are no uses of the alloca, just delete it now. - AI->eraseFromParent(); - + if (AI.emptyUsers()) { // Remove the alloca from the Allocas list, since it has been processed RemoveFromAllocasList(AllocaNum); ++NumDeadAlloca; continue; } - // Calculate the set of read and write-locations for each alloca. This is - // analogous to finding the 'uses' and 'definitions' of each variable. - Info.AnalyzeAlloca(AI); - // If there is only a single store to this value, replace any loads of // it that are directly dominated by the definition with the value stored. - if (Info.DefiningBlocks.size() == 1) { - if (rewriteSingleStoreAlloca(AI, Info, LBI, SQ.DL, DT, AC)) { - // The alloca has been processed, move on. - RemoveFromAllocasList(AllocaNum); - ++NumSingleStore; - continue; - } + if (AI.rewriteSingleStoreAlloca()) { + // The alloca has been processed, move on. + RemoveFromAllocasList(AllocaNum); + ++NumSingleStore; + continue; } // If the alloca is only read and written in one basic block, just perform a // linear sweep over the block to eliminate it. - if (Info.OnlyUsedInOneBlock && - promoteSingleBlockAlloca(AI, Info, LBI, SQ.DL, DT, AC)) { + if (AI.promoteSingleBlockAlloca()) { // The alloca has been processed, move on. RemoveFromAllocasList(AllocaNum); + ++NumLocalPromoted; continue; } @@ -607,12 +592,11 @@ BBNumbers[&BB] = ID++; } - // Remember the dbg.declare intrinsic describing this alloca, if any. - if (!Info.DbgDeclares.empty()) - AllocaDbgDeclares[AllocaNum] = Info.DbgDeclares; - // Keep the reverse mapping of the 'Allocas' array for the rename pass. - AllocaLookup[Allocas[AllocaNum]] = AllocaNum; + for (auto *LI : AI.getLoads()) + LoadLookup[LI] = AllocaNum; + for (auto *SI : AI.getStores()) + StoreLookup[SI] = AllocaNum; // At this point, we're committed to promoting the alloca using IDF's, and // the standard SSA construction algorithm. Determine which blocks need PHI @@ -621,12 +605,11 @@ // Unique the set of defining blocks for efficient lookup. SmallPtrSet DefBlocks; - DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); // Determine which blocks the value is live in. These are blocks which lead // to uses. SmallPtrSet LiveInBlocks; - ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); + AI.ComputeDefAndLiveInBlocks(DefBlocks, LiveInBlocks); // At this point, we're committed to promoting the alloca using IDF's, and // the standard SSA construction algorithm. Determine which blocks need phi @@ -678,19 +661,8 @@ Visited.clear(); // Remove the allocas themselves from the function. - for (Instruction *A : Allocas) { - // If there are any uses of the alloca instructions left, they must be in - // unreachable basic blocks that were not processed by walking the dominator - // tree. Just delete the users now. - if (!A->use_empty()) - A->replaceAllUsesWith(UndefValue::get(A->getType())); - A->eraseFromParent(); - } - - // Remove alloca's dbg.declare instrinsics from the function. - for (auto &Declares : AllocaDbgDeclares) - for (auto *DII : Declares) - DII->eraseFromParent(); + for (auto &AI : Allocas) + AI.erase(); // Loop over all of the PHI nodes and see if there are any that we can get // rid of because they merge all of the same incoming values. This can @@ -791,15 +763,17 @@ /// These are blocks which lead to uses. Knowing this allows us to avoid /// inserting PHI nodes into blocks which don't lead to uses (thus, the /// inserted phi nodes would be dead). -void PromoteMem2Reg::ComputeLiveInBlocks( - AllocaInst *AI, AllocaInfo &Info, - const SmallPtrSetImpl &DefBlocks, +void AllocaInfo::ComputeDefAndLiveInBlocks( + SmallPtrSetImpl &DefBlocks, SmallPtrSetImpl &LiveInBlocks) { + + DefBlocks.insert(DefiningBlocks.begin(), DefiningBlocks.end()); + // To determine liveness, we must iterate through the predecessors of blocks // where the def is live. Blocks are added to the worklist if we need to // check their predecessors. Start with all the using blocks. - SmallVector LiveInBlockWorklist(Info.UsingBlocks.begin(), - Info.UsingBlocks.end()); + SmallVector LiveInBlockWorklist(UsingBlocks.begin(), + UsingBlocks.end()); // If any of the using blocks is also a definition block, check to see if the // definition occurs before or after the use. If it happens before the use, @@ -813,7 +787,7 @@ // reference to the alloca is a def (store), then we know it isn't live-in. for (BasicBlock::iterator I = BB->begin();; ++I) { if (StoreInst *SI = dyn_cast(I)) { - if (SI->getOperand(1) != AI) + if (!Stores.count(SI)) continue; // We found a store to the alloca before a load. The alloca is not @@ -826,7 +800,7 @@ } if (LoadInst *LI = dyn_cast(I)) { - if (LI->getOperand(0) != AI) + if (!Loads.count(LI)) continue; // Okay, we found a load before a store to the alloca. It is actually @@ -934,7 +908,7 @@ // The currently active variable for this block is now the PHI. IncomingVals[AllocaNo] = APN; - for (DbgVariableIntrinsic *DII : AllocaDbgDeclares[AllocaNo]) + for (DbgVariableIntrinsic *DII : Allocas[AllocaNo].getDbgDeclares()) ConvertDebugDeclareToDebugValue(DII, APN, DIB); // Get the next phi node. @@ -957,46 +931,28 @@ Instruction *I = &*II++; // get the instruction, increment iterator if (LoadInst *LI = dyn_cast(I)) { - AllocaInst *Src = dyn_cast(LI->getPointerOperand()); - if (!Src) + auto It = LoadLookup.find(LI); + if (It == LoadLookup.end()) continue; - DenseMap::iterator AI = AllocaLookup.find(Src); - if (AI == AllocaLookup.end()) - continue; - - Value *V = IncomingVals[AI->second]; - - // If the load was marked as nonnull we don't want to lose - // that information when we erase this Load. So we preserve - // it with an assume. - if (AC && LI->getMetadata(LLVMContext::MD_nonnull) && - !isKnownNonZero(V, SQ.DL, 0, AC, LI, &DT)) - addAssumeNonNull(AC, LI); + unsigned AllocaNo = It->second; + Value *V = IncomingVals[AllocaNo]; // Anything using the load now uses the current value. - LI->replaceAllUsesWith(V); - BB->getInstList().erase(LI); + Allocas[AllocaNo].replaceLoadWith(LI, V); } else if (StoreInst *SI = dyn_cast(I)) { - // Delete this instruction and mark the name as the current holder of the - // value - AllocaInst *Dest = dyn_cast(SI->getPointerOperand()); - if (!Dest) - continue; - - DenseMap::iterator ai = AllocaLookup.find(Dest); - if (ai == AllocaLookup.end()) + auto It = StoreLookup.find(SI); + if (It == StoreLookup.end()) continue; // what value were we writing? - unsigned AllocaNo = ai->second; - IncomingVals[AllocaNo] = SI->getOperand(0); + unsigned AllocaNo = It->second; + IncomingVals[AllocaNo] = bitcastValue(SI->getOperand(0), + Allocas[AllocaNo]->getAllocatedType(), SI); // Record debuginfo for the store before removing it. IncomingLocs[AllocaNo] = SI->getDebugLoc(); - for (DbgVariableIntrinsic *DII : AllocaDbgDeclares[ai->second]) - ConvertDebugDeclareToDebugValue(DII, SI, DIB); - BB->getInstList().erase(SI); + Allocas[AllocaNo].eraseStore(SI); } } Index: test/Transforms/Mem2Reg/bitcast.ll =================================================================== --- test/Transforms/Mem2Reg/bitcast.ll +++ test/Transforms/Mem2Reg/bitcast.ll @@ -0,0 +1,44 @@ +; RUN: opt -mem2reg -S -o - %s | FileCheck %s + +declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) +declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) + +define float @test1(float* %p) { +; CHECK: test1 +; CHECK-NOT: alloca +entry: + %f = alloca float, align 4 + %f.gep = getelementptr inbounds float, float* %f, i64 0 + %f.lts = bitcast float* %f.gep to i8* + call void @llvm.lifetime.start.p0i8(i64 4, i8* %f.lts) + %p.i32 = bitcast float* %p to i32* + %p.val = load i32, i32* %p.i32, align 4 + %f.i32 = bitcast float* %f.gep to i32* + store i32 %p.val, i32* %f.i32, align 4 + %f.val = load float, float* %f.gep, align 4 + %f.lte = bitcast float* %f.gep to i8* + call void @llvm.lifetime.end.p0i8(i64 4, i8* %f.lte) + ret float %f.val +} + +define float @test2(float* %p, i32 %c) { +; CHECK: test2 +; CHECK-NOT: alloca +entry: + %f = alloca float, align 4 + %f.gep = getelementptr inbounds float, float* %f, i64 0 + store float 1.000000e+00, float* %f.gep, align 4 + %c.nz = icmp ne i32 %c, 0 + br i1 %c.nz, label %if.then, label %if.end + +if.then: + %p.i32 = bitcast float* %p to i32* + %p.val = load i32, i32* %p.i32, align 4 + %f.i32 = bitcast float* %f.gep to i32* + store i32 %p.val, i32* %f.i32, align 4 + br label %if.end + +if.end: + %f.val = load float, float* %f.gep, align 4 + ret float %f.val +}