This is an archive of the discontinued LLVM Phabricator instance.

Add a dereferencable attribute
ClosedPublic

Authored by hfinkel on Jul 9 2014, 8:19 PM.

Details

Summary

This patch adds a dereferencable attribute. In some sense, this is a companion to the nonnull attribute, but specifies that the pointer is known to be dereferencable in the same sense as a pointer generated by alloca is known to be dereferencable.

My primary use case for this is C++ references that are passes as function parameters and used in loops. For example,

void foo(int * restrict a, int * restrict b, int &c, int n) {

for (int i = 0; i < n; ++i)
  if (a[i] > 0)
    a[i] = c*b[i];

}

Currently, we generate a load of 'c' in every loop iteration because we can't prove that there is no control dependence on the dereferencability of 'c' from the if condition. But because 'c' is a reference, we know it must point to something, and since nothing else in the loop can alias it, it is safe to load it in the preheader.

(there is a simple companion Clang patch, which I'll also post.)

Diff Detail

Event Timeline

hfinkel updated this revision to Diff 11238.Jul 9 2014, 8:19 PM
hfinkel retitled this revision from to Add a dereferencable attribute.
hfinkel updated this object.
hfinkel edited the test plan for this revision. (Show Details)
hfinkel added a subscriber: Unknown Object (MLST).
hfinkel updated this revision to Diff 11292.Jul 10 2014, 2:13 PM

Updated per Nick's comment to include an explicit size (number of bytes). I currently picked 12 bits for the size, I'm not sure if that is a good choice (I did not want to use too many bits, are there only 64 in total?).

Also, I renamed the AlignAttr class to IntAttr (along with all associated functions) because these are now just integer-carrying attributes (not specifically some kind of alignment).

Hi Hal,

Sorry I'm getting to this late, but I have a comment:

/// \brief If this argument has the dereferencable attribute on it in its
/// containing function, return the number of bytes known to be
/// dereferencable.
unsigned getDereferencableBytes() const;

You are later on assuming this function returns zero if the dereferencable attribute is not set, but you do not specify this behaviour in the documentation. Could you please add it?

Cheers,

James

reames edited edge metadata.Jul 10 2014, 3:00 PM

I like the overall direction, but am not crazy about certain parts of the implementation. Specially:

  • the 4096 byte restriction
  • is there any value to a partial pointer to a partially dereferencable pointer? deref(2) i32* doesn't seem to make sense.
  • the consumption of so many bits in the attribute bitmask
  • the documentation
  • the combination of a refactoring and a functional change
docs/LangRef.rst
977

The obvious question left by the documentation is what's the difference between 'nonnull' and 'dereferencable'? Spelling this out explicitly would be helpful.

include/llvm/IR/Argument.h
66

Naming here could be improved.. possibly, getBytesKnownSafeToDereference?

The current name doesn't convey the meaning of the result.

Also, what is returned if the attribute is not present? Zero? Add to the documentation.

include/llvm/IR/Attributes.h
148

This rename should be a separate change.

186

Same issues as before.

Since you have similar accessors throughout, pretend I repeated those comments for each.

lib/AsmParser/LLParser.cpp
1640

This doesn't seem right. It seems like this should only be called from situations where you already have identified the dereferencable keyword. Should this be an assert?

lib/Bitcode/Reader/BitcodeReader.cpp
688

comment update.

lib/IR/Attributes.cpp
429

This encoding seems "unpleasant". We already except string attributes from the masking scheme, would it make sense to separate integer attributes as well? You'd need to leave handling for the existing two, but that might be least ugly option.

Also, 4096 is a fairly arbitrary limit. I could see cases where a array passed by reference would be useful larger than this. Why not have the units be in units of element size? i.e. i32* dereferencable(3) would be 12 bytes. This might make the restricted range much more powerful. (e.g. [i32 x 20000]* dereferencable(1) is a pointer to a array of 20000 elements all of which are dereferencable.)

1029

It might be time to extract an isIntAttrKind(...) function..

1138

What happens if I try to add this twice with different sizes?

test/Transforms/LICM/hoist-deref-load.ll
5

This is a pretty high level test. Could you add a couple of smaller examples? Actually, thinking about this a bit, that might be hard. Feel free to ignore this comment if you can't find smaller examples.

  • Original Message -----

From: "Philip Reames" <listmail@philipreames.com>
To: hfinkel@anl.gov, chandlerc@gmail.com, aschwaighofer@apple.com, nlewycky@google.com, me+llvm@luqman.ca,
listmail@philipreames.com
Cc: "james molloy" <james.molloy@arm.com>, llvm-commits@cs.uiuc.edu
Sent: Thursday, July 10, 2014 5:00:15 PM
Subject: Re: [PATCH] Add a dereferencable attribute

I like the overall direction, but am not crazy about certain parts of
the implementation. Specially:

  • the 4096 byte restriction

I'm not crazy about this either.

  • is there any value to a partial pointer to a partially

dereferencable pointer? deref(2) i32* doesn't seem to make sense.

As Nick pointed out initially, this actually does make sense. Many targets fool with the actual parameter types for ABI reasons (including "padding" them), and it is important to be able to specify that only part of the type size is dereferenceable.

  • the consumption of so many bits in the attribute bitmask

Yep.

  • the documentation

Okay.

  • the combination of a refactoring and a functional change

There really isn't any (aside from the one renaming, which I can certainly commit separately).

Comment at: docs/LangRef.rst:977
@@ +976,3 @@
+ trapping. The number of bytes known to be dereferencable must be
provided
+ in parentheses (only 12-bit values supported).

+

The obvious question left by the documentation is what's the
difference between 'nonnull' and 'dereferencable'? Spelling this
out explicitly would be helpful.

Agreed.

Comment at: include/llvm/IR/Argument.h:65
@@ +64,3 @@
+ /// dereferencable.
+ unsigned getDereferencableBytes() const;

+

Naming here could be improved.. possibly,
getBytesKnownSafeToDereference?

The current name doesn't convey the meaning of the result.

Also, what is returned if the attribute is not present? Zero? Add
to the documentation.

Comment at: include/llvm/IR/Attributes.h:148
@@ -146,1 +147,3 @@
+ /// \brief Return true if the attribute is an integer attribute.
+ bool isIntAttribute() const;

----------------

This rename should be a separate change.

Yea, I'm happy to commit this separately.

Comment at: include/llvm/IR/Attributes.h:186
@@ +185,3 @@
+ /// dereferencable attribute.
+ unsigned getDereferencableBytes() const;

+

Same issues as before.

Since you have similar accessors throughout, pretend I repeated those
comments for each.

Comment at: lib/AsmParser/LLParser.cpp:1630
@@ +1629,3 @@
+ if (!EatIfPresent(lltok::kw_dereferencable))
+ return false;

+ LocTy ParenLoc = Lex.getLoc();

This doesn't seem right. It seems like this should only be called
from situations where you already have identified the dereferencable
keyword. Should this be an assert?

This is done in exactly the same way as the other parametrized attributes. Maybe all of them need some work, but that's a separate issue.

Comment at: lib/Bitcode/Reader/BitcodeReader.cpp:688
@@ -685,3 +687,3 @@

  B.addAttribute(Kind);
} else if (Record[i] == 1) { // Align attribute
  Attribute::AttrKind Kind;

comment update.

Thanks.

Comment at: lib/IR/Attributes.cpp:430
@@ -400,2 +429,3 @@

case Attribute::JumpTable:       return 1ULL << 45;

+ case Attribute::Dereferencable: return 4095ULL << 46;

}

This encoding seems "unpleasant". We already except string
attributes from the masking scheme, would it make sense to separate
integer attributes as well? You'd need to leave handling for the
existing two, but that might be least ugly option.

I'm not sure, and as I recall, we don't actually accept string attributes on parameters, so some more-general changes would be needed.

Also, 4096 is a fairly arbitrary limit. I could see cases where a
array passed by reference would be useful larger than this. Why not
have the units be in units of element size? i.e. i32*
dereferencable(3) would be 12 bytes. This might make the restricted
range much more powerful. (e.g. [i32 x 20000]* dereferencable(1) is
a pointer to a array of 20000 elements all of which are
dereferencable.)

You don't need to convince me to not like the limit, I don't like it. Someone with a better understanding of the bitcode format, I hope, will be able to suggest something better.

Comment at: lib/IR/Attributes.cpp:1029
@@ -980,2 +1028,3 @@

assert((unsigned)Val < Attribute::EndAttrKinds && "Attribute out
of range!");
assert(Val != Attribute::Alignment && Val !=
Attribute::StackAlignment &&

+ Val != Attribute::Dereferencable &&

It might be time to extract an isIntAttrKind(...) function..

Agreed.

Comment at: lib/IR/Attributes.cpp:1138
@@ +1137,3 @@
+AttrBuilder &AttrBuilder::addDereferencableAttr(unsigned Bytes) {
+ if (Bytes == 0) return *this;

+

What happens if I try to add this twice with different sizes?

The same thing as happens for an alignment (it replaces the previous one, IIRC).

Comment at: test/Transforms/LICM/hoist-deref-load.ll:4
@@ +3,3 @@
+target triple = "x86_64-unknown-linux-gnu"
+

+; This test represents the following function:

This is a pretty high level test. Could you add a couple of smaller
examples? Actually, thinking about this a bit, that might be hard.
Feel free to ignore this comment if you can't find smaller
examples.

I don't know of any either.

Thanks again,
Hal

http://reviews.llvm.org/D4449

hfinkel updated this revision to Diff 11306.Jul 10 2014, 9:42 PM
hfinkel edited edge metadata.

I believe that this should address everyone's suggestions. Notably:

  • We're no longer limited to 12 bits (a full 64-bit unsigned value is accepted). The only downside is that we cannot use this attribute with the bitmask scheme used by older bitcode (and perhaps uses of the older associated C API?), but I don't think this is a major problem.
  • For addrspace(0), this attribute also implies nonnull (so we don't need to have both).
hfinkel updated this revision to Diff 11309.Jul 10 2014, 10:49 PM

Added a test that the dereferenceable attribute on a non-addrspace(0) pointer does not imply nonnull.

jfb added a subscriber: jfb.Jul 11 2014, 10:58 AM

Looks good to me, besides two small comments.

include/llvm/IR/Attributes.h
91

You'll make some people sad (not PNaCl, but Renderscript and others) by adding the attribute here in the enum instead of at the end, since it changes bitcode slightly.

lib/IR/Attributes.cpp
93

Math bikeshed: "non-zero" seems better than "positive".

jvoung added a subscriber: jvoung.Jul 11 2014, 11:21 AM
jvoung added inline comments.
include/llvm/Bitcode/LLVMBitCodes.h
378

DEFERERENCEABLE -> DEREFERENCEABLE ?

include/llvm/IR/Attributes.h
91

I think the enum in the bitc:: namespace is the one that affects serialized bitcode and not this enum?

I'm happy with the new encodings. Some of my previous comments still stand (naming, comments, etc..), but the overall structure looks good.

I am uncomfortable with the coupling of dereferenceable and nonnull. I don't have an actual counter example, but could we separate that from the current patch and revisit it separately?

Thinking out loud, I wonder about a truly perverse runtime system that wanted to use loads from null+offset to represent calls to runtime functions. The signal handler could advance the PC and parse the load instruction to "return" a value in the right register. This would be a "dereferenceable" load (very indirectly!), but not non-null. I don't think you could represent this in LLVM for other reasons, but it's the best I could do on the spot. :)

  • Original Message -----

From: "Philip Reames" <listmail@philipreames.com>
To: hfinkel@anl.gov, chandlerc@gmail.com, aschwaighofer@apple.com, nlewycky@google.com, me+llvm@luqman.ca,
listmail@philipreames.com
Cc: jvoung@chromium.org, jfb@chromium.org, "james molloy" <james.molloy@arm.com>, llvm-commits@cs.uiuc.edu
Sent: Friday, July 11, 2014 4:27:10 PM
Subject: Re: [PATCH] Add a dereferencable attribute

I'm happy with the new encodings.

Good, I like it better too :-)

Some of my previous comments still
stand (naming, comments, etc..), but the overall structure looks
good.

Alright, I want to be clear about this, because I thought that I had addressed your comments...

  • I will commit separately the AlignAttr -> IntAttr renaming
  • Regarding getDereferenceableBytes -> getBytesKnownSafeToDereference (or similar), I'm not thrilled by the idea of making a long name even longer, and I think that Dereferenceable implies safety. Would getDereferenceableByteCount be better?
  • If there is anything else under "naming", please clarify.
  • There is now some note on every getDereferenceableBytes function stating that zero is returned when the answer is unknown, and the LangRef text has been updated based on your comments.
  • Is there anything else under 'etc.'?

I am uncomfortable with the coupling of dereferenceable and nonnull.
I don't have an actual counter example, but could we separate that
from the current patch and revisit it separately?

We could, but it would cause a lot of test-case churn (on the Clang side) and I'd rather not. Realistically, the fact that dereferenceablility imples nonnull (only for addrspace(0)) is baked into several pieces of LLVM and specified in the language reference.

Thanks again,
Hal

Thinking out loud, I wonder about a truly perverse runtime system
that wanted to use loads from null+offset to represent calls to
runtime functions. The signal handler could advance the PC and
parse the load instruction to "return" a value in the right
register. This would be a "dereferenceable" load (very
indirectly!), but not non-null. I don't think you could represent
this in LLVM for other reasons, but it's the best I could do on the
spot. :)

http://reviews.llvm.org/D4449

hfinkel added inline comments.Jul 17 2014, 10:35 PM
include/llvm/Bitcode/LLVMBitCodes.h
378

Indeed :-)

include/llvm/IR/Attributes.h
91

Correct, the bitc:: ones are encoded.

lib/IR/Attributes.cpp
93

Agreed (the number is unsigned).

hfinkel accepted this revision.Jul 18 2014, 9:04 AM
hfinkel added a reviewer: hfinkel.

Reviewers approved, will close.

This revision is now accepted and ready to land.Jul 18 2014, 9:04 AM
hfinkel closed this revision.Jul 18 2014, 9:04 AM

r213385, thanks!