[llvm-dev] Function attributes for LibFunc and its impact on GlobalsAA
Vaivaswatha Nagaraj via llvm-dev
llvm-dev at lists.llvm.org
Thu Dec 3 07:20:16 PST 2015
Hi Hal,
>malloc hooks are an interesting point, but those are not standard, not
commonly used
I very much agree with this.
>readonly is a more-interesting question, because, in practice, this will
currently work. It works, however, for the wrong reason
Rather than read-only, could we mark malloc/free etc with
onlyAccessesArgMem()? GlobalsAA would just need a simple check to ignore
such functions (along with read-only which it already is checking for)
during propagation along the call graph. As a reference, I'm attaching a
prototype patch (This patch is on release37 unfortunately, but is
applicable verbatim to the latest svn version).
Thanks,
- Vaivaswatha
On Thu, Dec 3, 2015 at 5:53 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "James Molloy via llvm-dev" <llvm-dev at lists.llvm.org>
> > To: "Vaivaswatha Nagaraj" <vn at compilertree.com>
> > Cc: "LLVM Dev" <llvm-dev at lists.llvm.org>
> > Sent: Thursday, December 3, 2015 4:41:46 AM
> > Subject: Re: [llvm-dev] Function attributes for LibFunc and its impact
> on GlobalsAA
> >
> > Hi,
> >
> > I think that might be difficult to detect. If you wanted to force
> > this behaviour in your own toolchain, you could just use "-mllvm
> > -force-attribute=malloc:readnone" on the clang command line?
>
> This is unlikely to be desirable. A readnone function is one whose output
> is a function only of its inputs, and if you have this:
>
> int *x = malloc(4);
> *x = 2;
> int *y = malloc(4);
> *y = 4;
>
> you certainly don't want EarlyCSE to replace the second call to malloc
> with the result of the first (which it will happily do if you mark malloc
> as readnone).
>
> readonly is a more-interesting question, because, in practice, this will
> currently work. It works, however, for the wrong reason (as I recall, we
> currently don't CSE readonly calls because we need to assume that they
> might have infinite loops, which is a problem we need to otherwise fix).
> Thus, marking it readonly is probably not a good long-term plan.
>
> Given that malloc is an important special case, however, giving it special
> handling is potentially reasonable (we have isMallocLikeFn and
> isOperatorNewLikeFn in MemoryBuiltins.h). One might argue that tagging
> malloc() as readonly might break an LTO build, but doing so already
> potentially has problems because of our aliasing assumptions. malloc hooks
> are an interesting point, but those are not standard, not commonly used,
> can already cause violations of our aliasing assumptions, and the problem
> that hooking libc functions that we assume are readonly in a way that
> changes state visible to the caller might break things is not unique to
> malloc. Users always have the option of turning off these kinds of
> assumptions by compiling with -fno-builtin-malloc.
>
> -Hal
>
> >
> > James
> >
> >
> > On Thu, 3 Dec 2015 at 10:21 Vaivaswatha Nagaraj < vn at compilertree.com
> > > wrote:
> >
> > Hi James,
> >
> > Thank you for the response. I understand the concern about
> > malloc/free hooks. Could we detect that a program has setup malloc
> > hooks (assuming we're in a whole program compilation) and make
> > assumptions (such as onlyAccessesArgMem()) when the program hasn't
> > setup malloc hooks? Using a command line flag could be one option
> > too.
> >
> > I'm currently working on a program where having these attributes
> > could help GlobalsAA give significantly more precise results.
> > Considering that this info is propagated to the caller, its caller
> > and so on, this may have a wider impact than the program I'm
> > currently looking at.
> >
> > Thanks,
> >
> > - Vaivaswatha
> >
> > On Thu, Dec 3, 2015 at 2:57 PM, James Molloy <
> > james at jamesmolloy.co.uk > wrote:
> >
> >
> >
> > Hi Vaivaswatha,
> >
> >
> > I think not adding readnone/readonly to malloc/realloc is correct.
> > malloc/free hooks can be added to most implementations (for leak
> > checking and so on), so calling malloc could in fact call any other
> > arbitrary code that could write to memory.
> >
> >
> > Cheers,
> >
> >
> > James
> >
> >
> >
> >
> > On Wed, 2 Dec 2015 at 14:07 Vaivaswatha Nagaraj via llvm-dev <
> > llvm-dev at lists.llvm.org > wrote:
> >
> >
> >
> >
> >
> >
> > Hi,
> >
> > GlobalsAA, during propagation of mod-ref behavior in the call graph,
> > looks at library functions (in GlobalsAAResult::AnalyzeCallGraph:
> > F->isDeclaration() check), for attributes, and if the function does
> > not have the onlyReadsMemory attribute set, forgets it.
> >
> >
> >
> > I noticed that library functions such as malloc/realloc do not have
> > the attributes doesNotAccessMemory or onlyReadsMemory respectively
> > set (FunctionAttrs.cpp). This leads to a loss of GlobalsAA
> > information in the caller (and its caller and so on). Aren't these
> > attributes stricter than necessary currently? I do not see why the
> > presence of malloc/realloc in a function needs to invalidate all
> > mod-ref info gathered for that function so far.
> >
> >
> >
> > Please let me know if the question is not clear. I'll try to extract
> > out a simple test case from the program I'm looking at and post it,
> > so as to have a concrete example.
> >
> >
> > Thanks,
> >
> >
> >
> >
> >
> >
> > - Vaivaswatha
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20151203/bb985dad/attachment-0001.html>
-------------- next part --------------
diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp
index 28fb49c..ab5b9db 100644
--- a/lib/Analysis/IPA/GlobalsModRef.cpp
+++ b/lib/Analysis/IPA/GlobalsModRef.cpp
@@ -1,609 +1,609 @@
//===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This simple pass provides alias and mod/ref information for global values
// that do not have their address taken, and keeps track of whether functions
// read or write memory (are "pure"). For this simple (but very common) case,
// we can provide pretty accurate and useful information.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/Passes.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include <set>
using namespace llvm;
#define DEBUG_TYPE "globalsmodref-aa"
STATISTIC(NumNonAddrTakenGlobalVars,
"Number of global vars without address taken");
STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");
namespace {
/// FunctionRecord - One instance of this structure is stored for every
/// function in the program. Later, the entries for these functions are
/// removed if the function is found to call an external function (in which
/// case we know nothing about it.
struct FunctionRecord {
/// GlobalInfo - Maintain mod/ref info for all of the globals without
/// addresses taken that are read or written (transitively) by this
/// function.
std::map<const GlobalValue *, unsigned> GlobalInfo;
/// MayReadAnyGlobal - May read global variables, but it is not known which.
bool MayReadAnyGlobal;
unsigned getInfoForGlobal(const GlobalValue *GV) const {
unsigned Effect = MayReadAnyGlobal ? AliasAnalysis::Ref : 0;
std::map<const GlobalValue *, unsigned>::const_iterator I =
GlobalInfo.find(GV);
if (I != GlobalInfo.end())
Effect |= I->second;
return Effect;
}
/// FunctionEffect - Capture whether or not this function reads or writes to
/// ANY memory. If not, we can do a lot of aggressive analysis on it.
unsigned FunctionEffect;
FunctionRecord() : MayReadAnyGlobal(false), FunctionEffect(0) {}
};
/// GlobalsModRef - The actual analysis pass.
class GlobalsModRef : public ModulePass, public AliasAnalysis {
/// NonAddressTakenGlobals - The globals that do not have their addresses
/// taken.
std::set<const GlobalValue *> NonAddressTakenGlobals;
/// IndirectGlobals - The memory pointed to by this global is known to be
/// 'owned' by the global.
std::set<const GlobalValue *> IndirectGlobals;
/// AllocsForIndirectGlobals - If an instruction allocates memory for an
/// indirect global, this map indicates which one.
std::map<const Value *, const GlobalValue *> AllocsForIndirectGlobals;
/// FunctionInfo - For each function, keep track of what globals are
/// modified or read.
std::map<const Function *, FunctionRecord> FunctionInfo;
public:
static char ID;
GlobalsModRef() : ModulePass(ID) {
initializeGlobalsModRefPass(*PassRegistry::getPassRegistry());
}
bool runOnModule(Module &M) override {
InitializeAliasAnalysis(this, &M.getDataLayout());
// Find non-addr taken globals.
AnalyzeGlobals(M);
// Propagate on CG.
AnalyzeCallGraph(getAnalysis<CallGraphWrapperPass>().getCallGraph(), M);
return false;
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AliasAnalysis::getAnalysisUsage(AU);
AU.addRequired<CallGraphWrapperPass>();
AU.setPreservesAll(); // Does not transform code
}
//------------------------------------------------
// Implement the AliasAnalysis API
//
AliasResult alias(const MemoryLocation &LocA,
const MemoryLocation &LocB) override;
ModRefResult getModRefInfo(ImmutableCallSite CS,
const MemoryLocation &Loc) override;
ModRefResult getModRefInfo(ImmutableCallSite CS1,
ImmutableCallSite CS2) override {
return AliasAnalysis::getModRefInfo(CS1, CS2);
}
/// getModRefBehavior - Return the behavior of the specified function if
/// called from the specified call site. The call site may be null in which
/// case the most generic behavior of this function should be returned.
ModRefBehavior getModRefBehavior(const Function *F) override {
ModRefBehavior Min = UnknownModRefBehavior;
if (FunctionRecord *FR = getFunctionInfo(F)) {
if (FR->FunctionEffect == 0)
Min = DoesNotAccessMemory;
else if ((FR->FunctionEffect & Mod) == 0)
Min = OnlyReadsMemory;
}
return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min);
}
/// getModRefBehavior - Return the behavior of the specified function if
/// called from the specified call site. The call site may be null in which
/// case the most generic behavior of this function should be returned.
ModRefBehavior getModRefBehavior(ImmutableCallSite CS) override {
ModRefBehavior Min = UnknownModRefBehavior;
if (const Function *F = CS.getCalledFunction())
if (FunctionRecord *FR = getFunctionInfo(F)) {
if (FR->FunctionEffect == 0)
Min = DoesNotAccessMemory;
else if ((FR->FunctionEffect & Mod) == 0)
Min = OnlyReadsMemory;
}
return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
}
void deleteValue(Value *V) override;
void addEscapingUse(Use &U) override;
/// getAdjustedAnalysisPointer - This method is used when a pass implements
/// an analysis interface through multiple inheritance. If needed, it
/// should override this to adjust the this pointer as needed for the
/// specified pass info.
void *getAdjustedAnalysisPointer(AnalysisID PI) override {
if (PI == &AliasAnalysis::ID)
return (AliasAnalysis *)this;
return this;
}
private:
/// getFunctionInfo - Return the function info for the function, or null if
/// we don't have anything useful to say about it.
FunctionRecord *getFunctionInfo(const Function *F) {
std::map<const Function *, FunctionRecord>::iterator I =
FunctionInfo.find(F);
if (I != FunctionInfo.end())
return &I->second;
return nullptr;
}
void AnalyzeGlobals(Module &M);
void AnalyzeCallGraph(CallGraph &CG, Module &M);
bool AnalyzeUsesOfPointer(Value *V, std::vector<Function *> &Readers,
std::vector<Function *> &Writers,
GlobalValue *OkayStoreDest = nullptr);
bool AnalyzeIndirectGlobalMemory(GlobalValue *GV);
};
}
char GlobalsModRef::ID = 0;
INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
"Simple mod/ref analysis for globals", false, true,
false)
INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
"Simple mod/ref analysis for globals", false, true,
false)
Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); }
/// AnalyzeGlobals - Scan through the users of all of the internal
/// GlobalValue's in the program. If none of them have their "address taken"
/// (really, their address passed to something nontrivial), record this fact,
/// and record the functions that they are used directly in.
void GlobalsModRef::AnalyzeGlobals(Module &M) {
std::vector<Function *> Readers, Writers;
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (I->hasLocalLinkage()) {
if (!AnalyzeUsesOfPointer(I, Readers, Writers)) {
// Remember that we are tracking this global.
NonAddressTakenGlobals.insert(I);
++NumNonAddrTakenFunctions;
}
Readers.clear();
Writers.clear();
}
for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E;
++I)
if (I->hasLocalLinkage()) {
if (!AnalyzeUsesOfPointer(I, Readers, Writers)) {
// Remember that we are tracking this global, and the mod/ref fns
NonAddressTakenGlobals.insert(I);
for (unsigned i = 0, e = Readers.size(); i != e; ++i)
FunctionInfo[Readers[i]].GlobalInfo[I] |= Ref;
if (!I->isConstant()) // No need to keep track of writers to constants
for (unsigned i = 0, e = Writers.size(); i != e; ++i)
FunctionInfo[Writers[i]].GlobalInfo[I] |= Mod;
++NumNonAddrTakenGlobalVars;
// If this global holds a pointer type, see if it is an indirect global.
if (I->getType()->getElementType()->isPointerTy() &&
AnalyzeIndirectGlobalMemory(I))
++NumIndirectGlobalVars;
}
Readers.clear();
Writers.clear();
}
}
/// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
/// If this is used by anything complex (i.e., the address escapes), return
/// true. Also, while we are at it, keep track of those functions that read and
/// write to the value.
///
/// If OkayStoreDest is non-null, stores into this global are allowed.
bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
std::vector<Function *> &Readers,
std::vector<Function *> &Writers,
GlobalValue *OkayStoreDest) {
if (!V->getType()->isPointerTy())
return true;
for (Use &U : V->uses()) {
User *I = U.getUser();
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
Readers.push_back(LI->getParent()->getParent());
} else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
if (V == SI->getOperand(1)) {
Writers.push_back(SI->getParent()->getParent());
} else if (SI->getOperand(1) != OkayStoreDest) {
return true; // Storing the pointer
}
} else if (Operator::getOpcode(I) == Instruction::GetElementPtr) {
if (AnalyzeUsesOfPointer(I, Readers, Writers))
return true;
} else if (Operator::getOpcode(I) == Instruction::BitCast) {
if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest))
return true;
} else if (auto CS = CallSite(I)) {
// Make sure that this is just the function being called, not that it is
// passing into the function.
if (!CS.isCallee(&U)) {
// Detect calls to free.
if (isFreeCall(I, TLI))
Writers.push_back(CS->getParent()->getParent());
else
return true; // Argument of an unknown call.
}
} else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
return true; // Allow comparison against null.
} else {
return true;
}
}
return false;
}
/// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
/// which holds a pointer type. See if the global always points to non-aliased
/// heap memory: that is, all initializers of the globals are allocations, and
/// those allocations have no use other than initialization of the global.
/// Further, all loads out of GV must directly use the memory, not store the
/// pointer somewhere. If this is true, we consider the memory pointed to by
/// GV to be owned by GV and can disambiguate other pointers from it.
bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
// Keep track of values related to the allocation of the memory, f.e. the
// value produced by the malloc call and any casts.
std::vector<Value *> AllocRelatedValues;
// Walk the user list of the global. If we find anything other than a direct
// load or store, bail out.
for (User *U : GV->users()) {
if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
// The pointer loaded from the global can only be used in simple ways:
// we allow addressing of it and loading storing to it. We do *not* allow
// storing the loaded pointer somewhere else or passing to a function.
std::vector<Function *> ReadersWriters;
if (AnalyzeUsesOfPointer(LI, ReadersWriters, ReadersWriters))
return false; // Loaded pointer escapes.
// TODO: Could try some IP mod/ref of the loaded pointer.
} else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
// Storing the global itself.
if (SI->getOperand(0) == GV)
return false;
// If storing the null pointer, ignore it.
if (isa<ConstantPointerNull>(SI->getOperand(0)))
continue;
// Check the value being stored.
Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
GV->getParent()->getDataLayout());
if (!isAllocLikeFn(Ptr, TLI))
return false; // Too hard to analyze.
// Analyze all uses of the allocation. If any of them are used in a
// non-simple way (e.g. stored to another global) bail out.
std::vector<Function *> ReadersWriters;
if (AnalyzeUsesOfPointer(Ptr, ReadersWriters, ReadersWriters, GV))
return false; // Loaded pointer escapes.
// Remember that this allocation is related to the indirect global.
AllocRelatedValues.push_back(Ptr);
} else {
// Something complex, bail out.
return false;
}
}
// Okay, this is an indirect global. Remember all of the allocations for
// this global in AllocsForIndirectGlobals.
while (!AllocRelatedValues.empty()) {
AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
AllocRelatedValues.pop_back();
}
IndirectGlobals.insert(GV);
return true;
}
/// AnalyzeCallGraph - At this point, we know the functions where globals are
/// immediately stored to and read from. Propagate this information up the call
/// graph to all callers and compute the mod/ref info for all memory for each
/// function.
void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
// We do a bottom-up SCC traversal of the call graph. In other words, we
// visit all callees before callers (leaf-first).
for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
const std::vector<CallGraphNode *> &SCC = *I;
assert(!SCC.empty() && "SCC with no functions?");
if (!SCC[0]->getFunction()) {
// Calls externally - can't say anything useful. Remove any existing
// function records (may have been created when scanning globals).
for (unsigned i = 0, e = SCC.size(); i != e; ++i)
FunctionInfo.erase(SCC[i]->getFunction());
continue;
}
FunctionRecord &FR = FunctionInfo[SCC[0]->getFunction()];
bool KnowNothing = false;
unsigned FunctionEffect = 0;
// Collect the mod/ref properties due to called functions. We only compute
// one mod-ref set.
for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
Function *F = SCC[i]->getFunction();
if (!F) {
KnowNothing = true;
break;
}
if (F->isDeclaration()) {
// Try to get mod/ref behaviour from function attributes.
- if (F->doesNotAccessMemory()) {
+ if (F->doesNotAccessMemory() || F->onlyAccessesArgMemory()) {
// Can't do better than that!
} else if (F->onlyReadsMemory()) {
FunctionEffect |= Ref;
if (!F->isIntrinsic())
// This function might call back into the module and read a global -
// consider every global as possibly being read by this function.
FR.MayReadAnyGlobal = true;
} else {
FunctionEffect |= ModRef;
// Can't say anything useful unless it's an intrinsic - they don't
// read or write global variables of the kind considered here.
KnowNothing = !F->isIntrinsic();
}
continue;
}
for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
CI != E && !KnowNothing; ++CI)
if (Function *Callee = CI->second->getFunction()) {
if (FunctionRecord *CalleeFR = getFunctionInfo(Callee)) {
// Propagate function effect up.
FunctionEffect |= CalleeFR->FunctionEffect;
// Incorporate callee's effects on globals into our info.
for (const auto &G : CalleeFR->GlobalInfo)
FR.GlobalInfo[G.first] |= G.second;
FR.MayReadAnyGlobal |= CalleeFR->MayReadAnyGlobal;
} else {
// Can't say anything about it. However, if it is inside our SCC,
// then nothing needs to be done.
CallGraphNode *CalleeNode = CG[Callee];
if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end())
KnowNothing = true;
}
} else {
KnowNothing = true;
}
}
// If we can't say anything useful about this SCC, remove all SCC functions
// from the FunctionInfo map.
if (KnowNothing) {
for (unsigned i = 0, e = SCC.size(); i != e; ++i)
FunctionInfo.erase(SCC[i]->getFunction());
continue;
}
// Scan the function bodies for explicit loads or stores.
for (auto *Node : SCC) {
if (FunctionEffect == ModRef)
break; // The mod/ref lattice saturates here.
for (Instruction &I : inst_range(Node->getFunction())) {
if (FunctionEffect == ModRef)
break; // The mod/ref lattice saturates here.
// We handle calls specially because the graph-relevant aspects are
// handled above.
if (auto CS = CallSite(&I)) {
if (isAllocationFn(&I, TLI) || isFreeCall(&I, TLI)) {
// FIXME: It is completely unclear why this is necessary and not
// handled by the above graph code.
FunctionEffect |= ModRef;
} else if (Function *Callee = CS.getCalledFunction()) {
// The callgraph doesn't include intrinsic calls.
if (Callee->isIntrinsic()) {
ModRefBehavior Behaviour =
AliasAnalysis::getModRefBehavior(Callee);
FunctionEffect |= (Behaviour & ModRef);
}
}
continue;
}
// All non-call instructions we use the primary predicates for whether
// thay read or write memory.
if (I.mayReadFromMemory())
FunctionEffect |= Ref;
if (I.mayWriteToMemory())
FunctionEffect |= Mod;
}
}
if ((FunctionEffect & Mod) == 0)
++NumReadMemFunctions;
if (FunctionEffect == 0)
++NumNoMemFunctions;
FR.FunctionEffect = FunctionEffect;
// Finally, now that we know the full effect on this SCC, clone the
// information to each function in the SCC.
for (unsigned i = 1, e = SCC.size(); i != e; ++i)
FunctionInfo[SCC[i]->getFunction()] = FR;
}
}
/// alias - If one of the pointers is to a global that we are tracking, and the
/// other is some random pointer, we know there cannot be an alias, because the
/// address of the global isn't taken.
AliasResult GlobalsModRef::alias(const MemoryLocation &LocA,
const MemoryLocation &LocB) {
// Get the base object these pointers point to.
const Value *UV1 = GetUnderlyingObject(LocA.Ptr, *DL);
const Value *UV2 = GetUnderlyingObject(LocB.Ptr, *DL);
// If either of the underlying values is a global, they may be non-addr-taken
// globals, which we can answer queries about.
const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
if (GV1 || GV2) {
// If the global's address is taken, pretend we don't know it's a pointer to
// the global.
if (GV1 && !NonAddressTakenGlobals.count(GV1))
GV1 = nullptr;
if (GV2 && !NonAddressTakenGlobals.count(GV2))
GV2 = nullptr;
// If the two pointers are derived from two different non-addr-taken
// globals, or if one is and the other isn't, we know these can't alias.
if ((GV1 || GV2) && GV1 != GV2)
return NoAlias;
// Otherwise if they are both derived from the same addr-taken global, we
// can't know the two accesses don't overlap.
}
// These pointers may be based on the memory owned by an indirect global. If
// so, we may be able to handle this. First check to see if the base pointer
// is a direct load from an indirect global.
GV1 = GV2 = nullptr;
if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
if (IndirectGlobals.count(GV))
GV1 = GV;
if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
if (IndirectGlobals.count(GV))
GV2 = GV;
// These pointers may also be from an allocation for the indirect global. If
// so, also handle them.
if (AllocsForIndirectGlobals.count(UV1))
GV1 = AllocsForIndirectGlobals[UV1];
if (AllocsForIndirectGlobals.count(UV2))
GV2 = AllocsForIndirectGlobals[UV2];
// Now that we know whether the two pointers are related to indirect globals,
// use this to disambiguate the pointers. If either pointer is based on an
// indirect global and if they are not both based on the same indirect global,
// they cannot alias.
if ((GV1 || GV2) && GV1 != GV2)
return NoAlias;
return AliasAnalysis::alias(LocA, LocB);
}
AliasAnalysis::ModRefResult
GlobalsModRef::getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) {
unsigned Known = ModRef;
// If we are asking for mod/ref info of a direct call with a pointer to a
// global we are tracking, return information if we have it.
const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout();
if (const GlobalValue *GV =
dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
if (GV->hasLocalLinkage())
if (const Function *F = CS.getCalledFunction())
if (NonAddressTakenGlobals.count(GV))
if (const FunctionRecord *FR = getFunctionInfo(F))
Known = FR->getInfoForGlobal(GV);
if (Known == NoModRef)
return NoModRef; // No need to query other mod/ref analyses
return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, Loc));
}
//===----------------------------------------------------------------------===//
// Methods to update the analysis as a result of the client transformation.
//
void GlobalsModRef::deleteValue(Value *V) {
if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
if (NonAddressTakenGlobals.erase(GV)) {
// This global might be an indirect global. If so, remove it and remove
// any AllocRelatedValues for it.
if (IndirectGlobals.erase(GV)) {
// Remove any entries in AllocsForIndirectGlobals for this global.
for (std::map<const Value *, const GlobalValue *>::iterator
I = AllocsForIndirectGlobals.begin(),
E = AllocsForIndirectGlobals.end();
I != E;) {
if (I->second == GV) {
AllocsForIndirectGlobals.erase(I++);
} else {
++I;
}
}
}
}
}
// Otherwise, if this is an allocation related to an indirect global, remove
// it.
AllocsForIndirectGlobals.erase(V);
AliasAnalysis::deleteValue(V);
}
void GlobalsModRef::addEscapingUse(Use &U) {
// For the purposes of this analysis, it is conservatively correct to treat
// a newly escaping value equivalently to a deleted one. We could perhaps
// be more precise by processing the new use and attempting to update our
// saved analysis results to accommodate it.
deleteValue(U);
AliasAnalysis::addEscapingUse(U);
}
diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp
index bb5e64a..dd8b2f2 100644
--- a/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -1,1715 +1,1745 @@
//===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a simple interprocedural pass which walks the
// call-graph, looking for functions which do not access or only read
// non-local memory, and marking them readnone/readonly. It does the
// same with function arguments independently, marking them readonly/
// readnone/nocapture. Finally, well-known library call declarations
// are marked with all attributes that are consistent with the
// function's standard definition. This pass is implemented as a
// bottom-up traversal of the call-graph.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/IPO.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/CallGraphSCCPass.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
using namespace llvm;
#define DEBUG_TYPE "functionattrs"
STATISTIC(NumReadNone, "Number of functions marked readnone");
STATISTIC(NumReadOnly, "Number of functions marked readonly");
STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
STATISTIC(NumNoAlias, "Number of function returns marked noalias");
STATISTIC(NumAnnotated, "Number of attributes added to library functions");
namespace {
struct FunctionAttrs : public CallGraphSCCPass {
static char ID; // Pass identification, replacement for typeid
FunctionAttrs() : CallGraphSCCPass(ID), AA(nullptr) {
initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
}
// runOnSCC - Analyze the SCC, performing the transformation if possible.
bool runOnSCC(CallGraphSCC &SCC) override;
// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
bool AddReadAttrs(const CallGraphSCC &SCC);
// AddArgumentAttrs - Deduce nocapture attributes for the SCC.
bool AddArgumentAttrs(const CallGraphSCC &SCC);
// IsFunctionMallocLike - Does this function allocate new memory?
bool IsFunctionMallocLike(Function *F,
SmallPtrSet<Function*, 8> &) const;
// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
bool AddNoAliasAttrs(const CallGraphSCC &SCC);
// Utility methods used by inferPrototypeAttributes to add attributes
// and maintain annotation statistics.
void setDoesNotAccessMemory(Function &F) {
if (!F.doesNotAccessMemory()) {
F.setDoesNotAccessMemory();
++NumAnnotated;
}
}
+ void setOnlyAccessesArgMemory(Function &F) {
+ if (!F.onlyAccessesArgMemory()) {
+ F.setOnlyAccessesArgMemory();
+ ++NumAnnotated;
+ }
+ }
+
void setOnlyReadsMemory(Function &F) {
if (!F.onlyReadsMemory()) {
F.setOnlyReadsMemory();
++NumAnnotated;
}
}
void setDoesNotThrow(Function &F) {
if (!F.doesNotThrow()) {
F.setDoesNotThrow();
++NumAnnotated;
}
}
void setDoesNotCapture(Function &F, unsigned n) {
if (!F.doesNotCapture(n)) {
F.setDoesNotCapture(n);
++NumAnnotated;
}
}
void setOnlyReadsMemory(Function &F, unsigned n) {
if (!F.onlyReadsMemory(n)) {
F.setOnlyReadsMemory(n);
++NumAnnotated;
}
}
void setDoesNotAlias(Function &F, unsigned n) {
if (!F.doesNotAlias(n)) {
F.setDoesNotAlias(n);
++NumAnnotated;
}
}
// 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.
bool inferPrototypeAttributes(Function &F);
// annotateLibraryCalls - Adds attributes to well-known standard library
// call declarations.
bool annotateLibraryCalls(const CallGraphSCC &SCC);
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<AliasAnalysis>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
CallGraphSCCPass::getAnalysisUsage(AU);
}
private:
AliasAnalysis *AA;
TargetLibraryInfo *TLI;
};
}
char FunctionAttrs::ID = 0;
INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
"Deduce function attributes", false, false)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
"Deduce function attributes", false, false)
Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
SmallPtrSet<Function*, 8> 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());
// Check if any of the functions in the SCC read or write memory. If they
// write memory then they can't be marked readnone or readonly.
bool ReadsMemory = false;
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 - assume it may write
// memory and give up.
return false;
AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F);
if (MRB == AliasAnalysis::DoesNotAccessMemory)
// Already perfect!
continue;
// Definitions with weak linkage may be overridden at linktime with
// something that writes memory, so treat them like declarations.
if (F->isDeclaration() || F->mayBeOverridden()) {
if (!AliasAnalysis::onlyReadsMemory(MRB))
// May write memory. Just give up.
return false;
ReadsMemory = true;
continue;
}
// Scan the function body for instructions that may read or write memory.
for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
Instruction *I = &*II;
// Some instructions can be ignored even if they read or write memory.
// Detect these now, skipping to the next instruction if one is found.
CallSite CS(cast<Value>(I));
if (CS) {
// Ignore calls to functions in the same SCC.
if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
continue;
AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS);
// If the call doesn't access arbitrary memory, we may be able to
// figure out something.
if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
// If the call does access argument pointees, check each argument.
if (AliasAnalysis::doesAccessArgPointees(MRB))
// Check whether all pointer arguments point to local memory, and
// ignore calls that only access local memory.
for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
CI != CE; ++CI) {
Value *Arg = *CI;
if (Arg->getType()->isPointerTy()) {
AAMDNodes AAInfo;
I->getAAMetadata(AAInfo);
MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
if (MRB & AliasAnalysis::Mod)
// Writes non-local memory. Give up.
return false;
if (MRB & AliasAnalysis::Ref)
// Ok, it reads non-local memory.
ReadsMemory = true;
}
}
}
continue;
}
// The call could access any memory. If that includes writes, give up.
if (MRB & AliasAnalysis::Mod)
return false;
// If it reads, note it.
if (MRB & AliasAnalysis::Ref)
ReadsMemory = true;
continue;
} else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
// Ignore non-volatile loads from local memory. (Atomic is okay here.)
if (!LI->isVolatile()) {
MemoryLocation Loc = MemoryLocation::get(LI);
if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
continue;
}
} else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
// Ignore non-volatile stores to local memory. (Atomic is okay here.)
if (!SI->isVolatile()) {
MemoryLocation Loc = MemoryLocation::get(SI);
if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
continue;
}
} else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
// Ignore vaargs on local memory.
MemoryLocation Loc = MemoryLocation::get(VI);
if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
continue;
}
// Any remaining instructions need to be taken seriously! Check if they
// read or write memory.
if (I->mayWriteToMemory())
// Writes memory. Just give up.
return false;
// If this instruction may read memory, remember that.
ReadsMemory |= I->mayReadFromMemory();
}
}
// Success! Functions in this SCC do not access memory, or only read memory.
// Give them the appropriate attribute.
bool MadeChange = false;
for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
Function *F = (*I)->getFunction();
if (F->doesNotAccessMemory())
// Already perfect!
continue;
if (F->onlyReadsMemory() && ReadsMemory)
// No change.
continue;
MadeChange = true;
// Clear out any existing attributes.
AttrBuilder B;
B.addAttribute(Attribute::ReadOnly)
.addAttribute(Attribute::ReadNone);
F->removeAttributes(AttributeSet::FunctionIndex,
AttributeSet::get(F->getContext(),
AttributeSet::FunctionIndex, B));
// Add in the new attribute.
F->addAttribute(AttributeSet::FunctionIndex,
ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
if (ReadsMemory)
++NumReadOnly;
else
++NumReadNone;
}
return MadeChange;
}
namespace {
// For a given pointer Argument, this retains a list of Arguments of functions
// in the same SCC that the pointer data flows into. We use this to build an
// SCC of the arguments.
struct ArgumentGraphNode {
Argument *Definition;
SmallVector<ArgumentGraphNode*, 4> Uses;
};
class ArgumentGraph {
// We store pointers to ArgumentGraphNode objects, so it's important that
// that they not move around upon insert.
typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy;
ArgumentMapTy ArgumentMap;
// There is no root node for the argument graph, in fact:
// void f(int *x, int *y) { if (...) f(x, y); }
// is an example where the graph is disconnected. The SCCIterator requires a
// single entry point, so we maintain a fake ("synthetic") root node that
// uses every node. Because the graph is directed and nothing points into
// the root, it will not participate in any SCCs (except for its own).
ArgumentGraphNode SyntheticRoot;
public:
ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator;
iterator begin() { return SyntheticRoot.Uses.begin(); }
iterator end() { return SyntheticRoot.Uses.end(); }
ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
ArgumentGraphNode *operator[](Argument *A) {
ArgumentGraphNode &Node = ArgumentMap[A];
Node.Definition = A;
SyntheticRoot.Uses.push_back(&Node);
return &Node;
}
};
// This tracker checks whether callees are in the SCC, and if so it does not
// consider that a capture, instead adding it to the "Uses" list and
// continuing with the analysis.
struct ArgumentUsesTracker : public CaptureTracker {
ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes)
: Captured(false), SCCNodes(SCCNodes) {}
void tooManyUses() override { Captured = true; }
bool captured(const Use *U) override {
CallSite CS(U->getUser());
if (!CS.getInstruction()) { Captured = true; return true; }
Function *F = CS.getCalledFunction();
if (!F || !SCCNodes.count(F)) { Captured = true; return true; }
bool Found = false;
Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end();
PI != PE; ++PI, ++AI) {
if (AI == AE) {
assert(F->isVarArg() && "More params than args in non-varargs call");
Captured = true;
return true;
}
if (PI == U) {
Uses.push_back(AI);
Found = true;
break;
}
}
assert(Found && "Capturing call-site captured nothing?");
(void)Found;
return false;
}
bool Captured; // True only if certainly captured (used outside our SCC).
SmallVector<Argument*, 4> Uses; // Uses within our SCC.
const SmallPtrSet<Function*, 8> &SCCNodes;
};
}
namespace llvm {
template<> struct GraphTraits<ArgumentGraphNode*> {
typedef ArgumentGraphNode NodeType;
typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType;
static inline NodeType *getEntryNode(NodeType *A) { return A; }
static inline ChildIteratorType child_begin(NodeType *N) {
return N->Uses.begin();
}
static inline ChildIteratorType child_end(NodeType *N) {
return N->Uses.end();
}
};
template<> struct GraphTraits<ArgumentGraph*>
: public GraphTraits<ArgumentGraphNode*> {
static NodeType *getEntryNode(ArgumentGraph *AG) {
return AG->getEntryNode();
}
static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
return AG->begin();
}
static ChildIteratorType nodes_end(ArgumentGraph *AG) {
return AG->end();
}
};
}
// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
static Attribute::AttrKind
determinePointerReadAttrs(Argument *A,
const SmallPtrSet<Argument*, 8> &SCCNodes) {
SmallVector<Use*, 32> Worklist;
SmallSet<Use*, 32> Visited;
int Count = 0;
// inalloca arguments are always clobbered by the call.
if (A->hasInAllocaAttr())
return Attribute::None;
bool IsRead = false;
// We don't need to track IsWritten. If A is written to, return immediately.
for (Use &U : A->uses()) {
if (Count++ >= 20)
return Attribute::None;
Visited.insert(&U);
Worklist.push_back(&U);
}
while (!Worklist.empty()) {
Use *U = Worklist.pop_back_val();
Instruction *I = cast<Instruction>(U->getUser());
Value *V = U->get();
switch (I->getOpcode()) {
case Instruction::BitCast:
case Instruction::GetElementPtr:
case Instruction::PHI:
case Instruction::Select:
case Instruction::AddrSpaceCast:
// The original value is not read/written via this if the new value isn't.
for (Use &UU : I->uses())
if (Visited.insert(&UU).second)
Worklist.push_back(&UU);
break;
case Instruction::Call:
case Instruction::Invoke: {
bool Captures = true;
if (I->getType()->isVoidTy())
Captures = false;
auto AddUsersToWorklistIfCapturing = [&] {
if (Captures)
for (Use &UU : I->uses())
if (Visited.insert(&UU).second)
Worklist.push_back(&UU);
};
CallSite CS(I);
if (CS.doesNotAccessMemory()) {
AddUsersToWorklistIfCapturing();
continue;
}
Function *F = CS.getCalledFunction();
if (!F) {
if (CS.onlyReadsMemory()) {
IsRead = true;
AddUsersToWorklistIfCapturing();
continue;
}
return Attribute::None;
}
Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) {
if (A->get() == V) {
if (AI == AE) {
assert(F->isVarArg() &&
"More params than args in non-varargs call.");
return Attribute::None;
}
Captures &= !CS.doesNotCapture(A - B);
if (SCCNodes.count(AI))
continue;
if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B))
return Attribute::None;
if (!CS.doesNotAccessMemory(A - B))
IsRead = true;
}
}
AddUsersToWorklistIfCapturing();
break;
}
case Instruction::Load:
IsRead = true;
break;
case Instruction::ICmp:
case Instruction::Ret:
break;
default:
return Attribute::None;
}
}
return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
}
/// AddArgumentAttrs - Deduce nocapture attributes for the SCC.
bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
bool Changed = false;
SmallPtrSet<Function*, 8> 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) {
Function *F = (*I)->getFunction();
if (F && !F->isDeclaration() && !F->mayBeOverridden() &&
!F->hasFnAttribute(Attribute::OptimizeNone))
SCCNodes.insert(F);
}
ArgumentGraph AG;
AttrBuilder B;
B.addAttribute(Attribute::NoCapture);
// Check each function in turn, determining which pointer arguments are not
// captured.
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 function we're trying not to optimize - only a problem
// for arguments that we pass to it.
continue;
// Definitions with weak linkage may be overridden at linktime with
// something that captures pointers, so treat them like declarations.
if (F->isDeclaration() || F->mayBeOverridden())
continue;
// Functions that are readonly (or readnone) and nounwind and don't return
// a value can't capture arguments. Don't analyze them.
if (F->onlyReadsMemory() && F->doesNotThrow() &&
F->getReturnType()->isVoidTy()) {
for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
A != E; ++A) {
if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
++NumNoCapture;
Changed = true;
}
}
continue;
}
for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
A != E; ++A) {
if (!A->getType()->isPointerTy()) continue;
bool HasNonLocalUses = false;
if (!A->hasNoCaptureAttr()) {
ArgumentUsesTracker Tracker(SCCNodes);
PointerMayBeCaptured(A, &Tracker);
if (!Tracker.Captured) {
if (Tracker.Uses.empty()) {
// If it's trivially not captured, mark it nocapture now.
A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
++NumNoCapture;
Changed = true;
} else {
// If it's not trivially captured and not trivially not captured,
// then it must be calling into another function in our SCC. Save
// its particulars for Argument-SCC analysis later.
ArgumentGraphNode *Node = AG[A];
for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
UE = Tracker.Uses.end(); UI != UE; ++UI) {
Node->Uses.push_back(AG[*UI]);
if (*UI != A)
HasNonLocalUses = true;
}
}
}
// Otherwise, it's captured. Don't bother doing SCC analysis on it.
}
if (!HasNonLocalUses && !A->onlyReadsMemory()) {
// Can we determine that it's readonly/readnone without doing an SCC?
// Note that we don't allow any calls at all here, or else our result
// will be dependent on the iteration order through the functions in the
// SCC.
SmallPtrSet<Argument*, 8> Self;
Self.insert(A);
Attribute::AttrKind R = determinePointerReadAttrs(A, Self);
if (R != Attribute::None) {
AttrBuilder B;
B.addAttribute(R);
A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
Changed = true;
R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
}
}
}
}
// The graph we've collected is partial because we stopped scanning for
// argument uses once we solved the argument trivially. These partial nodes
// show up as ArgumentGraphNode objects with an empty Uses list, and for
// these nodes the final decision about whether they capture has already been
// made. If the definition doesn't have a 'nocapture' attribute by now, it
// captures.
for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
if (ArgumentSCC.size() == 1) {
if (!ArgumentSCC[0]->Definition) continue; // synthetic root node
// eg. "void f(int* x) { if (...) f(x); }"
if (ArgumentSCC[0]->Uses.size() == 1 &&
ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
Argument *A = ArgumentSCC[0]->Definition;
A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
++NumNoCapture;
Changed = true;
}
continue;
}
bool SCCCaptured = false;
for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
I != E && !SCCCaptured; ++I) {
ArgumentGraphNode *Node = *I;
if (Node->Uses.empty()) {
if (!Node->Definition->hasNoCaptureAttr())
SCCCaptured = true;
}
}
if (SCCCaptured) continue;
SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
// Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
// quickly looking up whether a given Argument is in this ArgumentSCC.
for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) {
ArgumentSCCNodes.insert((*I)->Definition);
}
for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
I != E && !SCCCaptured; ++I) {
ArgumentGraphNode *N = *I;
for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
UE = N->Uses.end(); UI != UE; ++UI) {
Argument *A = (*UI)->Definition;
if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
continue;
SCCCaptured = true;
break;
}
}
if (SCCCaptured) continue;
for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
Argument *A = ArgumentSCC[i]->Definition;
A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
++NumNoCapture;
Changed = true;
}
// We also want to compute readonly/readnone. With a small number of false
// negatives, we can assume that any pointer which is captured isn't going
// to be provably readonly or readnone, since by definition we can't
// analyze all uses of a captured pointer.
//
// The false negatives happen when the pointer is captured by a function
// that promises readonly/readnone behaviour on the pointer, then the
// pointer's lifetime ends before anything that writes to arbitrary memory.
// Also, a readonly/readnone pointer may be returned, but returning a
// pointer is capturing it.
Attribute::AttrKind ReadAttr = Attribute::ReadNone;
for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
Argument *A = ArgumentSCC[i]->Definition;
Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes);
if (K == Attribute::ReadNone)
continue;
if (K == Attribute::ReadOnly) {
ReadAttr = Attribute::ReadOnly;
continue;
}
ReadAttr = K;
break;
}
if (ReadAttr != Attribute::None) {
AttrBuilder B, R;
B.addAttribute(ReadAttr);
R.addAttribute(Attribute::ReadOnly)
.addAttribute(Attribute::ReadNone);
for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
Argument *A = ArgumentSCC[i]->Definition;
// Clear out existing readonly/readnone attributes
A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
Changed = true;
}
}
}
return Changed;
}
/// IsFunctionMallocLike - A function is malloc-like if it returns either null
/// or a pointer that doesn't alias any other pointer visible to the caller.
bool FunctionAttrs::IsFunctionMallocLike(Function *F,
SmallPtrSet<Function*, 8> &SCCNodes) const {
SmallSetVector<Value *, 8> FlowsToReturn;
for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
FlowsToReturn.insert(Ret->getReturnValue());
for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
Value *RetVal = FlowsToReturn[i];
if (Constant *C = dyn_cast<Constant>(RetVal)) {
if (!C->isNullValue() && !isa<UndefValue>(C))
return false;
continue;
}
if (isa<Argument>(RetVal))
return false;
if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
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<SelectInst>(RVI);
FlowsToReturn.insert(SI->getTrueValue());
FlowsToReturn.insert(SI->getFalseValue());
continue;
}
case Instruction::PHI: {
PHINode *PN = cast<PHINode>(RVI);
for (Value *IncValue : PN->incoming_values())
FlowsToReturn.insert(IncValue);
continue;
}
// Check whether the pointer came from an allocation.
case Instruction::Alloca:
break;
case Instruction::Call:
case Instruction::Invoke: {
CallSite CS(RVI);
if (CS.paramHasAttr(0, Attribute::NoAlias))
break;
if (CS.getCalledFunction() &&
SCCNodes.count(CS.getCalledFunction()))
break;
} // fall-through
default:
return false; // Did not come from an allocation.
}
if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
return false;
}
return true;
}
/// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
SmallPtrSet<Function*, 8> 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());
// Check each function in turn, determining which functions return noalias
// 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 noalias.
if (F->doesNotAlias(0))
continue;
// Definitions with weak linkage may be overridden at linktime, so
// treat them like declarations.
if (F->isDeclaration() || F->mayBeOverridden())
return false;
// We annotate noalias return values, which are only applicable to
// pointer types.
if (!F->getReturnType()->isPointerTy())
continue;
if (!IsFunctionMallocLike(F, SCCNodes))
return false;
}
bool MadeChange = false;
for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
Function *F = (*I)->getFunction();
if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
continue;
F->setDoesNotAlias(0);
++NumNoAlias;
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.
bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
if (F.hasFnAttribute(Attribute::OptimizeNone))
return false;
FunctionType *FTy = F.getFunctionType();
LibFunc::Func TheLibFunc;
if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
return false;
switch (TheLibFunc) {
case LibFunc::strlen:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setOnlyReadsMemory(F);
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::strchr:
case LibFunc::strrchr:
if (FTy->getNumParams() != 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isIntegerTy())
return false;
setOnlyReadsMemory(F);
setDoesNotThrow(F);
break;
case LibFunc::strtol:
case LibFunc::strtod:
case LibFunc::strtof:
case LibFunc::strtoul:
case LibFunc::strtoll:
case LibFunc::strtold:
case LibFunc::strtoull:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::strcpy:
case LibFunc::stpcpy:
case LibFunc::strcat:
case LibFunc::strncat:
case LibFunc::strncpy:
case LibFunc::stpncpy:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::strxfrm:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::strcmp: //0,1
case LibFunc::strspn: // 0,1
case LibFunc::strncmp: // 0,1
case LibFunc::strcspn: //0,1
case LibFunc::strcoll: //0,1
case LibFunc::strcasecmp: // 0,1
case LibFunc::strncasecmp: //
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setOnlyReadsMemory(F);
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
break;
case LibFunc::strstr:
case LibFunc::strpbrk:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setOnlyReadsMemory(F);
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::strtok:
case LibFunc::strtok_r:
if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::scanf:
if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::setbuf:
case LibFunc::setvbuf:
if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::strdup:
case LibFunc::strndup:
if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::stat:
case LibFunc::statvfs:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::sscanf:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::sprintf:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::snprintf:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(2)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 3);
setOnlyReadsMemory(F, 3);
break;
case LibFunc::setitimer:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(1)->isPointerTy() ||
!FTy->getParamType(2)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
setDoesNotCapture(F, 3);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::system:
if (FTy->getNumParams() != 1 ||
!FTy->getParamType(0)->isPointerTy())
return false;
// May throw; "system" is a valid pthread cancellation point.
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::malloc:
if (FTy->getNumParams() != 1 ||
!FTy->getReturnType()->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
+ setOnlyAccessesArgMemory(F);
break;
case LibFunc::memcmp:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setOnlyReadsMemory(F);
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
break;
case LibFunc::memchr:
case LibFunc::memrchr:
if (FTy->getNumParams() != 3)
return false;
setOnlyReadsMemory(F);
setDoesNotThrow(F);
break;
case LibFunc::modf:
case LibFunc::modff:
case LibFunc::modfl:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::memcpy:
case LibFunc::memccpy:
case LibFunc::memmove:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::memalign:
if (!FTy->getReturnType()->isPointerTy())
return false;
setDoesNotAlias(F, 0);
break;
case LibFunc::mkdir:
if (FTy->getNumParams() == 0 ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::mktime:
if (FTy->getNumParams() == 0 ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::realloc:
if (FTy->getNumParams() != 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getReturnType()->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 1);
+ setOnlyAccessesArgMemory(F);
break;
case LibFunc::read:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(1)->isPointerTy())
return false;
// May throw; "read" is a valid pthread cancellation point.
setDoesNotCapture(F, 2);
break;
case LibFunc::rewind:
if (FTy->getNumParams() < 1 ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::rmdir:
case LibFunc::remove:
case LibFunc::realpath:
if (FTy->getNumParams() < 1 ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::rename:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::readlink:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::write:
if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
return false;
// May throw; "write" is a valid pthread cancellation point.
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::bcopy:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::bcmp:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setOnlyReadsMemory(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
break;
case LibFunc::bzero:
if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::calloc:
if (FTy->getNumParams() != 2 ||
!FTy->getReturnType()->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
+ setOnlyAccessesArgMemory(F);
break;
case LibFunc::chmod:
case LibFunc::chown:
if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::ctermid:
case LibFunc::clearerr:
case LibFunc::closedir:
if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::atoi:
case LibFunc::atol:
case LibFunc::atof:
case LibFunc::atoll:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setOnlyReadsMemory(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::access:
if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::fopen:
if (FTy->getNumParams() != 2 ||
!FTy->getReturnType()->isPointerTy() ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::fdopen:
if (FTy->getNumParams() != 2 ||
!FTy->getReturnType()->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
- case LibFunc::feof:
case LibFunc::free:
+ if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
+ return false;
+ setDoesNotThrow(F);
+ setDoesNotCapture(F, 1);
+ setOnlyAccessesArgMemory(F);
+ break;
+ case LibFunc::feof:
case LibFunc::fseek:
case LibFunc::ftell:
case LibFunc::fgetc:
case LibFunc::fseeko:
case LibFunc::ftello:
case LibFunc::fileno:
case LibFunc::fflush:
case LibFunc::fclose:
case LibFunc::fsetpos:
case LibFunc::flockfile:
case LibFunc::funlockfile:
case LibFunc::ftrylockfile:
if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::ferror:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F);
break;
case LibFunc::fputc:
case LibFunc::fstat:
case LibFunc::frexp:
case LibFunc::frexpf:
case LibFunc::frexpl:
case LibFunc::fstatvfs:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::fgets:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(2)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 3);
break;
case LibFunc::fread:
if (FTy->getNumParams() != 4 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(3)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 4);
break;
case LibFunc::fwrite:
if (FTy->getNumParams() != 4 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(3)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 4);
break;
case LibFunc::fputs:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::fscanf:
case LibFunc::fprintf:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
+ setOnlyAccessesArgMemory(F);
break;
case LibFunc::fgetpos:
if (FTy->getNumParams() < 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
break;
case LibFunc::getc:
case LibFunc::getlogin_r:
case LibFunc::getc_unlocked:
if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::getenv:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setOnlyReadsMemory(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::gets:
case LibFunc::getchar:
setDoesNotThrow(F);
break;
case LibFunc::getitimer:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::getpwnam:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::ungetc:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::uname:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::unlink:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::unsetenv:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::utime:
case LibFunc::utimes:
if (FTy->getNumParams() != 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::putc:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::puts:
case LibFunc::printf:
case LibFunc::perror:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
+ setOnlyAccessesArgMemory(F);
break;
case LibFunc::pread:
if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
return false;
// May throw; "pread" is a valid pthread cancellation point.
setDoesNotCapture(F, 2);
break;
case LibFunc::pwrite:
if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
return false;
// May throw; "pwrite" is a valid pthread cancellation point.
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::putchar:
setDoesNotThrow(F);
break;
case LibFunc::popen:
if (FTy->getNumParams() != 2 ||
!FTy->getReturnType()->isPointerTy() ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::pclose:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::vscanf:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::vsscanf:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(1)->isPointerTy() ||
!FTy->getParamType(2)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::vfscanf:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(1)->isPointerTy() ||
!FTy->getParamType(2)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::valloc:
if (!FTy->getReturnType()->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
break;
case LibFunc::vprintf:
if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::vfprintf:
case LibFunc::vsprintf:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::vsnprintf:
if (FTy->getNumParams() != 4 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(2)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 3);
setOnlyReadsMemory(F, 3);
break;
case LibFunc::open:
if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
return false;
// May throw; "open" is a valid pthread cancellation point.
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::opendir:
if (FTy->getNumParams() != 1 ||
!FTy->getReturnType()->isPointerTy() ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::tmpfile:
if (!FTy->getReturnType()->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
break;
case LibFunc::times:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::htonl:
case LibFunc::htons:
case LibFunc::ntohl:
case LibFunc::ntohs:
setDoesNotThrow(F);
setDoesNotAccessMemory(F);
break;
case LibFunc::lstat:
if (FTy->getNumParams() != 2 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::lchown:
if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::qsort:
if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
return false;
// May throw; places call through function pointer.
setDoesNotCapture(F, 4);
break;
case LibFunc::dunder_strdup:
case LibFunc::dunder_strndup:
if (FTy->getNumParams() < 1 ||
!FTy->getReturnType()->isPointerTy() ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::dunder_strtok_r:
if (FTy->getNumParams() != 3 ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::under_IO_getc:
if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::under_IO_putc:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::dunder_isoc99_scanf:
if (FTy->getNumParams() < 1 ||
!FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::stat64:
case LibFunc::lstat64:
case LibFunc::statvfs64:
if (FTy->getNumParams() < 1 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::dunder_isoc99_sscanf:
if (FTy->getNumParams() < 1 ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::fopen64:
if (FTy->getNumParams() != 2 ||
!FTy->getReturnType()->isPointerTy() ||
!FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
setOnlyReadsMemory(F, 1);
setOnlyReadsMemory(F, 2);
break;
case LibFunc::fseeko64:
case LibFunc::ftello64:
if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
break;
case LibFunc::tmpfile64:
if (!FTy->getReturnType()->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotAlias(F, 0);
break;
case LibFunc::fstat64:
case LibFunc::fstatvfs64:
if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
return false;
setDoesNotThrow(F);
setDoesNotCapture(F, 2);
break;
case LibFunc::open64:
if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
return false;
// May throw; "open" is a valid pthread cancellation point.
setDoesNotCapture(F, 1);
setOnlyReadsMemory(F, 1);
break;
case LibFunc::gettimeofday:
if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
!FTy->getParamType(1)->isPointerTy())
return false;
// Currently some platforms have the restrict keyword on the arguments to
// gettimeofday. To be conservative, do not add noalias to gettimeofday's
// arguments.
setDoesNotThrow(F);
setDoesNotCapture(F, 1);
setDoesNotCapture(F, 2);
break;
+ case LibFunc::sin:
+ case LibFunc::cos:
+ case LibFunc::pow:
+ case LibFunc::sqrt:
+ case LibFunc::log:
+ setDoesNotThrow(F);
+ setDoesNotAccessMemory(F);
+ break;
+ case LibFunc::exit:
+ setDoesNotAccessMemory(F);
+ break;
default:
// Didn't mark any attributes.
return false;
}
return true;
}
/// annotateLibraryCalls - Adds attributes to well-known standard library
/// call declarations.
bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
bool MadeChange = false;
// Check each function in turn annotating well-known library function
// declarations with attributes.
for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
Function *F = (*I)->getFunction();
if (F && F->isDeclaration())
MadeChange |= inferPrototypeAttributes(*F);
}
return MadeChange;
}
bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
AA = &getAnalysis<AliasAnalysis>();
TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
bool Changed = annotateLibraryCalls(SCC);
Changed |= AddReadAttrs(SCC);
Changed |= AddArgumentAttrs(SCC);
Changed |= AddNoAliasAttrs(SCC);
return Changed;
}
More information about the llvm-dev
mailing list