spiglet.translate.graph
Class Liveness<T>

java.lang.Object
  spiglet.translate.graph.Liveness<T>

Type Parameters:

T - the type of the variable (member of live-in and live-out sets).

public class Liveness<T>
extends java.lang.Object

This class represents a liveness analyzer of a control flow graph. From the def and set sets of a flow graph, liveness analysis is done to generate the live-in and live-out sets of each node. This information will eventually be used to build an interference graph based on a given control flow graph.

Author:

Santoso Wijaya

See Also:

FlowGraph, InterferenceGraph, Node

Nested Class Summary

class

Liveness.LiveRange Defines the data structure for a live range of a variable, with the natural ordering based on start point.

Constructor Summary

Liveness(FlowGraph<T> graph)
Analyze the given flow graph for liveness of variables along its edges.

Method Summary

protected java.util.Set<T>	getInSet(Node n) Returns the (modifiable) live-in set of a node.
java.util.Set<Liveness.LiveRange>	getLiveRanges() Returns the set of variable live ranges (as encoded in the wrapper).
java.util.Set<T>	getOutSet(Node n) Returns the (unmodifiable) live-out set of a node.
java.lang.String	toString() Returns a multi-line string representation of each node's live-in and live-out sets, each line in the form: [#] [live-in={?,?,...,?.}, live-out={?,?,...,?,}].

Methods inherited from class java.lang.Object

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

Constructor Detail

Liveness

public Liveness(FlowGraph<T> graph)

Analyze the given flow graph for liveness of variables along its edges. The analysis encoded in an object of this class can eventually be used to produce an interference graph, or in a linear scan algorithm.

Parameters:

graph - the control flow graph

Method Detail

getInSet

protected java.util.Set<T> getInSet(Node n)

Returns the (modifiable) live-in set of a node. This set contains the variables that are live along the edge coming into the given node. Pre-condition: n exists in the given flow graph.

Parameters:

n - the node to look up

Returns:

the live-in set of the node

getOutSet

public java.util.Set<T> getOutSet(Node n)

Returns the (unmodifiable) live-out set of a node. This set contains the variables that are live along the edge going out of the given node. Pre-condition: n exists in the given flow graph.

Parameters:

n - the node to look up

Returns:

the live-out set of the node

getLiveRanges

public java.util.Set<Liveness.LiveRange> getLiveRanges()

Returns the set of variable live ranges (as encoded in the wrapper).

Returns:

the set of variable live ranges

toString

public java.lang.String toString()

Returns a multi-line string representation of each node's live-in and live-out sets, each line in the form: [#] [live-in={?,?,...,?.}, live-out={?,?,...,?,}]. Used for debugging dump.

Overrides:

toString in class java.lang.Object

Returns:

a multi-line string representation of the nodes' live-in and live-out sets