diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-ssa-threadupdate.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/tree-ssa-threadupdate.c | 913 |
1 files changed, 0 insertions, 913 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-ssa-threadupdate.c b/gcc-4.2.1-5666.3/gcc/tree-ssa-threadupdate.c deleted file mode 100644 index 0697ae464..000000000 --- a/gcc-4.2.1-5666.3/gcc/tree-ssa-threadupdate.c +++ /dev/null @@ -1,913 +0,0 @@ -/* Thread edges through blocks and update the control flow and SSA graphs. - Copyright (C) 2004, 2005, 2006 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 2, 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 COPYING. If not, write to -the Free Software Foundation, 51 Franklin Street, Fifth Floor, -Boston, MA 02110-1301, USA. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "tm.h" -#include "tree.h" -#include "flags.h" -#include "rtl.h" -#include "tm_p.h" -#include "ggc.h" -#include "basic-block.h" -#include "output.h" -#include "expr.h" -#include "function.h" -#include "diagnostic.h" -#include "tree-flow.h" -#include "tree-dump.h" -#include "tree-pass.h" -#include "cfgloop.h" - -/* Given a block B, update the CFG and SSA graph to reflect redirecting - one or more in-edges to B to instead reach the destination of an - out-edge from B while preserving any side effects in B. - - i.e., given A->B and B->C, change A->B to be A->C yet still preserve the - side effects of executing B. - - 1. Make a copy of B (including its outgoing edges and statements). Call - the copy B'. Note B' has no incoming edges or PHIs at this time. - - 2. Remove the control statement at the end of B' and all outgoing edges - except B'->C. - - 3. Add a new argument to each PHI in C with the same value as the existing - argument associated with edge B->C. Associate the new PHI arguments - with the edge B'->C. - - 4. For each PHI in B, find or create a PHI in B' with an identical - PHI_RESULT. Add an argument to the PHI in B' which has the same - value as the PHI in B associated with the edge A->B. Associate - the new argument in the PHI in B' with the edge A->B. - - 5. Change the edge A->B to A->B'. - - 5a. This automatically deletes any PHI arguments associated with the - edge A->B in B. - - 5b. This automatically associates each new argument added in step 4 - with the edge A->B'. - - 6. Repeat for other incoming edges into B. - - 7. Put the duplicated resources in B and all the B' blocks into SSA form. - - Note that block duplication can be minimized by first collecting the - the set of unique destination blocks that the incoming edges should - be threaded to. Block duplication can be further minimized by using - B instead of creating B' for one destination if all edges into B are - going to be threaded to a successor of B. - - We further reduce the number of edges and statements we create by - not copying all the outgoing edges and the control statement in - step #1. We instead create a template block without the outgoing - edges and duplicate the template. */ - - -/* Steps #5 and #6 of the above algorithm are best implemented by walking - all the incoming edges which thread to the same destination edge at - the same time. That avoids lots of table lookups to get information - for the destination edge. - - To realize that implementation we create a list of incoming edges - which thread to the same outgoing edge. Thus to implement steps - #5 and #6 we traverse our hash table of outgoing edge information. - For each entry we walk the list of incoming edges which thread to - the current outgoing edge. */ - -struct el -{ - edge e; - struct el *next; -}; - -/* Main data structure recording information regarding B's duplicate - blocks. */ - -/* We need to efficiently record the unique thread destinations of this - block and specific information associated with those destinations. We - may have many incoming edges threaded to the same outgoing edge. This - can be naturally implemented with a hash table. */ - -struct redirection_data -{ - /* A duplicate of B with the trailing control statement removed and which - targets a single successor of B. */ - basic_block dup_block; - - /* An outgoing edge from B. DUP_BLOCK will have OUTGOING_EDGE->dest as - its single successor. */ - edge outgoing_edge; - - /* A list of incoming edges which we want to thread to - OUTGOING_EDGE->dest. */ - struct el *incoming_edges; - - /* Flag indicating whether or not we should create a duplicate block - for this thread destination. This is only true if we are threading - all incoming edges and thus are using BB itself as a duplicate block. */ - bool do_not_duplicate; -}; - -/* Main data structure to hold information for duplicates of BB. */ -static htab_t redirection_data; - -/* Data structure of information to pass to hash table traversal routines. */ -struct local_info -{ - /* The current block we are working on. */ - basic_block bb; - - /* A template copy of BB with no outgoing edges or control statement that - we use for creating copies. */ - basic_block template_block; - - /* TRUE if we thread one or more jumps, FALSE otherwise. */ - bool jumps_threaded; -}; - -/* 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). */ -DEF_VEC_ALLOC_P(edge,heap); -static VEC(edge,heap) *threaded_edges; - - -/* Jump threading statistics. */ - -struct thread_stats_d -{ - unsigned long num_threaded_edges; -}; - -struct thread_stats_d thread_stats; - - -/* 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. */ - -static void -remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb) -{ - block_stmt_iterator bsi; - edge e; - edge_iterator ei; - - bsi = bsi_last (bb); - - /* 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. */ - if (!bsi_end_p (bsi) - && bsi_stmt (bsi) - && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR - || TREE_CODE (bsi_stmt (bsi)) == GOTO_EXPR - || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR)) - bsi_remove (&bsi, true); - - for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) - { - if (e->dest != dest_bb) - remove_edge (e); - else - ei_next (&ei); - } -} - -/* Create a duplicate of BB which only reaches the destination of the edge - stored in RD. Record the duplicate block in RD. */ - -static void -create_block_for_threading (basic_block bb, struct redirection_data *rd) -{ - /* We can use the generic block duplication code and simply remove - the stuff we do not need. */ - rd->dup_block = duplicate_block (bb, NULL, NULL); - - /* Zero out the profile, since the block is unreachable for now. */ - rd->dup_block->frequency = 0; - rd->dup_block->count = 0; - - /* The call to duplicate_block will copy everything, including the - useless COND_EXPR or SWITCH_EXPR at the end of BB. We just remove - the useless COND_EXPR or SWITCH_EXPR here rather than having a - specialized block copier. We also remove all outgoing edges - from the duplicate block. The appropriate edge will be created - later. */ - remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL); -} - -/* Hashing and equality routines for our hash table. */ -static hashval_t -redirection_data_hash (const void *p) -{ - edge e = ((struct redirection_data *)p)->outgoing_edge; - return e->dest->index; -} - -static int -redirection_data_eq (const void *p1, const void *p2) -{ - edge e1 = ((struct redirection_data *)p1)->outgoing_edge; - edge e2 = ((struct redirection_data *)p2)->outgoing_edge; - - return e1 == e2; -} - -/* 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. */ - -static struct redirection_data * -lookup_redirection_data (edge e, edge incoming_edge, enum insert_option insert) -{ - void **slot; - struct redirection_data *elt; - - /* Build a hash table element so we can see if E is already - in the table. */ - elt = XNEW (struct redirection_data); - elt->outgoing_edge = e; - elt->dup_block = NULL; - elt->do_not_duplicate = false; - elt->incoming_edges = NULL; - - slot = htab_find_slot (redirection_data, elt, insert); - - /* This will only happen if INSERT is false and the entry is not - in the hash table. */ - if (slot == NULL) - { - free (elt); - return NULL; - } - - /* This will only happen if E was not in the hash table and - INSERT is true. */ - if (*slot == NULL) - { - *slot = (void *)elt; - elt->incoming_edges = XNEW (struct el); - elt->incoming_edges->e = incoming_edge; - elt->incoming_edges->next = NULL; - return elt; - } - /* E was in the hash table. */ - else - { - /* Free ELT as we do not need it anymore, we will extract the - relevant entry from the hash table itself. */ - free (elt); - - /* Get the entry stored in the hash table. */ - elt = (struct redirection_data *) *slot; - - /* If insertion was requested, then we need to add INCOMING_EDGE - to the list of incoming edges associated with E. */ - if (insert) - { - struct el *el = XNEW (struct el); - el->next = elt->incoming_edges; - el->e = incoming_edge; - elt->incoming_edges = el; - } - - return elt; - } -} - -/* 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. */ - -static void -create_edge_and_update_destination_phis (struct redirection_data *rd) -{ - edge e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU); - tree phi; - - e->probability = REG_BR_PROB_BASE; - e->count = rd->dup_block->count; - - /* 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. */ - for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) - { - int indx = rd->outgoing_edge->dest_idx; - add_phi_arg (phi, PHI_ARG_DEF (phi, indx), e); - } -} - -/* Hash table traversal callback routine to create duplicate blocks. */ - -static int -create_duplicates (void **slot, void *data) -{ - struct redirection_data *rd = (struct redirection_data *) *slot; - struct local_info *local_info = (struct local_info *)data; - - /* If this entry should not have a duplicate created, then there's - nothing to do. */ - if (rd->do_not_duplicate) - return 1; - - /* Create a template block if we have not done so already. Otherwise - use the template to create a new block. */ - if (local_info->template_block == NULL) - { - create_block_for_threading (local_info->bb, rd); - local_info->template_block = rd->dup_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. */ - } - else - { - create_block_for_threading (local_info->template_block, rd); - - /* Go ahead and wire up outgoing edges and update PHIs for the duplicate - block. */ - create_edge_and_update_destination_phis (rd); - } - - /* Keep walking the hash table. */ - return 1; -} - -/* 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. */ - -static int -fixup_template_block (void **slot, void *data) -{ - struct redirection_data *rd = (struct redirection_data *) *slot; - struct local_info *local_info = (struct local_info *)data; - - /* If this is the template block, then create its outgoing edges - and halt the hash table traversal. */ - if (rd->dup_block && rd->dup_block == local_info->template_block) - { - create_edge_and_update_destination_phis (rd); - return 0; - } - - return 1; -} - -/* Not all jump threading requests are useful. In particular some - jump threading requests can create irreducible regions which are - undesirable. - - This routine will examine the BB's incoming edges for jump threading - requests which, if acted upon, would create irreducible regions. Any - such jump threading requests found will be pruned away. */ - -static void -prune_undesirable_thread_requests (basic_block bb) -{ - edge e; - edge_iterator ei; - bool may_create_irreducible_region = false; - unsigned int num_outgoing_edges_into_loop = 0; - - /* For the heuristics below, we need to know if BB has more than - one outgoing edge into a loop. */ - FOR_EACH_EDGE (e, ei, bb->succs) - num_outgoing_edges_into_loop += ((e->flags & EDGE_LOOP_EXIT) == 0); - - if (num_outgoing_edges_into_loop > 1) - { - edge backedge = NULL; - - /* Consider the effect of threading the edge (0, 1) to 2 on the left - CFG to produce the right CFG: - - - 0 0 - | | - 1<--+ 2<--------+ - / \ | | | - 2 3 | 4<----+ | - \ / | / \ | | - 4---+ E 1-- | --+ - | | | - E 3---+ - - - Threading the (0, 1) edge to 2 effectively creates two loops - (2, 4, 1) and (4, 1, 3) which are neither disjoint nor nested. - This is not good. - - However, we do need to be able to thread (0, 1) to 2 or 3 - in the left CFG below (which creates the middle and right - CFGs with nested loops). - - 0 0 0 - | | | - 1<--+ 2<----+ 3<-+<-+ - /| | | | | | | - 2 | | 3<-+ | 1--+ | - \| | | | | | | - 3---+ 1--+--+ 2-----+ - - - A safe heuristic appears to be to only allow threading if BB - has a single incoming backedge from one of its direct successors. */ - - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (e->flags & EDGE_DFS_BACK) - { - if (backedge) - { - backedge = NULL; - break; - } - else - { - backedge = e; - } - } - } - - if (backedge && find_edge (bb, backedge->src)) - ; - else - may_create_irreducible_region = true; - } - else - { - edge dest = NULL; - - /* If we thread across the loop entry block (BB) into the - loop and BB is still reached from outside the loop, then - we would create an irreducible CFG. Consider the effect - of threading the edge (1, 4) to 5 on the left CFG to produce - the right CFG - - 0 0 - / \ / \ - 1 2 1 2 - \ / | | - 4<----+ 5<->4 - / \ | | - E 5---+ E - - - Threading the (1, 4) edge to 5 creates two entry points - into the loop (4, 5) (one from block 1, the other from - block 2). A classic irreducible region. - - So look at all of BB's incoming edges which are not - backedges and which are not threaded to the loop exit. - If that subset of incoming edges do not all thread - to the same block, then threading any of them will create - an irreducible region. */ - - FOR_EACH_EDGE (e, ei, bb->preds) - { - edge e2; - - /* We ignore back edges for now. This may need refinement - as threading a backedge creates an inner loop which - we would need to verify has a single entry point. - - If all backedges thread to new locations, then this - block will no longer have incoming backedges and we - need not worry about creating irreducible regions - by threading through BB. I don't think this happens - enough in practice to worry about it. */ - if (e->flags & EDGE_DFS_BACK) - continue; - - /* If the incoming edge threads to the loop exit, then it - is clearly safe. */ - e2 = e->aux; - if (e2 && (e2->flags & EDGE_LOOP_EXIT)) - continue; - - /* E enters the loop header and is not threaded. We can - not allow any other incoming edges to thread into - the loop as that would create an irreducible region. */ - if (!e2) - { - may_create_irreducible_region = true; - break; - } - - /* We know that this incoming edge threads to a block inside - the loop. This edge must thread to the same target in - the loop as any previously seen threaded edges. Otherwise - we will create an irreducible region. */ - if (!dest) - dest = e2; - else if (e2 != dest) - { - may_create_irreducible_region = true; - break; - } - } - } - - /* If we might create an irreducible region, then cancel any of - the jump threading requests for incoming edges which are - not backedges and which do not thread to the exit block. */ - if (may_create_irreducible_region) - { - FOR_EACH_EDGE (e, ei, bb->preds) - { - edge e2; - - /* Ignore back edges. */ - if (e->flags & EDGE_DFS_BACK) - continue; - - e2 = e->aux; - - /* If this incoming edge was not threaded, then there is - nothing to do. */ - if (!e2) - continue; - - /* If this incoming edge threaded to the loop exit, - then it can be ignored as it is safe. */ - if (e2->flags & EDGE_LOOP_EXIT) - continue; - - if (e2) - { - /* This edge threaded into the loop and the jump thread - request must be cancelled. */ - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, " Not threading jump %d --> %d to %d\n", - e->src->index, e->dest->index, e2->dest->index); - e->aux = NULL; - } - } - } -} - -/* Hash table traversal callback to redirect each incoming edge - associated with this hash table element to its new destination. */ - -static int -redirect_edges (void **slot, void *data) -{ - struct redirection_data *rd = (struct redirection_data *) *slot; - struct local_info *local_info = (struct local_info *)data; - struct el *next, *el; - - /* Walk over all the incoming edges associated associated with this - hash table entry. */ - for (el = rd->incoming_edges; el; el = next) - { - edge e = el->e; - - /* Go ahead and free this element from the list. Doing this now - avoids the need for another list walk when we destroy the hash - table. */ - next = el->next; - free (el); - - /* Go ahead and clear E->aux. It's not needed anymore and failure - to clear it will cause all kinds of unpleasant problems later. */ - e->aux = NULL; - - thread_stats.num_threaded_edges++; - - if (rd->dup_block) - { - edge e2; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, " Threaded jump %d --> %d to %d\n", - e->src->index, e->dest->index, rd->dup_block->index); - - rd->dup_block->count += e->count; - rd->dup_block->frequency += EDGE_FREQUENCY (e); - EDGE_SUCC (rd->dup_block, 0)->count += e->count; - /* Redirect the incoming edge to the appropriate duplicate - block. */ - e2 = redirect_edge_and_branch (e, rd->dup_block); - flush_pending_stmts (e2); - - if ((dump_file && (dump_flags & TDF_DETAILS)) - && e->src != e2->src) - fprintf (dump_file, " basic block %d created\n", e2->src->index); - } - else - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, " Threaded jump %d --> %d to %d\n", - e->src->index, e->dest->index, local_info->bb->index); - - /* We are using BB as the duplicate. Remove the unnecessary - outgoing edges and statements from BB. */ - remove_ctrl_stmt_and_useless_edges (local_info->bb, - rd->outgoing_edge->dest); - - /* And fixup the flags on the single remaining edge. */ - single_succ_edge (local_info->bb)->flags - &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); - single_succ_edge (local_info->bb)->flags |= EDGE_FALLTHRU; - } - } - - /* Indicate that we actually threaded one or more jumps. */ - if (rd->incoming_edges) - local_info->jumps_threaded = true; - - return 1; -} - -/* 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. */ - -static bool -redirection_block_p (basic_block bb) -{ - block_stmt_iterator bsi; - - /* Advance to the first executable statement. */ - bsi = bsi_start (bb); - while (!bsi_end_p (bsi) - && (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR - || IS_EMPTY_STMT (bsi_stmt (bsi)))) - bsi_next (&bsi); - - /* Check if this is an empty block. */ - if (bsi_end_p (bsi)) - return true; - - /* Test that we've reached the terminating control statement. */ - return bsi_stmt (bsi) - && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR - || TREE_CODE (bsi_stmt (bsi)) == GOTO_EXPR - || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR); -} - -/* 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. - - BB and its duplicates will have assignments to the same set of - SSA_NAMEs. Right now, we just call into update_ssa to update the - SSA graph for those names. - - We are also going to experiment with a true incremental update - scheme for the duplicated resources. One of the interesting - properties we can exploit here is that all the resources set - in BB will have the same IDFS, so we have one IDFS computation - per block with incoming threaded edges, which can lower the - cost of the true incremental update algorithm. */ - -static bool -thread_block (basic_block bb) -{ - /* E is an incoming edge into BB that we may or may not want to - redirect to a duplicate of BB. */ - edge e; - edge_iterator ei; - struct local_info local_info; - - /* FOUND_BACKEDGE indicates that we found an incoming backedge - into BB, in which case we may ignore certain jump threads - to avoid creating irreducible regions. */ - bool found_backedge = false; - - /* ALL indicates whether or not all incoming edges into BB should - be threaded to a duplicate of BB. */ - bool all = true; - - /* If optimizing for size, only thread this block if we don't have - to duplicate it or it's an otherwise empty redirection block. */ - if (optimize_size - && EDGE_COUNT (bb->preds) > 1 - && !redirection_block_p (bb)) - { - FOR_EACH_EDGE (e, ei, bb->preds) - e->aux = NULL; - return false; - } - - /* 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. */ - redirection_data = htab_create (EDGE_COUNT (bb->succs), - redirection_data_hash, - redirection_data_eq, - free); - - FOR_EACH_EDGE (e, ei, bb->preds) - found_backedge |= ((e->flags & EDGE_DFS_BACK) != 0); - - /* If BB has incoming backedges, then threading across BB might - introduce an irreducible region, which would be undesirable - as that inhibits various optimizations later. Prune away - any jump threading requests which we know will result in - an irreducible region. */ - if (found_backedge) - prune_undesirable_thread_requests (bb); - - /* Record each unique threaded destination into a hash table for - efficient lookups. */ - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (!e->aux) - { - all = false; - } - else - { - edge e2 = e->aux; - update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e), - e->count, e->aux); - - /* Insert the outgoing edge into the hash table if it is not - already in the hash table. */ - lookup_redirection_data (e2, e, INSERT); - } - } - - /* If we are going to thread all incoming edges to an outgoing edge, then - BB will become unreachable. Rather than just throwing it away, use - it for one of the duplicates. Mark the first incoming edge with the - DO_NOT_DUPLICATE attribute. */ - if (all) - { - edge e = EDGE_PRED (bb, 0)->aux; - lookup_redirection_data (e, NULL, NO_INSERT)->do_not_duplicate = true; - } - - /* 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. */ - local_info.template_block = NULL; - local_info.bb = bb; - local_info.jumps_threaded = false; - htab_traverse (redirection_data, create_duplicates, &local_info); - - /* 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. */ - htab_traverse (redirection_data, fixup_template_block, &local_info); - - /* 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. */ - htab_traverse (redirection_data, redirect_edges, &local_info); - - /* Done with this block. Clear REDIRECTION_DATA. */ - htab_delete (redirection_data); - redirection_data = NULL; - - /* Indicate to our caller whether or not any jumps were threaded. */ - return local_info.jumps_threaded; -} - -/* 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. */ - -static void -mark_threaded_blocks (bitmap threaded_blocks) -{ - unsigned int i; - - for (i = 0; i < VEC_length (edge, threaded_edges); i += 2) - { - edge e = VEC_index (edge, threaded_edges, i); - edge e2 = VEC_index (edge, threaded_edges, i + 1); - - e->aux = e2; - bitmap_set_bit (threaded_blocks, e->dest->index); - } -} - - -/* 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. - - Returns true if one or more edges were threaded, false otherwise. */ - -bool -thread_through_all_blocks (void) -{ - bool retval = false; - unsigned int i; - bitmap_iterator bi; - bitmap threaded_blocks; - - if (threaded_edges == NULL) - return false; - - threaded_blocks = BITMAP_ALLOC (NULL); - memset (&thread_stats, 0, sizeof (thread_stats)); - - mark_threaded_blocks (threaded_blocks); - - EXECUTE_IF_SET_IN_BITMAP (threaded_blocks, 0, i, bi) - { - basic_block bb = BASIC_BLOCK (i); - - if (EDGE_COUNT (bb->preds) > 0) - retval |= thread_block (bb); - } - - if (dump_file && (dump_flags & TDF_STATS)) - fprintf (dump_file, "\nJumps threaded: %lu\n", - thread_stats.num_threaded_edges); - - BITMAP_FREE (threaded_blocks); - threaded_blocks = NULL; - VEC_free (edge, heap, threaded_edges); - threaded_edges = NULL; - return retval; -} - -/* 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. ie, we - are effectively recording that E->dest can be changed to E2->dest - after fixing the SSA graph. */ - -void -register_jump_thread (edge e, edge e2) -{ - if (threaded_edges == NULL) - threaded_edges = VEC_alloc (edge, heap, 10); - - VEC_safe_push (edge, heap, threaded_edges, e); - VEC_safe_push (edge, heap, threaded_edges, e2); -} |