if (isFreeCall(I, &TLI)) {
if (Writers)
Writers->insert(CS->getParent()->getParent());
+ } else if (CS.doesNotCapture(CS.getArgumentNo(&U))) {
+ Function *ParentF = CS->getParent()->getParent();
+ // A nocapture argument may be read from or written to, but does not
+ // escape unless the call can somehow recurse.
+ //
+ // nocapture "indicates that the callee does not make any copies of
+ // the pointer that outlive itself". Therefore if we directly or
+ // indirectly recurse, we must treat the pointer as escaping.
+ if (FunctionToSCCMap[ParentF] ==
+ FunctionToSCCMap[CS.getCalledFunction()])
+ return true;
+ if (Readers)
+ Readers->insert(ParentF);
+ if (Writers)
+ Writers->insert(ParentF);
} else {
return true; // Argument of an unknown call.
}
/// 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 GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
+bool GlobalsAAResult::AnalyzeIndirectGlobalMemory(GlobalVariable *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;
+ // If the initializer is a valid pointer, bail.
+ if (Constant *C = GV->getInitializer())
+ if (!C->isNullValue())
+ return false;
+
// 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()) {
return true;
}
+void GlobalsAAResult::CollectSCCMembership(CallGraph &CG) {
+ // We do a bottom-up SCC traversal of the call graph. In other words, we
+ // visit all callees before callers (leaf-first).
+ unsigned SCCID = 0;
+ for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
+ const std::vector<CallGraphNode *> &SCC = *I;
+ assert(!SCC.empty() && "SCC with no functions?");
+
+ for (auto *CGN : SCC)
+ if (Function *F = CGN->getFunction())
+ FunctionToSCCMap[F] = SCCID;
+ ++SCCID;
+ }
+}
+
/// 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
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
+ if (!SCC[0]->getFunction() || SCC[0]->getFunction()->mayBeOverridden()) {
+ // Calls externally or is weak - can't say anything useful. Remove any existing
// function records (may have been created when scanning globals).
for (auto *Node : SCC)
FunctionInfos.erase(Node->getFunction());
// Finally, now that we know the full effect on this SCC, clone the
// information to each function in the SCC.
+ // FI is a reference into FunctionInfos, so copy it now so that it doesn't
+ // get invalidated if DenseMap decides to re-hash.
+ FunctionInfo CachedFI = FI;
for (unsigned i = 1, e = SCC.size(); i != e; ++i)
- FunctionInfos[SCC[i]->getFunction()] = FI;
+ FunctionInfos[SCC[i]->getFunction()] = CachedFI;
}
}
+// GV is a non-escaping global. V is a pointer address that has been loaded from.
+// If we can prove that V must escape, we can conclude that a load from V cannot
+// alias GV.
+static bool isNonEscapingGlobalNoAliasWithLoad(const GlobalValue *GV,
+ const Value *V,
+ int &Depth,
+ const DataLayout &DL) {
+ SmallPtrSet<const Value *, 8> Visited;
+ SmallVector<const Value *, 8> Inputs;
+ Visited.insert(V);
+ Inputs.push_back(V);
+ do {
+ const Value *Input = Inputs.pop_back_val();
+
+ if (isa<GlobalValue>(Input) || isa<Argument>(Input) || isa<CallInst>(Input) ||
+ isa<InvokeInst>(Input))
+ // Arguments to functions or returns from functions are inherently
+ // escaping, so we can immediately classify those as not aliasing any
+ // non-addr-taken globals.
+ //
+ // (Transitive) loads from a global are also safe - if this aliased
+ // another global, its address would escape, so no alias.
+ continue;
+
+ // Recurse through a limited number of selects, loads and PHIs. This is an
+ // arbitrary depth of 4, lower numbers could be used to fix compile time
+ // issues if needed, but this is generally expected to be only be important
+ // for small depths.
+ if (++Depth > 4)
+ return false;
+
+ if (auto *LI = dyn_cast<LoadInst>(Input)) {
+ Inputs.push_back(GetUnderlyingObject(LI->getPointerOperand(), DL));
+ continue;
+ }
+ if (auto *SI = dyn_cast<SelectInst>(Input)) {
+ const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
+ const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
+ if (Visited.insert(LHS).second)
+ Inputs.push_back(LHS);
+ if (Visited.insert(RHS).second)
+ Inputs.push_back(RHS);
+ continue;
+ }
+ if (auto *PN = dyn_cast<PHINode>(Input)) {
+ for (const Value *Op : PN->incoming_values()) {
+ Op = GetUnderlyingObject(Op, DL);
+ if (Visited.insert(Op).second)
+ Inputs.push_back(Op);
+ }
+ continue;
+ }
+
+ return false;
+ } while (!Inputs.empty());
+
+ // All inputs were known to be no-alias.
+ return true;
+}
+
// There are particular cases where we can conclude no-alias between
// a non-addr-taken global and some other underlying object. Specifically,
// a non-addr-taken global is known to not be escaped from any function. It is
// non-addr-taken globals.
continue;
}
+
+ // Recurse through a limited number of selects, loads and PHIs. This is an
+ // arbitrary depth of 4, lower numbers could be used to fix compile time
+ // issues if needed, but this is generally expected to be only be important
+ // for small depths.
+ if (++Depth > 4)
+ return false;
+
if (auto *LI = dyn_cast<LoadInst>(Input)) {
// A pointer loaded from a global would have been captured, and we know
// that the global is non-escaping, so no alias.
- if (isa<GlobalValue>(GetUnderlyingObject(LI->getPointerOperand(), DL)))
+ const Value *Ptr = GetUnderlyingObject(LI->getPointerOperand(), DL);
+ if (isNonEscapingGlobalNoAliasWithLoad(GV, Ptr, Depth, DL))
+ // The load does not alias with GV.
continue;
-
// Otherwise, a load could come from anywhere, so bail.
return false;
}
-
- // Recurse through a limited number of selects and PHIs. This is an
- // arbitrary depth of 4, lower numbers could be used to fix compile time
- // issues if needed, but this is generally expected to be only be important
- // for small depths.
- if (++Depth > 4)
- return false;
if (auto *SI = dyn_cast<SelectInst>(Input)) {
const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), DL);
const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), DL);
return AAResultBase::alias(LocA, LocB);
}
+ModRefInfo GlobalsAAResult::getModRefInfoForArgument(ImmutableCallSite CS,
+ const GlobalValue *GV) {
+ if (CS.doesNotAccessMemory())
+ return MRI_NoModRef;
+ ModRefInfo ConservativeResult = CS.onlyReadsMemory() ? MRI_Ref : MRI_ModRef;
+
+ // Iterate through all the arguments to the called function. If any argument
+ // is based on GV, return the conservative result.
+ for (auto &A : CS.args()) {
+ SmallVector<Value*, 4> Objects;
+ GetUnderlyingObjects(A, Objects, DL);
+
+ // All objects must be identified.
+ if (!std::all_of(Objects.begin(), Objects.end(), isIdentifiedObject))
+ return ConservativeResult;
+
+ if (std::find(Objects.begin(), Objects.end(), GV) != Objects.end())
+ return ConservativeResult;
+ }
+
+ // We identified all objects in the argument list, and none of them were GV.
+ return MRI_NoModRef;
+}
+
ModRefInfo GlobalsAAResult::getModRefInfo(ImmutableCallSite CS,
const MemoryLocation &Loc) {
unsigned Known = MRI_ModRef;
if (const Function *F = CS.getCalledFunction())
if (NonAddressTakenGlobals.count(GV))
if (const FunctionInfo *FI = getFunctionInfo(F))
- Known = FI->getModRefInfoForGlobal(*GV);
+ Known = FI->getModRefInfoForGlobal(*GV) |
+ getModRefInfoForArgument(CS, GV);
if (Known == MRI_NoModRef)
return MRI_NoModRef; // No need to query other mod/ref analyses
CallGraph &CG) {
GlobalsAAResult Result(M.getDataLayout(), TLI);
+ // Discover which functions aren't recursive, to feed into AnalyzeGlobals.
+ Result.CollectSCCMembership(CG);
+
// Find non-addr taken globals.
Result.AnalyzeGlobals(M);
projects / oota-llvm.git / blobdiff