diff options
Diffstat (limited to 'llvm')
31 files changed, 834 insertions, 33 deletions
diff --git a/llvm/docs/LangRef.rst b/llvm/docs/LangRef.rst index 885da869da3..ddbf4003494 100644 --- a/llvm/docs/LangRef.rst +++ b/llvm/docs/LangRef.rst @@ -2829,6 +2829,59 @@ Note that the fields need not be contiguous. In this example, there is a 4 byte gap between the two fields. This gap represents padding which does not carry useful data and need not be preserved. +'``noalias``' and '``alias.scope``' Metadata +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +``noalias`` and ``alias.scope`` metadata provide the ability to specify generic +noalias memory-access sets. This means that some collection of memory access +instructions (loads, stores, memory-accessing calls, etc.) that carry +``noalias`` metadata can specifically be specified not to alias with some other +collection of memory access instructions that carry ``alias.scope`` metadata. +Each type of metadata specifies a list of scopes, and when evaluating an +aliasing query, if one of the instructions has a scope in its ``alias.scope`` +list that is identical to a scope in the other instruction's ``noalias`` list, +or is a descendant (in the scope hierarchy) of a scope in the other +instruction's ``noalias`` list , then the two memory accesses are assumed not +to alias. + +The metadata identifying each scope is itself a list containing one or two +entries. The first entry is the name of the scope. Note that if the name is a +string then it can be combined accross functions and translation units. A +self-reference can be used to create globally unique scope names. +Optionally, a metadata reference to a parent scope can be provided as a second +entry in the list. + +For example, + +.. code-block:: llvm + + ; A root scope (which doubles as a list of itself): + !0 = metadata !{metadata !0} + + ; Two child scopes (which must be self-referential to avoid being "uniqued"): + !1 = metadata !{metadata !2} ; A list containing only scope !2 + !2 = metadata !{metadata !2, metadata !0} ; Scope !2 is a descendant of scope !0 + + !3 = metadata !{metadata !4} ; A list containing only scope !4 + !4 = metadata !{metadata !4, metadata !0} ; Scope !4 is a descendant of scope !0 + + ; These two instructions don't alias: + %0 = load float* %c, align 4, !alias.scope !0 + store float %0, float* %arrayidx.i, align 4, !noalias !0 + + ; These two instructions may alias (scope !2 and scope !4 are peers): + %2 = load float* %c, align 4, !alias.scope !1 + store float %2, float* %arrayidx.i2, align 4, !noalias !3 + + ; These two instructions don't alias (scope !2 is a descendant of scope !0 + ; and the store does not alias with anything in scope !0 or any of its descendants): + %2 = load float* %c, align 4, !alias.scope !1 + store float %0, float* %arrayidx.i, align 4, !noalias !0 + + ; These two instructions may alias: + %2 = load float* %c, align 4, !alias.scope !0 + store float %0, float* %arrayidx.i, align 4, !noalias !1 + '``fpmath``' Metadata ^^^^^^^^^^^^^^^^^^^^^ diff --git a/llvm/include/llvm-c/Transforms/Scalar.h b/llvm/include/llvm-c/Transforms/Scalar.h index 0ca72cec0cd..c0d670e3050 100644 --- a/llvm/include/llvm-c/Transforms/Scalar.h +++ b/llvm/include/llvm-c/Transforms/Scalar.h @@ -132,6 +132,9 @@ void LLVMAddLowerExpectIntrinsicPass(LLVMPassManagerRef PM); /** See llvm::createTypeBasedAliasAnalysisPass function */ void LLVMAddTypeBasedAliasAnalysisPass(LLVMPassManagerRef PM); +/** See llvm::createScopedNoAliasAAPass function */ +void LLVMAddScopedNoAliasAAPass(LLVMPassManagerRef PM); + /** See llvm::createBasicAliasAnalysisPass function */ void LLVMAddBasicAliasAnalysisPass(LLVMPassManagerRef PM); diff --git a/llvm/include/llvm/Analysis/Passes.h b/llvm/include/llvm/Analysis/Passes.h index fd65ae5ca5b..683c1797ae4 100644 --- a/llvm/include/llvm/Analysis/Passes.h +++ b/llvm/include/llvm/Analysis/Passes.h @@ -88,6 +88,13 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createScopedNoAliasAAPass - This pass implements metadata-based + // scoped noalias analysis. + // + ImmutablePass *createScopedNoAliasAAPass(); + + //===--------------------------------------------------------------------===// + // // createObjCARCAliasAnalysisPass - This pass implements ObjC-ARC-based // alias analysis. // diff --git a/llvm/include/llvm/IR/IRBuilder.h b/llvm/include/llvm/IR/IRBuilder.h index aed2463d42d..6134f866a03 100644 --- a/llvm/include/llvm/IR/IRBuilder.h +++ b/llvm/include/llvm/IR/IRBuilder.h @@ -364,43 +364,60 @@ public: /// \brief Create and insert a memset to the specified pointer and the /// specified value. /// - /// If the pointer isn't an i8*, it will be converted. If a TBAA tag is - /// specified, it will be added to the instruction. + /// If the pointer isn't an i8*, it will be converted. If a TBAA tag is + /// specified, it will be added to the instruction. Likewise with alias.scope + /// and noalias tags. CallInst *CreateMemSet(Value *Ptr, Value *Val, uint64_t Size, unsigned Align, - bool isVolatile = false, MDNode *TBAATag = nullptr) { - return CreateMemSet(Ptr, Val, getInt64(Size), Align, isVolatile, TBAATag); + bool isVolatile = false, MDNode *TBAATag = nullptr, + MDNode *ScopeTag = nullptr, + MDNode *NoAliasTag = nullptr) { + return CreateMemSet(Ptr, Val, getInt64(Size), Align, isVolatile, + TBAATag, ScopeTag, NoAliasTag); } CallInst *CreateMemSet(Value *Ptr, Value *Val, Value *Size, unsigned Align, - bool isVolatile = false, MDNode *TBAATag = nullptr); + bool isVolatile = false, MDNode *TBAATag = nullptr, + MDNode *ScopeTag = nullptr, + MDNode *NoAliasTag = nullptr); /// \brief Create and insert a memcpy between the specified pointers. /// /// If the pointers aren't i8*, they will be converted. If a TBAA tag is - /// specified, it will be added to the instruction. + /// specified, it will be added to the instruction. Likewise with alias.scope + /// and noalias tags. CallInst *CreateMemCpy(Value *Dst, Value *Src, uint64_t Size, unsigned Align, bool isVolatile = false, MDNode *TBAATag = nullptr, - MDNode *TBAAStructTag = nullptr) { + MDNode *TBAAStructTag = nullptr, + MDNode *ScopeTag = nullptr, + MDNode *NoAliasTag = nullptr) { return CreateMemCpy(Dst, Src, getInt64(Size), Align, isVolatile, TBAATag, - TBAAStructTag); + TBAAStructTag, ScopeTag, NoAliasTag); } CallInst *CreateMemCpy(Value *Dst, Value *Src, Value *Size, unsigned Align, bool isVolatile = false, MDNode *TBAATag = nullptr, - MDNode *TBAAStructTag = nullptr); + MDNode *TBAAStructTag = nullptr, + MDNode *ScopeTag = nullptr, + MDNode *NoAliasTag = nullptr); /// \brief Create and insert a memmove between the specified /// pointers. /// /// If the pointers aren't i8*, they will be converted. If a TBAA tag is - /// specified, it will be added to the instruction. + /// specified, it will be added to the instruction. Likewise with alias.scope + /// and noalias tags. CallInst *CreateMemMove(Value *Dst, Value *Src, uint64_t Size, unsigned Align, - bool isVolatile = false, MDNode *TBAATag = nullptr) { - return CreateMemMove(Dst, Src, getInt64(Size), Align, isVolatile, TBAATag); + bool isVolatile = false, MDNode *TBAATag = nullptr, + MDNode *ScopeTag = nullptr, + MDNode *NoAliasTag = nullptr) { + return CreateMemMove(Dst, Src, getInt64(Size), Align, isVolatile, + TBAATag, ScopeTag, NoAliasTag); } CallInst *CreateMemMove(Value *Dst, Value *Src, Value *Size, unsigned Align, - bool isVolatile = false, MDNode *TBAATag = nullptr); + bool isVolatile = false, MDNode *TBAATag = nullptr, + MDNode *ScopeTag = nullptr, + MDNode *NoAliasTag = nullptr); /// \brief Create a lifetime.start intrinsic. /// diff --git a/llvm/include/llvm/IR/LLVMContext.h b/llvm/include/llvm/IR/LLVMContext.h index 4d940d599b9..7025571bb53 100644 --- a/llvm/include/llvm/IR/LLVMContext.h +++ b/llvm/include/llvm/IR/LLVMContext.h @@ -52,7 +52,9 @@ public: MD_fpmath = 3, // "fpmath" MD_range = 4, // "range" MD_tbaa_struct = 5, // "tbaa.struct" - MD_invariant_load = 6 // "invariant.load" + MD_invariant_load = 6, // "invariant.load" + MD_alias_scope = 7, // "alias.scope" + MD_noalias = 8 // "noalias" }; /// getMDKindID - Return a unique non-zero ID for the specified metadata kind. diff --git a/llvm/include/llvm/IR/MDBuilder.h b/llvm/include/llvm/IR/MDBuilder.h index 1da9d4599c5..6672b14f59a 100644 --- a/llvm/include/llvm/IR/MDBuilder.h +++ b/llvm/include/llvm/IR/MDBuilder.h @@ -63,24 +63,49 @@ public: MDNode *createRange(const APInt &Lo, const APInt &Hi); //===------------------------------------------------------------------===// - // TBAA metadata. + // AA metadata. //===------------------------------------------------------------------===// - /// \brief Return metadata appropriate for a TBAA root node. Each returned +protected: + /// \brief Return metadata appropriate for a AA root node (scope or TBAA). + /// Each returned node is distinct from all other metadata and will never + /// be identified (uniqued) with anything else. + MDNode *createAnonymousAARoot(StringRef Name = StringRef()); + +public: + /// \brief Return metadata appropriate for a TBAA root node. Each returned /// node is distinct from all other metadata and will never be identified /// (uniqued) with anything else. - MDNode *createAnonymousTBAARoot(); + MDNode *createAnonymousTBAARoot() { + return createAnonymousAARoot(); + } + + /// \brief Return metadata appropriate for an alias scope root node. + /// Each returned node is distinct from all other metadata and will never + /// be identified (uniqued) with anything else. + MDNode *createAnonymousAliasScopeRoot(StringRef Name = StringRef()) { + return createAnonymousAARoot(Name); + } /// \brief Return metadata appropriate for a TBAA root node with the given /// name. This may be identified (uniqued) with other roots with the same /// name. MDNode *createTBAARoot(StringRef Name); + /// \brief Return metadata appropriate for an alias scope root node with + /// the given name. This may be identified (uniqued) with other roots with + /// the same name. + MDNode *createAliasScopeRoot(StringRef Name); + /// \brief Return metadata for a non-root TBAA node with the given name, /// parent in the TBAA tree, and value for 'pointsToConstantMemory'. MDNode *createTBAANode(StringRef Name, MDNode *Parent, bool isConstant = false); + /// \brief Return metadata for a non-root alias scope node with the given + /// name and parent in the scope tree. + MDNode *createAliasScopeNode(StringRef Name, MDNode *Parent); + struct TBAAStructField { uint64_t Offset; uint64_t Size; diff --git a/llvm/include/llvm/IR/Metadata.h b/llvm/include/llvm/IR/Metadata.h index 17176ab4363..e7b379c4ef2 100644 --- a/llvm/include/llvm/IR/Metadata.h +++ b/llvm/include/llvm/IR/Metadata.h @@ -70,8 +70,8 @@ public: /// AAMDNodes - A collection of metadata nodes that might be associated with a /// memory access used by the alias-analysis infrastructure. struct AAMDNodes { - AAMDNodes(MDNode *T = nullptr) - : TBAA(T) {} + AAMDNodes(MDNode *T = nullptr, MDNode *S = nullptr, MDNode *N = nullptr) + : TBAA(T), Scope(S), NoAlias(N) {} bool operator == (const AAMDNodes &A) const { return equals(A); @@ -82,15 +82,21 @@ struct AAMDNodes { } operator bool() const { - return TBAA; + return TBAA || Scope || NoAlias; } /// TBAA - The tag for type-based alias analysis. MDNode *TBAA; + /// Scope - The tag for alias scope specification (used with noalias). + MDNode *Scope; + + /// NoAlias - The tag specifying the noalias scope. + MDNode *NoAlias; + protected: bool equals(const AAMDNodes &A) const { - return TBAA == A.TBAA; + return TBAA == A.TBAA && Scope == A.Scope && NoAlias == A.NoAlias; } }; @@ -98,13 +104,15 @@ protected: template<> struct DenseMapInfo<AAMDNodes> { static inline AAMDNodes getEmptyKey() { - return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey()); + return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey(), 0, 0); } static inline AAMDNodes getTombstoneKey() { - return AAMDNodes(DenseMapInfo<MDNode *>::getTombstoneKey()); + return AAMDNodes(DenseMapInfo<MDNode *>::getTombstoneKey(), 0, 0); } static unsigned getHashValue(const AAMDNodes &Val) { - return DenseMapInfo<MDNode *>::getHashValue(Val.TBAA); + return DenseMapInfo<MDNode *>::getHashValue(Val.TBAA) ^ + DenseMapInfo<MDNode *>::getHashValue(Val.Scope) ^ + DenseMapInfo<MDNode *>::getHashValue(Val.NoAlias); } static bool isEqual(const AAMDNodes &LHS, const AAMDNodes &RHS) { return LHS == RHS; @@ -214,6 +222,8 @@ public: bool isTBAAVtableAccess() const; /// Methods for metadata merging. + static MDNode *concatenate(MDNode *A, MDNode *B); + static MDNode *intersect(MDNode *A, MDNode *B); static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B); static AAMDNodes getMostGenericAA(const AAMDNodes &A, const AAMDNodes &B); static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B); diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index 02f4259a51a..20074f0a5d5 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -263,6 +263,7 @@ void initializeNoTTIPass(PassRegistry&); void initializeTargetLibraryInfoPass(PassRegistry&); void initializeTwoAddressInstructionPassPass(PassRegistry&); void initializeTypeBasedAliasAnalysisPass(PassRegistry&); +void initializeScopedNoAliasAAPass(PassRegistry&); void initializeUnifyFunctionExitNodesPass(PassRegistry&); void initializeUnreachableBlockElimPass(PassRegistry&); void initializeUnreachableMachineBlockElimPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h index e06560ca0b6..b7f832dcee9 100644 --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -56,6 +56,7 @@ namespace { (void) llvm::createLibCallAliasAnalysisPass(nullptr); (void) llvm::createScalarEvolutionAliasAnalysisPass(); (void) llvm::createTypeBasedAliasAnalysisPass(); + (void) llvm::createScopedNoAliasAAPass(); (void) llvm::createBoundsCheckingPass(); (void) llvm::createBreakCriticalEdgesPass(); (void) llvm::createCallGraphPrinterPass(); diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp index c58012f3a8c..010ad7440e6 100644 --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -66,6 +66,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeScalarEvolutionAliasAnalysisPass(Registry); initializeTargetTransformInfoAnalysisGroup(Registry); initializeTypeBasedAliasAnalysisPass(Registry); + initializeScopedNoAliasAAPass(Registry); } void LLVMInitializeAnalysis(LLVMPassRegistryRef R) { diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index d1632fd26ac..a6734772c07 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -53,6 +53,7 @@ add_llvm_library(LLVMAnalysis TargetTransformInfo.cpp Trace.cpp TypeBasedAliasAnalysis.cpp + ScopedNoAliasAA.cpp ValueTracking.cpp ) diff --git a/llvm/lib/Analysis/ScopedNoAliasAA.cpp b/llvm/lib/Analysis/ScopedNoAliasAA.cpp new file mode 100644 index 00000000000..f197f1c48a6 --- /dev/null +++ b/llvm/lib/Analysis/ScopedNoAliasAA.cpp @@ -0,0 +1,243 @@ +//===- ScopedNoAliasAA.cpp - Scoped No-Alias Alias Analysis ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the ScopedNoAlias alias-analysis pass, which implements +// metadata-based scoped no-alias support. +// +// Alias-analysis scopes are defined similar to TBAA nodes: +// +// !scope0 = metadata !{ metadata !"scope of foo()" } +// !scope1 = metadata !{ metadata !"scope 1", metadata !scope0 } +// !scope2 = metadata !{ metadata !"scope 2", metadata !scope0 } +// !scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 } +// !scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 } +// +// Loads and stores can be tagged with an alias-analysis scope, and also, with +// a noalias tag for a specific scope: +// +// ... = load %ptr1, !alias.scope !{ !scope1 } +// ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 } +// +// When evaluating an aliasing query, if one of the instructions is associated +// with an alias.scope id that is identical to the noalias scope associated +// with the other instruction, or is a descendant (in the scope hierarchy) of +// the noalias scope associated with the other instruction, then the two memory +// accesses are assumed not to alias. +// +// Note that if the first element of the scope metadata is a string, then it +// can be combined accross functions and translation units. The string can be +// replaced by a self-reference to create globally unqiue scope identifiers. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" +using namespace llvm; + +// A handy option for disabling scoped no-alias functionality. The same effect +// can also be achieved by stripping the associated metadata tags from IR, but +// this option is sometimes more convenient. +static cl::opt<bool> +EnableScopedNoAlias("enable-scoped-noalias", cl::init(true)); + +namespace { +/// AliasScopeNode - This is a simple wrapper around an MDNode which provides +/// a higher-level interface by hiding the details of how alias analysis +/// information is encoded in its operands. +class AliasScopeNode { + const MDNode *Node; + +public: + AliasScopeNode() : Node(0) {} + explicit AliasScopeNode(const MDNode *N) : Node(N) {} + + /// getNode - Get the MDNode for this AliasScopeNode. + const MDNode *getNode() const { return Node; } + + /// getParent - Get this AliasScopeNode's Alias tree parent. + AliasScopeNode getParent() const { + if (Node->getNumOperands() < 2) + return AliasScopeNode(); + MDNode *P = dyn_cast_or_null<MDNode>(Node->getOperand(1)); + if (!P) + return AliasScopeNode(); + // Ok, this node has a valid parent. Return it. + return AliasScopeNode(P); + } +}; + +/// ScopedNoAliasAA - This is a simple alias analysis +/// implementation that uses scoped-noalias metadata to answer queries. +class ScopedNoAliasAA : public ImmutablePass, public AliasAnalysis { +public: + static char ID; // Class identification, replacement for typeinfo + ScopedNoAliasAA() : ImmutablePass(ID) { + initializeScopedNoAliasAAPass(*PassRegistry::getPassRegistry()); + } + + virtual void initializePass() { + InitializeAliasAnalysis(this); + } + + /// getAdjustedAnalysisPointer - This method is used when a pass implements + /// an analysis interface through multiple inheritance. If needed, it + /// should override this to adjust the this pointer as needed for the + /// specified pass info. + virtual void *getAdjustedAnalysisPointer(const void *PI) { + if (PI == &AliasAnalysis::ID) + return (AliasAnalysis*)this; + return this; + } + +protected: + bool mayAlias(const MDNode *A, const MDNode *B) const; + bool mayAliasInScopes(const MDNode *Scopes, const MDNode *NoAlias) const; + +private: + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual AliasResult alias(const Location &LocA, const Location &LocB); + virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); + virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); + virtual ModRefBehavior getModRefBehavior(const Function *F); + virtual ModRefResult getModRefInfo(ImmutableCallSite CS, + const Location &Loc); + virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, + ImmutableCallSite CS2); +}; +} // End of anonymous namespace + +// Register this pass... +char ScopedNoAliasAA::ID = 0; +INITIALIZE_AG_PASS(ScopedNoAliasAA, AliasAnalysis, "scoped-noalias", + "Scoped NoAlias Alias Analysis", false, true, false) + +ImmutablePass *llvm::createScopedNoAliasAAPass() { + return new ScopedNoAliasAA(); +} + +void +ScopedNoAliasAA::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AliasAnalysis::getAnalysisUsage(AU); +} + +/// mayAlias - Test whether the scope represented by A may alias the +/// scope represented by B. Specifically, A is the target scope, and B is the +/// noalias scope. +bool +ScopedNoAliasAA::mayAlias(const MDNode *A, + const MDNode *B) const { + // Climb the tree from A to see if we reach B. + for (AliasScopeNode T(A); ; ) { + if (T.getNode() == B) + // B is an ancestor of A. + return false; + + T = T.getParent(); + if (!T.getNode()) + break; + } + + return true; +} + +bool +ScopedNoAliasAA::mayAliasInScopes(const MDNode *Scopes, + const MDNode *NoAlias) const { + if (!Scopes || !NoAlias) + return true; + + for (unsigned i = 0, ie = Scopes->getNumOperands(); i != ie; ++i) + if (const MDNode *SMD = dyn_cast<MDNode>(Scopes->getOperand(i))) + for (unsigned j = 0, je = NoAlias->getNumOperands(); j != je; ++j) + if (const MDNode *NAMD = dyn_cast<MDNode>(NoAlias->getOperand(j))) + if (!mayAlias(SMD, NAMD)) + return false; + + return true; +} + +AliasAnalysis::AliasResult +ScopedNoAliasAA::alias(const Location &LocA, const Location &LocB) { + if (!EnableScopedNoAlias) + return AliasAnalysis::alias(LocA, LocB); + + // Get the attached MDNodes. + const MDNode *AScopes = LocA.AATags.Scope, + *BScopes = LocB.AATags.Scope; + + const MDNode *ANoAlias = LocA.AATags.NoAlias, + *BNoAlias = LocB.AATags.NoAlias; + + if (!mayAliasInScopes(AScopes, BNoAlias)) + return NoAlias; + + if (!mayAliasInScopes(BScopes, ANoAlias)) + return NoAlias; + + // If they may alias, chain to the next AliasAnalysis. + return AliasAnalysis::alias(LocA, LocB); +} + +bool ScopedNoAliasAA::pointsToConstantMemory(const Location &Loc, + bool OrLocal) { + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); +} + +AliasAnalysis::ModRefBehavior +ScopedNoAliasAA::getModRefBehavior(ImmutableCallSite CS) { + return AliasAnalysis::getModRefBehavior(CS); +} + +AliasAnalysis::ModRefBehavior +ScopedNoAliasAA::getModRefBehavior(const Function *F) { + return AliasAnalysis::getModRefBehavior(F); +} + +AliasAnalysis::ModRefResult +ScopedNoAliasAA::getModRefInfo(ImmutableCallSite CS, const Location &Loc) { + if (!EnableScopedNoAlias) + return AliasAnalysis::getModRefInfo(CS, Loc); + + if (!mayAliasInScopes(Loc.AATags.Scope, + CS.getInstruction()->getMetadata(LLVMContext::MD_noalias))) + return NoModRef; + + if (!mayAliasInScopes( + CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), + Loc.AATags.NoAlias)) + return NoModRef; + + return AliasAnalysis::getModRefInfo(CS, Loc); +} + +AliasAnalysis::ModRefResult +ScopedNoAliasAA::getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { + if (!EnableScopedNoAlias) + return AliasAnalysis::getModRefInfo(CS1, CS2); + + if (!mayAliasInScopes( + CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), + CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias))) + return NoModRef; + + if (!mayAliasInScopes( + CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope), + CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias))) + return NoModRef; + + return AliasAnalysis::getModRefInfo(CS1, CS2); +} + diff --git a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp index c68ba5af9aa..27b469a43b0 100644 --- a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -618,5 +618,17 @@ void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const { getMetadata(LLVMContext::MD_tbaa)); else N.TBAA = getMetadata(LLVMContext::MD_tbaa); + + if (Merge) + N.Scope = MDNode::intersect(N.Scope, + getMetadata(LLVMContext::MD_alias_scope)); + else + N.Scope = getMetadata(LLVMContext::MD_alias_scope); + + if (Merge) + N.NoAlias = MDNode::intersect(N.NoAlias, + getMetadata(LLVMContext::MD_noalias)); + else + N.NoAlias = getMetadata(LLVMContext::MD_noalias); } diff --git a/llvm/lib/CodeGen/MachineInstr.cpp b/llvm/lib/CodeGen/MachineInstr.cpp index 06cce92caee..c9fe23448e7 100644 --- a/llvm/lib/CodeGen/MachineInstr.cpp +++ b/llvm/lib/CodeGen/MachineInstr.cpp @@ -523,6 +523,34 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, const MachineMemOperand &MMO) { OS << ")"; } + // Print AA scope info. + if (const MDNode *ScopeInfo = MMO.getAAInfo().Scope) { + OS << "(alias.scope="; + if (ScopeInfo->getNumOperands() > 0) + for (unsigned i = 0, ie = ScopeInfo->getNumOperands(); i != ie; ++i) { + ScopeInfo->getOperand(i)->printAsOperand(OS, /*PrintType=*/false); + if (i != ie-1) + OS << ","; + } + else + OS << "<unknown>"; + OS << ")"; + } + + // Print AA noalias scope info. + if (const MDNode *NoAliasInfo = MMO.getAAInfo().NoAlias) { + OS << "(noalias="; + if (NoAliasInfo->getNumOperands() > 0) + for (unsigned i = 0, ie = NoAliasInfo->getNumOperands(); i != ie; ++i) { + NoAliasInfo->getOperand(i)->printAsOperand(OS, /*PrintType=*/false); + if (i != ie-1) + OS << ","; + } + else + OS << "<unknown>"; + OS << ")"; + } + // Print nontemporal info. if (MMO.isNonTemporal()) OS << "(nontemporal)"; diff --git a/llvm/lib/CodeGen/Passes.cpp b/llvm/lib/CodeGen/Passes.cpp index 6e86c8f2109..bac0433dc87 100644 --- a/llvm/lib/CodeGen/Passes.cpp +++ b/llvm/lib/CodeGen/Passes.cpp @@ -377,6 +377,7 @@ void TargetPassConfig::addIRPasses() { // BasicAliasAnalysis wins if they disagree. This is intended to help // support "obvious" type-punning idioms. addPass(createTypeBasedAliasAnalysisPass()); + addPass(createScopedNoAliasAAPass()); addPass(createBasicAliasAnalysisPass()); // Before running any passes, run the verifier to determine if the input diff --git a/llvm/lib/IR/IRBuilder.cpp b/llvm/lib/IR/IRBuilder.cpp index 435e54f0ea2..7448e50bd82 100644 --- a/llvm/lib/IR/IRBuilder.cpp +++ b/llvm/lib/IR/IRBuilder.cpp @@ -62,7 +62,8 @@ static CallInst *createCallHelper(Value *Callee, ArrayRef<Value *> Ops, CallInst *IRBuilderBase:: CreateMemSet(Value *Ptr, Value *Val, Value *Size, unsigned Align, - bool isVolatile, MDNode *TBAATag) { + bool isVolatile, MDNode *TBAATag, MDNode *ScopeTag, + MDNode *NoAliasTag) { Ptr = getCastedInt8PtrValue(Ptr); Value *Ops[] = { Ptr, Val, Size, getInt32(Align), getInt1(isVolatile) }; Type *Tys[] = { Ptr->getType(), Size->getType() }; @@ -74,13 +75,20 @@ CreateMemSet(Value *Ptr, Value *Val, Value *Size, unsigned Align, // Set the TBAA info if present. if (TBAATag) CI->setMetadata(LLVMContext::MD_tbaa, TBAATag); - + + if (ScopeTag) + CI->setMetadata(LLVMContext::MD_alias_scope, ScopeTag); + + if (NoAliasTag) + CI->setMetadata(LLVMContext::MD_noalias, NoAliasTag); + return CI; } CallInst *IRBuilderBase:: CreateMemCpy(Value *Dst, Value *Src, Value *Size, unsigned Align, - bool isVolatile, MDNode *TBAATag, MDNode *TBAAStructTag) { + bool isVolatile, MDNode *TBAATag, MDNode *TBAAStructTag, + MDNode *ScopeTag, MDNode *NoAliasTag) { Dst = getCastedInt8PtrValue(Dst); Src = getCastedInt8PtrValue(Src); @@ -98,13 +106,20 @@ CreateMemCpy(Value *Dst, Value *Src, Value *Size, unsigned Align, // Set the TBAA Struct info if present. if (TBAAStructTag) CI->setMetadata(LLVMContext::MD_tbaa_struct, TBAAStructTag); - + + if (ScopeTag) + CI->setMetadata(LLVMContext::MD_alias_scope, ScopeTag); + + if (NoAliasTag) + CI->setMetadata(LLVMContext::MD_noalias, NoAliasTag); + return CI; } CallInst *IRBuilderBase:: CreateMemMove(Value *Dst, Value *Src, Value *Size, unsigned Align, - bool isVolatile, MDNode *TBAATag) { + bool isVolatile, MDNode *TBAATag, MDNode *ScopeTag, + MDNode *NoAliasTag) { Dst = getCastedInt8PtrValue(Dst); Src = getCastedInt8PtrValue(Src); @@ -118,7 +133,13 @@ CreateMemMove(Value *Dst, Value *Src, Value *Size, unsigned Align, // Set the TBAA info if present. if (TBAATag) CI->setMetadata(LLVMContext::MD_tbaa, TBAATag); - + + if (ScopeTag) + CI->setMetadata(LLVMContext::MD_alias_scope, ScopeTag); + + if (NoAliasTag) + CI->setMetadata(LLVMContext::MD_noalias, NoAliasTag); + return CI; } diff --git a/llvm/lib/IR/LLVMContext.cpp b/llvm/lib/IR/LLVMContext.cpp index de825f00b20..d4ba83dfa62 100644 --- a/llvm/lib/IR/LLVMContext.cpp +++ b/llvm/lib/IR/LLVMContext.cpp @@ -66,6 +66,16 @@ LLVMContext::LLVMContext() : pImpl(new LLVMContextImpl(*this)) { unsigned InvariantLdId = getMDKindID("invariant.load"); assert(InvariantLdId == MD_invariant_load && "invariant.load kind id drifted"); (void)InvariantLdId; + + // Create the 'alias.scope' metadata kind. + unsigned AliasScopeID = getMDKindID("alias.scope"); + assert(AliasScopeID == MD_alias_scope && "alias.scope kind id drifted"); + (void)AliasScopeID; + + // Create the 'noalias' metadata kind. + unsigned NoAliasID = getMDKindID("noalias"); + assert(NoAliasID == MD_noalias && "noalias kind id drifted"); + (void)NoAliasID; } LLVMContext::~LLVMContext() { delete pImpl; } diff --git a/llvm/lib/IR/MDBuilder.cpp b/llvm/lib/IR/MDBuilder.cpp index 65cdf388521..103915f5ae5 100644 --- a/llvm/lib/IR/MDBuilder.cpp +++ b/llvm/lib/IR/MDBuilder.cpp @@ -60,10 +60,15 @@ MDNode *MDBuilder::createRange(const APInt &Lo, const APInt &Hi) { return MDNode::get(Context, Range); } -MDNode *MDBuilder::createAnonymousTBAARoot() { +MDNode *MDBuilder::createAnonymousAARoot(StringRef Name) { // To ensure uniqueness the root node is self-referential. - MDNode *Dummy = MDNode::getTemporary(Context, ArrayRef<Value *>()); - MDNode *Root = MDNode::get(Context, Dummy); + MDNode *Dummy = MDNode::getTemporary(Context, ArrayRef<Value*>()); + + SmallVector<Value *, 2> Args(1, Dummy); + if (!Name.empty()) + Args.push_back(createString(Name)); + MDNode *Root = MDNode::get(Context, Args); + // At this point we have // !0 = metadata !{} <- dummy // !1 = metadata !{metadata !0} <- root @@ -93,6 +98,15 @@ MDNode *MDBuilder::createTBAANode(StringRef Name, MDNode *Parent, } } +MDNode *MDBuilder::createAliasScopeRoot(StringRef Name) { + return MDNode::get(Context, createString(Name)); +} + +MDNode *MDBuilder::createAliasScopeNode(StringRef Name, MDNode *Parent) { + Value *Ops[2] = { createString(Name), Parent }; + return MDNode::get(Context, Ops); +} + /// \brief Return metadata for a tbaa.struct node with the given /// struct field descriptions. MDNode *MDBuilder::createTBAAStructNode(ArrayRef<TBAAStructField> Fields) { diff --git a/llvm/lib/IR/Metadata.cpp b/llvm/lib/IR/Metadata.cpp index d7d64641bdb..a017bd3c0c0 100644 --- a/llvm/lib/IR/Metadata.cpp +++ b/llvm/lib/IR/Metadata.cpp @@ -406,6 +406,41 @@ void MDNode::replaceOperand(MDNodeOperand *Op, Value *To) { } } +MDNode *MDNode::concatenate(MDNode *A, MDNode *B) { + if (!A) + return B; + if (!B) + return A; + + SmallVector<Value *, 4> Vals(A->getNumOperands() + + B->getNumOperands()); + + unsigned j = 0; + for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) + Vals[j++] = A->getOperand(i); + for (unsigned i = 0, ie = B->getNumOperands(); i != ie; ++i) + Vals[j++] = B->getOperand(i); + + return MDNode::get(A->getContext(), Vals); +} + +MDNode *MDNode::intersect(MDNode *A, MDNode *B) { + if (!A || !B) + return nullptr; + + SmallVector<Value *, 4> Vals; + for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) { + Value *V = A->getOperand(i); + for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j) + if (V == B->getOperand(j)) { + Vals.push_back(V); + break; + } + } + + return MDNode::get(A->getContext(), Vals); +} + MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) { if (!A || !B) return nullptr; @@ -689,6 +724,8 @@ void Instruction::setMetadata(unsigned KindID, MDNode *Node) { void Instruction::setAAMetadata(const AAMDNodes &N) { setMetadata(LLVMContext::MD_tbaa, N.TBAA); + setMetadata(LLVMContext::MD_alias_scope, N.Scope); + setMetadata(LLVMContext::MD_noalias, N.NoAlias); } MDNode *Instruction::getMetadataImpl(unsigned KindID) const { diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp index 701fb462b4f..98477b5d71f 100644 --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -107,6 +107,7 @@ PassManagerBuilder::addInitialAliasAnalysisPasses(PassManagerBase &PM) const { // BasicAliasAnalysis wins if they disagree. This is intended to help // support "obvious" type-punning idioms. PM.add(createTypeBasedAliasAnalysisPass()); + PM.add(createScopedNoAliasAAPass()); PM.add(createBasicAliasAnalysisPass()); } diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index 43ccb995958..7135874003d 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -1791,6 +1791,19 @@ static void patchReplacementInstruction(Instruction *I, Value *Repl) { case LLVMContext::MD_tbaa: ReplInst->setMetadata(Kind, MDNode::getMostGenericTBAA(IMD, ReplMD)); break; + case LLVMContext::MD_alias_scope: + case LLVMContext::MD_noalias: + // FIXME: If both the original and replacement value are part of the + // same control-flow region (meaning that the execution of one + // guarentees the executation of the other), then we can combine the + // noalias scopes here and do better than the general conservative + // answer. + + // In general, GVN unifies expressions over different control-flow + // regions, and so we need a conservative combination of the noalias + // scopes. + ReplInst->setMetadata(Kind, MDNode::intersect(IMD, ReplMD)); + break; case LLVMContext::MD_range: ReplInst->setMetadata(Kind, MDNode::getMostGenericRange(IMD, ReplMD)); break; diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp index de724d419a4..12df676df87 100644 --- a/llvm/lib/Transforms/Scalar/Scalar.cpp +++ b/llvm/lib/Transforms/Scalar/Scalar.cpp @@ -203,6 +203,10 @@ void LLVMAddTypeBasedAliasAnalysisPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createTypeBasedAliasAnalysisPass()); } +void LLVMAddScopedNoAliasAAPass(LLVMPassManagerRef PM) { + unwrap(PM)->add(createScopedNoAliasAAPass()); +} + void LLVMAddBasicAliasAnalysisPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createBasicAliasAnalysisPass()); } diff --git a/llvm/lib/Transforms/Scalar/Scalarizer.cpp b/llvm/lib/Transforms/Scalar/Scalarizer.cpp index 7a73f113b1d..813041ab255 100644 --- a/llvm/lib/Transforms/Scalar/Scalarizer.cpp +++ b/llvm/lib/Transforms/Scalar/Scalarizer.cpp @@ -312,6 +312,8 @@ bool Scalarizer::canTransferMetadata(unsigned Tag) { || Tag == LLVMContext::MD_fpmath || Tag == LLVMContext::MD_tbaa_struct || Tag == LLVMContext::MD_invariant_load + || Tag == LLVMContext::MD_alias_scope + || Tag == LLVMContext::MD_noalias || Tag == ParallelLoopAccessMDKind); } diff --git a/llvm/lib/Transforms/Utils/InlineFunction.cpp b/llvm/lib/Transforms/Utils/InlineFunction.cpp index f0a9f2b1fcb..f4152dd490a 100644 --- a/llvm/lib/Transforms/Utils/InlineFunction.cpp +++ b/llvm/lib/Transforms/Utils/InlineFunction.cpp @@ -13,10 +13,13 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/CFG.h" @@ -28,6 +31,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" +#include "llvm/IR/MDBuilder.h" #include "llvm/IR/Module.h" #include "llvm/Transforms/Utils/Local.h" using namespace llvm; @@ -260,6 +264,100 @@ static void HandleInlinedInvoke(InvokeInst *II, BasicBlock *FirstNewBlock, InvokeDest->removePredecessor(II->getParent()); } +/// CloneAliasScopeMetadata - When inlining a function that contains noalias +/// scope metadata, this metadata needs to be cloned so that the inlined blocks +/// have different "unqiue scopes" at every call site. Were this not done, then +/// aliasing scopes from a function inlined into a caller multiple times could +/// not be differentiated (and this would lead to miscompiles because the +/// non-aliasing property communicated by the metadata could have +/// call-site-specific control dependencies). +static void CloneAliasScopeMetadata(CallSite CS, ValueToValueMapTy &VMap) { + const Function *CalledFunc = CS.getCalledFunction(); + SetVector<const MDNode *> MD; + + // Note: We could only clone the metadata if it is already used in the + // caller. I'm omitting that check here because it might confuse + // inter-procedural alias analysis passes. We can revisit this if it becomes + // an efficiency or overhead problem. + + for (Function::const_iterator I = CalledFunc->begin(), IE = CalledFunc->end(); + I != IE; ++I) + for (BasicBlock::const_iterator J = I->begin(), JE = I->end(); J != JE; ++J) { + if (const MDNode *M = J->getMetadata(LLVMContext::MD_alias_scope)) + MD.insert(M); + if (const MDNode *M = J->getMetadata(LLVMContext::MD_noalias)) + MD.insert(M); + } + + if (MD.empty()) + return; + + // Walk the existing metadata, adding the complete (perhaps cyclic) chain to + // the set. + SmallVector<const Value *, 16> Queue(MD.begin(), MD.end()); + while (!Queue.empty()) { + const MDNode *M = cast<MDNode>(Queue.pop_back_val()); + for (unsigned i = 0, ie = M->getNumOperands(); i != ie; ++i) + if (const MDNode *M1 = dyn_cast<MDNode>(M->getOperand(i))) + if (MD.insert(M1)) + Queue.push_back(M1); + } + + // Now we have a complete set of all metadata in the chains used to specify + // the noalias scopes and the lists of those scopes. + SmallVector<MDNode *, 16> DummyNodes; + DenseMap<const MDNode *, TrackingVH<MDNode> > MDMap; + for (SetVector<const MDNode *>::iterator I = MD.begin(), IE = MD.end(); + I != IE; ++I) { + MDNode *Dummy = MDNode::getTemporary(CalledFunc->getContext(), + ArrayRef<Value*>()); + DummyNodes.push_back(Dummy); + MDMap[*I] = Dummy; + } + + // Create new metadata nodes to replace the dummy nodes, replacing old + // metadata references with either a dummy node or an already-created new + // node. + for (SetVector<const MDNode *>::iterator I = MD.begin(), IE = MD.end(); + I != IE; ++I) { + SmallVector<Value *, 4> NewOps; + for (unsigned i = 0, ie = (*I)->getNumOperands(); i != ie; ++i) { + const Value *V = (*I)->getOperand(i); + if (const MDNode *M = dyn_cast<MDNode>(V)) + NewOps.push_back(MDMap[M]); + else + NewOps.push_back(const_cast<Value *>(V)); + } + + MDNode *NewM = MDNode::get(CalledFunc->getContext(), NewOps), + *TempM = MDMap[*I]; + + TempM->replaceAllUsesWith(NewM); + } + + // Now replace the metadata in the new inlined instructions with the + // repacements from the map. + for (ValueToValueMapTy::iterator VMI = VMap.begin(), VMIE = VMap.end(); + VMI != VMIE; ++VMI) { + if (!VMI->second) + continue; + + Instruction *NI = dyn_cast<Instruction>(VMI->second); + if (!NI) + continue; + + if (MDNode *M = NI->getMetadata(LLVMContext::MD_alias_scope)) + NI->setMetadata(LLVMContext::MD_alias_scope, MDMap[M]); + + if (MDNode *M = NI->getMetadata(LLVMContext::MD_noalias)) + NI->setMetadata(LLVMContext::MD_noalias, MDMap[M]); + } + + // Now that everything has been replaced, delete the dummy nodes. + for (unsigned i = 0, ie = DummyNodes.size(); i != ie; ++i) + MDNode::deleteTemporary(DummyNodes[i]); +} + /// UpdateCallGraphAfterInlining - Once we have cloned code over from a callee /// into the caller, update the specified callgraph to reflect the changes we /// made. Note that it's possible that not all code was copied over, so only @@ -648,6 +746,9 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI, // Update inlined instructions' line number information. fixupLineNumbers(Caller, FirstNewBlock, TheCall); + + // Clone existing noalias metadata if necessary. + CloneAliasScopeMetadata(CS, VMap); } // If there are any alloca instructions in the block that used to be the entry diff --git a/llvm/lib/Transforms/Vectorize/BBVectorize.cpp b/llvm/lib/Transforms/Vectorize/BBVectorize.cpp index 28ec83bf868..9ee0ffb03bb 100644 --- a/llvm/lib/Transforms/Vectorize/BBVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/BBVectorize.cpp @@ -2982,6 +2982,10 @@ namespace { case LLVMContext::MD_tbaa: K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD)); break; + case LLVMContext::MD_alias_scope: + case LLVMContext::MD_noalias: + K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); + break; case LLVMContext::MD_fpmath: K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); break; diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp index b60ce61886c..a88eb490e40 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -535,6 +535,8 @@ static void propagateMetadata(Instruction *To, const Instruction *From) { // non-speculated memory access when the condition was false, this would be // caught by the runtime overlap checks). if (Kind != LLVMContext::MD_tbaa && + Kind != LLVMContext::MD_alias_scope && + Kind != LLVMContext::MD_noalias && Kind != LLVMContext::MD_fpmath) continue; diff --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp index 53a43d9851e..bbfdb4e4fa9 100644 --- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -230,6 +230,10 @@ static Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL) { case LLVMContext::MD_tbaa: MD = MDNode::getMostGenericTBAA(MD, IMD); break; + case LLVMContext::MD_alias_scope: + case LLVMContext::MD_noalias: + MD = MDNode::intersect(MD, IMD); + break; case LLVMContext::MD_fpmath: MD = MDNode::getMostGenericFPMath(MD, IMD); break; diff --git a/llvm/test/Analysis/ScopedNoAliasAA/basic-hierarchy.ll b/llvm/test/Analysis/ScopedNoAliasAA/basic-hierarchy.ll new file mode 100644 index 00000000000..12d358e2dfc --- /dev/null +++ b/llvm/test/Analysis/ScopedNoAliasAA/basic-hierarchy.ll @@ -0,0 +1,80 @@ +; RUN: opt < %s -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define void @foo1(float* nocapture %a, float* nocapture readonly %c) #0 { +entry: +; CHECK-LABEL: Function: foo1 + %0 = load float* %c, align 4, !alias.scope !0 + %arrayidx.i = getelementptr inbounds float* %a, i64 5 + store float %0, float* %arrayidx.i, align 4, !noalias !0 + + %1 = load float* %c, align 4 + %arrayidx = getelementptr inbounds float* %a, i64 7 + store float %1, float* %arrayidx, align 4 + + %2 = load float* %c, align 4, !alias.scope !1 + %arrayidx.i2 = getelementptr inbounds float* %a, i64 15 + store float %2, float* %arrayidx.i2, align 4, !noalias !3 + + %3 = load float* %c, align 4, !alias.scope !3 + %arrayidx.i3 = getelementptr inbounds float* %a, i64 16 + store float %3, float* %arrayidx.i3, align 4, !noalias !0 + + %4 = load float* %c, align 4, !alias.scope !5 + %arrayidx.i4 = getelementptr inbounds float* %a, i64 17 + store float %4, float* %arrayidx.i4, align 4, !noalias !3 + ret void +} + +attributes #0 = { nounwind uwtable } + +; A root scope (which doubles as a list of itself): +!0 = metadata !{metadata !0} + +; Two child scopes (which must be self-referential to avoid being "uniqued"): +!1 = metadata !{metadata !2} +!2 = metadata !{metadata !2, metadata !0} + +!3 = metadata !{metadata !4} +!4 = metadata !{metadata !4, metadata !0} + +; A list of the two children: +!5 = metadata !{metadata !2, metadata !4} + +; CHECK: NoAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: MayAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %1, float* %arrayidx, align 4 +; CHECK: MayAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %2, float* %arrayidx.i2, align 4, !noalias !3 +; CHECK: NoAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %3, float* %arrayidx.i3, align 4, !noalias !0 +; CHECK: MayAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %4, float* %arrayidx.i4, align 4, !noalias !3 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %1, float* %arrayidx, align 4 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %2, float* %arrayidx.i2, align 4, !noalias !3 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %3, float* %arrayidx.i3, align 4, !noalias !0 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %4, float* %arrayidx.i4, align 4, !noalias !3 +; CHECK: NoAlias: %2 = load float* %c, align 4, !alias.scope !1 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: MayAlias: %2 = load float* %c, align 4, !alias.scope !1 <-> store float %1, float* %arrayidx, align 4 +; CHECK: MayAlias: %2 = load float* %c, align 4, !alias.scope !1 <-> store float %2, float* %arrayidx.i2, align 4, !noalias !3 +; CHECK: NoAlias: %2 = load float* %c, align 4, !alias.scope !1 <-> store float %3, float* %arrayidx.i3, align 4, !noalias !0 +; CHECK: MayAlias: %2 = load float* %c, align 4, !alias.scope !1 <-> store float %4, float* %arrayidx.i4, align 4, !noalias !3 +; CHECK: NoAlias: %3 = load float* %c, align 4, !alias.scope !3 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: MayAlias: %3 = load float* %c, align 4, !alias.scope !3 <-> store float %1, float* %arrayidx, align 4 +; CHECK: NoAlias: %3 = load float* %c, align 4, !alias.scope !3 <-> store float %2, float* %arrayidx.i2, align 4, !noalias !3 +; CHECK: NoAlias: %3 = load float* %c, align 4, !alias.scope !3 <-> store float %3, float* %arrayidx.i3, align 4, !noalias !0 +; CHECK: NoAlias: %3 = load float* %c, align 4, !alias.scope !3 <-> store float %4, float* %arrayidx.i4, align 4, !noalias !3 +; CHECK: NoAlias: %4 = load float* %c, align 4, !alias.scope !5 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: MayAlias: %4 = load float* %c, align 4, !alias.scope !5 <-> store float %1, float* %arrayidx, align 4 +; CHECK: NoAlias: %4 = load float* %c, align 4, !alias.scope !5 <-> store float %2, float* %arrayidx.i2, align 4, !noalias !3 +; CHECK: NoAlias: %4 = load float* %c, align 4, !alias.scope !5 <-> store float %3, float* %arrayidx.i3, align 4, !noalias !0 +; CHECK: NoAlias: %4 = load float* %c, align 4, !alias.scope !5 <-> store float %4, float* %arrayidx.i4, align 4, !noalias !3 +; CHECK: NoAlias: store float %1, float* %arrayidx, align 4 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: NoAlias: store float %2, float* %arrayidx.i2, align 4, !noalias !3 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: NoAlias: store float %2, float* %arrayidx.i2, align 4, !noalias !3 <-> store float %1, float* %arrayidx, align 4 +; CHECK: NoAlias: store float %3, float* %arrayidx.i3, align 4, !noalias !0 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: NoAlias: store float %3, float* %arrayidx.i3, align 4, !noalias !0 <-> store float %1, float* %arrayidx, align 4 +; CHECK: NoAlias: store float %3, float* %arrayidx.i3, align 4, !noalias !0 <-> store float %2, float* %arrayidx.i2, align 4, !noalias !3 +; CHECK: NoAlias: store float %4, float* %arrayidx.i4, align 4, !noalias !3 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: NoAlias: store float %4, float* %arrayidx.i4, align 4, !noalias !3 <-> store float %1, float* %arrayidx, align 4 +; CHECK: NoAlias: store float %4, float* %arrayidx.i4, align 4, !noalias !3 <-> store float %2, float* %arrayidx.i2, align 4, !noalias !3 +; CHECK: NoAlias: store float %4, float* %arrayidx.i4, align 4, !noalias !3 <-> store float %3, float* %arrayidx.i3, align 4, !noalias !0 + diff --git a/llvm/test/Analysis/ScopedNoAliasAA/basic.ll b/llvm/test/Analysis/ScopedNoAliasAA/basic.ll new file mode 100644 index 00000000000..bae977f28ee --- /dev/null +++ b/llvm/test/Analysis/ScopedNoAliasAA/basic.ll @@ -0,0 +1,26 @@ +; RUN: opt < %s -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define void @foo1(float* nocapture %a, float* nocapture readonly %c) #0 { +entry: +; CHECK-LABEL: Function: foo1 + %0 = load float* %c, align 4, !alias.scope !0 + %arrayidx.i = getelementptr inbounds float* %a, i64 5 + store float %0, float* %arrayidx.i, align 4, !noalias !0 + %1 = load float* %c, align 4 + %arrayidx = getelementptr inbounds float* %a, i64 7 + store float %1, float* %arrayidx, align 4 + ret void + +; CHECK: NoAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: MayAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %1, float* %arrayidx, align 4 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %1, float* %arrayidx, align 4 +; CHECK: NoAlias: store float %1, float* %arrayidx, align 4 <-> store float %0, float* %arrayidx.i, align 4, !noalias !0 +} + +attributes #0 = { nounwind uwtable } + +!0 = metadata !{metadata !0} + diff --git a/llvm/test/Analysis/ScopedNoAliasAA/basic2.ll b/llvm/test/Analysis/ScopedNoAliasAA/basic2.ll new file mode 100644 index 00000000000..44393bbdaab --- /dev/null +++ b/llvm/test/Analysis/ScopedNoAliasAA/basic2.ll @@ -0,0 +1,34 @@ +; RUN: opt < %s -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define void @foo2(float* nocapture %a, float* nocapture %b, float* nocapture readonly %c) #0 { +entry: +; CHECK-LABEL: Function: foo2 + %0 = load float* %c, align 4, !alias.scope !0 + %arrayidx.i = getelementptr inbounds float* %a, i64 5 + store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1 + %arrayidx1.i = getelementptr inbounds float* %b, i64 8 + store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2 + %1 = load float* %c, align 4 + %arrayidx = getelementptr inbounds float* %a, i64 7 + store float %1, float* %arrayidx, align 4 + ret void + +; CHECK: NoAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1 +; CHECK: NoAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2 +; CHECK: MayAlias: %0 = load float* %c, align 4, !alias.scope !0 <-> store float %1, float* %arrayidx, align 4 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2 +; CHECK: MayAlias: %1 = load float* %c, align 4 <-> store float %1, float* %arrayidx, align 4 +; CHECK: NoAlias: store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2 <-> store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1 +; CHECK: NoAlias: store float %1, float* %arrayidx, align 4 <-> store float %0, float* %arrayidx.i, align 4, !alias.scope !2, !noalias !1 +; CHECK: MayAlias: store float %1, float* %arrayidx, align 4 <-> store float %0, float* %arrayidx1.i, align 4, !alias.scope !1, !noalias !2 +} + +attributes #0 = { nounwind uwtable } + +!0 = metadata !{metadata !1, metadata !2} +!1 = metadata !{metadata !1} +!2 = metadata !{metadata !2} + diff --git a/llvm/test/Transforms/GVN/noalias.ll b/llvm/test/Transforms/GVN/noalias.ll new file mode 100644 index 00000000000..a774f3879b8 --- /dev/null +++ b/llvm/test/Transforms/GVN/noalias.ll @@ -0,0 +1,43 @@ +; RUN: opt -scoped-noalias -basicaa -gvn -S < %s | FileCheck %s + +define i32 @test1(i32* %p, i32* %q) { +; CHECK-LABEL: @test1(i32* %p, i32* %q) +; CHECK: load i32* %p +; CHECK-NOT: noalias +; CHECK: %c = add i32 %a, %a + %a = load i32* %p, !noalias !0 + %b = load i32* %p + %c = add i32 %a, %b + ret i32 %c +} + +define i32 @test2(i32* %p, i32* %q) { +; CHECK-LABEL: @test2(i32* %p, i32* %q) +; CHECK: load i32* %p, !alias.scope !0 +; CHECK: %c = add i32 %a, %a + %a = load i32* %p, !alias.scope !0 + %b = load i32* %p, !alias.scope !0 + %c = add i32 %a, %b + ret i32 %c +} + +; FIXME: In this case we can do better than intersecting the scopes, and can +; concatenate them instead. Both loads are in the same basic block, the first +; makes the second safe to speculatively execute, and there are no calls that may +; throw in between. +define i32 @test3(i32* %p, i32* %q) { +; CHECK-LABEL: @test3(i32* %p, i32* %q) +; CHECK: load i32* %p, !alias.scope !1 +; CHECK: %c = add i32 %a, %a + %a = load i32* %p, !alias.scope !1 + %b = load i32* %p, !alias.scope !2 + %c = add i32 %a, %b + ret i32 %c +} + +declare i32 @foo(i32*) readonly + +!0 = metadata !{metadata !0} +!1 = metadata !{metadata !1} +!2 = metadata !{metadata !0, metadata !1} + |
