Dereferenceable, dereferenceable_or_null metadata for loads

[apilipenko]

Summary

Introduce dereferenceable, dereferenceable_or_null metadata for loads with the same semantic as corresponding attributes.

This patch depends on http://reviews.llvm.org/D9253

[reames]

Code wise, looks fine. The tests need a bit more coverage and you need to update the LangRef. Once that's done, should be easy to do a final signoff.

Although, am I correct in believing your second test is dependent on your LICM changes? If so, you might want to separate that test case for the moment. I suspect this patch will be landing first.

test/Analysis/ValueTracking/memory-dereferenceable.ll

32 ↗

(On Diff #24689)

I'd really like to see some more exhaustive testing here. Cases to cover include:
load from an offset not covered by the dereferenceable portion
load from a potentially null point with dereferenceable_or_null
load from a non-null pointer with dereferenceable_or_null (i.e. pointer has nonnull metadata as well)

[apilipenko]

LangRef updated, more tests added.

[apilipenko]

ValueTracking part is also dependant on LICM changes. So I plan to integrate it after the LICM patch.

[reames]

LGTM

[sanjoy]

Minor comment inline for post-commit review.

lib/Analysis/ValueTracking.cpp

2880 ↗

(On Diff #24689)

In both the places, instead of doing

MDNode *MD = ...
if (MD)

you can do

if (MDNode *MD = ...)

[sanjoy]

This does not apply cleanly after applying D9253 -- I'll check in D9253 shortly, can you rebase on master once I have done that?

[apilipenko]

Rebased version.

llvm/trunk/docs/LangRef.rst

 '``load``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = load [volatile] <ty>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>][, !invariant.load !<index>][, !nonnull !<index>]
+      <result> = load [volatile] <ty>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>][, !invariant.load !<index>][, !nonnull !<index>][, !dereferenceable !<index>][, !dereferenceable_or_null !<index>]
       <result> = load atomic [volatile] <ty>* <pointer> [singlethread] <ordering>, align <alignment>
       !<index> = !{ i32 1 }
 
 Overview:
 """""""""
 
 The '``load``' instruction is used to read from memory.
 

 The optional ``!nonnull`` metadata must reference a single
 metadata name ``<index>`` corresponding to a metadata node with no
 entries. The existence of the ``!nonnull`` metadata on the
 instruction tells the optimizer that the value loaded is known to
 never be null.  This is analogous to the ''nonnull'' attribute
 on parameters and return values.  This metadata can only be applied
 to loads of a pointer type.
 
+The optional ``!dereferenceable`` metadata must reference a single
+metadata name ``<index>`` corresponding to a metadata node with one ``i64``
+entry. The existence of the ``!dereferenceable`` metadata on the instruction 
+tells the optimizer that the value loaded is known to be dereferenceable.
+The number of bytes known to be dereferenceable is specified by the integer 
+value in the metadata node. This is analogous to the ''dereferenceable'' 
+attribute on parameters and return values.  This metadata can only be applied 
+to loads of a pointer type.
+
+The optional ``!dereferenceable_or_null`` metadata must reference a single
+metadata name ``<index>`` corresponding to a metadata node with one ``i64``
+entry. The existence of the ``!dereferenceable_or_null`` metadata on the 
+instruction tells the optimizer that the value loaded is known to be either
+dereferenceable or null.
+The number of bytes known to be dereferenceable is specified by the integer 
+value in the metadata node. This is analogous to the ''dereferenceable_or_null'' 
+attribute on parameters and return values.  This metadata can only be applied 
+to loads of a pointer type.
+
 Semantics:
 """"""""""
 
 The location of memory pointed to is loaded. If the value being loaded
 is of scalar type then the number of bytes read does not exceed the
 minimum number of bytes needed to hold all bits of the type. For
 example, loading an ``i24`` reads at most three bytes. When loading a
 value of a type like ``i20`` with a size that is not an integral number

llvm/trunk/include/llvm/IR/LLVMContext.h

enum {
     MD_fpmath = 3,  // "fpmath"
     MD_range = 4, // "range"
     MD_tbaa_struct = 5, // "tbaa.struct"
     MD_invariant_load = 6, // "invariant.load"
     MD_alias_scope = 7, // "alias.scope"
     MD_noalias = 8, // "noalias",
     MD_nontemporal = 9, // "nontemporal"
     MD_mem_parallel_loop_access = 10, // "llvm.mem.parallel_loop_access"
-    MD_nonnull = 11 // "nonnull"
+    MD_nonnull = 11, // "nonnull"
+    MD_dereferenceable = 12, // "dereferenceable"
+    MD_dereferenceable_or_null = 13 // "dereferenceable_or_null"
   };
 
   /// getMDKindID - Return a unique non-zero ID for the specified metadata kind.
   /// This ID is uniqued across modules in the current LLVMContext.
   unsigned getMDKindID(StringRef Name) const;
 
   /// getMDKindNames - Populate client supplied SmallVector with the name for
   /// custom metadata IDs registered in this LLVMContext.

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (!DerefBytes.getBoolValue()) {
       CheckForNonNull = true;
     }
   } else if (auto CS = ImmutableCallSite(BV)) {
     DerefBytes = CS.getDereferenceableBytes(0);
     if (!DerefBytes.getBoolValue()) {
       DerefBytes = CS.getDereferenceableOrNullBytes(0);
       CheckForNonNull = true;
     }
+  } else if (const LoadInst *LI = dyn_cast<LoadInst>(BV)) {
+    if (MDNode *MD = LI->getMetadata(LLVMContext::MD_dereferenceable)) {
+      ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
+      DerefBytes = CI->getLimitedValue();
+    }
+    if (!DerefBytes.getBoolValue()) {
+      if (MDNode *MD = 
+              LI->getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
+        ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(0));
+        DerefBytes = CI->getLimitedValue();
+      }
+      CheckForNonNull = true;
+    }
   }
   
   if (DerefBytes.getBoolValue())
     if (DerefBytes.uge(Offset + DL.getTypeStoreSize(Ty)))
       if (!CheckForNonNull || isKnownNonNullAt(BV, CtxI, DT, TLI))
         return true;
 
   return false;

llvm/trunk/lib/IR/LLVMContext.cpp

LLVMContext::LLVMContext() : pImpl(new LLVMContextImpl(*this)) {
   (void)NonTemporalID;
 
   // Create the 'llvm.mem.parallel_loop_access' metadata kind.
   unsigned MemParallelLoopAccessID = getMDKindID("llvm.mem.parallel_loop_access");
   assert(MemParallelLoopAccessID == MD_mem_parallel_loop_access &&
          "mem_parallel_loop_access kind id drifted");
   (void)MemParallelLoopAccessID;
 
-
   // Create the 'nonnull' metadata kind.
   unsigned NonNullID = getMDKindID("nonnull");
   assert(NonNullID == MD_nonnull && "nonnull kind id drifted");
   (void)NonNullID;
+  
+  // Create the 'dereferenceable' metadata kind.
+  unsigned DereferenceableID = getMDKindID("dereferenceable");
+  assert(DereferenceableID == MD_dereferenceable && 
+         "dereferenceable kind id drifted");
+  (void)DereferenceableID;
+  
+  // Create the 'dereferenceable_or_null' metadata kind.
+  unsigned DereferenceableOrNullID = getMDKindID("dereferenceable_or_null");
+  assert(DereferenceableOrNullID == MD_dereferenceable_or_null && 
+         "dereferenceable_or_null kind id drifted");
+  (void)DereferenceableOrNullID;
 }
 LLVMContext::~LLVMContext() { delete pImpl; }
 
 void LLVMContext::addModule(Module *M) {
   pImpl->OwnedModules.insert(M);
 }
 
 void LLVMContext::removeModule(Module *M) {

llvm/trunk/test/Analysis/ValueTracking/memory-dereferenceable.ll

 ; RUN: opt -print-memderefs -analyze -S <%s | FileCheck %s
 
 ; Uses the print-deref (+ analyze to print) pass to run
 ; isDereferenceablePointer() on many load instruction operands
 
 target datalayout = "e"
 
 declare zeroext i1 @return_i1()
 
 @globalstr = global [6 x i8] c"hello\00"
+@globali32ptr = external global i32*
 
 define void @test(i32 addrspace(1)* dereferenceable(8) %dparam) gc "statepoint-example" {
 ; CHECK: The following are dereferenceable:
 ; CHECK: %globalptr
 ; CHECK: %alloca
 ; CHECK: %dparam
 ; CHECK: %relocate
+; CHECK: %d4_load
+; CHECK: %d_or_null_non_null_load
 ; CHECK-NOT: %nparam
+; CHECK-NOT: %nd_load
+; CHECK-NOT: %d2_load
+; CHECK-NOT: %d_or_null_load
 entry:
     %globalptr = getelementptr inbounds [6 x i8], [6 x i8]* @globalstr, i32 0, i32 0
     %load1 = load i8, i8* %globalptr
     %alloca = alloca i1
     %load2 = load i1, i1* %alloca
     %load3 = load i32, i32 addrspace(1)* %dparam
     %tok = tail call i32 (i64, i32, i1 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i1f(i64 0, i32 0, i1 ()* @return_i1, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %dparam)
     %relocate = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32 %tok, i32 7, i32 7)
     %load4 = load i32, i32 addrspace(1)* %relocate
     %nparam = getelementptr i32, i32 addrspace(1)* %dparam, i32 5
     %load5 = load i32, i32 addrspace(1)* %nparam
+
+    ; Load from a non-dereferenceable load
+    %nd_load = load i32*, i32** @globali32ptr, !dereferenceable !0
+    %load6 = load i32, i32* %nd_load
+
+    ; Load from a dereferenceable load
+    %d4_load = load i32*, i32** @globali32ptr, !dereferenceable !0
+    %load7 = load i32, i32* %d4_load
+
+    ; Load from an offset not covered by the dereferenceable portion
+    %d2_load = load i32*, i32** @globali32ptr, !dereferenceable !1
+    %load8 = load i32, i32* %d2_load
+
+    ; Load from a potentially null pointer with dereferenceable_or_null
+    %d_or_null_load = load i32*, i32** @globali32ptr, !dereferenceable_or_null !0
+    %load9 = load i32, i32* %d_or_null_load
+
+    ; Load from a non-null pointer with dereferenceable_or_null
+    %d_or_null_non_null_load = load i32*, i32** @globali32ptr, !nonnull !2, !dereferenceable_or_null !0
+    %load10 = load i32, i32* %d_or_null_non_null_load
+
     ret void
 }
 
 declare i32 @llvm.experimental.gc.statepoint.p0f_i1f(i64, i32, i1 ()*, i32, i32, ...)
-declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32, i32, i32)
+declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32, i32, i32)
+
+!0 = !{i64 4}
+!1 = !{i64 2}
+!2 = !{}

llvm/trunk/test/Transforms/LICM/hoist-deref-load.ll

for.inc:                                          ; preds = %for.body, %if.then
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.inc, %entry
   ret i1 %not_null
 }
 
-attributes #0 = { nounwind uwtable }
+; This test represents the following function:
+; void test1(int * __restrict__ a, int *b, int **cptr, int n) {
+;   c = *cptr;
+;   for (int i = 0; i < n; ++i)
+;     if (a[i] > 0)
+;       a[i] = (*c)*b[i];
+; }
+; and we want to hoist the load of %c out of the loop. This can be done only
+; because the dereferenceable meatdata on the c = *cptr load.
+
+; CHECK-LABEL: @test7
+; CHECK: load i32, i32* %c, align 4
+; CHECK: for.body:
+
+define void @test7(i32* noalias %a, i32* %b, i32** %cptr, i32 %n) #0 {
+entry:
+  %c = load i32*, i32** %cptr, !dereferenceable !0
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry
+  ret void
+}
+
+; This test represents the following function:
+; void test1(int * __restrict__ a, int *b, int **cptr, int n) {
+;   c = *cptr;
+;   if (c != null)
+;     for (int i = 0; i < n; ++i)
+;       if (a[i] > 0)
+;         a[i] = (*c)*b[i];
+; }
+; and we want to hoist the load of %c out of the loop. This can be done only
+; because the dereferenceable_or_null meatdata on the c = *cptr load and there 
+; is a null check on %c.
+
+; CHECK-LABEL: @test8
+; CHECK: load i32, i32* %c, align 4
+; CHECK: for.body:
+
+define void @test8(i32* noalias %a, i32* %b, i32** %cptr, i32 %n) #0 {
+entry:
+  %c = load i32*, i32** %cptr, !dereferenceable_or_null !0
+  %not_null = icmp ne i32* %c, null
+  br i1 %not_null, label %not.null, label %for.end
+
+not.null:
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
+
+for.body:                                         ; preds = %not.null, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %not.null ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry, %not.null
+  ret void
+}
+
+; This is the same as @test8, but without the null check on %c.
+; Without this check, we should not hoist the load of %c.
+
+; CHECK-LABEL: @test9
+; CHECK: if.then:
+; CHECK: load i32, i32* %c, align 4
+
+define void @test9(i32* noalias %a, i32* %b, i32** %cptr, i32 %n) #0 {
+entry:
+  %c = load i32*, i32** %cptr, !dereferenceable_or_null !0
+  %cmp11 = icmp sgt i32 %n, 0
+  br i1 %cmp11, label %for.body, label %for.end
 
+for.body:                                         ; preds = %entry, %for.inc
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %cmp1 = icmp sgt i32 %0, 0
+  br i1 %cmp1, label %if.then, label %for.inc
+
+if.then:                                          ; preds = %for.body
+  %1 = load i32, i32* %c, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
+  %2 = load i32, i32* %arrayidx3, align 4
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.inc, %entry
+  ret void
+}
+
+attributes #0 = { nounwind uwtable }
+!0 = !{i64 4}