[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[rakdver at gcc dot gnu dot org]

------- Comment #5 from rakdver at gcc dot gnu dot org  2005-10-09 19:35 -------
Created an attachment (id=9948)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9948&action=view)
Patch for no-overflow analysis from signedness


-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[rakdver at gcc dot gnu dot org]

------- Comment #6 from rakdver at gcc dot gnu dot org  2005-10-09 19:36 -------
With the recent changes to scev analysis that ensure that signed chrecs do not
wrap (assuming -fno-wrapv), it is fairly easy to get tree level # of iterations
analysis to use this fact, see the attached patch.

This does not directly help doloop opts that work on rtl, though.  There are
two possible solutions:

1) Rewrite the loop on tree level to a form that is easier to analyse, e.g.,
for (i = 0; i != n + 1; i++)

2) Somehow pass the information that the loop is not infinite (or even that its
control iv does not wrap) to rtl.


-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[tobi at gcc dot gnu dot org]

------- Comment #7 from tobi at gcc dot gnu dot org  2006-01-04 20:32 -------
Toon posted an updated patch here:
http://gcc.gnu.org/ml/fortran/2006-01/msg00048.html

(Toon, I had Andrew add you to the CC list, because somehow I couldn't, and I
think dicussion of the patch should either take place here or on gcc-patches,
but on the Fortran list you probably won't get far.)


-- 

tobi at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #8 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-01-04 20:55 -------
Subject: Re:  cannot determine number of iterations for loops with <=

> Toon posted an updated patch here:
> http://gcc.gnu.org/ml/fortran/2006-01/msg00048.html
> 
> (Toon, I had Andrew add you to the CC list, because somehow I couldn't, and I
> think dicussion of the patch should either take place here or on gcc-patches,
> but on the Fortran list you probably won't get far.)

there is a small mistake in my patch (and in the updated one as well) --
folded_casts is not used, the last chunk in simple_iv should be

+   if (no_overflow)
+     *no_overflow = (!folded_casts && !flag_wrapv && !TYPE_UNSIGNED (type));

I will test and submit the corrected patch.


-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[rakdver at gcc dot gnu dot org]

------- Comment #9 from rakdver at gcc dot gnu dot org  2006-01-06 20:23 -------
Subject: Bug 18527

Author: rakdver
Date: Fri Jan  6 20:22:56 2006
New Revision: 109427

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=109427
Log:
        PR tree-optimization/18527
        * tree-ssa-loop-niter.c (number_of_iterations_cond,
        number_of_iterations_special, number_of_iterations_exit):
        Move base and step of an iv to a single structure.  Add
        no_overflow flag, and use it in # of iterations analysis.
        * tree-scalar-evolution.c (analyze_scalar_evolution_in_loop): Add
        folded_casts argument.
        (simple_iv): Pass base and step in a structure.  Set no_overflow
        flag.
        (scev_const_prop): Add argument to analyze_scalar_evolution_in_loop.
        Evaluate expensiveness of computing # of iterations instead of
        the final expression.
        * tree-scalar-evolution.h (affine_iv): New structure.
        (simple_iv): Declaration changed.
        * tree-chrec.c (chrec_apply): Handle chrecs containing symbols.
        * tree-ssa-loop-ivopts.c (determine_biv_step, find_givs_in_stmt_scev,
        find_givs_in_stmt): Changed due to simple_iv change.

        * gcc.dg/tree-ssa/loop-15.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-15.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-chrec.c
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-scalar-evolution.h
    trunk/gcc/tree-ssa-loop-ivopts.c
    trunk/gcc/tree-ssa-loop-niter.c


-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[pinskia at gcc dot gnu dot org]

------- Comment #10 from pinskia at gcc dot gnu dot org  2006-01-07 16:03 -------
Fixed for 4.2.0.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.2.0


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[pbrook at gcc dot gnu dot org]

------- Comment #11 from pbrook at gcc dot gnu dot org  2006-04-02 13:19 -------
Subject: Bug 18527

Author: pbrook
Date: Sun Apr  2 13:19:15 2006
New Revision: 112622

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=112622
Log:
2006-04-02  Paul Brook  <paul@codesourcery.com>

        Backport form mainline.
        * gcc/testsuite/gcc.c-torture/execute/loop-ivopts-3.c: New test.

        2006-01-14  Zdenek Dvorak <dvorakz@suse.cz>
        * gcc/tree-ssa-loop-niter.c (number_of_iterations_cond): Split into
        several functions.
        (number_of_iterations_ne, number_of_iterations_lt_to_ne,
        assert_no_overflow_lt, assert_loop_rolls_lt, number_of_iterations_lt,
        number_of_iterations_le): New functions.
        (number_of_iterations_special): Removed.
        (number_of_iterations_exit): Do not use number_of_iterations_special.
        * gcc/tree.c (unsigned_type_for): Always return integer type.
        * gcc/testsuite/gcc.dg/tree-ssa/pr19210-1.c: Update outcome.
        Add new test loop.
        * gcc/testsuite/gcc.dg/tree-ssa/pr19210-2.c: Ditto.

        2005-01-06  Zdenek Dvorak <dvorakz@suse.cz>
        PR tree-optimization/18527
        * gcc/tree-ssa-loop-niter.c (number_of_iterations_cond,
        number_of_iterations_special, number_of_iterations_exit):
        Move base and step of an iv to a single structure.  Add
        no_overflow flag, and use it in # of iterations analysis.
        * gcc/tree-scalar-evolution.c (analyze_scalar_evolution_in_loop): Add
        folded_casts argument.
        (simple_iv): Pass base and step in a structure.  Set no_overflow
        flag.
        (scev_const_prop): Add argument to analyze_scalar_evolution_in_loop.
        Evaluate expensiveness of computing # of iterations instead of
        the final expression.
        * gcc/tree-scalar-evolution.h (affine_iv): New structure.
        (simple_iv): Declaration changed.
        * gcc/tree-chrec.c (chrec_apply): Handle chrecs containing symbols.
        * gcc/tree-ssa-loop-ivopts.c (determine_biv_step,
        find_givs_in_stmt_scev, find_givs_in_stmt): Changed due to simple_iv
        change.


Added:
   
branches/csl/sourcerygxx-4_1/gcc/testsuite/gcc.c-torture/execute/loop-ivopts-3.c
Modified:
    branches/csl/sourcerygxx-4_1/ChangeLog.csl
    branches/csl/sourcerygxx-4_1/gcc/testsuite/gcc.dg/tree-ssa/pr19210-1.c
    branches/csl/sourcerygxx-4_1/gcc/testsuite/gcc.dg/tree-ssa/pr19210-2.c
    branches/csl/sourcerygxx-4_1/gcc/tree-chrec.c
    branches/csl/sourcerygxx-4_1/gcc/tree-scalar-evolution.c
    branches/csl/sourcerygxx-4_1/gcc/tree-scalar-evolution.h
    branches/csl/sourcerygxx-4_1/gcc/tree-ssa-loop-ivopts.c
    branches/csl/sourcerygxx-4_1/gcc/tree-ssa-loop-niter.c
    branches/csl/sourcerygxx-4_1/gcc/tree.c


-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[pbrook at gcc dot gnu dot org]

------- Comment #12 from pbrook at gcc dot gnu dot org  2006-04-04 17:40 -------
Subject: Bug 18527

Author: pbrook
Date: Tue Apr  4 17:40:00 2006
New Revision: 112675

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=112675
Log:
2006-04-04  Paul Brook  <paul@codesourcery.com>

        Backport form mainline.
gcc/
        2006-01-14  Zdenek Dvorak <dvorakz@suse.cz>
        * tree-ssa-loop-niter.c (number_of_iterations_cond): Split into several
        functions.
        (number_of_iterations_ne, number_of_iterations_lt_to_ne,
        assert_no_overflow_lt, assert_loop_rolls_lt, number_of_iterations_lt,
        number_of_iterations_le): New functions.
        (number_of_iterations_special): Removed.
        (number_of_iterations_exit): Do not use number_of_iterations_special.
        * tree.c (unsigned_type_for): Always return integer type.

        2005-01-06  Zdenek Dvorak <dvorakz@suse.cz>
        PR tree-optimization/18527
        * tree-ssa-loop-niter.c (number_of_iterations_cond,
        number_of_iterations_special, number_of_iterations_exit):
        Move base and step of an iv to a single structure.  Add
        no_overflow flag, and use it in # of iterations analysis.
        * tree-scalar-evolution.c (analyze_scalar_evolution_in_loop): Add
        folded_casts argument.
        (simple_iv): Pass base and step in a structure.  Set no_overflow
        flag.
        (scev_const_prop): Add argument to analyze_scalar_evolution_in_loop.
        Evaluate expensiveness of computing # of iterations instead of
        the final expression.
        * tree-scalar-evolution.h (affine_iv): New structure.
        (simple_iv): Declaration changed.
        * tree-chrec.c (chrec_apply): Handle chrecs containing symbols.
        * tree-ssa-loop-ivopts.c (determine_biv_step, find_givs_in_stmt_scev,
        find_givs_in_stmt): Changed due to simple_iv change.

gcc/testsuite/
        * gcc.c-torture/execute/loop-ivopts-3.c: New test.

        2005-01-14  Zdenek Dvorak <dvorakz@suse.cz>
        * gcc.dg/tree-ssa/pr19210-1.c: Update outcome.  Add new test loop.
        * gcc.dg/tree-ssa/pr19210-2.c: Ditto.



Added:
    branches/gcc-4_1-branch/gcc/testsuite/gcc.c-torture/execute/loop-ivopts-3.c
Modified:
    branches/gcc-4_1-branch/gcc/ChangeLog
    branches/gcc-4_1-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/tree-ssa/pr19210-1.c
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/tree-ssa/pr19210-2.c
    branches/gcc-4_1-branch/gcc/tree-chrec.c
    branches/gcc-4_1-branch/gcc/tree-scalar-evolution.c
    branches/gcc-4_1-branch/gcc/tree-scalar-evolution.h
    branches/gcc-4_1-branch/gcc/tree-ssa-loop-ivopts.c
    branches/gcc-4_1-branch/gcc/tree-ssa-loop-niter.c
    branches/gcc-4_1-branch/gcc/tree.c


-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-20 17:51 -------
This is fixed with -funsafe-loop-optimizations but there are still some opions needing if it should be 
on by default at -O2/-O3 or not.

-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[pinskia at gcc dot gnu dot org]

-- 
Bug 18527 depends on bug 19210, which changed state.

Bug 19210 Summary: not using do-loop for some loops
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19210

           What    |Old Value                   |New Value
----------------------------------------------------------------------------
             Status|SUSPENDED                   |ASSIGNED
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[irar at il dot ibm dot com]

------- Additional Comments From irar at il dot ibm dot com  2005-03-09 06:56 -------
New testcase added: vect-3.f90 (in autovect branch for now).
If this PR is solved, testcase vect-3.f90 will be vectorized.

-- 


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

[Bug tree-optimization/18527] cannot determine number of iterations for loops with <=

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-16 03:37 -------
Also related to PR 19210 where we don't use bdnz because we don't know if the loop is finite.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |19210
   Last reconfirmed|2004-11-17 15:36:55         |2005-02-16 03:37:30
               date|                            |


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