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
  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.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));
 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   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
 261 public:
 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
 271 ConstantRange StackSafetyLocalAnalysis::offsetFrom(Value *Addr, Value *Base) {
 272   if (!SE.isSCEVable(Addr->getType()) || !SE.isSCEVable(Base->getType()))
 273     return UnknownRange;
 274
 275   auto *PtrTy = PointerType::getUnqual(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
 288 ConstantRange
 289 StackSafetyLocalAnalysis::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));
 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
 306 ConstantRange 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
 317 ConstantRange 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().isStrictlyPositive() || 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
 341 bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
 342                                             Value *V) {
 343   return isSafeAccess(U, AI, SE.getSCEV(V));
 344 }
 345
 346 bool 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
 355 bool StackSafetyLocalAnalysis::isSafeAccess(const Use &U, AllocaInst *AI,
 356                                             const SCEV *AccessSize) {
 357
 358   if (!AI)
 359     return true; // This only judges whether it is a safe *stack* access.
 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 = PointerType::getUnqual(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.
 393 void 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());
 410
 411       auto RecordStore = [&](const Value* StoredVal) {
 412         if (V == StoredVal) {
 413           // Stored the pointer - conservatively assume it may be unsafe.
 414           US.addRange(I, UnknownRange, /*IsSafe=*/false);
 415           return;
 416         }
 417         if (AI && !SL.isAliveAfter(AI, I)) {
 418           US.addRange(I, UnknownRange, /*IsSafe=*/false);
 419           return;
 420         }
 421         auto TypeSize = DL.getTypeStoreSize(StoredVal->getType());
 422         auto AccessRange = getAccessRange(UI, Ptr, TypeSize);
 423         bool Safe = isSafeAccess(UI, AI, TypeSize);
 424         US.addRange(I, AccessRange, Safe);
 425         return;
 426       };
 427
 428       switch (I->getOpcode()) {
 429       case Instruction::Load: {
 430         if (AI && !SL.isAliveAfter(AI, I)) {
 431           US.addRange(I, UnknownRange, /*IsSafe=*/false);
 432           break;
 433         }
 434         auto TypeSize = DL.getTypeStoreSize(I->getType());
 435         auto AccessRange = getAccessRange(UI, Ptr, TypeSize);
 436         bool Safe = isSafeAccess(UI, AI, TypeSize);
 437         US.addRange(I, AccessRange, Safe);
 438         break;
 439       }
 440
 441       case Instruction::VAArg:
 442         // "va-arg" from a pointer is safe.
 443         break;
 444       case Instruction::Store:
 445         RecordStore(cast<StoreInst>(I)->getValueOperand());
 446         break;
 447       case Instruction::AtomicCmpXchg:
 448         RecordStore(cast<AtomicCmpXchgInst>(I)->getNewValOperand());
 449         break;
 450       case Instruction::AtomicRMW:
 451         RecordStore(cast<AtomicRMWInst>(I)->getValOperand());
 452         break;
 453
 454       case Instruction::Ret:
 455         // Information leak.
 456         // FIXME: Process parameters correctly. This is a leak only if we return
 457         // alloca.
 458         US.addRange(I, UnknownRange, /*IsSafe=*/false);
 459         break;
 460
 461       case Instruction::Call:
 462       case Instruction::Invoke: {
 463         if (I->isLifetimeStartOrEnd())
 464           break;
 465
 466         if (AI && !SL.isAliveAfter(AI, I)) {
 467           US.addRange(I, UnknownRange, /*IsSafe=*/false);
 468           break;
 469         }
 470         if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
 471           auto AccessRange = getMemIntrinsicAccessRange(MI, UI, Ptr);
 472           bool Safe = false;
 473           if (const auto *MTI = dyn_cast<MemTransferInst>(MI)) {
 474             if (MTI->getRawSource() != UI && MTI->getRawDest() != UI)
 475               Safe = true;
 476           } else if (MI->getRawDest() != UI) {
 477             Safe = true;
 478           }
 479           Safe = Safe || isSafeAccess(UI, AI, MI->getLength());
 480           US.addRange(I, AccessRange, Safe);
 481           break;
 482         }
 483
 484         const auto &CB = cast<CallBase>(*I);
 485         if (CB.getReturnedArgOperand() == V) {
 486           if (Visited.insert(I).second)
 487             WorkList.push_back(cast<const Instruction>(I));
 488         }
 489
 490         if (!CB.isArgOperand(&UI)) {
 491           US.addRange(I, UnknownRange, /*IsSafe=*/false);
 492           break;
 493         }
 494
 495         unsigned ArgNo = CB.getArgOperandNo(&UI);
 496         if (CB.isByValArgument(ArgNo)) {
 497           auto TypeSize = DL.getTypeStoreSize(CB.getParamByValType(ArgNo));
 498           auto AccessRange = getAccessRange(UI, Ptr, TypeSize);
 499           bool Safe = isSafeAccess(UI, AI, TypeSize);
 500           US.addRange(I, AccessRange, Safe);
 501           break;
 502         }
 503
 504         // FIXME: consult devirt?
 505         // Do not follow aliases, otherwise we could inadvertently follow
 506         // dso_preemptable aliases or aliases with interposable linkage.
 507         const GlobalValue *Callee =
 508             dyn_cast<GlobalValue>(CB.getCalledOperand()->stripPointerCasts());
 509         if (!Callee) {
 510           US.addRange(I, UnknownRange, /*IsSafe=*/false);
 511           break;
 512         }
 513
 514         assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
 515         ConstantRange Offsets = offsetFrom(UI, Ptr);
 516         auto Insert =
 517             US.Calls.emplace(CallInfo<GlobalValue>(Callee, ArgNo), Offsets);
 518         if (!Insert.second)
 519           Insert.first->second = Insert.first->second.unionWith(Offsets);
 520         break;
 521       }
 522
 523       default:
 524         if (Visited.insert(I).second)
 525           WorkList.push_back(cast<const Instruction>(I));
 526       }
 527     }
 528   }
 529 }
 530
 531 FunctionInfo<GlobalValue> StackSafetyLocalAnalysis::run() {
 532   FunctionInfo<GlobalValue> Info;
 533   assert(!F.isDeclaration() &&
 534          "Can't run StackSafety on a function declaration");
 535
 536   LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
 537
 538   SmallVector<AllocaInst *, 64> Allocas;
 539   for (auto &I : instructions(F))
 540     if (auto *AI = dyn_cast<AllocaInst>(&I))
 541       Allocas.push_back(AI);
 542   StackLifetime SL(F, Allocas, StackLifetime::LivenessType::Must);
 543   SL.run();
 544
 545   for (auto *AI : Allocas) {
 546     auto &UI = Info.Allocas.emplace(AI, PointerSize).first->second;
 547     analyzeAllUses(AI, UI, SL);
 548   }
 549
 550   for (Argument &A : F.args()) {
 551     // Non pointers and bypass arguments are not going to be used in any global
 552     // processing.
 553     if (A.getType()->isPointerTy() && !A.hasByValAttr()) {
 554       auto &UI = Info.Params.emplace(A.getArgNo(), PointerSize).first->second;
 555       analyzeAllUses(&A, UI, SL);
 556     }
 557   }
 558
 559   LLVM_DEBUG(Info.print(dbgs(), F.getName(), &F));
 560   LLVM_DEBUG(dbgs() << "\n[StackSafety] done\n");
 561   return Info;
 562 }
 563
 564 template <typename CalleeTy> class StackSafetyDataFlowAnalysis {
 565   using FunctionMap = std::map<const CalleeTy *, FunctionInfo<CalleeTy>>;
 566
 567   FunctionMap Functions;
 568   const ConstantRange UnknownRange;
 569
 570   // Callee-to-Caller multimap.
 571   DenseMap<const CalleeTy *, SmallVector<const CalleeTy *, 4>> Callers;
 572   SetVector<const CalleeTy *> WorkList;
 573
 574   bool updateOneUse(UseInfo<CalleeTy> &US, bool UpdateToFullSet);
 575   void updateOneNode(const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS);
 576   void updateOneNode(const CalleeTy *Callee) {
 577     updateOneNode(Callee, Functions.find(Callee)->second);
 578   }
 579   void updateAllNodes() {
 580     for (auto &F : Functions)
 581       updateOneNode(F.first, F.second);
 582   }
 583   void runDataFlow();
 584 #ifndef NDEBUG
 585   void verifyFixedPoint();
 586 #endif
 587
 588 public:
 589   StackSafetyDataFlowAnalysis(uint32_t PointerBitWidth, FunctionMap Functions)
 590       : Functions(std::move(Functions)),
 591         UnknownRange(ConstantRange::getFull(PointerBitWidth)) {}
 592
 593   const FunctionMap &run();
 594
 595   ConstantRange getArgumentAccessRange(const CalleeTy *Callee, unsigned ParamNo,
 596                                        const ConstantRange &Offsets) const;
 597 };
 598
 599 template <typename CalleeTy>
 600 ConstantRange StackSafetyDataFlowAnalysis<CalleeTy>::getArgumentAccessRange(
 601     const CalleeTy *Callee, unsigned ParamNo,
 602     const ConstantRange &Offsets) const {
 603   auto FnIt = Functions.find(Callee);
 604   // Unknown callee (outside of LTO domain or an indirect call).
 605   if (FnIt == Functions.end())
 606     return UnknownRange;
 607   auto &FS = FnIt->second;
 608   auto ParamIt = FS.Params.find(ParamNo);
 609   if (ParamIt == FS.Params.end())
 610     return UnknownRange;
 611   auto &Access = ParamIt->second.Range;
 612   if (Access.isEmptySet())
 613     return Access;
 614   if (Access.isFullSet())
 615     return UnknownRange;
 616   return addOverflowNever(Access, Offsets);
 617 }
 618
 619 template <typename CalleeTy>
 620 bool StackSafetyDataFlowAnalysis<CalleeTy>::updateOneUse(UseInfo<CalleeTy> &US,
 621                                                          bool UpdateToFullSet) {
 622   bool Changed = false;
 623   for (auto &KV : US.Calls) {
 624     assert(!KV.second.isEmptySet() &&
 625            "Param range can't be empty-set, invalid offset range");
 626
 627     ConstantRange CalleeRange =
 628         getArgumentAccessRange(KV.first.Callee, KV.first.ParamNo, KV.second);
 629     if (!US.Range.contains(CalleeRange)) {
 630       Changed = true;
 631       if (UpdateToFullSet)
 632         US.Range = UnknownRange;
 633       else
 634         US.updateRange(CalleeRange);
 635     }
 636   }
 637   return Changed;
 638 }
 639
 640 template <typename CalleeTy>
 641 void StackSafetyDataFlowAnalysis<CalleeTy>::updateOneNode(
 642     const CalleeTy *Callee, FunctionInfo<CalleeTy> &FS) {
 643   bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
 644   bool Changed = false;
 645   for (auto &KV : FS.Params)
 646     Changed |= updateOneUse(KV.second, UpdateToFullSet);
 647
 648   if (Changed) {
 649     LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
 650                       << (UpdateToFullSet ? ", full-set" : "") << "] " << &FS
 651                       << "\n");
 652     // Callers of this function may need updating.
 653     for (auto &CallerID : Callers[Callee])
 654       WorkList.insert(CallerID);
 655
 656     ++FS.UpdateCount;
 657   }
 658 }
 659
 660 template <typename CalleeTy>
 661 void StackSafetyDataFlowAnalysis<CalleeTy>::runDataFlow() {
 662   SmallVector<const CalleeTy *, 16> Callees;
 663   for (auto &F : Functions) {
 664     Callees.clear();
 665     auto &FS = F.second;
 666     for (auto &KV : FS.Params)
 667       for (auto &CS : KV.second.Calls)
 668         Callees.push_back(CS.first.Callee);
 669
 670     llvm::sort(Callees);
 671     Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
 672
 673     for (auto &Callee : Callees)
 674       Callers[Callee].push_back(F.first);
 675   }
 676
 677   updateAllNodes();
 678
 679   while (!WorkList.empty()) {
 680     const CalleeTy *Callee = WorkList.pop_back_val();
 681     updateOneNode(Callee);
 682   }
 683 }
 684
 685 #ifndef NDEBUG
 686 template <typename CalleeTy>
 687 void StackSafetyDataFlowAnalysis<CalleeTy>::verifyFixedPoint() {
 688   WorkList.clear();
 689   updateAllNodes();
 690   assert(WorkList.empty());
 691 }
 692 #endif
 693
 694 template <typename CalleeTy>
 695 const typename StackSafetyDataFlowAnalysis<CalleeTy>::FunctionMap &
 696 StackSafetyDataFlowAnalysis<CalleeTy>::run() {
 697   runDataFlow();
 698   LLVM_DEBUG(verifyFixedPoint());
 699   return Functions;
 700 }
 701
 702 FunctionSummary *findCalleeFunctionSummary(ValueInfo VI, StringRef ModuleId) {
 703   if (!VI)
 704     return nullptr;
 705   auto SummaryList = VI.getSummaryList();
 706   GlobalValueSummary* S = nullptr;
 707   for (const auto& GVS : SummaryList) {
 708     if (!GVS->isLive())
 709       continue;
 710     if (const AliasSummary *AS = dyn_cast<AliasSummary>(GVS.get()))
 711       if (!AS->hasAliasee())
 712         continue;
 713     if (!isa<FunctionSummary>(GVS->getBaseObject()))
 714       continue;
 715     if (GlobalValue::isLocalLinkage(GVS->linkage())) {
 716       if (GVS->modulePath() == ModuleId) {
 717         S = GVS.get();
 718         break;
 719       }
 720     } else if (GlobalValue::isExternalLinkage(GVS->linkage())) {
 721       if (S) {
 722         ++NumIndexCalleeMultipleExternal;
 723         return nullptr;
 724       }
 725       S = GVS.get();
 726     } else if (GlobalValue::isWeakLinkage(GVS->linkage())) {
 727       if (S) {
 728         ++NumIndexCalleeMultipleWeak;
 729         return nullptr;
 730       }
 731       S = GVS.get();
 732     } else if (GlobalValue::isAvailableExternallyLinkage(GVS->linkage()) ||
 733                GlobalValue::isLinkOnceLinkage(GVS->linkage())) {
 734       if (SummaryList.size() == 1)
 735         S = GVS.get();
 736       // According thinLTOResolvePrevailingGUID these are unlikely prevailing.
 737     } else {
 738       ++NumIndexCalleeUnhandled;
 739     }
 740   };
 741   while (S) {
 742     if (!S->isLive() || !S->isDSOLocal())
 743       return nullptr;
 744     if (FunctionSummary *FS = dyn_cast<FunctionSummary>(S))
 745       return FS;
 746     AliasSummary *AS = dyn_cast<AliasSummary>(S);
 747     if (!AS || !AS->hasAliasee())
 748       return nullptr;
 749     S = AS->getBaseObject();
 750     if (S == AS)
 751       return nullptr;
 752   }
 753   return nullptr;
 754 }
 755
 756 const Function *findCalleeInModule(const GlobalValue *GV) {
 757   while (GV) {
 758     if (GV->isDeclaration() || GV->isInterposable() || !GV->isDSOLocal())
 759       return nullptr;
 760     if (const Function *F = dyn_cast<Function>(GV))
 761       return F;
 762     const GlobalAlias *A = dyn_cast<GlobalAlias>(GV);
 763     if (!A)
 764       return nullptr;
 765     GV = A->getAliaseeObject();
 766     if (GV == A)
 767       return nullptr;
 768   }
 769   return nullptr;
 770 }
 771
 772 const ConstantRange *findParamAccess(const FunctionSummary &FS,
 773                                      uint32_t ParamNo) {
 774   assert(FS.isLive());
 775   assert(FS.isDSOLocal());
 776   for (const auto &PS : FS.paramAccesses())
 777     if (ParamNo == PS.ParamNo)
 778       return &PS.Use;
 779   return nullptr;
 780 }
 781
 782 void resolveAllCalls(UseInfo<GlobalValue> &Use,
 783                      const ModuleSummaryIndex *Index) {
 784   ConstantRange FullSet(Use.Range.getBitWidth(), true);
 785   // Move Use.Calls to a temp storage and repopulate - don't use std::move as it
 786   // leaves Use.Calls in an undefined state.
 787   UseInfo<GlobalValue>::CallsTy TmpCalls;
 788   std::swap(TmpCalls, Use.Calls);
 789   for (const auto &C : TmpCalls) {
 790     const Function *F = findCalleeInModule(C.first.Callee);
 791     if (F) {
 792       Use.Calls.emplace(CallInfo<GlobalValue>(F, C.first.ParamNo), C.second);
 793       continue;
 794     }
 795
 796     if (!Index)
 797       return Use.updateRange(FullSet);
 798     FunctionSummary *FS =
 799         findCalleeFunctionSummary(Index->getValueInfo(C.first.Callee->getGUID()),
 800                                   C.first.Callee->getParent()->getModuleIdentifier());
 801     ++NumModuleCalleeLookupTotal;
 802     if (!FS) {
 803       ++NumModuleCalleeLookupFailed;
 804       return Use.updateRange(FullSet);
 805     }
 806     const ConstantRange *Found = findParamAccess(*FS, C.first.ParamNo);
 807     if (!Found || Found->isFullSet())
 808       return Use.updateRange(FullSet);
 809     ConstantRange Access = Found->sextOrTrunc(Use.Range.getBitWidth());
 810     if (!Access.isEmptySet())
 811       Use.updateRange(addOverflowNever(Access, C.second));
 812   }
 813 }
 814
 815 GVToSSI createGlobalStackSafetyInfo(
 816     std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions,
 817     const ModuleSummaryIndex *Index) {
 818   GVToSSI SSI;
 819   if (Functions.empty())
 820     return SSI;
 821
 822   // FIXME: Simplify printing and remove copying here.
 823   auto Copy = Functions;
 824
 825   for (auto &FnKV : Copy)
 826     for (auto &KV : FnKV.second.Params) {
 827       resolveAllCalls(KV.second, Index);
 828       if (KV.second.Range.isFullSet())
 829         KV.second.Calls.clear();
 830     }
 831
 832   uint32_t PointerSize =
 833       Copy.begin()->first->getParent()->getDataLayout().getPointerSizeInBits();
 834   StackSafetyDataFlowAnalysis<GlobalValue> SSDFA(PointerSize, std::move(Copy));
 835
 836   for (const auto &F : SSDFA.run()) {
 837     auto FI = F.second;
 838     auto &SrcF = Functions[F.first];
 839     for (auto &KV : FI.Allocas) {
 840       auto &A = KV.second;
 841       resolveAllCalls(A, Index);
 842       for (auto &C : A.Calls) {
 843         A.updateRange(SSDFA.getArgumentAccessRange(C.first.Callee,
 844                                                    C.first.ParamNo, C.second));
 845       }
 846       // FIXME: This is needed only to preserve calls in print() results.
 847       A.Calls = SrcF.Allocas.find(KV.first)->second.Calls;
 848     }
 849     for (auto &KV : FI.Params) {
 850       auto &P = KV.second;
 851       P.Calls = SrcF.Params.find(KV.first)->second.Calls;
 852     }
 853     SSI[F.first] = std::move(FI);
 854   }
 855
 856   return SSI;
 857 }
 858
 859 } // end anonymous namespace
 860
 861 StackSafetyInfo::StackSafetyInfo() = default;
 862
 863 StackSafetyInfo::StackSafetyInfo(Function *F,
 864                                  std::function<ScalarEvolution &()> GetSE)
 865     : F(F), GetSE(GetSE) {}
 866
 867 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
 868
 869 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
 870
 871 StackSafetyInfo::~StackSafetyInfo() = default;
 872
 873 const StackSafetyInfo::InfoTy &StackSafetyInfo::getInfo() const {
 874   if (!Info) {
 875     StackSafetyLocalAnalysis SSLA(*F, GetSE());
 876     Info.reset(new InfoTy{SSLA.run()});
 877   }
 878   return *Info;
 879 }
 880
 881 void StackSafetyInfo::print(raw_ostream &O) const {
 882   getInfo().Info.print(O, F->getName(), dyn_cast<Function>(F));
 883   O << "\n";
 884 }
 885
 886 const StackSafetyGlobalInfo::InfoTy &StackSafetyGlobalInfo::getInfo() const {
 887   if (!Info) {
 888     std::map<const GlobalValue *, FunctionInfo<GlobalValue>> Functions;
 889     for (auto &F : M->functions()) {
 890       if (!F.isDeclaration()) {
 891         auto FI = GetSSI(F).getInfo().Info;
 892         Functions.emplace(&F, std::move(FI));
 893       }
 894     }
 895     Info.reset(new InfoTy{
 896         createGlobalStackSafetyInfo(std::move(Functions), Index), {}, {}});
 897
 898     for (auto &FnKV : Info->Info) {
 899       for (auto &KV : FnKV.second.Allocas) {
 900         ++NumAllocaTotal;
 901         const AllocaInst *AI = KV.first;
 902         auto AIRange = getStaticAllocaSizeRange(*AI);
 903         if (AIRange.contains(KV.second.Range)) {
 904           Info->SafeAllocas.insert(AI);
 905           ++NumAllocaStackSafe;
 906         }
 907         Info->UnsafeAccesses.insert(KV.second.UnsafeAccesses.begin(),
 908                                     KV.second.UnsafeAccesses.end());
 909       }
 910     }
 911
 912     if (StackSafetyPrint)
 913       print(errs());
 914   }
 915   return *Info;
 916 }
 917
 918 std::vector<FunctionSummary::ParamAccess>
 919 StackSafetyInfo::getParamAccesses(ModuleSummaryIndex &Index) const {
 920   // Implementation transforms internal representation of parameter information
 921   // into FunctionSummary format.
 922   std::vector<FunctionSummary::ParamAccess> ParamAccesses;
 923   for (const auto &KV : getInfo().Info.Params) {
 924     auto &PS = KV.second;
 925     // Parameter accessed by any or unknown offset, represented as FullSet by
 926     // StackSafety, is handled as the parameter for which we have no
 927     // StackSafety info at all. So drop it to reduce summary size.
 928     if (PS.Range.isFullSet())
 929       continue;
 930
 931     ParamAccesses.emplace_back(KV.first, PS.Range);
 932     FunctionSummary::ParamAccess &Param = ParamAccesses.back();
 933
 934     Param.Calls.reserve(PS.Calls.size());
 935     for (const auto &C : PS.Calls) {
 936       // Parameter forwarded into another function by any or unknown offset
 937       // will make ParamAccess::Range as FullSet anyway. So we can drop the
 938       // entire parameter like we did above.
 939       // TODO(vitalybuka): Return already filtered parameters from getInfo().
 940       if (C.second.isFullSet()) {
 941         ParamAccesses.pop_back();
 942         break;
 943       }
 944       Param.Calls.emplace_back(C.first.ParamNo,
 945                                Index.getOrInsertValueInfo(C.first.Callee),
 946                                C.second);
 947     }
 948   }
 949   for (FunctionSummary::ParamAccess &Param : ParamAccesses) {
 950     sort(Param.Calls, [](const FunctionSummary::ParamAccess::Call &L,
 951                          const FunctionSummary::ParamAccess::Call &R) {
 952       return std::tie(L.ParamNo, L.Callee) < std::tie(R.ParamNo, R.Callee);
 953     });
 954   }
 955   return ParamAccesses;
 956 }
 957
 958 StackSafetyGlobalInfo::StackSafetyGlobalInfo() = default;
 959
 960 StackSafetyGlobalInfo::StackSafetyGlobalInfo(
 961     Module *M, std::function<const StackSafetyInfo &(Function &F)> GetSSI,
 962     const ModuleSummaryIndex *Index)
 963     : M(M), GetSSI(GetSSI), Index(Index) {
 964   if (StackSafetyRun)
 965     getInfo();
 966 }
 967
 968 StackSafetyGlobalInfo::StackSafetyGlobalInfo(StackSafetyGlobalInfo &&) =
 969     default;
 970
 971 StackSafetyGlobalInfo &
 972 StackSafetyGlobalInfo::operator=(StackSafetyGlobalInfo &&) = default;
 973
 974 StackSafetyGlobalInfo::~StackSafetyGlobalInfo() = default;
 975
 976 bool StackSafetyGlobalInfo::isSafe(const AllocaInst &AI) const {
 977   const auto &Info = getInfo();
 978   return Info.SafeAllocas.count(&AI);
 979 }
 980
 981 bool StackSafetyGlobalInfo::stackAccessIsSafe(const Instruction &I) const {
 982   const auto &Info = getInfo();
 983   return Info.UnsafeAccesses.find(&I) == Info.UnsafeAccesses.end();
 984 }
 985
 986 void StackSafetyGlobalInfo::print(raw_ostream &O) const {
 987   auto &SSI = getInfo().Info;
 988   if (SSI.empty())
 989     return;
 990   const Module &M = *SSI.begin()->first->getParent();
 991   for (const auto &F : M.functions()) {
 992     if (!F.isDeclaration()) {
 993       SSI.find(&F)->second.print(O, F.getName(), &F);
 994       O << "    safe accesses:"
 995         << "\n";
 996       for (const auto &I : instructions(F)) {
 997         const CallInst *Call = dyn_cast<CallInst>(&I);
 998         if ((isa<StoreInst>(I) || isa<LoadInst>(I) || isa<MemIntrinsic>(I) ||
 999              isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I) ||
1000              (Call && Call->hasByValArgument())) &&
1001             stackAccessIsSafe(I)) {
1002           O << "     " << I << "\n";
1003         }
1004       }
1005       O << "\n";
1006     }
1007   }
1008 }
1009
1010 LLVM_DUMP_METHOD void StackSafetyGlobalInfo::dump() const { print(dbgs()); }
1011
1012 AnalysisKey StackSafetyAnalysis::Key;
1013
1014 StackSafetyInfo StackSafetyAnalysis::run(Function &F,
1015                                          FunctionAnalysisManager &AM) {
1016   return StackSafetyInfo(&F, [&AM, &F]() -> ScalarEvolution & {
1017     return AM.getResult<ScalarEvolutionAnalysis>(F);
1018   });
1019 }
1020
1021 PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
1022                                               FunctionAnalysisManager &AM) {
1023   OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
1024   AM.getResult<StackSafetyAnalysis>(F).print(OS);
1025   return PreservedAnalyses::all();
1026 }
1027
1028 char StackSafetyInfoWrapperPass::ID = 0;
1029
1030 StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
1031   initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
1032 }
1033
1034 void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1035   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
1036   AU.setPreservesAll();
1037 }
1038
1039 void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
1040   SSI.print(O);
1041 }
1042
1043 bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
1044   auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1045   SSI = {&F, [SE]() -> ScalarEvolution & { return *SE; }};
1046   return false;
1047 }
1048
1049 AnalysisKey StackSafetyGlobalAnalysis::Key;
1050
1051 StackSafetyGlobalInfo
1052 StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
1053   // FIXME: Lookup Module Summary.
1054   FunctionAnalysisManager &FAM =
1055       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1056   return {&M,
1057           [&FAM](Function &F) -> const StackSafetyInfo & {
1058             return FAM.getResult<StackSafetyAnalysis>(F);
1059           },
1060           nullptr};
1061 }
1062
1063 PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
1064                                                     ModuleAnalysisManager &AM) {
1065   OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
1066   AM.getResult<StackSafetyGlobalAnalysis>(M).print(OS);
1067   return PreservedAnalyses::all();
1068 }
1069
1070 char StackSafetyGlobalInfoWrapperPass::ID = 0;
1071
1072 StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
1073     : ModulePass(ID) {
1074   initializeStackSafetyGlobalInfoWrapperPassPass(
1075       *PassRegistry::getPassRegistry());
1076 }
1077
1078 StackSafetyGlobalInfoWrapperPass::~StackSafetyGlobalInfoWrapperPass() = default;
1079
1080 void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
1081                                              const Module *M) const {
1082   SSGI.print(O);
1083 }
1084
1085 void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
1086     AnalysisUsage &AU) const {
1087   AU.setPreservesAll();
1088   AU.addRequired<StackSafetyInfoWrapperPass>();
1089 }
1090
1091 bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
1092   const ModuleSummaryIndex *ImportSummary = nullptr;
1093   if (auto *IndexWrapperPass =
1094           getAnalysisIfAvailable<ImmutableModuleSummaryIndexWrapperPass>())
1095     ImportSummary = IndexWrapperPass->getIndex();
1096
1097   SSGI = {&M,
1098           [this](Function &F) -> const StackSafetyInfo & {
1099             return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
1100           },
1101           ImportSummary};
1102   return false;
1103 }
1104
1105 bool llvm::needsParamAccessSummary(const Module &M) {
1106   if (StackSafetyRun)
1107     return true;
1108   for (const auto &F : M.functions())
1109     if (F.hasFnAttribute(Attribute::SanitizeMemTag))
1110       return true;
1111   return false;
1112 }
1113
1114 void llvm::generateParamAccessSummary(ModuleSummaryIndex &Index) {
1115   if (!Index.hasParamAccess())
1116     return;
1117   const ConstantRange FullSet(FunctionSummary::ParamAccess::RangeWidth, true);
1118
1119   auto CountParamAccesses = [&](auto &Stat) {
1120     if (!AreStatisticsEnabled())
1121       return;
1122     for (auto &GVS : Index)
1123       for (auto &GV : GVS.second.SummaryList)
1124         if (FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get()))
1125           Stat += FS->paramAccesses().size();
1126   };
1127
1128   CountParamAccesses(NumCombinedParamAccessesBefore);
1129
1130   std::map<const FunctionSummary *, FunctionInfo<FunctionSummary>> Functions;
1131
1132   // Convert the ModuleSummaryIndex to a FunctionMap
1133   for (auto &GVS : Index) {
1134     for (auto &GV : GVS.second.SummaryList) {
1135       FunctionSummary *FS = dyn_cast<FunctionSummary>(GV.get());
1136       if (!FS || FS->paramAccesses().empty())
1137         continue;
1138       if (FS->isLive() && FS->isDSOLocal()) {
1139         FunctionInfo<FunctionSummary> FI;
1140         for (const auto &PS : FS->paramAccesses()) {
1141           auto &US =
1142               FI.Params
1143                   .emplace(PS.ParamNo, FunctionSummary::ParamAccess::RangeWidth)
1144                   .first->second;
1145           US.Range = PS.Use;
1146           for (const auto &Call : PS.Calls) {
1147             assert(!Call.Offsets.isFullSet());
1148             FunctionSummary *S =
1149                 findCalleeFunctionSummary(Call.Callee, FS->modulePath());
1150             ++NumCombinedCalleeLookupTotal;
1151             if (!S) {
1152               ++NumCombinedCalleeLookupFailed;
1153               US.Range = FullSet;
1154               US.Calls.clear();
1155               break;
1156             }
1157             US.Calls.emplace(CallInfo<FunctionSummary>(S, Call.ParamNo),
1158                              Call.Offsets);
1159           }
1160         }
1161         Functions.emplace(FS, std::move(FI));
1162       }
1163       // Reset data for all summaries. Alive and DSO local will be set back from
1164       // of data flow results below. Anything else will not be accessed
1165       // by ThinLTO backend, so we can save on bitcode size.
1166       FS->setParamAccesses({});
1167     }
1168   }
1169   NumCombinedDataFlowNodes += Functions.size();
1170   StackSafetyDataFlowAnalysis<FunctionSummary> SSDFA(
1171       FunctionSummary::ParamAccess::RangeWidth, std::move(Functions));
1172   for (const auto &KV : SSDFA.run()) {
1173     std::vector<FunctionSummary::ParamAccess> NewParams;
1174     NewParams.reserve(KV.second.Params.size());
1175     for (const auto &Param : KV.second.Params) {
1176       // It's not needed as FullSet is processed the same as a missing value.
1177       if (Param.second.Range.isFullSet())
1178         continue;
1179       NewParams.emplace_back();
1180       FunctionSummary::ParamAccess &New = NewParams.back();
1181       New.ParamNo = Param.first;
1182       New.Use = Param.second.Range; // Only range is needed.
1183     }
1184     const_cast<FunctionSummary *>(KV.first)->setParamAccesses(
1185         std::move(NewParams));
1186   }
1187
1188   CountParamAccesses(NumCombinedParamAccessesAfter);
1189 }
1190
1191 static const char LocalPassArg[] = "stack-safety-local";
1192 static const char LocalPassName[] = "Stack Safety Local Analysis";
1193 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
1194                       false, true)
1195 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1196 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
1197                     false, true)
1198
1199 static const char GlobalPassName[] = "Stack Safety Analysis";
1200 INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
1201                       GlobalPassName, false, true)
1202 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
1203 INITIALIZE_PASS_DEPENDENCY(ImmutableModuleSummaryIndexWrapperPass)
1204 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
1205                     GlobalPassName, false, true)