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:

1. A hash set of local variable descriptors.
2. A hash set of field descriptors (which may be considered to represent ``all instances'' of the field involved, if they are instance variable descriptors).
3. 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.
4. A flag specifying ``all array elements'' must be assumed to be included in the set.
5. 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.