From patchwork Fri Jul 19 14:23:51 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 94220 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1BFB8386181A for ; Fri, 19 Jul 2024 14:36:45 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2a07:de40:b251:101:10:150:64:1]) by sourceware.org (Postfix) with ESMTPS id 1CB44384F032 for ; Fri, 19 Jul 2024 14:23:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1CB44384F032 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 1CB44384F032 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:1 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1721399036; cv=none; b=hOwP9Dc1jhXm6TCXG7pP9dASY0KtCTtszYNsWaedJJEPrJBdveHb8L4sG2Os8wkiBKdzFiYvKkyZ7b9sVnpUC+p9xvjYauMiMg1mTewL0k7yqClCATRO2VXyL7dG8QcKuUmbDxGCoMvjxrnzRP7ZwPC5UorLVVL9B2V7+ayn+fQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1721399036; c=relaxed/simple; bh=eBMSSt6IESIcEjdRXj4efkBF5sNkZkuJjoQR4HGY8JI=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version:Message-Id; b=K2A+Iy1NOr6ZXMGRg58+HIajVqvdeWYCs5rDgdzRYfxa06ku2Ba3C6al3h0wKkDU+1/M85DZhBeAYn5+AjVIyAc6PstI0pmO1FDn/NoLmHO0UJaC1xxuzZ6wAJgYq+IZqQpsBvlRPxJVQWvl52vc0uNOWBUPTSZDVGVGIF8N2TA= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap1.dmz-prg2.suse.org (unknown [10.150.64.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id CD53B21ABA; Fri, 19 Jul 2024 14:23:51 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1721399032; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=LCjCmV7ZsQ5OkKt1lBAilw9JI0wx/ABG3+vgL6Sqa7E=; b=kIbRHouEgW40D98gnjy2jnSp1apr03WPgwWH2L2JADkvWlG0jAdaVMcTmmC8oibFwbvucq 7H+69JZcb43nYnMODcKokWHDqjOAfmvszOOkQ/Yrnx1ijg7rg8p/3U0FKI9L9hKs4dYc1n mqAMIOAbMxnRR1I15Kozb8TByvHjOpg= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1721399032; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=LCjCmV7ZsQ5OkKt1lBAilw9JI0wx/ABG3+vgL6Sqa7E=; b=vse7RGRqA4DDo65i1OAMQ8rhPpYt/E2b6853OSu4w8lN2RRrTAThox3L68PVje+uRJjJwW I0qAqibdelSsaIDw== Authentication-Results: smtp-out1.suse.de; none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1721399031; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=LCjCmV7ZsQ5OkKt1lBAilw9JI0wx/ABG3+vgL6Sqa7E=; b=wtKbXh5w87gkVxWF7GSxlMaIKMP0bJKuX0jhnVdM/HuPT9IvliIYeS5m1MsSKYa+XOy7kX fttv/MpVpR01ZtB8r0TxZkhjWgjQfbuNSZSDzTt8hkZeb2Tk8/PccmGwGx4T/N4MwvKLul dJiXa8vL2n8VklXow5mGS7JkpdQ7DxI= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1721399031; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=LCjCmV7ZsQ5OkKt1lBAilw9JI0wx/ABG3+vgL6Sqa7E=; b=9imDZvmxJ5oJ9CsRf2t05Z2FF/dVzSKzj3M+0OhZXMINcZkCPHJet49i4XkElIJswMfX7T Oma6Y3nc7+7fV/Cw== Received: from imap1.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap1.dmz-prg2.suse.org (Postfix) with ESMTPS id A93A4132CB; Fri, 19 Jul 2024 14:23:51 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap1.dmz-prg2.suse.org with ESMTPSA id ky8jJ/d2mmZcIQAAD6G6ig (envelope-from ); Fri, 19 Jul 2024 14:23:51 +0000 Date: Fri, 19 Jul 2024 16:23:51 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: jeffreyalaw@gmail.com Subject: [PATCH] rtl-optimization/116002 - cselib hash is bad MIME-Version: 1.0 Message-Id: <20240719142351.A93A4132CB@imap1.dmz-prg2.suse.org> X-Spamd-Result: default: False [-4.30 / 50.00]; BAYES_HAM(-3.00)[100.00%]; NEURAL_HAM_LONG(-1.00)[-1.000]; NEURAL_HAM_SHORT(-0.20)[-0.997]; MIME_GOOD(-0.10)[text/plain]; RCVD_TLS_ALL(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; ARC_NA(0.00)[]; RCPT_COUNT_TWO(0.00)[2]; MISSING_XM_UA(0.00)[]; FREEMAIL_ENVRCPT(0.00)[gmail.com]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FUZZY_BLOCKED(0.00)[rspamd.com]; FROM_HAS_DN(0.00)[]; FREEMAIL_CC(0.00)[gmail.com]; MIME_TRACE(0.00)[0:+]; FROM_EQ_ENVFROM(0.00)[]; TO_DN_NONE(0.00)[]; RCVD_COUNT_TWO(0.00)[2]; TO_MATCH_ENVRCPT_ALL(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[imap1.dmz-prg2.suse.org:helo] X-Spam-Score: -4.30 X-Spam-Level: X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~patchwork=sourceware.org@gcc.gnu.org The following addresses the bad hash function of cselib which uses integer plus for merging. This causes a huge number of collisions for the testcase in the PR and thus very large compile-time. The following rewrites it to use inchash, eliding duplicate mixing of RTX code and mode in some cases and more consistently avoiding a return value of zero as well as treating zero as fatal. For cselib_hash_plus_const_int this removes the apparent attempt of making sure to hash the same as a PLUS as cselib_hash_rtx makes sure to dispatch to cselib_hash_plus_const_int consistently. This reduces compile-time for the testcase in the PR from unknown to 22s and for a reduced testcase from 73s to 9s. There's another pending patchset to improve the speed of inchash mixing, but it's not in the profile for this testcase (PTA pops up now). The generated code is equal. Bootstrap and regtest running on x86_64-unknown-linux-gnu. Any objections? PR rtl-optimization/116002 * cselib.cc (cselib_hash_rtx): Use inchash to get proper mixing. Consistently avoid a zero return value when hashing successfully. Consistently treat a zero hash value from recursing as fatal. (cselib_hash_plus_const_int): Likewise. --- gcc/cselib.cc | 195 ++++++++++++++++++++++++++------------------------ 1 file changed, 101 insertions(+), 94 deletions(-) diff --git a/gcc/cselib.cc b/gcc/cselib.cc index cbaab7d515c..6b4cdf266f8 100644 --- a/gcc/cselib.cc +++ b/gcc/cselib.cc @@ -1266,14 +1266,13 @@ cselib_hash_plus_const_int (rtx x, HOST_WIDE_INT c, int create, if (c == 0) return e->hash; - unsigned hash = (unsigned) PLUS + (unsigned) GET_MODE (x); - hash += e->hash; - unsigned int tem_hash = (unsigned) CONST_INT + (unsigned) VOIDmode; - tem_hash += ((unsigned) CONST_INT << 7) + (unsigned HOST_WIDE_INT) c; - if (tem_hash == 0) - tem_hash = (unsigned int) CONST_INT; - hash += tem_hash; - return hash ? hash : 1 + (unsigned int) PLUS; + inchash::hash hash; + hash.add_int (PLUS); + hash.add_int (GET_MODE (x)); + hash.merge_hash (e->hash); + hash.add_hwi (c); + + return hash.end () ? hash.end () : 1 + (unsigned int) PLUS; } /* Hash an rtx. Return 0 if we couldn't hash the rtx. @@ -1306,10 +1305,11 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) int i, j; enum rtx_code code; const char *fmt; - unsigned int hash = 0; + inchash::hash hash; code = GET_CODE (x); - hash += (unsigned) code + (unsigned) GET_MODE (x); + hash.add_int (code); + hash.add_int (GET_MODE (x)); switch (code) { @@ -1326,19 +1326,16 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) return e->hash; case DEBUG_EXPR: - hash += ((unsigned) DEBUG_EXPR << 7) - + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)); - return hash ? hash : (unsigned int) DEBUG_EXPR; + hash.add_int (DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x))); + return hash.end () ? hash.end() : (unsigned int) DEBUG_EXPR; case DEBUG_IMPLICIT_PTR: - hash += ((unsigned) DEBUG_IMPLICIT_PTR << 7) - + DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x)); - return hash ? hash : (unsigned int) DEBUG_IMPLICIT_PTR; + hash.add_int (DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x))); + return hash.end () ? hash.end () : (unsigned int) DEBUG_IMPLICIT_PTR; case DEBUG_PARAMETER_REF: - hash += ((unsigned) DEBUG_PARAMETER_REF << 7) - + DECL_UID (DEBUG_PARAMETER_REF_DECL (x)); - return hash ? hash : (unsigned int) DEBUG_PARAMETER_REF; + hash.add_int (DECL_UID (DEBUG_PARAMETER_REF_DECL (x))); + return hash.end () ? hash.end () : (unsigned int) DEBUG_PARAMETER_REF; case ENTRY_VALUE: /* ENTRY_VALUEs are function invariant, thus try to avoid @@ -1347,51 +1344,49 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) ENTRY_VALUE hash would depend on the current value in some register or memory. */ if (REG_P (ENTRY_VALUE_EXP (x))) - hash += (unsigned int) REG - + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x)) - + (unsigned int) REGNO (ENTRY_VALUE_EXP (x)); + hash.add_int ((unsigned int) REG + + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x)) + + (unsigned int) REGNO (ENTRY_VALUE_EXP (x))); else if (MEM_P (ENTRY_VALUE_EXP (x)) && REG_P (XEXP (ENTRY_VALUE_EXP (x), 0))) - hash += (unsigned int) MEM - + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0)) - + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0)); + hash.add_int ((unsigned int) MEM + + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0)) + + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0))); else - hash += cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode); - return hash ? hash : (unsigned int) ENTRY_VALUE; + hash.add_int (cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode)); + return hash.end () ? hash.end () : (unsigned int) ENTRY_VALUE; case CONST_INT: - hash += ((unsigned) CONST_INT << 7) + UINTVAL (x); - return hash ? hash : (unsigned int) CONST_INT; + hash.add_hwi (UINTVAL (x)); + return hash.end () ? hash.end () : (unsigned int) CONST_INT; case CONST_WIDE_INT: for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++) - hash += CONST_WIDE_INT_ELT (x, i); - return hash; + hash.add_hwi (CONST_WIDE_INT_ELT (x, i)); + return hash.end () ? hash.end () : (unsigned int) CONST_WIDE_INT; case CONST_POLY_INT: { - inchash::hash h; - h.add_int (hash); for (unsigned int i = 0; i < NUM_POLY_INT_COEFFS; ++i) - h.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]); - return h.end (); + hash.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]); + return hash.end () ? hash.end () : (unsigned int) CONST_POLY_INT; } case CONST_DOUBLE: /* This is like the general case, except that it only counts the integers representing the constant. */ - hash += (unsigned) code + (unsigned) GET_MODE (x); if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode) - hash += ((unsigned) CONST_DOUBLE_LOW (x) - + (unsigned) CONST_DOUBLE_HIGH (x)); + { + hash.add_hwi (CONST_DOUBLE_LOW (x)); + hash.add_hwi (CONST_DOUBLE_HIGH (x)); + } else - hash += real_hash (CONST_DOUBLE_REAL_VALUE (x)); - return hash ? hash : (unsigned int) CONST_DOUBLE; + hash.merge_hash (real_hash (CONST_DOUBLE_REAL_VALUE (x))); + return hash.end () ? hash.end () : (unsigned int) CONST_DOUBLE; case CONST_FIXED: - hash += (unsigned int) code + (unsigned int) GET_MODE (x); - hash += fixed_hash (CONST_FIXED_VALUE (x)); - return hash ? hash : (unsigned int) CONST_FIXED; + hash.merge_hash (fixed_hash (CONST_FIXED_VALUE (x))); + return hash.end () ? hash.end () : (unsigned int) CONST_FIXED; case CONST_VECTOR: { @@ -1403,19 +1398,18 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) for (i = 0; i < units; ++i) { elt = CONST_VECTOR_ENCODED_ELT (x, i); - hash += cselib_hash_rtx (elt, 0, memmode); + hash.merge_hash (cselib_hash_rtx (elt, 0, memmode)); } - return hash; + return hash.end () ? hash.end () : (unsigned int) CONST_VECTOR; } /* Assume there is only one rtx object for any given label. */ case LABEL_REF: /* We don't hash on the address of the CODE_LABEL to avoid bootstrap differences and differences between each stage's debugging dumps. */ - hash += (((unsigned int) LABEL_REF << 7) - + CODE_LABEL_NUMBER (label_ref_label (x))); - return hash ? hash : (unsigned int) LABEL_REF; + hash.add_int (CODE_LABEL_NUMBER (label_ref_label (x))); + return hash.end () ? hash.end () : (unsigned int) LABEL_REF; case SYMBOL_REF: { @@ -1424,51 +1418,69 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) different orders and thus different registers to be used in the final assembler. This also avoids differences in the dump files between various stages. */ - unsigned int h = 0; - const unsigned char *p = (const unsigned char *) XSTR (x, 0); + const char *p = (const char *) XSTR (x, 0); - while (*p) - h += (h << 7) + *p++; /* ??? revisit */ + if (*p) + hash.add (p, strlen (p)); - hash += ((unsigned int) SYMBOL_REF << 7) + h; - return hash ? hash : (unsigned int) SYMBOL_REF; + return hash.end () ? hash.end () : (unsigned int) SYMBOL_REF; } case PRE_DEC: case PRE_INC: - /* We can't compute these without knowing the MEM mode. */ - gcc_assert (memmode != VOIDmode); - offset = GET_MODE_SIZE (memmode); - if (code == PRE_DEC) - offset = -offset; - /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes - like (mem:MEMMODE (plus (reg) (const_int I))). */ - if (GET_MODE (x) == Pmode - && (REG_P (XEXP (x, 0)) - || MEM_P (XEXP (x, 0)) - || GET_CODE (XEXP (x, 0)) == VALUE)) - { - HOST_WIDE_INT c; - if (offset.is_constant (&c)) - return cselib_hash_plus_const_int (XEXP (x, 0), - trunc_int_for_mode (c, Pmode), - create, memmode); - } - hash = ((unsigned) PLUS + (unsigned) GET_MODE (x) - + cselib_hash_rtx (XEXP (x, 0), create, memmode) - + cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)), - create, memmode)); - return hash ? hash : 1 + (unsigned) PLUS; + { + /* We can't compute these without knowing the MEM mode. */ + gcc_assert (memmode != VOIDmode); + offset = GET_MODE_SIZE (memmode); + if (code == PRE_DEC) + offset = -offset; + /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes + like (mem:MEMMODE (plus (reg) (const_int I))). */ + if (GET_MODE (x) == Pmode + && (REG_P (XEXP (x, 0)) + || MEM_P (XEXP (x, 0)) + || GET_CODE (XEXP (x, 0)) == VALUE)) + { + HOST_WIDE_INT c; + if (offset.is_constant (&c)) + return cselib_hash_plus_const_int (XEXP (x, 0), + trunc_int_for_mode (c, Pmode), + create, memmode); + } + + unsigned tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode); + if (tem_hash == 0) + return 0; + hash.merge_hash (tem_hash); + tem_hash = cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)), + create, memmode); + if (tem_hash == 0) + return 0; + hash.merge_hash (tem_hash); + return hash.end () ? hash.end () : 1 + (unsigned) PLUS; + } case PRE_MODIFY: - gcc_assert (memmode != VOIDmode); - return cselib_hash_rtx (XEXP (x, 1), create, memmode); + { + gcc_assert (memmode != VOIDmode); + unsigned tem_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode); + if (tem_hash == 0) + return 0; + hash.merge_hash (tem_hash); + return hash.end () ? hash.end () : 1 + (unsigned) PRE_MODIFY; + } case POST_DEC: case POST_INC: case POST_MODIFY: - gcc_assert (memmode != VOIDmode); - return cselib_hash_rtx (XEXP (x, 0), create, memmode); + { + gcc_assert (memmode != VOIDmode); + unsigned tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode); + if (tem_hash == 0) + return 0; + hash.merge_hash (tem_hash); + return hash.end () ? hash.end () : 1 + (unsigned) code; + } case PC: case CALL: @@ -1505,11 +1517,9 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) { rtx tem = XEXP (x, i); unsigned int tem_hash = cselib_hash_rtx (tem, create, memmode); - if (tem_hash == 0) return 0; - - hash += tem_hash; + hash.merge_hash (tem_hash); } break; case 'E': @@ -1517,30 +1527,27 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) { unsigned int tem_hash = cselib_hash_rtx (XVECEXP (x, i, j), create, memmode); - if (tem_hash == 0) return 0; - - hash += tem_hash; + hash.merge_hash (tem_hash); } break; case 's': { - const unsigned char *p = (const unsigned char *) XSTR (x, i); + const char *p = (const char *) XSTR (x, i); - if (p) - while (*p) - hash += *p++; + if (p && *p) + hash.add (p, strlen (p)); break; } case 'i': - hash += XINT (x, i); + hash.add_hwi (XINT (x, i)); break; case 'p': - hash += constant_lower_bound (SUBREG_BYTE (x)); + hash.add_int (constant_lower_bound (SUBREG_BYTE (x))); break; case '0': @@ -1553,7 +1560,7 @@ cselib_hash_rtx (rtx x, int create, machine_mode memmode) } } - return hash ? hash : 1 + (unsigned int) GET_CODE (x); + return hash.end () ? hash.end () : 1 + (unsigned int) GET_CODE (x); } /* Create a new value structure for VALUE and initialize it. The mode of the