[CFLAA] Moved StratifiedAttrs and summary-related stuffs out of CFLSteensAliasAnalysis

[grievejia]

Summary

This patch continues the work of moving codes out of CFLSteensAliasAnalysis so that CFLAndersAliasAnalysis could also use them.

StratifiedAttrs is one such utility. It has been renamed to AliasAttrs, since its usage may no longer be local to StratifiedSets any more.

Summary-related structs, such as InterfaceValue, ExternalRelation, etc, are also refactored out. Again, the idea is to leave only Steensgard-specific codes in CFLSteensAliasAnalysis.cpp, and put summary-related codes in AliasAnalysisSummary.cpp

[george.burgess.iv]

The mechanical refactors for this (and D21963) look good. I don't really
like throwing so many generally-named things into llvm::, though (e.g.
llvm::EdgeType, ...). Could we do something like putting all of this into
a llvm::cflaa namespace, please? If it makes life easier, feel free to
put using namespace llvm::cflaa; at the top of our cpp files. :)

(Same comments apply to 21963)

Thank you!

[grievejia]

Added the cflaa namespace

[george.burgess.iv]

Explicitly LGTMing for code historians.

llvm/trunk/lib/Analysis/AliasAnalysisSummary.h

+//=====- 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 <bitset>
+
+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<NumAliasAttrs> 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<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite);
+
+/// This is the result of instantiating ExternalRelation at a particular
+/// callsite
+struct InstantiatedRelation {
+  InstantiatedValue From, To;
+};
+Optional<InstantiatedRelation> instantiateExternalRelation(ExternalRelation,
+                                                           CallSite);
+
+/// This is the result of instantiating ExternalAttribute at a particular
+/// callsite
+struct InstantiatedAttr {
+  InstantiatedValue IValue;
+  AliasAttrs Attr;
+};
+Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute,
+                                                        CallSite);
+}
+}
+
+#endif

llvm/trunk/lib/Analysis/AliasAnalysisSummary.cpp

+#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<GlobalValue>(Val))
+    return AttrGlobal;
+
+  if (auto *Arg = dyn_cast<Argument>(&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<InstantiatedValue> 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<InstantiatedRelation>
+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<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute EAttr,
+                                                        CallSite CS) {
+  auto Value = instantiateInterfaceValue(EAttr.IValue, CS);
+  if (!Value)
+    return None;
+  return InstantiatedAttr{*Value, EAttr.Attr};
+}
+}
+}

llvm/trunk/lib/Analysis/CFLGraph.h

 /// This file defines CFLGraph, an auxiliary data structure used by CFL-based
 /// alias analysis.
 ///
 //===----------------------------------------------------------------------===//
 
 #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 {
   /// The weight assigned when assigning from or to a value. For example, in:
   /// %b = getelementptr %a, 0
   /// ...The relationships are %b assign %a, and %a assign %b. This used to be
   /// two edges, but having a distinction bought us nothing.
   Assign,
struct Edge {
     EdgeType Type;
     Node Other;
   };
 
   typedef std::vector<Edge> EdgeList;
 
   struct NodeInfo {
     EdgeList Edges;
-    StratifiedAttrs Attr;
+    AliasAttrs Attr;
   };
 
   typedef DenseMap<Node, NodeInfo> NodeMap;
   NodeMap NodeImpls;
 
   // Gets the inverse of a given EdgeType.
   static EdgeType flipWeight(EdgeType Initial) {
     switch (Initial) {
typedef std::pointer_to_unary_function<const NodeMap::value_type &, Node>
       NodeDerefFun;
 
 public:
   typedef EdgeList::const_iterator const_edge_iterator;
   typedef mapped_iterator<NodeMap::const_iterator, NodeDerefFun>
       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;
   }
 
   void addEdge(Node From, Node To, EdgeType Type) {
     auto *FromInfo = getNode(From);
     assert(FromInfo != nullptr);
     auto *ToInfo = getNode(To);
     assert(ToInfo != nullptr);
 
     FromInfo->Edges.push_back(Edge{Type, To});
     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;
   }
 
   iterator_range<const_edge_iterator> edgesFor(Node N) const {
     auto *Info = getNode(N);
     assert(Info != nullptr);

llvm/trunk/lib/Analysis/CFLSteensAliasAnalysis.cpp

 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
 // CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because
 // FunctionPasses are only allowed to inspect the Function that they're being
 // run on. Realistically, this likely isn't a problem until we allow
 // FunctionPasses to run concurrently.
 
 #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"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstVisitor.h"

 #define DEBUG_TYPE "cfl-steens-aa"
 
 CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
     : AAResultBase(), TLI(TLI) {}
 CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
     : 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<Value *> Sets;
 
   // RetParamRelations is a collection of ExternalRelations.
   SmallVector<ExternalRelation, 8> RetParamRelations;
 
   // RetParamAttributes is a collection of ExternalAttributes.

 /// SmallVectorImpl. Returns true if targets found, false otherwise. This is
 /// templated so we can use it with CallInsts and InvokeInsts.
 static bool getPossibleTargets(CallSite, SmallVectorImpl<Function *> &);
 
 const StratifiedIndex StratifiedLink::SetSentinel =
     std::numeric_limits<StratifiedIndex>::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;
 
 /// StratifiedSets call for knowledge of "direction", so this is how we
 /// 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<GetEdgesVisitor, void> {
   CFLSteensAAResult &AA;
   const TargetLibraryInfo &TLI;
 
   CFLGraph &Graph;
   SmallVectorImpl<Value *> &ReturnValues;
   SmallPtrSetImpl<Value *> &Externals;
   SmallPtrSetImpl<Value *> &Escapes;
-  SmallVectorImpl<InterprocEdge> &InterprocEdges;
-  SmallVectorImpl<InterprocAttr> &InterprocAttrs;
+  SmallVectorImpl<InstantiatedRelation> &InstantiatedRelations;
+  SmallVectorImpl<InstantiatedAttr> &InstantiatedAttrs;
 
   static bool hasUsefulEdges(ConstantExpr *CE) {
     // ConstantExpr doesn't have terminators, invokes, or fences, so only needs
     // to check for compares.
     return CE->getOpcode() != Instruction::ICmp &&
            CE->getOpcode() != Instruction::FCmp;
   }
 
   void addNode(Value *Val) {
     if (!Graph.addNode(Val))
       return;
 
     if (isa<GlobalValue>(Val))
       Externals.insert(Val);
     else if (auto CExpr = dyn_cast<ConstantExpr>(Val))
       if (hasUsefulEdges(CExpr))
         visitConstantExpr(CExpr);
   }
 
-  void addNodeWithAttr(Value *Val, StratifiedAttrs Attr) {
+  void addNodeWithAttr(Value *Val, AliasAttrs Attr) {
     addNode(Val);
     Graph.addAttr(Val, Attr);
   }
 
   void addEdge(Value *From, Value *To, EdgeType Type) {
     if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy())
       return;
     addNode(From);
     if (To != From)
       addNode(To);
     Graph.addEdge(From, To, Type);
   }
 
 public:
   GetEdgesVisitor(CFLSteensAAResult &AA, const TargetLibraryInfo &TLI,
                   CFLGraph &Graph, SmallVectorImpl<Value *> &ReturnValues,
                   SmallPtrSetImpl<Value *> &Externals,
                   SmallPtrSetImpl<Value *> &Escapes,
-                  SmallVectorImpl<InterprocEdge> &InterprocEdges,
-                  SmallVectorImpl<InterprocAttr> &InterprocAttrs)
+                  SmallVectorImpl<InstantiatedRelation> &InstantiatedRelations,
+                  SmallVectorImpl<InstantiatedAttr> &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");
   }
 
   void visitReturnInst(ReturnInst &Inst) {
     if (auto RetVal = Inst.getReturnValue()) {
       if (RetVal->getType()->isPointerTy()) {
         addNode(RetVal);
         ReturnValues.push_back(RetVal);
       }
     }
   }
 
   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) {
     auto *Src = Inst.getOperand(0);
     addEdge(Src, &Inst, EdgeType::Assign);
   }
 
   void visitBinaryOperator(BinaryOperator &Inst) {
public:
 
   void visitVAArgInst(VAArgInst &Inst) {
     // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does
     // two things:
     //  1. Loads a value from *((T*)*Ptr).
     //  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) {
     return !Fn->hasExactDefinition();
   }
 
   bool tryInterproceduralAnalysis(CallSite CS,
                                   const SmallVectorImpl<Function *> &Fns) {
     assert(Fns.size() > 0);
 
     if (CS.arg_size() > MaxSupportedArgsInSummary)
       return false;
 
     // Exit early if we'll fail anyway
     for (auto *Fn : Fns) {
       if (isFunctionExternal(Fn) || Fn->isVarArg())
         return false;
       // Fail if the caller does not provide enough arguments
       assert(Fn->arg_size() <= CS.arg_size());
       auto &MaybeInfo = AA.ensureCached(Fn);
       if (!MaybeInfo.hasValue())
         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);
       }
     }
 
     return true;
   }
 
   void visitCallSite(CallSite CS) {
     auto Inst = CS.getInstruction();
if (!CS.onlyReadsMemory())
       for (Value *V : CS.args()) {
         if (V->getType()->isPointerTy())
           Escapes.insert(V);
       }
 
     if (Inst->getType()->isPointerTy()) {
       auto *Fn = CS.getCalledFunction();
       if (Fn == nullptr || !Fn->doesNotAlias(0))
-        Graph.addAttr(Inst, AttrUnknown);
+        Graph.addAttr(Inst, getAttrUnknown());
     }
   }
 
   /// Because vectors/aggregates are immutable and unaddressable, there's
   /// nothing we can do to coax a value out of them, other than calling
   /// Extract{Element,Value}. We can effectively treat them as pointers to
   /// arbitrary memory locations we can store in and load from.
   void visitExtractElementInst(ExtractElementInst &Inst) {
     auto *Ptr = Inst.getVectorOperand();
     auto *Val = &Inst;
     addEdge(Val, Ptr, EdgeType::Reference);
   }
 
   void visitInsertElementInst(InsertElementInst &Inst) {
     auto *Vec = Inst.getOperand(0);
     auto *Val = Inst.getOperand(1);
     addEdge(Vec, &Inst, EdgeType::Assign);
     addEdge(&Inst, Val, EdgeType::Dereference);
   }
 
   void visitLandingPadInst(LandingPadInst &Inst) {
     // 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) {
     auto *Agg = Inst.getOperand(0);
     auto *Val = Inst.getOperand(1);
     addEdge(Agg, &Inst, EdgeType::Assign);
     addEdge(&Inst, Val, EdgeType::Dereference);
   }
class CFLGraphBuilder {
 
   // Output of the builder
   CFLGraph Graph;
   SmallVector<Value *, 4> ReturnedValues;
 
   // Auxiliary structures used by the builder
   SmallPtrSet<Value *, 8> ExternalValues;
   SmallPtrSet<Value *, 8> EscapedValues;
-  SmallVector<InterprocEdge, 8> InterprocEdges;
-  SmallVector<InterprocAttr, 8> InterprocAttrs;
+  SmallVector<InstantiatedRelation, 8> InstantiatedRelations;
+  SmallVector<InstantiatedAttr, 8> InstantiatedAttrs;
 
   // Helper functions
 
   // Determines whether or not we an instruction is useless to us (e.g.
   // FenceInst)
   static bool hasUsefulEdges(Instruction *Inst) {
     bool IsNonInvokeRetTerminator = isa<TerminatorInst>(Inst) &&
                                     !isa<InvokeInst>(Inst) &&
class CFLGraphBuilder {
   //   %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2
   // addInstructionToGraph would add both the `load` and `getelementptr`
   // instructions to the graph appropriately.
   void addInstructionToGraph(Instruction &Inst) {
     if (!hasUsefulEdges(&Inst))
       return;
 
     GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues,
-                    EscapedValues, InterprocEdges, InterprocAttrs)
+                    EscapedValues, InstantiatedRelations, InstantiatedAttrs)
         .visit(Inst);
   }
 
   // Builds the graph needed for constructing the StratifiedSets for the given
   // function
   void buildGraphFrom(Function &Fn) {
     for (auto &Bb : Fn.getBasicBlockList())
       for (auto &Inst : Bb.getInstList())
const SmallVector<Value *, 4> &getReturnValues() const {
     return ReturnedValues;
   }
   const SmallPtrSet<Value *, 8> &getExternalValues() const {
     return ExternalValues;
   }
   const SmallPtrSet<Value *, 8> &getEscapedValues() const {
     return EscapedValues;
   }
-  const SmallVector<InterprocEdge, 8> &getInterprocEdges() const {
-    return InterprocEdges;
+  const SmallVector<InstantiatedRelation, 8> &getInstantiatedRelations() const {
+    return InstantiatedRelations;
   }
-  const SmallVector<InterprocAttr, 8> &getInterprocAttrs() const {
-    return InterprocAttrs;
+  const SmallVector<InstantiatedAttr, 8> &getInstantiatedAttrs() const {
+    return InstantiatedAttrs;
   }
 };
 }
 
 //===----------------------------------------------------------------------===//
 // 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<StratifiedAttrs> valueToAttr(Value *Val);
-
 /// Gets the "Level" that one should travel in StratifiedSets
 /// given an EdgeType.
 static Level directionOfEdgeType(EdgeType);
 
 /// Determines whether it would be pointless to add the given Value to our sets.
 static bool canSkipAddingToSets(Value *Val);
 
 static Optional<Function *> parentFunctionOfValue(Value *Val) {
if (auto *Fn = CS.getCalledFunction()) {
     return true;
   }
 
   // TODO: If the call is indirect, we might be able to enumerate all potential
   // targets of the call and return them, rather than just failing.
   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<StratifiedAttrs> valueToAttr(Value *Val) {
-  if (isa<GlobalValue>(Val))
-    return StratifiedAttrs(AttrGlobal);
-
-  if (auto *Arg = dyn_cast<Argument>(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:
     return Level::Above;
   case EdgeType::Dereference:
     return Level::Below;
   case EdgeType::Assign:
     return Level::Same;
while (true) {
       if (Itr != InterfaceMap.end()) {
         if (CurrValue != Itr->second)
           RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second});
         break;
       }
 
       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});
 
       if (!Link.hasBelow())
         break;
 
       ++Level;
for (const auto &Edge : Graph.edgesFor(CurValue)) {
       if (Added)
         Worklist.push_back(OtherValue);
     }
   }
 
   // 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<GlobalValue>(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);
     SetBuilder.add(ToVal);
     SetBuilder.addBelowWith(FromVal, Edge.From.DerefLevel, ToVal,
                             Edge.To.DerefLevel);
   }
 
   // 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());
 }
 
 void CFLSteensAAResult::scan(Function *Fn) {
   auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
   (void)InsertPair;
AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
   // - Non-local values may alias each other
   // - AttrNone values do not alias any non-local values
   // - AttrEscaped do not alias globals/arguments, but they may alias
   // AttrUnknown values
   if (SetA.Index == SetB.Index)
     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;
   return NoAlias;
 }
 
 ModRefInfo CFLSteensAAResult::getArgModRefInfo(ImmutableCallSite CS,
                                                unsigned ArgIdx) {

llvm/trunk/lib/Analysis/CMakeLists.txt

 add_llvm_library(LLVMAnalysis
   AliasAnalysis.cpp
   AliasAnalysisEvaluator.cpp
+  AliasAnalysisSummary.cpp
   AliasSetTracker.cpp
   Analysis.cpp
   AssumptionCache.cpp
   BasicAliasAnalysis.cpp
   BlockFrequencyInfo.cpp
   BlockFrequencyInfoImpl.cpp
   BranchProbabilityInfo.cpp
   CFG.cpp

llvm/trunk/lib/Analysis/StratifiedSets.h

 //===- StratifiedSets.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.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/ADT/SmallVector.h"
 #include <bitset>
 #include <cassert>
 #include <cmath>
 #include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 namespace cflaa {
 /// An index into Stratified Sets.
 typedef unsigned StratifiedIndex;
 /// NOTE: ^ This can't be a short -- bootstrapping clang has a case where
 /// ~1M sets exist.
 
 // \brief Container of information related to a value in a StratifiedSet.
 struct StratifiedInfo {
   StratifiedIndex Index;
   /// 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<NumStratifiedAttrs> StratifiedAttrs;
-
 /// A "link" between two StratifiedSets.
 struct StratifiedLink {
   /// \brief This is a value used to signify "does not exist" where the
   /// StratifiedIndex type is used.
   ///
   /// This is used instead of Optional<StratifiedIndex> because
   /// Optional<StratifiedIndex> would eat up a considerable amount of extra
   /// memory, after struct padding/alignment is taken into account.
   static const StratifiedIndex SetSentinel;
 
   /// The index for the set "above" current
   StratifiedIndex Above;
 
   /// The link for the set "below" current
   StratifiedIndex Below;
 
   /// Attributes for these StratifiedSets.
-  StratifiedAttrs Attrs;
+  AliasAttrs Attrs;
 
   StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {}
 
   bool hasBelow() const { return Below != SetSentinel; }
   bool hasAbove() const { return Above != SetSentinel; }
 
   void clearBelow() { Below = SetSentinel; }
   void clearAbove() { Above = SetSentinel; }
struct BuilderLink {
     }
 
     StratifiedIndex getAbove() const {
       assert(!isRemapped());
       assert(hasAbove());
       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; }
 
     /// For initial remapping to another set
     void remapTo(StratifiedIndex Other) {
       assert(!isRemapped());
       Remap = Other;
bool addBelow(const T &Main, const T &ToAdd) {
     auto Index = *indexOf(Main);
     if (!linksAt(Index).hasBelow())
       addLinkBelow(Index);
 
     auto Below = linksAt(Index).getBelow();
     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);
 
     for (unsigned I = 0; I < Level; ++I) {
       Index = Link->hasBelow() ? Link->getBelow() : addLinkBelow(Index);
       Link = &linksAt(Index);
     }
auto GetIndexBelow = [&](StratifiedIndex Index, unsigned NumLevel) {
       return Index;
     };
     auto MainIndex = GetIndexBelow(*indexOf(Main), MainBelow);
     auto ToAddIndex = GetIndexBelow(*indexOf(ToAdd), ToAddBelow);
     if (&linksAt(MainIndex) != &linksAt(ToAddIndex))
       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);
     Link.setAttrs(NewAttrs);
   }
 
 private:
   DenseMap<T, StratifiedInfo> Values;
void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) {
 
     // Merging strategy:
     //  > If neither has links below, stop.
     //  > If only `LinksInto` has links below, stop.
     //  > If only `LinksFrom` has links below, reset `LinksInto.Below` to
     //  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
       // assignment of LinksFrom
       auto *NewLinksFrom = &linksAt(LinksFrom->getBelow());
       LinksFrom->remapTo(LinksInto->Number);
       LinksFrom = NewLinksFrom;
       LinksInto = &linksAt(LinksInto->getBelow());