Index: llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp +++ llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp @@ -27,10 +27,12 @@ #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" +#include "llvm/Support/Debug.h" #include "llvm/Analysis/TargetLibraryInfo.h" using namespace llvm; @@ -42,6 +44,7 @@ STATISTIC(NumReadNoneArg, "Number of arguments marked readnone"); STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly"); STATISTIC(NumNoAlias, "Number of function returns marked noalias"); +STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull"); STATISTIC(NumAnnotated, "Number of attributes added to library functions"); namespace { @@ -67,6 +70,13 @@ // AddNoAliasAttrs - Deduce noalias attributes for the SCC. bool AddNoAliasAttrs(const CallGraphSCC &SCC); + /// \brief Does this function return null? + bool ReturnsNonNull(Function *F, SmallPtrSet &, + bool &Speculative) const; + + /// \brief Deduce nonnull attributes for the SCC. + bool AddNonNullAttrs(const CallGraphSCC &SCC); + // Utility methods used by inferPrototypeAttributes to add attributes // and maintain annotation statistics. @@ -832,6 +842,143 @@ return MadeChange; } +bool FunctionAttrs::ReturnsNonNull(Function *F, + SmallPtrSet &SCCNodes, + bool &Speculative) const { + assert(F->getReturnType()->isPointerTy() && + "nonnull only meaningful on pointer types"); + Speculative = false; + + SmallSetVector FlowsToReturn; + for (BasicBlock &BB : *F) + if (auto *Ret = dyn_cast(BB.getTerminator())) + FlowsToReturn.insert(Ret->getReturnValue()); + + for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { + Value *RetVal = FlowsToReturn[i]; + + // If this value is locally known to be non-null, we're good + if (isKnownNonNull(RetVal, TLI)) + continue; + + // Otherwise, we need to look upwards since we can't make any local + // conclusions. + Instruction *RVI = dyn_cast(RetVal); + if (!RVI) + return false; + switch (RVI->getOpcode()) { + // Extend the analysis by looking upwards. + case Instruction::BitCast: + case Instruction::GetElementPtr: + case Instruction::AddrSpaceCast: + FlowsToReturn.insert(RVI->getOperand(0)); + continue; + case Instruction::Select: { + SelectInst *SI = cast(RVI); + FlowsToReturn.insert(SI->getTrueValue()); + FlowsToReturn.insert(SI->getFalseValue()); + continue; + } + case Instruction::PHI: { + PHINode *PN = cast(RVI); + for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + FlowsToReturn.insert(PN->getIncomingValue(i)); + continue; + } + case Instruction::Call: + case Instruction::Invoke: { + CallSite CS(RVI); + Function *Callee = CS.getCalledFunction(); + // A call to a node within the SCC is assumed to return null until + // proven otherwise + if (Callee && SCCNodes.count(Callee)) { + Speculative = true; + continue; + } + return false; + } + default: + return false; // Unknown source, may be null + }; + llvm_unreachable("should have either continued or returned"); + } + + return true; +} + +bool FunctionAttrs::AddNonNullAttrs(const CallGraphSCC &SCC) { + SmallPtrSet SCCNodes; + + // Fill SCCNodes with the elements of the SCC. Used for quickly + // looking up whether a given CallGraphNode is in this SCC. + for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) + SCCNodes.insert((*I)->getFunction()); + + // Speculative that all functions in the SCC return only nonnull + // pointers. We may refute this as we analyze functions. + bool SCCReturnsNonNull = true; + + bool MadeChange = false; + + // Check each function in turn, determining which functions return nonnull + // pointers. + for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { + Function *F = (*I)->getFunction(); + + if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) + // External node or node we don't want to optimize - skip it; + return false; + + // Already nonnull. + if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, + Attribute::NonNull)) + continue; + + // Definitions with weak linkage may be overridden at linktime, so + // treat them like declarations. + if (F->isDeclaration() || F->mayBeOverridden()) + return false; + + // We annotate nonnull return values, which are only applicable to + // pointer types. + if (!F->getReturnType()->isPointerTy()) + continue; + + bool Speculative = false; + if (ReturnsNonNull(F, SCCNodes, Speculative)) { + if (!Speculative) { + // Mark the function eagerly since we may discover a function + // which prevents us from speculating about the entire SCC + DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n"); + F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull); + ++NumNonNullReturn; + MadeChange = true; + } + continue; + } + // At least one function returns something which could be null, can't + // speculate any more. + SCCReturnsNonNull = false; + } + + if (SCCReturnsNonNull) { + for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { + Function *F = (*I)->getFunction(); + if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, + Attribute::NonNull) || + !F->getReturnType()->isPointerTy()) + continue; + + DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n"); + F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull); + ++NumNonNullReturn; + MadeChange = true; + } + } + + return MadeChange; +} + /// inferPrototypeAttributes - Analyze the name and prototype of the /// given function and set any applicable attributes. Returns true /// if any attributes were set and false otherwise. @@ -1707,5 +1854,6 @@ Changed |= AddReadAttrs(SCC); Changed |= AddArgumentAttrs(SCC); Changed |= AddNoAliasAttrs(SCC); + Changed |= AddNonNullAttrs(SCC); return Changed; } Index: llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll =================================================================== --- llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll +++ llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll @@ -0,0 +1,74 @@ +; RUN: opt -S -functionattrs %s | FileCheck %s +declare nonnull i8* @ret_nonnull() + +; Return a pointer trivially nonnull (call return attribute) +define i8* @test1() { +; CHECK: define nonnull i8* @test1 + %ret = call i8* @ret_nonnull() + ret i8* %ret +} + +; Return a pointer trivially nonnull (argument attribute) +define i8* @test2(i8* nonnull %p) { +; CHECK: define nonnull i8* @test2 + ret i8* %p +} + +; Given an SCC where one of the functions can not be marked nonnull, +; can we still mark the other one which is trivially nonnull +define i8* @scc_binder() { +; CHECK: define i8* @scc_binder + call i8* @test3() + ret i8* null +} + +define i8* @test3() { +; CHECK: define nonnull i8* @test3 + call i8* @scc_binder() + %ret = call i8* @ret_nonnull() + ret i8* %ret +} + +; Given a mutual recursive set of functions, we can mark them +; nonnull if neither can ever return null. (In this case, they +; just never return period.) +define i8* @test4_helper() { +; CHECK: define noalias nonnull i8* @test4_helper + %ret = call i8* @test4() + ret i8* %ret +} + +define i8* @test4() { +; CHECK: define noalias nonnull i8* @test4 + %ret = call i8* @test4_helper() + ret i8* %ret +} + +; Given a mutual recursive set of functions which *can* return null +; make sure we haven't marked them as nonnull. +define i8* @test5_helper() { +; CHECK: define noalias i8* @test5_helper + %ret = call i8* @test5() + ret i8* null +} + +define i8* @test5() { +; CHECK: define noalias i8* @test5 + %ret = call i8* @test5_helper() + ret i8* %ret +} + +; Local analysis, but going through a self recursive phi +define i8* @test6() { +entry: +; CHECK: define nonnull i8* @test6 + %ret = call i8* @ret_nonnull() + br label %loop +loop: + %phi = phi i8* [%ret, %entry], [%phi, %loop] + br i1 undef, label %loop, label %exit +exit: + ret i8* %phi +} + +