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.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 || isa<GlobalIFunc>(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)