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 @@ -73,13 +73,14 @@ #define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/iterator_range.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" #include "llvm/ADT/iterator.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/PHITransAddr.h" @@ -108,6 +109,11 @@ class MemoryAccess; class LLVMContext; class raw_ostream; +namespace MSSAHelpers { + +struct AllAccessTag {}; +struct DefsOnlyTag {}; +} enum { // Used to signify what the default invalid ID is for MemoryAccess's @@ -122,8 +128,16 @@ // \brief The base for all memory accesses. All memory accesses in a block are // linked together using an intrusive list. -class MemoryAccess : public User, public ilist_node { +class MemoryAccess + : public User, + public ilist_node>, + public ilist_node> { public: + using AllAccessType = + ilist_node>; + using DefsOnlyType = + ilist_node>; + // Methods for support type inquiry through isa, cast, and // dyn_cast static inline bool classof(const MemoryAccess *) { return true; } @@ -156,6 +170,33 @@ memoryaccess_def_iterator defs_end(); const_memoryaccess_def_iterator defs_end() const; + /// \brief Get the iterators for the all access list and the defs only list + /// We default to the all access list. + AllAccessType::self_iterator getIterator() { + return this->AllAccessType::getIterator(); + } + AllAccessType::const_self_iterator getIterator() const { + return this->AllAccessType::getIterator(); + } + AllAccessType::reverse_self_iterator getReverseIterator() { + return this->AllAccessType::getReverseIterator(); + } + AllAccessType::const_reverse_self_iterator getReverseIterator() const { + return this->AllAccessType::getReverseIterator(); + } + DefsOnlyType::self_iterator getDefsIterator() { + return this->DefsOnlyType::getIterator(); + } + DefsOnlyType::const_self_iterator getDefsIterator() const { + return this->DefsOnlyType::getIterator(); + } + DefsOnlyType::reverse_self_iterator getReverseDefsIterator() { + return this->DefsOnlyType::getReverseIterator(); + } + DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const { + return this->DefsOnlyType::getReverseIterator(); + } + protected: friend class MemorySSA; friend class MemoryUseOrDef; @@ -531,7 +572,14 @@ return LiveOnEntryDef.get(); } - using AccessList = iplist; + // Sadly, iplists, by default, owns and deletes pointers added to the + // list. It's not currently possible to have two iplists for the same type, + // where one owns the pointers, and one does not. This is because the traits + // are per-type, not per-tag. If this ever changes, we should make the + // DefList an iplist. + using AccessList = iplist>; + using DefsList = + simple_ilist>; /// \brief Return the list of MemoryAccess's for a given basic block. /// @@ -540,6 +588,14 @@ return getWritableBlockAccesses(BB); } + /// \brief Return the list of MemoryDef's and MemoryPhi's for a given basic + /// block. + /// + /// This list is not modifiable by the user. + const DefsList *getBlockDefs(const BasicBlock *BB) const { + 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. @@ -623,12 +679,18 @@ void verifyDomination(Function &F) const; void verifyOrdering(Function &F) const; - // This is used by the use optimizer class + // This is used by the use optimizer and updater. AccessList *getWritableBlockAccesses(const BasicBlock *BB) const { auto It = PerBlockAccesses.find(BB); return It == PerBlockAccesses.end() ? nullptr : It->second.get(); } + // This is used by the use optimizer and updater. + DefsList *getWritableBlockDefs(const BasicBlock *BB) const { + auto It = PerBlockDefs.find(BB); + return It == PerBlockDefs.end() ? nullptr : It->second.get(); + } + private: class CachingWalker; class OptimizeUses; @@ -639,6 +701,7 @@ void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const; using AccessMap = DenseMap>; + using DefsMap = DenseMap>; void determineInsertionPoint(const SmallPtrSetImpl &DefiningBlocks); @@ -656,15 +719,26 @@ void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, SmallPtrSet &Visited); 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; // Memory SSA mappings DenseMap ValueToMemoryAccess; + // These two mappings contain the main block to access/def mappings for + // MemorySSA. The list contained in PerBlockAccesses really owns all the + // MemoryAccesses. + // Both maps maintain the invariant that if a block is found in them, the + // corresponding list is not empty, and if a block is not found in them, the + // corresponding list is empty. AccessMap PerBlockAccesses; + DefsMap PerBlockDefs; std::unique_ptr LiveOnEntryDef; // Domination mappings @@ -957,9 +1031,7 @@ fillInCurrentPair(); } - upward_defs_iterator() { - CurrentPair.first = nullptr; - } + upward_defs_iterator() { CurrentPair.first = nullptr; } bool operator==(const upward_defs_iterator &Other) const { return DefIterator == Other.DefIterator; Index: llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp @@ -145,8 +145,8 @@ private: union { - ImmutableCallSite CS; - MemoryLocation Loc; + ImmutableCallSite CS; + MemoryLocation Loc; }; }; } @@ -1247,6 +1247,13 @@ Res.first->second = make_unique(); return Res.first->second.get(); } +MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) { + auto Res = PerBlockDefs.insert(std::make_pair(BB, nullptr)); + + if (Res.second) + Res.first->second = make_unique(); + return Res.first->second.get(); +} /// This class is a batch walker of all MemoryUse's in the program, and points /// their defining access at the thing that actually clobbers them. Because it @@ -1477,14 +1484,8 @@ }); // Now place MemoryPhi nodes. - for (auto &BB : IDFBlocks) { - // Insert phi node - AccessList *Accesses = getOrCreateAccessList(BB); - MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++); - ValueToMemoryAccess[BB] = Phi; - // Phi's always are placed at the front of the block. - Accesses->push_front(Phi); - } + for (auto &BB : IDFBlocks) + createMemoryPhi(BB); } void MemorySSA::buildMemorySSA() { @@ -1511,15 +1512,21 @@ BBNumbers[&B] = NextBBNum++; bool InsertIntoDef = false; AccessList *Accesses = nullptr; + DefsList *Defs = nullptr; for (Instruction &I : B) { MemoryUseOrDef *MUD = createNewAccess(&I); if (!MUD) continue; - InsertIntoDef |= isa(MUD); if (!Accesses) Accesses = getOrCreateAccessList(&B); Accesses->push_back(MUD); + if (isa(MUD)) { + InsertIntoDef = true; + if (!Defs) + Defs = getOrCreateDefsList(&B); + Defs->push_back(*MUD); + } } if (InsertIntoDef) DefiningBlocks.insert(&B); @@ -1558,13 +1565,73 @@ return Walker.get(); } +// This is a helper function used by the creation routines. It places NewAccess +// into the access and defs lists for a given basic block, at the given +// insertion point. +void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess, + const BasicBlock *BB, + InsertionPlace Point) { + auto *Accesses = getOrCreateAccessList(BB); + if (Point == Beginning) { + // If it's a phi node, it goes first, otherwise, it goes after any phi + // nodes. + if (isa(NewAccess)) { + Accesses->push_front(NewAccess); + auto *Defs = getOrCreateDefsList(BB); + Defs->push_front(*NewAccess); + } else { + auto AI = find_if_not( + *Accesses, [](const MemoryAccess &MA) { return isa(MA); }); + Accesses->insert(AI, NewAccess); + if (!isa(NewAccess)) { + auto *Defs = getOrCreateDefsList(BB); + auto DI = find_if_not( + *Defs, [](const MemoryAccess &MA) { return isa(MA); }); + Defs->insert(DI, *NewAccess); + } + } + } else { + Accesses->push_back(NewAccess); + if (!isa(NewAccess)) { + auto *Defs = getOrCreateDefsList(BB); + Defs->push_back(*NewAccess); + } + } +} + +void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB, + AccessList::iterator InsertPt) { + auto *Accesses = getWritableBlockAccesses(BB); + bool WasEnd = InsertPt == Accesses->end(); + Accesses->insert(AccessList::iterator(InsertPt), What); + if (!isa(What)) { + auto *Defs = getOrCreateDefsList(BB); + // If we got asked to insert at the end, we have an easy job, just shove it + // at the end. If we got asked to insert before an existing def, we also get + // an terator. If we got asked to insert before a use, we have to hunt for + // the next def. + if (WasEnd) { + Defs->push_back(*What); + } else if (isa(InsertPt)) { + Defs->insert(InsertPt->getDefsIterator(), *What); + } else { + while (InsertPt != Accesses->end() && !isa(InsertPt)) + ++InsertPt; + // Either we found a def, or we are inserting at the end + if (InsertPt == Accesses->end()) + Defs->push_back(*What); + else + Defs->insert(InsertPt->getDefsIterator(), *What); + } + } +} + MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) { assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB"); - AccessList *Accesses = getOrCreateAccessList(BB); MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++); + insertIntoListsForBlock(Phi, BB, Beginning); ValueToMemoryAccess[BB] = Phi; // Phi's always are placed at the front of the block. - Accesses->push_front(Phi); BlockNumberingValid.erase(BB); return Phi; } @@ -1585,16 +1652,7 @@ const BasicBlock *BB, InsertionPlace Point) { MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - auto *Accesses = getOrCreateAccessList(BB); - if (Point == Beginning) { - // It goes after any phi nodes - auto AI = find_if( - *Accesses, [](const MemoryAccess &MA) { return !isa(MA); }); - - Accesses->insert(AI, NewAccess); - } else { - Accesses->push_back(NewAccess); - } + insertIntoListsForBlock(NewAccess, BB, Point); BlockNumberingValid.erase(BB); return NewAccess; } @@ -1605,9 +1663,9 @@ assert(I->getParent() == InsertPt->getBlock() && "New and old access must be in the same block"); MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - auto *Accesses = getOrCreateAccessList(InsertPt->getBlock()); - Accesses->insert(AccessList::iterator(InsertPt), NewAccess); BlockNumberingValid.erase(InsertPt->getBlock()); + insertIntoListsBefore(NewAccess, InsertPt->getBlock(), + InsertPt->getIterator()); return NewAccess; } @@ -1617,16 +1675,16 @@ assert(I->getParent() == InsertPt->getBlock() && "New and old access must be in the same block"); MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); - auto *Accesses = getOrCreateAccessList(InsertPt->getBlock()); - Accesses->insertAfter(AccessList::iterator(InsertPt), NewAccess); BlockNumberingValid.erase(InsertPt->getBlock()); + insertIntoListsBefore(NewAccess, InsertPt->getBlock(), + ++(InsertPt->getIterator())); return NewAccess; } void MemorySSA::spliceMemoryAccessAbove(MemoryDef *Where, MemoryUseOrDef *What) { - assert(What != getLiveOnEntryDef() && - Where != getLiveOnEntryDef() && "Can't splice (above) LOE."); + assert(What != getLiveOnEntryDef() && Where != getLiveOnEntryDef() && + "Can't splice (above) LOE."); assert(dominates(Where, What) && "Only upwards splices are permitted."); if (Where == What) @@ -1761,6 +1819,16 @@ if (VMA->second == MA) ValueToMemoryAccess.erase(VMA); + // The access list owns the reference, so we erase it from the non-owning list + // first. + if (!isa(MA)) { + auto DefsIt = PerBlockDefs.find(MA->getBlock()); + std::unique_ptr &Defs = DefsIt->second; + Defs->remove(*MA); + if (Defs->empty()) + PerBlockDefs.erase(DefsIt); + } + auto AccessIt = PerBlockAccesses.find(MA->getBlock()); std::unique_ptr &Accesses = AccessIt->second; Accesses->erase(MA); @@ -1838,26 +1906,42 @@ // lists think, as well as the order in the blocks vs the order in the access // lists. SmallVector ActualAccesses; + SmallVector ActualDefs; for (BasicBlock &B : F) { const AccessList *AL = getBlockAccesses(&B); + const auto *DL = getBlockDefs(&B); MemoryAccess *Phi = getMemoryAccess(&B); - if (Phi) + if (Phi) { ActualAccesses.push_back(Phi); + ActualDefs.push_back(Phi); + } + for (Instruction &I : B) { MemoryAccess *MA = getMemoryAccess(&I); - assert((!MA || AL) && "We have memory affecting instructions " - "in this block but they are not in the " - "access list"); - if (MA) + assert((!MA || (AL && (isa(MA) || DL))) && + "We have memory affecting instructions " + "in this block but they are not in the " + "access list or defs list"); + if (MA) { ActualAccesses.push_back(MA); + if (isa(MA)) + ActualDefs.push_back(MA); + } } // Either we hit the assert, really have no accesses, or we have both - // accesses and an access list - if (!AL) + // accesses and an access list. + // Same with defs. + if (!AL && !DL) continue; assert(AL->size() == ActualAccesses.size() && "We don't have the same number of accesses in the block as on the " "access list"); + assert(DL || + ActualDefs.size() == 0 && + "Either we should have a defs list, or we should have no defs"); + assert((!DL || DL->size() == ActualDefs.size()) && + "We don't have the same number of defs in the block as on the " + "def list"); auto ALI = AL->begin(); auto AAI = ActualAccesses.begin(); while (ALI != AL->end() && AAI != ActualAccesses.end()) { @@ -1866,6 +1950,16 @@ ++AAI; } ActualAccesses.clear(); + if (DL) { + auto DLI = DL->begin(); + auto ADI = ActualDefs.begin(); + while (DLI != DL->end() && ADI != ActualDefs.end()) { + assert(&*DLI == *ADI && "Not the same defs in the same order"); + ++DLI; + ++ADI; + } + } + ActualDefs.clear(); } } Index: llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp =================================================================== --- llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp +++ llvm/trunk/unittests/Transforms/Utils/MemorySSA.cpp @@ -485,6 +485,7 @@ EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber); } +#if 0 // Test out MemorySSA::spliceMemoryAccessAbove. TEST_F(MemorySSATest, SpliceAboveMemoryDef) { F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), @@ -532,3 +533,4 @@ EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1), MSSA.getMemoryAccess(StoreA2))); } +#endif