| Age | Commit message (Collapse) | Author |
|---|
|
Consider the following code:
bme(Int) ->
TagInt = Int band 2#111,
Tag = case TagInt of
0 -> a; 1 -> b; 2 -> c; 3 -> d;
4 -> e; 5 -> f; 6 -> g; 7 -> h
end,
case Tag of
g -> expects_g(TagInt, Tag);
h -> expects_h(TagInt, Tag);
_ -> Tag = id(Tag), ok
end.
expects_g(6, Atom) -> Atom = id(g), ok.
expects_h(7, Atom) -> Atom = id(h), ok.
The type optimization pass would recognize that TagInt can only be
[0 .. 7], so the first 'case' would select_val over [0 .. 6] and swap
out the fail label with the block for 7.
A later optimization would merge this block with 'expects_h' in the
second case, as the latter is only reachable from the former.
... but this broke down when the move elimination optimization didn't
take the fail label of the first select_val into account. This caused it
believe that the only way to reach 'expects_h' was through the second
case when 'Tag' =:= 'h', which made it remove the move instruction
added in the first case, passing garbage to expects_h/2.
|
|
|
|
The previous optimizations caused some code in beam_jump to
become uncovered. Add tests to cover more code. Also remove
a clause in beam_jump:opt/3 that does not seem possible to
cover anymore (this is safe, because the clause was an
optimization).
|
|
Eliminate a jump to a return sequence, replacing the jump with
the return sequence. This optimization always save execution time
and may also save code space.
|
|
181cfc4ef9d1 stopping used #st.index.
|
|
Prior to this commit, the optimizations using beam_utils:is_killed/3
were only executed a few times in the entire compiler test suite.
|
|
This will help investigation of compiler bugs.
|
|
* maint:
Fix bug when beam_jump removes put_tuple instructions
Conflicts:
lib/compiler/src/beam_jump.erl
lib/compiler/test/beam_jump_SUITE.erl
|
|
`beam_jump` could remove a `put_tuple` instruction when the
tuple would not be used, but it would leave the following
`put` instructions. Make sure they are removed.
https://bugs.erlang.org/browse/ERL-759
|
|
The `beam_jump` pass could eliminate `move` instructions when it was
not safe to do so. See the new test case `unsafe_move_elimination/1`
for an example.
Reported-by: Michał Muskała
|
|
This has been superseded by bs_get_tail/3. Note that it is NOT
removed from the emulator or beam_disasm, as old modules are still
legal.
|
|
Most of the optimizations in beam_dead have been superseded
by the optimizations in beam_ssa_dead.
The forward/1 pass of beam_dead has been moved to beam_jump.
The beam_split pass splits blocks that contain instructions with
non-zero labels. Because there are no optimizations left that optimize
instructions within blocks, beam_block never needs to put such
instructions into blocks in the first place. beam_split also moved
'move' instructions out block to help beam_dead. That is no longer
necessary since beam_dead no longer exists.
|
|
This functionality will soon be needed.
|
|
v3_codegen is replaced by three new passes:
* beam_kernel_to_ssa which translates the Kernel Erlang format
to a new SSA-based intermediate format.
* beam_ssa_pre_codegen which prepares the SSA-based format
for code generation, including register allocation. Registers
are allocated using the linear scan algorithm.
* beam_ssa_codegen which generates BEAM assembly code from the
SSA-based format.
It easier and more effective to optimize the SSA-based format before X
and Y registers have been assigned. The current optimization passes
constantly have to make sure no "holes" in the X register assignments
are created (that is, that no X register becomes undefined that an
allocation instruction depends on).
This commit also introduces the following optimizations:
* Replacing of tuple matching of records with the is_tagged_tuple
instruction. (Replacing beam_record.)
* Sinking of get_tuple_element instructions to just before the first
use of the extracted values. As well as potentially avoiding
extracting tuple elements when they are not actually used on all
executions paths, this optimization could also reduce the number
values that will need to be stored in Y registers. (Similar to
beam_reorder, but more effective.)
* Live optimizations, removing the definition of a variable that is
not subsequently used (provided that the operation has no side
effects), as well strength reduction of binary matching by replacing
the extraction of value from a binary with a skip instruction. (Used
to be done by beam_block, beam_utils, and v3_codegen.)
* Removal of redundant bs_restore2 instructions. (Formerly done
by beam_bs.)
* Type-based optimizations across branches. More effective than
the old beam_type pass that only did type-based optimizations in
basic blocks.
* Optimization of floating point instructions. (Formerly done
by beam_type.)
* Optimization of receive statements to introduce recv_mark and
recv_set instructions. More effective with far fewer restrictions
on what instructions are allowed between creating the reference
and entering the receive statement.
* Common subexpression elimination. (Formerly done by beam_block.)
|
|
Optimise beam_jump
|
|
|
|
This is an alternative to #1832.
The optimisation relies on special-casing the common pattern of
"renaming" a label by direct jump to another label. The change makes
beam_jump recognise couple more opportunities for optimisation.
The optimisation additionally avoids superfluous list concatenations by
only flattening the accumulator at the very end.
|
|
This is especially useful after inlining a function with a case.
Today the compiler would most probably be able to unify all the leafs of the
case during the sharing optimisation, but it would fail to unify the pattern
matching itself.
Naively running the optimisation multiple times wouldn't be able to find the
common code either, because it would differ in jump/fail targets of various
instructions.
To remedy this, after doing each sharing pass we traverse the code backwards
when reversing and update all the jump targets with the new targets that were
discovered during the unification pass. This allows running the optimisation
until fixpoint and makes sure all sharing opportunities will be discovered.
This optimisation also helps with the Elixir's `with/else` construct.
|
|
We have found cases where compilation drastically slows down
due to this commit. We are working on a minimal cases and plan
to bring this patch back once we can work our the performance
issues.
This reverts commit f7c9383f4c3d4b6819b5ba4d54c7093df806fe4a.
|
|
This clause seems to have been introduced in cac51274eb9a.
|
|
Even though, it's not possible to have fall-throughs when entering the otp
pass, it can produce them itself and we're running the pass until fixpoint.
|
|
This makes other optimisations more efficient since we have less labels overall.
|
|
It can happen we have the following situation:
{test,is_tuple,Fail,[R1]}
{test,test_arity,Fail,[R1,N1]}
{get_tuple_element,R1,N2,R2}
{test,is_eq_exaqct,Fail,[R2,Atom]}
{jump,Fail}
Previously, the optimisation would eliminate the last is_eq_exact test, but
we can do more. If the register R2 is not used in Fail, we can eliminate the
get_tuple_element instruction as well as all the preceding tests. Ultimately,
the whole sequence can be replaced by:
{jump,Fail}
|
|
This is especially useful after inlining a function with a case.
Today the compiler would most probably be able to unify all the leafs of the
case during the sharing optimisation, but it would fail to unify the pattern
matching itself.
Naively running the optimisation multiple times wouldn't be able to find the
common code either, because it would differ in jump/fail targets of various
instructions.
To remedy this, after doing each sharing pass we traverse the code backwards
when reversing and update all the jump targets with the new targets that were
discovered during the unification pass. This allows running the optimisation
until fixpoint and makes sure all sharing opportunities will be discovered.
This optimisation also helps with the Elixir's `with/else` construct.
|
|
|
|
The guard optimizations in v3_kernel has removed the need for
beam_bool.
|
|
Since the beam_a pass has always been run and have removed any
unused label, there can never be a label as the very last
instruction in a function.
|
|
eliminate_fallthroughs/2 has special code to handle two labels next to
each other, but that does not seem to ever happen and there was one
line uncovered in is_label/1. Since inserting an extra jump between
two labels would not cause any real problems, remove the extra
handling of two consecutive labels.
|
|
It is not safe to share code between 'catch' blocks.
|
|
In complicated code with many indirect jumps to the func_info label,
a label could get lost.
|
|
|
|
Put 'try' instructions inside block to improve the optimization
of allocation instructions. Currently, the compiler only looks
at initialization of y registers inside blocks when determining
which y registers that will be "naturally" initialized.
|
|
|
|
Before beam_split the get_map_elements instruction is still in
blocks and the helper function in beam_jump did not reflect this.
Reported-by: Quviq twitter account
|
|
|
|
|
|
The use of lists:dropwhile/2 is noticeable in the eprof results.
|
|
* bjorn/compiler/beam_jump-share:
beam_jump: Don't jump into the middle of a 'try'
|
|
José Valim noticed that code such as:
match(1) -> 1;
match(2) -> 2;
match(3) -> 3;
...
match(1000) -> 1000.
would compile very slowly. The culprit is opt/3 in beam_jump.
What happens is that opt/3 will rewrite this code:
select_val ...
label 1
jump 1000
label 2
jump 1000
...
label 999
jump 1000
label 1000
return
very slowly to this code:
select_val ...
label 1
label 2
...
label 999
label 1000
return
The reason for the slowness is that when opt/3 sees this
sequence:
label 1
jump 1000
...
it will remove the label (storing it in a dictionary),
and pick up the previously processed instruction from
the accumulator:
select_val ...
jump 1000
label 2
jump 1000
...
That is done in order to process all labels before the
jump and also to get rid of the jump instruction if the
previous instruction is an "unreachable after". In this
case, re-processing the sequence will remove the now
unreachable jump instruction:
select_val ...
label 2
jump 1000
...
The problem is that re-processing the select_val instruction is
expensive. The instruction has a list of 1000 labels, all of which
will be added (again) to the set of referenced labels. The
select_val instruction will be re-processed again and again
until all labels and jumps have been gobbled up.
In the original version of beam_jump, opt/3 was not called
repeatedly until a fixpoint was found, but was expected to do
all its optimizations in one pass. The fixpoint iteration was
added later.
Since we now have the fixpoint iteration, there is no need
to do everything in a single pass. When we encounter a jump, we will
collect all previously seen labels and put them into the dictionary,
and then we will move on.
As a further optimization, we will look for sequences like this:
jump X
label ...
jump X
and replace them with:
label ...
jump X
In the example above, that will avoid 1000 updates of the dictionary.
After applying this optimization, compilation of the
pattern went from roughly 55 s to 0.1 s for the example
above but with 10000 clauses.
Reported-by: José Valim
|
|
The code sharing optimization could produce a jump into the
middle of a 'try' block. beam_validator would reject the code.
Reported-by: Ulf Norell
|
|
The get_map_elements instruction has been removed from all blocks by the
mandatory beam_split pass and thus only needs handling by the outer loop.
|
|
* nox/maps-beam_jump-put_map:
Properly collect labels in put_map instructions in beam_jump
|
|
Reported-by: Ulf Norell
|
|
Reported-by: Ulf Norell
|
|
* Combine multiple get values with one instruction
* Combine multiple check keys with one instruction
|
|
|
|
To make it possible to build the entire OTP system, also define
dummys for the instructions in ops.tab.
|
|
This makes applying the pass a second time a no-op.
|
|
|
|
Generate slightly smaller and faster code.
|
