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/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/SmallSet.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/ADT/UniqueVector.h" 33 #include "llvm/Support/InstIterator.h" 34 using namespace llvm; 35 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"); 40 41 namespace { 42 struct FunctionAttrs : public CallGraphSCCPass { 43 static char ID; // Pass identification, replacement for typeid 44 FunctionAttrs() : CallGraphSCCPass(ID), AA(0) { 45 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); 46 } 47 48 // runOnSCC - Analyze the SCC, performing the transformation if possible. 49 bool runOnSCC(CallGraphSCC &SCC); 50 51 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 52 bool AddReadAttrs(const CallGraphSCC &SCC); 53 54 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 55 bool AddNoCaptureAttrs(const CallGraphSCC &SCC); 56 57 // IsFunctionMallocLike - Does this function allocate new memory? 58 bool IsFunctionMallocLike(Function *F, 59 SmallPtrSet<Function*, 8> &) const; 60 61 // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 62 bool AddNoAliasAttrs(const CallGraphSCC &SCC); 63 64 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 65 AU.setPreservesCFG(); 66 AU.addRequired<AliasAnalysis>(); 67 CallGraphSCCPass::getAnalysisUsage(AU); 68 } 69 70 private: 71 AliasAnalysis *AA; 72 }; 73 } 74 75 char FunctionAttrs::ID = 0; 76 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 77 "Deduce function attributes", false, false) 78 INITIALIZE_AG_DEPENDENCY(CallGraph) 79 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 80 "Deduce function attributes", false, false) 81 82 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 83 84 85 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 86 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 87 SmallPtrSet<Function*, 8> SCCNodes; 88 89 // Fill SCCNodes with the elements of the SCC. Used for quickly 90 // looking up whether a given CallGraphNode is in this SCC. 91 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 92 SCCNodes.insert((*I)->getFunction()); 93 94 // Check if any of the functions in the SCC read or write memory. If they 95 // write memory then they can't be marked readnone or readonly. 96 bool ReadsMemory = false; 97 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 98 Function *F = (*I)->getFunction(); 99 100 if (F == 0) 101 // External node - may write memory. Just give up. 102 return false; 103 104 AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F); 105 if (MRB == AliasAnalysis::DoesNotAccessMemory) 106 // Already perfect! 107 continue; 108 109 // Definitions with weak linkage may be overridden at linktime with 110 // something that writes memory, so treat them like declarations. 111 if (F->isDeclaration() || F->mayBeOverridden()) { 112 if (!AliasAnalysis::onlyReadsMemory(MRB)) 113 // May write memory. Just give up. 114 return false; 115 116 ReadsMemory = true; 117 continue; 118 } 119 120 // Scan the function body for instructions that may read or write memory. 121 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 122 Instruction *I = &*II; 123 124 // Some instructions can be ignored even if they read or write memory. 125 // Detect these now, skipping to the next instruction if one is found. 126 CallSite CS(cast<Value>(I)); 127 if (CS) { 128 // Ignore calls to functions in the same SCC. 129 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 130 continue; 131 AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS); 132 // If the call doesn't access arbitrary memory, we may be able to 133 // figure out something. 134 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 135 // If the call does access argument pointees, check each argument. 136 if (AliasAnalysis::doesAccessArgPointees(MRB)) 137 // Check whether all pointer arguments point to local memory, and 138 // ignore calls that only access local memory. 139 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 140 CI != CE; ++CI) { 141 Value *Arg = *CI; 142 if (Arg->getType()->isPointerTy()) { 143 AliasAnalysis::Location Loc(Arg, 144 AliasAnalysis::UnknownSize, 145 I->getMetadata(LLVMContext::MD_tbaa)); 146 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) { 147 if (MRB & AliasAnalysis::Mod) 148 // Writes non-local memory. Give up. 149 return false; 150 if (MRB & AliasAnalysis::Ref) 151 // Ok, it reads non-local memory. 152 ReadsMemory = true; 153 } 154 } 155 } 156 continue; 157 } 158 // The call could access any memory. If that includes writes, give up. 159 if (MRB & AliasAnalysis::Mod) 160 return false; 161 // If it reads, note it. 162 if (MRB & AliasAnalysis::Ref) 163 ReadsMemory = true; 164 continue; 165 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 166 // Ignore non-volatile loads from local memory. (Atomic is okay here.) 167 if (!LI->isVolatile()) { 168 AliasAnalysis::Location Loc = AA->getLocation(LI); 169 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 170 continue; 171 } 172 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 173 // Ignore non-volatile stores to local memory. (Atomic is okay here.) 174 if (!SI->isVolatile()) { 175 AliasAnalysis::Location Loc = AA->getLocation(SI); 176 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 177 continue; 178 } 179 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) { 180 // Ignore vaargs on local memory. 181 AliasAnalysis::Location Loc = AA->getLocation(VI); 182 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 183 continue; 184 } 185 186 // Any remaining instructions need to be taken seriously! Check if they 187 // read or write memory. 188 if (I->mayWriteToMemory()) 189 // Writes memory. Just give up. 190 return false; 191 192 // If this instruction may read memory, remember that. 193 ReadsMemory |= I->mayReadFromMemory(); 194 } 195 } 196 197 // Success! Functions in this SCC do not access memory, or only read memory. 198 // Give them the appropriate attribute. 199 bool MadeChange = false; 200 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 201 Function *F = (*I)->getFunction(); 202 203 if (F->doesNotAccessMemory()) 204 // Already perfect! 205 continue; 206 207 if (F->onlyReadsMemory() && ReadsMemory) 208 // No change. 209 continue; 210 211 MadeChange = true; 212 213 // Clear out any existing attributes. 214 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 215 216 // Add in the new attribute. 217 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 218 219 if (ReadsMemory) 220 ++NumReadOnly; 221 else 222 ++NumReadNone; 223 } 224 225 return MadeChange; 226 } 227 228 /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 229 bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 230 bool Changed = false; 231 232 // Check each function in turn, determining which pointer arguments are not 233 // captured. 234 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 235 Function *F = (*I)->getFunction(); 236 237 if (F == 0) 238 // External node - skip it; 239 continue; 240 241 // Definitions with weak linkage may be overridden at linktime with 242 // something that writes memory, so treat them like declarations. 243 if (F->isDeclaration() || F->mayBeOverridden()) 244 continue; 245 246 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 247 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr() && 248 !PointerMayBeCaptured(A, true, /*StoreCaptures=*/false)) { 249 A->addAttr(Attribute::NoCapture); 250 ++NumNoCapture; 251 Changed = true; 252 } 253 } 254 255 return Changed; 256 } 257 258 /// IsFunctionMallocLike - A function is malloc-like if it returns either null 259 /// or a pointer that doesn't alias any other pointer visible to the caller. 260 bool FunctionAttrs::IsFunctionMallocLike(Function *F, 261 SmallPtrSet<Function*, 8> &SCCNodes) const { 262 UniqueVector<Value *> FlowsToReturn; 263 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 264 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 265 FlowsToReturn.insert(Ret->getReturnValue()); 266 267 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 268 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 269 270 if (Constant *C = dyn_cast<Constant>(RetVal)) { 271 if (!C->isNullValue() && !isa<UndefValue>(C)) 272 return false; 273 274 continue; 275 } 276 277 if (isa<Argument>(RetVal)) 278 return false; 279 280 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 281 switch (RVI->getOpcode()) { 282 // Extend the analysis by looking upwards. 283 case Instruction::BitCast: 284 case Instruction::GetElementPtr: 285 FlowsToReturn.insert(RVI->getOperand(0)); 286 continue; 287 case Instruction::Select: { 288 SelectInst *SI = cast<SelectInst>(RVI); 289 FlowsToReturn.insert(SI->getTrueValue()); 290 FlowsToReturn.insert(SI->getFalseValue()); 291 continue; 292 } 293 case Instruction::PHI: { 294 PHINode *PN = cast<PHINode>(RVI); 295 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 296 FlowsToReturn.insert(PN->getIncomingValue(i)); 297 continue; 298 } 299 300 // Check whether the pointer came from an allocation. 301 case Instruction::Alloca: 302 break; 303 case Instruction::Call: 304 case Instruction::Invoke: { 305 CallSite CS(RVI); 306 if (CS.paramHasAttr(0, Attribute::NoAlias)) 307 break; 308 if (CS.getCalledFunction() && 309 SCCNodes.count(CS.getCalledFunction())) 310 break; 311 } // fall-through 312 default: 313 return false; // Did not come from an allocation. 314 } 315 316 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 317 return false; 318 } 319 320 return true; 321 } 322 323 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 324 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 325 SmallPtrSet<Function*, 8> SCCNodes; 326 327 // Fill SCCNodes with the elements of the SCC. Used for quickly 328 // looking up whether a given CallGraphNode is in this SCC. 329 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 330 SCCNodes.insert((*I)->getFunction()); 331 332 // Check each function in turn, determining which functions return noalias 333 // pointers. 334 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 335 Function *F = (*I)->getFunction(); 336 337 if (F == 0) 338 // External node - skip it; 339 return false; 340 341 // Already noalias. 342 if (F->doesNotAlias(0)) 343 continue; 344 345 // Definitions with weak linkage may be overridden at linktime, so 346 // treat them like declarations. 347 if (F->isDeclaration() || F->mayBeOverridden()) 348 return false; 349 350 // We annotate noalias return values, which are only applicable to 351 // pointer types. 352 if (!F->getReturnType()->isPointerTy()) 353 continue; 354 355 if (!IsFunctionMallocLike(F, SCCNodes)) 356 return false; 357 } 358 359 bool MadeChange = false; 360 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 361 Function *F = (*I)->getFunction(); 362 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 363 continue; 364 365 F->setDoesNotAlias(0); 366 ++NumNoAlias; 367 MadeChange = true; 368 } 369 370 return MadeChange; 371 } 372 373 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 374 AA = &getAnalysis<AliasAnalysis>(); 375 376 bool Changed = AddReadAttrs(SCC); 377 Changed |= AddNoCaptureAttrs(SCC); 378 Changed |= AddNoAliasAttrs(SCC); 379 return Changed; 380 } 381
