asan: do not instrument direct inbounds accesses to stack variables

[dvyukov]

Summary

This is most likely wrong.

But it eliminates 33% of instrumentation on webrtc/modules_unittests (number of memory accesses goes down from 290152 to 193998) and reduces binary size by 15% (from 74M to 64M) _and_ all existing asan tests pass.
This means that either our tests are bad or we are missing a good optimization opportunity.

Currently we instrument even the following code, which looks wrong:

define void @foo() uwtable sanitize_address {
entry:

%a = alloca i32, align 4
store i32 42, i32* %a, align 4
ret void

}

I've found one case which fails with this change. We do not instrument the store in this case:

define void @bar() sanitize_address {
entry:

%a = alloca [10 x i32], align 4
%e = getelementptr inbounds [10 x i32]* %a, i32 0, i64 12
store i32 42, i32* %e, align 4
ret void

; CHECK-LABEL: define void @bar
; CHECK: __asan_report
; CHECK: ret void
}

However, compiler should be able to recognize such cases (and it does because it issues a warning).

I am a bit lost.
There is Value::isGEPWithNoNotionalOverIndexing which looks like what we need (should eliminate array accesses with constant inbounds indices and struct field accesses). However, it does not give the desired effect.
Value::stripInBoundsConstantOffsets also looks like what we need and it gives the desired effect. However, there is a note that "Value::isGEPWithNoNotionalOverIndexing is not equivalant to, a subset of, or a superset of the "inbounds" property". Which suggests that stripInBoundsConstantOffsets is not what we want.

Also, is it possible to refer to an AllocaInst outside of its lifetime? It is not possible in C/C++ due to scoping rules, you simply can't mention a name that is out of scope. However, I am not sure about llvm and its transformations.

I am looking for advice here.

[dvyukov]

To make it clear, I want to eliminate instrumentation of locals within its lifetime (so it is not a use-after-scope) and that is known to be inbounds (that is, direct accesses, field accesses and array element accesses with constant indices; so it is not a out-of-bounds).

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

893

mega cool.
Let's put it under a flag e.g. asan-opt-stack-inbounds (off by default) and play with it more.

897

remove this then?

[dvyukov]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

893

Is it possible to make it work correctly? I am lost in all possible llvm predicates and their meaning. I don't understand how "int x[10]; x[12] = 1" can be an "in bounds constant offset".

[zaks.anna]

stripInBoundsConstantOffsets is not want you want, see the definition of "inbounds" ( http://llvm.org/docs/LangRef.html#getelementptr-instruction)
"If the inbounds keyword is present, the result value of the getelementptr is a poison value if the base pointer is not an in bounds address of an allocated object, or if any of the addresses that would be formed by successive addition of the offsets implied by the indices to the base address with infinitely precise signed arithmetic are not an in bounds address of that allocated object. The in bounds addresses for an allocated object are all the addresses that point into the object, plus the address one byte past the end. In cases where the base is a vector of pointers the inbounds keyword applies to each of the computations element-wise."

I recall Nuno Lopes working on reducing the number of bounce checks, but all I can find is this:
./lib/Transforms/Instrumentation/BoundsChecking.cpp

[dvyukov]

Rewrote to use SizeOffsetEvalType.compute to find inbounds accesses.

[dvyukov]

Thank you, Anna!

Changed the code to use SizeOffsetEvalType.compute to find inbounds accesses.
This patch still eliminates ~33% of accesses and binaries are 15% smaller. All existing and new tests pass.

Anna, does it fix the issue that you are trying to solve in the other patch?

Kostya, PTAL.

[zaks.anna]

How are you getting the speedup/size improvement measurements? Are these at -O1 or -O0?

When comparing to my patch, the intend of this patch is to be more aggressive in removing bounds checking. My patch does not introduce any improvement at optimization levels higher than -O0 and is trying to simulate mem2reg. On the other hand, the analysis here are more aggressive in the checks it removes. For example, my patch would not remove provably in bounds array accesses with constant offset and it does not do anything for non-alloca values.

On the other hand, with my patch, the allocas that are known not to have instrumented accesses do not get poisoned. Currently, this patch is only targeting removal of bounds checking. Also, I am not sure what is the compile time overhead this brings and how reliable it is since I don't think ObjectSizeOffsetEvaluator is used much.

I preference is to have this on top of non-promotable allocas.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

18

These seem out of place - should be moved after ADT.

189

This makes me nervous. I don't think ObjectSizeOffsetEvaluator is used much. This should probably go through more testing, though I am not sure how to catch issues here since we are removing checking.

408

const?

1502

/*RoundToAlign=*/true

2058

Why not use getTypeStoreSize()?

uint64_t getTypeStoreSizeInBits(Type *Ty) const {
  return 8 * getTypeStoreSize(Ty);
}

Also, is overflow possible in these calculations?

[zaks.anna]

Also, I believe removal of all unnecessary checks is a bigger task. If we want to ensure that all possible out of bounds accesses are instrumented, we'd have to do something similar to what Chandler suggested in the other thread. That would eliminate the false negatives that are now possible at -O1 and higher. We'd need to have an instrumentation pass that runs early on and instruments accesses before the optimizer kicks in. Later, we would work with LLVM analysis to remove those checks.

Here is the answer from Nuno on bounds check removal. Enjoy:)

"The file you mention is the instrumentation pass. It is pretty dumb: it basically instruments any memory write (it just performs one optimization to reduce the cost of the check if certain conditions hold; but it always introduces the check). So this one is not interesting for AddressSanitizer (the likelihood it can detect anything that ASan cannot detect is very small; the idea was to have something with a very small overhead to deploy on release builds). It can detect overflows that Valgrind cannot btw.

The part about removing checks is done by several passes which are run by default (with -O2). Instcombine can remove some checks, then Transforms/Scalar/CorrelatedValuePropagation.cpp performs range analysis to delete checks that are always safe. This analysis existed previously, but it had a bunch of problems and shortcomings.
The range analysis is in Analysis/LazyValueInfo.cpp. It's still fundamentally weak, because of the way it traverses basic-blocks to constrain the range due to branching conditions. We have discussed this quite a bit, but the major improvements were never implemented (ask me if you want more details).

There's also Analysis/MemoryBuiltins.cpp. This analysis provides (static or dynamic) information about the allocated size of an object (and knows about malloc, stack, etc).

A very important aspect of reducing the overhead of bounds checks is to hoist them out of loops. By default, LLVM cannot and won't do this. The reason is that it's not legal to move a function that has side-effects (namely terminate the application) because LLVM has precise exception semantics. However, for bounds checks we don't really care; if we know that the program will crash inside the loop, why not crash it sooner? (well, there's a price to pay, of course. the state of the program will be different when looking through a debugger, but I think that's ok).
Again, right now LLVM cannot do this transformation. At the time, I proposed that we introduced an "antecipable" trap to the IR. Something that the compiler could move freely up to the beginning of the function (or of the program), as long as we know it would only execute if it executed in the original program.
An example makes it clear I guess:

for (i=0; i < n; ++i) {

if (a[i] out of bounds)
  antecipable_trap();
a[i] = …;

}

Transform to:

if (any of a[0..n-1] out of bounds)

antecipable_trap();

for (i=0; i < n; ++i) {

a[i] = …;

}

This is an obvious transformation. Without it, vectorization will not kick in at all (since it is mostly oblivious about multiple exit loops). Anyway, this is something for the backend guys to work on. It isn't very hard to implement; it just hasn't been done.

The other thing that has been committed recently to LLVM (last month) is a loop splitter (Transforms/Scalar/InductiveRangeCheckElimination.cpp). The idea is that if we can prove that in the first x iterations of the loop, everything is in bounds, then we can duplicate the loop, and remove all checks from the first loop. This increases code size, but can enable many optimizations on the first x iterations (which we hope will be the majority, but that's only a hope).

Finally, how does all of this applies to ASan? I don't know. Sorry, I never took a look to how ASan instruments stuff. If it exposes, say, the bounds checks in the IR (i.e., if the comparison is inlined in the IR), then current transformation passes will look at that and try to optimized them away (with the caveat there is still work required on the backend). If ASan just introduces a function call (e.g., check_pointer_is_ok(%p)), then the optimizers have no clue what that function does and will not touch it. Of course it is possible to patch, say, the CVP pass to know about these ASan functions and then reuse the same range analysis. Or, alternatively, build a simple pass that is only runs when ASan is used and that queries current analyses.
So, yes, building analyses from scratch doesn't make sense IMHO. It should be possible to reuse what LLVM already has. Then, how to use the information is a different story, but grepping for ASan functions in the IR and using current analyses shouldn't be a hard task (again, I have no clue how ASan works).
ASan also has stronger guarantees that my bounds checkers. For example, I don't check if the object has been deleted in the meantime. And ASan does. So the analysis has to work a bit harder (basically check liveness of objects as well as the size; but then if we only managed to get one piece of information but not the other, probably it's possible to optimize the check).

Ok, so I think the email is already quite long, but feel free to ask me for more details. I just tried to give an overview of what LLVM can and cannot do. I'm sorry I don't know more about ASan to give you a more concrete answer.

Nuno"

[kcc]

lib/Transforms/Instrumentation/AddressSanitizer.cpp

189

ouch. Indeed, don't make it true by default for now.
Unfortunately, I don't know any good way to test complex optimizations that eliminate checks,
and so I don't know what it will take us to enable this by default.
But at least having this code in trunk will simplify the experiments.

[dvyukov]

uploaded new patch

lib/Transforms/Instrumentation/AddressSanitizer.cpp

18

Done

189

changed default value to false

408

done

1502

done

2058

done

These are int64's. I don't see how overflow can happen.

[dvyukov]

In D7583#129129, @zaks.anna wrote:

How are you getting the speedup/size improvement measurements? Are these at -O1 or -O0?

I compiled a large program with -O2 and measured binary size difference.
Then compiled with -O2 and call threshold set to -1 and objdump -d | grep "call.*__asan_report_" | wc -l

When comparing to my patch, the intend of this patch is to be more aggressive in removing bounds checking. My patch does not introduce any improvement at optimization levels higher than -O0 and is trying to simulate mem2reg. On the other hand, the analysis here are more aggressive in the checks it removes. For example, my patch would not remove provably in bounds array accesses with constant offset and it does not do anything for non-alloca values.

On the other hand, with my patch, the allocas that are known not to have instrumented accesses do not get poisoned. Currently, this patch is only targeting removal of bounds checking. Also, I am not sure what is the compile time overhead this brings and how reliable it is since I don't think ObjectSizeOffsetEvaluator is used much.

I preference is to have this on top of non-promotable allocas.

I am perfectly OK with it. But what do I know?

[dvyukov]

Also, I believe removal of all unnecessary checks is a bigger task.

I would say it is an infinite task. Besides loops there are also access coalescing, inter-BB duduplication, range deduplication (if we checked [this, this+X), then we may omit checks of everything in [this, this+X)), figuring out what calls can actually free what objects, etc.

[nlopes]

You should use ObjectSizeOffsetVisitor instead of ObjectSizeOffsetEvaluator. The interface is the similar, but it gives up when the object size is not constant, while the later may insert new instructions in the code. ObjectSizeOffsetVisitor is well tested (it's used by alias analysis, for example).

Second, the inbounds check is unsound (it may overflow -- check the prove here: http://rise4fun.com/Z3/PVrF). The correct set of checks are the following 3:

• Offset >= 0 (signed; you have this one)
• Size >= Offset (unsigned)
• Size - Offset >= AccessSize (unsigned)

Finally, you cannot derive the access size from "DL->getTypeStoreSize(OrigTy)". For example, just because an array has elements of size 4, it doesn't mean that all stores must be of size 4. You can have done a bitcast, and stored 8 bytes. Basically you need to get hold of the element stored and check its store size.

After fixing these 3 issues, I think the patch becomes correct and desirable for commit.

[dvyukov]

Thanks for the review, Nuno!
All you three comments are addressed. Please take another look.

[• dberlin]

FWIW: This optimization looks right to me.
GVN uses similar logic to do an optimization to loads it can prove come directly from allocation functions.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

2049

You may want to look if this does a better/worse job than GetPointerBaseWithConstantOffset

(This is what GVN, DeadStoreElimination, etc use to do what you are doing here - compute the pointer base and constant offset, make sure they match, then they use getTypeSizeInBits to compare the sizes)

[chandlerc]

This looks very good to me as well. I think you can submit now. The remaining issues are I think quite minor.

However, I would love to find some form of naming that doesn't so easily confuse the GEP "inbounds" keyword with this check. Sadly, I can't come up with any good ideas. Maybe just talk about "safe" in the APIs and explain what the object size check is computing, etc.? Anyways, a minor point.

If this causes a compile-time regression, it should be easy to track down. You might do a quick sanity check for some big inputs Dmitry, since it seems like you have them.

Danny, I'm pretty sure that the object size code is newer and should at least in theory be more powerful than just getting the base address. I could be wrong though. Still, easy to switch to that in a follow-up if needed.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

383–385

Surely clang-format puts this 'const' somewhere else...

[dvyukov]

applied clang-format

[dvyukov]

Chandler,

I've applied clang-format.

Renamed s/inbounds/safe/. Comment above the function explains the meaning of safe.

Regarding compilation speed. On top of removing instrumentation and reducing binary size, it also speedups compilation (less stuff for backed to deal with). I've tested on llvm's largest source file lib/Target/X86/X86ISelLowering.cpp.

current without asan -O0:
real 0m4.847s
real 0m4.813s
real 0m4.776s
(I cross-checked that the new compiler has the same performance)

current -fsanitize=address -O0
real 0m7.191s
real 0m7.257s
real 0m7.183s

new -fsanitize=address -O0
real 0m6.619s
real 0m6.798s
real 0m6.722s
(~-6.4%)

current -fsanitize=address -O1
real 0m17.466s
real 0m17.553s
real 0m17.449s

new -fsanitize=address -O1
real 0m15.908s
real 0m15.853s
real 0m15.329s
(~-12.15%)

current -fsanitize=address -O2
real 0m24.337s
real 0m24.246s
real 0m24.604s

new -fsanitize=address -O2
real 0m23.662s
real 0m23.430s
real 0m23.400s
(~-3.49%)

Object file size:
w/o asan: 1228800
current with asan: 3658480 (+197.73%)
new with asan: 3444760 (-5.84%)

Amount of instrumentation (since it is just an object file, I grepped for "callq"):
w/o asan: 8235
current with asan: 37342
new with asan: 33706 (-12.5%)

[dvyukov]

Reformat code with -style=Google, because otherwise linter in check-all barks.

[dvyukov]

Committed in rev 231241.
We also need some plan for testing and enabling such optimization by default.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

 //===-- AddressSanitizer.cpp - memory error detector ------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of AddressSanitizer, an address sanity checker.
 // Details of the algorithm:
 //  http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"

 // and benchmarking the tool.
 static cl::opt<bool> ClOpt("asan-opt",
        cl::desc("Optimize instrumentation"), cl::Hidden, cl::init(true));
 static cl::opt<bool> ClOptSameTemp("asan-opt-same-temp",
        cl::desc("Instrument the same temp just once"), cl::Hidden,
        cl::init(true));
 static cl::opt<bool> ClOptGlobals("asan-opt-globals",
        cl::desc("Don't instrument scalar globals"), cl::Hidden, cl::init(true));
+static cl::opt<bool> ClOptStack("asan-opt-stack",
+       cl::desc("Don't instrument scalar stack variables"), cl::Hidden,
+       cl::init(true));
 
 static cl::opt<bool> ClCheckLifetime("asan-check-lifetime",
        cl::desc("Use llvm.lifetime intrinsics to insert extra checks"),
        cl::Hidden, cl::init(false));
 
 static cl::opt<bool> ClDynamicAllocaStack(
     "asan-stack-dynamic-alloca",
     cl::desc("Use dynamic alloca to represent stack variables"), cl::Hidden,
static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"),
                                cl::Hidden, cl::init(-1));
 static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"),
                                cl::Hidden, cl::init(-1));
 
 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
 STATISTIC(NumInstrumentedDynamicAllocas,
           "Number of instrumented dynamic allocas");
-STATISTIC(NumOptimizedAccessesToGlobalArray,
-          "Number of optimized accesses to global arrays");
 STATISTIC(NumOptimizedAccessesToGlobalVar,
           "Number of optimized accesses to global vars");
+STATISTIC(NumOptimizedAccessesToStackVar,
+          "Number of optimized accesses to stack vars");
 
 namespace {
 /// Frontend-provided metadata for source location.
 struct LocationMetadata {
   StringRef Filename;
   int LineNo;
   int ColumnNo;
 
struct AddressSanitizer : public FunctionPass {
   AddressSanitizer() : FunctionPass(ID) {
     initializeAddressSanitizerPass(*PassRegistry::getPassRegistry());
   }
   const char *getPassName() const override {
     return "AddressSanitizerFunctionPass";
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<DataLayoutPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
   }
-  void instrumentMop(Instruction *I, bool UseCalls);
+  void instrumentMop(ObjectSizeOffsetEvaluator &ObjSizeEval, Instruction *I,
+                     bool UseCalls);
   void instrumentPointerComparisonOrSubtraction(Instruction *I);
   void instrumentAddress(Instruction *OrigIns, Instruction *InsertBefore,
                          Value *Addr, uint32_t TypeSize, bool IsWrite,
                          Value *SizeArgument, bool UseCalls);
   Value *createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
                            Value *ShadowValue, uint32_t TypeSize);
   Instruction *generateCrashCode(Instruction *InsertBefore, Value *Addr,
                                  bool IsWrite, size_t AccessSizeIndex,
                                  Value *SizeArgument);
   void instrumentMemIntrinsic(MemIntrinsic *MI);
   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
   bool runOnFunction(Function &F) override;
   bool maybeInsertAsanInitAtFunctionEntry(Function &F);
   bool doInitialization(Module &M) override;
   static char ID;  // Pass identification, replacement for typeid
 
   DominatorTree &getDominatorTree() const { return *DT; }
 
  private:
   void initializeCallbacks(Module &M);
 
   bool LooksLikeCodeInBug11395(Instruction *I);
   bool GlobalIsLinkerInitialized(GlobalVariable *G);
+  bool isInboundsAccess(ObjectSizeOffsetEvaluator &ObjSizeEval, Value *Addr);
 
   LLVMContext *C;
   const DataLayout *DL;
   Triple TargetTriple;
   int LongSize;
   Type *IntptrTy;
   ShadowMapping Mapping;
   DominatorTree *DT;
AddressSanitizer::instrumentPointerComparisonOrSubtraction(Instruction *I) {
   Value *Param[2] = {I->getOperand(0), I->getOperand(1)};
   for (int i = 0; i < 2; i++) {
     if (Param[i]->getType()->isPointerTy())
       Param[i] = IRB.CreatePointerCast(Param[i], IntptrTy);
   }
   IRB.CreateCall2(F, Param[0], Param[1]);
 }
 
-void AddressSanitizer::instrumentMop(Instruction *I, bool UseCalls) {
+void AddressSanitizer::instrumentMop(ObjectSizeOffsetEvaluator &ObjSizeEval,
+                                     Instruction *I, bool UseCalls) {
   bool IsWrite = false;
   unsigned Alignment = 0;
   Value *Addr = isInterestingMemoryAccess(I, &IsWrite, &Alignment);
   assert(Addr);
+
   if (ClOpt && ClOptGlobals) {
-    if (GlobalVariable *G = dyn_cast<GlobalVariable>(Addr)) {
-      // If initialization order checking is disabled, a simple access to a
-      // dynamically initialized global is always valid.
-      if (!ClInitializers || GlobalIsLinkerInitialized(G)) {
-        NumOptimizedAccessesToGlobalVar++;
-        return;
-      }
-    }
-    ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr);
-    if (CE && CE->isGEPWithNoNotionalOverIndexing()) {
-      if (GlobalVariable *G = dyn_cast<GlobalVariable>(CE->getOperand(0))) {
-        if (CE->getOperand(1)->isNullValue() && GlobalIsLinkerInitialized(G)) {
-          NumOptimizedAccessesToGlobalArray++;
-          return;
-        }
-      }
-    }
-  }
+    GlobalVariable *G = dyn_cast<GlobalVariable>(GetUnderlyingObject(Addr,
+                                                                     nullptr));
+    if (G != NULL && (!ClInitializers || GlobalIsLinkerInitialized(G)) &&
+        isInboundsAccess(ObjSizeEval, Addr)) {
+
+  if (ClOpt && ClOptStack) {
+    // A direct inbounds access to a stack variable is always valid.
+    if (isa<AllocaInst>(GetUnderlyingObject(Addr, nullptr)) &&
+        isInboundsAccess(ObjSizeEval, Addr)) {
+      NumOptimizedAccessesToStackVar++;
 
   Type *OrigPtrTy = Addr->getType();
   Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
 
   assert(OrigTy->isSized());
   uint32_t TypeSize = DL->getTypeStoreSizeInBits(OrigTy);
 
   assert((TypeSize % 8) == 0);
 
   if (IsWrite)
     NumInstrumentedWrites++;
   else
     NumInstrumentedReads++;
 
   unsigned Granularity = 1 << Mapping.Scale;
for (auto &BB : F) {
     }
   }
 
   bool UseCalls = false;
   if (ClInstrumentationWithCallsThreshold >= 0 &&
       ToInstrument.size() > (unsigned)ClInstrumentationWithCallsThreshold)
     UseCalls = true;
 
+  const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().
+      getTLI();
+  ObjectSizeOffsetEvaluator ObjSizeEval(DL, TLI, F.getContext(), true);
+
   // Instrument.
   int NumInstrumented = 0;
   for (auto Inst : ToInstrument) {
     if (ClDebugMin < 0 || ClDebugMax < 0 ||
         (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) {
       if (isInterestingMemoryAccess(Inst, &IsWrite, &Alignment))
-        instrumentMop(Inst, UseCalls);
+        instrumentMop(ObjSizeEval, Inst, UseCalls);
       else
         instrumentMemIntrinsic(cast<MemIntrinsic>(Inst));
     }
     NumInstrumented++;
   }
 
   FunctionStackPoisoner FSP(F, *this);
   bool ChangedStack = FSP.runOnFunction();
void FunctionStackPoisoner::handleDynamicAllocaCall(
   // Replace all uses of AddessReturnedByAlloca with NewAddress.
   AI->replaceAllUsesWith(NewAddressPtr);
 
   // We are done. Erase old alloca and store left, partial and right redzones
   // shadow addresses for future unpoisoning.
   AI->eraseFromParent();
   NumInstrumentedDynamicAllocas++;
 }
+
+// isInboundsAccess returns true if Addr is always inbounds with respect to its
+// base object. For example, it is a field access or an array access with
+// constant inbounds index.
+bool AddressSanitizer::isInboundsAccess(ObjectSizeOffsetEvaluator &ObjSizeEval,
+                                        Value *Addr) {
+  SizeOffsetEvalType SizeOffset = ObjSizeEval.compute(Addr);
+  if (!ObjSizeEval.bothKnown(SizeOffset) ||
+      !isa<ConstantInt>(SizeOffset.first) ||
+      !isa<ConstantInt>(SizeOffset.second))
+    return false;
+  Type *OrigTy = cast<PointerType>(Addr->getType())->getElementType();
+  uint32_t TypeSize = DL->getTypeStoreSizeInBits(OrigTy);
+  int64_t Size = dyn_cast<ConstantInt>(SizeOffset.first)->getSExtValue();
+  int64_t Offset = dyn_cast<ConstantInt>(SizeOffset.second)->getSExtValue();
+  return Offset >= 0 && Offset + TypeSize / 8 <= Size;
+}

test/Instrumentation/AddressSanitizer/instrument-stack.ll

+; This test checks that we are not instrumenting direct inbound stack accesses.
+; RUN: opt < %s -asan -asan-module -S | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+;@sink = global i32* null, align 4
+
+define void @foo() uwtable sanitize_address {
+entry:
+  %a = alloca i32, align 4
+  store i32 42, i32* %a, align 4
+  ret void
+; CHECK-LABEL: define void @foo
+; CHECK-NOT: __asan_report
+; CHECK: ret void
+}
+
+define void @baz(i64 %i) sanitize_address {
+entry:
+  %a = alloca [10 x i32], align 4
+  %e = getelementptr inbounds [10 x i32]* %a, i32 0, i64 %i
+  store i32 42, i32* %e, align 4
+  ret void
+; CHECK-LABEL: define void @baz
+; CHECK: __asan_report
+; CHECK: ret void
+}
+
+define void @bar() sanitize_address {
+entry:
+  %a = alloca [10 x i32], align 4
+  %e = getelementptr inbounds [10 x i32]* %a, i32 0, i64 12
+  store i32 42, i32* %e, align 4
+  ret void
+; CHECK-LABEL: define void @bar
+; CHECK: __asan_report
+; CHECK: ret void
+}
+
+define void @endoftests() sanitize_address {
+entry:
+  ret void
+; CHECK-LABEL: define void @endoftests
+}
+