** Next:** Expression nodes
** Up:** Expression simplification
** Previous:** Schematic algorithm
** Contents**
** Index**

###

Data structures

In the pseudocode of Figure A.5 code fragments
are written as Java-like strings of program text (with `+`

as the
concatenation operator). In the practical implementation these are
manipulated as nodes in an
abstract syntax tree.

Access sets will probably be implemented as two separate variable sets: the
set of *uses* and the set of *defs*. A straightforward
(possibly inefficient) approach is to implement each of these two sets
using five components:

- A hash set of local variable descriptors.
- A hash set of field descriptors (which may be considered to
represent ``all instances'' of the field involved, if they are
instance variable descriptors).
- A flag specifying that ``all fields'' must be assumed to be included in
the set. If this flag is
`true`, the previous component can be ignored.
- A flag specifying ``all array elements'' must be assumed to be
included in the set.
- A flag specifying that ``all variables'' must be assumed to be included in
the set. If this flag is
`true`, all other components can be ignored.

We consider two access sets to be *dependent* if they share
a common variable (or category of variables), and at least one of the
accesses is a *def*.

To complete the *simplify* algorithm we still need to define, for each
kind of expression in the language, the relevant set of subexpressions
(enumerated in the `foreach`), and also--for dependence analysis
within expressions--the ``direct accesses associated with'' this kind
of expression.

** Next:** Expression nodes
** Up:** Expression simplification
** Previous:** Schematic algorithm
** Contents**
** Index**
Bryan Carpenter
2003-04-15