harpoon.IR.Assem
Class Instr

java.lang.Object
  harpoon.IR.Assem.Instr

All Implemented Interfaces:

HCodeElement, CFGraphable<Instr,InstrEdge>, UseDefable, Graph.Node<Instr,InstrEdge>

Direct Known Subclasses:

CodeGen.InstrCC, CodeGen.InstrDELAYSLOT, InstrCALL, InstrDIRECTIVE, InstrJUMP, InstrLABEL, InstrMEM, InstrMOVE, InstrMOVEproxy, RegAlloc.RestoreProxy, RegAlloc.SpillProxy

public class Instr
extends Object
implements HCodeElement, UseDefable, CFGraphable<Instr,InstrEdge>

Instr is the primary class for representing assembly-level instructions used in the Backend.* packages. Important Note: Most Instrs have only one predecessor. One type of Instr with potentially more than one predecessor is an InstrLABEL. In any case, any code that relies on the "only one predecessor"-invariant must check each Instr with hasMultiplePredecessors(). Likewise, extensions of Instr which are designed to allow multiple predecessors must override predC() and hasMultiplePredecessors()

Version:

$Id: Instr.java,v 1.11 2004/02/08 05:09:51 cananian Exp $

Author:

Andrew Berkheimer <andyb@mit.edu>, Felix S. Klock II <pnkfelix@mit.edu>

Field Summary

static ArrayFactory<Instr>	arrayFactory Defines an array factory which can be used to generate arrays of Instrs.
boolean	canFallThrough Sets whether control flow can go to this.next.
protected Instr	next The next Instr to output after this.
protected Instr	prev The Instr that is output prior to this.

Constructor Summary

Instr(InstrFactory inf, HCodeElement source, String assem)
Creates an Instr consisting of the String assem.

Instr(InstrFactory inf, HCodeElement source, String assem, Temp[] src)
Creates an Instr consisting of the String assem and the list of sources in src.

Instr(InstrFactory inf, HCodeElement source, String assem, Temp[] dst, Temp[] src)
Creates an Instr consisting of the String assem and the lists of destinations and sources in dst and src.

Instr(InstrFactory inf, HCodeElement source, String assem, Temp[] dst, Temp[] src, boolean canFallThrough, List<Label> targets)
Creates an Instr consisting of the String assem and the list of destinations and sources in dst and src.

Method Summary

void	accept(InstrVisitor v) Accept a visitor.
Instr	cloneMutateAssem(InstrFactory inf, String newAssem) Clones this, mutating the assembly string.
Instr	cloneMutateAssem(String newAssem) Clones this, mutating the assembly string.
Temp[]	def() Returns the Temps defined by this Instr.
Collection<Temp>	defC() Returns a Collection of all the Temps defined in this HCodeElement.
List<InstrEdge>	edgeC() Returns the control flow edges of this.
InstrEdge[]	edges() Returns the control flow edges of this.
String	getAssem()
Instr	getEntry(InstrGroup.Type type) Returns the entry Instr when the instructions are being viewed as collected by type.
Instr	getExit(InstrGroup.Type type) Returns the exit Instr when the instructions are being viewed as collected by type.
InstrFactory	getFactory() Returns the InstrFactory that generated this.
Set<InstrGroup>	getGroups() Returns the Set of InstrGroups that this is an element of.
int	getID() Returns a unique numeric identifier for this element.
InstrLABEL	getInstrFor(Label l) Returns the InstrLABEL associated with l in the InstrFactory for this.
int	getLineNumber() Get the line in the original source file that this element is traceable to.
Instr	getNext() The next Instr to output after this.
Instr	getPrev() The Instr that is output prior to this.
String	getSourceFile() Get the original source file name that this element is derived from.
List<Label>	getTargets() List of target labels that this can branch to.
int	hashCode() Returns the hashcode for this.
boolean	hasModifiableTargets() Checks whether this.targets is modifiable.
protected boolean	hasMultiplePredecessors() Checks if this has multiple predecessors.
void	insertAt(CFGEdge edge) Inserts this at edge.
static void	insertInstrsAt(CFGEdge edge, List instrs) Not implemented yet.
boolean	isDirective() Returns true if this is a directive instruction that is meant to represent data stored in the code segment, not actual executable code.
boolean	isDummy() Returns true if this is a dummy instruction to express register allocation constraints.
boolean	isJump() Returns true if this is an unconditional Jump.
boolean	isLabel() Returns true if this is a label instruction that is meant to mark a location in the code segment, not actual executable code.
boolean	isMove() Returns true if this is a Move.
boolean	isPred(Instr i) Return true iff the given node is a predecessor of this node.
boolean	isSucc(Instr i) Return true iff the given node is a successor of this node.
void	layout(Instr from, Instr to) Places this in the instruction layout between from and to.
protected static Temp	map(TempMap tm, Temp t)
protected static Temp[]	map(TempMap tm, Temp[] ta)
protected static Temp[][]	map(TempMap tm, Temp[][] taa)
InstrEdge[]	pred() Returns the control flow predecessors of this.
List<InstrEdge>	predC() Returns the control flow predecessors of this.
void	remove() Removes this from its current place in the instruction layout.
Instr	rename(InstrFactory inf, TempMap defMap, TempMap useMap) Create a new Instr identical to the receiver, but with all Temps renamed according to the given mappings.
Instr	rename(TempMap tempmap) Create a new Instr identical to the receiver, but with all Temps renamed according to the given mappings.
Instr	rename(TempMap defMap, TempMap useMap) Create a new Instr identical to the receiver, but with all Temps renamed according to the given mappings.
static void	replace(Instr inOld, Instr inNew)
static void	replaceInstrList(Instr oldi, List newis) Replaces oldi in the Instruction Stream with newis.
void	setGroup(InstrGroup seq) Sets the InstrGroup sequence associated with this.
InstrEdge[]	succ() Returns the control flow successors of this.
List<InstrEdge>	succC() Returns the control flow successors of this.
String	toString() Returns a string representation of the Instr.
Temp[]	use() Returns the Temps used by this Instr.
Collection<Temp>	useC() Returns a Collection of all the Temps read in this HCodeElement.

Methods inherited from class java.lang.Object

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

Field Detail

prev

protected Instr prev

The Instr that is output prior to this. Should be null if this is the first instruction in the method or if this has not been inserted into an instruction stream (ie. insertAt(CFGEdge) has not been called since the last call to remove() or since construction).

next

protected Instr next

The next Instr to output after this. next can be significant for control flow, depending on if this.canFallThrough. Should be null if this is the last instruction in the method or if this has not been inserted into an instruction stream (ie. insertAt(CFGEdge) has not been called since the last call to remove() or since construction).

canFallThrough

public final boolean canFallThrough

Sets whether control flow can go to this.next. Note that if (!this.canFallThrough) && (this.targets == null) then this represents an exit point for the code and should be treated as such for data flow analysis, etc.

See Also:

getNext()

arrayFactory

public static final ArrayFactory<Instr> arrayFactory

Defines an array factory which can be used to generate arrays of Instrs.

Constructor Detail

Instr

public Instr(InstrFactory inf,
             HCodeElement source,
             String assem,
             Temp[] dst,
             Temp[] src,
             boolean canFallThrough,
             List<Label> targets)

Creates an Instr consisting of the String assem and the list of destinations and sources in dst and src.

Parameters:

inf - InstrFactory for this

source - HCodeElement that was the source for this

assem - Assembly code string for this

dst - Set of Temps that may be written to in the execution of this.

src - Set of Temps that may be read from in the execution of this.

canFallThrough - Decides whether control flow could fall to this.next.

targets - List of target Labels that control flow could potentially branch to. If targets is null, then this is a non-branching instruction.

Instr

public Instr(InstrFactory inf,
             HCodeElement source,
             String assem,
             Temp[] dst,
             Temp[] src)

Creates an Instr consisting of the String assem and the lists of destinations and sources in dst and src. canFallThrough is set to true and targets is set to null.

Instr

public Instr(InstrFactory inf,
             HCodeElement source,
             String assem,
             Temp[] src)

Creates an Instr consisting of the String assem and the list of sources in src. The list of destinations is empty. canFallThrough is set to true and targets is set to null.

Instr

public Instr(InstrFactory inf,
             HCodeElement source,
             String assem)

Creates an Instr consisting of the String assem. The lists of sources and destinations are empty. canFallThrough is set to true and targets is set to null.

Method Detail

setGroup

public void setGroup(InstrGroup seq)

Sets the InstrGroup sequence associated with this.
requires: this is not associated with any group.

getGroups

public Set<InstrGroup> getGroups()

Returns the Set of InstrGroups that this is an element of.

getEntry

public Instr getEntry(InstrGroup.Type type)

Returns the entry Instr when the instructions are being viewed as collected by type. Note that if this is not contained in any member of type, then this is its own group, and thus this is returned.

getExit

public Instr getExit(InstrGroup.Type type)

Returns the exit Instr when the instructions are being viewed as collected by type. Note that if this is not contained in any member of type, then this is its own group, and thus this is returned.

getPrev

public Instr getPrev()

The Instr that is output prior to this. Should be null if this is the first instruction in the method or if this has not been inserted into an instruction stream (ie. insertAt(CFGEdge) has not been called since the last call to remove() or since construction).

getNext

public Instr getNext()

The next Instr to output after this. next can be significant for control flow, depending on if this.canFallThrough. Should be null if this is the last instruction in the method or if this has not been inserted into an instruction stream (ie. insertAt(CFGEdge) has not been called since the last call to remove() or since construction).

See Also:

canFallThrough

getTargets

public List<Label> getTargets()

List of target labels that this can branch to. getTargets() may be empty (in which case control flow either falls through to the this.next (the case if this.canFallThrough), or returns to some unknown Instr (the case for 'return' statements)).

Returns:

A List of Labels.

See Also:

canFallThrough, getNext(), hasModifiableTargets()

getInstrFor

public InstrLABEL getInstrFor(Label l)

Returns the InstrLABEL associated with l in the InstrFactory for this.

replaceInstrList

public static void replaceInstrList(Instr oldi,
                                    List newis)

Replaces oldi in the Instruction Stream with newis.
requires:

1. oldi is a non-branching instruction
2. newis is a List of instructions such that the elements of newis form a basic block. (this constraint may be weakened later if necessary)

modifies: oldi.prev, oldi.next
effects: Modifies the Instrs immediately dominating and succeeding oldi as to substitute newis in the place of oldi.

insertInstrsAt

public static void insertInstrsAt(CFGEdge edge,
                                  List instrs)

Not implemented yet.

insertAt

public void insertAt(CFGEdge edge)

Inserts this at edge. The purpose of this insertion is to modify control flow, rather than just instruction layout. See layout(CFGEdge) for direct modification of layout (which is less constrained than this method but is not intended for generic program transformation use.
requires:

1. edge.from() and edge.to() are instances of Instr or one is null and the other is an instance of Instr.
2. if edge.from() is not null, then edge.from().hasModifiableTargets().
3. if edge.from() and edge.to() are not null, then edge.to() is a successor of edge.from().
4. this is a non-branching instruction (ie, this.targets equals null and this.canFallThrough).
5. this is not currently in an instruction stream (ie this.getPrev() == null and this.getNext() == null). This is true for newly created Instrs and for Instr which have just had their remove() method called.

modifies: edge.from(), edge.to(), this
effects: changes edge.from() and edge.to() so that after edge.from() is executed, this will be executed and then followed by edge.to().

See Also:

remove()

remove

public void remove()

Removes this from its current place in the instruction layout.
requires: this has a current location in the instruction layout. (ie insertAt(CFGEdge) or layout(Instr, Instr) has been called since the last time remove() was called, or since construction if remove() has never been called.)
modifies: this, this.prev, this.next
effects: removes this from its current instruction stream, updating the preceeding and succeeding Instrs accordingly (preceeding and succeeding according to instruction layout, not according to control flow) and setting the this.prev and this.next fields to null.

See Also:

insertAt(harpoon.IR.Properties.CFGEdge), layout(harpoon.IR.Assem.Instr, harpoon.IR.Assem.Instr)

layout

public void layout(Instr from,
                   Instr to)

Places this in the instruction layout between from and to.
requires:

1. if from is not null, then from.getNext() equals to.
2. if to is not null, then to.getPrev() equals from.
3. this is not currently in an instruction stream (ie this.getPrev() == null and this.getNext() == null) . This is true for newly created Instrs and for Instr which have just had their remove() method called.

modifies: from, to
effects: Inserts this into the instruction stream in between from and to. If from is null, then this is laid out as the beginning of the Instruction stream. If to is null, then this is laid out as the end of the Instruction stream.

replace

public static void replace(Instr inOld,
                           Instr inNew)

rename

public final Instr rename(TempMap tempmap)

Create a new Instr identical to the receiver, but with all Temps renamed according to the given mappings. The new Instr will have no edges, and will come from the InstrFactory for this.

rename

public final Instr rename(TempMap defMap,
                          TempMap useMap)

Create a new Instr identical to the receiver, but with all Temps renamed according to the given mappings. The new Instr will have no edges, and will come from the InstrFactory for this.

rename

public Instr rename(InstrFactory inf,
                    TempMap defMap,
                    TempMap useMap)

Create a new Instr identical to the receiver, but with all Temps renamed according to the given mappings. The new Instr will have no edges, and will come from the specified InstrFactory. FSK: I don't think this "no edges" part of the specification holds anymore (it was written before we revised the control-flow representation in the Instrs...

accept

public void accept(InstrVisitor v)

Accept a visitor.

getFactory

public InstrFactory getFactory()

Returns the InstrFactory that generated this.

hashCode

public int hashCode()

Returns the hashcode for this.

Overrides:

hashCode in class Object

getAssem

public String getAssem()

toString

public String toString()

Returns a string representation of the Instr. Note that while in the common case the String returned will match the executable assembly code for the Instr, this is not guaranteed. To produce executable assembly in all cases, use IR.Assem.Code.toAssem(Instr i).

Overrides:

toString in class Object

use

public final Temp[] use()

Returns the Temps used by this Instr.

Specified by:

use in interface UseDefable

def

public final Temp[] def()

Returns the Temps defined by this Instr.

Specified by:

def in interface UseDefable

useC

public Collection<Temp> useC()

Description copied from interface: UseDefable

Returns a Collection of all the Temps read in this HCodeElement.

Specified by:

useC in interface UseDefable

defC

public Collection<Temp> defC()

Description copied from interface: UseDefable

Returns a Collection of all the Temps defined in this HCodeElement.

Specified by:

defC in interface UseDefable

getSourceFile

public String getSourceFile()

Description copied from interface: HCodeElement

Get the original source file name that this element is derived from.

Specified by:

getSourceFile in interface HCodeElement

getLineNumber

public int getLineNumber()

Description copied from interface: HCodeElement

Get the line in the original source file that this element is traceable to.

Specified by:

getLineNumber in interface HCodeElement

getID

public int getID()

Description copied from interface: HCodeElement

Returns a unique numeric identifier for this element.

Specified by:

getID in interface HCodeElement

edges

public InstrEdge[] edges()

Returns the control flow edges of this. Note that this returns edges according to control flow, not in terms of instruction layout. Look at getNext() and getPrev() for information on instruction layout.

Specified by:

edges in interface CFGraphable<Instr,InstrEdge>

edgeC

public List<InstrEdge> edgeC()

Returns the control flow edges of this. Note that this returns edges according to control flow, not in terms of instruction layout. Look at getNext() and getPrev() for information on instruction layout.

Specified by:

edgeC in interface CFGraphable<Instr,InstrEdge>

isSucc

public boolean isSucc(Instr i)

Description copied from interface: Graph.Node

Return true iff the given node is a successor of this node.

Specified by:

isSucc in interface Graph.Node<Instr,InstrEdge>

isPred

public boolean isPred(Instr i)

Description copied from interface: Graph.Node

Return true iff the given node is a predecessor of this node.

Specified by:

isPred in interface Graph.Node<Instr,InstrEdge>

pred

public InstrEdge[] pred()

Returns the control flow predecessors of this. Note that this returns edges according to control flow, not in terms of instruction layout. Look at getNext() and getPrev() for information on instruction layout. Uses predC() to get the necessary information.

Specified by:

pred in interface CFGraphable<Instr,InstrEdge>

predC

public List<InstrEdge> predC()

Returns the control flow predecessors of this. Note that this returns edges according to control flow, not in terms of instruction layout. Look at getNext() and getPrev() for information on instruction layout.

Specified by:

predC in interface CFGraphable<Instr,InstrEdge>

Specified by:

predC in interface Graph.Node<Instr,InstrEdge>

succ

public InstrEdge[] succ()

Returns the control flow successors of this. Note that this returns edges according to control flow, not in terms of instruction layout. Look at getNext() and getPrev() for information on instruction layout.

Specified by:

succ in interface CFGraphable<Instr,InstrEdge>

succC

public List<InstrEdge> succC()

Returns the control flow successors of this. Note that this returns edges according to control flow, not in terms of instruction layout. Look at getNext() and getPrev() for information on instruction layout.

Specified by:

succC in interface CFGraphable<Instr,InstrEdge>

Specified by:

succC in interface Graph.Node<Instr,InstrEdge>

hasModifiableTargets

public boolean hasModifiableTargets()

Checks whether this.targets is modifiable. Most instructions with a list of targets allow for dynamic replacement of elements of the targets list. This way, branch targets can be modified to allow for easy insertion of arbitrary fixup code on edges between Instrs by adding new branches and labels.

For example:

[ code block 1 ]

beq L0

[ code block 2 ]

L0:

[ code block 3, which does not fall through]

can be turned into:

[ code block 1 ]

beq L1

[ code block 2 ]

L0:

[ code block 3, which does not fall through ]

L1:

[ fixup code prefixing block 3 ]

b L0

For such instructions, this method returns true.

However, some instructions (such as computed branches) cannot have their targets list modified in such a manner (the only way to safely insert code between blocks is to first ensure that a given computed branch is the only branch that jumps to the target label, and then insert the fixup code at the point of the label).

Such instructions should be initialized with an anonymous inner class that overrides this method and returns false.

An important invariant that must be preserved (and is high level enough that Tree form implementors must take note of it) is that

for all n0, n1, n2 elem of Instr such that there exists an edge < n0, n1 > and an edge < n1, n2 > , n0 doesn't have modifiable targets implies the edge < n0, n1 > dominates the edge < n1, n2 > .

In other words, n1 should have no predecessors other than n0.

hasMultiplePredecessors

protected boolean hasMultiplePredecessors()

Checks if this has multiple predecessors. Most Instrs have either zero or one predecessors. Any Instrs that can have more than one predecessor should override this method to return true.

map

protected static final Temp map(TempMap tm,
                                Temp t)

map

protected static final Temp[] map(TempMap tm,
                                  Temp[] ta)

map

protected static final Temp[][] map(TempMap tm,
                                    Temp[][] taa)

cloneMutateAssem

public final Instr cloneMutateAssem(String newAssem)

Clones this, mutating the assembly string.
requires: newAssem != null
effects: returns cloneMutateAssem(inf, newAssem)

cloneMutateAssem

public Instr cloneMutateAssem(InstrFactory inf,
                              String newAssem)

Clones this, mutating the assembly string.
requires: newAssem != null
effects: Returns a new Instr object with the same compiler-visible high level properties as this (use/def, isMove, etc), but instead of having the assembly-string of this, it has newAssem as its assembly string. The generated instr will not have a a place in the instruction layout; it is the responsiblity of the caller to subsequently call Instr.replace to swap this and the returned Instr.

isMove

public boolean isMove()

Returns true if this is a Move.
effects: Returns true if the only effect of executing this instruction is to copy a set of source Temps to a set of destination Temps.

isJump

public boolean isJump()

Returns true if this is an unconditional Jump.
effects: Returns true if the only effect of executing this instruction is to shift control-flow to one target Label with no side-effects.

isDummy

public boolean isDummy()

Returns true if this is a dummy instruction to express register allocation constraints.
effects: Returns true if this instruction has no effect in itself, but instead is an artificial use of some Temp(s) inserted as a note to the register allocator not to insert a Spill-Load before this instruction.

isDirective

public boolean isDirective()

Returns true if this is a directive instruction that is meant to represent data stored in the code segment, not actual executable code.

isLabel

public boolean isLabel()

Returns true if this is a label instruction that is meant to mark a location in the code segment, not actual executable code.