#
# Machine SSA representation.
#
# Some conventions
# ----------------
# 1. Each machine instruction is mapped into an ssa_op. Some exceptions:
# a. live-out and live-in for each entry and exit are represented as
# SINK and SOURCE nodes.
# b. PHI functions may be inserted
# c. COPYs may be propagated during construction of the ssa graph.
# 2. Each instruction set must provide the pseudo instructions SINK, SOURCE
# and PHI.
# 3. Each ssa_op is numbered with its own ssa_id, starting from 0.
# 4. Each definition is given a unique (non-negative) value id
# IMPORTANT: ssa_id != value. Each instructions may define multiple
# values, even zero. But each instruction is given its own unique id.
# 5. Negative value ids are immediate constants. These are value numbered
# so that the each distinct constant is given unique (negative) id.
# These constants are entered into the operandTable.
# 6. In-edges of the graph are use-def chains. These are computed on the
# fly.
# Out-edges are def-use chains. Both type of edges have the following
# form:
# (source id, dst id, register)
# Of course, immedidate operands have no edges associated with them.
# 7. The graph interface has high overhead. So in order to allow faster
# implementation, we allow direct access to the internal data structures.
# These are:
# Name Mapping Description
# ---------------------------------------------------------------
# defSiteTable value -> ssa_id Definition site of a value
# (i.e. use/def chains)
# blockTable ssa_id -> block Block id of an instruction
# defsTable ssa_id -> value List Definitions of an ssa_op
# usesTable ssa_id -> value List Uses of an ssa_op
# rtlTable ssa_id -> rtl RTL of an ssa_op
# succTable ssa_id -> outedges Out edges of an ssa_op
# (i.e. def/use chains)
# ssaOpTable ssa_id -> ssa_op ssa_op table
# registerKindTable value -> ssa_id registerkind of a value
# operandTable value -> operand operand table
#
# But in general, you should use the graph interface for traversal
# if are not sure how the internal tables work.
#
# -- Allen Leung (leunga@cs.nyu.edu)
### "Symmetry is a complexity-reducing concept;
### seek it everywhere."
###
### -- Alan Perlis
api SSA =
api
package i: Machcode
package c: Registers
package sp: SSA_PROPERTIES
package rtl: Treecode_Rtl
package mcg: SSA_FLOWGRAPH # "mcg" == "machcode_controlflow_graph".
package dom: Dominator_Tree
package dj: DJ_GRAPH
package gc_map: GC_MAP
package translate_treecode_to_machcode: Translate_Treecode_To_Machcode
package w: FREQ
sharing sp::I = mcg::I = translate_treecode_to_machcode::I = I
sharing sp::RTL = RTL
sharing translate_treecode_to_machcode::T = RTL::T
sharing i::C = sp::C = C
sharing Dom = dj::Dom
sharing mcg::W = W
# ------------------------------------------------------------------------
# Basic type definitions used in the SSA form
# ------------------------------------------------------------------------
type value = Int # value id
type pos = Int # position within a block
type block = graph::node_id # Block id
type ssa_id = graph::node_id # ssa id
type rtl = RTL::rtl # RTL
type const = sp::ot::const # Constants
type mcg = mcg::mcg # Control flow graph
# Dominator tree
type dom = Dom::dominator_tree( mcg::block, mcg::edge_info, mcg::info )
type nameTable
=
int_hashtable::Hashtable {
oldName: c::register,
index: Int
}
# ------------------------------------------------------------------------
# An SSA op is an instruction
# ------------------------------------------------------------------------
type ssa_op = i::instruction
# ------------------------------------------------------------------------
# Information about the SSA graph
# ------------------------------------------------------------------------
type ssa_info
# ------------------------------------------------------------------------
# The graph package
# ------------------------------------------------------------------------
type ssa
=
graph::graph( ssa_op, value, ssa_info )
# ------------------------------------------------------------------------
# How to create a new SSA graph
# ------------------------------------------------------------------------
# Create an empty SSA graph
my newSSA: { mcg: mcg,
dom: mcg -> dom,
gcmap: Null_Or( GCMap::gcmap ),
nameTable: Null_Or( nameTable )
} -> ssa
my newRenamedVariable: ssa -> c::register -> value # generate renamed variable
my newVariable: ssa -> c::register -> c::register
# Create a new op; but does not add edges
my newOp: ssa -> { id: ssa_id,
instruction: i::instruction,
rtl: rtl,
defs: List( value ),
uses: List( value ),
block: block,
pos: pos
} -> Void
my reserve: ssa -> Int -> Void # reserve n nodes
my immed: ssa -> Int -> value # lookup immed value
my operand: ssa -> i::operand -> value # lookup perand
my computeDefUseChains: ssa -> Void
# ------------------------------------------------------------------------
# Extract info from the SSA graph
# ------------------------------------------------------------------------
my dom: ssa -> dom # extracts the dominator
my mcg: ssa -> mcg # extracts the machcode_controlflow_graph
my maxVariable: ssa -> Int # maximum number of ssa names
my numberOfOperands: ssa -> Int # number of operands
my const: ssa -> value -> const # lookup const values
# ------------------------------------------------------------------------
# Extract the raw tables.
# These should only be used when the optimization guarantees that
# no new ssa ops are added to the graph, since that may involve resizing
# these tables, rendering them obsolete.
# ------------------------------------------------------------------------
my defSiteTable: ssa -> rw_vector::Rw_Vector( ssa_id )
my blockTable: ssa -> rw_vector::Rw_Vector( block )
my posTable: ssa -> rw_vector::Rw_Vector( pos )
my defsTable: ssa -> rw_vector::Rw_Vector( List( value ) )
my usesTable: ssa -> rw_vector::Rw_Vector( List( value ) )
my rtlTable: ssa -> rw_vector::Rw_Vector( rtl )
my succTable: ssa -> rw_vector::Rw_Vector( List( graph::edge( value ) ) ) # out edges
my ssaOpTable: ssa -> rw_vector::Rw_Vector( ssa_op ) # node table
my registerKindTable: ssa -> int_hashtable::Hashtable( c::registerkind )
# Registerkind table
my operandTable: ssa -> sp::ot::operandTable
my minPos: ssa -> REF( Int )
my maxPos: ssa -> REF( Int )
# ------------------------------------------------------------------------
# Zero registers, pinned registers
# ------------------------------------------------------------------------
my zeroRegs: rw_vector_of_one_byte_unts::Rw_Vector
my pinnedUseTable: rw_vector_of_one_byte_unts::Rw_Vector
my pinnedDefTable: rw_vector_of_one_byte_unts::Rw_Vector
# ------------------------------------------------------------------------
# Look up information (the safe way)
# ------------------------------------------------------------------------
my defSite: ssa -> value -> ssa_id # lookup definition site
my block: ssa -> ssa_id -> block # lookup block id
my rtl: ssa -> ssa_id -> rtl # lookup rtl
my uses: ssa -> ssa_id -> List( value )
my defs: ssa -> ssa_id -> List( value )
# nodes linearized and indexed by block id
my nodes: ssa -> { sources: rw_vector::Rw_Vector( List( ssa_id ) ),
phis: rw_vector::Rw_Vector( List( ssa_id ) ),
ops: rw_vector::Rw_Vector( List( ssa_id ) ),
sinks: rw_vector::Rw_Vector( List( ssa_id ) )
}
my freqTable: ssa -> rw_vector::Rw_Vector( w::freq ) # frequency indexed by block
my noResize: ssa -> (X -> Y) -> X -> Y
# ------------------------------------------------------------------------
# Iterators
# ------------------------------------------------------------------------
my forallNodes: ssa -> (ssa_id -> Void) -> Void
my foldNodes: ssa -> (ssa_id * X -> X) -> X -> X
# ------------------------------------------------------------------------
# Remove all useless phi-functions from the graph.
# Useless phi-functions are self-loops of the form
# t <- phi (t, t, ..., t, s, t, ..., t)
# This transformation removes this phi-function and replace all uses
# of t by s. This process is worklist driven; removing a useless
# phi-function can introduce other useless phi-functions.
# ------------------------------------------------------------------------
my removeUselessPhiFunctions: ssa -> Void
# ------------------------------------------------------------------------
# Remove all nodes from the graph. Note that no uses should be
# present after this transformation.
# ------------------------------------------------------------------------
my removeAllNodes: ssa -> List( ssa_id ) -> Void
# ------------------------------------------------------------------------
# Replace all use of one value with another. Return TRUE iff
# all uses of "from" has been replaced by "to".
# Note: The definition of "from" must dominate all uses of "to", as
# required by the SSA form.
# ------------------------------------------------------------------------
my replaceAllUses: ssa -> { from: value, to: value, vn: value } -> Bool
# ------------------------------------------------------------------------
# Replace the definition of value by const. Return TRUE iff
# this operation is successful.
# ------------------------------------------------------------------------
my foldConstant: ssa -> { value: value, const: value } -> Bool
# ------------------------------------------------------------------------
# Move an instruction from one block to another
# ------------------------------------------------------------------------
my moveOp: ssa -> { id: ssa_id, block: block } -> Void
# ------------------------------------------------------------------------
# Set the target of a conditional branch as TRUE or FALSE.
# This removes the branch and eliminates all unreachable code.
# ------------------------------------------------------------------------
my setBranch: ssa -> { id: ssa_id, cond: Bool } -> Void
# ------------------------------------------------------------------------
# Signal that an SSA has been changed. This uncaches all data structures.
# ------------------------------------------------------------------------
my changed: ssa -> Void
# ------------------------------------------------------------------------
# Pretty printing
# ------------------------------------------------------------------------
my showOp: ssa -> ssa_id -> String
my showVal: ssa -> value -> String
my showRTL: ssa -> rtl -> String
# ------------------------------------------------------------------------
# Graphical viewing
# ------------------------------------------------------------------------
my viewAsCFG: ssa -> graph_layout::layout
my viewAsSSA: ssa -> graph_layout::layout
# ------------------------------------------------------------------------
# Check whether the ssa graph is consistent
# ------------------------------------------------------------------------
my consistencyCheck: ssa -> Void
end