1 /* Thread edges through blocks and update the control flow and SSA graphs.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010, 201
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "tree-flow.h"
33 #include "hash-table.h"
35 /* Given a block B, update the CFG and SSA graph to reflect redirecting
36 one or more in-edges to B to instead reach the destination of an
37 out-edge from B while preserving any side effects in B.
39 i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
40 side effects of executing B.
42 1. Make a copy of B (including its outgoing edges and statements). Call
43 the copy B'. Note B' has no incoming edges or PHIs at this time.
45 2. Remove the control statement at the end of B' and all outgoing edges
48 3. Add a new argument to each PHI in C with the same value as the existing
49 argument associated with edge B->C. Associate the new PHI arguments
52 4. For each PHI in B, find or create a PHI in B' with an identical
53 PHI_RESULT. Add an argument to the PHI in B' which has the same
54 value as the PHI in B associated with the edge A->B. Associate
55 the new argument in the PHI in B' with the edge A->B.
57 5. Change the edge A->B to A->B'.
59 5a. This automatically deletes any PHI arguments associated with the
62 5b. This automatically associates each new argument added in step 4
65 6. Repeat for other incoming edges into B.
67 7. Put the duplicated resources in B and all the B' blocks into SSA form.
69 Note that block duplication can be minimized by first collecting the
70 set of unique destination blocks that the incoming edges should
73 Block duplication can be further minimized by using B instead of
74 creating B' for one destination if all edges into B are going to be
75 threaded to a successor of B. We had code to do this at one time, but
76 I'm not convinced it is correct with the changes to avoid mucking up
77 the loop structure (which may cancel threading requests, thus a block
78 which we thought was going to become unreachable may still be reachable).
79 This code was also going to get ugly with the introduction of the ability
80 for a single jump thread request to bypass multiple blocks.
82 We further reduce the number of edges and statements we create by
83 not copying all the outgoing edges and the control statement in
84 step #1. We instead create a template block without the outgoing
85 edges and duplicate the template. */
88 /* Steps #5 and #6 of the above algorithm are best implemented by walking
89 all the incoming edges which thread to the same destination edge at
90 the same time. That avoids lots of table lookups to get information
91 for the destination edge.
93 To realize that implementation we create a list of incoming edges
94 which thread to the same outgoing edge. Thus to implement steps
95 #5 and #6 we traverse our hash table of outgoing edge information.
96 For each entry we walk the list of incoming edges which thread to
97 the current outgoing edge. */
105 /* Main data structure recording information regarding B's duplicate
108 /* We need to efficiently record the unique thread destinations of this
109 block and specific information associated with those destinations. We
110 may have many incoming edges threaded to the same outgoing edge. This
111 can be naturally implemented with a hash table. */
113 struct redirection_data
: typed_free_remove
<redirection_data
>
115 /* A duplicate of B with the trailing control statement removed and which
116 targets a single successor of B. */
117 basic_block dup_block
;
119 /* An outgoing edge from B. DUP_BLOCK will have OUTGOING_EDGE->dest as
120 its single successor. */
123 edge intermediate_edge
;
125 /* A list of incoming edges which we want to thread to
126 OUTGOING_EDGE->dest. */
127 struct el
*incoming_edges
;
129 /* hash_table support. */
130 typedef redirection_data T
;
131 static inline hashval_t
hash (const redirection_data
*);
132 static inline int equal (const redirection_data
*, const redirection_data
*);
136 redirection_data::hash (const redirection_data
*p
)
138 edge e
= p
->outgoing_edge
;
139 return e
->dest
->index
;
143 redirection_data::equal (const redirection_data
*p1
, const redirection_data
*p2
)
145 edge e1
= p1
->outgoing_edge
;
146 edge e2
= p2
->outgoing_edge
;
147 edge e3
= p1
->intermediate_edge
;
148 edge e4
= p2
->intermediate_edge
;
149 return e1
== e2
&& e3
== e4
;
152 /* Data structure of information to pass to hash table traversal routines. */
153 struct ssa_local_info_t
155 /* The current block we are working on. */
158 /* A template copy of BB with no outgoing edges or control statement that
159 we use for creating copies. */
160 basic_block template_block
;
162 /* TRUE if we thread one or more jumps, FALSE otherwise. */
166 /* Passes which use the jump threading code register jump threading
167 opportunities as they are discovered. We keep the registered
168 jump threading opportunities in this vector as edge pairs
169 (original_edge, target_edge). */
170 static VEC(edge
,heap
) *threaded_edges
;
172 /* When we start updating the CFG for threading, data necessary for jump
173 threading is attached to the AUX field for the incoming edge. Use these
174 macros to access the underlying structure attached to the AUX field. */
175 #define THREAD_TARGET(E) ((edge *)(E)->aux)[0]
176 #define THREAD_TARGET2(E) ((edge *)(E)->aux)[1]
178 /* Jump threading statistics. */
180 struct thread_stats_d
182 unsigned long num_threaded_edges
;
185 struct thread_stats_d thread_stats
;
188 /* Remove the last statement in block BB if it is a control statement
189 Also remove all outgoing edges except the edge which reaches DEST_BB.
190 If DEST_BB is NULL, then remove all outgoing edges. */
193 remove_ctrl_stmt_and_useless_edges (basic_block bb
, basic_block dest_bb
)
195 gimple_stmt_iterator gsi
;
199 gsi
= gsi_last_bb (bb
);
201 /* If the duplicate ends with a control statement, then remove it.
203 Note that if we are duplicating the template block rather than the
204 original basic block, then the duplicate might not have any real
208 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
209 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_GOTO
210 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_SWITCH
))
211 gsi_remove (&gsi
, true);
213 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
215 if (e
->dest
!= dest_bb
)
222 /* Create a duplicate of BB. Record the duplicate block in RD. */
225 create_block_for_threading (basic_block bb
, struct redirection_data
*rd
)
230 /* We can use the generic block duplication code and simply remove
231 the stuff we do not need. */
232 rd
->dup_block
= duplicate_block (bb
, NULL
, NULL
);
234 FOR_EACH_EDGE (e
, ei
, rd
->dup_block
->succs
)
237 /* Zero out the profile, since the block is unreachable for now. */
238 rd
->dup_block
->frequency
= 0;
239 rd
->dup_block
->count
= 0;
242 /* Main data structure to hold information for duplicates of BB. */
244 static hash_table
<redirection_data
> redirection_data
;
246 /* Given an outgoing edge E lookup and return its entry in our hash table.
248 If INSERT is true, then we insert the entry into the hash table if
249 it is not already present. INCOMING_EDGE is added to the list of incoming
250 edges associated with E in the hash table. */
252 static struct redirection_data
*
253 lookup_redirection_data (edge e
, enum insert_option insert
)
255 struct redirection_data
**slot
;
256 struct redirection_data
*elt
;
258 /* Build a hash table element so we can see if E is already
260 elt
= XNEW (struct redirection_data
);
261 elt
->intermediate_edge
= THREAD_TARGET2 (e
) ? THREAD_TARGET (e
) : NULL
;
262 elt
->outgoing_edge
= THREAD_TARGET2 (e
) ? THREAD_TARGET2 (e
)
264 elt
->dup_block
= NULL
;
265 elt
->incoming_edges
= NULL
;
267 slot
= redirection_data
.find_slot (elt
, insert
);
269 /* This will only happen if INSERT is false and the entry is not
270 in the hash table. */
277 /* This will only happen if E was not in the hash table and
282 elt
->incoming_edges
= XNEW (struct el
);
283 elt
->incoming_edges
->e
= e
;
284 elt
->incoming_edges
->next
= NULL
;
287 /* E was in the hash table. */
290 /* Free ELT as we do not need it anymore, we will extract the
291 relevant entry from the hash table itself. */
294 /* Get the entry stored in the hash table. */
297 /* If insertion was requested, then we need to add INCOMING_EDGE
298 to the list of incoming edges associated with E. */
301 struct el
*el
= XNEW (struct el
);
302 el
->next
= elt
->incoming_edges
;
304 elt
->incoming_edges
= el
;
311 /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E. */
314 copy_phi_args (basic_block bb
, edge src_e
, edge tgt_e
)
316 gimple_stmt_iterator gsi
;
317 int src_indx
= src_e
->dest_idx
;
319 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
321 gimple phi
= gsi_stmt (gsi
);
322 source_location locus
= gimple_phi_arg_location (phi
, src_indx
);
323 add_phi_arg (phi
, gimple_phi_arg_def (phi
, src_indx
), tgt_e
, locus
);
327 /* We have recently made a copy of ORIG_BB, including its outgoing
328 edges. The copy is NEW_BB. Every PHI node in every direct successor of
329 ORIG_BB has a new argument associated with edge from NEW_BB to the
330 successor. Initialize the PHI argument so that it is equal to the PHI
331 argument associated with the edge from ORIG_BB to the successor. */
334 update_destination_phis (basic_block orig_bb
, basic_block new_bb
)
339 FOR_EACH_EDGE (e
, ei
, orig_bb
->succs
)
341 edge e2
= find_edge (new_bb
, e
->dest
);
342 copy_phi_args (e
->dest
, e
, e2
);
346 /* Given a duplicate block and its single destination (both stored
347 in RD). Create an edge between the duplicate and its single
350 Add an additional argument to any PHI nodes at the single
354 create_edge_and_update_destination_phis (struct redirection_data
*rd
,
357 edge e
= make_edge (bb
, rd
->outgoing_edge
->dest
, EDGE_FALLTHRU
);
359 rescan_loop_exit (e
, true, false);
360 e
->probability
= REG_BR_PROB_BASE
;
361 e
->count
= bb
->count
;
363 if (rd
->outgoing_edge
->aux
)
365 e
->aux
= (edge
*) XNEWVEC (edge
, 2);
366 THREAD_TARGET(e
) = THREAD_TARGET (rd
->outgoing_edge
);
367 THREAD_TARGET2(e
) = THREAD_TARGET2 (rd
->outgoing_edge
);
374 /* If there are any PHI nodes at the destination of the outgoing edge
375 from the duplicate block, then we will need to add a new argument
376 to them. The argument should have the same value as the argument
377 associated with the outgoing edge stored in RD. */
378 copy_phi_args (e
->dest
, rd
->outgoing_edge
, e
);
381 /* Wire up the outgoing edges from the duplicate block and
382 update any PHIs as needed. */
384 ssa_fix_duplicate_block_edges (struct redirection_data
*rd
,
385 ssa_local_info_t
*local_info
)
387 /* If we were threading through an joiner block, then we want
388 to keep its control statement and redirect an outgoing edge.
389 Else we want to remove the control statement & edges, then create
390 a new outgoing edge. In both cases we may need to update PHIs. */
391 if (THREAD_TARGET2 (rd
->incoming_edges
->e
))
395 edge e
= rd
->incoming_edges
->e
;
397 /* This updates the PHIs at the destination of the duplicate
399 update_destination_phis (local_info
->bb
, rd
->dup_block
);
401 /* Find the edge from the duplicate block to the block we're
402 threading through. That's the edge we want to redirect. */
403 victim
= find_edge (rd
->dup_block
, THREAD_TARGET (e
)->dest
);
404 e2
= redirect_edge_and_branch (victim
, THREAD_TARGET2 (e
)->dest
);
406 /* If we redirected the edge, then we need to copy PHI arguments
407 at the target. If the edge already existed (e2 != victim case),
408 then the PHIs in the target already have the correct arguments. */
410 copy_phi_args (e2
->dest
, THREAD_TARGET2 (e
), e2
);
414 remove_ctrl_stmt_and_useless_edges (rd
->dup_block
, NULL
);
415 create_edge_and_update_destination_phis (rd
, rd
->dup_block
);
418 /* Hash table traversal callback routine to create duplicate blocks. */
421 ssa_create_duplicates (struct redirection_data
**slot
,
422 ssa_local_info_t
*local_info
)
424 struct redirection_data
*rd
= *slot
;
426 /* Create a template block if we have not done so already. Otherwise
427 use the template to create a new block. */
428 if (local_info
->template_block
== NULL
)
430 create_block_for_threading (local_info
->bb
, rd
);
431 local_info
->template_block
= rd
->dup_block
;
433 /* We do not create any outgoing edges for the template. We will
434 take care of that in a later traversal. That way we do not
435 create edges that are going to just be deleted. */
439 create_block_for_threading (local_info
->template_block
, rd
);
441 /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
443 ssa_fix_duplicate_block_edges (rd
, local_info
);
446 /* Keep walking the hash table. */
450 /* We did not create any outgoing edges for the template block during
451 block creation. This hash table traversal callback creates the
452 outgoing edge for the template block. */
455 ssa_fixup_template_block (struct redirection_data
**slot
,
456 ssa_local_info_t
*local_info
)
458 struct redirection_data
*rd
= *slot
;
460 /* If this is the template block halt the traversal after updating
463 If we were threading through an joiner block, then we want
464 to keep its control statement and redirect an outgoing edge.
465 Else we want to remove the control statement & edges, then create
466 a new outgoing edge. In both cases we may need to update PHIs. */
467 if (rd
->dup_block
&& rd
->dup_block
== local_info
->template_block
)
469 ssa_fix_duplicate_block_edges (rd
, local_info
);
476 /* Hash table traversal callback to redirect each incoming edge
477 associated with this hash table element to its new destination. */
480 ssa_redirect_edges (struct redirection_data
**slot
,
481 ssa_local_info_t
*local_info
)
483 struct redirection_data
*rd
= *slot
;
484 struct el
*next
, *el
;
486 /* Walk over all the incoming edges associated associated with this
488 for (el
= rd
->incoming_edges
; el
; el
= next
)
492 /* Go ahead and free this element from the list. Doing this now
493 avoids the need for another list walk when we destroy the hash
498 thread_stats
.num_threaded_edges
++;
499 /* If we are threading through a joiner block, then we have to
500 find the edge we want to redirect and update some PHI nodes. */
501 if (THREAD_TARGET2 (e
))
505 /* We want to redirect the incoming edge to the joiner block (E)
506 to instead reach the duplicate of the joiner block. */
507 e2
= redirect_edge_and_branch (e
, rd
->dup_block
);
508 flush_pending_stmts (e2
);
510 else if (rd
->dup_block
)
514 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
515 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
516 e
->src
->index
, e
->dest
->index
, rd
->dup_block
->index
);
518 rd
->dup_block
->count
+= e
->count
;
520 /* Excessive jump threading may make frequencies large enough so
521 the computation overflows. */
522 if (rd
->dup_block
->frequency
< BB_FREQ_MAX
* 2)
523 rd
->dup_block
->frequency
+= EDGE_FREQUENCY (e
);
524 EDGE_SUCC (rd
->dup_block
, 0)->count
+= e
->count
;
525 /* Redirect the incoming edge to the appropriate duplicate
527 e2
= redirect_edge_and_branch (e
, rd
->dup_block
);
528 gcc_assert (e
== e2
);
529 flush_pending_stmts (e2
);
532 /* Go ahead and clear E->aux. It's not needed anymore and failure
533 to clear it will cause all kinds of unpleasant problems later. */
539 /* Indicate that we actually threaded one or more jumps. */
540 if (rd
->incoming_edges
)
541 local_info
->jumps_threaded
= true;
546 /* Return true if this block has no executable statements other than
547 a simple ctrl flow instruction. When the number of outgoing edges
548 is one, this is equivalent to a "forwarder" block. */
551 redirection_block_p (basic_block bb
)
553 gimple_stmt_iterator gsi
;
555 /* Advance to the first executable statement. */
556 gsi
= gsi_start_bb (bb
);
557 while (!gsi_end_p (gsi
)
558 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_LABEL
559 || is_gimple_debug (gsi_stmt (gsi
))
560 || gimple_nop_p (gsi_stmt (gsi
))))
563 /* Check if this is an empty block. */
567 /* Test that we've reached the terminating control statement. */
568 return gsi_stmt (gsi
)
569 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
570 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_GOTO
571 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_SWITCH
);
574 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
575 is reached via one or more specific incoming edges, we know which
576 outgoing edge from BB will be traversed.
578 We want to redirect those incoming edges to the target of the
579 appropriate outgoing edge. Doing so avoids a conditional branch
580 and may expose new optimization opportunities. Note that we have
581 to update dominator tree and SSA graph after such changes.
583 The key to keeping the SSA graph update manageable is to duplicate
584 the side effects occurring in BB so that those side effects still
585 occur on the paths which bypass BB after redirecting edges.
587 We accomplish this by creating duplicates of BB and arranging for
588 the duplicates to unconditionally pass control to one specific
589 successor of BB. We then revector the incoming edges into BB to
590 the appropriate duplicate of BB.
592 If NOLOOP_ONLY is true, we only perform the threading as long as it
593 does not affect the structure of the loops in a nontrivial way. */
596 thread_block (basic_block bb
, bool noloop_only
)
598 /* E is an incoming edge into BB that we may or may not want to
599 redirect to a duplicate of BB. */
602 ssa_local_info_t local_info
;
603 struct loop
*loop
= bb
->loop_father
;
605 /* To avoid scanning a linear array for the element we need we instead
606 use a hash table. For normal code there should be no noticeable
607 difference. However, if we have a block with a large number of
608 incoming and outgoing edges such linear searches can get expensive. */
609 redirection_data
.create (EDGE_COUNT (bb
->succs
));
611 /* If we thread the latch of the loop to its exit, the loop ceases to
612 exist. Make sure we do not restrict ourselves in order to preserve
614 if (loop
->header
== bb
)
616 e
= loop_latch_edge (loop
);
619 e2
= THREAD_TARGET (e
);
623 if (e2
&& loop_exit_edge_p (loop
, e2
))
627 loops_state_set (LOOPS_NEED_FIXUP
);
631 /* Record each unique threaded destination into a hash table for
632 efficient lookups. */
633 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
638 if (THREAD_TARGET2 (e
))
639 e2
= THREAD_TARGET2 (e
);
641 e2
= THREAD_TARGET (e
);
644 /* If NOLOOP_ONLY is true, we only allow threading through the
645 header of a loop to exit edges. */
647 && bb
== bb
->loop_father
->header
648 && (!loop_exit_edge_p (bb
->loop_father
, e2
)
649 || THREAD_TARGET2 (e
))))
652 if (e
->dest
== e2
->src
)
653 update_bb_profile_for_threading (e
->dest
, EDGE_FREQUENCY (e
),
654 e
->count
, THREAD_TARGET (e
));
656 /* Insert the outgoing edge into the hash table if it is not
657 already in the hash table. */
658 lookup_redirection_data (e
, INSERT
);
661 /* We do not update dominance info. */
662 free_dominance_info (CDI_DOMINATORS
);
664 /* We know we only thread through the loop header to loop exits.
665 Let the basic block duplication hook know we are not creating
666 a multiple entry loop. */
668 && bb
== bb
->loop_father
->header
)
669 set_loop_copy (bb
->loop_father
, loop_outer (bb
->loop_father
));
671 /* Now create duplicates of BB.
673 Note that for a block with a high outgoing degree we can waste
674 a lot of time and memory creating and destroying useless edges.
676 So we first duplicate BB and remove the control structure at the
677 tail of the duplicate as well as all outgoing edges from the
678 duplicate. We then use that duplicate block as a template for
679 the rest of the duplicates. */
680 local_info
.template_block
= NULL
;
682 local_info
.jumps_threaded
= false;
683 redirection_data
.traverse
<ssa_local_info_t
*, ssa_create_duplicates
>
686 /* The template does not have an outgoing edge. Create that outgoing
687 edge and update PHI nodes as the edge's target as necessary.
689 We do this after creating all the duplicates to avoid creating
690 unnecessary edges. */
691 redirection_data
.traverse
<ssa_local_info_t
*, ssa_fixup_template_block
>
694 /* The hash table traversals above created the duplicate blocks (and the
695 statements within the duplicate blocks). This loop creates PHI nodes for
696 the duplicated blocks and redirects the incoming edges into BB to reach
697 the duplicates of BB. */
698 redirection_data
.traverse
<ssa_local_info_t
*, ssa_redirect_edges
>
701 /* Done with this block. Clear REDIRECTION_DATA. */
702 redirection_data
.dispose ();
705 && bb
== bb
->loop_father
->header
)
706 set_loop_copy (bb
->loop_father
, NULL
);
708 /* Indicate to our caller whether or not any jumps were threaded. */
709 return local_info
.jumps_threaded
;
712 /* Threads edge E through E->dest to the edge THREAD_TARGET (E). Returns the
713 copy of E->dest created during threading, or E->dest if it was not necessary
714 to copy it (E is its single predecessor). */
717 thread_single_edge (edge e
)
719 basic_block bb
= e
->dest
;
720 edge eto
= THREAD_TARGET (e
);
721 struct redirection_data rd
;
726 thread_stats
.num_threaded_edges
++;
728 if (single_pred_p (bb
))
730 /* If BB has just a single predecessor, we should only remove the
731 control statements at its end, and successors except for ETO. */
732 remove_ctrl_stmt_and_useless_edges (bb
, eto
->dest
);
734 /* And fixup the flags on the single remaining edge. */
735 eto
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
| EDGE_ABNORMAL
);
736 eto
->flags
|= EDGE_FALLTHRU
;
741 /* Otherwise, we need to create a copy. */
742 if (e
->dest
== eto
->src
)
743 update_bb_profile_for_threading (bb
, EDGE_FREQUENCY (e
), e
->count
, eto
);
745 rd
.outgoing_edge
= eto
;
747 create_block_for_threading (bb
, &rd
);
748 remove_ctrl_stmt_and_useless_edges (rd
.dup_block
, NULL
);
749 create_edge_and_update_destination_phis (&rd
, rd
.dup_block
);
751 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
752 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
753 e
->src
->index
, e
->dest
->index
, rd
.dup_block
->index
);
755 rd
.dup_block
->count
= e
->count
;
756 rd
.dup_block
->frequency
= EDGE_FREQUENCY (e
);
757 single_succ_edge (rd
.dup_block
)->count
= e
->count
;
758 redirect_edge_and_branch (e
, rd
.dup_block
);
759 flush_pending_stmts (e
);
764 /* Callback for dfs_enumerate_from. Returns true if BB is different
765 from STOP and DBDS_CE_STOP. */
767 static basic_block dbds_ce_stop
;
769 dbds_continue_enumeration_p (const_basic_block bb
, const void *stop
)
771 return (bb
!= (const_basic_block
) stop
772 && bb
!= dbds_ce_stop
);
775 /* Evaluates the dominance relationship of latch of the LOOP and BB, and
776 returns the state. */
780 /* BB does not dominate latch of the LOOP. */
782 /* The LOOP is broken (there is no path from the header to its latch. */
784 /* BB dominates the latch of the LOOP. */
788 static enum bb_dom_status
789 determine_bb_domination_status (struct loop
*loop
, basic_block bb
)
791 basic_block
*bblocks
;
793 bool bb_reachable
= false;
797 /* This function assumes BB is a successor of LOOP->header.
798 If that is not the case return DOMST_NONDOMINATING which
803 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
805 if (e
->src
== loop
->header
)
813 return DOMST_NONDOMINATING
;
816 if (bb
== loop
->latch
)
817 return DOMST_DOMINATING
;
819 /* Check that BB dominates LOOP->latch, and that it is back-reachable
822 bblocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
823 dbds_ce_stop
= loop
->header
;
824 nblocks
= dfs_enumerate_from (loop
->latch
, 1, dbds_continue_enumeration_p
,
825 bblocks
, loop
->num_nodes
, bb
);
826 for (i
= 0; i
< nblocks
; i
++)
827 FOR_EACH_EDGE (e
, ei
, bblocks
[i
]->preds
)
829 if (e
->src
== loop
->header
)
832 return DOMST_NONDOMINATING
;
839 return (bb_reachable
? DOMST_DOMINATING
: DOMST_LOOP_BROKEN
);
842 /* Return true if BB is part of the new pre-header that is created
843 when threading the latch to DATA. */
846 def_split_header_continue_p (const_basic_block bb
, const void *data
)
848 const_basic_block new_header
= (const_basic_block
) data
;
849 return (bb
->loop_father
== new_header
->loop_father
850 && bb
!= new_header
);
853 /* Thread jumps through the header of LOOP. Returns true if cfg changes.
854 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
855 to the inside of the loop. */
858 thread_through_loop_header (struct loop
*loop
, bool may_peel_loop_headers
)
860 basic_block header
= loop
->header
;
861 edge e
, tgt_edge
, latch
= loop_latch_edge (loop
);
863 basic_block tgt_bb
, atgt_bb
;
864 enum bb_dom_status domst
;
866 /* We have already threaded through headers to exits, so all the threading
867 requests now are to the inside of the loop. We need to avoid creating
868 irreducible regions (i.e., loops with more than one entry block), and
869 also loop with several latch edges, or new subloops of the loop (although
870 there are cases where it might be appropriate, it is difficult to decide,
871 and doing it wrongly may confuse other optimizers).
873 We could handle more general cases here. However, the intention is to
874 preserve some information about the loop, which is impossible if its
875 structure changes significantly, in a way that is not well understood.
876 Thus we only handle few important special cases, in which also updating
877 of the loop-carried information should be feasible:
879 1) Propagation of latch edge to a block that dominates the latch block
880 of a loop. This aims to handle the following idiom:
891 After threading the latch edge, this becomes
902 The original header of the loop is moved out of it, and we may thread
903 the remaining edges through it without further constraints.
905 2) All entry edges are propagated to a single basic block that dominates
906 the latch block of the loop. This aims to handle the following idiom
907 (normally created for "for" loops):
930 /* Threading through the header won't improve the code if the header has just
932 if (single_succ_p (header
))
937 if (THREAD_TARGET2 (latch
))
939 tgt_edge
= THREAD_TARGET (latch
);
940 tgt_bb
= tgt_edge
->dest
;
942 else if (!may_peel_loop_headers
943 && !redirection_block_p (loop
->header
))
949 FOR_EACH_EDGE (e
, ei
, header
->preds
)
956 /* If latch is not threaded, and there is a header
957 edge that is not threaded, we would create loop
958 with multiple entries. */
962 if (THREAD_TARGET2 (e
))
964 tgt_edge
= THREAD_TARGET (e
);
965 atgt_bb
= tgt_edge
->dest
;
968 /* Two targets of threading would make us create loop
969 with multiple entries. */
970 else if (tgt_bb
!= atgt_bb
)
976 /* There are no threading requests. */
980 /* Redirecting to empty loop latch is useless. */
981 if (tgt_bb
== loop
->latch
982 && empty_block_p (loop
->latch
))
986 /* The target block must dominate the loop latch, otherwise we would be
987 creating a subloop. */
988 domst
= determine_bb_domination_status (loop
, tgt_bb
);
989 if (domst
== DOMST_NONDOMINATING
)
991 if (domst
== DOMST_LOOP_BROKEN
)
993 /* If the loop ceased to exist, mark it as such, and thread through its
997 loops_state_set (LOOPS_NEED_FIXUP
);
998 return thread_block (header
, false);
1001 if (tgt_bb
->loop_father
->header
== tgt_bb
)
1003 /* If the target of the threading is a header of a subloop, we need
1004 to create a preheader for it, so that the headers of the two loops
1006 if (EDGE_COUNT (tgt_bb
->preds
) > 2)
1008 tgt_bb
= create_preheader (tgt_bb
->loop_father
, 0);
1009 gcc_assert (tgt_bb
!= NULL
);
1012 tgt_bb
= split_edge (tgt_edge
);
1017 basic_block
*bblocks
;
1018 unsigned nblocks
, i
;
1020 /* First handle the case latch edge is redirected. We are copying
1021 the loop header but not creating a multiple entry loop. Make the
1022 cfg manipulation code aware of that fact. */
1023 set_loop_copy (loop
, loop
);
1024 loop
->latch
= thread_single_edge (latch
);
1025 set_loop_copy (loop
, NULL
);
1026 gcc_assert (single_succ (loop
->latch
) == tgt_bb
);
1027 loop
->header
= tgt_bb
;
1029 /* Remove the new pre-header blocks from our loop. */
1030 bblocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1031 nblocks
= dfs_enumerate_from (header
, 0, def_split_header_continue_p
,
1032 bblocks
, loop
->num_nodes
, tgt_bb
);
1033 for (i
= 0; i
< nblocks
; i
++)
1035 remove_bb_from_loops (bblocks
[i
]);
1036 add_bb_to_loop (bblocks
[i
], loop_outer (loop
));
1040 /* Cancel remaining threading requests that would make the
1041 loop a multiple entry loop. */
1042 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1048 if (THREAD_TARGET2 (e
))
1049 e2
= THREAD_TARGET2 (e
);
1051 e2
= THREAD_TARGET (e
);
1053 if (e
->src
->loop_father
!= e2
->dest
->loop_father
1054 && e2
->dest
!= loop
->header
)
1061 /* Thread the remaining edges through the former header. */
1062 thread_block (header
, false);
1066 basic_block new_preheader
;
1068 /* Now consider the case entry edges are redirected to the new entry
1069 block. Remember one entry edge, so that we can find the new
1070 preheader (its destination after threading). */
1071 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1077 /* The duplicate of the header is the new preheader of the loop. Ensure
1078 that it is placed correctly in the loop hierarchy. */
1079 set_loop_copy (loop
, loop_outer (loop
));
1081 thread_block (header
, false);
1082 set_loop_copy (loop
, NULL
);
1083 new_preheader
= e
->dest
;
1085 /* Create the new latch block. This is always necessary, as the latch
1086 must have only a single successor, but the original header had at
1087 least two successors. */
1089 mfb_kj_edge
= single_succ_edge (new_preheader
);
1090 loop
->header
= mfb_kj_edge
->dest
;
1091 latch
= make_forwarder_block (tgt_bb
, mfb_keep_just
, NULL
);
1092 loop
->header
= latch
->dest
;
1093 loop
->latch
= latch
->src
;
1099 /* We failed to thread anything. Cancel the requests. */
1100 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1108 /* Walk through the registered jump threads and convert them into a
1109 form convenient for this pass.
1111 Any block which has incoming edges threaded to outgoing edges
1112 will have its entry in THREADED_BLOCK set.
1114 Any threaded edge will have its new outgoing edge stored in the
1115 original edge's AUX field.
1117 This form avoids the need to walk all the edges in the CFG to
1118 discover blocks which need processing and avoids unnecessary
1119 hash table lookups to map from threaded edge to new target. */
1122 mark_threaded_blocks (bitmap threaded_blocks
)
1126 bitmap tmp
= BITMAP_ALLOC (NULL
);
1131 for (i
= 0; i
< VEC_length (edge
, threaded_edges
); i
+= 3)
1133 edge e
= VEC_index (edge
, threaded_edges
, i
);
1134 edge
*x
= (edge
*) XNEWVEC (edge
, 2);
1137 THREAD_TARGET (e
) = VEC_index (edge
, threaded_edges
, i
+ 1);
1138 THREAD_TARGET2 (e
) = VEC_index (edge
, threaded_edges
, i
+ 2);
1139 bitmap_set_bit (tmp
, e
->dest
->index
);
1142 /* If optimizing for size, only thread through block if we don't have
1143 to duplicate it or it's an otherwise empty redirection block. */
1144 if (optimize_function_for_size_p (cfun
))
1146 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
1148 bb
= BASIC_BLOCK (i
);
1149 if (EDGE_COUNT (bb
->preds
) > 1
1150 && !redirection_block_p (bb
))
1152 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1159 bitmap_set_bit (threaded_blocks
, i
);
1163 bitmap_copy (threaded_blocks
, tmp
);
1169 /* Walk through all blocks and thread incoming edges to the appropriate
1170 outgoing edge for each edge pair recorded in THREADED_EDGES.
1172 It is the caller's responsibility to fix the dominance information
1173 and rewrite duplicated SSA_NAMEs back into SSA form.
1175 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
1176 loop headers if it does not simplify the loop.
1178 Returns true if one or more edges were threaded, false otherwise. */
1181 thread_through_all_blocks (bool may_peel_loop_headers
)
1183 bool retval
= false;
1186 bitmap threaded_blocks
;
1190 /* We must know about loops in order to preserve them. */
1191 gcc_assert (current_loops
!= NULL
);
1193 if (threaded_edges
== NULL
)
1196 threaded_blocks
= BITMAP_ALLOC (NULL
);
1197 memset (&thread_stats
, 0, sizeof (thread_stats
));
1199 mark_threaded_blocks (threaded_blocks
);
1201 initialize_original_copy_tables ();
1203 /* First perform the threading requests that do not affect
1205 EXECUTE_IF_SET_IN_BITMAP (threaded_blocks
, 0, i
, bi
)
1207 basic_block bb
= BASIC_BLOCK (i
);
1209 if (EDGE_COUNT (bb
->preds
) > 0)
1210 retval
|= thread_block (bb
, true);
1213 /* Then perform the threading through loop headers. We start with the
1214 innermost loop, so that the changes in cfg we perform won't affect
1215 further threading. */
1216 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1219 || !bitmap_bit_p (threaded_blocks
, loop
->header
->index
))
1222 retval
|= thread_through_loop_header (loop
, may_peel_loop_headers
);
1225 statistics_counter_event (cfun
, "Jumps threaded",
1226 thread_stats
.num_threaded_edges
);
1228 free_original_copy_tables ();
1230 BITMAP_FREE (threaded_blocks
);
1231 threaded_blocks
= NULL
;
1232 VEC_free (edge
, heap
, threaded_edges
);
1233 threaded_edges
= NULL
;
1236 loops_state_set (LOOPS_NEED_FIXUP
);
1241 /* Register a jump threading opportunity. We queue up all the jump
1242 threading opportunities discovered by a pass and update the CFG
1243 and SSA form all at once.
1245 E is the edge we can thread, E2 is the new target edge, i.e., we
1246 are effectively recording that E->dest can be changed to E2->dest
1247 after fixing the SSA graph. */
1250 register_jump_thread (edge e
, edge e2
, edge e3
)
1252 /* This can occur if we're jumping to a constant address or
1253 or something similar. Just get out now. */
1257 if (threaded_edges
== NULL
)
1258 threaded_edges
= VEC_alloc (edge
, heap
, 15);
1260 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1261 && e
->dest
!= e2
->src
)
1263 " Registering jump thread around one or more intermediate blocks\n");
1265 VEC_safe_push (edge
, heap
, threaded_edges
, e
);
1266 VEC_safe_push (edge
, heap
, threaded_edges
, e2
);
1267 VEC_safe_push (edge
, heap
, threaded_edges
, e3
);