(**********************************************************************)
(* (c) Greg Morrisett, Steve Zdancewic                                *)
(*     June 1998, all rights reserved.                                *)
(**********************************************************************)

(* regifg.mli
 *
 * The data structure for interference graphs.
 *)

open Tal
open Set
open Cfg
open Identifier

type if_graph 
(* type live_range *)

(* Builds an interference graph from a control-flow graph and the number of *)
(* colors to use.  Each virtual register is represented by a single live-range.*)
(* Assumes that liveness analysis has been performed on the control flow graph.*)
(* Puts all live-ranges into the initial set and all register to register *)
(* moves into the active set *)
val build : cf_graph -> int -> if_graph

(* Used to signal that there are no spilled live-ranges intersecting the reg *)
(* set in spill_ifg *)
exception NoSpills

(* Constructs a subgraph of the given interference graph such that the only *)
(* live ranges included are those spilled simple lr's containing regs in the *)
(* given reg set. This subgraph can then be used to find appropriate stack *)
(* slots for each of the spilled registers. *)
val spill_ifg : if_graph -> reg set -> (if_graph * reg set)

(* Given an ifg, virtual register, and function label returns the true if *)
(* the live-range containing that register is a cross-call spill. *)
val reg_cc_spilled : if_graph -> reg -> identifier -> bool

(* Dumps the current state of the interference graph to standard out.  Used *)
(* for debugging. *)
val print_ifg : if_graph -> bool -> bool -> bool -> bool -> bool -> unit
val print_regmap : (reg, reg) Dict.dict -> unit

(* Takes an already built interference graph and initializes the appropriate *)
(* sets of live-ranges and move instructions *)
val initialize_sets : if_graph -> unit

(* The following aid in controlling the register allocation loop. *)
val simplifiable : if_graph -> bool
val coalescable : if_graph -> bool
val freezable : if_graph -> bool
val splitable : if_graph -> bool
val spillable : if_graph -> bool
val actual_spills : if_graph -> bool

(* Removes a live-range from the graph *)
val simplify : if_graph -> unit
val simplify_spills : if_graph -> unit

(* Coalesces two live-ranges *)
val coalesce_regs : if_graph -> unit
val coalesce_spills : if_graph -> unit

(* Freezes moves so that they won't be considered for future coalescing *)
val freeze : if_graph -> unit

(* Selects a spill candidate and either spills it or splits it depending on *)
(* whether it's a compound cross-module live-range or not. *)
val spill : if_graph -> unit

(* Splits a live-range into connected components each lying within a single *)
(* function.  Those atomic live-ranges that cross function calls are put *)
(* into individual live-ranges.  All the moves associated with the boundaries *)
(* of the split are frozen, so they won't be considered for coalescing *)
val split : if_graph -> unit

(* Attempts to color the interference graph for register usage.  If a *)
(* live-range must be spilled, it is put in the spilled set. Returns a mapping *)
(* from registers to physical registers. *)
val color_regs : if_graph -> (reg, reg) Dict.dict

(* Colors an interference graph without spilling, tries to use the fewest *)
(* number of stack slots possible. Returns a mapping from registers to *)
(* stack slots and the number of slots needed *)
val color_spills : if_graph -> (reg, int) Dict.dict * int

(* EOF: regifg.mli *)
