cfg
Class BasicBlock

java.lang.Object
  extended by cfg.BasicBlock

public class BasicBlock
extends java.lang.Object

A class representing a basic block, which is an individual node in the control flow graph. Each basic block is made up of a label (for control transfers targetting this basic block) and a list of Three-Address Code (TAC) instructions. For basic blocks that are not reached via a control transfer, the label is null.

Author:
Marc Corliss and Lori Pietraszek

Constructor Summary
BasicBlock(int startLineNum, int loopCnt, int ifCnt)
          BasicBlock constructor
 
Method Summary
 void addComment(java.lang.String comment)
          Add a comment to basic block (for debugging) (this can be called multiple times for multi-line comments)
 void addInEdge(BasicBlock b)
          Add an incoming edge from another control flow block Also adds outgoing edge from parameter to this block
 void addInst(TACInst inst)
          Append instruction into basic block Throws exception if attempting to place an instruction after an IF (which should terminate block)
 void addInst(TACInst inst, int n)
          Add instruction into specified place in the basic block Shifts instructions at specified position to the right one Throws exception if n is greater than the size or attempt to place an instruction after an IF (which should terminate block)
 void addInstAfter(TACInst inst1, TACInst inst2)
          Adds inst1 after inst2.
 void addInstBefore(TACInst inst1, TACInst inst2)
          Adds inst1 before inst2.
 void addOutEdge(BasicBlock b)
          Add an outgoing edge to another control flow block Also adds incoming edge from this block to parameter
 void check()
          Check block for errors throws an exception if block is malformed
 boolean containsInEdge(BasicBlock bb)
          Does this block contain another block as an in edge?
 boolean containsOutEdge(BasicBlock bb)
          Does this block contain another block as an out edge?
 java.util.Set<java.lang.String> getAvailableAnalyses()
          Returns a set of names of available dataflow analyses results.
static BasicBlock getBlock(int id)
          Returns basic block by ID.
 java.lang.String getComments()
          Get comments for instruction
 java.util.Set<BasicBlock> getDominanceFrontier()
          Returns the set of BasicBlocks in the dominance frontier.
 java.util.Set<?> getEntrySet(java.lang.String analysis)
          Returns the block entry set for the given analysis.
 java.util.Set<?> getExitSet(java.lang.String analysis)
          Returns the block exit set for the given analysis.
 java.lang.String getFullString()
          Returns string representation of entire basic block
 int getID()
          Get the identifier of this basic block
 int getIfCnt()
          Get the if count for this block, i.e., number of if statements this block is contained in (note: predicate considered part of the if statement)
 BasicBlock getImmediateDominator()
          Returns the immediate dominator of the block.
 int getIndexOf(TACInst inst)
          Returns the index of inst in block, or -1 if not found.
 java.util.List<TACInst> getInstructions()
          Returns a collection with the instructions in this block.
 int getLoopCnt()
          Get the loop count for this block, i.e., number of loops this block is contained in (note: predicate considered part of the loop)
 BasicBlock getNthInEdge(int n)
          Get nth incoming edge (basic block)
 TACInst getNthInst(int n)
          Get the nth instruction Note: throws an exception if there aren't at least n+1 instructions
 BasicBlock getNthOutEdge(int n)
          Get nth outgoing edge (basic block)
 int getNumInEdges()
          Get number of incoming edges
 int getNumInsn()
          Get the number of instructions at this basic block
 int getNumOutEdges()
          Get number of outgoing edges
 int getStartLineNum()
          Get the starting source line number of this basic block
 int indexOf(TACInst inst)
          Get the index of some instruction
 void print()
          Prints basic block -- for debugging
 void printAll()
          Prints basic block and all connected basic blocks -- for debugging Must be called using entrance block as reference object
 void removeAllInEdges()
          Remove all incoming edges from other control flow blocks Also removes outgoing edges from source basic blocks
 void removeAllOutEdges()
          Remove all outgoing edges to other control flow blocks Also removes incoming edges in source basic blocks
 void removeComments()
          Remove comments from an instruction
 void removeInEdge(BasicBlock b)
          Remove an incoming edge to another control flow block Also removes outgoing edge from parameter to this block
 void removeInst(TACInst inst)
          Removes given instruction from block (if found).
 void removeNthInst(int n)
          Remove the nth instruction Note: throws an exception if there aren't at least n+1 instructions
 void removeOutEdge(BasicBlock b)
          Remove an outgoing edge to another control flow block Also removes incoming edge from parameter to this block
 void replaceInEdge(BasicBlock remove, BasicBlock add)
          Replaces the incoming edge with an edge to the new control flock block.
 void replaceOutEdge(BasicBlock remove, BasicBlock add)
          Replaces the outgoing edge with an edge to the new control flock block.
 void setDominanceFrontier(java.util.Set<BasicBlock> df)
          Sets the set of BasicBlocks in the dominance frontier.
 void setEntrySet(java.lang.String analysis, java.util.Set<?> data)
          Sets the block entry result sets for given analysis.
 void setExitSet(java.lang.String analysis, java.util.Set<?> data)
          Sets the block exit result sets for given analysis.
 void setIfCnt(int ifCnt)
          Set the if count for this block, i.e., number of if statements this block is contained in (note: predicate considered part of the if)
 void setImmediateDominator(BasicBlock idom)
          Sets the immediate dominator of the block.
 void setLoopCnt(int loopCnt)
          Set the loop count for this block, i.e., number of loops this block is contained in (note: predicate considered part of the loop)
 void setNthInst(int n, TACInst inst)
          Set the nth instruction -- replaces the previous nth instruction with the specified instruction Note: throws an exception if there aren't at least n+1 instructions
 java.lang.String toString()
          Returns string identifier for basic block
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

BasicBlock

public BasicBlock(int startLineNum,
                  int loopCnt,
                  int ifCnt)
BasicBlock constructor

Parameters:
startLineNum - starting source line number of this block (for debugging -- does not have to be exact)
loopCnt - loop count (# loops block is contained in -- note: predicate considered part of loop)
ifCnt - if count (# if statements block is contained in -- note: predicate considered part of if statement)
Method Detail

getBlock

public static BasicBlock getBlock(int id)
Returns basic block by ID.

Parameters:
id -
Returns:
BasicBlock with id or null

getID

public int getID()
Get the identifier of this basic block

Returns:
identifier

getStartLineNum

public int getStartLineNum()
Get the starting source line number of this basic block

Returns:
starting line number

addInst

public void addInst(TACInst inst)
Append instruction into basic block Throws exception if attempting to place an instruction after an IF (which should terminate block)

Parameters:
inst - three-address code (TAC) instruction

addInst

public void addInst(TACInst inst,
                    int n)
Add instruction into specified place in the basic block Shifts instructions at specified position to the right one Throws exception if n is greater than the size or attempt to place an instruction after an IF (which should terminate block)

Parameters:
inst - three-address code (TAC) instruction
n - position to place

addInstBefore

public void addInstBefore(TACInst inst1,
                          TACInst inst2)
Adds inst1 before inst2.

Parameters:
inst1 -
inst2 -

addInstAfter

public void addInstAfter(TACInst inst1,
                         TACInst inst2)
Adds inst1 after inst2.

Parameters:
inst1 -
inst2 -

getIndexOf

public int getIndexOf(TACInst inst)
Returns the index of inst in block, or -1 if not found.

Parameters:
inst -
Returns:
index of inst in block, or -1 if not in block

getNumInsn

public int getNumInsn()
Get the number of instructions at this basic block

Returns:
number of instructions

getInstructions

public java.util.List<TACInst> getInstructions()
Returns a collection with the instructions in this block.

Returns:
List of TACInst

indexOf

public int indexOf(TACInst inst)
Get the index of some instruction

Parameters:
inst - instruction to find the index of
Returns:
index (<0 if not found)

getNthInst

public TACInst getNthInst(int n)
Get the nth instruction Note: throws an exception if there aren't at least n+1 instructions

Parameters:
n - index of instruction to get
Returns:
nth instruction

setNthInst

public void setNthInst(int n,
                       TACInst inst)
Set the nth instruction -- replaces the previous nth instruction with the specified instruction Note: throws an exception if there aren't at least n+1 instructions

Parameters:
n - index of instruction to get
inst - replacement instruction

removeNthInst

public void removeNthInst(int n)
Remove the nth instruction Note: throws an exception if there aren't at least n+1 instructions

Parameters:
n - index of instruction to remove

removeInst

public void removeInst(TACInst inst)
Removes given instruction from block (if found).

Parameters:
inst - TACInst to remove

addInEdge

public void addInEdge(BasicBlock b)
Add an incoming edge from another control flow block Also adds outgoing edge from parameter to this block

Parameters:
b - incoming basic block

addOutEdge

public void addOutEdge(BasicBlock b)
Add an outgoing edge to another control flow block Also adds incoming edge from this block to parameter

Parameters:
b - outgoing basic block

removeInEdge

public void removeInEdge(BasicBlock b)
Remove an incoming edge to another control flow block Also removes outgoing edge from parameter to this block

Parameters:
b - incoming basic block

removeOutEdge

public void removeOutEdge(BasicBlock b)
Remove an outgoing edge to another control flow block Also removes incoming edge from parameter to this block

Parameters:
b - outgoing basic block

removeAllInEdges

public void removeAllInEdges()
Remove all incoming edges from other control flow blocks Also removes outgoing edges from source basic blocks


removeAllOutEdges

public void removeAllOutEdges()
Remove all outgoing edges to other control flow blocks Also removes incoming edges in source basic blocks


replaceInEdge

public void replaceInEdge(BasicBlock remove,
                          BasicBlock add)
Replaces the incoming edge with an edge to the new control flock block. The order of the edges is not changed. This does not change the edges in other blocks.

Parameters:
remove - the edge to remove
add - the edge to add

replaceOutEdge

public void replaceOutEdge(BasicBlock remove,
                           BasicBlock add)
Replaces the outgoing edge with an edge to the new control flock block. The order of the edges is not changed. This does not change the edges in other blocks.

Parameters:
remove - the edge to remove
add - the edge to add

getNthInEdge

public BasicBlock getNthInEdge(int n)
Get nth incoming edge (basic block)

Parameters:
n - index of incoming edge to get
Returns:
nth incoming basic block

getNthOutEdge

public BasicBlock getNthOutEdge(int n)
Get nth outgoing edge (basic block)

Parameters:
n - index of outgoing edge to get
Returns:
nth outgoing basic block

getNumInEdges

public int getNumInEdges()
Get number of incoming edges

Returns:
number of incoming edges

getNumOutEdges

public int getNumOutEdges()
Get number of outgoing edges

Returns:
number of outgoing edges

containsInEdge

public boolean containsInEdge(BasicBlock bb)
Does this block contain another block as an in edge?

Parameters:
bb - block to check if contains
Returns:
flag indicating whether block is contained as an in edge

containsOutEdge

public boolean containsOutEdge(BasicBlock bb)
Does this block contain another block as an out edge?

Parameters:
bb - block to check if contains
Returns:
flag indicating whether block is contained as an out edge

getLoopCnt

public int getLoopCnt()
Get the loop count for this block, i.e., number of loops this block is contained in (note: predicate considered part of the loop)

Returns:
loop count

setLoopCnt

public void setLoopCnt(int loopCnt)
Set the loop count for this block, i.e., number of loops this block is contained in (note: predicate considered part of the loop)

Parameters:
loopCnt - new loop count

getIfCnt

public int getIfCnt()
Get the if count for this block, i.e., number of if statements this block is contained in (note: predicate considered part of the if statement)

Returns:
if count

setIfCnt

public void setIfCnt(int ifCnt)
Set the if count for this block, i.e., number of if statements this block is contained in (note: predicate considered part of the if)

Parameters:
ifCnt - new if count

check

public void check()
Check block for errors throws an exception if block is malformed


getComments

public java.lang.String getComments()
Get comments for instruction

Returns:
comments for instruction

addComment

public void addComment(java.lang.String comment)
Add a comment to basic block (for debugging) (this can be called multiple times for multi-line comments)

Parameters:
comment - comment to add

removeComments

public void removeComments()
Remove comments from an instruction


toString

public java.lang.String toString()
Returns string identifier for basic block

Overrides:
toString in class java.lang.Object
Returns:
string identifier for basic block

getFullString

public java.lang.String getFullString()
Returns string representation of entire basic block

Returns:
string representation of entire basic block

print

public void print()
Prints basic block -- for debugging


printAll

public void printAll()
Prints basic block and all connected basic blocks -- for debugging Must be called using entrance block as reference object


getImmediateDominator

public BasicBlock getImmediateDominator()
Returns the immediate dominator of the block.

Returns:
BasicBlock

setImmediateDominator

public void setImmediateDominator(BasicBlock idom)
Sets the immediate dominator of the block.

Parameters:
idom - BasicBlock

getAvailableAnalyses

public java.util.Set<java.lang.String> getAvailableAnalyses()
Returns a set of names of available dataflow analyses results.

Returns:
set of names to be used in getEntrySet/getExitSet.

getEntrySet

public java.util.Set<?> getEntrySet(java.lang.String analysis)
Returns the block entry set for the given analysis.

Parameters:
analysis - name of the analysis.
Returns:
result set.

setEntrySet

public void setEntrySet(java.lang.String analysis,
                        java.util.Set<?> data)
Sets the block entry result sets for given analysis.

Parameters:
analysis - name of the analysis.
data - block entry result sets.

getExitSet

public java.util.Set<?> getExitSet(java.lang.String analysis)
Returns the block exit set for the given analysis.

Parameters:
analysis - name of the analysis.
Returns:
result set.

setExitSet

public void setExitSet(java.lang.String analysis,
                       java.util.Set<?> data)
Sets the block exit result sets for given analysis.

Parameters:
analysis - name of the analysis.
data - block exit result sets.

getDominanceFrontier

public java.util.Set<BasicBlock> getDominanceFrontier()
Returns the set of BasicBlocks in the dominance frontier.

Returns:
Set of BasicBlock

setDominanceFrontier

public void setDominanceFrontier(java.util.Set<BasicBlock> df)
Sets the set of BasicBlocks in the dominance frontier.

Parameters:
df - Set of BasicBlock