[Bug rtl-optimization/58295] New: The combination pass doesn't eliminates some extra zero extensions

[Bug rtl-optimization/58295] New: The combination pass doesn't eliminates some extra zero extensions

[uranus at tinlans dot org]

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

            Bug ID: 58295
           Summary: The combination pass doesn't eliminates some extra
                    zero extensions
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: uranus at tinlans dot org

$ cat test.c
extern char zeb_test_array[10];

unsigned char ee_isdigit2(unsigned int i)
{
  unsigned char c = zeb_test_array[i];
  unsigned char retval;

  retval = ((c>='0') & (c<='9')) ? 1 : 0;
  return retval;
}

$ arm-eabi-gcc -v
Using built-in specs.
COLLECT_GCC=arm-eabi-gcc
COLLECT_LTO_WRAPPER=/home1/lhtseng/arm/4.9/libexec/gcc/arm-eabi/4.9.0/lto-wrapper
Target: arm-eabi
Configured with: ../../../../work/4.9/src/gcc-4.9.0/configure --target=arm-eabi
--prefix=/home1/lhtseng/arm/4.9 --disable-nls --disable-shared
--enable-languages=c --enable-__cxa_atexit --enable-c99 --enable-long-long
--enable-threads=single --with-newlib --disable-multilib --disable-libssp
--disable-libgomp --disable-decimal-float --disable-libffi --disable-libmudflap
--disable-lto --with-gmp=/home1/lhtseng/work/general
--with-mpfr=/home1/lhtseng/work/general --with-mpc=/home1/lhtseng/work/general
--with-isl=/home1/lhtseng/work/general --with-cloog=/home1/lhtseng/work/general
Thread model: single
gcc version 4.9.0 20130802 (experimental) (GCC) 

$ arm-eabi-gcc -O3 -S test.c
$ cat test.s
...
ee_isdigit2:
        @ Function supports interworking.
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        @ link register save eliminated.
        ldr     r3, .L2
        ldrb    r0, [r3, r0]    @ zero_extendqisi2
        sub     r0, r0, #48
        and     r0, r0, #255
        cmp     r0, #9
        movhi   r0, #0
        movls   r0, #1
        bx      lr
...

The instruction 'and r0, r0, #255' is a redundant instruction which cannot be
eliminated by the RTL instruction combination pass. This pass was able to
handle this case before this commit:
http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/simplify-rtx.c?r1=191909&r2=191928&pathrev=192303
And the code was re-organized to line 643 ~ 656 after this commit:
http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/simplify-rtx.c?r1=192006&r2=192186&pathrev=192303
For example, GCC 4.6.3 can handle it perfectly.

In GCC 4.9.0, reverting the two commits or simply commeting the lines mentioned
above can make the combination pass handle this case again:
$ arm-eabi-gcc-modified -O3 -da -S test.c
$ cat test.c.166r.expand
...
(insn 9 8 10 2 (set (reg:SI 120)
        (plus:SI (subreg:SI (reg:QI 118) 0)
            (const_int -48 [0xffffffffffffffd0]))) test.c:6 -1
     (nil))
(insn 10 9 11 2 (set (reg:SI 121)
        (and:SI (reg:SI 120)
            (const_int 255 [0xff]))) test.c:6 -1
     (nil))
(insn 11 10 12 2 (set (reg:CC 100 cc)
        (compare:CC (reg:SI 121)
            (const_int 9 [0x9]))) test.c:6 -1
     (nil))
(insn 12 11 13 2 (set (reg:SI 122)
        (leu:SI (reg:CC 100 cc)
            (const_int 0 [0]))) test.c:6 -1
     (nil))
...
$ cat test.c.197r.combine
...
Trying 9, 10 -> 11:
Failed to match this instruction:
(set (reg:CC 100 cc)
    (compare:CC (plus:SI (reg:SI 119)
            (const_int -48 [0xffffffffffffffd0]))
        (const_int 9 [0x9])))
Successfully matched this instruction:
(set (reg:SI 121)
    (plus:SI (reg:SI 119)
        (const_int -48 [0xffffffffffffffd0])))
Successfully matched this instruction:
(set (reg:CC 100 cc)
    (compare:CC (reg:SI 121)
        (const_int 9 [0x9])))
deferring deletion of insn with uid = 9.
modifying insn i2    10: r121:SI=r119:SI-0x30
      REG_DEAD r119:SI
deferring rescan insn with uid = 10.
modifying insn i3    11: cc:CC=cmp(r121:SI,0x9)
      REG_DEAD r121:SI
deferring rescan insn with uid = 11.
...

The insn 10 is generated by (define_expand "zero_extendqisi2" ...) of ARM's
machine description. Before the commits I mentioned above, the combination pass
successfully combines it with the insn 9. However, after those commits, the
combination pass never tries to do the combination '9, 10 -> 11.'

After reading the commit messages of the file 'simplify-rtx.c', we can
understand the commits, r191928, was trying to optimize x86 code generation,
but it led to the suboptimal code generation of the ARM's target.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |arm*-*-*
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2013-09-02
                 CC|                            |ebotcazou at gcc dot gnu.org
     Ever confirmed|0                           |1
            Summary|The combination pass        |[4.8/4.9 regression] Missed
                   |doesn't eliminate some      |zero-extension elimination
                   |extra zero extensions       |in the combiner
   Target Milestone|---                         |4.8.2

--- Comment #1 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Confirmed.  Seeing that insn 10 is redundant is not immediate but the combiner
was indeed clever enough to do it.  The QI subreg is clearly problematic for
the ARM here (and probably most RISC architectures).

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[jasonwucj at gmail dot com]

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

Chung-Ju Wu <jasonwucj at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jasonwucj at gmail dot com

--- Comment #2 from Chung-Ju Wu <jasonwucj at gmail dot com> ---
(In reply to Eric Botcazou from comment #1)
> combiner was indeed clever enough to do it.  The QI subreg is clearly
> problematic for the ARM here (and probably most RISC architectures).

Yes.  This problem also happens on our Andes nds32 architecture.
(The 'nds32' port is still awaiting for GWP approval before it
 may be committed.  But one can find its initial patch:
 http://gcc.gnu.org/ml/gcc-patches/2013-08/msg01441.html)

As long as we revert r191928, which is the fix for pr54457, and
design the pattern in nds32.md to recognize the insn that
combiner created, the redundant insn 10 can be eliminated.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So perhaps you should just look at combiner dump and see what insns it tried
and failed to match and see if you couldn't add some of them into the affected
backends.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[uranus at tinlans dot org]

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

--- Comment #4 from Ling-hua Tseng <uranus at tinlans dot org> ---
(In reply to Jakub Jelinek from comment #3)
> So perhaps you should just look at combiner dump and see what insns it tried
> and failed to match and see if you couldn't add some of them into the
> affected backends.

It's exactly what I did. Unfortunately, the combinder doesn't give any other
chance to eliminate that redundant zero extension. The cases tried by the
combinder are:
1. (set (reg:SI) (zero_extend:SI (plus:QI (mem:QI) (const_int))))
2. (set (reg:QI) (plus:QI (mem:QI) (const_int)))
3. (set (reg:QI) (plus:QI (subreg:QI) (const_int)))
4. (set (reg:CC) (compare:CC (subreg:QI) (const_int)))
5. (set (reg:CC) (compare:CC (plus:QI (mem:QI) (const_int))))
6. (set (reg:SI) (leu:SI (subreg:QI) (const_int)))
7. (set (reg:SI) (leu:SI (subreg:QI) (const_int)))
8. (set (reg:SI) (leu:SI (plus:QI ...)))

You know 1 & 2 are impossible to most RISC targets, and making all other ones
recognizable is lying GCC that your target supports QImode
arithmetic/comparison. Telling GCC a lie here will result in some code
generation bugs. For example, you will find a fail case in
gcc/testsuite/gcc.c-torture/execute/980617-1.c while you are running a test if
you provide a QImode comparison in the machine description. Here is the source
code of that test case:
void foo (unsigned int * p)
{
  if ((signed char)(*p & 0xFF) == 17 || (signed char)(*p & 0xFF) == 18)
    return;
  else
    abort ();
}

int main ()
{
  int i = 0x30011;
  foo(&i);
  exit (0);
}

The MSB 16 bits contain 0x0003, and the LSB 16 bits contain 0x0011. Using -O3
to compile this code, you will find that GCC simplifies the expression '(signed
char)(*p & 0xFF) == 17 || (signed char)(*p & 0xFF) == 18' to an SImode
subtraction and a QImode comparison.The result is incorrect, because the target
only supports SImode comparisons, i.e., you actually generate an SImode
hardware instruction for the pattern of a QImode comparison, and the MSB 16-bit
is still dirty. Hence 3 ~ 8 are not the ones we can match them in the RTL
combination pass.

Therefore, we can conclude that the original case tried by the combiner is the
best way to merge/reduce the redundant zero extension insn.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

--- Comment #5 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> Therefore, we can conclude that the original case tried by the combiner is
> the best way to merge/reduce the redundant zero extension insn.

Yes and, although x86 is the dominant architecture, it shouldn't be allowed to
penalize all the others.  I think we should restrict the effect of r191928, in
particular it makes little sense as-is if you also define PROMOTE_MODE as on
most RISC architectures.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.2                       |4.8.3

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.8.2 has been released.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
So, any progress here?

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|ebotcazou at gcc dot gnu.org       |
           Assignee|unassigned at gcc dot gnu.org      |ebotcazou at gcc dot gnu.org

--- Comment #9 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Will try something based on PROMOTE_MODE.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[npickito at gmail dot com]

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

Kito Cheng <npickito at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |npickito at gmail dot com

--- Comment #10 from Kito Cheng <npickito at gmail dot com> ---
So why don't reject it at
TARGET_LEGITIMATE_COMBINED_INSN/ix86_legitimate_combined_insn
instead of limit at combine phase if it's only benefit for x86 ?

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

--- Comment #11 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> So why don't reject it at
> TARGET_LEGITIMATE_COMBINED_INSN/ix86_legitimate_combined_insn
> instead of limit at combine phase if it's only benefit for x86 ?

The question sounds self-contradictory...  Anyway, rather than inventing a new
hook for each problem, let's try to formulate it in terms of existing hooks.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[npickito at gmail dot com]

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

--- Comment #12 from Kito Cheng <npickito at gmail dot com> ---
> The question sounds self-contradictory...  Anyway, rather than inventing a new 
> hook for each problem, let's try to formulate it in terms of existing hooks.

TARGET_LEGITIMATE_COMBINED_INSN hook is add in r190846
and x86 used it in r190847.

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

--- Comment #13 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> TARGET_LEGITIMATE_COMBINED_INSN hook is add in r190846
> and x86 used it in r190847.

Sure, but you cannot use an x86 hook to reject something for non-x86 arches...

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

--- Comment #14 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Author: ebotcazou
Date: Tue Dec 10 22:58:37 2013
New Revision: 205874

URL: http://gcc.gnu.org/viewcvs?rev=205874&root=gcc&view=rev
Log:
    PR rtl-optimization/58295
    * simplify-rtx.c (simplify_truncation): Restrict the distribution for
    WORD_REGISTER_OPERATIONS targets.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/simplify-rtx.c

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

--- Comment #15 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Author: ebotcazou
Date: Tue Dec 10 22:59:27 2013
New Revision: 205875

URL: http://gcc.gnu.org/viewcvs?rev=205875&root=gcc&view=rev
Log:
    PR rtl-optimization/58295
    * simplify-rtx.c (simplify_truncation): Restrict the distribution for
    WORD_REGISTER_OPERATIONS targets.

Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/simplify-rtx.c

[Bug rtl-optimization/58295] [4.8/4.9 regression] Missed zero-extension elimination in the combiner

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #16 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
This should be fixed.