contrib/llvm/lib/Analysis/StackSafetyAnalysis.cpp

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