Re: [RFC] Change (flatten) representation of memory references

[Zdenek Dvorak <rakdver@kam.mff.cuni.cz>]

Hi,

> I thought that special casing IDX_EXPR as a (possibly redundant) point to
> track a value range for the index (the bounds of the index are a value
> range after all) would be less nice than to have the ability to remember
> a (constant) value range for any SSA_NAME.
> 
> That is, if we would add a persistent map of SSA_NAME -> value_range
> we can store the lower/upper bounds for i_4 once we see it used as
> an array index.  (Yes, I see that we would need to defer MEM_REF lowering
> until after we go into SSA in this case, or insert ASSERT_EXPRs during
> lowering)

also, possibly quite some work to ensure that the information does not
get lost, and adding a support for persistent symbolic value ranges
for SSA names... all in all, I think having bounds in IDX_EXPR is
simpler, at least for the initial implementation.

> Other than that, extending IDX_EXPR with lower/upper value is the
> only way to keep the range information for the outermost index.  (I
> suppose for multi-dimensional accesses we can recover the range from
> the stride of the next outer IDX_EXPR, right?)

Maybe, but things become more complicated with variable-sized arrays.
I.e., if you have a[n1][n2], knowing that the range of the outermost
access is tmp (containing n1*n2 computed somewhere else in a possibly
complicated way due to expression simplification) and the stride is
n1, finding out that the range of the other index is n1 may be somewhat
difficult.

> > What about the indices whose value is a constant?  These can be
> > moved to offset, but that makes dependency analysis harder, so perhaps
> > it would make sense to make this lowering only after loop optimizations?
> 
> Constant valued indices are at the moment do not create an IDX_EXPR.
> This would be easy to change, but I thought this wouldn't complicate
> data dependency analysis (at least it shouldn't make it impossible).

How would dependency analysis know that these indices are there, and
what are their values?

> But I don't know to much about the workings of our data dependence
> analyzer.
> 
> If we defer lowering to after loop optimizatins I don't see a reason to
> keep IDX_EXPR at all?  I really like to have lowering before our usual
> memory optimizers (SCCVN and DSE for the two I looked at).

I would like to have IDX_EXPRs in the loop optimizer (but including all
the dimensions of the arrays, even those when the index is a constant).

> Looking at an actual example
> 
> float A[8][8][8];
> float B[8][8][8];
> 
> void foo(void)
> {
>   int i, j, k;
>   for (i=0; i<8; ++i)
>     for (j=0; j<8; ++j)
>       for (k=0; k<8; ++k)
>         A[i][j][k] = B[i][2][k];
> }
> 
> I see that I didn't implement constant-folding of IDX yet, or the
> lowering unconditionally emits an IDX expr in this case (possibly
> due to the non-constant offset - so we only get no IDX for constant
> innermost indices):
> 
>   D.1681 = IDX <0 + k.4 * 4>;
>   D.1682 = IDX <D.1681 + 2 * 32>;
>   D.1683 = IDX <D.1682 + i.3 * 256>;
>   D.1679 = MEM <float {0}, &B + D.1683>;
>   D.1684 = IDX <0 + k.2 * 4>;
>   D.1685 = IDX <D.1684 + j.1 * 32>;
>   D.1686 = IDX <D.1685 + i.0 * 256>;
>   MEM <float {0}, &A + D.1686> = D.1679;
> 
> does this look ok?

Yes, this (without constant-folding IDX) would work well for dependency
analysis,

Zdenek