[RFC] New SSA variable mapping infrastructure

[Richard Guenther]

This is an introduction to the SSA varmap infrastructure.  The
infrastructure was added to address the shortcoming that we only
can remember one user variable (name) per SSA name.  This makes
producing accurate debug information difficult.

Variable mappings build on the requirement to associate user
variables (that is, VAR_DECLs or PARAM_DECLs represented by their UID)
with values that are computed in a program.  In SSA representation
conveniently values can be mapped to SSA names which yields both a
handle for an (unchanging) value and a location for its definition.

SSA names have one associated variable, their SSA_NAME_VAR.  The
ability is added to on demand adding further variables to an SSA name
via a bitmap that is stored in a hashtable mapping SSA name version
to a bitmap of variable UIDs that at some point in the program give
a name to the SSA names value.

Throughout optimization the variable mapping of a SSA name changes
in the following occasions:
 - The SSA name is deleted.  In this case the variable mapping is
   deleted as well.
 - The SSA name is copied to another SSA name.  This relates both
   SSA names and their variable mapping becomes the union of both
   variable mappings.

New SSA names get their variable mappings initialized by either
based off an existing user variable, being initialized by copying
from another SSA name or by being defined as a result of a PHI
operation.  In the latter case its variable mapping is the
intersection of all variable mappings of the PHI arguments.

Unless we start creating/writing debug information for DECLs early,
we need to get hold of the DECLs referenced in the variable mappings.
This is done by a separate hashtable indexed by the DECL uids to not
artificially keep the referenced var list big.

At the time of going out-of SSA we need to attach the variable mapping
to the SSA name defining statement.  This is not yet implemented and
TER may require to attach the information to expression nodes instead.

During RTL optimization a reference or placeholder DECL from the
sets of associated variables will make var-tracking work as before.
Only at the time we write out debug information we will need to go
back to the variable sets and create copies of the variable location
lists for each of the variable in the associated set.  (fingers crossing,
this is all pure speculation)

Note that as opposed to the DEBUG_STMT/INSN approach this is _not_
a way we can conveniently cause values to be preserved that would
otherwise be deleted.

Note that the implementation detail that bitmaps are used is subject
to change dependent on statistical analysis how many variables are
in the mappings for typical programs.  For C I expect this number
to be pretty low making bitmaps a high overhead solution.  For C++
the story may be different.

Note that in the current implementation only the places where we
clearly lose information (DCE of a copy and substituting an inlined
PARAM_DECL for its argument) are "fixed".  The idea is to run a
(yet unimplemented) propagation pass just before out-of SSA instead
of keeping the sets propagated always.

I'll continue working on this, but any comments are welcome.  Please
also consider the different approach from Alexandre.

Thanks,
Richard.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: debug-varmap
Type: application/octet-stream
Size: 26237 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20071003/5dc2745a/attachment.obj>