1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===// 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. It does the 13 // same with function arguments independently, marking them readonly/ 14 // readnone/nocapture. Finally, well-known library call declarations 15 // are marked with all attributes that are consistent with the 16 // function's standard definition. This pass is implemented as a 17 // bottom-up traversal of the call-graph. 18 // 19 //===----------------------------------------------------------------------===// 20 21 #include "llvm/Transforms/IPO.h" 22 #include "llvm/ADT/SCCIterator.h" 23 #include "llvm/ADT/SetVector.h" 24 #include "llvm/ADT/SmallSet.h" 25 #include "llvm/ADT/Statistic.h" 26 #include "llvm/Analysis/AliasAnalysis.h" 27 #include "llvm/Analysis/CallGraph.h" 28 #include "llvm/Analysis/CallGraphSCCPass.h" 29 #include "llvm/Analysis/CaptureTracking.h" 30 #include "llvm/IR/GlobalVariable.h" 31 #include "llvm/IR/InstIterator.h" 32 #include "llvm/IR/IntrinsicInst.h" 33 #include "llvm/IR/LLVMContext.h" 34 #include "llvm/Target/TargetLibraryInfo.h" 35 using namespace llvm; 36 37 #define DEBUG_TYPE "functionattrs" 38 39 STATISTIC(NumReadNone, "Number of functions marked readnone"); 40 STATISTIC(NumReadOnly, "Number of functions marked readonly"); 41 STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 42 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone"); 43 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly"); 44 STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 45 STATISTIC(NumAnnotated, "Number of attributes added to library functions"); 46 47 namespace { 48 struct FunctionAttrs : public CallGraphSCCPass { 49 static char ID; // Pass identification, replacement for typeid 50 FunctionAttrs() : CallGraphSCCPass(ID), AA(nullptr) { 51 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); 52 } 53 54 // runOnSCC - Analyze the SCC, performing the transformation if possible. 55 bool runOnSCC(CallGraphSCC &SCC) override; 56 57 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 58 bool AddReadAttrs(const CallGraphSCC &SCC); 59 60 // AddArgumentAttrs - Deduce nocapture attributes for the SCC. 61 bool AddArgumentAttrs(const CallGraphSCC &SCC); 62 63 // IsFunctionMallocLike - Does this function allocate new memory? 64 bool IsFunctionMallocLike(Function *F, 65 SmallPtrSet<Function*, 8> &) const; 66 67 // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 68 bool AddNoAliasAttrs(const CallGraphSCC &SCC); 69 70 // Utility methods used by inferPrototypeAttributes to add attributes 71 // and maintain annotation statistics. 72 73 void setDoesNotAccessMemory(Function &F) { 74 if (!F.doesNotAccessMemory()) { 75 F.setDoesNotAccessMemory(); 76 ++NumAnnotated; 77 } 78 } 79 80 void setOnlyReadsMemory(Function &F) { 81 if (!F.onlyReadsMemory()) { 82 F.setOnlyReadsMemory(); 83 ++NumAnnotated; 84 } 85 } 86 87 void setDoesNotThrow(Function &F) { 88 if (!F.doesNotThrow()) { 89 F.setDoesNotThrow(); 90 ++NumAnnotated; 91 } 92 } 93 94 void setDoesNotCapture(Function &F, unsigned n) { 95 if (!F.doesNotCapture(n)) { 96 F.setDoesNotCapture(n); 97 ++NumAnnotated; 98 } 99 } 100 101 void setOnlyReadsMemory(Function &F, unsigned n) { 102 if (!F.onlyReadsMemory(n)) { 103 F.setOnlyReadsMemory(n); 104 ++NumAnnotated; 105 } 106 } 107 108 void setDoesNotAlias(Function &F, unsigned n) { 109 if (!F.doesNotAlias(n)) { 110 F.setDoesNotAlias(n); 111 ++NumAnnotated; 112 } 113 } 114 115 // inferPrototypeAttributes - Analyze the name and prototype of the 116 // given function and set any applicable attributes. Returns true 117 // if any attributes were set and false otherwise. 118 bool inferPrototypeAttributes(Function &F); 119 120 // annotateLibraryCalls - Adds attributes to well-known standard library 121 // call declarations. 122 bool annotateLibraryCalls(const CallGraphSCC &SCC); 123 124 void getAnalysisUsage(AnalysisUsage &AU) const override { 125 AU.setPreservesCFG(); 126 AU.addRequired<AliasAnalysis>(); 127 AU.addRequired<TargetLibraryInfo>(); 128 CallGraphSCCPass::getAnalysisUsage(AU); 129 } 130 131 private: 132 AliasAnalysis *AA; 133 TargetLibraryInfo *TLI; 134 }; 135 } 136 137 char FunctionAttrs::ID = 0; 138 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 139 "Deduce function attributes", false, false) 140 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 141 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 142 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 143 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 144 "Deduce function attributes", false, false) 145 146 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 147 148 149 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 150 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 151 SmallPtrSet<Function*, 8> SCCNodes; 152 153 // Fill SCCNodes with the elements of the SCC. Used for quickly 154 // looking up whether a given CallGraphNode is in this SCC. 155 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 156 SCCNodes.insert((*I)->getFunction()); 157 158 // Check if any of the functions in the SCC read or write memory. If they 159 // write memory then they can't be marked readnone or readonly. 160 bool ReadsMemory = false; 161 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 162 Function *F = (*I)->getFunction(); 163 164 if (!F) 165 // External node - may write memory. Just give up. 166 return false; 167 168 AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F); 169 if (MRB == AliasAnalysis::DoesNotAccessMemory) 170 // Already perfect! 171 continue; 172 173 // Definitions with weak linkage may be overridden at linktime with 174 // something that writes memory, so treat them like declarations. 175 if (F->isDeclaration() || F->mayBeOverridden()) { 176 if (!AliasAnalysis::onlyReadsMemory(MRB)) 177 // May write memory. Just give up. 178 return false; 179 180 ReadsMemory = true; 181 continue; 182 } 183 184 // Scan the function body for instructions that may read or write memory. 185 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 186 Instruction *I = &*II; 187 188 // Some instructions can be ignored even if they read or write memory. 189 // Detect these now, skipping to the next instruction if one is found. 190 CallSite CS(cast<Value>(I)); 191 if (CS) { 192 // Ignore calls to functions in the same SCC. 193 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 194 continue; 195 AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS); 196 // If the call doesn't access arbitrary memory, we may be able to 197 // figure out something. 198 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 199 // If the call does access argument pointees, check each argument. 200 if (AliasAnalysis::doesAccessArgPointees(MRB)) 201 // Check whether all pointer arguments point to local memory, and 202 // ignore calls that only access local memory. 203 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 204 CI != CE; ++CI) { 205 Value *Arg = *CI; 206 if (Arg->getType()->isPointerTy()) { 207 AliasAnalysis::Location Loc(Arg, 208 AliasAnalysis::UnknownSize, 209 I->getMetadata(LLVMContext::MD_tbaa)); 210 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) { 211 if (MRB & AliasAnalysis::Mod) 212 // Writes non-local memory. Give up. 213 return false; 214 if (MRB & AliasAnalysis::Ref) 215 // Ok, it reads non-local memory. 216 ReadsMemory = true; 217 } 218 } 219 } 220 continue; 221 } 222 // The call could access any memory. If that includes writes, give up. 223 if (MRB & AliasAnalysis::Mod) 224 return false; 225 // If it reads, note it. 226 if (MRB & AliasAnalysis::Ref) 227 ReadsMemory = true; 228 continue; 229 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 230 // Ignore non-volatile loads from local memory. (Atomic is okay here.) 231 if (!LI->isVolatile()) { 232 AliasAnalysis::Location Loc = AA->getLocation(LI); 233 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 234 continue; 235 } 236 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 237 // Ignore non-volatile stores to local memory. (Atomic is okay here.) 238 if (!SI->isVolatile()) { 239 AliasAnalysis::Location Loc = AA->getLocation(SI); 240 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 241 continue; 242 } 243 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) { 244 // Ignore vaargs on local memory. 245 AliasAnalysis::Location Loc = AA->getLocation(VI); 246 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 247 continue; 248 } 249 250 // Any remaining instructions need to be taken seriously! Check if they 251 // read or write memory. 252 if (I->mayWriteToMemory()) 253 // Writes memory. Just give up. 254 return false; 255 256 // If this instruction may read memory, remember that. 257 ReadsMemory |= I->mayReadFromMemory(); 258 } 259 } 260 261 // Success! Functions in this SCC do not access memory, or only read memory. 262 // Give them the appropriate attribute. 263 bool MadeChange = false; 264 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 265 Function *F = (*I)->getFunction(); 266 267 if (F->doesNotAccessMemory()) 268 // Already perfect! 269 continue; 270 271 if (F->onlyReadsMemory() && ReadsMemory) 272 // No change. 273 continue; 274 275 MadeChange = true; 276 277 // Clear out any existing attributes. 278 AttrBuilder B; 279 B.addAttribute(Attribute::ReadOnly) 280 .addAttribute(Attribute::ReadNone); 281 F->removeAttributes(AttributeSet::FunctionIndex, 282 AttributeSet::get(F->getContext(), 283 AttributeSet::FunctionIndex, B)); 284 285 // Add in the new attribute. 286 F->addAttribute(AttributeSet::FunctionIndex, 287 ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone); 288 289 if (ReadsMemory) 290 ++NumReadOnly; 291 else 292 ++NumReadNone; 293 } 294 295 return MadeChange; 296 } 297 298 namespace { 299 // For a given pointer Argument, this retains a list of Arguments of functions 300 // in the same SCC that the pointer data flows into. We use this to build an 301 // SCC of the arguments. 302 struct ArgumentGraphNode { 303 Argument *Definition; 304 SmallVector<ArgumentGraphNode*, 4> Uses; 305 }; 306 307 class ArgumentGraph { 308 // We store pointers to ArgumentGraphNode objects, so it's important that 309 // that they not move around upon insert. 310 typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy; 311 312 ArgumentMapTy ArgumentMap; 313 314 // There is no root node for the argument graph, in fact: 315 // void f(int *x, int *y) { if (...) f(x, y); } 316 // is an example where the graph is disconnected. The SCCIterator requires a 317 // single entry point, so we maintain a fake ("synthetic") root node that 318 // uses every node. Because the graph is directed and nothing points into 319 // the root, it will not participate in any SCCs (except for its own). 320 ArgumentGraphNode SyntheticRoot; 321 322 public: 323 ArgumentGraph() { SyntheticRoot.Definition = nullptr; } 324 325 typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator; 326 327 iterator begin() { return SyntheticRoot.Uses.begin(); } 328 iterator end() { return SyntheticRoot.Uses.end(); } 329 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } 330 331 ArgumentGraphNode *operator[](Argument *A) { 332 ArgumentGraphNode &Node = ArgumentMap[A]; 333 Node.Definition = A; 334 SyntheticRoot.Uses.push_back(&Node); 335 return &Node; 336 } 337 }; 338 339 // This tracker checks whether callees are in the SCC, and if so it does not 340 // consider that a capture, instead adding it to the "Uses" list and 341 // continuing with the analysis. 342 struct ArgumentUsesTracker : public CaptureTracker { 343 ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes) 344 : Captured(false), SCCNodes(SCCNodes) {} 345 346 void tooManyUses() override { Captured = true; } 347 348 bool captured(const Use *U) override { 349 CallSite CS(U->getUser()); 350 if (!CS.getInstruction()) { Captured = true; return true; } 351 352 Function *F = CS.getCalledFunction(); 353 if (!F || !SCCNodes.count(F)) { Captured = true; return true; } 354 355 bool Found = false; 356 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 357 for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end(); 358 PI != PE; ++PI, ++AI) { 359 if (AI == AE) { 360 assert(F->isVarArg() && "More params than args in non-varargs call"); 361 Captured = true; 362 return true; 363 } 364 if (PI == U) { 365 Uses.push_back(AI); 366 Found = true; 367 break; 368 } 369 } 370 assert(Found && "Capturing call-site captured nothing?"); 371 (void)Found; 372 return false; 373 } 374 375 bool Captured; // True only if certainly captured (used outside our SCC). 376 SmallVector<Argument*, 4> Uses; // Uses within our SCC. 377 378 const SmallPtrSet<Function*, 8> &SCCNodes; 379 }; 380 } 381 382 namespace llvm { 383 template<> struct GraphTraits<ArgumentGraphNode*> { 384 typedef ArgumentGraphNode NodeType; 385 typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType; 386 387 static inline NodeType *getEntryNode(NodeType *A) { return A; } 388 static inline ChildIteratorType child_begin(NodeType *N) { 389 return N->Uses.begin(); 390 } 391 static inline ChildIteratorType child_end(NodeType *N) { 392 return N->Uses.end(); 393 } 394 }; 395 template<> struct GraphTraits<ArgumentGraph*> 396 : public GraphTraits<ArgumentGraphNode*> { 397 static NodeType *getEntryNode(ArgumentGraph *AG) { 398 return AG->getEntryNode(); 399 } 400 static ChildIteratorType nodes_begin(ArgumentGraph *AG) { 401 return AG->begin(); 402 } 403 static ChildIteratorType nodes_end(ArgumentGraph *AG) { 404 return AG->end(); 405 } 406 }; 407 } 408 409 // Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone. 410 static Attribute::AttrKind 411 determinePointerReadAttrs(Argument *A, 412 const SmallPtrSet<Argument*, 8> &SCCNodes) { 413 414 SmallVector<Use*, 32> Worklist; 415 SmallSet<Use*, 32> Visited; 416 int Count = 0; 417 418 // inalloca arguments are always clobbered by the call. 419 if (A->hasInAllocaAttr()) 420 return Attribute::None; 421 422 bool IsRead = false; 423 // We don't need to track IsWritten. If A is written to, return immediately. 424 425 for (Use &U : A->uses()) { 426 if (Count++ >= 20) 427 return Attribute::None; 428 429 Visited.insert(&U); 430 Worklist.push_back(&U); 431 } 432 433 while (!Worklist.empty()) { 434 Use *U = Worklist.pop_back_val(); 435 Instruction *I = cast<Instruction>(U->getUser()); 436 Value *V = U->get(); 437 438 switch (I->getOpcode()) { 439 case Instruction::BitCast: 440 case Instruction::GetElementPtr: 441 case Instruction::PHI: 442 case Instruction::Select: 443 case Instruction::AddrSpaceCast: 444 // The original value is not read/written via this if the new value isn't. 445 for (Use &UU : I->uses()) 446 if (Visited.insert(&UU)) 447 Worklist.push_back(&UU); 448 break; 449 450 case Instruction::Call: 451 case Instruction::Invoke: { 452 bool Captures = true; 453 454 if (I->getType()->isVoidTy()) 455 Captures = false; 456 457 auto AddUsersToWorklistIfCapturing = [&] { 458 if (Captures) 459 for (Use &UU : I->uses()) 460 if (Visited.insert(&UU)) 461 Worklist.push_back(&UU); 462 }; 463 464 CallSite CS(I); 465 if (CS.doesNotAccessMemory()) { 466 AddUsersToWorklistIfCapturing(); 467 continue; 468 } 469 470 Function *F = CS.getCalledFunction(); 471 if (!F) { 472 if (CS.onlyReadsMemory()) { 473 IsRead = true; 474 AddUsersToWorklistIfCapturing(); 475 continue; 476 } 477 return Attribute::None; 478 } 479 480 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 481 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 482 for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) { 483 if (A->get() == V) { 484 if (AI == AE) { 485 assert(F->isVarArg() && 486 "More params than args in non-varargs call."); 487 return Attribute::None; 488 } 489 Captures &= !CS.doesNotCapture(A - B); 490 if (SCCNodes.count(AI)) 491 continue; 492 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B)) 493 return Attribute::None; 494 if (!CS.doesNotAccessMemory(A - B)) 495 IsRead = true; 496 } 497 } 498 AddUsersToWorklistIfCapturing(); 499 break; 500 } 501 502 case Instruction::Load: 503 IsRead = true; 504 break; 505 506 case Instruction::ICmp: 507 case Instruction::Ret: 508 break; 509 510 default: 511 return Attribute::None; 512 } 513 } 514 515 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone; 516 } 517 518 /// AddArgumentAttrs - Deduce nocapture attributes for the SCC. 519 bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { 520 bool Changed = false; 521 522 SmallPtrSet<Function*, 8> SCCNodes; 523 524 // Fill SCCNodes with the elements of the SCC. Used for quickly 525 // looking up whether a given CallGraphNode is in this SCC. 526 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 527 Function *F = (*I)->getFunction(); 528 if (F && !F->isDeclaration() && !F->mayBeOverridden()) 529 SCCNodes.insert(F); 530 } 531 532 ArgumentGraph AG; 533 534 AttrBuilder B; 535 B.addAttribute(Attribute::NoCapture); 536 537 // Check each function in turn, determining which pointer arguments are not 538 // captured. 539 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 540 Function *F = (*I)->getFunction(); 541 542 if (!F) 543 // External node - only a problem for arguments that we pass to it. 544 continue; 545 546 // Definitions with weak linkage may be overridden at linktime with 547 // something that captures pointers, so treat them like declarations. 548 if (F->isDeclaration() || F->mayBeOverridden()) 549 continue; 550 551 // Functions that are readonly (or readnone) and nounwind and don't return 552 // a value can't capture arguments. Don't analyze them. 553 if (F->onlyReadsMemory() && F->doesNotThrow() && 554 F->getReturnType()->isVoidTy()) { 555 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); 556 A != E; ++A) { 557 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 558 A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); 559 ++NumNoCapture; 560 Changed = true; 561 } 562 } 563 continue; 564 } 565 566 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); 567 A != E; ++A) { 568 if (!A->getType()->isPointerTy()) continue; 569 bool HasNonLocalUses = false; 570 if (!A->hasNoCaptureAttr()) { 571 ArgumentUsesTracker Tracker(SCCNodes); 572 PointerMayBeCaptured(A, &Tracker); 573 if (!Tracker.Captured) { 574 if (Tracker.Uses.empty()) { 575 // If it's trivially not captured, mark it nocapture now. 576 A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B)); 577 ++NumNoCapture; 578 Changed = true; 579 } else { 580 // If it's not trivially captured and not trivially not captured, 581 // then it must be calling into another function in our SCC. Save 582 // its particulars for Argument-SCC analysis later. 583 ArgumentGraphNode *Node = AG[A]; 584 for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(), 585 UE = Tracker.Uses.end(); UI != UE; ++UI) { 586 Node->Uses.push_back(AG[*UI]); 587 if (*UI != A) 588 HasNonLocalUses = true; 589 } 590 } 591 } 592 // Otherwise, it's captured. Don't bother doing SCC analysis on it. 593 } 594 if (!HasNonLocalUses && !A->onlyReadsMemory()) { 595 // Can we determine that it's readonly/readnone without doing an SCC? 596 // Note that we don't allow any calls at all here, or else our result 597 // will be dependent on the iteration order through the functions in the 598 // SCC. 599 SmallPtrSet<Argument*, 8> Self; 600 Self.insert(A); 601 Attribute::AttrKind R = determinePointerReadAttrs(A, Self); 602 if (R != Attribute::None) { 603 AttrBuilder B; 604 B.addAttribute(R); 605 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 606 Changed = true; 607 R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; 608 } 609 } 610 } 611 } 612 613 // The graph we've collected is partial because we stopped scanning for 614 // argument uses once we solved the argument trivially. These partial nodes 615 // show up as ArgumentGraphNode objects with an empty Uses list, and for 616 // these nodes the final decision about whether they capture has already been 617 // made. If the definition doesn't have a 'nocapture' attribute by now, it 618 // captures. 619 620 for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG); !I.isAtEnd(); ++I) { 621 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I; 622 if (ArgumentSCC.size() == 1) { 623 if (!ArgumentSCC[0]->Definition) continue; // synthetic root node 624 625 // eg. "void f(int* x) { if (...) f(x); }" 626 if (ArgumentSCC[0]->Uses.size() == 1 && 627 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) { 628 Argument *A = ArgumentSCC[0]->Definition; 629 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 630 ++NumNoCapture; 631 Changed = true; 632 } 633 continue; 634 } 635 636 bool SCCCaptured = false; 637 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); 638 I != E && !SCCCaptured; ++I) { 639 ArgumentGraphNode *Node = *I; 640 if (Node->Uses.empty()) { 641 if (!Node->Definition->hasNoCaptureAttr()) 642 SCCCaptured = true; 643 } 644 } 645 if (SCCCaptured) continue; 646 647 SmallPtrSet<Argument*, 8> ArgumentSCCNodes; 648 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for 649 // quickly looking up whether a given Argument is in this ArgumentSCC. 650 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) { 651 ArgumentSCCNodes.insert((*I)->Definition); 652 } 653 654 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); 655 I != E && !SCCCaptured; ++I) { 656 ArgumentGraphNode *N = *I; 657 for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(), 658 UE = N->Uses.end(); UI != UE; ++UI) { 659 Argument *A = (*UI)->Definition; 660 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A)) 661 continue; 662 SCCCaptured = true; 663 break; 664 } 665 } 666 if (SCCCaptured) continue; 667 668 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 669 Argument *A = ArgumentSCC[i]->Definition; 670 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 671 ++NumNoCapture; 672 Changed = true; 673 } 674 675 // We also want to compute readonly/readnone. With a small number of false 676 // negatives, we can assume that any pointer which is captured isn't going 677 // to be provably readonly or readnone, since by definition we can't 678 // analyze all uses of a captured pointer. 679 // 680 // The false negatives happen when the pointer is captured by a function 681 // that promises readonly/readnone behaviour on the pointer, then the 682 // pointer's lifetime ends before anything that writes to arbitrary memory. 683 // Also, a readonly/readnone pointer may be returned, but returning a 684 // pointer is capturing it. 685 686 Attribute::AttrKind ReadAttr = Attribute::ReadNone; 687 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 688 Argument *A = ArgumentSCC[i]->Definition; 689 Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes); 690 if (K == Attribute::ReadNone) 691 continue; 692 if (K == Attribute::ReadOnly) { 693 ReadAttr = Attribute::ReadOnly; 694 continue; 695 } 696 ReadAttr = K; 697 break; 698 } 699 700 if (ReadAttr != Attribute::None) { 701 AttrBuilder B; 702 B.addAttribute(ReadAttr); 703 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 704 Argument *A = ArgumentSCC[i]->Definition; 705 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 706 ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; 707 Changed = true; 708 } 709 } 710 } 711 712 return Changed; 713 } 714 715 /// IsFunctionMallocLike - A function is malloc-like if it returns either null 716 /// or a pointer that doesn't alias any other pointer visible to the caller. 717 bool FunctionAttrs::IsFunctionMallocLike(Function *F, 718 SmallPtrSet<Function*, 8> &SCCNodes) const { 719 SmallSetVector<Value *, 8> FlowsToReturn; 720 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 721 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 722 FlowsToReturn.insert(Ret->getReturnValue()); 723 724 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 725 Value *RetVal = FlowsToReturn[i]; 726 727 if (Constant *C = dyn_cast<Constant>(RetVal)) { 728 if (!C->isNullValue() && !isa<UndefValue>(C)) 729 return false; 730 731 continue; 732 } 733 734 if (isa<Argument>(RetVal)) 735 return false; 736 737 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 738 switch (RVI->getOpcode()) { 739 // Extend the analysis by looking upwards. 740 case Instruction::BitCast: 741 case Instruction::GetElementPtr: 742 case Instruction::AddrSpaceCast: 743 FlowsToReturn.insert(RVI->getOperand(0)); 744 continue; 745 case Instruction::Select: { 746 SelectInst *SI = cast<SelectInst>(RVI); 747 FlowsToReturn.insert(SI->getTrueValue()); 748 FlowsToReturn.insert(SI->getFalseValue()); 749 continue; 750 } 751 case Instruction::PHI: { 752 PHINode *PN = cast<PHINode>(RVI); 753 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 754 FlowsToReturn.insert(PN->getIncomingValue(i)); 755 continue; 756 } 757 758 // Check whether the pointer came from an allocation. 759 case Instruction::Alloca: 760 break; 761 case Instruction::Call: 762 case Instruction::Invoke: { 763 CallSite CS(RVI); 764 if (CS.paramHasAttr(0, Attribute::NoAlias)) 765 break; 766 if (CS.getCalledFunction() && 767 SCCNodes.count(CS.getCalledFunction())) 768 break; 769 } // fall-through 770 default: 771 return false; // Did not come from an allocation. 772 } 773 774 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 775 return false; 776 } 777 778 return true; 779 } 780 781 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 782 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 783 SmallPtrSet<Function*, 8> SCCNodes; 784 785 // Fill SCCNodes with the elements of the SCC. Used for quickly 786 // looking up whether a given CallGraphNode is in this SCC. 787 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 788 SCCNodes.insert((*I)->getFunction()); 789 790 // Check each function in turn, determining which functions return noalias 791 // pointers. 792 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 793 Function *F = (*I)->getFunction(); 794 795 if (!F) 796 // External node - skip it; 797 return false; 798 799 // Already noalias. 800 if (F->doesNotAlias(0)) 801 continue; 802 803 // Definitions with weak linkage may be overridden at linktime, so 804 // treat them like declarations. 805 if (F->isDeclaration() || F->mayBeOverridden()) 806 return false; 807 808 // We annotate noalias return values, which are only applicable to 809 // pointer types. 810 if (!F->getReturnType()->isPointerTy()) 811 continue; 812 813 if (!IsFunctionMallocLike(F, SCCNodes)) 814 return false; 815 } 816 817 bool MadeChange = false; 818 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 819 Function *F = (*I)->getFunction(); 820 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 821 continue; 822 823 F->setDoesNotAlias(0); 824 ++NumNoAlias; 825 MadeChange = true; 826 } 827 828 return MadeChange; 829 } 830 831 /// inferPrototypeAttributes - Analyze the name and prototype of the 832 /// given function and set any applicable attributes. Returns true 833 /// if any attributes were set and false otherwise. 834 bool FunctionAttrs::inferPrototypeAttributes(Function &F) { 835 FunctionType *FTy = F.getFunctionType(); 836 LibFunc::Func TheLibFunc; 837 if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc))) 838 return false; 839 840 switch (TheLibFunc) { 841 case LibFunc::strlen: 842 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 843 return false; 844 setOnlyReadsMemory(F); 845 setDoesNotThrow(F); 846 setDoesNotCapture(F, 1); 847 break; 848 case LibFunc::strchr: 849 case LibFunc::strrchr: 850 if (FTy->getNumParams() != 2 || 851 !FTy->getParamType(0)->isPointerTy() || 852 !FTy->getParamType(1)->isIntegerTy()) 853 return false; 854 setOnlyReadsMemory(F); 855 setDoesNotThrow(F); 856 break; 857 case LibFunc::strtol: 858 case LibFunc::strtod: 859 case LibFunc::strtof: 860 case LibFunc::strtoul: 861 case LibFunc::strtoll: 862 case LibFunc::strtold: 863 case LibFunc::strtoull: 864 if (FTy->getNumParams() < 2 || 865 !FTy->getParamType(1)->isPointerTy()) 866 return false; 867 setDoesNotThrow(F); 868 setDoesNotCapture(F, 2); 869 setOnlyReadsMemory(F, 1); 870 break; 871 case LibFunc::strcpy: 872 case LibFunc::stpcpy: 873 case LibFunc::strcat: 874 case LibFunc::strncat: 875 case LibFunc::strncpy: 876 case LibFunc::stpncpy: 877 if (FTy->getNumParams() < 2 || 878 !FTy->getParamType(1)->isPointerTy()) 879 return false; 880 setDoesNotThrow(F); 881 setDoesNotCapture(F, 2); 882 setOnlyReadsMemory(F, 2); 883 break; 884 case LibFunc::strxfrm: 885 if (FTy->getNumParams() != 3 || 886 !FTy->getParamType(0)->isPointerTy() || 887 !FTy->getParamType(1)->isPointerTy()) 888 return false; 889 setDoesNotThrow(F); 890 setDoesNotCapture(F, 1); 891 setDoesNotCapture(F, 2); 892 setOnlyReadsMemory(F, 2); 893 break; 894 case LibFunc::strcmp: //0,1 895 case LibFunc::strspn: // 0,1 896 case LibFunc::strncmp: // 0,1 897 case LibFunc::strcspn: //0,1 898 case LibFunc::strcoll: //0,1 899 case LibFunc::strcasecmp: // 0,1 900 case LibFunc::strncasecmp: // 901 if (FTy->getNumParams() < 2 || 902 !FTy->getParamType(0)->isPointerTy() || 903 !FTy->getParamType(1)->isPointerTy()) 904 return false; 905 setOnlyReadsMemory(F); 906 setDoesNotThrow(F); 907 setDoesNotCapture(F, 1); 908 setDoesNotCapture(F, 2); 909 break; 910 case LibFunc::strstr: 911 case LibFunc::strpbrk: 912 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 913 return false; 914 setOnlyReadsMemory(F); 915 setDoesNotThrow(F); 916 setDoesNotCapture(F, 2); 917 break; 918 case LibFunc::strtok: 919 case LibFunc::strtok_r: 920 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy()) 921 return false; 922 setDoesNotThrow(F); 923 setDoesNotCapture(F, 2); 924 setOnlyReadsMemory(F, 2); 925 break; 926 case LibFunc::scanf: 927 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) 928 return false; 929 setDoesNotThrow(F); 930 setDoesNotCapture(F, 1); 931 setOnlyReadsMemory(F, 1); 932 break; 933 case LibFunc::setbuf: 934 case LibFunc::setvbuf: 935 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy()) 936 return false; 937 setDoesNotThrow(F); 938 setDoesNotCapture(F, 1); 939 break; 940 case LibFunc::strdup: 941 case LibFunc::strndup: 942 if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() || 943 !FTy->getParamType(0)->isPointerTy()) 944 return false; 945 setDoesNotThrow(F); 946 setDoesNotAlias(F, 0); 947 setDoesNotCapture(F, 1); 948 setOnlyReadsMemory(F, 1); 949 break; 950 case LibFunc::stat: 951 case LibFunc::statvfs: 952 if (FTy->getNumParams() < 2 || 953 !FTy->getParamType(0)->isPointerTy() || 954 !FTy->getParamType(1)->isPointerTy()) 955 return false; 956 setDoesNotThrow(F); 957 setDoesNotCapture(F, 1); 958 setDoesNotCapture(F, 2); 959 setOnlyReadsMemory(F, 1); 960 break; 961 case LibFunc::sscanf: 962 if (FTy->getNumParams() < 2 || 963 !FTy->getParamType(0)->isPointerTy() || 964 !FTy->getParamType(1)->isPointerTy()) 965 return false; 966 setDoesNotThrow(F); 967 setDoesNotCapture(F, 1); 968 setDoesNotCapture(F, 2); 969 setOnlyReadsMemory(F, 1); 970 setOnlyReadsMemory(F, 2); 971 break; 972 case LibFunc::sprintf: 973 if (FTy->getNumParams() < 2 || 974 !FTy->getParamType(0)->isPointerTy() || 975 !FTy->getParamType(1)->isPointerTy()) 976 return false; 977 setDoesNotThrow(F); 978 setDoesNotCapture(F, 1); 979 setDoesNotCapture(F, 2); 980 setOnlyReadsMemory(F, 2); 981 break; 982 case LibFunc::snprintf: 983 if (FTy->getNumParams() != 3 || 984 !FTy->getParamType(0)->isPointerTy() || 985 !FTy->getParamType(2)->isPointerTy()) 986 return false; 987 setDoesNotThrow(F); 988 setDoesNotCapture(F, 1); 989 setDoesNotCapture(F, 3); 990 setOnlyReadsMemory(F, 3); 991 break; 992 case LibFunc::setitimer: 993 if (FTy->getNumParams() != 3 || 994 !FTy->getParamType(1)->isPointerTy() || 995 !FTy->getParamType(2)->isPointerTy()) 996 return false; 997 setDoesNotThrow(F); 998 setDoesNotCapture(F, 2); 999 setDoesNotCapture(F, 3); 1000 setOnlyReadsMemory(F, 2); 1001 break; 1002 case LibFunc::system: 1003 if (FTy->getNumParams() != 1 || 1004 !FTy->getParamType(0)->isPointerTy()) 1005 return false; 1006 // May throw; "system" is a valid pthread cancellation point. 1007 setDoesNotCapture(F, 1); 1008 setOnlyReadsMemory(F, 1); 1009 break; 1010 case LibFunc::malloc: 1011 if (FTy->getNumParams() != 1 || 1012 !FTy->getReturnType()->isPointerTy()) 1013 return false; 1014 setDoesNotThrow(F); 1015 setDoesNotAlias(F, 0); 1016 break; 1017 case LibFunc::memcmp: 1018 if (FTy->getNumParams() != 3 || 1019 !FTy->getParamType(0)->isPointerTy() || 1020 !FTy->getParamType(1)->isPointerTy()) 1021 return false; 1022 setOnlyReadsMemory(F); 1023 setDoesNotThrow(F); 1024 setDoesNotCapture(F, 1); 1025 setDoesNotCapture(F, 2); 1026 break; 1027 case LibFunc::memchr: 1028 case LibFunc::memrchr: 1029 if (FTy->getNumParams() != 3) 1030 return false; 1031 setOnlyReadsMemory(F); 1032 setDoesNotThrow(F); 1033 break; 1034 case LibFunc::modf: 1035 case LibFunc::modff: 1036 case LibFunc::modfl: 1037 if (FTy->getNumParams() < 2 || 1038 !FTy->getParamType(1)->isPointerTy()) 1039 return false; 1040 setDoesNotThrow(F); 1041 setDoesNotCapture(F, 2); 1042 break; 1043 case LibFunc::memcpy: 1044 case LibFunc::memccpy: 1045 case LibFunc::memmove: 1046 if (FTy->getNumParams() < 2 || 1047 !FTy->getParamType(1)->isPointerTy()) 1048 return false; 1049 setDoesNotThrow(F); 1050 setDoesNotCapture(F, 2); 1051 setOnlyReadsMemory(F, 2); 1052 break; 1053 case LibFunc::memalign: 1054 if (!FTy->getReturnType()->isPointerTy()) 1055 return false; 1056 setDoesNotAlias(F, 0); 1057 break; 1058 case LibFunc::mkdir: 1059 if (FTy->getNumParams() == 0 || 1060 !FTy->getParamType(0)->isPointerTy()) 1061 return false; 1062 setDoesNotThrow(F); 1063 setDoesNotCapture(F, 1); 1064 setOnlyReadsMemory(F, 1); 1065 break; 1066 case LibFunc::mktime: 1067 if (FTy->getNumParams() == 0 || 1068 !FTy->getParamType(0)->isPointerTy()) 1069 return false; 1070 setDoesNotThrow(F); 1071 setDoesNotCapture(F, 1); 1072 break; 1073 case LibFunc::realloc: 1074 if (FTy->getNumParams() != 2 || 1075 !FTy->getParamType(0)->isPointerTy() || 1076 !FTy->getReturnType()->isPointerTy()) 1077 return false; 1078 setDoesNotThrow(F); 1079 setDoesNotAlias(F, 0); 1080 setDoesNotCapture(F, 1); 1081 break; 1082 case LibFunc::read: 1083 if (FTy->getNumParams() != 3 || 1084 !FTy->getParamType(1)->isPointerTy()) 1085 return false; 1086 // May throw; "read" is a valid pthread cancellation point. 1087 setDoesNotCapture(F, 2); 1088 break; 1089 case LibFunc::rewind: 1090 if (FTy->getNumParams() < 1 || 1091 !FTy->getParamType(0)->isPointerTy()) 1092 return false; 1093 setDoesNotThrow(F); 1094 setDoesNotCapture(F, 1); 1095 break; 1096 case LibFunc::rmdir: 1097 case LibFunc::remove: 1098 case LibFunc::realpath: 1099 if (FTy->getNumParams() < 1 || 1100 !FTy->getParamType(0)->isPointerTy()) 1101 return false; 1102 setDoesNotThrow(F); 1103 setDoesNotCapture(F, 1); 1104 setOnlyReadsMemory(F, 1); 1105 break; 1106 case LibFunc::rename: 1107 if (FTy->getNumParams() < 2 || 1108 !FTy->getParamType(0)->isPointerTy() || 1109 !FTy->getParamType(1)->isPointerTy()) 1110 return false; 1111 setDoesNotThrow(F); 1112 setDoesNotCapture(F, 1); 1113 setDoesNotCapture(F, 2); 1114 setOnlyReadsMemory(F, 1); 1115 setOnlyReadsMemory(F, 2); 1116 break; 1117 case LibFunc::readlink: 1118 if (FTy->getNumParams() < 2 || 1119 !FTy->getParamType(0)->isPointerTy() || 1120 !FTy->getParamType(1)->isPointerTy()) 1121 return false; 1122 setDoesNotThrow(F); 1123 setDoesNotCapture(F, 1); 1124 setDoesNotCapture(F, 2); 1125 setOnlyReadsMemory(F, 1); 1126 break; 1127 case LibFunc::write: 1128 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy()) 1129 return false; 1130 // May throw; "write" is a valid pthread cancellation point. 1131 setDoesNotCapture(F, 2); 1132 setOnlyReadsMemory(F, 2); 1133 break; 1134 case LibFunc::bcopy: 1135 if (FTy->getNumParams() != 3 || 1136 !FTy->getParamType(0)->isPointerTy() || 1137 !FTy->getParamType(1)->isPointerTy()) 1138 return false; 1139 setDoesNotThrow(F); 1140 setDoesNotCapture(F, 1); 1141 setDoesNotCapture(F, 2); 1142 setOnlyReadsMemory(F, 1); 1143 break; 1144 case LibFunc::bcmp: 1145 if (FTy->getNumParams() != 3 || 1146 !FTy->getParamType(0)->isPointerTy() || 1147 !FTy->getParamType(1)->isPointerTy()) 1148 return false; 1149 setDoesNotThrow(F); 1150 setOnlyReadsMemory(F); 1151 setDoesNotCapture(F, 1); 1152 setDoesNotCapture(F, 2); 1153 break; 1154 case LibFunc::bzero: 1155 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) 1156 return false; 1157 setDoesNotThrow(F); 1158 setDoesNotCapture(F, 1); 1159 break; 1160 case LibFunc::calloc: 1161 if (FTy->getNumParams() != 2 || 1162 !FTy->getReturnType()->isPointerTy()) 1163 return false; 1164 setDoesNotThrow(F); 1165 setDoesNotAlias(F, 0); 1166 break; 1167 case LibFunc::chmod: 1168 case LibFunc::chown: 1169 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 1170 return false; 1171 setDoesNotThrow(F); 1172 setDoesNotCapture(F, 1); 1173 setOnlyReadsMemory(F, 1); 1174 break; 1175 case LibFunc::ctermid: 1176 case LibFunc::clearerr: 1177 case LibFunc::closedir: 1178 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 1179 return false; 1180 setDoesNotThrow(F); 1181 setDoesNotCapture(F, 1); 1182 break; 1183 case LibFunc::atoi: 1184 case LibFunc::atol: 1185 case LibFunc::atof: 1186 case LibFunc::atoll: 1187 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1188 return false; 1189 setDoesNotThrow(F); 1190 setOnlyReadsMemory(F); 1191 setDoesNotCapture(F, 1); 1192 break; 1193 case LibFunc::access: 1194 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) 1195 return false; 1196 setDoesNotThrow(F); 1197 setDoesNotCapture(F, 1); 1198 setOnlyReadsMemory(F, 1); 1199 break; 1200 case LibFunc::fopen: 1201 if (FTy->getNumParams() != 2 || 1202 !FTy->getReturnType()->isPointerTy() || 1203 !FTy->getParamType(0)->isPointerTy() || 1204 !FTy->getParamType(1)->isPointerTy()) 1205 return false; 1206 setDoesNotThrow(F); 1207 setDoesNotAlias(F, 0); 1208 setDoesNotCapture(F, 1); 1209 setDoesNotCapture(F, 2); 1210 setOnlyReadsMemory(F, 1); 1211 setOnlyReadsMemory(F, 2); 1212 break; 1213 case LibFunc::fdopen: 1214 if (FTy->getNumParams() != 2 || 1215 !FTy->getReturnType()->isPointerTy() || 1216 !FTy->getParamType(1)->isPointerTy()) 1217 return false; 1218 setDoesNotThrow(F); 1219 setDoesNotAlias(F, 0); 1220 setDoesNotCapture(F, 2); 1221 setOnlyReadsMemory(F, 2); 1222 break; 1223 case LibFunc::feof: 1224 case LibFunc::free: 1225 case LibFunc::fseek: 1226 case LibFunc::ftell: 1227 case LibFunc::fgetc: 1228 case LibFunc::fseeko: 1229 case LibFunc::ftello: 1230 case LibFunc::fileno: 1231 case LibFunc::fflush: 1232 case LibFunc::fclose: 1233 case LibFunc::fsetpos: 1234 case LibFunc::flockfile: 1235 case LibFunc::funlockfile: 1236 case LibFunc::ftrylockfile: 1237 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 1238 return false; 1239 setDoesNotThrow(F); 1240 setDoesNotCapture(F, 1); 1241 break; 1242 case LibFunc::ferror: 1243 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1244 return false; 1245 setDoesNotThrow(F); 1246 setDoesNotCapture(F, 1); 1247 setOnlyReadsMemory(F); 1248 break; 1249 case LibFunc::fputc: 1250 case LibFunc::fstat: 1251 case LibFunc::frexp: 1252 case LibFunc::frexpf: 1253 case LibFunc::frexpl: 1254 case LibFunc::fstatvfs: 1255 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1256 return false; 1257 setDoesNotThrow(F); 1258 setDoesNotCapture(F, 2); 1259 break; 1260 case LibFunc::fgets: 1261 if (FTy->getNumParams() != 3 || 1262 !FTy->getParamType(0)->isPointerTy() || 1263 !FTy->getParamType(2)->isPointerTy()) 1264 return false; 1265 setDoesNotThrow(F); 1266 setDoesNotCapture(F, 3); 1267 break; 1268 case LibFunc::fread: 1269 if (FTy->getNumParams() != 4 || 1270 !FTy->getParamType(0)->isPointerTy() || 1271 !FTy->getParamType(3)->isPointerTy()) 1272 return false; 1273 setDoesNotThrow(F); 1274 setDoesNotCapture(F, 1); 1275 setDoesNotCapture(F, 4); 1276 break; 1277 case LibFunc::fwrite: 1278 if (FTy->getNumParams() != 4 || 1279 !FTy->getParamType(0)->isPointerTy() || 1280 !FTy->getParamType(3)->isPointerTy()) 1281 return false; 1282 setDoesNotThrow(F); 1283 setDoesNotCapture(F, 1); 1284 setDoesNotCapture(F, 4); 1285 break; 1286 case LibFunc::fputs: 1287 if (FTy->getNumParams() < 2 || 1288 !FTy->getParamType(0)->isPointerTy() || 1289 !FTy->getParamType(1)->isPointerTy()) 1290 return false; 1291 setDoesNotThrow(F); 1292 setDoesNotCapture(F, 1); 1293 setDoesNotCapture(F, 2); 1294 setOnlyReadsMemory(F, 1); 1295 break; 1296 case LibFunc::fscanf: 1297 case LibFunc::fprintf: 1298 if (FTy->getNumParams() < 2 || 1299 !FTy->getParamType(0)->isPointerTy() || 1300 !FTy->getParamType(1)->isPointerTy()) 1301 return false; 1302 setDoesNotThrow(F); 1303 setDoesNotCapture(F, 1); 1304 setDoesNotCapture(F, 2); 1305 setOnlyReadsMemory(F, 2); 1306 break; 1307 case LibFunc::fgetpos: 1308 if (FTy->getNumParams() < 2 || 1309 !FTy->getParamType(0)->isPointerTy() || 1310 !FTy->getParamType(1)->isPointerTy()) 1311 return false; 1312 setDoesNotThrow(F); 1313 setDoesNotCapture(F, 1); 1314 setDoesNotCapture(F, 2); 1315 break; 1316 case LibFunc::getc: 1317 case LibFunc::getlogin_r: 1318 case LibFunc::getc_unlocked: 1319 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 1320 return false; 1321 setDoesNotThrow(F); 1322 setDoesNotCapture(F, 1); 1323 break; 1324 case LibFunc::getenv: 1325 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1326 return false; 1327 setDoesNotThrow(F); 1328 setOnlyReadsMemory(F); 1329 setDoesNotCapture(F, 1); 1330 break; 1331 case LibFunc::gets: 1332 case LibFunc::getchar: 1333 setDoesNotThrow(F); 1334 break; 1335 case LibFunc::getitimer: 1336 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1337 return false; 1338 setDoesNotThrow(F); 1339 setDoesNotCapture(F, 2); 1340 break; 1341 case LibFunc::getpwnam: 1342 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1343 return false; 1344 setDoesNotThrow(F); 1345 setDoesNotCapture(F, 1); 1346 setOnlyReadsMemory(F, 1); 1347 break; 1348 case LibFunc::ungetc: 1349 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1350 return false; 1351 setDoesNotThrow(F); 1352 setDoesNotCapture(F, 2); 1353 break; 1354 case LibFunc::uname: 1355 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1356 return false; 1357 setDoesNotThrow(F); 1358 setDoesNotCapture(F, 1); 1359 break; 1360 case LibFunc::unlink: 1361 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1362 return false; 1363 setDoesNotThrow(F); 1364 setDoesNotCapture(F, 1); 1365 setOnlyReadsMemory(F, 1); 1366 break; 1367 case LibFunc::unsetenv: 1368 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1369 return false; 1370 setDoesNotThrow(F); 1371 setDoesNotCapture(F, 1); 1372 setOnlyReadsMemory(F, 1); 1373 break; 1374 case LibFunc::utime: 1375 case LibFunc::utimes: 1376 if (FTy->getNumParams() != 2 || 1377 !FTy->getParamType(0)->isPointerTy() || 1378 !FTy->getParamType(1)->isPointerTy()) 1379 return false; 1380 setDoesNotThrow(F); 1381 setDoesNotCapture(F, 1); 1382 setDoesNotCapture(F, 2); 1383 setOnlyReadsMemory(F, 1); 1384 setOnlyReadsMemory(F, 2); 1385 break; 1386 case LibFunc::putc: 1387 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1388 return false; 1389 setDoesNotThrow(F); 1390 setDoesNotCapture(F, 2); 1391 break; 1392 case LibFunc::puts: 1393 case LibFunc::printf: 1394 case LibFunc::perror: 1395 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1396 return false; 1397 setDoesNotThrow(F); 1398 setDoesNotCapture(F, 1); 1399 setOnlyReadsMemory(F, 1); 1400 break; 1401 case LibFunc::pread: 1402 if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy()) 1403 return false; 1404 // May throw; "pread" is a valid pthread cancellation point. 1405 setDoesNotCapture(F, 2); 1406 break; 1407 case LibFunc::pwrite: 1408 if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy()) 1409 return false; 1410 // May throw; "pwrite" is a valid pthread cancellation point. 1411 setDoesNotCapture(F, 2); 1412 setOnlyReadsMemory(F, 2); 1413 break; 1414 case LibFunc::putchar: 1415 setDoesNotThrow(F); 1416 break; 1417 case LibFunc::popen: 1418 if (FTy->getNumParams() != 2 || 1419 !FTy->getReturnType()->isPointerTy() || 1420 !FTy->getParamType(0)->isPointerTy() || 1421 !FTy->getParamType(1)->isPointerTy()) 1422 return false; 1423 setDoesNotThrow(F); 1424 setDoesNotAlias(F, 0); 1425 setDoesNotCapture(F, 1); 1426 setDoesNotCapture(F, 2); 1427 setOnlyReadsMemory(F, 1); 1428 setOnlyReadsMemory(F, 2); 1429 break; 1430 case LibFunc::pclose: 1431 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1432 return false; 1433 setDoesNotThrow(F); 1434 setDoesNotCapture(F, 1); 1435 break; 1436 case LibFunc::vscanf: 1437 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1438 return false; 1439 setDoesNotThrow(F); 1440 setDoesNotCapture(F, 1); 1441 setOnlyReadsMemory(F, 1); 1442 break; 1443 case LibFunc::vsscanf: 1444 if (FTy->getNumParams() != 3 || 1445 !FTy->getParamType(1)->isPointerTy() || 1446 !FTy->getParamType(2)->isPointerTy()) 1447 return false; 1448 setDoesNotThrow(F); 1449 setDoesNotCapture(F, 1); 1450 setDoesNotCapture(F, 2); 1451 setOnlyReadsMemory(F, 1); 1452 setOnlyReadsMemory(F, 2); 1453 break; 1454 case LibFunc::vfscanf: 1455 if (FTy->getNumParams() != 3 || 1456 !FTy->getParamType(1)->isPointerTy() || 1457 !FTy->getParamType(2)->isPointerTy()) 1458 return false; 1459 setDoesNotThrow(F); 1460 setDoesNotCapture(F, 1); 1461 setDoesNotCapture(F, 2); 1462 setOnlyReadsMemory(F, 2); 1463 break; 1464 case LibFunc::valloc: 1465 if (!FTy->getReturnType()->isPointerTy()) 1466 return false; 1467 setDoesNotThrow(F); 1468 setDoesNotAlias(F, 0); 1469 break; 1470 case LibFunc::vprintf: 1471 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy()) 1472 return false; 1473 setDoesNotThrow(F); 1474 setDoesNotCapture(F, 1); 1475 setOnlyReadsMemory(F, 1); 1476 break; 1477 case LibFunc::vfprintf: 1478 case LibFunc::vsprintf: 1479 if (FTy->getNumParams() != 3 || 1480 !FTy->getParamType(0)->isPointerTy() || 1481 !FTy->getParamType(1)->isPointerTy()) 1482 return false; 1483 setDoesNotThrow(F); 1484 setDoesNotCapture(F, 1); 1485 setDoesNotCapture(F, 2); 1486 setOnlyReadsMemory(F, 2); 1487 break; 1488 case LibFunc::vsnprintf: 1489 if (FTy->getNumParams() != 4 || 1490 !FTy->getParamType(0)->isPointerTy() || 1491 !FTy->getParamType(2)->isPointerTy()) 1492 return false; 1493 setDoesNotThrow(F); 1494 setDoesNotCapture(F, 1); 1495 setDoesNotCapture(F, 3); 1496 setOnlyReadsMemory(F, 3); 1497 break; 1498 case LibFunc::open: 1499 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy()) 1500 return false; 1501 // May throw; "open" is a valid pthread cancellation point. 1502 setDoesNotCapture(F, 1); 1503 setOnlyReadsMemory(F, 1); 1504 break; 1505 case LibFunc::opendir: 1506 if (FTy->getNumParams() != 1 || 1507 !FTy->getReturnType()->isPointerTy() || 1508 !FTy->getParamType(0)->isPointerTy()) 1509 return false; 1510 setDoesNotThrow(F); 1511 setDoesNotAlias(F, 0); 1512 setDoesNotCapture(F, 1); 1513 setOnlyReadsMemory(F, 1); 1514 break; 1515 case LibFunc::tmpfile: 1516 if (!FTy->getReturnType()->isPointerTy()) 1517 return false; 1518 setDoesNotThrow(F); 1519 setDoesNotAlias(F, 0); 1520 break; 1521 case LibFunc::times: 1522 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1523 return false; 1524 setDoesNotThrow(F); 1525 setDoesNotCapture(F, 1); 1526 break; 1527 case LibFunc::htonl: 1528 case LibFunc::htons: 1529 case LibFunc::ntohl: 1530 case LibFunc::ntohs: 1531 setDoesNotThrow(F); 1532 setDoesNotAccessMemory(F); 1533 break; 1534 case LibFunc::lstat: 1535 if (FTy->getNumParams() != 2 || 1536 !FTy->getParamType(0)->isPointerTy() || 1537 !FTy->getParamType(1)->isPointerTy()) 1538 return false; 1539 setDoesNotThrow(F); 1540 setDoesNotCapture(F, 1); 1541 setDoesNotCapture(F, 2); 1542 setOnlyReadsMemory(F, 1); 1543 break; 1544 case LibFunc::lchown: 1545 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy()) 1546 return false; 1547 setDoesNotThrow(F); 1548 setDoesNotCapture(F, 1); 1549 setOnlyReadsMemory(F, 1); 1550 break; 1551 case LibFunc::qsort: 1552 if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy()) 1553 return false; 1554 // May throw; places call through function pointer. 1555 setDoesNotCapture(F, 4); 1556 break; 1557 case LibFunc::dunder_strdup: 1558 case LibFunc::dunder_strndup: 1559 if (FTy->getNumParams() < 1 || 1560 !FTy->getReturnType()->isPointerTy() || 1561 !FTy->getParamType(0)->isPointerTy()) 1562 return false; 1563 setDoesNotThrow(F); 1564 setDoesNotAlias(F, 0); 1565 setDoesNotCapture(F, 1); 1566 setOnlyReadsMemory(F, 1); 1567 break; 1568 case LibFunc::dunder_strtok_r: 1569 if (FTy->getNumParams() != 3 || 1570 !FTy->getParamType(1)->isPointerTy()) 1571 return false; 1572 setDoesNotThrow(F); 1573 setDoesNotCapture(F, 2); 1574 setOnlyReadsMemory(F, 2); 1575 break; 1576 case LibFunc::under_IO_getc: 1577 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 1578 return false; 1579 setDoesNotThrow(F); 1580 setDoesNotCapture(F, 1); 1581 break; 1582 case LibFunc::under_IO_putc: 1583 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1584 return false; 1585 setDoesNotThrow(F); 1586 setDoesNotCapture(F, 2); 1587 break; 1588 case LibFunc::dunder_isoc99_scanf: 1589 if (FTy->getNumParams() < 1 || 1590 !FTy->getParamType(0)->isPointerTy()) 1591 return false; 1592 setDoesNotThrow(F); 1593 setDoesNotCapture(F, 1); 1594 setOnlyReadsMemory(F, 1); 1595 break; 1596 case LibFunc::stat64: 1597 case LibFunc::lstat64: 1598 case LibFunc::statvfs64: 1599 if (FTy->getNumParams() < 1 || 1600 !FTy->getParamType(0)->isPointerTy() || 1601 !FTy->getParamType(1)->isPointerTy()) 1602 return false; 1603 setDoesNotThrow(F); 1604 setDoesNotCapture(F, 1); 1605 setDoesNotCapture(F, 2); 1606 setOnlyReadsMemory(F, 1); 1607 break; 1608 case LibFunc::dunder_isoc99_sscanf: 1609 if (FTy->getNumParams() < 1 || 1610 !FTy->getParamType(0)->isPointerTy() || 1611 !FTy->getParamType(1)->isPointerTy()) 1612 return false; 1613 setDoesNotThrow(F); 1614 setDoesNotCapture(F, 1); 1615 setDoesNotCapture(F, 2); 1616 setOnlyReadsMemory(F, 1); 1617 setOnlyReadsMemory(F, 2); 1618 break; 1619 case LibFunc::fopen64: 1620 if (FTy->getNumParams() != 2 || 1621 !FTy->getReturnType()->isPointerTy() || 1622 !FTy->getParamType(0)->isPointerTy() || 1623 !FTy->getParamType(1)->isPointerTy()) 1624 return false; 1625 setDoesNotThrow(F); 1626 setDoesNotAlias(F, 0); 1627 setDoesNotCapture(F, 1); 1628 setDoesNotCapture(F, 2); 1629 setOnlyReadsMemory(F, 1); 1630 setOnlyReadsMemory(F, 2); 1631 break; 1632 case LibFunc::fseeko64: 1633 case LibFunc::ftello64: 1634 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy()) 1635 return false; 1636 setDoesNotThrow(F); 1637 setDoesNotCapture(F, 1); 1638 break; 1639 case LibFunc::tmpfile64: 1640 if (!FTy->getReturnType()->isPointerTy()) 1641 return false; 1642 setDoesNotThrow(F); 1643 setDoesNotAlias(F, 0); 1644 break; 1645 case LibFunc::fstat64: 1646 case LibFunc::fstatvfs64: 1647 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy()) 1648 return false; 1649 setDoesNotThrow(F); 1650 setDoesNotCapture(F, 2); 1651 break; 1652 case LibFunc::open64: 1653 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy()) 1654 return false; 1655 // May throw; "open" is a valid pthread cancellation point. 1656 setDoesNotCapture(F, 1); 1657 setOnlyReadsMemory(F, 1); 1658 break; 1659 case LibFunc::gettimeofday: 1660 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() || 1661 !FTy->getParamType(1)->isPointerTy()) 1662 return false; 1663 // Currently some platforms have the restrict keyword on the arguments to 1664 // gettimeofday. To be conservative, do not add noalias to gettimeofday's 1665 // arguments. 1666 setDoesNotThrow(F); 1667 setDoesNotCapture(F, 1); 1668 setDoesNotCapture(F, 2); 1669 break; 1670 default: 1671 // Didn't mark any attributes. 1672 return false; 1673 } 1674 1675 return true; 1676 } 1677 1678 /// annotateLibraryCalls - Adds attributes to well-known standard library 1679 /// call declarations. 1680 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) { 1681 bool MadeChange = false; 1682 1683 // Check each function in turn annotating well-known library function 1684 // declarations with attributes. 1685 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 1686 Function *F = (*I)->getFunction(); 1687 1688 if (F && F->isDeclaration()) 1689 MadeChange |= inferPrototypeAttributes(*F); 1690 } 1691 1692 return MadeChange; 1693 } 1694 1695 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 1696 AA = &getAnalysis<AliasAnalysis>(); 1697 TLI = &getAnalysis<TargetLibraryInfo>(); 1698 1699 bool Changed = annotateLibraryCalls(SCC); 1700 Changed |= AddReadAttrs(SCC); 1701 Changed |= AddArgumentAttrs(SCC); 1702 Changed |= AddNoAliasAttrs(SCC); 1703 return Changed; 1704 } 1705
