#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringSwitch.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
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");
+STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
namespace {
typedef SmallSetVector<Function *, 8> SCCNodeSet;
}
bool runOnSCC(CallGraphSCC &SCC) override;
-
+ bool doInitialization(CallGraph &CG) override {
+ Revisit.clear();
+ return false;
+ }
+ bool doFinalization(CallGraph &CG) override;
+
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<AssumptionCacheTracker>();
private:
TargetLibraryInfo *TLI;
-
- bool annotateLibraryCalls(const CallGraphSCC &SCC);
+ SmallVector<WeakVH,16> Revisit;
};
}
for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
CI != CE; ++CI) {
Value *Arg = *CI;
- if (!Arg->getType()->isPointerTy())
+ if (!Arg->getType()->isPtrOrPtrVectorTy())
continue;
AAMDNodes AAInfo;
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;
- }
+ // Note: the callee and the two successor blocks *follow* the argument
+ // operands. This means there is no need to adjust UseIndex to account for
+ // these.
+
+ unsigned UseIndex =
+ std::distance(const_cast<const Use *>(CS.arg_begin()), U);
+
+ assert(UseIndex < CS.data_operands_size() &&
+ "Indirect function calls should have been filtered above!");
+
+ if (UseIndex >= CS.getNumArgOperands()) {
+ // Data operand, but not a argument operand -- must be a bundle operand
+ assert(CS.hasOperandBundles() && "Must be!");
+
+ // CaptureTracking told us that we're being captured by an operand bundle
+ // use. In this case it does not matter if the callee is within our SCC
+ // or not -- we've been captured in some unknown way, and we have to be
+ // conservative.
+ Captured = true;
+ return true;
+ }
+
+ if (UseIndex >= F->arg_size()) {
+ assert(F->isVarArg() && "More params than args in non-varargs call");
+ Captured = true;
+ return true;
}
- assert(Found && "Capturing call-site captured nothing?");
- (void)Found;
+
+ Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
return false;
}
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:
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;
- }
+ // Note: the callee and the two successor blocks *follow* the argument
+ // operands. This means there is no need to adjust UseIndex to account
+ // for these.
+
+ unsigned UseIndex = std::distance(CS.arg_begin(), U);
+
+ // U cannot be the callee operand use: since we're exploring the
+ // transitive uses of an Argument, having such a use be a callee would
+ // imply the CallSite is an indirect call or invoke; and we'd take the
+ // early exit above.
+ assert(UseIndex < CS.data_operands_size() &&
+ "Data operand use expected!");
+
+ bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
+
+ if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
+ assert(F->isVarArg() && "More params than args in non-varargs call");
+ return Attribute::None;
+ }
+
+ Captures &= !CS.doesNotCapture(UseIndex);
+
+ // Since the optimizer (by design) cannot see the data flow corresponding
+ // to a operand bundle use, these cannot participate in the optimistic SCC
+ // analysis. Instead, we model the operand bundle uses as arguments in
+ // call to a function external to the SCC.
+ if (!SCCNodes.count(&*std::next(F->arg_begin(), UseIndex)) ||
+ IsOperandBundleUse) {
+
+ // The accessors used on CallSite here do the right thing for calls and
+ // invokes with operand bundles.
+
+ if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
+ return Attribute::None;
+ if (!CS.doesNotAccessMemory(UseIndex))
+ IsRead = true;
}
+
AddUsersToWorklistIfCapturing();
break;
}
return MadeChange;
}
-static void setDoesNotAccessMemory(Function &F) {
- if (!F.doesNotAccessMemory()) {
- F.setDoesNotAccessMemory();
- ++NumAnnotated;
- }
-}
-
-static void setOnlyReadsMemory(Function &F) {
- if (!F.onlyReadsMemory()) {
- F.setOnlyReadsMemory();
- ++NumAnnotated;
- }
-}
-
-static void setDoesNotThrow(Function &F) {
- if (!F.doesNotThrow()) {
- F.setDoesNotThrow();
- ++NumAnnotated;
- }
-}
-
-static void setDoesNotCapture(Function &F, unsigned n) {
- if (!F.doesNotCapture(n)) {
- F.setDoesNotCapture(n);
- ++NumAnnotated;
- }
-}
-
-static void setOnlyReadsMemory(Function &F, unsigned n) {
- if (!F.onlyReadsMemory(n)) {
- F.setOnlyReadsMemory(n);
- ++NumAnnotated;
- }
+static bool setDoesNotRecurse(Function &F) {
+ if (F.doesNotRecurse())
+ return false;
+ F.setDoesNotRecurse();
+ ++NumNoRecurse;
+ return true;
}
-static void setDoesNotAlias(Function &F, unsigned n) {
- if (!F.doesNotAlias(n)) {
- F.setDoesNotAlias(n);
- ++NumAnnotated;
- }
-}
+static bool addNoRecurseAttrs(const CallGraphSCC &SCC,
+ SmallVectorImpl<WeakVH> &Revisit) {
+ // Try and identify functions that do not recurse.
-/// Analyze the name and prototype of the given function and set any applicable
-/// attributes.
-///
-/// Returns true if any attributes were set and false otherwise.
-static bool inferPrototypeAttributes(Function &F, const TargetLibraryInfo &TLI) {
- if (F.hasFnAttribute(Attribute::OptimizeNone))
+ // If the SCC contains multiple nodes we know for sure there is recursion.
+ if (!SCC.isSingular())
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);
- 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);
- 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);
- 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:
- 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);
- 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);
- 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;
- default:
- // Didn't mark any attributes.
+ const CallGraphNode *CGN = *SCC.begin();
+ Function *F = CGN->getFunction();
+ if (!F || F->isDeclaration() || F->doesNotRecurse())
return false;
- }
- return true;
+ // If all of the calls in F are identifiable and are to norecurse functions, F
+ // is norecurse. This check also detects self-recursion as F is not currently
+ // marked norecurse, so any called from F to F will not be marked norecurse.
+ if (std::all_of(CGN->begin(), CGN->end(),
+ [](const CallGraphNode::CallRecord &CR) {
+ Function *F = CR.second->getFunction();
+ return F && F->doesNotRecurse();
+ }))
+ // Function calls a potentially recursive function.
+ return setDoesNotRecurse(*F);
+
+ // We know that F is not obviously recursive, but we haven't been able to
+ // prove that it doesn't actually recurse. Add it to the Revisit list to try
+ // again top-down later.
+ Revisit.push_back(F);
+ return false;
}
-/// 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, *TLI);
+static bool addNoRecurseAttrsTopDownOnly(Function *F) {
+ // If F is internal and all uses are in norecurse functions, then F is also
+ // norecurse.
+ if (F->doesNotRecurse())
+ return false;
+ if (F->hasInternalLinkage()) {
+ for (auto *U : F->users())
+ if (auto *I = dyn_cast<Instruction>(U)) {
+ if (!I->getParent()->getParent()->doesNotRecurse())
+ return false;
+ } else {
+ return false;
+ }
+ return setDoesNotRecurse(*F);
}
-
- return MadeChange;
+ return false;
}
bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
-
- // Annotate declarations for which we have special knowledge.
- bool Changed = annotateLibraryCalls(SCC);
+ bool Changed = false;
// We compute dedicated AA results for each function in the SCC as needed. We
// use a lambda referencing external objects so that they live long enough to
Changed |= addReadAttrs(SCCNodes, AARGetter);
Changed |= addArgumentAttrs(SCCNodes);
- // If we have no external nodes participating in the SCC, we can infer some
+ // If we have no external nodes participating in the SCC, we can deduce some
// more precise attributes as well.
if (!ExternalNode) {
Changed |= addNoAliasAttrs(SCCNodes);
Changed |= addNonNullAttrs(SCCNodes, *TLI);
}
+
+ Changed |= addNoRecurseAttrs(SCC, Revisit);
+ return Changed;
+}
+bool FunctionAttrs::doFinalization(CallGraph &CG) {
+ bool Changed = false;
+ // When iterating over SCCs we visit functions in a bottom-up fashion. Some of
+ // the rules we have for identifying norecurse functions work best with a
+ // top-down walk, so look again at all the functions we previously marked as
+ // worth revisiting, in top-down order.
+ for (auto &F : reverse(Revisit))
+ if (F)
+ Changed |= addNoRecurseAttrsTopDownOnly(cast<Function>((Value*)F));
return Changed;
}
projects / oota-llvm.git / blobdiff