[llvm-dev] [RFC] Attribute overhaul 2

[Reid Kleckner via llvm-dev]

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>