Index: include/llvm/Analysis/MemorySSA.h =================================================================== --- include/llvm/Analysis/MemorySSA.h +++ include/llvm/Analysis/MemorySSA.h @@ -563,6 +563,49 @@ 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 remove all incoming values in a MemoryPhi."); + for (unsigned J = I + 1; J != E; ++J) { + setIncomingValue(J - 1, getIncomingValue(J)); + setIncomingBlock(J - 1, block_begin()[J]); + } + // Alternative: + // std::copy(op_begin() + I + 1, op_end(), op_begin() + I); + // std::copy(block_begin() + I + 1, block_end(), block_begin() + I); + setOperand(E - 1, nullptr); + block_begin()[E - 1] = nullptr; + setNumHungOffUseOperands(getNumOperands() - 1); + // TODO: Handle single entry MPhi case. + } + + void deleteIncomingBlock(const BasicBlock *BB) { + // Heck, this is O(N^2) and could delete all in O(N). But considering Phis + // should get only a few entries and normally BB incoming once ... fine! + 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."); + // TODO: Handle single entry MPhi case. + } + + 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."); + // TODO: Handle single entry MPhi case. + } + static bool classof(const Value *V) { return V->getValueID() == MemoryPhiVal; } @@ -740,7 +783,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 +797,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 +818,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,10 +88,65 @@ /// Where a mayalias b, *does* require RenameUses be set to true. void insertDef(MemoryDef *Def, bool RenameUses = false); void insertUse(MemoryUse *Use); + /// Update MemorySSA after a loop was cloned, given the loop header block, + /// the loop exit blocks and a 1:1 mapping of all blocks and instructions + /// cloned. This involves duplicating all defs and uses in the cloned blocks + /// and updating phi nodes in exit block successors. + void updateForClonedLoop(BasicBlock *HeaderBlock, + ArrayRef ExitBlocks, + ValueToValueMapTy &VM, + SmallPtrSetImpl &subLoopHeaders, + DominatorTree *DT, + bool IgnoreIncomingWithNoClones = false); + /// 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 values are `From`'s Phi node: MPhi, and 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. + /// |------| |------| + /// | From | | From | + /// | | |------| + /// | | || + /// | | => \/ + /// | | |------| <- Start + /// | | | To | + /// |------| |------| + void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, + Instruction *Start); + /// `From` block was merged into `To`. + /// Move all accesses from `From` to `To` starting at instruction `Start`. + /// `To` has a single successor and `From` has a single predecessor. + /// `From` is about to be deleted. + /// |------| |------| + /// | To | | To | + /// |------| | | + /// || => | | + /// \/ | | + /// |------| | | <- Start + /// | From | | | + /// |------| |------| + void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, + Instruction *Start); + void movePhiToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New); + /// Due to block cloning or block splitting, BB was added additional + /// predecessors beside the previously known single predecessor BB_Pred. + /// Update or insert Phi nodes to make MemorySSA valid again. + void updatePhisWhenAddingBBPredecessors(BasicBlock *BB, BasicBlock *BB_Pred, + DominatorTree *DT); // The below are utility functions. Other than creation of accesses to pass // to insertDef, and removeAccess to remove accesses, you should generally @@ -137,11 +195,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 +221,12 @@ 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); + void updateExitBlocksForClonedLoop(ArrayRef ExitBlocks, + ValueToValueMapTy &VM, 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 @@ -383,6 +383,308 @@ } } +void MemorySSAUpdater::updateForClonedLoop( + BasicBlock *HeaderBlock, ArrayRef ExitBlocks, + ValueToValueMapTy &VMap, SmallPtrSetImpl &subLoopHeaders, + DominatorTree *DT, 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 = cast(VMap[Insn]); + 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 = cast(VMap[Insn]); + MemoryAccess *NewUse = MSSA->createDefinedAccess( + NewInsn, GetNewDefiningAccess(MU->getDefiningAccess()), MU); + MSSA->insertIntoListsForBlock(NewUse, NewBB, MemorySSA::End); + } + } + }; + + std::function &)> + ProcessBlock; + auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) { + if (!Phi) + return; + 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); + } + } + }; + + ProcessBlock = [&](BasicBlock *BB, SmallPtrSetImpl &Processed) { + if (Processed.count(BB)) + return; + Processed.insert(BB); + + BasicBlock *NewBlock = dyn_cast_or_null(VMap[BB]); + if (!NewBlock) + return; + + // Add MemoryPhi. + MemoryPhi *MPhi = MSSA->getMemoryAccess(BB); + MemoryPhi *NewPhi; + if (MPhi) { + NewPhi = MSSA->createMemoryPhi(NewBlock); + MPhiMap[MPhi] = NewPhi; + } + + // Process all predecessors if BB is not a Loop Header + if (!subLoopHeaders.count(BB)) + for (pred_iterator Pi = pred_begin(BB), Pe = pred_end(BB); Pi != Pe; ++Pi) + ProcessBlock(*Pi, Processed); + + // Update Uses and Defs. + CloneUsesAndDefs(BB, NewBlock); + + // Process successors. Can be pruned to "if not an exit block". + for (succ_iterator Si = succ_begin(BB), Se = succ_end(BB); Si != Se; ++Si) + ProcessBlock(*Si, Processed); + + // Update incoming for NewPhi + if (MPhi) + FixPhiIncomingValues(MPhi, NewPhi); + }; + + // Process all blocks starting with the HeaderBlock + SmallPtrSet Processed; + ProcessBlock(HeaderBlock, Processed); + + // Split this method to call update exit blocks later in user code, if DT + // needs update inbetween. + updateExitBlocksForClonedLoop(ExitBlocks, VMap, DT); +} + +void MemorySSAUpdater::updateExitBlocksForClonedLoop( + ArrayRef ExitBlocks, ValueToValueMapTy &VMap, + DominatorTree *DT) { + // Update/insert phis in all successors of exit blocks. + for (unsigned It = 0, E = ExitBlocks.size(); It != E; ++It) { + BasicBlock *Exit = ExitBlocks[It]; + // SimpleLoopUnswitch does not clone all exit blocks. + if (!VMap[Exit]) + continue; + BasicBlock *NewExit = cast(VMap[Exit]); + BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); + updatePhisWhenAddingBBPredecessors(ExitSucc, Exit, DT); + } +} + +void MemorySSAUpdater::replaceDefToFixDomination(MemoryAccess *ToReplace, + MemoryAccess *ReplaceWith, + DominatorTree *DT) { + assert((!isa(ToReplace) && !isa(ReplaceWith)) && + "Must replace a definition with another definition"); + 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 to a block with no MemoryPhi"); + MemoryAccess *IncomingVal = + cast(MPhi->getIncomingValueForBlock(OldIncoming)); + MPhi->deleteIncomingBlock(OldIncoming); + + MemoryPhi *NewPhi = MSSA->createMemoryPhi(To); + NewPhi->addIncoming(IncomingVal, NewIncoming); + NewPhi->addIncoming(MPhi, From); +} + +void MemorySSAUpdater::updatePhisWhenAddingBBPredecessors(BasicBlock *BB, + BasicBlock *P1, + 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); + }; + + auto replaceUsesInBB = [&](MemoryAccess *MA, BasicBlock *BB, + MemoryAccess *New) { + Value::use_iterator UI = MA->use_begin(), E = MA->use_end(); + for (; UI != E;) { + Use &U = *UI; + ++UI; + auto *Usr = dyn_cast(U.getUser()); + if (Usr && Usr->getBlock() == BB) + U.set(New); + } + }; + + SmallPtrSet Seen; + SmallVector WorklistBB; + SmallVector WorklistP; + WorklistBB.push_back(BB); + WorklistP.push_back(P1); + MemoryAccess *DefReplace = GetLastDef(P1); + + auto addSuccToWorklist = [&](BasicBlock *BB_arg) { + succ_iterator Si = succ_begin(BB_arg), Se = succ_end(BB_arg); + for (; Si != Se; ++Si) { + BasicBlock *Succ = *Si; + if (Seen.count(Succ)) + continue; + WorklistBB.push_back(Succ); + WorklistP.push_back(BB_arg); + } + }; + + // Walk CFG and replace uses of DefReplace while inserting Phi nodes. + // Walk stops on a path when hitting a block with a Phi node. + for (unsigned Witer = 0; Witer < WorklistBB.size(); ++Witer) { + BB = WorklistBB[Witer]; + P1 = WorklistP[Witer]; + if (Seen.count(BB)) + continue; + Seen.insert(BB); + + MemoryAccess *DefP1 = GetLastDef(P1); + assert(DefP1 != nullptr && "Unable to find last definition of pred."); + + if (BB->getSinglePredecessor()) { + replaceUsesInBB(DefReplace, BB, DefP1); + addSuccToWorklist(BB); + continue; + } + + MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB); + if (NewPhi) { + // Update existing Phi to have incoming value from P1 the latest Def in + // P1. This happens due to the worklist approach, where a Phi was probably + // added in P1 and now that Phi is the new incoming value DefP1. + // TODO: A hash of would help avoid the repetative + // GetLastDef calls. + NewPhi->setIncomingValue(NewPhi->getBasicBlockIndex(P1), DefP1); + continue; + } + + MemoryAccess *DefOthers = nullptr; + for (pred_iterator Pi = pred_begin(BB), Pe = pred_end(BB); Pi != Pe; ++Pi) + if (*Pi != P1) { + DefOthers = GetLastDef(*Pi); + break; + } + assert(DefOthers != nullptr && "Unable to find last definition."); + + if (DefP1 == DefOthers) + continue; + + // Create MemoryPhi + NewPhi = MSSA->createMemoryPhi(BB); + replaceUsesInBB(DefReplace, BB, NewPhi); + NewPhi->addIncoming(DefP1, P1); + for (pred_iterator Pi = pred_begin(BB), Pe = pred_end(BB); Pi != Pe; ++Pi) + if (*Pi != P1) + NewPhi->addIncoming(DefOthers, *Pi); + addSuccToWorklist(BB); + } +} + // Move What before Where in the MemorySSA IR. template void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB, @@ -409,6 +711,81 @@ 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); +} + +void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, + Instruction *Start) { + assert(From->getSinglePredecessor() != To && + "From block is expected to have a single predecessor (To)."); + assert(To->getSingleSuccessor() != From && + "To block is expected to have a single successor (From)."); + moveAllAccesses(From, To, Start, MemorySSA::End); +} + +// 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(); // To->begin(); + while (StartSearch != To->end()) { + FirstInNew = MSSA->getMemoryAccess(&*StartSearch); + if (FirstInNew) + break; + ++StartSearch; + } + if (FirstInNew) { + // TODO: test throughly: + 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(); + } + } + } + + // Update MemoryPhis in all successors to replace incoming From with To. + SmallPtrSet Seen; + SmallVector Worklist; + Worklist.push_back(To); + while (!Worklist.empty()) { + BasicBlock *FixSuccPhis = Worklist.back(); + Worklist.pop_back(); + // TODO: make_range + succ_iterator Si = succ_begin(FixSuccPhis), Se = succ_end(FixSuccPhis); + for (; Si != Se; ++Si) { + BasicBlock *Succ = *Si; + // TODO: move after adding to Worklist? Or simplify entirely!! + Seen.insert(Succ); + if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ)) + MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), FixSuccPhis); + else if (!Seen.count(Succ)) + Worklist.push_back(Succ); + } + } +} + // Move What before Where in the MemorySSA IR. void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) { moveTo(What, Where->getBlock(), Where->getIterator()); @@ -424,6 +801,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) { @@ -486,6 +871,49 @@ MSSA->removeFromLists(MA); } +void MemorySSAUpdater::removeBlocks( + const SmallPtrSetImpl &DeadBlocks) { + for (BasicBlock *BB : DeadBlocks) { + // First delete all memory accesses in the block (and their uses) + 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 (!DeadBlocks.count(User->getBlock())) { + // If user won't be deleted, it must be a MemoryPhi losing a value. + MemoryPhi *MP = dyn_cast(User); + assert(MP && "User of deleted access must be a MemoryPhi"); + MP->deleteIncomingValue(MA); + } else { + // 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); + } + + // Now delete all uses of BB in MemoryPhis. + TerminatorInst *TI = BB->getTerminator(); + if (!TI) + continue; + for (BasicBlock *Succ : TI->successors()) { + if (!DeadBlocks.count(Succ)) + if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) + MP->deleteIncomingBlock(BB); + } + } +} + MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB( Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point) {