Proposal for reference annotations

[kenner at vlsi1 dot ultra dot nyu dot edu (Richard Kenner)]

I refined my proposal of yesterday about another way of adding the
information in ARRAY_REF and COMPONENT_REF and realized that a generalization
of it might help solve a number of other pending problems.

So my proposal is that we add an annotation mechanism for ARRAY_REF,
ARRAY_RANGE_REF, and COMPONENT_REF.  Because in most cases these fields will
be constants and usually the same for many nodes, we set up a hash table
mechanism like MEM_ATTRS and have the rule that you need to make a new one in
order to modify one. They are also always preserved and copied when the node
is copied.

The idea is that we can use this annotation to lazily and incrementally lower
a reference in stages.  That would allow us to keep high-level information
intact for the higher-level optimizations but provide a mechanism for
exposing all addressing computations in GIMPLE while not losing any data.

Each reference annotation would contain (rough proposal) the following
fields: lower bound, stride, alignment, offset, cumulative offset, cumulative
alignment, and bit offset.  tree-ssa-operands would know to look for these
and treat them as operands (except for the alignments and bit offsets, which
are not tree nodes).

During gimplification, for ARRAY_REF and ARRAY_RANGE_REF, the first three
fields would be set (as now, except that the stride can be in units of bytes
since we have the alignment it's based on).  During gimplification of
COMPONENT_REF, alignment and offset would be set, with the alignment being
set to the known alignment of the offset field.

Once some high-level optimizations have been done, we can walk the tree and
do a transformation of the ARRAY_REF (and ARRAY_RANGE_REF) nodes and compute
offset as (index - lower bound) * stride.  Once that's filled in,
tree-ssa-operands would no longer treat the index, lower bound, and stride as
operands.

A final pass could walk the tree and fill in the cumulative alignment,
cumulative offset, and bit offset from all the fields nested further down.
At this point, all of the inner offsets are no longer to be considered
operands.  This step must be done some time before RTL expansion.

So now the RTL expander will have the base address, the offset in bytes
(often a variable), a bit offset (always a constant; not even a tree), and
the alignment that the byte offset is known to have.  But it will also
have the shape of the tree for MEM_EXPR, which will also help in
the -fverbose-asm output.

Comments?