org.jikesrvm.compilers.opt.ssa

Class SSA

java.lang.Object

org.jikesrvm.compilers.opt.ssa.SSA

class SSA
extends Object

This module holds utility functions for SSA form.

Our SSA form is Heap Array SSA Form , an extension of SSA that allows analysis of scalars, arrays, and object fields in a unified framework. See our SAS 2000 paper Unified Analysis of Arrays and Object References in Strongly Typed Languages

Details about our current implementation include:

• We explicitly place phi-functions as instructions in the IR.
• Scalar registers are explicitly renamed in the IR.
• Heap variables are represented implicitly. Each instruction that reads or writes from the heap implicitly uses a Heap variable. The particular heap variable for each instruction is cached in HIRInfo.dictionary which is reachable via the IR object. dphi functions do not explicitly appear in the IR.

  For example, consider the code:

                a.x = z;
                b[100] = 5;
                y = a.x;
    

  Logically, we translate to Array SSA form (before renumbering) as:

                HEAP_x[a] = z
                HEAP_x = dphi(HEAP_x,HEAP_x)
                HEAP_I[] = { < b,100,5 > }
                HEAP_I[] = dphi(HEAP_I[], HEAP_I[])
                y = HEAP_x[a]
    

  However, the implementation does not actually modify the instruction stream. Instead, we keep track of the following information with ir.HIRInfo.dictionary :

                a.x = z  (implicit: reads HEAP_x, writes HEAP_x)
                b[100] =5 (implicit: reads HEAP_I[], writes HEAP_I[])
                y = a.x   (implicit: reads HEAP_x)
    

  Similarly, phi functions for the implicit heap variables will not appear explicitly in the instruction stream. Instead, the SSADictionary data structure keeps the heap control phi functions for each basic block in a lookaside table.

See Also:

EnterSSA, LeaveSSA, SSADictionary, HIRInfo

Constructor Summary

Constructors

Constructor and Description
SSA()

Method Summary

Modifier and Type	Method and Description
(package private) static void	addAtEnd(IR ir, BasicBlock bb, Instruction c, boolean exp) Add a move instruction at the end of a basic block, renaming with a temporary register if needed to protect conditional branches at the end of the block.
(package private) static Instruction	makeMoveInstruction(IR ir, Register r1, ConstantOperand c) Create a move instruction r1 := c.
(package private) static Instruction	makeMoveInstruction(IR ir, Register r1, Register r2, TypeReference t) Create a move instruction r1 := r2.
static void	printInstructions(IR ir) Print the instructions in SSA form.
(package private) static void	purgeBlockFromPHIs(BasicBlock source, BasicBlock target) Fix up any PHI instructions in the given target block to reflect that the given source block is no longer a predecessor of target.
(package private) static void	replaceBlockInPhis(BasicBlock target, BasicBlock B1, BasicBlock B2) Update PHI instructions in the target block so that any PHIs that come from basic block B1, now come from basic block B2.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SSA

SSA()

Method Detail

addAtEnd

static void addAtEnd(IR ir,
                     BasicBlock bb,
                     Instruction c,
                     boolean exp)

Add a move instruction at the end of a basic block, renaming with a temporary register if needed to protect conditional branches at the end of the block.

Parameters:

ir - governing IR

bb - the basic block

c - the move instruction to insert

exp - whether or not to respect exception control flow at the end of the block

printInstructions

public static void printInstructions(IR ir)

Print the instructions in SSA form.

Parameters:

ir - the IR, assumed to be in SSA form

makeMoveInstruction

static Instruction makeMoveInstruction(IR ir,
                                       Register r1,
                                       Register r2,
                                       TypeReference t)

Create a move instruction r1 := r2.

TODO: This utility function should be moved elsewhere.

Parameters:

ir - the governing ir

r1 - the destination

r2 - the source

t - the type of r1 and r2.

Returns:

the created move instruction

makeMoveInstruction

static Instruction makeMoveInstruction(IR ir,
                                       Register r1,
                                       ConstantOperand c)

Create a move instruction r1 := c.

!!TODO: put this functionality elsewhere.

Parameters:

ir - the governing ir

r1 - the destination

c - the source

Returns:

the created move instruction

purgeBlockFromPHIs

static void purgeBlockFromPHIs(BasicBlock source,
                               BasicBlock target)

Fix up any PHI instructions in the given target block to reflect that the given source block is no longer a predecessor of target. The basic algorithm is to erase the PHI operands related to the edge from source to target by sliding the other PHI operands down as required.

Parameters:

source - the source block to remove from PHIs in target

target - the target block that may contain PHIs to update.

replaceBlockInPhis

static void replaceBlockInPhis(BasicBlock target,
                               BasicBlock B1,
                               BasicBlock B2)

Update PHI instructions in the target block so that any PHIs that come from basic block B1, now come from basic block B2.

Parameters:

target - the target block that may contain PHIs to update.

B1 - the block to replace in the phi instructions

B2 - the replacement block for B1