/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/StackSafetyAnalysis.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- StackSafetyAnalysis.cpp - Stack memory safety analysis -------------===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | //===----------------------------------------------------------------------===// |
10 | | |
11 | | #include "llvm/Analysis/StackSafetyAnalysis.h" |
12 | | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
13 | | #include "llvm/IR/CallSite.h" |
14 | | #include "llvm/IR/InstIterator.h" |
15 | | #include "llvm/IR/IntrinsicInst.h" |
16 | | #include "llvm/Support/raw_ostream.h" |
17 | | |
18 | | using namespace llvm; |
19 | | |
20 | | #define DEBUG_TYPE "stack-safety" |
21 | | |
22 | | static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations", |
23 | | cl::init(20), cl::Hidden); |
24 | | |
25 | | namespace { |
26 | | |
27 | | /// Rewrite an SCEV expression for a memory access address to an expression that |
28 | | /// represents offset from the given alloca. |
29 | | class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> { |
30 | | const Value *AllocaPtr; |
31 | | |
32 | | public: |
33 | | AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr) |
34 | 400 | : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {} |
35 | | |
36 | 688 | const SCEV *visit(const SCEV *Expr) { |
37 | 688 | // Only re-write the expression if the alloca is used in an addition |
38 | 688 | // expression (it can be used in other types of expressions if it's cast to |
39 | 688 | // an int and passed as an argument.) |
40 | 688 | if (!isa<SCEVAddRecExpr>(Expr) && !isa<SCEVAddExpr>(Expr)680 && |
41 | 688 | !isa<SCEVUnknown>(Expr)544 ) |
42 | 132 | return Expr; |
43 | 556 | return SCEVRewriteVisitor<AllocaOffsetRewriter>::visit(Expr); |
44 | 556 | } |
45 | | |
46 | 412 | const SCEV *visitUnknown(const SCEVUnknown *Expr) { |
47 | 412 | // FIXME: look through one or several levels of definitions? |
48 | 412 | // This can be inttoptr(AllocaPtr) and SCEV would not unwrap |
49 | 412 | // it for us. |
50 | 412 | if (Expr->getValue() == AllocaPtr) |
51 | 364 | return SE.getZero(Expr->getType()); |
52 | 48 | return Expr; |
53 | 48 | } |
54 | | }; |
55 | | |
56 | | /// Describes use of address in as a function call argument. |
57 | | struct PassAsArgInfo { |
58 | | /// Function being called. |
59 | | const GlobalValue *Callee = nullptr; |
60 | | /// Index of argument which pass address. |
61 | | size_t ParamNo = 0; |
62 | | // Offset range of address from base address (alloca or calling function |
63 | | // argument). |
64 | | // Range should never set to empty-set, that is an invalid access range |
65 | | // that can cause empty-set to be propagated with ConstantRange::add |
66 | | ConstantRange Offset; |
67 | | PassAsArgInfo(const GlobalValue *Callee, size_t ParamNo, ConstantRange Offset) |
68 | 196 | : Callee(Callee), ParamNo(ParamNo), Offset(Offset) {} |
69 | | |
70 | 196 | StringRef getName() const { return Callee->getName(); } |
71 | | }; |
72 | | |
73 | 196 | raw_ostream &operator<<(raw_ostream &OS, const PassAsArgInfo &P) { |
74 | 196 | return OS << "@" << P.getName() << "(arg" << P.ParamNo << ", " << P.Offset |
75 | 196 | << ")"; |
76 | 196 | } |
77 | | |
78 | | /// Describe uses of address (alloca or parameter) inside of the function. |
79 | | struct UseInfo { |
80 | | // Access range if the address (alloca or parameters). |
81 | | // It is allowed to be empty-set when there are no known accesses. |
82 | | ConstantRange Range; |
83 | | |
84 | | // List of calls which pass address as an argument. |
85 | | SmallVector<PassAsArgInfo, 4> Calls; |
86 | | |
87 | 416 | explicit UseInfo(unsigned PointerSize) : Range{PointerSize, false} {} |
88 | | |
89 | 264 | void updateRange(ConstantRange R) { Range = Range.unionWith(R); } |
90 | | }; |
91 | | |
92 | 416 | raw_ostream &operator<<(raw_ostream &OS, const UseInfo &U) { |
93 | 416 | OS << U.Range; |
94 | 416 | for (auto &Call : U.Calls) |
95 | 196 | OS << ", " << Call; |
96 | 416 | return OS; |
97 | 416 | } |
98 | | |
99 | | struct AllocaInfo { |
100 | | const AllocaInst *AI = nullptr; |
101 | | uint64_t Size = 0; |
102 | | UseInfo Use; |
103 | | |
104 | | AllocaInfo(unsigned PointerSize, const AllocaInst *AI, uint64_t Size) |
105 | 268 | : AI(AI), Size(Size), Use(PointerSize) {} |
106 | | |
107 | 268 | StringRef getName() const { return AI->getName(); } |
108 | | }; |
109 | | |
110 | 268 | raw_ostream &operator<<(raw_ostream &OS, const AllocaInfo &A) { |
111 | 268 | return OS << A.getName() << "[" << A.Size << "]: " << A.Use; |
112 | 268 | } |
113 | | |
114 | | struct ParamInfo { |
115 | | const Argument *Arg = nullptr; |
116 | | UseInfo Use; |
117 | | |
118 | | explicit ParamInfo(unsigned PointerSize, const Argument *Arg) |
119 | 148 | : Arg(Arg), Use(PointerSize) {} |
120 | | |
121 | 148 | StringRef getName() const { return Arg ? Arg->getName()136 : "<N/A>"12 ; } |
122 | | }; |
123 | | |
124 | 148 | raw_ostream &operator<<(raw_ostream &OS, const ParamInfo &P) { |
125 | 148 | return OS << P.getName() << "[]: " << P.Use; |
126 | 148 | } |
127 | | |
128 | | /// Calculate the allocation size of a given alloca. Returns 0 if the |
129 | | /// size can not be statically determined. |
130 | 268 | uint64_t getStaticAllocaAllocationSize(const AllocaInst *AI) { |
131 | 268 | const DataLayout &DL = AI->getModule()->getDataLayout(); |
132 | 268 | uint64_t Size = DL.getTypeAllocSize(AI->getAllocatedType()); |
133 | 268 | if (AI->isArrayAllocation()) { |
134 | 28 | auto C = dyn_cast<ConstantInt>(AI->getArraySize()); |
135 | 28 | if (!C) |
136 | 12 | return 0; |
137 | 16 | Size *= C->getZExtValue(); |
138 | 16 | } |
139 | 268 | return Size256 ; |
140 | 268 | } |
141 | | |
142 | | } // end anonymous namespace |
143 | | |
144 | | /// Describes uses of allocas and parameters inside of a single function. |
145 | | struct StackSafetyInfo::FunctionInfo { |
146 | | // May be a Function or a GlobalAlias |
147 | | const GlobalValue *GV = nullptr; |
148 | | // Informations about allocas uses. |
149 | | SmallVector<AllocaInfo, 4> Allocas; |
150 | | // Informations about parameters uses. |
151 | | SmallVector<ParamInfo, 4> Params; |
152 | | // TODO: describe return value as depending on one or more of its arguments. |
153 | | |
154 | | // StackSafetyDataFlowAnalysis counter stored here for faster access. |
155 | | int UpdateCount = 0; |
156 | | |
157 | 156 | FunctionInfo(const StackSafetyInfo &SSI) : FunctionInfo(*SSI.Info) {} |
158 | | |
159 | 312 | explicit FunctionInfo(const Function *F) : GV(F){}; |
160 | | // Creates FunctionInfo that forwards all the parameters to the aliasee. |
161 | | explicit FunctionInfo(const GlobalAlias *A); |
162 | | |
163 | 492 | FunctionInfo(FunctionInfo &&) = default; |
164 | | |
165 | 888 | bool IsDSOLocal() const { return GV->isDSOLocal(); }; |
166 | | |
167 | 882 | bool IsInterposable() const { return GV->isInterposable(); }; |
168 | | |
169 | 324 | StringRef getName() const { return GV->getName(); } |
170 | | |
171 | 324 | void print(raw_ostream &O) const { |
172 | 324 | // TODO: Consider different printout format after |
173 | 324 | // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then. |
174 | 324 | O << " @" << getName() << (IsDSOLocal() ? ""78 : " dso_preemptable"246 ) |
175 | 324 | << (IsInterposable() ? " interposable"6 : ""318 ) << "\n"; |
176 | 324 | O << " args uses:\n"; |
177 | 324 | for (auto &P : Params) |
178 | 148 | O << " " << P << "\n"; |
179 | 324 | O << " allocas uses:\n"; |
180 | 324 | for (auto &AS : Allocas) |
181 | 268 | O << " " << AS << "\n"; |
182 | 324 | } |
183 | | |
184 | | private: |
185 | 156 | FunctionInfo(const FunctionInfo &) = default; |
186 | | }; |
187 | | |
188 | 12 | StackSafetyInfo::FunctionInfo::FunctionInfo(const GlobalAlias *A) : GV(A) { |
189 | 12 | unsigned PointerSize = A->getParent()->getDataLayout().getPointerSizeInBits(); |
190 | 12 | const GlobalObject *Aliasee = A->getBaseObject(); |
191 | 12 | const FunctionType *Type = cast<FunctionType>(Aliasee->getValueType()); |
192 | 12 | // 'Forward' all parameters to this alias to the aliasee |
193 | 24 | for (unsigned ArgNo = 0; ArgNo < Type->getNumParams(); ArgNo++12 ) { |
194 | 12 | Params.emplace_back(PointerSize, nullptr); |
195 | 12 | UseInfo &US = Params.back().Use; |
196 | 12 | US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0))); |
197 | 12 | } |
198 | 12 | } |
199 | | |
200 | | namespace { |
201 | | |
202 | | class StackSafetyLocalAnalysis { |
203 | | const Function &F; |
204 | | const DataLayout &DL; |
205 | | ScalarEvolution &SE; |
206 | | unsigned PointerSize = 0; |
207 | | |
208 | | const ConstantRange UnknownRange; |
209 | | |
210 | | ConstantRange offsetFromAlloca(Value *Addr, const Value *AllocaPtr); |
211 | | ConstantRange getAccessRange(Value *Addr, const Value *AllocaPtr, |
212 | | uint64_t AccessSize); |
213 | | ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U, |
214 | | const Value *AllocaPtr); |
215 | | |
216 | | bool analyzeAllUses(const Value *Ptr, UseInfo &AS); |
217 | | |
218 | 228 | ConstantRange getRange(uint64_t Lower, uint64_t Upper) const { |
219 | 228 | return ConstantRange(APInt(PointerSize, Lower), APInt(PointerSize, Upper)); |
220 | 228 | } |
221 | | |
222 | | public: |
223 | | StackSafetyLocalAnalysis(const Function &F, ScalarEvolution &SE) |
224 | | : F(F), DL(F.getParent()->getDataLayout()), SE(SE), |
225 | | PointerSize(DL.getPointerSizeInBits()), |
226 | 312 | UnknownRange(PointerSize, true) {} |
227 | | |
228 | | // Run the transformation on the associated function. |
229 | | StackSafetyInfo run(); |
230 | | }; |
231 | | |
232 | | ConstantRange |
233 | | StackSafetyLocalAnalysis::offsetFromAlloca(Value *Addr, |
234 | 184 | const Value *AllocaPtr) { |
235 | 184 | if (!SE.isSCEVable(Addr->getType())) |
236 | 0 | return UnknownRange; |
237 | 184 | |
238 | 184 | AllocaOffsetRewriter Rewriter(SE, AllocaPtr); |
239 | 184 | const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr)); |
240 | 184 | ConstantRange Offset = SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize); |
241 | 184 | assert(!Offset.isEmptySet()); |
242 | 184 | return Offset; |
243 | 184 | } |
244 | | |
245 | | ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, |
246 | | const Value *AllocaPtr, |
247 | 216 | uint64_t AccessSize) { |
248 | 216 | if (!SE.isSCEVable(Addr->getType())) |
249 | 0 | return UnknownRange; |
250 | 216 | |
251 | 216 | AllocaOffsetRewriter Rewriter(SE, AllocaPtr); |
252 | 216 | const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr)); |
253 | 216 | |
254 | 216 | ConstantRange AccessStartRange = |
255 | 216 | SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize); |
256 | 216 | ConstantRange SizeRange = getRange(0, AccessSize); |
257 | 216 | ConstantRange AccessRange = AccessStartRange.add(SizeRange); |
258 | 216 | assert(!AccessRange.isEmptySet()); |
259 | 216 | return AccessRange; |
260 | 216 | } |
261 | | |
262 | | ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange( |
263 | 100 | const MemIntrinsic *MI, const Use &U, const Value *AllocaPtr) { |
264 | 100 | if (auto MTI = dyn_cast<MemTransferInst>(MI)) { |
265 | 64 | if (MTI->getRawSource() != U && MTI->getRawDest() != U32 ) |
266 | 0 | return getRange(0, 1); |
267 | 36 | } else { |
268 | 36 | if (MI->getRawDest() != U) |
269 | 12 | return getRange(0, 1); |
270 | 88 | } |
271 | 88 | const auto *Len = dyn_cast<ConstantInt>(MI->getLength()); |
272 | 88 | // Non-constant size => unsafe. FIXME: try SCEV getRange. |
273 | 88 | if (!Len) |
274 | 12 | return UnknownRange; |
275 | 76 | ConstantRange AccessRange = getAccessRange(U, AllocaPtr, Len->getZExtValue()); |
276 | 76 | return AccessRange; |
277 | 76 | } |
278 | | |
279 | | /// The function analyzes all local uses of Ptr (alloca or argument) and |
280 | | /// calculates local access range and all function calls where it was used. |
281 | 404 | bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) { |
282 | 404 | SmallPtrSet<const Value *, 16> Visited; |
283 | 404 | SmallVector<const Value *, 8> WorkList; |
284 | 404 | WorkList.push_back(Ptr); |
285 | 404 | |
286 | 404 | // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc. |
287 | 1.29k | while (!WorkList.empty()) { |
288 | 912 | const Value *V = WorkList.pop_back_val(); |
289 | 976 | for (const Use &UI : V->uses()) { |
290 | 976 | auto I = cast<const Instruction>(UI.getUser()); |
291 | 976 | assert(V == UI.get()); |
292 | 976 | |
293 | 976 | switch (I->getOpcode()) { |
294 | 976 | case Instruction::Load: { |
295 | 32 | US.updateRange( |
296 | 32 | getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType()))); |
297 | 32 | break; |
298 | 976 | } |
299 | 976 | |
300 | 976 | case Instruction::VAArg: |
301 | 0 | // "va-arg" from a pointer is safe. |
302 | 0 | break; |
303 | 976 | case Instruction::Store: { |
304 | 112 | if (V == I->getOperand(0)) { |
305 | 4 | // Stored the pointer - conservatively assume it may be unsafe. |
306 | 4 | US.updateRange(UnknownRange); |
307 | 4 | return false; |
308 | 4 | } |
309 | 108 | US.updateRange(getAccessRange( |
310 | 108 | UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType()))); |
311 | 108 | break; |
312 | 108 | } |
313 | 108 | |
314 | 108 | case Instruction::Ret: |
315 | 12 | // Information leak. |
316 | 12 | // FIXME: Process parameters correctly. This is a leak only if we return |
317 | 12 | // alloca. |
318 | 12 | US.updateRange(UnknownRange); |
319 | 12 | return false; |
320 | 108 | |
321 | 292 | case Instruction::Call: |
322 | 292 | case Instruction::Invoke: { |
323 | 292 | ImmutableCallSite CS(I); |
324 | 292 | |
325 | 292 | if (I->isLifetimeStartOrEnd()) |
326 | 0 | break; |
327 | 292 | |
328 | 292 | if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { |
329 | 100 | US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr)); |
330 | 100 | break; |
331 | 100 | } |
332 | 192 | |
333 | 192 | // FIXME: consult devirt? |
334 | 192 | // Do not follow aliases, otherwise we could inadvertently follow |
335 | 192 | // dso_preemptable aliases or aliases with interposable linkage. |
336 | 192 | const GlobalValue *Callee = dyn_cast<GlobalValue>( |
337 | 192 | CS.getCalledValue()->stripPointerCastsNoFollowAliases()); |
338 | 192 | if (!Callee) { |
339 | 8 | US.updateRange(UnknownRange); |
340 | 8 | return false; |
341 | 8 | } |
342 | 184 | |
343 | 184 | assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee)); |
344 | 184 | |
345 | 184 | ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); |
346 | 464 | for (ImmutableCallSite::arg_iterator A = B; A != E; ++A280 ) { |
347 | 280 | if (A->get() == V) { |
348 | 184 | ConstantRange Offset = offsetFromAlloca(UI, Ptr); |
349 | 184 | US.Calls.emplace_back(Callee, A - B, Offset); |
350 | 184 | } |
351 | 280 | } |
352 | 184 | |
353 | 184 | break; |
354 | 184 | } |
355 | 184 | |
356 | 528 | default: |
357 | 528 | if (Visited.insert(I).second) |
358 | 508 | WorkList.push_back(cast<const Instruction>(I)); |
359 | 976 | } |
360 | 976 | } |
361 | 912 | } |
362 | 404 | |
363 | 404 | return true380 ; |
364 | 404 | } |
365 | | |
366 | 312 | StackSafetyInfo StackSafetyLocalAnalysis::run() { |
367 | 312 | StackSafetyInfo::FunctionInfo Info(&F); |
368 | 312 | assert(!F.isDeclaration() && |
369 | 312 | "Can't run StackSafety on a function declaration"); |
370 | 312 | |
371 | 312 | LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n"); |
372 | 312 | |
373 | 1.44k | for (auto &I : instructions(F)) { |
374 | 1.44k | if (auto AI = dyn_cast<AllocaInst>(&I)) { |
375 | 268 | Info.Allocas.emplace_back(PointerSize, AI, |
376 | 268 | getStaticAllocaAllocationSize(AI)); |
377 | 268 | AllocaInfo &AS = Info.Allocas.back(); |
378 | 268 | analyzeAllUses(AI, AS.Use); |
379 | 268 | } |
380 | 1.44k | } |
381 | 312 | |
382 | 312 | for (const Argument &A : make_range(F.arg_begin(), F.arg_end())) { |
383 | 136 | Info.Params.emplace_back(PointerSize, &A); |
384 | 136 | ParamInfo &PS = Info.Params.back(); |
385 | 136 | analyzeAllUses(&A, PS.Use); |
386 | 136 | } |
387 | 312 | |
388 | 312 | LLVM_DEBUG(dbgs() << "[StackSafety] done\n"); |
389 | 312 | LLVM_DEBUG(Info.print(dbgs())); |
390 | 312 | return StackSafetyInfo(std::move(Info)); |
391 | 312 | } |
392 | | |
393 | | class StackSafetyDataFlowAnalysis { |
394 | | using FunctionMap = |
395 | | std::map<const GlobalValue *, StackSafetyInfo::FunctionInfo>; |
396 | | |
397 | | FunctionMap Functions; |
398 | | // Callee-to-Caller multimap. |
399 | | DenseMap<const GlobalValue *, SmallVector<const GlobalValue *, 4>> Callers; |
400 | | SetVector<const GlobalValue *> WorkList; |
401 | | |
402 | | unsigned PointerSize = 0; |
403 | | const ConstantRange UnknownRange; |
404 | | |
405 | | ConstantRange getArgumentAccessRange(const GlobalValue *Callee, |
406 | | unsigned ParamNo) const; |
407 | | bool updateOneUse(UseInfo &US, bool UpdateToFullSet); |
408 | | void updateOneNode(const GlobalValue *Callee, |
409 | | StackSafetyInfo::FunctionInfo &FS); |
410 | 198 | void updateOneNode(const GlobalValue *Callee) { |
411 | 198 | updateOneNode(Callee, Functions.find(Callee)->second); |
412 | 198 | } |
413 | 10 | void updateAllNodes() { |
414 | 10 | for (auto &F : Functions) |
415 | 168 | updateOneNode(F.first, F.second); |
416 | 10 | } |
417 | | void runDataFlow(); |
418 | | #ifndef NDEBUG |
419 | | void verifyFixedPoint(); |
420 | | #endif |
421 | | |
422 | | public: |
423 | | StackSafetyDataFlowAnalysis( |
424 | | Module &M, std::function<const StackSafetyInfo &(Function &)> FI); |
425 | | StackSafetyGlobalInfo run(); |
426 | | }; |
427 | | |
428 | | StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis( |
429 | | Module &M, std::function<const StackSafetyInfo &(Function &)> FI) |
430 | | : PointerSize(M.getDataLayout().getPointerSizeInBits()), |
431 | 10 | UnknownRange(PointerSize, true) { |
432 | 10 | // Without ThinLTO, run the local analysis for every function in the TU and |
433 | 10 | // then run the DFA. |
434 | 10 | for (auto &F : M.functions()) |
435 | 174 | if (!F.isDeclaration()) |
436 | 156 | Functions.emplace(&F, FI(F)); |
437 | 10 | for (auto &A : M.aliases()) |
438 | 12 | if (isa<Function>(A.getBaseObject())) |
439 | 12 | Functions.emplace(&A, StackSafetyInfo::FunctionInfo(&A)); |
440 | 10 | } |
441 | | |
442 | | ConstantRange |
443 | | StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee, |
444 | 570 | unsigned ParamNo) const { |
445 | 570 | auto IT = Functions.find(Callee); |
446 | 570 | // Unknown callee (outside of LTO domain or an indirect call). |
447 | 570 | if (IT == Functions.end()) |
448 | 6 | return UnknownRange; |
449 | 564 | const StackSafetyInfo::FunctionInfo &FS = IT->second; |
450 | 564 | // The definition of this symbol may not be the definition in this linkage |
451 | 564 | // unit. |
452 | 564 | if (!FS.IsDSOLocal() || FS.IsInterposable()558 ) |
453 | 12 | return UnknownRange; |
454 | 552 | if (ParamNo >= FS.Params.size()) // possibly vararg |
455 | 0 | return UnknownRange; |
456 | 552 | return FS.Params[ParamNo].Use.Range; |
457 | 552 | } |
458 | | |
459 | | bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US, |
460 | 680 | bool UpdateToFullSet) { |
461 | 680 | bool Changed = false; |
462 | 680 | for (auto &CS : US.Calls) { |
463 | 570 | assert(!CS.Offset.isEmptySet() && |
464 | 570 | "Param range can't be empty-set, invalid offset range"); |
465 | 570 | |
466 | 570 | ConstantRange CalleeRange = getArgumentAccessRange(CS.Callee, CS.ParamNo); |
467 | 570 | CalleeRange = CalleeRange.add(CS.Offset); |
468 | 570 | if (!US.Range.contains(CalleeRange)) { |
469 | 260 | Changed = true; |
470 | 260 | if (UpdateToFullSet) |
471 | 8 | US.Range = UnknownRange; |
472 | 252 | else |
473 | 252 | US.Range = US.Range.unionWith(CalleeRange); |
474 | 260 | } |
475 | 570 | } |
476 | 680 | return Changed; |
477 | 680 | } |
478 | | |
479 | | void StackSafetyDataFlowAnalysis::updateOneNode( |
480 | 366 | const GlobalValue *Callee, StackSafetyInfo::FunctionInfo &FS) { |
481 | 366 | bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations; |
482 | 366 | bool Changed = false; |
483 | 366 | for (auto &AS : FS.Allocas) |
484 | 244 | Changed |= updateOneUse(AS.Use, UpdateToFullSet); |
485 | 366 | for (auto &PS : FS.Params) |
486 | 436 | Changed |= updateOneUse(PS.Use, UpdateToFullSet); |
487 | 366 | |
488 | 366 | if (Changed) { |
489 | 250 | LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount |
490 | 250 | << (UpdateToFullSet ? ", full-set" : "") << "] " |
491 | 250 | << FS.getName() << "\n"); |
492 | 250 | // Callers of this function may need updating. |
493 | 250 | for (auto &CallerID : Callers[Callee]) |
494 | 202 | WorkList.insert(CallerID); |
495 | 250 | |
496 | 250 | ++FS.UpdateCount; |
497 | 250 | } |
498 | 366 | } |
499 | | |
500 | 10 | void StackSafetyDataFlowAnalysis::runDataFlow() { |
501 | 10 | Callers.clear(); |
502 | 10 | WorkList.clear(); |
503 | 10 | |
504 | 10 | SmallVector<const GlobalValue *, 16> Callees; |
505 | 168 | for (auto &F : Functions) { |
506 | 168 | Callees.clear(); |
507 | 168 | StackSafetyInfo::FunctionInfo &FS = F.second; |
508 | 168 | for (auto &AS : FS.Allocas) |
509 | 134 | for (auto &CS : AS.Use.Calls) |
510 | 68 | Callees.push_back(CS.Callee); |
511 | 168 | for (auto &PS : FS.Params) |
512 | 80 | for (auto &CS : PS.Use.Calls) |
513 | 36 | Callees.push_back(CS.Callee); |
514 | 168 | |
515 | 168 | llvm::sort(Callees); |
516 | 168 | Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end()); |
517 | 168 | |
518 | 168 | for (auto &Callee : Callees) |
519 | 84 | Callers[Callee].push_back(F.first); |
520 | 168 | } |
521 | 10 | |
522 | 10 | updateAllNodes(); |
523 | 10 | |
524 | 208 | while (!WorkList.empty()) { |
525 | 198 | const GlobalValue *Callee = WorkList.back(); |
526 | 198 | WorkList.pop_back(); |
527 | 198 | updateOneNode(Callee); |
528 | 198 | } |
529 | 10 | } |
530 | | |
531 | | #ifndef NDEBUG |
532 | | void StackSafetyDataFlowAnalysis::verifyFixedPoint() { |
533 | | WorkList.clear(); |
534 | | updateAllNodes(); |
535 | | assert(WorkList.empty()); |
536 | | } |
537 | | #endif |
538 | | |
539 | 10 | StackSafetyGlobalInfo StackSafetyDataFlowAnalysis::run() { |
540 | 10 | runDataFlow(); |
541 | 10 | LLVM_DEBUG(verifyFixedPoint()); |
542 | 10 | |
543 | 10 | StackSafetyGlobalInfo SSI; |
544 | 10 | for (auto &F : Functions) |
545 | 168 | SSI.emplace(F.first, std::move(F.second)); |
546 | 10 | return SSI; |
547 | 10 | } |
548 | | |
549 | 10 | void print(const StackSafetyGlobalInfo &SSI, raw_ostream &O, const Module &M) { |
550 | 10 | size_t Count = 0; |
551 | 10 | for (auto &F : M.functions()) |
552 | 174 | if (!F.isDeclaration()) { |
553 | 156 | SSI.find(&F)->second.print(O); |
554 | 156 | O << "\n"; |
555 | 156 | ++Count; |
556 | 156 | } |
557 | 12 | for (auto &A : M.aliases()) { |
558 | 12 | SSI.find(&A)->second.print(O); |
559 | 12 | O << "\n"; |
560 | 12 | ++Count; |
561 | 12 | } |
562 | 10 | assert(Count == SSI.size() && "Unexpected functions in the result"); |
563 | 10 | } |
564 | | |
565 | | } // end anonymous namespace |
566 | | |
567 | 15 | StackSafetyInfo::StackSafetyInfo() = default; |
568 | 312 | StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default; |
569 | 156 | StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default; |
570 | | |
571 | | StackSafetyInfo::StackSafetyInfo(FunctionInfo &&Info) |
572 | 480 | : Info(new FunctionInfo(std::move(Info))) {} |
573 | | |
574 | 807 | StackSafetyInfo::~StackSafetyInfo() = default; |
575 | | |
576 | 324 | void StackSafetyInfo::print(raw_ostream &O) const { Info->print(O); } |
577 | | |
578 | | AnalysisKey StackSafetyAnalysis::Key; |
579 | | |
580 | | StackSafetyInfo StackSafetyAnalysis::run(Function &F, |
581 | 156 | FunctionAnalysisManager &AM) { |
582 | 156 | StackSafetyLocalAnalysis SSLA(F, AM.getResult<ScalarEvolutionAnalysis>(F)); |
583 | 156 | return SSLA.run(); |
584 | 156 | } |
585 | | |
586 | | PreservedAnalyses StackSafetyPrinterPass::run(Function &F, |
587 | 78 | FunctionAnalysisManager &AM) { |
588 | 78 | OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n"; |
589 | 78 | AM.getResult<StackSafetyAnalysis>(F).print(OS); |
590 | 78 | return PreservedAnalyses::all(); |
591 | 78 | } |
592 | | |
593 | | char StackSafetyInfoWrapperPass::ID = 0; |
594 | | |
595 | 15 | StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) { |
596 | 15 | initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry()); |
597 | 15 | } |
598 | | |
599 | 10 | void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
600 | 10 | AU.addRequired<ScalarEvolutionWrapperPass>(); |
601 | 10 | AU.setPreservesAll(); |
602 | 10 | } |
603 | | |
604 | 78 | void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const { |
605 | 78 | SSI.print(O); |
606 | 78 | } |
607 | | |
608 | 156 | bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) { |
609 | 156 | StackSafetyLocalAnalysis SSLA( |
610 | 156 | F, getAnalysis<ScalarEvolutionWrapperPass>().getSE()); |
611 | 156 | SSI = StackSafetyInfo(SSLA.run()); |
612 | 156 | return false; |
613 | 156 | } |
614 | | |
615 | | AnalysisKey StackSafetyGlobalAnalysis::Key; |
616 | | |
617 | | StackSafetyGlobalInfo |
618 | 5 | StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) { |
619 | 5 | FunctionAnalysisManager &FAM = |
620 | 5 | AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); |
621 | 5 | |
622 | 5 | StackSafetyDataFlowAnalysis SSDFA( |
623 | 78 | M, [&FAM](Function &F) -> const StackSafetyInfo & { |
624 | 78 | return FAM.getResult<StackSafetyAnalysis>(F); |
625 | 78 | }); |
626 | 5 | return SSDFA.run(); |
627 | 5 | } |
628 | | |
629 | | PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M, |
630 | 5 | ModuleAnalysisManager &AM) { |
631 | 5 | OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n"; |
632 | 5 | print(AM.getResult<StackSafetyGlobalAnalysis>(M), OS, M); |
633 | 5 | return PreservedAnalyses::all(); |
634 | 5 | } |
635 | | |
636 | | char StackSafetyGlobalInfoWrapperPass::ID = 0; |
637 | | |
638 | | StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass() |
639 | 5 | : ModulePass(ID) { |
640 | 5 | initializeStackSafetyGlobalInfoWrapperPassPass( |
641 | 5 | *PassRegistry::getPassRegistry()); |
642 | 5 | } |
643 | | |
644 | | void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O, |
645 | 5 | const Module *M) const { |
646 | 5 | ::print(SSI, O, *M); |
647 | 5 | } |
648 | | |
649 | | void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage( |
650 | 5 | AnalysisUsage &AU) const { |
651 | 5 | AU.addRequired<StackSafetyInfoWrapperPass>(); |
652 | 5 | } |
653 | | |
654 | 5 | bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) { |
655 | 5 | StackSafetyDataFlowAnalysis SSDFA( |
656 | 78 | M, [this](Function &F) -> const StackSafetyInfo & { |
657 | 78 | return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult(); |
658 | 78 | }); |
659 | 5 | SSI = SSDFA.run(); |
660 | 5 | return false; |
661 | 5 | } |
662 | | |
663 | | static const char LocalPassArg[] = "stack-safety-local"; |
664 | | static const char LocalPassName[] = "Stack Safety Local Analysis"; |
665 | 11.0k | INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName, |
666 | 11.0k | false, true) |
667 | 11.0k | INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) |
668 | 11.0k | INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName, |
669 | | false, true) |
670 | | |
671 | | static const char GlobalPassName[] = "Stack Safety Analysis"; |
672 | 11.0k | INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE, |
673 | 11.0k | GlobalPassName, false, false) |
674 | 11.0k | INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass) |
675 | 11.0k | INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE, |
676 | | GlobalPassName, false, false) |