[Bug target/36503] New: x86 can use x >> -y for x >> 32-y

[Bug target/36503] New: x86 can use x >> -y for x >> 32-y

[astrange at ithinksw dot com]

> gcc -v
Using built-in specs.
Target: i386-apple-darwin9.2.2
Configured with: ../gcc/configure --prefix=/usr/local/gcc44
--enable-threads=posix --with-arch=core2 --with-tune=core2 --with-gmp=/sw
--with-mpfr=/sw --disable-nls --disable-bootstrap --enable-checking=yes,rtl
--enable-languages=c,c++,objc
Thread model: posix
gcc version 4.4.0 20080611 (experimental) (GCC) 

gcc compiles

int shift32(int i, int n)
{
        return i >> (32 - n);
}

to

_shift32:
        subl    $12, %esp
        movl    $32, %ecx
        subl    20(%esp), %ecx
        movl    16(%esp), %eax
        sarl    %cl, %eax
        addl    $12, %esp
        ret

Since all 286-and-up CPUs only use the low 5 bits of ecx when shifting, this
can be:

_shift32:
        movl    8(%esp), %ecx
        movl    4(%esp), %eax
        negl   %ecx
        sarl    %cl, %eax
        ret

This is very common in bitstream readers, where it's used to read the top N
bits from a word. ffmpeg already has an inline asm to do it, which I'd like to
get rid of.

I'd guess this applies to some other architectures; it probably works on
x86-64, but doesn't on PPC.


-- 
           Summary: x86 can use x >> -y for x >> 32-y
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: astrange at ithinksw dot com
GCC target triplet: i?86-*-*


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[astrange at ithinksw dot com]

-- 

astrange at ithinksw dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2008-06-12 00:05 -------
>I'd guess this applies to some other architectures; 

Not really.  It depends on the definition of the shift.  Most targets have
undefined values are produced from negative shifts values.


-- 


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2008-06-12 09:25 -------
We have the SHIFT_COUNT_TRUNCATED macro for this (though I'm not sure if
that says negative values are ok).


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2008-06-12 09:25:00
               date|                            |


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[ubizjak at gmail dot com]

------- Comment #3 from ubizjak at gmail dot com  2008-06-12 10:43 -------
(In reply to comment #2)
> We have the SHIFT_COUNT_TRUNCATED macro for this (though I'm not sure if
> that says negative values are ok).

They are, but there is a comment in the documentation:

-- Macro: SHIFT_COUNT_TRUNCATED
   ...

     However, on some machines, such as the 80386 and the 680x0,
     truncation only applies to shift operations and not the (real or
     pretended) bit-field operations.  Define `SHIFT_COUNT_TRUNCATED'
     to be zero on such machines.  Instead, add patterns to the `md'
     file that include the implied truncation of the shift instructions.

I don't know which "real or pretended" bit-field operations are referred here,
since bt insn also truncate its bit-offset operand. OTOH, {SI,HI,QI}mode shifts
all truncate to 0x1f, not to GET_MODE_SIZE(mode) - 1.

I have a patch:

Index: config/i386/i386.c
===================================================================
--- config/i386/i386.c  (revision 136692)
+++ config/i386/i386.c  (working copy)
@@ -24681,6 +24681,22 @@
   emit_insn (fn (dest, tmp2, tmp3));
 }


+/* Target hook for target_shift_trucnation_mask.  */
+static unsigned HOST_WIDE_INT
+ix86_shift_truncation_mask (enum machine_mode mode)
+{
+  if (TARGET_64BIT
+      && mode == DImode)
+    return 0x3f;
+
+  if (mode == SImode
+      || mode == HImode
+      || mode == QImode)
+    return 0x1f;
+
+  return 0;
+}
+
 /* Target hook for scalar_mode_supported_p.  */
 static bool
 ix86_scalar_mode_supported_p (enum machine_mode mode)
@@ -26039,6 +26055,9 @@
 #undef TARGET_GIMPLIFY_VA_ARG_EXPR
 #define TARGET_GIMPLIFY_VA_ARG_EXPR ix86_gimplify_va_arg

+#undef TARGET_SHIFT_TRUNCATION_MASK
+#define TARGET_SHIFT_TRUNCATION_MASK ix86_shift_truncation_mask
+
 #undef TARGET_SCALAR_MODE_SUPPORTED_P
 #define TARGET_SCALAR_MODE_SUPPORTED_P ix86_scalar_mode_supported_p

But it does nothing for this optimization. I guess middle-end should be kicked
to handle this optimization.

BTW: Why does ffmpeg need inline asm for this optimization? Following code
snipped also produces expected code:

int shift32 (int i, int n)
{
  return i >> (-n);
}


-- 


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[astrange at ithinksw dot com]

------- Comment #4 from astrange at ithinksw dot com  2008-06-12 16:48 -------
Maybe it seemed likely to cause a warning - I haven't checked that yet, though.


-- 


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[bonzini at gnu dot org]

------- Comment #5 from bonzini at gnu dot org  2009-11-07 09:21 -------
bt with a memory object and a register index will _not_ truncate the argument:

static int btm(int *a, int b) {
  asm ("btl %2, %1; movl $0, %0; setc %b0" : "=r" (b) : "m" (*a), "0" (b));
  return b;
}

static int btr(int a, int b) {
  asm ("btl %2, %1; movl $0, %0; setc %b0" : "=r" (b) : "r" (a), "0" (b));
  return b;
}

#define btmi(a, b) ({ int __x; \
  asm ("btl %2, %1; movl $0, %0; setc %b0" : "=r" (__x) : "m" (*a), "i" (b)); \
  __x; \
})

int main () {
  int y[3] = { 0x5, 0, 0x5 };
  printf ("bt %%reg, %%reg: %d %d %d\n", btr(5, 0), btr(5, 32), btr(5, 64));
  printf ("bt $bit, (mem): %d %d %d\n", btmi(y, 0), btmi(y, 32), btmi(y, 64)); 
  printf ("bt %%reg, (mem): %d %d %d\n", btm(y, 0), btm(y, 32), btm(y, 64));
}


>> bt %reg, %reg: 1 1 1
>> bt $val, (mem): 1 1 1
>> bt %reg, (mem): 1 0 1


-- 


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[ubizjak at gmail dot com]

------- Comment #6 from ubizjak at gmail dot com  2009-11-09 07:38 -------
(In reply to comment #5)
> bt with a memory object and a register index will _not_ truncate the argument:

Actually, we avoid bt with memory objects just because of this (handling of
memory op is not consistent with register op). Please look at i386.md.


-- 


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

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[astrange at ithinksw dot com]

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

--- Comment #8 from Alexander Strange <astrange at ithinksw dot com> 2010-10-21 04:39:36 UTC ---
I built ffmpeg for x86-64 with --disable-asm with the attached patch and the
regression tests failed. Reverting the patch fixes them. I saved the binaries
but haven't investigated yet.

[Bug target/36503] x86 can use x >> -y for x >> 32-y

[ubizjak at gmail dot com]

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

--- Comment #9 from Uros Bizjak <ubizjak at gmail dot com> 2010-10-22 07:37:22 UTC ---
(In reply to comment #8)
> I built ffmpeg for x86-64 with --disable-asm with the attached patch and the
> regression tests failed. Reverting the patch fixes them. I saved the binaries
> but haven't investigated yet.

The problem is that new insn pattern clobbers %ecx. Currently, this is not
modeled correctly - if this is fixed, then the combine doesn't recognize
combined pattern.  So, either combine should be fixed to allow correct
(match_dup X) in the combined pattern or this transformation should be
implemented in generic part of the compiler.