aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src/beam_jump.erl
AgeCommit message (Collapse)Author
2018-11-28Cover more code in beam_jumpBjörn Gustavsson
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).
2018-11-28beam_jump: Eliminate jumps to return instructionsBjörn Gustavsson
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.
2018-11-28beam_jump: Remove the unused #st.index fieldBjörn Gustavsson
181cfc4ef9d1 stopping used #st.index.
2018-11-06beam_jump: Stop using beam_utils:is_killed/3Björn Gustavsson
Prior to this commit, the optimizations using beam_utils:is_killed/3 were only executed a few times in the entire compiler test suite.
2018-11-06beam_trim, beam_jump: Print Name/Arity if there is a crashBjörn Gustavsson
This will help investigation of compiler bugs.
2018-11-02Merge branch 'maint'Björn Gustavsson
* maint: Fix bug when beam_jump removes put_tuple instructions Conflicts: lib/compiler/src/beam_jump.erl lib/compiler/test/beam_jump_SUITE.erl
2018-10-31Fix bug when beam_jump removes put_tuple instructionsBjörn Gustavsson
`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
2018-10-22Make the move elimination optimization in beam_jump safeBjörn Gustavsson
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
2018-09-28Remove unused instruction bs_context_to_binary from the compilerJohn Högberg
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.
2018-09-17Remove the beam_dead and beam_split passesBjörn Gustavsson
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.
2018-09-12Introduce the beam_jump:instr_labels/1 functionBjörn Gustavsson
This functionality will soon be needed.
2018-08-24Introduce a new SSA-based intermediate formatBjörn Gustavsson
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.)
2018-06-27Merge pull request #1833 from michalmuskala/mm/fix-beam-jumpBjörn Gustavsson
Optimise beam_jump
2018-06-18Update copyright yearHenrik Nord
2018-06-08Optimise beam_jumpMichał Muskała
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.
2018-06-08Run the sharing optimisation in beam_jump until fixpointMichał Muskała
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.
2018-06-04Revert "Run the sharing optimisation in beam_jump until fixpoint"José Valim
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.
2017-11-27beam_jump: Eliminate a repeated clauseBjörn Gustavsson
This clause seems to have been introduced in cac51274eb9a.
2017-08-14Apply the redundant test optimisation also in case of fall-throughMichał Muskała
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.
2017-08-14Replace labels instead of inserting duplicates in beam_jumpMichał Muskała
This makes other optimisations more efficient since we have less labels overall.
2017-08-14Enhance elimination of useless tests in beam_jumpMichał Muskała
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}
2017-08-13Run the sharing optimisation in beam_jump until fixpointMichał Muskała
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.
2017-01-12beam_jump: Add types and specsBjörn Gustavsson
2016-11-18Remove beam_boolBjörn Gustavsson
The guard optimizations in v3_kernel has removed the need for beam_bool.
2016-09-21beam_jump: Don't try to handle a label at the very endBjörn Gustavsson
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.
2016-09-21beam_jump: Simplify eliminate_fallthroughs/2Björn Gustavsson
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.
2016-08-11[ERL-209] Fix ambiguous_catch_try_state inconsistency errorBjörn Gustavsson
It is not safe to share code between 'catch' blocks.
2016-05-25beam_jump: Clean up handling of labels before func_infoBjörn Gustavsson
In complicated code with many indirect jumps to the func_info label, a label could get lost.
2016-03-15update copyright-yearHenrik Nord
2015-08-21Put 'try' in blocks to optimize allocation instructionsBjörn Gustavsson
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.
2015-06-18Change license text to APLv2Bruce Yinhe
2015-06-17compiler: Fix beam_bool pass for get_map_elementsBjörn-Egil Dahlberg
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
2015-05-21compiler: Use Maps instead of dict in beam_jumpBjörn-Egil Dahlberg
2015-05-21compiler: Use cerl_sets instead of gb_sets in beam_jumpBjörn-Egil Dahlberg
2015-04-22beam_jump: Replace use of lists:dropwhile/2 with a custom functionBjörn Gustavsson
The use of lists:dropwhile/2 is noticeable in the eprof results.
2015-02-23Merge branch 'bjorn/compiler/beam_jump-share'Björn Gustavsson
* bjorn/compiler/beam_jump-share: beam_jump: Don't jump into the middle of a 'try'
2015-02-20beam_jump: Eliminate pathologically slow compilationBjörn Gustavsson
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
2015-02-20beam_jump: Don't jump into the middle of a 'try'Björn Gustavsson
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
2015-01-12compiler: Remove get_map_elements label check in blocksBjörn-Egil Dahlberg
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.
2014-03-07Merge branch 'nox/maps-beam_jump-put_map'Björn-Egil Dahlberg
* nox/maps-beam_jump-put_map: Properly collect labels in put_map instructions in beam_jump
2014-03-06Properly collect labels in put_map instructions in beam_jumpAnthony Ramine
Reported-by: Ulf Norell
2014-03-05Properly check label use in get_map_elements in beam_jumpAnthony Ramine
Reported-by: Ulf Norell
2014-02-13compiler: Change map instructions for fetching valuesBjörn-Egil Dahlberg
* Combine multiple get values with one instruction * Combine multiple check keys with one instruction
2014-01-28compiler: Implement different instructions for => and :=Björn Gustavsson
2014-01-28Implement support for maps in the compilerBjörn Gustavsson
To make it possible to build the entire OTP system, also define dummys for the instructions in ops.tab.
2013-12-13Keep exit blocks in order when moving them in beam_jumpAnthony Ramine
This makes applying the pass a second time a no-op.
2013-01-25Update copyright yearsBjörn-Egil Dahlberg
2012-11-26beam_jump: Move bs_context_to_binary/1 + exit instructionBjörn Gustavsson
Generate slightly smaller and faster code.
2012-10-10Break apart tail-recursive call instructionsBjörn Gustavsson
Somewhat reduce the code bloat by eliminating special cases.
2012-10-10Rewrite select_val and select_tuple_arity to a select instructionBjörn Gustavsson
Eliminate some code bloat.