EDU.purdue.cs.bloat.cfg
Class DominatorTree

java.lang.Object
  |
  +--EDU.purdue.cs.bloat.cfg.DominatorTree

public class DominatorTree

extends java.lang.Object

DominatorTree finds the dominator tree of a FlowGraph.

The algorithm used is Purdum-Moore. It isn't as fast as Lengauer-Tarjan, but it's a lot simpler.

See Also:

FlowGraph, Block

Field Summary

static boolean

DEBUG

Constructor Summary

DominatorTree()

Method Summary

static void

buildTree(FlowGraph graph, boolean reverse) Calculates what vertices dominate other verices and notify the basic Blocks as to who their dominator is.

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

public static boolean DEBUG

Constructor Detail

DominatorTree

public DominatorTree()

Method Detail

buildTree

public static void buildTree(FlowGraph graph,
                             boolean reverse)

Calculates what vertices dominate other verices and notify the basic Blocks as to who their dominator is.

Parameters:

graph - The cfg that is used to find the dominator tree.

reverse - Do we go in revsers? That is, are we computing the dominatance (false) or postdominance (true) tree.

See Also:

Block