1%% -*- erlang-indent-level: 2 -*- 2%% 3%% Licensed under the Apache License, Version 2.0 (the "License"); 4%% you may not use this file except in compliance with the License. 5%% You may obtain a copy of the License at 6%% 7%% http://www.apache.org/licenses/LICENSE-2.0 8%% 9%% Unless required by applicable law or agreed to in writing, software 10%% distributed under the License is distributed on an "AS IS" BASIS, 11%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12%% See the License for the specific language governing permissions and 13%% limitations under the License. 14%% 15%%----------------------------------------------------------------------- 16%% File : hipe_optimistic_regalloc.erl 17%% Authors : NilsOla Linnermark <nilsola@abc.se> 18%% Petter Holmberg <petter.holmberg@usa.net> 19%% Purpose : Play paintball with registers on a target machine. We win 20%% if they are all colored. This is an optimistic coalescing 21%% register allocator. 22%% Created : Spring 2005 23%%----------------------------------------------------------------------- 24 25-module(hipe_optimistic_regalloc). 26-export([regalloc/7]). 27 28-ifndef(DEBUG). 29%%-define(DEBUG,true). 30-else. 31-ifndef(COMPARE_ITERATED_OPTIMISTIC). 32%% If this macro is turned on you can easily compare 33%% each intermediate step in the iterated coalescing 34%% register allocator and the optimitsitc coalescing 35%% register allocator. This is useful for debugging - 36%% many small erlang functions should render the same 37%% register allocaton for both allocators. 38-define(COMPARE_ITERATED_OPTIMISTIC, true). 39-endif. 40-endif. 41-include("../main/hipe.hrl"). 42-ifdef(DEBUG_PRINTOUTS). 43-define(print_adjacent(IG), hipe_ig:print_adjacent(IG)). 44-define(print_degrees(IG), hipe_ig:print_degrees(IG)). 45-define(print_spill_costs(IG), hipe_ig:print_spill_costs(IG)). 46-define(mov_print_memberships(MV), hipe_moves:print_memberships(MV)). 47-define(reg_print_memberships(WL), hipe_reg_worklists:print_memberships(WL)). 48-define(print_alias(A), printAlias(A)). 49-define(print_colors(T,C), printColors(T,C)). 50-else. 51-define(print_adjacent(IG), no_print). 52-define(print_degrees(IG), no_print). 53-define(print_spill_costs(IG), no_print). 54-define(mov_print_memberships(MV), no_print). 55-define(reg_print_memberships(WL), no_print). 56-define(print_alias(A), no_print). 57-define(print_colors(T,C), no_print). 58-endif. 59 60 61%%----------------------------------------------------------------------- 62%% Function: regalloc 63%% 64%% Description: Creates a K coloring for a function. 65%% Parameters: 66%% CFG -- A control flow graph 67%% SpillIndex -- Last index of spill variable 68%% SpillLimit -- Temporaris with numbers higher than this have 69%% infinit spill cost. 70%% Consider changing this to a set. 71%% TgtMod -- The module containing the target-specific functions. 72%% TgtCtx -- Context data for TgtMod 73%% 74%% Returns: 75%% Coloring -- A coloring for specified CFG 76%% SpillIndex2 -- A new spill index 77%%----------------------------------------------------------------------- 78-ifdef(COMPARE_ITERATED_OPTIMISTIC). 79regalloc(CFG, Liveness, SpillIndex, SpillLimit, TgtMod, TgtCtx, _Options) -> 80 Target = {TgtMod, TgtCtx}, 81 ?debug_msg("optimistic ~w\n",[TgtMod]), 82 ?debug_msg("CFG: ~p\n",[CFG]), 83 %% Build interference graph 84 ?debug_msg("Build IG\n",[]), 85 IG_O = hipe_ig:build(CFG, Liveness, TgtMod, TgtCtx), 86 IG = hipe_ig:build(CFG, Liveness, TgtMod, TgtCtx), 87 ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), 88 ?debug_msg("IG:\n",[]), 89 ?print_adjacent(IG), 90 ?print_degrees(IG), 91 ?print_spill_costs(IG), 92 93 SavedSpillCosts = hipe_ig:spill_costs(IG), 94 SavedAdjList = hipe_ig:adj_list(IG), 95 96 ?debug_msg("Init\n",[]), 97 No_temporaries = number_of_temporaries(CFG, Target), 98 ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]), 99 Allocatable = allocatable(Target), 100 K = length(Allocatable), 101 All_colors = colset_from_list(Allocatable), 102 ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), 103 104 %% Add registers with their own coloring 105 ?debug_msg("Moves\n",[]), 106 Move_sets_O = hipe_moves:new(IG_O), 107 Move_sets = hipe_moves:new(IG), 108 ?debug_msg("Move_sets:\n ~p\n",[Move_sets]), 109 ?mov_print_memberships(Move_sets), 110 111 ?debug_msg("Build Worklist\n",[]), 112 Worklists_O = hipe_reg_worklists:new(IG_O, TgtMod, TgtCtx, CFG, Move_sets_O, 113 K, No_temporaries), 114 ?debug_msg("Worklists:\n ~p\n", [Worklists_O]), 115 ?reg_print_memberships(Worklists_O), 116 117 Worklists = hipe_reg_worklists:new(IG, TgtMod, TgtCtx, CFG, K, 118 No_temporaries), 119 ?debug_msg("New Worklists:\n ~p\n", [Worklists]), 120 ?reg_print_memberships(Worklists), 121 122 Alias_O = initAlias(No_temporaries), 123 Alias = initAlias(No_temporaries), 124 ?print_alias(Alias), 125 126 ?debug_msg("Do coloring\n~p~n",[Worklists_O]), 127 {IG0_O, Worklists0_O, Moves0_O, Alias0_O} = 128 do_coloring(IG_O, Worklists_O, Move_sets_O, Alias_O, 129 K, SpillLimit, Target), 130 ?debug_msg("IG_O after color:\n ~p\n",[IG0_O]), 131 ?print_adjacent(IG0_O), 132 ?print_degrees(IG0_O), 133 ?print_spill_costs(IG0_O), 134 ?debug_msg("Move_sets after color:\n ~p\n",[Moves0_O]), 135 ?mov_print_memberships(Moves0_O), 136 ?debug_msg("Worklists after color:\n ~p\n", [Worklists0_O]), 137 ?reg_print_memberships(Worklists0_O), 138 139 {IG0, Moves0, Alias0, Worklists0} = 140 do_coalescing(IG, Worklists, Move_sets, Alias, K, Target), 141 ?debug_msg("IG after coalescing:\n",[]), 142 ?print_adjacent(IG0), 143 ?print_degrees(IG0), 144 ?print_spill_costs(IG0), 145 ?debug_msg("Move_sets after coalescing:\n ~p\n",[Moves0]), 146 ?mov_print_memberships(Moves0), 147 ?debug_msg("New Worklists after coalescing:\n ~p\n", 148 [Worklists0]), 149 ?reg_print_memberships(Worklists0), 150 151 {IG1, Worklists1, Moves1, Alias1} = 152 do_simplify_or_spill(IG0, Worklists0, Moves0, Alias0, 153 K, SpillLimit, Target), 154 ?debug_msg("IG after simplify_or_spill:\n",[]), 155 ?print_adjacent(IG1), 156 ?print_degrees(IG1), 157 ?print_spill_costs(IG1), 158 ?debug_msg("Saved spill costs ~p~n", [SavedSpillCosts]), 159 ?debug_msg("Move_sets after simplify_or_spill:\n ~p\n",[Moves1]), 160 ?mov_print_memberships(Moves1), 161 ?debug_msg("New Worklists after simplify_or_spill:\n ~p\n", 162 [Worklists1]), 163 ?reg_print_memberships(Worklists1), 164 ?print_alias(Alias1), 165 166 %% only for testing undoCoalescing and member_coalesced_to 167 %test_undoCoalescing(No_temporaries, Alias1, Worklists1), 168 169 %% only for testing fixAdj 170 %?debug_msg("adj_lists_before_fixAdj ~n~p~n", [hipe_ig:adj_list(IG1)]), 171 %IG2 = test_fixAdj(No_temporaries, SavedAdjList, IG1, Target), 172 %?debug_msg("adj_lists__after_fixAdj ~n~p~n", [hipe_ig:adj_list(IG2)]), 173 174 ?debug_msg("Init node sets\n",[]), 175 Node_sets = hipe_node_sets:new(), 176 %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,non_alloc(CFG,Target)]), 177 ?debug_msg("Default coloring\n",[]), 178 {Color0,Node_sets1} = 179 defaultColoring(all_precoloured(Target), 180 initColor(No_temporaries), Node_sets, Target), 181 ?debug_msg("Color0\n",[]), 182 ?print_colors(No_temporaries, Color0), 183 184 ?debug_msg("----------------------Assign colors _N\n",[]), 185 186 Stack = hipe_reg_worklists:stack(Worklists1), 187 ?debug_msg("The stack _N ~p~n", [Stack]), 188 %SortedStack = sort_stack(Stack), 189 %?debug_msg("The stack _N ~p~n", [SortedStack]), 190 191 %?debug_msg("Nodes _N ~w~n", [Node_sets1]), 192 193 {Color1,Node_sets2,Alias2} = 194 assignColors(Worklists1, Stack, Node_sets1, Color0, 195 No_temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, All_colors, Target), 196 ?print_colors(No_temporaries, Color1), 197 ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), 198 199 ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), 200 {Coloring,SpillIndex2} = 201 build_namelist(Node_sets2,SpillIndex,Alias2,Color1), 202 ?debug_msg("Coloring ~p\n",[Coloring]), 203 SortedColoring = {sort_stack(Coloring), SpillIndex2}, 204 ?debug_msg("SortedColoring ~p\n",[SortedColoring]), 205 %%Coloring. 206 ?debug_msg("----------------------Assign colors _O\n",[]), 207 {Color1_O,Node_sets2_O} = 208 assignColors_O(hipe_reg_worklists:stack(Worklists0_O), Node_sets1, Color0, 209 Alias0_O, All_colors, Target), 210 ?print_colors(No_temporaries, Color1_O), 211 ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2_O,No_temporaries]), 212 213 ?debug_msg("Build mapping ~w\n",[Node_sets2_O]), 214 Coloring_O = build_namelist_O(Node_sets2_O,SpillIndex,Alias0_O,Color1_O), 215 ?debug_msg("Coloring_O ~p\n",[Coloring_O]), 216 SortedColoring_O = {sort_stack(element(1, Coloring_O)), element(2, Coloring_O)}, 217 ?debug_msg("SortedColoring_O ~p\n",[SortedColoring_O]), 218 sanity_compare(SortedColoring_O, SortedColoring), 219 {Coloring,SpillIndex2}. 220-else. 221regalloc(CFG, Liveness, SpillIndex, SpillLimit, TgtMod, TgtCtx, _Options) -> 222 Target = {TgtMod, TgtCtx}, 223 ?debug_msg("optimistic ~w\n",[TgtMod]), 224 ?debug_msg("CFG: ~p\n",[CFG]), 225 %% Build interference graph 226 ?debug_msg("Build IG\n",[]), 227 IG = hipe_ig:build(CFG, Liveness, TgtMod, TgtCtx), 228 ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), 229 ?debug_msg("IG:\n",[]), 230 ?print_adjacent(IG), 231 ?print_degrees(IG), 232 ?print_spill_costs(IG), 233 234 SavedSpillCosts = hipe_ig:spill_costs(IG), 235 SavedAdjList = hipe_ig:adj_list(IG), 236 237 ?debug_msg("Init\n",[]), 238 No_temporaries = number_of_temporaries(CFG, Target), 239 ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]), 240 Allocatable = allocatable(Target), 241 K = length(Allocatable), 242 All_colors = colset_from_list(Allocatable), 243 ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), 244 245 %% Add registers with their own coloring 246 ?debug_msg("Moves\n",[]), 247 Move_sets = hipe_moves:new(IG), 248 ?debug_msg("Move_sets:\n ~p\n",[Move_sets]), 249 ?mov_print_memberships(Move_sets), 250 251 ?debug_msg("Build Worklist\n",[]), 252 253 Worklists = hipe_reg_worklists:new(IG, TgtMod, TgtCtx, CFG, K, 254 No_temporaries), 255 ?debug_msg("New Worklists:\n ~p\n", [Worklists]), 256 ?reg_print_memberships(Worklists), 257 258 Alias = initAlias(No_temporaries), 259 ?print_alias(Alias), 260 261 {IG0, Moves0, Alias0, Worklists0} = 262 do_coalescing(IG, Worklists, Move_sets, Alias, K, Target), 263 ?debug_msg("IG after coalescing:\n",[]), 264 ?print_adjacent(IG0), 265 ?print_degrees(IG0), 266 ?print_spill_costs(IG0), 267 ?debug_msg("Move_sets after coalescing:\n ~p\n",[Moves0]), 268 ?mov_print_memberships(Moves0), 269 ?debug_msg("New Worklists after coalescing:\n ~p\n", 270 [Worklists0]), 271 ?reg_print_memberships(Worklists0), 272 273 {IG1, Worklists1, _Moves1, Alias1} = 274 do_simplify_or_spill(IG0, Worklists0, Moves0, Alias0, 275 K, SpillLimit, Target), 276 ?debug_msg("IG after simplify_or_spill:\n",[]), 277 ?print_adjacent(IG1), 278 ?print_degrees(IG1), 279 ?print_spill_costs(IG1), 280 ?debug_msg("Saved spill costs ~p~n", [SavedSpillCosts]), 281 ?debug_msg("New Worklists after simplify_or_spill:\n ~p\n", 282 [Worklists1]), 283 ?reg_print_memberships(Worklists1), 284 ?print_alias(Alias1), 285 286 %% only for testing undoCoalescing and member_coalesced_to 287 %test_undoCoalescing(No_temporaries, Alias1, Worklists1), 288 289 %% only for testing fixAdj 290 %?debug_msg("adj_lists_before_fixAdj ~n~p~n", [hipe_ig:adj_list(IG1)]), 291 %IG2 = test_fixAdj(No_temporaries, SavedAdjList, IG1, Target), 292 %?debug_msg("adj_lists__after_fixAdj ~n~p~n", [hipe_ig:adj_list(IG2)]), 293 294 ?debug_msg("Init node sets\n",[]), 295 Node_sets = hipe_node_sets:new(), 296 %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,non_alloc(CFG,Target)]), 297 ?debug_msg("Default coloring\n",[]), 298 {Color0,Node_sets1} = 299 defaultColoring(all_precoloured(Target), 300 initColor(No_temporaries), Node_sets, Target), 301 ?debug_msg("Color0\n",[]), 302 ?print_colors(No_temporaries, Color0), 303 304 ?debug_msg("----------------------Assign colors _N\n",[]), 305 306 Stack = hipe_reg_worklists:stack(Worklists1), 307 ?debug_msg("The stack _N ~p~n", [Stack]), 308 %SortedStack = sort_stack(Stack), 309 %?debug_msg("The stack _N ~p~n", [SortedStack]), 310 311 %?debug_msg("Nodes _N ~w~n", [Node_sets1]), 312 313 {Color1,Node_sets2,Alias2} = 314 assignColors(Worklists1, Stack, Node_sets1, Color0, 315 No_temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, All_colors, Target), 316 ?print_colors(No_temporaries, Color1), 317 ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), 318 319 ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), 320 {Coloring, SpillIndex2} = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), 321 ?debug_msg("Coloring ~p\n",[Coloring]), 322 {Coloring,SpillIndex2}. 323-endif. 324 325%%---------------------------------------------------------------------- 326%% Function: do_coloring 327%% 328%% Description: Create a coloring. That is, play paintball. 329%% Parameters: 330%% IG -- An interference graph 331%% Worklists -- Worklists, that is simplify, spill and freeze 332%% Moves -- Moves sets, that is coalesced, constrained 333%% and so on. 334%% Alias -- Tells if two temporaries can have their value 335%% in the same register. 336%% K -- Want to create a K coloring. 337%% SpillLimit -- Try not to spill nodes that are above the spill limit. 338%% 339%% Returns: 340%% IG -- Updated interference graph 341%% Worklists -- Updated Worklists structure 342%% Moves -- Updated Moves structure 343%% Alias -- Updates Alias structure 344%% 345%%---------------------------------------------------------------------- 346 347-ifdef(COMPARE_ITERATED_OPTIMISTIC). 348do_coloring(IG, Worklists, Moves, Alias, K, SpillLimit, Target) -> 349 Simplify = not(hipe_reg_worklists:is_empty_simplify(Worklists)), 350 Coalesce = not(hipe_moves:is_empty_worklist(Moves)), 351 Freeze = not(hipe_reg_worklists:is_empty_freeze(Worklists)), 352 Spill = not(hipe_reg_worklists:is_empty_spill(Worklists)), 353 if Simplify =:= true -> 354 {IG0, Worklists0, Moves0} = 355 simplify_O(hipe_reg_worklists:simplify(Worklists), 356 IG, 357 Worklists, 358 Moves, 359 K), 360 do_coloring(IG0, Worklists0, Moves0, Alias, K, SpillLimit, Target); 361 Coalesce =:= true -> 362 {Moves0, IG0, Worklists0, Alias0} = 363 coalesce_O(Moves, IG, Worklists, Alias, K, Target), 364 do_coloring(IG0, Worklists0, Moves0, Alias0, K, SpillLimit, Target); 365 Freeze =:= true -> 366 {Worklists0, Moves0} = 367 freeze(K, Worklists, Moves, IG, Alias), 368 do_coloring(IG, Worklists0, Moves0, Alias, K, SpillLimit, Target); 369 Spill =:= true -> 370 {Worklists0, Moves0} = 371 selectSpill_O(Worklists, Moves, IG, K, Alias, SpillLimit), 372 do_coloring(IG, Worklists0, Moves0, Alias, K, SpillLimit, Target); 373 true -> % Catchall case 374 {IG, Worklists, Moves, Alias} 375 end. 376-endif. 377 378%%---------------------------------------------------------------------- 379%% Function: do_coalescing 380%% 381%% Description: Try to coalesce everything (find out later if it was 382%% possible). 383%% Parameters: 384%% IG -- An interference graph 385%% Moves -- Moves sets, that is coalesced, constrained 386%% and so on. 387%% Alias -- Tells if two temporaries can have their value 388%% in the same register. 389%% 390%% Returns: 391%% IG -- Updated interference graph 392%% Moves -- Updated Moves structure 393%% Alias -- Updates Alias structure 394%% 395%%---------------------------------------------------------------------- 396 397do_coalescing(IG, Worklists, Moves, Alias, K, Target) -> 398 case hipe_moves:is_empty_worklist(Moves) of 399 true -> 400 {IG, Moves, Alias, Worklists}; 401 _ -> 402 {Moves0, IG0, Alias0, Worklists0} = 403 coalesce(Moves, IG, Worklists, Alias, K, Target), 404 do_coalescing(IG0, Worklists0, Moves0, Alias0, K, Target) 405 end. 406 407%%---------------------------------------------------------------------- 408%% Function: do_simplify_or_spill 409%% 410%% Parameters: 411%% IG -- An interference graph 412%% Worklists -- Worklists, that is simplify, spill and freeze 413%% Moves -- Moves sets, that is coalesced, constrained 414%% and so on. 415%% Alias -- Tells if two temporaries can have their value 416%% in the same register. 417%% K -- Want to create a K coloring. 418%% SpillLimit -- Try not to spill nodes that are above the spill limit. 419%% 420%% Returns: 421%% IG -- Updated interference graph 422%% Worklists -- Updated Worklists structure 423%% Moves -- Updated Moves structure 424%% Alias -- Updates Alias structure 425%% 426%%---------------------------------------------------------------------- 427 428do_simplify_or_spill(IG, Worklists, Moves, Alias, K, SpillLimit, Target) -> 429 Simplify = not(hipe_reg_worklists:is_empty_simplify(Worklists)), 430 Spill = not(hipe_reg_worklists:is_empty_spill(Worklists)), 431 if Simplify =:= true -> 432 {IG0, Worklists0, Moves0} = 433 simplify(hipe_reg_worklists:simplify(Worklists), 434 IG, 435 Worklists, 436 Moves, 437 K), 438 do_simplify_or_spill(IG0, Worklists0, Moves0, Alias, 439 K, SpillLimit, Target); 440 Spill =:= true -> 441 Worklists0 = 442 selectSpill(Worklists, IG, SpillLimit), 443 do_simplify_or_spill(IG, Worklists0, Moves, Alias, 444 K, SpillLimit, Target); 445 true -> % Catchall case 446 {IG, Worklists, Moves, Alias} 447 end. 448 449%%---------------------------------------------------------------------- 450%% Function: adjacent 451%% 452%% Description: Adjacent nodes that's not coalesced, on the stack or 453%% precoloured. 454%% Parameters: 455%% Node -- Node that you want to adjacents of 456%% IG -- The interference graph 457%% 458%% Returns: 459%% A set with nodes/temporaries that are not coalesced, on the 460%% stack or precoloured. 461%%---------------------------------------------------------------------- 462 463adjacent(Node, IG, Worklists) -> 464 Adjacent_edges = hipe_ig:node_adj_list(Node, IG), 465 hipe_reg_worklists:non_stacked_or_coalesced_nodes(Adjacent_edges, Worklists). 466 467%%---------------------------------------------------------------------- 468%% Function: simplify 469%% 470%% Description: Simplify graph by removing nodes of low degree. This 471%% function simplify all nodes it can at once. 472%% Parameters: 473%% [Node|Nodes] -- The simplify worklist 474%% IG -- The interference graph 475%% Worklists -- The worklists data-structure 476%% Moves -- The moves data-structure 477%% K -- Produce a K coloring 478%% 479%% Returns: 480%% IG -- An updated interference graph 481%% Worklists -- An updated worklists data-structure 482%% Moves -- An updated moves data-structure 483%%---------------------------------------------------------------------- 484 485-ifdef(COMPARE_ITERATED_OPTIMISTIC). 486simplify_O([], IG, Worklists, Moves, _K) -> 487 {IG, Worklists, Moves}; 488simplify_O([Node|Nodes], IG, Worklists, Moves, K) -> 489 Worklists0 = hipe_reg_worklists:remove_simplify(Node, Worklists), 490 ?debug_msg("putting ~w on stack~n",[Node]), 491 Adjacent = adjacent(Node, IG, Worklists0), 492 Worklists01 = hipe_reg_worklists:push_stack(Node, Adjacent, Worklists0), 493 {New_ig, Worklists1, New_moves} = 494 decrement_degree_O(Adjacent, IG, Worklists01, Moves, K), 495 simplify_O(Nodes, New_ig, Worklists1, New_moves, K). 496-endif. 497 498%%---------------------------------------------------------------------- 499%% Function: simplify 500%% 501%% Description: Simplify graph by removing nodes of low degree. This 502%% function simplify all nodes it can at once. 503%% Parameters: 504%% [Node|Nodes] -- The simplify worklist 505%% IG -- The interference graph 506%% Worklists -- The worklists data-structure 507%% Moves -- The moves data-structure 508%% K -- Produce a K coloring 509%% 510%% Returns: 511%% IG -- An updated interference graph 512%% Worklists -- An updated worklists data-structure 513%% Moves -- An updated moves data-structure 514%%---------------------------------------------------------------------- 515 516simplify([], IG, Worklists, Moves, _K) -> 517 {IG, Worklists, Moves}; 518simplify([Node|Nodes], IG, Worklists, Moves, K) -> 519 Worklists0 = hipe_reg_worklists:remove_simplify(Node, Worklists), 520 ?debug_msg("putting ~w on stack~n",[Node]), 521 Adjacent = adjacent(Node, IG, Worklists0), 522 Worklists01 = hipe_reg_worklists:push_stack(Node, Adjacent, Worklists0), 523 {New_ig, Worklists1} = decrement_degree(Adjacent, IG, Worklists01, K), 524 simplify(Nodes, New_ig, Worklists1, Moves, K). 525 526%%---------------------------------------------------------------------- 527%% Function: decrement_degree 528%% 529%% Description: Decrement the degree on a number of nodes/temporaries. 530%% Parameters: 531%% [Node|Nodes] -- Decrement degree on these nodes 532%% IG -- The interference graph 533%% Worklists -- The Worklists data structure 534%% Moves -- The Moves data structure. 535%% K -- We want to create a coloring with K colors 536%% 537%% Returns: 538%% IG -- An updated interference graph (the degrees) 539%% Worklists -- Updated Worklists. Changed if one degree goes 540%% down to K. 541%% Moves -- Updated Moves. Changed if a move related temporary 542%% gets degree K. 543%%---------------------------------------------------------------------- 544 545-ifdef(COMPARE_ITERATED_OPTIMISTIC). 546decrement_degree_O([], IG, Worklists, Moves, _K) -> 547 {IG, Worklists, Moves}; 548decrement_degree_O([Node|Nodes], IG, Worklists, Moves, K) -> 549 PrevDegree = hipe_ig:get_node_degree(Node, IG), 550 IG0 = hipe_ig:dec_node_degree(Node, IG), 551 case PrevDegree =:= K of 552 true -> 553 AdjList = hipe_ig:node_adj_list(Node, IG0), 554 %% OK since Node (a) is still in IG, and (b) cannot be adjacent to itself. 555 Moves00 = enable_moves_active_to_worklist(hipe_moves:node_movelist(Node, Moves), 556 Moves), 557 Moves0 = enable_moves(AdjList, Worklists, Moves00), 558 Worklists0 = hipe_reg_worklists:remove_spill(Node, Worklists), 559 case hipe_moves:move_related(Node, Moves0) of 560 true -> 561 Worklists1 = hipe_reg_worklists:add_freeze(Node, Worklists0), 562 decrement_degree_O(Nodes, IG0, Worklists1, Moves0, K); 563 _ -> 564 Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0), 565 decrement_degree_O(Nodes, IG0, Worklists1, Moves0, K) 566 end; 567 _ -> 568 decrement_degree_O(Nodes, IG0, Worklists, Moves, K) 569 end. 570-endif. 571 572%%---------------------------------------------------------------------- 573%% Function: decrement_degree 574%% 575%% Description: Decrement the degree on a number of nodes/temporaries. 576%% Parameters: 577%% [Node|Nodes] -- Decrement degree on these nodes 578%% IG -- The interference graph 579%% Worklists -- The Worklists data structure 580%% Moves -- The Moves data structure. 581%% K -- We want to create a coloring with K colors 582%% 583%% Returns: 584%% IG -- An updated interference graph (the degrees) 585%% Worklists -- Updated Worklists. Changed if one degree goes 586%% down to K. 587%% Moves -- Updated Moves. Changed if a move related temporary 588%% gets degree K. 589%%---------------------------------------------------------------------- 590 591decrement_degree([], IG, Worklists, _K) -> 592 {IG, Worklists}; 593decrement_degree([Node|Nodes], IG, Worklists, K) -> 594 PrevDegree = hipe_ig:get_node_degree(Node, IG), 595 IG0 = hipe_ig:dec_node_degree(Node, IG), 596 case PrevDegree =:= K of 597 true -> 598 Worklists0 = hipe_reg_worklists:remove_spill(Node, Worklists), 599 Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0), 600 decrement_degree(Nodes, IG0, Worklists1, K); 601 _ -> 602 decrement_degree(Nodes, IG0, Worklists, K) 603 end. 604 605%%---------------------------------------------------------------------- 606%% Function: enable_moves 607%% 608%% Description: Make (move-related) nodes that are not yet considered for 609%% coalescing, ready for possible coalescing. 610%% 611%% Parameters: 612%% [Node|Nodes] -- A list of move nodes 613%% Moves -- The moves data-structure 614%% 615%% Returns: 616%% An updated moves data-structure 617%%---------------------------------------------------------------------- 618 619-ifdef(COMPARE_ITERATED_OPTIMISTIC). 620enable_moves([], _Worklists, Moves) -> Moves; 621enable_moves([Node|Nodes], Worklists, Moves) -> 622 case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of 623 true -> enable_moves(Nodes, Worklists, Moves); 624 _ -> 625 %% moveList[n] suffices since we're checking for activeMoves membership 626 Node_moves = hipe_moves:node_movelist(Node, Moves), 627 New_moves = enable_moves_active_to_worklist(Node_moves, Moves), 628 enable_moves(Nodes, Worklists, New_moves) 629 end. 630-endif. 631 632%%---------------------------------------------------------------------- 633%% Function: enable_moves_active_to_worklist 634%% 635%% Description: Make (move-related) nodes that are not yeat considered for 636%% coalescing, ready for possible coalescing. 637%% 638%% Parameters: 639%% [Node|Nodes] -- A list of move nodes 640%% Moves -- The moves data-structure 641%% 642%% Returns: 643%% An updated moves data-structure 644%%---------------------------------------------------------------------- 645 646-ifdef(COMPARE_ITERATED_OPTIMISTIC). 647enable_moves_active_to_worklist([], Moves) -> Moves; 648enable_moves_active_to_worklist([Node|Nodes], Moves) -> 649 case hipe_moves:member_active(Node, Moves) of 650 true -> 651 New_moves = 652 hipe_moves:add_worklist(Node, hipe_moves:remove_active(Node, Moves)), 653 enable_moves_active_to_worklist(Nodes, New_moves); 654 _ -> 655 enable_moves_active_to_worklist(Nodes, Moves) 656 end. 657-endif. 658 659-ifdef(COMPARE_ITERATED_OPTIMISTIC). 660sanity_compare(Coloring, Coloring_N) -> 661 case compare_sanity(Coloring, Coloring_N) of 662 false -> 663 ?debug_msg("mismatch for coloring: ~n~p~n~p", [Coloring, Coloring_N]); 664 _ -> true 665 end. 666compare_sanity({[], _C}, {[], _C_N}) -> 667 ?debug_msg("Sanity - OK!~n", []), 668 true; 669compare_sanity({_Coloring_list, _C}, {[], _C_N}) -> 670 ?debug_msg("Sanity - unequal numbers~n", []), 671 false; 672compare_sanity({[], _C}, {_Coloring_list_N, _C_N}) -> 673 ?debug_msg("Sanity - unequal numbers~n", []), 674 false; 675compare_sanity({[Color|Coloring_list], C}, {[Color_N|Coloring_list_N], C_N}) -> 676 case element(1, Color) =:= element(1, Color_N) of 677 false -> 678 ?debug_msg("Sanity - unequal measure~n", []), 679 false; 680 _ -> 681 case element(2, Color) =:= element(2, Color_N) of 682 false -> 683 ?debug_msg("Sanity - unequal color~n", []), 684 false; 685 _ -> 686 case C =:= C_N of 687 false -> 688 ?debug_msg("Sanity - unequal last element~n", []), 689 false; 690 _ -> 691 compare_sanity({Coloring_list, C}, {Coloring_list_N, C_N}) 692 end 693 end 694 end. 695-endif. 696 697 698%% Build the namelists, these functions are fast hacks, they use knowledge 699%% about data representation that they shouldn't know, bad abstraction. 700 701-ifdef(COMPARE_ITERATED_OPTIMISTIC). 702build_namelist_O(NodeSets,Index,Alias,Color) -> 703 ?debug_msg("NodeSets ~w~n", [NodeSets]), 704 ?debug_msg("Building mapping\n",[]), 705 ?debug_msg("Vector to list\n",[]), 706 AliasList = 707 build_alias_list(aliasToList(Alias), 708 0, %% The first temporary has index 0 709 []), %% Accumulator 710 ?debug_msg("Alias list:~p\n",[AliasList]), 711 ?debug_msg("Coalesced\n",[]), 712 NL1 = build_coalescedlist(AliasList,Color,Alias,[]), 713 ?debug_msg("Coalesced list:~p\n",[NL1]), 714 ?debug_msg("Regs\n",[]), 715 NL2 = build_reglist_O(hipe_node_sets:colored(NodeSets),Color,NL1), 716 ?debug_msg("Regs list:~p\n",[NL2]), 717 ?debug_msg("Spills\n",[]), 718 build_spillist(hipe_node_sets:spilled(NodeSets),Index,NL2). 719-endif. 720 721build_namelist(NodeSets,Index,Alias,Color) -> 722 ?debug_msg("NodeSets _N ~w~n", [NodeSets]), 723 ?debug_msg("Building mapping _N\n",[]), 724 ?debug_msg("Vector to list _N\n",[]), 725 AliasList = 726 build_alias_list(aliasToList(Alias), 727 0, %% The first temporary has index 0 728 []), %% Accumulator 729 ?debug_msg("Alias list _N:~p\n",[AliasList]), 730 ?debug_msg("Coalesced\n",[]), 731 NL1 = build_coalescedlist(AliasList,Color,Alias,[]), 732 ?debug_msg("Coalesced list:~p\n",[NL1]), 733 ?debug_msg("Regs _N\n",[]), 734 ColoredNodes = hipe_node_sets:colored(NodeSets), 735 ?debug_msg("ColoredNodes ~p~n", [ColoredNodes]), 736 NL2 = build_reglist_N(ColoredNodes,Color,NL1,NL1), 737 ?debug_msg("Regs list _N:~p\n",[NL2]), 738 ?debug_msg("Spills _N\n",[]), 739 build_spillist(hipe_node_sets:spilled(NodeSets),Index,NL2). 740 741build_spillist([],Index,List) -> 742 {List,Index}; 743build_spillist([Node|Nodes],Index,List) -> 744 ?debug_msg("[~p]: Spill ~p to ~p\n", [?MODULE,Node,Index]), 745 build_spillist(Nodes,Index+1,[{Node,{spill,Index}}|List]). 746 747build_coalescedlist([],_Color,_Alias,List) -> 748 List; 749build_coalescedlist([Node|Ns],Color,Alias,List) when is_integer(Node) -> 750 ?debug_msg("Alias of ~p is ~p~n",[Node,getAlias(Node,Alias)]), 751 AC = getColor(getAlias(Node,Alias),Color), 752 build_coalescedlist(Ns,Color,Alias,[{Node,{reg,AC}}|List]). 753 754-ifdef(COMPARE_ITERATED_OPTIMISTIC). 755build_reglist_O([],_Color,List) -> 756 List; 757build_reglist_O([Node|Ns],Color,List) -> 758 build_reglist_O(Ns,Color,[{Node,{reg,getColor(Node,Color)}}|List]). 759-endif. 760 761build_reglist_N([],_Color,List,_OrgList) -> 762 List; 763build_reglist_N([Node|Ns],Color,List,OrgList) -> 764 %% XXX this could be done more efficiently if both lists were sorted 765 case is_already_in_list(Node, OrgList) of 766 true -> build_reglist_N(Ns, Color, List, OrgList); 767 _ -> build_reglist_N(Ns,Color,[{Node,{reg,getColor(Node,Color)}}|List], OrgList) 768 end. 769 770is_already_in_list(_Node, []) -> 771 false; 772is_already_in_list(Node, [L|List]) -> 773 ?debug_msg("---test--- Node ~w element ~w~n", [Node, element(1, L)]), 774 case Node =:= element(1, L) of 775 true -> true; 776 _ -> is_already_in_list(Node, List) 777 end. 778 779build_alias_list([], _I, List) -> 780 List; 781build_alias_list([Alias|Aliases], I, List) when is_integer(Alias) -> 782 build_alias_list(Aliases, I+1, [I|List]); 783build_alias_list([_Alias|Aliases], I, List) -> 784 build_alias_list(Aliases, I+1, List). 785 786-ifdef(COMPARE_ITERATED_OPTIMISTIC). 787sort_stack([]) -> []; 788sort_stack([Pivot|Rest]) -> 789 {Smaller, Bigger} = sort_stack_split(Pivot, Rest), 790 lists:append(sort_stack(Smaller), [Pivot|sort_stack(Bigger)]). 791 792sort_stack_split(Pivot, L) -> 793 sort_stack_split(Pivot, L, [], []). 794 795sort_stack_split(_Pivot, [], Smaller, Bigger) -> 796 {Smaller, Bigger}; 797sort_stack_split(Pivot, [H|T], Smaller, Bigger) when element(1, H) > element(1, Pivot) -> 798 sort_stack_split(Pivot, T, [H|Smaller], Bigger); 799sort_stack_split(Pivot, [H|T], Smaller, Bigger) -> 800 sort_stack_split(Pivot, T, Smaller, [H|Bigger]). 801-endif. 802 803%sort([]) -> []; 804%sort([Pivot|Rest]) -> 805% {Smaller, Bigger} = sort_split(Pivot, Rest), 806% lists:append(sort(Smaller), [Pivot|sort(Bigger)]). 807% 808%sort_split(Pivot, L) -> 809% sort_split(Pivot, L, [], []). 810% 811%sort_split(_Pivot, [], Smaller, Bigger) -> {Smaller, Bigger}; 812%sort_split(Pivot, [H|T], Smaller, Bigger) when H > Pivot -> 813% sort_split(Pivot, T, [H|Smaller], Bigger); 814%sort_split(Pivot, [H|T], Smaller, Bigger) -> 815% sort_split(Pivot, T, Smaller, [H|Bigger]). 816 817%%---------------------------------------------------------------------- 818%% Function: assignColors 819%% 820%% Description: Tries to assign colors to nodes in a stack. 821%% Parameters: 822%% Worklists -- The Worklists data structure. 823%% Stack -- The SelectStack built by the Select function, 824%% this stack contains tuples in the form {Node,Edges} 825%% where Node is the Node number and Edges is an ordset 826%% containing the numbers of all the adjacent nodes. 827%% NodeSets -- This is a record containing all the different node 828%% sets that are used in the register allocator. 829%% Color -- A mapping from nodes to their respective color. 830%% No_temporaries -- Number of temporaries. 831%% SavedAdjList -- Saved adjacency list (from before coalescing). 832%% SavedSpillCosts -- Saved spill costs (from before coalescing). 833%% IG -- The interference graph. 834%% Alias -- This is a mapping from nodes to nodes. If a node has 835%% been coalesced, this mapping shows the alias for that 836%% node. 837%% AllColors -- This is an ordset containing all the available colors 838%% Target -- The module containing the target-specific functions, 839%% along with its context data. 840%% 841%% Returns: 842%% Color -- A mapping from nodes to their respective color. 843%% NodeSets -- The updated node sets. 844%% Alias -- The updated aliases. 845%%---------------------------------------------------------------------- 846 847assignColors(Worklists, Stack, NodeSets, Color, No_Temporaries, 848 SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) -> 849 case Stack of 850 [] -> 851 {Color,NodeSets,Alias}; 852 [{Node,Edges}|Stack1] -> 853 ?debug_msg("Coloring Node: ~p~n",[Node]), 854 ?IF_DEBUG(lists:foreach(fun (_E) -> 855 ?msg(" Edge ~w-><~w>->~w~n", 856 begin A = getAlias(_E,Alias), 857 [_E,A,getColor(A,Color)] 858 end) 859 end, Edges), 860 []), 861 %% When debugging, check that Node isn't precoloured. 862 OkColors = findOkColors(Edges, AllColors, Color, Alias), 863 case colset_is_empty(OkColors) of 864 true -> % Spill case 865 case hipe_reg_worklists:member_coalesced_to(Node, Worklists) of 866 true -> 867 ?debug_msg("Alias case. Undoing coalescing.~n", []), 868 {Alias1, IG1, NodeSets1, Color1, Stack2} = tryPrimitiveNodes(Node, Stack1, NodeSets, AllColors, Color, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, Target), 869 %{Alias1, IG1, NodeSets1, Color1, Stack2} = {Alias, IG, NodeSets, Color, Stack1}, 870 assignColors(Worklists, Stack2, NodeSets1, Color1, No_Temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, AllColors, Target); 871 false -> 872 ?debug_msg("Spill case. Spilling node.~n", []), 873 NodeSets1 = hipe_node_sets:add_spilled(Node, NodeSets), 874 assignColors(Worklists, Stack1, NodeSets1, Color, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) 875 end; 876 false -> % Color case 877 Col = colset_smallest(OkColors), 878 NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), 879 Color1 = setColor(Node, physical_name(Col,Target), Color), 880 ?debug_msg("Color case. Assigning color ~p to node.~n", [Col]), 881 assignColors(Worklists, Stack1, NodeSets1, Color1, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) 882 end 883 end. 884 885%%---------------------------------------------------------------------- 886%% Function: tryPrimitiveNodes 887%% 888%% Description: Undoes coalescing of a non-colorable coalesced node and tries 889%% to assign colors to its primitives, such that the cheapest 890%% potential spill cost is achieved. 891%% Parameters: 892%% Node -- The representative node to undo coalescing for. 893%% Stack -- The SelectStack built by the Select function, 894%% this stack contains tuples in the form {Node,Edges} 895%% where Node is the Node number and Edges is an ordset 896%% containing the numbers of all the adjacent nodes. 897%% NodeSets -- This is a record containing all the different node 898%% sets that are used in the register allocator. 899%% AllColors -- This is an ordset containing all the available colors. 900%% No_temporaries -- Number of temporaries. 901%% SavedAdjList -- Saved adjacency list (from before coalescing). 902%% SavedSpillCosts -- Saved spill costs (from before coalescing). 903%% IG -- The interference graph. 904%% Alias -- This is a mapping from nodes to nodes. If a node has 905%% been coalesced, this mapping shows the alias for that 906%% node. 907%% Target -- The module containing the target-specific functions, 908%% along with its context data. 909%% 910%% Returns: 911%% Alias -- The restored aliases after the uncoalescing. 912%% IG -- An updated interference graph after the uncoalescing. 913%% NodeSets -- The updated node sets. 914%% Color -- A mapping from nodes to their respective color. 915%% Stack -- The updated SelectStack with non-colored primitives 916%% placed at the bottom. 917%%---------------------------------------------------------------------- 918 919tryPrimitiveNodes(Node, Stack, NodeSets, AllColors, Color, No_temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, Target) -> 920 ?debug_msg("Undoing coalescing of node ~p.~n", [Node]), 921 {PrimitiveNodes, Alias1, IG1} = undoCoalescing(Node, No_temporaries, Alias, SavedAdjList, IG, Target), 922 ?debug_msg("Spilling non-colorable primitives.~n", []), 923 {ColorableNodes, NodeSets1} = spillNonColorablePrimitives([], PrimitiveNodes, NodeSets, AllColors, Color, SavedAdjList, Alias1), 924 ?debug_msg("Generating splits of colorable nodes.~n", []), 925 Splits = splits(ColorableNodes, SavedSpillCosts), 926 {NodeSets2, Color1, Stack1} = processSplits(Splits, AllColors, IG1, Color, NodeSets1, Alias1, Target, Stack), 927 {Alias1, IG1, NodeSets2, Color1, Stack1}. 928 929%% Spill all non-colorable primitives and return the remaining set of nodes. 930 931spillNonColorablePrimitives(ColorableNodes, [], NodeSets, _AllColors, _Color, _SavedAdjList, _Alias) -> 932 {ColorableNodes, NodeSets}; 933spillNonColorablePrimitives(ColorableNodes, [Primitive|Primitives], NodeSets, AllColors, Color, SavedAdjList, Alias) -> 934 OkColors = findOkColors(hipe_adj_list:edges(Primitive, SavedAdjList), AllColors, Color, Alias), 935 case colset_is_empty(OkColors) of 936 true -> % Spill case 937 ?debug_msg(" Spilling primitive node ~p.~n", [Primitive]), 938 NodeSets1 = hipe_node_sets:add_spilled(Primitive, NodeSets), 939 spillNonColorablePrimitives(ColorableNodes, Primitives, NodeSets1, AllColors, Color, SavedAdjList, Alias); 940 false -> % Colorable case 941 ?debug_msg(" Primitive node ~p is colorable.~n", [Primitive]), 942 spillNonColorablePrimitives([Primitive|ColorableNodes], Primitives, NodeSets, AllColors, Color, SavedAdjList, Alias) 943 end. 944 945%% Generate all splits of colorable primitives, sorted in spill cost order. 946 947splits([], _SavedSpillCosts) -> 948 [{[], [], 0}]; 949splits([L|Ls], SavedSpillCosts) -> 950 Spl = splits(Ls, SavedSpillCosts), 951 SpillCost = hipe_spillcost:spill_cost(L, SavedSpillCosts), 952 Spl1 = [splits_1(S, L) || S <- Spl], 953 Spl2 = [splits_2(S, L, SpillCost) || S <- Spl], 954 spillCostOrderedMerge(Spl1, Spl2, []). 955 956splits_1({Cols, NonCols, OldSpillCost}, L) -> 957 {[L|Cols], NonCols, OldSpillCost}. 958 959splits_2({Cols, NonCols, OldSpillCost}, L, SpillCost) -> 960 {Cols, [L|NonCols], OldSpillCost + SpillCost}. 961 962%% Merge two ordered sub-splits into one. 963 964spillCostOrderedMerge(Spl1, [], Spl) -> 965 lists:reverse(Spl, Spl1); 966spillCostOrderedMerge([], Spl2, Spl) -> 967 lists:reverse(Spl, Spl2); 968spillCostOrderedMerge(Spl1, Spl2, Spl) -> 969 {_, _, SpillCost1} = hd(Spl1), 970 {_, _, SpillCost2} = hd(Spl2), 971 case SpillCost1 =< SpillCost2 of 972 true -> 973 spillCostOrderedMerge(tl(Spl1), Spl2, [hd(Spl1)|Spl]); 974 false -> 975 spillCostOrderedMerge(Spl1, tl(Spl2), [hd(Spl2)|Spl]) 976 end. 977 978%% Process splits, finding the one with the smallest spill cost that 979%% can be assigned one color. 980 981processSplits([], _AllColors, _IG, Color, NodeSets, _Alias, _Target, Stack) -> 982 {NodeSets, Color, Stack}; 983processSplits([{Cols, NonCols, _SpillCost}|Splits], AllColors, IG, Color, NodeSets, Alias, Target, Stack) -> 984 OkColors = findCommonColors(Cols, IG, Color, Alias, AllColors), 985 case colset_is_empty(OkColors) of 986 false -> % This split can be colored with one color - use it 987 ?debug_msg("Found a colorable split.~n", []), 988 Col = colset_smallest(OkColors), 989 {NodeSets1, Color1} = colorSplit(Cols, Col, NodeSets, Color, Target), 990 Stack1 = enqueueSplit(NonCols, IG, Stack), 991 {NodeSets1, Color1, Stack1}; 992 true -> % This split cannot be colored with one color - try another 993 ?debug_msg("Unable to color split.~n", []), 994 processSplits(Splits, AllColors, IG, Color, NodeSets, Alias, Target, Stack) 995 end. 996 997%% Find the set of colors that can be assigned to one split. 998 999findCommonColors([], _IG, _Color, _Alias, OkColors) -> 1000 OkColors; 1001findCommonColors([Primitive|Primitives], IG, Color, Alias, OkColors) -> 1002 OkColors1 = findOkColors(hipe_ig:node_adj_list(Primitive, IG), OkColors, Color, Alias), 1003 findCommonColors(Primitives, IG, Color, Alias, OkColors1). 1004 1005%% Color nodes in a split. 1006 1007colorSplit([], _Col, NodeSets, Color, _Target) -> 1008 {NodeSets, Color}; 1009colorSplit([Node|Nodes], Col, NodeSets, Color, Target) -> 1010 ?debug_msg(" Coloring node ~p with color ~p.~n", [Node, Col]), 1011 NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), 1012 Color1 = setColor(Node, physical_name(Col,Target), Color), 1013 colorSplit(Nodes, Col, NodeSets1, Color1, Target). 1014 1015%% Place non-colorable nodes in a split at the bottom of the SelectStack. 1016 1017enqueueSplit([], _IG, Stack) -> 1018 Stack; 1019enqueueSplit([Node|Nodes], IG, Stack) -> 1020 ?debug_msg(" Placing node ~p at the bottom of the stack.~n", [Node]), 1021 Edges = hipe_ig:node_adj_list(Node, IG), 1022 Stack1 = Stack ++ [{Node, Edges}], 1023 enqueueSplit(Nodes, IG, Stack1). 1024 1025%%---------------------------------------------------------------------- 1026%% Function: assignColors 1027%% 1028%% Description: Tries to assign colors to nodes in a stack. 1029%% Parameters: 1030%% Stack -- The SelectStack built by the Select function, 1031%% this stack contains tuples in the form {Node,Edges} 1032%% where Node is the Node number and Edges is an ordset 1033%% containing the numbers of all the adjacent nodes. 1034%% NodeSets -- This is a record containing all the different node 1035%% sets that are used in the register allocator. 1036%% Alias -- This is a mapping from nodes to nodes, if a node has 1037%% been coalesced this mapping shows the alias for that 1038%% node. 1039%% AllColors -- This is an ordset containing all the available colors 1040%% 1041%% Target -- The module containing the target-specific functions, 1042%% along with its context data. 1043%% 1044%% Returns: 1045%% Color -- A mapping from nodes to their respective color. 1046%% NodeSets -- The updated node sets. 1047%%---------------------------------------------------------------------- 1048 1049-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1050assignColors_O(Stack,NodeSets,Color,Alias,AllColors,Target) -> 1051 case Stack of 1052 [] -> 1053 {Color,NodeSets}; 1054 [{Node,Edges}|Stack1] -> 1055 ?debug_msg("Coloring Node: ~p~n",[Node]), 1056 ?IF_DEBUG(lists:foreach(fun (_E) -> 1057 ?msg(" Edge ~w-><~w>->~w~n", 1058 begin A = getAlias(_E,Alias), 1059 [_E,A,getColor(A,Color)] 1060 end) 1061 end, Edges), 1062 []), 1063 %% When debugging, check that Node isn't precoloured. 1064 OkColors = findOkColors(Edges, AllColors, Color, Alias), 1065 case colset_is_empty(OkColors) of 1066 true -> % Spill case 1067 NodeSets1 = hipe_node_sets:add_spilled(Node, NodeSets), 1068 assignColors_O(Stack1, NodeSets1, Color, Alias, AllColors, Target); 1069 false -> % Colour case 1070 Col = colset_smallest(OkColors), 1071 NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), 1072 Color1 = setColor(Node, physical_name(Col,Target), Color), 1073 assignColors_O(Stack1, NodeSets1, Color1, Alias, AllColors, Target) 1074 end 1075 end. 1076-endif. 1077 1078%%--------------------------------------------------------------------- 1079%% Function: defaultColoring 1080%% 1081%% Description: Make the default coloring 1082%% Parameters: 1083%% Regs -- The list of registers to be default colored 1084%% Color -- The color mapping that shall be changed 1085%% NodeSets -- The node sets that shall be updated 1086%% Target -- The module containing the target-specific functions, 1087%% along with its context data. 1088%% 1089%% Returns: 1090%% NewColor -- The updated color mapping 1091%% NewNodeSets -- The updated node sets 1092%%--------------------------------------------------------------------- 1093 1094defaultColoring([], Color, NodeSets, _Target) -> 1095 {Color,NodeSets}; 1096defaultColoring([Reg|Regs], Color, NodeSets, Target) -> 1097 Color1 = setColor(Reg,physical_name(Reg,Target), Color), 1098 NodeSets1 = hipe_node_sets:add_colored(Reg, NodeSets), 1099 defaultColoring(Regs, Color1, NodeSets1, Target). 1100 1101%% Find the colors that are OK for a node with certain edges. 1102 1103findOkColors(Edges, AllColors, Color, Alias) -> 1104 find(Edges, AllColors, Color, Alias). 1105 1106%% Find all the colors of the nodes in the list [Node|Nodes] and remove them 1107%% from the set OkColors, when the list is empty, return OkColors. 1108 1109find([], OkColors, _Color, _Alias) -> 1110 OkColors; 1111find([Node0|Nodes], OkColors, Color, Alias) -> 1112 Node = getAlias(Node0, Alias), 1113 case getColor(Node, Color) of 1114 [] -> 1115 find(Nodes, OkColors, Color, Alias); 1116 Col -> 1117 OkColors1 = colset_del_element(Col, OkColors), 1118 find(Nodes, OkColors1, Color, Alias) 1119 end. 1120 1121%%% 1122%%% ColSet -- ADT for the set of available colours while 1123%%% assigning colours. 1124%%% 1125-ifdef(notdef). % old ordsets-based implementation 1126colset_from_list(Allocatable) -> 1127 ordsets:from_list(Allocatable). 1128 1129colset_del_element(Colour, ColSet) -> 1130 ordsets:del_element(Colour, ColSet). 1131 1132colset_is_empty(ColSet) -> 1133 case ColSet of 1134 [] -> true; 1135 [_|_] -> false 1136 end. 1137 1138colset_smallest([Colour|_]) -> 1139 Colour. 1140-endif. 1141 1142-ifdef(notdef). % new gb_sets-based implementation 1143colset_from_list(Allocatable) -> 1144 gb_sets:from_list(Allocatable). 1145 1146colset_del_element(Colour, ColSet) -> 1147 %% Must use gb_sets:delete_any/2 since gb_sets:del_element/2 1148 %% fails if the element isn't present. Bummer. 1149 gb_sets:delete_any(Colour, ColSet). 1150 1151colset_is_empty(ColSet) -> 1152 gb_sets:is_empty(ColSet). 1153 1154colset_smallest(ColSet) -> 1155 gb_sets:smallest(ColSet). 1156-endif. 1157 1158%%-ifdef(notdef). % new bitmask-based implementation 1159colset_from_list(Allocatable) -> 1160 colset_from_list(Allocatable, 0). 1161 1162colset_from_list([], ColSet) -> 1163 ColSet; 1164colset_from_list([Colour|Allocatable], ColSet) -> 1165 colset_from_list(Allocatable, ColSet bor (1 bsl Colour)). 1166 1167colset_del_element(Colour, ColSet) -> 1168 ColSet band bnot(1 bsl Colour). 1169 1170colset_is_empty(0) -> true; 1171colset_is_empty(_) -> false. 1172 1173colset_smallest(ColSet) -> 1174 bitN_log2(ColSet band -ColSet, 0). 1175 1176bitN_log2(BitN, ShiftN) -> 1177 case BitN > 16#ffff of 1178 true -> 1179 bitN_log2(BitN bsr 16, ShiftN + 16); 1180 _ -> 1181 ShiftN + hweight16(BitN - 1) 1182 end. 1183 1184hweight16(W) -> 1185 Res1 = ( W band 16#5555) + (( W bsr 1) band 16#5555), 1186 Res2 = (Res1 band 16#3333) + ((Res1 bsr 2) band 16#3333), 1187 Res3 = (Res2 band 16#0F0F) + ((Res2 bsr 4) band 16#0F0F), 1188 (Res3 band 16#00FF) + ((Res3 bsr 8) band 16#00FF). 1189%%-endif. 1190 1191%%% 1192%%% Colour ADT providing a partial mapping from nodes to colours. 1193%%% 1194 1195initColor(NrNodes) -> 1196 {colmap, hipe_bifs:array(NrNodes, [])}. 1197 1198getColor(Node, {colmap, ColMap}) -> 1199 hipe_bifs:array_sub(ColMap, Node). 1200 1201setColor(Node, Color, {colmap, ColMap} = C) -> 1202 hipe_bifs:array_update(ColMap, Node, Color), 1203 C. 1204 1205-ifdef(DEBUG_PRINTOUTS). 1206printColors(0, _) -> 1207 true; 1208printColors(Node, {colmap, ColMap} = C) -> 1209 NextNode = Node - 1, 1210 ?debug_msg("node ~w color ~w~n", [NextNode, hipe_bifs:array_sub(ColMap, NextNode)]), 1211 printColors(NextNode, C). 1212-endif. 1213 1214%%% 1215%%% Alias ADT providing a partial mapping from nodes to nodes. 1216%%% 1217 1218initAlias(NrNodes) -> 1219 {alias, hipe_bifs:array(NrNodes, [])}. 1220 1221%% Get alias for a node. 1222%% Note that non-aliased nodes could be represented in 1223%% two ways, either not aliased or aliased to itself. 1224%% Including the latter case prevents looping bugs. 1225getAlias(Node, {alias, AliasMap} = Alias) -> 1226 case hipe_bifs:array_sub(AliasMap, Node) of 1227 [] -> 1228 Node; 1229 Node -> 1230 Node; 1231 AliasNode -> 1232 getAlias(AliasNode, Alias) 1233 end. 1234 1235-ifdef(DEBUG_PRINTOUTS). 1236printAlias({alias, AliasMap} = Alias) -> 1237 ?debug_msg("Aliases:\n",[]), 1238 printAlias(hipe_bifs:array_length(AliasMap), Alias). 1239 1240printAlias(0, {alias, _}) -> 1241 true ; 1242printAlias(Node, {alias, _AliasMap} = Alias) -> 1243 ?debug_msg("alias ~p ~p\n", [Node - 1, getAlias(Node - 1, Alias)]), 1244 printAlias(Node - 1, Alias). 1245-endif. 1246 1247setAlias(Node, AliasNode, {alias, AliasMap} = Alias) -> 1248 hipe_bifs:array_update(AliasMap, Node, AliasNode), 1249 Alias. 1250 1251aliasToList({alias, AliasMap}) -> 1252 aliasToList(AliasMap, hipe_bifs:array_length(AliasMap), []). 1253 1254aliasToList(AliasMap, I1, Tail) -> 1255 I0 = I1 - 1, 1256 case I0 >= 0 of 1257 true -> 1258 aliasToList(AliasMap, I0, [hipe_bifs:array_sub(AliasMap, I0)|Tail]); 1259 _ -> 1260 Tail 1261 end. 1262 1263%%---------------------------------------------------------------------- 1264%% Function: coalesce 1265%% 1266%% Description: Coalesces nodes in worklist 1267%% Parameters: 1268%% Moves -- Current move information 1269%% IG -- Interference graph 1270%% Worklists -- Current worklists 1271%% Alias -- Current aliases for temporaries 1272%% K -- Number of registers 1273%% 1274%% Returns: 1275%% {Moves, IG, Worklists, Alias} 1276%% (Updated versions of above structures, after coalescing) 1277%%---------------------------------------------------------------------- 1278 1279coalesce(Moves, IG, Worklists, Alias, K, Target) -> 1280 case hipe_moves:worklist_get_and_remove(Moves) of 1281 {[],Moves0} -> 1282 %% Moves marked for removal from worklistMoves by FreezeMoves() 1283 %% are removed by worklist_get_and_remove(). This case is unlikely, 1284 %% but can occur if only stale moves remain in worklistMoves. 1285 {Moves0, IG, Alias}; 1286 {Move,Moves0} -> 1287 {Dest,Source} = hipe_moves:get_move(Move, Moves0), 1288 ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), 1289 Alias_src = getAlias(Source, Alias), 1290 Alias_dst = getAlias(Dest, Alias), 1291 {U,V} = case is_precoloured(Alias_dst, Target) of 1292 true -> {Alias_dst, Alias_src}; 1293 false -> {Alias_src, Alias_dst} 1294 end, 1295 %% When debugging, check that neither V nor U is on the stack. 1296 case U =:= V of 1297 true -> 1298 %% drop coalesced move Move 1299 {Moves0, IG, Alias, Worklists}; 1300 _ -> 1301 case (is_precoloured(V, Target) orelse 1302 hipe_ig:nodes_are_adjacent(U, V, IG)) of 1303 true -> 1304 %% drop constrained move Move 1305 {Moves0, IG, Alias, Worklists}; 1306 false -> 1307 case (case is_precoloured(U, Target) of 1308 true -> 1309 AdjV = hipe_ig:node_adj_list(V, IG), 1310 all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); 1311 false -> 1312 AdjV = hipe_ig:node_adj_list(V, IG), 1313 AdjU = hipe_ig:node_adj_list(U, IG), 1314 conservative(AdjU, AdjV, U, Worklists, IG, K) 1315 end) of 1316 true -> 1317 %% drop coalesced move Move 1318 {IG1, Alias1, Worklists1} = 1319 combine(U, V, IG, Alias, Worklists, K, Target), 1320 {Moves0, IG1, Alias1, Worklists1}; 1321 false -> 1322 Moves1 = hipe_moves:add_active(Move, Moves0), 1323 {Moves1, IG, Alias, Worklists} 1324 end 1325 end 1326 end 1327 end. 1328 1329%%---------------------------------------------------------------------- 1330%% Function: coalesce_O 1331%% 1332%% Description: Coalesces nodes in worklist 1333%% Parameters: 1334%% Moves -- Current move information 1335%% IG -- Interference graph 1336%% Worklists -- Current worklists 1337%% Alias -- Current aliases for temporaries 1338%% K -- Number of registers 1339%% 1340%% Returns: 1341%% {Moves, IG, Worklists, Alias} 1342%% (Updated versions of above structures, after coalescing) 1343%%---------------------------------------------------------------------- 1344 1345-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1346coalesce_O(Moves, IG, Worklists, Alias, K, Target) -> 1347 case hipe_moves:worklist_get_and_remove(Moves) of 1348 {[],Moves0} -> 1349 %% Moves marked for removal from worklistMoves by FreezeMoves() 1350 %% are removed by worklist_get_and_remove(). This case is unlikely, 1351 %% but can occur if only stale moves remain in worklistMoves. 1352 {Moves0,IG,Worklists,Alias}; 1353 {Move,Moves0} -> 1354 {Dest,Source} = hipe_moves:get_move(Move, Moves0), 1355 ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), 1356 Alias_src = getAlias(Source, Alias), 1357 Alias_dst = getAlias(Dest, Alias), 1358 {U,V} = case is_precoloured(Alias_dst, Target) of 1359 true -> {Alias_dst, Alias_src}; 1360 false -> {Alias_src, Alias_dst} 1361 end, 1362 %% When debugging, check that neither V nor U is on the stack. 1363 case U =:= V of 1364 true -> 1365 Moves1 = Moves0, % drop coalesced move Move 1366 Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), 1367 {Moves1, IG, Worklists1, Alias}; 1368 _ -> 1369 case (is_precoloured(V, Target) orelse 1370 hipe_ig:nodes_are_adjacent(U, V, IG)) of 1371 true -> 1372 Moves1 = Moves0, % drop constrained move Move 1373 Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), 1374 Worklists2 = add_worklist(Worklists1, V, K, Moves1, IG, Target), 1375 {Moves1, IG, Worklists2, Alias}; 1376 false -> 1377 case (case is_precoloured(U, Target) of 1378 true -> 1379 AdjV = hipe_ig:node_adj_list(V, IG), 1380 all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); 1381 false -> 1382 AdjV = hipe_ig:node_adj_list(V, IG), 1383 AdjU = hipe_ig:node_adj_list(U, IG), 1384 conservative(AdjU, AdjV, U, Worklists, IG, K) 1385 end) of 1386 true -> 1387 Moves1 = Moves0, % drop coalesced move Move 1388 {IG1,Worklists1,Moves2,Alias1} = 1389 combine_O(U, V, IG, Worklists, Moves1, Alias, K, Target), 1390 Worklists2 = add_worklist(Worklists1, U, K, Moves2, IG1, Target), 1391 {Moves2, IG1, Worklists2, Alias1}; 1392 false -> 1393 Moves1 = hipe_moves:add_active(Move, Moves0), 1394 {Moves1, IG, Worklists, Alias} 1395 end 1396 end 1397 end 1398 end. 1399-endif. 1400 1401%%---------------------------------------------------------------------- 1402%% Function: add_worklist 1403%% 1404%% Description: Builds new worklists where U is transferred from freeze 1405%% to simplify, if possible 1406%% 1407%% Parameters: 1408%% Worklists -- Current worklists 1409%% U -- Node to operate on 1410%% K -- Number of registers 1411%% Moves -- Current move information 1412%% IG -- Interference graph 1413%% Target -- The containing the target-specific functions, along with 1414%% its context data. 1415%% 1416%% Returns: 1417%% Worklists (updated) 1418%%---------------------------------------------------------------------- 1419 1420-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1421add_worklist(Worklists, U, K, Moves, IG, Target) -> 1422 case (not(is_precoloured(U, Target)) 1423 andalso not(hipe_moves:move_related(U, Moves)) 1424 andalso (hipe_ig:is_trivially_colourable(U, K, IG))) of 1425 true -> 1426 hipe_reg_worklists:transfer_freeze_simplify(U, Worklists); 1427 false -> 1428 Worklists 1429 end. 1430-endif. 1431 1432%%---------------------------------------------------------------------- 1433%% Function: combine 1434%% 1435%% Description: Combines two nodes into one (used when coalescing) 1436%% 1437%% Parameters: 1438%% U -- First node to operate on 1439%% V -- Second node to operate on 1440%% IG -- Interference graph 1441%% Worklists -- Current worklists 1442%% Moves -- Current move information 1443%% Alias -- Current aliases for temporaries 1444%% K -- Number of registers 1445%% 1446%% Returns: 1447%% {IG, Worklists, Moves, Alias} (updated) 1448%%---------------------------------------------------------------------- 1449 1450-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1451combine_O(U, V, IG, Worklists, Moves, Alias, K, Target) -> 1452 Worklists1 = case hipe_reg_worklists:member_freeze(V, Worklists) of 1453 true -> hipe_reg_worklists:remove_freeze(V, Worklists); 1454 false -> hipe_reg_worklists:remove_spill(V, Worklists) 1455 end, 1456 Worklists11 = hipe_reg_worklists:add_coalesced(V, Worklists1), 1457 1458 ?debug_msg("Coalescing ~p and ~p to ~p~n",[V,U,U]), 1459 1460 Alias1 = setAlias(V, U, Alias), 1461 1462 %% Typo in published algorithm: s/nodeMoves/moveList/g to fix. 1463 %% XXX: moveList[u] \union moveList[v] OR NodeMoves(u) \union NodeMoves(v) ??? 1464 %% XXX: NodeMoves() is correct, but unnecessarily strict. The ordsets:union 1465 %% constrains NodeMoves() to return an ordset. 1466 Moves1 = hipe_moves:update_movelist(U, 1467 ordsets:union(hipe_moves:node_moves(U, Moves), 1468 hipe_moves:node_moves(V, Moves)), 1469 Moves), 1470 %% Missing in published algorithm. From Tiger book Errata. 1471 Moves2 = enable_moves_active_to_worklist(hipe_moves:node_movelist(V, Moves1), Moves1), 1472 AdjV = hipe_ig:node_adj_list(V, IG), 1473 1474 {IG1, Worklists2, Moves3} = 1475 combine_edges_O(AdjV, U, IG, Worklists11, Moves2, K, Target), 1476 1477 New_worklists = case (not(hipe_ig:is_trivially_colourable(U, K, IG1)) 1478 andalso hipe_reg_worklists:member_freeze(U, Worklists2)) of 1479 true -> hipe_reg_worklists:transfer_freeze_spill(U, Worklists2); 1480 false -> Worklists2 1481 end, 1482 {IG1, New_worklists, Moves3, Alias1}. 1483-endif. 1484 1485%%---------------------------------------------------------------------- 1486%% Function: combine 1487%% 1488%% Description: Combines two nodes into one (used when coalescing) 1489%% 1490%% Parameters: 1491%% U -- First node to operate on 1492%% V -- Second node to operate on 1493%% IG -- Interference graph 1494%% Worklists -- Current worklists 1495%% Moves -- Current move information 1496%% Alias -- Current aliases for temporaries 1497%% K -- Number of registers 1498%% 1499%% Returns: 1500%% {IG, Worklists, Moves, Alias} (updated) 1501%%---------------------------------------------------------------------- 1502 1503combine(U, V, IG, Alias, Worklists, K, Target) -> 1504 ?debug_msg("N_Coalescing ~p and ~p to ~p~n",[V,U,U]), 1505 Worklists1 = hipe_reg_worklists:add_coalesced(V, U, Worklists), 1506 Alias1 = setAlias(V, U, Alias), 1507 AdjV = hipe_ig:node_adj_list(V, IG), 1508 IG1 = combine_edges(AdjV, U, IG, Worklists1, K, Target), 1509 {IG1, Alias1, Worklists1}. 1510 1511%%---------------------------------------------------------------------- 1512%% Function: combine_edges 1513%% 1514%% Description: For each node in a list, make an edge between that node 1515%% and node U, and decrement its degree by 1 1516%% (Used when two nodes are coalesced, to connect all nodes 1517%% adjacent to one node to the other node) 1518%% 1519%% Parameters: 1520%% [T|Ts] -- List of nodes to make edges to 1521%% U -- Node to make edges from 1522%% IG -- Interference graph 1523%% Worklists -- Current worklists 1524%% Moves -- Current move information 1525%% K -- Number of registers 1526%% 1527%% Returns: 1528%% {IG, Worklists, Moves} (updated) 1529%%---------------------------------------------------------------------- 1530 1531combine_edges([], _U, IG, _Worklists, _K, _Target) -> 1532 IG; 1533combine_edges([T|Ts], U, IG, Worklists, K, Target={TgtMod,TgtCtx}) -> 1534 case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of 1535 true -> combine_edges(Ts, U, IG, Worklists, K, Target); 1536 _ -> 1537 IG1 = hipe_ig:add_edge(T, U, IG, TgtMod, TgtCtx), 1538 IG2 = case is_precoloured(T, Target) of 1539 true -> IG1; 1540 false -> hipe_ig:dec_node_degree(T, IG1) 1541 end, 1542 combine_edges(Ts, U, IG2, Worklists, K, Target) 1543 end. 1544 1545%%---------------------------------------------------------------------- 1546%% Function: combine_edges 1547%% 1548%% Description: For each node in a list, make an edge between that node 1549%% and node U, and decrement its degree by 1 1550%% (Used when two nodes are coalesced, to connect all nodes 1551%% adjacent to one node to the other node) 1552%% 1553%% Parameters: 1554%% [T|Ts] -- List of nodes to make edges to 1555%% U -- Node to make edges from 1556%% IG -- Interference graph 1557%% Worklists -- Current worklists 1558%% Moves -- Current move information 1559%% K -- Number of registers 1560%% 1561%% Returns: 1562%% {IG, Worklists, Moves} (updated) 1563%%---------------------------------------------------------------------- 1564 1565-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1566combine_edges_O([], _U, IG, Worklists, Moves, _K, _Target) -> 1567 {IG, Worklists, Moves}; 1568combine_edges_O([T|Ts], U, IG, Worklists, Moves, K, Target={TgtMod,TgtCtx}) -> 1569 case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of 1570 true -> combine_edges_O(Ts, U, IG, Worklists, Moves, K, Target); 1571 _ -> 1572 %% XXX: The issue below occurs because the T->V edge isn't removed. 1573 %% This causes adjList[T] to contain stale entries, to possibly grow 1574 %% (if T isn't already adjacent to U), and degree[T] to possibly 1575 %% increase (again, if T isn't already adjacent to U). 1576 %% The decrement_degree() call repairs degree[T] but not adjList[T]. 1577 %% It would be better to physically replace T->V with T->U, and only 1578 %% decrement_degree(T) if T->U already existed. 1579 %% 1580 %% add_edge() may change a low-degree move-related node to be of 1581 %% significant degree. In this case the node belongs in the spill 1582 %% worklist, and that's where decrement_degree() expects to find it. 1583 %% This issue is not covered in the published algorithm. 1584 OldDegree = hipe_ig:get_node_degree(T, IG), 1585 IG1 = hipe_ig:add_edge(T, U, IG, TgtMod, TgtCtx), 1586 NewDegree = hipe_ig:get_node_degree(T, IG1), 1587 Worklists0 = 1588 if NewDegree =:= K, OldDegree =:= K-1 -> 1589 %% ?debug_msg("~w:combine_edges_O(): repairing worklist membership for node ~w\n", [?MODULE,T]), 1590 %% The node T must be on the freeze worklist: 1591 %% 1. Since we're coalescing, the simplify worklist must have been 1592 %% empty when combine_edges_O() started. 1593 %% 2. decrement_degree() may put the node T back on the simplify 1594 %% worklist, but that occurs after the worklists repair step. 1595 %% 3. There are no duplicates among the edges. 1596 Worklists00 = hipe_reg_worklists:remove_freeze(T, Worklists), 1597 hipe_reg_worklists:add_spill(T, Worklists00); 1598 true -> 1599 Worklists 1600 end, 1601 {IG2, Worklists1, Moves1} = 1602 decrement_degree_O([T], IG1, Worklists0, Moves, K), 1603 combine_edges_O(Ts, U, IG2, Worklists1, Moves1, K, Target) 1604 end. 1605-endif. 1606 1607%%---------------------------------------------------------------------- 1608%% Function: undoCoalescing 1609%% 1610%% Description: Returns necessary information for a coalesced node 1611%% 1612%% Parameters: 1613%% N -- The node to uncoalesce 1614%% No_temporaries -- Number of temporaries 1615%% Alias -- The Alias vector before undoing 1616%% SavedAdj -- Saved adjacency list 1617%% IG -- Interference graph 1618%% Target -- The module containing the target-specific functions, 1619%% along with its context data. 1620%% 1621%% Returns: 1622%% list of primitive nodes, that is all nodes that were previously 1623%% coalesced to N 1624%% updated alias vector 1625%% updated Interferece graph 1626%%---------------------------------------------------------------------- 1627undoCoalescing(N, No_temporaries, Alias, SavedAdj, IG, Target) -> 1628 Primitives = findPrimitiveNodes(No_temporaries, N, Alias), 1629 Alias1 = restoreAliases(Primitives, Alias), 1630 IG1 = fixAdj(N, SavedAdj, IG, Target), 1631 {Primitives, Alias1, IG1}. 1632 1633%% Restore aliasinfo for primitive nodes, that is 1634%% unalias the node sthat were aliased to the primitive 1635%% nodes. Note that an unaliased node could be 1636%% represented in two ways, either not aliased or aliased 1637%% to itself. See also getAlias 1638restoreAliases([], Alias) -> 1639 Alias; 1640restoreAliases([Primitive|Primitives], Alias) -> 1641 Alias1 = setAlias(Primitive, Primitive, Alias), 1642 restoreAliases(Primitives, Alias1). 1643 1644%% find the primitive nodes to N, that is find all 1645%% nodes that are aliased to N 1646findPrimitiveNodes(No_temporaries, N, Alias) -> 1647 findPrimitiveNodes(No_temporaries, N, Alias, []). 1648 1649findPrimitiveNodes(0, _N, _Alias, PrimitiveNodes) -> 1650 PrimitiveNodes; 1651findPrimitiveNodes(Node, N, Alias, PrimitiveNodes) -> 1652 NextNode = Node - 1, 1653 case (getAlias(NextNode, Alias) =:= N) of 1654 true -> findPrimitiveNodes(NextNode, N, Alias, [NextNode | PrimitiveNodes]); 1655 _ -> findPrimitiveNodes(NextNode, N, Alias, PrimitiveNodes) 1656 end. 1657 1658%test_undoCoalescing(No_temporaries, Alias, Worklists) -> 1659% test_undoCoalescing(No_temporaries, No_temporaries, Alias, Worklists). 1660% 1661%test_undoCoalescing(0, _No_temporaries, _Alias, _Worklists) -> 1662% true; 1663%test_undoCoalescing(Node, No_temporaries, Alias, Worklists) -> 1664% %?debug_msg("++ the adj list: ~p~n", [SavedAdj]), 1665% %?debug_msg("Node ~p~n", [Node]), 1666% NextNode = Node - 1, 1667% Coalesced_to = hipe_reg_worklists:member_coalesced_to(NextNode, Worklists), 1668% ?debug_msg("³³-- member coalesced: ~p~n", [Coalesced_to]), 1669% {Primitives, Alias1} = undoCoalescing(NextNode, No_temporaries, Alias), 1670% ?debug_msg("½½-- primitivenodes ~w\n", [Primitives]), 1671% case (Coalesced_to) of 1672% true -> printAlias(Alias1); 1673% _ -> true 1674% end, 1675% test_undoCoalescing(NextNode, No_temporaries, Alias, Worklists). 1676 1677%%---------------------------------------------------------------------- 1678%% Function: fixAdj 1679%% 1680%% Description: Fixes adajency set and adjacency list when undoing coalescing 1681%% 1682%% Parameters: 1683%% N -- Node that should be uncoalesced 1684%% SavedAdj -- Saved adjacency list 1685%% IG -- Interference graph 1686%% Target -- The module containing the target-specific functions, along 1687%% with its context data. 1688%% 1689%% Returns: 1690%% updated Interferece graph 1691%%---------------------------------------------------------------------- 1692fixAdj(N, SavedAdj, IG, Target) -> 1693 %Saved = hipe_vectors:get(SavedAdj, N), 1694 Saved = hipe_adj_list:edges(N, SavedAdj), 1695 ?debug_msg("§§--adj to ~p: ~p~n", [N, Saved]), 1696 Adj = hipe_ig:node_adj_list(N, IG), 1697 ?debug_msg("««--adj to ~p: ~p~n", [N, Adj]), 1698 New = findNew(Adj, Saved), 1699 ?debug_msg("++--new adj to ~p: ~p~n", [N, New]), 1700 removeAdj(New, N, IG, Target), 1701 %% XXX the following lines seems to make double nodes in 1702 %% some adj_lists, which is a bug, apart from that they 1703 %% don't seem to make any difference at all (even though 1704 %% they are in the pseudocode of "optimistic coalescing") 1705 %% addedge for all in the restored adj_list 1706 %%RestoredAdj = hipe_ig:node_adj_list(N, IG), 1707 %%?debug_msg("adj_lists_before_restore_o ~n~p~n", [hipe_ig:adj_list(IG)]), 1708 %%restoreAdj(RestoredAdj, N, IG, Alias, Target). 1709 IG. 1710 1711removeAdj([], _N, _IG, _Target) -> 1712 true; 1713removeAdj([V| New], N, IG, Target={TgtMod,TgtCtx}) -> 1714 hipe_ig:remove_edge(V, N, IG, TgtMod, TgtCtx), 1715 removeAdj(New, N, IG, Target). 1716 1717%%restoreAdj([], _N, IG, _Alias, _Target) -> 1718%% %%?debug_msg("adj_lists__after_restore_o ~n~p~n", [hipe_ig:adj_list(IG)]), 1719%% IG; 1720%%restoreAdj([V| AdjToN], N, IG, Alias, Target={TgtMod,TgtCtx}) -> 1721%% AliasToV = getAlias(V, Alias), 1722%% IG1 = hipe_ig:add_edge(N, AliasToV, IG, TgtMod, TgtCtx), 1723%% restoreAdj(AdjToN, N, IG1, Alias, Target). 1724 1725%% XXX This is probably a clumsy way of doing it 1726%% better to assure the lists are sorted from the beginning 1727%% also coalesce findNew and removeAdj should improve performance 1728findNew(Adj, Saved) -> 1729 findNew(Adj, Saved, []). 1730 1731findNew([], _Saved, New) -> 1732 New; 1733findNew([A| Adj], Saved, New) -> 1734 case lists:member(A, Saved) of 1735 true -> findNew(Adj, Saved, New); 1736 _ -> findNew(Adj, Saved, [A| New]) 1737 end. 1738 1739%test_fixAdj(0, _SavedAdj, IG, _Target) -> 1740% IG; 1741%test_fixAdj(Node, SavedAdj, IG, Target) -> 1742% NextNode = Node - 1, 1743% IG1 = fixAdj(NextNode, SavedAdj, IG, Target), 1744% test_fixAdj(NextNode, SavedAdj, IG1, Target). 1745%%---------------------------------------------------------------------- 1746%% Function: ok 1747%% 1748%% Description: Checks if a node T is suitable to coalesce with R 1749%% 1750%% Parameters: 1751%% T -- Node to test 1752%% R -- Other node to test 1753%% IG -- Interference graph 1754%% K -- Number of registers 1755%% Target -- The module containing the target-specific functions, along 1756%% with its context data. 1757%% 1758%% Returns: 1759%% true iff coalescing is OK 1760%%---------------------------------------------------------------------- 1761 1762ok(T, R, IG, K, Target) -> 1763 ((hipe_ig:is_trivially_colourable(T, K, IG)) 1764 orelse is_precoloured(T, Target) 1765 orelse hipe_ig:nodes_are_adjacent(T, R, IG)). 1766 1767%%---------------------------------------------------------------------- 1768%% Function: all_ok 1769%% 1770%% Description: True iff, for every T in the list, OK(T,U) 1771%% 1772%% Parameters: 1773%% [T|Ts] -- Nodes to test 1774%% U -- Node to test for coalescing 1775%% IG -- Interference graph 1776%% K -- Number of registers 1777%% Target -- The module containing the target-specific functions, along 1778%% with its context data. 1779%% 1780%% Returns: 1781%% true iff coalescing is OK for all nodes in the list 1782%%---------------------------------------------------------------------- 1783 1784all_adjacent_ok([], _U, _Worklists, _IG, _K, _Target) -> true; 1785all_adjacent_ok([T|Ts], U, Worklists, IG, K, Target) -> 1786 case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of 1787 true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target); 1788 _ -> 1789 %% 'andalso' does not preserve tail-recursion 1790 case ok(T, U, IG, K, Target) of 1791 true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target); 1792 false -> false 1793 end 1794 end. 1795 1796%%---------------------------------------------------------------------- 1797%% Function: conservative 1798%% 1799%% Description: Checks if nodes can be safely coalesced according to 1800%% the Briggs' conservative coalescing heuristic 1801%% 1802%% Parameters: 1803%% Nodes -- Adjacent nodes 1804%% IG -- Interference graph 1805%% K -- Number of registers 1806%% 1807%% Returns: 1808%% true iff coalescing is safe 1809%%---------------------------------------------------------------------- 1810 1811conservative(AdjU, AdjV, U, Worklists, IG, K) -> 1812 conservative_countU(AdjU, AdjV, U, Worklists, IG, K, 0). 1813 1814%%---------------------------------------------------------------------- 1815%% Function: conservative_count 1816%% 1817%% Description: Counts degrees for conservative (Briggs' heuristics) 1818%% 1819%% Parameters: 1820%% Nodes -- (Remaining) adjacent nodes 1821%% IG -- Interference graph 1822%% K -- Number of registers 1823%% Cnt -- Accumulator for counting 1824%% 1825%% Returns: 1826%% Final value of accumulator 1827%%---------------------------------------------------------------------- 1828 1829conservative_countU([], AdjV, U, Worklists, IG, K, Cnt) -> 1830 conservative_countV(AdjV, U, Worklists, IG, K, Cnt); 1831conservative_countU([Node|AdjU], AdjV, U, Worklists, IG, K, Cnt) -> 1832 case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of 1833 true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt); 1834 _ -> 1835 case hipe_ig:is_trivially_colourable(Node, K, IG) of 1836 true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt); 1837 _ -> 1838 Cnt1 = Cnt + 1, 1839 if Cnt1 < K -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt1); 1840 true -> false 1841 end 1842 end 1843 end. 1844 1845conservative_countV([], _U, _Worklists, _IG, _K, _Cnt) -> true; 1846conservative_countV([Node|AdjV], U, Worklists, IG, K, Cnt) -> 1847 case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of 1848 true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); 1849 _ -> 1850 case hipe_ig:nodes_are_adjacent(Node, U, IG) of 1851 true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); 1852 _ -> 1853 case hipe_ig:is_trivially_colourable(Node, K, IG) of 1854 true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); 1855 _ -> 1856 Cnt1 = Cnt + 1, 1857 if Cnt1 < K -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt1); 1858 true -> false 1859 end 1860 end 1861 end 1862 end. 1863 1864%%--------------------------------------------------------------------- 1865%% Function: selectSpill 1866%% 1867%% Description: Select the node to spill and spill it 1868%% Parameters: 1869%% WorkLists -- A datatype containing the different worklists 1870%% IG -- The interference graph 1871%% K -- The number of available registers 1872%% Alias -- The alias mapping 1873%% SpillLimit -- Try not to spill any nodes above the spill limit 1874%% 1875%% Returns: 1876%% WorkLists -- The updated worklists 1877%%--------------------------------------------------------------------- 1878 1879selectSpill(WorkLists, IG, SpillLimit) -> 1880 [CAR|CDR] = hipe_reg_worklists:spill(WorkLists), 1881 SpillCost = getCost(CAR, IG, SpillLimit), 1882 M = findCheapest(CDR, IG, SpillCost, CAR, SpillLimit), 1883 WorkLists1 = hipe_reg_worklists:remove_spill(M, WorkLists), 1884 hipe_reg_worklists:add_simplify(M, WorkLists1). 1885 1886%%--------------------------------------------------------------------- 1887%% Function: selectSpill 1888%% 1889%% Description: Select the node to spill and spill it 1890%% Parameters: 1891%% WorkLists -- A datatype containing the different worklists 1892%% Moves -- A datatype containing the move sets 1893%% IG -- The interference graph 1894%% K -- The number of available registers 1895%% Alias -- The alias mapping 1896%% SpillLimit -- Try not to spill any nodes above the spill limit 1897%% 1898%% Returns: 1899%% WorkLists -- The updated worklists 1900%% Moves -- The updated moves 1901%%--------------------------------------------------------------------- 1902 1903-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1904selectSpill_O(WorkLists, Moves, IG, K, Alias, SpillLimit) -> 1905 [CAR|CDR] = hipe_reg_worklists:spill(WorkLists), 1906 1907 SpillCost = getCost(CAR, IG, SpillLimit), 1908 M = findCheapest(CDR, IG, SpillCost, CAR, SpillLimit), 1909 1910 WorkLists1 = hipe_reg_worklists:remove_spill(M, WorkLists), 1911 %% The published algorithm adds M to the simplify worklist 1912 %% before the freezeMoves() call. That breaks the worklist 1913 %% invariants, which is why the order is switched here. 1914 {WorkLists2,Moves1} = freezeMoves(M, K, WorkLists1, Moves, IG, Alias), 1915 WorkLists3 = hipe_reg_worklists:add_simplify(M, WorkLists2), 1916 {WorkLists3,Moves1}. 1917-endif. 1918 1919%% Find the node that is cheapest to spill 1920 1921findCheapest([], _IG, _Cost, Cheapest, _SpillLimit) -> 1922 Cheapest; 1923findCheapest([Node|Nodes], IG, Cost, Cheapest, SpillLimit) -> 1924 ThisCost = getCost(Node, IG, SpillLimit), 1925 case ThisCost < Cost of 1926 true -> 1927 findCheapest(Nodes, IG, ThisCost, Node, SpillLimit); 1928 false -> 1929 findCheapest(Nodes, IG, Cost, Cheapest, SpillLimit) 1930 end. 1931 1932%% Get the cost for spilling a certain node, node numbers above the spill 1933%% limit are extremely expensive. 1934 1935getCost(Node, IG, SpillLimit) -> 1936 case Node >= SpillLimit of 1937 true -> inf; 1938 false -> 1939 SpillCost = hipe_ig:node_spill_cost(Node, IG), 1940 ?debug_msg("Actual spillcost f node ~w is ~w~n", [Node, SpillCost]), 1941 SpillCost 1942 end. 1943 1944%%---------------------------------------------------------------------- 1945%% Function: freeze 1946%% 1947%% Description: When both simplifying and coalescing is impossible we 1948%% rather freezes a node in stead of spilling, this function 1949%% selects a node for freezing (it just picks the first one in 1950%% the list) 1951%% 1952%% Parameters: 1953%% K -- The number of available registers 1954%% WorkLists -- A datatype containing the different worklists 1955%% Moves -- A datatype containing the different movelists 1956%% IG -- Interference graph 1957%% Alias -- An alias mapping, shows the alias of all coalesced 1958%% nodes 1959%% 1960%% Returns: 1961%% WorkLists -- The updated worklists 1962%% Moves -- The updated movelists 1963%%---------------------------------------------------------------------- 1964 1965-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1966freeze(K, WorkLists, Moves, IG, Alias) -> 1967 [U|_] = hipe_reg_worklists:freeze(WorkLists), % Smarter routine? 1968 ?debug_msg("freezing node ~p~n", [U]), 1969 WorkLists0 = hipe_reg_worklists:remove_freeze(U, WorkLists), 1970 %% The published algorithm adds U to the simplify worklist 1971 %% before the freezeMoves() call. That breaks the worklist 1972 %% invariants, which is why the order is switched here. 1973 {WorkLists1, Moves1} = freezeMoves(U, K, WorkLists0, Moves, IG, Alias), 1974 WorkLists2 = hipe_reg_worklists:add_simplify(U, WorkLists1), 1975 {WorkLists2, Moves1}. 1976-endif. 1977 1978%%---------------------------------------------------------------------- 1979%% Function: freezeMoves 1980%% 1981%% Description: Make all move related interferences for a certain node 1982%% into ordinary interference arcs. 1983%% 1984%% Parameters: 1985%% U -- The node we want to freeze 1986%% K -- The number of available registers 1987%% WorkLists -- A datatype containing the different worklists 1988%% Moves -- A datatype containing the different movelists 1989%% IG -- Interference graph 1990%% Alias -- An alias mapping, shows the alias of all coalesced 1991%% nodes 1992%% 1993%% Returns: 1994%% WorkLists -- The updated worklists 1995%% Moves -- The updated movelists 1996%%---------------------------------------------------------------------- 1997 1998-ifdef(COMPARE_ITERATED_OPTIMISTIC). 1999freezeMoves(U, K, WorkLists, Moves, IG, Alias) -> 2000 Nodes = hipe_moves:node_moves(U, Moves), 2001 freezeEm(U, Nodes, K, WorkLists, Moves, IG, Alias). 2002 2003%% Find what the other value in a copy instruction is, return false if 2004%% the instruction isn't a move with the first argument in it. 2005 2006moves(U, Move, Alias, Moves) -> 2007 {X,Y} = hipe_moves:get_move(Move, Moves), 2008 %% The old code (which followed the published algorithm) did 2009 %% not follow aliases before looking for "the other" node. 2010 %% This caused moves() to skip some moves, making some nodes 2011 %% still move-related after freezeMoves(). These move-related 2012 %% nodes were then added to the simplify worklist (by freeze() 2013 %% or selectSpill()), breaking the worklist invariants. Nodes 2014 %% already simplified appeared in coalesce_O(), were re-added to 2015 %% the simplify worklist by add_worklist(), simplified again, 2016 %% and coloured multiple times by assignColors(). Ouch! 2017 X1 = getAlias(X, Alias), 2018 Y1 = getAlias(Y, Alias), 2019 if U =:= X1 -> Y1; 2020 U =:= Y1 -> X1; 2021 true -> exit({?MODULE,moves}) % XXX: shouldn't happen 2022 end. 2023 2024freezeEm(_U, [], _K, WorkLists, Moves, _IG, _Alias) -> 2025 {WorkLists,Moves}; 2026freezeEm(U, [M|Ms], K, WorkLists, Moves, IG, Alias) -> 2027 V = moves(U, M, Alias, Moves), 2028 {WorkLists2,Moves2} = freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias), 2029 freezeEm(U, Ms, K, WorkLists2, Moves2, IG, Alias). 2030 2031freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias) -> 2032 case hipe_moves:member_active(M, Moves) of 2033 true -> 2034 Moves1 = hipe_moves:remove_active(M, Moves), 2035 freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias); 2036 false -> 2037 Moves1 = hipe_moves:remove_worklist(M, Moves), 2038 freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias) 2039 end. 2040 2041freezeEm3(_U,V,_M,K,WorkLists,Moves,IG,_Alias) -> 2042 Moves1 = Moves, % drop frozen move M 2043 V1 = V, % getAlias(V,Alias), 2044 %% "not MoveRelated(v)" is cheaper than "NodeMoves(v) = {}" 2045 case ((not hipe_moves:move_related(V1,Moves1)) andalso 2046 hipe_ig:is_trivially_colourable(V1,K,IG)) of 2047 true -> 2048 ?debug_msg("freezing move to ~p~n", [V]), 2049 Worklists1 = hipe_reg_worklists:transfer_freeze_simplify(V1, WorkLists), 2050 {Worklists1,Moves1}; 2051 false -> 2052 {WorkLists,Moves1} 2053 end. 2054-endif. 2055 2056%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2057%% 2058%% Interface to external functions. 2059%% 2060%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2061 2062all_precoloured({TgtMod,TgtCtx}) -> 2063 TgtMod:all_precoloured(TgtCtx). 2064 2065allocatable({TgtMod,TgtCtx}) -> 2066 TgtMod:allocatable(TgtCtx). 2067 2068is_precoloured(R, {TgtMod,TgtCtx}) -> 2069 TgtMod:is_precoloured(R,TgtCtx). 2070 2071number_of_temporaries(CFG, {TgtMod,TgtCtx}) -> 2072 TgtMod:number_of_temporaries(CFG, TgtCtx). 2073 2074physical_name(R, {TgtMod,TgtCtx}) -> 2075 TgtMod:physical_name(R,TgtCtx). 2076