path: root/lib/hipe/opt/hipe_bb_weights.erl

%% -*- erlang-indent-level: 2 -*-
%%
%% 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.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%@doc
%%	                BASIC BLOCK WEIGHTING
%%
%% Computes basic block weights by using branch probabilities as weights in a
%% linear equation system, that is then solved using Gauss-Jordan Elimination.
%%
%% The equation system representation is intentionally sparse, since most blocks
%% have at most two successors.
-module(hipe_bb_weights).
-export([compute/3, compute_fast/3, weight/2, call_exn_pred/0]).
-export_type([bb_weights/0]).

-compile(inline).

%%-define(DO_ASSERT,1).
%%-define(DEBUG,1).
-include("../main/hipe.hrl").

%% If the equation system is large, it might take too long to solve it exactly.
%% Thus, if there are more than ?HEUR_MAX_SOLVE labels, we use the iterative
%% approximation.
-define(HEUR_MAX_SOLVE, 10000).

-opaque bb_weights() :: #{label() => float()}.

-type cfg() :: any().
-type target_module() :: module().
-type target_context() :: any().
-type target() :: {target_module(), target_context()}.

-type label()            :: integer().
-type var()              :: label().
-type assignment()       :: {var(), float()}.
-type eq_assoc()         :: [{var(), key()}].
-type solution()         :: [assignment()].

%% Constant. Predicted probability of a call resulting in an exception.
-spec call_exn_pred() -> float().
call_exn_pred() -> 0.01.

-spec compute(cfg(), target_module(), target_context()) -> bb_weights().
compute(CFG, TgtMod, TgtCtx) ->
  Target = {TgtMod, TgtCtx},
  Labels = labels(CFG, Target),
  if length(Labels) > ?HEUR_MAX_SOLVE ->
      ?debug_msg("~w: Too many labels (~w), approximating.~n",
		 [?MODULE, length(Labels)]),
      compute_fast(CFG, TgtMod, TgtCtx);
     true ->
      {EqSys, EqAssoc} = build_eq_system(CFG, Labels, Target),
      case solve(EqSys, EqAssoc) of
	{ok, Solution} ->
	  maps:from_list(Solution)
      end
  end.

-spec build_eq_system(cfg(), [label()], target()) -> {eq_system(), eq_assoc()}.
build_eq_system(CFG, Labels, Target) ->
  StartLb = hipe_gen_cfg:start_label(CFG),
  EQS0 = eqs_new(),
  {EQS1, Assoc} = build_eq_system(Labels, CFG, Target, [], EQS0),
  {StartLb, StartKey} = lists:keyfind(StartLb, 1, Assoc),
  StartRow0 = eqs_get(StartKey, EQS1),
  StartRow = row_set_const(-1.0, StartRow0), % -1.0 since StartLb coef is -1.0
  EQS = eqs_put(StartKey, StartRow, EQS1),
  {EQS, Assoc}.

build_eq_system([], _CFG, _Target, Map, EQS) -> {EQS, lists:reverse(Map)};
build_eq_system([L|Ls], CFG, Target, Map, EQS0) ->
  PredProb = pred_prob(L, CFG, Target),
  {Key, EQS} = eqs_insert(row_new([{L, -1.0}|PredProb], 0.0), EQS0),
  build_eq_system(Ls, CFG, Target, [{L, Key}|Map], EQS).

pred_prob(L, CFG, Target) ->
  [begin
     BB = bb(CFG, Pred, Target),
     Ps = branch_preds(hipe_bb:last(BB), Target),
     ?ASSERT(length(lists:ukeysort(1, Ps))
	     =:= length(hipe_gen_cfg:succ(CFG, Pred))),
     case lists:keyfind(L, 1, Ps) of
       {L, Prob} when is_float(Prob) -> {Pred, Prob}
     end
   end || Pred <- hipe_gen_cfg:pred(CFG, L)].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-spec triangelise(eq_system(), eq_assoc()) -> {eq_system(), eq_assoc()}.
triangelise(EQS, VKs) ->
  triangelise_1(mk_triix(EQS, VKs), []).

triangelise_1(TIX0, Acc) ->
  case triix_is_empty(TIX0) of
    true -> {triix_eqs(TIX0), lists:reverse(Acc)};
    false ->
      {V,Key,TIX1} = triix_pop_smallest(TIX0),
      Row0 = triix_get(Key, TIX1),
      case row_get(V, Row0) of
	Coef when Coef > -0.0001, Coef < 0.0001 ->
	  throw(error);
	_ ->
	  Row = row_normalise(V, Row0),
	  TIX2 = triix_put(Key, Row, TIX1),
	  TIX = eliminate_triix(V, Key, Row, TIX2),
	  triangelise_1(TIX, [{V,Key}|Acc])
      end
  end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Triangelisation maintains its own index, outside of eqs. This index is
%% essentially a BST (used as a heap) of all equations by size, with {Key,Var}
%% as the values and only containing a subset of all the keys in the whole
%% equation system. The key operation is triix_pop_smallest/1, which pops a
%% {Key,Var} from the heap corresponding to one of the smallest equations. This
%% is critical in order to prevent the equations from growing during
%% triangelisation, which would make the algorithm O(n^2) in the common case.
-type tri_eq_system() :: {eq_system(),
			  gb_trees:tree(non_neg_integer(),
					gb_trees:tree(key(), var()))}.

triix_eqs({EQS, _}) -> EQS.
triix_get(Key, {EQS, _}) -> eqs_get(Key, EQS).
triix_is_empty({_, Tree}) -> gb_trees:is_empty(Tree).
triix_lookup(V, {EQS, _}) -> eqs_lookup(V, EQS).

mk_triix(EQS, VKs) ->
  {EQS,
   lists:foldl(fun({V,Key}, Tree) ->
		   Size = row_size(eqs_get(Key, EQS)),
		   sitree_insert(Size, Key, V, Tree)
	       end, gb_trees:empty(), VKs)}.

sitree_insert(Size, Key, V, SiTree) ->
  SubTree1 =
    case gb_trees:lookup(Size, SiTree) of
      none -> gb_trees:empty();
      {value, SubTree0} -> SubTree0
    end,
  SubTree = gb_trees:insert(Key, V, SubTree1),
  gb_trees:enter(Size, SubTree, SiTree).

sitree_update_subtree(Size, SubTree, SiTree) ->
  case gb_trees:is_empty(SubTree) of
    true -> gb_trees:delete(Size, SiTree);
    false -> gb_trees:update(Size, SubTree, SiTree)
  end.

triix_put(Key, Row, {EQS, Tree0}) ->
  OldSize = row_size(eqs_get(Key, EQS)),
  case row_size(Row) of
    OldSize -> {eqs_put(Key, Row, EQS), Tree0};
    Size ->
      Tree =
	case gb_trees:lookup(OldSize, Tree0) of
	  none -> Tree0;
	  {value, SubTree0} ->
	    case gb_trees:lookup(Key, SubTree0) of
	      none -> Tree0;
	      {value, V} ->
		SubTree = gb_trees:delete(Key, SubTree0),
		Tree1 = sitree_update_subtree(OldSize, SubTree, Tree0),
		sitree_insert(Size, Key, V, Tree1)
	    end
	end,
      {eqs_put(Key, Row, EQS), Tree}
  end.

triix_pop_smallest({EQS, Tree}) ->
  {Size, SubTree0} = gb_trees:smallest(Tree),
  {Key, V, SubTree} = gb_trees:take_smallest(SubTree0),
  {V, Key, {EQS, sitree_update_subtree(Size, SubTree, Tree)}}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

row_normalise(Var, Row) ->
  %% Normalise v's coef to 1.0
  %% row_set_coef ensures the coef is exactly 1.0 (no rounding errors)
  row_set_coef(Var, 1.0, row_scale(Row, 1.0/row_get(Var, Row))).

%% Precondition: Row must be normalised; i.e. Vars coef must be 1.0 (mod
%% rounding errors)
-spec eliminate(var(), key(), row(), eq_system()) -> eq_system().
eliminate(Var, Key, Row, TIX0) ->
  eliminate_abstr(Var, Key, Row, TIX0,
		  fun eqs_get/2, fun eqs_lookup/2, fun eqs_put/3).

-spec eliminate_triix(var(), key(), row(), tri_eq_system()) -> tri_eq_system().
eliminate_triix(Var, Key, Row, TIX0) ->
  eliminate_abstr(Var, Key, Row, TIX0,
		  fun triix_get/2, fun triix_lookup/2, fun triix_put/3).

%% The same function implemented for two data types, eqs and triix.
-compile({inline, eliminate_abstr/7}).
-spec eliminate_abstr(var(), key(), row(), ADT, fun((key(), ADT) -> row()),
		      fun((var(), ADT) -> [key()]),
		      fun((key(), row(), ADT) -> ADT)) -> ADT.
eliminate_abstr(Var, Key, Row, ADT0, GetFun, LookupFun, PutFun) ->
  ?ASSERT(1.0 =:= row_get(Var, Row)),
  ADT =
    lists:foldl(fun(RK, ADT1) when RK =:= Key -> ADT1;
		   (RK, ADT1) ->
		    R = GetFun(RK, ADT1),
		    PutFun(RK, row_addmul(R, Row, -row_get(Var, R)), ADT1)
		end, ADT0, LookupFun(Var, ADT0)),
  [Key] = LookupFun(Var, ADT),
  ADT.

-spec solve(eq_system(), eq_assoc()) -> error | {ok, solution()}.
solve(EQS0, EqAssoc0) ->
  try triangelise(EQS0, EqAssoc0)
  of {EQS1, EqAssoc} ->
      {ok, solve_1(EqAssoc, maps:from_list(EqAssoc), EQS1, [])}
  catch error -> error
  end.

solve_1([], _VarEqs, _EQS, Acc) -> Acc;
solve_1([{V,K}|Ps], VarEqs, EQS0, Acc0) ->
  Row0 = eqs_get(K, EQS0),
  VarsToKill = [Var || {Var, _} <- row_coefs(Row0), Var =/= V],
  Row1 = kill_vars(VarsToKill, VarEqs, EQS0, Row0),
  [{V,_}] = row_coefs(Row1), % assertion
  Row = row_normalise(V, Row1),
  [{V,1.0}] = row_coefs(Row), % assertion
  EQS = eliminate(V, K, Row, EQS0),
  [K] = eqs_lookup(V, EQS),
  solve_1(Ps, VarEqs, eqs_remove(K, EQS), [{V, row_const(Row)}|Acc0]).

kill_vars([], _VarEqs, _EQS, Row) -> Row;
kill_vars([V|Vs], VarEqs, EQS, Row0) ->
  VRow0 = eqs_get(maps:get(V, VarEqs), EQS),
  VRow = row_normalise(V, VRow0),
  ?ASSERT(1.0 =:= row_get(V, VRow)),
  Row = row_addmul(Row0, VRow, -row_get(V, Row0)),
  ?ASSERT(0.0 =:= row_get(V, Row)), % V has been killed
  kill_vars(Vs, VarEqs, EQS, Row).

-spec weight(label(), bb_weights()) -> float().
weight(Lbl, Weights) ->
  maps:get(Lbl, Weights).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Row datatype
%% Invariant: No 0.0 coefficiets!
-spec row_empty() -> row().
row_empty() -> {orddict:new(), 0.0}.

-spec row_new([{var(), float()}], float()) -> row().
row_new(Coefs, Const) when is_float(Const) ->
  row_ensure_invar({row_squash_multiples(lists:keysort(1, Coefs)), Const}).

row_squash_multiples([{K, C1},{K, C2}|Ps]) ->
  row_squash_multiples([{K,C1+C2}|Ps]);
row_squash_multiples([P|Ps]) -> [P|row_squash_multiples(Ps)];
row_squash_multiples([]) -> [].

row_ensure_invar({Coef, Const}) ->
  {orddict:filter(fun(_, 0.0) -> false; (_, F) when is_float(F) -> true end,
		  Coef), Const}.

row_const({_, Const}) -> Const.
row_coefs({Coefs, _}) -> orddict:to_list(Coefs).
row_size({Coefs, _}) -> orddict:size(Coefs).

row_get(Var, {Coefs, _}) ->
  case lists:keyfind(Var, 1, Coefs) of
    false -> 0.0;
    {_, Coef} -> Coef
  end.

row_set_coef(Var, 0.0, {Coefs, Const}) ->
  {orddict:erase(Var, Coefs), Const};
row_set_coef(Var, Coef, {Coefs, Const}) ->
  {orddict:store(Var, Coef, Coefs), Const}.

row_set_const(Const, {Coefs, _}) -> {Coefs, Const}.

%% Lhs + Rhs*Factor
-spec row_addmul(row(), row(), float()) -> row().
row_addmul({LhsCoefs, LhsConst}, {RhsCoefs, RhsConst}, Factor)
  when is_float(Factor) ->
  Coefs = row_addmul_coefs(LhsCoefs, RhsCoefs, Factor),
  Const = LhsConst + RhsConst * Factor,
  {Coefs, Const}.

row_addmul_coefs(Ls, [], Factor) when is_float(Factor) -> Ls;
row_addmul_coefs([], Rs, Factor) when is_float(Factor) ->
  row_scale_coefs(Rs, Factor);
row_addmul_coefs([L={LV, _}|Ls], Rs=[{RV,_}|_], Factor)
  when LV < RV, is_float(Factor) ->
  [L|row_addmul_coefs(Ls, Rs, Factor)];
row_addmul_coefs(Ls=[{LV, _}|_], [{RV, RC}|Rs], Factor)
  when LV > RV, is_float(RC), is_float(Factor) ->
  [{RV, RC*Factor}|row_addmul_coefs(Ls, Rs, Factor)];
row_addmul_coefs([{V, LC}|Ls], [{V, RC}|Rs], Factor)
  when is_float(LC), is_float(RC), is_float(Factor) ->
  case LC + RC * Factor of
    0.0 ->      row_addmul_coefs(Ls, Rs, Factor);
    C -> [{V,C}|row_addmul_coefs(Ls, Rs, Factor)]
  end.

row_scale(_, 0.0) -> row_empty();
row_scale({RowCoefs, RowConst}, Factor) when is_float(Factor) ->
  {row_scale_coefs(RowCoefs, Factor), RowConst * Factor}.

row_scale_coefs([{V,C}|Cs], Factor) when is_float(Factor), is_float(C) ->
  [{V,C*Factor}|row_scale_coefs(Cs, Factor)];
row_scale_coefs([], Factor) when is_float(Factor) ->
  [].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Equation system ADT
%%
%% Stores a linear equation system, allowing for efficient updates and efficient
%% queries for all equations mentioning a variable.
%%
%% It is sort of like a "database" table of {Primary, Terms, Const} indexed both
%% on Primary as well as the vars (map keys) in Terms.
-type row()       :: {Terms :: orddict:orddict(var(), float()),
		      Const :: float()}.
-type key()       :: non_neg_integer().
-type rev_index() :: #{var() => ordsets:ordset(key())}.
-record(eq_system, {
	  rows = #{}              :: #{key() => row()},
	  revidx = revidx_empty() :: rev_index(),
	  next_key = 0            :: key()
	 }).
-type eq_system() :: #eq_system{}.

eqs_new() -> #eq_system{}.

-spec eqs_insert(row(), eq_system()) -> {key(), eq_system()}.
eqs_insert(Row, EQS=#eq_system{next_key=NextKey0}) ->
  Key = NextKey0,
  NextKey = NextKey0 + 1,
  {Key, eqs_insert(Key, Row, EQS#eq_system{next_key=NextKey})}.

eqs_insert(Key, Row, EQS=#eq_system{rows=Rows, revidx=RevIdx0}) ->
  RevIdx = revidx_add(Key, Row, RevIdx0),
  EQS#eq_system{rows=Rows#{Key => Row}, revidx=RevIdx}.

eqs_put(Key, Row, EQS0) ->
  eqs_insert(Key, Row, eqs_remove(Key, EQS0)).

eqs_remove(Key, EQS=#eq_system{rows=Rows, revidx=RevIdx0}) ->
  OldRow = maps:get(Key, Rows),
  RevIdx = revidx_remove(Key, OldRow, RevIdx0),
  EQS#eq_system{rows = maps:remove(Key, Rows), revidx=RevIdx}.

-spec eqs_get(key(), eq_system()) -> row().
eqs_get(Key, #eq_system{rows=Rows}) -> maps:get(Key, Rows).

%% Keys of all equations containing a nonzero coefficient for Var
-spec eqs_lookup(var(), eq_system()) -> ordsets:ordset(key()).
eqs_lookup(Var, #eq_system{revidx=RevIdx}) -> maps:get(Var, RevIdx).

%% eqs_rows(#eq_system{rows=Rows}) -> maps:to_list(Rows).

%% eqs_print(EQS) ->
%%   lists:foreach(fun({_, Row}) ->
%% 		    row_print(Row)
%% 		end, lists:sort(eqs_rows(EQS))).

%% row_print(Row) ->
%%   CoefStrs = [io_lib:format("~wl~w", [Coef, Var])
%% 	      || {Var, Coef} <- row_coefs(Row)],
%%   CoefStr = lists:join(" + ", CoefStrs),
%%   io:format("~w = ~s~n", [row_const(Row), CoefStr]).

revidx_empty() -> #{}.

-spec revidx_add(key(), row(), rev_index()) -> rev_index().
revidx_add(Key, Row, RevIdx0) ->
  orddict:fold(fun(Var, _Coef, RevIdx1) ->
		?ASSERT(_Coef /= 0.0),
		RevIdx1#{Var => ordsets:add_element(
				  Key, maps:get(Var, RevIdx1, ordsets:new()))}
	    end, RevIdx0, row_coefs(Row)).

-spec revidx_remove(key(), row(), rev_index()) -> rev_index().
revidx_remove(Key, {Coefs, _}, RevIdx0) ->
  orddict:fold(fun(Var, _Coef, RevIdx1) ->
		case RevIdx1 of
		  #{Var := Keys0} ->
		    case ordsets:del_element(Key, Keys0) of
		      [] -> maps:remove(Var, RevIdx1);
		      Keys -> RevIdx1#{Var := Keys}
		    end
		end
	    end, RevIdx0, Coefs).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-define(FAST_ITERATIONS, 5).

%% @doc Computes a rough approximation of BB weights. The approximation is
%% particularly poor (converges slowly) for recursive functions and loops.
-spec compute_fast(cfg(), target_module(), target_context()) -> bb_weights().
compute_fast(CFG, TgtMod, TgtCtx) ->
  Target = {TgtMod, TgtCtx},
  StartLb = hipe_gen_cfg:start_label(CFG),
  RPO = reverse_postorder(CFG, Target),
  PredProbs = [{L, pred_prob(L, CFG, Target)} || L <- RPO, L =/= StartLb],
  Probs0 = (maps:from_list([{L, 0.0} || L <- RPO]))#{StartLb := 1.0},
  fast_iterate(?FAST_ITERATIONS, PredProbs, Probs0).

fast_iterate(0, _Pred, Probs) -> Probs;
fast_iterate(Iters, Pred, Probs0) ->
  fast_iterate(Iters-1, Pred,
	       fast_one(Pred, Probs0)).

fast_one([{L, Pred}|Ls], Probs0) ->
  Weight = fast_sum(Pred, Probs0, 0.0),
  Probs = Probs0#{L => Weight},
  fast_one(Ls, Probs);
fast_one([], Probs) ->
  Probs.

fast_sum([{P,EWt}|Pred], Probs, Acc) when is_float(EWt), is_float(Acc) ->
  case Probs of
    #{P := PWt} when is_float(PWt) ->
      fast_sum(Pred, Probs, Acc + PWt * EWt)
  end;
fast_sum([], _Probs, Acc) when is_float(Acc) ->
  Acc.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Target module interface functions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-define(TGT_IFACE_0(N), N(         {M,C}) -> M:N(         C)).
-define(TGT_IFACE_1(N), N(A1,      {M,C}) -> M:N(A1,      C)).
-define(TGT_IFACE_2(N), N(A1,A2,   {M,C}) -> M:N(A1,A2,   C)).
-define(TGT_IFACE_3(N), N(A1,A2,A3,{M,C}) -> M:N(A1,A2,A3,C)).

?TGT_IFACE_2(bb).
?TGT_IFACE_1(branch_preds).
?TGT_IFACE_1(labels).
?TGT_IFACE_1(reverse_postorder).