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

["Nicola Pero" <nicola dot pero at meta-innovation dot com>]

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 ?

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