scale.backend.trips2
Class PredicateBlock

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

All Implemented Interfaces:

AnnotationInterface, DisplayNode

public class PredicateBlock
extends Node

This class represents a predicated basic block.

$Id: PredicateBlock.java,v 1.53 2007-10-04 19:57:59 burrill Exp $

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

A predicated block is similar to a traditional basic block, except that a predicate can be associated with the block. All instructions in the block are predicated on that predicate. If no predicate is specified, all instructions are considered to be unpredicated.

A hyperblock is made up of a collection of predicated blocks.

Field Summary

Fields inherited from class scale.backend.Node

color, label, predecessors, successors, tag

Constructor Summary

PredicateBlock()
Construct an unpredicated block.

PredicateBlock(Instruction first, Instruction last)
Construct an unpredicated block beginning with first.

PredicateBlock(int[] predicates, boolean predicatedOnTrue)
Construct a predicated block.

PredicateBlock(int predicate, boolean predicatedOnTrue)
Construct a predicated block.

Method Summary

void	addSpill(int size) Add a spill to the predicate block.
void	analyze(IntMap<Vector<java.lang.Integer>> targets, IntMap<java.lang.Integer> uses, BitVect mov3) This routine will determine the block size (including estimated fanout), the highest load/store queue id, and the number of branches.
void	appendInstruction(Instruction inst) Append the instruction to the end of the predicate block.
void	appendInstruction(Instruction inst, SSA ssa) Append the instruction to the end of the predicate block and maintain SSA form.
static int	blocksSplit() Return the number of blocks split.
PredicateBlock	copy() Copy the block.
PredicateBlock	cut(Instruction split, Trips2Generator gen) Return a new block starting with the instructions after the split point.
static int	dummyStores() Return the number of dummy stores inserted.
int	estimateFanout(Instruction inst, IntMap<Vector<java.lang.Integer>> targets, IntMap<java.lang.Integer> uses, BitVect mov3) This routine computes the fanout needed for the operands of an instruction.
int	estimateNumInstructions(Instruction inst) Return the number of real instructions needed to represent this instruction.
int	getBlockSize() Return the size of the instructions in the block (not including fanout).
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.
int	getFanout() Return the estimated fanout for the block.
Instruction	getFirstInstruction() Return the first instruction in this block.
Instruction	getLastInstruction() Return the last instruction in this block.
int	getPredicate() Return the predicate for this block.
int[]	getPredicates() Return the predicates for this block.
int	getSpillSize() Return the size of the spills in the block.
java.lang.String	getStats()
boolean	hasBranch() Return true if this block has a branch.
boolean	hasCall() Return true if this block has a function call.
boolean	hasDummyStores() Return true if this block has any "dummy" stores inserted for store nullification.
boolean	hasSwitch() Return true if this block has a switch.
Instruction	insertInstructionAfter(Instruction after, Instruction inst) Insert an instruction after the specified instruction.
void	insertInstructionAtHead(Instruction inst) Insert an instruction at the beginning of the block.
void	insertInstructionBeforeBranch(Instruction inst) Insert an instruction at the end of a block before the branch (if it exists).
boolean	isLegalBlock() Return true if this is a well formed TRIPS block.
boolean	isPredicated() Return true if the instruction is predicated.
boolean	isPredicatedOnTrue() Return true if this block is predicated on the predicate evaluating to true.
boolean	isSplitPoint() Return true if this block is a good candidate for reverse if-conversion.
int	maxLSID() Return the highest assigned load/store ID in the block.
void	nextVisit() The next unique color for traversing the graph.
protected void	nullifyStores(BitVect nulls, SSA ssa, Trips2RegisterSet registers) Insert a null and a dummy store in the block.
static int	nullStoresInserted() Return the number of nulls inserted.
int	numSpills() Return the number of spills in the block.
protected void	removeDummyStores(SSA ssa) Remove any dummy stores that were inserted by store nullification.
void	removeInstruction(Instruction inst) Delete the specified instruction.
void	removeInstruction(Instruction prev, Instruction inst) Delete the specified instruction.
void	removePredicates() Remove the predicates from a block.
protected void	removeSpillCode() Remove spill code from a block.
void	setFirstInstruction(Instruction first) Set the first instruction in this block.
void	setHasBranch() Set that the block has a branch.
void	setLastInstruction(Instruction last) Set the last instruction in this block.
void	setMaxLSID(int maxLSID)
void	setPredicate(int predicate) Set the predicate for this block.
void	setPredicate(int predicate, boolean onTrue) Set the predicate for this block.
void	setPredicates(int[] predicates) Set the predicates for this block.
void	setSplitPoint() Set that the block is a good candidate for reverse if-conversion.
void	setVisited() Mark that the block has been visited.
java.lang.String	toString() Returns a description of the block.
boolean	visited() Return true if the block has been visited.

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

Constructor Detail

PredicateBlock

public PredicateBlock()

Construct an unpredicated block.

PredicateBlock

public PredicateBlock(Instruction first,
                      Instruction last)

Construct an unpredicated block beginning with first.

PredicateBlock

public PredicateBlock(int predicate,
                      boolean predicatedOnTrue)

Construct a predicated block.

PredicateBlock

public PredicateBlock(int[] predicates,
                      boolean predicatedOnTrue)

Construct a predicated block.

Method Detail

blocksSplit

public static int blocksSplit()

Return the number of blocks split.

nullStoresInserted

public static int nullStoresInserted()

Return the number of nulls inserted.

dummyStores

public static int dummyStores()

Return the number of dummy stores inserted.

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

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.

maxLSID

public final int maxLSID()

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

setMaxLSID

public final void setMaxLSID(int maxLSID)

isSplitPoint

public final boolean isSplitPoint()

Return true if this block is a good candidate for reverse if-conversion.

setSplitPoint

public final void setSplitPoint()

Set that the block is a good candidate for reverse if-conversion.

hasBranch

public final boolean hasBranch()

Return true if this block has a branch.

hasCall

public final boolean hasCall()

Return true if this block has a function call.

hasSwitch

public final boolean hasSwitch()

Return true if this block has a switch.

setHasBranch

public final void setHasBranch()

Set that the block has a branch.

numSpills

public final int numSpills()

Return the number of spills in the block.

getSpillSize

public final int getSpillSize()

Return the size of the spills in the block.

addSpill

public final void addSpill(int size)

Add a spill to the predicate block.
This method is used during register allocation to adjust the stats for the block during spilling.
Do not change the fanout in this routine. Add any fanout to the spillSize for the block instead.

hasDummyStores

public final boolean hasDummyStores()

Return true if this block has any "dummy" stores inserted for store nullification.

appendInstruction

public final void appendInstruction(Instruction inst)

Append the instruction to the end of the predicate block.

appendInstruction

public final void appendInstruction(Instruction inst,
                                    SSA ssa)

Append the instruction to the end of the predicate block and maintain SSA form.

removeInstruction

public final void removeInstruction(Instruction inst)

Delete the specified instruction. Since this routine scans the list to find the previous instruction, it is O(n). Therefore, use the other form if possible.

removeInstruction

public final void removeInstruction(Instruction prev,
                                    Instruction inst)

Delete the specified instruction.

insertInstructionAfter

public final Instruction insertInstructionAfter(Instruction after,
                                                Instruction inst)

Insert an instruction after the specified instruction.

insertInstructionAtHead

public final void insertInstructionAtHead(Instruction inst)

Insert an instruction at the beginning of the block.
Do not use this method in SSA form unless you understand what you are doing. There may be a phi instruction in the predicate block you are inserting into that defines the predicate for the predicate block. Calling this method will insert the instruction before the phi! For example,
null_t<217> ... // trying to insert a null in the head phi_t<200> 217 ... // but the predicate is defined here by the phi!

insertInstructionBeforeBranch

public final void insertInstructionBeforeBranch(Instruction inst)

Insert an instruction at the end of a block before the branch (if it exists).
TODO This is no longer needed

getFirstInstruction

public final Instruction getFirstInstruction()

Return the first instruction in this block.

setFirstInstruction

public final void setFirstInstruction(Instruction first)

Set the first instruction in this block.

getLastInstruction

public final Instruction getLastInstruction()

Return the last instruction in this block.

setLastInstruction

public final void setLastInstruction(Instruction last)

Set the last instruction in this block.

getPredicate

public final int getPredicate()

Return the predicate for this block.

getPredicates

public final int[] getPredicates()

Return the predicates for this block.

removePredicates

public final void removePredicates()

Remove the predicates from a block.

setPredicate

public final void setPredicate(int predicate)

Set the predicate for this block.

setPredicates

public final void setPredicates(int[] predicates)

Set the predicates for this block.

setPredicate

public final void setPredicate(int predicate,
                               boolean onTrue)

Set the predicate for this block.

isPredicatedOnTrue

public final boolean isPredicatedOnTrue()

Return true if this block is predicated on the predicate evaluating to true.

isPredicated

public final boolean isPredicated()

Return true if the instruction is predicated.

analyze

public final void analyze(IntMap<Vector<java.lang.Integer>> targets,
                          IntMap<java.lang.Integer> uses,
                          BitVect mov3)

This routine will determine the block size (including estimated fanout), the highest load/store queue id, and the number of branches.

estimateFanout

public final int estimateFanout(Instruction inst,
                                IntMap<Vector<java.lang.Integer>> targets,
                                IntMap<java.lang.Integer> uses,
                                BitVect mov3)

This routine computes the fanout needed for the operands of an instruction. It is a helper routine for Hyperblock.estimateFanout().

estimateNumInstructions

public final int estimateNumInstructions(Instruction inst)

Return the number of real instructions needed to represent this instruction.

isLegalBlock

public final boolean isLegalBlock()

Return true if this is a well formed TRIPS block. This method is for use by the block splitter before register allocation.

cut

public final PredicateBlock cut(Instruction split,
                                Trips2Generator gen)

Return a new block starting with the instructions after the split point. After cutting the block estimates are not correct. The caller is responsible for updating the estimates.

removeSpillCode

protected void removeSpillCode()

Remove spill code from a block.

nullifyStores

protected void nullifyStores(BitVect nulls,
                             SSA ssa,
                             Trips2RegisterSet registers)

Insert a null and a dummy store in the block.

removeDummyStores

protected void removeDummyStores(SSA ssa)

Remove any dummy stores that were inserted by store nullification. Also remove null instructions inserted for store nullification. A null without an "rb" field is used to distinguish store nullification from write nullification.

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

getStats

public java.lang.String getStats()

toString

public final java.lang.String toString()

Returns a description of the block.

Overrides:

toString in class Root

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

copy

public PredicateBlock copy()

Copy the block.