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

# The Graph Library

The Graph Library

Overview
-The graph signature
-Selectors
-Graph hierarchy
-Mutators
-Iterators
-Manipulating a graph
-Creating a Graph
-Basic Graph Algorithms
-Depth-/Breath-First Search
-Preorder/Postorder numbering
-Topological Sort
-Strongly Connected Components
-Biconnected Components
-Cyclic Test
-Enumerate Simple Cycles
-Minimal Cost Spanning Tree
-Abelian Groups
-Single Source Shortest Paths
-All Pairs Shortest Paths
-Transitive Closure
-Max Flow
-Min Cut
-Max Cardinality Matching
-Node Partition
-Node Priority Queue
Views
- Update Transparency
-Structural Views
-Reversal
-Readonly
-Snapshot
-Map
-Singleton
-Node id renaming
-Union and Sum
-Simple Graph View
-No Entry or No Exit
-Subgraphs
-Trace
-Acyclic Subgraph
-Start and Stop
-Single-Entry/Multiple-Exits
-Behavioral Views
-Behavioral Primitives

## Overview

Graphs are the most fundamental data structure in the MLRISC system, and in fact in many optimizing compilers. MLRISC now contains an extensive library for working with graphs.

All graphs in MLRISC are modeled as edge- and node-labeled directed multi-graphs. Briefly, this means that nodes and edges can carry user supplied data, and multiple directed edges can be attached between any two nodes. Self-loops are also allowed.

A node is uniquely identified by its `node_id`, which is simply an integer. Node ids can be assigned externally by the user, or else generated automatically by a graph. All graphs keep track of all node ids that are currently used, and the method `new_id : unit -> node_id` generates a new unused id.

A node is modeled as a node id and node label pair, (i,l). An edge is modeled as a triple i ->l j, which contains the source and target node ids i and j, and the edge label l. These types are defined as follows:

        type 'n node = node_id * 'n
        type 'e edge = node_id * node_id * 'e

### The graph signature

All graphs are accessed through an abstract interface of the polymorphic type `('n,'e,'g) graph`. Here, `'n` is the type of the node labels, `'e` is the type of the edge labels, and `'g` is the type of any extra information embedded in a graph. We call the latter `graph info`.

Formally, a graph G is a quadruple (V,L,E,I) where V is a set of node ids, L : V -> 'a is a node labeling function from vertices to node labels, E is a multi-set of labeled-edges of type V * V * 'e, and I: 'g is the graph info.

The interface of a graph is packaged into a record of methods that manipulate the base representation:

      signature GRAPH = sig
        type node_id = int
        type 'n node = node_id * 'n
        type 'e edge = node_id * node_id * 'e

        exception Graph of string
        exception Subgraph
        exception NotFound
        exception Unimplemented
        exception Readonly

        datatype ('n,'e,'g) graph = GRAPH of ('n,'e,'g) graph_methods
        withtype ('n,'e,'g) graph_methods =
            {  name            : string,
               graph_info      : 'g,
               (* selectors *)
               (* mutators *)
               (* iterators *)
            }
      end

A few exceptions are predefined in this signature, which have the following informal interpretation. Exception `Graph` is raised when a bug is encountered. The exception `Subgraph` is raised if certain semantics constraints imposed on a graph are violated. The exception `NotFound` is raised if lookup of a node id fails. The exception `Unimplemented` is raised if a certain feature is accessed but is undefined on the graph. The exception `Readonly` is raised if the graph is readonly and an update operation is attempted.

### Selectors

Methods that access the structure of a graph are listed below:

`nodes : unit -> 'n node list`
  Return a list of all nodes in a graph em
`edges : unit -> 'e edge list`
  Return a list of all edges in a graph
`order : unit -> int`
  Return the number of nodes in a graph. The graph is empty if its order is zero
`size : unit -> int`
  Return the number of edges in a graph
`capacity : unit -> int`
  Return the maximum node id in the graph, plus 1. This can be used as a new id
`succ : node_id -> node_id list`
  Given a node id i, return the node ids of all its successors, i.e. { j | i ->l j in E}.
`pred : node_id -> node_id list`
  Given a node id j, return the node ids of all its predecessors, i.e. { i | i ->l j in E}.
`out_edges : node_id -> 'e edge list`
  Given a node id i, return all the out-going edges from node i, i.e. all edges whose source is i.
`in_edges : node_id -> 'e edge list`
  Given a node id j, return all the in-coming edges from node j, i.e. all edges whose target is j.
`has_edge : node_id * node_id -> bool`
  Given two node ids i and j, find out if an edge with source i and target j exists.
`has_node : node_id -> bool`
  Given a node id i, find out if a node of id i exists.
`node_info : node_id -> 'n`
  Given a node id, return its node label. If the node does not exist, raise exception `NotFound`.
``

### Graph hierarchy

A graph G may in fact be a subgraph of a base graph G', or obtained from G' via some transformation T. In such cases the following methods may be used to determine of the relationship between G and G'. An entry edge is an edge in G' that terminates at a node in G, but is not an edge in G. Similarly, an exit edge is an edge in G' that originates from a node in G, but is not an edge in G. An entry node is a node in G that has an incoming entry edge. An exit node is a node in G that has an out-going exit edge. If G is not a subgraph, all these methods will return nil.

`entries : unit -> node_id list`
  Return the node ids of all the entry nodes.
`exits : unit -> node_id list`
  Return the node ids of all the exit nodes.
`entry_edges : node_id -> 'e edge list`
  Given a node id i, return all the entry edges whose sources are i.
`exit_edges : node_id -> 'e edge list`
  Given a node id i, return all the exit edges whose targets are i.

### Mutators

Methods to update a graph are listed below:

`new_id : unit -> node_id`
  Return a unique node id guaranteed to be absent in the current graph.
`add_node : 'n node -> unit`
  Insert node into the graph. If a node of the same node id already exists, replace the old node with the new.
`add_edge : 'e edge -> unit`
  Insert an edge into the graph.
`remove_node : node_id -> unit`
  Given a node id n, remove the node with the node id from the graph. This also automatically removes all edges with source or target n.
`set_out_edges : node_id * 'e edge list -> unit`
  Given a node id n, and a list of edges e1,...,en with sources n, replace all out-edges of n by e1,...,en.
`set_in_edges : node_id * 'e edge list -> unit`
  Given a node id n, and a list of edges e1,...,en with targets n, replace all in-edges of n by e1,...,en.
`set_entries : node_id list -> unit`
  Set the entry nodes of a graph.
`set_exits : node_id list -> unit`
  Set the exit nodes of a graph.
`garbage_collect : unit -> unit`
  Reclaim all node ids of nodes that have been removed by `remove_node`. Subsequent `new_id` will reuse these node ids.
``

### Iterators

Two primitive iterators are supported in the graph interface. Method `forall_nodes` iterates over all the nodes in a graph, while method `forall_edges` iterates over all the edges. Other more complex iterators can be found in other modules.

`forall_nodes : ('n node -> unit) -> unit`
  Given a function f on nodes, apply f on all the nodes in the graph.
`forall_edges : ('e edge -> unit) -> unit`
  Given a function f on edges, apply f on all the edges in the graph.

### Manipulating a graph

Since operations on the graph type are packaged into a record, an ``object oriented'' style of graph manipulation should be used. For example, if `G` is a graph object, then we can obtain all the nodes and edges of `G` as follows.

      val GRAPH g = G
      val edges = #edges g ()
      val nodes = #nodes g ()

We can view `#edges g` as sending the message to `G`. While all this seems like mere syntactic deviation from the usual signature/structure approach, there are two crucial differences which we will exploit: (i) records are first class objects while structures are not (consequently late binding of ``methods'' and cannot be easily simulated on the structure level); (ii) recursion is possible on the type level, while recursive structures are not available. The extra flexibility of this choice becomes apparent with the introduction of views later.

### Creating a Graph

A graph implementation has the following signature

      signature GRAPH_IMPLEMENTATION = sig
        val graph : string * 'g * int -> ('n,'e,'g) graph
      end

The function `graph` takes a string (the name of the graph), graph info, and a default size as arguments and create an empty graph.

The functor `DirectedGraph`:

      functor DirectedGraph(A : ARRAY_SIG) : GRAPH_IMPLEMENTATION

implements a graph using adjacency lists as internal representation. It takes an array type as a parameter. For graphs with node ids that are dense enumerations, the `DynamicArray` structure should be used as the parameter to this functor. The structure `DirectedGraph` is predefined as follows:

      structure DirectedGraph = DirectedGraph(DynamicArray)

For node ids that are sparse enumerations, the structure `HashArray`, which implements integer-keyed hash tables with the signature of arrays, can be used as argument to `DirectedGraph`. For graphs with fixed sizes determined at creation time, the structure `Array` can be used (see also functor `UndoableArray`, which creates arrays with undoable updates, and transaction-like semantics.)

### Basic Graph Algorithms

### Depth-/Breath-First Search

        val dfs : ('n,'e,'g) graph  ->
                  (node_id -> unit) ->
                  ('e edge -> unit) ->
                  node_id list -> unit

The function `dfs` takes as arguments a graph, a function `f : node_id -> unit`, a function `g : 'e edge -> unit`, and a set of source vertices. It performs depth first search on the graph. The function `f` is invoked whenever a new node is being visited, while the function `g` is invoked whenever a new edge is being traversed. This algorithm has running time O(|V|+|E|).

        val dfsfold : ('n,'e,'g) graph  ->
                      (node_id * 'a -> 'a) ->
                      ('e edge * 'b -> 'a) ->
                      node_id list -> 'a * 'b -> 'a * 'b
        val dfsnum :  ('n,'e,'g) graph  ->
                      (node_id * 'a -> 'a) ->
                      { dfsnum : int array, compnum : int array }

The function `bfs` is similar to `dfs` except that breath first search is performed.

        val bfs : ('n,'e,'g) graph  ->
                  (node_id -> unit) ->
                  ('e edge -> unit) ->
                  node_id list -> unit
        val bfsdist : ('n,'e,'g) graph -> node_id list -> int array

### Preorder/Postorder numbering

        val preorder_numbering  : ('n,'e,'g) graph -> int -> int array
        val postorder_numbering : ('n,'e,'g) graph -> int -> int array

Both these functions take a tree T and a root v, and return the preorder numbering and the postorder numbering of the tree respectively.

### Topological Sort

       val topsort : ('n,'e,'g) graph -> node_id list -> node_id list

The function `topsort` takes a graph G and a set of source vertices S as arguments. It returns a topological sort of all the nodes reachable from the set S. This algorithm has running time O(|S|+|V|+|E|).

### Strongly Connected Components

      val strong_components : ('n,'e,'g) graph ->
        (node_id list * 'a -> 'a) -> 'a -> 'a

The function `strong_components` takes a graph G and an aggregate function f with type

       node_id list * 'a -> 'a

and an identity element `x : 'a` as arguments. Function f is invoked with a strongly connected component (represented as a list of node ids) as each is discovered. That is, the function `strong_components` computes

  f(SCCn,f(SCCn-1,..., f(SCC1,x)))

where SCC1,...,SCCn are the strongly connected components in topological order. This algorithm has running time O(|V|+|E|).

### Biconnected Components

      val biconnected_components : ('n,'e,'g) graph ->
             ('e edge list * 'a -> 'a) -> 'a -> 'a

The function `biconnected_components` takes a graph G and an aggregate function f with type

       'e edge list * 'a -> 'a

and an identity element `x : 'a` as arguments. Function f is invoked with a biconnected component (represented as a list of edges) as each is discovered. That is, the function `biconnected_components` computes

  f(BCCn,f(BCCn-1,..., f(BCC1,x)))

where BCC1,...,BCCn are the biconnected components. This algorithm has running time O(|V|+|E|).

### Cyclic Test

      val is_cyclic : ('n,'e,'g) graph -> bool

Function `is_cyclic` tests if a graph is cyclic. This algorithm has running time O(|V|+|E|).

### Enumerate Simple Cycles

      val cycles : ('n,'e,'g) graph -> ('e edge list * 'a -> 'a) -> 'a ->'a

A simple cycle is a circuit that visits each vertex only once. The function `cycles` enumerates all simple cycles in a graph G. It takes as argument an aggregate function f of type

            'e edge list * 'a -> 'a

and an identity element e, and computes as result the expression

  f(cn,f(cn-1,f(cn-2,..., f(c1,e))))

where c1,...,cn are all the simple cycles in the graph. All cycles c1,...,cn are guaranteed to be distinct. A cycle is represented as a sequence of adjacent edges, i.e. in the order of

  v1 -> v2, v2 -> v3, v3 -> v4, ..., vn-1 -> vn, vn -> v1

Our implementation works by first decomposing the graph into its strongly connected components, then uses backtracking to enumerate simple cycles in each component.

### Minimal Cost Spanning Tree

      signature MIN_COST_SPANNING_TREE = sig
        exception Unconnected

        val spanning_tree : { weight    : 'e edge -> 'a,
                              <         : 'a * 'a -> bool
                            } -> ('n, 'e, 'g) graph
                              -> ('e edge * 'a -> 'a) -> 'a -> 'a
      end
      structure Kruskal : MIN_COST_SPANNING_TREE

Structure `Kruskal` implements Kruskal's algorithm for computing a minimal cost spanning tree of a graph. The function `spanning_tree` takes as arguments:

- a `weight` function which when given an edge returns its weight
- an ordering function `<`, which is used to compare the weights
- a graph G
- an accumulator function f, and
- an identity element x

The function `spanning_tree` computes

  f(en,f(en-1,..., f(e1,x)))

where e1,...,en are the edges in a minimal cost spanning tree of the graph. The exception `Unconnected` is raised if the graph is unconnected.

### Abelian Groups

Graph algorithms that deal with numeric weights or distances are parameterized with respect to the signatures `ABELIAN_GROUP` or `ABELIAN_GROUP_WITH_INF`. These are defined as follows:

      signature ABELIAN_GROUP = sig
        type elem
        val +    : elem * elem -> elem
        val -    : elem * elem -> elem
        val      : elem -> elem
        val zero : elem
        val <    : elem * elem -> bool
        val ==   : elem * elem -> bool
      end
      signature ABELIAN_GROUP_WITH_INF = sig
        include ABELIAN_GROUP
        val inf : elem
      end

Signature `ABELIAN_GROUP` specifies an ordered commutative group, while signature `ABELIAN_GROUP_WITH_INF` specifies an ordered commutative group with an infinity element `inf`.

### Single Source Shortest Paths

      signature SINGLE_SOURCE_SHORTEST_PATHS = sig
        structure Num : ABELIAN_GROUP_WITH_INF
        val single_source_shortest_paths :
                      { graph : ('n,'e,'g) graph,
                        weight : 'e edge -> Num.elem,
                        s : node_id
                      } ->
                      { dist : Num.elem array,
                        pred :  node_id array
                      }
      end
      functor Dijkstra(Num : ABELIAN_GROUP_WITH_INF)
         : SINGLE_SOURCE_SHORTEST_PATHS

The functor `Dijkstra` implements Dijkstra's algorithm for single source shortest paths. The function `single_source_shortest_paths` takes as arguments:

- a graph G,
- a `weight` function on edges, and
- the source vertex s.

It returns two arrays `dist` and `pred` indexed by vertices. These arrays have the following interpretation. Given a vertex v,

- `dist`[v] contains the distance of v from the source s
- `pred`[v] contains the predecessor of v in the shortest path from s to v, or -1 if v=s.

Dijkstra's algorithm fails to work on graphs that have negative edge weights. To handle negative weights, Bellman-Ford's algorithm can be used. The exception `NegativeCycle` is raised if a cycle of negative total weight is detected.

      functor BellmanFord(Num : ABELIAN_GROUP_WITH_INF) : sig
         include SINGLE_SOURCE_SHORTEST_PATHS
         exception NegativeCycle
      end

### All Pairs Shortest Paths

      signature ALL_PAIRS_SHORTEST_PATHS = sig
        structure Num : ABELIAN_GROUP_WITH_INF
        val all_pairs_shortest_paths :
                      { graph : ('n,'e,'g) graph,
                        weight : 'e edge -> Num.elem
                      } ->
                      { dist : Num.elem Array2.array,
                        pred :  node_id Array2.array
                      }
      end
      functor FloydWarshall(Num : ABELIAN_GROUP_WITH_INF)
         : ALL_PAIRS_SHORTEST_PATHS

The functor `FloydWarshall` implements Floyd-Warshall's algorithm for all pairs shortest paths. The function `all_pairs_shortest_paths` takes as arguments:

- a graph G, and
- a `weight` function on edges

It returns two 2-dimensional arrays `dist` and `pred` indexed by vertices (u,v). These arrays have the following interpretation. Given a pair (u,v),

- `dist`[u,v] contains the distance from u to v.
- `pred`[u,v] contains the predecessor of v in the shortest path from u to v, or -1 if u=v.

This algorithm runs in time O(|V|3+|E|).

An alternative implementation is available that uses Johnson's algorithm, which works better for sparse graphs:

      functor Johnson(Num : ABELIAN_GROUP_WITH_INF)
         : sig include ALL_PAIRS_SHORTEST_PATHS
               exception Negative Cycle
           end

### Transitive Closure

      signature TRANSITIVE_CLOSURE = sig
         val acyclic_transitive_closure : {  + : ('e * 'e -> 'e), simple : bool }
             -> ('n,'e,'g) graph -> unit
         val acyclic_transitive_closure2 :
            {  + : 'e * 'e -> 'e,
               max : 'e * 'e -> 'e
            }  -> ('n,'e,'g) graph -> unit
         val transitive_closure : ('e * 'e -> 'e) -> ('n,'e,'g) graph -> unit
      structure TransitiveClosure : TRANSITIVE_CLOSURE

Structure `TransitiveClosure` implements in-place transitive closures on graphs. Three functions are implemented. Functions `acyclic_transitive_closure` and `acyclic_transitive_closure2` can be used to compute the transitive closure of an acyclic graph, whereas the function `transitive_closure` computes the transitive closure of a cyclic graph. All take a binary function

       + : 'e * 'e -> 'e

defined on edge labels. Transitive edges are inserted in the following manner:

- `acyclic_transitive_closure`: given u ->l v and v ->l' w, if the flag `simple` is false or if the transitive edge u -> w does not exists, then u ->l + l' w is added to the graph.
- `acyclic_transitive_closure2`: given u ->l v and v ->l' w, the transitive u ->l + l' w is added to the graph. Furthermore, all parallel edges
    u ->l1 w, ..., u ->ln w
  are coalesced into a single edge u ->l w, where l = `max`i = 1 ... n li

### Max Flow

The function `max_flow` computes the maximum flow between the source vertex `s` and the sink vertex `t` in the `graph` when given a `capacity` function.

      signature MAX_FLOW = sig
        structure Num : ABELIAN_GROUP
        val max_flow : { graph    : ('n,'e,'g) graph,
                         s        : node_id,
                         t        : node_id,
                         capacity : 'e edge -> Num.elem,
                         flows    : 'e edge * Num.elem -> unit
                       } -> Num.elem
      end
      functor MaxFlow(Num : ABELIAN_GROUP) : MAX_FLOW

The function `max_flow` returns its result in the follow manner: The function returns the total flow as its result value. Furthermore, the function `flows` is called once for each edge e in the graph with its associated flow fe.

This algorithm uses Goldberg's preflow-push approach, and runs in O(|V|2|E|) time.

### Min Cut

The function `min_cut` computes the minimum (undirected) cut in a `graph` when given a `weight` function on its edges.

      signature MIN_CUT = sig
        structure Num : ABELIAN_GROUP
        val min_cut : { graph    : ('n,'e,'g) graph,
                        weight : 'e edge -> Num.elem
                      } -> node_id list * Num.elem
      end
      functor MinCut(Num : ABELIAN_GROUP) : MIN_CUT

The function `min_cut` returns a list of node ids denoting one side of the cut C (the other side of the cut is (V - C) and the weight cut.

### Max Cardinality Matching

        val matching : ('n,'e,'g) graph -> ('e edge * 'a -> 'a) -> 'a -> 'a * int

The function `BipartiteMatching.matching` computes the maximal cardinality matching of a bipartite graph. As result, the function iterates over all the matched edges and returns the number of matched edges. The algorithm runs in time O(|V||E|).

### Node Partition

      signature NODE_PARTITION = sig
        type 'n node_partition

        val node_partition : ('n,'e,'g) graph -> 'n node_partition
        val !!    : 'n node_partition -> node_id -> 'n node
        val ==    : 'n node_partition -> node_id * node_id -> bool
        val union : 'n node_partition -> ('n node * 'n node -> 'n node) ->
                                             node_id * node_id -> bool
        val union': 'n node_partition -> node_id * node_id -> bool

      end

### Node Priority Queue

      signature NODE_PRIORITY_QUEUE = sig
        type node_priority_queue

        exception EmptyPriorityQueue

        val create         : (node_id * node_id -> bool) -> node_priority_queue
        val fromGraph      : (node_id * node_id -> bool) ->
           ('n,'e,'g) graph -> node_priority_queue
        val isEmpty        : node_priority_queue -> bool
        val clear          : node_priority_queue -> unit
        val min            : node_priority_queue -> node_id
        val deleteMin      : node_priority_queue -> node_id
        val decreaseWeight : node_priority_queue * node_id -> unit
        val insert         : node_priority_queue * node_id -> unit
        val toList         : node_priority_queue -> node_id list
      end

## Views

Simply put, a view is an alternative presentation of a data structure to a client. A graph, such as the control flow graph, frequently has to be presented in different ways in a compiler. For example, when global scheduling is applied on a region (a subgraph of the CFG), we want to be able to concentrate on just the region and ignore all nodes and edges that are not part of the current focus. All transformations that are applied on the current region view should be automatically reflected back to the entire CFG as a whole. Furthermore, we want to be able to freely intermix graphs and subgraphs of the same type in our program, without having to introducing sums in our type representations.

The `subgraph_view` view combinator accomplishes this. `Subgraph` takes a list of nodes and produces a graph object which is a view of the node induced subgraph of the original graph. All modification to the subgraph are automatically reflected back to the original graph. From the client point of view, a graph and a subgraph are entirely indistinguishable, and furthermore, graphs and subgraphs can be freely mixed together (they are the same type from ML's point of view.)

This transparency is obtained by selective method overriding, composition, and delegation. For example, a generic graph object provides the following methods for setting and looking up the entries and exits from a graph.

        set_entries  : node_id list -> unit
        set_exits    : node_id list -> unit
        entries      : unit -> node_id list
        exits        : unit -> node_id list

For example, a CFG usually has a single entry and a single exit. These methods allow the client to destinate one node as the entry and another as the exit. In the case of subgraph view, these methods are overridden so that the proper conventions are preserved: a node in a subgraph is an entry (exit) iff there is an in-edge (out-edge) from (to) outside the (sub-)graph. Similarly, the methods `entry_edges` and `exit_edges` can be used return the entry and exit edges associated with a node in a subgraph.

        entry_edges  : node_id -> 'e edge list
        exit_edges   : node_id -> 'e edge list

These methods are initially defined to return `[]` in a graph and subsequently overridden in a subgraph.

### Update Transparency

Suppose a view G' is created from some base graphs or views. Update transparency refers to the fact that G' behaves consistently according to its conventions and semantics when updates are performed. There are 4 different type of update transparencies:

- update opaque A update opaque view disallows updates to both itself and its base graphs.
- globally update transparent A globally update transparent view allows updates to its base graphs but not to itself. Changes will then be automatically reflected in the view.
- locally update transparent A locally update transparent view allows updates to itself but not to its base graphs. Changes will be automatically reflected to the base graphs.
- fully update transparent A fully update transparent view allows updates through its methods or through its base graphs'.

### Structural Views

### Reversal

        val ReversedGraphView.rev_view : ('n,'e,'g) graph -> ('n,'e,'g) graph

This combinator takes a graph G and produces a view GR which reverses the direction of all its edges, including entry and exit edges. Thus the edge i ->l j in G becomes the edge j ->l i in GR. This view is fully update transparent.

### Readonly

        val ReadOnlyGraphView.readonly_view : ('n,'e,'g) graph -> ('n,'e,'g) graph

This function takes a graph G and produces a view G' in which no mutator methods can be used. Invoking a mutator method raises the exception `Readonly`. This view is globally update transparent.

### Snapshot

        functor GraphSnapShot(GI : GRAPH_IMPLEMENTATION) : GRAPH_SNAPSHOT
        signature GRAPH_SNAPSHOT = sig
           val snapshot : ('n,'e,'g) graph ->
             { picture : ('n,'e,'g) graph, button : unit -> unit }
        end

The function `snapshot` can be used to keep a cached copy of a view a.k.a the `picture`. This cached copy can be updated locally but the modification will not be reflected back to the base graph. The function `button` can be used to keep the view and the base graph up-to-date.

### Map

        val IsomorphicGraphView.map :
          ('n node -> 'n') -> ('e edge -> 'e') -> ('g -> 'g') ->
          ('n,'e,'g) graph -> ('n','e','g') graph

The function `map` is a generalization of the `map` function on lists. It takes three functions

     f : 'n node -> 'n
     g : 'e edge -> 'e
     h : 'g -> g'

and a graph G=(V,L,E,I) as arguments. It computes the view G'=(V,L',E',I') where

  L'(v) = f(v,L(v)) \mbox{\ for all <math class="inline"><i>v isin; V</i></math>}
  E' = { i ->g(i,j,l) j | i ->l j in E }
  I' = h(I)

### Singleton

        val SingletonGraphView.singleton_view : ('n,'e,'g) graph -> node_id -> ('n,'e,'g) graph

Function `singleton_view` takes a graph G and a node id v (which must exists in G) and return an edge-free graph with only one node (v). This view is opaque.

### Node id renaming

        val RenamedGraphView.rename_view : int -> ('n,'e,'g) graph -> ('n','e','g') graph

The function `rename_view` takes an integer n and a graph G and create a fully update transparent view where all node ids are incremented by n. Formally, given graph G=(V,E,L,I) it computes the view G'=(V',E',L',I) where

  V' = { v + n | v in V }
  E' = { i+n ->l j+n | i ->l j in E }
  L' = λ v. L(v-n)

### Union and Sum

        val UnionGraphView.union_view : ('g * 'g') -> 'g'') ->
           ('n,'e,'g) graph * ('n,'e,'g') graph -> ('n','e','g'') graph
        GraphCombinations.unions : ('n,'e,'g) graph list -> ('n,'e,'g) graph
        GraphCombinations.sum : ('n,'e,'g) graph * ('n,'e,'g) graph -> ('n,'e,'g) graph
        GraphCombinations.sums : ('n,'e,'g) graph list -> ('n,'e,'g) graph

Function `union_view` takes as arguments a function f, and two graphs G=(V,L,E,I) and G'=(V',L',E',I'), it computes the union G+G' of these graphs. Formally, G \union G'=(V'',L'',E'',I'') where

  V'' = V \union V'
  L'' = L \overrides L'
  E'' = E \union E'
  I'' = f(I,I')

The function `sum` constructs a disjoint sum of two graphs.

### Simple Graph View

       val SimpleGraph.simple_graph : (node_id * node_id * 'e list -> 'e) ->
        ('n,'e,'g) graph -> ('n,'e,'g) graph

Function `simple_graph` takes a merge function f and a multi-graph G as arguments and return a view in which all parallel multi-edges (edges with the same source and target) are combined into a single edge: i.e. any collection of multi-edges between the same source s and target t and with labels l1,...,ln, are replaced by the edge s ->lst t in the view, where lst = f(s,t,[l1,...,ln]). The function f is assumed to satisfy the equality l = f(s,t,[l]) for all l, s and t.

### No Entry or No Exit

       val NoEntryView.no_entry_view : ('n,'e,'g) graph -> ('n,'e,'g) graph
       NoEntryView.no_exit_view : ('n,'e,'g) graph -> ('n,'e,'g) graph

The function `no_entry_view` creates a view in which all entry edges (and thus entry nodes) are removed. The function `no_exit_view` is the dual of this and creates a view in which all exit edges are removed. This view is fully update transparent. It is possible to remove all entry and exit edges by composing these two functions.

### Subgraphs

        val SubgraphView.subgraph_view : node_id list -> ('e edge -> bool) ->
          ('n,'e,'g) graph -> (n','e','g') graph

The function `subgraph_view` takes as arguments a set of node ids S, an edge predicate p and a graph G=(V,L,E,I). It returns a view in which only the visible nodes are S and the only visible edges e are those that satisfy p(e) and with sources and targets in S. S must be a subset of V.

        val Subgraph_P_View.subgraph_p_view : node_id list ->
          (node_id -> bool) -> (node_id * node_id -> bool) ->
          ('n,'e,'g) graph -> ('n','e','g') graph

The function `subgraph_view` takes as arguments a set of node ids S, a node predicate p, an edge predicate q and a graph G=(V,L,E,I). It returns a view in which only the visible nodes v are those in S satisfying p(v), and the only visible edges e are those that satisfy q(e) and with sources and targets in S. S must be a subset of V.

### Trace

        val TraceView.trace_view : node_id list -> ('n,'e,'g) graph -> ('n','e','g') graph

% \includegraphics[width=2.8in]{../pictures/pdf/trace}

A trace view

A trace is an acyclic path in a graph. The function `trace_view` takes a trace of node ids v1,...,vn and a graph G and returns a view in which only the nodes are visible. Only the edges that connected two adjacent nodes on the trace, i.e. vi -> vi+1 for some i = 1 ... n-1 are considered be within the view. Thus if there is an edge vi -> vj in G where j <> i+1 this edge is not considered to be within the view --- it is considered to be an exit edge from vi and an entry edge from vj however. Trace views can be used to construct a CFG region suitable for trace scheduling [trace-scheduling,bulldog].

Figure Trace illustrates this concept graphically. Here, the trace view is formed from the nodes `A, C, D, F` and `G`. The solid edges linking the trace is visible within the view. All other dotted edges are considered to be either entry of exit edges into the trace. The edge from node `G` to `A` is considered to be both since it exits from `G` and enters into `A`.

### Acyclic Subgraph

        val AcyclicSubgraphView.acyclic_view :
          node_id list ->
          ('n,'e,'g) graph -> ('n,'e,'g) graph

\includegraphics[width=2.8in]{../pictures/pdf/subgraph} %

An acyclic subgraph

The function `acyclic_view` takes an ordered list of node ids v1,...,vn and a graph G as arguments and return a view G' such that only the nodes v1,...,vn are visible. In addition, only the edges with directions consistent with the order list are considered to be within the view. Thus an edge vi -> vj from G is in G' iff 1 <= i < j <= n. Acyclic views can be used to construct a CFG region suitable for DAG scheduling. Figure Acyclic Subgraph illustrates this concept graphically.

### Start and Stop

        val StartStopView.start_stop_view :
          { start : 'n node,
             stop  : 'n node,
             edges : 'e edge list
          } -> ('n,'e,'g) graph -> ('n','e','g') graph

The function `start_stop_view`

### Single-Entry/Multiple-Exits

        SingleEntryMultipleExit.SEME
          exit : 'n node -> ('n,'e,'g) graph -> ('n,'e,'g) graph

The function `SEME` converts a single-entry/multiple-exits graph G into a single entry/single exit graph. It takes an exit node e and a graph G and returns a view G'. Suppose i ->l j is an exit edge in G. In view G this edge is replaced by a new normal edge i ->l e and a new exit edge e ->l j. Thus e becomes the sole exit node in the new view.

### Behavioral Views

### Behavioral Primitives

Figure Behavioral Primitives lists the set of behavioral primitives defined in structure `GraphWrappers`. These functions allow the user to attach an action a to a mutator method m such that whenever m is invoked so does a. Given a graph G, the combinator

        do_before_xxx : f -> ('n,'e,'g) graph -> ('n,'e,'g) graph

returns a view G' such that whenever method xxx is invoked in G', the function f is called. Similarly, the combinator

        do_after_xxx : f -> ('n,'e,'g) graph -> ('n,'e,'g) graph

creates a new view G'' such that the function f is called after the method is invoked.

      do_before_new_id : (unit -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_new_id : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_before_add_node : ('n node -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_add_node : ('n node -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_before_add_edge : ('e edge -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_add_edge : ('e edge -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_before_remove_node : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_remove_node : (node_id -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_before_set_in_edges : (node_id * 'e edge list -> unit) ->
         ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_set_in_edges : (node_id * 'e edge list -> unit) ->
         ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_before_set_out_edges : (node_id * 'e edge list -> unit) ->
         ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_set_out_edges : (node_id * 'e edge list -> unit) ->
         ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_before_set_entries : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_set_entries : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_before_set_exits : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
      do_after_set_exits : (node_id list -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph

Behavioral view primitives

Frequently it is not necessary to know precisely by which method a graph's structure has been modified, only that it is. The following two methods take a notification function f and returns a new view. f is invoked before a modification is attempted in a view created by `do_before_changed`. It is invoked after the modification in a view created by `do_after_changed`.

        do_before_changed : (('n,'e,'g) graph -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph
        do_after_changed : (('n,'e,'g) graph -> unit) -> ('n,'e,'g) graph -> ('n,'e,'g) graph

Behavioral views created by the above functions are all fully update transparent.

Lal George
Allen Leung

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