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