Index: include/llvm/Analysis/MemorySSA.h =================================================================== --- include/llvm/Analysis/MemorySSA.h +++ include/llvm/Analysis/MemorySSA.h @@ -740,7 +740,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 +754,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 +775,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 &, const DenseMap &); 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,50 @@ /// 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, 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. + /// |------| |------| + /// | 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 @@ -142,6 +185,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 * Index: lib/Analysis/MemorySSA.cpp =================================================================== --- lib/Analysis/MemorySSA.cpp +++ lib/Analysis/MemorySSA.cpp @@ -1481,8 +1481,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); @@ -1498,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"); @@ -1523,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 @@ -1532,18 +1541,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,222 @@ } } +void MemorySSAUpdater::updateForClonedLoop(BasicBlock *HeaderBlock, + ArrayRef ExitBlocks, + ValueToValueMapTy &VMap, + DominatorTree *DT) { + + // LoopBlocks include ExitBlocks. Traverse from HeaderBlock. + // ClonedBlocks are clones of LoopBlocks (including ExitBlocks) + // VMap[LoopBlocks[i]] = ClonedBlocks[j] + // LoopBlocks[0] = NewPreheader, followed by L->block_begin(), L->block_end() + // Update Phi nodes in exit block successors. + + 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; + 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; + 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; + + 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 the Loop Header + if (BB != HeaderBlock) + for (pred_iterator Si = pred_begin(BB), Se = pred_end(BB); Si != Se; ++Si) + ProcessBlock(*Si, 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); + + // TODO: Separate processing of ExitBlocks? + // Update/insert phis in all successors of exit blocks. + for (unsigned It = 0, E = ExitBlocks.size(); It != E; ++It) { + BasicBlock *Exit = ExitBlocks[It]; + BasicBlock *NewExit = cast(VMap[Exit]); + BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); + updatePhisWhenAddingBBPredecessors(ExitSucc, Exit, DT); + } +} + +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) { + 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); + + for (unsigned Witer = 0; Witer < WorklistBB.size(); ++Witer) { + BB = WorklistBB[Witer]; + P1 = WorklistP[Witer]; + if (Seen.count(BB)) + continue; + Seen.insert(BB); + + if (BB->getSinglePredecessor()) + continue; + + MemoryAccess *DefP1 = GetLastDef(P1); + assert(DefP1 != nullptr && "Unable to find last definition of pred."); + + MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB); + if (NewPhi) { + 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) { + // 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); + + succ_iterator Si = succ_begin(BB), Se = succ_end(BB); + for (; Si != Se; ++Si) { + BasicBlock *Succ = *Si; + if (Seen.count(Succ)) // redundant with above, earlier pruning..maybe? + continue; + WorklistBB.push_back(Succ); + WorklistP.push_back(BB); + } + } + } +} + // Move What before Where in the MemorySSA IR. template void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB, @@ -409,6 +625,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 +715,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) {