scale.backend.trips2
Class SSA

java.lang.Object
  scale.backend.trips2.SSA

public class SSA
extends java.lang.Object

This class converts a PFG into the SSA form of the PFG.

$Id: SSA.java,v 1.56 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.

The algorithm comes from Practical Improvements to the Construction and Destruction of Static Single Assignment Form by Briggs, et al, in Software - Practice and Experience, Vol 1(1), 1-28, January 1988.

To enter SSA form, read/write instructions must already be inserted for all global registers which are live-in/out of the hyperblock.

Constructor Summary

SSA(RegisterSet registers, Hyperblock hb)
The SSA constructor.

Method Summary

protected void	addUse(Instruction inst, int use) Record that an instruction uses a register.
void	clearDefUse(Instruction inst) Remove all the use-def and def-use information for an instruction.
static int	copiesFolded() Return the number of instructions removed.
static int	deadInstructions() Return the number of instructions removed.
IntMap<Vector<Instruction>>	getDefUse() Get a map of uses to Instructions.
IntMap<Instruction>	getUseDef() Get a map of definitions to Instructions.
static int	phisInserted() Return the number of phi instructions inserted.
void	placePhis() Place phi functions and rename all variables.
void	removeDeadCode() Remove instructions which are dead.
void	removePhis() Remove any phi instructions still in the PFG.
void	removeUse(Instruction inst, int use) Remove an instruction from the set of uses.
void	setDef(Instruction inst, int def) Set the instruction which defines a register.

Methods inherited from class java.lang.Object

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

Constructor Detail

SSA

public SSA(RegisterSet registers,
           Hyperblock hb)

The SSA constructor.

Method Detail

deadInstructions

public static int deadInstructions()

Return the number of instructions removed.

copiesFolded

public static int copiesFolded()

Return the number of instructions removed.

phisInserted

public static int phisInserted()

Return the number of phi instructions inserted.

placePhis

public final void placePhis()

Place phi functions and rename all variables.

getUseDef

public final IntMap<Instruction> getUseDef()

Get a map of definitions to Instructions.

getDefUse

public final IntMap<Vector<Instruction>> getDefUse()

Get a map of uses to Instructions.

setDef

public final void setDef(Instruction inst,
                         int def)

Set the instruction which defines a register.

removeUse

public final void removeUse(Instruction inst,
                            int use)

Remove an instruction from the set of uses.

addUse

protected void addUse(Instruction inst,
                      int use)

Record that an instruction uses a register.

clearDefUse

public final void clearDefUse(Instruction inst)

Remove all the use-def and def-use information for an instruction. This should be called whenever an instruction is removed.

removePhis

public final void removePhis()

Remove any phi instructions still in the PFG.
We use Cytron's algorithm of inserting copies into all predecessors of the phi. This works because we don't have critical edges inside a hyperblock.
If the instruction which defines a phi's operand can be renamed we do so and avoid inserting a copy in the predecessor predicate block.
There is a special case for handling phi's which define predicates. Instead of replacing the phi with mov instructions we rename all the instructions which reference one of the phi's operands to the same register. If we were to insert mov instructions, the mov's would define predicates and when the PFG was rebuilt each mov would cause a split in the PFG.

removeDeadCode

public final void removeDeadCode()

Remove instructions which are dead.
This routine also maintains the predicates for the hyperblock.