x86: Improve expansion of __builtin_parity

This patch changes the way that __builtin_parity is expanded in i386.md.

This changes the code generated for the function:

int test(unsigned char a)

{

   unsigned char x = a + 1;

   return __builtin_parity(x);

}

from this before the patch:

test:   addl    $1, %edi

        movzbl  %dil, %edi

        movl    %edi, %eax

        shrl    $16, %edi

        xorl    %edi, %eax

        xorb    %ah, %al

        setnp   %al

        movzbl  %al, %eax

        ret

to this with the patch:

test:   leal    1(%rdi), %eax

        testb   %al, %al

        setnp   %al

        movzbl  %al, %eax

        ret

GCC currently hides the shift and xor reduction inside a backend

specific UNSPEC PARITY, making it invisible to the RTL optimizers until

very late during compilation.  It is normally reasonable for the

middle-end to maintain wider mode representations for as long as possible

and split them later, but this only helps if the semantics are visible

at the RTL-level (to combine and other passes), but UNSPECs are black

boxes, so in this case splitting early (during RTL expansion) is a

better strategy.

I'd originally written this patch after investigating whether GCC could

generate the x86's "jp" and "jnp" conditional branch on parity flag,

and noticed the inefficient reduction.  It was only when I was preparing

this patch for submission that I discovered that this is actually a

regression fix, and that Uros had already implemented/thought about the

above optimization back in 2007.  Indeed the example above is taken from

https://gcc.gnu.org/legacy-ml/gcc-patches/2007-02/msg00972.html

Alas there is a mismatch between RTL's definition of PARITY operation

which has an integer mode result, and the x86's parity flag.  So when

Uros addressed PR target/44481 in 2010, by introducing UNSPEC PARITY,

we lost some of the optimization opportunities of his original patch.

https://gcc.gnu.org/legacy-ml/gcc-patches/2010-06/msg01259.html

The early splitting approach in this patch safely restores the 2007-2010

optimization opportunities.

It turns out that that popcount instruction on modern x86_64 processors

has (almost) made the integer parity flag in the x86 ALU completely

obsolete, especially as POPCOUNT's integer semantics are a much better

fit to RTL.  The one remaining case where these transistors are useful

is where __builtin_parity is immediately tested by a conditional branch,

and therefore the result is wanted in a flags register rather than as

an integer.  This case is captured by two peephole2 optimizations in

the attached patch.

Hence the code:

void foo(unsigned char x)

{

  if (__builtin_parity(x))

    bar();

}

which on modern hardware is currently generated as:

foo:    movzbl  %dil, %edi

        popcntl %edi, %edi

        andl    $1, %edi

        jne     .L4

        ret

.L4:    jmp     bar

with this patch will be generated as:

foo:    testb   %dil, %dil

        jnp     .L4

        ret

.L4:    jmp     bar

[I believe that popcount has a 3-cycle latency, but a test followed by a

conditional branch can dispatch in the same cycle, but I'm not an expert].

The new parityhi2 and parityqi2 expanders are infrastructure to support

(possible) future middle-end changes.

This patch has been tested with a "make bootstrap" and "make -k check" on

x86_64-pc-linux-gnu with no regressions.  I've also added 7 new test cases;

4 tests gcc.target/i386/parity-[3-6].c check the existing behaviour, and

3 tests gcc.target/i386/parity-[7-9].c check the changes from this patch.

Alas I'm very out of practice contributing patches (but my paperwork should

still be valid), so if a friendly i386/x86_64 backend maintainer could take

care of things from here, that would be very much appreciated.

Many thanks in advance,

Roger

--

2020-06-05  Roger Sayle  <roger@nextmovesoftware.com>

        * config/i386/i386.md (paritydi2, paritysi2): Expand reduction

        via shift and xor to an USPEC PARITY matching a parityhi2_cmp.

        (paritydi2_cmp, paritysi2_cmp): Delete these define_insn_and_split.

        (parityhi2, parityqi2): New expanders.

        (parityhi2_cmp): Implement set parity flag with xorb insn.

        (parityqi2_cmp): Implement set parity flag with testb insn.

        New peephole2s to use these insns (UNSPEC PARITY) when appropriate.

2020-06-05  Roger Sayle  <roger@nextmovesoftware.com>

        * gcc.target/i386/parity-[3-9].c: New tests.

/* { dg-do compile } */
/* { dg-options "-O2 -march=core-avx2 -mno-popcnt" } */
/* { dg-final { scan-assembler "setp" } } */
/* { dg-final { scan-assembler "jnp" } } */
/* { dg-final { scan-assembler "jp" } } */

void dummy(void);

int foo(unsigned int x)
{
  return !__builtin_parity(x);
}

void bar(unsigned int x)
{
  if (__builtin_parity(x))
    dummy();
}

void baz(unsigned int x)
{
  if (!__builtin_parity(x))
    dummy();
}
/* { dg-do compile } */
/* { dg-options "-O2 -march=core-avx2 -mno-popcnt" } */
/* { dg-final { scan-assembler "setp" } } */
/* { dg-final { scan-assembler "jnp" } } */
/* { dg-final { scan-assembler "jp" } } */

void dummy(void);

int foo(unsigned long long x)
{
  return !__builtin_parityll(x);
}

void bar(unsigned long long x)
{
  if (__builtin_parityll(x))
    dummy();
}

void baz(unsigned long long x)
{
  if (!__builtin_parityll(x))
    dummy();
}
/* { dg-do compile } */
/* { dg-options "-O2 -march=core-avx2" } */
/* { dg-final { scan-assembler "popcnt" } } */
/* { dg-final { scan-assembler "and" } } */

int foo(unsigned int x)
{
  return __builtin_parity(x);
}
/* { dg-do compile } */
/* { dg-options "-O2 -march=core-avx2" } */
/* { dg-final { scan-assembler "popcnt" } } */
/* { dg-final { scan-assembler "and" } } */

int foo(unsigned long long x)
{
  return __builtin_parityll(x);
}
/* { dg-do compile } */
/* { dg-options "-O2 -march=core-avx2 -mno-popcnt" } */
/* { dg-final { scan-assembler-times "test" 2 } } */
/* { dg-final { scan-assembler-not "shr" } } */

int foo(unsigned char x)
{
  return __builtin_parity(x);
}

int bar(unsigned char x)
{
  return __builtin_parityll(x);
}
/* { dg-do compile } */
/* { dg-options "-O2 -march=core-avx2 -mno-popcnt" } */
/* { dg-final { scan-assembler-not "shr" } } */

int foo(unsigned short x)
{
  return __builtin_parity(x);
}

int bar(unsigned short x)
{
  return __builtin_parityll(x);
}
/* { dg-do compile } */
/* { dg-options "-O2 -march=core-avx2" } */
/* { dg-final { scan-assembler-not "popcnt" } } */
/* { dg-final { scan-assembler-not "shr" } } */
/* { dg-final { scan-assembler-times "jp" 2 } } */
/* { dg-final { scan-assembler-times "jnp" 2 } } */

void dummy(void);

void pos8(unsigned char x)
{
  if (__builtin_parity(x))
    dummy();
}

void neg8(unsigned char x)
{
  if (!__builtin_parity(x))
    dummy();
}

void pos16(unsigned short x)
{
  if (__builtin_parity(x))
    dummy();
}

void neg16(unsigned short x)
{
  if (!__builtin_parity(x))
    dummy();
}

Message ID	004b01d63c08$f3c70640$db5512c0$@nextmovesoftware.com
State	New
Headers	show Return-Path: <gcc-patches-bounces@gcc.gnu.org> X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=<UNKNOWN>) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=nextmovesoftware.com header.i=@nextmovesoftware.com header.a=rsa-sha256 header.s=default header.b=hGJehrO1; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (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 ozlabs.org (Postfix) with ESMTPS id 49fLRR5ZN5z9sRh for <incoming@patchwork.ozlabs.org>; Sat, 6 Jun 2020 23:47:13 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 848FF387090B; Sat, 6 Jun 2020 13:47:04 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from server.nextmovesoftware.com (server.nextmovesoftware.com [162.254.253.69]) by sourceware.org (Postfix) with ESMTPS id AC2A03851C2F for <gcc-patches@gcc.gnu.org>; Sat, 6 Jun 2020 13:47:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org AC2A03851C2F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=nextmovesoftware.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=roger@nextmovesoftware.com DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=nextmovesoftware.com; s=default; h=Content-Type:MIME-Version:Message-ID: Date:Subject:To:From:Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:In-Reply-To:References:List-Id:List-Help:List-Unsubscribe: List-Subscribe:List-Post:List-Owner:List-Archive; bh=TKdiF74gI6D9jDlJgeqVX1FkK8ruH+SKKInwxzsWLw8=; b=hGJehrO1MxQrt+j6lo15KbYGpH nPl2CpKA8oECYq2B4XX2tuC+q99PuWLxyAigm6TQNlQMIzS3ljdZOf2aTE5RpbPJy8yV6V/9yYYrX 79V2U6nE2uyREYu5pG0Dx6Zv24UwvTtZcnBOeCuah5UoDD/B8NMeDIwVdnnHVyDJe8OKNWqQMwJjc rK0geCXl1CD74kkkkDDRUHekQSMp0vhLGALOil052sQKKFgLPfmhd5IZDPp2kk0//REENLWjhZQzn q6WCchuAahbOujtPMnR7Gt335oo0Cgr0gemAcyT4/MUXIpbKqV87rJUjeIhJMuIAOhb5ksfRFsd8K A4UBqZZw==; Received: from host86-137-89-123.range86-137.btcentralplus.com ([86.137.89.123]:56466 helo=Dell) by server.nextmovesoftware.com with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.93) (envelope-from <roger@nextmovesoftware.com>) id 1jhZA4-0005Ws-S0 for gcc-patches@gcc.gnu.org; Sat, 06 Jun 2020 09:47:01 -0400 From: "Roger Sayle" <roger@nextmovesoftware.com> To: <gcc-patches@gcc.gnu.org> Subject: [PATCH] x86: Improve expansion of __builtin_parity Date: Sat, 6 Jun 2020 14:46:58 +0100 Message-ID: <004b01d63c08$f3c70640$db5512c0$@nextmovesoftware.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_NextPart_000_004C_01D63C11.55929A30" X-Mailer: Microsoft Outlook 16.0 Thread-Index: AdY8B6mcl+PXoeHHSn2RoFcCVC56Fg== Content-Language: en-gb X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - server.nextmovesoftware.com X-AntiAbuse: Original Domain - gcc.gnu.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - nextmovesoftware.com X-Get-Message-Sender-Via: server.nextmovesoftware.com: authenticated_id: roger@nextmovesoftware.com X-Authenticated-Sender: server.nextmovesoftware.com: roger@nextmovesoftware.com X-Source: X-Source-Args: X-Source-Dir: X-Spam-Status: No, score=-11.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, HTML_MESSAGE, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list <gcc-patches.gcc.gnu.org> List-Unsubscribe: <http://gcc.gnu.org/mailman/options/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe> List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help> List-Subscribe: <http://gcc.gnu.org/mailman/listinfo/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe> Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" <gcc-patches-bounces@gcc.gnu.org>
Series	x86: Improve expansion of __builtin_parity \| expand x86: Improve expansion of __builtin_parity

x86: Improve expansion of __builtin_parity

Commit Message

Patch