scale.backend.trips2
Class Hyperblock

java.lang.Object
  scale.common.Root
      scale.backend.Node
          scale.backend.trips2.Hyperblock

All Implemented Interfaces:

AnnotationInterface, DisplayNode

public class Hyperblock
extends Node

This class represents a hyperblock which represents a predicate flow graph.

$Id: Hyperblock.java,v 1.117 2007-10-31 16:39:16 bmaher Exp $

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

A hyperblock is a directed graph of "predicate" blocks called a predicate flow graph.

Field Summary

static boolean	doFastStoreNullification There are two ways to nullify store instructions: (1) null t100 (2) null_t t100 sd_t t100, t100 [1] mov t101, t100 null t101 mov t102, t100 sd_t t101, t101 [2] sd_t t101, t101 [1] sd_t t102, t102 [2] If this is set to true we do (1) which inserts a null for every store.
static boolean	enableInterBlockPredicateMinimization If inter-block predicate minimization should be performed.
static boolean	enableIntraBlockPredicateMinimization If intra-block predicate minimization should be performed.
static boolean	enableRedundantLoadRemoval If redundant loads should be removed.
static int	intraBlockDefault The default intra-block predicate minimization.
static boolean	noLoadStorePredicateField True if load and store instructions do not have a predicate field.
static int	PREDICATE_BOTTOM Predicate only the bottom of dependence chains.
static int	PREDICATE_TOP Predicate only the top of dependence chains.
static boolean	unpredicateLoads To unpredicate a load it cannot share a LSID with another load.
static boolean	useMinMaxLoadStoreAssignment If true, loads are given a unique LSID and stores are given the minimal number of LSIDs.

Fields inherited from class scale.backend.Node

color, label, predecessors, successors, tag

Constructor Summary

Hyperblock(Instruction first, Trips2RegisterSet registers)
Construct a new hyperblock starting with the given instruction.

Hyperblock(PredicateBlock start, BitVect predicates, Trips2RegisterSet registers)
Construct a new hyperblock from a PredicateBlock.

Hyperblock(PredicateBlock start, Trips2RegisterSet registers)
Construct a new hyperblock from a PredicateBlock.

Method Summary

void	addSpill(PredicateBlock block, Instruction inst) Add a spill to the hyperblock.
void	analyzeLeaveSSA() Update the block statistics before leaving SSA form.
void	assignBranchIds(boolean verbose) Assign branch identifiers.
protected void	assignLoadStoreQueueIds() Assign load/store queue ids and nullify stores.
void	clearPredicates() Clear the predicates used in this hyperblock.
static void	computeHyperblockFlowGraph(Vector<Hyperblock> hbs, HashMap<Instruction,Hyperblock> entries) Compute the hyperblock flow graph.
IntMap<Vector<java.lang.Integer>>	computeTargets(Stack<Node> wl, BitVect mov3) Compute the number of targets for each instruction.
Hyperblock	copy() Copy the hyperblock.
void	determinePredicatesBranches() Compute the set of predicates and number of branches.
static void	dumpHyperblockFlowGraph(Hyperblock hbStart) Output the hyperblock flow graph for debugging.
void	dumpPredicateFlowGraph() Output the predicate flow graph for debugging.
static Hyperblock	enterHyperblockFlowGraph(Instruction first, Trips2Generator gen)
void	enterSSA() Convert the PFG into SSA form.
void	findLastBlock() Find the last block in the PFG.
java.lang.String	getBlockName() Returns the name of the block, as seen in the TIL.
int	getBlockSize() Return the size of the instructions in the block (not including fanout).
double	getBranchProbability(Hyperblock succ) Return the probability of branching to the specified hyperblock.
DColor	getDisplayColorHint() Return a String specifying the color to use for coloring this node in a graphical display.
java.lang.String	getDisplayLabel() Return a String suitable for labeling this node in a graphical display.
java.lang.String	getDisplayName() Return the unique node label.
DShape	getDisplayShapeHint() Return a String specifying a shape to use when drawing this node in a graphical display.
DominanceFrontier	getDominanceFrontier() Return the dominance frontier information for the PFG.
Domination	getDomination() Return the dominator information for the PFG.
int	getFanout() Return the estimated fanout for the block.
PredicateBlock	getFirstBlock() Return the first block in the PFG.
PredicateBlock	getLastBlock() Return the last block in the PFG.
BitVect	getLiveIn() Return the registers live-in to (and used in) the hyperblock
BitVect	getLiveOut() Return the registers live-out of (and define by) the hyperblock
int	getLoopNumber()
Vector<PredicateBlock>	getNextPFGLevel(Vector<PredicateBlock> wl) Given a set of PFG nodes that are the same depth from the root node, this routine will return the PFG nodes which are one level deeper.
BitVect	getPredicates() Get the predicates for the hyperblock.
int	getSpillSize() Return the estimated size of the spills in the block.
SSA	getSSA() Return the ssa instance for this hyperblock.
boolean	hasBranchTo(Hyperblock s) Return true if there is a branch to the specified hyperblock.
boolean	hasCall() Return true if this hyperblock contains a function call.
boolean	hasCallTo(Hyperblock s) Return true if there is a call to the specified hyperblock.
boolean	hasDummyStores() Return true if the block contains stores inserted for nullification.
boolean	hasSwitch() Return true if this hyperblock contains a switch statement.
boolean	inSSA() Return true if the hyperblock is in SSA form.
static int	instructionsMerged() Return the number of instructions merged.
protected boolean	interBlockPredicateMinimization(DataflowAnalysis df) Perform inter-block predicate minimization.
void	invalidateDomination() Clear the dominator information for the PFG.
boolean	isLegalBlock(boolean beforeRegisterAllocation) Return true if this is a well formed TRIPS block.
boolean	isPredicate(int reg) Return true if the register is used as a predicate.
boolean	isSimpleLoop() Return true if this hyperblock contains a back-edge to itself.
static Instruction	leaveHyperblockFlowGraph(Hyperblock hbStart, Trips2Generator gen) Convert a function in hyperblock form to straight-line form.
void	leaveSSA(boolean removeReadWrite) Convert the hyperblock out of SSA form.
static int	loadsRemoved() Return the number of loads which were removed.
int	maxLSID() Return the highest assigned load/store ID in the block.
protected void	mergeInstructions(boolean includeBranches) Merge instructions.
void	nextVisit() The next unique color for traversing the graph.
protected void	noLoadStorePredicateField() If load and store instructions cannot be predicated this method ensures that atleast one of the instructions in the dependence chain is predicated.
static int	nullWritesInserted() Return the number of nulls inserted.
int	numBranches() Return the number of branches in the block.
int	numSpills() Return the number of spill instructions in the block.
void	optimize(boolean removeLoads, DataflowAnalysis df) Optimize a hyperblock.
static int	predicatesCombined() Return the number of predicates combined.
void	propagateCopies() Perform copy propagation in SSA.
void	removeDeadPredicateBlocks() Remove dead predicate blocks.
void	removePredicates() Remove predicates from a hyperblock.
void	removeRedundantLoads() Remove redundant loads within a predicate block.
protected void	removeSpillCode() Remove spill code from a hyperblock.
void	setBranchProbability(Hyperblock succ, double prob) Set the probability of branching to the specified hyperblock.
void	setBranchProbability(Instruction succ, double prob) Set the probability of branching to the specified hyperblock.
void	setLiveIn(BitVect in) Update the registers live-in and used by the hyperblock
void	setLiveOut(BitVect out) Update the registers live-out and defined by the hyperblock.
protected void	setLoopNumber(int loopNumber)
void	setPredicate(int reg) Set that a register is used as a predicate.
void	setVisited() Mark that the block has been visited.
java.lang.String	toString() Returns a description of the block.
void	updateFanout(int fanout) Update the fanout.
void	updateLastBlock() Find the last block in the PFG or create one if its missing.
static int	valueNumberCount() Return the number of instructions value numbering removed.
boolean	visited() Return true if the block has been visited.
static void	writeDotFlowGraph(Hyperblock hbStart, java.lang.String filename) Write a dot file that shows the hyperblock flow graph.

Methods inherited from class scale.backend.Node

addInEdge, addOutEdge, deleteInEdge, deleteOutEdge, getInEdge, getInEdges, getLabel, getOutEdge, getOutEdges, getTag, indexOfInEdge, indexOfOutEdge, numInEdges, numOutEdges, pushInEdges, pushInEdges, pushOutEdges, pushOutEdges, replaceInEdge, replaceOutEdge, setLabel, setTag, unlink

Methods inherited from class scale.common.Root

addAnnotation, allAnnotations, allMatchingAnnotations, getAnnotation, 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

enableInterBlockPredicateMinimization

public static boolean enableInterBlockPredicateMinimization

If inter-block predicate minimization should be performed.

enableIntraBlockPredicateMinimization

public static boolean enableIntraBlockPredicateMinimization

If intra-block predicate minimization should be performed.

enableRedundantLoadRemoval

public static boolean enableRedundantLoadRemoval

If redundant loads should be removed.

doFastStoreNullification

public static boolean doFastStoreNullification

There are two ways to nullify store instructions:
(1) null t100 (2) null_t t100 sd_t t100, t100 [1] mov t101, t100 null t101 mov t102, t100 sd_t t101, t101 [2] sd_t t101, t101 [1] sd_t t102, t102 [2]
If this is set to true we do (1) which inserts a null for every store. This is "fast" because it has the shortest dependence height. It may have more fanout because the predicate has to be sent to every store but the store can issue as soon as the predicate resolves.
If this is set to false we do (2) which uses a single null for multiple stores. This is "slow" because it has the longest dependence height and requires fanout when there is more than one store to be nullified.

useMinMaxLoadStoreAssignment

public static boolean useMinMaxLoadStoreAssignment

If true, loads are given a unique LSID and stores are given the minimal number of LSIDs. This allows all loads to be unpredicated and requires the fewest instructions for store nullification. Otherwise, all memory instructions are given unique ids.

unpredicateLoads

public static boolean unpredicateLoads

To unpredicate a load it cannot share a LSID with another load. Therefore, loads will only be unpredicated when using an LSID assignment policy that maximizes the identifiers assigned to loads.

noLoadStorePredicateField

public static boolean noLoadStorePredicateField

True if load and store instructions do not have a predicate field. This should always be false when compiling to the TRIPS ISA.

PREDICATE_TOP

public static final int PREDICATE_TOP

Predicate only the top of dependence chains.

See Also:

Constant Field Values

PREDICATE_BOTTOM

public static final int PREDICATE_BOTTOM

Predicate only the bottom of dependence chains.

See Also:

Constant Field Values

intraBlockDefault

public static int intraBlockDefault

The default intra-block predicate minimization.

Constructor Detail

Hyperblock

public Hyperblock(Instruction first,
                  Trips2RegisterSet registers)

Construct a new hyperblock starting with the given instruction.

Parameters:

first - the first instruction in the hyperblock.

registers - the RegisterSet to use.

Hyperblock

public Hyperblock(PredicateBlock start,
                  Trips2RegisterSet registers)

Construct a new hyperblock from a PredicateBlock.

Parameters:

start - the block which starts the hyperblock.

registers - the RegisterSet to use.

Hyperblock

public Hyperblock(PredicateBlock start,
                  BitVect predicates,
                  Trips2RegisterSet registers)

Construct a new hyperblock from a PredicateBlock.

Parameters:

start - the block which starts the hyperblock.

end - the block which ends the hyperblock.

registers - the RegisterSet to use.

Method Detail

nullWritesInserted

public static int nullWritesInserted()

Return the number of nulls inserted.

predicatesCombined

public static int predicatesCombined()

Return the number of predicates combined.

loadsRemoved

public static int loadsRemoved()

Return the number of loads which were removed.

instructionsMerged

public static int instructionsMerged()

Return the number of instructions merged.

valueNumberCount

public static int valueNumberCount()

Return the number of instructions value numbering removed.

removeDeadPredicateBlocks

public void removeDeadPredicateBlocks()

Remove dead predicate blocks.
If a predicate block becomes empty, and it was the only use of a predicate, then the predicate block needs to be removed to maintain the PFG.
For example,
pb1: mov_t p2, #1 -> pb3 pb2: mov_f p2, #1 -> pb3 pb3: empty -> pb4
PB1 and PB2 both create predicate {p2,true} and their successor is PB3 which has no instructions. When we go into SSA form, no phi will be inserted for p2 because there is no instruction that references it. When SSA tries to rename the predicate for PB3 to maintain the PFG, it will fail because p2 has not been seen and there is nothing on the rename stack for it. We remove PB3 from the PFG and make the successor of PB1 and PB2, PB4 to maintain the PFG.

determinePredicatesBranches

public void determinePredicatesBranches()

Compute the set of predicates and number of branches.

hasCall

public final boolean hasCall()

Return true if this hyperblock contains a function call.

hasBranchTo

public final boolean hasBranchTo(Hyperblock s)

Return true if there is a branch to the specified hyperblock.

hasCallTo

public final boolean hasCallTo(Hyperblock s)

Return true if there is a call to the specified hyperblock.

hasSwitch

public final boolean hasSwitch()

Return true if this hyperblock contains a switch statement.

getBranchProbability

public final double getBranchProbability(Hyperblock succ)

Return the probability of branching to the specified hyperblock.

setBranchProbability

public final void setBranchProbability(Hyperblock succ,
                                       double prob)

Set the probability of branching to the specified hyperblock.

setBranchProbability

public final void setBranchProbability(Instruction succ,
                                       double prob)

Set the probability of branching to the specified hyperblock.

isSimpleLoop

public final boolean isSimpleLoop()

Return true if this hyperblock contains a back-edge to itself.

getLiveIn

public final BitVect getLiveIn()

Return the registers live-in to (and used in) the hyperblock

setLiveIn

public final void setLiveIn(BitVect in)

Update the registers live-in and used by the hyperblock

getLiveOut

public final BitVect getLiveOut()

Return the registers live-out of (and define by) the hyperblock

setLiveOut

public final void setLiveOut(BitVect out)

Update the registers live-out and defined by the hyperblock.

getPredicates

public final BitVect getPredicates()

Get the predicates for the hyperblock.

clearPredicates

public final void clearPredicates()

Clear the predicates used in this hyperblock.

isPredicate

public final boolean isPredicate(int reg)

Return true if the register is used as a predicate.

setPredicate

public final void setPredicate(int reg)

Set that a register is used as a predicate.

copy

public Hyperblock copy()

Copy the hyperblock.

getNextPFGLevel

public final Vector<PredicateBlock> getNextPFGLevel(Vector<PredicateBlock> wl)

Given a set of PFG nodes that are the same depth from the root node, this routine will return the PFG nodes which are one level deeper.

getFirstBlock

public final PredicateBlock getFirstBlock()

Return the first block in the PFG.

getLastBlock

public final PredicateBlock getLastBlock()

Return the last block in the PFG.

findLastBlock

public void findLastBlock()

Find the last block in the PFG.
There must be a path from the root to the last block or the PFG is corrupt.

updateLastBlock

public final void updateLastBlock()

Find the last block in the PFG or create one if its missing.
Useful when fixing the PFG as its being pulled apart.

getDominanceFrontier

public final DominanceFrontier getDominanceFrontier()

Return the dominance frontier information for the PFG.

getDomination

public final Domination getDomination()

Return the dominator information for the PFG.

invalidateDomination

public final void invalidateDomination()

Clear the dominator information for the PFG.

dumpPredicateFlowGraph

public final void dumpPredicateFlowGraph()

Output the predicate flow graph for debugging.

writeDotFlowGraph

public static void writeDotFlowGraph(Hyperblock hbStart,
                                     java.lang.String filename)

Write a dot file that shows the hyperblock flow graph.

getBlockName

public java.lang.String getBlockName()

Returns the name of the block, as seen in the TIL.

computeTargets

public final IntMap<Vector<java.lang.Integer>> computeTargets(Stack<Node> wl,
                                                              BitVect mov3)

Compute the number of targets for each instruction.
Returns a map of vectors indexed by the register number. Since multiple instructions may define a register, there is one entry for each instruction in the vector. The entries represent the number of targets for that instruction.
This routine also computes if a target can be fanned out with a mov3 instruction. The bit vector will be true if a mov3 cannot be used.

isLegalBlock

public boolean isLegalBlock(boolean beforeRegisterAllocation)

Return true if this is a well formed TRIPS block.

getBlockSize

public final int getBlockSize()

Return the size of the instructions in the block (not including fanout).

getFanout

public final int getFanout()

Return the estimated fanout for the block.

updateFanout

public final void updateFanout(int fanout)

Update the fanout.

numBranches

public final int numBranches()

Return the number of branches in the block.

maxLSID

public final int maxLSID()

Return the highest assigned load/store ID in the block.

numSpills

public final int numSpills()

Return the number of spill instructions in the block.

getSpillSize

public final int getSpillSize()

Return the estimated size of the spills in the block.

addSpill

public final void addSpill(PredicateBlock block,
                           Instruction inst)

Add a spill to the hyperblock.

hasDummyStores

public final boolean hasDummyStores()

Return true if the block contains stores inserted for nullification.

assignLoadStoreQueueIds

protected void assignLoadStoreQueueIds()

Assign load/store queue ids and nullify stores.

noLoadStorePredicateField

protected void noLoadStorePredicateField()

If load and store instructions cannot be predicated this method ensures that atleast one of the instructions in the dependence chain is predicated.
For loads we insert a predicated mov as the only use of the load. For stores we search up the dependence chain looking for a predicate or we predicate one of the store's operands.

mergeInstructions

protected void mergeInstructions(boolean includeBranches)

Merge instructions.

removeRedundantLoads

public void removeRedundantLoads()

Remove redundant loads within a predicate block. If a load is identified as redundant, and there is no intervening store to the same memory location, we can remove the redundant load.
This routine assumes that register allocation has been done and all displacements are known.

propagateCopies

public void propagateCopies()

Perform copy propagation in SSA.

interBlockPredicateMinimization

protected boolean interBlockPredicateMinimization(DataflowAnalysis df)

Perform inter-block predicate minimization.
This optimization needs the live-outs for each predicate block.

removePredicates

public void removePredicates()

Remove predicates from a hyperblock.

removeSpillCode

protected void removeSpillCode()

Remove spill code from a hyperblock.
A hyperblock cannot be split if it contains spill code.

assignBranchIds

public final void assignBranchIds(boolean verbose)

Assign branch identifiers.
We can encode up to 8 exit using a maximum predicate tree depth of 3. Any exit that exceeds this is encoded as 0.

optimize

public final void optimize(boolean removeLoads,
                           DataflowAnalysis df)

Optimize a hyperblock.
The main goal of this routine is to reduce the block size to allow additional blocks to be merged.

enterSSA

public final void enterSSA()

Convert the PFG into SSA form.

leaveSSA

public final void leaveSSA(boolean removeReadWrite)

Convert the hyperblock out of SSA form.

Parameters:

removeReadWrite - if read and write instructions should be removed when converting out of SSA form. SSA form can only be re-entered if read and write instructions are removed.

analyzeLeaveSSA

public final void analyzeLeaveSSA()

Update the block statistics before leaving SSA form.

inSSA

public final boolean inSSA()

Return true if the hyperblock is in SSA form.

getSSA

public final SSA getSSA()

Return the ssa instance for this hyperblock.

setVisited

public final void setVisited()

Mark that the block has been visited.

Specified by:

setVisited in class Node

visited

public final boolean visited()

Return true if the block has been visited.

Specified by:

visited in class Node

nextVisit

public final void nextVisit()

The next unique color for traversing the graph.

Specified by:

nextVisit in class Node

enterHyperblockFlowGraph

public static Hyperblock enterHyperblockFlowGraph(Instruction first,
                                                  Trips2Generator gen)

leaveHyperblockFlowGraph

public static Instruction leaveHyperblockFlowGraph(Hyperblock hbStart,
                                                   Trips2Generator gen)

Convert a function in hyperblock form to straight-line form. Returns the new firstInstruction (should be the BeginMarker).

computeHyperblockFlowGraph

public static void computeHyperblockFlowGraph(Vector<Hyperblock> hbs,
                                              HashMap<Instruction,Hyperblock> entries)

Compute the hyperblock flow graph. The caller should provide the set of entry points to use.
TODO Does this belong in the block splitter?

dumpHyperblockFlowGraph

public static void dumpHyperblockFlowGraph(Hyperblock hbStart)

Output the hyperblock flow graph for debugging.

getDisplayName

public java.lang.String getDisplayName()

Return the unique node label.

Specified by:

getDisplayName in interface DisplayNode

Overrides:

getDisplayName in class Root

getDisplayLabel

public java.lang.String getDisplayLabel()

Return a String suitable for labeling this node in a graphical display.

Specified by:

getDisplayLabel in interface DisplayNode

Overrides:

getDisplayLabel in class Root

toString

public final java.lang.String toString()

Returns a description of the block.

Overrides:

toString in class Root

getLoopNumber

public int getLoopNumber()

setLoopNumber

protected void setLoopNumber(int loopNumber)

getDisplayColorHint

public DColor getDisplayColorHint()

Return a String specifying the color to use for coloring this node in a graphical display.

Specified by:

getDisplayColorHint in interface DisplayNode

Overrides:

getDisplayColorHint in class Root

See Also:

DColor

getDisplayShapeHint

public DShape getDisplayShapeHint()

Return a String specifying a shape to use when drawing this node in a graphical display.

Specified by:

getDisplayShapeHint in interface DisplayNode

Overrides:

getDisplayShapeHint in class Root

See Also:

DShape