From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x22e.google.com (mail-lj1-x22e.google.com [IPv6:2a00:1450:4864:20::22e]) by sourceware.org (Postfix) with ESMTPS id B27813858D28 for ; Wed, 3 May 2023 10:22:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B27813858D28 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lj1-x22e.google.com with SMTP id 38308e7fff4ca-2ac762d3bb4so3348061fa.3 for ; Wed, 03 May 2023 03:22:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1683109350; x=1685701350; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=4yRYI7ef/r9C85JqUN/AlhYvI+W6UcG/lQNx0FmyoUg=; b=U7WA2hFUHGqfH3MsSrePZSFQgBQB+Xz+YTsELczF/SJWh8D17SdCKhNzGFDEzscSsD FXReVqksT2WiCi6G8cDr7+/w9hrIDbbjwmrO/Lom+HdXteefkTZIhHBD3X3LGgm+EM9S TxXZiK7Sd+8OkrvrDuDYzAYy2N0WzOzeBNe3vxfpW1kI594AenNkiXFNJ58UFOpHmOFW AvK5Ea8zy3tOuu0i1MJlSbd//SGcHXT/Y/cWZ2wLY/Q36ZednHGxjGxWEipf8K/UQ1NH G7+UiKilRDNEcuCI3lAMYoHUX0k72H67wvcEMe9HrXDKuOHSiCQby4o4nqVV5OBAXwxJ bIHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1683109350; x=1685701350; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=4yRYI7ef/r9C85JqUN/AlhYvI+W6UcG/lQNx0FmyoUg=; b=QouiNfTjrTUoecQBgdwZPkOixxAmrZvlS7J+0kw3hu/fR3C+Xr7GJdiTiwZgXugRKT PoVISjZZG84P0Al5K7wIzn65dtnQwUIxxGlnjfaQk+kn1TBn17sr5ZqZd6pYEVuQdLjo GF8S2BjWFJiyQ4n4iyt8VAcVqfnRT8iMLIaI6/26nw48BUQBIlcBMY1eEmHpnbQku7HS RDFkh4pmiUrUIev3NTuN3qD5EOW19FPYqlcL9cWpD/zhMDo8eumN/nonS+jguh3wHD1N +3ijp51wH6iyc2p1YrC3yansYYkLNyaGvPF0LM/BQYxM5wU8pktKHPlO8uiT/cAAzppy TWRw== X-Gm-Message-State: AC+VfDx+pgPCp3EJB0XQXyMyjzHKCK5QCdApwaEnygPvXI+l/sRZM2Tf wsIei/t/9i6YrP+V+IfRR3AbjGkqtadu6j0pVkw= X-Google-Smtp-Source: ACHHUZ6NEuUrPC6uc5vna1FJBw2+64QeyemmIZcJYvuhlveJDpqGts9zrUPhUyXardLtO34qq8ZWeA0lIvDUWhMqdEg= X-Received: by 2002:ac2:4a90:0:b0:4ed:b818:48ae with SMTP id l16-20020ac24a90000000b004edb81848aemr1044101lfp.21.1683109349899; Wed, 03 May 2023 03:22:29 -0700 (PDT) MIME-Version: 1.0 References: <20230203140650.E72031346D@imap2.suse-dmz.suse.de> In-Reply-To: <20230203140650.E72031346D@imap2.suse-dmz.suse.de> From: Richard Biener Date: Wed, 3 May 2023 12:22:17 +0200 Message-ID: Subject: Re: [PATCH] Improve RTL CSE hash table hash usage To: Richard Biener Cc: gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Fri, Feb 3, 2023 at 3:07=E2=80=AFPM Richard Biener via Gcc-patches wrote: > > The RTL CSE hash table has a fixed number of buckets (32) each > with a linked list of entries with the same hash value. The > actual hash values are computed using hash_rtx which uses adds > for mixing and adds the rtx CODE as CODE << 7 (apart from some > exceptions such as MEM). The unsigned int typed hash value > is then simply truncated for the actual lookup into the fixed > size table which means that usually CODE is simply lost. > > The following improves this truncation by first mixing in more > bits using xor. It does not change the actual hash function > since that's used outside of CSE as well. > > An alternative would be to bump the fixed number of buckets, > say to 256 which would retain the LSB of CODE or to 8192 which > can capture all 6 bits required for the last CODE. > > As the comment in CSE says, there's invalidate_memory and > flush_hash_table done possibly frequently and those at least > need to walk all slots, so when the hash table is mostly empty > enlarging it will be a loss. Still there should be more > regular lookups by hash, so less collisions should pay off > as well. > > Without enlarging the table a better hash function is unlikely > going to make a big difference, simple statistics on the > number of collisions at insertion time shows a reduction of > around 10%. Bumping HASH_SHIFT by 1 improves that to 30% > at the expense of reducing the average table fill by 10% > (all of this stats from looking just at fold-const.i at -O2). > Increasing HASH_SHIFT more leaves the table even more sparse > likely showing that hash_rtx uses add for mixing which is > quite bad. Bumping HASH_SHIFT by 2 removes 90% of all > collisions. > > Experimenting with using inchash instead of adds for the > mixing does not improve things when looking at the HASH_SHIFT > bumped by 2 numbers. > > Bootstrapped and tested on x86_64-unknown-linux-gnu. > > Any opinions? I have pushed this change now after re-bootstrapping and testing on x86_64-unknown-linux-gnu. Richard. > * cse.cc (HASH): Turn into inline function and mix > in another HASH_SHIFT bits. > (SAFE_HASH): Likewise. > --- > gcc/cse.cc | 37 +++++++++++++++++++++++-------------- > 1 file changed, 23 insertions(+), 14 deletions(-) > > diff --git a/gcc/cse.cc b/gcc/cse.cc > index 37afc88b439..4777e559b86 100644 > --- a/gcc/cse.cc > +++ b/gcc/cse.cc > @@ -420,20 +420,6 @@ struct table_elt > #define HASH_SIZE (1 << HASH_SHIFT) > #define HASH_MASK (HASH_SIZE - 1) > > -/* Compute hash code of X in mode M. Special-case case where X is a pse= udo > - register (hard registers may require `do_not_record' to be set). */ > - > -#define HASH(X, M) \ > - ((REG_P (X) && REGNO (X) >=3D FIRST_PSEUDO_REGISTER \ > - ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \ > - : canon_hash (X, M)) & HASH_MASK) > - > -/* Like HASH, but without side-effects. */ > -#define SAFE_HASH(X, M) \ > - ((REG_P (X) && REGNO (X) >=3D FIRST_PSEUDO_REGISTER \ > - ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (X))) \ > - : safe_hash (X, M)) & HASH_MASK) > - > /* Determine whether register number N is considered a fixed register fo= r the > purpose of approximating register costs. > It is desirable to replace other regs with fixed regs, to reduce need= for > @@ -586,6 +572,29 @@ static machine_mode cse_cc_succs (basic_block, basic= _block, rtx, rtx, > > static const struct rtl_hooks cse_rtl_hooks =3D RTL_HOOKS_INITIALIZER; > > +/* Compute hash code of X in mode M. Special-case case where X is a pse= udo > + register (hard registers may require `do_not_record' to be set). */ > + > +static inline unsigned > +HASH (rtx x, machine_mode mode) > +{ > + unsigned h =3D (REG_P (x) && REGNO (x) >=3D FIRST_PSEUDO_REGISTER > + ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (x))= ) > + : canon_hash (x, mode)); > + return (h ^ (h >> HASH_SHIFT)) & HASH_MASK; > +} > + > +/* Like HASH, but without side-effects. */ > + > +static inline unsigned > +SAFE_HASH (rtx x, machine_mode mode) > +{ > + unsigned h =3D (REG_P (x) && REGNO (x) >=3D FIRST_PSEUDO_REGISTER > + ? (((unsigned) REG << 7) + (unsigned) REG_QTY (REGNO (x))= ) > + : safe_hash (x, mode)); > + return (h ^ (h >> HASH_SHIFT)) & HASH_MASK; > +} > + > /* Nonzero if X has the form (PLUS frame-pointer integer). */ > > static bool > -- > 2.35.3