scale.score
Class DominanceFrontier

java.lang.Object
  scale.score.DominanceFrontier

public class DominanceFrontier
extends java.lang.Object

This class computes and manages dominance frontiers.

$Id: DominanceFrontier.java,v 1.73 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.

This class also converts irreducible graphs to reducible graphs by "node-splitting".

Constructor Summary

DominanceFrontier(Chord begin, Domination dom)

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.
java.util.Iterator<Chord>	getDominanceFrontier(Chord bb) Return an iteration of all of the nodes on the dominance frontier of a CFG node.
boolean	inDominanceFrontier(Chord b1, Chord b2) Return true if b2 is in b1's dominance frontier.
boolean	makeGraphReducible(int maxImplicitLoopFactor) Reduce an irreducible graph by spliting nodes.
static int	newCFGNodes() Return the number of new nodes created.
static int	splitNodes() Return the current number of split nodes created.

Methods inherited from class java.lang.Object

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

Constructor Detail

DominanceFrontier

public DominanceFrontier(Chord begin,
                         Domination dom)

Parameters:

begin - is the root node of the CFG (or end node for post-dominators)

dom - is the (post) dominance relation ship

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.

splitNodes

public static int splitNodes()

Return the current number of split nodes created.

newCFGNodes

public static int newCFGNodes()

Return the number of new nodes created.

getDominanceFrontier

public java.util.Iterator<Chord> getDominanceFrontier(Chord bb)

Return an iteration of all of the nodes on the dominance frontier of a CFG node.

Parameters:

bb - the node for which the dominance frontier is requested.

inDominanceFrontier

public boolean inDominanceFrontier(Chord b1,
                                   Chord b2)

Return true if b2 is in b1's dominance frontier.

makeGraphReducible

public boolean makeGraphReducible(int maxImplicitLoopFactor)
                           throws ResourceException

Reduce an irreducible graph by spliting nodes. The logic has to handle the following case. That's why we select the node with the fewest in-coming edges.

 int cmd_exec(int cmdparm)
 {
     if (cmdparm == 5)
       goto finish_while;
 
   until_loop:
     if (cmdparm == 6) {
       if (cmdparm == 1) {
       finish_while:
    if (cmdparm != 2)
      goto until_loop;
       }
       if (cmdparm == 3) {
    goto until_loop;
       }
     }
   return 0;
 }
 

If the CFG is modified, new dominators and a new dominance frontier must be computed and makeGraphReducible() must be called again. This loop must be iterated until makeGraphReducible() returns false.

If there are too many possible implicit loops, this logic can take a very long time and result in very large CFGs. We punt in this case. As a result, other optimizations that SSA form are not performed.

Parameters:

maxImplicitLoopFactor - is a limit on the complexity of the graph that will be reduced

Returns:

true if the CFG has been modified

Throws:

ResourceException - if there are too many possible implicit loops