From 84adefa331c4159d432d22840663c38f155cd4c1 Mon Sep 17 00:00:00 2001 From: Erlang/OTP Date: Fri, 20 Nov 2009 14:54:40 +0000 Subject: The R13B03 release. --- lib/hipe/regalloc/Makefile | 123 ++ lib/hipe/regalloc/hipe_adj_list.erl | 143 ++ lib/hipe/regalloc/hipe_amd64_specific.erl | 20 + lib/hipe/regalloc/hipe_amd64_specific_sse2.erl | 175 ++ lib/hipe/regalloc/hipe_amd64_specific_x87.erl | 20 + lib/hipe/regalloc/hipe_arm_specific.erl | 168 ++ lib/hipe/regalloc/hipe_coalescing_regalloc.erl | 1029 ++++++++++ lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl | 806 ++++++++ lib/hipe/regalloc/hipe_ig.erl | 776 ++++++++ lib/hipe/regalloc/hipe_ig_moves.erl | 81 + lib/hipe/regalloc/hipe_ls_regalloc.erl | 788 ++++++++ lib/hipe/regalloc/hipe_moves.erl | 165 ++ lib/hipe/regalloc/hipe_node_sets.erl | 48 + lib/hipe/regalloc/hipe_optimistic_regalloc.erl | 2043 ++++++++++++++++++++ lib/hipe/regalloc/hipe_ppc_specific.erl | 168 ++ lib/hipe/regalloc/hipe_ppc_specific_fp.erl | 146 ++ lib/hipe/regalloc/hipe_reg_worklists.erl | 360 ++++ lib/hipe/regalloc/hipe_regalloc_loop.erl | 68 + lib/hipe/regalloc/hipe_sparc_specific.erl | 168 ++ lib/hipe/regalloc/hipe_sparc_specific_fp.erl | 146 ++ lib/hipe/regalloc/hipe_spillcost.erl | 101 + lib/hipe/regalloc/hipe_spillcost.hrl | 27 + lib/hipe/regalloc/hipe_temp_map.erl | 125 ++ lib/hipe/regalloc/hipe_x86_specific.erl | 203 ++ lib/hipe/regalloc/hipe_x86_specific_x87.erl | 164 ++ 25 files changed, 8061 insertions(+) create mode 100644 lib/hipe/regalloc/Makefile create mode 100644 lib/hipe/regalloc/hipe_adj_list.erl create mode 100644 lib/hipe/regalloc/hipe_amd64_specific.erl create mode 100644 lib/hipe/regalloc/hipe_amd64_specific_sse2.erl create mode 100644 lib/hipe/regalloc/hipe_amd64_specific_x87.erl create mode 100644 lib/hipe/regalloc/hipe_arm_specific.erl create mode 100644 lib/hipe/regalloc/hipe_coalescing_regalloc.erl create mode 100644 lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl create mode 100644 lib/hipe/regalloc/hipe_ig.erl create mode 100644 lib/hipe/regalloc/hipe_ig_moves.erl create mode 100644 lib/hipe/regalloc/hipe_ls_regalloc.erl create mode 100644 lib/hipe/regalloc/hipe_moves.erl create mode 100644 lib/hipe/regalloc/hipe_node_sets.erl create mode 100644 lib/hipe/regalloc/hipe_optimistic_regalloc.erl create mode 100644 lib/hipe/regalloc/hipe_ppc_specific.erl create mode 100644 lib/hipe/regalloc/hipe_ppc_specific_fp.erl create mode 100644 lib/hipe/regalloc/hipe_reg_worklists.erl create mode 100644 lib/hipe/regalloc/hipe_regalloc_loop.erl create mode 100644 lib/hipe/regalloc/hipe_sparc_specific.erl create mode 100644 lib/hipe/regalloc/hipe_sparc_specific_fp.erl create mode 100644 lib/hipe/regalloc/hipe_spillcost.erl create mode 100644 lib/hipe/regalloc/hipe_spillcost.hrl create mode 100644 lib/hipe/regalloc/hipe_temp_map.erl create mode 100644 lib/hipe/regalloc/hipe_x86_specific.erl create mode 100644 lib/hipe/regalloc/hipe_x86_specific_x87.erl (limited to 'lib/hipe/regalloc') diff --git a/lib/hipe/regalloc/Makefile b/lib/hipe/regalloc/Makefile new file mode 100644 index 0000000000..5ab70d1837 --- /dev/null +++ b/lib/hipe/regalloc/Makefile @@ -0,0 +1,123 @@ +# +# %CopyrightBegin% +# +# Copyright Ericsson AB 2001-2009. All Rights Reserved. +# +# The contents of this file are subject to the Erlang Public License, +# Version 1.1, (the "License"); you may not use this file except in +# compliance with the License. You should have received a copy of the +# Erlang Public License along with this software. If not, it can be +# retrieved online at http://www.erlang.org/. +# +# Software distributed under the License is distributed on an "AS IS" +# basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +# the License for the specific language governing rights and limitations +# under the License. +# +# %CopyrightEnd% +# + +ifndef EBIN +EBIN = ../ebin +endif + +ifndef DOCS +DOCS = ../doc +endif + +include $(ERL_TOP)/make/target.mk +include $(ERL_TOP)/make/$(TARGET)/otp.mk + +# ---------------------------------------------------- +# Application version +# ---------------------------------------------------- +include ../vsn.mk +VSN=$(HIPE_VSN) + +# ---------------------------------------------------- +# Release directory specification +# ---------------------------------------------------- +RELSYSDIR = $(RELEASE_PATH)/lib/hipe-$(VSN) + +# ---------------------------------------------------- +# Target Specs +# ---------------------------------------------------- +MODULES = hipe_ig hipe_ig_moves hipe_moves \ + hipe_node_sets hipe_spillcost hipe_reg_worklists \ + hipe_adj_list \ + hipe_temp_map \ + hipe_optimistic_regalloc \ + hipe_coalescing_regalloc \ + hipe_graph_coloring_regalloc \ + hipe_regalloc_loop \ + hipe_ls_regalloc \ + hipe_ppc_specific hipe_ppc_specific_fp \ + hipe_sparc_specific hipe_sparc_specific_fp \ + hipe_arm_specific \ + hipe_x86_specific hipe_x86_specific_x87 \ + hipe_amd64_specific hipe_amd64_specific_sse2 hipe_amd64_specific_x87 + +HRL_FILES= +ERL_FILES= $(MODULES:%=%.erl) +TARGET_FILES= $(MODULES:%=$(EBIN)/%.$(EMULATOR)) +DOC_FILES= $(MODULES:%=$(DOCS)/%.html) + +# APP_FILE= +# APP_SRC= $(APP_FILE).src +# APP_TARGET= $(EBIN)/$(APP_FILE) +# +# APPUP_FILE= +# APPUP_SRC= $(APPUP_FILE).src +# APPUP_TARGET= $(EBIN)/$(APPUP_FILE) + +# ---------------------------------------------------- +# FLAGS +# ---------------------------------------------------- + +include ../native.mk + +ERL_COMPILE_FLAGS += +warn_exported_vars# +warn_missing_spec +warn_untyped_record + +# ---------------------------------------------------- +# Targets +# ---------------------------------------------------- + +debug opt: $(TARGET_FILES) + +docs: $(DOC_FILES) + +clean: + rm -f $(TARGET_FILES) + rm -f core + +$(DOCS)/%.html:%.erl + erl -noshell -run edoc_run file '"$<"' '[{dir, "$(DOCS)"}]' -s init stop + +# ---------------------------------------------------- +# Special Build Targets +# ---------------------------------------------------- + + + +# ---------------------------------------------------- +# Release Target +# ---------------------------------------------------- +include $(ERL_TOP)/make/otp_release_targets.mk + +release_spec: opt + $(INSTALL_DIR) $(RELSYSDIR)/ebin + $(INSTALL_DATA) $(TARGET_FILES) $(RELSYSDIR)/ebin + +release_docs_spec: + +$(EBIN)/hipe_amd64_specific.beam: hipe_x86_specific.erl +$(EBIN)/hipe_amd64_specific_x87.beam: hipe_x86_specific_x87.erl +$(EBIN)/hipe_coalescing_regalloc.beam: ../main/hipe.hrl +$(EBIN)/hipe_graph_coloring_regalloc.beam: ../main/hipe.hrl +$(EBIN)/hipe_ig.beam: ../main/hipe.hrl ../flow/cfg.hrl hipe_spillcost.hrl +$(EBIN)/hipe_ig_moves.beam: ../util/hipe_vectors.hrl +$(EBIN)/hipe_ls_regalloc.beam: ../main/hipe.hrl +$(EBIN)/hipe_optimistic_regalloc.beam: ../main/hipe.hrl +$(EBIN)/hipe_regalloc_loop.beam: ../main/hipe.hrl +$(EBIN)/hipe_spillcost.beam: hipe_spillcost.hrl +$(EBIN)/hipe_temp_map.beam: ../main/hipe.hrl diff --git a/lib/hipe/regalloc/hipe_adj_list.erl b/lib/hipe/regalloc/hipe_adj_list.erl new file mode 100644 index 0000000000..b55b22cb22 --- /dev/null +++ b/lib/hipe/regalloc/hipe_adj_list.erl @@ -0,0 +1,143 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%---------------------------------------------------------------------- +%% File : hipe_adj_list.erl +%% Author : Andreas Wallin +%% Purpose : Keeps track of adjacency lists for the inference graph. +%% Created : 18 Mar 2000 by Andreas Wallin +%%---------------------------------------------------------------------- + +-module(hipe_adj_list). +-author("Andreas Wallin"). +-export([new/1, + add_edge/3, + %% add_edges/3, + remove_edge/3, + %% remove_edges/3, + edges/2]). + +%%---------------------------------------------------------------------- +%% Function: new +%% +%% Description: Creates an empty structure for adjacency lists +%% +%% Parameters: +%% Max_nodes -- Limit for node numbers +%% +%% Returns: +%% Empty adj_list structure +%% +%%---------------------------------------------------------------------- + +new(Max_nodes) -> + hipe_vectors:new(Max_nodes, []). + +%%---------------------------------------------------------------------- +%% Function: add_edges +%% +%% Description: Adds edges from a node to other nodes +%% +%% Parameters: +%% U -- A node +%% Vs -- Nodes to add edges to +%% Adj_list -- Old adjacency lists +%% +%% Returns: +%% An updated adj_list data-structure +%% +%%---------------------------------------------------------------------- + +%%add_edges(_, [], Adj_list) -> Adj_list; +%%add_edges(U, Vs, Adj_list) when is_list(Vs), is_integer(U) -> +%% hipe_vectors:set(Adj_list, U, ordsets:union(Vs, hipe_vectors:get(Adj_list, U))). + +%%---------------------------------------------------------------------- +%% Function: add_edge +%% +%% Description: Creates an edge between two nodes +%% +%% Parameters: +%% U -- A node +%% V -- Another node +%% Adj_list -- Old adjacency lists +%% +%% Returns: +%% New adj_list data-structure with (U and V connected) +%% +%%---------------------------------------------------------------------- + +add_edge(U, V, Adj_list) -> % PRE: U =/= V, not V \in adjList[U] + hipe_vectors:set(Adj_list, U, + [V | hipe_vectors:get(Adj_list, U)]). + +%%---------------------------------------------------------------------- +%% Function: remove_edges +%% +%% Description: Removes edges from a node to other nodes +%% +%% Parameters: +%% U -- A node +%% Vs -- Nodes to remove edges to +%% Adj_list -- Old adjacency lists +%% +%% Returns: +%% An updated adj_list data-structure +%% +%%---------------------------------------------------------------------- + +%% remove_edges(_, [], Adj_list) -> Adj_list; +remove_edges(U, Vs, Adj_list) when is_list(Vs), is_integer(U) -> + hipe_vectors:set(Adj_list, U, hipe_vectors:get(Adj_list, U) -- Vs). + +%%---------------------------------------------------------------------- +%% Function: remove_edge +%% +%% Description: Removes an edge between two nodes +%% +%% Parameters: +%% U -- A node +%% V -- Another node +%% Adj_list -- Old adjacency lists +%% +%% Returns: +%% New adjacency lists with (U and V not connected) +%% +%%---------------------------------------------------------------------- + +remove_edge(U, U, Adj_list) -> Adj_list; +remove_edge(U, V, Adj_list) when is_integer(U), is_integer(V) -> + remove_edges(U, [V], Adj_list). + +%%---------------------------------------------------------------------- +%% Function: edges +%% +%% Description: Tells where the edges of a node go +%% +%% Parameters: +%% U -- A node +%% Adj_list -- Adjacency lists +%% +%% Returns: +%% The set of nodes connected to U +%% +%%---------------------------------------------------------------------- + +edges(U, Adj_list) -> + hipe_vectors:get(Adj_list, U). diff --git a/lib/hipe/regalloc/hipe_amd64_specific.erl b/lib/hipe/regalloc/hipe_amd64_specific.erl new file mode 100644 index 0000000000..91a8c7253a --- /dev/null +++ b/lib/hipe/regalloc/hipe_amd64_specific.erl @@ -0,0 +1,20 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2004-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +-define(HIPE_AMD64, true). +-include("hipe_x86_specific.erl"). diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl new file mode 100644 index 0000000000..5654455b44 --- /dev/null +++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl @@ -0,0 +1,175 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2004-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_amd64_specific_sse2). + +-export([number_of_temporaries/1]). + +% The following exports are used as M:F(...) calls from other modules; +%% e.g. hipe_amd64_ra_ls. +-export([analyze/1, + bb/2, + args/1, + labels/1, + livein/2, + liveout/2, + uses/1, + defines/1, + def_use/1, + is_arg/1, %% used by hipe_ls_regalloc + is_move/1, + is_fixed/1, %% used by hipe_graph_coloring_regalloc + is_global/1, + is_precoloured/1, + reg_nr/1, + non_alloc/1, + allocatable/0, + physical_name/1, + all_precoloured/0, + new_spill_index/1, %% used by hipe_ls_regalloc + var_range/1, + breadthorder/1, + postorder/1, + reverse_postorder/1]). + +%% callbacks for hipe_regalloc_loop +-export([defun_to_cfg/1, + check_and_rewrite/2]). + +%%---------------------------------------------------------------------------- + +-include("../flow/cfg.hrl"). + +%%---------------------------------------------------------------------------- + +defun_to_cfg(Defun) -> + hipe_x86_cfg:init(Defun). + +check_and_rewrite(Defun, Coloring) -> + hipe_amd64_ra_sse2_postconditions:check_and_rewrite(Defun, Coloring). + +reverse_postorder(CFG) -> + hipe_x86_cfg:reverse_postorder(CFG). + +breadthorder(CFG) -> + hipe_x86_cfg:breadthorder(CFG). + +postorder(CFG) -> + hipe_x86_cfg:postorder(CFG). + +is_global(_Reg) -> + false. + +is_fixed(_Reg) -> + false. + +is_arg(_Reg) -> + false. + +-spec args(#cfg{}) -> []. +args(_CFG) -> + []. + +non_alloc(_) -> + []. + +%% Liveness stuff + +analyze(CFG) -> + hipe_amd64_liveness:analyze(CFG). + +livein(Liveness, L) -> + [X || X <- hipe_amd64_liveness:livein(Liveness, L), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double']. + +liveout(BB_in_out_liveness, Label) -> + [X || X <- hipe_amd64_liveness:liveout(BB_in_out_liveness, Label), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double']. + +%% Registers stuff + +allocatable() -> + hipe_amd64_registers:allocatable_sse2(). + +all_precoloured() -> + allocatable(). + +is_precoloured(Reg) -> + lists:member(Reg,all_precoloured()). + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_x86_cfg:labels(CFG). + +var_range(_CFG) -> + hipe_gensym:var_range(x86). + +-spec number_of_temporaries(#cfg{}) -> non_neg_integer(). +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(x86), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG, L) -> + hipe_x86_cfg:bb(CFG, L). + +%% AMD64 stuff + +def_use(Instruction) -> + {[X || X <- hipe_amd64_defuse:insn_def(Instruction), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double'], + [X || X <- hipe_amd64_defuse:insn_use(Instruction), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double'] + }. + +uses(I) -> + [X || X <- hipe_amd64_defuse:insn_use(I), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double']. + +defines(I) -> + [X || X <- hipe_amd64_defuse:insn_def(I), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double']. + +is_move(Instruction) -> + case hipe_x86:is_fmove(Instruction) of + true -> + Src = hipe_x86:fmove_src(Instruction), + Dst = hipe_x86:fmove_dst(Instruction), + hipe_x86:is_temp(Src) andalso hipe_x86:temp_is_allocatable(Src) + andalso hipe_x86:is_temp(Dst) andalso hipe_x86:temp_is_allocatable(Dst); + false -> false + end. + +reg_nr(Reg) -> + hipe_x86:temp_reg(Reg). + +-spec new_spill_index(non_neg_integer()) -> pos_integer(). +new_spill_index(SpillIndex) when is_integer(SpillIndex) -> + SpillIndex + 1. diff --git a/lib/hipe/regalloc/hipe_amd64_specific_x87.erl b/lib/hipe/regalloc/hipe_amd64_specific_x87.erl new file mode 100644 index 0000000000..b5e8253ae1 --- /dev/null +++ b/lib/hipe/regalloc/hipe_amd64_specific_x87.erl @@ -0,0 +1,20 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2004-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +-define(HIPE_AMD64, true). +-include("hipe_x86_specific_x87.erl"). diff --git a/lib/hipe/regalloc/hipe_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl new file mode 100644 index 0000000000..246095e926 --- /dev/null +++ b/lib/hipe/regalloc/hipe_arm_specific.erl @@ -0,0 +1,168 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2005-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_arm_specific). + +%% for hipe_coalescing_regalloc: +-export([number_of_temporaries/1 + ,analyze/1 + ,labels/1 + ,all_precoloured/0 + ,bb/2 + ,liveout/2 + ,reg_nr/1 + ,def_use/1 + ,is_move/1 + ,is_precoloured/1 + ,var_range/1 + ,allocatable/0 + ,non_alloc/1 + ,physical_name/1 + ,reverse_postorder/1 + ,livein/2 + ,uses/1 + ,defines/1 + ]). + +%% for hipe_graph_coloring_regalloc: +-export([is_fixed/1]). + +%% for hipe_ls_regalloc: +-export([args/1, is_arg/1, is_global/1, new_spill_index/1]). +-export([breadthorder/1, postorder/1]). + +%% callbacks for hipe_regalloc_loop +-export([defun_to_cfg/1, + check_and_rewrite/2]). + +defun_to_cfg(Defun) -> + hipe_arm_cfg:init(Defun). + +check_and_rewrite(Defun, Coloring) -> + hipe_arm_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). + +reverse_postorder(CFG) -> + hipe_arm_cfg:reverse_postorder(CFG). + +non_alloc(CFG) -> + non_alloc(hipe_arm_registers:nr_args(), hipe_arm_cfg:params(CFG)). + +%% same as hipe_arm_frame:fix_formals/2 +non_alloc(0, Rest) -> Rest; +non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); +non_alloc(_, []) -> []. + +%% Liveness stuff + +analyze(CFG) -> + hipe_arm_liveness_gpr:analyse(CFG). + +livein(Liveness,L) -> + [X || X <- hipe_arm_liveness_gpr:livein(Liveness,L), + hipe_arm:temp_is_allocatable(X)]. + +liveout(BB_in_out_liveness,Label) -> + [X || X <- hipe_arm_liveness_gpr:liveout(BB_in_out_liveness,Label), + hipe_arm:temp_is_allocatable(X)]. + +%% Registers stuff + +allocatable() -> + hipe_arm_registers:allocatable_gpr(). + +all_precoloured() -> + hipe_arm_registers:all_precoloured(). + +is_precoloured(Reg) -> + hipe_arm_registers:is_precoloured_gpr(Reg). + +is_fixed(R) -> + hipe_arm_registers:is_fixed(R). + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_arm_cfg:labels(CFG). + +var_range(_CFG) -> + hipe_gensym:var_range(arm). + +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(arm), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG,L) -> + hipe_arm_cfg:bb(CFG,L). + +%% ARM stuff + +def_use(Instruction) -> + {defines(Instruction), uses(Instruction)}. + +uses(I) -> + [X || X <- hipe_arm_defuse:insn_use_gpr(I), + hipe_arm:temp_is_allocatable(X)]. + +defines(I) -> + [X || X <- hipe_arm_defuse:insn_def_gpr(I), + hipe_arm:temp_is_allocatable(X)]. + +is_move(Instruction) -> + case hipe_arm:is_pseudo_move(Instruction) of + true -> + Dst = hipe_arm:pseudo_move_dst(Instruction), + case hipe_arm:temp_is_allocatable(Dst) of + false -> false; + _ -> + Src = hipe_arm:pseudo_move_src(Instruction), + hipe_arm:temp_is_allocatable(Src) + end; + false -> false + end. + +reg_nr(Reg) -> + hipe_arm:temp_reg(Reg). + +%%% Linear Scan stuff + +new_spill_index(SpillIndex) when is_integer(SpillIndex) -> + SpillIndex+1. + +breadthorder(CFG) -> + hipe_arm_cfg:breadthorder(CFG). + +postorder(CFG) -> + hipe_arm_cfg:postorder(CFG). + +is_global(R) -> + R =:= hipe_arm_registers:temp1() orelse + R =:= hipe_arm_registers:temp2() orelse + R =:= hipe_arm_registers:temp3() orelse + hipe_arm_registers:is_fixed(R). + +is_arg(R) -> + hipe_arm_registers:is_arg(R). + +args(CFG) -> + hipe_arm_registers:args(hipe_arm_cfg:arity(CFG)). diff --git a/lib/hipe/regalloc/hipe_coalescing_regalloc.erl b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl new file mode 100644 index 0000000000..5a4b017c71 --- /dev/null +++ b/lib/hipe/regalloc/hipe_coalescing_regalloc.erl @@ -0,0 +1,1029 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%----------------------------------------------------------------------- +%% File : hipe_coalescing_regalloc.erl +%% Authors : Andreas Wallin +%% Thorild Selén +%% Ingemar Åberg +%% Purpose : Play paintball with registers on a target machine. We win +%% if they are all colored. This is an iterated coalescing +%% register allocator. +%% Created : 4 Mar 2000 +%%----------------------------------------------------------------------- + +-module(hipe_coalescing_regalloc). +-export([regalloc/5]). + +%%-ifndef(DEBUG). +%%-define(DEBUG,true). +%%-endif. +-include("../main/hipe.hrl"). + +%%----------------------------------------------------------------------- +%% Function: regalloc +%% +%% Description: Creates a K coloring for a function. +%% Parameters: +%% CFG -- A control flow graph +%% SpillIndex -- Last index of spill variable +%% SpillLimit -- Temporaries with numbers higher than this have +%% infinite spill cost. +%% Consider changing this to a set. +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% Coloring -- A coloring for specified CFG +%% SpillIndex0 -- A new spill index +%%----------------------------------------------------------------------- + +regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> + %% Build interference graph + ?debug_msg("Build IG\n", []), + IG = hipe_ig:build(CFG, Target), + %% io:format("IG: ~p\n", [IG]), + + ?debug_msg("Init\n", []), + Num_Temps = Target:number_of_temporaries(CFG), + ?debug_msg("Coalescing RA: num_temps = ~p~n", [Num_Temps]), + Allocatable = Target:allocatable(), + K = length(Allocatable), + All_colors = colset_from_list(Allocatable), + + %% Add registers with their own coloring + ?debug_msg("Moves\n", []), + Move_sets = hipe_moves:new(IG), + + ?debug_msg("Build Worklist\n", []), + Worklists = hipe_reg_worklists:new(IG, Target, CFG, Move_sets, K, Num_Temps), + Alias = initAlias(Num_Temps), + + ?debug_msg("Do coloring\n~p~n", [Worklists]), + {_IG0, Worklists0, _Moves0, Alias0} = + do_coloring(IG, Worklists, Move_sets, Alias, K, SpillLimit, Target), + %% io:format("SelStk0 ~w\n",[SelStk0]), + ?debug_msg("Init node sets\n", []), + Node_sets = hipe_node_sets:new(), + %% io:format("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]), + ?debug_msg("Default coloring\n", []), + {Color0,Node_sets1} = + defaultColoring(Target:all_precoloured(), + initColor(Num_Temps), Node_sets, Target), + + ?debug_msg("Assign colors\n", []), + {Color1,Node_sets2} = + assignColors(hipe_reg_worklists:stack(Worklists0), Node_sets1, Color0, + Alias0, All_colors, Target), + %% io:format("color0:~w\nColor1:~w\nNodes:~w\nNodes2:~w\nNum_Temps:~w\n",[Color0,Color1,Node_sets,Node_sets2,Num_Temps]), + + ?debug_msg("Build mapping ~p\n", [Node_sets2]), + Coloring = build_namelist(Node_sets2, SpillIndex, Alias0, Color1), + ?debug_msg("Coloring ~p\n", [Coloring]), + Coloring. + +%%---------------------------------------------------------------------- +%% Function: do_coloring +%% +%% Description: Create a coloring. That is, play paintball. +%% Parameters: +%% IG -- An interference graph +%% Worklists -- Worklists, that is simplify, spill and freeze +%% Moves -- Moves sets, that is coalesced, constrained +%% and so on. +%% Alias -- Tells if two temporaries can have their value +%% in the same register. +%% K -- Want to create a K coloring. +%% SpillLimit -- Try not to spill nodes that are above the spill limit. +%% +%% Returns: +%% IG -- Updated interference graph +%% Worklists -- Updated Worklists structure +%% Moves -- Updated Moves structure +%% Alias -- Updates Alias structure +%% +%%---------------------------------------------------------------------- + +do_coloring(IG, Worklists, Moves, Alias, K, SpillLimit, Target) -> + Simplify = not(hipe_reg_worklists:is_empty_simplify(Worklists)), + Coalesce = not(hipe_moves:is_empty_worklist(Moves)), + Freeze = not(hipe_reg_worklists:is_empty_freeze(Worklists)), + Spill = not(hipe_reg_worklists:is_empty_spill(Worklists)), + if Simplify =:= true -> + {IG0, Worklists0, Moves0} = + simplify(hipe_reg_worklists:simplify(Worklists), + IG, + Worklists, + Moves, + K), + do_coloring(IG0, Worklists0, Moves0, Alias, K, SpillLimit, Target); + Coalesce =:= true -> + {Moves0, IG0, Worklists0, Alias0} = + coalesce(Moves, IG, Worklists, Alias, K, Target), + do_coloring(IG0, Worklists0, Moves0, Alias0, K, SpillLimit, Target); + Freeze =:= true -> + {Worklists0,Moves0} = + freeze(K, Worklists, Moves, IG, Alias), + do_coloring(IG, Worklists0, Moves0, Alias, + K, SpillLimit, Target); + Spill =:= true -> + {Worklists0, Moves0} = + selectSpill(Worklists, Moves, IG, K, Alias, SpillLimit), + do_coloring(IG, Worklists0, Moves0, Alias, K, SpillLimit, Target); + true -> % Catchall case + {IG, Worklists, Moves, Alias} + end. + +%%---------------------------------------------------------------------- +%% Function: adjacent +%% +%% Description: Adjacent nodes that's not coalesced, on the stack or +%% precoloured. +%% Parameters: +%% Node -- Node that you want to adjacents of +%% IG -- The interference graph +%% +%% Returns: +%% A set with nodes/temporaries that are not coalesced, on the +%% stack or precoloured. +%%---------------------------------------------------------------------- + +adjacent(Node, IG, Worklists) -> + Adjacent_edges = hipe_ig:node_adj_list(Node, IG), + hipe_reg_worklists:non_stacked_or_coalesced_nodes(Adjacent_edges, Worklists). + +%%---------------------------------------------------------------------- +%% Function: simplify +%% +%% Description: Simplify graph by removing nodes of low degree. This +%% function simplifies all nodes it can at once. +%% Parameters: +%% [Node|Nodes] -- The simplify worklist +%% IG -- The interference graph +%% Worklists -- The worklists data-structure +%% Moves -- The moves data-structure +%% K -- Produce a K coloring +%% +%% Returns: +%% IG -- An updated interference graph +%% Worklists -- An updated worklists data-structure +%% Moves -- An updated moves data-structure +%%---------------------------------------------------------------------- + +simplify([], IG, Worklists, Moves, _K) -> + {IG, Worklists, Moves}; +simplify([Node|Nodes], IG, Worklists, Moves, K) -> + Worklists0 = hipe_reg_worklists:remove_simplify(Node, Worklists), + ?debug_msg("putting ~w on stack~n",[Node]), + Adjacent = adjacent(Node, IG, Worklists0), + Worklists01 = hipe_reg_worklists:push_stack(Node, Adjacent, Worklists0), + {New_ig, Worklists1, New_moves} = + decrement_degree(Adjacent, IG, Worklists01, Moves, K), + simplify(Nodes, New_ig, Worklists1, New_moves, K). + +%%---------------------------------------------------------------------- +%% Function: decrement_degree +%% +%% Description: Decrement the degree on a number of nodes/temporaries. +%% Parameters: +%% [Node|Nodes] -- Decrement degree on these nodes +%% IG -- The interference graph +%% Worklists -- The Worklists data structure +%% Moves -- The Moves data structure. +%% K -- We want to create a coloring with K colors +%% +%% Returns: +%% IG -- An updated interference graph (the degrees) +%% Worklists -- Updated Worklists. Changed if one degree goes +%% down to K. +%% Moves -- Updated Moves. Changed if a move related temporary +%% gets degree K. +%%---------------------------------------------------------------------- + +decrement_degree([], IG, Worklists, Moves, _K) -> + {IG, Worklists, Moves}; +decrement_degree([Node|Nodes], IG, Worklists, Moves, K) -> + PrevDegree = hipe_ig:get_node_degree(Node, IG), + IG0 = hipe_ig:dec_node_degree(Node, IG), + if PrevDegree =:= K -> + AdjList = hipe_ig:node_adj_list(Node, IG0), + %% Ok since Node (a) is still in IG, and (b) cannot be adjacent to itself + Moves00 = enable_moves_active_to_worklist(hipe_moves:node_movelist(Node, Moves), + Moves), + Moves0 = enable_moves(AdjList, Worklists, Moves00), + Worklists0 = hipe_reg_worklists:remove_spill(Node, Worklists), + case hipe_moves:move_related(Node, Moves0) of + true -> + Worklists1 = hipe_reg_worklists:add_freeze(Node, Worklists0), + decrement_degree(Nodes, IG0, Worklists1, Moves0, K); + _ -> + Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0), + decrement_degree(Nodes, IG0, Worklists1, Moves0, K) + end; + true -> + decrement_degree(Nodes, IG0, Worklists, Moves, K) + end. + +%%---------------------------------------------------------------------- +%% Function: enable_moves +%% +%% Description: Make (move-related) nodes that are not yet considered for +%% coalescing, ready for possible coalescing. +%% +%% Parameters: +%% [Node|Nodes] -- A list of move nodes +%% Moves -- The moves data-structure +%% +%% Returns: +%% An updated moves data-structure +%%---------------------------------------------------------------------- + +enable_moves([], _Worklists, Moves) -> Moves; +enable_moves([Node|Nodes], Worklists, Moves) -> + case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of + true -> enable_moves(Nodes, Worklists, Moves); + _ -> + %% moveList[n] suffices since we're checking for activeMoves membership + Node_moves = hipe_moves:node_movelist(Node, Moves), + New_moves = enable_moves_active_to_worklist(Node_moves, Moves), + enable_moves(Nodes, Worklists, New_moves) + end. + +%%---------------------------------------------------------------------- +%% Function: enable_moves_active_to_worklist +%% +%% Description: Make (move-related) nodes that are not yet considered for +%% coalescing, ready for possible coalescing. +%% +%% Parameters: +%% [Node|Nodes] -- A list of move nodes +%% Moves -- The moves data structure +%% +%% Returns: +%% An updated moves data structure +%%---------------------------------------------------------------------- + +enable_moves_active_to_worklist([], Moves) -> Moves; +enable_moves_active_to_worklist([Node|Nodes], Moves) -> + NewMoves = + case hipe_moves:member_active(Node, Moves) of + true -> + hipe_moves:add_worklist(Node, hipe_moves:remove_active(Node, Moves)); + _ -> + Moves + end, + enable_moves_active_to_worklist(Nodes, NewMoves). + +%% Build the namelists, these functions are fast hacks, they use knowledge +%% about data representation that they shouldn't know, bad abstraction. + +build_namelist(NodeSets, Index, Alias, Color) -> + ?debug_msg("Building mapping\n",[]), + ?debug_msg("Vector to list\n",[]), + AliasList = build_alias_list(aliasToList(Alias), + 0, %% The first temporary has index 0 + []), %% Accumulator + ?debug_msg("Alias list:~p\n",[AliasList]), + ?debug_msg("Coalesced\n",[]), + NL1 = build_coalescedlist(AliasList, Color, Alias, []), + ?debug_msg("Coalesced list:~p\n",[NL1]), + ?debug_msg("Regs\n",[]), + NL2 = build_reglist(hipe_node_sets:colored(NodeSets), Color, NL1), + ?debug_msg("Regs list:~p\n",[NL2]), + ?debug_msg("Spills\n",[]), + build_spillist(hipe_node_sets:spilled(NodeSets), Index, NL2). + +build_spillist([], Index, List) -> + {List,Index}; +build_spillist([Node|Nodes], Index, List) -> + ?debug_msg("[~p]: Spill ~p to ~p\n", [?MODULE,Node,Index]), + build_spillist(Nodes, Index+1, [{Node,{spill,Index}}|List]). + +build_coalescedlist([], _Color, _Alias, List) -> + List; +build_coalescedlist([Node|Ns], Color, Alias, List) when is_integer(Node) -> + ?debug_msg("Alias of ~p is ~p~n", [Node, getAlias(Node,Alias)]), + AC = getColor(getAlias(Node, Alias), Color), + build_coalescedlist(Ns, Color, Alias, [{Node,{reg,AC}}|List]). + +build_reglist([], _Color, List) -> + List; +build_reglist([Node|Ns], Color, List) -> + build_reglist(Ns, Color, [{Node,{reg,getColor(Node,Color)}}|List]). + +build_alias_list([], _I, List) -> + List; +build_alias_list([Alias|Aliases], I, List) when is_integer(Alias) -> + build_alias_list(Aliases, I+1, [I|List]); +build_alias_list([_Alias|Aliases], I, List) -> + build_alias_list(Aliases, I+1, List). + +%%---------------------------------------------------------------------- +%% Function: assignColors +%% +%% Description: Tries to assign colors to nodes in a stack. +%% Parameters: +%% Stack -- The SelectStack built by the Select function, +%% this stack contains tuples in the form {Node,Edges} +%% where Node is the Node number and Edges is an ordset +%% containing the numbers of all the adjacent nodes. +%% NodeSets -- This is a record containing all the different node +%% sets that are used in the register allocator. +%% Alias -- This is a mapping from nodes to nodes, if a node has +%% been coalesced this mapping shows the alias for that +%% node. +%% AllColors -- This is an ordset containing all the available colors +%% +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% Color -- A mapping from nodes to their respective color. +%% NodeSets -- The updated node sets. +%%---------------------------------------------------------------------- + +assignColors(Stack, NodeSets, Color, Alias, AllColors, Target) -> + case Stack of + [] -> + {Color,NodeSets}; + [{Node,Edges}|Stack1] -> + ?debug_msg("Coloring Node: ~p~n",[Node]), + ?IF_DEBUG(lists:foreach(fun (_E) -> + ?msg(" Edge ~w-><~w>->~w~n", + begin A = getAlias(_E,Alias), + [_E,A,getColor(A,Color)] + end) + end, Edges), + []), + %% When debugging, check that Node isn't precoloured. + OkColors = findOkColors(Edges, AllColors, Color, Alias), + case colset_is_empty(OkColors) of + true -> % Spill case + NodeSets1 = hipe_node_sets:add_spilled(Node, NodeSets), + assignColors(Stack1, NodeSets1, Color, Alias, AllColors, Target); + false -> % Colour case + Col = colset_smallest(OkColors), + NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), + Color1 = setColor(Node, Target:physical_name(Col), Color), + assignColors(Stack1, NodeSets1, Color1, Alias, AllColors, Target) + end + end. + +%%--------------------------------------------------------------------- +%% Function: defaultColoring +%% +%% Description: Make the default coloring +%% Parameters: +%% Regs -- The list of registers to be default colored +%% Color -- The color mapping that shall be changed +%% NodeSets -- The node sets that shall be updated +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% NewColor -- The updated color mapping +%% NewNodeSets -- The updated node sets +%%--------------------------------------------------------------------- + +defaultColoring([], Color, NodeSets, _Target) -> + {Color,NodeSets}; +defaultColoring([Reg|Regs], Color, NodeSets, Target) -> + Color1 = setColor(Reg,Target:physical_name(Reg), Color), + NodeSets1 = hipe_node_sets:add_colored(Reg, NodeSets), + defaultColoring(Regs, Color1, NodeSets1, Target). + +%% Find the colors that are OK for a node with certain edges. + +findOkColors(Edges, AllColors, Color, Alias) -> + find(Edges, AllColors, Color, Alias). + +%% Find all the colors of the nodes in the list [Node|Nodes] and remove them +%% from the set OkColors, when the list is empty, return OkColors. + +find([], OkColors, _Color, _Alias) -> + OkColors; +find([Node0|Nodes], OkColors, Color, Alias) -> + Node = getAlias(Node0, Alias), + case getColor(Node, Color) of + [] -> + find(Nodes, OkColors, Color, Alias); + Col -> + OkColors1 = colset_del_element(Col, OkColors), + find(Nodes, OkColors1, Color, Alias) + end. + +%%% +%%% ColSet -- ADT for the set of available colours while +%%% assigning colours. +%%% +-ifdef(notdef). % old ordsets-based implementation +colset_from_list(Allocatable) -> + ordsets:from_list(Allocatable). + +colset_del_element(Colour, ColSet) -> + ordsets:del_element(Colour, ColSet). + +colset_is_empty(ColSet) -> + case ColSet of + [] -> true; + [_|_] -> false + end. + +colset_smallest([Colour|_]) -> + Colour. +-endif. + +-ifdef(notdef). % new gb_sets-based implementation +colset_from_list(Allocatable) -> + gb_sets:from_list(Allocatable). + +colset_del_element(Colour, ColSet) -> + %% Must use gb_sets:delete_any/2 since gb_sets:del_element/2 + %% fails if the element isn't present. Bummer. + gb_sets:delete_any(Colour, ColSet). + +colset_is_empty(ColSet) -> + gb_sets:is_empty(ColSet). + +colset_smallest(ColSet) -> + gb_sets:smallest(ColSet). +-endif. + +%%-ifdef(notdef). % new bitmask-based implementation +colset_from_list(Allocatable) -> + colset_from_list(Allocatable, 0). + +colset_from_list([], ColSet) -> + ColSet; +colset_from_list([Colour|Allocatable], ColSet) -> + colset_from_list(Allocatable, ColSet bor (1 bsl Colour)). + +colset_del_element(Colour, ColSet) -> + ColSet band bnot(1 bsl Colour). + +colset_is_empty(0) -> true; +colset_is_empty(_) -> false. + +colset_smallest(ColSet) -> + bitN_log2(ColSet band -ColSet, 0). + +bitN_log2(BitN, ShiftN) -> + if BitN > 16#ffff -> + bitN_log2(BitN bsr 16, ShiftN + 16); + true -> + ShiftN + hweight16(BitN - 1) + end. + +hweight16(W) -> + Res1 = ( W band 16#5555) + (( W bsr 1) band 16#5555), + Res2 = (Res1 band 16#3333) + ((Res1 bsr 2) band 16#3333), + Res3 = (Res2 band 16#0F0F) + ((Res2 bsr 4) band 16#0F0F), + (Res3 band 16#00FF) + ((Res3 bsr 8) band 16#00FF). +%%-endif. + +%%% +%%% Colour ADT providing a partial mapping from nodes to colours. +%%% + +initColor(NrNodes) -> + {colmap, hipe_bifs:array(NrNodes, [])}. + +getColor(Node, {colmap, ColMap}) -> + hipe_bifs:array_sub(ColMap, Node). + +setColor(Node, Colour, {colmap, ColMap} = Col) -> + hipe_bifs:array_update(ColMap, Node, Colour), + Col. + +%%% +%%% Alias ADT providing a partial mapping from nodes to nodes. +%%% + +initAlias(NrNodes) -> + {alias, hipe_bifs:array(NrNodes, [])}. + +getAlias(Node, {alias, AliasMap} = Alias) -> + case hipe_bifs:array_sub(AliasMap, Node) of + [] -> + Node; + AliasNode -> + getAlias(AliasNode, Alias) + end. + +setAlias(Node, AliasNode, {alias, AliasMap} = Alias) -> + hipe_bifs:array_update(AliasMap, Node, AliasNode), + Alias. + +aliasToList({alias,AliasMap}) -> + aliasToList(AliasMap, hipe_bifs:array_length(AliasMap), []). + +aliasToList(AliasMap, I1, Tail) -> + I0 = I1 - 1, + if I0 >= 0 -> + aliasToList(AliasMap, I0, [hipe_bifs:array_sub(AliasMap, I0)|Tail]); + true -> + Tail + end. + +%%---------------------------------------------------------------------- +%% Function: coalesce +%% +%% Description: Coalesces nodes in worklist +%% Parameters: +%% Moves -- Current move information +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Alias -- Current aliases for temporaries +%% K -- Number of registers +%% +%% Returns: +%% {Moves, IG, Worklists, Alias} +%% (Updated versions of above structures, after coalescing) +%%---------------------------------------------------------------------- + +coalesce(Moves, IG, Worklists, Alias, K, Target) -> + case hipe_moves:worklist_get_and_remove(Moves) of + {[],Moves0} -> + %% Moves marked for removal from worklistMoves by FreezeMoves() + %% are removed by worklist_get_and_remove(). This case is unlikely, + %% but can occur if only stale moves remain in worklistMoves. + {Moves0,IG,Worklists,Alias}; + {Move,Moves0} -> + {Dest,Source} = hipe_moves:get_move(Move, Moves0), + ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), + Alias_src = getAlias(Source, Alias), + Alias_dst = getAlias(Dest, Alias), + {U,V} = case Target:is_precoloured(Alias_dst) of + true -> {Alias_dst, Alias_src}; + false -> {Alias_src, Alias_dst} + end, + %% When debugging, check that neither V nor U is on the stack. + if U =:= V -> + Moves1 = Moves0, % drop coalesced move Move + Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), + {Moves1, IG, Worklists1, Alias}; + true -> + case (Target:is_precoloured(V) orelse + hipe_ig:nodes_are_adjacent(U, V, IG)) of + true -> + Moves1 = Moves0, % drop constrained move Move + Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), + Worklists2 = add_worklist(Worklists1, V, K, Moves1, IG, Target), + {Moves1, IG, Worklists2, Alias}; + false -> + case (case Target:is_precoloured(U) of + true -> + AdjV = hipe_ig:node_adj_list(V, IG), + all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); + false -> + AdjV = hipe_ig:node_adj_list(V, IG), + AdjU = hipe_ig:node_adj_list(U, IG), + conservative(AdjU, AdjV, U, Worklists, IG, K) + end) of + true -> + Moves1 = Moves0, % drop coalesced move Move + {IG1,Worklists1,Moves2,Alias1} = + combine(U, V, IG, Worklists, Moves1, Alias, K, Target), + Worklists2 = add_worklist(Worklists1, U, K, Moves2, IG1, Target), + {Moves2, IG1, Worklists2, Alias1}; + false -> + Moves1 = hipe_moves:add_active(Move, Moves0), + {Moves1, IG, Worklists, Alias} + end + end + end + end. + +%%---------------------------------------------------------------------- +%% Function: add_worklist +%% +%% Description: Builds new worklists where U is transferred from freeze +%% to simplify, if possible +%% +%% Parameters: +%% Worklists -- Current worklists +%% U -- Node to operate on +%% K -- Number of registers +%% Moves -- Current move information +%% IG -- Interference graph +%% Target -- The containing the target-specific functions +%% +%% Returns: +%% Worklists (updated) +%%---------------------------------------------------------------------- + +add_worklist(Worklists, U, K, Moves, IG, Target) -> + case (not(Target:is_precoloured(U)) + andalso not(hipe_moves:move_related(U, Moves)) + andalso (hipe_ig:is_trivially_colourable(U, K, IG))) of + true -> + hipe_reg_worklists:transfer_freeze_simplify(U, Worklists); + false -> + Worklists + end. + +%%---------------------------------------------------------------------- +%% Function: combine +%% +%% Description: Combines two nodes into one (used when coalescing) +%% +%% Parameters: +%% U -- First node to operate on +%% V -- Second node to operate on +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Moves -- Current move information +%% Alias -- Current aliases for temporaries +%% K -- Number of registers +%% +%% Returns: +%% {IG, Worklists, Moves, Alias} (updated) +%%---------------------------------------------------------------------- + +combine(U, V, IG, Worklists, Moves, Alias, K, Target) -> + Worklists1 = case hipe_reg_worklists:member_freeze(V, Worklists) of + true -> hipe_reg_worklists:remove_freeze(V, Worklists); + false -> hipe_reg_worklists:remove_spill(V, Worklists) + end, + Worklists11 = hipe_reg_worklists:add_coalesced(V, Worklists1), + + ?debug_msg("Coalescing ~p and ~p to ~p~n",[V,U,U]), + + Alias1 = setAlias(V, U, Alias), + + %% Typo in published algorithm: s/nodeMoves/moveList/g to fix. + %% XXX: moveList[u] \union moveList[v] OR NodeMoves(u) \union NodeMoves(v) ??? + %% XXX: NodeMoves() is correct, but unnecessarily strict. The ordsets:union + %% constrains NodeMoves() to return an ordset. + Moves1 = hipe_moves:update_movelist(U, + ordsets:union(hipe_moves:node_moves(U, Moves), + hipe_moves:node_moves(V, Moves)), + Moves), + %% Missing in published algorithm. From Tiger book Errata. + Moves2 = enable_moves_active_to_worklist(hipe_moves:node_movelist(V, Moves1), Moves1), + AdjV = hipe_ig:node_adj_list(V, IG), + + {IG1, Worklists2, Moves3} = + combine_edges(AdjV, U, IG, Worklists11, Moves2, K, Target), + + New_worklists = case (not(hipe_ig:is_trivially_colourable(U, K, IG1)) + andalso + hipe_reg_worklists:member_freeze(U, Worklists2)) of + true -> + hipe_reg_worklists:transfer_freeze_spill(U, Worklists2); + false -> Worklists2 + end, + {IG1, New_worklists, Moves3, Alias1}. + +%%---------------------------------------------------------------------- +%% Function: combine_edges +%% +%% Description: For each node in a list, make an edge between that node +%% and node U, and decrement its degree by 1 +%% (Used when two nodes are coalesced, to connect all nodes +%% adjacent to one node to the other node) +%% +%% Parameters: +%% [T|Ts] -- List of nodes to make edges to +%% U -- Node to make edges from +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Moves -- Current move information +%% K -- Number of registers +%% +%% Returns: +%% {IG, Worklists, Moves} (updated) +%%---------------------------------------------------------------------- + +combine_edges([], _U, IG, Worklists, Moves, _K, _Target) -> + {IG, Worklists, Moves}; +combine_edges([T|Ts], U, IG, Worklists, Moves, K, Target) -> + case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of + true -> combine_edges(Ts, U, IG, Worklists, Moves, K, Target); + _ -> + %% XXX: The issue below occurs because the T->V edge isn't removed. + %% This causes adjList[T] to contain stale entries, to possibly grow + %% (if T isn't already adjacent to U), and degree[T] to possibly + %% increase (again, if T isn't already adjacent to U). + %% The decrement_degree() call repairs degree[T] but not adjList[T]. + %% It would be better to physically replace T->V with T->U, and only + %% decrement_degree(T) if T->U already existed. + %% + %% add_edge() may change a low-degree move-related node to be of + %% significant degree. In this case the node belongs in the spill + %% worklist, and that's where decrement_degree() expects to find it. + %% This issue is not covered in the published algorithm. + OldDegree = hipe_ig:get_node_degree(T, IG), + IG1 = hipe_ig:add_edge(T, U, IG, Target), + NewDegree = hipe_ig:get_node_degree(T, IG1), + Worklists0 = + if NewDegree =:= K, OldDegree =:= K-1 -> + %% io:format("~w:combine_edges(): repairing worklist membership for node ~w\n", [?MODULE,T]), + %% The node T must be on the freeze worklist: + %% 1. Since we're coalescing, the simplify worklist must have been + %% empty when combine_edges() started. + %% 2. decrement_degree() may put the node T back on the simplify + %% worklist, but that occurs after the worklists repair step. + %% 3. There are no duplicates among the edges. + Worklists00 = hipe_reg_worklists:remove_freeze(T, Worklists), + hipe_reg_worklists:add_spill(T, Worklists00); + true -> + Worklists + end, + {IG2, Worklists1, Moves1} = + decrement_degree([T], IG1, Worklists0, Moves, K), + combine_edges(Ts, U, IG2, Worklists1, Moves1, K, Target) + end. + +%%---------------------------------------------------------------------- +%% Function: ok +%% +%% Description: Checks if a node T is suitable to coalesce with R +%% +%% Parameters: +%% T -- Node to test +%% R -- Other node to test +%% IG -- Interference graph +%% K -- Number of registers +%% Target -- The module containing the target-specific functions +%% +%% Returns: +%% true iff coalescing is OK +%%---------------------------------------------------------------------- + +ok(T, R, IG, K, Target) -> + ((hipe_ig:is_trivially_colourable(T, K, IG)) + orelse Target:is_precoloured(T) + orelse hipe_ig:nodes_are_adjacent(T, R, IG)). + +%%---------------------------------------------------------------------- +%% Function: all_ok +%% +%% Description: True iff, for every T in the list, OK(T,U) +%% +%% Parameters: +%% [T|Ts] -- Nodes to test +%% U -- Node to test for coalescing +%% IG -- Interference graph +%% K -- Number of registers +%% Target -- The module containing the target-specific functions +%% +%% Returns: +%% true iff coalescing is OK for all nodes in the list +%%---------------------------------------------------------------------- + +all_adjacent_ok([], _U, _Worklists, _IG, _K, _Target) -> true; +all_adjacent_ok([T|Ts], U, Worklists, IG, K, Target) -> + case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of + true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target); + _ -> + %% 'andalso' does not preserve tail-recursion + case ok(T, U, IG, K, Target) of + true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target); + false -> false + end + end. + +%%---------------------------------------------------------------------- +%% Function: conservative +%% +%% Description: Checks if nodes can be safely coalesced according to +%% the Briggs' conservative coalescing heuristic +%% +%% Parameters: +%% Nodes -- Adjacent nodes +%% IG -- Interference graph +%% K -- Number of registers +%% +%% Returns: +%% true iff coalescing is safe +%%---------------------------------------------------------------------- + +conservative(AdjU, AdjV, U, Worklists, IG, K) -> + conservative_countU(AdjU, AdjV, U, Worklists, IG, K, 0). + +%%---------------------------------------------------------------------- +%% Function: conservative_count +%% +%% Description: Counts degrees for conservative (Briggs' heuristic) +%% +%% Parameters: +%% Nodes -- (Remaining) adjacent nodes +%% IG -- Interference graph +%% K -- Number of registers +%% Cnt -- Accumulator for counting +%% +%% Returns: +%% Final value of accumulator +%%---------------------------------------------------------------------- + +conservative_countU([], AdjV, U, Worklists, IG, K, Cnt) -> + conservative_countV(AdjV, U, Worklists, IG, K, Cnt); +conservative_countU([Node|AdjU], AdjV, U, Worklists, IG, K, Cnt) -> + case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of + true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt); + _ -> + case hipe_ig:is_trivially_colourable(Node, K, IG) of + true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt); + _ -> + Cnt1 = Cnt + 1, + if Cnt1 < K -> + conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt1); + true -> false + end + end + end. + +conservative_countV([], _U, _Worklists, _IG, _K, _Cnt) -> true; +conservative_countV([Node|AdjV], U, Worklists, IG, K, Cnt) -> + case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of + true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); + _ -> + case hipe_ig:nodes_are_adjacent(Node, U, IG) of + true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); + _ -> + case hipe_ig:is_trivially_colourable(Node, K, IG) of + true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); + _ -> + Cnt1 = Cnt + 1, + if Cnt1 < K -> + conservative_countV(AdjV, U, Worklists, IG, K, Cnt1); + true -> false + end + end + end + end. + +%%--------------------------------------------------------------------- +%% Function: selectSpill +%% +%% Description: Select the node to spill and spill it +%% Parameters: +%% WorkLists -- A datatype containing the different worklists +%% Moves -- A datatype containing the move sets +%% IG -- The interference graph +%% K -- The number of available registers +%% Alias -- The alias mapping +%% SpillLimit -- Try not to spill any nodes above the spill limit +%% +%% Returns: +%% WorkLists -- The updated worklists +%% Moves -- The updated moves +%%--------------------------------------------------------------------- + +selectSpill(WorkLists, Moves, IG, K, Alias, SpillLimit) -> + [CAR|CDR] = hipe_reg_worklists:spill(WorkLists), + + SpillCost = getCost(CAR, IG, SpillLimit), + M = findCheapest(CDR, IG, SpillCost, CAR, SpillLimit), + + WorkLists1 = hipe_reg_worklists:remove_spill(M, WorkLists), + %% The published algorithm adds M to the simplify worklist + %% before the freezeMoves() call. That breaks the worklist + %% invariants, which is why the order is switched here. + {WorkLists2,Moves1} = freezeMoves(M, K, WorkLists1, Moves, IG, Alias), + WorkLists3 = hipe_reg_worklists:add_simplify(M, WorkLists2), + {WorkLists3,Moves1}. + +%% Find the node that is cheapest to spill + +findCheapest([], _IG, _Cost, Cheapest, _SpillLimit) -> + Cheapest; +findCheapest([Node|Nodes], IG, Cost, Cheapest, SpillLimit) -> + ThisCost = getCost(Node, IG, SpillLimit), + case ThisCost < Cost of + true -> + findCheapest(Nodes, IG, ThisCost, Node, SpillLimit); + false -> + findCheapest(Nodes, IG, Cost, Cheapest, SpillLimit) + end. + +%% Get the cost for spilling a certain node, node numbers above the spill +%% limit are extremely expensive. + +getCost(Node, IG, SpillLimit) -> + case Node > SpillLimit of + true -> inf; + false -> hipe_ig:node_spill_cost(Node, IG) + end. + +%%---------------------------------------------------------------------- +%% Function: freeze +%% +%% Description: When both simplifying and coalescing is impossible we +%% rather freezes a node in stead of spilling, this function +%% selects a node for freezing (it just picks the first one in +%% the list) +%% +%% Parameters: +%% K -- The number of available registers +%% WorkLists -- A datatype containing the different worklists +%% Moves -- A datatype containing the different movelists +%% IG -- Interference graph +%% Alias -- An alias mapping, shows the alias of all coalesced +%% nodes +%% +%% Returns: +%% WorkLists -- The updated worklists +%% Moves -- The updated movelists +%%---------------------------------------------------------------------- + +freeze(K, WorkLists, Moves, IG, Alias) -> + [U|_] = hipe_reg_worklists:freeze(WorkLists), % Smarter routine? + ?debug_msg("freezing node ~p~n", [U]), + WorkLists0 = hipe_reg_worklists:remove_freeze(U, WorkLists), + %% The published algorithm adds U to the simplify worklist + %% before the freezeMoves() call. That breaks the worklist + %% invariants, which is why the order is switched here. + {WorkLists1,Moves1} = freezeMoves(U,K,WorkLists0,Moves,IG,Alias), + WorkLists2 = hipe_reg_worklists:add_simplify(U, WorkLists1), + {WorkLists2,Moves1}. + +%%---------------------------------------------------------------------- +%% Function: freezeMoves +%% +%% Description: Make all move related interferences for a certain node +%% into ordinary interference arcs. +%% +%% Parameters: +%% U -- The node we want to freeze +%% K -- The number of available registers +%% WorkLists -- A datatype containing the different worklists +%% Moves -- A datatype containing the different movelists +%% IG -- Interference graph +%% Alias -- An alias mapping, shows the alias of all coalesced +%% nodes +%% +%% Returns: +%% WorkLists -- The updated worklists +%% Moves -- The updated movelists +%%---------------------------------------------------------------------- + +freezeMoves(U, K, WorkLists, Moves, IG, Alias) -> + Nodes = hipe_moves:node_moves(U, Moves), + freezeEm(U, Nodes, K, WorkLists, Moves, IG, Alias). + +%% Find what the other value in a copy instruction is, return false if +%% the instruction isn't a move with the first argument in it. + +moves(U, Move, Alias, Moves) -> + {X,Y} = hipe_moves:get_move(Move, Moves), + %% The old code (which followed the published algorithm) did + %% not follow aliases before looking for "the other" node. + %% This caused moves() to skip some moves, making some nodes + %% still move-related after freezeMoves(). These move-related + %% nodes were then added to the simplify worklist (by freeze() + %% or selectSpill()), breaking the worklist invariants. Nodes + %% already simplified appeared in coalesce(), were re-added to + %% the simplify worklist by add_worklist(), simplified again, + %% and coloured multiple times by assignColors(). Ouch! + X1 = getAlias(X, Alias), + Y1 = getAlias(Y, Alias), + if U =:= X1 -> Y1; + U =:= Y1 -> X1; + true -> exit({?MODULE,moves}) % XXX: shouldn't happen + end. + +freezeEm(_U, [], _K, WorkLists, Moves, _IG, _Alias) -> + {WorkLists,Moves}; +freezeEm(U,[M|Ms], K, WorkLists, Moves, IG, Alias) -> + V = moves(U, M, Alias, Moves), + {WorkLists2,Moves2} = freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias), + freezeEm(U, Ms, K, WorkLists2, Moves2, IG, Alias). + +freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias) -> + case hipe_moves:member_active(M, Moves) of + true -> + Moves1 = hipe_moves:remove_active(M, Moves), + freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias); + false -> + Moves1 = hipe_moves:remove_worklist(M, Moves), + freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias) + end. + +freezeEm3(_U, V, _M, K, WorkLists, Moves, IG, _Alias) -> + Moves1 = Moves, % drop frozen move M + V1 = V, % getAlias(V,Alias), + %% "not MoveRelated(v)" is cheaper than "NodeMoves(v) = {}" + case ((not hipe_moves:move_related(V1, Moves1)) andalso + hipe_ig:is_trivially_colourable(V1, K, IG)) of + true -> + ?debug_msg("freezing move to ~p~n", [V]), + Worklists1 = hipe_reg_worklists:transfer_freeze_simplify(V1, WorkLists), + {Worklists1, Moves1}; + false -> + {WorkLists, Moves1} + end. diff --git a/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl new file mode 100644 index 0000000000..ac555b933c --- /dev/null +++ b/lib/hipe/regalloc/hipe_graph_coloring_regalloc.erl @@ -0,0 +1,806 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%@doc +%% GRAPH COLORING REGISTER ALLOCATOR +%% +%% A simple graph coloring register allocator: +%% +%% - build interference graph + estimate spill costs +%% - simplify graph (push on stack + spill) +%% - select colors +%% +%% Emits a coloring: a list of {TempName,Location} +%% where Location is {reg,N} or {spill,M} +%% and {reg,N} denotes some register N +%% and {spill,M} denotes the Mth spilled node +%% You have to figure out how to rewrite the code yourself. +%% +%% This version uses vectors rather than hash tables, and uses +%% faster algorithms since all vars are known at the start. +%% The result should be considerably quicker than earlier versions. +%% +%% Deficiencies: +%% - no renaming (to reduce unnecessary register pressure) +%% - spill costs are naive (should use better; e.g., exec.estimates) +%% - no biased coloring (which coalesces moves) +%% - no live range splitting (possibly not critical) +%% +%% *** NOTE *** +%% Uses apply for target specific functions, takes the module name as +%% argument. This target specific module should implement all target +%% specific functions, see the end of the file. +%% + +-module(hipe_graph_coloring_regalloc). +-export([regalloc/5]). + +%%-ifndef(DO_ASSERT). +%%-define(DO_ASSERT, true). +%%-endif. + +%%-ifndef(DEBUG). +%%-define(DEBUG,0). +%%-endif. +-include("../main/hipe.hrl"). + +%% Define these as 'ok' or 'report(X,Y)' depending on how much output you want. +-define(report0(X,Y), ?IF_DEBUG_LEVEL(0,?msg(X, Y),ok)). +-define(report(X,Y), ?IF_DEBUG_LEVEL(1,?msg(X, Y),ok)). +-define(report2(X,Y), ?IF_DEBUG_LEVEL(2,?msg(X, Y),ok)). +-define(report3(X,Y), ?IF_DEBUG_LEVEL(3,?msg(X, Y),ok)). + +%% Given CFG and number of colors K, produce a coloring list +%% of items {reg,N} (0 =< N =< K) and {spill,M}, where M is +%% an index denoting 'a location'. +%% (You might use it as a stack index, perhaps.) +%% +%% You can in principle delete check_coloring/2; it merely checks +%% that the coloring agrees with the interference graph (that is, that +%% no neighbors have the same register or spill location). + +%% @spec regalloc(#cfg{}, non_neg_fixnum(), non_neg_fixnum(), atom(), list()) -> {, non_neg_fixnum()} + +regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> + PhysRegs = Target:allocatable(), + ?report2("building IG~n", []), + {IG, Spill} = build_ig(CFG, Target), + + %% check_ig(IG), + ?report3("graph: ~p~nphysical regs: ~p~n", [list_ig(IG), PhysRegs]), + + %% These nodes *can't* be allocated to registers. + NotAllocatable = [Target:reg_nr(X) || X <- Target:non_alloc(CFG)], + %% i.e. Arguments on x86 + ?report2("Nonalloc ~w~n", [NotAllocatable]), + + {Cols, NewSpillIndex} = + color(IG, Spill, + ordsets:from_list(PhysRegs), + SpillIndex, + SpillLimit, + Target:number_of_temporaries(CFG), + Target, NotAllocatable), + Coloring = [{X, {reg, X}} || X <- NotAllocatable] ++ Cols, + ?ASSERT(check_coloring(Coloring, IG, Target)), + + {Coloring, NewSpillIndex}. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% *** BUILD THE INTERFERENCE GRAPH *** +%% +%% Returns {Interference_graph, Spill_cost_dictionary} +%% + +build_ig(CFG, Target) -> + try build_ig0(CFG, Target) + catch error:Rsn -> exit({?MODULE, build_ig, Rsn}) + end. + +build_ig0(CFG, Target) -> + Live = Target:analyze(CFG), + NumN = Target:number_of_temporaries(CFG), % poss. N-1? + {IG, Spill} = build_ig_bbs(Target:labels(CFG), + CFG, + Live, + empty_ig(NumN), + empty_spill(NumN), + Target), + {normalize_ig(IG), Spill}. + +build_ig_bbs([], _CFG, _Live, IG, Spill, _Target) -> + {IG, Spill}; +build_ig_bbs([L|Ls], CFG, Live, IG, Spill, Target) -> + Xs = bb(CFG, L, Target), + {_, NewIG, NewSpill} = + build_ig_bb(Xs, liveout(Live, L, Target), IG, Spill, Target), + build_ig_bbs(Ls, CFG, Live, NewIG, NewSpill, Target). + +build_ig_bb([], LiveOut, IG, Spill, _Target) -> + {LiveOut, IG, Spill}; +build_ig_bb([X|Xs], LiveOut, IG, Spill, Target) -> + {Live,NewIG,NewSpill} = build_ig_bb(Xs, LiveOut, IG, Spill, Target), + build_ig_instr(X, Live, NewIG, NewSpill, Target). + +%% Note: We could add move-related arcs here as well. +%% +%% Note: Ideally, we would like to add all registers to the IG +%% at once rather than doing 'add_nodes' for each instruction. +%% (This is costly, since nodes that already are present are checked!) + +build_ig_instr(X, Live, IG, Spill, Target) -> + {Def, Use} = def_use(X, Target), + ?report3("Live ~w\n~w : Def: ~w Use ~w\n", [Live, X, Def,Use]), + DefList = ordsets:to_list(Def), + NewSpill = inc_spill_costs(DefList, + inc_spill_costs(ordsets:to_list(Use), Spill)), + NewIG = interference_arcs(DefList, ordsets:to_list(Live), IG), + NewLive = ordsets:union(Use, ordsets:subtract(Live, Def)), + {NewLive, NewIG, NewSpill}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +interference_arcs([], _Live, IG) -> + IG; +interference_arcs([X|Xs], Live, IG) -> + interference_arcs(Xs, Live, i_arcs(X, Live, IG)). + +i_arcs(_X, [], IG) -> + IG; +i_arcs(X, [Y|Ys], IG) -> + i_arcs(X, Ys, add_edge(X,Y, IG)). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +inc_spill_costs([], Spill) -> Spill; +inc_spill_costs([X|Xs], Spill) -> + inc_spill_costs(Xs, inc_spill_cost(X, Spill)). + +inc_spill_cost(X, Spill) -> + set_spill_cost(X, get_spill_cost(X, Spill)+1, Spill). + +get_spill_cost(X, Spill) -> + spill_cost_lookup(X, Spill). + +set_spill_cost(X, N, Spill) -> + spill_cost_update(X, N, Spill). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% *** COLORING *** +%% +%% Coloring is done straightforwardly: +%% - find the low-degree nodes, put them in low +%% - while low non-empty: +%% * remove x from low +%% * push x on stack +%% * decrement degree of neighbors of x +%% * for each neighbor y of low degree, put y on low +%% - when low empty: +%% - if graph empty, return stack +%% - otherwise +%% * select a node z to spill +%% * push z on stack +%% * decrement degree of neighbors of z +%% * add low-degree neighbors of z to low +%% * restart the while-loop above + +color(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, NotAllocatable) -> + try color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit, + NumNodes, Target, NotAllocatable) + catch + error:Rsn -> + ?error_msg("Coloring failed with ~p~n", [Rsn]), + ?EXIT(Rsn) + end. + +color_0(IG, Spill, PhysRegs, SpillIx, SpillLimit, NumNodes, Target, + NotAllocatable) -> + ?report("simplification of IG~n", []), + K = ordsets:size(PhysRegs), + Nodes = list_ig(IG), + + Low = low_degree_nodes(Nodes, K, NotAllocatable), + + %% Any nodes above the spillimit must be colored first... + MustNotSpill = + if NumNodes > SpillLimit+1 -> + sort_on_degree(lists:seq(SpillLimit+1,NumNodes-1) -- Low,IG); + true -> [] + end, + + ?report(" starting with low degree nodes ~p~n",[Low]), + EmptyStk = [], + Precolored = Target:all_precoloured(), + {Stk, NewSpillIx} = + simplify(Low, NumNodes, Precolored, + IG, Spill, K, SpillIx, EmptyStk, + SpillLimit, Target, NotAllocatable, MustNotSpill), + ?report("selecting colors~n",[]), + {select(Stk, Precolored, IG, K, PhysRegs, NumNodes, Target), + NewSpillIx}. + +sort_on_degree(Nodes, IG) -> + [ Node3 || {_,Node3} <- + lists:sort([{degree(Info),Node2} || + {Info,Node2} <- [{hipe_vectors:get(IG, Node), + Node} || Node <- + Nodes]])]. + +%%%%%%%%%%%%%%%%%%%% +%% +%% Simplification: push all easily colored nodes on a stack; +%% when the list of easy nodes becomes empty, see if graph is +%% empty as well. If it is not, spill a node and continue. +%% If it is empty, return the stack. +%% +%% Notes: +%% - We keep the set of visited nodes around for spill purposes +%% (visited nodes are not considered for spilling) +%% +%% - At present, nodes can be pushed onto the stack even if they +%% already are on the stack. This can be fixed by another 'Vis' +%% dictionary that keeps track of what is on the stack. +%% Currently, we just skip already colored nodes. +%% +%% - Arguments: +%% Low: low-degree nodes (ready to color) +%% NumNodes: number of remaining nodes in graph +%% IG: interference graph +%% Spill: spill costs of nodes +%% K: number of colors +%% Ix: next spill index +%% Stk: stack of already simplified nodes +%% +%% Physical registers are marked as 'visited' prior to simplify. +%% This has the following effect: +%% - they are not considered for spilling +%% - they are not pushed on the stack +%% - since we do NOT decrement degrees of surrounding vars, the +%% non-physreg variables must still take them into account. + +simplify(Low, NumNodes, PreC, IG, Spill, K, Ix, Stk, SpillLimit, + Target, NotAllocatable, MustNotSpill) -> + Vis = visit_all(PreC, none_visited(NumNodes)), + Vis1 = visit_all(NotAllocatable, Vis), + ActualNumNodes = (NumNodes-length(PreC))-length(NotAllocatable), + %% Make sure that the registers that must not be spilled + %% get a degree less than K by spilling other regs. + {Stk2, Ix2, Vis2, Low2} = + handle_non_spill(MustNotSpill, IG, Spill, K, Ix, Stk, Vis1, Low, + SpillLimit, Target), + simplify_ig(Low2, ActualNumNodes-length(Stk2), IG, Spill, K, Ix2, Stk2, Vis2, + SpillLimit, Target). + +handle_non_spill([], _IG, _Spill, _K, Ix, Stk, Vis, Low, _SpillLimit, _Target) -> + {Stk, Ix, Vis, Low}; +handle_non_spill([X|Xs] = L, IG, Spill, K, Ix, Stk, Vis, Low, SpillLimit, Target) -> + Info = hipe_vectors:get(IG, X), + Degree = degree(Info), + ?report("Can't Spill ~w with degree ~w\n", [X,Degree]), + if Degree > K -> + ?report(" *** spill required (N<~w)***~n", [SpillLimit]), + {Y, NewLow, NewIG} = spill(IG, Vis, Spill, K, SpillLimit, Target), + NewVis = visit(Y,Vis), + {NewStk, NewIx} = push_spill_node(Y, Ix, Stk), + ?report(" node ~w spilled~n", [Y]), + handle_non_spill(L, NewIG, Spill, K, NewIx, NewStk, NewVis, + Low ++ NewLow, SpillLimit, Target); + true -> + {NewLow, NewIG} = decrement_neighbors(X, Low, IG, Vis, K), + ?report(" node ~w pushed\n(~w now ready)~n", [X,NewLow]), + NewStk = push_colored(X, Stk), + handle_non_spill(Xs, NewIG, Spill, K, Ix, NewStk, visit(X,Vis), + NewLow, SpillLimit, Target) + end. + +simplify_ig([], 0, _IG, _Spill, _K, Ix, Stk, _Vis, _SpillLimit, _Target) -> + {Stk, Ix}; +simplify_ig([], N, IG, Spill, K, Ix, Stk, Vis, SpillLimit, Target) + when N > 0 -> + ?report3("N: ~w Stk: ~w N+Stk ~w\n", [N,length(Stk),N+length(Stk)]), + ?report(" *** spill required (N<~w)***~n", [SpillLimit]), + {X, Low, NewIG} = spill(IG, Vis, Spill, K, SpillLimit, Target), + NewVis = visit(X,Vis), + {NewStk, NewIx} = push_spill_node(X, Ix, Stk), + ?report(" node ~w spilled\n(~w now ready)~n", [X, Low]), + simplify_ig(Low, N-1, NewIG, Spill, K, NewIx, NewStk, NewVis, + SpillLimit, Target); +simplify_ig([X|Xs], N, IG, Spill, K, Ix, Stk, Vis, SpillLimit, Target) -> + ?report3("N: ~w Stk: ~w N+Stk ~w\n", [N,length(Stk),N+length(Stk)]), + case is_visited(X,Vis) of + true -> + ?report(" node ~p already visited~n",[X]), + simplify_ig(Xs, N, IG, Spill, K, Ix, Stk, Vis, SpillLimit, Target); + false -> + ?report("Stack ~w\n", [Stk]), + {NewLow, NewIG} = decrement_neighbors(X, Xs, IG, Vis, K), + ?report(" node ~w pushed\n(~w now ready)~n", [X,NewLow]), + NewStk = push_colored(X, Stk), + simplify_ig(NewLow, N-1, NewIG, Spill, K, Ix, NewStk, visit(X,Vis), + SpillLimit, Target) + end. + +%% Returns { NowLowDegreeNeighbors, NewIG } + +decrement_neighbors(X, Xs, IG, Vis, K) -> + Ns = unvisited_neighbors(X, Vis, IG), + ?report(" node ~p has neighbors ~w\n(unvisited ~p)~n", + [X, neighbors(X, IG), Ns]), + decrement_each(Ns, Xs, IG, Vis, K). + +%% For each node, decrement its degree and check if it is now +%% a low-degree node. In that case, add it to the 'low list'. + +decrement_each([], Low, IG, _Vis, _K) -> + {Low, IG}; +decrement_each([N|Ns], OldLow, IG, Vis, K) -> + {Low, CurrIG} = Res = decrement_each(Ns, OldLow, IG, Vis, K), + case is_visited(N, Vis) of + true -> + Res; + false -> + {D, NewIG} = decrement_degree(N, CurrIG), + if + D =:= K-1 -> + {[N|Low], NewIG}; + true -> + {Low, NewIG} + end + end. + +%%%%%%%%%%%%%%%%%%%% +%% +%% The spill cost of a node is: +%% est_spill_cost / current_degree +%% +%% For all unvisited nodes, compute spill cost and select the minimum. +%% This node is chosen to be spilled. Then decrement the degree of its +%% neighbors, and return those of low degree. +%% +%% Notes: +%% - A better method for computing spill costs is to just keep the +%% minimum cost node. But for debugging purposes, we compute a list +%% of {node,spillcost} pairs and select the minimum. +%% +%% Returns: +%% {Spilled_node, Low_degree_neighbors, New_interference_graph} + +spill(IG, Vis, Spill, K, SpillLimit, Target) -> + Ns = list_ig(IG), + Costs = spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target), + ?report3("spill costs are ~p~n",[Costs]), + ActualCosts = lists:sort(Costs), + ?report3("actual costs are ~p~n",[ActualCosts]), + case ActualCosts of + [] -> + ?error_msg("There is no node to spill",[]), + ?EXIT('no node to spill'); + [{_Cost,N}|_] -> + {Low, NewIG} = decrement_neighbors(N, [], IG, Vis, K), + %?report("spilled node ~p at cost ~p (~p now ready)~n",[N,Cost,Low]), + {N, Low, NewIG} + end. + +spill_costs([], _IG, _Vis, _Spill, _SpillLimit, _Target) -> + []; +spill_costs([{N,Info}|Ns], IG, Vis, Spill, SpillLimit, Target) -> + case degree(Info) of + 0 -> spill_costs(Ns,IG,Vis,Spill, SpillLimit, Target); + Deg -> + case is_visited(N,Vis) of + true -> + spill_costs(Ns,IG,Vis,Spill, SpillLimit, Target); + _ -> + case Target:is_fixed(N) of + true -> + spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target); + false -> + if N > SpillLimit -> + spill_costs(Ns, IG, Vis, Spill, SpillLimit, Target); + true -> + [{spill_cost_of(N,Spill)/Deg,N} | + spill_costs(Ns,IG, Vis, Spill, SpillLimit, Target)] + end + end + end + end. + +%%%%%%%%%%%%%%%%%%%% +%% +%% Returns a list of {Name,Location}, where Location is +%% either {spill,M} or {reg,R} +%% +%% Note: we use pessimistic coloring here. +%% - we could use optimistic coloring: for spilled node, check if there is +%% an unused color among the neighbors and choose that. + +select(Stk, PreC, IG, K, PhysRegs, NumNodes, Target) -> + %% NumNodes = length(Stk)+length(PreC), + {PhysColors, Cols} = precolor(PreC, none_colored(NumNodes), Target), + ?report("precoloring has yielded ~p~n",[list_coloring(Cols)]), + PhysColors ++ select_colors(Stk, IG, Cols, PhysRegs, K). + +select_colors([], _IG, _Cols, _PhysRegs, _K) -> + ?report("all nodes colored~n",[]), + []; +select_colors([{X,colorable}|Xs], IG, Cols, PhysRegs, K) -> + ?report("color of ~p\n",[X]), + {Reg,NewCols} = select_color(X, IG, Cols, PhysRegs), + ?report("~p~n",[Reg]), + [{X,{reg,Reg}} | select_colors(Xs, IG, NewCols, PhysRegs, K)]; +%select_colors([{X,{spill,M}}|Xs], IG, Cols, PhysRegs, K) -> +% ?report('spilled: ~p~n',[X]), +% %% Check if optimistic coloring could have found a color +% case catch select_color(X,IG,Cols,K) of +% {'EXIT',_} -> % no color possible +% ?report('(no optimistic color)~n',[]), +% [{X,{spill,M}}|select_colors(Xs, IG, Cols, PhysRegs, K)]; +% {Reg,NewCols} -> +% ?report('(optimistic color: ~p)~n',[Reg]), +% [{X,{reg,Reg}}|select_colors(Xs, IG, Cols, PhysRegs, K)] +% end. + +%% Old code / pessimistic coloring: +select_colors([{X,{spill,M}}|Xs], IG, Cols, PhysRegs, K) -> + ?report("spilled: ~p~n",[X]), + %% Check if optimistic coloring could have found a color +% case catch select_color(X,IG,Cols,K) of +% {'EXIT',_} -> % no color possible +% ?report('(no optimistic color)~n',[]); +% {Reg,NewCols} -> +% ?report('(optimistic color: ~p)~n',[Reg]) +% end, + [{X,{spill,M}} | select_colors(Xs, IG, Cols, PhysRegs, K)]. + +select_color(X, IG, Cols, PhysRegs) -> + UsedColors = get_colors(neighbors(X, IG), Cols), + Reg = select_unused_color(UsedColors, PhysRegs), + {Reg, set_color(X, Reg, Cols)}. + +%%%%%%%%%%%%%%%%%%%% + +get_colors([], _Cols) -> []; +get_colors([X|Xs], Cols) -> + case color_of(X, Cols) of + uncolored -> + get_colors(Xs, Cols); + {color,R} -> + [R|get_colors(Xs, Cols)] + end. + +select_unused_color(UsedColors, PhysRegs) -> + Summary = ordsets:from_list(UsedColors), + AvailRegs = ordsets:to_list(ordsets:subtract(PhysRegs, Summary)), + hd(AvailRegs). + %% select_avail_reg(AvailRegs). + +%% We choose the register to use randomly from the set of available +%% registers. +%% +%% Note: Another way of doing it is LRU-order: +%% - Have an LRU-queue of register names; when coloring, try the colors in that +%% order (some may be occupied). +%% - When a color has been selected, put it at the end of the LRU. + +%% select_avail_reg(Regs) -> +%% case get(seeded) of +%% undefined -> +%% random:seed(), +%% put(seeded,true); +%% true -> +%% ok +%% end, +%% NReg = length(Regs), +%% RegNo = random:uniform(NReg), +%% lists:nth(RegNo, Regs). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +push_spill_node(X, M, Stk) -> + {[{X,{spill,M}}|Stk], M+1}. + +push_colored(X, Stk) -> + [{X, colorable} | Stk]. + +%%%%%%%%%%%%%%%%%%%% + +low_degree_nodes([], _K, _NotAllocatable) -> []; +low_degree_nodes([{N,Info}|Xs], K, NotAllocatable) -> + case lists:member(N, NotAllocatable) of + true -> + low_degree_nodes(Xs,K, NotAllocatable); + false -> + ?report0("node ~p has degree ~p: ~w~n",[N,degree(Info),neighbors(Info)]), + Deg = degree(Info), + if + Deg < K -> + [N|low_degree_nodes(Xs, K, NotAllocatable)]; + true -> + low_degree_nodes(Xs, K, NotAllocatable) + end + end. + +%%%%%%%%%%%%%%%%%%%% + +unvisited_neighbors(X, Vis, IG) -> + ordsets:from_list(unvisited(neighbors(X,IG), Vis)). + +unvisited([], _Vis) -> []; +unvisited([X|Xs], Vis) -> + case is_visited(X, Vis) of + true -> + unvisited(Xs, Vis); + false -> + [X|unvisited(Xs, Vis)] + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% *** ABSTRACT DATATYPES *** + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The ig datatype: +%% +%% Note: if we know the number of temps used, we can use a VECTOR +%% instead, which will speed up things. +%% +%% Note: later on, we may wish to add 'move-related' support. + +-record(ig_info, {neighbors=[], degree=0 :: integer()}). + +empty_ig(NumNodes) -> + hipe_vectors:new(NumNodes, #ig_info{neighbors=[], degree=0}). + +degree(Info) -> + Info#ig_info.degree. + +neighbors(Info) -> + Info#ig_info.neighbors. + +add_edge(X, X, IG) -> IG; +add_edge(X, Y, IG) -> + add_arc(X, Y, add_arc(Y, X, IG)). + +add_arc(X, Y, IG) -> + Info = hipe_vectors:get(IG, X), + Old = neighbors(Info), + New = Info#ig_info{neighbors=[Y|Old]}, + hipe_vectors:set(IG, X, New). + +normalize_ig(IG) -> + Size = hipe_vectors:size(IG), + normalize_ig(Size-1, IG). + +normalize_ig(-1, IG) -> + IG; +normalize_ig(I, IG) -> + Info = hipe_vectors:get(IG, I), + N = ordsets:from_list(neighbors(Info)), + NewIG = hipe_vectors:set(IG, I, Info#ig_info{neighbors=N, degree=length(N)}), + normalize_ig(I-1, NewIG). + +%%degree(X, IG) -> +%% Info = hipe_vectors:get(IG, X), +%% Info#ig_info.degree. + +neighbors(X, IG) -> + Info = hipe_vectors:get(IG, X), + Info#ig_info.neighbors. + +decrement_degree(X, IG) -> + Info = hipe_vectors:get(IG, X), + Degree = degree(Info), + NewDegree = Degree-1, + NewInfo = Info#ig_info{degree=NewDegree}, + {NewDegree, hipe_vectors:set(IG,X,NewInfo)}. + +list_ig(IG) -> + hipe_vectors:list(IG). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The spill cost datatype: +%% +%% Note: if we know the number of temps used, we can use a VECTOR +%% instead, which will speed up things. + +empty_spill(NumNodes) -> + hipe_vectors:new(NumNodes, 0). + +spill_cost_of(X, Spill) -> + hipe_vectors:get(Spill, X). + +spill_cost_lookup(X, Spill) -> + spill_cost_of(X, Spill). + +spill_cost_update(X, N, Spill) -> + hipe_vectors:set(Spill, X, N). + +%%list_spill_costs(Spill) -> +%% hipe_vectors:list(Spill). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The coloring datatype: + +none_colored(NumNodes) -> + hipe_vectors:new(NumNodes,uncolored). + +color_of(X,Cols) -> + hipe_vectors:get(Cols,X). + +set_color(X,R,Cols) -> + hipe_vectors:set(Cols,X,{color,R}). + +-ifdef(DEBUG). +list_coloring(Cols) -> + hipe_vectors:list(Cols). +-endif. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Note: there might be a slight gain in separating the two versions +%% of visit/2 and visited/2. (So that {var,X} selects X and calls the +%% integer version. + +none_visited(NumNodes) -> + hipe_vectors:new(NumNodes, false). + +visit(X,Vis) -> + hipe_vectors:set(Vis, X, true). + +is_visited(X,Vis) -> + hipe_vectors:get(Vis, X). + +visit_all([], Vis) -> Vis; +visit_all([X|Xs], Vis) -> + visit_all(Xs, visit(X, Vis)). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% Check that all arcs in IG are bidirectional + degree is correct + +%% check_ig(IG) -> +%% check_ig(list_ig(IG),IG). + +%% check_ig([],IG) -> +%% ok; +%% check_ig([{N,Info}|Xs],IG) -> +%% Ns = neighbors(Info), +%% NumNs = length(Ns), +%% D = degree(Info), +%% if +%% D =:= NumNs -> +%% ok; +%% true -> +%% ?WARNING_MSG('node ~p has degree ~p but ~p neighbors~n',[N,D,NumNs]) +%% end, +%% check_neighbors(N,Ns,IG), +%% check_ig(Xs,IG). + +%% check_neighbors(N,[],IG) -> +%% ok; +%% check_neighbors(N,[M|Ms],IG) -> +%% Ns = neighbors(M,IG), +%% case member(N,Ns) of +%% true -> +%% ok; +%% true -> +%% ?WARNING_MSG('node ~p should have ~p as neighbor (has ~p)~n',[M,N,Ns]) +%% end, +%% check_neighbors(N,Ms,IG). + +-ifdef(DO_ASSERT). +%%%%%%%%%%%%%%%%%%%% +%% Check that the coloring is correct (if the IG is correct): +%% + +check_coloring(Coloring, IG, Target) -> + ?report0("checking coloring ~p~n",[Coloring]), + check_cols(list_ig(IG),init_coloring(Coloring, Target)). + +init_coloring(Xs, Target) -> + hipe_temp_map:cols2tuple(Xs, Target). + +check_color_of(X, Cols) -> +%% if +%% is_precoloured(X) -> +%% phys_reg_color(X,Cols); +%% true -> + case hipe_temp_map:find(X, Cols) of + unknown -> + ?WARNING_MSG("node ~p: color not found~n", [X]), + uncolored; + C -> + C + end. + +check_cols([], Cols) -> + ?report("coloring valid~n",[]), + true; +check_cols([{X,Info}|Xs], Cols) -> + Cs = [{N, check_color_of(N, Cols)} || N <- neighbors(Info)], + C = check_color_of(X, Cols), + case valid_coloring(X, C, Cs) of + yes -> + check_cols(Xs, Cols); + {no,Invalids} -> + ?WARNING_MSG("node ~p has same color (~p) as ~p~n", [X,C,Invalids]), + check_cols(Xs, Cols) + end. + +valid_coloring(X, C, []) -> + yes; +valid_coloring(X, C, [{Y,C}|Ys]) -> + case valid_coloring(X, C, Ys) of + yes -> {no, [Y]}; + {no,Zs} -> {no, [Y|Zs]} + end; +valid_coloring(X, C, [_|Ys]) -> + valid_coloring(X, C, Ys). +-endif. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% *** INTERFACES TO OTHER MODULES *** +%% + +liveout(CFG, L, Target) -> + ordsets:from_list(reg_names(Target:liveout(CFG, L), Target)). + +bb(CFG, L, Target) -> + hipe_bb:code(Target:bb(CFG, L)). + +def_use(X, Target) -> + {ordsets:from_list(reg_names(Target:defines(X), Target)), + ordsets:from_list(reg_names(Target:uses(X), Target))}. + +reg_names(Regs, Target) -> + [Target:reg_nr(X) || X <- Regs]. + +%% +%% Precoloring: use this version when a proper implementation of +%% physical_name(X) is available! +%% + +precolor(Xs, Cols, Target) -> + ?report("precoloring ~p~n", [Xs]), + {_Cs, _NewCol} = Res = precolor0(Xs, Cols, Target), + ?report(" yielded ~p~n", [_Cs]), + Res. + +precolor0([], Cols, _Target) -> + {[], Cols}; +precolor0([R|Rs], Cols, Target) -> + {Cs, Cols1} = precolor0(Rs, Cols, Target), + {[{R, {reg, physical_name(R, Target)}}|Cs], + set_color(R, physical_name(R, Target), Cols1)}. + +physical_name(X, Target) -> + Target:physical_name(X). diff --git a/lib/hipe/regalloc/hipe_ig.erl b/lib/hipe/regalloc/hipe_ig.erl new file mode 100644 index 0000000000..4991e73e53 --- /dev/null +++ b/lib/hipe/regalloc/hipe_ig.erl @@ -0,0 +1,776 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%---------------------------------------------------------------------- +%% File : hipe_ig.erl +%% Author : Andreas Wallin +%% Purpose : Creates an interference graph that tells which temporaries +%% interfere with each other. +%% Created : 5 Feb 2000 +%%---------------------------------------------------------------------- + +-module(hipe_ig). + +-export([build/2, + nodes_are_adjacent/3, + node_spill_cost/2, + node_adj_list/2, + get_moves/1, + %% degree/1, + %% number_of_temps/1, + spill_costs/1, + adj_list/1, + %% adj_set/1, + add_edge/4, + remove_edge/4, + %% set_adj_set/2, + %% set_adj_list/2, + %% set_ig_moves/2, + %% set_spill_costs/2, + %% set_degree/2 + get_node_degree/2, + dec_node_degree/2, + is_trivially_colourable/3 + ]). +-ifdef(DEBUG_PRINTOUTS). +-export([print_spill_costs/1, + print_adjacent/1, + print_degrees/1 + ]). +-endif. + +%%-ifndef(DEBUG). +%%-define(DEBUG,true). +%%-endif. + +-include("../main/hipe.hrl"). +-include("../flow/cfg.hrl"). +-include("hipe_spillcost.hrl"). + +%%---------------------------------------------------------------------- + +-record(igraph, {adj_set, adj_list, ig_moves, degree, + spill_costs :: #spill_cost{}, + num_temps :: non_neg_integer()}). + +%%---------------------------------------------------------------------- +%% Degree: array mapping nodes to integer degrees. +%% Precoloured nodes have 'infinite' degrees: they are initialised with +%% degrees K + number_of_temporaries. +%% Operations include incrementing, decrementing, and querying a node's +%% degree, and testing for trivial colourability (degree < K). +%%---------------------------------------------------------------------- + +degree_new(No_temporaries, Target) -> + Degree = hipe_bifs:array(No_temporaries, 0), + K = length(Target:allocatable()), + Inf = K + No_temporaries, + precoloured_to_inf_degree(Target:all_precoloured(), Inf, Degree). + +precoloured_to_inf_degree([], _Inf, Degree) -> Degree; +precoloured_to_inf_degree([P|Ps], Inf, Degree) -> + hipe_bifs:array_update(Degree, P, Inf), + precoloured_to_inf_degree(Ps, Inf, Degree). + +degree_inc(Node, Degree) -> + hipe_bifs:array_update(Degree, Node, hipe_bifs:array_sub(Degree, Node) + 1). + +degree_dec(Node, Degree) -> + hipe_bifs:array_update(Degree, Node, hipe_bifs:array_sub(Degree, Node) - 1). + +degree_get(Node, Degree) -> + hipe_bifs:array_sub(Degree, Node). + +degree_is_trivially_colourable(Node, K, Degree) -> + hipe_bifs:array_sub(Degree, Node) < K. + +%%---------------------------------------------------------------------- +%% AdjSet: +%% Implements sets of adjacent nodes. +%% Symmetry implies that when (U,V) is a member, then so is (V,U). +%% Hence, only (U,V), where U + ArrayWords = (ArrayBits + (?BITS_PER_WORD - 1)) bsr ?LOG2_BITS_PER_WORD, + Byte = + case Val of + true -> 16#FF; + false -> 16#00 + end, + hipe_bifs:bytearray(ArrayWords, Byte). + +hipe_bifs_bitarray_update(Array, BitNr, Val) -> + WordNr = BitNr bsr ?LOG2_BITS_PER_WORD, + WordMask = 1 bsl (BitNr band (?BITS_PER_WORD - 1)), + Word = hipe_bifs:bytearray_sub(Array, WordNr), + NewWord = + case Val of + true -> Word bor WordMask; + false -> Word band (bnot WordMask) + end, + hipe_bifs:bytearray_update(Array, WordNr, NewWord). + +hipe_bifs_bitarray_sub(Array, BitNr) -> + WordNr = BitNr bsr ?LOG2_BITS_PER_WORD, + WordMask = 1 bsl (BitNr band (?BITS_PER_WORD - 1)), + Word = hipe_bifs:bytearray_sub(Array, WordNr), + Word band WordMask =/= 0. + +-define(HIPE_BIFS_BITARRAY(ArrayBits, Val), hipe_bifs_bitarray(ArrayBits, Val)). +-define(HIPE_BIFS_BITARRAY_UPDATE(Array, BitNr, Val), hipe_bifs_bitarray_update(Array, BitNr, Val)). +-define(HIPE_BIFS_BITARRAY_SUB(Array, BitNr), hipe_bifs_bitarray_sub(Array, BitNr)). + +-endif. % EMULATE_BITARRAY_BIFS + +-record(adjset, {index, array}). +-record(adjset_chunked, {index, chunks}). + +-spec adjset_new(non_neg_integer()) -> #adjset{} | #adjset_chunked{}. + +adjset_new(NrTemps) -> + ArrayBits = (NrTemps * (NrTemps - 1)) div 2, + Index = adjset_mk_index(NrTemps, []), + try ?HIPE_BIFS_BITARRAY(ArrayBits, false) of + Array -> + #adjset{index=Index,array=Array} + catch + _:_ -> + #adjset_chunked{index=Index,chunks=adjset_mk_chunks(ArrayBits)} + end. + +-define(LOG2_CHUNK_BITS, 19). % 2^19 bits == 64KB +-define(CHUNK_BITS, (1 bsl ?LOG2_CHUNK_BITS)). + +adjset_mk_chunks(ArrayBits) -> + Tail = + case ArrayBits band (?CHUNK_BITS - 1) of + 0 -> []; + LastChunkBits -> [?HIPE_BIFS_BITARRAY(LastChunkBits, false)] + end, + N = ArrayBits bsr ?LOG2_CHUNK_BITS, + adjset_mk_chunks(N, Tail). + +adjset_mk_chunks(0, Tail) -> + list_to_tuple(Tail); +adjset_mk_chunks(N, Tail) -> + adjset_mk_chunks(N-1, [?HIPE_BIFS_BITARRAY(?CHUNK_BITS, false) | Tail]). + +adjset_mk_index(0, Tail) -> + list_to_tuple(Tail); +adjset_mk_index(N, Tail) -> + I = N - 1, + adjset_mk_index(I, [(I * (I-1)) div 2 | Tail]). + +adjset_add_edge(U0, V0, #adjset{index=Index,array=Array}) -> % PRE: U0 =/= V0 + {U,V} = + if U0 < V0 -> {U0,V0}; + true -> {V0,U0} + end, + %% INV: U < V + BitNr = element(V+1, Index) + U, + ?HIPE_BIFS_BITARRAY_UPDATE(Array, BitNr, true); +adjset_add_edge(U0, V0, #adjset_chunked{index=Index,chunks=Chunks}) -> % PRE: U0 =/= V0 + {U,V} = + if U0 < V0 -> {U0,V0}; + true -> {V0,U0} + end, + %% INV: U < V + BitNr = element(V+1, Index) + U, + %% here things become different + ChunkNr = BitNr bsr ?LOG2_CHUNK_BITS, + ChunkBit = BitNr band (?CHUNK_BITS - 1), + Chunk = element(ChunkNr+1, Chunks), + ?HIPE_BIFS_BITARRAY_UPDATE(Chunk, ChunkBit, true). + +adjset_remove_edge(U0, V0, #adjset{index=Index,array=Array}) -> % PRE: U0 =/= V0 + {U,V} = + if U0 < V0 -> {U0,V0}; + true -> {V0,U0} + end, + %% INV: U < V + BitNr = element(V+1, Index) + U, + ?HIPE_BIFS_BITARRAY_UPDATE(Array, BitNr, false); +adjset_remove_edge(U0, V0, #adjset_chunked{index=Index,chunks=Chunks}) -> % PRE: U0 =/= V0 + {U,V} = + if U0 < V0 -> {U0,V0}; + true -> {V0,U0} + end, + %% INV: U < V + BitNr = element(V+1, Index) + U, + %% here things become different + ChunkNr = BitNr bsr ?LOG2_CHUNK_BITS, + ChunkBit = BitNr band (?CHUNK_BITS - 1), + Chunk = element(ChunkNr+1, Chunks), + ?HIPE_BIFS_BITARRAY_UPDATE(Chunk, ChunkBit, false). + +adjset_are_adjacent(U0, V0, #adjset{index=Index,array=Array}) -> + {U,V} = + if U0 < V0 -> {U0,V0}; + U0 =:= V0 -> exit({?MODULE,adjacent,U0,V0}); % XXX: probably impossible + true -> {V0,U0} + end, + %% INV: U < V + BitNr = element(V+1, Index) + U, + ?HIPE_BIFS_BITARRAY_SUB(Array, BitNr); +adjset_are_adjacent(U0, V0, #adjset_chunked{index=Index,chunks=Chunks}) -> + {U,V} = + if U0 < V0 -> {U0,V0}; + U0 =:= V0 -> exit({?MODULE,adjacent,U0,V0}); % XXX: probably impossible + true -> {V0,U0} + end, + %% INV: U < V + BitNr = element(V+1, Index) + U, + %% here things become different + ChunkNr = BitNr bsr ?LOG2_CHUNK_BITS, + ChunkBit = BitNr band (?CHUNK_BITS - 1), + Chunk = element(ChunkNr+1, Chunks), + ?HIPE_BIFS_BITARRAY_SUB(Chunk, ChunkBit). + +%%--------------------------------------------------------------------- +%% Print functions - only used for debugging + +-ifdef(DEBUG_PRINTOUTS). +print_adjacent(IG) -> + ?debug_msg("Adjacent nodes:\n", []), + adjset_print(number_of_temps(IG),IG). + +adjset_print(2, IG) -> + adjset_print(1, 0, IG); +adjset_print(Ntemps, IG) -> + adjset_print(Ntemps - 1, Ntemps - 2, IG), + adjset_print(Ntemps - 1, IG). + +adjset_print(U, 0, IG) -> + case nodes_are_adjacent(U, 0, IG) of + true -> ?debug_msg("edge ~w ~w\n", [U, 0]); + _ -> true + end; +adjset_print(U, V, IG) -> + case nodes_are_adjacent(U, V, IG) of + true -> ?debug_msg("edge ~w ~w\n", [U, V]); + _ -> true + end, + adjset_print(U, V - 1, IG). +-endif. + +%%---------------------------------------------------------------------- +%% Function: adj_set, adj_list, degree, spill_costs +%% +%% Description: Selector functions. Used to get one of the encapsulated +%% data-structure contained in the IG structure. +%% Parameters: +%% IG -- An interference graph +%% +%% Returns: +%% One of the encapsulated data-structures. +%%---------------------------------------------------------------------- +adj_set(IG) -> IG#igraph.adj_set. +adj_list(IG) -> IG#igraph.adj_list. +ig_moves(IG) -> IG#igraph.ig_moves. +degree(IG) -> IG#igraph.degree. + +-spec spill_costs(#igraph{}) -> #spill_cost{}. +spill_costs(IG) -> IG#igraph.spill_costs. + +-ifdef(DEBUG_PRINTOUTS). +number_of_temps(IG) -> IG#igraph.no_temps. +-endif. + +%%---------------------------------------------------------------------- +%% Function: set_adj_set, set_adj_list, set_degree, set_spill_costs +%% +%% Description: Modifier functions. Used to set one of the encapsulated +%% data-structure contained in the IG structure. +%% Parameters: +%% Data-structure -- Data-structure you want to set. An adj_set +%% data-structure for example. +%% IG -- An interference graph +%% +%% Returns: +%% An updated interference graph. +%%---------------------------------------------------------------------- + +%%set_adj_set(Adj_set, IG) -> IG#igraph{adj_set = Adj_set}. +set_adj_list(Adj_list, IG) -> IG#igraph{adj_list = Adj_list}. +set_ig_moves(IG_moves, IG) -> IG#igraph{ig_moves = IG_moves}. +%%set_degree(Degree, IG) -> IG#igraph{degree = Degree}. +set_spill_costs(Spill_costs, IG) -> IG#igraph{spill_costs = Spill_costs}. + +%%---------------------------------------------------------------------- +%% Function: initial_ig +%% +%% Description: The initial interference record that we start with when +%% building the interference graph. +%% Parameters: +%% NumTemps -- Number of temporaries in the CFG we work on. This is +%% because we have some data structures built out of vectors. +%% +%% Returns: +%% A new interference record +%%---------------------------------------------------------------------- + +-spec initial_ig(non_neg_integer(), atom()) -> #igraph{}. + +initial_ig(NumTemps, Target) -> + #igraph{adj_set = adjset_new(NumTemps), + adj_list = hipe_adj_list:new(NumTemps), + ig_moves = hipe_ig_moves:new(NumTemps), + degree = degree_new(NumTemps, Target), + spill_costs = hipe_spillcost:new(NumTemps), + num_temps = NumTemps + }. + +%%---------------------------------------------------------------------- +%% Function: build +%% +%% Description: Constructs an interference graph for the specifyed CFG. +%% +%% Parameters: +%% CFG -- A Control Flow Graph +%% Target -- The module that contains the target-specific functions +%% +%% Returns: +%% An interference graph for the given CFG. +%%---------------------------------------------------------------------- + +-spec build(#cfg{}, atom()) -> #igraph{}. + +build(CFG, Target) -> + BBs_in_out_liveness = Target:analyze(CFG), + Labels = Target:labels(CFG), + %% How many temporaries exist? + NumTemps = Target:number_of_temporaries(CFG), + IG0 = initial_ig(NumTemps, Target), + %%?debug_msg("initial adjset: ~p\n",[element(2, IG0)]), + %%?debug_msg("initial adjset array: ~.16b\n",[element(3, element(2, IG0))]), + analyze_bbs(Labels, BBs_in_out_liveness, IG0, CFG, Target). + +%%---------------------------------------------------------------------- +%% Function: analyze_bbs +%% +%% Description: Looks up the code that exists in all basic blocks and +%% analyse instructions use and def's to see what +%% temporaries that interfere with each other. +%% +%% Parameters: +%% L -- A label +%% Ls -- Other labels that exits in the CFG +%% BBs_in_out_liveness -- The in and out liveness on all basic blocks +%% IG -- The interference graph in it's current state +%% CFG -- The Control Flow Graph that we constructs +%% the interference graph from. +%% Target -- The module containing the target-specific +%% functions +%% +%% Returns: +%% An interference graph for the given CFG. +%%---------------------------------------------------------------------- + +analyze_bbs([], _, IG, _, _) -> IG; +analyze_bbs([L|Ls], BBs_in_out_liveness, IG, CFG, Target) -> + % Get basic block associated with label L + BB = Target:bb(CFG, L), + % Get basic block code + BB_code = hipe_bb:code(BB), + % Temporaries that are live out from this basic block + BB_liveout = Target:liveout(BBs_in_out_liveness, L), + % Only temporary numbers + BB_liveout_numbers = reg_numbers(BB_liveout, Target), + % {Liveness, New Interference Graph} + {_, New_ig, Ref} = analyze_bb_instructions(BB_code, + ordsets:from_list(BB_liveout_numbers), + IG, + Target), + Newer_ig = set_spill_costs(hipe_spillcost:ref_in_bb(Ref, + spill_costs(New_ig)), + New_ig), + analyze_bbs(Ls, BBs_in_out_liveness, Newer_ig, CFG, Target). + +%%---------------------------------------------------------------------- +%% Function: analyze_bb_instructions +%% +%% Description: Analyzes all instructions that is contained in a basic +%% block in reverse order. +%% +%% Parameters: +%% Instruction -- An instruction +%% Instructions -- The remaining instructions +%% Live -- All temporaries that are live at the time. +%% Live is a set of temporary "numbers only". +%% IG -- The interference graph in it's current state +%% Target -- The mopdule containing the target-specific functions +%% +%% Returns: +%% Live -- Temporaries that are live at entery of basic block +%% that we analyze. +%% IG -- Updated interference graph. +%% Ref -- Set of temporaries referred to in this bb. +%%---------------------------------------------------------------------- + +%% Ref: set of temporaries referred to in this bb +analyze_bb_instructions([], Live, IG, _) -> {Live, IG, ordsets:new()}; +analyze_bb_instructions([Instruction|Instructions], Live, IG, Target) -> + %% Analyze last instruction first. + {Live0, IG0, Ref} = analyze_bb_instructions(Instructions, Live, + IG, Target), + %% Check for temporaries that are defined and used in instruction + {Def, Use} = Target:def_use(Instruction), + %% Convert to register numbers + Def_numbers = ordsets:from_list(reg_numbers(Def, Target)), + Use_numbers = ordsets:from_list(reg_numbers(Use, Target)), + Ref_numbers = ordsets:union(Ref, ordsets:union(Def_numbers, Use_numbers)), + %% Increase spill cost on all used temporaries + IG1 = set_spill_costs(hipe_spillcost:inc_costs(Use_numbers, + spill_costs(IG0)), + IG0), + {Live1, IG2} = analyze_move(Instruction, + Live0, + Def_numbers, + Use_numbers, + IG1, + Target), + %% Adding Def to Live here has the effect of creating edges between + %% the defined registers, which is O(N^2) for an instruction that + %% clobbers N registers. + %% + %% Adding Def to Live is redundant when: + %% 1. Def is empty, or + %% 2. Def is a singleton, or + %% 3. Def contains only precoloured registers, or + %% 4. Def contains exactly one non-precoloured register, and the + %% remaining ones are all non-allocatable precoloured registers. + %% + %% HiPE's backends only create multiple-element Def sets + %% for CALL instructions, and then all elements are precoloured. + %% + %% Therefore we can avoid adding Def to Live. The benefit is greatest + %% on backends with many physical registers, since CALLs clobber all + %% physical registers. + Live2 = Live1, % ordsets:union(Live1, Def_numbers), + IG3 = interfere(Def_numbers, Live2, IG2, Target), + Live3 = ordsets:union(Use_numbers, ordsets:subtract(Live2, Def_numbers)), + {Live3, IG3, Ref_numbers}. + +%%---------------------------------------------------------------------- +%% Function: analyze_move +%% +%% Description: If a move instructions is discovered, this function is +%% called. It is used to remember what move instructions +%% a temporary is associated with and all moves that exists +%% in the CFG. +%% +%% Parameters: +%% Instruction -- An instruction +%% Live -- All temporaries that are live at the time. +%% Live is a set of temporary "numbers only". +%% Def_numbers -- Temporaries that are defined at this instruction +%% Use_numbers -- Temporaries that are used at this instruction +%% IG -- The interference graph in its current state +%% Target -- The module containing the target-specific functions +%% Returns: +%% Live -- An updated live set +%% IG -- An updated interference graph +%%---------------------------------------------------------------------- + +analyze_move(Instruction, Live, Def_numbers, Use_numbers, IG, Target) -> + case Target:is_move(Instruction) of + true -> + case {Def_numbers, Use_numbers} of + {[Dst], [Src]} -> + New_IG = set_ig_moves(hipe_ig_moves:new_move(Dst, Src, ig_moves(IG)), IG), + New_live = ordsets:del_element(Src, Live), + {New_live, New_IG}; + _ -> + {Live, IG} + end; + _ -> + {Live, IG} + end. + +%%---------------------------------------------------------------------- +%% Function: interfere +%% +%% Description: A number of temporaries that are defined interfere with +%% everything in the current live set. +%% +%% Parameters: +%% Define -- A Define temporary +%% Defines -- Rest of temporaries. +%% Live -- Current live set +%% IG -- An interference graph +%% +%% Returns: +%% An updated interference graph. +%%---------------------------------------------------------------------- + +interfere([], _, IG, _) -> IG; +interfere([Define|Defines], Living, IG, Target) -> + New_ig = interfere_with_living(Define, Living, IG, Target), + interfere(Defines, Living, New_ig, Target). + +%%---------------------------------------------------------------------- +%% Function: interfere_with_living +%% +%% Description: Let one temporary that is in the define set interfere +%% with all live temporaries. +%% +%% Parameters: +%% Define -- A Define temporary +%% Live -- Current live set +%% Lives -- Rest of living temporaries. +%% IG -- An interference graph +%% Target -- The module containing the target-specific functions +%% Returns: +%% An updated interference graph +%%---------------------------------------------------------------------- + +interfere_with_living(_, [], IG, _) -> IG; +interfere_with_living(Define, [Live|Living], IG, Target) -> + New_ig = add_edge(Define, Live, IG, Target), + interfere_with_living(Define, Living, New_ig, Target). + +%% +%% nodes_are_adjacent(U, V, IG) +%% returns true if nodes U and V are adjacent in interference graph IG +%% +-spec nodes_are_adjacent(integer(), integer(), #igraph{}) -> boolean(). +nodes_are_adjacent(U, V, IG) -> + adjset_are_adjacent(U, V, adj_set(IG)). + +%% +%% node_adj_set(Node, IG) +%% returns list of Node's adjacent nodes in interference graph IG +%% +node_adj_list(Node, IG) -> + hipe_adj_list:edges(Node, adj_list(IG)). + +%% +%% node_spill_cost(Node, IG) +%% returns the Node's spill cost +%% +node_spill_cost(Node, IG) -> + hipe_spillcost:spill_cost(Node, spill_costs(IG)). + +%%---------------------------------------------------------------------- +%% Print functions - only used for debugging + +-ifdef(DEBUG_PRINTOUTS). +print_spill_costs(IG) -> + ?debug_msg("Spill costs:\n", []), + print_spill_costs(number_of_temps(IG), IG). + +print_spill_costs(0, _) -> + true; +print_spill_costs(Node, IG) -> + NextNode = Node - 1, + case hipe_spillcost:nr_of_use(NextNode, spill_costs(IG)) of + 0 -> + ?debug_msg("node ~w not used\n", [NextNode]); + _ -> + ?debug_msg("node ~w sc ~p\n", [NextNode, node_spill_cost(NextNode, IG)]) + end, + print_spill_costs(NextNode, IG). +-endif. + +%%---------------------------------------------------------------------- + +get_moves(IG) -> + hipe_ig_moves:get_moves(ig_moves(IG)). + +%%---------------------------------------------------------------------- +%% Function: add_edge +%% +%% Description: Adds an edge to the adj_set data structure if it is +%% not already a part of it and if U is not precoloured +%% we add V to its adj_list. If V is not precoloured +%% we add U to its adj_list. +%% +%% Parameters: +%% U -- A temporary number +%% V -- A temporary number +%% Target -- The module containing the target-specific functions +%% Returns: +%% An updated interference graph. +%%---------------------------------------------------------------------- + +add_edge(U, U, IG, _) -> IG; +add_edge(U, V, IG, Target) -> + case nodes_are_adjacent(U, V, IG) of + true -> + IG; + false -> + _ = adjset_add_edge(U, V, adj_set(IG)), + Degree = degree(IG), + AdjList0 = interfere_if_uncolored(U, V, adj_list(IG), Degree, Target), + AdjList1 = interfere_if_uncolored(V, U, AdjList0, Degree, Target), + set_adj_list(AdjList1, IG) + end. + +%%---------------------------------------------------------------------- +%% Function: remove_edge +%% +%% Description: Removes an edge to the adj_set data-structure if it's +%% a part of it and if U is not precoloured +%% we remove V from it's adj_list. If V is not precoloured +%% we remove U from it's adj_list. +%% +%% Parameters: +%% U -- A temporary number +%% V -- A temporary number +%% Target -- The module containing the target-specific functions +%% Returns: +%% An updated interference graph. +%%---------------------------------------------------------------------- + +remove_edge(U, U, IG, _) -> IG; +remove_edge(U, V, IG, Target) -> + case nodes_are_adjacent(U, V, IG) of + false -> + IG; + true -> + _ = adjset_remove_edge(U, V, adj_set(IG)), + Degree = degree(IG), + AdjList0 = remove_if_uncolored(U, V, adj_list(IG), Degree, Target), + AdjList1 = remove_if_uncolored(V, U, AdjList0, Degree, Target), + set_adj_list(AdjList1, IG) + end. + +%%---------------------------------------------------------------------- +%% Function: remove_if_uncolored +%% +%% Description: +%% +%% Parameters: +%% Temporary -- A temporary that is added to the adjacent +%% list if it's not precoloured. +%% Interfere_temporary -- Temporary will interfere with +%% Interfere_temporary if temporary is not +%% precoloured. +%% Adj_list -- An adj_list +%% Degree -- The degree that all nodes currently have +%% Target -- The module containing the target-specific +%% functions +%% +%% Returns: +%% Adj_list -- An updated adj_list data structure +%% Degree -- An updated degree data structure (via side-effects) +%%---------------------------------------------------------------------- + +remove_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) -> + case Target:is_precoloured(Temp) of + false -> + New_adj_list = hipe_adj_list:remove_edge(Temp, InterfereTemp, Adj_list), + degree_dec(Temp, Degree), + New_adj_list; + true -> + Adj_list + end. + +%%---------------------------------------------------------------------- +%% Function: interfere_if_uncolored +%% +%% Description: Let a not precoloured temporary interfere with another. +%% +%% Parameters: +%% Temporary -- A temporary that is added to the adjacent +%% list if it's not precoloured. +%% Interfere_temporary -- Temporary will interfere with +%% Interfere_temporary if temporary is not +%% precoloured. +%% Adj_list -- An adj_list +%% Degree -- The degree that all nodes currently have +%% Target -- The module containing the target-specific +%% functions +%% +%% Returns: +%% Adj_list -- An updated adj_list data structure +%% Degree -- An updated degree data structure (via side-effects) +%%---------------------------------------------------------------------- + +interfere_if_uncolored(Temp, InterfereTemp, Adj_list, Degree, Target) -> + case Target:is_precoloured(Temp) of + false -> + New_adj_list = hipe_adj_list:add_edge(Temp, InterfereTemp, Adj_list), + degree_inc(Temp, Degree), + New_adj_list; + true -> + Adj_list + end. + +%%---------------------------------------------------------------------- +%% Function: reg_numbers +%% +%% Description: Converts a list of tuple with {something, reg_number} +%% to a list of register numbers. +%% +%% Parameters: +%% TRs -- A list of temporary registers +%% Target -- The module containing the target-specific functions +%% Returns: +%% A list of register numbers. +%%---------------------------------------------------------------------- + +reg_numbers(Regs, Target) -> + [Target:reg_nr(X) || X <- Regs]. + +%%--------------------------------------------------------------------- +%% Print functions - only used for debugging + +-ifdef(DEBUG_PRINTOUTS). +print_degrees(IG) -> + ?debug_msg("The nodes degrees:\n", []), + print_node_degree(number_of_temps(IG), IG). + +print_node_degree(0, _) -> + true; +print_node_degree(Node, IG) -> + NextNode = Node - 1, + ?debug_msg("node ~w ~w\n", [NextNode, get_node_degree(NextNode, IG)]), + print_node_degree(NextNode, IG). +-endif. + +%%---------------------------------------------------------------------- + +get_node_degree(Node, IG) -> + degree_get(Node, degree(IG)). + +dec_node_degree(Node, IG) -> + degree_dec(Node, degree(IG)), + IG. + +is_trivially_colourable(Node, K, IG) -> + degree_is_trivially_colourable(Node, K, degree(IG)). diff --git a/lib/hipe/regalloc/hipe_ig_moves.erl b/lib/hipe/regalloc/hipe_ig_moves.erl new file mode 100644 index 0000000000..186c87a690 --- /dev/null +++ b/lib/hipe/regalloc/hipe_ig_moves.erl @@ -0,0 +1,81 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%============================================================================= + +-module(hipe_ig_moves). +-export([new/1, + new_move/3, + get_moves/1]). + +-include("../util/hipe_vectors.hrl"). + +%%----------------------------------------------------------------------------- +%% The main data structure; its fields are: +%% - movelist : mapping from temp to set of associated move numbers +%% - nrmoves : number of distinct move instructions seen so far +%% - moveinsns : list of move instructions, in descending move number order +%% - moveset : set of move instructions + +-record(ig_moves, {movelist :: hipe_vector(), + nrmoves = 0 :: non_neg_integer(), + moveinsns = [] :: [{_,_}], + moveset = gb_sets:empty() :: gb_set()}). + +%%----------------------------------------------------------------------------- + +-spec new(non_neg_integer()) -> #ig_moves{}. + +new(NrTemps) -> + MoveList = hipe_vectors:new(NrTemps, ordsets:new()), + #ig_moves{movelist = MoveList}. + +-spec new_move(_, _, #ig_moves{}) -> #ig_moves{}. + +new_move(Dst, Src, IG_moves) -> + MoveSet = IG_moves#ig_moves.moveset, + MoveInsn = {Dst, Src}, + case gb_sets:is_member(MoveInsn, MoveSet) of + true -> + IG_moves; + false -> + MoveNr = IG_moves#ig_moves.nrmoves, + Movelist0 = IG_moves#ig_moves.movelist, + Movelist1 = add_movelist(MoveNr, Dst, + add_movelist(MoveNr, Src, Movelist0)), + IG_moves#ig_moves{nrmoves = MoveNr+1, + movelist = Movelist1, + moveinsns = [MoveInsn|IG_moves#ig_moves.moveinsns], + moveset = gb_sets:insert(MoveInsn, MoveSet)} + end. + +-spec add_movelist(non_neg_integer(), non_neg_integer(), hipe_vector()) -> hipe_vector(). + +add_movelist(MoveNr, Temp, MoveList) -> + AssocMoves = hipe_vectors:get(MoveList, Temp), + %% XXX: MoveNr does not occur in moveList[Temp], but the new list must be an + %% ordset due to the ordsets:union in hipe_coalescing_regalloc:combine(). + hipe_vectors:set(MoveList, Temp, ordsets:add_element(MoveNr, AssocMoves)). + +-spec get_moves(#ig_moves{}) -> {hipe_vector(), non_neg_integer(), tuple()}. + +get_moves(IG_moves) -> % -> {MoveList, NrMoves, MoveInsns} + {IG_moves#ig_moves.movelist, + IG_moves#ig_moves.nrmoves, + list_to_tuple(lists:reverse(IG_moves#ig_moves.moveinsns))}. diff --git a/lib/hipe/regalloc/hipe_ls_regalloc.erl b/lib/hipe/regalloc/hipe_ls_regalloc.erl new file mode 100644 index 0000000000..d06b938bea --- /dev/null +++ b/lib/hipe/regalloc/hipe_ls_regalloc.erl @@ -0,0 +1,788 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%% ===================================================================== +%% @doc +%% 
+%%  Module   :	hipe_ls_regalloc
+%%  Purpose  :  Perform a register allocation based on the 
+%%              "linear-scan algorithm".
+%%  Notes    :  * This is an implementation of 
+%%                "Linear Scan Register Allocation" by 
+%%                Massimiliano Poletto & Vivek Sarkar described in
+%%                ACM TOPLAS Vol 21, No 5, September 1999.
+%%
+%%              * This implementation is target-independent and
+%%                requires a target specific interface module
+%%                as argument.  
+%%                (Still waiting for a modular module system for Erlang.)
+%%
+%% @end +%% +%% History : * 2000-04-07 Erik Johansson (happi@it.uu.se): Created. +%% * 2001-07-16 Erik Johansson: Made less sparc-specific. +%% ===================================================================== +%% Exported functions (short description): +%% regalloc(CFG,PhysRegs,Entrypoints, Options) -> +%% {Coloring, NumberOfSpills} +%% Takes a CFG and returns a coloring of all used registers. +%% PhysRegs should be a list of available physical registers. +%% Entrypoints should be a list of names of Basic Blocks that have +%% external entry points. +%% +%% The Coloring will be in the form of the "allocation datastructure" +%% described below, that is, a list of tuples on the form +%% {Name, {reg, PhysicalRegister}} or +%% {Name, {spill, SpillIndex}} +%% The NumberOfSpills is either 0 indicating no spill or the +%% SpillIndex of the last spilled register. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-module(hipe_ls_regalloc). +-export([regalloc/7]). + +%%-define(DEBUG,1). +-define(HIPE_INSTRUMENT_COMPILER, true). + +-include("../main/hipe.hrl"). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% @spec +%% regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, +%% Target) -> +%% {Coloring, NumberOfSpills} +%% CFG = cfg() +%% PhysRegs = [reg()] +%% Entrypoints = [labelname()] +%% DontSpill = reg() +%% Options = proplist:proplist() +%% Target = atom() +%% Coloring = [{temp(), pos()}] +%% NumberOfSpills = integer() +%% reg() = integer() +%% temp() = integer() +%% pos() = {reg, reg()} | {spill, integer()} +%% +%% @doc +%% Calculates an allocation of registers using a linear_scan algorithm. +%% There are three steps in the algorithm: +%%
    +%%
  1. Calculate live-ranges for all registers.
    2. +%%
  2. Calculate live-intervals for each register. +%% The live interval consists of a start position and an end +%% position. These are the first definition and last use of the +%% register given as instruction numbers in a breadth-first +%% traversal of the control-flow-graph.
    3. +%%
  3. Perform a linear scan allocation over the live intervals.
    4. +%%
+%% @end +%%- - - - - - - - - - - - - - - - - - - - - - - - +regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) -> + ?debug_msg("LinearScan: ~w\n", [erlang:statistics(runtime)]), + %% Step 1: Calculate liveness (Call external implementation.) + Liveness = liveness(CFG, Target), + ?debug_msg("liveness (done)~w\n", [erlang:statistics(runtime)]), + USIntervals = calculate_intervals(CFG, Liveness, + Entrypoints, Options, Target), + ?debug_msg("intervals (done) ~w\n", [erlang:statistics(runtime)]), + Intervals = sort_on_start(USIntervals), + ?debug_msg("sort intervals (done) ~w\n", [erlang:statistics(runtime)]), + %% ?debug_msg("Intervals ~w\n", [Intervals]), + ?debug_msg("No intervals: ~w\n",[length(Intervals)]), + ?debug_msg("count intervals (done) ~w\n", [erlang:statistics(runtime)]), + Allocation = allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target), + ?debug_msg("allocation (done) ~w\n", [erlang:statistics(runtime)]), + Allocation. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% Step 2: Calculate live-intervals for each register. %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% calculate_intervals(CFG,Liveness,Entrypoints, Options, Target) +%% CFG: The Control-Flow Graph. +%% Liveness: A map of live-in and live-out sets for each Basic-Block. +%% Entrypoints: A set of BB names that have external entrypoints. +%% +calculate_intervals(CFG,Liveness,_Entrypoints, Options, Target) -> + %% Add start point for the argument registers. + Args = arg_vars(CFG, Target), + Interval = + add_def_point(Args, 0, empty_interval(Target:number_of_temporaries(CFG))), + %% Interval = add_livepoint(Args, 0, empty_interval()), + Worklist = + case proplists:get_value(ls_order, Options) of + reversepostorder -> + Target:reverse_postorder(CFG); + breadth -> + Target:breadthorder(CFG); + postorder -> + Target:postorder(CFG); + inorder -> + Target:inorder(CFG); + reverse_inorder -> + Target:reverse_inorder(CFG); + preorder -> + Target:preorder(CFG); + prediction -> + Target:predictionorder(CFG); + random -> + Target:labels(CFG); + _ -> + Target:reverse_postorder(CFG) + end, + %% ?inc_counter(bbs_counter, length(Worklist)), + %% ?debug_msg("No BBs ~w\n",[length(Worklist)]), + intervals(Worklist, Interval, 1, CFG, Liveness, Target). + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% intervals(WorkList, Intervals, InstructionNr, CFG, Liveness, Target) +%% WorkList: List of BB-names to handle. +%% Intervals: Intervals seen so far (sorted on register names). +%% InstructionNr: The number of examined insturctions. +%% CFG: The Control-Flow Graph. +%% Liveness: A map of live-in and live-out sets for each Basic-Block. +%% Target: The backend for which we generate code. +%%- - - - - - - - - - - - - - - - - - - - - - - - +intervals([L|ToDO], Intervals, InstructionNr, CFG, Liveness, Target) -> + %% Add all variables that are live at the entry of this block + %% to the interval data structure. + LiveIn = livein(Liveness, L, Target), + Intervals2 = add_def_point(LiveIn, InstructionNr, Intervals), + LiveOut = liveout(Liveness, L, Target), + + %% Traverse this block instruction by instruction and add all + %% uses and defines to the intervals. + Code = hipe_bb:code(bb(CFG, L, Target)), + {Intervals3, NewINr} = + traverse_block(Code, InstructionNr+1, Intervals2, Target), + + %% Add end points for the registers that are in the live-out set. + Intervals4 = add_use_point(LiveOut, NewINr+1, Intervals3), + + intervals(ToDO, Intervals4, NewINr+1, CFG, Liveness, Target); +intervals([], Intervals, _, _, _, _) -> + %% Return the calculated intervals + LI = interval_to_list(Intervals), + %% io:format("Intervals:~n~p~n", [LI]), + LI. + +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% traverse_block(Code, InstructionNo, Intervals, Unchanged) +%% Examine each instruction in the Code: +%% For each temporary T used or defined by instruction number N: +%% extend the interval of T to include N. +%%- - - - - - - - - - - - - - - - - - - - - - - - +traverse_block([Instruction|Is],InstrNo,Intervals, Target) -> + %% Get defined temps. + DefsSet = defines(Instruction, Target), + Intervals1 = add_def_point(DefsSet, InstrNo, Intervals), + + %% Get used temps. + UsesSet = uses(Instruction, Target), + %% Extend the intervals for these temporaries to include InstrNo. + Intervals2 = add_use_point(UsesSet, InstrNo, Intervals1), + + %% Handle the next instruction. + traverse_block(Is,InstrNo+1,Intervals2,Target); +traverse_block([], InstrNo, Intervals, _) -> + %% Return the new intervals and the number of the next instruction. + {Intervals,InstrNo}. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% Step 3. Do a linear scan allocation over the live intervals. %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% allocate(Intervals, PhysicalRegisters, DontSpill, Target) +%% +%% This function performs the linear scan algorithm. +%% Intervals contains the start and stop position of each register, +%% sorted on increasing startpositions +%% PhysicalRegisters is a list of available Physical registers to use. +%% +%%- - - - - - - - - - - - - - - - - - - - - - - - +allocate(Intervals, PhysRegs, SpillIndex, DontSpill, Target) -> + ActiveRegisters =[], + AllocatedRegisters = empty_allocation(), + AllFree = create_freeregs(PhysRegs), + allocate(Intervals, AllFree, ActiveRegisters, + AllocatedRegisters, SpillIndex, DontSpill, Target). +%%- - - - - - - - - - - - - - - - - - - - - - - - +%% allocate(Intervals, Free, Active, Allocated, SpillIndex, Target) +%% Iterates of each register interval. +%% Intervals: The list of register intervals. +%% Free: Currently available physical registers. +%% Active: Currently used physical registers (sorted on increasing +%% interval enpoints) +%% Allocated: The mapping of register names to physical registers or +%% to spill positions. +%% SpillIndex: The number of spilled registers. +%%- - - - - - - - - - - - - - - - - - - - - - - - +allocate([RegInt|RIS], Free, Active, Alloc, SpillIndex, DontSpill, Target) -> + %io:format("~nAlloc:~n~p", [Alloc]), + %% Remove from the active list those registers who's intervals + %% ends before the start of the current interval. + {NewActive, NewFree} = + expire_old_intervals(Active, startpoint(RegInt), Free, Target), + ?debug_msg("Alloc interval: ~w, Free ~w\n",[RegInt, NewFree]), + %% Get the name of the temp in the current interval. + Temp = reg(RegInt), + case is_precoloured(Temp, Target) of + true -> + %% This is a precoloured register we don't need to find a color + %% Get the physical name of the register. + PhysName = physical_name(Temp, Target), + %% Bind it to the precoloured name. + NewAlloc = alloc(Temp, PhysName, Alloc), + case is_global(Temp, Target) of + true -> + %% this is a global precoloured register + allocate(RIS, NewFree, NewActive, + NewAlloc, SpillIndex, DontSpill, Target); + false -> + case is_free(PhysName, NewFree) of + {true,Rest} -> + allocate(RIS, Rest, + add_active(endpoint(RegInt), startpoint(RegInt), + PhysName, Temp, NewActive), + NewAlloc, + SpillIndex, DontSpill, Target); + false -> + %% Some other temp has taken this precoloured register, + %% throw it out. + {OtherActive, NewActive2} = deactivate(PhysName, NewActive), + OtherTemp = active_name(OtherActive), + OtherEnd = active_endpoint(OtherActive), + OtherStart = active_startpoint(OtherActive), + NewActive3 = add_active(endpoint(RegInt), startpoint(RegInt), + PhysName, Temp, NewActive2), + case exists_free_register(OtherStart, NewFree) of + {true, NewPhys, RestFree} -> + allocate(RIS, RestFree, + add_active(OtherEnd, OtherStart, + NewPhys, OtherTemp, NewActive3), + alloc(OtherTemp,NewPhys,NewAlloc), + SpillIndex, DontSpill, Target); + false -> + NewSpillIndex = Target:new_spill_index(SpillIndex), + {NewAlloc2, NewActive4} = + spill(OtherTemp, OtherEnd, OtherStart, NewActive3, + NewAlloc, SpillIndex, DontSpill, Target), + allocate(RIS, + NewFree, + NewActive4, + NewAlloc2, NewSpillIndex, DontSpill, Target) + end + end + end; + false -> + %% This is not a precoloured register. + case NewFree of + [] -> + %% No physical registers available, we have to spill. + NewSpillIndex = Target:new_spill_index(SpillIndex), + {NewAlloc, NewActive2} = + spill(Temp, endpoint(RegInt), startpoint(RegInt), + Active, Alloc, SpillIndex, DontSpill, Target), + %% io:format("Spilled ~w\n",[NewAlloc]), + allocate(RIS, NewFree, NewActive2, NewAlloc, NewSpillIndex, + DontSpill, Target); + + [{FreeReg,_Start} | Regs] -> + %% The register FreeReg is available, let's use it. + %%io:format("Allocating Reg:~p~n",[FreeReg]), + allocate(RIS,Regs, + add_active(endpoint(RegInt), startpoint(RegInt), + FreeReg, Temp, NewActive), + alloc(Temp, FreeReg, Alloc), + SpillIndex, DontSpill, Target) + end + end; +allocate([],_,_,Alloc,SpillIndex, _, _) -> + %% No more register intervals to handle + %% return the result. + %%io:format("~nAlloc:~n~p", [Alloc]), + {Alloc, SpillIndex}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% expire_old_intervals(ActiveRegisters, CurrentPos, FreeRegisters) +%% Remove all registers that have live-ranges that ends before the +%% current position from the active list and put them into the free +%% list instead. +%% +%% --------------------------------------------------------------------- +expire_old_intervals([Act|Acts] = AllActives, CurrentPos, Free, Target) -> + %% Does the live-range of the first active register end before + %% the current position? + + %% We expand multimove before regalloc, ignore the next 2 lines. + %% %% We don't free registers that end at the current position, + %% %% since a multimove can decide to do the moves in another order... + case active_endpoint(Act) =< CurrentPos of + true -> %% Yes -> Then we can free that register. + Reg = active_reg(Act), + %% Add the register to the free pool. + NewFree = + case is_arg(Reg, Target) of + true -> + [{Reg, CurrentPos}|Free]; + false -> + [{Reg, CurrentPos}|Free] + %% Here we could try appending the + %% register to get a more widespread + %% use of registers. + %% Free ++ [active_reg(Act)]); + %% At the moment this does not seem to + %% improve performance at all, + %% on the other hand, the cost is very low. + end, + expire_old_intervals(Acts, CurrentPos, NewFree, Target); + false -> + %% No -> Then we cannot free any more registers. + %% (Since they are sorted on endpoints...) + {AllActives, Free} + end; +expire_old_intervals([], _, Free, _) -> + {[], Free}. + +deactivate(Reg, [Active|Actives]) -> + case Reg =:= active_reg(Active) of + true -> + {Active, Actives}; + false -> + {TheActive, NewActives} = deactivate(Reg, Actives), + {TheActive, [Active|NewActives]} + end; +deactivate(_,[]) -> {no,[]}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% spill(CurrentReg, CurrentEndpoint, Active, Alloc, SpillIndex, +%% DontSpill, Target) +%% Find the register with the longest live range and spill it to memory. +%% +%% --------------------------------------------------------------------- +spill(CurrentReg, CurrentEndpoint,CurrentStartpoint, + Active = [_|_], + Alloc, SpillIndex, + DontSpill, Target) -> + ?debug_msg("spilling one of ~w\nDOnt spill ~w\n", + [[CurrentReg|Active], DontSpill]), + + %% Find a spill candidate (one of the active): + %% The register with the longest live-range. + {NewActive, SpillCandidate} = butlast_last(Active), + + SpillStartpoint = active_startpoint(SpillCandidate) , + SpillEndpoint = active_endpoint(SpillCandidate) , + SpillName = active_name(SpillCandidate), + SpillPhysName = active_reg(SpillCandidate), + + case SpillEndpoint > CurrentEndpoint of + true -> + %% There is an already allocated register that has + %% a longer live-range than the current register. + case can_spill(SpillName, DontSpill, Target) and + (SpillStartpoint =< CurrentStartpoint) of + false -> + {NewAlloc, NewActive2} = + spill(CurrentReg, CurrentEndpoint, CurrentStartpoint, + NewActive, Alloc, SpillIndex, DontSpill, Target), + {NewAlloc, + add_active(SpillEndpoint, SpillStartpoint, SpillPhysName, + SpillName, NewActive2)}; + true -> + %% It is not precoloured... or have too short liverange + + %% Allocate SpillCandidate to spill-slot SpillIndex + SpillAlloc = + spillalloc(active_name(SpillCandidate), SpillIndex, + Alloc), + + %% Allocated the current register to the physical register + %% used by the spill candidate. + NewAlloc = alloc(CurrentReg, SpillPhysName, SpillAlloc), + + %% Add the current register to the active registers + NewActive2 = + add_active(CurrentEndpoint, CurrentStartpoint, + SpillPhysName, CurrentReg, NewActive), + {NewAlloc, NewActive2} + end; + + false -> + %% The current register has the longest live-range. + + case can_spill(CurrentReg, DontSpill, Target) of + false -> + %% Cannot spill a precoloured register + {NewAlloc, NewActive2} = + spill(SpillName, SpillEndpoint, SpillStartpoint, + NewActive, Alloc, SpillIndex, DontSpill, Target), + NewActive3 = + add_active(CurrentEndpoint, CurrentStartpoint, + SpillPhysName, CurrentReg, NewActive2), + {NewAlloc, NewActive3}; + true -> + %% It is not precoloured... + %% Allocate the current register to spill-slot SpillIndex + {spillalloc(CurrentReg, SpillIndex, Alloc), Active} + end + end; +spill(CurrentReg, _CurrentEndpoint, _CurrentStartpoint, [], + Alloc, SpillIndex, DontSpill, Target) -> + case can_spill(CurrentReg, DontSpill, Target) of + false -> %% Can't spill current! + ?error_msg("Can't allocate registers\n",[]), + ?EXIT({cannot_allocate_regs}); + true -> %% Can spill current. + %% Allocate the current register to spill-slot SpillIndex + {spillalloc(CurrentReg, SpillIndex, Alloc), []} + end. + +can_spill(Name, DontSpill, Target) -> + (Name < DontSpill) and (not is_precoloured(Name, Target)). + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% %% +%% D A T A S T R U C T U R E S %% +%% & %% +%% A U X I L I A R Y F U N C T I O N S %% +%% %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The "allocation datastructure" +%% +%% This is an order list of register names paired with their allocations. +%% {Name, Allocation} +%% The allocation is either {reg, physical register} or +%% {spill, spill index} +%% +%% --------------------------------------------------------------------- +empty_allocation() -> []. + +alloc(Name,Reg,[{Name,_}|A]) -> + [{Name,{reg,Reg}}|A]; +alloc(Name,Reg,[{Name2,Binding}|Bindings]) when Name > Name2 -> + [{Name2,Binding}|alloc(Name,Reg,Bindings)]; +alloc(Name,Reg,Bindings) -> + [{Name,{reg,Reg}}|Bindings]. + +spillalloc(Name,N,[{Name,_}|A]) -> + ?debug_msg("Spilled ~w\n",[Name]), + [{Name,{spill,N}}|A]; +spillalloc(Name,N,[{Name2,Binding}|Bindings]) when Name > Name2 -> + [{Name2,Binding}|spillalloc(Name,N,Bindings)]; +spillalloc(Name,N,Bindings) -> + [{Name,{spill,N}}|Bindings]. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% +butlast_last([X]) -> + {[],X}; +butlast_last([X|Y]) -> + {L,Last} = butlast_last(Y), + {[X|L],Last}. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% The active datastructure. +%% Keeps tracks of currently active (allocated) physical registers. +%% It is sorted on end points in the intervals +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +add_active(Endpoint, StartPoint, PhysReg, RegName, + [{P1,R1,O1,S1}|Active]) when P1 < Endpoint -> + [{P1,R1,O1,S1}|add_active(Endpoint, StartPoint, PhysReg, RegName, Active)]; +add_active(Endpoint, StartPoint, PhysReg, RegName, Active) -> + [{Endpoint, PhysReg, RegName, StartPoint}|Active]. + +active_reg({_,PhysReg,_,_}) -> + PhysReg. +active_endpoint({EndPoint,_,_,_}) -> + EndPoint. +active_startpoint({_,_,_,StartPoint}) -> + StartPoint. +active_name({_,_,RegName,_}) -> + RegName. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The Interval data structure. +%% +%% +%%- - - - - - - - - - - - - - - - - - - - - - - - + +%% mk_interval(Name, Start, End) -> +%% {Name, Start, End}. + +endpoint({_R,_S,Endpoint}) -> + Endpoint. +startpoint({_R,Startpoint,_E}) -> + Startpoint. +reg({RegName,_S,_E}) -> + RegName. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The Intervals data structure. + +sort_on_start(I) -> + lists:keysort(2, I). + +-ifdef(gb_intervals). +empty_interval(_) -> + gb_trees:empty(). + +interval_to_list(Intervals) -> + lists:flatten( + lists:map( + fun({T, I}) when list(I) -> + lists:map( + fun ({none, End}) -> + {T,End,End}; + ({Beg, none}) -> + {T,Beg, Beg} + end, + I); + ({T,{B,E}}) -> {T, B, E} + end, + gb_trees:to_list(Intervals))). + +add_use_point([Temp|Temps],Pos,Intervals) -> + %% Extend the old interval... + NewInterval = + case gb_trees:lookup(Temp, Intervals) of + %% This temp has an old interval... + {value, Value} -> + %% ... extend it. + extend_interval(Pos, Value); + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos} + end, + %% Add or update the extended interval. + Intervals2 = gb_trees:enter(Temp, NewInterval, Intervals), + %% Add the rest of teh temporaries. + add_use_point(Temps, Pos, Intervals2); +add_use_point([], _, I) -> + %% No more to add return the interval. + I. + +add_def_point([Temp|Temps],Pos,Intervals) -> + %% Extend the old interval... + NewInterval = + case gb_trees:lookup(Temp, Intervals) of + %% This temp has an old interval... + {value, Value} -> + %% ... extend it. + extend_interval(Pos, Value); + + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos} + end, + %% Add or update the extended interval. + Intervals2 = gb_trees:enter(Temp, NewInterval, Intervals), + %% Add the rest of the temporaries. + add_def_point(Temps, Pos, Intervals2); +add_def_point([], _, I) -> + %% No more to add return the interval. + I. + +extend_interval(Pos, {Beginning, End}) -> + %% If this position occures before the beginning + %% of the interval, then extend the beginning to + %% this position. + NewBeginning = erlang:min(Pos, Beginning), + %% If this position occures after the end + %% of the interval, then extend the end to + %% this position. + NewEnd = erlang:max(Pos, End), + {NewBeginning, NewEnd}. + +-else. %% isdef gb_intervals + +empty_interval(N) -> + hipe_vectors:new(N, none). + +interval_to_list(Intervals) -> + add_indices(hipe_vectors:vector_to_list(Intervals),0). + +add_indices([{B,E}|Xs],N) -> + [{N,B,E}|add_indices(Xs,N+1)]; +add_indices([List|Xs],N) when is_list(List) -> + flatten(List,N,Xs); +add_indices([none|Xs],N) -> + add_indices(Xs,N+1); +add_indices([],_N) -> []. + +flatten([{none, End}|Rest], N, More) -> + [{N,End,End} | flatten(Rest, N, More)]; +flatten([{Beg, none}|Rest], N ,More) -> + [{N,Beg,Beg} | flatten(Rest, N, More)]; +flatten([],N,More) -> + add_indices(More,N+1). + +add_use_point([Temp|Temps],Pos,Intervals) -> + %% Extend the old interval... + NewInterval = + case hipe_vectors:get(Intervals, Temp) of + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos}; + %% This temp has an old interval... + Value -> + %% ... extend it. + extend_interval(Pos, Value) + end, + %% Add or update the extended interval. + Intervals2 = hipe_vectors:set(Intervals, Temp, NewInterval), + %% Add the rest of the temporaries. + add_use_point(Temps, Pos, Intervals2); +add_use_point([], _, I) -> + %% No more to add return the interval. + I. + +add_def_point([Temp|Temps],Pos,Intervals) -> + %% Extend the old interval... + NewInterval = + case hipe_vectors:get(Intervals, Temp) of + %% This is the first time we see this temp... + none -> + %% ... create a new interval + {Pos, Pos}; + %% This temp has an old interval... + Value -> + %% ... extend it. + extend_interval(Pos, Value) + end, + %% Add or update the extended interval. + Intervals2 = hipe_vectors:set(Intervals, Temp, NewInterval), + %% Add the rest of teh temporaries. + add_def_point(Temps, Pos, Intervals2); +add_def_point([], _, I) -> + %% No more to add return the interval. + I. + +extend_interval(Pos, {Beginning, End}) -> + %% If this position occurs before the beginning of the interval, + %% then extend the beginning to this position. + NewBeginning = erlang:min(Pos, Beginning), + %% If this position occures after the end + %% of the interval, then extend the end to + %% this position. + NewEnd = erlang:max(Pos, End), + {NewBeginning, NewEnd}. +-endif. %% gb_intervals + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% The Freel data structure. +%% +%%- - - - - - - - - - - - - - - - - - - - - - - - + +is_free(R, Free) -> + is_free(R, Free, []). + +is_free(R, [{R,_}|Rest], Acc) -> + {true,lists:reverse(Acc)++Rest}; +is_free(R, [X|Rs],Acc) -> + is_free(R, Rs, [X|Acc]); +is_free(_, [], _) -> + false. + +exists_free_register(Start, Regs) -> + exists_free_register(Start, Regs, []). + +exists_free_register(Start, [{Phys, Start0}|Rest], Acc) + when Start > Start0 -> + {true, Phys, lists:reverse(Acc)++Rest}; +exists_free_register(Start, [Free|Rest], Acc) -> + exists_free_register(Start, Rest, [Free|Acc]); +exists_free_register(_, [], _) -> + false. + +create_freeregs([Phys|Rest]) -> + [{Phys,-1}|create_freeregs(Rest)]; +create_freeregs([]) -> + []. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% +%% Interface to external functions. +%% XXX: Make this efficient somehow... +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +liveness(CFG, Target) -> + Target:analyze(CFG). + +bb(CFG, L, Target) -> + Target:bb(CFG,L). + +livein(Liveness,L, Target) -> + regnames(Target:livein(Liveness,L), Target). + +liveout(Liveness,L, Target) -> + regnames(Target:liveout(Liveness,L), Target). + +uses(I, Target) -> + regnames(Target:uses(I), Target). + +defines(I, Target) -> + regnames(Target:defines(I), Target). + +is_precoloured(R, Target) -> + Target:is_precoloured(R). + +is_global(R, Target) -> + Target:is_global(R). + +physical_name(R, Target) -> + Target:physical_name(R). + +regnames(Regs, Target) -> + [Target:reg_nr(X) || X <- Regs]. + +arg_vars(CFG, Target) -> + Target:args(CFG). + +is_arg(Reg, Target) -> + Target:is_arg(Reg). diff --git a/lib/hipe/regalloc/hipe_moves.erl b/lib/hipe/regalloc/hipe_moves.erl new file mode 100644 index 0000000000..afec4aa4ce --- /dev/null +++ b/lib/hipe/regalloc/hipe_moves.erl @@ -0,0 +1,165 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_moves). +-export([new/1, + update_movelist/3, + node_moves/2, + move_related/2, + node_movelist/2, + get_move/2, + is_empty_worklist/1, + worklist_get_and_remove/1, + remove_worklist/2, + remove_active/2, + add_worklist/2, + add_active/2, + member_active/2 + ]). +-ifdef(DEBUG_PRINTOUTS). +-export([print_memberships/1]). +-endif. + +-record(movesets, + {worklist, % Moves enabled for possible coalescing + membership, % Maps move numbers to 'worklist' or 'active' or 'none' + moveinsns, % Maps move numbers to move insns ({Dst,Src}-tuples) + movelist % Mapping from node to list of moves it's associated with + }). + +%%-ifndef(DEBUG). +%%-define(DEBUG,true). +%%-endif. +-include("../main/hipe.hrl"). + +worklist(MoveSets) -> MoveSets#movesets.worklist. +movelist(MoveSets) -> MoveSets#movesets.movelist. + +set_worklist(New_worklist, MoveSets) -> + MoveSets#movesets{worklist = New_worklist}. +set_movelist(New_movelist, MoveSets) -> + MoveSets#movesets{movelist = New_movelist}. + +update_movelist(Node, MoveList, MoveSets) -> + set_movelist(hipe_vectors:set(movelist(MoveSets), Node, MoveList), + MoveSets). + +new(IG) -> + {MoveList,NrMoves,MoveInsns} = hipe_ig:get_moves(IG), + Worklist = case NrMoves of 0 -> []; _ -> lists:seq(0, NrMoves-1) end, + #movesets{worklist = Worklist, + membership = hipe_bifs:array(NrMoves, 'worklist'), + moveinsns = MoveInsns, + movelist = MoveList}. + +remove_worklist(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'worklist' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'none'), + %% Implementing this faithfully would require a SET structure, such + %% as an ordset or a gb_set. However, removal of elements not at the + %% head of the structure is a fairly infrequent event (only done by + %% FreezeMoves()), so instead we let the elements remain but mark + %% them as being removed. It is the task of worklist_get_and_remove() + %% to filter out any stale elements. + MoveSets. + +remove_active(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'active' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'none'), + MoveSets. + +add_worklist(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'none' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'worklist'), + set_worklist([Element | worklist(MoveSets)], MoveSets). + +add_active(Element, MoveSets) -> + Membership = MoveSets#movesets.membership, + %% check for 'none' membership here, if debugging + hipe_bifs:array_update(Membership, Element, 'active'), + MoveSets. + +member_active(Element, MoveSets) -> + hipe_bifs:array_sub(MoveSets#movesets.membership, Element) =:= 'active'. + +is_empty_worklist(MoveSets) -> + %% This is an approximation. See worklist_get_and_remove(). + worklist(MoveSets) =:= []. + +worklist_get_and_remove(MoveSets) -> + worklist_get_and_remove(worklist(MoveSets), MoveSets#movesets.membership, MoveSets). + +worklist_get_and_remove([], _Membership, MoveSets) -> + {[], set_worklist([], MoveSets)}; +worklist_get_and_remove([Move|Worklist], Membership, MoveSets) -> + case hipe_bifs:array_sub(Membership, Move) of + 'worklist' -> + hipe_bifs:array_update(Membership, Move, 'none'), + {Move, set_worklist(Worklist, MoveSets)}; + _ -> + worklist_get_and_remove(Worklist, Membership, MoveSets) + end. + +node_moves(Node, MoveSets) -> + Associated = node_movelist(Node, MoveSets), + Membership = MoveSets#movesets.membership, + %% The ordsets:union() in hipe_coalescing_regalloc:combine() + %% constrains us to return an ordset here. + [X || X <- Associated, hipe_bifs:array_sub(Membership, X) =/= 'none']. + +move_related(Node, MoveSets) -> + %% Same as node_moves(Node, MoveSets) =/= [], but less expensive to compute. + %% XXX: George&Appel'96 hints that this should be maintained as a per-node counter. + move_related2(node_movelist(Node, MoveSets), MoveSets#movesets.membership). + +move_related2([], _Membership) -> false; +move_related2([Move|MoveSets], Membership) -> + case hipe_bifs:array_sub(Membership, Move) of + 'none' -> move_related2(MoveSets, Membership); + _ -> true % 'active' or 'worklist' + end. + +node_movelist(Node, MoveSets) -> + hipe_vectors:get(movelist(MoveSets), Node). + +get_move(Move, MoveSets) -> + element(Move+1, MoveSets#movesets.moveinsns). + +%%---------------------------------------------------------------------- +%% Print functions - only used for debugging + +-ifdef(DEBUG_PRINTOUTS). +print_memberships(MoveSets) -> + ?debug_msg("Move memeberships:\n", []), + Membership = MoveSets#movesets.membership, + NrMoves = hipe_bifs:array_length(Membership), + print_membership(NrMoves, Membership). + +print_membership(0, _) -> + true; +print_membership(Element, Membership) -> + NextElement = Element - 1, + ?debug_msg("move ~w ~w\n", [NextElement, hipe_bifs:array_sub(Membership, NextElement)]), + print_membership(NextElement, Membership). +-endif. + diff --git a/lib/hipe/regalloc/hipe_node_sets.erl b/lib/hipe/regalloc/hipe_node_sets.erl new file mode 100644 index 0000000000..b5e2971c4d --- /dev/null +++ b/lib/hipe/regalloc/hipe_node_sets.erl @@ -0,0 +1,48 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_node_sets). + +-export([new/0, + spilled/1, + colored/1, + add_spilled/2, + add_colored/2 + ]). + +-record(node_sets, + {spilled, % Nodes marked for spilling + colored % Nodes succesfully colored + }). + +spilled(Node_sets) -> Node_sets#node_sets.spilled. +colored(Node_sets) -> Node_sets#node_sets.colored. + +set_spilled(Spilled, Node_sets) -> Node_sets#node_sets{spilled = Spilled}. +set_colored(Colored, Node_sets) -> Node_sets#node_sets{colored = Colored}. + +new() -> + #node_sets{spilled = [], colored = []}. + +add_spilled(Node, Node_sets) -> + set_spilled([Node | spilled(Node_sets)], Node_sets). + +add_colored(Node, Node_sets) -> + set_colored([Node | colored(Node_sets)], Node_sets). diff --git a/lib/hipe/regalloc/hipe_optimistic_regalloc.erl b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl new file mode 100644 index 0000000000..183ec1994c --- /dev/null +++ b/lib/hipe/regalloc/hipe_optimistic_regalloc.erl @@ -0,0 +1,2043 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2005-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%%----------------------------------------------------------------------- +%% File : hipe_optimistic_regalloc.erl +%% Authors : NilsOla Linnermark +%% Petter Holmberg +%% Purpose : Play paintball with registers on a target machine. We win +%% if they are all colored. This is an optimistic coalescing +%% register allocator. +%% Created : Spring 2005 +%%----------------------------------------------------------------------- + +-module(hipe_optimistic_regalloc). +-export([regalloc/5]). + +-ifndef(DEBUG). +%%-define(DEBUG,true). +-else. +-ifndef(COMPARE_ITERATED_OPTIMISTIC). +%% If this macro is turned on you can easily compare +%% each intermediate step in the iterated coalescing +%% register allocator and the optimitsitc coalescing +%% register allocator. This is useful for debugging - +%% many small erlang functions should render the same +%% register allocaton for both allocators. +-define(COMPARE_ITERATED_OPTIMISTIC, true). +-endif. +-endif. +-include("../main/hipe.hrl"). +-ifdef(DEBUG_PRINTOUTS). +-define(print_adjacent(IG), hipe_ig:print_adjacent(IG)). +-define(print_degrees(IG), hipe_ig:print_degrees(IG)). +-define(print_spill_costs(IG), hipe_ig:print_spill_costs(IG)). +-define(mov_print_memberships(MV), hipe_moves:print_memberships(MV)). +-define(reg_print_memberships(WL), hipe_reg_worklists:print_memberships(WL)). +-define(print_alias(A), printAlias(A)). +-define(print_colors(T,C), printColors(T,C)). +-else. +-define(print_adjacent(IG), no_print). +-define(print_degrees(IG), no_print). +-define(print_spill_costs(IG), no_print). +-define(mov_print_memberships(MV), no_print). +-define(reg_print_memberships(WL), no_print). +-define(print_alias(A), no_print). +-define(print_colors(T,C), no_print). +-endif. + + +%%----------------------------------------------------------------------- +%% Function: regalloc +%% +%% Description: Creates a K coloring for a function. +%% Parameters: +%% CFG -- A control flow graph +%% SpillIndex -- Last index of spill variable +%% SpillLimit -- Temporaris with numbers higher than this have +%% infinit spill cost. +%% Consider changing this to a set. +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% Coloring -- A coloring for specified CFG +%% SpillIndex0 -- A new spill index +%%----------------------------------------------------------------------- +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> + ?debug_msg("optimistic ~w\n",[Target]), + ?debug_msg("CFG: ~p\n",[CFG]), + %% Build interference graph + ?debug_msg("Build IG\n",[]), + IG_O = hipe_ig:build(CFG, Target), + IG = hipe_ig:build(CFG, Target), + ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), + ?debug_msg("IG:\n",[]), + ?print_adjacent(IG), + ?print_degrees(IG), + ?print_spill_costs(IG), + + SavedSpillCosts = hipe_ig:spill_costs(IG), + SavedAdjList = hipe_ig:adj_list(IG), + + ?debug_msg("Init\n",[]), + No_temporaries = Target:number_of_temporaries(CFG), + ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]), + Allocatable = Target:allocatable(), + K = length(Allocatable), + All_colors = colset_from_list(Allocatable), + ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), + + %% Add registers with their own coloring + ?debug_msg("Moves\n",[]), + Move_sets_O = hipe_moves:new(IG_O), + Move_sets = hipe_moves:new(IG), + ?debug_msg("Move_sets:\n ~p\n",[Move_sets]), + ?mov_print_memberships(Move_sets), + + ?debug_msg("Build Worklist\n",[]), + Worklists_O = hipe_reg_worklists:new(IG_O, Target, CFG, Move_sets_O, K, No_temporaries), + ?debug_msg("Worklists:\n ~p\n", [Worklists_O]), + ?reg_print_memberships(Worklists_O), + + Worklists = hipe_reg_worklists:new(IG, Target, CFG, K, No_temporaries), + ?debug_msg("New Worklists:\n ~p\n", [Worklists]), + ?reg_print_memberships(Worklists), + + Alias_O = initAlias(No_temporaries), + Alias = initAlias(No_temporaries), + ?print_alias(Alias), + + ?debug_msg("Do coloring\n~p~n",[Worklists_O]), + {IG0_O, Worklists0_O, Moves0_O, Alias0_O} = + do_coloring(IG_O, Worklists_O, Move_sets_O, Alias_O, + K, SpillLimit, Target), + ?debug_msg("IG_O after color:\n ~p\n",[IG0_O]), + ?print_adjacent(IG0_O), + ?print_degrees(IG0_O), + ?print_spill_costs(IG0_O), + ?debug_msg("Move_sets after color:\n ~p\n",[Moves0_O]), + ?mov_print_memberships(Moves0_O), + ?debug_msg("Worklists after color:\n ~p\n", [Worklists0_O]), + ?reg_print_memberships(Worklists0_O), + + {IG0, Moves0, Alias0, Worklists0} = + do_coalescing(IG, Worklists, Move_sets, Alias, K, Target), + ?debug_msg("IG after coalescing:\n",[]), + ?print_adjacent(IG0), + ?print_degrees(IG0), + ?print_spill_costs(IG0), + ?debug_msg("Move_sets after coalescing:\n ~p\n",[Moves0]), + ?mov_print_memberships(Moves0), + ?debug_msg("New Worklists after coalescing:\n ~p\n", + [Worklists0]), + ?reg_print_memberships(Worklists0), + + {IG1, Worklists1, Moves1, Alias1} = + do_simplify_or_spill(IG0, Worklists0, Moves0, Alias0, + K, SpillLimit, Target), + ?debug_msg("IG after simplify_or_spill:\n",[]), + ?print_adjacent(IG1), + ?print_degrees(IG1), + ?print_spill_costs(IG1), + ?debug_msg("Saved spill costs ~p~n", [SavedSpillCosts]), + ?debug_msg("Move_sets after simplify_or_spill:\n ~p\n",[Moves1]), + ?mov_print_memberships(Moves1), + ?debug_msg("New Worklists after simplify_or_spill:\n ~p\n", + [Worklists1]), + ?reg_print_memberships(Worklists1), + ?print_alias(Alias1), + + %% only for testing undoCoalescing and member_coalesced_to + %test_undoCoalescing(No_temporaries, Alias1, Worklists1), + + %% only for testing fixAdj + %?debug_msg("adj_lists_before_fixAdj ~n~p~n", [hipe_ig:adj_list(IG1)]), + %IG2 = test_fixAdj(No_temporaries, SavedAdjList, IG1, Target), + %?debug_msg("adj_lists__after_fixAdj ~n~p~n", [hipe_ig:adj_list(IG2)]), + + ?debug_msg("Init node sets\n",[]), + Node_sets = hipe_node_sets:new(), + %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]), + ?debug_msg("Default coloring\n",[]), + {Color0,Node_sets1} = + defaultColoring(Target:all_precoloured(), + initColor(No_temporaries), Node_sets, Target), + ?debug_msg("Color0\n",[]), + ?print_colors(No_temporaries, Color0), + + ?debug_msg("----------------------Assign colors _N\n",[]), + + Stack = hipe_reg_worklists:stack(Worklists1), + ?debug_msg("The stack _N ~p~n", [Stack]), + %SortedStack = sort_stack(Stack), + %?debug_msg("The stack _N ~p~n", [SortedStack]), + + %?debug_msg("Nodes _N ~w~n", [Node_sets1]), + + {Color1,Node_sets2,Alias2} = + assignColors(Worklists1, Stack, Node_sets1, Color0, + No_temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, All_colors, Target), + ?print_colors(No_temporaries, Color1), + ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), + + ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), + Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), + ?debug_msg("Coloring ~p\n",[Coloring]), + SortedColoring = { sort_stack(element(1, Coloring)), element(2, Coloring)}, + ?debug_msg("SortedColoring ~p\n",[SortedColoring]), + %%Coloring. + ?debug_msg("----------------------Assign colors _O\n",[]), + {Color1_O,Node_sets2_O} = + assignColors_O(hipe_reg_worklists:stack(Worklists0_O), Node_sets1, Color0, + Alias0_O, All_colors, Target), + ?print_colors(No_temporaries, Color1_O), + ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2_O,No_temporaries]), + + ?debug_msg("Build mapping ~w\n",[Node_sets2_O]), + Coloring_O = build_namelist_O(Node_sets2_O,SpillIndex,Alias0_O,Color1_O), + ?debug_msg("Coloring_O ~p\n",[Coloring_O]), + SortedColoring_O = {sort_stack(element(1, Coloring_O)), element(2, Coloring_O)}, + ?debug_msg("SortedColoring_O ~p\n",[SortedColoring_O]), + sanity_compare(SortedColoring_O, SortedColoring), + Coloring. +-else. +regalloc(CFG, SpillIndex, SpillLimit, Target, _Options) -> + ?debug_msg("optimistic ~w\n",[Target]), + ?debug_msg("CFG: ~p\n",[CFG]), + %% Build interference graph + ?debug_msg("Build IG\n",[]), + IG = hipe_ig:build(CFG, Target), + ?debug_msg("adjlist: ~p\n",[hipe_ig:adj_list(IG)]), + ?debug_msg("IG:\n",[]), + ?print_adjacent(IG), + ?print_degrees(IG), + ?print_spill_costs(IG), + + SavedSpillCosts = hipe_ig:spill_costs(IG), + SavedAdjList = hipe_ig:adj_list(IG), + + ?debug_msg("Init\n",[]), + No_temporaries = Target:number_of_temporaries(CFG), + ?debug_msg("Coalescing RA: num_temps = ~p~n", [No_temporaries]), + Allocatable = Target:allocatable(), + K = length(Allocatable), + All_colors = colset_from_list(Allocatable), + ?debug_msg("K: ~w~nAll_colors: ~p\n",[K, All_colors]), + + %% Add registers with their own coloring + ?debug_msg("Moves\n",[]), + Move_sets = hipe_moves:new(IG), + ?debug_msg("Move_sets:\n ~p\n",[Move_sets]), + ?mov_print_memberships(Move_sets), + + ?debug_msg("Build Worklist\n",[]), + + Worklists = hipe_reg_worklists:new(IG, Target, CFG, K, No_temporaries), + ?debug_msg("New Worklists:\n ~p\n", [Worklists]), + ?reg_print_memberships(Worklists), + + Alias = initAlias(No_temporaries), + ?print_alias(Alias), + + {IG0, Moves0, Alias0, Worklists0} = + do_coalescing(IG, Worklists, Move_sets, Alias, K, Target), + ?debug_msg("IG after coalescing:\n",[]), + ?print_adjacent(IG0), + ?print_degrees(IG0), + ?print_spill_costs(IG0), + ?debug_msg("Move_sets after coalescing:\n ~p\n",[Moves0]), + ?mov_print_memberships(Moves0), + ?debug_msg("New Worklists after coalescing:\n ~p\n", + [Worklists0]), + ?reg_print_memberships(Worklists0), + + {IG1, Worklists1, _Moves1, Alias1} = + do_simplify_or_spill(IG0, Worklists0, Moves0, Alias0, + K, SpillLimit, Target), + ?debug_msg("IG after simplify_or_spill:\n",[]), + ?print_adjacent(IG1), + ?print_degrees(IG1), + ?print_spill_costs(IG1), + ?debug_msg("Saved spill costs ~p~n", [SavedSpillCosts]), + ?debug_msg("New Worklists after simplify_or_spill:\n ~p\n", + [Worklists1]), + ?reg_print_memberships(Worklists1), + ?print_alias(Alias1), + + %% only for testing undoCoalescing and member_coalesced_to + %test_undoCoalescing(No_temporaries, Alias1, Worklists1), + + %% only for testing fixAdj + %?debug_msg("adj_lists_before_fixAdj ~n~p~n", [hipe_ig:adj_list(IG1)]), + %IG2 = test_fixAdj(No_temporaries, SavedAdjList, IG1, Target), + %?debug_msg("adj_lists__after_fixAdj ~n~p~n", [hipe_ig:adj_list(IG2)]), + + ?debug_msg("Init node sets\n",[]), + Node_sets = hipe_node_sets:new(), + %% ?debug_msg("NodeSet: ~w\n NonAlloc ~w\n",[Node_sets,Target:non_alloc(CFG)]), + ?debug_msg("Default coloring\n",[]), + {Color0,Node_sets1} = + defaultColoring(Target:all_precoloured(), + initColor(No_temporaries), Node_sets, Target), + ?debug_msg("Color0\n",[]), + ?print_colors(No_temporaries, Color0), + + ?debug_msg("----------------------Assign colors _N\n",[]), + + Stack = hipe_reg_worklists:stack(Worklists1), + ?debug_msg("The stack _N ~p~n", [Stack]), + %SortedStack = sort_stack(Stack), + %?debug_msg("The stack _N ~p~n", [SortedStack]), + + %?debug_msg("Nodes _N ~w~n", [Node_sets1]), + + {Color1,Node_sets2,Alias2} = + assignColors(Worklists1, Stack, Node_sets1, Color0, + No_temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, All_colors, Target), + ?print_colors(No_temporaries, Color1), + ?debug_msg("Nodes:~w\nNodes2:~w\nNo_temporaries:~w\n",[Node_sets,Node_sets2,No_temporaries]), + + ?debug_msg("Build mapping _N ~w\n",[Node_sets2]), + Coloring = build_namelist(Node_sets2,SpillIndex,Alias2,Color1), + ?debug_msg("Coloring ~p\n",[Coloring]), + Coloring. +-endif. + +%%---------------------------------------------------------------------- +%% Function: do_coloring +%% +%% Description: Create a coloring. That is, play paintball. +%% Parameters: +%% IG -- An interference graph +%% Worklists -- Worklists, that is simplify, spill and freeze +%% Moves -- Moves sets, that is coalesced, constrained +%% and so on. +%% Alias -- Tells if two temporaries can have their value +%% in the same register. +%% K -- Want to create a K coloring. +%% SpillLimit -- Try not to spill nodes that are above the spill limit. +%% +%% Returns: +%% IG -- Updated interference graph +%% Worklists -- Updated Worklists structure +%% Moves -- Updated Moves structure +%% Alias -- Updates Alias structure +%% +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +do_coloring(IG, Worklists, Moves, Alias, K, SpillLimit, Target) -> + Simplify = not(hipe_reg_worklists:is_empty_simplify(Worklists)), + Coalesce = not(hipe_moves:is_empty_worklist(Moves)), + Freeze = not(hipe_reg_worklists:is_empty_freeze(Worklists)), + Spill = not(hipe_reg_worklists:is_empty_spill(Worklists)), + if Simplify =:= true -> + {IG0, Worklists0, Moves0} = + simplify_O(hipe_reg_worklists:simplify(Worklists), + IG, + Worklists, + Moves, + K), + do_coloring(IG0, Worklists0, Moves0, Alias, K, SpillLimit, Target); + Coalesce =:= true -> + {Moves0, IG0, Worklists0, Alias0} = + coalesce_O(Moves, IG, Worklists, Alias, K, Target), + do_coloring(IG0, Worklists0, Moves0, Alias0, K, SpillLimit, Target); + Freeze =:= true -> + {Worklists0, Moves0} = + freeze(K, Worklists, Moves, IG, Alias), + do_coloring(IG, Worklists0, Moves0, Alias, K, SpillLimit, Target); + Spill =:= true -> + {Worklists0, Moves0} = + selectSpill_O(Worklists, Moves, IG, K, Alias, SpillLimit), + do_coloring(IG, Worklists0, Moves0, Alias, K, SpillLimit, Target); + true -> % Catchall case + {IG, Worklists, Moves, Alias} + end. +-endif. + +%%---------------------------------------------------------------------- +%% Function: do_coalescing +%% +%% Description: Try to coalesce everything (find out later if it was +%% possible). +%% Parameters: +%% IG -- An interference graph +%% Moves -- Moves sets, that is coalesced, constrained +%% and so on. +%% Alias -- Tells if two temporaries can have their value +%% in the same register. +%% +%% Returns: +%% IG -- Updated interference graph +%% Moves -- Updated Moves structure +%% Alias -- Updates Alias structure +%% +%%---------------------------------------------------------------------- + +do_coalescing(IG, Worklists, Moves, Alias, K, Target) -> + case hipe_moves:is_empty_worklist(Moves) of + true -> + {IG, Moves, Alias, Worklists}; + _ -> + {Moves0, IG0, Alias0, Worklists0} = + coalesce(Moves, IG, Worklists, Alias, K, Target), + do_coalescing(IG0, Worklists0, Moves0, Alias0, K, Target) + end. + +%%---------------------------------------------------------------------- +%% Function: do_simplify_or_spill +%% +%% Parameters: +%% IG -- An interference graph +%% Worklists -- Worklists, that is simplify, spill and freeze +%% Moves -- Moves sets, that is coalesced, constrained +%% and so on. +%% Alias -- Tells if two temporaries can have their value +%% in the same register. +%% K -- Want to create a K coloring. +%% SpillLimit -- Try not to spill nodes that are above the spill limit. +%% +%% Returns: +%% IG -- Updated interference graph +%% Worklists -- Updated Worklists structure +%% Moves -- Updated Moves structure +%% Alias -- Updates Alias structure +%% +%%---------------------------------------------------------------------- + +do_simplify_or_spill(IG, Worklists, Moves, Alias, K, SpillLimit, Target) -> + Simplify = not(hipe_reg_worklists:is_empty_simplify(Worklists)), + Spill = not(hipe_reg_worklists:is_empty_spill(Worklists)), + if Simplify =:= true -> + {IG0, Worklists0, Moves0} = + simplify(hipe_reg_worklists:simplify(Worklists), + IG, + Worklists, + Moves, + K), + do_simplify_or_spill(IG0, Worklists0, Moves0, Alias, + K, SpillLimit, Target); + Spill =:= true -> + Worklists0 = + selectSpill(Worklists, IG, SpillLimit), + do_simplify_or_spill(IG, Worklists0, Moves, Alias, + K, SpillLimit, Target); + true -> % Catchall case + {IG, Worklists, Moves, Alias} + end. + +%%---------------------------------------------------------------------- +%% Function: adjacent +%% +%% Description: Adjacent nodes that's not coalesced, on the stack or +%% precoloured. +%% Parameters: +%% Node -- Node that you want to adjacents of +%% IG -- The interference graph +%% +%% Returns: +%% A set with nodes/temporaries that are not coalesced, on the +%% stack or precoloured. +%%---------------------------------------------------------------------- + +adjacent(Node, IG, Worklists) -> + Adjacent_edges = hipe_ig:node_adj_list(Node, IG), + hipe_reg_worklists:non_stacked_or_coalesced_nodes(Adjacent_edges, Worklists). + +%%---------------------------------------------------------------------- +%% Function: simplify +%% +%% Description: Simplify graph by removing nodes of low degree. This +%% function simplify all nodes it can at once. +%% Parameters: +%% [Node|Nodes] -- The simplify worklist +%% IG -- The interference graph +%% Worklists -- The worklists data-structure +%% Moves -- The moves data-structure +%% K -- Produce a K coloring +%% +%% Returns: +%% IG -- An updated interference graph +%% Worklists -- An updated worklists data-structure +%% Moves -- An updated moves data-structure +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +simplify_O([], IG, Worklists, Moves, _K) -> + {IG, Worklists, Moves}; +simplify_O([Node|Nodes], IG, Worklists, Moves, K) -> + Worklists0 = hipe_reg_worklists:remove_simplify(Node, Worklists), + ?debug_msg("putting ~w on stack~n",[Node]), + Adjacent = adjacent(Node, IG, Worklists0), + Worklists01 = hipe_reg_worklists:push_stack(Node, Adjacent, Worklists0), + {New_ig, Worklists1, New_moves} = + decrement_degree_O(Adjacent, IG, Worklists01, Moves, K), + simplify_O(Nodes, New_ig, Worklists1, New_moves, K). +-endif. + +%%---------------------------------------------------------------------- +%% Function: simplify +%% +%% Description: Simplify graph by removing nodes of low degree. This +%% function simplify all nodes it can at once. +%% Parameters: +%% [Node|Nodes] -- The simplify worklist +%% IG -- The interference graph +%% Worklists -- The worklists data-structure +%% Moves -- The moves data-structure +%% K -- Produce a K coloring +%% +%% Returns: +%% IG -- An updated interference graph +%% Worklists -- An updated worklists data-structure +%% Moves -- An updated moves data-structure +%%---------------------------------------------------------------------- + +simplify([], IG, Worklists, Moves, _K) -> + {IG, Worklists, Moves}; +simplify([Node|Nodes], IG, Worklists, Moves, K) -> + Worklists0 = hipe_reg_worklists:remove_simplify(Node, Worklists), + ?debug_msg("putting ~w on stack~n",[Node]), + Adjacent = adjacent(Node, IG, Worklists0), + Worklists01 = hipe_reg_worklists:push_stack(Node, Adjacent, Worklists0), + {New_ig, Worklists1} = decrement_degree(Adjacent, IG, Worklists01, K), + simplify(Nodes, New_ig, Worklists1, Moves, K). + +%%---------------------------------------------------------------------- +%% Function: decrement_degree +%% +%% Description: Decrement the degree on a number of nodes/temporaries. +%% Parameters: +%% [Node|Nodes] -- Decrement degree on these nodes +%% IG -- The interference graph +%% Worklists -- The Worklists data structure +%% Moves -- The Moves data structure. +%% K -- We want to create a coloring with K colors +%% +%% Returns: +%% IG -- An updated interference graph (the degrees) +%% Worklists -- Updated Worklists. Changed if one degree goes +%% down to K. +%% Moves -- Updated Moves. Changed if a move related temporary +%% gets degree K. +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +decrement_degree_O([], IG, Worklists, Moves, _K) -> + {IG, Worklists, Moves}; +decrement_degree_O([Node|Nodes], IG, Worklists, Moves, K) -> + PrevDegree = hipe_ig:get_node_degree(Node, IG), + IG0 = hipe_ig:dec_node_degree(Node, IG), + case PrevDegree =:= K of + true -> + AdjList = hipe_ig:node_adj_list(Node, IG0), + %% OK since Node (a) is still in IG, and (b) cannot be adjacent to itself. + Moves00 = enable_moves_active_to_worklist(hipe_moves:node_movelist(Node, Moves), + Moves), + Moves0 = enable_moves(AdjList, Worklists, Moves00), + Worklists0 = hipe_reg_worklists:remove_spill(Node, Worklists), + case hipe_moves:move_related(Node, Moves0) of + true -> + Worklists1 = hipe_reg_worklists:add_freeze(Node, Worklists0), + decrement_degree_O(Nodes, IG0, Worklists1, Moves0, K); + _ -> + Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0), + decrement_degree_O(Nodes, IG0, Worklists1, Moves0, K) + end; + _ -> + decrement_degree_O(Nodes, IG0, Worklists, Moves, K) + end. +-endif. + +%%---------------------------------------------------------------------- +%% Function: decrement_degree +%% +%% Description: Decrement the degree on a number of nodes/temporaries. +%% Parameters: +%% [Node|Nodes] -- Decrement degree on these nodes +%% IG -- The interference graph +%% Worklists -- The Worklists data structure +%% Moves -- The Moves data structure. +%% K -- We want to create a coloring with K colors +%% +%% Returns: +%% IG -- An updated interference graph (the degrees) +%% Worklists -- Updated Worklists. Changed if one degree goes +%% down to K. +%% Moves -- Updated Moves. Changed if a move related temporary +%% gets degree K. +%%---------------------------------------------------------------------- + +decrement_degree([], IG, Worklists, _K) -> + {IG, Worklists}; +decrement_degree([Node|Nodes], IG, Worklists, K) -> + PrevDegree = hipe_ig:get_node_degree(Node, IG), + IG0 = hipe_ig:dec_node_degree(Node, IG), + case PrevDegree =:= K of + true -> + Worklists0 = hipe_reg_worklists:remove_spill(Node, Worklists), + Worklists1 = hipe_reg_worklists:add_simplify(Node, Worklists0), + decrement_degree(Nodes, IG0, Worklists1, K); + _ -> + decrement_degree(Nodes, IG0, Worklists, K) + end. + +%%---------------------------------------------------------------------- +%% Function: enable_moves +%% +%% Description: Make (move-related) nodes that are not yet considered for +%% coalescing, ready for possible coalescing. +%% +%% Parameters: +%% [Node|Nodes] -- A list of move nodes +%% Moves -- The moves data-structure +%% +%% Returns: +%% An updated moves data-structure +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +enable_moves([], _Worklists, Moves) -> Moves; +enable_moves([Node|Nodes], Worklists, Moves) -> + case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of + true -> enable_moves(Nodes, Worklists, Moves); + _ -> + %% moveList[n] suffices since we're checking for activeMoves membership + Node_moves = hipe_moves:node_movelist(Node, Moves), + New_moves = enable_moves_active_to_worklist(Node_moves, Moves), + enable_moves(Nodes, Worklists, New_moves) + end. +-endif. + +%%---------------------------------------------------------------------- +%% Function: enable_moves_active_to_worklist +%% +%% Description: Make (move-related) nodes that are not yeat considered for +%% coalescing, ready for possible coalescing. +%% +%% Parameters: +%% [Node|Nodes] -- A list of move nodes +%% Moves -- The moves data-structure +%% +%% Returns: +%% An updated moves data-structure +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +enable_moves_active_to_worklist([], Moves) -> Moves; +enable_moves_active_to_worklist([Node|Nodes], Moves) -> + case hipe_moves:member_active(Node, Moves) of + true -> + New_moves = + hipe_moves:add_worklist(Node, hipe_moves:remove_active(Node, Moves)), + enable_moves_active_to_worklist(Nodes, New_moves); + _ -> + enable_moves_active_to_worklist(Nodes, Moves) + end. +-endif. + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +sanity_compare(Coloring, Coloring_N) -> + case compare_sanity(Coloring, Coloring_N) of + false -> + ?debug_msg("mismatch for coloring: ~n~p~n~p", [Coloring, Coloring_N]); + _ -> true + end. +compare_sanity({[], _C}, {[], _C_N}) -> + ?debug_msg("Sanity - OK!~n", []), + true; +compare_sanity({_Coloring_list, _C}, {[], _C_N}) -> + ?debug_msg("Sanity - unequal numbers~n", []), + false; +compare_sanity({[], _C}, {_Coloring_list_N, _C_N}) -> + ?debug_msg("Sanity - unequal numbers~n", []), + false; +compare_sanity({[Color|Coloring_list], C}, {[Color_N|Coloring_list_N], C_N}) -> + case element(1, Color) =:= element(1, Color_N) of + false -> + ?debug_msg("Sanity - unequal measure~n", []), + false; + _ -> + case element(2, Color) =:= element(2, Color_N) of + false -> + ?debug_msg("Sanity - unequal color~n", []), + false; + _ -> + case C =:= C_N of + false -> + ?debug_msg("Sanity - unequal last element~n", []), + false; + _ -> + compare_sanity({Coloring_list, C}, {Coloring_list_N, C_N}) + end + end + end. +-endif. + + +%% Build the namelists, these functions are fast hacks, they use knowledge +%% about data representation that they shouldn't know, bad abstraction. + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +build_namelist_O(NodeSets,Index,Alias,Color) -> + ?debug_msg("NodeSets ~w~n", [NodeSets]), + ?debug_msg("Building mapping\n",[]), + ?debug_msg("Vector to list\n",[]), + AliasList = + build_alias_list(aliasToList(Alias), + 0, %% The first temporary has index 0 + []), %% Accumulator + ?debug_msg("Alias list:~p\n",[AliasList]), + ?debug_msg("Coalesced\n",[]), + NL1 = build_coalescedlist(AliasList,Color,Alias,[]), + ?debug_msg("Coalesced list:~p\n",[NL1]), + ?debug_msg("Regs\n",[]), + NL2 = build_reglist_O(hipe_node_sets:colored(NodeSets),Color,NL1), + ?debug_msg("Regs list:~p\n",[NL2]), + ?debug_msg("Spills\n",[]), + build_spillist(hipe_node_sets:spilled(NodeSets),Index,NL2). +-endif. + +build_namelist(NodeSets,Index,Alias,Color) -> + ?debug_msg("NodeSets _N ~w~n", [NodeSets]), + ?debug_msg("Building mapping _N\n",[]), + ?debug_msg("Vector to list _N\n",[]), + AliasList = + build_alias_list(aliasToList(Alias), + 0, %% The first temporary has index 0 + []), %% Accumulator + ?debug_msg("Alias list _N:~p\n",[AliasList]), + ?debug_msg("Coalesced\n",[]), + NL1 = build_coalescedlist(AliasList,Color,Alias,[]), + ?debug_msg("Coalesced list:~p\n",[NL1]), + ?debug_msg("Regs _N\n",[]), + ColoredNodes = hipe_node_sets:colored(NodeSets), + ?debug_msg("ColoredNodes ~p~n", [ColoredNodes]), + NL2 = build_reglist_N(ColoredNodes,Color,NL1,NL1), + ?debug_msg("Regs list _N:~p\n",[NL2]), + ?debug_msg("Spills _N\n",[]), + build_spillist(hipe_node_sets:spilled(NodeSets),Index,NL2). + +build_spillist([],Index,List) -> + {List,Index}; +build_spillist([Node|Nodes],Index,List) -> + ?debug_msg("[~p]: Spill ~p to ~p\n", [?MODULE,Node,Index]), + build_spillist(Nodes,Index+1,[{Node,{spill,Index}}|List]). + +build_coalescedlist([],_Color,_Alias,List) -> + List; +build_coalescedlist([Node|Ns],Color,Alias,List) when is_integer(Node) -> + ?debug_msg("Alias of ~p is ~p~n",[Node,getAlias(Node,Alias)]), + AC = getColor(getAlias(Node,Alias),Color), + build_coalescedlist(Ns,Color,Alias,[{Node,{reg,AC}}|List]). + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +build_reglist_O([],_Color,List) -> + List; +build_reglist_O([Node|Ns],Color,List) -> + build_reglist_O(Ns,Color,[{Node,{reg,getColor(Node,Color)}}|List]). +-endif. + +build_reglist_N([],_Color,List,_OrgList) -> + List; +build_reglist_N([Node|Ns],Color,List,OrgList) -> + %% XXX this could be done more efficiently if both lists were sorted + case is_already_in_list(Node, OrgList) of + true -> build_reglist_N(Ns, Color, List, OrgList); + _ -> build_reglist_N(Ns,Color,[{Node,{reg,getColor(Node,Color)}}|List], OrgList) + end. + +is_already_in_list(_Node, []) -> + false; +is_already_in_list(Node, [L|List]) -> + ?debug_msg("---test--- Node ~w element ~w~n", [Node, element(1, L)]), + case Node =:= element(1, L) of + true -> true; + _ -> is_already_in_list(Node, List) + end. + +build_alias_list([], _I, List) -> + List; +build_alias_list([Alias|Aliases], I, List) when is_integer(Alias) -> + build_alias_list(Aliases, I+1, [I|List]); +build_alias_list([_Alias|Aliases], I, List) -> + build_alias_list(Aliases, I+1, List). + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +sort_stack([]) -> []; +sort_stack([Pivot|Rest]) -> + {Smaller, Bigger} = sort_stack_split(Pivot, Rest), + lists:append(sort_stack(Smaller), [Pivot|sort_stack(Bigger)]). + +sort_stack_split(Pivot, L) -> + sort_stack_split(Pivot, L, [], []). + +sort_stack_split(_Pivot, [], Smaller, Bigger) -> + {Smaller, Bigger}; +sort_stack_split(Pivot, [H|T], Smaller, Bigger) when element(1, H) > element(1, Pivot) -> + sort_stack_split(Pivot, T, [H|Smaller], Bigger); +sort_stack_split(Pivot, [H|T], Smaller, Bigger) -> + sort_stack_split(Pivot, T, Smaller, [H|Bigger]). +-endif. + +%sort([]) -> []; +%sort([Pivot|Rest]) -> +% {Smaller, Bigger} = sort_split(Pivot, Rest), +% lists:append(sort(Smaller), [Pivot|sort(Bigger)]). +% +%sort_split(Pivot, L) -> +% sort_split(Pivot, L, [], []). +% +%sort_split(_Pivot, [], Smaller, Bigger) -> {Smaller, Bigger}; +%sort_split(Pivot, [H|T], Smaller, Bigger) when H > Pivot -> +% sort_split(Pivot, T, [H|Smaller], Bigger); +%sort_split(Pivot, [H|T], Smaller, Bigger) -> +% sort_split(Pivot, T, Smaller, [H|Bigger]). + +%%---------------------------------------------------------------------- +%% Function: assignColors +%% +%% Description: Tries to assign colors to nodes in a stack. +%% Parameters: +%% Worklists -- The Worklists data structure. +%% Stack -- The SelectStack built by the Select function, +%% this stack contains tuples in the form {Node,Edges} +%% where Node is the Node number and Edges is an ordset +%% containing the numbers of all the adjacent nodes. +%% NodeSets -- This is a record containing all the different node +%% sets that are used in the register allocator. +%% Color -- A mapping from nodes to their respective color. +%% No_temporaries -- Number of temporaries. +%% SavedAdjList -- Saved adjacency list (from before coalescing). +%% SavedSpillCosts -- Saved spill costs (from before coalescing). +%% IG -- The interference graph. +%% Alias -- This is a mapping from nodes to nodes. If a node has +%% been coalesced, this mapping shows the alias for that +%% node. +%% AllColors -- This is an ordset containing all the available colors +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% Color -- A mapping from nodes to their respective color. +%% NodeSets -- The updated node sets. +%% Alias -- The updated aliases. +%%---------------------------------------------------------------------- + +assignColors(Worklists, Stack, NodeSets, Color, No_Temporaries, + SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) -> + case Stack of + [] -> + {Color,NodeSets,Alias}; + [{Node,Edges}|Stack1] -> + ?debug_msg("Coloring Node: ~p~n",[Node]), + ?IF_DEBUG(lists:foreach(fun (_E) -> + ?msg(" Edge ~w-><~w>->~w~n", + begin A = getAlias(_E,Alias), + [_E,A,getColor(A,Color)] + end) + end, Edges), + []), + %% When debugging, check that Node isn't precoloured. + OkColors = findOkColors(Edges, AllColors, Color, Alias), + case colset_is_empty(OkColors) of + true -> % Spill case + case hipe_reg_worklists:member_coalesced_to(Node, Worklists) of + true -> + ?debug_msg("Alias case. Undoing coalescing.~n", []), + {Alias1, IG1, NodeSets1, Color1, Stack2} = tryPrimitiveNodes(Node, Stack1, NodeSets, AllColors, Color, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, Target), + %{Alias1, IG1, NodeSets1, Color1, Stack2} = {Alias, IG, NodeSets, Color, Stack1}, + assignColors(Worklists, Stack2, NodeSets1, Color1, No_Temporaries, SavedAdjList, SavedSpillCosts, IG1, Alias1, AllColors, Target); + false -> + ?debug_msg("Spill case. Spilling node.~n", []), + NodeSets1 = hipe_node_sets:add_spilled(Node, NodeSets), + assignColors(Worklists, Stack1, NodeSets1, Color, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) + end; + false -> % Color case + Col = colset_smallest(OkColors), + NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), + Color1 = setColor(Node, Target:physical_name(Col), Color), + ?debug_msg("Color case. Assigning color ~p to node.~n", [Col]), + assignColors(Worklists, Stack1, NodeSets1, Color1, No_Temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, AllColors, Target) + end + end. + +%%---------------------------------------------------------------------- +%% Function: tryPrimitiveNodes +%% +%% Description: Undoes coalescing of a non-colorable coalesced node and tries +%% to assign colors to its primitives, such that the cheapest +%% potential spill cost is achieved. +%% Parameters: +%% Node -- The representative node to undo coalescing for. +%% Stack -- The SelectStack built by the Select function, +%% this stack contains tuples in the form {Node,Edges} +%% where Node is the Node number and Edges is an ordset +%% containing the numbers of all the adjacent nodes. +%% NodeSets -- This is a record containing all the different node +%% sets that are used in the register allocator. +%% AllColors -- This is an ordset containing all the available colors. +%% No_temporaries -- Number of temporaries. +%% SavedAdjList -- Saved adjacency list (from before coalescing). +%% SavedSpillCosts -- Saved spill costs (from before coalescing). +%% IG -- The interference graph. +%% Alias -- This is a mapping from nodes to nodes. If a node has +%% been coalesced, this mapping shows the alias for that +%% node. +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% Alias -- The restored aliases after the uncoalescing. +%% IG -- An updated interference graph after the uncoalescing. +%% NodeSets -- The updated node sets. +%% Color -- A mapping from nodes to their respective color. +%% Stack -- The updated SelectStack with non-colored primitives +%% placed at the bottom. +%%---------------------------------------------------------------------- + +tryPrimitiveNodes(Node, Stack, NodeSets, AllColors, Color, No_temporaries, SavedAdjList, SavedSpillCosts, IG, Alias, Target) -> + ?debug_msg("Undoing coalescing of node ~p.~n", [Node]), + {PrimitiveNodes, Alias1, IG1} = undoCoalescing(Node, No_temporaries, Alias, SavedAdjList, IG, Target), + ?debug_msg("Spilling non-colorable primitives.~n", []), + {ColorableNodes, NodeSets1} = spillNonColorablePrimitives([], PrimitiveNodes, NodeSets, AllColors, Color, SavedAdjList, Alias1), + ?debug_msg("Generating splits of colorable nodes.~n", []), + Splits = splits(ColorableNodes, SavedSpillCosts), + {NodeSets2, Color1, Stack1} = processSplits(Splits, AllColors, IG1, Color, NodeSets1, Alias1, Target, Stack), + {Alias1, IG1, NodeSets2, Color1, Stack1}. + +%% Spill all non-colorable primitives and return the remaining set of nodes. + +spillNonColorablePrimitives(ColorableNodes, [], NodeSets, _AllColors, _Color, _SavedAdjList, _Alias) -> + {ColorableNodes, NodeSets}; +spillNonColorablePrimitives(ColorableNodes, [Primitive|Primitives], NodeSets, AllColors, Color, SavedAdjList, Alias) -> + OkColors = findOkColors(hipe_adj_list:edges(Primitive, SavedAdjList), AllColors, Color, Alias), + case colset_is_empty(OkColors) of + true -> % Spill case + ?debug_msg(" Spilling primitive node ~p.~n", [Primitive]), + NodeSets1 = hipe_node_sets:add_spilled(Primitive, NodeSets), + spillNonColorablePrimitives(ColorableNodes, Primitives, NodeSets1, AllColors, Color, SavedAdjList, Alias); + false -> % Colorable case + ?debug_msg(" Primitive node ~p is colorable.~n", [Primitive]), + spillNonColorablePrimitives([Primitive|ColorableNodes], Primitives, NodeSets, AllColors, Color, SavedAdjList, Alias) + end. + +%% Generate all splits of colorable primitives, sorted in spill cost order. + +splits([], _SavedSpillCosts) -> + [{[], [], 0}]; +splits([L|Ls], SavedSpillCosts) -> + Spl = splits(Ls, SavedSpillCosts), + SpillCost = hipe_spillcost:spill_cost(L, SavedSpillCosts), + Spl1 = [splits_1(S, L) || S <- Spl], + Spl2 = [splits_2(S, L, SpillCost) || S <- Spl], + spillCostOrderedMerge(Spl1, Spl2, []). + +splits_1({Cols, NonCols, OldSpillCost}, L) -> + {[L|Cols], NonCols, OldSpillCost}. + +splits_2({Cols, NonCols, OldSpillCost}, L, SpillCost) -> + {Cols, [L|NonCols], OldSpillCost + SpillCost}. + +%% Merge two ordered sub-splits into one. + +spillCostOrderedMerge(Spl1, [], Spl) -> + lists:reverse(Spl) ++ Spl1; +spillCostOrderedMerge([], Spl2, Spl) -> + lists:reverse(Spl) ++ Spl2; +spillCostOrderedMerge(Spl1, Spl2, Spl) -> + {_, _, SpillCost1} = hd(Spl1), + {_, _, SpillCost2} = hd(Spl2), + case SpillCost1 =< SpillCost2 of + true -> + spillCostOrderedMerge(tl(Spl1), Spl2, [hd(Spl1)|Spl]); + false -> + spillCostOrderedMerge(Spl1, tl(Spl2), [hd(Spl2)|Spl]) + end. + +%% Process splits, finding the one with the smallest spill cost that +%% can be assigned one color. + +processSplits([], _AllColors, _IG, Color, NodeSets, _Alias, _Target, Stack) -> + {NodeSets, Color, Stack}; +processSplits([{Cols, NonCols, _SpillCost}|Splits], AllColors, IG, Color, NodeSets, Alias, Target, Stack) -> + OkColors = findCommonColors(Cols, IG, Color, Alias, AllColors), + case colset_is_empty(OkColors) of + false -> % This split can be colored with one color - use it + ?debug_msg("Found a colorable split.~n", []), + Col = colset_smallest(OkColors), + {NodeSets1, Color1} = colorSplit(Cols, Col, NodeSets, Color, Target), + Stack1 = enqueueSplit(NonCols, IG, Stack), + {NodeSets1, Color1, Stack1}; + true -> % This split cannot be colored with one color - try another + ?debug_msg("Unable to color split.~n", []), + processSplits(Splits, AllColors, IG, Color, NodeSets, Alias, Target, Stack) + end. + +%% Find the set of colors that can be assigned to one split. + +findCommonColors([], _IG, _Color, _Alias, OkColors) -> + OkColors; +findCommonColors([Primitive|Primitives], IG, Color, Alias, OkColors) -> + OkColors1 = findOkColors(hipe_ig:node_adj_list(Primitive, IG), OkColors, Color, Alias), + findCommonColors(Primitives, IG, Color, Alias, OkColors1). + +%% Color nodes in a split. + +colorSplit([], _Col, NodeSets, Color, _Target) -> + {NodeSets, Color}; +colorSplit([Node|Nodes], Col, NodeSets, Color, Target) -> + ?debug_msg(" Coloring node ~p with color ~p.~n", [Node, Col]), + NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), + Color1 = setColor(Node, Target:physical_name(Col), Color), + colorSplit(Nodes, Col, NodeSets1, Color1, Target). + +%% Place non-colorable nodes in a split at the bottom of the SelectStack. + +enqueueSplit([], _IG, Stack) -> + Stack; +enqueueSplit([Node|Nodes], IG, Stack) -> + ?debug_msg(" Placing node ~p at the bottom of the stack.~n", [Node]), + Edges = hipe_ig:node_adj_list(Node, IG), + Stack1 = Stack ++ [{Node, Edges}], + enqueueSplit(Nodes, IG, Stack1). + +%%---------------------------------------------------------------------- +%% Function: assignColors +%% +%% Description: Tries to assign colors to nodes in a stack. +%% Parameters: +%% Stack -- The SelectStack built by the Select function, +%% this stack contains tuples in the form {Node,Edges} +%% where Node is the Node number and Edges is an ordset +%% containing the numbers of all the adjacent nodes. +%% NodeSets -- This is a record containing all the different node +%% sets that are used in the register allocator. +%% Alias -- This is a mapping from nodes to nodes, if a node has +%% been coalesced this mapping shows the alias for that +%% node. +%% AllColors -- This is an ordset containing all the available colors +%% +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% Color -- A mapping from nodes to their respective color. +%% NodeSets -- The updated node sets. +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +assignColors_O(Stack,NodeSets,Color,Alias,AllColors,Target) -> + case Stack of + [] -> + {Color,NodeSets}; + [{Node,Edges}|Stack1] -> + ?debug_msg("Coloring Node: ~p~n",[Node]), + ?IF_DEBUG(lists:foreach(fun (_E) -> + ?msg(" Edge ~w-><~w>->~w~n", + begin A = getAlias(_E,Alias), + [_E,A,getColor(A,Color)] + end) + end, Edges), + []), + %% When debugging, check that Node isn't precoloured. + OkColors = findOkColors(Edges, AllColors, Color, Alias), + case colset_is_empty(OkColors) of + true -> % Spill case + NodeSets1 = hipe_node_sets:add_spilled(Node, NodeSets), + assignColors_O(Stack1, NodeSets1, Color, Alias, AllColors, Target); + false -> % Colour case + Col = colset_smallest(OkColors), + NodeSets1 = hipe_node_sets:add_colored(Node, NodeSets), + Color1 = setColor(Node, Target:physical_name(Col), Color), + assignColors_O(Stack1, NodeSets1, Color1, Alias, AllColors, Target) + end + end. +-endif. + +%%--------------------------------------------------------------------- +%% Function: defaultColoring +%% +%% Description: Make the default coloring +%% Parameters: +%% Regs -- The list of registers to be default colored +%% Color -- The color mapping that shall be changed +%% NodeSets -- The node sets that shall be updated +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% NewColor -- The updated color mapping +%% NewNodeSets -- The updated node sets +%%--------------------------------------------------------------------- + +defaultColoring([], Color, NodeSets, _Target) -> + {Color,NodeSets}; +defaultColoring([Reg|Regs], Color, NodeSets, Target) -> + Color1 = setColor(Reg,Target:physical_name(Reg), Color), + NodeSets1 = hipe_node_sets:add_colored(Reg, NodeSets), + defaultColoring(Regs, Color1, NodeSets1, Target). + +%% Find the colors that are OK for a node with certain edges. + +findOkColors(Edges, AllColors, Color, Alias) -> + find(Edges, AllColors, Color, Alias). + +%% Find all the colors of the nodes in the list [Node|Nodes] and remove them +%% from the set OkColors, when the list is empty, return OkColors. + +find([], OkColors, _Color, _Alias) -> + OkColors; +find([Node0|Nodes], OkColors, Color, Alias) -> + Node = getAlias(Node0, Alias), + case getColor(Node, Color) of + [] -> + find(Nodes, OkColors, Color, Alias); + Col -> + OkColors1 = colset_del_element(Col, OkColors), + find(Nodes, OkColors1, Color, Alias) + end. + +%%% +%%% ColSet -- ADT for the set of available colours while +%%% assigning colours. +%%% +-ifdef(notdef). % old ordsets-based implementation +colset_from_list(Allocatable) -> + ordsets:from_list(Allocatable). + +colset_del_element(Colour, ColSet) -> + ordsets:del_element(Colour, ColSet). + +colset_is_empty(ColSet) -> + case ColSet of + [] -> true; + [_|_] -> false + end. + +colset_smallest([Colour|_]) -> + Colour. +-endif. + +-ifdef(notdef). % new gb_sets-based implementation +colset_from_list(Allocatable) -> + gb_sets:from_list(Allocatable). + +colset_del_element(Colour, ColSet) -> + %% Must use gb_sets:delete_any/2 since gb_sets:del_element/2 + %% fails if the element isn't present. Bummer. + gb_sets:delete_any(Colour, ColSet). + +colset_is_empty(ColSet) -> + gb_sets:is_empty(ColSet). + +colset_smallest(ColSet) -> + gb_sets:smallest(ColSet). +-endif. + +%%-ifdef(notdef). % new bitmask-based implementation +colset_from_list(Allocatable) -> + colset_from_list(Allocatable, 0). + +colset_from_list([], ColSet) -> + ColSet; +colset_from_list([Colour|Allocatable], ColSet) -> + colset_from_list(Allocatable, ColSet bor (1 bsl Colour)). + +colset_del_element(Colour, ColSet) -> + ColSet band bnot(1 bsl Colour). + +colset_is_empty(0) -> true; +colset_is_empty(_) -> false. + +colset_smallest(ColSet) -> + bitN_log2(ColSet band -ColSet, 0). + +bitN_log2(BitN, ShiftN) -> + case BitN > 16#ffff of + true -> + bitN_log2(BitN bsr 16, ShiftN + 16); + _ -> + ShiftN + hweight16(BitN - 1) + end. + +hweight16(W) -> + Res1 = ( W band 16#5555) + (( W bsr 1) band 16#5555), + Res2 = (Res1 band 16#3333) + ((Res1 bsr 2) band 16#3333), + Res3 = (Res2 band 16#0F0F) + ((Res2 bsr 4) band 16#0F0F), + (Res3 band 16#00FF) + ((Res3 bsr 8) band 16#00FF). +%%-endif. + +%%% +%%% Colour ADT providing a partial mapping from nodes to colours. +%%% + +initColor(NrNodes) -> + {colmap, hipe_bifs:array(NrNodes, [])}. + +getColor(Node, {colmap, ColMap}) -> + hipe_bifs:array_sub(ColMap, Node). + +setColor(Node, Color, {colmap, ColMap} = C) -> + hipe_bifs:array_update(ColMap, Node, Color), + C. + +-ifdef(DEBUG_PRINTOUTS). +printColors(0, _) -> + true; +printColors(Node, {colmap, ColMap} = C) -> + NextNode = Node - 1, + ?debug_msg("node ~w color ~w~n", [NextNode, hipe_bifs:array_sub(ColMap, NextNode)]), + printColors(NextNode, C). +-endif. + +%%% +%%% Alias ADT providing a partial mapping from nodes to nodes. +%%% + +initAlias(NrNodes) -> + {alias, hipe_bifs:array(NrNodes, [])}. + +%% Get alias for a node. +%% Note that non-aliased nodes could be represented in +%% two ways, either not aliased or aliased to itself. +%% Including the latter case prevents looping bugs. +getAlias(Node, {alias, AliasMap} = Alias) -> + case hipe_bifs:array_sub(AliasMap, Node) of + [] -> + Node; + Node -> + Node; + AliasNode -> + getAlias(AliasNode, Alias) + end. + +-ifdef(DEBUG_PRINTOUTS). +printAlias({alias, AliasMap} = Alias) -> + ?debug_msg("Aliases:\n",[]), + printAlias(hipe_bifs:array_length(AliasMap), Alias). + +printAlias(0, {alias, _}) -> + true ; +printAlias(Node, {alias, _AliasMap} = Alias) -> + ?debug_msg("alias ~p ~p\n", [Node - 1, getAlias(Node - 1, Alias)]), + printAlias(Node - 1, Alias). +-endif. + +setAlias(Node, AliasNode, {alias, AliasMap} = Alias) -> + hipe_bifs:array_update(AliasMap, Node, AliasNode), + Alias. + +aliasToList({alias, AliasMap}) -> + aliasToList(AliasMap, hipe_bifs:array_length(AliasMap), []). + +aliasToList(AliasMap, I1, Tail) -> + I0 = I1 - 1, + case I0 >= 0 of + true -> + aliasToList(AliasMap, I0, [hipe_bifs:array_sub(AliasMap, I0)|Tail]); + _ -> + Tail + end. + +%%---------------------------------------------------------------------- +%% Function: coalesce +%% +%% Description: Coalesces nodes in worklist +%% Parameters: +%% Moves -- Current move information +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Alias -- Current aliases for temporaries +%% K -- Number of registers +%% +%% Returns: +%% {Moves, IG, Worklists, Alias} +%% (Updated versions of above structures, after coalescing) +%%---------------------------------------------------------------------- + +coalesce(Moves, IG, Worklists, Alias, K, Target) -> + case hipe_moves:worklist_get_and_remove(Moves) of + {[],Moves0} -> + %% Moves marked for removal from worklistMoves by FreezeMoves() + %% are removed by worklist_get_and_remove(). This case is unlikely, + %% but can occur if only stale moves remain in worklistMoves. + {Moves0, IG, Alias}; + {Move,Moves0} -> + {Dest,Source} = hipe_moves:get_move(Move, Moves0), + ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), + Alias_src = getAlias(Source, Alias), + Alias_dst = getAlias(Dest, Alias), + {U,V} = case Target:is_precoloured(Alias_dst) of + true -> {Alias_dst, Alias_src}; + false -> {Alias_src, Alias_dst} + end, + %% When debugging, check that neither V nor U is on the stack. + case U =:= V of + true -> + %% drop coalesced move Move + {Moves0, IG, Alias, Worklists}; + _ -> + case (Target:is_precoloured(V) orelse + hipe_ig:nodes_are_adjacent(U, V, IG)) of + true -> + %% drop constrained move Move + {Moves0, IG, Alias, Worklists}; + false -> + case (case Target:is_precoloured(U) of + true -> + AdjV = hipe_ig:node_adj_list(V, IG), + all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); + false -> + AdjV = hipe_ig:node_adj_list(V, IG), + AdjU = hipe_ig:node_adj_list(U, IG), + conservative(AdjU, AdjV, U, Worklists, IG, K) + end) of + true -> + %% drop coalesced move Move + {IG1, Alias1, Worklists1} = + combine(U, V, IG, Alias, Worklists, K, Target), + {Moves0, IG1, Alias1, Worklists1}; + false -> + Moves1 = hipe_moves:add_active(Move, Moves0), + {Moves1, IG, Alias, Worklists} + end + end + end + end. + +%%---------------------------------------------------------------------- +%% Function: coalesce_O +%% +%% Description: Coalesces nodes in worklist +%% Parameters: +%% Moves -- Current move information +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Alias -- Current aliases for temporaries +%% K -- Number of registers +%% +%% Returns: +%% {Moves, IG, Worklists, Alias} +%% (Updated versions of above structures, after coalescing) +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +coalesce_O(Moves, IG, Worklists, Alias, K, Target) -> + case hipe_moves:worklist_get_and_remove(Moves) of + {[],Moves0} -> + %% Moves marked for removal from worklistMoves by FreezeMoves() + %% are removed by worklist_get_and_remove(). This case is unlikely, + %% but can occur if only stale moves remain in worklistMoves. + {Moves0,IG,Worklists,Alias}; + {Move,Moves0} -> + {Dest,Source} = hipe_moves:get_move(Move, Moves0), + ?debug_msg("Testing nodes ~p and ~p for coalescing~n",[Dest,Source]), + Alias_src = getAlias(Source, Alias), + Alias_dst = getAlias(Dest, Alias), + {U,V} = case Target:is_precoloured(Alias_dst) of + true -> {Alias_dst, Alias_src}; + false -> {Alias_src, Alias_dst} + end, + %% When debugging, check that neither V nor U is on the stack. + case U =:= V of + true -> + Moves1 = Moves0, % drop coalesced move Move + Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), + {Moves1, IG, Worklists1, Alias}; + _ -> + case (Target:is_precoloured(V) orelse + hipe_ig:nodes_are_adjacent(U, V, IG)) of + true -> + Moves1 = Moves0, % drop constrained move Move + Worklists1 = add_worklist(Worklists, U, K, Moves1, IG, Target), + Worklists2 = add_worklist(Worklists1, V, K, Moves1, IG, Target), + {Moves1, IG, Worklists2, Alias}; + false -> + case (case Target:is_precoloured(U) of + true -> + AdjV = hipe_ig:node_adj_list(V, IG), + all_adjacent_ok(AdjV, U, Worklists, IG, K, Target); + false -> + AdjV = hipe_ig:node_adj_list(V, IG), + AdjU = hipe_ig:node_adj_list(U, IG), + conservative(AdjU, AdjV, U, Worklists, IG, K) + end) of + true -> + Moves1 = Moves0, % drop coalesced move Move + {IG1,Worklists1,Moves2,Alias1} = + combine_O(U, V, IG, Worklists, Moves1, Alias, K, Target), + Worklists2 = add_worklist(Worklists1, U, K, Moves2, IG1, Target), + {Moves2, IG1, Worklists2, Alias1}; + false -> + Moves1 = hipe_moves:add_active(Move, Moves0), + {Moves1, IG, Worklists, Alias} + end + end + end + end. +-endif. + +%%---------------------------------------------------------------------- +%% Function: add_worklist +%% +%% Description: Builds new worklists where U is transferred from freeze +%% to simplify, if possible +%% +%% Parameters: +%% Worklists -- Current worklists +%% U -- Node to operate on +%% K -- Number of registers +%% Moves -- Current move information +%% IG -- Interference graph +%% Target -- The containing the target-specific functions +%% +%% Returns: +%% Worklists (updated) +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +add_worklist(Worklists, U, K, Moves, IG, Target) -> + case (not(Target:is_precoloured(U)) + andalso not(hipe_moves:move_related(U, Moves)) + andalso (hipe_ig:is_trivially_colourable(U, K, IG))) of + true -> + hipe_reg_worklists:transfer_freeze_simplify(U, Worklists); + false -> + Worklists + end. +-endif. + +%%---------------------------------------------------------------------- +%% Function: combine +%% +%% Description: Combines two nodes into one (used when coalescing) +%% +%% Parameters: +%% U -- First node to operate on +%% V -- Second node to operate on +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Moves -- Current move information +%% Alias -- Current aliases for temporaries +%% K -- Number of registers +%% +%% Returns: +%% {IG, Worklists, Moves, Alias} (updated) +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +combine_O(U, V, IG, Worklists, Moves, Alias, K, Target) -> + Worklists1 = case hipe_reg_worklists:member_freeze(V, Worklists) of + true -> hipe_reg_worklists:remove_freeze(V, Worklists); + false -> hipe_reg_worklists:remove_spill(V, Worklists) + end, + Worklists11 = hipe_reg_worklists:add_coalesced(V, Worklists1), + + ?debug_msg("Coalescing ~p and ~p to ~p~n",[V,U,U]), + + Alias1 = setAlias(V, U, Alias), + + %% Typo in published algorithm: s/nodeMoves/moveList/g to fix. + %% XXX: moveList[u] \union moveList[v] OR NodeMoves(u) \union NodeMoves(v) ??? + %% XXX: NodeMoves() is correct, but unnecessarily strict. The ordsets:union + %% constrains NodeMoves() to return an ordset. + Moves1 = hipe_moves:update_movelist(U, + ordsets:union(hipe_moves:node_moves(U, Moves), + hipe_moves:node_moves(V, Moves)), + Moves), + %% Missing in published algorithm. From Tiger book Errata. + Moves2 = enable_moves_active_to_worklist(hipe_moves:node_movelist(V, Moves1), Moves1), + AdjV = hipe_ig:node_adj_list(V, IG), + + {IG1, Worklists2, Moves3} = + combine_edges_O(AdjV, U, IG, Worklists11, Moves2, K, Target), + + New_worklists = case (not(hipe_ig:is_trivially_colourable(U, K, IG1)) + andalso hipe_reg_worklists:member_freeze(U, Worklists2)) of + true -> hipe_reg_worklists:transfer_freeze_spill(U, Worklists2); + false -> Worklists2 + end, + {IG1, New_worklists, Moves3, Alias1}. +-endif. + +%%---------------------------------------------------------------------- +%% Function: combine +%% +%% Description: Combines two nodes into one (used when coalescing) +%% +%% Parameters: +%% U -- First node to operate on +%% V -- Second node to operate on +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Moves -- Current move information +%% Alias -- Current aliases for temporaries +%% K -- Number of registers +%% +%% Returns: +%% {IG, Worklists, Moves, Alias} (updated) +%%---------------------------------------------------------------------- + +combine(U, V, IG, Alias, Worklists, K, Target) -> + ?debug_msg("N_Coalescing ~p and ~p to ~p~n",[V,U,U]), + Worklists1 = hipe_reg_worklists:add_coalesced(V, U, Worklists), + Alias1 = setAlias(V, U, Alias), + AdjV = hipe_ig:node_adj_list(V, IG), + IG1 = combine_edges(AdjV, U, IG, Worklists1, K, Target), + {IG1, Alias1, Worklists1}. + +%%---------------------------------------------------------------------- +%% Function: combine_edges +%% +%% Description: For each node in a list, make an edge between that node +%% and node U, and decrement its degree by 1 +%% (Used when two nodes are coalesced, to connect all nodes +%% adjacent to one node to the other node) +%% +%% Parameters: +%% [T|Ts] -- List of nodes to make edges to +%% U -- Node to make edges from +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Moves -- Current move information +%% K -- Number of registers +%% +%% Returns: +%% {IG, Worklists, Moves} (updated) +%%---------------------------------------------------------------------- + +combine_edges([], _U, IG, _Worklists, _K, _Target) -> + IG; +combine_edges([T|Ts], U, IG, Worklists, K, Target) -> + case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of + true -> combine_edges(Ts, U, IG, Worklists, K, Target); + _ -> + IG1 = hipe_ig:add_edge(T, U, IG, Target), + IG2 = case Target:is_precoloured(T) of + true -> IG1; + false -> hipe_ig:dec_node_degree(T, IG1) + end, + combine_edges(Ts, U, IG2, Worklists, K, Target) + end. + +%%---------------------------------------------------------------------- +%% Function: combine_edges +%% +%% Description: For each node in a list, make an edge between that node +%% and node U, and decrement its degree by 1 +%% (Used when two nodes are coalesced, to connect all nodes +%% adjacent to one node to the other node) +%% +%% Parameters: +%% [T|Ts] -- List of nodes to make edges to +%% U -- Node to make edges from +%% IG -- Interference graph +%% Worklists -- Current worklists +%% Moves -- Current move information +%% K -- Number of registers +%% +%% Returns: +%% {IG, Worklists, Moves} (updated) +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +combine_edges_O([], _U, IG, Worklists, Moves, _K, _Target) -> + {IG, Worklists, Moves}; +combine_edges_O([T|Ts], U, IG, Worklists, Moves, K, Target) -> + case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of + true -> combine_edges_O(Ts, U, IG, Worklists, Moves, K, Target); + _ -> + %% XXX: The issue below occurs because the T->V edge isn't removed. + %% This causes adjList[T] to contain stale entries, to possibly grow + %% (if T isn't already adjacent to U), and degree[T] to possibly + %% increase (again, if T isn't already adjacent to U). + %% The decrement_degree() call repairs degree[T] but not adjList[T]. + %% It would be better to physically replace T->V with T->U, and only + %% decrement_degree(T) if T->U already existed. + %% + %% add_edge() may change a low-degree move-related node to be of + %% significant degree. In this case the node belongs in the spill + %% worklist, and that's where decrement_degree() expects to find it. + %% This issue is not covered in the published algorithm. + OldDegree = hipe_ig:get_node_degree(T, IG), + IG1 = hipe_ig:add_edge(T, U, IG, Target), + NewDegree = hipe_ig:get_node_degree(T, IG1), + Worklists0 = + if NewDegree =:= K, OldDegree =:= K-1 -> + %% ?debug_msg("~w:combine_edges_O(): repairing worklist membership for node ~w\n", [?MODULE,T]), + %% The node T must be on the freeze worklist: + %% 1. Since we're coalescing, the simplify worklist must have been + %% empty when combine_edges_O() started. + %% 2. decrement_degree() may put the node T back on the simplify + %% worklist, but that occurs after the worklists repair step. + %% 3. There are no duplicates among the edges. + Worklists00 = hipe_reg_worklists:remove_freeze(T, Worklists), + hipe_reg_worklists:add_spill(T, Worklists00); + true -> + Worklists + end, + {IG2, Worklists1, Moves1} = + decrement_degree_O([T], IG1, Worklists0, Moves, K), + combine_edges_O(Ts, U, IG2, Worklists1, Moves1, K, Target) + end. +-endif. + +%%---------------------------------------------------------------------- +%% Function: undoCoalescing +%% +%% Description: Returns necessary information for a coalesced node +%% +%% Parameters: +%% N -- The node to uncoalesce +%% No_temporaries -- Number of temporaries +%% Alias -- The Alias vector before undoing +%% SavedAdj -- Saved adjacency list +%% IG -- Interference graph +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% list of primitive nodes, that is all nodes that were previously +%% coalesced to N +%% updated alias vector +%% updated Interferece graph +%%---------------------------------------------------------------------- +undoCoalescing(N, No_temporaries, Alias, SavedAdj, IG, Target) -> + Primitives = findPrimitiveNodes(No_temporaries, N, Alias), + Alias1 = restoreAliases(Primitives, Alias), + IG1 = fixAdj(N, SavedAdj, IG, Target), + {Primitives, Alias1, IG1}. + +%% Restore aliasinfo for primitive nodes, that is +%% unalias the node sthat were aliased to the primitive +%% nodes. Note that an unaliased node could be +%% represented in two ways, either not aliased or aliased +%% to itself. See also getAlias +restoreAliases([], Alias) -> + Alias; +restoreAliases([Primitive|Primitives], Alias) -> + Alias1 = setAlias(Primitive, Primitive, Alias), + restoreAliases(Primitives, Alias1). + +%% find the primitive nodes to N, that is find all +%% nodes that are aliased to N +findPrimitiveNodes(No_temporaries, N, Alias) -> + findPrimitiveNodes(No_temporaries, N, Alias, []). + +findPrimitiveNodes(0, _N, _Alias, PrimitiveNodes) -> + PrimitiveNodes; +findPrimitiveNodes(Node, N, Alias, PrimitiveNodes) -> + NextNode = Node - 1, + case (getAlias(NextNode, Alias) =:= N) of + true -> findPrimitiveNodes(NextNode, N, Alias, [NextNode | PrimitiveNodes]); + _ -> findPrimitiveNodes(NextNode, N, Alias, PrimitiveNodes) + end. + +%test_undoCoalescing(No_temporaries, Alias, Worklists) -> +% test_undoCoalescing(No_temporaries, No_temporaries, Alias, Worklists). +% +%test_undoCoalescing(0, _No_temporaries, _Alias, _Worklists) -> +% true; +%test_undoCoalescing(Node, No_temporaries, Alias, Worklists) -> +% %?debug_msg("++ the adj list: ~p~n", [SavedAdj]), +% %?debug_msg("Node ~p~n", [Node]), +% NextNode = Node - 1, +% Coalesced_to = hipe_reg_worklists:member_coalesced_to(NextNode, Worklists), +% ?debug_msg("³³-- member coalesced: ~p~n", [Coalesced_to]), +% {Primitives, Alias1} = undoCoalescing(NextNode, No_temporaries, Alias), +% ?debug_msg("½½-- primitivenodes ~w\n", [Primitives]), +% case (Coalesced_to) of +% true -> printAlias(Alias1); +% _ -> true +% end, +% test_undoCoalescing(NextNode, No_temporaries, Alias, Worklists). + +%%---------------------------------------------------------------------- +%% Function: fixAdj +%% +%% Description: Fixes adajency set and adjacency list when undoing coalescing +%% +%% Parameters: +%% N -- Node that should be uncoalesced +%% SavedAdj -- Saved adjacency list +%% IG -- Interference graph +%% Target -- The module containing the target-specific functions. +%% +%% Returns: +%% updated Interferece graph +%%---------------------------------------------------------------------- +fixAdj(N, SavedAdj, IG, Target) -> + %Saved = hipe_vectors:get(SavedAdj, N), + Saved = hipe_adj_list:edges(N, SavedAdj), + ?debug_msg("§§--adj to ~p: ~p~n", [N, Saved]), + Adj = hipe_ig:node_adj_list(N, IG), + ?debug_msg("««--adj to ~p: ~p~n", [N, Adj]), + New = findNew(Adj, Saved), + ?debug_msg("++--new adj to ~p: ~p~n", [N, New]), + removeAdj(New, N, IG, Target), + %% XXX the following lines seems to make double nodes in + %% some adj_lists, which is a bug, apart from that they + %% don't seem to make any difference at all (even though + %% they are in the pseudocode of "optimistic coalescing") + %% addedge for all in the restored adj_list + %%RestoredAdj = hipe_ig:node_adj_list(N, IG), + %%?debug_msg("adj_lists_before_restore_o ~n~p~n", [hipe_ig:adj_list(IG)]), + %%restoreAdj(RestoredAdj, N, IG, Alias, Target). + IG. + +removeAdj([], _N, _IG, _Target) -> + true; +removeAdj([V| New], N, IG, Target) -> + hipe_ig:remove_edge(V, N, IG, Target), + removeAdj(New, N, IG, Target). + +%%restoreAdj([], _N, IG, _Alias, _Target) -> +%% %%?debug_msg("adj_lists__after_restore_o ~n~p~n", [hipe_ig:adj_list(IG)]), +%% IG; +%%restoreAdj([V| AdjToN], N, IG, Alias, Target) -> +%% AliasToV = getAlias(V, Alias), +%% IG1 = hipe_ig:add_edge(N, AliasToV, IG, Target), +%% restoreAdj(AdjToN, N, IG1, Alias, Target). + +%% XXX This is probably a clumsy way of doing it +%% better to assure the lists are sorted from the beginning +%% also coalesce findNew and removeAdj should improve performance +findNew(Adj, Saved) -> + findNew(Adj, Saved, []). + +findNew([], _Saved, New) -> + New; +findNew([A| Adj], Saved, New) -> + case lists:member(A, Saved) of + true -> findNew(Adj, Saved, New); + _ -> findNew(Adj, Saved, [A| New]) + end. + +%test_fixAdj(0, _SavedAdj, IG, _Target) -> +% IG; +%test_fixAdj(Node, SavedAdj, IG, Target) -> +% NextNode = Node - 1, +% IG1 = fixAdj(NextNode, SavedAdj, IG, Target), +% test_fixAdj(NextNode, SavedAdj, IG1, Target). +%%---------------------------------------------------------------------- +%% Function: ok +%% +%% Description: Checks if a node T is suitable to coalesce with R +%% +%% Parameters: +%% T -- Node to test +%% R -- Other node to test +%% IG -- Interference graph +%% K -- Number of registers +%% Target -- The module containing the target-specific functions +%% +%% Returns: +%% true iff coalescing is OK +%%---------------------------------------------------------------------- + +ok(T, R, IG, K, Target) -> + ((hipe_ig:is_trivially_colourable(T, K, IG)) + orelse Target:is_precoloured(T) + orelse hipe_ig:nodes_are_adjacent(T, R, IG)). + +%%---------------------------------------------------------------------- +%% Function: all_ok +%% +%% Description: True iff, for every T in the list, OK(T,U) +%% +%% Parameters: +%% [T|Ts] -- Nodes to test +%% U -- Node to test for coalescing +%% IG -- Interference graph +%% K -- Number of registers +%% Target -- The module containing the target-specific functions +%% +%% Returns: +%% true iff coalescing is OK for all nodes in the list +%%---------------------------------------------------------------------- + +all_adjacent_ok([], _U, _Worklists, _IG, _K, _Target) -> true; +all_adjacent_ok([T|Ts], U, Worklists, IG, K, Target) -> + case hipe_reg_worklists:member_stack_or_coalesced(T, Worklists) of + true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target); + _ -> + %% 'andalso' does not preserve tail-recursion + case ok(T, U, IG, K, Target) of + true -> all_adjacent_ok(Ts, U, Worklists, IG, K, Target); + false -> false + end + end. + +%%---------------------------------------------------------------------- +%% Function: conservative +%% +%% Description: Checks if nodes can be safely coalesced according to +%% the Briggs' conservative coalescing heuristic +%% +%% Parameters: +%% Nodes -- Adjacent nodes +%% IG -- Interference graph +%% K -- Number of registers +%% +%% Returns: +%% true iff coalescing is safe +%%---------------------------------------------------------------------- + +conservative(AdjU, AdjV, U, Worklists, IG, K) -> + conservative_countU(AdjU, AdjV, U, Worklists, IG, K, 0). + +%%---------------------------------------------------------------------- +%% Function: conservative_count +%% +%% Description: Counts degrees for conservative (Briggs' heuristics) +%% +%% Parameters: +%% Nodes -- (Remaining) adjacent nodes +%% IG -- Interference graph +%% K -- Number of registers +%% Cnt -- Accumulator for counting +%% +%% Returns: +%% Final value of accumulator +%%---------------------------------------------------------------------- + +conservative_countU([], AdjV, U, Worklists, IG, K, Cnt) -> + conservative_countV(AdjV, U, Worklists, IG, K, Cnt); +conservative_countU([Node|AdjU], AdjV, U, Worklists, IG, K, Cnt) -> + case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of + true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt); + _ -> + case hipe_ig:is_trivially_colourable(Node, K, IG) of + true -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt); + _ -> + Cnt1 = Cnt + 1, + if Cnt1 < K -> conservative_countU(AdjU, AdjV, U, Worklists, IG, K, Cnt1); + true -> false + end + end + end. + +conservative_countV([], _U, _Worklists, _IG, _K, _Cnt) -> true; +conservative_countV([Node|AdjV], U, Worklists, IG, K, Cnt) -> + case hipe_reg_worklists:member_stack_or_coalesced(Node, Worklists) of + true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); + _ -> + case hipe_ig:nodes_are_adjacent(Node, U, IG) of + true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); + _ -> + case hipe_ig:is_trivially_colourable(Node, K, IG) of + true -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt); + _ -> + Cnt1 = Cnt + 1, + if Cnt1 < K -> conservative_countV(AdjV, U, Worklists, IG, K, Cnt1); + true -> false + end + end + end + end. + +%%--------------------------------------------------------------------- +%% Function: selectSpill +%% +%% Description: Select the node to spill and spill it +%% Parameters: +%% WorkLists -- A datatype containing the different worklists +%% IG -- The interference graph +%% K -- The number of available registers +%% Alias -- The alias mapping +%% SpillLimit -- Try not to spill any nodes above the spill limit +%% +%% Returns: +%% WorkLists -- The updated worklists +%%--------------------------------------------------------------------- + +selectSpill(WorkLists, IG, SpillLimit) -> + [CAR|CDR] = hipe_reg_worklists:spill(WorkLists), + SpillCost = getCost(CAR, IG, SpillLimit), + M = findCheapest(CDR, IG, SpillCost, CAR, SpillLimit), + WorkLists1 = hipe_reg_worklists:remove_spill(M, WorkLists), + hipe_reg_worklists:add_simplify(M, WorkLists1). + +%%--------------------------------------------------------------------- +%% Function: selectSpill +%% +%% Description: Select the node to spill and spill it +%% Parameters: +%% WorkLists -- A datatype containing the different worklists +%% Moves -- A datatype containing the move sets +%% IG -- The interference graph +%% K -- The number of available registers +%% Alias -- The alias mapping +%% SpillLimit -- Try not to spill any nodes above the spill limit +%% +%% Returns: +%% WorkLists -- The updated worklists +%% Moves -- The updated moves +%%--------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +selectSpill_O(WorkLists, Moves, IG, K, Alias, SpillLimit) -> + [CAR|CDR] = hipe_reg_worklists:spill(WorkLists), + + SpillCost = getCost(CAR, IG, SpillLimit), + M = findCheapest(CDR, IG, SpillCost, CAR, SpillLimit), + + WorkLists1 = hipe_reg_worklists:remove_spill(M, WorkLists), + %% The published algorithm adds M to the simplify worklist + %% before the freezeMoves() call. That breaks the worklist + %% invariants, which is why the order is switched here. + {WorkLists2,Moves1} = freezeMoves(M, K, WorkLists1, Moves, IG, Alias), + WorkLists3 = hipe_reg_worklists:add_simplify(M, WorkLists2), + {WorkLists3,Moves1}. +-endif. + +%% Find the node that is cheapest to spill + +findCheapest([], _IG, _Cost, Cheapest, _SpillLimit) -> + Cheapest; +findCheapest([Node|Nodes], IG, Cost, Cheapest, SpillLimit) -> + ThisCost = getCost(Node, IG, SpillLimit), + case ThisCost < Cost of + true -> + findCheapest(Nodes, IG, ThisCost, Node, SpillLimit); + false -> + findCheapest(Nodes, IG, Cost, Cheapest, SpillLimit) + end. + +%% Get the cost for spilling a certain node, node numbers above the spill +%% limit are extremely expensive. + +getCost(Node, IG, SpillLimit) -> + case Node > SpillLimit of + true -> inf; + false -> + SpillCost = hipe_ig:node_spill_cost(Node, IG), + ?debug_msg("Actual spillcost f node ~w is ~w~n", [Node, SpillCost]), + SpillCost + end. + +%%---------------------------------------------------------------------- +%% Function: freeze +%% +%% Description: When both simplifying and coalescing is impossible we +%% rather freezes a node in stead of spilling, this function +%% selects a node for freezing (it just picks the first one in +%% the list) +%% +%% Parameters: +%% K -- The number of available registers +%% WorkLists -- A datatype containing the different worklists +%% Moves -- A datatype containing the different movelists +%% IG -- Interference graph +%% Alias -- An alias mapping, shows the alias of all coalesced +%% nodes +%% +%% Returns: +%% WorkLists -- The updated worklists +%% Moves -- The updated movelists +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +freeze(K, WorkLists, Moves, IG, Alias) -> + [U|_] = hipe_reg_worklists:freeze(WorkLists), % Smarter routine? + ?debug_msg("freezing node ~p~n", [U]), + WorkLists0 = hipe_reg_worklists:remove_freeze(U, WorkLists), + %% The published algorithm adds U to the simplify worklist + %% before the freezeMoves() call. That breaks the worklist + %% invariants, which is why the order is switched here. + {WorkLists1, Moves1} = freezeMoves(U, K, WorkLists0, Moves, IG, Alias), + WorkLists2 = hipe_reg_worklists:add_simplify(U, WorkLists1), + {WorkLists2, Moves1}. +-endif. + +%%---------------------------------------------------------------------- +%% Function: freezeMoves +%% +%% Description: Make all move related interferences for a certain node +%% into ordinary interference arcs. +%% +%% Parameters: +%% U -- The node we want to freeze +%% K -- The number of available registers +%% WorkLists -- A datatype containing the different worklists +%% Moves -- A datatype containing the different movelists +%% IG -- Interference graph +%% Alias -- An alias mapping, shows the alias of all coalesced +%% nodes +%% +%% Returns: +%% WorkLists -- The updated worklists +%% Moves -- The updated movelists +%%---------------------------------------------------------------------- + +-ifdef(COMPARE_ITERATED_OPTIMISTIC). +freezeMoves(U, K, WorkLists, Moves, IG, Alias) -> + Nodes = hipe_moves:node_moves(U, Moves), + freezeEm(U, Nodes, K, WorkLists, Moves, IG, Alias). + +%% Find what the other value in a copy instruction is, return false if +%% the instruction isn't a move with the first argument in it. + +moves(U, Move, Alias, Moves) -> + {X,Y} = hipe_moves:get_move(Move, Moves), + %% The old code (which followed the published algorithm) did + %% not follow aliases before looking for "the other" node. + %% This caused moves() to skip some moves, making some nodes + %% still move-related after freezeMoves(). These move-related + %% nodes were then added to the simplify worklist (by freeze() + %% or selectSpill()), breaking the worklist invariants. Nodes + %% already simplified appeared in coalesce_O(), were re-added to + %% the simplify worklist by add_worklist(), simplified again, + %% and coloured multiple times by assignColors(). Ouch! + X1 = getAlias(X, Alias), + Y1 = getAlias(Y, Alias), + if U =:= X1 -> Y1; + U =:= Y1 -> X1; + true -> exit({?MODULE,moves}) % XXX: shouldn't happen + end. + +freezeEm(_U, [], _K, WorkLists, Moves, _IG, _Alias) -> + {WorkLists,Moves}; +freezeEm(U, [M|Ms], K, WorkLists, Moves, IG, Alias) -> + V = moves(U, M, Alias, Moves), + {WorkLists2,Moves2} = freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias), + freezeEm(U, Ms, K, WorkLists2, Moves2, IG, Alias). + +freezeEm2(U, V, M, K, WorkLists, Moves, IG, Alias) -> + case hipe_moves:member_active(M, Moves) of + true -> + Moves1 = hipe_moves:remove_active(M, Moves), + freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias); + false -> + Moves1 = hipe_moves:remove_worklist(M, Moves), + freezeEm3(U, V, M, K, WorkLists, Moves1, IG, Alias) + end. + +freezeEm3(_U,V,_M,K,WorkLists,Moves,IG,_Alias) -> + Moves1 = Moves, % drop frozen move M + V1 = V, % getAlias(V,Alias), + %% "not MoveRelated(v)" is cheaper than "NodeMoves(v) = {}" + case ((not hipe_moves:move_related(V1,Moves1)) andalso + hipe_ig:is_trivially_colourable(V1,K,IG)) of + true -> + ?debug_msg("freezing move to ~p~n", [V]), + Worklists1 = hipe_reg_worklists:transfer_freeze_simplify(V1, WorkLists), + {Worklists1,Moves1}; + false -> + {WorkLists,Moves1} + end. +-endif. diff --git a/lib/hipe/regalloc/hipe_ppc_specific.erl b/lib/hipe/regalloc/hipe_ppc_specific.erl new file mode 100644 index 0000000000..dd2855208b --- /dev/null +++ b/lib/hipe/regalloc/hipe_ppc_specific.erl @@ -0,0 +1,168 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2004-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_ppc_specific). + +%% for hipe_coalescing_regalloc: +-export([number_of_temporaries/1 + ,analyze/1 + ,labels/1 + ,all_precoloured/0 + ,bb/2 + ,liveout/2 + ,reg_nr/1 + ,def_use/1 + ,is_move/1 + ,is_precoloured/1 + ,var_range/1 + ,allocatable/0 + ,non_alloc/1 + ,physical_name/1 + ,reverse_postorder/1 + ,livein/2 + ,uses/1 + ,defines/1 + ]). + +%% for hipe_graph_coloring_regalloc: +-export([is_fixed/1]). + +%% for hipe_ls_regalloc: +-export([args/1, is_arg/1, is_global/1, new_spill_index/1]). +-export([breadthorder/1, postorder/1]). + +%% callbacks for hipe_regalloc_loop +-export([defun_to_cfg/1, + check_and_rewrite/2]). + +defun_to_cfg(Defun) -> + hipe_ppc_cfg:init(Defun). + +check_and_rewrite(Defun, Coloring) -> + hipe_ppc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). + +reverse_postorder(CFG) -> + hipe_ppc_cfg:reverse_postorder(CFG). + +non_alloc(CFG) -> + non_alloc(hipe_ppc_registers:nr_args(), hipe_ppc_cfg:params(CFG)). + +%% same as hipe_ppc_frame:fix_formals/2 +non_alloc(0, Rest) -> Rest; +non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); +non_alloc(_, []) -> []. + +%% Liveness stuff + +analyze(CFG) -> + hipe_ppc_liveness_gpr:analyse(CFG). + +livein(Liveness,L) -> + [X || X <- hipe_ppc_liveness_gpr:livein(Liveness,L), + hipe_ppc:temp_is_allocatable(X)]. + +liveout(BB_in_out_liveness,Label) -> + [X || X <- hipe_ppc_liveness_gpr:liveout(BB_in_out_liveness,Label), + hipe_ppc:temp_is_allocatable(X)]. + +%% Registers stuff + +allocatable() -> + hipe_ppc_registers:allocatable_gpr(). + +all_precoloured() -> + hipe_ppc_registers:all_precoloured(). + +is_precoloured(Reg) -> + hipe_ppc_registers:is_precoloured_gpr(Reg). + +is_fixed(R) -> + hipe_ppc_registers:is_fixed(R). + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_ppc_cfg:labels(CFG). + +var_range(_CFG) -> + hipe_gensym:var_range(ppc). + +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(ppc), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG,L) -> + hipe_ppc_cfg:bb(CFG,L). + +%% PowerPC stuff + +def_use(Instruction) -> + {defines(Instruction), uses(Instruction)}. + +uses(I) -> + [X || X <- hipe_ppc_defuse:insn_use_gpr(I), + hipe_ppc:temp_is_allocatable(X)]. + +defines(I) -> + [X || X <- hipe_ppc_defuse:insn_def_gpr(I), + hipe_ppc:temp_is_allocatable(X)]. + +is_move(Instruction) -> + case hipe_ppc:is_pseudo_move(Instruction) of + true -> + Dst = hipe_ppc:pseudo_move_dst(Instruction), + case hipe_ppc:temp_is_allocatable(Dst) of + false -> false; + _ -> + Src = hipe_ppc:pseudo_move_src(Instruction), + hipe_ppc:temp_is_allocatable(Src) + end; + false -> false + end. + +reg_nr(Reg) -> + hipe_ppc:temp_reg(Reg). + +%%% Linear Scan stuff + +new_spill_index(SpillIndex) when is_integer(SpillIndex) -> + SpillIndex+1. + +breadthorder(CFG) -> + hipe_ppc_cfg:breadthorder(CFG). + +postorder(CFG) -> + hipe_ppc_cfg:postorder(CFG). + +is_global(R) -> + R =:= hipe_ppc_registers:temp1() orelse + R =:= hipe_ppc_registers:temp2() orelse + R =:= hipe_ppc_registers:temp3() orelse + hipe_ppc_registers:is_fixed(R). + +is_arg(R) -> + hipe_ppc_registers:is_arg(R). + +args(CFG) -> + hipe_ppc_registers:args(hipe_ppc_cfg:arity(CFG)). diff --git a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl new file mode 100644 index 0000000000..35623e7994 --- /dev/null +++ b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl @@ -0,0 +1,146 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2004-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_ppc_specific_fp). + +%% for hipe_coalescing_regalloc: +-export([number_of_temporaries/1 + ,analyze/1 + ,labels/1 + ,all_precoloured/0 + ,bb/2 + ,liveout/2 + ,reg_nr/1 + ,def_use/1 + ,is_move/1 + ,is_precoloured/1 + ,var_range/1 + ,allocatable/0 + ,non_alloc/1 + ,physical_name/1 + ,reverse_postorder/1 + ,livein/2 + ,uses/1 + ,defines/1 + ]). + +%% for hipe_graph_coloring_regalloc: +-export([is_fixed/1]). + +%% for hipe_ls_regalloc: +%%-export([args/1, is_arg/1, is_global, new_spill_index/1]). +%%-export([breadthorder/1, postorder/1]). + +%% callbacks for hipe_regalloc_loop +-export([defun_to_cfg/1, + check_and_rewrite/2]). + +defun_to_cfg(Defun) -> + hipe_ppc_cfg:init(Defun). + +check_and_rewrite(Defun, Coloring) -> + hipe_ppc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring). + +reverse_postorder(CFG) -> + hipe_ppc_cfg:reverse_postorder(CFG). + +non_alloc(_CFG) -> + []. + +%% Liveness stuff + +analyze(CFG) -> + hipe_ppc_liveness_fpr:analyse(CFG). + +livein(Liveness, L) -> + hipe_ppc_liveness_fpr:livein(Liveness, L). + +liveout(BB_in_out_liveness, Label) -> + hipe_ppc_liveness_fpr:liveout(BB_in_out_liveness, Label). + +%% Registers stuff + +allocatable() -> + hipe_ppc_registers:allocatable_fpr(). + +all_precoloured() -> + allocatable(). + +is_precoloured(Reg) -> + hipe_ppc_registers:is_precoloured_fpr(Reg). + +is_fixed(_Reg) -> + false. + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_ppc_cfg:labels(CFG). + +var_range(_CFG) -> + hipe_gensym:var_range(ppc). + +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(ppc), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG, L) -> + hipe_ppc_cfg:bb(CFG, L). + +%% PowerPC stuff + +def_use(I) -> + {defines(I), uses(I)}. + +uses(I) -> + hipe_ppc_defuse:insn_use_fpr(I). + +defines(I) -> + hipe_ppc_defuse:insn_def_fpr(I). + +is_move(I) -> + hipe_ppc:is_pseudo_fmove(I). + +reg_nr(Reg) -> + hipe_ppc:temp_reg(Reg). + +-ifdef(notdef). +new_spill_index(SpillIndex) -> + SpillIndex+1. + +breadthorder(CFG) -> + hipe_ppc_cfg:breadthorder(CFG). + +postorder(CFG) -> + hipe_ppc_cfg:postorder(CFG). + +is_global(_R) -> + false. + +is_arg(_R) -> + false. + +args(_CFG) -> + []. +-endif. diff --git a/lib/hipe/regalloc/hipe_reg_worklists.erl b/lib/hipe/regalloc/hipe_reg_worklists.erl new file mode 100644 index 0000000000..67a5788c7c --- /dev/null +++ b/lib/hipe/regalloc/hipe_reg_worklists.erl @@ -0,0 +1,360 @@ +%%% -*- erlang-indent-level: 2 -*- +%%% +%%% %CopyrightBegin% +%%% +%%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%%% +%%% The contents of this file are subject to the Erlang Public License, +%%% Version 1.1, (the "License"); you may not use this file except in +%%% compliance with the License. You should have received a copy of the +%%% Erlang Public License along with this software. If not, it can be +%%% retrieved online at http://www.erlang.org/. +%%% +%%% Software distributed under the License is distributed on an "AS IS" +%%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%%% the License for the specific language governing rights and limitations +%%% under the License. +%%% +%%% %CopyrightEnd% +%%% +%%%---------------------------------------------------------------------- +%%% File : hipe_reg_worklists.erl +%%% Author : Andreas Wallin +%%% Purpose : Represents sets of nodes/temporaries that we are +%%% working on, such as simplify and spill sets. +%%% Created : 3 Feb 2000 by Andreas Wallin +%%% Modified: Spring 2005 by NilsOla Linnermark +%%% to suit the optimistic coalesching allocator +%%%---------------------------------------------------------------------- + +-module(hipe_reg_worklists). +-author(['Andreas Wallin', 'Thorild Selén']). +-export([new/5, % only used by optimistic allocator + new/6, + simplify/1, + spill/1, + freeze/1, + stack/1, + add_simplify/2, + add_freeze/2, + add_coalesced/2, + add_coalesced/3, % only used by optimistic allocator + add_spill/2, + push_stack/3, + remove_simplify/2, + remove_spill/2, + remove_freeze/2, + is_empty_simplify/1, + is_empty_spill/1, + is_empty_freeze/1, + member_freeze/2, + member_coalesced_to/2, % only used by optimistic allocator + member_stack_or_coalesced/2, + non_stacked_or_coalesced_nodes/2, + transfer_freeze_simplify/2, + transfer_freeze_spill/2 + ]). +-ifdef(DEBUG_PRINTOUTS). +-export([print_memberships/1]). +-endif. + +-record(worklists, + {simplify, % Low-degree nodes (if coalescing non move-related) + stack, % Stack of removed low-degree nodes, with adjacency lists + membership, % Mapping from temp to which set it is in + coalesced_to, % if the node is coalesced to (only used by optimistic allocator) + spill, % Significant-degree nodes + freeze % Low-degree move-related nodes + }). + +%%-ifndef(DEBUG). +%%-define(DEBUG,true). +%%-endif. +-include("../main/hipe.hrl"). + +%%%---------------------------------------------------------------------- +%% Function: new +%% +%% Description: Constructor for worklists structure +%% +%% Parameters: +%% IG -- Interference graph +%% Target -- Target module name +%% CFG -- Target-specific CFG +%% Move_sets -- Move information +%% K -- Number of registers +%% +%% Returns: +%% A new worklists data structure +%% +%%%---------------------------------------------------------------------- + +new(IG, Target, CFG, K, No_temporaries) -> % only used by optimistic allocator + CoalescedTo = hipe_bifs:array(No_temporaries, 'none'), + init(initial(Target, CFG), K, IG, empty(No_temporaries, CoalescedTo)). + +new(IG, Target, CFG, Move_sets, K, No_temporaries) -> + init(initial(Target, CFG), K, IG, Move_sets, empty(No_temporaries, [])). + +initial(Target, CFG) -> + {Min_temporary, Max_temporary} = Target:var_range(CFG), + NonAlloc = Target:non_alloc(CFG), + non_precoloured(Target, Min_temporary, Max_temporary, []) + -- [Target:reg_nr(X) || X <- NonAlloc]. + +non_precoloured(Target, Current, Max_temporary, Initial) -> + if Current > Max_temporary -> + Initial; + true -> + NewInitial = + case Target:is_precoloured(Current) of + true -> Initial; + false -> [Current|Initial] + end, + non_precoloured(Target, Current+1, Max_temporary, NewInitial) + end. + +%% construct an empty initialized worklists data structure +empty(No_temporaries, CoalescedTo) -> + #worklists{ + membership = hipe_bifs:array(No_temporaries, 'none'), + coalesced_to = CoalescedTo, % only used by optimistic allocator + simplify = ordsets:new(), + stack = [], + spill = ordsets:new(), + freeze = ordsets:new() + }. + +%% Selectors for worklists record + +simplify(Worklists) -> Worklists#worklists.simplify. +spill(Worklists) -> Worklists#worklists.spill. +freeze(Worklists) -> Worklists#worklists.freeze. +stack(Worklists) -> Worklists#worklists.stack. + +%% Updating worklists records + +set_simplify(Simplify, Worklists) -> + Worklists#worklists{simplify = Simplify}. +set_spill(Spill, Worklists) -> + Worklists#worklists{spill = Spill}. +set_freeze(Freeze, Worklists) -> + Worklists#worklists{freeze = Freeze}. + + +%%---------------------------------------------------------------------- +%% Function: init +%% +%% Description: Initializes worklists +%% +%% Parameters: +%% Initials -- Not precoloured temporaries +%% K -- Number of registers +%% IG -- Interference graph +%% Move_sets -- Move information +%% Worklists -- (Empty) worklists structure +%% +%% Returns: +%% Initialized worklists structure +%% +%%---------------------------------------------------------------------- + +init([], _, _, Worklists) -> Worklists; +init([Initial|Initials], K, IG, Worklists) -> + case hipe_ig:is_trivially_colourable(Initial, K, IG) of + false -> + New_worklists = add_spill(Initial, Worklists), + init(Initials, K, IG, New_worklists); + _ -> + New_worklists = add_simplify(Initial, Worklists), + init(Initials, K, IG, New_worklists) + end. + +init([], _, _, _, Worklists) -> Worklists; +init([Initial|Initials], K, IG, Move_sets, Worklists) -> + case hipe_ig:is_trivially_colourable(Initial, K, IG) of + false -> + New_worklists = add_spill(Initial, Worklists), + init(Initials, K, IG, Move_sets, New_worklists); + _ -> + case hipe_moves:move_related(Initial, Move_sets) of + true -> + New_worklists = add_freeze(Initial, Worklists), + init(Initials, K, IG, Move_sets, New_worklists); + _ -> + New_worklists = add_simplify(Initial, Worklists), + init(Initials, K, IG, Move_sets, New_worklists) + end + end. + +%%%---------------------------------------------------------------------- +%% Function: is_empty +%% +%% Description: Tests if the selected worklist if empty or not. +%% +%% Parameters: +%% Worklists -- A worklists data structure +%% +%% Returns: +%% true -- If the worklist was empty +%% false -- otherwise +%% +%%%---------------------------------------------------------------------- + +is_empty_simplify(Worklists) -> + simplify(Worklists) =:= []. + +is_empty_spill(Worklists) -> + spill(Worklists) =:= []. + +is_empty_freeze(Worklists) -> + freeze(Worklists) =:= []. + +%%%---------------------------------------------------------------------- +%% Function: add +%% +%% Description: Adds one element to one of the worklists. +%% +%% Parameters: +%% Element -- An element you want to add to the +%% selected worklist. The element should +%% be a node/temporary. +%% Worklists -- A worklists data structure +%% +%% Returns: +%% An worklists data-structure that have Element in selected +%% worklist. +%% +%%%---------------------------------------------------------------------- +add_coalesced(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'stack_or_coalesced'), + Worklists. + +add_coalesced(From, To, Worklists) -> % only used by optimistic allocator + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, From, 'stack_or_coalesced'), + Coalesced_to = Worklists#worklists.coalesced_to, + hipe_bifs:array_update(Coalesced_to, To, 'coalesced_to'), + Worklists. + +add_simplify(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'simplify'), + Simplify = ordsets:add_element(Element, simplify(Worklists)), + set_simplify(Simplify, Worklists). + +add_spill(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'spill'), + Spill = ordsets:add_element(Element, spill(Worklists)), + set_spill(Spill, Worklists). + +add_freeze(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'freeze'), + Freeze = ordsets:add_element(Element, freeze(Worklists)), + set_freeze(Freeze, Worklists). + +push_stack(Node, AdjList, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Node, 'stack_or_coalesced'), + Stack = Worklists#worklists.stack, + Worklists#worklists{stack = [{Node,AdjList}|Stack]}. + +%%%---------------------------------------------------------------------- +%% Function: remove +%% +%% Description: Removes one element to one of the worklists. +%% +%% Parameters: +%% Element -- An element you want to remove from the +%% selected worklist. The element should +%% be a node/temporary. +%% Worklists -- A worklists data structure +%% +%% Returns: +%% A worklists data-structure that don't have Element in selected +%% worklist. +%% +%%%---------------------------------------------------------------------- +remove_simplify(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'none'), + Simplify = ordsets:del_element(Element, simplify(Worklists)), + set_simplify(Simplify, Worklists). + +remove_spill(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'none'), + Spill = ordsets:del_element(Element, spill(Worklists)), + set_spill(Spill, Worklists). + +remove_freeze(Element, Worklists) -> + Membership = Worklists#worklists.membership, + hipe_bifs:array_update(Membership, Element, 'none'), + Freeze = ordsets:del_element(Element, freeze(Worklists)), + set_freeze(Freeze, Worklists). + +%%%---------------------------------------------------------------------- +%% Function: transfer +%% +%% Description: Moves element from one worklist to another. +%% +%%%---------------------------------------------------------------------- +transfer_freeze_simplify(Element, Worklists) -> + add_simplify(Element, remove_freeze(Element, Worklists)). + +transfer_freeze_spill(Element, Worklists) -> + add_spill(Element, remove_freeze(Element, Worklists)). + +%%%---------------------------------------------------------------------- +%% Function: member +%% +%% Description: Checks if one element if member of selected worklist. +%% +%% Parameters: +%% Element -- Element you want to know if it's a +%% member of selected worklist. +%% Worklists -- A worklists data structure +%% +%% Returns: +%% true -- if Element is a member of selected worklist +%% false -- Otherwise +%% +%%%---------------------------------------------------------------------- + +member_coalesced_to(Element, Worklists) -> % only used by optimistic allocator + hipe_bifs:array_sub(Worklists#worklists.coalesced_to, Element) =:= 'coalesced_to'. + +member_freeze(Element, Worklists) -> + hipe_bifs:array_sub(Worklists#worklists.membership, Element) =:= 'freeze'. + +member_stack_or_coalesced(Element, Worklists) -> + hipe_bifs:array_sub(Worklists#worklists.membership, Element) =:= 'stack_or_coalesced'. + +non_stacked_or_coalesced_nodes(Nodes, Worklists) -> + Membership = Worklists#worklists.membership, + [Node || Node <- Nodes, + hipe_bifs:array_sub(Membership, Node) =/= 'stack_or_coalesced']. + +%%%---------------------------------------------------------------------- +%% Print functions - only used for debugging + +-ifdef(DEBUG_PRINTOUTS). +print_memberships(Worklists) -> + ?debug_msg("Worklist memeberships:\n", []), + Membership = Worklists#worklists.membership, + NrElems = hipe_bifs:array_length(Membership), + Coalesced_to = Worklists#worklists.coalesced_to, + print_membership(NrElems, Membership, Coalesced_to). + +print_membership(0, _, _) -> + true; +print_membership(Element, Membership, Coalesced_to) -> + NextElement = Element - 1, + ?debug_msg("worklist ~w ~w ~w\n", + [NextElement, hipe_bifs:array_sub(Membership, NextElement), + hipe_bifs:array_sub(Coalesced_to, NextElement)]), + print_membership(NextElement, Membership, Coalesced_to). +-endif. diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl new file mode 100644 index 0000000000..428a82c87b --- /dev/null +++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl @@ -0,0 +1,68 @@ +%%% -*- erlang-indent-level: 2 -*- +%%% +%%% %CopyrightBegin% +%%% +%%% Copyright Ericsson AB 2004-2009. All Rights Reserved. +%%% +%%% The contents of this file are subject to the Erlang Public License, +%%% Version 1.1, (the "License"); you may not use this file except in +%%% compliance with the License. You should have received a copy of the +%%% Erlang Public License along with this software. If not, it can be +%%% retrieved online at http://www.erlang.org/. +%%% +%%% Software distributed under the License is distributed on an "AS IS" +%%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%%% the License for the specific language governing rights and limitations +%%% under the License. +%%% +%%% %CopyrightEnd% +%%% +%%% Common wrapper for graph_coloring and coalescing regallocs. + +-module(hipe_regalloc_loop). +-export([ra/5, ra_fp/4]). + +%%-define(HIPE_INSTRUMENT_COMPILER, true). %% Turn on instrumentation. +-include("../main/hipe.hrl"). + +ra(Defun, SpillIndex, Options, RegAllocMod, TargetMod) -> + {NewDefun, Coloring, _NewSpillIndex} = + ra_common(Defun, SpillIndex, Options, RegAllocMod, TargetMod), + {NewDefun, Coloring}. + +ra_fp(Defun, Options, RegAllocMod, TargetMod) -> + ra_common(Defun, 0, Options, RegAllocMod, TargetMod). + +ra_common(Defun, SpillIndex, Options, RegAllocMod, TargetMod) -> + ?inc_counter(ra_calls_counter, 1), + CFG = TargetMod:defun_to_cfg(Defun), + SpillLimit = TargetMod:number_of_temporaries(CFG), + alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod). + +alloc(Defun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) -> + ?inc_counter(ra_iteration_counter, 1), + CFG = TargetMod:defun_to_cfg(Defun), + {Coloring, _NewSpillIndex} = + RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit, TargetMod, Options), + {NewDefun, DidSpill} = TargetMod:check_and_rewrite(Defun, Coloring), + case DidSpill of + false -> %% No new temps, we are done. + ?add_spills(Options, _NewSpillIndex), + TempMap = hipe_temp_map:cols2tuple(Coloring, TargetMod), + {TempMap2, NewSpillIndex2} = + hipe_spillmin:stackalloc(CFG, [], SpillIndex, Options, + TargetMod, TempMap), + Coloring2 = + hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), TempMap2), + %% case proplists:get_bool(verbose_spills, Options) of + %% true -> + %% ?msg("Num spill slots used: ~p~n", [NewSpillIndex2-SpillIndex]); + %% false -> + %% ok + %% end, + {NewDefun, Coloring2, NewSpillIndex2}; + _ -> + %% Since SpillLimit is used as a low-water-mark + %% the list of temps not to spill is uninteresting. + alloc(NewDefun, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) + end. diff --git a/lib/hipe/regalloc/hipe_sparc_specific.erl b/lib/hipe/regalloc/hipe_sparc_specific.erl new file mode 100644 index 0000000000..7b8c62e802 --- /dev/null +++ b/lib/hipe/regalloc/hipe_sparc_specific.erl @@ -0,0 +1,168 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_sparc_specific). + +%% for hipe_coalescing_regalloc: +-export([number_of_temporaries/1 + ,analyze/1 + ,labels/1 + ,all_precoloured/0 + ,bb/2 + ,liveout/2 + ,reg_nr/1 + ,def_use/1 + ,is_move/1 + ,is_precoloured/1 + ,var_range/1 + ,allocatable/0 + ,non_alloc/1 + ,physical_name/1 + ,reverse_postorder/1 + ,livein/2 + ,uses/1 + ,defines/1 + ]). + +%% for hipe_graph_coloring_regalloc: +-export([is_fixed/1]). + +%% for hipe_ls_regalloc: +-export([args/1, is_arg/1, is_global/1, new_spill_index/1]). +-export([breadthorder/1, postorder/1]). + +%% callbacks for hipe_regalloc_loop +-export([defun_to_cfg/1, + check_and_rewrite/2]). + +defun_to_cfg(Defun) -> + hipe_sparc_cfg:init(Defun). + +check_and_rewrite(Defun, Coloring) -> + hipe_sparc_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal'). + +reverse_postorder(CFG) -> + hipe_sparc_cfg:reverse_postorder(CFG). + +non_alloc(CFG) -> + non_alloc(hipe_sparc_registers:nr_args(), hipe_sparc_cfg:params(CFG)). + +%% same as hipe_sparc_frame:fix_formals/2 +non_alloc(0, Rest) -> Rest; +non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); +non_alloc(_, []) -> []. + +%% Liveness stuff + +analyze(CFG) -> + hipe_sparc_liveness_gpr:analyse(CFG). + +livein(Liveness,L) -> + [X || X <- hipe_sparc_liveness_gpr:livein(Liveness,L), + hipe_sparc:temp_is_allocatable(X)]. + +liveout(BB_in_out_liveness,Label) -> + [X || X <- hipe_sparc_liveness_gpr:liveout(BB_in_out_liveness,Label), + hipe_sparc:temp_is_allocatable(X)]. + +%% Registers stuff + +allocatable() -> + hipe_sparc_registers:allocatable_gpr(). + +all_precoloured() -> + hipe_sparc_registers:all_precoloured(). + +is_precoloured(Reg) -> + hipe_sparc_registers:is_precoloured_gpr(Reg). + +is_fixed(R) -> + hipe_sparc_registers:is_fixed(R). + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_sparc_cfg:labels(CFG). + +var_range(_CFG) -> + hipe_gensym:var_range(sparc). + +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(sparc), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG,L) -> + hipe_sparc_cfg:bb(CFG,L). + +%% SPARC stuff + +def_use(Instruction) -> + {defines(Instruction), uses(Instruction)}. + +uses(I) -> + [X || X <- hipe_sparc_defuse:insn_use_gpr(I), + hipe_sparc:temp_is_allocatable(X)]. + +defines(I) -> + [X || X <- hipe_sparc_defuse:insn_def_gpr(I), + hipe_sparc:temp_is_allocatable(X)]. + +is_move(Instruction) -> + case hipe_sparc:is_pseudo_move(Instruction) of + true -> + Dst = hipe_sparc:pseudo_move_dst(Instruction), + case hipe_sparc:temp_is_allocatable(Dst) of + false -> false; + _ -> + Src = hipe_sparc:pseudo_move_src(Instruction), + hipe_sparc:temp_is_allocatable(Src) + end; + false -> false + end. + +reg_nr(Reg) -> + hipe_sparc:temp_reg(Reg). + +%%% Linear Scan stuff + +new_spill_index(SpillIndex) when is_integer(SpillIndex) -> + SpillIndex+1. + +breadthorder(CFG) -> + hipe_sparc_cfg:breadthorder(CFG). + +postorder(CFG) -> + hipe_sparc_cfg:postorder(CFG). + +is_global(R) -> + R =:= hipe_sparc_registers:temp1() orelse + R =:= hipe_sparc_registers:temp2() orelse + R =:= hipe_sparc_registers:temp3() orelse + hipe_sparc_registers:is_fixed(R). + +is_arg(R) -> + hipe_sparc_registers:is_arg(R). + +args(CFG) -> + hipe_sparc_registers:args(hipe_sparc_cfg:arity(CFG)). diff --git a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl new file mode 100644 index 0000000000..8a27f84e67 --- /dev/null +++ b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl @@ -0,0 +1,146 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2002-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_sparc_specific_fp). + +%% for hipe_coalescing_regalloc: +-export([number_of_temporaries/1 + ,analyze/1 + ,labels/1 + ,all_precoloured/0 + ,bb/2 + ,liveout/2 + ,reg_nr/1 + ,def_use/1 + ,is_move/1 + ,is_precoloured/1 + ,var_range/1 + ,allocatable/0 + ,non_alloc/1 + ,physical_name/1 + ,reverse_postorder/1 + ,livein/2 + ,uses/1 + ,defines/1 + ]). + +%% for hipe_graph_coloring_regalloc: +-export([is_fixed/1]). + +%% for hipe_ls_regalloc: +%%-export([args/1, is_arg/1, is_global, new_spill_index/1]). +%%-export([breadthorder/1, postorder/1]). + +%% callbacks for hipe_regalloc_loop +-export([defun_to_cfg/1, + check_and_rewrite/2]). + +defun_to_cfg(Defun) -> + hipe_sparc_cfg:init(Defun). + +check_and_rewrite(Defun, Coloring) -> + hipe_sparc_ra_postconditions_fp:check_and_rewrite(Defun, Coloring). + +reverse_postorder(CFG) -> + hipe_sparc_cfg:reverse_postorder(CFG). + +non_alloc(_CFG) -> + []. + +%% Liveness stuff + +analyze(CFG) -> + hipe_sparc_liveness_fpr:analyse(CFG). + +livein(Liveness, L) -> + hipe_sparc_liveness_fpr:livein(Liveness, L). + +liveout(BB_in_out_liveness, Label) -> + hipe_sparc_liveness_fpr:liveout(BB_in_out_liveness, Label). + +%% Registers stuff + +allocatable() -> + hipe_sparc_registers:allocatable_fpr(). + +all_precoloured() -> + allocatable(). + +is_precoloured(Reg) -> + hipe_sparc_registers:is_precoloured_fpr(Reg). + +is_fixed(_Reg) -> + false. + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_sparc_cfg:labels(CFG). + +var_range(_CFG) -> + hipe_gensym:var_range(sparc). + +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(sparc), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG, L) -> + hipe_sparc_cfg:bb(CFG, L). + +%% SPARC stuff + +def_use(I) -> + {defines(I), uses(I)}. + +uses(I) -> + hipe_sparc_defuse:insn_use_fpr(I). + +defines(I) -> + hipe_sparc_defuse:insn_def_fpr(I). + +is_move(I) -> + hipe_sparc:is_pseudo_fmove(I). + +reg_nr(Reg) -> + hipe_sparc:temp_reg(Reg). + +-ifdef(notdef). +new_spill_index(SpillIndex)-> + SpillIndex+1. + +breadthorder(CFG) -> + hipe_sparc_cfg:breadthorder(CFG). + +postorder(CFG) -> + hipe_sparc_cfg:postorder(CFG). + +is_global(_R) -> + false. + +is_arg(_R) -> + false. + +args(_CFG) -> + []. +-endif. diff --git a/lib/hipe/regalloc/hipe_spillcost.erl b/lib/hipe/regalloc/hipe_spillcost.erl new file mode 100644 index 0000000000..04b25f6339 --- /dev/null +++ b/lib/hipe/regalloc/hipe_spillcost.erl @@ -0,0 +1,101 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(hipe_spillcost). + +-export([new/1, + inc_costs/2, + ref_in_bb/2, + spill_cost/2]). +%% The following is exported only for debugging purposes. +-ifdef(DEBUG_PRINTOUTS). +-export([nr_of_use/2]). +-endif. + +%%---------------------------------------------------------------------------- + +-include("hipe_spillcost.hrl"). + +%%---------------------------------------------------------------------------- + +-spec new(non_neg_integer()) -> #spill_cost{}. + +new(NrTemps) -> + #spill_cost{uses = hipe_bifs:array(NrTemps, 0), + bb_uses = hipe_bifs:array(NrTemps, 0)}. + +%%---------------------------------------------------------------------------- +%% Function: inc_costs +%% +%% Description: Registers usage of a list of temporaries (for spill_cost) +%%---------------------------------------------------------------------------- + +-spec inc_costs([non_neg_integer()], #spill_cost{}) -> #spill_cost{}. + +inc_costs(Temps, SC) -> + Uses = SC#spill_cost.uses, + lists:foreach(fun (T) -> inc_use(T, Uses) end, Temps), + SC. % updated via side-effects + +inc_use(Temp, Uses) -> + hipe_bifs:array_update(Uses, Temp, get_uses(Temp, Uses) + 1). + +nr_of_use(Temp, SC) -> + get_uses(Temp, SC#spill_cost.uses). + +get_uses(Temp, Uses) -> + hipe_bifs:array_sub(Uses, Temp). + +%%---------------------------------------------------------------------------- +%% Function: ref_in_bb +%% +%% Description: Registers that a set of temporaries are used in one basic +%% block; should be done exactly once per basic block +%%---------------------------------------------------------------------------- + +-spec ref_in_bb([non_neg_integer()], #spill_cost{}) -> #spill_cost{}. + +ref_in_bb(Temps, SC) -> + BBUses = SC#spill_cost.bb_uses, + lists:foreach(fun (T) -> inc_bb_use(T, BBUses) end, Temps), + SC. % updated via side-effects + +inc_bb_use(Temp, BBUses) -> + hipe_bifs:array_update(BBUses, Temp, get_bb_uses(Temp, BBUses) + 1). + +bb_use(Temp, SC) -> + get_bb_uses(Temp, SC#spill_cost.bb_uses). + +get_bb_uses(Temp, BBUses) -> + hipe_bifs:array_sub(BBUses, Temp). + +%%---------------------------------------------------------------------------- +%% Function: spill_cost +%% +%% Description: Computes a spill cost for a temporary +%% +%% Returns: +%% Spill cost (a real number -- higher means worse to spill) +%%---------------------------------------------------------------------------- + +-spec spill_cost(non_neg_integer(), #spill_cost{}) -> float(). + +spill_cost(Temp, SC) -> + nr_of_use(Temp, SC) / bb_use(Temp, SC). diff --git a/lib/hipe/regalloc/hipe_spillcost.hrl b/lib/hipe/regalloc/hipe_spillcost.hrl new file mode 100644 index 0000000000..e736a561d7 --- /dev/null +++ b/lib/hipe/regalloc/hipe_spillcost.hrl @@ -0,0 +1,27 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-type hipe_array() :: integer(). + +-record(spill_cost, + {uses :: hipe_array(), % number of uses of each temp + bb_uses :: hipe_array() % number of basic blocks each temp occurs in + }). + diff --git a/lib/hipe/regalloc/hipe_temp_map.erl b/lib/hipe/regalloc/hipe_temp_map.erl new file mode 100644 index 0000000000..85678edd54 --- /dev/null +++ b/lib/hipe/regalloc/hipe_temp_map.erl @@ -0,0 +1,125 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% +%% =========================================================================== +%% Copyright (c) 2001 by Erik Johansson. All Rights Reserved +%% Time-stamp: <2008-04-20 14:54:00 richard> +%% =========================================================================== +%% Module : hipe_temp_map +%% Purpose : +%% Notes : +%% History : * 2001-07-24 Erik Johansson (happi@it.uu.se): Created. +%% =========================================================================== +%% Exports : +%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +-module(hipe_temp_map). + +-export([cols2tuple/2, is_spilled/2, to_substlist/1]). + +-include("../main/hipe.hrl"). + +%%---------------------------------------------------------------------------- +%% Convert a list of [{R0, C1}, {R1, C2}, ...] to a temp_map +%% (Currently implemented as a tuple) tuple {C1, C2, ...}. +%% +%% The indices (Ri) must be unique but do not have to be sorted and +%% they can be sparse. +%% Note that the first allowed index is 0 -- this will be mapped to +%% element 1 +%%---------------------------------------------------------------------------- + +-spec cols2tuple(hipe_map(), atom()) -> hipe_temp_map(). + +cols2tuple(Map, Target) -> + ?ASSERT(check_list(Map)), + SortedMap = lists:keysort(1, Map), + cols2tuple(0, SortedMap, [], Target). + +%% sorted_cols2tuple(Map, Target) -> +%% ?ASSERT(check_list(Map)), +%% ?ASSERT(Map =:= lists:keysort(1, Map)), +%% cols2tuple(0, Map, [], Target). + +%% Build a dense mapping +cols2tuple(_, [], Vs, _) -> + %% Done reverse the list and convert to tuple. + list_to_tuple(lists:reverse(Vs)); +cols2tuple(N, [{R, C}|Ms], Vs, Target) when N =:= R -> + %% N makes sure the mapping is dense. N is he next key. + cols2tuple(N+1, Ms, [C|Vs], Target); +cols2tuple(N, SourceMapping, Vs, Target) -> + %% The source was sparse, make up some placeholders... + Val = + case Target:is_precoloured(N) of + %% If it is precoloured, we know what to map it to. + true -> {reg, N}; + false -> unknown + end, + cols2tuple(N+1, SourceMapping, [Val|Vs], Target). + +%% +%% True if temp Temp is spilled. +%% +-spec is_spilled(non_neg_integer(), hipe_temp_map()) -> boolean(). + +is_spilled(Temp, Map) -> + case element(Temp+1, Map) of + {reg, _R} -> false; + {fp_reg, _R}-> false; + {spill, _N} -> true; + unknown -> false + end. + +%% %% True if temp Temp is allocated to a reg. +%% in_reg(Temp, Map) -> +%% case element(Temp+1, Map) of +%% {reg, _R} -> true; +%% {fp_reg, _R}-> false; +%% {spill, _N} -> false; +%% unknown -> false +%% end. +%% +%% %% True if temp Temp is allocated to a fp_reg. +%% in_fp_reg(Temp, Map) -> +%% case element(Temp+1, Map) of +%% {fp_reg, _R} -> true; +%% {reg, _R} -> false; +%% {spill, _N} -> false; +%% unknown -> false +%% end. +%% +%% %% Returns the inf temp Temp is mapped to. +%% find(Temp, Map) -> element(Temp+1, Map). + + +%% +%% Converts a temp_map tuple back to a (sorted) key-list. +%% +-spec to_substlist(hipe_temp_map()) -> hipe_map(). + +to_substlist(Map) -> + T = tuple_to_list(Map), + mapping(T, 0). + +mapping([R|Rs], Temp) -> + [{Temp, R}| mapping(Rs, Temp+1)]; +mapping([], _) -> + []. diff --git a/lib/hipe/regalloc/hipe_x86_specific.erl b/lib/hipe/regalloc/hipe_x86_specific.erl new file mode 100644 index 0000000000..0f490ba14d --- /dev/null +++ b/lib/hipe/regalloc/hipe_x86_specific.erl @@ -0,0 +1,203 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-ifdef(HIPE_AMD64). +-define(HIPE_X86_SPECIFIC, hipe_amd64_specific). +-define(HIPE_X86_RA_POSTCONDITIONS, hipe_amd64_ra_postconditions). +-define(HIPE_X86_REGISTERS, hipe_amd64_registers). +-define(HIPE_X86_LIVENESS, hipe_amd64_liveness). +-define(HIPE_X86_DEFUSE, hipe_amd64_defuse). +-else. +-define(HIPE_X86_SPECIFIC, hipe_x86_specific). +-define(HIPE_X86_RA_POSTCONDITIONS, hipe_x86_ra_postconditions). +-define(HIPE_X86_REGISTERS, hipe_x86_registers). +-define(HIPE_X86_LIVENESS, hipe_x86_liveness). +-define(HIPE_X86_DEFUSE, hipe_x86_defuse). +-endif. + +-module(?HIPE_X86_SPECIFIC). + +-export([number_of_temporaries/1]). + +%% The following exports are used as M:F(...) calls from other modules; +%% e.g. hipe_x86_ra_ls. +-export([analyze/1, + bb/2, + args/1, + labels/1, + livein/2, + liveout/2, + uses/1, + defines/1, + def_use/1, + is_arg/1, % used by hipe_ls_regalloc + is_move/1, + is_fixed/1, % used by hipe_graph_coloring_regalloc + is_global/1, + is_precoloured/1, + reg_nr/1, + non_alloc/1, + allocatable/0, + physical_name/1, + all_precoloured/0, + new_spill_index/1, % used by hipe_ls_regalloc + var_range/1, + breadthorder/1, + postorder/1, + reverse_postorder/1]). + +%% callbacks for hipe_regalloc_loop +-export([defun_to_cfg/1, + check_and_rewrite/2]). + +defun_to_cfg(Defun) -> + hipe_x86_cfg:init(Defun). + +check_and_rewrite(Defun, Coloring) -> + ?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(Defun, Coloring, 'normal'). + +reverse_postorder(CFG) -> + hipe_x86_cfg:reverse_postorder(CFG). + +breadthorder(CFG) -> + hipe_x86_cfg:breadthorder(CFG). + +postorder(CFG) -> + hipe_x86_cfg:postorder(CFG). + +%% Globally defined registers for linear scan +is_global(R) -> + ?HIPE_X86_REGISTERS:temp1() =:= R orelse + ?HIPE_X86_REGISTERS:temp0() =:= R orelse + ?HIPE_X86_REGISTERS:is_fixed(R). + +is_fixed(R) -> + ?HIPE_X86_REGISTERS:is_fixed(R). + +is_arg(R) -> + ?HIPE_X86_REGISTERS:is_arg(R). + +args(CFG) -> + ?HIPE_X86_REGISTERS:args(hipe_x86_cfg:arity(CFG)). + +non_alloc(CFG) -> + non_alloc(?HIPE_X86_REGISTERS:nr_args(), hipe_x86_cfg:params(CFG)). + +%% same as hipe_x86_frame:fix_formals/2 +non_alloc(0, Rest) -> Rest; +non_alloc(N, [_|Rest]) -> non_alloc(N-1, Rest); +non_alloc(_, []) -> []. + +%% Liveness stuff + +analyze(CFG) -> + ?HIPE_X86_LIVENESS:analyze(CFG). + +livein(Liveness,L) -> + [X || X <- ?HIPE_X86_LIVENESS:livein(Liveness,L), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_reg(X) =/= ?HIPE_X86_REGISTERS:fcalls(), + hipe_x86:temp_reg(X) =/= ?HIPE_X86_REGISTERS:heap_limit(), + hipe_x86:temp_type(X) =/= 'double']. + +liveout(BB_in_out_liveness,Label) -> + [X || X <- ?HIPE_X86_LIVENESS:liveout(BB_in_out_liveness,Label), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_reg(X) =/= ?HIPE_X86_REGISTERS:fcalls(), + hipe_x86:temp_reg(X) =/= ?HIPE_X86_REGISTERS:heap_limit(), + hipe_x86:temp_type(X) =/= 'double']. + +%% Registers stuff + +allocatable() -> + ?HIPE_X86_REGISTERS:allocatable(). + +all_precoloured() -> + ?HIPE_X86_REGISTERS:all_precoloured(). + +is_precoloured(Reg) -> + ?HIPE_X86_REGISTERS:is_precoloured(Reg). + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_x86_cfg:labels(CFG). + +var_range(_CFG) -> + hipe_gensym:var_range(x86). + +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(x86), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG,L) -> + hipe_x86_cfg:bb(CFG,L). + +%% X86 stuff + +def_use(Instruction) -> + {[X || X <- ?HIPE_X86_DEFUSE:insn_def(Instruction), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =/= 'double'], + [X || X <- ?HIPE_X86_DEFUSE:insn_use(Instruction), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =/= 'double'] + }. + +uses(I) -> + [X || X <- ?HIPE_X86_DEFUSE:insn_use(I), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =/= 'double']. + +defines(I) -> + [X || X <- ?HIPE_X86_DEFUSE:insn_def(I), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =/= 'double']. + +is_move(Instruction) -> + case hipe_x86:is_move(Instruction) of + true -> + Src = hipe_x86:move_src(Instruction), + Dst = hipe_x86:move_dst(Instruction), + case hipe_x86:is_temp(Src) of + true -> + case hipe_x86:temp_is_allocatable(Src) of + true -> + case hipe_x86:is_temp(Dst) of + true -> + hipe_x86:temp_is_allocatable(Dst); + false -> false + end; + false -> false + end; + false -> false + end; + false -> false + end. + +reg_nr(Reg) -> + hipe_x86:temp_reg(Reg). + +new_spill_index(SpillIndex) when is_integer(SpillIndex) -> + SpillIndex+1. diff --git a/lib/hipe/regalloc/hipe_x86_specific_x87.erl b/lib/hipe/regalloc/hipe_x86_specific_x87.erl new file mode 100644 index 0000000000..7fd80b63d8 --- /dev/null +++ b/lib/hipe/regalloc/hipe_x86_specific_x87.erl @@ -0,0 +1,164 @@ +%% -*- erlang-indent-level: 2 -*- +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2006-2009. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-ifdef(HIPE_AMD64). +-define(HIPE_X86_SPECIFIC_X87, hipe_amd64_specific_x87). +-define(HIPE_X86_LIVENESS, hipe_amd64_liveness). +-define(HIPE_X86_REGISTERS, hipe_amd64_registers). +-define(HIPE_X86_DEFUSE, hipe_amd64_defuse). +-else. +-define(HIPE_X86_SPECIFIC_X87, hipe_x86_specific_x87). +-define(HIPE_X86_LIVENESS, hipe_x86_liveness). +-define(HIPE_X86_REGISTERS, hipe_x86_registers). +-define(HIPE_X86_DEFUSE, hipe_x86_defuse). +-endif. + +-module(?HIPE_X86_SPECIFIC_X87). +-export([allocatable/0, + is_precoloured/1, + %% var_range/1, + %% def_use/1, + %% is_fixed/1, + is_arg/1, + %% non_alloc/1, + new_spill_index/1, + number_of_temporaries/1 + ]). + +%% The following exports are used as M:F(...) calls from other modules; +%% e.g. hipe_x86_ra_ls. +-export([analyze/1, + bb/2, + args/1, + labels/1, + livein/2, + liveout/2, + uses/1, + defines/1, + is_global/1, + reg_nr/1, + physical_name/1, + breadthorder/1, + postorder/1, + reverse_postorder/1]). + +breadthorder(CFG) -> + hipe_x86_cfg:breadthorder(CFG). +postorder(CFG) -> + hipe_x86_cfg:postorder(CFG). +reverse_postorder(CFG) -> + hipe_x86_cfg:reverse_postorder(CFG). + +is_global(_) -> + false. + +-ifdef(notdef). +is_fixed(_) -> + false. +-endif. + +is_arg(_) -> + false. + +args(_) -> + []. + +-ifdef(notdef). +non_alloc(_) -> + []. +-endif. + +%% Liveness stuff + +analyze(CFG) -> + ?HIPE_X86_LIVENESS:analyze(CFG). + +livein(Liveness,L) -> + [X || X <- ?HIPE_X86_LIVENESS:livein(Liveness,L), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double']. + +liveout(BB_in_out_liveness,Label) -> + [X || X <- ?HIPE_X86_LIVENESS:liveout(BB_in_out_liveness,Label), + hipe_x86:temp_is_allocatable(X), + hipe_x86:temp_type(X) =:= 'double']. + +%% Registers stuff + +allocatable() -> + ?HIPE_X86_REGISTERS:allocatable_x87(). + +is_precoloured(Reg) -> + ?HIPE_X86_REGISTERS:is_precoloured_x87(Reg). + +physical_name(Reg) -> + Reg. + +%% CFG stuff + +labels(CFG) -> + hipe_x86_cfg:labels(CFG). + +-ifdef(notdef). +var_range(_CFG) -> + {Min,Max} = hipe_gensym:var_range(x86), + %% io:format("Var_range: ~w\n",[{Min,Max}]), + {Min,Max}. +-endif. + +number_of_temporaries(_CFG) -> + Highest_temporary = hipe_gensym:get_var(x86), + %% Since we can have temps from 0 to Max adjust by +1. + Highest_temporary + 1. + +bb(CFG,L) -> + hipe_x86_cfg:bb(CFG,L). + +%% X86 stuff + +-ifdef(notdef). +def_use(Instruction) -> + {[X || X <- ?HIPE_X86_DEFUSE:insn_def(Instruction), + hipe_x86:temp_is_allocatable(X), + temp_is_double(X)], + [X || X <- ?HIPE_X86_DEFUSE:insn_use(Instruction), + hipe_x86:temp_is_allocatable(X), + temp_is_double(X)] + }. +-endif. + +uses(I) -> + [X || X <- ?HIPE_X86_DEFUSE:insn_use(I), + hipe_x86:temp_is_allocatable(X), + temp_is_double(X)]. + +defines(I) -> + [X || X <- ?HIPE_X86_DEFUSE:insn_def(I), + hipe_x86:temp_is_allocatable(X), + temp_is_double(X)]. + +temp_is_double(Temp) -> + hipe_x86:temp_type(Temp) =:= 'double'. + +reg_nr(Reg) -> + hipe_x86:temp_reg(Reg). + +new_spill_index(SpillIndex) -> + SpillIndex+1. -- cgit v1.2.3