Bug Summary

File:build/source/llvm/lib/Analysis/StackSafetyAnalysis.cpp
Warning:line 183, column 37
Value assigned to field 'UpdateCount' in implicit constructor is garbage or undefined

Annotated Source Code

Press '?' to see keyboard shortcuts

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