1 /* Thread edges through blocks and update the control flow and SSA graphs.
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "fold-const.h"
31 #include "gimple-iterator.h"
33 #include "tree-ssa-threadupdate.h"
37 #include "tree-vectorizer.h"
39 /* Given a block B, update the CFG and SSA graph to reflect redirecting
40 one or more in-edges to B to instead reach the destination of an
41 out-edge from B while preserving any side effects in B.
43 i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
44 side effects of executing B.
46 1. Make a copy of B (including its outgoing edges and statements). Call
47 the copy B'. Note B' has no incoming edges or PHIs at this time.
49 2. Remove the control statement at the end of B' and all outgoing edges
52 3. Add a new argument to each PHI in C with the same value as the existing
53 argument associated with edge B->C. Associate the new PHI arguments
56 4. For each PHI in B, find or create a PHI in B' with an identical
57 PHI_RESULT. Add an argument to the PHI in B' which has the same
58 value as the PHI in B associated with the edge A->B. Associate
59 the new argument in the PHI in B' with the edge A->B.
61 5. Change the edge A->B to A->B'.
63 5a. This automatically deletes any PHI arguments associated with the
66 5b. This automatically associates each new argument added in step 4
69 6. Repeat for other incoming edges into B.
71 7. Put the duplicated resources in B and all the B' blocks into SSA form.
73 Note that block duplication can be minimized by first collecting the
74 set of unique destination blocks that the incoming edges should
77 We reduce the number of edges and statements we create by not copying all
78 the outgoing edges and the control statement in step #1. We instead create
79 a template block without the outgoing edges and duplicate the template.
81 Another case this code handles is threading through a "joiner" block. In
82 this case, we do not know the destination of the joiner block, but one
83 of the outgoing edges from the joiner block leads to a threadable path. This
84 case largely works as outlined above, except the duplicate of the joiner
85 block still contains a full set of outgoing edges and its control statement.
86 We just redirect one of its outgoing edges to our jump threading path. */
89 /* Steps #5 and #6 of the above algorithm are best implemented by walking
90 all the incoming edges which thread to the same destination edge at
91 the same time. That avoids lots of table lookups to get information
92 for the destination edge.
94 To realize that implementation we create a list of incoming edges
95 which thread to the same outgoing edge. Thus to implement steps
96 #5 and #6 we traverse our hash table of outgoing edge information.
97 For each entry we walk the list of incoming edges which thread to
98 the current outgoing edge. */
106 /* Main data structure recording information regarding B's duplicate
109 /* We need to efficiently record the unique thread destinations of this
110 block and specific information associated with those destinations. We
111 may have many incoming edges threaded to the same outgoing edge. This
112 can be naturally implemented with a hash table. */
114 struct redirection_data
: free_ptr_hash
<redirection_data
>
116 /* We support wiring up two block duplicates in a jump threading path.
118 One is a normal block copy where we remove the control statement
119 and wire up its single remaining outgoing edge to the thread path.
121 The other is a joiner block where we leave the control statement
122 in place, but wire one of the outgoing edges to a thread path.
124 In theory we could have multiple block duplicates in a jump
125 threading path, but I haven't tried that.
127 The duplicate blocks appear in this array in the same order in
128 which they appear in the jump thread path. */
129 basic_block dup_blocks
[2];
131 /* The jump threading path. */
132 vec
<jump_thread_edge
*> *path
;
134 /* A list of incoming edges which we want to thread to the
136 struct el
*incoming_edges
;
138 /* hash_table support. */
139 static inline hashval_t
hash (const redirection_data
*);
140 static inline int equal (const redirection_data
*, const redirection_data
*);
143 /* Dump a jump threading path, including annotations about each
147 dump_jump_thread_path (FILE *dump_file
, vec
<jump_thread_edge
*> path
,
151 " %s%s jump thread: (%d, %d) incoming edge; ",
152 (registering
? "Registering" : "Cancelling"),
153 (path
[0]->type
== EDGE_FSM_THREAD
? " FSM": ""),
154 path
[0]->e
->src
->index
, path
[0]->e
->dest
->index
);
156 for (unsigned int i
= 1; i
< path
.length (); i
++)
158 /* We can get paths with a NULL edge when the final destination
159 of a jump thread turns out to be a constant address. We dump
160 those paths when debugging, so we have to be prepared for that
162 if (path
[i
]->e
== NULL
)
165 if (path
[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
166 fprintf (dump_file
, " (%d, %d) joiner; ",
167 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
168 if (path
[i
]->type
== EDGE_COPY_SRC_BLOCK
)
169 fprintf (dump_file
, " (%d, %d) normal;",
170 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
171 if (path
[i
]->type
== EDGE_NO_COPY_SRC_BLOCK
)
172 fprintf (dump_file
, " (%d, %d) nocopy;",
173 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
174 if (path
[0]->type
== EDGE_FSM_THREAD
)
175 fprintf (dump_file
, " (%d, %d) ",
176 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
178 fputc ('\n', dump_file
);
181 /* Simple hashing function. For any given incoming edge E, we're going
182 to be most concerned with the final destination of its jump thread
183 path. So hash on the block index of the final edge in the path. */
186 redirection_data::hash (const redirection_data
*p
)
188 vec
<jump_thread_edge
*> *path
= p
->path
;
189 return path
->last ()->e
->dest
->index
;
192 /* Given two hash table entries, return true if they have the same
193 jump threading path. */
195 redirection_data::equal (const redirection_data
*p1
, const redirection_data
*p2
)
197 vec
<jump_thread_edge
*> *path1
= p1
->path
;
198 vec
<jump_thread_edge
*> *path2
= p2
->path
;
200 if (path1
->length () != path2
->length ())
203 for (unsigned int i
= 1; i
< path1
->length (); i
++)
205 if ((*path1
)[i
]->type
!= (*path2
)[i
]->type
206 || (*path1
)[i
]->e
!= (*path2
)[i
]->e
)
213 /* Rather than search all the edges in jump thread paths each time
214 DOM is able to simply if control statement, we build a hash table
215 with the deleted edges. We only care about the address of the edge,
217 struct removed_edges
: nofree_ptr_hash
<edge_def
>
219 static hashval_t
hash (edge e
) { return htab_hash_pointer (e
); }
220 static bool equal (edge e1
, edge e2
) { return e1
== e2
; }
223 static hash_table
<removed_edges
> *removed_edges
;
225 /* Data structure of information to pass to hash table traversal routines. */
226 struct ssa_local_info_t
228 /* The current block we are working on. */
231 /* We only create a template block for the first duplicated block in a
232 jump threading path as we may need many duplicates of that block.
234 The second duplicate block in a path is specific to that path. Creating
235 and sharing a template for that block is considerably more difficult. */
236 basic_block template_block
;
238 /* Blocks duplicated for the thread. */
239 bitmap duplicate_blocks
;
241 /* TRUE if we thread one or more jumps, FALSE otherwise. */
244 /* When we have multiple paths through a joiner which reach different
245 final destinations, then we may need to correct for potential
246 profile insanities. */
247 bool need_profile_correction
;
250 /* Passes which use the jump threading code register jump threading
251 opportunities as they are discovered. We keep the registered
252 jump threading opportunities in this vector as edge pairs
253 (original_edge, target_edge). */
254 static vec
<vec
<jump_thread_edge
*> *> paths
;
256 /* When we start updating the CFG for threading, data necessary for jump
257 threading is attached to the AUX field for the incoming edge. Use these
258 macros to access the underlying structure attached to the AUX field. */
259 #define THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux)
261 /* Jump threading statistics. */
263 struct thread_stats_d
265 unsigned long num_threaded_edges
;
268 struct thread_stats_d thread_stats
;
271 /* Remove the last statement in block BB if it is a control statement
272 Also remove all outgoing edges except the edge which reaches DEST_BB.
273 If DEST_BB is NULL, then remove all outgoing edges. */
276 remove_ctrl_stmt_and_useless_edges (basic_block bb
, basic_block dest_bb
)
278 gimple_stmt_iterator gsi
;
282 gsi
= gsi_last_bb (bb
);
284 /* If the duplicate ends with a control statement, then remove it.
286 Note that if we are duplicating the template block rather than the
287 original basic block, then the duplicate might not have any real
291 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
292 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_GOTO
293 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_SWITCH
))
294 gsi_remove (&gsi
, true);
296 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
298 if (e
->dest
!= dest_bb
)
300 free_dom_edge_info (e
);
305 e
->probability
= REG_BR_PROB_BASE
;
306 e
->count
= bb
->count
;
311 /* If the remaining edge is a loop exit, there must have
312 a removed edge that was not a loop exit.
314 In that case BB and possibly other blocks were previously
315 in the loop, but are now outside the loop. Thus, we need
316 to update the loop structures. */
317 if (single_succ_p (bb
)
318 && loop_outer (bb
->loop_father
)
319 && loop_exit_edge_p (bb
->loop_father
, single_succ_edge (bb
)))
320 loops_state_set (LOOPS_NEED_FIXUP
);
323 /* Create a duplicate of BB. Record the duplicate block in an array
324 indexed by COUNT stored in RD. */
327 create_block_for_threading (basic_block bb
,
328 struct redirection_data
*rd
,
330 bitmap
*duplicate_blocks
)
335 /* We can use the generic block duplication code and simply remove
336 the stuff we do not need. */
337 rd
->dup_blocks
[count
] = duplicate_block (bb
, NULL
, NULL
);
339 FOR_EACH_EDGE (e
, ei
, rd
->dup_blocks
[count
]->succs
)
342 /* Zero out the profile, since the block is unreachable for now. */
343 rd
->dup_blocks
[count
]->frequency
= 0;
344 rd
->dup_blocks
[count
]->count
= profile_count::uninitialized ();
345 if (duplicate_blocks
)
346 bitmap_set_bit (*duplicate_blocks
, rd
->dup_blocks
[count
]->index
);
349 /* Main data structure to hold information for duplicates of BB. */
351 static hash_table
<redirection_data
> *redirection_data
;
353 /* Given an outgoing edge E lookup and return its entry in our hash table.
355 If INSERT is true, then we insert the entry into the hash table if
356 it is not already present. INCOMING_EDGE is added to the list of incoming
357 edges associated with E in the hash table. */
359 static struct redirection_data
*
360 lookup_redirection_data (edge e
, enum insert_option insert
)
362 struct redirection_data
**slot
;
363 struct redirection_data
*elt
;
364 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
366 /* Build a hash table element so we can see if E is already
368 elt
= XNEW (struct redirection_data
);
370 elt
->dup_blocks
[0] = NULL
;
371 elt
->dup_blocks
[1] = NULL
;
372 elt
->incoming_edges
= NULL
;
374 slot
= redirection_data
->find_slot (elt
, insert
);
376 /* This will only happen if INSERT is false and the entry is not
377 in the hash table. */
384 /* This will only happen if E was not in the hash table and
389 elt
->incoming_edges
= XNEW (struct el
);
390 elt
->incoming_edges
->e
= e
;
391 elt
->incoming_edges
->next
= NULL
;
394 /* E was in the hash table. */
397 /* Free ELT as we do not need it anymore, we will extract the
398 relevant entry from the hash table itself. */
401 /* Get the entry stored in the hash table. */
404 /* If insertion was requested, then we need to add INCOMING_EDGE
405 to the list of incoming edges associated with E. */
408 struct el
*el
= XNEW (struct el
);
409 el
->next
= elt
->incoming_edges
;
411 elt
->incoming_edges
= el
;
418 /* Similar to copy_phi_args, except that the PHI arg exists, it just
419 does not have a value associated with it. */
422 copy_phi_arg_into_existing_phi (edge src_e
, edge tgt_e
)
424 int src_idx
= src_e
->dest_idx
;
425 int tgt_idx
= tgt_e
->dest_idx
;
427 /* Iterate over each PHI in e->dest. */
428 for (gphi_iterator gsi
= gsi_start_phis (src_e
->dest
),
429 gsi2
= gsi_start_phis (tgt_e
->dest
);
431 gsi_next (&gsi
), gsi_next (&gsi2
))
433 gphi
*src_phi
= gsi
.phi ();
434 gphi
*dest_phi
= gsi2
.phi ();
435 tree val
= gimple_phi_arg_def (src_phi
, src_idx
);
436 source_location locus
= gimple_phi_arg_location (src_phi
, src_idx
);
438 SET_PHI_ARG_DEF (dest_phi
, tgt_idx
, val
);
439 gimple_phi_arg_set_location (dest_phi
, tgt_idx
, locus
);
443 /* Given ssa_name DEF, backtrack jump threading PATH from node IDX
444 to see if it has constant value in a flow sensitive manner. Set
445 LOCUS to location of the constant phi arg and return the value.
446 Return DEF directly if either PATH or idx is ZERO. */
449 get_value_locus_in_path (tree def
, vec
<jump_thread_edge
*> *path
,
450 basic_block bb
, int idx
, source_location
*locus
)
456 if (path
== NULL
|| idx
== 0)
459 def_phi
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (def
));
463 def_bb
= gimple_bb (def_phi
);
464 /* Don't propagate loop invariants into deeper loops. */
465 if (!def_bb
|| bb_loop_depth (def_bb
) < bb_loop_depth (bb
))
468 /* Backtrack jump threading path from IDX to see if def has constant
470 for (int j
= idx
- 1; j
>= 0; j
--)
472 edge e
= (*path
)[j
]->e
;
473 if (e
->dest
== def_bb
)
475 arg
= gimple_phi_arg_def (def_phi
, e
->dest_idx
);
476 if (is_gimple_min_invariant (arg
))
478 *locus
= gimple_phi_arg_location (def_phi
, e
->dest_idx
);
488 /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
489 Try to backtrack jump threading PATH from node IDX to see if the arg
490 has constant value, copy constant value instead of argument itself
494 copy_phi_args (basic_block bb
, edge src_e
, edge tgt_e
,
495 vec
<jump_thread_edge
*> *path
, int idx
)
498 int src_indx
= src_e
->dest_idx
;
500 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
502 gphi
*phi
= gsi
.phi ();
503 tree def
= gimple_phi_arg_def (phi
, src_indx
);
504 source_location locus
= gimple_phi_arg_location (phi
, src_indx
);
506 if (TREE_CODE (def
) == SSA_NAME
507 && !virtual_operand_p (gimple_phi_result (phi
)))
508 def
= get_value_locus_in_path (def
, path
, bb
, idx
, &locus
);
510 add_phi_arg (phi
, def
, tgt_e
, locus
);
514 /* We have recently made a copy of ORIG_BB, including its outgoing
515 edges. The copy is NEW_BB. Every PHI node in every direct successor of
516 ORIG_BB has a new argument associated with edge from NEW_BB to the
517 successor. Initialize the PHI argument so that it is equal to the PHI
518 argument associated with the edge from ORIG_BB to the successor.
519 PATH and IDX are used to check if the new PHI argument has constant
520 value in a flow sensitive manner. */
523 update_destination_phis (basic_block orig_bb
, basic_block new_bb
,
524 vec
<jump_thread_edge
*> *path
, int idx
)
529 FOR_EACH_EDGE (e
, ei
, orig_bb
->succs
)
531 edge e2
= find_edge (new_bb
, e
->dest
);
532 copy_phi_args (e
->dest
, e
, e2
, path
, idx
);
536 /* Given a duplicate block and its single destination (both stored
537 in RD). Create an edge between the duplicate and its single
540 Add an additional argument to any PHI nodes at the single
541 destination. IDX is the start node in jump threading path
542 we start to check to see if the new PHI argument has constant
543 value along the jump threading path. */
546 create_edge_and_update_destination_phis (struct redirection_data
*rd
,
547 basic_block bb
, int idx
)
549 edge e
= make_edge (bb
, rd
->path
->last ()->e
->dest
, EDGE_FALLTHRU
);
551 rescan_loop_exit (e
, true, false);
552 e
->probability
= REG_BR_PROB_BASE
;
553 e
->count
= bb
->count
;
555 /* We used to copy the thread path here. That was added in 2007
556 and dutifully updated through the representation changes in 2013.
558 In 2013 we added code to thread from an interior node through
559 the backedge to another interior node. That runs after the code
560 to thread through loop headers from outside the loop.
562 The latter may delete edges in the CFG, including those
563 which appeared in the jump threading path we copied here. Thus
564 we'd end up using a dangling pointer.
566 After reviewing the 2007/2011 code, I can't see how anything
567 depended on copying the AUX field and clearly copying the jump
568 threading path is problematical due to embedded edge pointers.
569 It has been removed. */
572 /* If there are any PHI nodes at the destination of the outgoing edge
573 from the duplicate block, then we will need to add a new argument
574 to them. The argument should have the same value as the argument
575 associated with the outgoing edge stored in RD. */
576 copy_phi_args (e
->dest
, rd
->path
->last ()->e
, e
, rd
->path
, idx
);
579 /* Look through PATH beginning at START and return TRUE if there are
580 any additional blocks that need to be duplicated. Otherwise,
583 any_remaining_duplicated_blocks (vec
<jump_thread_edge
*> *path
,
586 for (unsigned int i
= start
+ 1; i
< path
->length (); i
++)
588 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
589 || (*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
)
596 /* Compute the amount of profile count/frequency coming into the jump threading
597 path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
598 PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
599 duplicated path, returned in PATH_OUT_COUNT_PTR. LOCAL_INFO is used to
600 identify blocks duplicated for jump threading, which have duplicated
601 edges that need to be ignored in the analysis. Return true if path contains
602 a joiner, false otherwise.
604 In the non-joiner case, this is straightforward - all the counts/frequency
605 flowing into the jump threading path should flow through the duplicated
606 block and out of the duplicated path.
608 In the joiner case, it is very tricky. Some of the counts flowing into
609 the original path go offpath at the joiner. The problem is that while
610 we know how much total count goes off-path in the original control flow,
611 we don't know how many of the counts corresponding to just the jump
612 threading path go offpath at the joiner.
614 For example, assume we have the following control flow and identified
615 jump threading paths:
634 Jump threading paths: A -> J -> Son -> D (path 1)
635 C -> J -> Son -> E (path 2)
637 Note that the control flow could be more complicated:
638 - Each jump threading path may have more than one incoming edge. I.e. A and
639 Ea could represent multiple incoming blocks/edges that are included in
641 - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
642 before or after the "normal" copy block). These are not duplicated onto
643 the jump threading path, as they are single-successor.
644 - Any of the blocks along the path may have other incoming edges that
645 are not part of any jump threading path, but add profile counts along
648 In the above example, after all jump threading is complete, we will
649 end up with the following control flow:
658 Eona/ \ ---/---\-------- \Eonc
663 \___________ / \ _____/
668 The main issue to notice here is that when we are processing path 1
669 (A->J->Son->D) we need to figure out the outgoing edge weights to
670 the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
671 sum of the incoming weights to D remain Ed. The problem with simply
672 assuming that Ja (and Jc when processing path 2) has the same outgoing
673 probabilities to its successors as the original block J, is that after
674 all paths are processed and other edges/counts removed (e.g. none
675 of Ec will reach D after processing path 2), we may end up with not
676 enough count flowing along duplicated edge Sona->D.
678 Therefore, in the case of a joiner, we keep track of all counts
679 coming in along the current path, as well as from predecessors not
680 on any jump threading path (Eb in the above example). While we
681 first assume that the duplicated Eona for Ja->Sona has the same
682 probability as the original, we later compensate for other jump
683 threading paths that may eliminate edges. We do that by keep track
684 of all counts coming into the original path that are not in a jump
685 thread (Eb in the above example, but as noted earlier, there could
686 be other predecessors incoming to the path at various points, such
687 as at Son). Call this cumulative non-path count coming into the path
688 before D as Enonpath. We then ensure that the count from Sona->D is as at
689 least as big as (Ed - Enonpath), but no bigger than the minimum
690 weight along the jump threading path. The probabilities of both the
691 original and duplicated joiner block J and Ja will be adjusted
692 accordingly after the updates. */
695 compute_path_counts (struct redirection_data
*rd
,
696 ssa_local_info_t
*local_info
,
697 profile_count
*path_in_count_ptr
,
698 profile_count
*path_out_count_ptr
,
699 int *path_in_freq_ptr
)
701 edge e
= rd
->incoming_edges
->e
;
702 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
703 edge elast
= path
->last ()->e
;
704 profile_count nonpath_count
= profile_count::zero ();
705 bool has_joiner
= false;
706 profile_count path_in_count
= profile_count::zero ();
707 int path_in_freq
= 0;
709 /* Start by accumulating incoming edge counts to the path's first bb
710 into a couple buckets:
711 path_in_count: total count of incoming edges that flow into the
713 nonpath_count: total count of incoming edges that are not
714 flowing along *any* path. These are the counts
715 that will still flow along the original path after
716 all path duplication is done by potentially multiple
717 calls to this routine.
718 (any other incoming edge counts are for a different jump threading
719 path that will be handled by a later call to this routine.)
720 To make this easier, start by recording all incoming edges that flow into
721 the current path in a bitmap. We could add up the path's incoming edge
722 counts here, but we still need to walk all the first bb's incoming edges
723 below to add up the counts of the other edges not included in this jump
725 struct el
*next
, *el
;
726 auto_bitmap in_edge_srcs
;
727 for (el
= rd
->incoming_edges
; el
; el
= next
)
730 bitmap_set_bit (in_edge_srcs
, el
->e
->src
->index
);
734 FOR_EACH_EDGE (ein
, ei
, e
->dest
->preds
)
736 vec
<jump_thread_edge
*> *ein_path
= THREAD_PATH (ein
);
737 /* Simply check the incoming edge src against the set captured above. */
739 && bitmap_bit_p (in_edge_srcs
, (*ein_path
)[0]->e
->src
->index
))
741 /* It is necessary but not sufficient that the last path edges
742 are identical. There may be different paths that share the
743 same last path edge in the case where the last edge has a nocopy
745 gcc_assert (ein_path
->last ()->e
== elast
);
746 path_in_count
+= ein
->count
;
747 path_in_freq
+= EDGE_FREQUENCY (ein
);
751 /* Keep track of the incoming edges that are not on any jump-threading
752 path. These counts will still flow out of original path after all
753 jump threading is complete. */
754 nonpath_count
+= ein
->count
;
758 /* This is needed due to insane incoming frequencies. */
759 if (path_in_freq
> BB_FREQ_MAX
)
760 path_in_freq
= BB_FREQ_MAX
;
762 /* Now compute the fraction of the total count coming into the first
763 path bb that is from the current threading path. */
764 profile_count total_count
= e
->dest
->count
;
765 /* Handle incoming profile insanities. */
766 if (total_count
< path_in_count
)
767 path_in_count
= total_count
;
768 int onpath_scale
= path_in_count
.probability_in (total_count
);
770 /* Walk the entire path to do some more computation in order to estimate
771 how much of the path_in_count will flow out of the duplicated threading
772 path. In the non-joiner case this is straightforward (it should be
773 the same as path_in_count, although we will handle incoming profile
774 insanities by setting it equal to the minimum count along the path).
776 In the joiner case, we need to estimate how much of the path_in_count
777 will stay on the threading path after the joiner's conditional branch.
778 We don't really know for sure how much of the counts
779 associated with this path go to each successor of the joiner, but we'll
780 estimate based on the fraction of the total count coming into the path
781 bb was from the threading paths (computed above in onpath_scale).
782 Afterwards, we will need to do some fixup to account for other threading
783 paths and possible profile insanities.
785 In order to estimate the joiner case's counts we also need to update
786 nonpath_count with any additional counts coming into the path. Other
787 blocks along the path may have additional predecessors from outside
789 profile_count path_out_count
= path_in_count
;
790 profile_count min_path_count
= path_in_count
;
791 for (unsigned int i
= 1; i
< path
->length (); i
++)
793 edge epath
= (*path
)[i
]->e
;
794 profile_count cur_count
= epath
->count
;
795 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
798 cur_count
= cur_count
.apply_probability (onpath_scale
);
800 /* In the joiner case we need to update nonpath_count for any edges
801 coming into the path that will contribute to the count flowing
802 into the path successor. */
803 if (has_joiner
&& epath
!= elast
)
805 /* Look for other incoming edges after joiner. */
806 FOR_EACH_EDGE (ein
, ei
, epath
->dest
->preds
)
809 /* Ignore in edges from blocks we have duplicated for a
810 threading path, which have duplicated edge counts until
811 they are redirected by an invocation of this routine. */
812 && !bitmap_bit_p (local_info
->duplicate_blocks
,
814 nonpath_count
+= ein
->count
;
817 if (cur_count
< path_out_count
)
818 path_out_count
= cur_count
;
819 if (epath
->count
< min_path_count
)
820 min_path_count
= epath
->count
;
823 /* We computed path_out_count above assuming that this path targeted
824 the joiner's on-path successor with the same likelihood as it
825 reached the joiner. However, other thread paths through the joiner
826 may take a different path through the normal copy source block
827 (i.e. they have a different elast), meaning that they do not
828 contribute any counts to this path's elast. As a result, it may
829 turn out that this path must have more count flowing to the on-path
830 successor of the joiner. Essentially, all of this path's elast
831 count must be contributed by this path and any nonpath counts
832 (since any path through the joiner with a different elast will not
833 include a copy of this elast in its duplicated path).
834 So ensure that this path's path_out_count is at least the
835 difference between elast->count and nonpath_count. Otherwise the edge
836 counts after threading will not be sane. */
837 if (local_info
->need_profile_correction
838 && has_joiner
&& path_out_count
< elast
->count
- nonpath_count
)
840 path_out_count
= elast
->count
- nonpath_count
;
841 /* But neither can we go above the minimum count along the path
842 we are duplicating. This can be an issue due to profile
843 insanities coming in to this pass. */
844 if (path_out_count
> min_path_count
)
845 path_out_count
= min_path_count
;
848 *path_in_count_ptr
= path_in_count
;
849 *path_out_count_ptr
= path_out_count
;
850 *path_in_freq_ptr
= path_in_freq
;
855 /* Update the counts and frequencies for both an original path
856 edge EPATH and its duplicate EDUP. The duplicate source block
857 will get a count/frequency of PATH_IN_COUNT and PATH_IN_FREQ,
858 and the duplicate edge EDUP will have a count of PATH_OUT_COUNT. */
860 update_profile (edge epath
, edge edup
, profile_count path_in_count
,
861 profile_count path_out_count
, int path_in_freq
)
864 /* First update the duplicated block's count / frequency. */
867 basic_block dup_block
= edup
->src
;
868 gcc_assert (!dup_block
->count
.initialized_p ());
869 gcc_assert (dup_block
->frequency
== 0);
870 dup_block
->count
= path_in_count
;
871 dup_block
->frequency
= path_in_freq
;
874 /* Now update the original block's count and frequency in the
875 opposite manner - remove the counts/freq that will flow
876 into the duplicated block. Handle underflow due to precision/
878 epath
->src
->count
-= path_in_count
;
879 epath
->src
->frequency
-= path_in_freq
;
880 if (epath
->src
->frequency
< 0)
881 epath
->src
->frequency
= 0;
883 /* Next update this path edge's original and duplicated counts. We know
884 that the duplicated path will have path_out_count flowing
885 out of it (in the joiner case this is the count along the duplicated path
886 out of the duplicated joiner). This count can then be removed from the
887 original path edge. */
889 edup
->count
= path_out_count
;
890 epath
->count
-= path_out_count
;
891 /* FIXME: can epath->count be legally uninitialized here? */
895 /* The duplicate and original joiner blocks may end up with different
896 probabilities (different from both the original and from each other).
897 Recompute the probabilities here once we have updated the edge
898 counts and frequencies. */
901 recompute_probabilities (basic_block bb
)
905 FOR_EACH_EDGE (esucc
, ei
, bb
->succs
)
907 if (!(bb
->count
> 0))
910 /* Prevent overflow computation due to insane profiles. */
911 if (esucc
->count
< bb
->count
)
912 esucc
->probability
= esucc
->count
.probability_in (bb
->count
);
914 /* Can happen with missing/guessed probabilities, since we
915 may determine that more is flowing along duplicated
916 path than joiner succ probabilities allowed.
917 Counts and freqs will be insane after jump threading,
918 at least make sure probability is sane or we will
919 get a flow verification error.
920 Not much we can do to make counts/freqs sane without
921 redoing the profile estimation. */
922 esucc
->probability
= REG_BR_PROB_BASE
;
927 /* Update the counts of the original and duplicated edges from a joiner
928 that go off path, given that we have already determined that the
929 duplicate joiner DUP_BB has incoming count PATH_IN_COUNT and
930 outgoing count along the path PATH_OUT_COUNT. The original (on-)path
931 edge from joiner is EPATH. */
934 update_joiner_offpath_counts (edge epath
, basic_block dup_bb
,
935 profile_count path_in_count
,
936 profile_count path_out_count
)
938 /* Compute the count that currently flows off path from the joiner.
939 In other words, the total count of joiner's out edges other than
940 epath. Compute this by walking the successors instead of
941 subtracting epath's count from the joiner bb count, since there
942 are sometimes slight insanities where the total out edge count is
943 larger than the bb count (possibly due to rounding/truncation
945 profile_count total_orig_off_path_count
= profile_count::zero ();
948 FOR_EACH_EDGE (enonpath
, ei
, epath
->src
->succs
)
950 if (enonpath
== epath
)
952 total_orig_off_path_count
+= enonpath
->count
;
955 /* For the path that we are duplicating, the amount that will flow
956 off path from the duplicated joiner is the delta between the
957 path's cumulative in count and the portion of that count we
958 estimated above as flowing from the joiner along the duplicated
960 profile_count total_dup_off_path_count
= path_in_count
- path_out_count
;
962 /* Now do the actual updates of the off-path edges. */
963 FOR_EACH_EDGE (enonpath
, ei
, epath
->src
->succs
)
965 /* Look for edges going off of the threading path. */
966 if (enonpath
== epath
)
969 /* Find the corresponding edge out of the duplicated joiner. */
970 edge enonpathdup
= find_edge (dup_bb
, enonpath
->dest
);
971 gcc_assert (enonpathdup
);
973 /* We can't use the original probability of the joiner's out
974 edges, since the probabilities of the original branch
975 and the duplicated branches may vary after all threading is
976 complete. But apportion the duplicated joiner's off-path
977 total edge count computed earlier (total_dup_off_path_count)
978 among the duplicated off-path edges based on their original
979 ratio to the full off-path count (total_orig_off_path_count).
981 int scale
= enonpath
->count
.probability_in (total_orig_off_path_count
);
982 /* Give the duplicated offpath edge a portion of the duplicated
984 enonpathdup
->count
= total_dup_off_path_count
.apply_probability (scale
);
985 /* Now update the original offpath edge count, handling underflow
986 due to rounding errors. */
987 enonpath
->count
-= enonpathdup
->count
;
992 /* Check if the paths through RD all have estimated frequencies but zero
993 profile counts. This is more accurate than checking the entry block
994 for a zero profile count, since profile insanities sometimes creep in. */
997 estimated_freqs_path (struct redirection_data
*rd
)
999 edge e
= rd
->incoming_edges
->e
;
1000 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1003 bool non_zero_freq
= false;
1004 FOR_EACH_EDGE (ein
, ei
, e
->dest
->preds
)
1008 non_zero_freq
|= ein
->src
->frequency
!= 0;
1011 for (unsigned int i
= 1; i
< path
->length (); i
++)
1013 edge epath
= (*path
)[i
]->e
;
1014 if (epath
->src
->count
> 0)
1016 non_zero_freq
|= epath
->src
->frequency
!= 0;
1018 FOR_EACH_EDGE (esucc
, ei
, epath
->src
->succs
)
1020 if (esucc
->count
> 0)
1022 non_zero_freq
|= esucc
->src
->frequency
!= 0;
1025 return non_zero_freq
;
1029 /* Invoked for routines that have guessed frequencies and no profile
1030 counts to record the block and edge frequencies for paths through RD
1031 in the profile count fields of those blocks and edges. This is because
1032 ssa_fix_duplicate_block_edges incrementally updates the block and
1033 edge counts as edges are redirected, and it is difficult to do that
1034 for edge frequencies which are computed on the fly from the source
1035 block frequency and probability. When a block frequency is updated
1036 its outgoing edge frequencies are affected and become difficult to
1040 freqs_to_counts_path (struct redirection_data
*rd
)
1042 edge e
= rd
->incoming_edges
->e
;
1043 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1046 FOR_EACH_EDGE (ein
, ei
, e
->dest
->preds
)
1048 /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
1049 errors applying the probability when the frequencies are very
1051 ein
->count
= profile_count::from_gcov_type
1052 (apply_probability (ein
->src
->frequency
* REG_BR_PROB_BASE
,
1056 for (unsigned int i
= 1; i
< path
->length (); i
++)
1058 edge epath
= (*path
)[i
]->e
;
1060 /* Scale up the frequency by REG_BR_PROB_BASE, to avoid rounding
1061 errors applying the edge probability when the frequencies are very
1064 profile_count::from_gcov_type
1065 (epath
->src
->frequency
* REG_BR_PROB_BASE
);
1066 FOR_EACH_EDGE (esucc
, ei
, epath
->src
->succs
)
1068 esucc
->src
->count
.apply_probability (esucc
->probability
);
1073 /* For routines that have guessed frequencies and no profile counts, where we
1074 used freqs_to_counts_path to record block and edge frequencies for paths
1075 through RD, we clear the counts after completing all updates for RD.
1076 The updates in ssa_fix_duplicate_block_edges are based off the count fields,
1077 but the block frequencies and edge probabilities were updated as well,
1078 so we can simply clear the count fields. */
1081 clear_counts_path (struct redirection_data
*rd
)
1083 edge e
= rd
->incoming_edges
->e
;
1084 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1087 FOR_EACH_EDGE (ein
, ei
, e
->dest
->preds
)
1088 ein
->count
= profile_count::uninitialized ();
1090 /* First clear counts along original path. */
1091 for (unsigned int i
= 1; i
< path
->length (); i
++)
1093 edge epath
= (*path
)[i
]->e
;
1094 FOR_EACH_EDGE (esucc
, ei
, epath
->src
->succs
)
1095 esucc
->count
= profile_count::uninitialized ();
1096 epath
->src
->count
= profile_count::uninitialized ();
1098 /* Also need to clear the counts along duplicated path. */
1099 for (unsigned int i
= 0; i
< 2; i
++)
1101 basic_block dup
= rd
->dup_blocks
[i
];
1104 FOR_EACH_EDGE (esucc
, ei
, dup
->succs
)
1105 esucc
->count
= profile_count::uninitialized ();
1106 dup
->count
= profile_count::uninitialized ();
1110 /* Wire up the outgoing edges from the duplicate blocks and
1111 update any PHIs as needed. Also update the profile counts
1112 on the original and duplicate blocks and edges. */
1114 ssa_fix_duplicate_block_edges (struct redirection_data
*rd
,
1115 ssa_local_info_t
*local_info
)
1117 bool multi_incomings
= (rd
->incoming_edges
->next
!= NULL
);
1118 edge e
= rd
->incoming_edges
->e
;
1119 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1120 edge elast
= path
->last ()->e
;
1121 profile_count path_in_count
= profile_count::zero ();
1122 profile_count path_out_count
= profile_count::zero ();
1123 int path_in_freq
= 0;
1125 /* This routine updates profile counts, frequencies, and probabilities
1126 incrementally. Since it is difficult to do the incremental updates
1127 using frequencies/probabilities alone, for routines without profile
1128 data we first take a snapshot of the existing block and edge frequencies
1129 by copying them into the empty profile count fields. These counts are
1130 then used to do the incremental updates, and cleared at the end of this
1131 routine. If the function is marked as having a profile, we still check
1132 to see if the paths through RD are using estimated frequencies because
1133 the routine had zero profile counts. */
1134 bool do_freqs_to_counts
= (profile_status_for_fn (cfun
) != PROFILE_READ
1135 || estimated_freqs_path (rd
));
1136 if (do_freqs_to_counts
)
1137 freqs_to_counts_path (rd
);
1139 /* First determine how much profile count to move from original
1140 path to the duplicate path. This is tricky in the presence of
1141 a joiner (see comments for compute_path_counts), where some portion
1142 of the path's counts will flow off-path from the joiner. In the
1143 non-joiner case the path_in_count and path_out_count should be the
1145 bool has_joiner
= compute_path_counts (rd
, local_info
,
1146 &path_in_count
, &path_out_count
,
1149 int cur_path_freq
= path_in_freq
;
1150 for (unsigned int count
= 0, i
= 1; i
< path
->length (); i
++)
1152 edge epath
= (*path
)[i
]->e
;
1154 /* If we were threading through an joiner block, then we want
1155 to keep its control statement and redirect an outgoing edge.
1156 Else we want to remove the control statement & edges, then create
1157 a new outgoing edge. In both cases we may need to update PHIs. */
1158 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1163 gcc_assert (has_joiner
);
1165 /* This updates the PHIs at the destination of the duplicate
1166 block. Pass 0 instead of i if we are threading a path which
1167 has multiple incoming edges. */
1168 update_destination_phis (local_info
->bb
, rd
->dup_blocks
[count
],
1169 path
, multi_incomings
? 0 : i
);
1171 /* Find the edge from the duplicate block to the block we're
1172 threading through. That's the edge we want to redirect. */
1173 victim
= find_edge (rd
->dup_blocks
[count
], (*path
)[i
]->e
->dest
);
1175 /* If there are no remaining blocks on the path to duplicate,
1176 then redirect VICTIM to the final destination of the jump
1178 if (!any_remaining_duplicated_blocks (path
, i
))
1180 e2
= redirect_edge_and_branch (victim
, elast
->dest
);
1181 /* If we redirected the edge, then we need to copy PHI arguments
1182 at the target. If the edge already existed (e2 != victim
1183 case), then the PHIs in the target already have the correct
1186 copy_phi_args (e2
->dest
, elast
, e2
,
1187 path
, multi_incomings
? 0 : i
);
1191 /* Redirect VICTIM to the next duplicated block in the path. */
1192 e2
= redirect_edge_and_branch (victim
, rd
->dup_blocks
[count
+ 1]);
1194 /* We need to update the PHIs in the next duplicated block. We
1195 want the new PHI args to have the same value as they had
1196 in the source of the next duplicate block.
1198 Thus, we need to know which edge we traversed into the
1199 source of the duplicate. Furthermore, we may have
1200 traversed many edges to reach the source of the duplicate.
1202 Walk through the path starting at element I until we
1203 hit an edge marked with EDGE_COPY_SRC_BLOCK. We want
1204 the edge from the prior element. */
1205 for (unsigned int j
= i
+ 1; j
< path
->length (); j
++)
1207 if ((*path
)[j
]->type
== EDGE_COPY_SRC_BLOCK
)
1209 copy_phi_arg_into_existing_phi ((*path
)[j
- 1]->e
, e2
);
1215 /* Update the counts and frequency of both the original block
1216 and path edge, and the duplicates. The path duplicate's
1217 incoming count and frequency are the totals for all edges
1218 incoming to this jump threading path computed earlier.
1219 And we know that the duplicated path will have path_out_count
1220 flowing out of it (i.e. along the duplicated path out of the
1221 duplicated joiner). */
1222 update_profile (epath
, e2
, path_in_count
, path_out_count
,
1225 /* Next we need to update the counts of the original and duplicated
1226 edges from the joiner that go off path. */
1227 update_joiner_offpath_counts (epath
, e2
->src
, path_in_count
,
1230 /* Finally, we need to set the probabilities on the duplicated
1231 edges out of the duplicated joiner (e2->src). The probabilities
1232 along the original path will all be updated below after we finish
1233 processing the whole path. */
1234 recompute_probabilities (e2
->src
);
1236 /* Record the frequency flowing to the downstream duplicated
1238 cur_path_freq
= EDGE_FREQUENCY (e2
);
1240 else if ((*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
)
1242 remove_ctrl_stmt_and_useless_edges (rd
->dup_blocks
[count
], NULL
);
1243 create_edge_and_update_destination_phis (rd
, rd
->dup_blocks
[count
],
1244 multi_incomings
? 0 : i
);
1246 single_succ_edge (rd
->dup_blocks
[1])->aux
= NULL
;
1248 /* Update the counts and frequency of both the original block
1249 and path edge, and the duplicates. Since we are now after
1250 any joiner that may have existed on the path, the count
1251 flowing along the duplicated threaded path is path_out_count.
1252 If we didn't have a joiner, then cur_path_freq was the sum
1253 of the total frequencies along all incoming edges to the
1254 thread path (path_in_freq). If we had a joiner, it would have
1255 been updated at the end of that handling to the edge frequency
1256 along the duplicated joiner path edge. */
1257 update_profile (epath
, EDGE_SUCC (rd
->dup_blocks
[count
], 0),
1258 path_out_count
, path_out_count
,
1263 /* No copy case. In this case we don't have an equivalent block
1264 on the duplicated thread path to update, but we do need
1265 to remove the portion of the counts/freqs that were moved
1266 to the duplicated path from the counts/freqs flowing through
1267 this block on the original path. Since all the no-copy edges
1268 are after any joiner, the removed count is the same as
1271 If we didn't have a joiner, then cur_path_freq was the sum
1272 of the total frequencies along all incoming edges to the
1273 thread path (path_in_freq). If we had a joiner, it would have
1274 been updated at the end of that handling to the edge frequency
1275 along the duplicated joiner path edge. */
1276 update_profile (epath
, NULL
, path_out_count
, path_out_count
,
1280 /* Increment the index into the duplicated path when we processed
1281 a duplicated block. */
1282 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
1283 || (*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
)
1289 /* Now walk orig blocks and update their probabilities, since the
1290 counts and freqs should be updated properly by above loop. */
1291 for (unsigned int i
= 1; i
< path
->length (); i
++)
1293 edge epath
= (*path
)[i
]->e
;
1294 recompute_probabilities (epath
->src
);
1297 /* Done with all profile and frequency updates, clear counts if they
1299 if (do_freqs_to_counts
)
1300 clear_counts_path (rd
);
1303 /* Hash table traversal callback routine to create duplicate blocks. */
1306 ssa_create_duplicates (struct redirection_data
**slot
,
1307 ssa_local_info_t
*local_info
)
1309 struct redirection_data
*rd
= *slot
;
1311 /* The second duplicated block in a jump threading path is specific
1312 to the path. So it gets stored in RD rather than in LOCAL_DATA.
1314 Each time we're called, we have to look through the path and see
1315 if a second block needs to be duplicated.
1317 Note the search starts with the third edge on the path. The first
1318 edge is the incoming edge, the second edge always has its source
1319 duplicated. Thus we start our search with the third edge. */
1320 vec
<jump_thread_edge
*> *path
= rd
->path
;
1321 for (unsigned int i
= 2; i
< path
->length (); i
++)
1323 if ((*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
1324 || (*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1326 create_block_for_threading ((*path
)[i
]->e
->src
, rd
, 1,
1327 &local_info
->duplicate_blocks
);
1332 /* Create a template block if we have not done so already. Otherwise
1333 use the template to create a new block. */
1334 if (local_info
->template_block
== NULL
)
1336 create_block_for_threading ((*path
)[1]->e
->src
, rd
, 0,
1337 &local_info
->duplicate_blocks
);
1338 local_info
->template_block
= rd
->dup_blocks
[0];
1340 /* We do not create any outgoing edges for the template. We will
1341 take care of that in a later traversal. That way we do not
1342 create edges that are going to just be deleted. */
1346 create_block_for_threading (local_info
->template_block
, rd
, 0,
1347 &local_info
->duplicate_blocks
);
1349 /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
1351 ssa_fix_duplicate_block_edges (rd
, local_info
);
1354 /* Keep walking the hash table. */
1358 /* We did not create any outgoing edges for the template block during
1359 block creation. This hash table traversal callback creates the
1360 outgoing edge for the template block. */
1363 ssa_fixup_template_block (struct redirection_data
**slot
,
1364 ssa_local_info_t
*local_info
)
1366 struct redirection_data
*rd
= *slot
;
1368 /* If this is the template block halt the traversal after updating
1371 If we were threading through an joiner block, then we want
1372 to keep its control statement and redirect an outgoing edge.
1373 Else we want to remove the control statement & edges, then create
1374 a new outgoing edge. In both cases we may need to update PHIs. */
1375 if (rd
->dup_blocks
[0] && rd
->dup_blocks
[0] == local_info
->template_block
)
1377 ssa_fix_duplicate_block_edges (rd
, local_info
);
1384 /* Hash table traversal callback to redirect each incoming edge
1385 associated with this hash table element to its new destination. */
1388 ssa_redirect_edges (struct redirection_data
**slot
,
1389 ssa_local_info_t
*local_info
)
1391 struct redirection_data
*rd
= *slot
;
1392 struct el
*next
, *el
;
1394 /* Walk over all the incoming edges associated with this hash table
1396 for (el
= rd
->incoming_edges
; el
; el
= next
)
1399 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1401 /* Go ahead and free this element from the list. Doing this now
1402 avoids the need for another list walk when we destroy the hash
1407 thread_stats
.num_threaded_edges
++;
1409 if (rd
->dup_blocks
[0])
1413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1414 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
1415 e
->src
->index
, e
->dest
->index
, rd
->dup_blocks
[0]->index
);
1417 /* Redirect the incoming edge (possibly to the joiner block) to the
1418 appropriate duplicate block. */
1419 e2
= redirect_edge_and_branch (e
, rd
->dup_blocks
[0]);
1420 gcc_assert (e
== e2
);
1421 flush_pending_stmts (e2
);
1424 /* Go ahead and clear E->aux. It's not needed anymore and failure
1425 to clear it will cause all kinds of unpleasant problems later. */
1426 delete_jump_thread_path (path
);
1431 /* Indicate that we actually threaded one or more jumps. */
1432 if (rd
->incoming_edges
)
1433 local_info
->jumps_threaded
= true;
1438 /* Return true if this block has no executable statements other than
1439 a simple ctrl flow instruction. When the number of outgoing edges
1440 is one, this is equivalent to a "forwarder" block. */
1443 redirection_block_p (basic_block bb
)
1445 gimple_stmt_iterator gsi
;
1447 /* Advance to the first executable statement. */
1448 gsi
= gsi_start_bb (bb
);
1449 while (!gsi_end_p (gsi
)
1450 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_LABEL
1451 || is_gimple_debug (gsi_stmt (gsi
))
1452 || gimple_nop_p (gsi_stmt (gsi
))
1453 || gimple_clobber_p (gsi_stmt (gsi
))))
1456 /* Check if this is an empty block. */
1457 if (gsi_end_p (gsi
))
1460 /* Test that we've reached the terminating control statement. */
1461 return gsi_stmt (gsi
)
1462 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
1463 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_GOTO
1464 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_SWITCH
);
1467 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
1468 is reached via one or more specific incoming edges, we know which
1469 outgoing edge from BB will be traversed.
1471 We want to redirect those incoming edges to the target of the
1472 appropriate outgoing edge. Doing so avoids a conditional branch
1473 and may expose new optimization opportunities. Note that we have
1474 to update dominator tree and SSA graph after such changes.
1476 The key to keeping the SSA graph update manageable is to duplicate
1477 the side effects occurring in BB so that those side effects still
1478 occur on the paths which bypass BB after redirecting edges.
1480 We accomplish this by creating duplicates of BB and arranging for
1481 the duplicates to unconditionally pass control to one specific
1482 successor of BB. We then revector the incoming edges into BB to
1483 the appropriate duplicate of BB.
1485 If NOLOOP_ONLY is true, we only perform the threading as long as it
1486 does not affect the structure of the loops in a nontrivial way.
1488 If JOINERS is true, then thread through joiner blocks as well. */
1491 thread_block_1 (basic_block bb
, bool noloop_only
, bool joiners
)
1493 /* E is an incoming edge into BB that we may or may not want to
1494 redirect to a duplicate of BB. */
1497 ssa_local_info_t local_info
;
1499 local_info
.duplicate_blocks
= BITMAP_ALLOC (NULL
);
1500 local_info
.need_profile_correction
= false;
1502 /* To avoid scanning a linear array for the element we need we instead
1503 use a hash table. For normal code there should be no noticeable
1504 difference. However, if we have a block with a large number of
1505 incoming and outgoing edges such linear searches can get expensive. */
1507 = new hash_table
<struct redirection_data
> (EDGE_COUNT (bb
->succs
));
1509 /* Record each unique threaded destination into a hash table for
1510 efficient lookups. */
1512 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1517 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1519 if (((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
&& !joiners
)
1520 || ((*path
)[1]->type
== EDGE_COPY_SRC_BLOCK
&& joiners
))
1523 e2
= path
->last ()->e
;
1524 if (!e2
|| noloop_only
)
1526 /* If NOLOOP_ONLY is true, we only allow threading through the
1527 header of a loop to exit edges. */
1529 /* One case occurs when there was loop header buried in a jump
1530 threading path that crosses loop boundaries. We do not try
1531 and thread this elsewhere, so just cancel the jump threading
1532 request by clearing the AUX field now. */
1533 if (bb
->loop_father
!= e2
->src
->loop_father
1534 && !loop_exit_edge_p (e2
->src
->loop_father
, e2
))
1536 /* Since this case is not handled by our special code
1537 to thread through a loop header, we must explicitly
1538 cancel the threading request here. */
1539 delete_jump_thread_path (path
);
1544 /* Another case occurs when trying to thread through our
1545 own loop header, possibly from inside the loop. We will
1546 thread these later. */
1548 for (i
= 1; i
< path
->length (); i
++)
1550 if ((*path
)[i
]->e
->src
== bb
->loop_father
->header
1551 && (!loop_exit_edge_p (bb
->loop_father
, e2
)
1552 || (*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
))
1556 if (i
!= path
->length ())
1560 /* Insert the outgoing edge into the hash table if it is not
1561 already in the hash table. */
1562 lookup_redirection_data (e
, INSERT
);
1564 /* When we have thread paths through a common joiner with different
1565 final destinations, then we may need corrections to deal with
1566 profile insanities. See the big comment before compute_path_counts. */
1567 if ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1571 else if (e2
!= last
)
1572 local_info
.need_profile_correction
= true;
1576 /* We do not update dominance info. */
1577 free_dominance_info (CDI_DOMINATORS
);
1579 /* We know we only thread through the loop header to loop exits.
1580 Let the basic block duplication hook know we are not creating
1581 a multiple entry loop. */
1583 && bb
== bb
->loop_father
->header
)
1584 set_loop_copy (bb
->loop_father
, loop_outer (bb
->loop_father
));
1586 /* Now create duplicates of BB.
1588 Note that for a block with a high outgoing degree we can waste
1589 a lot of time and memory creating and destroying useless edges.
1591 So we first duplicate BB and remove the control structure at the
1592 tail of the duplicate as well as all outgoing edges from the
1593 duplicate. We then use that duplicate block as a template for
1594 the rest of the duplicates. */
1595 local_info
.template_block
= NULL
;
1597 local_info
.jumps_threaded
= false;
1598 redirection_data
->traverse
<ssa_local_info_t
*, ssa_create_duplicates
>
1601 /* The template does not have an outgoing edge. Create that outgoing
1602 edge and update PHI nodes as the edge's target as necessary.
1604 We do this after creating all the duplicates to avoid creating
1605 unnecessary edges. */
1606 redirection_data
->traverse
<ssa_local_info_t
*, ssa_fixup_template_block
>
1609 /* The hash table traversals above created the duplicate blocks (and the
1610 statements within the duplicate blocks). This loop creates PHI nodes for
1611 the duplicated blocks and redirects the incoming edges into BB to reach
1612 the duplicates of BB. */
1613 redirection_data
->traverse
<ssa_local_info_t
*, ssa_redirect_edges
>
1616 /* Done with this block. Clear REDIRECTION_DATA. */
1617 delete redirection_data
;
1618 redirection_data
= NULL
;
1621 && bb
== bb
->loop_father
->header
)
1622 set_loop_copy (bb
->loop_father
, NULL
);
1624 BITMAP_FREE (local_info
.duplicate_blocks
);
1625 local_info
.duplicate_blocks
= NULL
;
1627 /* Indicate to our caller whether or not any jumps were threaded. */
1628 return local_info
.jumps_threaded
;
1631 /* Wrapper for thread_block_1 so that we can first handle jump
1632 thread paths which do not involve copying joiner blocks, then
1633 handle jump thread paths which have joiner blocks.
1635 By doing things this way we can be as aggressive as possible and
1636 not worry that copying a joiner block will create a jump threading
1640 thread_block (basic_block bb
, bool noloop_only
)
1643 retval
= thread_block_1 (bb
, noloop_only
, false);
1644 retval
|= thread_block_1 (bb
, noloop_only
, true);
1648 /* Callback for dfs_enumerate_from. Returns true if BB is different
1649 from STOP and DBDS_CE_STOP. */
1651 static basic_block dbds_ce_stop
;
1653 dbds_continue_enumeration_p (const_basic_block bb
, const void *stop
)
1655 return (bb
!= (const_basic_block
) stop
1656 && bb
!= dbds_ce_stop
);
1659 /* Evaluates the dominance relationship of latch of the LOOP and BB, and
1660 returns the state. */
1663 determine_bb_domination_status (struct loop
*loop
, basic_block bb
)
1665 basic_block
*bblocks
;
1666 unsigned nblocks
, i
;
1667 bool bb_reachable
= false;
1671 /* This function assumes BB is a successor of LOOP->header.
1672 If that is not the case return DOMST_NONDOMINATING which
1677 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1679 if (e
->src
== loop
->header
)
1687 return DOMST_NONDOMINATING
;
1690 if (bb
== loop
->latch
)
1691 return DOMST_DOMINATING
;
1693 /* Check that BB dominates LOOP->latch, and that it is back-reachable
1696 bblocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1697 dbds_ce_stop
= loop
->header
;
1698 nblocks
= dfs_enumerate_from (loop
->latch
, 1, dbds_continue_enumeration_p
,
1699 bblocks
, loop
->num_nodes
, bb
);
1700 for (i
= 0; i
< nblocks
; i
++)
1701 FOR_EACH_EDGE (e
, ei
, bblocks
[i
]->preds
)
1703 if (e
->src
== loop
->header
)
1706 return DOMST_NONDOMINATING
;
1709 bb_reachable
= true;
1713 return (bb_reachable
? DOMST_DOMINATING
: DOMST_LOOP_BROKEN
);
1716 /* Thread jumps through the header of LOOP. Returns true if cfg changes.
1717 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
1718 to the inside of the loop. */
1721 thread_through_loop_header (struct loop
*loop
, bool may_peel_loop_headers
)
1723 basic_block header
= loop
->header
;
1724 edge e
, tgt_edge
, latch
= loop_latch_edge (loop
);
1726 basic_block tgt_bb
, atgt_bb
;
1727 enum bb_dom_status domst
;
1729 /* We have already threaded through headers to exits, so all the threading
1730 requests now are to the inside of the loop. We need to avoid creating
1731 irreducible regions (i.e., loops with more than one entry block), and
1732 also loop with several latch edges, or new subloops of the loop (although
1733 there are cases where it might be appropriate, it is difficult to decide,
1734 and doing it wrongly may confuse other optimizers).
1736 We could handle more general cases here. However, the intention is to
1737 preserve some information about the loop, which is impossible if its
1738 structure changes significantly, in a way that is not well understood.
1739 Thus we only handle few important special cases, in which also updating
1740 of the loop-carried information should be feasible:
1742 1) Propagation of latch edge to a block that dominates the latch block
1743 of a loop. This aims to handle the following idiom:
1754 After threading the latch edge, this becomes
1765 The original header of the loop is moved out of it, and we may thread
1766 the remaining edges through it without further constraints.
1768 2) All entry edges are propagated to a single basic block that dominates
1769 the latch block of the loop. This aims to handle the following idiom
1770 (normally created for "for" loops):
1793 /* Threading through the header won't improve the code if the header has just
1795 if (single_succ_p (header
))
1798 if (!may_peel_loop_headers
&& !redirection_block_p (loop
->header
))
1804 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1811 /* If latch is not threaded, and there is a header
1812 edge that is not threaded, we would create loop
1813 with multiple entries. */
1817 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1819 if ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1821 tgt_edge
= (*path
)[1]->e
;
1822 atgt_bb
= tgt_edge
->dest
;
1825 /* Two targets of threading would make us create loop
1826 with multiple entries. */
1827 else if (tgt_bb
!= atgt_bb
)
1833 /* There are no threading requests. */
1837 /* Redirecting to empty loop latch is useless. */
1838 if (tgt_bb
== loop
->latch
1839 && empty_block_p (loop
->latch
))
1843 /* The target block must dominate the loop latch, otherwise we would be
1844 creating a subloop. */
1845 domst
= determine_bb_domination_status (loop
, tgt_bb
);
1846 if (domst
== DOMST_NONDOMINATING
)
1848 if (domst
== DOMST_LOOP_BROKEN
)
1850 /* If the loop ceased to exist, mark it as such, and thread through its
1852 mark_loop_for_removal (loop
);
1853 return thread_block (header
, false);
1856 if (tgt_bb
->loop_father
->header
== tgt_bb
)
1858 /* If the target of the threading is a header of a subloop, we need
1859 to create a preheader for it, so that the headers of the two loops
1861 if (EDGE_COUNT (tgt_bb
->preds
) > 2)
1863 tgt_bb
= create_preheader (tgt_bb
->loop_father
, 0);
1864 gcc_assert (tgt_bb
!= NULL
);
1867 tgt_bb
= split_edge (tgt_edge
);
1870 basic_block new_preheader
;
1872 /* Now consider the case entry edges are redirected to the new entry
1873 block. Remember one entry edge, so that we can find the new
1874 preheader (its destination after threading). */
1875 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1881 /* The duplicate of the header is the new preheader of the loop. Ensure
1882 that it is placed correctly in the loop hierarchy. */
1883 set_loop_copy (loop
, loop_outer (loop
));
1885 thread_block (header
, false);
1886 set_loop_copy (loop
, NULL
);
1887 new_preheader
= e
->dest
;
1889 /* Create the new latch block. This is always necessary, as the latch
1890 must have only a single successor, but the original header had at
1891 least two successors. */
1893 mfb_kj_edge
= single_succ_edge (new_preheader
);
1894 loop
->header
= mfb_kj_edge
->dest
;
1895 latch
= make_forwarder_block (tgt_bb
, mfb_keep_just
, NULL
);
1896 loop
->header
= latch
->dest
;
1897 loop
->latch
= latch
->src
;
1901 /* We failed to thread anything. Cancel the requests. */
1902 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1904 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1908 delete_jump_thread_path (path
);
1915 /* E1 and E2 are edges into the same basic block. Return TRUE if the
1916 PHI arguments associated with those edges are equal or there are no
1917 PHI arguments, otherwise return FALSE. */
1920 phi_args_equal_on_edges (edge e1
, edge e2
)
1923 int indx1
= e1
->dest_idx
;
1924 int indx2
= e2
->dest_idx
;
1926 for (gsi
= gsi_start_phis (e1
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1928 gphi
*phi
= gsi
.phi ();
1930 if (!operand_equal_p (gimple_phi_arg_def (phi
, indx1
),
1931 gimple_phi_arg_def (phi
, indx2
), 0))
1937 /* Walk through the registered jump threads and convert them into a
1938 form convenient for this pass.
1940 Any block which has incoming edges threaded to outgoing edges
1941 will have its entry in THREADED_BLOCK set.
1943 Any threaded edge will have its new outgoing edge stored in the
1944 original edge's AUX field.
1946 This form avoids the need to walk all the edges in the CFG to
1947 discover blocks which need processing and avoids unnecessary
1948 hash table lookups to map from threaded edge to new target. */
1951 mark_threaded_blocks (bitmap threaded_blocks
)
1960 /* It is possible to have jump threads in which one is a subpath
1961 of the other. ie, (A, B), (B, C), (C, D) where B is a joiner
1962 block and (B, C), (C, D) where no joiner block exists.
1964 When this occurs ignore the jump thread request with the joiner
1965 block. It's totally subsumed by the simpler jump thread request.
1967 This results in less block copying, simpler CFGs. More importantly,
1968 when we duplicate the joiner block, B, in this case we will create
1969 a new threading opportunity that we wouldn't be able to optimize
1970 until the next jump threading iteration.
1972 So first convert the jump thread requests which do not require a
1974 for (i
= 0; i
< paths
.length (); i
++)
1976 vec
<jump_thread_edge
*> *path
= paths
[i
];
1978 if ((*path
)[1]->type
!= EDGE_COPY_SRC_JOINER_BLOCK
)
1980 edge e
= (*path
)[0]->e
;
1981 e
->aux
= (void *)path
;
1982 bitmap_set_bit (tmp
, e
->dest
->index
);
1986 /* Now iterate again, converting cases where we want to thread
1987 through a joiner block, but only if no other edge on the path
1988 already has a jump thread attached to it. We do this in two passes,
1989 to avoid situations where the order in the paths vec can hide overlapping
1990 threads (the path is recorded on the incoming edge, so we would miss
1991 cases where the second path starts at a downstream edge on the same
1992 path). First record all joiner paths, deleting any in the unexpected
1993 case where there is already a path for that incoming edge. */
1994 for (i
= 0; i
< paths
.length ();)
1996 vec
<jump_thread_edge
*> *path
= paths
[i
];
1998 if ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
2000 /* Attach the path to the starting edge if none is yet recorded. */
2001 if ((*path
)[0]->e
->aux
== NULL
)
2003 (*path
)[0]->e
->aux
= path
;
2008 paths
.unordered_remove (i
);
2009 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2010 dump_jump_thread_path (dump_file
, *path
, false);
2011 delete_jump_thread_path (path
);
2020 /* Second, look for paths that have any other jump thread attached to
2021 them, and either finish converting them or cancel them. */
2022 for (i
= 0; i
< paths
.length ();)
2024 vec
<jump_thread_edge
*> *path
= paths
[i
];
2025 edge e
= (*path
)[0]->e
;
2027 if ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
&& e
->aux
== path
)
2030 for (j
= 1; j
< path
->length (); j
++)
2031 if ((*path
)[j
]->e
->aux
!= NULL
)
2034 /* If we iterated through the entire path without exiting the loop,
2035 then we are good to go, record it. */
2036 if (j
== path
->length ())
2038 bitmap_set_bit (tmp
, e
->dest
->index
);
2044 paths
.unordered_remove (i
);
2045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2046 dump_jump_thread_path (dump_file
, *path
, false);
2047 delete_jump_thread_path (path
);
2056 /* If optimizing for size, only thread through block if we don't have
2057 to duplicate it or it's an otherwise empty redirection block. */
2058 if (optimize_function_for_size_p (cfun
))
2060 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2062 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2063 if (EDGE_COUNT (bb
->preds
) > 1
2064 && !redirection_block_p (bb
))
2066 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2070 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
2071 delete_jump_thread_path (path
);
2077 bitmap_set_bit (threaded_blocks
, i
);
2081 bitmap_copy (threaded_blocks
, tmp
);
2083 /* If we have a joiner block (J) which has two successors S1 and S2 and
2084 we are threading though S1 and the final destination of the thread
2085 is S2, then we must verify that any PHI nodes in S2 have the same
2086 PHI arguments for the edge J->S2 and J->S1->...->S2.
2088 We used to detect this prior to registering the jump thread, but
2089 that prohibits propagation of edge equivalences into non-dominated
2090 PHI nodes as the equivalency test might occur before propagation.
2092 This must also occur after we truncate any jump threading paths
2093 as this scenario may only show up after truncation.
2095 This works for now, but will need improvement as part of the FSA
2098 Note since we've moved the thread request data to the edges,
2099 we have to iterate on those rather than the threaded_edges vector. */
2100 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2102 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2103 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2107 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
2108 bool have_joiner
= ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
);
2112 basic_block joiner
= e
->dest
;
2113 edge final_edge
= path
->last ()->e
;
2114 basic_block final_dest
= final_edge
->dest
;
2115 edge e2
= find_edge (joiner
, final_dest
);
2117 if (e2
&& !phi_args_equal_on_edges (e2
, final_edge
))
2119 delete_jump_thread_path (path
);
2127 /* Look for jump threading paths which cross multiple loop headers.
2129 The code to thread through loop headers will change the CFG in ways
2130 that invalidate the cached loop iteration information. So we must
2131 detect that case and wipe the cached information. */
2132 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2134 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2135 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2139 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
2141 for (unsigned int i
= 0, crossed_headers
= 0;
2142 i
< path
->length ();
2145 basic_block dest
= (*path
)[i
]->e
->dest
;
2146 basic_block src
= (*path
)[i
]->e
->src
;
2147 /* If we enter a loop. */
2148 if (flow_loop_nested_p (src
->loop_father
, dest
->loop_father
))
2150 /* If we step from a block outside an irreducible region
2151 to a block inside an irreducible region, then we have
2152 crossed into a loop. */
2153 else if (! (src
->flags
& BB_IRREDUCIBLE_LOOP
)
2154 && (dest
->flags
& BB_IRREDUCIBLE_LOOP
))
2156 if (crossed_headers
> 1)
2158 vect_free_loop_info_assumptions
2159 ((*path
)[path
->length () - 1]->e
->dest
->loop_father
);
2169 /* Verify that the REGION is a valid jump thread. A jump thread is a special
2170 case of SEME Single Entry Multiple Exits region in which all nodes in the
2171 REGION have exactly one incoming edge. The only exception is the first block
2172 that may not have been connected to the rest of the cfg yet. */
2175 verify_jump_thread (basic_block
*region
, unsigned n_region
)
2177 for (unsigned i
= 0; i
< n_region
; i
++)
2178 gcc_assert (EDGE_COUNT (region
[i
]->preds
) <= 1);
2181 /* Return true when BB is one of the first N items in BBS. */
2184 bb_in_bbs (basic_block bb
, basic_block
*bbs
, int n
)
2186 for (int i
= 0; i
< n
; i
++)
2193 /* Duplicates a jump-thread path of N_REGION basic blocks.
2194 The ENTRY edge is redirected to the duplicate of the region.
2196 Remove the last conditional statement in the last basic block in the REGION,
2197 and create a single fallthru edge pointing to the same destination as the
2200 The new basic blocks are stored to REGION_COPY in the same order as they had
2201 in REGION, provided that REGION_COPY is not NULL.
2203 Returns false if it is unable to copy the region, true otherwise. */
2206 duplicate_thread_path (edge entry
, edge exit
,
2207 basic_block
*region
, unsigned n_region
,
2208 basic_block
*region_copy
)
2211 bool free_region_copy
= false;
2212 struct loop
*loop
= entry
->dest
->loop_father
;
2216 profile_count curr_count
;
2218 if (!can_copy_bbs_p (region
, n_region
))
2221 /* Some sanity checking. Note that we do not check for all possible
2222 missuses of the functions. I.e. if you ask to copy something weird,
2223 it will work, but the state of structures probably will not be
2225 for (i
= 0; i
< n_region
; i
++)
2227 /* We do not handle subloops, i.e. all the blocks must belong to the
2229 if (region
[i
]->loop_father
!= loop
)
2233 initialize_original_copy_tables ();
2235 set_loop_copy (loop
, loop
);
2239 region_copy
= XNEWVEC (basic_block
, n_region
);
2240 free_region_copy
= true;
2243 copy_bbs (region
, n_region
, region_copy
, &exit
, 1, &exit_copy
, loop
,
2244 split_edge_bb_loc (entry
), false);
2246 /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The
2247 following code ensures that all the edges exiting the jump-thread path are
2248 redirected back to the original code: these edges are exceptions
2249 invalidating the property that is propagated by executing all the blocks of
2250 the jump-thread path in order. */
2252 curr_count
= entry
->count
;
2253 curr_freq
= EDGE_FREQUENCY (entry
);
2255 for (i
= 0; i
< n_region
; i
++)
2259 basic_block bb
= region_copy
[i
];
2261 /* Watch inconsistent profile. */
2262 if (curr_count
> region
[i
]->count
)
2263 curr_count
= region
[i
]->count
;
2264 if (curr_freq
> region
[i
]->frequency
)
2265 curr_freq
= region
[i
]->frequency
;
2266 /* Scale current BB. */
2267 if (region
[i
]->count
> 0 && curr_count
.initialized_p ())
2269 /* In the middle of the path we only scale the frequencies.
2270 In last BB we need to update probabilities of outgoing edges
2271 because we know which one is taken at the threaded path. */
2272 if (i
+ 1 != n_region
)
2273 scale_bbs_frequencies_profile_count (region
+ i
, 1,
2274 region
[i
]->count
- curr_count
,
2277 update_bb_profile_for_threading (region
[i
],
2278 curr_freq
, curr_count
,
2280 scale_bbs_frequencies_profile_count (region_copy
+ i
, 1, curr_count
,
2281 region_copy
[i
]->count
);
2283 else if (region
[i
]->frequency
)
2285 if (i
+ 1 != n_region
)
2286 scale_bbs_frequencies_int (region
+ i
, 1,
2287 region
[i
]->frequency
- curr_freq
,
2288 region
[i
]->frequency
);
2290 update_bb_profile_for_threading (region
[i
],
2291 curr_freq
, curr_count
,
2293 scale_bbs_frequencies_int (region_copy
+ i
, 1, curr_freq
,
2294 region_copy
[i
]->frequency
);
2297 if (single_succ_p (bb
))
2299 /* Make sure the successor is the next node in the path. */
2300 gcc_assert (i
+ 1 == n_region
2301 || region_copy
[i
+ 1] == single_succ_edge (bb
)->dest
);
2302 if (i
+ 1 != n_region
)
2304 curr_freq
= EDGE_FREQUENCY (single_succ_edge (bb
));
2305 curr_count
= single_succ_edge (bb
)->count
;
2310 /* Special case the last block on the path: make sure that it does not
2311 jump back on the copied path, including back to itself. */
2312 if (i
+ 1 == n_region
)
2314 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2315 if (bb_in_bbs (e
->dest
, region_copy
, n_region
))
2317 basic_block orig
= get_bb_original (e
->dest
);
2319 redirect_edge_and_branch_force (e
, orig
);
2324 /* Redirect all other edges jumping to non-adjacent blocks back to the
2326 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2327 if (region_copy
[i
+ 1] != e
->dest
)
2329 basic_block orig
= get_bb_original (e
->dest
);
2331 redirect_edge_and_branch_force (e
, orig
);
2335 curr_freq
= EDGE_FREQUENCY (e
);
2336 curr_count
= e
->count
;
2342 verify_jump_thread (region_copy
, n_region
);
2344 /* Remove the last branch in the jump thread path. */
2345 remove_ctrl_stmt_and_useless_edges (region_copy
[n_region
- 1], exit
->dest
);
2347 /* And fixup the flags on the single remaining edge. */
2348 edge fix_e
= find_edge (region_copy
[n_region
- 1], exit
->dest
);
2349 fix_e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
| EDGE_ABNORMAL
);
2350 fix_e
->flags
|= EDGE_FALLTHRU
;
2352 edge e
= make_edge (region_copy
[n_region
- 1], exit
->dest
, EDGE_FALLTHRU
);
2356 rescan_loop_exit (e
, true, false);
2357 e
->probability
= REG_BR_PROB_BASE
;
2358 e
->count
= region_copy
[n_region
- 1]->count
;
2361 /* Redirect the entry and add the phi node arguments. */
2362 if (entry
->dest
== loop
->header
)
2363 mark_loop_for_removal (loop
);
2364 redirected
= redirect_edge_and_branch (entry
, get_bb_copy (entry
->dest
));
2365 gcc_assert (redirected
!= NULL
);
2366 flush_pending_stmts (entry
);
2368 /* Add the other PHI node arguments. */
2369 add_phi_args_after_copy (region_copy
, n_region
, NULL
);
2371 if (free_region_copy
)
2374 free_original_copy_tables ();
2378 /* Return true when PATH is a valid jump-thread path. */
2381 valid_jump_thread_path (vec
<jump_thread_edge
*> *path
)
2383 unsigned len
= path
->length ();
2385 /* Check that the path is connected. */
2386 for (unsigned int j
= 0; j
< len
- 1; j
++)
2388 edge e
= (*path
)[j
]->e
;
2389 if (e
->dest
!= (*path
)[j
+1]->e
->src
)
2395 /* Remove any queued jump threads that include edge E.
2397 We don't actually remove them here, just record the edges into ax
2398 hash table. That way we can do the search once per iteration of
2399 DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR. */
2402 remove_jump_threads_including (edge_def
*e
)
2404 if (!paths
.exists ())
2408 removed_edges
= new hash_table
<struct removed_edges
> (17);
2410 edge
*slot
= removed_edges
->find_slot (e
, INSERT
);
2414 /* Walk through all blocks and thread incoming edges to the appropriate
2415 outgoing edge for each edge pair recorded in THREADED_EDGES.
2417 It is the caller's responsibility to fix the dominance information
2418 and rewrite duplicated SSA_NAMEs back into SSA form.
2420 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
2421 loop headers if it does not simplify the loop.
2423 Returns true if one or more edges were threaded, false otherwise. */
2426 thread_through_all_blocks (bool may_peel_loop_headers
)
2428 bool retval
= false;
2432 auto_bitmap threaded_blocks
;
2434 if (!paths
.exists ())
2440 memset (&thread_stats
, 0, sizeof (thread_stats
));
2442 /* Remove any paths that referenced removed edges. */
2444 for (i
= 0; i
< paths
.length (); )
2447 vec
<jump_thread_edge
*> *path
= paths
[i
];
2449 for (j
= 0; j
< path
->length (); j
++)
2451 edge e
= (*path
)[j
]->e
;
2452 if (removed_edges
->find_slot (e
, NO_INSERT
))
2456 if (j
!= path
->length ())
2458 delete_jump_thread_path (path
);
2459 paths
.unordered_remove (i
);
2465 /* Jump-thread all FSM threads before other jump-threads. */
2466 for (i
= 0; i
< paths
.length ();)
2468 vec
<jump_thread_edge
*> *path
= paths
[i
];
2469 edge entry
= (*path
)[0]->e
;
2471 /* Only code-generate FSM jump-threads in this loop. */
2472 if ((*path
)[0]->type
!= EDGE_FSM_THREAD
)
2478 /* Do not jump-thread twice from the same block. */
2479 if (bitmap_bit_p (threaded_blocks
, entry
->src
->index
)
2480 /* We may not want to realize this jump thread path
2481 for various reasons. So check it first. */
2482 || !valid_jump_thread_path (path
))
2484 /* Remove invalid FSM jump-thread paths. */
2485 delete_jump_thread_path (path
);
2486 paths
.unordered_remove (i
);
2490 unsigned len
= path
->length ();
2491 edge exit
= (*path
)[len
- 1]->e
;
2492 basic_block
*region
= XNEWVEC (basic_block
, len
- 1);
2494 for (unsigned int j
= 0; j
< len
- 1; j
++)
2495 region
[j
] = (*path
)[j
]->e
->dest
;
2497 if (duplicate_thread_path (entry
, exit
, region
, len
- 1, NULL
))
2499 /* We do not update dominance info. */
2500 free_dominance_info (CDI_DOMINATORS
);
2501 bitmap_set_bit (threaded_blocks
, entry
->src
->index
);
2503 thread_stats
.num_threaded_edges
++;
2506 delete_jump_thread_path (path
);
2507 paths
.unordered_remove (i
);
2511 /* Remove from PATHS all the jump-threads starting with an edge already
2513 for (i
= 0; i
< paths
.length ();)
2515 vec
<jump_thread_edge
*> *path
= paths
[i
];
2516 edge entry
= (*path
)[0]->e
;
2518 /* Do not jump-thread twice from the same block. */
2519 if (bitmap_bit_p (threaded_blocks
, entry
->src
->index
))
2521 delete_jump_thread_path (path
);
2522 paths
.unordered_remove (i
);
2528 bitmap_clear (threaded_blocks
);
2530 mark_threaded_blocks (threaded_blocks
);
2532 initialize_original_copy_tables ();
2534 /* First perform the threading requests that do not affect
2536 EXECUTE_IF_SET_IN_BITMAP (threaded_blocks
, 0, i
, bi
)
2538 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2540 if (EDGE_COUNT (bb
->preds
) > 0)
2541 retval
|= thread_block (bb
, true);
2544 /* Then perform the threading through loop headers. We start with the
2545 innermost loop, so that the changes in cfg we perform won't affect
2546 further threading. */
2547 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2550 || !bitmap_bit_p (threaded_blocks
, loop
->header
->index
))
2553 retval
|= thread_through_loop_header (loop
, may_peel_loop_headers
);
2556 /* All jump threading paths should have been resolved at this
2557 point. Verify that is the case. */
2559 FOR_EACH_BB_FN (bb
, cfun
)
2563 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2564 gcc_assert (e
->aux
== NULL
);
2567 statistics_counter_event (cfun
, "Jumps threaded",
2568 thread_stats
.num_threaded_edges
);
2570 free_original_copy_tables ();
2575 loops_state_set (LOOPS_NEED_FIXUP
);
2578 delete removed_edges
;
2579 removed_edges
= NULL
;
2583 /* Delete the jump threading path PATH. We have to explcitly delete
2584 each entry in the vector, then the container. */
2587 delete_jump_thread_path (vec
<jump_thread_edge
*> *path
)
2589 for (unsigned int i
= 0; i
< path
->length (); i
++)
2595 /* Register a jump threading opportunity. We queue up all the jump
2596 threading opportunities discovered by a pass and update the CFG
2597 and SSA form all at once.
2599 E is the edge we can thread, E2 is the new target edge, i.e., we
2600 are effectively recording that E->dest can be changed to E2->dest
2601 after fixing the SSA graph. */
2604 register_jump_thread (vec
<jump_thread_edge
*> *path
)
2606 if (!dbg_cnt (registered_jump_thread
))
2608 delete_jump_thread_path (path
);
2612 /* First make sure there are no NULL outgoing edges on the jump threading
2613 path. That can happen for jumping to a constant address. */
2614 for (unsigned int i
= 0; i
< path
->length (); i
++)
2616 if ((*path
)[i
]->e
== NULL
)
2618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2621 "Found NULL edge in jump threading path. Cancelling jump thread:\n");
2622 dump_jump_thread_path (dump_file
, *path
, false);
2625 delete_jump_thread_path (path
);
2629 /* Only the FSM threader is allowed to thread across
2630 backedges in the CFG. */
2632 && (*path
)[0]->type
!= EDGE_FSM_THREAD
)
2633 gcc_assert (((*path
)[i
]->e
->flags
& EDGE_DFS_BACK
) == 0);
2636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2637 dump_jump_thread_path (dump_file
, *path
, true);
2639 if (!paths
.exists ())
2642 paths
.safe_push (path
);