From a868002322aa30a66a364b1b4c069095374bc5a8 Mon Sep 17 00:00:00 2001 From: vmakarov Date: Thu, 10 Jan 2008 22:57:59 +0000 Subject: [PATCH] 2008-01-10 Vladimir Makarov * reload1.c (compute_use_by_pseudos): Permits spilled registers in FROM. (temp_pseudo_reg_arr): New variable. (reload): Use instead temp_pseudo_reg_arr of pseudo_regs. Move freeing to the function end. Don't clear spilled_pseudos for IRA. Restore original insn chain for IRA. (calculate_needs_all_insns): Call IRA's mark_memory_move_deletion. (count_pseudo, count_spilled_pseudo): Check spilled pseudos. (alter_reg): Set up spilled_pseudos. (finish_spills): Set up pseudo_previous_regs only for spilled pseudos. Call reassign_pseudos once for all spilled pseudos, pass more arguments. Don't clear live_throughout and dead_or_set for spilled pseudos. * global.c (reg_becomes_live, build_insn_chain): Don't ignore spilled pseudos for IRA. * caller-save.c (calculate_local_save_info, save_call_clobbered_regs): Ignore spilled pseudos for IRA. * toplev.c (backend_init_target): Call init_ira. (backend_init): Move call of init_ira_once before backend_init_target. * ira.h (init_ira, sort_insn_chain, mark_memory_move_deletion): New function prototypes. (retry_ira_color): Rename to reassign_pseudos. Change signature. * ira-int.h (allocno): New member dont_reassign_p. (ALLOCNO_DONT_REASSIGN_P): New macro. (memory_move_cost): Change element type. (register_move_cost): Change type. (register_may_move_in_cost, register_may_move_out_cost, reg_class_intersect): New arrays. (important_class_nums): Fix element type. (hard_reg_not_in_set_p): Make it static inline. (init_register_move_cost, init_ira_costs): New function prototypes. (allocno_conflict_index): Remove. (allocate_and_set_costs, allocate_and_copy_costs, allocate_and_set_or_copy_costs): New static inline functions. * ira-build.c (compress_allocno_conflict_vec, compress_conflict_vecs): New functions. (allocno_conflict_index): Remove. (allocno_conflict_check, curr_allocno_conflict_check_tick): New variables. (propagate_info_to_cap): Use allocate_and_copy_costs. (check_and_add_conflicts): Don't call allocno_conflict_index. (ira_flattening): Add some assertions. Check that cost vectors have been allocated. Don't call allocno_conflict_index. Call compress_conflict_vecs. * ira.c (memory_move_cost, register_move_cost): Change types. (register_may_move_in_cost, register_may_move_out_cost, strict_class_subset_p): New variables. (setup_class_subset_and_move_costs): Rename to setup_class_subset_and_memory_move_costs. Remove register_move_cost setup. Don't consider no_unit_alloc_regs. Add strict_class_subset_p setup. (setup_reg_class_intersect): Rename to setup_reg_class_intersect_union. Don't consider no_unit_alloc_regs. Add reg_class_union setup. (hard_reg_not_in_set_p): Move to ira-int.h. (setup_reg_subclasses): Use no_unit_alloc_regs instead of fixed_reg_set. Don't consider no_unit_alloc_regs. (important_class_nums): Fix element type. (setup_cover_classes): Use no_unit_alloc_regs instead of fixed_reg_set. Don't consider no_unit_alloc_regs. (setup_class_translate): Ditto. (reg_class_union): New variable. (init_register_move_cost, free_register_move_costs): New functions. (init_ira_once): Initialize register_move_cost, register_may_move_in_cost, register_may_move_out_cost. Move some code to init_ira. (init_ira): New function. Move some code from init_ira_once. Call free_register_move_costs and init_ira_costs. (calculate_allocation_cost): Check allocation of allocno hard reg cost vector. (basic_block_order_nums): New variable. (chain_freq_compare, chain_bb_compare, sort_insn_chain): New functions. (ira): Call sort_insn_chain. * ira-color.c (allocno_coalesced_p): New variable. (update_copy_costs): Use allocate_and_set_or_copy_costs. (assign_hard_reg): Clear and use processed_coalesced_allocno_bitmap only if allocno_coalesced_p. Use allocate_and_copy_costs. Use allocno cover class cost if the hard register cost vector is not allocated. (get_coalesced_allocnos_best_class_and_freq): Use reg_class_intersect instead of reg_class_subintersect. (add_allocno_to_ordered_bucket): Use strict_class_subset_p. (push_allocno_to_stack): Clear and use processed_coalesced_allocno_bitmap only if allocno_coalesced_p. (setup_allocno_left_conflicts_num): Don't setup ALLOCNO_UPDATED_HARD_REG_COSTS and ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS. Clear and use processed_coalesced_allocno_bitmap only if allocno_coalesced_p. (put_allocno_into_bucket): Don't setup ALLOCNO_UPDATED_HARD_REG_COSTS and ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS. (coalesced_allocno_conflict_p): Clear and use processed_coalesced_allocno_bitmap only if allocno_coalesced_p. (coalesce_allocnos): Setup allocno_coalesced_p. (color_allocnos): Add processing reg class NO_REGS. (color_pass): Propagate assignment of spilled allocno not mentioned in the subregion for the mixed algorithm. Use allocate_and_set_costs. (move_spill_restore, mark_allocation_change): Check unallocated hard reg cost vectors. (setup_curr_costs): Don't setup ALLOCNO_UPDATED_HARD_REG_COSTS and ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS. Use allocate_and_set_or_copy_costs. (mark_memory_move_deletion, allocno_reload_assign, pseudo_reg_compare, reassign_pseudos): New functions. (retry_ira_color): Remove. * ira-conflicts.c (add_insn_allocno_copies): Use allocate_and_set_costs. (allocno_conflict_p): Simplify the code. * ira-costs.c: Rename reg_class_subunion to reg_class_union everywhere. (cost_classes, cost_classes_num, cost_class_nums, max_struct_costs_size): New variables. (copy_cost): Use init_register_move_cost instead of init_move_cost. (record_reg_classes): Ditto. Use cost_classes and cost_classes_num instead of important_classes and important_classes_num. Use register_may_move_{in,out}_cost instead of may_move_{in,out}_cost. Check reg class intersection for alt_cost. (record_address_regs): Use init_register_move_cost instead of init_move_cost. Use cost_classes and cost_classes_num instead of important_classes and important_classes_num. Use register_may_move_in_cost instead of may_move_in_cost. (scan_one_insn): Use cost_classes_num instead of important_classes_num. (print_costs): Use cost_classes and cost_classes_num instead of important_classes and important_classes_num. (find_allocno_class_costs): Initialize cost_classes and cost_class_nums. Use cost_classes and cost_classes_num instead of important_classes and important_classes_num. (process_bb_node_for_hard_reg_moves): Use allocate_and_set_costs. (setup_allocno_cover_class_and_costs): Use cost_classes and cost_classes_num instead of important_classes and important_classes_num. (init_ira_costs_once): Move some code to init_ira_costs. Initiate cost_classes. (free_ira_costs: New function. Move some code from finish_ira_costs_once. (init_ira_costs): New function. Move some code from init_ira_costs_once. Use max_struct_costs_size instead of struct_costs_size. Call free_ira_costs. Allocate cost_classes. (finish_ira_costs_once): Move some code to finish_ira_costs. Call free_ira_costs. (ira_costs): Use max_struct_costs_size instead of struct_costs_size. Use allocate_and_set_costs. * ira-emit.c (modify_move_list): Remove allocation of hard reg cost vectors. * ira-lives.c (process_single_reg_class_operands): Add new parameter freq. Calculate costs basing on the frequency. (process_bb_node_lives): Pass the frequency to process_single_reg_class_operands. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/ira@131452 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 172 +++++++++++++++++++++++ gcc/caller-save.c | 4 + gcc/global.c | 7 +- gcc/ira-build.c | 294 ++++++++++++++++++++++---------------- gcc/ira-color.c | 395 +++++++++++++++++++++++++++++++++++++++------------ gcc/ira-conflicts.c | 29 +++- gcc/ira-costs.c | 345 ++++++++++++++++++++++++++++----------------- gcc/ira-emit.c | 16 +-- gcc/ira-int.h | 103 ++++++++++++-- gcc/ira-lives.c | 34 +++-- gcc/ira.c | 398 +++++++++++++++++++++++++++++++++++++++------------- gcc/ira.h | 6 +- gcc/reload1.c | 151 +++++++++++--------- gcc/toplev.c | 5 +- 14 files changed, 1400 insertions(+), 559 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 6cf4acde49b..27421b5672c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,175 @@ +2008-01-10 Vladimir Makarov + + * reload1.c (compute_use_by_pseudos): Permits spilled registers in + FROM. + (temp_pseudo_reg_arr): New variable. + (reload): Use instead temp_pseudo_reg_arr of pseudo_regs. Move + freeing to the function end. Don't clear spilled_pseudos for IRA. + Restore original insn chain for IRA. + (calculate_needs_all_insns): Call IRA's mark_memory_move_deletion. + (count_pseudo, count_spilled_pseudo): Check spilled pseudos. + (alter_reg): Set up spilled_pseudos. + (finish_spills): Set up pseudo_previous_regs only for spilled + pseudos. Call reassign_pseudos once for all spilled pseudos, + pass more arguments. Don't clear live_throughout and dead_or_set + for spilled pseudos. + + * global.c (reg_becomes_live, build_insn_chain): Don't ignore + spilled pseudos for IRA. + + * caller-save.c (calculate_local_save_info, + save_call_clobbered_regs): Ignore spilled pseudos for IRA. + + * toplev.c (backend_init_target): Call init_ira. + (backend_init): Move call of init_ira_once before + backend_init_target. + + * ira.h (init_ira, sort_insn_chain, mark_memory_move_deletion): + New function prototypes. + (retry_ira_color): Rename to reassign_pseudos. Change + signature. + + * ira-int.h (allocno): New member dont_reassign_p. + (ALLOCNO_DONT_REASSIGN_P): New macro. + (memory_move_cost): Change element type. + (register_move_cost): Change type. + (register_may_move_in_cost, register_may_move_out_cost, + reg_class_intersect): New arrays. + (important_class_nums): Fix element type. + (hard_reg_not_in_set_p): Make it static inline. + (init_register_move_cost, init_ira_costs): New function + prototypes. + (allocno_conflict_index): Remove. + (allocate_and_set_costs, allocate_and_copy_costs, + allocate_and_set_or_copy_costs): New static inline functions. + + * ira-build.c (compress_allocno_conflict_vec, + compress_conflict_vecs): New functions. + (allocno_conflict_index): Remove. + (allocno_conflict_check, curr_allocno_conflict_check_tick): New + variables. + (propagate_info_to_cap): Use allocate_and_copy_costs. + (check_and_add_conflicts): Don't call allocno_conflict_index. + (ira_flattening): Add some assertions. Check that cost vectors + have been allocated. Don't call allocno_conflict_index. Call + compress_conflict_vecs. + + * ira.c (memory_move_cost, register_move_cost): Change types. + (register_may_move_in_cost, register_may_move_out_cost, + strict_class_subset_p): New variables. + (setup_class_subset_and_move_costs): Rename to + setup_class_subset_and_memory_move_costs. Remove + register_move_cost setup. Don't consider no_unit_alloc_regs. Add + strict_class_subset_p setup. + (setup_reg_class_intersect): Rename to + setup_reg_class_intersect_union. Don't consider + no_unit_alloc_regs. Add reg_class_union setup. + (hard_reg_not_in_set_p): Move to ira-int.h. + (setup_reg_subclasses): Use no_unit_alloc_regs instead of + fixed_reg_set. Don't consider no_unit_alloc_regs. + (important_class_nums): Fix element type. + (setup_cover_classes): Use no_unit_alloc_regs instead of + fixed_reg_set. Don't consider no_unit_alloc_regs. + (setup_class_translate): Ditto. + (reg_class_union): New variable. + (init_register_move_cost, free_register_move_costs): New + functions. + (init_ira_once): Initialize register_move_cost, + register_may_move_in_cost, register_may_move_out_cost. Move some + code to init_ira. + (init_ira): New function. Move some code from init_ira_once. + Call free_register_move_costs and init_ira_costs. + (calculate_allocation_cost): Check allocation of allocno hard reg + cost vector. + (basic_block_order_nums): New variable. + (chain_freq_compare, chain_bb_compare, sort_insn_chain): New + functions. + (ira): Call sort_insn_chain. + + * ira-color.c (allocno_coalesced_p): New variable. + (update_copy_costs): Use allocate_and_set_or_copy_costs. + (assign_hard_reg): Clear and use + processed_coalesced_allocno_bitmap only if allocno_coalesced_p. + Use allocate_and_copy_costs. Use allocno cover class cost if the + hard register cost vector is not allocated. + (get_coalesced_allocnos_best_class_and_freq): Use + reg_class_intersect instead of reg_class_subintersect. + (add_allocno_to_ordered_bucket): Use strict_class_subset_p. + (push_allocno_to_stack): Clear and use + processed_coalesced_allocno_bitmap only if allocno_coalesced_p. + (setup_allocno_left_conflicts_num): Don't setup + ALLOCNO_UPDATED_HARD_REG_COSTS and + ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS. Clear and use + processed_coalesced_allocno_bitmap only if allocno_coalesced_p. + (put_allocno_into_bucket): Don't setup + ALLOCNO_UPDATED_HARD_REG_COSTS and + ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS. + (coalesced_allocno_conflict_p): Clear and use + processed_coalesced_allocno_bitmap only if allocno_coalesced_p. + (coalesce_allocnos): Setup allocno_coalesced_p. + (color_allocnos): Add processing reg class NO_REGS. + (color_pass): Propagate assignment of spilled allocno not + mentioned in the subregion for the mixed algorithm. Use + allocate_and_set_costs. + (move_spill_restore, mark_allocation_change): Check unallocated + hard reg cost vectors. + (setup_curr_costs): Don't setup ALLOCNO_UPDATED_HARD_REG_COSTS and + ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS. Use + allocate_and_set_or_copy_costs. + (mark_memory_move_deletion, allocno_reload_assign, + pseudo_reg_compare, reassign_pseudos): New functions. + (retry_ira_color): Remove. + + * ira-conflicts.c (add_insn_allocno_copies): Use + allocate_and_set_costs. + (allocno_conflict_p): Simplify the code. + + * ira-costs.c: Rename reg_class_subunion to reg_class_union + everywhere. + (cost_classes, cost_classes_num, cost_class_nums, + max_struct_costs_size): New variables. + (copy_cost): Use init_register_move_cost instead of + init_move_cost. + (record_reg_classes): Ditto. Use cost_classes and + cost_classes_num instead of important_classes and + important_classes_num. Use register_may_move_{in,out}_cost + instead of may_move_{in,out}_cost. Check reg class intersection + for alt_cost. + (record_address_regs): Use init_register_move_cost instead of + init_move_cost. Use cost_classes and cost_classes_num instead of + important_classes and important_classes_num. Use + register_may_move_in_cost instead of may_move_in_cost. + (scan_one_insn): Use cost_classes_num instead of + important_classes_num. + (print_costs): Use cost_classes and cost_classes_num instead of + important_classes and important_classes_num. + (find_allocno_class_costs): Initialize cost_classes and + cost_class_nums. Use cost_classes and cost_classes_num instead of + important_classes and important_classes_num. + (process_bb_node_for_hard_reg_moves): Use allocate_and_set_costs. + (setup_allocno_cover_class_and_costs): Use cost_classes and + cost_classes_num instead of important_classes and + important_classes_num. + (init_ira_costs_once): Move some code to init_ira_costs. Initiate + cost_classes. + (free_ira_costs: New function. Move some code from + finish_ira_costs_once. + (init_ira_costs): New function. Move some code from + init_ira_costs_once. Use max_struct_costs_size instead of + struct_costs_size. Call free_ira_costs. Allocate cost_classes. + (finish_ira_costs_once): Move some code to finish_ira_costs. Call + free_ira_costs. + (ira_costs): Use max_struct_costs_size instead of + struct_costs_size. Use allocate_and_set_costs. + + * ira-emit.c (modify_move_list): Remove allocation of hard reg + cost vectors. + + * ira-lives.c (process_single_reg_class_operands): Add new + parameter freq. Calculate costs basing on the frequency. + (process_bb_node_lives): Pass the frequency to + process_single_reg_class_operands. + 2007-12-17 Vladimir Makarov * doc/invoke.texi (fira-algoirthm): Remove prioirity coloring. diff --git a/gcc/caller-save.c b/gcc/caller-save.c index e2ec2fd8741..dbcd0420ff5 100644 --- a/gcc/caller-save.c +++ b/gcc/caller-save.c @@ -794,6 +794,8 @@ calculate_local_save_info (void) int nregs; enum machine_mode mode; + if (flag_ira && r < 0) + continue; gcc_assert (r >= 0); nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (regno)]; mode = HARD_REGNO_CALLER_SAVE_MODE @@ -1250,6 +1252,8 @@ save_call_clobbered_regs (void) int nregs; enum machine_mode mode; + if (flag_ira && r < 0) + continue; gcc_assert (r >= 0); nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (regno)]; mode = HARD_REGNO_CALLER_SAVE_MODE diff --git a/gcc/global.c b/gcc/global.c index fe888083c82..e1521c327fe 100644 --- a/gcc/global.c +++ b/gcc/global.c @@ -1836,7 +1836,7 @@ reg_becomes_live (rtx reg, const_rtx setter ATTRIBUTE_UNUSED, void *regs_set) regno++; } } - else if (reg_renumber[regno] >= 0) + else if (reg_renumber[regno] >= 0 || flag_ira) { if (GET_CODE (setter) == CLOBBER) CLEAR_REGNO_REG_SET (live_relevant_regs, regno); @@ -1864,7 +1864,7 @@ reg_dies (int regno, enum machine_mode mode, struct insn_chain *chain) else { CLEAR_REGNO_REG_SET (live_relevant_regs, regno); - if (reg_renumber[regno] >= 0) + if (reg_renumber[regno] >= 0 || flag_ira) SET_REGNO_REG_SET (&chain->dead_or_set, regno); } } @@ -1879,7 +1879,6 @@ build_insn_chain (rtx first) basic_block b = ENTRY_BLOCK_PTR->next_bb; live_relevant_regs = ALLOC_REG_SET (®_obstack); - for (; first; first = NEXT_INSN (first)) { struct insn_chain *c; @@ -1895,7 +1894,7 @@ build_insn_chain (rtx first) { if (i < FIRST_PSEUDO_REGISTER ? ! TEST_HARD_REG_BIT (eliminable_regset, i) - : reg_renumber[i] >= 0) + : reg_renumber[i] >= 0 || flag_ira) SET_REGNO_REG_SET (live_relevant_regs, i); } } diff --git a/gcc/ira-build.c b/gcc/ira-build.c index e09d8a80c5f..f3acdb3987b 100644 --- a/gcc/ira-build.c +++ b/gcc/ira-build.c @@ -56,6 +56,8 @@ static void finish_calls (void); static void initiate_allocnos (void); static void check_allocno_conflict_vec (allocno_t, int); static void add_to_allocno_conflict_vec (allocno_t, allocno_t); +static void compress_allocno_conflict_vec (allocno_t); +static void compress_conflict_vecs (void); static allocno_t create_cap_allocno (allocno_t); static void propagate_info_to_cap (allocno_t); static allocno_live_range_t copy_allocno_live_range (allocno_live_range_t); @@ -510,6 +512,7 @@ create_allocno (int regno, int cap_p, loop_tree_node_t loop_tree_node) #endif ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL; ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = FALSE; + ALLOCNO_DONT_REASSIGN_P (a) = FALSE; ALLOCNO_IN_GRAPH_P (a) = FALSE; ALLOCNO_ASSIGNED_P (a) = FALSE; ALLOCNO_MAY_BE_SPILLED_P (a) = FALSE; @@ -535,21 +538,6 @@ create_allocno (int regno, int cap_p, loop_tree_node_t loop_tree_node) return a; } -/* The function returns index of A2 in conflict vector of A1, or -1 if - it is absent. */ -int -allocno_conflict_index (allocno_t a1, allocno_t a2) -{ - int i; - allocno_t conflict_allocno, *allocno_vec; - - allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a1); - for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++) - if (conflict_allocno == a2) - return i; - return -1; -} - /* The function allocates conflict vector of A for NUM allocnos. */ void allocate_allocno_conflicts (allocno_t a, int num) @@ -608,6 +596,55 @@ add_allocno_conflict (allocno_t a1, allocno_t a2) add_to_allocno_conflict_vec (a2, a1); } +/* The array used to find duplications in conflict vecs of + allocnos. */ +static int *allocno_conflict_check; +/* The value used to mark allocation presence in conflict vec of the + current allocno. */ +static int curr_allocno_conflict_check_tick; + +/* The function removes duplications in conflict vector of A. */ +static void +compress_allocno_conflict_vec (allocno_t a) +{ + allocno_t *vec, conflict_a; + int i, j; + + vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a); + curr_allocno_conflict_check_tick++; + for (i = j = 0; (conflict_a = vec [i]) != NULL; i++) + { + if (ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) == i) + ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = j; + if (allocno_conflict_check [ALLOCNO_NUM (conflict_a)] + != curr_allocno_conflict_check_tick) + { + allocno_conflict_check [ALLOCNO_NUM (conflict_a)] + = curr_allocno_conflict_check_tick; + vec [j++] = conflict_a; + } + } + if (ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) == i) + ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = j; + ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) = j; + vec [j] = NULL; +} + +/* The function removes duplications in conflict vectors of all + allocnos. */ +static void +compress_conflict_vecs (void) +{ + int i; + + allocno_conflict_check = ira_allocate (sizeof (int) * allocnos_num); + memset (allocno_conflict_check, 0, sizeof (int) * allocnos_num); + curr_allocno_conflict_check_tick = 0; + for (i = 0; i < allocnos_num; i++) + compress_allocno_conflict_vec (allocnos [i]); + ira_free (allocno_conflict_check); +} + /* This recursive function outputs allocno A and if it is cap the function outputs members. */ void @@ -649,6 +686,7 @@ create_cap_allocno (allocno_t a) bitmap_set_bit (father->mentioned_allocnos, ALLOCNO_NUM (cap)); ALLOCNO_CAP (a) = cap; ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a); + /* ??? memory_cost */ ALLOCNO_UPDATED_MEMORY_COST (cap) = ALLOCNO_UPDATED_MEMORY_COST (a); if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) { @@ -665,7 +703,6 @@ static void propagate_info_to_cap (allocno_t cap) { int i, regno, hard_regs_num, conflicts_num; - int *reg_costs, *conflict_reg_costs; allocno_t a, conflict_allocno, conflict_father_allocno; allocno_t another_a, father_a; allocno_t *allocno_vec; @@ -679,17 +716,12 @@ propagate_info_to_cap (allocno_t cap) a = ALLOCNO_CAP_MEMBER (cap); father = ALLOCNO_LOOP_TREE_NODE (cap); hard_regs_num = class_hard_regs_num [ALLOCNO_COVER_CLASS (cap)]; - ALLOCNO_HARD_REG_COSTS (cap) = reg_costs - = ira_allocate (hard_regs_num * sizeof (int)); - memcpy (reg_costs, ALLOCNO_HARD_REG_COSTS (a), hard_regs_num * sizeof (int)); - ALLOCNO_CONFLICT_HARD_REG_COSTS (cap) = conflict_reg_costs - = ira_allocate (hard_regs_num * sizeof (int)); - memcpy (conflict_reg_costs, ALLOCNO_CONFLICT_HARD_REG_COSTS (a), - hard_regs_num * sizeof (int)); - ALLOCNO_UPDATED_HARD_REG_COSTS (cap) - = ira_allocate (hard_regs_num * sizeof (int)); - ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (cap) - = ira_allocate (hard_regs_num * sizeof (int)); + allocate_and_copy_costs + (&ALLOCNO_HARD_REG_COSTS (cap), hard_regs_num, + ALLOCNO_HARD_REG_COSTS (a)); + allocate_and_copy_costs + (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), hard_regs_num, + ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a); ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a); ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a); @@ -1375,7 +1407,9 @@ merge_ranges (allocno_live_range_t r1, allocno_live_range_t r2) ira_assert (r2->next == NULL); } else - ira_assert (last->next == NULL); + { + ira_assert (last->next == NULL); + } return first; } @@ -1413,10 +1447,8 @@ check_and_add_conflicts (allocno_t a, allocno_t *conflict_vec) { conflict_a = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (conflict_a))]; - if (allocno_conflict_p (conflict_a, a) - && allocno_conflict_index (conflict_a, a) < 0) + if (allocno_conflict_p (conflict_a, a)) { - ira_assert (allocno_conflict_index (a, conflict_a) < 0); add_to_allocno_conflict_vec (conflict_a, a); add_to_allocno_conflict_vec (a, conflict_a); if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) @@ -1467,7 +1499,7 @@ add_conflict_with_underlying_allocnos (allocno_t a, void ira_flattening (int max_regno_before_emit, int max_point_before_emit) { - int i, j, k, free, propagate_p, stop_p, keep_p, hard_regs_num; + int i, j, k, free, propagate_p, stop_p, keep_p, hard_regs_num, new_allocnos_p; unsigned int n; enum reg_class cover_class; rtx call, *allocno_calls; @@ -1483,6 +1515,7 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) = ira_allocate (max_reg_num () * sizeof (allocno_t)); memset (regno_top_level_allocno_map, 0, max_reg_num () * sizeof (allocno_t)); expand_calls (); + new_allocnos_p = FALSE; /* Updating accumulated attributes. */ for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--) { @@ -1491,8 +1524,9 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) a != NULL; a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) { - if (ALLOCNO_CAP_MEMBER (a) == NULL - && (unsigned int) ALLOCNO_REGNO (a) != REGNO (ALLOCNO_REG (a)) + if (ALLOCNO_CAP_MEMBER (a) != NULL) + continue; + if ((unsigned int) ALLOCNO_REGNO (a) != REGNO (ALLOCNO_REG (a)) && ALLOCNO_CALLS_CROSSED_NUM (a) != 0) { allocno_calls = (VEC_address (rtx, @@ -1508,13 +1542,14 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) } } if ((father = ALLOCNO_LOOP_TREE_NODE (a)->father) == NULL - || (father_a = father->regno_allocno_map [ALLOCNO_REGNO (a)]) - == NULL) + || ((father_a = father->regno_allocno_map [ALLOCNO_REGNO (a)]) + == NULL)) { ALLOCNO_COPIES (a) = NULL; regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] = a; continue; } + ira_assert (ALLOCNO_CAP_MEMBER (father_a) == NULL); if (propagate_p) { COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (father_a), @@ -1548,6 +1583,7 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) || ALLOCNO_MEM_OPTIMIZED_DEST_P (a)); continue; } + new_allocnos_p = TRUE; propagate_p = TRUE; first = ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL ? NULL : a; for (;;) @@ -1560,13 +1596,16 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) ALLOCNO_CALL_FREQ (father_a) -= ALLOCNO_CALL_FREQ (a); cover_class = ALLOCNO_COVER_CLASS (father_a); hard_regs_num = class_hard_regs_num [cover_class]; - for (j = 0; j < hard_regs_num; j++) - { + if (ALLOCNO_HARD_REG_COSTS (a) != NULL + && ALLOCNO_HARD_REG_COSTS (father_a) != NULL) + for (j = 0; j < hard_regs_num; j++) ALLOCNO_HARD_REG_COSTS (father_a) [j] -= ALLOCNO_HARD_REG_COSTS (a) [j]; + if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL + && ALLOCNO_CONFLICT_HARD_REG_COSTS (father_a) != NULL) + for (j = 0; j < hard_regs_num; j++) ALLOCNO_CONFLICT_HARD_REG_COSTS (father_a) [j] -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [j]; - } ALLOCNO_COVER_CLASS_COST (father_a) -= ALLOCNO_COVER_CLASS_COST (a); ALLOCNO_MEMORY_COST (father_a) -= ALLOCNO_MEMORY_COST (a); @@ -1617,17 +1656,21 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] = a; } } - /* Fix final allocnos attributes concerning calls. */ - compress_calls (); - for (i = 0; i < allocnos_num; i++) + ira_assert (new_allocnos_p || max_point_before_emit == max_point); + if (new_allocnos_p) { - a = allocnos [i]; - if (a != regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] - || ALLOCNO_CAP_MEMBER (a) != NULL) - continue; - ALLOCNO_CALLS_CROSSED_START (a) = 0; - ALLOCNO_CALLS_CROSSED_NUM (a) - = VEC_length (rtx, regno_calls [REGNO (ALLOCNO_REG (a))]); + /* Fix final allocnos attributes concerning calls. */ + compress_calls (); + for (i = 0; i < allocnos_num; i++) + { + a = allocnos [i]; + if (a != regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] + || ALLOCNO_CAP_MEMBER (a) != NULL) + continue; + ALLOCNO_CALLS_CROSSED_START (a) = 0; + ALLOCNO_CALLS_CROSSED_NUM (a) + = VEC_length (rtx, regno_calls [REGNO (ALLOCNO_REG (a))]); + } } /* Mark copies for removing and change allocnos in copies. */ for (i = 0; i < copies_num; i++) @@ -1678,35 +1721,38 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) REGNO (ALLOCNO_REG (cp->second))); } } - /* Add conflicting allocnos from lower levels. If we have a situation - A1----conflict---B1 - A2----conflict---B2 - - and A1 and A2 will be presented by themselves in final IR and B1 - and B2 will be presented by B1, then we need to check conflict A2 - and B1. - - There is another situation when we should check and add conflicts - too. It should be done when we removed restoring allocno value - at the loop exits because the allocno value is stored in memory - and the value is not changed in the loop. In this case the - allocno lives in the loop and can conflict with allocnos inside - the loop. */ - for (i = 0; i < allocnos_num; i++) + if (new_allocnos_p) { - a = allocnos [i]; - if (a != regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] - || ALLOCNO_CAP_MEMBER (a) != NULL) - continue; - add_conflict_with_underlying_allocnos (a, ALLOCNO_LOOP_TREE_NODE (a), - FALSE); - if ((first = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL) + /* Add conflicting allocnos from lower levels. If we have a situation + A1----conflict---B1 + A2----conflict---B2 + + and A1 and A2 will be presented by themselves in final IR and + B1 and B2 will be presented by B1, then we need to check + conflict A2 and B1. + + There is another situation when we should check and add + conflicts too. It should be done when we removed restoring + allocno value at the loop exits because the allocno value is + stored in memory and the value is not changed in the loop. + In this case the allocno lives in the loop and can conflict + with allocnos inside the loop. */ + for (i = 0; i < allocnos_num; i++) { - first = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (first))]; - check_and_add_conflicts - (first, ALLOCNO_CONFLICT_ALLOCNO_VEC (a)); - add_conflict_with_underlying_allocnos - (first, ALLOCNO_LOOP_TREE_NODE (a), TRUE); + a = allocnos [i]; + if (a != regno_top_level_allocno_map [REGNO (ALLOCNO_REG (a))] + || ALLOCNO_CAP_MEMBER (a) != NULL) + continue; + add_conflict_with_underlying_allocnos (a, ALLOCNO_LOOP_TREE_NODE (a), + FALSE); + if ((first = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL) + { + first = regno_top_level_allocno_map [REGNO (ALLOCNO_REG (first))]; + check_and_add_conflicts + (first, ALLOCNO_CONFLICT_ALLOCNO_VEC (a)); + add_conflict_with_underlying_allocnos + (first, ALLOCNO_LOOP_TREE_NODE (a), TRUE); + } } } /* Change allocnos regno, conflicting allocnos, and range allocnos. */ @@ -1740,27 +1786,30 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) continue; } ALLOCNO_CAP (a) = NULL; - /* Remove conflicts. */ - allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a); - for (k = j = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a); - (conflict_a = allocno_vec [j]) != NULL; - j++) + if (new_allocnos_p) { - if (allocno_conflict_p (a, conflict_a)) - allocno_vec [k++] = conflict_a; - else + /* Remove conflicts. */ + allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a); + for (k = j = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a); + (conflict_a = allocno_vec [j]) != NULL; + j++) { - if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) - fprintf (ira_dump_file, - " Remove conflict a%dr%d - a%dr%d\n", - ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)), - ALLOCNO_NUM (conflict_a), - REGNO (ALLOCNO_REG (conflict_a))); - + if (allocno_conflict_p (a, conflict_a)) + allocno_vec [k++] = conflict_a; + else + { + if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) + fprintf (ira_dump_file, + " Remove conflict a%dr%d - a%dr%d\n", + ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)), + ALLOCNO_NUM (conflict_a), + REGNO (ALLOCNO_REG (conflict_a))); + + } } + allocno_vec [k] = NULL; + ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) = k; } - allocno_vec [k] = NULL; - ALLOCNO_TOTAL_CONFLICT_ALLOCNOS_NUM (a) = k; if (i == free) { free++; @@ -1808,53 +1857,50 @@ ira_flattening (int max_regno_before_emit, int max_point_before_emit) rebuild_regno_allocno_maps (); rebuild_start_finish_chains (); ira_free (regno_top_level_allocno_map); - live_allocnos = ira_allocate_bitmap (); - for (i = max_point_before_emit; i < max_point; i++) + if (new_allocnos_p) { - for (r = start_point_ranges [i]; r != NULL; r = r->start_next) + live_allocnos = ira_allocate_bitmap (); + for (i = max_point_before_emit; i < max_point; i++) { - a = r->allocno; - j = ALLOCNO_NUM (a); - EXECUTE_IF_SET_IN_BITMAP (live_allocnos, 0, n, bi) + for (r = start_point_ranges [i]; r != NULL; r = r->start_next) { - if (n == (unsigned int) j) - continue; - conflict_a = allocnos [n]; - if (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (conflict_a)) + a = r->allocno; + j = ALLOCNO_NUM (a); + EXECUTE_IF_SET_IN_BITMAP (live_allocnos, 0, n, bi) { - if (allocno_conflict_index (a, conflict_a) < 0) + if (n == (unsigned int) j) + continue; + conflict_a = allocnos [n]; + if (ALLOCNO_COVER_CLASS (a) + == ALLOCNO_COVER_CLASS (conflict_a)) { if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) - fprintf - (ira_dump_file, - " Add a%dr%d to conflict vec of a%dr%d\n", - ALLOCNO_NUM (conflict_a), - REGNO (ALLOCNO_REG (conflict_a)), - ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a))); + fprintf (ira_dump_file, + " Add a%dr%d to conflict vec of a%dr%d\n", + ALLOCNO_NUM (conflict_a), + REGNO (ALLOCNO_REG (conflict_a)), + ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a))); add_to_allocno_conflict_vec (a, conflict_a); - } - if (allocno_conflict_index (conflict_a, a) < 0) - { if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) - fprintf - (ira_dump_file, - " Add a%dr%d to conflict vec of a%dr%d\n", - ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)), - ALLOCNO_NUM (conflict_a), - REGNO (ALLOCNO_REG (conflict_a))); + fprintf (ira_dump_file, + " Add a%dr%d to conflict vec of a%dr%d\n", + ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)), + ALLOCNO_NUM (conflict_a), + REGNO (ALLOCNO_REG (conflict_a))); add_to_allocno_conflict_vec (conflict_a, a); } } + bitmap_set_bit (live_allocnos, j); } - bitmap_set_bit (live_allocnos, j); + + for (r = finish_point_ranges [i]; r != NULL; r = r->finish_next) + bitmap_clear_bit (live_allocnos, ALLOCNO_NUM (r->allocno)); } - - for (r = finish_point_ranges [i]; r != NULL; r = r->finish_next) - bitmap_clear_bit (live_allocnos, ALLOCNO_NUM (r->allocno)); + compress_conflict_vecs (); + ira_free_bitmap (live_allocnos); } - ira_free_bitmap (live_allocnos); } diff --git a/gcc/ira-color.c b/gcc/ira-color.c index f913265035a..068f8f317e8 100644 --- a/gcc/ira-color.c +++ b/gcc/ira-color.c @@ -83,6 +83,11 @@ static bitmap coloring_allocno_bitmap; allocnos. */ static bitmap consideration_allocno_bitmap; +/* TRUE if we coalesced some allocnos. In other words, if we have + loops formed by members first_coalesced_allocno and + next_coalesced_allocno containing more one allocno. */ +static int allocno_coalesced_p; + /* Bitmap used to prevent a repeated allocno processing because of coalescing. */ static bitmap processed_coalesced_allocno_bitmap; @@ -103,7 +108,7 @@ static int allocated_hardreg_p [FIRST_PSEUDO_REGISTER]; static void update_copy_costs (allocno_t allocno, int decr_p) { - int i, hard_regno, cost; + int i, hard_regno, cost, hard_regs_num; enum machine_mode mode; enum reg_class class; allocno_t another_allocno; @@ -134,6 +139,7 @@ update_copy_costs (allocno_t allocno, int decr_p) if (ALLOCNO_COVER_CLASS (allocno) != ALLOCNO_COVER_CLASS (another_allocno)) continue; + hard_regs_num = class_hard_regs_num [ALLOCNO_COVER_CLASS (allocno)]; cost = (cp->second == allocno ? register_move_cost [mode] [class] [ALLOCNO_COVER_CLASS (another_allocno)] @@ -141,7 +147,16 @@ update_copy_costs (allocno_t allocno, int decr_p) [ALLOCNO_COVER_CLASS (another_allocno)] [class]); if (decr_p) cost = -cost; - ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno) [i] += cp->freq * cost; + allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (another_allocno), + ALLOCNO_HARD_REG_COSTS (another_allocno)); + allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), + hard_regs_num, 0, + ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); + ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno) [i] + += cp->freq * cost; ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno) [i] += cp->freq * cost; } @@ -186,7 +201,7 @@ static varray_type allocno_stack_varray; /* Function choosing a hard register for ALLOCNO. If RETRY_P is nonzero, it means that the function called from - `retry_ira_color'. */ + `reassign_pseudos'. */ static int assign_hard_reg (allocno_t allocno, int retry_p) { @@ -216,8 +231,9 @@ assign_hard_reg (allocno_t allocno, int retry_p) IOR_COMPL_HARD_REG_SET (conflicting_regs, reg_class_contents [cover_class]); best_hard_regno = -1; memset (full_costs, 0, sizeof (int) * class_size); - mem_cost = 0; - bitmap_clear (processed_coalesced_allocno_bitmap); + mem_cost = 0; + if (allocno_coalesced_p) + bitmap_clear (processed_coalesced_allocno_bitmap); memset (costs, 0, sizeof (int) * class_size); memset (full_costs, 0, sizeof (int) * class_size); #ifdef STACK_REGS @@ -230,15 +246,23 @@ assign_hard_reg (allocno_t allocno, int retry_p) allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a); IOR_HARD_REG_SET (conflicting_regs, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a)); + allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), + class_size, ALLOCNO_HARD_REG_COSTS (a)); a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a); #ifdef STACK_REGS no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a); #endif - for (i = 0; i < class_size; i++) - { - costs [i] += a_costs [i]; - full_costs [i] += a_costs [i]; - } + for (cost = ALLOCNO_COVER_CLASS_COST (a), i = 0; i < class_size; i++) + if (a_costs != NULL) + { + costs [i] += a_costs [i]; + full_costs [i] += a_costs [i]; + } + else + { + costs [i] += cost; + full_costs [i] += cost; + } for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++) /* Reload can give another class so we need to check all allocnos. */ @@ -246,11 +270,14 @@ assign_hard_reg (allocno_t allocno, int retry_p) ALLOCNO_NUM (conflict_allocno))) { ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno)); - if (bitmap_bit_p (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno))) - continue; - bitmap_set_bit (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno)); + if (allocno_coalesced_p) + { + if (bitmap_bit_p (processed_coalesced_allocno_bitmap, + ALLOCNO_NUM (conflict_allocno))) + continue; + bitmap_set_bit (processed_coalesced_allocno_bitmap, + ALLOCNO_NUM (conflict_allocno)); + } if (ALLOCNO_ASSIGNED_P (conflict_allocno)) { if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0) @@ -268,6 +295,10 @@ assign_hard_reg (allocno_t allocno, int retry_p) } else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno)) { + allocate_and_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno), + class_size, + ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno)); conflict_costs = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno); if (conflict_costs != NULL) @@ -298,6 +329,9 @@ assign_hard_reg (allocno_t allocno, int retry_p) if (cover_class != ALLOCNO_COVER_CLASS (another_allocno) || ALLOCNO_ASSIGNED_P (another_allocno)) continue; + allocate_and_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno), + class_size, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno)); conflict_costs = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno); if (conflict_costs != NULL @@ -432,7 +466,7 @@ get_coalesced_allocnos_best_class_and_freq (allocno_t allocno, { *freq += ALLOCNO_FREQ (a); *best_class - = reg_class_subintersect [ALLOCNO_BEST_CLASS (a)] [*best_class]; + = reg_class_intersect [ALLOCNO_BEST_CLASS (a)] [*best_class]; if (a == allocno) break; } @@ -461,11 +495,9 @@ add_allocno_to_ordered_bucket (allocno_t allocno, allocno_t *bucket_ptr) break; get_coalesced_allocnos_best_class_and_freq (before, &best_class_before, &freq_before); - if (best_class != best_class_before - && class_subset_p [best_class_before] [best_class]) + if (strict_class_subset_p [best_class_before] [best_class]) break; - else if (best_class != best_class_before - && class_subset_p [best_class] [best_class_before]) + else if (strict_class_subset_p [best_class] [best_class_before]) ; else if (freq_before > freq) break; @@ -517,7 +549,8 @@ push_allocno_to_stack (allocno_t allocno) if (cover_class == NO_REGS) return; size = reg_class_nregs [cover_class] [ALLOCNO_MODE (allocno)]; - bitmap_clear (processed_coalesced_allocno_bitmap); + if (allocno_coalesced_p) + bitmap_clear (processed_coalesced_allocno_bitmap); for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) { @@ -527,11 +560,14 @@ push_allocno_to_stack (allocno_t allocno) ALLOCNO_NUM (conflict_allocno))) { ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno)); - if (bitmap_bit_p (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno))) - continue; - bitmap_set_bit (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno)); + if (allocno_coalesced_p) + { + if (bitmap_bit_p (processed_coalesced_allocno_bitmap, + ALLOCNO_NUM (conflict_allocno))) + continue; + bitmap_set_bit (processed_coalesced_allocno_bitmap, + ALLOCNO_NUM (conflict_allocno)); + } if (ALLOCNO_IN_GRAPH_P (conflict_allocno) && ! ALLOCNO_ASSIGNED_P (conflict_allocno)) { @@ -899,14 +935,6 @@ setup_allocno_left_conflicts_num (allocno_t allocno) cover_class = ALLOCNO_COVER_CLASS (allocno); hard_regs_num = class_hard_regs_num [cover_class]; - if (hard_regs_num != 0) - { - memcpy (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), - ALLOCNO_HARD_REG_COSTS (allocno), sizeof (int) * hard_regs_num); - memcpy (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno), - ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno), - sizeof (int) * hard_regs_num); - } CLEAR_HARD_REG_SET (temp_set); ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno); for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; @@ -932,7 +960,8 @@ setup_allocno_left_conflicts_num (allocno_t allocno) } } CLEAR_HARD_REG_SET (temp_set); - bitmap_clear (processed_coalesced_allocno_bitmap); + if (allocno_coalesced_p) + bitmap_clear (processed_coalesced_allocno_bitmap); if (cover_class != NO_REGS) for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);; a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) @@ -944,11 +973,14 @@ setup_allocno_left_conflicts_num (allocno_t allocno) { ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno)); - if (bitmap_bit_p (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno))) - continue; - bitmap_set_bit (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno)); + if (allocno_coalesced_p) + { + if (bitmap_bit_p (processed_coalesced_allocno_bitmap, + ALLOCNO_NUM (conflict_allocno))) + continue; + bitmap_set_bit (processed_coalesced_allocno_bitmap, + ALLOCNO_NUM (conflict_allocno)); + } if (! ALLOCNO_ASSIGNED_P (conflict_allocno)) conflict_allocnos_size += (reg_class_nregs @@ -987,14 +1019,6 @@ put_allocno_into_bucket (allocno_t allocno) cover_class = ALLOCNO_COVER_CLASS (allocno); hard_regs_num = class_hard_regs_num [cover_class]; - if (hard_regs_num != 0) - { - memcpy (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), - ALLOCNO_HARD_REG_COSTS (allocno), sizeof (int) * hard_regs_num); - memcpy (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno), - ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno), - sizeof (int) * hard_regs_num); - } if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno) return; ALLOCNO_IN_GRAPH_P (allocno) = TRUE; @@ -1059,21 +1083,26 @@ coalesced_allocno_conflict_p (allocno_t a1, allocno_t a2) allocno_t a, conflict_allocno, *allocno_vec; int i; - bitmap_clear (processed_coalesced_allocno_bitmap); - for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);; - a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + if (allocno_coalesced_p) { - bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a)); - if (a == a1) - break; + bitmap_clear (processed_coalesced_allocno_bitmap); + for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);; + a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) + { + bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a)); + if (a == a1) + break; + } } for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);; a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a)) { allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a); for (i = 0; (conflict_allocno = allocno_vec [i]) != NULL; i++) - if (bitmap_bit_p (processed_coalesced_allocno_bitmap, - ALLOCNO_NUM (conflict_allocno))) + if (conflict_allocno == a1 + || (allocno_coalesced_p + && bitmap_bit_p (processed_coalesced_allocno_bitmap, + ALLOCNO_NUM (conflict_allocno)))) return TRUE; if (a == a2) break; @@ -1118,13 +1147,14 @@ coalesce_allocnos (void) } } qsort (sorted_copies, cp_num, sizeof (copy_t), copy_freq_compare_func); - for (;cp_num != 0;) + for (; cp_num != 0;) { for (i = 0; i < cp_num; i++) { cp = sorted_copies [i]; if (! coalesced_allocno_conflict_p (cp->first, cp->second)) { + allocno_coalesced_p = TRUE; if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) fprintf (ira_dump_file, " Coalescing copy %d (freq=%d)\n", cp->num, cp->freq); @@ -1153,7 +1183,9 @@ color_allocnos (void) { unsigned int i; bitmap_iterator bi; + allocno_t a; + allocno_coalesced_p = FALSE; processed_coalesced_allocno_bitmap = ira_allocate_bitmap (); if (flag_ira_coalesce) coalesce_allocnos (); @@ -1161,19 +1193,34 @@ color_allocnos (void) colorable_allocno_bucket = NULL; uncolorable_allocno_bucket = NULL; EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) - put_allocno_into_bucket (allocnos [i]); + { + a = allocnos [i]; + if (ALLOCNO_COVER_CLASS (a) == NO_REGS) + { + ALLOCNO_HARD_REGNO (a) = -1; + ALLOCNO_ASSIGNED_P (a) = TRUE; + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + { + fprintf (ira_dump_file, " Spill"); + print_coalesced_allocno (a); + fprintf (ira_dump_file, "\n"); + } + continue; + } + put_allocno_into_bucket (a); + } push_allocnos_to_stack (); pop_allocnos_from_stack (); if (flag_ira_coalesce) - /* We don't need coalesced allocnos for retry_ira_color. */ + /* We don't need coalesced allocnos for reassign_pseudos. */ EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi) { - allocno_t a = allocnos [i]; - + a = allocnos [i]; ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a; ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a; } ira_free_bitmap (processed_coalesced_allocno_bitmap); + allocno_coalesced_p = FALSE; } @@ -1222,7 +1269,7 @@ print_loop_title (loop_tree_node_t loop_tree_node) static void color_pass (loop_tree_node_t loop_tree_node) { - int regno, hard_regno, index = -1; + int regno, hard_regno, hard_regs_num, index = -1; int cost, exit_freq, enter_freq; unsigned int j; bitmap_iterator bi; @@ -1273,7 +1320,10 @@ color_pass (loop_tree_node_t loop_tree_node) continue; if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED && loop_tree_node->reg_pressure [class] - <= available_class_regs [class])) + <= available_class_regs [class]) + || (hard_regno < 0 + && ! bitmap_bit_p (subloop_node->mentioned_allocnos, + ALLOCNO_NUM (subloop_allocno)))) { if (! ALLOCNO_ASSIGNED_P (subloop_allocno)) { @@ -1305,6 +1355,15 @@ color_pass (loop_tree_node_t loop_tree_node) } else { + hard_regs_num + = class_hard_regs_num [ALLOCNO_COVER_CLASS + (subloop_allocno)]; + allocate_and_set_costs + (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (subloop_allocno)); + allocate_and_set_costs + (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno), + hard_regs_num, 0); cost = (register_move_cost [mode] [class] [class] * (exit_freq + enter_freq)); ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index] -= cost; @@ -1321,11 +1380,14 @@ color_pass (loop_tree_node_t loop_tree_node) } else { + subloop_allocno = ALLOCNO_CAP_MEMBER (a); if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED && loop_tree_node->reg_pressure [class] - <= available_class_regs [class])) + <= available_class_regs [class]) + || (hard_regno < 0 + && ! bitmap_bit_p (subloop_node->mentioned_allocnos, + ALLOCNO_NUM (subloop_allocno)))) { - subloop_allocno = ALLOCNO_CAP_MEMBER (a); if (! ALLOCNO_ASSIGNED_P (subloop_allocno)) { ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno; @@ -1340,7 +1402,15 @@ color_pass (loop_tree_node_t loop_tree_node) enter_freq = loop_edge_freq (subloop_node, -1, FALSE); cost = (register_move_cost [mode] [class] [class] * (exit_freq + enter_freq)); - subloop_allocno = ALLOCNO_CAP_MEMBER (a); + hard_regs_num + = class_hard_regs_num [ALLOCNO_COVER_CLASS + (subloop_allocno)]; + allocate_and_set_costs + (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (subloop_allocno)); + allocate_and_set_costs + (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno), + hard_regs_num, 0); ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index] -= cost; ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno) [index] -= cost; @@ -1467,7 +1537,10 @@ move_spill_restore (void) class = ALLOCNO_COVER_CLASS (a); index = class_hard_reg_index [class] [hard_regno]; ira_assert (index >= 0); - cost = ALLOCNO_MEMORY_COST (a) - ALLOCNO_HARD_REG_COSTS (a) [index]; + cost = (ALLOCNO_MEMORY_COST (a) + - (ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a) [index])); for (subloop_node = loop_node->inner; subloop_node != NULL; subloop_node = subloop_node->next) @@ -1478,7 +1551,9 @@ move_spill_restore (void) if (subloop_allocno == NULL) continue; cost -= (ALLOCNO_MEMORY_COST (subloop_allocno) - - ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index]); + - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL + ? ALLOCNO_COVER_CLASS_COST (subloop_allocno) + : ALLOCNO_HARD_REG_COSTS (subloop_allocno) [index])); exit_freq = loop_edge_freq (subloop_node, regno, TRUE); enter_freq = loop_edge_freq (subloop_node, regno, FALSE); if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0) @@ -1550,10 +1625,6 @@ setup_curr_costs (allocno_t a) if (hard_regs_num == 0) return; mode = ALLOCNO_MODE (a); - memcpy (ALLOCNO_UPDATED_HARD_REG_COSTS (a), - ALLOCNO_HARD_REG_COSTS (a), sizeof (int) * hard_regs_num); - memcpy (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), - ALLOCNO_CONFLICT_HARD_REG_COSTS (a), sizeof (int) * hard_regs_num); for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) { if (cp->first == a) @@ -1578,6 +1649,13 @@ setup_curr_costs (allocno_t a) cost = (cp->first == a ? register_move_cost [mode] [class] [cover_class] : register_move_cost [mode] [cover_class] [class]); + allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_HARD_REG_COSTS (a), + hard_regs_num, ALLOCNO_COVER_CLASS_COST (a), + ALLOCNO_HARD_REG_COSTS (a)); + allocate_and_set_or_copy_costs + (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), + hard_regs_num, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); ALLOCNO_UPDATED_HARD_REG_COSTS (a) [i] -= cp->freq * cost; ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) [i] -= cp->freq * cost; } @@ -1677,8 +1755,10 @@ mark_allocation_change (int regno) else { ira_assert (class_hard_reg_index [cover_class] [old_hard_regno] >= 0); - cost = -(ALLOCNO_HARD_REG_COSTS (a) - [class_hard_reg_index [cover_class] [old_hard_regno]]); + cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a) + [class_hard_reg_index [cover_class] [old_hard_regno]]); update_copy_costs (a, FALSE); } overall_cost -= cost; @@ -1687,8 +1767,10 @@ mark_allocation_change (int regno) cost += ALLOCNO_UPDATED_MEMORY_COST (a); else if (class_hard_reg_index [cover_class] [hard_regno] >= 0) { - cost += (ALLOCNO_HARD_REG_COSTS (a) - [class_hard_reg_index [cover_class] [hard_regno]]); + cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a) + [class_hard_reg_index [cover_class] [hard_regno]]); update_copy_costs (a, TRUE); } else @@ -1697,23 +1779,30 @@ mark_allocation_change (int regno) overall_cost += cost; } -/* The function is analog of function `retry_global_alloc'. It is - called by reload to try to put spilled pseudo-register REGNO into a - hard register which is not in FORBIDDEN_REGS. */ +/* This function is called when the reload deletes memory-memory move. */ void -retry_ira_color (int regno, HARD_REG_SET forbidden_regs) +mark_memory_move_deletion (int dst_regno, int src_regno) +{ + allocno_t dst = regno_allocno_map [dst_regno]; + allocno_t src = regno_allocno_map [src_regno]; + + ira_assert (dst != NULL && src != NULL + && ALLOCNO_HARD_REGNO (dst) < 0 + && ALLOCNO_HARD_REGNO (src) < 0); + ALLOCNO_DONT_REASSIGN_P (dst) = TRUE; + ALLOCNO_DONT_REASSIGN_P (src) = TRUE; +} + +/* The function tries to assign a hard register (except for + FORBIDDEN_REGS) to allocno A and return TRUE in the case of + success. */ +static int +allocno_reload_assign (allocno_t a, HARD_REG_SET forbidden_regs) { - allocno_t a; int hard_regno; enum reg_class cover_class; + int regno = ALLOCNO_REGNO (a); - a = regno_allocno_map [regno]; - mark_allocation_change (regno); - ira_assert (reg_renumber [regno] < 0); - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf (ira_dump_file, - " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a), - ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a)); IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs); if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0) IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set); @@ -1727,8 +1816,11 @@ retry_ira_color (int regno, HARD_REG_SET forbidden_regs) { ira_assert (class_hard_reg_index [cover_class] [hard_regno] >= 0); overall_cost -= (ALLOCNO_UPDATED_MEMORY_COST (a) - - (ALLOCNO_HARD_REG_COSTS (a) - [class_hard_reg_index [cover_class] [hard_regno]])); + - (ALLOCNO_HARD_REG_COSTS (a) == NULL + ? ALLOCNO_COVER_CLASS_COST (a) + : ALLOCNO_HARD_REG_COSTS (a) + [class_hard_reg_index + [cover_class] [hard_regno]])); if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0 && ! hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a), call_used_reg_set)) @@ -1742,14 +1834,131 @@ retry_ira_color (int regno, HARD_REG_SET forbidden_regs) the hard register, and mark that register live. */ if (reg_renumber[regno] >= 0) { - if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf (ira_dump_file, ": reassign to %d", reg_renumber[regno]); + if (internal_flag_ira_verbose > 3 && stderr != NULL) + fprintf (stderr, ": reassign to %d", reg_renumber[regno]); SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]); mark_home_live (regno); } + if (internal_flag_ira_verbose > 3 && stderr != NULL) + fprintf (stderr, "\n"); + + return reg_renumber[regno] >= 0; +} + +/* The function is used to sort pseudos according their usage + frequencies (putting most frequently ones first). */ +static int +pseudo_reg_compare (const void *v1p, const void *v2p) +{ + int regno1 = *(int *) v1p; + int regno2 = *(int *) v2p; + int diff; + + if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0) + return diff; + return regno1 - regno2; +} + +/* The function tries to allocate hard registers to + SPILLED_PSEUDO_REGS (there are NUM of them) or spilled pseudos + conflicting with pseudos in SPILLED_PSEUDO_REGS. It returns TRUE + and update SPILLED, if the allocation has been changed. The + function doesn't use BAD_SPILL_REGS and corresponding hard + registers in PSEUDO_FORBIDDEN_REGS and PSEUDO_PREVIOUS_REGS. */ +int +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) +{ + int i, j, m, n, regno, changed_p; + allocno_t a, conflict_a, *allocno_vec; + HARD_REG_SET forbidden_regs; + + if (num > 1) + qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare); + changed_p = FALSE; + for (m = i = 0; i < num; i++) + { + regno = spilled_pseudo_regs [i]; + COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs); + IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs [regno]); + IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs [regno]); + gcc_assert (reg_renumber [regno] < 0); + a = regno_allocno_map [regno]; + mark_allocation_change (regno); + ira_assert (reg_renumber [regno] < 0); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, + " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a), + ALLOCNO_UPDATED_MEMORY_COST (a) + - ALLOCNO_COVER_CLASS_COST (a)); + allocno_reload_assign (a, forbidden_regs); + if (reg_renumber [regno] >= 0) + { + CLEAR_REGNO_REG_SET (spilled, regno); + changed_p = TRUE; + } + else + spilled_pseudo_regs [m++] = regno; + } + if (m == 0) + return changed_p; if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) - fprintf (ira_dump_file, "\n"); + { + fprintf (ira_dump_file, " Spilled regs"); + for (i = 0; i < m; i++) + fprintf (ira_dump_file, " %d", spilled_pseudo_regs [i]); + fprintf (ira_dump_file, "\n"); + } + consideration_allocno_bitmap = ira_allocate_bitmap (); + sorted_allocnos = ira_allocate (sizeof (allocno_t) * allocnos_num); + for (i = n = 0; i < m; i++) + { + regno = spilled_pseudo_regs [i]; + a = regno_allocno_map [regno]; + allocno_vec = ALLOCNO_CONFLICT_ALLOCNO_VEC (a); + for (j = 0; (conflict_a = allocno_vec [j]) != NULL; j++) + if (ALLOCNO_HARD_REGNO (conflict_a) < 0 + && ! ALLOCNO_DONT_REASSIGN_P (conflict_a) + && ! bitmap_bit_p (consideration_allocno_bitmap, + ALLOCNO_NUM (conflict_a))) + { + sorted_allocnos [n++] = conflict_a; + bitmap_set_bit (consideration_allocno_bitmap, + ALLOCNO_NUM (conflict_a)); + } + } + if (n != 0) + { + start_allocno_priorities (sorted_allocnos, n); + qsort (sorted_allocnos, n, sizeof (allocno_t), + allocno_priority_compare_func); + finish_allocno_priorities (); + for (i = 0; i < n; i++) + { + a = sorted_allocnos [i]; + regno = ALLOCNO_REGNO (a); + COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs); + IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs [regno]); + IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs [regno]); + if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) + fprintf (ira_dump_file, + " Try assign %d(a%d), cost=%d", + regno, ALLOCNO_NUM (a), + ALLOCNO_UPDATED_MEMORY_COST (a) + - ALLOCNO_COVER_CLASS_COST (a)); + if (allocno_reload_assign (a, forbidden_regs)) + { + changed_p = TRUE; + bitmap_clear_bit (spilled, regno); + } + } + } + ira_free (sorted_allocnos); + ira_free_bitmap (consideration_allocno_bitmap); + return changed_p; } diff --git a/gcc/ira-conflicts.c b/gcc/ira-conflicts.c index ef850376800..068672deee4 100644 --- a/gcc/ira-conflicts.c +++ b/gcc/ira-conflicts.c @@ -367,7 +367,7 @@ add_insn_allocno_copies (rtx insn) rtx set, operand, dup; const char *str; int commut_p, bound_p; - int i, j, freq, hard_regno, cost, index; + int i, j, freq, hard_regno, cost, index, hard_regs_num; copy_t cp; allocno_t a; enum reg_class class, cover_class; @@ -412,6 +412,12 @@ add_insn_allocno_copies (rtx insn) cost = register_move_cost [mode] [cover_class] [class] * freq; else cost = register_move_cost [mode] [class] [cover_class] * freq; + hard_regs_num = class_hard_regs_num [cover_class]; + allocate_and_set_costs + (&ALLOCNO_HARD_REG_COSTS (a), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (a)); + allocate_and_set_costs + (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), hard_regs_num, 0); ALLOCNO_HARD_REG_COSTS (a) [index] -= cost; ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [index] -= cost; } @@ -472,6 +478,13 @@ add_insn_allocno_copies (rtx insn) cost = register_move_cost [mode] [class] [cover_class]; cost *= freq; + hard_regs_num = class_hard_regs_num [cover_class]; + allocate_and_set_costs + (&ALLOCNO_HARD_REG_COSTS (a), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (a)); + allocate_and_set_costs + (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), + hard_regs_num, 0); ALLOCNO_HARD_REG_COSTS (a) [index] -= cost; ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [index] -= cost; bound_p = TRUE; @@ -531,6 +544,13 @@ add_insn_allocno_copies (rtx insn) cost = register_move_cost [mode] [class] [cover_class]; cost *= (freq < 8 ? 1 : freq / 8); + hard_regs_num = class_hard_regs_num [cover_class]; + allocate_and_set_costs + (&ALLOCNO_HARD_REG_COSTS (a), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (a)); + allocate_and_set_costs + (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), + hard_regs_num, 0); ALLOCNO_HARD_REG_COSTS (a) [index] -= cost; ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [index] -= cost; } @@ -649,13 +669,12 @@ allocno_conflict_p (allocno_t a1, allocno_t a2) for (r1 = ALLOCNO_LIVE_RANGES (a1), r2 = ALLOCNO_LIVE_RANGES (a2); r1 != NULL && r2 != NULL;) { - if ((r2->start <= r1->start && r1->start <= r2->finish) - || (r1->start <= r2->start && r2->start <= r1->finish)) - return TRUE; if (r1->start > r2->finish) r1 = r1->next; - else + else if (r2->start > r1->finish) r2 = r2->next; + else + return TRUE; } return FALSE; } diff --git a/gcc/ira-costs.c b/gcc/ira-costs.c index 37317eeaaae..6b12eded0a3 100644 --- a/gcc/ira-costs.c +++ b/gcc/ira-costs.c @@ -59,6 +59,7 @@ static void process_bb_node_for_costs (loop_tree_node_t); static void find_allocno_class_costs (void); static void process_bb_node_for_hard_reg_moves (loop_tree_node_t); static void setup_allocno_cover_class_and_costs (void); +static void free_ira_costs (void); #ifdef FORBIDDEN_INC_DEC_CLASSES /* Indexed by n, is nonzero if (REG n) is used in an auto-inc or @@ -77,7 +78,7 @@ struct costs }; /* Initialized once. It is a size of the allocated struct costs. */ -static int struct_costs_size; +static int max_struct_costs_size; /* Allocated and initialized once, and used to initialize cost values for each insn. */ @@ -94,6 +95,18 @@ static struct costs *this_op_costs [MAX_RECOG_OPERANDS]; allocno. */ static struct costs *total_costs; +/* Classes used for cost calculation. */ +static enum reg_class *cost_classes; + +/* The size of the previous array. */ +static int cost_classes_num; + +/* The array containing order numbers of cost classes. */ +static int cost_class_nums [N_REG_CLASSES]; + +/* It is the current size of struct costs. */ +static int struct_costs_size; + /* Return pointer to structure containing costs of allocno with given NUM in array ARR. */ #define COSTS_OF_ALLOCNO(arr, num) \ @@ -133,8 +146,8 @@ copy_cost (rtx x, enum machine_mode mode, enum reg_class class, int to_p, sri.extra_cost = 0; secondary_class = targetm.secondary_reload (to_p, x, class, mode, &sri); - if (move_cost [mode] == NULL) - init_move_cost (mode); + if (register_move_cost [mode] == NULL) + init_register_move_cost (mode); if (secondary_class != NO_REGS) return (move_cost [mode] [secondary_class] [class] @@ -279,19 +292,19 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, needs to do a copy, which is one instruction. */ struct costs *pp = this_op_costs [i]; - if (move_cost [mode] == NULL) - init_move_cost (mode); + if (register_move_cost [mode] == NULL) + init_register_move_cost (mode); - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) { - class = important_classes [k]; + class = cost_classes [k]; pp->cost [k] = ((recog_data.operand_type [i] != OP_OUT - ? may_move_in_cost [mode] [class] [classes [i]] - : 0) + ? register_may_move_in_cost [mode] + [class] [classes [i]] : 0) + (recog_data.operand_type [i] != OP_IN - ? may_move_out_cost [mode] [classes [i]] [class] - : 0)); + ? register_may_move_out_cost [mode] + [classes [i]] [class] : 0)); } /* If the alternative actually allows memory, make @@ -326,9 +339,10 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, + (recog_data.operand_type [i] != OP_OUT ? memory_move_cost [mode] [classes [i]] [1] : 0)); - else + else if (reg_class_intersect + [pref_class] [classes [i]] == NO_REGS) alt_cost - += (may_move_in_cost + += (register_move_cost [mode] [pref_class] [classes [i]]); } if (REGNO (ops [i]) != REGNO (ops [j]) @@ -375,7 +389,7 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, to be allocated to a register that can be the base of an address, i.e. BASE_REG_CLASS. */ classes [i] - = reg_class_subunion [classes [i]] + = reg_class_union [classes [i]] [base_reg_class (VOIDmode, ADDRESS, SCRATCH)]; break; @@ -461,15 +475,13 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, win = 1; allows_mem [i] = 1; case 'r': - classes [i] - = reg_class_subunion [classes [i]] [GENERAL_REGS]; + classes [i] = reg_class_union [classes [i]] [GENERAL_REGS]; break; default: if (REG_CLASS_FROM_CONSTRAINT (c, p) != NO_REGS) - classes [i] - = reg_class_subunion [classes [i]] - [REG_CLASS_FROM_CONSTRAINT (c, p)]; + classes [i] = reg_class_union [classes [i]] + [REG_CLASS_FROM_CONSTRAINT (c, p)]; #ifdef EXTRA_CONSTRAINT_STR else if (EXTRA_CONSTRAINT_STR (op, c, p)) win = 1; @@ -492,7 +504,7 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, can be the base of an address, i.e. BASE_REG_CLASS. */ classes [i] - = reg_class_subunion [classes [i]] + = reg_class_union [classes [i]] [base_reg_class (VOIDmode, ADDRESS, SCRATCH)]; } #endif @@ -528,19 +540,19 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, { struct costs *pp = this_op_costs [i]; - if (move_cost [mode] == NULL) - init_move_cost (mode); + if (register_move_cost [mode] == NULL) + init_register_move_cost (mode); - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) { - class = important_classes [k]; + class = cost_classes [k]; pp->cost [k] = ((recog_data.operand_type [i] != OP_OUT - ? may_move_in_cost [mode] [class] [classes [i]] - : 0) + ? register_may_move_in_cost [mode] + [class] [classes [i]] : 0) + (recog_data.operand_type [i] != OP_IN - ? may_move_out_cost [mode] [classes [i]] [class] - : 0)); + ? register_may_move_out_cost [mode] + [classes [i]] [class] : 0)); } /* If the alternative actually allows memory, make @@ -575,9 +587,10 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, + (recog_data.operand_type [i] != OP_OUT ? memory_move_cost [mode] [classes [i]] [1] : 0)); - else + else if (reg_class_intersect + [pref_class] [classes [i]] == NO_REGS) alt_cost - += (may_move_in_cost + += (register_move_cost [mode] [pref_class] [classes [i]]); } } @@ -626,7 +639,7 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, pp->mem_cost = MIN (pp->mem_cost, (qq->mem_cost + alt_cost) * scale); - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) pp->cost [k] = MIN (pp->cost [k], (qq->cost [k] + alt_cost) * scale); } @@ -672,12 +685,12 @@ record_reg_classes (int n_alts, int n_ops, rtx *ops, && (reg_class_size [pref] == (unsigned) CLASS_MAX_NREGS (pref, mode)) && register_move_cost [mode] [pref] [pref] < 10 * 2) - op_costs [i]->cost [important_class_nums [pref]] = -1; + op_costs [i]->cost [cost_class_nums [pref]] = -1; } else if (regno < FIRST_PSEUDO_REGISTER) - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) { - class = important_classes [k]; + class = cost_classes [k]; if (TEST_HARD_REG_BIT (reg_class_contents [class], regno) && (reg_class_size [class] == (unsigned) CLASS_MAX_NREGS (class, mode))) @@ -894,12 +907,13 @@ record_address_regs (enum machine_mode mode, rtx x, int context, ALLOCNO_NUM (ira_curr_regno_allocno_map [REGNO (x)])); pp->mem_cost += (memory_move_cost [Pmode] [class] [1] * scale) / 2; - if (move_cost [Pmode] == NULL) - init_move_cost (Pmode); - for (k = 0; k < important_classes_num; k++) + if (register_move_cost [Pmode] == NULL) + init_register_move_cost (Pmode); + for (k = 0; k < cost_classes_num; k++) { - i = important_classes [k]; - pp->cost [k] += (may_move_in_cost [Pmode] [i] [class] * scale) / 2; + i = cost_classes [k]; + pp->cost [k] += (register_may_move_in_cost [Pmode] [i] [class] + * scale) / 2; } } break; @@ -1037,7 +1051,7 @@ scan_one_insn (rtx insn) struct costs *q = op_costs [i]; p->mem_cost += q->mem_cost * frequency; - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) p->cost [k] += q->cost [k] * frequency; } @@ -1066,9 +1080,9 @@ print_costs (FILE *f) else fprintf (f, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num); fprintf (f, ") costs:"); - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) { - class = important_classes [k]; + class = cost_classes [k]; if (contains_reg_of_mode [class] [PSEUDO_REGNO_MODE (regno)] #ifdef FORBIDDEN_INC_DEC_CLASSES && (! in_inc_dec [i] || ! forbidden_inc_dec_class [class]) @@ -1127,6 +1141,34 @@ find_allocno_class_costs (void) if (internal_flag_ira_verbose > 0 && ira_dump_file) fprintf (ira_dump_file, "\nPass %i for finding allocno costs\n\n", pass); + if (pass != flag_expensive_optimizations) + { + for (cost_classes_num = 0; + cost_classes_num < reg_class_cover_size; + cost_classes_num++) + { + cost_classes [cost_classes_num] + = reg_class_cover [cost_classes_num]; + cost_class_nums [cost_classes [cost_classes_num]] + = cost_classes_num; + } + struct_costs_size + = sizeof (struct costs) + sizeof (int) * (cost_classes_num - 1); + } + else + { + for (cost_classes_num = 0; + cost_classes_num < important_classes_num; + cost_classes_num++) + { + cost_classes [cost_classes_num] + = important_classes [cost_classes_num]; + cost_class_nums [cost_classes [cost_classes_num]] + = cost_classes_num; + } + struct_costs_size + = sizeof (struct costs) + sizeof (int) * (cost_classes_num - 1); + } /* Zero out our accumulation of the cost of each class for each allocno. */ memset (total_costs, 0, allocnos_num * struct_costs_size); @@ -1169,13 +1211,13 @@ find_allocno_class_costs (void) && (father_a = father->regno_allocno_map [i]) != NULL) { father_a_num = ALLOCNO_NUM (father_a); - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) COSTS_OF_ALLOCNO (total_costs, father_a_num)->cost [k] += COSTS_OF_ALLOCNO (total_costs, a_num)->cost [k]; COSTS_OF_ALLOCNO (total_costs, father_a_num)->mem_cost += COSTS_OF_ALLOCNO (total_costs, a_num)->mem_cost; } - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) temp_costs->cost [k] += COSTS_OF_ALLOCNO (total_costs, a_num)->cost [k]; temp_costs->mem_cost @@ -1187,9 +1229,9 @@ find_allocno_class_costs (void) } best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1; best = ALL_REGS; - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) { - class = important_classes [k]; + class = cost_classes [k]; /* Ignore classes that are too small for this operand or invalid for an operand that was auto-incremented. */ if (! contains_reg_of_mode [class] [PSEUDO_REGNO_MODE (i)] @@ -1208,7 +1250,7 @@ find_allocno_class_costs (void) best = (enum reg_class) class; } else if (temp_costs->cost [k] == best_cost) - best = reg_class_subunion [best] [class]; + best = reg_class_union [best] [class]; } if (best_cost > temp_costs->mem_cost) common_class = NO_REGS; @@ -1224,16 +1266,16 @@ find_allocno_class_costs (void) { a_num = ALLOCNO_NUM (a); if (common_class == NO_REGS) - best = NO_REGS; + best = NO_REGS; else { /* Finding best class which is cover class for the register. */ best_cost = (1 << (HOST_BITS_PER_INT - 2)) - 1; best = ALL_REGS; - for (k = 0; k < important_classes_num; k++) + for (k = 0; k < cost_classes_num; k++) { - class = important_classes [k]; + class = cost_classes [k]; if (! class_subset_p [class] [common_class]) continue; /* Ignore classes that are too small for this @@ -1259,7 +1301,7 @@ find_allocno_class_costs (void) } else if (COSTS_OF_ALLOCNO (total_costs, a_num)->cost [k] == best_cost) - best = reg_class_subunion [best] [class]; + best = reg_class_union [best] [class]; } } if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL @@ -1301,7 +1343,7 @@ find_allocno_class_costs (void) static void process_bb_node_for_hard_reg_moves (loop_tree_node_t loop_tree_node) { - int i, freq, cost, src_regno, dst_regno, hard_regno, to_p; + int i, freq, cost, src_regno, dst_regno, hard_regno, to_p, hard_regs_num; allocno_t a; enum reg_class class, hard_reg_class; enum machine_mode mode; @@ -1353,6 +1395,11 @@ process_bb_node_for_hard_reg_moves (loop_tree_node_t loop_tree_node) hard_reg_class = REGNO_REG_CLASS (hard_regno); cost = (to_p ? register_move_cost [mode] [hard_reg_class] [class] : register_move_cost [mode] [class] [hard_reg_class]) * freq; + hard_regs_num = class_hard_regs_num [class]; + allocate_and_set_costs (&ALLOCNO_HARD_REG_COSTS (a), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (a)); + allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), + hard_regs_num, 0); ALLOCNO_HARD_REG_COSTS (a) [i] -= cost; ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [i] -= cost; ALLOCNO_COVER_CLASS_COST (a) = MIN (ALLOCNO_COVER_CLASS_COST (a), @@ -1369,6 +1416,12 @@ process_bb_node_for_hard_reg_moves (loop_tree_node_t loop_tree_node) break; if ((a = father->regno_allocno_map [regno]) == NULL) break; + hard_regs_num = class_hard_regs_num [ALLOCNO_COVER_CLASS (a)]; + allocate_and_set_costs + (&ALLOCNO_HARD_REG_COSTS (a), hard_regs_num, + ALLOCNO_COVER_CLASS_COST (a)); + allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), + hard_regs_num, 0); ALLOCNO_HARD_REG_COSTS (a) [i] -= cost; ALLOCNO_CONFLICT_HARD_REG_COSTS (a) [i] -= cost; ALLOCNO_COVER_CLASS_COST (a) @@ -1387,7 +1440,6 @@ setup_allocno_cover_class_and_costs (void) { int i, j, n, regno; int *reg_costs; - int *reg_conflict_costs; enum reg_class cover_class, class; enum machine_mode mode; allocno_t a; @@ -1407,21 +1459,19 @@ setup_allocno_cover_class_and_costs (void) ALLOCNO_AVAILABLE_REGS_NUM (a) = available_class_regs [cover_class]; ALLOCNO_COVER_CLASS_COST (a) = (COSTS_OF_ALLOCNO (total_costs, i) - ->cost [important_class_nums [allocno_pref [i]]]); - n = class_hard_regs_num [cover_class]; - ALLOCNO_HARD_REG_COSTS (a) = reg_costs = ira_allocate (n * sizeof (int)); - ALLOCNO_CONFLICT_HARD_REG_COSTS (a) - = reg_conflict_costs = ira_allocate (n * sizeof (int)); - ALLOCNO_UPDATED_HARD_REG_COSTS (a) = ira_allocate (n * sizeof (int)); - ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) - = ira_allocate (n * sizeof (int)); - memset (reg_conflict_costs, 0, n * sizeof (int)); - for (j = n - 1; j >= 0; j--) + ->cost [cost_class_nums [allocno_pref [i]]]); + if (ALLOCNO_COVER_CLASS (a) != allocno_pref [i]) { - regno = class_hard_regs [cover_class] [j]; - class = REGNO_REG_CLASS (regno); - reg_costs [j] = (COSTS_OF_ALLOCNO (total_costs, i) - ->cost [important_class_nums [class]]); + n = class_hard_regs_num [cover_class]; + ALLOCNO_HARD_REG_COSTS (a) + = reg_costs = ira_allocate (n * sizeof (int)); + for (j = n - 1; j >= 0; j--) + { + regno = class_hard_regs [cover_class] [j]; + class = REGNO_REG_CLASS (regno); + reg_costs [j] = (COSTS_OF_ALLOCNO (total_costs, i) + ->cost [cost_class_nums [class]]); + } } } traverse_loop_tree (FALSE, ira_loop_tree_root, @@ -1437,33 +1487,70 @@ init_ira_costs_once (void) { int i; - struct_costs_size + init_cost = NULL; + for (i = 0; i < MAX_RECOG_OPERANDS; i++) + { + op_costs [i] = NULL; + this_op_costs [i] = NULL; + } + temp_costs = NULL; + cost_classes = NULL; +} + +/* The function frees different cost vectors. */ +static void +free_ira_costs (void) +{ + int i; + + if (init_cost != NULL) + free (init_cost); + init_cost = NULL; + for (i = 0; i < MAX_RECOG_OPERANDS; i++) + { + if (op_costs [i] != NULL) + free (op_costs [i]); + if (this_op_costs [i] != NULL) + free (this_op_costs [i]); + op_costs [i] = this_op_costs [i] = NULL; + } + if (temp_costs != NULL) + free (temp_costs); + temp_costs = NULL; + if (cost_classes != NULL) + free (cost_classes); + cost_classes = NULL; +} + +/* The function called every time when register related information is + changed. */ +void +init_ira_costs (void) +{ + int i; + + free_ira_costs (); + max_struct_costs_size = sizeof (struct costs) + sizeof (int) * (important_classes_num - 1); - init_cost = xmalloc (struct_costs_size); + /* Don't use ira_allocate because vectors live through several IRA calls. */ + init_cost = xmalloc (max_struct_costs_size); init_cost->mem_cost = 10000; for (i = 0; i < important_classes_num; i++) init_cost->cost [i] = 10000; for (i = 0; i < MAX_RECOG_OPERANDS; i++) { - op_costs [i] = xmalloc (struct_costs_size); - this_op_costs [i] = xmalloc (struct_costs_size); + op_costs [i] = xmalloc (max_struct_costs_size); + this_op_costs [i] = xmalloc (max_struct_costs_size); } - temp_costs = xmalloc (struct_costs_size); + temp_costs = xmalloc (max_struct_costs_size); + cost_classes = xmalloc (sizeof (enum reg_class) * important_classes_num); } /* Function called once at the end of compiler work. */ void finish_ira_costs_once (void) { - int i; - - free (temp_costs); - for (i = MAX_RECOG_OPERANDS - 1; i >= 0; i--) - { - free (this_op_costs [i]); - free (op_costs [i]); - } - free (init_cost); + free_ira_costs (); } @@ -1473,7 +1560,7 @@ finish_ira_costs_once (void) void ira_costs (void) { - total_costs = ira_allocate (struct_costs_size * allocnos_num); + total_costs = ira_allocate (max_struct_costs_size * allocnos_num); allocno_pref_buffer = ira_allocate (sizeof (enum reg_class) * allocnos_num); find_allocno_class_costs (); setup_allocno_cover_class_and_costs (); @@ -1505,55 +1592,59 @@ tune_allocno_costs_and_cover_classes (void) continue; mode = ALLOCNO_MODE (a); n = class_hard_regs_num [cover_class]; - reg_costs = ALLOCNO_HARD_REG_COSTS (a); min_cost = INT_MAX; if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0) - for (j = n - 1; j >= 0; j--) - { - regno = class_hard_regs [cover_class] [j]; - class = REGNO_REG_CLASS (regno); - cost = 0; - if (! flag_ira_ipra) - { - /* ??? If only part is call clobbered. */ - if (! hard_reg_not_in_set_p (regno, mode, call_used_reg_set)) - { - cost += (ALLOCNO_CALL_FREQ (a) - * (memory_move_cost [mode] [class] [0] - + memory_move_cost [mode] [class] [1])); - } - } - else - { - allocno_calls - = (VEC_address (rtx, regno_calls [ALLOCNO_REGNO (a)]) - + ALLOCNO_CALLS_CROSSED_START (a)); - ira_assert (allocno_calls != NULL); - for (k = ALLOCNO_CALLS_CROSSED_NUM (a) - 1; k >= 0; k--) - { - call = allocno_calls [k]; - freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (call)); - if (freq == 0) - freq = 1; - get_call_invalidated_used_regs (call, &clobbered_regs, - FALSE); - /* ??? If only part is call clobbered. */ - if (! hard_reg_not_in_set_p (regno, mode, clobbered_regs)) - cost - += freq * (memory_move_cost [mode] [class] [0] - + memory_move_cost [mode] [class] [1]); - } - } + { + allocate_and_set_costs + (&ALLOCNO_HARD_REG_COSTS (a), n, ALLOCNO_COVER_CLASS_COST (a)); + reg_costs = ALLOCNO_HARD_REG_COSTS (a); + for (j = n - 1; j >= 0; j--) + { + regno = class_hard_regs [cover_class] [j]; + class = REGNO_REG_CLASS (regno); + cost = 0; + if (! flag_ira_ipra) + { + /* ??? If only part is call clobbered. */ + if (! hard_reg_not_in_set_p (regno, mode, call_used_reg_set)) + { + cost += (ALLOCNO_CALL_FREQ (a) + * (memory_move_cost [mode] [class] [0] + + memory_move_cost [mode] [class] [1])); + } + } + else + { + allocno_calls + = (VEC_address (rtx, regno_calls [ALLOCNO_REGNO (a)]) + + ALLOCNO_CALLS_CROSSED_START (a)); + ira_assert (allocno_calls != NULL); + for (k = ALLOCNO_CALLS_CROSSED_NUM (a) - 1; k >= 0; k--) + { + call = allocno_calls [k]; + freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (call)); + if (freq == 0) + freq = 1; + get_call_invalidated_used_regs (call, &clobbered_regs, + FALSE); + /* ??? If only part is call clobbered. */ + if (! hard_reg_not_in_set_p (regno, mode, clobbered_regs)) + cost + += freq * (memory_move_cost [mode] [class] [0] + + memory_move_cost [mode] [class] [1]); + } + } #ifdef IRA_HARD_REGNO_ADD_COST_MULTIPLIER - cost += ((memory_move_cost [mode] [class] [0] - + memory_move_cost [mode] [class] [1]) - * ALLOCNO_FREQ (a) - * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2); + cost += ((memory_move_cost [mode] [class] [0] + + memory_move_cost [mode] [class] [1]) + * ALLOCNO_FREQ (a) + * IRA_HARD_REGNO_ADD_COST_MULTIPLIER (regno) / 2); #endif - reg_costs [j] += cost; - if (min_cost > reg_costs [j]) - min_cost = reg_costs [j]; - } + reg_costs [j] += cost; + if (min_cost > reg_costs [j]) + min_cost = reg_costs [j]; + } + } if (min_cost != INT_MAX) ALLOCNO_COVER_CLASS_COST (a) = min_cost; } diff --git a/gcc/ira-emit.c b/gcc/ira-emit.c index baba58dd59a..5fb9e172003 100644 --- a/gcc/ira-emit.c +++ b/gcc/ira-emit.c @@ -522,7 +522,7 @@ traverse_moves (struct move *move) static struct move * modify_move_list (struct move *list) { - int i, n, nregs, hard_regno, hard_regs_num; + int i, n, nregs, hard_regno; allocno_t to, from, new_allocno; struct move *move, *new_move, *set_move, *first, *last; @@ -604,20 +604,6 @@ modify_move_list (struct move *list) = ALLOCNO_COVER_CLASS (set_move->to); ALLOCNO_BEST_CLASS (new_allocno) = ALLOCNO_COVER_CLASS (new_allocno); - hard_regs_num - = class_hard_regs_num [ALLOCNO_COVER_CLASS (new_allocno)]; - ALLOCNO_HARD_REG_COSTS (new_allocno) - = ira_allocate (hard_regs_num * sizeof (int)); - memset (ALLOCNO_HARD_REG_COSTS (new_allocno), 0, - hard_regs_num * sizeof (int)); - ALLOCNO_CONFLICT_HARD_REG_COSTS (new_allocno) - = ira_allocate (hard_regs_num * sizeof (int)); - memset (ALLOCNO_CONFLICT_HARD_REG_COSTS (new_allocno), 0, - hard_regs_num * sizeof (int)); - ALLOCNO_UPDATED_HARD_REG_COSTS (new_allocno) - = ira_allocate (hard_regs_num * sizeof (int)); - ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (new_allocno) - = ira_allocate (hard_regs_num * sizeof (int)); ALLOCNO_ASSIGNED_P (new_allocno) = TRUE; ALLOCNO_HARD_REGNO (new_allocno) = -1; ALLOCNO_REG (new_allocno) diff --git a/gcc/ira-int.h b/gcc/ira-int.h index 4030173c47b..6fba7508806 100644 --- a/gcc/ira-int.h +++ b/gcc/ira-int.h @@ -265,7 +265,9 @@ struct allocno /* TRUE if the allocno was a destination of removed move at the end of loop because the value is not changed in loop. */ unsigned int mem_optimized_dest_p : 1; - + /* In the reload, we should not reassign a hard register to the + allocno got memory if the flag value is TRUE. */ + unsigned int dont_reassign_p : 1; #ifdef STACK_REGS /* Set to TRUE if allocno can't be allocated in the stack register. */ @@ -329,6 +331,7 @@ struct allocno #define ALLOCNO_CALLS_CROSSED_NUM(A) ((A)->calls_crossed_num) #define ALLOCNO_MEM_OPTIMIZED_DEST(A) ((A)->mem_optimized_dest) #define ALLOCNO_MEM_OPTIMIZED_DEST_P(A) ((A)->mem_optimized_dest_p) +#define ALLOCNO_DONT_REASSIGN_P(A) ((A)->dont_reassign_p) #ifdef STACK_REGS #define ALLOCNO_NO_STACK_REG_P(A) ((A)->no_stack_reg_p) #define ALLOCNO_TOTAL_NO_STACK_REG_P(A) ((A)->total_no_stack_reg_p) @@ -493,15 +496,22 @@ extern HARD_REG_SET reg_mode_hard_regset [FIRST_PSEUDO_REGISTER] [NUM_MACHINE_MODES]; /* Array analog of macros MEMORY_MOVE_COST and REGISTER_MOVE_COST. */ -extern int memory_move_cost [MAX_MACHINE_MODE] [N_REG_CLASSES] [2]; -extern int register_move_cost [MAX_MACHINE_MODE] [N_REG_CLASSES] - [N_REG_CLASSES]; +extern short memory_move_cost [MAX_MACHINE_MODE] [N_REG_CLASSES] [2]; +extern move_table *register_move_cost [MAX_MACHINE_MODE]; -/* Register class subset relation. */ -extern int class_subset_p [N_REG_CLASSES] [N_REG_CLASSES]; +/* Similar to move_cost, but here we don't have to move if the first + index is a subset of the second (taking registers available for + allocation into account) so in that case the cost is zero. */ +extern move_table *register_may_move_in_cost [MAX_MACHINE_MODE]; -/* The biggest class inside of intersection of the two classes. */ -extern enum reg_class reg_class_subintersect [N_REG_CLASSES] [N_REG_CLASSES]; +/* Similar, but here we don't have to move if the first index is a + superset of the second (taking registers available for allocation + into account) so in that case the cost is zero. */ +extern move_table *register_may_move_out_cost [MAX_MACHINE_MODE]; + +/* Register class (strict) subset relation. */ +extern int class_subset_p [N_REG_CLASSES] [N_REG_CLASSES]; +extern int strict_class_subset_p [N_REG_CLASSES] [N_REG_CLASSES]; /* Hard registers which can be used for the allocation of given register class. */ @@ -547,12 +557,19 @@ extern enum reg_class important_classes [N_REG_CLASSES]; /* The array containing order numbers of important classes (they are subclasses of cover classes). */ -extern enum reg_class important_class_nums [N_REG_CLASSES]; +extern int important_class_nums [N_REG_CLASSES]; /* Map of register classes to corresponding cover class containing the given class. */ extern enum reg_class class_translate [N_REG_CLASSES]; +/* The biggest important class inside of intersection of the two + classes (taking only registers available for allocation). */ +extern enum reg_class reg_class_intersect [N_REG_CLASSES] [N_REG_CLASSES]; +/* The biggest important class inside of union of the two classes + (taking only registers available for allocation). */ +extern enum reg_class reg_class_union [N_REG_CLASSES] [N_REG_CLASSES]; + extern void set_non_alloc_regs (int); extern void *ira_allocate (size_t); extern void *ira_reallocate (void *, size_t); @@ -561,10 +578,10 @@ extern bitmap ira_allocate_bitmap (void); extern void ira_free_bitmap (bitmap); extern regset ira_allocate_regset (void); extern void ira_free_regset (regset); -extern int hard_reg_not_in_set_p (int, enum machine_mode, HARD_REG_SET); extern void print_disposition (FILE *); extern void debug_disposition (void); extern void debug_class_cover (void); +extern void init_register_move_cost (enum machine_mode); /* Regno invariant flags. */ extern int *reg_equiv_invariant_p; @@ -586,7 +603,6 @@ extern void traverse_loop_tree (int, loop_tree_node_t, void (*) (loop_tree_node_t)); extern allocno_t create_allocno (int, int, loop_tree_node_t); extern void allocate_allocno_conflicts (allocno_t, int); -extern int allocno_conflict_index (allocno_t, allocno_t); extern void add_allocno_conflict (allocno_t, allocno_t); extern void print_expanded_allocno (allocno_t); extern allocno_live_range_t create_allocno_live_range (allocno_t, int, int, @@ -605,6 +621,7 @@ extern void ira_destroy (void); /* ira-costs.c */ extern void init_ira_costs_once (void); +extern void init_ira_costs (void); extern void finish_ira_costs_once (void); extern void ira_costs (void); extern void tune_allocno_costs_and_cover_classes (void); @@ -635,3 +652,67 @@ extern void ira_color (void); /* ira-emit.c */ extern void ira_emit (int); + + + +/* The function returns nonzero if hard registers starting with + HARD_REGNO and containing value of MODE are not in set + HARD_REGSET. */ +static inline int +hard_reg_not_in_set_p (int hard_regno, enum machine_mode mode, + HARD_REG_SET hard_regset) +{ + int i; + + ira_assert (hard_regno >= 0); + for (i = hard_regno_nregs [hard_regno] [mode] - 1; i >= 0; i--) + if (TEST_HARD_REG_BIT (hard_regset, hard_regno + i)) + return FALSE; + return TRUE; +} + + + +/* Allocate cost vector *VEC and initialize the elements by VAL if it + is necessary */ +static inline void +allocate_and_set_costs (int **vec, int len, int val) +{ + int i, *reg_costs; + + if (*vec != NULL) + return; + *vec = reg_costs = ira_allocate (sizeof (int) * len); + for (i = 0; i < len; i++) + reg_costs [i] = val; +} + +/* Allocate cost vector *VEC and copy values of SRC into the vector if + it is necessary */ +static inline void +allocate_and_copy_costs (int **vec, int len, int *src) +{ + if (*vec != NULL || src == NULL) + return; + *vec = ira_allocate (sizeof (int) * len); + memcpy (*vec, src, sizeof (int) * len); +} + +/* Allocate cost vector *VEC and copy values of SRC into the vector or + initialize it by VAL (if SRC is null). */ +static inline void +allocate_and_set_or_copy_costs (int **vec, int len, int val, int *src) +{ + int i, *reg_costs; + + if (*vec != NULL) + return; + *vec = reg_costs = ira_allocate (sizeof (int) * len); + if (src != NULL) + memcpy (reg_costs, src, sizeof (int) * len); + else + { + for (i = 0; i < len; i++) + reg_costs [i] = val; + } +} diff --git a/gcc/ira-lives.c b/gcc/ira-lives.c index 7199af5a6fa..3cbb7b36592 100644 --- a/gcc/ira-lives.c +++ b/gcc/ira-lives.c @@ -49,7 +49,7 @@ static void mark_reg_conflicts (rtx); static void mark_reg_death (rtx); static enum reg_class single_reg_class (const char *, rtx op, rtx); static enum reg_class single_reg_operand_class (int); -static void process_single_reg_class_operands (int); +static void process_single_reg_class_operands (int, int); static void process_bb_node_lives (loop_tree_node_t); /* Program points are enumerated by number from range @@ -483,11 +483,12 @@ single_reg_operand_class (int op_num) recog_data.operand [op_num], NULL_RTX); } -/* The function processes input (if IN_P) or output operands to find - allocno which can use only one hard register and makes other - currently living reg allocnos conflicting with the hard register. */ +/* The function processes input (if IN_P) or output operands of insn + with FREQ to find allocno which can use only one hard register and + makes other currently living reg allocnos conflicting with the hard + register. */ static void -process_single_reg_class_operands (int in_p) +process_single_reg_class_operands (int in_p, int freq) { int i, regno, px, cost; enum reg_class cl, cover_class; @@ -525,9 +526,13 @@ process_single_reg_class_operands (int in_p) && (reg_class_size [cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))) { - cost = (in_p - ? register_move_cost [mode] [cover_class] [cl] - : register_move_cost [mode] [cl] [cover_class]); + /* ??? FREQ */ + cost = freq * (in_p + ? register_move_cost [mode] [cover_class] [cl] + : register_move_cost [mode] [cl] [cover_class]); + allocate_and_set_costs + (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), + class_hard_regs_num [cover_class], 0); ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a) [class_hard_reg_index [cover_class] [class_hard_regs [cl] [0]]] -= cost; @@ -651,10 +656,15 @@ process_bb_node_lives (loop_tree_node_t loop_tree_node) FOR_BB_INSNS (bb, insn) { rtx link; + int freq; if (! INSN_P (insn)) continue; + freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)); + if (freq == 0) + freq = 1; + if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) fprintf (ira_dump_file, " Insn %u(l%d): point = %d\n", INSN_UID (insn), loop_tree_node->father->loop->num, @@ -668,7 +678,7 @@ process_bb_node_lives (loop_tree_node_t loop_tree_node) note_stores (PATTERN (insn), mark_reg_clobber, NULL); extract_insn (insn); - process_single_reg_class_operands (TRUE); + process_single_reg_class_operands (TRUE, freq); /* Mark any allocnos dead after INSN as dead now. */ for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) @@ -684,12 +694,8 @@ process_bb_node_lives (loop_tree_node_t loop_tree_node) IOR_HARD_REG_SET (cfun->emit->call_used_regs, clobbered_regs); EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, i, { - int freq; allocno_t a = allocnos [i]; - freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)); - if (freq == 0) - freq = 1; ALLOCNO_CALL_FREQ (a) += freq; index = add_regno_call (ALLOCNO_REGNO (a), insn); if (ALLOCNO_CALLS_CROSSED_START (a) < 0) @@ -750,7 +756,7 @@ process_bb_node_lives (loop_tree_node_t loop_tree_node) mark_reg_conflicts (reg); } - process_single_reg_class_operands (FALSE); + process_single_reg_class_operands (FALSE, freq); /* Mark any allocnos set in INSN and then never used. */ while (! VEC_empty (rtx, regs_set)) diff --git a/gcc/ira.c b/gcc/ira.c index a2522699d20..323de04648d 100644 --- a/gcc/ira.c +++ b/gcc/ira.c @@ -95,15 +95,15 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA static void setup_inner_mode (void); static void setup_reg_mode_hard_regset (void); -static void setup_class_subset_and_move_costs (void); -static void setup_reg_class_intersect (void); static void setup_class_hard_regs (void); static void setup_available_class_regs (void); static void setup_alloc_regs (int); +static void setup_class_subset_and_memory_move_costs (void); static void setup_reg_subclasses (void); #ifdef IRA_COVER_CLASSES static void setup_cover_classes (void); static void setup_class_translate (void); +static void setup_reg_class_intersect_union (void); #endif static void print_class_cover (FILE *); static void find_reg_class_closure (void); @@ -167,15 +167,26 @@ HARD_REG_SET reg_mode_hard_regset [FIRST_PSEUDO_REGISTER] [NUM_MACHINE_MODES]; /* The following two variables are array analog of macros MEMORY_MOVE_COST and REGISTER_MOVE_COST. */ -int memory_move_cost [MAX_MACHINE_MODE] [N_REG_CLASSES] [2]; -int register_move_cost [MAX_MACHINE_MODE] [N_REG_CLASSES] [N_REG_CLASSES]; +short int memory_move_cost [MAX_MACHINE_MODE] [N_REG_CLASSES] [2]; +move_table *register_move_cost [MAX_MACHINE_MODE]; + +/* Similar to move_cost, but here we don't have to move if the first + index is a subset of the second (taking registers available for + allocation into account) so in that case the cost is zero. */ +move_table *register_may_move_in_cost [MAX_MACHINE_MODE]; + +/* Similar, but here we don't have to move if the first index is a + superset of the second (taking registers available for allocation + into account) so in that case the cost is zero. */ +move_table *register_may_move_out_cost [MAX_MACHINE_MODE]; /* Nonzero value of element of the following array means that the 1st class is a subset of the 2nd class. */ int class_subset_p [N_REG_CLASSES] [N_REG_CLASSES]; -/* The biggest class inside of intersection of the two classes. */ -enum reg_class reg_class_subintersect [N_REG_CLASSES] [N_REG_CLASSES]; +/* Nonzero value of element of the following array means that the + 1st class is a strict subset of the 2nd class. */ +int strict_class_subset_p [N_REG_CLASSES] [N_REG_CLASSES]; /* Temporary hard reg set used for different calculation. */ static HARD_REG_SET temp_hard_regset; @@ -223,62 +234,6 @@ setup_reg_mode_hard_regset (void) -/* The function sets up MEMORY_MOVE_COST, REGISTER_MOVE_COST and - CLASS_SUBSET_P. */ -static void -setup_class_subset_and_move_costs (void) -{ - int cl, cl2; - enum machine_mode mode; - - for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) - { - for (mode = 0; mode < MAX_MACHINE_MODE; mode++) - { - memory_move_cost [mode] [cl] [0] = MEMORY_MOVE_COST (mode, cl, 0); - memory_move_cost [mode] [cl] [1] = MEMORY_MOVE_COST (mode, cl, 1); - } - - for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--) - { - if (cl != NO_REGS && cl2 != NO_REGS) - for (mode = 0; mode < MAX_MACHINE_MODE; mode++) - register_move_cost [mode] [cl] [cl2] - = REGISTER_MOVE_COST (mode, cl, cl2); - class_subset_p [cl] [cl2] - = hard_reg_set_subset_p (reg_class_contents[cl], - reg_class_contents[cl2]); - } - } -} - -/* The function sets up REG_CLASS_SUBINTERSECT. */ -static void -setup_reg_class_intersect (void) -{ - int cl1, cl2, cl3; - HARD_REG_SET temp_set; - - for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++) - { - for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++) - { - reg_class_subintersect [cl1] [cl2] = NO_REGS; - COPY_HARD_REG_SET (temp_set, reg_class_contents [cl1]); - AND_HARD_REG_SET (temp_set, reg_class_contents [cl2]); - for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++) - if (hard_reg_set_subset_p (reg_class_contents [cl3], temp_set) - && ! hard_reg_set_subset_p (reg_class_contents [cl3], - reg_class_contents - [(int) reg_class_subintersect - [cl1] [cl2]])) - reg_class_subintersect [cl1] [cl2] = (enum reg_class) cl3; - } - } -} - - - /* Hard registers can not be used for the register allocator for all functions of the current compile unit. */ static HARD_REG_SET no_unit_alloc_regs; @@ -370,6 +325,41 @@ setup_alloc_regs (int use_hard_frame_p) +/* The function sets up MEMORY_MOVE_COST, REGISTER_MOVE_COST and + CLASS_SUBSET_P and STRICT_CLASS_SUBSET_P. */ +static void +setup_class_subset_and_memory_move_costs (void) +{ + int cl, cl2; + enum machine_mode mode; + HARD_REG_SET temp_hard_regset2; + + for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) + { + for (mode = 0; mode < MAX_MACHINE_MODE; mode++) + { + memory_move_cost [mode] [cl] [0] = MEMORY_MOVE_COST (mode, cl, 0); + memory_move_cost [mode] [cl] [1] = MEMORY_MOVE_COST (mode, cl, 1); + } + + for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--) + { + COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [cl]); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); + COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents [cl2]); + AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs); + class_subset_p [cl] [cl2] + = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2); + strict_class_subset_p [cl] [cl2] = class_subset_p [cl] [cl2]; + if (class_subset_p [cl] [cl2] + && hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)) + strict_class_subset_p [cl] [cl2] = FALSE; + } + } +} + + + /* Define the following macro if allocation through malloc if preferable. */ #define IRA_NO_OBSTACK @@ -453,24 +443,6 @@ ira_free_regset (regset r ATTRIBUTE_UNUSED) -/* The function returns nonzero if hard registers starting with - HARD_REGNO and containing value of MODE are not in set - HARD_REGSET. */ -int -hard_reg_not_in_set_p (int hard_regno, enum machine_mode mode, - HARD_REG_SET hard_regset) -{ - int i; - - ira_assert (hard_regno >= 0); - for (i = hard_regno_nregs [hard_regno] [mode] - 1; i >= 0; i--) - if (TEST_HARD_REG_BIT (hard_regset, hard_regno + i)) - return FALSE; - return TRUE; -} - - - /* The function outputs information about allocation of all allocnos into file F. */ void @@ -514,8 +486,8 @@ debug_disposition (void) /* For each reg class, table listing all the classes contained in it - (excluding the class itself. Fixed registers are excluded from the - consideration). */ + (excluding the class itself. Non-allocatable registers are + excluded from the consideration). */ static enum reg_class alloc_reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES]; /* The function initializes the tables of subclasses of each reg @@ -524,6 +496,7 @@ static void setup_reg_subclasses (void) { int i, j; + HARD_REG_SET temp_hard_regset2; for (i = 0; i < N_REG_CLASSES; i++) for (j = 0; j < N_REG_CLASSES; j++) @@ -535,7 +508,7 @@ setup_reg_subclasses (void) continue; COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [i]); - AND_COMPL_HARD_REG_SET (temp_hard_regset, fixed_reg_set); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); if (hard_reg_set_equal_p (temp_hard_regset, zero_hard_reg_set)) continue; for (j = 0; j < N_REG_CLASSES; j++) @@ -543,8 +516,10 @@ setup_reg_subclasses (void) { enum reg_class *p; - if (! hard_reg_set_subset_p (reg_class_contents [i], - reg_class_contents [j])) + COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents [j]); + AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs); + if (! hard_reg_set_subset_p (temp_hard_regset, + temp_hard_regset2)) continue; p = &alloc_reg_class_subclasses [j] [0]; while (*p != LIM_REG_CLASSES) p++; @@ -572,7 +547,7 @@ enum reg_class important_classes [N_REG_CLASSES]; /* The array containing order numbers of important classes (they are subclasses of cover classes). */ -enum reg_class important_class_nums [N_REG_CLASSES]; +int important_class_nums [N_REG_CLASSES]; #ifdef IRA_COVER_CLASSES @@ -584,6 +559,7 @@ setup_cover_classes (void) int i, j; enum reg_class cl; static enum reg_class classes [] = IRA_COVER_CLASSES; + HARD_REG_SET temp_hard_regset2; reg_class_cover_size = 0; for (i = 0; (cl = classes [i]) != LIM_REG_CLASSES; i++) @@ -592,7 +568,7 @@ setup_cover_classes (void) if (reg_classes_intersect_p (cl, classes [j])) gcc_unreachable (); COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [cl]); - AND_COMPL_HARD_REG_SET (temp_hard_regset, fixed_reg_set); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); if (! hard_reg_set_equal_p (temp_hard_regset, zero_hard_reg_set)) reg_class_cover [reg_class_cover_size++] = cl; } @@ -600,15 +576,24 @@ setup_cover_classes (void) for (cl = 0; cl < N_REG_CLASSES; cl++) { COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [cl]); - AND_COMPL_HARD_REG_SET (temp_hard_regset, fixed_reg_set); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); if (! hard_reg_set_equal_p (temp_hard_regset, zero_hard_reg_set)) for (j = 0; j < reg_class_cover_size; j++) - if (hard_reg_set_subset_p (reg_class_contents [cl], - reg_class_contents [reg_class_cover [j]])) - { - important_class_nums [cl] = important_classes_num; - important_classes [important_classes_num++] = cl; - } + { + COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [cl]); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); + COPY_HARD_REG_SET (temp_hard_regset2, + reg_class_contents [reg_class_cover [j]]); + AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs); + if (cl == reg_class_cover [j] + || (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2) + && ! hard_reg_set_equal_p (temp_hard_regset, + temp_hard_regset2))) + { + important_class_nums [cl] = important_classes_num; + important_classes [important_classes_num++] = cl; + } + } } } #endif @@ -643,7 +628,7 @@ setup_class_translate (void) else { COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [cl]); - AND_COMPL_HARD_REG_SET (temp_hard_regset, fixed_reg_set); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); if (! hard_reg_set_subset_p (temp_hard_regset, zero_hard_reg_set)) gcc_unreachable (); @@ -667,6 +652,7 @@ setup_class_translate (void) COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [cover_class]); AND_HARD_REG_SET (temp_hard_regset, reg_class_contents [cl]); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); if (! hard_reg_set_equal_p (temp_hard_regset, zero_hard_reg_set)) { min_cost = INT_MAX; @@ -689,6 +675,64 @@ setup_class_translate (void) } #endif +/* The biggest important class inside of intersection of the two classes. */ +enum reg_class reg_class_intersect [N_REG_CLASSES] [N_REG_CLASSES]; +/* The biggest important class inside of union of the two classes. */ +enum reg_class reg_class_union [N_REG_CLASSES] [N_REG_CLASSES]; + +#ifdef IRA_COVER_CLASSES + +/* The function sets up REG_CLASS_INTERSECT and REG_CLASS_UNION. */ +static void +setup_reg_class_intersect_union (void) +{ + int i, cl1, cl2, cl3; + HARD_REG_SET intersection_set, union_set, temp_set2; + + for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++) + { + for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++) + { + reg_class_intersect [cl1] [cl2] = NO_REGS; + reg_class_union [cl1] [cl2] = NO_REGS; + COPY_HARD_REG_SET (intersection_set, reg_class_contents [cl1]); + AND_HARD_REG_SET (intersection_set, reg_class_contents [cl2]); + AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs); + COPY_HARD_REG_SET (union_set, reg_class_contents [cl1]); + IOR_HARD_REG_SET (union_set, reg_class_contents [cl2]); + AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs); + for (i = 0; i < important_classes_num; i++) + { + cl3 = important_classes [i]; + COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents [cl3]); + AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); + if (hard_reg_set_subset_p (temp_hard_regset, intersection_set)) + { + COPY_HARD_REG_SET + (temp_set2, + reg_class_contents + [(int) reg_class_intersect [cl1] [cl2]]); + AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs); + if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)) + reg_class_intersect [cl1] [cl2] = (enum reg_class) cl3; + } + if (hard_reg_set_subset_p (temp_hard_regset, union_set)) + { + COPY_HARD_REG_SET + (temp_set2, + reg_class_contents + [(int) reg_class_union [cl1] [cl2]]); + AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs); + if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)) + reg_class_union [cl1] [cl2] = (enum reg_class) cl3; + } + } + } + } +} + +#endif + /* The function outputs all cover classes and the translation map into file F. */ static void @@ -723,6 +767,7 @@ find_reg_class_closure (void) #ifdef IRA_COVER_CLASSES setup_cover_classes (); setup_class_translate (); + setup_reg_class_intersect_union (); #endif } @@ -785,6 +830,44 @@ setup_prohibited_class_mode_regs (void) +/* The function allocates and initializes REGISTER_MOVE_COST, + REGISTER_MAY_MOVE_IN_COST, and REGISTER_MAY_MOVE_OUT_COST for MODE + if it is not done yet. */ +void +init_register_move_cost (enum machine_mode mode) +{ + int cl1, cl2; + + ira_assert (register_move_cost [mode] == NULL + && register_may_move_in_cost [mode] == NULL + && register_may_move_out_cost [mode] == NULL); + if (move_cost [mode] == NULL) + init_move_cost (mode); + register_move_cost [mode] = move_cost [mode]; + /* Don't use ira_allocate becuase the tables exist out of scope of a + IRA call. */ + register_may_move_in_cost [mode] + = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES); + memcpy (register_may_move_in_cost [mode], may_move_in_cost [mode], + sizeof (move_table) * N_REG_CLASSES); + register_may_move_out_cost [mode] + = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES); + memcpy (register_may_move_out_cost [mode], may_move_out_cost [mode], + sizeof (move_table) * N_REG_CLASSES); + for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++) + { + for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++) + { + if (class_subset_p [cl1] [cl2]) + register_may_move_in_cost [mode] [cl1] [cl2] = 0; + if (class_subset_p [cl2] [cl1]) + register_may_move_out_cost [mode] [cl1] [cl2] = 0; + } + } +} + + + /* Hard regsets whose all bits are correspondingly zero or one. */ HARD_REG_SET zero_hard_reg_set; HARD_REG_SET one_hard_reg_set; @@ -794,17 +877,52 @@ HARD_REG_SET one_hard_reg_set; void init_ira_once (void) { + enum machine_mode mode; + CLEAR_HARD_REG_SET (zero_hard_reg_set); SET_HARD_REG_SET (one_hard_reg_set); + for (mode = 0; mode < MAX_MACHINE_MODE; mode++) + { + register_move_cost [mode] = NULL; + register_may_move_in_cost [mode] = NULL; + register_may_move_out_cost [mode] = NULL; + } setup_inner_mode (); + init_ira_costs_once (); +} + +/* The function frees register_move_cost, register_may_move_in_cost, + and register_may_move_out_cost for each mode. */ +static void +free_register_move_costs (void) +{ + enum machine_mode mode; + + for (mode = 0; mode < MAX_MACHINE_MODE; mode++) + { + if (register_may_move_in_cost [mode] != NULL) + free (register_may_move_in_cost [mode]); + if (register_may_move_out_cost [mode] != NULL) + free (register_may_move_out_cost [mode]); + register_move_cost [mode] = NULL; + register_may_move_in_cost [mode] = NULL; + register_may_move_out_cost [mode] = NULL; + } +} + +/* The function called every time when register related information is + changed. */ +void +init_ira (void) +{ + free_register_move_costs (); setup_reg_mode_hard_regset (); - setup_class_subset_and_move_costs (); - setup_reg_class_intersect (); setup_alloc_regs (flag_omit_frame_pointer != 0); + setup_class_subset_and_memory_move_costs (); find_reg_class_closure (); setup_reg_class_nregs (); setup_prohibited_class_mode_regs (); - init_ira_costs_once (); + init_ira_costs (); } /* Function called once at the end of compiler work. */ @@ -812,6 +930,7 @@ void finish_ira_once (void) { finish_ira_costs_once (); + free_register_move_costs (); } @@ -1138,13 +1257,18 @@ calculate_allocation_cost (void) cost = ALLOCNO_UPDATED_MEMORY_COST (a); mem_cost += cost; } - else + else if (ALLOCNO_HARD_REG_COSTS (a) != NULL) { cost = (ALLOCNO_HARD_REG_COSTS (a) [class_hard_reg_index [ALLOCNO_COVER_CLASS (a)] [hard_regno]]); reg_cost += cost; } + else + { + cost = ALLOCNO_COVER_CLASS_COST (a); + reg_cost += cost; + } overall_cost += cost; } @@ -1316,6 +1440,81 @@ expand_reg_info (int old_size) +/* Map bb index -> order number in the BB chain. */ +static int *basic_block_order_nums; + +/* The function is used to sort insn chain according insn execution + frequencies. */ +static int +chain_freq_compare (const void *v1p, const void *v2p) +{ + struct insn_chain *c1 = *(struct insn_chain **)v1p; + struct insn_chain *c2 = *(struct insn_chain **)v2p; + int diff; + + diff = (BASIC_BLOCK (c2->block)->frequency + - BASIC_BLOCK (c1->block)->frequency); + if (diff) + return diff; + return (char *) v1p - (char *) v2p; +} + +/* The function is used to sort insn chain according insn original + order. */ +static int +chain_bb_compare (const void *v1p, const void *v2p) +{ + struct insn_chain *c1 = *(struct insn_chain **)v1p; + struct insn_chain *c2 = *(struct insn_chain **)v2p; + int diff; + + diff = (basic_block_order_nums [c1->block] + - basic_block_order_nums [c2->block]); + if (diff) + return diff; + return (char *) v1p - (char *) v2p; +} + +/* The function sorts insn chain according insn frequencies (if + FREQ_P) or insn original order. */ +void +sort_insn_chain (int freq_p) +{ + struct insn_chain *chain, **chain_arr; + basic_block bb; + int i, n; + + for (n = 0, chain = reload_insn_chain; chain != 0; chain = chain->next) + n++; + if (n <= 1) + return; + chain_arr = ira_allocate (n * sizeof (struct insn_chain *)); + basic_block_order_nums = ira_allocate (sizeof (int) * last_basic_block); + n = 0; + FOR_EACH_BB (bb) + { + basic_block_order_nums [bb->index] = n++; + } + for (n = 0, chain = reload_insn_chain; chain != 0; chain = chain->next) + chain_arr [n++] = chain; + qsort (chain_arr, n, sizeof (struct insn_chain *), + freq_p ? chain_freq_compare : chain_bb_compare); + for (i = 1; i < n - 1; i++) + { + chain_arr [i]->next = chain_arr [i + 1]; + chain_arr [i]->prev = chain_arr [i - 1]; + } + chain_arr [i]->next = NULL; + chain_arr [i]->prev = chain_arr [i - 1]; + reload_insn_chain = chain_arr [0]; + reload_insn_chain->prev = NULL; + reload_insn_chain->next = chain_arr [1]; + ira_free (basic_block_order_nums); + ira_free (chain_arr); +} + + + /* This is the main entry of IRA. */ void @@ -1466,6 +1665,7 @@ ira (FILE *f) df_set_flags (DF_NO_INSN_RESCAN); build_insn_chain (get_insns ()); + sort_insn_chain (TRUE); reload_completed = ! reload (get_insns (), 1); ira_free (spilled_reg_stack_slots); diff --git a/gcc/ira.h b/gcc/ira.h index 394a590210d..8c8c0102356 100644 --- a/gcc/ira.h +++ b/gcc/ira.h @@ -54,12 +54,16 @@ extern rtx *reg_equiv_address; extern rtx *reg_equiv_mem; extern void init_ira_once (void); +extern void init_ira (void); extern void finish_ira_once (void); extern rtx ira_eliminate_regs (rtx, enum machine_mode); +extern void sort_insn_chain (int); extern void ira (FILE *); extern void mark_allocation_change (int); -extern void retry_ira_color (int, HARD_REG_SET); +extern void mark_memory_move_deletion (int, int); +extern int reassign_pseudos (int *, int, HARD_REG_SET, HARD_REG_SET *, + HARD_REG_SET *, bitmap); extern rtx reuse_stack_slot (int, unsigned int, unsigned int); extern void mark_new_stack_slot (rtx, int, unsigned int); extern void collect_pseudo_call_clobbered_regs (int, HARD_REG_SET *); diff --git a/gcc/reload1.c b/gcc/reload1.c index f63879c5055..61edbfa17d2 100644 --- a/gcc/reload1.c +++ b/gcc/reload1.c @@ -552,7 +552,7 @@ compute_use_by_pseudos (HARD_REG_SET *to, regset from) DF_RA_LIVE_IN (BASIC_BLOCK), which might still contain registers that have not actually been allocated since they have an equivalence. */ - gcc_assert (reload_completed); + gcc_assert (flag_ira || reload_completed); } else add_to_hard_reg_set (to, PSEUDO_REGNO_MODE (regno), r); @@ -686,6 +686,9 @@ static int something_needs_operands_changed; /* Nonzero means we couldn't get enough spill regs. */ static int failure; +/* Temporary array of pseudo-register number. */ +static int *temp_pseudo_reg_arr; + /* The function is used to sort pseudos according their usage frequencies (putting most frequently ones first). */ static int @@ -716,7 +719,7 @@ pseudo_reg_compare (const void *v1p, const void *v2p) int reload (rtx first, int global) { - int i; + int i, n; rtx insn; struct elim_table *ep; basic_block bb; @@ -897,27 +900,22 @@ reload (rtx first, int global) offsets_known_at = XNEWVEC (char, num_labels); offsets_at = (HOST_WIDE_INT (*)[NUM_ELIMINABLE_REGS]) xmalloc (num_labels * NUM_ELIMINABLE_REGS * sizeof (HOST_WIDE_INT)); - { - int n, *pseudo_regs; - - /* Alter each pseudo-reg rtx to contain its hard reg number. - Assign stack slots to the pseudos that lack hard regs or - equivalents. Do not touch virtual registers. */ - - pseudo_regs = XNEWVEC (int, max_regno - LAST_VIRTUAL_REGISTER - 1); - for (n = 0, i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++) - pseudo_regs [n++] = i; - - if (flag_ira) - qsort (pseudo_regs, n, sizeof (int), pseudo_reg_compare); - if (frame_pointer_needed || ! flag_ira) - for (i = 0; i < n; i++) - alter_reg (pseudo_regs [i], -1, false); - else - for (i = n - 1; i >= 0; i--) - alter_reg (pseudo_regs [i], -1, false); - free (pseudo_regs); - } + /* Alter each pseudo-reg rtx to contain its hard reg number. Assign + stack slots to the pseudos that lack hard regs or equivalents. + Do not touch virtual registers. */ + + temp_pseudo_reg_arr = XNEWVEC (int, max_regno - LAST_VIRTUAL_REGISTER - 1); + for (n = 0, i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++) + temp_pseudo_reg_arr [n++] = i; + + if (flag_ira) + qsort (temp_pseudo_reg_arr, n, sizeof (int), pseudo_reg_compare); + if (frame_pointer_needed || ! flag_ira) + for (i = 0; i < n; i++) + alter_reg (temp_pseudo_reg_arr [i], -1, false); + else + for (i = n - 1; i >= 0; i--) + alter_reg (temp_pseudo_reg_arr [i], -1, false); /* If we have some registers we think can be eliminated, scan all insns to see if there is an insn that sets one of these registers to something @@ -1065,7 +1063,8 @@ reload (rtx first, int global) calculate_needs_all_insns (global); - CLEAR_REG_SET (&spilled_pseudos); + if (! flag_ira) + CLEAR_REG_SET (&spilled_pseudos); did_spill = 0; something_changed = 0; @@ -1123,6 +1122,9 @@ reload (rtx first, int global) obstack_free (&reload_obstack, reload_firstobj); } + if (flag_ira) + sort_insn_chain (FALSE); + /* If global-alloc was run, notify it of any register eliminations we have done. */ if (global) @@ -1375,6 +1377,8 @@ reload (rtx first, int global) VEC_free (rtx, gc, reg_equiv_memory_loc_vec); reg_equiv_memory_loc = 0; + free (temp_pseudo_reg_arr); + if (offsets_known_at) free (offsets_known_at); if (offsets_at) @@ -1630,6 +1634,9 @@ calculate_needs_all_insns (int global) reg_equiv_memory_loc [REGNO (SET_DEST (set))])))) { + if (flag_ira) + mark_memory_move_deletion (REGNO (SET_DEST (set)), + REGNO (SET_SRC (set))); delete_insn (insn); /* Delete it from the reload chain. */ if (chain->prev) @@ -1728,7 +1735,8 @@ count_pseudo (int reg) int nregs; if (REGNO_REG_SET_P (&pseudos_counted, reg) - || REGNO_REG_SET_P (&spilled_pseudos, reg)) + || REGNO_REG_SET_P (&spilled_pseudos, reg) + || (flag_ira && r < 0)) return; SET_REGNO_REG_SET (&pseudos_counted, reg); @@ -1803,7 +1811,8 @@ count_spilled_pseudo (int spilled, int spilled_nregs, int reg) int r = reg_renumber[reg]; int nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (reg)]; - if (REGNO_REG_SET_P (&spilled_pseudos, reg) + if ((flag_ira && r < 0) + || REGNO_REG_SET_P (&spilled_pseudos, reg) || spilled + spilled_nregs <= r || r + nregs <= spilled) return; @@ -2115,7 +2124,8 @@ alter_reg (int i, int from_reg, bool dont_share_p) int adjust = 0; bool shared_p = false; - + if (flag_ira) + SET_REGNO_REG_SET (&spilled_pseudos, i); x = (dont_share_p || ! flag_ira ? NULL_RTX : reuse_stack_slot (i, inherent_size, total_size)); if (x) @@ -3890,20 +3900,21 @@ finish_spills (int global) spill_reg_order[i] = -1; EXECUTE_IF_SET_IN_REG_SET (&spilled_pseudos, FIRST_PSEUDO_REGISTER, i, rsi) - { - /* Record the current hard register the pseudo is allocated to in - pseudo_previous_regs so we avoid reallocating it to the same - hard reg in a later pass. */ - gcc_assert (reg_renumber[i] >= 0); - - SET_HARD_REG_BIT (pseudo_previous_regs[i], reg_renumber[i]); - /* Mark it as no longer having a hard register home. */ - reg_renumber[i] = -1; - if (flag_ira) - mark_allocation_change (i); - /* We will need to scan everything again. */ - something_changed = 1; - } + if (! flag_ira || reg_renumber[i] >= 0) + { + /* Record the current hard register the pseudo is allocated to + in pseudo_previous_regs so we avoid reallocating it to the + same hard reg in a later pass. */ + gcc_assert (reg_renumber[i] >= 0); + + SET_HARD_REG_BIT (pseudo_previous_regs[i], reg_renumber[i]); + /* Mark it as no longer having a hard register home. */ + reg_renumber[i] = -1; + if (flag_ira) + mark_allocation_change (i); + /* We will need to scan everything again. */ + something_changed = 1; + } /* Retry global register allocation if possible. */ if (global) @@ -3933,32 +3944,40 @@ finish_spills (int global) and call retry_global_alloc. We change spill_pseudos here to only contain pseudos that did not get a new hard register. */ - for (i = FIRST_PSEUDO_REGISTER; i < (unsigned)max_regno; i++) - if (reg_old_renumber[i] != reg_renumber[i]) - { - HARD_REG_SET forbidden; + if (! flag_ira) + { + for (i = FIRST_PSEUDO_REGISTER; i < (unsigned)max_regno; i++) + if (reg_old_renumber[i] != reg_renumber[i]) + { + HARD_REG_SET forbidden; + + COPY_HARD_REG_SET (forbidden, bad_spill_regs_global); + IOR_HARD_REG_SET (forbidden, pseudo_forbidden_regs[i]); + IOR_HARD_REG_SET (forbidden, pseudo_previous_regs[i]); + retry_global_alloc (i, forbidden); + if (reg_renumber[i] >= 0) + CLEAR_REGNO_REG_SET (&spilled_pseudos, i); + } + } + else + { + unsigned int n; - COPY_HARD_REG_SET (forbidden, bad_spill_regs_global); - IOR_HARD_REG_SET (forbidden, pseudo_forbidden_regs[i]); - IOR_HARD_REG_SET (forbidden, pseudo_previous_regs[i]); - if (flag_ira) + for (n = 0, i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++) + if (reg_old_renumber[i] != reg_renumber[i]) { - /* We might migrate pseudo to another hard register on - previous iteration. So check this. */ if (reg_renumber [i] < 0) - { - retry_ira_color (i, forbidden); - if (reg_renumber[i] >= 0) - something_changed = 1; - } + temp_pseudo_reg_arr [n++] = i; + else + CLEAR_REGNO_REG_SET (&spilled_pseudos, i); } - else - retry_global_alloc (i, forbidden); - if (reg_renumber[i] >= 0) - CLEAR_REGNO_REG_SET (&spilled_pseudos, i); - } + if (reassign_pseudos (temp_pseudo_reg_arr, n, bad_spill_regs_global, + pseudo_forbidden_regs, pseudo_previous_regs, + &spilled_pseudos)) + something_changed = 1; + + } } - /* Fix up the register information in the insn chain. This involves deleting those of the spilled pseudos which did not get a new hard register home from the live_{before,after} sets. */ @@ -3967,9 +3986,11 @@ finish_spills (int global) HARD_REG_SET used_by_pseudos; HARD_REG_SET used_by_pseudos2; - AND_COMPL_REG_SET (&chain->live_throughout, &spilled_pseudos); - AND_COMPL_REG_SET (&chain->dead_or_set, &spilled_pseudos); - + if (! flag_ira) + { + AND_COMPL_REG_SET (&chain->live_throughout, &spilled_pseudos); + AND_COMPL_REG_SET (&chain->dead_or_set, &spilled_pseudos); + } /* Mark any unallocated hard regs as available for spills. That makes inheritance work somewhat better. */ if (chain->need_reload) diff --git a/gcc/toplev.c b/gcc/toplev.c index c81a384391b..f8e22f9b790 100644 --- a/gcc/toplev.c +++ b/gcc/toplev.c @@ -2032,6 +2032,9 @@ backend_init_target (void) mode-dependent. */ init_regs (); + /* This invokes IRA to set up reg related data structures. */ + init_ira (); + /* This depends on stack_pointer_rtx. */ init_fake_stack_mems (); @@ -2075,8 +2078,8 @@ backend_init (void) init_varasm_once (); /* Initialize the target-specific back end pieces. */ - backend_init_target (); init_ira_once (); + backend_init_target (); } /* Initialize things that are both lang-dependent and target-dependent. -- 2.11.4.GIT