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
SML/NJ Validate this page
Generated by mltex2html
Last modified: Thu Jan 9 19:38:15 EST 2003 by leunga@slinky