scale.score
Class CDG

java.lang.Object
  scale.score.CDG

public class CDG
extends java.lang.Object

The CDG class builds the control dependence graph for the scribble graph input.

$Id: CDG.java,v 1.30 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.

The representation is a hash set to a vector of Chords.

• The hash key is the branch chord (i.e., the last chord in a basic block).
• The vector entries are the first chords of the basic blocks dependent on the branch point.

This representation is useful for branch prediction analysis but may be better if the hash keys are the first chord in a basic block if class is made part of Scale proper.

The reverse representation is a hash of the first chords to a vector of the controlling branch points (yes, there can be more than one), again, each of which is the last chord in the basic block with the branch point.

Constructor Summary

CDG(Scribble scribble)
Calculates the CDG from the scribble graph.

Method Summary

void	dumpCDG() Output the CDG for debugging.
Vector<Chord>	getDependents(Chord parent) Return a list of CFG nodes that are immediately dependent on this node.
java.util.HashMap<Chord,java.lang.Boolean>	getParents(Chord child) Returns a map from the child CFG node to the Chord(s) upon which the child is control dependent.
void	updateKey(Chord oldKey, Chord newKey) CDG lookups are done based on the first basic block, if a client changes the basic blocks, they must update the CDG.

Methods inherited from class java.lang.Object

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

Constructor Detail

CDG

public CDG(Scribble scribble)

Calculates the CDG from the scribble graph.

Parameters:

scribble - is the Scribble graph representing a single routine

Method Detail

getParents

public java.util.HashMap<Chord,java.lang.Boolean> getParents(Chord child)

Returns a map from the child CFG node to the Chord(s) upon which the child is control dependent.

The parent node is the key in the map and the condition (true, false or null) is the value. A value of null should only be associated with the BeginChord.

It is legal for the map to contain the BeginChord instance along with other CFG nodes. To check for control independence, the caller should check there is only one parent and that it is the BeginChord or for null.

Parameters:

child - the Chord whose parent is returned.

getDependents

public Vector<Chord> getDependents(Chord parent)

Return a list of CFG nodes that are immediately dependent on this node. Note, if this CFG node is not a control flow node a null is returned.

updateKey

public void updateKey(Chord oldKey,
                      Chord newKey)

CDG lookups are done based on the first basic block, if a client changes the basic blocks, they must update the CDG. This keeps the CDG tables small.

Parameters:

oldKey - old chord that was the first basic block

newKey - new chord that is the first basic block

dumpCDG

public void dumpCDG()

Output the CDG for debugging.