| Message ID | 1308609437.64587569@www2.webmail.us |
|---|---|
| State | New |
| Headers | show |
On Tue, Jun 21, 2011 at 12:37 AM, Nicola Pero <nicola.pero@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.pero@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 <joseph@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); > > > > > > > >
>> 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. Can you explain why ? You never do in your response :-) I'm guessing it's because you think the inline functions are too big and that's counter-productive ? > 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. Ok ... so is this what you'd like - the common, hot case in the inline function, and the less common, cold case in the out-of-line one ? :-) That makes sense - I'll try that out tonight (it takes a few hours to run all the benchmarks). ;-) > 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). Sure ... one step at a time. :-) Thanks
On Tue, Jun 21, 2011 at 12:17 PM, Nicola Pero <nicola.pero@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. > > Can you explain why ? You never do in your response :-) > > I'm guessing it's because you think the inline functions are too big and that's > counter-productive ? Yes. >> 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. > > Ok ... so is this what you'd like - the common, hot case in the inline function, > and the less common, cold case in the out-of-line one ? :-) Right. > That makes sense - I'll try that out tonight (it takes a few hours to run all > the benchmarks). ;-) Thanks. > >> 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). > > Sure ... one step at a time. :-) Of course ;) Richard. > Thanks > >
Index: ChangeLog =================================================================== --- ChangeLog (revision 173917) +++ ChangeLog (working copy) @@ -1,3 +1,24 @@ +2011-06-19 Nicola Pero <nicola.pero@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 <joseph@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);
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. 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. * a tiny tweak in tree.c to speed up attribute_list_equal() which is almost always called with two identical pointers. * 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. 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. * 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 "_". * 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). 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.