Index: include/llvm/Analysis/MemorySSA.h =================================================================== --- include/llvm/Analysis/MemorySSA.h +++ include/llvm/Analysis/MemorySSA.h @@ -781,7 +781,7 @@ // relies on the updater to fixup what it breaks, so it is not public. void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where); - void moveTo(MemoryUseOrDef *What, BasicBlock *BB, InsertionPlace Point); + void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point); // Rename the dominator tree branch rooted at BB. void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, @@ -795,7 +795,8 @@ InsertionPlace); void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator); - MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); + MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *, + const MemoryUseOrDef *Template = nullptr); private: class CachingWalker; @@ -815,7 +816,8 @@ void markUnreachableAsLiveOnEntry(BasicBlock *BB); bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const; MemoryPhi *createMemoryPhi(BasicBlock *BB); - MemoryUseOrDef *createNewAccess(Instruction *); + MemoryUseOrDef *createNewAccess(Instruction *, + const MemoryUseOrDef *Template = nullptr); MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); void placePHINodes(const SmallPtrSetImpl &); MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool); Index: include/llvm/Analysis/MemorySSAUpdater.h =================================================================== --- include/llvm/Analysis/MemorySSAUpdater.h +++ include/llvm/Analysis/MemorySSAUpdater.h @@ -35,6 +35,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Dominators.h" @@ -45,6 +46,7 @@ #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" +#include "llvm/IR/ValueMap.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/ErrorHandling.h" @@ -57,6 +59,9 @@ class LLVMContext; class raw_ostream; +using ValueToValueMapTy = ValueMap; +using PhiToDefMap = SmallDenseMap; + class MemorySSAUpdater { private: MemorySSA *MSSA; @@ -66,6 +71,29 @@ public: MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} + + // Data structure modelling an new edge inserted in the cfg. + struct CFGEdgeUpdate { + BasicBlock *From; + BasicBlock *To; + + CFGEdgeUpdate(BasicBlock *From, BasicBlock *To) : From(From), To(To) {} + + BasicBlock *getFrom() const { return From; } + BasicBlock *getTo() const { return To; } + bool operator==(const CFGEdgeUpdate &RHS) const { + return From == RHS.From && To == RHS.To; + } + + friend raw_ostream &operator<<(raw_ostream &OS, const CFGEdgeUpdate &U) { + OS << "Insert "; + U.getFrom()->printAsOperand(OS, false); + OS << " -> "; + U.getTo()->printAsOperand(OS, false); + return OS; + } + }; + /// Insert a definition into the MemorySSA IR. RenameUses will rename any use /// below the new def block (and any inserted phis). RenameUses should be set /// to true if the definition may cause new aliases for loads below it. This @@ -85,11 +113,92 @@ /// Where a mayalias b, *does* require RenameUses be set to true. void insertDef(MemoryDef *Def, bool RenameUses = false); void insertUse(MemoryUse *Use); + /// Update the MemoryPhi in To following an edge deletion between `From` and + /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made. + void removeEdge(BasicBlock *From, BasicBlock *To); + /// Update MemorySSA after a loop was cloned, given the blocks in RPO order, + /// the exit blocks and a 1:1 mapping of all blocks and instructions + /// cloned. This involves duplicating all defs and uses in the cloned blocks + /// Updating phi nodes in exit block successors is done separately. + void updateForClonedLoop(LoopBlocksRPO &LoopBlocks, + ArrayRef ExitBlocks, + ValueToValueMapTy &VM, + bool IgnoreIncomingWithNoClones = false); + // Block BB was fully or partially cloned into its predecessor P1. Map + // contains the 1:1 mapping of instructions cloned and VM[BB]=P1. + void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, + ValueToValueMapTy &VM); + /// Update phi nodes in exit block successors following cloning. + void updateExitBlocksForClonedLoop(ArrayRef ExitBlocks, + ValueToValueMapTy &VMap, + DominatorTree *DT); + void updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, + SmallVectorImpl> &VMaps, + DominatorTree *DT); + /// Due to block cloning or block splitting, BB was added an additional + /// predecessor P_Added beside the previously known single predecessor + /// P_Known. Insert and update Phi nodes, and uses that areno longer + /// dominated, in order to make MemorySSA valid again. + void + updatePhisWhenAddingBBPredecessors(ArrayRef, + DominatorTree *DT); + /// `Header` may have a MemoryPhi with uses it no longer dominates. Replace + /// those uses with the MemoryPhi's incoming value from `NewPreheader`. + void updateHeaderPhisUsesAfterLoopUnswitch(BasicBlock *Header, + BasicBlock *NewPreheader, + DominatorTree *DT); + /// `To` is a newly unswitched block with two predecessors: `From` and + /// `NewIncoming. Add a new MemoryPhi node into `To` for the two + /// predecessors. Incoming value from `From` is the last def, at least a Phi + /// node: MPhi exists. Incoming from `NewIncoming` is MPhi's incoming value + /// from OldIncoming. For a full unswitch, also remove the incoming value + /// into MPhi from OldIncoming, which possibly deletes MPhi. + void wireOldPhiIntoNewPhiAfterUnswitch(BasicBlock *From, BasicBlock *To, + BasicBlock *OldIncoming, + BasicBlock *NewIncoming, + bool FullUnswitch); void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where); - + /// `From` block was spliced into `From` and `To`. + /// Move all accesses from `From` to `To` starting at instruction `Start`. + /// `To` is newly created BB, so empty of MemorySSA::MemoryAccesses. + /// Edges are already updated, so successors of `To` with MPhi nodes need to + /// update incoming block. + /// |------| |------| + /// | From | | From | + /// | | |------| + /// | | || + /// | | => \/ + /// | | |------| <- Start + /// | | | To | + /// |------| |------| + void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, + Instruction *Start); + /// `From` block was merged into `To`. All instructiones were moved and + /// `From` is an empty block with successor edges; `From` is about to be + /// deleted. Move all accesses from `From` to `To` starting at instruction + /// `Start`. `To` may have multiple successors, `From` has a single + /// predecessor. `From` may have successors with MPhi nodes, replace their + /// incoming block with `To`. + /// |------| |------| + /// | To | | To | + /// |------| | | + /// || => | | + /// \/ | | + /// |------| | | <- Start + /// | From | | | + /// |------| |------| + void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, + Instruction *Start); + /// `ToReplace` used to be a predecessor of BB. `ReplaceWith` is the new + /// predecessor. Update Phi in BB to replace incoming block `ToReplace` with + /// `ReplaceWith`. + void replacePhiIncomingBlock(BasicBlock *BB, BasicBlock *ToReplace, + BasicBlock *ReplaceWith); + void movePhiToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New); // The below are utility functions. Other than creation of accesses to pass // to insertDef, and removeAccess to remove accesses, you should generally // not attempt to update memoryssa yourself. It is very non-trivial to get @@ -162,6 +271,10 @@ // Move What before Where in the MemorySSA IR. template void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); + // Move all memory accesses from `From` to `To` starting at `Start`. + // Restrictions apply, see public wrappers of this method. + void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start, + MemorySSA::InsertionPlace Where); MemoryAccess *getPreviousDef(MemoryAccess *); MemoryAccess *getPreviousDefInBlock(MemoryAccess *); MemoryAccess * @@ -174,6 +287,15 @@ template MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); void fixupDefs(const SmallVectorImpl &); + // Clone all uses and defs from BB to NewBB given a 1:1 map of all + // instructions and blocks cloned, and a map of MemoryPhi : Definition + // (MemoryAccess Phi or Def). + void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB, + ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap); + // A CFG change caused uses of ToReplace to no longer be dominated by it. + // Replace those uses with ReplaceWith. + void replaceDefToFixDomination(MemoryAccess *ToReplace, + MemoryAccess *ReplaceWith, DominatorTree *DT); }; } // end namespace llvm Index: lib/Analysis/MemorySSA.cpp =================================================================== --- lib/Analysis/MemorySSA.cpp +++ lib/Analysis/MemorySSA.cpp @@ -1473,8 +1473,15 @@ insertIntoListsBefore(What, BB, Where); } -void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB, +void MemorySSA::moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point) { + if (isa(What)) { + assert(Point == Beginning && + "Can only move a Phi at the beginning of the block"); + // Update lookup table entry + ValueToMemoryAccess.erase(What->getBlock()); + ValueToMemoryAccess[BB] = What; + } removeFromLists(What, false); What->setBlock(BB); insertIntoListsForBlock(What, BB, Point); @@ -1490,9 +1497,10 @@ } MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I, - MemoryAccess *Definition) { + MemoryAccess *Definition, + const MemoryUseOrDef *Template) { assert(!isa(I) && "Cannot create a defined access for a PHI"); - MemoryUseOrDef *NewAccess = createNewAccess(I); + MemoryUseOrDef *NewAccess = createNewAccess(I, Template); assert( NewAccess != nullptr && "Tried to create a memory access for a non-memory touching instruction"); @@ -1515,7 +1523,8 @@ } /// Helper function to create new memory accesses -MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) { +MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I, + const MemoryUseOrDef *Template) { // The assume intrinsic has a control dependency which we model by claiming // that it writes arbitrarily. Ignore that fake memory dependency here. // FIXME: Replace this special casing with a more accurate modelling of @@ -1524,18 +1533,32 @@ if (II->getIntrinsicID() == Intrinsic::assume) return nullptr; - // Find out what affect this instruction has on memory. - ModRefInfo ModRef = AA->getModRefInfo(I, None); - // The isOrdered check is used to ensure that volatiles end up as defs - // (atomics end up as ModRef right now anyway). Until we separate the - // ordering chain from the memory chain, this enables people to see at least - // some relative ordering to volatiles. Note that getClobberingMemoryAccess - // will still give an answer that bypasses other volatile loads. TODO: - // Separate memory aliasing and ordering into two different chains so that we - // can precisely represent both "what memory will this read/write/is clobbered - // by" and "what instructions can I move this past". - bool Def = isModSet(ModRef) || isOrdered(I); - bool Use = isRefSet(ModRef); + bool Def, Use; + if (Template) { + Def = dyn_cast_or_null(Template) != nullptr; + Use = dyn_cast_or_null(Template) != nullptr; +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + ModRefInfo ModRef = AA->getModRefInfo(I, None); + bool DefCheck, UseCheck; + DefCheck = isModSet(ModRef) || isOrdered(I); + UseCheck = isRefSet(ModRef); + assert(Def == DefCheck && (Def == true || Use == UseCheck) && + "Invalid template"); +#endif + } else { + // Find out what affect this instruction has on memory. + ModRefInfo ModRef = AA->getModRefInfo(I, None); + // The isOrdered check is used to ensure that volatiles end up as defs + // (atomics end up as ModRef right now anyway). Until we separate the + // ordering chain from the memory chain, this enables people to see at least + // some relative ordering to volatiles. Note that getClobberingMemoryAccess + // will still give an answer that bypasses other volatile loads. TODO: + // Separate memory aliasing and ordering into two different chains so that + // we can precisely represent both "what memory will this read/write/is + // clobbered by" and "what instructions can I move this past". + Def = isModSet(ModRef) || isOrdered(I); + Use = isRefSet(ModRef); + } // It's possible for an instruction to not modify memory at all. During // construction, we ignore them. Index: lib/Analysis/MemorySSAUpdater.cpp =================================================================== --- lib/Analysis/MemorySSAUpdater.cpp +++ lib/Analysis/MemorySSAUpdater.cpp @@ -13,6 +13,7 @@ #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/IteratedDominanceFrontier.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" @@ -389,6 +390,440 @@ } } +void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) { + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) { + MPhi->unorderedDeleteIncomingBlock(From); + if (MPhi->getNumIncomingValues() == 1) + removeMemoryAccess(MPhi); + } +} + +void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB, + ValueToValueMapTy &VMap, + PhiToDefMap &MPhiMap) { + auto GetNewDefiningAccess = [&](MemoryAccess *MA) -> MemoryAccess * { + MemoryAccess *InsnDefining = MA; + if (MemoryUseOrDef *DefMUD = dyn_cast_or_null(InsnDefining)) + if (Instruction *DefMUDI = DefMUD->getMemoryInst()) + if (Instruction *NewDefMUDI = + dyn_cast_or_null(VMap[DefMUDI])) + InsnDefining = MSSA->getMemoryAccess(NewDefMUDI); + if (MemoryPhi *DefPhi = dyn_cast_or_null(InsnDefining)) + if (MemoryAccess *NewDefPhi = MPhiMap[DefPhi]) + InsnDefining = NewDefPhi; + assert(InsnDefining && "Defining instruction cannot be nullptr."); + return InsnDefining; + }; + + const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB); + if (!Acc) + return; + for (const MemoryAccess &MA : *Acc) { + if (const MemoryUseOrDef *MUD = dyn_cast_or_null(&MA)) { + Instruction *Insn = MUD->getMemoryInst(); + Instruction *NewInsn = dyn_cast_or_null(VMap[Insn]); + // Entry does not exist if the clone of the block did not clone all + // instructions. This occurs in LoopRotate when cloning instructions + // from the old header to the old preheader. + if (!NewInsn) + continue; + MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess( + NewInsn, GetNewDefiningAccess(MUD->getDefiningAccess()), MUD); + MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End); + } + } +} + +void MemorySSAUpdater::updateForClonedLoop(LoopBlocksRPO &LoopBlocks, + ArrayRef ExitBlocks, + ValueToValueMapTy &VMap, + bool IgnoreIncomingWithNoClones) { + PhiToDefMap MPhiMap; + + auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) { + assert(Phi && NewPhi && "Invalid Phi nodes."); + BasicBlock *NewPhiBB = NewPhi->getBlock(); + SmallPtrSet NewPhiBBPreds(pred_begin(NewPhiBB), + pred_end(NewPhiBB)); + for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) { + MemoryAccess *IncomingAccess = Phi->getIncomingValue(It); + BasicBlock *IncBB = Phi->getIncomingBlock(It); + + if (BasicBlock *NewIncBB = dyn_cast_or_null(VMap[IncBB])) + IncBB = NewIncBB; + else if (IgnoreIncomingWithNoClones) + continue; + + // Now we have IncBB, and will need to add incoming from it to NewPhi. + + // If IncBB is not a predecessor of NewPhiBB, then do not add it. + // NewPhiBB was cloned without that edge. + if (!NewPhiBBPreds.count(IncBB)) + continue; + + // Determine incoming value and add it as incoming from IncBB. + if (MemoryUseOrDef *IncMUD = + dyn_cast_or_null(IncomingAccess)) { + if (Instruction *IncI = IncMUD->getMemoryInst()) + if (Instruction *NewIncI = + dyn_cast_or_null(VMap[IncI])) { + IncMUD = MSSA->getMemoryAccess(NewIncI); + assert(IncMUD && + "MemoryUseOrDef cannot be null, all pred processed."); + } + NewPhi->addIncoming(IncMUD, IncBB); + } else if (MemoryPhi *IncPhi = + dyn_cast_or_null(IncomingAccess)) { + if (MemoryAccess *NewDefPhi = MPhiMap[IncPhi]) + NewPhi->addIncoming(NewDefPhi, IncBB); + else + NewPhi->addIncoming(IncPhi, IncBB); + } + } + }; + + auto ProcessBlock = [&](BasicBlock *BB) { + BasicBlock *NewBlock = dyn_cast_or_null(VMap[BB]); + if (!NewBlock) + return; + + assert(!MSSA->getWritableBlockAccesses(NewBlock) && + "Cloned block should have no accesses"); + + // Add MemoryPhi. + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) { + MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock); + MPhiMap[MPhi] = NewPhi; + } + // Update Uses and Defs. + cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap); + }; + + for (auto BB : llvm::concat(LoopBlocks, ExitBlocks)) + ProcessBlock(BB); + + for (auto BB : llvm::concat(LoopBlocks, ExitBlocks)) + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) + if (MemoryAccess *NewPhi = MPhiMap[MPhi]) + FixPhiIncomingValues(MPhi, cast(NewPhi)); +} + +void MemorySSAUpdater::updateForClonedBlockIntoPred(BasicBlock *BB, + BasicBlock *P1, + ValueToValueMapTy &VM) { + // All defs/phis from outside BB that are used in BB, are valid uses in P1. + // Since those defs/phis must have dominated BB, and also dominate P1. + // Defs from BB being used in BB will be replaced with the cloned defs from + // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the + // incoming def into the Phi from P1. + PhiToDefMap MPhiMap; + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) { + MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1); + } + cloneUsesAndDefs(BB, P1, VM, MPhiMap); +} + +void MemorySSAUpdater::updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, ValueToValueMapTy &VMap, + DominatorTree *DT) { + SmallVector Updates; + // Update/insert phis in all successors of exit blocks. + for (unsigned It = 0, E = ExitBlocks.size(); It != E; ++It) { + BasicBlock *Exit = ExitBlocks[It]; + if (VMap[Exit]) { + BasicBlock *NewExit = cast(VMap[Exit]); + BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); + Updates.push_back({NewExit, ExitSucc}); + } + } + updatePhisWhenAddingBBPredecessors(Updates, DT); +} + +void MemorySSAUpdater::updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, + SmallVectorImpl> &VMaps, + DominatorTree *DT) { + SmallVector Updates; + // Update/insert phis in all successors of exit blocks. + for (unsigned It = 0, E = ExitBlocks.size(); It != E; ++It) { + BasicBlock *Exit = ExitBlocks[It]; + for (auto &VMap : VMaps) + if ((*VMap)[Exit]) { + BasicBlock *NewExit = cast((*VMap)[Exit]); + BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); + Updates.push_back({NewExit, ExitSucc}); + } + } + updatePhisWhenAddingBBPredecessors(Updates, DT); +} + +void MemorySSAUpdater::replaceDefToFixDomination(MemoryAccess *ToReplace, + MemoryAccess *ReplaceWith, + DominatorTree *DT) { + assert((!isa(ToReplace) && !isa(ReplaceWith)) && + "Must replace a definition with another definition"); + assert(MSSA->dominates(ReplaceWith, ToReplace) && + "Replacement def must dominate def being replaced"); + BasicBlock *ToReplaceBB = ToReplace->getBlock(); + Value::use_iterator UI = ToReplace->use_begin(), E = ToReplace->use_end(); + for (; UI != E;) { + Use &U = *UI; + ++UI; + auto *Usr = dyn_cast(U.getUser()); + if (!Usr) + continue; + BasicBlock *UsrBlock = Usr->getBlock(); + if (!DT->dominates(ToReplaceBB, UsrBlock)) { + U.set(ReplaceWith); + } + } +} + +void MemorySSAUpdater::updateHeaderPhisUsesAfterLoopUnswitch( + BasicBlock *Header, BasicBlock *NewPreheader, DominatorTree *DT) { + MemoryPhi *MPhi = MSSA->getMemoryAccess(Header); + if (!MPhi) + return; + auto *NewMA = dyn_cast_or_null( + MPhi->getIncomingValueForBlock(NewPreheader)); + assert(NewMA && "MemoryPhi must have an incoming value from new preheader"); + + replaceDefToFixDomination(MPhi, NewMA, DT); +} + +void MemorySSAUpdater::wireOldPhiIntoNewPhiAfterUnswitch( + BasicBlock *From, BasicBlock *To, BasicBlock *OldIncoming, + BasicBlock *NewIncoming, bool FullUnswitch) { + + MemoryPhi *MPhi = MSSA->getMemoryAccess(From); + if (!MPhi) + return; + + assert(MPhi && "Cannot wire from a block with no MemoryPhi"); + MemoryAccess *IncomingVal = + cast(MPhi->getIncomingValueForBlock(OldIncoming)); + // Last definition in From. At least one exists: MPhi. + MemoryAccess *LastDef = &*(MSSA->getWritableBlockDefs(From)->rbegin()); + + MemoryPhi *NewPhi = MSSA->createMemoryPhi(To); + NewPhi->addIncoming(IncomingVal, NewIncoming); + NewPhi->addIncoming(LastDef, From); + + if (FullUnswitch) { + MPhi->unorderedDeleteIncomingBlock(OldIncoming); + if (MPhi->getNumIncomingValues() == 1) + removeMemoryAccess(MPhi); + } +} + +void MemorySSAUpdater::updatePhisWhenAddingBBPredecessors( + ArrayRef Updates, DominatorTree *DT) { + // Get recursive last Def, assuming well formed MSSA and updated DT. + std::function GetLastDef = + [&](BasicBlock *BB) -> MemoryAccess * { + MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB); + // Return last Def or Phi in BB, if it exists. + if (Defs) + return &*(--Defs->end()); + + BasicBlock *Pred = BB->getSinglePredecessor(); + if (!Pred) { + // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its + // DT is invalidated. Return LoE as its last def. This will be added to + // MemoryPhi node, and later deleted when the block is deleted. + if (!DT->getNode(BB)) + return MSSA->getLiveOnEntryDef(); + if (auto *IDom = DT->getNode(BB)->getIDom()) + if (IDom->getBlock() != BB) + return GetLastDef(IDom->getBlock()); + return MSSA->getLiveOnEntryDef(); + } + assert(Pred && + "Basic Block must have a single predecessor, a MemoryPhi or LoE"); + return GetLastDef(Pred); + }; + + // Get nearest IDom given a set of blocks. + auto FindNearestCommonDominator = + [&](SmallPtrSetImpl &BBSet) -> BasicBlock * { + BasicBlock *PrevIDom = *BBSet.begin(); + for (auto BB : BBSet) + PrevIDom = DT->findNearestCommonDominator(PrevIDom, BB); + return PrevIDom; + }; + + // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not + // include CurrIDom. + auto GetNoLongerDomBlocks = + [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom, + SmallVectorImpl &BlocksPrevDom) { + if (PrevIDom == CurrIDom) + return; + BlocksPrevDom.push_back(PrevIDom); + BasicBlock *NextIDom = PrevIDom; + while (BasicBlock *UpIDom = + DT->getNode(NextIDom)->getIDom()->getBlock()) { + if (UpIDom == CurrIDom) + break; + BlocksPrevDom.push_back(UpIDom); + NextIDom = UpIDom; + } + }; + + // Map a BB with a set of predecessors it is being added. + SmallDenseMap>> + AddedPredMap; + for (auto Edge : Updates) { + BasicBlock *BB = Edge.getTo(); + auto BlockSet = &AddedPredMap[BB]; + if (!BlockSet->get()) { + AddedPredMap[BB] = make_unique>(); + BlockSet = &AddedPredMap[BB]; + } + BlockSet->get()->insert(Edge.getFrom()); + } + + // Store all existing predecessor for each BB, at least one must exist. + SmallDenseMap>> + PrevPredMap; + for (auto &Pair : AddedPredMap) { + auto *BB = Pair.first; + auto *AddedBlockSet = Pair.second.get(); + PrevPredMap[BB] = make_unique>(); + auto *PrevBlockSet = PrevPredMap[BB].get(); + for (pred_iterator Pi = pred_begin(BB), Pe = pred_end(BB); Pi != Pe; ++Pi) + if (!AddedBlockSet->count(*Pi)) + PrevBlockSet->insert(*Pi); + if (!PrevBlockSet->size()) { + assert(pred_size(BB) == AddedBlockSet->size() && "Duplicate edges added"); + LLVM_DEBUG( + dbgs() + << "Adding a predecessor to a block with previously no predecessors. " + "No MSSA updates known for this case. They must be handled via " + "block cloning or creating new accesses for the new block.\n"); + PrevPredMap.erase(BB); + } + } + + // FIXME: The set and vector store the same data. + // Can llvm_concat accept a sets? + SmallPtrSet DefiningBlocks; + SmallVector BlocksToProcess; + + SmallVector BlocksWithDefsToReplace; + + for (auto &Pair : PrevPredMap) { + auto *BB = Pair.first; + auto *PrevBlockSet = Pair.second.get(); + auto *AddedBlockSet = AddedPredMap[BB].get(); + + SmallDenseMap LastDefAddedPred; + for (auto *AddedPred : *AddedBlockSet) { + auto *DefPn = GetLastDef(AddedPred); + assert(DefPn != nullptr && "Unable to find last definition."); + LastDefAddedPred[AddedPred] = DefPn; + } + + MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB); + // If Phi exists, add an incoming edge from each added pred and move on. + if (NewPhi) { + for (auto LastDefPredPair : LastDefAddedPred) + NewPhi->addIncoming(LastDefPredPair.second, LastDefPredPair.first); + // FIXME: May still need to check defs that no longer dominate their + // uses. In particular defs optimized through NewPhi? + continue; + } + + // Pick any existing predecessor and get its definition. All other existing + // predecessors should have the same one, since no phi existed. + auto *P1 = *PrevBlockSet->begin(); + MemoryAccess *DefP1 = GetLastDef(P1); + + // Check DefP1 against all Defs in LastDefPredPair. If all the same, nothing + // to add. + bool InsertPhi = false; + for (auto LastDefPredPair : LastDefAddedPred) + if (DefP1 != LastDefPredPair.second) { + InsertPhi = true; + break; + } + if (!InsertPhi) + continue; + + // Insert Phi with new values for new predecessors and old value for all + // other predecessors. + NewPhi = MSSA->createMemoryPhi(BB); + for (auto Pred : *AddedBlockSet) + NewPhi->addIncoming(LastDefAddedPred[Pred], Pred); + for (auto Pred : *PrevBlockSet) + NewPhi->addIncoming(DefP1, Pred); + + // Get all blocks that used to dominate BB and no longer do after adding + // AddedBlockSet, where PrevBlockSet are the previously known predecessors. + assert(DT->getNode(BB)->getIDom() && "BB does not have valid idom"); + BasicBlock *PrevIDom = FindNearestCommonDominator(*PrevBlockSet); + assert(PrevIDom && "Previous IDom should exists"); + BasicBlock *NewIDom = DT->getNode(BB)->getIDom()->getBlock(); + assert(NewIDom && "BB should have a new valid idom"); + assert(DT->dominates(NewIDom, PrevIDom) && + "New idom should dominate old idom"); + assert(DT->dominates(DefP1->getBlock(), PrevIDom) && + "Block with last definition must dominate idom"); + GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace); + + // Insert BB in the set of blocks that now have definition. We'll use this + // to compute IDF and add Phis there next. + DefiningBlocks.insert(BB); + BlocksToProcess.push_back(BB); + } + + // Compute IDF and add Phis in all IDF blocks without one.. + ForwardIDFCalculator IDFs(*DT); + IDFs.setDefiningBlocks(DefiningBlocks); + SmallVector IDFBlocks; + IDFs.calculate(IDFBlocks); + for (auto *BBIDF : IDFBlocks) + if (!MSSA->getMemoryAccess(BBIDF)) { + auto *IDFPhi = MSSA->createMemoryPhi(BBIDF); + for (pred_iterator Pi = pred_begin(BBIDF), Pe = pred_end(BBIDF); Pi != Pe; + ++Pi) + IDFPhi->addIncoming(GetLastDef(*Pi), *Pi); + } + + // Now for all defs in BlocksWithDefsToReplace, if there are uses they no + // longer dominate, replace those with the closest dominating def. + for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) + if (auto BlockDefList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) + for (auto &DefToReplaceUses : *BlockDefList) { + BasicBlock *DominatedBlock; + BasicBlock *DominatingBlock = DefToReplaceUses.getBlock(); + Value::use_iterator UI = DefToReplaceUses.use_begin(), + E = DefToReplaceUses.use_end(); + for (; UI != E;) { + Use &U = *UI; + ++UI; + MemoryAccess *Usr = dyn_cast(U.getUser()); + if (!Usr) + continue; + if (MemoryPhi *UsrPhi = dyn_cast(Usr)) { + DominatedBlock = UsrPhi->getIncomingBlock(U); + if (!DT->dominates(DominatingBlock, DominatedBlock)) + U.set(GetLastDef(DominatedBlock)); + } else { + DominatedBlock = Usr->getBlock(); + if (!DT->dominates(DominatingBlock, DominatedBlock)) { + for (auto *BB : + llvm::concat(BlocksToProcess, IDFBlocks)) + if (DT->dominates(BB, DominatedBlock)) { + U.set(MSSA->getMemoryAccess(BB)); + break; + } + } + } + } + } // end for over all defs to have uses replaced. +} + // Move What before Where in the MemorySSA IR. template void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB, @@ -415,6 +850,74 @@ NonOptPhis.clear(); } +void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From, + BasicBlock *To, + Instruction *Start) { + assert(MSSA->getBlockAccesses(To) == nullptr && + "To block is expected to be free of MemoryAccesses."); + moveAllAccesses(From, To, Start, MemorySSA::End); + for (succ_iterator Si = succ_begin(To), Se = succ_end(To); Si != Se; ++Si) + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(*Si)) + MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To); +} + +void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, + Instruction *Start) { + assert(From->getSinglePredecessor() == To && + "From block is expected to have a single predecessor (To)."); + moveAllAccesses(From, To, Start, MemorySSA::End); + for (succ_iterator Si = succ_begin(From), Se = succ_end(From); Si != Se; ++Si) + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(*Si)) + MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To); +} + +void MemorySSAUpdater::replacePhiIncomingBlock(BasicBlock *BB, + BasicBlock *ToReplace, + BasicBlock *ReplaceWith) { + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) { + unsigned I = MPhi->getBasicBlockIndex(ToReplace); + assert((I >= 0) && "MemoryPhi position out of bounds"); + MPhi->setIncomingBlock(I, ReplaceWith); + } +} + +// All accesses in To used to be in From. Update access lists. +void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To, + Instruction *Start, + MemorySSA::InsertionPlace Where) { + + if (MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From)) { + MemoryAccess *FirstInNew = nullptr; + BasicBlock::iterator StartSearch = Start->getIterator(); + while (StartSearch != To->end()) { + FirstInNew = MSSA->getMemoryAccess(&*StartSearch); + if (FirstInNew) + break; + ++StartSearch; + } + if (FirstInNew) { + auto *MUD = dyn_cast_or_null(FirstInNew); + auto NextIt = ++MUD->getIterator(); + MemoryUseOrDef *NextMUD = + (NextIt == Accs->end()) ? nullptr + : dyn_cast_or_null(&*NextIt); + MSSA->moveTo(MUD, To, Where); + auto InsertionPlace = ++MUD->getIterator(); + + while (NextMUD) { + MUD = NextMUD; + NextIt = ++MUD->getIterator(); + MemorySSA::AccessList *NewAccs = MSSA->getWritableBlockAccesses(From); + NextMUD = (!NewAccs || NextIt == NewAccs->end()) + ? nullptr + : dyn_cast_or_null(&*NextIt); + MSSA->moveTo(MUD, To, InsertionPlace); + InsertionPlace = ++MUD->getIterator(); + } + } + } +} + // Move What before Where in the MemorySSA IR. void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) { moveTo(What, Where->getBlock(), Where->getIterator()); @@ -430,6 +933,16 @@ return moveTo(What, BB, Where); } +void MemorySSAUpdater::movePhiToNewImmediatePredecessor(BasicBlock *Old, + BasicBlock *New) { + assert(MSSA->getWritableBlockAccesses(New) == nullptr && + "Access list should be null for a new block"); + MemoryPhi *Phi = MSSA->getMemoryAccess(Old); + if (!Phi) + return; + MSSA->moveTo(Phi, New, MemorySSA::Beginning); +} + /// If all arguments of a MemoryPHI are defined by the same incoming /// argument, return that argument. static MemoryAccess *onlySingleValue(MemoryPhi *MP) {