Index: llvm/trunk/lib/Analysis/AliasAnalysisSummary.h =================================================================== --- llvm/trunk/lib/Analysis/AliasAnalysisSummary.h +++ llvm/trunk/lib/Analysis/AliasAnalysisSummary.h @@ -0,0 +1,158 @@ +//=====- CFLSummary.h - Abstract stratified sets implementation. --------=====// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file defines various utility types and functions useful to +/// summary-based alias analysis. +/// +/// Summary-based analysis, also known as bottom-up analysis, is a style of +/// interprocedrual static analysis that tries to analyze the callees before the +/// callers get analyzed. The key idea of summary-based analysis is to first +/// process each function indepedently, outline its behavior in a condensed +/// summary, and then instantiate the summary at the callsite when the said +/// function is called elsewhere. This is often in contrast to another style +/// called top-down analysis, in which callers are always analyzed first before +/// the callees. +/// +/// In a summary-based analysis, functions must be examined independently and +/// out-of-context. We have no information on the state of the memory, the +/// arguments, the global values, and anything else external to the function. To +/// carry out the analysis conservative assumptions have to be made about those +/// external states. In exchange for the potential loss of precision, the +/// summary we obtain this way is highly reusable, which makes the analysis +/// easier to scale to large programs even if carried out context-sensitively. +/// +/// Currently, all CFL-based alias analyses adopt the summary-based approach +/// and therefore heavily rely on this header. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H +#define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H + +#include "llvm/ADT/Optional.h" +#include "llvm/IR/CallSite.h" +#include + +namespace llvm { +namespace cflaa { + +//===----------------------------------------------------------------------===// +// AliasAttr related stuffs +//===----------------------------------------------------------------------===// + +/// The number of attributes that AliasAttr should contain. Attributes are +/// described below, and 32 was an arbitrary choice because it fits nicely in 32 +/// bits (because we use a bitset for AliasAttr). +static const unsigned NumAliasAttrs = 32; + +/// These are attributes that an alias analysis can use to mark certain special +/// properties of a given pointer. Refer to the related functions below to see +/// what kinds of attributes are currently defined. +typedef std::bitset AliasAttrs; + +/// Attr represent whether the said pointer comes from an unknown source +/// (such as opaque memory or an integer cast). +AliasAttrs getAttrNone(); + +/// AttrUnknown represent whether the said pointer comes from a source not known +/// to alias analyses (such as opaque memory or an integer cast). +AliasAttrs getAttrUnknown(); +bool hasUnknownAttr(AliasAttrs); + +/// AttrCaller represent whether the said pointer comes from a source not known +/// to the current function but known to the caller. Values pointed to by the +/// arguments of the current function have this attribute set +AliasAttrs getAttrCaller(); +bool hasCallerAttr(AliasAttrs); +bool hasUnknownOrCallerAttr(AliasAttrs); + +/// AttrEscaped represent whether the said pointer comes from a known source but +/// escapes to the unknown world (e.g. casted to an integer, or passed as an +/// argument to opaque function). Unlike non-escaped pointers, escaped ones may +/// alias pointers coming from unknown sources. +AliasAttrs getAttrEscaped(); +bool hasEscapedAttr(AliasAttrs); + +/// AttrGlobal represent whether the said pointer is a global value. +/// AttrArg represent whether the said pointer is an argument, and if so, what +/// index the argument has. +AliasAttrs getGlobalOrArgAttrFromValue(const Value &); +bool isGlobalOrArgAttr(AliasAttrs); + +/// Given an AliasAttrs, return a new AliasAttrs that only contains attributes +/// meaningful to the caller. This function is primarily used for +/// interprocedural analysis +/// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal, +/// and AttrEscaped +AliasAttrs getExternallyVisibleAttrs(AliasAttrs); + +//===----------------------------------------------------------------------===// +// Function summary related stuffs +//===----------------------------------------------------------------------===// + +/// We use InterfaceValue to describe parameters/return value, as well as +/// potential memory locations that are pointed to by parameters/return value, +/// of a function. +/// Index is an integer which represents a single parameter or a return value. +/// When the index is 0, it refers to the return value. Non-zero index i refers +/// to the i-th parameter. +/// DerefLevel indicates the number of dereferences one must perform on the +/// parameter/return value to get this InterfaceValue. +struct InterfaceValue { + unsigned Index; + unsigned DerefLevel; +}; + +inline bool operator==(InterfaceValue lhs, InterfaceValue rhs) { + return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel; +} +inline bool operator!=(InterfaceValue lhs, InterfaceValue rhs) { + return !(lhs == rhs); +} + +/// We use ExternalRelation to describe an externally visible aliasing relations +/// between parameters/return value of a function. +struct ExternalRelation { + InterfaceValue From, To; +}; + +/// We use ExternalAttribute to describe an externally visible AliasAttrs +/// for parameters/return value. +struct ExternalAttribute { + InterfaceValue IValue; + AliasAttrs Attr; +}; + +/// This is the result of instantiating InterfaceValue at a particular callsite +struct InstantiatedValue { + Value *Val; + unsigned DerefLevel; +}; +Optional instantiateInterfaceValue(InterfaceValue, CallSite); + +/// This is the result of instantiating ExternalRelation at a particular +/// callsite +struct InstantiatedRelation { + InstantiatedValue From, To; +}; +Optional instantiateExternalRelation(ExternalRelation, + CallSite); + +/// This is the result of instantiating ExternalAttribute at a particular +/// callsite +struct InstantiatedAttr { + InstantiatedValue IValue; + AliasAttrs Attr; +}; +Optional instantiateExternalAttribute(ExternalAttribute, + CallSite); +} +} + +#endif Index: llvm/trunk/lib/Analysis/AliasAnalysisSummary.cpp =================================================================== --- llvm/trunk/lib/Analysis/AliasAnalysisSummary.cpp +++ llvm/trunk/lib/Analysis/AliasAnalysisSummary.cpp @@ -0,0 +1,105 @@ +#include "AliasAnalysisSummary.h" +#include "llvm/IR/Argument.h" +#include "llvm/IR/Type.h" +#include "llvm/Support/Compiler.h" + +namespace llvm { +namespace cflaa { + +namespace { +LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0; +LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1; +LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2; +LLVM_CONSTEXPR unsigned AttrCallerIndex = 3; +LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4; +LLVM_CONSTEXPR unsigned AttrLastArgIndex = NumAliasAttrs; +LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex; + +// NOTE: These aren't AliasAttrs because bitsets don't have a constexpr +// ctor for some versions of MSVC that we support. We could maybe refactor, +// but... +using AliasAttr = unsigned; +LLVM_CONSTEXPR AliasAttr AttrNone = 0; +LLVM_CONSTEXPR AliasAttr AttrEscaped = 1 << AttrEscapedIndex; +LLVM_CONSTEXPR AliasAttr AttrUnknown = 1 << AttrUnknownIndex; +LLVM_CONSTEXPR AliasAttr AttrGlobal = 1 << AttrGlobalIndex; +LLVM_CONSTEXPR AliasAttr AttrCaller = 1 << AttrCallerIndex; +LLVM_CONSTEXPR AliasAttr ExternalAttrMask = + AttrEscaped | AttrUnknown | AttrGlobal; +} + +AliasAttrs getAttrNone() { return AttrNone; } + +AliasAttrs getAttrUnknown() { return AttrUnknown; } +bool hasUnknownAttr(AliasAttrs Attr) { return Attr.test(AttrUnknownIndex); } + +AliasAttrs getAttrCaller() { return AttrCaller; } +bool hasCallerAttr(AliasAttrs Attr) { return Attr.test(AttrCaller); } +bool hasUnknownOrCallerAttr(AliasAttrs Attr) { + return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex); +} + +AliasAttrs getAttrEscaped() { return AttrEscaped; } +bool hasEscapedAttr(AliasAttrs Attr) { return Attr.test(AttrEscapedIndex); } + +static AliasAttr argNumberToAttr(unsigned ArgNum) { + if (ArgNum >= AttrMaxNumArgs) + return AttrUnknown; + // N.B. MSVC complains if we use `1U` here, since AliasAttr' ctor takes + // an unsigned long long. + return AliasAttr(1ULL << (ArgNum + AttrFirstArgIndex)); +} + +AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val) { + if (isa(Val)) + return AttrGlobal; + + if (auto *Arg = dyn_cast(&Val)) + // Only pointer arguments should have the argument attribute, + // because things can't escape through scalars without us seeing a + // cast, and thus, interaction with them doesn't matter. + if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy()) + return argNumberToAttr(Arg->getArgNo()); + return AttrNone; +} + +bool isGlobalOrArgAttr(AliasAttrs Attr) { + return Attr.reset(AttrEscapedIndex) + .reset(AttrUnknownIndex) + .reset(AttrCallerIndex) + .any(); +} + +AliasAttrs getExternallyVisibleAttrs(AliasAttrs Attr) { + return Attr & AliasAttrs(ExternalAttrMask); +} + +Optional instantiateInterfaceValue(InterfaceValue IValue, + CallSite CS) { + auto Index = IValue.Index; + auto Value = (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1); + if (Value->getType()->isPointerTy()) + return InstantiatedValue{Value, IValue.DerefLevel}; + return None; +} + +Optional +instantiateExternalRelation(ExternalRelation ERelation, CallSite CS) { + auto From = instantiateInterfaceValue(ERelation.From, CS); + if (!From) + return None; + auto To = instantiateInterfaceValue(ERelation.To, CS); + if (!To) + return None; + return InstantiatedRelation{*From, *To}; +} + +Optional instantiateExternalAttribute(ExternalAttribute EAttr, + CallSite CS) { + auto Value = instantiateInterfaceValue(EAttr.IValue, CS); + if (!Value) + return None; + return InstantiatedAttr{*Value, EAttr.Attr}; +} +} +} Index: llvm/trunk/lib/Analysis/CFLGraph.h =================================================================== --- llvm/trunk/lib/Analysis/CFLGraph.h +++ llvm/trunk/lib/Analysis/CFLGraph.h @@ -15,14 +15,11 @@ #ifndef LLVM_ANALYSIS_CFLGRAPH_H #define LLVM_ANALYSIS_CFLGRAPH_H -#include "StratifiedSets.h" +#include "AliasAnalysisSummary.h" +#include "llvm/ADT/STLExtras.h" namespace llvm { - -class Value; - namespace cflaa { - /// Edges can be one of four "weights" -- each weight must have an inverse /// weight (Assign has Assign; Reference has Dereference). enum class EdgeType { @@ -62,7 +59,7 @@ struct NodeInfo { EdgeList Edges; - StratifiedAttrs Attr; + AliasAttrs Attr; }; typedef DenseMap NodeMap; @@ -104,10 +101,12 @@ const_node_iterator; bool addNode(Node N) { - return NodeImpls.insert(std::make_pair(N, NodeInfo{EdgeList(), 0})).second; + return NodeImpls + .insert(std::make_pair(N, NodeInfo{EdgeList(), getAttrNone()})) + .second; } - void addAttr(Node N, StratifiedAttrs Attr) { + void addAttr(Node N, AliasAttrs Attr) { auto *Info = getNode(N); assert(Info != nullptr); Info->Attr |= Attr; @@ -123,7 +122,7 @@ ToInfo->Edges.push_back(Edge{flipWeight(Type), From}); } - StratifiedAttrs attrFor(Node N) const { + AliasAttrs attrFor(Node N) const { auto *Info = getNode(N); assert(Info != nullptr); return Info->Attr; Index: llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp @@ -37,6 +37,7 @@ #include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "CFLGraph.h" +#include "StratifiedSets.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" @@ -67,39 +68,6 @@ : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {} CFLSteensAAResult::~CFLSteensAAResult() {} -/// We use InterfaceValue to describe parameters/return value, as well as -/// potential memory locations that are pointed to by parameters/return value, -/// of a function. -/// Index is an integer which represents a single parameter or a return value. -/// When the index is 0, it refers to the return value. Non-zero index i refers -/// to the i-th parameter. -/// DerefLevel indicates the number of dereferences one must perform on the -/// parameter/return value to get this InterfaceValue. -struct InterfaceValue { - unsigned Index; - unsigned DerefLevel; -}; - -bool operator==(InterfaceValue lhs, InterfaceValue rhs) { - return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel; -} -bool operator!=(InterfaceValue lhs, InterfaceValue rhs) { - return !(lhs == rhs); -} - -/// We use ExternalRelation to describe an externally visible aliasing relations -/// between parameters/return value of a function. -struct ExternalRelation { - InterfaceValue From, To; -}; - -/// We use ExternalAttribute to describe an externally visible StratifiedAttrs -/// for parameters/return value. -struct ExternalAttribute { - InterfaceValue IValue; - StratifiedAttrs Attr; -}; - /// Information we have about a function and would like to keep around. class CFLSteensAAResult::FunctionInfo { StratifiedSets Sets; @@ -135,26 +103,6 @@ std::numeric_limits::max(); namespace { -/// StratifiedInfo Attribute things. -LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs; -LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0; -LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1; -LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2; -LLVM_CONSTEXPR unsigned AttrCallerIndex = 3; -LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4; -LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex; -LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex; - -// NOTE: These aren't StratifiedAttrs because bitsets don't have a constexpr -// ctor for some versions of MSVC that we support. We could maybe refactor, -// but... -using StratifiedAttr = unsigned; -LLVM_CONSTEXPR StratifiedAttr AttrEscaped = 1 << AttrEscapedIndex; -LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex; -LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex; -LLVM_CONSTEXPR StratifiedAttr AttrCaller = 1 << AttrCallerIndex; -LLVM_CONSTEXPR StratifiedAttr ExternalAttrMask = - AttrEscaped | AttrUnknown | AttrGlobal; /// The maximum number of arguments we can put into a summary. LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50; @@ -163,23 +111,6 @@ /// represent that locally. enum class Level { Same, Above, Below }; -// This is the result of instantiating InterfaceValue at a particular callsite -struct InterprocNode { - Value *Val; - unsigned DerefLevel; -}; - -// Interprocedural assignment edges that CFLGraph may not easily model -struct InterprocEdge { - InterprocNode From, To; -}; - -// Interprocedural attribute tagging that CFLGraph may not easily model -struct InterprocAttr { - InterprocNode Node; - StratifiedAttrs Attr; -}; - /// Gets the edges our graph should have, based on an Instruction* class GetEdgesVisitor : public InstVisitor { CFLSteensAAResult &AA; @@ -189,8 +120,8 @@ SmallVectorImpl &ReturnValues; SmallPtrSetImpl &Externals; SmallPtrSetImpl &Escapes; - SmallVectorImpl &InterprocEdges; - SmallVectorImpl &InterprocAttrs; + SmallVectorImpl &InstantiatedRelations; + SmallVectorImpl &InstantiatedAttrs; static bool hasUsefulEdges(ConstantExpr *CE) { // ConstantExpr doesn't have terminators, invokes, or fences, so only needs @@ -210,7 +141,7 @@ visitConstantExpr(CExpr); } - void addNodeWithAttr(Value *Val, StratifiedAttrs Attr) { + void addNodeWithAttr(Value *Val, AliasAttrs Attr) { addNode(Val); Graph.addAttr(Val, Attr); } @@ -229,11 +160,12 @@ CFLGraph &Graph, SmallVectorImpl &ReturnValues, SmallPtrSetImpl &Externals, SmallPtrSetImpl &Escapes, - SmallVectorImpl &InterprocEdges, - SmallVectorImpl &InterprocAttrs) + SmallVectorImpl &InstantiatedRelations, + SmallVectorImpl &InstantiatedAttrs) : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues), - Externals(Externals), Escapes(Escapes), InterprocEdges(InterprocEdges), - InterprocAttrs(InterprocAttrs) {} + Externals(Externals), Escapes(Escapes), + InstantiatedRelations(InstantiatedRelations), + InstantiatedAttrs(InstantiatedAttrs) {} void visitInstruction(Instruction &) { llvm_unreachable("Unsupported instruction encountered"); @@ -250,12 +182,12 @@ void visitPtrToIntInst(PtrToIntInst &Inst) { auto *Ptr = Inst.getOperand(0); - addNodeWithAttr(Ptr, AttrEscaped); + addNodeWithAttr(Ptr, getAttrEscaped()); } void visitIntToPtrInst(IntToPtrInst &Inst) { auto *Ptr = &Inst; - addNodeWithAttr(Ptr, AttrUnknown); + addNodeWithAttr(Ptr, getAttrUnknown()); } void visitCastInst(CastInst &Inst) { @@ -325,7 +257,7 @@ // 2. Increments (stores to) *Ptr by some target-specific amount. // For now, we'll handle this like a landingpad instruction (by placing the // result in its own group, and having that group alias externals). - addNodeWithAttr(&Inst, AttrUnknown); + addNodeWithAttr(&Inst, getAttrUnknown()); } static bool isFunctionExternal(Function *Fn) { @@ -350,35 +282,22 @@ return false; } - auto InstantiateInterfaceIndex = [&CS](unsigned Index) { - auto Value = - (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1); - return Value->getType()->isPointerTy() ? Value : nullptr; - }; - for (auto *Fn : Fns) { auto &FnInfo = AA.ensureCached(Fn); assert(FnInfo.hasValue()); auto &RetParamRelations = FnInfo->getRetParamRelations(); for (auto &Relation : RetParamRelations) { - auto FromVal = InstantiateInterfaceIndex(Relation.From.Index); - auto ToVal = InstantiateInterfaceIndex(Relation.To.Index); - if (FromVal && ToVal) { - auto FromLevel = Relation.From.DerefLevel; - auto ToLevel = Relation.To.DerefLevel; - InterprocEdges.push_back( - InterprocEdge{InterprocNode{FromVal, FromLevel}, - InterprocNode{ToVal, ToLevel}}); - } + auto IRelation = instantiateExternalRelation(Relation, CS); + if (IRelation.hasValue()) + InstantiatedRelations.push_back(*IRelation); } auto &RetParamAttributes = FnInfo->getRetParamAttributes(); for (auto &Attribute : RetParamAttributes) { - if (auto Val = InstantiateInterfaceIndex(Attribute.IValue.Index)) { - InterprocAttrs.push_back(InterprocAttr{ - InterprocNode{Val, Attribute.IValue.DerefLevel}, Attribute.Attr}); - } + auto IAttr = instantiateExternalAttribute(Attribute, CS); + if (IAttr.hasValue()) + InstantiatedAttrs.push_back(*IAttr); } } @@ -422,7 +341,7 @@ if (Inst->getType()->isPointerTy()) { auto *Fn = CS.getCalledFunction(); if (Fn == nullptr || !Fn->doesNotAlias(0)) - Graph.addAttr(Inst, AttrUnknown); + Graph.addAttr(Inst, getAttrUnknown()); } } @@ -447,7 +366,7 @@ // Exceptions come from "nowhere", from our analysis' perspective. // So we place the instruction its own group, noting that said group may // alias externals - addNodeWithAttr(&Inst, AttrUnknown); + addNodeWithAttr(&Inst, getAttrUnknown()); } void visitInsertValueInst(InsertValueInst &Inst) { @@ -495,8 +414,8 @@ // Auxiliary structures used by the builder SmallPtrSet ExternalValues; SmallPtrSet EscapedValues; - SmallVector InterprocEdges; - SmallVector InterprocAttrs; + SmallVector InstantiatedRelations; + SmallVector InstantiatedAttrs; // Helper functions @@ -528,7 +447,7 @@ return; GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues, - EscapedValues, InterprocEdges, InterprocAttrs) + EscapedValues, InstantiatedRelations, InstantiatedAttrs) .visit(Inst); } @@ -560,11 +479,11 @@ const SmallPtrSet &getEscapedValues() const { return EscapedValues; } - const SmallVector &getInterprocEdges() const { - return InterprocEdges; + const SmallVector &getInstantiatedRelations() const { + return InstantiatedRelations; } - const SmallVector &getInterprocAttrs() const { - return InterprocAttrs; + const SmallVector &getInstantiatedAttrs() const { + return InstantiatedAttrs; } }; } @@ -573,20 +492,6 @@ // Function declarations that require types defined in the namespace above //===----------------------------------------------------------------------===// -/// Given a StratifiedAttrs, returns true if it marks the corresponding values -/// as globals or arguments -static bool isGlobalOrArgAttr(StratifiedAttrs Attr); - -/// Given a StratifiedAttrs, returns true if the corresponding values come from -/// an unknown source (such as opaque memory or an integer cast) -static bool isUnknownAttr(StratifiedAttrs Attr); - -/// Given an argument number, returns the appropriate StratifiedAttr to set. -static StratifiedAttrs argNumberToAttr(unsigned ArgNum); - -/// Given a Value, potentially return which StratifiedAttr it maps to. -static Optional valueToAttr(Value *Val); - /// Gets the "Level" that one should travel in StratifiedSets /// given an EdgeType. static Level directionOfEdgeType(EdgeType); @@ -617,38 +522,6 @@ return false; } -static bool isGlobalOrArgAttr(StratifiedAttrs Attr) { - return Attr.reset(AttrEscapedIndex) - .reset(AttrUnknownIndex) - .reset(AttrCallerIndex) - .any(); -} - -static bool isUnknownAttr(StratifiedAttrs Attr) { - return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex); -} - -static Optional valueToAttr(Value *Val) { - if (isa(Val)) - return StratifiedAttrs(AttrGlobal); - - if (auto *Arg = dyn_cast(Val)) - // Only pointer arguments should have the argument attribute, - // because things can't escape through scalars without us seeing a - // cast, and thus, interaction with them doesn't matter. - if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy()) - return argNumberToAttr(Arg->getArgNo()); - return None; -} - -static StratifiedAttrs argNumberToAttr(unsigned ArgNum) { - if (ArgNum >= AttrMaxNumArgs) - return AttrUnknown; - // N.B. MSVC complains if we use `1U` here, since StratifiedAttrs' ctor takes - // an unsigned long long. - return StratifiedAttrs(1ULL << (ArgNum + AttrFirstArgIndex)); -} - static Level directionOfEdgeType(EdgeType Weight) { switch (Weight) { case EdgeType::Reference: @@ -715,7 +588,7 @@ auto &Link = Sets.getLink(SetIndex); InterfaceMap.insert(std::make_pair(SetIndex, CurrValue)); - auto ExternalAttrs = Link.Attrs & StratifiedAttrs(ExternalAttrMask); + auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs); if (ExternalAttrs.any()) RetParamAttributes.push_back( ExternalAttribute{CurrValue, ExternalAttrs}); @@ -796,18 +669,18 @@ // Special handling for globals and arguments for (auto *External : GraphBuilder.getExternalValues()) { SetBuilder.add(External); - auto Attr = valueToAttr(External); - if (Attr.hasValue()) { - SetBuilder.noteAttributes(External, *Attr); - if (*Attr == AttrGlobal) - SetBuilder.addAttributesBelow(External, 1, AttrUnknown); + auto Attr = getGlobalOrArgAttrFromValue(*External); + if (Attr.any()) { + SetBuilder.noteAttributes(External, Attr); + if (isa(External)) + SetBuilder.addAttributesBelow(External, 1, getAttrUnknown()); else - SetBuilder.addAttributesBelow(External, 1, AttrCaller); + SetBuilder.addAttributesBelow(External, 1, getAttrCaller()); } } // Special handling for interprocedural aliases - for (auto &Edge : GraphBuilder.getInterprocEdges()) { + for (auto &Edge : GraphBuilder.getInstantiatedRelations()) { auto FromVal = Edge.From.Val; auto ToVal = Edge.To.Val; SetBuilder.add(FromVal); @@ -817,17 +690,17 @@ } // Special handling for interprocedural attributes - for (auto &IPAttr : GraphBuilder.getInterprocAttrs()) { - auto Val = IPAttr.Node.Val; + for (auto &IPAttr : GraphBuilder.getInstantiatedAttrs()) { + auto Val = IPAttr.IValue.Val; SetBuilder.add(Val); - SetBuilder.addAttributesBelow(Val, IPAttr.Node.DerefLevel, IPAttr.Attr); + SetBuilder.addAttributesBelow(Val, IPAttr.IValue.DerefLevel, IPAttr.Attr); } // Special handling for opaque external functions for (auto *Escape : GraphBuilder.getEscapedValues()) { SetBuilder.add(Escape); - SetBuilder.noteAttributes(Escape, AttrEscaped); - SetBuilder.addAttributesBelow(Escape, 1, AttrUnknown); + SetBuilder.noteAttributes(Escape, getAttrEscaped()); + SetBuilder.addAttributesBelow(Escape, 1, getAttrUnknown()); } return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); @@ -923,7 +796,7 @@ return MayAlias; if (AttrsA.none() || AttrsB.none()) return NoAlias; - if (isUnknownAttr(AttrsA) || isUnknownAttr(AttrsB)) + if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB)) return MayAlias; if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB)) return MayAlias; Index: llvm/trunk/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Analysis/CMakeLists.txt +++ llvm/trunk/lib/Analysis/CMakeLists.txt @@ -1,6 +1,7 @@ add_llvm_library(LLVMAnalysis AliasAnalysis.cpp AliasAnalysisEvaluator.cpp + AliasAnalysisSummary.cpp AliasSetTracker.cpp Analysis.cpp AssumptionCache.cpp Index: llvm/trunk/lib/Analysis/StratifiedSets.h =================================================================== --- llvm/trunk/lib/Analysis/StratifiedSets.h +++ llvm/trunk/lib/Analysis/StratifiedSets.h @@ -10,6 +10,7 @@ #ifndef LLVM_ADT_STRATIFIEDSETS_H #define LLVM_ADT_STRATIFIEDSETS_H +#include "AliasAnalysisSummary.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallSet.h" @@ -34,17 +35,6 @@ /// For field sensitivity, etc. we can tack fields on here. }; -/// The number of attributes that StratifiedAttrs should contain. Attributes are -/// described below, and 32 was an arbitrary choice because it fits nicely in 32 -/// bits (because we use a bitset for StratifiedAttrs). -static const unsigned NumStratifiedAttrs = 32; - -/// These are attributes that the users of StratifiedSets/StratifiedSetBuilders -/// may use for various purposes. These also have the special property of that -/// they are merged down. So, if set A is above set B, and one decides to set an -/// attribute in set A, then the attribute will automatically be set in set B. -typedef std::bitset StratifiedAttrs; - /// A "link" between two StratifiedSets. struct StratifiedLink { /// \brief This is a value used to signify "does not exist" where the @@ -62,7 +52,7 @@ StratifiedIndex Below; /// Attributes for these StratifiedSets. - StratifiedAttrs Attrs; + AliasAttrs Attrs; StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {} @@ -243,14 +233,14 @@ return Link.Above; } - StratifiedAttrs &getAttrs() { + AliasAttrs getAttrs() { assert(!isRemapped()); return Link.Attrs; } - void setAttrs(const StratifiedAttrs &other) { + void setAttrs(AliasAttrs Other) { assert(!isRemapped()); - Link.Attrs |= other; + Link.Attrs |= Other; } bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; } @@ -396,9 +386,9 @@ return addAtMerging(ToAdd, Below); } - /// \brief Set the StratifiedAttrs of the set "Level"-levels below "Main". If + /// \brief Set the AliasAttrs of the set "Level"-levels below "Main". If /// there is no set below "Main", create one for it. - void addAttributesBelow(const T &Main, unsigned Level, StratifiedAttrs Attr) { + void addAttributesBelow(const T &Main, unsigned Level, AliasAttrs Attr) { assert(has(Main)); auto Index = *indexOf(Main); auto *Link = &linksAt(Index); @@ -436,7 +426,7 @@ merge(MainIndex, ToAddIndex); } - void noteAttributes(const T &Main, const StratifiedAttrs &NewAttrs) { + void noteAttributes(const T &Main, AliasAttrs NewAttrs) { assert(has(Main)); auto *Info = *get(Main); auto &Link = linksAt(Info->Index); @@ -538,7 +528,7 @@ // match `LinksFrom.Below` // > If both have links above, deal with those next. while (LinksInto->hasBelow() && LinksFrom->hasBelow()) { - auto &FromAttrs = LinksFrom->getAttrs(); + auto FromAttrs = LinksFrom->getAttrs(); LinksInto->setAttrs(FromAttrs); // Remap needs to happen after getBelow(), but before