Index: include/llvm/Transforms/Utils/MemorySSA.h =================================================================== --- include/llvm/Transforms/Utils/MemorySSA.h +++ 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" @@ -109,6 +110,9 @@ class LLVMContext; class raw_ostream; +struct AllAccessTag {}; +struct DefsOnlyTag {}; + enum { // Used to signify what the default invalid ID is for MemoryAccess's // getID() @@ -122,8 +126,13 @@ // \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 +165,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; @@ -207,7 +243,7 @@ protected: friend class MemorySSA; - + friend class MemorySSAUpdater; MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty, Instruction *MI, BasicBlock *BB) : MemoryAccess(C, Vty, BB, 1), MemoryInst(MI) { @@ -531,7 +567,13 @@ return LiveOnEntryDef.get(); } - using AccessList = iplist; + // Sadly, ilist_traits controls the ownership properties of the list, and we + // can't differentiate the ilist traits based on tags, only on the value + // type. So we can't use iplist for both since iplist's own if you don't + // change the traits. Thus, we use simple_ilist for one, and iplist for the + // other. This means the deflist usage is a bit uglier, but c'est la vie. + using AccessList = iplist>; + using DefsList = simple_ilist>; /// \brief Return the list of MemoryAccess's for a given basic block. /// @@ -540,6 +582,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. @@ -570,8 +620,8 @@ /// 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 clobbering definition - /// must be non-null. + /// 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, @@ -618,17 +668,24 @@ // Used by Memory SSA annotater, dumpers, and wrapper pass friend class MemorySSAAnnotatedWriter; friend class MemorySSAPrinterLegacyPass; + friend class MemorySSAUpdater; void verifyDefUses(Function &F) const; 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 +696,7 @@ void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const; using AccessMap = DenseMap>; + using DefsMap = DenseMap>; void determineInsertionPoint(const SmallPtrSetImpl &DefiningBlocks); @@ -656,6 +714,7 @@ void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, SmallPtrSet &Visited); AccessList *getOrCreateAccessList(const BasicBlock *); + DefsList *getOrCreateDefsList(const BasicBlock *); void renumberBlock(const BasicBlock *) const; AliasAnalysis *AA; @@ -665,6 +724,7 @@ // Memory SSA mappings DenseMap ValueToMemoryAccess; AccessMap PerBlockAccesses; + DefsMap PerBlockDefs; std::unique_ptr LiveOnEntryDef; // Domination mappings @@ -678,6 +738,28 @@ unsigned NextID; }; +class MemorySSAUpdater { +private: + MemorySSA *MSSA; + SmallVector InsertedPHIs; + DenseSet VisitedBlocks; + +public: + MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} + void insertDef(MemoryAccess *Def); + void insertUse(MemoryAccess *Use); + +private: + MemoryAccess *getPreviousDef(MemoryAccess *); + MemoryAccess *getPreviousDefInBlock(MemoryAccess *); + MemoryAccess *getPreviousDefFromEnd(BasicBlock *); + MemoryAccess *getPreviousDefRecursive(BasicBlock *); + MemoryAccess *recursePhi(MemoryAccess *Phi); + template + MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); + void fixupDefsAfterUs(const SmallVectorImpl &); +}; + // This pass does eager building and then printing of MemorySSA. It is used by // the tests to be able to build, dump, and verify Memory SSA. class MemorySSAPrinterLegacyPass : public FunctionPass { @@ -957,9 +1039,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: lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- lib/Transforms/Utils/MemorySSA.cpp +++ 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 @@ -1480,10 +1487,12 @@ for (auto &BB : IDFBlocks) { // Insert phi node AccessList *Accesses = getOrCreateAccessList(BB); + DefsList *Defs = getOrCreateDefsList(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); + Defs->push_front(*Phi); } } @@ -1511,15 +1520,20 @@ 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; + Defs = getOrCreateDefsList(&B); + Defs->push_back(*MUD); + } } if (InsertIntoDef) DefiningBlocks.insert(&B); @@ -1561,10 +1575,12 @@ MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) { assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB"); AccessList *Accesses = getOrCreateAccessList(BB); + DefsList *Defs = getOrCreateDefsList(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); + Defs->push_front(*Phi); BlockNumberingValid.erase(BB); return Phi; } @@ -1592,8 +1608,16 @@ *Accesses, [](const MemoryAccess &MA) { return !isa(MA); }); Accesses->insert(AI, NewAccess); + if (!isa(NewAccess)) { + auto *Defs = getOrCreateDefsList(BB); + Defs->push_front(*NewAccess); + } } else { Accesses->push_back(NewAccess); + if (!isa(NewAccess)) { + auto *Defs = getOrCreateDefsList(BB); + Defs->push_back(*NewAccess); + } } BlockNumberingValid.erase(BB); return NewAccess; @@ -1605,9 +1629,18 @@ 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()); + // Should already exist, since insertpt is in that block. + auto *Accesses = getWritableBlockAccesses(InsertPt->getBlock()); Accesses->insert(AccessList::iterator(InsertPt), NewAccess); BlockNumberingValid.erase(InsertPt->getBlock()); + if (!isa(NewAccess)) { + // May not exist, since we are not guaranteed insertion point is a def. + auto *Defs = getOrCreateDefsList(InsertPt->getBlock()); + auto DefsPoint = + isa(InsertPt) ? InsertPt->getDefsIterator() : Defs->end(); + Defs->insert(DefsPoint, *NewAccess); + } + return NewAccess; } @@ -1619,14 +1652,22 @@ MemoryUseOrDef *NewAccess = createDefinedAccess(I, Definition); auto *Accesses = getOrCreateAccessList(InsertPt->getBlock()); Accesses->insertAfter(AccessList::iterator(InsertPt), NewAccess); + if (!isa(NewAccess)) { + // May not exist, since we are not guaranteed insertion point is a def. + auto *Defs = getOrCreateDefsList(InsertPt->getBlock()); + auto DefsPoint = isa(InsertPt) ? ++(InsertPt->getDefsIterator()) + : Defs->end(); + Defs->insert(DefsPoint, *NewAccess); + } BlockNumberingValid.erase(InsertPt->getBlock()); + 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 +1802,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); @@ -1787,7 +1838,7 @@ } // Re-point the uses at our defining access - if (!MA->use_empty()) { + 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 @@ -1838,26 +1889,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 +1933,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(); } } @@ -2302,4 +2379,306 @@ return Use->getDefiningAccess(); return StartingAccess; } +// This is the marker algorithm from "Simple and Efficient Construction of +// Static Single Assignment Form" +// The simple, non-marker algorithm places phi nodes at any join +// Here, we place markers, and only place phi nodes if they end up necessary. +// They are only necessary if they break a cycle (IE we recursively visit +// ourselves again), or we discover, while getting the value of the operands, +// that there are two or more definitions needing to be merged. +// This still will leave non-minimal form in the case of irreducible control +// flow, where phi nodes may be in cycles with themselves, but unnecessary. +MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(BasicBlock *BB) { + MemoryAccess *Result; + + // Single predecessor case, just recurse, we can only have one definition. + if (BasicBlock *Pred = BB->getSinglePredecessor()) { + Result = getPreviousDefFromEnd(Pred); + } else if (VisitedBlocks.count(BB)) { + // We hit our node again, meaning we had a cycle, we must insert a phi + // node to break it so we have an operand. The only case this will + // insert useless phis is if we have irreducible control flow. + Result = MSSA->createMemoryPhi(BB); + } else { + // Mark us visited so we can detect a cycle + VisitedBlocks.insert(BB); + SmallVector PhiOps; + + // Recurse to get the values in our predecessors for placement of a + // potential phi node. This will insert phi nodes if we cycle in order to + // break the cycle and have an operand. + for (auto *Pred : predecessors(BB)) + PhiOps.push_back(getPreviousDefFromEnd(Pred)); + // Now try to simplify the ops to avoid placing a phi. + // This may return null if we never created a phi yet, that's okay + MemoryPhi *Phi = dyn_cast_or_null(MSSA->getMemoryAccess(BB)); + // See if we can avoid the phi by simplifying it. + Result = tryRemoveTrivialPhi(Phi, PhiOps); + // If we couldn't simplify, we may have to create a phi + if (Result == Phi) { + if (!Phi) { + Phi = MSSA->createMemoryPhi(BB); + } + + // These will be filled in by the recursive read. + unsigned i = 0; + for (auto *Pred : predecessors(BB)) + Phi->addIncoming(PhiOps[i++], Pred); + Result = Phi; + } + if (MemoryPhi *MP = dyn_cast(Result)) + InsertedPHIs.push_back(MP); + // Set ourselves up for the next variable by resetting visited state. + VisitedBlocks.erase(BB); + } + return Result; +} + +// This starts at the memory access +MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) { + auto *LocalResult = getPreviousDefInBlock(MA); + + return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock()); +} + +// This starts at the memory access +MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) { + auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock()); + + // It's possible there are no defs, or we got handed the first def to start. + if (Defs) { + // If this is a def, we can just use the def iterators. + if (!isa(MA)) { + auto Iter = MA->getReverseDefsIterator(); + ++Iter; + if (Iter != Defs->rend()) + return &*Iter; + } else { + // Otherwise, have to walk the all access iterator. + auto Iter = MA->getReverseIterator(); + ++Iter; + while (&*Iter != &*Defs->begin()) { + if (!isa(*Iter)) + return &*Iter; + --Iter; + } + // At this point it must be pointing at firstdef + assert(&*Iter == &*Defs->begin() && + "Should have hit first def walking backwards"); + return &*Iter; + } + } + return nullptr; +} + +// This starts at the end of block +MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) { + auto *Defs = MSSA->getWritableBlockDefs(BB); + + if (Defs) + return &*Defs->rbegin(); + + return getPreviousDefRecursive(BB); +} +// Recurse over a set of phi uses to eliminate the trivial ones +MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) { + if (!Phi) + return nullptr; + TrackingVH Res(Phi); + SmallVector, 8> Uses; + std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses)); + for (auto &U : Uses) { + if (MemoryPhi *UsePhi = dyn_cast(&*U)) { + auto OperRange = UsePhi->operands(); + tryRemoveTrivialPhi(UsePhi, OperRange); + } + } + return Res; +} + +// Eliminate trivial phis +// Phis are trivial if they are defined either by themselves, or all the same +// argument. +// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c) +// We recursively try to remove them. +template +MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi, + RangeType &Operands) { + // Detect equal or self arguments + MemoryAccess *Same = nullptr; + for (auto &Op : Operands) { + // If the same or self, good so far + if (Op == Phi || Op == Same) + continue; + // not the same, return the phi since it's not eliminatable by us + if (Same) + return Phi; + Same = cast(Op); + } + // Never found a non-self reference, the phi is undef + if (Same == nullptr) + return MSSA->getLiveOnEntryDef(); + if (Phi) { + Phi->replaceAllUsesWith(Same); + MSSA->removeMemoryAccess(Phi); + } + + // We should only end up recursing in case we replaced something, in which + // case, we may have made other Phis trivial. + return recursePhi(Same); +} + +void MemorySSAUpdater::insertUse(MemoryAccess *MA) { + InsertedPHIs.clear(); + cast(MA)->setDefiningAccess(getPreviousDef(MA)); + // Unlike for defs, there is no extra work to do. Because uses do not create + // new may-defs, there are only two cases: + // + // 1. There was a def already below us, and therefore, we should not have + // created a phi node because it was already needed for the def. + // + // 2. There is no def below us, and therefore, there is no extra renaming work + // to do. +} + +void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB, + MemoryAccess *NewDef) { + // Replace any operand with us an incoming block with the new defining + // access. + int i = MP->getBasicBlockIndex(BB); + assert(i != -1 && "Should have found the basic block in the phi"); + while (MP->getIncomingBlock(i) == BB) { + // Unlike above, there is already a phi node here, so we only need + // to set the right value. + MP->setIncomingValue(i, NewDef); + ++i; + } +} + +// A brief description of the algorithm: +// First, we generate figure out what should define the new def, using the ssa +// construction algorithm. +// 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(MemoryAccess *MA) { + InsertedPHIs.clear(); + assert((isa(MA)) && + "Trying to insert a memory use as a memorydef!"); + + // See if we had a local def, and if not, go hunting. + MemoryAccess *DefBefore = getPreviousDefInBlock(MA); + bool DefBeforeSameBlock = DefBefore != nullptr; + if (!DefBefore) + DefBefore = getPreviousDefRecursive(MA->getBlock()); + + // There is a def before us, which means we can replace any store/phi uses + // of that thing with us, since we are in the way of whatever was there + // before. + // We now define that def's memorydefs and memoryphis + for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end(); UI != UE;) { + Use &U = *UI++; + // Leave the uses alone + if (isa(U.getUser())) + continue; + U.set(MA); + } + // and that def is now our defining access. + // We change them in this order otherwise we will appear in the use list + // above and reset ourselves. + cast(MA)->setDefiningAccess(DefBefore); + + SmallVector FixupList(InsertedPHIs.begin(), + InsertedPHIs.end()); + if (!DefBeforeSameBlock) { + // If there was a local def before us, we must have the same effect it + // did. Because every may-def is the same, any phis/etc we would create, it + // would also have created. If there was no local def before us, we + // performed a global update, and have to search all successors and make + // sure we update the first def in each of them (following all path until we + // hit the first def). This may also insert phi nodes. TODO: There are + // other cases we can skip this work, such as when we have a single + // successor, and only used a straight line of single pred blocks backwards + // to find the def. To make that work, we'd have to track whether + // getDefRecursive only ever used the single predecessor case. They only + // exist in between CFG simplifications + FixupList.push_back(MA); + } + + while (!FixupList.empty()) { + unsigned StartingPHISize = InsertedPHIs.size(); + fixupDefsAfterUs(FixupList); + FixupList.clear(); + // Put any new phis on the fixup list, and process them + for (unsigned i = InsertedPHIs.size() - StartingPHISize; + i < InsertedPHIs.size(); ++i) + FixupList.push_back(InsertedPHIs[i]); + } +} + +void MemorySSAUpdater::fixupDefsAfterUs( + const SmallVectorImpl &Vars) { + SmallPtrSet Seen; + SmallVector Worklist; + for (auto *NewDef : Vars) { + // First, see if there is a local def after the operand. + auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock()); + auto DefIter = NewDef->getDefsIterator(); + + // If there is a local def after us, we only have to rename that. + if (++DefIter != Defs->end()) { + cast(DefIter)->setDefiningAccess(NewDef); + continue; + } + + // Otherwise, we need to search down through the CFG. + // For each of our successors, handle it directly if their is a phi, or + // place on the fixup worklist. + for (const auto *S : successors(NewDef->getBlock())) { + if (auto *MP = MSSA->getMemoryAccess(S)) + setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef); + else + Worklist.push_back(S); + } + + while (!Worklist.empty()) { + const BasicBlock *FixupBlock = Worklist.back(); + Worklist.pop_back(); + + // Get the first def in the block that isn't a phi node. + auto *Defs = MSSA->getWritableBlockDefs(FixupBlock); + if (Defs) { + auto *FirstDef = &*Defs->begin(); + // The loop above and below should have taken care of phi nodes + assert(!isa(FirstDef) && + "Should have already handled phi nodes!"); + // We are now this def's defining access,make sure we actually dominate + // it + assert(MSSA->dominates(NewDef, FirstDef) && + "Should have dominated the new access"); + + // This may insert new phi nodes, because we are not guaranteed the + // block we are processing has a single pred, and depending where the + // store was inserted, it may require phi nodes below it. + cast(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef)); + return; + } + // We didn't find a def, so we must continue. + for (const auto *S : successors(FixupBlock)) { + // If there is a phi node, handle it. + // Otherwise, put the block on the worklist + if (auto *MP = MSSA->getMemoryAccess(S)) + setMemoryPhiValueForBlock(MP, FixupBlock, NewDef); + else { + // If we cycle, we should have ended up at a phi node that we already + // processed. FIXME: Double check this + if (!Seen.insert(S).second) + continue; + Worklist.push_back(S); + } + } + } + } +} + } // namespace llvm Index: unittests/Transforms/Utils/MemorySSA.cpp =================================================================== --- unittests/Transforms/Utils/MemorySSA.cpp +++ unittests/Transforms/Utils/MemorySSA.cpp @@ -104,6 +104,139 @@ EXPECT_TRUE(isa(DefiningAccess)); MSSA.verifyMemorySSA(); } +TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) { + // We create a diamond, then build memoryssa with no memory accesses, and + // incrementally update it by inserting a store in the, entry, a load in the + // merge point, then a store in the branch, another load in the merge point, + // and then a store in the entry. + F = Function::Create( + FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), + GlobalValue::ExternalLinkage, "F", &M); + BasicBlock *Entry(BasicBlock::Create(C, "", F)); + BasicBlock *Left(BasicBlock::Create(C, "", F)); + BasicBlock *Right(BasicBlock::Create(C, "", F)); + BasicBlock *Merge(BasicBlock::Create(C, "", F)); + B.SetInsertPoint(Entry); + B.CreateCondBr(B.getTrue(), Left, Right); + B.SetInsertPoint(Left, Left->begin()); + Argument *PointerArg = &*F->arg_begin(); + B.SetInsertPoint(Left); + B.CreateBr(Merge); + B.SetInsertPoint(Right); + B.CreateBr(Merge); + + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAUpdater Updater(&MSSA); + // Add the store + B.SetInsertPoint(Entry, Entry->begin()); + StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); + MemoryAccess *EntryStoreAccess = MSSA.createMemoryAccessInBB( + EntryStore, nullptr, Entry, MemorySSA::Beginning); + Updater.insertDef(EntryStoreAccess); + + // Add the load + B.SetInsertPoint(Merge, Merge->begin()); + LoadInst *FirstLoad = B.CreateLoad(PointerArg); + + // MemoryPHI should not already exist. + MemoryPhi *MP = MSSA.getMemoryAccess(Merge); + EXPECT_EQ(MP, nullptr); + + // Create the load memory access + MemoryUse *FirstLoadAccess = cast(MSSA.createMemoryAccessInBB( + FirstLoad, nullptr, Merge, MemorySSA::Beginning)); + Updater.insertUse(FirstLoadAccess); + // Should just have a load using the entry access, because it should discover + // the phi is trivial + EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess); + + // Create a store on the left + // Add the store + B.SetInsertPoint(Left, Left->begin()); + StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg); + MemoryAccess *LeftStoreAccess = MSSA.createMemoryAccessInBB( + LeftStore, nullptr, Left, MemorySSA::Beginning); + Updater.insertDef(LeftStoreAccess); + // 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()); + LoadInst *SecondLoad = B.CreateLoad(PointerArg); + + // MemoryPHI should not already exist. + MP = MSSA.getMemoryAccess(Merge); + EXPECT_EQ(MP, nullptr); + + // Create the load memory access + MemoryUse *SecondLoadAccess = cast(MSSA.createMemoryAccessInBB( + SecondLoad, nullptr, Merge, MemorySSA::Beginning)); + Updater.insertUse(SecondLoadAccess); + // Now the load should be a phi of the entry store and the left store + MemoryPhi *MergePhi = + dyn_cast(SecondLoadAccess->getDefiningAccess()); + EXPECT_NE(MergePhi, nullptr); + EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess); + // 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( + SecondEntryStore, nullptr, Entry, MemorySSA::End); + Updater.insertDef(SecondEntryStoreAccess); + // and make sure the phi below it got updated, despite being blocks away + MergePhi = dyn_cast(SecondLoadAccess->getDefiningAccess()); + EXPECT_NE(MergePhi, nullptr); + EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess); + MSSA.verifyMemorySSA(); +} + +TEST_F(MemorySSATest, CreateALoadUpdater) { + // We create a diamond, then build memoryssa with no memory accesses, and + // incrementally update it by inserting a store in one of the branches, and a + // load in the merge point + F = Function::Create( + FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), + GlobalValue::ExternalLinkage, "F", &M); + BasicBlock *Entry(BasicBlock::Create(C, "", F)); + BasicBlock *Left(BasicBlock::Create(C, "", F)); + BasicBlock *Right(BasicBlock::Create(C, "", F)); + BasicBlock *Merge(BasicBlock::Create(C, "", F)); + B.SetInsertPoint(Entry); + B.CreateCondBr(B.getTrue(), Left, Right); + B.SetInsertPoint(Left, Left->begin()); + Argument *PointerArg = &*F->arg_begin(); + B.SetInsertPoint(Left); + B.CreateBr(Merge); + B.SetInsertPoint(Right); + B.CreateBr(Merge); + + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAUpdater Updater(&MSSA); + B.SetInsertPoint(Left, Left->begin()); + // Add the store + StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg); + MemoryAccess *StoreAccess = + MSSA.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning); + Updater.insertDef(StoreAccess); + + // Add the load + B.SetInsertPoint(Merge, Merge->begin()); + LoadInst *LoadInst = B.CreateLoad(PointerArg); + + // MemoryPHI should not already exist. + MemoryPhi *MP = MSSA.getMemoryAccess(Merge); + EXPECT_EQ(MP, nullptr); + + // Create the load memory acccess + MemoryUse *LoadAccess = cast(MSSA.createMemoryAccessInBB( + LoadInst, nullptr, Merge, MemorySSA::Beginning)); + Updater.insertUse(LoadAccess); + MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); + EXPECT_TRUE(isa(DefiningAccess)); + MSSA.verifyMemorySSA(); +} TEST_F(MemorySSATest, MoveAStore) { // We create a diamond where there is a in the entry, a store on one side, and @@ -140,6 +273,56 @@ MSSA.verifyMemorySSA(); } +TEST_F(MemorySSATest, MoveAStoreUpdater) { +#if 0 + // We create a diamond where there is a in the entry, a store on one side, and + // a load at the end. After building MemorySSA, we test updating by moving + // the store from the side block to the entry block. + F = Function::Create( + FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), + GlobalValue::ExternalLinkage, "F", &M); + BasicBlock *Entry(BasicBlock::Create(C, "", F)); + BasicBlock *Left(BasicBlock::Create(C, "", F)); + BasicBlock *Right(BasicBlock::Create(C, "", F)); + BasicBlock *Merge(BasicBlock::Create(C, "", F)); + B.SetInsertPoint(Entry); + Argument *PointerArg = &*F->arg_begin(); + StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); + B.CreateCondBr(B.getTrue(), Left, Right); + B.SetInsertPoint(Left); + auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg); + BranchInst::Create(Merge, Left); + BranchInst::Create(Merge, Right); + B.SetInsertPoint(Merge); + auto *MergeLoad = B.CreateLoad(PointerArg); + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAUpdater Updater(&MSSA); + + // Move the store + SideStore->moveBefore(Entry->getTerminator()); + auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); + auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore); + auto *NewStoreAccess = MSSA.createMemoryAccessAfter( + SideStore, EntryStoreAccess, EntryStoreAccess); + // Before, the load will point to a phi of the EntryStore and SideStore + auto *LoadAccess = cast(MSSA.getMemoryAccess(MergeLoad)); + EXPECT_TRUE(isa(LoadAccess->getDefiningAccess())); + MemoryPhi *MergePhi = cast(LoadAccess->getDefiningAccess()); + EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess); + // SideStoreAccess->replaceAllUsesWith(NewStoreAccess); + MSSA.removeMemoryAccess(SideStoreAccess); + Updater.insertDef(NewStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess); + EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess); + + // After, the load should point to a phi of the EntryStore and NewStore + // At this point + MSSA.verifyMemorySSA(); +#endif +} + TEST_F(MemorySSATest, RemoveAPhi) { // We create a diamond where there is a store on one side, and then a load // after the merge point. This enables us to test a bunch of different @@ -485,6 +668,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 +716,43 @@ EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1), MSSA.getMemoryAccess(StoreA2))); } +#endif +TEST_F(MemorySSATest, Irreducible) { + // Create the equivalent of + // x = something + // if (...) + // goto second_loop_entry + // while (...) { + // second_loop_entry: + // } + // use(x) + + SmallVector Inserted; + IRBuilder<> B(C); + F = Function::Create( + FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), + GlobalValue::ExternalLinkage, "F", &M); + + // Make blocks + BasicBlock *IfBB = BasicBlock::Create(C, "if", F); + BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F); + BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F); + BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F); + B.SetInsertPoint(IfBB); + B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB); + B.SetInsertPoint(LoopStartBB); + B.CreateBr(LoopMainBB); + B.SetInsertPoint(LoopMainBB); + B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB); + B.SetInsertPoint(AfterLoopBB); + Argument *FirstArg = &*F->arg_begin(); + setupAnalyses(); + MemorySSA &MSSA = *Analyses->MSSA; + MemorySSAUpdater Updater(&MSSA); + // Create the load memory acccess + LoadInst *LoadInst = B.CreateLoad(FirstArg); + MemoryUse *LoadAccess = cast(MSSA.createMemoryAccessInBB( + LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning)); + Updater.insertUse(LoadAccess); + MSSA.verifyMemorySSA(); +}