58
58
%% that the coloring agrees with the interference graph (that is, that
59
59
%% no neighbors have the same register or spill location).
61
%% @spec regalloc(#cfg{}, non_neg_fixnum(), non_neg_fixnum(), atom(), list()) -> {, non_neg_fixnum()}
61
63
regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) ->
62
64
PhysRegs = Target:allocatable(),
63
65
?report2("building IG~n", []),
64
66
{IG, Spill} = build_ig(CFG, Target),
67
?report3("graph: ~p~nphysical regs: ~p~n",[list_ig(IG), PhysRegs]),
69
?report3("graph: ~p~nphysical regs: ~p~n", [list_ig(IG), PhysRegs]),
69
71
%% These nodes *can't* be allocated to registers.
70
72
NotAllocatable = [Target:reg_nr(X) || X <- Target:non_alloc(CFG)],
143
145
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
145
147
interference_arcs([], _Live, IG) ->
147
interference_arcs([X|Xs],Live,IG) ->
148
interference_arcs(Xs, Live, i_arcs(X, Live, IG)).
149
interference_arcs([X|Xs], Live, IG) ->
150
interference_arcs(Xs, Live, i_arcs(X, Live, IG)).
150
152
i_arcs(_X, [], IG) ->
152
154
i_arcs(X, [Y|Ys], IG) ->
153
i_arcs(X, Ys, add_edge(X,Y, IG)).
155
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
157
inc_spill_costs([],Spill) -> Spill;
158
inc_spill_costs([X|Xs],Spill) ->
159
inc_spill_costs(Xs,inc_spill_cost(X,Spill)).
161
inc_spill_cost(X,Spill) ->
162
set_spill_cost(X,get_spill_cost(X,Spill)+1,Spill).
164
get_spill_cost(X,Spill) ->
165
spill_cost_lookup(X,Spill).
167
set_spill_cost(X,N,Spill) ->
168
spill_cost_update(X,N,Spill).
170
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
155
i_arcs(X, Ys, add_edge(X,Y, IG)).
157
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
159
inc_spill_costs([], Spill) -> Spill;
160
inc_spill_costs([X|Xs], Spill) ->
161
inc_spill_costs(Xs, inc_spill_cost(X, Spill)).
163
inc_spill_cost(X, Spill) ->
164
set_spill_cost(X, get_spill_cost(X, Spill)+1, Spill).
166
get_spill_cost(X, Spill) ->
167
spill_cost_lookup(X, Spill).
169
set_spill_cost(X, N, Spill) ->
170
spill_cost_update(X, N, Spill).
172
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
174
175
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
308
309
simplify_ig([], N, IG, Spill, K, Ix, Stk, Vis, SpillLimit, Target)
310
?report3("N: ~w Stk: ~w N+Stk ~w\n",[N,length(Stk),N+length(Stk)]),
312
?report(" *** spill required (N<~w)***~n",[SpillLimit]),
311
?report3("N: ~w Stk: ~w N+Stk ~w\n", [N,length(Stk),N+length(Stk)]),
312
?report(" *** spill required (N<~w)***~n", [SpillLimit]),
313
313
{X, Low, NewIG} = spill(IG, Vis, Spill, K, SpillLimit, Target),
314
314
NewVis = visit(X,Vis),
315
315
{NewStk, NewIx} = push_spill_node(X, Ix, Stk),
530
525
Deg = degree(Info),
533
[N|low_degree_nodes(Xs,K, NotAllocatable)];
528
[N|low_degree_nodes(Xs, K, NotAllocatable)];
535
low_degree_nodes(Xs,K, NotAllocatable)
530
low_degree_nodes(Xs, K, NotAllocatable)
539
534
%%%%%%%%%%%%%%%%%%%%
541
unvisited_neighbors(X,Vis,IG) ->
542
ordsets:from_list(unvisited(neighbors(X,IG),Vis)).
544
unvisited([],_Vis) -> [];
545
unvisited([X|Xs],Vis) ->
546
case is_visited(X,Vis) of
550
[X|unvisited(Xs,Vis)]
536
unvisited_neighbors(X, Vis, IG) ->
537
ordsets:from_list(unvisited(neighbors(X,IG), Vis)).
539
unvisited([], _Vis) -> [];
540
unvisited([X|Xs], Vis) ->
541
case is_visited(X, Vis) of
545
[X|unvisited(Xs, Vis)]
554
548
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
661
654
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
663
656
%% Note: there might be a slight gain in separating the two versions
664
%% of visit/2 and visited/2. (So that {var,X} selects X and calls
665
%% the integer version.
657
%% of visit/2 and visited/2. (So that {var,X} selects X and calls the
667
660
none_visited(NumNodes) ->
668
hipe_vectors:new(NumNodes,false).
661
hipe_vectors:new(NumNodes, false).
671
hipe_vectors:set(Vis,X,true).
664
hipe_vectors:set(Vis, X, true).
673
666
is_visited(X,Vis) ->
674
hipe_vectors:get(Vis,X).
667
hipe_vectors:get(Vis, X).
676
visit_all([],Vis) -> Vis;
677
visit_all([X|Xs],Vis) ->
678
visit_all(Xs,visit(X,Vis)).
669
visit_all([], Vis) -> Vis;
670
visit_all([X|Xs], Vis) ->
671
visit_all(Xs, visit(X, Vis)).
680
673
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
681
674
%% Check that all arcs in IG are bidirectional + degree is correct
684
% check_ig(list_ig(IG),IG).
688
% check_ig([{N,Info}|Xs],IG) ->
689
% Ns = neighbors(Info),
690
% NumNs = length(Ns),
696
% ?WARNING_MSG('node ~p has degree ~p but ~p neighbors~n',[N,D,NumNs])
698
% check_neighbors(N,Ns,IG),
701
% check_neighbors(N,[],IG) ->
703
% check_neighbors(N,[M|Ms],IG) ->
704
% Ns = neighbors(M,IG),
705
% case member(N,Ns) of
709
% ?WARNING_MSG('node ~p should have ~p as neighbor (has ~p)~n',[M,N,Ns])
711
% check_neighbors(N,Ms,IG).
677
%% check_ig(list_ig(IG),IG).
679
%% check_ig([],IG) ->
681
%% check_ig([{N,Info}|Xs],IG) ->
682
%% Ns = neighbors(Info),
683
%% NumNs = length(Ns),
689
%% ?WARNING_MSG('node ~p has degree ~p but ~p neighbors~n',[N,D,NumNs])
691
%% check_neighbors(N,Ns,IG),
694
%% check_neighbors(N,[],IG) ->
696
%% check_neighbors(N,[M|Ms],IG) ->
697
%% Ns = neighbors(M,IG),
698
%% case member(N,Ns) of
702
%% ?WARNING_MSG('node ~p should have ~p as neighbor (has ~p)~n',[M,N,Ns])
704
%% check_neighbors(N,Ms,IG).
713
706
-ifdef(DO_ASSERT).
714
707
%%%%%%%%%%%%%%%%%%%%
715
708
%% Check that the coloring is correct (if the IG is correct):
718
check_coloring(Coloring,IG, Target) ->
719
?report0("checking coloring ~p~n",[Coloring]),
720
check_cols(list_ig(IG),init_coloring(Coloring, Target)).
711
check_coloring(Coloring, IG, Target) ->
712
?report0("checking coloring ~p~n",[Coloring]),
713
check_cols(list_ig(IG),init_coloring(Coloring, Target)).
722
715
init_coloring(Xs, Target) ->
723
716
hipe_temp_map:cols2tuple(Xs, Target).
725
check_color_of(X,Cols) ->
718
check_color_of(X, Cols) ->
727
720
%% is_precoloured(X) ->
728
721
%% phys_reg_color(X,Cols);
730
case hipe_temp_map:find(X,Cols) of
732
?WARNING_MSG("node ~p: color not found~n",[X]),
738
check_cols([],Cols) ->
739
?report("coloring valid~n",[]),
741
check_cols([{X,Info}|Xs],Cols) ->
742
Cs = [ {N,check_color_of(N,Cols)} || N <- neighbors(Info) ],
743
C = check_color_of(X,Cols),
744
case valid_coloring(X,C,Cs) of
748
?WARNING_MSG("node ~p has same color (~p) as ~p~n",
753
valid_coloring(X,C,[]) ->
755
valid_coloring(X,C,[{Y,C}|Ys]) ->
756
case valid_coloring(X,C,Ys) of
758
{no,Zs} -> {no,[Y|Zs]}
761
valid_coloring(X,C,[_|Ys]) ->
762
valid_coloring(X,C,Ys).
723
case hipe_temp_map:find(X, Cols) of
725
?WARNING_MSG("node ~p: color not found~n", [X]),
731
check_cols([], Cols) ->
732
?report("coloring valid~n",[]),
734
check_cols([{X,Info}|Xs], Cols) ->
735
Cs = [{N, check_color_of(N, Cols)} || N <- neighbors(Info)],
736
C = check_color_of(X, Cols),
737
case valid_coloring(X, C, Cs) of
739
check_cols(Xs, Cols);
741
?WARNING_MSG("node ~p has same color (~p) as ~p~n", [X,C,Invalids]),
745
valid_coloring(X, C, []) ->
747
valid_coloring(X, C, [{Y,C}|Ys]) ->
748
case valid_coloring(X, C, Ys) of
750
{no,Zs} -> {no, [Y|Zs]}
752
valid_coloring(X, C, [_|Ys]) ->
753
valid_coloring(X, C, Ys).
796
787
precolor(Xs, Cols, Target) ->
797
?report("precoloring ~p~n",[Xs]),
798
{Cs,NewCol} = precolor0(Xs, Cols, Target),
799
?report(" yielded ~p~n", [Cs]),
788
?report("precoloring ~p~n", [Xs]),
789
{Cs,NewCol} = precolor0(Xs, Cols, Target),
790
?report(" yielded ~p~n", [Cs]),
802
793
precolor0([], Cols, _Target) ->
804
795
precolor0([R|Rs], Cols, Target) ->
805
{Cs, Cols1} = precolor0(Rs, Cols, Target),
806
{[{R,{reg,physical_name(R, Target)}}|Cs],
807
set_color(R,physical_name(R, Target),Cols1)}.
796
{Cs, Cols1} = precolor0(Rs, Cols, Target),
797
{[{R, {reg, physical_name(R, Target)}}|Cs],
798
set_color(R, physical_name(R, Target), Cols1)}.
809
800
physical_name(X, Target) ->
810
Target:physical_name(X).
801
Target:physical_name(X).
added
removed
lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl
