[RFC][CodeGen] Emit range metadata for array subscript.

[courbet]

Summary

To allow LLVM to do better alias anaysis. See RFC on llvm-dev.

[courbet]

Forgot to add test file.

clang/lib/CodeGen/CGExpr.cpp

if (const auto *CE = dyn_cast<CastExpr>(Base)) {
       return false;
     }
   }
   return true;
 }
 
 LValue CodeGenFunction::EmitCheckedLValue(const Expr *E, TypeCheckKind TCK) {
   LValue LV;
-  if (SanOpts.has(SanitizerKind::ArrayBounds) && isa<ArraySubscriptExpr>(E))
+  if (isa<ArraySubscriptExpr>(E))
     LV = EmitArraySubscriptExpr(cast<ArraySubscriptExpr>(E), /*Accessed*/true);
   else
     LV = EmitLValue(E);
   if (!isa<DeclRefExpr>(E) && !LV.isBitField() && LV.isSimple()) {
     SanitizerSet SkippedChecks;
     if (const auto *ME = dyn_cast<MemberExpr>(E)) {
       bool IsBaseCXXThis = IsWrappedCXXThis(ME->getBase());
       if (IsBaseCXXThis)
eltPtr = CGF.Builder.CreatePreserveArrayAccessIndex(addr.getElementType(),
                                                         addr.getPointer(),
                                                         indices.size() - 1,
                                                         idx, DbgInfo);
   }
 
   return Address(eltPtr, eltAlign);
 }
 
+// Add range metadata: It is UB to subscript outside of the array, therefore
+// array indices are known to be in range:
+//   * [0, indexing_bound) if the array is accessed.
+//   * [0, indexing_bound] if only address computation is preformed.
+static llvm::Value *addArrayIndexingRangeMetadata(CodeGenFunction &CGF,
+                                                  const Expr *Base,
+                                                  llvm::Value *Idx,
+                                                  bool Accessed) {
+  QualType IdxTy;
+  llvm::ConstantInt *Bound = dyn_cast_or_null<llvm::ConstantInt>(
+      getArrayIndexingBound(CGF, Base, IdxTy));
+  if (Bound == nullptr)
+    return Idx;
+  llvm::Instruction *AnnotatedIdx =
+      CGF.Builder.CreateIntrinsic(llvm::Intrinsic::annotation, {Idx->getType()},
+                                  {Idx, llvm::UndefValue::get(CGF.Int8PtrTy),
+                                   llvm::UndefValue::get(CGF.Int8PtrTy),
+                                   llvm::UndefValue::get(CGF.Int32Ty)});
+  llvm::MDBuilder MDHelper(CGF.getLLVMContext());
+  AnnotatedIdx->setMetadata(
+      llvm::LLVMContext::MD_range,
+      MDHelper.createRange(llvm::APInt(Bound->getBitWidth(), 0),
+                           Bound->getValue() + (Accessed ? 0 : 1)));
+  return AnnotatedIdx;
+}
+
 LValue CodeGenFunction::EmitArraySubscriptExpr(const ArraySubscriptExpr *E,
                                                bool Accessed) {
   // The index must always be an integer, which is not an aggregate.  Emit it
   // in lexical order (this complexity is, sadly, required by C++17).
   llvm::Value *IdxPre =
       (E->getLHS() == E->getIdx()) ? EmitScalarExpr(E->getIdx()) : nullptr;
   bool SignedIndices = false;
   auto EmitIdxAfterBase = [&, IdxPre](bool Promote) -> llvm::Value * {
auto EmitIdxAfterBase = [&, IdxPre](bool Promote) -> llvm::Value * {
 
     if (SanOpts.has(SanitizerKind::ArrayBounds))
       EmitBoundsCheck(E, E->getBase(), Idx, IdxTy, Accessed);
 
     // Extend or truncate the index type to 32 or 64-bits.
     if (Promote && Idx->getType() != IntPtrTy)
       Idx = Builder.CreateIntCast(Idx, IntPtrTy, IdxSigned, "idxprom");
 
+    if (CGM.getCodeGenOpts().OptimizationLevel > 0)
+      Idx = addArrayIndexingRangeMetadata(*this, E->getBase(), Idx, Accessed);
+
     return Idx;
   };
   IdxPre = nullptr;
 
   // If the base is a vector type, then we are forming a vector element lvalue
   // with this subscript.
   if (E->getBase()->getType()->isVectorType() &&
       !isa<ExtVectorElementExpr>(E->getBase())) {

clang/test/CodeGen/array-bounds.cpp

+// RUN: %clang_cc1 -triple x86_64-linux -O1 -disable-llvm-passes %s \
+// RUN:     -emit-llvm -o - | FileCheck %s
+//
+// Check that we generate array bound information for accesses to array
+// elements.
+
+struct A { int i; };
+struct B { A a[1]; };
+struct C { int i; int x[3]; };
+struct D { int i; int* x; };
+struct E { int x[3][5]; };
+
+//TODO: std::array
+
+int deref(C *c, int j) {
+// CHECK-LABEL: _Z5derefP1Ci
+// CHECK: [[INDEX:%.*]] = call i64 @llvm.annotation{{.*}}, !range [[RANGE_0_3:!.*]]
+// CHECK: getelementptr {{.*}} [[INDEX]]
+  return c->x[j];
+}
+
+int deref_noindex(B *b) {
+// CHECK-LABEL: _Z13deref_noindexP1B
+// CHECK-NOT: llvm.annotation
+// CHECK: getelementptr {{.*}}
+  return b->a->i;
+}
+
+int deref_ptr(D *d, int j) {
+// CHECK-LABEL: _Z9deref_ptrP1Di
+// CHECK-NOT: llvm.annotation
+// CHECK: getelementptr {{.*}}
+  return d->x[j];
+}
+
+int deref_multi(E *e, int j, int k) {
+// CHECK-LABEL: _Z11deref_multiP1Eii
+// CHECK: [[INDEX1:%.*]] =  call i64 @llvm.annotation{{.*}}, !range [[RANGE_0_3]]
+// CHECK: getelementptr {{.*}} [[INDEX1]]
+// CHECK: [[INDEX2:%.*]] =  call i64 @llvm.annotation{{.*}}, !range [[RANGE_0_5:!.*]]
+// CHECK: getelementptr {{.*}} [[INDEX2]]
+  return e->x[j][k];
+}
+
+// We are not dereferencing the computed address, it is valid to compute a
+// past-the-end address.
+int* addr(C *c, int j) {
+// CHECK-LABEL: _Z4addrP1Ci
+// CHECK: [[INDEX:%.*]] = call i64 @llvm.annotation{{.*}}, !range [[RANGE_0_4:!.*]]
+// CHECK: getelementptr {{.*}} [[INDEX]]
+  return &c->x[j];
+}
+
+// CHECK-DAG: [[RANGE_0_3]] = !{i64 0, i64 3}
+// CHECK-DAG: [[RANGE_0_4]] = !{i64 0, i64 4}
+// CHECK-DAG: [[RANGE_0_5]] = !{i64 0, i64 5}