aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler/src/v3_kernel.erl
AgeCommit message (Collapse)Author
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-24Remove match context reuse annotations from core/kernel passesJohn Högberg
The upcoming beam_ssa_bsm pass makes this redundant.
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-18Update copyright yearHenrik Nord
2018-03-24Avoid overflowing the atom tableBjörn Gustavsson
Use integer variable names instead of atoms in v3_core, sys_core_fold, and v3_kernel to avoid overflowing the atom table. It is a deliberate design decision to calculate the first free integer variable name (in sys_core_fold and v3_kernel) instead of somehow passing it from one pass to another. I don't want that kind of dependency between compiler passes. Also note that the next free variable name is not easily available after running the inliner.
2018-03-14v3_kernel: Stop ensuring one return value in #k_try{}Björn Gustavsson
For unclear reasons, v3_kernel attempts to guarantee that #k_try{} always has at least one return value, even if it will never be used. I said "attempts", because the handler block that is executed when an exception is caught does not have the same guarantee. That means that if an exception is thrown, the return value will not actually be set. In practice, however, this is not a problem for the existing code generator (v3_codegen). The generated code will still be safe. If we are to rewrite the code generator to generate an SSA-based intermediate format, this inconsistency *will* cause problems when creating phi nodes. While at it, also remove an unecessary creation of new variables in generation of #k_try_enter{}.
2017-12-08Use the new syntax for retrieving stack tracesBjörn Gustavsson
2017-12-04v3_kernel: Make #k_break{} consistent with the code it followsBjörn Gustavsson
v3_kernel could generate a #k_break{} with only one variable, even if the preceding code and succeding code expected more than one value. It happened to work anyway because the value returned from the break was not actually used.
2017-10-27Eliminate the v3_life passBjörn Gustavsson
The v3_life pass does not do enough to be worth being its own pass. Essentially it does two things: * Calculates life-time information starting from the annotations that v3_kernel provides. That part can be moved into v3_codegen. * Rewrites the Kernel Erlang records to similar plain tuples (for example, #k_cons{hd=Hd,tl=Tl} is rewritten to {cons,Hd,Tl}). That rewriting is not needed and can be eliminated.
2017-10-21Optimize matching of literals for single-valued typesBjörn Gustavsson
If a type only has one clause and if the pattern is literal, the matching can be done more efficiently by directly comparing with the literal. Example: find(String, "") -> String; find(String, <<>>) -> String; find(String, SearchPattern) -> . . . Without this optimization, the relevant part of the code would look this: {test,bs_start_match2,{f,3},2,[{x,1},0],{x,2}}. {test,bs_test_tail2,{f,4},[{x,2},0]}. return. {label,3}. {test,is_nil,{f,4},[{x,1}]}. return. {label,4}. . . . That is, if {x,1} is a binary, a match context will be built to test whether {x,1} is an empty binary. With the optimization, the code will look this: {test,is_eq_exact,{f,3},[{x,1},{literal,<<>>}]}. return. {label,3}. {test,is_nil,{f,4},[{x,1}]}. return. {label,4}. . . .
2017-06-13v3_kernel: Keep orddicts sortedBjörn Gustavsson
2017-05-04Update copyright yearRaimo Niskanen
2017-04-25Store abstract code in the Dbgi chunkJosé Valim
The new Dbgi chunk returns data in the following format: {debug_info_v1, Backend, Data} This allows compilers to store the debug info in different formats. In order to retrieve a particular format, for instance, Erlang Abstract Format, one may invoke: Backend:debug_info(erlang_v1, Module, Data, Opts) Besides introducing the chunk above, this commit also: * Changes beam_lib:chunk(Beam, [:abstract_code]) to read from the new Dbgi chunk while keeping backwards compatibility with old .beams * Adds the {debug_info, {Backend, Data}} option to compile:file/2 and friends that are stored in the Dbgi chunk. This allows the debug info encryption mechanism to work across compilers * Improves dialyzer to work directly on Core Erlang, allowing languages that do not have the Erlang Abstract Format to be dialyzer as long as they emit the new chunk and their backend implementation is available Backwards compatibility is kept across the board except for those calling beam_lib:chunk(Beam, ["Abst"]), as the old chunk is no longer available. Note however the "Abst" chunk has always been optional. Future OTP versions may remove parsing the "Abst" chunk altogether from beam_lib once Erlang 19 and earlier is no longer supported. The current Dialyzer implementation still supports earlier .beam files and such may also be removed in future versions.
2016-12-02Merge branch 'egil/compiler/opt-maps-pattern-matching/OTP-14072'Björn-Egil Dahlberg
* egil/compiler/opt-maps-pattern-matching/OTP-14072: compiler: Add regression tests compiler: Optimize maps pattern matching compiler: Allow for unaligned match argument in value groups
2016-12-01compiler: Optimize maps pattern matchingBjörn-Egil Dahlberg
2016-11-18v3_kernel: Generate optimized code for guardsBjörn Gustavsson
The compiler produces poor code for complex guard expressions with andalso/orelse. Here is an example from the filename module: -define(IS_DRIVELETTER(Letter),(((Letter >= $A) andalso (Letter =< $Z)) orelse ((Letter >= $a) andalso (Letter =< $z)))). skip_prefix(Name, false) -> Name; skip_prefix([L, DrvSep|Name], DrvSep) when ?IS_DRIVELETTER(L) -> Name; skip_prefix(Name, _) -> Name. beam_bool fails to simplify the code for the guard, leaving several 'bif' instructions: {function, skip_prefix, 2, 49}. {label,48}. {line,[{location,"filename.erl",187}]}. {func_info,{atom,filename},{atom,skip_prefix},2}. {label,49}. {test,is_ne_exact,{f,52},[{x,1},{atom,false}]}. {test,is_nonempty_list,{f,52},[{x,0}]}. {get_list,{x,0},{x,2},{x,3}}. {test,is_nonempty_list,{f,52},[{x,3}]}. {get_list,{x,3},{x,4},{x,5}}. {bif,'=:=',{f,52},[{x,1},{x,4}],{x,6}}. {test,is_ge,{f,50},[{x,2},{integer,65}]}. {bif,'=<',{f,52},[{x,2},{integer,90}],{x,7}}. {test,is_eq_exact,{f,51},[{x,7},{atom,false}]}. {test,is_ge,{f,50},[{x,2},{integer,97}]}. {bif,'=<',{f,52},[{x,2},{integer,122}],{x,7}}. {jump,{f,51}}. {label,50}. {move,{atom,false},{x,7}}. {label,51}. {bif,'=:=',{f,52},[{x,7},{atom,true}],{x,7}}. {test,is_eq_exact,{f,52},[{x,6},{atom,true}]}. {test,is_eq_exact,{f,52},[{x,7},{atom,true}]}. {move,{x,5},{x,0}}. return. {label,52}. return. We can add optimizations of guard tests to v3_kernel to achive a better result: {function, skip_prefix, 2, 49}. {label,48}. {line,[{location,"filename.erl",187}]}. {func_info,{atom,filename},{atom,skip_prefix},2}. {label,49}. {test,is_ne_exact,{f,51},[{x,1},{atom,false}]}. {test,is_nonempty_list,{f,51},[{x,0}]}. {get_list,{x,0},{x,2},{x,3}}. {test,is_nonempty_list,{f,51},[{x,3}]}. {get_list,{x,3},{x,4},{x,5}}. {test,is_eq_exact,{f,51},[{x,1},{x,4}]}. {test,is_ge,{f,51},[{x,2},{integer,65}]}. {test,is_lt,{f,50},[{integer,90},{x,2}]}. {test,is_ge,{f,51},[{x,2},{integer,97}]}. {test,is_ge,{f,51},[{integer,122},{x,2}]}. {label,50}. {move,{x,5},{x,0}}. return. {label,51}. return. Looking at the STDLIB application, there were 112 lines of BIF calls in guards that beam_bool failed to convert to test instructions. This commit eliminates all those BIF calls. Here is how I counted the instructions: $ PATH=$ERL_TOP/bin:$PATH erlc -I ../include -I ../../kernel/include -S *.erl $ grep "bif,'[=<>]" *.S | grep -v f,0 dets.S: {bif,'=:=',{f,547},[{x,4},{atom,read_write}],{x,4}}. dets.S: {bif,'=:=',{f,547},[{x,5},{atom,saved}],{x,5}}. dets.S: {bif,'=:=',{f,589},[{x,5},{atom,read}],{x,5}}. . . . $ grep "bif,'[=<>]" *.S | grep -v f,0 | wc 112 224 6765 $
2016-09-29compiler: Allow for unaligned match argument in value groupsBjörn-Egil Dahlberg
At this stage in match compilation we are allowed to change the alignment of arguments and constructors as long as they are the same aligned in the same group.
2016-09-29Merge branch 'josevalim/compiler/at-var/PR-1081/OTP-13924'Björn Gustavsson
* josevalim/compiler/at-var/PR-1081/OTP-13924: Use @ in variable names generated by core and kernel
2016-09-26Use @ in variable names generated by core and kernelJosé Valim
The previous variable names can be generated by projects like LFE and Elixir, leading to possible conflicts. Our first to choice to solve such conflicts was to use $ but that's not a valid variable name in core. Therefore we picked @ which is currently supported and still reduces the chance of conflicts.
2016-09-21Simplify handling of internal BIFsBjörn Gustavsson
Do a simpler translation of internal BIFs. While we are it, also remove the dummy values of Index and Uniq from the make_fun internal operation.
2016-09-21v3_life: Eliminate special handling of guardsBjörn Gustavsson
Remove the special handling #k_try{} in guards in v3_life. If we introduce a new #k_protected{} record in v3_kernel, v3_life no longer needs to know whether it is processing guards or bodies.
2016-05-25Merge branch 'kostis/compiler/v3_kernel/eta-conversion'Björn Gustavsson
* kostis/compiler/v3_kernel/eta-conversion: v3_kernel: Fix typo in comment
2016-05-23v3_kernel: Fix typo in commentKostis Sagonas
2016-05-09compiler: Let module_info(attributes) skip more attributesHans Bolinder
'callback' and 'optional_callbacks' are no longer wild attributes.
2016-04-14v3_kernel: Construct literal lists properlyBjörn Gustavsson
Use cerl:make_list/1 instead of a home-made make_list/1 to ensure that literal lists are constructed as literals. In a future release, we would like to forbid in the loader construction of literal lists using instructions like: put_list {atom,a} [] Dst The proper way is: move {literal,[a]} {x,0} Also update the comment about "put_list Const [] Dst" in ops.tab.
2016-02-17compiler: Update the compiler to handle typed record fieldsBjörn Gustavsson
2015-11-11v3_kernel: Speed up compilation of modules with many funsBjörn Gustavsson
Using a map to store the number of free variables for funs instead of an orddict will speed up the v3_kernel pass for modules with a huge number of funs (such as NBAP-PDU-Contents in the asn1 test suite).
2015-06-18Change license text to APLv2Bruce Yinhe
2015-05-21compiler: Use cerl_sets instead of sets in v3_kernelBjörn-Egil Dahlberg
2015-04-22v3_kernel: Optimize subst_vsub/3Björn Gustavsson
Profiling shows that subst_vsub/3 dominates the running time. It is therefore worthwhile optimizing it.
2015-03-09v3_core: Add is_map tests before map instructionsBjörn Gustavsson
If we have a sequence of put_map_* instructions operating on the same map, it will be more efficient if we can have one is_map/2 instruction before put_map_* instructions, so that each put_map_* does not need to test whether the argument is a map.
2015-02-12Eliminate use of core_lib:literal_value/1Björn Gustavsson
Essentially, core_lib:literal_value/1 became useless when literals were introduced in R12. Since we always create #c_literal{} records whenever possible, literal_value/1 would *only* succeed when it was passed a #c_literal{} argument.
2015-01-29Move grouping of map constructions from v3_core to v3_kernelBjörn Gustavsson
When translating a function with map construction: f(A) -> B = b, C = c, #{A=>1,B=>2,C=>3}. v3_core would break apart the map construction into three parts because of the way the map instructions in BEAM work -- variable keys need to be in their own instruction. In the example, constant propagation will turn two of the keys to literal keys. But the initial breaking apart will not be undone, so there will still be three map constructions: 'f'/1 = fun (_cor0) -> let <_cor3> = ~{::<_cor0,1>}~ in let <_cor4> = ~{::<'b',2>|_cor3}~ in ~{::<'c',3>|_cor4}~ It would be possible to complicate the sys_core_fold pass to regroup map operations so that we would get: 'f'/1 = fun (_cor0) -> let <_cor3> = ~{::<_cor0,1>}~ in ~{::<'b',2>,::<'c',3>|_cor3}~ A simpler way that allows to simplify the translation is to skip the grouping in v3_core and translate the function to: 'f'/1 = fun (_cor0) -> ~{::<_cor0,1>,::<'b',2>,::<'c',3>}~ We will then let v3_kernel do the grouping while translating from Core Erlang to Kernel Erlang.
2014-08-22compiler: Use variables in Map kernel passBjörn-Egil Dahlberg
2014-03-25compiler: Variable keys are not allowed in MapsBjörn-Egil Dahlberg
No need to check for variables in Map keys.
2014-03-17compiler: Change #c_map{var} to #c_map{arg}Björn-Egil Dahlberg
Not only variables are allowed as arguments, the name should reflect that. Change cerl Map argument interface * cerl:map_arg/1 is more suitable then cerl:map_val/1 in this case.
2014-03-17compiler: Validate Map srcBjörn-Egil Dahlberg
Reject all expressions that are known to fail. Emit 'badarg' for those expressions. Ex. []#{ a => 1} Is not a valid map update expression.
2014-03-04Properly order Kernel code for maps with mixed pairsAnthony Ramine
The Kernel instructions were not properly ordered when compiling maps with complex values mixed in assoc and exact pairs. 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-02-10Merge branch 'egil/compiler/maps-fix-codegen'Björn-Egil Dahlberg
* egil/compiler/maps-fix-codegen: compiler: Fix codegen multiple updates for Maps erts,compiler: Correct and amend tests for Maps
2014-02-07compiler: Fix codegen multiple updates for MapsBjörn-Egil Dahlberg
This fixes an error on multiple updates optimization for map pairs. The error was introduced with moving to term order in Maps. This also fixes an error where register life time was lost for values and could result in erroneuos values being emitted in for map pairs. Simplified v3_codegen by moving multiple update optimizations to v3_kernel.
2014-02-07Merge branch 'hsv/using_lists_droplast'Henrik Nord
* hsv/using_lists_droplast: lib/mnesia/test/ - Replace reverse(tl(reverse(L))) with lists:droplast/1 lib/ssh - Replace reverse(tl(reverse(L))) with lists:droplast/1 lib/wx - Replace reverse(tl(reverse(L))) with lists:droplast/1 Use lists:droplast/1 in orber/orber_interceptors.erl Import and use lists:droplast/1 in v3_core/v3_kernel OTP-11678 OTP-11677
2014-01-29compiler: Squash #c_map_pair_*{} to #c_map_pair{}Björn-Egil Dahlberg
Simplify compiler internals and parsing of core format.
2014-01-29compiler: Squash #k_map_pair_*{} to #k_map_pair{}Björn-Egil Dahlberg
Simplify compiler internals for kernel passes.
2014-01-28compiler: Rename map pattern to proper nameBjörn-Egil Dahlberg
2014-01-28Pass the map pair operators through to the v3_codegen passBjörn Gustavsson
2014-01-28compiler: Implement support for exact Op in MapsBjörn-Egil Dahlberg
The syntax is handled upto v3_kernel where it is reduced to previous behaviour for construction and updates. Meaning, the ':=' operator is handled exactly as '=>' operator.
2014-01-28compiler: Fix multiple same keysBjörn-Egil Dahlberg
2014-01-28compiler: Handle literals, not just atoms, as keys in mapsBjörn-Egil Dahlberg
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.