From 85bd166647e7f260fd665eb44da9151c0d88f208 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Magnus=20L=C3=A5ng?= <margnus1@telia.com>
Date: Sat, 28 May 2016 20:22:34 +0200
Subject: hipe: Add hipe_regalloc_prepass

hipe_regalloc_prepass speeds up register allocation by spilling any temp
that is live over a call (which clobbers all register).

In order to detect these, a new function was added to the target
interface; defines_all_alloc/1, that takes an instruction and returns a
boolean.
---
 lib/hipe/amd64/hipe_amd64_registers.erl        |   3 +
 lib/hipe/arm/hipe_arm_defuse.erl               |   7 +
 lib/hipe/arm/hipe_arm_registers.erl            |   2 +
 lib/hipe/main/hipe.app.src                     |   1 +
 lib/hipe/ppc/hipe_ppc_defuse.erl               |   7 +
 lib/hipe/ppc/hipe_ppc_registers.erl            |   2 +
 lib/hipe/regalloc/Makefile                     |   1 +
 lib/hipe/regalloc/hipe_amd64_specific_sse2.erl |   3 +
 lib/hipe/regalloc/hipe_arm_specific.erl        |   4 +
 lib/hipe/regalloc/hipe_ppc_specific.erl        |   4 +
 lib/hipe/regalloc/hipe_ppc_specific_fp.erl     |   4 +
 lib/hipe/regalloc/hipe_regalloc_loop.erl       |   3 +-
 lib/hipe/regalloc/hipe_regalloc_prepass.erl    | 400 +++++++++++++++++++++++++
 lib/hipe/regalloc/hipe_sparc_specific.erl      |   4 +
 lib/hipe/regalloc/hipe_sparc_specific_fp.erl   |   4 +
 lib/hipe/regalloc/hipe_temp_map.erl            |  17 +-
 lib/hipe/regalloc/hipe_x86_specific.erl        |   3 +
 lib/hipe/regalloc/hipe_x86_specific_x87.erl    |   3 +
 lib/hipe/sparc/hipe_sparc_defuse.erl           |  13 +
 lib/hipe/sparc/hipe_sparc_registers.erl        |   2 +
 lib/hipe/x86/hipe_x86_defuse.erl               |  12 +-
 lib/hipe/x86/hipe_x86_registers.erl            |   2 +
 22 files changed, 490 insertions(+), 11 deletions(-)
 create mode 100644 lib/hipe/regalloc/hipe_regalloc_prepass.erl

diff --git a/lib/hipe/amd64/hipe_amd64_registers.erl b/lib/hipe/amd64/hipe_amd64_registers.erl
index ada5311453..7c6965b938 100644
--- a/lib/hipe/amd64/hipe_amd64_registers.erl
+++ b/lib/hipe/amd64/hipe_amd64_registers.erl
@@ -253,6 +253,9 @@ ret(N) ->
     _ -> exit({?MODULE, ret, N})
   end.
 
+%% Note: the fact that (allocatable() UNION allocatable_x87() UNION
+%% allocatable_sse2()) is a subset of call_clobbered() is hard-coded in
+%% hipe_x86_defuse:insn_defs_all/1
 call_clobbered() ->
   [{?RAX,tagged},{?RAX,untagged},	% does the RA strip the type or not?
    {?RDX,tagged},{?RDX,untagged},
diff --git a/lib/hipe/arm/hipe_arm_defuse.erl b/lib/hipe/arm/hipe_arm_defuse.erl
index f57b0e601c..f92cf4f82a 100644
--- a/lib/hipe/arm/hipe_arm_defuse.erl
+++ b/lib/hipe/arm/hipe_arm_defuse.erl
@@ -22,6 +22,7 @@
 -module(hipe_arm_defuse).
 -export([insn_def_all/1, insn_use_all/1]).
 -export([insn_def_gpr/1, insn_use_gpr/1]).
+-export([insn_defs_all_gpr/1]).
 -include("hipe_arm.hrl").
 
 %%%
@@ -55,6 +56,12 @@ insn_def_gpr(I) ->
     _ -> []
   end.
 
+insn_defs_all_gpr(I) ->
+  case I of
+    #pseudo_call{} -> true;
+    _ -> false
+  end.
+
 call_clobbered_gpr() ->
   [hipe_arm:mk_temp(R, T)
    || {R,T} <- hipe_arm_registers:call_clobbered() ++ all_fp_pseudos()].
diff --git a/lib/hipe/arm/hipe_arm_registers.erl b/lib/hipe/arm/hipe_arm_registers.erl
index dcf039676b..3ecf2f2fdb 100644
--- a/lib/hipe/arm/hipe_arm_registers.erl
+++ b/lib/hipe/arm/hipe_arm_registers.erl
@@ -180,6 +180,8 @@ is_arg(R) ->
     _ -> false
   end.
 
+%% Note: the fact that allocatable_gpr() is a subset of call_clobbered() is
+%% hard-coded in hipe_arm_defuse:insn_defs_all_gpr/1
 call_clobbered() ->		% does the RA strip the type or not?
   [{?R0,tagged},{?R0,untagged},
    {?R1,tagged},{?R1,untagged},
diff --git a/lib/hipe/main/hipe.app.src b/lib/hipe/main/hipe.app.src
index 6c3a2741b3..e4796368c3 100644
--- a/lib/hipe/main/hipe.app.src
+++ b/lib/hipe/main/hipe.app.src
@@ -145,6 +145,7 @@
 	     hipe_profile,
 	     hipe_reg_worklists,
 	     hipe_regalloc_loop,
+	     hipe_regalloc_prepass,
 	     hipe_rtl,
 	     hipe_rtl_arch,
 	     hipe_rtl_arith_32,
diff --git a/lib/hipe/ppc/hipe_ppc_defuse.erl b/lib/hipe/ppc/hipe_ppc_defuse.erl
index 77b84dc574..305e88488d 100644
--- a/lib/hipe/ppc/hipe_ppc_defuse.erl
+++ b/lib/hipe/ppc/hipe_ppc_defuse.erl
@@ -22,6 +22,7 @@
 -module(hipe_ppc_defuse).
 -export([insn_def_all/1, insn_use_all/1]).
 -export([insn_def_gpr/1, insn_use_gpr/1]).
+-export([insn_defs_all_gpr/1, insn_defs_all_fpr/1]).
 -export([insn_def_fpr/1, insn_use_fpr/1]).
 -include("hipe_ppc.hrl").
 
@@ -52,6 +53,9 @@ insn_def_gpr(I) ->
     _ -> []
   end.
 
+insn_defs_all_gpr(#pseudo_call{}) -> true;
+insn_defs_all_gpr(_) -> false.
+
 call_clobbered_gpr() ->
   [hipe_ppc:mk_temp(R, T)
    || {R,T} <- hipe_ppc_registers:call_clobbered() ++ all_fp_pseudos()].
@@ -116,6 +120,9 @@ insn_def_fpr(I) ->
     _ -> []
   end.
 
+insn_defs_all_fpr(#pseudo_call{}) -> true;
+insn_defs_all_fpr(_) -> false.
+
 call_clobbered_fpr() ->
   [hipe_ppc:mk_temp(R, 'double') || R <- hipe_ppc_registers:allocatable_fpr()].
 
diff --git a/lib/hipe/ppc/hipe_ppc_registers.erl b/lib/hipe/ppc/hipe_ppc_registers.erl
index f4781d5ed7..8f6d9779fc 100644
--- a/lib/hipe/ppc/hipe_ppc_registers.erl
+++ b/lib/hipe/ppc/hipe_ppc_registers.erl
@@ -201,6 +201,8 @@ is_arg(R) ->
     _ -> false
   end.
 
+%% Note: the fact that allocatable_gpr() is a subset of call_clobbered() is
+%% hard-coded in hipe_ppc_defuse:insn_defs_all_gpr/1
 call_clobbered() ->		% does the RA strip the type or not?
   [{?R0,tagged},{?R0,untagged},
    %% R1 is reserved for C
diff --git a/lib/hipe/regalloc/Makefile b/lib/hipe/regalloc/Makefile
index ceb535f1c7..209f230a9b 100644
--- a/lib/hipe/regalloc/Makefile
+++ b/lib/hipe/regalloc/Makefile
@@ -51,6 +51,7 @@ MODULES = hipe_ig hipe_ig_moves hipe_moves \
 	  hipe_coalescing_regalloc \
 	  hipe_graph_coloring_regalloc \
 	  hipe_regalloc_loop \
+	  hipe_regalloc_prepass \
 	  hipe_ls_regalloc \
 	  hipe_ppc_specific hipe_ppc_specific_fp \
 	  hipe_sparc_specific hipe_sparc_specific_fp \
diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
index 2e5804337d..6ef79ce95d 100644
--- a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
+++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
@@ -33,6 +33,7 @@
          liveout/2,
          uses/1,
          defines/1,
+	 defines_all_alloc/1,
 	 def_use/1,
 	 is_arg/1,	%% used by hipe_ls_regalloc
 	 is_move/1,
@@ -174,6 +175,8 @@ defines(I) ->
 	     hipe_x86:temp_is_allocatable(X),
 	     hipe_x86:temp_type(X) =:= 'double'].
 
+defines_all_alloc(I) -> hipe_amd64_defuse:insn_defs_all(I).
+
 is_move(Instruction) ->
   case hipe_x86:is_fmove(Instruction) of
     true ->
diff --git a/lib/hipe/regalloc/hipe_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl
index e04d80f690..c696668399 100644
--- a/lib/hipe/regalloc/hipe_arm_specific.erl
+++ b/lib/hipe/regalloc/hipe_arm_specific.erl
@@ -40,6 +40,7 @@
 	 ,livein/2
 	 ,uses/1
 	 ,defines/1
+	 ,defines_all_alloc/1
 	]).
 
 %% for hipe_graph_coloring_regalloc:
@@ -129,6 +130,9 @@ defines(I) ->
   [X || X <- hipe_arm_defuse:insn_def_gpr(I),
 	hipe_arm:temp_is_allocatable(X)].
 
+defines_all_alloc(I) ->
+  hipe_arm_defuse:insn_defs_all_gpr(I).
+
 is_move(Instruction) ->
   case hipe_arm:is_pseudo_move(Instruction) of
     true ->
diff --git a/lib/hipe/regalloc/hipe_ppc_specific.erl b/lib/hipe/regalloc/hipe_ppc_specific.erl
index 988501c96f..79ca333865 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific.erl
@@ -40,6 +40,7 @@
 	 ,livein/2
 	 ,uses/1
 	 ,defines/1
+	 ,defines_all_alloc/1
 	]).
 
 %% for hipe_graph_coloring_regalloc:
@@ -129,6 +130,9 @@ defines(I) ->
   [X || X <- hipe_ppc_defuse:insn_def_gpr(I),
 	hipe_ppc:temp_is_allocatable(X)].
 
+defines_all_alloc(I) ->
+  hipe_ppc_defuse:insn_defs_all_gpr(I).
+
 is_move(Instruction) ->
   case hipe_ppc:is_pseudo_move(Instruction) of
     true ->
diff --git a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
index 6f00111777..4bf1385e0f 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
@@ -40,6 +40,7 @@
 	 ,livein/2
 	 ,uses/1
 	 ,defines/1
+	 ,defines_all_alloc/1
 	]).
 
 %% for hipe_graph_coloring_regalloc:
@@ -120,6 +121,9 @@ uses(I) ->
 defines(I) ->
   hipe_ppc_defuse:insn_def_fpr(I).
 
+defines_all_alloc(I) ->
+  hipe_ppc_defuse:insn_defs_all_fpr(I).
+
 is_move(I) ->
   hipe_ppc:is_pseudo_fmove(I).
  
diff --git a/lib/hipe/regalloc/hipe_regalloc_loop.erl b/lib/hipe/regalloc/hipe_regalloc_loop.erl
index fa42cdd0fb..33a7130ff1 100644
--- a/lib/hipe/regalloc/hipe_regalloc_loop.erl
+++ b/lib/hipe/regalloc/hipe_regalloc_loop.erl
@@ -43,7 +43,8 @@ ra_common(Defun, SpillIndex, Options, RegAllocMod, TargetMod) ->
 alloc(Defun, CFG, SpillLimit, SpillIndex, Options, RegAllocMod, TargetMod) ->
   ?inc_counter(ra_iteration_counter, 1),
   {Coloring, _NewSpillIndex, Liveness} =
-    RegAllocMod:regalloc(CFG, SpillIndex, SpillLimit,TargetMod, Options),
+    hipe_regalloc_prepass:regalloc(
+      RegAllocMod, CFG, SpillIndex, SpillLimit, TargetMod, Options),
   {NewDefun, DidSpill} = TargetMod:check_and_rewrite(Defun, Coloring),
   case DidSpill of
     false -> %% No new temps, we are done.
diff --git a/lib/hipe/regalloc/hipe_regalloc_prepass.erl b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
new file mode 100644
index 0000000000..f9df3a68de
--- /dev/null
+++ b/lib/hipe/regalloc/hipe_regalloc_prepass.erl
@@ -0,0 +1,400 @@
+%% -*- erlang-indent-level: 2 -*-
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 2016. All Rights Reserved.
+%%
+%% Licensed under the Apache License, Version 2.0 (the "License");
+%% you may not use this file except in compliance with the License.
+%% You may obtain a copy of the License at
+%%
+%%     http://www.apache.org/licenses/LICENSE-2.0
+%%
+%% Unless required by applicable law or agreed to in writing, software
+%% distributed under the License is distributed on an "AS IS" BASIS,
+%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+%% See the License for the specific language governing permissions and
+%% limitations under the License.
+%%
+%% %CopyrightEnd%
+%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%@doc
+%%	       PREPASS FOR ITERATED REGISTER ALLOCATORS
+%%
+%% Implements a trivial partial but optimal fast register allocator to be used
+%% as the first pass of the register allocation loop.
+%%
+%% The idea is to drastically reduce the number of temporaries, so as to speed
+%% up the real register allocators.
+%%
+%%  * Spills trivially unallocatable temps
+%%    This relies on the fact that calls intentionally clobber all registers.
+%%    Since this is the case, any temp that is alive over a call can't possibly
+%%    be allocated to a
+%%
+%% TODO: Partition the IG (without constructing it) into connected components
+%% and call the actual register allocator on them individually.
+
+-module(hipe_regalloc_prepass).
+-export([regalloc/6]).
+
+%% -ifndef(DEBUG).
+%% -compile(inline).
+%% -endif.
+
+%%-define(DO_ASSERT, 1).
+-include("../main/hipe.hrl").
+
+%% We present a "pseudo-target" to the register allocator we wrap.
+%% Note: all arities are +1 as we're currently using the parameterised module
+%% facility to store context data.
+-export([analyze/2,
+	 all_precoloured/1,
+	 allocatable/1,
+	 args/2,
+	 bb/3,
+	 breadthorder/2,
+	 def_use/2,
+	 defines/2,
+	 is_fixed/2,	% used by hipe_graph_coloring_regalloc
+	 is_global/2,
+	 is_move/2,
+	 is_precoloured/2,
+	 labels/2,
+	 livein/3,
+	 liveout/3,
+	 non_alloc/2,
+	 number_of_temporaries/2,
+	 physical_name/2,
+	 postorder/2,
+	 reg_nr/2,
+	 uses/2,
+	 var_range/2,
+	 reverse_postorder/2]).
+
+%% Eww, parameterised module. Can we fix it without having to touch all the
+%% register allocators?
+-record(?MODULE,
+	{target   :: module()
+	,sub      :: sub_map() % Translates temp numbers found in CFG and understood by
+			       % Target to temp numbers passed to RegAllocMod.
+	,inv      :: inv_map() % Translates temp numbers passed to RegAllocMod
+			       % to temp numbers found in CFG and understood by
+			       % Target
+	,max_phys :: temp()    % Exclusive upper bound on physical registers
+	}).
+
+-record(cfg,
+	{cfg     :: target_cfg()
+	,bbs     :: #{label() => hipe_bb:bb(instr())}
+	,max_reg :: temp()    % Exclusive upper bound on temp numbers
+	,live    :: target_liveness()
+	}).
+
+-record(instr,
+	{tgt_instr :: target_instr() % Not used, for debugging
+	,defuse    :: {[temp()], [temp()]}
+	,is_move   :: boolean()
+	}).
+%% -record(label,
+%% 	{no :: label()
+%% 	}).
+-type instr() :: #instr{} %% | #label{}
+		 .
+
+-type target_cfg() :: any().
+-type target_instr() :: any().
+-type target_temp() :: any().
+-type target_reg() :: non_neg_integer().
+-type target_liveness() :: any().
+-type spillno() :: non_neg_integer().
+-type temp() :: non_neg_integer().
+-type label() :: non_neg_integer().
+
+-spec regalloc(module(), target_cfg(), spillno(), spillno(), module(),
+	       proplists:proplist())
+	      -> {hipe_map(), spillno(), target_liveness()}.
+regalloc(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options) ->
+  Liveness = Target:analyze(CFG),
+  {BBs0, LivePseudos, _Unused, SpilledPseudos, SpillIndex} =
+    scan_cfg(CFG, Liveness, SpillIndex0, Target),
+
+  {SubMap, InvMap, MaxPhys, MaxR, SubSpillLimit} =
+    number_and_map(Target:all_precoloured(), LivePseudos, SpillLimit),
+  BBs = transform_cfg(BBs0, SubMap),
+  SubMod = #cfg{cfg=CFG, bbs=BBs, max_reg=MaxR, live=Liveness},
+  SubTarget = #?MODULE{target=Target, max_phys=MaxPhys, inv=InvMap, sub=SubMap},
+  case
+    RegAllocMod:regalloc(SubMod, SpillIndex, SubSpillLimit, SubTarget, Options)
+  of
+    {SubColoring, NewSpillIndex} -> ok;
+    {SubColoring, NewSpillIndex, _SubLiveness} -> ok
+  end,
+  ?ASSERT(check_coloring(SubColoring, SubMod, SubTarget)), % blame the RA ;)
+  SpillColors = [{T, {spill, S}} || {T, S} <- maps:to_list(SpilledPseudos)],
+  Coloring = translate_coloring(SubColoring, InvMap) ++ SpillColors,
+  ?ASSERT(check_coloring(Coloring, CFG, Target)), % Sanity-check
+  ?ASSERT(just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target,
+			  Options, Coloring, _Unused)),
+  {Coloring, NewSpillIndex, Liveness}.
+
+number_and_map(Phys, Pseud, SpillLimit) ->
+  MaxPhys = lists:max(Phys) + 1,
+  case Pseud of [] -> ok; _ ->
+      case lists:min(Pseud) of % Assertion
+	FirstPseudo when FirstPseudo >= MaxPhys -> ok
+      end end,
+  NrPseuds = length(Pseud),
+  MaxR = MaxPhys+NrPseuds,
+  PseudNrs = lists:zip(Pseud, lists:seq(MaxPhys, MaxR-1)),
+  MapList = lists:zip(Phys, Phys) % Physicals are identity-mapped
+    ++ PseudNrs,
+  SubMap = maps:from_list(MapList),
+  InvMap = maps:from_list([{Fake, Real} || {Real, Fake} <- MapList]),
+  LastPseudo = case Pseud of [] -> MaxPhys-1; _ -> lists:max(Pseud) end,
+  SubSpillLimit = if SpillLimit > LastPseudo -> MaxR;
+		     true -> map_get(SpillLimit, SubMap)
+		  end,
+  {SubMap, InvMap, MaxPhys, MaxR, SubSpillLimit}.
+
+-record(spill_state,
+	{map :: spill_map()
+	,ix  :: spillno()
+	}).
+-type spill_state() :: #spill_state{}.
+-type spill_map()   :: #{target_reg() => spillno()}.
+
+-spec scan_cfg(target_cfg(), target_liveness(), spillno(), module())
+	      -> {#{label() => [instr()]}
+		 ,ordsets:set(target_reg())
+		 ,ordsets:set(target_reg())
+		 ,spill_map()
+		 ,spillno()
+		 }.
+scan_cfg(CFG, Liveness, SpillIndex0, Target) ->
+  State0 = #spill_state{map=#{}, ix=SpillIndex0},
+  {BBs, Seen, #spill_state{map=Spill, ix=SpillIndex}} =
+    scan_bbs(Target:labels(CFG), CFG, Liveness, #{}, State0, #{}, Target),
+  SeenOSet = ordsets:from_list(maps:keys(Seen)),
+  SpillOSet = ordsets:from_list(maps:keys(Spill)),
+  PhysOSet = ordsets:from_list(Target:all_precoloured()),
+  Dead = ordsets:union(SpillOSet, PhysOSet),
+  LivePseudos = ordsets:subtract(SeenOSet, Dead),
+  {_TMin, _TMax} = Target:var_range(CFG),
+  _Unused = ordsets:subtract(lists:seq(_TMin, _TMax),
+			     ordsets:union(SeenOSet, PhysOSet)),
+  {BBs, LivePseudos, _Unused, Spill, SpillIndex}.
+
+-type seen() :: #{target_reg() => []}. % set
+
+-spec scan_bbs([label()], target_cfg(), target_liveness(), seen(),
+	       spill_state(), #{label() => [instr()]}, module())
+	      -> {#{label() => [instr()]}, seen(), spill_state()}.
+scan_bbs([], _CFG, _Liveness, Seen, State, BBs, _Target) -> {BBs, Seen, State};
+scan_bbs([L|Ls], CFG, Liveness, Seen0, State0, BBs, Target) ->
+    {Code, _, Seen, State} = scan_bb(hipe_bb:code(Target:bb(CFG, L)),
+				     t_liveout(Liveness, L, Target),
+				     Seen0, State0, Target),
+    scan_bbs(Ls, CFG, Liveness, Seen, State, BBs#{L=>Code}, Target).
+
+t_liveout(Liveness, L, Target) ->
+  %% FIXME: unnecessary sort; liveout is sorted, reg_names(...) should be sorted
+  %% or consist of a few sorted subsequences (per type)
+  ordsets:from_list(reg_names(Target:liveout(Liveness, L), Target)).
+
+-spec reg_names([target_temp()], module()) -> [target_reg()].
+reg_names(Regs, Target) ->
+  [Target:reg_nr(X) || X <- Regs].
+
+scan_bb([], Live, Seen, State, _Target) -> {[], Live, Seen, State};
+scan_bb([I|Is0], Live0, Seen0, State0, Target) ->
+  %% We could pass Target in the return tuple to make the stack frames
+  %% smaller, but without multireturn opt, it's probably not worth it.
+  {Is1, Live1, Seen1, State1} = scan_bb(Is0, Live0, Seen0, State0, Target),
+  {TDef, TUse} = Target:def_use(I),
+  Def = ordsets:from_list(reg_names(TDef, Target)),
+  Use = ordsets:from_list(reg_names(TUse, Target)),
+  Live = ordsets:union(Use, ToSpill = ordsets:subtract(Live1, Def)),
+  Seen = add_seen(Def, add_seen(Use, Seen1)),
+  State =
+    case Target:defines_all_alloc(I) of
+      false -> State1;
+      true -> spill_all(ToSpill, Target, State1)
+    end,
+  NewI = #instr{tgt_instr=I, defuse={Def, Use}, is_move=Target:is_move(I)},
+  {[NewI|Is1], Live, Seen, State}.
+
+add_seen([], Seen) -> Seen;
+add_seen([R|Rs], Seen) -> add_seen(Rs, Seen#{R=>[]}).
+
+spill_all([], _Target, State) -> State;
+spill_all([R|Rs], Target, State=#spill_state{map=Map, ix=Ix}) ->
+  case Target:is_precoloured(R) or maps:is_key(R, Map) of
+    true -> spill_all(Rs, Target, State);
+    false -> spill_all(Rs, Target, State#spill_state{map=Map#{R=>Ix}, ix=Ix+1})
+  end.
+
+transform_cfg(BBs0, SubMap) ->
+  maps:map(fun(_, BB) -> transform_bb(BB, SubMap) end, BBs0).
+
+transform_bb(BB, SubMap) ->
+  hipe_bb:mk_bb([I#instr{defuse={map_get_all_partial(Def, SubMap),
+				 map_get_all_partial(Use, SubMap)}}
+		 || I = #instr{defuse={Def,Use}} <- BB]).
+
+-spec translate_coloring(hipe_map(), _) -> hipe_map().
+translate_coloring(SubColoring, InvMap) ->
+  lists:map(fun({T, P}) -> {map_get(T, InvMap), P} end, SubColoring).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Interference graph partitioning
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% We partition the program
+
+%% The algorithm considers two kinds of components; those that are local to a
+%% basic block, and those that are not. The key is that any basic block belongs
+%% to at most two non-local components; one from the beginning to the first
+%% split point, and one from the end to the last split point.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Temp map ADT
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+-type sub_map() :: #{target_temp() => temp()}.
+-type inv_map() :: #{temp() => target_temp()}.
+map_get(Temp, Map) when is_integer(Temp) -> maps:get(Temp, Map).
+
+%% map_get_all(Ts, Map) -> [map_get(T, Map) || T <- Ts].
+
+map_get_all_partial([], _) -> [];
+map_get_all_partial([T|Ts], Map) when is_integer(T) ->
+  case Map of
+    #{T := R} -> [R|map_get_all_partial(Ts, Map)];
+    #{} -> map_get_all_partial(Ts, Map)
+  end.
+
+-ifdef(DO_ASSERT).
+%%%%%%%%%%%%%%%%%%%%
+%% Check that the coloring is correct (if the IG is correct):
+%%
+
+%% 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)).
+
+check_coloring(Coloring, CFG, Target) ->
+  ?report0("checking coloring ~p~n",[Coloring]),
+  IG = hipe_ig:build(CFG, Target),
+  check_cols(hipe_vectors:list(hipe_ig:adj_list(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,Neighbours}|Xs], Cols) ->
+  Cs = [{N, check_color_of(N, Cols)} || N <- Neighbours],
+  C = check_color_of(X, Cols),
+  case valid_coloring(X, C, Cs) of
+    yes ->
+      check_cols(Xs, Cols);
+    {no,Invalids} ->
+      ?msg("node ~p has same color (~p) as ~p~n", [X,C,Invalids]),
+      check_cols(Xs, Cols) andalso false
+  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).
+
+%%%%%%%%%%%%%%%%%%%%
+%% Check that no register allocation opportinities were missed due to ?MODULE
+%%
+just_as_good_as(RegAllocMod, CFG, SpillIndex0, SpillLimit, Target, Options,
+		Coloring, Unused) ->
+  {CheckColoring, _} = RegAllocMod:regalloc(CFG, SpillIndex0, SpillLimit,
+					    Target, Options),
+  Now   = lists:sort([vt(C) || C <- Coloring]),
+  Check = lists:sort([vt(C) || C={R,_} <- CheckColoring,
+			       not ordsets:is_element(R, Unused)]),
+  case Now of
+    Check -> true;
+    _ ->
+      io:fwrite(standard_error, "Colorings differ (~w, sub: ~w, full: ~w)!~n"
+		%% "Sub:~w~n"
+		"Unused: ~w~n"
+		"Now:~w~nCorrect:~w~n",
+		[Target, count(Coloring), count(CheckColoring),
+		 %% SubColoring,
+		 Unused,
+		 Now -- Check, Check -- Now]),
+	false
+  end.
+
+count(C) -> {length([[] || {_, {reg, _}} <- C]),
+	     length([[] || {_, {spill, _}} <- C])}.
+
+vt({R, {reg, _}}) -> {R, reg};
+vt({R, {spill, _}}) -> {R, spill}.
+-endif.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% Pseudo-target interface
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+analyze(Cfg, _ModRec) -> Cfg.
+bb(#cfg{bbs=BBs}, Ix, _ModRec) -> maps:get(Ix, BBs).
+args(Arity, #?MODULE{target=Target, sub=SubM}) ->
+    map_get(Target:args(Arity), SubM).
+labels(#cfg{cfg=CFG}, #?MODULE{target=Target}) -> Target:labels(CFG).
+livein(#cfg{live=Live}, Lb, #?MODULE{target=Target, sub=SubM}) ->
+  map_get_all_partial(reg_names(Target:livein(Live, Lb), Target), SubM). % Should we precompute?
+liveout(#cfg{live=Live}, Lb, #?MODULE{target=Target, sub=SubM}) ->
+  map_get_all_partial(reg_names(Target:liveout(Live, Lb), Target), SubM). % dito
+uses(I, MR) -> element(2, def_use(I, MR)).
+defines(I, MR) -> element(1, def_use(I, MR)).
+def_use(#instr{defuse=DefUse}, _ModRec) -> DefUse.
+is_move(#instr{is_move=IM}, _ModRec) -> IM.
+is_fixed(Reg, #?MODULE{target=Target,inv=InvM}) ->
+  Target:is_fixed(map_get(Reg, InvM)). % XXX: Is this hot?
+is_global(Reg, #?MODULE{target=Target,max_phys=MaxPhys}) when Reg < MaxPhys ->
+  Target:is_global(Reg). % assume id-map
+is_precoloured(Reg, #?MODULE{max_phys=MaxPhys}) -> Reg < MaxPhys.
+reg_nr(Reg, _ModRec) -> Reg. % After mapping (naturally)
+non_alloc(#cfg{cfg=CFG}, #?MODULE{target=Target,sub=SubM}) ->
+  map_get_all_partial(reg_names(Target:non_alloc(CFG), Target), SubM).
+number_of_temporaries(#cfg{max_reg=MaxR}, _ModRec) -> MaxR.
+allocatable(#?MODULE{target=Target}) -> Target:allocatable(). % assume id-map
+physical_name(Reg, _ModRec) -> Reg. % XXX: is this correct?
+all_precoloured(#?MODULE{target=Target}) -> Target:all_precoloured(). % dito
+var_range(#cfg{cfg=CFG, max_reg=MaxReg}, #?MODULE{target=Target}) ->
+  {0, _} = Target:var_range(CFG),
+  {0, MaxReg-1}. % What is the correct answer?
+
+breadthorder(#cfg{cfg=CFG}, #?MODULE{target=Target}) ->
+  Target:breadthorder(CFG).
+postorder(#cfg{cfg=CFG}, #?MODULE{target=Target}) -> Target:postorder(CFG).
+reverse_postorder(#cfg{cfg=CFG}, #?MODULE{target=Target}) ->
+  Target:reverse_postorder(CFG).
diff --git a/lib/hipe/regalloc/hipe_sparc_specific.erl b/lib/hipe/regalloc/hipe_sparc_specific.erl
index 29d0908caf..7df1bbe113 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific.erl
@@ -40,6 +40,7 @@
 	 ,livein/2
 	 ,uses/1
 	 ,defines/1
+	 ,defines_all_alloc/1
 	]).
 
 %% for hipe_graph_coloring_regalloc:
@@ -129,6 +130,9 @@ defines(I) ->
   [X || X <- hipe_sparc_defuse:insn_def_gpr(I),
 	hipe_sparc:temp_is_allocatable(X)].
 
+defines_all_alloc(I) ->
+  hipe_sparc_defuse:insn_defs_all_gpr(I).
+
 is_move(Instruction) ->
   case hipe_sparc:is_pseudo_move(Instruction) of
     true ->
diff --git a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
index 08c2541b41..fd80053708 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
@@ -40,6 +40,7 @@
 	 ,livein/2
 	 ,uses/1
 	 ,defines/1
+	 ,defines_all_alloc/1
 	]).
 
 %% for hipe_graph_coloring_regalloc:
@@ -120,6 +121,9 @@ uses(I) ->
 defines(I) ->
   hipe_sparc_defuse:insn_def_fpr(I).
 
+defines_all_alloc(I) ->
+  hipe_sparc_defuse:insn_defs_all_fpr(I).
+
 is_move(I) ->
   hipe_sparc:is_pseudo_fmove(I).
  
diff --git a/lib/hipe/regalloc/hipe_temp_map.erl b/lib/hipe/regalloc/hipe_temp_map.erl
index 4085a0e1a7..171c2fb019 100644
--- a/lib/hipe/regalloc/hipe_temp_map.erl
+++ b/lib/hipe/regalloc/hipe_temp_map.erl
@@ -33,7 +33,7 @@
 
 -module(hipe_temp_map).
 
--export([cols2tuple/2, is_spilled/2, to_substlist/1]).
+-export([cols2tuple/2, find/2, is_spilled/2, to_substlist/1]).
 
 -include("../main/hipe.hrl").
 
@@ -50,12 +50,10 @@
 -spec cols2tuple(hipe_map(), atom()) -> hipe_temp_map().
 
 cols2tuple(Map, Target) ->
-  ?ASSERT(check_list(Map)),
-  SortedMap = lists:keysort(1, 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). 
 
@@ -66,7 +64,7 @@ cols2tuple(_, [], 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) ->
+cols2tuple(N, SourceMapping=[{R,_}|_], Vs, Target) when N < R ->
   %% The source was sparse, make up some placeholders...
   Val = 	      
     case Target:is_precoloured(N) of
@@ -82,7 +80,7 @@ cols2tuple(N, SourceMapping, Vs, Target) ->
 -spec is_spilled(non_neg_integer(), hipe_temp_map()) -> boolean().
 
 is_spilled(Temp, Map) ->
-  case element(Temp+1, Map) of
+  case find(Temp, Map) of
     {reg, _R} -> false;
     {fp_reg, _R}-> false;
     {spill, _N} -> true;
@@ -106,9 +104,10 @@ is_spilled(Temp, Map) ->
 %%     {spill, _N} -> false;
 %%     unknown -> false
 %%   end.
-%% 
-%% %% Returns the inf temp Temp is mapped to.
-%% find(Temp, Map) -> element(Temp+1, Map).
+
+%% Returns the inf temp Temp is mapped to.
+find(Temp, Map) when Temp < tuple_size(Map) -> element(Temp+1, Map);
+find(_,    Map) when is_tuple(Map) -> unknown. % consistency with cols2tuple/2
 
 
 %%
diff --git a/lib/hipe/regalloc/hipe_x86_specific.erl b/lib/hipe/regalloc/hipe_x86_specific.erl
index f1007c95ed..2720af92c1 100644
--- a/lib/hipe/regalloc/hipe_x86_specific.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific.erl
@@ -47,6 +47,7 @@
 	 liveout/2,
 	 uses/1,
 	 defines/1,
+	 defines_all_alloc/1,
 	 def_use/1,
 	 is_arg/1,	% used by hipe_ls_regalloc
 	 is_move/1,
@@ -176,6 +177,8 @@ defines(I) ->
 	hipe_x86:temp_is_allocatable(X),
 	hipe_x86:temp_type(X) =/= 'double'].
 
+defines_all_alloc(I) -> ?HIPE_X86_DEFUSE:insn_defs_all(I).
+
 is_move(Instruction) ->
   case hipe_x86:is_move(Instruction) of
     true ->
diff --git a/lib/hipe/regalloc/hipe_x86_specific_x87.erl b/lib/hipe/regalloc/hipe_x86_specific_x87.erl
index 0c022d5a27..cd4d02491d 100644
--- a/lib/hipe/regalloc/hipe_x86_specific_x87.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific_x87.erl
@@ -53,6 +53,7 @@
 	 liveout/2,
 	 uses/1,
 	 defines/1,
+	 defines_all_alloc/1,
 	 is_global/1,
 	 reg_nr/1,
 	 physical_name/1,
@@ -162,6 +163,8 @@ defines(I) ->
  	     hipe_x86:temp_is_allocatable(X),
  	     temp_is_double(X)].
 
+defines_all_alloc(I) -> hipe_amd64_defuse:insn_defs_all(I).
+
 temp_is_double(Temp) ->
   hipe_x86:temp_type(Temp) =:= 'double'.
 
diff --git a/lib/hipe/sparc/hipe_sparc_defuse.erl b/lib/hipe/sparc/hipe_sparc_defuse.erl
index 4f66299f1d..4b5a19a19d 100644
--- a/lib/hipe/sparc/hipe_sparc_defuse.erl
+++ b/lib/hipe/sparc/hipe_sparc_defuse.erl
@@ -23,6 +23,7 @@
 -export([insn_def_all/1, insn_use_all/1]).
 -export([insn_def_gpr/1, insn_use_gpr/1]).
 -export([insn_def_fpr/1, insn_use_fpr/1]).
+-export([insn_defs_all_gpr/1, insn_defs_all_fpr/1]).
 -include("hipe_sparc.hrl").
 
 %%%
@@ -51,6 +52,12 @@ insn_def_gpr(I) ->
     _ -> []
   end.
 
+insn_defs_all_gpr(I) ->
+  case I of
+    #pseudo_call{} -> true;
+    _ -> false
+  end.
+
 call_clobbered_gpr() ->
   [hipe_sparc:mk_temp(R, T)
    || {R,T} <- hipe_sparc_registers:call_clobbered() ++ all_fp_pseudos()].
@@ -115,6 +122,12 @@ insn_def_fpr(I) ->
     _ -> []
   end.
 
+insn_defs_all_fpr(I) ->
+  case I of
+    #pseudo_call{} -> true;
+    _ -> false
+  end.
+
 call_clobbered_fpr() ->
   [hipe_sparc:mk_temp(R, 'double') || R <- hipe_sparc_registers:allocatable_fpr()].
 
diff --git a/lib/hipe/sparc/hipe_sparc_registers.erl b/lib/hipe/sparc/hipe_sparc_registers.erl
index 6681a10070..20138836dd 100644
--- a/lib/hipe/sparc/hipe_sparc_registers.erl
+++ b/lib/hipe/sparc/hipe_sparc_registers.erl
@@ -249,6 +249,8 @@ is_arg(R) ->
     _ -> false
   end.
 
+%% Note: the fact that allocatable_gpr() is a subset of call_clobbered() is
+%% hard-coded in hipe_sparc_defuse:insn_defs_all_gpr/1
 call_clobbered() ->		% does the RA strip the type or not?
   [%% ?G0 is the non-allocatable constant zero
    {?G1,tagged},{?G1,untagged},
diff --git a/lib/hipe/x86/hipe_x86_defuse.erl b/lib/hipe/x86/hipe_x86_defuse.erl
index 9cba6cbe4b..4455def74e 100644
--- a/lib/hipe/x86/hipe_x86_defuse.erl
+++ b/lib/hipe/x86/hipe_x86_defuse.erl
@@ -35,7 +35,7 @@
 -endif.
 
 -module(?HIPE_X86_DEFUSE).
--export([insn_def/1, insn_use/1]). %% src_use/1]).
+-export([insn_def/1, insn_defs_all/1, insn_use/1]). %% src_use/1]).
 -include("../x86/hipe_x86.hrl").
 
 %%%
@@ -64,6 +64,16 @@ insn_def(I) ->
     _ -> []
   end.
 
+
+%% @doc Answers whether instruction I defines all allocatable registers. Used by
+%% hipe_regalloc_prepass.
+-spec insn_defs_all(_) -> boolean().
+insn_defs_all(I) ->
+  case I of
+    #pseudo_call{} -> true;
+    _ -> false
+  end.
+
 dst_def(Dst) ->
   case Dst of
     #x86_temp{} -> [Dst];
diff --git a/lib/hipe/x86/hipe_x86_registers.erl b/lib/hipe/x86/hipe_x86_registers.erl
index 179d734501..f00bbfb280 100644
--- a/lib/hipe/x86/hipe_x86_registers.erl
+++ b/lib/hipe/x86/hipe_x86_registers.erl
@@ -224,6 +224,8 @@ ret(N) ->
 	    exit({?MODULE, ret, N})
     end.
 
+%% Note: the fact that (allocatable() UNION allocatable_x87()) is a subset of
+%% call_clobbered() is hard-coded in hipe_x86_defuse:insn_defs_all/1
 call_clobbered() ->
     [{?EAX,tagged},{?EAX,untagged},	% does the RA strip the type or not?
      {?EDX,tagged},{?EDX,untagged},
-- 
cgit v1.2.3