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