## guess-machcode-loop-probabilities-g.pkg
#
# See also:
#
# src/lib/compiler/back/low/main/nextcode/guess-nextcode-branch-probabilities.pkg# Compiled by:
# src/lib/compiler/back/low/lib/lowhalf.lib# I'd guess the "wu-larus paper" below is:
#
# Statis Branch Frequency and Program Profile Analysis
# Youfeng Wu + James R Larus
# http://www.cs.wisc.edu/techreports/1994/TR1248.pdf
#
# or a close relative thereof. The "Ball-Larus" is presumably
# that mentioned in src/lib/compiler/back/low/doc/latex/lowhalf.bib
#
# Branch Prediction for Free
# T.~Ball and J.~Larus"
# Proceedings of the SIGPLAN`93 Conference on Programming Language Design and Implementation
# June 1993
# http://research.microsoft.com/en-us/um/people/tball/papers/pldi93.pdf
#
# -- 2011-08-15 CrT
#
# "Given a machcode_controlflow_graph that
# may have some existing edge probabilities
# (represented as BRANCHPROB annotations)
# add probabilities based on the loop package
# using the heuristics from Ball-Larus and Wu-Larus."
#
# TODO:
# generalize to switch edges
# Loop Header Heuristic XXX BUGGO FIXME
### "Go not to the Elves for counsel,
### for they will say both yes and no."
###
### -- J. R. R. Tolkien
stipulate
package odg = oop_digraph; # oop_digraph is from src/lib/graph/oop-digraph.pkg package dom
=
dominator_tree_g ( # dominator_tree_g is from src/lib/graph/dominator-tree-g.pkg #
digraph_by_adjacency_list # digraph_by_adjacency_list is from src/lib/graph/digraph-by-adjacency-list.pkg );
package lp
=
loop_structure_g (
#
package meg = digraph_by_adjacency_list; # digraph_by_adjacency_list is from src/lib/graph/digraph-by-adjacency-list.pkg package dom = dom;
);
package an = note; # note is from src/lib/src/note.pkg package prb = probability; # probability is from src/lib/compiler/back/low/library/probability.pkgherein
# This generic is invoked (only) from:
#
# src/lib/compiler/back/low/main/main/backend-lowhalf-g.pkg #
generic package guess_machcode_loop_probabilities_g (
# ===================================
#
package mcg: Machcode_Controlflow_Graph; # Machcode_Controlflow_Graph is from src/lib/compiler/back/low/mcg/machcode-controlflow-graph.api )
: (weak) api {
#
package mcg: Machcode_Controlflow_Graph; # Machcode_Controlflow_Graph is from src/lib/compiler/back/low/mcg/machcode-controlflow-graph.api #
guess_machcode_loop_probabilities
:
mcg::Machcode_Controlflow_Graph
->
Void;
}
{
# Export to client packages:
#
package mcg = mcg; # "mcg" == "machcode_controlflow_graph".
# Flags
disable_loop_probability_estimation
=
lowhalf_control::make_bool (
"disable_loop_probability_estimation",
"TRUE to disable loop probability estimation"
);
dump_machcode_controlflow_graph_after_loop_probability_estimation
=
lowhalf_control::make_bool (
"dump_machcode_controlflow_graph_after_loop_probability_estimation",
"TRUE to dump control flow graph after loop probability estimatimation"
);
dump_strm
=
lowhalf_control::debug_stream;
stipulate
package a = lowhalf_notes; # lowhalf_notes is from src/lib/compiler/back/low/code/lowhalf-notes.pkg #
a::branch_probability -> { get, set, ... };
herein
fun get_edge_prob ( _, _, mcg::EDGE_INFO { notes, ... } ) = get *notes;
fun set_edge_prob ((_, _, mcg::EDGE_INFO { notes, ... } ), p) = notes := set (p, *notes);
end;
# probabilities
prob_loop_branch_heuristic = prb::percent 88; # Loob Branch Heuristic
prob_loop_exit_heuristic = prb::percent 80; # Loop Exit Heuristic
prob50_50 = 50;
# Compute loop package information
#
fun compute_loop_structure mcg
=
{ dom_tree = dom::make_dominator mcg;
dominates = dom::dominates dom_tree;
my odg::DIGRAPH { has_node, forall_nodes, ... }
=
lp::loop_structure dom_tree;
{ is_loop_header => has_node,
forall_loops => forall_nodes
};
};
fun same_edge ( (_, _, mcg::EDGE_INFO { notes => notes1, ... } ),
(_, _, mcg::EDGE_INFO { notes => notes2, ... } )
)
=
notes1 == notes2;
# Add loop probabilities:
#
fun do_estimate (mcg as odg::DIGRAPH { out_edges, ... } )
=
{
my { is_loop_header, forall_loops }
=
compute_loop_structure mcg;
fun compute_probs (true_e, false_e, taken_prob)
=
{
my { t, f }
=
case (get_edge_prob true_e, get_edge_prob false_e)
#
(NULL, NULL)
=>
{ t=>taken_prob, f=>prb::(-) (prb::always, taken_prob) };
(THE p, _)
=>
prb::combine_prob2 { true_prob=>p, taken_prob };
(_, THE p)
=>
prb::combine_prob2
{
true_prob=>prb::(-) (prb::always, p),
taken_prob
};
esac;
set_edge_prob (true_e, t);
set_edge_prob (false_e, f);
};
fun do_loop (hdr_id, lp::LOOP { backedges, exits, ... } )
=
{
# Apply the Loop Branch Heuristic to a back edge:
#
fun do_back_edge (e as (src, _, _))
=
case (out_edges src)
#
[e1, e2]
=>
same_edge (e, e1)
?? compute_probs (e1, e2, prob_loop_branch_heuristic)
:: compute_probs (e2, e1, prob_loop_branch_heuristic);
_ => ();
esac;
# Apply the Loop Exit Heuristic to an exit edges;
# note that the probability is that the loop will NOT be exited.
#
fun do_exit_edge (e as (src, _, _))
=
case (out_edges src)
#
[e1, e2]
=>
if (same_edge (e, e1))
if (is_loop_header (#2 e2)) ();
# e1 is exit edge, so e2 is taken branch
else compute_probs (e2, e1, prob_loop_exit_heuristic);
fi;
elif (is_loop_header (#2 e1))
();
# e2 is exit edge, so e1 is taken branch
else
compute_probs (e1, e2, prob_loop_exit_heuristic);
fi;
_ => ();
esac;
list::apply do_back_edge backedges;
list::apply do_exit_edge exits;
};
forall_loops do_loop;
};
fun guess_machcode_loop_probabilities machcode_controlflow_graph
=
if (not *disable_loop_probability_estimation)
#
do_estimate machcode_controlflow_graph;
if *dump_machcode_controlflow_graph_after_loop_probability_estimation
#
mcg::dump (
*lowhalf_control::debug_stream,
"after loop probability estimates",
machcode_controlflow_graph
);
fi;
fi;
};
end;
## COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.