#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "tree.h"#include "gimple.h"#include "cfghooks.h"#include "tree-pass.h"#include "ssa.h"#include "fold-const.h"#include "cfganal.h"#include "gimple-iterator.h"#include "tree-ssa.h"#include "tree-ssa-threadupdate.h"#include "cfgloop.h"#include "dbgcnt.h"#include "tree-cfg.h"#include "tree-vectorizer.h"
Data Structures | |
| struct | el |
| struct | redirection_data |
| struct | ssa_local_info_t |
Macros | |
| #define | INCLUDE_MEMORY |
| #define | THREAD_PATH(E) |
Variables | |
| static basic_block | dbds_ce_stop |
Macro Definition Documentation
◆ INCLUDE_MEMORY
| #define INCLUDE_MEMORY |
Thread edges through blocks and update the control flow and SSA graphs. Copyright (C) 2004-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/>.
◆ THREAD_PATH
| #define THREAD_PATH | ( | E | ) |
When we start updating the CFG for threading, data necessary for jump threading is attached to the AUX field for the incoming edge. Use these macros to access the underlying structure attached to the AUX field.
Referenced by compute_path_counts(), fwd_jt_path_registry::lookup_redirection_data(), fwd_jt_path_registry::mark_threaded_blocks(), ssa_fix_duplicate_block_edges(), ssa_redirect_edges(), fwd_jt_path_registry::thread_block_1(), and fwd_jt_path_registry::thread_through_loop_header().
Function Documentation
◆ any_remaining_duplicated_blocks()
|
static |
Look through PATH beginning at START and return TRUE if there are any additional blocks that need to be duplicated. Otherwise, return FALSE.
References EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, and i.
Referenced by ssa_fix_duplicate_block_edges().
◆ bb_in_bbs()
|
inlinestatic |
Return true when BB is one of the first N items in BBS.
References i.
Referenced by back_jt_path_registry::duplicate_thread_path().
◆ cancel_thread()
|
static |
Release the memory associated with PATH, and if dumping is enabled, dump out the reason why the thread was canceled.
References dump_file, dump_flags, dump_jump_thread_path(), and TDF_DETAILS.
Referenced by back_jt_path_registry::adjust_paths_after_duplication(), jt_path_registry::cancel_invalid_paths(), fwd_jt_path_registry::mark_threaded_blocks(), fwd_jt_path_registry::thread_block_1(), fwd_jt_path_registry::thread_through_loop_header(), back_jt_path_registry::update_cfg(), and fwd_jt_path_registry::update_cfg().
◆ compute_path_counts()
|
static |
Compute the amount of profile count coming into the jump threading
path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
duplicated path, returned in PATH_OUT_COUNT_PTR. LOCAL_INFO is used to
identify blocks duplicated for jump threading, which have duplicated
edges that need to be ignored in the analysis. Return true if path contains
a joiner, false otherwise.
In the non-joiner case, this is straightforward - all the counts
flowing into the jump threading path should flow through the duplicated
block and out of the duplicated path.
In the joiner case, it is very tricky. Some of the counts flowing into
the original path go offpath at the joiner. The problem is that while
we know how much total count goes off-path in the original control flow,
we don't know how many of the counts corresponding to just the jump
threading path go offpath at the joiner.
For example, assume we have the following control flow and identified
jump threading paths:
A B C
\ | /
Ea \ |Eb / Ec
\ | /
v v v
J <-- Joiner
/ \
Eoff/ \Eon
/ \
v v
Soff Son <--- Normal
/\
Ed/ \ Ee
/ \
v v
D E
Jump threading paths: A -> J -> Son -> D (path 1)
C -> J -> Son -> E (path 2)
Note that the control flow could be more complicated:
- Each jump threading path may have more than one incoming edge. I.e. A and
Ea could represent multiple incoming blocks/edges that are included in
path 1.
- There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
before or after the "normal" copy block). These are not duplicated onto
the jump threading path, as they are single-successor.
- Any of the blocks along the path may have other incoming edges that
are not part of any jump threading path, but add profile counts along
the path.
In the above example, after all jump threading is complete, we will
end up with the following control flow:
A B C
| | |
Ea| |Eb |Ec
| | |
v v v
Ja J Jc
/ \ / \Eon' / \
Eona/ \ ---/---\-------- \Eonc
/ \ / / \ \
v v v v v
Sona Soff Son Sonc
\ /\ /
\___________ / \ _____/
\ / \/
vv v
D E
The main issue to notice here is that when we are processing path 1
(A->J->Son->D) we need to figure out the outgoing edge weights to
the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
sum of the incoming weights to D remain Ed. The problem with simply
assuming that Ja (and Jc when processing path 2) has the same outgoing
probabilities to its successors as the original block J, is that after
all paths are processed and other edges/counts removed (e.g. none
of Ec will reach D after processing path 2), we may end up with not
enough count flowing along duplicated edge Sona->D.
Therefore, in the case of a joiner, we keep track of all counts
coming in along the current path, as well as from predecessors not
on any jump threading path (Eb in the above example). While we
first assume that the duplicated Eona for Ja->Sona has the same
probability as the original, we later compensate for other jump
threading paths that may eliminate edges. We do that by keep track
of all counts coming into the original path that are not in a jump
thread (Eb in the above example, but as noted earlier, there could
be other predecessors incoming to the path at various points, such
as at Son). Call this cumulative non-path count coming into the path
before D as Enonpath. We then ensure that the count from Sona->D is as at
least as big as (Ed - Enonpath), but no bigger than the minimum
weight along the jump threading path. The probabilities of both the
original and duplicated joiner block J and Ja will be adjusted
accordingly after the updates.
References profile_count::apply_probability(), bitmap_bit_p, bitmap_set_bit, count, ssa_local_info_t::duplicate_blocks, el::e, EDGE_COPY_SRC_JOINER_BLOCK, FOR_EACH_EDGE, gcc_assert, i, redirection_data::incoming_edges, ssa_local_info_t::need_profile_correction, el::next, profile_count::probability_in(), THREAD_PATH, and profile_count::zero().
Referenced by ssa_fix_duplicate_block_edges().
◆ copy_phi_args()
|
static |
For each PHI in BB, copy the argument associated with SRC_E to TGT_E. Try to backtrack jump threading PATH from node IDX to see if the arg has constant value, copy constant value instead of argument itself if yes.
References add_phi_arg(), get_value_locus_in_path(), gimple_phi_arg_def(), gimple_phi_arg_location(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gphi_iterator::phi(), TREE_CODE, and virtual_operand_p().
Referenced by create_edge_and_update_destination_phis(), ssa_fix_duplicate_block_edges(), and update_destination_phis().
◆ count_stmts_and_phis_in_block()
|
static |
Return the number of non-debug statements and non-virtual PHIs in a block.
References gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), is_gimple_debug(), gphi_iterator::phi(), PHI_RESULT, and virtual_operand_p().
Referenced by fwd_jt_path_registry::mark_threaded_blocks().
◆ create_block_for_threading()
|
static |
Create a duplicate of BB. Record the duplicate block in an array indexed by COUNT stored in RD.
References bitmap_set_bit, basic_block_def::count, count, redirection_data::dup_blocks, duplicate_block(), FOR_EACH_EDGE, basic_block_def::index, NULL, basic_block_def::succs, and profile_count::uninitialized().
Referenced by ssa_create_duplicates().
◆ create_edge_and_update_destination_phis()
|
static |
Given a duplicate block and its single destination (both stored in RD). Create an edge between the duplicate and its single destination. Add an additional argument to any PHI nodes at the single destination. IDX is the start node in jump threading path we start to check to see if the new PHI argument has constant value along the jump threading path.
References copy_phi_args(), el::e, make_single_succ_edge(), NULL, redirection_data::path, and rescan_loop_exit().
Referenced by ssa_fix_duplicate_block_edges().
◆ dbds_continue_enumeration_p()
|
static |
References dbds_ce_stop.
Referenced by determine_bb_domination_status().
◆ debug() [1/2]
| DEBUG_FUNCTION void debug | ( | const vec< jump_thread_edge * > & | path | ) |
References dump_jump_thread_path().
◆ debug() [2/2]
| DEBUG_FUNCTION void debug | ( | const vec< jump_thread_edge * > * | path | ) |
References debug.
◆ determine_bb_domination_status()
| enum bb_dom_status determine_bb_domination_status | ( | class loop * | loop, |
| basic_block | bb ) |
Evaluates the dominance relationship of latch of the LOOP and BB, and returns the state.
References dbds_ce_stop, dbds_continue_enumeration_p(), dfs_enumerate_from(), DOMST_DOMINATING, DOMST_LOOP_BROKEN, DOMST_NONDOMINATING, el::e, FOR_EACH_EDGE, free(), loop::header, i, loop::latch, loop::num_nodes, and basic_block_def::preds.
Referenced by back_threader_profitability::profitable_path_p(), and fwd_jt_path_registry::thread_through_loop_header().
◆ dump_jump_thread_path()
|
static |
Dump a jump threading path, including annotations about each edge in the path.
References dbg_cnt_counter(), dump_file, el::e, EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, EDGE_NO_COPY_SRC_BLOCK, gcc_unreachable, i, and NULL.
Referenced by cancel_thread(), debug(), and jt_path_registry::register_jump_thread().
◆ estimate_threading_killed_stmts()
| unsigned int estimate_threading_killed_stmts | ( | basic_block | bb | ) |
Starting from the final control flow stmt in BB, assuming it will be removed, follow uses in to-be-removed stmts back to their defs and count how many defs are to become dead and be removed as well.
References dump_file, EDGE_COUNT, FOR_EACH_SSA_USE_OPERAND, gcc_assert, hash_map< KeyId, Value, Traits >::get(), hash_map< KeyId, Value, Traits >::get_or_insert(), gimple_bb(), gimple_has_side_effects(), gimple_phi_result(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, basic_block_def::preds, hash_map< KeyId, Value, Traits >::remove(), SSA_NAME_DEF_STMT, SSA_OP_USE, USE_FROM_PTR, uses_in_bb(), and virtual_operand_p().
Referenced by fwd_jt_path_registry::mark_threaded_blocks(), and jump_threader::record_temporary_equivalences_from_stmts_at_dest().
◆ get_value_locus_in_path()
|
static |
Given ssa_name DEF, backtrack jump threading PATH from node IDX to see if it has constant value in a flow sensitive manner. Set LOCUS to location of the constant phi arg and return the value. Return DEF directly if either PATH or idx is ZERO.
References bb_loop_depth(), dyn_cast(), el::e, gimple_bb(), gimple_phi_arg_def(), gimple_phi_arg_location(), is_gimple_min_invariant(), NULL, and SSA_NAME_DEF_STMT.
Referenced by copy_phi_args().
◆ phi_args_equal_on_edges()
E1 and E2 are edges into the same basic block. Return TRUE if the PHI arguments associated with those edges are equal or there are no PHI arguments, otherwise return FALSE.
References gimple_phi_arg_def(), gsi_end_p(), gsi_next(), gsi_start_phis(), operand_equal_p(), and gphi_iterator::phi().
Referenced by fwd_jt_path_registry::mark_threaded_blocks().
◆ redirection_block_p()
|
static |
Return true if this block has no executable statements other than a simple ctrl flow instruction. When the number of outgoing edges is one, this is equivalent to a "forwarder" block.
References gimple_clobber_p(), gimple_nop_p(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), and is_gimple_debug().
Referenced by fwd_jt_path_registry::mark_threaded_blocks(), and fwd_jt_path_registry::thread_through_loop_header().
◆ remove_ctrl_stmt_and_useless_edges()
|
static |
Remove the last statement in block BB if it is a control statement Also remove all outgoing edges except the edge which reaches DEST_BB. If DEST_BB is NULL, then remove all outgoing edges.
References profile_probability::always(), ei_next(), ei_safe_edge(), ei_start, free_dom_edge_info(), gsi_end_p(), gsi_last_bb(), gsi_remove(), gsi_stmt(), loop_exit_edge_p(), basic_block_def::loop_father, loop_outer(), LOOPS_NEED_FIXUP, loops_state_set(), remove_edge(), single_succ_edge(), single_succ_p(), and basic_block_def::succs.
Referenced by back_jt_path_registry::duplicate_thread_path(), and ssa_fix_duplicate_block_edges().
◆ ssa_create_duplicates()
| int ssa_create_duplicates | ( | struct redirection_data ** | slot, |
| ssa_local_info_t * | local_info ) |
Hash table traversal callback routine to create duplicate blocks.
References bb_seq(), create_block_for_threading(), redirection_data::dup_blocks, ssa_local_info_t::duplicate_blocks, EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, EDGE_NO_COPY_SRC_BLOCK, gcc_assert, gimple_copy(), gsi_after_labels(), gsi_bb(), gsi_end_p(), gsi_insert_before(), gsi_insert_seq_after(), gsi_last_bb(), gsi_next(), gsi_none(), GSI_SAME_STMT, gsi_split_seq_after(), gsi_start_bb(), gsi_stmt(), i, is_gimple_debug(), MAY_HAVE_DEBUG_STMTS, NULL, redirection_data::path, set_bb_seq(), ssa_fix_duplicate_block_edges(), stmt_ends_bb_p(), ssa_local_info_t::template_block, and ssa_local_info_t::template_last_to_copy.
Referenced by fwd_jt_path_registry::thread_block_1().
◆ ssa_fix_duplicate_block_edges()
| void ssa_fix_duplicate_block_edges | ( | struct redirection_data * | rd, |
| ssa_local_info_t * | local_info ) |
Wire up the outgoing edges from the duplicate blocks and update any PHIs as needed. Also update the profile counts on the original and duplicate blocks and edges.
References any_remaining_duplicated_blocks(), ssa_local_info_t::bb, compute_path_counts(), copy_phi_arg_into_existing_phi(), copy_phi_args(), count, create_edge_and_update_destination_phis(), redirection_data::dup_blocks, el::e, EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, EDGE_SUCC, find_edge(), gcc_assert, i, redirection_data::incoming_edges, el::next, NULL, redirect_edge_and_branch(), remove_ctrl_stmt_and_useless_edges(), single_succ_edge(), THREAD_PATH, update_destination_phis(), update_profile(), and profile_count::zero().
Referenced by ssa_create_duplicates(), and ssa_fixup_template_block().
◆ ssa_fixup_template_block()
|
inline |
We did not create any outgoing edges for the template block during block creation. This hash table traversal callback creates the outgoing edge for the template block.
References redirection_data::dup_blocks, ssa_fix_duplicate_block_edges(), and ssa_local_info_t::template_block.
Referenced by fwd_jt_path_registry::thread_block_1().
◆ ssa_redirect_edges()
|
static |
Hash table traversal callback to redirect each incoming edge associated with this hash table element to its new destination.
References dump_file, dump_flags, redirection_data::dup_blocks, el::e, flush_pending_stmts(), free(), gcc_assert, redirection_data::incoming_edges, basic_block_def::index, ssa_local_info_t::jumps_threaded, el::next, NULL, ssa_local_info_t::num_threaded_edges, redirect_edge_and_branch(), TDF_DETAILS, and THREAD_PATH.
Referenced by fwd_jt_path_registry::thread_block_1().
◆ update_destination_phis()
|
static |
We have recently made a copy of ORIG_BB, including its outgoing edges. The copy is NEW_BB. Every PHI node in every direct successor of ORIG_BB has a new argument associated with edge from NEW_BB to the successor. Initialize the PHI argument so that it is equal to the PHI argument associated with the edge from ORIG_BB to the successor. PATH and IDX are used to check if the new PHI argument has constant value in a flow sensitive manner.
References copy_phi_args(), el::e, find_edge(), FOR_EACH_EDGE, and basic_block_def::succs.
Referenced by ssa_fix_duplicate_block_edges().
◆ update_profile()
|
static |
Update the counts and frequencies for both an original path edge EPATH and its duplicate EDUP. The duplicate source block will get a count of PATH_IN_COUNT and PATH_IN_FREQ, and the duplicate edge EDUP will have a count of PATH_OUT_COUNT.
References profile_probability::always(), basic_block_def::count, FOR_EACH_EDGE, gcc_assert, profile_count::initialized_p(), profile_probability::initialized_p(), profile_count::probability_in(), basic_block_def::succs, and profile_count::zero().
Referenced by ssa_fix_duplicate_block_edges().
◆ uses_in_bb()
|
static |
Return how many uses of T there are within BB, as long as there aren't any uses outside BB. If there are any uses outside BB, return -1 if there's at most one use within BB, or -2 if there is more than one use within BB.
References FOR_EACH_IMM_USE_FAST, gimple_bb(), is_gimple_debug(), and USE_STMT.
Referenced by estimate_threading_killed_stmts().
◆ valid_jump_thread_path()
|
static |
Return true when PATH is a valid jump-thread path.
Referenced by back_jt_path_registry::update_cfg().
◆ verify_jump_thread()
| DEBUG_FUNCTION void verify_jump_thread | ( | basic_block * | region, |
| unsigned | n_region ) |
Verify that the REGION is a valid jump thread. A jump thread is a special case of SEME Single Entry Multiple Exits region in which all nodes in the REGION have exactly one incoming edge. The only exception is the first block that may not have been connected to the rest of the cfg yet.
References EDGE_COUNT, gcc_assert, and i.
Referenced by back_jt_path_registry::duplicate_thread_path().
Variable Documentation
◆ dbds_ce_stop
|
static |
Callback for dfs_enumerate_from. Returns true if BB is different from STOP and DBDS_CE_STOP.
Referenced by dbds_continue_enumeration_p(), and determine_bb_domination_status().
