GCC Middle and Back End API Reference
tree-ssa-threadupdate.cc File Reference
#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"
Include dependency graph for tree-ssa-threadupdate.cc:

Data Structures

struct  el
struct  redirection_data
struct  ssa_local_info_t


#define THREAD_PATH(E)   ((vec<jump_thread_edge *> *)(E)->aux)


static void dump_jump_thread_path (FILE *dump_file, const vec< jump_thread_edge * > &path, bool registering)
DEBUG_FUNCTION void debug (const vec< jump_thread_edge * > &path)
DEBUG_FUNCTION void debug (const vec< jump_thread_edge * > *path)
static void cancel_thread (vec< jump_thread_edge * > *path, const char *reason=NULL)
static void remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
static void create_block_for_threading (basic_block bb, struct redirection_data *rd, unsigned int count, bitmap *duplicate_blocks)
static tree get_value_locus_in_path (tree def, vec< jump_thread_edge * > *path, basic_block bb, int idx, location_t *locus)
static void copy_phi_args (basic_block bb, edge src_e, edge tgt_e, vec< jump_thread_edge * > *path, int idx)
static void update_destination_phis (basic_block orig_bb, basic_block new_bb, vec< jump_thread_edge * > *path, int idx)
static void create_edge_and_update_destination_phis (struct redirection_data *rd, basic_block bb, int idx)
static bool any_remaining_duplicated_blocks (vec< jump_thread_edge * > *path, unsigned int start)
static bool compute_path_counts (struct redirection_data *rd, ssa_local_info_t *local_info, profile_count *path_in_count_ptr, profile_count *path_out_count_ptr)
static void update_profile (edge epath, edge edup, profile_count path_in_count, profile_count path_out_count)
void ssa_fix_duplicate_block_edges (struct redirection_data *rd, ssa_local_info_t *local_info)
int ssa_create_duplicates (struct redirection_data **slot, ssa_local_info_t *local_info)
int ssa_fixup_template_block (struct redirection_data **slot, ssa_local_info_t *local_info)
static int ssa_redirect_edges (struct redirection_data **slot, ssa_local_info_t *local_info)
static bool redirection_block_p (basic_block bb)
static bool dbds_continue_enumeration_p (const_basic_block bb, const void *stop)
enum bb_dom_status determine_bb_domination_status (class loop *loop, basic_block bb)
static bool phi_args_equal_on_edges (edge e1, edge e2)
static unsigned int count_stmts_and_phis_in_block (basic_block bb)
DEBUG_FUNCTION void verify_jump_thread (basic_block *region, unsigned n_region)
static bool bb_in_bbs (basic_block bb, basic_block *bbs, int n)
static bool valid_jump_thread_path (vec< jump_thread_edge * > *path)
static int uses_in_bb (tree t, basic_block bb)
unsigned int estimate_threading_killed_stmts (basic_block bb)


static basic_block dbds_ce_stop

Macro Definition Documentation


#define THREAD_PATH ( E)    ((vec<jump_thread_edge *> *)(E)->aux)
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 bool any_remaining_duplicated_blocks ( vec< jump_thread_edge * > * path,
unsigned int start )
Look through PATH beginning at START and return TRUE if there are
any additional blocks that need to be duplicated.  Otherwise,
return FALSE.   


Referenced by ssa_fix_duplicate_block_edges().

◆ bb_in_bbs()

static bool bb_in_bbs ( basic_block bb,
basic_block * bbs,
int n )
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 void cancel_thread ( vec< jump_thread_edge * > * path,
const char * reason = NULL )

◆ compute_path_counts()

static bool compute_path_counts ( struct redirection_data * rd,
ssa_local_info_t * local_info,
profile_count * path_in_count_ptr,
profile_count * path_out_count_ptr )
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 void copy_phi_args ( basic_block bb,
edge src_e,
edge tgt_e,
vec< jump_thread_edge * > * path,
int idx )
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 unsigned int count_stmts_and_phis_in_block ( basic_block bb)
Return the number of non-debug statements and non-virtual PHIs in a

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 void create_block_for_threading ( basic_block bb,
struct redirection_data * rd,
unsigned int count,
bitmap * duplicate_blocks )
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 void create_edge_and_update_destination_phis ( struct redirection_data * rd,
basic_block bb,
int idx )
Given a duplicate block and its single destination (both stored
in RD).  Create an edge between the duplicate and its single

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 bool dbds_continue_enumeration_p ( const_basic_block bb,
const void * stop )

References dbds_ce_stop.

Referenced by determine_bb_domination_status().

◆ debug() [1/2]

DEBUG_FUNCTION void debug ( const vec< jump_thread_edge * > & 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 )

◆ dump_jump_thread_path()

static void dump_jump_thread_path ( FILE * dump_file,
const vec< jump_thread_edge * > & path,
bool registering )
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()

◆ get_value_locus_in_path()

static tree get_value_locus_in_path ( tree def,
vec< jump_thread_edge * > * path,
basic_block bb,
int idx,
location_t * locus )
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()

static bool phi_args_equal_on_edges ( edge e1,
edge e2 )
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 bool redirection_block_p ( basic_block bb)
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 void remove_ctrl_stmt_and_useless_edges ( basic_block bb,
basic_block dest_bb )
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()

◆ ssa_fix_duplicate_block_edges()

◆ ssa_fixup_template_block()

int ssa_fixup_template_block ( struct redirection_data ** slot,
ssa_local_info_t * local_info )
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 int ssa_redirect_edges ( struct redirection_data ** slot,
ssa_local_info_t * local_info )

◆ update_destination_phis()

static void update_destination_phis ( basic_block orig_bb,
basic_block new_bb,
vec< jump_thread_edge * > * path,
int idx )
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 void update_profile ( edge epath,
edge edup,
profile_count path_in_count,
profile_count path_out_count )
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 int uses_in_bb ( tree t,
basic_block bb )
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 bool valid_jump_thread_path ( vec< jump_thread_edge * > * path)
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

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