[Bug middle-end/26900] New: Number of iterations not know for simple loop

[Bug middle-end/26900] New: Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

int foo0(int i0, int i1)
{
  int i, j = 0;
  for (i=i0; i<=i1+1; ++i)
    ++j;
  return j;
}

we cannot figure out the number of iterations for this loop because of
PR26898 and PR26899.


-- 
           Summary: Number of iterations not know for simple loop
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org
 BugsThisDependsOn: 26898,26899


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2006-03-28 15:13 -------
Note that we in principle know the number of iterations - just we cannot prove
the loop runs at least once in number of iterations analysis.  Of course we
know this because we did loop header copying on the loop and no other pass
interfered with this.  Maybe we should remember the BB of the loop header copy
so we can verify
later that it still dominates the loop header.  This would avoid needing to
deal
with symbolic range simplification like in PR26899.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sebastian dot pop at cri dot
                   |                            |ensmp dot fr


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2006-03-28 15:14 -------
Zdenek may also have an idea on this.


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2006-03-28 15:16 -------
Eh, of course we don't preserve loop information beyond CH.  But if we did,
this would be possible?


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rakdver at gcc dot gnu dot org]

------- Comment #4 from rakdver at gcc dot gnu dot org  2006-03-29 01:03 -------
(In reply to comment #1)
> Note that we in principle know the number of iterations - just we cannot prove
> the loop runs at least once in number of iterations analysis.  Of course we
> know this because we did loop header copying on the loop and no other pass
> interfered with this.  Maybe we should remember the BB of the loop header copy
> so we can verify
> later that it still dominates the loop header.

I do not see much difference wrto the current system (where we simply check all
blocks that dominate the loop header); checking just the one known to be the
copy of the original header would be a bit more efficient, but it might also
cause us to miss some opportunities to learn something about the bounds of the
loop from the other conditions.

I do not think remembering what the copied loop header is affects the need to
deal with symbolic range simplification in any way.  I think I can however
improve the # of iterations analysis to be less demanding to fold, though.


-- 

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         |2006-03-29 01:03:55
               date|                            |


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2006-03-29 08:01 -------
I thought if we know that we are looking at the loop header copy condition that
we _know_ that the loop runs at least once, so we can avoid trying to prove
that again using fold.


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

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

------- Comment #6 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-03-29 09:01 -------
Subject: Re:  Number of iterations not know for simple loop

> I thought if we know that we are looking at the loop header copy condition that
> we _know_ that the loop runs at least once, so we can avoid trying to prove
> that again using fold.

How?


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

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

------- Comment #7 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-03-29 09:11 -------
Subject: Re:  Number of iterations not know for simple loop

> > I thought if we know that we are looking at the loop header copy condition that
> > we _know_ that the loop runs at least once, so we can avoid trying to prove
> > that again using fold.
> 
> How?

Sorry for the dumb question, I now understand what you mean.  Let me
think about this for a moment, please.


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2006-03-29 15:45 -------
Created an attachment (id=11154)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11154&action=view)
patch

I have a simple patch for # iterations analysis to check whether either cond1
follows from cond2 or !cond1 follows from cond2.

Patch is untested but fixes the testcase.


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[patchapp at dberlin dot org]

------- Comment #9 from patchapp at dberlin dot org  2006-03-30 09:15 -------
Subject: Bug number PR26900

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-03/msg01736.html


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rakdver at gcc dot gnu dot org]

------- Comment #10 from rakdver at gcc dot gnu dot org  2006-04-02 16:04 -------
(In reply to comment #7)
> Subject: Re:  Number of iterations not know for simple loop
> 
> > > I thought if we know that we are looking at the loop header copy condition that
> > > we _know_ that the loop runs at least once, so we can avoid trying to prove
> > > that again using fold.
> > 
> > How?
> 
> Sorry for the dumb question, I now understand what you mean.  Let me
> think about this for a moment, please.

I think the basic idea is OK, although one needs to be a bit careful, at least
with the following details:

1) Loops with multiple exits -- one would have to record the fact whether the
condition was duplicated or not for each exit separately.

2) One would need to restrict this for "nice" induction variables; e.g., a loop
like this one:

int i, x, n;
int a[10];

for (i = 0, x = -100; x < n; i++, x = (int) (unsigned char) x + 1)
  a[i] = x;


becomes

x = -100;
i = 0;
if (-100 < n)
  do
    {
      a[i] = x;
      i++;
      x = (int) (unsigned char) x + 1
    }
   while (x < n)

Now, the variable x in the compare x < n has evolution {156, +, 1} (the loop
contains enough information to infer this, although we currently are not be
able to do it), and we must check for n >= 156 in may_be_zero.

>Maybe we should remember the BB of the loop header copy so we can verify
>later that it still dominates the loop header.

Checking that it still dominates the loop header should not be neccessary, just
the fact that it was copied should matter.


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[sebastian dot pop at cri dot ensmp dot fr]

------- Comment #11 from sebastian dot pop at cri dot ensmp dot fr  2006-06-19 07:50 -------
Subject: Re:  Number of iterations not know for simple loop

I thought that this bug should have been fixed by now:
http://gcc.gnu.org/ml/gcc-patches/2006-03/msg01749.html
what is the status of that patch?


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2006-06-19 09:25 -------
Roger requested this do be done differently by canonicalizing comparisons in
fold and using an improved operand_equal_p to do this.  Patches for this are
done, but need to wait for stage1.


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2006-10-28 18:22 -------
Now that we do all possible canonicalization we still can not figure out # of
iterations here.

I'm revisiting the proposed patch for this PR and am going to attack
tree-ssa-loop-niter.c:simplify_using_initial_conditions again.

(Zdenek, I hope you don't mind if I take this bug from you again ;))


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|rakdver at gcc dot gnu dot  |rguenth at gcc dot gnu dot
                   |org                         |org


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2007-01-24 14:59 -------
I'm not working on this one.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|rguenth at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rakdver at gcc dot gnu dot org]

------- Comment #15 from rakdver at gcc dot gnu dot org  2007-02-10 20:07 -------
Patch: http://gcc.gnu.org/ml/gcc-patches/2007-02/msg00931.html


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[rakdver at gcc dot gnu dot org]

------- Comment #16 from rakdver at gcc dot gnu dot org  2007-03-14 00:39 -------
Subject: Bug 26900

Author: rakdver
Date: Wed Mar 14 00:38:34 2007
New Revision: 122896

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=122896
Log:
        PR tree-optimization/30730
        PR tree-optimization/26900
        * tree-ssa-loop-niter.c: Include gmp.h.
        (bounds): New type.
        (mpz_set_double_int, get_type_bounds, mpz_to_double_int,
        split_to_var_and_offset, determine_value_range,
        bound_difference_of_offsetted_base, refine_bounds_using_guard,
        bound_difference, bounds_add, bounds_negate,
        number_of_iterations_ne_max, dump_affine_iv): New functions.
        (number_of_iterations_ne, number_of_iterations_lt_to_ne,
        assert_loop_rolls_lt, assert_loop_rolls_le): Use bounds on the
        difference of initial and final value of control iv to validate
        results.
        (number_of_iterations_cond): Add loop parameter.  Determine bounds
        on the difference of the extremes of the control iv.  Add dumps.
        (expand_simple_operations): Handle phi nodes.
        (simplify_using_initial_conditions): Do not record used conditions.
        (number_of_iterations_exit): Pass loop to number_of_iterations_cond.
        Do not set additional_info.
        (implies_nonnegative_p, implies_ge_p): Removed.
        (derive_constant_upper_bound): Do not use parameter `additional'.
        (record_estimate): Parameter `additional' removed.  Parameter
        `i_bound' added.  Do not call derive_constant_upper_bound.
        (record_nonwrapping_iv): Use derive_constant_upper_bound to
        bound the number of iterations estimate.
        (estimate_numbers_of_iterations_loop): Pass the estimate from
        the number of iterations analysis to record_estimate.
        * tree.h (multiple_of_p): Declare.
        * tree-scalar-evolution.c (expression_expensive_p): Removed.
        (scev_const_prop): Do not check expression_expensive_p.
        * fold-const.c (multiple_of_p): Exported.
        * double-int.c (double_int_mask): Exported.
        * double-int.h (double_int_mask): Declare.
        * tree-flow.h (struct tree_niter_desc): Removed additional_info
        field.  Added max field.

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


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-26.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/double-int.c
    trunk/gcc/double-int.h
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-scalar-evolution.c
    trunk/gcc/tree-ssa-loop-niter.c
    trunk/gcc/tree.h


-- 


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

[Bug middle-end/26900] Number of iterations not know for simple loop

[spop at gcc dot gnu dot org]

------- Comment #17 from spop at gcc dot gnu dot org  2007-07-10 08:30 -------
Fixed.


-- 

spop at gcc dot gnu dot org changed:

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


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