Index: llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h +++ llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h @@ -685,6 +685,11 @@ // 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); + // Rename the dominator tree branch rooted at BB. + void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, + SmallPtrSetImpl &Visited) { + renamePass(DT->getNode(BB), IncomingVal, Visited, true, true); + } private: class CachingWalker; @@ -708,12 +713,13 @@ MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); void removeFromLookups(MemoryAccess *); void removeFromLists(MemoryAccess *, bool ShouldDelete = true); - void placePHINodes(const SmallPtrSetImpl &, const DenseMap &); - MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *); + MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool); + void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool); void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, - SmallPtrSet &Visited); + SmallPtrSetImpl &Visited, + bool SkipVisited = false, bool RenameAllUses = false); AccessList *getOrCreateAccessList(const BasicBlock *); DefsList *getOrCreateDefsList(const BasicBlock *); void renumberBlock(const BasicBlock *) const; Index: llvm/trunk/include/llvm/Transforms/Utils/MemorySSAUpdater.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/MemorySSAUpdater.h +++ llvm/trunk/include/llvm/Transforms/Utils/MemorySSAUpdater.h @@ -63,12 +63,30 @@ public: MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} - void insertDef(MemoryDef *Def); + // 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 + // is not the case for hoisting or sinking or other forms of code *movement*. + // It *is* the case for straight code insertion. + // For example: + // store a + // if (foo) { } + // load a + // + // Moving the store into the if block, and calling insertDef, does not + // require RenameUses. + // However, changing it to: + // store a + // if (foo) { store b } + // load a + // Where a mayalias b, *does* require RenameUses be set to true. + void insertDef(MemoryDef *Def, bool RenameUses = false); void insertUse(MemoryUse *Use); void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where); + private: // Move What before Where in the MemorySSA IR. template Index: llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp @@ -1116,18 +1116,37 @@ } }; +void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal, + bool RenameAllUses) { + // Pass through values to our successors + for (const BasicBlock *S : successors(BB)) { + auto It = PerBlockAccesses.find(S); + // Rename the phi nodes in our successor block + if (It == PerBlockAccesses.end() || !isa(It->second->front())) + continue; + AccessList *Accesses = It->second.get(); + auto *Phi = cast(&Accesses->front()); + if (RenameAllUses) { + int PhiIndex = Phi->getBasicBlockIndex(BB); + assert(PhiIndex != -1 && "Incomplete phi during partial rename"); + Phi->setIncomingValue(PhiIndex, IncomingVal); + } else + Phi->addIncoming(IncomingVal, BB); + } +} + /// \brief Rename a single basic block into MemorySSA form. /// Uses the standard SSA renaming algorithm. /// \returns The new incoming value. -MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, - MemoryAccess *IncomingVal) { +MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal, + bool RenameAllUses) { auto It = PerBlockAccesses.find(BB); // Skip most processing if the list is empty. if (It != PerBlockAccesses.end()) { AccessList *Accesses = It->second.get(); for (MemoryAccess &L : *Accesses) { if (MemoryUseOrDef *MUD = dyn_cast(&L)) { - if (MUD->getDefiningAccess() == nullptr) + if (MUD->getDefiningAccess() == nullptr || RenameAllUses) MUD->setDefiningAccess(IncomingVal); if (isa(&L)) IncomingVal = &L; @@ -1136,18 +1155,6 @@ } } } - - // Pass through values to our successors - for (const BasicBlock *S : successors(BB)) { - auto It = PerBlockAccesses.find(S); - // Rename the phi nodes in our successor block - if (It == PerBlockAccesses.end() || !isa(It->second->front())) - continue; - AccessList *Accesses = It->second.get(); - auto *Phi = cast(&Accesses->front()); - Phi->addIncoming(IncomingVal, BB); - } - return IncomingVal; } @@ -1156,11 +1163,19 @@ /// We walk the dominator tree in preorder, renaming accesses, and then filling /// in phi nodes in our successors. void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal, - SmallPtrSet &Visited) { + SmallPtrSetImpl &Visited, + bool SkipVisited, bool RenameAllUses) { SmallVector WorkStack; - IncomingVal = renameBlock(Root->getBlock(), IncomingVal); + // Skip everything if we already renamed this block and we are skipping. + // Note: You can't sink this into the if, because we need it to occur + // regardless of whether we skip blocks or not. + bool AlreadyVisited = !Visited.insert(Root->getBlock()).second; + if (SkipVisited && AlreadyVisited) + return; + + IncomingVal = renameBlock(Root->getBlock(), IncomingVal, RenameAllUses); + renameSuccessorPhis(Root->getBlock(), IncomingVal, RenameAllUses); WorkStack.push_back({Root, Root->begin(), IncomingVal}); - Visited.insert(Root->getBlock()); while (!WorkStack.empty()) { DomTreeNode *Node = WorkStack.back().DTN; @@ -1173,8 +1188,20 @@ DomTreeNode *Child = *ChildIt; ++WorkStack.back().ChildIt; BasicBlock *BB = Child->getBlock(); - Visited.insert(BB); - IncomingVal = renameBlock(BB, IncomingVal); + // Note: You can't sink this into the if, because we need it to occur + // regardless of whether we skip blocks or not. + AlreadyVisited = !Visited.insert(BB).second; + if (SkipVisited && AlreadyVisited) { + // We already visited this during our renaming, which can happen when + // being asked to rename multiple blocks. Figure out the incoming val, + // which is the last def. + // Incoming value can only change if there is a block def, and in that + // case, it's the last block def in the list. + if (auto *BlockDefs = getWritableBlockDefs(BB)) + IncomingVal = &*BlockDefs->rbegin(); + } else + IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses); + renameSuccessorPhis(BB, IncomingVal, RenameAllUses); WorkStack.push_back({Child, Child->begin(), IncomingVal}); } } @@ -1891,9 +1918,7 @@ } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -LLVM_DUMP_METHOD void MemorySSA::dump() const { - print(dbgs()); -} +LLVM_DUMP_METHOD void MemorySSA::dump() const { print(dbgs()); } #endif void MemorySSA::verifyMemorySSA() const { @@ -2163,7 +2188,7 @@ } void MemoryAccess::dump() const { - // Cannot completely remove virtual function even in release mode. +// Cannot completely remove virtual function even in release mode. #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) print(dbgs()); dbgs() << "\n"; Index: llvm/trunk/lib/Transforms/Utils/MemorySSAUpdater.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/MemorySSAUpdater.cpp +++ llvm/trunk/lib/Transforms/Utils/MemorySSAUpdater.cpp @@ -234,7 +234,7 @@ // Then, we update the defs below us (and any new phi nodes) in the graph to // point to the correct new defs, to ensure we only have one variable, and no // disconnected stores. -void MemorySSAUpdater::insertDef(MemoryDef *MD) { +void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) { InsertedPHIs.clear(); // See if we had a local def, and if not, go hunting. @@ -287,6 +287,24 @@ // Put any new phis on the fixup list, and process them FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end()); } + // Now that all fixups are done, rename all uses if we are asked. + if (RenameUses) { + SmallPtrSet Visited; + BasicBlock *StartBlock = MD->getBlock(); + // We are guaranteed there is a def in the block, because we just got it + // handed to us in this function. + MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin(); + // Convert to incoming value if it's a memorydef. A phi *is* already an + // incoming value. + if (auto *MD = dyn_cast(FirstDef)) + FirstDef = MD->getDefiningAccess(); + + MSSA->renamePass(MD->getBlock(), FirstDef, Visited); + // We just inserted a phi into this block, so the incoming value will become + // the phi anyway, so it does not matter what we pass. + for (auto *MP : InsertedPHIs) + MSSA->renamePass(MP->getBlock(), nullptr, Visited); + } } void MemorySSAUpdater::fixupDefs(const SmallVectorImpl &Vars) { Index: llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp @@ -158,7 +158,7 @@ StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg); MemoryAccess *LeftStoreAccess = MSSA.createMemoryAccessInBB( LeftStore, nullptr, Left, MemorySSA::Beginning); - Updater.insertDef(cast(LeftStoreAccess)); + Updater.insertDef(cast(LeftStoreAccess), false); // We don't touch existing loads, so we need to create a new one to get a phi // Add the second load B.SetInsertPoint(Merge, Merge->begin()); @@ -183,7 +183,11 @@ StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg); MemoryAccess *SecondEntryStoreAccess = MSSA.createMemoryAccessInBB( SecondEntryStore, nullptr, Entry, MemorySSA::End); - Updater.insertDef(cast(SecondEntryStoreAccess)); + // Insert it twice just to test renaming + Updater.insertDef(cast(SecondEntryStoreAccess), false); + EXPECT_NE(FirstLoadAccess->getDefiningAccess(), MergePhi); + Updater.insertDef(cast(SecondEntryStoreAccess), true); + EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), MergePhi); // and make sure the phi below it got updated, despite being blocks away MergePhi = dyn_cast(SecondLoadAccess->getDefiningAccess()); EXPECT_NE(MergePhi, nullptr);