Bug Summary

File:llvm/lib/Analysis/StackSafetyAnalysis.cpp
Warning:line 699, column 7
Method called on moved-from object 'Calls' of type 'std::map'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name StackSafetyAnalysis.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-12/lib/clang/12.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/build-llvm/lib/Analysis -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-09-28-092409-31635-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp
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/ADT/APInt.h"
13#include "llvm/ADT/SmallPtrSet.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/ADT/Statistic.h"
16#include "llvm/Analysis/ModuleSummaryAnalysis.h"
17#include "llvm/Analysis/ScalarEvolutionExpressions.h"
18#include "llvm/Analysis/StackLifetime.h"
19#include "llvm/IR/ConstantRange.h"
20#include "llvm/IR/DerivedTypes.h"
21#include "llvm/IR/GlobalValue.h"
22#include "llvm/IR/InstIterator.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/ModuleSummaryIndex.h"
26#include "llvm/InitializePasses.h"
27#include "llvm/Support/Casting.h"
28#include "llvm/Support/CommandLine.h"
29#include "llvm/Support/FormatVariadic.h"
30#include "llvm/Support/raw_ostream.h"
31#include <algorithm>
32#include <memory>
33
34using namespace llvm;
35
36#define DEBUG_TYPE"stack-safety" "stack-safety"
37
38STATISTIC(NumAllocaStackSafe, "Number of safe allocas")static llvm::Statistic NumAllocaStackSafe = {"stack-safety", "NumAllocaStackSafe"
, "Number of safe allocas"};
39STATISTIC(NumAllocaTotal, "Number of total allocas")static llvm::Statistic NumAllocaTotal = {"stack-safety", "NumAllocaTotal"
, "Number of total allocas"};
40
41STATISTIC(NumCombinedCalleeLookupTotal,static llvm::Statistic NumCombinedCalleeLookupTotal = {"stack-safety"
, "NumCombinedCalleeLookupTotal", "Number of total callee lookups on combined index."
}
42 "Number of total callee lookups on combined index.")static llvm::Statistic NumCombinedCalleeLookupTotal = {"stack-safety"
, "NumCombinedCalleeLookupTotal", "Number of total callee lookups on combined index."
};
43STATISTIC(NumCombinedCalleeLookupFailed,static llvm::Statistic NumCombinedCalleeLookupFailed = {"stack-safety"
, "NumCombinedCalleeLookupFailed", "Number of failed callee lookups on combined index."
}
44 "Number of failed callee lookups on combined index.")static llvm::Statistic NumCombinedCalleeLookupFailed = {"stack-safety"
, "NumCombinedCalleeLookupFailed", "Number of failed callee lookups on combined index."
};
45STATISTIC(NumModuleCalleeLookupTotal,static llvm::Statistic NumModuleCalleeLookupTotal = {"stack-safety"
, "NumModuleCalleeLookupTotal", "Number of total callee lookups on module index."
}
46 "Number of total callee lookups on module index.")static llvm::Statistic NumModuleCalleeLookupTotal = {"stack-safety"
, "NumModuleCalleeLookupTotal", "Number of total callee lookups on module index."
};
47STATISTIC(NumModuleCalleeLookupFailed,static llvm::Statistic NumModuleCalleeLookupFailed = {"stack-safety"
, "NumModuleCalleeLookupFailed", "Number of failed callee lookups on module index."
}
48 "Number of failed callee lookups on module index.")static llvm::Statistic NumModuleCalleeLookupFailed = {"stack-safety"
, "NumModuleCalleeLookupFailed", "Number of failed callee lookups on module index."
};
49STATISTIC(NumCombinedParamAccessesBefore,static llvm::Statistic NumCombinedParamAccessesBefore = {"stack-safety"
, "NumCombinedParamAccessesBefore", "Number of total param accesses before generateParamAccessSummary."
}
50 "Number of total param accesses before generateParamAccessSummary.")static llvm::Statistic NumCombinedParamAccessesBefore = {"stack-safety"
, "NumCombinedParamAccessesBefore", "Number of total param accesses before generateParamAccessSummary."
};
51STATISTIC(NumCombinedParamAccessesAfter,static llvm::Statistic NumCombinedParamAccessesAfter = {"stack-safety"
, "NumCombinedParamAccessesAfter", "Number of total param accesses after generateParamAccessSummary."
}
52 "Number of total param accesses after generateParamAccessSummary.")static llvm::Statistic NumCombinedParamAccessesAfter = {"stack-safety"
, "NumCombinedParamAccessesAfter", "Number of total param accesses after generateParamAccessSummary."
};
53STATISTIC(NumCombinedDataFlowNodes,static llvm::Statistic NumCombinedDataFlowNodes = {"stack-safety"
, "NumCombinedDataFlowNodes", "Number of total nodes in combined index for dataflow processing."
}
54 "Number of total nodes in combined index for dataflow processing.")static llvm::Statistic NumCombinedDataFlowNodes = {"stack-safety"
, "NumCombinedDataFlowNodes", "Number of total nodes in combined index for dataflow processing."
};
55STATISTIC(NumIndexCalleeUnhandled, "Number of index callee which are unhandled.")static llvm::Statistic NumIndexCalleeUnhandled = {"stack-safety"
, "NumIndexCalleeUnhandled", "Number of index callee which are unhandled."
};
56STATISTIC(NumIndexCalleeMultipleWeak, "Number of index callee non-unique weak.")static llvm::Statistic NumIndexCalleeMultipleWeak = {"stack-safety"
, "NumIndexCalleeMultipleWeak", "Number of index callee non-unique weak."
};
57STATISTIC(NumIndexCalleeMultipleExternal, "Number of index callee non-unique external.")static llvm::Statistic NumIndexCalleeMultipleExternal = {"stack-safety"
, "NumIndexCalleeMultipleExternal", "Number of index callee non-unique external."
};
58
59
60static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
61 cl::init(20), cl::Hidden);
62
63static cl::opt<bool> StackSafetyPrint("stack-safety-print", cl::init(false),
64 cl::Hidden);
65
66static cl::opt<bool> StackSafetyRun("stack-safety-run", cl::init(false),
67 cl::Hidden);
68
69namespace {
70
71// Check if we should bailout for such ranges.
72bool isUnsafe(const ConstantRange &R) {
73 return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
74}
75
76ConstantRange addOverflowNever(const ConstantRange &L, const ConstantRange &R) {
77 assert(!L.isSignWrappedSet())((!L.isSignWrappedSet()) ? static_cast<void> (0) : __assert_fail
("!L.isSignWrappedSet()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 77, __PRETTY_FUNCTION__));
78 assert(!R.isSignWrappedSet())((!R.isSignWrappedSet()) ? static_cast<void> (0) : __assert_fail
("!R.isSignWrappedSet()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 78, __PRETTY_FUNCTION__));
79 if (L.signedAddMayOverflow(R) !=
80 ConstantRange::OverflowResult::NeverOverflows)
81 return ConstantRange::getFull(L.getBitWidth());
82 ConstantRange Result = L.add(R);
83 assert(!Result.isSignWrappedSet())((!Result.isSignWrappedSet()) ? static_cast<void> (0) :
__assert_fail ("!Result.isSignWrappedSet()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 83, __PRETTY_FUNCTION__));
84 return Result;
85}
86
87ConstantRange unionNoWrap(const ConstantRange &L, const ConstantRange &R) {
88 assert(!L.isSignWrappedSet())((!L.isSignWrappedSet()) ? static_cast<void> (0) : __assert_fail
("!L.isSignWrappedSet()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 88, __PRETTY_FUNCTION__));
89 assert(!R.isSignWrappedSet())((!R.isSignWrappedSet()) ? static_cast<void> (0) : __assert_fail
("!R.isSignWrappedSet()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 89, __PRETTY_FUNCTION__));
90 auto Result = L.unionWith(R);
91 // Two non-wrapped sets can produce wrapped.
92 if (Result.isSignWrappedSet())
93 Result = ConstantRange::getFull(Result.getBitWidth());
94 return Result;
95}
96
97/// Describes use of address in as a function call argument.
98template <typename CalleeTy> struct CallInfo {
99 /// Function being called.
100 const CalleeTy *Callee = nullptr;
101 /// Index of argument which pass address.
102 size_t ParamNo = 0;
103
104 CallInfo(const CalleeTy *Callee, size_t ParamNo)
105 : Callee(Callee), ParamNo(ParamNo) {}
106
107 struct Less {
108 bool operator()(const CallInfo &L, const CallInfo &R) const {
109 return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
110 }
111 };
112};
113
114/// Describe uses of address (alloca or parameter) inside of the function.
115template <typename CalleeTy> struct UseInfo {
116 // Access range if the address (alloca or parameters).
117 // It is allowed to be empty-set when there are no known accesses.
118 ConstantRange Range;
119
120 // List of calls which pass address as an argument.
121 // Value is offset range of address from base address (alloca or calling
122 // function argument). Range should never set to empty-set, that is an invalid
123 // access range that can cause empty-set to be propagated with
124 // ConstantRange::add
125 using CallsTy = std::map<CallInfo<CalleeTy>, ConstantRange,
126 typename CallInfo<CalleeTy>::Less>;
127 CallsTy Calls;
128
129 UseInfo(unsigned PointerSize) : Range{PointerSize, false} {}
130
131 void updateRange(const ConstantRange &R) { Range = unionNoWrap(Range, R); }
132};
133
134template <typename CalleeTy>
135raw_ostream &operator<<(raw_ostream &OS, const UseInfo<CalleeTy> &U) {
136 OS << U.Range;
137 for (auto &Call : U.Calls)
138 OS << ", "
139 << "@" << Call.first.Callee->getName() << "(arg" << Call.first.ParamNo
140 << ", " << Call.second << ")";
141 return OS;
142}
143
144/// Calculate the allocation size of a given alloca. Returns empty range
145// in case of confution.
146ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) {
147 const DataLayout &DL = AI.getModule()->getDataLayout();
148 TypeSize TS = DL.getTypeAllocSize(AI.getAllocatedType());
149 unsigned PointerSize = DL.getMaxPointerSizeInBits();
150 // Fallback to empty range for alloca size.
151 ConstantRange R = ConstantRange::getEmpty(PointerSize);
152 if (TS.isScalable())
153 return R;
154 APInt APSize(PointerSize, TS.getFixedSize(), true);
155 if (APSize.isNonPositive())
156 return R;
157 if (AI.isArrayAllocation()) {
158 const auto *C = dyn_cast<ConstantInt>(AI.getArraySize());
159 if (!C)
160 return R;
161 bool Overflow = false;
162 APInt Mul = C->getValue();
163 if (Mul.isNonPositive())
164 return R;
165 Mul = Mul.sextOrTrunc(PointerSize);
166 APSize = APSize.smul_ov(Mul, Overflow);
167 if (Overflow)
168 return R;
169 }
170 R = ConstantRange(APInt::getNullValue(PointerSize), APSize);
171 assert(!isUnsafe(R))((!isUnsafe(R)) ? static_cast<void> (0) : __assert_fail
("!isUnsafe(R)", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 171, __PRETTY_FUNCTION__));
172 return R;
173}
174
175template <typename CalleeTy> struct FunctionInfo {
176 std::map<const AllocaInst *, UseInfo<CalleeTy>> Allocas;
177 std::map<uint32_t, UseInfo<CalleeTy>> Params;
178 // TODO: describe return value as depending on one or more of its arguments.
179
180 // StackSafetyDataFlowAnalysis counter stored here for faster access.
181 int UpdateCount = 0;
182
183 void print(raw_ostream &O, StringRef Name, const Function *F) const {
184 // TODO: Consider different printout format after
185 // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.
186 O << " @" << Name << ((F && F->isDSOLocal()) ? "" : " dso_preemptable")
187 << ((F && F->isInterposable()) ? " interposable" : "") << "\n";
188
189 O << " args uses:\n";
190 for (auto &KV : Params) {
191 O << " ";
192 if (F)
193 O << F->getArg(KV.first)->getName();
194 else
195 O << formatv("arg{0}", KV.first);
196 O << "[]: " << KV.second << "\n";
197 }
198
199 O << " allocas uses:\n";
200 if (F) {
201 for (auto &I : instructions(F)) {
202 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
203 auto &AS = Allocas.find(AI)->second;
204 O << " " << AI->getName() << "["
205 << getStaticAllocaSizeRange(*AI).getUpper() << "]: " << AS << "\n";
206 }
207 }
208 } else {
209 assert(Allocas.empty())((Allocas.empty()) ? static_cast<void> (0) : __assert_fail
("Allocas.empty()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 209, __PRETTY_FUNCTION__));
210 }
211 O << "\n";
212 }
213};
214
215using GVToSSI = std::map<const GlobalValue *, FunctionInfo<GlobalValue>>;
216
217} // namespace
218
219struct StackSafetyInfo::InfoTy {
220 FunctionInfo<GlobalValue> Info;
221};
222
223struct StackSafetyGlobalInfo::InfoTy {
224 GVToSSI Info;
225 SmallPtrSet<const AllocaInst *, 8> SafeAllocas;
226};
227
228namespace {
229
230class StackSafetyLocalAnalysis {
231 Function &F;
232 const DataLayout &DL;
233 ScalarEvolution &SE;
234 unsigned PointerSize = 0;
235
236 const ConstantRange UnknownRange;
237
238 ConstantRange offsetFrom(Value *Addr, Value *Base);
239 ConstantRange getAccessRange(Value *Addr, Value *Base,
240 const ConstantRange &SizeRange);
241 ConstantRange getAccessRange(Value *Addr, Value *Base, TypeSize Size);
242 ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
243 Value *Base);
244
245 bool analyzeAllUses(Value *Ptr, UseInfo<GlobalValue> &AS,
246 const StackLifetime &SL);
247
248public:
249 StackSafetyLocalAnalysis(Function &F, ScalarEvolution &SE)
250 : F(F), DL(F.getParent()->getDataLayout()), SE(SE),
251 PointerSize(DL.getPointerSizeInBits()),
252 UnknownRange(PointerSize, true) {}
253
254 // Run the transformation on the associated function.
255 FunctionInfo<GlobalValue> run();
256};
257
258ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {
259 if (!SE.isSCEVable(Addr->getType()) || !SE.isSCEVable(Base->getType()))
260 return UnknownRange;
261
262 auto *PtrTy = IntegerType::getInt8PtrTy(SE.getContext());
263 const SCEV *AddrExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Addr), PtrTy);
264 const SCEV *BaseExp = SE.getTruncateOrZeroExtend(SE.getSCEV(Base), PtrTy);
265 const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);
266
267 ConstantRange Offset = SE.getSignedRange(Diff);
268 if (isUnsafe(Offset))
269 return UnknownRange;
270 return Offset.sextOrTrunc(PointerSize);
271}
272
273ConstantRange
274StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
275 const ConstantRange &SizeRange) {
276 // Zero-size loads and stores do not access memory.
277 if (SizeRange.isEmptySet())
278 return ConstantRange::getEmpty(PointerSize);
279 assert(!isUnsafe(SizeRange))((!isUnsafe(SizeRange)) ? static_cast<void> (0) : __assert_fail
("!isUnsafe(SizeRange)", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 279, __PRETTY_FUNCTION__));
280
281 ConstantRange Offsets = offsetFrom(Addr, Base);
282 if (isUnsafe(Offsets))
283 return UnknownRange;
284
285 Offsets = addOverflowNever(Offsets, SizeRange);
286 if (isUnsafe(Offsets))
287 return UnknownRange;
288 return Offsets;
289}
290
291ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
292 TypeSize Size) {
293 if (Size.isScalable())
294 return UnknownRange;
295 APInt APSize(PointerSize, Size.getFixedSize(), true);
296 if (APSize.isNegative())
297 return UnknownRange;
298 return getAccessRange(
299 Addr, Base, ConstantRange(APInt::getNullValue(PointerSize), APSize));
300}
301
302ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
303 const MemIntrinsic *MI, const Use &U, Value *Base) {
304 if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
305 if (MTI->getRawSource() != U && MTI->getRawDest() != U)
306 return ConstantRange::getEmpty(PointerSize);
307 } else {
308 if (MI->getRawDest() != U)
309 return ConstantRange::getEmpty(PointerSize);
310 }
311
312 auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
313 if (!SE.isSCEVable(MI->getLength()->getType()))
314 return UnknownRange;
315
316 const SCEV *Expr =
317 SE.getTruncateOrZeroExtend(SE.getSCEV(MI->getLength()), CalculationTy);
318 ConstantRange Sizes = SE.getSignedRange(Expr);
319 if (Sizes.getUpper().isNegative() || isUnsafe(Sizes))
320 return UnknownRange;
321 Sizes = Sizes.sextOrTrunc(PointerSize);
322 ConstantRange SizeRange(APInt::getNullValue(PointerSize),
323 Sizes.getUpper() - 1);
324 return getAccessRange(U, Base, SizeRange);
325}
326
327/// The function analyzes all local uses of Ptr (alloca or argument) and
328/// calculates local access range and all function calls where it was used.
329bool StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr,
330 UseInfo<GlobalValue> &US,
331 const StackLifetime &SL) {
332 SmallPtrSet<const Value *, 16> Visited;
333 SmallVector<const Value *, 8> WorkList;
334 WorkList.push_back(Ptr);
335 const AllocaInst *AI = dyn_cast<AllocaInst>(Ptr);
336
337 // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
338 while (!WorkList.empty()) {
339 const Value *V = WorkList.pop_back_val();
340 for (const Use &UI : V->uses()) {
341 const auto *I = cast<Instruction>(UI.getUser());
342 if (!SL.isReachable(I))
343 continue;
344
345 assert(V == UI.get())((V == UI.get()) ? static_cast<void> (0) : __assert_fail
("V == UI.get()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 345, __PRETTY_FUNCTION__));
346
347 switch (I->getOpcode()) {
348 case Instruction::Load: {
349 if (AI && !SL.isAliveAfter(AI, I)) {
350 US.updateRange(UnknownRange);
351 return false;
352 }
353 US.updateRange(
354 getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType())));
355 break;
356 }
357
358 case Instruction::VAArg:
359 // "va-arg" from a pointer is safe.
360 break;
361 case Instruction::Store: {
362 if (V == I->getOperand(0)) {
363 // Stored the pointer - conservatively assume it may be unsafe.
364 US.updateRange(UnknownRange);
365 return false;
366 }
367 if (AI && !SL.isAliveAfter(AI, I)) {
368 US.updateRange(UnknownRange);
369 return false;
370 }
371 US.updateRange(getAccessRange(
372 UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType())));
373 break;
374 }
375
376 case Instruction::Ret:
377 // Information leak.
378 // FIXME: Process parameters correctly. This is a leak only if we return
379 // alloca.
380 US.updateRange(UnknownRange);
381 return false;
382
383 case Instruction::Call:
384 case Instruction::Invoke: {
385 if (I->isLifetimeStartOrEnd())
386 break;
387
388 if (AI && !SL.isAliveAfter(AI, I)) {
389 US.updateRange(UnknownRange);
390 return false;
391 }
392
393 if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
394 US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr));
395 break;
396 }
397
398 const auto &CB = cast<CallBase>(*I);
399 if (!CB.isArgOperand(&UI)) {
400 US.updateRange(UnknownRange);
401 return false;
402 }
403
404 unsigned ArgNo = CB.getArgOperandNo(&UI);
405 if (CB.isByValArgument(ArgNo)) {
406 US.updateRange(getAccessRange(
407 UI, Ptr, DL.getTypeStoreSize(CB.getParamByValType(ArgNo))));
408 break;
409 }
410
411 // FIXME: consult devirt?
412 // Do not follow aliases, otherwise we could inadvertently follow
413 // dso_preemptable aliases or aliases with interposable linkage.
414 const GlobalValue *Callee =
415 dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
416 if (!Callee) {
417 US.updateRange(UnknownRange);
418 return false;
419 }
420
421 assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee))((isa<Function>(Callee) || isa<GlobalAlias>(Callee
)) ? static_cast<void> (0) : __assert_fail ("isa<Function>(Callee) || isa<GlobalAlias>(Callee)"
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 421, __PRETTY_FUNCTION__));
422 ConstantRange Offsets = offsetFrom(UI, Ptr);
423 auto Insert =
424 US.Calls.emplace(CallInfo<GlobalValue>(Callee, ArgNo), Offsets);
425 if (!Insert.second)
426 Insert.first->second = Insert.first->second.unionWith(Offsets);
427 break;
428 }
429
430 default:
431 if (Visited.insert(I).second)
432 WorkList.push_back(cast<const Instruction>(I));
433 }
434 }
435 }
436
437 return true;
438}
439
440FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() {
441 FunctionInfo<GlobalValue> Info;
442 assert(!F.isDeclaration() &&((!F.isDeclaration() && "Can't run StackSafety on a function declaration"
) ? static_cast<void> (0) : __assert_fail ("!F.isDeclaration() && \"Can't run StackSafety on a function declaration\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 443, __PRETTY_FUNCTION__))
443 "Can't run StackSafety on a function declaration")((!F.isDeclaration() && "Can't run StackSafety on a function declaration"
) ? static_cast<void> (0) : __assert_fail ("!F.isDeclaration() && \"Can't run StackSafety on a function declaration\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 443, __PRETTY_FUNCTION__));
444
445 LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("stack-safety")) { dbgs() << "[StackSafety] " <<
F.getName() << "\n"; } } while (false);
446
447 SmallVector<AllocaInst *, 64> Allocas;
448 for (auto &I : instructions(F))
449 if (auto *AI = dyn_cast<AllocaInst>(&I))
450 Allocas.push_back(AI);
451 StackLifetime SL(F, Allocas, StackLifetime::LivenessType::Must);
452 SL.run();
453
454 for (auto *AI : Allocas) {
455 auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second;
456 analyzeAllUses(AI, UI, SL);
457 }
458
459 for (Argument &A : make_range(F.arg_begin(), F.arg_end())) {
460 // Non pointers and bypass arguments are not going to be used in any global
461 // processing.
462 if (A.getType()->isPointerTy() && !A.hasByValAttr()) {
463 auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second;
464 analyzeAllUses(&A, UI, SL);
465 }
466 }
467
468 LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("stack-safety")) { Info.print(dbgs(), F.getName(), &F); }
} while (false);
469 LLVM_DEBUG(dbgs() << "[StackSafety] done\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("stack-safety")) { dbgs() << "[StackSafety] done\n"; }
} while (false);
470 return Info;
471}
472
473template <typename CalleeTy> class StackSafetyDataFlowAnalysis {
474 using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>;
475
476 FunctionMap Functions;
477 const ConstantRange UnknownRange;
478
479 // Callee-to-Caller multimap.
480 DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers;
481 SetVector<const CalleeTy *> WorkList;
482
483 bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet);
484 void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS);
485 void updateOneNode(const CalleeTy *Callee) {
486 updateOneNode(Callee, Functions.find(Callee)->second);
487 }
488 void updateAllNodes() {
489 for (auto &F : Functions)
490 updateOneNode(F.first, F.second);
491 }
492 void runDataFlow();
493#ifndef NDEBUG
494 void verifyFixedPoint();
495#endif
496
497public:
498 StackSafetyDataFlowAnalysis(uint32_t PointerBitWidth, FunctionMap Functions)
499 : Functions(std::move(Functions)),
500 UnknownRange(ConstantRange::getFull(PointerBitWidth)) {}
501
502 const FunctionMap &run();
503
504 ConstantRange getArgumentAccessRange(const CalleeTy *Callee, unsigned ParamNo,
505 const ConstantRange &Offsets) const;
506};
507
508template <typename CalleeTy>
509ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(
510 const CalleeTy *Callee, unsigned ParamNo,
511 const ConstantRange &Offsets) const {
512 auto FnIt = Functions.find(Callee);
513 // Unknown callee (outside of LTO domain or an indirect call).
514 if (FnIt == Functions.end())
515 return UnknownRange;
516 auto &FS = FnIt->second;
517 auto ParamIt = FS.Params.find(ParamNo);
518 if (ParamIt == FS.Params.end())
519 return UnknownRange;
520 auto &Access = ParamIt->second.Range;
521 if (Access.isEmptySet())
522 return Access;
523 if (Access.isFullSet())
524 return UnknownRange;
525 return addOverflowNever(Access, Offsets);
526}
527
528template <typename CalleeTy>
529bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,
530 bool UpdateToFullSet) {
531 bool Changed = false;
532 for (auto &KV : US.Calls) {
533 assert(!KV.second.isEmptySet() &&((!KV.second.isEmptySet() && "Param range can't be empty-set, invalid offset range"
) ? static_cast<void> (0) : __assert_fail ("!KV.second.isEmptySet() && \"Param range can't be empty-set, invalid offset range\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 534, __PRETTY_FUNCTION__))
534 "Param range can't be empty-set, invalid offset range")((!KV.second.isEmptySet() && "Param range can't be empty-set, invalid offset range"
) ? static_cast<void> (0) : __assert_fail ("!KV.second.isEmptySet() && \"Param range can't be empty-set, invalid offset range\""
, "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 534, __PRETTY_FUNCTION__));
535
536 ConstantRange CalleeRange =
537 getArgumentAccessRange(KV.first.Callee, KV.first.ParamNo, KV.second);
538 if (!US.Range.contains(CalleeRange)) {
539 Changed = true;
540 if (UpdateToFullSet)
541 US.Range = UnknownRange;
542 else
543 US.updateRange(CalleeRange);
544 }
545 }
546 return Changed;
547}
548
549template <typename CalleeTy>
550void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(
551 const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) {
552 bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
553 bool Changed = false;
554 for (auto &KV : FS.Params)
555 Changed |= updateOneUse(KV.second, UpdateToFullSet);
556
557 if (Changed) {
558 LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCountdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("stack-safety")) { dbgs() << "=== update [" << FS
.UpdateCount << (UpdateToFullSet ? ", full-set" : "") <<
"] " << &FS << "\n"; } } while (false)
559 << (UpdateToFullSet ? ", full-set" : "") << "] " << &FSdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("stack-safety")) { dbgs() << "=== update [" << FS
.UpdateCount << (UpdateToFullSet ? ", full-set" : "") <<
"] " << &FS << "\n"; } } while (false)
560 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("stack-safety")) { dbgs() << "=== update [" << FS
.UpdateCount << (UpdateToFullSet ? ", full-set" : "") <<
"] " << &FS << "\n"; } } while (false);
561 // Callers of this function may need updating.
562 for (auto &CallerID : Callers[Callee])
563 WorkList.insert(CallerID);
564
565 ++FS.UpdateCount;
566 }
567}
568
569template <typename CalleeTy>
570void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {
571 SmallVector<const CalleeTy *, 16> Callees;
572 for (auto &F : Functions) {
573 Callees.clear();
574 auto &FS = F.second;
575 for (auto &KV : FS.Params)
576 for (auto &CS : KV.second.Calls)
577 Callees.push_back(CS.first.Callee);
578
579 llvm::sort(Callees);
580 Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
581
582 for (auto &Callee : Callees)
583 Callers[Callee].push_back(F.first);
584 }
585
586 updateAllNodes();
587
588 while (!WorkList.empty()) {
589 const CalleeTy *Callee = WorkList.back();
590 WorkList.pop_back();
591 updateOneNode(Callee);
592 }
593}
594
595#ifndef NDEBUG
596template <typename CalleeTy>
597void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {
598 WorkList.clear();
599 updateAllNodes();
600 assert(WorkList.empty())((WorkList.empty()) ? static_cast<void> (0) : __assert_fail
("WorkList.empty()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 600, __PRETTY_FUNCTION__));
601}
602#endif
603
604template <typename CalleeTy>
605const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &
606StackSafetyDataFlowAnalysis<CalleeTy>::run() {
607 runDataFlow();
608 LLVM_DEBUG(verifyFixedPoint())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("stack-safety")) { verifyFixedPoint(); } } while (false);
609 return Functions;
610}
611
612FunctionSummary *findCalleeFunctionSummary(ValueInfo VI, StringRef ModuleId) {
613 if (!VI)
614 return nullptr;
615 auto SummaryList = VI.getSummaryList();
616 GlobalValueSummary* S = nullptr;
617 for (const auto& GVS : SummaryList) {
618 if (!GVS->isLive())
619 continue;
620 if (const AliasSummary *AS = dyn_cast<AliasSummary>(GVS.get()))
621 if (!AS->hasAliasee())
622 continue;
623 if (!isa<FunctionSummary>(GVS->getBaseObject()))
624 continue;
625 if (GlobalValue::isLocalLinkage(GVS->linkage())) {
626 if (GVS->modulePath() == ModuleId) {
627 S = GVS.get();
628 break;
629 }
630 } else if (GlobalValue::isExternalLinkage(GVS->linkage())) {
631 if (S) {
632 ++NumIndexCalleeMultipleExternal;
633 return nullptr;
634 }
635 S = GVS.get();
636 } else if (GlobalValue::isWeakLinkage(GVS->linkage())) {
637 if (S) {
638 ++NumIndexCalleeMultipleWeak;
639 return nullptr;
640 }
641 S = GVS.get();
642 } else if (GlobalValue::isAvailableExternallyLinkage(GVS->linkage()) ||
643 GlobalValue::isLinkOnceLinkage(GVS->linkage())) {
644 if (SummaryList.size() == 1)
645 S = GVS.get();
646 // According thinLTOResolvePrevailingGUID these are unlikely prevailing.
647 } else {
648 ++NumIndexCalleeUnhandled;
649 }
650 };
651 while (S) {
652 if (!S->isLive() || !S->isDSOLocal())
653 return nullptr;
654 if (FunctionSummary *FS = dyn_cast<FunctionSummary>(S))
655 return FS;
656 AliasSummary *AS = dyn_cast<AliasSummary>(S);
657 if (!AS || !AS->hasAliasee())
658 return nullptr;
659 S = AS->getBaseObject();
660 if (S == AS)
661 return nullptr;
662 }
663 return nullptr;
664}
665
666const Function *findCalleeInModule(const GlobalValue *GV) {
667 while (GV) {
668 if (GV->isDeclaration() || GV->isInterposable() || !GV->isDSOLocal())
669 return nullptr;
670 if (const Function *F = dyn_cast<Function>(GV))
671 return F;
672 const GlobalAlias *A = dyn_cast<GlobalAlias>(GV);
673 if (!A)
674 return nullptr;
675 GV = A->getBaseObject();
676 if (GV == A)
677 return nullptr;
678 }
679 return nullptr;
680}
681
682const ConstantRange *findParamAccess(const FunctionSummary &FS,
683 uint32_t ParamNo) {
684 assert(FS.isLive())((FS.isLive()) ? static_cast<void> (0) : __assert_fail (
"FS.isLive()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 684, __PRETTY_FUNCTION__));
685 assert(FS.isDSOLocal())((FS.isDSOLocal()) ? static_cast<void> (0) : __assert_fail
("FS.isDSOLocal()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 685, __PRETTY_FUNCTION__));
686 for (auto &PS : FS.paramAccesses())
687 if (ParamNo == PS.ParamNo)
688 return &PS.Use;
689 return nullptr;
690}
691
692void resolveAllCalls(UseInfo<GlobalValue> &Use,
693 const ModuleSummaryIndex *Index) {
694 ConstantRange FullSet(Use.Range.getBitWidth(), true);
695 UseInfo<GlobalValue>::CallsTy TmpCalls = std::move(Use.Calls);
11
←
Object 'Calls' of type 'std::map' is left in a valid but unspecified state after move
→
696 for (const auto &C : TmpCalls) {
697 const Function *F = findCalleeInModule(C.first.Callee);
698 if (F) {
12
←
Assuming 'F' is non-null
→
13
←
Taking true branch
→
699 Use.Calls.emplace(CallInfo<GlobalValue>(F, C.first.ParamNo), C.second);
14
←
Method called on moved-from object 'Calls' of type 'std::map'
700 continue;
701 }
702
703 if (!Index)
704 return Use.updateRange(FullSet);
705 FunctionSummary *FS =
706 findCalleeFunctionSummary(Index->getValueInfo(C.first.Callee->getGUID()),
707 C.first.Callee->getParent()->getModuleIdentifier());
708 ++NumModuleCalleeLookupTotal;
709 if (!FS) {
710 ++NumModuleCalleeLookupFailed;
711 return Use.updateRange(FullSet);
712 }
713 const ConstantRange *Found = findParamAccess(*FS, C.first.ParamNo);
714 if (!Found || Found->isFullSet())
715 return Use.updateRange(FullSet);
716 ConstantRange Access = Found->sextOrTrunc(Use.Range.getBitWidth());
717 if (!Access.isEmptySet())
718 Use.updateRange(addOverflowNever(Access, C.second));
719 }
720}
721
722GVToSSI createGlobalStackSafetyInfo(
723 std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions,
724 const ModuleSummaryIndex *Index) {
725 GVToSSI SSI;
726 if (Functions.empty())
8
←
Assuming the condition is false
→
9
←
Taking false branch
→
727 return SSI;
728
729 // FIXME: Simplify printing and remove copying here.
730 auto Copy = Functions;
731
732 for (auto &FnKV : Copy)
733 for (auto &KV : FnKV.second.Params) {
734 resolveAllCalls(KV.second, Index);
10
←
Calling 'resolveAllCalls'
→
735 if (KV.second.Range.isFullSet())
736 KV.second.Calls.clear();
737 }
738
739 uint32_t PointerSize = Copy.begin()
740 ->first->getParent()
741 ->getDataLayout()
742 .getMaxPointerSizeInBits();
743 StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy));
744
745 for (auto &F : SSDFA.run()) {
746 auto FI = F.second;
747 auto &SrcF = Functions[F.first];
748 for (auto &KV : FI.Allocas) {
749 auto &A = KV.second;
750 resolveAllCalls(A, Index);
751 for (auto &C : A.Calls) {
752 A.updateRange(SSDFA.getArgumentAccessRange(C.first.Callee,
753 C.first.ParamNo, C.second));
754 }
755 // FIXME: This is needed only to preserve calls in print() results.
756 A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;
757 }
758 for (auto &KV : FI.Params) {
759 auto &P = KV.second;
760 P.Calls = SrcF.Params.find(KV.first)->second.Calls;
761 }
762 SSI[F.first] = std::move(FI);
763 }
764
765 return SSI;
766}
767
768} // end anonymous namespace
769
770StackSafetyInfo::StackSafetyInfo() = default;
771
772StackSafetyInfo::StackSafetyInfo(Function *F,
773 std::function<ScalarEvolution &()> GetSE)
774 : F(F), GetSE(GetSE) {}
775
776StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
777
778StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
779
780StackSafetyInfo::~StackSafetyInfo() = default;
781
782const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const {
783 if (!Info) {
784 StackSafetyLocalAnalysis SSLA(*F, GetSE());
785 Info.reset(new InfoTy{SSLA.run()});
786 }
787 return *Info;
788}
789
790void StackSafetyInfo::print(raw_ostream &O) const {
791 getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
792}
793
794const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {
795 if (!Info) {
6
←
Taking true branch
→
796 std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;
797 for (auto &F : M->functions()) {
798 if (!F.isDeclaration()) {
799 auto FI = GetSSI(F).getInfo().Info;
800 Functions.emplace(&F, std::move(FI));
801 }
802 }
803 Info.reset(new InfoTy{
804 createGlobalStackSafetyInfo(std::move(Functions), Index), {}});
7
←
Calling 'createGlobalStackSafetyInfo'
→
805 for (auto &FnKV : Info->Info) {
806 for (auto &KV : FnKV.second.Allocas) {
807 ++NumAllocaTotal;
808 const AllocaInst *AI = KV.first;
809 if (getStaticAllocaSizeRange(*AI).contains(KV.second.Range)) {
810 Info->SafeAllocas.insert(AI);
811 ++NumAllocaStackSafe;
812 }
813 }
814 }
815 if (StackSafetyPrint)
816 print(errs());
817 }
818 return *Info;
819}
820
821std::vector<FunctionSummary::ParamAccess>
822StackSafetyInfo::getParamAccesses(ModuleSummaryIndex &Index) const {
823 // Implementation transforms internal representation of parameter information
824 // into FunctionSummary format.
825 std::vector<FunctionSummary::ParamAccess> ParamAccesses;
826 for (const auto &KV : getInfo().Info.Params) {
827 auto &PS = KV.second;
828 // Parameter accessed by any or unknown offset, represented as FullSet by
829 // StackSafety, is handled as the parameter for which we have no
830 // StackSafety info at all. So drop it to reduce summary size.
831 if (PS.Range.isFullSet())
832 continue;
833
834 ParamAccesses.emplace_back(KV.first, PS.Range);
835 FunctionSummary::ParamAccess &Param = ParamAccesses.back();
836
837 Param.Calls.reserve(PS.Calls.size());
838 for (auto &C : PS.Calls) {
839 // Parameter forwarded into another function by any or unknown offset
840 // will make ParamAccess::Range as FullSet anyway. So we can drop the
841 // entire parameter like we did above.
842 // TODO(vitalybuka): Return already filtered parameters from getInfo().
843 if (C.second.isFullSet()) {
844 ParamAccesses.pop_back();
845 break;
846 }
847 Param.Calls.emplace_back(C.first.ParamNo,
848 Index.getOrInsertValueInfo(C.first.Callee),
849 C.second);
850 }
851 }
852 for (FunctionSummary::ParamAccess &Param : ParamAccesses) {
853 sort(Param.Calls, [](const FunctionSummary::ParamAccess::Call &L,
854 const FunctionSummary::ParamAccess::Call &R) {
855 return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
856 });
857 }
858 return ParamAccesses;
859}
860
861StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;
862
863StackSafetyGlobalInfo::StackSafetyGlobalInfo(
864 Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,
865 const ModuleSummaryIndex *Index)
866 : M(M), GetSSI(GetSSI), Index(Index) {
867 if (StackSafetyRun)
3
←
Assuming the condition is true
→
4
←
Taking true branch
→
868 getInfo();
5
←
Calling 'StackSafetyGlobalInfo::getInfo'
→
869}
870
871StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =
872 default;
873
874StackSafetyGlobalInfo &
875StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;
876
877StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;
878
879bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const {
880 const auto &Info = getInfo();
881 return Info.SafeAllocas.count(&AI);
882}
883
884void StackSafetyGlobalInfo::print(raw_ostream &O) const {
885 auto &SSI = getInfo().Info;
886 if (SSI.empty())
887 return;
888 const Module &M = *SSI.begin()->first->getParent();
889 for (auto &F : M.functions()) {
890 if (!F.isDeclaration()) {
891 SSI.find(&F)->second.print(O, F.getName(), &F);
892 O << "\n";
893 }
894 }
895}
896
897LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void StackSafetyGlobalInfo::dump() const { print(dbgs()); }
898
899AnalysisKey StackSafetyAnalysis::Key;
900
901StackSafetyInfo StackSafetyAnalysis::run(Function &F,
902 FunctionAnalysisManager &AM) {
903 return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
904 return AM.getResult<ScalarEvolutionAnalysis>(F);
905 });
906}
907
908PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
909 FunctionAnalysisManager &AM) {
910 OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
911 AM.getResult<StackSafetyAnalysis>(F).print(OS);
912 return PreservedAnalyses::all();
913}
914
915char StackSafetyInfoWrapperPass::ID = 0;
916
917StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
918 initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
919}
920
921void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
922 AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
923 AU.setPreservesAll();
924}
925
926void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
927 SSI.print(O);
928}
929
930bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
931 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
932 SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
933 return false;
934}
935
936AnalysisKey StackSafetyGlobalAnalysis::Key;
937
938StackSafetyGlobalInfo
939StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
940 // FIXME: Lookup Module Summary.
941 FunctionAnalysisManager &FAM =
942 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
943 return {&M,
944 [&FAM](Function &F) -> const StackSafetyInfo & {
945 return FAM.getResult<StackSafetyAnalysis>(F);
946 },
947 nullptr};
948}
949
950PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
951 ModuleAnalysisManager &AM) {
952 OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
953 AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS);
954 return PreservedAnalyses::all();
955}
956
957char StackSafetyGlobalInfoWrapperPass::ID = 0;
958
959StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
960 : ModulePass(ID) {
961 initializeStackSafetyGlobalInfoWrapperPassPass(
962 *PassRegistry::getPassRegistry());
963}
964
965StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;
966
967void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
968 const Module *M) const {
969 SSGI.print(O);
970}
971
972void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
973 AnalysisUsage &AU) const {
974 AU.setPreservesAll();
975 AU.addRequired<StackSafetyInfoWrapperPass>();
976}
977
978bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
979 const ModuleSummaryIndex *ImportSummary = nullptr;
980 if (auto *IndexWrapperPass
0.1
'IndexWrapperPass' is null
 =
1
Taking false branch
→
981 getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
982 ImportSummary = IndexWrapperPass->getIndex();
983
984 SSGI = {&M,
2
←
Calling constructor for 'StackSafetyGlobalInfo'
→
985 [this](Function &F) -> const StackSafetyInfo & {
986 return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
987 },
988 ImportSummary};
989 return false;
990}
991
992bool llvm::needsParamAccessSummary(const Module &M) {
993 if (StackSafetyRun)
994 return true;
995 for (auto &F : M.functions())
996 if (F.hasFnAttribute(Attribute::SanitizeMemTag))
997 return true;
998 return false;
999}
1000
1001void llvm::generateParamAccessSummary(ModuleSummaryIndex &Index) {
1002 if (!Index.hasParamAccess())
1003 return;
1004 const ConstantRange FullSet(FunctionSummary::ParamAccess::RangeWidth, true);
1005
1006 auto CountParamAccesses = [&](auto &Stat) {
1007 if (!AreStatisticsEnabled())
1008 return;
1009 for (auto &GVS : Index)
1010 for (auto &GV : GVS.second.SummaryList)
1011 if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get()))
1012 Stat += FS->paramAccesses().size();
1013 };
1014
1015 CountParamAccesses(NumCombinedParamAccessesBefore);
1016
1017 std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions;
1018
1019 // Convert the ModuleSummaryIndex to a FunctionMap
1020 for (auto &GVS : Index) {
1021 for (auto &GV : GVS.second.SummaryList) {
1022 FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get());
1023 if (!FS || FS->paramAccesses().empty())
1024 continue;
1025 if (FS->isLive() && FS->isDSOLocal()) {
1026 FunctionInfo<FunctionSummary> FI;
1027 for (auto &PS : FS->paramAccesses()) {
1028 auto &US =
1029 FI.Params
1030 .emplace(PS.ParamNo, FunctionSummary::ParamAccess::RangeWidth)
1031 .first->second;
1032 US.Range = PS.Use;
1033 for (auto &Call : PS.Calls) {
1034 assert(!Call.Offsets.isFullSet())((!Call.Offsets.isFullSet()) ? static_cast<void> (0) : __assert_fail
("!Call.Offsets.isFullSet()", "/build/llvm-toolchain-snapshot-12~++20200927111121+5811d723998/llvm/lib/Analysis/StackSafetyAnalysis.cpp"
, 1034, __PRETTY_FUNCTION__));
1035 FunctionSummary *S =
1036 findCalleeFunctionSummary(Call.Callee, FS->modulePath());
1037 ++NumCombinedCalleeLookupTotal;
1038 if (!S) {
1039 ++NumCombinedCalleeLookupFailed;
1040 US.Range = FullSet;
1041 US.Calls.clear();
1042 break;
1043 }
1044 US.Calls.emplace(CallInfo<FunctionSummary>(S, Call.ParamNo),
1045 Call.Offsets);
1046 }
1047 }
1048 Functions.emplace(FS, std::move(FI));
1049 }
1050 // Reset data for all summaries. Alive and DSO local will be set back from
1051 // of data flow results below. Anything else will not be accessed
1052 // by ThinLTO backend, so we can save on bitcode size.
1053 FS->setParamAccesses({});
1054 }
1055 }
1056 NumCombinedDataFlowNodes += Functions.size();
1057 StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA(
1058 FunctionSummary::ParamAccess::RangeWidth, std::move(Functions));
1059 for (auto &KV : SSDFA.run()) {
1060 std::vector<FunctionSummary::ParamAccess> NewParams;
1061 NewParams.reserve(KV.second.Params.size());
1062 for (auto &Param : KV.second.Params) {
1063 // It's not needed as FullSet is processed the same as a missing value.
1064 if (Param.second.Range.isFullSet())
1065 continue;
1066 NewParams.emplace_back();
1067 FunctionSummary::ParamAccess &New = NewParams.back();
1068 New.ParamNo = Param.first;
1069 New.Use = Param.second.Range; // Only range is needed.
1070 }
1071 const_cast<FunctionSummary *>(KV.first)->setParamAccesses(
1072 std::move(NewParams));
1073 }
1074
1075 CountParamAccesses(NumCombinedParamAccessesAfter);
1076}
1077
1078static const char LocalPassArg[] = "stack-safety-local";
1079static const char LocalPassName[] = "Stack Safety Local Analysis";
1080INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,static void *initializeStackSafetyInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1081 false, true)static void *initializeStackSafetyInfoWrapperPassPassOnce(PassRegistry
&Registry) {
1082INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);
1083INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,PassInfo *PI = new PassInfo( LocalPassName, LocalPassArg, &
StackSafetyInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<StackSafetyInfoWrapperPass>), false, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeStackSafetyInfoWrapperPassPassFlag
; void llvm::initializeStackSafetyInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeStackSafetyInfoWrapperPassPassFlag
, initializeStackSafetyInfoWrapperPassPassOnce, std::ref(Registry
)); }
1084 false, true)PassInfo *PI = new PassInfo( LocalPassName, LocalPassArg, &
StackSafetyInfoWrapperPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<StackSafetyInfoWrapperPass>), false, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeStackSafetyInfoWrapperPassPassFlag
; void llvm::initializeStackSafetyInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeStackSafetyInfoWrapperPassPassFlag
, initializeStackSafetyInfoWrapperPassPassOnce, std::ref(Registry
)); }
1085
1086static const char GlobalPassName[] = "Stack Safety Analysis";
1087INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,static void *initializeStackSafetyGlobalInfoWrapperPassPassOnce
(PassRegistry &Registry) {
1088 GlobalPassName, false, true)static void *initializeStackSafetyGlobalInfoWrapperPassPassOnce
(PassRegistry &Registry) {
1089INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)initializeStackSafetyInfoWrapperPassPass(Registry);
1090INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass)initializeImmutableModuleSummaryIndexWrapperPassPass(Registry
);
1091INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,PassInfo *PI = new PassInfo( GlobalPassName, "stack-safety", &
StackSafetyGlobalInfoWrapperPass::ID, PassInfo::NormalCtor_t(
callDefaultCtor<StackSafetyGlobalInfoWrapperPass>), false
, true); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeStackSafetyGlobalInfoWrapperPassPassFlag
; void llvm::initializeStackSafetyGlobalInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeStackSafetyGlobalInfoWrapperPassPassFlag
, initializeStackSafetyGlobalInfoWrapperPassPassOnce, std::ref
(Registry)); }
1092 GlobalPassName, false, true)PassInfo *PI = new PassInfo( GlobalPassName, "stack-safety", &
StackSafetyGlobalInfoWrapperPass::ID, PassInfo::NormalCtor_t(
callDefaultCtor<StackSafetyGlobalInfoWrapperPass>), false
, true); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeStackSafetyGlobalInfoWrapperPassPassFlag
; void llvm::initializeStackSafetyGlobalInfoWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeStackSafetyGlobalInfoWrapperPassPassFlag
, initializeStackSafetyGlobalInfoWrapperPassPassOnce, std::ref
(Registry)); }