#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "rtl.h"#include "tm_p.h"#include "target.h"#include "regs.h"#include "flags.h"#include "sbitmap.h"#include "bitmap.h"#include "hash-table.h"#include "hard-reg-set.h"#include "basic-block.h"#include "expr.h"#include "diagnostic-core.h"#include "reload.h"#include "params.h"#include "df.h"#include "ira-int.h"
Data Structures | |
| struct | allocno_hard_regs |
| struct | allocno_hard_regs_node |
| struct | update_cost_record |
| struct | allocno_color_data |
| struct | allocno_hard_regs_hasher |
| struct | allocno_hard_regs_subnode |
| struct | update_cost_queue_elem |
| struct | coalesce_data |
Macros | |
| #define | ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a)) |
| #define | SORTGT(x, y) (((x) > (y)) ? 1 : -1) |
| #define | COST_HOP_DIVISOR 4 |
| #define | ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a)) |
| #define | STACK_GROWS_DOWNWARD 0 |
Typedefs | |
| typedef struct allocno_hard_regs * | allocno_hard_regs_t |
| typedef struct allocno_hard_regs_node * | allocno_hard_regs_node_t |
| typedef struct allocno_color_data * | allocno_color_data_t |
| typedef struct allocno_hard_regs_subnode * | allocno_hard_regs_subnode_t |
| typedef struct coalesce_data * | coalesce_data_t |
Macro Definition Documentation
| #define ALLOCNO_COALESCE_DATA | ( | a | ) | ((coalesce_data_t) ALLOCNO_ADD_DATA (a)) |
Macro to access the data concerning coalescing.
Referenced by coalesce_allocnos(), coalesced_pseudo_reg_slot_compare(), ira_reassign_conflict_allocnos(), and merge_allocnos().
| #define ALLOCNO_COLOR_DATA | ( | a | ) | ((allocno_color_data_t) ALLOCNO_ADD_DATA (a)) |
Macro to access the data concerning coloring.
Referenced by add_allocno_to_bucket(), bucket_allocno_compare_func(), put_allocno_into_bucket(), remove_allocno_from_bucket_and_push(), update_allocno_cost(), update_costs_from_allocno(), and update_left_conflict_sizes_p().
| #define COST_HOP_DIVISOR 4 |
When we traverse allocnos to update hard register costs, the cost divisor will be multiplied by the following macro value for each hop from given allocno to directly connected allocnos.
| #define SORTGT | ( | x, | |
| y | |||
| ) | (((x) > (y)) ? 1 : -1) |
Helper for qsort comparison callbacks - return a positive integer if X > Y, or a negative value otherwise. Use a conditional expression instead of a difference computation to insulate from possible overflow issues, e.g. X - Y < 0 for some X > 0 and Y < 0.
| #define STACK_GROWS_DOWNWARD 0 |
Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1.
Typedef Documentation
| typedef struct allocno_color_data* allocno_color_data_t |
See above.
| typedef struct allocno_hard_regs_node* allocno_hard_regs_node_t |
| typedef struct allocno_hard_regs_subnode* allocno_hard_regs_subnode_t |
See below.
| typedef struct allocno_hard_regs* allocno_hard_regs_t |
IRA allocation based on graph coloring. Copyright (C) 2006-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/.
| typedef struct coalesce_data* coalesce_data_t |
See below.
Function Documentation
|
static |
Add (or update info about) allocno hard registers with SET and COST.
|
static |
Add allocno hard registers HV (or its best approximation if it is not possible) to the forest on its level given by ROOTS.
Create a new node which contains nodes in hard_regs_node_vec.
Referenced by setup_allocno_hard_regs_subnode_index().
|
static |
Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket before the call.
References ALLOCNO_CLASS, ALLOCNO_COLOR_DATA, ALLOCNO_MODE, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, gcc_assert, allocno_color_data::in_graph_p, and ira_reg_class_max_nregs.
|
static |
Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according their priority. ALLOCNO should be not in a bucket before the call.
References bucket_allocno_compare_func(), NULL, remove_allocno_from_bucket_and_push(), and sort_bucket().
Referenced by bucket_allocno_compare_func().
|
static |
Add allocno hard registers node NEW_NODE to the forest on its level given by ROOTS.
References allocno_hard_regs_node::first, allocno_hard_regs_node::next, NULL, and allocno_hard_regs_node::prev.
|
static |
Sort allocnos according to the profit of usage of a hard register instead of memory for them.
If regs are equally good, sort by allocno numbers, so that the results of qsort leave nothing to chance.
References ALLOCNO_HARD_REGNO, ALLOCNO_MODE, ALLOCNO_OBJECT, FOR_EACH_OBJECT_CONFLICT, hard_regno_nregs, internal_flag_ira_verbose, ira_dump_file, NULL, and OBJECT_ALLOCNO.
|
static |
Sort hard regs according to their frequency of usage.
References allocno_hard_regs_node::next, NULL, and allocno_hard_regs_node::prev.
|
static |
Sort allocnos according to their priorities.
If regs are equally good, sort by allocnos, so that the results of qsort leave nothing to chance.
References ira_pressure_classes, and ira_loop_tree_node::reg_pressure.
|
static |
Try to assign a hard register (except for FORBIDDEN_REGS) to allocno A and return TRUE in the case of success.
If we found a hard register, modify the RTL for the pseudo register to show the hard register, and mark the pseudo register live.
|
inlinestatic |
Return the current spill priority of allocno A. The less the number, the more preferable the allocno for spilling.
|
inlinestatic |
Used for sorting allocnos for spilling.
|
static |
Used for sorting allocnos for spilling.
|
static |
This page contains functions used to find conflicts using allocno live ranges. Return TRUE if live ranges of allocnos A1 and A2 intersect. It is used to find a conflict for new allocnos or allocnos with the different allocno classes.
|
static |
Choose a hard register for allocno A. If RETRY_P is TRUE, it means that the function called from function `ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In this case some allocno data are not defined or updated and we should not touch these data. The function returns true if we managed to assign a hard register to the allocno.
To assign a hard register, first of all we calculate all conflict hard registers which can come from conflicting allocnos with already assigned hard registers. After that we find first free hard register with the minimal cost. During hard register cost calculation we take conflict hard register costs into account to give a chance for conflicting allocnos to get a better hard register in the future.
If the best hard register cost is bigger than cost of memory usage for the allocno, we don't assign a hard register to given allocno at all.
If we assign a hard register to the allocno, we update costs of the hard register for allocnos connected by copies to improve a chance to coalesce insns represented by the copies when we assign hard registers to the allocnos connected by the copies.
Take preferences of conflicting allocnos into account.
Reload can give another class so we need to check all
allocnos. Don't process the conflict allocno twice.
Take into account preferences of allocnos connected by copies to the conflict allocnos.
Take preferences of allocnos connected by copies into account.
We don't care about giving callee saved registers to allocnos no living through calls because call clobbered registers are allocated first (it is usual practice to put them first in REG_ALLOC_ORDER).
We need to save/restore the hard register in
epilogue/prologue. Therefore we increase the cost. We don't need updated costs anymore:
|
static |
Compare two allocnos to define which allocno should be pushed first into the coloring stack. If the return is a negative number, the allocno given by the first parameter will be pushed first. In this case such allocno has less priority than the second one and the hard register will be assigned to it after assignment to the second one. As the result of such assignment order, the second allocno has a better chance to get the best hard register.
Push pseudos requiring less hard registers first. It means that we will assign pseudos requiring more hard registers first avoiding creation small holes in free hard register file into which the pseudos requiring more hard registers can not fit.
References add_allocno_to_ordered_bucket(), ALLOCNO_ASSIGNED_P, ALLOCNO_COLOR_DATA, ALLOCNO_NUM, bitmap_bit_p, allocno_color_data::colorable_p, delete_allocno_from_bucket(), hard_reg_set_intersect_p(), allocno_color_data::in_graph_p, internal_flag_ira_verbose, ira_assert, ira_dump_file, ira_print_expanded_allocno(), NULL, OBJECT_ALLOCNO, allocno_color_data::profitable_hard_regs, and update_left_conflict_sizes_p().
Referenced by add_allocno_to_ordered_bucket().
|
static |
Calculate and return the cost of putting allocno A into memory.
Referenced by remove_allocno_from_bucket_and_push().
|
static |
Return number of registers needed to be saved and restored at function prologue/epilogue if we allocate HARD_REGNO to hold value of MODE.
|
static |
Return spill cost for pseudo-registers whose numbers are in array REGNOS (with a negative number as an end marker) for reload with given IN and OUT for INSN. Return also number points (through EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and the register pressure is high, number of references of the pseudo-registers (through NREFS), number of callee-clobbered hard-registers occupied by the pseudo-registers (through CALL_USED_COUNT), and the first hard regno occupied by the pseudo-registers (through FIRST_HARD_REGNO).
|
inlinestatic |
Return true if HARD_REGNO is ok for assigning to allocno A with PROFITABLE_REGS and whose objects have CONFLICT_REGS.
Checking only profitable hard regs.
|
static |
The major function for aggressive allocno coalescing. We coalesce only spilled allocnos. If some allocnos have been coalesced, we set up flag allocno_coalesced_p.
Collect copies.
For priority coloring we coalesce allocnos only with
the same allocno class not with intersected allocno
classes as it were possible. It is done for
simplicity. Coalesced copies, most frequently executed first.
Collect the rest of copies.
References ALLOCNO_COALESCE_DATA, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, ira_live_ranges_intersect_p(), nr, and OBJECT_LIVE_RANGES.
Referenced by coalesced_pseudo_reg_slot_compare().
|
static |
We have coalesced allocnos involving in copies. Coalesce allocnos further in order to share the same memory stack slot. Allocnos representing sets of allocnos coalesced before the call are given in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if some allocnos were coalesced in the function.
Coalesce non-conflicting spilled allocnos preferring most frequently used.
No coalescing: set up number for coalesced allocnos
represented by ALLOCNO.
|
static |
Return TRUE if there are conflicting allocnos from two sets of coalesced allocnos given correspondingly by allocnos A1 and A2. We use live ranges to find conflicts because conflicts are represented only for allocnos of the same allocno class and during the reload pass we coalesce allocnos for sharing stack memory slots.
|
static |
Sort pseudos according frequencies of coalesced allocno sets they belong to (putting most frequently ones first), and according to coalesced allocno set order numbers.
|
static |
Sort pseudos according their slot numbers (putting ones with smaller numbers first, or last when the frame pointer is not needed).
References ALLOCNO_ADD_DATA, ALLOCNO_COALESCE_DATA, ALLOCNO_NUM, bitmap_set_bit, coalesce_allocnos(), FOR_EACH_ALLOCNO, ira_allocate(), ira_allocate_bitmap(), ira_allocnos_num, ira_free_bitmap(), ira_regno_allocno_map, max_reg_num(), max_regno, and NULL.
|
static |
Add allocno hard registers nodes starting with the forest level given by FIRST which contains biggest set inside SET.
|
static |
Collect spilled allocnos representing coalesced allocno sets (the first coalesced allocno). The collected allocnos are returned through array SPILLED_COALESCED_ALLOCNOS. The function returns the number of the collected allocnos. The allocnos are given by their regnos in array PSEUDO_REGNOS of length N.
References ALLOCNO_FREQ, ALLOCNO_HARD_REGNO, ALLOCNO_NUM, ALLOCNO_REGNO, internal_flag_ira_verbose, ira_assert, ira_dump_file, MAX, NULL, and PSEUDO_REGNO_BYTES.
|
static |
Entry function doing color-based register allocation.
Referenced by draw_cfg_node_succ_edges().
|
static |
Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP.
We don't need updated costs anymore.
Put the allocnos into the corresponding buckets.
|
static |
Color the allocnos inside loop (in the extreme case it can be all of the function) given the corresponding LOOP_TREE_NODE. The function is called for each loop during top-down traverse of the loop tree.
Color all mentioned allocnos including transparent ones.
Process caps. They are processed just once.
Remove from processing in the next loop.
We don't need updated costs anymore:
Update costs of the corresponding allocnos (not caps) in the subloops.
Use hard register class here. ???
??? conflict costs
We don't need updated costs anymore:
We don't need updated costs anymore:
|
static |
The function is used to sort allocnos according to their execution frequencies.
If freqencies are equal, sort by copies, so that the results of qsort leave nothing to chance.
|
static |
Create and return allocno hard registers node containing allocno hard registers HV.
|
static |
Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before the call.
References bitmap_bit_p, df_get_live_in(), df_get_live_out(), EDGE_FREQUENCY, FOR_EACH_VEC_ELT, get_loop_exit_edges(), and ira_loop_tree_node::loop.
Referenced by bucket_allocno_compare_func().
|
static |
Initialize the common data for coloring and calls functions to do Chaitin-Briggs and regional coloring.
References ALLOCNO_ASSIGNED_P, ALLOCNO_CLASS, ALLOCNO_NUM, ALLOCNO_NUM_OBJECTS, bitmap_bit_p, FOR_EACH_ALLOCNO, and ira_allocate_bitmap().
|
static |
Return true if allocno A has empty profitable hard regs.
|
static |
Set up fields preorder_num starting with START_NUM in all allocno hard registers nodes in forest given by FIRST. Return biggest set PREORDER_NUM increased by 1.
References allocno_hard_regs_nodes_num, and allocno_hard_regs_node::preorder_num.
|
static |
This page contains a simple register allocator without usage of allocno conflicts. This is used for fast allocation for -O0. Do register allocation by not using allocno conflicts. It uses only allocno live ranges. The algorithm is close to Chow's priority coloring.
|
static |
Return allocno hard registers in the hash table equal to HV.
|
static |
Finalize data concerning allocno hard registers.
References allocno_hard_regs_node::check, allocno_hard_regs_node::first, hard_reg_set_size(), allocno_hard_regs_node::hard_regs, allocno_hard_regs_node::hard_regs_num, ira_allocate(), NULL, allocno_hard_regs::set, and allocno_hard_regs_node::used_p.
|
static |
Finish work with the forest of allocno hard registers nodes.
|
static |
Free tree of allocno hard registers nodes given by its ROOT.
References allocno_hard_regs_node::check, allocno_hard_regs_node::conflict_size, and node_check_tick.
|
static |
Deallocate data used by function update_costs_from_copies.
|
static |
Free memory allocated for all update cost records.
|
static |
Return allocno hard registers node which is a first common ancestor node of FIRST and SECOND in the forest.
|
static |
Build the forest of allocno hard registers nodes and assign each allocno a node from the forest.
We need to set up parent fields for right work of first_common_ancestor_node.
That is a temporary storage.
|
static |
Free memory for all records in LIST.
References ALLOCNO_CLASS, ALLOCNO_NUM, update_cost_queue_elem::check, update_cost_queue_elem::divisor, update_cost_queue_elem::from, update_cost_queue_elem::next, NULL, and update_cost_check.
Referenced by update_allocno_cost().
|
static |
Count all allocno hard registers nodes in tree ROOT.
|
inlinestatic |
Set up conflicting (through CONFLICT_REGS) for each object of allocno A and the start allocno profitable regs (through START_PROFITABLE_REGS). Remember that the start profitable regs exclude hard regs which can not hold value of mode of allocno A. This covers mostly cases when multi-register value should be aligned.
|
inlinestatic |
Try to remove the first element from update_cost_queue. Return false if the queue was empty, otherwise make (*ALLOCNO, *FROM, *DIVISOR) describe the removed element.
Referenced by update_costs_from_allocno().
|
staticread |
Return new update cost record with given params.
References NULL.
|
static |
We used Chaitin-Briggs coloring to assign as many pseudos as possible to hard registers. Let us try to improve allocation with cost point of view. This function improves the allocation by spilling some allocnos and assigning the freed hard registers to other allocnos if it decreases the overall allocation cost.
Clear counts used to process conflicting allocnos only once for each allocno.
Process each allocno and try to assign a hard register to it by spilling some its conflicting allocnos.
It means that assigning a hard register is not profitable
(we don't waste memory for hard register costs in this
case). Set up cost improvement for usage of each profitable hard
register for allocno A. There is no chance to improve the allocation cost by
assigning hard register to allocno A even without spilling
conflicting allocnos. Process each allocno conflicting with A and update the cost
improvement for profitable hard registers of A. To use a
hard register for A we need to spill some conflicting
allocnos and that creates penalty for the cost
improvement. We already processed this conflicting allocno
because we processed earlier another object of the
conflicting allocno. Now we choose hard register for A which results in highest
allocation cost improvement. We are in a situation when assigning any hard register to A
by spilling some conflicting allocnos does not improve the
allocation cost. Now spill conflicting allocnos which contain a hard register
of A when we assign the best chosen hard register to it. No intersection.
Assign the best chosen hard register to A.
We spilled some allocnos to assign their hard registers to other allocnos. The spilled allocnos are now in array 'sorted_allocnos'. There is still a possibility that some of the spilled allocnos can get hard registers. So let us try assign them hard registers again (just a reminder – function 'assign_hard_reg' assigns hard registers only if it is possible and profitable). We process the spilled allocnos with biggest benefit to get hard register first – see function 'allocno_cost_compare_func'.
|
static |
Initialize data concerning allocno hard registers.
References allocno_hard_regs::cost.
|
static |
Initiate update cost records.
|
static |
Allocate and initialize data necessary for function update_costs_from_copiess.
Referenced by ira_reuse_stack_slot().
|
static |
Insert allocno hard registers HV in the hash table (if it is not there yet) and return the value which in the table.
| bool ira_better_spill_reload_regno_p | ( | int * | regnos, |
| int * | other_regnos, | ||
| rtx | in, | ||
| rtx | out, | ||
| rtx | insn | ||
| ) |
Return TRUE if spilling pseudo-registers whose numbers are in array REGNOS is better than spilling pseudo-registers with numbers in OTHER_REGNOS for reload with given IN and OUT for INSN. The function used by the reload pass to make better register spilling decisions.
| void ira_color | ( | void | ) |
Entry function doing coloring.
Setup updated costs.
Referenced by split_live_ranges_for_shrink_wrap().
| void ira_debug_hard_regs_forest | ( | void | ) |
Print the allocno hard register forest to stderr.
| void ira_finish_assign | ( | void | ) |
Deallocate data used by assign_hard_reg.
| void ira_initiate_assign | ( | void | ) |
Allocate and initialize data necessary for assign_hard_reg.
Referenced by move_unallocated_pseudos(), and split_live_ranges_for_shrink_wrap().
| int ira_loop_edge_freq | ( | ) |
Return the frequency of exit edges (if EXIT_P) or entry from/to the loop given by its LOOP_NODE.
References ira_dump_file, and ira_print_expanded_allocno().
| void ira_mark_allocation_change | ( | ) |
This page contains code used by the reload pass to improve the final code. The function is called from reload to mark changes in the allocation of REGNO made by the reload. Remember that reg_renumber reflects the change result.
Reload changed class of the allocno.
| void ira_mark_memory_move_deletion | ( | ) |
This function is called when reload deletes memory-memory move. In this case we marks that the allocation of the corresponding allocnos should be not changed in future. Otherwise we risk to get a wrong code.
References ira_allocno_copy::first, and ira_allocno_copy::next_second_allocno_copy.
Referenced by maybe_fix_stack_asms().
| void ira_mark_new_stack_slot | ( | ) |
This is called by reload every time a new stack slot X with TOTAL_SIZE was allocated for REGNO. We store this info for subsequent ira_reuse_stack_slot calls.
| void ira_reassign_conflict_allocnos | ( | ) |
Try to assign hard registers to the unassigned allocnos and allocnos conflicting with them or conflicting with allocnos whose regno >= START_REGNO. The function is called after ira_flattening, so more allocnos (including ones created in ira-emit.c) will have a chance to get a hard register. We use simple assignment algorithm based on priorities.
References ALLOCNO_COALESCE_DATA, ALLOCNO_NUM, first, last, and coalesce_data::next.
Referenced by move_unallocated_pseudos().
| bool ira_reassign_pseudos | ( | int * | spilled_pseudo_regs, |
| int | num, | ||
| HARD_REG_SET | bad_spill_regs, | ||
| HARD_REG_SET * | pseudo_forbidden_regs, | ||
| HARD_REG_SET * | pseudo_previous_regs, | ||
| bitmap | spilled | ||
| ) |
Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are NUM of them) or spilled pseudos conflicting with pseudos in SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the allocation has been changed. The function doesn't use BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function is called by the reload pass at the end of each reload iteration.
Add pseudos which conflict with pseudos already in SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable to allocating in two steps as some of the conflicts might have a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS.
?!? This seems wrong.
Try to assign hard registers to pseudos from SPILLED_PSEUDO_REGS.
References ALLOCNO_CLASS, ALLOCNO_CLASS_COST, ALLOCNO_EXCESS_PRESSURE_POINTS_NUM, ALLOCNO_MEMORY_COST, ALLOCNO_MODE, ALLOCNO_NUM_OBJECTS, BLOCK_FOR_INSN, call_used_reg_set, find_regno_note(), hard_regno_nregs, ira_assert, ira_memory_move_cost, ira_regno_allocno_map, NULL_RTX, REG_FREQ_FROM_BB, REG_N_REFS(), REG_P, reg_renumber, REGNO, and TEST_HARD_REG_BIT.
| rtx ira_reuse_stack_slot | ( | int | regno, |
| unsigned int | inherent_size, | ||
| unsigned int | total_size | ||
| ) |
The function is called by reload and returns already allocated stack slot (if any) for REGNO with given INHERENT_SIZE and TOTAL_SIZE. In the case of failure to find a slot which can be used for REGNO, the function returns NULL.
It means that the pseudo was spilled in the reload pass, try to reuse a slot.
References initiate_cost_update(), ira_allocate(), ira_allocate_bitmap(), and ira_allocnos_num.
| void ira_sort_regnos_for_alter_reg | ( | int * | pseudo_regnos, |
| int | n, | ||
| unsigned int * | reg_max_ref_width | ||
| ) |
Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for subsequent assigning stack slots to them in the reload pass. To do this we coalesce spilled allocnos first to decrease the number of memory-memory move insns. This function is called by the reload.
Set up allocnos can be coalesced.
Initialize coalesce data for allocnos.
Sort regnos according frequencies of the corresponding coalesced allocno sets.
Collect allocnos representing the spilled coalesced allocno sets.
Assign stack slot numbers to spilled allocno sets, use smaller numbers for most frequently used coalesced allocnos. -1 is reserved for dynamic search of stack slots for pseudos spilled by the reload.
Sort regnos according the slot numbers.
|
static |
Merge two sets of coalesced allocnos given correspondingly by allocnos A1 and A2 (more accurately merging A2 set into A1 set).
References ALLOCNO_COALESCE_DATA, ALLOCNO_FREQ, ira_regno_allocno_map, and NULL.
|
static |
Move spill/restore code, which are to be generated in ira-emit.c, to less frequent points (if it is profitable) by reassigning some allocnos (in loop with subloops containing in another loop) to memory which results in longer live-range where the corresponding pseudo-registers will be in memory.
don't do the optimization because it can create copies and the reload pass can spill the allocno set by copy although the allocno will not get memory slot.
We have accumulated cost. To get the real cost of
allocno usage in the loop we should subtract costs of
the subloop allocnos.
|
static |
Pop the coloring stack and assign hard registers to the popped allocnos.
References ALLOCNO_NUM, ALLOCNO_UPDATED_CLASS_COST, and ALLOCNO_UPDATED_MEMORY_COST.
|
static |
Print hard reg set SET to F.
References allocno_hard_regs_node::first, last, allocno_hard_regs_node::next, NULL, allocno_hard_regs_node::prev, remove_unused_allocno_hard_regs_nodes(), and allocno_hard_regs_node::used_p.
Referenced by setup_allocno_hard_regs_nodes_parent().
|
static |
Print the allocno hard register forest to F.
References allocno_hard_regs_node::next, NULL, allocno_hard_regs_node::parent, and allocno_hard_regs_node::preorder_num.
|
static |
Print allocno hard register subforest given by ROOTS and its LEVEL to F.
Referenced by setup_allocno_hard_regs_nodes_parent().
|
static |
Output information about the loop given by its LOOP_TREE_NODE.
|
static |
Sort pseudos according their usage frequencies (putting most frequently ones first).
References count.
|
static |
Put allocno A onto the coloring stack without removing it from its bucket. Pushing allocno to the coloring stack can result in moving conflicting allocnos from the uncolorable bucket to the colorable one.
We will deal with the subwords individually.
|
static |
Push allocnos to the coloring stack. The order of allocnos in the stack defines the order for the subsequent coloring.
Calculate uncolorable allocno spill costs.
??? Remove cost of copies between the coalesced
allocnos.
References ALLOCNO_CLASS, ALLOCNO_CLASS_COST, ALLOCNO_MEMORY_COST, ALLOCNO_MODE, ALLOCNO_NREFS, ALLOCNO_NUM, floor_log2(), ira_assert, and ira_reg_class_max_nregs.
|
static |
Put all allocnos from colorable bucket onto the coloring stack.
References ALLOCNO_CLASS, internal_flag_ira_verbose, ira_dump_file, and NULL.
|
static |
Put ALLOCNO in a bucket corresponding to its number and size of its conflicting allocnos and hard registers.
References ALLOCNO_COLOR_DATA, ALLOCNO_HARD_REGNO, ALLOCNO_UPDATED_MEMORY_COST, and OBJECT_ALLOCNO.
|
inlinestatic |
Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless ALLOCNO is already in the queue, or has NO_REGS class.
|
static |
Put ALLOCNO onto the coloring stack and remove it from its bucket. The allocno is in the colorable bucket if COLORABLE_P is TRUE.
References ALLOCNO_COLOR_DATA, and calculate_allocno_spill_cost().
Referenced by add_allocno_to_ordered_bucket().
|
static |
Remove unused allocno hard registers nodes from forest given by its *ROOTS.
References allocno_hard_regs_subnode::left_conflict_size, allocno_hard_regs_subnode::left_conflict_subnodes_size, and allocno_hard_regs_subnode::max_node_impact.
Referenced by print_hard_reg_set().
|
static |
Restore costs of allocnos connected to ALLOCNO by copies as it was before updating costs of these allocnos from given allocno. This is a wise thing to do as if given allocno did not get an expected hard reg, using smaller cost of the hard reg for allocnos connected by copies to given allocno becomes actually misleading. Free all update cost records for ALLOCNO as we don't need them anymore.
References ALLOCNO_CLASS, ALLOCNO_MODE, AND_COMPL_HARD_REG_SET, COPY_HARD_REG_SET, ira_prohibited_class_mode_regs, and reg_class_contents.
|
static |
Set up number of available hard registers for allocno A.
Checking only profitable hard regs.
|
static |
Set up field parent as PARENT in all allocno hard registers nodes in forest given by FIRST.
References allocno_hard_regs::cost, allocno_hard_regs_node::first, allocno_hard_regs_node::hard_regs, HOST_WIDEST_INT_PRINT_DEC, allocno_hard_regs_node::next, NULL, allocno_hard_regs_node::preorder_num, print_hard_reg_set(), print_hard_regs_subforest(), and allocno_hard_regs::set.
|
static |
Setup arrays ALLOCNO_HARD_REGS_NODES and ALLOCNO_HARD_REGS_SUBNODE_INDEX.
References add_allocno_hard_regs_to_forest(), and ira_assert.
|
static |
Set up priorities for N allocnos in array CONSIDERATION_ALLOCNOS.
|
static |
Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM for coalesced allocno sets containing allocnos with their regnos given in array PSEUDO_REGNOS of length N.
|
static |
Set up left conflict sizes and left conflict subnodes sizes of hard registers subnodes of allocno A. Return TRUE if allocno A is trivially colorable.
We will deal with the subwords individually.
|
static |
Set up profitable hard registers for each allocno being colored.
Initial set up from allocno classes and explicitly conflicting hard regs.
Exclude hard regs already assigned for conflicting objects.
We can process the conflict allocno repeatedly with
the same result. Exclude too costly hard regs.
|
static |
Update live ranges of slot to which coalesced allocnos represented by ALLOCNO were assigned.
References ALLOCNO_HARD_REGNO, and ALLOCNO_MEMORY_COST.
|
static |
Return TRUE if coalesced allocnos represented by ALLOCNO has live ranges intersected with live ranges of coalesced allocnos assigned to slot with number N.
References ALLOCNO_CLASS, ALLOCNO_CLASS_COST, ALLOCNO_HARD_REG_COSTS, ALLOCNO_HARD_REGNO, ALLOCNO_MEMORY_COST, ira_assert, ira_regno_allocno_map, reg_renumber, and update_costs_from_copies().
|
static |
Sort bucket *BUCKET_PTR and return the result through BUCKET_PTR.
Referenced by add_allocno_to_ordered_bucket().
|
static |
Start a new cost-updating pass.
Referenced by update_allocno_cost().
|
static |
Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO. Return true if we really modified the cost.
References ALLOCNO_COLOR_DATA, update_cost_record::divisor, free_update_cost_record_list(), update_cost_record::hard_regno, update_cost_record::next, NULL, start_update_cost(), and update_costs_from_allocno().
|
static |
This function updates COSTS (decrease if DECR_P) for hard_registers of ACLASS by conflict costs of the unassigned allocnos connected by copies with allocnos in update_cost_queue. This update increases chances to remove some copies.
Probably 5 hops will be enough.
|
static |
Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected by copies to ALLOCNO to increase chances to remove some copies as the result of subsequent assignment. Record cost updates if RECORD_P is true.
References ALLOCNO_ASSIGNED_P, ALLOCNO_CLASS, ALLOCNO_COLOR_DATA, ALLOCNO_CONFLICT_HARD_REG_COSTS, ALLOCNO_COPIES, ALLOCNO_FREQ, ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS, update_cost_record::divisor, ira_allocno_copy::first, ira_allocno_copy::freq, gcc_unreachable, get_next_update_cost(), update_cost_record::hard_regno, ira_allocate_and_copy_costs(), ira_assert, ira_class_hard_reg_index, ira_class_hard_regs, ira_class_hard_regs_num, ira_reg_classes_intersect_p, mult, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, NULL, and ira_allocno_copy::second.
Referenced by update_allocno_cost().
|
static |
Update (decrease if DECR_P) the cost of allocnos connected to ALLOCNO through copies to increase chances to remove some copies as the result of subsequent assignment. ALLOCNO was just assigned to a hard register.
References ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, COPY_HARD_REG_SET, and OBJECT_TOTAL_CONFLICT_HARD_REGS.
Referenced by slot_coalesced_allocno_live_ranges_intersect_p().
|
static |
Decrease preferred ALLOCNO hard register costs and costs of allocnos connected to ALLOCNO through copy.
|
static |
Update current hard reg costs and current conflict hard reg costs for allocno A. It is done by processing its copies containing other allocnos already assigned.
References coalesce_data::first, coalesce_data::next, and coalesce_data::temp.
|
static |
Update left conflict sizes of hard registers subnodes of allocno A after removing allocno REMOVED_A with SIZE from the conflict graph. Return TRUE if A is trivially colorable.
References ALLOCNO_CLASS, ALLOCNO_CLASS_COST, ALLOCNO_COLOR_DATA, ALLOCNO_MEMORY_COST, ALLOCNO_MODE, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, ALLOCNO_UPDATED_HARD_REG_COSTS, AND_COMPL_HARD_REG_SET, CLEAR_HARD_REG_SET, COPY_HARD_REG_SET, ira_allocnos, ira_useful_class_mode_regs, NULL, OBJECT_TOTAL_CONFLICT_HARD_REGS, and allocno_color_data::profitable_hard_regs.
Referenced by bucket_allocno_compare_func().
Variable Documentation
|
static |
Array whose element value is TRUE if the corresponding hard register was already allocated for an allocno.
|
static |
Container for storing allocno data concerning coalescing.
|
static |
This page contains code to coalesce memory stack slots used by spilled allocnos. This results in smaller stack frame, better data locality, and in smaller code for some architectures like x86/x86_64 where insn size depends on address displacement value. On the other hand, it can worsen insn scheduling after the RA but in practice it is less important than smaller stack frames. TRUE if we coalesced some allocnos. In other words, if we got loops formed by members first_coalesced_allocno and next_coalesced_allocno containing more one allocno.
Container for storing allocno data concerning coloring.
|
static |
Hash table of unique allocno hard registers.
|
static |
Table preorder number of allocno hard registers node in the forest -> the allocno hard registers node.
|
static |
Number of allocno hard registers nodes in the forest.
Referenced by enumerate_allocno_hard_regs_nodes().
|
static |
Table (preorder number of allocno hard registers node in the forest, preorder number of allocno hard registers subnode) -> index of the subnode relative to the node. -1 if it is not a subnode.
|
static |
Container for hard regs subnodes of all allocnos.
|
static |
Definition of vector of allocno hard registers. Vector of unique allocno hard registers.
|
static |
Map: allocno number -> allocno priority.
|
static |
Vec representing the stack of allocnos used during coloring.
|
static |
This page contains the allocator based on the Chaitin-Briggs algorithm. Bucket of allocnos that can colored currently without spilling.
|
static |
This file contains code for regional graph coloring, spill/restore code placement optimization, and code helping the reload pass to do a better job. Bitmap of allocnos which should be colored.
|
static |
Bitmap of allocnos which should be taken into account during coloring. In general case it contains allocnos from coloring_allocno_bitmap plus other already colored conflicting allocnos.
|
static |
Used for finding allocno colorability to exclude repeated allocno processing and for updating preferencing to exclude repeated allocno processing during assignment.
|
static |
Definition of vector of allocno hard register nodes. Vector used to create the forest.
|
static |
Roots of the forest containing hard register sets can be assigned to allocnos.
|
static |
Used for finding a common ancestor of two allocno hard registers nodes in the forest. We use the current value of 'node_check_tick' to mark all nodes from one node to the top and then walking up from another node until we find a marked node.
It is also used to figure out allocno colorability as a mark that we already reset value of member 'conflict_size' for the forest node corresponding to the processed allocno.
Referenced by finish_allocno_hard_regs_nodes_tree().
|
static |
Bitmap used to prevent a repeated allocno processing because of coalescing.
|
static |
Usage cost and order number of coalesced allocno set to which given pseudo register belongs to.
|
static |
|
static |
Widest width in which each pseudo reg is referred to (via subreg). It is used for sorting pseudo registers.
|
static |
Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for given slot contains live ranges of coalesced allocnos assigned to given slot.
|
static |
All allocnos sorted according their priorities.
|
static |
Bucket of allocnos that might be not colored currently without spilling.
|
static |
The current number of allocnos in the uncolorable_bucket.
|
static |
The current value of update_costs_from_copies call count.
Referenced by free_update_cost_record_list().
|
static |
The first element in a queue of allocnos whose copy costs need to be updated. Null if the queue is empty.
|
static |
A pool of elements in the queue described by update_cost_queue. Elements are indexed by ALLOCNO_NUM.
|
static |
The last element in the queue described by update_cost_queue. Not valid if update_cost_queue is null.
|
static |
This page contains functions used to choose hard registers for allocnos. Pool for update cost records.
