NControlFlowGraph (j-- (A Non-trivial Subset of Java))

java.lang.Object
- jminusminus.NControlFlowGraph

```
 class NControlFlowGraph
extends Object
```
Representation of a control flow graph (cfg) for a method.

Field Summary

Fields
Modifier and Type	Field and Description
`ArrayList<NBasicBlock>`	`basicBlocks` List of blocks forming the cfg for the method.
`static int`	`blockId` block identifier.
`ArrayList<String>`	`data` SPIM code for string literals added to the data segment.
`String`	`desc` Descriptor of the method this cfg corresponds to.
`static int`	`hirId` HIR instruction identifier.
`TreeMap<Integer,NHIRInstruction>`	`hirMap` Maps HIR instruction ids in this cfg to HIR instructions.
`ArrayList<NInterval>`	`intervals` Intervals allocated by the register allocation algorithm.
`String`	`labelPrefix` Used to construct jump labels in spim output.
`static int`	`lirId` HIR instruction identifier.
`static int`	`loopIndex` Loop identifier.
`int`	`maxIntervals` The total number of intervals.
`String`	`name` Name of the method this cfg corresponds to.
`int`	`offset` Stack offset counter..
`ArrayList<NPhysicalRegister>`	`pRegisters` Physical registers allocated for this cfg by the HIR to LIR conversion algorithm.
`static int`	`regId` Virtual register identifier.
`ArrayList<NRegister>`	`registers` Registers allocated for this cfg by the HIR to LIR conversion algorithm.

Constructor Summary

Constructors
Constructor and Description
`NControlFlowGraph(CLConstantPool cp, CLMethodInfo m)` Construct an NControlFlowGraph object for a method given the constant pool for the class containing the method and the object containing information about the method.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`allocatePhysicalRegisters()` Replace references to virtual registers in LIR instructions with references to physical registers.
`NBasicBlock`	`blockAt(int id)` The basic block at a particular instruction id.
`void`	`computeDominators(NBasicBlock block, NBasicBlock pred)` Compute the dominator of each block in this cfg recursively given the starting block and its predecessor.
`void`	`detectLoops(NBasicBlock block, NBasicBlock pred)` Implements loop detection algorithm to figure out if the specified block is a loop head or a loop tail.
`void`	`eliminateRedundantPhiFunctions()` Eliminate redundant phi functions of the form x = (y, x, x, ..., x) with y.
`void`	`hirToLir()` Convert the hir instructions in this cfg to lir instructions.
`void`	`optimize()` Carry out optimizations on the high-level instructions.
`void`	`orderBlocks()` Compute optimal ordering of the basic blocks in this cfg.
`void`	`removeUnreachableBlocks()` Remove blocks that cannot be reached from the begin block (B0).
`void`	`renumberLirInstructions()` Assign new ids to the LIR instructions in this cfg.
`void`	`resolvePhiFunctions()` Resolve the phi functions in this cfg, i.e., for each x = phi(x1, x2, ..., xn) generate an (LIR) move xi, x instruction at the end of the predecessor i of thte block defining the phi function; if the instruction there is a branch, add the instruction prior to the branch.
`void`	`tuplesToHir()` Convert tuples in each block to their high-level (HIR) representations.
`void`	`writeHirToStdOut(PrettyPrinter p)` Write the hir instructions in this cfg to STDOUT.
`void`	`writeIntervalsToStdOut(PrettyPrinter p)` Write the intervals in this cfg to STDOUT.
`void`	`writeLirToStdOut(PrettyPrinter p)` Write the lir instructions in this cfg to STDOUT.
`void`	`writeTuplesToStdOut(PrettyPrinter p)` Write the tuples in this cfg to STDOUT.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - blockId
```
public static int blockId
```
    block identifier.
  - hirId
```
public static int hirId
```
    HIR instruction identifier.
  - lirId
```
public static int lirId
```
    HIR instruction identifier.
  - regId
```
public static int regId
```
    Virtual register identifier.
  - offset
```
public int offset
```
    Stack offset counter..
  - loopIndex
```
public static int loopIndex
```
    Loop identifier.
  - name
```
public String name
```
    Name of the method this cfg corresponds to.
  - desc
```
public String desc
```
    Descriptor of the method this cfg corresponds to.
  - basicBlocks
```
public ArrayList<NBasicBlock> basicBlocks
```
    List of blocks forming the cfg for the method.
  - hirMap
```
public TreeMap<Integer,NHIRInstruction> hirMap
```
    Maps HIR instruction ids in this cfg to HIR instructions.
  - registers
```
public ArrayList<NRegister> registers
```
    Registers allocated for this cfg by the HIR to LIR conversion algorithm.
  - maxIntervals
```
public int maxIntervals
```
    The total number of intervals. This is used to name split children and grows as more intervals are created by spills.
  - pRegisters
```
public ArrayList<NPhysicalRegister> pRegisters
```
    Physical registers allocated for this cfg by the HIR to LIR conversion algorithm.
  - intervals
```
public ArrayList<NInterval> intervals
```
    Intervals allocated by the register allocation algorithm.
  - labelPrefix
```
public String labelPrefix
```
    Used to construct jump labels in spim output.
  - data
```
public ArrayList<String> data
```
    SPIM code for string literals added to the data segment.
- Constructor Detail
  - NControlFlowGraph
```
public NControlFlowGraph(CLConstantPool cp,
                 CLMethodInfo m)
```
    Construct an NControlFlowGraph object for a method given the constant pool for the class containing the method and the object containing information about the method.
    
    Parameters:
    cp - constant pool for the class containing the method.
    m - contains information about the method.
- Method Detail
  - detectLoops
```
public void detectLoops(NBasicBlock block,
               NBasicBlock pred)
```
    Implements loop detection algorithm to figure out if the specified block is a loop head or a loop tail. Also calculates the number of backward branches to the block.
    
    Parameters:
    block - a block.
    pred - block's predecessor or null.
  - removeUnreachableBlocks
```
public void removeUnreachableBlocks()
```
    Remove blocks that cannot be reached from the begin block (B0). Also removes these blocks from the predecessor lists.
  - computeDominators
```
public void computeDominators(NBasicBlock block,
                     NBasicBlock pred)
```
    Compute the dominator of each block in this cfg recursively given the starting block and its predecessor.
    
    Parameters:
    block - starting block.
    pred - block's predecessor.
  - tuplesToHir
```
public void tuplesToHir()
```
    Convert tuples in each block to their high-level (HIR) representations.
  - optimize
```
public void optimize()
```
    Carry out optimizations on the high-level instructions.
  - eliminateRedundantPhiFunctions
```
public void eliminateRedundantPhiFunctions()
```
    Eliminate redundant phi functions of the form x = (y, x, x, ..., x) with y.
  - hirToLir
```
public void hirToLir()
```
    Convert the hir instructions in this cfg to lir instructions.
  - resolvePhiFunctions
```
public void resolvePhiFunctions()
```
    Resolve the phi functions in this cfg, i.e., for each x = phi(x1, x2, ..., xn) generate an (LIR) move xi, x instruction at the end of the predecessor i of thte block defining the phi function; if the instruction there is a branch, add the instruction prior to the branch.
  - orderBlocks
```
public void orderBlocks()
```
    Compute optimal ordering of the basic blocks in this cfg.
  - blockAt
```
public NBasicBlock blockAt(int id)
```
    The basic block at a particular instruction id.
    
    Parameters:
    id - the (LIR) instruction id.
    
    Returns:
    the basic block.
  - renumberLirInstructions
```
public void renumberLirInstructions()
```
    Assign new ids to the LIR instructions in this cfg.
  - allocatePhysicalRegisters
```
public void allocatePhysicalRegisters()
```
    Replace references to virtual registers in LIR instructions with references to physical registers.
  - writeTuplesToStdOut
```
public void writeTuplesToStdOut(PrettyPrinter p)
```
    Write the tuples in this cfg to STDOUT.
    
    Parameters:
    p - for pretty printing with indentation.
  - writeHirToStdOut
```
public void writeHirToStdOut(PrettyPrinter p)
```
    Write the hir instructions in this cfg to STDOUT.
    
    Parameters:
    p - for pretty printing with indentation.
  - writeLirToStdOut
```
public void writeLirToStdOut(PrettyPrinter p)
```
    Write the lir instructions in this cfg to STDOUT.
    
    Parameters:
    p - for pretty printing with indentation.
  - writeIntervalsToStdOut
```
public void writeIntervalsToStdOut(PrettyPrinter p)
```
    Write the intervals in this cfg to STDOUT.
    
    Parameters:
    p - for pretty printing with indentation.

Class NControlFlowGraph

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

blockId

hirId

lirId

regId

offset

loopIndex

name

desc

basicBlocks

hirMap

registers

maxIntervals

pRegisters

intervals

labelPrefix

data

Constructor Detail

NControlFlowGraph

Method Detail

detectLoops

removeUnreachableBlocks

computeDominators

tuplesToHir

optimize

eliminateRedundantPhiFunctions

hirToLir

resolvePhiFunctions

orderBlocks

blockAt

renumberLirInstructions

allocatePhysicalRegisters

writeTuplesToStdOut

writeHirToStdOut

writeLirToStdOut

writeIntervalsToStdOut