Flowgraphs

Flowgraphs

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.

Target Machine Instructions

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 Data Structure

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.

Flowgraph Generation

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:

This is accomplished using the 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.

MLTREECOMP

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  

[ INDEX | TOP | Parent | Root ]

Author: Lal George
Last Modified: September 4, 1996
Copyright © 1996 Bell Laboratories