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.

Flow

Structure Flow, which defines the representation of control flow graphs, need not use the Graph abstraction: 
structure Flow =
struct
    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
end

MakeGraph

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

Liveness

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 : 
sig
    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}

    end
    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
end

Color

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:
INGRAPH(d)
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.
REMOVED
means that the node has been removed from the graph (for efficiency, do not actually delete the nodes and edges).
COLORED(r)
means that the node has been assigned color (i.e., register name) r. 
signature COLOR =
sig
  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
end