state tracking by PostOrderNodeIterator, holding to states longer than needed

[Miguel Garcia Gutierrez]

Hi,

I was thinking about ways to lower the memory-footprint of ConditionalEliminationPhase and FlowSensitiveReductionPhase.

Both rely on PostOrderNodeIterator that tracks program-state on a per program-point basis. PostOrderNodeIterator is used to realize a single-pass visit of nodes, as opposed to multi-pass as in iterative dataflow.

(Actually, the "single-pass" property is not intrinsic to PostOrderNodeIterator, but determined by the subclass of MergeableState in use: an override of merge() that always returns true makes PostOderNodeIterator perform a single-pass visit).

Back to lowering memory-footprint. 

PostOrderNodeIterator tracks states in a map from FixedNode to state, a map that is used to grab states for loop begins and ends, for merge forward-ends, and for the predecessor of begin-nodes.

That map is cleared only at the end of the single-pass visit. However, some entries are accessed for a last time well before that. For example, after all forward-ends of a merge have been visited, which entries won't be ever looked up again?

I'm trying to visualize the above, comments are welcome!


Miguel