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 /// \file 11 /// This file implements interprocedural passes which walk the 12 /// call-graph deducing and/or propagating function attributes. 13 /// 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/Transforms/IPO/FunctionAttrs.h" 17 #include "llvm/Transforms/IPO.h" 18 #include "llvm/ADT/SCCIterator.h" 19 #include "llvm/ADT/SetVector.h" 20 #include "llvm/ADT/SmallSet.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/ADT/StringSwitch.h" 23 #include "llvm/Analysis/AliasAnalysis.h" 24 #include "llvm/Analysis/AssumptionCache.h" 25 #include "llvm/Analysis/BasicAliasAnalysis.h" 26 #include "llvm/Analysis/CallGraph.h" 27 #include "llvm/Analysis/CallGraphSCCPass.h" 28 #include "llvm/Analysis/CaptureTracking.h" 29 #include "llvm/Analysis/TargetLibraryInfo.h" 30 #include "llvm/Analysis/ValueTracking.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/Support/Debug.h" 36 #include "llvm/Support/raw_ostream.h" 37 #include "llvm/Analysis/TargetLibraryInfo.h" 38 using namespace llvm; 39 40 #define DEBUG_TYPE "functionattrs" 41 42 STATISTIC(NumReadNone, "Number of functions marked readnone"); 43 STATISTIC(NumReadOnly, "Number of functions marked readonly"); 44 STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 45 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone"); 46 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly"); 47 STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 48 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull"); 49 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse"); 50 51 namespace { 52 typedef SmallSetVector<Function *, 8> SCCNodeSet; 53 } 54 55 namespace { 56 /// The three kinds of memory access relevant to 'readonly' and 57 /// 'readnone' attributes. 58 enum MemoryAccessKind { 59 MAK_ReadNone = 0, 60 MAK_ReadOnly = 1, 61 MAK_MayWrite = 2 62 }; 63 } 64 65 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR, 66 const SCCNodeSet &SCCNodes) { 67 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F); 68 if (MRB == FMRB_DoesNotAccessMemory) 69 // Already perfect! 70 return MAK_ReadNone; 71 72 // Non-exact function definitions may not be selected at link time, and an 73 // alternative version that writes to memory may be selected. See the comment 74 // on GlobalValue::isDefinitionExact for more details. 75 if (!F.hasExactDefinition()) { 76 if (AliasAnalysis::onlyReadsMemory(MRB)) 77 return MAK_ReadOnly; 78 79 // Conservatively assume it writes to memory. 80 return MAK_MayWrite; 81 } 82 83 // Scan the function body for instructions that may read or write memory. 84 bool ReadsMemory = false; 85 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 86 Instruction *I = &*II; 87 88 // Some instructions can be ignored even if they read or write memory. 89 // Detect these now, skipping to the next instruction if one is found. 90 CallSite CS(cast<Value>(I)); 91 if (CS) { 92 // Ignore calls to functions in the same SCC, as long as the call sites 93 // don't have operand bundles. Calls with operand bundles are allowed to 94 // have memory effects not described by the memory effects of the call 95 // target. 96 if (!CS.hasOperandBundles() && CS.getCalledFunction() && 97 SCCNodes.count(CS.getCalledFunction())) 98 continue; 99 FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS); 100 101 // If the call doesn't access memory, we're done. 102 if (!(MRB & MRI_ModRef)) 103 continue; 104 105 if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) { 106 // The call could access any memory. If that includes writes, give up. 107 if (MRB & MRI_Mod) 108 return MAK_MayWrite; 109 // If it reads, note it. 110 if (MRB & MRI_Ref) 111 ReadsMemory = true; 112 continue; 113 } 114 115 // Check whether all pointer arguments point to local memory, and 116 // ignore calls that only access local memory. 117 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 118 CI != CE; ++CI) { 119 Value *Arg = *CI; 120 if (!Arg->getType()->isPtrOrPtrVectorTy()) 121 continue; 122 123 AAMDNodes AAInfo; 124 I->getAAMetadata(AAInfo); 125 MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo); 126 127 // Skip accesses to local or constant memory as they don't impact the 128 // externally visible mod/ref behavior. 129 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 130 continue; 131 132 if (MRB & MRI_Mod) 133 // Writes non-local memory. Give up. 134 return MAK_MayWrite; 135 if (MRB & MRI_Ref) 136 // Ok, it reads non-local memory. 137 ReadsMemory = true; 138 } 139 continue; 140 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 141 // Ignore non-volatile loads from local memory. (Atomic is okay here.) 142 if (!LI->isVolatile()) { 143 MemoryLocation Loc = MemoryLocation::get(LI); 144 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 145 continue; 146 } 147 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 148 // Ignore non-volatile stores to local memory. (Atomic is okay here.) 149 if (!SI->isVolatile()) { 150 MemoryLocation Loc = MemoryLocation::get(SI); 151 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 152 continue; 153 } 154 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) { 155 // Ignore vaargs on local memory. 156 MemoryLocation Loc = MemoryLocation::get(VI); 157 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 158 continue; 159 } 160 161 // Any remaining instructions need to be taken seriously! Check if they 162 // read or write memory. 163 if (I->mayWriteToMemory()) 164 // Writes memory. Just give up. 165 return MAK_MayWrite; 166 167 // If this instruction may read memory, remember that. 168 ReadsMemory |= I->mayReadFromMemory(); 169 } 170 171 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone; 172 } 173 174 /// Deduce readonly/readnone attributes for the SCC. 175 template <typename AARGetterT> 176 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT AARGetter) { 177 // Check if any of the functions in the SCC read or write memory. If they 178 // write memory then they can't be marked readnone or readonly. 179 bool ReadsMemory = false; 180 for (Function *F : SCCNodes) { 181 // Call the callable parameter to look up AA results for this function. 182 AAResults &AAR = AARGetter(*F); 183 184 switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) { 185 case MAK_MayWrite: 186 return false; 187 case MAK_ReadOnly: 188 ReadsMemory = true; 189 break; 190 case MAK_ReadNone: 191 // Nothing to do! 192 break; 193 } 194 } 195 196 // Success! Functions in this SCC do not access memory, or only read memory. 197 // Give them the appropriate attribute. 198 bool MadeChange = false; 199 for (Function *F : SCCNodes) { 200 if (F->doesNotAccessMemory()) 201 // Already perfect! 202 continue; 203 204 if (F->onlyReadsMemory() && ReadsMemory) 205 // No change. 206 continue; 207 208 MadeChange = true; 209 210 // Clear out any existing attributes. 211 AttrBuilder B; 212 B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone); 213 F->removeAttributes( 214 AttributeSet::FunctionIndex, 215 AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B)); 216 217 // Add in the new attribute. 218 F->addAttribute(AttributeSet::FunctionIndex, 219 ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone); 220 221 if (ReadsMemory) 222 ++NumReadOnly; 223 else 224 ++NumReadNone; 225 } 226 227 return MadeChange; 228 } 229 230 namespace { 231 /// For a given pointer Argument, this retains a list of Arguments of functions 232 /// in the same SCC that the pointer data flows into. We use this to build an 233 /// SCC of the arguments. 234 struct ArgumentGraphNode { 235 Argument *Definition; 236 SmallVector<ArgumentGraphNode *, 4> Uses; 237 }; 238 239 class ArgumentGraph { 240 // We store pointers to ArgumentGraphNode objects, so it's important that 241 // that they not move around upon insert. 242 typedef std::map<Argument *, ArgumentGraphNode> ArgumentMapTy; 243 244 ArgumentMapTy ArgumentMap; 245 246 // There is no root node for the argument graph, in fact: 247 // void f(int *x, int *y) { if (...) f(x, y); } 248 // is an example where the graph is disconnected. The SCCIterator requires a 249 // single entry point, so we maintain a fake ("synthetic") root node that 250 // uses every node. Because the graph is directed and nothing points into 251 // the root, it will not participate in any SCCs (except for its own). 252 ArgumentGraphNode SyntheticRoot; 253 254 public: 255 ArgumentGraph() { SyntheticRoot.Definition = nullptr; } 256 257 typedef SmallVectorImpl<ArgumentGraphNode *>::iterator iterator; 258 259 iterator begin() { return SyntheticRoot.Uses.begin(); } 260 iterator end() { return SyntheticRoot.Uses.end(); } 261 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } 262 263 ArgumentGraphNode *operator[](Argument *A) { 264 ArgumentGraphNode &Node = ArgumentMap[A]; 265 Node.Definition = A; 266 SyntheticRoot.Uses.push_back(&Node); 267 return &Node; 268 } 269 }; 270 271 /// This tracker checks whether callees are in the SCC, and if so it does not 272 /// consider that a capture, instead adding it to the "Uses" list and 273 /// continuing with the analysis. 274 struct ArgumentUsesTracker : public CaptureTracker { 275 ArgumentUsesTracker(const SCCNodeSet &SCCNodes) 276 : Captured(false), SCCNodes(SCCNodes) {} 277 278 void tooManyUses() override { Captured = true; } 279 280 bool captured(const Use *U) override { 281 CallSite CS(U->getUser()); 282 if (!CS.getInstruction()) { 283 Captured = true; 284 return true; 285 } 286 287 Function *F = CS.getCalledFunction(); 288 if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) { 289 Captured = true; 290 return true; 291 } 292 293 // Note: the callee and the two successor blocks *follow* the argument 294 // operands. This means there is no need to adjust UseIndex to account for 295 // these. 296 297 unsigned UseIndex = 298 std::distance(const_cast<const Use *>(CS.arg_begin()), U); 299 300 assert(UseIndex < CS.data_operands_size() && 301 "Indirect function calls should have been filtered above!"); 302 303 if (UseIndex >= CS.getNumArgOperands()) { 304 // Data operand, but not a argument operand -- must be a bundle operand 305 assert(CS.hasOperandBundles() && "Must be!"); 306 307 // CaptureTracking told us that we're being captured by an operand bundle 308 // use. In this case it does not matter if the callee is within our SCC 309 // or not -- we've been captured in some unknown way, and we have to be 310 // conservative. 311 Captured = true; 312 return true; 313 } 314 315 if (UseIndex >= F->arg_size()) { 316 assert(F->isVarArg() && "More params than args in non-varargs call"); 317 Captured = true; 318 return true; 319 } 320 321 Uses.push_back(&*std::next(F->arg_begin(), UseIndex)); 322 return false; 323 } 324 325 bool Captured; // True only if certainly captured (used outside our SCC). 326 SmallVector<Argument *, 4> Uses; // Uses within our SCC. 327 328 const SCCNodeSet &SCCNodes; 329 }; 330 } 331 332 namespace llvm { 333 template <> struct GraphTraits<ArgumentGraphNode *> { 334 typedef ArgumentGraphNode NodeType; 335 typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType; 336 337 static inline NodeType *getEntryNode(NodeType *A) { return A; } 338 static inline ChildIteratorType child_begin(NodeType *N) { 339 return N->Uses.begin(); 340 } 341 static inline ChildIteratorType child_end(NodeType *N) { 342 return N->Uses.end(); 343 } 344 }; 345 template <> 346 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> { 347 static NodeType *getEntryNode(ArgumentGraph *AG) { 348 return AG->getEntryNode(); 349 } 350 static ChildIteratorType nodes_begin(ArgumentGraph *AG) { 351 return AG->begin(); 352 } 353 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); } 354 }; 355 } 356 357 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone. 358 static Attribute::AttrKind 359 determinePointerReadAttrs(Argument *A, 360 const SmallPtrSet<Argument *, 8> &SCCNodes) { 361 362 SmallVector<Use *, 32> Worklist; 363 SmallSet<Use *, 32> Visited; 364 365 // inalloca arguments are always clobbered by the call. 366 if (A->hasInAllocaAttr()) 367 return Attribute::None; 368 369 bool IsRead = false; 370 // We don't need to track IsWritten. If A is written to, return immediately. 371 372 for (Use &U : A->uses()) { 373 Visited.insert(&U); 374 Worklist.push_back(&U); 375 } 376 377 while (!Worklist.empty()) { 378 Use *U = Worklist.pop_back_val(); 379 Instruction *I = cast<Instruction>(U->getUser()); 380 381 switch (I->getOpcode()) { 382 case Instruction::BitCast: 383 case Instruction::GetElementPtr: 384 case Instruction::PHI: 385 case Instruction::Select: 386 case Instruction::AddrSpaceCast: 387 // The original value is not read/written via this if the new value isn't. 388 for (Use &UU : I->uses()) 389 if (Visited.insert(&UU).second) 390 Worklist.push_back(&UU); 391 break; 392 393 case Instruction::Call: 394 case Instruction::Invoke: { 395 bool Captures = true; 396 397 if (I->getType()->isVoidTy()) 398 Captures = false; 399 400 auto AddUsersToWorklistIfCapturing = [&] { 401 if (Captures) 402 for (Use &UU : I->uses()) 403 if (Visited.insert(&UU).second) 404 Worklist.push_back(&UU); 405 }; 406 407 CallSite CS(I); 408 if (CS.doesNotAccessMemory()) { 409 AddUsersToWorklistIfCapturing(); 410 continue; 411 } 412 413 Function *F = CS.getCalledFunction(); 414 if (!F) { 415 if (CS.onlyReadsMemory()) { 416 IsRead = true; 417 AddUsersToWorklistIfCapturing(); 418 continue; 419 } 420 return Attribute::None; 421 } 422 423 // Note: the callee and the two successor blocks *follow* the argument 424 // operands. This means there is no need to adjust UseIndex to account 425 // for these. 426 427 unsigned UseIndex = std::distance(CS.arg_begin(), U); 428 429 // U cannot be the callee operand use: since we're exploring the 430 // transitive uses of an Argument, having such a use be a callee would 431 // imply the CallSite is an indirect call or invoke; and we'd take the 432 // early exit above. 433 assert(UseIndex < CS.data_operands_size() && 434 "Data operand use expected!"); 435 436 bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands(); 437 438 if (UseIndex >= F->arg_size() && !IsOperandBundleUse) { 439 assert(F->isVarArg() && "More params than args in non-varargs call"); 440 return Attribute::None; 441 } 442 443 Captures &= !CS.doesNotCapture(UseIndex); 444 445 // Since the optimizer (by design) cannot see the data flow corresponding 446 // to a operand bundle use, these cannot participate in the optimistic SCC 447 // analysis. Instead, we model the operand bundle uses as arguments in 448 // call to a function external to the SCC. 449 if (!SCCNodes.count(&*std::next(F->arg_begin(), UseIndex)) || 450 IsOperandBundleUse) { 451 452 // The accessors used on CallSite here do the right thing for calls and 453 // invokes with operand bundles. 454 455 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex)) 456 return Attribute::None; 457 if (!CS.doesNotAccessMemory(UseIndex)) 458 IsRead = true; 459 } 460 461 AddUsersToWorklistIfCapturing(); 462 break; 463 } 464 465 case Instruction::Load: 466 // A volatile load has side effects beyond what readonly can be relied 467 // upon. 468 if (cast<LoadInst>(I)->isVolatile()) 469 return Attribute::None; 470 471 IsRead = true; 472 break; 473 474 case Instruction::ICmp: 475 case Instruction::Ret: 476 break; 477 478 default: 479 return Attribute::None; 480 } 481 } 482 483 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone; 484 } 485 486 /// Deduce nocapture attributes for the SCC. 487 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) { 488 bool Changed = false; 489 490 ArgumentGraph AG; 491 492 AttrBuilder B; 493 B.addAttribute(Attribute::NoCapture); 494 495 // Check each function in turn, determining which pointer arguments are not 496 // captured. 497 for (Function *F : SCCNodes) { 498 // We can infer and propagate function attributes only when we know that the 499 // definition we'll get at link time is *exactly* the definition we see now. 500 // For more details, see GlobalValue::mayBeDerefined. 501 if (!F->hasExactDefinition()) 502 continue; 503 504 // Functions that are readonly (or readnone) and nounwind and don't return 505 // a value can't capture arguments. Don't analyze them. 506 if (F->onlyReadsMemory() && F->doesNotThrow() && 507 F->getReturnType()->isVoidTy()) { 508 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E; 509 ++A) { 510 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 511 A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); 512 ++NumNoCapture; 513 Changed = true; 514 } 515 } 516 continue; 517 } 518 519 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E; 520 ++A) { 521 if (!A->getType()->isPointerTy()) 522 continue; 523 bool HasNonLocalUses = false; 524 if (!A->hasNoCaptureAttr()) { 525 ArgumentUsesTracker Tracker(SCCNodes); 526 PointerMayBeCaptured(&*A, &Tracker); 527 if (!Tracker.Captured) { 528 if (Tracker.Uses.empty()) { 529 // If it's trivially not captured, mark it nocapture now. 530 A->addAttr( 531 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); 532 ++NumNoCapture; 533 Changed = true; 534 } else { 535 // If it's not trivially captured and not trivially not captured, 536 // then it must be calling into another function in our SCC. Save 537 // its particulars for Argument-SCC analysis later. 538 ArgumentGraphNode *Node = AG[&*A]; 539 for (Argument *Use : Tracker.Uses) { 540 Node->Uses.push_back(AG[Use]); 541 if (Use != &*A) 542 HasNonLocalUses = true; 543 } 544 } 545 } 546 // Otherwise, it's captured. Don't bother doing SCC analysis on it. 547 } 548 if (!HasNonLocalUses && !A->onlyReadsMemory()) { 549 // Can we determine that it's readonly/readnone without doing an SCC? 550 // Note that we don't allow any calls at all here, or else our result 551 // will be dependent on the iteration order through the functions in the 552 // SCC. 553 SmallPtrSet<Argument *, 8> Self; 554 Self.insert(&*A); 555 Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self); 556 if (R != Attribute::None) { 557 AttrBuilder B; 558 B.addAttribute(R); 559 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 560 Changed = true; 561 R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; 562 } 563 } 564 } 565 } 566 567 // The graph we've collected is partial because we stopped scanning for 568 // argument uses once we solved the argument trivially. These partial nodes 569 // show up as ArgumentGraphNode objects with an empty Uses list, and for 570 // these nodes the final decision about whether they capture has already been 571 // made. If the definition doesn't have a 'nocapture' attribute by now, it 572 // captures. 573 574 for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) { 575 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I; 576 if (ArgumentSCC.size() == 1) { 577 if (!ArgumentSCC[0]->Definition) 578 continue; // synthetic root node 579 580 // eg. "void f(int* x) { if (...) f(x); }" 581 if (ArgumentSCC[0]->Uses.size() == 1 && 582 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) { 583 Argument *A = ArgumentSCC[0]->Definition; 584 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 585 ++NumNoCapture; 586 Changed = true; 587 } 588 continue; 589 } 590 591 bool SCCCaptured = false; 592 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); 593 I != E && !SCCCaptured; ++I) { 594 ArgumentGraphNode *Node = *I; 595 if (Node->Uses.empty()) { 596 if (!Node->Definition->hasNoCaptureAttr()) 597 SCCCaptured = true; 598 } 599 } 600 if (SCCCaptured) 601 continue; 602 603 SmallPtrSet<Argument *, 8> ArgumentSCCNodes; 604 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for 605 // quickly looking up whether a given Argument is in this ArgumentSCC. 606 for (ArgumentGraphNode *I : ArgumentSCC) { 607 ArgumentSCCNodes.insert(I->Definition); 608 } 609 610 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); 611 I != E && !SCCCaptured; ++I) { 612 ArgumentGraphNode *N = *I; 613 for (ArgumentGraphNode *Use : N->Uses) { 614 Argument *A = Use->Definition; 615 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A)) 616 continue; 617 SCCCaptured = true; 618 break; 619 } 620 } 621 if (SCCCaptured) 622 continue; 623 624 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 625 Argument *A = ArgumentSCC[i]->Definition; 626 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 627 ++NumNoCapture; 628 Changed = true; 629 } 630 631 // We also want to compute readonly/readnone. With a small number of false 632 // negatives, we can assume that any pointer which is captured isn't going 633 // to be provably readonly or readnone, since by definition we can't 634 // analyze all uses of a captured pointer. 635 // 636 // The false negatives happen when the pointer is captured by a function 637 // that promises readonly/readnone behaviour on the pointer, then the 638 // pointer's lifetime ends before anything that writes to arbitrary memory. 639 // Also, a readonly/readnone pointer may be returned, but returning a 640 // pointer is capturing it. 641 642 Attribute::AttrKind ReadAttr = Attribute::ReadNone; 643 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 644 Argument *A = ArgumentSCC[i]->Definition; 645 Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes); 646 if (K == Attribute::ReadNone) 647 continue; 648 if (K == Attribute::ReadOnly) { 649 ReadAttr = Attribute::ReadOnly; 650 continue; 651 } 652 ReadAttr = K; 653 break; 654 } 655 656 if (ReadAttr != Attribute::None) { 657 AttrBuilder B, R; 658 B.addAttribute(ReadAttr); 659 R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone); 660 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 661 Argument *A = ArgumentSCC[i]->Definition; 662 // Clear out existing readonly/readnone attributes 663 A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R)); 664 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 665 ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; 666 Changed = true; 667 } 668 } 669 } 670 671 return Changed; 672 } 673 674 /// Tests whether a function is "malloc-like". 675 /// 676 /// A function is "malloc-like" if it returns either null or a pointer that 677 /// doesn't alias any other pointer visible to the caller. 678 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) { 679 SmallSetVector<Value *, 8> FlowsToReturn; 680 for (BasicBlock &BB : *F) 681 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) 682 FlowsToReturn.insert(Ret->getReturnValue()); 683 684 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 685 Value *RetVal = FlowsToReturn[i]; 686 687 if (Constant *C = dyn_cast<Constant>(RetVal)) { 688 if (!C->isNullValue() && !isa<UndefValue>(C)) 689 return false; 690 691 continue; 692 } 693 694 if (isa<Argument>(RetVal)) 695 return false; 696 697 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 698 switch (RVI->getOpcode()) { 699 // Extend the analysis by looking upwards. 700 case Instruction::BitCast: 701 case Instruction::GetElementPtr: 702 case Instruction::AddrSpaceCast: 703 FlowsToReturn.insert(RVI->getOperand(0)); 704 continue; 705 case Instruction::Select: { 706 SelectInst *SI = cast<SelectInst>(RVI); 707 FlowsToReturn.insert(SI->getTrueValue()); 708 FlowsToReturn.insert(SI->getFalseValue()); 709 continue; 710 } 711 case Instruction::PHI: { 712 PHINode *PN = cast<PHINode>(RVI); 713 for (Value *IncValue : PN->incoming_values()) 714 FlowsToReturn.insert(IncValue); 715 continue; 716 } 717 718 // Check whether the pointer came from an allocation. 719 case Instruction::Alloca: 720 break; 721 case Instruction::Call: 722 case Instruction::Invoke: { 723 CallSite CS(RVI); 724 if (CS.paramHasAttr(0, Attribute::NoAlias)) 725 break; 726 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 727 break; 728 } // fall-through 729 default: 730 return false; // Did not come from an allocation. 731 } 732 733 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 734 return false; 735 } 736 737 return true; 738 } 739 740 /// Deduce noalias attributes for the SCC. 741 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) { 742 // Check each function in turn, determining which functions return noalias 743 // pointers. 744 for (Function *F : SCCNodes) { 745 // Already noalias. 746 if (F->doesNotAlias(0)) 747 continue; 748 749 // We can infer and propagate function attributes only when we know that the 750 // definition we'll get at link time is *exactly* the definition we see now. 751 // For more details, see GlobalValue::mayBeDerefined. 752 if (!F->hasExactDefinition()) 753 return false; 754 755 // We annotate noalias return values, which are only applicable to 756 // pointer types. 757 if (!F->getReturnType()->isPointerTy()) 758 continue; 759 760 if (!isFunctionMallocLike(F, SCCNodes)) 761 return false; 762 } 763 764 bool MadeChange = false; 765 for (Function *F : SCCNodes) { 766 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 767 continue; 768 769 F->setDoesNotAlias(0); 770 ++NumNoAlias; 771 MadeChange = true; 772 } 773 774 return MadeChange; 775 } 776 777 /// Tests whether this function is known to not return null. 778 /// 779 /// Requires that the function returns a pointer. 780 /// 781 /// Returns true if it believes the function will not return a null, and sets 782 /// \p Speculative based on whether the returned conclusion is a speculative 783 /// conclusion due to SCC calls. 784 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes, 785 bool &Speculative) { 786 assert(F->getReturnType()->isPointerTy() && 787 "nonnull only meaningful on pointer types"); 788 Speculative = false; 789 790 SmallSetVector<Value *, 8> FlowsToReturn; 791 for (BasicBlock &BB : *F) 792 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) 793 FlowsToReturn.insert(Ret->getReturnValue()); 794 795 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 796 Value *RetVal = FlowsToReturn[i]; 797 798 // If this value is locally known to be non-null, we're good 799 if (isKnownNonNull(RetVal)) 800 continue; 801 802 // Otherwise, we need to look upwards since we can't make any local 803 // conclusions. 804 Instruction *RVI = dyn_cast<Instruction>(RetVal); 805 if (!RVI) 806 return false; 807 switch (RVI->getOpcode()) { 808 // Extend the analysis by looking upwards. 809 case Instruction::BitCast: 810 case Instruction::GetElementPtr: 811 case Instruction::AddrSpaceCast: 812 FlowsToReturn.insert(RVI->getOperand(0)); 813 continue; 814 case Instruction::Select: { 815 SelectInst *SI = cast<SelectInst>(RVI); 816 FlowsToReturn.insert(SI->getTrueValue()); 817 FlowsToReturn.insert(SI->getFalseValue()); 818 continue; 819 } 820 case Instruction::PHI: { 821 PHINode *PN = cast<PHINode>(RVI); 822 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 823 FlowsToReturn.insert(PN->getIncomingValue(i)); 824 continue; 825 } 826 case Instruction::Call: 827 case Instruction::Invoke: { 828 CallSite CS(RVI); 829 Function *Callee = CS.getCalledFunction(); 830 // A call to a node within the SCC is assumed to return null until 831 // proven otherwise 832 if (Callee && SCCNodes.count(Callee)) { 833 Speculative = true; 834 continue; 835 } 836 return false; 837 } 838 default: 839 return false; // Unknown source, may be null 840 }; 841 llvm_unreachable("should have either continued or returned"); 842 } 843 844 return true; 845 } 846 847 /// Deduce nonnull attributes for the SCC. 848 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) { 849 // Speculative that all functions in the SCC return only nonnull 850 // pointers. We may refute this as we analyze functions. 851 bool SCCReturnsNonNull = true; 852 853 bool MadeChange = false; 854 855 // Check each function in turn, determining which functions return nonnull 856 // pointers. 857 for (Function *F : SCCNodes) { 858 // Already nonnull. 859 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, 860 Attribute::NonNull)) 861 continue; 862 863 // We can infer and propagate function attributes only when we know that the 864 // definition we'll get at link time is *exactly* the definition we see now. 865 // For more details, see GlobalValue::mayBeDerefined. 866 if (!F->hasExactDefinition()) 867 return false; 868 869 // We annotate nonnull return values, which are only applicable to 870 // pointer types. 871 if (!F->getReturnType()->isPointerTy()) 872 continue; 873 874 bool Speculative = false; 875 if (isReturnNonNull(F, SCCNodes, Speculative)) { 876 if (!Speculative) { 877 // Mark the function eagerly since we may discover a function 878 // which prevents us from speculating about the entire SCC 879 DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n"); 880 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull); 881 ++NumNonNullReturn; 882 MadeChange = true; 883 } 884 continue; 885 } 886 // At least one function returns something which could be null, can't 887 // speculate any more. 888 SCCReturnsNonNull = false; 889 } 890 891 if (SCCReturnsNonNull) { 892 for (Function *F : SCCNodes) { 893 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, 894 Attribute::NonNull) || 895 !F->getReturnType()->isPointerTy()) 896 continue; 897 898 DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n"); 899 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull); 900 ++NumNonNullReturn; 901 MadeChange = true; 902 } 903 } 904 905 return MadeChange; 906 } 907 908 /// Remove the convergent attribute from all functions in the SCC if every 909 /// callsite within the SCC is not convergent (except for calls to functions 910 /// within the SCC). Returns true if changes were made. 911 static bool removeConvergentAttrs(const SCCNodeSet &SCCNodes) { 912 // For every function in SCC, ensure that either 913 // * it is not convergent, or 914 // * we can remove its convergent attribute. 915 bool HasConvergentFn = false; 916 for (Function *F : SCCNodes) { 917 if (!F->isConvergent()) continue; 918 HasConvergentFn = true; 919 920 // Can't remove convergent from function declarations. 921 if (F->isDeclaration()) return false; 922 923 // Can't remove convergent if any of our functions has a convergent call to a 924 // function not in the SCC. 925 for (Instruction &I : instructions(*F)) { 926 CallSite CS(&I); 927 // Bail if CS is a convergent call to a function not in the SCC. 928 if (CS && CS.isConvergent() && 929 SCCNodes.count(CS.getCalledFunction()) == 0) 930 return false; 931 } 932 } 933 934 // If the SCC doesn't have any convergent functions, we have nothing to do. 935 if (!HasConvergentFn) return false; 936 937 // If we got here, all of the calls the SCC makes to functions not in the SCC 938 // are non-convergent. Therefore all of the SCC's functions can also be made 939 // non-convergent. We'll remove the attr from the callsites in 940 // InstCombineCalls. 941 for (Function *F : SCCNodes) { 942 if (!F->isConvergent()) continue; 943 944 DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName() 945 << "\n"); 946 F->setNotConvergent(); 947 } 948 return true; 949 } 950 951 static bool setDoesNotRecurse(Function &F) { 952 if (F.doesNotRecurse()) 953 return false; 954 F.setDoesNotRecurse(); 955 ++NumNoRecurse; 956 return true; 957 } 958 959 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) { 960 // Try and identify functions that do not recurse. 961 962 // If the SCC contains multiple nodes we know for sure there is recursion. 963 if (SCCNodes.size() != 1) 964 return false; 965 966 Function *F = *SCCNodes.begin(); 967 if (!F || F->isDeclaration() || F->doesNotRecurse()) 968 return false; 969 970 // If all of the calls in F are identifiable and are to norecurse functions, F 971 // is norecurse. This check also detects self-recursion as F is not currently 972 // marked norecurse, so any called from F to F will not be marked norecurse. 973 for (Instruction &I : instructions(*F)) 974 if (auto CS = CallSite(&I)) { 975 Function *Callee = CS.getCalledFunction(); 976 if (!Callee || Callee == F || !Callee->doesNotRecurse()) 977 // Function calls a potentially recursive function. 978 return false; 979 } 980 981 // Every call was to a non-recursive function other than this function, and 982 // we have no indirect recursion as the SCC size is one. This function cannot 983 // recurse. 984 return setDoesNotRecurse(*F); 985 } 986 987 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C, 988 CGSCCAnalysisManager &AM) { 989 FunctionAnalysisManager &FAM = 990 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager(); 991 992 // We pass a lambda into functions to wire them up to the analysis manager 993 // for getting function analyses. 994 auto AARGetter = [&](Function &F) -> AAResults & { 995 return FAM.getResult<AAManager>(F); 996 }; 997 998 // Fill SCCNodes with the elements of the SCC. Also track whether there are 999 // any external or opt-none nodes that will prevent us from optimizing any 1000 // part of the SCC. 1001 SCCNodeSet SCCNodes; 1002 bool HasUnknownCall = false; 1003 for (LazyCallGraph::Node &N : C) { 1004 Function &F = N.getFunction(); 1005 if (F.hasFnAttribute(Attribute::OptimizeNone)) { 1006 // Treat any function we're trying not to optimize as if it were an 1007 // indirect call and omit it from the node set used below. 1008 HasUnknownCall = true; 1009 continue; 1010 } 1011 // Track whether any functions in this SCC have an unknown call edge. 1012 // Note: if this is ever a performance hit, we can common it with 1013 // subsequent routines which also do scans over the instructions of the 1014 // function. 1015 if (!HasUnknownCall) 1016 for (Instruction &I : instructions(F)) 1017 if (auto CS = CallSite(&I)) 1018 if (!CS.getCalledFunction()) { 1019 HasUnknownCall = true; 1020 break; 1021 } 1022 1023 SCCNodes.insert(&F); 1024 } 1025 1026 bool Changed = false; 1027 Changed |= addReadAttrs(SCCNodes, AARGetter); 1028 Changed |= addArgumentAttrs(SCCNodes); 1029 1030 // If we have no external nodes participating in the SCC, we can deduce some 1031 // more precise attributes as well. 1032 if (!HasUnknownCall) { 1033 Changed |= addNoAliasAttrs(SCCNodes); 1034 Changed |= addNonNullAttrs(SCCNodes); 1035 Changed |= removeConvergentAttrs(SCCNodes); 1036 Changed |= addNoRecurseAttrs(SCCNodes); 1037 } 1038 1039 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); 1040 } 1041 1042 namespace { 1043 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass { 1044 static char ID; // Pass identification, replacement for typeid 1045 PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) { 1046 initializePostOrderFunctionAttrsLegacyPassPass(*PassRegistry::getPassRegistry()); 1047 } 1048 1049 bool runOnSCC(CallGraphSCC &SCC) override; 1050 1051 void getAnalysisUsage(AnalysisUsage &AU) const override { 1052 AU.setPreservesCFG(); 1053 AU.addRequired<AssumptionCacheTracker>(); 1054 getAAResultsAnalysisUsage(AU); 1055 CallGraphSCCPass::getAnalysisUsage(AU); 1056 } 1057 }; 1058 } 1059 1060 char PostOrderFunctionAttrsLegacyPass::ID = 0; 1061 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs", 1062 "Deduce function attributes", false, false) 1063 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1064 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 1065 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs", 1066 "Deduce function attributes", false, false) 1067 1068 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() { return new PostOrderFunctionAttrsLegacyPass(); } 1069 1070 template <typename AARGetterT> 1071 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) { 1072 bool Changed = false; 1073 1074 // Fill SCCNodes with the elements of the SCC. Used for quickly looking up 1075 // whether a given CallGraphNode is in this SCC. Also track whether there are 1076 // any external or opt-none nodes that will prevent us from optimizing any 1077 // part of the SCC. 1078 SCCNodeSet SCCNodes; 1079 bool ExternalNode = false; 1080 for (CallGraphNode *I : SCC) { 1081 Function *F = I->getFunction(); 1082 if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) { 1083 // External node or function we're trying not to optimize - we both avoid 1084 // transform them and avoid leveraging information they provide. 1085 ExternalNode = true; 1086 continue; 1087 } 1088 1089 SCCNodes.insert(F); 1090 } 1091 1092 Changed |= addReadAttrs(SCCNodes, AARGetter); 1093 Changed |= addArgumentAttrs(SCCNodes); 1094 1095 // If we have no external nodes participating in the SCC, we can deduce some 1096 // more precise attributes as well. 1097 if (!ExternalNode) { 1098 Changed |= addNoAliasAttrs(SCCNodes); 1099 Changed |= addNonNullAttrs(SCCNodes); 1100 Changed |= removeConvergentAttrs(SCCNodes); 1101 Changed |= addNoRecurseAttrs(SCCNodes); 1102 } 1103 1104 return Changed; 1105 } 1106 1107 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) { 1108 if (skipSCC(SCC)) 1109 return false; 1110 1111 // We compute dedicated AA results for each function in the SCC as needed. We 1112 // use a lambda referencing external objects so that they live long enough to 1113 // be queried, but we re-use them each time. 1114 Optional<BasicAAResult> BAR; 1115 Optional<AAResults> AAR; 1116 auto AARGetter = [&](Function &F) -> AAResults & { 1117 BAR.emplace(createLegacyPMBasicAAResult(*this, F)); 1118 AAR.emplace(createLegacyPMAAResults(*this, F, *BAR)); 1119 return *AAR; 1120 }; 1121 1122 return runImpl(SCC, AARGetter); 1123 } 1124 1125 namespace { 1126 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass { 1127 static char ID; // Pass identification, replacement for typeid 1128 ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) { 1129 initializeReversePostOrderFunctionAttrsLegacyPassPass(*PassRegistry::getPassRegistry()); 1130 } 1131 1132 bool runOnModule(Module &M) override; 1133 1134 void getAnalysisUsage(AnalysisUsage &AU) const override { 1135 AU.setPreservesCFG(); 1136 AU.addRequired<CallGraphWrapperPass>(); 1137 AU.addPreserved<CallGraphWrapperPass>(); 1138 } 1139 }; 1140 } 1141 1142 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0; 1143 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs", 1144 "Deduce function attributes in RPO", false, false) 1145 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 1146 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs", 1147 "Deduce function attributes in RPO", false, false) 1148 1149 Pass *llvm::createReversePostOrderFunctionAttrsPass() { 1150 return new ReversePostOrderFunctionAttrsLegacyPass(); 1151 } 1152 1153 static bool addNoRecurseAttrsTopDown(Function &F) { 1154 // We check the preconditions for the function prior to calling this to avoid 1155 // the cost of building up a reversible post-order list. We assert them here 1156 // to make sure none of the invariants this relies on were violated. 1157 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!"); 1158 assert(!F.doesNotRecurse() && 1159 "This function has already been deduced as norecurs!"); 1160 assert(F.hasInternalLinkage() && 1161 "Can only do top-down deduction for internal linkage functions!"); 1162 1163 // If F is internal and all of its uses are calls from a non-recursive 1164 // functions, then none of its calls could in fact recurse without going 1165 // through a function marked norecurse, and so we can mark this function too 1166 // as norecurse. Note that the uses must actually be calls -- otherwise 1167 // a pointer to this function could be returned from a norecurse function but 1168 // this function could be recursively (indirectly) called. Note that this 1169 // also detects if F is directly recursive as F is not yet marked as 1170 // a norecurse function. 1171 for (auto *U : F.users()) { 1172 auto *I = dyn_cast<Instruction>(U); 1173 if (!I) 1174 return false; 1175 CallSite CS(I); 1176 if (!CS || !CS.getParent()->getParent()->doesNotRecurse()) 1177 return false; 1178 } 1179 return setDoesNotRecurse(F); 1180 } 1181 1182 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) { 1183 // We only have a post-order SCC traversal (because SCCs are inherently 1184 // discovered in post-order), so we accumulate them in a vector and then walk 1185 // it in reverse. This is simpler than using the RPO iterator infrastructure 1186 // because we need to combine SCC detection and the PO walk of the call 1187 // graph. We can also cheat egregiously because we're primarily interested in 1188 // synthesizing norecurse and so we can only save the singular SCCs as SCCs 1189 // with multiple functions in them will clearly be recursive. 1190 SmallVector<Function *, 16> Worklist; 1191 for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) { 1192 if (I->size() != 1) 1193 continue; 1194 1195 Function *F = I->front()->getFunction(); 1196 if (F && !F->isDeclaration() && !F->doesNotRecurse() && 1197 F->hasInternalLinkage()) 1198 Worklist.push_back(F); 1199 } 1200 1201 bool Changed = false; 1202 for (auto *F : reverse(Worklist)) 1203 Changed |= addNoRecurseAttrsTopDown(*F); 1204 1205 return Changed; 1206 } 1207 1208 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) { 1209 if (skipModule(M)) 1210 return false; 1211 1212 auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 1213 1214 return deduceFunctionAttributeInRPO(M, CG); 1215 } 1216 1217 PreservedAnalyses 1218 ReversePostOrderFunctionAttrsPass::run(Module &M, AnalysisManager<Module> &AM) { 1219 auto &CG = AM.getResult<CallGraphAnalysis>(M); 1220 1221 bool Changed = deduceFunctionAttributeInRPO(M, CG); 1222 if (!Changed) 1223 return PreservedAnalyses::all(); 1224 PreservedAnalyses PA; 1225 PA.preserve<CallGraphAnalysis>(); 1226 return PA; 1227 } 1228