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/Analysis/AliasAnalysis.h"
27 #include "llvm/Analysis/CallGraph.h"
28 #include "llvm/Analysis/CaptureTracking.h"
29 #include "llvm/Analysis/MemoryBuiltins.h"
30 #include "llvm/ADT/SmallSet.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/ADT/UniqueVector.h"
33 #include "llvm/Support/InstIterator.h"
36 STATISTIC(NumReadNone
, "Number of functions marked readnone");
37 STATISTIC(NumReadOnly
, "Number of functions marked readonly");
38 STATISTIC(NumNoCapture
, "Number of arguments marked nocapture");
39 STATISTIC(NumNoAlias
, "Number of function returns marked noalias");
42 struct FunctionAttrs
: public CallGraphSCCPass
{
43 static char ID
; // Pass identification, replacement for typeid
44 FunctionAttrs() : CallGraphSCCPass(ID
) {}
46 // runOnSCC - Analyze the SCC, performing the transformation if possible.
47 bool runOnSCC(CallGraphSCC
&SCC
);
49 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
50 bool AddReadAttrs(const CallGraphSCC
&SCC
);
52 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
53 bool AddNoCaptureAttrs(const CallGraphSCC
&SCC
);
55 // IsFunctionMallocLike - Does this function allocate new memory?
56 bool IsFunctionMallocLike(Function
*F
,
57 SmallPtrSet
<Function
*, 8> &) const;
59 // AddNoAliasAttrs - Deduce noalias attributes for the SCC.
60 bool AddNoAliasAttrs(const CallGraphSCC
&SCC
);
62 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
64 CallGraphSCCPass::getAnalysisUsage(AU
);
67 bool PointsToLocalMemory(Value
*V
);
71 char FunctionAttrs::ID
= 0;
72 INITIALIZE_PASS(FunctionAttrs
, "functionattrs",
73 "Deduce function attributes", false, false);
75 Pass
*llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
78 /// PointsToLocalMemory - Returns whether the given pointer value points to
79 /// memory that is local to the function. Global constants are considered
80 /// local to all functions.
81 bool FunctionAttrs::PointsToLocalMemory(Value
*V
) {
82 SmallVector
<Value
*, 16> Worklist
;
83 unsigned MaxLookup
= 8;
85 Worklist
.push_back(V
);
88 V
= Worklist
.pop_back_val()->getUnderlyingObject();
90 // An alloca instruction defines local memory.
91 if (isa
<AllocaInst
>(V
))
94 // A global constant counts as local memory for our purposes.
95 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(V
)) {
96 if (!GV
->isConstant())
101 // If both select values point to local memory, then so does the select.
102 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(V
)) {
103 Worklist
.push_back(SI
->getTrueValue());
104 Worklist
.push_back(SI
->getFalseValue());
108 // If all values incoming to a phi node point to local memory, then so does
110 if (PHINode
*PN
= dyn_cast
<PHINode
>(V
)) {
111 // Don't bother inspecting phi nodes with many operands.
112 if (PN
->getNumIncomingValues() > MaxLookup
)
114 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
)
115 Worklist
.push_back(PN
->getIncomingValue(i
));
120 } while (!Worklist
.empty() && --MaxLookup
);
122 return Worklist
.empty();
125 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
126 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC
&SCC
) {
127 SmallPtrSet
<Function
*, 8> SCCNodes
;
129 // Fill SCCNodes with the elements of the SCC. Used for quickly
130 // looking up whether a given CallGraphNode is in this SCC.
131 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
)
132 SCCNodes
.insert((*I
)->getFunction());
134 // Check if any of the functions in the SCC read or write memory. If they
135 // write memory then they can't be marked readnone or readonly.
136 bool ReadsMemory
= false;
137 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
138 Function
*F
= (*I
)->getFunction();
141 // External node - may write memory. Just give up.
144 if (F
->doesNotAccessMemory())
148 // Definitions with weak linkage may be overridden at linktime with
149 // something that writes memory, so treat them like declarations.
150 if (F
->isDeclaration() || F
->mayBeOverridden()) {
151 if (!F
->onlyReadsMemory())
152 // May write memory. Just give up.
159 // Scan the function body for instructions that may read or write memory.
160 for (inst_iterator II
= inst_begin(F
), E
= inst_end(F
); II
!= E
; ++II
) {
161 Instruction
*I
= &*II
;
163 // Some instructions can be ignored even if they read or write memory.
164 // Detect these now, skipping to the next instruction if one is found.
165 CallSite
CS(cast
<Value
>(I
));
166 if (CS
&& CS
.getCalledFunction()) {
167 // Ignore calls to functions in the same SCC.
168 if (SCCNodes
.count(CS
.getCalledFunction()))
170 // Ignore intrinsics that only access local memory.
171 if (unsigned id
= CS
.getCalledFunction()->getIntrinsicID())
172 if (AliasAnalysis::getIntrinsicModRefBehavior(id
) ==
173 AliasAnalysis::AccessesArguments
) {
174 // Check that all pointer arguments point to local memory.
175 for (CallSite::arg_iterator CI
= CS
.arg_begin(), CE
= CS
.arg_end();
178 if (Arg
->getType()->isPointerTy() && !PointsToLocalMemory(Arg
))
179 // Writes memory. Just give up.
182 // Only reads and writes local memory.
185 } else if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
)) {
186 // Ignore loads from local memory.
187 if (PointsToLocalMemory(LI
->getPointerOperand()))
189 } else if (StoreInst
*SI
= dyn_cast
<StoreInst
>(I
)) {
190 // Ignore stores to local memory.
191 if (PointsToLocalMemory(SI
->getPointerOperand()))
195 // Any remaining instructions need to be taken seriously! Check if they
196 // read or write memory.
197 if (I
->mayWriteToMemory())
198 // Writes memory. Just give up.
202 // malloc claims not to write memory! PR3754.
205 // If this instruction may read memory, remember that.
206 ReadsMemory
|= I
->mayReadFromMemory();
210 // Success! Functions in this SCC do not access memory, or only read memory.
211 // Give them the appropriate attribute.
212 bool MadeChange
= false;
213 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
214 Function
*F
= (*I
)->getFunction();
216 if (F
->doesNotAccessMemory())
220 if (F
->onlyReadsMemory() && ReadsMemory
)
226 // Clear out any existing attributes.
227 F
->removeAttribute(~0, Attribute::ReadOnly
| Attribute::ReadNone
);
229 // Add in the new attribute.
230 F
->addAttribute(~0, ReadsMemory
? Attribute::ReadOnly
: Attribute::ReadNone
);
241 /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
242 bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC
&SCC
) {
243 bool Changed
= false;
245 // Check each function in turn, determining which pointer arguments are not
247 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
248 Function
*F
= (*I
)->getFunction();
251 // External node - skip it;
254 // Definitions with weak linkage may be overridden at linktime with
255 // something that writes memory, so treat them like declarations.
256 if (F
->isDeclaration() || F
->mayBeOverridden())
259 for (Function::arg_iterator A
= F
->arg_begin(), E
= F
->arg_end(); A
!=E
; ++A
)
260 if (A
->getType()->isPointerTy() && !A
->hasNoCaptureAttr() &&
261 !PointerMayBeCaptured(A
, true, /*StoreCaptures=*/false)) {
262 A
->addAttr(Attribute::NoCapture
);
271 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
272 /// or a pointer that doesn't alias any other pointer visible to the caller.
273 bool FunctionAttrs::IsFunctionMallocLike(Function
*F
,
274 SmallPtrSet
<Function
*, 8> &SCCNodes
) const {
275 UniqueVector
<Value
*> FlowsToReturn
;
276 for (Function::iterator I
= F
->begin(), E
= F
->end(); I
!= E
; ++I
)
277 if (ReturnInst
*Ret
= dyn_cast
<ReturnInst
>(I
->getTerminator()))
278 FlowsToReturn
.insert(Ret
->getReturnValue());
280 for (unsigned i
= 0; i
!= FlowsToReturn
.size(); ++i
) {
281 Value
*RetVal
= FlowsToReturn
[i
+1]; // UniqueVector[0] is reserved.
283 if (Constant
*C
= dyn_cast
<Constant
>(RetVal
)) {
284 if (!C
->isNullValue() && !isa
<UndefValue
>(C
))
290 if (isa
<Argument
>(RetVal
))
293 if (Instruction
*RVI
= dyn_cast
<Instruction
>(RetVal
))
294 switch (RVI
->getOpcode()) {
295 // Extend the analysis by looking upwards.
296 case Instruction::BitCast
:
297 case Instruction::GetElementPtr
:
298 FlowsToReturn
.insert(RVI
->getOperand(0));
300 case Instruction::Select
: {
301 SelectInst
*SI
= cast
<SelectInst
>(RVI
);
302 FlowsToReturn
.insert(SI
->getTrueValue());
303 FlowsToReturn
.insert(SI
->getFalseValue());
306 case Instruction::PHI
: {
307 PHINode
*PN
= cast
<PHINode
>(RVI
);
308 for (int i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
)
309 FlowsToReturn
.insert(PN
->getIncomingValue(i
));
313 // Check whether the pointer came from an allocation.
314 case Instruction::Alloca
:
316 case Instruction::Call
:
317 case Instruction::Invoke
: {
319 if (CS
.paramHasAttr(0, Attribute::NoAlias
))
321 if (CS
.getCalledFunction() &&
322 SCCNodes
.count(CS
.getCalledFunction()))
326 return false; // Did not come from an allocation.
329 if (PointerMayBeCaptured(RetVal
, false, /*StoreCaptures=*/false))
336 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
337 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC
&SCC
) {
338 SmallPtrSet
<Function
*, 8> SCCNodes
;
340 // Fill SCCNodes with the elements of the SCC. Used for quickly
341 // looking up whether a given CallGraphNode is in this SCC.
342 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
)
343 SCCNodes
.insert((*I
)->getFunction());
345 // Check each function in turn, determining which functions return noalias
347 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
348 Function
*F
= (*I
)->getFunction();
351 // External node - skip it;
355 if (F
->doesNotAlias(0))
358 // Definitions with weak linkage may be overridden at linktime, so
359 // treat them like declarations.
360 if (F
->isDeclaration() || F
->mayBeOverridden())
363 // We annotate noalias return values, which are only applicable to
365 if (!F
->getReturnType()->isPointerTy())
368 if (!IsFunctionMallocLike(F
, SCCNodes
))
372 bool MadeChange
= false;
373 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
374 Function
*F
= (*I
)->getFunction();
375 if (F
->doesNotAlias(0) || !F
->getReturnType()->isPointerTy())
378 F
->setDoesNotAlias(0);
386 bool FunctionAttrs::runOnSCC(CallGraphSCC
&SCC
) {
387 bool Changed
= AddReadAttrs(SCC
);
388 Changed
|= AddNoCaptureAttrs(SCC
);
389 Changed
|= AddNoAliasAttrs(SCC
);