Modern Compiler Implementation in ML

©1998 by Andrew W. Appel

An Alternate Graph Representation for the Tiger Compiler

Chapter 10 describes the Graph module, which presents an abstract view of directed graphs for CFG's and interference graphs. Without so much abstraction, the compiler can run faster: in particular, with the following representation of flowgraphs and interference graphs, liveness analysis and register allocation is about 10 times faster.


Structure Flow, which defines the representation of control flow graphs, need not use the Graph abstraction:
structure Flow =
    datatype node = NODE of {def: Temp.temp list, 
			     use: Temp.temp list, 
			     ismove: bool,
			     succ: node list ref,
			     pred: node list ref,	
			     liveOut: Temp.temp list ref}

    type flowgraph = node list


The flowgraph created by MakeGraph will have accurate def,use,ismove,succ,pred information, but all the liveOut lists will be empty:
structure MakeGraph : 
       val instrs2graph : Assem.instr list -> Flow.flowgraph


Liveness analysis will fill in the liveOut information of each flow node, and will then create an interference graph in which each node has a status of INGRAPH(d), where d=length(!adj).
structure Liveness : 
    structure I : sig
          datatype status = INGRAPH of int (* degree *)
			  | REMOVED
			  | COLORED of string

          datatype node = NODE of {temp: Temp.temp,
				   adj: node list ref,
				   status: status ref}

    datatype igraph = IGRAPH of {graph: I.node list,
			         moves: (I.node*I.node) list}

    val interferenceGraph : Flow.flowgraph -> igraph
    val show : TextIO.outstream * igraph -> unit


The signature COLOR doesn't change, but of course it's referring to a different igraph type than before. The status of a node in an interference graph can be any of:
means that the node is still in the graph, and d the number of nodes on the adj list whose status is either INGRAPH or COLORED.
means that the node has been removed from the graph (for efficiency, do not actually delete the nodes and edges).
means that the node has been assigned color (i.e., register name) r.
signature COLOR =
  structure Frame : FRAME

  type allocation = Frame.register Temp.Table.table

  val color: {interference: Liveness.igraph,
	      initial: allocation,
	      spillCost: Temp.temp -> int,
	      registers: Frame.register list}
	       -> allocation * Temp.temp list