aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/regalloc
AgeCommit message (Collapse)Author
2017-03-23HiPE: Fix off-by-one in register allocatorsMagnus Lång
hipe_regalloc_loop considers SpillLimit to be an inclusive lower bound, the allocators considered it to be an exclusive lower bound. The allocators are changed to also consider it an inclusive lower bound. This caused the register allocators to occasionally spill the first "unspillable" temporary. This caused a failure in a newly added assertion when hipe-compiling dets_v9 on x86.
2017-03-16hipe: Add pseudo_spill_f?move instructionsMagnus Lång
These pseudo instructions are added to all backends and allow spill slot to spill slot move coalescing in a clean way. They have regular move semantics, but contain an additional scratch register to be used if both source and destination are spilled, and can not be move coalesced. Additionally, a register allocator callback Target:is_spill_move(Instr, Context) is added which allows the spill slot allocators to check for these instructions and try to coalesce the spill slots the two temporaries are allocated to.
2017-03-16hipe: Add range splitter range_splitMagnus Lång
hipe_range_split is a complex live range splitter, more sophisticated thatn hipe_restore_reuse, but still targeted specifically at temporaries forced onto stack by being live over call instructions. hipe_range_split partitions the control flow graph at call instructions, like hipe_regalloc_prepass. Splitting decisions are made on a per partition and per temporary basis. There are three different ways in which hipe_range_split may choose to split a temporary in a program partition: * Mode1: Spill the temp before calls, and restore it after them * Mode2: Spill the temp after definitions, restore it after calls * Mode3: Spill the temp after definitions, restore it before uses To pick which of these should be used for each temp×partiton pair, hipe_range_split uses a cost function. The cost is simply the sum of the cost of all expected stack accesses, and the cost for an individual stack access is based on the probability weight of the basic block that it resides in. This biases the range splitter so that it attempts moving stack accesses from a functions hot path to the cold path. hipe_bb_weights is used to compute the probability weights. mode3 is effectively the same as what hipe_restore_reuse does. Because of this, hipe_restore_reuse reuses the analysis pass of hipe_restore_reuse in order to compute the minimal needed set of spills and restores. The reason mode3 was introduced to hipe_range_split rather than simply composing it with hipe_restore_reuse (by running both) is that such a composition resulted in poor register allocation results due to insufficiently strong move coalescing in the register allocator. The cost function heuristic has a couple of tuning knobs: * {range_split_min_gain, Gain} (default: 1.1, range: [0.0, inf)) The minimum proportional improvement that the cost of all stack accesses to a temp must display in order for that temp to be split. * {range_split_mode1_fudge, Factor} (default: 1.1, range: [0.0, inf)) Costs for mode1 are multiplied by this factor in order to discourage it when it provides marginal benefits. The justification is that mode1 causes temps to be live for longest, thus leading to higher register pressure. * {range_split_weight_power, Factor} (default: 2, range: (0.0, inf)) Adjusts how much effect the basic block weights have on the cost of a stack access. A stack access in a block with weight 1.0 has cost 1.0, a stack access in a block with weight 0.01 has cost 1/Factor. Additionally, the option range_split_weights chooses whether the basic block weights are used at all. In the case that the input is very big, hipe_range_split automatically falls back to hipe_restore_reuse only in order to keep compile times under control. Note that this is not only because of hipe_range_split being slow, but also due to the resulting program being slow to register allocate, and is not as partitionable by hipe_regalloc_prepass. hipe_restore_reuse, on the other hand, does not affect the programs partitionability. The hipe_range_split pass is controlled by a new option ra_range_split. ra_range_split is added to o2, and ra_restore_reuse is disabled in o2.
2017-03-16hipe: Add branch prediction accessor ra callbacksMagnus Lång
Adds a new register allocator callback Target:branch_preds(Instr, Context) which, for a control flow instruction Instr, returns a list of tuples {Target, Probability} for each label name Target that Instr may branch to. Probability is a float between 0.0 and 1.0 and corresponds to the predicted probability that control flow branches to the corresponding target. The probabilities may sum to at most 1.0 (rounding errors aside). Note that a sum less than 1.0 is valid.
2017-03-16hipe: Add range splitter restore_reuseMagnus Lång
hipe_restore_reuse is a simplistic range splitter that splits temps that are forced onto the stack by being live over call instructions. In particular, it attempts to avoid cases where there are several accesses to such stack allocated temps in straight-line code, uninterrupted by any calls. In order to achieve this it splits temps between just before the first access(es) and just after the last access(es) in such straight-line code groups. The hipe_restore_reuse pass is controlled by a new option ra_restore_reuse. ra_restore_reuse is added to o1.
2017-03-16hipe: Add basic range splitting ra callbacksMagnus Lång
In addition to the temporary name rewriting that hipe_regalloc_prepass does, range splitters also need to be able to insert move instructions, as well as inserting new basic blocks in the control flow graph. The following four callbacks are added for that purpose: * Target:mk_move(Src, Dst, Context) Returns a move instruction from the temporary (not just register number) Src to Dst. * Target:mk_goto(Label, Context) Returns a unconditional control flow instruction that branches to the label with name Label. * Target:redirect_jmp(Instr, ToOld, ToNew, Context) Modifies the control flow instruction Instr so that any control flow that would go to a label with name ToOld instead goes to the label with name ToNew. * Target:new_label(Context) Returns a fresh label name that does not belong to any existing block in the current function, and is to be used to create a new basic block in the control flow graph by calling Target:update_bb/4 with this new name.
2017-03-16hipe: Extract disjoint sets to its own moduleMagnus Lång
2017-03-06hipe_x86: CleanupMagnus Lång
2016-11-23Remove Emacs timestamp markersRichard Carlsson
2016-11-23Correct copyright on remaining hipe filesRichard Carlsson
2016-09-05hipe: Refactor ra callbacks to accept context argMagnus Lång
This allows us to pass around the context data that hipe_regalloc_prepass needs cleanly, without using process dictionary or parameterised modules (like it was previous to this change).
2016-09-05hipe: Reuse liveness between regalloc iterationsMagnus Lång
This is sound because the liveness data structure only stores liveness info at basic block boundaries, and the rewrites that happen in TargetSpecific:check_and_rewrite/2 preserves all existing definitions and uses, and all new liveness intervals, belonging to newly introduced temporaries, are always local to a basic block, and thus do not show up in the liveout or livein sets for the basic block.
2016-09-05hipe_regalloc_prepass: Change splitting heuristicMagnus Lång
The division into an initial pass that may introduce temps, and following passes that must not forces us to make the same heuristic decision during each of these passes. Thus, the splitting heuristic can't be based on the number of temporaries -- at least without excluding temporaries above SpillLimit.
2016-09-02hipe: Make sure prepass temps are below SpillLimitMagnus Lång
If temps introduced by hipe_regalloc_prepass end up above SpillLimit, the register allocators will not spill them. This constraint is unnecessarily limiting the allocators and might theoretically lead to unallocatable programs (more temps above SpillLimit alive at a time than there are physical registers).
2016-09-02hipe_regalloc_prepass: Rename coloring collisionsMagnus Lång
2016-09-02hipe_ppc: Add code rewrite RA callbacksMagnus Lång
These will not only be useful for hipe_regalloc_prepass, but also, after the introduction of a mk_move/2 (or similar) callback, for the purpose of range splitting. Since the substitution needed to case over all the instructions, a new module, hipe_ppc_subst, was introduced to the ppc backend.
2016-09-02hipe_sparc: Add code rewrite RA callbacksMagnus Lång
These will not only be useful for hipe_regalloc_prepass, but also, after the introduction of a mk_move/2 (or similar) callback, for the purpose of range splitting. Since the substitution needed to case over all the instructions, a new module, hipe_sparc_subst, was introduced to the sparc backend.
2016-09-02hipe_arm: Add code rewrite RA callbacksMagnus Lång
These will not only be useful for hipe_regalloc_prepass, but also, after the introduction of a mk_move/2 (or similar) callback, for the purpose of range splitting. Since the substitution needed to case over all the instructions, a new module, hipe_arm_subst, was introduced to the arm backend.
2016-09-02hipe_x86: Add code rewrite RA callbacksMagnus Lång
These will not only be useful for hipe_regalloc_prepass, but also, after the introduction of a mk_move/2 (or similar) callback, for the purpose of range splitting. Since the substitution needed to case over all the instructions, a new module, hipe_x86_subst, was introduced to the x86 backend. Due to differences in the 'jtab' field of a #jmp_switch{} between x86 and amd64, it regrettably needed to be duplicated to hipe_amd64_subst.
2016-09-02hipe: Remove defun_to_cfg/1 RA callbackMagnus Lång
Now that all backends do register allocation on a CFG directly and define the defun_to_cfg/1 callback as the identity function, it can be removed.
2016-09-02Add new sanity assertion to hipe_regalloc_prepassMagnus Lång
As the just_as_good_as assertion was loosened with the `NowRegs >= CheckRegs` check, it no longer verified that hipe_regalloc_prepass had not incorrectly labeled a temp as unallocatable. We add that behaviour back.
2016-09-02hipe: clean up unnecessary catchesMagnus Lång
2016-09-02hipe: Add IG partitioning to hipe_regalloc_prepassMagnus Lång
2016-09-02hipe: Add hipe_regalloc_prepassMagnus Lång
hipe_regalloc_prepass speeds up register allocation by spilling any temp that is live over a call (which clobbers all register). In order to detect these, a new function was added to the target interface; defines_all_alloc/1, that takes an instruction and returns a boolean.
2016-08-30hipe_sparc: Minimise CFG<->linear conversionsMagnus Lång
Now, there will only ever be a single Linear->CFG conversion, just after lowering from RTL, and only ever a single CFG->Linear conversion, just before the finalise pass. Both of these now happen in hipe_sparc_main.
2016-08-30hipe_ppc: Minimise CFG<->linear conversionsMagnus Lång
Now, there will only ever be a single Linear->CFG conversion, just after lowering from RTL, and only ever a single CFG->Linear conversion, just before the finalise pass. Both of these now happen in hipe_ppc_main.
2016-08-30hipe_arm: Minimise CFG<->linear conversionsMagnus Lång
Now, there will only ever be a single Linear->CFG conversion, just after lowering from RTL, and only ever a single CFG->Linear conversion, just before the finalise pass. Both of these now happen in hipe_arm_main.
2016-08-30hipe: Reuse liveness info for spillminMagnus Lång
For x86, additionally reuse liveness from float LSRA for the GP LSRA.
2016-08-30hipe_x86: Minimise CFG<->linear conversionsMagnus Lång
Most x86 passes were either linearise(pass(to_cfg(Code))) or trivially rewritable to process a CFG. This saves a great deal of time and memory churn when compiling large programs. Now, there will only ever be a single Linear->CFG conversion, just after lowering from RTL, and only ever a single CFG->Linear conversion, just before the finalise pass. Both of these now happen in hipe_x86_main.
2016-08-30hipe_x86: LSRA for SSE2Magnus Lång
There is little point offering LSRA for x86 if we're still going to call hipe_graph_coloring_regalloc for the floats. In particular, all allocators except LSRA allocates an N^2 interference matrix, making them unusable for really large functions.
2016-07-11hipe_vectors: Change implementation to 'array'Magnus Lång
The 'array' module is highly optimised for the hipe_vectors use-case, and seems to perform slightly better than the gb_trees implementation. Also, we remove the completely unnecessary hipe_vectors.hrl header.
2016-05-31Add compiler option -Werror to MakefilesKostis Sagonas
and correct the name of another, erroneously spelt, option in the process.
2016-03-15update copyright-yearHenrik Nord
2015-06-18Change license text to APLv2Bruce Yinhe
2014-02-26Substitude uses of lists:reverse(L1) ++ L2 with lists:reverse(L1, L2)Kostis Sagonas
2014-02-23Deprecate pre-defined built-in typesHans Bolinder
The types array(), dict(), digraph(), gb_set(), gb_tree(), queue(), set(), and tid() have been deprecated. They will be removed in OTP 18.0. Instead the types array:array(), dict:dict(), digraph:graph(), gb_set:set(), gb_tree:tree(), queue:queue(), sets:set(), and ets:tid() can be used. (Note: it has always been necessary to use ets:tid().) It is allowed in OTP 17.0 to locally re-define the types array(), dict(), and so on. New types array:array/1, dict:dict/2, gb_sets:set/1, gb_trees:tree/2, queue:queue/1, and sets:set/1 have been added.
2013-06-12Merge branch 'maint'Björn-Egil Dahlberg
2013-06-12Update copyright yearsBjörn-Egil Dahlberg
2013-04-19Remove the "coding: utf-8" comment from all Erlang source filesHans Bolinder
2013-03-10Use correct type nameKostis Sagonas
2013-01-09Prepare OTP files for Unicode as default encodingHans Bolinder
2012-06-05Update to work with whitespace in exec pathLukas Larsson
OTP-10106 OTP-10107
2012-03-30Update copyright yearsBjörn-Egil Dahlberg
2012-02-28Make hipe hipe-compiled w/ --enable-native-libsPatrik Nyblom
2011-09-29Update copyright yearsBjörn-Egil Dahlberg
2011-09-15Fix misspelling of successfulTuncer Ayaz
2011-03-11Update copyright yearsBjörn-Egil Dahlberg
2010-09-24Cleanup and small fixes in hipe filesKostis Sagonas
2010-01-26OTP-8343 The documentation is now possible to build in an open sourceLars G Thorsen
environment after a number of bugs are fixed and some features are added in the documentation build process. - The arity calculation is updated. - The module prefix used in the function names for bif's are removed in the generated links so the links will look like http://www.erlang.org/doc/man/erlang.html#append_element-2 instead of http://www.erlang.org/doc/man/erlang.html#erlang:append_element-2 - Enhanced the menu positioning in the html documentation when a new page is loaded. - A number of corrections in the generation of man pages (thanks to Sergei Golovan) - Moved some man pages to more apropriate sections, pages in section 4 moved to 5 and pages in 6 moved to 7. - The legal notice is taken from the xml book file so OTP's build process can be used for non OTP applications.
2009-11-20The R13B03 release.OTP_R13B03Erlang/OTP