<div dir="ltr"><div>LLVM's Attribute APIs need an overhaul.</div><div><br></div><div>Current problems</div><div>================</div><div><br></div><div>First, testing for an attribute on an Argument is slow.</div><div>llvm::AttributeSet::getAttributes(int) consumed 2% of cycles while optimizing</div><div>llc during LTO. Our mid-level optimizations are constantly asking if a given</div><div>argument has some attribute (nonnull, dereferencable, etc), and this is</div><div>currently linear in the size of the function prototype.  This should be constant</div><div>time.</div><div><br></div><div>Adding and removing individual attributes is also inefficient. Every single</div><div>attribute addition or removal convenience method, for example, inserts a new</div><div>AttributeSet into a FoldingSet. AttributeFuncs::mergeAttributesForInlining is</div><div>written in terms of these APIs, and is therefore quite inefficient. This also</div><div>shows up during LTO. I don't think it's practical to remove these inherently</div><div>expensive APIs, but if we make AttributeBuilder easier to use, it will be a lot</div><div>easier to fix these problems as they come up.</div><div><br></div><div>Lastly, the Attribute APIs are hard to use because they do too much information</div><div>hiding. In particular, the choice to make AttributeSetNode an internal</div><div>implementation detail of lib/IR is problematic. This type describes all of the</div><div>attributes on an individual argument, return value, or function, which IPO</div><div>transforms often want. Today the getFnAttributes, getRetAttributes, and</div><div>getParamAttributes APIs find the relevant AttributeSetNode* and wrap it in a</div><div>new, uniqued AttributeListImpl. This requires callers to keep around the index</div><div>of the extracted attributes so they can look through the wrapper list. If we</div><div>make AttributeSetNode public, we can simplify a lot of IPO transform code.</div><div><br></div><div>Naming</div><div>======</div><div><br></div><div>The naming of today's APIs is confusing. I'll try to explain what the current</div><div>important classes are.</div><div><br></div><div>- AttributeSet: This is a uniqued, ordered list of sets of attributes, and is</div><div>  associated with a function or call prototype. It is stored on Function,</div><div>  CallInst, and InvokeInst. It is a smart pointer value type that wraps</div><div>  AttributeSetImpl, which contains the actual storage.</div><div><br></div><div>- AttributeSetImpl: The private implementation of AttributeSet. Owned by the</div><div>  LLVMContext. Today this is a vector of pairs of attribute indices and</div><div>  AttributeSetNode pointers.</div><div><br></div><div>- AttributeSetNode: This is an ordered, uniqued set of Attributes that might</div><div>  apply to a single function, callee, return value, parameter, or argument.  It</div><div>  uses TrailingObjects to store the attributes, and until Jan 2016, tested for</div><div>  attribute presence by a linear scan. Matthias Braum added a bitset to speed up</div><div>  tests in r259251.</div><div><br></div><div>- AttributeBuilder: A mutable representation of an AttributeSetNode. Used for</div><div>  efficiently building a collection of attributes before freezing it into an</div><div>  AttributeSetNode.</div><div><br></div><div>- Attribute: Pointer wrapping an AttributeImpl.</div><div><br></div><div>- AttributeImpl: Polymorphic base class of StringAttributeImpl,</div><div>  EnumAttributeImpl, and IntAttributeImpl. Enums have the attribute kind,</div><div>  integers have a uint64_t value, and strings have two StringRefs for the kind</div><div>  and value.</div><div><br></div><div>AttributeSet doesn't seem like a good name to me. In the past it was called</div><div>AttrListPtr and PAListPtr. Today's AttributeSetImpl was called</div><div>"ParameterAttributeList", which is why we have "PAL" local variables.  I'd like</div><div>to rename AttributeSet to just "AttributeList".  It's a list of sets of</div><div>attributes that is parallel to some function prototype. I already have a patch</div><div>out for this here: <a href="https://reviews.llvm.org/D31102">https://reviews.llvm.org/D31102</a></div><div><br></div><div>The natural second thing to do is to rename AttributeSetNode to AttributeSet, or</div><div>create a pointer wrapper type called AttributeSet and rename today's</div><div>AttributeSetNode to AttributeSetImpl. It is inherently an ordered set of</div><div>attributes. I also propose to make this type public, as described earlier.</div><div><br></div><div>Optimizations</div><div>=============</div><div><br></div><div>Testing for presence of an attribute on a parameter should be fast. Today it is</div><div>linear in the size of the prototype. I propose that we change AttributeList to</div><div>make attributes randomly accessible by slot index, so that it stores a trailing</div><div>object array of AttributeSetNode*, or some equivalent type that makes it</div><div>efficient to test for attribute presence. I'll do some benchmarking to show that</div><div>this change doesn't measurably impact LTO memory usage.</div><div><br></div><div>I also want to reduce the number of loads needed to test a single attribute.</div><div>One potential optimization is to move the bitset of enum attributes up out of</div><div>AttributeSetNode* into a wrapper type, perhaps called AttributeSet. The wrapper</div><div>type could be a bitset and pointer pair, or we could try to union those together</div><div>in the usual way to save memory. I suspect the memory savings of the union are</div><div>unimportant, but I will measure. If we can always store the enumerated</div><div>attributes that have no associated size locally, that seems ideal, since it</div><div>allows modifying them without copying the immutable data stored in the LLVM</div><div>context.</div><div><br></div><div>Another idea is to eliminate the use of AttributeList completely from Function,</div><div>and instead store the attributes of an Argument directly *in* the Argument. The</div><div>function and return attributes would live on the Function. At the end of the</div><div>day, `Arg->hasNonNullAttr()` should compile to a load and a bittest. This is a</div><div>more invasive change that would require more API migration, but again it would</div><div>avoid more FoldingSet usage.</div><div><br></div><div>The last two optimizations taken together are particularly nice, because it</div><div>means that changing enum attributes on functions and arguments won't trigger</div><div>copies of immutable objects. It will only involve flipping bits in a locally</div><div>stored bitset.</div><div><br></div><div>Separately, I want to collapse dereferenceable(N), nonnull, and</div><div>dereferenceable_or_null(N) for efficiency and orthogonality. I will probably</div><div>raise this in a separate RFC, but I think it was a mistake to have to attribute</div><div>imply nonnull. I'm mostly looking at this from an efficiency and redundancy</div><div>perspective, though, not a semantic one.</div><div><br></div><div>----------</div><div><br></div><div>Does this all seem reasonable? Speak up now if you think any of this looks like</div><div>a step in the wrong direction.</div><div><br></div><div><br></div><div>Notes:</div><div><br></div><div>RFC Overhauling Attributes, Bill Wending Sept 2012</div><div><a href="https://groups.google.com/forum/#!topic/llvm-dev/RnZVfYmmkMc">https://groups.google.com/forum/#!topic/llvm-dev/RnZVfYmmkMc</a></div><div>User struggle</div><div><a href="http://lists.llvm.org/pipermail/llvm-dev/2013-January/058822.html">http://lists.llvm.org/pipermail/llvm-dev/2013-January/058822.html</a></div><div>dereferenceable vs dereferenceable_or_null split</div><div><a href="http://thread.gmane.org/gmane.comp.compilers.llvm.devel/82186">http://thread.gmane.org/gmane.comp.compilers.llvm.devel/82186</a></div><div><br></div></div>