Macros
#define	BB_TO_VISIT BB_VISITED

Functions
static ira_copy_t	find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx, ira_loop_tree_node_t)
static void	init_loop_tree_node ()
static void	create_loop_tree_nodes ()
static bool	more_one_region_p ()
static void	finish_loop_tree_node ()
static void	finish_loop_tree_nodes ()
static void	add_loop_to_tree ()
static int	setup_loop_tree_level ()
static void	form_loop_tree ()
static void	rebuild_regno_allocno_maps ()
static void	initiate_allocnos ()
static ira_object_t	ira_create_object ()
ira_allocno_t	ira_create_allocno (int regno, bool cap_p, ira_loop_tree_node_t loop_tree_node)
void	ira_set_allocno_class ()
void	ira_create_allocno_objects ()
static void	create_allocno_objects ()
static void	merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to, bool total_only)
void	ior_hard_reg_conflicts ()
bool	ira_conflict_vector_profitable_p ()
void	ira_allocate_conflict_vec ()
static void	allocate_conflict_bit_vec ()
void	ira_allocate_object_conflicts ()
static void	add_to_conflicts ()
static void	ira_add_conflict ()
static void	clear_conflicts ()
static void	compress_conflict_vec ()
static void	compress_conflict_vecs ()
void	ira_print_expanded_allocno ()
static ira_allocno_t	create_cap_allocno ()
live_range_t	ira_create_live_range (ira_object_t obj, int start, int finish, live_range_t next)
void	ira_add_live_range_to_object ()
static live_range_t	copy_live_range ()
live_range_t	ira_copy_live_range_list ()
live_range_t	ira_merge_live_ranges ()
bool	ira_live_ranges_intersect_p ()
void	ira_finish_live_range ()
void	ira_finish_live_range_list ()
void	ira_free_allocno_updated_costs ()
static void	ira_free_allocno_costs ()
static void	finish_allocno ()
static void	finish_allocnos ()
static void	initiate_copies ()
ira_copy_t	ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq, bool constraint_p, rtx insn, ira_loop_tree_node_t loop_tree_node)
void	ira_add_allocno_copy_to_list ()
void	ira_swap_allocno_copy_ends_if_necessary ()
ira_copy_t	ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq, bool constraint_p, rtx insn, ira_loop_tree_node_t loop_tree_node)
static void	print_copy ()
DEBUG_FUNCTION void	debug ()
void	ira_debug_copy ()
static void	print_copies ()
void	ira_debug_copies ()
static void	print_allocno_copies ()
void	ira_debug_allocno_copies ()
static void	finish_copy ()
static void	finish_copies ()
static void	initiate_cost_vectors ()
int *	ira_allocate_cost_vector ()
void	ira_free_cost_vector ()
static void	finish_cost_vectors ()
static vec< ira_loop_tree_node_t >	ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node, vec< ira_loop_tree_node_t > loop_preorder)
void	ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node, void(preorder_func)(ira_loop_tree_node_t), void(postorder_func)(ira_loop_tree_node_t))
static void	create_insn_allocnos ()
static void	create_bb_allocnos ()
static void	create_loop_allocnos ()
static void	create_loop_tree_node_allocnos ()
static void	propagate_modified_regnos ()
static void	propagate_allocno_info ()
static void	create_allocnos ()
static void	change_object_in_range_list ()
static void	move_allocno_live_ranges ()
static void	copy_allocno_live_ranges ()
static bool	low_pressure_loop_node_p ()
static int	loop_compare_func ()
static void	mark_loops_for_removal ()
static void	mark_all_loops_for_removal ()
static void	remove_uneccesary_loop_nodes_from_loop_tree ()
static bool	loop_is_inside_p ()
static int	regno_allocno_order_compare_func ()
static void	ira_rebuild_regno_allocno_list ()
static void	propagate_some_info_from_allocno ()
static void	remove_unnecessary_allocnos ()
static void	remove_low_level_allocnos ()
static void	remove_unnecessary_regions ()
static void	update_bad_spill_attribute ()
static void	setup_min_max_allocno_live_range_point ()
static int	object_range_compare_func ()
static void	sort_conflict_id_map ()
static void	setup_min_max_conflict_allocno_ids ()
static void	create_caps ()
ira_allocno_t	ira_parent_allocno ()
ira_allocno_t	ira_parent_or_cap_allocno ()
static bool	copy_info_to_removed_store_destinations ()
void	ira_flattening ()
static void	update_conflict_hard_reg_costs ()
bool	ira_build ()
void	ira_destroy ()

Variables
ira_loop_tree_node_t	ira_loop_tree_root
int	ira_loop_tree_height
ira_loop_tree_node_t	ira_bb_nodes
ira_loop_tree_node_t	ira_loop_nodes
unsigned int	ira_loop_nodes_count
ira_allocno_t *	ira_regno_allocno_map
ira_allocno_t *	ira_allocnos
int	ira_allocnos_num
int	ira_objects_num
ira_object_t *	ira_object_id_map
ira_copy_t *	ira_copies
int	ira_copies_num
static int	last_basic_block_before_change
static alloc_pool	allocno_pool
static alloc_pool	live_range_pool
static alloc_pool	object_pool
static vec< ira_allocno_t >	allocno_vec
static vec< ira_object_t >	ira_object_id_map_vec
static int *	conflict_check
static int	curr_conflict_check_tick
static alloc_pool	copy_pool
static vec< ira_copy_t >	copy_vec
static alloc_pool	cost_vector_pool [N_REG_CLASSES]
ira_loop_tree_node_t	ira_curr_loop_tree_node
ira_allocno_t *	ira_curr_regno_allocno_map
static basic_block	curr_bb
static vec< ira_loop_tree_node_t >	removed_loop_vec
static vec< ira_loop_tree_node_t >	children_vec
static ira_allocno_t *	regno_allocnos
static ira_allocno_t *	regno_top_level_allocno_map

Macro Definition Documentation

#define BB_TO_VISIT BB_VISITED

Referenced by ira_loop_tree_body_rev_postorder().

Function Documentation

static void add_loop_to_tree ( )

static

The following recursive function adds LOOP to the loop tree
   hierarchy.  LOOP is added only once.  If LOOP is NULL we adding
   loop designating the whole function when CFG loops are not
   built.

References ira_loop_tree_node::bb, ira_loop_tree_node::children, ira_loop_tree_node::loop, ira_loop_tree_node::loop_num, loop_outer(), ira_loop_tree_node::next, 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 form_loop_tree().

static void add_to_conflicts ( )

static

Add OBJ2 to the conflicts of OBJ1.

References ira_allocate(), ira_free(), memcpy(), memset(), and loop::num.

Referenced by ira_add_conflict().

static void allocate_conflict_bit_vec ( )

static

Allocate and initialize the conflict bit vector of OBJ.

References ira_allocate(), and memset().

Referenced by ira_allocate_object_conflicts().

static void change_object_in_range_list ( )

static

The page contains function to remove some regions from a separate
   register allocation.  We remove regions whose separate allocation
   will hardly improve the result.  As a result we speed up regional
   register allocation.

The function changes the object in range list given by R to OBJ.

References live_range::next, and live_range::object.

Referenced by copy_allocno_live_ranges(), and move_allocno_live_ranges().

static void clear_conflicts ( )

static

Clear all conflicts of OBJ.

References memset().

Referenced by ira_flattening().

static void compress_conflict_vec ( )

static

Remove duplications in conflict vector of OBJ.

References conflict_check, and curr_conflict_check_tick.

Referenced by compress_conflict_vecs().

static void compress_conflict_vecs ( )

static

Remove duplications in conflict vectors of all allocnos.

References compress_conflict_vec(), conflict_check, curr_conflict_check_tick, ira_allocate(), ira_free(), ira_objects_num, and memset().

Referenced by ira_flattening().

static void copy_allocno_live_ranges ( )

static

References change_object_in_range_list(), internal_flag_ira_verbose, ira_copy_live_range_list(), ira_dump_file, ira_merge_live_ranges(), and ira_print_live_range_list().

Referenced by copy_info_to_removed_store_destinations().

static bool copy_info_to_removed_store_destinations ( )

static

Process all allocnos originated from pseudo REGNO and copy live
   ranges, hard reg conflicts, and allocno stack reg attributes from
   low level allocnos to final allocnos which are destinations of
   removed stores at a loop exit.  Return true if we copied live
   ranges.

References allocno_emit_reg(), copy_allocno_live_ranges(), merge_hard_reg_conflicts(), ira_loop_tree_node::parent, and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_flattening().

static live_range_t copy_live_range ( )

static

Copy allocno live range R and return the result.

References pool_alloc().

Referenced by ira_copy_live_range_list().

static void create_allocno_objects ( )

static

For each allocno, set ALLOCNO_NUM_OBJECTS and create the
   ALLOCNO_OBJECT structures.  This must be called after the allocno
   classes are known.

References ira_create_allocno_objects().

Referenced by ira_build().

static void create_allocnos ( )

static

Create allocnos corresponding to pseudo-registers in the current
   function.  Traverse the loop tree for this.

References create_loop_tree_node_allocnos(), ira_traverse_loop_tree(), and propagate_modified_regnos().

Referenced by ira_build().

static void create_bb_allocnos ( )

static

Create allocnos corresponding to pseudo-registers living in the
   basic block represented by the corresponding loop tree node
   BB_NODE.

References ira_loop_tree_node::bb, create_insn_allocnos(), df_get_live_in(), and ira_create_allocno().

Referenced by create_loop_tree_node_allocnos().

static ira_allocno_t create_cap_allocno ( )

static

Create and return the cap representing allocno A in the
   parent loop.

References internal_flag_ira_verbose, ira_allocate_and_copy_costs(), ira_create_allocno(), ira_create_allocno_objects(), ira_dump_file, ira_print_expanded_allocno(), ira_set_allocno_class(), merge_hard_reg_conflicts(), and ira_loop_tree_node::parent.

Referenced by create_caps().

static void create_caps ( )

static

References bitmap_bit_p(), ira_loop_tree_node::border_allocnos, and create_cap_allocno().

Referenced by ira_build().

static void create_insn_allocnos ( )

static

This recursive function creates allocnos corresponding to
   pseudo-registers containing in X.  True OUTPUT_P means that X is
   a lvalue.

References bitmap_set_bit(), ira_create_allocno(), ira_loop_tree_node::modified_regnos, and SET.

Referenced by create_bb_allocnos().

static void create_loop_allocnos ( )

static

Create allocnos corresponding to pseudo-registers living on edge E
   (a loop entry or exit).  Also mark the allocnos as living on the
   loop border.

References bitmap_bit_p(), bitmap_set_bit(), ira_loop_tree_node::border_allocnos, edge_def::dest, df_get_live_in(), df_get_live_out(), ira_create_allocno(), ira_loop_tree_node::parent, ira_loop_tree_node::regno_allocno_map, and edge_def::src.

Referenced by create_loop_tree_node_allocnos().

static void create_loop_tree_node_allocnos ( )

static

Create allocnos corresponding to pseudo-registers living in loop
   represented by the corresponding loop tree node LOOP_NODE.  This
   function is called by ira_traverse_loop_tree.

References ira_loop_tree_node::bb, create_bb_allocnos(), create_loop_allocnos(), get_loop_exit_edges(), loop::header, loop::latch, ira_loop_tree_node::loop, basic_block_def::preds, and edge_def::src.

Referenced by create_allocnos().

static void create_loop_tree_nodes ( )

static

The following function allocates the loop tree nodes.  If
   CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
   the root which corresponds the all function) will be not allocated
   but nodes will still be allocated for basic blocks.

References ira_loop_tree_node::all_allocnos, ira_loop_tree_node::border_allocnos, cfun, edge_def::flags, get_loop_exit_edges(), get_loops(), loop::header, init_loop_tree_node(), ira_allocate(), ira_loop_nodes_count, last_basic_block_before_change, loop::latch, ira_loop_tree_node::local_copies, loop_outer(), memset(), ira_loop_tree_node::modified_regnos, loop::num, number_of_loops(), basic_block_def::preds, ira_loop_tree_node::reg_pressure, ira_loop_tree_node::regno_allocno_map, and edge_def::src.

Referenced by ira_build().

DEBUG_FUNCTION void debug ( )

References print_copy().

static ira_copy_t find_allocno_copy	(	ira_allocno_t	a1,
		ira_allocno_t	a2,
		rtx	insn,
		ira_loop_tree_node_t	loop_tree_node
	)

static

@verbatim Building internal representation for IRA.

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

Return copy connecting A1 and A2 and originated from INSN of
   LOOP_TREE_NODE if any.

References ira_allocno_copy::first, ira_allocno_copy::insn, ira_allocno_copy::loop_tree_node, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, and ira_allocno_copy::second.

Referenced by ira_add_allocno_copy().

static void finish_allocno ( )

static

Free the memory allocated for allocno A.

References ira_free_allocno_costs(), and pool_free().

Referenced by finish_allocnos(), ira_flattening(), remove_low_level_allocnos(), and remove_unnecessary_allocnos().

static void finish_allocnos ( )

static

Free the memory allocated for all allocnos.

References finish_allocno(), free_alloc_pool(), and ira_free().

Referenced by ira_destroy().

static void finish_copies ( )

static

Free memory allocated for all copies.

References finish_copy(), and free_alloc_pool().

Referenced by ira_destroy().

static void finish_copy ( )

static

The function frees memory allocated for copy CP.

References pool_free().

Referenced by finish_copies(), and ira_flattening().

static void finish_cost_vectors ( )

static

Finish work with hard register cost vectors.  Release allocation
   pool for each allocno class.

References free_alloc_pool().

Referenced by ira_destroy().

static void finish_loop_tree_node ( )

static

Free the loop tree node of a loop.

References ira_loop_tree_node::all_allocnos, ira_loop_tree_node::bb, ira_loop_tree_node::border_allocnos, ira_free(), ira_free_bitmap(), ira_loop_tree_node::local_copies, ira_loop_tree_node::modified_regnos, and ira_loop_tree_node::regno_allocno_map.

Referenced by finish_loop_tree_nodes(), and remove_unnecessary_regions().

static void finish_loop_tree_nodes ( )

static

Free the loop tree nodes.

References ira_loop_tree_node::all_allocnos, ira_loop_tree_node::border_allocnos, finish_loop_tree_node(), ira_free(), ira_free_bitmap(), ira_loop_nodes_count, last_basic_block_before_change, ira_loop_tree_node::local_copies, ira_loop_tree_node::modified_regnos, and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_destroy().

static void form_loop_tree ( )

static

Create the loop tree.  The algorithm is designed to provide correct
   order of loops (they are ordered by their last loop BB) and basic
   blocks in the chain formed by member next.

References add_loop_to_tree(), ira_loop_tree_node::bb, ira_loop_tree_node::children, basic_block_def::index, ira_loop_tree_height, ira_loop_tree_node::loop, basic_block_def::loop_father, loop_outer(), ira_loop_tree_node::next, loop::num, ira_loop_tree_node::parent, ira_loop_tree_node::regno_allocno_map, setup_loop_tree_level(), ira_loop_tree_node::subloop_next, and ira_loop_tree_node::subloops.

Referenced by ira_build().

static void init_loop_tree_node ( )

static

Initialize some members in loop tree node NODE.  Use LOOP_NUM for
   the member loop_num.

References ira_loop_tree_node::all_allocnos, ira_loop_tree_node::border_allocnos, ira_loop_tree_node::children, ira_allocate(), ira_allocate_bitmap(), ira_loop_tree_node::local_copies, ira_loop_tree_node::loop_num, max_reg_num(), max_regno, memset(), ira_loop_tree_node::modified_regnos, ira_loop_tree_node::reg_pressure, ira_loop_tree_node::regno_allocno_map, and ira_loop_tree_node::subloops.

Referenced by create_loop_tree_nodes().

static void initiate_allocnos ( )

static

Initialize data concerning allocnos.

References create_alloc_pool(), ira_allocate(), ira_allocnos_num, ira_objects_num, max_reg_num(), and memset().

Referenced by ira_build().

static void initiate_copies ( )

static

The function initializes data concerning allocno copies.

References create_alloc_pool(), get_max_uid(), and ira_copies_num.

Referenced by ira_build().

static void initiate_cost_vectors ( )

static

The function initiates work with hard register cost vectors.  It
   creates allocation pool for each allocno class.

References create_alloc_pool().

Referenced by ira_build().

void ior_hard_reg_conflicts ( )

Update hard register conflict information for all objects associated with
   A to include the regs in SET.

Referenced by add_range_and_copies_from_move_list(), and ira_build().

ira_copy_t ira_add_allocno_copy	(	ira_allocno_t	first,
		ira_allocno_t	second,
		int	freq,
		bool	constraint_p,
		rtx	insn,
		ira_loop_tree_node_t	loop_tree_node
	)

Create (or update frequency if the copy already exists) and return
   the copy of allocnos FIRST and SECOND with frequency FREQ
   corresponding to move insn INSN (if any) and originated from
   LOOP_TREE_NODE.

References find_allocno_copy(), ira_allocno_copy::freq, ira_add_allocno_copy_to_list(), ira_create_copy(), and ira_swap_allocno_copy_ends_if_necessary().

Referenced by add_range_and_copies_from_move_list(), process_regs_for_copy(), and propagate_copies().

void ira_add_allocno_copy_to_list ( )

Attach a copy CP to allocnos involved into the copy.

References first, ira_allocno_copy::first, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, ira_allocno_copy::prev_first_allocno_copy, ira_allocno_copy::prev_second_allocno_copy, and ira_allocno_copy::second.

Referenced by ira_add_allocno_copy(), and ira_flattening().

static void ira_add_conflict ( )

static

Add OBJ1 to the conflicts of OBJ2 and vice versa.

References add_to_conflicts().

Referenced by ira_flattening().

void ira_add_live_range_to_object ( )

Create a new live range for OBJECT and queue it at the head of its
   live range list.

References ira_create_live_range().

Referenced by add_range_and_copies_from_move_list(), and make_object_born().

void ira_allocate_conflict_vec ( )

Allocates and initialize the conflict vector of OBJ for NUM
   conflicting objects.

References ira_allocate().

Referenced by build_object_conflicts(), and ira_allocate_object_conflicts().

int* ira_allocate_cost_vector ( )

Allocate and return a cost vector VEC for ACLASS.

References pool_alloc().

Referenced by ira_allocate_and_accumulate_costs(), ira_allocate_and_copy_costs(), ira_allocate_and_set_costs(), ira_allocate_and_set_or_copy_costs(), and setup_allocno_class_and_costs().

void ira_allocate_object_conflicts ( )

Allocate and initialize the conflict vector or conflict bit vector
   of OBJ for NUM conflicting allocnos whatever is more profitable.

References allocate_conflict_bit_vec(), ira_allocate_conflict_vec(), and ira_conflict_vector_profitable_p().

Referenced by add_range_and_copies_from_move_list().

bool ira_build ( void )

Create a internal representation (IR) for IRA (allocnos, copies,
   loop tree nodes).  The function returns TRUE if we generate loop
   structure (besides nodes representing all function and the basic
   blocks) for regional allocation.  A true return means that we
   really need to flatten IR before the reload.

References cfun, create_allocno_objects(), create_allocnos(), create_caps(), create_loop_tree_nodes(), df_analyze(), form_loop_tree(), initiate_allocnos(), initiate_copies(), initiate_cost_vectors(), internal_flag_ira_verbose, ior_hard_reg_conflicts(), ira_allocnos_num, ira_build_conflicts(), ira_compress_allocno_live_ranges(), ira_conflicts_p, ira_copies_num, ira_costs(), ira_create_allocno_live_ranges(), ira_dump_file, ira_max_point, ira_tune_allocno_costs(), more_one_region_p(), live_range::next, nr, number_of_loops(), print_copies(), propagate_allocno_info(), remove_unnecessary_regions(), setup_min_max_allocno_live_range_point(), setup_min_max_conflict_allocno_ids(), sort_conflict_id_map(), update_bad_spill_attribute(), and update_conflict_hard_reg_costs().

Referenced by ira().

bool ira_conflict_vector_profitable_p ( )

Return TRUE if a conflict vector with NUM elements is more
   profitable than a conflict bit vector for OBJ.

Referenced by build_object_conflicts(), and ira_allocate_object_conflicts().

live_range_t ira_copy_live_range_list ( )

Copy allocno live range list given by its head R and return the
   result.

References copy_live_range(), first, last, and live_range::next.

Referenced by copy_allocno_live_ranges(), and setup_slot_coalesced_allocno_live_ranges().

ira_allocno_t ira_create_allocno	(	int	regno,
		bool	cap_p,
		ira_loop_tree_node_t	loop_tree_node
	)

Create and return the allocno corresponding to REGNO in
   LOOP_TREE_NODE.  Add the allocno to the list of allocnos with the
   same regno if CAP_P is FALSE.

References ira_loop_tree_node::all_allocnos, bitmap_set_bit(), ira_allocnos_num, pool_alloc(), and ira_loop_tree_node::regno_allocno_map.

Referenced by create_bb_allocnos(), create_cap_allocno(), create_insn_allocnos(), create_loop_allocnos(), and create_new_allocno().

void ira_create_allocno_objects ( )

Determine the number of objects we should associate with allocno A
   and allocate them.

References ira_create_object().

Referenced by create_allocno_objects(), create_cap_allocno(), and modify_move_list().

ira_copy_t ira_create_copy	(	ira_allocno_t	first,
		ira_allocno_t	second,
		int	freq,
		bool	constraint_p,
		rtx	insn,
		ira_loop_tree_node_t	loop_tree_node
	)

Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
   SECOND, FREQ, CONSTRAINT_P, and INSN.

References ira_allocno_copy::constraint_p, first, ira_allocno_copy::first, ira_allocno_copy::freq, ira_allocno_copy::insn, ira_copies_num, ira_allocno_copy::loop_tree_node, ira_allocno_copy::num, pool_alloc(), and ira_allocno_copy::second.

Referenced by ira_add_allocno_copy().

live_range_t ira_create_live_range	(	ira_object_t	obj,
		int	start,
		int	finish,
		live_range_t	next
	)

Create and return a live range for OBJECT with given attributes.

References live_range::finish, loop::next, live_range::next, live_range::object, pool_alloc(), and live_range::start.

Referenced by ira_add_live_range_to_object().

static ira_object_t ira_create_object ( )

static

Create and return an object corresponding to a new allocno A.

References ira_objects_num, and pool_alloc().

Referenced by ira_create_allocno_objects().

void ira_debug_allocno_copies ( )

Print info about copies involving allocno A into stderr.

References print_allocno_copies().

void ira_debug_copies ( void )

Print info about all copies into stderr.

References print_copies().

void ira_debug_copy ( )

Print info about copy CP into stderr.

References print_copy().

void ira_destroy ( void )

Release the data created by function ira_build.

References finish_allocnos(), finish_copies(), finish_cost_vectors(), finish_loop_tree_nodes(), and ira_finish_allocno_live_ranges().

Referenced by do_reload().

void ira_finish_live_range ( )

Free allocno live range R.

References pool_free().

Referenced by ira_finish_live_range_list(), ira_merge_live_ranges(), and remove_some_program_points_and_update_live_ranges().

void ira_finish_live_range_list ( )

Free list of allocno live ranges starting with R.

References ira_finish_live_range(), and live_range::next.

Referenced by coalesce_spill_slots(), and ira_free_allocno_costs().

void ira_flattening ( )

Flatten the IR.  In other words, this function transforms IR as if
   it were built with one region (without loops).  We could make it
   much simpler by rebuilding IR with one region, but unfortunately it
   takes a lot of time.  MAX_REGNO_BEFORE_EMIT and
   IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
   IRA_MAX_POINT before emitting insns on the loop borders.

References allocno_emit_reg(), clear_conflicts(), compress_conflict_vecs(), copy_info_to_removed_store_destinations(), finish_allocno(), finish_copy(), live_range::finish_next, first, ira_allocno_copy::first, internal_flag_ira_verbose, ira_add_allocno_copy_to_list(), ira_add_conflict(), ira_allocate(), ira_compress_allocno_live_ranges(), ira_dump_file, ira_finish_point_ranges, ira_free(), ira_free_allocno_updated_costs(), ira_loop_tree_root, ira_max_point, ira_objects_num, ira_parent_allocno(), ira_rebuild_start_finish_chains(), ira_start_point_ranges, ira_swap_allocno_copy_ends_if_necessary(), ira_allocno_copy::loop_tree_node, max_reg_num(), ira_emit_data::mem_optimized_dest, ira_emit_data::mem_optimized_dest_p, memset(), merge_hard_reg_conflicts(), move_allocno_live_ranges(), live_range::next, ira_allocno_copy::num, live_range::object, objects_live, rebuild_regno_allocno_maps(), ira_emit_data::reg, ira_loop_tree_node::regno_allocno_map, ira_allocno_copy::second, ira_emit_data::somewhere_renamed_p, sparseset_alloc(), sparseset_clear_bit(), sparseset_set_bit(), and live_range::start_next.

Referenced by ira().

static void ira_free_allocno_costs ( )

static

Free and nullify all cost vectors allocated earlier for allocno
   A.

References ira_finish_live_range_list(), ira_free(), ira_free_cost_vector(), and pool_free().

Referenced by finish_allocno().

void ira_free_allocno_updated_costs ( )

Free updated register costs of allocno A.

References ira_free_cost_vector().

Referenced by assign_hard_reg(), color_allocnos(), color_pass(), ira_flattening(), setup_allocno_assignment_flags(), setup_reg_renumber(), and update_curr_costs().

void ira_free_cost_vector ( )

Free a cost vector VEC for ACLASS.

References pool_free().

Referenced by ira_free_allocno_costs(), and ira_free_allocno_updated_costs().

bool ira_live_ranges_intersect_p ( )

Return TRUE if live ranges R1 and R2 intersect.

References live_range::finish, live_range::next, and live_range::start.

Referenced by allocnos_conflict_by_live_ranges_p(), and slot_coalesced_allocno_live_ranges_intersect_p().

static vec<ira_loop_tree_node_t> ira_loop_tree_body_rev_postorder	(	ira_loop_tree_node_t	loop_node,
		vec< ira_loop_tree_node_t >	loop_preorder
	)

static

Compute a post-ordering of the reverse control flow of the loop body
   designated by the children nodes of LOOP_NODE, whose body nodes in
   pre-order are input as LOOP_PREORDER.  Return a VEC with a post-order
   of the reverse loop body.

   For the post-order of the reverse CFG, we visit the basic blocks in
   LOOP_PREORDER array in the reverse order of where they appear.
   This is important: We do not just want to compute a post-order of
   the reverse CFG, we want to make a best-guess for a visiting order that
   minimizes the number of chain elements per allocno live range.  If the
   blocks would be visited in a different order, we would still compute a
   correct post-ordering but it would be less likely that two nodes
   connected by an edge in the CFG are neighbours in the topsort.

References ira_loop_tree_node::bb, BB_TO_VISIT, basic_block_def::flags, basic_block_def::index, basic_block_def::preds, edge_def::src, and vNULL.

Referenced by ira_traverse_loop_tree().

live_range_t ira_merge_live_ranges ( )

Merge ranges R1 and R2 and returns the result.  The function
   maintains the order of ranges and tries to minimize number of the
   result ranges.

References live_range::finish, first, ira_finish_live_range(), last, live_range::next, and live_range::start.

Referenced by copy_allocno_live_ranges(), move_allocno_live_ranges(), and setup_slot_coalesced_allocno_live_ranges().

ira_allocno_t ira_parent_allocno ( )

Find the allocno that corresponds to A at a level one higher up in the
   loop tree.  Returns NULL if A is a cap, or if it has no parent.

References ira_loop_tree_node::parent, and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_flattening(), and ira_parent_or_cap_allocno().

ira_allocno_t ira_parent_or_cap_allocno ( )

Find the allocno that corresponds to A at a level one higher up in the
   loop tree.  If ALLOCNO_CAP is set for A, return that.

References ira_parent_allocno().

Referenced by build_object_conflicts(), process_regs_for_copy(), and propagate_copies().

void ira_print_expanded_allocno ( )

This recursive function outputs allocno A and if it is a cap the
   function outputs its members.

References basic_block_def::index, and ira_dump_file.

Referenced by color_allocnos(), create_cap_allocno(), improve_allocation(), pop_allocnos_from_stack(), push_allocno_to_stack(), and remove_allocno_from_bucket_and_push().

static void ira_rebuild_regno_allocno_list ( )

static

Restore allocno order for REGNO in the regno allocno list.

References internal_flag_ira_verbose, ira_dump_file, and regno_allocno_order_compare_func().

Referenced by remove_unnecessary_allocnos().

void ira_set_allocno_class ( )

Set up register class for A and update its conflict hard
   registers.

Referenced by create_cap_allocno(), modify_move_list(), and setup_allocno_class_and_costs().

void ira_swap_allocno_copy_ends_if_necessary ( )

Make a copy CP a canonical copy where number of the
   first allocno is less than the second one.

References ira_allocno_copy::first, ira_allocno_copy::next_first_allocno_copy, ira_allocno_copy::next_second_allocno_copy, ira_allocno_copy::prev_first_allocno_copy, ira_allocno_copy::prev_second_allocno_copy, and ira_allocno_copy::second.

Referenced by ira_add_allocno_copy(), and ira_flattening().

void ira_traverse_loop_tree	(	bool	bb_p,
		ira_loop_tree_node_t	loop_node,
		void(*)(ira_loop_tree_node_t)	preorder_func,
		void(*)(ira_loop_tree_node_t)	postorder_func
	)

This recursive function traverses loop tree with root LOOP_NODE
   calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
   correspondingly in preorder and postorder.  The function sets up
   IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP.  If BB_P,
   basic block nodes of LOOP_NODE is also processed (before its
   subloop nodes).
   
   If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
   the loop are passed in the *reverse* post-order of the *reverse*
   CFG.  This is only used by ira_create_allocno_live_ranges, which
   wants to visit basic blocks in this order to minimize the number
   of elements per live range chain.
   Note that the loop tree nodes are still visited in the normal,
   forward post-order of  the loop tree.

References ira_loop_tree_node::bb, ira_loop_tree_node::children, ira_loop_tree_body_rev_postorder(), ira_traverse_loop_tree(), ira_loop_tree_node::next, ira_loop_tree_node::regno_allocno_map, ira_loop_tree_node::subloop_next, ira_loop_tree_node::subloops, and vNULL.

Referenced by create_allocnos(), do_coloring(), find_costs_and_classes(), ira_build_conflicts(), ira_create_allocno_live_ranges(), ira_emit(), ira_traverse_loop_tree(), and setup_allocno_class_and_costs().

static int loop_compare_func ( )

static

Sort loops for marking them for removal.  We put already marked
   loops first, then less frequent loops next, and then outer loops
   next.

References basic_block_def::frequency, loop::header, ira_loop_tree_node::loop, loop_depth(), ira_loop_tree_node::loop_num, ira_loop_tree_node::parent, and ira_loop_tree_node::to_remove_p.

Referenced by mark_loops_for_removal().

static bool loop_is_inside_p ( )

static

Return TRUE if NODE is inside PARENT.

References ira_loop_tree_node::parent.

Referenced by regno_allocno_order_compare_func().

static bool low_pressure_loop_node_p ( )

static

Return TRUE if NODE represents a loop with low register
   pressure.

References ira_loop_tree_node::bb, and ira_loop_tree_node::reg_pressure.

Referenced by mark_loops_for_removal().

static void mark_all_loops_for_removal ( )

static

Mark all loops but root for removing.

References cfun, basic_block_def::frequency, get_loops(), loop::header, basic_block_def::index, internal_flag_ira_verbose, ira_dump_file, ira_loop_tree_node::loop, loop_depth(), and ira_loop_tree_node::to_remove_p.

Referenced by remove_unnecessary_regions().

static void mark_loops_for_removal ( )

static

Mark loops which should be removed from regional allocation.  We
   remove a loop with low register pressure inside another loop with
   register pressure.  In this case a separate allocation of the loop
   hardly helps (for irregular register file architecture it could
   help by choosing a better hard register in the loop but we prefer
   faster allocation even in this case).  We also remove cheap loops
   if there are more than IRA_MAX_LOOPS_NUM of them.  Loop with EH
   exit or enter edges are removed too because the allocation might
   require put pseudo moves on the EH edges (we could still do this
   for pseudos with caller saved hard registers in some cases but it
   is impossible to say here or during top-down allocation pass what
   hard register the pseudos get finally).

References cfun, basic_block_def::frequency, get_loops(), loop::header, basic_block_def::index, internal_flag_ira_verbose, ira_allocate(), ira_dump_file, ira_free(), ira_loop_tree_node::loop, loop_compare_func(), loop_depth(), low_pressure_loop_node_p(), number_of_loops(), ira_loop_tree_node::to_remove_p, and vec_safe_iterate().

Referenced by remove_unnecessary_regions().

static void merge_hard_reg_conflicts	(	ira_allocno_t	from,
		ira_allocno_t	to,
		bool	total_only
	)

static

Merge hard register conflict information for all objects associated with
   allocno TO into the corresponding objects associated with FROM.
   If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS.

Referenced by copy_info_to_removed_store_destinations(), create_cap_allocno(), ira_flattening(), propagate_allocno_info(), and propagate_some_info_from_allocno().

static bool more_one_region_p ( )

static

The function returns TRUE if there are more one allocation
   region.

References cfun, get_loops(), ira_loop_tree_node::loop, and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_build().

static void move_allocno_live_ranges ( )

static

Move all live ranges associated with allocno FROM to allocno TO.

References change_object_in_range_list(), internal_flag_ira_verbose, ira_dump_file, ira_merge_live_ranges(), and ira_print_live_range_list().

Referenced by ira_flattening(), remove_low_level_allocnos(), and remove_unnecessary_allocnos().

static int object_range_compare_func ( )

static

Sort allocnos according to their live ranges.  Allocnos with
   smaller allocno class are put first unless we use priority
   coloring.  Allocnos with the same class are ordered according
   their start (min).  Allocnos with the same start are ordered
   according their finish (max).

Referenced by sort_conflict_id_map().

static void print_allocno_copies ( )

static

Print info about copies involving allocno A into file F.

References ira_allocno_copy::first, ira_allocno_copy::freq, 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_debug_allocno_copies().

static void print_copies ( )

static

Print info about all copies into file F.

References print_copy().

Referenced by ira_build(), and ira_debug_copies().

static void print_copy ( )

static

Print info about copy CP into file F.

References ira_allocno_copy::constraint_p, ira_allocno_copy::first, ira_allocno_copy::freq, ira_allocno_copy::insn, ira_allocno_copy::num, and ira_allocno_copy::second.

Referenced by debug(), ira_debug_copy(), and print_copies().

static void propagate_allocno_info ( )

static

Propagate new info about allocno A (see comments about accumulated
   info in allocno definition) to the corresponding allocno on upper
   loop tree level.  So allocnos on upper levels accumulate
   information about the corresponding allocnos in nested regions.
   The new info means allocno info finally calculated in this
   file.

References bitmap_bit_p(), ira_allocate_and_accumulate_costs(), IRA_REGION_ALL, IRA_REGION_MIXED, max_reg_num(), merge_hard_reg_conflicts(), and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_build().

static void propagate_modified_regnos ( )

static

Propagate information about allocnos modified inside the loop given
   by its LOOP_TREE_NODE to its parent.

References ira_loop_tree_node::bb, bitmap_ior_into(), ira_loop_tree_node::modified_regnos, and ira_loop_tree_node::parent.

Referenced by create_allocnos().

static void propagate_some_info_from_allocno ( )

static

Propagate info from allocno FROM_A to allocno A.

References ira_allocate_and_accumulate_costs(), and merge_hard_reg_conflicts().

Referenced by remove_low_level_allocnos(), and remove_unnecessary_allocnos().

static void rebuild_regno_allocno_maps ( )

static

Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
   tree nodes.

References cfun, get_loops(), ira_allocate(), ira_free(), max_reg_num(), max_regno, memset(), and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_flattening().

static int regno_allocno_order_compare_func ( )

static

Sort allocnos according to their order in regno allocno list.

References loop_is_inside_p().

Referenced by ira_rebuild_regno_allocno_list().

static void remove_low_level_allocnos ( )

static

Remove allocnos from all loops but the root.

References finish_allocno(), ira_loop_tree_root, ira_rebuild_start_finish_chains(), move_allocno_live_ranges(), ira_loop_tree_node::parent, propagate_some_info_from_allocno(), and ira_loop_tree_node::regno_allocno_map.

Referenced by remove_unnecessary_regions().

static void remove_uneccesary_loop_nodes_from_loop_tree ( )

static

Remove subregions of NODE if their separate allocation will not
   improve the result.

References ira_loop_tree_node::bb, ira_loop_tree_node::children, ira_loop_tree_node::next, ira_loop_tree_node::parent, ira_loop_tree_node::subloop_next, ira_loop_tree_node::subloops, and ira_loop_tree_node::to_remove_p.

Referenced by remove_unnecessary_regions().

static void remove_unnecessary_allocnos ( )

static

Remove allocnos from loops removed from the allocation
   consideration.

References ira_loop_tree_node::all_allocnos, bitmap_set_bit(), finish_allocno(), ira_allocate(), ira_allocnos_num, ira_free(), ira_rebuild_regno_allocno_list(), ira_rebuild_start_finish_chains(), max_reg_num(), move_allocno_live_ranges(), ira_loop_tree_node::parent, propagate_some_info_from_allocno(), ira_loop_tree_node::regno_allocno_map, and ira_loop_tree_node::to_remove_p.

Referenced by remove_unnecessary_regions().

static void remove_unnecessary_regions ( )

static

Remove loops from consideration.  We remove all loops except for
   root if ALL_P or loops for which a separate allocation will not
   improve the result.  We have to do this after allocno creation and
   their costs and allocno class evaluation because only after that
   the register pressure can be known and is calculated.

References cfun, finish_loop_tree_node(), mark_all_loops_for_removal(), mark_loops_for_removal(), number_of_loops(), remove_low_level_allocnos(), remove_uneccesary_loop_nodes_from_loop_tree(), and remove_unnecessary_allocnos().

Referenced by ira_build().

static int setup_loop_tree_level ( )

static

The following recursive function sets up levels of nodes of the
   tree given its root LOOP_NODE.  The enumeration starts with LEVEL.
   The function returns maximal value of level in the tree + 1.

References ira_loop_tree_node::bb, ira_loop_tree_node::level, ira_loop_tree_node::subloop_next, and ira_loop_tree_node::subloops.

Referenced by form_loop_tree().

static void setup_min_max_allocno_live_range_point ( )

static

Set up minimal and maximal live range points for allocnos.

References live_range::finish, ira_max_point, max_reg_num(), live_range::next, ira_loop_tree_node::regno_allocno_map, and live_range::start.

Referenced by ira_build().

static void setup_min_max_conflict_allocno_ids ( )

static

Set up minimal and maximal conflict ids of allocnos with which
   given allocno can conflict.

References ira_allocate(), ira_free(), ira_max_point, and ira_objects_num.

Referenced by ira_build().

static void sort_conflict_id_map ( )

static

Sort ira_object_id_map and set up conflict id of allocnos.

References ira_objects_num, loop::num, and object_range_compare_func().

Referenced by ira_build().

static void update_bad_spill_attribute ( )

static

At this point true value of allocno attribute bad_spill_p means
   that there is an insn where allocno occurs and where the allocno
   can not be used as memory.  The function updates the attribute, now
   it can be true only for allocnos which can not be used as memory in
   an insn and in whose live ranges there is other allocno deaths.
   Spilling allocnos with true value will not improve the code because
   it will not make other allocnos colorable and additional reloads
   for the corresponding pseudo will be generated in reload pass for
   each insn it occurs.

   This is a trick mentioned in one classic article of Chaitin etc
   which is frequently omitted in other implementations of RA based on
   graph coloring.

References bitmap_bit_p(), bitmap_clear(), bitmap_set_bit(), live_range::finish, live_range::next, reg_obstack, and live_range::start.

Referenced by ira_build().

static void update_conflict_hard_reg_costs ( )

static

Identify allocnos which prefer a register class with a single hard register.
   Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
   less likely to use the preferred singleton register.

References ira_allocate_and_set_costs(), pref, and reg_preferred_class().

Referenced by ira_build().

Variable Documentation

alloc_pool allocno_pool

static

Pools for allocnos, allocno live ranges and objects.

vec<ira_allocno_t> allocno_vec

static

Vec containing references to all created allocnos.  It is a
   container of array allocnos.

vec<ira_loop_tree_node_t> children_vec

static

Vec containing references to all children of loop tree nodes.

int* conflict_check

static

The array used to find duplications in conflict vectors of
   allocnos.

Referenced by compress_conflict_vec(), and compress_conflict_vecs().

alloc_pool copy_pool

static

Pools for copies.

vec<ira_copy_t> copy_vec

static

Vec containing references to all created copies.  It is a
   container of array ira_copies.

alloc_pool cost_vector_pool[N_REG_CLASSES]

static

Pools for cost vectors.  It is defined only for allocno classes.

basic_block curr_bb

static

The basic block currently being processed.

int curr_conflict_check_tick

static

The value used to mark allocation presence in conflict vector of
   the current allocno.

Referenced by compress_conflict_vec(), and compress_conflict_vecs().

ira_allocno_t* ira_allocnos

Array of references to all allocnos.  The order number of the
   allocno corresponds to the index in the array.  Removed allocnos
   have NULL element value.

Referenced by change_loop(), coalesce_allocnos(), color_allocnos(), color_pass(), form_allocno_hard_regs_nodes_forest(), improve_allocation(), print_loop_title(), and setup_profitable_hard_regs().

int ira_allocnos_num

Sizes of the previous array.

Referenced by coalesce_spill_slots(), color(), fast_allocation(), find_costs_and_classes(), initiate_allocnos(), initiate_cost_update(), ira_build(), ira_costs(), ira_create_allocno(), ira_create_allocno_live_ranges(), ira_emit(), ira_initiate_assign(), ira_initiate_emit_data(), ira_sort_regnos_for_alter_reg(), and remove_unnecessary_allocnos().

ira_loop_tree_node_t ira_bb_nodes

All nodes representing basic blocks are referred through the
   following array.  We can not use basic block member `aux' for this
   because it is used for insertion of insns on edges.

ira_copy_t* ira_copies

Array of references to all copies.  The order number of the copy
   corresponds to the index in the array.  Removed copies have NULL
   element value.

int ira_copies_num

Size of the previous array.

Referenced by coalesce_allocnos(), initiate_copies(), ira_build(), and ira_create_copy().

ira_loop_tree_node_t ira_curr_loop_tree_node

The current loop tree node and its regno allocno map.

Referenced by change_loop(), and process_regs_for_copy().

ira_allocno_t* ira_curr_regno_allocno_map

Referenced by change_regs(), check_and_make_def_conflict(), make_pseudo_conflict(), mark_pseudo_regno_dead(), mark_pseudo_regno_live(), mark_pseudo_regno_subword_dead(), mark_pseudo_regno_subword_live(), process_bb_node_for_hard_reg_moves(), process_regs_for_copy(), process_single_reg_class_operands(), pseudo_regno_single_word_and_live_p(), record_address_regs(), and record_reg_classes().

ira_loop_tree_node_t ira_loop_nodes

All nodes representing loops are referred through the following
   array.

Referenced by setup_entered_from_non_parent_p().

unsigned int ira_loop_nodes_count

And size of the ira_loop_nodes array.

Referenced by create_loop_tree_nodes(), and finish_loop_tree_nodes().

int ira_loop_tree_height

Height of the loop tree.

Referenced by form_loop_tree().

ira_loop_tree_node_t ira_loop_tree_root

The root of the loop tree corresponding to the all function.

Referenced by change_loop(), conflict_by_live_ranges_p(), do_coloring(), find_costs_and_classes(), ira_build_conflicts(), ira_create_allocno_live_ranges(), ira_emit(), ira_flattening(), process_bb_node_lives(), propagate_copies(), remove_low_level_allocnos(), setup_allocno_class_and_costs(), and too_high_register_pressure_p().

ira_object_t* ira_object_id_map

Map a conflict id to its conflict record.

Referenced by build_conflict_bit_table(), build_object_conflicts(), dec_register_pressure(), make_hard_regno_born(), process_bb_node_lives(), and process_single_reg_class_operands().

vec<ira_object_t> ira_object_id_map_vec

static

Vec containing references to all created ira_objects.  It is a
   container of ira_object_id_map.

int ira_objects_num

Count of conflict record structures we've created, used when creating
   a new conflict id.

Referenced by build_conflict_bit_table(), build_conflicts(), compress_conflict_vecs(), initiate_allocnos(), ira_create_allocno_live_ranges(), ira_create_object(), ira_flattening(), modify_move_list(), setup_min_max_conflict_allocno_ids(), and sort_conflict_id_map().

ira_allocno_t* ira_regno_allocno_map

Map regno -> allocnos with given regno (see comments for
   allocno member `next_regno_allocno').

Referenced by build_conflicts(), calculate_spill_cost(), coalesced_pseudo_reg_slot_compare(), collect_spilled_coalesced_allocnos(), find_costs_and_classes(), ira_bad_reload_regno_1(), ira_mark_allocation_change(), ira_mark_memory_move_deletion(), ira_mark_new_stack_slot(), ira_print_disposition(), ira_reassign_pseudos(), ira_reuse_stack_slot(), ira_sort_regnos_for_alter_reg(), set_allocno_reg(), and setup_coalesced_allocno_costs_and_nums().

int last_basic_block_before_change

static

LAST_BASIC_BLOCK before generating additional insns because of live
   range splitting.  Emitting insns on a critical edge creates a new
   basic block.

Referenced by create_loop_tree_nodes(), and finish_loop_tree_nodes().

alloc_pool live_range_pool

static

alloc_pool object_pool

static

ira_allocno_t* regno_allocnos

static

This array is used to sort allocnos to restore allocno order in
   the regno allocno list.

ira_allocno_t* regno_top_level_allocno_map

static

The page contains code transforming more one region internal
   representation (IR) to one region IR which is necessary for reload.
   This transformation is called IR flattening.  We might just rebuild
   the IR for one region but we don't do it because it takes a lot of
   time.

Map: regno -> allocnos which will finally represent the regno for
   IR with one region.

vec<ira_loop_tree_node_t> removed_loop_vec

static

Definition of vector of loop tree nodes.

Vec containing references to all removed loop tree nodes.

Macros

Functions

Variables

Macro Definition Documentation

Function Documentation

Variable Documentation