spiglet.translate.graph
Class InterferenceGraph<T>

java.lang.Object
  spiglet.translate.graph.Graph
      spiglet.translate.graph.InterferenceGraph<T>

Type Parameters:

T - the type of the variable (attributed to nodes in the graph).

public class InterferenceGraph<T>
extends Graph

This class represents an interference graph. An interference graph has variables as its nodes. If two variables are ever live at the same time in a given statement (or, basic block) of the program, an edge exists between them. Unlike a flow graph, an interference graph is undirected. (Implementation detail: the edges of this graph class are represented as a matrix, rather than linked list of successors/predecessors).

Author:

Santoso Wijaya

See Also:

Liveness, FlowGraph, Node

Field Summary

Fields inherited from class spiglet.translate.graph.Graph

nodes

Constructor Summary

InterferenceGraph(FlowGraph<T> graph)
Given a control flow graph, use a Liveness analyzer and the information computed therein to derive an interference graph.

Method Summary

boolean	addEdge(Node from, Node to) Adds an undirected edge between the two given nodes.
Node	getNode(T var) Looks up and returns the node object that is associated with the given variable.
T	getVariable(Node node) Looks up and returns the variable that is associated with the given node.
boolean	removeEdge(Node from, Node to) Removes an edge between the two given nodes in the graph.
java.lang.String	toString() Returns the string representation of this interference graph, for debugging dump.

Methods inherited from class spiglet.translate.graph.Graph

addNode, check, createNode, getNodes

Methods inherited from class java.lang.Object

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

Constructor Detail

InterferenceGraph

public InterferenceGraph(FlowGraph<T> graph)

Given a control flow graph, use a Liveness analyzer and the information computed therein to derive an interference graph.

Parameters:

graph - the control flow graph from where to derive the interference graph

See Also:

Liveness

Method Detail

addEdge

public boolean addEdge(Node from,
                       Node to)

Adds an undirected edge between the two given nodes.

Overrides:

addEdge in class Graph

Parameters:

from - the node

to - the node

Returns:

false if such an edge already exists.

removeEdge

public boolean removeEdge(Node from,
                          Node to)

Removes an edge between the two given nodes in the graph.

Overrides:

removeEdge in class Graph

Parameters:

from - the node

to - the ndoe

Returns:

false if such an edge does not exist

getVariable

public T getVariable(Node node)

Looks up and returns the variable that is associated with the given node.

Parameters:

node - the node to look up

Returns:

the variable that is associated with the given node, null if the given node is null

getNode

public Node getNode(T var)

Looks up and returns the node object that is associated with the given variable.

Parameters:

var - the variable too look up

Returns:

the node object with which the given variable is associated

toString

public java.lang.String toString()

Returns the string representation of this interference graph, for debugging dump. The string is in one line, in the form of ({#,#,...,#,}, {(#,#),(#,#),...,(#,#),}), which represents the set of nodes and edges in the graph, where each node is the string representation of the variables.

Overrides:

toString in class Graph

Returns:

the string representation of this interference graph