From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x630.google.com (mail-ej1-x630.google.com [IPv6:2a00:1450:4864:20::630]) by sourceware.org (Postfix) with ESMTPS id C10A03858D20 for ; Thu, 10 Nov 2022 09:04:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C10A03858D20 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-ej1-x630.google.com with SMTP id m22so3228693eji.10 for ; Thu, 10 Nov 2022 01:04:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=Rf+CAszQIRCDc8l+GRVY/dvpR14ltz7Y9yzm8a9ghN4=; b=QI2mqK89UVGrkrOXt3gKJw+7ZZNf5SJ4E+e/I0ZP9As5p0aJY4B1gxjF3jyjQX0stS nrlgKkmDJdwGXm4oMcJeF1XK4Iw3zl7saU1sqIaEYAAFliVkFobKWq+kK+uU5r1LF66v bMJrrok1491CMRn13qtvK/b9iAH/295WwVyXRqKi/1Ckya4UtuSWqfzEjR3jjBW5Zutk NK7C8UNRdag2JxeuaYiMnfPx+GMLYqMMIdeFZo+8RElQVDXQHaRRGiujInndBTOjwoP+ 89HwXYrAsxsDc7W6BVOxabjzHOjRrDO6xC6+/W8qppqUOO58Yq38zCTo59pQrA3/s2UT Y1lg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=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=Rf+CAszQIRCDc8l+GRVY/dvpR14ltz7Y9yzm8a9ghN4=; b=K5xGXZddon334jqlC3xAcf7aiu6Uzk/EgYL5ba4kCDiWUrT31JjA1FKZsp/YO4Nwjp Jk+69+qH0LAA7f82EodVFpT1JRXA/iaGiK7jAUZ3qpuF/cUM/PZkSPquN9fUOkgZepZ9 xAG5eYQbZFkxmeFGoy2KvWT9RmblAEZwnunMnH04AmmUUw08KwEJP+AZm23Lk7j0i2+l uR7RafZzN2W33kg+csYKWi001pxOMeSg+Uxp2oSDzFeiBreYZKyUuCumD62VGrzgH+21 EqBfS36olfJlA04QRj4n0SNjWOe5UE8oXi26nhY8DxGp9jMkrc0ytU4HOEg01uXDKQW/ UpMQ== X-Gm-Message-State: ACrzQf3imnpKQbk1/PAuW4jN647NthqU9zR0jTunJI2Jl4IxJet4awBg EiTMScutTbyOmcH3wX1wIW2LZY3aKFp+xcN3jPs= X-Google-Smtp-Source: AMsMyM6ahLyGEb3zTdJ4AXZ5Ed/N7Nb5kCOajQj5eStiImZTrnHXZyEIKdGLuSIulO+sdh0qGFL1iNyKDYCrFethWCA= X-Received: by 2002:a17:907:971f:b0:7ad:e232:f115 with SMTP id jg31-20020a170907971f00b007ade232f115mr47119200ejc.754.1668071050772; Thu, 10 Nov 2022 01:04:10 -0800 (PST) MIME-Version: 1.0 References: <92ff713b-e82b-ec4a-4054-b0b7d9f7dfe8@rivosinc.com> In-Reply-To: <92ff713b-e82b-ec4a-4054-b0b7d9f7dfe8@rivosinc.com> From: Richard Biener Date: Thu, 10 Nov 2022 10:03:58 +0100 Message-ID: Subject: Re: [PATCH] match.pd: rewrite select to branchless expression To: Michael Collison Cc: gcc-patches@gcc.gnu.org, Jeff Law , "jakub@redhat.com >> Jakub Jelinek" Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-8.1 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 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 Wed, Nov 9, 2022 at 10:06 PM Michael Collison wrote: > > Richard, > > Thanks for your feedback. I want to make sure I am following what you > are recommending. Are you suggesting changing: > > (for op (bit_xor bit_ior) > (simplify > (cond (eq (bit_and @0 integer_onep@1) > integer_zerop) > @2 > (op:c @3 @2)) > (if (INTEGRAL_TYPE_P (type) > && (INTEGRAL_TYPE_P (TREE_TYPE (@0)))) > (op (bit_and (negate (convert:type (bit_and @0 @1))) @3) @2)))) > > > to > > (for op (bit_xor bit_ior) > (simplify > (cond (eq zero_one_valued_p@0 > integer_zerop) > @1 > (op:c @2 @1)) > (if (INTEGRAL_TYPE_P (type) > && (INTEGRAL_TYPE_P (TREE_TYPE (@0)))) > (op (bit_and (negate (convert:type (bit_and @0 { build_one_cst > (type); }))) @2) @1)))) in the replacement you'd simply use (op (bit_and (negate (convert:type @0)) @2) @1))) that is, convert the [0,1] valued @0 to 'type' directly. At least I can't see how that can go wrong? > > > On 11/9/22 02:41, Richard Biener wrote: > > On Tue, Nov 8, 2022 at 9:02 PM Michael Collison wrote: > >> This patches transforms (cond (and (x , 0x1) == 0), y, (z op y)) into > >> (-(and (x , 0x1)) & z ) op y, where op is a '^' or a '|'. It also > >> transforms (cond (and (x , 0x1) != 0), (z op y), y ) into (-(and (x , > >> 0x1)) & z ) op y. > >> > >> Matching this patterns allows GCC to generate branchless code for one of > >> the functions in coremark. > >> > >> Bootstrapped and tested on x86 and RISC-V. Okay? > >> > >> Michael. > >> > >> 2022-11-08 Michael Collison > >> > >> * match.pd ((cond (and (x , 0x1) == 0), y, (z op y) ) > >> -> (-(and (x , 0x1)) & z ) op y) > >> > >> 2022-11-08 Michael Collison > >> > >> * gcc.dg/tree-ssa/branchless-cond.c: New test. > >> > >> --- > >> gcc/match.pd | 22 ++++++++++++++++ > >> .../gcc.dg/tree-ssa/branchless-cond.c | 26 +++++++++++++++++++ > >> 2 files changed, 48 insertions(+) > >> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c > >> > >> diff --git a/gcc/match.pd b/gcc/match.pd > >> index 194ba8f5188..722f517ac6d 100644 > >> --- a/gcc/match.pd > >> +++ b/gcc/match.pd > >> @@ -3486,6 +3486,28 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > >> (cond (le @0 integer_zerop@1) (negate@2 @0) integer_zerop@1) > >> (max @2 @1)) > >> > >> +/* (cond (and (x , 0x1) == 0), y, (z ^ y) ) -> (-(and (x , 0x1)) & z ) > >> ^ y */ > > Please write the match as a C expression in the comment, as present > > it's a weird mix. So x & 0x1 == 0 ? y : z y -> (-(typeof(y))(x & > > 0x1) & z) y > > > >> +(for op (bit_xor bit_ior) > >> + (simplify > >> + (cond (eq (bit_and @0 integer_onep@1) > >> + integer_zerop) > >> + @2 > >> + (op:c @3 @2)) > >> + (if (INTEGRAL_TYPE_P (type) > >> + && (INTEGRAL_TYPE_P (TREE_TYPE (@0)))) > >> + (op (bit_and (negate (convert:type (bit_and @0 @1))) @3) @2)))) > > Since you are literally keeping (bit_and @0 @1) and not matching @0 with > > anything I suspect you could instead use > > > > (simplify (cond (eq zero_one_valued_p@0 integer_zerop) ... > > > > eventually extending that to cover bit_and with one. Do you need to guard > > this against 'type' being a signed/unsigned 1-bit precision integer? > > > >> + > >> +/* (cond (and (x , 0x1) != 0), (z ^ y), y ) -> (-(and (x , 0x1)) & z ) > >> ^ y */ > >> +(for op (bit_xor bit_ior) > >> + (simplify > >> + (cond (ne (bit_and @0 integer_onep@1) > >> + integer_zerop) > >> + (op:c @3 @2) > >> + @2) > >> + (if (INTEGRAL_TYPE_P (type) > >> + && (INTEGRAL_TYPE_P (TREE_TYPE (@0)))) > >> + (op (bit_and (negate (convert:type (bit_and @0 @1))) @3) @2)))) > >> + > >> /* Simplifications of shift and rotates. */ > >> > >> (for rotate (lrotate rrotate) > >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c > >> b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c > >> new file mode 100644 > >> index 00000000000..68087ae6568 > >> --- /dev/null > >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c > >> @@ -0,0 +1,26 @@ > >> +/* { dg-do compile } */ > >> +/* { dg-options "-O2 -fdump-tree-optimized" } */ > >> + > >> +int f1(unsigned int x, unsigned int y, unsigned int z) > >> +{ > >> + return ((x & 1) == 0) ? y : z ^ y; > >> +} > >> + > >> +int f2(unsigned int x, unsigned int y, unsigned int z) > >> +{ > >> + return ((x & 1) != 0) ? z ^ y : y; > >> +} > >> + > >> +int f3(unsigned int x, unsigned int y, unsigned int z) > >> +{ > >> + return ((x & 1) == 0) ? y : z | y; > >> +} > >> + > >> +int f4(unsigned int x, unsigned int y, unsigned int z) > >> +{ > >> + return ((x & 1) != 0) ? z | y : y; > >> +} > >> + > >> +/* { dg-final { scan-tree-dump-times " -" 4 "optimized" } } */ > >> +/* { dg-final { scan-tree-dump-times " & " 8 "optimized" } } */ > >> +/* { dg-final { scan-tree-dump-not "if" "optimized" } } */ > >> -- > >> 2.34.1 > >> > >> > >> > >>