While MLRisc is being generated by the front end, behind the scenes there is the incremental construction of a flowgraph and interprocedural optimization being performed over clusters. As described earlier, BEGINCLUSTER marks the beginning of a flowgraph creation and ENDCLUSTER initiates interprocedural optimizations on the flowgraph that was built. The exact nature of interprocedural optimizations is under the control of a user, and is made available as a function of type cluster -> unit. The chart below shows the main module dependencies related to flowgraph construction and optimization.
The specialization of MLTREE with respect to pseudo-ops and constants has already been discussed. The generic flowgraph data structure (FLOWGRAPHS) must be specialized with respect to a representation of target machine instructions and pseudo-ops. The pseudo-ops in the MLTREE structure are migrated wholesale into the flowgraph, and instructions are used to populate the basic blocks of the flowgraph.
Flowgraph generation FLOWGRAPH_GEN, must be dependent on properties of the instruction set (INSN_PROPERTIES) in order to construct the edges of the flowgraph. It is also dependent on MLTREE. When flow of control terminates with an escaping branch whose destination cannot be determined, it is necessary to convey what registers are live at the branch. This annotation on the flowgraph is necessary for liveness analysis. During MLRisc generation these registers are conveyed using the ESCAPEBLOCK constructor that carries with it a list of MLRisc registers, and hence the dependency on MLTREE.
In the chart, codegen refers to a function of type CD/(cluster -> unit)/, that is invoked on a per-cluster basis to perform inter-procedural optimizations. codegen is constructed by piecing optimization modules together and finally used to specialize the flowgraph generation process.
Finally, MLTREECOMP is specialized with the MLTREE data structure and the flowgraph generation module. The main purpose of MLTREECOMP is to translate MLRisc into target machine instructions and pass on everything else to the flowgraph generation module.
The target machine instructions is specified by the INSTRUCTIONS interface.
signature INSTRUCTIONS = sig
structure Constant : CONSTANT
structure C : CELLS
type instruction
end
The type defined in the CONSTANT module is used to define the immediate operand in the instruction set. CELLS is rarely used within the INSTRUCTIONS module, but helps to reduce the number of parameters required when defining optimization modules. The actual representation of the instruction set remains abstract. When porting the MLRisc technology to a new architecture, it is important to design a representation that will enable fast queries such as definition/use.
The flowgraph is the primary data structure passed between the various optimization phases. The flowgraph data structure is specialized to the pseudo-ops and instructions of the target machine, and is created by the FlowGraphF functor.
functor FlowGraphF(structure I : INSTRUCTIONS
structure P : PSEUDO_OPS)
The FLOWGRAPH interface describes the flowgraph data structure:
signature FLOWGRAPH = sig
structure C : CELLS
structure I : INSTRUCTIONS
structure P : PSEUDO_OPS
datatype block =
PSEUDO of P.pseudo_op
| LABEL of Label.label
| BBLOCK of {
blknum : int,
insns: I.instruction list ref,
liveIn : C.cellset,
succ : int list
...
}
| CODE of I.instruction Vector.vector ref
datatype cluster
CLUSTER of {blocks : block list, regmap: int Array.array ref list}
end
Labels could have easily been implemented using a pseudo-op directive, however they are so pervasive that direct support is provided.
Each basic code block (BBLOCK) has information such as successors succ, predecessors pred, variables live on entry to the block liveIn, and variables live on exit from the block. Warning: the insns instruction list is in reverse order. This choice was arbitrary but was found to be convenient.
A basic block can also be a compressed code block that throws away most of the baggage associated with regular basic blocks. This is useful for cutting down space usage.
Finally, a cluster is a list of basic blocks and a set of register maps. The register maps contain the assignment of pseudo registers to machine register or aliases to other pseudo registers. It is important to emphasize that this is all the information that clusters will ever contain. Any extra information required for different optimizations must be passed directly to those optimizations along with the cluster.
The mlrisc code emitted by the front end is translated to target machine code which is ultimately deposited into the flowgraph. Other components of mltree such as labels and pseudo-ops are passed unchanged to the flowgraph generation module.
Like everything else, the flowgraph generation module must be specialized over:
mltree datatype that has also been specialized, and
FlowGraphGen functor:
functor FlowGraphGen
(structure Flowgraph : FLOWGRAPH
structure InsnProps : INSN_PROPERTIES
structure MLTree : MLTREE
val codegen : Flowgraph.cluster -> unit
sharing Flowgraph.I = InsnProps.I
sharing MLTree.Constant = InsnProps.I.Constant
sharing MLTree.PseudoOp = Flowgraph.P) : FLOWGRAPH_GEN
The INSN_PROPERTIES interface describe queries of the target architecture that are useful for the actual flowgraph construction.
signature INSN_PROPERTIES = sig
structure C : CELLS
structure I : INSTRUCTIONS
datatype kind = IK_JUMP | IK_NOP | IK_INSTR
datatype target = LABELLED of Label.label list | FALLTHROUGH | ESACAPES
val instrKind : I.instruction -> kind
val branchTargets : I.instruction -> target
val moveInstr : I.instruction -> bool
val defUseR : I.instruction -> (int list * int list)
...
end
The FLOWGRAPH_GEN signature is the interface provided by FlowgraphGen. Most of these functions would be used directly to pass components of the mltree datatype. However, special emphasis must be paid to the codegen parameter passed into the FlowGraphGen functor. The codegen function is invoked by the endCluster function, and is used to peform optimizations on the cluster that has just been built.
signature FLOWGRAPH_GEN
structure F : FLOWGRAPH
structure I : INSTRUCTIONS
structure P : INSN_PROPERTIES
structure T : MLTREE
structure Pu : PSEUDO_OPS
val defineLabel : Label.label -> unit
val pseudoOp : Pu.pseudo_op -> unit
val emitInstr : I.instruction -> unit
val exitBlock : T.mlrisc list -> unit
val endCluster : (int list * int Array.array ref list) -> unit
val beginCluster : unit -> unit
end
The type of codegen is cluster -> unit and not cluster -> cluster. The last phase of codegen generation will either be emission of assembly code, or a module that accumilates all the clusters so that machine code can be generated for the compilation unit after all clusters have been processed.
Each architecture will define a module matching MLTREECOMP. The two functions in MLTREECOMP are used to compile the generated mltrees into a flowgraph of target instructions. The implementation of the functions in MLTREECOMP make calls to functions exported by FLOWGRAPH_GEN.
For the DEC Alpha, the functor Alpha32 generates an interface matching MLTREECOMP. The functor takes a structure matching FLOWGRAPH_GEN as an argument. The details of this functor will be explained in more detail later.
functor Alpha32
(structure Flowgen : FLOWGRAPH_GEN sharing ...) : MLTREECOMP
Submit a comment on this page
Author: Lal George
Last Modified: September 4, 1996
Copyright © 1996 Bell Laboratories