]> Joshua Wise's Git repositories - snipe.git/blame - codegen/igraph.sml
Add strings to type system and parser/lexer
[snipe.git] / codegen / igraph.sml
CommitLineData
6ade8b0a 1(* L3 compiler
0a24e44d 2 * interference graph generator
12aa4087 3 * Takes a list of interfering temps and generates the interference graph
0a24e44d 4 * Author: Chris Lu <czl@andrew.cmu.edu>
12aa4087
JW
5 *)
6
7signature IGRAPH =
8sig
6ade8b0a 9 structure OperSet : ORD_SET
f285fa89 10 where type Key.ord_key = Blarg.oper
6ade8b0a
JW
11 structure LiveMap : ORD_MAP
12 where type Key.ord_key = int
13 structure TempMap : ORD_MAP
14 where type Key.ord_key = Temp.temp
15
16 type predicates = Liveness.predicates
17 type livenesses = Liveness.livenesses
18 type graph = OperSet.set TempMap.map
19 val gengraph : predicates * livenesses -> graph * Temp.temp list
12aa4087
JW
20end
21
22structure Igraph :> IGRAPH =
23struct
6ade8b0a
JW
24 structure OperSet = Liveness.OperSet
25 structure LiveMap = Liveness.LiveMap
26
27 structure TempSet = BinarySetFn (
28 struct
29 type ord_key = Temp.temp
30 val compare = Temp.compare
31 end
32 )
33
34 structure TempMap = SplayMapFn (
35 struct
36 type ord_key = Temp.temp
37 val compare = Temp.compare
38 end)
39
40 type predicates = Liveness.predicates
41 type livenesses = Liveness.livenesses
42 type graph = OperSet.set TempMap.map
43
f285fa89 44 structure X = Blarg
12aa4087 45
6ade8b0a 46 fun add_temp_interfere g (t, oper) =
12aa4087 47 let
6ade8b0a 48 val set = (valOf (TempMap.find (g, t))) handle Option => OperSet.empty
12aa4087 49 in
6ade8b0a
JW
50 TempMap.insert (g, t, OperSet.union (set, OperSet.singleton oper))
51 end
52
53 fun add_interfere g (o1, o2) =
54 let
55 val g = case o1
56 of (X.TEMP t) => add_temp_interfere g (t, o2)
57 | _ => g
58 in
59 case o2
60 of (X.TEMP t) => add_temp_interfere g (t, o1)
61 | _ => g
12aa4087
JW
62 end
63
6ade8b0a
JW
64 fun alltemps preds =
65 LiveMap.foldr
66 (fn (ps, ts) => List.foldr
67 (fn (Liveness.DEF(X.TEMP t), ts') => TempSet.add (ts', t)
68 | (Liveness.USE(X.TEMP t), ts') => TempSet.add (ts', t)
69 | (_, ts') => ts')
70 ts
71 ps
72 )
73 TempSet.empty
74 preds
12aa4087 75
0a24e44d 76 (* val gengraph : interferences -> graph
12aa4087
JW
77 * generates the interference graph from a list of interfering temps
78 * by creating separate interference graphs for each line, concatenating them,
79 * and putting them in canonical form
80 *)
6ade8b0a
JW
81 fun gengraph (preds, lives) : graph * Temp.temp list =
82 (LiveMap.foldri
83 (fn (ln, predlist, map) =>
84 let
85 val ismove = Liveness.ismove predlist
86 in
87 List.foldr
88 (fn (oper, map) =>
89 List.foldr
90 (fn (ln', map) =>
91 let
92 val liveat = valOf (LiveMap.find (lives, ln'))
93 val liveat =
94 if not ismove
95 then liveat
96 else OperSet.difference
97 (liveat,
98 OperSet.addList (OperSet.empty, Liveness.uses predlist))
99 in
100 OperSet.foldr
101 (fn (oper', map) => add_interfere map (oper, oper'))
102 map
103 liveat
104 end)
105 map
106 (Liveness.succs predlist))
107 map
108 (Liveness.defs predlist)
109 end
12aa4087 110 )
6ade8b0a
JW
111 TempMap.empty
112 preds,
113 TempSet.listItems (alltemps preds))
12aa4087 114end
This page took 0.036183 seconds and 4 git commands to generate.