#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "tree.h"#include "gimple.h"#include "ssa.h"#include "fold-const.h"#include "gimple-iterator.h"#include "tree-ssa.h"#include "gt-tree-phinodes.h"
Macros | |
| #define | NUM_BUCKETS 10 |
Functions | |
| static int | ideal_phi_node_len (int) |
| void | phinodes_print_statistics (void) |
| static gphi * | allocate_phi_node (size_t len) |
| static gphi * | make_phi_node (tree var, int len) |
| static void | release_phi_node (gimple *phi) |
| static gphi * | resize_phi_node (gphi *phi, size_t len) |
| void | reserve_phi_args_for_new_edge (basic_block bb) |
| static void | add_phi_node_to_bb (gphi *phi, basic_block bb) |
| gphi * | create_phi_node (tree var, basic_block bb) |
| void | add_phi_arg (gphi *phi, tree def, edge e, location_t locus) |
| static void | remove_phi_arg_num (gphi *phi, int i) |
| void | remove_phi_args (edge e) |
| void | remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p) |
| void | remove_phi_nodes (basic_block bb) |
| tree | degenerate_phi_result (gphi *phi) |
| void | set_phi_nodes (basic_block bb, gimple_seq seq) |
Variables | |
| static vec< gimple *, va_gc > * | free_phinodes [NUM_BUCKETS - 2] |
| static unsigned long | free_phinode_count |
| unsigned int | phi_nodes_reused |
| unsigned int | phi_nodes_created |
Macro Definition Documentation
◆ NUM_BUCKETS
| #define NUM_BUCKETS 10 |
Generic routines for manipulating PHIs Copyright (C) 2003-2024 Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see <http://www.gnu.org/licenses/>.
Rewriting a function into SSA form can create a huge number of PHIs many of which may be thrown away shortly after their creation if jumps were threaded through PHI nodes. While our garbage collection mechanisms will handle this situation, it is extremely wasteful to create nodes and throw them away, especially when the nodes can be reused. For PR 8361, we can significantly reduce the number of nodes allocated and thus the total amount of memory allocated by managing PHIs a little. This additionally helps reduce the amount of work done by the garbage collector. Similar results have been seen on a wider variety of tests (such as the compiler itself). PHI nodes have different sizes, so we can't have a single list of all the PHI nodes as it would be too expensive to walk down that list to find a PHI of a suitable size. Instead we have an array of lists of free PHI nodes. The array is indexed by the number of PHI alternatives that PHI node can hold. Except for the last array member, which holds all remaining PHI nodes. So to find a free PHI node, we compute its index into the free PHI node array and see if there are any elements with an exact match. If so, then we are done. Otherwise, we test the next larger size up and continue until we are in the last array element. We do not actually walk members of the last array element. While it might allow us to pick up a few reusable PHI nodes, it could potentially be very expensive if the program has released a bunch of large PHI nodes, but keeps asking for even larger PHI nodes. Experiments have shown that walking the elements of the last array entry would result in finding less than .1% additional reusable PHI nodes. Note that we can never have less than two PHI argument slots. Thus, the -2 on all the calculations below.
Referenced by allocate_phi_node(), and release_phi_node().
Function Documentation
◆ add_phi_arg()
Add a new argument to PHI node PHI. DEF is the incoming reaching definition and E is the edge through which DEF reaches PHI. The new argument is added at the end of the argument list. If PHI has reached its maximum capacity, add a few slots. In this case, PHI points to the reallocated phi node when we return.
References gcc_assert, gimple_bb(), gimple_phi_arg_set_location(), gimple_phi_capacity(), gimple_phi_num_args(), PHI_RESULT, SET_PHI_ARG_DEF, and SSA_NAME_OCCURS_IN_ABNORMAL_PHI.
Referenced by add_exit_phi(), add_phi_args_after_copy_edge(), add_successor_phi_arg(), branch_fixup(), cond_if_else_store_replacement_1(), cond_store_replacement(), connect_loop_phis(), convert_if_conditions_to_switch(), copy_phi_args(), copy_phis_for_bb(), create_iv(), create_parallel_loop(), create_phi_basis_1(), create_phi_for_local_result(), create_tailcall_accumulator(), edge_before_returns_twice_call(), eliminate_tail_call(), emit_phi_nodes(), execute_sm_if_changed(), tree_switch_conversion::switch_conversion::exp_index_transform(), expand_complex_multiplication(), expand_omp_for_generic(), expand_omp_for_static_chunk(), expand_omp_for_static_nochunk(), expand_parallel_call(), factor_out_conditional_operation(), tree_switch_conversion::switch_conversion::fix_phi_nodes(), tree_switch_conversion::switch_decision_tree::fix_phi_operands_for_edges(), flush_pending_stmts(), fuse_loops(), tree_switch_conversion::switch_conversion::gen_inbound_check(), gimple_ic(), gimple_lower_bitint(), gimple_lv_adjust_loop_header_phi(), gimple_make_forwarder_block(), gimple_stringop_fixed_value(), hoist_guard(), initialize_root_vars(), initialize_root_vars_lm(), initialize_root_vars_store_elim_2(), input_phi(), rt_bb_visited::insert_exit_check_on_edge(), insert_into_preds_of_block(), insert_phi_nodes_for(), make_forwarders_with_degenerate_phis(), maybe_set_vectorized_backedge_value(), oacc_entry_exit_single_gang(), optimize_mask_stores(), phiprop_insert_phi(), remove_forwarder_block_with_phi(), replace_block_by(), rewrite_add_phi_arguments(), sese_add_exit_phis_edge(), shrink_wrap_one_built_in_call_with_conds(), simd_clone_adjust(), sink_common_stores_to_bb(), slpeel_tree_duplicate_loop_to_edge_cfg(), slpeel_update_phi_nodes_for_guard1(), split_function(), split_loop_exit_edge(), transform_to_exit_first_loop(), transform_to_exit_first_loop_alt(), tree_optimize_tail_calls_1(), tree_transform_and_unroll_loop(), vect_create_epilog_for_reduction(), vect_do_peeling(), vect_get_main_loop_result(), vect_loop_versioning(), vect_schedule_scc(), vect_set_loop_condition_normal(), vect_set_loop_control(), vect_setup_realignment(), vect_transform_cycle_phi(), vectorizable_induction(), vectorizable_lc_phi(), vectorizable_load(), vectorizable_nonlinear_induction(), vectorizable_phi(), vectorizable_recurr(), vectorizable_simd_clone_call(), worker_single_copy(), and worker_single_simple().
◆ add_phi_node_to_bb()
|
static |
Adds PHI to BB.
References gcc_assert, gimple_seq_add_stmt(), gimple_seq_alloc_with_stmt(), gimple_set_bb(), NULL, phi_nodes(), and set_phi_nodes().
Referenced by create_phi_node().
◆ allocate_phi_node()
|
inlinestatic |
Allocate a PHI node with at least LEN arguments. If the free list happens to contain a PHI node with LEN arguments or more, return that one.
References as_a(), free_phinode_count, free_phinodes, ggc_internal_alloc(), gimple_alloc_counts, gimple_alloc_sizes, gimple_phi_capacity(), is_empty(), NUM_BUCKETS, phi_nodes_created, phi_nodes_reused, and vec_free().
Referenced by make_phi_node(), and resize_phi_node().
◆ create_phi_node()
| gphi * create_phi_node | ( | tree | var, |
| basic_block | bb ) |
Create a new PHI node for variable VAR at basic block BB.
References add_phi_node_to_bb(), EDGE_COUNT, make_phi_node(), and basic_block_def::preds.
Referenced by add_exit_phi(), branch_fixup(), cond_if_else_store_replacement_1(), cond_store_replacement(), connect_loop_phis(), copy_phis_for_bb(), create_iv(), create_phi_basis_1(), create_phi_for_local_result(), create_tailcall_accumulator(), edge_before_returns_twice_call(), emit_phi_nodes(), expand_complex_multiplication(), expand_omp_atomic_pipeline(), expand_omp_for_generic(), expand_omp_for_static_chunk(), expand_parallel_call(), factor_out_conditional_operation(), gimple_duplicate_bb(), gimple_ic(), gimple_lower_bitint(), gimple_make_forwarder_block(), gimple_stringop_fixed_value(), initialize_root_vars(), initialize_root_vars_lm(), initialize_root_vars_store_elim_2(), input_phi(), rt_bb_visited::insert_exit_check_on_edge(), insert_into_preds_of_block(), insert_phi_nodes_for(), make_forwarders_with_degenerate_phis(), oacc_entry_exit_single_gang(), optimize_mask_stores(), phiprop_insert_phi(), sese_add_exit_phis_edge(), shrink_wrap_one_built_in_call_with_conds(), simd_clone_adjust(), sink_common_stores_to_bb(), slpeel_tree_duplicate_loop_to_edge_cfg(), slpeel_update_phi_nodes_for_guard1(), split_loop_exit_edge(), transform_to_exit_first_loop(), transform_to_exit_first_loop_alt(), tree_optimize_tail_calls_1(), tree_transform_and_unroll_loop(), update_phi_components(), vect_create_epilog_for_reduction(), vect_do_peeling(), vect_get_main_loop_result(), vect_loop_versioning(), vect_set_loop_condition_normal(), vect_set_loop_control(), vect_setup_realignment(), vect_transform_cycle_phi(), vectorizable_induction(), vectorizable_lc_phi(), vectorizable_live_operation_1(), vectorizable_nonlinear_induction(), vectorizable_phi(), vectorizable_recurr(), vectorizable_simd_clone_call(), worker_single_copy(), and worker_single_simple().
◆ degenerate_phi_result()
Given PHI, return its RHS if the PHI is a degenerate, otherwise return NULL.
References gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), i, NULL, operand_equal_p(), and TREE_CODE.
Referenced by follow_copies_to_constant(), insert_debug_temp_for_var_def(), predicate_scalar_phi(), and ipa_param_body_adjustments::prepare_debug_expressions().
◆ ideal_phi_node_len()
|
static |
Given LEN, the original number of requested PHI arguments, return a new, "ideal" length for the PHI node. The "ideal" length rounds the total size of the PHI node up to the next power of two bytes. Rounding up will not result in wasting any memory since the size request will be rounded up by the GC system anyway. [ Note this is not entirely true since the original length might have fit on one of the special GC pages. ] By rounding up, we may avoid the need to reallocate the PHI node later if we increase the number of arguments for the PHI.
References ceil_log2().
Referenced by make_phi_node(), and reserve_phi_args_for_new_edge().
◆ make_phi_node()
Return a PHI node with LEN argument slots for variable VAR.
References allocate_phi_node(), gphi::capacity, gimple::code, gimple_init_singleton(), gimple_phi_arg_def_ptr(), gimple_phi_arg_imm_use_ptr(), gimple_phi_arg_set_location(), gimple_phi_set_result(), i, ideal_phi_node_len(), ssa_use_operand_t::loc, make_ssa_name(), gphi::nargs, ssa_use_operand_t::next, NULL, ssa_use_operand_t::prev, ssa_use_operand_t::stmt, TREE_CODE, UNKNOWN_LOCATION, and ssa_use_operand_t::use.
Referenced by create_phi_node().
◆ phinodes_print_statistics()
| void phinodes_print_statistics | ( | void | ) |
Dump some simple statistics regarding the re-use of PHI nodes.
References phi_nodes_created, phi_nodes_reused, PRsa, and SIZE_AMOUNT.
Referenced by dump_tree_statistics().
◆ release_phi_node()
|
static |
We no longer need PHI, release it so that it may be reused.
References delink_imm_use(), free_phinode_count, free_phinodes, ggc_free(), gimple_phi_arg_imm_use_ptr(), gimple_phi_capacity(), gimple_phi_num_args(), NUM_BUCKETS, and vec_safe_push().
Referenced by remove_phi_node(), and reserve_phi_args_for_new_edge().
◆ remove_phi_arg_num()
|
static |
Remove the Ith argument from PHI's argument list. This routine implements removal by swapping the last alternative with the alternative we want to delete and then shrinking the vector, which is consistent with how we remove an edge from the edge vector.
References delink_imm_use(), gcc_assert, gimple_phi_arg_imm_use_ptr(), gimple_phi_arg_location(), gimple_phi_arg_set_location(), gimple_phi_num_args(), i, gphi::nargs, relink_imm_use(), and ssa_use_operand_t::use.
Referenced by remove_phi_args().
◆ remove_phi_args()
| void remove_phi_args | ( | edge | e | ) |
Remove all PHI arguments associated with edge E.
References gsi_end_p(), gsi_next(), gsi_start_phis(), gphi_iterator::phi(), and remove_phi_arg_num().
Referenced by gimple_execute_on_shrinking_pred().
◆ remove_phi_node()
| void remove_phi_node | ( | gimple_stmt_iterator * | gsi, |
| bool | release_lhs_p ) |
Remove the PHI node pointed-to by iterator GSI from basic block BB. After removal, iterator GSI is updated to point to the next PHI node in the sequence. If RELEASE_LHS_P is true, the LHS of this PHI node is released into the free pool of SSA names.
References gimple_phi_result(), gsi_remove(), gsi_stmt(), insert_debug_temps_for_defs(), release_phi_node(), and release_ssa_name().
Referenced by eliminate_dom_walker::before_dom_children(), clean_up_loop_closed_phi(), combine_blocks(), create_loads_for_reductions(), eliminate_dom_walker::eliminate_cleanup(), eliminate_useless_phis(), expand_omp_for_static_chunk(), final_value_replacement_loop(), generate_loops_for_partition(), gimple_merge_blocks(), ifcombine_replace_cond(), tree_loop_interchange::map_inductions_to_loop(), move_block_to_fn(), move_computations_worker(), move_early_exit_stmts(), crc_optimization::optimize_crc_loop(), predicate_all_scalar_phis(), record_equivalences_from_phis(), release_defs_bitset(), remove_dead_phis(), remove_gimple_phi_args(), remove_phi_nodes(), pcom_worker::remove_stmt(), replace_ref_with(), rewrite_phi_with_iv(), rewrite_use_nonlinear_expr(), shrink_wrap_one_built_in_call_with_conds(), simple_dce_from_worklist(), slpeel_tree_duplicate_loop_to_edge_cfg(), spaceship_replacement(), split_function(), transform_to_exit_first_loop(), unsplit_eh(), and vectorizable_live_operation().
◆ remove_phi_nodes()
| void remove_phi_nodes | ( | basic_block | bb | ) |
Remove all the phi nodes from BB.
References gsi_end_p(), gsi_start_phis(), NULL, remove_phi_node(), and set_phi_nodes().
Referenced by remove_phi_nodes_and_edges_for_unreachable_block().
◆ reserve_phi_args_for_new_edge()
| void reserve_phi_args_for_new_edge | ( | basic_block | bb | ) |
Reserve PHI arguments for a new edge to basic block BB.
References EDGE_COUNT, gimple_phi_arg_def_ptr(), gimple_phi_arg_imm_use_ptr(), gimple_phi_arg_set_location(), gimple_phi_capacity(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_set_stmt(), gsi_start_phis(), ideal_phi_node_len(), ssa_use_operand_t::loc, gphi::nargs, ssa_use_operand_t::next, NULL, NULL_TREE, gphi_iterator::phi(), basic_block_def::preds, ssa_use_operand_t::prev, release_phi_node(), resize_phi_node(), SET_PHI_ARG_DEF, SSA_NAME_DEF_STMT, ssa_use_operand_t::stmt, UNKNOWN_LOCATION, and ssa_use_operand_t::use.
Referenced by gimple_execute_on_growing_pred().
◆ resize_phi_node()
Resize an existing PHI node. The only way is up. Return the possibly relocated phi.
References allocate_phi_node(), gphi::capacity, gcc_assert, gimple_phi_arg_def_ptr(), gimple_phi_arg_imm_use_ptr(), gimple_phi_capacity(), gimple_phi_num_args(), i, relink_imm_use_stmt(), and ssa_use_operand_t::use.
Referenced by reserve_phi_args_for_new_edge().
◆ set_phi_nodes()
| void set_phi_nodes | ( | basic_block | bb, |
| gimple_seq | seq ) |
Set PHI nodes of a basic block BB to SEQ.
References basic_block_def::flags, gcc_checking_assert, basic_block_def::basic_block_il_dependent::gimple, gimple_set_bb(), gsi_end_p(), gsi_next(), gsi_start(), gsi_stmt(), i, basic_block_def::il, and gimple_bb_info::phi_nodes.
Referenced by add_phi_node_to_bb(), expand_phi_nodes(), gimple_split_edge(), and remove_phi_nodes().
Variable Documentation
◆ free_phinode_count
|
static |
Referenced by allocate_phi_node(), and release_phi_node().
◆ free_phinodes
|
static |
Referenced by allocate_phi_node(), and release_phi_node().
◆ phi_nodes_created
| unsigned int phi_nodes_created |
Referenced by allocate_phi_node(), and phinodes_print_statistics().
◆ phi_nodes_reused
| unsigned int phi_nodes_reused |
Referenced by allocate_phi_node(), and phinodes_print_statistics().
