%%
%% %CopyrightBegin%
%%
%% Copyright Ericsson AB 2018. All Rights Reserved.
%%
%% 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.
%%
%% %CopyrightEnd%
%%
%% Purpose: Internal consistency checks for the beam_ssa format.
-module(beam_ssa_lint).
-export([module/2, format_error/1]).
-import(lists, [append/1, foldl/3, foreach/2]).
-include("beam_ssa.hrl").
-spec module(#b_module{}, [compile:option()]) ->
{'ok',#b_module{}} | {'error',list()}.
module(#b_module{body=Fs,name=Name}=Mod0, _Options) ->
Es0 = append([validate_function(F) || F <- Fs]),
case [{?MODULE,E} || E <- Es0] of
[] ->
{ok, Mod0};
[_|_]=Es ->
{error,[{atom_to_list(Name), Es}]}
end.
-spec format_error(term()) -> iolist().
format_error({{_M,F,A},{redefined_variable, Name, Old, I}}) ->
io_lib:format("~p/~p: Variable ~ts (~ts) redefined by ~ts",
[F, A, format_var(Name), format_instr(Old), format_instr(I)]);
format_error({{_M,F,A},{missing_phi_paths, Paths, I}}) ->
io_lib:format("~p/~p: Phi node ~ts doesn't define a value for these "
"branches: ~w",
[F, A, format_instr(I), Paths]);
format_error({{_M,F,A},{garbage_phi_paths, Paths, I}}) ->
io_lib:format("~p/~p: Phi node ~ts defines a value for these unreachable "
"or non-existent branches: ~w",
[F, A, format_instr(I), Paths]);
format_error({{_M,F,A},{unknown_phi_variable, Name, {From, _To}, I}}) ->
io_lib:format("~p/~p: Variable ~ts used in phi node ~ts is undefined on "
"branch ~w",
[F, A, format_var(Name), format_instr(I), From]);
format_error({{_M,F,A},{unknown_block, Label, I}}) ->
io_lib:format("~p/~p: Unknown block ~p referenced in ~ts",
[F, A, Label, I]);
format_error({{_M,F,A},{unknown_variable, Name, I}}) ->
io_lib:format("~p/~p: Unbound variable ~ts used in ~ts",
[F, A, format_var(Name), format_instr(I)]);
format_error({{_M,F,A},{phi_inside_block, Name, Id}}) ->
io_lib:format("~p/~p: Phi node defining ~ts is not at start of block ~p",
[F, A, format_var(Name), Id]);
format_error({{_M,F,A},{undefined_label_in_phi, Label, I}}) ->
io_lib:format("~p/~p: Unknown block label ~p in phi node ~ts",
[F, A, Label, format_instr(I)]);
format_error({{_M,F,A},{succeeded_not_preceded, I}}) ->
io_lib:format("~p/~p: ~ts does not reference the preceding instruction",
[F, A, format_instr(I)]);
format_error({{_M,F,A},{succeeded_not_last, I}}) ->
io_lib:format("~p/~p: ~ts is not the last instruction in its block",
[F, A, format_instr(I)]).
format_instr(I) ->
[$',beam_ssa_pp:format_instr(I),$'].
format_var(V) ->
beam_ssa_pp:format_var(V).
validate_function(F) ->
try
validate_variables(F),
[]
catch
throw:Reason ->
#{func_info:=MFA} = F#b_function.anno,
[{MFA,Reason}];
Class:Error:Stack ->
io:fwrite("Function: ~p\n", [F#b_function.anno]),
erlang:raise(Class, Error, Stack)
end.
-type defined_vars() :: gb_sets:set(beam_ssa:argument()).
-record(vvars,
{blocks :: #{ beam_ssa:label() => beam_ssa:b_blk() },
branch_def_vars :: #{
%% Describes the variable state at the time of
%% this exact branch (phi node validation).
{From :: beam_ssa:label(),
To :: beam_ssa:label()} => defined_vars(),
%% Describes the variable state common to all
%% branches leading to this label (un/redefined
%% variable validation).
beam_ssa:label() => defined_vars() },
defined_vars :: defined_vars()}).
-spec validate_variables(beam_ssa:b_function()) -> ok.
validate_variables(#b_function{ args = Args, bs = Blocks }) ->
%% Prefill the mapping with function arguments.
Args = vvars_get_variables(Args),
DefVars = gb_sets:from_list(Args),
Entry = 0,
State = #vvars{blocks = Blocks,
branch_def_vars = #{ Entry => DefVars },
defined_vars = DefVars},
ok = vvars_assert_unique(Blocks, Args),
vvars_phi_nodes(vvars_block(Entry, State)).
%% Checks the uniqueness of all variables across all blocks.
-spec vvars_assert_unique(Blocks, [beam_ssa:b_var()]) -> ok when
Blocks :: #{ beam_ssa:label() => beam_ssa:b_blk() }.
vvars_assert_unique(Blocks, Args) ->
BlockIs = [Is || #b_blk{is=Is} <- maps:values(Blocks)],
Defined0 = maps:from_list([{V,argument} || V <- Args]),
_ = foldl(fun(Is, Defined) ->
vvars_assert_unique_1(Is, Defined)
end, Defined0, BlockIs),
ok.
-spec vvars_assert_unique_1(Is, Defined) -> ok when
Is :: list(beam_ssa:b_set()),
Defined :: #{ beam_ssa:b_var() => beam_ssa:b_set() }.
vvars_assert_unique_1([#b_set{dst=Dst}=I|Is], Defined) ->
case Defined of
#{Dst:=Old} -> throw({redefined_variable, Dst, Old, I});
_ -> vvars_assert_unique_1(Is, Defined#{Dst=>I})
end;
vvars_assert_unique_1([], Defined) ->
Defined.
-spec vvars_phi_nodes(State :: #vvars{}) -> ok.
vvars_phi_nodes(#vvars{ blocks = Blocks }=State) ->
_ = [vvars_phi_nodes_1(Is, Id, State) ||
{Id, #b_blk{ is = Is }} <- maps:to_list(Blocks)],
ok.
-spec vvars_phi_nodes_1(Is, Id, State) -> ok when
Is :: list(beam_ssa:b_set()),
Id :: beam_ssa:label(),
State :: #vvars{}.
vvars_phi_nodes_1([#b_set{ op = phi, args = Phis }=I | Is], Id, State) ->
ok = vvars_assert_phi_paths(Phis, I, Id, State),
ok = vvars_assert_phi_vars(Phis, I, Id, State),
vvars_phi_nodes_1(Is, Id, State);
vvars_phi_nodes_1([_ | Is], Id, _State) ->
case [Dst || #b_set{op=phi,dst=Dst} <- Is] of
[Var|_] ->
throw({phi_inside_block, Var, Id});
[] ->
ok
end;
vvars_phi_nodes_1([], _Id, _State) ->
ok.
%% Checks whether all paths leading to this phi node are represented, and that
%% it doesn't reference any non-existent paths.
-spec vvars_assert_phi_paths(Phis, I, Id, State) -> ok when
Phis :: list({beam_ssa:argument(), beam_ssa:label()}),
Id :: beam_ssa:label(),
I :: beam_ssa:b_set(),
State :: #vvars{}.
vvars_assert_phi_paths(Phis, I, Id, State) ->
BranchKeys = maps:keys(State#vvars.branch_def_vars),
RequiredPaths = ordsets:from_list([From || {From, To} <- BranchKeys, To =:= Id]),
ProvidedPaths = ordsets:from_list([From || {_Value, From} <- Phis]),
case ordsets:subtract(RequiredPaths, ProvidedPaths) of
[_|_]=MissingPaths -> throw({missing_phi_paths, MissingPaths, I});
[] -> ok
end.
%% %% The following test is sometimes useful to find missing optimizations.
%% %% It is commented out, though, because it can be triggered by
%% %% by weird but legal code.
%% case ordsets:subtract(ProvidedPaths, RequiredPaths) of
%% [_|_]=GarbagePaths -> throw({garbage_phi_paths, GarbagePaths, I});
%% [] -> ok
%% end.
%% Checks whether all variables used in this phi node are defined in the branch
%% they arrived on.
-spec vvars_assert_phi_vars(Phis, I, Id, State) -> ok when
Phis :: list({beam_ssa:argument(), beam_ssa:label()}),
Id :: beam_ssa:label(),
I :: beam_ssa:b_set(),
State :: #vvars{}.
vvars_assert_phi_vars(Phis, I, Id, #vvars{blocks=Blocks,
branch_def_vars=BranchDefVars}) ->
Vars = [{Var, From} || {#b_var{}=Var, From} <- Phis],
foreach(fun({Var, From}) ->
BranchKey = {From, Id},
case BranchDefVars of
#{BranchKey:=DefVars} ->
case gb_sets:is_member(Var, DefVars) of
true -> ok;
false -> throw({unknown_variable, Var, I})
end;
#{} ->
throw({unknown_phi_variable, Var, BranchKey, I})
end
end, Vars),
Labels = [From || {#b_literal{},From} <- Phis],
foreach(fun(Label) ->
case Blocks of
#{Label:=_} ->
ok;
#{} ->
throw({undefined_label_in_phi, Label, I})
end
end, Labels).
-spec vvars_block(Id, State) -> #vvars{} when
Id :: beam_ssa:label(),
State :: #vvars{}.
vvars_block(Id, State0) ->
#{ Id := #b_blk{ is = Is, last = Terminator} } = State0#vvars.blocks,
#{ Id := DefVars } = State0#vvars.branch_def_vars,
State = State0#vvars{ defined_vars = DefVars },
vvars_terminator(Terminator, Id, vvars_block_1(Is, State)).
-spec vvars_block_1(Is, State) -> #vvars{} when
Is :: list(#b_set{}),
State :: #vvars{}.
vvars_block_1([], State) ->
State;
vvars_block_1([#b_set{dst=OpVar,args=OpArgs}=I,
#b_set{op=succeeded,args=[OpVar],dst=SuccVar}], State) ->
ok = vvars_assert_args(OpArgs, I, State),
vvars_save_var(SuccVar, vvars_save_var(OpVar, State));
vvars_block_1([#b_set{op=succeeded,args=Args}=I | [_|_]], State) ->
ok = vvars_assert_args(Args, I, State),
%% 'succeeded' must be the last instruction in its block.
throw({succeeded_not_last, I});
vvars_block_1([#b_set{op=succeeded,args=Args}=I], State)->
ok = vvars_assert_args(Args, I, State),
%% 'succeeded' must be be directly preceded by the operation it checks.
throw({succeeded_not_preceded, I});
vvars_block_1([#b_set{ dst = Dst, op = phi } | Is], State) ->
%% We don't check phi node arguments at this point since we may not have
%% visited their definition yet. They'll be handled later on in
%% vvars_phi_nodes/1 after all blocks are processed.
vvars_block_1(Is, vvars_save_var(Dst, State));
vvars_block_1([#b_set{ dst = Dst, args = Args }=I | Is], State) ->
ok = vvars_assert_args(Args, I, State),
vvars_block_1(Is, vvars_save_var(Dst, State)).
-spec vvars_terminator(Terminator, From, State) -> #vvars{} when
Terminator :: beam_ssa:terminator(),
From :: beam_ssa:label(),
State :: #vvars{}.
vvars_terminator(#b_ret{ arg = Arg }=I, _From, State) ->
ok = vvars_assert_args([Arg], I, State),
State;
vvars_terminator(#b_switch{arg=Arg,fail=Fail,list=Switch}=I, From, State) ->
ok = vvars_assert_args([Arg], I, State),
ok = vvars_assert_args([A || {A,_Lbl} <- Switch], I, State),
Labels = [Fail | [Lbl || {_Arg, Lbl} <- Switch]],
ok = vvars_assert_labels(Labels, I, State),
vvars_terminator_1(Labels, From, State);
vvars_terminator(#b_br{bool=#b_literal{val=true},succ=Succ}=I, From, State) ->
Labels = [Succ],
ok = vvars_assert_labels(Labels, I, State),
vvars_terminator_1(Labels, From, State);
vvars_terminator(#b_br{bool=#b_literal{val=false},fail=Fail}=I, From, State) ->
Labels = [Fail],
ok = vvars_assert_labels(Labels, I, State),
vvars_terminator_1(Labels, From, State);
vvars_terminator(#b_br{ bool = Arg, succ = Succ, fail = Fail }=I, From, State) ->
ok = vvars_assert_args([Arg], I, State),
Labels = [Fail, Succ],
ok = vvars_assert_labels(Labels, I, State),
vvars_terminator_1(Labels, From, State).
-spec vvars_terminator_1(Labels, From, State) -> #vvars{} when
Labels :: list(beam_ssa:label()),
From :: beam_ssa:label(),
State :: #vvars{}.
vvars_terminator_1(Labels0, From, State0) ->
%% Filter out all branches that have already been taken. This should result
%% in either all of Labels0 or an empty list.
Labels = [To || To <- Labels0,
not maps:is_key({From, To}, State0#vvars.branch_def_vars)],
true = Labels =:= Labels0 orelse Labels =:= [], %Assertion
State1 = foldl(fun(To, State) ->
vvars_save_branch(From, To, State)
end, State0, Labels),
foldl(fun(To, State) ->
vvars_block(To, State)
end, State1, Labels).
%% Gets all variable names in args, ignoring literals etc
-spec vvars_get_variables(Args) -> list(beam_ssa:b_var()) when
Args :: list(beam_ssa:argument()).
vvars_get_variables(Args) ->
[Var || #b_var{}=Var <- Args].
%% Checks that all variables in Args are defined in all paths leading to the
%% current State.
-spec vvars_assert_args(Args, I, State) -> ok when
Args :: list(beam_ssa:argument()),
I :: beam_ssa:terminator() | beam_ssa:b_set(),
State :: #vvars{}.
vvars_assert_args(Args, I, #vvars{defined_vars=DefVars}=State) ->
foreach(fun(#b_remote{mod=Mod,name=Name}) ->
vvars_assert_args([Mod,Name], I, State);
(#b_var{}=Var) ->
case gb_sets:is_member(Var, DefVars) of
true -> ok;
false -> throw({unknown_variable,Var,I})
end;
(_) -> ok
end, Args).
%% Checks that all given labels are defined in State.
-spec vvars_assert_labels(Labels, I, State) -> ok when
Labels :: list(beam_ssa:label()),
I :: beam_ssa:terminator(),
State :: #vvars{}.
vvars_assert_labels(Labels, I, #vvars{blocks=Blocks}) ->
foreach(fun(Label) ->
case maps:is_key(Label, Blocks) of
false -> throw({unknown_block, Label, I});
true -> ok
end
end, Labels).
-spec vvars_save_branch(From, To, State) -> #vvars{} when
From :: beam_ssa:label(),
To :: beam_ssa:label(),
State :: #vvars{}.
vvars_save_branch(From, To, State) ->
DefVars = State#vvars.defined_vars,
Branches0 = State#vvars.branch_def_vars,
case Branches0 of
#{ To := LblDefVars } ->
MergedVars = vvars_merge_branches(DefVars, LblDefVars),
Branches = Branches0#{ To => MergedVars, {From, To} => DefVars },
State#vvars { branch_def_vars = Branches };
_ ->
Branches = Branches0#{ To => DefVars, {From, To} => DefVars },
State#vvars { branch_def_vars = Branches }
end.
-spec vvars_merge_branches(New, Existing) -> defined_vars() when
New :: defined_vars(),
Existing :: defined_vars().
vvars_merge_branches(New, Existing) ->
gb_sets:intersection(New, Existing).
-spec vvars_save_var(Var, State) -> #vvars{} when
Var :: #b_var{},
State :: #vvars{}.
vvars_save_var(Var, State0) ->
%% vvars_assert_unique guarantees that variables are never set twice.
DefVars = gb_sets:insert(Var, State0#vvars.defined_vars),
State0#vvars{ defined_vars = DefVars }.
