MLRISC

MLRISC Contributors Requirements How to Obtain MLRISC

Overview

Problem Statement Contributions MLRISC Based Compiler MLRISC Intermediate Representation MLRisc Generation Back End Optimizations Register Allocation Machine Description Garbage Collection Safety System Integration Optimizations Graphical Interface Line Counts Systems Using MLRISC Future Work

System

Architecture of MLRISC The MLTREE Language MLTree Extensions MLTree Utilities Instruction Selection Assemblers Machine Code Emitters Delay Slot Filling Span Dependency Resolution The Graph Library The Graph Visualization Library Basic Compiler Graphs The MLRISC IR SSA Optimizations ILP Optimizations Optimizations for VLIW/EPIC Architectur... Register Allocator

Back Ends

The Alpha Back End The PA RISC Back End The Sparc Back End The Intel x86 Back End The PowerPC Back End The MIPS Back End The TI C6x Back End

Basic Types

Annotations Cells Cluster Client Defined Constants Client Defined Pseudo Ops Instructions Instruction Streams Label Expressions Labels Regions Regmap

# Basic Compiler Graphs

Basic Compiler Graphs

Introduction -Dominator/Post-dominator Trees -Control Dependence Graph -Dominance Frontiers -Iterated Dominance Frontiers -Loop Nesting Tree -Static Single Assignment -IDEFS/IUSE sets

## Introduction

In this section we describe the set of core compiler specific graphs and algorithms implemented in MLRISC. Mostly of these algorithms are parameterized with respect to the actual intermediate representation, and as such they do not provide many facilities that are provided by higher abstraction layers, such as in MLRISC IR, or in SSA.

### Dominator/Post-dominator Trees

Dominance is a fundamental concept in compiler optimizations. Node A dominates B iff all paths from the start node to B intersects A. A dual notion is the concept of post-dominance: A post-dominates B iff all paths from B to the stop node intersects A. A (post-)dominator tree can be used to summarize the dominance/post-dominance relationship.

      functor DominatorTree
         (GraphImpl : GRAPH_IMPLEMENTATION) : DOMINATOR_TREE

The functor implements dominator analysis and creates a dominator/post-dominator tree from a graph G. A dominator tree is implemented as a graph with the following definition:

      signature DOMINATOR_TREE = sig
         exception Dominator
         datatype 'n dom_node =
            DOM of { node : 'n, level : int, preorder : int, postorder : int }
         type ('n,'e,'g) dom_info
         type ('n,'e,'g) dominator_tree = ('n dom_node,unit,('n,'e,'g) dom_info) graph
         type ('n,'e,'g) postdominator_tree = ('n dom_node,unit,('n,'e,'g) dom_info) graph

We annotated each node in a dominator tree with three extra fields of information, which is useful for other algorithms:

- `level` is the nesting level of the tree. The root node has level 0, children of the root has level 1 and so on.
- `preorder` is the preorder numbering of a node
- `preorder` is the postorder numbering of a node.

To create a dominator tree and a postdominator tree from a graph, the following function should be called.

      val dominator_trees : ('n,'e,'g) graph ->
              ('n,'e,'g) dominator_tree * ('n,'e,'g) postdominator_tree

We use the algorithm of Tarjan and Lengauer, which runs in time O(|V+E|α(|V+E|)) where α is the functional inverse of the Ackermann function.

To perform many common queries on a dominator tree, we first call the function `methods` to obtain a method object.

       val methods : ('n,'e,'g) dominator_tree -> dominator_methods

The methods are packed into the following type:

        type dominator_methods =
              { dominates              : node_id * node_id -> bool,
                immediately_dominates  : node_id * node_id -> bool,
                strictly_dominates     : node_id * node_id -> bool,
                postdominates          : node_id * node_id -> bool,
                immediately_postdominates : node_id * node_id -> bool,
                strictly_postdominates : node_id * node_id -> bool,
                control_equivalent     : node_id * node_id -> bool,
                idom         : node_id -> node_id, $(* ~1 if none *)$
                idoms        : node_id -> node_id list,
                doms         : node_id -> node_id list,
                ipdom        : node_id -> node_id, $(* ~1 if none *)$
                ipdoms       : node_id -> node_id list,
                pdoms        : node_id -> node_id list,
                dom_lca      : node_id * node_id -> node_id,
                pdom_lca     : node_id * node_id -> node_id,
                dom_level    : node_id -> int,
                pdom_level   : node_id -> int,
                control_equivalent_partitions : unit -> node_id list list
              }

The query methods are as follows:

`dominates(a,b)`
  returns true iff a dominates b
`immediately_dominates(a,b)`
  returns true iff a immediately dominates b
`strictly_dominates(a,b)`
  returns true iff a strictly dominates b
`postdominates(a,b)`
  returns true iff a post-dominates b
`immediately_postdominates(a,b)`
  returns true iff a immediately post-dominates b
`strictly_postdominates(a,b)`
  returns true iff a strictly post-dominates b
`control_equivalent(a,b)`
  returns true iff a dominates b and vice versa
`idom(a)`
  returns the immediate dominator of a, or -1 if none exists
`idoms(a)`
  returns all nodes that a immediately dominates
`doms(a)`
  returns all nodes that a dominates (including a itself)
`ipdom(a)`
  returns the immediate post-dominator of a, or -1 if none exists
`ipdoms(a)`
  returns all nodes that a immediately post-dominates
`pdoms(a)`
  returns all nodes that a post-dominates (including a itself)
`dom_lca(a,b)`
  returns the least common ancestor of a and b in the dominator tree
`pdom_lca(a,b)`
  returns the least common ancestor of a and b in the post-dominator tree
`dom_level(a)`
  returns the nesting level of a in the dominator tree
`pdom_level(b)`
  returns the nesting level of a in the post-dominator tree
`control_equivalent_partitions`
  partitions the graph into a set of control equivalent nodes.

The methods `dom_lca`, `pdom_lca` and `control_equivalent_partitions` executes in O(n) time, where n is the size of the dominator tree. The other methods run in O(1) time.

### Control Dependence Graph

Given two nodes A and B in a control flow graph G, we say that B is control dependent on A iff

- B post-dominates a successor of A
- B does not strictly post-dominates A

Intuitively, B is control dependent on A means that some path in the program that goes through A can by-passed B, and furthermore, A is the point in which this divergence can occur. Control dependence is used to various kinds of analysis and optimizations in a compiler, such as code motion and global scheduling[bernstein-rodeh].

To build a control dependence graph, the functor `ControlDependenceGraph` can be used:

      signature CONTROL_DEPENDENCE_GRAPH = sig
         type ('n,'e,'g) cdg = ('n,'e,'g) graph

         val control_dependence_graph :
               ('e -> bool) ->
               ('n,'e,'g) dominator_tree *
               ('n,'e,'g) postdominator_tree ->
               ('n,'e,'g) cdg
      end
      functor ControlDependenceGraph
         (structure Dom : DOMINATOR_TREE
          structure GraphImpl : GRAPH_IMPLEMENTATION
         ) : CONTROL_DEPENDENCE_GRAPH

The control depedence graph is a subcomponent of the program dependence graph commonly used in modern compiler optimizations.

### Dominance Frontiers

Many algorithms involving the notion of control dependence or dominance can be rephrased in terms of dominance frontiers. A node A is in the dominance frontiers of B iff B dominates a predecessor of A but B does not strictly-dominate A. We denote this as A in DF(B). The dual notion of post-dominance frontiers can be defined analogously using the post-dominator tree\footnote{Control dependence can be defined in terms of post-dominance frontiers.}.

       functor DominanceFrontiers(Dom : DOMINATOR_TREE) : DOMINANCE_FRONTIERS

The functor `DominanceFrontiers` can be used to compute all the dominance frontiers of all the nodes in a graph. It has the following signature.

      signature DOMINANCE_FRONTIERS = sig
        structure Dom : DOMINATOR_TREE
        type dominance_frontiers = node_id list array
        val DFs : ('n,'e,'g) Dom.dominator_tree -> dominance_frontiers
      end

### Iterated Dominance Frontiers

Iterated dominance frontiers (denoted as DF+) are defined as the least fixed point of iterating the operation DF. Formally, define the dominance frontiers on a set S as follows:

  DF(S) = \UnionA in S DF(A)

Define iteration of DF, denoted as DFn, as follows:

  DF1(S) = DF(S)
  DF^{n+1}(S) = DF(S \union DFn(S))

The iterated dominance frontiers DF+(S) on a set S are defined as the limit:

  DF+(S) = limn \to \infty DFn(S)

Iterated dominance frontiers of a set S can be computed in time O(|S|+|V|+|E|) using the algorithm by Sreedhar and Gao[linear-time-IDF]\footnote{ In practice it is often sub-linear in |V|+|E|.}.

       functor DJGraph(Dom : DOMINATOR_TREE) : DJ_GRAPH

The functor `DJGraph` implements this algorithm. It satisfies the signature below:

      signature DJ_GRAPH = sig
         structure Dom : DOMINATOR_TREE
         type ('n,'e,'g) dj_graph = ('n,'e,'g) Dom.dominator_tree
         val dj_graph : ('n,'e,'g) dj_graph ->
             {  DF   : node_id -> node_id list,
                IDF  : node_id -> node_id list,
                IDFs : node_id list -> node_id list
             }
      end

The function `dj_graph` takes a dominator tree and returns three query methods for computing dominance and iterated dominance frontiers. Method `DF` computes DF(v) for a single node v. Method `IDF` computes the DF+(v), and method `IDFs` computes DF+(S) when given a set of node ids. The dominator tree must not be updated while these operations are being performed.

Sreedhar's original algorithm is phrased in terms of the DJ-graph, which is a fusion of the dominator tree with its underlying flowgraph. Our variant operates on the dominator tree and the flowgraph at the same time, without building an intermediate data structure.

Iterated dominance frontiers are used in many algorithms that deal with the notion of dominance. For example, our SSA construction algorithm uses iterated dominance frontiers to identify confluent points in the program where phi-functions are to be placed.

### Loop Nesting Tree

A natural loop L in a graph is a maximal strongly connected component such that all nodes in L are dominated by a single node h, called the loop header. Loops tend to form good optimization candidates and consequently loop detection is an essential task in a compiler. The functor

      functor structure

.sml" target=code>LoopStructure (structure GraphImpl : GRAPH_IMPLEMENTATION structure Dom : DOMINATOR_TREE ) : LOOP_STRUCTURE recognizes all natural loops in a graph and built a loop nesting tree that describes the loop nesting relationship between graphs.

      signature structure.sig" target=code>LOOP_STRUCTURE = sig
        structure Dom : DOMINATOR_TREE
        datatype ('n,'e,'g) loop =
           LOOP of { nesting    : int,
                     header     : node_id,
                     loop_nodes : node_id list,
                     backedges  : 'e edge list,
                     exits      : 'e edge list
                   }

        type ('n,'e,'g) loop_info
        type ('n,'e,'g) loop_structure = (('n,'e,'g) loop,unit, ('n,'e,'g) loop_info) graph

        val loop_structure : ('n,'e,'g) Dom.dominator_tree -> ('n,'e,'g) loop_structure
        val nesting_level : ('n,'e,'g) loop_structure -> node_id array
        val header        : ('n,'e,'g) loop_structure -> node_id array
      end

Our algorithm computes the loop nesting tree in time O((|V|+|E|)α(|V|+|E|)). Each node in this tree represents a loop in the flowgraph, except the root of the tree, which represents the entire graph. Given a flowgraph G, the root of the loop nesting tree is defined to be the sole vertex in `#entry` G. Other nodes in the tree are indexed by the loop header node ids.

Loop detection classifies each loop and for each loop L, the following information is obtained:

- An integer `nesting`. The root of the tree has nesting depth 0. The top level loops have nesting depth 1, etc.
- The node id of the loop `header` h.
- A set of `loop_nodes`. Loop nodes are nodes that are in the strongly connected component L, but excluding the header h and all nodes that are part of any nested loops. Thus all nodes are uniquely partitioned in header nodes and loop nodes, and loop nodes are further partitioned into different sets according to which headers they are immediately nested under.
- A set of `backedges`. A back-edge is an edge that targets the header h and originates from a loop node in L.
- A set of loop `exits`. An exit-edge is an edge that originates from a loop node within L targets a node outside of L. Note that this set does not include any exit-edges contained in loops nested in L but target a node out of L.

### Static Single Assignment

An SSA construction algorithm based on[SSA,Briggs-SSA,linear-time-IDF] is implemented in the following functor:

       functor StaticSingleAssignmentForm
          (Dom : DOMINATOR_TREE) : STATIC_SINGLE_ASSIGNMENT_FORM

SSA-based optimizations in MLRISC are actually implemented on top of a high-level SSA layer described in Section SSA Optimizations. So it is not necessary to use this module directly. Nevertheless, there can be situations in which this module can be specialized in other ways; for example, in the construction of sparse evaluation graphs.

      signature STATIC_SINGLE_ASSIGNMENT_FORM = sig
        structure Dom : DOMINATOR_TREE
        type var     = int
        type phi  = var * var * var list $(* orig def/def/uses *)$
        type renamer = {defs : var list, uses: var list} ->
                       {defs : var list, uses: var list}
        type copy    = {dst : var list, src: var list} -> unit

        val compute_ssa :
            ('n,'e,'g) Dom.dominator_tree ->
            { max_var      : var,
              defs         : 'n node -> var list,
              is_live      : var * int -> bool,
              rename_var   : var -> var,
              rename_stmt  : {rename:renamer,copy:copy} -> 'n node -> unit,
              insert_phi   : {block    : 'n node,
                              in_edges : 'e edge list,
                              phis     : phi list
                             } -> unit
            } -> unit
      end

This module defines the function `compute_ssa`, which constructs an SSA graph. It requires the following information from the client:

- A dominator tree of the flowgraph.
- `max_var` -- the maximum variable id (integer) that exists in the flowgraph. All variables are assumed to be indexed by non-negative integers.
- `defs`(X) -- a function that returns defs(X), i.e.~the set of variable names defined in block X. If a minimal SSA form is desired, this set should include all the definitions in X. If a pruned SSA form is required, this set should include only the set of names that are live-out in X.
- `is_live`(v,X) -- a function that determines if variable v is live-in into block X. If not, a φ-function will not be placed in X. For example, to compute the minimal-SSA form, this function should always return true.
- `rename_var`(v) -- a function that returns a new unique name for variable v.
- `rename_stmt` -- a function of type \sml{{rename:renamer,copy:copy} -> 'n node -> unit} where

          type renamer = {defs : var list, uses: var list} ->
                         {defs : var list, uses: var list}
          type copy    = {dst : var list, src: var list} -> unit

  Function `rename_stmt` is called for each block in the flowgraph in the order of the dominator tree, and is responsible for renaming all the variables in X by calling the functions `renamer` or `copy`. Function `renamer` renames all definitions and uses of a statement, while function `copy` renames of a set of parallel assignments
- `insert_phi`(X,es,phis) -- a function that inserts a set of φ-definitions phis in block X, where es is the list of control flow edges that merge into block X.

### IDEFS/IUSE sets

Reif and Tarjan define the following useful notions for computing approximate birth-points for expressions, which in turn can be used to drive other optimizations. Given a node X, let idom(X) denote the immediate dominator of X. Let def(X) (use(X)) denote all the definitions (uses) in X. Given a path p == v1... vn, define def(p) (use(p)) as

  def(v1... vn) == \unioni in 1 ... n def(vi)
  use(v1... vn) == \unioni in 1 ... n use(vi)

Let P(X) denotes all the paths from idom(X) to X that does not cross idom(X) internally. Then define idef(X) (iuse(X)) as:

  idef(X) == \Unionidom(X) v1 ... vn X in P(X) def(v1... vn)
  iuse(X) == \Unionidom(X) v1 ... vn X in P(X) use(v1... vn)

The sets ipostdef(X) and ipostuse(X) are defined analogously using the postdominator tree.

      signature IDEFS = sig
        type var = int
        val compute_idefs :
            {def_use : 'n Graph.node -> var list * var list,
             cfg     : ('n,'e,'g) Graph.graph
            } ->
            { idefuse      : unit -> (RegSet.regset * RegSet.regset) Array.array,
              ipostdefuse  : unit -> (RegSet.regset * RegSet.regset) Array.array
            }
      end
      structure IDefs : IDEFS

Structure `IDefs` implements the function `comput_idefs` for computing the idef, iuse, ipostdef and ipostuse sets of a control flow graph. It takes as arguments a flowgraph and a function `def_use`, which takes a graph node and returns the def/use sets of the node. It returns two functions `idefuse` and `ipostdefuse` which compute the idef/iuse and ipostdef/ipostuse sets. These sets are returned as arrays indexed by node ids.

Lal George
Allen Leung

Generated by mltex2html
Last modified: Mon Oct 3 20:52:35 UTC 2022 by buildd@x86-grnet-02