aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorMagnus Lång <[email protected]>2016-09-24 09:37:46 +0200
committerMagnus Lång <[email protected]>2017-03-16 20:49:42 +0100
commitcc115ebc67a465233c7740efb42e0bc9584ad352 (patch)
tree766d1f10b40e4a4c145bad262d2bbd372eb3f636 /lib
parente99f1d41bc8a7e035e35fd5aef6f3ea023d7f12e (diff)
downloadotp-cc115ebc67a465233c7740efb42e0bc9584ad352.tar.gz
otp-cc115ebc67a465233c7740efb42e0bc9584ad352.tar.bz2
otp-cc115ebc67a465233c7740efb42e0bc9584ad352.zip
hipe: Add branch prediction accessor ra callbacks
Adds a new register allocator callback Target:branch_preds(Instr, Context) which, for a control flow instruction Instr, returns a list of tuples {Target, Probability} for each label name Target that Instr may branch to. Probability is a float between 0.0 and 1.0 and corresponds to the predicted probability that control flow branches to the corresponding target. The probabilities may sum to at most 1.0 (rounding errors aside). Note that a sum less than 1.0 is valid.
Diffstat (limited to 'lib')
-rw-r--r--lib/hipe/arm/hipe_arm_cfg.erl21
-rw-r--r--lib/hipe/ppc/hipe_ppc_cfg.erl21
-rw-r--r--lib/hipe/regalloc/hipe_amd64_specific_sse2.erl6
-rw-r--r--lib/hipe/regalloc/hipe_arm_specific.erl6
-rw-r--r--lib/hipe/regalloc/hipe_ppc_specific.erl6
-rw-r--r--lib/hipe/regalloc/hipe_ppc_specific_fp.erl6
-rw-r--r--lib/hipe/regalloc/hipe_sparc_specific.erl6
-rw-r--r--lib/hipe/regalloc/hipe_sparc_specific_fp.erl6
-rw-r--r--lib/hipe/regalloc/hipe_x86_specific.erl6
-rw-r--r--lib/hipe/sparc/hipe_sparc_cfg.erl22
-rw-r--r--lib/hipe/x86/hipe_x86_cfg.erl22
11 files changed, 126 insertions, 2 deletions
diff --git a/lib/hipe/arm/hipe_arm_cfg.erl b/lib/hipe/arm/hipe_arm_cfg.erl
index ea6da67317..0bc3df30b9 100644
--- a/lib/hipe/arm/hipe_arm_cfg.erl
+++ b/lib/hipe/arm/hipe_arm_cfg.erl
@@ -24,6 +24,7 @@
-export([params/1, reverse_postorder/1]).
-export([arity/1]). % for linear scan
%%-export([redirect_jmp/3]).
+-export([branch_preds/1]).
%%% these tell cfg.inc what to define (ugly as hell)
-define(BREADTH_ORDER,true). % for linear scan
@@ -75,6 +76,26 @@ branch_successors(Branch) ->
#pseudo_tailcall{} -> []
end.
+branch_preds(Branch) ->
+ case Branch of
+ #pseudo_bc{true_label=TrueLab,false_label=FalseLab,pred=Pred} ->
+ [{FalseLab, 1.0-Pred}, {TrueLab, Pred}];
+ #pseudo_call{contlab=ContLab, sdesc=#arm_sdesc{exnlab=[]}} ->
+ %% A function can still cause an exception, even if we won't catch it
+ [{ContLab, 1.0-hipe_bb_weights:call_exn_pred()}];
+ #pseudo_call{contlab=ContLab, sdesc=#arm_sdesc{exnlab=ExnLab}} ->
+ CallExnPred = hipe_bb_weights:call_exn_pred(),
+ [{ContLab, 1.0-CallExnPred}, {ExnLab, CallExnPred}];
+ #pseudo_switch{labels=Labels} ->
+ Prob = 1.0/length(Labels),
+ [{L, Prob} || L <- Labels];
+ _ ->
+ case branch_successors(Branch) of
+ [] -> [];
+ [Single] -> [{Single, 1.0}]
+ end
+ end.
+
-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
fails_to(_Instr) -> [].
-endif.
diff --git a/lib/hipe/ppc/hipe_ppc_cfg.erl b/lib/hipe/ppc/hipe_ppc_cfg.erl
index 58a4d5c8c3..d44d38f38d 100644
--- a/lib/hipe/ppc/hipe_ppc_cfg.erl
+++ b/lib/hipe/ppc/hipe_ppc_cfg.erl
@@ -22,6 +22,7 @@
-export([postorder/1]).
-export([linearise/1, params/1, reverse_postorder/1]).
-export([redirect_jmp/3, arity/1]).
+-export([branch_preds/1]).
%%% these tell cfg.inc what to define (ugly as hell)
-define(BREADTH_ORDER,true).
@@ -74,6 +75,26 @@ branch_successors(Branch) ->
#pseudo_tailcall{} -> []
end.
+branch_preds(Branch) ->
+ case Branch of
+ #bctr{labels=Labels} ->
+ Prob = 1.0/length(Labels),
+ [{L, Prob} || L <- Labels];
+ #pseudo_bc{true_label=TrueLab,false_label=FalseLab,pred=Pred} ->
+ [{FalseLab, 1.0-Pred}, {TrueLab, Pred}];
+ #pseudo_call{contlab=ContLab, sdesc=#ppc_sdesc{exnlab=[]}} ->
+ %% A function can still cause an exception, even if we won't catch it
+ [{ContLab, 1.0-hipe_bb_weights:call_exn_pred()}];
+ #pseudo_call{contlab=ContLab, sdesc=#ppc_sdesc{exnlab=ExnLab}} ->
+ CallExnPred = hipe_bb_weights:call_exn_pred(),
+ [{ContLab, 1.0-CallExnPred}, {ExnLab, CallExnPred}];
+ _ ->
+ case branch_successors(Branch) of
+ [] -> [];
+ [Single] -> [{Single, 1.0}]
+ end
+ end.
+
-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
fails_to(_Instr) -> [].
-endif.
diff --git a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
index 341233e851..8914e7cac3 100644
--- a/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
+++ b/lib/hipe/regalloc/hipe_amd64_specific_sse2.erl
@@ -60,6 +60,9 @@
update_bb/4,
subst_temps/3]).
+%% callbacks for hipe_bb_weights
+-export([branch_preds/2]).
+
%%----------------------------------------------------------------------------
-include("../flow/cfg.hrl").
@@ -156,6 +159,9 @@ bb(CFG, L, _) ->
update_bb(CFG,L,BB,_) ->
hipe_x86_cfg:bb_add(CFG,L,BB).
+branch_preds(Instr,_) ->
+ hipe_x86_cfg:branch_preds(Instr).
+
%% AMD64 stuff
def_use(Instruction, _) ->
diff --git a/lib/hipe/regalloc/hipe_arm_specific.erl b/lib/hipe/regalloc/hipe_arm_specific.erl
index 224837a34a..517ad83982 100644
--- a/lib/hipe/regalloc/hipe_arm_specific.erl
+++ b/lib/hipe/regalloc/hipe_arm_specific.erl
@@ -56,6 +56,9 @@
update_bb/4,
subst_temps/3]).
+%% callbacks for hipe_bb_weights, hipe_range_split
+-export([branch_preds/2]).
+
check_and_rewrite(CFG, Coloring, no_context) ->
hipe_arm_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal').
@@ -119,6 +122,9 @@ bb(CFG,L,_) ->
update_bb(CFG,L,BB,_) ->
hipe_arm_cfg:bb_add(CFG,L,BB).
+branch_preds(Branch,_) ->
+ hipe_arm_cfg:branch_preds(Branch).
+
%% ARM stuff
def_use(Instruction, Ctx) ->
diff --git a/lib/hipe/regalloc/hipe_ppc_specific.erl b/lib/hipe/regalloc/hipe_ppc_specific.erl
index bc4bd1972e..50ab0f04cf 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific.erl
@@ -56,6 +56,9 @@
update_bb/4,
subst_temps/3]).
+%% callbacks for hipe_bb_weights
+-export([branch_preds/2]).
+
check_and_rewrite(CFG, Coloring, _) ->
hipe_ppc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal').
@@ -119,6 +122,9 @@ bb(CFG,L,_) ->
update_bb(CFG,L,BB,_) ->
hipe_ppc_cfg:bb_add(CFG,L,BB).
+branch_preds(Instr,_) ->
+ hipe_ppc_cfg:branch_preds(Instr).
+
%% PowerPC stuff
def_use(Instruction, Ctx) ->
diff --git a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
index 3aab14f061..5a4f63fc78 100644
--- a/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_ppc_specific_fp.erl
@@ -56,6 +56,9 @@
update_bb/4,
subst_temps/3]).
+%% callbacks for hipe_bb_weights
+-export([branch_preds/2]).
+
check_and_rewrite(CFG, Coloring, _) ->
hipe_ppc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring).
@@ -112,6 +115,9 @@ bb(CFG, L, _) ->
update_bb(CFG,L,BB,_) ->
hipe_ppc_cfg:bb_add(CFG,L,BB).
+branch_preds(Instr,_) ->
+ hipe_ppc_cfg:branch_preds(Instr).
+
%% PowerPC stuff
def_use(I, Ctx) ->
diff --git a/lib/hipe/regalloc/hipe_sparc_specific.erl b/lib/hipe/regalloc/hipe_sparc_specific.erl
index 12642709b9..9eb57dafd2 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific.erl
@@ -56,6 +56,9 @@
update_bb/4,
subst_temps/3]).
+%% callbacks for hipe_bb_weights, hipe_range_split
+-export([branch_preds/2]).
+
check_and_rewrite(CFG, Coloring, no_context) ->
hipe_sparc_ra_postconditions:check_and_rewrite(CFG, Coloring, 'normal').
@@ -119,6 +122,9 @@ bb(CFG,L,_) ->
update_bb(CFG,L,BB,_) ->
hipe_sparc_cfg:bb_add(CFG,L,BB).
+branch_preds(Branch,_) ->
+ hipe_sparc_cfg:branch_preds(Branch).
+
%% SPARC stuff
def_use(Instruction, Ctx) ->
diff --git a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
index ba4849d2d5..9993af81c2 100644
--- a/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
+++ b/lib/hipe/regalloc/hipe_sparc_specific_fp.erl
@@ -56,6 +56,9 @@
update_bb/4,
subst_temps/3]).
+%% callbacks for hipe_bb_weights, hipe_range_split
+-export([branch_preds/2]).
+
check_and_rewrite(CFG, Coloring, no_context) ->
hipe_sparc_ra_postconditions_fp:check_and_rewrite(CFG, Coloring).
@@ -112,6 +115,9 @@ bb(CFG, L, _) ->
update_bb(CFG,L,BB,_) ->
hipe_sparc_cfg:bb_add(CFG,L,BB).
+branch_preds(Branch,_) ->
+ hipe_sparc_cfg:branch_preds(Branch).
+
%% SPARC stuff
def_use(I, Ctx) ->
diff --git a/lib/hipe/regalloc/hipe_x86_specific.erl b/lib/hipe/regalloc/hipe_x86_specific.erl
index 0d9d7b751e..f21384d377 100644
--- a/lib/hipe/regalloc/hipe_x86_specific.erl
+++ b/lib/hipe/regalloc/hipe_x86_specific.erl
@@ -73,6 +73,9 @@
update_bb/4,
subst_temps/3]).
+%% callbacks for hipe_bb_weights
+-export([branch_preds/2]).
+
check_and_rewrite(CFG, Coloring, _) ->
?HIPE_X86_RA_POSTCONDITIONS:check_and_rewrite(CFG, Coloring, 'normal').
@@ -160,6 +163,9 @@ bb(CFG,L,_) ->
update_bb(CFG,L,BB,_) ->
hipe_x86_cfg:bb_add(CFG,L,BB).
+branch_preds(Instr,_) ->
+ hipe_x86_cfg:branch_preds(Instr).
+
%% X86 stuff
def_use(Instruction,_) ->
diff --git a/lib/hipe/sparc/hipe_sparc_cfg.erl b/lib/hipe/sparc/hipe_sparc_cfg.erl
index b31c90a03a..45c8e887b5 100644
--- a/lib/hipe/sparc/hipe_sparc_cfg.erl
+++ b/lib/hipe/sparc/hipe_sparc_cfg.erl
@@ -23,7 +23,7 @@
-export([linearise/1]).
-export([params/1]).
-export([arity/1]). % for linear scan
--export([redirect_jmp/3]).
+-export([redirect_jmp/3, branch_preds/1]).
-define(SPARC_CFG, true). % needed for cfg.inc
@@ -78,6 +78,26 @@ branch_successors(Branch) ->
#pseudo_tailcall{} -> []
end.
+branch_preds(Branch) ->
+ case Branch of
+ #jmp{labels=Labels} ->
+ Prob = 1.0/length(Labels),
+ [{L, Prob} || L <- Labels];
+ #pseudo_bp{true_label=TrueLab,false_label=FalseLab,pred=Pred} ->
+ [{FalseLab, 1.0-Pred}, {TrueLab, Pred}];
+ #pseudo_call{contlab=ContLab, sdesc=#sparc_sdesc{exnlab=[]}} ->
+ %% A function can still cause an exception, even if we won't catch it
+ [{ContLab, 1.0-hipe_bb_weights:call_exn_pred()}];
+ #pseudo_call{contlab=ContLab, sdesc=#sparc_sdesc{exnlab=ExnLab}} ->
+ CallExnPred = hipe_bb_weights:call_exn_pred(),
+ [{ContLab, 1.0-CallExnPred}, {ExnLab, CallExnPred}];
+ _ ->
+ case branch_successors(Branch) of
+ [] -> [];
+ [Single] -> [{Single, 1.0}]
+ end
+ end.
+
-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
fails_to(_Instr) -> [].
-endif.
diff --git a/lib/hipe/x86/hipe_x86_cfg.erl b/lib/hipe/x86/hipe_x86_cfg.erl
index a4544e1086..0a3c0fc9d6 100644
--- a/lib/hipe/x86/hipe_x86_cfg.erl
+++ b/lib/hipe/x86/hipe_x86_cfg.erl
@@ -19,7 +19,7 @@
succ/2, pred/2,
bb/2, bb_add/3, map_bbs/2, fold_bbs/3]).
-export([postorder/1, reverse_postorder/1]).
--export([linearise/1, params/1, arity/1, redirect_jmp/3]).
+-export([linearise/1, params/1, arity/1, redirect_jmp/3, branch_preds/1]).
%%% these tell cfg.inc what to define (ugly as hell)
-define(PRED_NEEDED,true).
@@ -72,6 +72,26 @@ branch_successors(Branch) ->
#ret{} -> []
end.
+branch_preds(Branch) ->
+ case Branch of
+ #jmp_switch{labels=Labels} ->
+ Prob = 1.0/length(Labels),
+ [{L, Prob} || L <- Labels];
+ #pseudo_call{contlab=ContLab, sdesc=#x86_sdesc{exnlab=[]}} ->
+ %% A function can still cause an exception, even if we won't catch it
+ [{ContLab, 1.0-hipe_bb_weights:call_exn_pred()}];
+ #pseudo_call{contlab=ContLab, sdesc=#x86_sdesc{exnlab=ExnLab}} ->
+ CallExnPred = hipe_bb_weights:call_exn_pred(),
+ [{ContLab, 1.0-CallExnPred}, {ExnLab, CallExnPred}];
+ #pseudo_jcc{true_label=TrueLab,false_label=FalseLab,pred=Pred} ->
+ [{FalseLab, 1.0-Pred}, {TrueLab, Pred}];
+ _ ->
+ case branch_successors(Branch) of
+ [] -> [];
+ [Single] -> [{Single, 1.0}]
+ end
+ end.
+
-ifdef(REMOVE_TRIVIAL_BBS_NEEDED).
fails_to(_Instr) -> [].
-endif.