From a25e5dbcc2371352386a01e3c1b8e76dd890272b Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 8 Nov 2010 16:45:26 +0000 Subject: [PATCH] Extend the AliasAnalysis::pointsToConstantMemory interface to allow it to optionally look for constant or local (alloca) memory. Teach BasicAliasAnalysis::pointsToConstantMemory to look through Select and Phi nodes, and to support looking for local memory. Remove FunctionAttrs' PointsToLocalOrConstantMemory function, now that AliasAnalysis knows all the tricks that it knew. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@118412 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/AliasAnalysis.h | 15 +++-- lib/Analysis/AliasAnalysis.cpp | 5 +- lib/Analysis/AliasAnalysisCounter.cpp | 4 +- lib/Analysis/AliasDebugger.cpp | 4 +- lib/Analysis/BasicAliasAnalysis.cpp | 65 +++++++++++++++---- lib/Analysis/NoAliasAnalysis.cpp | 5 +- lib/Analysis/TypeBasedAliasAnalysis.cpp | 11 ++-- lib/Transforms/IPO/FunctionAttrs.cpp | 57 ++-------------- .../FunctionAttrs/2008-12-29-Constant.ll | 2 +- 9 files changed, 85 insertions(+), 83 deletions(-) diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 6a22ad36a59..48a93962627 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -154,15 +154,16 @@ public: return isNoAlias(Location(V1, V1Size), Location(V2, V2Size)); } - /// pointsToConstantMemory - If the specified memory location is known to be - /// constant, return true. This allows disambiguation of store - /// instructions from constant pointers. - /// - virtual bool pointsToConstantMemory(const Location &Loc); + /// pointsToConstantMemory - If the specified memory location is + /// known to be constant, return true. If OrLocal is true and the + /// specified memory location is known to be "local" (derived from + /// an alloca), return true. Otherwise return false. + virtual bool pointsToConstantMemory(const Location &Loc, + bool OrLocal = false); /// pointsToConstantMemory - A convenient wrapper. - bool pointsToConstantMemory(const Value *P) { - return pointsToConstantMemory(Location(P)); + bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { + return pointsToConstantMemory(Location(P), OrLocal); } //===--------------------------------------------------------------------===// diff --git a/lib/Analysis/AliasAnalysis.cpp b/lib/Analysis/AliasAnalysis.cpp index 472d57ab402..d513ebbc2a9 100644 --- a/lib/Analysis/AliasAnalysis.cpp +++ b/lib/Analysis/AliasAnalysis.cpp @@ -49,9 +49,10 @@ AliasAnalysis::alias(const Location &LocA, const Location &LocB) { return AA->alias(LocA, LocB); } -bool AliasAnalysis::pointsToConstantMemory(const Location &Loc) { +bool AliasAnalysis::pointsToConstantMemory(const Location &Loc, + bool OrLocal) { assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); - return AA->pointsToConstantMemory(Loc); + return AA->pointsToConstantMemory(Loc, OrLocal); } void AliasAnalysis::deleteValue(Value *V) { diff --git a/lib/Analysis/AliasAnalysisCounter.cpp b/lib/Analysis/AliasAnalysisCounter.cpp index a82d9598295..23be94ffb08 100644 --- a/lib/Analysis/AliasAnalysisCounter.cpp +++ b/lib/Analysis/AliasAnalysisCounter.cpp @@ -95,8 +95,8 @@ namespace { } // FIXME: We could count these too... - bool pointsToConstantMemory(const Location &Loc) { - return getAnalysis().pointsToConstantMemory(Loc); + bool pointsToConstantMemory(const Location &Loc, bool OrLocal) { + return getAnalysis().pointsToConstantMemory(Loc, OrLocal); } // Forwarding functions: just delegate to a real AA implementation, counting diff --git a/lib/Analysis/AliasDebugger.cpp b/lib/Analysis/AliasDebugger.cpp index 4b9aefcb114..f15c05153e1 100644 --- a/lib/Analysis/AliasDebugger.cpp +++ b/lib/Analysis/AliasDebugger.cpp @@ -113,9 +113,9 @@ namespace { return AliasAnalysis::getModRefInfo(CS1,CS2); } - bool pointsToConstantMemory(const Location &Loc) { + bool pointsToConstantMemory(const Location &Loc, bool OrLocal) { assert(Vals.find(Loc.Ptr) != Vals.end() && "Never seen value in AA before"); - return AliasAnalysis::pointsToConstantMemory(Loc); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); } virtual void deleteValue(Value *V) { diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 221c8639e0f..db493eeedca 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -456,7 +456,7 @@ namespace { /// pointsToConstantMemory - Chase pointers until we find a (constant /// global) or not. - virtual bool pointsToConstantMemory(const Location &Loc); + virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); /// getModRefBehavior - Return the behavior when calling the given /// call site. @@ -517,18 +517,61 @@ ImmutablePass *llvm::createBasicAliasAnalysisPass() { return new BasicAliasAnalysis(); } +/// pointsToConstantMemory - Returns whether the given pointer value +/// points to memory that is local to the function, with global constants being +/// considered local to all functions. +bool +BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { + assert(Visited.empty() && "Visited must be cleared after use!"); -/// pointsToConstantMemory - Chase pointers until we find a (constant -/// global) or not. -bool BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc) { - if (const GlobalVariable *GV = - dyn_cast(Loc.Ptr->getUnderlyingObject())) - // Note: this doesn't require GV to be "ODR" because it isn't legal for a - // global to be marked constant in some modules and non-constant in others. - // GV may even be a declaration, not a definition. - return GV->isConstant(); + SmallVector Worklist; + Worklist.push_back(Loc.Ptr); + do { + const Value *V = Worklist.pop_back_val()->getUnderlyingObject(); + if (!Visited.insert(V)) { + Visited.clear(); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); + } + + // An alloca instruction defines local memory. + if (OrLocal && isa(V)) + continue; + + // A global constant counts as local memory for our purposes. + if (const GlobalVariable *GV = dyn_cast(V)) { + // Note: this doesn't require GV to be "ODR" because it isn't legal for a + // global to be marked constant in some modules and non-constant in + // others. GV may even be a declaration, not a definition. + if (!GV->isConstant()) { + Visited.clear(); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); + } + continue; + } + + // If both select values point to local memory, then so does the select. + if (const SelectInst *SI = dyn_cast(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 (const PHINode *PN = dyn_cast(V)) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + Worklist.push_back(PN->getIncomingValue(i)); + continue; + } + + // Otherwise be conservative. + Visited.clear(); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); + + } while (!Worklist.empty()); - return AliasAnalysis::pointsToConstantMemory(Loc); + Visited.clear(); + return true; } /// getModRefBehavior - Return the behavior when calling the given call site. diff --git a/lib/Analysis/NoAliasAnalysis.cpp b/lib/Analysis/NoAliasAnalysis.cpp index 7602149edc0..ab7a69241e9 100644 --- a/lib/Analysis/NoAliasAnalysis.cpp +++ b/lib/Analysis/NoAliasAnalysis.cpp @@ -50,7 +50,10 @@ namespace { return UnknownModRefBehavior; } - virtual bool pointsToConstantMemory(const Location &Loc) { return false; } + virtual bool pointsToConstantMemory(const Location &Loc, + bool OrLocal) { + return false; + } virtual ModRefResult getModRefInfo(ImmutableCallSite CS, const Location &Loc) { return ModRef; diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp index 0516d64a710..044a93f8661 100644 --- a/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -138,7 +138,7 @@ namespace { private: virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual AliasResult alias(const Location &LocA, const Location &LocB); - virtual bool pointsToConstantMemory(const Location &Loc); + virtual bool pointsToConstantMemory(const Location &Loc, bool OrLocal); virtual ModRefResult getModRefInfo(ImmutableCallSite CS, const Location &Loc); virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, @@ -225,19 +225,20 @@ TypeBasedAliasAnalysis::alias(const Location &LocA, return NoAlias; } -bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc) { +bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, + bool OrLocal) { if (!EnableTBAA) - return AliasAnalysis::pointsToConstantMemory(Loc); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); const MDNode *M = Loc.TBAATag; - if (!M) return AliasAnalysis::pointsToConstantMemory(Loc); + if (!M) return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); // If this is an "immutable" type, we can assume the pointer is pointing // to constant memory. if (TBAANode(M).TypeIsImmutable()) return true; - return AliasAnalysis::pointsToConstantMemory(Loc); + return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); } AliasAnalysis::ModRefResult diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp index 062e366158a..be5d827e8e5 100644 --- a/lib/Transforms/IPO/FunctionAttrs.cpp +++ b/lib/Transforms/IPO/FunctionAttrs.cpp @@ -66,8 +66,6 @@ namespace { CallGraphSCCPass::getAnalysisUsage(AU); } - bool PointsToLocalOrConstantMemory(Value *V); - private: AliasAnalysis *AA; }; @@ -83,53 +81,6 @@ INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } -/// PointsToLocalOrConstantMemory - Returns whether the given pointer value -/// points to memory that is local to the function, with global constants being -/// considered local to all functions. -bool FunctionAttrs::PointsToLocalOrConstantMemory(Value *V) { - SmallVector Worklist; - unsigned MaxLookup = 8; - - Worklist.push_back(V); - - do { - V = Worklist.pop_back_val()->getUnderlyingObject(); - - // An alloca instruction defines local memory. - if (isa(V)) - continue; - - // A global constant counts as local memory for our purposes. - if (GlobalVariable *GV = dyn_cast(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(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(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 CallGraphSCC &SCC) { SmallPtrSet SCCNodes; @@ -190,7 +141,7 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { CI != CE; ++CI) { Value *Arg = *CI; if (Arg->getType()->isPointerTy() && - !PointsToLocalOrConstantMemory(Arg)) + !AA->pointsToConstantMemory(Arg, /*OrLocal=*/true)) // Writes memory. Just give up. return false; } @@ -203,12 +154,14 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { } else if (LoadInst *LI = dyn_cast(I)) { // Ignore non-volatile loads from local memory. if (!LI->isVolatile() && - PointsToLocalOrConstantMemory(LI->getPointerOperand())) + AA->pointsToConstantMemory(LI->getPointerOperand(), + /*OrLocal=*/true)) continue; } else if (StoreInst *SI = dyn_cast(I)) { // Ignore non-volatile stores to local memory. if (!SI->isVolatile() && - PointsToLocalOrConstantMemory(SI->getPointerOperand())) + AA->pointsToConstantMemory(SI->getPointerOperand(), + /*OrLocal=*/true)) continue; } diff --git a/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll b/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll index 672b5e1392b..9655da45c64 100644 --- a/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll +++ b/test/Transforms/FunctionAttrs/2008-12-29-Constant.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -functionattrs -S | grep readnone +; RUN: opt < %s -basicaa -functionattrs -S | grep readnone @s = external constant i8 ; [#uses=1] -- 2.34.1