Re: Patch: speed up compiler a little bit by optimizing lookup_attribute() and is_attribute_p()

[Richard Guenther <richard dot guenther at gmail dot com>]

On Wed, Jun 22, 2011 at 2:17 AM, Nicola Pero
<nicola.pero@meta-innovation.com> wrote:
> Ok, here's a revised patch (contextual diff, as requested).
>
> The inline code is now minimized to the "hot" stuff, as discussed. ?In benchmarks
> this arrangement performs a tiny bit slightly better than the previous patch, so
> that's great news. :-)
>
> Bootstrapped on GNU/Linux i686, regression tested. ?Benchmarked.
>
> OK to commit ?

Ok.

Thanks,
Richard.

> Thanks
>
> Index: attribs.c
> ===================================================================
> *** attribs.c ? (revision 175269)
> --- attribs.c ? (working copy)
> ***************
> *** 198,203 ****
> --- 198,208 ----
>
> ? ?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,284 ****
> --- 284,290 ----
> ? ?/* 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 175269)
> --- tree.c ? ? ?(working copy)
> ***************
> *** 5218,5299 ****
> ? }
> ?};
>
> ! /* Return nonzero if IDENT is a valid name for attribute ATTR,
> ! ? ?or zero if not.
> !
> ! ? ?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)
> ?{
> ! ? int ident_len;
> ! ? const char *p;
> !
> ! ? 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] == '_')
> ? ? ?{
> ! ? ? ? 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;
> ? ? ?}
> ! ? 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 nonzero if IDENT is a valid name for attribute ATTR,
> ! ? ?or zero if not.
>
> ! ? ?We try both `text' and `__text__', ATTR may be either one. ?*/
>
> ! int
> ! is_attribute_p (const char *attr, const_tree ident)
> ! {
> ! ? return is_attribute_with_length_p (attr, strlen (attr), ident);
> ?}
>
> ! /* 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))
> ? ? ?{
> ! ? ? ? 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;
> ?}
>
> ?/* Remove any instances of attribute ATTR_NAME in LIST and return the
> --- 5218,5336 ----
> ? }
> ?};
>
> ! /* The backbone of is_attribute_p(). ?ATTR_LEN is the string length of
> ! ? ?ATTR_NAME. ?Also used internally by remove_attribute(). ?*/
> ! bool
> ! private_is_attribute_p (const char *attr_name, size_t attr_len, const_tree ident)
> ?{
> ! ? size_t ident_len = IDENTIFIER_LENGTH (ident);
>
> ! ? 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;
> ?}
>
> ! /* The backbone of lookup_attribute(). ?ATTR_LEN is the string length
> ! ? ?of ATTR_NAME, and LIST is not NULL_TREE. ?*/
> ! tree
> ! private_lookup_attribute (const char *attr_name, size_t attr_len, tree list)
> ! {
> ! ? while (list)
> ! ? ? {
> ! ? ? ? size_t ident_len = IDENTIFIER_LENGTH (TREE_PURPOSE (list));
>
> ! ? ? ? 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;
> ?}
>
> ! /* 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__'.
> !
> ! ? ?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)
> ?{
> ! ? gcc_checking_assert (TREE_CODE (attr_identifier) == IDENTIFIER_NODE);
>
> ! ? while (list)
> ? ? ?{
> ! ? ? ? gcc_checking_assert (TREE_CODE (TREE_PURPOSE (list)) == IDENTIFIER_NODE);
> !
> ! ? ? ? /* Identifiers can be compared directly for equality. ?*/
> ! ? ? ? if (attr_identifier == TREE_PURPOSE (list))
> ! ? ? ? break;
> !
> ! ? ? ? /* If they are not equal, they may still be one in the form
> ! ? ? ? ?'text' while the other one is in the form '__text__'. ?TODO:
> ! ? ? ? ?If we were storing attributes in normalized 'text' form, then
> ! ? ? ? ?this could all go away and we could take full advantage of
> ! ? ? ? ?the fact that we're comparing identifiers. :-) ?*/
> ! ? ? ? {
> ! ? ? ? size_t attr_len = IDENTIFIER_LENGTH (attr_identifier);
> ! ? ? ? size_t ident_len = IDENTIFIER_LENGTH (TREE_PURPOSE (list));
> !
> ! ? ? ? 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;
> ?}
>
> ?/* Remove any instances of attribute ATTR_NAME in LIST and return the
> ***************
> *** 5305,5315 ****
> ? ?tree *p;
> ? ?size_t attr_len = strlen (attr_name);
>
> ? ?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);
> --- 5342,5355 ----
> ? ?tree *p;
> ? ?size_t attr_len = strlen (attr_name);
>
> + ? gcc_checking_assert (attr_name[0] != '_');
> +
> ? ?for (p = &list; *p; )
> ? ? ?{
> ? ? ? ?tree l = *p;
> ! ? ? ? /* TODO: If we were storing attributes in normalized form, here
> ! ? ? ? ?we could use a simple strcmp(). ?*/
> ! ? ? ? if (private_is_attribute_p (attr_name, attr_len, TREE_PURPOSE (l)))
> ? ? ? ?*p = TREE_CHAIN (l);
> ? ? ? ?else
> ? ? ? ?p = &TREE_CHAIN (l);
> ***************
> *** 5346,5356 ****
> ? ? ? ? ?for (; a2 != 0; a2 = TREE_CHAIN (a2))
> ? ? ? ? ? ?{
> ? ? ? ? ? ? ?tree a;
> ! ? ? ? ? ? ? for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
> ! ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?attributes);
> ? ? ? ? ? ? ? ? ? a != NULL_TREE && !attribute_value_equal (a, a2);
> ! ? ? ? ? ? ? ? ? ?a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
> ! ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?TREE_CHAIN (a)))
> ? ? ? ? ? ? ? ?;
> ? ? ? ? ? ? ?if (a == NULL_TREE)
> ? ? ? ? ? ? ? ?{
> --- 5386,5394 ----
> ? ? ? ? ?for (; a2 != 0; a2 = TREE_CHAIN (a2))
> ? ? ? ? ? ?{
> ? ? ? ? ? ? ?tree a;
> ! ? ? ? ? ? ? for (a = lookup_ident_attribute (TREE_PURPOSE (a2), attributes);
> ? ? ? ? ? ? ? ? ? a != NULL_TREE && !attribute_value_equal (a, a2);
> ! ? ? ? ? ? ? ? ? ?a = lookup_ident_attribute (TREE_PURPOSE (a2), TREE_CHAIN (a)))
> ? ? ? ? ? ? ? ?;
> ? ? ? ? ? ? ?if (a == NULL_TREE)
> ? ? ? ? ? ? ? ?{
> ***************
> *** 5449,5472 ****
> ? ?a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new_tree));
>
> ? ?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 (prev == NULL_TREE)
> ! ? ? ? ? ? ? ? a = TREE_CHAIN (a);
> ! ? ? ? ? ? ? else
> ! ? ? ? ? ? ? ? TREE_CHAIN (prev) = TREE_CHAIN (t);
> ! ? ? ? ? ? ? break;
> ! ? ? ? ? ? }
> ! ? ? ? }
> ! ? ? }
>
> ? ?return a;
> ?}
> --- 5487,5493 ----
> ? ?a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new_tree));
>
> ? ?if (delete_dllimport_p)
> ! ? ? a = remove_attribute ("dllimport", a);
>
> ? ?return a;
> ?}
> ***************
> *** 6254,6259 ****
> --- 6275,6283 ----
> ?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);
> ?}
> ***************
> *** 6292,6302 ****
> ? ? ? ?/* 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));
> ? ? ? ? ? attr != NULL_TREE && !attribute_value_equal (t2, attr);
> ! ? ? ? ? ?attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
> ! ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? TREE_CHAIN (attr)))
> ? ? ? ?;
>
> ? ? ? ?if (attr == NULL_TREE)
> --- 6316,6324 ----
> ? ? ? ?/* 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_ident_attribute (TREE_PURPOSE (t2), CONST_CAST_TREE(l1));
> ? ? ? ? ? attr != NULL_TREE && !attribute_value_equal (t2, attr);
> ! ? ? ? ? ?attr = lookup_ident_attribute (TREE_PURPOSE (t2), TREE_CHAIN (attr)))
> ? ? ? ?;
>
> ? ? ? ?if (attr == NULL_TREE)
> Index: tree.h
> ===================================================================
> *** tree.h ? ? ?(revision 175269)
> --- tree.h ? ? ?(working copy)
> ***************
> *** 4498,4515 ****
> ?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. ?*/
>
> ! extern int is_attribute_p (const char *, const_tree);
> !
> ! /* Given an attribute name and a list of attributes, return the list element
> ! ? ?of the attribute or NULL_TREE if not found. ?*/
>
> ! extern tree lookup_attribute (const char *, tree);
>
> ?/* Remove any instances of attribute ATTR_NAME in LIST and return the
> ! ? ?modified list. ?*/
>
> ?extern tree remove_attribute (const char *, tree);
>
> --- 4498,4550 ----
> ?extern tree merge_decl_attributes (tree, tree);
> ?extern tree merge_type_attributes (tree, tree);
>
> ! /* This function is a private implementation detail of lookup_attribute()
> ! ? ?and you should never call it directly. ?*/
> ! extern tree private_lookup_attribute (const char *, size_t, tree);
> !
> ! /* 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__'). ?*/
>
> ! static inline tree
> ! lookup_attribute (const char *attr_name, tree list)
> ! {
> ! ? gcc_checking_assert (attr_name[0] != '_');
> ! ? /* In most cases, list is NULL_TREE. ?*/
> ! ? if (list == NULL_TREE)
> ! ? ? return NULL_TREE;
> ! ? else
> ! ? ? /* Do the strlen() before calling the out-of-line implementation.
> ! ? ? ? ?In most cases attr_name is a string constant, and the compiler
> ! ? ? ? ?will optimize the strlen() away. ?*/
> ! ? ? return private_lookup_attribute (attr_name, strlen (attr_name), list);
> ! }
>
> ! /* This function is a private implementation detail of
> ! ? ?is_attribute_p() and you should never call it directly. ?*/
> ! extern bool private_is_attribute_p (const char *, size_t, const_tree);
> !
> ! /* 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)
> ! {
> ! ? gcc_checking_assert (attr_name[0] != '_');
> ! ? /* Do the strlen() before calling the out-of-line implementation.
> ! ? ? ?In most cases attr_name is a string constant, and the compiler
> ! ? ? ?will optimize the strlen() away. ?*/
> ! ? return private_is_attribute_p (attr_name, strlen (attr_name), ident);
> ! }
>
> ?/* Remove any instances of attribute ATTR_NAME in LIST and return the
> ! ? ?modified list. ?ATTR_NAME must be in the form 'text' (not
> ! ? ?'__text__'). ?*/
>
> ?extern tree remove_attribute (const char *, tree);
>
> Index: ChangeLog
> ===================================================================
> *** ChangeLog ? (revision 175269)
> --- ChangeLog ? (working copy)
> ***************
> *** 1,3 ****
> --- 1,32 ----
> + 2011-06-21 ?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.
> + ? ? ? (private_is_attribute_p): New.
> + ? ? ? (private_lookup_attribute): New.
> + ? ? ? (lookup_attribute): Removed.
> + ? ? ? (lookup_ident_attribute): New.
> + ? ? ? (remove_attribute): Require the first argument to be in the form
> + ? ? ? 'text', not '__text__'. ?Updated asserts.
> + ? ? ? (merge_attributes): Use lookup_ident_attributes instead of
> + ? ? ? lookup_attribute.
> + ? ? ? (merge_dllimport_decl_attributes): Use remove_attribute.
> + ? ? ? (attribute_list_contained): Likewise.
> + ? ? ? (attribute_list_equal): Immediately return 1 if the arguments are
> + ? ? ? identical pointers.
> + ? ? ? * tree.h (is_attribute_p): Made inline. ?Return a 'bool', not an
> + ? ? ? 'int'. ?Require the first argument to be in the form 'text', not
> + ? ? ? '__text__'. ?Require the second argument to be an identifier.
> + ? ? ? (lookup_attribute): Made inline. ?Require the first argument to be
> + ? ? ? in the form 'text', not '__text__'.
> + ? ? ? (private_is_attribute_p, private_lookup_attribute): New.
> + ? ? ? Updated comments.
> +
> ?2011-06-21 ?Georg-Johann Lay ?<avr@gjlay.de>
>
> ? ? ? ?PR target/33049
>
>
>
>
>
>