[stack-safety] Local analysis implementation

[vitalybuka]

Summary

Analysis produces StackSafetyInfo which contains information with how allocas
and parameters were used in functions.

From prototype by Evgenii Stepanov and Vlad Tsyrklevich.

[eugenis]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

58

Please add a short comment to this struct.
Maybe rename it to CallUseInfo? It describes a use of an address in a function call argument, not the call itself; also mention that Range is not access range, but an offset range.

239

Please update the comment. This is not only about safe stack.

[vitalybuka]

docs

[vlad.tsyrklevich]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

119

Would be worth copying over the comment from the SafeStack pass:

/// Calculate the allocation size of a given alloca. Returns 0 if the
/// size can not be statically determined.

133

Mark this a TODO and update the struct name.

135

This uses a different naming convention than the structs above though it's part of the same 'type set' as the *Info structs above which is confusing. Couldn't immediately think of a fix that makes it nicer though. Might just be worth a comment to at least be explicit about why this is.

321

Is this comment outdated? I can't figure out what it's referring to, Maybe @eugenis knows.

[vitalybuka]

addressing @vlad.tsyrklevich comments

[vitalybuka]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

135

renamed
WDYT?

321

This is correct but not optimal behavior. I've added FIXME: into "case Instruction::Ret:" and new test into IPA analysis

[eugenis]

llvm/lib/Analysis/StackSafetyAnalysis.cpp

321

Right. We could track return values of function call the same as we track allocas and arguments, and have each function describe its return value as possibly being equal to an argument pointer with an offset range. I have not seen too many cases like that, and opted for simplicity: consider anything that escapes through return value untrackable and, on the caller side, consider return values safe (i.e. unrelated to any tracked object).

Btw, I don't like the name "leak". I think the usual term for this is escaped pointer / alloca, but full-set range is also possible when we can not prove anything about the range of offsets in a memory access - even if it is the only access. Rename it to smth like setUnknown() ?

[vitalybuka]

Rename setLeak

[eugenis]

LGTM

[vitalybuka]

update

[vlad.tsyrklevich]

I've been busy and still haven't had a chance to run down why the behavior of %z in the NonConstantOffset() test changes so oddly with different select values.

llvm/lib/Analysis/StackSafetyAnalysis.cpp

30

"mentions of the alloca in addition expressions with zero" (I didn't update the comment after this change was made.)

135

Looks good, 'FunctionStackSummary' still needs to be updated and that comment should also have a TODO or FIXME to indicate it's a future idea.

[vitalybuka]

In D54504#1308376, @vlad.tsyrklevich wrote:

I've been busy and still haven't had a chance to run down why the behavior of %z in the NonConstantOffset() test changes so oddly with different select values.

I'd like to submit as-is and investigate later and fix if needed, so I can have less patches to rebase.
This code is not hooked into any useful functionality yet.

[vlad.tsyrklevich]

modulo nits on updating comments that I left earlier

[vitalybuka]

Renames and comments

llvm/include/llvm/Analysis/StackSafetyAnalysis.h

 #ifndef LLVM_ANALYSIS_STACKSAFETYANALYSIS_H
 #define LLVM_ANALYSIS_STACKSAFETYANALYSIS_H
 
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
 
+struct StackSafetyFunctionInfo;
+
+/// Function-local stack safety analysis interface provided to other analysis
+/// consumers like the ModuleSummaryAnalysis.
 class StackSafetyInfo {
+  friend struct StackSafetyFunctionInfo;
+  std::unique_ptr<StackSafetyFunctionInfo> Info;
+
 public:
+  StackSafetyInfo();
+  StackSafetyInfo(StackSafetyFunctionInfo &&Info);
+  StackSafetyInfo(StackSafetyInfo &&);
+  StackSafetyInfo &operator=(StackSafetyInfo &&);
+  ~StackSafetyInfo();
+
+  // TODO: Add useful for client methods.
   void print(raw_ostream &O) const;
 };
 
 /// Function-local stack safety analysis pass.
 class StackSafetyAnalysis : public AnalysisInfoMixin<StackSafetyAnalysis> {
   friend AnalysisInfoMixin<StackSafetyAnalysis>;
   static AnalysisKey Key;
 

llvm/lib/Analysis/StackSafetyAnalysis.cpp

 //===- StackSafetyAnalysis.cpp - Safe Stack Insertion
 //-------------------------------===//
 //
 //                     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"
 
-AnalysisKey StackSafetyAnalysis::Key;
+namespace {
+
+/// Rewrite an SCEV expression for a memory access address to an expression that
+/// represents offset from the given alloca.
+///
+/// The implementation simply replaces all mentions of the alloca with zero.
+class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
+  const Value *AllocaPtr;
+
+public:
+  AllocaOffsetRewriter(ScalarEvolution &SE, const Value *AllocaPtr)
+      : SCEVRewriteVisitor(SE), AllocaPtr(AllocaPtr) {}
+
+  const SCEV *visit(const SCEV *Expr) {
+    // Only re-write the expression if the alloca is used in an addition
+    // expression (it can be used in other types of expressions if it's cast to
+    // an int and passed as an argument.)
+    if (!isa<SCEVAddRecExpr>(Expr) && !isa<SCEVAddExpr>(Expr) &&
+        !isa<SCEVUnknown>(Expr))
+      return Expr;
+    return SCEVRewriteVisitor<AllocaOffsetRewriter>::visit(Expr);
+  }
+
+  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+    // FIXME: look through one or several levels of definitions?
+    // This can be inttoptr(AllocaPtr) and SCEV would not unwrap
+    // it for us.
+    if (Expr->getValue() == AllocaPtr)
+      return SE.getZero(Expr->getType());
+    return Expr;
+  }
+};
+
+struct CallInfo {
+  const GlobalValue *GV = nullptr;
+  size_t ParamNo = 0;
+  // Range should never set to empty-set, that is an invalid access range
+  // that can cause empty-set to be propagated with ConstantRange::add
+  ConstantRange Range;
+  CallInfo(const GlobalValue *GV, size_t ParamNo, ConstantRange Range)
+      : GV(GV), ParamNo(ParamNo), Range(Range) {}
+
+  StringRef getName() const { return GV->getName(); }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const CallInfo &C) {
+  return OS << "@" << C.getName() << "(arg" << C.ParamNo << ", " << C.Range
+            << ")";
+}
+
+struct UseInfo {
+  // Range is allowed to be empty-set when there are no known
+  // accesses.
+  ConstantRange Range{64, false};
+  SmallVector<CallInfo, 4> Calls;
+
+  void updateRange(ConstantRange R) { Range = Range.unionWith(R); }
+  void setLeak() { Range = ConstantRange(64); }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const UseInfo &U) {
+  OS << U.Range;
+  for (auto &Call : U.Calls)
+    OS << ", " << Call;
+  return OS;
+}
+
+struct AllocaInfo {
+  const AllocaInst *AI = nullptr;
+  uint64_t Size = 0;
+  UseInfo Use;
+
+  AllocaInfo(const AllocaInst *AI, uint64_t Size) : AI(AI), Size(Size) {}
+
+  StringRef getName() const { return AI->getName(); }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const AllocaInfo &A) {
+  return OS << A.getName() << "[" << A.Size << "]: " << A.Use;
+}
+
+struct ParamInfo {
+  const Argument *Arg = nullptr;
+  UseInfo Use;
+
+  explicit ParamInfo(const Argument *Arg) : Arg(Arg) {}
+
+  StringRef getName() const { return Arg ? Arg->getName() : "<N/A>"; }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const ParamInfo &P) {
+  return OS << P.getName() << "[]: " << P.Use;
+}
+
+uint64_t getStaticAllocaAllocationSize(const AllocaInst *AI) {
+  const DataLayout &DL = AI->getModule()->getDataLayout();
+  uint64_t Size = DL.getTypeAllocSize(AI->getAllocatedType());
+  if (AI->isArrayAllocation()) {
+    auto C = dyn_cast<ConstantInt>(AI->getArraySize());
+    if (!C)
+      return 0;
+    Size *= C->getZExtValue();
+  }
+  return Size;
+}
+
+} // end anonymous namespace
+
+// FunctionStackSummary could also describe return value as depending on one or
+// more of its arguments.
+struct llvm::StackSafetyFunctionInfo {
+  // May be a Function or a GlobalAlias
+  const GlobalValue *GV = nullptr;
+  SmallVector<AllocaInfo, 4> Allocas;
+  SmallVector<ParamInfo, 4> Params;
+
+  StackSafetyFunctionInfo(const StackSafetyInfo &SSI)
+      : StackSafetyFunctionInfo(*SSI.Info) {}
+
+  explicit StackSafetyFunctionInfo(const Function *F) : GV(F){};
+
+  StackSafetyFunctionInfo(StackSafetyFunctionInfo &&) = 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 {
+    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:
+  StackSafetyFunctionInfo(const StackSafetyFunctionInfo &) = default;
+};
+
+namespace {
+
+class StackSafetyLocalAnalysis {
+  const Function &F;
+  const DataLayout &DL;
+  ScalarEvolution &SE;
+
+  ConstantRange OffsetFromAlloca(Value *Addr, const Value *AllocaPtr);
+  ConstantRange GetAccessRange(Value *Addr, const Value *AllocaPtr,
+                               uint64_t AccessSize);
+  ConstantRange GetMemIntrinsicAccessRange(const MemIntrinsic *MI, const Use &U,
+                                           const Value *AllocaPtr);
+
+  bool analyzeAllUses(const Value *Ptr, UseInfo &AS);
+
+public:
+  StackSafetyLocalAnalysis(const Function &F, ScalarEvolution &SE)
+      : F(F), DL(F.getParent()->getDataLayout()), SE(SE) {}
+
+  // Run the transformation on the associated function.
+  StackSafetyInfo run();
+};
+
+ConstantRange
+StackSafetyLocalAnalysis::OffsetFromAlloca(Value *Addr,
+                                           const Value *AllocaPtr) {
+  if (!SE.isSCEVable(Addr->getType()))
+    return ConstantRange(64);
+
+  AllocaOffsetRewriter Rewriter(SE, AllocaPtr);
+  const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr));
+  ConstantRange OffsetRange = SE.getUnsignedRange(Expr).zextOrTrunc(64);
+  assert(!OffsetRange.isEmptySet());
+  return OffsetRange;
+}
+
+ConstantRange StackSafetyLocalAnalysis::GetAccessRange(Value *Addr,
+                                                       const Value *AllocaPtr,
+                                                       uint64_t AccessSize) {
+  if (!SE.isSCEVable(Addr->getType()))
+    return ConstantRange(64);
+
+  AllocaOffsetRewriter Rewriter(SE, AllocaPtr);
+  const SCEV *Expr = Rewriter.visit(SE.getSCEV(Addr));
+
+  ConstantRange AccessStartRange = SE.getUnsignedRange(Expr).zextOrTrunc(64);
+  ConstantRange SizeRange = ConstantRange(APInt(64, 0), APInt(64, AccessSize));
+  ConstantRange AccessRange = AccessStartRange.add(SizeRange);
+  assert(!AccessRange.isEmptySet());
+  return AccessRange;
+}
+
+ConstantRange StackSafetyLocalAnalysis::GetMemIntrinsicAccessRange(
+    const MemIntrinsic *MI, const Use &U, const Value *AllocaPtr) {
+  if (auto MTI = dyn_cast<MemTransferInst>(MI)) {
+    if (MTI->getRawSource() != U && MTI->getRawDest() != U)
+      return ConstantRange(APInt(64, 0), APInt(64, 1));
+  } else {
+    if (MI->getRawDest() != U)
+      return ConstantRange(APInt(64, 0), APInt(64, 1));
+  }
+  const auto *Len = dyn_cast<ConstantInt>(MI->getLength());
+  // Non-constant size => unsafe. FIXME: try SCEV getRange.
+  if (!Len)
+    return ConstantRange(64);
+  ConstantRange AccessRange = GetAccessRange(U, AllocaPtr, Len->getZExtValue());
+  return AccessRange;
+}
+
+/// Check whether a given allocation must be put on the safe
+/// stack or not. The function analyzes all uses of AI and checks whether it is
+/// only accessed in a memory safe way (as decided statically).
+bool StackSafetyLocalAnalysis::analyzeAllUses(const Value *Ptr, UseInfo &US) {
+  // Go through all uses of this alloca and check whether all accesses to the
+  // allocated object are statically known to be memory safe and, hence, the
+  // object can be placed on the safe stack.
+  SmallPtrSet<const Value *, 16> Visited;
+  SmallVector<const Value *, 8> WorkList;
+  WorkList.push_back(Ptr);
+
+  // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
+  while (!WorkList.empty()) {
+    const Value *V = WorkList.pop_back_val();
+    for (const Use &UI : V->uses()) {
+      auto I = cast<const Instruction>(UI.getUser());
+      assert(V == UI.get());
+
+      switch (I->getOpcode()) {
+      case Instruction::Load: {
+        US.updateRange(
+            GetAccessRange(UI, Ptr, DL.getTypeStoreSize(I->getType())));
+        break;
+      }
 
-void StackSafetyInfo::print(raw_ostream &O) const { O << "Not Implemented\n"; }
+      case Instruction::VAArg:
+        // "va-arg" from a pointer is safe.
+        break;
+      case Instruction::Store: {
+        if (V == I->getOperand(0)) {
+          // Stored the pointer - conservatively assume it may be unsafe.
+          US.setLeak();
+          return false;
+        }
+        US.updateRange(GetAccessRange(
+            UI, Ptr, DL.getTypeStoreSize(I->getOperand(0)->getType())));
+        break;
+      }
+
+      case Instruction::Ret:
+        // Information leak.
+        US.setLeak();
+        return false;
+
+      case Instruction::Call:
+      case Instruction::Invoke: {
+        ImmutableCallSite CS(I);
+
+        if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+          if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
+              II->getIntrinsicID() == Intrinsic::lifetime_end)
+            break;
+        }
+
+        if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
+          US.updateRange(GetMemIntrinsicAccessRange(MI, UI, Ptr));
+          break;
+        }
+
+        // Ignore value used as call destination.
+        const Value *CV = CS.getCalledValue();
+        if (CV == V)
+          break;
+
+        // FIXME: consult devirt?
+        // Do not follow aliases, otherwise we could inadvertently follow
+        // dso_preemptable aliases or aliases with interposable linkage.
+        const GlobalValue *Callee =
+            dyn_cast<GlobalValue>(CV->stripPointerCastsNoFollowAliases());
+        if (!Callee) {
+          US.setLeak();
+          return false;
+        }
+
+        assert(isa<Function>(Callee) || isa<GlobalAlias>(Callee));
+
+        ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
+        for (ImmutableCallSite::arg_iterator A = B; A != E; ++A) {
+          if (A->get() == V) {
+            ConstantRange OffsetRange = OffsetFromAlloca(UI, Ptr);
+            US.Calls.emplace_back(Callee, A - B, OffsetRange);
+          }
+        }
+        // Don't visit function return value: if it depends on the alloca, then
+        // argument range would be full-set.
+
+        break;
+      }
+
+      default:
+        if (Visited.insert(I).second)
+          WorkList.push_back(cast<const Instruction>(I));
+      }
+    }
+  }
+
+  return true;
+}
+
+StackSafetyInfo StackSafetyLocalAnalysis::run() {
+  StackSafetyFunctionInfo Info(&F);
+  assert(!F.isDeclaration() &&
+         "Can't run StackSafety on a function declaration");
+
+  LLVM_DEBUG(dbgs() << "[StackSafety] " << F.getName() << "\n");
+
+  for (auto &I : instructions(F)) {
+    if (auto AI = dyn_cast<AllocaInst>(&I)) {
+      Info.Allocas.emplace_back(AI, getStaticAllocaAllocationSize(AI));
+      AllocaInfo &AS = Info.Allocas.back();
+      analyzeAllUses(AI, AS.Use);
+    }
+  }
+
+  for (const Argument &A : make_range(F.arg_begin(), F.arg_end())) {
+    Info.Params.emplace_back(&A);
+    ParamInfo &PS = Info.Params.back();
+    analyzeAllUses(&A, PS.Use);
+  }
+
+  LLVM_DEBUG(dbgs() << "[StackSafety] done\n");
+  LLVM_DEBUG(Info.print(dbgs()));
+  return StackSafetyInfo(std::move(Info));
+}
+
+} // end anonymous namespace
+
+StackSafetyInfo::StackSafetyInfo() = default;
+StackSafetyInfo::StackSafetyInfo(StackSafetyInfo &&) = default;
+StackSafetyInfo &StackSafetyInfo::operator=(StackSafetyInfo &&) = default;
+
+StackSafetyInfo::StackSafetyInfo(StackSafetyFunctionInfo &&Info)
+    : Info(new StackSafetyFunctionInfo(std::move(Info))) {}
+
+StackSafetyInfo::~StackSafetyInfo() = default;
+
+void StackSafetyInfo::print(raw_ostream &O) const { Info->print(O); }
+
+AnalysisKey StackSafetyAnalysis::Key;
 
 StackSafetyInfo StackSafetyAnalysis::run(Function &F,
                                          FunctionAnalysisManager &AM) {
-  return StackSafetyInfo();
+  StackSafetyLocalAnalysis SSLA(F, AM.getResult<ScalarEvolutionAnalysis>(F));
+  return SSLA.run();
 }
 
 PreservedAnalyses StackSafetyPrinterPass::run(Function &F,
                                               FunctionAnalysisManager &AM) {
   OS << "'Stack Safety Local Analysis' for function '" << F.getName() << "'\n";
   AM.getResult<StackSafetyAnalysis>(F).print(OS);
   return PreservedAnalyses::all();
 }
 
 char StackSafetyInfoWrapperPass::ID = 0;
 
 StackSafetyInfoWrapperPass::StackSafetyInfoWrapperPass() : FunctionPass(ID) {
   initializeStackSafetyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 void StackSafetyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<ScalarEvolutionWrapperPass>();
   AU.setPreservesAll();
 }
 
 void StackSafetyInfoWrapperPass::print(raw_ostream &O, const Module *M) const {
   SSI.print(O);
 }
 
-bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) { return false; }
+bool StackSafetyInfoWrapperPass::runOnFunction(Function &F) {
+  StackSafetyLocalAnalysis SSLA(
+      F, getAnalysis<ScalarEvolutionWrapperPass>().getSE());
+  SSI = StackSafetyInfo(SSLA.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)

llvm/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
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
-; CHECK: 'Stack Safety Local Analysis' for function 'Foo'
-; CHECK-NEXT: Not Implemented
+@sink = global i8* null, align 8
 
-define dso_local void @Foo() {
+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)
+
+; Address leaked.
+define void @LeakAddress() {
+; CHECK-LABEL: @LeakAddress dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: full-set{{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  store i8* %x1, i8** @sink, align 8
+  ret void
+}
+
+define void @StoreInBounds() {
+; CHECK-LABEL: @StoreInBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,1){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  store i8 0, i8* %x1, align 1
+  ret void
+}
+
+define void @StoreInBounds2() {
+; CHECK-LABEL: @StoreInBounds2 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,4){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  store i32 0, i32* %x, align 4
+  ret void
+}
+
+define void @StoreInBounds3() {
+; CHECK-LABEL: @StoreInBounds3 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [2,3){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 2
+  store i8 0, i8* %x2, align 1
+  ret void
+}
+
+; FIXME: ScalarEvolution does not look through ptrtoint/inttoptr.
+define void @StoreInBounds4() {
+; CHECK-LABEL: @StoreInBounds4 dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [2,-1){{$}}
+; CHECK-NOT: ]:
 entry:
+  %x = alloca i32, align 4
+  %x1 = ptrtoint i32* %x to i64
+  %x2 = add i64 %x1, 2
+  %x3 = inttoptr i64 %x2 to i8*
+  store i8 0, i8* %x3, align 1
+  ret void
+}
+
+define void @StoreOutOfBounds() {
+; CHECK-LABEL: @StoreOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [2,6){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 2
+  %x3 = bitcast i8* %x2 to i32*
+  store i32 0, i32* %x3, align 1
+  ret void
+}
+
+; There is no difference in load vs store handling.
+define void @LoadInBounds() {
+; CHECK-LABEL: @LoadInBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,1){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %v = load i8, i8* %x1, align 1
+  ret void
+}
+
+define void @LoadOutOfBounds() {
+; CHECK-LABEL: @LoadOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [2,6){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 2
+  %x3 = bitcast i8* %x2 to i32*
+  %v = load i32, i32* %x3, align 1
+  ret void
+}
+
+; Leak through ret.
+define i8* @Ret() {
+; CHECK-LABEL: @Ret dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: full-set{{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 2
+  ret i8* %x2
+}
+
+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)){{$}}
+; 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
+}
+
+; Indirect calls can not be analyzed (yet).
+; FIXME: %p[]: full-set looks invalid
+define void @IndirectCall(void (i8*)* %p) {
+; CHECK-LABEL: @IndirectCall dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: p[]: empty-set{{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: full-set{{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void %p(i8* %x1);
+  ret void
+}
+
+define void @NonConstantOffset(i1 zeroext %z) {
+; CHECK-LABEL: @NonConstantOffset dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: z[]: full-set{{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,4){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %idx = select i1 %z, i64 1, i64 2
+  %x2 = getelementptr i8, i8* %x1, i64 %idx
+  store i8 0, i8* %x2, align 1
+  ret void
+}
+
+define void @NonConstantOffsetOOB(i1 zeroext %z) {
+; CHECK-LABEL: @NonConstantOffsetOOB dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: z[]: full-set{{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,6){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %idx = select i1 %z, i64 1, i64 4
+  %x2 = getelementptr i8, i8* %x1, i64 %idx
+  store i8 0, i8* %x2, align 1
+  ret void
+}
+
+define void @ArrayAlloca() {
+; CHECK-LABEL: @ArrayAlloca dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[40]: [36,40){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, i32 10, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 36
+  %x3 = bitcast i8* %x2 to i32*
+  store i32 0, i32* %x3, align 1
+  ret void
+}
+
+define void @ArrayAllocaOOB() {
+; CHECK-LABEL: @ArrayAllocaOOB dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[40]: [37,41){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, i32 10, align 4
+  %x1 = bitcast i32* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 37
+  %x3 = bitcast i8* %x2 to i32*
+  store i32 0, i32* %x3, align 1
+  ret void
+}
+
+define void @DynamicAllocaUnused(i64 %size) {
+; CHECK-LABEL: @DynamicAllocaUnused dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: size[]: empty-set{{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[0]: empty-set{{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, i64 %size, align 16
+  ret void
+}
+
+; Dynamic alloca with unknown size.
+define void @DynamicAlloca(i64 %size) {
+; CHECK-LABEL: @DynamicAlloca dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: size[]: [0,-12){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[0]: [0,4){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, i64 %size, align 16
+  store i32 0, i32* %x, align 1
+  ret void
+}
+
+; Dynamic alloca with limited size.
+; FIXME: could be proved safe. Implement.
+define void @DynamicAllocaFiniteSizeRange(i1 zeroext %z) {
+; CHECK-LABEL: @DynamicAllocaFiniteSizeRange dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: z[]: [0,-12){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[0]: [0,4){{$}}
+; CHECK-NOT: ]:
+entry:
+  %size = select i1 %z, i64 3, i64 5
+  %x = alloca i32, i64 %size, align 16
+  store i32 0, i32* %x, align 1
+  ret void
+}
+
+define signext i8 @SimpleLoop() {
+; CHECK-LABEL: @SimpleLoop dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[10]: [0,10){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca [10 x i8], align 1
+  %0 = getelementptr inbounds [10 x i8], [10 x i8]* %x, i64 0, i64 0
+  %lftr.limit = getelementptr inbounds [10 x i8], [10 x i8]* %x, i64 0, i64 10
+  br label %for.body
+
+for.body:
+  %sum.010 = phi i8 [ 0, %entry ], [ %add, %for.body ]
+  %p.09 = phi i8* [ %0, %entry ], [ %incdec.ptr, %for.body ]
+  %incdec.ptr = getelementptr inbounds i8, i8* %p.09, i64 1
+  %1 = load volatile i8, i8* %p.09, align 1
+  %add = add i8 %1, %sum.010
+  %exitcond = icmp eq i8* %incdec.ptr, %lftr.limit
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret i8 %add
+}
+
+; OOB in a loop.
+define signext i8 @SimpleLoopOOB() {
+; CHECK-LABEL: @SimpleLoopOOB dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[10]: [0,11){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca [10 x i8], align 1
+  %0 = getelementptr inbounds [10 x i8], [10 x i8]* %x, i64 0, i64 0
+ ; 11 iterations
+  %lftr.limit = getelementptr inbounds [10 x i8], [10 x i8]* %x, i64 0, i64 11
+  br label %for.body
+
+for.body:
+  %sum.010 = phi i8 [ 0, %entry ], [ %add, %for.body ]
+  %p.09 = phi i8* [ %0, %entry ], [ %incdec.ptr, %for.body ]
+  %incdec.ptr = getelementptr inbounds i8, i8* %p.09, i64 1
+  %1 = load volatile i8, i8* %p.09, align 1
+  %add = add i8 %1, %sum.010
+  %exitcond = icmp eq i8* %incdec.ptr, %lftr.limit
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret i8 %add
+}
+
+; FIXME: we don't understand that %sz in the memset call is limited to 128 by the preceding check.
+define dso_local void @SizeCheck(i32 %sz) {
+; CHECK-LABEL: @SizeCheck{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: sz[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x1[128]: full-set{{$}}
+; CHECK-NOT: ]:
+entry:
+  %x1 = alloca [128 x i8], align 16
+  %x1.sub = getelementptr inbounds [128 x i8], [128 x i8]* %x1, i64 0, i64 0
+  %cmp = icmp slt i32 %sz, 129
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  call void @llvm.memset.p0i8.i32(i8* nonnull align 16 %x1.sub, i8 0, i32 %sz, i1 false)
+  br label %if.end
+
+if.end:
   ret void
 }

llvm/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
+
+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)
+
+define void @MemsetInBounds() {
+; CHECK-LABEL: MemsetInBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,4){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  call void @llvm.memset.p0i8.i32(i8* %x1, i8 42, i32 4, i1 false)
+  ret void
+}
+
+; Volatile does not matter for access bounds.
+define void @VolatileMemsetInBounds() {
+; CHECK-LABEL: VolatileMemsetInBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,4){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+    %x1 = bitcast i32* %x to i8*
+  call void @llvm.memset.p0i8.i32(i8* %x1, i8 42, i32 4, i1 true)
+  ret void
+}
+
+define void @MemsetOutOfBounds() {
+; CHECK-LABEL: MemsetOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,5){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+    %x1 = bitcast i32* %x to i8*
+  call void @llvm.memset.p0i8.i32(i8* %x1, i8 42, i32 5, i1 false)
+  ret void
+}
+
+define void @MemsetNonConst(i32 %size) {
+; CHECK-LABEL: MemsetNonConst dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: size[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: full-set{{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+    %x1 = bitcast i32* %x to i8*
+  call void @llvm.memset.p0i8.i32(i8* %x1, i8 42, i32 %size, i1 false)
+  ret void
+}
+
+; FIXME: memintrinsics should look at size range when possible
+; Right now we refuse any non-constant size.
+define void @MemsetNonConstInBounds(i1 zeroext %z) {
+; CHECK-LABEL: MemsetNonConstInBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: z[]: [0,1){{$}}
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: full-set{{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %size = select i1 %z, i32 3, i32 4
+  call void @llvm.memset.p0i8.i32(i8* %x1, i8 42, i32 %size, i1 false)
+  ret void
+}
+
+define void @MemcpyInBounds() {
+; CHECK-LABEL: MemcpyInBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,4){{$}}
+; CHECK-NEXT: y[4]: [0,4){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %y = alloca i32, align 4
+  %x1 = bitcast i32* %x to i8*
+  %y1 = bitcast i32* %y to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %x1, i8* %y1, i32 4, i1 false)
+  ret void
+}
+
+define void @MemcpySrcOutOfBounds() {
+; CHECK-LABEL: MemcpySrcOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[8]: [0,5){{$}}
+; CHECK-NEXT: y[4]: [0,5){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %y = alloca i32, align 4
+  %x1 = bitcast i64* %x to i8*
+  %y1 = bitcast i32* %y to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %x1, i8* %y1, i32 5, i1 false)
+  ret void
+}
+
+define void @MemcpyDstOutOfBounds() {
+; CHECK-LABEL: MemcpyDstOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,5){{$}}
+; CHECK-NEXT: y[8]: [0,5){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %y = alloca i64, align 4
+  %x1 = bitcast i32* %x to i8*
+  %y1 = bitcast i64* %y to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %x1, i8* %y1, i32 5, i1 false)
+  ret void
+}
+
+define void @MemcpyBothOutOfBounds() {
+; CHECK-LABEL: MemcpyBothOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[4]: [0,9){{$}}
+; CHECK-NEXT: y[8]: [0,9){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i32, align 4
+  %y = alloca i64, align 4
+  %x1 = bitcast i32* %x to i8*
+  %y1 = bitcast i64* %y to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %x1, i8* %y1, i32 9, i1 false)
+  ret void
+}
+
+define void @MemcpySelfInBounds() {
+; CHECK-LABEL: MemcpySelfInBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[8]: [0,8){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 5
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %x1, i8* %x2, i32 3, i1 false)
+  ret void
+}
+
+define void @MemcpySelfSrcOutOfBounds() {
+; CHECK-LABEL: MemcpySelfSrcOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[8]: [0,9){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 5
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %x1, i8* %x2, i32 4, i1 false)
+  ret void
+}
+
+define void @MemcpySelfDstOutOfBounds() {
+; CHECK-LABEL: MemcpySelfDstOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[8]: [0,9){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 5
+  call void @llvm.memcpy.p0i8.p0i8.i32(i8* %x2, i8* %x1, i32 4, i1 false)
+  ret void
+}
+
+define void @MemmoveSelfBothOutOfBounds() {
+; CHECK-LABEL: MemmoveSelfBothOutOfBounds dso_preemptable{{$}}
+; CHECK-NEXT: args uses:
+; CHECK-NEXT: allocas uses:
+; CHECK-NEXT: x[8]: [0,14){{$}}
+; CHECK-NOT: ]:
+entry:
+  %x = alloca i64, align 4
+  %x1 = bitcast i64* %x to i8*
+  %x2 = getelementptr i8, i8* %x1, i64 5
+  call void @llvm.memmove.p0i8.p0i8.i32(i8* %x1, i8* %x2, i32 9, i1 false)
+  ret void
+}