diff options
| -rw-r--r-- | llvm/lib/Analysis/CFLAliasAnalysis.cpp | 237 | ||||
| -rw-r--r-- | llvm/lib/Analysis/StratifiedSets.h | 331 |
2 files changed, 276 insertions, 292 deletions
diff --git a/llvm/lib/Analysis/CFLAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAliasAnalysis.cpp index d56d5bcd5c7..929d6b6a57f 100644 --- a/llvm/lib/Analysis/CFLAliasAnalysis.cpp +++ b/llvm/lib/Analysis/CFLAliasAnalysis.cpp @@ -62,7 +62,7 @@ CFLAAResult::CFLAAResult() : AAResultBase() {} CFLAAResult::CFLAAResult(CFLAAResult &&Arg) : AAResultBase(std::move(Arg)) {} CFLAAResult::~CFLAAResult() {} -// \brief Information we have about a function and would like to keep around +/// Information we have about a function and would like to keep around. struct CFLAAResult::FunctionInfo { StratifiedSets<Value *> Sets; // Lots of functions have < 4 returns. Adjust as necessary. @@ -72,33 +72,31 @@ struct CFLAAResult::FunctionInfo { : Sets(std::move(S)), ReturnedValues(std::move(RV)) {} }; -// Try to go from a Value* to a Function*. Never returns nullptr. +/// Try to go from a Value* to a Function*. Never returns nullptr. static Optional<Function *> parentFunctionOfValue(Value *); -// Returns possible functions called by the Inst* into the given -// SmallVectorImpl. Returns true if targets found, false otherwise. -// This is templated because InvokeInst/CallInst give us the same -// set of functions that we care about, and I don't like repeating -// myself. +/// Returns possible functions called by the Inst* into the given +/// SmallVectorImpl. Returns true if targets found, false otherwise. This is +/// templated so we can use it with CallInsts and InvokeInsts. template <typename Inst> static bool getPossibleTargets(Inst *, SmallVectorImpl<Function *> &); -// Some instructions need to have their users tracked. Instructions like -// `add` require you to get the users of the Instruction* itself, other -// instructions like `store` require you to get the users of the first -// operand. This function gets the "proper" value to track for each -// type of instruction we support. +/// Some instructions need to have their users tracked. Instructions like +/// `add` require you to get the users of the Instruction* itself, other +/// instructions like `store` require you to get the users of the first +/// operand. This function gets the "proper" value to track for each +/// type of instruction we support. static Optional<Value *> getTargetValue(Instruction *); -// There are certain instructions (i.e. FenceInst, etc.) that we ignore. -// This notes that we should ignore those. +/// Determines whether or not we an instruction is useless to us (e.g. +/// FenceInst) static bool hasUsefulEdges(Instruction *); const StratifiedIndex StratifiedLink::SetSentinel = std::numeric_limits<StratifiedIndex>::max(); namespace { -// StratifiedInfo Attribute things. +/// StratifiedInfo Attribute things. typedef unsigned StratifiedAttr; LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs; LLVM_CONSTEXPR unsigned AttrAllIndex = 0; @@ -112,53 +110,53 @@ LLVM_CONSTEXPR StratifiedAttr AttrNone = 0; LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex; LLVM_CONSTEXPR StratifiedAttr AttrAll = ~AttrNone; -// \brief StratifiedSets call for knowledge of "direction", so this is how we -// represent that locally. +/// StratifiedSets call for knowledge of "direction", so this is how we +/// represent that locally. enum class Level { Same, Above, Below }; -// \brief Edges can be one of four "weights" -- each weight must have an inverse -// weight (Assign has Assign; Reference has Dereference). +/// 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. + /// 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, - // The edge used when we have an edge going from some handle to a Value. - // Examples of this include: - // %b = load %a (%b Dereference %a) - // %b = extractelement %a, 0 (%a Dereference %b) + /// The edge used when we have an edge going from some handle to a Value. + /// Examples of this include: + /// %b = load %a (%b Dereference %a) + /// %b = extractelement %a, 0 (%a Dereference %b) Dereference, - // The edge used when our edge goes from a value to a handle that may have - // contained it at some point. Examples: - // %b = load %a (%a Reference %b) - // %b = extractelement %a, 0 (%b Reference %a) + /// The edge used when our edge goes from a value to a handle that may have + /// contained it at some point. Examples: + /// %b = load %a (%a Reference %b) + /// %b = extractelement %a, 0 (%b Reference %a) Reference }; // \brief Encodes the notion of a "use" struct Edge { - // \brief Which value the edge is coming from + /// Which value the edge is coming from Value *From; - // \brief Which value the edge is pointing to + /// Which value the edge is pointing to Value *To; - // \brief Edge weight + /// Edge weight EdgeType Weight; - // \brief Whether we aliased any external values along the way that may be - // invisible to the analysis (i.e. landingpad for exceptions, calls for - // interprocedural analysis, etc.) + /// Whether we aliased any external values along the way that may be + /// invisible to the analysis (i.e. landingpad for exceptions, calls for + /// interprocedural analysis, etc.) StratifiedAttrs AdditionalAttrs; Edge(Value *From, Value *To, EdgeType W, StratifiedAttrs A) : From(From), To(To), Weight(W), AdditionalAttrs(A) {} }; -// \brief Gets the edges our graph should have, based on an Instruction* +/// Gets the edges our graph should have, based on an Instruction* class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> { CFLAAResult &AA; SmallVectorImpl<Edge> &Output; @@ -258,8 +256,8 @@ public: return Fn->isDeclaration() || !Fn->hasLocalLinkage(); } - // Gets whether the sets at Index1 above, below, or equal to the sets at - // Index2. Returns None if they are not in the same set chain. + /// Gets whether the sets at Index1 above, below, or equal to the sets at + /// Index2. Returns None if they are not in the same set chain. static Optional<Level> getIndexRelation(const StratifiedSets<Value *> &Sets, StratifiedIndex Index1, StratifiedIndex Index2) { @@ -291,8 +289,8 @@ public: const unsigned MaxSupportedArgs = 50; assert(Fns.size() > 0); - // I put this here to give us an upper bound on time taken by IPA. Is it - // really (realistically) needed? Keep in mind that we do have an n^2 algo. + // This algorithm is n^2, so an arbitrary upper-bound of 50 args was + // selected, so it doesn't take too long in insane cases. if (std::distance(Args.begin(), Args.end()) > (int)MaxSupportedArgs) return false; @@ -351,12 +349,12 @@ public: if (Parameters.size() != Arguments.size()) return false; - // Adding edges between arguments for arguments that may end up aliasing - // each other. This is necessary for functions such as - // void foo(int** a, int** b) { *a = *b; } - // (Technically, the proper sets for this would be those below - // Arguments[I] and Arguments[X], but our algorithm will produce - // extremely similar, and equally correct, results either way) + /// Adding edges between arguments for arguments that may end up aliasing + /// each other. This is necessary for functions such as + /// void foo(int** a, int** b) { *a = *b; } + /// (Technically, the proper sets for this would be those below + /// Arguments[I] and Arguments[X], but our algorithm will produce + /// extremely similar, and equally correct, results either way) for (unsigned I = 0, E = Arguments.size(); I != E; ++I) { auto &MainVal = Arguments[I]; auto &MainInfo = Parameters[I]; @@ -406,11 +404,10 @@ public: void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); } - // 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. + /// 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; @@ -464,16 +461,16 @@ public: } }; -// For a given instruction, we need to know which Value* to get the -// users of in order to build our graph. In some cases (i.e. add), -// we simply need the Instruction*. In other cases (i.e. store), -// finding the users of the Instruction* is useless; we need to find -// the users of the first operand. This handles determining which -// value to follow for us. -// -// Note: we *need* to keep this in sync with GetEdgesVisitor. Add -// something to GetEdgesVisitor, add it here -- remove something from -// GetEdgesVisitor, remove it here. +/// For a given instruction, we need to know which Value* to get the +/// users of in order to build our graph. In some cases (i.e. add), +/// we simply need the Instruction*. In other cases (i.e. store), +/// finding the users of the Instruction* is useless; we need to find +/// the users of the first operand. This handles determining which +/// value to follow for us. +/// +/// Note: we *need* to keep this in sync with GetEdgesVisitor. Add +/// something to GetEdgesVisitor, add it here -- remove something from +/// GetEdgesVisitor, remove it here. class GetTargetValueVisitor : public InstVisitor<GetTargetValueVisitor, Value *> { public: @@ -498,7 +495,7 @@ public: } }; -// Set building requires a weighted bidirectional graph. +/// Set building requires a weighted bidirectional graph. template <typename EdgeTypeT> class WeightedBidirectionalGraph { public: typedef std::size_t Node; @@ -531,12 +528,10 @@ private: NodeImpl &getNode(Node N) { return NodeImpls[N]; } public: - // ----- Various Edge iterators for the graph ----- // - - // \brief Iterator for edges. Because this graph is bidirected, we don't - // allow modification of the edges using this iterator. Additionally, the - // iterator becomes invalid if you add edges to or from the node you're - // getting the edges of. + /// \brief Iterator for edges. Because this graph is bidirected, we don't + /// allow modification of the edges using this iterator. Additionally, the + /// iterator becomes invalid if you add edges to or from the node you're + /// getting the edges of. struct EdgeIterator : public std::iterator<std::forward_iterator_tag, std::tuple<EdgeTypeT, Node *>> { EdgeIterator(const typename std::vector<Edge>::const_iterator &Iter) @@ -573,7 +568,7 @@ public: std::tuple<EdgeTypeT, Node> Store; }; - // Wrapper for EdgeIterator with begin()/end() calls. + /// Wrapper for EdgeIterator with begin()/end() calls. struct EdgeIterable { EdgeIterable(const std::vector<Edge> &Edges) : BeginIter(Edges.begin()), EndIter(Edges.end()) {} @@ -617,16 +612,16 @@ public: ToNode.Edges.push_back(Edge(ReverseWeight, From)); } - EdgeIterable edgesFor(const Node &N) const { + iterator_range<EdgeIterator> edgesFor(const Node &N) const { const auto &Node = getNode(N); - return EdgeIterable(Node.Edges); + return make_range(EdgeIterator(Node.Edges.begin()), + EdgeIterator(Node.Edges.end())); } bool empty() const { return NodeImpls.empty(); } std::size_t size() const { return NodeImpls.size(); } - // \brief Gets an arbitrary node in the graph as a starting point for - // traversal. + /// Gets an arbitrary node in the graph as a starting point for traversal. Node getEntryNode() { assert(inbounds(StartNode)); return StartNode; @@ -641,47 +636,47 @@ typedef DenseMap<Value *, GraphT::Node> NodeMapT; // Function declarations that require types defined in the namespace above //===----------------------------------------------------------------------===// -// Given an argument number, returns the appropriate Attr index to set. -static StratifiedAttr argNumberToAttrIndex(StratifiedAttr); +/// Given an argument number, returns the appropriate Attr index to set. +static StratifiedAttr argNumberToAttrIndex(unsigned ArgNum); -// Given a Value, potentially return which AttrIndex it maps to. +/// Given a Value, potentially return which AttrIndex it maps to. static Optional<StratifiedAttr> valueToAttrIndex(Value *Val); -// Gets the inverse of a given EdgeType. -static EdgeType flipWeight(EdgeType); +/// Gets the inverse of a given EdgeType. +static EdgeType flipWeight(EdgeType Initial); -// Gets edges of the given Instruction*, writing them to the SmallVector*. +/// Gets edges of the given Instruction*, writing them to the SmallVector*. static void argsToEdges(CFLAAResult &, Instruction *, SmallVectorImpl<Edge> &); -// Gets edges of the given ConstantExpr*, writing them to the SmallVector*. +/// Gets edges of the given ConstantExpr*, writing them to the SmallVector*. static void argsToEdges(CFLAAResult &, ConstantExpr *, SmallVectorImpl<Edge> &); -// Gets the "Level" that one should travel in StratifiedSets -// given an EdgeType. +/// Gets the "Level" that one should travel in StratifiedSets +/// given an EdgeType. static Level directionOfEdgeType(EdgeType); -// Builds the graph needed for constructing the StratifiedSets for the -// given function +/// Builds the graph needed for constructing the StratifiedSets for the +/// given function static void buildGraphFrom(CFLAAResult &, Function *, SmallVectorImpl<Value *> &, NodeMapT &, GraphT &); -// Gets the edges of a ConstantExpr as if it was an Instruction. This -// function also acts on any nested ConstantExprs, adding the edges -// of those to the given SmallVector as well. +/// Gets the edges of a ConstantExpr as if it was an Instruction. This function +/// also acts on any nested ConstantExprs, adding the edges of those to the +/// given SmallVector as well. static void constexprToEdges(CFLAAResult &, ConstantExpr &, SmallVectorImpl<Edge> &); -// Given an Instruction, this will add it to the graph, along with any -// Instructions that are potentially only available from said Instruction -// For example, given the following line: -// %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. +/// Given an Instruction, this will add it to the graph, along with any +/// Instructions that are potentially only available from said Instruction +/// For example, given the following line: +/// %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. static void addInstructionToGraph(CFLAAResult &, Instruction &, SmallVectorImpl<Value *> &, NodeMapT &, GraphT &); -// Notes whether it would be pointless to add the given Value to our sets. +/// 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) { @@ -848,7 +843,7 @@ static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst, return; } - const auto addEdgeToGraph = [&Graph, &findOrInsertNode](const Edge &E) { + auto addEdgeToGraph = [&](const Edge &E) { auto To = findOrInsertNode(E.To); auto From = findOrInsertNode(E.From); auto FlippedWeight = flipWeight(E.Weight); @@ -873,13 +868,11 @@ static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst, } } -// Aside: We may remove graph construction entirely, because it doesn't really -// buy us much that we don't already have. I'd like to add interprocedural -// analysis prior to this however, in case that somehow requires the graph -// produced by this for efficient execution static void buildGraphFrom(CFLAAResult &Analysis, Function *Fn, SmallVectorImpl<Value *> &ReturnedValues, NodeMapT &Map, GraphT &Graph) { + // (N.B. We may remove graph construction entirely, because it doesn't really + // buy us much.) for (auto &Bb : Fn->getBasicBlockList()) for (auto &Inst : Bb.getInstList()) addInstructionToGraph(Analysis, Inst, ReturnedValues, Map, Graph); @@ -1003,15 +996,14 @@ void CFLAAResult::scan(Function *Fn) { assert(InsertPair.second && "Trying to scan a function that has already been cached"); - FunctionInfo Info(buildSetsFrom(Fn)); - Cache[Fn] = std::move(Info); + Cache[Fn] = buildSetsFrom(Fn); Handles.push_front(FunctionHandle(Fn, this)); } void CFLAAResult::evict(Function *Fn) { Cache.erase(Fn); } -/// \brief Ensures that the given function is available in the cache. -/// Returns the appropriate entry from the cache. +/// Ensures that the given function is available in the cache, and returns the +/// entry. const Optional<CFLAAResult::FunctionInfo> & CFLAAResult::ensureCached(Function *Fn) { auto Iter = Cache.find(Fn); @@ -1033,8 +1025,8 @@ AliasResult CFLAAResult::query(const MemoryLocation &LocA, auto MaybeFnA = parentFunctionOfValue(ValA); auto MaybeFnB = parentFunctionOfValue(ValB); if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) { - // The only times this is known to happen are when globals + InlineAsm - // are involved + // The only times this is known to happen are when globals + InlineAsm are + // involved DEBUG(dbgs() << "CFLAA: could not extract parent function information.\n"); return MayAlias; } @@ -1067,28 +1059,23 @@ AliasResult CFLAAResult::query(const MemoryLocation &LocA, // Stratified set attributes are used as markets to signify whether a member // of a StratifiedSet (or a member of a set above the current set) has - // interacted with either arguments or globals. "Interacted with" meaning - // its value may be different depending on the value of an argument or - // global. The thought behind this is that, because arguments and globals - // may alias each other, if AttrsA and AttrsB have touched args/globals, - // we must conservatively say that they alias. However, if at least one of - // the sets has no values that could legally be altered by changing the value - // of an argument or global, then we don't have to be as conservative. + // interacted with either arguments or globals. "Interacted with" meaning its + // value may be different depending on the value of an argument or global. The + // thought behind this is that, because arguments and globals may alias each + // other, if AttrsA and AttrsB have touched args/globals, we must + // conservatively say that they alias. However, if at least one of the sets + // has no values that could legally be altered by changing the value of an + // argument or global, then we don't have to be as conservative. if (AttrsA.any() && AttrsB.any()) return MayAlias; // We currently unify things even if the accesses to them may not be in - // bounds, so we can't return partial alias here because we don't - // know whether the pointer is really within the object or not. - // IE Given an out of bounds GEP and an alloca'd pointer, we may - // unify the two. We can't return partial alias for this case. - // Since we do not currently track enough information to - // differentiate - - if (SetA.Index == SetB.Index) - return MayAlias; - - return NoAlias; + // bounds, so we can't return partial alias here because we don't know whether + // the pointer is really within the object or not. + // e.g. Given an out of bounds GEP and an alloca'd pointer, we may unify the + // two. We can't return partial alias for this case. Since we do not currently + // track enough information to differentiate. + return SetA.Index == SetB.Index ? MayAlias : NoAlias; } char CFLAA::PassID; diff --git a/llvm/lib/Analysis/StratifiedSets.h b/llvm/lib/Analysis/StratifiedSets.h index fd3fbc0d86a..54af04d0ca0 100644 --- a/llvm/lib/Analysis/StratifiedSets.h +++ b/llvm/lib/Analysis/StratifiedSets.h @@ -25,44 +25,45 @@ #include <vector> namespace llvm { -// \brief An index into Stratified Sets. +/// An index into Stratified Sets. typedef unsigned StratifiedIndex; -// NOTE: ^ This can't be a short -- bootstrapping clang has a case where -// ~1M sets exist. +/// 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 attributes on to this struct. + /// 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). +/// 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. +/// 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; -// \brief A "link" between two StratifiedSets. +/// 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. + /// \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; - // \brief The index for the set "above" current + /// The index for the set "above" current StratifiedIndex Above; - // \brief The link for the set "below" current + /// The link for the set "below" current StratifiedIndex Below; - // \brief Attributes for these StratifiedSets. + /// Attributes for these StratifiedSets. StratifiedAttrs Attrs; StratifiedLink() : Above(SetSentinel), Below(SetSentinel) {} @@ -74,25 +75,25 @@ struct StratifiedLink { void clearAbove() { Above = SetSentinel; } }; -// \brief These are stratified sets, as described in "Fast algorithms for -// Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M -// R, Yuan H, and Su Z. -- in short, this is meant to represent different sets -// of Value*s. If two Value*s are in the same set, or if both sets have -// overlapping attributes, then the Value*s are said to alias. -// -// Sets may be related by position, meaning that one set may be considered as -// above or below another. In CFL Alias Analysis, this gives us an indication -// of how two variables are related; if the set of variable A is below a set -// containing variable B, then at some point, a variable that has interacted -// with B (or B itself) was either used in order to extract the variable A, or -// was used as storage of variable A. -// -// Sets may also have attributes (as noted above). These attributes are -// generally used for noting whether a variable in the set has interacted with -// a variable whose origins we don't quite know (i.e. globals/arguments), or if -// the variable may have had operations performed on it (modified in a function -// call). All attributes that exist in a set A must exist in all sets marked as -// below set A. +/// \brief These are stratified sets, as described in "Fast algorithms for +/// Dyck-CFL-reachability with applications to Alias Analysis" by Zhang Q, Lyu M +/// R, Yuan H, and Su Z. -- in short, this is meant to represent different sets +/// of Value*s. If two Value*s are in the same set, or if both sets have +/// overlapping attributes, then the Value*s are said to alias. +/// +/// Sets may be related by position, meaning that one set may be considered as +/// above or below another. In CFL Alias Analysis, this gives us an indication +/// of how two variables are related; if the set of variable A is below a set +/// containing variable B, then at some point, a variable that has interacted +/// with B (or B itself) was either used in order to extract the variable A, or +/// was used as storage of variable A. +/// +/// Sets may also have attributes (as noted above). These attributes are +/// generally used for noting whether a variable in the set has interacted with +/// a variable whose origins we don't quite know (i.e. globals/arguments), or if +/// the variable may have had operations performed on it (modified in a function +/// call). All attributes that exist in a set A must exist in all sets marked as +/// below set A. template <typename T> class StratifiedSets { public: StratifiedSets() {} @@ -111,9 +112,8 @@ public: Optional<StratifiedInfo> find(const T &Elem) const { auto Iter = Values.find(Elem); - if (Iter == Values.end()) { - return NoneType(); - } + if (Iter == Values.end()) + return None; return Iter->second; } @@ -129,91 +129,91 @@ private: bool inbounds(StratifiedIndex Idx) const { return Idx < Links.size(); } }; -// \brief Generic Builder class that produces StratifiedSets instances. -// -// The goal of this builder is to efficiently produce correct StratifiedSets -// instances. To this end, we use a few tricks: -// > Set chains (A method for linking sets together) -// > Set remaps (A method for marking a set as an alias [irony?] of another) -// -// ==== Set chains ==== -// This builder has a notion of some value A being above, below, or with some -// other value B: -// > The `A above B` relationship implies that there is a reference edge going -// from A to B. Namely, it notes that A can store anything in B's set. -// > The `A below B` relationship is the opposite of `A above B`. It implies -// that there's a dereference edge going from A to B. -// > The `A with B` relationship states that there's an assignment edge going -// from A to B, and that A and B should be treated as equals. -// -// As an example, take the following code snippet: -// -// %a = alloca i32, align 4 -// %ap = alloca i32*, align 8 -// %app = alloca i32**, align 8 -// store %a, %ap -// store %ap, %app -// %aw = getelementptr %ap, 0 -// -// Given this, the follow relations exist: -// - %a below %ap & %ap above %a -// - %ap below %app & %app above %ap -// - %aw with %ap & %ap with %aw -// -// These relations produce the following sets: -// [{%a}, {%ap, %aw}, {%app}] -// -// ...Which states that the only MayAlias relationship in the above program is -// between %ap and %aw. -// -// Life gets more complicated when we actually have logic in our programs. So, -// we either must remove this logic from our programs, or make consessions for -// it in our AA algorithms. In this case, we have decided to select the latter -// option. -// -// First complication: Conditionals -// Motivation: -// %ad = alloca int, align 4 -// %a = alloca int*, align 8 -// %b = alloca int*, align 8 -// %bp = alloca int**, align 8 -// %c = call i1 @SomeFunc() -// %k = select %c, %ad, %bp -// store %ad, %a -// store %b, %bp -// -// %k has 'with' edges to both %a and %b, which ordinarily would not be linked -// together. So, we merge the set that contains %a with the set that contains -// %b. We then recursively merge the set above %a with the set above %b, and -// the set below %a with the set below %b, etc. Ultimately, the sets for this +/// Generic Builder class that produces StratifiedSets instances. +/// +/// The goal of this builder is to efficiently produce correct StratifiedSets +/// instances. To this end, we use a few tricks: +/// > Set chains (A method for linking sets together) +/// > Set remaps (A method for marking a set as an alias [irony?] of another) +/// +/// ==== Set chains ==== +/// This builder has a notion of some value A being above, below, or with some +/// other value B: +/// > The `A above B` relationship implies that there is a reference edge +/// going from A to B. Namely, it notes that A can store anything in B's set. +/// > The `A below B` relationship is the opposite of `A above B`. It implies +/// that there's a dereference edge going from A to B. +/// > The `A with B` relationship states that there's an assignment edge going +/// from A to B, and that A and B should be treated as equals. +/// +/// As an example, take the following code snippet: +/// +/// %a = alloca i32, align 4 +/// %ap = alloca i32*, align 8 +/// %app = alloca i32**, align 8 +/// store %a, %ap +/// store %ap, %app +/// %aw = getelementptr %ap, 0 +/// +/// Given this, the follow relations exist: +/// - %a below %ap & %ap above %a +/// - %ap below %app & %app above %ap +/// - %aw with %ap & %ap with %aw +/// +/// These relations produce the following sets: +/// [{%a}, {%ap, %aw}, {%app}] +/// +/// ...Which states that the only MayAlias relationship in the above program is +/// between %ap and %aw. +/// +/// Life gets more complicated when we actually have logic in our programs. So, +/// we either must remove this logic from our programs, or make consessions for +/// it in our AA algorithms. In this case, we have decided to select the latter +/// option. +/// +/// First complication: Conditionals +/// Motivation: +/// %ad = alloca int, align 4 +/// %a = alloca int*, align 8 +/// %b = alloca int*, align 8 +/// %bp = alloca int**, align 8 +/// %c = call i1 @SomeFunc() +/// %k = select %c, %ad, %bp +/// store %ad, %a +/// store %b, %bp +/// +/// %k has 'with' edges to both %a and %b, which ordinarily would not be linked +/// together. So, we merge the set that contains %a with the set that contains +/// %b. We then recursively merge the set above %a with the set above %b, and +/// the set below %a with the set below %b, etc. Ultimately, the sets for this // program would end up like: {%ad}, {%a, %b, %k}, {%bp}, where {%ad} is below -// {%a, %b, %c} is below {%ad}. -// -// Second complication: Arbitrary casts -// Motivation: -// %ip = alloca int*, align 8 -// %ipp = alloca int**, align 8 -// %i = bitcast ipp to int -// store %ip, %ipp -// store %i, %ip -// -// This is impossible to construct with any of the rules above, because a set -// containing both {%i, %ipp} is supposed to exist, the set with %i is supposed -// to be below the set with %ip, and the set with %ip is supposed to be below -// the set with %ipp. Because we don't allow circular relationships like this, -// we merge all concerned sets into one. So, the above code would generate a -// single StratifiedSet: {%ip, %ipp, %i}. -// -// ==== Set remaps ==== -// More of an implementation detail than anything -- when merging sets, we need -// to update the numbers of all of the elements mapped to those sets. Rather -// than doing this at each merge, we note in the BuilderLink structure that a -// remap has occurred, and use this information so we can defer renumbering set -// elements until build time. +/// {%a, %b, %c} is below {%ad}. +/// +/// Second complication: Arbitrary casts +/// Motivation: +/// %ip = alloca int*, align 8 +/// %ipp = alloca int**, align 8 +/// %i = bitcast ipp to int +/// store %ip, %ipp +/// store %i, %ip +/// +/// This is impossible to construct with any of the rules above, because a set +/// containing both {%i, %ipp} is supposed to exist, the set with %i is supposed +/// to be below the set with %ip, and the set with %ip is supposed to be below +/// the set with %ipp. Because we don't allow circular relationships like this, +/// we merge all concerned sets into one. So, the above code would generate a +/// single StratifiedSet: {%ip, %ipp, %i}. +/// +/// ==== Set remaps ==== +/// More of an implementation detail than anything -- when merging sets, we need +/// to update the numbers of all of the elements mapped to those sets. Rather +/// than doing this at each merge, we note in the BuilderLink structure that a +/// remap has occurred, and use this information so we can defer renumbering set +/// elements until build time. template <typename T> class StratifiedSetsBuilder { - // \brief Represents a Stratified Set, with information about the Stratified - // Set above it, the set below it, and whether the current set has been - // remapped to another. + /// \brief Represents a Stratified Set, with information about the Stratified + /// Set above it, the set below it, and whether the current set has been + /// remapped to another. struct BuilderLink { const StratifiedIndex Number; @@ -281,7 +281,7 @@ template <typename T> class StratifiedSetsBuilder { bool isRemapped() const { return Remap != StratifiedLink::SetSentinel; } - // \brief For initial remapping to another set + /// For initial remapping to another set void remapTo(StratifiedIndex Other) { assert(!isRemapped()); Remap = Other; @@ -292,15 +292,15 @@ template <typename T> class StratifiedSetsBuilder { return Remap; } - // \brief Should only be called when we're already remapped. + /// Should only be called when we're already remapped. void updateRemap(StratifiedIndex Other) { assert(isRemapped()); Remap = Other; } - // \brief Prefer the above functions to calling things directly on what's - // returned from this -- they guard against unexpected calls when the - // current BuilderLink is remapped. + /// Prefer the above functions to calling things directly on what's returned + /// from this -- they guard against unexpected calls when the current + /// BuilderLink is remapped. const StratifiedLink &getLink() const { return Link; } private: @@ -308,15 +308,14 @@ template <typename T> class StratifiedSetsBuilder { StratifiedIndex Remap; }; - // \brief This function performs all of the set unioning/value renumbering - // that we've been putting off, and generates a vector<StratifiedLink> that - // may be placed in a StratifiedSets instance. + /// \brief This function performs all of the set unioning/value renumbering + /// that we've been putting off, and generates a vector<StratifiedLink> that + /// may be placed in a StratifiedSets instance. void finalizeSets(std::vector<StratifiedLink> &StratLinks) { DenseMap<StratifiedIndex, StratifiedIndex> Remaps; for (auto &Link : Links) { - if (Link.isRemapped()) { + if (Link.isRemapped()) continue; - } StratifiedIndex Number = StratLinks.size(); Remaps.insert(std::make_pair(Link.Number, Number)); @@ -348,8 +347,8 @@ template <typename T> class StratifiedSetsBuilder { } } - // \brief There's a guarantee in StratifiedLink where all bits set in a - // Link.externals will be set in all Link.externals "below" it. + /// \brief There's a guarantee in StratifiedLink where all bits set in a + /// Link.externals will be set in all Link.externals "below" it. static void propagateAttrs(std::vector<StratifiedLink> &Links) { const auto getHighestParentAbove = [&Links](StratifiedIndex Idx) { const auto *Link = &Links[Idx]; @@ -363,9 +362,8 @@ template <typename T> class StratifiedSetsBuilder { SmallSet<StratifiedIndex, 16> Visited; for (unsigned I = 0, E = Links.size(); I < E; ++I) { auto CurrentIndex = getHighestParentAbove(I); - if (!Visited.insert(CurrentIndex).second) { + if (!Visited.insert(CurrentIndex).second) continue; - } while (Links[CurrentIndex].hasBelow()) { auto &CurrentBits = Links[CurrentIndex].Attrs; @@ -378,8 +376,8 @@ template <typename T> class StratifiedSetsBuilder { } public: - // \brief Builds a StratifiedSet from the information we've been given since - // either construction or the prior build() call. + /// Builds a StratifiedSet from the information we've been given since either + /// construction or the prior build() call. StratifiedSets<T> build() { std::vector<StratifiedLink> StratLinks; finalizeSets(StratLinks); @@ -401,9 +399,9 @@ public: return addAtMerging(Main, NewIndex); } - // \brief Restructures the stratified sets as necessary to make "ToAdd" in a - // set above "Main". There are some cases where this is not possible (see - // above), so we merge them such that ToAdd and Main are in the same set. + /// \brief Restructures the stratified sets as necessary to make "ToAdd" in a + /// set above "Main". There are some cases where this is not possible (see + /// above), so we merge them such that ToAdd and Main are in the same set. bool addAbove(const T &Main, const T &ToAdd) { assert(has(Main)); auto Index = *indexOf(Main); @@ -414,9 +412,9 @@ public: return addAtMerging(ToAdd, Above); } - // \brief Restructures the stratified sets as necessary to make "ToAdd" in a - // set below "Main". There are some cases where this is not possible (see - // above), so we merge them such that ToAdd and Main are in the same set. + /// \brief Restructures the stratified sets as necessary to make "ToAdd" in a + /// set below "Main". There are some cases where this is not possible (see + /// above), so we merge them such that ToAdd and Main are in the same set. bool addBelow(const T &Main, const T &ToAdd) { assert(has(Main)); auto Index = *indexOf(Main); @@ -467,9 +465,9 @@ public: return Attrs[AttrNum]; } - // \brief Gets the attributes that have been applied to the set that Main - // belongs to. It ignores attributes in any sets above the one that Main - // resides in. + /// \brief Gets the attributes that have been applied to the set that Main + /// belongs to. It ignores attributes in any sets above the one that Main + /// resides in. StratifiedAttrs getRawAttributes(const T &Main) { assert(has(Main)); auto *Info = *get(Main); @@ -477,9 +475,9 @@ public: return Link.getAttrs(); } - // \brief Gets an attribute from the attributes that have been applied to the - // set that Main belongs to. It ignores attributes in any sets above the one - // that Main resides in. + /// \brief Gets an attribute from the attributes that have been applied to the + /// set that Main belongs to. It ignores attributes in any sets above the one + /// that Main resides in. bool getRawAttribute(const T &Main, unsigned AttrNum) { assert(AttrNum < StratifiedLink::SetSentinel); auto Attrs = getRawAttributes(Main); @@ -490,8 +488,7 @@ private: DenseMap<T, StratifiedInfo> Values; std::vector<BuilderLink> Links; - // \brief Adds the given element at the given index, merging sets if - // necessary. + /// Adds the given element at the given index, merging sets if necessary. bool addAtMerging(const T &ToAdd, StratifiedIndex Index) { StratifiedInfo Info = {Index}; auto Pair = Values.insert(std::make_pair(ToAdd, Info)); @@ -509,8 +506,8 @@ private: return false; } - // \brief Gets the BuilderLink at the given index, taking set remapping into - // account. + /// Gets the BuilderLink at the given index, taking set remapping into + /// account. BuilderLink &linksAt(StratifiedIndex Index) { auto *Start = &Links[Index]; if (!Start->isRemapped()) @@ -534,8 +531,8 @@ private: return *Current; } - // \brief Merges two sets into one another. Assumes that these sets are not - // already one in the same + /// \brief Merges two sets into one another. Assumes that these sets are not + /// already one in the same. void merge(StratifiedIndex Idx1, StratifiedIndex Idx2) { assert(inbounds(Idx1) && inbounds(Idx2)); assert(&linksAt(Idx1) != &linksAt(Idx2) && @@ -555,8 +552,8 @@ private: mergeDirect(Idx1, Idx2); } - // \brief Merges two sets assuming that the set at `Idx1` is unreachable from - // traversing above or below the set at `Idx2`. + /// \brief Merges two sets assuming that the set at `Idx1` is unreachable from + /// traversing above or below the set at `Idx2`. void mergeDirect(StratifiedIndex Idx1, StratifiedIndex Idx2) { assert(inbounds(Idx1) && inbounds(Idx2)); @@ -602,9 +599,9 @@ private: LinksFrom->remapTo(LinksInto->Number); } - // \brief Checks to see if lowerIndex is at a level lower than upperIndex. - // If so, it will merge lowerIndex with upperIndex (and all of the sets - // between) and return true. Otherwise, it will return false. + /// Checks to see if lowerIndex is at a level lower than upperIndex. If so, it + /// will merge lowerIndex with upperIndex (and all of the sets between) and + /// return true. Otherwise, it will return false. bool tryMergeUpwards(StratifiedIndex LowerIndex, StratifiedIndex UpperIndex) { assert(inbounds(LowerIndex) && inbounds(UpperIndex)); auto *Lower = &linksAt(LowerIndex); @@ -644,21 +641,21 @@ private: Optional<const StratifiedInfo *> get(const T &Val) const { auto Result = Values.find(Val); if (Result == Values.end()) - return NoneType(); + return None; return &Result->second; } Optional<StratifiedInfo *> get(const T &Val) { auto Result = Values.find(Val); if (Result == Values.end()) - return NoneType(); + return None; return &Result->second; } Optional<StratifiedIndex> indexOf(const T &Val) { auto MaybeVal = get(Val); if (!MaybeVal.hasValue()) - return NoneType(); + return None; auto *Info = *MaybeVal; auto &Link = linksAt(Info->Index); return Link.Number; |
