com.oracle.graal.phases.graph

Class SinglePassNodeIterator<T extends MergeableState<T>>

java.lang.Object

com.oracle.graal.phases.graph.SinglePassNodeIterator<T>

Type Parameters:

T - the type of MergeableState handled by this SinglePassNodeIterator

Direct Known Subclasses:

ConditionalEliminationPhase.ConditionalElimination, ValueAnchorCleanupPhase.CleanupValueAnchorsClosure

public abstract class SinglePassNodeIterator<T extends MergeableState<T>>
extends Object

A SinglePassNodeIterator iterates the fixed nodes of the graph in post order starting from its start node. Unlike in iterative dataflow analysis, a single pass is performed, which allows keeping a smaller working set of pending MergeableState. This iteration scheme requires:

• MergeableState.merge(AbstractMergeNode, List) to always return true (an assertion checks this)
• controlSplit(ControlSplitNode) to always return all successors (otherwise, not all associated EndNode will be visited. In turn, visiting all the end nodes for a given AbstractMergeNode is a precondition before that merge node can be visited)

For this iterator the CFG is defined by the classical CFG nodes ( ControlSplitNode, AbstractMergeNode ...) and the next pointers of FixedWithNextNode.

The lifecycle that single-pass node iterators go through is described in apply()

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	SinglePassNodeIterator.PathStart<U> An item queued in nodeQueue can be used to continue with the single-pass visit after the previous path can't be followed anymore.

Field Summary

Fields

Modifier and Type	Field and Description
private Deque<SinglePassNodeIterator.PathStart<T>>	nodeQueue
private Map<FixedNode,T>	nodeStates The keys in this map may be: loop-begins and loop-ends, see finishLoopEnds(LoopEndNode) forward-ends of merge-nodes, see queueMerge(EndNode)
private StartNode	start
protected T	state
private NodeBitMap	visitedEnds

Constructor Summary

Constructors

Constructor and Description
SinglePassNodeIterator(StartNode start, T initialState)

Method Summary

Modifier and Type	Method and Description
void	apply() Performs a single-pass iteration.
protected void	controlSplit(ControlSplitNode controlSplit)
protected void	end(EndNode endNode)
protected void	finished() The lifecycle that single-pass node iterators go through is described in apply()
private void	finishLoopEnds(LoopEndNode end) Once all loop-end-nodes for a given loop-node have been visited.
protected void	invoke(Invoke invoke)
private void	keepForLater(FixedNode x, T s)
protected void	loopBegin(LoopBeginNode loopBegin)
protected void	loopEnd(LoopEndNode loopEnd)
protected void	merge(AbstractMergeNode merge)
private FixedNode	nextQueuedNode() This method is invoked upon not having a (single) next FixedNode to visit.
protected abstract void	node(FixedNode node)
private T	pruneEntry(FixedNode x)
private void	queueMerge(EndNode end) Once all end-nodes for a given merge-node have been visited, that merge-node is added to the nodeQueue
private void	queueSuccessors(FixedNode x) Two methods enqueue items in nodeQueue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

visitedEnds

private final NodeBitMap visitedEnds

nodeQueue

private final Deque<SinglePassNodeIterator.PathStart<T extends MergeableState<T>>> nodeQueue

See Also:

SinglePassNodeIterator.PathStart

nodeStates

private final Map<FixedNode,T extends MergeableState<T>> nodeStates

The keys in this map may be:

• loop-begins and loop-ends, see finishLoopEnds(LoopEndNode)
• forward-ends of merge-nodes, see queueMerge(EndNode)

It's tricky to answer whether the state an entry contains is the pre-state or the post-state for the key in question, because states are mutable. Thus an entry may be created to contain a pre-state (at the time, as done for a loop-begin in apply()) only to make it a post-state soon after (continuing with the loop-begin example, also in apply()). In any case, given that keys are limited to the nodes mentioned in the previous paragraph, in all cases an entry can be considered to hold a post-state by the time such entry is retrieved.

The only method that makes this map grow is keepForLater(FixedNode, MergeableState) and the only one that shrinks it is pruneEntry(FixedNode). To make sure no entry is left behind inadvertently, asserts in finished() are in place.

start

private final StartNode start

state

protected T extends MergeableState<T> state

Constructor Detail

SinglePassNodeIterator

public SinglePassNodeIterator(StartNode start,
                              T initialState)

Method Detail

apply

public void apply()

Performs a single-pass iteration.

After this method has been invoked, the SinglePassNodeIterator instance can't be used again. This saves clearing up fields in finished(), the assumption being that this instance will be garbage-collected soon afterwards.

queueSuccessors

private void queueSuccessors(FixedNode x)

Two methods enqueue items in nodeQueue. Of them, only this method enqueues items with non-null state (the other method being queueMerge(EndNode)).

A space optimization is made: the state is cloned for all successors except the first. Given that right after invoking this method, nextQueuedNode() is invoked, that single non-cloned state instance is in effect "handed over" to its next owner (thus realizing an owner-is-mutator access protocol).

nextQueuedNode

private FixedNode nextQueuedNode()

This method is invoked upon not having a (single) next FixedNode to visit. This method picks such next-node-to-visit from nodeQueue and updates state with the pre-state for that node.

Upon reaching a AbstractMergeNode, some entries are pruned from nodeStates (ie, the entries associated to forward-ends for that merge-node).

finishLoopEnds

private void finishLoopEnds(LoopEndNode end)

Once all loop-end-nodes for a given loop-node have been visited.

• the state for that loop-node is updated based on the states of the loop-end-nodes
• entries in nodeStates are pruned for the loop (they aren't going to be looked up again, anyway)

The entries removed by this method were inserted:

• for the loop-begin, by apply()
• for loop-ends, by (previous) invocations of this method

queueMerge

private void queueMerge(EndNode end)

Once all end-nodes for a given merge-node have been visited, that merge-node is added to the nodeQueue

nextQueuedNode() is in charge of pruning entries (held by nodeStates) for the forward-ends inserted by this method.

node

protected abstract void node(FixedNode node)

end

protected void end(EndNode endNode)

merge

protected void merge(AbstractMergeNode merge)

loopBegin

protected void loopBegin(LoopBeginNode loopBegin)

loopEnd

protected void loopEnd(LoopEndNode loopEnd)

controlSplit

protected void controlSplit(ControlSplitNode controlSplit)

invoke

protected void invoke(Invoke invoke)

finished

protected void finished()

The lifecycle that single-pass node iterators go through is described in apply()

When overriding this method don't forget to invoke this implementation, otherwise the assertions will be skipped.

keepForLater

private void keepForLater(FixedNode x,
                          T s)

pruneEntry

private T pruneEntry(FixedNode x)