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. It implements
13 // this as a bottom-up traversal of the call-graph.
15 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "functionattrs"
18 #include "llvm/Transforms/IPO.h"
19 #include "llvm/CallGraphSCCPass.h"
20 #include "llvm/GlobalVariable.h"
21 #include "llvm/Instructions.h"
22 #include "llvm/Analysis/CallGraph.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Support/Compiler.h"
26 #include "llvm/Support/InstIterator.h"
29 STATISTIC(NumReadNone, "Number of functions marked readnone");
30 STATISTIC(NumReadOnly, "Number of functions marked readonly");
31 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
34 struct VISIBILITY_HIDDEN FunctionAttrs : public CallGraphSCCPass {
35 static char ID; // Pass identification, replacement for typeid
36 FunctionAttrs() : CallGraphSCCPass(&ID) {}
38 // runOnSCC - Analyze the SCC, performing the transformation if possible.
39 bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
41 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
42 bool AddReadAttrs(const std::vector<CallGraphNode *> &SCC);
44 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
45 bool AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC);
47 // isCaptured - Returns whether this pointer value is captured.
48 bool isCaptured(Function &F, Value *V);
50 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
52 CallGraphSCCPass::getAnalysisUsage(AU);
55 bool PointsToLocalMemory(Value *V);
59 char FunctionAttrs::ID = 0;
60 static RegisterPass<FunctionAttrs>
61 X("functionattrs", "Deduce function attributes");
63 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
66 /// PointsToLocalMemory - Returns whether the given pointer value points to
67 /// memory that is local to the function. Global constants are considered
68 /// local to all functions.
69 bool FunctionAttrs::PointsToLocalMemory(Value *V) {
70 V = V->getUnderlyingObject();
71 // An alloca instruction defines local memory.
72 if (isa<AllocaInst>(V))
74 // A global constant counts as local memory for our purposes.
75 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
76 return GV->isConstant();
77 // Could look through phi nodes and selects here, but it doesn't seem
78 // to be useful in practice.
82 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
83 bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) {
84 SmallPtrSet<CallGraphNode*, 8> SCCNodes;
85 CallGraph &CG = getAnalysis<CallGraph>();
87 // Fill SCCNodes with the elements of the SCC. Used for quickly
88 // looking up whether a given CallGraphNode is in this SCC.
89 for (unsigned i = 0, e = SCC.size(); i != e; ++i)
90 SCCNodes.insert(SCC[i]);
92 // Check if any of the functions in the SCC read or write memory. If they
93 // write memory then they can't be marked readnone or readonly.
94 bool ReadsMemory = false;
95 for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
96 Function *F = SCC[i]->getFunction();
99 // External node - may write memory. Just give up.
102 if (F->doesNotAccessMemory())
106 // Definitions with weak linkage may be overridden at linktime with
107 // something that writes memory, so treat them like declarations.
108 if (F->isDeclaration() || F->mayBeOverridden()) {
109 if (!F->onlyReadsMemory())
110 // May write memory. Just give up.
117 // Scan the function body for instructions that may read or write memory.
118 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
119 Instruction *I = &*II;
121 // Some instructions can be ignored even if they read or write memory.
122 // Detect these now, skipping to the next instruction if one is found.
123 CallSite CS = CallSite::get(I);
124 if (CS.getInstruction()) {
125 // Ignore calls to functions in the same SCC.
126 if (SCCNodes.count(CG[CS.getCalledFunction()]))
128 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
129 // Ignore loads from local memory.
130 if (PointsToLocalMemory(LI->getPointerOperand()))
132 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
133 // Ignore stores to local memory.
134 if (PointsToLocalMemory(SI->getPointerOperand()))
138 // Any remaining instructions need to be taken seriously! Check if they
139 // read or write memory.
140 if (I->mayWriteToMemory())
141 // Writes memory. Just give up.
143 // If this instruction may read memory, remember that.
144 ReadsMemory |= I->mayReadFromMemory();
148 // Success! Functions in this SCC do not access memory, or only read memory.
149 // Give them the appropriate attribute.
150 bool MadeChange = false;
151 for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
152 Function *F = SCC[i]->getFunction();
154 if (F->doesNotAccessMemory())
158 if (F->onlyReadsMemory() && ReadsMemory)
164 // Clear out any existing attributes.
165 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone);
167 // Add in the new attribute.
168 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone);
179 /// isCaptured - Returns whether this pointer value is captured.
180 bool FunctionAttrs::isCaptured(Function &F, Value *V) {
181 SmallVector<Use*, 16> Worklist;
182 SmallPtrSet<Use*, 16> Visited;
184 for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;
186 Use *U = &UI.getUse();
188 Worklist.push_back(U);
191 while (!Worklist.empty()) {
192 Use *U = Worklist.pop_back_val();
193 Instruction *I = cast<Instruction>(U->getUser());
196 if (isa<LoadInst>(I)) {
197 // Loading a pointer does not cause it to escape.
201 if (isa<StoreInst>(I)) {
202 if (V == I->getOperand(0))
203 // Stored the pointer - escapes. TODO: improve this.
205 // Storing to the pointee does not cause the pointer to escape.
209 CallSite CS = CallSite::get(I);
210 if (CS.getInstruction()) {
211 // Does not escape if only passed via 'nocapture' arguments. Note
212 // that calling a function pointer does not in itself cause that
213 // function pointer to escape. This is a subtle point considering
214 // that (for example) the callee might return its own address. It
215 // is analogous to saying that loading a value from a pointer does
216 // not cause the pointer to escape, even though the loaded value
217 // might be the pointer itself (think of self-referential objects).
218 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
219 for (CallSite::arg_iterator A = B; A != E; ++A)
220 if (A->get() == V && !CS.paramHasAttr(A-B+1, Attribute::NoCapture))
221 // The parameter is not marked 'nocapture' - escapes.
223 // Only passed via 'nocapture' arguments, or is the called function.
228 if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) {
229 // Type conversion or calculating an offset. Does not escape if the new
231 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
233 Use *U = &UI.getUse();
234 if (Visited.insert(U))
235 Worklist.push_back(U);
240 // Something else - be conservative and say it escapes.
247 /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
248 bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) {
249 bool Changed = false;
251 // Check each function in turn, determining which pointer arguments are not
253 for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
254 Function *F = SCC[i]->getFunction();
257 // External node - skip it;
260 // Definitions with weak linkage may be overridden at linktime with
261 // something that writes memory, so treat them like declarations.
262 if (F->isDeclaration() || F->mayBeOverridden())
265 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A)
266 if (isa<PointerType>(A->getType()) && !isCaptured(*F, A)) {
267 A->addAttr(Attribute::NoCapture);
276 bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
277 bool Changed = AddReadAttrs(SCC);
278 Changed |= AddNoCaptureAttrs(SCC);