FunctionAttrs.cpp revision c92b8aa79f4a2cd16f7b674189e425c2c367e886
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/SCCIterator.h" 31#include "llvm/ADT/SmallSet.h" 32#include "llvm/ADT/Statistic.h" 33#include "llvm/ADT/UniqueVector.h" 34#include "llvm/Support/InstIterator.h" 35using namespace llvm; 36 37STATISTIC(NumReadNone, "Number of functions marked readnone"); 38STATISTIC(NumReadOnly, "Number of functions marked readonly"); 39STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 40STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 41 42namespace { 43 struct FunctionAttrs : public CallGraphSCCPass { 44 static char ID; // Pass identification, replacement for typeid 45 FunctionAttrs() : CallGraphSCCPass(ID), AA(0) { 46 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); 47 } 48 49 // runOnSCC - Analyze the SCC, performing the transformation if possible. 50 bool runOnSCC(CallGraphSCC &SCC); 51 52 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 53 bool AddReadAttrs(const CallGraphSCC &SCC); 54 55 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 56 bool AddNoCaptureAttrs(const CallGraphSCC &SCC); 57 58 // IsFunctionMallocLike - Does this function allocate new memory? 59 bool IsFunctionMallocLike(Function *F, 60 SmallPtrSet<Function*, 8> &) const; 61 62 // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 63 bool AddNoAliasAttrs(const CallGraphSCC &SCC); 64 65 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 66 AU.setPreservesCFG(); 67 AU.addRequired<AliasAnalysis>(); 68 CallGraphSCCPass::getAnalysisUsage(AU); 69 } 70 71 private: 72 AliasAnalysis *AA; 73 }; 74} 75 76char FunctionAttrs::ID = 0; 77INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 78 "Deduce function attributes", false, false) 79INITIALIZE_AG_DEPENDENCY(CallGraph) 80INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 81 "Deduce function attributes", false, false) 82 83Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 84 85 86/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 87bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 88 SmallPtrSet<Function*, 8> SCCNodes; 89 90 // Fill SCCNodes with the elements of the SCC. Used for quickly 91 // looking up whether a given CallGraphNode is in this SCC. 92 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 93 SCCNodes.insert((*I)->getFunction()); 94 95 // Check if any of the functions in the SCC read or write memory. If they 96 // write memory then they can't be marked readnone or readonly. 97 bool ReadsMemory = false; 98 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 99 Function *F = (*I)->getFunction(); 100 101 if (F == 0) 102 // External node - may write memory. Just give up. 103 return false; 104 105 AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F); 106 if (MRB == AliasAnalysis::DoesNotAccessMemory) 107 // Already perfect! 108 continue; 109 110 // Definitions with weak linkage may be overridden at linktime with 111 // something that writes memory, so treat them like declarations. 112 if (F->isDeclaration() || F->mayBeOverridden()) { 113 if (!AliasAnalysis::onlyReadsMemory(MRB)) 114 // May write memory. Just give up. 115 return false; 116 117 ReadsMemory = true; 118 continue; 119 } 120 121 // Scan the function body for instructions that may read or write memory. 122 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 123 Instruction *I = &*II; 124 125 // Some instructions can be ignored even if they read or write memory. 126 // Detect these now, skipping to the next instruction if one is found. 127 CallSite CS(cast<Value>(I)); 128 if (CS) { 129 // Ignore calls to functions in the same SCC. 130 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 131 continue; 132 AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS); 133 // If the call doesn't access arbitrary memory, we may be able to 134 // figure out something. 135 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 136 // If the call does access argument pointees, check each argument. 137 if (AliasAnalysis::doesAccessArgPointees(MRB)) 138 // Check whether all pointer arguments point to local memory, and 139 // ignore calls that only access local memory. 140 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 141 CI != CE; ++CI) { 142 Value *Arg = *CI; 143 if (Arg->getType()->isPointerTy()) { 144 AliasAnalysis::Location Loc(Arg, 145 AliasAnalysis::UnknownSize, 146 I->getMetadata(LLVMContext::MD_tbaa)); 147 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) { 148 if (MRB & AliasAnalysis::Mod) 149 // Writes non-local memory. Give up. 150 return false; 151 if (MRB & AliasAnalysis::Ref) 152 // Ok, it reads non-local memory. 153 ReadsMemory = true; 154 } 155 } 156 } 157 continue; 158 } 159 // The call could access any memory. If that includes writes, give up. 160 if (MRB & AliasAnalysis::Mod) 161 return false; 162 // If it reads, note it. 163 if (MRB & AliasAnalysis::Ref) 164 ReadsMemory = true; 165 continue; 166 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 167 // Ignore non-volatile loads from local memory. (Atomic is okay here.) 168 if (!LI->isVolatile()) { 169 AliasAnalysis::Location Loc = AA->getLocation(LI); 170 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 171 continue; 172 } 173 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 174 // Ignore non-volatile stores to local memory. (Atomic is okay here.) 175 if (!SI->isVolatile()) { 176 AliasAnalysis::Location Loc = AA->getLocation(SI); 177 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 178 continue; 179 } 180 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) { 181 // Ignore vaargs on local memory. 182 AliasAnalysis::Location Loc = AA->getLocation(VI); 183 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 184 continue; 185 } 186 187 // Any remaining instructions need to be taken seriously! Check if they 188 // read or write memory. 189 if (I->mayWriteToMemory()) 190 // Writes memory. Just give up. 191 return false; 192 193 // If this instruction may read memory, remember that. 194 ReadsMemory |= I->mayReadFromMemory(); 195 } 196 } 197 198 // Success! Functions in this SCC do not access memory, or only read memory. 199 // Give them the appropriate attribute. 200 bool MadeChange = false; 201 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 202 Function *F = (*I)->getFunction(); 203 204 if (F->doesNotAccessMemory()) 205 // Already perfect! 206 continue; 207 208 if (F->onlyReadsMemory() && ReadsMemory) 209 // No change. 210 continue; 211 212 MadeChange = true; 213 214 // Clear out any existing attributes. 215 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 216 217 // Add in the new attribute. 218 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 219 220 if (ReadsMemory) 221 ++NumReadOnly; 222 else 223 ++NumReadNone; 224 } 225 226 return MadeChange; 227} 228 229namespace { 230 // For a given pointer Argument, this retains a list of Arguments of functions 231 // in the same SCC that the pointer data flows into. We use this to build an 232 // SCC of the arguments. 233 struct ArgumentGraphNode { 234 Argument *Definition; 235 SmallVector<ArgumentGraphNode*, 4> Uses; 236 }; 237 238 class ArgumentGraph { 239 // We store pointers to ArgumentGraphNode objects, so it's important that 240 // that they not move around upon insert. 241 typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy; 242 243 ArgumentMapTy ArgumentMap; 244 245 // There is no root node for the argument graph, in fact: 246 // void f(int *x, int *y) { if (...) f(x, y); } 247 // is an example where the graph is disconnected. The SCCIterator requires a 248 // single entry point, so we maintain a fake ("synthetic") root node that 249 // uses every node. Because the graph is directed and nothing points into 250 // the root, it will not participate in any SCCs (except for its own). 251 ArgumentGraphNode SyntheticRoot; 252 253 public: 254 ArgumentGraph() { SyntheticRoot.Definition = 0; } 255 256 typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator; 257 258 iterator begin() { return SyntheticRoot.Uses.begin(); } 259 iterator end() { return SyntheticRoot.Uses.end(); } 260 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } 261 262 ArgumentGraphNode *operator[](Argument *A) { 263 ArgumentGraphNode &Node = ArgumentMap[A]; 264 Node.Definition = A; 265 SyntheticRoot.Uses.push_back(&Node); 266 return &Node; 267 } 268 }; 269 270 // This tracker checks whether callees are in the SCC, and if so it does not 271 // consider that a capture, instead adding it to the "Uses" list and 272 // continuing with the analysis. 273 struct ArgumentUsesTracker : public CaptureTracker { 274 ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes) 275 : Captured(false), SCCNodes(SCCNodes) {} 276 277 void tooManyUses() { Captured = true; } 278 279 bool captured(Use *U) { 280 CallSite CS(U->getUser()); 281 if (!CS.getInstruction()) { Captured = true; return true; } 282 283 Function *F = CS.getCalledFunction(); 284 if (!F || !SCCNodes.count(F)) { Captured = true; return true; } 285 286 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 287 for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end(); 288 PI != PE; ++PI, ++AI) { 289 if (AI == AE) { 290 assert(F->isVarArg() && "More params than args in non-varargs call"); 291 Captured = true; 292 return true; 293 } 294 if (PI == U) { 295 Uses.push_back(AI); 296 break; 297 } 298 } 299 assert(!Uses.empty() && "Capturing call-site captured nothing?"); 300 return false; 301 } 302 303 bool Captured; // True only if certainly captured (used outside our SCC). 304 SmallVector<Argument*, 4> Uses; // Uses within our SCC. 305 306 const SmallPtrSet<Function*, 8> &SCCNodes; 307 }; 308} 309 310namespace llvm { 311 template<> struct GraphTraits<ArgumentGraphNode*> { 312 typedef ArgumentGraphNode NodeType; 313 typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType; 314 315 static inline NodeType *getEntryNode(NodeType *A) { return A; } 316 static inline ChildIteratorType child_begin(NodeType *N) { 317 return N->Uses.begin(); 318 } 319 static inline ChildIteratorType child_end(NodeType *N) { 320 return N->Uses.end(); 321 } 322 }; 323 template<> struct GraphTraits<ArgumentGraph*> 324 : public GraphTraits<ArgumentGraphNode*> { 325 static NodeType *getEntryNode(ArgumentGraph *AG) { 326 return AG->getEntryNode(); 327 } 328 static ChildIteratorType nodes_begin(ArgumentGraph *AG) { 329 return AG->begin(); 330 } 331 static ChildIteratorType nodes_end(ArgumentGraph *AG) { 332 return AG->end(); 333 } 334 }; 335} 336 337/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 338bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 339 bool Changed = false; 340 341 SmallPtrSet<Function*, 8> SCCNodes; 342 343 // Fill SCCNodes with the elements of the SCC. Used for quickly 344 // looking up whether a given CallGraphNode is in this SCC. 345 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 346 Function *F = (*I)->getFunction(); 347 if (F && !F->isDeclaration() && !F->mayBeOverridden()) 348 SCCNodes.insert(F); 349 } 350 351 ArgumentGraph AG; 352 353 // Check each function in turn, determining which pointer arguments are not 354 // captured. 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 - only a problem for arguments that we pass to it. 360 continue; 361 362 // Definitions with weak linkage may be overridden at linktime with 363 // something that captures pointers, so treat them like declarations. 364 if (F->isDeclaration() || F->mayBeOverridden()) 365 continue; 366 367 // Functions that are readonly (or readnone) and nounwind and don't return 368 // a value can't capture arguments. Don't analyze them. 369 if (F->onlyReadsMemory() && F->doesNotThrow() && 370 F->getReturnType()->isVoidTy()) { 371 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); 372 A != E; ++A) { 373 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 374 A->addAttr(Attribute::NoCapture); 375 ++NumNoCapture; 376 Changed = true; 377 } 378 } 379 continue; 380 } 381 382 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 383 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 384 ArgumentUsesTracker Tracker(SCCNodes); 385 PointerMayBeCaptured(A, &Tracker); 386 if (!Tracker.Captured) { 387 if (Tracker.Uses.empty()) { 388 // If it's trivially not captured, mark it nocapture now. 389 A->addAttr(Attribute::NoCapture); 390 ++NumNoCapture; 391 Changed = true; 392 } else { 393 // If it's not trivially captured and not trivially not captured, 394 // then it must be calling into another function in our SCC. Save 395 // its particulars for Argument-SCC analysis later. 396 ArgumentGraphNode *Node = AG[A]; 397 for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(), 398 UE = Tracker.Uses.end(); UI != UE; ++UI) 399 Node->Uses.push_back(AG[*UI]); 400 } 401 } 402 // Otherwise, it's captured. Don't bother doing SCC analysis on it. 403 } 404 } 405 406 // The graph we've collected is partial because we stopped scanning for 407 // argument uses once we solved the argument trivially. These partial nodes 408 // show up as ArgumentGraphNode objects with an empty Uses list, and for 409 // these nodes the final decision about whether they capture has already been 410 // made. If the definition doesn't have a 'nocapture' attribute by now, it 411 // captures. 412 413 for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG), E = scc_end(&AG); 414 I != E; ++I) { 415 std::vector<ArgumentGraphNode*> &ArgumentSCC = *I; 416 if (ArgumentSCC.size() == 1) { 417 if (!ArgumentSCC[0]->Definition) continue; // synthetic root node 418 419 // eg. "void f(int* x) { if (...) f(x); }" 420 if (ArgumentSCC[0]->Uses.size() == 1 && 421 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) { 422 ArgumentSCC[0]->Definition->addAttr(Attribute::NoCapture); 423 ++NumNoCapture; 424 Changed = true; 425 } 426 continue; 427 } 428 429 bool SCCCaptured = false; 430 for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 431 E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { 432 ArgumentGraphNode *Node = *I; 433 if (Node->Uses.empty()) { 434 if (!Node->Definition->hasNoCaptureAttr()) 435 SCCCaptured = true; 436 } 437 } 438 if (SCCCaptured) continue; 439 440 SmallPtrSet<Argument*, 8> ArgumentSCCNodes; 441 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for 442 // quickly looking up whether a given Argument is in this ArgumentSCC. 443 for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 444 E = ArgumentSCC.end(); I != E; ++I) { 445 ArgumentSCCNodes.insert((*I)->Definition); 446 } 447 448 for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 449 E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { 450 ArgumentGraphNode *N = *I; 451 for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(), 452 UE = N->Uses.end(); UI != UE; ++UI) { 453 Argument *A = (*UI)->Definition; 454 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A)) 455 continue; 456 SCCCaptured = true; 457 break; 458 } 459 } 460 if (SCCCaptured) continue; 461 462 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 463 Argument *A = ArgumentSCC[i]->Definition; 464 A->addAttr(Attribute::NoCapture); 465 ++NumNoCapture; 466 Changed = true; 467 } 468 } 469 470 return Changed; 471} 472 473/// IsFunctionMallocLike - A function is malloc-like if it returns either null 474/// or a pointer that doesn't alias any other pointer visible to the caller. 475bool FunctionAttrs::IsFunctionMallocLike(Function *F, 476 SmallPtrSet<Function*, 8> &SCCNodes) const { 477 UniqueVector<Value *> FlowsToReturn; 478 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 479 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 480 FlowsToReturn.insert(Ret->getReturnValue()); 481 482 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 483 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 484 485 if (Constant *C = dyn_cast<Constant>(RetVal)) { 486 if (!C->isNullValue() && !isa<UndefValue>(C)) 487 return false; 488 489 continue; 490 } 491 492 if (isa<Argument>(RetVal)) 493 return false; 494 495 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 496 switch (RVI->getOpcode()) { 497 // Extend the analysis by looking upwards. 498 case Instruction::BitCast: 499 case Instruction::GetElementPtr: 500 FlowsToReturn.insert(RVI->getOperand(0)); 501 continue; 502 case Instruction::Select: { 503 SelectInst *SI = cast<SelectInst>(RVI); 504 FlowsToReturn.insert(SI->getTrueValue()); 505 FlowsToReturn.insert(SI->getFalseValue()); 506 continue; 507 } 508 case Instruction::PHI: { 509 PHINode *PN = cast<PHINode>(RVI); 510 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 511 FlowsToReturn.insert(PN->getIncomingValue(i)); 512 continue; 513 } 514 515 // Check whether the pointer came from an allocation. 516 case Instruction::Alloca: 517 break; 518 case Instruction::Call: 519 case Instruction::Invoke: { 520 CallSite CS(RVI); 521 if (CS.paramHasNoAliasAttr(0)) 522 break; 523 if (CS.getCalledFunction() && 524 SCCNodes.count(CS.getCalledFunction())) 525 break; 526 } // fall-through 527 default: 528 return false; // Did not come from an allocation. 529 } 530 531 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 532 return false; 533 } 534 535 return true; 536} 537 538/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 539bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 540 SmallPtrSet<Function*, 8> SCCNodes; 541 542 // Fill SCCNodes with the elements of the SCC. Used for quickly 543 // looking up whether a given CallGraphNode is in this SCC. 544 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 545 SCCNodes.insert((*I)->getFunction()); 546 547 // Check each function in turn, determining which functions return noalias 548 // pointers. 549 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 550 Function *F = (*I)->getFunction(); 551 552 if (F == 0) 553 // External node - skip it; 554 return false; 555 556 // Already noalias. 557 if (F->doesNotAlias(0)) 558 continue; 559 560 // Definitions with weak linkage may be overridden at linktime, so 561 // treat them like declarations. 562 if (F->isDeclaration() || F->mayBeOverridden()) 563 return false; 564 565 // We annotate noalias return values, which are only applicable to 566 // pointer types. 567 if (!F->getReturnType()->isPointerTy()) 568 continue; 569 570 if (!IsFunctionMallocLike(F, SCCNodes)) 571 return false; 572 } 573 574 bool MadeChange = false; 575 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 576 Function *F = (*I)->getFunction(); 577 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 578 continue; 579 580 F->setDoesNotAlias(0); 581 ++NumNoAlias; 582 MadeChange = true; 583 } 584 585 return MadeChange; 586} 587 588bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 589 AA = &getAnalysis<AliasAnalysis>(); 590 591 bool Changed = AddReadAttrs(SCC); 592 Changed |= AddNoCaptureAttrs(SCC); 593 Changed |= AddNoAliasAttrs(SCC); 594 return Changed; 595} 596