Index: include/llvm/Analysis/MemorySSA.h =================================================================== --- include/llvm/Analysis/MemorySSA.h +++ include/llvm/Analysis/MemorySSA.h @@ -796,7 +796,8 @@ InsertionPlace); void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator); - MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); + MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *, + const MemoryUseOrDef *Template = nullptr); private: class CachingWalker; @@ -816,7 +817,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,8 +35,10 @@ #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/CFGDiff.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Module.h" #include "llvm/IR/OperandTraits.h" @@ -45,6 +47,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 +60,12 @@ class LLVMContext; class raw_ostream; +using ValueToValueMapTy = ValueMap; +using PhiToDefMap = SmallDenseMap; +using DTUpdate = cfg::Update; +using GraphDiffInvBBPair = + std::pair *, Inverse>; + class MemorySSAUpdater { private: MemorySSA *MSSA; @@ -70,6 +79,7 @@ public: MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} + /// 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 @@ -89,10 +99,45 @@ /// 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 the MemoryPhi in `To` to have a single incoming edge from `From`, + /// following a CFG change that replaced multiple edges (switch) with a direct + /// branch. + void removeAllButOneEdge(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. Exit blocks + /// that were not cloned don't have additional predecessors added. + void updateExitBlocksForClonedLoop(ArrayRef ExitBlocks, + ValueToValueMapTy &VMap, + DominatorTree *DT); + void updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, + SmallVectorImpl> &VMaps, + DominatorTree *DT); + + /// Apply CFG updates, analogous with the DT edge updates. + void applyUpdates(ArrayRef Updates, DominatorTree &DT); + /// Apply CFG insert updates, analogous with the DT edge updates. + void applyInsertUpdates(ArrayRef Updates, DominatorTree *DT); + 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. @@ -132,7 +177,6 @@ void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef Preds); - // 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 @@ -220,6 +264,17 @@ 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); + template + void privateUpdateExitBlocksForClonedLoop(ArrayRef ExitBlocks, + Iter ValuesBegin, Iter ValuesEnd, + DominatorTree *DT); + void applyInsertUpdates(ArrayRef, DominatorTree *DT, + GraphDiff *GD); }; } // end namespace llvm Index: lib/Analysis/MemorySSA.cpp =================================================================== --- lib/Analysis/MemorySSA.cpp +++ lib/Analysis/MemorySSA.cpp @@ -1505,9 +1505,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"); @@ -1530,7 +1531,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 @@ -1539,18 +1541,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" @@ -392,6 +393,479 @@ } } +void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) { + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) { + MPhi->unorderedDeleteIncomingBlock(From); + if (MPhi->getNumIncomingValues() == 1) + removeMemoryAccess(MPhi); + } +} + +void MemorySSAUpdater::removeAllButOneEdge(BasicBlock *From, BasicBlock *To) { + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) { + bool Found = false; + MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) { + if (From != B) + return false; + if (Found) + return true; + Found = true; + return false; + }); + 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 = + cast_or_null(VMap.lookup(DefMUDI))) + InsnDefining = MSSA->getMemoryAccess(NewDefMUDI); + if (MemoryPhi *DefPhi = dyn_cast_or_null(InsnDefining)) + if (MemoryAccess *NewDefPhi = MPhiMap.lookup(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(); + // 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 (Instruction *NewInsn = cast_or_null(VMap.lookup(Insn))) { + 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 = cast_or_null(VMap.lookup(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 = + cast_or_null(VMap.lookup(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.lookup(IncPhi)) + NewPhi->addIncoming(NewDefPhi, IncBB); + else + NewPhi->addIncoming(IncPhi, IncBB); + } + } + }; + + auto ProcessBlock = [&](BasicBlock *BB) { + BasicBlock *NewBlock = cast_or_null(VMap.lookup(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.lookup(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); +} + +template +void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, Iter ValuesBegin, Iter ValuesEnd, + 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 (ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd)) + if (BasicBlock *NewExit = cast_or_null(VMap->lookup(Exit))) { + BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); + Updates.push_back({DT->Insert, NewExit, ExitSucc}); + } + } + applyInsertUpdates(Updates, DT); +} + +void MemorySSAUpdater::updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, ValueToValueMapTy &VMap, + DominatorTree *DT) { + ValueToValueMapTy *Arr[] = {&VMap}; + privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr), + std::end(Arr), DT); +} + +void MemorySSAUpdater::updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, + SmallVectorImpl> &VMaps, + DominatorTree *DT) { + auto GetPtr = [&](const std::unique_ptr &I) { + return I.get(); + }; + using MappedIteratorType = + mapped_iterator *, decltype(GetPtr)>; + auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr); + auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr); + privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT); +} + +void MemorySSAUpdater::applyUpdates(ArrayRef Updates, + DominatorTree &DT) { + SmallVector RevDeleteUpdates; + SmallVector InsertUpdates; + for (auto &Update : Updates) { + if (Update.getKind() == DT.Insert) { + InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()}); + } else + RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()}); + } + + if (RevDeleteUpdates.size()) { + // Update for inserted edges: use newDT and snapshot CFG as if deletes had + // not occured. + DominatorTree NewDT(DT, RevDeleteUpdates); + GraphDiff GD(RevDeleteUpdates); + applyInsertUpdates(InsertUpdates, &NewDT, &GD); + } else { + GraphDiff GD; + applyInsertUpdates(InsertUpdates, &DT, &GD); + } + + // Update for deleted edges + for (auto &Update : RevDeleteUpdates) + removeEdge(Update.getFrom(), Update.getTo()); +} + +void MemorySSAUpdater::applyInsertUpdates(ArrayRef Updates, + DominatorTree *DT) { + GraphDiff GD; + applyInsertUpdates(Updates, DT, &GD); +} + +void MemorySSAUpdater::applyInsertUpdates(ArrayRef Updates, + DominatorTree *DT, + GraphDiff *GD) { + // 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()); + + // If BB has multiple predecessors, get last definition from IDom. + unsigned count = 0; + BasicBlock *Pred = nullptr; + for (auto &Pair : children({GD, BB})) { + Pred = Pair.second; + count++; + if (count == 2) + break; + } + + if (count != 1) { + // [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(); + } + + // Single predecessor, GetLastDef for it. + assert(count == 1 && Pred && "Single predecessors expected."); + 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(); + if (!AddedPredMap.count(BB)) + AddedPredMap[BB] = SmallPtrSet(); + auto &AddedBlockSet = AddedPredMap[BB]; + AddedBlockSet.insert(Edge.getFrom()); + } + + // Store all existing predecessor for each BB, at least one must exist. + SmallDenseMap> PrevPredMap; + SmallDenseMap, int> EdgeCountMap; + for (auto &Pair : AddedPredMap) { + auto *BB = Pair.first; + auto &AddedBlockSet = Pair.second; + PrevPredMap[BB] = SmallPtrSet(); + auto &PrevBlockSet = PrevPredMap[BB]; + for (auto &Pair : children({GD, BB})) { + BasicBlock *Pi = Pair.second; + if (!AddedBlockSet.count(Pi)) { + bool Inserted = PrevBlockSet.insert(Pi).second; + if (!Inserted) + EdgeCountMap[{Pi, BB}]++; + else + EdgeCountMap[{Pi, BB}] = 1; + } else { + if (EdgeCountMap.count({Pi, BB})) + EdgeCountMap[{Pi, BB}]++; + else + EdgeCountMap[{Pi, BB}] = 1; + } + } + + if (!PrevBlockSet.size()) { + assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added."); + PrevPredMap.erase(BB); + LLVM_DEBUG( + dbgs() + << "Adding a predecessor to a block with no predecessors." + "This must be an edge added to a new, likely cloned, block." + "Its memory accesses must be already correct, assuming completed " + "via the updateExitBlocksForClonedLoop API." + "Assert a single such edge is added so no phi addition or " + "additional processing is required.\n"); + assert(AddedBlockSet.size() == 1 && + "Can only handle adding one predecessor to a new block."); + } + } + + SmallVector BlocksToProcess; + SmallVector BlocksWithDefsToReplace; + + // First create MemoryPhis in all blocks that don't have one. + for (auto &Pair : PrevPredMap) { + auto *BB = Pair.first; + if (!MSSA->getMemoryAccess(BB)) + MSSA->createMemoryPhi(BB); + } + + // Now we'll fill in the MemoryPhis with the right incoming values. + for (auto &Pair : PrevPredMap) { + auto *BB = Pair.first; + auto &PrevBlockSet = Pair.second; + auto &AddedBlockSet = AddedPredMap[BB]; + assert(PrevBlockSet.size() > 0 && + "At least one previous predecessor must exist."); + + 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 is not empty, add an incoming edge from each added pred and move + // on. + if (NewPhi->getNumOperands()) { + for (auto LastDefPredPair : LastDefAddedPred) + for (int I = 0, E = EdgeCountMap[{LastDefPredPair.first, BB}]; I < E; + ++I) + 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) { + // Add a single incoming value in case this Phi is already used in another + // newly added Phi. Then delete it. Now, when NewPhi is deleted, its uses + // will be replaced with DefP1. + NewPhi->addIncoming(DefP1, P1); + removeMemoryAccess(NewPhi); + continue; + } + + // Update Phi with new values for new predecessors and old value for all + // other predecessors. + for (auto Pred : AddedBlockSet) + for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I) + NewPhi->addIncoming(LastDefAddedPred[Pred], Pred); + for (auto Pred : PrevBlockSet) + for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I) + 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. + BlocksToProcess.push_back(BB); + } + + // Compute IDF and add Phis in all IDF blocks without one.. + ForwardIDFCalculator IDFs(*DT, GD); + SmallPtrSet DefiningBlocks(BlocksToProcess.begin(), + BlocksToProcess.end()); + IDFs.setDefiningBlocks(DefiningBlocks); + SmallVector IDFBlocks; + IDFs.calculate(IDFBlocks); + for (auto *BBIDF : IDFBlocks) + if (!MSSA->getMemoryAccess(BBIDF)) { + auto *IDFPhi = MSSA->createMemoryPhi(BBIDF); + for (auto &Pair : children({GD, BBIDF})) { + BasicBlock *Pi = Pair.second; + 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,