FunctionAttrs.cpp revision bacd5df0f8bf8d380c60237417ed9e06a513855f
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" 34using namespace llvm; 35 36STATISTIC(NumReadNone, "Number of functions marked readnone"); 37STATISTIC(NumReadOnly, "Number of functions marked readonly"); 38STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 39STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 40 41namespace { 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 75char FunctionAttrs::ID = 0; 76INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 77 "Deduce function attributes", false, false) 78INITIALIZE_AG_DEPENDENCY(CallGraph) 79INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 80 "Deduce function attributes", false, false) 81 82Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 83 84 85/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 86bool 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 switch (AA->getModRefBehavior(CS)) { 132 case AliasAnalysis::DoesNotAccessMemory: 133 // Ignore calls that don't access memory. 134 continue; 135 case AliasAnalysis::OnlyReadsMemory: 136 // Handle calls that only read from memory. 137 ReadsMemory = true; 138 continue; 139 case AliasAnalysis::AccessesArguments: 140 // Check whether all pointer arguments point to local memory, and 141 // ignore calls that only access local memory. 142 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 143 CI != CE; ++CI) { 144 Value *Arg = *CI; 145 if (Arg->getType()->isPointerTy()) { 146 AliasAnalysis::Location Loc(Arg, 147 AliasAnalysis::UnknownSize, 148 I->getMetadata(LLVMContext::MD_tbaa)); 149 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 150 // Writes memory. Just give up. 151 return false; 152 } 153 } 154 // Only reads and writes local memory. 155 continue; 156 case AliasAnalysis::AccessesArgumentsReadonly: 157 // Check whether all pointer arguments point to local memory, and 158 // ignore calls that only access local memory. 159 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 160 CI != CE; ++CI) { 161 Value *Arg = *CI; 162 if (Arg->getType()->isPointerTy()) { 163 AliasAnalysis::Location Loc(Arg, 164 AliasAnalysis::UnknownSize, 165 I->getMetadata(LLVMContext::MD_tbaa)); 166 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) { 167 // Reads non-local memory. 168 ReadsMemory = true; 169 break; 170 } 171 } 172 } 173 // Only reads memory. 174 continue; 175 default: 176 // Otherwise, be conservative. 177 break; 178 } 179 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 180 // Ignore non-volatile loads from local memory. 181 if (!LI->isVolatile()) { 182 AliasAnalysis::Location Loc(LI->getPointerOperand(), 183 AA->getTypeStoreSize(LI->getType()), 184 LI->getMetadata(LLVMContext::MD_tbaa)); 185 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 186 continue; 187 } 188 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 189 // Ignore non-volatile stores to local memory. 190 if (!SI->isVolatile()) { 191 const Type *StoredType = SI->getValueOperand()->getType(); 192 AliasAnalysis::Location Loc(SI->getPointerOperand(), 193 AA->getTypeStoreSize(StoredType), 194 SI->getMetadata(LLVMContext::MD_tbaa)); 195 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 196 continue; 197 } 198 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) { 199 // Ignore vaargs on local memory. 200 AliasAnalysis::Location Loc(VI->getPointerOperand(), 201 AliasAnalysis::UnknownSize, 202 VI->getMetadata(LLVMContext::MD_tbaa)); 203 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 204 continue; 205 } 206 207 // Any remaining instructions need to be taken seriously! Check if they 208 // read or write memory. 209 if (I->mayWriteToMemory()) 210 // Writes memory. Just give up. 211 return false; 212 213 // If this instruction may read memory, remember that. 214 ReadsMemory |= I->mayReadFromMemory(); 215 } 216 } 217 218 // Success! Functions in this SCC do not access memory, or only read memory. 219 // Give them the appropriate attribute. 220 bool MadeChange = false; 221 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 222 Function *F = (*I)->getFunction(); 223 224 if (F->doesNotAccessMemory()) 225 // Already perfect! 226 continue; 227 228 if (F->onlyReadsMemory() && ReadsMemory) 229 // No change. 230 continue; 231 232 MadeChange = true; 233 234 // Clear out any existing attributes. 235 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 236 237 // Add in the new attribute. 238 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 239 240 if (ReadsMemory) 241 ++NumReadOnly; 242 else 243 ++NumReadNone; 244 } 245 246 return MadeChange; 247} 248 249/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 250bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 251 bool Changed = false; 252 253 // Check each function in turn, determining which pointer arguments are not 254 // captured. 255 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 256 Function *F = (*I)->getFunction(); 257 258 if (F == 0) 259 // External node - skip it; 260 continue; 261 262 // Definitions with weak linkage may be overridden at linktime with 263 // something that writes memory, so treat them like declarations. 264 if (F->isDeclaration() || F->mayBeOverridden()) 265 continue; 266 267 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 268 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr() && 269 !PointerMayBeCaptured(A, true, /*StoreCaptures=*/false)) { 270 A->addAttr(Attribute::NoCapture); 271 ++NumNoCapture; 272 Changed = true; 273 } 274 } 275 276 return Changed; 277} 278 279/// IsFunctionMallocLike - A function is malloc-like if it returns either null 280/// or a pointer that doesn't alias any other pointer visible to the caller. 281bool FunctionAttrs::IsFunctionMallocLike(Function *F, 282 SmallPtrSet<Function*, 8> &SCCNodes) const { 283 UniqueVector<Value *> FlowsToReturn; 284 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 285 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 286 FlowsToReturn.insert(Ret->getReturnValue()); 287 288 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 289 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 290 291 if (Constant *C = dyn_cast<Constant>(RetVal)) { 292 if (!C->isNullValue() && !isa<UndefValue>(C)) 293 return false; 294 295 continue; 296 } 297 298 if (isa<Argument>(RetVal)) 299 return false; 300 301 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 302 switch (RVI->getOpcode()) { 303 // Extend the analysis by looking upwards. 304 case Instruction::BitCast: 305 case Instruction::GetElementPtr: 306 FlowsToReturn.insert(RVI->getOperand(0)); 307 continue; 308 case Instruction::Select: { 309 SelectInst *SI = cast<SelectInst>(RVI); 310 FlowsToReturn.insert(SI->getTrueValue()); 311 FlowsToReturn.insert(SI->getFalseValue()); 312 continue; 313 } 314 case Instruction::PHI: { 315 PHINode *PN = cast<PHINode>(RVI); 316 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 317 FlowsToReturn.insert(PN->getIncomingValue(i)); 318 continue; 319 } 320 321 // Check whether the pointer came from an allocation. 322 case Instruction::Alloca: 323 break; 324 case Instruction::Call: 325 case Instruction::Invoke: { 326 CallSite CS(RVI); 327 if (CS.paramHasAttr(0, Attribute::NoAlias)) 328 break; 329 if (CS.getCalledFunction() && 330 SCCNodes.count(CS.getCalledFunction())) 331 break; 332 } // fall-through 333 default: 334 return false; // Did not come from an allocation. 335 } 336 337 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 338 return false; 339 } 340 341 return true; 342} 343 344/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 345bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 346 SmallPtrSet<Function*, 8> SCCNodes; 347 348 // Fill SCCNodes with the elements of the SCC. Used for quickly 349 // looking up whether a given CallGraphNode is in this SCC. 350 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 351 SCCNodes.insert((*I)->getFunction()); 352 353 // Check each function in turn, determining which functions return noalias 354 // pointers. 355 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 356 Function *F = (*I)->getFunction(); 357 358 if (F == 0) 359 // External node - skip it; 360 return false; 361 362 // Already noalias. 363 if (F->doesNotAlias(0)) 364 continue; 365 366 // Definitions with weak linkage may be overridden at linktime, so 367 // treat them like declarations. 368 if (F->isDeclaration() || F->mayBeOverridden()) 369 return false; 370 371 // We annotate noalias return values, which are only applicable to 372 // pointer types. 373 if (!F->getReturnType()->isPointerTy()) 374 continue; 375 376 if (!IsFunctionMallocLike(F, SCCNodes)) 377 return false; 378 } 379 380 bool MadeChange = false; 381 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 382 Function *F = (*I)->getFunction(); 383 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 384 continue; 385 386 F->setDoesNotAlias(0); 387 ++NumNoAlias; 388 MadeChange = true; 389 } 390 391 return MadeChange; 392} 393 394bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 395 AA = &getAnalysis<AliasAnalysis>(); 396 397 bool Changed = AddReadAttrs(SCC); 398 Changed |= AddNoCaptureAttrs(SCC); 399 Changed |= AddNoAliasAttrs(SCC); 400 return Changed; 401} 402