From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x62a.google.com (mail-ej1-x62a.google.com [IPv6:2a00:1450:4864:20::62a]) by sourceware.org (Postfix) with ESMTPS id EFBB93858D32 for ; Wed, 9 Nov 2022 07:42:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EFBB93858D32 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-x62a.google.com with SMTP id f27so44465691eje.1 for ; Tue, 08 Nov 2022 23:42:13 -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=pN6P6tBcOKUAvO6YZdaMMW+FgDJjCZWDOP4vITZ7h1o=; b=MYPmP0LRcskzhZ8JR9Ao89zyGBpvgL4rpy/FrMxdFOTqsaspXNcz6J9B35+FdDtkSZ 84oPO8rmCyKgmUxzMutWKFPsxNzXVXimDGZz196omXvaJ7YsrVa/Lnm9F46NHnR4zuuO kBTakIjT0aH8vqd+FKa+q0plKFGvMgdsOuKgkNgAk8WRktaHFNtrZiEKkUPeVQtiG4+6 bWMkIKuyxGPlz4mED8gxELCJdfaJ7Z4bodJnYvkrY/mOKX7u0J+ofTUr0AwrxjjfvWAS mg/zuHOAXHzYEckaj7xoGB6GuTdDFqKtQ/7xRXyYq1b2D83S9f/IJzB8M1TrDNJc24N7 ZwlQ== 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=pN6P6tBcOKUAvO6YZdaMMW+FgDJjCZWDOP4vITZ7h1o=; b=hQdetUMcrZG7UMljrtQObMS7uF52ZoSj28rlrqzjQ17E/MrAuehqMj0cZY7LXBcQks smOS8EpphHf+MvZ9ZHHwbZMym/HnbTcg8Fjhd28NAT6kWq4H/S00zJpaazy8sa4xP2Ol 8Txnaq1aRHPxvsxPxvy9+kj+koqskh2tnNLomceQRslSSyUSkmM7JeJSl5gr03cAx9i8 94maZMkKRFAAnkMTKjxg8gyEjW54CdZMFvw6tgUNbTETdv5lQJsG8Sa71PLg5BSr8nrk /9sQPfocEfyBtrvW9FNLj/Gh+20Iwsy7mggJcs2kXTvQI7ARQDJAo9YH8QqoNwJRPB44 jFEQ== X-Gm-Message-State: ACrzQf3XZoWM2UfZ8AsKBN7DDY600YB5JjbbLeKOKBdwCqDJHZv7NNMQ SXy2VHwf7pOmf3hDlg3Nx/4VDpiOJILpNVYRngo= X-Google-Smtp-Source: AMsMyM6toFa1/FlDv3ujdDnfgoQACwAhQaP5nxISNXJSIbxiqRRoIayelRFQXmWn4qMt2SSNX/HeYBHPnsdcM5f1SB0= X-Received: by 2002:a17:906:839a:b0:78d:f308:1cd with SMTP id p26-20020a170906839a00b0078df30801cdmr1065221ejx.754.1667979732579; Tue, 08 Nov 2022 23:42:12 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Wed, 9 Nov 2022 08:41:59 +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.3 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 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 > > > >