[Bug libstdc++/61107] New: [4.8/4.9/4.10] stl_algo.h : std::__inplace_stable_partition() doesn't process the whole data range

[Bug libstdc++/61107] New: [4.8/4.9/4.10] stl_algo.h : std::__inplace_stable_partition() doesn't process the whole data range

[tomytsai at gmail dot com]

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

            Bug ID: 61107
           Summary: [4.8/4.9/4.10] stl_algo.h :
                    std::__inplace_stable_partition() doesn't process the
                    whole data range
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tomytsai at gmail dot com

In GCC 4.8.2 / 4.9 (20140430 snapsot) / 4.10.0 (20140504 snapshot)

If we test the following code:

  auto vec = vector<int> {1, 0, 1}
  auto cmp = [] (int v) {return v == 0;};
  std::__inplace_stable_partition( begin(vec), cmp, vec.size() )

  final vec == {1, 0, 1}
  (the expected result is {0, 1, 1})

It is because of the following line in stl_algo.h :
__inplace_stable_partition()

(from
http://gcc.gnu.org/onlinedocs/gcc-4.9.0/libstdc++/api/a01499_source.html#l01519)

1531  _ForwardIterator __right_split =
1532  std::__find_if_not_n(__middle, __right_len, __pred);
1533  if (__right_len)
1534  __right_split = std::__inplace_stable_partition(__middle,
1535  __pred,
1536  __right_len);

In line 1534, __middle should be replaced with __right_split. Otherwise,
the recursive call will start from __middle, with the updated __right_len
(modified by __find_if_not_n() ), That is, if  __find_if_not_n()  reduces
__right_len , some of the tailing data will leave unprocessed by 
the current function.

Note this problem is not critical because:

1. The corresponding function __stable_partition_adaptive() has the right
   logic (it uses __right_split instead of __middle ). Maybe someone forgot
   to update __inplace_stable_partition() when he/she updated 
   __stable_partition_adaptive().

2. This function is only called when the available buffer size is 0. Otherwise,
   __stable_partition_adaptive() will be called and it has mirrored all the 
   codes from __stable_partition_adaptive(), with the correct logic.

However it is still good to patch this bug. We can do either
   1. Replace the __middle with __right_split , as shown above.
or 2. From stable_partition() , call __stable_partition_adaptive() exclusively.
      This way we can totally remove __inplace_stable_partition(), as 
      __stable_partition_adaptive() is doing the same thing if the memory is 
      not enough (or totally not available).

Thanks!

Tomy

[Bug libstdc++/61107] stl_algo.h: std::__inplace_stable_partition() doesn't process the whole data range

[fdumont at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61107

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2014-10-08
                 CC|                            |fdumont at gcc dot gnu.org
           Assignee|unassigned at gcc dot gnu.org      |fdumont at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from François Dumont <fdumont at gcc dot gnu.org> ---
There is indeed a bug, thanks for the report.
>From gcc-bugs-return-463607-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Oct 08 22:54:06 2014
Return-Path: <gcc-bugs-return-463607-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 18274 invoked by alias); 8 Oct 2014 22:54:06 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 18244 invoked by uid 48); 8 Oct 2014 22:54:02 -0000
From: "bergner at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/63491] New: Ice in LRA with simple vector test case on power
Date: Wed, 08 Oct 2014 22:54:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: bergner at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter
Message-ID: <bug-63491-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-10/txt/msg00628.txt.bz2
Content-length: 4452

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63491

            Bug ID: 63491
           Summary: Ice in LRA with simple vector test case on power
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: bergner at gcc dot gnu.org

The following test case causes an ICE in LRA using trunk:

[bergner@makalu-lp1 LRA]$ cat pack01.i 
typedef __int128_t __attribute__((__vector_size__(16))) vector_128_t;
typedef unsigned long long scalar_64_t;
void bar (vector_128_t);

void
foo (void)
{
  union {
    scalar_64_t i64[2];
    vector_128_t v128;
  } u;
  u.i64[0] = 1;
  u.i64[1] = 2;
  bar (u.v128);
}
[bergner@makalu-lp1 LRA]$
/home/bergner/gcc/build/gcc-fsf-mainline-bootstrap-lra-debug/gcc/xgcc
-B/home/bergner/gcc/build/gcc-fsf-mainline-bootstrap-lra-debug/gcc/
-mcpu=power8 -O1 -S -m64 -mlra pack01.i
pack01.i: In function ‘foo’:
pack01.i:15:1: internal compiler error: in check_and_process_move, at
lra-constraints.c:1135
 }
 ^
0x1087c5e3 check_and_process_move
   
/home/bergner/gcc/gcc-fsf-mainline-bootstrap-reload/gcc/lra-constraints.c:1132
0x108845d3 curr_insn_transform
   
/home/bergner/gcc/gcc-fsf-mainline-bootstrap-reload/gcc/lra-constraints.c:3274
0x108888a3 lra_constraints(bool)
   
/home/bergner/gcc/gcc-fsf-mainline-bootstrap-reload/gcc/lra-constraints.c:4203
0x1086a163 lra(_IO_FILE*)
    /home/bergner/gcc/gcc-fsf-mainline-bootstrap-reload/gcc/lra.c:2198
0x107ecc9b do_reload
    /home/bergner/gcc/gcc-fsf-mainline-bootstrap-reload/gcc/ira.c:5311
0x107ed25f execute
    /home/bergner/gcc/gcc-fsf-mainline-bootstrap-reload/gcc/ira.c:5470


The problematic rtl sequence is setting up the parameter to the call.  After
IRA, we have the following rtl with pseudo 156 being allocated to hardreg
(pair) 10 (and 11).

(insn 12 5 13 2 (set (subreg:DI (reg/v:TI 156 [ u ]) 0)
        (const_int 1 [0x1])) pack01.i:13 534 {*movdi_internal64}
     (nil))
(insn 13 12 7 2 (set (subreg:DI (reg/v:TI 156 [ u ]) 8)
        (const_int 2 [0x2])) pack01.i:13 534 {*movdi_internal64}
     (nil))
(insn 7 13 8 2 (set (reg:V1TI 79 2)
        (subreg:V1TI (reg/v:TI 156 [ u ]) 0)) pack01.i:14 967 {*vsx_movv1ti}
     (expr_list:REG_DEAD (reg/v:TI 156 [ u ])
        (nil)))

With reload (-mno-lra), we do:

Reload 1: reload_in (V1TI) = (reg:V1TI 10 10)
        ALTIVEC_REGS, RELOAD_FOR_INPUT (opnum = 1), can't combine
        reload_in_reg: (subreg:V1TI (reg/v:TI 10 10 [orig:156 u ] [156]) 0)
        reload_reg_rtx: (reg:V1TI 79 2)
        secondary_in_reload = 0
        secondary_in_icode = reload_vsx_from_gprv1ti

which leads to:

(insn 12 5 13 2 (set (reg:DI 10 10 [ u ])
        (const_int 1 [0x1])) pack01.i:13 534 {*movdi_internal64}
     (nil))
(insn 13 12 17 2 (set (reg:DI 11 11 [orig:156 u+8 ] [156])
        (const_int 2 [0x2])) pack01.i:13 534 {*movdi_internal64}
     (nil))
(insn 17 13 8 2 (parallel [
            (set (reg:V1TI 79 2)
                (unspec:V1TI [
                        (reg:V1TI 10 10)
                    ] UNSPEC_P8V_RELOAD_FROM_GPR))
            (clobber (reg:TF 32 0))
        ]) pack01.i:14 513 {reload_vsx_from_gprv1ti}
     (nil))

...and all is fine.  However, with LRA (-mlra), we hit the assert in
check_and_process_move():

      /* Check the target hook consistency.  */
      lra_assert
        ((secondary_class == NO_REGS && sri.icode == CODE_FOR_nothing)
         || (old_sclass == NO_REGS && old_sri.icode == CODE_FOR_nothing)
         || (secondary_class == old_sclass && sri.icode == old_sri.icode));

Due to:

(gdb) p secondary_class
$1 = NO_REGS
(gdb) p (enum insn_code) sri.icode
$2 = CODE_FOR_reload_vsx_from_gprti
(gdb) p old_sclass
$3 = NO_REGS
(gdb) p (enum insn_code) old_sri.icode
$4 = CODE_FOR_reload_vsx_from_gprv1ti

The problem seems to be that LRA is trying to use
CODE_FOR_reload_vsx_from_gprti to reload the src rather than
CODE_FOR_reload_vsx_from_gprv1ti.  This is due to calling
targetm.secondary_reload() with sreg_mode (ie, TImode) rather than V1TImode
that reload is calling it with.  Shouldn't we be using V1TImode since we're
accessing src via a subreg:V1TI?

I'm marking this as an rtl issue for now, since the ICE is coming from LRA, but
I know this could end up as a target bug in the end.
>From gcc-bugs-return-463608-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Oct 08 22:55:55 2014
Return-Path: <gcc-bugs-return-463608-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 19818 invoked by alias); 8 Oct 2014 22:55:54 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 19771 invoked by uid 48); 8 Oct 2014 22:55:51 -0000
From: "bergner at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug rtl-optimization/63491] Ice in LRA with simple vector test case on power
Date: Wed, 08 Oct 2014 22:55:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: rtl-optimization
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: bergner at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cf_gcctarget cc
Message-ID: <bug-63491-4-orznqkzVNb@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-63491-4@http.gcc.gnu.org/bugzilla/>
References: <bug-63491-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-10/txt/msg00629.txt.bz2
Content-length: 631

https://gcc.gnu.org/bugzilla/show_bug.cgi?idc491

Peter Bergner <bergner at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |powerpc64-linux,
                   |                            |powerpc64le-linux
                 CC|                            |meissner at gcc dot gnu.org,
                   |                            |vmakarov at gcc dot gnu.org

--- Comment #1 from Peter Bergner <bergner at gcc dot gnu.org> ---
CCing Vlad and Mike for their input.