[Bug target/36473] New: Generate bit test (bt) instructions

[Bug target/36473] New: Generate bit test (bt) instructions

[ubizjak at gmail dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1805 bytes --]

According to Intel Technology Journal [1], page 270, bt instruction runs 20%
faster on Core2 Duo than equivalent generic code.

---Qoute from p.270---
The bit test instruction bt was introduced in the i386™
processor. In some implementations, including the Intel
NetBurst® micro-architecture, the instruction has a high
latency. The Intel Core micro-architecture executes bt in
a single cycle, when the bit base operand is a register.
Therefore, the Intel C++/Fortran compiler uses the bt
instruction to implement a common bit test idiom when
optimizing for the Intel Core micro-architecture. The
optimized code runs about 20% faster than the generic
version on an Intel Core 2 Duo processor. Both of these
versions are shown below:

C source code
  int x, n;
  ...
  if (x & (1 << n)) ...

Generic code generation
  ; edx contains x, ecx contains n.
  mov eax, 1
  shl eax, cl
  test edx, eax
  je taken

Intel Core micro-architecture code generation
  ; edx contains x, eax contains n.
  bt edx, eax
  jae taken
---/Quote---

I have a patch in testing that implements suggested optimization for
TARGET_USE_BT (including core2) targets.

[1] Inside the Intel® 10.1 Compilers: New Threadizer and New
Vectorizer for Intel® Core™2 Processors, Intel Technology Journal, Vol. 11,
Issue 4, November 15, 2007,
http://download.intel.com/technology/itj/2007/v11i4/1-inside/1-Inside_the_Intel_Compilers.pdf


-- 
           Summary: Generate bit test (bt) instructions
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: target
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: ubizjak at gmail dot com
GCC target triplet: x86


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36473

[Bug target/36473] Generate bit test (bt) instructions

[ubizjak at gmail dot com]

------- Comment #1 from ubizjak at gmail dot com  2008-06-09 11:39 -------
Created an attachment (id=15741)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15741&action=view)
Proposed patch

Following code:

--cut here--
void foo (void);

int test (int x, int n)
{
  if (x & (1 << n))
    foo ();

  return 0;
}
--cut here--

compiles using -O2 to:

test:
        subl    $12, %esp
        movl    16(%esp), %eax
        movl    20(%esp), %ecx
        sarl    %cl, %eax
        testb   $1, %al
        je      .L2
        call    foo
.L2:
        xorl    %eax, %eax
        addl    $12, %esp
        ret

With attached patch, following code is produced:

test:
        subl    $12, %esp
        movl    20(%esp), %edx
        movl    16(%esp), %eax
        btl     %edx, %eax
        jnc     .L2
        call    foo
.L2:
        xorl    %eax, %eax
        addl    $12, %esp
        ret

Attached patch doesn't have TARGET_USE_BT insn predicates, and it generates bt
instructions by default. It was used to bootstrap gcc on i686-pc-linux-gnu,
where it converts >1800 shift-and-test sequences into eqivalent bt instruction.

The patch as is was bootstrapped and regression tested on x86_64-pc-linux-gnu
as well as i686-pc-linux-gnu.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36473

[Bug target/36473] Generate bit test (bt) instructions

[ubizjak at gmail dot com]

------- Comment #2 from ubizjak at gmail dot com  2008-06-09 11:41 -------
Mine, the patch needs testcases.

2008-06-09  Uros Bizjak  <ubizjak@gmail.com>

        * config/i386/predicates.md (bt_comparison_operator): New predicate.
        * config/i386/i386.md (*btdi_rex64): New instruction pattern.
        (*btsi): Ditto.
        (*jcc_btdi_rex64): New instruction and split pattern.
        (*jcc_btsi): Ditto.
        (*jcc_btsi_1): Ditto.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |ubizjak at gmail dot com
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-06-09 11:41:11
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36473

[Bug target/36473] Generate bit test (bt) instructions

[uros at gcc dot gnu dot org]

------- Comment #3 from uros at gcc dot gnu dot org  2008-06-10 10:30 -------
Subject: Bug 36473

Author: uros
Date: Tue Jun 10 10:29:36 2008
New Revision: 136615

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=136615
Log:
        PR target/36473
        * config/i386/i386.c (ix86_tune_features) [TUNE_USE_BT]:
        Add m_CORE2 and m_GENERIC.
        * config/i386/predicates.md (bt_comparison_operator): New predicate.
        * config/i386/i386.md (*btdi_rex64): New instruction pattern.
        (*btsi): Ditto.
        (*jcc_btdi_rex64): New instruction and split pattern.
        (*jcc_btsi): Ditto.
        (*jcc_btsi_1): Ditto.
        (*btsq): Fix Intel asm dialect operand order.
        (*btrq): Ditto.
        (*btcq): Ditto.

testsuite/ChangeLog:

        PR target/36473
        * testsuite/gcc.target/i386/bt-1.c: New test.
        * testsuite/gcc.target/i386/bt-2.c: Ditto.


Added:
    trunk/gcc/testsuite/gcc.target/i386/bt-1.c
    trunk/gcc/testsuite/gcc.target/i386/bt-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/config/i386/i386.c
    trunk/gcc/config/i386/i386.md
    trunk/gcc/config/i386/predicates.md
    trunk/gcc/testsuite/ChangeLog


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36473

[Bug target/36473] Generate bit test (bt) instructions

[ubizjak at gmail dot com]

------- Comment #4 from ubizjak at gmail dot com  2008-07-13 08:44 -------
This is now implemented in mainline.


-- 

ubizjak at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2008-
                   |                            |06/msg00503.html
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36473