1 //===- FunctionAttrs.cpp - Pass which marks functions readnone or readonly ===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a simple interprocedural pass which walks the
11 // call-graph, looking for functions which do not access or only read
12 // non-local memory, and marking them readnone/readonly. In addition,
13 // it marks function arguments (of pointer type) 'nocapture' if a call
14 // to the function does not create any copies of the pointer value that
15 // outlive the call. This more or less means that the pointer is only
16 // dereferenced, and not returned from the function or stored in a global.
17 // This pass is implemented as a bottom-up traversal of the call-graph.
19 //===----------------------------------------------------------------------===//
21 #define DEBUG_TYPE "functionattrs"
22 #include "llvm/Transforms/IPO.h"
23 #include "llvm/CallGraphSCCPass.h"
24 #include "llvm/GlobalVariable.h"
25 #include "llvm/IntrinsicInst.h"
26 #include "llvm/LLVMContext.h"
27 #include "llvm/Analysis/AliasAnalysis.h"
28 #include "llvm/Analysis/CallGraph.h"
29 #include "llvm/Analysis/CaptureTracking.h"
30 #include "llvm/ADT/SCCIterator.h"
31 #include "llvm/ADT/SmallSet.h"
32 #include "llvm/ADT/Statistic.h"
33 #include "llvm/ADT/UniqueVector.h"
34 #include "llvm/Support/InstIterator.h"
37 STATISTIC(NumReadNone
, "Number of functions marked readnone");
38 STATISTIC(NumReadOnly
, "Number of functions marked readonly");
39 STATISTIC(NumNoCapture
, "Number of arguments marked nocapture");
40 STATISTIC(NumNoAlias
, "Number of function returns marked noalias");
43 struct FunctionAttrs
: public CallGraphSCCPass
{
44 static char ID
; // Pass identification, replacement for typeid
45 FunctionAttrs() : CallGraphSCCPass(ID
), AA(0) {
46 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
49 // runOnSCC - Analyze the SCC, performing the transformation if possible.
50 bool runOnSCC(CallGraphSCC
&SCC
);
52 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
53 bool AddReadAttrs(const CallGraphSCC
&SCC
);
55 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
56 bool AddNoCaptureAttrs(const CallGraphSCC
&SCC
);
58 // IsFunctionMallocLike - Does this function allocate new memory?
59 bool IsFunctionMallocLike(Function
*F
,
60 SmallPtrSet
<Function
*, 8> &) const;
62 // AddNoAliasAttrs - Deduce noalias attributes for the SCC.
63 bool AddNoAliasAttrs(const CallGraphSCC
&SCC
);
65 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
67 AU
.addRequired
<AliasAnalysis
>();
68 CallGraphSCCPass::getAnalysisUsage(AU
);
76 char FunctionAttrs::ID
= 0;
77 INITIALIZE_PASS_BEGIN(FunctionAttrs
, "functionattrs",
78 "Deduce function attributes", false, false)
79 INITIALIZE_AG_DEPENDENCY(CallGraph
)
80 INITIALIZE_PASS_END(FunctionAttrs
, "functionattrs",
81 "Deduce function attributes", false, false)
83 Pass
*llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
86 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
87 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC
&SCC
) {
88 SmallPtrSet
<Function
*, 8> SCCNodes
;
90 // Fill SCCNodes with the elements of the SCC. Used for quickly
91 // looking up whether a given CallGraphNode is in this SCC.
92 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
)
93 SCCNodes
.insert((*I
)->getFunction());
95 // Check if any of the functions in the SCC read or write memory. If they
96 // write memory then they can't be marked readnone or readonly.
97 bool ReadsMemory
= false;
98 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
99 Function
*F
= (*I
)->getFunction();
102 // External node - may write memory. Just give up.
105 AliasAnalysis::ModRefBehavior MRB
= AA
->getModRefBehavior(F
);
106 if (MRB
== AliasAnalysis::DoesNotAccessMemory
)
110 // Definitions with weak linkage may be overridden at linktime with
111 // something that writes memory, so treat them like declarations.
112 if (F
->isDeclaration() || F
->mayBeOverridden()) {
113 if (!AliasAnalysis::onlyReadsMemory(MRB
))
114 // May write memory. Just give up.
121 // Scan the function body for instructions that may read or write memory.
122 for (inst_iterator II
= inst_begin(F
), E
= inst_end(F
); II
!= E
; ++II
) {
123 Instruction
*I
= &*II
;
125 // Some instructions can be ignored even if they read or write memory.
126 // Detect these now, skipping to the next instruction if one is found.
127 CallSite
CS(cast
<Value
>(I
));
129 // Ignore calls to functions in the same SCC.
130 if (CS
.getCalledFunction() && SCCNodes
.count(CS
.getCalledFunction()))
132 AliasAnalysis::ModRefBehavior MRB
= AA
->getModRefBehavior(CS
);
133 // If the call doesn't access arbitrary memory, we may be able to
134 // figure out something.
135 if (AliasAnalysis::onlyAccessesArgPointees(MRB
)) {
136 // If the call does access argument pointees, check each argument.
137 if (AliasAnalysis::doesAccessArgPointees(MRB
))
138 // Check whether all pointer arguments point to local memory, and
139 // ignore calls that only access local memory.
140 for (CallSite::arg_iterator CI
= CS
.arg_begin(), CE
= CS
.arg_end();
143 if (Arg
->getType()->isPointerTy()) {
144 AliasAnalysis::Location
Loc(Arg
,
145 AliasAnalysis::UnknownSize
,
146 I
->getMetadata(LLVMContext::MD_tbaa
));
147 if (!AA
->pointsToConstantMemory(Loc
, /*OrLocal=*/true)) {
148 if (MRB
& AliasAnalysis::Mod
)
149 // Writes non-local memory. Give up.
151 if (MRB
& AliasAnalysis::Ref
)
152 // Ok, it reads non-local memory.
159 // The call could access any memory. If that includes writes, give up.
160 if (MRB
& AliasAnalysis::Mod
)
162 // If it reads, note it.
163 if (MRB
& AliasAnalysis::Ref
)
166 } else if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
)) {
167 // Ignore non-volatile loads from local memory. (Atomic is okay here.)
168 if (!LI
->isVolatile()) {
169 AliasAnalysis::Location Loc
= AA
->getLocation(LI
);
170 if (AA
->pointsToConstantMemory(Loc
, /*OrLocal=*/true))
173 } else if (StoreInst
*SI
= dyn_cast
<StoreInst
>(I
)) {
174 // Ignore non-volatile stores to local memory. (Atomic is okay here.)
175 if (!SI
->isVolatile()) {
176 AliasAnalysis::Location Loc
= AA
->getLocation(SI
);
177 if (AA
->pointsToConstantMemory(Loc
, /*OrLocal=*/true))
180 } else if (VAArgInst
*VI
= dyn_cast
<VAArgInst
>(I
)) {
181 // Ignore vaargs on local memory.
182 AliasAnalysis::Location Loc
= AA
->getLocation(VI
);
183 if (AA
->pointsToConstantMemory(Loc
, /*OrLocal=*/true))
187 // Any remaining instructions need to be taken seriously! Check if they
188 // read or write memory.
189 if (I
->mayWriteToMemory())
190 // Writes memory. Just give up.
193 // If this instruction may read memory, remember that.
194 ReadsMemory
|= I
->mayReadFromMemory();
198 // Success! Functions in this SCC do not access memory, or only read memory.
199 // Give them the appropriate attribute.
200 bool MadeChange
= false;
201 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
202 Function
*F
= (*I
)->getFunction();
204 if (F
->doesNotAccessMemory())
208 if (F
->onlyReadsMemory() && ReadsMemory
)
214 // Clear out any existing attributes.
215 F
->removeAttribute(~0, Attribute::ReadOnly
| Attribute::ReadNone
);
217 // Add in the new attribute.
218 F
->addAttribute(~0, ReadsMemory
? Attribute::ReadOnly
: Attribute::ReadNone
);
230 // For a given pointer Argument, this retains a list of Arguments of functions
231 // in the same SCC that the pointer data flows into. We use this to build an
232 // SCC of the arguments.
233 struct ArgumentGraphNode
{
234 Argument
*Definition
;
235 SmallVector
<ArgumentGraphNode
*, 4> Uses
;
238 class ArgumentGraph
{
239 // We store pointers to ArgumentGraphNode objects, so it's important that
240 // that they not move around upon insert.
241 typedef std::map
<Argument
*, ArgumentGraphNode
> ArgumentMapTy
;
243 ArgumentMapTy ArgumentMap
;
245 // There is no root node for the argument graph, in fact:
246 // void f(int *x, int *y) { if (...) f(x, y); }
247 // is an example where the graph is disconnected. The SCCIterator requires a
248 // single entry point, so we maintain a fake ("synthetic") root node that
249 // uses every node. Because the graph is directed and nothing points into
250 // the root, it will not participate in any SCCs (except for its own).
251 ArgumentGraphNode SyntheticRoot
;
254 ArgumentGraph() { SyntheticRoot
.Definition
= 0; }
256 typedef SmallVectorImpl
<ArgumentGraphNode
*>::iterator iterator
;
258 iterator
begin() { return SyntheticRoot
.Uses
.begin(); }
259 iterator
end() { return SyntheticRoot
.Uses
.end(); }
260 ArgumentGraphNode
*getEntryNode() { return &SyntheticRoot
; }
262 ArgumentGraphNode
*operator[](Argument
*A
) {
263 ArgumentGraphNode
&Node
= ArgumentMap
[A
];
265 SyntheticRoot
.Uses
.push_back(&Node
);
270 // This tracker checks whether callees are in the SCC, and if so it does not
271 // consider that a capture, instead adding it to the "Uses" list and
272 // continuing with the analysis.
273 struct ArgumentUsesTracker
: public CaptureTracker
{
274 ArgumentUsesTracker(const SmallPtrSet
<Function
*, 8> &SCCNodes
)
275 : Captured(false), SCCNodes(SCCNodes
) {}
277 void tooManyUses() { Captured
= true; }
279 bool shouldExplore(Use
*U
) { return true; }
281 bool captured(Use
*U
) {
282 CallSite
CS(U
->getUser());
283 if (!CS
.getInstruction()) { Captured
= true; return true; }
285 Function
*F
= CS
.getCalledFunction();
286 if (!F
|| !SCCNodes
.count(F
)) { Captured
= true; return true; }
288 Function::arg_iterator AI
= F
->arg_begin(), AE
= F
->arg_end();
289 for (CallSite::arg_iterator PI
= CS
.arg_begin(), PE
= CS
.arg_end();
290 PI
!= PE
; ++PI
, ++AI
) {
292 assert(F
->isVarArg() && "More params than args in non-varargs call");
301 assert(!Uses
.empty() && "Capturing call-site captured nothing?");
305 bool Captured
; // True only if certainly captured (used outside our SCC).
306 SmallVector
<Argument
*, 4> Uses
; // Uses within our SCC.
308 const SmallPtrSet
<Function
*, 8> &SCCNodes
;
313 template<> struct GraphTraits
<ArgumentGraphNode
*> {
314 typedef ArgumentGraphNode NodeType
;
315 typedef SmallVectorImpl
<ArgumentGraphNode
*>::iterator ChildIteratorType
;
317 static inline NodeType
*getEntryNode(NodeType
*A
) { return A
; }
318 static inline ChildIteratorType
child_begin(NodeType
*N
) {
319 return N
->Uses
.begin();
321 static inline ChildIteratorType
child_end(NodeType
*N
) {
322 return N
->Uses
.end();
325 template<> struct GraphTraits
<ArgumentGraph
*>
326 : public GraphTraits
<ArgumentGraphNode
*> {
327 static NodeType
*getEntryNode(ArgumentGraph
*AG
) {
328 return AG
->getEntryNode();
330 static ChildIteratorType
nodes_begin(ArgumentGraph
*AG
) {
333 static ChildIteratorType
nodes_end(ArgumentGraph
*AG
) {
339 /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
340 bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC
&SCC
) {
341 bool Changed
= false;
343 SmallPtrSet
<Function
*, 8> SCCNodes
;
345 // Fill SCCNodes with the elements of the SCC. Used for quickly
346 // looking up whether a given CallGraphNode is in this SCC.
347 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
348 Function
*F
= (*I
)->getFunction();
349 if (F
&& !F
->isDeclaration() && !F
->mayBeOverridden())
355 // Check each function in turn, determining which pointer arguments are not
357 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
358 Function
*F
= (*I
)->getFunction();
361 // External node - only a problem for arguments that we pass to it.
364 // Definitions with weak linkage may be overridden at linktime with
365 // something that captures pointers, so treat them like declarations.
366 if (F
->isDeclaration() || F
->mayBeOverridden())
369 // Functions that are readonly (or readnone) and nounwind and don't return
370 // a value can't capture arguments. Don't analyze them.
371 if (F
->onlyReadsMemory() && F
->doesNotThrow() &&
372 F
->getReturnType()->isVoidTy()) {
373 for (Function::arg_iterator A
= F
->arg_begin(), E
= F
->arg_end();
375 if (A
->getType()->isPointerTy() && !A
->hasNoCaptureAttr()) {
376 A
->addAttr(Attribute::NoCapture
);
384 for (Function::arg_iterator A
= F
->arg_begin(), E
= F
->arg_end(); A
!=E
; ++A
)
385 if (A
->getType()->isPointerTy() && !A
->hasNoCaptureAttr()) {
386 ArgumentUsesTracker
Tracker(SCCNodes
);
387 PointerMayBeCaptured(A
, &Tracker
);
388 if (!Tracker
.Captured
) {
389 if (Tracker
.Uses
.empty()) {
390 // If it's trivially not captured, mark it nocapture now.
391 A
->addAttr(Attribute::NoCapture
);
395 // If it's not trivially captured and not trivially not captured,
396 // then it must be calling into another function in our SCC. Save
397 // its particulars for Argument-SCC analysis later.
398 ArgumentGraphNode
*Node
= AG
[A
];
399 for (SmallVectorImpl
<Argument
*>::iterator UI
= Tracker
.Uses
.begin(),
400 UE
= Tracker
.Uses
.end(); UI
!= UE
; ++UI
)
401 Node
->Uses
.push_back(AG
[*UI
]);
404 // Otherwise, it's captured. Don't bother doing SCC analysis on it.
408 // The graph we've collected is partial because we stopped scanning for
409 // argument uses once we solved the argument trivially. These partial nodes
410 // show up as ArgumentGraphNode objects with an empty Uses list, and for
411 // these nodes the final decision about whether they capture has already been
412 // made. If the definition doesn't have a 'nocapture' attribute by now, it
415 for (scc_iterator
<ArgumentGraph
*> I
= scc_begin(&AG
), E
= scc_end(&AG
);
417 std::vector
<ArgumentGraphNode
*> &ArgumentSCC
= *I
;
418 if (ArgumentSCC
.size() == 1) {
419 if (!ArgumentSCC
[0]->Definition
) continue; // synthetic root node
421 // eg. "void f(int* x) { if (...) f(x); }"
422 if (ArgumentSCC
[0]->Uses
.size() == 1 &&
423 ArgumentSCC
[0]->Uses
[0] == ArgumentSCC
[0]) {
424 ArgumentSCC
[0]->Definition
->addAttr(Attribute::NoCapture
);
431 bool SCCCaptured
= false;
432 for (std::vector
<ArgumentGraphNode
*>::iterator I
= ArgumentSCC
.begin(),
433 E
= ArgumentSCC
.end(); I
!= E
&& !SCCCaptured
; ++I
) {
434 ArgumentGraphNode
*Node
= *I
;
435 if (Node
->Uses
.empty()) {
436 if (!Node
->Definition
->hasNoCaptureAttr())
440 if (SCCCaptured
) continue;
442 SmallPtrSet
<Argument
*, 8> ArgumentSCCNodes
;
443 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for
444 // quickly looking up whether a given Argument is in this ArgumentSCC.
445 for (std::vector
<ArgumentGraphNode
*>::iterator I
= ArgumentSCC
.begin(),
446 E
= ArgumentSCC
.end(); I
!= E
; ++I
) {
447 ArgumentSCCNodes
.insert((*I
)->Definition
);
450 for (std::vector
<ArgumentGraphNode
*>::iterator I
= ArgumentSCC
.begin(),
451 E
= ArgumentSCC
.end(); I
!= E
&& !SCCCaptured
; ++I
) {
452 ArgumentGraphNode
*N
= *I
;
453 for (SmallVectorImpl
<ArgumentGraphNode
*>::iterator UI
= N
->Uses
.begin(),
454 UE
= N
->Uses
.end(); UI
!= UE
; ++UI
) {
455 Argument
*A
= (*UI
)->Definition
;
456 if (A
->hasNoCaptureAttr() || ArgumentSCCNodes
.count(A
))
462 if (SCCCaptured
) continue;
464 for (unsigned i
= 0, e
= ArgumentSCC
.size(); i
!= e
; ++i
) {
465 Argument
*A
= ArgumentSCC
[i
]->Definition
;
466 A
->addAttr(Attribute::NoCapture
);
475 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
476 /// or a pointer that doesn't alias any other pointer visible to the caller.
477 bool FunctionAttrs::IsFunctionMallocLike(Function
*F
,
478 SmallPtrSet
<Function
*, 8> &SCCNodes
) const {
479 UniqueVector
<Value
*> FlowsToReturn
;
480 for (Function::iterator I
= F
->begin(), E
= F
->end(); I
!= E
; ++I
)
481 if (ReturnInst
*Ret
= dyn_cast
<ReturnInst
>(I
->getTerminator()))
482 FlowsToReturn
.insert(Ret
->getReturnValue());
484 for (unsigned i
= 0; i
!= FlowsToReturn
.size(); ++i
) {
485 Value
*RetVal
= FlowsToReturn
[i
+1]; // UniqueVector[0] is reserved.
487 if (Constant
*C
= dyn_cast
<Constant
>(RetVal
)) {
488 if (!C
->isNullValue() && !isa
<UndefValue
>(C
))
494 if (isa
<Argument
>(RetVal
))
497 if (Instruction
*RVI
= dyn_cast
<Instruction
>(RetVal
))
498 switch (RVI
->getOpcode()) {
499 // Extend the analysis by looking upwards.
500 case Instruction::BitCast
:
501 case Instruction::GetElementPtr
:
502 FlowsToReturn
.insert(RVI
->getOperand(0));
504 case Instruction::Select
: {
505 SelectInst
*SI
= cast
<SelectInst
>(RVI
);
506 FlowsToReturn
.insert(SI
->getTrueValue());
507 FlowsToReturn
.insert(SI
->getFalseValue());
510 case Instruction::PHI
: {
511 PHINode
*PN
= cast
<PHINode
>(RVI
);
512 for (int i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
)
513 FlowsToReturn
.insert(PN
->getIncomingValue(i
));
517 // Check whether the pointer came from an allocation.
518 case Instruction::Alloca
:
520 case Instruction::Call
:
521 case Instruction::Invoke
: {
523 if (CS
.paramHasAttr(0, Attribute::NoAlias
))
525 if (CS
.getCalledFunction() &&
526 SCCNodes
.count(CS
.getCalledFunction()))
530 return false; // Did not come from an allocation.
533 if (PointerMayBeCaptured(RetVal
, false, /*StoreCaptures=*/false))
540 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
541 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC
&SCC
) {
542 SmallPtrSet
<Function
*, 8> SCCNodes
;
544 // Fill SCCNodes with the elements of the SCC. Used for quickly
545 // looking up whether a given CallGraphNode is in this SCC.
546 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
)
547 SCCNodes
.insert((*I
)->getFunction());
549 // Check each function in turn, determining which functions return noalias
551 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
552 Function
*F
= (*I
)->getFunction();
555 // External node - skip it;
559 if (F
->doesNotAlias(0))
562 // Definitions with weak linkage may be overridden at linktime, so
563 // treat them like declarations.
564 if (F
->isDeclaration() || F
->mayBeOverridden())
567 // We annotate noalias return values, which are only applicable to
569 if (!F
->getReturnType()->isPointerTy())
572 if (!IsFunctionMallocLike(F
, SCCNodes
))
576 bool MadeChange
= false;
577 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
578 Function
*F
= (*I
)->getFunction();
579 if (F
->doesNotAlias(0) || !F
->getReturnType()->isPointerTy())
582 F
->setDoesNotAlias(0);
590 bool FunctionAttrs::runOnSCC(CallGraphSCC
&SCC
) {
591 AA
= &getAnalysis
<AliasAnalysis
>();
593 bool Changed
= AddReadAttrs(SCC
);
594 Changed
|= AddNoCaptureAttrs(SCC
);
595 Changed
|= AddNoAliasAttrs(SCC
);