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

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

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) = \Union_{A in S} DF(A)

Define iteration of

DF, denoted as

DFⁿ, as follows:

: DF¹(S) = DF(S)
: DF^{n+1}(S) = DF(S \union DFⁿ(S))

The iterated dominance frontiers

DF⁺(S) on a set

S are defined as the limit:

: DF⁺(S) = lim_{n \to \infty} DFⁿ(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