scale.score
Class Domination

java.lang.Object
  scale.common.Root
      scale.score.Domination

All Implemented Interfaces:

AnnotationInterface, DisplayNode

public class Domination
extends Root

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

$Id: Domination.java,v 1.76 2007-10-04 19:58:18 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, Chord start)

Method Summary

void	addDominatee(Chord d, Chord me) Specify that node d dominates node me.
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	deadCFGNodes() Return the number of dead nodes removed.
void	displayDominance(java.io.PrintStream s, Chord n) Print out the dominance relations for node n.
Chord[]	getDominatees(Chord dominator) Return the set of CFG nodes that dominator strictly dominates.
Chord	getDominatorOf(Chord v) Return the dominator of v.
Vector<Chord>	getIterativeDomination(Chord n) Return the set of all nodes strictly dominated by node n and all nodes dominated by nodes dominated by n, and so on.
void	getIterativeDomination(Chord n, Vector<Chord> 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	getIterativeDominationLH(LoopPreHeaderChord lph, Vector<Chord> idom, boolean calls, HashSet<Chord> stops) Return true if the entire loop is dominated by the loop pre-header without interference from calls, etc.
void	getIterativeDominationNF(Chord dominator, Vector<Chord> idom) Return the set of all nodes dominated by node n and all nodes dominated by nodes dominated by n, and so on.
void	getIterativeDominationNF(Chord dominator, Vector<Chord> idom, boolean calls, HashSet<Chord> stops) Return the set of all nodes dominated by node c and all nodes dominated by nodes dominated by c, and so on.
void	getIterativeDominationNF(Chord dominator, Vector<Chord> idom, HashSet<Chord> stops) Return the set of all nodes dominated by node c and all nodes dominated by nodes dominated by c, and so on.
boolean	inDominatees(Chord n, Chord d) Return true if CFG node n strictly dominates node d.
boolean	inIterativeDominatees(Chord n, Chord d) Return true if CFG node n dominates node d.
boolean	isPostDomination() Return true if this domination is a post domination.
int	numDominatees(Chord dominator) Return the number of the nodes that dominator strictly dominates.
void	pushDominatees(Chord dominator, Stack<Chord> wl) Push onto the stack all of the nodes that dominator strictly dominates.
void	removeDeadCode() Removes all nodes that do not have a dominator.
void	removeDominatee(Chord d, Chord me) Specify that node d no longer dominates node me.
java.lang.String	toStringSpecial() Return any special information of a node that is not a child or annotation.

Methods inherited from class scale.common.Root

addAnnotation, allAnnotations, allMatchingAnnotations, getAnnotation, getDisplayColorHint, getDisplayLabel, getDisplayName, getDisplayShapeHint, getDisplayString, getNodeCount, getNodeID, hasAnnotation, hasEqualAnnotation, hashCode, removeAnnotation, removeAnnotations, toString, toStringAnnotations, toStringClass, trace, trace, trace

Methods inherited from class java.lang.Object

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

Constructor Detail

Domination

public Domination(boolean post,
                  Chord 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.

deadCFGNodes

public static int deadCFGNodes()

Return the number of dead nodes removed.

getDominatorOf

public final Chord getDominatorOf(Chord v)

Return the dominator of v.

addDominatee

public final void addDominatee(Chord d,
                               Chord me)

Specify that node d dominates node me. This method should only be used to update the domination information after the dominators have been computed.

removeDominatee

public final void removeDominatee(Chord d,
                                  Chord me)

Specify that node d no longer dominates node me. This method should only be used to update the domination information after the dominators have been computed.

getDominatees

public final Chord[] getDominatees(Chord dominator)

Return the set of CFG nodes that dominator strictly dominates.

pushDominatees

public final void pushDominatees(Chord dominator,
                                 Stack<Chord> wl)

Push onto the stack all of the nodes that dominator strictly dominates. The nodes are placed on the stack in ascending order by the node's label.

See Also:

Scribble.labelCFG()

numDominatees

public final int numDominatees(Chord dominator)

Return the number of the nodes that dominator strictly dominates.

getIterativeDominationNF

public void getIterativeDominationNF(Chord dominator,
                                     Vector<Chord> idom)

Return the set of all nodes dominated by node n and all nodes dominated by nodes dominated by n, and so on. However, don't go past a non-pure subroutine call.

Consider the case where a subroutine call exists inside of a loop dominated by c. In this case, all of the nodes in the loop must be eliminated from the set returned.

We can go to the ends of the CFG as long as there is no join. For example, in

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     y = abc();
  (4)   y = g + 4
 

even though line (1) dominates line (4), the call to abc on line (3) prevents the nodes of line (4) from being included in the same set. However, in

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     return x;
  (4)   y = g + 4
 

line (4) can be included because line (3) is an "end". Note - In this case:

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     z = 123;
  (4)   y = g + 4
 

line (4) is still not included because there is a join to line (4) and our logic is not powerful enough to know that line(3) is not a problem.

Note - this method uses nextVisit().

Parameters:

dominator - is the dominator node

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

getIterativeDominationNF

public void getIterativeDominationNF(Chord dominator,
                                     Vector<Chord> idom,
                                     HashSet<Chord> stops)

Return the set of all nodes dominated by node c and all nodes dominated by nodes dominated by c, and so on. However, don't go past a non-pure subroutine call or one of the nodes specified by the stops.

Consider the case where a subroutine call exists inside of a loop dominated by c. In this case, all of the nodes in the loop must be eliminated from the set returned.

We can go to the ends of the CFG as long as there is no join. For example, in

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     y = abc();
  (4)   y = g + 4
 

even though line (1) dominates line (4), the call to abc on line (3) prevents the nodes of line (4) from being included in the same set. However, in

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     return x;
  (4)   y = g + 4
 

line (4) can be included because line (3) is an "end". Note - In this case:

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     z = 123;
  (4)   y = g + 4
 

line (4) is still not included because there is a join to line (4) and our logic is not powerful enough to know that line(3) is not a problem.

Note - this method uses nextVisit().

Parameters:

dominator - is the dominator node

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

stops - is the list of nodes that should terminate the collection

getIterativeDominationNF

public void getIterativeDominationNF(Chord dominator,
                                     Vector<Chord> idom,
                                     boolean calls,
                                     HashSet<Chord> stops)

Return the set of all nodes dominated by node c and all nodes dominated by nodes dominated by c, and so on. If specified, do not go past a non-pure subroutine call. Do not go past one of the nodes specified by the stops.

Consider the case where a subroutine call exists inside of a loop dominated by c. In this case, all of the nodes in the loop must be eliminated from the set returned.

We can go to the ends of the CFG as long as there is no join. For example, in

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     y = abc();
  (4)   y = g + 4
 

even though line (1) dominates line (4), the call to abc on line (3) prevents the nodes of line (4) from being included in the same set. However, in

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     return x;
  (4)   y = g + 4
 

line (4) can be included because line (3) is an "end". Note - In this case:

  (1)   x = g + 3;
  (2)   if (exp)
  (3)     z = 123;
  (4)   y = g + 4
 

line (4) is still not included because there is a join to line (4) and our logic is not powerful enough to know that line(3) is not a problem.

Note - this method uses nextVisit().

Parameters:

dominator - is the dominator node

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

calls - is true if a call to a non-pure function should terminate

stops - is the list of nodes that should terminate the collection

getIterativeDominationLH

public boolean getIterativeDominationLH(LoopPreHeaderChord lph,
                                        Vector<Chord> idom,
                                        boolean calls,
                                        HashSet<Chord> stops)

Return true if the entire loop is dominated by the loop pre-header without interference from calls, etc. It is necessary to do a

   Chord.nextVisit();
 

before calling this method.

Parameters:

lph - is the dominator node

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

calls - is true if non-pure calls should be checked

stops - is the list of nodes that should terminate the collection

getIterativeDomination

public final Vector<Chord> getIterativeDomination(Chord 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

public void getIterativeDomination(Chord n,
                                   Vector<Chord> 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(Chord n,
                                  Chord d)

Return true if CFG node n strictly dominates node d.

Parameters:

n - the node to test

d - the node to test

inIterativeDominatees

public final boolean inIterativeDominatees(Chord n,
                                           Chord d)

Return true if CFG 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,
                                   Chord n)

Print out the dominance relations for node n.

Parameters:

s - the stream to write to

isPostDomination

public final boolean isPostDomination()

Return true if this domination is a post domination.

removeDeadCode

public final void removeDeadCode()

Removes all nodes that do not have a dominator. If a node is found that has no dominator, it and all of its children in the dominator tree are removed from the CFG.

toStringSpecial

public java.lang.String toStringSpecial()

Description copied from class: Root

Return any special information of a node that is not a child or annotation. This method is meant to be overridden by nodes that need to provide special output.

Overrides:

toStringSpecial in class Root