blob: e81b6dc5144ed15fa298c31e5ca57172be12906f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
(* *********************************************************************)
(* *)
(* The Compcert verified compiler *)
(* *)
(* Xavier Leroy, INRIA Paris-Rocquencourt *)
(* *)
(* Copyright Institut National de Recherche en Informatique et en *)
(* Automatique. All rights reserved. This file is distributed *)
(* under the terms of the INRIA Non-Commercial License Agreement. *)
(* *)
(* *********************************************************************)
(* Iterated Register Coalescing: George and Appel's graph coloring algorithm *)
open AST
open Registers
open Machregs
open Locations
open XTL
(* The abstract type of interference and preference graphs. *)
type graph
(* Information associated to every variable. *)
type var_stats = {
mutable cost: int; (* estimated cost of a spill *)
mutable usedefs: int (* number of uses and defs *)
}
(* Create an empty graph. The given function associates statistics to
every variable. *)
val init: (reg -> var_stats) -> graph
(* Add an interference between two variables. *)
val add_interf: graph -> var -> var -> unit
(* Add a preference between two variables. *)
val add_pref: graph -> var -> var -> unit
(* Color the graph. Return an assignment of locations to variables. *)
val coloring: graph -> (var -> loc)
(* Machine registers that are reserved and not available for allocation. *)
val reserved_registers: mreg list ref
|