aboutsummaryrefslogtreecommitdiffstats
path: root/lib/compiler
AgeCommit message (Collapse)Author
2019-02-11Merge pull request #2134 from bjorng/bjorn/compiler/propagate-noneBjörn Gustavsson
beam_ssa_type: Propagate the 'none' type from calls
2019-02-11beam_ssa_type: Propagate the 'none' type from callsBjörn Gustavsson
Consider this pseudo code: f(...) -> Val = case Expr of ... -> ... ; ... -> ... ; ... -> my_abort(something_went_wrong) end, %% Here follows code that uses Val. . . . my_abort(Reason) -> throw({error,Reason}). The first two clauses in the case will probably provide some information about the type of the variable `Var`, information that would be useful for optimizing the code that follows the case. However, the third clause would ruin everything. The call to `my_abort/1` could return anything, and thus `Val` could also have any type. 294d66a295f6 introduced module-level type analysis, which will in general keep track of the return type of a local function call. However, it does not improve the optimization for this specific function. When a function never returns, that is, when its type is `none`, it does not propagate the `none` type, but instead pretends that the return type is `any`. This commit extends the handling of functions that don't return to properly handle the `none` type. Any instructions that directly follows the function that does not return will be discarded, and the call will be rewritten to a tail-recursive call. For this specific example, it means that the type for `Val` deduced from the first two clauses will be retained and can be used for optimizing the code after the case.
2019-02-07Merge pull request #2135 from bjorng/bjorn/compiler/optimize-dominatorsBjörn Gustavsson
Optimize ssa_opt_sink for huge functions
2019-02-06Optimize ssa_opt_sink for huge functionsBjörn Gustavsson
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.
2019-02-05beam_ssa_type: Track the types of tuple elementsJohn Högberg
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]>
2019-02-04beam_ssa_type: Infer types based on the result of #b_switch{}John Högberg
2019-02-04beam_ssa_opt: Fix function name printing in sub-pass crash dumpJohn Högberg
2019-02-04beam_validator: Remove unreachable case clauseJohn Högberg
2019-02-04Merge pull request #2126 from bjorng/bjorn/compiler/compilation-speedBjörn Gustavsson
Reduce compilation times
2019-02-01inline_SUITE: Don't start a slave nodeBjörn Gustavsson
A long time ago there was a good idea to run compiled code in a slave node. Nowadays, not so much.
2019-02-01Correct test_lib:is_cloned_mod/1Björn Gustavsson
test_lib:is_cloned_mod(inline_SUITE) would return true.
2019-02-01sys_core_fold_lists: Propagate annotations in expansion of lists functionsBjörn Gustavsson
There could be a warning with a `no_file` atom instead of filename and line number.
2019-02-01Parallelize compile_SUITE:bc_options/1Björn Gustavsson
2019-02-01Remove the optimized_guard/1 test caseBjörn Gustavsson
With the new SSA code passes, the optimized_guard/1 test case has become really bad at finding unnecessary `and` and `or` instructions.
2019-02-01Make helper functions tail-recursiveBjörn Gustavsson
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.
2019-02-01Optimize beam_ssa:def_used/2Björn Gustavsson
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.
2019-02-01Prefer map syntax and guard BIFs over the maps modulesBjörn Gustavsson
Avoiding calls usually reduces the size of the stack frame and reduces register shuffling.
2019-02-01beam_ssa_type: Optimize calculation of variables that are only used onceBjörn Gustavsson
2019-02-01Use gb_sets:delete/2 instead of gb_sets:delete_any/2Björn Gustavsson
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.
2019-02-01Speed up beam_ssa_dead when there are many sequential blocksBjörn Gustavsson
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
2019-02-01Optimize ssa_opt_sink when nothing can be sunkBjörn Gustavsson
Compilation will be much faster if there are many blocks, but no get_tuple_element instructions. Reported-by: Michał Muskała
2019-02-01Merge pull request #2122 from bjorng/bjorn/compiler/fix-beam_exceptBjörn Gustavsson
Fix internal consistency failure caused by beam_except
2019-01-31Fix internal consistency failure caused by beam_exceptBjörn Gustavsson
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}}.
2019-01-31Merge branch 'maint'Björn Gustavsson
* maint: Eliminate bogus warning when using tuple calls
2019-01-30Eliminate bogus warning when using tuple callsBjörn Gustavsson
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
2019-01-30Merge pull request #2115 from bjorng/bjorn/compiler/opt-function_clauseBjörn Gustavsson
Enhance optimization of function_clause exceptions
2019-01-29Add lib/compiler/scripts/smokeBjörn Gustavsson
Add `lib/compiler/scripts/smoke` for smoke testing the compiler (that is, test that the compiler does not crash during compilation). `smoke` first installs Elixir and mix. It then uses `mix` to download a number of `hex` packages and compile them. We don't intend to use `smoke` in our daily builds or Travis, but to run it manually during compiler development.
2019-01-29Enhance optimization of function_clause exceptionsBjörn Gustavsson
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.
2019-01-29Merge branch 'john/compiler/refactor-validator-type-mgmt'John Högberg
* john/compiler/refactor-validator-type-mgmt: beam_validator: Add explicit assertions for fragile terms beam_validator: Refactor type management
2019-01-29Merge pull request #2112 from bjorng/bjorn/compiler/compilation-speedBjörn Gustavsson
Speed up the compiler when compiling the idna package
2019-01-29Merge pull request #2111 from bjorng/bjorn/compiler/not-problem/ERL-840Björn Gustavsson
Fix problems compiling Scalaris
2019-01-28beam_validator: Add explicit assertions for fragile termsJohn Högberg
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.
2019-01-28beam_validator: Refactor type managementJohn Högberg
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.
2019-01-28beam_except: Eliminate unsafe function_clause translationBjörn Gustavsson
The translation from `error(function_clause, Args)` to a jump to the `func_info` label is not safe if there is a stack frame.
2019-01-28Speed up beam_ssa_deadBjörn Gustavsson
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.
2019-01-28Speed up ssa_opt_merge_blocksBjörn Gustavsson
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.
2019-01-28Fix crash in beam_ssa_typeBjörn Gustavsson
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
2019-01-28beam_ssa_opt: Make phase/4 tail-recursiveBjörn Gustavsson
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
2019-01-25Merge branch 'john/compiler/trim-ignore-annos'John Högberg
* john/compiler/trim-ignore-annos: beam_trim: Ignore type annotations
2019-01-25Merge branch 'john/compiler/misc-validator-fixes/ERL-832'John Högberg
* john/compiler/misc-validator-fixes/ERL-832: Make the beam_validator smarter again, again
2019-01-25Merge pull request #2106 from bjorng/bjorn/compiler/fewer-movesBjörn Gustavsson
Reduce redundant moves and register shuffling
2019-01-24Make the beam_validator smarter again, againJohn Högberg
The fix in f9ea85611faca82c7494449ddb8bcb1ef1d194cb didn't consider that the tested register could be aliased.
2019-01-24beam_trim: Ignore type annotationsJohn Högberg
The type annotations inserted by beam_ssa_type and beam_ssa_bsm would inadvertently disable stack trimming, as unknown instructions are considered unsafe.
2019-01-24Introduce optimizations of tail phisBjörn Gustavsson
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
2019-01-24Merge pull request #2100 from jhogberg/john/compiler/module-type-optimizationJohn Högberg
Apply type optimizations across local function calls
2019-01-24compiler: Introduce module-level type optimizationJohn Högberg
This commit lets the type optimization pass work across functions, tracking return and argument types to eliminate redundant tests.
2019-01-24beam_ssa_opt: Add a scaffold for module-level optimizationsJohn Högberg
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.
2019-01-24Reduce redundant moves and register shufflingBjörn Gustavsson
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.)
2019-01-23beam_ssa_pre_codegen: Use lists:splitwith/2 for separating phi nodesBjörn Gustavsson
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.
2019-01-21beam_ssa_opt: Don't ruin arguments of bs_match/skipJohn Högberg
If the match instruction was already marked as a skip, we'd ruin its argument list.