%% -*- 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.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% ============================================================================
%% Filename : hipe_rtl_ssa_const_prop.erl
%% Authors : Bjorn Bergman, Bjarni Juliusson
%% Purpose : Perform sparse conditional constant propagation on RTL.
%% Notes : Works on an SSA-converted control-flow graph.
%%
%% History : * 2004-03-14: Blatantly stolen from Icode (code by
%% Daniel Luna and Erik Andersson) and query-replaced for RTL.
%% * 2004-04-30: Added in the repository.
%% ============================================================================
%%
%% Exports: propagate/1.
%%
%% ============================================================================
%%
%% Some things to note:
%%
%% 1. All precoloured registers are assumed to contain bottom. We can not
%% do anything with them since they are not in SSA-form. This might be
%% possible to resolve in some way, but we decided to not go there.
%%
%% 2. const_labels are assumed to be bottom, we can not find the address
%% in any nice way (that I know of, maybe someone can help ?). I
%% suppose they don't get a value until linking (or some step that
%% resembles it). They are only affecting bignums and floats (at least
%% as far as I can tell), which are both stored in memory and hence
%% not handled very well by us anyway.
%%
%% 3. can v <- Constant be removed ? I think so. all uses of v will be
%% replaced with an immediate. So why not ?
%%
%% ============================================================================
%%
%% TODO:
%%
%% Take care of failures in call and replace operation with apropriate
%% failure.
%%
%% Handle ifs with non-binary operators
%%
%% We want multisets for easier (and faster) creation of env->ssa_edges
%%
%% Propagation of constant arguments when some of the arguments are bottom
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-module(hipe_rtl_ssa_const_prop).
-export([propagate/1]).
-include("../main/hipe.hrl").
-include("hipe_rtl.hrl").
-include("../flow/cfg.hrl").
%-define(DEBUG, true).
-ifdef(DEBUG).
-define(SCCPDBG(W), W).
-define(DEBUG_TST, true). % make sure that we can use ?DEBUG in if-cases...
-else.
-define(DEBUG_TST, false). % make sure that we can use ?DEBUG in if-cases...
-define(SCCPDBG(W), ok).
-endif.
%%-----------------------------------------------------------------------------
%% Include stuff shared between SCCP on Icode and RTL.
%% NOTE: Needs to appear after DEBUG is possibly defined.
%%-----------------------------------------------------------------------------
-define(CODE, hipe_rtl).
-define(CFG, hipe_rtl_cfg).
-include("../ssa/hipe_ssa_const_prop.inc").
-type bool_lattice() :: 'true' | 'false' | 'top' | 'bottom'.
%%-----------------------------------------------------------------------------
%% Procedure : visit_expression/2
%% Purpose : do a symbolic execution of the given instruction. This is just
%% a wrapper that chooses the right function to handle a particular
%% instruction.
%% Arguments : Instructions - the instruction
%% Environment - have a guess.
%% Returns : {FlowWorkList, SSAWorkList, Environment}
%%-----------------------------------------------------------------------------
visit_expression(Instruction, Environment) ->
case Instruction of
#alu{} ->
visit_alu(Instruction, Environment);
#alub{} ->
visit_alub(Instruction, Environment);
#call{} ->
visit_call(Instruction, Environment);
%% #comment{} ->
%% visit_comment(Instruction, Environment);
%% #enter{} ->
%% visit_enter(Instruction, Environment);
#fconv{} ->
visit_fconv(Instruction, Environment);
#fixnumop{} ->
visit_fixnumop(Instruction, Environment);
#fload{} ->
visit_fload(Instruction, Environment);
#fmove{} ->
visit_fmove(Instruction, Environment);
#fp{} ->
visit_fp(Instruction, Environment);
#fp_unop{} ->
visit_fp_unop(Instruction, Environment);
%% #fstore{} ->
%% visit_fstore(Instruction, Environment);
%% #gctest{} ->
%% visit_gctest(Instruction, Environment);
#goto{} ->
visit_goto(Instruction, Environment);
#goto_index{} ->
visit_goto_index(Instruction, Environment);
%% #label{} ->
%% visit_label(Instruction, Environment);
#load{} ->
visit_load(Instruction, Environment);
#load_address{} ->
visit_load_address(Instruction, Environment);
#load_atom{} ->
visit_load_atom(Instruction, Environment);
#load_word_index{} ->
visit_load_word_index(Instruction, Environment);
#move{} ->
visit_move(Instruction, Environment);
#multimove{} ->
visit_multimove(Instruction, Environment);
%% phi-nodes are handled in scc
%% #phi{} ->
%% visit_phi(Instruction, Environment);
%% #return{} ->
%% visit_return(Instruction, Environment);
%% #store{} ->
%% visit_store(Instruction, Environment);
#switch{} ->
visit_switch(Instruction, Environment);
_ ->
%% label, end_try, comment, return, fail, et al
{[], [], Environment}
end.
%%-----------------------------------------------------------------------------
%% Procedure : set_to/3
%% Purpose : many of the visit_<inst> functions ends in a update of the
%% environment (and resulting SSA-edges) this function does the
%% update in a nice way and formats the result so that it can be
%% imediatly returned to visit_expression
%% Arguments : Dst - the destination may be a list of destinations.
%% Val - the new value (bottom, or some constant).
%% Env - the environment in which the update should be done.
%% Returns : { FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
set_to(Dst, Val, Env) ->
{Env1, SSAWork} = update_lattice_value({Dst, Val}, Env),
{[], SSAWork, Env1}.
%%-----------------------------------------------------------------------------
%% Procedure : evaluate_fixnumop/2
%% Purpose : try to evaluate a fixnumop.
%% Arguments : Val1 - operand (an integer, 'top' or 'bottom')
%% Op - the operation.
%% Returns : Result
%% where result is an integer, 'top' or 'bottom'
%%-----------------------------------------------------------------------------
evaluate_fixnumop(Val1, Op) ->
if Val1 =:= top ->
top;
Val1 =:= bottom ->
bottom;
is_integer(Val1) ->
case Op of
tag ->
hipe_tagscheme:mk_fixnum(Val1);
untag ->
hipe_tagscheme:fixnum_val(Val1)
end
end.
%%-----------------------------------------------------------------------------
%% Procedure : visit_alu/2
%% Purpose : do symbolic exection of a alu
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : { FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_alu(Inst, Env) ->
Val1 = lookup_lattice_value(hipe_rtl:alu_src1(Inst), Env),
Val2 = lookup_lattice_value(hipe_rtl:alu_src2(Inst), Env),
{NewVal, _, _, _, _} = evaluate_alu(Val1, hipe_rtl:alu_op(Inst), Val2),
set_to(hipe_rtl:alu_dst(Inst), NewVal, Env).
%% Here follows the alu-evaluation stuff. This is the most involved part I
%% guess. The function that you may want to use is evaluate_alu/3. The
%% evaluation functions returns
%% { Result, SignFlag, ZeroFlag, Overflow flag, CarryBit}
%% it uses some helpers which are explained breifly:
%% lattice_meet/2 - handles the general case of most alu-operations, called
%% when at least one of the operands is nonconstant, and the
%% operation-specifics have been taken care of.
%% all_ones/0 - returns the value of a rtl-word set to all 1 bits.
%% partial_eval_alu - tries to catch some operation specific special cases
%% when one (or both) of the operands is nonconstant.
lattice_meet(Val1, Val2) ->
M = if (Val1 =:= top) or (Val2 =:= top) -> top;
(Val1 =:= bottom) or (Val2 =:= bottom) -> bottom
% the check is realy just sanity
end,
{M, M, M, M, M}.
all_ones() ->
(1 bsl ?bytes_to_bits(hipe_rtl_arch:word_size())) - 1.
%% when calling partial_eval*() we know that at least one of the Values
%% are bottom or top. They return { Value, Sign, Zero, Overflow, Carry }.
%% (just like hipe_rtl_arch:eval_alu)
%% logic shifts are very similar each other. Limit is the number of
%% bits in the words.
partial_eval_shift(Limit, Val1, Val2) ->
if
Val2 =:= 0 -> {Val1, Val1, Val1, Val1, Val1};
Val1 =:= 0 -> {0, false, true, false, false};
is_integer(Val2), Val2 >= Limit -> % (Val2 =/= top) and (Val2 =/= bottom)
{0, false, true, Val1, Val1}; % OVerflow & carry we dont know about.
true -> lattice_meet(Val1, Val2)
end.
%%-----------------------------------------------------------------------------
%% Procedure : partial_eval_alu/3
%% Purpose : try to evaluate as much as possible an alu operation where at
%% least one of the operands is not constant.
%% Arguments : Val1, Val2 - operands (integer, top or bottom)
%% Op - the operation.
%% Returns : {Result, Sign, Zero, Overflow, Carry}
%% where Result is an integer, 'top' or 'bottom'
%% and the others are bool, 'top' or 'bottom'.
%%-----------------------------------------------------------------------------
partial_eval_alu(Val1, add, Val2) ->
if
(Val1 == 0) -> {Val2, Val2, Val2, false, false};
(Val2 == 0) -> {Val1, Val1, Val1, false, false};
true -> lattice_meet(Val1, Val2)
end;
partial_eval_alu(Val1, sub, Val2) ->
if
(Val2 == 0) -> {Val1, Val1, Val1, false, false};
true -> lattice_meet(Val1, Val2)
end;
partial_eval_alu(Val1, 'or', Val2) ->
All_ones = all_ones(),
if
(Val1 == 0) -> {Val2, Val2, Val2, false, false};
(Val2 == 0) -> {Val1, Val1, Val1, false, false};
(Val1 == All_ones) or (Val2 == All_ones) ->
{All_ones, true, false, false, false};
true -> lattice_meet(Val1, Val2)
end;
partial_eval_alu(Val1, 'and', Val2) ->
All_ones = all_ones(),
if
Val1 == All_ones -> {Val2, Val2, Val2, false, false};
Val2 == All_ones -> {Val1, Val1, Val1, false, false};
(Val1 == 0) or (Val2 == 0) -> {0, false, true, false, false};
true -> lattice_meet(Val1, Val2)
end;
partial_eval_alu(Val1, 'xor', Val2) ->
if
(Val1 == 0) -> {Val2, Val2, Val2, false, false};
(Val2 == 0) -> {Val1, Val1, Val1, false, false};
true -> lattice_meet(Val1, Val2)
end;
partial_eval_alu(Val1, 'xornot', Val2) ->
All_ones = all_ones(),
if
Val1 == All_ones -> {Val2, Val2, Val2, false, false};
Val2 == All_ones -> {Val1, Val1, Val1, false, false};
true -> lattice_meet(Val1, Val2)
end;
partial_eval_alu(Val1, andnot, Val2) ->
All_ones = all_ones(),
if
(Val2 == 0) -> {Val1, Val1, Val1, false, false};
(Val1 == 0) or (Val2 == All_ones) -> {0, false, true, false, false};
true -> lattice_meet(Val1, Val2)
end;
partial_eval_alu(Val1, Op, Val2) when (Op =:= 'sll') or (Op =:= 'srl') ->
BitSize = ?bytes_to_bits(hipe_rtl_arch:word_size()),
partial_eval_shift(BitSize, Val1, Val2);
partial_eval_alu(Val1, Op, Val2) when (Op =:= 'sllx') or (Op =:= 'srlx') ->
partial_eval_shift(64, Val1, Val2);
partial_eval_alu(Val1, mul, Val2) -> lattice_meet(Val1, Val2); % XXX: suboptimal
% arithmetic shifts are more tricky, shifting something unknown can
% generate all_ones() and 0 depenging on the sign of Val1.
partial_eval_alu(Val1, Op, Val2) when (Op =:= 'sra') or (Op =:= 'srax') ->
if
(Val2 == 0) -> {Val1, Val1, Val1, false, false};
(Val1 == 0) -> {0, false, true, false, false};
true -> lattice_meet(Val1, Val2)
end.
%%-----------------------------------------------------------------------------
%% Procedure : evaluate_alu/3
%% Purpose : try to evaluate as much as possible of a alu operation.
%% Arguments : Val1, Val2 - operands (an integer, 'top' or 'bottom')
%% Op - the operation.
%% Returns : {Result, Sign, Zero, Overflow, Carry}
%% where result is an integer, 'top' or 'bottom'
%% and the others are Bool, 'top' or 'bottom'.
%%-----------------------------------------------------------------------------
evaluate_alu(Val1, Op, Val2) ->
if
(Val1 =:= top) or (Val2 =:= top) or
(Val1 =:= bottom) or (Val2 =:= bottom) -> partial_eval_alu(Val1, Op, Val2);
true ->
case Op of
sllx -> hipe_rtl_arith_64:eval_alu('sll', Val1, Val2);
srlx -> hipe_rtl_arith_64:eval_alu('srl', Val1, Val2);
srax -> hipe_rtl_arith_64:eval_alu('sra', Val1, Val2);
_ -> hipe_rtl_arch:eval_alu(Op, Val1, Val2)
end
end.
maybe_top_or_bottom(List) ->
maybe_top_or_bottom(List, false).
maybe_top_or_bottom([], TB) -> TB;
maybe_top_or_bottom([top | Rest], _) -> maybe_top_or_bottom(Rest, top);
maybe_top_or_bottom([bottom | _], _) -> bottom;
maybe_top_or_bottom([_ | Rest], TB) -> maybe_top_or_bottom(Rest, TB).
-spec partial_eval_branch(hipe_rtl:alub_cond(), bool_lattice(), bool_lattice(),
bool_lattice() | 0, bool_lattice() | 0) ->
bool_lattice().
partial_eval_branch(Cond, N0, Z0, V0, C0) ->
{N, Z, V, C} =
if Cond =:= 'eq';
Cond =:= 'ne' -> {true, Z0, true, true};
Cond =:= 'gt';
Cond =:= 'le' -> {N0, Z0, V0, true};
Cond =:= 'leu';
Cond =:= 'gtu' -> {true, Z0, true, C0 };
Cond =:= 'lt';
Cond =:= 'ge' -> {N0, true, V0, true};
Cond =:= 'geu';
Cond =:= 'ltu' -> {true, true, true, C0 };
Cond =:= 'overflow';
Cond =:= 'not_overflow' -> {true, true, V0, true}
end,
case maybe_top_or_bottom([N, Z, V, C]) of
false -> hipe_rtl_arch:eval_cond_bits(Cond, N, Z, V, C);
top -> top;
bottom -> bottom
end.
%%-----------------------------------------------------------------------------
%% Procedure : visit_alub/2
%% Purpose : do symbolic exection of a alub instruction
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : { FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_alub(Inst, Env) ->
Val1 = lookup_lattice_value(hipe_rtl:alub_src1(Inst), Env),
Val2 = lookup_lattice_value(hipe_rtl:alub_src2(Inst), Env),
{NewVal, N, Z, C, V} = evaluate_alu(Val1, hipe_rtl:alub_op(Inst), Val2),
Labels =
case NewVal of
bottom -> [hipe_rtl:alub_true_label(Inst),
hipe_rtl:alub_false_label(Inst)];
top -> [];
_ ->
%% if the partial branch cannot be evaluated we must execute the
%% instruction at runtime.
case partial_eval_branch(hipe_rtl:alub_cond(Inst), N, Z, C, V) of
bottom -> [hipe_rtl:alub_true_label(Inst),
hipe_rtl:alub_false_label(Inst)];
top -> [];
true -> [hipe_rtl:alub_true_label(Inst)];
false -> [hipe_rtl:alub_false_label(Inst)]
end
end,
{[], NewSSA, NewEnv} =
case hipe_rtl:alub_has_dst(Inst) of
false -> {[], [], Env};
true -> set_to(hipe_rtl:alub_dst(Inst), NewVal, Env)
end,
{Labels, NewSSA, NewEnv}.
%%-----------------------------------------------------------------------------
%% Procedure : visit_fixnumop/2
%% Purpose : do symbolic exection of a fixnumop instruction.
%% fixnumop is like a specialized alu.
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : { FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_fixnumop(Inst, Env) ->
Val = lookup_lattice_value(hipe_rtl:fixnumop_src(Inst), Env),
Res = evaluate_fixnumop(Val, hipe_rtl:fixnumop_type(Inst)),
set_to(hipe_rtl:fixnumop_dst(Inst), Res, Env).
%%-----------------------------------------------------------------------------
%% Procedure : visit_f*
%% Purpose : Do symbolic execution of floating point instructions.
%% All floating-point hitngs are mapped to bottom. In order to
%% implement them we would have to add hipe_rtl_arch:eval_f*
%% instructions since floating point is no exact science.
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_fconv(Inst, Env) ->
set_to(hipe_rtl:fconv_dst(Inst), bottom, Env).
visit_fp(Inst, Env) ->
set_to(hipe_rtl:fp_dst(Inst), bottom, Env).
visit_fp_unop(Inst, Env) ->
set_to(hipe_rtl:fp_unop_dst(Inst), bottom, Env).
visit_fload(Inst, Env) ->
set_to(hipe_rtl:fload_dst(Inst), bottom, Env).
visit_fmove(Inst, Env) ->
set_to(hipe_rtl:fmove_dst(Inst), bottom, Env).
%%-----------------------------------------------------------------------------
%% Procedure : visit_move/2
%% Purpose : execute a register-copy
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_move(Inst, Env) ->
Src = hipe_rtl:move_src(Inst),
Dst = hipe_rtl:move_dst(Inst),
set_to(Dst, lookup_lattice_value(Src, Env), Env).
%%-----------------------------------------------------------------------------
%% Procedure : visit_goto/2
%% Purpose : execute a goto
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_goto(Instruction, Environment) ->
GotoLabel = hipe_rtl:goto_label(Instruction),
{[GotoLabel], [], Environment}.
%%-----------------------------------------------------------------------------
%% Procedure : visit_goto_index/2
%% Purpose : execute a goto_index
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_goto_index(Inst, Env) ->
Index = hipe_rtl:goto_index_index(Inst),
case lookup_lattice_value(Index, Env) of
top -> { [], [], Env };
bottom -> %% everything is reachable
{ hipe_rtl:goto_index_labels(Inst), [], Env };
I -> %% only the ith label will be taken.
io:format("hipe_rtl_ssa_const_prop foud goto-index with constant index ~w in ~w\n",
[I, Inst]),
{ [ lists:nth(hipe_rtl:goto_index_labels(Inst), I) ], [], Env }
end.
%%-----------------------------------------------------------------------------
%% Procedure : visit_load/2
%% Purpose : do a visit_load. Its hard to track whats in memory, and it's
%% not in ssa form, so let's assume bottom-values !
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_load(Inst, Env) ->
set_to(hipe_rtl:load_dst(Inst), bottom, Env).
%%-----------------------------------------------------------------------------
%% Procedure : visit_load_address/2
%% Purpose : execute a load_address instruction, while there might be things
%% here that are runtime-constant they are not compile-time
%% constant since code loading interferes with addresses.
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_load_address(Inst, Env) ->
Dst = hipe_rtl:load_address_dst(Inst),
Val = bottom, %% all these are probably run-time, but not
%% compile-time constants
set_to(Dst, Val, Env).
%%-----------------------------------------------------------------------------
%% Procedure : visit_load_atom/2
%% Purpose : Like loadadress this one gets something that is not
%% compiletime-constant
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_load_atom(Inst, Env) ->
set_to(hipe_rtl:load_atom_dst(Inst), bottom, Env).
%%-----------------------------------------------------------------------------
%% Procedure : visit_load_word_index/2
%% Purpose : execute a load_word_index. Here is probably room for
%% improvement, we should be able to find some constants here,
%% since we can get the labeled values from the environment, and
%% then find the value with the given index.
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_load_word_index(Inst, Env) ->
io:format(" this is load word index: ~w\n", [Inst]),
set_to(hipe_rtl:load_word_index_dst(Inst), bottom, Env).
%%-----------------------------------------------------------------------------
%% Procedure : visit_multimove/2 & visit_multimove/4
%% Purpose : execute a multimove instruction.
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_multimove([Dst | Dsts], [Val | Vals], MyEnv, MySSA) ->
{NewEnv, NewSSA} = update_lattice_value({Dst, Val}, MyEnv),
visit_multimove(Dsts, Vals, NewEnv, MySSA ++ NewSSA);
visit_multimove([], [], MyEnv, MySSA) ->
{MyEnv, MySSA}.
visit_multimove(Inst, Env) ->
Srcs = [lookup_lattice_value(S, Env) ||
S <- hipe_rtl:multimove_srclist(Inst)],
{NewEnv, NewSSA} = visit_multimove(hipe_rtl:multimove_dstlist(Inst),
Srcs, Env, []),
{[], NewSSA, NewEnv}.
%%-----------------------------------------------------------------------------
%% Procedure : visit_call/2
%% Purpose : execute a call-instruction. All calls return bottom. We make
%% this assumption since the icode-leel have taken care of BIF's
%% and we belive that we are left with the things that can not be
%% done att compile time.
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
visit_call(Inst, Env) ->
{Env1, SSAWork} =
update_lattice_value({hipe_rtl:call_dstlist(Inst), bottom}, Env),
% remeber to add both continuation & failto things to the cfgwl
Cont = case hipe_rtl:call_continuation(Inst) of
[] -> [];
C -> [C]
end,
Succ = case hipe_rtl:call_fail(Inst) of
[] -> Cont;
Fail -> [Fail | Cont]
end,
{Succ, SSAWork, Env1}.
%%-----------------------------------------------------------------------------
%% Procedure : visit_switch/2
%% Purpose : execute a switch-statement.
%% Arguments : Inst - The instruction
%% Env - The environment
%% Returns : {FlowWorkList, SSAWorkList, NewEnvironment}
%%-----------------------------------------------------------------------------
%% first two helpers that are used to handle the mapping from value to label.
%% why isn't there a function that does this ?
find_switch_label(Inst, Val) ->
Labels = hipe_rtl:switch_labels(Inst),
?SCCPDBG(io:format("finding switch_label, ~w in ~w\n", [Val,Inst])),
%% it seems like the index is zero based. nth uses 1-based indexing.
lists:nth(Val + 1, Labels).
%% Switches seem tricky. the sort-order is a list of key-values to be
%% tested in order. (if elem i matches then we should jump to elem i of
%% the labels-list)
visit_switch(Inst, Env) ->
case lookup_lattice_value(hipe_rtl:switch_src(Inst), Env) of
top ->
{[], [], Env};
bottom ->
{hipe_rtl:switch_labels(Inst), [], Env};
Val ->
{[find_switch_label(Inst, Val) ], [], Env}
end.
%%-----------------------------------------------------------------------------
%% Procedure : update_instruction/2
%% Purpose : update the given instruction using any information found in
%% the environment.
%% Arguments : Inst - the instruction
%% Environment - in which everything happens.
%% Returns : list of new instructions.
%%-----------------------------------------------------------------------------
%% idea: what to do with vi <- Constant. wouldn't it be possible to
%% remove those ? (and similarily for alu-instructions. and alub
%% instructions also ! (of course this will be done in some later step dead
%% code elimination ? but it's a simple check.)
update_instruction(Inst, Env) ->
case Inst of
#alu{} ->
update_alu(Inst, Env);
#alub{} ->
update_alub(Inst, Env);
#call{} ->
subst_all_uses(Inst, Env);
%% #comment{} ->
%% [Inst];
#enter{} ->
subst_all_uses(Inst, Env);
#fconv{} ->
subst_all_uses(Inst, Env);
#fload{} ->
subst_all_uses(Inst, Env);
#fmove{} ->
subst_all_uses(Inst, Env);
#fp{} ->
subst_all_uses(Inst, Env);
#fp_unop{} ->
subst_all_uses(Inst, Env);
#fstore{} ->
subst_all_uses(Inst, Env);
#gctest{} ->
subst_all_uses(Inst, Env);
%% #goto{} ->
%% [ Inst ];
#goto_index{} ->
update_goto_index(Inst, Env);
%% #label{} ->
%% [ Inst ];
#load{} ->
subst_all_uses(Inst, Env);
#load_address{} ->
subst_all_uses(Inst, Env);
#load_atom{} ->
subst_all_uses(Inst, Env);
#load_word_index{} ->
subst_all_uses(Inst, Env);
#move{} ->
subst_all_uses(Inst, Env);
#multimove{} ->
subst_all_uses(Inst, Env);
#return{} ->
subst_all_uses(Inst, Env);
#store{} ->
subst_all_uses(Inst, Env);
#switch{} ->
update_switch(Inst, Env);
#phi{} ->
update_phi(Inst, Env);
_ -> % for the others it's sufficient to just update any thing they use.
[ Inst ]
end.
%%-----------------------------------------------------------------------------
%% Procedure : subst_uses/2
%% Purpose : looks up all things that an instruction uses and replaces
%% anything that is determined to be constant.
%% Arguments : Inst - the instruction
%% Env - in which everything happen.
%% Returns : list of instructions to replace Inst with.
%%-----------------------------------------------------------------------------
subst_all_uses(Inst, Env) ->
Uses = hipe_rtl_ssa:uses_to_rename(Inst),
[ hipe_rtl:subst_uses(update_srcs(Uses, Env), Inst) ].
%%-----------------------------------------------------------------------------
%% Procedure : update_srcs/2
%% Purpose : given the things that a instruction use return a list
%% {Src, NewValue} pairs that can be sent to subs_uses.
%% Arguments : Srcs - list of uses
%% Env - in which everything happens.
%% Returns : list of {Src, NewValue} pairs.
%%-----------------------------------------------------------------------------
update_srcs(Srcs, Env) ->
Update =
fun(Src, Os) ->
case lookup_lattice_value(Src, Env) of
bottom -> Os;
top -> % this would be realy strange.
?EXIT({"update_src, top", Src });
Constant ->
[ {Src, hipe_rtl:mk_imm(Constant)} | Os]
end
end,
lists:foldl(Update, [], Srcs ).
%%-----------------------------------------------------------------------------
%% functions for performing partial evaluation of alu-operations. They can
%% return either an integer (the actual result), move_src1 or move_src2 in
%% which case the alu-operation can be replace with a move, or keep_it in
%% which case the instruction must be kept.
%%-----------------------------------------------------------------------------
%% Procedure : partial_update_shift/3
%% Purpose : perform a shift
%% Arguments : Limit - the number of bits in the word to shift.
%% Val1 - the shiftee
%% Val2 - number of bits to shift
%% Returns : Integer, move_src1, keep_it
%%-----------------------------------------------------------------------------
partial_update_shift(Limit, Val1, Val2) ->
if
(Val1 =:= bottom) and (Val2 =:= 0) -> move_src1;
(Val1 =:= 0) or ((Val2 =/= bottom) and (Val2 >= Limit)) -> 0;
true -> keep_it
end.
%%-----------------------------------------------------------------------------
%% Procedure : partial_update_alu/3
%% Purpose : perform as much of alu-operations where exatcly one of the
%% operands is bottom.
%% Arguments : Val1, Val2 - operands
%% Op - the operation.
%% Returns : Integer, move_src1, move_src2, keep_it
%%-----------------------------------------------------------------------------
%% we know that exactly one of the operands are bottom this one
%% returns what to do with the instruction (it's either replace with
%% src1, replace src2 replace with constant or keep it.
partial_update_alu(Val1, 'add', Val2) ->
if
(Val1 == 0) -> move_src2;
(Val2 == 0) -> move_src1;
true -> keep_it
end;
partial_update_alu(_Val1, 'sub', Val2) ->
if
(Val2 == 0) -> move_src1;
true -> keep_it
end;
partial_update_alu(Val1, 'or', Val2) ->
All_ones = all_ones(),
if
(Val1 == 0) -> move_src2;
(Val2 == 0) -> move_src1;
(Val1 == All_ones) or (Val2 == All_ones) -> All_ones;
true -> keep_it
end;
partial_update_alu(Val1, 'and', Val2) ->
All_ones = all_ones(),
if
Val1 == All_ones -> move_src2;
Val2 == All_ones -> move_src1;
(Val1 == 0) or (Val2 == 0) -> 0;
true -> keep_it
end;
partial_update_alu(Val1, 'xor', Val2) ->
if
(Val1 == 0) -> move_src2;
(Val2 == 0) -> move_src1;
true -> keep_it
end;
partial_update_alu(Val1, 'xornot', Val2) ->
All_ones = all_ones(),
if
(Val1 == All_ones) -> move_src2;
(Val2 == All_ones) -> move_src1;
true -> keep_it
end;
partial_update_alu(Val1, andnot, Val2) ->
All_ones = all_ones(),
if
Val2 == 0 -> move_src1;
(Val1 == 0) or (Val2 == All_ones) -> 0;
true -> keep_it
end;
partial_update_alu(Val1, Op, Val2) when (Op =:= 'sll') or (Op =:= 'srl') ->
BitSize = ?bytes_to_bits(hipe_rtl_arch:word_size()),
partial_update_shift(BitSize, Val1, Val2);
partial_update_alu(Val1, Op, Val2) when (Op =:= 'sllx') or (Op =:= 'srlx') ->
partial_update_shift(64, Val1, Val2);
partial_update_alu(Val1, Op, Val2) when (Op =:= 'sra') or (Op =:= 'srax') ->
if
Val2 == 0 -> move_src1;
Val1 == 0 -> 0;
true -> keep_it
end.
%%-----------------------------------------------------------------------------
%% Procedure : update_alu/2
%% Purpose : update an alu-instruction.
%% Arguments : Inst - the instruction.
%% Env - in which everything happens.
%% Returns : list of new instruction
%%-----------------------------------------------------------------------------
update_alu(Inst, Env) ->
Val1 = lookup_lattice_value(hipe_rtl:alu_src1(Inst), Env),
Val2 = lookup_lattice_value(hipe_rtl:alu_src2(Inst), Env),
if
(Val1 =:= bottom) and (Val2 =:= bottom) ->
[Inst];
(Val1 =:= bottom) or (Val2 =:= bottom) ->
NewInst =
case partial_update_alu(Val1, hipe_rtl:alu_op(Inst), Val2) of
move_src1 ->
hipe_rtl:mk_move(hipe_rtl:alu_dst(Inst), hipe_rtl:alu_src1(Inst));
move_src2 ->
hipe_rtl:mk_move(hipe_rtl:alu_dst(Inst), hipe_rtl:alu_src2(Inst));
keep_it ->
S1 = make_alub_subst_list(Val1, hipe_rtl:alu_src1(Inst), []),
S2 = make_alub_subst_list(Val2, hipe_rtl:alu_src2(Inst), S1),
hipe_rtl:subst_uses(S2, Inst);
Constant ->
hipe_rtl:mk_move(hipe_rtl:alu_dst(Inst), hipe_rtl:mk_imm(Constant))
end,
[NewInst];
true ->
{Val,_,_,_,_} = evaluate_alu(Val1, hipe_rtl:alu_op(Inst), Val2),
[hipe_rtl:mk_move(hipe_rtl:alu_dst(Inst), hipe_rtl:mk_imm(Val))]
end.
%%-----------------------------------------------------------------------------
%% Procedure : update_alub/2
%% Purpose : update an alub-instruction. Here are some finer points, we might
%% be able to do the math (think b = a+0), but it's hard to replace
%% the branch, since the mapping b/w AluOp,RelOp to BranchInstr is
%% boring to do. (lazyness is a bliss).
%% Arguments : Inst - the instruction.
%% Env - in which everything happens.
%% Returns : list of new instructions
%%-----------------------------------------------------------------------------
%% some small helpers.
alub_to_move(Inst, Res, Lab) ->
Goto = [hipe_rtl:mk_goto(Lab)],
case hipe_rtl:alub_has_dst(Inst) of
false -> Goto;
true ->
[hipe_rtl:mk_move(hipe_rtl:alub_dst(Inst), Res) | Goto]
end.
make_alub_subst_list(bottom, _, Tail) -> Tail;
make_alub_subst_list(top, Src, _) ->
?EXIT({"~w is top during update",Src });
make_alub_subst_list(Val, Src, Tail) ->
case hipe_rtl:is_imm(Src) of
true -> Tail;
false -> [{Src, hipe_rtl:mk_imm(Val)} | Tail]
end.
update_alub(Inst, Env) ->
Src1 = hipe_rtl:alub_src1(Inst),
Src2 = hipe_rtl:alub_src2(Inst),
Val1 = lookup_lattice_value(Src1, Env),
Val2 = lookup_lattice_value(Src2, Env),
{ResVal, N, Z, C, V} = evaluate_alu(Val1, hipe_rtl:alub_op(Inst), Val2),
CondRes = partial_eval_branch(hipe_rtl:alub_cond(Inst), N, Z, C, V),
case CondRes of
bottom ->
%% if we can't evaluate the branch, we have to keep it as a alub isnt
%% since other optimizations might insert other instructions b/w the
%% move and the branch. We can however replace variable with constants:
S1 = make_alub_subst_list(Val1, Src1, []),
S2 = make_alub_subst_list(Val2, Src2, S1),
[hipe_rtl:subst_uses(S2, Inst)];
_ -> %% we know where we will be going, let's find out what Dst should be.
%% knowing where we are going means that at most one of the values is
%% bottom, hence we can replace the alu-instr with a move.
%% remember, a = b + 0 can give us enough info to know what jump to
%% do without knowing the value of a. (I wonder if this will ever
%% actualy happen ;)
Res = case ResVal of
bottom -> % something nonconstant.
if (Val1 =:= bottom) -> Src1;
(Val2 =:= bottom) -> Src2
end;
_ -> hipe_rtl:mk_imm(ResVal)
end,
case CondRes of
top ->
io:format("oops. something VERY bad: ~w ~w V1 & 2 ~w ~w\n",
[Inst, {ResVal, N, Z, C, V} , Val1, Val2]),
[Inst];
true -> alub_to_move(Inst, Res, hipe_rtl:alub_true_label(Inst));
false -> alub_to_move(Inst, Res, hipe_rtl:alub_false_label(Inst))
end
end.
%%-----------------------------------------------------------------------------
%% Procedure : update_goto_index/2
%% Purpose : update a goto_index instruction.
%% Arguments : Inst - the instruction.
%% Env - in which everything happens.
%% Returns : list of new instructions.
%%-----------------------------------------------------------------------------
update_goto_index(Inst, Env) ->
Index = hipe_rtl:goto_index_index(Inst),
case lookup_lattice_value(Index, Env) of
bottom -> %% everything is reachable
[Inst];
I -> %% only the ith label will be taken.
[hipe_rtl:mk_goto(lists:nth(hipe_rtl:goto_index_labels(Inst), I))]
end.
%%-----------------------------------------------------------------------------
%% Procedure : update_switch/2
%% Purpose : update a switch instruction.
%% Arguments : Inst - the instruction.
%% Env - in which everything happens.
%% Returns : list of new instructions.
%%-----------------------------------------------------------------------------
update_switch(Inst, Env) ->
case lookup_lattice_value(hipe_rtl:switch_src(Inst), Env) of
bottom ->
[Inst];
Const ->
Lab = find_switch_label(Inst, Const),
[hipe_rtl:mk_goto(Lab)]
end.
%%-----------------------------------------------------------------------------
%% Procedure : update_phi/3
%% Purpose : Update a phi-function w.r.t. constants. do nothing for now.
%% Arguments : Instruction - The instruction
%% Environment - The environment
%% Returns : [NewInstruction]
%%-----------------------------------------------------------------------------
update_phi(Instruction, Environment) ->
Destination = hipe_rtl:phi_dst(Instruction),
case lookup_lattice_value(Destination, Environment) of
bottom ->
[Instruction];
top ->
?WARNING_MSG("The dst of ~w is top after SCCP. Strange\n",[Instruction]),
?EXIT({"bang !", Instruction}),
[Instruction];
Value ->
[hipe_rtl:mk_move(Destination, hipe_rtl:mk_imm(Value))]
end.
%%-----------------------------------------------------------------------------
%% make sure that all precoloured registers are taken out of the equation.
lookup_lattice_value(X, Environment) ->
case hipe_rtl_arch:is_precoloured(X) or hipe_rtl:is_const_label(X) of
true ->
bottom;
false ->
lookup_lattice_value2(X, Environment)
end.
lookup_lattice_value2(X, Environment) ->
LatticeValues = env__lattice_values(Environment),
case hipe_rtl:is_imm(X) of
true ->
hipe_rtl:imm_value(X);
false ->
case gb_trees:lookup(X, LatticeValues) of
none ->
io:format("~w~n",[LatticeValues]),
?WARNING_MSG("Earlier compiler steps generated erroneous "
"code for X = ~w. We are ignoring this.\n",[X]),
bottom;
{value, top} ->
?EXIT({"lookup_lattice_value, top", X}),
top;
{value, Y} ->
Y
end
end.
%%----------------------------- End of file -----------------------------------
