Index: lib/Analysis/AliasAnalysisSummary.h =================================================================== --- lib/Analysis/AliasAnalysisSummary.h +++ lib/Analysis/AliasAnalysisSummary.h @@ -35,6 +35,7 @@ #ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H #define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/CallSite.h" @@ -166,6 +167,25 @@ Optional instantiateExternalAttribute(ExternalAttribute, CallSite); } + +template <> struct DenseMapInfo { + static inline cflaa::InstantiatedValue getEmptyKey() { + return cflaa::InstantiatedValue{DenseMapInfo::getEmptyKey(), + DenseMapInfo::getEmptyKey()}; + } + static inline cflaa::InstantiatedValue getTombstoneKey() { + return cflaa::InstantiatedValue{DenseMapInfo::getTombstoneKey(), + DenseMapInfo::getTombstoneKey()}; + } + static unsigned getHashValue(const cflaa::InstantiatedValue &IV) { + return DenseMapInfo>::getHashValue( + std::make_pair(IV.Val, IV.DerefLevel)); + } + static bool isEqual(const cflaa::InstantiatedValue &LHS, + const cflaa::InstantiatedValue &RHS) { + return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; + } +}; } #endif Index: lib/Analysis/CFLGraph.h =================================================================== --- lib/Analysis/CFLGraph.h +++ lib/Analysis/CFLGraph.h @@ -16,45 +16,30 @@ #define LLVM_ANALYSIS_CFLGRAPH_H #include "AliasAnalysisSummary.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/IR/InstVisitor.h" #include "llvm/IR/Instructions.h" namespace llvm { 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, - - /// 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) - Reference -}; /// \brief The Program Expression Graph (PEG) of CFL analysis /// CFLGraph is auxiliary data structure used by CFL-based alias analysis to /// describe flow-insensitive pointer-related behaviors. Given an LLVM function, /// the main purpose of this graph is to abstract away unrelated facts and /// translate the rest into a form that can be easily digested by CFL analyses. +/// Each Node in the graph is an InstantiatedValue, and each edge represent a +/// pointer assignment between InstantiatedValue. Pointer +/// references/dereferences are not explicitly stored in the graph: we +/// implicitly assume that for each node (X, I) it has a dereference edge to (X, +/// I+1) and a reference edge to (X, I-1). class CFLGraph { - typedef Value *Node; +public: + typedef InstantiatedValue Node; struct Edge { - EdgeType Type; + int64_t Offset; Node Other; }; @@ -65,48 +50,61 @@ AliasAttrs Attr; }; - typedef DenseMap NodeMap; - NodeMap NodeImpls; + class ValueInfo { + private: + std::vector Levels; + + public: + bool addNodeToLevel(unsigned Level) { + auto NumLevels = Levels.size(); + if (NumLevels > Level) + return false; + while (NumLevels <= Level) { + Levels.push_back(NodeInfo{EdgeList(), AliasAttrs()}); + ++NumLevels; + } + return true; + } - // Gets the inverse of a given EdgeType. - static EdgeType flipWeight(EdgeType Initial) { - switch (Initial) { - case EdgeType::Assign: - return EdgeType::Assign; - case EdgeType::Dereference: - return EdgeType::Reference; - case EdgeType::Reference: - return EdgeType::Dereference; + NodeInfo &getNodeInfoAtLevel(unsigned Level) { + assert(Level < Levels.size()); + return Levels[Level]; + } + const NodeInfo &getNodeInfoAtLevel(unsigned Level) const { + assert(Level < Levels.size()); + return Levels[Level]; } - llvm_unreachable("Incomplete coverage of EdgeType enum"); - } + + unsigned getNumLevels() const { return Levels.size(); } + }; + +private: + typedef DenseMap ValueMap; + ValueMap ValueImpls; const NodeInfo *getNode(Node N) const { - auto Itr = NodeImpls.find(N); - if (Itr == NodeImpls.end()) + auto Itr = ValueImpls.find(N.Val); + if (Itr == ValueImpls.end()) return nullptr; - return &Itr->second; + else if (Itr->second.getNumLevels() <= N.DerefLevel) + return nullptr; + return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); } NodeInfo *getNode(Node N) { - auto Itr = NodeImpls.find(N); - if (Itr == NodeImpls.end()) + auto Itr = ValueImpls.find(N.Val); + if (Itr == ValueImpls.end()) + return nullptr; + else if (Itr->second.getNumLevels() <= N.DerefLevel) return nullptr; - return &Itr->second; + return &Itr->second.getNodeInfoAtLevel(N.DerefLevel); } - static Node nodeDeref(const NodeMap::value_type &P) { return P.first; } - typedef std::pointer_to_unary_function - NodeDerefFun; - public: - typedef EdgeList::const_iterator const_edge_iterator; - typedef mapped_iterator - const_node_iterator; + typedef ValueMap::const_iterator const_value_iterator; bool addNode(Node N) { - return NodeImpls - .insert(std::make_pair(N, NodeInfo{EdgeList(), getAttrNone()})) - .second; + assert(N.Val != nullptr); + return ValueImpls[N.Val].addNodeToLevel(N.DerefLevel); } void addAttr(Node N, AliasAttrs Attr) { @@ -115,14 +113,13 @@ Info->Attr |= Attr; } - void addEdge(Node From, Node To, EdgeType Type) { + void addEdge(Node From, Node To, int64_t Offset = 0) { 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}); + FromInfo->Edges.push_back(Edge{Offset, To}); } AliasAttrs attrFor(Node N) const { @@ -131,21 +128,10 @@ return Info->Attr; } - iterator_range edgesFor(Node N) const { - auto *Info = getNode(N); - assert(Info != nullptr); - auto &Edges = Info->Edges; - return make_range(Edges.begin(), Edges.end()); - } - - iterator_range nodes() const { - return make_range( - map_iterator(NodeImpls.begin(), NodeDerefFun(nodeDeref)), - map_iterator(NodeImpls.end(), NodeDerefFun(nodeDeref))); + iterator_range value_mappings() const { + return make_range(ValueImpls.begin(), + ValueImpls.end()); } - - bool empty() const { return NodeImpls.empty(); } - std::size_t size() const { return NodeImpls.size(); } }; ///\brief A builder class used to create CFLGraph instance from a given function @@ -165,10 +151,6 @@ CFLGraph Graph; SmallVector ReturnedValues; - // Auxiliary structures used by the builder - SmallVector InstantiatedRelations; - SmallVector InstantiatedAttrs; - // Helper class /// Gets the edges our graph should have, based on an Instruction* class GetEdgesVisitor : public InstVisitor { @@ -177,8 +159,9 @@ CFLGraph &Graph; SmallVectorImpl &ReturnValues; - SmallVectorImpl &InstantiatedRelations; - SmallVectorImpl &InstantiatedAttrs; + + SmallPtrSet GlobalValues; + SmallPtrSet ConstantExprs; static bool hasUsefulEdges(ConstantExpr *CE) { // ConstantExpr doesn't have terminators, invokes, or fences, so only @@ -203,42 +186,60 @@ return false; } - void addNode(Value *Val) { + void checkGlobalOrCExpr(Value *Val) { assert(Val != nullptr); - if (!Graph.addNode(Val)) - return; - - if (isa(Val)) { - Graph.addAttr(Val, getGlobalOrArgAttrFromValue(*Val)); - // Currently we do not attempt to be smart on globals - InstantiatedAttrs.push_back( - InstantiatedAttr{InstantiatedValue{Val, 1}, getAttrUnknown()}); - } else if (auto CExpr = dyn_cast(Val)) - if (hasUsefulEdges(CExpr)) + if (auto GVal = dyn_cast(Val)) { + if (!GlobalValues.insert(GVal).second) + return; + Graph.addNode(InstantiatedValue{GVal, 0}); + Graph.addAttr(InstantiatedValue{GVal, 0}, + getGlobalOrArgAttrFromValue(*GVal)); + Graph.addNode(InstantiatedValue{GVal, 1}); + Graph.addAttr(InstantiatedValue{GVal, 1}, getAttrUnknown()); + } else if (auto CExpr = dyn_cast(Val)) { + if (hasUsefulEdges(CExpr)) { + if (!ConstantExprs.insert(CExpr).second) + return; visitConstantExpr(CExpr); + } + } } - void addNodeWithAttr(Value *Val, AliasAttrs Attr) { - addNode(Val); - Graph.addAttr(Val, Attr); + void addNode(Value *Val, AliasAttrs Attr = AliasAttrs()) { + checkGlobalOrCExpr(Val); + Graph.addNode(InstantiatedValue{Val, 0}); + Graph.addAttr(InstantiatedValue{Val, 0}, Attr); } - void addEdge(Value *From, Value *To, EdgeType Type) { + void addAssignEdge(Value *From, Value *To, int64_t Offset = 0) { assert(From != nullptr && To != nullptr); if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy()) return; - addNode(From); - if (To != From) - addNode(To); - Graph.addEdge(From, To, Type); + checkGlobalOrCExpr(From); + Graph.addNode(InstantiatedValue{From, 0}); + if (To != From) { + checkGlobalOrCExpr(To); + Graph.addNode(InstantiatedValue{To, 0}); + Graph.addEdge(InstantiatedValue{From, 0}, InstantiatedValue{To, 0}, + Offset); + } + } + + void addDerefEdge(Value *From, Value *To) { + assert(From != nullptr && To != nullptr); + if (!From->getType()->isPointerTy() || !To->getType()->isPointerTy()) + return; + checkGlobalOrCExpr(From); + checkGlobalOrCExpr(To); + Graph.addNode(InstantiatedValue{From, 1}); + Graph.addNode(InstantiatedValue{To, 0}); + Graph.addEdge(InstantiatedValue{From, 1}, InstantiatedValue{To, 0}); } public: GetEdgesVisitor(CFLGraphBuilder &Builder) : AA(Builder.Analysis), TLI(Builder.TLI), Graph(Builder.Graph), - ReturnValues(Builder.ReturnedValues), - InstantiatedRelations(Builder.InstantiatedRelations), - InstantiatedAttrs(Builder.InstantiatedAttrs) {} + ReturnValues(Builder.ReturnedValues) {} void visitInstruction(Instruction &) { llvm_unreachable("Unsupported instruction encountered"); @@ -255,46 +256,46 @@ void visitPtrToIntInst(PtrToIntInst &Inst) { auto *Ptr = Inst.getOperand(0); - addNodeWithAttr(Ptr, getAttrEscaped()); + addNode(Ptr, getAttrEscaped()); } void visitIntToPtrInst(IntToPtrInst &Inst) { auto *Ptr = &Inst; - addNodeWithAttr(Ptr, getAttrUnknown()); + addNode(Ptr, getAttrUnknown()); } void visitCastInst(CastInst &Inst) { auto *Src = Inst.getOperand(0); - addEdge(Src, &Inst, EdgeType::Assign); + addAssignEdge(Src, &Inst); } void visitBinaryOperator(BinaryOperator &Inst) { auto *Op1 = Inst.getOperand(0); auto *Op2 = Inst.getOperand(1); - addEdge(Op1, &Inst, EdgeType::Assign); - addEdge(Op2, &Inst, EdgeType::Assign); + addAssignEdge(Op1, &Inst); + addAssignEdge(Op2, &Inst); } void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getNewValOperand(); - addEdge(Ptr, Val, EdgeType::Dereference); + addDerefEdge(Ptr, Val); } void visitAtomicRMWInst(AtomicRMWInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getValOperand(); - addEdge(Ptr, Val, EdgeType::Dereference); + addDerefEdge(Ptr, Val); } void visitPHINode(PHINode &Inst) { for (Value *Val : Inst.incoming_values()) - addEdge(Val, &Inst, EdgeType::Assign); + addAssignEdge(Val, &Inst); } void visitGetElementPtrInst(GetElementPtrInst &Inst) { auto *Op = Inst.getPointerOperand(); - addEdge(Op, &Inst, EdgeType::Assign); + addAssignEdge(Op, &Inst); } void visitSelectInst(SelectInst &Inst) { @@ -305,22 +306,22 @@ auto *TrueVal = Inst.getTrueValue(); auto *FalseVal = Inst.getFalseValue(); - addEdge(TrueVal, &Inst, EdgeType::Assign); - addEdge(FalseVal, &Inst, EdgeType::Assign); + addAssignEdge(TrueVal, &Inst); + addAssignEdge(FalseVal, &Inst); } - void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); } + void visitAllocaInst(AllocaInst &Inst) { addNode(&Inst); } void visitLoadInst(LoadInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = &Inst; - addEdge(Val, Ptr, EdgeType::Reference); + addDerefEdge(Ptr, Val); } void visitStoreInst(StoreInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getValueOperand(); - addEdge(Ptr, Val, EdgeType::Dereference); + addDerefEdge(Ptr, Val); } void visitVAArgInst(VAArgInst &Inst) { @@ -332,7 +333,7 @@ // 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, getAttrUnknown()); + addNode(&Inst, getAttrUnknown()); } static bool isFunctionExternal(Function *Fn) { @@ -363,15 +364,20 @@ auto &RetParamRelations = Summary->RetParamRelations; for (auto &Relation : RetParamRelations) { auto IRelation = instantiateExternalRelation(Relation, CS); - if (IRelation.hasValue()) - InstantiatedRelations.push_back(*IRelation); + if (IRelation.hasValue()) { + Graph.addNode(IRelation->From); + Graph.addNode(IRelation->To); + Graph.addEdge(IRelation->From, IRelation->To); + } } auto &RetParamAttributes = Summary->RetParamAttributes; for (auto &Attribute : RetParamAttributes) { auto IAttr = instantiateExternalAttribute(Attribute, CS); - if (IAttr.hasValue()) - InstantiatedAttrs.push_back(*IAttr); + if (IAttr.hasValue()) { + Graph.addNode(IAttr->IValue); + Graph.addAttr(IAttr->IValue, IAttr->Attr); + } } } @@ -383,7 +389,8 @@ // Make sure all arguments and return value are added to the graph first for (Value *V : CS.args()) - addNode(V); + if (V->getType()->isPointerTy()) + addNode(V); if (Inst->getType()->isPointerTy()) addNode(Inst); @@ -413,23 +420,21 @@ for (Value *V : CS.args()) { if (V->getType()->isPointerTy()) { // The argument itself escapes. - addNodeWithAttr(V, getAttrEscaped()); + Graph.addAttr(InstantiatedValue{V, 0}, getAttrEscaped()); // The fate of argument memory is unknown. Note that since - // AliasAttrs - // is transitive with respect to dereference, we only need to - // specify - // it for the first-level memory. - InstantiatedAttrs.push_back( - InstantiatedAttr{InstantiatedValue{V, 1}, getAttrUnknown()}); + // AliasAttrs is transitive with respect to dereference, we only + // need to specify it for the first-level memory. + Graph.addNode(InstantiatedValue{V, 1}); + Graph.addAttr(InstantiatedValue{V, 1}, getAttrUnknown()); } } if (Inst->getType()->isPointerTy()) { auto *Fn = CS.getCalledFunction(); if (Fn == nullptr || !Fn->doesNotAlias(0)) - // No need to call addNodeWithAttr() since we've added Inst at the + // No need to call addNode() since we've added Inst at the // beginning of this function and we know it is not a global. - Graph.addAttr(Inst, getAttrUnknown()); + Graph.addAttr(InstantiatedValue{Inst, 0}, getAttrUnknown()); } } @@ -440,40 +445,40 @@ void visitExtractElementInst(ExtractElementInst &Inst) { auto *Ptr = Inst.getVectorOperand(); auto *Val = &Inst; - addEdge(Val, Ptr, EdgeType::Reference); + addDerefEdge(Ptr, Val); } void visitInsertElementInst(InsertElementInst &Inst) { auto *Vec = Inst.getOperand(0); auto *Val = Inst.getOperand(1); - addEdge(Vec, &Inst, EdgeType::Assign); - addEdge(&Inst, Val, EdgeType::Dereference); + addAssignEdge(Vec, &Inst); + addDerefEdge(&Inst, Val); } 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, getAttrUnknown()); + addNode(&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); + addAssignEdge(Agg, &Inst); + addDerefEdge(&Inst, Val); } void visitExtractValueInst(ExtractValueInst &Inst) { auto *Ptr = Inst.getAggregateOperand(); - addEdge(&Inst, Ptr, EdgeType::Reference); + addDerefEdge(Ptr, &Inst); } void visitShuffleVectorInst(ShuffleVectorInst &Inst) { auto *From1 = Inst.getOperand(0); auto *From2 = Inst.getOperand(1); - addEdge(From1, &Inst, EdgeType::Assign); - addEdge(From2, &Inst, EdgeType::Assign); + addAssignEdge(From1, &Inst); + addAssignEdge(From2, &Inst); } void visitConstantExpr(ConstantExpr *CE) { @@ -504,11 +509,12 @@ void addArgumentToGraph(Argument &Arg) { if (Arg.getType()->isPointerTy()) { - Graph.addNode(&Arg); - Graph.addAttr(&Arg, getGlobalOrArgAttrFromValue(Arg)); + Graph.addNode(InstantiatedValue{&Arg, 0}); + Graph.addAttr(InstantiatedValue{&Arg, 0}, + getGlobalOrArgAttrFromValue(Arg)); // Pointees of a formal parameter is known to the caller - InstantiatedAttrs.push_back( - InstantiatedAttr{InstantiatedValue{&Arg, 1}, getAttrCaller()}); + Graph.addNode(InstantiatedValue{&Arg, 1}); + Graph.addAttr(InstantiatedValue{&Arg, 1}, getAttrCaller()); } } @@ -518,19 +524,21 @@ // %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) { + void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) { if (!hasUsefulEdges(&Inst)) return; - GetEdgesVisitor(*this).visit(Inst); + Visitor.visit(Inst); } // Builds the graph needed for constructing the StratifiedSets for the given // function void buildGraphFrom(Function &Fn) { + GetEdgesVisitor Visitor(*this); + for (auto &Bb : Fn.getBasicBlockList()) for (auto &Inst : Bb.getInstList()) - addInstructionToGraph(Inst); + addInstructionToGraph(Visitor, Inst); for (auto &Arg : Fn.args()) addArgumentToGraph(Arg); @@ -546,12 +554,6 @@ const SmallVector &getReturnValues() const { return ReturnedValues; } - const SmallVector &getInstantiatedRelations() const { - return InstantiatedRelations; - } - const SmallVector &getInstantiatedAttrs() const { - return InstantiatedAttrs; - } }; } } Index: lib/Analysis/CFLSteensAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLSteensAliasAnalysis.cpp +++ lib/Analysis/CFLSteensAliasAnalysis.cpp @@ -67,14 +67,16 @@ /// Information we have about a function and would like to keep around. class CFLSteensAAResult::FunctionInfo { - StratifiedSets Sets; + StratifiedSets Sets; AliasSummary Summary; public: FunctionInfo(Function &Fn, const SmallVectorImpl &RetVals, - StratifiedSets S); + StratifiedSets S); - const StratifiedSets &getStratifiedSets() const { return Sets; } + const StratifiedSets &getStratifiedSets() const { + return Sets; + } const AliasSummary &getAliasSummary() const { return Summary; } }; @@ -84,21 +86,10 @@ const StratifiedIndex StratifiedLink::SetSentinel = std::numeric_limits::max(); -namespace { - -/// StratifiedSets call for knowledge of "direction", so this is how we -/// represent that locally. -enum class Level { Same, Above, Below }; -} - //===----------------------------------------------------------------------===// // Function declarations that require types defined in the namespace above //===----------------------------------------------------------------------===// -/// 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); @@ -113,18 +104,6 @@ return None; } -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; - } - llvm_unreachable("Incomplete switch coverage"); -} - static bool canSkipAddingToSets(Value *Val) { // Constants can share instances, which may falsely unify multiple // sets, e.g. in @@ -148,7 +127,7 @@ CFLSteensAAResult::FunctionInfo::FunctionInfo( Function &Fn, const SmallVectorImpl &RetVals, - StratifiedSets S) + StratifiedSets S) : Sets(std::move(S)) { // Historically, an arbitrary upper-bound of 50 args was selected. We may want // to remove this if it doesn't really matter in practice. @@ -197,7 +176,7 @@ for (auto *RetVal : RetVals) { assert(RetVal != nullptr); assert(RetVal->getType()->isPointerTy()); - auto RetInfo = Sets.find(RetVal); + auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0}); if (RetInfo.hasValue()) AddToRetParamRelations(0, RetInfo->Index); } @@ -206,7 +185,7 @@ unsigned I = 0; for (auto &Param : Fn.args()) { if (Param.getType()->isPointerTy()) { - auto ParamInfo = Sets.find(&Param); + auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0}); if (ParamInfo.hasValue()) AddToRetParamRelations(I + 1, ParamInfo->Index); } @@ -217,62 +196,41 @@ // Builds the graph + StratifiedSets for a function. CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) { CFLGraphBuilder GraphBuilder(*this, TLI, *Fn); - StratifiedSetsBuilder SetBuilder; + StratifiedSetsBuilder SetBuilder; + // Add all CFLGraph nodes and all Dereference edges to StratifiedSets auto &Graph = GraphBuilder.getCFLGraph(); - SmallVector Worklist; - for (auto Node : Graph.nodes()) - Worklist.push_back(Node); - - while (!Worklist.empty()) { - auto *CurValue = Worklist.pop_back_val(); - SetBuilder.add(CurValue); - if (canSkipAddingToSets(CurValue)) + for (const auto &mapping : Graph.value_mappings()) { + auto Val = mapping.first; + if (canSkipAddingToSets(Val)) continue; - - auto Attr = Graph.attrFor(CurValue); - SetBuilder.noteAttributes(CurValue, Attr); - - for (const auto &Edge : Graph.edgesFor(CurValue)) { - auto Label = Edge.Type; - auto *OtherValue = Edge.Other; - - if (canSkipAddingToSets(OtherValue)) - continue; - - bool Added; - switch (directionOfEdgeType(Label)) { - case Level::Above: - Added = SetBuilder.addAbove(CurValue, OtherValue); - break; - case Level::Below: - Added = SetBuilder.addBelow(CurValue, OtherValue); - break; - case Level::Same: - Added = SetBuilder.addWith(CurValue, OtherValue); - break; - } - - if (Added) - Worklist.push_back(OtherValue); + auto &ValueInfo = mapping.second; + + assert(ValueInfo.getNumLevels() > 0); + SetBuilder.add(InstantiatedValue{Val, 0}); + SetBuilder.noteAttributes(InstantiatedValue{Val, 0}, + ValueInfo.getNodeInfoAtLevel(0).Attr); + for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) { + SetBuilder.add(InstantiatedValue{Val, I + 1}); + SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1}, + ValueInfo.getNodeInfoAtLevel(I + 1).Attr); + SetBuilder.addBelow(InstantiatedValue{Val, I}, + InstantiatedValue{Val, I + 1}); } } - // Special handling for interprocedural aliases - 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); - } + // Add all assign edges to StratifiedSets + for (const auto &mapping : Graph.value_mappings()) { + auto Val = mapping.first; + if (canSkipAddingToSets(Val)) + continue; + auto &ValueInfo = mapping.second; - // Special handling for interprocedural attributes - for (auto &IPAttr : GraphBuilder.getInstantiatedAttrs()) { - auto Val = IPAttr.IValue.Val; - SetBuilder.add(Val); - SetBuilder.addAttributesBelow(Val, IPAttr.IValue.DerefLevel, IPAttr.Attr); + for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) { + auto Src = InstantiatedValue{Val, I}; + for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) + SetBuilder.addWith(Src, Edge.Other); + } } return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); @@ -349,11 +307,11 @@ assert(MaybeInfo.hasValue()); auto &Sets = MaybeInfo->getStratifiedSets(); - auto MaybeA = Sets.find(ValA); + auto MaybeA = Sets.find(InstantiatedValue{ValA, 0}); if (!MaybeA.hasValue()) return MayAlias; - auto MaybeB = Sets.find(ValB); + auto MaybeB = Sets.find(InstantiatedValue{ValB, 0}); if (!MaybeB.hasValue()) return MayAlias; Index: lib/Analysis/StratifiedSets.h =================================================================== --- lib/Analysis/StratifiedSets.h +++ lib/Analysis/StratifiedSets.h @@ -386,46 +386,12 @@ return addAtMerging(ToAdd, Below); } - /// \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, 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); - } - Link->setAttrs(Attr); - } - bool addWith(const T &Main, const T &ToAdd) { assert(has(Main)); auto MainIndex = *indexOf(Main); return addAtMerging(ToAdd, MainIndex); } - /// \brief Merge the set "MainBelow"-levels below "Main" and the set - /// "ToAddBelow"-levels below "ToAdd". - void addBelowWith(const T &Main, unsigned MainBelow, const T &ToAdd, - unsigned ToAddBelow) { - assert(has(Main)); - assert(has(ToAdd)); - - auto GetIndexBelow = [&](StratifiedIndex Index, unsigned NumLevel) { - for (unsigned I = 0; I < NumLevel; ++I) { - auto Link = linksAt(Index); - Index = Link.hasBelow() ? Link.getBelow() : addLinkBelow(Index); - } - 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, AliasAttrs NewAttrs) { assert(has(Main)); auto *Info = *get(Main); @@ -545,6 +511,7 @@ NewBelow.setAbove(LinksInto->Number); } + LinksInto->setAttrs(LinksFrom->getAttrs()); LinksFrom->remapTo(LinksInto->Number); }