blob: 254f27ffb605c0e024bab0152cb0b58d0ad35308 (
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
|
(* *********************************************************************)
(* *)
(* 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 Registers
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)
(* Auxiliaries to deal with register classes *)
val class_of_loc: loc -> int
|
