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