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