[graphite] instancewise dependence analysis functions and structures

[Sebastian Pop]

On Thu, Feb 21, 2008 at 11:25 AM, Konrad Trifunovic
<konrad.trifunovic@gmail.com> wrote:
> Hi,
>
>  I have added an additional boolean parameter to dr_analyze_indices
>  called outer_loop_evolutions.
>
>
>  For the following loop nest:
>
>   for (i=0;i<100;i++)
>   {
>     for (j = 5;j < 100;j++)
>     {
>       ... = A[i][j-1];
>     }
>   }
>
>  Default behavior was to analyze the evolution of access function with respect
>  to the innermost loop enclosing the statement, so the result was the following
>  ( as You can see, the access function with respect to 'i' loop is
>  constant here):
>

The evolution of "i" in the innermost loop should be {0, +, 1}_1, and
the evolution of "j" in the innermost loop should be {5, +, 1}_2.
They should not be constant.

>
>  (Data Ref:
>   stmt: D.1562_11 = A[i_46][D.1561_10];
>   ref: A[i_46][D.1561_10];
>   base_object: A[0][0];
>   Access function 0: {4, +, 1}_2
>   Access function 1: 99
>  )
>  (Data Ref:
>   stmt: A[i_46][j_48] = D.1562_11;
>   ref: A[i_46][j_48];
>   base_object: A[0][0];
>   Access function 0: {5, +, 1}_2
>   Access function 1: 99
>  )
>

This looks suspiciously wrong, and I cannot really tell what went
wrong.

The access functions look like the analysis has been done in the loop
around the loop that iterates on i: the 99 is the value of i after
exiting the outermost loop.

Could you send me a preprocessed source file where you see this
happening?

Thanks,
Sebastian

PS: The patch that you sent does not seem to be the right approach.
In particular, this part of the patch does not seem correct:

> @@ -751,6 +752,11 @@ dr_analyze_indices (struct data_referenc
>        if (TREE_CODE (aref) == ARRAY_REF)
>  	{
>  	  op = TREE_OPERAND (aref, 1);
> +          if (outer_loop_evolutions && TREE_CODE (op) == SSA_NAME)
> +          {
> +            tree def_stmt = SSA_NAME_DEF_STMT (op);
> +            loop = loop_containing_stmt (def_stmt);
> +          }
>  	  access_fn = analyze_scalar_evolution (loop, op);
>  	  access_fn = resolve_mixers (nest, access_fn);
>  	  VEC_safe_push (tree, heap, access_fns, access_fn);

We really want to analyze the array indexes in the innermost loop and
not in outer loops.