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.

Zdenek may also have an idea on this.

Eh, of course we don't preserve loop information beyond CH.  But if we did, this would be possible?

(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.

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.

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?

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.

Created attachment 11154 [details]
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.

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

(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.

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?

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.

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 ;))

I'm not working on this one.

Patch: http://gcc.gnu.org/ml/gcc-patches/2007-02/msg00931.html

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

Fixed.