]>
Commit | Line | Data |
---|---|---|
1 | (* L2 Compiler | |
2 | * Takes a interference graph and generates an ordering for coloring | |
3 | * Author: Joshua Wise <jwise@andrew.cmu.edu> | |
4 | * Author: Chris Lu <czl@aundrew.cmu.edu> | |
5 | *) | |
6 | ||
7 | signature COLORORDER = | |
8 | sig | |
9 | type igraph = (Temp.temp * x86.oper list) list | |
10 | type ordering = Temp.temp list | |
11 | ||
12 | val colororder : igraph -> ordering | |
13 | end | |
14 | ||
15 | structure ColorOrder :> COLORORDER = | |
16 | struct | |
17 | structure T = Temp | |
18 | structure X = x86 | |
19 | ||
20 | type igraph = (Temp.temp * x86.oper list) list | |
21 | type ordering = Temp.temp list | |
22 | ||
23 | fun colororder graph = | |
24 | let | |
25 | val initialWeights = map (fn (t, _) => (t, 0)) graph | |
26 | ||
27 | fun sortWeights weights = (* Sort the weights such that the largest is at left, ready to be grabbed. *) | |
28 | ListMergeSort.sort (fn ((_, a), (_, b)) => a < b) weights | |
29 | ||
30 | (* Chooses one temporary to pick, and updates the weights. *) | |
31 | fun orderOne (weights : (Temp.temp * int) list) : Temp.temp * (Temp.temp * int) list = | |
32 | let | |
33 | val sorted = sortWeights weights | |
34 | val (chosen, w) = List.hd sorted (* Grab the temp with the highest weight. *) | |
35 | val remaining = List.tl sorted | |
36 | val neighbors = (* Grab all the neighbors for some given temp. *) | |
37 | List.hd | |
38 | (List.map (fn (_, neighbors) => neighbors) | |
39 | (List.filter (fn (t, _) => T.compare (t, chosen) = EQUAL) graph)) | |
40 | val newWeights = | |
41 | List.map | |
42 | (fn (t, wt) => | |
43 | (t, | |
44 | if (List.exists | |
45 | (fn X.TEMP t' => (T.compare (t, t') = EQUAL) | |
46 | | _ => false) | |
47 | neighbors) | |
48 | then (wt + 1) | |
49 | else wt | |
50 | ) | |
51 | ) remaining | |
52 | in | |
53 | (chosen, newWeights) | |
54 | end | |
55 | ||
56 | (* Recursively order until we run out of things to order. *) | |
57 | fun keepOrdering (nil : (Temp.temp * int) list) : Temp.temp list = nil | |
58 | | keepOrdering (weights) = | |
59 | let | |
60 | val (chosen, newWeights) = orderOne weights | |
61 | in | |
62 | chosen :: (keepOrdering newWeights) | |
63 | end | |
64 | in | |
65 | (keepOrdering initialWeights) | |
66 | end | |
67 | end |