[Bug middle-end/32729] New: Loop unrolling not performed with large constant loop bound

[Bug middle-end/32729] New: Loop unrolling not performed with large constant loop bound

[scovich at gmail dot com]

Consider the following functions:

// g++ -mtune=core2 -O3 -S -dp
void loop(int* dest, int* src, int count) {
  for(int i=0; i < count; i++)
    dest[i] = src[i];
}
void loop_few(int* dest, int* src) { loop(dest, src, 8); }
void loop_many(int* dest, int* src) { loop(dest, src, 64); }

loop() unrolls 8x, as expected. loop_few() peels completely, as expected.
However, loop_many() neither peels nor unrolls. 

_Z9loop_manyPiS_:
        xorl    %edx, %edx      # 34    *movdi_xor_rex64        [length = 2]
.L47:
        movl    (%rsi,%rdx,4), %eax     # 11    *movsi_1/1      [length = 3]
        movl    %eax, (%rdi,%rdx,4)     # 12    *movsi_1/2      [length = 3]
        incq    %rdx    # 13    *adddi_1_rex64/1        [length = 3]
        cmpq    $64, %rdx       # 15    cmpdi_1_insn_rex64/1    [length = 4]
        jne     .L47    # 16    *jcc_1  [length = 2]
        rep ; ret       # 35    return_internal_long    [length = 1]            

Ideally the optimizer would unroll 8x, then notice that (count%8==0) and
eliminate the partial unroll code. However, even a stock unroll would be better
than nothing.


-- 
           Summary: Loop unrolling not performed with large constant loop
                    bound
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: scovich at gmail dot com
GCC target triplet: x86_64-linux-gnu


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

[Bug middle-end/32729] Loop unrolling not performed with large constant loop bound

[scovich at gmail dot com]

------- Comment #1 from scovich at gmail dot com  2007-07-11 16:36 -------
(In reply to comment #0)
> // g++ -mtune=core2 -O3 -S -dp
Oops... that doesn't actually unroll loop() all, though it still peels
loop_few().

Adding -funroll-loops (supposedly enabled by -O3?) unrolls loop()
Adding -funroll-all-loops does nothing

Nested loops also have issues:

void nested_loop(int* dest, int* src) {
  for(int i=0; i < 2; i++)
    for(int j=0; j < 2; j++)
      dest[4*i+j] = src[4*j+i];
}

becomes

_Z11nested_loopPiS_:
.LFB533:
        xorl    %edx, %edx      # 39    *movdi_xor_rex64        [length = 2]
.L47:
        movl    (%rsi), %ecx    # 13    *movsi_1/1      [length = 2]
        movl    %ecx, (%rdi,%rdx,4)     # 14    *movsi_1/2      [length = 3]
        movl    16(%rsi), %eax  # 15    *movsi_1/1      [length = 3]
        addq    $4, %rsi        # 17    *adddi_1_rex64/1        [length = 4]
        movl    %eax, 4(%rdi,%rdx,4)    # 16    *movsi_1/2      [length = 4]
        addq    $4, %rdx        # 18    *adddi_1_rex64/1        [length = 4]
        cmpq    $8, %rdx        # 20    cmpdi_1_insn_rex64/1    [length = 4]
        jne     .L47    # 21    *jcc_1  [length = 2]
        rep ; ret       # 40    return_internal_long    [length = 1]            


-- 


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

[Bug middle-end/32729] Regression: Loop unrolling not performed with large constant loop bound

[scovich at gmail dot com]

------- Comment #2 from scovich at gmail dot com  2007-07-11 16:37 -------
Regression: gcc-4.1.2 outputs the expected code for all test cases


-- 

scovich at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Loop unrolling not performed|Regression: Loop unrolling
                   |with large constant loop    |not performed with large
                   |bound                       |constant loop bound


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

[Bug middle-end/32729] Regression: Loop unrolling not performed with large constant loop bound

[rakdver at gcc dot gnu dot org]

------- Comment #3 from rakdver at gcc dot gnu dot org  2007-07-11 20:47 -------
Something c++ specific, when compiled by gcc, the loop is unrolled just fine.


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-07-11 20:47:54
               date|                            |


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

[Bug middle-end/32729] Regression: Loop unrolling not performed with large constant loop bound

[rakdver at gcc dot gnu dot org]

------- Comment #4 from rakdver at gcc dot gnu dot org  2007-07-11 20:56 -------
The following patch fixes the problem; I am not quite sure why this check is
there.

Index: cfghooks.c
===================================================================
*** cfghooks.c  (revision 126547)
--- cfghooks.c  (working copy)
*************** tidy_fallthru_edges (void)
*** 838,845 ****
  bool
  can_duplicate_block_p (basic_block bb)
  {
-   edge e;
-
    if (!cfg_hooks->can_duplicate_block_p)
      internal_error ("%s does not support can_duplicate_block_p",
                    cfg_hooks->name);
--- 838,843 ----
*************** can_duplicate_block_p (basic_block bb)
*** 847,858 ****
    if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
      return false;

-   /* Duplicating fallthru block to exit would require adding a jump
-      and splitting the real last BB.  */
-   e = find_edge (bb, EXIT_BLOCK_PTR);
-   if (e && (e->flags & EDGE_FALLTHRU))
-     return false;
-
    return cfg_hooks->can_duplicate_block_p (bb);
  }

--- 845,850 ----


-- 


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

[Bug rtl-optimization/32729] Regression: Loop unrolling not performed with large constant loop bound

[rakdver at gcc dot gnu dot org]

------- Comment #5 from rakdver at gcc dot gnu dot org  2007-07-12 07:36 -------
Patch: http://gcc.gnu.org/ml/gcc-patches/2007-07/msg01130.html


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2007-
                   |                            |07/msg01130.html
          Component|middle-end                  |rtl-optimization
           Keywords|                            |patch


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

[Bug rtl-optimization/32729] Regression: Loop unrolling not performed with large constant loop bound

[rakdver at gcc dot gnu dot org]

------- Comment #6 from rakdver at gcc dot gnu dot org  2007-07-12 10:24 -------
Subject: Bug 32729

Author: rakdver
Date: Thu Jul 12 10:24:19 2007
New Revision: 126576

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=126576
Log:
        PR rtl-optimization/32729
        * cfghooks.c (can_duplicate_block_p): Do not forbid duplicating blocks
        that fallthru to exit.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cfghooks.c


-- 


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

[Bug rtl-optimization/32729] [4.3 Regression] : Loop unrolling not performed with large constant loop bound

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2007-07-15 20:53 -------
Fixed.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
            Summary|Regression: Loop unrolling  |[4.3 Regression] : Loop
                   |not performed with large    |unrolling not performed with
                   |constant loop bound         |large constant loop bound
   Target Milestone|---                         |4.3.0


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