llvm-project

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

36
using namespace llvm;
37

38
#define DEBUG_TYPE "stack-safety"
39

40
STATISTIC(NumAllocaStackSafe, "Number of safe allocas");
41
STATISTIC(NumAllocaTotal, "Number of total allocas");
42

43
STATISTIC(NumCombinedCalleeLookupTotal,
44
          "Number of total callee lookups on combined index.");
45
STATISTIC(NumCombinedCalleeLookupFailed,
46
          "Number of failed callee lookups on combined index.");
47
STATISTIC(NumModuleCalleeLookupTotal,
48
          "Number of total callee lookups on module index.");
49
STATISTIC(NumModuleCalleeLookupFailed,
50
          "Number of failed callee lookups on module index.");
51
STATISTIC(NumCombinedParamAccessesBefore,
52
          "Number of total param accesses before generateParamAccessSummary.");
53
STATISTIC(NumCombinedParamAccessesAfter,
54
          "Number of total param accesses after generateParamAccessSummary.");
55
STATISTIC(NumCombinedDataFlowNodes,
56
          "Number of total nodes in combined index for dataflow processing.");
57
STATISTIC(NumIndexCalleeUnhandled, "Number of index callee which are unhandled.");
58
STATISTIC(NumIndexCalleeMultipleWeak, "Number of index callee non-unique weak.");
59
STATISTIC(NumIndexCalleeMultipleExternal, "Number of index callee non-unique external.");
60

61

62
static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
63
                                             cl::init(20), cl::Hidden);
64

65
static cl::opt<bool> StackSafetyPrint("stack-safety-print", cl::init(false),
66
                                      cl::Hidden);
67

68
static cl::opt<bool> StackSafetyRun("stack-safety-run", cl::init(false),
69
                                    cl::Hidden);
70

71
namespace {
72

73
// Check if we should bailout for such ranges.
74
bool isUnsafe(const ConstantRange &R) {
75
  return R.isEmptySet() || R.isFullSet() || R.isUpperSignWrapped();
76
}
77

78
ConstantRange addOverflowNever(const ConstantRange &L, const ConstantRange &R) {
79
  assert(!L.isSignWrappedSet());
80
  assert(!R.isSignWrappedSet());
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());
86
  return Result;
87
}
88

89
ConstantRange unionNoWrap(const ConstantRange &L, const ConstantRange &R) {
90
  assert(!L.isSignWrappedSet());
91
  assert(!R.isSignWrappedSet());
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.
100
template <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.
117
template <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

142
template <typename CalleeTy>
143
raw_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.
154
ConstantRange getStaticAllocaSizeRange(const AllocaInst &AI) {
155
  const DataLayout &DL = AI.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));
180
  return R;
181
}
182

183
template <typename CalleeTy> struct FunctionInfo {
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());
218
    }
219
  }
220
};
221

222
using GVToSSI = std::map<const GlobalValue *, FunctionInfo<GlobalValue>>;
223

224
} // namespace
225

226
struct StackSafetyInfo::InfoTy {
227
  FunctionInfo<GlobalValue> Info;
228
};
229

230
struct StackSafetyGlobalInfo::InfoTy {
231
  GVToSSI Info;
232
  SmallPtrSet<const AllocaInst *, 8> SafeAllocas;
233
  std::set<const Instruction *> UnsafeAccesses;
234
};
235

236
namespace {
237

238
class StackSafetyLocalAnalysis {
239
  Function &F;
240
  const DataLayout &DL;
241
  ScalarEvolution &SE;
242
  unsigned PointerSize = 0;
243

244
  const ConstantRange UnknownRange;
245

246
  /// FIXME: This function is a bandaid, it's only needed
247
  /// because this pass doesn't handle address spaces of different pointer
248
  /// sizes.
249
  ///
250
  /// \returns \p Val's SCEV as a pointer of AS zero, or nullptr if it can't be
251
  /// converted to AS 0.
252
  const SCEV *getSCEVAsPointer(Value *Val);
253

254
  ConstantRange offsetFrom(Value *Addr, Value *Base);
255
  ConstantRange getAccessRange(Value *Addr, Value *Base,
256
                               const ConstantRange &SizeRange);
257
  ConstantRange getAccessRange(Value *Addr, Value *Base, TypeSize Size);
258
  ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
259
                                           Value *Base);
260

261
  void analyzeAllUses(Value *Ptr, UseInfo<GlobalValue> &AS,
262
                      const StackLifetime &SL);
263

264

265
  bool isSafeAccess(const Use &U, AllocaInst *AI, const SCEV *AccessSize);
266
  bool isSafeAccess(const Use &U, AllocaInst *AI, Value *V);
267
  bool isSafeAccess(const Use &U, AllocaInst *AI, TypeSize AccessSize);
268

269
public:
270
  StackSafetyLocalAnalysis(Function &F, ScalarEvolution &SE)
271
      : F(F), DL(F.getDataLayout()), SE(SE),
272
        PointerSize(DL.getPointerSizeInBits()),
273
        UnknownRange(PointerSize, true) {}
274

275
  // Run the transformation on the associated function.
276
  FunctionInfo<GlobalValue> run();
277
};
278

279
const SCEV *StackSafetyLocalAnalysis::getSCEVAsPointer(Value *Val) {
280
  Type *ValTy = Val->getType();
281

282
  // We don't handle targets with multiple address spaces.
283
  if (!ValTy->isPointerTy()) {
284
    auto *PtrTy = PointerType::getUnqual(SE.getContext());
285
    return SE.getTruncateOrZeroExtend(SE.getSCEV(Val), PtrTy);
286
  }
287

288
  if (ValTy->getPointerAddressSpace() != 0)
289
    return nullptr;
290
  return SE.getSCEV(Val);
291
}
292

293
ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {
294
  if (!SE.isSCEVable(Addr->getType()) || !SE.isSCEVable(Base->getType()))
295
    return UnknownRange;
296

297
  const SCEV *AddrExp = getSCEVAsPointer(Addr);
298
  const SCEV *BaseExp = getSCEVAsPointer(Base);
299
  if (!AddrExp || !BaseExp)
300
    return UnknownRange;
301

302
  const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);
303
  if (isa<SCEVCouldNotCompute>(Diff))
304
    return UnknownRange;
305

306
  ConstantRange Offset = SE.getSignedRange(Diff);
307
  if (isUnsafe(Offset))
308
    return UnknownRange;
309
  return Offset.sextOrTrunc(PointerSize);
310
}
311

312
ConstantRange
313
StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
314
                                         const ConstantRange &SizeRange) {
315
  // Zero-size loads and stores do not access memory.
316
  if (SizeRange.isEmptySet())
317
    return ConstantRange::getEmpty(PointerSize);
318
  assert(!isUnsafe(SizeRange));
319

320
  ConstantRange Offsets = offsetFrom(Addr, Base);
321
  if (isUnsafe(Offsets))
322
    return UnknownRange;
323

324
  Offsets = addOverflowNever(Offsets, SizeRange);
325
  if (isUnsafe(Offsets))
326
    return UnknownRange;
327
  return Offsets;
328
}
329

330
ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr, Value *Base,
331
                                                       TypeSize Size) {
332
  if (Size.isScalable())
333
    return UnknownRange;
334
  APInt APSize(PointerSize, Size.getFixedValue(), true);
335
  if (APSize.isNegative())
336
    return UnknownRange;
337
  return getAccessRange(Addr, Base,
338
                        ConstantRange(APInt::getZero(PointerSize), APSize));
339
}
340

341
ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
342
    const MemIntrinsic *MI, const Use &U, Value *Base) {
343
  if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
344
    if (MTI->getRawSource() != U && MTI->getRawDest() != U)
345
      return ConstantRange::getEmpty(PointerSize);
346
  } else {
347
    if (MI->getRawDest() != U)
348
      return ConstantRange::getEmpty(PointerSize);
349
  }
350

351
  auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
352
  if (!SE.isSCEVable(MI->getLength()->getType()))
353
    return UnknownRange;
354

355
  const SCEV *Expr =
356
      SE.getTruncateOrZeroExtend(SE.getSCEV(MI->getLength()), CalculationTy);
357
  ConstantRange Sizes = SE.getSignedRange(Expr);
358
  if (!Sizes.getUpper().isStrictlyPositive() || isUnsafe(Sizes))
359
    return UnknownRange;
360
  Sizes = Sizes.sextOrTrunc(PointerSize);
361
  ConstantRange SizeRange(APInt::getZero(PointerSize), Sizes.getUpper() - 1);
362
  return getAccessRange(U, Base, SizeRange);
363
}
364

365
bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
366
                                            Value *V) {
367
  return isSafeAccess(U, AI, SE.getSCEV(V));
368
}
369

370
bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
371
                                            TypeSize TS) {
372
  if (TS.isScalable())
373
    return false;
374
  auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
375
  const SCEV *SV = SE.getConstant(CalculationTy, TS.getFixedValue());
376
  return isSafeAccess(U, AI, SV);
377
}
378

379
bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
380
                                            const SCEV *AccessSize) {
381

382
  if (!AI)
383
    return true; // This only judges whether it is a safe *stack* access.
384
  if (isa<SCEVCouldNotCompute>(AccessSize))
385
    return false;
386

387
  const auto *I = cast<Instruction>(U.getUser());
388

389
  const SCEV *AddrExp = getSCEVAsPointer(U.get());
390
  const SCEV *BaseExp = getSCEVAsPointer(AI);
391
  if (!AddrExp || !BaseExp)
392
    return false;
393

394
  const SCEV *Diff = SE.getMinusSCEV(AddrExp, BaseExp);
395
  if (isa<SCEVCouldNotCompute>(Diff))
396
    return false;
397

398
  auto Size = getStaticAllocaSizeRange(*AI);
399

400
  auto *CalculationTy = IntegerType::getIntNTy(SE.getContext(), PointerSize);
401
  auto ToDiffTy = [&](const SCEV *V) {
402
    return SE.getTruncateOrZeroExtend(V, CalculationTy);
403
  };
404
  const SCEV *Min = ToDiffTy(SE.getConstant(Size.getLower()));
405
  const SCEV *Max = SE.getMinusSCEV(ToDiffTy(SE.getConstant(Size.getUpper())),
406
                                    ToDiffTy(AccessSize));
407
  return SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SGE, Diff, Min, I)
408
             .value_or(false) &&
409
         SE.evaluatePredicateAt(ICmpInst::Predicate::ICMP_SLE, Diff, Max, I)
410
             .value_or(false);
411
}
412

413
/// The function analyzes all local uses of Ptr (alloca or argument) and
414
/// calculates local access range and all function calls where it was used.
415
void StackSafetyLocalAnalysis::analyzeAllUses(Value *Ptr,
416
                                              UseInfo<GlobalValue> &US,
417
                                              const StackLifetime &SL) {
418
  SmallPtrSet<const Value *, 16> Visited;
419
  SmallVector<const Value *, 8> WorkList;
420
  WorkList.push_back(Ptr);
421
  AllocaInst *AI = dyn_cast<AllocaInst>(Ptr);
422

423
  // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
424
  while (!WorkList.empty()) {
425
    const Value *V = WorkList.pop_back_val();
426
    for (const Use &UI : V->uses()) {
427
      const auto *I = cast<Instruction>(UI.getUser());
428
      if (!SL.isReachable(I))
429
        continue;
430

431
      assert(V == UI.get());
432

433
      auto RecordStore = [&](const Value* StoredVal) {
434
        if (V == StoredVal) {
435
          // Stored the pointer - conservatively assume it may be unsafe.
436
          US.addRange(I, UnknownRange, /*IsSafe=*/false);
437
          return;
438
        }
439
        if (AI && !SL.isAliveAfter(AI, I)) {
440
          US.addRange(I, UnknownRange, /*IsSafe=*/false);
441
          return;
442
        }
443
        auto TypeSize = DL.getTypeStoreSize(StoredVal->getType());
444
        auto AccessRange = getAccessRange(UI, Ptr, TypeSize);
445
        bool Safe = isSafeAccess(UI, AI, TypeSize);
446
        US.addRange(I, AccessRange, Safe);
447
        return;
448
      };
449

450
      switch (I->getOpcode()) {
451
      case Instruction::Load: {
452
        if (AI && !SL.isAliveAfter(AI, I)) {
453
          US.addRange(I, UnknownRange, /*IsSafe=*/false);
454
          break;
455
        }
456
        auto TypeSize = DL.getTypeStoreSize(I->getType());
457
        auto AccessRange = getAccessRange(UI, Ptr, TypeSize);
458
        bool Safe = isSafeAccess(UI, AI, TypeSize);
459
        US.addRange(I, AccessRange, Safe);
460
        break;
461
      }
462

463
      case Instruction::VAArg:
464
        // "va-arg" from a pointer is safe.
465
        break;
466
      case Instruction::Store:
467
        RecordStore(cast<StoreInst>(I)->getValueOperand());
468
        break;
469
      case Instruction::AtomicCmpXchg:
470
        RecordStore(cast<AtomicCmpXchgInst>(I)->getNewValOperand());
471
        break;
472
      case Instruction::AtomicRMW:
473
        RecordStore(cast<AtomicRMWInst>(I)->getValOperand());
474
        break;
475

476
      case Instruction::Ret:
477
        // Information leak.
478
        // FIXME: Process parameters correctly. This is a leak only if we return
479
        // alloca.
480
        US.addRange(I, UnknownRange, /*IsSafe=*/false);
481
        break;
482

483
      case Instruction::Call:
484
      case Instruction::Invoke: {
485
        if (I->isLifetimeStartOrEnd())
486
          break;
487

488
        if (AI && !SL.isAliveAfter(AI, I)) {
489
          US.addRange(I, UnknownRange, /*IsSafe=*/false);
490
          break;
491
        }
492
        if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
493
          auto AccessRange = getMemIntrinsicAccessRange(MI, UI, Ptr);
494
          bool Safe = false;
495
          if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
496
            if (MTI->getRawSource() != UI && MTI->getRawDest() != UI)
497
              Safe = true;
498
          } else if (MI->getRawDest() != UI) {
499
            Safe = true;
500
          }
501
          Safe = Safe || isSafeAccess(UI, AI, MI->getLength());
502
          US.addRange(I, AccessRange, Safe);
503
          break;
504
        }
505

506
        const auto &CB = cast<CallBase>(*I);
507
        if (CB.getReturnedArgOperand() == V) {
508
          if (Visited.insert(I).second)
509
            WorkList.push_back(cast<const Instruction>(I));
510
        }
511

512
        if (!CB.isArgOperand(&UI)) {
513
          US.addRange(I, UnknownRange, /*IsSafe=*/false);
514
          break;
515
        }
516

517
        unsigned ArgNo = CB.getArgOperandNo(&UI);
518
        if (CB.isByValArgument(ArgNo)) {
519
          auto TypeSize = DL.getTypeStoreSize(CB.getParamByValType(ArgNo));
520
          auto AccessRange = getAccessRange(UI, Ptr, TypeSize);
521
          bool Safe = isSafeAccess(UI, AI, TypeSize);
522
          US.addRange(I, AccessRange, Safe);
523
          break;
524
        }
525

526
        // FIXME: consult devirt?
527
        // Do not follow aliases, otherwise we could inadvertently follow
528
        // dso_preemptable aliases or aliases with interposable linkage.
529
        const GlobalValue *Callee =
530
            dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
531
        if (!Callee) {
532
          US.addRange(I, UnknownRange, /*IsSafe=*/false);
533
          break;
534
        }
535

536
        assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
537
        ConstantRange Offsets = offsetFrom(UI, Ptr);
538
        auto Insert =
539
            US.Calls.emplace(CallInfo<GlobalValue>(Callee, ArgNo), Offsets);
540
        if (!Insert.second)
541
          Insert.first->second = Insert.first->second.unionWith(Offsets);
542
        break;
543
      }
544

545
      default:
546
        if (Visited.insert(I).second)
547
          WorkList.push_back(cast<const Instruction>(I));
548
      }
549
    }
550
  }
551
}
552

553
FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() {
554
  FunctionInfo<GlobalValue> Info;
555
  assert(!F.isDeclaration() &&
556
         "Can't run StackSafety on a function declaration");
557

558
  LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
559

560
  SmallVector<AllocaInst *, 64> Allocas;
561
  for (auto &I : instructions(F))
562
    if (auto *AI = dyn_cast<AllocaInst>(&I))
563
      Allocas.push_back(AI);
564
  StackLifetime SL(F, Allocas, StackLifetime::LivenessType::Must);
565
  SL.run();
566

567
  for (auto *AI : Allocas) {
568
    auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second;
569
    analyzeAllUses(AI, UI, SL);
570
  }
571

572
  for (Argument &A : F.args()) {
573
    // Non pointers and bypass arguments are not going to be used in any global
574
    // processing.
575
    if (A.getType()->isPointerTy() && !A.hasByValAttr()) {
576
      auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second;
577
      analyzeAllUses(&A, UI, SL);
578
    }
579
  }
580

581
  LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F));
582
  LLVM_DEBUG(dbgs() << "\n[StackSafety] done\n");
583
  return Info;
584
}
585

586
template <typename CalleeTy> class StackSafetyDataFlowAnalysis {
587
  using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>;
588

589
  FunctionMap Functions;
590
  const ConstantRange UnknownRange;
591

592
  // Callee-to-Caller multimap.
593
  DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers;
594
  SetVector<const CalleeTy *> WorkList;
595

596
  bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet);
597
  void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS);
598
  void updateOneNode(const CalleeTy *Callee) {
599
    updateOneNode(Callee, Functions.find(Callee)->second);
600
  }
601
  void updateAllNodes() {
602
    for (auto &F : Functions)
603
      updateOneNode(F.first, F.second);
604
  }
605
  void runDataFlow();
606
#ifndef NDEBUG
607
  void verifyFixedPoint();
608
#endif
609

610
public:
611
  StackSafetyDataFlowAnalysis(uint32_t PointerBitWidth, FunctionMap Functions)
612
      : Functions(std::move(Functions)),
613
        UnknownRange(ConstantRange::getFull(PointerBitWidth)) {}
614

615
  const FunctionMap &run();
616

617
  ConstantRange getArgumentAccessRange(const CalleeTy *Callee, unsigned ParamNo,
618
                                       const ConstantRange &Offsets) const;
619
};
620

621
template <typename CalleeTy>
622
ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(
623
    const CalleeTy *Callee, unsigned ParamNo,
624
    const ConstantRange &Offsets) const {
625
  auto FnIt = Functions.find(Callee);
626
  // Unknown callee (outside of LTO domain or an indirect call).
627
  if (FnIt == Functions.end())
628
    return UnknownRange;
629
  auto &FS = FnIt->second;
630
  auto ParamIt = FS.Params.find(ParamNo);
631
  if (ParamIt == FS.Params.end())
632
    return UnknownRange;
633
  auto &Access = ParamIt->second.Range;
634
  if (Access.isEmptySet())
635
    return Access;
636
  if (Access.isFullSet())
637
    return UnknownRange;
638
  return addOverflowNever(Access, Offsets);
639
}
640

641
template <typename CalleeTy>
642
bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,
643
                                                         bool UpdateToFullSet) {
644
  bool Changed = false;
645
  for (auto &KV : US.Calls) {
646
    assert(!KV.second.isEmptySet() &&
647
           "Param range can't be empty-set, invalid offset range");
648

649
    ConstantRange CalleeRange =
650
        getArgumentAccessRange(KV.first.Callee, KV.first.ParamNo, KV.second);
651
    if (!US.Range.contains(CalleeRange)) {
652
      Changed = true;
653
      if (UpdateToFullSet)
654
        US.Range = UnknownRange;
655
      else
656
        US.updateRange(CalleeRange);
657
    }
658
  }
659
  return Changed;
660
}
661

662
template <typename CalleeTy>
663
void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(
664
    const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) {
665
  bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
666
  bool Changed = false;
667
  for (auto &KV : FS.Params)
668
    Changed |= updateOneUse(KV.second, UpdateToFullSet);
669

670
  if (Changed) {
671
    LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
672
                      << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS
673
                      << "\n");
674
    // Callers of this function may need updating.
675
    for (auto &CallerID : Callers[Callee])
676
      WorkList.insert(CallerID);
677

678
    ++FS.UpdateCount;
679
  }
680
}
681

682
template <typename CalleeTy>
683
void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {
684
  SmallVector<const CalleeTy *, 16> Callees;
685
  for (auto &F : Functions) {
686
    Callees.clear();
687
    auto &FS = F.second;
688
    for (auto &KV : FS.Params)
689
      for (auto &CS : KV.second.Calls)
690
        Callees.push_back(CS.first.Callee);
691

692
    llvm::sort(Callees);
693
    Callees.erase(llvm::unique(Callees), Callees.end());
694

695
    for (auto &Callee : Callees)
696
      Callers[Callee].push_back(F.first);
697
  }
698

699
  updateAllNodes();
700

701
  while (!WorkList.empty()) {
702
    const CalleeTy *Callee = WorkList.pop_back_val();
703
    updateOneNode(Callee);
704
  }
705
}
706

707
#ifndef NDEBUG
708
template <typename CalleeTy>
709
void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {
710
  WorkList.clear();
711
  updateAllNodes();
712
  assert(WorkList.empty());
713
}
714
#endif
715

716
template <typename CalleeTy>
717
const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &
718
StackSafetyDataFlowAnalysis<CalleeTy>::run() {
719
  runDataFlow();
720
  LLVM_DEBUG(verifyFixedPoint());
721
  return Functions;
722
}
723

724
FunctionSummary *findCalleeFunctionSummary(ValueInfo VI, StringRef ModuleId) {
725
  if (!VI)
726
    return nullptr;
727
  auto SummaryList = VI.getSummaryList();
728
  GlobalValueSummary* S = nullptr;
729
  for (const auto& GVS : SummaryList) {
730
    if (!GVS->isLive())
731
      continue;
732
    if (const AliasSummary *AS = dyn_cast<AliasSummary>(GVS.get()))
733
      if (!AS->hasAliasee())
734
        continue;
735
    if (!isa<FunctionSummary>(GVS->getBaseObject()))
736
      continue;
737
    if (GlobalValue::isLocalLinkage(GVS->linkage())) {
738
      if (GVS->modulePath() == ModuleId) {
739
        S = GVS.get();
740
        break;
741
      }
742
    } else if (GlobalValue::isExternalLinkage(GVS->linkage())) {
743
      if (S) {
744
        ++NumIndexCalleeMultipleExternal;
745
        return nullptr;
746
      }
747
      S = GVS.get();
748
    } else if (GlobalValue::isWeakLinkage(GVS->linkage())) {
749
      if (S) {
750
        ++NumIndexCalleeMultipleWeak;
751
        return nullptr;
752
      }
753
      S = GVS.get();
754
    } else if (GlobalValue::isAvailableExternallyLinkage(GVS->linkage()) ||
755
               GlobalValue::isLinkOnceLinkage(GVS->linkage())) {
756
      if (SummaryList.size() == 1)
757
        S = GVS.get();
758
      // According thinLTOResolvePrevailingGUID these are unlikely prevailing.
759
    } else {
760
      ++NumIndexCalleeUnhandled;
761
    }
762
  };
763
  while (S) {
764
    if (!S->isLive() || !S->isDSOLocal())
765
      return nullptr;
766
    if (FunctionSummary *FS = dyn_cast<FunctionSummary>(S))
767
      return FS;
768
    AliasSummary *AS = dyn_cast<AliasSummary>(S);
769
    if (!AS || !AS->hasAliasee())
770
      return nullptr;
771
    S = AS->getBaseObject();
772
    if (S == AS)
773
      return nullptr;
774
  }
775
  return nullptr;
776
}
777

778
const Function *findCalleeInModule(const GlobalValue *GV) {
779
  while (GV) {
780
    if (GV->isDeclaration() || GV->isInterposable() || !GV->isDSOLocal())
781
      return nullptr;
782
    if (const Function *F = dyn_cast<Function>(GV))
783
      return F;
784
    const GlobalAlias *A = dyn_cast<GlobalAlias>(GV);
785
    if (!A)
786
      return nullptr;
787
    GV = A->getAliaseeObject();
788
    if (GV == A)
789
      return nullptr;
790
  }
791
  return nullptr;
792
}
793

794
const ConstantRange *findParamAccess(const FunctionSummary &FS,
795
                                     uint32_t ParamNo) {
796
  assert(FS.isLive());
797
  assert(FS.isDSOLocal());
798
  for (const auto &PS : FS.paramAccesses())
799
    if (ParamNo == PS.ParamNo)
800
      return &PS.Use;
801
  return nullptr;
802
}
803

804
void resolveAllCalls(UseInfo<GlobalValue> &Use,
805
                     const ModuleSummaryIndex *Index) {
806
  ConstantRange FullSet(Use.Range.getBitWidth(), true);
807
  // Move Use.Calls to a temp storage and repopulate - don't use std::move as it
808
  // leaves Use.Calls in an undefined state.
809
  UseInfo<GlobalValue>::CallsTy TmpCalls;
810
  std::swap(TmpCalls, Use.Calls);
811
  for (const auto &C : TmpCalls) {
812
    const Function *F = findCalleeInModule(C.first.Callee);
813
    if (F) {
814
      Use.Calls.emplace(CallInfo<GlobalValue>(F, C.first.ParamNo), C.second);
815
      continue;
816
    }
817

818
    if (!Index)
819
      return Use.updateRange(FullSet);
820
    FunctionSummary *FS =
821
        findCalleeFunctionSummary(Index->getValueInfo(C.first.Callee->getGUID()),
822
                                  C.first.Callee->getParent()->getModuleIdentifier());
823
    ++NumModuleCalleeLookupTotal;
824
    if (!FS) {
825
      ++NumModuleCalleeLookupFailed;
826
      return Use.updateRange(FullSet);
827
    }
828
    const ConstantRange *Found = findParamAccess(*FS, C.first.ParamNo);
829
    if (!Found || Found->isFullSet())
830
      return Use.updateRange(FullSet);
831
    ConstantRange Access = Found->sextOrTrunc(Use.Range.getBitWidth());
832
    if (!Access.isEmptySet())
833
      Use.updateRange(addOverflowNever(Access, C.second));
834
  }
835
}
836

837
GVToSSI createGlobalStackSafetyInfo(
838
    std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions,
839
    const ModuleSummaryIndex *Index) {
840
  GVToSSI SSI;
841
  if (Functions.empty())
842
    return SSI;
843

844
  // FIXME: Simplify printing and remove copying here.
845
  auto Copy = Functions;
846

847
  for (auto &FnKV : Copy)
848
    for (auto &KV : FnKV.second.Params) {
849
      resolveAllCalls(KV.second, Index);
850
      if (KV.second.Range.isFullSet())
851
        KV.second.Calls.clear();
852
    }
853

854
  uint32_t PointerSize =
855
      Copy.begin()->first->getDataLayout().getPointerSizeInBits();
856
  StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy));
857

858
  for (const auto &F : SSDFA.run()) {
859
    auto FI = F.second;
860
    auto &SrcF = Functions[F.first];
861
    for (auto &KV : FI.Allocas) {
862
      auto &A = KV.second;
863
      resolveAllCalls(A, Index);
864
      for (auto &C : A.Calls) {
865
        A.updateRange(SSDFA.getArgumentAccessRange(C.first.Callee,
866
                                                   C.first.ParamNo, C.second));
867
      }
868
      // FIXME: This is needed only to preserve calls in print() results.
869
      A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;
870
    }
871
    for (auto &KV : FI.Params) {
872
      auto &P = KV.second;
873
      P.Calls = SrcF.Params.find(KV.first)->second.Calls;
874
    }
875
    SSI[F.first] = std::move(FI);
876
  }
877

878
  return SSI;
879
}
880

881
} // end anonymous namespace
882

883
StackSafetyInfo::StackSafetyInfo() = default;
884

885
StackSafetyInfo::StackSafetyInfo(Function *F,
886
                                 std::function<ScalarEvolution &()> GetSE)
887
    : F(F), GetSE(GetSE) {}
888

889
StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
890

891
StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
892

893
StackSafetyInfo::~StackSafetyInfo() = default;
894

895
const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const {
896
  if (!Info) {
897
    StackSafetyLocalAnalysis SSLA(*F, GetSE());
898
    Info.reset(new InfoTy{SSLA.run()});
899
  }
900
  return *Info;
901
}
902

903
void StackSafetyInfo::print(raw_ostream &O) const {
904
  getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
905
  O << "\n";
906
}
907

908
const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {
909
  if (!Info) {
910
    std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;
911
    for (auto &F : M->functions()) {
912
      if (!F.isDeclaration()) {
913
        auto FI = GetSSI(F).getInfo().Info;
914
        Functions.emplace(&F, std::move(FI));
915
      }
916
    }
917
    Info.reset(new InfoTy{
918
        createGlobalStackSafetyInfo(std::move(Functions), Index), {}, {}});
919

920
    for (auto &FnKV : Info->Info) {
921
      for (auto &KV : FnKV.second.Allocas) {
922
        ++NumAllocaTotal;
923
        const AllocaInst *AI = KV.first;
924
        auto AIRange = getStaticAllocaSizeRange(*AI);
925
        if (AIRange.contains(KV.second.Range)) {
926
          Info->SafeAllocas.insert(AI);
927
          ++NumAllocaStackSafe;
928
        }
929
        Info->UnsafeAccesses.insert(KV.second.UnsafeAccesses.begin(),
930
                                    KV.second.UnsafeAccesses.end());
931
      }
932
    }
933

934
    if (StackSafetyPrint)
935
      print(errs());
936
  }
937
  return *Info;
938
}
939

940
std::vector<FunctionSummary::ParamAccess>
941
StackSafetyInfo::getParamAccesses(ModuleSummaryIndex &Index) const {
942
  // Implementation transforms internal representation of parameter information
943
  // into FunctionSummary format.
944
  std::vector<FunctionSummary::ParamAccess> ParamAccesses;
945
  for (const auto &KV : getInfo().Info.Params) {
946
    auto &PS = KV.second;
947
    // Parameter accessed by any or unknown offset, represented as FullSet by
948
    // StackSafety, is handled as the parameter for which we have no
949
    // StackSafety info at all. So drop it to reduce summary size.
950
    if (PS.Range.isFullSet())
951
      continue;
952

953
    ParamAccesses.emplace_back(KV.first, PS.Range);
954
    FunctionSummary::ParamAccess &Param = ParamAccesses.back();
955

956
    Param.Calls.reserve(PS.Calls.size());
957
    for (const auto &C : PS.Calls) {
958
      // Parameter forwarded into another function by any or unknown offset
959
      // will make ParamAccess::Range as FullSet anyway. So we can drop the
960
      // entire parameter like we did above.
961
      // TODO(vitalybuka): Return already filtered parameters from getInfo().
962
      if (C.second.isFullSet()) {
963
        ParamAccesses.pop_back();
964
        break;
965
      }
966
      Param.Calls.emplace_back(C.first.ParamNo,
967
                               Index.getOrInsertValueInfo(C.first.Callee),
968
                               C.second);
969
    }
970
  }
971
  for (FunctionSummary::ParamAccess &Param : ParamAccesses) {
972
    sort(Param.Calls, [](const FunctionSummary::ParamAccess::Call &L,
973
                         const FunctionSummary::ParamAccess::Call &R) {
974
      return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
975
    });
976
  }
977
  return ParamAccesses;
978
}
979

980
StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;
981

982
StackSafetyGlobalInfo::StackSafetyGlobalInfo(
983
    Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,
984
    const ModuleSummaryIndex *Index)
985
    : M(M), GetSSI(GetSSI), Index(Index) {
986
  if (StackSafetyRun)
987
    getInfo();
988
}
989

990
StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =
991
    default;
992

993
StackSafetyGlobalInfo &
994
StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;
995

996
StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;
997

998
bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const {
999
  const auto &Info = getInfo();
1000
  return Info.SafeAllocas.count(&AI);
1001
}
1002

1003
bool StackSafetyGlobalInfo::stackAccessIsSafe(const Instruction &I) const {
1004
  const auto &Info = getInfo();
1005
  return Info.UnsafeAccesses.find(&I) == Info.UnsafeAccesses.end();
1006
}
1007

1008
void StackSafetyGlobalInfo::print(raw_ostream &O) const {
1009
  auto &SSI = getInfo().Info;
1010
  if (SSI.empty())
1011
    return;
1012
  const Module &M = *SSI.begin()->first->getParent();
1013
  for (const auto &F : M.functions()) {
1014
    if (!F.isDeclaration()) {
1015
      SSI.find(&F)->second.print(O, F.getName(), &F);
1016
      O << "    safe accesses:"
1017
        << "\n";
1018
      for (const auto &I : instructions(F)) {
1019
        const CallInst *Call = dyn_cast<CallInst>(&I);
1020
        if ((isa<StoreInst>(I) || isa<LoadInst>(I) || isa<MemIntrinsic>(I) ||
1021
             isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I) ||
1022
             (Call && Call->hasByValArgument())) &&
1023
            stackAccessIsSafe(I)) {
1024
          O << "     " << I << "\n";
1025
        }
1026
      }
1027
      O << "\n";
1028
    }
1029
  }
1030
}
1031

1032
LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); }
1033

1034
AnalysisKey StackSafetyAnalysis::Key;
1035

1036
StackSafetyInfo StackSafetyAnalysis::run(Function &F,
1037
                                         FunctionAnalysisManager &AM) {
1038
  return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
1039
    return AM.getResult<ScalarEvolutionAnalysis>(F);
1040
  });
1041
}
1042

1043
PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
1044
                                              FunctionAnalysisManager &AM) {
1045
  OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
1046
  AM.getResult<StackSafetyAnalysis>(F).print(OS);
1047
  return PreservedAnalyses::all();
1048
}
1049

1050
char StackSafetyInfoWrapperPass::ID = 0;
1051

1052
StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
1053
  initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
1054
}
1055

1056
void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1057
  AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
1058
  AU.setPreservesAll();
1059
}
1060

1061
void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
1062
  SSI.print(O);
1063
}
1064

1065
bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
1066
  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1067
  SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
1068
  return false;
1069
}
1070

1071
AnalysisKey StackSafetyGlobalAnalysis::Key;
1072

1073
StackSafetyGlobalInfo
1074
StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
1075
  // FIXME: Lookup Module Summary.
1076
  FunctionAnalysisManager &FAM =
1077
      AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1078
  return {&M,
1079
          [&FAM](Function &F) -> const StackSafetyInfo & {
1080
            return FAM.getResult<StackSafetyAnalysis>(F);
1081
          },
1082
          nullptr};
1083
}
1084

1085
PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
1086
                                                    ModuleAnalysisManager &AM) {
1087
  OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
1088
  AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS);
1089
  return PreservedAnalyses::all();
1090
}
1091

1092
char StackSafetyGlobalInfoWrapperPass::ID = 0;
1093

1094
StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
1095
    : ModulePass(ID) {
1096
  initializeStackSafetyGlobalInfoWrapperPassPass(
1097
      *PassRegistry::getPassRegistry());
1098
}
1099

1100
StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;
1101

1102
void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
1103
                                             const Module *M) const {
1104
  SSGI.print(O);
1105
}
1106

1107
void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
1108
    AnalysisUsage &AU) const {
1109
  AU.setPreservesAll();
1110
  AU.addRequired<StackSafetyInfoWrapperPass>();
1111
}
1112

1113
bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
1114
  const ModuleSummaryIndex *ImportSummary = nullptr;
1115
  if (auto *IndexWrapperPass =
1116
          getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
1117
    ImportSummary = IndexWrapperPass->getIndex();
1118

1119
  SSGI = {&M,
1120
          [this](Function &F) -> const StackSafetyInfo & {
1121
            return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
1122
          },
1123
          ImportSummary};
1124
  return false;
1125
}
1126

1127
bool llvm::needsParamAccessSummary(const Module &M) {
1128
  if (StackSafetyRun)
1129
    return true;
1130
  for (const auto &F : M.functions())
1131
    if (F.hasFnAttribute(Attribute::SanitizeMemTag))
1132
      return true;
1133
  return false;
1134
}
1135

1136
void llvm::generateParamAccessSummary(ModuleSummaryIndex &Index) {
1137
  if (!Index.hasParamAccess())
1138
    return;
1139
  const ConstantRange FullSet(FunctionSummary::ParamAccess::RangeWidth, true);
1140

1141
  auto CountParamAccesses = [&](auto &Stat) {
1142
    if (!AreStatisticsEnabled())
1143
      return;
1144
    for (auto &GVS : Index)
1145
      for (auto &GV : GVS.second.SummaryList)
1146
        if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get()))
1147
          Stat += FS->paramAccesses().size();
1148
  };
1149

1150
  CountParamAccesses(NumCombinedParamAccessesBefore);
1151

1152
  std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions;
1153

1154
  // Convert the ModuleSummaryIndex to a FunctionMap
1155
  for (auto &GVS : Index) {
1156
    for (auto &GV : GVS.second.SummaryList) {
1157
      FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get());
1158
      if (!FS || FS->paramAccesses().empty())
1159
        continue;
1160
      if (FS->isLive() && FS->isDSOLocal()) {
1161
        FunctionInfo<FunctionSummary> FI;
1162
        for (const auto &PS : FS->paramAccesses()) {
1163
          auto &US =
1164
              FI.Params
1165
                  .emplace(PS.ParamNo, FunctionSummary::ParamAccess::RangeWidth)
1166
                  .first->second;
1167
          US.Range = PS.Use;
1168
          for (const auto &Call : PS.Calls) {
1169
            assert(!Call.Offsets.isFullSet());
1170
            FunctionSummary *S =
1171
                findCalleeFunctionSummary(Call.Callee, FS->modulePath());
1172
            ++NumCombinedCalleeLookupTotal;
1173
            if (!S) {
1174
              ++NumCombinedCalleeLookupFailed;
1175
              US.Range = FullSet;
1176
              US.Calls.clear();
1177
              break;
1178
            }
1179
            US.Calls.emplace(CallInfo<FunctionSummary>(S, Call.ParamNo),
1180
                             Call.Offsets);
1181
          }
1182
        }
1183
        Functions.emplace(FS, std::move(FI));
1184
      }
1185
      // Reset data for all summaries. Alive and DSO local will be set back from
1186
      // of data flow results below. Anything else will not be accessed
1187
      // by ThinLTO backend, so we can save on bitcode size.
1188
      FS->setParamAccesses({});
1189
    }
1190
  }
1191
  NumCombinedDataFlowNodes += Functions.size();
1192
  StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA(
1193
      FunctionSummary::ParamAccess::RangeWidth, std::move(Functions));
1194
  for (const auto &KV : SSDFA.run()) {
1195
    std::vector<FunctionSummary::ParamAccess> NewParams;
1196
    NewParams.reserve(KV.second.Params.size());
1197
    for (const auto &Param : KV.second.Params) {
1198
      // It's not needed as FullSet is processed the same as a missing value.
1199
      if (Param.second.Range.isFullSet())
1200
        continue;
1201
      NewParams.emplace_back();
1202
      FunctionSummary::ParamAccess &New = NewParams.back();
1203
      New.ParamNo = Param.first;
1204
      New.Use = Param.second.Range; // Only range is needed.
1205
    }
1206
    const_cast<FunctionSummary *>(KV.first)->setParamAccesses(
1207
        std::move(NewParams));
1208
  }
1209

1210
  CountParamAccesses(NumCombinedParamAccessesAfter);
1211
}
1212

1213
static const char LocalPassArg[] = "stack-safety-local";
1214
static const char LocalPassName[] = "Stack Safety Local Analysis";
1215
INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
1216
                      false, true)
1217
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1218
INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
1219
                    false, true)
1220

1221
static const char GlobalPassName[] = "Stack Safety Analysis";
1222
INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
1223
                      GlobalPassName, false, true)
1224
INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
1225
INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass)
1226
INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
1227
                    GlobalPassName, false, true)
1228