[stack-safety] Inter-Procedural Analysis implementation

[vitalybuka]

Summary

IPA is implemented as module pass which produce map from Function or Alias to
StackSafetyInfo for a single function.

From prototype by Evgenii Stepanov and Vlad Tsyrklevich.

[vitalybuka]

cleanup includes

[mgrang]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

494 ↗

(On Diff #174098)

Please use the range-based llvm::sort(Callees) instead of std::sort.

See https://llvm.org/docs/CodingStandards.html#beware-of-non-deterministic-sorting-order-of-equal-elements

[vitalybuka]

llvm::sort

[vlad.tsyrklevich]

The local tests that check for use 'empty-set, $CALL_INFO' for the local and 'full-set, $CALL_INFO' for the global analysis is sort of confusing. It seems like the use is safe in local analysis (empty-set means no uses!) but unsafe in the global, when really the situation is actually local analysis has 'no local uses but used in function calls' and the global analysis is just 'it's safe/unsafe (function call info is integrated into the previous distintion)'. Maybe we should clear all of the UseInfo::Calls fields at the end of StackSafetyDataFlowAnalysis?

llvm/lib/Analysis/StackSafetyAnalysis.cpp

147 ↗

(On Diff #174098)

s/'function' summary/FunctionInfo/

599 ↗

(On Diff #174098)

Do we need this comment here and in StackSafetyDataFlowAnalysis?

634 ↗

(On Diff #174098)

Do we need this comment here and in StackSafetyDataFlowAnalysis?

[vitalybuka]

In D54543#1299824, @vlad.tsyrklevich wrote:

The local tests that check for use 'empty-set, $CALL_INFO' for the local and 'full-set, $CALL_INFO' for the global analysis is sort of confusing. It seems like the use is safe in local analysis (empty-set means no uses!) but unsafe in the global, when really the situation is actually local analysis has 'no local uses but used in function calls' and the global analysis is just 'it's safe/unsafe (function call info is integrated into the previous distintion)'. Maybe we should clear all of the UseInfo::Calls fields at the end of StackSafetyDataFlowAnalysis?

That's unfortunate, as now we can keep checks for local and global passes mostly the same and highlight the difference with branched LOCAL-NEXT/GLOBAL-NEXT

[vlad.tsyrklevich]

In D54543#1300326, @vitalybuka wrote:

That's unfortunate, as now we can keep checks for local and global passes mostly the same and highlight the difference with branched LOCAL-NEXT/GLOBAL-NEXT

That's a good point, I didn't consider that it would break that pattern. Though looking at the tests now it seems that the current tests don't have cases where this would happen? Presumably most tests where an alloca has a use in a function call it would result in a local/global difference due to the IPA being able to refine the use range.

[vitalybuka]

In D54543#1300349, @vlad.tsyrklevich wrote:

In D54543#1300326, @vitalybuka wrote:

That's unfortunate, as now we can keep checks for local and global passes mostly the same and highlight the difference with branched LOCAL-NEXT/GLOBAL-NEXT

That's a good point, I didn't consider that it would break that pattern. Though looking at the tests now it seems that the current tests don't have cases where this would happen? Presumably most tests where an alloca has a use in a function call it would result in a local/global difference due to the IPA being able to refine the use range.

Can we reconsider this later. I've added TODO. Probably these are implementation details which are unneeded.

[vitalybuka]

@vlad.tsyrklevich comments

[vlad.tsyrklevich]

In D54543#1300455, @vitalybuka wrote:

Can we reconsider this later. I've added TODO. Probably these are implementation details which are unneeded.

I'm OK coming back to it after the bulk of the changes have landed.

[eugenis]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

380 ↗

(On Diff #174283)

UpdateCount could be moved to FunctionInfo to save a hash map lookup.

421 ↗

(On Diff #174283)

Use DataLayout::getPointerSizeInBits instead of 64.

514 ↗

(On Diff #174283)

This makes verifyFixedPoint unused in no-assertions build. Move it under LLVM_DEBUG, too.

[vitalybuka]

@eugenis comments

llvm/lib/Analysis/StackSafetyAnalysis.cpp

514 ↗

(On Diff #174283)

I'd rather keep unused function than introducing "#ifndef NDEBUG"

[eugenis]

LGTM with nit

llvm/lib/Analysis/StackSafetyAnalysis.cpp

187 ↗

(On Diff #174986)

getPointerSizeInBits implementation is not trivial, consider caching the result in StackSafetyLocalAnalysis

[vitalybuka]

update

[vlad.tsyrklevich]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

428 ↗

(On Diff #175003)

s/ and annotate allocas//

[vitalybuka]

rebase

[jfb]

Please fix the build break introduced.

llvm/trunk/lib/Analysis/StackSafetyAnalysis.cpp

466

This doesn't build:

../lib/Analysis/StackSafetyAnalysis.cpp:465:16: error: no member named 'Range' in '(anonymous namespace)::PassAsArgInfo'
    assert(!CS.Range.isEmptySet() &&
            ~~ ^

I commented it out in r347616. Please fix.

[vitalybuka]

Thanks, I'll fix the assert.

llvm/trunk/lib/Analysis/StackSafetyAnalysis.cpp

 //===- StackSafetyAnalysis.cpp - Stack memory safety analysis -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/StackSafetyAnalysis.h"
-#include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "stack-safety"
 
+static cl::opt<int> StackSafetyMaxIterations("stack-safety-max-iterations",
+                                             cl::init(20), cl::Hidden);
+
 namespace {
 
 /// Rewrite an SCEV expression for a memory access address to an expression that
 /// represents offset from the given alloca.
 class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
   const Value *AllocaPtr;
 
 public:
struct StackSafetyInfo::FunctionInfo {
   // May be a Function or a GlobalAlias
   const GlobalValue *GV = nullptr;
   // Informations about allocas uses.
   SmallVector<AllocaInfo, 4> Allocas;
   // Informations about parameters uses.
   SmallVector<ParamInfo, 4> Params;
   // TODO: describe return value as depending on one or more of its arguments.
 
+  // StackSafetyDataFlowAnalysis counter stored here for faster access.
+  int UpdateCount = 0;
+
   FunctionInfo(const StackSafetyInfo &SSI) : FunctionInfo(*SSI.Info) {}
 
   explicit FunctionInfo(const Function *F) : GV(F){};
+  // Creates FunctionInfo that forwards all the parameters to the aliasee.
+  explicit FunctionInfo(const GlobalAlias *A);
 
   FunctionInfo(FunctionInfo &&) = default;
 
   bool IsDSOLocal() const { return GV->isDSOLocal(); };
 
   bool IsInterposable() const { return GV->isInterposable(); };
 
   StringRef getName() const { return GV->getName(); }
 
   void print(raw_ostream &O) const {
+    // TODO: Consider different printout format after
+    // StackSafetyDataFlowAnalysis. Calls and parameters are irrelevant then.
     O << "  @" << getName() << (IsDSOLocal() ? "" : " dso_preemptable")
       << (IsInterposable() ? " interposable" : "") << "\n";
     O << "    args uses:\n";
     for (auto &P : Params)
       O << "      " << P << "\n";
     O << "    allocas uses:\n";
     for (auto &AS : Allocas)
       O << "      " << AS << "\n";
   }
 
 private:
   FunctionInfo(const FunctionInfo &) = default;
 };
 
+StackSafetyInfo::FunctionInfo::FunctionInfo(const GlobalAlias *A) : GV(A) {
+  unsigned PointerSize = A->getParent()->getDataLayout().getPointerSizeInBits();
+  const GlobalObject *Aliasee = A->getBaseObject();
+  const FunctionType *Type = cast<FunctionType>(Aliasee->getValueType());
+  // 'Forward' all parameters to this alias to the aliasee
+  for (unsigned ArgNo = 0; ArgNo < Type->getNumParams(); ArgNo++) {
+    Params.emplace_back(PointerSize, nullptr);
+    UseInfo &US = Params.back().Use;
+    US.Calls.emplace_back(Aliasee, ArgNo, ConstantRange(APInt(PointerSize, 0)));
+  }
+}
+
 namespace {
 
 class StackSafetyLocalAnalysis {
   const Function &F;
   const DataLayout &DL;
   ScalarEvolution &SE;
   unsigned PointerSize = 0;
 
for (const Argument &A : make_range(F.arg_begin(), F.arg_end())) {
     analyzeAllUses(&A, PS.Use);
   }
 
   LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
   LLVM_DEBUG(Info.print(dbgs()));
   return StackSafetyInfo(std::move(Info));
 }
 
+class StackSafetyDataFlowAnalysis {
+  using FunctionMap =
+      std::map<const GlobalValue *, StackSafetyInfo::FunctionInfo>;
+
+  FunctionMap Functions;
+  // Callee-to-Caller multimap.
+  DenseMap<const GlobalValue *, SmallVector<const GlobalValue *, 4>> Callers;
+  SetVector<const GlobalValue *> WorkList;
+
+  unsigned PointerSize = 0;
+  const ConstantRange UnknownRange;
+
+  ConstantRange getArgumentAccessRange(const GlobalValue *Callee,
+                                       unsigned ParamNo) const;
+  bool updateOneUse(UseInfo &US, bool UpdateToFullSet);
+  void updateOneNode(const GlobalValue *Callee,
+                     StackSafetyInfo::FunctionInfo &FS);
+  void updateOneNode(const GlobalValue *Callee) {
+    updateOneNode(Callee, Functions.find(Callee)->second);
+  }
+  void updateAllNodes() {
+    for (auto &F : Functions)
+      updateOneNode(F.first, F.second);
+  }
+  void runDataFlow();
+  void verifyFixedPoint();
+
+public:
+  StackSafetyDataFlowAnalysis(
+      Module &M, std::function<const StackSafetyInfo &(Function &)> FI);
+  StackSafetyGlobalInfo run();
+};
+
+StackSafetyDataFlowAnalysis::StackSafetyDataFlowAnalysis(
+    Module &M, std::function<const StackSafetyInfo &(Function &)> FI)
+    : PointerSize(M.getDataLayout().getPointerSizeInBits()),
+      UnknownRange(PointerSize, true) {
+  // Without ThinLTO, run the local analysis for every function in the TU and
+  // then run the DFA and annotate allocas
+  for (auto &F : M.functions())
+    if (!F.isDeclaration())
+      Functions.emplace(&F, FI(F));
+  for (auto &A : M.aliases())
+    if (isa<Function>(A.getBaseObject()))
+      Functions.emplace(&A, &A);
+}
+
+ConstantRange
+StackSafetyDataFlowAnalysis::getArgumentAccessRange(const GlobalValue *Callee,
+                                                    unsigned ParamNo) const {
+  auto IT = Functions.find(Callee);
+  // Unknown callee (outside of LTO domain or an indirect call).
+  if (IT == Functions.end())
+    return UnknownRange;
+  const StackSafetyInfo::FunctionInfo &FS = IT->second;
+  // The definition of this symbol may not be the definition in this linkage
+  // unit.
+  if (!FS.IsDSOLocal() || FS.IsInterposable())
+    return UnknownRange;
+  if (ParamNo >= FS.Params.size()) // possibly vararg
+    return UnknownRange;
+  return FS.Params[ParamNo].Use.Range;
+}
+
+bool StackSafetyDataFlowAnalysis::updateOneUse(UseInfo &US,
+                                               bool UpdateToFullSet) {
+  bool Changed = false;
+  for (auto &CS : US.Calls) {
+    assert(!CS.Range.isEmptySet() &&
+           "Param range can't be empty-set, invalid access range");
+
+    ConstantRange CalleeRange = getArgumentAccessRange(CS.Callee, CS.ParamNo);
+    CalleeRange = CalleeRange.add(CS.Offset);
+    if (!US.Range.contains(CalleeRange)) {
+      Changed = true;
+      if (UpdateToFullSet)
+        US.Range = UnknownRange;
+      else
+        US.Range = US.Range.unionWith(CalleeRange);
+    }
+  }
+  return Changed;
+}
+
+void StackSafetyDataFlowAnalysis::updateOneNode(
+    const GlobalValue *Callee, StackSafetyInfo::FunctionInfo &FS) {
+  bool UpdateToFullSet = FS.UpdateCount > StackSafetyMaxIterations;
+  bool Changed = false;
+  for (auto &AS : FS.Allocas)
+    Changed |= updateOneUse(AS.Use, UpdateToFullSet);
+  for (auto &PS : FS.Params)
+    Changed |= updateOneUse(PS.Use, UpdateToFullSet);
+
+  if (Changed) {
+    LLVM_DEBUG(dbgs() << "=== update [" << FS.UpdateCount
+                      << (UpdateToFullSet ? ", full-set" : "") << "] "
+                      << FS.getName() << "\n");
+    // Callers of this function may need updating.
+    for (auto &CallerID : Callers[Callee])
+      WorkList.insert(CallerID);
+
+    ++FS.UpdateCount;
+  }
+}
+
+void StackSafetyDataFlowAnalysis::runDataFlow() {
+  Callers.clear();
+  WorkList.clear();
+
+  SmallVector<const GlobalValue *, 16> Callees;
+  for (auto &F : Functions) {
+    Callees.clear();
+    StackSafetyInfo::FunctionInfo &FS = F.second;
+    for (auto &AS : FS.Allocas)
+      for (auto &CS : AS.Use.Calls)
+        Callees.push_back(CS.Callee);
+    for (auto &PS : FS.Params)
+      for (auto &CS : PS.Use.Calls)
+        Callees.push_back(CS.Callee);
+
+    llvm::sort(Callees);
+    Callees.erase(std::unique(Callees.begin(), Callees.end()), Callees.end());
+
+    for (auto &Callee : Callees)
+      Callers[Callee].push_back(F.first);
+  }
+
+  updateAllNodes();
+
+  while (!WorkList.empty()) {
+    const GlobalValue *Callee = WorkList.back();
+    WorkList.pop_back();
+    updateOneNode(Callee);
+  }
+}
+
+void StackSafetyDataFlowAnalysis::verifyFixedPoint() {
+  WorkList.clear();
+  updateAllNodes();
+  assert(WorkList.empty());
+}
+
+StackSafetyGlobalInfo StackSafetyDataFlowAnalysis::run() {
+  runDataFlow();
+  LLVM_DEBUG(verifyFixedPoint());
+
+  StackSafetyGlobalInfo SSI;
+  for (auto &F : Functions)
+    SSI.emplace(F.first, std::move(F.second));
+  return SSI;
+}
+
 void print(const StackSafetyGlobalInfo &SSI, raw_ostream &O, const Module &M) {
-  O << "Not Implemented\n";
+  size_t Count = 0;
+  for (auto &F : M.functions())
+    if (!F.isDeclaration()) {
+      SSI.find(&F)->second.print(O);
+      O << "\n";
+      ++Count;
+    }
+  for (auto &A : M.aliases()) {
+    SSI.find(&A)->second.print(O);
+    O << "\n";
+    ++Count;
+  }
+  assert(Count == SSI.size() && "Unexpected functions in the result");
 }
 
 } // end anonymous namespace
 
 StackSafetyInfo::StackSafetyInfo() = default;
 StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
 StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
 
bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
   SSI = StackSafetyInfo(SSLA.run());
   return false;
 }
 
 AnalysisKey StackSafetyGlobalAnalysis::Key;
 
 StackSafetyGlobalInfo
 StackSafetyGlobalAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
-  return {};
+  FunctionAnalysisManager &FAM =
+      AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+
+  StackSafetyDataFlowAnalysis SSDFA(
+      M, [&FAM](Function &F) -> const StackSafetyInfo & {
+        return FAM.getResult<StackSafetyAnalysis>(F);
+      });
+  return SSDFA.run();
 }
 
 PreservedAnalyses StackSafetyGlobalPrinterPass::run(Module &M,
                                                     ModuleAnalysisManager &AM) {
   OS << "'Stack Safety Analysis' for module '" << M.getName() << "'\n";
   print(AM.getResult<StackSafetyGlobalAnalysis>(M), OS, M);
   return PreservedAnalyses::all();
 }
void StackSafetyGlobalInfoWrapperPass::print(raw_ostream &O,
   ::print(SSI, O, *M);
 }
 
 void StackSafetyGlobalInfoWrapperPass::getAnalysisUsage(
     AnalysisUsage &AU) const {
   AU.addRequired<StackSafetyInfoWrapperPass>();
 }
 
-bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) { return false; }
+bool StackSafetyGlobalInfoWrapperPass::runOnModule(Module &M) {
+  StackSafetyDataFlowAnalysis SSDFA(
+      M, [this](Function &F) -> const StackSafetyInfo & {
+        return getAnalysis<StackSafetyInfoWrapperPass>(F).getResult();
+      });
+  SSI = SSDFA.run();
+  return false;
+}
 
 static const char LocalPassArg[] = "stack-safety-local";
 static const char LocalPassName[] = "Stack Safety Local Analysis";
 INITIALIZE_PASS_BEGIN(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
                       false, true)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_END(StackSafetyInfoWrapperPass, LocalPassArg, LocalPassName,
                     false, true)
 
 static const char GlobalPassName[] = "Stack Safety Analysis";
 INITIALIZE_PASS_BEGIN(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
                       GlobalPassName, false, false)
 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
 INITIALIZE_PASS_END(StackSafetyGlobalInfoWrapperPass, DEBUG_TYPE,
                     GlobalPassName, false, false)

llvm/trunk/test/Analysis/StackSafetyAnalysis/Inputs/ipa-alias.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@InterposableAliasWrite1 = linkonce dso_local alias void(i8*), void(i8*)* @Write1
+
+@PreemptableAliasWrite1 = dso_preemptable alias void(i8*), void(i8*)* @Write1
+@AliasToPreemptableAliasWrite1 = dso_local alias void(i8*), void(i8*)* @PreemptableAliasWrite1
+
+@AliasWrite1 = dso_local alias void(i8*), void(i8*)* @Write1
+
+@BitcastAliasWrite1 = dso_local alias void(i32*), bitcast (void(i8*)* @Write1 to void(i32*)*)
+@AliasToBitcastAliasWrite1 = dso_local alias void(i8*), bitcast (void(i32*)* @BitcastAliasWrite1 to void(i8*)*)
+
+define dso_local void @Write1(i8* %p) {
+entry:
+  store i8 0, i8* %p, align 1
+  ret void
+}

llvm/trunk/test/Analysis/StackSafetyAnalysis/Inputs/ipa.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define dso_local void @Write1(i8* %p) {
+entry:
+  store i8 0, i8* %p, align 1
+  ret void
+}
+
+define dso_local void @Write4(i8* %p) {
+entry:
+  %0 = bitcast i8* %p to i32*
+  store i32 0, i32* %0, align 1
+  ret void
+}
+
+define dso_local void @Write4_2(i8* %p, i8* %q) {
+entry:
+  %0 = bitcast i8* %p to i32*
+  store i32 0, i32* %0, align 1
+  %1 = bitcast i8* %q to i32*
+  store i32 0, i32* %1, align 1
+  ret void
+}
+
+define dso_local void @Write8(i8* %p) {
+entry:
+  %0 = bitcast i8* %p to i64*
+  store i64 0, i64* %0, align 1
+  ret void
+}
+
+define dso_local i8* @WriteAndReturn8(i8* %p) {
+entry:
+  store i8 0, i8* %p, align 1
+  ret i8* %p
+}
+
+declare dso_local void @ExternalCall(i8* %p)
+
+define dso_preemptable void @PreemptableWrite1(i8* %p) {
+entry:
+  store i8 0, i8* %p, align 1
+  ret void
+}
+
+define linkonce dso_local void @InterposableWrite1(i8* %p) {
+entry:
+  store i8 0, i8* %p, align 1
+  ret void
+}
+
+define dso_local i8* @ReturnDependent(i8* %p) {
+entry:
+  %p2 = getelementptr i8, i8* %p, i64 2
+  ret i8* %p2
+}
+
+; access range [2, 6)
+define dso_local void @Rec0(i8* %p) {
+entry:
+  %p1 = getelementptr i8, i8* %p, i64 2
+  call void @Write4(i8* %p1)
+  ret void
+}
+
+; access range [3, 7)
+define dso_local void @Rec1(i8* %p) {
+entry:
+  %p1 = getelementptr i8, i8* %p, i64 1
+  call void @Rec0(i8* %p1)
+  ret void
+}
+
+; access range [-2, 2)
+define dso_local void @Rec2(i8* %p) {
+entry:
+  %p1 = getelementptr i8, i8* %p, i64 -5
+  call void @Rec1(i8* %p1)
+  ret void
+}
+
+; Recursive function that passes %acc unchanged => access range [0, 4).
+define dso_local void @RecursiveNoOffset(i32* %p, i32 %size, i32* %acc) {
+entry:
+  %cmp = icmp eq i32 %size, 0
+  br i1 %cmp, label %return, label %if.end
+
+if.end:
+  %0 = load i32, i32* %p, align 4
+  %1 = load i32, i32* %acc, align 4
+  %add = add nsw i32 %1, %0
+  store i32 %add, i32* %acc, align 4
+  %add.ptr = getelementptr inbounds i32, i32* %p, i64 1
+  %sub = add nsw i32 %size, -1
+  tail call void @RecursiveNoOffset(i32* %add.ptr, i32 %sub, i32* %acc)
+  ret void
+
+return:
+  ret void
+}
+
+; Recursive function that advances %acc on each iteration => access range unlimited.
+define dso_local void @RecursiveWithOffset(i32 %size, i32* %acc) {
+entry:
+  %cmp = icmp eq i32 %size, 0
+  br i1 %cmp, label %return, label %if.end
+
+if.end:
+  store i32 0, i32* %acc, align 4
+  %acc2 = getelementptr inbounds i32, i32* %acc, i64 1
+  %sub = add nsw i32 %size, -1
+  tail call void @RecursiveWithOffset(i32 %sub, i32* %acc2)
+  ret void
+
+return:
+  ret void
+}

llvm/trunk/test/Analysis/StackSafetyAnalysis/ipa-alias.ll

+; Test IPA over a single combined file
+; RUN: llvm-as %s -o %t0.bc
+; RUN: llvm-as %S/Inputs/ipa-alias.ll -o %t1.bc
+; RUN: llvm-link %t0.bc %t1.bc -o %t.combined.bc
+; RUN: opt -S -analyze -stack-safety-local %t.combined.bc | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -passes="print<stack-safety-local>" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -analyze -stack-safety %t.combined.bc | FileCheck %s --check-prefixes=CHECK,GLOBAL
+; RUN: opt -S -passes="print-stack-safety" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @PreemptableAliasWrite1(i8* %p)
+declare void @AliasToPreemptableAliasWrite1(i8* %p)
+
+declare void @InterposableAliasWrite1(i8* %p)
+; Aliases to interposable aliases are not allowed
+
+declare void @AliasWrite1(i8* %p)
+
+declare void @BitcastAliasWrite1(i32* %p)
+declare void @AliasToBitcastAliasWrite1(i8* %p)
+
+; Call to dso_preemptable alias to a dso_local aliasee
+define void @PreemptableAliasCall() {
+; CHECK-LABEL: @PreemptableAliasCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x1[1]: empty-set, @PreemptableAliasWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x1[1]: full-set, @PreemptableAliasWrite1(arg0, [0,1)){{$}}
+; LOCAL-NEXT: x2[1]: empty-set, @AliasToPreemptableAliasWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x2[1]: [0,1), @AliasToPreemptableAliasWrite1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x1 = alloca i8
+  call void @PreemptableAliasWrite1(i8* %x1)
+
+  %x2 = alloca i8
+; Alias to a preemptable alias is not preemptable
+  call void @AliasToPreemptableAliasWrite1(i8* %x2)
+  ret void
+}
+
+; Call to an interposable alias to a non-interposable aliasee
+define void @InterposableAliasCall() {
+; CHECK-LABEL: @InterposableAliasCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[1]: empty-set, @InterposableAliasWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[1]: full-set, @InterposableAliasWrite1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i8
+; ThinLTO can resolve the prevailing implementation for interposable definitions.
+  call void @InterposableAliasWrite1(i8* %x)
+  ret void
+}
+
+; Call to a dso_local/non-interposable alias/aliasee
+define void @AliasCall() {
+; CHECK-LABEL: @AliasCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[1]: empty-set, @AliasWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[1]: [0,1), @AliasWrite1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i8
+  call void @AliasWrite1(i8* %x)
+  ret void
+}
+
+; Call to a bitcasted dso_local/non-interposable alias/aliasee
+define void @BitcastAliasCall() {
+; CHECK-LABEL: @BitcastAliasCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x1[4]: empty-set, @BitcastAliasWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x1[4]: [0,1), @BitcastAliasWrite1(arg0, [0,1)){{$}}
+; LOCAL-NEXT: x2[1]: empty-set, @AliasToBitcastAliasWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x2[1]: [0,1), @AliasToBitcastAliasWrite1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x1 = alloca i32
+  call void @BitcastAliasWrite1(i32* %x1)
+  %x2 = alloca i8
+  call void @AliasToBitcastAliasWrite1(i8* %x2)
+  ret void
+}
+
+; The rest is from Inputs/ipa-alias.ll
+
+; CHECK-LABEL: @Write1{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; GLOBAL-LABEL: @InterposableAliasWrite1 interposable{{$}}
+; GLOBAL-NEXT: args uses:
+; GLOBAL-NEXT: <N/A>[]: [0,1), @Write1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: allocas uses:
+; GLOBAL-NOT: ]:
+
+; GLOBAL-LABEL: @PreemptableAliasWrite1 dso_preemptable{{$}}
+; GLOBAL-NEXT: args uses:
+; GLOBAL-NEXT: <N/A>[]: [0,1), @Write1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: allocas uses:
+; GLOBAL-NOT: ]:
+
+; GLOBAL-LABEL: @AliasToPreemptableAliasWrite1{{$}}
+; GLOBAL-NEXT: args uses:
+; GLOBAL-NEXT: <N/A>[]: [0,1), @Write1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: allocas uses:
+; GLOBAL-NOT: ]:
+
+; GLOBAL-LABEL: @AliasWrite1{{$}}
+; GLOBAL-NEXT: args uses:
+; GLOBAL-NEXT: <N/A>[]: [0,1), @Write1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: allocas uses:
+; GLOBAL-NOT: ]:
+
+; GLOBAL-LABEL: @BitcastAliasWrite1{{$}}
+; GLOBAL-NEXT: args uses:
+; GLOBAL-NEXT: <N/A>[]: [0,1), @Write1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: allocas uses:
+; GLOBAL-NOT: ]:
+
+; GLOBAL-LABEL: @AliasToBitcastAliasWrite1{{$}}
+; GLOBAL-NEXT: args uses:
+; GLOBAL-NEXT: <N/A>[]: [0,1), @Write1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: allocas uses:
+; GLOBAL-NOT: ]:

llvm/trunk/test/Analysis/StackSafetyAnalysis/ipa.ll

+; RUN: llvm-as %s -o %t0.bc
+; RUN: llvm-as %S/Inputs/ipa.ll -o %t1.bc
+; RUN: llvm-link -disable-lazy-loading %t0.bc %t1.bc -o %t.combined.bc
+; RUN: opt -S -analyze -stack-safety-local %t.combined.bc | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -passes="print<stack-safety-local>" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -analyze -stack-safety %t.combined.bc | FileCheck %s --check-prefixes=CHECK,GLOBAL
+; RUN: opt -S -passes="print-stack-safety" -disable-output %t.combined.bc 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @Write1(i8* %p)
+declare void @Write4(i8* %p)
+declare void @Write4_2(i8* %p, i8* %q)
+declare void @Write8(i8* %p)
+declare dso_local i8* @WriteAndReturn8(i8* %p)
+declare dso_local void @ExternalCall(i8* %p)
+declare void @PreemptableWrite1(i8* %p)
+declare void @InterposableWrite1(i8* %p)
+declare i8* @ReturnDependent(i8* %p)
+declare void @Rec2(i8* %p)
+declare void @RecursiveNoOffset(i32* %p, i32 %size, i32* %acc)
+declare void @RecursiveWithOffset(i32 %size, i32* %acc)
+
+; Basic out-of-bounds.
+define void @f1() {
+; CHECK-LABEL: @f1 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @Write8(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: [0,8), @Write8(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @Write8(i8* %x1)
+  ret void
+}
+
+; Basic in-bounds.
+define void @f2() {
+; CHECK-LABEL: @f2 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @Write1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: [0,1), @Write1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @Write1(i8* %x1)
+  ret void
+}
+
+; Another basic in-bounds.
+define void @f3() {
+; CHECK-LABEL: @f3 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @Write4(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: [0,4), @Write4(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @Write4(i8* %x1)
+  ret void
+}
+
+; In-bounds with offset.
+define void @f4() {
+; CHECK-LABEL: @f4 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @Write1(arg0, [1,2)){{$}}
+; GLOBAL-NEXT: x[4]: [1,2), @Write1(arg0, [1,2)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 1
+  call void @Write1(i8* %x2)
+  ret void
+}
+
+; Out-of-bounds with offset.
+define void @f5() {
+; CHECK-LABEL: @f5 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: empty-set, @Write4(arg0, [1,2)){{$}}
+; GLOBAL-NEXT: [1,5), @Write4(arg0, [1,2)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 1
+  call void @Write4(i8* %x2)
+  ret void
+}
+
+; External call.
+define void @f6() {
+; CHECK-LABEL: @f6 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @ExternalCall(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: full-set, @ExternalCall(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @ExternalCall(i8* %x1)
+  ret void
+}
+
+; Call to dso_preemptable function
+define void @PreemptableCall() {
+; CHECK-LABEL: @PreemptableCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @PreemptableWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: full-set, @PreemptableWrite1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @PreemptableWrite1(i8* %x1)
+  ret void
+}
+
+; Call to function with interposable linkage
+define void @InterposableCall() {
+; CHECK-LABEL: @InterposableCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @InterposableWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: full-set, @InterposableWrite1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @InterposableWrite1(i8* %x1)
+  ret void
+}
+
+; Call to function with private linkage
+define void @PrivateCall() {
+; CHECK-LABEL: @PrivateCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @PrivateWrite1(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: [0,1), @PrivateWrite1(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @PrivateWrite1(i8* %x1)
+  ret void
+}
+
+define private void @PrivateWrite1(i8* %p) {
+; CHECK-LABEL: @PrivateWrite1{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+entry:
+  store i8 0, i8* %p, align 1
+  ret void
+}
+
+; Caller returns a dependent value.
+; FIXME: alloca considered unsafe even if the return value is unused.
+define void @f7() {
+; CHECK-LABEL: @f7 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[4]: empty-set, @ReturnDependent(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[4]: full-set, @ReturnDependent(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = call i8* @ReturnDependent(i8* %x1)
+  ret void
+}
+
+define void @f8left() {
+; CHECK-LABEL: @f8left dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [2,3)){{$}}
+; GLOBAL-NEXT: x[8]: [0,4), @Rec2(arg0, [2,3)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 2
+; 2 + [-2, 2) = [0, 4) => OK
+  call void @Rec2(i8* %x2)
+  ret void
+}
+
+define void @f8right() {
+; CHECK-LABEL: @f8right dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [6,7)){{$}}
+; GLOBAL-NEXT: x[8]: [4,8), @Rec2(arg0, [6,7)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 6
+; 6 + [-2, 2) = [4, 8) => OK
+  call void @Rec2(i8* %x2)
+  ret void
+}
+
+define void @f8oobleft() {
+; CHECK-LABEL: @f8oobleft dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [1,2)){{$}}
+; GLOBAL-NEXT: x[8]: [-1,3), @Rec2(arg0, [1,2)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 1
+; 1 + [-2, 2) = [-1, 3) => NOT OK
+  call void @Rec2(i8* %x2)
+  ret void
+}
+
+define void @f8oobright() {
+; CHECK-LABEL: @f8oobright dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Rec2(arg0, [7,8)){{$}}
+; GLOBAL-NEXT: x[8]: [5,9), @Rec2(arg0, [7,8)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 7
+; 7 + [-2, 2) = [5, 9) => NOT OK
+  call void @Rec2(i8* %x2)
+  ret void
+}
+
+define void @TwoArguments() {
+; CHECK-LABEL: @TwoArguments dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [0,1)), @Write4_2(arg0, [4,5)){{$}}
+; GLOBAL-NEXT: x[8]: [0,8), @Write4_2(arg1, [0,1)), @Write4_2(arg0, [4,5)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 4
+  call void @Write4_2(i8* %x2, i8* %x1)
+  ret void
+}
+
+define void @TwoArgumentsOOBOne() {
+; CHECK-LABEL: @TwoArgumentsOOBOne dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [0,1)), @Write4_2(arg0, [5,6)){{$}}
+; GLOBAL-NEXT: x[8]: [0,9), @Write4_2(arg1, [0,1)), @Write4_2(arg0, [5,6)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 5
+  call void @Write4_2(i8* %x2, i8* %x1)
+  ret void
+}
+
+define void @TwoArgumentsOOBOther() {
+; CHECK-LABEL: @TwoArgumentsOOBOther dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [4,5)){{$}}
+; GLOBAL-NEXT: x[8]: [-1,8), @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [4,5)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x0 = bitcast i64* %x to i8*
+  %x1 = getelementptr i8, i8* %x0, i64 -1
+  %x2 = getelementptr i8, i8* %x0, i64 4
+  call void @Write4_2(i8* %x2, i8* %x1)
+  ret void
+}
+
+define void @TwoArgumentsOOBBoth() {
+; CHECK-LABEL: @TwoArgumentsOOBBoth dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[8]: empty-set, @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [5,6)){{$}}
+; GLOBAL-NEXT: x[8]: [-1,9), @Write4_2(arg1, [-1,0)), @Write4_2(arg0, [5,6)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x0 = bitcast i64* %x to i8*
+  %x1 = getelementptr i8, i8* %x0, i64 -1
+  %x2 = getelementptr i8, i8* %x0, i64 5
+  call void @Write4_2(i8* %x2, i8* %x1)
+  ret void
+}
+
+define i32 @TestRecursiveNoOffset(i32* %p, i32 %size) {
+; CHECK-LABEL: @TestRecursiveNoOffset dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; LOCAL-NEXT: p[]: empty-set, @RecursiveNoOffset(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: p[]: full-set, @RecursiveNoOffset(arg0, [0,1)){{$}}
+; CHECK-NEXT: size[]: empty-set, @RecursiveNoOffset(arg1, [0,1)){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: sum[4]: [0,4), @RecursiveNoOffset(arg2, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %sum = alloca i32, align 4
+  %0 = bitcast i32* %sum to i8*
+  store i32 0, i32* %sum, align 4
+  call void @RecursiveNoOffset(i32* %p, i32 %size, i32* %sum)
+  %1 = load i32, i32* %sum, align 4
+  ret i32 %1
+}
+
+define void @TestRecursiveWithOffset(i32 %size) {
+; CHECK-LABEL: @TestRecursiveWithOffset dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: size[]: empty-set, @RecursiveWithOffset(arg0, [0,1)){{$}}
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: sum[64]: empty-set, @RecursiveWithOffset(arg1, [0,1)){{$}}
+; GLOBAL-NEXT: sum[64]: full-set, @RecursiveWithOffset(arg1, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %sum = alloca i32, i64 16, align 4
+  call void @RecursiveWithOffset(i32 %size, i32* %sum)
+  ret void
+}
+
+; FIXME: IPA should detect that access is safe
+define void @TestUpdateArg() {
+; CHECK-LABEL: @TestUpdateArg dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[16]: empty-set, @WriteAndReturn8(arg0, [0,1)){{$}}
+; GLOBAL-NEXT: x[16]: full-set, @WriteAndReturn8(arg0, [0,1)){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i8, i64 16, align 4
+  %0 = call i8* @WriteAndReturn8(i8* %x)
+  ret void
+}
+
+; The rest is from Inputs/ipa.ll
+
+; CHECK-LABEL: @Write1{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @Write4{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,4){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @Write4_2{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,4){{$}}
+; CHECK-NEXT: q[]: [0,4){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @Write8{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,8){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @WriteAndReturn8{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: full-set{{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @PreemptableWrite1 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @InterposableWrite1 interposable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @ReturnDependent{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: full-set{{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @Rec0{{$}}
+; CHECK-NEXT: args uses:
+; LOCAL-NEXT: p[]: empty-set, @Write4(arg0, [2,3)){{$}}
+; GLOBAL-NEXT: p[]: [2,6), @Write4(arg0, [2,3)){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @Rec1{{$}}
+; CHECK-NEXT: args uses:
+; LOCAL-NEXT: p[]: empty-set, @Rec0(arg0, [1,2)){{$}}
+; GLOBAL-NEXT: p[]: [3,7), @Rec0(arg0, [1,2)){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @Rec2{{$}}
+; CHECK-NEXT: args uses:
+; LOCAL-NEXT: p[]: empty-set, @Rec1(arg0, [-5,-4)){{$}}
+; GLOBAL-NEXT: p[]: [-2,2), @Rec1(arg0, [-5,-4)){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @RecursiveNoOffset{{$}}
+; CHECK-NEXT: args uses:
+; LOCAL-NEXT: p[]: [0,4), @RecursiveNoOffset(arg0, [4,5)){{$}}
+; GLOBAL-NEXT: p[]: full-set, @RecursiveNoOffset(arg0, [4,5)){{$}}
+; CHECK-NEXT: size[]: empty-set, @RecursiveNoOffset(arg1, [4294967295,4294967296)){{$}}
+; CHECK-NEXT: acc[]: [0,4), @RecursiveNoOffset(arg2, [0,1)){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+
+; CHECK-LABEL: @RecursiveWithOffset{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: size[]: empty-set, @RecursiveWithOffset(arg0, [4294967295,4294967296)){{$}}
+; LOCAL-NEXT: acc[]: [0,4), @RecursiveWithOffset(arg1, [4,5)){{$}}
+; GLOBAL-NEXT: acc[]: full-set, @RecursiveWithOffset(arg1, [4,5)){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:

llvm/trunk/test/Analysis/StackSafetyAnalysis/local.ll

-; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s
-; RUN: opt -S -passes="print<stack-safety-local>" -disable-output < %s 2>&1 | FileCheck %s
-; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s --check-prefix=GLOBAL
-; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=GLOBAL
-
-; GLOBAL: Not Implemented
+; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -passes="print<stack-safety-local>" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s --check-prefixes=CHECK,GLOBAL
+; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @sink = global i8* null, align 8
 
 declare void @llvm.memset.p0i8.i32(i8* %dest, i8 %val, i32 %len, i1 %isvolatile)
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 %len, i1 %isvolatile)

 }
 
 declare void @Foo(i16* %p)
 
 define void @DirectCall() {
 ; CHECK-LABEL: @DirectCall dso_preemptable{{$}}
 ; CHECK-NEXT: args uses:
 ; CHECK-NEXT: allocas uses:
-; CHECK-NEXT: x[8]: empty-set, @Foo(arg0, [2,3)){{$}}
+; LOCAL-NEXT: x[8]: empty-set, @Foo(arg0, [2,3)){{$}}
+; GLOBAL-NEXT: x[8]: full-set, @Foo(arg0, [2,3)){{$}}
 ; CHECK-NOT: ]:
 entry:
   %x = alloca i64, align 4
   %x1 = bitcast i64* %x to i16*
   %x2 = getelementptr i16, i16* %x1, i64 1
   call void @Foo(i16* %x2);
   ret void
 }

llvm/trunk/test/Analysis/StackSafetyAnalysis/memintrin.ll

 ; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s
 ; RUN: opt -S -passes="print<stack-safety-local>" -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s
+; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @llvm.memset.p0i8.i32(i8* %dest, i8 %val, i32 %len, i1 %isvolatile)
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 %len, i1 %isvolatile)
 declare void @llvm.memmove.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 %len, i1 %isvolatile)
 

llvm/trunk/test/Analysis/StackSafetyAnalysis/scev-udiv.ll

+; RUN: opt -S -analyze -stack-safety-local < %s | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -passes="print<stack-safety-local>" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,LOCAL
+; RUN: opt -S -analyze -stack-safety < %s | FileCheck %s --check-prefixes=CHECK,GLOBAL
+; RUN: opt -S -passes="print-stack-safety" -disable-output < %s 2>&1 | FileCheck %s --check-prefixes=CHECK,GLOBAL
+
+; Regression test that exercises a case when a AllocaOffsetRewritten SCEV
+; could return an empty-set range. This could occur with udiv SCEVs where the
+; RHS was re-written to 0.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @ExternalFn(i64)
+
+define void @Test1() {
+; CHECK-LABEL: @Test1 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[1]: empty-set, @Divide1(arg0, full-set){{$}}
+; GLOBAL-NEXT: x[1]: full-set, @Divide1(arg0, full-set){{$}}
+; CHECK-NOT: ]:
+  %x = alloca i8
+  %int = ptrtoint i8* %x to i64
+  call void @Divide1(i64 %int)
+  ret void
+}
+
+define dso_local void @Divide1(i64 %arg) {
+; CHECK-LABEL: @Divide1{{$}}
+; CHECK-NEXT: args uses:
+; LOCAL-NEXT: arg[]: empty-set, @ExternalFn(arg0, full-set){{$}}
+; GLOBAL-NEXT: arg[]: full-set, @ExternalFn(arg0, full-set){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+  %quotient = udiv i64 undef, %arg
+  call void @ExternalFn(i64 %quotient)
+  unreachable
+}
+
+define void @Test2(i64 %arg) {
+; CHECK-LABEL: @Test2 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: arg[]: empty-set{{$}}
+; CHECK-NEXT: allocas uses:
+; LOCAL-NEXT: x[1]: empty-set, @Divide2(arg0, full-set){{$}}
+; GLOBAL-NEXT: x[1]: full-set, @Divide2(arg0, full-set){{$}}
+; CHECK-NOT: ]:
+  %x = alloca i8
+  %int = ptrtoint i8* %x to i64
+  call void @Divide2(i64 %int)
+  ret void
+}
+
+define dso_local void @Divide2(i64 %arg) {
+; CHECK-LABEL: @Divide2{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: arg[]: full-set{{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NOT: ]:
+  %x = inttoptr i64 %arg to i8*
+  %quotient = udiv i64 undef, %arg
+  %arrayidx = getelementptr i8, i8* %x, i64 %quotient
+  load i8, i8* %arrayidx
+  unreachable
+}