[BoundsChecking] Fix merging of sizes

[aeubanks]

Summary

BoundsChecking uses ObjectSizeOffsetEvaluator to keep track of the
underlying size/offset of pointers in allocations. However,
ObjectSizeOffsetVisitor (something ObjectSizeOffsetEvaluator
uses to check for constant sizes/offsets)
doesn't quite treat sizes and offsets the same way as
BoundsChecking. BoundsChecking wants to know the size of the
underlying allocation and the current pointer's offset within
it, but ObjectSizeOffsetVisitor only cares about the size
from the pointer to the end of the underlying allocation.

This only comes up when merging two size/offset pairs. Add a new mode to
ObjectSizeOffsetVisitor which cares about the underlying size/offset
rather than the size from the current pointer to the end of the
allocation.

Fixes a false positive with -fsanitize=bounds.

[vitalybuka]

llvm/lib/Analysis/MemoryBuiltins.cpp

1006

1006

or even

[aeubanks]

llvm/lib/Analysis/MemoryBuiltins.cpp

1006

derp, I even had that at some point

llvm/include/llvm/Analysis/MemoryBuiltins.h

 //===----------------------------------------------------------------------===//
 //  Utility functions to compute size of objects.
 //
 
 /// Various options to control the behavior of getObjectSize.
 struct ObjectSizeOpts {
   /// Controls how we handle conditional statements with unknown conditions.
   enum class Mode : uint8_t {
-    /// Fail to evaluate an unknown condition.
-    Exact,
+    /// All branches must be known and have the same size, starting from the
+    /// offset, to be merged.
+    ExactSizeFromOffset,
+    /// All branches must be known and have the same underlying size and offset
+    /// to be merged.
+    ExactUnderlyingSizeAndOffset,
     /// Evaluate all branches of an unknown condition. If all evaluations
     /// succeed, pick the minimum size.
     Min,
     /// Same as Min, except we pick the maximum size of all of the branches.
-    Max
+    Max,
   };
 
   /// How we want to evaluate this object's size.
-  Mode EvalMode = Mode::Exact;
+  Mode EvalMode = Mode::ExactSizeFromOffset;
   /// Whether to round the result up to the alignment of allocas, byval
   /// arguments, and global variables.
   bool RoundToAlign = false;
   /// If this is true, null pointers in address space 0 will be treated as
   /// though they can't be evaluated. Otherwise, null is always considered to
   /// point to a 0 byte region of memory.
   bool NullIsUnknownSize = false;
   /// If set, used for more accurate evaluation

llvm/lib/Analysis/MemoryBuiltins.cpp

Value *llvm::lowerObjectSizeCall(IntrinsicInst *ObjectSize,
   EvalOptions.AA = AA;
 
   // Unless we have to fold this to something, try to be as accurate as
   // possible.
   if (MustSucceed)
     EvalOptions.EvalMode =
         MaxVal ? ObjectSizeOpts::Mode::Max : ObjectSizeOpts::Mode::Min;
   else
-    EvalOptions.EvalMode = ObjectSizeOpts::Mode::Exact;
+    EvalOptions.EvalMode = ObjectSizeOpts::Mode::ExactSizeFromOffset;
 
   EvalOptions.NullIsUnknownSize =
       cast<ConstantInt>(ObjectSize->getArgOperand(2))->isOne();
 
   auto *ResultType = cast<IntegerType>(ObjectSize->getType());
   bool StaticOnly = cast<ConstantInt>(ObjectSize->getArgOperand(3))->isZero();
   if (StaticOnly) {
     // FIXME: Does it make sense to just return a failure value if the size won't
SizeOffsetType ObjectSizeOffsetVisitor::combineSizeOffset(SizeOffsetType LHS,
   if (!bothKnown(LHS) || !bothKnown(RHS))
     return unknown();
 
   switch (Options.EvalMode) {
   case ObjectSizeOpts::Mode::Min:
     return (getSizeWithOverflow(LHS).slt(getSizeWithOverflow(RHS))) ? LHS : RHS;
   case ObjectSizeOpts::Mode::Max:
     return (getSizeWithOverflow(LHS).sgt(getSizeWithOverflow(RHS))) ? LHS : RHS;
-  case ObjectSizeOpts::Mode::Exact:
+  case ObjectSizeOpts::Mode::ExactSizeFromOffset:
     return (getSizeWithOverflow(LHS).eq(getSizeWithOverflow(RHS))) ? LHS
                                                                    : unknown();
+  case ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset:
+    return LHS == RHS && LHS.second.eq(RHS.second) ? LHS : unknown();
   }
   llvm_unreachable("missing an eval mode");
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode &PN) {
   auto IncomingValues = PN.incoming_values();
   return std::accumulate(IncomingValues.begin() + 1, IncomingValues.end(),
                          compute(*IncomingValues.begin()),

llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp

 static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,
                               ScalarEvolution &SE) {
   if (F.hasFnAttribute(Attribute::NoSanitizeBounds))
     return false;
 
   const DataLayout &DL = F.getParent()->getDataLayout();
   ObjectSizeOpts EvalOpts;
   EvalOpts.RoundToAlign = true;
+  EvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;
   ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);
 
   // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
   // touching instructions
   SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;
   for (Instruction &I : instructions(F)) {
     Value *Or = nullptr;
     BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));

llvm/test/Instrumentation/BoundsChecking/simple.ll

dead:
   %l = load i32, ptr %incdec.ptr
   br label %alive
 
 alive:
   ret void
 }
 
 ; Check that merging sizes in a phi works.
-; FIXME: bounds-checking thinks that %alloc has an underlying size of 0.
 define i8 @f14(i1 %i) {
 ; CHECK-LABEL: @f14(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[I:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[A:%.*]] = alloca [32 x i8], align 1
 ; CHECK-NEXT:    [[G:%.*]] = getelementptr i8, ptr [[A]], i32 32
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[ALLOC:%.*]] = phi ptr [ null, [[ENTRY:%.*]] ], [ [[G]], [[BB1]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ 32, [[BB1]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ 32, [[BB1]] ]
+; CHECK-NEXT:    [[ALLOC:%.*]] = phi ptr [ null, [[ENTRY]] ], [ [[G]], [[BB1]] ]
 ; CHECK-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ -4, [[BB1]] ]
-; CHECK-NEXT:    [[TMP0:%.*]] = add i64 0, [[IND]]
+; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[TMP1]], [[IND]]
 ; CHECK-NEXT:    [[P:%.*]] = getelementptr i8, ptr [[ALLOC]], i64 [[IND]]
-; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[TMP0]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i64 0, [[TMP0]]
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP4:%.*]] = or i1 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    br i1 [[TMP4]], label [[TRAP:%.*]], label [[TMP5:%.*]]
-; CHECK:       5:
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP0]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i64 [[TMP0]], [[TMP2]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i64 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP6:%.*]] = or i1 [[TMP4]], [[TMP5]]
+; CHECK-NEXT:    br i1 [[TMP6]], label [[TRAP:%.*]], label [[TMP7:%.*]]
+; CHECK:       7:
 ; CHECK-NEXT:    [[RET:%.*]] = load i8, ptr [[P]], align 1
 ; CHECK-NEXT:    ret i8 [[RET]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap() #[[ATTR5]]
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br i1 %i, label %bb1, label %bb2