Index: lib/Analysis/CFLAliasAnalysis.cpp =================================================================== --- lib/Analysis/CFLAliasAnalysis.cpp +++ lib/Analysis/CFLAliasAnalysis.cpp @@ -80,15 +80,7 @@ /// 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 -static bool getPossibleTargets(Inst *, SmallVectorImpl &); - -/// 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 getTargetValue(Instruction *); +static bool getPossibleTargets(CallSite, SmallVectorImpl &); const StratifiedIndex StratifiedLink::SetSentinel = std::numeric_limits::max(); @@ -135,36 +127,132 @@ Reference }; -// \brief Encodes the notion of a "use" -struct Edge { - /// Which value the edge is coming from - Value *From; +/// The Program Expression Graph (PEG) of CFL analysis +class CFLGraph { +private: + typedef Value *Node; - /// Which value the edge is pointing to - Value *To; + struct Edge { + StratifiedAttrs Attr; + EdgeType Type; + Node Other; + }; - /// Edge weight - EdgeType Weight; + typedef std::vector EdgeList; + typedef DenseMap NodeMap; + NodeMap NodeImpls; - /// 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; + // 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; + } + llvm_unreachable("Incomplete coverage of EdgeType enum"); + } - Edge(Value *From, Value *To, EdgeType W, StratifiedAttrs A) - : From(From), To(To), Weight(W), AdditionalAttrs(A) {} + const EdgeList *getNode(Node N) const { + auto Itr = NodeImpls.find(N); + if (Itr == NodeImpls.end()) + return nullptr; + return &Itr->second; + } + EdgeList *getNode(Node N) { + auto Itr = NodeImpls.find(N); + if (Itr == NodeImpls.end()) + return nullptr; + return &Itr->second; + } + + 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; + + CFLGraph() = default; + CFLGraph(CFLGraph &&) = default; + CFLGraph &operator=(CFLGraph &&) = default; + + bool addNode(Node N) { + return NodeImpls.insert(std::make_pair(N, EdgeList())).second; + } + + void addEdge(Node From, Node To, EdgeType Type, + StratifiedAttrs Attr = StratifiedAttrs()) { + auto FromEdges = getNode(From); + assert(FromEdges != nullptr); + auto ToEdges = getNode(To); + assert(ToEdges != nullptr); + + FromEdges->push_back(Edge{Attr, Type, To}); + ToEdges->push_back(Edge{Attr, flipWeight(Type), From}); + } + + iterator_range edgesFor(Node N) const { + auto Edges = getNode(N); + assert(Edges != nullptr); + 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))); + } + + bool empty() const { return NodeImpls.empty(); } + std::size_t size() const { return NodeImpls.size(); } }; /// Gets the edges our graph should have, based on an Instruction* class GetEdgesVisitor : public InstVisitor { CFLAAResult &AA; - SmallVectorImpl &Output; const TargetLibraryInfo &TLI; + CFLGraph &Graph; + SmallPtrSetImpl &Externals; + SmallPtrSetImpl &Escapes; + + 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(Val)) + Externals.insert(Val); + else if (auto CExpr = dyn_cast(Val)) { + if (hasUsefulEdges(CExpr)) + visitConstantExpr(CExpr); + } + } + + void addEdge(Value *From, Value *To, EdgeType Type, StratifiedAttrs Attr) { + addNode(From); + if (To != From) + addNode(To); + Graph.addEdge(From, To, Type, Attr); + } + public: - GetEdgesVisitor(CFLAAResult &AA, SmallVectorImpl &Output, - const TargetLibraryInfo &TLI) - : AA(AA), Output(Output), TLI(TLI) {} + GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI, + CFLGraph &Graph, SmallPtrSetImpl &Externals, + SmallPtrSetImpl &Escapes) + : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes) { + } void visitInstruction(Instruction &) { llvm_unreachable("Unsupported instruction encountered"); @@ -172,46 +260,46 @@ void visitPtrToIntInst(PtrToIntInst &Inst) { auto *Ptr = Inst.getOperand(0); - Output.push_back(Edge(Ptr, &Inst, EdgeType::Assign, AttrEscaped)); + addEdge(Ptr, &Inst, EdgeType::Assign, AttrEscaped); } void visitIntToPtrInst(IntToPtrInst &Inst) { auto *Ptr = &Inst; - Output.push_back(Edge(Ptr, Ptr, EdgeType::Assign, AttrUnknown)); + addEdge(Ptr, Ptr, EdgeType::Assign, AttrUnknown); } void visitCastInst(CastInst &Inst) { - Output.push_back( - Edge(&Inst, Inst.getOperand(0), EdgeType::Assign, AttrNone)); + auto *Src = Inst.getOperand(0); + addEdge(Src, &Inst, EdgeType::Assign, AttrNone); } void visitBinaryOperator(BinaryOperator &Inst) { auto *Op1 = Inst.getOperand(0); auto *Op2 = Inst.getOperand(1); - Output.push_back(Edge(&Inst, Op1, EdgeType::Assign, AttrNone)); - Output.push_back(Edge(&Inst, Op2, EdgeType::Assign, AttrNone)); + addEdge(Op1, &Inst, EdgeType::Assign, AttrNone); + addEdge(Op2, &Inst, EdgeType::Assign, AttrNone); } void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getNewValOperand(); - Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone)); + addEdge(Ptr, Val, EdgeType::Dereference, AttrNone); } void visitAtomicRMWInst(AtomicRMWInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getValOperand(); - Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone)); + addEdge(Ptr, Val, EdgeType::Dereference, AttrNone); } void visitPHINode(PHINode &Inst) { for (Value *Val : Inst.incoming_values()) - Output.push_back(Edge(&Inst, Val, EdgeType::Assign, AttrNone)); + addEdge(Val, &Inst, EdgeType::Assign, AttrNone); } void visitGetElementPtrInst(GetElementPtrInst &Inst) { auto *Op = Inst.getPointerOperand(); - Output.push_back(Edge(&Inst, Op, EdgeType::Assign, AttrNone)); + addEdge(Op, &Inst, EdgeType::Assign, AttrNone); } void visitSelectInst(SelectInst &Inst) { @@ -221,23 +309,23 @@ // simply as a result of being the condition of a select. auto *TrueVal = Inst.getTrueValue(); - Output.push_back(Edge(&Inst, TrueVal, EdgeType::Assign, AttrNone)); auto *FalseVal = Inst.getFalseValue(); - Output.push_back(Edge(&Inst, FalseVal, EdgeType::Assign, AttrNone)); + addEdge(TrueVal, &Inst, EdgeType::Assign, AttrNone); + addEdge(FalseVal, &Inst, EdgeType::Assign, AttrNone); } - void visitAllocaInst(AllocaInst &) {} + void visitAllocaInst(AllocaInst &Inst) { Graph.addNode(&Inst); } void visitLoadInst(LoadInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = &Inst; - Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone)); + addEdge(Val, Ptr, EdgeType::Reference, AttrNone); } void visitStoreInst(StoreInst &Inst) { auto *Ptr = Inst.getPointerOperand(); auto *Val = Inst.getValueOperand(); - Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone)); + addEdge(Ptr, Val, EdgeType::Dereference, AttrNone); } void visitVAArgInst(VAArgInst &Inst) { @@ -248,7 +336,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). auto *Val = &Inst; - Output.push_back(Edge(Val, Val, EdgeType::Assign, AttrUnknown)); + addEdge(Val, Val, EdgeType::Assign, AttrUnknown); } static bool isFunctionExternal(Function *Fn) { @@ -280,6 +368,23 @@ return None; } + // Encodes the notion of a "use" + struct Edge { + // Which value the edge is coming from + Value *From; + + // Which value the edge is pointing to + Value *To; + + // Edge weight + EdgeType Weight; + + // 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; + }; + bool tryInterproceduralAnalysis(const SmallVectorImpl &Fns, Value *FuncValue, @@ -302,6 +407,7 @@ return false; } + SmallVector Output; SmallVector Arguments(Args.begin(), Args.end()); SmallVector Parameters; for (auto *Fn : Fns) { @@ -342,7 +448,7 @@ } if (AddEdge) Output.push_back( - Edge(FuncValue, ArgVal, EdgeType::Assign, Externals)); + Edge{FuncValue, ArgVal, EdgeType::Assign, Externals}); } if (Parameters.size() != Arguments.size()) @@ -369,53 +475,57 @@ continue; auto NewAttrs = SubAttrs | MainAttrs; - Output.push_back(Edge(MainVal, SubVal, EdgeType::Assign, NewAttrs)); + Output.push_back(Edge{MainVal, SubVal, EdgeType::Assign, NewAttrs}); } } } + + // Commit all edges in Output to CFLGraph + for (const auto &Edge : Output) + addEdge(Edge.From, Edge.To, Edge.Weight, Edge.AdditionalAttrs); + return true; } - template void visitCallLikeInst(InstT &Inst) { + void visitCallSite(CallSite CS) { + auto Inst = CS.getInstruction(); + + // Make sure all arguments and return value are added to the graph first + for (Value *V : CS.args()) + addNode(V); + if (!Inst->getType()->isVoidTy()) + addNode(Inst); + // Check if Inst is a call to a library function that allocates/deallocates // on the heap. Those kinds of functions do not introduce any aliases. // TODO: address other common library functions such as realloc(), strdup(), // etc. - if (isMallocLikeFn(&Inst, &TLI) || isCallocLikeFn(&Inst, &TLI)) { - Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrNone)); + if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI) || + isFreeCall(Inst, &TLI)) return; - } else if (isFreeCall(&Inst, &TLI)) { - assert(Inst.getNumArgOperands() == 1); - auto argVal = Inst.arg_begin()->get(); - Output.push_back(Edge(argVal, argVal, EdgeType::Assign, AttrNone)); - return; - } // TODO: Add support for noalias args/all the other fun function attributes // that we can tack on. SmallVector Targets; - if (getPossibleTargets(&Inst, Targets)) { - if (tryInterproceduralAnalysis(Targets, &Inst, Inst.arg_operands())) + if (getPossibleTargets(CS, Targets)) + if (tryInterproceduralAnalysis(Targets, Inst, CS.args())) return; - // Cleanup from interprocedural analysis - Output.clear(); - } // Because the function is opaque, we need to note that anything - // could have happened to the arguments, and that the result could alias - // just about anything, too. - // The goal of the loop is in part to unify many Values into one set, so we - // don't care if the function is void there. - for (Value *V : Inst.arg_operands()) - Output.push_back(Edge(&Inst, V, EdgeType::Assign, AttrUnknown)); - if (Inst.getNumArgOperands() == 0 && - Inst.getType() != Type::getVoidTy(Inst.getContext())) - Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrUnknown)); - } - - void visitCallInst(CallInst &Inst) { visitCallLikeInst(Inst); } + // could have happened to the arguments (unless the function is marked + // readonly or readnone), and that the result could alias just about + // anything, too (unless the result is marked noalias). + if (!CS.onlyReadsMemory()) + for (Value *V : CS.args()) { + Escapes.insert(V); + } - void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); } + if (!Inst->getType()->isVoidTy()) { + auto *Fn = CS.getCalledFunction(); + if (Fn == nullptr || !Fn->doesNotAlias(0)) + addEdge(Inst, Inst, EdgeType::Assign, AttrUnknown); + } + } /// Because vectors/aggregates are immutable and unaddressable, there's /// nothing we can do to coax a value out of them, other than calling @@ -424,40 +534,40 @@ void visitExtractElementInst(ExtractElementInst &Inst) { auto *Ptr = Inst.getVectorOperand(); auto *Val = &Inst; - Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone)); + addEdge(Val, Ptr, EdgeType::Reference, AttrNone); } void visitInsertElementInst(InsertElementInst &Inst) { auto *Vec = Inst.getOperand(0); auto *Val = Inst.getOperand(1); - Output.push_back(Edge(&Inst, Vec, EdgeType::Assign, AttrNone)); - Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone)); + addEdge(Vec, &Inst, EdgeType::Assign, AttrNone); + addEdge(&Inst, Val, EdgeType::Dereference, AttrNone); } 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 - Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrUnknown)); + addEdge(&Inst, &Inst, EdgeType::Assign, AttrUnknown); } void visitInsertValueInst(InsertValueInst &Inst) { auto *Agg = Inst.getOperand(0); auto *Val = Inst.getOperand(1); - Output.push_back(Edge(&Inst, Agg, EdgeType::Assign, AttrNone)); - Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone)); + addEdge(Agg, &Inst, EdgeType::Assign, AttrNone); + addEdge(&Inst, Val, EdgeType::Dereference, AttrNone); } void visitExtractValueInst(ExtractValueInst &Inst) { auto *Ptr = Inst.getAggregateOperand(); - Output.push_back(Edge(&Inst, Ptr, EdgeType::Reference, AttrNone)); + addEdge(&Inst, Ptr, EdgeType::Reference, AttrNone); } void visitShuffleVectorInst(ShuffleVectorInst &Inst) { auto *From1 = Inst.getOperand(0); auto *From2 = Inst.getOperand(1); - Output.push_back(Edge(&Inst, From1, EdgeType::Assign, AttrNone)); - Output.push_back(Edge(&Inst, From2, EdgeType::Assign, AttrNone)); + addEdge(From1, &Inst, EdgeType::Assign, AttrNone); + addEdge(From2, &Inst, EdgeType::Assign, AttrNone); } void visitConstantExpr(ConstantExpr *CE) { @@ -474,116 +584,6 @@ } }; -/// 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 { -public: - Value *visitInstruction(Instruction &Inst) { return &Inst; } - - Value *visitStoreInst(StoreInst &Inst) { return Inst.getPointerOperand(); } - - Value *visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { - return Inst.getPointerOperand(); - } - - Value *visitAtomicRMWInst(AtomicRMWInst &Inst) { - return Inst.getPointerOperand(); - } - - Value *visitInsertElementInst(InsertElementInst &Inst) { - return Inst.getOperand(0); - } - - Value *visitInsertValueInst(InsertValueInst &Inst) { - return Inst.getAggregateOperand(); - } -}; - -/// The Program Expression Graph (PEG) of CFL analysis -class CFLGraph { -private: - typedef Value *Node; - - struct Edge { - StratifiedAttrs Attr; - EdgeType Type; - Node Other; - }; - - typedef std::vector EdgeList; - typedef DenseMap NodeMap; - NodeMap NodeImpls; - - // 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; - } - llvm_unreachable("Incomplete coverage of EdgeType enum"); - } - - const EdgeList *getNode(Node N) const { - auto Itr = NodeImpls.find(N); - if (Itr == NodeImpls.end()) - return nullptr; - return &Itr->second; - } - EdgeList &getOrCreateNode(Node N) { return NodeImpls[N]; } - - 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; - - void addNode(Node N) { getOrCreateNode(N); } - - void addEdge(Node From, Node To, EdgeType Type, - StratifiedAttrs Attr = StratifiedAttrs()) { - - // We can't getOrCreateNode() twice in a row here since the second call may - // invalidate the reference returned from the first call - getOrCreateNode(From); - auto &ToEdges = getOrCreateNode(To); - auto &FromEdges = getOrCreateNode(From); - - FromEdges.push_back(Edge{Attr, Type, To}); - ToEdges.push_back(Edge{Attr, flipWeight(Type), From}); - } - - iterator_range edgesFor(Node N) const { - auto Edges = getNode(N); - assert(Edges != nullptr); - 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))); - } - - bool empty() const { return NodeImpls.empty(); } - std::size_t size() const { return NodeImpls.size(); } -}; - class CFLGraphBuilder { // Input of the builder CFLAAResult &Analysis; @@ -594,6 +594,8 @@ SmallVector ReturnedValues; // Auxiliary structures used by the builder + SmallPtrSet ExternalValues; + SmallPtrSet EscapedValues; // Helper functions @@ -606,67 +608,9 @@ !IsNonInvokeTerminator; } - 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; - } - - // Gets edges of the given Instruction*, writing them to the SmallVector*. - void argsToEdges(Instruction *Inst, SmallVectorImpl &Output) { - assert(hasUsefulEdges(Inst) && - "Expected instructions to have 'useful' edges"); - GetEdgesVisitor v(Analysis, Output, TLI); - v.visit(Inst); - } - - // Gets edges of the given ConstantExpr*, writing them to the SmallVector*. - void argsToEdges(ConstantExpr *CE, SmallVectorImpl &Output) { - assert(hasUsefulEdges(CE) && - "Expected constant expr to have 'useful' edges"); - GetEdgesVisitor v(Analysis, Output, TLI); - v.visitConstantExpr(CE); - } - - // 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. - void constexprToEdges(ConstantExpr &CExprToCollapse, - SmallVectorImpl &Results) { - SmallVector Worklist; - Worklist.push_back(&CExprToCollapse); - - SmallVector ConstexprEdges; - SmallPtrSet Visited; - while (!Worklist.empty()) { - auto *CExpr = Worklist.pop_back_val(); - - if (!hasUsefulEdges(CExpr)) - continue; - - ConstexprEdges.clear(); - argsToEdges(CExpr, ConstexprEdges); - for (auto &Edge : ConstexprEdges) { - if (auto *Nested = dyn_cast(Edge.From)) - if (Visited.insert(Nested).second) - Worklist.push_back(Nested); - - if (auto *Nested = dyn_cast(Edge.To)) - if (Visited.insert(Nested).second) - Worklist.push_back(Nested); - } - - Results.append(ConstexprEdges.begin(), ConstexprEdges.end()); - } - } - - // 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()) - addInstructionToGraph(Inst); + void addArgumentToGraph(Argument &Arg) { + Graph.addNode(&Arg); + ExternalValues.insert(&Arg); } // Given an Instruction, this will add it to the graph, along with any @@ -684,37 +628,19 @@ if (!hasUsefulEdges(&Inst)) return; - SmallVector Edges; - argsToEdges(&Inst, Edges); - - // In the case of an unused alloca (or similar), edges may be empty. Note - // that it exists so we can potentially answer NoAlias. - if (Edges.empty()) { - auto MaybeVal = getTargetValue(&Inst); - assert(MaybeVal.hasValue()); - auto *Target = *MaybeVal; - Graph.addNode(Target); - return; - } + GetEdgesVisitor(Analysis, TLI, Graph, ExternalValues, EscapedValues) + .visit(Inst); + } - auto addEdgeToGraph = [this](const Edge &E) { - Graph.addEdge(E.From, E.To, E.Weight, E.AdditionalAttrs); - }; - - SmallVector ConstantExprs; - for (const Edge &E : Edges) { - addEdgeToGraph(E); - if (auto *Constexpr = dyn_cast(E.To)) - ConstantExprs.push_back(Constexpr); - if (auto *Constexpr = dyn_cast(E.From)) - ConstantExprs.push_back(Constexpr); - } + // 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()) + addInstructionToGraph(Inst); - for (ConstantExpr *CE : ConstantExprs) { - Edges.clear(); - constexprToEdges(*CE, Edges); - std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph); - } + for (auto &Arg : Fn.args()) + addArgumentToGraph(Arg); } public: @@ -728,6 +654,8 @@ SmallVector getReturnValues() { return std::move(ReturnedValues); } + const SmallPtrSet &getExternalValues() { return ExternalValues; } + const SmallPtrSet &getEscapedValues() { return EscapedValues; } }; } @@ -767,10 +695,9 @@ return None; } -template -static bool getPossibleTargets(Inst *Call, +static bool getPossibleTargets(CallSite CS, SmallVectorImpl &Output) { - if (auto *Fn = Call->getCalledFunction()) { + if (auto *Fn = CS.getCalledFunction()) { Output.push_back(Fn); return true; } @@ -780,11 +707,6 @@ return false; } -static Optional getTargetValue(Instruction *Inst) { - GetTargetValueVisitor V; - return V.visit(Inst); -} - static bool isGlobalOrArgAttr(StratifiedAttrs Attr) { return Attr.reset(AttrEscapedIndex).reset(AttrUnknownIndex).any(); } @@ -852,7 +774,6 @@ auto &Graph = GraphBuilder.getCFLGraph(); SmallVector Worklist; - SmallPtrSet Globals; for (auto Node : Graph.nodes()) Worklist.push_back(Node); @@ -862,17 +783,12 @@ if (canSkipAddingToSets(CurValue)) continue; - if (isa(CurValue)) - Globals.insert(CurValue); - for (const auto &Edge : Graph.edgesFor(CurValue)) { auto Label = Edge.Type; auto *OtherValue = Edge.Other; if (canSkipAddingToSets(OtherValue)) continue; - if (isa(OtherValue)) - Globals.insert(OtherValue); bool Added; switch (directionOfEdgeType(Label)) { @@ -897,20 +813,20 @@ } // Special handling for globals and arguments - auto ProcessGlobalOrArgValue = [&SetBuilder](Value &Val) { - SetBuilder.add(&Val); - auto Attr = valueToAttr(&Val); + for (auto *External : GraphBuilder.getExternalValues()) { + SetBuilder.add(External); + auto Attr = valueToAttr(External); if (Attr.hasValue()) { - SetBuilder.noteAttributes(&Val, *Attr); - // TODO: do we need to filter out non-pointer values here? - SetBuilder.addAttributesBelow(&Val, AttrUnknown); + SetBuilder.noteAttributes(External, *Attr); + SetBuilder.addAttributesBelow(External, AttrUnknown); } - }; + } - for (auto &Arg : Fn->args()) - ProcessGlobalOrArgValue(Arg); - for (auto *Global : Globals) - ProcessGlobalOrArgValue(*Global); + for (auto *Escape : GraphBuilder.getEscapedValues()) { + SetBuilder.add(Escape); + SetBuilder.noteAttributes(Escape, AttrEscaped); + SetBuilder.addAttributesBelow(Escape, AttrUnknown); + } return FunctionInfo(SetBuilder.build(), GraphBuilder.getReturnValues()); } Index: lib/Analysis/StratifiedSets.h =================================================================== --- lib/Analysis/StratifiedSets.h +++ lib/Analysis/StratifiedSets.h @@ -621,4 +621,4 @@ bool inbounds(StratifiedIndex N) const { return N < Links.size(); } }; } -#endif // LLVM_ADT_STRATIFIEDSETS_H +#endif // LLVM_ADT_STRATIFIEDSETS_H \ No newline at end of file Index: test/Analysis/CFLAliasAnalysis/attr-escape.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/attr-escape.ll +++ test/Analysis/CFLAliasAnalysis/attr-escape.ll @@ -30,3 +30,53 @@ %gload = load i32*, i32** @ext_global ret void } + +declare void @external_func(i32**) +; CHECK-LABEL: Function: test_external_call +; CHECK: NoAlias: i32* %b, i32* %x +; CHECK: NoAlias: i32* %b, i32** %a +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: MayAlias: i32* %c, i32** %a +; CHECK: NoAlias: i32* %b, i32* %c +define void @test_external_call(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + call void @external_func(i32** %a) + %c = load i32*, i32** %a + ret void +} + +declare void @external_func_readonly(i32**) readonly +; CHECK-LABEL: Function: test_external_call_readonly +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %c, i32** %a +define void @test_external_call_readonly(i32* %x) { + %a = alloca i32*, align 8 + %b = alloca i32, align 4 + store i32* %x, i32** %a, align 4 + call void @external_func_readonly(i32** %a) + %c = load i32*, i32** %a + ret void +} + +declare i32* @external_func_normal_return(i32*) +; CHECK-LABEL: Function: test_external_call_normal_return +; CHECK: MayAlias: i32* %c, i32* %x +; CHECK: MayAlias: i32* %a, i32* %c +define void @test_external_call_normal_return(i32* %x) { + %a = alloca i32, align 8 + %b = alloca i32, align 4 + %c = call i32* @external_func_normal_return(i32* %a) + ret void +} + +declare noalias i32* @external_func_noalias_return(i32*) +; CHECK-LABEL: Function: test_external_call_noalias_return +; CHECK: NoAlias: i32* %c, i32* %x +; CHECK: NoAlias: i32* %a, i32* %c +define void @test_external_call_noalias_return(i32* %x) { + %a = alloca i32, align 8 + %b = alloca i32, align 4 + %c = call i32* @external_func_noalias_return(i32* %a) + ret void +} Index: test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll +++ test/Analysis/CFLAliasAnalysis/opaque-call-alias.ll @@ -2,10 +2,10 @@ ; its own stratified set. This would make cases like the one in @test say that ; nothing (except %Escapes and %Arg) can alias -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; CHECK: Function: test -; CHECK: MayAlias: i8* %Arg, i8* %Escapes +; CHECK: NoAlias: i8* %Arg, i8* %Escapes ; CHECK: MayAlias: i8* %Arg, i8* %Retrieved ; CHECK: MayAlias: i8* %Escapes, i8* %Retrieved define void @test(i8* %Arg) { Index: test/Analysis/CFLAliasAnalysis/va.ll =================================================================== --- test/Analysis/CFLAliasAnalysis/va.ll +++ test/Analysis/CFLAliasAnalysis/va.ll @@ -1,16 +1,19 @@ -; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-may-aliases -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; CHECK-LABEL: Function: test1 -; CHECK: 0 no alias responses +; CHECK: MayAlias: i32* %X, i32* %tmp +; CHECK: MayAlias: i32* %tmp, i8** %ap +; CHECK: NoAlias: i8** %ap, i8** %aq +; CHECK: MayAlias: i32* %tmp, i8** %aq -define i32 @test1(i32 %X, ...) { +define i32* @test1(i32* %X, ...) { ; Initialize variable argument processing %ap = alloca i8* %ap2 = bitcast i8** %ap to i8* call void @llvm.va_start(i8* %ap2) - ; Read a single integer argument - %tmp = va_arg i8** %ap, i32 + ; Read a single pointer argument + %tmp = va_arg i8** %ap, i32* ; Demonstrate usage of llvm.va_copy and llvm.va_end %aq = alloca i8* @@ -20,7 +23,7 @@ ; Stop processing of arguments. call void @llvm.va_end(i8* %ap2) - ret i32 %tmp + ret i32* %tmp } declare void @llvm.va_start(i8*)