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 Visualization Library

The Graph Visualization Library

Overview Graph Layout Layout style Graph Displays Graph Viewers

## Overview

Visualization is an important aid for debugging graph algorithms. MLRISC provides a simple facility for displaying graphs that adheres to the graph interface. Two graph viewer back-ends are currently supported. (An interface to the dot tool is still available but is unsupported.)

- vcg -- this tool supports the browsing of hierarchical graphs, zoom in/zoom out functions. It can handle up to around 5000 nodes in a graph.
- daVinci -- this tool supports a separate ``survey'' view from the main view and text searching. This tool is slower than vcg but it has a nicer interface, and can handle up to around 500 nodes in a graph.

All graph viewing back-ends work in the same manner. They take a graph whose nodes and edges are annotated with layout instructions and translate these layout instructions into the target description language. For vcg, the target description language is GDL. For daVinci, it is a language based on s-expressions.

## Graph Layout

Some basic layout formats are defined structure `GraphLayout` are:

      structure GraphLayout = struct
        datatype format =
          LABEL of string
        | COLOR of string
        | NODE_COLOR of string
        | EDGE_COLOR of string
        | TEXT_COLOR of string
        | ARROW_COLOR of string
        | BACKARROW_COLOR of string
        | BORDER_COLOR of string
        | BORDERLESS
        | SHAPE of string
        | ALGORITHM of string
        | EDGEPATTERN of string

        type ('n,'e,'g) style =
           { edge  : 'e edge -> format list,
             node  : 'n node -> format list,
             graph : 'g -> format list
           }
        type layout = (format list, format list, format list) graph
      end

The interpretation of the layout formats are as follows:

`LABEL` l | Label a node or an edge with the string l
`COLOR` c | Use color c for a node or an edge
`NODE_COLOR` c | Use color c for a node
`EDGE_COLOR` c | Use color c for an edge
`TEXT_COLOR` c | Use color c for the text within a node
`ARROW_COLOR` c | Use color c for the arrow of an edge
`BACKARROW_COLOR` c | Use color c for the arrow of an edge
`BORDER_COLOR` c | Use color c for the border in a node
`BORDERLESS` | Disable border for a node
`SHAPE` s | Use shape s for a node
`ALGORITHM` a | Use algorithm a to layout the graph
`EDGEPATTERN` p | Use pattern p to layout an edge

Exactly how these formats are interpreted is determined by the visualization tool that is used. If a feature is unsupported then the corresponding format will be ignored. Please see the appropriate reference manuals of vcg and daVinci for details.

## Layout style

How a graph is layout is determined by its layout style:

        type ('n,'e,'g) style =
           { edge  : 'e edge -> format list,
             node  : 'n node -> format list,
             graph : 'g -> format list
           }

which is simply three functions that convert nodes, edges and graph info into layout formats. The function `makeLayout` can be used to convert a layout style into a layout, which can then be passed to a graph viewer to be displayed.

        GraphLayout.makeLayout : ('n,'e,'g) style -> ('n,'e,'g) graph -> layout

## Graph Displays

A graph display is an abstraction for the interface that converts a layout graph into an external graph description language. This abstraction is defined in the signature below.

      signature GRAPH_DISPLAY = sig
        val suffix    : unit -> string
        val program   : unit -> string
        val visualize : (string -> unit) -> GraphLayout.layout -> unit
      end

- `suffix` is the common file suffix used for the graph description language
- `program` is the common name of the graph visualization tool
- `visualize` is a function that takes a string output function and a layout graph G as arguments and generates a graph description based on G

## Graph Viewers

The graph viewer functor GraphViewer takes a graph display back-end and creates a graph viewer that can be used to display any layout graph.

      signature GRAPH_VIEWER = sig
         val view : GraphLayout.layout -> unit
      end
      functor GraphViewer(D : GRAPH_DISPLAY) : GRAPH_VIEWER

Lal George
Allen Leung

Generated by mltex2html
Last modified: Fri Oct 11 18:19:52 UTC 2019 by buildd@x86-grnet-02