FunctionAttrs.cpp revision 2265b0cc728e76b5846ee92dc0a049d916b87134
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 // The value V may have any type if it comes from tracking a load. 202 V = U->get(); 203 // The depth represents the number of loads that need to be performed to 204 // get back the original pointer (or a bitcast etc of it). For example, 205 // if the pointer is stored to an alloca, then all uses of the alloca get 206 // depth 1: if the alloca is loaded then you get the original pointer back. 207 // If a load of the alloca is returned then the pointer has been captured. 208 // The depth is needed in order to know which loads dereference the original 209 // pointer (these do not capture), and which return a value which needs to 210 // be tracked because if it is captured then so is the original pointer. 211 unsigned Depth = UD.getInt(); 212 213 switch (I->getOpcode()) { 214 case Instruction::Call: 215 case Instruction::Invoke: { 216 CallSite CS = CallSite::get(I); 217 // Not captured if the callee is readonly and doesn't return a copy 218 // through its return value. 219 if (CS.onlyReadsMemory() && I->getType() == Type::VoidTy) 220 break; 221 222 // Not captured if only passed via 'nocapture' arguments. Note that 223 // calling a function pointer does not in itself cause the pointer to 224 // be captured. This is a subtle point considering that (for example) 225 // the callee might return its own address. It is analogous to saying 226 // that loading a value from a pointer does not cause the pointer to be 227 // captured, even though the loaded value might be the pointer itself 228 // (think of self-referential objects). 229 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 230 for (CallSite::arg_iterator A = B; A != E; ++A) 231 if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) 232 // The parameter is not marked 'nocapture' - captured. 233 return true; 234 // Only passed via 'nocapture' arguments, or is the called function - not 235 // captured. 236 break; 237 } 238 case Instruction::Free: 239 // Freeing a pointer does not cause it to be captured. 240 break; 241 case Instruction::Store: 242 if (V == I->getOperand(0)) { 243 // Stored the pointer - it may be captured. If it is stored to a local 244 // object (alloca) then track that object. Otherwise give up. 245 Value *Target = I->getOperand(1)->getUnderlyingObject(); 246 if (!isa<AllocaInst>(Target)) 247 // Didn't store to an obviously local object - captured. 248 return true; 249 if (Depth >= 3) 250 // Alloca recursion too deep - give up. 251 return true; 252 // Analyze all uses of the alloca. 253 for (Value::use_iterator UI = Target->use_begin(), 254 UE = Target->use_end(); UI != UE; ++UI) { 255 UseWithDepth NUD(&UI.getUse(), Depth + 1); 256 if (Visited.insert(NUD)) 257 Worklist.push_back(NUD); 258 } 259 } 260 // Storing to the pointee does not cause the pointer to be captured. 261 break; 262 case Instruction::BitCast: 263 case Instruction::GetElementPtr: 264 case Instruction::Load: 265 case Instruction::PHI: 266 case Instruction::Select: 267 // Track any uses of this instruction to see if they are captured. 268 // First handle any special cases. 269 if (isa<GetElementPtrInst>(I)) { 270 // Play safe and do not accept being used as an index. 271 if (V != I->getOperand(0)) 272 return true; 273 } else if (isa<SelectInst>(I)) { 274 // Play safe and do not accept being used as the condition. 275 if (V == I->getOperand(0)) 276 return true; 277 } else if (isa<LoadInst>(I)) { 278 // Usually loads can be ignored because they dereference the original 279 // pointer. However the loaded value needs to be tracked if loading 280 // from an object that the original pointer was stored to. 281 if (Depth == 0) 282 // Loading the original pointer or a variation of it. This does not 283 // cause the pointer to be captured. Note that the loaded value might 284 // be the pointer itself (think of self-referential objects), but that 285 // is fine as long as it's not this function that stored it there. 286 break; 287 // Loading a pointer to (a pointer to...) the original pointer or a 288 // variation of it. Track uses of the loaded value, noting that one 289 // dereference was performed. Note that the loaded value need not be 290 // of pointer type. For example, an alloca may have been bitcast to 291 // a pointer to another type, which was then loaded. 292 --Depth; 293 } 294 295 // The original value is not captured via this if the instruction isn't. 296 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 297 UI != UE; ++UI) { 298 UseWithDepth UD(&UI.getUse(), Depth); 299 if (Visited.insert(UD)) 300 Worklist.push_back(UD); 301 } 302 break; 303 default: 304 // Something else - be conservative and say it is captured. 305 return true; 306 } 307 } 308 309 // All uses examined - not captured. 310 return false; 311} 312 313/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 314bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) { 315 bool Changed = false; 316 317 // Check each function in turn, determining which pointer arguments are not 318 // captured. 319 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 320 Function *F = SCC[i]->getFunction(); 321 322 if (F == 0) 323 // External node - skip it; 324 continue; 325 326 // Definitions with weak linkage may be overridden at linktime with 327 // something that writes memory, so treat them like declarations. 328 if (F->isDeclaration() || F->mayBeOverridden()) 329 continue; 330 331 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 332 if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr() && 333 !isCaptured(*F, A)) { 334 A->addAttr(Attribute::NoCapture); 335 ++NumNoCapture; 336 Changed = true; 337 } 338 } 339 340 return Changed; 341} 342 343bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 344 bool Changed = AddReadAttrs(SCC); 345 Changed |= AddNoCaptureAttrs(SCC); 346 return Changed; 347} 348