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