[Bug middle-end/45098] New: Missed induction variable optimization

[Bug middle-end/45098] New: Missed induction variable optimization

[carrot at google dot com]

Compile the following code with options -march=armv7-a -mthumb -Os

extern void foo(int*);
void tr(int array[], int n)
{
  int i;
  for (i=0; i<n; i++)
    foo(&array[i]);
}

GCC 4.6 generates:

        push    {r4, r5, r6, lr}
        mov     r6, r1
        mov     r5, r0
        movs    r4, #0
        b       .L2
.L3:
        mov     r0, r5
        adds    r4, r4, #1
        bl      foo
        adds    r5, r5, #4
.L2:
        cmp     r4, r6
        blt     .L3
        pop     {r4, r5, r6, pc}

We can see that both r4 and r5 are loop induction variables, and r4 is used for
loop counter only. So we can transform it to

        push    {r4, r5, r6, lr}
        mov     r5, r0
        add     r6, r5, r1 << 2
        b       .L2
.L3:
        mov     r0, r5
        bl      foo
        adds    r5, r5, #4
.L2:
        cmp     r5, r6
        blt     .L3
        pop     {r4, r5, r6, pc}

This new code is shorter and faster than original result, it uses one less
register at the same time.

Both tree-ssa and rtl loop optimizations missed this optimization.


-- 
           Summary: Missed induction variable optimization
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: carrot at google dot com
 GCC build triplet: i686-linux
  GCC host triplet: i686-linux
GCC target triplet: arm-eabi


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

[Bug middle-end/45098] Missed induction variable optimization

[davidxl at gcc dot gnu dot org]

------- Comment #1 from davidxl at gcc dot gnu dot org  2010-07-30 17:23 -------
Seems -Os specific -- also reproducible on x86. With -O2, the result is
expected.

David


-- 

davidxl at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |davidxl at gcc dot gnu dot
                   |                            |org


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

[Bug middle-end/45098] Missed induction variable optimization

[ramana at gcc dot gnu dot org]

-- 

ramana at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2010-08-02 07:55:00
               date|                            |


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

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

vries at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
            Version|4.6.0                       |4.7.0
         Resolution|                            |FIXED
   Target Milestone|---                         |3.1.x/3.2.x

--- Comment #18 from vries at gcc dot gnu.org 2011-07-11 16:31:56 UTC ---
All ivopts improvements related to this example for -march=armv7-a -mthumb -Os
are committed to trunk. Regression test are in place. Closing bug.

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #17 from vries at gcc dot gnu.org 2011-06-16 18:00:57 UTC ---
Author: vries
Date: Thu Jun 16 18:00:54 2011
New Revision: 175106

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=175106
Log:
2011-06-16  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * gcc.target/arm/ivopts-3.c: Update test.
    * gcc.target/arm/ivopts-5.c: Same.

Modified:
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.target/arm/ivopts-3.c
    trunk/gcc/testsuite/gcc.target/arm/ivopts-5.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #16 from vries at gcc dot gnu.org 2011-06-16 17:57:12 UTC ---
Author: vries
Date: Thu Jun 16 17:57:08 2011
New Revision: 175105

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=175105
Log:
2011-06-16  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Disallow
    NULL pointer for pointer arithmetic.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-niter.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #15 from vries at gcc dot gnu.org 2011-06-14 15:05:29 UTC ---
Author: vries
Date: Tue Jun 14 15:05:26 2011
New Revision: 175025

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=175025
Log:
2011-06-14  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * gcc.target/arm/ivopts-3.c: New test.
    * gcc.target/arm/ivopts-4.c: New test.
    * gcc.target/arm/ivopts-5.c: New test.

Added:
    trunk/gcc/testsuite/gcc.target/arm/ivopts-3.c
    trunk/gcc/testsuite/gcc.target/arm/ivopts-4.c
    trunk/gcc/testsuite/gcc.target/arm/ivopts-5.c
Modified:
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #14 from vries at gcc dot gnu.org 2011-06-14 14:30:01 UTC ---
Author: vries
Date: Tue Jun 14 14:29:58 2011
New Revision: 175022

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=175022
Log:
2011-06-14  Zdenek Dvorak  <ook@ucw.cz>
        Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * cfgloop.h (nb_iterations_upper_bound, nb_iterations_estimate):
    Document changed semantics.
    (max_stmt_executions, max_stmt_executions_int): Declare.
    * tree-data-ref.c (estimated_loop_iterations)
    (estimated_loop_iterations_int): Move functions...
    * tree-ssa-loop-niter.c (estimated_loop_iterations)
    (estimated_loop_iterations_int): here.
    (record_estimate): Change nb_iterations_upper_bound and
    nb_iterations_estimate semantics.
    (max_stmt_executions, max_stmt_executions_int): New function.
    * tree-data-ref.c (estimated_loop_iterations_tree): Rename to ...
    (max_stmt_executions_tree): this.
    (analyze_miv_subscript): Use max_stmt_executions_tree instead of
    estimated_loop_iterations_tree.
    tree-ssa-loop-ivopts.c (avg_loop_niter): Use
    max_stmt_executions_int instead of estimated_loop_iterations_int.
    * predict.c (predict_loops): Idem.
    * tree-parloops.c (parallelize_loops): Idem.
    * tree-data-ref.c (analyze_siv_subscript_cst_affine)
    (compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine)
    (init_omega_for_ddr_1): Idem.
    * tree-ssa-loop-prefetch.c (determine_loop_nest_reuse)
    (loop_prefetch_arrays): Idem
    * graphite-sese-to-poly.c (build_loop_iteration_domains): Use
    max_stmt_executions instead of estimated_loop_iterations.
    * tree-data-ref.c (estimated_loop_iterations_tree): Idem.
    * tree-vrp.c (adjust_range_with_scev): Use estimated_loop_iterations
    instead of nb_iterations_upper_bound.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cfgloop.h
    trunk/gcc/graphite-sese-to-poly.c
    trunk/gcc/predict.c
    trunk/gcc/tree-data-ref.c
    trunk/gcc/tree-parloops.c
    trunk/gcc/tree-ssa-loop-ivopts.c
    trunk/gcc/tree-ssa-loop-niter.c
    trunk/gcc/tree-ssa-loop-prefetch.c
    trunk/gcc/tree-vrp.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #13 from vries at gcc dot gnu.org 2011-06-04 08:42:29 UTC ---
> Tom can this now be marked as being fixed for 4.7.0 ?

I'm still discussing one patch with Zdenek. Latest gcc-patches mail on this is
http://gcc.gnu.org/ml/gcc-patches/2011-05/msg02384.html.

[Bug middle-end/45098] Missed induction variable optimization

[ramana at gcc dot gnu.org]

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

Ramana Radhakrishnan <ramana at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ramana at gcc dot gnu.org,
                   |                            |vries at gcc dot gnu.org

--- Comment #12 from Ramana Radhakrishnan <ramana at gcc dot gnu.org> 2011-06-04 08:20:52 UTC ---
Tom can this now be marked as being fixed for 4.7.0 ?

Ramana

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #11 from vries at gcc dot gnu.org 2011-05-23 07:28:03 UTC ---
Author: vries
Date: Mon May 23 07:27:59 2011
New Revision: 174056

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174056
Log:
2011-05-23  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): New
    function.
    (infer_loop_bounds_from_undefined): Use new function.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-niter.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #10 from vries at gcc dot gnu.org 2011-05-23 07:00:07 UTC ---
Author: vries
Date: Mon May 23 07:00:02 2011
New Revision: 174055

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174055
Log:
2011-05-23  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * gcc.target/arm/ivopts-6.c: New test.

Added:
    trunk/gcc/testsuite/gcc.target/arm/ivopts-6.c
Modified:
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #9 from vries at gcc dot gnu.org 2011-05-22 19:57:22 UTC ---
Author: vries
Revision: 174033
Modified property: svn:log

Modified: svn:log at Sun May 22 19:57:20 2011
------------------------------------------------------------------------------
--- svn:log (original)
+++ svn:log Sun May 22 19:57:20 2011
@@ -1,5 +1,5 @@
 2011-05-22  Tom de Vries  <tom@codesourcery.com>

     PR target/45098
-    * tree-ssa-loop-ivopts.c (force_expr_to_var_cost): Fixed const test
+    * tree-ssa-loop-ivopts.c (force_expr_to_var_cost): Fix const test
     for call to get_shiftadd_cost.

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #8 from vries at gcc dot gnu.org 2011-05-22 18:57:21 UTC ---
Author: vries
Date: Sun May 22 18:57:19 2011
New Revision: 174033

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174033
Log:
2011-05-22  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-ivopts.c (force_expr_to_var_cost): Fixed const test
    for call to get_shiftadd_cost.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #7 from vries at gcc dot gnu.org 2011-05-20 19:32:33 UTC ---
Author: vries
Date: Fri May 20 19:32:30 2011
New Revision: 173976

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173976
Log:
2011-05-20  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-ivopts.c: Include expmed.h.
    (get_shiftadd_cost): New function.
    (force_expr_to_var_cost): Declare forward.  Use get_shiftadd_cost.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #6 from vries at gcc dot gnu.org 2011-05-19 09:33:52 UTC ---
Author: vries
Date: Thu May 19 09:33:49 2011
New Revision: 173896

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173896
Log:
2011-05-19  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * gcc.target/arm/ivopts.c: New test.
    * gcc.target/arm/ivopts-2.c: New test.

Added:
    trunk/gcc/testsuite/gcc.target/arm/ivopts-2.c
    trunk/gcc/testsuite/gcc.target/arm/ivopts.c
Modified:
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #5 from vries at gcc dot gnu.org 2011-05-19 09:03:15 UTC ---
Author: vries
Date: Thu May 19 09:03:12 2011
New Revision: 173894

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173894
Log:
2011-05-19  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-ivopts.c (get_expr_id): Factored new function out of
    get_loop_invariant_expr_id.
    (get_loop_invariant_expr_id): Use get_expr_id.
    (parm_decl_cost): New function.
    (determine_use_iv_cost_condition): Use get_expr_id and parm_decl_cost.
    Improve bound cost estimation.  Use different inv_expr_id for elim and
    express cases.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #4 from vries at gcc dot gnu.org 2011-05-19 08:49:32 UTC ---
Author: vries
Date: Thu May 19 08:49:28 2011
New Revision: 173893

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173893
Log:
2011-05-19  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-ivopts.c (determine_iv_cost): Prevent
    cost_base.cost == 0.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #3 from vries at gcc dot gnu.org 2011-05-18 18:27:15 UTC ---
Author: vries
Date: Wed May 18 18:27:11 2011
New Revision: 173872

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173872
Log:
2011-05-18  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-ivopts.c (computation_cost): Prevent cost of 0.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c

[Bug middle-end/45098] Missed induction variable optimization

[vries at gcc dot gnu.org]

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

--- Comment #2 from vries at gcc dot gnu.org 2011-05-18 10:20:59 UTC ---
Author: vries
Date: Wed May 18 10:20:55 2011
New Revision: 173853

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173853
Log:
2011-05-18  Tom de Vries  <tom@codesourcery.com>

    PR target/45098
    * tree-ssa-loop-ivopts.c (seq_cost): Fix call to rtx_cost.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c