[Bug rtl-optimization/57459] New: LRA inheritance bug

[Bug rtl-optimization/57459] New: LRA inheritance bug

[wmi at google dot com]

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

            Bug ID: 57459
           Summary: LRA inheritance bug
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: wmi at google dot com

Created attachment 30218
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30218&action=edit
small testcase

To reproduce the bug on using 1.c attached: 

Target: x86_64-unknown-linux-gnu
gcc version 4.9.0 20130529 (experimental) (GCC)

$~/workarea/gcc-r199418/build/install/bin/gcc -fno-inline -O2
-minline-all-stringops -fno-omit-frame-pointer -m32 1.c
$./a.out
len = 9

$~/workarea/gcc-r199418/build/install/bin/gcc -O2 -m32 1.c
$./a.out
len = 8

The expanded __builtin_strlen is wrong:

 80484c3:       8b 07                   mov    (%edi),%eax
 80484c5:       83 c7 04                add    $0x4,%edi
 80484c8:       8d 90 ff fe fe fe       lea    -0x1010101(%eax),%edx
 80484ce:       f7 d0                   not    %eax
 80484d0:       21 c2                   and    %eax,%edx
 80484d2:       81 e2 80 80 80 80       and    $0x80808080,%edx
 80484d8:       74 e9                   je     80484c3 <foo+0x63>
 80484da:       89 d0                   mov    %edx,%eax
 80484dc:       8b 55 ec                mov    -0x14(%ebp),%edx
 80484df:       89 55 e8                mov    %edx,-0x18(%ebp)
 80484e2:       89 c2                   mov    %eax,%edx
 80484e4:       c1 e8 10                shr    $0x10,%eax
 80484e7:       f7 c2 80 80 00 00       test   $0x8080,%edx
 80484ed:       89 45 ec                mov    %eax,-0x14(%ebp)
 80484f0:       89 d0                   mov    %edx,%eax
 80484f2:       8d 57 02                lea    0x2(%edi),%edx
 80484f5:       0f 44 fa                cmove  %edx,%edi
 80484f8:       8b 55 e8                mov    -0x18(%ebp),%edx
 80484fb:       0f 44 45 ec             cmove  -0x14(%ebp),%eax

 80484ff:       00 45 e4                add    %al,-0x1c(%ebp)   ====> Wrong
here, the correct insn is: add %al, %al. %al is either 0x80 or 0x0 here. The
insn "add  %al, %al" is used to check whether %al is 0x80, and it will produce
carry bit for the following sbb. (The lowest 0x80 in %eax shows where the first
'\0' is in the input string)

 8048502:       83 df 03                sbb    $0x3,%edi
 8048505:       8b 45 08                mov    0x8(%ebp),%eax
 8048508:       2b 7d 08                sub    0x8(%ebp),%edi


The IR after IRA and before LRA:

(insn 51 50 52 12 (parallel [
            (set (reg:CC 17 flags)
                (unspec:CC [
                        (subreg:QI (reg:SI 79) 0)
                        (subreg:QI (re(insn 292 50 51 12 (set (reg:QI 118)
        (subreg:QI (reg:SI 79) 0)) 1.c:16 87 {*movqi_internal}
     (nil))
(insn 51 292 52 12 (parallel [
            (set (reg:CC 17 flags)
                (unspec:CC [
                        (subreg:QI (reg:SI 79) 0)
                        (reg:QI 118)
                    ] UNSPEC_ADD_CARRY))
            (set (subreg:QI (reg:SI 79) 0)
                (plus:QI (subreg:QI (reg:SI 79) 0)
                    (reg:QI 118)))
        ]) 1.c:16 259 {addqi3_cc}
     (expr_list:REG_UNUSED (reg:SI 79)
        (nil)))g:SI 79) 0)
                    ] UNSPEC_ADD_CARRY))
            (set (subreg:QI (reg:SI 79) 0)
                (plus:QI (subreg:QI (reg:SI 79) 0)
                    (subreg:QI (reg:SI 79) 0)))
        ]) 1.c:16 259 {addqi3_cc}
     (expr_list:REG_UNUSED (reg:SI 79)
        (nil)))

The IR is correct till now. insn 51 will produce the problematic "add
%al,-0x1c(%ebp)" finally. All the input and output operands of insn 51 are
reg79. The reg79 gets no hardreg in IRA phase.  

The IR after lra_constraints:

(insn 292 50 51 12 (set (reg:QI 118)
        (subreg:QI (reg:SI 79) 0)) 1.c:16 87 {*movqi_internal}
     (nil))
(insn 51 292 52 12 (parallel [
            (set (reg:CC 17 flags)
                (unspec:CC [
                        (subreg:QI (reg:SI 79) 0)
                        (reg:QI 118)
                    ] UNSPEC_ADD_CARRY))
            (set (subreg:QI (reg:SI 79) 0)
                (plus:QI (subreg:QI (reg:SI 79) 0)
                    (reg:QI 118)))
        ]) 1.c:16 259 {addqi3_cc}
     (expr_list:REG_UNUSED (reg:SI 79)
        (nil)))

The IR is still correct. 
The choosen constraints of insn 51 are "rm" "0" "rn". reg79 get no hardreg in
IRA, so the output operand and the first input operand satisfy the constraint
(staying in mem), but the second input operand should stay in register. That is
why reg118 is introduced and insn 292 is inserted. 

The IR after lra_inheritance:

(insn 289 47 48 12 (set (reg:SI 116 [79])
        (reg:SI 121 [79])) 1.c:16 85 {*movsi_internal}
     (nil))
(insn 48 289 290 12 (set (reg:SI 116 [79])
        (if_then_else:SI (eq (reg:CCNO 17 flags)
                (const_int 0 [0]))
            (reg:SI 122 [83])
            (reg:SI 116 [79]))) 1.c:16 923 {*movsicc_noc}
     (expr_list:REG_DEAD (reg:SI 122 [83])
        (nil)))
(insn 290 48 294 12 (set (reg:SI 120 [79])
        (reg:SI 116 [79])) 1.c:16 85 {*movsi_internal}
     (nil))
......
(insn 292 50 51 12 (set (reg:QI 118)
        (subreg:QI (reg:SI 120 [79]) 0)) 1.c:16 87 {*movqi_internal}
     (nil))
(insn 51 292 52 12 (parallel [
            (set (reg:CC 17 flags)
                (unspec:CC [
                        (subreg:QI (reg:SI 79) 0)
                        (reg:QI 118)
                    ] UNSPEC_ADD_CARRY))
            (set (subreg:QI (reg:SI 79) 0)
                (plus:QI (subreg:QI (reg:SI 79) 0)
                    (reg:QI 118)))
        ]) 1.c:16 259 {addqi3_cc}
     (expr_list:REG_UNUSED (reg:SI 79)
        (nil)))

The IR is incorrect here. 
The reg79 in insn 292 get a reload reg to reuse, so it is changed to reg120.
But the reg79 in insn 51 doesn't change accordingly. It is the cause of the
problem. If all the reg79 do the reload reg reuse, then the problem will not
happen.  

In inherit_in_ebb called by lra_inheritance, those pesudo reg which doesn't get
hardreg and those with reg_type == OP_IN are considered as candidates to reuse
previous reload regs (lra-constraints.c:4892, r199418). For reg79 in insn 292,
it has no hardreg and its type is OP_IN, so it is choosen and replaced by
reg120, but for reg79 in insn 51, its type is OP_INOUT, so it is not choosen. I
guess OP_INOUT should also be included into the candidate choosing conditions,
but I am not sure.

[Bug rtl-optimization/57459] LRA inheritance bug

[ppluzhnikov at google dot com]

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

--- Comment #1 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
Google ref: b/9070967

This is a 4.8/4.9 regression.

We have ~300 test cases (out of 500,000) that are all failing (in i386 mode
only) due to this bug.

[Bug rtl-optimization/57459] [4.8/4.9 Regression] LRA inheritance bug

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ra, wrong-code
   Target Milestone|---                         |4.8.1
            Summary|LRA inheritance bug         |[4.8/4.9 Regression] LRA
                   |                            |inheritance bug

[Bug rtl-optimization/57459] [4.8/4.9 Regression] LRA inheritance bug

[jakub at gcc dot gnu.org]

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

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

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

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

[Bug rtl-optimization/57459] [4.8/4.9 Regression] LRA inheritance bug

[ppluzhnikov at google dot com]

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

--- Comment #3 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
Mis-computing strlen() in shipping GCC releases doesn't look like P3 to me.

Could anyone please confirm this bug, set priority appropriately, and/or
comment on how this should be fixed?  Thanks,

[Bug rtl-optimization/57459] [4.8/4.9 Regression] LRA inheritance bug

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Paul Pluzhnikov from comment #3)
> Mis-computing strlen() in shipping GCC releases doesn't look like P3 to me.

P3 means unset priority.

[Bug rtl-optimization/57459] [4.8/4.9 Regression] LRA inheritance bug

[mikpe at it dot uu.se]

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

Mikael Pettersson <mikpe at it dot uu.se> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mikpe at it dot uu.se

--- Comment #5 from Mikael Pettersson <mikpe at it dot uu.se> ---
r192718 was OK, started with r192719, the LRA merge and activation on x86.

[Bug rtl-optimization/57459] [4.8/4.9 Regression] LRA inheritance bug

[wmi at google dot com]

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

--- Comment #6 from wmi at google dot com ---
continue the analysis in the first post, for the smallcase 1.c, the IR after
calling inherit_in_ebb in lra_inheritance for bb12 is:

(insn 289 47 48 12 (set (reg:SI 116 [79])
        (reg:SI 121 [79])) 1.c:16 85 {*movsi_internal}
     (nil))
(insn 48 289 290 12 (set (reg:SI 116 [79])
        (if_then_else:SI (eq (reg:CCNO 17 flags)
                (const_int 0 [0]))
            (reg:SI 122 [83])
            (reg:SI 116 [79]))) 1.c:16 923 {*movsicc_noc}
     (expr_list:REG_DEAD (reg:SI 122 [83])
        (nil)))
(insn 290 48 294 12 (set (reg:SI 120 [79])
        (reg:SI 116 [79])) 1.c:16 85 {*movsi_internal}
     (nil))
(insn 294 290 49 12 (set (reg:SI 79)
        (reg:SI 120 [79])) 1.c:16 85 {*movsi_internal}
     (nil))
......
(insn 292 50 51 12 (set (reg:QI 118)
        (subreg:QI (reg:SI 120 [79]) 0)) 1.c:16 87 {*movqi_internal}
     (nil))
(insn 51 292 52 12 (parallel [
            (set (reg:CC 17 flags)
                (unspec:CC [
                        (subreg:QI (reg:SI 79) 0)
                        (reg:QI 118)
                    ] UNSPEC_ADD_CARRY))
            (set (subreg:QI (reg:SI 79) 0)
                (plus:QI (subreg:QI (reg:SI 79) 0)It is still correct 
                    (reg:QI 118)))
        ]) 1.c:16 259 {addqi3_cc}
     (expr_list:REG_UNUSED (reg:SI 79)
        (nil)))

The IR is still correct after this step. 

However, after update_ebb_live_info (called after inherit_in_ebb), insn 294 is
removed. Then reg 79 cannot get updated value and it doesn't equal to reg 118
anymore. IR is wrong after this step. 
insn 294 is removed in update_ebb_live_info because the reg type of reg 79 is
OP_INOUT but update_ebb_live_info only marks OP_IN type reg as live_regs.

So the fix is:
Index: gcc/lra-constraints.c
===================================================================
--- gcc/lra-constraints.c    (revision 199752)
+++ gcc/lra-constraints.c    (working copy)
@@ -4545,7 +4545,7 @@ update_ebb_live_info (rtx head, rtx tail
       bitmap_clear_bit (&live_regs, reg->regno);
       /* Mark each used value as live.  */
       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
-    if (reg->type == OP_IN
+    if ((reg->type == OP_IN || reg->type == OP_INOUT)
         && bitmap_bit_p (&check_only_regs, reg->regno))
       bitmap_set_bit (&live_regs, reg->regno);
       /* It is quite important to remove dead move insns because it

Bootstrapped and tested on x86_64-linux.

[Bug rtl-optimization/57459] [4.8 Regression] LRA inheritance bug

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-06-07
           Assignee|unassigned at gcc dot gnu.org      |vmakarov at gcc dot gnu.org
            Summary|[4.8/4.9 Regression] LRA    |[4.8 Regression] LRA
                   |inheritance bug             |inheritance bug
     Ever confirmed|0                           |1

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: vmakarov
Date: Thu Jun  6 20:58:46 2013
New Revision: 199762

URL: http://gcc.gnu.org/viewcvs?rev=199762&root=gcc&view=rev
Log:
2013-06-06  Vladimir Makarov  <vmakarov@redhat.com>

    PR rtl-optimization/57459
    * lra-constraints.c (update_ebb_live_info): Fix typo for operand
    type when setting live regs.

2013-06-06  Vladimir Makarov  <vmakarov@redhat.com>

    PR rtl-optimization/57459
    * gcc.target/i386/pr57459.c: New test.


Added:
    trunk/gcc/testsuite/gcc.target/i386/pr57459.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/lra-constraints.c
    trunk/gcc/testsuite/ChangeLog

[Bug rtl-optimization/57459] [4.8 Regression] LRA inheritance bug

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 30643
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30643&action=edit
rh995446.i

We've got this reported in https://bugzilla.redhat.com/show_bug.cgi?id=995446
too.
I've created a self-contained executable testcase out of that.

Vlad, can you please backport this to 4.8 branch or are there any issues that
prevent it?  I'll add the testcase to 4.8/trunk afterwards.

[Bug rtl-optimization/57459] [4.8 Regression] LRA inheritance bug

[vmakarov at gcc dot gnu.org]

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

--- Comment #9 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #8)
> Created attachment 30643 [details]
> rh995446.i
> 
> We've got this reported in
> https://bugzilla.redhat.com/show_bug.cgi?id=995446 too.
> I've created a self-contained executable testcase out of that.
> 
> Vlad, can you please backport this to 4.8 branch or are there any issues
> that prevent it?  I'll add the testcase to 4.8/trunk afterwards.

As the patch does not depend on any recent LRA development,  I've committed the
patch into gcc-4_8-branch.  So the problem should be solved for gcc-4.8.

[Bug rtl-optimization/57459] [4.8 Regression] LRA inheritance bug

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: vmakarov
Date: Tue Aug 13 16:40:33 2013
New Revision: 201695

URL: http://gcc.gnu.org/viewcvs?rev=201695&root=gcc&view=rev
Log:
2013-08-13  Vladimir Makarov  <vmakarov@redhat.com>

    Backport from mainline
    2013-06-06  Vladimir Makarov  <vmakarov@redhat.com>

    PR rtl-optimization/57459
    * lra-constraints.c (update_ebb_live_info): Fix typo for operand
    type when setting live regs.

2013-08-13  Vladimir Makarov  <vmakarov@redhat.com>

    Backport from mainline
    2013-06-06  Vladimir Makarov  <vmakarov@redhat.com>

    PR rtl-optimization/57459
    * gcc.target/i386/pr57459.c: New test.


Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.target/i386/pr57459.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/lra-constraints.c
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog