| Age | Commit message (Collapse) | Author |
|---|
|
Optimize ssa_opt_sink for huge functions
|
|
The ssa_opt_sink optimization of beam_ssa_opt could get very slow
for certain huge functions. 9a190cae9bd7 partly addressed this issue
by terminating the optimization early if there happened to be no
get_tuple_element instructions at all in the function.
This commit addresses the issue more directly by making the dominator
calculation in beam_ssa:dominators/1 more efficient. The same
algorithm as before is used, but it is implemented in a more efficient
way based on the ideas in "A Simple, Fast Dominance Algorithm"
(http://www.hipersoft.rice.edu/grads/publications/dom14.pdf).
As well as being more efficient, the new implementation also gives
an explicit representation of the dominator tree, which makes it
possible to simplify and optimize the ssa_opt_sink optimization.
|
|
Prior to 294d66a295f6c2101fe3c2da630979ad4e736c08 there wasn't much
point to keeping track of tuple element types; they were only known
when we had inserted or extracted values from a tuple, and in
neither case was it likely that we'd extract the same values again.
It makes a lot more sense to do so now that type optimizations are
applied across functions; if we return a tuple it's very likely
that its elements will be extracted soon after, and knowing their
types lets us eliminate more type checks.
Co-authored-by: Björn Gustavsson <[email protected]>
|
|
|
|
|
|
|
|
Reduce compilation times
|
|
There could be a warning with a `no_file` atom instead of filename
and line number.
|
|
Two helper functions in beam_ssa_opt and beam_ssa_dead
are body-recursive for no good reason.
While at it, add some clarifying comments to the functions.
|
|
beam_ssa:def_used/2 is used by beam_ssa_pre_codegen when reserving
Y registers.
Do the following optimizations:
* Use an ordset instead of a gb_set. When the only operation performed
on a set is union/2, an ordset will usually be faster, especially when
the result is an ordset.
* Use a cerl_set instead of a gb_set for the set of all possible
predecessors. cerl_sets is usually faster than gb_sets.
|
|
Avoiding calls usually reduces the size of the stack frame and reduces
register shuffling.
|
|
|
|
Save a little time by using gb_sets:delete/2 instead of
gb_sets:delete_any/2 when the key is known to be in the set.
|
|
beam_ssa_dead could be very slow if there were many blocks
connected with unconditional branches (for example, if a block
had contained many `call` instructions and been split by
ssa_opt_split_blocks).
It turns out that `comb_get_sw/3` does an unnecessary (and perhaps
incorrect) recursive call to itself when the terminator for the
block is an unconditional branch. Removing the recursive call does
not disable any optimizations, but will be much faster if there
are many blocks connected with unconditional branches.
Reported-by: Michał Muskała
|
|
Compilation will be much faster if there are many blocks, but no
get_tuple_element instructions.
Reported-by: Michał Muskała
|
|
Fix internal consistency failure caused by beam_except
|
|
Fix a bug where the number of live registers in a `bs_get_tail`
instruction was too low.
Consider this example:
-export([bs_get_tail/2]).
bs_get_tail(Bin, Config) ->
bs_get_tail_1(Bin, 0, 0, Config).
bs_get_tail_1(<<_:32, Rest/binary>>, Z1, Z2, F1) ->
{Rest,Z1,Z2,F1}.
`beam_validator` would emit the following diagnostics:
t: function bs_get_tail_1/4+2:
Internal consistency check failed - please report this bug.
Instruction: {func_info,{atom,t},{atom,bs_get_tail_1},4}
Error: {uninitialized_reg,{x,3}}:
Here is the part of the code that generates the `function_clause`
exception before the optimization:
{test_heap,6,4}.
{put_list,{x,3},nil,{x,2}}.
{put_list,{integer,0},{x,2},{x,2}}.
{put_list,{integer,0},{x,2},{x,2}}.
{bs_set_position,{x,1},{x,0}}.
{bs_get_tail,{x,1},{x,0},3}. %3 live registers.
{test_heap,2,3}.
{put_list,{x,0},{x,2},{x,1}}.
{move,{atom,function_clause},{x,0}}.
{line,[{location,"t.erl",8}]}.
{call_ext_only,2,{extfunc,erlang,error,2}}.
The `bs_get_tail` instruction expects that 3 registers will be live
at this point. `beam_except` rewrites the code like this:
{bs_set_position,{x,1},{x,0}}.
{bs_get_tail,{x,1},{x,0},3}. %Still 3. Too low.
{move,{integer,0},{x,1}}.
{move,{integer,0},{x,2}}.
{jump,{f,3}}.
Now the number of live registers in `bs_get_tail` is too low,
because the `{x,3}` register will become undefined.
This commit adds code to update the number of live registers
in the `bs_get_tail` instruction, producing this code:
{bs_set_position,{x,1},{x,0}}.
{bs_get_tail,{x,1},{x,0},4}. %Adjusted to 4.
{move,{integer,0},{x,1}}.
{move,{integer,0},{x,2}}.
{jump,{f,3}}.
|
|
* maint:
Eliminate bogus warning when using tuple calls
|
|
There would be a bogus warning when compiling the following
function with the `tuple_calls` option:
dispatch(X) ->
(list_to_atom("prefix_" ++ atom_to_list(suffix))):doit(X).
The warning would look like this:
no_file: this expression will fail with a 'badarg' exception
https://bugs.erlang.org/browse/ERL-838
|
|
Enhance optimization of function_clause exceptions
|
|
There is an optimization for reducing the number of instructions needed
to generate a `function_clause`. After the latest improvements of the
type optimization pass, that optimization is not always applied.
Here is an example:
-export([foo/3]).
foo(X, Y, Z) ->
bar(a, X, Y, Z).
bar(a, X, Y, Z) when is_tuple(X) ->
{X,Y,Z}.
Note that the compiler internally adds a clause to each function to
generate a `function_clause` exception. Thus:
bar(a, X, Y, Z) when is_tuple(X) ->
{X,Y,Z};
bar(A1, A2, A3, A4) ->
erlang:error(function_clause, [A1,A2,A3,A4]).
Optimizations will rewrite the code basically like this:
bar(_, X, Y, Z) when is_tuple(X) ->
{X,Y,Z};
bar(_, A2, A3, A4) ->
erlang:error(function_clause, [a,A2,A3,A4]).
Note the `a` as the first element of the list of arguments. It
will prevent the optimization of the `function_clause` exception.
The BEAM code for `bar/4` looks like this:
{function, bar, 4, 4}.
{label,3}.
{line,[{location,"t.erl",8}]}.
{func_info,{atom,t},{atom,bar},4}.
{label,4}.
{'%',{type_info,{x,0},{atom,a}}}.
{test,is_tuple,{f,5},[{x,1}]}.
{test_heap,4,4}.
{put_tuple2,{x,0},{list,[{x,1},{x,2},{x,3}]}}.
return.
{label,5}.
{test_heap,8,4}.
{put_list,{x,3},nil,{x,0}}.
{put_list,{x,2},{x,0},{x,0}}.
{put_list,{x,1},{x,0},{x,0}}.
{put_list,{atom,a},{x,0},{x,1}}.
{move,{atom,function_clause},{x,0}}.
{line,[{location,"t.erl",8}]}.
{call_ext,2,{extfunc,erlang,error,2}}.
The code after label 5 is the clause that generates the
`function_clause` exception.
This commit generalizes the optimization so that it can be applied for
this function:
{function, bar, 4, 4}.
{label,3}.
{line,[{location,"t.erl",8}]}.
{func_info,{atom,t},{atom,bar},4}.
{label,4}.
{'%',{type_info,{x,0},{atom,a}}}.
{test,is_tuple,{f,5},[{x,1}]}.
{test_heap,4,4}.
{put_tuple2,{x,0},{list,[{x,1},{x,2},{x,3}]}}.
return.
{label,5}.
{move,{atom,a},{x,0}}.
{jump,{f,3}}.
For this particular function, it would be safe to omit the
`move` instruction before the `{jump,{f,3}}` instruction, but
it would not be safe in general to omit `move` instructions.
|
|
* john/compiler/refactor-validator-type-mgmt:
beam_validator: Add explicit assertions for fragile terms
beam_validator: Refactor type management
|
|
Speed up the compiler when compiling the idna package
|
|
Fix problems compiling Scalaris
|
|
We haven't seen any related bugs so far, but all instructions that
place a term in another ought to reject fragile inputs. It can't
hurt to check.
|
|
Our current type management (based on set_type_reg etc) is rather
error-prone, often requiring special cases on a per-instruction
basis. This commit replaces nearly all ad-hoc mechanisms with more
general abstractions:
* assign - Moves a term.
* create_term - Creates a new term.
* extract_term - Extracts a term from another, maintaining
fragility as required.
* update_type - Adds more type information about a register.
* type_test - Helper function for type tests that subtracts on
failure and meets on success.
|
|
The translation from `error(function_clause, Args)` to a jump
to the `func_info` label is not safe if there is a stack frame.
|
|
Compilation of code similar the following would be very slow:
uts46_map(CP) when 0 =< CP, CP =< 44 -> '3';
uts46_map(CP) when 45 =< CP, CP =< 46 -> 'V';
uts46_map(CP) when 48 =< CP, CP =< 57 -> 'V';
%% More than 2500 similar lines follows.
.
.
.
The code is from from:
https://github.com/benoitc/erlang-idna/blob/3eb54ccbfa6fb917c0f4ca9197da337ad888ffe0/src/idna_mapping.erl#L6780
By using information about skippable blocks, the beam_ssa_dead
pass can be sped up to compile idna_mapping.erl about 10 times faster.
|
|
It is never possible to merge a block ending in a switch with the
next block, so it is not necessary to call `beam_ssa:successors/1` in
that case. Avoiding the call slightly improves compilation speeds
for switches with many branches.
|
|
To improve compilation times, beam_ssa_type keeps track of variables
that are only used once and don't keep types for those variables. As
currently implemented, it turns to be unsafe. Change it to only keep
track of variables that are only used in the terminator of the block
they are defined in.
https://bugs.erlang.org/browse/ERL-840
|
|
If compilation failed, the name of the current function *and*
all previously compiled functions would be printed because
phase/4 was not tail-recursive.
https://bugs.erlang.org/browse/ERL-840
|
|
* john/compiler/trim-ignore-annos:
beam_trim: Ignore type annotations
|
|
* john/compiler/misc-validator-fixes/ERL-832:
Make the beam_validator smarter again, again
|
|
Reduce redundant moves and register shuffling
|
|
The fix in f9ea85611faca82c7494449ddb8bcb1ef1d194cb didn't consider
that the tested register could be aliased.
|
|
The type annotations inserted by beam_ssa_type and beam_ssa_bsm
would inadvertently disable stack trimming, as unknown instructions
are considered unsafe.
|
|
Try to eliminate short blocks that starts with a phi node
and end in a return. For example:
Result = phi { Res1, 4 }, { literal true, 5 }
Ret = put_tuple literal ok, Result
ret Ret
The code in this block can be inserted at the end blocks 4 and
5. Thus, the following code can be inserted into block 4:
Ret:1 = put_tuple literal ok, Res1
ret Ret:1
And the following code into block 5:
Ret:2 = put_tuple literal ok, literal true
ret Ret:2
Which can be further simplified to:
ret literal {ok, true}
This transformation may lead to more code improvements, for example:
* Stack trimming
* Fewer test_heap instructions
* Smaller stack frames
|
|
Apply type optimizations across local function calls
|
|
This commit lets the type optimization pass work across functions,
tracking return and argument types to eliminate redundant tests.
|
|
This serves as a base for the upcoming module-level type
optimization, but may come in handy for other passes like
beam_ssa_funs and beam_ssa_bsm that have their own ad-hoc
implementations.
|
|
Consider this function and its corresponding BEAM code:
foo(Map, Key) ->
Val = case Map of
#{Key:=Val0} -> Val0;
_ -> default
end,
bar(1, 2, Val).
{label,2}.
{test,is_map,{f,3},[{x,0}]}.
{get_map_elements,{f,3},{x,0},{list,[{x,1},{x,0}]}}.
^^^^^
{jump,{f,4}}.
{label,3}.
{move,{atom,default},{x,0}}.
^^^^^
{label,4}.
{move,{integer,2},{x,1}}.
{move,{x,0},{x,2}}.
^^^^^
{move,{integer,1},{x,0}}.
{call_only,3,{f,6}}.
Note that the value of the variable `Val` will first be
placed in `{x,0}` and then moved to `{x,2}` where it needs
to be when calling the `bar/3` function.
The reason for the extra `move` instruction is that the
register allocator picks the lowest numbered available register
when choosing a register to put a variable in. In this case,
`{x,0}` will be chosen.
If we only could give a hint to the register allocator that
it would be better to put `Val` in `{x,2}`, the extra `move`
would disappear:
{label,2}.
{test,is_map,{f,3},[{x,0}]}.
{get_map_elements,{f,3},{x,0},{list,[{x,1},{x,2}]}}.
{jump,{f,4}}.
{label,3}.
{move,{atom,default},{x,2}}.
{label,4}.
{move,{integer,2},{x,1}}.
{move,{integer,1},{x,0}}.
{call_only,3,{f,6}}.
There already is an existing sub pass (`reserve_regs`) in
`beam_ssa_pre_codegen` that among things tries to give the register
allocator hints that some variables should be placed in specific
registers, if possible. However, the existing hinting mechanism is
limited, essentially only working within a single SSA block.
This commit extends the hinting mechanism, allowing hints to be passed
across SSA blocks, eliminating `move` instructions and register
shuffling in many places. (494 modules out of a sample of 1236 modules
were changed by this commit.)
|
|
Use lists:splitwith/2 instead of lists:partition/2 for splitting out
phi nodes. Since phi nodes are always the first instructions in a
block, the result will be the same, but splitwith/2 is faster.
|
|
If the match instruction was already marked as a skip, we'd ruin
its argument list.
|
|
A switch is equivalent to a series of '=:=', so we have to subtract
each value individually from the type. Subtracting a join risks
removing too much type information, and managed to narrow "number"
into "float" in the attached test case.
|
|
|
|
|
|
|
|
|
|
* bjorn/compiler/misc:
beam_ssa_type: Simplify is_singleton_type/1
beam_ssa_opt: Run ssa_opt_tuple_size early
beam_ssa_codegen: Remove forgotten and unreachable clause
beam_ssa_opt: Run the type optimization pass twice
beam_ssa_type: Eliminate redundant 'succeeded' instructions
|
|
* bjorn/compiler/fix-inlined-funs:
sys_core_inline: Kill *all* fun annotations when inlining
|
