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