#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstIterator.h"
/// general and as pertains to specific globals. We only have this detailed
/// information when we know *something* useful about the behavior. If we
/// saturate to fully general mod/ref, we remove the info for the function.
-class GlobalsModRef::FunctionInfo {
+class GlobalsAAResult::FunctionInfo {
typedef SmallDenseMap<const GlobalValue *, ModRefInfo, 16> GlobalInfoMapType;
/// Build a wrapper struct that has 8-byte alignment. All heap allocations
PointerIntPair<AlignedMap *, 3, unsigned, AlignedMapPointerTraits> Info;
};
-void GlobalsModRef::DeletionCallbackHandle::deleted() {
+void GlobalsAAResult::DeletionCallbackHandle::deleted() {
Value *V = getValPtr();
if (auto *F = dyn_cast<Function>(V))
- GMR.FunctionInfos.erase(F);
+ GAR->FunctionInfos.erase(F);
if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
- if (GMR.NonAddressTakenGlobals.erase(GV)) {
+ if (GAR->NonAddressTakenGlobals.erase(GV)) {
// This global might be an indirect global. If so, remove it and
// remove any AllocRelatedValues for it.
- if (GMR.IndirectGlobals.erase(GV)) {
+ if (GAR->IndirectGlobals.erase(GV)) {
// Remove any entries in AllocsForIndirectGlobals for this global.
- for (auto I = GMR.AllocsForIndirectGlobals.begin(),
- E = GMR.AllocsForIndirectGlobals.end();
+ for (auto I = GAR->AllocsForIndirectGlobals.begin(),
+ E = GAR->AllocsForIndirectGlobals.end();
I != E; ++I)
if (I->second == GV)
- GMR.AllocsForIndirectGlobals.erase(I);
+ GAR->AllocsForIndirectGlobals.erase(I);
}
// Scan the function info we have collected and remove this global
// from all of them.
- for (auto &FIPair : GMR.FunctionInfos)
+ for (auto &FIPair : GAR->FunctionInfos)
FIPair.second.eraseModRefInfoForGlobal(*GV);
}
}
// If this is an allocation related to an indirect global, remove it.
- GMR.AllocsForIndirectGlobals.erase(V);
+ GAR->AllocsForIndirectGlobals.erase(V);
// And clear out the handle.
setValPtr(nullptr);
- GMR.Handles.erase(I);
+ GAR->Handles.erase(I);
// This object is now destroyed!
}
-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(); }
-
-GlobalsModRef::GlobalsModRef() : ModulePass(ID) {
- initializeGlobalsModRefPass(*PassRegistry::getPassRegistry());
-}
-
-FunctionModRefBehavior GlobalsModRef::getModRefBehavior(const Function *F) {
+FunctionModRefBehavior GlobalsAAResult::getModRefBehavior(const Function *F) {
FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
if (FunctionInfo *FI = getFunctionInfo(F)) {
Min = FMRB_OnlyReadsMemory;
}
- return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min);
+ return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min);
}
-FunctionModRefBehavior GlobalsModRef::getModRefBehavior(ImmutableCallSite CS) {
+FunctionModRefBehavior
+GlobalsAAResult::getModRefBehavior(ImmutableCallSite CS) {
FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
if (const Function *F = CS.getCalledFunction())
Min = FMRB_OnlyReadsMemory;
}
- return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
+ return FunctionModRefBehavior(AAResultBase::getModRefBehavior(CS) & Min);
}
/// Returns the function info for the function, or null if we don't have
/// anything useful to say about it.
-GlobalsModRef::FunctionInfo *GlobalsModRef::getFunctionInfo(const Function *F) {
+GlobalsAAResult::FunctionInfo *
+GlobalsAAResult::getFunctionInfo(const Function *F) {
auto I = FunctionInfos.find(F);
if (I != FunctionInfos.end())
return &I->second;
/// 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) {
+void GlobalsAAResult::AnalyzeGlobals(Module &M) {
SmallPtrSet<Function *, 64> TrackedFunctions;
for (Function &F : M)
if (F.hasLocalLinkage())
/// write to the value.
///
/// If OkayStoreDest is non-null, stores into this global are allowed.
-bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
- SmallPtrSetImpl<Function *> *Readers,
- SmallPtrSetImpl<Function *> *Writers,
- GlobalValue *OkayStoreDest) {
+bool GlobalsAAResult::AnalyzeUsesOfPointer(Value *V,
+ SmallPtrSetImpl<Function *> *Readers,
+ SmallPtrSetImpl<Function *> *Writers,
+ GlobalValue *OkayStoreDest) {
if (!V->getType()->isPointerTy())
return true;
// passing into the function.
if (!CS.isCallee(&U)) {
// Detect calls to free.
- if (isFreeCall(I, TLI)) {
+ 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 GlobalsModRef::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()) {
Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
GV->getParent()->getDataLayout());
- if (!isAllocLikeFn(Ptr, TLI))
+ if (!isAllocLikeFn(Ptr, &TLI))
return false; // Too hard to analyze.
// Analyze all uses of the allocation. If any of them are used in a
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
/// function.
-void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
+void GlobalsAAResult::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
+ 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());
// We handle calls specially because the graph-relevant aspects are
// handled above.
if (auto CS = CallSite(&I)) {
- if (isAllocationFn(&I, TLI) || isFreeCall(&I, TLI)) {
+ if (isAllocationFn(&I, &TLI) || isFreeCall(&I, &TLI)) {
// FIXME: It is completely unclear why this is necessary and not
// handled by the above graph code.
FI.addModRefInfo(MRI_ModRef);
// The callgraph doesn't include intrinsic calls.
if (Callee->isIntrinsic()) {
FunctionModRefBehavior Behaviour =
- AliasAnalysis::getModRefBehavior(Callee);
+ AAResultBase::getModRefBehavior(Callee);
FI.addModRefInfo(ModRefInfo(Behaviour & MRI_ModRef));
}
}
// 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
// variables in this way to either not trust AA results while the escape is
// active, or to be forced to operate as a module pass that cannot co-exist
// with an alias analysis such as GMR.
-bool GlobalsModRef::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
- const Value *V) {
+bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
+ const Value *V) {
// In order to know that the underlying object cannot alias the
// non-addr-taken global, we must know that it would have to be an escape.
// Thus if the underlying object is a function argument, a load from
Type *GVType = GVar->getInitializer()->getType();
Type *InputGVType = InputGVar->getInitializer()->getType();
if (GVType->isSized() && InputGVType->isSized() &&
- (DL->getTypeAllocSize(GVType) > 0) &&
- (DL->getTypeAllocSize(InputGVType) > 0))
+ (DL.getTypeAllocSize(GVType) > 0) &&
+ (DL.getTypeAllocSize(InputGVType) > 0))
continue;
}
// 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);
+ 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)
}
if (auto *PN = dyn_cast<PHINode>(Input)) {
for (const Value *Op : PN->incoming_values()) {
- Op = GetUnderlyingObject(Op, *DL);
+ Op = GetUnderlyingObject(Op, DL);
if (Visited.insert(Op).second)
Inputs.push_back(Op);
}
// FIXME: It would be good to handle other obvious no-alias cases here, but
// it isn't clear how to do so reasonbly without building a small version
- // of BasicAA into this code. We could recurse into AliasAnalysis::alias
+ // of BasicAA into this code. We could recurse into AAResultBase::alias
// here but that seems likely to go poorly as we're inside the
// implementation of such a query. Until then, just conservatievly retun
// false.
/// 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) {
+AliasResult GlobalsAAResult::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);
+ 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.
if ((GV1 || GV2) && GV1 != GV2)
return NoAlias;
- return AliasAnalysis::alias(LocA, LocB);
+ return AAResultBase::alias(LocA, LocB);
}
-ModRefInfo GlobalsModRef::getModRefInfo(ImmutableCallSite CS,
- const MemoryLocation &Loc) {
+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 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 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
- return ModRefInfo(Known & AliasAnalysis::getModRefInfo(CS, Loc));
+ return ModRefInfo(Known & AAResultBase::getModRefInfo(CS, Loc));
+}
+
+GlobalsAAResult::GlobalsAAResult(const DataLayout &DL,
+ const TargetLibraryInfo &TLI)
+ : AAResultBase(TLI), DL(DL) {}
+
+GlobalsAAResult::GlobalsAAResult(GlobalsAAResult &&Arg)
+ : AAResultBase(std::move(Arg)), DL(Arg.DL),
+ NonAddressTakenGlobals(std::move(Arg.NonAddressTakenGlobals)),
+ IndirectGlobals(std::move(Arg.IndirectGlobals)),
+ AllocsForIndirectGlobals(std::move(Arg.AllocsForIndirectGlobals)),
+ FunctionInfos(std::move(Arg.FunctionInfos)),
+ Handles(std::move(Arg.Handles)) {
+ // Update the parent for each DeletionCallbackHandle.
+ for (auto &H : Handles) {
+ assert(H.GAR == &Arg);
+ H.GAR = this;
+ }
+}
+
+/*static*/ GlobalsAAResult
+GlobalsAAResult::analyzeModule(Module &M, const TargetLibraryInfo &TLI,
+ 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);
+
+ // Propagate on CG.
+ Result.AnalyzeCallGraph(CG, M);
+
+ return Result;
+}
+
+GlobalsAAResult GlobalsAA::run(Module &M, AnalysisManager<Module> *AM) {
+ return GlobalsAAResult::analyzeModule(M,
+ AM->getResult<TargetLibraryAnalysis>(M),
+ AM->getResult<CallGraphAnalysis>(M));
+}
+
+char GlobalsAA::PassID;
+
+char GlobalsAAWrapperPass::ID = 0;
+INITIALIZE_PASS_BEGIN(GlobalsAAWrapperPass, "globals-aa",
+ "Globals Alias Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_END(GlobalsAAWrapperPass, "globals-aa",
+ "Globals Alias Analysis", false, true)
+
+ModulePass *llvm::createGlobalsAAWrapperPass() {
+ return new GlobalsAAWrapperPass();
+}
+
+GlobalsAAWrapperPass::GlobalsAAWrapperPass() : ModulePass(ID) {
+ initializeGlobalsAAWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+bool GlobalsAAWrapperPass::runOnModule(Module &M) {
+ Result.reset(new GlobalsAAResult(GlobalsAAResult::analyzeModule(
+ M, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
+ getAnalysis<CallGraphWrapperPass>().getCallGraph())));
+ return false;
+}
+
+bool GlobalsAAWrapperPass::doFinalization(Module &M) {
+ Result.reset();
+ return false;
+}
+
+void GlobalsAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AU.addRequired<CallGraphWrapperPass>();
+ AU.addRequired<TargetLibraryInfoWrapperPass>();
}
projects / oota-llvm.git / blobdiff