Allocation de registres, solutions |
La fonction forbidden_colors considère comme couleurs impossibles pour une variable v :
(* [forbidden_colors graph coloring v] is the set of colors that cannot be assigned to [v] considering [coloring], a coloring of every vertex in [graph] except [v]. This takes into account [v]'s possible interferences with hardware registers, which are viewed as forbidden colors. *) let forbidden_colors graph coloring v = Vertex.Set.fold (add_color coloring) (ipp graph v) (iph graph v)
Les fonctions simplification et selection sont artificiellement séparées, mais cela permet de mieux comprendre les changements ultérieurs.
On imprime une trace d’exécution dans le mode verbose.
(* The algorithm maintains a transformed graph as it runs. *) (* Each of the functions that follow returns a coloring of the graph that it is passed. *) (* [simplification] removes nodes of low degree. It is the algorithm's initial state. *) let rec simplification graph : coloring = match lowest graph with Some (v, _) -> (* We found a node [v] of lowest degree. Color the rest of the graph, then color [v]. This is what I call selection. *) if G.verbose then printf "Simplifying low vertex: %s.\n%!" (print_vertex graph v); selection graph v None -> (* The graph is empty. Return an empty coloring. *) Vertex.Map.empty (* [selection] removes the vertex [v] from the graph, colors the remaining graph, then selects a color for [v]. *) and selection graph v : coloring = (* Remove [v] from the graph and color what remains. *) let coloring = simplification (remove graph v) in (* Determine which colors are allowed. *) let allowed = ColorSet.diff colors (forbidden_colors graph coloring v) in (* Make a decision. We pick a color randomly among those that are allowed. One could attempt to use biased coloring, that is, to pick a color that seems desirable (or not undesirable) according to the preference edges found in the initial graph. But that is probably not worth the trouble. *) let decision = try Color (ColorSet.choose allowed) with Not_found -> Spill in if G.verbose then printf "Decision concerning %s: %s.\n%!" (print_vertex graph v) (print_decision decision); (* Record our decision and return. *) Vertex.Map.add v decision coloring
La fonction forbidden_slots considère comme couleurs impossibles pour une variable v les emplacements de pile occupés par les variables qui interfèrent avec v.
(* [forbidden_slots graph coloring v] is the set of stack slots that cannot be assigned to [v] considering the (partial) coloring [coloring]. This takes into account [v]'s possible interferences with other spilled vertices. *) let forbidden_slots graph coloring v = Vertex.Set.fold (add_slot coloring) (ipp graph v) Int32Set.empty
Par rapport à l’allocation de registres, ce qui correspondait aux fonctions simplification et selection est ici contenu dans la fonction simplify.
La fonction coalescing utilise pppick avec en argument une fonction anonyme qui renvoie toujours true. En effet, ici toute arête de préférence conduit à une fusion (ce qui ne sera pas le cas dans la suite).
(* Allocation is in two phases, implemented by [coalesce] and [simplify]. Each of these functions produces a coloring of its graph argument. *) (* [simplify] expects a graph that does not contain any preference edges. It picks a vertex [v], removes it, colors the remaining graph, then colors [v] using a color that is still available. Such a color must exist, since there is an unlimited number of colors. Following Appel, [v] is chosen with lowest degree: this will make this vertex easier to color and might (?) help use fewer colors. *) let rec simplify graph : coloring = match lowest graph with Some (v, _) -> if G.verbose then printf "SPILL: Picking vertex: %s.\n" (print_vertex graph v); (* Remove [v] from the graph and color what remains. *) let coloring = simplify (Interference.remove graph v) in (* Choose a color for [v]. *) let decision = allocate_slot (forbidden_slots graph coloring v) in if G.verbose then printf "SPILL: Decision concerning %s: offset %ld.\n" (print_vertex graph v) decision; (* Record our decision and return. *) Vertex.Map.add v decision coloring None -> (* The graph is empty. Return an empty coloring. *) Vertex.Map.empty (* [coalesce] looks for a preference edge, that is, for two vertices [x] and [y] such that [x] and [y] are move-related. In that case, [x] and [y] cannot interfere, because the [Interference] module does not allow two vertices to be related by both an interference edge and a preference edge. If [coalesce] finds such an edge, it coalesces [x] and [y] and continues coalescing. Otherwise, it invokes the next phase, [simplify]. This is aggressive coalescing: we coalesce all preference edges, without fear of creating high-degree nodes. This is good because a move between two pseudo-registers that have been spilled in distinct stack slots is very expensive: one load followed by one store. *) let rec coalesce graph : coloring = match pppick graph (fun _ -> true) with Some (x, y) -> if G.verbose then printf "SPILL: Coalescing %s and %s.\n" (print_vertex graph x) (print_vertex graph y); let graph = Interference.coalesce graph x y in let coloring = coalesce graph in Vertex.Map.add x (Vertex.Map.find y coloring) coloring None -> simplify graph
La fonction selection est conservée à l’identique.
Entre les fonctions simplification et selection, on trouve maintenant les fonctions coalescing et spilling.
(* The algorithm maintains a transformed graph as it runs. It is obtained from the original graph by removing and coalescing vertices. *) (* Each of the functions that follow returns a coloring of the graph that it is passed. These functions correspond to the various states of the algorithm (simplification, coalescing, selection). *) (* [simplification] removes nodes of low degree. It is the algorithm's initial state. *) let rec simplification graph : coloring = match lowest graph with Some (v, d) when d < k -> (* We found a node [v] of low degree. Color the rest of the graph, then color [v]. This is what I call selection. *) if G.verbose then printf "Simplifying low vertex: %s.\n%!" (print_vertex graph v); selection graph v _ -> (* There are no nodes of low degree. Could not simplify further. Start coalescing. *) coalescing graph (* [coalescing] looks for a preference edge that can be collapsed. It is called after [simplification], so it is known, at this point, that there are no nodes of low degree. *) and coalescing graph : coloring = (* Find a preference edge between two vertices that passes George's criterion. *) match pppick graph (georgepp graph) with Some (a, b) -> if G.verbose then printf "Coalescing %s with %s.\n%!" (print_vertex graph a) (print_vertex graph b); (* Coalesce [a] with [b] and color the remaining graph. *) let coloring = simplification (coalesce graph a b) in (* Assign [a] the same color as [b]. *) Vertex.Map.add a (Vertex.Map.find b coloring) coloring None -> (* Find a preference edge between a vertex and a hardware register that passes George's criterion. *) match phpick graph (georgeph graph) with Some (a, c) -> if G.verbose then printf "Coalescing %s with $%s.\n%!" (print_vertex graph a) (MIPS.print c); (* Coalesce [a] with [c] and color the remaining graph. *) let coloring = simplification (coalesceh graph a c) in (* Assign [a] the color [c]. *) Vertex.Map.add a (Color c) coloring None -> (* Could not coalesce further. Start spilling. *) spilling graph (* [spilling] begins after [simplification] and [coalescing], so it is known, at this point, that there are no nodes of low degree. Thus, we are facing a potential spill. However, we do optimistic coloring: we do not spill a vertex right away, but proceed normally, just as if we were doing simplification. So, we pick a vertex [v], remove it, and check whether a color can be assigned to [v] only after coloring what remains of the graph. *) and spilling graph : coloring = match highest graph with Some v -> if G.verbose then printf "Spilling high vertex: %s.\n%!" (print_vertex graph v); selection graph v None -> (* The graph is empty. Return an empty coloring. *) Vertex.Map.empty
La fonction freeze vient s’intercaler entre les fonctions coalescing et spilling.
(* The algorithm maintains a transformed graph as it runs. It is obtained from the original graph by removing, coalescing, and freezing vertices. *) (* Each of the functions that follow returns a coloring of the graph that it is passed. These functions correspond to the various states of the algorithm (simplification, coalescing, freezing, spilling, selection). *) (* [simplification] removes non-move-related nodes of low degree. It is the algorithm's initial state. *) let rec simplification graph : coloring = match lowest_non_move_related graph with Some (v, d) when d < k -> (* We found a non-move-related node [v] of low degree. Color the rest of the graph, then color [v]. This is what I call selection. *) if G.verbose then printf "Simplifying low vertex: %s.\n%!" (print_vertex graph v); selection graph v _ -> (* There are no non-move-related nodes of low degree. Could not simplify further. Start coalescing. *) coalescing graph (* [coalescing] looks for a preference edge that can be collapsed. It is called after [simplification], so it is known, at this point, that all nodes of low degree are move-related. *) and coalescing graph : coloring = (* Find a preference edge between two vertices that passes George's criterion. *) match pppick graph (georgepp graph) with Some (a, b) -> if G.verbose then printf "Coalescing %s with %s.\n%!" (print_vertex graph a) (print_vertex graph b); (* Coalesce [a] with [b] and color the remaining graph. *) let coloring = simplification (coalesce graph a b) in (* Assign [a] the same color as [b]. *) Vertex.Map.add a (Vertex.Map.find b coloring) coloring None -> (* Find a preference edge between a vertex and a hardware register that passes George's criterion. *) match phpick graph (georgeph graph) with Some (a, c) -> if G.verbose then printf "Coalescing %s with $%s.\n%!" (print_vertex graph a) (MIPS.print c); (* Coalesce [a] with [c] and color the remaining graph. *) let coloring = simplification (coalesceh graph a c) in (* Assign [a] the color [c]. *) Vertex.Map.add a (Color c) coloring None -> (* Could not coalesce further. Start freezing. *) freezing graph (* [freezing] begins after [simplification] and [coalescing] are finished, so it is known, at this point, that all nodes of low degree are move-related and no coalescing is possible. [freezing] looks for a node of low degree (which must be move-related) and removes the preference edges that it carries. This potentially opens new opportunities for simplification and coalescing. *) and freezing graph : coloring = match lowest graph with Some (v, d) when d < k -> (* We found a move-related node [v] of low degree. Freeze it and start over. *) if G.verbose then printf "Freezing low vertex: %s.\n%!" (print_vertex graph v); simplification (freeze graph v) _ -> (* Could not freeze further. Start spilling. *) spilling graph
Seule la fonction spilling est modifiée.
(* [spilling] begins after [simplification], [coalescing], and [freezing] are finished, so it is known, at this point, that there are no nodes of low degree. Thus, we are facing a potential spill. However, we do optimistic coloring: we do not spill a vertex right away, but proceed normally, just as if we were doing simplification. So, we pick a vertex [v], remove it, and check whether a color can be assigned to [v] only after coloring what remains of the graph. It is crucial to pick a vertex that has few uses in the code. It would also be good to pick one that has high degree, as this will help color the rest of the graph. Thus, we pick a vertex that has minimum cost, where the cost is obtained as the ratio of the number of uses of the pseudo-registers represented by this vertex in the code by the degree of the vertex. One could also take into account the number of nested loops that the uses appear within, but that is not done here. *) and spilling graph : coloring = match minimum (cost graph) graph with Some v -> if G.verbose then printf "Spilling high vertex: %s.\n%!" (print_vertex graph v); selection graph v None -> (* The graph is empty. Return an empty coloring. *) Vertex.Map.empty
Ce document a été traduit de LATEX par HEVEA