llvm dev - Mar 2017 - [RFC] Attribute overhaul 2

LLVM's Attribute APIs need an overhaul.

Current problems
===============
First, testing for an attribute on an Argument is slow.
llvm::AttributeSet::getAttributes(int) consumed 2% of cycles while
optimizing
llc during LTO. Our mid-level optimizations are constantly asking if a given
argument has some attribute (nonnull, dereferencable, etc), and this is
currently linear in the size of the function prototype.  This should be
constant
time.

Adding and removing individual attributes is also inefficient. Every single
attribute addition or removal convenience method, for example, inserts a new
AttributeSet into a FoldingSet. AttributeFuncs::mergeAttributesForInlining
is
written in terms of these APIs, and is therefore quite inefficient. This
also
shows up during LTO. I don't think it's practical to remove these
inherently
expensive APIs, but if we make AttributeBuilder easier to use, it will be a
lot
easier to fix these problems as they come up.

Lastly, the Attribute APIs are hard to use because they do too much
information
hiding. In particular, the choice to make AttributeSetNode an internal
implementation detail of lib/IR is problematic. This type describes all of
the
attributes on an individual argument, return value, or function, which IPO
transforms often want. Today the getFnAttributes, getRetAttributes, and
getParamAttributes APIs find the relevant AttributeSetNode* and wrap it in a
new, uniqued AttributeListImpl. This requires callers to keep around the
index
of the extracted attributes so they can look through the wrapper list. If we
make AttributeSetNode public, we can simplify a lot of IPO transform code.

Naming
=====
The naming of today's APIs is confusing. I'll try to explain what the
current
important classes are.

- AttributeSet: This is a uniqued, ordered list of sets of attributes, and
is
  associated with a function or call prototype. It is stored on Function,
  CallInst, and InvokeInst. It is a smart pointer value type that wraps
  AttributeSetImpl, which contains the actual storage.

- AttributeSetImpl: The private implementation of AttributeSet. Owned by the
  LLVMContext. Today this is a vector of pairs of attribute indices and
  AttributeSetNode pointers.

- AttributeSetNode: This is an ordered, uniqued set of Attributes that might
  apply to a single function, callee, return value, parameter, or
argument.  It
  uses TrailingObjects to store the attributes, and until Jan 2016, tested
for
  attribute presence by a linear scan. Matthias Braum added a bitset to
speed up
  tests in r259251.

- AttributeBuilder: A mutable representation of an AttributeSetNode. Used
for
  efficiently building a collection of attributes before freezing it into an
  AttributeSetNode.

- Attribute: Pointer wrapping an AttributeImpl.

- AttributeImpl: Polymorphic base class of StringAttributeImpl,
  EnumAttributeImpl, and IntAttributeImpl. Enums have the attribute kind,
  integers have a uint64_t value, and strings have two StringRefs for the
kind
  and value.

AttributeSet doesn't seem like a good name to me. In the past it was called
AttrListPtr and PAListPtr. Today's AttributeSetImpl was called
"ParameterAttributeList", which is why we have "PAL" local
variables.  I'd
like
to rename AttributeSet to just "AttributeList".  It's a list of
sets of
attributes that is parallel to some function prototype. I already have a
patch
out for this here: https://reviews.llvm.org/D31102

The natural second thing to do is to rename AttributeSetNode to
AttributeSet, or
create a pointer wrapper type called AttributeSet and rename today's
AttributeSetNode to AttributeSetImpl. It is inherently an ordered set of
attributes. I also propose to make this type public, as described earlier.

Optimizations
============
Testing for presence of an attribute on a parameter should be fast. Today
it is
linear in the size of the prototype. I propose that we change AttributeList
to
make attributes randomly accessible by slot index, so that it stores a
trailing
object array of AttributeSetNode*, or some equivalent type that makes it
efficient to test for attribute presence. I'll do some benchmarking to show
that
this change doesn't measurably impact LTO memory usage.

I also want to reduce the number of loads needed to test a single attribute.
One potential optimization is to move the bitset of enum attributes up out
of
AttributeSetNode* into a wrapper type, perhaps called AttributeSet. The
wrapper
type could be a bitset and pointer pair, or we could try to union those
together
in the usual way to save memory. I suspect the memory savings of the union
are
unimportant, but I will measure. If we can always store the enumerated
attributes that have no associated size locally, that seems ideal, since it
allows modifying them without copying the immutable data stored in the LLVM
context.

Another idea is to eliminate the use of AttributeList completely from
Function,
and instead store the attributes of an Argument directly *in* the Argument.
The
function and return attributes would live on the Function. At the end of the
day, `Arg->hasNonNullAttr()` should compile to a load and a bittest. This
is a
more invasive change that would require more API migration, but again it
would
avoid more FoldingSet usage.

The last two optimizations taken together are particularly nice, because it
means that changing enum attributes on functions and arguments won't trigger
copies of immutable objects. It will only involve flipping bits in a locally
stored bitset.

Separately, I want to collapse dereferenceable(N), nonnull, and
dereferenceable_or_null(N) for efficiency and orthogonality. I will probably
raise this in a separate RFC, but I think it was a mistake to have to
attribute
imply nonnull. I'm mostly looking at this from an efficiency and redundancy
perspective, though, not a semantic one.

----------

Does this all seem reasonable? Speak up now if you think any of this looks
like
a step in the wrong direction.


Notes:

RFC Overhauling Attributes, Bill Wending Sept 2012
https://groups.google.com/forum/#!topic/llvm-dev/RnZVfYmmkMc
User struggle
http://lists.llvm.org/pipermail/llvm-dev/2013-January/058822.html
dereferenceable vs dereferenceable_or_null split
http://thread.gmane.org/gmane.comp.compilers.llvm.devel/82186
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170320/72b48fd0/attachment.html>

Firstly, thanks for looking at this.  I took a look a couple of years ago but
quickly fell in to patch hell with way too many patches all over the compiler!

I did manage to find a few of my changes, and I ultimately focused on specific
APIs which looked expensive.  For example, AttributeSet::addAttributes, or even
just code which looks and feels like its examining internal state, like
AttributeSet::getNumSlots().
> On Mar 20, 2017, at 9:48 AM, Reid Kleckner via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> LLVM's Attribute APIs need an overhaul.
> 
> Current problems
> ===============> 
> First, testing for an attribute on an Argument is slow.
> llvm::AttributeSet::getAttributes(int) consumed 2% of cycles while
optimizing
> llc during LTO. Our mid-level optimizations are constantly asking if a
given
> argument has some attribute (nonnull, dereferencable, etc), and this is
> currently linear in the size of the function prototype.  This should be
constant
> time.
My guess is that arguments having attributes is still a relatively new thing, so
they have just outgrown the implementation.  Back when this was written i don’t
think we were nearly as aggressive about adding or querying things like non null
on arguments so the cost of the implementation wasn’t really
clear.
> 
> Adding and removing individual attributes is also inefficient. Every single
> attribute addition or removal convenience method, for example, inserts a
new
> AttributeSet into a FoldingSet. AttributeFuncs::mergeAttributesForInlining
is
> written in terms of these APIs, and is therefore quite inefficient. This
also
> shows up during LTO. I don't think it's practical to remove these
inherently
> expensive APIs, but if we make AttributeBuilder easier to use, it will be a
lot
> easier to fix these problems as they come up.
I think the worst offender is AttributeSet::addAttributes where we have to build
intermediate sets just to add them to a parent set.

If you completely flatten the list so that return, function, and arguments all
have their own, as you suggest later, then I think you’ll just happen to fix
most of the slow construction APIs.  As you’ve mentioned AttrBuilder, that
probably will handle most of the remaining construction cases
efficiently.
> 
> Lastly, the Attribute APIs are hard to use because they do too much
information
> hiding. In particular, the choice to make AttributeSetNode an internal
> implementation detail of lib/IR is problematic. This type describes all of
the
> attributes on an individual argument, return value, or function, which IPO
> transforms often want. Today the getFnAttributes, getRetAttributes, and
> getParamAttributes APIs find the relevant AttributeSetNode* and wrap it in
a
> new, uniqued AttributeListImpl. This requires callers to keep around the
index
> of the extracted attributes so they can look through the wrapper list. If
we
> make AttributeSetNode public, we can simplify a lot of IPO transform code.
Do you have a particular IPO spot where this looks bad today?  I’d be interested
in taking a look to see whether flattening them out just works here
too?
> 
> Naming
> =====> 
> The naming of today's APIs is confusing. I'll try to explain what
the current
> important classes are.
> 
> - AttributeSet: This is a uniqued, ordered list of sets of attributes, and
is
>   associated with a function or call prototype. It is stored on Function,
>   CallInst, and InvokeInst. It is a smart pointer value type that wraps
>   AttributeSetImpl, which contains the actual storage.
> 
> - AttributeSetImpl: The private implementation of AttributeSet. Owned by
the
>   LLVMContext. Today this is a vector of pairs of attribute indices and
>   AttributeSetNode pointers.
> 
> - AttributeSetNode: This is an ordered, uniqued set of Attributes that
might
>   apply to a single function, callee, return value, parameter, or argument.
It
>   uses TrailingObjects to store the attributes, and until Jan 2016, tested
for
>   attribute presence by a linear scan. Matthias Braum added a bitset to
speed up
>   tests in r259251.
> 
> - AttributeBuilder: A mutable representation of an AttributeSetNode. Used
for
>   efficiently building a collection of attributes before freezing it into
an
>   AttributeSetNode.
> 
> - Attribute: Pointer wrapping an AttributeImpl.
> 
> - AttributeImpl: Polymorphic base class of StringAttributeImpl,
>   EnumAttributeImpl, and IntAttributeImpl. Enums have the attribute kind,
>   integers have a uint64_t value, and strings have two StringRefs for the
kind
>   and value.
> 
> AttributeSet doesn't seem like a good name to me. In the past it was
called
> AttrListPtr and PAListPtr. Today's AttributeSetImpl was called
> "ParameterAttributeList", which is why we have "PAL"
local variables.  I'd like
> to rename AttributeSet to just "AttributeList".  It's a list
of sets of
> attributes that is parallel to some function prototype. I already have a
patch
> out for this here: https://reviews.llvm.org/D31102
<https://reviews.llvm.org/D31102>Thats where PAL came from!  I always
wondered.
> 
> The natural second thing to do is to rename AttributeSetNode to
AttributeSet, or
> create a pointer wrapper type called AttributeSet and rename today's
> AttributeSetNode to AttributeSetImpl. It is inherently an ordered set of
> attributes. I also propose to make this type public, as described earlier.
Whether as an intermediate step, or the final naming, this all seems fine to
me.
> 
> Optimizations
> ============> 
> Testing for presence of an attribute on a parameter should be fast. Today
it is
> linear in the size of the prototype. I propose that we change AttributeList
to
> make attributes randomly accessible by slot index, so that it stores a
trailing
> object array of AttributeSetNode*, or some equivalent type that makes it
> efficient to test for attribute presence. I'll do some benchmarking to
show that
> this change doesn't measurably impact LTO memory usage.
At the very least here, it seems like we should have Argument’s store their
argument number in the Value subclass data or something like that.

uint64_t Argument::getDereferenceableOrNullBytes() const {
  assert(getType()->isPointerTy() &&
         "Only pointers have dereferenceable bytes");
  return getParent()->getDereferenceableOrNullBytes(getArgNo()+1);
}

This is horrible once you realize that getArgNo() is a linear scan over the
arguments then getDereferenceableOrNullBytes() is another linear scan over the
slots.  Worst case 2n just to check a simple value!
> 
> I also want to reduce the number of loads needed to test a single
attribute.
> One potential optimization is to move the bitset of enum attributes up out
of
> AttributeSetNode* into a wrapper type, perhaps called AttributeSet. The
wrapper
> type could be a bitset and pointer pair, or we could try to union those
together
> in the usual way to save memory. I suspect the memory savings of the union
are
> unimportant, but I will measure. If we can always store the enumerated
> attributes that have no associated size locally, that seems ideal, since it
> allows modifying them without copying the immutable data stored in the LLVM
> context.
> 
> Another idea is to eliminate the use of AttributeList completely from
Function,
> and instead store the attributes of an Argument directly *in* the Argument.
The
> function and return attributes would live on the Function. At the end of
the
> day, `Arg->hasNonNullAttr()` should compile to a load and a bittest.
This is a
> more invasive change that would require more API migration, but again it
would
> avoid more FoldingSet usage.
You may get lucky in terms of this change as most of the queries are already on
the argument or the function and can be changed internally to their
hasNonNullAttr (or whatever) methods.

Any of the approaches here sounds fine, and its looks like you’re going to
measure anyway.  I think you’ve already observed that we query these far more
than we construct them, so i’d go for the ‘load and check a bit’ approach.  We
want that query to be as fast as possible.  Even if it means putting a pointer
on every Argument, I expect we have a high enough proportion of Argument’s with
attributes at this point that its likely not too bad.
> 
> The last two optimizations taken together are particularly nice, because it
> means that changing enum attributes on functions and arguments won't
trigger
> copies of immutable objects. It will only involve flipping bits in a
locally
> stored bitset.
> 
> Separately, I want to collapse dereferenceable(N), nonnull, and
> dereferenceable_or_null(N) for efficiency and orthogonality. I will
probably
> raise this in a separate RFC, but I think it was a mistake to have to
attribute
> imply nonnull. I'm mostly looking at this from an efficiency and
redundancy
> perspective, though, not a semantic one.
> 
> ----------
> 
> Does this all seem reasonable? Speak up now if you think any of this looks
like
> a step in the wrong direction.
Seems good to me.

Thanks again for doing this!
Pete
> 
> 
> Notes:
> 
> RFC Overhauling Attributes, Bill Wending Sept 2012
> https://groups.google.com/forum/#!topic/llvm-dev/RnZVfYmmkMc
<https://groups.google.com/forum/#!topic/llvm-dev/RnZVfYmmkMc>
> User struggle
> http://lists.llvm.org/pipermail/llvm-dev/2013-January/058822.html
<http://lists.llvm.org/pipermail/llvm-dev/2013-January/058822.html>
> dereferenceable vs dereferenceable_or_null split
> http://thread.gmane.org/gmane.comp.compilers.llvm.devel/82186
<http://thread.gmane.org/gmane.comp.compilers.llvm.devel/82186>
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170320/c856449e/attachment.html>

On Mon, Mar 20, 2017 at 11:25 PM, Pete Cooper <peter_cooper at apple.com>
wrote:
>
> My guess is that arguments having attributes is still a relatively new
> thing, so they have just outgrown the implementation.  Back when this was
> written i don’t think we were nearly as aggressive about adding or querying
> things like non null on arguments so the cost of the implementation wasn’t
> really clear.
>
Well, we've had argument attributes forever, but yes, they have become much
more common in the last few years now that we use them for more than just
ABI notes.

I think the worst offender is AttributeSet::addAttributes where we have
to
> build intermediate sets just to add them to a parent set.
>
> If you completely flatten the list so that return, function, and arguments
> all have their own, as you suggest later, then I think you’ll just happen
> to fix most of the slow construction APIs.  As you’ve mentioned
> AttrBuilder, that probably will handle most of the remaining construction
> cases efficiently.
>
The addAttributes implementation is obviously very inefficient, but I
suspect it's not on the hot path.

> Do you have a particular IPO spot where this looks bad today?  I’d be
> interested in taking a look to see whether flattening them out just works
> here too?
>
I don't think IPO pass manipulation of attributes is a hotspot, what's
hot
is really just instcombine asking if a value is nonnull. This paragraph was
mostly about making IPO code more readable by changing the
AttributeList::get() API to take a list of AttributeSetNodes instead of a
list of pairs of slot numbers and AttributeSetNodes. DeadArgElim in
particular hacks on AttributeLists, and it's pretty ugly.

> Thats where PAL came from!  I always wondered.
>
Yep. :)
> Testing for presence of an attribute on a parameter should be fast. Today
> it is
> linear in the size of the prototype. I propose that we change
> AttributeList to
> make attributes randomly accessible by slot index, so that it stores a
> trailing
> object array of AttributeSetNode*, or some equivalent type that makes it
> efficient to test for attribute presence. I'll do some benchmarking to
> show that
> this change doesn't measurably impact LTO memory usage.
>
> At the very least here, it seems like we should have Argument’s store
> their argument number in the Value subclass data or something like that.
>
> uint64_t Argument::getDereferenceableOrNullBytes() const {
>   assert(getType()->isPointerTy() &&
>          "Only pointers have dereferenceable bytes");
>   return getParent()->getDereferenceableOrNullBytes(getArgNo()+1);
> }
>
> This is horrible once you realize that getArgNo() is a linear scan over
> the arguments then getDereferenceableOrNullBytes() is another linear scan
> over the slots.  Worst case 2n just to check a simple value!
>
I actually fixed getArgNo() first, that seemed uncontroversial. :)
Arguments store their argument number now, so getArgNo() is just a load. We
could go further and eliminate that field and make it two loads and some
pointer arithmetic as Sanjoy pointed out, but one load seems better than
two to me.

You may get lucky in terms of this change as most of the queries
are
> already on the argument or the function and can be changed internally to
> their hasNonNullAttr (or whatever) methods.
>
Yep. That's the API that users seem to want anyway. All this "PAL"
stuff is
just implementation details to most callers.

> Any of the approaches here sounds fine, and its looks like you’re going to
> measure anyway.  I think you’ve already observed that we query these far
> more than we construct them, so i’d go for the ‘load and check a bit’
> approach.  We want that query to be as fast as possible.  Even if it means
> putting a pointer on every Argument, I expect we have a high enough
> proportion of Argument’s with attributes at this point that its likely not
> too bad.
>
Great. I've also already changed Arguments to not be stored in an iplist in
function, so we have some extra memory headroom here.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170321/3dc6ef89/attachment.html>

Reid,

Thank for you taking a close look at this area.  Attributes definitely 
need a good amount of love.  As you point out, the naming of some of the 
code involved is more than a bit confusing and overly abstracted.  
However, there's also a delicate balance here in terms of having a 
generic understandable API.  In general, I really like your proposal, a 
few comments inline.

On 03/20/2017 09:48 AM, Reid Kleckner wrote:
> LLVM's Attribute APIs need an overhaul.
>
> Current problems
> ===============>
> First, testing for an attribute on an Argument is slow.
> llvm::AttributeSet::getAttributes(int) consumed 2% of cycles while 
> optimizing
> llc during LTO. Our mid-level optimizations are constantly asking if a 
> given
> argument has some attribute (nonnull, dereferencable, etc), and this is
> currently linear in the size of the function prototype. This should be 
> constant
> time.
>
> Adding and removing individual attributes is also inefficient. Every 
> single
> attribute addition or removal convenience method, for example, inserts 
> a new
> AttributeSet into a FoldingSet. 
> AttributeFuncs::mergeAttributesForInlining is
> written in terms of these APIs, and is therefore quite inefficient. 
> This also
> shows up during LTO. I don't think it's practical to remove these 
> inherently
> expensive APIs, but if we make AttributeBuilder easier to use, it will 
> be a lot
> easier to fix these problems as they come up.
One observation I want to highlight is that enum attributes are the most 
common by far, but that string attributes are also widely used.  Despite 
that, there are very few string attributes actually alive in a module at 
any one time.  On the other hand, the presence of an attribute on one 
argument makes it much more likely that other arguments will also have 
that attribute.  (Generally, we either attributed a function, or we 
didn't.)  I don't have an exact design to suggest here, but I strongly 
suspect these observations could lead to an efficient bitset 
representation in the fastpath with a slower fallback path to handle the 
general case.
>
> Lastly, the Attribute APIs are hard to use because they do too much 
> information
> hiding. In particular, the choice to make AttributeSetNode an internal
> implementation detail of lib/IR is problematic. This type describes 
> all of the
> attributes on an individual argument, return value, or function, which IPO
> transforms often want. Today the getFnAttributes, getRetAttributes, and
> getParamAttributes APIs find the relevant AttributeSetNode* and wrap 
> it in a
> new, uniqued AttributeListImpl. This requires callers to keep around 
> the index
> of the extracted attributes so they can look through the wrapper list. 
> If we
> make AttributeSetNode public, we can simplify a lot of IPO transform code.
>
> Naming
> =====>
> The naming of today's APIs is confusing. I'll try to explain what
the
> current
> important classes are.
>
> - AttributeSet: This is a uniqued, ordered list of sets of attributes, 
> and is
>   associated with a function or call prototype. It is stored on Function,
>   CallInst, and InvokeInst. It is a smart pointer value type that wraps
>   AttributeSetImpl, which contains the actual storage.
>
> - AttributeSetImpl: The private implementation of AttributeSet. Owned 
> by the
>   LLVMContext. Today this is a vector of pairs of attribute indices and
>   AttributeSetNode pointers.
>
> - AttributeSetNode: This is an ordered, uniqued set of Attributes that 
> might
>   apply to a single function, callee, return value, parameter, or 
> argument.  It
>   uses TrailingObjects to store the attributes, and until Jan 2016, 
> tested for
>   attribute presence by a linear scan. Matthias Braum added a bitset 
> to speed up
>   tests in r259251.
>
> - AttributeBuilder: A mutable representation of an AttributeSetNode. 
> Used for
>   efficiently building a collection of attributes before freezing it 
> into an
>   AttributeSetNode.
>
> - Attribute: Pointer wrapping an AttributeImpl.
>
> - AttributeImpl: Polymorphic base class of StringAttributeImpl,
>   EnumAttributeImpl, and IntAttributeImpl. Enums have the attribute kind,
>   integers have a uint64_t value, and strings have two StringRefs for 
> the kind
>   and value.
>
> AttributeSet doesn't seem like a good name to me. In the past it was 
> called
> AttrListPtr and PAListPtr. Today's AttributeSetImpl was called
> "ParameterAttributeList", which is why we have "PAL"
local variables.
> I'd like
> to rename AttributeSet to just "AttributeList".  It's a list
of sets of
> attributes that is parallel to some function prototype. I already have 
> a patch
> out for this here: https://reviews.llvm.org/D31102
>
> The natural second thing to do is to rename AttributeSetNode to 
> AttributeSet, or
> create a pointer wrapper type called AttributeSet and rename today's
> AttributeSetNode to AttributeSetImpl. It is inherently an ordered set of
> attributes. I also propose to make this type public, as described earlier.
SGTM.  From an API design perspective, I'd absolutely love to see 
AttributeSet die.  The fact that it represents both the set of 
attributes on a particular operand and the set of attributes across 
*all* operands is needlessly confusing.  (Note: only in the API, the 
implementation is a bit more sane.)   I really like your suggestion to 
rename the current AttributeSet to something like AttributeList and 
publishing the existing AttributeSetNode.   Once we've done that, we can 
update the bulk add/remove APIs to be sane.  The current semantics are 
an utter mess.
>
> Optimizations
> ============>
> Testing for presence of an attribute on a parameter should be fast. 
> Today it is
> linear in the size of the prototype. I propose that we change 
> AttributeList to
> make attributes randomly accessible by slot index, so that it stores a 
> trailing
> object array of AttributeSetNode*, or some equivalent type that makes it
> efficient to test for attribute presence. I'll do some benchmarking to 
> show that
> this change doesn't measurably impact LTO memory usage.
Sounds like a generally good idea.  Maybe we can hide the indexing from 
the client though?  Do something like store the index in the Value 
itself and have the AttributeSet (current name) interface be in terms of 
the Use?  Not a strong requirement or anything, just thinking that might 
keep the interface a bit cleaner.
> I also want to reduce the number of loads needed to test a single 
> attribute.
> One potential optimization is to move the bitset of enum attributes up 
> out of
> AttributeSetNode* into a wrapper type, perhaps called AttributeSet. 
> The wrapper
> type could be a bitset and pointer pair, or we could try to union 
> those together
> in the usual way to save memory. I suspect the memory savings of the 
> union are
> unimportant, but I will measure. If we can always store the enumerated
> attributes that have no associated size locally, that seems ideal, 
> since it
> allows modifying them without copying the immutable data stored in the 
> LLVM
> context.
I got lost here.  Might be good to land some of the renames and then 
restate this.  I think we may be confusing meanings of
AttributeSet?
>
> Another idea is to eliminate the use of AttributeList completely from 
> Function,
> and instead store the attributes of an Argument directly *in* the 
> Argument. The
> function and return attributes would live on the Function. At the end 
> of the
> day, `Arg->hasNonNullAttr()` should compile to a load and a bittest. 
> This is a
> more invasive change that would require more API migration, but again 
> it would
> avoid more FoldingSet usage.
I particularly like this.  It's worth pointing out that we can do the 
same for return values of Invokes and Calls, but that handling parameter 
attributes is much harder.  This is also the point where I'd point out 
that metadata and return attributes have grown to heavily overlap in 
semantic with distinct sets of instructions. Maybe it's time to common 
the implementation, even if the interfaces stay separate?  Once we'd 
done that, we'd have three cases: return attributes/metadata on all 
instructions, parameter attributes on Call and Invoke, and Argument 
attributes on Functions.
>
> The last two optimizations taken together are particularly nice, 
> because it
> means that changing enum attributes on functions and arguments won't 
> trigger
> copies of immutable objects. It will only involve flipping bits in a 
> locally
> stored bitset.
>
> Separately, I want to collapse dereferenceable(N), nonnull, and
> dereferenceable_or_null(N) for efficiency and orthogonality. I will 
> probably
> raise this in a separate RFC, but I think it was a mistake to have to 
> attribute
> imply nonnull. I'm mostly looking at this from an efficiency and 
> redundancy
> perspective, though, not a semantic one.
>
> ----------
>
> Does this all seem reasonable? Speak up now if you think any of this 
> looks like
> a step in the wrong direction.
>
>
> Notes:
>
> RFC Overhauling Attributes, Bill Wending Sept 2012
> https://groups.google.com/forum/#!topic/llvm-dev/RnZVfYmmkMc 
> <https://groups.google.com/forum/#%21topic/llvm-dev/RnZVfYmmkMc>
> User struggle
> http://lists.llvm.org/pipermail/llvm-dev/2013-January/058822.html
> dereferenceable vs dereferenceable_or_null split
> http://thread.gmane.org/gmane.comp.compilers.llvm.devel/82186
>

Getting back to this after a two week hiatus...

On Sat, Mar 25, 2017 at 3:17 PM, Philip Reames <listmail at
philipreames.com>
wrote:
> Reid,
>
> Thank for you taking a close look at this area.  Attributes definitely
> need a good amount of love.  As you point out, the naming of some of the
> code involved is more than a bit confusing and overly abstracted.  However,
> there's also a delicate balance here in terms of having a generic
> understandable API.  In general, I really like your proposal, a few
> comments inline.

Thanks!

The natural second thing to do is to rename AttributeSetNode
to
>> AttributeSet, or
>> create a pointer wrapper type called AttributeSet and rename
today's
>> AttributeSetNode to AttributeSetImpl. It is inherently an ordered set
of
>> attributes. I also propose to make this type public, as described
earlier.
>>
> SGTM.  From an API design perspective, I'd absolutely love to see
> AttributeSet die.  The fact that it represents both the set of attributes
> on a particular operand and the set of attributes across *all* operands is
> needlessly confusing.  (Note: only in the API, the implementation is a bit
> more sane.)   I really like your suggestion to rename the current
> AttributeSet to something like AttributeList and publishing the existing
> AttributeSetNode.   Once we've done that, we can update the bulk
add/remove
> APIs to be sane.  The current semantics are an utter mess.

Yep. AttributeLists shouldn't be a list of more AttributeLists. I've got
a
patch out which tries to untangle that a little bit more:
https://reviews.llvm.org/D31198

With that patch, getParamAttributes(unsigned) returns an AttributeSetNode*
instead of an AttributeList.

>> Optimizations
>> ============>>
>> Testing for presence of an attribute on a parameter should be fast.
Today
>> it is
>> linear in the size of the prototype. I propose that we change
>> AttributeList to
>> make attributes randomly accessible by slot index, so that it stores a
>> trailing
>> object array of AttributeSetNode*, or some equivalent type that makes
it
>> efficient to test for attribute presence. I'll do some benchmarking
to
>> show that
>> this change doesn't measurably impact LTO memory usage.
>>
> Sounds like a generally good idea.  Maybe we can hide the indexing from
> the client though?  Do something like store the index in the Value itself
> and have the AttributeSet (current name) interface be in terms of the Use?
> Not a strong requirement or anything, just thinking that might keep the
> interface a bit cleaner.

Huh, I hadn't considered building the API in terms of Use& or Use*. That
would greatly reduce the need for all these extra integer induction
variables and let us use a lot more range-based for loops. I think we can
compute operand # from Use* in constant time, right? Thanks for the idea!

>
> I also want to reduce the number of loads needed to test a single
>> attribute.
>> One potential optimization is to move the bitset of enum attributes up
>> out of
>> AttributeSetNode* into a wrapper type, perhaps called AttributeSet. The
>> wrapper
>> type could be a bitset and pointer pair, or we could try to union those
>> together
>> in the usual way to save memory. I suspect the memory savings of the
>> union are
>> unimportant, but I will measure. If we can always store the enumerated
>> attributes that have no associated size locally, that seems ideal,
since
>> it
>> allows modifying them without copying the immutable data stored in the
>> LLVM
>> context.
>>
> I got lost here.  Might be good to land some of the renames and then
> restate this.  I think we may be confusing meanings of AttributeSet?

Yeah, I was trying to describe a *new* AttributeSet type. It would probably
look something like:

class AttributeSet {
  uint64_t EnumAttrs; // bitset of that can answer hasAttr with a load and
test
  AttributeSetNode *SlowAttrs; // string and integer attributes
...
};

This would be a trivially copyable value type, and would describe the
attributes of a single function, arg, or ret. AttributeList would become an
array of these. Adding an enum attribute is very cheap now: copy 16 (or 12)
bytes of data and set a bit.

Another idea is to eliminate the use of AttributeList completely
from
>> Function,
>> and instead store the attributes of an Argument directly *in* the
>> Argument. The
>> function and return attributes would live on the Function. At the end
of
>> the
>> day, `Arg->hasNonNullAttr()` should compile to a load and a bittest.
This
>> is a
>> more invasive change that would require more API migration, but again
it
>> would
>> avoid more FoldingSet usage.
>>
> I particularly like this.  It's worth pointing out that we can do the
same
> for return values of Invokes and Calls, but that handling parameter
> attributes is much harder.  This is also the point where I'd point out
that
> metadata and return attributes have grown to heavily overlap in semantic
> with distinct sets of instructions. Maybe it's time to common the
> implementation, even if the interfaces stay separate?  Once we'd done
that,
> we'd have three cases: return attributes/metadata on all instructions,
> parameter attributes on Call and Invoke, and Argument attributes on
> Functions.

As nice as this is, I think I've convinced myself to stop short of doing
this. It's nice if Function, CallInst, and InvokeInst all use the same data
structures to store attributes. As long as Arg->hasAttr(Enum) is O(1), I
think we've won. Moving the data out of the parallel array and into
Argument probably isn't necessary.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170407/b309e9ca/attachment.html>