On Tue, Jun 21, 2011 at 12:37 AM, Nicola Pero
<nicola.p...@meta-innovation.com> wrote:
> This patch speeds up the C/C++/ObjC/ObjC++ compiler a little bit by optimizing
> lookup_attribute() and is_attribute_p(). The main change is that these
> functions
> are now inline.
I don't think this is a good idea. And I doubt that inlining the loops
is what makes it fast - so, what's the common case that makes
inlining these so much faster?
Btw, the tree.c diff is quite unreadable (stupid diff tool ...), can you
instead attach a context diff?
> Benchmarking the C compiler (--enable-checking=release) compiling postgresql
> from
> source shows that total compilation times are reduced by about 0.4% with this
> patch
> (saving about 1 second over an average compilation time of 167 seconds).
> Benchmarking
> the C++ compiler compiling gold from source shows a similar speedup (about
> 0.5%).
> Not a huge speedup, but a real one.
>
> The original version of the patch was meant to speed up the Objective-C
> compiler
> and used preprocessor macros and some hacks to get a similar performance
> benefit
> in an uglier way. I prefer this new version because inline functions make
> the code
> neat and easy to read/understand, while providing similar performance
> benefits.
>
> The patch contains the following changes:
>
> * a tiny tweak in attribs.c to avoid looking up the attribute specs
> for the "naked" attribute for each and every function. If the
> function has no attributes whatsoever, the lookup is pointless.
This change is ok.
> * a tiny tweak in tree.c to speed up attribute_list_equal() which is
> almost always called with two identical pointers.
As said, the diff is quite unreadable - I'll have a look at a context
diff if you post it. The change as described sounds reasonable.
> * inling of lookup_attribute() and is_attribute_p(). Most of the speedup
> (at least for the C/ObjC compiler, I haven't really studied the C++ one;
> it's probably the same) comes from the inling of lookup_attribute().
> The reason inlining these functions is a winner is not just because we save
> a function call each time they are used, but also because the
> inlining allows further optimizations to be applied; in particular,
> the first argument (the attribute name) is almost always a fixed
> string (eg, lookup_attribute ("visibility", attrs)) and inlining
> allows the compiler to optimize the strlen() of the first argument.
So, why not for example have lookup_attribute_with_length ()?
> In the case of lookup_attribute(), the attribute list argument is
> also almost always NULL; before this patch, even with a NULL attribute
> argument, you'd still perform at least the function call to
> lookup_attribute()
> and then the strlen() of the first argument. With this patch, if
> the attribute list argument is NULL and the first argument is a string
> constant,
> which is the most likely case, nothing (expensive) should usually happen.
For this case I'd factor out the NULL attribute list check into an
inline function and keeping the non-NULL attribute list pieces out-of-line.
>
> * changes to lookup_attribute(), is_attribute_p() and remove_attribute()
> to require the first const char* argument to be in the form "text",
> disallowing the form "__text__" (the form "__text__" is still allowed
> in the attribute list; changing that is another simplification I'd like
> to make, but requires another wave of work). The only place in the compiler
> where the form "__text__" was required was inside tree.c, precisely inside
> functions that are comparing/merging attribute lists. There I
> replaced lookup_attribute() with a new static lookup_ident_attribute()
> which closely matches what is required there. I couldn't find any other
> place in the
> compiler where the form "__text__" would be required for the first argument,
> so it seemed pointless to allow it (particularly as, with the inlining, it
> would now bloat the code). I did document this change, and added asserts to
> catch cases that may have been missed (and, of course, it all still
> bootstraps with checking enabled, and works fine for me after the change).
> I
> also added an assert in attribs.c where attribute specs are registered
> to make sure that the names do not start with "_".
Does it work for all languages? And yes, I agree it would be nice to
canonicalize to the form without _s even in the attribute lists itself.
Or go one step further - do not store an identifier but an enum as we
in fact only ever insert known attributes into the list (which should
be a VEC instead, possibly even sorted to allow binary search).
> * some tidyups in tree.c (in particular, the removal of
> is_attribute_with_length_p(),
> and the addition of lookup_ident_attribute(), which are internal details,
> consequences
> of the changes above).
Thanks,
Richard.
> OK to commit ?
>
> Thanks
>
> PS: The next steps would be:
>
> - move all the "attribute list" functions from tree.h/tree.c (ie,
> lookup_attribute(), remove_attribute(),
> merge_attributes(), etc) into a separate .h/.c file ? Presumably
> attribs.h/attribs.c ?
>
> - see if we can manage to normalize attributes (eg, from '__text__' to
> 'text') when storing them in attribute
> lists; this would simplify/speedup the lookup_attribute() inline call. I
> expect that would result in faster
> compilation, but obviously would need to benchmark.
>
> I'll submit these as separate patches if I work on them; this one is big
> enough.
>
> PS2: While doing benchmarks, I accidentally benchmarked an older trunk and
> couldn't but notice that compiling
> gold with the C++ compiler regressed, in terms of performance, by 1.5%
> from 2011-05-19 to 2011-06-20.
>
>
> Index: ChangeLog
> ===================================================================
> --- ChangeLog (revision 173917)
> +++ ChangeLog (working copy)
> @@ -1,3 +1,24 @@
> +2011-06-19 Nicola Pero <nicola.p...@meta-innovation.com>
> +
> + * attribs.c (register_attribute): Added assert to check that all
> + attribute specs are registered with a name that is not empty and
> + does not start with '_'.
> + (decl_attributes): Avoid the lookup of the "naked" attribute spec
> + if the function has no attributes.
> + * tree.c (is_attribute_with_length_p): Removed.
> + (is_attribute_p): Removed.
> + (remove_attribute): Use is_attribute_p instead of
> + is_attribute_with_length_p.
> + (merge_dllimport_decl_attributes): Likewise.
> + (lookup_ident_attribute): New.
> + (merge_attributes): Use lookup_ident_attributes instead of
> + lookup_attribute.
> + (attribute_list_contained): Likewise.
> + (attribute_list_equal): Immediately return 1 if the arguments are
> + identical pointers.
> + * tree.h (is_attribute_p, lookup_attribute): New inline functions.
> + Updated comments.
> +
> 2011-05-19 Joseph Myers <jos...@codesourcery.com>
>
> * config/arm/arm-fpus.def: New.
> Index: attribs.c
> ===================================================================
> --- attribs.c (revision 173917)
> +++ attribs.c (working copy)
> @@ -198,6 +198,11 @@ register_attribute (const struct attribute_spec *a
>
> str.str = attr->name;
> str.length = strlen (str.str);
> +
> + /* Attribute names in the table must be in the form 'text' and not
> + in the form '__text__'. */
> + gcc_assert (str.length > 0 && str.str[0] != '_');
> +
> slot = htab_find_slot_with_hash (attribute_hash, &str,
> substring_hash (str.str, str.length),
> INSERT);
> @@ -279,6 +284,7 @@ decl_attributes (tree *node, tree attributes, int
> /* A "naked" function attribute implies "noinline" and "noclone" for
> those targets that support it. */
> if (TREE_CODE (*node) == FUNCTION_DECL
> + && attributes
> && lookup_attribute_spec (get_identifier ("naked"))
> && lookup_attribute ("naked", attributes) != NULL)
> {
> Index: tree.c
> ===================================================================
> --- tree.c (revision 173917)
> +++ tree.c (working copy)
> @@ -5235,101 +5235,80 @@ struct simple_ipa_opt_pass pass_ipa_free_lang_data
> }
> };
>
> -/* Return nonzero if IDENT is a valid name for attribute ATTR,
> - or zero if not.
> +/* Remove any instances of attribute ATTR_NAME in LIST and return the
> + modified list. */
>
> - We try both `text' and `__text__', ATTR may be either one. */
> -/* ??? It might be a reasonable simplification to require ATTR to be only
> - `text'. One might then also require attribute lists to be stored in
> - their canonicalized form. */
> -
> -static int
> -is_attribute_with_length_p (const char *attr, int attr_len, const_tree ident)
> +tree
> +remove_attribute (const char *attr_name, tree list)
> {
> - int ident_len;
> - const char *p;
> + gcc_checking_assert (attr_name[0] != '_');
>
> - if (TREE_CODE (ident) != IDENTIFIER_NODE)
> - return 0;
> -
> - p = IDENTIFIER_POINTER (ident);
> - ident_len = IDENTIFIER_LENGTH (ident);
> -
> - if (ident_len == attr_len
> - && strcmp (attr, p) == 0)
> - return 1;
> -
> - /* If ATTR is `__text__', IDENT must be `text'; and vice versa. */
> - if (attr[0] == '_')
> + if (list != NULL_TREE)
> {
> - gcc_assert (attr[1] == '_');
> - gcc_assert (attr[attr_len - 2] == '_');
> - gcc_assert (attr[attr_len - 1] == '_');
> - if (ident_len == attr_len - 4
> - && strncmp (attr + 2, p, attr_len - 4) == 0)
> - return 1;
> + tree *p;
> +
> + for (p = &list; *p; )
> + {
> + if (is_attribute_p (attr_name, TREE_PURPOSE (*p)))
> + *p = TREE_CHAIN (*p);
> + else
> + p = &TREE_CHAIN (*p);
> + }
> + return list;
> }
> - else
> - {
> - if (ident_len == attr_len + 4
> - && p[0] == '_' && p[1] == '_'
> - && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
> - && strncmp (attr, p + 2, attr_len) == 0)
> - return 1;
> - }
> -
> - return 0;
> + return NULL_TREE;
> }
>
> -/* Return nonzero if IDENT is a valid name for attribute ATTR,
> - or zero if not.
> +/* A variant of lookup_attribute() that can be used with an identifier
> + as the first argument, and where the identifier can be either
> + 'text' or '__text__'.
>
> - We try both `text' and `__text__', ATTR may be either one. */
> -
> -int
> -is_attribute_p (const char *attr, const_tree ident)
> + Given an attribute ATTR_IDENTIFIER, and a list of attributes LIST,
> + return a pointer to the attribute's list element if the attribute
> + is part of the list, or NULL_TREE if not found. If the attribute
> + appears more than once, this only returns the first occurrence; the
> + TREE_CHAIN of the return value should be passed back in if further
> + occurrences are wanted. ATTR_IDENTIFIER must be an identifier but
> + can be in the form 'text' or '__text__'. */
> +static tree
> +lookup_ident_attribute (tree attr_identifier, tree list)
> {
> - return is_attribute_with_length_p (attr, strlen (attr), ident);
> -}
> + gcc_checking_assert (TREE_CODE (attr_identifier) == IDENTIFIER_NODE);
>
> -/* Given an attribute name and a list of attributes, return a pointer to the
> - attribute's list element if the attribute is part of the list, or
> NULL_TREE
> - if not found. If the attribute appears more than once, this only
> - returns the first occurrence; the TREE_CHAIN of the return value should
> - be passed back in if further occurrences are wanted. */
> -
> -tree
> -lookup_attribute (const char *attr_name, tree list)
> -{
> - tree l;
> - size_t attr_len = strlen (attr_name);
> -
> - for (l = list; l; l = TREE_CHAIN (l))
> + while (list)
> {
> - gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
> - if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
> - return l;
> - }
> - return NULL_TREE;
> -}
> + gcc_checking_assert (TREE_CODE (TREE_PURPOSE (list)) ==
> IDENTIFIER_NODE);
>
> -/* Remove any instances of attribute ATTR_NAME in LIST and return the
> - modified list. */
> + /* Identifiers can be compared directly for equality. */
> + if (attr_identifier == TREE_PURPOSE (list))
> + break;
>
> -tree
> -remove_attribute (const char *attr_name, tree list)
> -{
> - tree *p;
> - size_t attr_len = strlen (attr_name);
> + /* If they are not equal, they may still be one in the form
> + 'text' while the other one is in the form '__text__'. */
> + {
> + size_t attr_len = IDENTIFIER_LENGTH (attr_identifier);
> + size_t ident_len = IDENTIFIER_LENGTH (TREE_PURPOSE (list));
>
> - for (p = &list; *p; )
> - {
> - tree l = *p;
> - gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
> - if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
> - *p = TREE_CHAIN (l);
> - else
> - p = &TREE_CHAIN (l);
> + if (ident_len == attr_len + 4)
> + {
> + const char *p = IDENTIFIER_POINTER (TREE_PURPOSE (list));
> + const char *q = IDENTIFIER_POINTER (attr_identifier);
> + if (p[0] == '_' && p[1] == '_'
> + && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
> + && strncmp (q, p + 2, attr_len) == 0)
> + break;
> + }
> + else if (ident_len + 4 == attr_len)
> + {
> + const char *p = IDENTIFIER_POINTER (TREE_PURPOSE (list));
> + const char *q = IDENTIFIER_POINTER (attr_identifier);
> + if (q[0] == '_' && q[1] == '_'
> + && q[attr_len - 2] == '_' && q[attr_len - 1] == '_'
> + && strncmp (q + 2, p, ident_len) == 0)
> + break;
> + }
> + }
> + list = TREE_CHAIN (list);
> }
>
> return list;
> @@ -5363,11 +5342,9 @@ merge_attributes (tree a1, tree a2)
> for (; a2 != 0; a2 = TREE_CHAIN (a2))
> {
> tree a;
> - for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE
> (a2)),
> - attributes);
> + for (a = lookup_ident_attribute (TREE_PURPOSE (a2), attributes);
> a != NULL_TREE && !attribute_value_equal (a, a2);
> - a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE
> (a2)),
> - TREE_CHAIN (a)))
> + a = lookup_ident_attribute (TREE_PURPOSE (a2), TREE_CHAIN
> (a)))
> ;
> if (a == NULL_TREE)
> {
> @@ -5468,13 +5445,11 @@ merge_dllimport_decl_attributes (tree old, tree ne
> if (delete_dllimport_p)
> {
> tree prev, t;
> - const size_t attr_len = strlen ("dllimport");
>
> /* Scan the list for dllimport and delete it. */
> for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
> {
> - if (is_attribute_with_length_p ("dllimport", attr_len,
> - TREE_PURPOSE (t)))
> + if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
> {
> if (prev == NULL_TREE)
> a = TREE_CHAIN (a);
> @@ -6271,6 +6246,9 @@ attribute_hash_list (const_tree list, hashval_t ha
> int
> attribute_list_equal (const_tree l1, const_tree l2)
> {
> + if (l1 == l2)
> + return 1;
> +
> return attribute_list_contained (l1, l2)
> && attribute_list_contained (l2, l1);
> }
> @@ -6309,11 +6287,9 @@ attribute_list_contained (const_tree l1, const_tre
> /* This CONST_CAST is okay because lookup_attribute does not
> modify its argument and the return value is assigned to a
> const_tree. */
> - for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
> - CONST_CAST_TREE(l1));
> + for (attr = lookup_ident_attribute (TREE_PURPOSE (t2),
> CONST_CAST_TREE(l1));
> attr != NULL_TREE && !attribute_value_equal (t2, attr);
> - attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
> - TREE_CHAIN (attr)))
> + attr = lookup_ident_attribute (TREE_PURPOSE (t2), TREE_CHAIN
> (attr)))
> ;
>
> if (attr == NULL_TREE)
> Index: tree.h
> ===================================================================
> --- tree.h (revision 173917)
> +++ tree.h (working copy)
> @@ -4485,18 +4485,79 @@ enum attribute_flags
> extern tree merge_decl_attributes (tree, tree);
> extern tree merge_type_attributes (tree, tree);
>
> -/* Given a tree node and a string, return nonzero if the tree node is
> - a valid attribute name for the string. */
> +/* Given an attribute name ATTR_NAME and a list of attributes LIST,
> + return a pointer to the attribute's list element if the attribute
> + is part of the list, or NULL_TREE if not found. If the attribute
> + appears more than once, this only returns the first occurrence; the
> + TREE_CHAIN of the return value should be passed back in if further
> + occurrences are wanted. ATTR_NAME must be in the form 'text' (not
> + '__text__'). */
>
> -extern int is_attribute_p (const char *, const_tree);
> +static inline tree
> +lookup_attribute (const char *attr_name, tree list)
> +{
> + size_t attr_len = strlen (attr_name);
> + gcc_checking_assert (attr_name[0] != '_');
>
> -/* Given an attribute name and a list of attributes, return the list element
> - of the attribute or NULL_TREE if not found. */
> + while (list)
> + {
> + size_t ident_len = IDENTIFIER_LENGTH (TREE_PURPOSE (list));
>
> -extern tree lookup_attribute (const char *, tree);
> + if (ident_len == attr_len)
> + {
> + if (strcmp (attr_name, IDENTIFIER_POINTER (TREE_PURPOSE (list))) ==
> 0)
> + break;
> + }
> + /* TODO: If we made sure that attributes were stored in the
> + canonical form without '__...__' (ie, as in 'text' as opposed
> + to '__text__') then we could avoid the following case. */
> + else if (ident_len == attr_len + 4)
> + {
> + const char *p = IDENTIFIER_POINTER (TREE_PURPOSE (list));
> + if (p[0] == '_' && p[1] == '_'
> + && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
> + && strncmp (attr_name, p + 2, attr_len) == 0)
> + break;
> + }
> + list = TREE_CHAIN (list);
> + }
>
> + return list;
> +}
> +
> +/* Given an identifier node IDENT and a string ATTR_NAME, return true
> + if the identifier node is a valid attribute name for the string.
> + ATTR_NAME must be in the form 'text' (not '__text__'). IDENT could
> + be the identifier for 'text' or for '__text__'. */
> +static inline bool
> +is_attribute_p (const char *attr_name, const_tree ident)
> +{
> + size_t attr_len = strlen (attr_name);
> + size_t ident_len = IDENTIFIER_LENGTH (ident);
> + gcc_checking_assert (attr_name[0] != '_');
> +
> + if (ident_len == attr_len)
> + {
> + if (strcmp (attr_name, IDENTIFIER_POINTER (ident)) == 0)
> + return true;
> + }
> + else if (ident_len == attr_len + 4)
> + {
> + /* There is the possibility that ATTR is 'text' and IDENT is
> + '__text__'. */
> + const char *p = IDENTIFIER_POINTER (ident);
> + if (p[0] == '_' && p[1] == '_'
> + && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
> + && strncmp (attr_name, p + 2, attr_len) == 0)
> + return true;
> + }
> +
> + return false;
> +}
> +
> /* Remove any instances of attribute ATTR_NAME in LIST and return the
> - modified list. */
> + modified list. ATTR_NAME must be in the form 'text' (not
> + '__text__'). */
>
> extern tree remove_attribute (const char *, tree);
>
>
>
>
>
>
>
>
