FunctionAttrs.cpp revision 338cd6ba6e36c291185541bb8e391427f57a32b1
1//===- FunctionAttrs.cpp - Pass which marks functions readnone or readonly ===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 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. 18// 19//===----------------------------------------------------------------------===// 20 21#define DEBUG_TYPE "functionattrs" 22#include "llvm/Transforms/IPO.h" 23#include "llvm/CallGraphSCCPass.h" 24#include "llvm/GlobalVariable.h" 25#include "llvm/Instructions.h" 26#include "llvm/Analysis/CallGraph.h" 27#include "llvm/ADT/PointerIntPair.h" 28#include "llvm/ADT/SmallSet.h" 29#include "llvm/ADT/Statistic.h" 30#include "llvm/Support/Compiler.h" 31#include "llvm/Support/InstIterator.h" 32using namespace llvm; 33 34STATISTIC(NumReadNone, "Number of functions marked readnone"); 35STATISTIC(NumReadOnly, "Number of functions marked readonly"); 36STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 37 38namespace { 39 struct VISIBILITY_HIDDEN FunctionAttrs : public CallGraphSCCPass { 40 static char ID; // Pass identification, replacement for typeid 41 FunctionAttrs() : CallGraphSCCPass(&ID) {} 42 43 // runOnSCC - Analyze the SCC, performing the transformation if possible. 44 bool runOnSCC(const std::vector<CallGraphNode *> &SCC); 45 46 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 47 bool AddReadAttrs(const std::vector<CallGraphNode *> &SCC); 48 49 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 50 bool AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC); 51 52 // isCaptured - Return true if this pointer value may be captured. 53 bool isCaptured(Function &F, Value *V); 54 55 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 56 AU.setPreservesCFG(); 57 CallGraphSCCPass::getAnalysisUsage(AU); 58 } 59 60 bool PointsToLocalMemory(Value *V); 61 }; 62} 63 64char FunctionAttrs::ID = 0; 65static RegisterPass<FunctionAttrs> 66X("functionattrs", "Deduce function attributes"); 67 68Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 69 70 71/// PointsToLocalMemory - Returns whether the given pointer value points to 72/// memory that is local to the function. Global constants are considered 73/// local to all functions. 74bool FunctionAttrs::PointsToLocalMemory(Value *V) { 75 V = V->getUnderlyingObject(); 76 // An alloca instruction defines local memory. 77 if (isa<AllocaInst>(V)) 78 return true; 79 // A global constant counts as local memory for our purposes. 80 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 81 return GV->isConstant(); 82 // Could look through phi nodes and selects here, but it doesn't seem 83 // to be useful in practice. 84 return false; 85} 86 87/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 88bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) { 89 SmallPtrSet<CallGraphNode*, 8> SCCNodes; 90 CallGraph &CG = getAnalysis<CallGraph>(); 91 92 // Fill SCCNodes with the elements of the SCC. Used for quickly 93 // looking up whether a given CallGraphNode is in this SCC. 94 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 95 SCCNodes.insert(SCC[i]); 96 97 // Check if any of the functions in the SCC read or write memory. If they 98 // write memory then they can't be marked readnone or readonly. 99 bool ReadsMemory = false; 100 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 101 Function *F = SCC[i]->getFunction(); 102 103 if (F == 0) 104 // External node - may write memory. Just give up. 105 return false; 106 107 if (F->doesNotAccessMemory()) 108 // Already perfect! 109 continue; 110 111 // Definitions with weak linkage may be overridden at linktime with 112 // something that writes memory, so treat them like declarations. 113 if (F->isDeclaration() || F->mayBeOverridden()) { 114 if (!F->onlyReadsMemory()) 115 // May write memory. Just give up. 116 return false; 117 118 ReadsMemory = true; 119 continue; 120 } 121 122 // Scan the function body for instructions that may read or write memory. 123 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 124 Instruction *I = &*II; 125 126 // Some instructions can be ignored even if they read or write memory. 127 // Detect these now, skipping to the next instruction if one is found. 128 CallSite CS = CallSite::get(I); 129 if (CS.getInstruction()) { 130 // Ignore calls to functions in the same SCC. 131 if (SCCNodes.count(CG[CS.getCalledFunction()])) 132 continue; 133 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 134 // Ignore loads from local memory. 135 if (PointsToLocalMemory(LI->getPointerOperand())) 136 continue; 137 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 138 // Ignore stores to local memory. 139 if (PointsToLocalMemory(SI->getPointerOperand())) 140 continue; 141 } 142 143 // Any remaining instructions need to be taken seriously! Check if they 144 // read or write memory. 145 if (I->mayWriteToMemory()) 146 // Writes memory. Just give up. 147 return false; 148 // If this instruction may read memory, remember that. 149 ReadsMemory |= I->mayReadFromMemory(); 150 } 151 } 152 153 // Success! Functions in this SCC do not access memory, or only read memory. 154 // Give them the appropriate attribute. 155 bool MadeChange = false; 156 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 157 Function *F = SCC[i]->getFunction(); 158 159 if (F->doesNotAccessMemory()) 160 // Already perfect! 161 continue; 162 163 if (F->onlyReadsMemory() && ReadsMemory) 164 // No change. 165 continue; 166 167 MadeChange = true; 168 169 // Clear out any existing attributes. 170 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 171 172 // Add in the new attribute. 173 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 174 175 if (ReadsMemory) 176 ++NumReadOnly; 177 else 178 ++NumReadNone; 179 } 180 181 return MadeChange; 182} 183 184/// isCaptured - Return true if this pointer value may be captured. 185bool FunctionAttrs::isCaptured(Function &F, Value *V) { 186 typedef PointerIntPair<Use*, 2> UseWithDepth; 187 SmallVector<UseWithDepth, 16> Worklist; 188 SmallSet<UseWithDepth, 16> Visited; 189 190 for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; 191 ++UI) { 192 UseWithDepth UD(&UI.getUse(), 0); 193 Visited.insert(UD); 194 Worklist.push_back(UD); 195 } 196 197 while (!Worklist.empty()) { 198 UseWithDepth UD = Worklist.pop_back_val(); 199 Use *U = UD.getPointer(); 200 Instruction *I = cast<Instruction>(U->getUser()); 201 V = U->get(); 202 // The depth represents the number of loads that need to be performed to 203 // get back the original pointer (or a bitcast etc of it). For example, 204 // if the pointer is stored to an alloca, then all uses of the alloca get 205 // depth 1: if the alloca is loaded then you get the original pointer back. 206 // If a load of the alloca is returned then the pointer has been captured. 207 // The depth is needed in order to know which loads dereference the original 208 // pointer (these do not capture), and which return a value which needs to 209 // be tracked because if it is captured then so is the original pointer. 210 unsigned Depth = UD.getInt(); 211 212 if (isa<StoreInst>(I)) { 213 if (V == I->getOperand(0)) { 214 // Stored the pointer - it may be captured. If it is stored to a local 215 // object (alloca) then track that object. Otherwise give up. 216 Value *Target = I->getOperand(1)->getUnderlyingObject(); 217 if (!isa<AllocaInst>(Target)) 218 // Didn't store to an obviously local object - captured. 219 return true; 220 if (Depth >= 3) 221 // Alloca recursion too deep - give up. 222 return true; 223 // Analyze all uses of the alloca. 224 for (Value::use_iterator UI = Target->use_begin(), 225 UE = Target->use_end(); UI != UE; ++UI) { 226 UseWithDepth NUD(&UI.getUse(), Depth + 1); 227 if (Visited.insert(NUD)) 228 Worklist.push_back(NUD); 229 } 230 } 231 // Storing to the pointee does not cause the pointer to be captured. 232 } else if (isa<FreeInst>(I)) { 233 // Freeing a pointer does not cause it to be captured. 234 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 235 CallSite CS = CallSite::get(I); 236 // Not captured if the callee is readonly and doesn't return a copy 237 // through its return value. 238 if (CS.onlyReadsMemory() && I->getType() == Type::VoidTy) 239 continue; 240 241 // Not captured if only passed via 'nocapture' arguments. Note that 242 // calling a function pointer does not in itself cause the pointer to 243 // be captured. This is a subtle point considering that (for example) 244 // the callee might return its own address. It is analogous to saying 245 // that loading a value from a pointer does not cause the pointer to be 246 // captured, even though the loaded value might be the pointer itself 247 // (think of self-referential objects). 248 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 249 for (CallSite::arg_iterator A = B; A != E; ++A) 250 if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) 251 // The parameter is not marked 'nocapture' - captured. 252 return true; 253 // Only passed via 'nocapture' arguments, or is the called function - not 254 // captured. 255 } else if (isa<BitCastInst>(I) || isa<LoadInst>(I) || isa<PHINode>(I) || 256 isa<GetElementPtrInst>(I) || isa<SelectInst>(I)) { 257 258 // Usually loads can be ignored because they dereference the original 259 // pointer. However the loaded value needs to be tracked if loading 260 // from an object that the original pointer was stored to. 261 if (isa<LoadInst>(I)) { 262 if (Depth == 0) 263 // Loading the original pointer or a variation of it. This does not 264 // cause the pointer to be captured. Note that the loaded value might 265 // be the pointer itself (think of self-referential objects), but that 266 // is fine as long as it's not this function that stored it there. 267 continue; 268 // Loading a pointer to (a pointer to...) the original pointer or a 269 // variation of it. Track uses of the loaded value, noting that one 270 // dereference was performed. 271 --Depth; 272 } 273 274 // The original value is not captured via this if the instruction isn't. 275 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 276 UI != UE; ++UI) { 277 UseWithDepth UD(&UI.getUse(), Depth); 278 if (Visited.insert(UD)) 279 Worklist.push_back(UD); 280 } 281 } else { 282 // Something else - be conservative and say it is captured. 283 return true; 284 } 285 } 286 287 // All uses examined - not captured. 288 return false; 289} 290 291/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 292bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) { 293 bool Changed = false; 294 295 // Check each function in turn, determining which pointer arguments are not 296 // captured. 297 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 298 Function *F = SCC[i]->getFunction(); 299 300 if (F == 0) 301 // External node - skip it; 302 continue; 303 304 // If the function is readonly and doesn't return any value, we know that 305 // the pointer value is not captured. Mark all of its pointer arguments 306 // nocapture. 307 if (F->onlyReadsMemory() && F->getReturnType() == Type::VoidTy) { 308 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); 309 A != E; ++A) 310 if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr()) { 311 A->addAttr(Attribute::NoCapture); 312 ++NumNoCapture; 313 Changed = true; 314 } 315 continue; 316 } 317 318 // Definitions with weak linkage may be overridden at linktime with 319 // something that writes memory, so treat them like declarations. 320 if (F->isDeclaration() || F->mayBeOverridden()) 321 continue; 322 323 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 324 if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr() && 325 !isCaptured(*F, A)) { 326 A->addAttr(Attribute::NoCapture); 327 ++NumNoCapture; 328 Changed = true; 329 } 330 } 331 332 return Changed; 333} 334 335bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 336 bool Changed = AddReadAttrs(SCC); 337 Changed |= AddNoCaptureAttrs(SCC); 338 return Changed; 339} 340