GCC Middle and Back End API Reference
tree-ssa-threadupdate.c File Reference

Data Structures

struct  el
struct  redirection_data
struct  ssa_local_info_t
struct  thread_stats_d




static void remove_ctrl_stmt_and_useless_edges ()
static void create_block_for_threading ()
static struct redirection_datalookup_redirection_data ()
static void copy_phi_args ()
static void update_destination_phis ()
static void create_edge_and_update_destination_phis (struct redirection_data *rd, basic_block bb)
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)
int ssa_redirect_edges (struct redirection_data **slot, ssa_local_info_t *local_info)
static bool redirection_block_p ()
static bool thread_block_1 ()
static bool thread_block ()
static basic_block thread_single_edge ()
static bool dbds_continue_enumeration_p ()
static enum bb_dom_status determine_bb_domination_status ()
static bool def_split_header_continue_p ()
static bool thread_through_loop_header ()
static bool phi_args_equal_on_edges ()
static void mark_threaded_blocks ()
bool thread_through_all_blocks ()
static void dump_jump_thread_path ()
void register_jump_thread ()


static vec< vec
< jump_thread_edge * > * > 
struct thread_stats_d thread_stats
static hash_table
< redirection_data
static basic_block dbds_ce_stop

Enumeration Type Documentation

   Evaluates the dominance relationship of latch of the LOOP and BB, and
   returns the state.  
     BB does not dominate latch of the LOOP.  
     The LOOP is broken (there is no path from the header to its latch.  
     BB dominates the latch of the LOOP.  

Function Documentation

static void copy_phi_args ( )
   For each PHI in BB, copy the argument associated with SRC_E to TGT_E.  

References edge_def::count, basic_block_def::count, make_edge(), redirection_data::path, edge_def::probability, and rescan_loop_exit().

static void create_block_for_threading ( )
   Create a duplicate of BB.  Record the duplicate block in RD.  
     We can use the generic block duplication code and simply remove
     the stuff we do not need.  
     Zero out the profile, since the block is unreachable for now.  

References redirection_data::dup_block, redirection_data::incoming_edges, redirection_data::path, and path.

Referenced by ssa_fix_duplicate_block_edges().

static void create_edge_and_update_destination_phis ( struct redirection_data rd,
basic_block  bb 
   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
     We have to copy path -- which means creating a new vector as well
     as all the jump_thread_edge entries.  
         Sadly, the elements of the vector are pointers and need to
         be copied as well.  
     If there are any PHI nodes at the destination of the outgoing edge
     from the duplicate block, then we will need to add a new argument
     to them.  The argument should have the same value as the argument
     associated with the outgoing edge stored in RD.  
static bool dbds_continue_enumeration_p ( )

Referenced by thread_single_edge().

static bool def_split_header_continue_p ( )
   Return true if BB is part of the new pre-header that is created
   when threading the latch to DATA.  

References edge_def::dest, and EDGE_COPY_SRC_JOINER_BLOCK.

static enum bb_dom_status determine_bb_domination_status ( )
     This function assumes BB is a successor of LOOP->header.
     If that is not the case return DOMST_NONDOMINATING which
     is always safe.  
     Check that BB dominates LOOP->latch, and that it is back-reachable
     from it.  
static void dump_jump_thread_path ( )
   Dump a jump threading path, including annotations about each
   edge in the path.  
         We can get paths with a NULL edge when the final destination
         of a jump thread turns out to be a constant address.  We dump
         those paths when debugging, so we have to be prepared for that
         possibility here.  
static struct redirection_data* lookup_redirection_data ( )
   Given an outgoing edge E lookup and return its entry in our hash table.

   If INSERT is true, then we insert the entry into the hash table if
   it is not already present.  INCOMING_EDGE is added to the list of incoming
   edges associated with E in the hash table.  
    Build a hash table element so we can see if E is already
     in the table.  
     This will only happen if INSERT is false and the entry is not
     in the hash table.  
     This will only happen if E was not in the hash table and
     INSERT is true.  
     E was in the hash table.  
         Free ELT as we do not need it anymore, we will extract the
         relevant entry from the hash table itself.  
         Get the entry stored in the hash table.  
         If insertion was requested, then we need to add INCOMING_EDGE
         to the list of incoming edges associated with E.  

References el::e, redirection_data::incoming_edges, and el::next.

static void mark_threaded_blocks ( )
   Walk through the registered jump threads and convert them into a
   form convenient for this pass.

   Any block which has incoming edges threaded to outgoing edges
   will have its entry in THREADED_BLOCK set.

   Any threaded edge will have its new outgoing edge stored in the
   original edge's AUX field.

   This form avoids the need to walk all the edges in the CFG to
   discover blocks which need processing and avoids unnecessary
   hash table lookups to map from threaded edge to new target.  
     Move the jump threading requests from PATHS to each edge
     which starts a jump thread path.  
     If we have a joiner block (J) which has two successors S1 and S2 and
     we are threading though S1 and the final destination of the thread
     is S2, then we must verify that any PHI nodes in S2 have the same
     PHI arguments for the edge J->S2 and J->S1->...->S2.

     We used to detect this prior to registering the jump thread, but
     that prohibits propagation of edge equivalences into non-dominated
     PHI nodes as the equivalency test might occur before propagation.

     This works for now, but will need improvement as part of the FSA

     Note since we've moved the thread request data to the edges,
     we have to iterate on those rather than the threaded_edges vector.  
     If optimizing for size, only thread through block if we don't have
     to duplicate it or it's an otherwise empty redirection block.  
     Look for jump threading paths which cross multiple loop headers.

     The code to thread through loop headers will change the CFG in ways
     that break assumptions made by the loop optimization code.

     We don't want to blindly cancel the requests.  We can instead do better
     by trimming off the end of the jump thread path.  
                 Basically we're looking for a situation where we can see
                 3 or more loop structures on a jump threading path.  
                     See if this is a loop father we have not seen before.  
                         We've already seen two loop fathers, so we
                         need to trim this jump threading path.  
                             Trim from entry I onwards.  
                             Now that we've truncated the path, make sure
                             what's left is still valid.   We need at least
                             two edges on the path and the last edge can not
                             be a joiner.  This should never happen, but let's
                             be safe.  

References edge_def::aux, and EDGE_COPY_SRC_JOINER_BLOCK.

static bool 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.  
static bool redirection_block_p ( )
   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.  
     Advance to the first executable statement.  
     Check if this is an empty block.  
     Test that we've reached the terminating control statement.  

References EDGE_COPY_SRC_BLOCK, EDGE_COPY_SRC_JOINER_BLOCK, loop::header, loop::latch, loop_exit_edge_p(), loop_latch_edge(), LOOPS_NEED_FIXUP, and loops_state_set().

void register_jump_thread ( )
   Register a jump threading opportunity.  We queue up all the jump
   threading opportunities discovered by a pass and update the CFG
   and SSA form all at once.

   E is the edge we can thread, E2 is the new target edge, i.e., we
   are effectively recording that E->dest can be changed to E2->dest
   after fixing the SSA graph.  
     First make sure there are no NULL outgoing edges on the jump threading
     path.  That can happen for jumping to a constant address.  
static void remove_ctrl_stmt_and_useless_edges ( )
   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.  
     If the duplicate ends with a control statement, then remove it.

     Note that if we are duplicating the template block rather than the
     original basic block, then the duplicate might not have any real
     statements in it.  

References edge_def::dest, ei_next(), and remove_edge().

int ssa_create_duplicates ( struct redirection_data **  slot,
ssa_local_info_t local_info 
   Hash table traversal callback routine to create duplicate blocks.  
     Create a template block if we have not done so already.  Otherwise
     use the template to create a new block.  
         We do not create any outgoing edges for the template.  We will
         take care of that in a later traversal.  That way we do not
         create edges that are going to just be deleted.  
         Go ahead and wire up outgoing edges and update PHIs for the duplicate
     Keep walking the hash table.  

References 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 block and
   update any PHIs as needed.  
     If we were threading through an joiner block, then we want
     to keep its control statement and redirect an outgoing edge.
     Else we want to remove the control statement & edges, then create
     a new outgoing edge.  In both cases we may need to update PHIs.  
         This updates the PHIs at the destination of the duplicate
         Find the edge from the duplicate block to the block we're
         threading through.  That's the edge we want to redirect.  
         If we redirected the edge, then we need to copy PHI arguments
         at the target.  If the edge already existed (e2 != victim case),
         then the PHIs in the target already have the correct arguments.  

References ssa_local_info_t::bb, create_block_for_threading(), redirection_data::dup_block, and ssa_local_info_t::template_block.

Referenced by ssa_create_duplicates().

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.  
     If this is the template block halt the traversal after updating
     it appropriately.

     If we were threading through an joiner block, then we want
     to keep its control statement and redirect an outgoing edge.
     Else we want to remove the control statement & edges, then create
     a new outgoing edge.  In both cases we may need to update PHIs.  
int ssa_redirect_edges ( struct redirection_data **  slot,
ssa_local_info_t local_info 
   Hash table traversal callback to redirect each incoming edge
   associated with this hash table element to its new destination.  
     Walk over all the incoming edges associated associated with this
     hash table entry.  
         Go ahead and free this element from the list.  Doing this now
         avoids the need for another list walk when we destroy the hash
             Excessive jump threading may make frequencies large enough so
             the computation overflows.  
             In the case of threading through a joiner block, the outgoing
             edges from the duplicate block were updated when they were
             redirected during ssa_fix_duplicate_block_edges.  
             Redirect the incoming edge (possibly to the joiner block) to the
             appropriate duplicate block.  
         Go ahead and clear E->aux.  It's not needed anymore and failure
         to clear it will cause all kinds of unpleasant problems later.  
     Indicate that we actually threaded one or more jumps.  
static bool thread_block ( )
   Wrapper for thread_block_1 so that we can first handle jump
   thread paths which do not involve copying joiner blocks, then
   handle jump thread paths which have joiner blocks.

   By doing things this way we can be as aggressive as possible and
   not worry that copying a joiner block will create a jump threading
static bool thread_block_1 ( )
   BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
   is reached via one or more specific incoming edges, we know which
   outgoing edge from BB will be traversed.

   We want to redirect those incoming edges to the target of the
   appropriate outgoing edge.  Doing so avoids a conditional branch
   and may expose new optimization opportunities.  Note that we have
   to update dominator tree and SSA graph after such changes.

   The key to keeping the SSA graph update manageable is to duplicate
   the side effects occurring in BB so that those side effects still
   occur on the paths which bypass BB after redirecting edges.

   We accomplish this by creating duplicates of BB and arranging for
   the duplicates to unconditionally pass control to one specific
   successor of BB.  We then revector the incoming edges into BB to
   the appropriate duplicate of BB.

   If NOLOOP_ONLY is true, we only perform the threading as long as it
   does not affect the structure of the loops in a nontrivial way. 

   If JOINERS is true, then thread through joiner blocks as well.  
     E is an incoming edge into BB that we may or may not want to
     redirect to a duplicate of BB.  
     To avoid scanning a linear array for the element we need we instead
     use a hash table.  For normal code there should be no noticeable
     difference.  However, if we have a block with a large number of
     incoming and outgoing edges such linear searches can get expensive.  
     If we thread the latch of the loop to its exit, the loop ceases to
     exist.  Make sure we do not restrict ourselves in order to preserve
     this loop.  
     Record each unique threaded destination into a hash table for
     efficient lookups.  
             If NOLOOP_ONLY is true, we only allow threading through the
             header of a loop to exit edges.

             There are two cases to consider.  The first when BB is the
             loop header.  We will attempt to thread this elsewhere, so
             we can just continue here.  
             The second occurs when there was loop header buried in a jump
             threading path.  We do not try and thread this elsewhere, so
             just cancel the jump threading request by clearing the AUX
             field now.  
                 Since this case is not handled by our special code
                 to thread through a loop header, we must explicitly
                 cancel the threading request here.  
         Insert the outgoing edge into the hash table if it is not
         already in the hash table.  
     We do not update dominance info.  
     We know we only thread through the loop header to loop exits.
     Let the basic block duplication hook know we are not creating
     a multiple entry loop.  
     Now create duplicates of BB.

     Note that for a block with a high outgoing degree we can waste
     a lot of time and memory creating and destroying useless edges.

     So we first duplicate BB and remove the control structure at the
     tail of the duplicate as well as all outgoing edges from the
     duplicate.  We then use that duplicate block as a template for
     the rest of the duplicates.  
     The template does not have an outgoing edge.  Create that outgoing
     edge and update PHI nodes as the edge's target as necessary.

     We do this after creating all the duplicates to avoid creating
     unnecessary edges.  
     The hash table traversals above created the duplicate blocks (and the
     statements within the duplicate blocks).  This loop creates PHI nodes for
     the duplicated blocks and redirects the incoming edges into BB to reach
     the duplicates of BB.  
     Done with this block.  Clear REDIRECTION_DATA.  
     Indicate to our caller whether or not any jumps were threaded.  

References edge_def::aux.

static basic_block thread_single_edge ( )
   Threads edge E through E->dest to the edge THREAD_TARGET (E).  Returns the
   copy of E->dest created during threading, or E->dest if it was not necessary
   to copy it (E is its single predecessor).  
         If BB has just a single predecessor, we should only remove the
         control statements at its end, and successors except for ETO.  
         And fixup the flags on the single remaining edge.  
     Otherwise, we need to create a copy.  

References dbds_continue_enumeration_p(), dfs_enumerate_from(), DOMST_DOMINATING, DOMST_LOOP_BROKEN, DOMST_NONDOMINATING, free(), loop::header, loop::latch, loop::num_nodes, basic_block_def::preds, and edge_def::src.

bool thread_through_all_blocks ( )
   Walk through all blocks and thread incoming edges to the appropriate
   outgoing edge for each edge pair recorded in THREADED_EDGES.

   It is the caller's responsibility to fix the dominance information
   and rewrite duplicated SSA_NAMEs back into SSA form.

   If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
   loop headers if it does not simplify the loop.

   Returns true if one or more edges were threaded, false otherwise.  
     We must know about loops in order to preserve them.  
     First perform the threading requests that do not affect
     loop structure.  
     Then perform the threading through loop headers.  We start with the
     innermost loop, so that the changes in cfg we perform won't affect
     further threading.  
     Assume we had a jump thread path which went from the latch to the exit
     and a path which goes from outside to inside the same loop.  

     If the latch to exit was handled first, we will thread it and clear

     The second path will be ignored by thread_block because we're going
     through a loop header.  It will also be ignored by the loop above
     because loop->header is NULL.

     This results in the second path never being threaded.  The failure
     mode is a dangling AUX field.

     This is inherently a bit of a pain to fix, so we just walk all the
     blocks and all the incoming edges to those blocks and clear their
     AUX fields.  
static bool thread_through_loop_header ( )
   Thread jumps through the header of LOOP.  Returns true if cfg changes.
   If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
   to the inside of the loop.  
     We have already threaded through headers to exits, so all the threading
     requests now are to the inside of the loop.  We need to avoid creating
     irreducible regions (i.e., loops with more than one entry block), and
     also loop with several latch edges, or new subloops of the loop (although
     there are cases where it might be appropriate, it is difficult to decide,
     and doing it wrongly may confuse other optimizers).

     We could handle more general cases here.  However, the intention is to
     preserve some information about the loop, which is impossible if its
     structure changes significantly, in a way that is not well understood.
     Thus we only handle few important special cases, in which also updating
     of the loop-carried information should be feasible:

     1) Propagation of latch edge to a block that dominates the latch block
        of a loop.  This aims to handle the following idiom:

        first = 1;
        while (1)
            if (first)
            first = 0;

        After threading the latch edge, this becomes

        first = 1;
        if (first)
        while (1)
            first = 0;

        The original header of the loop is moved out of it, and we may thread
        the remaining edges through it without further constraints.

     2) All entry edges are propagated to a single basic block that dominates
        the latch block of the loop.  This aims to handle the following idiom
        (normally created for "for" loops):

        i = 0;
        while (1)
            if (i >= 100)

        This becomes

        i = 0;
        while (1)
            if (i >= 100)
     Threading through the header won't improve the code if the header has just
     one successor.  
                 If latch is not threaded, and there is a header
                 edge that is not threaded, we would create loop
                 with multiple entries.  
             Two targets of threading would make us create loop
             with multiple entries.  
             There are no threading requests.  
         Redirecting to empty loop latch is useless.  
     The target block must dominate the loop latch, otherwise we would be
     creating a subloop.  
         If the loop ceased to exist, mark it as such, and thread through its
         original header.  
         If the target of the threading is a header of a subloop, we need
         to create a preheader for it, so that the headers of the two loops
         do not merge.  
         First handle the case latch edge is redirected.  We are copying
         the loop header but not creating a multiple entry loop.  Make the
         cfg manipulation code aware of that fact.  
         Remove the new pre-header blocks from our loop.  
         If the new header has multiple latches mark it so.  
         Cancel remaining threading requests that would make the
         loop a multiple entry loop.  
         Thread the remaining edges through the former header.  
         Now consider the case entry edges are redirected to the new entry
         block.  Remember one entry edge, so that we can find the new
         preheader (its destination after threading).  
         The duplicate of the header is the new preheader of the loop.  Ensure
         that it is placed correctly in the loop hierarchy.  
         Create the new latch block.  This is always necessary, as the latch
         must have only a single successor, but the original header had at
         least two successors.  
     We failed to thread anything.  Cancel the requests.  

References edge_def::aux, edge_def::dest, and EDGE_COPY_SRC_JOINER_BLOCK.

static void update_destination_phis ( )
   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.  

Variable Documentation

basic_block dbds_ce_stop
   Callback for dfs_enumerate_from.  Returns true if BB is different
   from STOP and DBDS_CE_STOP.  
vec<vec<jump_thread_edge *> *> paths
   Passes which use the jump threading code register jump threading
   opportunities as they are discovered.  We keep the registered
   jump threading opportunities in this vector as edge pairs
   (original_edge, target_edge).  
   Main data structure to hold information for duplicates of BB.  
struct thread_stats_d thread_stats