Mercurial > hg > CbC > CbC_llvm

comparison lib/Transforms/IPO/FunctionAttrs.cpp @ 100:7d135dc70f03 LLVM 3.9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.9
author Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
date Tue, 26 Jan 2016 22:53:40 +0900
parents afa8332a0e37
children 1172e4bd9c6f
comparison
equal deleted inserted replaced
96:6418606d0ead 100:7d135dc70f03
4 // 4 //
5 // This file is distributed under the University of Illinois Open Source 5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details. 6 // License. See LICENSE.TXT for details.
7 // 7 //
8 //===----------------------------------------------------------------------===// 8 //===----------------------------------------------------------------------===//
9 // 9 ///
10 // This file implements a simple interprocedural pass which walks the 10 /// \file
11 // call-graph, looking for functions which do not access or only read 11 /// This file implements interprocedural passes which walk the
12 // non-local memory, and marking them readnone/readonly. It does the 12 /// call-graph deducing and/or propagating function attributes.
13 // same with function arguments independently, marking them readonly/ 13 ///
14 // readnone/nocapture. Finally, well-known library call declarations
15 // are marked with all attributes that are consistent with the
16 // function's standard definition. This pass is implemented as a
17 // bottom-up traversal of the call-graph.
18 //
19 //===----------------------------------------------------------------------===// 14 //===----------------------------------------------------------------------===//
20 15
21 #include "llvm/Transforms/IPO.h" 16 #include "llvm/Transforms/IPO.h"
22 #include "llvm/ADT/SCCIterator.h" 17 #include "llvm/ADT/SCCIterator.h"
23 #include "llvm/ADT/SetVector.h" 18 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallSet.h" 19 #include "llvm/ADT/SmallSet.h"
25 #include "llvm/ADT/Statistic.h" 20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/ADT/StringSwitch.h"
26 #include "llvm/Analysis/AliasAnalysis.h" 22 #include "llvm/Analysis/AliasAnalysis.h"
27 #include "llvm/Analysis/AssumptionCache.h" 23 #include "llvm/Analysis/AssumptionCache.h"
28 #include "llvm/Analysis/BasicAliasAnalysis.h" 24 #include "llvm/Analysis/BasicAliasAnalysis.h"
29 #include "llvm/Analysis/CallGraph.h" 25 #include "llvm/Analysis/CallGraph.h"
30 #include "llvm/Analysis/CallGraphSCCPass.h" 26 #include "llvm/Analysis/CallGraphSCCPass.h"
47 STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 43 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
48 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone"); 44 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
49 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly"); 45 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
50 STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 46 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
51 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull"); 47 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
52 STATISTIC(NumAnnotated, "Number of attributes added to library functions"); 48 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
53 49
54 namespace { 50 namespace {
55 struct FunctionAttrs : public CallGraphSCCPass { 51 typedef SmallSetVector<Function *, 8> SCCNodeSet;
52 }
53
54 namespace {
55 struct PostOrderFunctionAttrs : public CallGraphSCCPass {
56 static char ID; // Pass identification, replacement for typeid 56 static char ID; // Pass identification, replacement for typeid
57 FunctionAttrs() : CallGraphSCCPass(ID) { 57 PostOrderFunctionAttrs() : CallGraphSCCPass(ID) {
58 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); 58 initializePostOrderFunctionAttrsPass(*PassRegistry::getPassRegistry());
59 } 59 }
60 60
61 bool runOnSCC(CallGraphSCC &SCC) override; 61 bool runOnSCC(CallGraphSCC &SCC) override;
62 62
63 void getAnalysisUsage(AnalysisUsage &AU) const override { 63 void getAnalysisUsage(AnalysisUsage &AU) const override {
67 CallGraphSCCPass::getAnalysisUsage(AU); 67 CallGraphSCCPass::getAnalysisUsage(AU);
68 } 68 }
69 69
70 private: 70 private:
71 TargetLibraryInfo *TLI; 71 TargetLibraryInfo *TLI;
72
73 bool AddReadAttrs(const CallGraphSCC &SCC);
74 bool AddArgumentAttrs(const CallGraphSCC &SCC);
75 bool AddNoAliasAttrs(const CallGraphSCC &SCC);
76 bool AddNonNullAttrs(const CallGraphSCC &SCC);
77 bool annotateLibraryCalls(const CallGraphSCC &SCC);
78 }; 72 };
79 } 73 }
80 74
81 char FunctionAttrs::ID = 0; 75 char PostOrderFunctionAttrs::ID = 0;
82 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 76 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrs, "functionattrs",
83 "Deduce function attributes", false, false) 77 "Deduce function attributes", false, false)
84 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 78 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
85 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 79 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
86 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 80 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
87 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 81 INITIALIZE_PASS_END(PostOrderFunctionAttrs, "functionattrs",
88 "Deduce function attributes", false, false) 82 "Deduce function attributes", false, false)
89 83
90 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 84 Pass *llvm::createPostOrderFunctionAttrsPass() { return new PostOrderFunctionAttrs(); }
91 85
92 namespace { 86 namespace {
93 /// The three kinds of memory access relevant to 'readonly' and 87 /// The three kinds of memory access relevant to 'readonly' and
94 /// 'readnone' attributes. 88 /// 'readnone' attributes.
95 enum MemoryAccessKind { 89 enum MemoryAccessKind {
97 MAK_ReadOnly = 1, 91 MAK_ReadOnly = 1,
98 MAK_MayWrite = 2 92 MAK_MayWrite = 2
99 }; 93 };
100 } 94 }
101 95
102 static MemoryAccessKind 96 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR,
103 checkFunctionMemoryAccess(Function &F, AAResults &AAR, 97 const SCCNodeSet &SCCNodes) {
104 const SmallPtrSetImpl<Function *> &SCCNodes) {
105 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F); 98 FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
106 if (MRB == FMRB_DoesNotAccessMemory) 99 if (MRB == FMRB_DoesNotAccessMemory)
107 // Already perfect! 100 // Already perfect!
108 return MAK_ReadNone; 101 return MAK_ReadNone;
109 102
128 if (CS) { 121 if (CS) {
129 // Ignore calls to functions in the same SCC. 122 // Ignore calls to functions in the same SCC.
130 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 123 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
131 continue; 124 continue;
132 FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS); 125 FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS);
133 // If the call doesn't access arbitrary memory, we may be able to 126
134 // figure out something. 127 // If the call doesn't access memory, we're done.
135 if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 128 if (!(MRB & MRI_ModRef))
136 // If the call does access argument pointees, check each argument. 129 continue;
137 if (AliasAnalysis::doesAccessArgPointees(MRB)) 130
138 // Check whether all pointer arguments point to local memory, and 131 if (!AliasAnalysis::onlyAccessesArgPointees(MRB)) {
139 // ignore calls that only access local memory. 132 // The call could access any memory. If that includes writes, give up.
140 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 133 if (MRB & MRI_Mod)
141 CI != CE; ++CI) { 134 return MAK_MayWrite;
142 Value *Arg = *CI; 135 // If it reads, note it.
143 if (Arg->getType()->isPointerTy()) { 136 if (MRB & MRI_Ref)
144 AAMDNodes AAInfo; 137 ReadsMemory = true;
145 I->getAAMetadata(AAInfo); 138 continue;
146 139 }
147 MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo); 140
148 if (!AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) { 141 // Check whether all pointer arguments point to local memory, and
149 if (MRB & MRI_Mod) 142 // ignore calls that only access local memory.
150 // Writes non-local memory. Give up. 143 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
151 return MAK_MayWrite; 144 CI != CE; ++CI) {
152 if (MRB & MRI_Ref) 145 Value *Arg = *CI;
153 // Ok, it reads non-local memory. 146 if (!Arg->getType()->isPtrOrPtrVectorTy())
154 ReadsMemory = true; 147 continue;
155 } 148
156 } 149 AAMDNodes AAInfo;
157 } 150 I->getAAMetadata(AAInfo);
158 continue; 151 MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
159 } 152
160 // The call could access any memory. If that includes writes, give up. 153 // Skip accesses to local or constant memory as they don't impact the
161 if (MRB & MRI_Mod) 154 // externally visible mod/ref behavior.
162 return MAK_MayWrite; 155 if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
163 // If it reads, note it. 156 continue;
164 if (MRB & MRI_Ref) 157
165 ReadsMemory = true; 158 if (MRB & MRI_Mod)
159 // Writes non-local memory. Give up.
160 return MAK_MayWrite;
161 if (MRB & MRI_Ref)
162 // Ok, it reads non-local memory.
163 ReadsMemory = true;
164 }
166 continue; 165 continue;
167 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 166 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
168 // Ignore non-volatile loads from local memory. (Atomic is okay here.) 167 // Ignore non-volatile loads from local memory. (Atomic is okay here.)
169 if (!LI->isVolatile()) { 168 if (!LI->isVolatile()) {
170 MemoryLocation Loc = MemoryLocation::get(LI); 169 MemoryLocation Loc = MemoryLocation::get(LI);
197 196
198 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone; 197 return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
199 } 198 }
200 199
201 /// Deduce readonly/readnone attributes for the SCC. 200 /// Deduce readonly/readnone attributes for the SCC.
202 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 201 template <typename AARGetterT>
203 SmallPtrSet<Function *, 8> SCCNodes; 202 static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT AARGetter) {
204
205 // Fill SCCNodes with the elements of the SCC. Used for quickly
206 // looking up whether a given CallGraphNode is in this SCC.
207 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
208 SCCNodes.insert((*I)->getFunction());
209
210 // Check if any of the functions in the SCC read or write memory. If they 203 // Check if any of the functions in the SCC read or write memory. If they
211 // write memory then they can't be marked readnone or readonly. 204 // write memory then they can't be marked readnone or readonly.
212 bool ReadsMemory = false; 205 bool ReadsMemory = false;
213 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 206 for (Function *F : SCCNodes) {
214 Function *F = (*I)->getFunction(); 207 // Call the callable parameter to look up AA results for this function.
215 208 AAResults &AAR = AARGetter(*F);
216 if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
217 // External node or node we don't want to optimize - assume it may write
218 // memory and give up.
219 return false;
220
221 // We need to manually construct BasicAA directly in order to disable its
222 // use of other function analyses.
223 BasicAAResult BAR(createLegacyPMBasicAAResult(*this, *F));
224
225 // Construct our own AA results for this function. We do this manually to
226 // work around the limitations of the legacy pass manager.
227 AAResults AAR(createLegacyPMAAResults(*this, *F, BAR));
228 209
229 switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) { 210 switch (checkFunctionMemoryAccess(*F, AAR, SCCNodes)) {
230 case MAK_MayWrite: 211 case MAK_MayWrite:
231 return false; 212 return false;
232 case MAK_ReadOnly: 213 case MAK_ReadOnly:
239 } 220 }
240 221
241 // Success! Functions in this SCC do not access memory, or only read memory. 222 // Success! Functions in this SCC do not access memory, or only read memory.
242 // Give them the appropriate attribute. 223 // Give them the appropriate attribute.
243 bool MadeChange = false; 224 bool MadeChange = false;
244 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 225 for (Function *F : SCCNodes) {
245 Function *F = (*I)->getFunction();
246
247 if (F->doesNotAccessMemory()) 226 if (F->doesNotAccessMemory())
248 // Already perfect! 227 // Already perfect!
249 continue; 228 continue;
250 229
251 if (F->onlyReadsMemory() && ReadsMemory) 230 if (F->onlyReadsMemory() && ReadsMemory)
317 296
318 /// This tracker checks whether callees are in the SCC, and if so it does not 297 /// This tracker checks whether callees are in the SCC, and if so it does not
319 /// consider that a capture, instead adding it to the "Uses" list and 298 /// consider that a capture, instead adding it to the "Uses" list and
320 /// continuing with the analysis. 299 /// continuing with the analysis.
321 struct ArgumentUsesTracker : public CaptureTracker { 300 struct ArgumentUsesTracker : public CaptureTracker {
322 ArgumentUsesTracker(const SmallPtrSet<Function *, 8> &SCCNodes) 301 ArgumentUsesTracker(const SCCNodeSet &SCCNodes)
323 : Captured(false), SCCNodes(SCCNodes) {} 302 : Captured(false), SCCNodes(SCCNodes) {}
324 303
325 void tooManyUses() override { Captured = true; } 304 void tooManyUses() override { Captured = true; }
326 305
327 bool captured(const Use *U) override { 306 bool captured(const Use *U) override {
330 Captured = true; 309 Captured = true;
331 return true; 310 return true;
332 } 311 }
333 312
334 Function *F = CS.getCalledFunction(); 313 Function *F = CS.getCalledFunction();
335 if (!F || !SCCNodes.count(F)) { 314 if (!F || F->isDeclaration() || F->mayBeOverridden() ||
315 !SCCNodes.count(F)) {
336 Captured = true; 316 Captured = true;
337 return true; 317 return true;
338 } 318 }
339 319
340 bool Found = false; 320 // Note: the callee and the two successor blocks *follow* the argument
341 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 321 // operands. This means there is no need to adjust UseIndex to account for
342 for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end(); 322 // these.
343 PI != PE; ++PI, ++AI) { 323
344 if (AI == AE) { 324 unsigned UseIndex =
345 assert(F->isVarArg() && "More params than args in non-varargs call"); 325 std::distance(const_cast<const Use *>(CS.arg_begin()), U);
346 Captured = true; 326
347 return true; 327 assert(UseIndex < CS.data_operands_size() &&
348 } 328 "Indirect function calls should have been filtered above!");
349 if (PI == U) { 329
350 Uses.push_back(AI); 330 if (UseIndex >= CS.getNumArgOperands()) {
351 Found = true; 331 // Data operand, but not a argument operand -- must be a bundle operand
352 break; 332 assert(CS.hasOperandBundles() && "Must be!");
353 } 333
354 } 334 // CaptureTracking told us that we're being captured by an operand bundle
355 assert(Found && "Capturing call-site captured nothing?"); 335 // use. In this case it does not matter if the callee is within our SCC
356 (void)Found; 336 // or not -- we've been captured in some unknown way, and we have to be
337 // conservative.
338 Captured = true;
339 return true;
340 }
341
342 if (UseIndex >= F->arg_size()) {
343 assert(F->isVarArg() && "More params than args in non-varargs call");
344 Captured = true;
345 return true;
346 }
347
348 Uses.push_back(&*std::next(F->arg_begin(), UseIndex));
357 return false; 349 return false;
358 } 350 }
359 351
360 bool Captured; // True only if certainly captured (used outside our SCC). 352 bool Captured; // True only if certainly captured (used outside our SCC).
361 SmallVector<Argument *, 4> Uses; // Uses within our SCC. 353 SmallVector<Argument *, 4> Uses; // Uses within our SCC.
362 354
363 const SmallPtrSet<Function *, 8> &SCCNodes; 355 const SCCNodeSet &SCCNodes;
364 }; 356 };
365 } 357 }
366 358
367 namespace llvm { 359 namespace llvm {
368 template <> struct GraphTraits<ArgumentGraphNode *> { 360 template <> struct GraphTraits<ArgumentGraphNode *> {
410 } 402 }
411 403
412 while (!Worklist.empty()) { 404 while (!Worklist.empty()) {
413 Use *U = Worklist.pop_back_val(); 405 Use *U = Worklist.pop_back_val();
414 Instruction *I = cast<Instruction>(U->getUser()); 406 Instruction *I = cast<Instruction>(U->getUser());
415 Value *V = U->get();
416 407
417 switch (I->getOpcode()) { 408 switch (I->getOpcode()) {
418 case Instruction::BitCast: 409 case Instruction::BitCast:
419 case Instruction::GetElementPtr: 410 case Instruction::GetElementPtr:
420 case Instruction::PHI: 411 case Instruction::PHI:
454 continue; 445 continue;
455 } 446 }
456 return Attribute::None; 447 return Attribute::None;
457 } 448 }
458 449
459 Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 450 // Note: the callee and the two successor blocks *follow* the argument
460 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 451 // operands. This means there is no need to adjust UseIndex to account
461 for (CallSite::arg_iterator A = B; A != E; ++A, ++AI) { 452 // for these.
462 if (A->get() == V) { 453
463 if (AI == AE) { 454 unsigned UseIndex = std::distance(CS.arg_begin(), U);
464 assert(F->isVarArg() && 455
465 "More params than args in non-varargs call."); 456 // U cannot be the callee operand use: since we're exploring the
466 return Attribute::None; 457 // transitive uses of an Argument, having such a use be a callee would
467 } 458 // imply the CallSite is an indirect call or invoke; and we'd take the
468 Captures &= !CS.doesNotCapture(A - B); 459 // early exit above.
469 if (SCCNodes.count(AI)) 460 assert(UseIndex < CS.data_operands_size() &&
470 continue; 461 "Data operand use expected!");
471 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B)) 462
472 return Attribute::None; 463 bool IsOperandBundleUse = UseIndex >= CS.getNumArgOperands();
473 if (!CS.doesNotAccessMemory(A - B)) 464
474 IsRead = true; 465 if (UseIndex >= F->arg_size() && !IsOperandBundleUse) {
475 } 466 assert(F->isVarArg() && "More params than args in non-varargs call");
476 } 467 return Attribute::None;
468 }
469
470 Captures &= !CS.doesNotCapture(UseIndex);
471
472 // Since the optimizer (by design) cannot see the data flow corresponding
473 // to a operand bundle use, these cannot participate in the optimistic SCC
474 // analysis. Instead, we model the operand bundle uses as arguments in
475 // call to a function external to the SCC.
476 if (!SCCNodes.count(&*std::next(F->arg_begin(), UseIndex)) ||
477 IsOperandBundleUse) {
478
479 // The accessors used on CallSite here do the right thing for calls and
480 // invokes with operand bundles.
481
482 if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(UseIndex))
483 return Attribute::None;
484 if (!CS.doesNotAccessMemory(UseIndex))
485 IsRead = true;
486 }
487
477 AddUsersToWorklistIfCapturing(); 488 AddUsersToWorklistIfCapturing();
478 break; 489 break;
479 } 490 }
480 491
481 case Instruction::Load: 492 case Instruction::Load:
493 504
494 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone; 505 return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
495 } 506 }
496 507
497 /// Deduce nocapture attributes for the SCC. 508 /// Deduce nocapture attributes for the SCC.
498 bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) { 509 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
499 bool Changed = false; 510 bool Changed = false;
500
501 SmallPtrSet<Function *, 8> SCCNodes;
502
503 // Fill SCCNodes with the elements of the SCC. Used for quickly
504 // looking up whether a given CallGraphNode is in this SCC.
505 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
506 Function *F = (*I)->getFunction();
507 if (F && !F->isDeclaration() && !F->mayBeOverridden() &&
508 !F->hasFnAttribute(Attribute::OptimizeNone))
509 SCCNodes.insert(F);
510 }
511 511
512 ArgumentGraph AG; 512 ArgumentGraph AG;
513 513
514 AttrBuilder B; 514 AttrBuilder B;
515 B.addAttribute(Attribute::NoCapture); 515 B.addAttribute(Attribute::NoCapture);
516 516
517 // Check each function in turn, determining which pointer arguments are not 517 // Check each function in turn, determining which pointer arguments are not
518 // captured. 518 // captured.
519 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 519 for (Function *F : SCCNodes) {
520 Function *F = (*I)->getFunction();
521
522 if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
523 // External node or function we're trying not to optimize - only a problem
524 // for arguments that we pass to it.
525 continue;
526
527 // Definitions with weak linkage may be overridden at linktime with 520 // Definitions with weak linkage may be overridden at linktime with
528 // something that captures pointers, so treat them like declarations. 521 // something that captures pointers, so treat them like declarations.
529 if (F->isDeclaration() || F->mayBeOverridden()) 522 if (F->isDeclaration() || F->mayBeOverridden())
530 continue; 523 continue;
531 524
549 if (!A->getType()->isPointerTy()) 542 if (!A->getType()->isPointerTy())
550 continue; 543 continue;
551 bool HasNonLocalUses = false; 544 bool HasNonLocalUses = false;
552 if (!A->hasNoCaptureAttr()) { 545 if (!A->hasNoCaptureAttr()) {
553 ArgumentUsesTracker Tracker(SCCNodes); 546 ArgumentUsesTracker Tracker(SCCNodes);
554 PointerMayBeCaptured(A, &Tracker); 547 PointerMayBeCaptured(&*A, &Tracker);
555 if (!Tracker.Captured) { 548 if (!Tracker.Captured) {
556 if (Tracker.Uses.empty()) { 549 if (Tracker.Uses.empty()) {
557 // If it's trivially not captured, mark it nocapture now. 550 // If it's trivially not captured, mark it nocapture now.
558 A->addAttr( 551 A->addAttr(
559 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); 552 AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
561 Changed = true; 554 Changed = true;
562 } else { 555 } else {
563 // If it's not trivially captured and not trivially not captured, 556 // If it's not trivially captured and not trivially not captured,
564 // then it must be calling into another function in our SCC. Save 557 // then it must be calling into another function in our SCC. Save
565 // its particulars for Argument-SCC analysis later. 558 // its particulars for Argument-SCC analysis later.
566 ArgumentGraphNode *Node = AG[A]; 559 ArgumentGraphNode *Node = AG[&*A];
567 for (SmallVectorImpl<Argument *>::iterator 560 for (SmallVectorImpl<Argument *>::iterator
568 UI = Tracker.Uses.begin(), 561 UI = Tracker.Uses.begin(),
569 UE = Tracker.Uses.end(); 562 UE = Tracker.Uses.end();
570 UI != UE; ++UI) { 563 UI != UE; ++UI) {
571 Node->Uses.push_back(AG[*UI]); 564 Node->Uses.push_back(AG[*UI]);
580 // Can we determine that it's readonly/readnone without doing an SCC? 573 // Can we determine that it's readonly/readnone without doing an SCC?
581 // Note that we don't allow any calls at all here, or else our result 574 // Note that we don't allow any calls at all here, or else our result
582 // will be dependent on the iteration order through the functions in the 575 // will be dependent on the iteration order through the functions in the
583 // SCC. 576 // SCC.
584 SmallPtrSet<Argument *, 8> Self; 577 SmallPtrSet<Argument *, 8> Self;
585 Self.insert(A); 578 Self.insert(&*A);
586 Attribute::AttrKind R = determinePointerReadAttrs(A, Self); 579 Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
587 if (R != Attribute::None) { 580 if (R != Attribute::None) {
588 AttrBuilder B; 581 AttrBuilder B;
589 B.addAttribute(R); 582 B.addAttribute(R);
590 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 583 A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
591 Changed = true; 584 Changed = true;
706 699
707 /// Tests whether a function is "malloc-like". 700 /// Tests whether a function is "malloc-like".
708 /// 701 ///
709 /// A function is "malloc-like" if it returns either null or a pointer that 702 /// A function is "malloc-like" if it returns either null or a pointer that
710 /// doesn't alias any other pointer visible to the caller. 703 /// doesn't alias any other pointer visible to the caller.
711 static bool isFunctionMallocLike(Function *F, 704 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
712 SmallPtrSet<Function *, 8> &SCCNodes) {
713 SmallSetVector<Value *, 8> FlowsToReturn; 705 SmallSetVector<Value *, 8> FlowsToReturn;
714 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 706 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
715 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 707 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
716 FlowsToReturn.insert(Ret->getReturnValue()); 708 FlowsToReturn.insert(Ret->getReturnValue());
717 709
770 762
771 return true; 763 return true;
772 } 764 }
773 765
774 /// Deduce noalias attributes for the SCC. 766 /// Deduce noalias attributes for the SCC.
775 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 767 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
776 SmallPtrSet<Function *, 8> SCCNodes;
777
778 // Fill SCCNodes with the elements of the SCC. Used for quickly
779 // looking up whether a given CallGraphNode is in this SCC.
780 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
781 SCCNodes.insert((*I)->getFunction());
782
783 // Check each function in turn, determining which functions return noalias 768 // Check each function in turn, determining which functions return noalias
784 // pointers. 769 // pointers.
785 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 770 for (Function *F : SCCNodes) {
786 Function *F = (*I)->getFunction();
787
788 if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
789 // External node or node we don't want to optimize - skip it;
790 return false;
791
792 // Already noalias. 771 // Already noalias.
793 if (F->doesNotAlias(0)) 772 if (F->doesNotAlias(0))
794 continue; 773 continue;
795 774
796 // Definitions with weak linkage may be overridden at linktime, so 775 // Definitions with weak linkage may be overridden at linktime, so
806 if (!isFunctionMallocLike(F, SCCNodes)) 785 if (!isFunctionMallocLike(F, SCCNodes))
807 return false; 786 return false;
808 } 787 }
809 788
810 bool MadeChange = false; 789 bool MadeChange = false;
811 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 790 for (Function *F : SCCNodes) {
812 Function *F = (*I)->getFunction();
813 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 791 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy())
814 continue; 792 continue;
815 793
816 F->setDoesNotAlias(0); 794 F->setDoesNotAlias(0);
817 ++NumNoAlias; 795 ++NumNoAlias;
826 /// Requires that the function returns a pointer. 804 /// Requires that the function returns a pointer.
827 /// 805 ///
828 /// Returns true if it believes the function will not return a null, and sets 806 /// Returns true if it believes the function will not return a null, and sets
829 /// \p Speculative based on whether the returned conclusion is a speculative 807 /// \p Speculative based on whether the returned conclusion is a speculative
830 /// conclusion due to SCC calls. 808 /// conclusion due to SCC calls.
831 static bool isReturnNonNull(Function *F, SmallPtrSet<Function *, 8> &SCCNodes, 809 static bool isReturnNonNull(Function *F, const SCCNodeSet &SCCNodes,
832 const TargetLibraryInfo &TLI, bool &Speculative) { 810 const TargetLibraryInfo &TLI, bool &Speculative) {
833 assert(F->getReturnType()->isPointerTy() && 811 assert(F->getReturnType()->isPointerTy() &&
834 "nonnull only meaningful on pointer types"); 812 "nonnull only meaningful on pointer types");
835 Speculative = false; 813 Speculative = false;
836 814
890 868
891 return true; 869 return true;
892 } 870 }
893 871
894 /// Deduce nonnull attributes for the SCC. 872 /// Deduce nonnull attributes for the SCC.
895 bool FunctionAttrs::AddNonNullAttrs(const CallGraphSCC &SCC) { 873 static bool addNonNullAttrs(const SCCNodeSet &SCCNodes,
896 SmallPtrSet<Function *, 8> SCCNodes; 874 const TargetLibraryInfo &TLI) {
897
898 // Fill SCCNodes with the elements of the SCC. Used for quickly
899 // looking up whether a given CallGraphNode is in this SCC.
900 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
901 SCCNodes.insert((*I)->getFunction());
902
903 // Speculative that all functions in the SCC return only nonnull 875 // Speculative that all functions in the SCC return only nonnull
904 // pointers. We may refute this as we analyze functions. 876 // pointers. We may refute this as we analyze functions.
905 bool SCCReturnsNonNull = true; 877 bool SCCReturnsNonNull = true;
906 878
907 bool MadeChange = false; 879 bool MadeChange = false;
908 880
909 // Check each function in turn, determining which functions return nonnull 881 // Check each function in turn, determining which functions return nonnull
910 // pointers. 882 // pointers.
911 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 883 for (Function *F : SCCNodes) {
912 Function *F = (*I)->getFunction();
913
914 if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
915 // External node or node we don't want to optimize - skip it;
916 return false;
917
918 // Already nonnull. 884 // Already nonnull.
919 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, 885 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
920 Attribute::NonNull)) 886 Attribute::NonNull))
921 continue; 887 continue;
922 888
929 // pointer types. 895 // pointer types.
930 if (!F->getReturnType()->isPointerTy()) 896 if (!F->getReturnType()->isPointerTy())
931 continue; 897 continue;
932 898
933 bool Speculative = false; 899 bool Speculative = false;
934 if (isReturnNonNull(F, SCCNodes, *TLI, Speculative)) { 900 if (isReturnNonNull(F, SCCNodes, TLI, Speculative)) {
935 if (!Speculative) { 901 if (!Speculative) {
936 // Mark the function eagerly since we may discover a function 902 // Mark the function eagerly since we may discover a function
937 // which prevents us from speculating about the entire SCC 903 // which prevents us from speculating about the entire SCC
938 DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n"); 904 DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
939 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull); 905 F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
946 // speculate any more. 912 // speculate any more.
947 SCCReturnsNonNull = false; 913 SCCReturnsNonNull = false;
948 } 914 }
949 915
950 if (SCCReturnsNonNull) { 916 if (SCCReturnsNonNull) {
951 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 917 for (Function *F : SCCNodes) {
952 Function *F = (*I)->getFunction();
953 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex, 918 if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
954 Attribute::NonNull) || 919 Attribute::NonNull) ||
955 !F->getReturnType()->isPointerTy()) 920 !F->getReturnType()->isPointerTy())
956 continue; 921 continue;
957 922
963 } 928 }
964 929
965 return MadeChange; 930 return MadeChange;
966 } 931 }
967 932
968 static void setDoesNotAccessMemory(Function &F) { 933 static bool setDoesNotRecurse(Function &F) {
969 if (!F.doesNotAccessMemory()) { 934 if (F.doesNotRecurse())
970 F.setDoesNotAccessMemory();
971 ++NumAnnotated;
972 }
973 }
974
975 static void setOnlyReadsMemory(Function &F) {
976 if (!F.onlyReadsMemory()) {
977 F.setOnlyReadsMemory();
978 ++NumAnnotated;
979 }
980 }
981
982 static void setDoesNotThrow(Function &F) {
983 if (!F.doesNotThrow()) {
984 F.setDoesNotThrow();
985 ++NumAnnotated;
986 }
987 }
988
989 static void setDoesNotCapture(Function &F, unsigned n) {
990 if (!F.doesNotCapture(n)) {
991 F.setDoesNotCapture(n);
992 ++NumAnnotated;
993 }
994 }
995
996 static void setOnlyReadsMemory(Function &F, unsigned n) {
997 if (!F.onlyReadsMemory(n)) {
998 F.setOnlyReadsMemory(n);
999 ++NumAnnotated;
1000 }
1001 }
1002
1003 static void setDoesNotAlias(Function &F, unsigned n) {
1004 if (!F.doesNotAlias(n)) {
1005 F.setDoesNotAlias(n);
1006 ++NumAnnotated;
1007 }
1008 }
1009
1010 /// Analyze the name and prototype of the given function and set any applicable
1011 /// attributes.
1012 ///
1013 /// Returns true if any attributes were set and false otherwise.
1014 static bool inferPrototypeAttributes(Function &F, const TargetLibraryInfo &TLI) {
1015 if (F.hasFnAttribute(Attribute::OptimizeNone))
1016 return false; 935 return false;
1017 936 F.setDoesNotRecurse();
1018 FunctionType *FTy = F.getFunctionType(); 937 ++NumNoRecurse;
1019 LibFunc::Func TheLibFunc; 938 return true;
1020 if (!(TLI.getLibFunc(F.getName(), TheLibFunc) && TLI.has(TheLibFunc))) 939 }
940
941 static bool addNoRecurseAttrs(const CallGraphSCC &SCC) {
942 // Try and identify functions that do not recurse.
943
944 // If the SCC contains multiple nodes we know for sure there is recursion.
945 if (!SCC.isSingular())
1021 return false; 946 return false;
1022 947
1023 switch (TheLibFunc) { 948 const CallGraphNode *CGN = *SCC.begin();
1024 case LibFunc::strlen: 949 Function *F = CGN->getFunction();
1025 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy()) 950 if (!F || F->isDeclaration() || F->doesNotRecurse())
1026 return false;
1027 setOnlyReadsMemory(F);
1028 setDoesNotThrow(F);
1029 setDoesNotCapture(F, 1);
1030 break;
1031 case LibFunc::strchr:
1032 case LibFunc::strrchr:
1033 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1034 !FTy->getParamType(1)->isIntegerTy())
1035 return false;
1036 setOnlyReadsMemory(F);
1037 setDoesNotThrow(F);
1038 break;
1039 case LibFunc::strtol:
1040 case LibFunc::strtod:
1041 case LibFunc::strtof:
1042 case LibFunc::strtoul:
1043 case LibFunc::strtoll:
1044 case LibFunc::strtold:
1045 case LibFunc::strtoull:
1046 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1047 return false;
1048 setDoesNotThrow(F);
1049 setDoesNotCapture(F, 2);
1050 setOnlyReadsMemory(F, 1);
1051 break;
1052 case LibFunc::strcpy:
1053 case LibFunc::stpcpy:
1054 case LibFunc::strcat:
1055 case LibFunc::strncat:
1056 case LibFunc::strncpy:
1057 case LibFunc::stpncpy:
1058 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1059 return false;
1060 setDoesNotThrow(F);
1061 setDoesNotCapture(F, 2);
1062 setOnlyReadsMemory(F, 2);
1063 break;
1064 case LibFunc::strxfrm:
1065 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1066 !FTy->getParamType(1)->isPointerTy())
1067 return false;
1068 setDoesNotThrow(F);
1069 setDoesNotCapture(F, 1);
1070 setDoesNotCapture(F, 2);
1071 setOnlyReadsMemory(F, 2);
1072 break;
1073 case LibFunc::strcmp: // 0,1
1074 case LibFunc::strspn: // 0,1
1075 case LibFunc::strncmp: // 0,1
1076 case LibFunc::strcspn: // 0,1
1077 case LibFunc::strcoll: // 0,1
1078 case LibFunc::strcasecmp: // 0,1
1079 case LibFunc::strncasecmp: //
1080 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1081 !FTy->getParamType(1)->isPointerTy())
1082 return false;
1083 setOnlyReadsMemory(F);
1084 setDoesNotThrow(F);
1085 setDoesNotCapture(F, 1);
1086 setDoesNotCapture(F, 2);
1087 break;
1088 case LibFunc::strstr:
1089 case LibFunc::strpbrk:
1090 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1091 return false;
1092 setOnlyReadsMemory(F);
1093 setDoesNotThrow(F);
1094 setDoesNotCapture(F, 2);
1095 break;
1096 case LibFunc::strtok:
1097 case LibFunc::strtok_r:
1098 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1099 return false;
1100 setDoesNotThrow(F);
1101 setDoesNotCapture(F, 2);
1102 setOnlyReadsMemory(F, 2);
1103 break;
1104 case LibFunc::scanf:
1105 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1106 return false;
1107 setDoesNotThrow(F);
1108 setDoesNotCapture(F, 1);
1109 setOnlyReadsMemory(F, 1);
1110 break;
1111 case LibFunc::setbuf:
1112 case LibFunc::setvbuf:
1113 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1114 return false;
1115 setDoesNotThrow(F);
1116 setDoesNotCapture(F, 1);
1117 break;
1118 case LibFunc::strdup:
1119 case LibFunc::strndup:
1120 if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
1121 !FTy->getParamType(0)->isPointerTy())
1122 return false;
1123 setDoesNotThrow(F);
1124 setDoesNotAlias(F, 0);
1125 setDoesNotCapture(F, 1);
1126 setOnlyReadsMemory(F, 1);
1127 break;
1128 case LibFunc::stat:
1129 case LibFunc::statvfs:
1130 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1131 !FTy->getParamType(1)->isPointerTy())
1132 return false;
1133 setDoesNotThrow(F);
1134 setDoesNotCapture(F, 1);
1135 setDoesNotCapture(F, 2);
1136 setOnlyReadsMemory(F, 1);
1137 break;
1138 case LibFunc::sscanf:
1139 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1140 !FTy->getParamType(1)->isPointerTy())
1141 return false;
1142 setDoesNotThrow(F);
1143 setDoesNotCapture(F, 1);
1144 setDoesNotCapture(F, 2);
1145 setOnlyReadsMemory(F, 1);
1146 setOnlyReadsMemory(F, 2);
1147 break;
1148 case LibFunc::sprintf:
1149 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1150 !FTy->getParamType(1)->isPointerTy())
1151 return false;
1152 setDoesNotThrow(F);
1153 setDoesNotCapture(F, 1);
1154 setDoesNotCapture(F, 2);
1155 setOnlyReadsMemory(F, 2);
1156 break;
1157 case LibFunc::snprintf:
1158 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1159 !FTy->getParamType(2)->isPointerTy())
1160 return false;
1161 setDoesNotThrow(F);
1162 setDoesNotCapture(F, 1);
1163 setDoesNotCapture(F, 3);
1164 setOnlyReadsMemory(F, 3);
1165 break;
1166 case LibFunc::setitimer:
1167 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
1168 !FTy->getParamType(2)->isPointerTy())
1169 return false;
1170 setDoesNotThrow(F);
1171 setDoesNotCapture(F, 2);
1172 setDoesNotCapture(F, 3);
1173 setOnlyReadsMemory(F, 2);
1174 break;
1175 case LibFunc::system:
1176 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1177 return false;
1178 // May throw; "system" is a valid pthread cancellation point.
1179 setDoesNotCapture(F, 1);
1180 setOnlyReadsMemory(F, 1);
1181 break;
1182 case LibFunc::malloc:
1183 if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy())
1184 return false;
1185 setDoesNotThrow(F);
1186 setDoesNotAlias(F, 0);
1187 break;
1188 case LibFunc::memcmp:
1189 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1190 !FTy->getParamType(1)->isPointerTy())
1191 return false;
1192 setOnlyReadsMemory(F);
1193 setDoesNotThrow(F);
1194 setDoesNotCapture(F, 1);
1195 setDoesNotCapture(F, 2);
1196 break;
1197 case LibFunc::memchr:
1198 case LibFunc::memrchr:
1199 if (FTy->getNumParams() != 3)
1200 return false;
1201 setOnlyReadsMemory(F);
1202 setDoesNotThrow(F);
1203 break;
1204 case LibFunc::modf:
1205 case LibFunc::modff:
1206 case LibFunc::modfl:
1207 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1208 return false;
1209 setDoesNotThrow(F);
1210 setDoesNotCapture(F, 2);
1211 break;
1212 case LibFunc::memcpy:
1213 case LibFunc::memccpy:
1214 case LibFunc::memmove:
1215 if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
1216 return false;
1217 setDoesNotThrow(F);
1218 setDoesNotCapture(F, 2);
1219 setOnlyReadsMemory(F, 2);
1220 break;
1221 case LibFunc::memalign:
1222 if (!FTy->getReturnType()->isPointerTy())
1223 return false;
1224 setDoesNotAlias(F, 0);
1225 break;
1226 case LibFunc::mkdir:
1227 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1228 return false;
1229 setDoesNotThrow(F);
1230 setDoesNotCapture(F, 1);
1231 setOnlyReadsMemory(F, 1);
1232 break;
1233 case LibFunc::mktime:
1234 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1235 return false;
1236 setDoesNotThrow(F);
1237 setDoesNotCapture(F, 1);
1238 break;
1239 case LibFunc::realloc:
1240 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1241 !FTy->getReturnType()->isPointerTy())
1242 return false;
1243 setDoesNotThrow(F);
1244 setDoesNotAlias(F, 0);
1245 setDoesNotCapture(F, 1);
1246 break;
1247 case LibFunc::read:
1248 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1249 return false;
1250 // May throw; "read" is a valid pthread cancellation point.
1251 setDoesNotCapture(F, 2);
1252 break;
1253 case LibFunc::rewind:
1254 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1255 return false;
1256 setDoesNotThrow(F);
1257 setDoesNotCapture(F, 1);
1258 break;
1259 case LibFunc::rmdir:
1260 case LibFunc::remove:
1261 case LibFunc::realpath:
1262 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1263 return false;
1264 setDoesNotThrow(F);
1265 setDoesNotCapture(F, 1);
1266 setOnlyReadsMemory(F, 1);
1267 break;
1268 case LibFunc::rename:
1269 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1270 !FTy->getParamType(1)->isPointerTy())
1271 return false;
1272 setDoesNotThrow(F);
1273 setDoesNotCapture(F, 1);
1274 setDoesNotCapture(F, 2);
1275 setOnlyReadsMemory(F, 1);
1276 setOnlyReadsMemory(F, 2);
1277 break;
1278 case LibFunc::readlink:
1279 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1280 !FTy->getParamType(1)->isPointerTy())
1281 return false;
1282 setDoesNotThrow(F);
1283 setDoesNotCapture(F, 1);
1284 setDoesNotCapture(F, 2);
1285 setOnlyReadsMemory(F, 1);
1286 break;
1287 case LibFunc::write:
1288 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1289 return false;
1290 // May throw; "write" is a valid pthread cancellation point.
1291 setDoesNotCapture(F, 2);
1292 setOnlyReadsMemory(F, 2);
1293 break;
1294 case LibFunc::bcopy:
1295 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1296 !FTy->getParamType(1)->isPointerTy())
1297 return false;
1298 setDoesNotThrow(F);
1299 setDoesNotCapture(F, 1);
1300 setDoesNotCapture(F, 2);
1301 setOnlyReadsMemory(F, 1);
1302 break;
1303 case LibFunc::bcmp:
1304 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1305 !FTy->getParamType(1)->isPointerTy())
1306 return false;
1307 setDoesNotThrow(F);
1308 setOnlyReadsMemory(F);
1309 setDoesNotCapture(F, 1);
1310 setDoesNotCapture(F, 2);
1311 break;
1312 case LibFunc::bzero:
1313 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1314 return false;
1315 setDoesNotThrow(F);
1316 setDoesNotCapture(F, 1);
1317 break;
1318 case LibFunc::calloc:
1319 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy())
1320 return false;
1321 setDoesNotThrow(F);
1322 setDoesNotAlias(F, 0);
1323 break;
1324 case LibFunc::chmod:
1325 case LibFunc::chown:
1326 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1327 return false;
1328 setDoesNotThrow(F);
1329 setDoesNotCapture(F, 1);
1330 setOnlyReadsMemory(F, 1);
1331 break;
1332 case LibFunc::ctermid:
1333 case LibFunc::clearerr:
1334 case LibFunc::closedir:
1335 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1336 return false;
1337 setDoesNotThrow(F);
1338 setDoesNotCapture(F, 1);
1339 break;
1340 case LibFunc::atoi:
1341 case LibFunc::atol:
1342 case LibFunc::atof:
1343 case LibFunc::atoll:
1344 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1345 return false;
1346 setDoesNotThrow(F);
1347 setOnlyReadsMemory(F);
1348 setDoesNotCapture(F, 1);
1349 break;
1350 case LibFunc::access:
1351 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1352 return false;
1353 setDoesNotThrow(F);
1354 setDoesNotCapture(F, 1);
1355 setOnlyReadsMemory(F, 1);
1356 break;
1357 case LibFunc::fopen:
1358 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1359 !FTy->getParamType(0)->isPointerTy() ||
1360 !FTy->getParamType(1)->isPointerTy())
1361 return false;
1362 setDoesNotThrow(F);
1363 setDoesNotAlias(F, 0);
1364 setDoesNotCapture(F, 1);
1365 setDoesNotCapture(F, 2);
1366 setOnlyReadsMemory(F, 1);
1367 setOnlyReadsMemory(F, 2);
1368 break;
1369 case LibFunc::fdopen:
1370 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1371 !FTy->getParamType(1)->isPointerTy())
1372 return false;
1373 setDoesNotThrow(F);
1374 setDoesNotAlias(F, 0);
1375 setDoesNotCapture(F, 2);
1376 setOnlyReadsMemory(F, 2);
1377 break;
1378 case LibFunc::feof:
1379 case LibFunc::free:
1380 case LibFunc::fseek:
1381 case LibFunc::ftell:
1382 case LibFunc::fgetc:
1383 case LibFunc::fseeko:
1384 case LibFunc::ftello:
1385 case LibFunc::fileno:
1386 case LibFunc::fflush:
1387 case LibFunc::fclose:
1388 case LibFunc::fsetpos:
1389 case LibFunc::flockfile:
1390 case LibFunc::funlockfile:
1391 case LibFunc::ftrylockfile:
1392 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1393 return false;
1394 setDoesNotThrow(F);
1395 setDoesNotCapture(F, 1);
1396 break;
1397 case LibFunc::ferror:
1398 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1399 return false;
1400 setDoesNotThrow(F);
1401 setDoesNotCapture(F, 1);
1402 setOnlyReadsMemory(F);
1403 break;
1404 case LibFunc::fputc:
1405 case LibFunc::fstat:
1406 case LibFunc::frexp:
1407 case LibFunc::frexpf:
1408 case LibFunc::frexpl:
1409 case LibFunc::fstatvfs:
1410 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1411 return false;
1412 setDoesNotThrow(F);
1413 setDoesNotCapture(F, 2);
1414 break;
1415 case LibFunc::fgets:
1416 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1417 !FTy->getParamType(2)->isPointerTy())
1418 return false;
1419 setDoesNotThrow(F);
1420 setDoesNotCapture(F, 3);
1421 break;
1422 case LibFunc::fread:
1423 if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
1424 !FTy->getParamType(3)->isPointerTy())
1425 return false;
1426 setDoesNotThrow(F);
1427 setDoesNotCapture(F, 1);
1428 setDoesNotCapture(F, 4);
1429 break;
1430 case LibFunc::fwrite:
1431 if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
1432 !FTy->getParamType(3)->isPointerTy())
1433 return false;
1434 setDoesNotThrow(F);
1435 setDoesNotCapture(F, 1);
1436 setDoesNotCapture(F, 4);
1437 break;
1438 case LibFunc::fputs:
1439 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1440 !FTy->getParamType(1)->isPointerTy())
1441 return false;
1442 setDoesNotThrow(F);
1443 setDoesNotCapture(F, 1);
1444 setDoesNotCapture(F, 2);
1445 setOnlyReadsMemory(F, 1);
1446 break;
1447 case LibFunc::fscanf:
1448 case LibFunc::fprintf:
1449 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1450 !FTy->getParamType(1)->isPointerTy())
1451 return false;
1452 setDoesNotThrow(F);
1453 setDoesNotCapture(F, 1);
1454 setDoesNotCapture(F, 2);
1455 setOnlyReadsMemory(F, 2);
1456 break;
1457 case LibFunc::fgetpos:
1458 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
1459 !FTy->getParamType(1)->isPointerTy())
1460 return false;
1461 setDoesNotThrow(F);
1462 setDoesNotCapture(F, 1);
1463 setDoesNotCapture(F, 2);
1464 break;
1465 case LibFunc::getc:
1466 case LibFunc::getlogin_r:
1467 case LibFunc::getc_unlocked:
1468 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1469 return false;
1470 setDoesNotThrow(F);
1471 setDoesNotCapture(F, 1);
1472 break;
1473 case LibFunc::getenv:
1474 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1475 return false;
1476 setDoesNotThrow(F);
1477 setOnlyReadsMemory(F);
1478 setDoesNotCapture(F, 1);
1479 break;
1480 case LibFunc::gets:
1481 case LibFunc::getchar:
1482 setDoesNotThrow(F);
1483 break;
1484 case LibFunc::getitimer:
1485 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1486 return false;
1487 setDoesNotThrow(F);
1488 setDoesNotCapture(F, 2);
1489 break;
1490 case LibFunc::getpwnam:
1491 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1492 return false;
1493 setDoesNotThrow(F);
1494 setDoesNotCapture(F, 1);
1495 setOnlyReadsMemory(F, 1);
1496 break;
1497 case LibFunc::ungetc:
1498 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1499 return false;
1500 setDoesNotThrow(F);
1501 setDoesNotCapture(F, 2);
1502 break;
1503 case LibFunc::uname:
1504 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1505 return false;
1506 setDoesNotThrow(F);
1507 setDoesNotCapture(F, 1);
1508 break;
1509 case LibFunc::unlink:
1510 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1511 return false;
1512 setDoesNotThrow(F);
1513 setDoesNotCapture(F, 1);
1514 setOnlyReadsMemory(F, 1);
1515 break;
1516 case LibFunc::unsetenv:
1517 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1518 return false;
1519 setDoesNotThrow(F);
1520 setDoesNotCapture(F, 1);
1521 setOnlyReadsMemory(F, 1);
1522 break;
1523 case LibFunc::utime:
1524 case LibFunc::utimes:
1525 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1526 !FTy->getParamType(1)->isPointerTy())
1527 return false;
1528 setDoesNotThrow(F);
1529 setDoesNotCapture(F, 1);
1530 setDoesNotCapture(F, 2);
1531 setOnlyReadsMemory(F, 1);
1532 setOnlyReadsMemory(F, 2);
1533 break;
1534 case LibFunc::putc:
1535 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1536 return false;
1537 setDoesNotThrow(F);
1538 setDoesNotCapture(F, 2);
1539 break;
1540 case LibFunc::puts:
1541 case LibFunc::printf:
1542 case LibFunc::perror:
1543 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1544 return false;
1545 setDoesNotThrow(F);
1546 setDoesNotCapture(F, 1);
1547 setOnlyReadsMemory(F, 1);
1548 break;
1549 case LibFunc::pread:
1550 if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1551 return false;
1552 // May throw; "pread" is a valid pthread cancellation point.
1553 setDoesNotCapture(F, 2);
1554 break;
1555 case LibFunc::pwrite:
1556 if (FTy->getNumParams() != 4 || !FTy->getParamType(1)->isPointerTy())
1557 return false;
1558 // May throw; "pwrite" is a valid pthread cancellation point.
1559 setDoesNotCapture(F, 2);
1560 setOnlyReadsMemory(F, 2);
1561 break;
1562 case LibFunc::putchar:
1563 setDoesNotThrow(F);
1564 break;
1565 case LibFunc::popen:
1566 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1567 !FTy->getParamType(0)->isPointerTy() ||
1568 !FTy->getParamType(1)->isPointerTy())
1569 return false;
1570 setDoesNotThrow(F);
1571 setDoesNotAlias(F, 0);
1572 setDoesNotCapture(F, 1);
1573 setDoesNotCapture(F, 2);
1574 setOnlyReadsMemory(F, 1);
1575 setOnlyReadsMemory(F, 2);
1576 break;
1577 case LibFunc::pclose:
1578 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1579 return false;
1580 setDoesNotThrow(F);
1581 setDoesNotCapture(F, 1);
1582 break;
1583 case LibFunc::vscanf:
1584 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1585 return false;
1586 setDoesNotThrow(F);
1587 setDoesNotCapture(F, 1);
1588 setOnlyReadsMemory(F, 1);
1589 break;
1590 case LibFunc::vsscanf:
1591 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
1592 !FTy->getParamType(2)->isPointerTy())
1593 return false;
1594 setDoesNotThrow(F);
1595 setDoesNotCapture(F, 1);
1596 setDoesNotCapture(F, 2);
1597 setOnlyReadsMemory(F, 1);
1598 setOnlyReadsMemory(F, 2);
1599 break;
1600 case LibFunc::vfscanf:
1601 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
1602 !FTy->getParamType(2)->isPointerTy())
1603 return false;
1604 setDoesNotThrow(F);
1605 setDoesNotCapture(F, 1);
1606 setDoesNotCapture(F, 2);
1607 setOnlyReadsMemory(F, 2);
1608 break;
1609 case LibFunc::valloc:
1610 if (!FTy->getReturnType()->isPointerTy())
1611 return false;
1612 setDoesNotThrow(F);
1613 setDoesNotAlias(F, 0);
1614 break;
1615 case LibFunc::vprintf:
1616 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy())
1617 return false;
1618 setDoesNotThrow(F);
1619 setDoesNotCapture(F, 1);
1620 setOnlyReadsMemory(F, 1);
1621 break;
1622 case LibFunc::vfprintf:
1623 case LibFunc::vsprintf:
1624 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
1625 !FTy->getParamType(1)->isPointerTy())
1626 return false;
1627 setDoesNotThrow(F);
1628 setDoesNotCapture(F, 1);
1629 setDoesNotCapture(F, 2);
1630 setOnlyReadsMemory(F, 2);
1631 break;
1632 case LibFunc::vsnprintf:
1633 if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
1634 !FTy->getParamType(2)->isPointerTy())
1635 return false;
1636 setDoesNotThrow(F);
1637 setDoesNotCapture(F, 1);
1638 setDoesNotCapture(F, 3);
1639 setOnlyReadsMemory(F, 3);
1640 break;
1641 case LibFunc::open:
1642 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1643 return false;
1644 // May throw; "open" is a valid pthread cancellation point.
1645 setDoesNotCapture(F, 1);
1646 setOnlyReadsMemory(F, 1);
1647 break;
1648 case LibFunc::opendir:
1649 if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy() ||
1650 !FTy->getParamType(0)->isPointerTy())
1651 return false;
1652 setDoesNotThrow(F);
1653 setDoesNotAlias(F, 0);
1654 setDoesNotCapture(F, 1);
1655 setOnlyReadsMemory(F, 1);
1656 break;
1657 case LibFunc::tmpfile:
1658 if (!FTy->getReturnType()->isPointerTy())
1659 return false;
1660 setDoesNotThrow(F);
1661 setDoesNotAlias(F, 0);
1662 break;
1663 case LibFunc::times:
1664 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1665 return false;
1666 setDoesNotThrow(F);
1667 setDoesNotCapture(F, 1);
1668 break;
1669 case LibFunc::htonl:
1670 case LibFunc::htons:
1671 case LibFunc::ntohl:
1672 case LibFunc::ntohs:
1673 setDoesNotThrow(F);
1674 setDoesNotAccessMemory(F);
1675 break;
1676 case LibFunc::lstat:
1677 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1678 !FTy->getParamType(1)->isPointerTy())
1679 return false;
1680 setDoesNotThrow(F);
1681 setDoesNotCapture(F, 1);
1682 setDoesNotCapture(F, 2);
1683 setOnlyReadsMemory(F, 1);
1684 break;
1685 case LibFunc::lchown:
1686 if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy())
1687 return false;
1688 setDoesNotThrow(F);
1689 setDoesNotCapture(F, 1);
1690 setOnlyReadsMemory(F, 1);
1691 break;
1692 case LibFunc::qsort:
1693 if (FTy->getNumParams() != 4 || !FTy->getParamType(3)->isPointerTy())
1694 return false;
1695 // May throw; places call through function pointer.
1696 setDoesNotCapture(F, 4);
1697 break;
1698 case LibFunc::dunder_strdup:
1699 case LibFunc::dunder_strndup:
1700 if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
1701 !FTy->getParamType(0)->isPointerTy())
1702 return false;
1703 setDoesNotThrow(F);
1704 setDoesNotAlias(F, 0);
1705 setDoesNotCapture(F, 1);
1706 setOnlyReadsMemory(F, 1);
1707 break;
1708 case LibFunc::dunder_strtok_r:
1709 if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
1710 return false;
1711 setDoesNotThrow(F);
1712 setDoesNotCapture(F, 2);
1713 setOnlyReadsMemory(F, 2);
1714 break;
1715 case LibFunc::under_IO_getc:
1716 if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
1717 return false;
1718 setDoesNotThrow(F);
1719 setDoesNotCapture(F, 1);
1720 break;
1721 case LibFunc::under_IO_putc:
1722 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1723 return false;
1724 setDoesNotThrow(F);
1725 setDoesNotCapture(F, 2);
1726 break;
1727 case LibFunc::dunder_isoc99_scanf:
1728 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
1729 return false;
1730 setDoesNotThrow(F);
1731 setDoesNotCapture(F, 1);
1732 setOnlyReadsMemory(F, 1);
1733 break;
1734 case LibFunc::stat64:
1735 case LibFunc::lstat64:
1736 case LibFunc::statvfs64:
1737 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() ||
1738 !FTy->getParamType(1)->isPointerTy())
1739 return false;
1740 setDoesNotThrow(F);
1741 setDoesNotCapture(F, 1);
1742 setDoesNotCapture(F, 2);
1743 setOnlyReadsMemory(F, 1);
1744 break;
1745 case LibFunc::dunder_isoc99_sscanf:
1746 if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() ||
1747 !FTy->getParamType(1)->isPointerTy())
1748 return false;
1749 setDoesNotThrow(F);
1750 setDoesNotCapture(F, 1);
1751 setDoesNotCapture(F, 2);
1752 setOnlyReadsMemory(F, 1);
1753 setOnlyReadsMemory(F, 2);
1754 break;
1755 case LibFunc::fopen64:
1756 if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
1757 !FTy->getParamType(0)->isPointerTy() ||
1758 !FTy->getParamType(1)->isPointerTy())
1759 return false;
1760 setDoesNotThrow(F);
1761 setDoesNotAlias(F, 0);
1762 setDoesNotCapture(F, 1);
1763 setDoesNotCapture(F, 2);
1764 setOnlyReadsMemory(F, 1);
1765 setOnlyReadsMemory(F, 2);
1766 break;
1767 case LibFunc::fseeko64:
1768 case LibFunc::ftello64:
1769 if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
1770 return false;
1771 setDoesNotThrow(F);
1772 setDoesNotCapture(F, 1);
1773 break;
1774 case LibFunc::tmpfile64:
1775 if (!FTy->getReturnType()->isPointerTy())
1776 return false;
1777 setDoesNotThrow(F);
1778 setDoesNotAlias(F, 0);
1779 break;
1780 case LibFunc::fstat64:
1781 case LibFunc::fstatvfs64:
1782 if (FTy->getNumParams() != 2 || !FTy->getParamType(1)->isPointerTy())
1783 return false;
1784 setDoesNotThrow(F);
1785 setDoesNotCapture(F, 2);
1786 break;
1787 case LibFunc::open64:
1788 if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy())
1789 return false;
1790 // May throw; "open" is a valid pthread cancellation point.
1791 setDoesNotCapture(F, 1);
1792 setOnlyReadsMemory(F, 1);
1793 break;
1794 case LibFunc::gettimeofday:
1795 if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
1796 !FTy->getParamType(1)->isPointerTy())
1797 return false;
1798 // Currently some platforms have the restrict keyword on the arguments to
1799 // gettimeofday. To be conservative, do not add noalias to gettimeofday's
1800 // arguments.
1801 setDoesNotThrow(F);
1802 setDoesNotCapture(F, 1);
1803 setDoesNotCapture(F, 2);
1804 break;
1805 default:
1806 // Didn't mark any attributes.
1807 return false; 951 return false;
1808 } 952
1809 953 // If all of the calls in F are identifiable and are to norecurse functions, F
1810 return true; 954 // is norecurse. This check also detects self-recursion as F is not currently
1811 } 955 // marked norecurse, so any called from F to F will not be marked norecurse.
1812 956 if (std::all_of(CGN->begin(), CGN->end(),
1813 /// Adds attributes to well-known standard library call declarations. 957 [](const CallGraphNode::CallRecord &CR) {
1814 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) { 958 Function *F = CR.second->getFunction();
1815 bool MadeChange = false; 959 return F && F->doesNotRecurse();
1816 960 }))
1817 // Check each function in turn annotating well-known library function 961 // Function calls a potentially recursive function.
1818 // declarations with attributes. 962 return setDoesNotRecurse(*F);
963
964 // Nothing else we can deduce usefully during the postorder traversal.
965 return false;
966 }
967
968 bool PostOrderFunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
969 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
970 bool Changed = false;
971
972 // We compute dedicated AA results for each function in the SCC as needed. We
973 // use a lambda referencing external objects so that they live long enough to
974 // be queried, but we re-use them each time.
975 Optional<BasicAAResult> BAR;
976 Optional<AAResults> AAR;
977 auto AARGetter = [&](Function &F) -> AAResults & {
978 BAR.emplace(createLegacyPMBasicAAResult(*this, F));
979 AAR.emplace(createLegacyPMAAResults(*this, F, *BAR));
980 return *AAR;
981 };
982
983 // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
984 // whether a given CallGraphNode is in this SCC. Also track whether there are
985 // any external or opt-none nodes that will prevent us from optimizing any
986 // part of the SCC.
987 SCCNodeSet SCCNodes;
988 bool ExternalNode = false;
1819 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 989 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
1820 Function *F = (*I)->getFunction(); 990 Function *F = (*I)->getFunction();
1821 991 if (!F || F->hasFnAttribute(Attribute::OptimizeNone)) {
1822 if (F && F->isDeclaration()) 992 // External node or function we're trying not to optimize - we both avoid
1823 MadeChange |= inferPrototypeAttributes(*F, *TLI); 993 // transform them and avoid leveraging information they provide.
1824 } 994 ExternalNode = true;
1825 995 continue;
1826 return MadeChange; 996 }
1827 } 997
1828 998 SCCNodes.insert(F);
1829 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 999 }
1830 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 1000
1831 1001 Changed |= addReadAttrs(SCCNodes, AARGetter);
1832 bool Changed = annotateLibraryCalls(SCC); 1002 Changed |= addArgumentAttrs(SCCNodes);
1833 Changed |= AddReadAttrs(SCC); 1003
1834 Changed |= AddArgumentAttrs(SCC); 1004 // If we have no external nodes participating in the SCC, we can deduce some
1835 Changed |= AddNoAliasAttrs(SCC); 1005 // more precise attributes as well.
1836 Changed |= AddNonNullAttrs(SCC); 1006 if (!ExternalNode) {
1007 Changed |= addNoAliasAttrs(SCCNodes);
1008 Changed |= addNonNullAttrs(SCCNodes, *TLI);
1009 }
1010
1011 Changed |= addNoRecurseAttrs(SCC);
1837 return Changed; 1012 return Changed;
1838 } 1013 }
1014
1015 namespace {
1016 /// A pass to do RPO deduction and propagation of function attributes.
1017 ///
1018 /// This pass provides a general RPO or "top down" propagation of
1019 /// function attributes. For a few (rare) cases, we can deduce significantly
1020 /// more about function attributes by working in RPO, so this pass
1021 /// provides the compliment to the post-order pass above where the majority of
1022 /// deduction is performed.
1023 // FIXME: Currently there is no RPO CGSCC pass structure to slide into and so
1024 // this is a boring module pass, but eventually it should be an RPO CGSCC pass
1025 // when such infrastructure is available.
1026 struct ReversePostOrderFunctionAttrs : public ModulePass {
1027 static char ID; // Pass identification, replacement for typeid
1028 ReversePostOrderFunctionAttrs() : ModulePass(ID) {
1029 initializeReversePostOrderFunctionAttrsPass(*PassRegistry::getPassRegistry());
1030 }
1031
1032 bool runOnModule(Module &M) override;
1033
1034 void getAnalysisUsage(AnalysisUsage &AU) const override {
1035 AU.setPreservesCFG();
1036 AU.addRequired<CallGraphWrapperPass>();
1037 }
1038 };
1039 }
1040
1041 char ReversePostOrderFunctionAttrs::ID = 0;
1042 INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrs, "rpo-functionattrs",
1043 "Deduce function attributes in RPO", false, false)
1044 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
1045 INITIALIZE_PASS_END(ReversePostOrderFunctionAttrs, "rpo-functionattrs",
1046 "Deduce function attributes in RPO", false, false)
1047
1048 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
1049 return new ReversePostOrderFunctionAttrs();
1050 }
1051
1052 static bool addNoRecurseAttrsTopDown(Function &F) {
1053 // We check the preconditions for the function prior to calling this to avoid
1054 // the cost of building up a reversible post-order list. We assert them here
1055 // to make sure none of the invariants this relies on were violated.
1056 assert(!F.isDeclaration() && "Cannot deduce norecurse without a definition!");
1057 assert(!F.doesNotRecurse() &&
1058 "This function has already been deduced as norecurs!");
1059 assert(F.hasInternalLinkage() &&
1060 "Can only do top-down deduction for internal linkage functions!");
1061
1062 // If F is internal and all of its uses are calls from a non-recursive
1063 // functions, then none of its calls could in fact recurse without going
1064 // through a function marked norecurse, and so we can mark this function too
1065 // as norecurse. Note that the uses must actually be calls -- otherwise
1066 // a pointer to this function could be returned from a norecurse function but
1067 // this function could be recursively (indirectly) called. Note that this
1068 // also detects if F is directly recursive as F is not yet marked as
1069 // a norecurse function.
1070 for (auto *U : F.users()) {
1071 auto *I = dyn_cast<Instruction>(U);
1072 if (!I)
1073 return false;
1074 CallSite CS(I);
1075 if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
1076 return false;
1077 }
1078 return setDoesNotRecurse(F);
1079 }
1080
1081 bool ReversePostOrderFunctionAttrs::runOnModule(Module &M) {
1082 // We only have a post-order SCC traversal (because SCCs are inherently
1083 // discovered in post-order), so we accumulate them in a vector and then walk
1084 // it in reverse. This is simpler than using the RPO iterator infrastructure
1085 // because we need to combine SCC detection and the PO walk of the call
1086 // graph. We can also cheat egregiously because we're primarily interested in
1087 // synthesizing norecurse and so we can only save the singular SCCs as SCCs
1088 // with multiple functions in them will clearly be recursive.
1089 auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1090 SmallVector<Function *, 16> Worklist;
1091 for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
1092 if (I->size() != 1)
1093 continue;
1094
1095 Function *F = I->front()->getFunction();
1096 if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
1097 F->hasInternalLinkage())
1098 Worklist.push_back(F);
1099 }
1100
1101 bool Changed = false;
1102 for (auto *F : reverse(Worklist))
1103 Changed |= addNoRecurseAttrsTopDown(*F);
1104
1105 return Changed;
1106 }