scale.backend
Class Domination

java.lang.Object
  scale.backend.Domination

public class Domination
extends java.lang.Object

This class computes the dominators and post dominators of nodes in a graph.

$Id: Domination.java,v 1.9 2007-10-04 19:57:48 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

As described in A Fast Algorithm for Finding Dominators in a Flowgraph by Lengauer and Tarjan, ACM. Tran. on Prog. Lang and System, July 1979.

Constructor Summary

Domination(boolean post, Node start)

Method Summary

static int	computed() Return the number of times the dominance frontier was computed.
static int	created() Return the number of instances of this class that were created.
static int	deadNodes() Return the number of dead nodes removed.
void	displayDominance(java.io.PrintStream s, Node n) Print out my dominance relations.
Node[]	getDominatees(Node n) Return an iteration of the nodes that n strictly dominates.
Node	getDominatorOf(Node v) Return the dominator of v.
Vector<Node>	getIterativeDomination(Node n) Return the set of all nodes strictly dominated by node n and all nodes dominated by nodes dominated by n, and so on.
protected void	getIterativeDomination(Node n, Vector<Node> v) Return the set of all nodes strictly dominated by node n and all nodes dominated by nodes dominated by n, and so on.
boolean	inDominatees(Node n, Node d) Return true if PFG node n dominates node d.
boolean	isPostDomination() Return true if this domination is a post domination.
int	numDominatees(Node n) Return the number of the nodes that n dominates.
void	pushDominatees(Node n, Stack<java.lang.Object> wl) Push onto the stack all of the nodes that n strictly dominates.

Methods inherited from class java.lang.Object

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

Constructor Detail

Domination

public Domination(boolean post,
                  Node start)

Parameters:

post - false for dominators, true for post dominators to be determined

start - the starting node in the graph (or end if post dominators)

Method Detail

created

public static int created()

Return the number of instances of this class that were created.

computed

public static int computed()

Return the number of times the dominance frontier was computed.

deadNodes

public static int deadNodes()

Return the number of dead nodes removed.

getDominatorOf

public final Node getDominatorOf(Node v)

Return the dominator of v.

getDominatees

public final Node[] getDominatees(Node n)

Return an iteration of the nodes that n strictly dominates.

pushDominatees

public final void pushDominatees(Node n,
                                 Stack<java.lang.Object> wl)

Push onto the stack all of the nodes that n strictly dominates. The nodes are placed on the stack in descending order by the node's label. The nodes will be popped from the stack in reverse post-order.

numDominatees

public final int numDominatees(Node n)

Return the number of the nodes that n dominates.

getIterativeDomination

public final Vector<Node> getIterativeDomination(Node n)

Return the set of all nodes strictly dominated by node n and all nodes dominated by nodes dominated by n, and so on.

Parameters:

n - is the dominator node

getIterativeDomination

protected void getIterativeDomination(Node n,
                                      Vector<Node> v)

Return the set of all nodes strictly dominated by node n and all nodes dominated by nodes dominated by n, and so on.

Parameters:

n - is the dominator node

v - is the vector to which the dominated nodes are added

inDominatees

public final boolean inDominatees(Node n,
                                  Node d)

Return true if PFG node n dominates node d.

Parameters:

n - the node to test

d - the node to test

displayDominance

public final void displayDominance(java.io.PrintStream s,
                                   Node n)

Print out my dominance relations.

Parameters:

s - the stream to write to

isPostDomination

public final boolean isPostDomination()

Return true if this domination is a post domination.