1 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// \file 10 /// This file implements interprocedural passes which walk the 11 /// call-graph deducing and/or propagating function attributes. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/IPO/FunctionAttrs.h" 16 #include "llvm/ADT/SCCIterator.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/ADT/SmallPtrSet.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/Analysis/AliasAnalysis.h" 23 #include "llvm/Analysis/AssumptionCache.h" 24 #include "llvm/Analysis/BasicAliasAnalysis.h" 25 #include "llvm/Analysis/CGSCCPassManager.h" 26 #include "llvm/Analysis/CallGraph.h" 27 #include "llvm/Analysis/CallGraphSCCPass.h" 28 #include "llvm/Analysis/CaptureTracking.h" 29 #include "llvm/Analysis/LazyCallGraph.h" 30 #include "llvm/Analysis/MemoryBuiltins.h" 31 #include "llvm/Analysis/MemoryLocation.h" 32 #include "llvm/Analysis/ValueTracking.h" 33 #include "llvm/IR/Argument.h" 34 #include "llvm/IR/Attributes.h" 35 #include "llvm/IR/BasicBlock.h" 36 #include "llvm/IR/CallSite.h" 37 #include "llvm/IR/Constant.h" 38 #include "llvm/IR/Constants.h" 39 #include "llvm/IR/Function.h" 40 #include "llvm/IR/InstIterator.h" 41 #include "llvm/IR/InstrTypes.h" 42 #include "llvm/IR/Instruction.h" 43 #include "llvm/IR/Instructions.h" 44 #include "llvm/IR/IntrinsicInst.h" 45 #include "llvm/IR/Metadata.h" 46 #include "llvm/IR/PassManager.h" 47 #include "llvm/IR/Type.h" 48 #include "llvm/IR/Use.h" 49 #include "llvm/IR/User.h" 50 #include "llvm/IR/Value.h" 51 #include "llvm/Pass.h" 52 #include "llvm/Support/Casting.h" 53 #include "llvm/Support/CommandLine.h" 54 #include "llvm/Support/Compiler.h" 55 #include "llvm/Support/Debug.h" 56 #include "llvm/Support/ErrorHandling.h" 57 #include "llvm/Support/raw_ostream.h" 58 #include "llvm/Transforms/IPO.h" 59 #include <cassert> 60 #include <iterator> 61 #include <map> 62 #include <vector> 63 64 using namespace llvm; 65 66 #define DEBUG_TYPE "functionattrs" 67 68 STATISTIC(NumReadNone, "Number of functions marked readnone"); 69 STATISTIC(NumReadOnly, "Number of functions marked readonly"); 70 STATISTIC(NumWriteOnly, "Number of functions marked writeonly"); 71 STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 72 STATISTIC(NumReturned, "Number of arguments marked returned"); 73 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone"); 74 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly"); 75 STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 76 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull"); 77 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse"); 78 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind"); 79 STATISTIC(NumNoFree, "Number of functions marked as nofree"); 80 81 // FIXME: This is disabled by default to avoid exposing security vulnerabilities 82 // in C/C++ code compiled by clang: 83 // http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html 84 static cl::opt<bool> EnableNonnullArgPropagation( 85 "enable-nonnull-arg-prop", cl::Hidden, 86 cl::desc("Try to propagate nonnull argument attributes from callsites to " 87 "caller functions.")); 88 89 static cl::opt<bool> DisableNoUnwindInference( 90 "disable-nounwind-inference", cl::Hidden, 91 cl::desc("Stop inferring nounwind attribute during function-attrs pass")); 92 93 static cl::opt<bool> DisableNoFreeInference( 94 "disable-nofree-inference", cl::Hidden, 95 cl::desc("Stop inferring nofree attribute during function-attrs pass")); 96 97 namespace { 98 99 using SCCNodeSet = SmallSetVector<Function *, 8>; 100 101 } // end anonymous namespace 102 103 /// Returns the memory access attribute for function F using AAR for AA results, 104 /// where SCCNodes is the current SCC. 105 /// 106 /// If ThisBody is true, this function may examine the function body and will 107 /// return a result pertaining to this copy of the function. If it is false, the 108 /// result will be based only on AA results for the function declaration; it 109 /// will be assumed that some other (perhaps less optimized) version of the 110 /// function may be selected at link time. 111 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, bool ThisBody, 112 AAResults &AAR, 113 const SCCNodeSet &SCCNodes) { 114 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F); 115 if (MRB == FMRB_DoesNotAccessMemory) 116 // Already perfect! 117 return MAK_ReadNone; 118 119 if (!ThisBody) { 120 if (AliasAnalysis::onlyReadsMemory(MRB)) 121 return MAK_ReadOnly; 122 123 if (AliasAnalysis::doesNotReadMemory(MRB)) 124 return MAK_WriteOnly; 125 126 // Conservatively assume it reads and writes to memory. 127 return MAK_MayWrite; 128 } 129 130 // Scan the function body for instructions that may read or write memory. 131 bool ReadsMemory = false; 132 bool WritesMemory = false; 133 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 134 Instruction *I = &*II; 135 136 // Some instructions can be ignored even if they read or write memory. 137 // Detect these now, skipping to the next instruction if one is found. 138 if (auto *Call = dyn_cast<CallBase>(I)) { 139 // Ignore calls to functions in the same SCC, as long as the call sites 140 // don't have operand bundles. Calls with operand bundles are allowed to 141 // have memory effects not described by the memory effects of the call 142 // target. 143 if (!Call->hasOperandBundles() && Call->getCalledFunction() && 144 SCCNodes.count(Call->getCalledFunction())) 145 continue; 146 FunctionModRefBehavior MRB = AAR.getModRefBehavior(Call); 147 ModRefInfo MRI = createModRefInfo(MRB); 148 149 // If the call doesn't access memory, we're done. 150 if (isNoModRef(MRI)) 151 continue; 152 153 if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) { 154 // The call could access any memory. If that includes writes, note it. 155 if (isModSet(MRI)) 156 WritesMemory = true; 157 // If it reads, note it. 158 if (isRefSet(MRI)) 159 ReadsMemory = true; 160 continue; 161 } 162 163 // Check whether all pointer arguments point to local memory, and 164 // ignore calls that only access local memory. 165 for (CallSite::arg_iterator CI = Call->arg_begin(), CE = Call->arg_end(); 166 CI != CE; ++CI) { 167 Value *Arg = *CI; 168 if (!Arg->getType()->isPtrOrPtrVectorTy()) 169 continue; 170 171 AAMDNodes AAInfo; 172 I->getAAMetadata(AAInfo); 173 MemoryLocation Loc(Arg, LocationSize::unknown(), AAInfo); 174 175 // Skip accesses to local or constant memory as they don't impact the 176 // externally visible mod/ref behavior. 177 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 178 continue; 179 180 if (isModSet(MRI)) 181 // Writes non-local memory. 182 WritesMemory = true; 183 if (isRefSet(MRI)) 184 // Ok, it reads non-local memory. 185 ReadsMemory = true; 186 } 187 continue; 188 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 189 // Ignore non-volatile loads from local memory. (Atomic is okay here.) 190 if (!LI->isVolatile()) { 191 MemoryLocation Loc = MemoryLocation::get(LI); 192 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 193 continue; 194 } 195 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 196 // Ignore non-volatile stores to local memory. (Atomic is okay here.) 197 if (!SI->isVolatile()) { 198 MemoryLocation Loc = MemoryLocation::get(SI); 199 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 200 continue; 201 } 202 } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) { 203 // Ignore vaargs on local memory. 204 MemoryLocation Loc = MemoryLocation::get(VI); 205 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) 206 continue; 207 } 208 209 // Any remaining instructions need to be taken seriously! Check if they 210 // read or write memory. 211 // 212 // Writes memory, remember that. 213 WritesMemory |= I->mayWriteToMemory(); 214 215 // If this instruction may read memory, remember that. 216 ReadsMemory |= I->mayReadFromMemory(); 217 } 218 219 if (WritesMemory) { 220 if (!ReadsMemory) 221 return MAK_WriteOnly; 222 else 223 return MAK_MayWrite; 224 } 225 226 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone; 227 } 228 229 MemoryAccessKind llvm::computeFunctionBodyMemoryAccess(Function &F, 230 AAResults &AAR) { 231 return checkFunctionMemoryAccess(F, /*ThisBody=*/true, AAR, {}); 232 } 233 234 /// Deduce readonly/readnone attributes for the SCC. 235 template <typename AARGetterT> 236 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) { 237 // Check if any of the functions in the SCC read or write memory. If they 238 // write memory then they can't be marked readnone or readonly. 239 bool ReadsMemory = false; 240 bool WritesMemory = false; 241 for (Function *F : SCCNodes) { 242 // Call the callable parameter to look up AA results for this function. 243 AAResults &AAR = AARGetter(*F); 244 245 // Non-exact function definitions may not be selected at link time, and an 246 // alternative version that writes to memory may be selected. See the 247 // comment on GlobalValue::isDefinitionExact for more details. 248 switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(), 249 AAR, SCCNodes)) { 250 case MAK_MayWrite: 251 return false; 252 case MAK_ReadOnly: 253 ReadsMemory = true; 254 break; 255 case MAK_WriteOnly: 256 WritesMemory = true; 257 break; 258 case MAK_ReadNone: 259 // Nothing to do! 260 break; 261 } 262 } 263 264 // If the SCC contains both functions that read and functions that write, then 265 // we cannot add readonly attributes. 266 if (ReadsMemory && WritesMemory) 267 return false; 268 269 // Success! Functions in this SCC do not access memory, or only read memory. 270 // Give them the appropriate attribute. 271 bool MadeChange = false; 272 273 for (Function *F : SCCNodes) { 274 if (F->doesNotAccessMemory()) 275 // Already perfect! 276 continue; 277 278 if (F->onlyReadsMemory() && ReadsMemory) 279 // No change. 280 continue; 281 282 if (F->doesNotReadMemory() && WritesMemory) 283 continue; 284 285 MadeChange = true; 286 287 // Clear out any existing attributes. 288 F->removeFnAttr(Attribute::ReadOnly); 289 F->removeFnAttr(Attribute::ReadNone); 290 F->removeFnAttr(Attribute::WriteOnly); 291 292 if (!WritesMemory && !ReadsMemory) { 293 // Clear out any "access range attributes" if readnone was deduced. 294 F->removeFnAttr(Attribute::ArgMemOnly); 295 F->removeFnAttr(Attribute::InaccessibleMemOnly); 296 F->removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly); 297 } 298 299 // Add in the new attribute. 300 if (WritesMemory && !ReadsMemory) 301 F->addFnAttr(Attribute::WriteOnly); 302 else 303 F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone); 304 305 if (WritesMemory && !ReadsMemory) 306 ++NumWriteOnly; 307 else if (ReadsMemory) 308 ++NumReadOnly; 309 else 310 ++NumReadNone; 311 } 312 313 return MadeChange; 314 } 315 316 namespace { 317 318 /// For a given pointer Argument, this retains a list of Arguments of functions 319 /// in the same SCC that the pointer data flows into. We use this to build an 320 /// SCC of the arguments. 321 struct ArgumentGraphNode { 322 Argument *Definition; 323 SmallVector<ArgumentGraphNode *, 4> Uses; 324 }; 325 326 class ArgumentGraph { 327 // We store pointers to ArgumentGraphNode objects, so it's important that 328 // that they not move around upon insert. 329 using ArgumentMapTy = std::map<Argument *, ArgumentGraphNode>; 330 331 ArgumentMapTy ArgumentMap; 332 333 // There is no root node for the argument graph, in fact: 334 // void f(int *x, int *y) { if (...) f(x, y); } 335 // is an example where the graph is disconnected. The SCCIterator requires a 336 // single entry point, so we maintain a fake ("synthetic") root node that 337 // uses every node. Because the graph is directed and nothing points into 338 // the root, it will not participate in any SCCs (except for its own). 339 ArgumentGraphNode SyntheticRoot; 340 341 public: 342 ArgumentGraph() { SyntheticRoot.Definition = nullptr; } 343 344 using iterator = SmallVectorImpl<ArgumentGraphNode *>::iterator; 345 346 iterator begin() { return SyntheticRoot.Uses.begin(); } 347 iterator end() { return SyntheticRoot.Uses.end(); } 348 ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } 349 350 ArgumentGraphNode *operator[](Argument *A) { 351 ArgumentGraphNode &Node = ArgumentMap[A]; 352 Node.Definition = A; 353 SyntheticRoot.Uses.push_back(&Node); 354 return &Node; 355 } 356 }; 357 358 /// This tracker checks whether callees are in the SCC, and if so it does not 359 /// consider that a capture, instead adding it to the "Uses" list and 360 /// continuing with the analysis. 361 struct ArgumentUsesTracker : public CaptureTracker { 362 ArgumentUsesTracker(const SCCNodeSet &SCCNodes) : SCCNodes(SCCNodes) {} 363 364 void tooManyUses() override { Captured = true; } 365 366 bool captured(const Use *U) override { 367 CallSite CS(U->getUser()); 368 if (!CS.getInstruction()) { 369 Captured = true; 370 return true; 371 } 372 373 Function *F = CS.getCalledFunction(); 374 if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) { 375 Captured = true; 376 return true; 377 } 378 379 // Note: the callee and the two successor blocks *follow* the argument 380 // operands. This means there is no need to adjust UseIndex to account for 381 // these. 382 383 unsigned UseIndex = 384 std::distance(const_cast<const Use *>(CS.arg_begin()), U); 385 386 assert(UseIndex < CS.data_operands_size() && 387 "Indirect function calls should have been filtered above!"); 388 389 if (UseIndex >= CS.getNumArgOperands()) { 390 // Data operand, but not a argument operand -- must be a bundle operand 391 assert(CS.hasOperandBundles() && "Must be!"); 392 393 // CaptureTracking told us that we're being captured by an operand bundle 394 // use. In this case it does not matter if the callee is within our SCC 395 // or not -- we've been captured in some unknown way, and we have to be 396 // conservative. 397 Captured = true; 398 return true; 399 } 400 401 if (UseIndex >= F->arg_size()) { 402 assert(F->isVarArg() && "More params than args in non-varargs call"); 403 Captured = true; 404 return true; 405 } 406 407 Uses.push_back(&*std::next(F->arg_begin(), UseIndex)); 408 return false; 409 } 410 411 // True only if certainly captured (used outside our SCC). 412 bool Captured = false; 413 414 // Uses within our SCC. 415 SmallVector<Argument *, 4> Uses; 416 417 const SCCNodeSet &SCCNodes; 418 }; 419 420 } // end anonymous namespace 421 422 namespace llvm { 423 424 template <> struct GraphTraits<ArgumentGraphNode *> { 425 using NodeRef = ArgumentGraphNode *; 426 using ChildIteratorType = SmallVectorImpl<ArgumentGraphNode *>::iterator; 427 428 static NodeRef getEntryNode(NodeRef A) { return A; } 429 static ChildIteratorType child_begin(NodeRef N) { return N->Uses.begin(); } 430 static ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); } 431 }; 432 433 template <> 434 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> { 435 static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); } 436 437 static ChildIteratorType nodes_begin(ArgumentGraph *AG) { 438 return AG->begin(); 439 } 440 441 static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); } 442 }; 443 444 } // end namespace llvm 445 446 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone. 447 static Attribute::AttrKind 448 determinePointerReadAttrs(Argument *A, 449 const SmallPtrSet<Argument *, 8> &SCCNodes) { 450 SmallVector<Use *, 32> Worklist; 451 SmallPtrSet<Use *, 32> Visited; 452 453 // inalloca arguments are always clobbered by the call. 454 if (A->hasInAllocaAttr()) 455 return Attribute::None; 456 457 bool IsRead = false; 458 // We don't need to track IsWritten. If A is written to, return immediately. 459 460 for (Use &U : A->uses()) { 461 Visited.insert(&U); 462 Worklist.push_back(&U); 463 } 464 465 while (!Worklist.empty()) { 466 Use *U = Worklist.pop_back_val(); 467 Instruction *I = cast<Instruction>(U->getUser()); 468 469 switch (I->getOpcode()) { 470 case Instruction::BitCast: 471 case Instruction::GetElementPtr: 472 case Instruction::PHI: 473 case Instruction::Select: 474 case Instruction::AddrSpaceCast: 475 // The original value is not read/written via this if the new value isn't. 476 for (Use &UU : I->uses()) 477 if (Visited.insert(&UU).second) 478 Worklist.push_back(&UU); 479 break; 480 481 case Instruction::Call: 482 case Instruction::Invoke: { 483 bool Captures = true; 484 485 if (I->getType()->isVoidTy()) 486 Captures = false; 487 488 auto AddUsersToWorklistIfCapturing = [&] { 489 if (Captures) 490 for (Use &UU : I->uses()) 491 if (Visited.insert(&UU).second) 492 Worklist.push_back(&UU); 493 }; 494 495 CallSite CS(I); 496 if (CS.doesNotAccessMemory()) { 497 AddUsersToWorklistIfCapturing(); 498 continue; 499 } 500 501 Function *F = CS.getCalledFunction(); 502 if (!F) { 503 if (CS.onlyReadsMemory()) { 504 IsRead = true; 505 AddUsersToWorklistIfCapturing(); 506 continue; 507 } 508 return Attribute::None; 509 } 510 511 // Note: the callee and the two successor blocks *follow* the argument 512 // operands. This means there is no need to adjust UseIndex to account 513 // for these. 514 515 unsigned UseIndex = std::distance(CS.arg_begin(), U); 516 517 // U cannot be the callee operand use: since we're exploring the 518 // transitive uses of an Argument, having such a use be a callee would 519 // imply the CallSite is an indirect call or invoke; and we'd take the 520 // early exit above. 521 assert(UseIndex < CS.data_operands_size() && 522 "Data operand use expected!"); 523 524 bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands(); 525 526 if (UseIndex >= F->arg_size() && !IsOperandBundleUse) { 527 assert(F->isVarArg() && "More params than args in non-varargs call"); 528 return Attribute::None; 529 } 530 531 Captures &= !CS.doesNotCapture(UseIndex); 532 533 // Since the optimizer (by design) cannot see the data flow corresponding 534 // to a operand bundle use, these cannot participate in the optimistic SCC 535 // analysis. Instead, we model the operand bundle uses as arguments in 536 // call to a function external to the SCC. 537 if (IsOperandBundleUse || 538 !SCCNodes.count(&*std::next(F->arg_begin(), UseIndex))) { 539 540 // The accessors used on CallSite here do the right thing for calls and 541 // invokes with operand bundles. 542 543 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex)) 544 return Attribute::None; 545 if (!CS.doesNotAccessMemory(UseIndex)) 546 IsRead = true; 547 } 548 549 AddUsersToWorklistIfCapturing(); 550 break; 551 } 552 553 case Instruction::Load: 554 // A volatile load has side effects beyond what readonly can be relied 555 // upon. 556 if (cast<LoadInst>(I)->isVolatile()) 557 return Attribute::None; 558 559 IsRead = true; 560 break; 561 562 case Instruction::ICmp: 563 case Instruction::Ret: 564 break; 565 566 default: 567 return Attribute::None; 568 } 569 } 570 571 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone; 572 } 573 574 /// Deduce returned attributes for the SCC. 575 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) { 576 bool Changed = false; 577 578 // Check each function in turn, determining if an argument is always returned. 579 for (Function *F : SCCNodes) { 580 // We can infer and propagate function attributes only when we know that the 581 // definition we'll get at link time is *exactly* the definition we see now. 582 // For more details, see GlobalValue::mayBeDerefined. 583 if (!F->hasExactDefinition()) 584 continue; 585 586 if (F->getReturnType()->isVoidTy()) 587 continue; 588 589 // There is nothing to do if an argument is already marked as 'returned'. 590 if (llvm::any_of(F->args(), 591 [](const Argument &Arg) { return Arg.hasReturnedAttr(); })) 592 continue; 593 594 auto FindRetArg = [&]() -> Value * { 595 Value *RetArg = nullptr; 596 for (BasicBlock &BB : *F) 597 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) { 598 // Note that stripPointerCasts should look through functions with 599 // returned arguments. 600 Value *RetVal = Ret->getReturnValue()->stripPointerCasts(); 601 if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType()) 602 return nullptr; 603 604 if (!RetArg) 605 RetArg = RetVal; 606 else if (RetArg != RetVal) 607 return nullptr; 608 } 609 610 return RetArg; 611 }; 612 613 if (Value *RetArg = FindRetArg()) { 614 auto *A = cast<Argument>(RetArg); 615 A->addAttr(Attribute::Returned); 616 ++NumReturned; 617 Changed = true; 618 } 619 } 620 621 return Changed; 622 } 623 624 /// If a callsite has arguments that are also arguments to the parent function, 625 /// try to propagate attributes from the callsite's arguments to the parent's 626 /// arguments. This may be important because inlining can cause information loss 627 /// when attribute knowledge disappears with the inlined call. 628 static bool addArgumentAttrsFromCallsites(Function &F) { 629 if (!EnableNonnullArgPropagation) 630 return false; 631 632 bool Changed = false; 633 634 // For an argument attribute to transfer from a callsite to the parent, the 635 // call must be guaranteed to execute every time the parent is called. 636 // Conservatively, just check for calls in the entry block that are guaranteed 637 // to execute. 638 // TODO: This could be enhanced by testing if the callsite post-dominates the 639 // entry block or by doing simple forward walks or backward walks to the 640 // callsite. 641 BasicBlock &Entry = F.getEntryBlock(); 642 for (Instruction &I : Entry) { 643 if (auto CS = CallSite(&I)) { 644 if (auto *CalledFunc = CS.getCalledFunction()) { 645 for (auto &CSArg : CalledFunc->args()) { 646 if (!CSArg.hasNonNullAttr()) 647 continue; 648 649 // If the non-null callsite argument operand is an argument to 'F' 650 // (the caller) and the call is guaranteed to execute, then the value 651 // must be non-null throughout 'F'. 652 auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo())); 653 if (FArg && !FArg->hasNonNullAttr()) { 654 FArg->addAttr(Attribute::NonNull); 655 Changed = true; 656 } 657 } 658 } 659 } 660 if (!isGuaranteedToTransferExecutionToSuccessor(&I)) 661 break; 662 } 663 664 return Changed; 665 } 666 667 /// Deduce nocapture attributes for the SCC. 668 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) { 669 bool Changed = false; 670 671 ArgumentGraph AG; 672 673 // Check each function in turn, determining which pointer arguments are not 674 // captured. 675 for (Function *F : SCCNodes) { 676 // We can infer and propagate function attributes only when we know that the 677 // definition we'll get at link time is *exactly* the definition we see now. 678 // For more details, see GlobalValue::mayBeDerefined. 679 if (!F->hasExactDefinition()) 680 continue; 681 682 Changed |= addArgumentAttrsFromCallsites(*F); 683 684 // Functions that are readonly (or readnone) and nounwind and don't return 685 // a value can't capture arguments. Don't analyze them. 686 if (F->onlyReadsMemory() && F->doesNotThrow() && 687 F->getReturnType()->isVoidTy()) { 688 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E; 689 ++A) { 690 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 691 A->addAttr(Attribute::NoCapture); 692 ++NumNoCapture; 693 Changed = true; 694 } 695 } 696 continue; 697 } 698 699 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E; 700 ++A) { 701 if (!A->getType()->isPointerTy()) 702 continue; 703 bool HasNonLocalUses = false; 704 if (!A->hasNoCaptureAttr()) { 705 ArgumentUsesTracker Tracker(SCCNodes); 706 PointerMayBeCaptured(&*A, &Tracker); 707 if (!Tracker.Captured) { 708 if (Tracker.Uses.empty()) { 709 // If it's trivially not captured, mark it nocapture now. 710 A->addAttr(Attribute::NoCapture); 711 ++NumNoCapture; 712 Changed = true; 713 } else { 714 // If it's not trivially captured and not trivially not captured, 715 // then it must be calling into another function in our SCC. Save 716 // its particulars for Argument-SCC analysis later. 717 ArgumentGraphNode *Node = AG[&*A]; 718 for (Argument *Use : Tracker.Uses) { 719 Node->Uses.push_back(AG[Use]); 720 if (Use != &*A) 721 HasNonLocalUses = true; 722 } 723 } 724 } 725 // Otherwise, it's captured. Don't bother doing SCC analysis on it. 726 } 727 if (!HasNonLocalUses && !A->onlyReadsMemory()) { 728 // Can we determine that it's readonly/readnone without doing an SCC? 729 // Note that we don't allow any calls at all here, or else our result 730 // will be dependent on the iteration order through the functions in the 731 // SCC. 732 SmallPtrSet<Argument *, 8> Self; 733 Self.insert(&*A); 734 Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self); 735 if (R != Attribute::None) { 736 A->addAttr(R); 737 Changed = true; 738 R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; 739 } 740 } 741 } 742 } 743 744 // The graph we've collected is partial because we stopped scanning for 745 // argument uses once we solved the argument trivially. These partial nodes 746 // show up as ArgumentGraphNode objects with an empty Uses list, and for 747 // these nodes the final decision about whether they capture has already been 748 // made. If the definition doesn't have a 'nocapture' attribute by now, it 749 // captures. 750 751 for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) { 752 const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I; 753 if (ArgumentSCC.size() == 1) { 754 if (!ArgumentSCC[0]->Definition) 755 continue; // synthetic root node 756 757 // eg. "void f(int* x) { if (...) f(x); }" 758 if (ArgumentSCC[0]->Uses.size() == 1 && 759 ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) { 760 Argument *A = ArgumentSCC[0]->Definition; 761 A->addAttr(Attribute::NoCapture); 762 ++NumNoCapture; 763 Changed = true; 764 } 765 continue; 766 } 767 768 bool SCCCaptured = false; 769 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); 770 I != E && !SCCCaptured; ++I) { 771 ArgumentGraphNode *Node = *I; 772 if (Node->Uses.empty()) { 773 if (!Node->Definition->hasNoCaptureAttr()) 774 SCCCaptured = true; 775 } 776 } 777 if (SCCCaptured) 778 continue; 779 780 SmallPtrSet<Argument *, 8> ArgumentSCCNodes; 781 // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for 782 // quickly looking up whether a given Argument is in this ArgumentSCC. 783 for (ArgumentGraphNode *I : ArgumentSCC) { 784 ArgumentSCCNodes.insert(I->Definition); 785 } 786 787 for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); 788 I != E && !SCCCaptured; ++I) { 789 ArgumentGraphNode *N = *I; 790 for (ArgumentGraphNode *Use : N->Uses) { 791 Argument *A = Use->Definition; 792 if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A)) 793 continue; 794 SCCCaptured = true; 795 break; 796 } 797 } 798 if (SCCCaptured) 799 continue; 800 801 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 802 Argument *A = ArgumentSCC[i]->Definition; 803 A->addAttr(Attribute::NoCapture); 804 ++NumNoCapture; 805 Changed = true; 806 } 807 808 // We also want to compute readonly/readnone. With a small number of false 809 // negatives, we can assume that any pointer which is captured isn't going 810 // to be provably readonly or readnone, since by definition we can't 811 // analyze all uses of a captured pointer. 812 // 813 // The false negatives happen when the pointer is captured by a function 814 // that promises readonly/readnone behaviour on the pointer, then the 815 // pointer's lifetime ends before anything that writes to arbitrary memory. 816 // Also, a readonly/readnone pointer may be returned, but returning a 817 // pointer is capturing it. 818 819 Attribute::AttrKind ReadAttr = Attribute::ReadNone; 820 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 821 Argument *A = ArgumentSCC[i]->Definition; 822 Attribute::AttrKind K = determinePointerReadAttrs(A, ArgumentSCCNodes); 823 if (K == Attribute::ReadNone) 824 continue; 825 if (K == Attribute::ReadOnly) { 826 ReadAttr = Attribute::ReadOnly; 827 continue; 828 } 829 ReadAttr = K; 830 break; 831 } 832 833 if (ReadAttr != Attribute::None) { 834 for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 835 Argument *A = ArgumentSCC[i]->Definition; 836 // Clear out existing readonly/readnone attributes 837 A->removeAttr(Attribute::ReadOnly); 838 A->removeAttr(Attribute::ReadNone); 839 A->addAttr(ReadAttr); 840 ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; 841 Changed = true; 842 } 843 } 844 } 845 846 return Changed; 847 } 848 849 /// Tests whether a function is "malloc-like". 850 /// 851 /// A function is "malloc-like" if it returns either null or a pointer that 852 /// doesn't alias any other pointer visible to the caller. 853 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) { 854 SmallSetVector<Value *, 8> FlowsToReturn; 855 for (BasicBlock &BB : *F) 856 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) 857 FlowsToReturn.insert(Ret->getReturnValue()); 858 859 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 860 Value *RetVal = FlowsToReturn[i]; 861 862 if (Constant *C = dyn_cast<Constant>(RetVal)) { 863 if (!C->isNullValue() && !isa<UndefValue>(C)) 864 return false; 865 866 continue; 867 } 868 869 if (isa<Argument>(RetVal)) 870 return false; 871 872 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 873 switch (RVI->getOpcode()) { 874 // Extend the analysis by looking upwards. 875 case Instruction::BitCast: 876 case Instruction::GetElementPtr: 877 case Instruction::AddrSpaceCast: 878 FlowsToReturn.insert(RVI->getOperand(0)); 879 continue; 880 case Instruction::Select: { 881 SelectInst *SI = cast<SelectInst>(RVI); 882 FlowsToReturn.insert(SI->getTrueValue()); 883 FlowsToReturn.insert(SI->getFalseValue()); 884 continue; 885 } 886 case Instruction::PHI: { 887 PHINode *PN = cast<PHINode>(RVI); 888 for (Value *IncValue : PN->incoming_values()) 889 FlowsToReturn.insert(IncValue); 890 continue; 891 } 892 893 // Check whether the pointer came from an allocation. 894 case Instruction::Alloca: 895 break; 896 case Instruction::Call: 897 case Instruction::Invoke: { 898 CallSite CS(RVI); 899 if (CS.hasRetAttr(Attribute::NoAlias)) 900 break; 901 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 902 break; 903 LLVM_FALLTHROUGH; 904 } 905 default: 906 return false; // Did not come from an allocation. 907 } 908 909 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 910 return false; 911 } 912 913 return true; 914 } 915 916 /// Deduce noalias attributes for the SCC. 917 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) { 918 // Check each function in turn, determining which functions return noalias 919 // pointers. 920 for (Function *F : SCCNodes) { 921 // Already noalias. 922 if (F->returnDoesNotAlias()) 923 continue; 924 925 // We can infer and propagate function attributes only when we know that the 926 // definition we'll get at link time is *exactly* the definition we see now. 927 // For more details, see GlobalValue::mayBeDerefined. 928 if (!F->hasExactDefinition()) 929 return false; 930 931 // We annotate noalias return values, which are only applicable to 932 // pointer types. 933 if (!F->getReturnType()->isPointerTy()) 934 continue; 935 936 if (!isFunctionMallocLike(F, SCCNodes)) 937 return false; 938 } 939 940 bool MadeChange = false; 941 for (Function *F : SCCNodes) { 942 if (F->returnDoesNotAlias() || 943 !F->getReturnType()->isPointerTy()) 944 continue; 945 946 F->setReturnDoesNotAlias(); 947 ++NumNoAlias; 948 MadeChange = true; 949 } 950 951 return MadeChange; 952 } 953 954 /// Tests whether this function is known to not return null. 955 /// 956 /// Requires that the function returns a pointer. 957 /// 958 /// Returns true if it believes the function will not return a null, and sets 959 /// \p Speculative based on whether the returned conclusion is a speculative 960 /// conclusion due to SCC calls. 961 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes, 962 bool &Speculative) { 963 assert(F->getReturnType()->isPointerTy() && 964 "nonnull only meaningful on pointer types"); 965 Speculative = false; 966 967 SmallSetVector<Value *, 8> FlowsToReturn; 968 for (BasicBlock &BB : *F) 969 if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) 970 FlowsToReturn.insert(Ret->getReturnValue()); 971 972 auto &DL = F->getParent()->getDataLayout(); 973 974 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 975 Value *RetVal = FlowsToReturn[i]; 976 977 // If this value is locally known to be non-null, we're good 978 if (isKnownNonZero(RetVal, DL)) 979 continue; 980 981 // Otherwise, we need to look upwards since we can't make any local 982 // conclusions. 983 Instruction *RVI = dyn_cast<Instruction>(RetVal); 984 if (!RVI) 985 return false; 986 switch (RVI->getOpcode()) { 987 // Extend the analysis by looking upwards. 988 case Instruction::BitCast: 989 case Instruction::GetElementPtr: 990 case Instruction::AddrSpaceCast: 991 FlowsToReturn.insert(RVI->getOperand(0)); 992 continue; 993 case Instruction::Select: { 994 SelectInst *SI = cast<SelectInst>(RVI); 995 FlowsToReturn.insert(SI->getTrueValue()); 996 FlowsToReturn.insert(SI->getFalseValue()); 997 continue; 998 } 999 case Instruction::PHI: { 1000 PHINode *PN = cast<PHINode>(RVI); 1001 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1002 FlowsToReturn.insert(PN->getIncomingValue(i)); 1003 continue; 1004 } 1005 case Instruction::Call: 1006 case Instruction::Invoke: { 1007 CallSite CS(RVI); 1008 Function *Callee = CS.getCalledFunction(); 1009 // A call to a node within the SCC is assumed to return null until 1010 // proven otherwise 1011 if (Callee && SCCNodes.count(Callee)) { 1012 Speculative = true; 1013 continue; 1014 } 1015 return false; 1016 } 1017 default: 1018 return false; // Unknown source, may be null 1019 }; 1020 llvm_unreachable("should have either continued or returned"); 1021 } 1022 1023 return true; 1024 } 1025 1026 /// Deduce nonnull attributes for the SCC. 1027 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes) { 1028 // Speculative that all functions in the SCC return only nonnull 1029 // pointers. We may refute this as we analyze functions. 1030 bool SCCReturnsNonNull = true; 1031 1032 bool MadeChange = false; 1033 1034 // Check each function in turn, determining which functions return nonnull 1035 // pointers. 1036 for (Function *F : SCCNodes) { 1037 // Already nonnull. 1038 if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex, 1039 Attribute::NonNull)) 1040 continue; 1041 1042 // We can infer and propagate function attributes only when we know that the 1043 // definition we'll get at link time is *exactly* the definition we see now. 1044 // For more details, see GlobalValue::mayBeDerefined. 1045 if (!F->hasExactDefinition()) 1046 return false; 1047 1048 // We annotate nonnull return values, which are only applicable to 1049 // pointer types. 1050 if (!F->getReturnType()->isPointerTy()) 1051 continue; 1052 1053 bool Speculative = false; 1054 if (isReturnNonNull(F, SCCNodes, Speculative)) { 1055 if (!Speculative) { 1056 // Mark the function eagerly since we may discover a function 1057 // which prevents us from speculating about the entire SCC 1058 LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName() 1059 << " as nonnull\n"); 1060 F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull); 1061 ++NumNonNullReturn; 1062 MadeChange = true; 1063 } 1064 continue; 1065 } 1066 // At least one function returns something which could be null, can't 1067 // speculate any more. 1068 SCCReturnsNonNull = false; 1069 } 1070 1071 if (SCCReturnsNonNull) { 1072 for (Function *F : SCCNodes) { 1073 if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex, 1074 Attribute::NonNull) || 1075 !F->getReturnType()->isPointerTy()) 1076 continue; 1077 1078 LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n"); 1079 F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull); 1080 ++NumNonNullReturn; 1081 MadeChange = true; 1082 } 1083 } 1084 1085 return MadeChange; 1086 } 1087 1088 namespace { 1089 1090 /// Collects a set of attribute inference requests and performs them all in one 1091 /// go on a single SCC Node. Inference involves scanning function bodies 1092 /// looking for instructions that violate attribute assumptions. 1093 /// As soon as all the bodies are fine we are free to set the attribute. 1094 /// Customization of inference for individual attributes is performed by 1095 /// providing a handful of predicates for each attribute. 1096 class AttributeInferer { 1097 public: 1098 /// Describes a request for inference of a single attribute. 1099 struct InferenceDescriptor { 1100 1101 /// Returns true if this function does not have to be handled. 1102 /// General intent for this predicate is to provide an optimization 1103 /// for functions that do not need this attribute inference at all 1104 /// (say, for functions that already have the attribute). 1105 std::function<bool(const Function &)> SkipFunction; 1106 1107 /// Returns true if this instruction violates attribute assumptions. 1108 std::function<bool(Instruction &)> InstrBreaksAttribute; 1109 1110 /// Sets the inferred attribute for this function. 1111 std::function<void(Function &)> SetAttribute; 1112 1113 /// Attribute we derive. 1114 Attribute::AttrKind AKind; 1115 1116 /// If true, only "exact" definitions can be used to infer this attribute. 1117 /// See GlobalValue::isDefinitionExact. 1118 bool RequiresExactDefinition; 1119 1120 InferenceDescriptor(Attribute::AttrKind AK, 1121 std::function<bool(const Function &)> SkipFunc, 1122 std::function<bool(Instruction &)> InstrScan, 1123 std::function<void(Function &)> SetAttr, 1124 bool ReqExactDef) 1125 : SkipFunction(SkipFunc), InstrBreaksAttribute(InstrScan), 1126 SetAttribute(SetAttr), AKind(AK), 1127 RequiresExactDefinition(ReqExactDef) {} 1128 }; 1129 1130 private: 1131 SmallVector<InferenceDescriptor, 4> InferenceDescriptors; 1132 1133 public: 1134 void registerAttrInference(InferenceDescriptor AttrInference) { 1135 InferenceDescriptors.push_back(AttrInference); 1136 } 1137 1138 bool run(const SCCNodeSet &SCCNodes); 1139 }; 1140 1141 /// Perform all the requested attribute inference actions according to the 1142 /// attribute predicates stored before. 1143 bool AttributeInferer::run(const SCCNodeSet &SCCNodes) { 1144 SmallVector<InferenceDescriptor, 4> InferInSCC = InferenceDescriptors; 1145 // Go through all the functions in SCC and check corresponding attribute 1146 // assumptions for each of them. Attributes that are invalid for this SCC 1147 // will be removed from InferInSCC. 1148 for (Function *F : SCCNodes) { 1149 1150 // No attributes whose assumptions are still valid - done. 1151 if (InferInSCC.empty()) 1152 return false; 1153 1154 // Check if our attributes ever need scanning/can be scanned. 1155 llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) { 1156 if (ID.SkipFunction(*F)) 1157 return false; 1158 1159 // Remove from further inference (invalidate) when visiting a function 1160 // that has no instructions to scan/has an unsuitable definition. 1161 return F->isDeclaration() || 1162 (ID.RequiresExactDefinition && !F->hasExactDefinition()); 1163 }); 1164 1165 // For each attribute still in InferInSCC that doesn't explicitly skip F, 1166 // set up the F instructions scan to verify assumptions of the attribute. 1167 SmallVector<InferenceDescriptor, 4> InferInThisFunc; 1168 llvm::copy_if( 1169 InferInSCC, std::back_inserter(InferInThisFunc), 1170 [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); }); 1171 1172 if (InferInThisFunc.empty()) 1173 continue; 1174 1175 // Start instruction scan. 1176 for (Instruction &I : instructions(*F)) { 1177 llvm::erase_if(InferInThisFunc, [&](const InferenceDescriptor &ID) { 1178 if (!ID.InstrBreaksAttribute(I)) 1179 return false; 1180 // Remove attribute from further inference on any other functions 1181 // because attribute assumptions have just been violated. 1182 llvm::erase_if(InferInSCC, [&ID](const InferenceDescriptor &D) { 1183 return D.AKind == ID.AKind; 1184 }); 1185 // Remove attribute from the rest of current instruction scan. 1186 return true; 1187 }); 1188 1189 if (InferInThisFunc.empty()) 1190 break; 1191 } 1192 } 1193 1194 if (InferInSCC.empty()) 1195 return false; 1196 1197 bool Changed = false; 1198 for (Function *F : SCCNodes) 1199 // At this point InferInSCC contains only functions that were either: 1200 // - explicitly skipped from scan/inference, or 1201 // - verified to have no instructions that break attribute assumptions. 1202 // Hence we just go and force the attribute for all non-skipped functions. 1203 for (auto &ID : InferInSCC) { 1204 if (ID.SkipFunction(*F)) 1205 continue; 1206 Changed = true; 1207 ID.SetAttribute(*F); 1208 } 1209 return Changed; 1210 } 1211 1212 } // end anonymous namespace 1213 1214 /// Helper for non-Convergent inference predicate InstrBreaksAttribute. 1215 static bool InstrBreaksNonConvergent(Instruction &I, 1216 const SCCNodeSet &SCCNodes) { 1217 const CallSite CS(&I); 1218 // Breaks non-convergent assumption if CS is a convergent call to a function 1219 // not in the SCC. 1220 return CS && CS.isConvergent() && SCCNodes.count(CS.getCalledFunction()) == 0; 1221 } 1222 1223 /// Helper for NoUnwind inference predicate InstrBreaksAttribute. 1224 static bool InstrBreaksNonThrowing(Instruction &I, const SCCNodeSet &SCCNodes) { 1225 if (!I.mayThrow()) 1226 return false; 1227 if (const auto *CI = dyn_cast<CallInst>(&I)) { 1228 if (Function *Callee = CI->getCalledFunction()) { 1229 // I is a may-throw call to a function inside our SCC. This doesn't 1230 // invalidate our current working assumption that the SCC is no-throw; we 1231 // just have to scan that other function. 1232 if (SCCNodes.count(Callee) > 0) 1233 return false; 1234 } 1235 } 1236 return true; 1237 } 1238 1239 /// Helper for NoFree inference predicate InstrBreaksAttribute. 1240 static bool InstrBreaksNoFree(Instruction &I, const SCCNodeSet &SCCNodes) { 1241 CallSite CS(&I); 1242 if (!CS) 1243 return false; 1244 1245 Function *Callee = CS.getCalledFunction(); 1246 if (!Callee) 1247 return true; 1248 1249 if (Callee->doesNotFreeMemory()) 1250 return false; 1251 1252 if (SCCNodes.count(Callee) > 0) 1253 return false; 1254 1255 return true; 1256 } 1257 1258 /// Infer attributes from all functions in the SCC by scanning every 1259 /// instruction for compliance to the attribute assumptions. Currently it 1260 /// does: 1261 /// - removal of Convergent attribute 1262 /// - addition of NoUnwind attribute 1263 /// 1264 /// Returns true if any changes to function attributes were made. 1265 static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) { 1266 1267 AttributeInferer AI; 1268 1269 // Request to remove the convergent attribute from all functions in the SCC 1270 // if every callsite within the SCC is not convergent (except for calls 1271 // to functions within the SCC). 1272 // Note: Removal of the attr from the callsites will happen in 1273 // InstCombineCalls separately. 1274 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{ 1275 Attribute::Convergent, 1276 // Skip non-convergent functions. 1277 [](const Function &F) { return !F.isConvergent(); }, 1278 // Instructions that break non-convergent assumption. 1279 [SCCNodes](Instruction &I) { 1280 return InstrBreaksNonConvergent(I, SCCNodes); 1281 }, 1282 [](Function &F) { 1283 LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName() 1284 << "\n"); 1285 F.setNotConvergent(); 1286 }, 1287 /* RequiresExactDefinition= */ false}); 1288 1289 if (!DisableNoUnwindInference) 1290 // Request to infer nounwind attribute for all the functions in the SCC if 1291 // every callsite within the SCC is not throwing (except for calls to 1292 // functions within the SCC). Note that nounwind attribute suffers from 1293 // derefinement - results may change depending on how functions are 1294 // optimized. Thus it can be inferred only from exact definitions. 1295 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{ 1296 Attribute::NoUnwind, 1297 // Skip non-throwing functions. 1298 [](const Function &F) { return F.doesNotThrow(); }, 1299 // Instructions that break non-throwing assumption. 1300 [SCCNodes](Instruction &I) { 1301 return InstrBreaksNonThrowing(I, SCCNodes); 1302 }, 1303 [](Function &F) { 1304 LLVM_DEBUG(dbgs() 1305 << "Adding nounwind attr to fn " << F.getName() << "\n"); 1306 F.setDoesNotThrow(); 1307 ++NumNoUnwind; 1308 }, 1309 /* RequiresExactDefinition= */ true}); 1310 1311 if (!DisableNoFreeInference) 1312 // Request to infer nofree attribute for all the functions in the SCC if 1313 // every callsite within the SCC does not directly or indirectly free 1314 // memory (except for calls to functions within the SCC). Note that nofree 1315 // attribute suffers from derefinement - results may change depending on 1316 // how functions are optimized. Thus it can be inferred only from exact 1317 // definitions. 1318 AI.registerAttrInference(AttributeInferer::InferenceDescriptor{ 1319 Attribute::NoFree, 1320 // Skip functions known not to free memory. 1321 [](const Function &F) { return F.doesNotFreeMemory(); }, 1322 // Instructions that break non-deallocating assumption. 1323 [SCCNodes](Instruction &I) { 1324 return InstrBreaksNoFree(I, SCCNodes); 1325 }, 1326 [](Function &F) { 1327 LLVM_DEBUG(dbgs() 1328 << "Adding nofree attr to fn " << F.getName() << "\n"); 1329 F.setDoesNotFreeMemory(); 1330 ++NumNoFree; 1331 }, 1332 /* RequiresExactDefinition= */ true}); 1333 1334 // Perform all the requested attribute inference actions. 1335 return AI.run(SCCNodes); 1336 } 1337 1338 static bool setDoesNotRecurse(Function &F) { 1339 if (F.doesNotRecurse()) 1340 return false; 1341 F.setDoesNotRecurse(); 1342 ++NumNoRecurse; 1343 return true; 1344 } 1345 1346 static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) { 1347 // Try and identify functions that do not recurse. 1348 1349 // If the SCC contains multiple nodes we know for sure there is recursion. 1350 if (SCCNodes.size() != 1) 1351 return false; 1352 1353 Function *F = *SCCNodes.begin(); 1354 if (!F || !F->hasExactDefinition() || F->doesNotRecurse()) 1355 return false; 1356 1357 // If all of the calls in F are identifiable and are to norecurse functions, F 1358 // is norecurse. This check also detects self-recursion as F is not currently 1359 // marked norecurse, so any called from F to F will not be marked norecurse. 1360 for (auto &BB : *F) 1361 for (auto &I : BB.instructionsWithoutDebug()) 1362 if (auto CS = CallSite(&I)) { 1363 Function *Callee = CS.getCalledFunction(); 1364 if (!Callee || Callee == F || !Callee->doesNotRecurse()) 1365 // Function calls a potentially recursive function. 1366 return false; 1367 } 1368 1369 // Every call was to a non-recursive function other than this function, and 1370 // we have no indirect recursion as the SCC size is one. This function cannot 1371 // recurse. 1372 return setDoesNotRecurse(*F); 1373 } 1374 1375 template <typename AARGetterT> 1376 static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes, 1377 AARGetterT &&AARGetter, 1378 bool HasUnknownCall) { 1379 bool Changed = false; 1380 1381 // Bail if the SCC only contains optnone functions. 1382 if (SCCNodes.empty()) 1383 return Changed; 1384 1385 Changed |= addArgumentReturnedAttrs(SCCNodes); 1386 Changed |= addReadAttrs(SCCNodes, AARGetter); 1387 Changed |= addArgumentAttrs(SCCNodes); 1388 1389 // If we have no external nodes participating in the SCC, we can deduce some 1390 // more precise attributes as well. 1391 if (!HasUnknownCall) { 1392 Changed |= addNoAliasAttrs(SCCNodes); 1393 Changed |= addNonNullAttrs(SCCNodes); 1394 Changed |= inferAttrsFromFunctionBodies(SCCNodes); 1395 Changed |= addNoRecurseAttrs(SCCNodes); 1396 } 1397 1398 return Changed; 1399 } 1400 1401 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C, 1402 CGSCCAnalysisManager &AM, 1403 LazyCallGraph &CG, 1404 CGSCCUpdateResult &) { 1405 FunctionAnalysisManager &FAM = 1406 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager(); 1407 1408 // We pass a lambda into functions to wire them up to the analysis manager 1409 // for getting function analyses. 1410 auto AARGetter = [&](Function &F) -> AAResults & { 1411 return FAM.getResult<AAManager>(F); 1412 }; 1413 1414 // Fill SCCNodes with the elements of the SCC. Also track whether there are 1415 // any external or opt-none nodes that will prevent us from optimizing any 1416 // part of the SCC. 1417 SCCNodeSet SCCNodes; 1418 bool HasUnknownCall = false; 1419 for (LazyCallGraph::Node &N : C) { 1420 Function &F = N.getFunction(); 1421 if (F.hasOptNone() || F.hasFnAttribute(Attribute::Naked)) { 1422 // Treat any function we're trying not to optimize as if it were an 1423 // indirect call and omit it from the node set used below. 1424 HasUnknownCall = true; 1425 continue; 1426 } 1427 // Track whether any functions in this SCC have an unknown call edge. 1428 // Note: if this is ever a performance hit, we can common it with 1429 // subsequent routines which also do scans over the instructions of the 1430 // function. 1431 if (!HasUnknownCall) 1432 for (Instruction &I : instructions(F)) 1433 if (auto CS = CallSite(&I)) 1434 if (!CS.getCalledFunction()) { 1435 HasUnknownCall = true; 1436 break; 1437 } 1438 1439 SCCNodes.insert(&F); 1440 } 1441 1442 if (deriveAttrsInPostOrder(SCCNodes, AARGetter, HasUnknownCall)) 1443 return PreservedAnalyses::none(); 1444 1445 return PreservedAnalyses::all(); 1446 } 1447 1448 namespace { 1449 1450 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass { 1451 // Pass identification, replacement for typeid 1452 static char ID; 1453 1454 PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) { 1455 initializePostOrderFunctionAttrsLegacyPassPass( 1456 *PassRegistry::getPassRegistry()); 1457 } 1458 1459 bool runOnSCC(CallGraphSCC &SCC) override; 1460 1461 void getAnalysisUsage(AnalysisUsage &AU) const override { 1462 AU.setPreservesCFG(); 1463 AU.addRequired<AssumptionCacheTracker>(); 1464 getAAResultsAnalysisUsage(AU); 1465 CallGraphSCCPass::getAnalysisUsage(AU); 1466 } 1467 }; 1468 1469 } // end anonymous namespace 1470 1471 char PostOrderFunctionAttrsLegacyPass::ID = 0; 1472 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs", 1473 "Deduce function attributes", false, false) 1474 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1475 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 1476 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs", 1477 "Deduce function attributes", false, false) 1478 1479 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() { 1480 return new PostOrderFunctionAttrsLegacyPass(); 1481 } 1482 1483 template <typename AARGetterT> 1484 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) { 1485 1486 // Fill SCCNodes with the elements of the SCC. Used for quickly looking up 1487 // whether a given CallGraphNode is in this SCC. Also track whether there are 1488 // any external or opt-none nodes that will prevent us from optimizing any 1489 // part of the SCC. 1490 SCCNodeSet SCCNodes; 1491 bool ExternalNode = false; 1492 for (CallGraphNode *I : SCC) { 1493 Function *F = I->getFunction(); 1494 if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) { 1495 // External node or function we're trying not to optimize - we both avoid 1496 // transform them and avoid leveraging information they provide. 1497 ExternalNode = true; 1498 continue; 1499 } 1500 1501 SCCNodes.insert(F); 1502 } 1503 1504 return deriveAttrsInPostOrder(SCCNodes, AARGetter, ExternalNode); 1505 } 1506 1507 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) { 1508 if (skipSCC(SCC)) 1509 return false; 1510 return runImpl(SCC, LegacyAARGetter(*this)); 1511 } 1512 1513 namespace { 1514 1515 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass { 1516 // Pass identification, replacement for typeid 1517 static char ID; 1518 1519 ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) { 1520 initializeReversePostOrderFunctionAttrsLegacyPassPass( 1521 *PassRegistry::getPassRegistry()); 1522 } 1523 1524 bool runOnModule(Module &M) override; 1525 1526 void getAnalysisUsage(AnalysisUsage &AU) const override { 1527 AU.setPreservesCFG(); 1528 AU.addRequired<CallGraphWrapperPass>(); 1529 AU.addPreserved<CallGraphWrapperPass>(); 1530 } 1531 }; 1532 1533 } // end anonymous namespace 1534 1535 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0; 1536 1537 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs", 1538 "Deduce function attributes in RPO", false, false) 1539 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 1540 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs", 1541 "Deduce function attributes in RPO", false, false) 1542 1543 Pass *llvm::createReversePostOrderFunctionAttrsPass() { 1544 return new ReversePostOrderFunctionAttrsLegacyPass(); 1545 } 1546 1547 static bool addNoRecurseAttrsTopDown(Function &F) { 1548 // We check the preconditions for the function prior to calling this to avoid 1549 // the cost of building up a reversible post-order list. We assert them here 1550 // to make sure none of the invariants this relies on were violated. 1551 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!"); 1552 assert(!F.doesNotRecurse() && 1553 "This function has already been deduced as norecurs!"); 1554 assert(F.hasInternalLinkage() && 1555 "Can only do top-down deduction for internal linkage functions!"); 1556 1557 // If F is internal and all of its uses are calls from a non-recursive 1558 // functions, then none of its calls could in fact recurse without going 1559 // through a function marked norecurse, and so we can mark this function too 1560 // as norecurse. Note that the uses must actually be calls -- otherwise 1561 // a pointer to this function could be returned from a norecurse function but 1562 // this function could be recursively (indirectly) called. Note that this 1563 // also detects if F is directly recursive as F is not yet marked as 1564 // a norecurse function. 1565 for (auto *U : F.users()) { 1566 auto *I = dyn_cast<Instruction>(U); 1567 if (!I) 1568 return false; 1569 CallSite CS(I); 1570 if (!CS || !CS.getParent()->getParent()->doesNotRecurse()) 1571 return false; 1572 } 1573 return setDoesNotRecurse(F); 1574 } 1575 1576 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) { 1577 // We only have a post-order SCC traversal (because SCCs are inherently 1578 // discovered in post-order), so we accumulate them in a vector and then walk 1579 // it in reverse. This is simpler than using the RPO iterator infrastructure 1580 // because we need to combine SCC detection and the PO walk of the call 1581 // graph. We can also cheat egregiously because we're primarily interested in 1582 // synthesizing norecurse and so we can only save the singular SCCs as SCCs 1583 // with multiple functions in them will clearly be recursive. 1584 SmallVector<Function *, 16> Worklist; 1585 for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) { 1586 if (I->size() != 1) 1587 continue; 1588 1589 Function *F = I->front()->getFunction(); 1590 if (F && !F->isDeclaration() && !F->doesNotRecurse() && 1591 F->hasInternalLinkage()) 1592 Worklist.push_back(F); 1593 } 1594 1595 bool Changed = false; 1596 for (auto *F : llvm::reverse(Worklist)) 1597 Changed |= addNoRecurseAttrsTopDown(*F); 1598 1599 return Changed; 1600 } 1601 1602 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) { 1603 if (skipModule(M)) 1604 return false; 1605 1606 auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 1607 1608 return deduceFunctionAttributeInRPO(M, CG); 1609 } 1610 1611 PreservedAnalyses 1612 ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) { 1613 auto &CG = AM.getResult<CallGraphAnalysis>(M); 1614 1615 if (!deduceFunctionAttributeInRPO(M, CG)) 1616 return PreservedAnalyses::all(); 1617 1618 PreservedAnalyses PA; 1619 PA.preserve<CallGraphAnalysis>(); 1620 return PA; 1621 } 1622