From patchwork Mon Jun 20 22:37:17 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicola Pero X-Patchwork-Id: 101221 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 7D6B0B6F84 for ; Tue, 21 Jun 2011 08:37:43 +1000 (EST) Received: (qmail 32234 invoked by alias); 20 Jun 2011 22:37:41 -0000 Received: (qmail 32223 invoked by uid 22791); 20 Jun 2011 22:37:39 -0000 X-SWARE-Spam-Status: No, hits=-1.4 required=5.0 tests=AWL, BAYES_00, SARE_SUB_ENC_UTF8, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (140.186.70.10) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 20 Jun 2011 22:37:23 +0000 Received: from eggs.gnu.org ([140.186.70.92]:48334) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1QYn5u-0003FT-7m for gcc-patches@gnu.org; Mon, 20 Jun 2011 18:37:22 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QYn5r-0006kX-BC for gcc-patches@gnu.org; Mon, 20 Jun 2011 18:37:22 -0400 Received: from smtp131.iad.emailsrvr.com ([207.97.245.131]:43230) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QYn5q-0006kQ-Qe for gcc-patches@gnu.org; Mon, 20 Jun 2011 18:37:19 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp53.relay.iad1a.emailsrvr.com (SMTP Server) with ESMTP id D3C47587F6 for ; Mon, 20 Jun 2011 18:37:17 -0400 (EDT) Received: from dynamic4.wm-web.iad.mlsrvr.com (dynamic4.wm-web.iad1a.rsapps.net [192.168.2.153]) by smtp53.relay.iad1a.emailsrvr.com (SMTP Server) with ESMTP id BE41A587F7 for ; Mon, 20 Jun 2011 18:37:17 -0400 (EDT) Received: from meta-innovation.com (localhost [127.0.0.1]) by dynamic4.wm-web.iad.mlsrvr.com (Postfix) with ESMTP id 9E9111D4A325 for ; Mon, 20 Jun 2011 18:37:17 -0400 (EDT) Received: by www2.webmail.us (Authenticated sender: nicola.pero@meta-innovation.com, from: nicola.pero@meta-innovation.com) with HTTP; Tue, 21 Jun 2011 00:37:17 +0200 (CEST) Date: Tue, 21 Jun 2011 00:37:17 +0200 (CEST) Subject: =?utf-8?Q?Patch=3A_speed_up_compiler_a_little_bit_by_optimizing_lookup=5F?= =?utf-8?Q?attribute=28=29_and_is=5Fattribute=5Fp=28=29?= From: "Nicola Pero" To: "gcc-patches@gnu.org" MIME-Version: 1.0 X-Type: plain Message-ID: <1308609437.64587569@www2.webmail.us> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 207.97.245.131 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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. Index: ChangeLog =================================================================== --- ChangeLog (revision 173917) +++ ChangeLog (working copy) @@ -1,3 +1,24 @@ +2011-06-19 Nicola Pero + + * 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 * 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);