GCC Middle and Back End API Reference
ira-color.c File Reference

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


typedef struct allocno_hard_regsallocno_hard_regs_t
typedef struct
typedef struct allocno_color_dataallocno_color_data_t
typedef struct
typedef struct coalesce_datacoalesce_data_t


static allocno_hard_regs_t find_hard_regs ()
static allocno_hard_regs_t insert_hard_regs ()
static void init_allocno_hard_regs ()
static allocno_hard_regs_t add_allocno_hard_regs ()
static void finish_allocno_hard_regs ()
static int allocno_hard_regs_compare ()
static allocno_hard_regs_node_t create_new_allocno_hard_regs_node ()
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 ()
static void print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots, int level)
static void print_hard_regs_forest ()
void ira_debug_hard_regs_forest ()
static void remove_unused_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)
static void setup_allocno_hard_regs_subnode_index ()
static int get_allocno_hard_regs_subnodes_num ()
static void form_allocno_hard_regs_nodes_forest ()
static void finish_allocno_hard_regs_nodes_tree ()
static void finish_allocno_hard_regs_nodes_forest ()
static bool setup_left_conflict_sizes_p ()
static bool update_left_conflict_sizes_p (ira_allocno_t a, ira_allocno_t removed_a, int size)
static bool empty_profitable_hard_regs ()
static void setup_profitable_hard_regs ()
static void init_update_cost_records ()
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 ()
static void finish_update_cost_records ()
static void initiate_cost_update ()
static void finish_cost_update ()
static void start_update_cost ()
static void queue_update_cost ()
static bool get_next_update_cost ()
static bool update_allocno_cost ()
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 ()
static void update_costs_from_copies ()
static void restore_costs_from_copies ()
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 ()
static bool assign_hard_reg ()
static int allocno_spill_priority ()
static void add_allocno_to_bucket ()
static int bucket_allocno_compare_func ()
static void sort_bucket (ira_allocno_t *bucket_ptr, int(*compare_func)(const void *, const void *))
static void add_allocno_to_ordered_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
static void delete_allocno_from_bucket ()
static void push_allocno_to_stack ()
static void remove_allocno_from_bucket_and_push ()
static void push_only_colorable ()
int ira_loop_edge_freq ()
static int calculate_allocno_spill_cost ()
static int allocno_spill_priority_compare ()
static int allocno_spill_sort_compare ()
static void push_allocnos_to_stack ()
static void pop_allocnos_from_stack ()
static void setup_allocno_available_regs_num ()
static void put_allocno_into_bucket ()
static void setup_allocno_priorities ()
static int allocno_cost_compare_func ()
static void improve_allocation ()
static int allocno_priority_compare_func ()
static void color_allocnos ()
static void print_loop_title ()
static void color_pass ()
static void do_coloring ()
static void move_spill_restore ()
static void update_curr_costs ()
void ira_reassign_conflict_allocnos ()
static bool allocnos_conflict_by_live_ranges_p ()
static bool conflict_by_live_ranges_p ()
static int copy_freq_compare_func ()
static void merge_allocnos ()
static bool coalesced_allocno_conflict_p ()
static void coalesce_allocnos ()
static int coalesced_pseudo_reg_freq_compare ()
static int coalesced_pseudo_reg_slot_compare ()
static void setup_coalesced_allocno_costs_and_nums ()
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 ()
static void setup_slot_coalesced_allocno_live_ranges ()
static bool coalesce_spill_slots ()
void ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n, unsigned int *reg_max_ref_width)
void ira_mark_allocation_change ()
void ira_mark_memory_move_deletion ()
static bool allocno_reload_assign ()
static int pseudo_reg_compare ()
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, unsigned int inherent_size, unsigned int total_size)
void ira_mark_new_stack_slot ()
static int calculate_spill_cost (int *regnos, rtx in, rtx out, rtx 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)
void ira_initiate_assign ()
void ira_finish_assign ()
static void color ()
static void fast_allocation ()
void ira_color ()


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
static int node_check_tick
static allocno_hard_regs_node_t hard_regs_roots
static vec
< allocno_hard_regs_node_t
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 alloc_pool update_cost_record_pool
static bool allocated_hardreg_p [FIRST_PSEUDO_REGISTER]
static ira_allocno_t update_cost_queue
static struct
static struct
static int update_cost_check
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 unsigned int * regno_max_ref_width
static live_range_tslot_coalesced_allocnos_live_ranges

Typedef Documentation

   See above.  

IRA allocation based on graph coloring. Copyright (C) 2006-2013 Free Software Foundation, Inc. Contributed by Vladimir Makarov vmaka.nosp@m.rov@.nosp@m.redha.nosp@m.t.co.nosp@m.m.

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 allocno_hard_regs_t add_allocno_hard_regs ( )
   Add (or update info about) allocno hard registers with SET and
static void add_allocno_hard_regs_to_forest ( allocno_hard_regs_node_t roots,
allocno_hard_regs_t  hv 
   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 void add_allocno_to_bucket ( )
   Add allocno A to bucket *BUCKET_PTR.  A should be not in a bucket
   before the call.  

References allocno_color_data::in_graph_p.

static void add_allocno_to_ordered_bucket ( ira_allocno_t  allocno,
ira_allocno_t bucket_ptr 
   Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
   their priority.  ALLOCNO should be not in a bucket before the

References bucket_allocno_compare_func(), remove_allocno_from_bucket_and_push(), and sort_bucket().

Referenced by bucket_allocno_compare_func().

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::first, allocno_hard_regs_node::next, and allocno_hard_regs_node::prev.

static int allocno_cost_compare_func ( )
   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 internal_flag_ira_verbose, and ira_dump_file.

static int allocno_hard_regs_compare ( )
   Sort hard regs according to their frequency of usage. 

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

static int allocno_priority_compare_func ( )
   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_loop_tree_node::reg_pressure.

static bool allocno_reload_assign ( )
   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
static int allocno_spill_priority ( )
   Return the current spill priority of allocno A.  The less the
   number, the more preferable the allocno for spilling.  
static int allocno_spill_priority_compare ( )
   Used for sorting allocnos for spilling.  
static int allocno_spill_sort_compare ( )
   Used for sorting allocnos for spilling.  
static bool allocnos_conflict_by_live_ranges_p ( )
   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 bool assign_hard_reg ( )
   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
                      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
     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
           We need to save/restore the hard register in
           epilogue/prologue.  Therefore we increase the cost.  
     We don't need updated costs anymore: 
static int bucket_allocno_compare_func ( )
   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(), 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_dump_file, ira_print_expanded_allocno(), allocno_color_data::profitable_hard_regs, and update_left_conflict_sizes_p().

Referenced by add_allocno_to_ordered_bucket().

static int calculate_allocno_spill_cost ( )
   Calculate and return the cost of putting allocno A into memory.  

Referenced by remove_allocno_from_bucket_and_push().

static int calculate_saved_nregs ( )
   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 int calculate_spill_cost ( int *  regnos,
rtx  in,
rtx  out,
rtx  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), 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).  
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.  
     Checking only profitable hard regs.  
static void coalesce_allocnos ( )
   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
     Coalesced copies, most frequently executed first.  
         Collect the rest of copies.  

References ira_live_ranges_intersect_p(), and nr.

Referenced by coalesced_pseudo_reg_slot_compare().

static bool coalesce_spill_slots ( )
   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 bool coalesced_allocno_conflict_p ( )
   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 int coalesced_pseudo_reg_freq_compare ( )
   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 int coalesced_pseudo_reg_slot_compare ( )
   Sort pseudos according their slot numbers (putting ones with
  smaller numbers first, or last when the frame pointer is not

References bitmap_set_bit(), coalesce_allocnos(), ira_allocate(), ira_allocate_bitmap(), ira_allocnos_num, ira_free_bitmap(), ira_regno_allocno_map, max_reg_num(), and max_regno.

static void collect_allocno_hard_regs_cover ( allocno_hard_regs_node_t  first,
   Add allocno hard registers nodes starting with the forest level
   given by FIRST which contains biggest set inside SET.  
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 internal_flag_ira_verbose, and ira_dump_file.

static void color ( )
   Entry function doing color-based register allocation.  

Referenced by draw_cfg_node_succ_edges().

static void color_allocnos ( )
   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 void color_pass ( )
   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
             Use hard register class here.  ??? 
             ??? conflict costs 
                     We don't need updated costs anymore: 
                     We don't need updated costs anymore: 
static bool conflict_by_live_ranges_p ( )
   Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
   intersect.  This should be used when there is only one region.
   Currently this is used during reload.  
     Reg info caclulated by dataflow infrastructure can be different
     from one calculated by regclass.  
static int copy_freq_compare_func ( )
   The function is used to sort allocnos according to their execution
     If freqencies are equal, sort by copies, so that the results of
     qsort leave nothing to chance.  
static allocno_hard_regs_node_t create_new_allocno_hard_regs_node ( )
   Create and return allocno hard registers node containing allocno
   hard registers HV.  
static void delete_allocno_from_bucket ( )
   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(), get_loop_exit_edges(), and ira_loop_tree_node::loop.

Referenced by bucket_allocno_compare_func().

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

References bitmap_bit_p(), and ira_allocate_bitmap().

static bool empty_profitable_hard_regs ( )
   Return true if allocno A has empty profitable hard regs.  
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 allocno_hard_regs_nodes_num, and allocno_hard_regs_node::preorder_num.

static void fast_allocation ( )
   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 allocno_hard_regs_t find_hard_regs ( )
   Return allocno hard registers in the hash table equal to HV.  
static void finish_allocno_hard_regs_nodes_forest ( )
   Finish work with the forest of allocno hard registers nodes.  
static void finish_allocno_hard_regs_nodes_tree ( )
   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 void finish_cost_update ( )
   Deallocate data used by function update_costs_from_copies.  
static void finish_update_cost_records ( )
   Free memory allocated for all update cost records.  
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.  
static void form_allocno_hard_regs_nodes_forest ( )
   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
         That is a temporary storage.  
static void free_update_cost_record_list ( )
static int get_allocno_hard_regs_subnodes_num ( )
   Count all allocno hard registers nodes in tree ROOT.  
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 can not hold value of mode of allocno A.
   This covers mostly cases when multi-register value should be
static bool get_next_update_cost ( )
   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().

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.  
static void improve_allocation ( )
   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
         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
                   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
static void init_allocno_hard_regs ( )
   Initialize data concerning allocno hard registers.  

References allocno_hard_regs::cost.

static void init_update_cost_records ( )
   Initiate update cost records.  
static void initiate_cost_update ( )
   Allocate and initialize data necessary for function

Referenced by ira_reuse_stack_slot().

static allocno_hard_regs_t insert_hard_regs ( )
   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
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 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
     Add pseudos which conflict with pseudos already in
     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

References find_regno_note(), ira_regno_allocno_map, REG_N_REFS(), and reg_renumber.

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
     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
     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 void merge_allocnos ( )
   Merge two sets of coalesced allocnos given correspondingly by
   allocnos A1 and A2 (more accurately merging A2 set into A1

References ira_regno_allocno_map.

static void move_spill_restore ( )
   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
                 We have accumulated cost.  To get the real cost of
                 allocno usage in the loop we should subtract costs of
                 the subloop allocnos.  
static void pop_allocnos_from_stack ( )
   Pop the coloring stack and assign hard registers to the popped
static void print_hard_regs_forest ( )
   Print the allocno hard register forest to F.  

References allocno_hard_regs_node::next, allocno_hard_regs_node::parent, and allocno_hard_regs_node::preorder_num.

static void print_hard_regs_subforest ( FILE *  f,
allocno_hard_regs_node_t  roots,
int  level 
   Print allocno hard register subforest given by ROOTS and its LEVEL
   to F.  

Referenced by setup_allocno_hard_regs_nodes_parent().

static void print_loop_title ( )
   Output information about the loop given by its LOOP_TREE_NODE. 
static int pseudo_reg_compare ( )
   Sort pseudos according their usage frequencies (putting most
   frequently ones first).  

References count.

static void push_allocno_to_stack ( )
   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
         We will deal with the subwords individually.  
static void push_allocnos_to_stack ( )
   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

References floor_log2(), and priority().

static void push_only_colorable ( )
   Put all allocnos from colorable bucket onto the coloring stack.  

References internal_flag_ira_verbose, and ira_dump_file.

static void put_allocno_into_bucket ( )
   Put ALLOCNO in a bucket corresponding to its number and size of its
   conflicting allocnos and hard registers.  
static void queue_update_cost ( )
   Add (ALLOCNO, FROM, DIVISOR) to the end of update_cost_queue, unless
   ALLOCNO is already in the queue, or has NO_REGS class.  
static void remove_allocno_from_bucket_and_push ( )
   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 calculate_allocno_spill_cost().

Referenced by add_allocno_to_ordered_bucket().

static void remove_unused_allocno_hard_regs_nodes ( )
   Remove unused allocno hard registers nodes from forest given by its

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 void restore_costs_from_copies ( )
   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.  
static void setup_allocno_available_regs_num ( )
   Set up number of available hard registers for allocno A.  
         Checking only profitable hard regs.  
static void setup_allocno_hard_regs_nodes_parent ( allocno_hard_regs_node_t  first,
allocno_hard_regs_node_t  parent 
static void setup_allocno_hard_regs_subnode_index ( )
   Setup arrays ALLOCNO_HARD_REGS_NODES and

References add_allocno_hard_regs_to_forest().

static void setup_allocno_priorities ( )
   Set up priorities for N allocnos in array
static void setup_coalesced_allocno_costs_and_nums ( )
   for coalesced allocno sets containing allocnos with their regnos
   given in array PSEUDO_REGNOS of length N.  
static bool setup_left_conflict_sizes_p ( )
   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 void setup_profitable_hard_regs ( )
   Set up profitable hard registers for each allocno being
     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 void setup_slot_coalesced_allocno_live_ranges ( )
   Update live ranges of slot to which coalesced allocnos represented
   by ALLOCNO were assigned.  
static bool slot_coalesced_allocno_live_ranges_intersect_p ( )
   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 ira_regno_allocno_map, reg_renumber, and update_costs_from_copies().

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

Referenced by add_allocno_to_ordered_bucket().

static void start_update_cost ( )
   Start a new cost-updating pass.  

Referenced by update_allocno_cost().

static bool update_allocno_cost ( )
   Increase costs of HARD_REGNO by UPDATE_COST for ALLOCNO.  Return
   true if we really modified the cost.  

References update_cost_record::divisor, free_update_cost_record_list(), update_cost_record::hard_regno, update_cost_record::next, start_update_cost(), and update_costs_from_allocno().

static void update_conflict_hard_regno_costs ( int *  costs,
enum reg_class  aclass,
bool  decr_p 
   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 void update_costs_from_allocno ( ira_allocno_t  allocno,
int  hard_regno,
int  divisor,
bool  decr_p,
bool  record_p 
   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 update_cost_record::divisor, ira_allocno_copy::first, ira_allocno_copy::freq, get_next_update_cost(), update_cost_record::hard_regno, ira_allocate_and_copy_costs(), mult, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, and ira_allocno_copy::second.

Referenced by update_allocno_cost().

static void update_costs_from_copies ( )
   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.  

Referenced by slot_coalesced_allocno_live_ranges_intersect_p().

static void update_costs_from_prefs ( )
   Decrease preferred ALLOCNO hard register costs and costs of
   allocnos connected to ALLOCNO through copy.  
static void update_curr_costs ( )
   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 bool update_left_conflict_sizes_p ( ira_allocno_t  a,
ira_allocno_t  removed_a,
int  size 
   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 ira_allocnos, and allocno_color_data::profitable_hard_regs.

Referenced by bucket_allocno_compare_func().

Variable Documentation

bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER]
   Array whose element value is TRUE if the corresponding hard
   register was already allocated for an allocno.  
coalesce_data_t allocno_coalesce_data
   Container for storing allocno data concerning coalescing.  
bool allocno_coalesced_p
   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.  
hash_table<allocno_hard_regs_hasher> allocno_hard_regs_htab
   Hash table of unique allocno hard registers.  
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.  
int allocno_hard_regs_nodes_num
   Number of allocno hard registers nodes in the forest.  

Referenced by enumerate_allocno_hard_regs_nodes().

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
allocno_hard_regs_subnode_t allocno_hard_regs_subnodes
   Container for hard regs subnodes of all allocnos.  
vec<allocno_hard_regs_t> allocno_hard_regs_vec
   Definition of vector of allocno hard registers.  
   Vector of unique allocno hard registers.  
int* allocno_priorities
   Map: allocno number -> allocno priority.  
vec<ira_allocno_t> allocno_stack_vec
   Vec representing the stack of allocnos used during coloring.  
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.  
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.  
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
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.  
vec<allocno_hard_regs_node_t> hard_regs_node_vec
   Definition of vector of allocno hard register nodes.  
   Vector used to create the forest.  
allocno_hard_regs_node_t hard_regs_roots
   Roots of the forest containing hard register sets can be assigned
   to allocnos.  
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 finish_allocno_hard_regs_nodes_tree().

bitmap processed_coalesced_allocno_bitmap
   Bitmap used to prevent a repeated allocno processing because of
int* regno_coalesced_allocno_cost
   Usage cost and order number of coalesced allocno set to which
   given pseudo register belongs to.  
int* regno_coalesced_allocno_num
unsigned int* regno_max_ref_width
   Widest width in which each pseudo reg is referred to (via subreg).
   It is used for sorting pseudo registers.  
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.  
ira_allocno_t* sorted_allocnos
   All allocnos sorted according their priorities.  
ira_allocno_t uncolorable_allocno_bucket
   Bucket of allocnos that might be not colored currently without
int uncolorable_allocnos_num
   The current number of allocnos in the uncolorable_bucket.  
int update_cost_check
   The current value of update_costs_from_copies call count.  

Referenced by free_update_cost_record_list().

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.  
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.  
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.  
alloc_pool update_cost_record_pool
   This page contains functions used to choose hard registers for
   Pool for update cost records.