#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/UniqueVector.h"
-#include "llvm/Support/Compiler.h"
#include "llvm/Support/InstIterator.h"
using namespace llvm;
STATISTIC(NumNoAlias, "Number of function returns marked noalias");
namespace {
- struct VISIBILITY_HIDDEN FunctionAttrs : public CallGraphSCCPass {
+ struct FunctionAttrs : public CallGraphSCCPass {
static char ID; // Pass identification, replacement for typeid
FunctionAttrs() : CallGraphSCCPass(&ID) {}
// runOnSCC - Analyze the SCC, performing the transformation if possible.
- bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
+ bool runOnSCC(std::vector<CallGraphNode *> &SCC);
// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
bool AddReadAttrs(const std::vector<CallGraphNode *> &SCC);
// IsFunctionMallocLike - Does this function allocate new memory?
bool IsFunctionMallocLike(Function *F,
- SmallPtrSet<CallGraphNode*, 8> &) const;
+ SmallPtrSet<Function*, 8> &) const;
// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
bool AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC);
/// memory that is local to the function. Global constants are considered
/// local to all functions.
bool FunctionAttrs::PointsToLocalMemory(Value *V) {
- V = V->getUnderlyingObject();
- // An alloca instruction defines local memory.
- if (isa<AllocaInst>(V))
- return true;
- // A global constant counts as local memory for our purposes.
- if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
- return GV->isConstant();
- // Could look through phi nodes and selects here, but it doesn't seem
- // to be useful in practice.
- return false;
+ SmallVector<Value*, 16> Worklist;
+ unsigned MaxLookup = 8;
+
+ Worklist.push_back(V);
+
+ do {
+ V = Worklist.pop_back_val()->getUnderlyingObject();
+
+ // An alloca instruction defines local memory.
+ if (isa<AllocaInst>(V))
+ continue;
+
+ // A global constant counts as local memory for our purposes.
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
+ if (!GV->isConstant())
+ return false;
+ continue;
+ }
+
+ // If both select values point to local memory, then so does the select.
+ if (SelectInst *SI = dyn_cast<SelectInst>(V)) {
+ Worklist.push_back(SI->getTrueValue());
+ Worklist.push_back(SI->getFalseValue());
+ continue;
+ }
+
+ // If all values incoming to a phi node point to local memory, then so does
+ // the phi.
+ if (PHINode *PN = dyn_cast<PHINode>(V)) {
+ // Don't bother inspecting phi nodes with many operands.
+ if (PN->getNumIncomingValues() > MaxLookup)
+ return false;
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ Worklist.push_back(PN->getIncomingValue(i));
+ continue;
+ }
+
+ return false;
+ } while (!Worklist.empty() && --MaxLookup);
+
+ return Worklist.empty();
}
/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) {
- SmallPtrSet<CallGraphNode*, 8> SCCNodes;
- CallGraph &CG = getAnalysis<CallGraph>();
+ 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 (unsigned i = 0, e = SCC.size(); i != e; ++i)
- SCCNodes.insert(SCC[i]);
+ SCCNodes.insert(SCC[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.
// 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 = CallSite::get(I);
- if (CS.getInstruction()) {
+ if (CS.getInstruction() && CS.getCalledFunction()) {
// Ignore calls to functions in the same SCC.
- if (SCCNodes.count(CG[CS.getCalledFunction()]))
+ if (SCCNodes.count(CS.getCalledFunction()))
continue;
+ // Ignore intrinsics that only access local memory.
+ if (unsigned id = CS.getCalledFunction()->getIntrinsicID())
+ if (AliasAnalysis::getModRefBehavior(id) ==
+ AliasAnalysis::AccessesArguments) {
+ // Check that all pointer arguments point to local memory.
+ for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
+ CI != CE; ++CI) {
+ Value *Arg = *CI;
+ if (Arg->getType()->isPointerTy() && !PointsToLocalMemory(Arg))
+ // Writes memory. Just give up.
+ return false;
+ }
+ // Only reads and writes local memory.
+ continue;
+ }
} else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
// Ignore loads from local memory.
if (PointsToLocalMemory(LI->getPointerOperand()))
continue;
}
- // Ignore dbg info intrinsics.
- if (isa<DbgInfoIntrinsic>(I))
- 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 (isMalloc(I))
+ // malloc claims not to write memory! PR3754.
+ return false;
+
// If this instruction may read memory, remember that.
ReadsMemory |= I->mayReadFromMemory();
}
continue;
for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A)
- if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr() &&
- !PointerMayBeCaptured(A, true)) {
+ if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr() &&
+ !PointerMayBeCaptured(A, true, /*StoreCaptures=*/false)) {
A->addAttr(Attribute::NoCapture);
++NumNoCapture;
Changed = true;
}
/// IsFunctionMallocLike - A function is malloc-like if it returns either null
-/// or a pointer that don't alias any other pointer visible to the caller.
+/// or a pointer that doesn't alias any other pointer visible to the caller.
bool FunctionAttrs::IsFunctionMallocLike(Function *F,
- SmallPtrSet<CallGraphNode*, 8> &SCCNodes) const {
- CallGraph &CG = getAnalysis<CallGraph>();
-
+ SmallPtrSet<Function*, 8> &SCCNodes) const {
UniqueVector<Value *> FlowsToReturn;
for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
switch (RVI->getOpcode()) {
// Extend the analysis by looking upwards.
- case Instruction::GetElementPtr:
case Instruction::BitCast:
+ case Instruction::GetElementPtr:
FlowsToReturn.insert(RVI->getOperand(0));
continue;
case Instruction::Select: {
SelectInst *SI = cast<SelectInst>(RVI);
FlowsToReturn.insert(SI->getTrueValue());
FlowsToReturn.insert(SI->getFalseValue());
- } continue;
+ continue;
+ }
case Instruction::PHI: {
PHINode *PN = cast<PHINode>(RVI);
for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
FlowsToReturn.insert(PN->getIncomingValue(i));
- } continue;
+ continue;
+ }
// Check whether the pointer came from an allocation.
case Instruction::Alloca:
- case Instruction::Malloc:
break;
case Instruction::Call:
case Instruction::Invoke: {
if (CS.paramHasAttr(0, Attribute::NoAlias))
break;
if (CS.getCalledFunction() &&
- SCCNodes.count(CG[CS.getCalledFunction()]))
+ SCCNodes.count(CS.getCalledFunction()))
break;
} // fall-through
default:
return false; // Did not come from an allocation.
}
- if (PointerMayBeCaptured(RetVal, false))
+ if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
return false;
}
/// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
bool FunctionAttrs::AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC) {
- SmallPtrSet<CallGraphNode*, 8> SCCNodes;
+ 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 (unsigned i = 0, e = SCC.size(); i != e; ++i)
- SCCNodes.insert(SCC[i]);
+ SCCNodes.insert(SCC[i]->getFunction());
- // Check each function in turn, determining which pointer arguments are not
- // captured.
+ // Check each function in turn, determining which functions return noalias
+ // pointers.
for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
Function *F = SCC[i]->getFunction();
// We annotate noalias return values, which are only applicable to
// pointer types.
- if (!isa<PointerType>(F->getReturnType()))
+ if (!F->getReturnType()->isPointerTy())
continue;
if (!IsFunctionMallocLike(F, SCCNodes))
bool MadeChange = false;
for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
Function *F = SCC[i]->getFunction();
- if (F->doesNotAlias(0) || !isa<PointerType>(F->getReturnType()))
+ if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
continue;
F->setDoesNotAlias(0);
return MadeChange;
}
-bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
+bool FunctionAttrs::runOnSCC(std::vector<CallGraphNode *> &SCC) {
bool Changed = AddReadAttrs(SCC);
Changed |= AddNoCaptureAttrs(SCC);
Changed |= AddNoAliasAttrs(SCC);
projects / oota-llvm.git / blobdiff