contrib/llvm-project/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/Analysis/ScalarEvolutionExpressions.h"
  13 #include "llvm/IR/CallSite.h"
  14 #include "llvm/IR/InstIterator.h"
  15 #include "llvm/IR/IntrinsicInst.h"
  16 #include "llvm/Support/raw_ostream.h"
  17
  18 using namespace llvm;
  19
  20 #define DEBUG_TYPE "stack-safety"
  21
  22 static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
  23                                              cl::init(20), cl::Hidden);
  24
  25 namespace {
  26
  27 /// Rewrite an SCEV expression for a memory access address to an expression that
  28 /// represents offset from the given alloca.
  29 class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
  30   const Value *AllocaPtr;
  31
  32 public:
  33   AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr)
  34       : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {}
  35
  36   const SCEV *visit(const SCEV *Expr) {
  37     // Only re-write the expression if the alloca is used in an addition
  38     // expression (it can be used in other types of expressions if it's cast to
  39     // an int and passed as an argument.)
  40     if (!isa<SCEVAddRecExpr>(Expr) && !isa<SCEVAddExpr>(Expr) &&
  41         !isa<SCEVUnknown>(Expr))
  42       return Expr;
  43     return SCEVRewriteVisitor<AllocaOffsetRewriter>::visit(Expr);
  44   }
  45
  46   const SCEV *visitUnknown(const SCEVUnknown *Expr) {
  47     // FIXME: look through one or several levels of definitions?
  48     // This can be inttoptr(AllocaPtr) and SCEV would not unwrap
  49     // it for us.
  50     if (Expr->getValue() == AllocaPtr)
  51       return SE.getZero(Expr->getType());
  52     return Expr;
  53   }
  54 };
  55
  56 /// Describes use of address in as a function call argument.
  57 struct PassAsArgInfo {
  58   /// Function being called.
  59   const GlobalValue *Callee = nullptr;
  60   /// Index of argument which pass address.
  61   size_t ParamNo = 0;
  62   // Offset range of address from base address (alloca or calling function
  63   // argument).
  64   // Range should never set to empty-set, that is an invalid access range
  65   // that can cause empty-set to be propagated with ConstantRange::add
  66   ConstantRange Offset;
  67   PassAsArgInfo(const GlobalValue *Callee, size_t ParamNo, ConstantRange Offset)
  68       : Callee(Callee), ParamNo(ParamNo), Offset(Offset) {}
  69
  70   StringRef getName() const { return Callee->getName(); }
  71 };
  72
  73 raw_ostream &operator<<(raw_ostream &OS, const PassAsArgInfo &P) {
  74   return OS << "@" << P.getName() << "(arg" << P.ParamNo << ", " << P.Offset
  75             << ")";
  76 }
  77
  78 /// Describe uses of address (alloca or parameter) inside of the function.
  79 struct UseInfo {
  80   // Access range if the address (alloca or parameters).
  81   // It is allowed to be empty-set when there are no known accesses.
  82   ConstantRange Range;
  83
  84   // List of calls which pass address as an argument.
  85   SmallVector<PassAsArgInfo, 4> Calls;
  86
  87   explicit UseInfo(unsigned PointerSize) : Range{PointerSize, false} {}
  88
  89   void updateRange(ConstantRange R) { Range = Range.unionWith(R); }
  90 };
  91
  92 raw_ostream &operator<<(raw_ostream &OS, const UseInfo &U) {
  93   OS << U.Range;
  94   for (auto &Call : U.Calls)
  95     OS << ", " << Call;
  96   return OS;
  97 }
  98
  99 struct AllocaInfo {
 100   const AllocaInst *AI = nullptr;
 101   uint64_t Size = 0;
 102   UseInfo Use;
 103
 104   AllocaInfo(unsigned PointerSize, const AllocaInst *AI, uint64_t Size)
 105       : AI(AI), Size(Size), Use(PointerSize) {}
 106
 107   StringRef getName() const { return AI->getName(); }
 108 };
 109
 110 raw_ostream &operator<<(raw_ostream &OS, const AllocaInfo &A) {
 111   return OS << A.getName() << "[" << A.Size << "]: " << A.Use;
 112 }
 113
 114 struct ParamInfo {
 115   const Argument *Arg = nullptr;
 116   UseInfo Use;
 117
 118   explicit ParamInfo(unsigned PointerSize, const Argument *Arg)
 119       : Arg(Arg), Use(PointerSize) {}
 120
 121   StringRef getName() const { return Arg ? Arg->getName() : "<N/A>"; }
 122 };
 123
 124 raw_ostream &operator<<(raw_ostream &OS, const ParamInfo &P) {
 125   return OS << P.getName() << "[]: " << P.Use;
 126 }
 127
 128 /// Calculate the allocation size of a given alloca. Returns 0 if the
 129 /// size can not be statically determined.
 130 uint64_t getStaticAllocaAllocationSize(const AllocaInst *AI) {
 131   const DataLayout &DL = AI->getModule()->getDataLayout();
 132   uint64_t Size = DL.getTypeAllocSize(AI->getAllocatedType());
 133   if (AI->isArrayAllocation()) {
 134     auto C = dyn_cast<ConstantInt>(AI->getArraySize());
 135     if (!C)
 136       return 0;
 137     Size *= C->getZExtValue();
 138   }
 139   return Size;
 140 }
 141
 142 } // end anonymous namespace
 143
 144 /// Describes uses of allocas and parameters inside of a single function.
 145 struct StackSafetyInfo::FunctionInfo {
 146   // May be a Function or a GlobalAlias
 147   const GlobalValue *GV = nullptr;
 148   // Informations about allocas uses.
 149   SmallVector<AllocaInfo, 4> Allocas;
 150   // Informations about parameters uses.
 151   SmallVector<ParamInfo, 4> Params;
 152   // TODO: describe return value as depending on one or more of its arguments.
 153
 154   // StackSafetyDataFlowAnalysis counter stored here for faster access.
 155   int UpdateCount = 0;
 156
 157   FunctionInfo(const StackSafetyInfo &SSI) : FunctionInfo(*SSI.Info) {}
 158
 159   explicit FunctionInfo(const Function *F) : GV(F){};
 160   // Creates FunctionInfo that forwards all the parameters to the aliasee.
 161   explicit FunctionInfo(const GlobalAlias *A);
 162
 163   FunctionInfo(FunctionInfo &&) = default;
 164
 165   bool IsDSOLocal() const { return GV->isDSOLocal(); };
 166
 167   bool IsInterposable() const { return GV->isInterposable(); };
 168
 169   StringRef getName() const { return GV->getName(); }
 170
 171   void print(raw_ostream &O) const {
 172     // TODO: Consider different printout format after
 173     // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.
 174     O << "  @" << getName() << (IsDSOLocal() ? "" : " dso_preemptable")
 175       << (IsInterposable() ? " interposable" : "") << "\n";
 176     O << "    args uses:\n";
 177     for (auto &P : Params)
 178       O << "      " << P << "\n";
 179     O << "    allocas uses:\n";
 180     for (auto &AS : Allocas)
 181       O << "      " << AS << "\n";
 182   }
 183
 184 private:
 185   FunctionInfo(const FunctionInfo &) = default;
 186 };
 187
 188 StackSafetyInfo::FunctionInfo::FunctionInfo(const GlobalAlias *A) : GV(A) {
 189   unsigned PointerSize = A->getParent()->getDataLayout().getPointerSizeInBits();
 190   const GlobalObject *Aliasee = A->getBaseObject();
 191   const FunctionType *Type = cast<FunctionType>(Aliasee->getValueType());
 192   // 'Forward' all parameters to this alias to the aliasee
 193   for (unsigned ArgNo = 0; ArgNo < Type->getNumParams(); ArgNo++) {
 194     Params.emplace_back(PointerSize, nullptr);
 195     UseInfo &US = Params.back().Use;
 196     US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0)));
 197   }
 198 }
 199
 200 namespace {
 201
 202 class StackSafetyLocalAnalysis {
 203   const Function &F;
 204   const DataLayout &DL;
 205   ScalarEvolution &SE;
 206   unsigned PointerSize = 0;
 207
 208   const ConstantRange UnknownRange;
 209
 210   ConstantRange offsetFromAlloca(Value *Addr, const Value *AllocaPtr);
 211   ConstantRange getAccessRange(Value *Addr, const Value *AllocaPtr,
 212                                uint64_t AccessSize);
 213   ConstantRange getMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
 214                                            const Value *AllocaPtr);
 215
 216   bool analyzeAllUses(const Value *Ptr, UseInfo &AS);
 217
 218   ConstantRange getRange(uint64_t Lower, uint64_t Upper) const {
 219     return ConstantRange(APInt(PointerSize, Lower), APInt(PointerSize, Upper));
 220   }
 221
 222 public:
 223   StackSafetyLocalAnalysis(const Function &F, ScalarEvolution &SE)
 224       : F(F), DL(F.getParent()->getDataLayout()), SE(SE),
 225         PointerSize(DL.getPointerSizeInBits()),
 226         UnknownRange(PointerSize, true) {}
 227
 228   // Run the transformation on the associated function.
 229   StackSafetyInfo run();
 230 };
 231
 232 ConstantRange
 233 StackSafetyLocalAnalysis::offsetFromAlloca(Value *Addr,
 234                                            const Value *AllocaPtr) {
 235   if (!SE.isSCEVable(Addr->getType()))
 236     return UnknownRange;
 237
 238   AllocaOffsetRewriter Rewriter(SE, AllocaPtr);
 239   const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr));
 240   ConstantRange Offset = SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize);
 241   assert(!Offset.isEmptySet());
 242   return Offset;
 243 }
 244
 245 ConstantRange StackSafetyLocalAnalysis::getAccessRange(Value *Addr,
 246                                                        const Value *AllocaPtr,
 247                                                        uint64_t AccessSize) {
 248   if (!SE.isSCEVable(Addr->getType()))
 249     return UnknownRange;
 250
 251   AllocaOffsetRewriter Rewriter(SE, AllocaPtr);
 252   const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr));
 253
 254   ConstantRange AccessStartRange =
 255       SE.getUnsignedRange(Expr).zextOrTrunc(PointerSize);
 256   ConstantRange SizeRange = getRange(0, AccessSize);
 257   ConstantRange AccessRange = AccessStartRange.add(SizeRange);
 258   assert(!AccessRange.isEmptySet());
 259   return AccessRange;
 260 }
 261
 262 ConstantRange StackSafetyLocalAnalysis::getMemIntrinsicAccessRange(
 263     const MemIntrinsic *MI, const Use &U, const Value *AllocaPtr) {
 264   if (auto MTI = dyn_cast<MemTransferInst>(MI)) {
 265     if (MTI->getRawSource() != U && MTI->getRawDest() != U)
 266       return getRange(0, 1);
 267   } else {
 268     if (MI->getRawDest() != U)
 269       return getRange(0, 1);
 270   }
 271   const auto *Len = dyn_cast<ConstantInt>(MI->getLength());
 272   // Non-constant size => unsafe. FIXME: try SCEV getRange.
 273   if (!Len)
 274     return UnknownRange;
 275   ConstantRange AccessRange = getAccessRange(U, AllocaPtr, Len->getZExtValue());
 276   return AccessRange;
 277 }
 278
 279 /// The function analyzes all local uses of Ptr (alloca or argument) and
 280 /// calculates local access range and all function calls where it was used.
 281 bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) {
 282   SmallPtrSet<const Value *, 16> Visited;
 283   SmallVector<const Value *, 8> WorkList;
 284   WorkList.push_back(Ptr);
 285
 286   // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
 287   while (!WorkList.empty()) {
 288     const Value *V = WorkList.pop_back_val();
 289     for (const Use &UI : V->uses()) {
 290       auto I = cast<const Instruction>(UI.getUser());
 291       assert(V == UI.get());
 292
 293       switch (I->getOpcode()) {
 294       case Instruction::Load: {
 295         US.updateRange(
 296             getAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType())));
 297         break;
 298       }
 299
 300       case Instruction::VAArg:
 301         // "va-arg" from a pointer is safe.
 302         break;
 303       case Instruction::Store: {
 304         if (V == I->getOperand(0)) {
 305           // Stored the pointer - conservatively assume it may be unsafe.
 306           US.updateRange(UnknownRange);
 307           return false;
 308         }
 309         US.updateRange(getAccessRange(
 310             UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType())));
 311         break;
 312       }
 313
 314       case Instruction::Ret:
 315         // Information leak.
 316         // FIXME: Process parameters correctly. This is a leak only if we return
 317         // alloca.
 318         US.updateRange(UnknownRange);
 319         return false;
 320
 321       case Instruction::Call:
 322       case Instruction::Invoke: {
 323         ImmutableCallSite CS(I);
 324
 325         if (I->isLifetimeStartOrEnd())
 326           break;
 327
 328         if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
 329           US.updateRange(getMemIntrinsicAccessRange(MI, UI, Ptr));
 330           break;
 331         }
 332
 333         // FIXME: consult devirt?
 334         // Do not follow aliases, otherwise we could inadvertently follow
 335         // dso_preemptable aliases or aliases with interposable linkage.
 336         const GlobalValue *Callee = dyn_cast<GlobalValue>(
 337             CS.getCalledValue()->stripPointerCastsNoFollowAliases());
 338         if (!Callee) {
 339           US.updateRange(UnknownRange);
 340           return false;
 341         }
 342
 343         assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
 344
 345         ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
 346         for (ImmutableCallSite::arg_iterator A = B; A != E; ++A) {
 347           if (A->get() == V) {
 348             ConstantRange Offset = offsetFromAlloca(UI, Ptr);
 349             US.Calls.emplace_back(Callee, A - B, Offset);
 350           }
 351         }
 352
 353         break;
 354       }
 355
 356       default:
 357         if (Visited.insert(I).second)
 358           WorkList.push_back(cast<const Instruction>(I));
 359       }
 360     }
 361   }
 362
 363   return true;
 364 }
 365
 366 StackSafetyInfo StackSafetyLocalAnalysis::run() {
 367   StackSafetyInfo::FunctionInfo Info(&F);
 368   assert(!F.isDeclaration() &&
 369          "Can't run StackSafety on a function declaration");
 370
 371   LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
 372
 373   for (auto &I : instructions(F)) {
 374     if (auto AI = dyn_cast<AllocaInst>(&I)) {
 375       Info.Allocas.emplace_back(PointerSize, AI,
 376                                 getStaticAllocaAllocationSize(AI));
 377       AllocaInfo &AS = Info.Allocas.back();
 378       analyzeAllUses(AI, AS.Use);
 379     }
 380   }
 381
 382   for (const Argument &A : make_range(F.arg_begin(), F.arg_end())) {
 383     Info.Params.emplace_back(PointerSize, &A);
 384     ParamInfo &PS = Info.Params.back();
 385     analyzeAllUses(&A, PS.Use);
 386   }
 387
 388   LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
 389   LLVM_DEBUG(Info.print(dbgs()));
 390   return StackSafetyInfo(std::move(Info));
 391 }
 392
 393 class StackSafetyDataFlowAnalysis {
 394   using FunctionMap =
 395       std::map<const GlobalValue *, StackSafetyInfo::FunctionInfo>;
 396
 397   FunctionMap Functions;
 398   // Callee-to-Caller multimap.
 399   DenseMap<const GlobalValue *, SmallVector<const GlobalValue *, 4>> Callers;
 400   SetVector<const GlobalValue *> WorkList;
 401
 402   unsigned PointerSize = 0;
 403   const ConstantRange UnknownRange;
 404
 405   ConstantRange getArgumentAccessRange(const GlobalValue *Callee,
 406                                        unsigned ParamNo) const;
 407   bool updateOneUse(UseInfo &US, bool UpdateToFullSet);
 408   void updateOneNode(const GlobalValue *Callee,
 409                      StackSafetyInfo::FunctionInfo &FS);
 410   void updateOneNode(const GlobalValue *Callee) {
 411     updateOneNode(Callee, Functions.find(Callee)->second);
 412   }
 413   void updateAllNodes() {
 414     for (auto &F : Functions)
 415       updateOneNode(F.first, F.second);
 416   }
 417   void runDataFlow();
 418 #ifndef NDEBUG
 419   void verifyFixedPoint();
 420 #endif
 421
 422 public:
 423   StackSafetyDataFlowAnalysis(
 424       Module &M, std::function<const StackSafetyInfo &(Function &)> FI);
 425   StackSafetyGlobalInfo run();
 426 };
 427
 428 StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis(
 429     Module &M, std::function<const StackSafetyInfo &(Function &)> FI)
 430     : PointerSize(M.getDataLayout().getPointerSizeInBits()),
 431       UnknownRange(PointerSize, true) {
 432   // Without ThinLTO, run the local analysis for every function in the TU and
 433   // then run the DFA.
 434   for (auto &F : M.functions())
 435     if (!F.isDeclaration())
 436       Functions.emplace(&F, FI(F));
 437   for (auto &A : M.aliases())
 438     if (isa<Function>(A.getBaseObject()))
 439       Functions.emplace(&A, StackSafetyInfo::FunctionInfo(&A));
 440 }
 441
 442 ConstantRange
 443 StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee,
 444                                                     unsigned ParamNo) const {
 445   auto IT = Functions.find(Callee);
 446   // Unknown callee (outside of LTO domain or an indirect call).
 447   if (IT == Functions.end())
 448     return UnknownRange;
 449   const StackSafetyInfo::FunctionInfo &FS = IT->second;
 450   // The definition of this symbol may not be the definition in this linkage
 451   // unit.
 452   if (!FS.IsDSOLocal() || FS.IsInterposable())
 453     return UnknownRange;
 454   if (ParamNo >= FS.Params.size()) // possibly vararg
 455     return UnknownRange;
 456   return FS.Params[ParamNo].Use.Range;
 457 }
 458
 459 bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US,
 460                                                bool UpdateToFullSet) {
 461   bool Changed = false;
 462   for (auto &CS : US.Calls) {
 463     assert(!CS.Offset.isEmptySet() &&
 464            "Param range can't be empty-set, invalid offset range");
 465
 466     ConstantRange CalleeRange = getArgumentAccessRange(CS.Callee, CS.ParamNo);
 467     CalleeRange = CalleeRange.add(CS.Offset);
 468     if (!US.Range.contains(CalleeRange)) {
 469       Changed = true;
 470       if (UpdateToFullSet)
 471         US.Range = UnknownRange;
 472       else
 473         US.Range = US.Range.unionWith(CalleeRange);
 474     }
 475   }
 476   return Changed;
 477 }
 478
 479 void StackSafetyDataFlowAnalysis::updateOneNode(
 480     const GlobalValue *Callee, StackSafetyInfo::FunctionInfo &FS) {
 481   bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
 482   bool Changed = false;
 483   for (auto &AS : FS.Allocas)
 484     Changed |= updateOneUse(AS.Use, UpdateToFullSet);
 485   for (auto &PS : FS.Params)
 486     Changed |= updateOneUse(PS.Use, UpdateToFullSet);
 487
 488   if (Changed) {
 489     LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
 490                       << (UpdateToFullSet ? ", full-set" : "") << "] "
 491                       << FS.getName() << "\n");
 492     // Callers of this function may need updating.
 493     for (auto &CallerID : Callers[Callee])
 494       WorkList.insert(CallerID);
 495
 496     ++FS.UpdateCount;
 497   }
 498 }
 499
 500 void StackSafetyDataFlowAnalysis::runDataFlow() {
 501   Callers.clear();
 502   WorkList.clear();
 503
 504   SmallVector<const GlobalValue *, 16> Callees;
 505   for (auto &F : Functions) {
 506     Callees.clear();
 507     StackSafetyInfo::FunctionInfo &FS = F.second;
 508     for (auto &AS : FS.Allocas)
 509       for (auto &CS : AS.Use.Calls)
 510         Callees.push_back(CS.Callee);
 511     for (auto &PS : FS.Params)
 512       for (auto &CS : PS.Use.Calls)
 513         Callees.push_back(CS.Callee);
 514
 515     llvm::sort(Callees);
 516     Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
 517
 518     for (auto &Callee : Callees)
 519       Callers[Callee].push_back(F.first);
 520   }
 521
 522   updateAllNodes();
 523
 524   while (!WorkList.empty()) {
 525     const GlobalValue *Callee = WorkList.back();
 526     WorkList.pop_back();
 527     updateOneNode(Callee);
 528   }
 529 }
 530
 531 #ifndef NDEBUG
 532 void StackSafetyDataFlowAnalysis::verifyFixedPoint() {
 533   WorkList.clear();
 534   updateAllNodes();
 535   assert(WorkList.empty());
 536 }
 537 #endif
 538
 539 StackSafetyGlobalInfo StackSafetyDataFlowAnalysis::run() {
 540   runDataFlow();
 541   LLVM_DEBUG(verifyFixedPoint());
 542
 543   StackSafetyGlobalInfo SSI;
 544   for (auto &F : Functions)
 545     SSI.emplace(F.first, std::move(F.second));
 546   return SSI;
 547 }
 548
 549 void print(const StackSafetyGlobalInfo &SSI, raw_ostream &O, const Module &M) {
 550   size_t Count = 0;
 551   for (auto &F : M.functions())
 552     if (!F.isDeclaration()) {
 553       SSI.find(&F)->second.print(O);
 554       O << "\n";
 555       ++Count;
 556     }
 557   for (auto &A : M.aliases()) {
 558     SSI.find(&A)->second.print(O);
 559     O << "\n";
 560     ++Count;
 561   }
 562   assert(Count == SSI.size() && "Unexpected functions in the result");
 563 }
 564
 565 } // end anonymous namespace
 566
 567 StackSafetyInfo::StackSafetyInfo() = default;
 568 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
 569 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
 570
 571 StackSafetyInfo::StackSafetyInfo(FunctionInfo &&Info)
 572     : Info(new FunctionInfo(std::move(Info))) {}
 573
 574 StackSafetyInfo::~StackSafetyInfo() = default;
 575
 576 void StackSafetyInfo::print(raw_ostream &O) const { Info->print(O); }
 577
 578 AnalysisKey StackSafetyAnalysis::Key;
 579
 580 StackSafetyInfo StackSafetyAnalysis::run(Function &F,
 581                                          FunctionAnalysisManager &AM) {
 582   StackSafetyLocalAnalysis SSLA(F, AM.getResult<ScalarEvolutionAnalysis>(F));
 583   return SSLA.run();
 584 }
 585
 586 PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
 587                                               FunctionAnalysisManager &AM) {
 588   OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
 589   AM.getResult<StackSafetyAnalysis>(F).print(OS);
 590   return PreservedAnalyses::all();
 591 }
 592
 593 char StackSafetyInfoWrapperPass::ID = 0;
 594
 595 StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
 596   initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
 597 }
 598
 599 void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 600   AU.addRequired<ScalarEvolutionWrapperPass>();
 601   AU.setPreservesAll();
 602 }
 603
 604 void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
 605   SSI.print(O);
 606 }
 607
 608 bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
 609   StackSafetyLocalAnalysis SSLA(
 610       F, getAnalysis<ScalarEvolutionWrapperPass>().getSE());
 611   SSI = StackSafetyInfo(SSLA.run());
 612   return false;
 613 }
 614
 615 AnalysisKey StackSafetyGlobalAnalysis::Key;
 616
 617 StackSafetyGlobalInfo
 618 StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
 619   FunctionAnalysisManager &FAM =
 620       AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 621
 622   StackSafetyDataFlowAnalysis SSDFA(
 623       M, [&FAM](Function &F) -> const StackSafetyInfo & {
 624         return FAM.getResult<StackSafetyAnalysis>(F);
 625       });
 626   return SSDFA.run();
 627 }
 628
 629 PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
 630                                                     ModuleAnalysisManager &AM) {
 631   OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
 632   print(AM.getResult<StackSafetyGlobalAnalysis>(M), OS, M);
 633   return PreservedAnalyses::all();
 634 }
 635
 636 char StackSafetyGlobalInfoWrapperPass::ID = 0;
 637
 638 StackSafetyGlobalInfoWrapperPass::StackSafetyGlobalInfoWrapperPass()
 639     : ModulePass(ID) {
 640   initializeStackSafetyGlobalInfoWrapperPassPass(
 641       *PassRegistry::getPassRegistry());
 642 }
 643
 644 void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
 645                                              const Module *M) const {
 646   ::print(SSI, O, *M);
 647 }
 648
 649 void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
 650     AnalysisUsage &AU) const {
 651   AU.addRequired<StackSafetyInfoWrapperPass>();
 652 }
 653
 654 bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
 655   StackSafetyDataFlowAnalysis SSDFA(
 656       M, [this](Function &F) -> const StackSafetyInfo & {
 657         return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
 658       });
 659   SSI = SSDFA.run();
 660   return false;
 661 }
 662
 663 static const char LocalPassArg[] = "stack-safety-local";
 664 static const char LocalPassName[] = "Stack Safety Local Analysis";
 665 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
 666                       false, true)
 667 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 668 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
 669                     false, true)
 670
 671 static const char GlobalPassName[] = "Stack Safety Analysis";
 672 INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
 673                       GlobalPassName, false, false)
 674 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
 675 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
 676                     GlobalPassName, false, false)