Package jminusminus

Class NControlFlowGraph

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

  • Field Details

    • 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 Details

    • NControlFlowGraph

      public NControlFlowGraph(CLConstantPool cp, CLMethodInfo m)
      Constructs a NControlFlowGraph object for a method..
      Parameters:
      cp - constant pool for the class containing the method.
      m - contains information about the method.

  • Method Details

    • 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()
      Removes 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)
      Computes 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()
      Converts tuples in each block to their high-level (HIR) representations.

    • optimize

      public void optimize()
      Carries out optimizations on the high-level instructions.

    • eliminateRedundantPhiFunctions

      public void eliminateRedundantPhiFunctions()
      Eliminates redundant phi functions of the form x = (y, x, x, ..., x) with y.

    • hirToLir

      public void hirToLir()
      Converts the hir instructions in this cfg to lir instructions.

    • resolvePhiFunctions

      public void resolvePhiFunctions()
      Resolves 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()
      Computes optimal ordering of the basic blocks in this cfg.

    • blockAt

      public NBasicBlock blockAt(int id)
      Returns the basic block at a particular instruction id, or null.
      Parameters:
      id - the (LIR) instruction id.
      Returns:
      the basic block at a particular instruction id, or null.

    • renumberLirInstructions

      public void renumberLirInstructions()
      Assigns new ids to the LIR instructions in this cfg.

    • allocatePhysicalRegisters

      public void allocatePhysicalRegisters()
      Replaces references to virtual registers in LIR instructions with references to physical registers.

    • writeTuplesToStdOut

      public void writeTuplesToStdOut(PrettyPrinter p)
      Writes the tuples in this cfg to standard output.
      Parameters:
      p - for pretty printing with indentation.

    • writeHirToStdOut

      public void writeHirToStdOut(PrettyPrinter p)
      Writes the hir instructions in this cfg to standard output.
      Parameters:
      p - for pretty printing with indentation.

    • writeLirToStdOut

      public void writeLirToStdOut(PrettyPrinter p)
      Writes the lir instructions in this cfg to standard output.
      Parameters:
      p - for pretty printing with indentation.

    • writeIntervalsToStdOut

      public void writeIntervalsToStdOut(PrettyPrinter p)
      Writes the intervals in this cfg to standard output.
      Parameters:
      p - for pretty printing with indentation.