[Bug rtl-optimization/56605] New: Redundant branch introduced during loop2 phases

[Bug rtl-optimization/56605] New: Redundant branch introduced during loop2 phases

[wschmidt at gcc dot gnu.org]

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

             Bug #: 56605
           Summary: Redundant branch introduced during loop2 phases
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: wschmidt@gcc.gnu.org
                CC: bergner@vnet.ibm.com
              Host: powerpc64-unknown-linux-gnu
            Target: powerpc64-unknown-linux-gnu
             Build: powerpc64-unknown-linux-gnu


I've recently noticed that GCC commonly generates redundant branches prior to
vectorized loops, such as:

   cmpwi 7,12,0
    ...
   beq- 7,.L22
   beq- 7,.L22
   .p2align 4,,15
.L8:
    ... loop body ...

The branches first appear in the 186r.loop2_doloop debug dump:

(note 260 254 258 23 [bb 23] NOTE_INSN_BASIC_BLOCK)
(insn 258 260 259 23 (set (reg:CC 330)
        (compare:CC (subreg:SI (reg:DI 153 [ bnd.10+-4 ]) 4)
            (const_int 0 [0]))) -1
     (nil))
(jump_insn 259 258 263 23 (set (pc)
        (if_then_else (eq (reg:CC 330)
                (const_int 0 [0]))
            (label_ref 257)
            (pc))) -1
     (expr_list:REG_BR_PROB (const_int 0 [0])
        (nil))
 -> 257)
(note 263 259 261 24 [bb 24] NOTE_INSN_BASIC_BLOCK)
(insn 261 263 262 24 (set (reg:CC 331)
        (compare:CC (subreg:SI (reg:DI 153 [ bnd.10+-4 ]) 4)
            (const_int 0 [0]))) -1
     (nil))
(jump_insn 262 261 257 24 (set (pc)
        (if_then_else (eq (reg:CC 331)
                (const_int 0 [0]))
            (label_ref 257)
            (pc))) -1
     (expr_list:REG_BR_PROB (const_int 0 [0])
        (nil))
 -> 257)

Subsequently GCC removes the redundant compare, but does not remove the
redundant branch.

Simple test case to reproduce:

#define N 4000
void foo(short* __restrict sb, int* __restrict ia) {
  int i;
  for (i = 0; i < N; i++)
    ia[i] = (int) sb[i];
}

$GCC_INSTALL/bin/gcc -S -O3 -mvsx example.c

(-mvsx is necessary to vectorize the loop.  It may also be necessary to add
-mcpu=power7.)

[Bug rtl-optimization/56605] Redundant branch introduced during loop2 phases

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-03-12
     Ever Confirmed|0                           |1

[Bug rtl-optimization/56605] Redundant branch introduced during loop2 phases

[steven at gcc dot gnu.org]

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

--- Comment #1 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-12 19:54:05 UTC ---
Confirmed, compiling with -mcpu=power7 -msvx -O3 -fno-unroll-loops

Comes from here:

Breakpoint 8, doloop_modify (loop=0x3fffb5dc0ee0, desc=0x111d6d00,
doloop_seq=0x3fffb5f35780, condition=0x3fffb5fd1680, count=0x3fffb5fd16e0)
    at ../../trunk/gcc/loop-doloop.c:505
505           for (; ass; ass = XEXP (ass, 1))
(gdb) p debug_rtx(ass)
(expr_list:REG_DEP_TRUE (eq:SI (subreg:SI (reg:DI 153) 4)
        (const_int 0 [0]))
    (expr_list:REG_DEP_TRUE (eq:SI (subreg:SI (reg:DI 153) 4)
            (const_int 0 [0]))
        (nil)))
$51 = void
(gdb) 

These are the noloop_assumptions, and the same assertion appears twice.

[Bug rtl-optimization/56605] Redundant branch introduced during loop2 phases

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

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

--- Comment #2 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-12 23:00:07 UTC ---
The first assumption is recorded at loop-iv.c:2472:

Breakpoint 7, iv_number_of_iterations (loop=0x3fffb5dc0ee0,
insn=0x3fffb5db6fa8, condition=0x3fffb5fd13c8, desc=0x3fffffffdf98)
    at ../../trunk/gcc/loop-iv.c:2472
2472                      alloc_EXPR_LIST (0, assumption,
desc->noloop_assumptions);
(gdb) p assumption
$1 = (rtx) 0x3fffb5fd1410
(gdb) p debug_rtx(assumption)
(eq:SI (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ]) 4)
    (const_int 0 [0]))
$2 = void
(gdb) cont
Continuing.

The second comes from loop-iv.c:2623:
Breakpoint 8, iv_number_of_iterations (loop=0x3fffb5dc0ee0,
insn=0x3fffb5db6fa8, condition=0x3fffb5fd13c8, desc=0x3fffffffdf98)
    at ../../trunk/gcc/loop-iv.c:2623
2623                        alloc_EXPR_LIST (0, assumption,
desc->noloop_assumptions);
(gdb) p debug_rtx(assumption)
(gtu:SI (plus:SI (subreg:SI (reg:DI 163 [ ivtmp.33D.2058+-4 ]) 4)
        (const_int 1 [0x1]))
    (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ]) 4))


The second one is simplified using initial values at loop-iv.c:2777:
2777      simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
(gdb) p debug_rtx(desc->noloop_assumptions)
(expr_list:REG_DEP_TRUE (gtu:SI (plus:SI (subreg:SI (reg:DI 163 [
ivtmp.33D.2058+-4 ]) 4)
            (const_int 1 [0x1]))
        (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ]) 4))
    (expr_list:REG_DEP_TRUE (eq:SI (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ])
4)
            (const_int 0 [0]))
        (nil)))
$15 = void
(gdb) next
2778      simplify_using_initial_values (loop, IOR, &desc->infinite);
(gdb) p debug_rtx(desc->noloop_assumptions)
(expr_list:REG_DEP_TRUE (eq:SI (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ]) 4)
        (const_int 0 [0]))
    (expr_list:REG_DEP_TRUE (eq:SI (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ])
4)
            (const_int 0 [0]))
        (nil)))
$16 = void
(gdb) 

Insofar I can claim to understand loop-iv.c, this is supposed to be
cleaned up by eliminate_implied_conditions.

[Bug rtl-optimization/56605] Redundant branch introduced during loop2 phases

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

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

--- Comment #3 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-12 23:14:39 UTC ---
GCC gets to implies_p with:

Breakpoint 11, implies_p (a=0x3fffb5fd1410, b=0x3fffb5fd15c0) at
../../trunk/gcc/loop-iv.c:1499
1499      if (GET_CODE (a) == EQ)
(gdb) p debug_rtx(a)
(eq:SI (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ]) 4)
    (const_int 0 [0]))
$26 = void
(gdb) p debug_rtx(b)
(eq:SI (subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ]) 4)
    (const_int 0 [0]))
$27 = void
(gdb) 

But implies_p doesn't handle SUBREGs.  If it would allow REGs and SUBREGs
of REGs, it would fold the assumption away:

1504          if (REG_P (op0))
(gdb) p op0
$29 = (rtx) 0x3fffb5fd13e0
(gdb) p debug_rtx(op0)
(subreg:SI (reg:DI 153 [ bnd.10D.2035+-4 ]) 4)
$30 = void
(gdb) p debug_rtx(op1)
(const_int 0 [0])
$31 = void
(gdb) p debug_rtx(simplify_replace_rtx (b, op0, op1))
(const_int 1 [0x1])
$32 = void


Something like the following, perhaps?

Index: loop-iv.c
===================================================================
--- loop-iv.c   (revision 196575)
+++ loop-iv.c   (working copy)
@@ -1496,19 +1496,26 @@ implies_p (rtx a, rtx b)
   rtx op0, op1, opb0, opb1, r;
   enum machine_mode mode;

+  if (rtx_equal_p (a, b))
+    return true;
+
   if (GET_CODE (a) == EQ)
     {
       op0 = XEXP (a, 0);
       op1 = XEXP (a, 1);

-      if (REG_P (op0))
+      if (REG_P (op0)
+         || (GET_CODE (op0) == SUBREG
+             && REG_P (SUBREG_REG (op0))))
        {
          r = simplify_replace_rtx (b, op0, op1);
          if (r == const_true_rtx)
            return true;
        }

-      if (REG_P (op1))
+      if (REG_P (op1)
+         || (GET_CODE (op1) == SUBREG
+             && REG_P (SUBREG_REG (op1))))
        {
          r = simplify_replace_rtx (b, op1, op0);
          if (r == const_true_rtx)

[Bug rtl-optimization/56605] Redundant branch introduced during loop2 phases

[wschmidt at gcc dot gnu.org]

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

Bill Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot       |wschmidt at gcc dot gnu.org
                   |gnu.org                     |
   Target Milestone|---                         |4.8.1

--- Comment #4 from Bill Schmidt <wschmidt at gcc dot gnu.org> 2013-04-15 18:32:53 UTC ---
This was fixed in trunk on 2013-03-20.  Now that it's burned in for a few
weeks, I'll plan to fix it in 4.8.1 shortly, provided there are no objections.

[Bug rtl-optimization/56605] Redundant branch introduced during loop2 phases

[wschmidt at gcc dot gnu.org]

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

Bill Schmidt <wschmidt at gcc dot gnu.org> changed:

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

--- Comment #5 from Bill Schmidt <wschmidt at gcc dot gnu.org> 2013-04-23 19:49:08 UTC ---
Fixed.