From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qv1-xf31.google.com (mail-qv1-xf31.google.com [IPv6:2607:f8b0:4864:20::f31]) by sourceware.org (Postfix) with ESMTPS id CC1943858D1E for ; Wed, 9 Nov 2022 21:06:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CC1943858D1E Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=rivosinc.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rivosinc.com Received: by mail-qv1-xf31.google.com with SMTP id x15so124057qvp.1 for ; Wed, 09 Nov 2022 13:06:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rivosinc-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :from:to:cc:subject:date:message-id:reply-to; bh=0Za/zSjsXSVLghP8pwqC9UI4mURn3t/+Dri8XW7mxz8=; b=sUNrsudbo0UfF1d3Q3h0TqrAJk6CoURYtsbFL1c2Da/Qf7jzC4pT0MYPLu0M2HF0h9 dYTTTfqZ56Z/4KSzg0OSKfx1qxyPtc1oUYa6gwwDsFn1hOWH/8dl4sngnFhupf6IqbJP fNVxgZax9fuJc+cdGCqQe1+wqHQw6LQU0D0Q6lF4EU9IVIpQHtFRjncZqyVdn73887Xd TZoQNGsFYuVeuDKB2DydYmG4+11vVeeeFldQJSw0JsNyRy4sRFI/LpwzO/AGXWGeakiL QdP1msyMorN7/oQ7zP7PP4/HhdRjQokc+mrLbLvQsNEW6I8nbZSH1vqjkKZ2UnhchquY 459g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=0Za/zSjsXSVLghP8pwqC9UI4mURn3t/+Dri8XW7mxz8=; b=LlfcZpL3IEXzBjf9hyjpd7zSDdDkQ4GlboQhgmCE3Z6c/+bovUYBA+bedQzdan0tXb clF87QEdmQsCwz3RFFpSiQ5iYwmPEj7CxyMnDfXaDWJ39E+Hw+oDd7Iq29FfVSgL0XXw B+piWcKR8aopVm9FlMnnFrPdrbBDgEpJ4yWRssYI2EB4IydC4WpHsQGoUdt6thfMXL5U uJ8cb0bcWDC8q1JFA21poqcasBbODfBkhtd1qEFrv9S31RMJnL3Nq6oOcLIgyiddQEuO fpjSbwWUDwtInuPrvRQfcKCeJk4D4jvI32ceo3Cs6rGFH8g4oVm8lH6y+Du7NZfmKJzf S4iA== X-Gm-Message-State: ACrzQf1MHJJx11C4rwaAKAdoqO4ThQOQVAIynruAO3rEiFfeXzklaiw7 RQK7bxJvB1ja7DDMvVRRhbQJaw== X-Google-Smtp-Source: AMsMyM5t7rD1tfP7F3etgELd9eI7PAAb18qw5M9ohsQKgYQjP4/cVr8MdbwHeNYG6yAEIkw6R5z7Ng== X-Received: by 2002:a05:6214:62f:b0:4bb:ea3c:a56 with SMTP id a15-20020a056214062f00b004bbea3c0a56mr50678601qvx.52.1668028007953; Wed, 09 Nov 2022 13:06:47 -0800 (PST) Received: from [192.168.86.117] ([136.57.172.92]) by smtp.gmail.com with ESMTPSA id bs6-20020a05620a470600b006b61b2cb1d2sm11834861qkb.46.2022.11.09.13.06.47 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 09 Nov 2022 13:06:47 -0800 (PST) Message-ID: <92ff713b-e82b-ec4a-4054-b0b7d9f7dfe8@rivosinc.com> Date: Wed, 9 Nov 2022 16:06:47 -0500 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.2.2 Subject: Re: [PATCH] match.pd: rewrite select to branchless expression Content-Language: en-US To: Richard Biener Cc: gcc-patches@gcc.gnu.org, Jeff Law , "jakub@redhat.com >> Jakub Jelinek" References: From: Michael Collison In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-9.2 required=5.0 tests=BAYES_00,BODY_8BITS,DKIM_SIGNED,DKIM_VALID,GIT_PATCH_0,NICE_REPLY_A,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: 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)))) 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 >> >> >> >>