Index: include/llvm/Analysis/MemorySSA.h =================================================================== --- include/llvm/Analysis/MemorySSA.h +++ include/llvm/Analysis/MemorySSA.h @@ -563,6 +563,40 @@ return getIncomingValue(Idx); } + void deleteIncoming(const unsigned I) { + unsigned E = getNumOperands(); + assert((I < E) && "Cannot remove out of bounds Phi entry."); + assert((E >= 2) && "Cannot only remove incoming values in MemoryPhis with " + "at least 2 values."); + setIncomingValue(I, getIncomingValue(E - 1)); + setIncomingBlock(I, block_begin()[E - 1]); + setOperand(E - 1, nullptr); + block_begin()[E - 1] = nullptr; + setNumHungOffUseOperands(getNumOperands() - 1); + } + + void deleteIncomingBlock(const BasicBlock *BB) { + for (unsigned I = 0, E = getNumOperands(); I != E; ++I) + if (block_begin()[I] == BB) { + deleteIncoming(I); + E = getNumOperands(); + --I; + } + assert((getNumOperands() >= 1) && + "Cannot remove all incoming blocks in a MemoryPhi."); + } + + void deleteIncomingValue(const MemoryAccess *MA) { + for (unsigned I = 0, E = getNumOperands(); I != E; ++I) + if (getIncomingValue(I) == MA) { + deleteIncoming(I); + E = getNumOperands(); + --I; + } + assert((getNumOperands() >= 1) && + "Cannot remove all incoming values in a MemoryPhi."); + } + static bool classof(const Value *V) { return V->getValueID() == MemoryPhiVal; } @@ -740,7 +774,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, @@ -754,7 +788,8 @@ InsertionPlace); void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator); - MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); + MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *, + const MemoryUseOrDef *Template = nullptr); private: class CachingWalker; @@ -774,7 +809,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 @@ -45,6 +45,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 +58,8 @@ class LLVMContext; class raw_ostream; +using ValueToValueMapTy = ValueMap; + class MemorySSAUpdater { private: MemorySSA *MSSA; @@ -85,11 +88,77 @@ /// Where a mayalias b, *does* require RenameUses be set to true. void insertDef(MemoryDef *Def, bool RenameUses = false); void insertUse(MemoryUse *Use); + 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(std::vector::const_reverse_iterator BIt, + std::vector::const_reverse_iterator EIt, + ArrayRef ExitBlocks, ValueToValueMapTy &VM, + bool IgnoreIncomingWithNoClones = false); + /// Update phi nodes in exit block successors following cloning. + void updateExitBlocksForClonedLoop(ArrayRef ExitBlocks, + ValueToValueMapTy &VM, 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(SmallVectorImpl &BB, + SmallVectorImpl &P_Added, + 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. + void wireOldPhiIntoNewPhiAfterUnswitch(BasicBlock *From, BasicBlock *To, + BasicBlock *OldIncoming, + BasicBlock *NewIncoming); 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); + 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 @@ -137,11 +206,20 @@ /// load is simply erased (not replaced), removeMemoryAccess should be called /// on the MemoryAccess for that store/load. void removeMemoryAccess(MemoryAccess *); + /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. + /// Assumption we make here: all uses of deleted defs and phi must either + /// occur in blocks about to be deleted (thus will be deleted as well), or + /// they occur in phis that will simply lose an incoming value. + void removeBlocks(const SmallPtrSetImpl &DeadBlocks); private: // 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 * @@ -154,6 +232,10 @@ template MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); void fixupDefs(const SmallVectorImpl &); + // 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,24 @@ 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; + } 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,400 @@ } } +void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) { + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) + MPhi->deleteIncomingBlock(From); + // TODO: Additional updates? +} + +void MemorySSAUpdater::updateForClonedLoop( + std::vector::const_reverse_iterator BIt, + std::vector::const_reverse_iterator EIt, + ArrayRef ExitBlocks, ValueToValueMapTy &VMap, + bool IgnoreIncomingWithNoClones) { + SmallDenseMap 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 (MemoryPhi *NewDefPhi = MPhiMap[DefPhi]) + InsnDefining = NewDefPhi; + assert(InsnDefining && "Defining instruction cannot be nullptr."); + return InsnDefining; + }; + + auto CloneUsesAndDefs = [&](BasicBlock *BB, BasicBlock *NewBB) { + const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB); + if (!Acc) + return; + for (const MemoryAccess &MA : *Acc) { + if (const MemoryDef *MD = dyn_cast_or_null(&MA)) { + Instruction *Insn = MD->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 *NewDef = MSSA->createDefinedAccess( + NewInsn, GetNewDefiningAccess(MD->getDefiningAccess()), MD); + MSSA->insertIntoListsForBlock(NewDef, NewBB, MemorySSA::End); + } else if (const MemoryUse *MU = dyn_cast_or_null(&MA)) { + Instruction *Insn = MU->getMemoryInst(); + Instruction *NewInsn = dyn_cast_or_null(VMap[Insn]); + // Same as above. + if (!NewInsn) + continue; + MemoryAccess *NewUse = MSSA->createDefinedAccess( + NewInsn, GetNewDefiningAccess(MU->getDefiningAccess()), MU); + MSSA->insertIntoListsForBlock(NewUse, NewBB, MemorySSA::End); + } + } + }; + + 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 (MemoryPhi *NewDefPhi = MPhiMap[IncPhi]) + IncPhi = NewDefPhi; + NewPhi->addIncoming(IncPhi, IncBB); + } + } + }; + + auto ProcessBlock = [&](BasicBlock *BB) { + BasicBlock *NewBlock = dyn_cast_or_null(VMap[BB]); + if (!NewBlock) + return; + + // Add MemoryPhi. + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) { + MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock); + MPhiMap[MPhi] = NewPhi; + } + // Update Uses and Defs. + CloneUsesAndDefs(BB, NewBlock); + }; + + for (auto It = BIt; It != EIt; ++It) + ProcessBlock(*It); + for (auto BB : ExitBlocks) + ProcessBlock(BB); + + for (auto It = BIt; It != EIt; ++It) + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(*It)) + if (MemoryPhi *NewPhi = MPhiMap[MPhi]) + FixPhiIncomingValues(MPhi, NewPhi); + for (auto BB : ExitBlocks) + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) + if (MemoryPhi *NewPhi = MPhiMap[MPhi]) + FixPhiIncomingValues(MPhi, NewPhi); +} + +void MemorySSAUpdater::updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, ValueToValueMapTy &VMap, + DominatorTree *DT) { + // Update/insert phis in all successors of exit blocks. + SmallVector BBs; + SmallVector Pns; + for (unsigned It = 0, E = ExitBlocks.size(); It != E; ++It) { + BasicBlock *Exit = ExitBlocks[It]; + dbgs() << "Exit block to possibly add phi: " << Exit->getName() << "\n"; + // SimpleLoopUnswitch does not clone all exit blocks. + if (!VMap[Exit]) + continue; + BasicBlock *NewExit = cast(VMap[Exit]); + dbgs() << "Exit block clone: " << NewExit->getName() << "\n"; + BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); + BBs.push_back(ExitSucc); + Pns.push_back(NewExit); + } + updatePhisWhenAddingBBPredecessors(BBs, Pns, 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) { + + MemoryPhi *MPhi = MSSA->getMemoryAccess(From); + if (!MPhi) + return; + + assert(MPhi && "Cannot wire from a block with no MemoryPhi"); + MemoryAccess *IncomingVal = + cast(MPhi->getIncomingValueForBlock(OldIncoming)); + MPhi->deleteIncomingBlock(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); +} + +void MemorySSAUpdater::updatePhisWhenAddingBBPredecessors( + SmallVectorImpl &BBs, SmallVectorImpl &Pns, + 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 BB's IDom before adding pred Pn, where P1 is a known pred. + auto GetPreviousIDom = [&](BasicBlock *BB, BasicBlock *P1, + BasicBlock *Pn) -> BasicBlock * { + BasicBlock *PrevIDom = P1; + for (pred_iterator Pi = pred_begin(BB), Pe = pred_end(BB); Pi != Pe; ++Pi) + if (*Pi != Pn) + PrevIDom = DT->findNearestCommonDominator(PrevIDom, *Pi); + return PrevIDom; + }; + + // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. + auto GetNoLongerDomBlocks = + [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom, + SmallVectorImpl &BlocksPrevDom) { + 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; + } + }; + + SmallPtrSet DefiningBlocks; + SmallVector BlocksToProcess; + SmallVector BlocksWithDefsToReplace; + + unsigned I = 0; + for (BasicBlock *BB : BBs) { + BasicBlock *Pn = Pns[I++]; + MemoryAccess *DefPn = GetLastDef(Pn); + assert(DefPn != nullptr && "Unable to find last definition."); + + MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB); + // If Phi exists, add an incoming edge from Pn and move on. + if (NewPhi) { + NewPhi->addIncoming(DefPn, Pn); + // FIXME: May still need to check defs that no longer dominate their + // uses. In particular defs optimized through NewPhi? + continue; + } + + // If no Phi used to exist, all other predecessors had the same incoming + // def, so choose any one previous predecessor P1. + BasicBlock *P1 = nullptr; + for (pred_iterator Pi = pred_begin(BB), Pe = pred_end(BB); Pi != Pe; ++Pi) + if (*Pi != Pn) { + P1 = *Pi; + break; + } + + // If no other predecessor exists, BB is a newly added block and a single + // edge (from Pn is coming into it). Do not handle this here, move on. + if (!P1) { + assert(pred_size(BB) == 1 && "Expected 1 predecessor"); + 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"); + continue; + } + + // A different predecessor was found, get it's last definition. + MemoryAccess *DefP1 = GetLastDef(P1); + + // Nothing to do if new incoming def is the same, no phi to add. + if (DefP1 == DefPn) + continue; + + // Insert Phi with new value for new predecessor and old value for all other + // predecessors. + NewPhi = MSSA->createMemoryPhi(BB); + for (pred_iterator Pi = pred_begin(BB), Pe = pred_end(BB); Pi != Pe; ++Pi) + if (*Pi != Pn) { + NewPhi->addIncoming(DefP1, *Pi); + } + NewPhi->addIncoming(DefPn, Pn); + + // Get all blocks that used to dominate BB and no longer do after adding Pn, + // where P1 is a known predecessor, P1 != Pn. + BasicBlock *PrevIDom = GetPreviousIDom(BB, P1, Pn); + assert(DT->dominates(DefP1->getBlock(), PrevIDom) && + "Block with last definition must dominate idom"); + GetNoLongerDomBlocks(PrevIDom, DT->getNode(BB)->getIDom()->getBlock(), + 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 everywhere where there aren't any and there + // are different incoming defs. + // FIXME: is it redundant to check that incoming defs are different and should + // just always add phis? + ForwardIDFCalculator IDFs(*DT); + IDFs.setDefiningBlocks(DefiningBlocks); + SmallVector IDFBlocks; + IDFs.calculate(IDFBlocks); + for (auto *BBIDF : IDFBlocks) { + if (!MSSA->getMemoryAccess(BBIDF)) { + SmallVector PredDefs; + MemoryAccess *CmpDef = nullptr; + bool CreatePhi = false; + for (pred_iterator Pi = pred_begin(BBIDF), Pe = pred_end(BBIDF); Pi != Pe; + ++Pi) { + MemoryAccess *PiLastDef = GetLastDef(*Pi); + PredDefs.push_back(PiLastDef); + if (!CmpDef) + CmpDef = PiLastDef; + else if (CmpDef != PiLastDef) + CreatePhi = true; + } + if (CreatePhi) { + auto *IDFPhi = MSSA->createMemoryPhi(BBIDF); + unsigned I = 0; + for (pred_iterator Pi = pred_begin(BBIDF), Pe = pred_end(BBIDF); + Pi != Pe; ++Pi, ++I) { + IDFPhi->addIncoming(PredDefs[I], *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)); + // Conservative (losing optimized accesses): last def, not phi. + // With optimization, tbd if this is always correct: + // U.set(MSSA->getMemoryAccess(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 +810,64 @@ 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); +} + +// 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 +883,14 @@ return moveTo(What, BB, Where); } +void MemorySSAUpdater::movePhiToNewImmediatePredecessor(BasicBlock *Old, + BasicBlock *New) { + 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) { @@ -492,6 +953,51 @@ MSSA->removeFromLists(MA); } +void MemorySSAUpdater::removeBlocks( + const SmallPtrSetImpl &DeadBlocks) { + + // First delete all uses of BB in MemoryPhis. + for (BasicBlock *BB : DeadBlocks) { + TerminatorInst *TI = BB->getTerminator(); + if (TI) + for (BasicBlock *Succ : TI->successors()) { + if (!DeadBlocks.count(Succ)) + if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) { + MP->deleteIncomingBlock(BB); + if (MP->getNumIncomingValues() == 1) + removeMemoryAccess(MP); + } + } + } + + // Next, delete all memory accesses in each block (and their uses) + for (BasicBlock *BB : DeadBlocks) { + while (MemorySSA::AccessList *Accesses = + MSSA->getWritableBlockAccesses(BB)) { + MemoryAccess *MA = &*Accesses->begin(); + // Not special casing MemoryPhis. + if (!isa(MA) && !MA->use_empty()) { + if (MA->hasValueHandle()) + ValueHandleBase::ValueIsDeleted(MA); + + while (!MA->use_empty()) { + Use &U = *MA->use_begin(); + MemoryAccess *User = dyn_cast(U.getUser()); + // If user won't be deleted, it must be a MemoryPhi losing a value. + // We should have addressed that in the pass above. + assert(DeadBlocks.count(User->getBlock()) && + "User must be deleted too."); + // So, the access using MA will be deleted anyway, replace use with + // LoE to clear MA's uses. + U.set(MSSA->getLiveOnEntryDef()); + } + } + MSSA->removeFromLookups(MA); + MSSA->removeFromLists(MA); + } + } +} + MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB( Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point) {