FunctionAttrs.cpp revision 7d2f2496c1d263eecdc104fd72e847a31d8695b9
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 Attributes::Builder B; 216 B.addAttribute(Attributes::ReadOnly) 217 .addAttribute(Attributes::ReadNone); 218 F->removeAttribute(~0, Attributes::get(B)); 219 220 // Add in the new attribute. 221 B.clear(); 222 B.addAttribute(ReadsMemory ? Attributes::ReadOnly : Attributes::ReadNone); 223 F->addAttribute(~0, Attributes::get(B)); 224 225 if (ReadsMemory) 226 ++NumReadOnly; 227 else 228 ++NumReadNone; 229 } 230 231 return MadeChange; 232} 233 234namespace { 235 // For a given pointer Argument, this retains a list of Arguments of functions 236 // in the same SCC that the pointer data flows into. We use this to build an 237 // SCC of the arguments. 238 struct ArgumentGraphNode { 239 Argument *Definition; 240 SmallVector<ArgumentGraphNode*, 4> Uses; 241 }; 242 243 class ArgumentGraph { 244 // We store pointers to ArgumentGraphNode objects, so it's important that 245 // that they not move around upon insert. 246 typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy; 247 248 ArgumentMapTy ArgumentMap; 249 250 // There is no root node for the argument graph, in fact: 251 // void f(int *x, int *y) { if (...) f(x, y); } 252 // is an example where the graph is disconnected. The SCCIterator requires a 253 // single entry point, so we maintain a fake ("synthetic") root node that 254 // uses every node. Because the graph is directed and nothing points into 255 // the root, it will not participate in any SCCs (except for its own). 256 ArgumentGraphNode SyntheticRoot; 257 258 public: 259 ArgumentGraph() { SyntheticRoot.Definition = 0; } 260 261 typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator; 262 263 iterator begin() { return SyntheticRoot.Uses.begin(); } 264 iterator end() { return SyntheticRoot.Uses.end(); } 265 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } 266 267 ArgumentGraphNode *operator[](Argument *A) { 268 ArgumentGraphNode &Node = ArgumentMap[A]; 269 Node.Definition = A; 270 SyntheticRoot.Uses.push_back(&Node); 271 return &Node; 272 } 273 }; 274 275 // This tracker checks whether callees are in the SCC, and if so it does not 276 // consider that a capture, instead adding it to the "Uses" list and 277 // continuing with the analysis. 278 struct ArgumentUsesTracker : public CaptureTracker { 279 ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes) 280 : Captured(false), SCCNodes(SCCNodes) {} 281 282 void tooManyUses() { Captured = true; } 283 284 bool captured(Use *U) { 285 CallSite CS(U->getUser()); 286 if (!CS.getInstruction()) { Captured = true; return true; } 287 288 Function *F = CS.getCalledFunction(); 289 if (!F || !SCCNodes.count(F)) { Captured = true; return true; } 290 291 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 292 for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end(); 293 PI != PE; ++PI, ++AI) { 294 if (AI == AE) { 295 assert(F->isVarArg() && "More params than args in non-varargs call"); 296 Captured = true; 297 return true; 298 } 299 if (PI == U) { 300 Uses.push_back(AI); 301 break; 302 } 303 } 304 assert(!Uses.empty() && "Capturing call-site captured nothing?"); 305 return false; 306 } 307 308 bool Captured; // True only if certainly captured (used outside our SCC). 309 SmallVector<Argument*, 4> Uses; // Uses within our SCC. 310 311 const SmallPtrSet<Function*, 8> &SCCNodes; 312 }; 313} 314 315namespace llvm { 316 template<> struct GraphTraits<ArgumentGraphNode*> { 317 typedef ArgumentGraphNode NodeType; 318 typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType; 319 320 static inline NodeType *getEntryNode(NodeType *A) { return A; } 321 static inline ChildIteratorType child_begin(NodeType *N) { 322 return N->Uses.begin(); 323 } 324 static inline ChildIteratorType child_end(NodeType *N) { 325 return N->Uses.end(); 326 } 327 }; 328 template<> struct GraphTraits<ArgumentGraph*> 329 : public GraphTraits<ArgumentGraphNode*> { 330 static NodeType *getEntryNode(ArgumentGraph *AG) { 331 return AG->getEntryNode(); 332 } 333 static ChildIteratorType nodes_begin(ArgumentGraph *AG) { 334 return AG->begin(); 335 } 336 static ChildIteratorType nodes_end(ArgumentGraph *AG) { 337 return AG->end(); 338 } 339 }; 340} 341 342/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 343bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 344 bool Changed = false; 345 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 Function *F = (*I)->getFunction(); 352 if (F && !F->isDeclaration() && !F->mayBeOverridden()) 353 SCCNodes.insert(F); 354 } 355 356 ArgumentGraph AG; 357 358 Attributes::Builder B; 359 B.addAttribute(Attributes::NoCapture); 360 361 // Check each function in turn, determining which pointer arguments are not 362 // captured. 363 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 364 Function *F = (*I)->getFunction(); 365 366 if (F == 0) 367 // External node - only a problem for arguments that we pass to it. 368 continue; 369 370 // Definitions with weak linkage may be overridden at linktime with 371 // something that captures pointers, so treat them like declarations. 372 if (F->isDeclaration() || F->mayBeOverridden()) 373 continue; 374 375 // Functions that are readonly (or readnone) and nounwind and don't return 376 // a value can't capture arguments. Don't analyze them. 377 if (F->onlyReadsMemory() && F->doesNotThrow() && 378 F->getReturnType()->isVoidTy()) { 379 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); 380 A != E; ++A) { 381 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 382 A->addAttr(Attributes::get(B)); 383 ++NumNoCapture; 384 Changed = true; 385 } 386 } 387 continue; 388 } 389 390 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 391 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 392 ArgumentUsesTracker Tracker(SCCNodes); 393 PointerMayBeCaptured(A, &Tracker); 394 if (!Tracker.Captured) { 395 if (Tracker.Uses.empty()) { 396 // If it's trivially not captured, mark it nocapture now. 397 A->addAttr(Attributes::get(B)); 398 ++NumNoCapture; 399 Changed = true; 400 } else { 401 // If it's not trivially captured and not trivially not captured, 402 // then it must be calling into another function in our SCC. Save 403 // its particulars for Argument-SCC analysis later. 404 ArgumentGraphNode *Node = AG[A]; 405 for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(), 406 UE = Tracker.Uses.end(); UI != UE; ++UI) 407 Node->Uses.push_back(AG[*UI]); 408 } 409 } 410 // Otherwise, it's captured. Don't bother doing SCC analysis on it. 411 } 412 } 413 414 // The graph we've collected is partial because we stopped scanning for 415 // argument uses once we solved the argument trivially. These partial nodes 416 // show up as ArgumentGraphNode objects with an empty Uses list, and for 417 // these nodes the final decision about whether they capture has already been 418 // made. If the definition doesn't have a 'nocapture' attribute by now, it 419 // captures. 420 421 for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG), E = scc_end(&AG); 422 I != E; ++I) { 423 std::vector<ArgumentGraphNode*> &ArgumentSCC = *I; 424 if (ArgumentSCC.size() == 1) { 425 if (!ArgumentSCC[0]->Definition) continue; // synthetic root node 426 427 // eg. "void f(int* x) { if (...) f(x); }" 428 if (ArgumentSCC[0]->Uses.size() == 1 && 429 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) { 430 ArgumentSCC[0]->Definition->addAttr(Attributes::get(B)); 431 ++NumNoCapture; 432 Changed = true; 433 } 434 continue; 435 } 436 437 bool SCCCaptured = false; 438 for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 439 E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { 440 ArgumentGraphNode *Node = *I; 441 if (Node->Uses.empty()) { 442 if (!Node->Definition->hasNoCaptureAttr()) 443 SCCCaptured = true; 444 } 445 } 446 if (SCCCaptured) continue; 447 448 SmallPtrSet<Argument*, 8> ArgumentSCCNodes; 449 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for 450 // quickly looking up whether a given Argument is in this ArgumentSCC. 451 for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 452 E = ArgumentSCC.end(); I != E; ++I) { 453 ArgumentSCCNodes.insert((*I)->Definition); 454 } 455 456 for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 457 E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { 458 ArgumentGraphNode *N = *I; 459 for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(), 460 UE = N->Uses.end(); UI != UE; ++UI) { 461 Argument *A = (*UI)->Definition; 462 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A)) 463 continue; 464 SCCCaptured = true; 465 break; 466 } 467 } 468 if (SCCCaptured) continue; 469 470 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 471 Argument *A = ArgumentSCC[i]->Definition; 472 A->addAttr(Attributes::get(B)); 473 ++NumNoCapture; 474 Changed = true; 475 } 476 } 477 478 return Changed; 479} 480 481/// IsFunctionMallocLike - A function is malloc-like if it returns either null 482/// or a pointer that doesn't alias any other pointer visible to the caller. 483bool FunctionAttrs::IsFunctionMallocLike(Function *F, 484 SmallPtrSet<Function*, 8> &SCCNodes) const { 485 UniqueVector<Value *> FlowsToReturn; 486 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 487 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 488 FlowsToReturn.insert(Ret->getReturnValue()); 489 490 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 491 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 492 493 if (Constant *C = dyn_cast<Constant>(RetVal)) { 494 if (!C->isNullValue() && !isa<UndefValue>(C)) 495 return false; 496 497 continue; 498 } 499 500 if (isa<Argument>(RetVal)) 501 return false; 502 503 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 504 switch (RVI->getOpcode()) { 505 // Extend the analysis by looking upwards. 506 case Instruction::BitCast: 507 case Instruction::GetElementPtr: 508 FlowsToReturn.insert(RVI->getOperand(0)); 509 continue; 510 case Instruction::Select: { 511 SelectInst *SI = cast<SelectInst>(RVI); 512 FlowsToReturn.insert(SI->getTrueValue()); 513 FlowsToReturn.insert(SI->getFalseValue()); 514 continue; 515 } 516 case Instruction::PHI: { 517 PHINode *PN = cast<PHINode>(RVI); 518 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 519 FlowsToReturn.insert(PN->getIncomingValue(i)); 520 continue; 521 } 522 523 // Check whether the pointer came from an allocation. 524 case Instruction::Alloca: 525 break; 526 case Instruction::Call: 527 case Instruction::Invoke: { 528 CallSite CS(RVI); 529 if (CS.paramHasAttr(0, Attributes::NoAlias)) 530 break; 531 if (CS.getCalledFunction() && 532 SCCNodes.count(CS.getCalledFunction())) 533 break; 534 } // fall-through 535 default: 536 return false; // Did not come from an allocation. 537 } 538 539 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 540 return false; 541 } 542 543 return true; 544} 545 546/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 547bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 548 SmallPtrSet<Function*, 8> SCCNodes; 549 550 // Fill SCCNodes with the elements of the SCC. Used for quickly 551 // looking up whether a given CallGraphNode is in this SCC. 552 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 553 SCCNodes.insert((*I)->getFunction()); 554 555 // Check each function in turn, determining which functions return noalias 556 // pointers. 557 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 558 Function *F = (*I)->getFunction(); 559 560 if (F == 0) 561 // External node - skip it; 562 return false; 563 564 // Already noalias. 565 if (F->doesNotAlias(0)) 566 continue; 567 568 // Definitions with weak linkage may be overridden at linktime, so 569 // treat them like declarations. 570 if (F->isDeclaration() || F->mayBeOverridden()) 571 return false; 572 573 // We annotate noalias return values, which are only applicable to 574 // pointer types. 575 if (!F->getReturnType()->isPointerTy()) 576 continue; 577 578 if (!IsFunctionMallocLike(F, SCCNodes)) 579 return false; 580 } 581 582 bool MadeChange = false; 583 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 584 Function *F = (*I)->getFunction(); 585 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 586 continue; 587 588 F->setDoesNotAlias(0); 589 ++NumNoAlias; 590 MadeChange = true; 591 } 592 593 return MadeChange; 594} 595 596bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 597 AA = &getAnalysis<AliasAnalysis>(); 598 599 bool Changed = AddReadAttrs(SCC); 600 Changed |= AddNoCaptureAttrs(SCC); 601 Changed |= AddNoAliasAttrs(SCC); 602 return Changed; 603} 604