| | 1 | (* L3 compiler |
| | 2 | * colorizer |
| | 3 | * colors a graph and returns a list of nodes with associated colors |
| | 4 | * Author: Joshua Wise <jwise@andrew.cmu.edu> |
| | 5 | * Author: Chris Lu <czl@andrew.cmu.edu> |
| | 6 | *) |
| | 7 | |
| | 8 | signature COLORIZER = |
| | 9 | sig |
| | 10 | structure OperSet : ORD_SET |
| | 11 | where type Key.ord_key = Blarg.oper |
| | 12 | structure LiveMap : ORD_MAP |
| | 13 | where type Key.ord_key = int |
| | 14 | structure TempMap : ORD_MAP |
| | 15 | where type Key.ord_key = Temp.temp |
| | 16 | |
| | 17 | type temps = Temp.temp list |
| | 18 | type colorlist = (Temp.temp * int) list |
| | 19 | type igraph = OperSet.set TempMap.map |
| | 20 | |
| | 21 | val colorize : temps -> Igraph.graph -> colorlist |
| | 22 | end |
| | 23 | |
| | 24 | structure Colorizer :> COLORIZER = |
| | 25 | struct |
| | 26 | structure OperSet = Igraph.OperSet |
| | 27 | structure LiveMap = Igraph.LiveMap |
| | 28 | structure TempMap = Igraph.TempMap |
| | 29 | |
| | 30 | type temps = Temp.temp list |
| | 31 | type colorlist = (Temp.temp * int) list |
| | 32 | type igraph = OperSet.set TempMap.map |
| | 33 | |
| | 34 | structure X = Blarg |
| | 35 | |
| | 36 | (* val color_single : igraph -> Temp.temp * colorlist -> colorlist |
| | 37 | * color_single graph (temp, regs) => takes an interference graph, the temp to be colored, and the |
| | 38 | * already-colored nodes, colors the temp, and adds it to the list |
| | 39 | * this is a helper function for the foldr in colorize |
| | 40 | *) |
| | 41 | fun color_single (graph: Igraph.graph) (temp, regs) = |
| | 42 | let |
| | 43 | (* Grab the set of interfering operands from the graph *) |
| | 44 | val interfere = case TempMap.find (graph, temp) |
| | 45 | of SOME(l) => OperSet.listItems l |
| | 46 | | NONE => [] |
| | 47 | (* | NONE => raise ErrorMsg.InternalError "Temporary not found in graph" *) |
| | 48 | |
| | 49 | (* Grab the subset of those that are already colorized *) |
| | 50 | val colorized = |
| | 51 | List.filter |
| | 52 | (fn (t,_) => |
| | 53 | List.exists |
| | 54 | (fn X.TEMP t' => Temp.eq (t, t') |
| | 55 | | _ => false) |
| | 56 | interfere |
| | 57 | ) regs |
| | 58 | |
| | 59 | (* Grab the subset of those that are fixed colors *) |
| | 60 | val fixeds = |
| | 61 | List.filter |
| | 62 | (fn X.REG _ => true |
| | 63 | | _ => false) |
| | 64 | interfere |
| | 65 | |
| | 66 | (* Grab the register number of the already-colorized ones *) |
| | 67 | val ints = |
| | 68 | (List.map |
| | 69 | (fn (_,i) => i) |
| | 70 | colorized) |
| | 71 | @ (List.map |
| | 72 | (fn X.REG a => X.regtonum a |
| | 73 | | loss => raise ErrorMsg.InternalError ("Bad kind of specreg " ^ (X.pp_oper loss))) |
| | 74 | fixeds) |
| | 75 | (* Greedy-colorize -- pick the lowest number that isn't used by a neighbor *) |
| | 76 | fun greedy i l = |
| | 77 | if (List.exists (fn a => a = i) l) |
| | 78 | then greedy (i+1) l |
| | 79 | else i |
| | 80 | |
| | 81 | val newcolor = greedy 0 ints |
| | 82 | (* val () = print (" Assigned color "^(Int.toString newcolor)^" to temp "^(Temp.name temp)^"\n") *) |
| | 83 | in |
| | 84 | (temp, (greedy 0 ints)) :: regs |
| | 85 | end |
| | 86 | |
| | 87 | (* val colorize : temps -> igraph -> colorlist |
| | 88 | * colorizes a graph given the graph representation and the order in which to color |
| | 89 | * nodes, returns a list of nodes numbered with their respective color *) |
| | 90 | fun colorize order graph = foldl (color_single graph) nil order |
| | 91 | |
| | 92 | end |
git.joshuawise.com / snipe.git / blame_incremental