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 @@ -593,55 +593,6 @@ return getWritableBlockDefs(BB); } - /// \brief Create an empty MemoryPhi in MemorySSA for a given basic block. - /// Only one MemoryPhi for a block exists at a time, so this function will - /// assert if you try to create one where it already exists. - MemoryPhi *createMemoryPhi(BasicBlock *BB); - - enum InsertionPlace { Beginning, End }; - - /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block, - /// with a specified clobbering definition. - /// - /// Returns the new MemoryAccess. - /// This should be called when a memory instruction is created that is being - /// used to replace an existing memory instruction. It will *not* create PHI - /// nodes, or verify the clobbering definition. The insertion place is used - /// solely to determine where in the memoryssa access lists the instruction - /// will be placed. The caller is expected to keep ordering the same as - /// instructions. - /// It will return the new MemoryAccess. - /// Note: If a MemoryAccess already exists for I, this function will make it - /// inaccessible and it *must* have removeMemoryAccess called on it. - MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, - const BasicBlock *BB, - InsertionPlace Point); - - /// \brief Create a MemoryAccess in MemorySSA before or after an existing - /// MemoryAccess. - /// - /// Returns the new MemoryAccess. - /// This should be called when a memory instruction is created that is being - /// used to replace an existing memory instruction. It will *not* create PHI - /// nodes, or verify the clobbering definition. - /// - /// Note: If a MemoryAccess already exists for I, this function will make it - /// inaccessible and it *must* have removeMemoryAccess called on it. - MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, - MemoryAccess *Definition, - MemoryUseOrDef *InsertPt); - MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, - MemoryAccess *Definition, - MemoryAccess *InsertPt); - - /// \brief Remove a MemoryAccess from MemorySSA, including updating all - /// definitions and uses. - /// This should be called when a memory instruction that has a MemoryAccess - /// associated with it is erased from the program. For example, if a store or - /// load is simply erased (not replaced), removeMemoryAccess should be called - /// on the MemoryAccess for that store/load. - void removeMemoryAccess(MemoryAccess *); - /// \brief Given two memory accesses in the same basic block, determine /// whether MemoryAccess \p A dominates MemoryAccess \p B. bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const; @@ -658,6 +609,10 @@ /// all uses, uses appear in the right places). This is used by unit tests. void verifyMemorySSA() const; + /// Used in various insertion functions to specify whether we are talking + /// about the beginning or end of a block. + enum InsertionPlace { Beginning, End }; + protected: // Used by Memory SSA annotater, dumpers, and wrapper pass friend class MemorySSAAnnotatedWriter; @@ -680,9 +635,10 @@ return It == PerBlockDefs.end() ? nullptr : It->second.get(); } - // This is used by the updater to perform the internal memoryssa machinations - // for moves. It does not always leave the IR in a correct state, and relies - // on the updater to fixup what it breaks, so it is not public. + // These is used by the updater to perform various internal MemorySSA + // machinsations. They do not always leave the IR in a correct state, and + // 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); // Rename the dominator tree branch rooted at BB. @@ -690,6 +646,13 @@ SmallPtrSetImpl &Visited) { renamePass(DT->getNode(BB), IncomingVal, Visited, true, true); } + void removeFromLookups(MemoryAccess *); + void removeFromLists(MemoryAccess *, bool ShouldDelete = true); + void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, + InsertionPlace); + void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, + AccessList::iterator); + MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); private: class CachingWalker; @@ -708,11 +671,9 @@ void computeDomLevels(DenseMap &DomLevels); void markUnreachableAsLiveOnEntry(BasicBlock *BB); bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const; + MemoryPhi *createMemoryPhi(BasicBlock *BB); MemoryUseOrDef *createNewAccess(Instruction *); - MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *); MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); - void removeFromLookups(MemoryAccess *); - void removeFromLists(MemoryAccess *, bool ShouldDelete = true); void placePHINodes(const SmallPtrSetImpl &, const DenseMap &); MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool); @@ -723,10 +684,6 @@ AccessList *getOrCreateAccessList(const BasicBlock *); DefsList *getOrCreateDefsList(const BasicBlock *); void renumberBlock(const BasicBlock *) const; - void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, - InsertionPlace); - void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, - AccessList::iterator); AliasAnalysis *AA; DominatorTree *DT; Function &F; 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,23 +63,23 @@ public: MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} - // 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. + /// 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); @@ -87,11 +87,58 @@ void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where); + // 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 + // the edge cases right, and the above calls already operate in near-optimal + // time bounds. + + /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block, + /// with a specified clobbering definition. + /// + /// Returns the new MemoryAccess. + /// This should be called when a memory instruction is created that is being + /// used to replace an existing memory instruction. It will *not* create PHI + /// nodes, or verify the clobbering definition. The insertion place is used + /// solely to determine where in the memoryssa access lists the instruction + /// will be placed. The caller is expected to keep ordering the same as + /// instructions. + /// It will return the new MemoryAccess. + /// Note: If a MemoryAccess already exists for I, this function will make it + /// inaccessible and it *must* have removeMemoryAccess called on it. + MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, + const BasicBlock *BB, + MemorySSA::InsertionPlace Point); + + /// \brief Create a MemoryAccess in MemorySSA before or after an existing + /// MemoryAccess. + /// + /// Returns the new MemoryAccess. + /// This should be called when a memory instruction is created that is being + /// used to replace an existing memory instruction. It will *not* create PHI + /// nodes, or verify the clobbering definition. + /// + /// Note: If a MemoryAccess already exists for I, this function will make it + /// inaccessible and it *must* have removeMemoryAccess called on it. + MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, + MemoryAccess *Definition, + MemoryUseOrDef *InsertPt); + MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, + MemoryAccess *Definition, + MemoryAccess *InsertPt); + + /// \brief Remove a MemoryAccess from MemorySSA, including updating all + /// definitions and uses. + /// This should be called when a memory instruction that has a MemoryAccess + /// associated with it is erased from the program. For example, if a store or + /// load is simply erased (not replaced), removeMemoryAccess should be called + /// on the MemoryAccess for that store/load. + void removeMemoryAccess(MemoryAccess *); + private: // Move What before Where in the MemorySSA IR. template - void moveTo(MemoryUseOrDef *What, BasicBlock *BB, - WhereType Where); + void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); MemoryAccess *getPreviousDef(MemoryAccess *); MemoryAccess *getPreviousDefInBlock(MemoryAccess *); MemoryAccess *getPreviousDefFromEnd(BasicBlock *); Index: llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp +++ llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp @@ -33,6 +33,7 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/MemorySSA.h" +#include "llvm/Transforms/Utils/MemorySSAUpdater.h" #include using namespace llvm; using namespace llvm::PatternMatch; @@ -253,6 +254,7 @@ DominatorTree &DT; AssumptionCache &AC; MemorySSA *MSSA; + std::unique_ptr MSSAUpdater; typedef RecyclingAllocator< BumpPtrAllocator, ScopedHashTableVal> AllocatorTy; typedef ScopedHashTable, @@ -315,7 +317,9 @@ /// \brief Set up the EarlyCSE runner for a particular function. EarlyCSE(const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI, DominatorTree &DT, AssumptionCache &AC, MemorySSA *MSSA) - : TLI(TLI), TTI(TTI), DT(DT), AC(AC), MSSA(MSSA), CurrentGeneration(0) {} + : TLI(TLI), TTI(TTI), DT(DT), AC(AC), MSSA(MSSA), + MSSAUpdater(make_unique(MSSA)), CurrentGeneration(0) { + } bool run(); @@ -517,7 +521,7 @@ if (MemoryPhi *MP = dyn_cast(U)) PhisToCheck.push_back(MP); - MSSA->removeMemoryAccess(WI); + MSSAUpdater->removeMemoryAccess(WI); for (MemoryPhi *MP : PhisToCheck) { MemoryAccess *FirstIn = MP->getIncomingValue(0); Index: llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp +++ llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp @@ -27,6 +27,7 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/MemorySSA.h" +#include "llvm/Transforms/Utils/MemorySSAUpdater.h" using namespace llvm; @@ -201,11 +202,13 @@ public: GVNHoist(DominatorTree *DT, AliasAnalysis *AA, MemoryDependenceResults *MD, MemorySSA *MSSA, bool OptForMinSize) - : DT(DT), AA(AA), MD(MD), MSSA(MSSA), OptForMinSize(OptForMinSize), - HoistingGeps(OptForMinSize), HoistedCtr(0) { - // Hoist as far as possible when optimizing for code-size. - if (OptForMinSize) - MaxNumberOfBBSInPath = -1; + : DT(DT), AA(AA), MD(MD), MSSA(MSSA), + MSSAUpdater(make_unique(MSSA)), + OptForMinSize(OptForMinSize), HoistingGeps(OptForMinSize), + HoistedCtr(0) { + // Hoist as far as possible when optimizing for code-size. + if (OptForMinSize) + MaxNumberOfBBSInPath = -1; } bool run(Function &F) { @@ -251,6 +254,7 @@ AliasAnalysis *AA; MemoryDependenceResults *MD; MemorySSA *MSSA; + std::unique_ptr MSSAUpdater; const bool OptForMinSize; const bool HoistingGeps; DenseMap DFSNumber; @@ -817,9 +821,9 @@ // legal when the ld/st is not moved past its current definition. MemoryAccess *Def = OldMemAcc->getDefiningAccess(); NewMemAcc = - MSSA->createMemoryAccessInBB(Repl, Def, HoistPt, MemorySSA::End); + MSSAUpdater->createMemoryAccessInBB(Repl, Def, HoistPt, MemorySSA::End); OldMemAcc->replaceAllUsesWith(NewMemAcc); - MSSA->removeMemoryAccess(OldMemAcc); + MSSAUpdater->removeMemoryAccess(OldMemAcc); } } @@ -858,7 +862,7 @@ // Update the uses of the old MSSA access with NewMemAcc. MemoryAccess *OldMA = MSSA->getMemoryAccess(I); OldMA->replaceAllUsesWith(NewMemAcc); - MSSA->removeMemoryAccess(OldMA); + MSSAUpdater->removeMemoryAccess(OldMA); } Repl->andIRFlags(I); @@ -880,7 +884,7 @@ auto In = Phi->incoming_values(); if (all_of(In, [&](Use &U) { return U == NewMemAcc; })) { Phi->replaceAllUsesWith(NewMemAcc); - MSSA->removeMemoryAccess(Phi); + MSSAUpdater->removeMemoryAccess(Phi); } } } Index: llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp @@ -1691,37 +1691,6 @@ return NewAccess; } -MemoryAccess *MemorySSA::createMemoryAccessInBB(Instruction *I, - MemoryAccess *Definition, - const BasicBlock *BB, - InsertionPlace Point) { - MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - insertIntoListsForBlock(NewAccess, BB, Point); - return NewAccess; -} - -MemoryUseOrDef *MemorySSA::createMemoryAccessBefore(Instruction *I, - MemoryAccess *Definition, - MemoryUseOrDef *InsertPt) { - assert(I->getParent() == InsertPt->getBlock() && - "New and old access must be in the same block"); - MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - insertIntoListsBefore(NewAccess, InsertPt->getBlock(), - InsertPt->getIterator()); - return NewAccess; -} - -MemoryUseOrDef *MemorySSA::createMemoryAccessAfter(Instruction *I, - MemoryAccess *Definition, - MemoryAccess *InsertPt) { - assert(I->getParent() == InsertPt->getBlock() && - "New and old access must be in the same block"); - MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - insertIntoListsBefore(NewAccess, InsertPt->getBlock(), - ++(InsertPt->getIterator())); - return NewAccess; -} - /// \brief Helper function to create new memory accesses MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) { // The assume intrinsic has a control dependency which we model by claiming @@ -1754,33 +1723,6 @@ return MUD; } -MemoryAccess *MemorySSA::findDominatingDef(BasicBlock *UseBlock, - enum InsertionPlace Where) { - // Handle the initial case - if (Where == Beginning) - // The only thing that could define us at the beginning is a phi node - if (MemoryPhi *Phi = getMemoryAccess(UseBlock)) - return Phi; - - DomTreeNode *CurrNode = DT->getNode(UseBlock); - // Need to be defined by our dominator - if (Where == Beginning) - CurrNode = CurrNode->getIDom(); - Where = End; - while (CurrNode) { - auto It = PerBlockAccesses.find(CurrNode->getBlock()); - if (It != PerBlockAccesses.end()) { - auto &Accesses = It->second; - for (MemoryAccess &RA : reverse(*Accesses)) { - if (isa(RA) || isa(RA)) - return &RA; - } - } - CurrNode = CurrNode->getIDom(); - } - return LiveOnEntryDef.get(); -} - /// \brief Returns true if \p Replacer dominates \p Replacee . bool MemorySSA::dominatesUse(const MemoryAccess *Replacer, const MemoryAccess *Replacee) const { @@ -1798,20 +1740,6 @@ return true; } -/// \brief If all arguments of a MemoryPHI are defined by the same incoming -/// argument, return that argument. -static MemoryAccess *onlySingleValue(MemoryPhi *MP) { - MemoryAccess *MA = nullptr; - - for (auto &Arg : MP->operands()) { - if (!MA) - MA = cast(Arg); - else if (MA != Arg) - return nullptr; - } - return MA; -} - /// \brief Properly remove \p MA from all of MemorySSA's lookup tables. void MemorySSA::removeFromLookups(MemoryAccess *MA) { assert(MA->use_empty() && @@ -1865,53 +1793,6 @@ PerBlockAccesses.erase(AccessIt); } -void MemorySSA::removeMemoryAccess(MemoryAccess *MA) { - assert(!isLiveOnEntryDef(MA) && "Trying to remove the live on entry def"); - // We can only delete phi nodes if they have no uses, or we can replace all - // uses with a single definition. - MemoryAccess *NewDefTarget = nullptr; - if (MemoryPhi *MP = dyn_cast(MA)) { - // Note that it is sufficient to know that all edges of the phi node have - // the same argument. If they do, by the definition of dominance frontiers - // (which we used to place this phi), that argument must dominate this phi, - // and thus, must dominate the phi's uses, and so we will not hit the assert - // below. - NewDefTarget = onlySingleValue(MP); - assert((NewDefTarget || MP->use_empty()) && - "We can't delete this memory phi"); - } else { - NewDefTarget = cast(MA)->getDefiningAccess(); - } - - // Re-point the uses at our defining access - if (!isa(MA) && !MA->use_empty()) { - // Reset optimized on users of this store, and reset the uses. - // A few notes: - // 1. This is a slightly modified version of RAUW to avoid walking the - // uses twice here. - // 2. If we wanted to be complete, we would have to reset the optimized - // flags on users of phi nodes if doing the below makes a phi node have all - // the same arguments. Instead, we prefer users to removeMemoryAccess those - // phi nodes, because doing it here would be N^3. - if (MA->hasValueHandle()) - ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget); - // Note: We assume MemorySSA is not used in metadata since it's not really - // part of the IR. - - while (!MA->use_empty()) { - Use &U = *MA->use_begin(); - if (MemoryUse *MU = dyn_cast(U.getUser())) - MU->resetOptimized(); - U.set(NewDefTarget); - } - } - - // The call below to erase will destroy MA, so we can't change the order we - // are doing things here - removeFromLookups(MA); - removeFromLists(MA); -} - void MemorySSA::print(raw_ostream &OS) const { MemorySSAAnnotatedWriter Writer(this); F.print(OS, &Writer); Index: llvm/trunk/lib/Transforms/Utils/MemorySSAUpdater.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/MemorySSAUpdater.cpp +++ llvm/trunk/lib/Transforms/Utils/MemorySSAUpdater.cpp @@ -189,7 +189,7 @@ return MSSA->getLiveOnEntryDef(); if (Phi) { Phi->replaceAllUsesWith(Same); - MSSA->removeMemoryAccess(Phi); + removeMemoryAccess(Phi); } // We should only end up recursing in case we replaced something, in which @@ -401,4 +401,94 @@ MemorySSA::InsertionPlace Where) { return moveTo(What, BB, Where); } + +/// \brief If all arguments of a MemoryPHI are defined by the same incoming +/// argument, return that argument. +static MemoryAccess *onlySingleValue(MemoryPhi *MP) { + MemoryAccess *MA = nullptr; + + for (auto &Arg : MP->operands()) { + if (!MA) + MA = cast(Arg); + else if (MA != Arg) + return nullptr; + } + return MA; +} +void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) { + assert(!MSSA->isLiveOnEntryDef(MA) && + "Trying to remove the live on entry def"); + // We can only delete phi nodes if they have no uses, or we can replace all + // uses with a single definition. + MemoryAccess *NewDefTarget = nullptr; + if (MemoryPhi *MP = dyn_cast(MA)) { + // Note that it is sufficient to know that all edges of the phi node have + // the same argument. If they do, by the definition of dominance frontiers + // (which we used to place this phi), that argument must dominate this phi, + // and thus, must dominate the phi's uses, and so we will not hit the assert + // below. + NewDefTarget = onlySingleValue(MP); + assert((NewDefTarget || MP->use_empty()) && + "We can't delete this memory phi"); + } else { + NewDefTarget = cast(MA)->getDefiningAccess(); + } + + // Re-point the uses at our defining access + if (!isa(MA) && !MA->use_empty()) { + // Reset optimized on users of this store, and reset the uses. + // A few notes: + // 1. This is a slightly modified version of RAUW to avoid walking the + // uses twice here. + // 2. If we wanted to be complete, we would have to reset the optimized + // flags on users of phi nodes if doing the below makes a phi node have all + // the same arguments. Instead, we prefer users to removeMemoryAccess those + // phi nodes, because doing it here would be N^3. + if (MA->hasValueHandle()) + ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget); + // Note: We assume MemorySSA is not used in metadata since it's not really + // part of the IR. + + while (!MA->use_empty()) { + Use &U = *MA->use_begin(); + if (MemoryUse *MU = dyn_cast(U.getUser())) + MU->resetOptimized(); + U.set(NewDefTarget); + } + } + + // The call below to erase will destroy MA, so we can't change the order we + // are doing things here + MSSA->removeFromLookups(MA); + MSSA->removeFromLists(MA); +} + +MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB( + Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, + MemorySSA::InsertionPlace Point) { + MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition); + MSSA->insertIntoListsForBlock(NewAccess, BB, Point); + return NewAccess; +} + +MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore( + Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) { + assert(I->getParent() == InsertPt->getBlock() && + "New and old access must be in the same block"); + MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition); + MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(), + InsertPt->getIterator()); + return NewAccess; +} + +MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter( + Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) { + assert(I->getParent() == InsertPt->getBlock() && + "New and old access must be in the same block"); + MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition); + MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(), + ++InsertPt->getIterator()); + return NewAccess; +} + } // namespace llvm Index: llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp @@ -90,6 +90,7 @@ setupAnalyses(); MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAUpdater Updater(&MSSA); // Add the load B.SetInsertPoint(Merge); LoadInst *LoadInst = B.CreateLoad(PointerArg); @@ -99,8 +100,8 @@ EXPECT_NE(MP, nullptr); // Create the load memory acccess - MemoryUse *LoadAccess = cast( - MSSA.createMemoryAccessInBB(LoadInst, MP, Merge, MemorySSA::Beginning)); + MemoryUse *LoadAccess = cast(Updater.createMemoryAccessInBB( + LoadInst, MP, Merge, MemorySSA::Beginning)); MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); EXPECT_TRUE(isa(DefiningAccess)); MSSA.verifyMemorySSA(); @@ -132,7 +133,7 @@ // Add the store B.SetInsertPoint(Entry, Entry->begin()); StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); - MemoryAccess *EntryStoreAccess = MSSA.createMemoryAccessInBB( + MemoryAccess *EntryStoreAccess = Updater.createMemoryAccessInBB( EntryStore, nullptr, Entry, MemorySSA::Beginning); Updater.insertDef(cast(EntryStoreAccess)); @@ -145,7 +146,7 @@ EXPECT_EQ(MP, nullptr); // Create the load memory access - MemoryUse *FirstLoadAccess = cast(MSSA.createMemoryAccessInBB( + MemoryUse *FirstLoadAccess = cast(Updater.createMemoryAccessInBB( FirstLoad, nullptr, Merge, MemorySSA::Beginning)); Updater.insertUse(FirstLoadAccess); // Should just have a load using the entry access, because it should discover @@ -156,7 +157,7 @@ // Add the store B.SetInsertPoint(Left, Left->begin()); StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg); - MemoryAccess *LeftStoreAccess = MSSA.createMemoryAccessInBB( + MemoryAccess *LeftStoreAccess = Updater.createMemoryAccessInBB( LeftStore, nullptr, Left, MemorySSA::Beginning); Updater.insertDef(cast(LeftStoreAccess), false); // We don't touch existing loads, so we need to create a new one to get a phi @@ -169,7 +170,7 @@ EXPECT_EQ(MP, nullptr); // Create the load memory access - MemoryUse *SecondLoadAccess = cast(MSSA.createMemoryAccessInBB( + MemoryUse *SecondLoadAccess = cast(Updater.createMemoryAccessInBB( SecondLoad, nullptr, Merge, MemorySSA::Beginning)); Updater.insertUse(SecondLoadAccess); // Now the load should be a phi of the entry store and the left store @@ -181,7 +182,7 @@ // Now create a store below the existing one in the entry B.SetInsertPoint(Entry, --Entry->end()); StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg); - MemoryAccess *SecondEntryStoreAccess = MSSA.createMemoryAccessInBB( + MemoryAccess *SecondEntryStoreAccess = Updater.createMemoryAccessInBB( SecondEntryStore, nullptr, Entry, MemorySSA::End); // Insert it twice just to test renaming Updater.insertDef(cast(SecondEntryStoreAccess), false); @@ -223,7 +224,7 @@ // Add the store StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg); MemoryAccess *StoreAccess = - MSSA.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning); + Updater.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning); Updater.insertDef(cast(StoreAccess)); // Add the load @@ -235,7 +236,7 @@ EXPECT_EQ(MP, nullptr); // Create the load memory acccess - MemoryUse *LoadAccess = cast(MSSA.createMemoryAccessInBB( + MemoryUse *LoadAccess = cast(Updater.createMemoryAccessInBB( LoadInst, nullptr, Merge, MemorySSA::Beginning)); Updater.insertUse(LoadAccess); MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); @@ -267,15 +268,15 @@ B.CreateLoad(PointerArg); setupAnalyses(); MemorySSA &MSSA = *Analyses->MSSA; - + MemorySSAUpdater Updater(&MSSA); // Move the store SideStore->moveBefore(Entry->getTerminator()); MemoryAccess *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore); - MemoryAccess *NewStoreAccess = MSSA.createMemoryAccessAfter( + MemoryAccess *NewStoreAccess = Updater.createMemoryAccessAfter( SideStore, EntryStoreAccess, EntryStoreAccess); EntryStoreAccess->replaceAllUsesWith(NewStoreAccess); - MSSA.removeMemoryAccess(SideStoreAccess); + Updater.removeMemoryAccess(SideStoreAccess); MSSA.verifyMemorySSA(); } @@ -309,7 +310,7 @@ SideStore->moveBefore(Entry->getTerminator()); auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore); - auto *NewStoreAccess = MSSA.createMemoryAccessAfter( + auto *NewStoreAccess = Updater.createMemoryAccessAfter( SideStore, EntryStoreAccess, EntryStoreAccess); // Before, the load will point to a phi of the EntryStore and SideStore. auto *LoadAccess = cast(MSSA.getMemoryAccess(MergeLoad)); @@ -317,7 +318,7 @@ MemoryPhi *MergePhi = cast(LoadAccess->getDefiningAccess()); EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess); - MSSA.removeMemoryAccess(SideStoreAccess); + Updater.removeMemoryAccess(SideStoreAccess); Updater.insertDef(cast(NewStoreAccess)); // After it's a phi of the new side store access. EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess); @@ -448,13 +449,15 @@ setupAnalyses(); MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAUpdater Updater(&MSSA); + // Before, the load will be a use of a phi. MemoryUse *LoadAccess = cast(MSSA.getMemoryAccess(LoadInst)); MemoryDef *StoreAccess = cast(MSSA.getMemoryAccess(StoreInst)); MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); EXPECT_TRUE(isa(DefiningAccess)); // Kill the store - MSSA.removeMemoryAccess(StoreAccess); + Updater.removeMemoryAccess(StoreAccess); MemoryPhi *MP = cast(DefiningAccess); // Verify the phi ended up as liveonentry, liveonentry for (auto &Op : MP->incoming_values()) @@ -464,7 +467,7 @@ // Verify the load is now defined by liveOnEntryDef EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess())); // Remove the PHI - MSSA.removeMemoryAccess(MP); + Updater.removeMemoryAccess(MP); MSSA.verifyMemorySSA(); } @@ -492,6 +495,7 @@ setupAnalyses(); MemorySSA &MSSA = *Analyses->MSSA; MemorySSAWalker *Walker = Analyses->Walker; + MemorySSAUpdater Updater(&MSSA); // Before, the load will be a use of a phi. It should be // the same after. @@ -502,7 +506,7 @@ // The load is currently clobbered by one of the phi arguments, so the walker // should determine the clobbering access as the phi. EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst)); - MSSA.removeMemoryAccess(StoreAccess); + Updater.removeMemoryAccess(StoreAccess); MSSA.verifyMemorySSA(); // After the removeaccess, let's see if we got the right accesses // The load should still point to the phi ... @@ -526,7 +530,7 @@ } // Now we try to remove the single valued phi - MSSA.removeMemoryAccess(DefiningAccess); + Updater.removeMemoryAccess(DefiningAccess); MSSA.verifyMemorySSA(); // Now the load should be a load of live on entry. EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess())); @@ -680,10 +684,11 @@ setupAnalyses(); MemorySSA &MSSA = *Analyses->MSSA; MemorySSAWalker *Walker = Analyses->Walker; + MemorySSAUpdater Updater(&MSSA); // Kill `KillStore`; it exists solely so that the load after it won't be // optimized to FirstStore. - MSSA.removeMemoryAccess(MSSA.getMemoryAccess(KillStore)); + Updater.removeMemoryAccess(MSSA.getMemoryAccess(KillStore)); KillStore->eraseFromParent(); auto *ALoadMA = cast(MSSA.getMemoryAccess(ALoad)); EXPECT_EQ(ALoadMA->getDefiningAccess(), MSSA.getMemoryAccess(BStore)); @@ -755,15 +760,16 @@ setupAnalyses(); MemorySSA &MSSA = *Analyses->MSSA; MemorySSAWalker *Walker = Analyses->Walker; + MemorySSAUpdater Updater(&MSSA); MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LIA); MemoryUse *LoadAccess = cast(MSSA.getMemoryAccess(LIA)); EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SIA)); EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SIA))); - MSSA.removeMemoryAccess(LoadAccess); + Updater.removeMemoryAccess(LoadAccess); // Create the load memory access pointing to an unoptimized place. - MemoryUse *NewLoadAccess = cast(MSSA.createMemoryAccessInBB( + MemoryUse *NewLoadAccess = cast(Updater.createMemoryAccessInBB( LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End)); // This should it cause it to be optimized EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber); @@ -852,7 +858,7 @@ MemorySSAUpdater Updater(&MSSA); // Create the load memory acccess LoadInst *LoadInst = B.CreateLoad(FirstArg); - MemoryUse *LoadAccess = cast(MSSA.createMemoryAccessInBB( + MemoryUse *LoadAccess = cast(Updater.createMemoryAccessInBB( LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning)); Updater.insertUse(LoadAccess); MSSA.verifyMemorySSA();