[RFC] Change (flatten) representation of memory references

15 msg	Wrong warning? ISO C restricts enumerator value...
1 msg	Do your research on this company PERT
4 msg	interesting case of DCE with dataflow.
3 msg	Is there summarized table of ABI binary compati...
1 msg	Is that possible not to generate duplicated err...
1 msg	gcc-4.1-20080204 is now available
1 msg	best method to implement dynamic initializers?
14 msg	c99-math execute failures on sparc-sun-solaris2.11

[RFC] Change (flatten) representation of memory...
\ Richard Guenther (4 Feb 2008)
. \ Richard Guenther (6 Feb 2008)
. . \ Eric Botcazou (6 Feb 2008)
. . . \ Richard Guenther (6 Feb 2008)
. . . . \ Eric Botcazou (6 Feb 2008)
. . . . \ (Richard Kenner) (6 Feb 2008)
. . . . . \ Richard Guenther (6 Feb 2008)
. . . . . . \ Hans-Peter Nilsson (7 Feb 2008)
. . . . . . . \ (Richard Kenner) (7 Feb 2008)
. . . . . . . . \ Sebastian Pop (7 Feb 2008)
. . . . . . . . \ Richard Guenther (7 Feb 2008)
. . . . . . . . . \ Olivier Hainque (7 Feb 2008)
. . . . . . . . \ Hans-Peter Nilsson (7 Feb 2008)
. . . . . . . . . \ Arnaud Charlet (7 Feb 2008)
. . . . . . . . . . \ Diego Novillo (7 Feb 2008)

9 msg	How to implement efficiently builtins for dual-...
7 msg	Why is DImode aligned at 8 byte for i386?
1 msg	GCC 4.2.3 Released
14 msg	Replying to a mailing list thread
2 msg	Processor for header files.
1 msg	[tuples] If you need to re-enable -O2
1 msg	4.2 branch open again
1 msg	gcc-4.3-20080201 is now available
8 msg	Some 4.4 project musings
1 msg	Adding extra instructions in the Ready List
1 msg	4.2 branch frozen

Subject:	[RFC] Change (flatten) representation of memory references
Group:	Gcc
From:	Richard Guenther
Date:	4 Feb 2008

Following the old discussions at

http://gcc.gnu.org/ml/gcc/2007-04/msg00096.html
and http://gcc.gnu.org/ml/gcc/2007-04/msg00096.html

I'd like to get the ball rolling and start implementing a
unified flattened memory access operation for 4.4. Following
my earlier proposal and keeping in mind the requirements
fulfilled by Zdeneks approach I came up with

MEM_REF ( base, offset, alias_set )
INDIRECT_MEM_REF ( base, offset, alias_set )

which has the following information:

- the BASE object with its type attached
- a gimple val OFFSET
- an alias_set_type alias_set, for TBAA and to be used in place
of the RTL MEM_REF tree
- the access type on the MEM_REF itself

This is a compact representation for all our memory reference trees.

Multi-dimensional array accesses like a.x[i][j].y would be represented
as (following Zdeneks notation)

idx_1 = IDX ( offsetof (x) + offsetof (y), j, sizeof (a.x[][j]) )
idx_2 = IDX ( idx_1, i, sizeof (a.x[i]) )
MEM_REF ( a, idx_2, 3)

introducing a new indexing operation IDX ( offset, idx, step ) effectively
capturing the information Zdenek keeps in the vector of indices in the
memory reference itself. The result is of course offset + idx * step,
so this is a multiply-add expression with non-communtative multiplication
(as we want to preserve what is index and what is step).

The advantage is that with the above form the
individual IDXes can be CSEd and moved out of loops where they are invariant
easily. The offset member of MEM_REF is not constrained to use IDX
operations, but they can be reconstructed by an analysis phase from
pointer arithmetic as well. For example for

for (i=0; i<n; ++i)
for (j=0; j<m; ++j)
*(p + j * n + i) = *(q + j * n + i);

can be transformed to

atmp_1 = (T (*)[m][n])p;
atmp_2 = (T (*)[m][n])q;
for (i=0; i<n; ++i)
{
idx_1 = IDX (0, i, sizeof(T)*m);
for (j=0; j<m; ++j)
{
idx_2 = IDX (idx_1, j, sizeof(T));
tmp_1 = INDIRECT_MEM_REF (atmp_2, idx_2, 3);
INDIRECT_MEM_REF (atmp_1, idx_2, 3) = tmp_1;
}
}

capturing the domain we loop over in the VLA type of atmp_1 and atmp_2
(that is, in the object, not the access as with Zdeneks proposal). Note
that at this point (and not only to replace RTL MEM_REF) having the
alias set encoded in the access is crucial, as dependent on the FE it
may no longer be reconstructable from the base object type and the access
type (?).

Thoughts?

Thanks,
Richard.