Re: [patch] Fix estimate number of iterations

[Daniel Berlin <dberlin at dberlin dot org>]

On Mon, 2005-09-19 at 22:01 +0200, Sebastian Pop wrote:
> Hi,
> here is a patch for restricting the computation of loop bounds to
> arrays not contained in structs.

This is not correct, unfortunately, it's not the right condition.

I imagine that if you simply change it so it only computes the estimate
if estimate_only is true, it will DTRT because we only call that on real
ARRAY_REF's.

This seems much nicer than adding a random check for VAR_DECL there :)

> Another correction to the bound estimation is that we have to check
> that the array is accessed without surrounding conditions: for
> example, in the following case it is not possible to determine a bound
> for the loop:

Well, actually, you only have to take the min of the accesses that
actually occur (which may be 0 if there is a path through which the
array is not accessed).


> 
> int A[10];
> for (i = 0; i < some_param; i++)
>   if (foo ())
>     A[i] = ...

because in the following case it is:

int A[10];
> for (i = 0; i < some_param; i++)
>   if (foo ())
>     A[i] = ...
    else
      A[i] = ....

as well as this case:


for (i = 0; i < some_param; i++)
>   if (foo ())
>     A[i+4] = ...
    else
      A[i+9] = ....

This looks like a standard MOP problem.
Just annotate the bb's with a (array name, max access index), and then
iterate computing the meet of them until it stops changing.