aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMagnus Lång <[email protected]>2016-06-10 19:29:22 +0200
committerMagnus Lång <[email protected]>2016-08-30 17:21:20 +0200
commitd9b091472f9afb216fe9f0c763053baf89390a6c (patch)
treee7904d4146ac66bcbae6ac4a7e20874c6a7c07e1
parent1567585dda8bc604871be06a37aa5d19ad6d28f3 (diff)
downloadotp-d9b091472f9afb216fe9f0c763053baf89390a6c.tar.gz
otp-d9b091472f9afb216fe9f0c763053baf89390a6c.tar.bz2
otp-d9b091472f9afb216fe9f0c763053baf89390a6c.zip
hipe_arm: Minimise CFG<->linear conversions
Now, there will only ever be a single Linear->CFG conversion, just after lowering from RTL, and only ever a single CFG->Linear conversion, just before the finalise pass. Both of these now happen in hipe_arm_main.
-rw-r--r--lib/hipe/arm/hipe_arm_cfg.erl2
-rw-r--r--lib/hipe/arm/hipe_arm_frame.erl97
-rw-r--r--lib/hipe/arm/hipe_arm_main.erl8
-rw-r--r--lib/hipe/arm/hipe_arm_ra.erl32
-rw-r--r--lib/hipe/arm/hipe_arm_ra_finalise.erl11
-rw-r--r--lib/hipe/arm/hipe_arm_ra_ls.erl15
-rw-r--r--lib/hipe/arm/hipe_arm_ra_naive.erl8
-rw-r--r--lib/hipe/arm/hipe_arm_ra_postconditions.erl19
-rw-r--r--lib/hipe/regalloc/hipe_arm_specific.erl8
9 files changed, 97 insertions, 103 deletions
diff --git a/lib/hipe/arm/hipe_arm_cfg.erl b/lib/hipe/arm/hipe_arm_cfg.erl
index f2fa0a5164..2fb6675da9 100644
--- a/lib/hipe/arm/hipe_arm_cfg.erl
+++ b/lib/hipe/arm/hipe_arm_cfg.erl
@@ -24,6 +24,7 @@
-export([init/1,
labels/1, start_label/1,
succ/2,
+ map_bbs/2, fold_bbs/3,
bb/2, bb_add/3]).
-export([postorder/1]).
-export([linearise/1]).
@@ -35,6 +36,7 @@
-define(BREADTH_ORDER,true). % for linear scan
-define(PARAMS_NEEDED,true).
-define(START_LABEL_UPDATE_NEEDED,true).
+-define(MAP_FOLD_NEEDED,true).
-include("hipe_arm.hrl").
-include("../flow/cfg.hrl").
diff --git a/lib/hipe/arm/hipe_arm_frame.erl b/lib/hipe/arm/hipe_arm_frame.erl
index e1e441a967..9a349b47d3 100644
--- a/lib/hipe/arm/hipe_arm_frame.erl
+++ b/lib/hipe/arm/hipe_arm_frame.erl
@@ -27,16 +27,14 @@
-define(LIVENESS_ALL, hipe_arm_liveness_gpr). % since we have no FP yet
-frame(Defun) ->
- Formals = fix_formals(hipe_arm:defun_formals(Defun)),
- Temps0 = all_temps(hipe_arm:defun_code(Defun), Formals),
- MinFrame = defun_minframe(Defun),
+frame(CFG) ->
+ Formals = fix_formals(hipe_arm_cfg:params(CFG)),
+ Temps0 = all_temps(CFG, Formals),
+ MinFrame = defun_minframe(CFG),
Temps = ensure_minframe(MinFrame, Temps0),
- ClobbersLR = clobbers_lr(hipe_arm:defun_code(Defun)),
- CFG0 = hipe_arm_cfg:init(Defun),
- Liveness = ?LIVENESS_ALL:analyse(CFG0),
- CFG1 = do_body(CFG0, Liveness, Formals, Temps, ClobbersLR),
- hipe_arm_cfg:linearise(CFG1).
+ ClobbersLR = clobbers_lr(CFG),
+ Liveness = ?LIVENESS_ALL:analyse(CFG),
+ do_body(CFG, Liveness, Formals, Temps, ClobbersLR).
fix_formals(Formals) ->
fix_formals(hipe_arm_registers:nr_args(), Formals).
@@ -51,32 +49,21 @@ do_body(CFG0, Liveness, Formals, Temps, ClobbersLR) ->
do_prologue(CFG1, Context).
do_blocks(CFG, Context) ->
- Labels = hipe_arm_cfg:labels(CFG),
- do_blocks(Labels, CFG, Context).
+ hipe_arm_cfg:map_bbs(fun(Lbl, BB) -> do_block(Lbl, BB, Context) end, CFG).
-do_blocks([Label|Labels], CFG, Context) ->
+do_block(Label, Block, Context) ->
Liveness = context_liveness(Context),
LiveOut = ?LIVENESS_ALL:liveout(Liveness, Label),
- Block = hipe_arm_cfg:bb(CFG, Label),
Code = hipe_bb:code(Block),
- NewCode = do_block(Code, LiveOut, Context),
- NewBlock = hipe_bb:code_update(Block, NewCode),
- NewCFG = hipe_arm_cfg:bb_add(CFG, Label, NewBlock),
- do_blocks(Labels, NewCFG, Context);
-do_blocks([], CFG, _) ->
- CFG.
-
-do_block(Insns, LiveOut, Context) ->
- do_block(Insns, LiveOut, Context, context_framesize(Context), []).
+ NewCode = do_block(Code, LiveOut, Context, context_framesize(Context), []),
+ hipe_bb:code_update(Block, NewCode).
do_block([I|Insns], LiveOut, Context, FPoff0, RevCode) ->
{NewIs, FPoff1} = do_insn(I, LiveOut, Context, FPoff0),
do_block(Insns, LiveOut, Context, FPoff1, lists:reverse(NewIs, RevCode));
do_block([], _, Context, FPoff, RevCode) ->
FPoff0 = context_framesize(Context),
- if FPoff =:= FPoff0 -> [];
- true -> exit({?MODULE,do_block,FPoff})
- end,
+ FPoff0 = FPoff,
lists:reverse(RevCode, []).
do_insn(I, LiveOut, Context, FPoff) ->
@@ -543,39 +530,46 @@ temp_is_pseudo(Temp) ->
%%% Detect if a Defun's body clobbers LR.
%%%
-clobbers_lr(Insns) ->
+clobbers_lr(CFG) ->
LRreg = hipe_arm_registers:lr(),
LRtagged = hipe_arm:mk_temp(LRreg, 'tagged'),
LRuntagged = hipe_arm:mk_temp(LRreg, 'untagged'),
- clobbers_lr(Insns, LRtagged, LRuntagged).
-
-clobbers_lr([I|Insns], LRtagged, LRuntagged) ->
- Defs = hipe_arm_defuse:insn_def_gpr(I),
- case lists:member(LRtagged, Defs) of
- true -> true;
- false ->
- case lists:member(LRuntagged, Defs) of
- true -> true;
- false -> clobbers_lr(Insns, LRtagged, LRuntagged)
- end
- end;
-clobbers_lr([], _LRtagged, _LRuntagged) -> false.
+ any_insn(fun(I) ->
+ Defs = hipe_arm_defuse:insn_def_gpr(I),
+ lists:member(LRtagged, Defs)
+ orelse lists:member(LRuntagged, Defs)
+ end, CFG).
+
+any_insn(Pred, CFG) ->
+ %% Abuse fold to do an efficient "any"-operation using nonlocal control flow
+ FoundSatisfying = make_ref(),
+ try fold_insns(fun (I, _) ->
+ case Pred(I) of
+ true -> throw(FoundSatisfying);
+ false -> false
+ end
+ end, false, CFG)
+ of _ -> false
+ catch FoundSatisfying -> true
+ end.
%%%
%%% Build the set of all temps used in a Defun's body.
%%%
-all_temps(Code, Formals) ->
- S0 = find_temps(Code, tset_empty()),
+all_temps(CFG, Formals) ->
+ S0 = fold_insns(fun find_temps/2, tset_empty(), CFG),
S1 = tset_del_list(S0, Formals),
tset_filter(S1, fun(T) -> temp_is_pseudo(T) end).
-find_temps([I|Insns], S0) ->
+find_temps(I, S0) ->
S1 = tset_add_list(S0, hipe_arm_defuse:insn_def_all(I)),
- S2 = tset_add_list(S1, hipe_arm_defuse:insn_use_all(I)),
- find_temps(Insns, S2);
-find_temps([], S) ->
- S.
+ tset_add_list(S1, hipe_arm_defuse:insn_use_all(I)).
+
+fold_insns(Fun, InitAcc, CFG) ->
+ hipe_arm_cfg:fold_bbs(
+ fun(_, BB, Acc0) -> lists:foldl(Fun, Acc0, hipe_bb:code(BB)) end,
+ InitAcc, CFG).
tset_empty() ->
gb_sets:new().
@@ -604,16 +598,11 @@ tset_to_list(S) ->
%%% in the middle of a tailcall.
%%%
-defun_minframe(Defun) ->
- MaxTailArity = body_mta(hipe_arm:defun_code(Defun), 0),
- MyArity = length(fix_formals(hipe_arm:defun_formals(Defun))),
+defun_minframe(CFG) ->
+ MaxTailArity = fold_insns(fun insn_mta/2, 0, CFG),
+ MyArity = length(fix_formals(hipe_arm_cfg:params(CFG))),
erlang:max(MaxTailArity - MyArity, 0).
-body_mta([I|Code], MTA) ->
- body_mta(Code, insn_mta(I, MTA));
-body_mta([], MTA) ->
- MTA.
-
insn_mta(I, MTA) ->
case I of
#pseudo_tailcall{arity=Arity} ->
diff --git a/lib/hipe/arm/hipe_arm_main.erl b/lib/hipe/arm/hipe_arm_main.erl
index c81cd92160..8a7fa86394 100644
--- a/lib/hipe/arm/hipe_arm_main.erl
+++ b/lib/hipe/arm/hipe_arm_main.erl
@@ -24,12 +24,14 @@
rtl_to_arm(MFA, RTL, Options) ->
Defun1 = hipe_rtl_to_arm:translate(RTL),
+ CFG1 = hipe_arm_cfg:init(Defun1),
%% io:format("~w: after translate\n", [?MODULE]),
%% hipe_arm_pp:pp(Defun1),
- Defun2 = hipe_arm_ra:ra(Defun1, Options),
+ CFG2 = hipe_arm_ra:ra(CFG1, Options),
%% io:format("~w: after regalloc\n", [?MODULE]),
- %% hipe_arm_pp:pp(Defun2),
- Defun3 = hipe_arm_frame:frame(Defun2),
+ %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG2)),
+ CFG3 = hipe_arm_frame:frame(CFG2),
+ Defun3 = hipe_arm_cfg:linearise(CFG3),
%% io:format("~w: after frame\n", [?MODULE]),
%% hipe_arm_pp:pp(Defun3),
Defun4 = hipe_arm_finalise:finalise(Defun3, Options),
diff --git a/lib/hipe/arm/hipe_arm_ra.erl b/lib/hipe/arm/hipe_arm_ra.erl
index 2f65e864fd..5a7884b63c 100644
--- a/lib/hipe/arm/hipe_arm_ra.erl
+++ b/lib/hipe/arm/hipe_arm_ra.erl
@@ -22,36 +22,36 @@
-module(hipe_arm_ra).
-export([ra/2]).
-ra(Defun0, Options) ->
- %% hipe_arm_pp:pp(Defun0),
- {Defun1, Coloring_fp, SpillIndex}
+ra(CFG0, Options) ->
+ %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG0)),
+ {CFG1, Coloring_fp, SpillIndex}
= case proplists:get_bool(inline_fp, Options) of
%% true ->
-%% hipe_regalloc_loop:ra_fp(Defun0, Options,
+%% hipe_regalloc_loop:ra_fp(CFG0, Options,
%% hipe_coalescing_regalloc,
%% hipe_arm_specific_fp);
false ->
- {Defun0,[],0}
+ {CFG0,[],0}
end,
- %% hipe_arm_pp:pp(Defun1),
- {Defun2, Coloring}
+ %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG1)),
+ {CFG2, Coloring}
= case proplists:get_value(regalloc, Options, coalescing) of
coalescing ->
- ra(Defun1, SpillIndex, Options, hipe_coalescing_regalloc);
+ ra(CFG1, SpillIndex, Options, hipe_coalescing_regalloc);
optimistic ->
- ra(Defun1, SpillIndex, Options, hipe_optimistic_regalloc);
+ ra(CFG1, SpillIndex, Options, hipe_optimistic_regalloc);
graph_color ->
- ra(Defun1, SpillIndex, Options, hipe_graph_coloring_regalloc);
+ ra(CFG1, SpillIndex, Options, hipe_graph_coloring_regalloc);
linear_scan ->
- hipe_arm_ra_ls:ra(Defun1, SpillIndex, Options);
+ hipe_arm_ra_ls:ra(CFG1, SpillIndex, Options);
naive ->
- hipe_arm_ra_naive:ra(Defun1, Coloring_fp, Options);
+ hipe_arm_ra_naive:ra(CFG1, Coloring_fp, Options);
_ ->
exit({unknown_regalloc_compiler_option,
proplists:get_value(regalloc,Options)})
end,
- %% hipe_arm_pp:pp(Defun2),
- hipe_arm_ra_finalise:finalise(Defun2, Coloring, Coloring_fp).
+ %% hipe_arm_pp:pp(hipe_arm_cfg:linearise(CFG2)),
+ hipe_arm_ra_finalise:finalise(CFG2, Coloring, Coloring_fp).
-ra(Defun, SpillIndex, Options, RegAllocMod) ->
- hipe_regalloc_loop:ra(Defun, SpillIndex, Options, RegAllocMod, hipe_arm_specific).
+ra(CFG, SpillIndex, Options, RegAllocMod) ->
+ hipe_regalloc_loop:ra(CFG, SpillIndex, Options, RegAllocMod, hipe_arm_specific).
diff --git a/lib/hipe/arm/hipe_arm_ra_finalise.erl b/lib/hipe/arm/hipe_arm_ra_finalise.erl
index 4faeadcd7f..2a3fded147 100644
--- a/lib/hipe/arm/hipe_arm_ra_finalise.erl
+++ b/lib/hipe/arm/hipe_arm_ra_finalise.erl
@@ -23,12 +23,13 @@
-export([finalise/3]).
-include("hipe_arm.hrl").
-finalise(Defun, TempMap, _FPMap0=[]) ->
- Code = hipe_arm:defun_code(Defun),
- {_, SpillLimit} = hipe_arm:defun_var_range(Defun),
+finalise(CFG, TempMap, _FPMap0=[]) ->
+ {_, SpillLimit} = hipe_gensym:var_range(arm),
Map = mk_ra_map(TempMap, SpillLimit),
- NewCode = ra_code(Code, Map, []),
- Defun#defun{code=NewCode}.
+ hipe_arm_cfg:map_bbs(fun(_Lbl, BB) -> ra_bb(BB, Map) end, CFG).
+
+ra_bb(BB, Map) ->
+ hipe_bb:code_update(BB, ra_code(hipe_bb:code(BB), Map, [])).
ra_code([I|Insns], Map, Accum) ->
ra_code(Insns, Map, [ra_insn(I, Map) | Accum]);
diff --git a/lib/hipe/arm/hipe_arm_ra_ls.erl b/lib/hipe/arm/hipe_arm_ra_ls.erl
index 7891403fc3..f9193ca9e0 100644
--- a/lib/hipe/arm/hipe_arm_ra_ls.erl
+++ b/lib/hipe/arm/hipe_arm_ra_ls.erl
@@ -23,14 +23,11 @@
-module(hipe_arm_ra_ls).
-export([ra/3]).
-ra(Defun, SpillIndex, Options) ->
- NewDefun = Defun, %% hipe_${ARCH}_ra_rename:rename(Defun,Options),
- CFG = hipe_arm_cfg:init(NewDefun),
+ra(CFG, SpillIndex, Options) ->
SpillLimit = hipe_arm_specific:number_of_temporaries(CFG),
- alloc(NewDefun, SpillIndex, SpillLimit, Options).
+ alloc(CFG, SpillIndex, SpillLimit, Options).
-alloc(Defun, SpillIndex, SpillLimit, Options) ->
- CFG = hipe_arm_cfg:init(Defun),
+alloc(CFG, SpillIndex, SpillLimit, Options) ->
{Coloring, _NewSpillIndex, Liveness} =
regalloc(
CFG,
@@ -41,16 +38,16 @@ alloc(Defun, SpillIndex, SpillLimit, Options) ->
[hipe_arm_cfg:start_label(CFG)],
SpillIndex, SpillLimit, Options,
hipe_arm_specific),
- {NewDefun, _DidSpill} =
+ {NewCFG, _DidSpill} =
hipe_arm_ra_postconditions:check_and_rewrite(
- Defun, Coloring, 'linearscan'),
+ CFG, Coloring, 'linearscan'),
TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific),
{SpillMap, _NewSpillIndex2} =
hipe_spillmin:stackalloc(CFG, Liveness, [], SpillIndex, Options,
hipe_arm_specific, TempMap),
Coloring2 =
hipe_spillmin:mapmerge(hipe_temp_map:to_substlist(TempMap), SpillMap),
- {NewDefun, Coloring2}.
+ {NewCFG, Coloring2}.
regalloc(CFG, PhysRegs, Entrypoints, SpillIndex, DontSpill, Options, Target) ->
hipe_ls_regalloc:regalloc(
diff --git a/lib/hipe/arm/hipe_arm_ra_naive.erl b/lib/hipe/arm/hipe_arm_ra_naive.erl
index 6201269f44..0ea4b04092 100644
--- a/lib/hipe/arm/hipe_arm_ra_naive.erl
+++ b/lib/hipe/arm/hipe_arm_ra_naive.erl
@@ -24,7 +24,7 @@
-include("hipe_arm.hrl").
-ra(Defun, _Coloring_fp, _Options) -> % -> {Defun, Coloring}
- {NewDefun,_DidSpill} =
- hipe_arm_ra_postconditions:check_and_rewrite2(Defun, [], 'naive'),
- {NewDefun, []}.
+ra(CFG, _Coloring_fp, _Options) -> % -> {CFG, Coloring}
+ {NewCFG,_DidSpill} =
+ hipe_arm_ra_postconditions:check_and_rewrite2(CFG, [], 'naive'),
+ {NewCFG, []}.
diff --git a/lib/hipe/arm/hipe_arm_ra_postconditions.erl b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
index 40978e65f6..04365f29b0 100644
--- a/lib/hipe/arm/hipe_arm_ra_postconditions.erl
+++ b/lib/hipe/arm/hipe_arm_ra_postconditions.erl
@@ -25,17 +25,13 @@
-include("hipe_arm.hrl").
-check_and_rewrite(Defun, Coloring, Allocator) ->
+check_and_rewrite(CFG, Coloring, Allocator) ->
TempMap = hipe_temp_map:cols2tuple(Coloring, hipe_arm_specific),
- check_and_rewrite2(Defun, TempMap, Allocator).
+ check_and_rewrite2(CFG, TempMap, Allocator).
-check_and_rewrite2(Defun, TempMap, Allocator) ->
+check_and_rewrite2(CFG, TempMap, Allocator) ->
Strategy = strategy(Allocator),
- #defun{code=Code0} = Defun,
- {Code1,DidSpill} = do_insns(Code0, TempMap, Strategy, [], false),
- VarRange = {0, hipe_gensym:get_var(arm)},
- {Defun#defun{code=Code1, var_range=VarRange},
- DidSpill}.
+ do_bbs(hipe_arm_cfg:labels(CFG), TempMap, Strategy, CFG, false).
strategy(Allocator) ->
case Allocator of
@@ -44,6 +40,13 @@ strategy(Allocator) ->
'naive' -> 'fixed'
end.
+do_bbs([], _, _, CFG, DidSpill) -> {CFG, DidSpill};
+do_bbs([Lbl|Lbls], TempMap, Strategy, CFG0, DidSpill0) ->
+ Code0 = hipe_bb:code(BB = hipe_arm_cfg:bb(CFG0, Lbl)),
+ {Code, DidSpill} = do_insns(Code0, TempMap, Strategy, [], DidSpill0),
+ CFG = hipe_arm_cfg:bb_add(CFG0, Lbl, hipe_bb:code_update(BB, Code)),
+ do_bbs(Lbls, TempMap, Strategy, CFG, DidSpill).
+
do_insns([I|Insns], TempMap, Strategy, Accum, DidSpill0) ->
{NewIs, DidSpill1} = do_insn(I, TempMap, Strategy),
do_insns(Insns, TempMap, Strategy, lists:reverse(NewIs, Accum), DidSpill0 or DidSpill1);
diff --git a/lib/hipe/regalloc/hipe_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl
index 4e34cb1d99..e04d80f690 100644
--- a/lib/hipe/regalloc/hipe_arm_specific.erl
+++ b/lib/hipe/regalloc/hipe_arm_specific.erl
@@ -53,11 +53,11 @@
-export([defun_to_cfg/1,
check_and_rewrite/2]).
-defun_to_cfg(Defun) ->
- hipe_arm_cfg:init(Defun).
+defun_to_cfg(AlreadyACFG) ->
+ AlreadyACFG.
-check_and_rewrite(Defun, Coloring) ->
- hipe_arm_ra_postconditions:check_and_rewrite(Defun, Coloring, 'normal').
+check_and_rewrite(CFG, Coloring) ->
+ hipe_arm_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal').
reverse_postorder(CFG) ->
hipe_arm_cfg:reverse_postorder(CFG).