Index: include/llvm/Analysis/MemorySSA.h =================================================================== --- include/llvm/Analysis/MemorySSA.h +++ include/llvm/Analysis/MemorySSA.h @@ -754,7 +754,9 @@ InsertionPlace); void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator); - MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); + MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *, + bool IsKnownDef = false, + bool IsKnownUse = false); private: class CachingWalker; @@ -774,7 +776,8 @@ void markUnreachableAsLiveOnEntry(BasicBlock *BB); bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const; MemoryPhi *createMemoryPhi(BasicBlock *BB); - MemoryUseOrDef *createNewAccess(Instruction *); + MemoryUseOrDef *createNewAccess(Instruction *, bool IsKnownDef = false, + bool IsKnownUse = false); 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 @@ -44,6 +44,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" @@ -56,6 +57,8 @@ class LLVMContext; class raw_ostream; +using ValueToValueMapTy = ValueMap; + class MemorySSAUpdater { private: MemorySSA *MSSA; @@ -83,10 +86,19 @@ /// Where a mayalias b, *does* require RenameUses be set to true. void insertDef(MemoryDef *Def, bool RenameUses = false); void insertUse(MemoryUse *Use); + void insertAccessesFromMap(BasicBlock *HeaderBlock, + ArrayRef ExitBlocks, + ValueToValueMapTy &VM, DominatorTree *DT); + void moveInBulk(BasicBlock *From, BasicBlock *To, Instruction *Start, + MemorySSA::InsertionPlace Where); void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where); + void updatePhisForSplitBlock(BasicBlock *Old, BasicBlock *New, + ArrayRef Preds); + void insertPhisIfNeeded(BasicBlock *BB, BasicBlock *BB_Predecessor, + DominatorTree *DT); // The below are utility functions. Other than creation of accesses to pass // to insertDef, and removeAccess to remove accesses, you should generally Index: lib/Analysis/MemorySSA.cpp =================================================================== --- lib/Analysis/MemorySSA.cpp +++ lib/Analysis/MemorySSA.cpp @@ -1514,9 +1514,11 @@ } MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I, - MemoryAccess *Definition) { + MemoryAccess *Definition, + bool IsKnownDef, + bool IsKnownUse) { assert(!isa(I) && "Cannot create a defined access for a PHI"); - MemoryUseOrDef *NewAccess = createNewAccess(I); + MemoryUseOrDef *NewAccess = createNewAccess(I, IsKnownDef, IsKnownUse); assert( NewAccess != nullptr && "Tried to create a memory access for a non-memory touching instruction"); @@ -1539,7 +1541,7 @@ } /// \brief Helper function to create new memory accesses -MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) { +MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I, bool Def, bool Use) { // 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 @@ -1548,18 +1550,22 @@ 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); + if (Def || Use) + assert(!(Def && Use) && "MemoryAccess cannot be both Use and Def"); + 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 @@ -375,6 +375,225 @@ } } +void MemorySSAUpdater::insertAccessesFromMap(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()), + /*IsKnownDef=*/true, + /*IsKnownUse=*/false); + 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()), + /*IsKnownDef=*/false, + /*IsKnownUse=*/true); + 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); + insertPhisIfNeeded(ExitSucc, Exit, DT); + } +} + +void MemorySSAUpdater::insertPhisIfNeeded(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, @@ -392,6 +611,63 @@ insertUse(cast(What)); } +// All accesses in To used to be in From. Update access lists. +void MemorySSAUpdater::moveInBulk(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 Old with New. + 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; + 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()); @@ -407,6 +683,27 @@ return moveTo(What, BB, Where); } +void MemorySSAUpdater::updatePhisForSplitBlock(BasicBlock *Old, BasicBlock *New, + ArrayRef Preds) { + if (Preds.empty()) + return; + MemoryPhi *Phi = MSSA->getMemoryAccess(Old); + if (!Phi) + return; + MemoryPhi *NewPhi = MSSA->createMemoryPhi(New); + for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) { + MemoryAccess *IncomingAccess = Phi->getIncomingValue(It); + BasicBlock *IncBB = Phi->getIncomingBlock(It); + NewPhi->addIncoming(IncomingAccess, IncBB); + } + Phi->replaceAllUsesWith(NewPhi); + removeMemoryAccess(Phi); + + // Alternative? + // removeFromLists(Phi, ShouldDelete=false) + // insertIntoListsForBlock(Phi, New, MemorySSA::Beginning); +} + /// \brief If all arguments of a MemoryPHI are defined by the same incoming /// argument, return that argument. static MemoryAccess *onlySingleValue(MemoryPhi *MP) {