#include "lra.h"#include "bitmap.h"#include "recog.h"#include "insn-attr.h"#include "insn-codes.h"#include "insn-config.h"#include "regs.h"
Go to the source code of this file.
Data Structures | |
| struct | lra_live_range |
| struct | lra_copy |
| struct | lra_reg |
| struct | lra_operand_data |
| struct | lra_insn_reg |
| struct | lra_static_insn_data |
| struct | lra_insn_recog_data |
| struct | target_lra_int |
Macros | |
| #define | lra_assert(c) gcc_checking_assert (c) |
| #define | LRA_MAX_INSN_RELOADS (MAX_RECOG_OPERANDS * 3) |
| #define | LRA_TEMP_CLOBBER_P(x) (RTL_FLAG_CHECK1 ("TEMP_CLOBBER_P", (x), CLOBBER)->unchanging) |
| #define | LRA_LOSER_COST_FACTOR 6 |
| #define | LRA_MAX_REJECT 600 |
| #define | LRA_MAX_CONSTRAINT_ITERATION_NUMBER 30 |
| #define | LRA_MAX_INHERITANCE_PASSES 2 |
| #define | this_target_lra_int (&default_target_lra_int) |
| #define | op_alt_data (this_target_lra_int->x_op_alt_data) |
Typedefs | |
| typedef struct lra_live_range * | lra_live_range_t |
| typedef struct lra_copy * | lra_copy_t |
| typedef struct lra_insn_recog_data * | lra_insn_recog_data_t |
Macro Definition Documentation
| #define lra_assert | ( | c | ) | gcc_checking_assert (c) |
Local Register Allocator (LRA) intercommunication header file. Copyright (C) 2010-2013 Free Software Foundation, Inc. Contributed by Vladimir Makarov vmakarov@redhat.com.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.
Referenced by bb_has_abnormal_call_pred(), init_insn_code_data_once(), initialize_lra_reg_info_element(), lra_former_scratch_operand_p(), lra_intersected_live_ranges_p(), lra_update_insn_recog_data(), ok_for_index_p_nonstrict(), process_alt_operands(), reverse_equiv_p(), setup_try_hard_regno_pseudos(), spill_pseudos(), split_reg(), substitute_pseudo(), and update_hard_regno_preference().
| #define LRA_LOSER_COST_FACTOR 6 |
Cost factor for each additional reload and maximal cost reject for insn reloads. One might ask about such strange numbers. Their values occurred historically from former reload pass.
Referenced by process_alt_operands().
| #define LRA_MAX_CONSTRAINT_ITERATION_NUMBER 30 |
Maximum allowed number of constraint pass iterations after the last spill pass. It is for preventing LRA cycling in a bug case.
| #define LRA_MAX_INHERITANCE_PASSES 2 |
The maximal number of inheritance/split passes in LRA. It should be more 1 in order to perform caller saves transformations and much less MAX_CONSTRAINT_ITERATION_NUMBER to prevent LRA to do as many as permitted constraint passes in some complicated cases. The first inheritance/split pass has a biggest impact on generated code quality. Each subsequent affects generated code in less degree. For example, the 3rd pass does not change generated SPEC2000 code at all on x86-64.
| #define LRA_MAX_INSN_RELOADS (MAX_RECOG_OPERANDS * 3) |
The parameter used to prevent infinite reloading for an insn. Each insn operands might require a reload and, if it is a memory, its base and index registers might require a reload too.
Referenced by split_reg().
| #define LRA_MAX_REJECT 600 |
Referenced by process_alt_operands().
| #define LRA_TEMP_CLOBBER_P | ( | x | ) | (RTL_FLAG_CHECK1 ("TEMP_CLOBBER_P", (x), CLOBBER)->unchanging) |
Whether the clobber is used temporary in LRA.
| #define op_alt_data (this_target_lra_int->x_op_alt_data) |
| #define this_target_lra_int (&default_target_lra_int) |
Typedef Documentation
| typedef struct lra_copy* lra_copy_t |
| typedef struct lra_insn_recog_data* lra_insn_recog_data_t |
| typedef struct lra_live_range* lra_live_range_t |
Function Documentation
| void debug | ( | lra_live_range & | ref | ) |
| void debug | ( | lra_live_range * | ptr | ) |
| bool lra_assign | ( | void | ) |
Entry function to assign hard registers to new reload pseudos starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling of old pseudos) and possibly to the old pseudos. The function adds what insns to process for the next constraint pass. Those are all insns who contains non-reload and non-inheritance pseudos with changed allocation.
Return true if we did not spill any non-reload and non-inheritance pseudos.
Setup insns to process on the next constraint pass.
We ignore spilled pseudos created on last inheritance pass because they will be removed.
Invalidate alternatives for insn should be processed.
|
inlinestatic |
Assign value of register FROM to TO.
Referenced by match_reload().
| void lra_clear_live_ranges | ( | void | ) |
Finish all live ranges.
| bool lra_coalesce | ( | void | ) |
The major function for aggressive pseudo coalescing of moves only if the both pseudos were spilled and not special reload pseudos.
Collect moves.
Coalesced copies, most frequently executed first.
We updated involved_insns_bitmap when doing the merge.
Coalesced move.
| int lra_constraint_offset | ( | int | , |
| enum | machine_mode | ||
| ) |
| void lra_constraints_finish | ( | void | ) |
Finalize the LRA constraint pass. It is done once per function.
| void lra_constraints_init | ( | void | ) |
Initiate the LRA constraint pass. It is done once per function.
| lra_live_range_t lra_copy_live_range_list | ( | lra_live_range_t | ) |
| void lra_create_copy | ( | int | , |
| int | , | ||
| int | |||
| ) |
| void lra_create_live_ranges | ( | bool | ) |
Referenced by setup_reg_spill_flag().
| rtx lra_create_new_reg_with_unique_value | ( | enum machine_mode | md_mode, |
| rtx | original, | ||
| enum reg_class | rclass, | ||
| const char * | title | ||
| ) |
Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL or of VOIDmode, use MD_MODE for the new reg. Initialize its register class to RCLASS. Print message about assigning class RCLASS containing new register name TITLE unless it is NULL. Use attributes of ORIGINAL if it is a register. The created register will have unique held value.
Referenced by change_class().
| void lra_debug_elim_table | ( | void | ) |
lra-elimination.c:
Print info about elimination table to stderr.
| void lra_debug_live_range_list | ( | lra_live_range_t | ) |
| void lra_debug_live_ranges | ( | void | ) |
Print live ranges of all pseudos to stderr.
References lra_reg::freq, lra_hard_reg_usage, lra_reg_info, and reg_renumber.
| void lra_debug_pseudo_live_ranges | ( | int | ) |
| void lra_delete_dead_insn | ( | rtx | ) |
| void lra_eliminate | ( | bool | ) |
| void lra_eliminate_reg_if_possible | ( | rtx * | ) |
| rtx lra_eliminate_regs_1 | ( | rtx | x, |
| enum machine_mode | mem_mode, | ||
| bool | subst_p, | ||
| bool | update_p, | ||
| bool | full_p | ||
| ) |
Scan X and replace any eliminable registers (such as fp) with a replacement (such as sp) if SUBST_P, plus an offset. The offset is a change in the offset between the eliminable register and its substitution if UPDATE_P, or the full offset if FULL_P, or otherwise zero.
MEM_MODE is the mode of an enclosing MEM. We need this to know how much to adjust a register for, e.g., PRE_DEC. Also, if we are inside a MEM, we are allowed to replace a sum of a hard register and the constant zero with the hard register, which we cannot do outside a MEM. In addition, we need to record the fact that a hard register is referenced outside a MEM.
Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST). That's used when we eliminate in expressions stored in notes.
First handle the case where we encounter a bare hard register
that is eliminable. Replace it with a PLUS.
If this is the sum of an eliminable register and a constant, rework
the sum. If the hard register is not eliminable, we are done since
the other operand is a constant. If this is part of an address, we want to bring any constant
to the outermost PLUS. We will do this by doing hard
register replacement in our operands and seeing if a constant
shows up in one of them.
Note that there is no risk of modifying the structure of the
insn, since we only get called for its operands, thus we are
either modifying the address inside a MEM, or something like
an address operand of a load-address insn. If this is the product of an eliminable hard register and a
constant, apply the distribute law and move the constant out
so that we have (plus (mult ..) ..). This is needed in order
to keep load-address insns valid. This case is pathological.
We ignore the possibility of overflow here. ... fall through ...
See comments before PLUS about handling MINUS.
If we have something in XEXP (x, 0), the usual case,
eliminate it. If this is a REG_DEAD note, it is not valid anymore.
Using the eliminated version could result in creating a
REG_DEAD note for the stack or frame pointer. ... fall through ...
Now do eliminations in the rest of the chain. If this was
an EXPR_LIST, this might result in allocating more memory than is
strictly needed, but it simplifies the code. We do not support elimination of a register that is modified.
elimination_effects has already make sure that this does not
happen. We do not support elimination of a hard register that is
modified. LRA has already make sure that this does not
happen. The only remaining case we need to consider here is
that the increment value may be an eliminable register. Our only special processing is to pass the mode of the MEM to our
recursive call and copy the flags. While we are here, handle this
case more efficiently. Handle insn_list USE that a call to a pure function may generate.
Process each of our operands recursively. If any have changed, make a copy of the rtx.
References elim_table::from_rtx, elim_table::offset, plus_constant(), elim_table::previous_offset, elim_table::to, and elim_table::to_rtx.
Referenced by assign_mem_slot().
| void lra_final_code_change | ( | void | ) |
Final change of pseudos got hard registers into the corresponding hard registers and removing temporary clobbers.
Remove clobbers temporarily created in LRA. We don't need them anymore and don't want to waste compiler time processing them in a few subsequent passes.
Remove an useless move insn but only involving
pseudos as some subsequent optimizations are based on
that move insns involving originally hard registers
are preserved. IRA can generate move insns involving
pseudos. It is better remove them earlier to speed
up compiler a bit. It is also better to do it here
as they might not pass final RTL check in LRA,
(e.g. insn moving a control register into
itself).
References delete_insn(), and lra_invalidate_insn_data().
| bool lra_former_scratch_p | ( | int | ) |
Referenced by assign_stack_slot_num_and_sort_pseudos(), process_alt_operands(), and remove_pseudos().
| void lra_free_copies | ( | void | ) |
Free all copies.
| lra_copy_t lra_get_copy | ( | int | ) |
| int lra_get_elimination_hard_regno | ( | int | ) |
|
inlinestatic |
Return info about INSN. Set up the info if it is not done yet.
Check that we did not change insn without updating the insn info.
Referenced by push_insns().
|
read |
Referenced by setup_try_hard_regno_pseudos().
|
inlinestatic |
Return the hard register which given pseudo REGNO assigned to. Negative value means that the register got memory or we don't know allocation yet.
Referenced by assign_stack_slot_num_and_sort_pseudos(), remove_pseudos(), reverse_equiv_p(), and strip_subreg().
| void lra_inheritance | ( | void | ) |
Entry function for inheritance/split pass.
Form a EBB starting with BB.
Remember that the EBB head and tail can change in
inherit_in_ebb.
References dump_insn_slim(), INSN_UID, lra_dump_file, and lra_set_insn_deleted().
| unsigned int lra_insn_stack_length | ( | void | ) |
Return the current size of the insn stack.
| bool lra_intersected_live_ranges_p | ( | lra_live_range_t | , |
| lra_live_range_t | |||
| ) |
Referenced by add_pseudo_to_slot().
| void lra_invalidate_insn_data | ( | rtx | ) |
Referenced by lra_final_code_change(), and lra_invalidate_insn_data().
| void lra_invalidate_insn_regno_info | ( | rtx | ) |
Referenced by lra_set_regno_unique_value().
| void lra_live_ranges_finish | ( | void | ) |
Finish live ranges data once per function.
| void lra_live_ranges_init | ( | void | ) |
Initialize live ranges data once per function.
| lra_live_range_t lra_merge_live_ranges | ( | lra_live_range_t | , |
| lra_live_range_t | |||
| ) |
| bool lra_need_for_spills_p | ( | void | ) |
Return true if we need to change some pseudos into memory.
| rtx lra_pop_insn | ( | void | ) |
Take the last-inserted insns off the stack and return it.
References sloc::insn.
| void lra_print_live_range_list | ( | FILE * | , |
| lra_live_range_t | |||
| ) |
Referenced by insert_move_for_subreg().
| void lra_push_insn | ( | rtx | ) |
Referenced by init_elim_table(), remove_pseudos(), and setup_insn_reg_info().
| void lra_push_insn_and_update_insn_regno_info | ( | rtx | ) |
| void lra_push_insn_by_uid | ( | unsigned | int | ) |
|
inlinestatic |
Return true if register content is equal to VAL with OFFSET.
| void lra_set_insn_deleted | ( | rtx | ) |
Referenced by lra_inheritance().
| lra_insn_recog_data_t lra_set_insn_recog_data | ( | rtx | ) |
| void lra_set_regno_unique_value | ( | int | ) |
| void lra_set_used_insn_alternative | ( | rtx | , |
| int | |||
| ) |
Referenced by init_elim_table(), and remove_pseudos().
| void lra_set_used_insn_alternative_by_uid | ( | int | , |
| int | |||
| ) |
| void lra_setup_reg_renumber | ( | int | , |
| int | , | ||
| bool | |||
| ) |
| void lra_setup_reload_pseudo_preferenced_hard_reg | ( | int | regno, |
| int | hard_regno, | ||
| int | profit | ||
| ) |
Update the preference of HARD_REGNO for pseudo REGNO by PROFIT.
Keep the 1st hard regno as more profitable.
| void lra_spill | ( | void | ) |
Change spilled pseudos into memory or spill hard regs. Put changed insns on the constraint stack (these insns will be considered on the next constraint pass). The changed insns are all insns in which pseudos were changed.
We do not want to assign memory for former scratches.
Sort regnos according their usage frequencies. If we have a stack frame, we must align it now. The stack size may be a part of the offset computation for register elimination.
| bool lra_undo_inheritance | ( | void | ) |
Entry function for undoing inheritance/split transformation. Return true if we did any RTL change in this pass.
If the original pseudo changed its allocation, just
removing inheritance is dangerous as for changing
allocation we used shorter live-ranges.
Clear restore_regnos.
|
inlinestatic |
Update insn operands which are duplication of NOP operand. The insn is represented by its LRA internal representation ID.
References lra_reg::offset, and lra_reg::val.
Referenced by push_insns().
| void lra_update_dups | ( | lra_insn_recog_data_t | , |
| signed char * | |||
| ) |
| lra_insn_recog_data_t lra_update_insn_recog_data | ( | rtx | ) |
Referenced by init_elim_table().
| void lra_update_insn_regno_info | ( | rtx | ) |
Referenced by init_elim_table(), and invalidate_insn_data_regno_info().
|
inlinestatic |
Process operator duplications in insn with ID. We do it after the operands processing. Generally speaking, we could do this probably simultaneously with operands processing because a common practice is to enumerate the operators after their operands.
|
inlinestatic |
Update offset from pseudos with VAL by INCR.
Variable Documentation
| struct target_lra_int default_target_lra_int |
This page contains code dealing LRA insn info (or in other words LRA internal insn representation).
| int lra_coalesce_iter |
The current iteration (1, 2, ...) of the coalescing pass.
| int lra_constraint_iter |
The current iteration number of this LRA pass.
| int lra_constraint_iter_after_spill |
The current iteration number of this LRA pass after the last spill pass.
| int lra_constraint_new_insn_uid_start |
First UID of insns generated before a new spill pass.
| int lra_constraint_new_regno_start |
Start of reload pseudo regnos before the new spill pass.
Referenced by bb_has_abnormal_call_pred(), spill_for(), and update_lives().
| int lra_curr_reload_num |
The number of emitted reload insns so far.
| FILE* lra_dump_file |
File used for output of LRA debug information.
Referenced by coalescable_pseudo_p(), lra_get_insn_regs(), lra_inheritance(), lra_init_elimination(), process_alt_operands(), reg_in_class_p(), remove_pseudos(), spill_pseudos(), swap_operands(), update_hard_regno_preference(), and valid_address_p().
| int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER] |
Accumulated execution frequency of all references for each hard register.
Referenced by lra_debug_live_ranges(), and update_hard_regno_preference().
| int lra_inheritance_iter |
Current number of inheritance/split iteration.
| bitmap_head lra_inheritance_pseudos |
Inheritance pseudo regnos before the new spill pass.
Map INSN_UID -> the insn recog data (NULL if unknown).
| int lra_insn_recog_data_len |
The current length of the following array.
| int lra_live_max_point |
Build live ranges for pseudos. Copyright (C) 2010-2013 Free Software Foundation, Inc. Contributed by Vladimir Makarov vmakarov@redhat.com.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. This file contains code to build pseudo live-ranges (analogous structures used in IRA, so read comments about the live-ranges there) and other info necessary for other passes to assign hard-registers to pseudos, coalesce the spilled pseudos, and assign stack memory slots to spilled pseudos. Program points are enumerated by numbers from range 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more program points than insns. Program points are places in the program where liveness info can be changed. In most general case (there are more complicated cases too) some program points correspond to places where input operand dies and other ones correspond to places where output operands are born.
Referenced by finish_live_range_start_chains(), remove_some_program_points_and_update_live_ranges(), and update_lives().
| int lra_live_range_iter |
The number of the current live range pass.
| int lra_new_regno_start |
Start of pseudo regnos before the LRA.
Referenced by match_reload().
| HARD_REG_SET lra_no_alloc_regs |
LRA (local register allocator) driver and LRA utilities. Copyright (C) 2010-2013 Free Software Foundation, Inc. Contributed by Vladimir Makarov vmakarov@redhat.com.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. The Local Register Allocator (LRA) is a replacement of former reload pass. It is focused to simplify code solving the reload pass tasks, to make the code maintenance easier, and to implement new perspective optimizations.
The major LRA design solutions are: o division small manageable, separated sub-tasks o reflection of all transformations and decisions in RTL as more as possible o insn constraints as a primary source of the info (minimizing number of target-depended macros/hooks)
In brief LRA works by iterative insn process with the final goal is to satisfy all insn and address constraints: o New reload insns (in brief reloads) and reload pseudos might be generated; o Some pseudos might be spilled to assign hard registers to new reload pseudos; o Changing spilled pseudos to stack memory or their equivalences; o Allocation stack memory changes the address displacement and new iteration is needed.
Here is block diagram of LRA passes:
————— | Undo inheritance for | ————— | Memory-memory | | spilled pseudos, | | New (and old) | | move coalesce |<—| splits for pseudos got |<– | pseudos | ————— | the same hard regs, | | assignment | Start | | and optional reloads | ————— | | ———————— ^ V | —————- | ———– V | Update virtual | | | Remove |—-> ————>| register | | | scratches | ^ | displacements | | ----------- | ---------------- | | | | | V New | —————- No ———— pseudos ——————- | Spilled pseudo | change |Constraints:| or insns | Inheritance/split | | to memory |<——-| RTL |———>| transformations | | substitution | | transfor- | | in EBB scope | —————- | mations | ——————- | ------------
V
| Hard regs substitution, | | devirtalization, and |——> Finish | restoring scratches got |
| memory |
To speed up the process: o We process only insns affected by changes on previous iterations; o We don't use DFA-infrastructure because it results in much slower compiler speed than a special IR described below does; o We use a special insn representation for quick access to insn info which is always synchronized with the current RTL; o Insn IR is minimized by memory. It is divided on three parts: o one specific for each insn in RTL (only operand locations); o one common for all insns in RTL with the same insn code (different operand attributes from machine descriptions); o one oriented for maintenance of live info (list of pseudos). o Pseudo data: o all insns where the pseudo is referenced; o live info (conflicting hard regs, live ranges, # of references etc); o data used for assigning (preferred hard regs, costs etc).
This file contains LRA driver, LRA utility functions and data, and code for dealing with scratches. Hard registers currently not available for allocation. It can changed after some hard registers become not eliminable.
Referenced by lra_intersected_live_ranges_p(), process_alt_operands(), and substitute_pseudo().
| bitmap_head lra_optional_reload_pseudos |
Reload pseudo regnos before the new assignmnet pass which still can be spilled after the assinment pass as memory is also accepted in insns for the reload pseudos.
| int* lra_point_freq |
The start of the above vector elements.
| struct lra_reg* lra_reg_info |
References to the common info about each register.
Common info about each register.
Referenced by add_pseudo_to_slot(), bb_has_abnormal_call_pred(), create_live_range_start_chains(), init_lives(), lra_debug_live_ranges(), lra_intersected_live_ranges_p(), lra_update_dups(), next_program_point(), process_alt_operands(), remove_pseudos(), remove_some_program_points_and_update_live_ranges(), setup_try_hard_regno_pseudos(), spill_pseudos(), update_hard_regno_preference(), and update_lives().
| bool lra_reg_spill_p |
True if we should try spill into registers of different classes instead of memory.
Referenced by remove_pseudos().
| bool lra_risky_transformations_p |
True if we substituted equiv which needs checking register allocation correctness because the equivalent value contains allocatable hard registers or when we restore multi-register pseudo.
| bitmap_head lra_split_regs |
Split regnos before the new spill pass.
| bitmap_head lra_subreg_reload_pseudos |
Pseudo regnos used for subreg reloads before the new assignment pass. Such pseudos still can be spilled after the assinment pass.
Referenced by insert_move_for_subreg().
| int lra_undo_inheritance_iter |
This page contains code to undo failed inheritance/split transformations. Current number of iteration undoing inheritance/split.
