GCC Middle and Back End API Reference
ira-color.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "target.h"
#include "rtl.h"
#include "tree.h"
#include "predict.h"
#include "df.h"
#include "memmodel.h"
#include "tm_p.h"
#include "insn-config.h"
#include "regs.h"
#include "ira.h"
#include "ira-int.h"
#include "reload.h"
#include "cfgloop.h"
Include dependency graph for ira-color.cc:

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


#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))


typedef struct allocno_hard_regsallocno_hard_regs_t
typedef struct allocno_hard_regs_nodeallocno_hard_regs_node_t
typedef struct allocno_color_dataallocno_color_data_t
typedef struct allocno_hard_regs_subnodeallocno_hard_regs_subnode_t
typedef struct coalesce_datacoalesce_data_t


static allocno_hard_regs_t find_hard_regs (allocno_hard_regs_t hv)
static allocno_hard_regs_t insert_hard_regs (allocno_hard_regs_t hv)
static void init_allocno_hard_regs (void)
static allocno_hard_regs_t add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
static void finish_allocno_hard_regs (void)
static int allocno_hard_regs_compare (const void *v1p, const void *v2p)
static allocno_hard_regs_node_t create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
static void add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots, allocno_hard_regs_node_t new_node)
static void add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots, allocno_hard_regs_t hv)
static void collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first, HARD_REG_SET set)
static void setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first, allocno_hard_regs_node_t parent)
static allocno_hard_regs_node_t first_common_ancestor_node (allocno_hard_regs_node_t first, allocno_hard_regs_node_t second)
static void print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
DEBUG_FUNCTION void debug_hard_reg_set (HARD_REG_SET set)
static void print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots, int level)
static void print_hard_regs_forest (FILE *f)
void ira_debug_hard_regs_forest (void)
static void remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
static int enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first, allocno_hard_regs_node_t parent, int start_num)
static void setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
static int get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
static void form_allocno_hard_regs_nodes_forest (void)
static void finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
static void finish_allocno_hard_regs_nodes_forest (void)
static bool setup_left_conflict_sizes_p (ira_allocno_t a)
static bool update_left_conflict_sizes_p (ira_allocno_t a, ira_allocno_t removed_a, int size)
static bool empty_profitable_hard_regs (ira_allocno_t a)
static void setup_profitable_hard_regs (void)
static struct update_cost_recordget_update_cost_record (int hard_regno, int divisor, struct update_cost_record *next)
static void free_update_cost_record_list (struct update_cost_record *list)
static void finish_update_cost_records (void)
static void initiate_cost_update (void)
static void finish_cost_update (void)
static void start_update_cost (void)
static void queue_update_cost (ira_allocno_t allocno, ira_allocno_t start, ira_allocno_t from, int divisor)
static bool get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start, ira_allocno_t *from, int *divisor)
static bool update_allocno_cost (ira_allocno_t allocno, int hard_regno, int update_cost, int update_conflict_cost)
static bool object_conflicts_with_allocno_p (ira_object_t obj, ira_allocno_t a)
static bool allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
static void update_costs_from_allocno (ira_allocno_t allocno, int hard_regno, int divisor, bool decr_p, bool record_p)
static void update_costs_from_prefs (ira_allocno_t allocno)
static void update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
static void update_conflict_allocno_hard_prefs (ira_allocno_t allocno)
static void restore_costs_from_copies (ira_allocno_t allocno)
static void update_conflict_hard_regno_costs (int *costs, enum reg_class aclass, bool decr_p)
static void get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p, HARD_REG_SET *conflict_regs, HARD_REG_SET *start_profitable_regs)
static bool check_hard_reg_p (ira_allocno_t a, int hard_regno, HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
static int calculate_saved_nregs (int hard_regno, machine_mode mode)
ira_allocno_t ira_soft_conflict (ira_allocno_t a1, ira_allocno_t a2)
static void spill_soft_conflicts (ira_allocno_t a, bitmap allocnos_to_spill, HARD_REG_SET soft_conflict_regs, int hregno)
static bool assign_hard_reg (ira_allocno_t a, bool retry_p)
static ira_allocno_t get_cap_member (ira_allocno_t a)
static bool allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
static int copy_freq_compare_func (const void *v1p, const void *v2p)
static bool allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
static void merge_threads (ira_allocno_t t1, ira_allocno_t t2)
static void form_threads_from_copies (int cp_num)
static void form_threads_from_bucket (ira_allocno_t bucket)
static void form_threads_from_colorable_allocno (ira_allocno_t a)
static void init_allocno_threads (void)
static int allocno_spill_priority (ira_allocno_t a)
static void add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
static int bucket_allocno_compare_func (const void *v1p, const void *v2p)
static void sort_bucket (ira_allocno_t *bucket_ptr, int(*compare_func)(const void *, const void *))
static void add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
static void delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
static void push_allocno_to_stack (ira_allocno_t a)
static void remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
static void push_only_colorable (void)
int ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
static int calculate_allocno_spill_cost (ira_allocno_t a)
static int allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
static int allocno_spill_sort_compare (const void *v1p, const void *v2p)
static void push_allocnos_to_stack (void)
static void pop_allocnos_from_stack (void)
static void setup_allocno_available_regs_num (ira_allocno_t a)
static void put_allocno_into_bucket (ira_allocno_t allocno)
static void setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
static int allocno_cost_compare_func (const void *v1p, const void *v2p)
static int allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
static void improve_allocation (void)
static int allocno_priority_compare_func (const void *v1p, const void *v2p)
static void color_allocnos (void)
static void print_loop_title (ira_loop_tree_node_t loop_tree_node)
static void color_pass (ira_loop_tree_node_t loop_tree_node)
static void do_coloring (void)
static void move_spill_restore (void)
static void update_curr_costs (ira_allocno_t a)
void ira_reassign_conflict_allocnos (int start_regno)
static void merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
static bool coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
static void coalesce_allocnos (void)
static int coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
static int coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
static void setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
static int collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n, ira_allocno_t *spilled_coalesced_allocnos)
static bool slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
static void setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
static bool coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
void ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, machine_mode *reg_max_ref_mode)
void ira_mark_allocation_change (int regno)
void ira_mark_memory_move_deletion (int dst_regno, int src_regno)
static bool allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
static int pseudo_reg_compare (const void *v1p, const void *v2p)
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)
rtx ira_reuse_stack_slot (int regno, poly_uint64 inherent_size, poly_uint64 total_size)
void ira_mark_new_stack_slot (rtx x, int regno, poly_uint64 total_size)
static int calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn, int *excess_pressure_live_length, int *nrefs, int *call_used_count, int *first_hard_regno)
bool ira_better_spill_reload_regno_p (int *regnos, int *other_regnos, rtx in, rtx out, rtx_insn *insn)
void ira_initiate_assign (void)
void ira_finish_assign (void)
static void color (void)
static void fast_allocation (void)
void ira_color (void)


const int max_soft_conflict_loop_depth = 64
static allocno_color_data_t allocno_color_data
static int curr_allocno_process
static bitmap coloring_allocno_bitmap
static bitmap consideration_allocno_bitmap
static ira_allocno_tsorted_allocnos
static vec< ira_allocno_tallocno_stack_vec
static vec< allocno_hard_regs_tallocno_hard_regs_vec
static hash_table< allocno_hard_regs_hasher > * allocno_hard_regs_htab
static int node_check_tick
static allocno_hard_regs_node_t hard_regs_roots
static vec< allocno_hard_regs_node_thard_regs_node_vec
static int allocno_hard_regs_nodes_num
static allocno_hard_regs_node_tallocno_hard_regs_nodes
static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes
static int * allocno_hard_regs_subnode_index
static object_allocator< update_cost_recordupdate_cost_record_pool ("update cost records")
static bool allocated_hardreg_p [FIRST_PSEUDO_REGISTER]
static ira_allocno_t update_cost_queue
static struct update_cost_queue_elemupdate_cost_queue_tail
static struct update_cost_queue_elemupdate_cost_queue_elems
static int update_cost_check
static ira_copy_tsorted_copies
static ira_allocno_t colorable_allocno_bucket
static ira_allocno_t uncolorable_allocno_bucket
static int uncolorable_allocnos_num
static int * allocno_priorities
static bool allocno_coalesced_p
static bitmap processed_coalesced_allocno_bitmap
static coalesce_data_t allocno_coalesce_data
static int * regno_coalesced_allocno_cost
static int * regno_coalesced_allocno_num
static machine_mode * regno_max_ref_mode
static live_range_tslot_coalesced_allocnos_live_ranges

Macro Definition Documentation




#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.   

Referenced by assign_hard_reg(), update_conflict_hard_regno_costs(), update_costs_from_allocno(), and update_costs_from_prefs().


#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.   

Referenced by allocno_hard_regs_compare(), and allocno_priority_compare_func().

Typedef Documentation

◆ allocno_color_data_t

See above.   

◆ allocno_hard_regs_node_t

◆ allocno_hard_regs_subnode_t

◆ allocno_hard_regs_t

◆ coalesce_data_t

typedef struct coalesce_data* coalesce_data_t
See below.   

Function Documentation

◆ add_allocno_hard_regs()

static allocno_hard_regs_t add_allocno_hard_regs ( HARD_REG_SET set,
int64_t cost )

◆ add_allocno_hard_regs_to_forest()

◆ add_allocno_to_bucket()

static void add_allocno_to_bucket ( ira_allocno_t a,
ira_allocno_t * bucket_ptr )
Add allocno A to bucket *BUCKET_PTR.  A should be not in a bucket
before the call.   

References a, ALLOCNO_CLASS, ALLOCNO_COLOR_DATA, ira_assert, NULL, uncolorable_allocno_bucket, and uncolorable_allocnos_num.

Referenced by put_allocno_into_bucket().

◆ add_allocno_to_ordered_colorable_bucket()

static void add_allocno_to_ordered_colorable_bucket ( ira_allocno_t allocno)
Add ALLOCNO to colorable bucket maintaining the order according
their priority.  ALLOCNO should be not in a bucket before the

References ALLOCNO_COLOR_DATA, bucket_allocno_compare_func(), colorable_allocno_bucket, form_threads_from_colorable_allocno(), and NULL.

Referenced by push_allocno_to_stack().

◆ add_new_allocno_hard_regs_node_to_forest()

static void add_new_allocno_hard_regs_node_to_forest ( allocno_hard_regs_node_t * roots,
allocno_hard_regs_node_t new_node )
Add allocno hard registers node NEW_NODE to the forest on its level
given by ROOTS.   

References allocno_hard_regs_node::next, NULL, and allocno_hard_regs_node::prev.

Referenced by add_allocno_hard_regs_to_forest(), and form_allocno_hard_regs_nodes_forest().

◆ allocno_copy_cost_saving()

◆ allocno_cost_compare_func()

static int allocno_cost_compare_func ( const void * v1p,
const void * v2p )
Sort allocnos according to the profit of usage of a hard register
instead of memory for them.  


Referenced by improve_allocation().

◆ allocno_hard_regs_compare()

static int allocno_hard_regs_compare ( const void * v1p,
const void * v2p )
Sort hard regs according to their frequency of usage.  

References allocno_hard_regs::cost, allocno_hard_regs_hasher::hash(), and SORTGT.

Referenced by form_allocno_hard_regs_nodes_forest().

◆ allocno_priority_compare_func()

static int allocno_priority_compare_func ( const void * v1p,
const void * v2p )

◆ allocno_reload_assign()

◆ allocno_spill_priority()

static int allocno_spill_priority ( ira_allocno_t a)
Return the current spill priority of allocno A.  The less the
number, the more preferable the allocno for spilling.   


Referenced by allocno_spill_priority_compare(), and remove_allocno_from_bucket_and_push().

◆ allocno_spill_priority_compare()

static int allocno_spill_priority_compare ( ira_allocno_t a1,
ira_allocno_t a2 )

◆ allocno_spill_sort_compare()

static int allocno_spill_sort_compare ( const void * v1p,
const void * v2p )
Used for sorting allocnos for spilling.   

References allocno_spill_priority_compare().

Referenced by push_allocnos_to_stack().

◆ allocno_thread_conflict_p()

static bool allocno_thread_conflict_p ( ira_allocno_t a1,
ira_allocno_t a2 )
Return true if any allocno from thread of A1 conflicts with any
allocno from thread A2.   

References a, ALLOCNO_COLOR_DATA, and allocnos_conflict_by_live_ranges_p().

Referenced by form_threads_from_copies().

◆ allocnos_conflict_by_live_ranges_p()

static bool allocnos_conflict_by_live_ranges_p ( ira_allocno_t a1,
ira_allocno_t a2 )
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.   

References ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, ALLOCNO_REGNO, get_cap_member(), i, ira_live_ranges_intersect_p(), NULL, OBJECT_LIVE_RANGES, ORIGINAL_REGNO, and regno_reg_rtx.

Referenced by allocno_thread_conflict_p(), coalesced_allocno_conflict_p(), and ira_reuse_stack_slot().

◆ allocnos_conflict_p()

static bool allocnos_conflict_p ( ira_allocno_t a1,
ira_allocno_t a2 )
Return TRUE if allocnos A1 and A2 conflicts. Here we are
interested only in conflicts of allocnos with intersecting allocno


Referenced by update_conflict_hard_regno_costs().

◆ assign_hard_reg()

static bool assign_hard_reg ( ira_allocno_t a,
bool retry_p )
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.   

References a, add_cost(), allocated_hardreg_p, ALLOCNO_ASSIGNED_P, ALLOCNO_CLASS, ALLOCNO_COLOR_DATA, ALLOCNO_CONFLICT_HARD_REG_COSTS, ALLOCNO_HARD_REG_COSTS, ALLOCNO_HARD_REGNO, ALLOCNO_MODE, ALLOCNO_NUM, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, ALLOCNO_REGISTER_FILTERS, ALLOCNO_REGNO, ALLOCNO_UPDATED_CLASS_COST, ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS, ALLOCNO_UPDATED_HARD_REG_COSTS, ALLOCNO_UPDATED_MEMORY_COST, bitmap_bit_p, bitmap_set_bit, calculate_saved_nregs(), cfun, check_hard_reg_p(), consideration_allocno_bitmap, COST_HOP_DIVISOR, curr_allocno_process, end_hard_regno(), ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_OBJECT_CONFLICT, get_conflict_and_start_profitable_regs(), hard_reg_set_intersect_p(), hard_reg_set_subset_p(), update_cost_record::hard_regno, hard_regno_nregs(), HONOR_REG_ALLOC_ORDER, i, INT_MAX, internal_flag_ira_verbose, ira_allocate_and_copy_costs(), ira_assert, ira_class_hard_reg_index, ira_class_hard_regs, ira_class_hard_regs_num, ira_dump_file, ira_free_allocno_updated_costs(), ira_hard_reg_set_intersection_p(), ira_memory_move_cost, ira_reg_classes_intersect_p, ira_reg_mode_hard_regset, ira_soft_conflict(), non_spilled_static_chain_regno_p(), NULL, OBJECT_ALLOCNO, OBJECT_SUBWORD, queue_update_cost(), r, reg_class_contents, REG_FREQ_FROM_BB, REG_WORDS_BIG_ENDIAN, restore_costs_from_copies(), SET_HARD_REG_BIT, ira_loop_border_costs::spill_inside_loop_cost(), spill_soft_conflicts(), start_update_cost(), TEST_HARD_REG_BIT, update_conflict_hard_regno_costs(), and update_costs_from_copies().

Referenced by allocno_reload_assign(), color_allocnos(), improve_allocation(), ira_reassign_conflict_allocnos(), and pop_allocnos_from_stack().

◆ bucket_allocno_compare_func()

static int bucket_allocno_compare_func ( const void * v1p,
const void * v2p )
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.   


Referenced by add_allocno_to_ordered_colorable_bucket(), and push_only_colorable().

◆ calculate_allocno_spill_cost()

◆ calculate_saved_nregs()

static int calculate_saved_nregs ( int hard_regno,
machine_mode mode )
Return number of registers needed to be saved and restored at
function prologue/epilogue if we allocate HARD_REGNO to hold value
of MODE.   

References allocated_hardreg_p, crtl, update_cost_record::hard_regno, hard_regno_nregs(), i, ira_assert, and LOCAL_REGNO.

Referenced by assign_hard_reg(), and improve_allocation().

◆ calculate_spill_cost()

static int calculate_spill_cost ( int * regnos,
rtx in,
rtx out,
rtx_insn * insn,
int * excess_pressure_live_length,
int * nrefs,
int * call_used_count,
int * first_hard_regno )
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), the number of psuedo registers
whose allocated register wouldn't need saving in the prologue
(through CALL_USED_COUNT), and the first hard regno occupied by the
pseudo-registers (through FIRST_HARD_REGNO).   

References a, ALLOCNO_CLASS, ALLOCNO_CLASS_COST, ALLOCNO_EXCESS_PRESSURE_POINTS_NUM, ALLOCNO_MEMORY_COST, ALLOCNO_MODE, ALLOCNO_NUM_OBJECTS, BLOCK_FOR_INSN(), count, crtl, find_regno_note(), i, in_hard_reg_set_p(), ira_assert, ira_memory_move_cost, ira_regno_allocno_map, NULL_RTX, REG_FREQ_FROM_BB, REG_N_REFS(), REG_P, reg_renumber, and REGNO.

Referenced by ira_better_spill_reload_regno_p().

◆ check_hard_reg_p()

static bool check_hard_reg_p ( ira_allocno_t a,
int hard_regno,
HARD_REG_SET * conflict_regs,
HARD_REG_SET profitable_regs )
Return true if HARD_REGNO is ok for assigning to allocno A with
PROFITABLE_REGS and whose objects have CONFLICT_REGS.   

References a, ALLOCNO_CLASS, ALLOCNO_MODE, ALLOCNO_NUM_OBJECTS, update_cost_record::hard_regno, hard_regno_nregs(), ira_prohibited_class_mode_regs, REG_WORDS_BIG_ENDIAN, and TEST_HARD_REG_BIT.

Referenced by assign_hard_reg(), and improve_allocation().

◆ coalesce_allocnos()

◆ coalesce_spill_slots()

static bool coalesce_spill_slots ( ira_allocno_t * spilled_coalesced_allocnos,
int num )
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.   

References a, ALLOCNO_COALESCE_DATA, allocno_coalesced_p, ALLOCNO_NUM, ALLOCNO_REGNO, bitmap_bit_p, i, internal_flag_ira_verbose, ira_allocate(), ira_allocnos_num, ira_assert, ira_dump_file, ira_equiv_no_lvalue_p(), ira_finish_live_range_list(), ira_free(), merge_allocnos(), NULL, regstat_get_setjmp_crosses(), setup_slot_coalesced_allocno_live_ranges(), slot_coalesced_allocno_live_ranges_intersect_p(), and slot_coalesced_allocnos_live_ranges.

Referenced by ira_sort_regnos_for_alter_reg().

◆ coalesced_allocno_conflict_p()

static bool coalesced_allocno_conflict_p ( ira_allocno_t a1,
ira_allocno_t a2 )
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.   

References a, ALLOCNO_COALESCE_DATA, allocno_coalesced_p, ALLOCNO_NUM, allocnos_conflict_by_live_ranges_p(), bitmap_clear(), bitmap_set_bit, and processed_coalesced_allocno_bitmap.

Referenced by coalesce_allocnos().

◆ coalesced_pseudo_reg_freq_compare()

static int coalesced_pseudo_reg_freq_compare ( const void * v1p,
const void * v2p )
Sort pseudos according frequencies of coalesced allocno sets they
belong to (putting most frequently ones first), and according to
coalesced allocno set order numbers.   

References regno_coalesced_allocno_cost, and regno_coalesced_allocno_num.

Referenced by ira_sort_regnos_for_alter_reg().

◆ coalesced_pseudo_reg_slot_compare()

static int coalesced_pseudo_reg_slot_compare ( const void * v1p,
const void * v2p )
Sort pseudos according their slot numbers (putting ones with
smaller numbers first, or last when the frame pointer is not

References ALLOCNO_HARD_REGNO, FRAME_GROWS_DOWNWARD, frame_pointer_needed, GET_MODE_SIZE(), ira_regno_allocno_map, NULL, PSEUDO_REGNO_MODE, regno_max_ref_mode, STACK_GROWS_DOWNWARD, and wider_subreg_mode().

Referenced by ira_sort_regnos_for_alter_reg().

◆ collect_allocno_hard_regs_cover()

static void collect_allocno_hard_regs_cover ( allocno_hard_regs_node_t first,

◆ collect_spilled_coalesced_allocnos()

static int collect_spilled_coalesced_allocnos ( int * pseudo_regnos,
int n,
ira_allocno_t * spilled_coalesced_allocnos )
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_COALESCE_DATA, ALLOCNO_HARD_REGNO, i, ira_regno_allocno_map, and NULL.

Referenced by ira_sort_regnos_for_alter_reg().

◆ color()

static void color ( void )

◆ color_allocnos()

◆ color_pass()

static void color_pass ( ira_loop_tree_node_t loop_tree_node)
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.   

References a, ira_loop_tree_node::all_allocnos, ALLOCNO_ADD_DATA, ALLOCNO_ASSIGNED_P, ALLOCNO_CAP, ALLOCNO_CAP_MEMBER, ALLOCNO_CLASS, ALLOCNO_CONFLICT_HARD_REG_COSTS, ALLOCNO_HARD_REG_COSTS, ALLOCNO_HARD_REGNO, ALLOCNO_LOOP_TREE_NODE, ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P, ALLOCNO_MODE, ALLOCNO_NUM, ALLOCNO_REGNO, ALLOCNO_UPDATED_CLASS_COST, ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS, ALLOCNO_UPDATED_HARD_REG_COSTS, ALLOCNO_UPDATED_MEMORY_COST, ira_loop_tree_node::bb, bitmap_bit_p, bitmap_clear_bit(), bitmap_copy(), color_allocnos(), coloring_allocno_bitmap, consideration_allocno_bitmap, curr_allocno_process, EXECUTE_IF_SET_IN_BITMAP, gcc_assert, update_cost_record::hard_regno, init_allocno_threads(), internal_flag_ira_verbose, ira_allocate(), ira_allocate_and_set_or_copy_costs(), ira_allocnos, ira_assert, ira_class_hard_reg_index, ira_dump_file, ira_free(), ira_free_allocno_updated_costs(), ira_init_register_move_cost_if_necessary(), IRA_REGION_ALL, IRA_REGION_MIXED, ira_single_region_allocno_p(), ira_subloop_allocnos_can_differ_p(), ira_loop_border_costs::move_between_loops_cost(), NULL, print_loop_title(), ira_loop_tree_node::regno_allocno_map, ira_loop_border_costs::spill_inside_loop_cost(), ira_loop_border_costs::spill_outside_loop_cost(), ira_loop_tree_node::subloop_next, ira_loop_tree_node::subloops, and update_costs_from_copies().

Referenced by do_coloring().

◆ copy_freq_compare_func()

static int copy_freq_compare_func ( const void * v1p,
const void * v2p )
The function is used to sort copies according to their execution

References ira_allocno_copy::freq, and ira_allocno_copy::num.

Referenced by coalesce_allocnos(), and form_threads_from_copies().

◆ create_new_allocno_hard_regs_node()

◆ debug_hard_reg_set()

DEBUG_FUNCTION void debug_hard_reg_set ( HARD_REG_SET set)
Dump a hard reg set SET to stderr.   

References print_hard_reg_set().

◆ delete_allocno_from_bucket()

static void delete_allocno_from_bucket ( ira_allocno_t allocno,
ira_allocno_t * bucket_ptr )
Delete ALLOCNO from bucket *BUCKET_PTR.  It should be there before
the call.   

References ALLOCNO_CLASS, ALLOCNO_COLOR_DATA, ira_assert, NULL, uncolorable_allocno_bucket, and uncolorable_allocnos_num.

Referenced by push_allocno_to_stack(), and remove_allocno_from_bucket_and_push().

◆ do_coloring()

static void do_coloring ( void )
Initialize the common data for coloring and calls functions to do
Chaitin-Briggs and regional coloring.   

References color_pass(), coloring_allocno_bitmap, internal_flag_ira_verbose, ira_allocate_bitmap(), ira_dump_file, ira_free_bitmap(), ira_loop_tree_root, ira_print_disposition(), ira_traverse_loop_tree(), and NULL.

Referenced by color().

◆ empty_profitable_hard_regs()

static bool empty_profitable_hard_regs ( ira_allocno_t a)
Return true if allocno A has empty profitable hard regs.   

References a, ALLOCNO_COLOR_DATA, and hard_reg_set_empty_p().

Referenced by color_allocnos(), improve_allocation(), and setup_profitable_hard_regs().

◆ enumerate_allocno_hard_regs_nodes()

static int enumerate_allocno_hard_regs_nodes ( allocno_hard_regs_node_t first,
allocno_hard_regs_node_t parent,
int start_num )
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 enumerate_allocno_hard_regs_nodes(), allocno_hard_regs_node::first, allocno_hard_regs_node::next, NULL, allocno_hard_regs_node::parent, and allocno_hard_regs_node::preorder_num.

Referenced by enumerate_allocno_hard_regs_nodes(), and form_allocno_hard_regs_nodes_forest().

◆ fast_allocation()

◆ find_hard_regs()

static allocno_hard_regs_t find_hard_regs ( allocno_hard_regs_t hv)
Return allocno hard registers in the hash table equal to HV.   

References allocno_hard_regs_htab.

Referenced by add_allocno_hard_regs().

◆ finish_allocno_hard_regs()

static void finish_allocno_hard_regs ( void )
Finalize data concerning allocno hard registers.   

References allocno_hard_regs_htab, allocno_hard_regs_vec, i, ira_free(), and NULL.

Referenced by finish_allocno_hard_regs_nodes_forest().

◆ finish_allocno_hard_regs_nodes_forest()

static void finish_allocno_hard_regs_nodes_forest ( void )

◆ finish_allocno_hard_regs_nodes_tree()

static void finish_allocno_hard_regs_nodes_tree ( allocno_hard_regs_node_t root)

◆ finish_cost_update()

static void finish_cost_update ( void )
Deallocate data used by function update_costs_from_copies.   

References finish_update_cost_records(), ira_free(), and update_cost_queue_elems.

Referenced by ira_finish_assign().

◆ finish_update_cost_records()

static void finish_update_cost_records ( void )
Free memory allocated for all update cost records.   

References update_cost_record_pool.

Referenced by finish_cost_update().

◆ first_common_ancestor_node()

static allocno_hard_regs_node_t first_common_ancestor_node ( allocno_hard_regs_node_t first,
allocno_hard_regs_node_t second )
Return allocno hard registers node which is a first common ancestor
node of FIRST and SECOND in the forest.   

References allocno_hard_regs_node::check, allocno_hard_regs_node::first, first_common_ancestor_node(), node_check_tick, NULL, and allocno_hard_regs_node::parent.

Referenced by first_common_ancestor_node(), and form_allocno_hard_regs_nodes_forest().

◆ form_allocno_hard_regs_nodes_forest()

◆ form_threads_from_bucket()

static void form_threads_from_bucket ( ira_allocno_t bucket)
Create threads by processing copies of all alocnos from BUCKET.  We
process the most expensive copies first.   

References a, ALLOCNO_COLOR_DATA, ALLOCNO_COPIES, ira_allocno_copy::first, form_threads_from_copies(), gcc_unreachable, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, NULL, ira_allocno_copy::second, and sorted_copies.

Referenced by push_only_colorable().

◆ form_threads_from_colorable_allocno()

◆ form_threads_from_copies()

static void form_threads_from_copies ( int cp_num)

◆ free_update_cost_record_list()

static void free_update_cost_record_list ( struct update_cost_record * list)
Free memory for all records in LIST.   

References update_cost_record::next, NULL, and update_cost_record_pool.

Referenced by restore_costs_from_copies().

◆ get_allocno_hard_regs_subnodes_num()

static int get_allocno_hard_regs_subnodes_num ( allocno_hard_regs_node_t root)

◆ get_cap_member()

static ira_allocno_t get_cap_member ( ira_allocno_t a)
If allocno A is a cap, return non-cap allocno from which A is
created.  Otherwise, return A.   

References a, ALLOCNO_CAP_MEMBER, and NULL.

Referenced by allocnos_conflict_by_live_ranges_p().

◆ get_conflict_and_start_profitable_regs()

static void get_conflict_and_start_profitable_regs ( ira_allocno_t a,
bool retry_p,
HARD_REG_SET * conflict_regs,
HARD_REG_SET * start_profitable_regs )
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 cannot hold value of mode of allocno A.
This covers mostly cases when multi-register value should be


Referenced by assign_hard_reg(), and improve_allocation().

◆ get_next_update_cost()

static bool get_next_update_cost ( ira_allocno_t * allocno,
ira_allocno_t * start,
ira_allocno_t * from,
int * divisor )
Try to remove the first element from update_cost_queue.  Return
false if the queue was empty, otherwise make (*ALLOCNO, *START,
*FROM, *DIVISOR) describe the removed element.   

References ALLOCNO_NUM, update_cost_queue_elem::divisor, update_cost_queue_elem::from, update_cost_queue_elem::next, NULL, update_cost_queue_elem::start, update_cost_queue, and update_cost_queue_elems.

Referenced by update_conflict_hard_regno_costs(), and update_costs_from_allocno().

◆ get_update_cost_record()

static struct update_cost_record * get_update_cost_record ( int hard_regno,
int divisor,
struct update_cost_record * next )
Return new update cost record with given params.   

References update_cost_record::divisor, update_cost_record::hard_regno, update_cost_record::next, and update_cost_record_pool.

Referenced by update_costs_from_allocno().

◆ improve_allocation()

◆ init_allocno_hard_regs()

static void init_allocno_hard_regs ( void )
Initialize data concerning allocno hard registers.   

References allocno_hard_regs_htab, and allocno_hard_regs_vec.

Referenced by form_allocno_hard_regs_nodes_forest().

◆ init_allocno_threads()

static void init_allocno_threads ( void )
Form initial threads which contain only one allocno.   

References a, ALLOCNO_COLOR_DATA, ALLOCNO_FREQ, ALLOCNO_PREFS, consideration_allocno_bitmap, EXECUTE_IF_SET_IN_BITMAP, ira_allocnos, NULL, and pref.

Referenced by color_pass().

◆ initiate_cost_update()

static void initiate_cost_update ( void )
Allocate and initialize data necessary for function

References ira_allocate(), ira_allocnos_num, update_cost_check, and update_cost_queue_elems.

Referenced by ira_initiate_assign().

◆ insert_hard_regs()

static allocno_hard_regs_t insert_hard_regs ( allocno_hard_regs_t hv)
Insert allocno hard registers HV in the hash table (if it is not
there yet) and return the value which in the table.   

References allocno_hard_regs_htab, and NULL.

Referenced by add_allocno_hard_regs().

◆ ira_better_spill_reload_regno_p()

bool ira_better_spill_reload_regno_p ( int * regnos,
int * other_regnos,
rtx in,
rtx out,
rtx_insn * 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

References calculate_spill_cost(), and inv_reg_alloc_order.

Referenced by find_reg().

◆ ira_color()

void ira_color ( void )

◆ ira_debug_hard_regs_forest()

void ira_debug_hard_regs_forest ( void )
Print the allocno hard register forest to stderr.   

References print_hard_regs_forest().

◆ ira_finish_assign()

void ira_finish_assign ( void )
Deallocate data used by assign_hard_reg.   

References allocno_priorities, consideration_allocno_bitmap, finish_cost_update(), ira_free(), ira_free_bitmap(), sorted_allocnos, and sorted_copies.

Referenced by color(), and do_reload().

◆ ira_initiate_assign()

void ira_initiate_assign ( void )
Allocate and initialize data necessary for assign_hard_reg.   

References allocno_priorities, consideration_allocno_bitmap, initiate_cost_update(), ira_allocate(), ira_allocate_bitmap(), ira_allocnos_num, ira_copies_num, sorted_allocnos, and sorted_copies.

Referenced by color(), and ira().

◆ ira_loop_edge_freq()

int ira_loop_edge_freq ( ira_loop_tree_node_t loop_node,
int regno,
bool exit_p )

◆ ira_mark_allocation_change()

void ira_mark_allocation_change ( int regno)
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.   

References a, ALLOCNO_CLASS, ALLOCNO_CLASS_COST, ALLOCNO_HARD_REG_COSTS, ALLOCNO_HARD_REGNO, ALLOCNO_MEMORY_COST, ira_assert, ira_class_hard_reg_index, ira_overall_cost, ira_regno_allocno_map, NULL, reg_renumber, and update_costs_from_copies().

Referenced by delete_output_reload(), emit_input_reload_insns(), finish_spills(), and ira_reassign_pseudos().

◆ ira_mark_memory_move_deletion()

void ira_mark_memory_move_deletion ( int dst_regno,
int src_regno )
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 ALLOCNO_DONT_REASSIGN_P, ALLOCNO_HARD_REGNO, ira_assert, ira_regno_allocno_map, and NULL.

Referenced by calculate_needs_all_insns().

◆ ira_mark_new_stack_slot()

void ira_mark_new_stack_slot ( rtx x,
int regno,
poly_uint64 total_size )
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.   

References ALLOCNO_HARD_REGNO, INIT_REG_SET, internal_flag_ira_verbose, ira_assert, ira_dump_file, ira_regno_allocno_map, ira_spilled_reg_stack_slots, ira_spilled_reg_stack_slots_num, ira_use_lra_p, known_le, slot::mem, PSEUDO_REGNO_BYTES, REG_FREQ, and SET_REGNO_REG_SET.

Referenced by alter_reg().

◆ ira_reassign_conflict_allocnos()

void ira_reassign_conflict_allocnos ( int start_regno)
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.cc) will have a
chance to get a hard register.  We use simple assignment algorithm
based on priorities.   

References a, ALLOCNO_ASSIGNED_P, ALLOCNO_CLASS, ALLOCNO_HARD_REGNO, ALLOCNO_NUM, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, allocno_priority_compare_func(), ALLOCNO_REGNO, ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS, ALLOCNO_UPDATED_HARD_REG_COSTS, assign_hard_reg(), bitmap_bit_p, bitmap_set_bit, FOR_EACH_ALLOCNO, FOR_EACH_OBJECT_CONFLICT, i, internal_flag_ira_verbose, ira_allocate_bitmap(), ira_assert, ira_dump_file, ira_free_bitmap(), ira_reg_classes_intersect_p, NULL, OBJECT_ALLOCNO, qsort, setup_allocno_priorities(), sorted_allocnos, and update_curr_costs().

Referenced by ira().

◆ ira_reassign_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

References a, ALLOCNO_CLASS_COST, ALLOCNO_DONT_REASSIGN_P, ALLOCNO_HARD_REGNO, ALLOCNO_MEMORY_COST, ALLOCNO_NUM, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, ALLOCNO_REGNO, allocno_reload_assign(), bad_spill_regs, BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, CLEAR_REGNO_REG_SET, consideration_allocno_bitmap, FOR_EACH_OBJECT_CONFLICT, gcc_assert, i, internal_flag_ira_verbose, ira_assert, ira_dump_file, ira_mark_allocation_change(), ira_regno_allocno_map, nr, NULL, OBJECT_ALLOCNO, pseudo_forbidden_regs, pseudo_previous_regs, pseudo_reg_compare(), qsort, and reg_renumber.

Referenced by finish_spills().

◆ ira_reuse_stack_slot()

◆ ira_soft_conflict()

ira_allocno_t ira_soft_conflict ( ira_allocno_t a1,
ira_allocno_t a2 )
Allocnos A1 and A2 are known to conflict.  Check whether, in some loop L
that is either the current loop or a nested subloop, the conflict is of
the following form:

- One allocno (X) is a cap allocno for some non-cap allocno X2.

- X2 belongs to some loop L2.

- The other allocno (Y) is a non-cap allocno.

- Y is an ancestor of some allocno Y2 in L2.  (Note that such a Y2
  must exist, given that X and Y conflict.)

- Y2 is not referenced in L2 (that is, ALLOCNO_NREFS (Y2) == 0).

- Y can use a different allocation from Y2.

In this case, Y's register is live across L2 but is not used within it,
whereas X's register is used only within L2.  The conflict is therefore
only "soft", in that it can easily be avoided by spilling Y2 inside L2
without affecting any insn references.

If the conflict does have this form, return the Y2 that would need to be
spilled in order to allow X and Y (and thus A1 and A2) to use the same
register.  Return null otherwise.  Returning null is conservatively correct;
any nonnnull return value is an optimization.   

References ALLOCNO_CAP_MEMBER, ALLOCNO_LOOP_TREE_NODE, ALLOCNO_NREFS, ALLOCNO_REGNO, ira_assert, ira_parent_allocno(), ira_subloop_allocnos_can_differ_p(), and max_soft_conflict_loop_depth.

Referenced by assign_hard_reg(), improve_allocation(), and spill_soft_conflicts().

◆ ira_sort_regnos_for_alter_reg()

◆ merge_allocnos()

static void merge_allocnos ( ira_allocno_t a1,
ira_allocno_t a2 )
Merge two sets of coalesced allocnos given correspondingly by
allocnos A1 and A2 (more accurately merging A2 set into A1

References a, ALLOCNO_COALESCE_DATA, allocno_coalesce_data, ALLOCNO_NUM, last, and coalesce_data::next.

Referenced by coalesce_allocnos(), and coalesce_spill_slots().

◆ merge_threads()

static void merge_threads ( ira_allocno_t t1,
ira_allocno_t t2 )
Merge two threads given correspondingly by their first allocnos T1
and T2 (more accurately merging T2 into T1).   

References a, ALLOCNO_COLOR_DATA, gcc_assert, last, and update_cost_record::next.

Referenced by form_threads_from_copies().

◆ move_spill_restore()

◆ object_conflicts_with_allocno_p()

static bool object_conflicts_with_allocno_p ( ira_object_t obj,
ira_allocno_t a )

◆ pop_allocnos_from_stack()

static void pop_allocnos_from_stack ( void )

◆ print_hard_reg_set()

static void print_hard_reg_set ( FILE * f,
bool new_line_p )
Print hard reg set SET to F.   

References end(), i, and TEST_HARD_REG_BIT.

Referenced by debug_hard_reg_set(), print_hard_regs_subforest(), and setup_allocno_available_regs_num().

◆ print_hard_regs_forest()

static void print_hard_regs_forest ( FILE * f)
Print the allocno hard register forest to F.   

References hard_regs_roots, and print_hard_regs_subforest().

Referenced by color_allocnos(), and ira_debug_hard_regs_forest().

◆ print_hard_regs_subforest()

static void print_hard_regs_subforest ( FILE * f,
allocno_hard_regs_node_t roots,
int level )

◆ print_loop_title()

◆ pseudo_reg_compare()

static int pseudo_reg_compare ( const void * v1p,
const void * v2p )
Sort pseudos according their usage frequencies (putting most
frequently ones first).   

References REG_FREQ.

Referenced by ira_reassign_pseudos().

◆ push_allocno_to_stack()

◆ push_allocnos_to_stack()

static void push_allocnos_to_stack ( void )
Push allocnos to the coloring stack.  The order of allocnos in the
stack defines the order for the subsequent coloring.   

References a, ALLOCNO_CLASS, ALLOCNO_COLOR_DATA, allocno_spill_sort_compare(), calculate_allocno_spill_cost(), colorable_allocno_bucket, ira_assert, NULL, push_only_colorable(), remove_allocno_from_bucket_and_push(), sort_bucket(), uncolorable_allocno_bucket, and uncolorable_allocnos_num.

Referenced by color_allocnos().

◆ push_only_colorable()

static void push_only_colorable ( void )

◆ put_allocno_into_bucket()

static void put_allocno_into_bucket ( ira_allocno_t allocno)
Put ALLOCNO in a bucket corresponding to its number and size of its
conflicting allocnos and hard registers.   

References add_allocno_to_bucket(), ALLOCNO_COLOR_DATA, colorable_allocno_bucket, setup_allocno_available_regs_num(), setup_left_conflict_sizes_p(), and uncolorable_allocno_bucket.

Referenced by color_allocnos().

◆ queue_update_cost()

static void queue_update_cost ( ira_allocno_t allocno,
ira_allocno_t start,
ira_allocno_t from,
int divisor )

◆ remove_allocno_from_bucket_and_push()

static void remove_allocno_from_bucket_and_push ( ira_allocno_t allocno,
bool colorable_p )
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_BAD_SPILL_P, ALLOCNO_COLOR_DATA, allocno_spill_priority(), colorable_allocno_bucket, delete_allocno_from_bucket(), internal_flag_ira_verbose, ira_dump_file, ira_print_expanded_allocno(), NULL, push_allocno_to_stack(), and uncolorable_allocno_bucket.

Referenced by push_allocnos_to_stack(), and push_only_colorable().

◆ remove_unused_allocno_hard_regs_nodes()

static void remove_unused_allocno_hard_regs_nodes ( allocno_hard_regs_node_t * roots)

◆ restore_costs_from_copies()

static void restore_costs_from_copies ( ira_allocno_t allocno)
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_COLOR_DATA, ALLOCNO_NUM, ALLOCNO_REGNO, update_cost_record::divisor, free_update_cost_record_list(), update_cost_record::hard_regno, internal_flag_ira_verbose, ira_dump_file, update_cost_record::next, NULL, start_update_cost(), and update_costs_from_allocno().

Referenced by assign_hard_reg().

◆ setup_allocno_available_regs_num()

◆ setup_allocno_hard_regs_nodes_parent()

static void setup_allocno_hard_regs_nodes_parent ( allocno_hard_regs_node_t first,
allocno_hard_regs_node_t parent )
Set up field parent as PARENT in all allocno hard registers nodes
in forest given by FIRST.   

References allocno_hard_regs_node::first, allocno_hard_regs_node::next, NULL, allocno_hard_regs_node::parent, and setup_allocno_hard_regs_nodes_parent().

Referenced by form_allocno_hard_regs_nodes_forest(), and setup_allocno_hard_regs_nodes_parent().

◆ setup_allocno_hard_regs_subnode_index()

◆ setup_allocno_priorities()

static void setup_allocno_priorities ( ira_allocno_t * consideration_allocnos,
int n )

◆ setup_coalesced_allocno_costs_and_nums()

static void setup_coalesced_allocno_costs_and_nums ( int * pseudo_regnos,
int n )
for coalesced allocno sets containing allocnos with their regnos
given in array PSEUDO_REGNOS of length N.   

References a, ALLOCNO_COALESCE_DATA, ALLOCNO_FREQ, ALLOCNO_REGNO, i, ira_regno_allocno_map, NULL, regno_coalesced_allocno_cost, and regno_coalesced_allocno_num.

Referenced by ira_sort_regnos_for_alter_reg().

◆ setup_left_conflict_sizes_p()

◆ setup_profitable_hard_regs()

◆ setup_slot_coalesced_allocno_live_ranges()

static void setup_slot_coalesced_allocno_live_ranges ( ira_allocno_t allocno)
Update live ranges of slot to which coalesced allocnos represented
by ALLOCNO were assigned.   

References a, ALLOCNO_CAP_MEMBER, ALLOCNO_COALESCE_DATA, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, gcc_assert, i, ira_copy_live_range_list(), ira_merge_live_ranges(), nr, NULL, OBJECT_LIVE_RANGES, r, and slot_coalesced_allocnos_live_ranges.

Referenced by coalesce_spill_slots().

◆ slot_coalesced_allocno_live_ranges_intersect_p()

static bool slot_coalesced_allocno_live_ranges_intersect_p ( ira_allocno_t allocno,
int n )
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 a, ALLOCNO_CAP_MEMBER, ALLOCNO_COALESCE_DATA, ALLOCNO_NUM_OBJECTS, ALLOCNO_OBJECT, gcc_assert, i, ira_live_ranges_intersect_p(), nr, NULL, OBJECT_LIVE_RANGES, and slot_coalesced_allocnos_live_ranges.

Referenced by coalesce_spill_slots().

◆ sort_bucket()

static void sort_bucket ( ira_allocno_t * bucket_ptr,
int(* compare_func )(const void *, const void *) )
Sort bucket *BUCKET_PTR and return the result through

References a, ALLOCNO_COLOR_DATA, NULL, qsort, and sorted_allocnos.

Referenced by push_allocnos_to_stack(), and push_only_colorable().

◆ spill_soft_conflicts()

static void spill_soft_conflicts ( ira_allocno_t a,
bitmap allocnos_to_spill,
HARD_REG_SET soft_conflict_regs,
int hregno )
The caller has decided to allocate HREGNO to A and has proved that
this is safe.  However, the allocation might require the kind of
spilling described in the comment above ira_soft_conflict.
The caller has recorded that:

- The allocnos in ALLOCNOS_TO_SPILL are the ones that would need
  to be spilled to satisfy soft conflicts for at least one allocation
  (not necessarily HREGNO).

- The soft conflicts apply only to A allocations that overlap

If allocating HREGNO is subject to any soft conflicts, record the
subloop allocnos that need to be spilled.   

References a, ALLOCNO_HARD_REGNO, ALLOCNO_LOOP_TREE_NODE, ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P, ALLOCNO_MODE, EXECUTE_IF_SET_IN_BITMAP, hard_regno_nregs(), i, ira_allocnos, ira_assert, ira_hard_reg_set_intersection_p(), ira_parent_or_cap_allocno(), and ira_soft_conflict().

Referenced by assign_hard_reg(), and improve_allocation().

◆ start_update_cost()

static void start_update_cost ( void )

◆ update_allocno_cost()

static bool update_allocno_cost ( ira_allocno_t allocno,
int hard_regno,
int update_cost,
int update_conflict_cost )
Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
UPDATE_CONFLICT_COST for ALLOCNO.  Return true if we really
modified the cost.   


Referenced by update_costs_from_allocno().

◆ update_conflict_allocno_hard_prefs()

static void update_conflict_allocno_hard_prefs ( ira_allocno_t allocno)

◆ update_conflict_hard_regno_costs()

static void update_conflict_hard_regno_costs ( int * costs,
enum reg_class aclass,
bool decr_p )

◆ update_costs_from_allocno()

◆ update_costs_from_copies()

static void update_costs_from_copies ( ira_allocno_t allocno,
bool decr_p,
bool record_p )
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.  Record cost updates if RECORD_P is true.   

References ALLOCNO_CLASS, ALLOCNO_HARD_REGNO, ALLOCNO_NUM, ALLOCNO_REGNO, internal_flag_ira_verbose, ira_assert, ira_dump_file, NULL, start_update_cost(), and update_costs_from_allocno().

Referenced by assign_hard_reg(), color_pass(), and ira_mark_allocation_change().

◆ update_costs_from_prefs()

static void update_costs_from_prefs ( ira_allocno_t allocno)
Decrease preferred ALLOCNO hard register costs and costs of
allocnos connected to ALLOCNO through copy.   

References ALLOCNO_NUM, ALLOCNO_PREFS, ALLOCNO_REGNO, COST_HOP_DIVISOR, ira_allocno::hard_regno, internal_flag_ira_verbose, ira_dump_file, NULL, pref, start_update_cost(), and update_costs_from_allocno().

Referenced by push_only_colorable().

◆ update_curr_costs()

◆ update_left_conflict_sizes_p()

Variable Documentation

◆ allocated_hardreg_p

bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER]
Array whose element value is TRUE if the corresponding hard
register was already allocated for an allocno.   

Referenced by assign_hard_reg(), calculate_saved_nregs(), color(), and improve_allocation().

◆ allocno_coalesce_data

coalesce_data_t allocno_coalesce_data
Container for storing allocno data concerning coalescing.   

Referenced by coalesce_allocnos(), ira_sort_regnos_for_alter_reg(), and merge_allocnos().

◆ allocno_coalesced_p

bool allocno_coalesced_p
This page contains functions used to find conflicts using allocno
live ranges.   
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.   

Referenced by coalesce_allocnos(), coalesce_spill_slots(), coalesced_allocno_conflict_p(), and ira_sort_regnos_for_alter_reg().

◆ allocno_color_data

allocno_color_data_t allocno_color_data
Container for storing allocno data concerning coloring.   

◆ allocno_hard_regs_htab

hash_table<allocno_hard_regs_hasher>* allocno_hard_regs_htab
Hash table of unique allocno hard registers.   

Referenced by find_hard_regs(), finish_allocno_hard_regs(), init_allocno_hard_regs(), and insert_hard_regs().

◆ allocno_hard_regs_nodes

allocno_hard_regs_node_t* allocno_hard_regs_nodes
Table preorder number of allocno hard registers node in the forest
-> the allocno hard registers node.   

Referenced by finish_allocno_hard_regs_nodes_forest(), form_allocno_hard_regs_nodes_forest(), setup_allocno_hard_regs_subnode_index(), setup_left_conflict_sizes_p(), and update_left_conflict_sizes_p().

◆ allocno_hard_regs_nodes_num

int allocno_hard_regs_nodes_num

◆ allocno_hard_regs_subnode_index

int* allocno_hard_regs_subnode_index
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

Referenced by finish_allocno_hard_regs_nodes_forest(), form_allocno_hard_regs_nodes_forest(), setup_allocno_hard_regs_subnode_index(), setup_left_conflict_sizes_p(), and update_left_conflict_sizes_p().

◆ allocno_hard_regs_subnodes

allocno_hard_regs_subnode_t allocno_hard_regs_subnodes

◆ allocno_hard_regs_vec

vec<allocno_hard_regs_t> allocno_hard_regs_vec
Definition of vector of allocno hard registers.   
Vector of unique allocno hard registers.   

Referenced by add_allocno_hard_regs(), finish_allocno_hard_regs(), form_allocno_hard_regs_nodes_forest(), and init_allocno_hard_regs().

◆ allocno_priorities

int* allocno_priorities

◆ allocno_stack_vec

vec<ira_allocno_t> allocno_stack_vec
Vec representing the stack of allocnos used during coloring.   

Referenced by color(), pop_allocnos_from_stack(), and push_allocno_to_stack().

◆ colorable_allocno_bucket

ira_allocno_t colorable_allocno_bucket
This page contains the allocator based on the Chaitin-Briggs algorithm.   
Bucket of allocnos that can colored currently without spilling.   

Referenced by add_allocno_to_ordered_colorable_bucket(), color_allocnos(), push_allocnos_to_stack(), push_only_colorable(), put_allocno_into_bucket(), and remove_allocno_from_bucket_and_push().

◆ coloring_allocno_bitmap

bitmap coloring_allocno_bitmap
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.   

Referenced by coalesce_allocnos(), color_allocnos(), color_pass(), do_coloring(), form_allocno_hard_regs_nodes_forest(), improve_allocation(), ira_sort_regnos_for_alter_reg(), push_allocno_to_stack(), and setup_profitable_hard_regs().

◆ consideration_allocno_bitmap

bitmap consideration_allocno_bitmap
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

Referenced by assign_hard_reg(), color_pass(), init_allocno_threads(), ira_finish_assign(), ira_initiate_assign(), ira_reassign_pseudos(), and setup_profitable_hard_regs().

◆ curr_allocno_process

int curr_allocno_process
Used for finding allocno colorability to exclude repeated allocno
processing and for updating preferencing to exclude repeated
allocno processing during assignment.   

Referenced by assign_hard_reg(), and color_pass().

◆ hard_regs_node_vec

vec<allocno_hard_regs_node_t> hard_regs_node_vec
Definition of vector of allocno hard register nodes.   
Vector used to create the forest.   

Referenced by add_allocno_hard_regs_to_forest(), collect_allocno_hard_regs_cover(), and form_allocno_hard_regs_nodes_forest().

◆ hard_regs_roots

allocno_hard_regs_node_t hard_regs_roots
Roots of the forest containing hard register sets can be assigned
to allocnos.   

Referenced by finish_allocno_hard_regs_nodes_forest(), form_allocno_hard_regs_nodes_forest(), and print_hard_regs_forest().

◆ max_soft_conflict_loop_depth

const int max_soft_conflict_loop_depth = 64
IRA allocation based on graph coloring.
   Copyright (C) 2006-2024 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

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
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
To prevent soft conflict detection becoming quadratic in the
loop depth.  Only for very pathological cases, so it hardly
seems worth a --param.   

Referenced by ira_soft_conflict().

◆ node_check_tick

int node_check_tick
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 first_common_ancestor_node(), form_allocno_hard_regs_nodes_forest(), and setup_left_conflict_sizes_p().

◆ processed_coalesced_allocno_bitmap

bitmap processed_coalesced_allocno_bitmap
Bitmap used to prevent a repeated allocno processing because of

Referenced by coalesced_allocno_conflict_p(), and ira_sort_regnos_for_alter_reg().

◆ regno_coalesced_allocno_cost

int* regno_coalesced_allocno_cost
Usage cost and order number of coalesced allocno set to which
given pseudo register belongs to.   

Referenced by coalesced_pseudo_reg_freq_compare(), ira_sort_regnos_for_alter_reg(), and setup_coalesced_allocno_costs_and_nums().

◆ regno_coalesced_allocno_num

◆ regno_max_ref_mode

machine_mode* regno_max_ref_mode
Widest width in which each pseudo reg is referred to (via subreg).
It is used for sorting pseudo registers.   

Referenced by coalesced_pseudo_reg_slot_compare(), and ira_sort_regnos_for_alter_reg().

◆ slot_coalesced_allocnos_live_ranges

live_range_t* slot_coalesced_allocnos_live_ranges
Array of live ranges of size IRA_ALLOCNOS_NUM.  Live range for
given slot contains live ranges of coalesced allocnos assigned to
given slot.   

Referenced by coalesce_spill_slots(), setup_slot_coalesced_allocno_live_ranges(), and slot_coalesced_allocno_live_ranges_intersect_p().

◆ sorted_allocnos

ira_allocno_t* sorted_allocnos

◆ sorted_copies

◆ uncolorable_allocno_bucket

ira_allocno_t uncolorable_allocno_bucket

◆ uncolorable_allocnos_num

int uncolorable_allocnos_num
The current number of allocnos in the uncolorable_bucket.   

Referenced by add_allocno_to_bucket(), delete_allocno_from_bucket(), and push_allocnos_to_stack().

◆ update_cost_check

int update_cost_check
The current value of update_costs_from_copies call count.   

Referenced by initiate_cost_update(), queue_update_cost(), and start_update_cost().

◆ update_cost_queue

ira_allocno_t update_cost_queue
The first element in a queue of allocnos whose copy costs need to be
updated.  Null if the queue is empty.   

Referenced by get_next_update_cost(), queue_update_cost(), and start_update_cost().

◆ update_cost_queue_elems

struct update_cost_queue_elem* update_cost_queue_elems
A pool of elements in the queue described by update_cost_queue.
Elements are indexed by ALLOCNO_NUM.   

Referenced by finish_cost_update(), get_next_update_cost(), initiate_cost_update(), and queue_update_cost().

◆ update_cost_queue_tail

struct update_cost_queue_elem* update_cost_queue_tail
The last element in the queue described by update_cost_queue.
Not valid if update_cost_queue is null.   

Referenced by queue_update_cost().

◆ update_cost_record_pool

object_allocator< update_cost_record > update_cost_record_pool("update cost records") ( "update cost records" )
This page contains functions used to choose hard registers for
Pool for update cost records.   

Referenced by finish_update_cost_records(), free_update_cost_record_list(), and get_update_cost_record().