ira-color.c File Reference

Data Structures
struct	allocno_hard_regs
struct	allocno_hard_regs_node
struct	allocno_color_data
struct	allocno_hard_regs_hasher
struct	allocno_hard_regs_subnode
struct	update_cost_queue_elem
struct	coalesce_data

Typedefs
typedef struct allocno_hard_regs *	allocno_hard_regs_t
typedef struct allocno_hard_regs_node *	allocno_hard_regs_node_t
typedef struct allocno_color_data *	allocno_color_data_t
typedef struct allocno_hard_regs_subnode *	allocno_hard_regs_subnode_t
typedef struct coalesce_data *	coalesce_data_t

Functions
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	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 void	update_copy_costs ()
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 ()

Variables
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_t *	sorted_allocnos
static vec< ira_allocno_t >	allocno_stack_vec
static vec< allocno_hard_regs_t >	allocno_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_t >	hard_regs_node_vec
static int	allocno_hard_regs_nodes_num
static allocno_hard_regs_node_t *	allocno_hard_regs_nodes
static allocno_hard_regs_subnode_t	allocno_hard_regs_subnodes
static int *	allocno_hard_regs_subnode_index
static bool	allocated_hardreg_p [FIRST_PSEUDO_REGISTER]
static ira_allocno_t	update_cost_queue
static struct update_cost_queue_elem *	update_cost_queue_tail
static struct update_cost_queue_elem *	update_cost_queue_elems
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_t *	slot_coalesced_allocnos_live_ranges

---

Typedef Documentation

typedef struct allocno_color_data* allocno_color_data_t

See above.   

typedef struct allocno_hard_regs_node* allocno_hard_regs_node_t

typedef struct allocno_hard_regs_subnode* allocno_hard_regs_subnode_t

See below.   

typedef struct allocno_hard_regs* allocno_hard_regs_t

@verbatim 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 ( )

static

Add (or update info about) allocno hard registers with SET and
   COST.   

References allocno_hard_regs::cost, find_hard_regs(), hard_reg_set_empty_p(), insert_hard_regs(), ira_allocate(), and allocno_hard_regs::set.

Referenced by add_allocno_hard_regs_to_forest(), and form_allocno_hard_regs_nodes_forest().

static void add_allocno_hard_regs_to_forest ( allocno_hard_regs_node_t *  roots, allocno_hard_regs_t  hv  )

static

Add allocno hard registers HV (or its best approximation if it is
   not possible) to the forest on its level given by ROOTS.   

References add_allocno_hard_regs(), add_new_allocno_hard_regs_node_to_forest(), allocno_hard_regs::cost, create_new_allocno_hard_regs_node(), allocno_hard_regs_node::first, hard_reg_set_equal_p(), hard_reg_set_intersect_p(), hard_reg_set_subset_p(), allocno_hard_regs_node::hard_regs, allocno_hard_regs_node::next, allocno_hard_regs_node::prev, and allocno_hard_regs::set.

Referenced by form_allocno_hard_regs_nodes_forest().

static void add_allocno_to_bucket ( )

static

Add allocno A to bucket *BUCKET_PTR.  A should be not in a bucket
   before the call.   

References allocno_color_data::next_bucket_allocno, and allocno_color_data::prev_bucket_allocno.

Referenced by put_allocno_into_bucket().

static void add_allocno_to_ordered_bucket ( ira_allocno_t  allocno, ira_allocno_t *  bucket_ptr  )

static

Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
   their priority.  ALLOCNO should be not in a bucket before the
   call.   

References bucket_allocno_compare_func().

Referenced by push_allocno_to_stack().

static void add_new_allocno_hard_regs_node_to_forest ( allocno_hard_regs_node_t *  roots, allocno_hard_regs_node_t  new_node  )

static

Add allocno hard registers node NEW_NODE to the forest on its level
   given by ROOTS.   

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

Referenced by add_allocno_hard_regs_to_forest(), and form_allocno_hard_regs_nodes_forest().

static int allocno_cost_compare_func ( )

static

Sort allocnos according to the profit of usage of a hard register
   instead of memory for them.  

Referenced by improve_allocation().

static int allocno_hard_regs_compare ( )

static

Sort hard regs according to their frequency of usage.  

References allocno_hard_regs::cost.

Referenced by form_allocno_hard_regs_nodes_forest().

static int allocno_priority_compare_func ( )

static

Sort allocnos according to their priorities.   

Referenced by color_allocnos(), fast_allocation(), and ira_reassign_conflict_allocnos().

static bool allocno_reload_assign ( )

static

Try to assign a hard register (except for FORBIDDEN_REGS) to
   allocno A and return TRUE in the case of success.   

References assign_hard_reg(), caller_save_needed, internal_flag_ira_verbose, ira_dump_file, ira_hard_reg_set_intersection_p(), ira_overall_cost, mark_home_live(), reg_renumber, regno_reg_rtx, and update_curr_costs().

Referenced by ira_reassign_pseudos().

static int allocno_spill_priority ( )

inlinestatic

Return the current spill priority of allocno A.  The less the
   number, the more preferable the allocno for spilling.   

References allocno_color_data::temp.

Referenced by allocno_spill_priority_compare(), and remove_allocno_from_bucket_and_push().

static int allocno_spill_priority_compare ( )

inlinestatic

Used for sorting allocnos for spilling.   

References allocno_spill_priority().

Referenced by allocno_spill_sort_compare().

static int allocno_spill_sort_compare ( )

static

Used for sorting allocnos for spilling.   

References allocno_spill_priority_compare().

Referenced by push_allocnos_to_stack().

static bool allocnos_conflict_by_live_ranges_p ( )

static

This page contains functions used to find conflicts using allocno
   live ranges.   

Return TRUE if live ranges of allocnos A1 and A2 intersect.  It is
   used to find a conflict for new allocnos or allocnos with the
   different allocno classes.   

References ira_live_ranges_intersect_p(), and regno_reg_rtx.

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

static bool assign_hard_reg ( )

static

Choose a hard register for allocno A.  If RETRY_P is TRUE, it means
   that the function called from function
   `ira_reassign_conflict_allocnos' and `allocno_reload_assign'.  In
   this case some allocno data are not defined or updated and we
   should not touch these data.  The function returns true if we
   managed to assign a hard register to the allocno.

   To assign a hard register, first of all we calculate all conflict
   hard registers which can come from conflicting allocnos with
   already assigned hard registers.  After that we find first free
   hard register with the minimal cost.  During hard register cost
   calculation we take conflict hard register costs into account to
   give a chance for conflicting allocnos to get a better hard
   register in the future.

   If the best hard register cost is bigger than cost of memory usage
   for the allocno, we don't assign a hard register to given allocno
   at all.

   If we assign a hard register to the allocno, we update costs of the
   hard register for allocnos connected by copies to improve a chance
   to coalesce insns represented by the copies when we assign hard
   registers to the allocnos connected by the copies.   

References add_cost(), bitmap_bit_p(), calculate_saved_nregs(), check_hard_reg_p(), curr_allocno_process, get_conflict_and_start_profitable_regs(), hard_reg_set_intersect_p(), hard_reg_set_subset_p(), internal_flag_ira_verbose, ira_allocate_and_copy_costs(), ira_dump_file, ira_free_allocno_updated_costs(), ira_hard_reg_set_intersection_p(), memset(), queue_update_cost(), start_update_cost(), update_conflict_hard_regno_costs(), and update_copy_costs().

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

static int bucket_allocno_compare_func ( )

static

Compare two allocnos to define which allocno should be pushed first
   into the coloring stack.  If the return is a negative number, the
   allocno given by the first parameter will be pushed first.  In this
   case such allocno has less priority than the second one and the
   hard register will be assigned to it after assignment to the second
   one.  As the result of such assignment order, the second allocno
   has a better chance to get the best hard register.   

Referenced by add_allocno_to_ordered_bucket(), and push_only_colorable().

static int calculate_allocno_spill_cost ( )

static

Calculate and return the cost of putting allocno A into memory.   

References ira_init_register_move_cost_if_necessary(), ira_loop_edge_freq(), ira_loop_tree_node::parent, and ira_loop_tree_node::regno_allocno_map.

Referenced by push_allocnos_to_stack().

static int calculate_saved_nregs ( )

static

Return number of registers needed to be saved and restored at
   function prologue/epilogue if we allocate HARD_REGNO to hold value
   of MODE.   

Referenced by assign_hard_reg().

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  )

static

Return spill cost for pseudo-registers whose numbers are in array
   REGNOS (with a negative number as an end marker) for reload with
   given IN and OUT for INSN.  Return also number points (through
   EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
   the register pressure is high, number of references of the
   pseudo-registers (through NREFS), number of callee-clobbered
   hard-registers occupied by the pseudo-registers (through
   CALL_USED_COUNT), and the first hard regno occupied by the
   pseudo-registers (through FIRST_HARD_REGNO).   

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

Referenced by ira_better_spill_reload_regno_p().

static bool check_hard_reg_p ( ira_allocno_t  a, int  hard_regno, HARD_REG_SET *  conflict_regs, HARD_REG_SET  profitable_regs  )

inlinestatic

Return true if HARD_REGNO is ok for assigning to allocno A with
   PROFITABLE_REGS and whose objects have CONFLICT_REGS.   

Referenced by assign_hard_reg(), and improve_allocation().

static void coalesce_allocnos ( )

static

The major function for aggressive allocno coalescing.  We coalesce
   only spilled allocnos.  If some allocnos have been coalesced, we
   set up flag allocno_coalesced_p.   

References coalesced_allocno_conflict_p(), ira_allocno_copy::constraint_p, copy_freq_compare_func(), ira_allocno_copy::first, coalesce_data::first, ira_allocno_copy::freq, ira_allocno_copy::insn, internal_flag_ira_verbose, ira_allocate(), ira_allocnos, ira_copies_num, ira_dump_file, ira_equiv_no_lvalue_p(), ira_free(), merge_allocnos(), ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, ira_allocno_copy::num, and ira_allocno_copy::second.

Referenced by ira_sort_regnos_for_alter_reg().

static bool coalesce_spill_slots ( )

static

We have coalesced allocnos involving in copies.  Coalesce allocnos
   further in order to share the same memory stack slot.  Allocnos
   representing sets of allocnos coalesced before the call are given
   in array SPILLED_COALESCED_ALLOCNOS of length NUM.  Return TRUE if
   some allocnos were coalesced in the function.   

References bitmap_bit_p(), first, internal_flag_ira_verbose, ira_allocate(), ira_allocnos_num, ira_dump_file, ira_equiv_no_lvalue_p(), ira_finish_live_range_list(), ira_free(), memset(), merge_allocnos(), regstat_get_setjmp_crosses(), setup_slot_coalesced_allocno_live_ranges(), and slot_coalesced_allocno_live_ranges_intersect_p().

Referenced by ira_sort_regnos_for_alter_reg().

static bool coalesced_allocno_conflict_p ( )

static

Return TRUE if there are conflicting allocnos from two sets of
   coalesced allocnos given correspondingly by allocnos A1 and A2.  We
   use live ranges to find conflicts because conflicts are represented
   only for allocnos of the same allocno class and during the reload
   pass we coalesce allocnos for sharing stack memory slots.   

References allocnos_conflict_by_live_ranges_p(), bitmap_clear(), and bitmap_set_bit().

Referenced by coalesce_allocnos().

static int coalesced_pseudo_reg_freq_compare ( )

static

Sort pseudos according frequencies of coalesced allocno sets they
   belong to (putting most frequently ones first), and according to
   coalesced allocno set order numbers.   

Referenced by ira_sort_regnos_for_alter_reg().

static int coalesced_pseudo_reg_slot_compare ( )

static

Sort pseudos according their slot numbers (putting ones with
  smaller numbers first, or last when the frame pointer is not
  needed).   

References ira_regno_allocno_map.

Referenced by ira_sort_regnos_for_alter_reg().

static void collect_allocno_hard_regs_cover ( allocno_hard_regs_node_t  first, HARD_REG_SET  set  )

static

Add allocno hard registers nodes starting with the forest level
   given by FIRST which contains biggest set inside SET.   

References allocno_hard_regs_node::first, hard_reg_set_intersect_p(), hard_reg_set_subset_p(), allocno_hard_regs_node::hard_regs, allocno_hard_regs_node::next, and allocno_hard_regs::set.

Referenced by form_allocno_hard_regs_nodes_forest().

static int collect_spilled_coalesced_allocnos ( int *  pseudo_regnos, int  n, ira_allocno_t *  spilled_coalesced_allocnos  )

static

Collect spilled allocnos representing coalesced allocno sets (the
   first coalesced allocno).  The collected allocnos are returned
   through array SPILLED_COALESCED_ALLOCNOS.  The function returns the
   number of the collected allocnos.  The allocnos are given by their
   regnos in array PSEUDO_REGNOS of length N.   

References first, and ira_regno_allocno_map.

Referenced by ira_sort_regnos_for_alter_reg().

static void color ( )

static

Entry function doing color-based register allocation.   

References do_coloring(), ira_allocnos_num, ira_finish_assign(), ira_initiate_assign(), memset(), and move_spill_restore().

Referenced by dot_all_scops_1(), draw_cfg_node_succ_edges(), ira_color(), omega_add_zero_eq(), omega_add_zero_geq(), omega_constrain_variable_sign(), omega_constrain_variable_value(), omega_solve_eq(), sel_dump_cfg_2(), and sel_dump_cfg_edge().

static void color_allocnos ( )

static

Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
   taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP.   

References allocno_priority_compare_func(), assign_hard_reg(), empty_profitable_hard_regs(), finish_allocno_hard_regs_nodes_forest(), form_allocno_hard_regs_nodes_forest(), improve_allocation(), internal_flag_ira_verbose, IRA_ALGORITHM_PRIORITY, ira_allocnos, ira_dump_file, ira_free_allocno_updated_costs(), ira_print_expanded_allocno(), pop_allocnos_from_stack(), print_hard_regs_forest(), push_allocnos_to_stack(), put_allocno_into_bucket(), setup_allocno_priorities(), and setup_profitable_hard_regs().

Referenced by color_pass().

static void color_pass ( )

static

Color the allocnos inside loop (in the extreme case it can be all
   of the function) given the corresponding LOOP_TREE_NODE.  The
   function is called for each loop during top-down traverse of the
   loop tree.   

References ira_loop_tree_node::all_allocnos, ira_loop_tree_node::bb, bitmap_bit_p(), bitmap_clear_bit(), bitmap_copy(), color_allocnos(), curr_allocno_process, internal_flag_ira_verbose, ira_allocate(), ira_allocate_and_set_or_copy_costs(), ira_allocnos, ira_dump_file, ira_equiv_no_lvalue_p(), ira_free(), ira_free_allocno_updated_costs(), ira_init_register_move_cost_if_necessary(), ira_loop_edge_freq(), ira_reg_equiv_len, IRA_REGION_ALL, IRA_REGION_MIXED, memset(), print_loop_title(), ira_loop_tree_node::reg_pressure, ira_loop_tree_node::regno_allocno_map, ira_loop_tree_node::subloop_next, ira_loop_tree_node::subloops, and update_copy_costs().

Referenced by do_coloring().

static bool conflict_by_live_ranges_p ( )

static

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.   

References allocnos_conflict_by_live_ranges_p(), ira_loop_tree_root, and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_reuse_stack_slot().

static int copy_freq_compare_func ( )

static

The function is used to sort allocnos according to their execution
   frequencies.   

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

Referenced by coalesce_allocnos().

static allocno_hard_regs_node_t create_new_allocno_hard_regs_node ( )

static

Create and return allocno hard registers node containing allocno
   hard registers HV.   

References allocno_hard_regs_node::check, allocno_hard_regs_node::first, hard_reg_set_size(), allocno_hard_regs_node::hard_regs, allocno_hard_regs_node::hard_regs_num, ira_allocate(), allocno_hard_regs::set, and allocno_hard_regs_node::used_p.

Referenced by add_allocno_hard_regs_to_forest(), and form_allocno_hard_regs_nodes_forest().

static void delete_allocno_from_bucket ( )

static

Delete ALLOCNO from bucket *BUCKET_PTR.  It should be there before
   the call.   

Referenced by push_allocno_to_stack(), and remove_allocno_from_bucket_and_push().

static void do_coloring ( )

static

Initialize the common data for coloring and calls functions to do
   Chaitin-Briggs and regional coloring.   

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

Referenced by color().

static bool empty_profitable_hard_regs ( )

static

Return true if allocno A has empty profitable hard regs.   

References hard_reg_set_empty_p(), and allocno_color_data::profitable_hard_regs.

Referenced by color_allocnos(), improve_allocation(), and setup_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  )

static

Set up fields preorder_num starting with START_NUM in all allocno
   hard registers nodes in forest given by FIRST.  Return biggest set
   PREORDER_NUM increased by 1.   

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

Referenced by form_allocno_hard_regs_nodes_forest().

static void fast_allocation ( )

static

This page contains a simple register allocator without usage of
   allocno conflicts.  This is used for fast allocation for -O0.   

Do register allocation by not using allocno conflicts.  It uses
   only allocno live ranges.  The algorithm is close to Chow's
   priority coloring.   

References allocno_priority_compare_func(), hard_reg_set_subset_p(), internal_flag_ira_verbose, ira_allocate(), ira_allocnos_num, ira_dump_file, ira_free(), ira_hard_reg_set_intersection_p(), ira_max_point, ira_print_disposition(), live_range::next, nr, setup_allocno_priorities(), and live_range::start.

Referenced by ira_color().

static allocno_hard_regs_t find_hard_regs ( )

static

Return allocno hard registers in the hash table equal to HV.   

References hash_table< Descriptor, Allocator >::find().

Referenced by add_allocno_hard_regs().

static void finish_allocno_hard_regs ( )

static

Finalize data concerning allocno hard registers.   

References hash_table< Descriptor, Allocator >::dispose(), and ira_free().

Referenced by finish_allocno_hard_regs_nodes_forest().

static void finish_allocno_hard_regs_nodes_forest ( )

static

Finish work with the forest of allocno hard registers nodes.   

References allocno_hard_regs_subnode_index, finish_allocno_hard_regs(), finish_allocno_hard_regs_nodes_tree(), ira_free(), and allocno_hard_regs_node::next.

Referenced by color_allocnos().

static void finish_allocno_hard_regs_nodes_tree ( )

static

Free tree of allocno hard registers nodes given by its ROOT.   

References allocno_hard_regs_node::first, ira_free(), and allocno_hard_regs_node::next.

Referenced by finish_allocno_hard_regs_nodes_forest().

static void finish_cost_update ( )

static

Deallocate data used by function update_copy_costs.   

References ira_free().

Referenced by ira_finish_assign().

static allocno_hard_regs_node_t first_common_ancestor_node ( allocno_hard_regs_node_t  first, allocno_hard_regs_node_t  second  )

static

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, node_check_tick, and allocno_hard_regs_node::parent.

Referenced by form_allocno_hard_regs_nodes_forest().

static void form_allocno_hard_regs_nodes_forest ( )

static

Build the forest of allocno hard registers nodes and assign each
   allocno a node from the forest.   

References add_allocno_hard_regs(), add_allocno_hard_regs_to_forest(), add_new_allocno_hard_regs_node_to_forest(), allocno_hard_regs_compare(), allocno_hard_regs_nodes_num, allocno_hard_regs_subnode_index, collect_allocno_hard_regs_cover(), create_new_allocno_hard_regs_node(), enumerate_allocno_hard_regs_nodes(), first_common_ancestor_node(), get_allocno_hard_regs_subnodes_num(), hard_reg_set_empty_p(), allocno_color_data::hard_regs_node, allocno_color_data::hard_regs_subnodes_num, allocno_color_data::hard_regs_subnodes_start, init_allocno_hard_regs(), ira_allocate(), ira_allocnos, len, allocno_hard_regs_node::next, node_check_tick, allocno_color_data::profitable_hard_regs, remove_unused_allocno_hard_regs_nodes(), setup_allocno_hard_regs_nodes_parent(), setup_allocno_hard_regs_subnode_index(), and allocno_hard_regs_node::used_p.

Referenced by color_allocnos().

static int get_allocno_hard_regs_subnodes_num ( )

static

Count all allocno hard registers nodes in tree ROOT.   

References allocno_hard_regs_node::first, len, and allocno_hard_regs_node::next.

Referenced by form_allocno_hard_regs_nodes_forest().

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  )

inlinestatic

Set up conflicting (through CONFLICT_REGS) for each object of
   allocno A and the start allocno profitable regs (through
   START_PROFITABLE_REGS).  Remember that the start profitable regs
   exclude hard regs which can not hold value of mode of allocno A.
   This covers mostly cases when multi-register value should be
   aligned.   

Referenced by assign_hard_reg(), and improve_allocation().

static bool get_next_update_cost ( )

inlinestatic

Try to remove the first element from update_cost_queue.  Return false
   if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
   the removed element.   

References update_cost_queue_elem::divisor, update_cost_queue_elem::next, and update_cost_queue.

Referenced by update_conflict_hard_regno_costs(), and update_copy_costs().

static void improve_allocation ( )

static

We used Chaitin-Briggs coloring to assign as many pseudos as
   possible to hard registers.  Let us try to improve allocation with
   cost point of view.  This function improves the allocation by
   spilling some allocnos and assigning the freed hard registers to
   other allocnos if it decreases the overall allocation cost.   

References allocno_cost_compare_func(), assign_hard_reg(), update_cost_queue_elem::check, check_hard_reg_p(), empty_profitable_hard_regs(), get_conflict_and_start_profitable_regs(), internal_flag_ira_verbose, ira_allocnos, ira_dump_file, ira_print_expanded_allocno(), and spill_cost.

Referenced by color_allocnos().

static void init_allocno_hard_regs ( )

static

Initialize data concerning allocno hard registers.   

References hash_table< Descriptor, Allocator >::create().

Referenced by form_allocno_hard_regs_nodes_forest().

static void initiate_cost_update ( )

static

Allocate and initialize data necessary for function
   update_copy_costs.   

References ira_allocate(), ira_allocnos_num, and memset().

Referenced by ira_initiate_assign().

static allocno_hard_regs_t insert_hard_regs ( )

static

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

References hash_table< Descriptor, Allocator >::find_slot().

Referenced by add_allocno_hard_regs().

bool ira_better_spill_reload_regno_p	(	int *	regnos,
		int *	other_regnos,
		rtx	in,
		rtx	out,
		rtx	insn
	)

Return TRUE if spilling pseudo-registers whose numbers are in array
   REGNOS is better than spilling pseudo-registers with numbers in
   OTHER_REGNOS for reload with given IN and OUT for INSN.  The
   function used by the reload pass to make better register spilling
   decisions.   

References calculate_spill_cost().

Referenced by find_reg().

void ira_color

(

void

)

Entry function doing coloring.   

References color(), fast_allocation(), and ira_conflicts_p.

Referenced by ira().

void ira_debug_hard_regs_forest

(

void

)

Print the allocno hard register forest to stderr.   

References print_hard_regs_forest().

void ira_finish_assign

(

void

)

Deallocate data used by assign_hard_reg.   

References finish_cost_update(), ira_free(), and ira_free_bitmap().

Referenced by color(), and do_reload().

void ira_initiate_assign

(

void

)

Allocate and initialize data necessary for assign_hard_reg.   

References initiate_cost_update(), ira_allocate(), ira_allocate_bitmap(), and ira_allocnos_num.

Referenced by color(), and ira().

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 bitmap_bit_p(), edge_def::dest, df_get_live_in(), df_get_live_out(), get_loop_exit_edges(), loop::header, loop::latch, ira_loop_tree_node::loop, basic_block_def::preds, and edge_def::src.

Referenced by calculate_allocno_spill_cost(), color_pass(), and move_spill_restore().

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.   

References ira_overall_cost, ira_regno_allocno_map, reg_renumber, and update_copy_costs().

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

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

Referenced by calculate_needs_all_insns().

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.   

References internal_flag_ira_verbose, ira_dump_file, ira_regno_allocno_map, ira_spilled_reg_stack_slots, ira_spilled_reg_stack_slots_num, ira_spilled_reg_stack_slot::mem, ira_spilled_reg_stack_slot::spilled_regs, and ira_spilled_reg_stack_slot::width.

Referenced by alter_reg().

void ira_reassign_conflict_allocnos

(

)

Try to assign hard registers to the unassigned allocnos and
   allocnos conflicting with them or conflicting with allocnos whose
   regno >= START_REGNO.  The function is called after ira_flattening,
   so more allocnos (including ones created in ira-emit.c) will have a
   chance to get a hard register.  We use simple assignment algorithm
   based on priorities.   

References allocno_priority_compare_func(), assign_hard_reg(), bitmap_bit_p(), bitmap_set_bit(), internal_flag_ira_verbose, ira_allocate_bitmap(), ira_dump_file, ira_free_bitmap(), setup_allocno_priorities(), and update_curr_costs().

Referenced by ira().

bool ira_reassign_pseudos	(	int *	spilled_pseudo_regs,
		int	num,
		HARD_REG_SET	bad_spill_regs,
		HARD_REG_SET *	pseudo_forbidden_regs,
		HARD_REG_SET *	pseudo_previous_regs,
		bitmap	spilled
	)

Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
   NUM of them) or spilled pseudos conflicting with pseudos in
   SPILLED_PSEUDO_REGS.  Return TRUE and update SPILLED, if the
   allocation has been changed.  The function doesn't use
   BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
   PSEUDO_PREVIOUS_REGS for the corresponding pseudos.  The function
   is called by the reload pass at the end of each reload
   iteration.   

References allocno_reload_assign(), bitmap_set_bit(), internal_flag_ira_verbose, ira_dump_file, ira_mark_allocation_change(), ira_regno_allocno_map, nr, pseudo_reg_compare(), and reg_renumber.

Referenced by finish_spills().

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.   

References allocnos_conflict_by_live_ranges_p(), bitmap_bit_p(), conflict_by_live_ranges_p(), ira_allocno_copy::first, ira_allocno_copy::freq, ira_allocno_copy::insn, internal_flag_ira_verbose, ira_dump_file, ira_regno_allocno_map, ira_spilled_reg_stack_slots, ira_spilled_reg_stack_slots_num, ira_spilled_reg_stack_slot::mem, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, ira_allocno_copy::second, ira_spilled_reg_stack_slot::spilled_regs, and ira_spilled_reg_stack_slot::width.

Referenced by alter_reg().

void ira_sort_regnos_for_alter_reg	(	int *	pseudo_regnos,
		int	n,
		unsigned int *	reg_max_ref_width
	)

Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
   subsequent assigning stack slots to them in the reload pass.  To do
   this we coalesce spilled allocnos first to decrease the number of
   memory-memory move insns.  This function is called by the
   reload.   

References bitmap_set_bit(), coalesce_allocnos(), coalesce_spill_slots(), coalesced_pseudo_reg_freq_compare(), coalesced_pseudo_reg_slot_compare(), collect_spilled_coalesced_allocnos(), first, internal_flag_ira_verbose, ira_allocate(), ira_allocate_bitmap(), ira_allocnos_num, ira_dump_file, ira_equiv_no_lvalue_p(), ira_free(), ira_free_bitmap(), ira_regno_allocno_map, ira_spilled_reg_stack_slots_num, max_reg_num(), max_regno, memset(), reg_max_ref_width, and setup_coalesced_allocno_costs_and_nums().

Referenced by reload().

static void merge_allocnos ( )

static

Merge two sets of coalesced allocnos given correspondingly by
   allocnos A1 and A2 (more accurately merging A2 set into A1
   set).   

References first, last, and coalesce_data::next.

Referenced by coalesce_allocnos(), and coalesce_spill_slots().

static void move_spill_restore ( )

static

Move spill/restore code, which are to be generated in ira-emit.c,
   to less frequent points (if it is profitable) by reassigning some
   allocnos (in loop with subloops containing in another loop) to
   memory which results in longer live-range where the corresponding
   pseudo-registers will be in memory.   

References ira_loop_tree_node::bb, bitmap_bit_p(), ira_loop_tree_node::border_allocnos, ira_loop_tree_node::children, internal_flag_ira_verbose, ira_dump_file, ira_equiv_no_lvalue_p(), ira_init_register_move_cost_if_necessary(), ira_loop_edge_freq(), ira_loop_tree_node::loop_num, ira_loop_tree_node::parent, ira_loop_tree_node::regno_allocno_map, ira_loop_tree_node::subloop_next, and ira_loop_tree_node::subloops.

Referenced by color().

static void pop_allocnos_from_stack ( )

static

Pop the coloring stack and assign hard registers to the popped
   allocnos.   

References assign_hard_reg(), internal_flag_ira_verbose, ira_dump_file, and ira_print_expanded_allocno().

Referenced by color_allocnos().

static void print_hard_reg_set ( )

static

Print hard reg set SET to F.   

Referenced by print_hard_regs_subforest(), and setup_allocno_available_regs_num().

static void print_hard_regs_forest ( )

static

Print the allocno hard register forest to F.   

References print_hard_regs_subforest().

Referenced by color_allocnos(), and ira_debug_hard_regs_forest().

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

static

Print allocno hard register subforest given by ROOTS and its LEVEL
   to F.   

References allocno_hard_regs::cost, allocno_hard_regs_node::first, allocno_hard_regs_node::hard_regs, HOST_WIDEST_INT_PRINT_DEC, allocno_hard_regs_node::next, allocno_hard_regs_node::preorder_num, print_hard_reg_set(), and allocno_hard_regs::set.

Referenced by print_hard_regs_forest().

static void print_loop_title ( )

static

Output information about the loop given by its LOOP_TREE_NODE.  

References ira_loop_tree_node::all_allocnos, ira_loop_tree_node::bb, ira_loop_tree_node::border_allocnos, ira_loop_tree_node::children, edge_def::dest, loop::header, basic_block_def::index, ira_allocnos, ira_dump_file, ira_loop_tree_node::loop, loop_depth(), ira_loop_tree_node::loop_num, ira_loop_tree_node::modified_regnos, ira_loop_tree_node::next, ira_loop_tree_node::parent, reg_class_names, ira_loop_tree_node::reg_pressure, and basic_block_def::succs.

Referenced by color_pass().

static int pseudo_reg_compare ( )

static

Sort pseudos according their usage frequencies (putting most
   frequently ones first).   

Referenced by ira_reassign_pseudos().

static void push_allocno_to_stack ( )

static

Put allocno A onto the coloring stack without removing it from its
   bucket.  Pushing allocno to the coloring stack can result in moving
   conflicting allocnos from the uncolorable bucket to the colorable
   one.   

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 remove_allocno_from_bucket_and_push().

static void push_allocnos_to_stack ( )

static

Push allocnos to the coloring stack.  The order of allocnos in the
   stack defines the order for the subsequent coloring.   

References allocno_spill_sort_compare(), calculate_allocno_spill_cost(), push_only_colorable(), remove_allocno_from_bucket_and_push(), sort_bucket(), and uncolorable_allocno_bucket.

Referenced by color_allocnos().

static void push_only_colorable ( )

static

Put all allocnos from colorable bucket onto the coloring stack.   

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

Referenced by push_allocnos_to_stack().

static void put_allocno_into_bucket ( )

static

Put ALLOCNO in a bucket corresponding to its number and size of its
   conflicting allocnos and hard registers.   

References add_allocno_to_bucket(), setup_allocno_available_regs_num(), and setup_left_conflict_sizes_p().

Referenced by color_allocnos().

static void queue_update_cost ( )

inlinestatic

Add (ALLOCNO, DIVISOR) to the end of update_cost_queue, unless
   ALLOCNO is already in the queue, or has NO_REGS class.   

References update_cost_queue_elem::check, update_cost_queue_elem::divisor, update_cost_queue_elem::next, and update_cost_check.

Referenced by assign_hard_reg(), update_conflict_hard_regno_costs(), and update_copy_costs().

static void remove_allocno_from_bucket_and_push ( )

static

Put ALLOCNO onto the coloring stack and remove it from its bucket.
   The allocno is in the colorable bucket if COLORABLE_P is TRUE.   

References allocno_spill_priority(), delete_allocno_from_bucket(), internal_flag_ira_verbose, ira_dump_file, ira_print_expanded_allocno(), and push_allocno_to_stack().

Referenced by push_allocnos_to_stack(), and push_only_colorable().

static void remove_unused_allocno_hard_regs_nodes ( )

static

Remove unused allocno hard registers nodes from forest given by its
   *ROOTS.   

References allocno_hard_regs_node::first, ira_free(), last, allocno_hard_regs_node::next, allocno_hard_regs_node::prev, and allocno_hard_regs_node::used_p.

Referenced by form_allocno_hard_regs_nodes_forest().

static void setup_allocno_available_regs_num ( )

static

Set up number of available hard registers for allocno A.   

References allocno_color_data::available_regs_num, hard_reg_set_equal_p(), allocno_hard_regs_node::hard_regs, allocno_color_data::hard_regs_node, internal_flag_ira_verbose, ira_dump_file, print_hard_reg_set(), allocno_color_data::profitable_hard_regs, reg_class_names, and allocno_hard_regs::set.

Referenced by put_allocno_into_bucket().

static void setup_allocno_hard_regs_nodes_parent ( allocno_hard_regs_node_t  first, allocno_hard_regs_node_t  parent  )

static

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, and allocno_hard_regs_node::parent.

Referenced by form_allocno_hard_regs_nodes_forest().

static void setup_allocno_hard_regs_subnode_index ( )

static

Setup arrays ALLOCNO_HARD_REGS_NODES and
   ALLOCNO_HARD_REGS_SUBNODE_INDEX.   

References allocno_hard_regs_nodes_num, allocno_hard_regs_subnode_index, allocno_hard_regs_node::first, allocno_hard_regs_node::next, allocno_hard_regs_node::parent, and allocno_hard_regs_node::preorder_num.

Referenced by form_allocno_hard_regs_nodes_forest().

static void setup_allocno_priorities ( )

static

Set up priorities for N allocnos in array
   CONSIDERATION_ALLOCNOS.   

References floor_log2(), mult, and priority().

Referenced by color_allocnos(), fast_allocation(), and ira_reassign_conflict_allocnos().

static void setup_coalesced_allocno_costs_and_nums ( )

static

Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
   for coalesced allocno sets containing allocnos with their regnos
   given in array PSEUDO_REGNOS of length N.   

References first, and ira_regno_allocno_map.

Referenced by ira_sort_regnos_for_alter_reg().

static bool setup_left_conflict_sizes_p ( )

static

Set up left conflict sizes and left conflict subnodes sizes of hard
   registers subnodes of allocno A.  Return TRUE if allocno A is
   trivially colorable.   

References allocno_hard_regs_node::check, allocno_hard_regs_node::conflict_size, hard_reg_set_intersect_p(), hard_reg_set_subset_p(), allocno_hard_regs_node::hard_regs, allocno_color_data::hard_regs_node, allocno_hard_regs_node::hard_regs_num, allocno_color_data::hard_regs_subnodes_num, allocno_color_data::hard_regs_subnodes_start, allocno_hard_regs_subnode::left_conflict_size, allocno_hard_regs_subnode::left_conflict_subnodes_size, allocno_hard_regs_subnode::max_node_impact, node_check_tick, allocno_hard_regs_node::preorder_num, allocno_color_data::profitable_hard_regs, and allocno_hard_regs::set.

Referenced by put_allocno_into_bucket().

static void setup_profitable_hard_regs ( )

static

Set up profitable hard registers for each allocno being
   colored.   

References costs, empty_profitable_hard_regs(), ira_allocnos, and allocno_color_data::profitable_hard_regs.

Referenced by color_allocnos().

static void setup_slot_coalesced_allocno_live_ranges ( )

static

Update live ranges of slot to which coalesced allocnos represented
   by ALLOCNO were assigned.   

References ira_copy_live_range_list(), ira_merge_live_ranges(), and nr.

Referenced by coalesce_spill_slots().

static bool slot_coalesced_allocno_live_ranges_intersect_p ( )

static

Return TRUE if coalesced allocnos represented by ALLOCNO has live
   ranges intersected with live ranges of coalesced allocnos assigned
   to slot with number N.   

References ira_live_ranges_intersect_p(), and nr.

Referenced by coalesce_spill_slots().

static void sort_bucket ( ira_allocno_t *  bucket_ptr, int(*)(const void *, const void *)  compare_func  )

static

Sort bucket *BUCKET_PTR and return the result through
   BUCKET_PTR.   

Referenced by push_allocnos_to_stack(), and push_only_colorable().

static void start_update_cost ( )

static

Start a new cost-updating pass.   

Referenced by assign_hard_reg(), and update_copy_costs().

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

static

This function updates COSTS (decrease if DECR_P) for hard_registers
   of ACLASS by conflict costs of the unassigned allocnos
   connected by copies with allocnos in update_cost_queue.  This
   update increases chances to remove some copies.   

References update_cost_queue_elem::divisor, ira_allocno_copy::first, ira_allocno_copy::freq, get_next_update_cost(), ira_allocate_and_copy_costs(), mult, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, queue_update_cost(), and ira_allocno_copy::second.

Referenced by assign_hard_reg().

static void update_copy_costs ( )

static

Update the cost of allocnos to increase chances to remove some
   copies as the result of subsequent assignment.   

References update_cost_queue_elem::divisor, ira_allocno_copy::first, ira_allocno_copy::freq, get_next_update_cost(), ira_allocate_and_set_or_copy_costs(), ira_init_register_move_cost_if_necessary(), ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, queue_update_cost(), ira_allocno_copy::second, and start_update_cost().

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

static void update_curr_costs ( )

static

Update current hard reg costs and current conflict hard reg costs
   for allocno A.  It is done by processing its copies containing
   other allocnos already assigned.   

References ira_allocno_copy::first, ira_allocno_copy::freq, ira_allocate_and_set_or_copy_costs(), ira_free_allocno_updated_costs(), ira_init_register_move_cost_if_necessary(), ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, and ira_allocno_copy::second.

Referenced by allocno_reload_assign(), and ira_reassign_conflict_allocnos().

static bool update_left_conflict_sizes_p ( ira_allocno_t  a, ira_allocno_t  removed_a, int  size  )

static

Update left conflict sizes of hard registers subnodes of allocno A
   after removing allocno REMOVED_A with SIZE from the conflict graph.
   Return TRUE if A is trivially colorable.   

References allocno_hard_regs_nodes_num, allocno_hard_regs_subnode_index, allocno_color_data::available_regs_num, allocno_color_data::colorable_p, hard_reg_set_subset_p(), allocno_hard_regs_node::hard_regs, allocno_color_data::hard_regs_node, allocno_color_data::hard_regs_subnodes_start, allocno_hard_regs_subnode::left_conflict_size, allocno_hard_regs_subnode::left_conflict_subnodes_size, allocno_hard_regs_node::parent, allocno_hard_regs_node::preorder_num, and allocno_hard_regs::set.

Referenced by push_allocno_to_stack().

---

Variable Documentation

bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER]

static

This page contains functions used to choose hard registers for
   allocnos.   

Array whose element value is TRUE if the corresponding hard
   register was already allocated for an allocno.   

coalesce_data_t allocno_coalesce_data

static

Container for storing allocno data concerning coalescing.   

bool allocno_coalesced_p

static

This page contains code to coalesce memory stack slots used by
   spilled allocnos.  This results in smaller stack frame, better data
   locality, and in smaller code for some architectures like
   x86/x86_64 where insn size depends on address displacement value.
   On the other hand, it can worsen insn scheduling after the RA but
   in practice it is less important than smaller stack frames.   

TRUE if we coalesced some allocnos.  In other words, if we got
   loops formed by members first_coalesced_allocno and
   next_coalesced_allocno containing more one allocno.   

allocno_color_data_t allocno_color_data

static

Container for storing allocno data concerning coloring.   

hash_table<allocno_hard_regs_hasher> allocno_hard_regs_htab

static

Hash table of unique allocno hard registers.   

allocno_hard_regs_node_t* allocno_hard_regs_nodes

static

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

int allocno_hard_regs_nodes_num

static

Number of allocno hard registers nodes in the forest.   

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

int* allocno_hard_regs_subnode_index

static

Table (preorder number of allocno hard registers node in the
   forest, preorder number of allocno hard registers subnode) -> index
   of the subnode relative to the node.  -1 if it is not a
   subnode.   

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

allocno_hard_regs_subnode_t allocno_hard_regs_subnodes

static

Container for hard regs subnodes of all allocnos.   

vec<allocno_hard_regs_t> allocno_hard_regs_vec

static

Definition of vector of allocno hard registers.   

Vector of unique allocno hard registers.   

int* allocno_priorities

static

Map: allocno number -> allocno priority.   

vec<ira_allocno_t> allocno_stack_vec

static

Vec representing the stack of allocnos used during coloring.   

ira_allocno_t colorable_allocno_bucket

static

This page contains the allocator based on the Chaitin-Briggs algorithm.   

Bucket of allocnos that can colored currently without spilling.   

bitmap coloring_allocno_bitmap

static

This file contains code for regional graph coloring, spill/restore
   code placement optimization, and code helping the reload pass to do
   a better job.   

Bitmap of allocnos which should be colored.   

bitmap consideration_allocno_bitmap

static

Bitmap of allocnos which should be taken into account during
   coloring.  In general case it contains allocnos from
   coloring_allocno_bitmap plus other already colored conflicting
   allocnos.   

int curr_allocno_process

static

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().

vec<allocno_hard_regs_node_t> hard_regs_node_vec

static

Definition of vector of allocno hard register nodes.   

Vector used to create the forest.   

allocno_hard_regs_node_t hard_regs_roots

static

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

int node_check_tick

static

Used for finding a common ancestor of two allocno hard registers
   nodes in the forest.  We use the current value of
   'node_check_tick' to mark all nodes from one node to the top and
   then walking up from another node until we find a marked node.

   It is also used to figure out allocno colorability as a mark that
   we already reset value of member 'conflict_size' for the forest
   node corresponding to the processed allocno.   

Referenced by first_common_ancestor_node(), form_allocno_hard_regs_nodes_forest(), and setup_left_conflict_sizes_p().

bitmap processed_coalesced_allocno_bitmap

static

Bitmap used to prevent a repeated allocno processing because of
   coalescing.   

int* regno_coalesced_allocno_cost

static

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

int* regno_coalesced_allocno_num

static

unsigned int* regno_max_ref_width

static

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

static

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

ira_allocno_t* sorted_allocnos

static

All allocnos sorted according their priorities.   

ira_allocno_t uncolorable_allocno_bucket

static

Bucket of allocnos that might be not colored currently without
   spilling.   

Referenced by push_allocnos_to_stack().

int uncolorable_allocnos_num

static

The current number of allocnos in the uncolorable_bucket.   

int update_cost_check

static

The current value of update_copy_cost call count.   

Referenced by queue_update_cost().

ira_allocno_t update_cost_queue

static

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().

struct update_cost_queue_elem* update_cost_queue_elems

static

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

static

The last element in the queue described by update_cost_queue.
   Not valid if update_cost_queue is null.