scale.score
Class Scribble

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

All Implemented Interfaces:

AnnotationInterface, DisplayNode

public final class Scribble
extends Root

This class represents a Scribble graph (CFG).

$Id: Scribble.java,v 1.323 2007-10-29 13:41:44 burrill Exp $

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

Scribble graphs are built for one procedure at a time, so this class represents a single procedure.

Scale converts irreducible graphs into reducible graphs using node-splitting. This can create a memory & time problem when going into and out of SSA form. The problem results from generating multiple definitions of temporary, compiler-created variables. There may be thousands of them. Each one then becomes a non-local variable and requires phi-functions and re-naming. The solution adopted here is to bypass SSA form (and optimizations) for those routines that had irreducible graphs. Another solution is to change Clef2Scribble to create more complex expression trees instead of placing one expression per CFG node. This solution should provide a significant speed-up because:

• there will be vastly fewer varaibles, and
• the scans over the CFG will be faster (fewer nodes).

The downside is that many optimizations currently depend on having simple expression trees and will need re-writting.

Scalar variables have alias information. Data dependence for scalar variables is represented by use-def links in SSA form. Array references have data dependence information represented via a DDGraph instance and no alias information.

Field Summary

static boolean	doIfCombine Set true to combine if-then-elses where possible.
static boolean	doIfConversion Set true to convert if-then-else to conditional expressions where possible.
static int	invalidSSA The CFG is in an invalid SSA form.
static int	LTC_TABLE_SIZE The number of slots to use in the loop trip count table for each loop.
static int	maxImplicitLoopFactor If the count of possible implicit loops exceeds this value, no conversion of implicit loops to explicit loops is performed and no optimizations that require SSA form are performed.
static int	notSSA The CFG is not in SSA form.
static int	PROFILE_BLOCKS Profile block execution.
static int	PROFILE_EDGES Profile if-then-else choices.
static int	PROFILE_LICNT Do loop instruction count profiling.
static int	PROFILE_LOOPS Do loop iteration count profiling.
static int	PROFILE_PATHS Do path profiling.
static boolean	reportOptTimes Set true to report elapsed times for each optimization.
static int	validSSA The CFG is in SSA form.

Constructor Summary

Scribble(RoutineDecl cn, SourceLanguage sourceLang, CallGraph cg)
Creates a Scribble object to collect information about a Scribble CFG.

Method Summary

void	addDeclaration(Declaration decl) Add a new declaration to the set of declarations for this CFG if it is not already there.
VariableDecl	addProfiling(int profileOptions, boolean isMain) Add the profiling information to this CFG.
void	addWarning(int msg, java.lang.String text1, java.lang.String text2) Add a warning message to be displayed for this routine.
boolean	applyOptimization(Optimization opt, PlaceIndirectOps pio) Apply the specified optimization to the CFG.
void	applyProfInfo(ProfileInfo pf, int profileOptions) Obtain the profile information from a previous execution of the program and annotate the CFG with the information.
void	applyProfLoopInfo(ProfileInfo pf, Vector<LoopHeaderChord> loops) Apply loop trip count profiling information to the CFG.
static void	cleanup() Clean up for profiling statistics.
boolean	containedGotos() Return true if the source program was unstructured.
static int	deadVarCFGNodes() Return the number of dead nodes removed.
static int	deadVariables() Return the number of dead variables removed.
void	exitSSA() If the CFG is in SSA form, exit SSA form.
protected VariableDecl	genTemp(Type t) Create a new temporary variable for use by the optimized code.
void	getAllDeclarations(java.util.AbstractCollection<Declaration> collection) Add all declarations, associated with this CFG, to the specified collection.
BeginChord	getBegin() Return the head of this CFG.
Declaration	getDecl(int i) Return the specified declaration associated with this CFG.
DominanceFrontier	getDominanceFrontier() Return the dominance frontier information.
Domination	getDomination() Return the dominator information for the CFG.
EndChord	getEnd() Return the tail of the CFG.
int	getLoopIcount(LoopHeaderChord loop) Return the loop body instruction count for a particular loop.
int	getLoopLtcUnrollCount(LoopHeaderChord loop) Return the unroll count determined from loop histogram profiling.
LoopHeaderChord	getLoopTree() Return the top loop which is the BeginChord.
int	getLoopUcount(LoopHeaderChord loopHeader) Return the loop body unroll count for a particular loop.
int	getNextLoopNumber() Provide unique loop IDs for each loop in the CFG.
java.util.Iterator<Declaration>	getNonLocalVars() Return a list of variables used in more than one basic block.
DominanceFrontier	getPostDominanceFrontier() Return the post dominance frontier information.
Domination	getPostDomination() Return the dominator information for the CFG.
PPCfg	getPPCfg() Return the path profiling-specific representation of this Scribble CFG.
References	getRefs() Return the reference information object.
RoutineDecl	getRoutineDecl() Return the routine associated with this CFG.
SourceLanguage	getSourceLanguage() Return the source language of the Scribble tree.
SSA	getSSA() Return the SSA instance for this CFG.
java.util.Enumeration<java.lang.String>	getWarnings() Return an enumeration of the warnings.
static Vector<Chord>	grabSubgraph(Chord first, HashMap<Chord,Chord> nm, Vector<Chord> newn, Stack<Chord> wl) Make a copy of the CFG specified.
static int	ifsCombined() Return the number of if-then-else nodes eliminated by combining them with another if-then-else.
static int	ifsReduced() Return the number of if-then-else nodes changed to conditional expressions.
static int	implicitLoops() Return the current number of implicit loops found.
void	incrementLoopInstCount(int loopNumber, int instructionCount)
boolean	inIteratedDominanceFrontier(Chord c, Chord b) Return true if b is in the iterated dominance frontier of c.
int	inSSA() Return an indication of the state of the SSA form of the CFG.
void	inSSAForm() Specify that the CFG is in valid SSA form.
void	instantiate(BeginChord begin, EndChord end, Vector<Declaration> declarations, boolean containedGotos) Attach the CFG information to the Scribble node.
void	invalidSSAForm() Specify that the CFG is in invalid SSA form.
static int	irreducible() Return the number of irreducible routines.
boolean	isIrreducible() Return true if this routine has an irreducible CFG.
boolean	isSimpleFunction() Return true if the function is simple.
void	labelCFG() Give unique labels to all CFG nodes.
int	labelCfgForBackend(int labelIndex) Label the CFG nodes for the backend code generator.
void	linearize(Vector<Chord> linear) Append the CFG nodes to the specified vector in execution order.
static void	linkSubgraph(Vector<Chord> newn, HashMap<Chord,Chord> nm, Vector<Chord> special) Given a mapping from old CFG nodes to new ones, create the subgraph that is the duplicate of the old graph by replacing, in the new nodes, edges to the old nodes with edges to the new nodes.
static int	newCFGNodes() Return the number of new nodes created.
void	notSSAForm() Specify that the CFG is not in SSA form.
int	numDecls() Return the count of declarations associated with this CFG.
void	performedScalarReplacement() Specify that Scalar Replacement was performed on the CFG.
void	recomputeDataDependence() This method is called if an optimization makes any change to the CFG that would result in making the data dependence information invalid.
void	recomputeDominators() This method is called if an optimization makes any change to the CFG that would result in making the dominator tree invalid.
void	recomputeLoops() Specify that all the loop information is no longer valid for this CFG.
void	recomputeRefs() This method is called if an optimization makes any change to the CFG that would result in making the use - def information invalid.
void	reduceMemory() Reduce the amount of memory used by this instance of a Scribble graph.
void	removeDeadVariables(boolean ssa) Removes statements that set the value of a variable that is not used.
void	removeDeclaration(Declaration a) Removes a declaration from any list it might be on.
void	removeDualExprs() Remove all DualExpr instances from the CFG.
boolean	scalarReplacementPerformed() Return true if scalar replacement has been performed.
void	setLoopICEst(LoopHeaderChord loop, int instCountEstimate)
void	setLoopUC(LoopHeaderChord loop, int unrollCount)
void	setLoopUCEst(LoopHeaderChord loop, int unrollCountEst)
java.lang.String	toString()
void	validateCFG() Throw an error if the CFG has an invalid link.

Methods inherited from class scale.common.Root

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

Methods inherited from class java.lang.Object

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

Field Detail

notSSA

public static final int notSSA

The CFG is not in SSA form.

See Also:

Constant Field Values

validSSA

public static final int validSSA

The CFG is in SSA form.

See Also:

Constant Field Values

invalidSSA

public static final int invalidSSA

The CFG is in an invalid SSA form.

See Also:

Constant Field Values

doIfCombine

public static boolean doIfCombine

Set true to combine if-then-elses where possible.

doIfConversion

public static boolean doIfConversion

Set true to convert if-then-else to conditional expressions where possible.

reportOptTimes

public static boolean reportOptTimes

Set true to report elapsed times for each optimization.

maxImplicitLoopFactor

public static int maxImplicitLoopFactor

If the count of possible implicit loops exceeds this value, no conversion of implicit loops to explicit loops is performed and no optimizations that require SSA form are performed.

PROFILE_BLOCKS

public static final int PROFILE_BLOCKS

Profile block execution.

See Also:

Constant Field Values

PROFILE_EDGES

public static final int PROFILE_EDGES

Profile if-then-else choices.

See Also:

Constant Field Values

PROFILE_PATHS

public static final int PROFILE_PATHS

Do path profiling.

See Also:

Constant Field Values

PROFILE_LOOPS

public static final int PROFILE_LOOPS

Do loop iteration count profiling.

See Also:

Constant Field Values

PROFILE_LICNT

public static final int PROFILE_LICNT

Do loop instruction count profiling.

See Also:

Constant Field Values

LTC_TABLE_SIZE

public static final int LTC_TABLE_SIZE

The number of slots to use in the loop trip count table for each loop.

See Also:

Constant Field Values

Constructor Detail

Scribble

public Scribble(RoutineDecl cn,
                SourceLanguage sourceLang,
                CallGraph cg)

Creates a Scribble object to collect information about a Scribble CFG.

Parameters:

sourceLang - the source language

Method Detail

implicitLoops

public static int implicitLoops()

Return the current number of implicit loops found.

deadVarCFGNodes

public static int deadVarCFGNodes()

Return the number of dead nodes removed.

newCFGNodes

public static int newCFGNodes()

Return the number of new nodes created.

deadVariables

public static int deadVariables()

Return the number of dead variables removed.

irreducible

public static int irreducible()

Return the number of irreducible routines.

ifsReduced

public static int ifsReduced()

Return the number of if-then-else nodes changed to conditional expressions.

ifsCombined

public static int ifsCombined()

Return the number of if-then-else nodes eliminated by combining them with another if-then-else.

instantiate

public void instantiate(BeginChord begin,
                        EndChord end,
                        Vector<Declaration> declarations,
                        boolean containedGotos)

Attach the CFG information to the Scribble node. As part of this, the dominators of the CFG nodes are determined.

Parameters:

begin - the starting node in the graph

end - the ending node in the graph

declarations - a vector of the Clef Declarations associated with this graph

containedGotos - true if the CFG may be irreducible

genTemp

protected VariableDecl genTemp(Type t)

Create a new temporary variable for use by the optimized code. The variable definition is added to the set of variables for this CFG.

getNextLoopNumber

public final int getNextLoopNumber()

Provide unique loop IDs for each loop in the CFG. The BeginChord instance is loop 0.

inSSAForm

public void inSSAForm()

Specify that the CFG is in valid SSA form.

invalidSSAForm

public void invalidSSAForm()

Specify that the CFG is in invalid SSA form.

notSSAForm

public void notSSAForm()

Specify that the CFG is not in SSA form.

inSSA

public int inSSA()

Return an indication of the state of the SSA form of the CFG.

getSSA

public final SSA getSSA()

Return the SSA instance for this CFG.

performedScalarReplacement

public void performedScalarReplacement()

Specify that Scalar Replacement was performed on the CFG.

scalarReplacementPerformed

public boolean scalarReplacementPerformed()

Return true if scalar replacement has been performed.

validateCFG

public void validateCFG()

Throw an error if the CFG has an invalid link.

reduceMemory

public void reduceMemory()

Reduce the amount of memory used by this instance of a Scribble graph.

Note - this method uses nextVisit().

isSimpleFunction

public boolean isSimpleFunction()

Return true if the function is simple. A simple function has no more than one loop.

getSourceLanguage

public final SourceLanguage getSourceLanguage()

Return the source language of the Scribble tree.

getDomination

public Domination getDomination()

Return the dominator information for the CFG.

getPostDomination

public Domination getPostDomination()

Return the dominator information for the CFG.

removeDeadVariables

public void removeDeadVariables(boolean ssa)

Removes statements that set the value of a variable that is not used. See Algorithm 19.12 in "Modern Compiler Implementation in Java" by Appel.

Note - this method uses nextVisit().

Parameters:

ssa - true if SSA variable coalescing has not yet been performed

See Also:

SSA.coalesceVariables()

removeDualExprs

public void removeDualExprs()

Remove all DualExpr instances from the CFG. Use the lower form. This eliminates references to variables that may no longer be needed.

Note - this method uses nextVisit().

removeDeclaration

public void removeDeclaration(Declaration a)

Removes a declaration from any list it might be on.

Parameters:

a - is the variable

getRefs

public References getRefs()

Return the reference information object.

getNonLocalVars

public java.util.Iterator<Declaration> getNonLocalVars()

Return a list of variables used in more than one basic block. Create a list of non-local variables for use in creating a pruned-SSA form. This is the list of variables for which Phi functions must be inserted. The algorithm comes from Practical Improvements to the Construction and Destruction of Static Single Assignment Form by Briggs, et al, in Software - Practice and Experience, Vol 1(1), 1-28 (January 1988. This algorithm requires that multiple statements be placed into a single basic block in order to determine whether a variable reference is "non-local". Since Scribble places each statement into its own basic block, we must determine what "normally" would be in a traditional basic-block. We use an iterative algorithm because the recursive algorithm proved too costly for Fortran programs that have large basic blocks.

getDominanceFrontier

public DominanceFrontier getDominanceFrontier()

Return the dominance frontier information.

getPostDominanceFrontier

public DominanceFrontier getPostDominanceFrontier()

Return the post dominance frontier information.

containedGotos

public boolean containedGotos()

Return true if the source program was unstructured.

isIrreducible

public final boolean isIrreducible()

Return true if this routine has an irreducible CFG.

inIteratedDominanceFrontier

public boolean inIteratedDominanceFrontier(Chord c,
                                           Chord b)

Return true if b is in the iterated dominance frontier of c.

recomputeRefs

public void recomputeRefs()

This method is called if an optimization makes any change to the CFG that would result in making the use - def information invalid.

recomputeDominators

public void recomputeDominators()

This method is called if an optimization makes any change to the CFG that would result in making the dominator tree invalid.

recomputeLoops

public void recomputeLoops()

Specify that all the loop information is no longer valid for this CFG.

getBegin

public BeginChord getBegin()

Return the head of this CFG.

getEnd

public EndChord getEnd()

Return the tail of the CFG.

getDecl

public Declaration getDecl(int i)

Return the specified declaration associated with this CFG.

numDecls

public int numDecls()

Return the count of declarations associated with this CFG.

getAllDeclarations

public void getAllDeclarations(java.util.AbstractCollection<Declaration> collection)

Add all declarations, associated with this CFG, to the specified collection.

addDeclaration

public void addDeclaration(Declaration decl)

Add a new declaration to the set of declarations for this CFG if it is not already there. This method is designed for optimizations that may try to define something twice such as Inlining.

getRoutineDecl

public final RoutineDecl getRoutineDecl()

Return the routine associated with this CFG.

toString

public java.lang.String toString()

Overrides:

toString in class Root

getLoopTree

public LoopHeaderChord getLoopTree()

Return the top loop which is the BeginChord. The outermost code containing the loop(s) is considered to be the level 0 loop. Although technically it is not a loop, the root (level 0) is encapsulated in a LoopHeaderChord instance for consistency of representation. Nesting info is available thru the LoopHeaderChord instance.

recomputeDataDependence

public void recomputeDataDependence()

This method is called if an optimization makes any change to the CFG that would result in making the data dependence information invalid.

labelCFG

public void labelCFG()

Give unique labels to all CFG nodes. For any given node n1, node n1's label is greater than the labels of all its immediate predecessors.

Note - other algorithms may use the label field and destroy this value. An example is the computation of dominators.

Note - this method uses nextVisit().

See Also:

Domination

labelCfgForBackend

public int labelCfgForBackend(int labelIndex)

Label the CFG nodes for the backend code generator. Only nodes that begin a basic block are given non-zero label values. This method is intended to help code generators decide when to generate labels in the output text.

Note - this method uses nextVisit().

Parameters:

labelIndex - is the first label index value to use

Returns:

the next label index value to use

linearize

public void linearize(Vector<Chord> linear)

Append the CFG nodes to the specified vector in execution order. All the nodes of a loop are guaranteed to be before the nodes after the loop exits.

See Also:

GlobalVarReplacement, Chord.pushChordWhenReady(Stack), LoopHeaderChord.labelCFGLoopOrder()

applyOptimization

public boolean applyOptimization(Optimization opt,
                                 PlaceIndirectOps pio)

Apply the specified optimization to the CFG. Insure that the CFG is in the proper SSA form for the optimization first.

Parameters:

opt - is the optimization

pio - is the proper class instance for the alias analysis virtual variables

Returns:

true if the optimization was performed

exitSSA

public void exitSSA()

If the CFG is in SSA form, exit SSA form.

addWarning

public final void addWarning(int msg,
                             java.lang.String text1,
                             java.lang.String text2)

Add a warning message to be displayed for this routine.

getWarnings

public final java.util.Enumeration<java.lang.String> getWarnings()

Return an enumeration of the warnings.

grabSubgraph

public static Vector<Chord> grabSubgraph(Chord first,
                                         HashMap<Chord,Chord> nm,
                                         Vector<Chord> newn,
                                         Stack<Chord> wl)

Make a copy of the CFG specified. The new CFG is not linked (see linkSubgraph. The spanning of the CFG halts when a node is encountered that is already in the map.

Parameters:

first - specifies the first node to copy

nm - maps from old node to new node

newn - is a vector of the new nodes that are created

wl - is a work stack - it is empty on exit

Returns:

a vector of the special nodes (e.g., Phi CFG nodes & LoopHeaderChords) in the original graph that require special treatment or null

See Also:

linkSubgraph(scale.common.Vector, scale.common.HashMap, scale.common.Vector)

linkSubgraph

public static void linkSubgraph(Vector<Chord> newn,
                                HashMap<Chord,Chord> nm,
                                Vector<Chord> special)

Given a mapping from old CFG nodes to new ones, create the subgraph that is the duplicate of the old graph by replacing, in the new nodes, edges to the old nodes with edges to the new nodes. The actual nodes in the subgraph, that are specified in the mapping, may be determined in many ways:

1. from the dominance tree as is the case for irreducible graphs
2. from the loop as is done for unroll
3. from a complete routine as is done for inlining.

Parameters:

newn - is the list of the new nodes

nm - is the mapping from old nodes to new ones

special - is the set or original nodes that require special treatment

See Also:

grabSubgraph(scale.score.chords.Chord, scale.common.HashMap, scale.common.Vector, scale.common.Stack)

addProfiling

public VariableDecl addProfiling(int profileOptions,
                                 boolean isMain)

Add the profiling information to this CFG. A variable is defined that holds the profiling information. It is an struct of ten fields. The first entry points to a C string containing the name of the function.

The second entry is the size of the next two arrays. The third entry points to an array of C ints containing line numbers from the source code or is null. The fourth entry points to the array of C ints of block frequencies or is null. There is a one-to-one correspondence between the entries in the line number array and the entries in the frequency array.

The fifth entry is the size of the next two arrays. The sixth entry points to an array of C ints containing edges from the source code or is null. The seventh entry points to the array of C ints of edge frequencies or is null. There is a one-to-one correspondence between the entries in the line number array and the entries in the frequency array. The edges in the line number array are encoded as a pair (src, dst) of line numbers.

The eighth entry is the size of the next array. The ninth entry points to an array of C ints of path numbers. The tenth entry points to an array of C ints of path frequencies or is null.

The eleventh entry is the number of loops. The twelfth entry is the loop trip count histogram (LTCH) table, which has size numLoops * LTC_TABLE_SIZE.

Note - this method uses nextVisit().

Parameters:

profileOptions - specifies which profiling instrumentation to insert

isMain - - is true if this is the "main" entry node

Returns:

the variable definition for the profiling information

applyProfInfo

public void applyProfInfo(ProfileInfo pf,
                          int profileOptions)

Obtain the profile information from a previous execution of the program and annotate the CFG with the information.

The user's program is first modified to produce the profiling information by inserting operations into the CFG. This insertion occurs just prior to code generation. The user requests this via a command line switch.

When the program is executed it produces a .pft file for every source module in the program. This file contains the profile information on the number of times a block, edge, or path in the program was executed.

On a subsequent compilation an optimization can request that this profile information be read and the CFG annotated with it. For edge profiling, the out-going CFG edges of a DecisionChord are given a probability of that edge being used.

In order for this to work, the CFG must be equivalent, in the structure of the graph edges when the profile information is read, to the CCFG when the profiling operations were inserted.

applyProfLoopInfo

public void applyProfLoopInfo(ProfileInfo pf,
                              Vector<LoopHeaderChord> loops)

Apply loop trip count profiling information to the CFG.

Parameters:

pf - is the profile info that has been read in for the CFG

loops - is the set of loops in the program

getPPCfg

public PPCfg getPPCfg()

Return the path profiling-specific representation of this Scribble CFG.

getLoopUcount

public int getLoopUcount(LoopHeaderChord loopHeader)

Return the loop body unroll count for a particular loop. Returns -1 if not found.

getLoopIcount

public int getLoopIcount(LoopHeaderChord loop)

Return the loop body instruction count for a particular loop. Returns -1 if not found.

getLoopLtcUnrollCount

public int getLoopLtcUnrollCount(LoopHeaderChord loop)

Return the unroll count determined from loop histogram profiling. Returns -1 if not found.

incrementLoopInstCount

public void incrementLoopInstCount(int loopNumber,
                                   int instructionCount)

setLoopICEst

public void setLoopICEst(LoopHeaderChord loop,
                         int instCountEstimate)

setLoopUC

public void setLoopUC(LoopHeaderChord loop,
                      int unrollCount)

setLoopUCEst

public void setLoopUCEst(LoopHeaderChord loop,
                         int unrollCountEst)

cleanup

public static void cleanup()

Clean up for profiling statistics.