Add support for nonnull metadata on Loads

[reames]

Summary

This patch simply adds support for marking a load as returning a non-null pointer. This is analogous to the existing nonnull return attribute, but it applies to specific load instructions instead. The value of the load is allowed to vary between successive loads, but null is not a valid value to be loaded by any load marked nonnull.

Hal - I'd particularly like your input here. Is adding a parallel metadata construct to the existing attribute a reasonable idea? Should we be uniform and accept the metadata on calls too? Is there a better way to approach this.

[hfinkel]

• Original Message -----

From: "Philip Reames" <[e-mail]>
To: [e-mail], [e-mail]
Cc: [e-mail]
Sent: Friday, September 5, 2014 4:42:25 PM
Subject: [PATCH] Add support for nonnull metadata on Loads

Hi hfinkel,

This patch simply adds support for marking a load as returning a
non-null pointer. This is analogous to the existing nonnull return
attribute, but it applies to specific load instructions instead.
The value of the load is allowed to vary between successive loads,
but null is not a valid value to be loaded by any load marked
nonnull.

Hal - I'd particularly like your input here. Is adding a parallel
metadata construct to the existing attribute a reasonable idea?
Should we be uniform and accept the metadata on calls too? Is
there a better way to approach this.

Now that the @llvm.assume infrastructure is in place, I can legitimately respond by saying: I think that we can model this by @llvm.assume(x != null). If that currently does not work, then we should fix it.

Thanks again,
Hal

http://reviews.llvm.org/D5220

Files:

lib/Analysis/ValueTracking.cpp
test/Transforms/InstSimplify/compare.ll

[nlewycky]

It would be an entirely new thing, but I would rather this be a
non-metadata attribute on loads, and support nonnull as well as
dereferenceable(n) and possibly other pointer attributes in the future.

[reames]

Adding LangRef changes.

assume(x != nullptr) will follow in a separate review thread.

[hfinkel]

Also, if I might engage in some bikeshedding, I'd prefer that we name this something other than just nonnull, because I'd like to make it more clear that this refers to the value being returned from the load and not the pointer from which the value is being loaded. Maybe result.nonnull or value.nonnull or similar?

docs/LangRef.rst

5223 ↗

(On Diff #13840)

I'd prefer to specify this in the same way that !invariant.load is specified. It says:

The optional ``!invariant.load`` metadata must reference a single
metadata name ``<index>`` corresponding to a metadata node with no 
entries. The existence of the ``!invariant.load`` metadata on the
instruction tells the optimizer...

I'd like to use similar terminology here to talk about what the referenced metadata should be (instead of saying unspecified and meaningless).

[reames]

Finally got around to rephrasing the LangRef as Hal requested.

I chose not to adopt the name result.nonnull. I believe we should stick with precedent here. There's an existing nonnull attribute with the same semantics. I believe using an alternate name would be more confusing.

Hal, with a commitment to handle assume(x != null) in the near future, is this patch good to go?

[hfinkel]

I chose not to adopt the name result.nonnull. I believe we should stick with precedent here. There's an existing nonnull attribute with the same semantics. I believe using an alternate name would be more confusing.

I hate to be a pain, but -- now that I've had time to think about it ;) -- I *really* would like to name this something that makes it clear that the semantics apply to the result, and not the operand -- we *don't* currently have a naming precedent here (for metadata on loads that mirrors argument attributes), and I'd like to set a precedent that makes sense, not one that will lead to confusion. The existing attributes are clearly attached to values, so there is no ambiguity. But here there is a large ambiguity: there are two pointers involved here, and seeing !nonnull next to a load, it would be perfectly reasonable to assume that meant that the address being loaded from is nonnull (and not that the pointer being loaded is nonnull). Let's pick a less-ambiguous name and I think this is good. Let's set a precedent for result.<attr-name> or value.<attr-name> or whatever, I think that will be much better.

[reames]

In D5220#12, @hfinkel wrote:

I chose not to adopt the name result.nonnull. I believe we should stick with precedent here. There's an existing nonnull attribute with the same semantics. I believe using an alternate name would be more confusing.

I hate to be a pain, but -- now that I've had time to think about it ;) -- I *really* would like to name this something that makes it clear that the semantics apply to the result, and not the operand -- we *don't* currently have a naming precedent here (for metadata on loads that mirrors argument attributes), and I'd like to set a precedent that makes sense, not one that will lead to confusion. The existing attributes are clearly attached to values, so there is no ambiguity. But here there is a large ambiguity: there are two pointers involved here, and seeing !nonnull next to a load, it would be perfectly reasonable to assume that meant that the address being loaded from is nonnull (and not that the pointer being loaded is nonnull). Let's pick a less-ambiguous name and I think this is good. Let's set a precedent for result.<attr-name> or value.<attr-name> or whatever, I think that will be much better.

I would appreciate inputs from others on this point.

I don't agree with Hal's points. I don't really see there being much confusion - all metadata and most attributes apply to the value of the instruction, not the operands - and I believe that having two names for the exact same semantics (one attribute, one metadata) is confusing.

If outvoted, I will go along with the majority here, but I believe the naming scheme Hal is proposing would be a mistake.

[hfinkel]

• Original Message -----

From: "Philip Reames" <[e-mail]>
To: [e-mail], [e-mail]
Cc: [e-mail], [e-mail]
Sent: Friday, October 17, 2014 4:28:58 PM
Subject: Re: [PATCH] Add support for nonnull metadata on Loads

In D5220#12, @hfinkel wrote:

I chose not to adopt the name result.nonnull. I believe we should
stick with precedent here. There's an existing nonnull attribute
with the same semantics. I believe using an alternate name would
be more confusing.

I hate to be a pain, but -- now that I've had time to think about
it ;) -- I *really* would like to name this something that makes
it clear that the semantics apply to the result, and not the
operand -- we *don't* currently have a naming precedent here (for
metadata on loads that mirrors argument attributes), and I'd like
to set a precedent that makes sense, not one that will lead to
confusion. The existing attributes are clearly attached to values,
so there is no ambiguity. But here there is a large ambiguity:
there are two pointers involved here, and seeing !nonnull next to
a load, it would be perfectly reasonable to assume that meant that
the address being loaded from is nonnull (and not that the pointer
being loaded is nonnull). Let's pick a less-ambiguous name and I
think this is good. Let's set a precedent for result.<attr-name>
or value.<attr-name> or whatever, I think that will be much
better.

I would appreciate inputs from others on this point.

I don't agree with Hal's points. I don't really see there being much
confusion - all metadata and most attributes apply to the value of
the instruction, not the operands - and I believe that having two
names for the exact same semantics (one attribute, one metadata) is
confusing.

I'm not proposing two different names, I'm proposing a prefix that is used on the metadata name. Many metadata names have prefixes. Also, I reject your premise:

!tbaa, !noalias/!alias.scope, !llvm.mem.parallel_loop_access, all apply to loads, and all refer to properties of the pointer being loaded from. Only !range applies to loads and refers to the value being loaded, and I don't see any particular ambiguity there. There are more types of metadata in the first category than in the second (!invariant.load could, perhaps, be argued either way, so I left it out, but I also view it as more of a loaded-from-pointer property than a property of the value being loaded).

If outvoted, I will go along with the majority here, but I believe
the naming scheme Hal is proposing would be a mistake.

Sounds good. ;)

Thanks again,
Hal

http://reviews.llvm.org/D5220

[reames]

Closed by commit rL220240 (authored by @reames).

llvm/trunk/docs/LangRef.rst

 '``load``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
-      <result> = load [volatile] <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>][, !invariant.load !<index>]
+      <result> = load [volatile] <ty>* <pointer>[, align <alignment>][, !nontemporal !<index>][, !invariant.load !<index>][, !nonnull !<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 ``!invariant.load`` metadata must reference a single
 metadata name ``<index>`` corresponding to a metadata node with no
 entries. The existence of the ``!invariant.load`` metadata on the
 instruction tells the optimizer and code generator that this load
 address points to memory which does not change value during program
 execution. The optimizer may then move this load around, for example, by
 hoisting it out of loops using loop invariant code motion.
 
+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.  
+
 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/lib/Analysis/ValueTracking.cpp

bool llvm::isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI) {
   // A byval, inalloca, or nonnull argument is never null.
   if (const Argument *A = dyn_cast<Argument>(V))
     return A->hasByValOrInAllocaAttr() || A->hasNonNullAttr();
 
   // Global values are not null unless extern weak.
   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
     return !GV->hasExternalWeakLinkage();
 
+  // A Load tagged w/nonnull metadata is never null. 
+  if (const LoadInst *LI = dyn_cast<LoadInst>(V))
+    return LI->getMetadata("nonnull");
+
   if (ImmutableCallSite CS = V)
     if (CS.isReturnNonNull())
       return true;
 
   // operator new never returns null.
   if (isOperatorNewLikeFn(V, TLI, /*LookThroughBitCast=*/true))
     return true;
 
   return false;
 }

llvm/trunk/test/Transforms/InstSimplify/compare.ll

define i1 @returns_nonnull_as_deref() {
   %call = call dereferenceable(4) i32 addrspace(1)* @returns_nonnull_deref_as_helper()
   %cmp = icmp eq i32 addrspace(1)* %call, null
   ret i1 %cmp
 ; CHECK-LABEL: @returns_nonnull_as_deref
 ; CHECK: icmp
 ; CHECK: ret
 }
 
+define i1 @nonnull_load(i32** %addr) {
+  %ptr = load i32** %addr, !nonnull !{}
+  %cmp = icmp eq i32* %ptr, null
+  ret i1 %cmp
+; CHECK-LABEL: @nonnull_load
+; CHECK: ret i1 false
+}
+
+define i1 @nonnull_load_as_outer(i32* addrspace(1)* %addr) {
+  %ptr = load i32* addrspace(1)* %addr, !nonnull !{}
+  %cmp = icmp eq i32* %ptr, null
+  ret i1 %cmp
+; CHECK-LABEL: @nonnull_load_as_outer
+; CHECK: ret i1 false
+}
+define i1 @nonnull_load_as_inner(i32 addrspace(1)** %addr) {
+  %ptr = load i32 addrspace(1)** %addr, !nonnull !{}
+  %cmp = icmp eq i32 addrspace(1)* %ptr, null
+  ret i1 %cmp
+; CHECK-LABEL: @nonnull_load_as_inner
+; CHECK: ret i1 false
+}
+
 ; If a bit is known to be zero for A and known to be one for B,
 ; then A and B cannot be equal.
 define i1 @icmp_eq_const(i32 %a) nounwind {
   %b = mul nsw i32 %a, -2
   %c = icmp eq i32 %b, 1
   ret i1 %c
 
 ; CHECK-LABEL: @icmp_eq_const