+/* 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 = xmalloc (sizeof (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 = xmalloc (sizeof (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 = xmalloc (sizeof (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);
+
+ /* 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;
+}
+