Index: include/llvm/IR/Function.h =================================================================== --- include/llvm/IR/Function.h +++ include/llvm/IR/Function.h @@ -546,6 +546,12 @@ Constant *getPrologueData() const; void setPrologueData(Constant *PrologueData); + /// Print the function to an output stream with an optional + /// AssemblyAnnotationWriter. + void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW = nullptr, + bool ShouldPreserveUseListOrder = false, + bool IsForDebug = false) const; + /// viewCFG - This function is meant for use from the debugger. You can just /// say 'call F->viewCFG()' and a ghostview window should pop up from the /// program, displaying the CFG of the current function with the code for each Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -204,6 +204,8 @@ void initializeMemDepPrinterPass(PassRegistry&); void initializeMemDerefPrinterPass(PassRegistry&); void initializeMemoryDependenceAnalysisPass(PassRegistry&); +void initializeMemorySSALazyPass(PassRegistry&); +void initializeMemorySSAPrinterPassPass(PassRegistry&); void initializeMergedLoadStoreMotionPass(PassRegistry &); void initializeMetaRenamerPass(PassRegistry&); void initializeMergeFunctionsPass(PassRegistry&); Index: include/llvm/Transforms/Utils/MemorySSA.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Utils/MemorySSA.h @@ -0,0 +1,925 @@ +//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// \file +// \brief This file exposes an interface to building/using memory SSA to +// walk memory instructions using a use/def graph + +// Memory SSA class builds an SSA form that links together memory access +// instructions such loads, stores, atomics and calls. Additionally, it does a +// trivial form of "heap versioning" Every time the memory state changes in the +// program, we generate a new heap version It generates MemoryDef/Uses/Phis that +// are overlayed on top of the existing instructions + +// As a trivial example, +// define i32 @main() #0 { +// entry: +// %call = call noalias i8* @_Znwm(i64 4) #2 +// %0 = bitcast i8* %call to i32* +// %call1 = call noalias i8* @_Znwm(i64 4) #2 +// %1 = bitcast i8* %call1 to i32* +// store i32 5, i32* %0, align 4 +// store i32 7, i32* %1, align 4 +// %2 = load i32* %0, align 4 +// %3 = load i32* %1, align 4 +// %add = add nsw i32 %2, %3 +// ret i32 %add +// } +// Will become +// define i32 @main() #0 { +// entry: +// ; 1 = MemoryDef(0) +// %call = call noalias i8* @_Znwm(i64 4) #3 +// %2 = bitcast i8* %call to i32* +// ; 2 = MemoryDef(1) +// %call1 = call noalias i8* @_Znwm(i64 4) #3 +// %4 = bitcast i8* %call1 to i32* +// ; 3 = MemoryDef(2) +// store i32 5, i32* %2, align 4 +// ; 4 = MemoryDef(3) +// store i32 7, i32* %4, align 4 +// ; MemoryUse(4) +// %7 = load i32* %2, align 4 +// ; MemoryUse(3) +// %8 = load i32* %4, align 4 +// %add = add nsw i32 %7, %8 +// ret i32 %add +// } +// Given this form, all the stores that could ever effect the load +// at %8 can be gotten by using the memory use associated with it, +// and walking from use to def until you hit the top of the function. + +// Each def also has a list of users associated with it, so you can walk from +// both def to users, and users to defs. +// Note that we disambiguate MemoryUse's, but not the RHS of memorydefs. +// You can see this above at %8, which would otherwise be a MemoryUse(4) +// Being disambiguated means that for a given store, all the MemoryUses on its +// use lists are may-aliases of that store (but the MemoryDefs on its use list +// may not be) +// +// MemoryDefs are not disambiguated because it would require multiple reaching +// definitions, which would require multiple phis, and multiple memoryaccesses +// per instruction. + +//===----------------------------------------------------------------------===// +#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H +#define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include + +namespace llvm { + +class BasicBlock; +class DominatorTree; +class Function; +class MemoryAccess; +template class memoryaccess_def_iterator_base; +typedef memoryaccess_def_iterator_base memoryaccess_def_iterator; +typedef memoryaccess_def_iterator_base + const_memoryaccess_def_iterator; + +// \brief The base for all memory accesses. All memory accesses in a +// block are linked together using an intrusive list. +class MemoryAccess : public ilist_node { +public: + enum AccessType { AccessUse, AccessDef, AccessPhi }; + + // Methods for support type inquiry through isa, cast, and + // dyn_cast + static inline bool classof(const MemoryAccess *) { return true; } + + virtual ~MemoryAccess(); + BasicBlock *getBlock() const { return Block; } + + /// \brief Get the instruction that this MemoryAccess represents. + /// This may be null in the case of phi nodes. + virtual Instruction *getMemoryInst() const = 0; + + /// \brief Get the access that produces the memory state used by this access. + virtual MemoryAccess *getDefiningAccess() const = 0; + + /// \brief Replace our defining access with a new one. + /// + /// This function updates use lists. + virtual void setDefiningAccess(MemoryAccess *) = 0; + + virtual void print(raw_ostream &OS) const {}; + virtual void dump() const; + + typedef SmallPtrSet UserListType; + typedef UserListType::iterator iterator; + typedef UserListType::const_iterator const_iterator; + + unsigned user_size() const { return Users.size(); } + bool user_empty() const { return Users.empty(); } + iterator user_begin() { return Users.begin(); } + iterator user_end() { return Users.end(); } + iterator_range users() { + return iterator_range(user_begin(), user_end()); + } + + const_iterator user_begin() const { return Users.begin(); } + const_iterator user_end() const { return Users.end(); } + iterator_range uses() const { + return iterator_range(user_begin(), user_end()); + } + + /// \brief This iterator walks over all of the defs in a given + /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For + /// MemoryUse/MemoryDef, this walks the defining access. + memoryaccess_def_iterator defs_begin(); + const_memoryaccess_def_iterator defs_begin() const; + memoryaccess_def_iterator defs_end(); + const_memoryaccess_def_iterator defs_end() const; + +protected: + friend class MemorySSA; + friend class MemoryUse; + friend class MemoryDef; + friend class MemoryPhi; + AccessType getAccessType() const { return AccessType; } + + /// \brief Set the instruction that this MemoryUse represents. + virtual void setMemoryInst(Instruction *MI) = 0; + + /// \brief Add a use of this memory access to our list of uses. + /// + /// Note: We depend on being able to add the same use multiple times and not + /// have it end up in our use list multiple times. + void addUse(MemoryAccess *Use) { Users.insert(Use); } + + /// \brief Remove a use of this memory access from our list of uses. + void removeUse(MemoryAccess *Use) { Users.erase(Use); } + + /// \brief Return true if \p Use is one of the uses of this memory access. + bool hasUse(MemoryAccess *Use) { return Users.count(Use); } + + MemoryAccess(AccessType AT, BasicBlock *BB) : AccessType(AT), Block(BB) {} + + /// \brief Used internally to give IDs to MemoryAccesses for printing + virtual unsigned int getID() const = 0; + +private: + MemoryAccess(const MemoryAccess &); + void operator=(const MemoryAccess &); + AccessType AccessType; + BasicBlock *Block; + UserListType Users; +}; + +template <> +struct ilist_traits : public ilist_default_traits { + // See details of the instruction class for why this trick works + MemoryAccess *createSentinel() const { + return static_cast(&Sentinel); + } + + static void destroySentinel(MemoryAccess *) {} + + MemoryAccess *provideInitialHead() const { return createSentinel(); } + MemoryAccess *ensureHead(MemoryAccess *) const { return createSentinel(); } + static void noteHead(MemoryAccess *, MemoryAccess *) {} + +private: + mutable ilist_half_node Sentinel; +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) { + MA.print(OS); + return OS; +} + +/// \brief Represents read-only accesses to memory +/// +/// In particular, the set of Instructions that will be represented by +/// MemoryUse's is exactly the set of Instructions for which +/// AliasAnalysis::getModRefInfo returns "Ref". +class MemoryUse : public MemoryAccess { +public: + MemoryUse(MemoryAccess *DMA, Instruction *MI, BasicBlock *BB) + : MemoryUse(DMA, AccessUse, MI, BB) {} + + virtual MemoryAccess *getDefiningAccess() const final { + return DefiningAccess; + } + + virtual Instruction *getMemoryInst() const final { return MemoryInst; } + + static inline bool classof(const MemoryUse *) { return true; } + static inline bool classof(const MemoryAccess *MA) { + return MA->getAccessType() == AccessUse; + } + virtual void print(raw_ostream &OS) const; + +protected: + friend class MemorySSA; + + MemoryUse(MemoryAccess *DMA, enum AccessType AT, Instruction *MI, + BasicBlock *BB) + : MemoryAccess(AT, BB), DefiningAccess(nullptr), MemoryInst(MI) { + setDefiningAccess(DMA); + } + virtual void setMemoryInst(Instruction *MI) final { MemoryInst = MI; } + virtual void setDefiningAccess(MemoryAccess *DMA) final { + if (DefiningAccess != DMA) { + if (DefiningAccess) + DefiningAccess->removeUse(this); + if (DMA) + DMA->addUse(this); + } + DefiningAccess = DMA; + } + virtual unsigned int getID() const { + llvm_unreachable("MemoryUse's do not have ID's"); + } + +private: + MemoryAccess *DefiningAccess; + Instruction *MemoryInst; +}; + +/// \brief Represents a read-write access to memory, whether it is a must-alias, +/// or a may-alias. +/// +/// In particular, the set of Instructions that will be represented by +/// MemoryDef's is exactly the set of Instructions for which +/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef". +/// Note that, in order to provide def-def chains, all defs also have a use +/// associated with them. This use points to the nearest reaching +/// MemoryDef/MemoryPhi. +class MemoryDef final : public MemoryUse { +public: + MemoryDef(MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, unsigned Ver) + : MemoryUse(DMA, AccessDef, MI, BB), ID(Ver) {} + + static inline bool classof(const MemoryDef *) { return true; } + static inline bool classof(const MemoryUse *MA) { + return MA->getAccessType() == AccessDef; + } + + static inline bool classof(const MemoryAccess *MA) { + return MA->getAccessType() == AccessDef; + } + virtual void print(raw_ostream &OS) const; + +protected: + friend class MemorySSA; + // For debugging only. This gets used to give memory accesses pretty numbers + // when printing them out + + virtual unsigned int getID() const final { return ID; } + +private: + const unsigned int ID; +}; + +/// \brief Represents phi nodes for memory accesses. +/// +/// These have the same semantic as regular phi nodes, with the exception that +/// only one phi will ever exist in a given basic block. +/// Guaranteeing one phi per block means guaranteeing there is only ever one +/// valid reaching MemoryDef/MemoryPHI along each path to the phi node. +/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or +/// a MemoryPhi's operands. +/// That is, given +/// if (a) { +/// store %a +/// store %b +/// } +/// it *must* be transformed into +/// if (a) { +/// 1 = MemoryDef(liveOnEntry) +/// store %a +/// 2 = MemoryDef(1) +/// store %b +/// } +/// and *not* +/// if (a) { +/// 1 = MemoryDef(liveOnEntry) +/// store %a +/// 2 = MemoryDef(liveOnEntry) +/// store %b +/// } +/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the +/// end of the branch, and if there are not two phi nodes, one will be +/// disconnected completely from the SSA graph below that point. +/// Because MemoryUse's do not generate new definitions, they do not have this +/// issue. +class MemoryPhi final : public MemoryAccess { +public: + MemoryPhi(BasicBlock *BB, unsigned int NP, unsigned int Ver) + : MemoryAccess(AccessPhi, BB), ID(Ver), NumPreds(NP) { + Operands.reserve(NumPreds); + } + + virtual Instruction *getMemoryInst() const final { + llvm_unreachable( + "MemoryPhi's do not have a memory instruction associated with them"); + } + + virtual MemoryAccess *getDefiningAccess() const final { + llvm_unreachable("MemoryPhi's do not have a single defining access"); + } + + /// \brief This is the number of actual predecessors this phi node has. + unsigned int getNumPreds() const { return NumPreds; } + + /// \brief This is the number of incoming values currently in use + /// + /// During SSA construction, we differentiate between this and NumPreds to + /// know when the PHI node is fully constructed. + unsigned int getNumIncomingValues() const { return Operands.size(); } + + /// \brief Set the memory access of argument \p v of this phi node to be \p MA + /// + /// This function updates use lists. + void setIncomingValue(unsigned int v, MemoryAccess *MA) { + std::pair &Val = Operands[v]; + // We need to update use lists. Because our uses are not to specific + // operands, but instead to this MemoryAccess, and because a given memory + // access may appear multiple times in the phi argument list, we need to be + // careful not to remove the use of this phi, from MA, until we check to + // make sure MA does not appear elsewhere in the phi argument list. + if (Val.second != MA) { + if (Val.second) { + bool existsElsewhere = false; + for (unsigned i = 0, e = Operands.size(); i != e; ++i) { + if (i == v) + continue; + if (Operands[i].second == Val.second) + existsElsewhere = true; + } + if (!existsElsewhere) + Val.second->removeUse(this); + } + MA->addUse(this); + Val.second = MA; + } + } + + MemoryAccess *getIncomingValue(unsigned int v) const { + return Operands[v].second; + } + void setIncomingBlock(unsigned int v, BasicBlock *BB) { + std::pair &Val = Operands[v]; + Val.first = BB; + } + BasicBlock *getIncomingBlock(unsigned int v) const { + return Operands[v].first; + } + + typedef SmallVector, 8> OperandsType; + typedef OperandsType::const_iterator const_op_iterator; + inline const_op_iterator ops_begin() const { return Operands.begin(); } + inline const_op_iterator ops_end() const { return Operands.end(); } + inline iterator_range operands() const { + return iterator_range(ops_begin(), ops_end()); + } + + static inline bool classof(const MemoryPhi *) { return true; } + static inline bool classof(const MemoryAccess *MA) { + return MA->getAccessType() == AccessPhi; + } + + virtual void print(raw_ostream &OS) const; + +protected: + friend class MemorySSA; + + virtual void setDefiningAccess(MemoryAccess *) final { + llvm_unreachable("MemoryPhi's do not have a single defining access"); + } + virtual void setMemoryInst(Instruction *MI) final {} + + // MemorySSA currently cannot handle edge additions or deletions (but can + // handle direct replacement). This is protected to ensure people don't try. + void addIncoming(MemoryAccess *MA, BasicBlock *BB) { + Operands.push_back(std::make_pair(BB, MA)); + MA->addUse(this); + } + + // For debugging only. This gets used to give memory accesses pretty numbers + // when printing them out + virtual unsigned int getID() const final { return ID; } + +private: + // For debugging only + const unsigned ID; + unsigned NumPreds; + OperandsType Operands; +}; + +class MemorySSAWalker; + +/// \brief Encapsulates MemorySSA, including all data associated with memory +/// accesses. +class MemorySSA { +public: + MemorySSA(Function &); + ~MemorySSA(); + + /// \brief Build Memory SSA, and return the walker we used during building, + /// for later reuse. If MemorySSA is already built, just return the walker. + MemorySSAWalker *buildMemorySSA(AliasAnalysis *, DominatorTree *); + bool isFinishedBuilding() const { return builtAlready; } + + /// \brief Given a memory Mod/Ref'ing instruction, get the MemorySSA + /// access associaed with it. If passed a basic block gets the memory phi + /// node that exists for that block, if there is one. + MemoryAccess *getMemoryAccess(const Value *) const; + void dump() const; + void print(raw_ostream &) const; + + /// \brief Return true if \p MA represents the live on entry value + /// + /// Loads and stores from pointer arguments and other global values may be + /// defined by memory operations that do not occur in the current function, so + /// they may be live on entry to the function. MemorySSA represents such + /// memory state by the live on entry definition, which is guaranteed to + /// occurr before any other memory access in the function. + inline bool isLiveOnEntryDef(const MemoryAccess *MA) const { + return MA == LiveOnEntryDef; + } + + inline MemoryAccess *getLiveOnEntryDef() const { + assert(LiveOnEntryDef && "Live on entry def not initialized yet"); + return LiveOnEntryDef; + } + + typedef iplist AccessListType; + + /// \brief Return the list of MemoryAccess's for a given basic block. + /// + /// This list is not modifiable by the user. + const AccessListType *getBlockAccesses(const BasicBlock *BB) const { + auto It = PerBlockAccesses.find(BB); + if (It == PerBlockAccesses.end()) + return nullptr; + return It->second.get(); + } + + /// \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 Replace one MemoryAccess with another, including updating all + /// definitions and uses. + /// This should be called when one memory instruction is being replaced with + /// another. For example, during GVN, a load may be replaced with another + /// existing load. This function should be called to let MemorySSA know that + /// this has happened + void replaceMemoryAccess(MemoryAccess *Replacee, MemoryAccess *Replacer); + + enum InsertionPlace { Beginning, End }; + + /// \brief Replace a MemoryAccess with a new access, created based on + /// instruction \p Replacer - this does not perform generic SSA updates, so it + /// only works if the new access dominates the old accesses uses. + /// + /// This API should be used if a new memory instruction has been added that is + /// being used to replace an existing one. For example, during store sinking, + /// we may replace a store sunk further down the CFG. In that + /// case, this function should be called with the MemoryAccess for the + /// original store, and the new instruction replacing it. + /// We may also merge two stores in two branches into a store after the + /// branch. + /// For example, we may have + /// if (a) { + /// 1 = MemoryDef(liveOnEntry) + /// store %a + /// } else { + /// 2 = MemoryDef(liveOnEntry) + /// store %a + /// } + /// 3 = MemoryPhi(1, 2) + /// MemoryUse(3) + /// load %a + /// If the store is sunk below the branch, the correct update would be to call + /// tihs function with the MemoryPhi and the new store, and removeAccess on + /// the two old stores. + /// This version places the access at either the end or the beginning of \p + /// Replacer's block, depending on the value of \p Where. + /// + /// \returns the new access that was created. + MemoryAccess *replaceMemoryAccessWithNewAccess(MemoryAccess *Replacee, + Instruction *Replacer, + enum InsertionPlace Where); + /// \brief Replace a MemoryAccess with a new access, created based on + /// instruction \p Replacer - this does not perform generic SSA updates, so it + /// only works if the new access dominates the old accesses uses. + /// + /// This version places the access before the place that \p Where points to. + MemoryAccess * + replaceMemoryAccessWithNewAccess(MemoryAccess *Replacee, + Instruction *Replacer, + const AccessListType::iterator &Where); + + /// \brief Add a new MemoryUse for \p Use at the beginning or end of a block. + /// + /// This API is used to add MemoryUse's for new loads (or other memory Ref'ing + /// instructions) to MemorySSA. For example, if a load is hoisted and the old + /// load eliminated, the proper update is to call addNewMemoryUse on the new + /// load, and then replaceMemoryAccess with (old load, new load). + MemoryAccess *addNewMemoryUse(Instruction *Use, enum InsertionPlace Where); + + /// \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; + +protected: + // Used by Memory SSA annotater, dumpers, and wrapper pass + friend class MemorySSAAnnotatedWriter; + friend class MemorySSAPrinterPass; + void verifyDefUses(Function &F); + void verifyDomination(Function &F); + +private: + void verifyUseInDefs(MemoryAccess *, MemoryAccess *); + typedef DenseMap> + AccessMap; + + void + determineInsertionPoint(const SmallPtrSetImpl &DefiningBlocks); + void computeDomLevels(DenseMap &DomLevels); + void markUnreachableAsLiveOnEntry(BasicBlock *BB); + bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const; + void removeFromLookups(MemoryAccess *); + MemoryAccess *createNewAccess(Instruction *, bool ignoreNonMemory = false); + MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace); + + MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *); + void renamePass(DomTreeNode *, MemoryAccess *IncomingVal, + SmallPtrSet &Visited); + std::unique_ptr &getOrCreateAccessList(BasicBlock *); + bool replaceAllOccurrences(MemoryPhi *, MemoryAccess *, MemoryAccess *); + AliasAnalysis *AA; + DominatorTree *DT; + Function &F; + + // Memory SSA mappings + DenseMap InstructionToMemoryAccess; + AccessMap PerBlockAccesses; + MemoryAccess *LiveOnEntryDef; + + // Memory SSA building info + unsigned int nextID; + bool builtAlready; + MemorySSAWalker *Walker; +}; + +// 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 MemorySSAPrinterPass : public FunctionPass { +public: + MemorySSAPrinterPass(); + + static char ID; + bool doInitialization(Module &M) override; + bool runOnFunction(Function &) override; + void releaseMemory() override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + void print(raw_ostream &OS, const Module *M) const override; + static void registerOptions(); + MemorySSA &getMSSA() { return *MSSA; } + +private: + bool VerifyMemorySSA; + + MemorySSA *MSSA; + MemorySSAWalker *Walker; + Function *F; +}; + +class MemorySSALazy : public FunctionPass { +public: + MemorySSALazy(); + + static char ID; + bool runOnFunction(Function &) override; + void releaseMemory() override; + MemorySSA &getMSSA() { return *MSSA; } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + } + +private: + MemorySSA *MSSA; +}; + +/// \brief This is the generic walker interface for walkers of MemorySSA. +/// Walkers are used to be able to further disambiguate the def-use chains +/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives +/// you. +/// In particular, while the def-use chains provide basic information, and are +/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a +/// MemoryUse as AliasAnalysis considers it, a user mant want better or other +/// information. In particular, they may want to use SCEV info to further +/// disambiguate memory accesses, or they may want the nearest dominating +/// may-aliasing MemoryDef for a call or a store. This API enables a +/// standardized interface to getting and using that info. + +class MemorySSAWalker { +public: + MemorySSAWalker(MemorySSA *); + virtual ~MemorySSAWalker() {} + + typedef SmallVector MemoryAccessSet; + /// \brief Given a memory Mod/Ref/ModRef'ing instruction, calling this + /// will give you the nearest dominating MemoryAccess that Mod's the location + /// the instruction accesses (by skipping any def which AA can prove does not + /// alias the location(s) accessed by the instruction given). + /// + /// Note that this will return a single access, and it must dominate the + /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction, + /// this will return the MemoryPhi, not the operand. This means that + /// given: + /// if (a) { + /// 1 = MemoryDef(liveOnEntry) + /// store %a + /// } else { + /// 2 = MemoryDef(liveOnEntry) + /// store %b + /// } + /// 3 = MemoryPhi(2, 1) + /// MemoryUse(3) + /// load %a + /// + /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef + /// in the if (a) branch. + virtual MemoryAccess *getClobberingMemoryAccess(const Instruction *) = 0; + + /// \brief Given a potentially clobbering memory access and a new location, + /// calling this will give you the nearest dominating clobbering MemoryAccess + /// (by skipping non-aliasing def links). + /// + /// This version of the function is mainly used to disambiguate phi translated + /// pointers, where the value of a pointer may have changed from the initial + /// memory access. Note that this expects to be handed either a memory use, + /// or an already potentially clobbering access. Unlike the above API, if + /// given a MemoryDef that clobbers the pointer as the starting access, it + /// will return that MemoryDef, whereas the above would return the clobber + /// starting from the use side of the memory def. + virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + MemoryLocation &) = 0; + + /// \brief Given a memory access, invalidate anything this walker knows about + /// that access. + /// This API is used by walkers that store information to perform basic cache + /// invalidation. This will be called by MemorySSA at appropriate times for + /// the walker it uses or returns through getWalker. + virtual void invalidateInfo(MemoryAccess *){}; + +protected: + MemorySSA *MSSA; +}; + +/// \brief A MemorySSAWalker that does no alias queries, or anything else. It +/// simply returns the links as they were constructed by the builder. +class DoNothingMemorySSAWalker final : public MemorySSAWalker { +public: + MemoryAccess *getClobberingMemoryAccess(const Instruction *) override; + MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + MemoryLocation &) override; +}; +typedef std::pair MemoryAccessPair; +typedef std::pair ConstMemoryAccessPair; + +/// \brief A MemorySSAWalker that does AA walks and caching of lookups to +/// disambiguate accesses. +class CachingMemorySSAWalker final : public MemorySSAWalker { +public: + CachingMemorySSAWalker(MemorySSA *, AliasAnalysis *, DominatorTree *); + virtual ~CachingMemorySSAWalker(); + MemoryAccess *getClobberingMemoryAccess(const Instruction *) override; + MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + MemoryLocation &) override; + void invalidateInfo(MemoryAccess *) override; + +protected: + struct UpwardsMemoryQuery; + MemoryAccess *doCacheLookup(const MemoryAccess *, const UpwardsMemoryQuery &, + const MemoryLocation &); + + void doCacheInsert(const MemoryAccess *, MemoryAccess *, + const UpwardsMemoryQuery &, const MemoryLocation &); + + void doCacheRemove(const MemoryAccess *, const UpwardsMemoryQuery &, + const MemoryLocation &); + +private: + MemoryAccessPair UpwardsDFSWalk(MemoryAccess *, const MemoryLocation &, + UpwardsMemoryQuery &, bool); + + MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, + struct UpwardsMemoryQuery &); + bool instructionClobbersQuery(const MemoryDef *, struct UpwardsMemoryQuery &, + const MemoryLocation &Loc) const; + SmallDenseMap + CachedUpwardsClobberingAccess; + DenseMap CachedUpwardsClobberingCall; + AliasAnalysis *AA; + DominatorTree *DT; +}; + +/// \brief Iterator base class used to implement const and non-const iterators +/// over the defining accesses of a MemoryAccess. +template +class memoryaccess_def_iterator_base + : public iterator_facade_base, + std::forward_iterator_tag, T, ptrdiff_t, T *, + T *> { + typedef typename memoryaccess_def_iterator_base::iterator_facade_base BaseT; + +public: + memoryaccess_def_iterator_base(T *Start) : Access(Start), ArgNo(0) {} + memoryaccess_def_iterator_base() : Access(nullptr), ArgNo(0) {} + bool operator==(const memoryaccess_def_iterator_base &Other) const { + if (Access == nullptr) + return Other.Access == nullptr; + return Access == Other.Access && ArgNo == Other.ArgNo; + } + + // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the + // block from the operand in constant time (In a PHINode, the uselist has + // both, so it's just subtraction). We provide it as part of the + // iterator to avoid callers having to linear walk to get the block. + // If the operation becomes constant time on MemoryPHI's, this bit of + // abstraction breaking should be removed. + BasicBlock *getPhiArgBlock() const { + MemoryPhi *MP = dyn_cast(Access); + assert(MP && "Tried to get phi arg block when not iterating over a PHI"); + return MP->getIncomingBlock(ArgNo); + } + typename BaseT::iterator::pointer operator*() const { + assert(Access && "Tried to access past the end of our iterator"); + // Go to the first argument for phis, and the defining access for everything + // else. + if (MemoryPhi *MP = dyn_cast(Access)) + return MP->getIncomingValue(ArgNo); + return Access->getDefiningAccess(); + } + using BaseT::operator++; + memoryaccess_def_iterator &operator++() { + assert(Access && "Hit end of iterator"); + if (MemoryPhi *MP = dyn_cast(Access)) { + if (++ArgNo >= MP->getNumIncomingValues()) { + ArgNo = 0; + Access = nullptr; + } + } else { + Access = nullptr; + } + return *this; + } + +private: + T *Access; + unsigned ArgNo; +}; + +inline memoryaccess_def_iterator MemoryAccess::defs_begin() { + return memoryaccess_def_iterator(this); +} +inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const { + return const_memoryaccess_def_iterator(this); +} + +inline memoryaccess_def_iterator MemoryAccess::defs_end() { + return memoryaccess_def_iterator(); +} + +inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const { + return const_memoryaccess_def_iterator(); +} + +/// \brief GraphTraits for a MemoryAccess, which walks defs in the normal case, +/// and uses in the inverse case. +template <> struct GraphTraits { + typedef MemoryAccess NodeType; + typedef memoryaccess_def_iterator ChildIteratorType; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->defs_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->defs_end(); + } +}; + +template <> struct GraphTraits> { + typedef MemoryAccess NodeType; + typedef MemoryAccess::iterator ChildIteratorType; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->user_begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->user_end(); + } +}; + +/// \brief Provide an iterator that walks defs, giving both the memory access, +/// and the current pointer location, updating the pointer location as it +/// changes due to phi node translation. +/// +/// This iterator, while somewhat specialized, is what most clients actually +/// want when walking upwards through MemorySSA def chains. It takes a pair of +/// , and walks defs, properly translating the +/// memory location through phi nodes for the user. +class upward_defs_iterator + : public iterator_facade_base { + typedef typename upward_defs_iterator::iterator_facade_base BaseT; + +public: + upward_defs_iterator(const MemoryAccessPair &Info) + : DefIterator(Info.first), Location(Info.second), + OriginalAccess(Info.first) { + CurrentPair.first = nullptr; + + if (Info.first) + WalkingPhi = isa(Info.first); + fillInCurrentPair(); + } + upward_defs_iterator() : DefIterator(), Location(), OriginalAccess() { + CurrentPair.first = nullptr; + } + bool operator==(const upward_defs_iterator &Other) const { + return DefIterator == Other.DefIterator; + } + + typename BaseT::iterator::reference operator*() const { + assert(DefIterator != OriginalAccess->defs_end() && + "Tried to access past the end of our iterator"); + return CurrentPair; + } + using BaseT::operator++; + + upward_defs_iterator &operator++() { + assert(DefIterator != OriginalAccess->defs_end() && + "Tried to access past the end of the iterator"); + ++DefIterator; + if (DefIterator != OriginalAccess->defs_end()) + fillInCurrentPair(); + return *this; + } + + BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); } + +private: + void fillInCurrentPair() { + CurrentPair.first = *DefIterator; + if (WalkingPhi && Location.Ptr) { + PHITransAddr Translator( + const_cast(Location.Ptr), + OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr); + if (!Translator.PHITranslateValue(OriginalAccess->getBlock(), + DefIterator.getPhiArgBlock(), nullptr, + false)) + if (Translator.getAddr() != Location.Ptr) { + CurrentPair.second = Location.getWithNewPtr(Translator.getAddr()); + return; + } + } + CurrentPair.second = Location; + } + + MemoryAccessPair CurrentPair; + memoryaccess_def_iterator DefIterator; + MemoryLocation Location; + bool WalkingPhi; + MemoryAccess *OriginalAccess; +}; + +inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) { + return upward_defs_iterator(Pair); +} +inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); } +} + +#endif Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -58,6 +58,8 @@ initializeMemDepPrinterPass(Registry); initializeMemDerefPrinterPass(Registry); initializeMemoryDependenceAnalysisPass(Registry); + initializeMemorySSALazyPass(Registry); + initializeMemorySSAPrinterPassPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializePostDominatorTreePass(Registry); Index: lib/IR/AsmWriter.cpp =================================================================== --- lib/IR/AsmWriter.cpp +++ lib/IR/AsmWriter.cpp @@ -3215,6 +3215,17 @@ // External Interface declarations //===----------------------------------------------------------------------===// +void Function::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW, + bool ShouldPreserveUseListOrder, + bool IsForDebug) const { + SlotTracker SlotTable(this->getParent()); + formatted_raw_ostream OS(ROS); + AssemblyWriter W(OS, SlotTable, this->getParent(), AAW, + IsForDebug, + ShouldPreserveUseListOrder); + W.printFunction(this); +} + void Module::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW, bool ShouldPreserveUseListOrder, bool IsForDebug) const { SlotTracker SlotTable(this); Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -26,6 +26,7 @@ LowerInvoke.cpp LowerSwitch.cpp Mem2Reg.cpp + MemorySSA.cpp MetaRenamer.cpp ModuleUtils.cpp PromoteMemoryToRegister.cpp Index: lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- /dev/null +++ lib/Transforms/Utils/MemorySSA.cpp @@ -0,0 +1,1201 @@ + +//===-- MemorySSA.cpp - Memory SSA Builder---------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------===// +// +// This file implements the MemorySSA class. +// +//===----------------------------------------------------------------===// +#include "llvm/Transforms/Scalar.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/IteratedDominanceFrontier.h" +#include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/IR/AssemblyAnnotationWriter.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FormattedStream.h" +#include "llvm/Transforms/Utils/MemorySSA.h" +#include +#include + +#define DEBUG_TYPE "memoryssa" +using namespace llvm; +STATISTIC(NumClobberCacheLookups, "Number of Memory SSA version cache lookups"); +STATISTIC(NumClobberCacheHits, "Number of Memory SSA version cache hits"); +STATISTIC(NumClobberCacheInserts, "Number of MemorySSA version cache inserts"); +INITIALIZE_PASS_WITH_OPTIONS_BEGIN(MemorySSAPrinterPass, "print-memoryssa", + "Memory SSA", true, true) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) +INITIALIZE_PASS_END(MemorySSAPrinterPass, "print-memoryssa", "Memory SSA", true, + true) +INITIALIZE_PASS(MemorySSALazy, "memoryssalazy", "Memory SSA", true, true) + +namespace llvm { + +/// \brief An assembly annotator class to print Memory SSA information in +/// comments. +class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter { + friend class MemorySSA; + const MemorySSA *MSSA; + +public: + MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {} + + virtual void emitBasicBlockStartAnnot(const BasicBlock *BB, + formatted_raw_ostream &OS) { + MemoryAccess *MA = MSSA->getMemoryAccess(BB); + if (MA) + OS << "; " << *MA << "\n"; + } + + virtual void emitInstructionAnnot(const Instruction *I, + formatted_raw_ostream &OS) { + MemoryAccess *MA = MSSA->getMemoryAccess(I); + if (MA) + OS << "; " << *MA << "\n"; + } +}; +} + +namespace { +struct RenamePassData { + DomTreeNode *DTN; + DomTreeNode::const_iterator ChildIt; + MemoryAccess *IncomingVal; + + RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It, + MemoryAccess *M) + : DTN(D), ChildIt(It), IncomingVal(M) {} + void swap(RenamePassData &RHS) { + std::swap(DTN, RHS.DTN); + std::swap(ChildIt, RHS.ChildIt); + std::swap(IncomingVal, RHS.IncomingVal); + } +}; +} + +namespace llvm { + +/// \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) { + auto It = PerBlockAccesses.find(BB); + // Skip most processing if the list is empty. + if (It != PerBlockAccesses.end()) { + auto &Accesses = It->second; + for (auto &L : *Accesses) { + if (isa(L)) { + IncomingVal = &L; + } else if (MemoryUse *MU = dyn_cast(&L)) { + MU->setDefiningAccess(IncomingVal); + } else if (MemoryDef *MD = dyn_cast(&L)) { + // We can't legally optimize defs, because we only allow single + // memory phis/uses on operations, and if we optimize these, we can + // end up with multiple reaching defs. Uses do not have this + // problem, since they do not produce a value + MD->setDefiningAccess(IncomingVal); + IncomingVal = MD; + } + } + } + + // Pass through values to our successors + for (auto S : successors(BB)) { + auto It = PerBlockAccesses.find(S); + // Rename the phi nodes in our successor block + if (It != PerBlockAccesses.end() && isa(It->second->front())) { + auto &Accesses = It->second; + MemoryPhi *Phi = cast(&Accesses->front()); + unsigned NumEdges = std::count(succ_begin(BB), succ_end(BB), S); + assert(NumEdges && "Must be at least one edge from Succ to BB!"); + for (unsigned i = 0; i != NumEdges; ++i) + Phi->addIncoming(IncomingVal, BB); + } + } + return IncomingVal; +} + +/// \brief This is the standard SSA renaming algorithm. +/// +/// 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) { + SmallVector WorkStack; + IncomingVal = renameBlock(Root->getBlock(), IncomingVal); + WorkStack.push_back({Root, Root->begin(), IncomingVal}); + Visited.insert(Root->getBlock()); + + while (!WorkStack.empty()) { + DomTreeNode *Node = WorkStack.back().DTN; + DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt; + IncomingVal = WorkStack.back().IncomingVal; + + if (ChildIt == Node->end()) { + WorkStack.pop_back(); + } else { + DomTreeNode *Child = *ChildIt; + ++WorkStack.back().ChildIt; + BasicBlock *BB = Child->getBlock(); + Visited.insert(BB); + IncomingVal = renameBlock(BB, IncomingVal); + WorkStack.push_back({Child, Child->begin(), IncomingVal}); + } + } +} + +/// \brief Compute dominator levels, used by the phi insertion algorithm above. +void MemorySSA::computeDomLevels(DenseMap &DomLevels) { + for (auto DFI = df_begin(DT->getRootNode()), DFE = df_end(DT->getRootNode()); + DFI != DFE; ++DFI) + DomLevels[*DFI] = DFI.getPathLength() - 1; +} + +/// \brief This handles unreachable block acccesses by deleting phi nodes in +/// unreachable blocks, and marking all other unreachable MemoryAccess's as +/// being uses of the live on entry definition. +void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) { + assert(!DT->isReachableFromEntry(BB) && + "Reachable block found while handling unreachable blocks"); + + auto It = PerBlockAccesses.find(BB); + if (It == PerBlockAccesses.end()) + return; + + auto &Accesses = It->second; + for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) { + auto Next = std::next(AI); + // If we have a phi, just remove it. We are going to replace all + // users with live on entry. + if (isa(&*AI)) { + Accesses->erase(AI); + } else { + AI->setDefiningAccess(LiveOnEntryDef); + } + AI = Next; + } +} + +MemorySSA::MemorySSA(Function &Func) + : F(Func), LiveOnEntryDef(nullptr), nextID(0), builtAlready(false), + Walker(nullptr) {} + +MemorySSA::~MemorySSA() { + InstructionToMemoryAccess.clear(); + PerBlockAccesses.clear(); + delete LiveOnEntryDef; +} +std::unique_ptr & +MemorySSA::getOrCreateAccessList(BasicBlock *BB) { + auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr)); + if (Res.second) { + Res.first->second = make_unique(); // AccessListType(); + } + return Res.first->second; +} + +MemorySSAWalker *MemorySSA::buildMemorySSA(AliasAnalysis *AA, + DominatorTree *DT) { + if (builtAlready) + return Walker; + else + Walker = new CachingMemorySSAWalker(this, AA, DT); + + this->AA = AA; + this->DT = DT; + + // We create an access to represent "live on entry", for things like + // arguments or users of globals, where the memory they use is defined before + // the beginning of the function. We do not actually insert it in to the IR. + // We do not define a live on exit for the immediate uses, and thus our + // semantics do *not* imply that something with no immediate uses can simply + // be + // removed. + BasicBlock &StartingPoint = F.getEntryBlock(); + LiveOnEntryDef = new MemoryDef(nullptr, nullptr, &StartingPoint, nextID++); + + // We maintain lists of memory accesses per-block, trading memory for time. We + // could just look up the memory access for every possible instruction in the + // stream. + SmallPtrSet DefiningBlocks; + + // Go through each block, figure out where defs occur, and chain together all + // the accesses. + for (auto &B : F) { + AccessListType *Accesses = nullptr; + for (auto &I : B) { + MemoryAccess *MA = createNewAccess(&I, true); + if (!MA) + continue; + if (isa(MA)) + DefiningBlocks.insert(&B); + if (!Accesses) + Accesses = getOrCreateAccessList(&B).get(); + Accesses->push_back(MA); + } + } + + // Determine where our MemoryPhi's should go + IDFCalculator IDFs(*DT); + IDFs.setDefiningBlocks(DefiningBlocks); + SmallVector IDFBlocks; + IDFs.calculate(IDFBlocks); + + // Now place MemoryPhi nodes. + for (auto &BB : IDFBlocks) { + // Insert phi node + auto &Accesses = getOrCreateAccessList(BB); + MemoryPhi *Phi = new MemoryPhi( + BB, std::distance(pred_begin(BB), pred_end(BB)), nextID++); + InstructionToMemoryAccess.insert(std::make_pair(BB, Phi)); + // Phi's always are placed at the front of the block. + Accesses->push_front(Phi); + } + + // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get + // filled in with all blocks. + SmallPtrSet Visited; + renamePass(DT->getRootNode(), LiveOnEntryDef, Visited); + // Now optimize the MemoryUse's defining access to point to the nearest + // dominating clobbering def. + // This ensures that MemoryUse's that are killed by the same store are + // immediate users of that store, one of the invariants we guarantee. + for (auto DomNode : depth_first(DT)) { + BasicBlock *BB = DomNode->getBlock(); + auto AI = PerBlockAccesses.find(BB); + if (AI == PerBlockAccesses.end()) + continue; + auto &Accesses = AI->second; + for (auto &MA : *Accesses) { + if (MemoryUse *MU = dyn_cast(&MA)) { + auto RealVal = Walker->getClobberingMemoryAccess(MU->getMemoryInst()); + MU->setDefiningAccess(RealVal); + } + } + } + + // Mark the uses in unreachable blocks as live on entry, so that they go + // somewhere. + for (auto &BB : F) + if (!Visited.count(&BB)) + markUnreachableAsLiveOnEntry(&BB); + + builtAlready = true; + return Walker; +} + +static MemoryAccess *getDefiningAccess(MemoryAccess *MA) { + if (isa(MA) || isa(MA)) + return MA->getDefiningAccess(); + else + return nullptr; +} +static void setDefiningAccess(MemoryAccess *Of, MemoryAccess *To) { + if (isa(Of) || isa(Of)) + Of->setDefiningAccess(To); +} + +/// \brief Properly remove \p MA from all of MemorySSA's lookup tables. +/// +/// Because of the way the intrusive list and use lists work, it is important to +/// do removal in the right order. +void MemorySSA::removeFromLookups(MemoryAccess *MA) { + assert(MA->user_empty() && + "Trying to remove memory access that still has uses"); + setDefiningAccess(MA, nullptr); + // Invalidate our walker's cache if necessary + if (!isa(MA)) + Walker->invalidateInfo(MA); + // The call below to erase will destroy MA, so we can't change the order we + // are doing things here + Instruction *MemoryInst = MA->getMemoryInst(); + if (MemoryInst) + InstructionToMemoryAccess.erase(MemoryInst); + auto &Accesses = PerBlockAccesses.find(MA->getBlock())->second; + Accesses->erase(MA); + if (Accesses->empty()) { + PerBlockAccesses.erase(MA->getBlock()); + } +} + +/// \brief Helper function to create new memory accesses +MemoryAccess *MemorySSA::createNewAccess(Instruction *I, bool ignoreNonMemory) { + // Find out what affect this instruction has on memory. + ModRefInfo ModRef = AA->getModRefInfo(I); + bool def = false, use = false; + if (ModRef & MRI_Mod) + def = true; + if (ModRef & MRI_Ref) + use = true; + + // It's possible for an instruction to not modify memory at all. During + // construction, we ignore them. + if (ignoreNonMemory && !def && !use) + return nullptr; + + assert((def || use) && + "Trying to create a memory access with a non-memory instruction"); + + if (def) { + MemoryDef *MD = new MemoryDef(nullptr, I, I->getParent(), nextID++); + InstructionToMemoryAccess.insert(std::make_pair(I, MD)); + return MD; + } else if (use) { + MemoryUse *MU = new MemoryUse(nullptr, I, I->getParent()); + InstructionToMemoryAccess.insert(std::make_pair(I, MU)); + return MU; + } + + llvm_unreachable("Not a memory instruction!"); +} + +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 (MemoryAccess *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 (auto RAI = Accesses->rbegin(), RAE = Accesses->rend(); RAI != RAE; + ++RAI) { + if (isa(*RAI) || isa(*RAI)) + return &*RAI; + } + } + CurrNode = CurrNode->getIDom(); + } + return LiveOnEntryDef; +} + +MemoryAccess *MemorySSA::addNewMemoryUse(Instruction *Use, + enum InsertionPlace Where) { + BasicBlock *UseBlock = Use->getParent(); + MemoryAccess *DefiningDef = findDominatingDef(UseBlock, Where); + auto &Accesses = getOrCreateAccessList(UseBlock); + MemoryAccess *MA = createNewAccess(Use); + + // Set starting point, then optimize to get correct answer. + MA->setDefiningAccess(DefiningDef); + auto RealVal = Walker->getClobberingMemoryAccess(MA->getMemoryInst()); + MA->setDefiningAccess(RealVal); + + // Easy case + if (Where == Beginning) { + auto AI = Accesses->begin(); + while (isa(AI)) + ++AI; + Accesses->insert(AI, MA); + } else { + Accesses->push_back(MA); + } + return MA; +} + +MemoryAccess *MemorySSA::replaceMemoryAccessWithNewAccess( + MemoryAccess *Replacee, Instruction *Replacer, enum InsertionPlace Where) { + BasicBlock *ReplacerBlock = Replacer->getParent(); + + auto &Accesses = getOrCreateAccessList(ReplacerBlock); + if (Where == Beginning) { + // Access must go after the first phi + auto AI = Accesses->begin(); + while (AI != Accesses->end()) { + if (!isa(AI)) + break; + ++AI; + } + return replaceMemoryAccessWithNewAccess(Replacee, Replacer, AI); + } else { + return replaceMemoryAccessWithNewAccess(Replacee, Replacer, + Accesses->end()); + } +} + +MemoryAccess *MemorySSA::replaceMemoryAccessWithNewAccess( + MemoryAccess *Replacee, Instruction *Replacer, + const AccessListType::iterator &Where) { + + BasicBlock *ReplacerBlock = Replacer->getParent(); + MemoryAccess *MA = nullptr; + MemoryAccess *DefiningAccess = getDefiningAccess(Replacee); + + // Handle the case we are replacing a phi node, in which case, we don't kill + // the phi node + if (DefiningAccess == nullptr) { + assert(isa(Replacee) && + "Should have been a phi node if we can't get a defining access"); + assert(DT->dominates(Replacee->getBlock(), ReplacerBlock) && + "Need to reuse PHI for defining access, but it will not dominate " + "replacing instruction"); + DefiningAccess = Replacee; + } + + MA = createNewAccess(Replacer); + MA->setDefiningAccess(DefiningAccess); + auto It = PerBlockAccesses.find(ReplacerBlock); + assert(It != PerBlockAccesses.end() && + "Can't use iterator insertion for brand new block"); + auto &Accesses = It->second; + Accesses->insert(Where, MA); + replaceMemoryAccess(Replacee, MA); + return MA; +} + +/// \brief Returns true if \p Replacer dominates \p Replacee . +bool MemorySSA::dominatesUse(const MemoryAccess *Replacer, + const MemoryAccess *Replacee) const { + if (isa(Replacee) || isa(Replacee)) + return DT->dominates(Replacer->getBlock(), Replacee->getBlock()); + const MemoryPhi *MP = cast(Replacee); + // For a phi node, the use occurs in the predecessor block of the phi node. + // Since we may occur multiple times in the phi node, we have to check each + // operand to ensure Replacer dominates each operand where Replacee occurs. + for (const auto &Arg : MP->operands()) + if (Arg.second == Replacee) + if (!DT->dominates(Replacer->getBlock(), Arg.first)) + return false; + return true; +} + +/// \brief Replace all occurrences of \p Replacee with \p Replacer in a PHI +/// node. +/// \return true if we replaced all operands of the phi node. +bool MemorySSA::replaceAllOccurrences(MemoryPhi *P, MemoryAccess *Replacee, + MemoryAccess *Replacer) { + bool ReplacedAllValues = true; + for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { + if (P->getIncomingValue(i) == Replacee) + P->setIncomingValue(i, Replacer); + else + ReplacedAllValues = false; + } + return ReplacedAllValues; +} + +void MemorySSA::replaceMemoryAccess(MemoryAccess *Replacee, + MemoryAccess *Replacer) { + + // If we don't replace all phi node entries, we can't remove it. + bool replacedAllPhiEntries = true; + // If we are replacing a phi node, we may still actually use it, since we + // may now be defined in terms of it. + bool usedByReplacee = getDefiningAccess(Replacer) == Replacee; + + // Just to note: We can replace the live on entry def, unlike removing it, so + // we don't assert here, but it's almost always a bug, unless you are + // inserting a load/store in a block that dominates the rest of the program. + for (auto U : Replacee->users()) { + if (U == Replacer) + continue; + assert(dominatesUse(Replacer, Replacee) && + "Definitions will not dominate uses in replacement!"); + if (MemoryPhi *MP = dyn_cast(U)) { + if (replaceAllOccurrences(MP, Replacee, Replacer)) + replacedAllPhiEntries = true; + } else { + U->setDefiningAccess(Replacer); + } + } + // Kill our dead replacee if it's really dead + if (replacedAllPhiEntries && !usedByReplacee) { + removeFromLookups(Replacee); + } +} + +#ifndef NDEBUG +/// \brief Returns true if a phi is defined by the same value on all edges +static bool onlySingleValue(MemoryPhi *MP) { + MemoryAccess *MA = nullptr; + + for (const auto &Arg : MP->operands()) { + if (!MA) + MA = Arg.second; + else if (MA != Arg.second) + return false; + } + return true; +} +#endif + +void MemorySSA::removeMemoryAccess(MemoryAccess *MA) { + assert(MA != LiveOnEntryDef && "Trying to remove the live on entry def"); + // We can only delete phi nodes if they are use empty + if (MemoryPhi *MP = dyn_cast(MA)) { + // This code only used in assert builds + (void)MP; + assert(MP->user_empty() && "We can't delete memory phis that still have " + "uses, we don't know where the uses should " + "repoint to!"); + assert((MP->user_empty() || onlySingleValue(MP)) && + "This phi still points to multiple values, " + "which means it is still needed"); + } else { + MemoryAccess *DefiningAccess = getDefiningAccess(MA); + // Re-point the uses at our defining access + for (auto U : MA->users()) { + assert(dominatesUse(DefiningAccess, U) && + "Definitions will not dominate uses in removal!"); + if (MemoryPhi *MP = dyn_cast(U)) { + replaceAllOccurrences(MP, MA, DefiningAccess); + } else { + U->setDefiningAccess(DefiningAccess); + } + } + } + + // The call below to erase will destroy MA, so we can't change the order we + // are doing things here + removeFromLookups(MA); +} + +void MemorySSA::print(raw_ostream &OS) const { + MemorySSAAnnotatedWriter Writer(this); + F.print(OS, &Writer); +} + +void MemorySSA::dump() const { + MemorySSAAnnotatedWriter Writer(this); + F.print(dbgs(), &Writer); +} + +/// \brief Verify the domination properties of MemorySSA by checking that each +/// definition dominates all of its uses. +void MemorySSA::verifyDomination(Function &F) { + for (auto &B : F) { + // Phi nodes are attached to basic blocks + MemoryAccess *MA = getMemoryAccess(&B); + if (MA) { + MemoryPhi *MP = cast(MA); + for (const auto &U : MP->users()) { + BasicBlock *UseBlock; + // Phi operands are used on edges, we simulate the right domination by + // acting as if the use occurred at the end of the predecessor block. + if (MemoryPhi *P = dyn_cast(U)) { + for (const auto &Arg : P->operands()) { + if (Arg.second == MP) { + UseBlock = Arg.first; + break; + } + } + } else { + UseBlock = U->getBlock(); + } + assert(DT->dominates(MP->getBlock(), UseBlock) && + "Memory PHI does not dominate it's uses"); + } + } + for (auto &I : B) { + MA = getMemoryAccess(&I); + if (MA) { + if (MemoryDef *MD = dyn_cast(MA)) + for (const auto &U : MD->users()) { + BasicBlock *UseBlock; + // Things are allowed to flow to phi nodes over their predecessor + // edge. + if (MemoryPhi *P = dyn_cast(U)) { + for (const auto &Arg : P->operands()) { + if (Arg.second == MD) { + UseBlock = Arg.first; + break; + } + } + } else { + UseBlock = U->getBlock(); + } + assert(DT->dominates(MD->getBlock(), UseBlock) && + "Memory Def does not dominate it's uses"); + } + } + } + } +} + +/// \brief Verify the def-use lists in MemorySSA, by verifying that \p Use +/// appears in the use list of \p Def. +void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) { + // The live on entry use may cause us to get a NULL def here + if (Def == nullptr) { + assert(isLiveOnEntryDef(Use) && + "Null def but use not point to live on entry def"); + return; + } + assert(Def->hasUse(Use) && "Did not find use in def's use list"); +} + +/// \brief Verify the immediate use information, by walking all the memory +/// accesses and verifying that, for each use, it appears in the +/// appropriate def's use list +void MemorySSA::verifyDefUses(Function &F) { + for (auto &B : F) { + // Phi nodes are attached to basic blocks + MemoryAccess *MA = getMemoryAccess(&B); + if (MA) { + assert(isa(MA) && + "Something other than phi node on basic block"); + MemoryPhi *MP = cast(MA); + for (unsigned i = 0, e = MP->getNumIncomingValues(); i != e; ++i) + verifyUseInDefs(MP->getIncomingValue(i), MP); + } + for (auto &I : B) { + MA = getMemoryAccess(&I); + if (MA) { + if (MemoryPhi *MP = dyn_cast(MA)) { + for (unsigned i = 0, e = MP->getNumIncomingValues(); i != e; ++i) + verifyUseInDefs(MP->getIncomingValue(i), MP); + } else { + verifyUseInDefs(MA->getDefiningAccess(), MA); + } + } + } + } +} + +MemoryAccess *MemorySSA::getMemoryAccess(const Value *I) const { + return InstructionToMemoryAccess.lookup(I); +} + +/// \brief Determine, for two memory accesses in the same block, +/// whether \p Dominator dominates \p Dominatee. +/// \returns True if \p Dominator dominates \p Dominatee. +bool MemorySSA::locallyDominates(const MemoryAccess *Dominator, + const MemoryAccess *Dominatee) const { + + assert((Dominator->getBlock() == Dominatee->getBlock()) && + "Asking for local domination when accesses are in different blocks!"); + // Get the access list for the block + const auto *AccessList = getBlockAccesses(Dominator->getBlock()); + AccessListType::const_reverse_iterator It(Dominator->getIterator()); + + // If we hit the beginning of the access list before we hit dominatee, we must + // dominate it + while (It != AccessList->rend()) { + if (&*It == Dominatee) + return false; + ++It; + } + return true; +} + +void MemoryDef::print(raw_ostream &OS) const { + MemoryAccess *UO = getDefiningAccess(); + + OS << getID() << " = " + << "MemoryDef("; + if (UO && UO->getID() != 0) + OS << UO->getID(); + else + OS << "liveOnEntry"; + OS << ")"; +} + +void MemoryPhi::print(raw_ostream &OS) const { + OS << getID() << " = " + << "MemoryPhi("; + for (unsigned int i = 0, e = getNumIncomingValues(); i != e; ++i) { + BasicBlock *BB = getIncomingBlock(i); + MemoryAccess *MA = getIncomingValue(i); + OS << "{"; + if (BB->hasName()) + OS << BB->getName(); + else + BB->printAsOperand(OS, false); + OS << ","; + assert((isa(MA) || isa(MA)) && + "Phi node should have referred to def or another phi"); + if (MA->getID() != 0) + OS << MA->getID(); + else + OS << "liveOnEntry"; + OS << "}"; + if (i + 1 < e) + OS << ","; + } + OS << ")"; +} + +MemoryAccess::~MemoryAccess() {} + +void MemoryUse::print(raw_ostream &OS) const { + MemoryAccess *UO = getDefiningAccess(); + OS << "MemoryUse("; + if (UO && UO->getID() != 0) + OS << UO->getID(); + else + OS << "liveOnEntry"; + OS << ")"; +} + +void MemoryAccess::dump() const { + print(dbgs()); + dbgs() << "\n"; +} + +char MemorySSAPrinterPass::ID = 0; + +MemorySSAPrinterPass::MemorySSAPrinterPass() : FunctionPass(ID) { + initializeMemorySSAPrinterPassPass(*PassRegistry::getPassRegistry()); +} + +void MemorySSAPrinterPass::releaseMemory() { + delete MSSA; + delete Walker; +} + +void MemorySSAPrinterPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); +} + +bool MemorySSAPrinterPass::doInitialization(Module &M) { + + VerifyMemorySSA = + M.getContext() + .template getOption(); + return false; +} + +void MemorySSAPrinterPass::registerOptions() { + OptionRegistry::registerOption( + "verify-memoryssa", "Run the Memory SSA verifier", false); +} + +void MemorySSAPrinterPass::print(raw_ostream &OS, const Module *M) const { + MSSA->print(OS); +} + +bool MemorySSAPrinterPass::runOnFunction(Function &F) { + this->F = &F; + MSSA = new MemorySSA(F); + AliasAnalysis *AA = &getAnalysis().getAAResults(); + DominatorTree *DT = &getAnalysis().getDomTree(); + Walker = MSSA->buildMemorySSA(AA, DT); + + if (VerifyMemorySSA) { + MSSA->verifyDefUses(F); + MSSA->verifyDomination(F); + } + + return false; +} + +char MemorySSALazy::ID = 0; + +MemorySSALazy::MemorySSALazy() : FunctionPass(ID) { + initializeMemorySSALazyPass(*PassRegistry::getPassRegistry()); +} + +void MemorySSALazy::releaseMemory() { delete MSSA; } + +bool MemorySSALazy::runOnFunction(Function &F) { + MSSA = new MemorySSA(F); + return false; +} + +MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {} + +CachingMemorySSAWalker::CachingMemorySSAWalker(MemorySSA *M, AliasAnalysis *A, + DominatorTree *D) + : MemorySSAWalker(M), AA(A), DT(D) {} + +CachingMemorySSAWalker::~CachingMemorySSAWalker() { + CachedUpwardsClobberingAccess.clear(); + CachedUpwardsClobberingCall.clear(); +} + +struct CachingMemorySSAWalker::UpwardsMemoryQuery { + // True if we saw a phi whose predecessor was a backedge + bool SawBackedgePhi; + // True if our original query started off as a call + bool isCall; + // The pointer location we started the query with. This will be + // empty if isCall is true. + MemoryLocation StartingLoc; + // This is the instruction we were querying about. + const Instruction *Inst; + // Set of visited Instructions for this query. + DenseSet Visited; + // Set of visited call accesses for this query This is separated out because + // you can always cache and lookup the result of call queries (IE when + // isCall == true) for every call in the chain. The calls have no AA + // location associated with them with them, and thus, no context dependence. + SmallPtrSet VisitedCalls; + // The MemoryAccess we actually got called with, used to test local domination + const MemoryAccess *OriginalAccess; + // The Datalayout for the module we started in + const DataLayout *DL; +}; + +void CachingMemorySSAWalker::doCacheRemove(const MemoryAccess *M, + const UpwardsMemoryQuery &Q, + const MemoryLocation &Loc) { + if (Q.isCall) + CachedUpwardsClobberingCall.erase(M); + else + CachedUpwardsClobberingAccess.erase({M, Loc}); +} + +void CachingMemorySSAWalker::doCacheInsert(const MemoryAccess *M, + MemoryAccess *Result, + const UpwardsMemoryQuery &Q, + const MemoryLocation &Loc) { + ++NumClobberCacheInserts; + if (Q.isCall) + CachedUpwardsClobberingCall[M] = Result; + else + CachedUpwardsClobberingAccess[{M, Loc}] = Result; +} + +MemoryAccess *CachingMemorySSAWalker::doCacheLookup(const MemoryAccess *M, + const UpwardsMemoryQuery &Q, + const MemoryLocation &Loc) { + ++NumClobberCacheLookups; + MemoryAccess *Result = nullptr; + + if (Q.isCall) + Result = CachedUpwardsClobberingCall.lookup(M); + else + Result = CachedUpwardsClobberingAccess.lookup({M, Loc}); + + if (Result) { + ++NumClobberCacheHits; + return Result; + } + return nullptr; +} + +/// \brief Return true if \p QueryInst could possibly have a Mod result with \p +/// DefInst. +static bool possiblyAffectedBy(const Instruction *QueryInst, + const Instruction *DefInst) { + if (isa(DefInst) && isa(QueryInst)) { + const LoadInst *DefLI = cast(DefInst); + const LoadInst *QueryLI = cast(QueryInst); + // A non-volatile load can't be clobbered by a volatile one unless the + // volatile one is ordered. + if (!QueryLI->isVolatile() && DefLI->isVolatile()) + return DefLI->getOrdering() > Unordered; + } + return true; +} + +bool CachingMemorySSAWalker::instructionClobbersQuery( + const MemoryDef *MD, struct UpwardsMemoryQuery &Q, + const MemoryLocation &Loc) const { + Instruction *DefMemoryInst = MD->getMemoryInst(); + assert(DefMemoryInst && "Defining instruction not actually an instruction"); + + if (!Q.isCall) { + // Okay, well, see if it's a volatile load vs non-volatile load + // situation. + if (possiblyAffectedBy(Q.Inst, DefMemoryInst)) + // Check whether our memory location is modified by this instruction + if (AA->getModRefInfo(DefMemoryInst, Loc) & MRI_Mod) + return true; + } else { + // If this is a call, try then mark it for caching + if (ImmutableCallSite(DefMemoryInst)) { + Q.VisitedCalls.insert(MD); + } + if (AA->getModRefInfo(DefMemoryInst, ImmutableCallSite(Q.Inst)) != + MRI_NoModRef) + return true; + } + return false; +} + +MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk( + MemoryAccess *StartingAccess, const MemoryLocation &Loc, + UpwardsMemoryQuery &Q, bool FollowingBackedge) { + MemoryAccess *ModifyingAccess = nullptr; + + auto DFI = df_begin(StartingAccess); + for (auto DFE = df_end(StartingAccess); DFI != DFE;) { + MemoryAccess *CurrAccess = *DFI; + if (MSSA->isLiveOnEntryDef(CurrAccess)) + return {CurrAccess, Loc}; + if (auto CacheResult = doCacheLookup(CurrAccess, Q, Loc)) { + return {CacheResult, Loc}; + } + // If this is a MemoryDef, check whether it clobbers our current query. + if (MemoryDef *MD = dyn_cast(CurrAccess)) { + // If we hit the top, stop following this path + // While we can do lookups, we can't sanely do inserts here unless we + // were to track every thing we saw along the way, since we don't + // know where we will stop. + if (instructionClobbersQuery(MD, Q, Loc)) { + ModifyingAccess = CurrAccess; + break; + } + } + // We need to know whether it is a phi so we can track backedges. + // Otherwise, walk all upward defs. + bool IsPhi = isa(CurrAccess); + // Recurse on PHI nodes, since we need to change locations. + // TODO: Allow graphtraits on pairs, which would turn this whole function + // into a normal single depth first walk. + if (IsPhi) { + MemoryAccess *FirstDef = nullptr; + DFI = DFI.skipChildren(); + const MemoryAccessPair PHIPair(CurrAccess, Loc); + bool VisitedOnlyOne = true; + for (auto MPI = upward_defs_begin(PHIPair), MPE = upward_defs_end(); + MPI != MPE; ++MPI) { + bool Backedge = false; + // Don't follow this path again if we've followed it once + if (!Q.Visited.insert(*MPI).second) + continue; + + if (IsPhi && !FollowingBackedge && + DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock())) + Backedge = true; + MemoryAccessPair CurrentPair = + UpwardsDFSWalk(MPI->first, MPI->second, Q, Backedge); + // All the phi arguments should reach the same point if we can bypass + // this phi. The alternative is that they hit this phi node, which + // means we can skip this argument. + if (FirstDef && (CurrentPair.first != PHIPair.first && + CurrentPair.first != FirstDef)) { + ModifyingAccess = CurrAccess; + break; + } else if (!FirstDef) { + FirstDef = CurrentPair.first; + } else { + VisitedOnlyOne = false; + } + } + // The above loop determines if all arguments of the phi node reach the + // same place. However we skip arguments that are cyclically dependent + // only on the value of this phi node. This means in some cases, we may + // only visit one argument of the phi node, and the above loop will + // happily say that all the arguments are the same. However, in that case, + // we still can't walk past the phi node, because that argument still + // kills the access unless we hit the top of the function when walking + // that argument. + if (VisitedOnlyOne && FirstDef && !MSSA->isLiveOnEntryDef(FirstDef)) + ModifyingAccess = CurrAccess; + } else { + // You can't call skipchildren and also increment the iterator + ++DFI; + } + } + if (!ModifyingAccess) + return {MSSA->getLiveOnEntryDef(), Q.StartingLoc}; + const BasicBlock *OriginalBlock = Q.OriginalAccess->getBlock(); + unsigned N = DFI.getPathLength(); + MemoryAccess *FinalAccess = ModifyingAccess; + + for (; N != 0; --N) { + ModifyingAccess = DFI.getPath(N - 1); + BasicBlock *CurrBlock = ModifyingAccess->getBlock(); + if (!FollowingBackedge) + doCacheInsert(ModifyingAccess, FinalAccess, Q, Loc); + if (DT->dominates(CurrBlock, OriginalBlock) && + (CurrBlock != OriginalBlock || !FollowingBackedge || + MSSA->locallyDominates(ModifyingAccess, Q.OriginalAccess))) + break; + } + // Cache everything else on the way back + for (; N != 0; --N) { + MemoryAccess *CacheAccess = DFI.getPath(N - 1); + doCacheInsert(CacheAccess, ModifyingAccess, Q, Loc); + } + assert(Q.Visited.size() < 1000 && "Visited too much"); + + return {ModifyingAccess, Loc}; +} + +/// \brief Walk the use-def chains starting at \p MA and find +/// the MemoryAccess that actually clobbers Loc. +/// +/// \returns our clobbering memory access + +MemoryAccess *CachingMemorySSAWalker::getClobberingMemoryAccess( + MemoryAccess *StartingAccess, struct UpwardsMemoryQuery &Q) { + return UpwardsDFSWalk(StartingAccess, Q.StartingLoc, Q, false).first; +} + +MemoryAccess * +CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess, + MemoryLocation &Loc) { + if (isa(StartingAccess)) + return StartingAccess; + if (MSSA->isLiveOnEntryDef(StartingAccess)) + return StartingAccess; + + Instruction *I = StartingAccess->getMemoryInst(); + + struct UpwardsMemoryQuery Q; + // Conservatively, fences are always clobbers, so don't perform the walk if we + // hit a fence. + if (isa(I)) + return StartingAccess; + + Q.OriginalAccess = StartingAccess; + Q.StartingLoc = Loc; + Q.Inst = StartingAccess->getMemoryInst(); + Q.isCall = false; + Q.DL = &Q.Inst->getParent()->getModule()->getDataLayout(); + + auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc); + if (CacheResult) + return CacheResult; + + // Unlike the other function, do not walk to the def of a def, because we are + // handed + // something we already believe is the clobbering access. + if (isa(StartingAccess)) + StartingAccess = StartingAccess->getDefiningAccess(); + + MemoryAccess *FinalAccess = getClobberingMemoryAccess(StartingAccess, Q); + doCacheInsert(Q.OriginalAccess, FinalAccess, Q, Q.StartingLoc); + DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is "); + DEBUG(dbgs() << *StartingAccess << "\n"); + DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is "); + DEBUG(dbgs() << *FinalAccess << "\n"); + + return FinalAccess; +} + +MemoryAccess * +CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) { + + MemoryAccess *StartingAccess = MSSA->getMemoryAccess(I); + + // There should be no way to lookup an instruction and get a phi as the + // access, since we only map BB's to PHI's. + assert(!isa(StartingAccess)); + + struct UpwardsMemoryQuery Q; + Q.OriginalAccess = StartingAccess; + + // First extract our location, then start walking until it is + // clobbered + // For calls, we store the call instruction we started with in + // Loc.Ptr + MemoryLocation Loc(I); + // We can't sanely do anything with a FenceInst, they conservatively + // clobber all memory, and have no locations to get pointers from to + // try to disambiguate + if (isa(I)) { + return StartingAccess; + } else if (ImmutableCallSite(I)) { + Q.isCall = true; + Q.Inst = I; + } else { + Q.isCall = false; + Q.StartingLoc = MemoryLocation::get(I); + Q.Inst = I; + } + Q.DL = &Q.Inst->getParent()->getModule()->getDataLayout(); + auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc); + if (CacheResult) + return CacheResult; + + // Short circuit invariant loads + if (const LoadInst *LI = dyn_cast(I)) + if (LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr) { + doCacheInsert(StartingAccess, MSSA->getLiveOnEntryDef(), Q, + Q.StartingLoc); + return MSSA->getLiveOnEntryDef(); + } + + // Start with the thing we already think clobbers this location + StartingAccess = StartingAccess->getDefiningAccess(); + + // At this point, StartingAccess may be the live on entry def. + // If it is, we will not get a better result. + if (MSSA->isLiveOnEntryDef(StartingAccess)) + return StartingAccess; + MemoryAccess *FinalAccess = getClobberingMemoryAccess(StartingAccess, Q); + + doCacheInsert(Q.OriginalAccess, FinalAccess, Q, Q.StartingLoc); + if (Q.isCall) { + for (const auto &C : Q.VisitedCalls) + doCacheInsert(C, FinalAccess, Q, Q.StartingLoc); + } + + DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is "); + DEBUG(dbgs() << *StartingAccess << "\n"); + DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is "); + DEBUG(dbgs() << *FinalAccess << "\n"); + + return FinalAccess; +} + +void CachingMemorySSAWalker::invalidateInfo(MemoryAccess *MA) { + UpwardsMemoryQuery Q; + if (!isa(MA)) { + Instruction *I = MA->getMemoryInst(); + if (ImmutableCallSite(I)) { + Q.isCall = true; + Q.Inst = I; + } else { + Q.isCall = false; + Q.StartingLoc = MemoryLocation::get(I); + Q.Inst = I; + } + } + + doCacheRemove(MA, Q, Q.StartingLoc); +} + +MemoryAccess * +DoNothingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) { + MemoryAccess *MA = MSSA->getMemoryAccess(I); + if (isa(MA)) + return MA; + return MA->getDefiningAccess(); +} + +MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess( + MemoryAccess *StartingAccess, MemoryLocation &) { + if (isa(StartingAccess)) + return StartingAccess; + return StartingAccess->getDefiningAccess(); +} +} Index: test/Transforms/Util/memoryssa-cyclicphi.ll =================================================================== --- /dev/null +++ test/Transforms/Util/memoryssa-cyclicphi.ll @@ -0,0 +1,39 @@ +; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1| FileCheck %s + +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" + +%struct.hoge = type { i32, %struct.widget } +%struct.widget = type { i64 } +define hidden void @quux(%struct.hoge *%f) align 2 { + %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0 + %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1 + %tmp25 = bitcast %struct.widget* %tmp24 to i64** + br label %bb26 + +bb26: ; preds = %bb77, %0 +; CHECK: 3 = MemoryPhi({%0,liveOnEntry},{bb77,2}) +; 3 = MemoryPhi({%0,liveOnEntry},{bb77,2}) +; CHECK-NEXT: br i1 undef, label %bb68, label %bb77 + br i1 undef, label %bb68, label %bb77 + +bb68: ; preds = %bb26 +; CHECK: MemoryUse(liveOnEntry) +; MemoryUse(liveOnEntry) +; CHECK-NEXT: %tmp69 = load i64, i64* null, align 8 + %tmp69 = load i64, i64* null, align 8 +; CHECK: 1 = MemoryDef(3) +; 1 = MemoryDef(3) +; CHECK-NEXT: store i64 %tmp69, i64* %tmp, align 8 + store i64 %tmp69, i64* %tmp, align 8 + br label %bb77 + +bb77: ; preds = %bb68, %bb26 +; CHECK: 2 = MemoryPhi({bb26,3},{bb68,1}) +; 2 = MemoryPhi({bb26,3},{bb68,1}) +; CHECK: MemoryUse(2) +; MemoryUse(2) +; CHECK-NEXT: %tmp78 = load i64*, i64** %tmp25, align 8 + %tmp78 = load i64*, i64** %tmp25, align 8 + %tmp79 = getelementptr inbounds i64, i64* %tmp78, i64 undef + br label %bb26 +} Index: test/Transforms/Util/memoryssa-no-disconnected.ll =================================================================== --- /dev/null +++ test/Transforms/Util/memoryssa-no-disconnected.ll @@ -0,0 +1,48 @@ +; RUN: opt -basicaa -print-memoryssa -analyze -verify-memoryssa < %s 2>&1| FileCheck %s +; This test ensures we don't end up with multiple reaching defs for a single use/phi edge +; If we were to optimize defs, we would end up with 2= MemoryDef(liveOnEntry) and 4 = MemoryDef(liveOnEntry) +; Both would mean both 1,2, and 3,4 would reach the phi node. Because the phi node can only have one entry +; on each edge, it would choose 2, 4 and disconnect 1 and 3 completely from the SSA graph, even though they +; are not dead +target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" +define void @sink_store(i32 %index, i32* noalias nocapture %foo, i32* noalias nocapture %bar) { +entry: + %cmp = trunc i32 %index to i1 + br i1 %cmp, label %if.then, label %if.else + +if.then: ; preds = %entry +; CHECK: 1 = MemoryDef(liveOnEntry) +; 1 = MemoryDef(liveOnEntry) +; CHECK-NEXT: store i32 %index, i32* %foo, align 4, !alias.scope !0 + store i32 %index, i32* %foo, align 4, !alias.scope !0 +; CHECK: 2 = MemoryDef(1) +; 2 = MemoryDef(1) +; CHECK-NEXT: store i32 %index, i32* %bar, align 4, !noalias !0 + store i32 %index, i32* %bar, align 4, !noalias !0 + br label %if.end + +if.else: ; preds = %entry +; CHECK: 3 = MemoryDef(liveOnEntry) +; 3 = MemoryDef(liveOnEntry) +; CHECK-NEXT: store i32 %index, i32* %foo, align 4, !alias.scope !0 + store i32 %index, i32* %foo, align 4, !alias.scope !0 +; CHECK: 4 = MemoryDef(3) +; 4 = MemoryDef(3) +; CHECK-NEXT: store i32 %index, i32* %bar, align 4, !noalias !0 + store i32 %index, i32* %bar, align 4, !noalias !0 + br label %if.end + +if.end: ; preds = %if.else, %if.then +; CHECK: 5 = MemoryPhi({if.then,2},{if.else,4}) +; 5 = MemoryPhi({if.then,2},{if.else,4}) +; CHECK: MemoryUse(5) +; MemoryUse(5) +; CHECK-NEXT: %c = load i32, i32* %foo, !alias.scope !0 + %c = load i32, i32* %foo, !alias.scope !0 +; CHECK: MemoryUse(5) +; MemoryUse(5) +; CHECK-NEXT: %d = load i32, i32* %bar, !noalias !0 + %d = load i32, i32* %bar, !noalias !0 + ret void +} +!0 = !{!0} Index: test/Transforms/Util/memoryssa-optimize-use.ll =================================================================== --- /dev/null +++ test/Transforms/Util/memoryssa-optimize-use.ll @@ -0,0 +1,54 @@ +; RUN: opt -basicaa -print-memoryssa -analyze -verify-memoryssa < %s 2>&1| FileCheck %s + +target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" +; Function Attrs: ssp uwtable +define i32 @main() #0 { +entry: +; CHECK: 1 = MemoryDef(liveOnEntry) +; 1 = MemoryDef(liveOnEntry) +; CHECK-NEXT: %call = call noalias i8* @_Znwm(i64 4) #2 + %call = call noalias i8* @_Znwm(i64 4) #2 + %0 = bitcast i8* %call to i32* +; CHECK: 2 = MemoryDef(1) +; 2 = MemoryDef(1) +; CHECK-NEXT: %call1 = call noalias i8* @_Znwm(i64 4) #2 + %call1 = call noalias i8* @_Znwm(i64 4) #2 + %1 = bitcast i8* %call1 to i32* +; CHECK: 3 = MemoryDef(2) +; 3 = MemoryDef(2) +; CHECK-NEXT: store i32 5, i32* %0, align 4 + store i32 5, i32* %0, align 4 +; CHECK: 4 = MemoryDef(3) +; 4 = MemoryDef(3) +; CHECK-NEXT: store i32 7, i32* %1, align 4 + store i32 7, i32* %1, align 4 +; CHECK: MemoryUse(3) +; MemoryUse(3) +; CHECK-NEXT: %2 = load i32, i32* %0, align 4 + %2 = load i32, i32* %0, align 4 +; CHECK: MemoryUse(4) +; MemoryUse(4) +; CHECK-NEXT: %3 = load i32, i32* %1, align 4 + %3 = load i32, i32* %1, align 4 +; CHECK: MemoryUse(3) +; MemoryUse(3) +; CHECK-NEXT: %4 = load i32, i32* %0, align 4 + %4 = load i32, i32* %0, align 4 +; CHECK: MemoryUse(4) +; MemoryUse(4) +; CHECK-NEXT: %5 = load i32, i32* %1, align 4 + %5 = load i32, i32* %1, align 4 + %add = add nsw i32 %3, %5 + ret i32 %add +} +declare noalias i8* @_Znwm(i64) #1 + +attributes #0 = { ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { nobuiltin "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #2 = { builtin } + +!llvm.module.flags = !{!0} +!llvm.ident = !{!1} + +!0 = !{i32 1, !"PIC Level", i32 2} +!1 = !{!"clang version 3.7.0 (http://llvm.org/git/clang.git c9903b44534b8b5debcdbe375ee5c1fec6cc7243) (llvm/trunk 228022)"}