Index: llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp +++ llvm/trunk/lib/Analysis/CFLAliasAnalysis.cpp @@ -90,6 +90,13 @@ InterfaceValue From, To; }; +/// We use ExternalAttribute to describe an externally visible StratifiedAttrs +/// for parameters/return value. +struct ExternalAttribute { + InterfaceValue IValue; + StratifiedAttrs Attr; +}; + /// Information we have about a function and would like to keep around. class CFLAAResult::FunctionInfo { StratifiedSets Sets; @@ -97,6 +104,9 @@ // RetParamRelations is a collection of ExternalRelations. SmallVector RetParamRelations; + // RetParamAttributes is a collection of ExternalAttributes. + SmallVector RetParamAttributes; + public: FunctionInfo(Function &Fn, const SmallVectorImpl &RetVals, StratifiedSets S); @@ -105,6 +115,9 @@ const SmallVectorImpl &getRetParamRelations() const { return RetParamRelations; } + const SmallVectorImpl &getRetParamAttributes() const { + return RetParamAttributes; + } }; /// Try to go from a Value* to a Function*. Never returns nullptr. @@ -120,19 +133,22 @@ namespace { /// StratifiedInfo Attribute things. -typedef unsigned StratifiedAttr; LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs; LLVM_CONSTEXPR unsigned AttrEscapedIndex = 0; LLVM_CONSTEXPR unsigned AttrUnknownIndex = 1; LLVM_CONSTEXPR unsigned AttrGlobalIndex = 2; -LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 3; +LLVM_CONSTEXPR unsigned AttrCallerIndex = 3; +LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 4; LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex; LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex; -LLVM_CONSTEXPR StratifiedAttr AttrNone = 0; -LLVM_CONSTEXPR StratifiedAttr AttrEscaped = 1 << AttrEscapedIndex; -LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex; -LLVM_CONSTEXPR StratifiedAttr AttrGlobal = 1 << AttrGlobalIndex; +LLVM_CONSTEXPR StratifiedAttrs AttrNone = 0; +LLVM_CONSTEXPR StratifiedAttrs AttrEscaped = 1 << AttrEscapedIndex; +LLVM_CONSTEXPR StratifiedAttrs AttrUnknown = 1 << AttrUnknownIndex; +LLVM_CONSTEXPR StratifiedAttrs AttrGlobal = 1 << AttrGlobalIndex; +LLVM_CONSTEXPR StratifiedAttrs AttrCaller = 1 << AttrCallerIndex; +LLVM_CONSTEXPR StratifiedAttrs ExternalAttrMask = + (1 << AttrEscapedIndex) | (1 << AttrUnknownIndex) | (1 << AttrGlobalIndex); /// The maximum number of arguments we can put into a summary. LLVM_CONSTEXPR unsigned MaxSupportedArgsInSummary = 50; @@ -261,14 +277,21 @@ std::size_t size() const { return NodeImpls.size(); } }; +// This is the result of instantiating InterfaceValue at a particular callsite +struct InterprocNode { + Value *Val; + unsigned DerefLevel; +}; + // Interprocedural assignment edges that CFLGraph may not easily model struct InterprocEdge { - struct Node { - Value *Val; - unsigned DerefLevel; - }; + InterprocNode From, To; +}; - Node From, To; +// Interprocedural attribute tagging that CFLGraph may not easily model +struct InterprocAttr { + InterprocNode Node; + StratifiedAttrs Attr; }; /// Gets the edges our graph should have, based on an Instruction* @@ -277,9 +300,11 @@ const TargetLibraryInfo &TLI; CFLGraph &Graph; + SmallVectorImpl &ReturnValues; SmallPtrSetImpl &Externals; SmallPtrSetImpl &Escapes; SmallVectorImpl &InterprocEdges; + SmallVectorImpl &InterprocAttrs; static bool hasUsefulEdges(ConstantExpr *CE) { // ConstantExpr doesn't have terminators, invokes, or fences, so only needs @@ -315,16 +340,28 @@ public: GetEdgesVisitor(CFLAAResult &AA, const TargetLibraryInfo &TLI, - CFLGraph &Graph, SmallPtrSetImpl &Externals, + CFLGraph &Graph, SmallVectorImpl &ReturnValues, + SmallPtrSetImpl &Externals, SmallPtrSetImpl &Escapes, - SmallVectorImpl &InterprocEdges) - : AA(AA), TLI(TLI), Graph(Graph), Externals(Externals), Escapes(Escapes), - InterprocEdges(InterprocEdges) {} + SmallVectorImpl &InterprocEdges, + SmallVectorImpl &InterprocAttrs) + : AA(AA), TLI(TLI), Graph(Graph), ReturnValues(ReturnValues), + Externals(Externals), Escapes(Escapes), InterprocEdges(InterprocEdges), + InterprocAttrs(InterprocAttrs) {} void visitInstruction(Instruction &) { llvm_unreachable("Unsupported instruction encountered"); } + void visitReturnInst(ReturnInst &Inst) { + if (auto RetVal = Inst.getReturnValue()) { + if (RetVal->getType()->isPointerTy()) { + addNode(RetVal); + ReturnValues.push_back(RetVal); + } + } + } + void visitPtrToIntInst(PtrToIntInst &Inst) { auto *Ptr = Inst.getOperand(0); addNodeWithAttr(Ptr, AttrEscaped); @@ -427,25 +464,34 @@ return false; } + auto InstantiateInterfaceIndex = [&CS](unsigned Index) { + auto Value = + (Index == 0) ? CS.getInstruction() : CS.getArgument(Index - 1); + return Value->getType()->isPointerTy() ? Value : nullptr; + }; + for (auto *Fn : Fns) { auto &FnInfo = AA.ensureCached(Fn); assert(FnInfo.hasValue()); auto &RetParamRelations = FnInfo->getRetParamRelations(); for (auto &Relation : RetParamRelations) { - auto FromIndex = Relation.From.Index; - auto ToIndex = Relation.To.Index; - auto FromVal = (FromIndex == 0) ? CS.getInstruction() - : CS.getArgument(FromIndex - 1); - auto ToVal = - (ToIndex == 0) ? CS.getInstruction() : CS.getArgument(ToIndex - 1); - if (FromVal->getType()->isPointerTy() && - ToVal->getType()->isPointerTy()) { + auto FromVal = InstantiateInterfaceIndex(Relation.From.Index); + auto ToVal = InstantiateInterfaceIndex(Relation.To.Index); + if (FromVal && ToVal) { auto FromLevel = Relation.From.DerefLevel; auto ToLevel = Relation.To.DerefLevel; InterprocEdges.push_back( - InterprocEdge{InterprocEdge::Node{FromVal, FromLevel}, - InterprocEdge::Node{ToVal, ToLevel}}); + InterprocEdge{InterprocNode{FromVal, FromLevel}, + InterprocNode{ToVal, ToLevel}}); + } + } + + auto &RetParamAttributes = FnInfo->getRetParamAttributes(); + for (auto &Attribute : RetParamAttributes) { + if (auto Val = InstantiateInterfaceIndex(Attribute.IValue.Index)) { + InterprocAttrs.push_back(InterprocAttr{ + InterprocNode{Val, Attribute.IValue.DerefLevel}, Attribute.Attr}); } } } @@ -564,16 +610,18 @@ SmallPtrSet ExternalValues; SmallPtrSet EscapedValues; SmallVector InterprocEdges; + SmallVector InterprocAttrs; // Helper functions // Determines whether or not we an instruction is useless to us (e.g. // FenceInst) static bool hasUsefulEdges(Instruction *Inst) { - bool IsNonInvokeTerminator = - isa(Inst) && !isa(Inst); + bool IsNonInvokeRetTerminator = isa(Inst) && + !isa(Inst) && + !isa(Inst); return !isa(Inst) && !isa(Inst) && - !IsNonInvokeTerminator; + !IsNonInvokeRetTerminator; } void addArgumentToGraph(Argument &Arg) { @@ -590,18 +638,11 @@ // addInstructionToGraph would add both the `load` and `getelementptr` // instructions to the graph appropriately. void addInstructionToGraph(Instruction &Inst) { - // We don't want the edges of most "return" instructions, but we *do* want - // to know what can be returned. - if (auto RetInst = dyn_cast(&Inst)) - if (auto RetVal = RetInst->getReturnValue()) - if (RetVal->getType()->isPointerTy()) - ReturnedValues.push_back(RetVal); - if (!hasUsefulEdges(&Inst)) return; - GetEdgesVisitor(Analysis, TLI, Graph, ExternalValues, EscapedValues, - InterprocEdges) + GetEdgesVisitor(Analysis, TLI, Graph, ReturnedValues, ExternalValues, + EscapedValues, InterprocEdges, InterprocAttrs) .visit(Inst); } @@ -636,6 +677,9 @@ const SmallVector &getInterprocEdges() const { return InterprocEdges; } + const SmallVector &getInterprocAttrs() const { + return InterprocAttrs; + } }; } @@ -652,10 +696,10 @@ static bool isUnknownAttr(StratifiedAttrs Attr); /// Given an argument number, returns the appropriate StratifiedAttr to set. -static StratifiedAttr argNumberToAttr(unsigned ArgNum); +static StratifiedAttrs argNumberToAttr(unsigned ArgNum); /// Given a Value, potentially return which StratifiedAttr it maps to. -static Optional valueToAttr(Value *Val); +static Optional valueToAttr(Value *Val); /// Gets the "Level" that one should travel in StratifiedSets /// given an EdgeType. @@ -688,14 +732,17 @@ } static bool isGlobalOrArgAttr(StratifiedAttrs Attr) { - return Attr.reset(AttrEscapedIndex).reset(AttrUnknownIndex).any(); + return Attr.reset(AttrEscapedIndex) + .reset(AttrUnknownIndex) + .reset(AttrCallerIndex) + .any(); } static bool isUnknownAttr(StratifiedAttrs Attr) { - return Attr.test(AttrUnknownIndex); + return Attr.test(AttrUnknownIndex) || Attr.test(AttrCallerIndex); } -static Optional valueToAttr(Value *Val) { +static Optional valueToAttr(Value *Val) { if (isa(Val)) return AttrGlobal; @@ -708,10 +755,10 @@ return None; } -static StratifiedAttr argNumberToAttr(unsigned ArgNum) { +static StratifiedAttrs argNumberToAttr(unsigned ArgNum) { if (ArgNum >= AttrMaxNumArgs) return AttrUnknown; - return 1 << (ArgNum + AttrFirstArgIndex); + return StratifiedAttrs(1 << (ArgNum + AttrFirstArgIndex)); } static Level directionOfEdgeType(EdgeType Weight) { @@ -764,6 +811,7 @@ // in InterfaceMap: if it is not, we add the correspondence to the map; // otherwise, an aliasing relation is found and we add it to // RetParamRelations. + auto AddToRetParamRelations = [&](unsigned InterfaceIndex, StratifiedIndex SetIndex) { unsigned Level = 0; @@ -775,10 +823,15 @@ if (CurrValue != Itr->second) RetParamRelations.push_back(ExternalRelation{CurrValue, Itr->second}); break; - } else - InterfaceMap.insert(std::make_pair(SetIndex, CurrValue)); + } auto &Link = Sets.getLink(SetIndex); + InterfaceMap.insert(std::make_pair(SetIndex, CurrValue)); + auto ExternalAttrs = Link.Attrs & ExternalAttrMask; + if (ExternalAttrs.any()) + RetParamAttributes.push_back( + ExternalAttribute{CurrValue, ExternalAttrs}); + if (!Link.hasBelow()) break; @@ -789,6 +842,8 @@ // Populate RetParamRelations for return values for (auto *RetVal : RetVals) { + assert(RetVal != nullptr); + assert(RetVal->getType()->isPointerTy()); auto RetInfo = Sets.find(RetVal); if (RetInfo.hasValue()) AddToRetParamRelations(0, RetInfo->Index); @@ -856,7 +911,10 @@ auto Attr = valueToAttr(External); if (Attr.hasValue()) { SetBuilder.noteAttributes(External, *Attr); - SetBuilder.addAttributesBelow(External, AttrUnknown); + if (*Attr == AttrGlobal) + SetBuilder.addAttributesBelow(External, 1, AttrUnknown); + else + SetBuilder.addAttributesBelow(External, 1, AttrCaller); } } @@ -870,11 +928,18 @@ Edge.To.DerefLevel); } + // Special handling for interprocedural attributes + for (auto &IPAttr : GraphBuilder.getInterprocAttrs()) { + auto Val = IPAttr.Node.Val; + SetBuilder.add(Val); + SetBuilder.addAttributesBelow(Val, IPAttr.Node.DerefLevel, IPAttr.Attr); + } + // Special handling for opaque external functions for (auto *Escape : GraphBuilder.getEscapedValues()) { SetBuilder.add(Escape); SetBuilder.noteAttributes(Escape, AttrEscaped); - SetBuilder.addAttributesBelow(Escape, AttrUnknown); + SetBuilder.addAttributesBelow(Escape, 1, AttrUnknown); } return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build()); Index: llvm/trunk/lib/Analysis/StratifiedSets.h =================================================================== --- llvm/trunk/lib/Analysis/StratifiedSets.h +++ llvm/trunk/lib/Analysis/StratifiedSets.h @@ -395,15 +395,18 @@ return addAtMerging(ToAdd, Below); } - /// \brief Set the StratifiedAttrs of the set below "Main". If there is no set - /// below "Main", create one for it. - void addAttributesBelow(const T &Main, StratifiedAttrs Attr) { + /// \brief Set the StratifiedAttrs of the set "Level"-levels below "Main". If + /// there is no set below "Main", create one for it. + void addAttributesBelow(const T &Main, unsigned Level, StratifiedAttrs Attr) { assert(has(Main)); auto Index = *indexOf(Main); - auto Link = linksAt(Index); + auto *Link = &linksAt(Index); - auto BelowIndex = Link.hasBelow() ? Link.getBelow() : addLinkBelow(Index); - linksAt(BelowIndex).setAttrs(Attr); + 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) { Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-deref-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-deref-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-deref-escape.ll @@ -0,0 +1,33 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to escape the memory pointed to by its parameters + +; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare void @opaque(i32*) +define void @escape_arg_deref(i32** %arg) { + %arg_deref = load i32*, i32** %arg + call void @opaque(i32* %arg_deref) + ret void +} +; CHECK-LABEL: Function: test_arg_deref_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32** %p, i32** %x +; CHECK: NoAlias: i32* %a, i32** %p +; CHECK: NoAlias: i32* %b, i32** %p +; CHECK: MayAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %c, i32** %p +define void @test_arg_deref_escape(i32** %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %p = alloca i32*, align 4 + + store i32* %a, i32** %p + call void @escape_arg_deref(i32** %p) + %c = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-arg-escape.ll @@ -0,0 +1,31 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to escape its parameters + +; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare void @opaque(i32*) +define void @escape_arg(i32* %arg) { + call void @opaque(i32* %arg) + ret void +} +; CHECK-LABEL: Function: test_arg_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32* %c, i32** %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: MayAlias: i32* %a, i32* %d +; CHECK: MayAlias: i32* %b, i32* %d +; CHECK: NoAlias: i32* %c, i32* %d +define void @test_arg_escape(i32** %x) { + %a = alloca i32, align 4 + %b = alloca i32, align 4 + %c = alloca i32, align 4 + call void @escape_arg(i32* %a) + call void @escape_arg(i32* %b) + %d = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-escape.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-escape.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-escape.ll @@ -0,0 +1,33 @@ +; This testcase ensures that CFL AA answers queries soundly when callee tries +; to return an escaped pointer + +; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s +; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +declare noalias i8* @malloc(i64) +declare void @opaque(i32*) + +define i32* @return_escaped_callee() { + %ptr = call noalias i8* @malloc(i64 8) + %ptr_cast = bitcast i8* %ptr to i32* + call void @opaque(i32* %ptr_cast) + ret i32* %ptr_cast +} +; CHECK-LABEL: Function: test_return_escape +; CHECK: NoAlias: i32* %a, i32** %x +; CHECK: NoAlias: i32* %b, i32** %x +; CHECK: NoAlias: i32* %a, i32* %b +; CHECK: NoAlias: i32* %c, i32** %x +; CHECK: NoAlias: i32* %a, i32* %c +; CHECK: NoAlias: i32* %b, i32* %c +; CHECK: NoAlias: i32* %a, i32* %d +; CHECK: MayAlias: i32* %b, i32* %d +; CHECK: MayAlias: i32* %c, i32* %d +define void @test_return_escape(i32** %x) { + %a = alloca i32, align 4 + %b = call i32* @return_escaped_callee() + %c = call i32* @return_escaped_callee() + %d = load i32*, i32** %x + + ret void +} \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-ret-unknown.ll @@ -4,11 +4,7 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - @g = external global i32 - define i32* @return_unknown_callee(i32* %arg1, i32* %arg2) { ret i32* @g } @@ -24,4 +20,19 @@ %c = call i32* @return_unknown_callee(i32* %a, i32* %b) ret void +} + +@g2 = external global i32* +define i32** @return_unknown_callee2() { + ret i32** @g2 +} +; CHECK-LABEL: Function: test_return_unknown2 +; CHECK: MayAlias: i32* %x, i32** %a +; CHECK: MayAlias: i32* %b, i32* %x +; CHECK: MayAlias: i32* %b, i32** %a +define void @test_return_unknown2(i32* %x) { + %a = call i32** @return_unknown_callee2() + %b = load i32*, i32** %a + + ret void } \ No newline at end of file Index: llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll =================================================================== --- llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll +++ llvm/trunk/test/Analysis/CFLAliasAnalysis/interproc-store-arg-unknown.ll @@ -4,9 +4,6 @@ ; RUN: opt < %s -disable-basicaa -cfl-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s ; RUN: opt < %s -aa-pipeline=cfl-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -; xfail for now due to buggy interproc analysis -; XFAIL: * - @g = external global i32 define void @store_arg_unknown_callee(i32** %arg1) { @@ -20,7 +17,7 @@ ; CHECK: MayAlias: i32* %lp, i32* %x ; CHECK: MayAlias: i32* %a, i32* %lp ; CHECK: NoAlias: i32* %b, i32* %lp -; CHECK: MayAlias: 32* %lp, i32** %p +; CHECK: NoAlias: i32* %lp, i32** %p define void @test_store_arg_unknown(i32* %x) { %a = alloca i32, align 4 %b = alloca i32, align 4