1 /* Thread edges through blocks and update the control flow and SSA graphs.
2 Copyright (C) 2004-2021 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 vec
<jump_thread_edge
*> *path
;
133 /* A list of incoming edges which we want to thread to the
135 struct el
*incoming_edges
;
137 /* hash_table support. */
138 static inline hashval_t
hash (const redirection_data
*);
139 static inline int equal (const redirection_data
*, const redirection_data
*);
142 jump_thread_path_allocator::jump_thread_path_allocator ()
144 obstack_init (&m_obstack
);
147 jump_thread_path_allocator::~jump_thread_path_allocator ()
149 obstack_free (&m_obstack
, NULL
);
153 jump_thread_path_allocator::allocate_thread_edge (edge e
,
154 jump_thread_edge_type type
)
156 void *r
= obstack_alloc (&m_obstack
, sizeof (jump_thread_edge
));
157 return new (r
) jump_thread_edge (e
, type
);
160 vec
<jump_thread_edge
*> *
161 jump_thread_path_allocator::allocate_thread_path ()
163 // ?? Since the paths live in an obstack, we should be able to remove all
164 // references to path->release() throughout the code.
165 void *r
= obstack_alloc (&m_obstack
, sizeof (vec
<jump_thread_edge
*>));
166 return new (r
) vec
<jump_thread_edge
*> ();
169 jump_thread_path_registry::jump_thread_path_registry ()
172 m_removed_edges
= new hash_table
<struct removed_edges
> (17);
173 m_num_threaded_edges
= 0;
174 m_redirection_data
= NULL
;
177 jump_thread_path_registry::~jump_thread_path_registry ()
180 delete m_removed_edges
;
184 jump_thread_path_registry::allocate_thread_edge (edge e
,
185 jump_thread_edge_type t
)
187 return m_allocator
.allocate_thread_edge (e
, t
);
190 vec
<jump_thread_edge
*> *
191 jump_thread_path_registry::allocate_thread_path ()
193 return m_allocator
.allocate_thread_path ();
196 /* Dump a jump threading path, including annotations about each
200 dump_jump_thread_path (FILE *dump_file
,
201 const vec
<jump_thread_edge
*> path
,
205 " %s%s jump thread: (%d, %d) incoming edge; ",
206 (registering
? "Registering" : "Cancelling"),
207 (path
[0]->type
== EDGE_FSM_THREAD
? " FSM": ""),
208 path
[0]->e
->src
->index
, path
[0]->e
->dest
->index
);
210 for (unsigned int i
= 1; i
< path
.length (); i
++)
212 /* We can get paths with a NULL edge when the final destination
213 of a jump thread turns out to be a constant address. We dump
214 those paths when debugging, so we have to be prepared for that
216 if (path
[i
]->e
== NULL
)
219 if (path
[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
220 fprintf (dump_file
, " (%d, %d) joiner; ",
221 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
222 if (path
[i
]->type
== EDGE_COPY_SRC_BLOCK
)
223 fprintf (dump_file
, " (%d, %d) normal;",
224 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
225 if (path
[i
]->type
== EDGE_NO_COPY_SRC_BLOCK
)
226 fprintf (dump_file
, " (%d, %d) nocopy;",
227 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
228 if (path
[0]->type
== EDGE_FSM_THREAD
)
229 fprintf (dump_file
, " (%d, %d) ",
230 path
[i
]->e
->src
->index
, path
[i
]->e
->dest
->index
);
232 fputc ('\n', dump_file
);
236 debug (const vec
<jump_thread_edge
*> &path
)
238 dump_jump_thread_path (stderr
, path
, true);
241 /* Simple hashing function. For any given incoming edge E, we're going
242 to be most concerned with the final destination of its jump thread
243 path. So hash on the block index of the final edge in the path. */
246 redirection_data::hash (const redirection_data
*p
)
248 vec
<jump_thread_edge
*> *path
= p
->path
;
249 return path
->last ()->e
->dest
->index
;
252 /* Given two hash table entries, return true if they have the same
253 jump threading path. */
255 redirection_data::equal (const redirection_data
*p1
, const redirection_data
*p2
)
257 vec
<jump_thread_edge
*> *path1
= p1
->path
;
258 vec
<jump_thread_edge
*> *path2
= p2
->path
;
260 if (path1
->length () != path2
->length ())
263 for (unsigned int i
= 1; i
< path1
->length (); i
++)
265 if ((*path1
)[i
]->type
!= (*path2
)[i
]->type
266 || (*path1
)[i
]->e
!= (*path2
)[i
]->e
)
273 /* Data structure of information to pass to hash table traversal routines. */
274 struct ssa_local_info_t
276 /* The current block we are working on. */
279 /* We only create a template block for the first duplicated block in a
280 jump threading path as we may need many duplicates of that block.
282 The second duplicate block in a path is specific to that path. Creating
283 and sharing a template for that block is considerably more difficult. */
284 basic_block template_block
;
286 /* If we append debug stmts to the template block after creating it,
287 this iterator won't be the last one in the block, and further
288 copies of the template block shouldn't get debug stmts after
290 gimple_stmt_iterator template_last_to_copy
;
292 /* Blocks duplicated for the thread. */
293 bitmap duplicate_blocks
;
295 /* TRUE if we thread one or more jumps, FALSE otherwise. */
298 /* When we have multiple paths through a joiner which reach different
299 final destinations, then we may need to correct for potential
300 profile insanities. */
301 bool need_profile_correction
;
303 // Jump threading statistics.
304 unsigned long num_threaded_edges
;
307 /* When we start updating the CFG for threading, data necessary for jump
308 threading is attached to the AUX field for the incoming edge. Use these
309 macros to access the underlying structure attached to the AUX field. */
310 #define THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux)
312 /* Remove the last statement in block BB if it is a control statement
313 Also remove all outgoing edges except the edge which reaches DEST_BB.
314 If DEST_BB is NULL, then remove all outgoing edges. */
317 remove_ctrl_stmt_and_useless_edges (basic_block bb
, basic_block dest_bb
)
319 gimple_stmt_iterator gsi
;
323 gsi
= gsi_last_bb (bb
);
325 /* If the duplicate ends with a control statement, then remove it.
327 Note that if we are duplicating the template block rather than the
328 original basic block, then the duplicate might not have any real
332 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
333 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_GOTO
334 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_SWITCH
))
335 gsi_remove (&gsi
, true);
337 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
339 if (e
->dest
!= dest_bb
)
341 free_dom_edge_info (e
);
346 e
->probability
= profile_probability::always ();
351 /* If the remaining edge is a loop exit, there must have
352 a removed edge that was not a loop exit.
354 In that case BB and possibly other blocks were previously
355 in the loop, but are now outside the loop. Thus, we need
356 to update the loop structures. */
357 if (single_succ_p (bb
)
358 && loop_outer (bb
->loop_father
)
359 && loop_exit_edge_p (bb
->loop_father
, single_succ_edge (bb
)))
360 loops_state_set (LOOPS_NEED_FIXUP
);
363 /* Create a duplicate of BB. Record the duplicate block in an array
364 indexed by COUNT stored in RD. */
367 create_block_for_threading (basic_block bb
,
368 struct redirection_data
*rd
,
370 bitmap
*duplicate_blocks
)
375 /* We can use the generic block duplication code and simply remove
376 the stuff we do not need. */
377 rd
->dup_blocks
[count
] = duplicate_block (bb
, NULL
, NULL
);
379 FOR_EACH_EDGE (e
, ei
, rd
->dup_blocks
[count
]->succs
)
383 /* If we duplicate a block with an outgoing edge marked as
384 EDGE_IGNORE, we must clear EDGE_IGNORE so that it doesn't
385 leak out of the current pass.
387 It would be better to simplify switch statements and remove
388 the edges before we get here, but the sequencing is nontrivial. */
389 e
->flags
&= ~EDGE_IGNORE
;
392 /* Zero out the profile, since the block is unreachable for now. */
393 rd
->dup_blocks
[count
]->count
= profile_count::uninitialized ();
394 if (duplicate_blocks
)
395 bitmap_set_bit (*duplicate_blocks
, rd
->dup_blocks
[count
]->index
);
398 /* Given an outgoing edge E lookup and return its entry in our hash table.
400 If INSERT is true, then we insert the entry into the hash table if
401 it is not already present. INCOMING_EDGE is added to the list of incoming
402 edges associated with E in the hash table. */
405 jump_thread_path_registry::lookup_redirection_data (edge e
,
406 enum insert_option insert
)
408 struct redirection_data
**slot
;
409 struct redirection_data
*elt
;
410 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
412 /* Build a hash table element so we can see if E is already
414 elt
= XNEW (struct redirection_data
);
416 elt
->dup_blocks
[0] = NULL
;
417 elt
->dup_blocks
[1] = NULL
;
418 elt
->incoming_edges
= NULL
;
420 slot
= m_redirection_data
->find_slot (elt
, insert
);
422 /* This will only happen if INSERT is false and the entry is not
423 in the hash table. */
430 /* This will only happen if E was not in the hash table and
435 elt
->incoming_edges
= XNEW (struct el
);
436 elt
->incoming_edges
->e
= e
;
437 elt
->incoming_edges
->next
= NULL
;
440 /* E was in the hash table. */
443 /* Free ELT as we do not need it anymore, we will extract the
444 relevant entry from the hash table itself. */
447 /* Get the entry stored in the hash table. */
450 /* If insertion was requested, then we need to add INCOMING_EDGE
451 to the list of incoming edges associated with E. */
454 struct el
*el
= XNEW (struct el
);
455 el
->next
= elt
->incoming_edges
;
457 elt
->incoming_edges
= el
;
464 /* Similar to copy_phi_args, except that the PHI arg exists, it just
465 does not have a value associated with it. */
468 copy_phi_arg_into_existing_phi (edge src_e
, edge tgt_e
)
470 int src_idx
= src_e
->dest_idx
;
471 int tgt_idx
= tgt_e
->dest_idx
;
473 /* Iterate over each PHI in e->dest. */
474 for (gphi_iterator gsi
= gsi_start_phis (src_e
->dest
),
475 gsi2
= gsi_start_phis (tgt_e
->dest
);
477 gsi_next (&gsi
), gsi_next (&gsi2
))
479 gphi
*src_phi
= gsi
.phi ();
480 gphi
*dest_phi
= gsi2
.phi ();
481 tree val
= gimple_phi_arg_def (src_phi
, src_idx
);
482 location_t locus
= gimple_phi_arg_location (src_phi
, src_idx
);
484 SET_PHI_ARG_DEF (dest_phi
, tgt_idx
, val
);
485 gimple_phi_arg_set_location (dest_phi
, tgt_idx
, locus
);
489 /* Given ssa_name DEF, backtrack jump threading PATH from node IDX
490 to see if it has constant value in a flow sensitive manner. Set
491 LOCUS to location of the constant phi arg and return the value.
492 Return DEF directly if either PATH or idx is ZERO. */
495 get_value_locus_in_path (tree def
, vec
<jump_thread_edge
*> *path
,
496 basic_block bb
, int idx
, location_t
*locus
)
502 if (path
== NULL
|| idx
== 0)
505 def_phi
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (def
));
509 def_bb
= gimple_bb (def_phi
);
510 /* Don't propagate loop invariants into deeper loops. */
511 if (!def_bb
|| bb_loop_depth (def_bb
) < bb_loop_depth (bb
))
514 /* Backtrack jump threading path from IDX to see if def has constant
516 for (int j
= idx
- 1; j
>= 0; j
--)
518 edge e
= (*path
)[j
]->e
;
519 if (e
->dest
== def_bb
)
521 arg
= gimple_phi_arg_def (def_phi
, e
->dest_idx
);
522 if (is_gimple_min_invariant (arg
))
524 *locus
= gimple_phi_arg_location (def_phi
, e
->dest_idx
);
534 /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
535 Try to backtrack jump threading PATH from node IDX to see if the arg
536 has constant value, copy constant value instead of argument itself
540 copy_phi_args (basic_block bb
, edge src_e
, edge tgt_e
,
541 vec
<jump_thread_edge
*> *path
, int idx
)
544 int src_indx
= src_e
->dest_idx
;
546 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
548 gphi
*phi
= gsi
.phi ();
549 tree def
= gimple_phi_arg_def (phi
, src_indx
);
550 location_t locus
= gimple_phi_arg_location (phi
, src_indx
);
552 if (TREE_CODE (def
) == SSA_NAME
553 && !virtual_operand_p (gimple_phi_result (phi
)))
554 def
= get_value_locus_in_path (def
, path
, bb
, idx
, &locus
);
556 add_phi_arg (phi
, def
, tgt_e
, locus
);
560 /* We have recently made a copy of ORIG_BB, including its outgoing
561 edges. The copy is NEW_BB. Every PHI node in every direct successor of
562 ORIG_BB has a new argument associated with edge from NEW_BB to the
563 successor. Initialize the PHI argument so that it is equal to the PHI
564 argument associated with the edge from ORIG_BB to the successor.
565 PATH and IDX are used to check if the new PHI argument has constant
566 value in a flow sensitive manner. */
569 update_destination_phis (basic_block orig_bb
, basic_block new_bb
,
570 vec
<jump_thread_edge
*> *path
, int idx
)
575 FOR_EACH_EDGE (e
, ei
, orig_bb
->succs
)
577 edge e2
= find_edge (new_bb
, e
->dest
);
578 copy_phi_args (e
->dest
, e
, e2
, path
, idx
);
582 /* Given a duplicate block and its single destination (both stored
583 in RD). Create an edge between the duplicate and its single
586 Add an additional argument to any PHI nodes at the single
587 destination. IDX is the start node in jump threading path
588 we start to check to see if the new PHI argument has constant
589 value along the jump threading path. */
592 create_edge_and_update_destination_phis (struct redirection_data
*rd
,
593 basic_block bb
, int idx
)
595 edge e
= make_single_succ_edge (bb
, rd
->path
->last ()->e
->dest
, EDGE_FALLTHRU
);
597 rescan_loop_exit (e
, true, false);
599 /* We used to copy the thread path here. That was added in 2007
600 and dutifully updated through the representation changes in 2013.
602 In 2013 we added code to thread from an interior node through
603 the backedge to another interior node. That runs after the code
604 to thread through loop headers from outside the loop.
606 The latter may delete edges in the CFG, including those
607 which appeared in the jump threading path we copied here. Thus
608 we'd end up using a dangling pointer.
610 After reviewing the 2007/2011 code, I can't see how anything
611 depended on copying the AUX field and clearly copying the jump
612 threading path is problematical due to embedded edge pointers.
613 It has been removed. */
616 /* If there are any PHI nodes at the destination of the outgoing edge
617 from the duplicate block, then we will need to add a new argument
618 to them. The argument should have the same value as the argument
619 associated with the outgoing edge stored in RD. */
620 copy_phi_args (e
->dest
, rd
->path
->last ()->e
, e
, rd
->path
, idx
);
623 /* Look through PATH beginning at START and return TRUE if there are
624 any additional blocks that need to be duplicated. Otherwise,
627 any_remaining_duplicated_blocks (vec
<jump_thread_edge
*> *path
,
630 for (unsigned int i
= start
+ 1; i
< path
->length (); i
++)
632 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
633 || (*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
)
640 /* Compute the amount of profile count coming into the jump threading
641 path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
642 PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
643 duplicated path, returned in PATH_OUT_COUNT_PTR. LOCAL_INFO is used to
644 identify blocks duplicated for jump threading, which have duplicated
645 edges that need to be ignored in the analysis. Return true if path contains
646 a joiner, false otherwise.
648 In the non-joiner case, this is straightforward - all the counts
649 flowing into the jump threading path should flow through the duplicated
650 block and out of the duplicated path.
652 In the joiner case, it is very tricky. Some of the counts flowing into
653 the original path go offpath at the joiner. The problem is that while
654 we know how much total count goes off-path in the original control flow,
655 we don't know how many of the counts corresponding to just the jump
656 threading path go offpath at the joiner.
658 For example, assume we have the following control flow and identified
659 jump threading paths:
678 Jump threading paths: A -> J -> Son -> D (path 1)
679 C -> J -> Son -> E (path 2)
681 Note that the control flow could be more complicated:
682 - Each jump threading path may have more than one incoming edge. I.e. A and
683 Ea could represent multiple incoming blocks/edges that are included in
685 - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
686 before or after the "normal" copy block). These are not duplicated onto
687 the jump threading path, as they are single-successor.
688 - Any of the blocks along the path may have other incoming edges that
689 are not part of any jump threading path, but add profile counts along
692 In the above example, after all jump threading is complete, we will
693 end up with the following control flow:
702 Eona/ \ ---/---\-------- \Eonc
707 \___________ / \ _____/
712 The main issue to notice here is that when we are processing path 1
713 (A->J->Son->D) we need to figure out the outgoing edge weights to
714 the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
715 sum of the incoming weights to D remain Ed. The problem with simply
716 assuming that Ja (and Jc when processing path 2) has the same outgoing
717 probabilities to its successors as the original block J, is that after
718 all paths are processed and other edges/counts removed (e.g. none
719 of Ec will reach D after processing path 2), we may end up with not
720 enough count flowing along duplicated edge Sona->D.
722 Therefore, in the case of a joiner, we keep track of all counts
723 coming in along the current path, as well as from predecessors not
724 on any jump threading path (Eb in the above example). While we
725 first assume that the duplicated Eona for Ja->Sona has the same
726 probability as the original, we later compensate for other jump
727 threading paths that may eliminate edges. We do that by keep track
728 of all counts coming into the original path that are not in a jump
729 thread (Eb in the above example, but as noted earlier, there could
730 be other predecessors incoming to the path at various points, such
731 as at Son). Call this cumulative non-path count coming into the path
732 before D as Enonpath. We then ensure that the count from Sona->D is as at
733 least as big as (Ed - Enonpath), but no bigger than the minimum
734 weight along the jump threading path. The probabilities of both the
735 original and duplicated joiner block J and Ja will be adjusted
736 accordingly after the updates. */
739 compute_path_counts (struct redirection_data
*rd
,
740 ssa_local_info_t
*local_info
,
741 profile_count
*path_in_count_ptr
,
742 profile_count
*path_out_count_ptr
)
744 edge e
= rd
->incoming_edges
->e
;
745 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
746 edge elast
= path
->last ()->e
;
747 profile_count nonpath_count
= profile_count::zero ();
748 bool has_joiner
= false;
749 profile_count path_in_count
= profile_count::zero ();
751 /* Start by accumulating incoming edge counts to the path's first bb
752 into a couple buckets:
753 path_in_count: total count of incoming edges that flow into the
755 nonpath_count: total count of incoming edges that are not
756 flowing along *any* path. These are the counts
757 that will still flow along the original path after
758 all path duplication is done by potentially multiple
759 calls to this routine.
760 (any other incoming edge counts are for a different jump threading
761 path that will be handled by a later call to this routine.)
762 To make this easier, start by recording all incoming edges that flow into
763 the current path in a bitmap. We could add up the path's incoming edge
764 counts here, but we still need to walk all the first bb's incoming edges
765 below to add up the counts of the other edges not included in this jump
767 struct el
*next
, *el
;
768 auto_bitmap in_edge_srcs
;
769 for (el
= rd
->incoming_edges
; el
; el
= next
)
772 bitmap_set_bit (in_edge_srcs
, el
->e
->src
->index
);
776 FOR_EACH_EDGE (ein
, ei
, e
->dest
->preds
)
778 vec
<jump_thread_edge
*> *ein_path
= THREAD_PATH (ein
);
779 /* Simply check the incoming edge src against the set captured above. */
781 && bitmap_bit_p (in_edge_srcs
, (*ein_path
)[0]->e
->src
->index
))
783 /* It is necessary but not sufficient that the last path edges
784 are identical. There may be different paths that share the
785 same last path edge in the case where the last edge has a nocopy
787 gcc_assert (ein_path
->last ()->e
== elast
);
788 path_in_count
+= ein
->count ();
792 /* Keep track of the incoming edges that are not on any jump-threading
793 path. These counts will still flow out of original path after all
794 jump threading is complete. */
795 nonpath_count
+= ein
->count ();
799 /* Now compute the fraction of the total count coming into the first
800 path bb that is from the current threading path. */
801 profile_count total_count
= e
->dest
->count
;
802 /* Handle incoming profile insanities. */
803 if (total_count
< path_in_count
)
804 path_in_count
= total_count
;
805 profile_probability onpath_scale
= path_in_count
.probability_in (total_count
);
807 /* Walk the entire path to do some more computation in order to estimate
808 how much of the path_in_count will flow out of the duplicated threading
809 path. In the non-joiner case this is straightforward (it should be
810 the same as path_in_count, although we will handle incoming profile
811 insanities by setting it equal to the minimum count along the path).
813 In the joiner case, we need to estimate how much of the path_in_count
814 will stay on the threading path after the joiner's conditional branch.
815 We don't really know for sure how much of the counts
816 associated with this path go to each successor of the joiner, but we'll
817 estimate based on the fraction of the total count coming into the path
818 bb was from the threading paths (computed above in onpath_scale).
819 Afterwards, we will need to do some fixup to account for other threading
820 paths and possible profile insanities.
822 In order to estimate the joiner case's counts we also need to update
823 nonpath_count with any additional counts coming into the path. Other
824 blocks along the path may have additional predecessors from outside
826 profile_count path_out_count
= path_in_count
;
827 profile_count min_path_count
= path_in_count
;
828 for (unsigned int i
= 1; i
< path
->length (); i
++)
830 edge epath
= (*path
)[i
]->e
;
831 profile_count cur_count
= epath
->count ();
832 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
835 cur_count
= cur_count
.apply_probability (onpath_scale
);
837 /* In the joiner case we need to update nonpath_count for any edges
838 coming into the path that will contribute to the count flowing
839 into the path successor. */
840 if (has_joiner
&& epath
!= elast
)
842 /* Look for other incoming edges after joiner. */
843 FOR_EACH_EDGE (ein
, ei
, epath
->dest
->preds
)
846 /* Ignore in edges from blocks we have duplicated for a
847 threading path, which have duplicated edge counts until
848 they are redirected by an invocation of this routine. */
849 && !bitmap_bit_p (local_info
->duplicate_blocks
,
851 nonpath_count
+= ein
->count ();
854 if (cur_count
< path_out_count
)
855 path_out_count
= cur_count
;
856 if (epath
->count () < min_path_count
)
857 min_path_count
= epath
->count ();
860 /* We computed path_out_count above assuming that this path targeted
861 the joiner's on-path successor with the same likelihood as it
862 reached the joiner. However, other thread paths through the joiner
863 may take a different path through the normal copy source block
864 (i.e. they have a different elast), meaning that they do not
865 contribute any counts to this path's elast. As a result, it may
866 turn out that this path must have more count flowing to the on-path
867 successor of the joiner. Essentially, all of this path's elast
868 count must be contributed by this path and any nonpath counts
869 (since any path through the joiner with a different elast will not
870 include a copy of this elast in its duplicated path).
871 So ensure that this path's path_out_count is at least the
872 difference between elast->count () and nonpath_count. Otherwise the edge
873 counts after threading will not be sane. */
874 if (local_info
->need_profile_correction
875 && has_joiner
&& path_out_count
< elast
->count () - nonpath_count
)
877 path_out_count
= elast
->count () - nonpath_count
;
878 /* But neither can we go above the minimum count along the path
879 we are duplicating. This can be an issue due to profile
880 insanities coming in to this pass. */
881 if (path_out_count
> min_path_count
)
882 path_out_count
= min_path_count
;
885 *path_in_count_ptr
= path_in_count
;
886 *path_out_count_ptr
= path_out_count
;
891 /* Update the counts and frequencies for both an original path
892 edge EPATH and its duplicate EDUP. The duplicate source block
893 will get a count of PATH_IN_COUNT and PATH_IN_FREQ,
894 and the duplicate edge EDUP will have a count of PATH_OUT_COUNT. */
896 update_profile (edge epath
, edge edup
, profile_count path_in_count
,
897 profile_count path_out_count
)
900 /* First update the duplicated block's count. */
903 basic_block dup_block
= edup
->src
;
905 /* Edup's count is reduced by path_out_count. We need to redistribute
906 probabilities to the remaining edges. */
910 profile_probability edup_prob
911 = path_out_count
.probability_in (path_in_count
);
913 /* Either scale up or down the remaining edges.
914 probabilities are always in range <0,1> and thus we can't do
915 both by same loop. */
916 if (edup
->probability
> edup_prob
)
918 profile_probability rev_scale
919 = (profile_probability::always () - edup
->probability
)
920 / (profile_probability::always () - edup_prob
);
921 FOR_EACH_EDGE (esucc
, ei
, dup_block
->succs
)
923 esucc
->probability
/= rev_scale
;
925 else if (edup
->probability
< edup_prob
)
927 profile_probability scale
928 = (profile_probability::always () - edup_prob
)
929 / (profile_probability::always () - edup
->probability
);
930 FOR_EACH_EDGE (esucc
, ei
, dup_block
->succs
)
932 esucc
->probability
*= scale
;
934 if (edup_prob
.initialized_p ())
935 edup
->probability
= edup_prob
;
937 gcc_assert (!dup_block
->count
.initialized_p ());
938 dup_block
->count
= path_in_count
;
941 if (path_in_count
== profile_count::zero ())
944 profile_count final_count
= epath
->count () - path_out_count
;
946 /* Now update the original block's count in the
947 opposite manner - remove the counts/freq that will flow
948 into the duplicated block. Handle underflow due to precision/
950 epath
->src
->count
-= path_in_count
;
952 /* Next update this path edge's original and duplicated counts. We know
953 that the duplicated path will have path_out_count flowing
954 out of it (in the joiner case this is the count along the duplicated path
955 out of the duplicated joiner). This count can then be removed from the
956 original path edge. */
960 profile_probability epath_prob
= final_count
.probability_in (epath
->src
->count
);
962 if (epath
->probability
> epath_prob
)
964 profile_probability rev_scale
965 = (profile_probability::always () - epath
->probability
)
966 / (profile_probability::always () - epath_prob
);
967 FOR_EACH_EDGE (esucc
, ei
, epath
->src
->succs
)
969 esucc
->probability
/= rev_scale
;
971 else if (epath
->probability
< epath_prob
)
973 profile_probability scale
974 = (profile_probability::always () - epath_prob
)
975 / (profile_probability::always () - epath
->probability
);
976 FOR_EACH_EDGE (esucc
, ei
, epath
->src
->succs
)
978 esucc
->probability
*= scale
;
980 if (epath_prob
.initialized_p ())
981 epath
->probability
= epath_prob
;
984 /* Wire up the outgoing edges from the duplicate blocks and
985 update any PHIs as needed. Also update the profile counts
986 on the original and duplicate blocks and edges. */
988 ssa_fix_duplicate_block_edges (struct redirection_data
*rd
,
989 ssa_local_info_t
*local_info
)
991 bool multi_incomings
= (rd
->incoming_edges
->next
!= NULL
);
992 edge e
= rd
->incoming_edges
->e
;
993 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
994 edge elast
= path
->last ()->e
;
995 profile_count path_in_count
= profile_count::zero ();
996 profile_count path_out_count
= profile_count::zero ();
998 /* First determine how much profile count to move from original
999 path to the duplicate path. This is tricky in the presence of
1000 a joiner (see comments for compute_path_counts), where some portion
1001 of the path's counts will flow off-path from the joiner. In the
1002 non-joiner case the path_in_count and path_out_count should be the
1004 bool has_joiner
= compute_path_counts (rd
, local_info
,
1005 &path_in_count
, &path_out_count
);
1007 for (unsigned int count
= 0, i
= 1; i
< path
->length (); i
++)
1009 edge epath
= (*path
)[i
]->e
;
1011 /* If we were threading through an joiner block, then we want
1012 to keep its control statement and redirect an outgoing edge.
1013 Else we want to remove the control statement & edges, then create
1014 a new outgoing edge. In both cases we may need to update PHIs. */
1015 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1020 gcc_assert (has_joiner
);
1022 /* This updates the PHIs at the destination of the duplicate
1023 block. Pass 0 instead of i if we are threading a path which
1024 has multiple incoming edges. */
1025 update_destination_phis (local_info
->bb
, rd
->dup_blocks
[count
],
1026 path
, multi_incomings
? 0 : i
);
1028 /* Find the edge from the duplicate block to the block we're
1029 threading through. That's the edge we want to redirect. */
1030 victim
= find_edge (rd
->dup_blocks
[count
], (*path
)[i
]->e
->dest
);
1032 /* If there are no remaining blocks on the path to duplicate,
1033 then redirect VICTIM to the final destination of the jump
1035 if (!any_remaining_duplicated_blocks (path
, i
))
1037 e2
= redirect_edge_and_branch (victim
, elast
->dest
);
1038 /* If we redirected the edge, then we need to copy PHI arguments
1039 at the target. If the edge already existed (e2 != victim
1040 case), then the PHIs in the target already have the correct
1043 copy_phi_args (e2
->dest
, elast
, e2
,
1044 path
, multi_incomings
? 0 : i
);
1048 /* Redirect VICTIM to the next duplicated block in the path. */
1049 e2
= redirect_edge_and_branch (victim
, rd
->dup_blocks
[count
+ 1]);
1051 /* We need to update the PHIs in the next duplicated block. We
1052 want the new PHI args to have the same value as they had
1053 in the source of the next duplicate block.
1055 Thus, we need to know which edge we traversed into the
1056 source of the duplicate. Furthermore, we may have
1057 traversed many edges to reach the source of the duplicate.
1059 Walk through the path starting at element I until we
1060 hit an edge marked with EDGE_COPY_SRC_BLOCK. We want
1061 the edge from the prior element. */
1062 for (unsigned int j
= i
+ 1; j
< path
->length (); j
++)
1064 if ((*path
)[j
]->type
== EDGE_COPY_SRC_BLOCK
)
1066 copy_phi_arg_into_existing_phi ((*path
)[j
- 1]->e
, e2
);
1072 /* Update the counts of both the original block
1073 and path edge, and the duplicates. The path duplicate's
1074 incoming count are the totals for all edges
1075 incoming to this jump threading path computed earlier.
1076 And we know that the duplicated path will have path_out_count
1077 flowing out of it (i.e. along the duplicated path out of the
1078 duplicated joiner). */
1079 update_profile (epath
, e2
, path_in_count
, path_out_count
);
1081 else if ((*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
)
1083 remove_ctrl_stmt_and_useless_edges (rd
->dup_blocks
[count
], NULL
);
1084 create_edge_and_update_destination_phis (rd
, rd
->dup_blocks
[count
],
1085 multi_incomings
? 0 : i
);
1087 single_succ_edge (rd
->dup_blocks
[1])->aux
= NULL
;
1089 /* Update the counts of both the original block
1090 and path edge, and the duplicates. Since we are now after
1091 any joiner that may have existed on the path, the count
1092 flowing along the duplicated threaded path is path_out_count.
1093 If we didn't have a joiner, then cur_path_freq was the sum
1094 of the total frequencies along all incoming edges to the
1095 thread path (path_in_freq). If we had a joiner, it would have
1096 been updated at the end of that handling to the edge frequency
1097 along the duplicated joiner path edge. */
1098 update_profile (epath
, EDGE_SUCC (rd
->dup_blocks
[count
], 0),
1099 path_out_count
, path_out_count
);
1103 /* No copy case. In this case we don't have an equivalent block
1104 on the duplicated thread path to update, but we do need
1105 to remove the portion of the counts/freqs that were moved
1106 to the duplicated path from the counts/freqs flowing through
1107 this block on the original path. Since all the no-copy edges
1108 are after any joiner, the removed count is the same as
1111 If we didn't have a joiner, then cur_path_freq was the sum
1112 of the total frequencies along all incoming edges to the
1113 thread path (path_in_freq). If we had a joiner, it would have
1114 been updated at the end of that handling to the edge frequency
1115 along the duplicated joiner path edge. */
1116 update_profile (epath
, NULL
, path_out_count
, path_out_count
);
1119 /* Increment the index into the duplicated path when we processed
1120 a duplicated block. */
1121 if ((*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
1122 || (*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
)
1129 /* Hash table traversal callback routine to create duplicate blocks. */
1132 ssa_create_duplicates (struct redirection_data
**slot
,
1133 ssa_local_info_t
*local_info
)
1135 struct redirection_data
*rd
= *slot
;
1137 /* The second duplicated block in a jump threading path is specific
1138 to the path. So it gets stored in RD rather than in LOCAL_DATA.
1140 Each time we're called, we have to look through the path and see
1141 if a second block needs to be duplicated.
1143 Note the search starts with the third edge on the path. The first
1144 edge is the incoming edge, the second edge always has its source
1145 duplicated. Thus we start our search with the third edge. */
1146 vec
<jump_thread_edge
*> *path
= rd
->path
;
1147 for (unsigned int i
= 2; i
< path
->length (); i
++)
1149 if ((*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
1150 || (*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1152 create_block_for_threading ((*path
)[i
]->e
->src
, rd
, 1,
1153 &local_info
->duplicate_blocks
);
1158 /* Create a template block if we have not done so already. Otherwise
1159 use the template to create a new block. */
1160 if (local_info
->template_block
== NULL
)
1162 create_block_for_threading ((*path
)[1]->e
->src
, rd
, 0,
1163 &local_info
->duplicate_blocks
);
1164 local_info
->template_block
= rd
->dup_blocks
[0];
1165 local_info
->template_last_to_copy
1166 = gsi_last_bb (local_info
->template_block
);
1168 /* We do not create any outgoing edges for the template. We will
1169 take care of that in a later traversal. That way we do not
1170 create edges that are going to just be deleted. */
1174 gimple_seq seq
= NULL
;
1175 if (gsi_stmt (local_info
->template_last_to_copy
)
1176 != gsi_stmt (gsi_last_bb (local_info
->template_block
)))
1178 if (gsi_end_p (local_info
->template_last_to_copy
))
1180 seq
= bb_seq (local_info
->template_block
);
1181 set_bb_seq (local_info
->template_block
, NULL
);
1184 seq
= gsi_split_seq_after (local_info
->template_last_to_copy
);
1186 create_block_for_threading (local_info
->template_block
, rd
, 0,
1187 &local_info
->duplicate_blocks
);
1190 if (gsi_end_p (local_info
->template_last_to_copy
))
1191 set_bb_seq (local_info
->template_block
, seq
);
1193 gsi_insert_seq_after (&local_info
->template_last_to_copy
,
1194 seq
, GSI_SAME_STMT
);
1197 /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
1199 ssa_fix_duplicate_block_edges (rd
, local_info
);
1202 if (MAY_HAVE_DEBUG_STMTS
)
1204 /* Copy debug stmts from each NO_COPY src block to the block
1205 that would have been its predecessor, if we can append to it
1206 (we can't add stmts after a block-ending stmt), or prepending
1207 to the duplicate of the successor, if there is one. If
1208 there's no duplicate successor, we'll mostly drop the blocks
1209 on the floor; propagate_threaded_block_debug_into, called
1210 elsewhere, will consolidate and preserve the effects of the
1211 binds, but none of the markers. */
1212 gimple_stmt_iterator copy_to
= gsi_last_bb (rd
->dup_blocks
[0]);
1213 if (!gsi_end_p (copy_to
))
1215 if (stmt_ends_bb_p (gsi_stmt (copy_to
)))
1217 if (rd
->dup_blocks
[1])
1218 copy_to
= gsi_after_labels (rd
->dup_blocks
[1]);
1220 copy_to
= gsi_none ();
1223 gsi_next (©_to
);
1225 for (unsigned int i
= 2, j
= 0; i
< path
->length (); i
++)
1226 if ((*path
)[i
]->type
== EDGE_NO_COPY_SRC_BLOCK
1227 && gsi_bb (copy_to
))
1229 for (gimple_stmt_iterator gsi
= gsi_start_bb ((*path
)[i
]->e
->src
);
1230 !gsi_end_p (gsi
); gsi_next (&gsi
))
1232 if (!is_gimple_debug (gsi_stmt (gsi
)))
1234 gimple
*stmt
= gsi_stmt (gsi
);
1235 gimple
*copy
= gimple_copy (stmt
);
1236 gsi_insert_before (©_to
, copy
, GSI_SAME_STMT
);
1239 else if ((*path
)[i
]->type
== EDGE_COPY_SRC_BLOCK
1240 || (*path
)[i
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1244 copy_to
= gsi_last_bb (rd
->dup_blocks
[j
]);
1245 if (!gsi_end_p (copy_to
))
1247 if (stmt_ends_bb_p (gsi_stmt (copy_to
)))
1248 copy_to
= gsi_none ();
1250 gsi_next (©_to
);
1255 /* Keep walking the hash table. */
1259 /* We did not create any outgoing edges for the template block during
1260 block creation. This hash table traversal callback creates the
1261 outgoing edge for the template block. */
1264 ssa_fixup_template_block (struct redirection_data
**slot
,
1265 ssa_local_info_t
*local_info
)
1267 struct redirection_data
*rd
= *slot
;
1269 /* If this is the template block halt the traversal after updating
1272 If we were threading through an joiner block, then we want
1273 to keep its control statement and redirect an outgoing edge.
1274 Else we want to remove the control statement & edges, then create
1275 a new outgoing edge. In both cases we may need to update PHIs. */
1276 if (rd
->dup_blocks
[0] && rd
->dup_blocks
[0] == local_info
->template_block
)
1278 ssa_fix_duplicate_block_edges (rd
, local_info
);
1285 /* Hash table traversal callback to redirect each incoming edge
1286 associated with this hash table element to its new destination. */
1289 ssa_redirect_edges (struct redirection_data
**slot
,
1290 ssa_local_info_t
*local_info
)
1292 struct redirection_data
*rd
= *slot
;
1293 struct el
*next
, *el
;
1295 /* Walk over all the incoming edges associated with this hash table
1297 for (el
= rd
->incoming_edges
; el
; el
= next
)
1300 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1302 /* Go ahead and free this element from the list. Doing this now
1303 avoids the need for another list walk when we destroy the hash
1308 local_info
->num_threaded_edges
++;
1310 if (rd
->dup_blocks
[0])
1314 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1315 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
1316 e
->src
->index
, e
->dest
->index
, rd
->dup_blocks
[0]->index
);
1318 /* Redirect the incoming edge (possibly to the joiner block) to the
1319 appropriate duplicate block. */
1320 e2
= redirect_edge_and_branch (e
, rd
->dup_blocks
[0]);
1321 gcc_assert (e
== e2
);
1322 flush_pending_stmts (e2
);
1325 /* Go ahead and clear E->aux. It's not needed anymore and failure
1326 to clear it will cause all kinds of unpleasant problems later. */
1332 /* Indicate that we actually threaded one or more jumps. */
1333 if (rd
->incoming_edges
)
1334 local_info
->jumps_threaded
= true;
1339 /* Return true if this block has no executable statements other than
1340 a simple ctrl flow instruction. When the number of outgoing edges
1341 is one, this is equivalent to a "forwarder" block. */
1344 redirection_block_p (basic_block bb
)
1346 gimple_stmt_iterator gsi
;
1348 /* Advance to the first executable statement. */
1349 gsi
= gsi_start_bb (bb
);
1350 while (!gsi_end_p (gsi
)
1351 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_LABEL
1352 || is_gimple_debug (gsi_stmt (gsi
))
1353 || gimple_nop_p (gsi_stmt (gsi
))
1354 || gimple_clobber_p (gsi_stmt (gsi
))))
1357 /* Check if this is an empty block. */
1358 if (gsi_end_p (gsi
))
1361 /* Test that we've reached the terminating control statement. */
1362 return gsi_stmt (gsi
)
1363 && (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
1364 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_GOTO
1365 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_SWITCH
);
1368 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
1369 is reached via one or more specific incoming edges, we know which
1370 outgoing edge from BB will be traversed.
1372 We want to redirect those incoming edges to the target of the
1373 appropriate outgoing edge. Doing so avoids a conditional branch
1374 and may expose new optimization opportunities. Note that we have
1375 to update dominator tree and SSA graph after such changes.
1377 The key to keeping the SSA graph update manageable is to duplicate
1378 the side effects occurring in BB so that those side effects still
1379 occur on the paths which bypass BB after redirecting edges.
1381 We accomplish this by creating duplicates of BB and arranging for
1382 the duplicates to unconditionally pass control to one specific
1383 successor of BB. We then revector the incoming edges into BB to
1384 the appropriate duplicate of BB.
1386 If NOLOOP_ONLY is true, we only perform the threading as long as it
1387 does not affect the structure of the loops in a nontrivial way.
1389 If JOINERS is true, then thread through joiner blocks as well. */
1392 jump_thread_path_registry::thread_block_1 (basic_block bb
,
1396 /* E is an incoming edge into BB that we may or may not want to
1397 redirect to a duplicate of BB. */
1400 ssa_local_info_t local_info
;
1402 local_info
.duplicate_blocks
= BITMAP_ALLOC (NULL
);
1403 local_info
.need_profile_correction
= false;
1404 local_info
.num_threaded_edges
= 0;
1406 /* To avoid scanning a linear array for the element we need we instead
1407 use a hash table. For normal code there should be no noticeable
1408 difference. However, if we have a block with a large number of
1409 incoming and outgoing edges such linear searches can get expensive. */
1411 = new hash_table
<struct redirection_data
> (EDGE_COUNT (bb
->succs
));
1413 /* Record each unique threaded destination into a hash table for
1414 efficient lookups. */
1416 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1421 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1423 if (((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
&& !joiners
)
1424 || ((*path
)[1]->type
== EDGE_COPY_SRC_BLOCK
&& joiners
))
1427 e2
= path
->last ()->e
;
1428 if (!e2
|| noloop_only
)
1430 /* If NOLOOP_ONLY is true, we only allow threading through the
1431 header of a loop to exit edges. */
1433 /* One case occurs when there was loop header buried in a jump
1434 threading path that crosses loop boundaries. We do not try
1435 and thread this elsewhere, so just cancel the jump threading
1436 request by clearing the AUX field now. */
1437 if (bb
->loop_father
!= e2
->src
->loop_father
1438 && (!loop_exit_edge_p (e2
->src
->loop_father
, e2
)
1439 || flow_loop_nested_p (bb
->loop_father
,
1440 e2
->dest
->loop_father
)))
1442 /* Since this case is not handled by our special code
1443 to thread through a loop header, we must explicitly
1444 cancel the threading request here. */
1450 /* Another case occurs when trying to thread through our
1451 own loop header, possibly from inside the loop. We will
1452 thread these later. */
1454 for (i
= 1; i
< path
->length (); i
++)
1456 if ((*path
)[i
]->e
->src
== bb
->loop_father
->header
1457 && (!loop_exit_edge_p (bb
->loop_father
, e2
)
1458 || (*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
))
1462 if (i
!= path
->length ())
1465 /* Loop parallelization can be confused by the result of
1466 threading through the loop exit test back into the loop.
1467 However, theading those jumps seems to help other codes.
1469 I have been unable to find anything related to the shape of
1470 the CFG, the contents of the affected blocks, etc which would
1471 allow a more sensible test than what we're using below which
1472 merely avoids the optimization when parallelizing loops. */
1473 if (flag_tree_parallelize_loops
> 1)
1475 for (i
= 1; i
< path
->length (); i
++)
1476 if (bb
->loop_father
== e2
->src
->loop_father
1477 && loop_exits_from_bb_p (bb
->loop_father
,
1479 && !loop_exit_edge_p (bb
->loop_father
, e2
))
1482 if (i
!= path
->length ())
1491 /* Insert the outgoing edge into the hash table if it is not
1492 already in the hash table. */
1493 lookup_redirection_data (e
, INSERT
);
1495 /* When we have thread paths through a common joiner with different
1496 final destinations, then we may need corrections to deal with
1497 profile insanities. See the big comment before compute_path_counts. */
1498 if ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1502 else if (e2
!= last
)
1503 local_info
.need_profile_correction
= true;
1507 /* We do not update dominance info. */
1508 free_dominance_info (CDI_DOMINATORS
);
1510 /* We know we only thread through the loop header to loop exits.
1511 Let the basic block duplication hook know we are not creating
1512 a multiple entry loop. */
1514 && bb
== bb
->loop_father
->header
)
1515 set_loop_copy (bb
->loop_father
, loop_outer (bb
->loop_father
));
1517 /* Now create duplicates of BB.
1519 Note that for a block with a high outgoing degree we can waste
1520 a lot of time and memory creating and destroying useless edges.
1522 So we first duplicate BB and remove the control structure at the
1523 tail of the duplicate as well as all outgoing edges from the
1524 duplicate. We then use that duplicate block as a template for
1525 the rest of the duplicates. */
1526 local_info
.template_block
= NULL
;
1528 local_info
.jumps_threaded
= false;
1529 m_redirection_data
->traverse
<ssa_local_info_t
*, ssa_create_duplicates
>
1532 /* The template does not have an outgoing edge. Create that outgoing
1533 edge and update PHI nodes as the edge's target as necessary.
1535 We do this after creating all the duplicates to avoid creating
1536 unnecessary edges. */
1537 m_redirection_data
->traverse
<ssa_local_info_t
*, ssa_fixup_template_block
>
1540 /* The hash table traversals above created the duplicate blocks (and the
1541 statements within the duplicate blocks). This loop creates PHI nodes for
1542 the duplicated blocks and redirects the incoming edges into BB to reach
1543 the duplicates of BB. */
1544 m_redirection_data
->traverse
<ssa_local_info_t
*, ssa_redirect_edges
>
1547 /* Done with this block. Clear REDIRECTION_DATA. */
1548 delete m_redirection_data
;
1549 m_redirection_data
= NULL
;
1552 && bb
== bb
->loop_father
->header
)
1553 set_loop_copy (bb
->loop_father
, NULL
);
1555 BITMAP_FREE (local_info
.duplicate_blocks
);
1556 local_info
.duplicate_blocks
= NULL
;
1558 m_num_threaded_edges
+= local_info
.num_threaded_edges
;
1560 /* Indicate to our caller whether or not any jumps were threaded. */
1561 return local_info
.jumps_threaded
;
1564 /* Wrapper for thread_block_1 so that we can first handle jump
1565 thread paths which do not involve copying joiner blocks, then
1566 handle jump thread paths which have joiner blocks.
1568 By doing things this way we can be as aggressive as possible and
1569 not worry that copying a joiner block will create a jump threading
1573 jump_thread_path_registry::thread_block (basic_block bb
, bool noloop_only
)
1576 retval
= thread_block_1 (bb
, noloop_only
, false);
1577 retval
|= thread_block_1 (bb
, noloop_only
, true);
1581 /* Callback for dfs_enumerate_from. Returns true if BB is different
1582 from STOP and DBDS_CE_STOP. */
1584 static basic_block dbds_ce_stop
;
1586 dbds_continue_enumeration_p (const_basic_block bb
, const void *stop
)
1588 return (bb
!= (const_basic_block
) stop
1589 && bb
!= dbds_ce_stop
);
1592 /* Evaluates the dominance relationship of latch of the LOOP and BB, and
1593 returns the state. */
1596 determine_bb_domination_status (class loop
*loop
, basic_block bb
)
1598 basic_block
*bblocks
;
1599 unsigned nblocks
, i
;
1600 bool bb_reachable
= false;
1604 /* This function assumes BB is a successor of LOOP->header.
1605 If that is not the case return DOMST_NONDOMINATING which
1610 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1612 if (e
->src
== loop
->header
)
1620 return DOMST_NONDOMINATING
;
1623 if (bb
== loop
->latch
)
1624 return DOMST_DOMINATING
;
1626 /* Check that BB dominates LOOP->latch, and that it is back-reachable
1629 bblocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1630 dbds_ce_stop
= loop
->header
;
1631 nblocks
= dfs_enumerate_from (loop
->latch
, 1, dbds_continue_enumeration_p
,
1632 bblocks
, loop
->num_nodes
, bb
);
1633 for (i
= 0; i
< nblocks
; i
++)
1634 FOR_EACH_EDGE (e
, ei
, bblocks
[i
]->preds
)
1636 if (e
->src
== loop
->header
)
1639 return DOMST_NONDOMINATING
;
1642 bb_reachable
= true;
1646 return (bb_reachable
? DOMST_DOMINATING
: DOMST_LOOP_BROKEN
);
1649 /* Thread jumps through the header of LOOP. Returns true if cfg changes.
1650 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
1651 to the inside of the loop. */
1654 jump_thread_path_registry::thread_through_loop_header
1656 bool may_peel_loop_headers
)
1658 basic_block header
= loop
->header
;
1659 edge e
, tgt_edge
, latch
= loop_latch_edge (loop
);
1661 basic_block tgt_bb
, atgt_bb
;
1662 enum bb_dom_status domst
;
1664 /* We have already threaded through headers to exits, so all the threading
1665 requests now are to the inside of the loop. We need to avoid creating
1666 irreducible regions (i.e., loops with more than one entry block), and
1667 also loop with several latch edges, or new subloops of the loop (although
1668 there are cases where it might be appropriate, it is difficult to decide,
1669 and doing it wrongly may confuse other optimizers).
1671 We could handle more general cases here. However, the intention is to
1672 preserve some information about the loop, which is impossible if its
1673 structure changes significantly, in a way that is not well understood.
1674 Thus we only handle few important special cases, in which also updating
1675 of the loop-carried information should be feasible:
1677 1) Propagation of latch edge to a block that dominates the latch block
1678 of a loop. This aims to handle the following idiom:
1689 After threading the latch edge, this becomes
1700 The original header of the loop is moved out of it, and we may thread
1701 the remaining edges through it without further constraints.
1703 2) All entry edges are propagated to a single basic block that dominates
1704 the latch block of the loop. This aims to handle the following idiom
1705 (normally created for "for" loops):
1728 /* Threading through the header won't improve the code if the header has just
1730 if (single_succ_p (header
))
1733 if (!may_peel_loop_headers
&& !redirection_block_p (loop
->header
))
1739 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1746 /* If latch is not threaded, and there is a header
1747 edge that is not threaded, we would create loop
1748 with multiple entries. */
1752 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1754 if ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1756 tgt_edge
= (*path
)[1]->e
;
1757 atgt_bb
= tgt_edge
->dest
;
1760 /* Two targets of threading would make us create loop
1761 with multiple entries. */
1762 else if (tgt_bb
!= atgt_bb
)
1768 /* There are no threading requests. */
1772 /* Redirecting to empty loop latch is useless. */
1773 if (tgt_bb
== loop
->latch
1774 && empty_block_p (loop
->latch
))
1778 /* The target block must dominate the loop latch, otherwise we would be
1779 creating a subloop. */
1780 domst
= determine_bb_domination_status (loop
, tgt_bb
);
1781 if (domst
== DOMST_NONDOMINATING
)
1783 if (domst
== DOMST_LOOP_BROKEN
)
1785 /* If the loop ceased to exist, mark it as such, and thread through its
1787 mark_loop_for_removal (loop
);
1788 return thread_block (header
, false);
1791 if (tgt_bb
->loop_father
->header
== tgt_bb
)
1793 /* If the target of the threading is a header of a subloop, we need
1794 to create a preheader for it, so that the headers of the two loops
1796 if (EDGE_COUNT (tgt_bb
->preds
) > 2)
1798 tgt_bb
= create_preheader (tgt_bb
->loop_father
, 0);
1799 gcc_assert (tgt_bb
!= NULL
);
1802 tgt_bb
= split_edge (tgt_edge
);
1805 basic_block new_preheader
;
1807 /* Now consider the case entry edges are redirected to the new entry
1808 block. Remember one entry edge, so that we can find the new
1809 preheader (its destination after threading). */
1810 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1816 /* The duplicate of the header is the new preheader of the loop. Ensure
1817 that it is placed correctly in the loop hierarchy. */
1818 set_loop_copy (loop
, loop_outer (loop
));
1820 thread_block (header
, false);
1821 set_loop_copy (loop
, NULL
);
1822 new_preheader
= e
->dest
;
1824 /* Create the new latch block. This is always necessary, as the latch
1825 must have only a single successor, but the original header had at
1826 least two successors. */
1828 mfb_kj_edge
= single_succ_edge (new_preheader
);
1829 loop
->header
= mfb_kj_edge
->dest
;
1830 latch
= make_forwarder_block (tgt_bb
, mfb_keep_just
, NULL
);
1831 loop
->header
= latch
->dest
;
1832 loop
->latch
= latch
->src
;
1836 /* We failed to thread anything. Cancel the requests. */
1837 FOR_EACH_EDGE (e
, ei
, header
->preds
)
1839 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
1850 /* E1 and E2 are edges into the same basic block. Return TRUE if the
1851 PHI arguments associated with those edges are equal or there are no
1852 PHI arguments, otherwise return FALSE. */
1855 phi_args_equal_on_edges (edge e1
, edge e2
)
1858 int indx1
= e1
->dest_idx
;
1859 int indx2
= e2
->dest_idx
;
1861 for (gsi
= gsi_start_phis (e1
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1863 gphi
*phi
= gsi
.phi ();
1865 if (!operand_equal_p (gimple_phi_arg_def (phi
, indx1
),
1866 gimple_phi_arg_def (phi
, indx2
), 0))
1872 /* Return the number of non-debug statements and non-virtual PHIs in a
1876 count_stmts_and_phis_in_block (basic_block bb
)
1878 unsigned int num_stmts
= 0;
1881 for (gpi
= gsi_start_phis (bb
); !gsi_end_p (gpi
); gsi_next (&gpi
))
1882 if (!virtual_operand_p (PHI_RESULT (gpi
.phi ())))
1885 gimple_stmt_iterator gsi
;
1886 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1888 gimple
*stmt
= gsi_stmt (gsi
);
1889 if (!is_gimple_debug (stmt
))
1897 /* Walk through the registered jump threads and convert them into a
1898 form convenient for this pass.
1900 Any block which has incoming edges threaded to outgoing edges
1901 will have its entry in THREADED_BLOCK set.
1903 Any threaded edge will have its new outgoing edge stored in the
1904 original edge's AUX field.
1906 This form avoids the need to walk all the edges in the CFG to
1907 discover blocks which need processing and avoids unnecessary
1908 hash table lookups to map from threaded edge to new target. */
1911 jump_thread_path_registry::mark_threaded_blocks (bitmap threaded_blocks
)
1920 /* It is possible to have jump threads in which one is a subpath
1921 of the other. ie, (A, B), (B, C), (C, D) where B is a joiner
1922 block and (B, C), (C, D) where no joiner block exists.
1924 When this occurs ignore the jump thread request with the joiner
1925 block. It's totally subsumed by the simpler jump thread request.
1927 This results in less block copying, simpler CFGs. More importantly,
1928 when we duplicate the joiner block, B, in this case we will create
1929 a new threading opportunity that we wouldn't be able to optimize
1930 until the next jump threading iteration.
1932 So first convert the jump thread requests which do not require a
1934 for (i
= 0; i
< m_paths
.length (); i
++)
1936 vec
<jump_thread_edge
*> *path
= m_paths
[i
];
1938 if (path
->length () > 1
1939 && (*path
)[1]->type
!= EDGE_COPY_SRC_JOINER_BLOCK
)
1941 edge e
= (*path
)[0]->e
;
1942 e
->aux
= (void *)path
;
1943 bitmap_set_bit (tmp
, e
->dest
->index
);
1947 /* Now iterate again, converting cases where we want to thread
1948 through a joiner block, but only if no other edge on the path
1949 already has a jump thread attached to it. We do this in two passes,
1950 to avoid situations where the order in the paths vec can hide overlapping
1951 threads (the path is recorded on the incoming edge, so we would miss
1952 cases where the second path starts at a downstream edge on the same
1953 path). First record all joiner paths, deleting any in the unexpected
1954 case where there is already a path for that incoming edge. */
1955 for (i
= 0; i
< m_paths
.length ();)
1957 vec
<jump_thread_edge
*> *path
= m_paths
[i
];
1959 if (path
->length () > 1
1960 && (*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
)
1962 /* Attach the path to the starting edge if none is yet recorded. */
1963 if ((*path
)[0]->e
->aux
== NULL
)
1965 (*path
)[0]->e
->aux
= path
;
1970 m_paths
.unordered_remove (i
);
1971 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1972 dump_jump_thread_path (dump_file
, *path
, false);
1982 /* Second, look for paths that have any other jump thread attached to
1983 them, and either finish converting them or cancel them. */
1984 for (i
= 0; i
< m_paths
.length ();)
1986 vec
<jump_thread_edge
*> *path
= m_paths
[i
];
1987 edge e
= (*path
)[0]->e
;
1989 if (path
->length () > 1
1990 && (*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
&& e
->aux
== path
)
1993 for (j
= 1; j
< path
->length (); j
++)
1994 if ((*path
)[j
]->e
->aux
!= NULL
)
1997 /* If we iterated through the entire path without exiting the loop,
1998 then we are good to go, record it. */
1999 if (j
== path
->length ())
2001 bitmap_set_bit (tmp
, e
->dest
->index
);
2007 m_paths
.unordered_remove (i
);
2008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2009 dump_jump_thread_path (dump_file
, *path
, false);
2019 /* When optimizing for size, prune all thread paths where statement
2020 duplication is necessary.
2022 We walk the jump thread path looking for copied blocks. There's
2023 two types of copied blocks.
2025 EDGE_COPY_SRC_JOINER_BLOCK is always copied and thus we will
2026 cancel the jump threading request when optimizing for size.
2028 EDGE_COPY_SRC_BLOCK which is copied, but some of its statements
2029 will be killed by threading. If threading does not kill all of
2030 its statements, then we should cancel the jump threading request
2031 when optimizing for size. */
2032 if (optimize_function_for_size_p (cfun
))
2034 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2036 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, i
)->preds
)
2039 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
2042 for (j
= 1; j
< path
->length (); j
++)
2044 bb
= (*path
)[j
]->e
->src
;
2045 if (redirection_block_p (bb
))
2047 else if ((*path
)[j
]->type
== EDGE_COPY_SRC_JOINER_BLOCK
2048 || ((*path
)[j
]->type
== EDGE_COPY_SRC_BLOCK
2049 && (count_stmts_and_phis_in_block (bb
)
2050 != estimate_threading_killed_stmts (bb
))))
2054 if (j
!= path
->length ())
2056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2057 dump_jump_thread_path (dump_file
, *path
, false);
2062 bitmap_set_bit (threaded_blocks
, i
);
2067 bitmap_copy (threaded_blocks
, tmp
);
2069 /* If we have a joiner block (J) which has two successors S1 and S2 and
2070 we are threading though S1 and the final destination of the thread
2071 is S2, then we must verify that any PHI nodes in S2 have the same
2072 PHI arguments for the edge J->S2 and J->S1->...->S2.
2074 We used to detect this prior to registering the jump thread, but
2075 that prohibits propagation of edge equivalences into non-dominated
2076 PHI nodes as the equivalency test might occur before propagation.
2078 This must also occur after we truncate any jump threading paths
2079 as this scenario may only show up after truncation.
2081 This works for now, but will need improvement as part of the FSA
2084 Note since we've moved the thread request data to the edges,
2085 we have to iterate on those rather than the threaded_edges vector. */
2086 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2088 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2089 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2093 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
2094 bool have_joiner
= ((*path
)[1]->type
== EDGE_COPY_SRC_JOINER_BLOCK
);
2098 basic_block joiner
= e
->dest
;
2099 edge final_edge
= path
->last ()->e
;
2100 basic_block final_dest
= final_edge
->dest
;
2101 edge e2
= find_edge (joiner
, final_dest
);
2103 if (e2
&& !phi_args_equal_on_edges (e2
, final_edge
))
2113 /* Look for jump threading paths which cross multiple loop headers.
2115 The code to thread through loop headers will change the CFG in ways
2116 that invalidate the cached loop iteration information. So we must
2117 detect that case and wipe the cached information. */
2118 EXECUTE_IF_SET_IN_BITMAP (tmp
, 0, i
, bi
)
2120 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2121 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2125 vec
<jump_thread_edge
*> *path
= THREAD_PATH (e
);
2127 for (unsigned int i
= 0, crossed_headers
= 0;
2128 i
< path
->length ();
2131 basic_block dest
= (*path
)[i
]->e
->dest
;
2132 basic_block src
= (*path
)[i
]->e
->src
;
2133 /* If we enter a loop. */
2134 if (flow_loop_nested_p (src
->loop_father
, dest
->loop_father
))
2136 /* If we step from a block outside an irreducible region
2137 to a block inside an irreducible region, then we have
2138 crossed into a loop. */
2139 else if (! (src
->flags
& BB_IRREDUCIBLE_LOOP
)
2140 && (dest
->flags
& BB_IRREDUCIBLE_LOOP
))
2142 if (crossed_headers
> 1)
2144 vect_free_loop_info_assumptions
2145 ((*path
)[path
->length () - 1]->e
->dest
->loop_father
);
2155 /* Verify that the REGION is a valid jump thread. A jump thread is a special
2156 case of SEME Single Entry Multiple Exits region in which all nodes in the
2157 REGION have exactly one incoming edge. The only exception is the first block
2158 that may not have been connected to the rest of the cfg yet. */
2161 verify_jump_thread (basic_block
*region
, unsigned n_region
)
2163 for (unsigned i
= 0; i
< n_region
; i
++)
2164 gcc_assert (EDGE_COUNT (region
[i
]->preds
) <= 1);
2167 /* Return true when BB is one of the first N items in BBS. */
2170 bb_in_bbs (basic_block bb
, basic_block
*bbs
, int n
)
2172 for (int i
= 0; i
< n
; i
++)
2180 jump_thread_path_registry::debug_path (FILE *dump_file
, int pathno
)
2182 vec
<jump_thread_edge
*> *p
= m_paths
[pathno
];
2183 fprintf (dump_file
, "path: ");
2184 for (unsigned i
= 0; i
< p
->length (); ++i
)
2185 fprintf (dump_file
, "%d -> %d, ",
2186 (*p
)[i
]->e
->src
->index
, (*p
)[i
]->e
->dest
->index
);
2187 fprintf (dump_file
, "\n");
2191 jump_thread_path_registry::dump ()
2193 for (unsigned i
= 0; i
< m_paths
.length (); ++i
)
2194 debug_path (stderr
, i
);
2197 /* Rewire a jump_thread_edge so that the source block is now a
2198 threaded source block.
2200 PATH_NUM is an index into the global path table PATHS.
2201 EDGE_NUM is the jump thread edge number into said path.
2203 Returns TRUE if we were able to successfully rewire the edge. */
2206 jump_thread_path_registry::rewire_first_differing_edge (unsigned path_num
,
2209 vec
<jump_thread_edge
*> *path
= m_paths
[path_num
];
2210 edge
&e
= (*path
)[edge_num
]->e
;
2211 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2212 fprintf (dump_file
, "rewiring edge candidate: %d -> %d\n",
2213 e
->src
->index
, e
->dest
->index
);
2214 basic_block src_copy
= get_bb_copy (e
->src
);
2215 if (src_copy
== NULL
)
2217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2218 fprintf (dump_file
, "ignoring candidate: there is no src COPY\n");
2221 edge new_edge
= find_edge (src_copy
, e
->dest
);
2222 /* If the previously threaded paths created a flow graph where we
2223 can no longer figure out where to go, give up. */
2224 if (new_edge
== NULL
)
2226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2227 fprintf (dump_file
, "ignoring candidate: we lost our way\n");
2234 /* After an FSM path has been jump threaded, adjust the remaining FSM
2235 paths that are subsets of this path, so these paths can be safely
2236 threaded within the context of the new threaded path.
2238 For example, suppose we have just threaded:
2240 5 -> 6 -> 7 -> 8 -> 12 => 5 -> 6' -> 7' -> 8' -> 12'
2242 And we have an upcoming threading candidate:
2243 5 -> 6 -> 7 -> 8 -> 15 -> 20
2245 This function adjusts the upcoming path into:
2248 CURR_PATH_NUM is an index into the global paths table. It
2249 specifies the path that was just threaded. */
2252 jump_thread_path_registry::adjust_paths_after_duplication
2253 (unsigned curr_path_num
)
2255 vec
<jump_thread_edge
*> *curr_path
= m_paths
[curr_path_num
];
2256 gcc_assert ((*curr_path
)[0]->type
== EDGE_FSM_THREAD
);
2258 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2260 fprintf (dump_file
, "just threaded: ");
2261 debug_path (dump_file
, curr_path_num
);
2264 /* Iterate through all the other paths and adjust them. */
2265 for (unsigned cand_path_num
= 0; cand_path_num
< m_paths
.length (); )
2267 if (cand_path_num
== curr_path_num
)
2272 /* Make sure the candidate to adjust starts with the same path
2273 as the recently threaded path and is an FSM thread. */
2274 vec
<jump_thread_edge
*> *cand_path
= m_paths
[cand_path_num
];
2275 if ((*cand_path
)[0]->type
!= EDGE_FSM_THREAD
2276 || (*cand_path
)[0]->e
!= (*curr_path
)[0]->e
)
2281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2283 fprintf (dump_file
, "adjusting candidate: ");
2284 debug_path (dump_file
, cand_path_num
);
2287 /* Chop off from the candidate path any prefix it shares with
2288 the recently threaded path. */
2289 unsigned minlength
= MIN (curr_path
->length (), cand_path
->length ());
2291 for (j
= 0; j
< minlength
; ++j
)
2293 edge cand_edge
= (*cand_path
)[j
]->e
;
2294 edge curr_edge
= (*curr_path
)[j
]->e
;
2296 /* Once the prefix no longer matches, adjust the first
2297 non-matching edge to point from an adjusted edge to
2298 wherever it was going. */
2299 if (cand_edge
!= curr_edge
)
2301 gcc_assert (cand_edge
->src
== curr_edge
->src
);
2302 if (!rewire_first_differing_edge (cand_path_num
, j
))
2303 goto remove_candidate_from_list
;
2309 /* If we consumed the max subgraph we could look at, and
2310 still didn't find any different edges, it's the
2311 last edge after MINLENGTH. */
2312 if (cand_path
->length () > minlength
)
2314 if (!rewire_first_differing_edge (cand_path_num
, j
))
2315 goto remove_candidate_from_list
;
2317 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2318 fprintf (dump_file
, "adjusting first edge after MINLENGTH.\n");
2322 /* If we are removing everything, delete the entire candidate. */
2323 if (j
== cand_path
->length ())
2325 remove_candidate_from_list
:
2326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2327 fprintf (dump_file
, "adjusted candidate: [EMPTY]\n");
2328 cand_path
->release ();
2329 m_paths
.unordered_remove (cand_path_num
);
2332 /* Otherwise, just remove the redundant sub-path. */
2333 cand_path
->block_remove (0, j
);
2335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2337 fprintf (dump_file
, "adjusted candidate: ");
2338 debug_path (dump_file
, cand_path_num
);
2344 /* Duplicates a jump-thread path of N_REGION basic blocks.
2345 The ENTRY edge is redirected to the duplicate of the region.
2347 Remove the last conditional statement in the last basic block in the REGION,
2348 and create a single fallthru edge pointing to the same destination as the
2351 CURRENT_PATH_NO is an index into the global paths[] table
2352 specifying the jump-thread path.
2354 Returns false if it is unable to copy the region, true otherwise. */
2357 jump_thread_path_registry::duplicate_thread_path (edge entry
,
2359 basic_block
*region
,
2361 unsigned current_path_no
)
2364 class loop
*loop
= entry
->dest
->loop_father
;
2367 profile_count curr_count
;
2369 if (!can_copy_bbs_p (region
, n_region
))
2372 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2374 fprintf (dump_file
, "\nabout to thread: ");
2375 debug_path (dump_file
, current_path_no
);
2378 /* Some sanity checking. Note that we do not check for all possible
2379 missuses of the functions. I.e. if you ask to copy something weird,
2380 it will work, but the state of structures probably will not be
2382 for (i
= 0; i
< n_region
; i
++)
2384 /* We do not handle subloops, i.e. all the blocks must belong to the
2386 if (region
[i
]->loop_father
!= loop
)
2390 initialize_original_copy_tables ();
2392 set_loop_copy (loop
, loop
);
2394 basic_block
*region_copy
= XNEWVEC (basic_block
, n_region
);
2395 copy_bbs (region
, n_region
, region_copy
, &exit
, 1, &exit_copy
, loop
,
2396 split_edge_bb_loc (entry
), false);
2398 /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The
2399 following code ensures that all the edges exiting the jump-thread path are
2400 redirected back to the original code: these edges are exceptions
2401 invalidating the property that is propagated by executing all the blocks of
2402 the jump-thread path in order. */
2404 curr_count
= entry
->count ();
2406 for (i
= 0; i
< n_region
; i
++)
2410 basic_block bb
= region_copy
[i
];
2412 /* Watch inconsistent profile. */
2413 if (curr_count
> region
[i
]->count
)
2414 curr_count
= region
[i
]->count
;
2415 /* Scale current BB. */
2416 if (region
[i
]->count
.nonzero_p () && curr_count
.initialized_p ())
2418 /* In the middle of the path we only scale the frequencies.
2419 In last BB we need to update probabilities of outgoing edges
2420 because we know which one is taken at the threaded path. */
2421 if (i
+ 1 != n_region
)
2422 scale_bbs_frequencies_profile_count (region
+ i
, 1,
2423 region
[i
]->count
- curr_count
,
2426 update_bb_profile_for_threading (region
[i
],
2429 scale_bbs_frequencies_profile_count (region_copy
+ i
, 1, curr_count
,
2430 region_copy
[i
]->count
);
2433 if (single_succ_p (bb
))
2435 /* Make sure the successor is the next node in the path. */
2436 gcc_assert (i
+ 1 == n_region
2437 || region_copy
[i
+ 1] == single_succ_edge (bb
)->dest
);
2438 if (i
+ 1 != n_region
)
2440 curr_count
= single_succ_edge (bb
)->count ();
2445 /* Special case the last block on the path: make sure that it does not
2446 jump back on the copied path, including back to itself. */
2447 if (i
+ 1 == n_region
)
2449 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2450 if (bb_in_bbs (e
->dest
, region_copy
, n_region
))
2452 basic_block orig
= get_bb_original (e
->dest
);
2454 redirect_edge_and_branch_force (e
, orig
);
2459 /* Redirect all other edges jumping to non-adjacent blocks back to the
2461 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2462 if (region_copy
[i
+ 1] != e
->dest
)
2464 basic_block orig
= get_bb_original (e
->dest
);
2466 redirect_edge_and_branch_force (e
, orig
);
2470 curr_count
= e
->count ();
2476 verify_jump_thread (region_copy
, n_region
);
2478 /* Remove the last branch in the jump thread path. */
2479 remove_ctrl_stmt_and_useless_edges (region_copy
[n_region
- 1], exit
->dest
);
2481 /* And fixup the flags on the single remaining edge. */
2482 edge fix_e
= find_edge (region_copy
[n_region
- 1], exit
->dest
);
2483 fix_e
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
| EDGE_ABNORMAL
);
2484 fix_e
->flags
|= EDGE_FALLTHRU
;
2486 edge e
= make_edge (region_copy
[n_region
- 1], exit
->dest
, EDGE_FALLTHRU
);
2490 rescan_loop_exit (e
, true, false);
2491 e
->probability
= profile_probability::always ();
2494 /* Redirect the entry and add the phi node arguments. */
2495 if (entry
->dest
== loop
->header
)
2496 mark_loop_for_removal (loop
);
2497 redirected
= redirect_edge_and_branch (entry
, get_bb_copy (entry
->dest
));
2498 gcc_assert (redirected
!= NULL
);
2499 flush_pending_stmts (entry
);
2501 /* Add the other PHI node arguments. */
2502 add_phi_args_after_copy (region_copy
, n_region
, NULL
);
2506 adjust_paths_after_duplication (current_path_no
);
2508 free_original_copy_tables ();
2512 /* Return true when PATH is a valid jump-thread path. */
2515 valid_jump_thread_path (vec
<jump_thread_edge
*> *path
)
2517 unsigned len
= path
->length ();
2519 /* Check that the path is connected. */
2520 for (unsigned int j
= 0; j
< len
- 1; j
++)
2522 edge e
= (*path
)[j
]->e
;
2523 if (e
->dest
!= (*path
)[j
+1]->e
->src
)
2529 /* Remove any queued jump threads that include edge E.
2531 We don't actually remove them here, just record the edges into ax
2532 hash table. That way we can do the search once per iteration of
2533 DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR. */
2536 jump_thread_path_registry::remove_jump_threads_including (edge_def
*e
)
2538 if (!m_paths
.exists ())
2541 edge
*slot
= m_removed_edges
->find_slot (e
, INSERT
);
2545 /* Walk through all blocks and thread incoming edges to the appropriate
2546 outgoing edge for each edge pair recorded in THREADED_EDGES.
2548 It is the caller's responsibility to fix the dominance information
2549 and rewrite duplicated SSA_NAMEs back into SSA form.
2551 If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
2552 loop headers if it does not simplify the loop.
2554 Returns true if one or more edges were threaded, false otherwise. */
2557 jump_thread_path_registry::thread_through_all_blocks
2558 (bool may_peel_loop_headers
)
2560 bool retval
= false;
2563 auto_bitmap threaded_blocks
;
2564 hash_set
<edge
> visited_starting_edges
;
2566 if (!m_paths
.exists ())
2572 m_num_threaded_edges
= 0;
2574 /* Remove any paths that referenced removed edges. */
2575 if (m_removed_edges
)
2576 for (i
= 0; i
< m_paths
.length (); )
2579 vec
<jump_thread_edge
*> *path
= m_paths
[i
];
2581 for (j
= 0; j
< path
->length (); j
++)
2583 edge e
= (*path
)[j
]->e
;
2584 if (m_removed_edges
->find_slot (e
, NO_INSERT
))
2588 if (j
!= path
->length ())
2591 m_paths
.unordered_remove (i
);
2597 /* Jump-thread all FSM threads before other jump-threads. */
2598 for (i
= 0; i
< m_paths
.length ();)
2600 vec
<jump_thread_edge
*> *path
= m_paths
[i
];
2601 edge entry
= (*path
)[0]->e
;
2603 /* Only code-generate FSM jump-threads in this loop. */
2604 if ((*path
)[0]->type
!= EDGE_FSM_THREAD
)
2610 /* Do not jump-thread twice from the same starting edge.
2612 Previously we only checked that we weren't threading twice
2613 from the same BB, but that was too restrictive. Imagine a
2614 path that starts from GIMPLE_COND(x_123 == 0,...), where both
2615 edges out of this conditional yield paths that can be
2616 threaded (for example, both lead to an x_123==0 or x_123!=0
2617 conditional further down the line. */
2618 if (visited_starting_edges
.contains (entry
)
2619 /* We may not want to realize this jump thread path for
2620 various reasons. So check it first. */
2621 || !valid_jump_thread_path (path
))
2623 /* Remove invalid FSM jump-thread paths. */
2625 m_paths
.unordered_remove (i
);
2629 unsigned len
= path
->length ();
2630 edge exit
= (*path
)[len
- 1]->e
;
2631 basic_block
*region
= XNEWVEC (basic_block
, len
- 1);
2633 for (unsigned int j
= 0; j
< len
- 1; j
++)
2634 region
[j
] = (*path
)[j
]->e
->dest
;
2636 if (duplicate_thread_path (entry
, exit
, region
, len
- 1, i
))
2638 /* We do not update dominance info. */
2639 free_dominance_info (CDI_DOMINATORS
);
2640 visited_starting_edges
.add (entry
);
2642 m_num_threaded_edges
++;
2646 m_paths
.unordered_remove (i
);
2650 /* Remove from PATHS all the jump-threads starting with an edge already
2652 for (i
= 0; i
< m_paths
.length ();)
2654 vec
<jump_thread_edge
*> *path
= m_paths
[i
];
2655 edge entry
= (*path
)[0]->e
;
2657 /* Do not jump-thread twice from the same block. */
2658 if (visited_starting_edges
.contains (entry
))
2661 m_paths
.unordered_remove (i
);
2667 mark_threaded_blocks (threaded_blocks
);
2669 initialize_original_copy_tables ();
2671 /* The order in which we process jump threads can be important.
2673 Consider if we have two jump threading paths A and B. If the
2674 target edge of A is the starting edge of B and we thread path A
2675 first, then we create an additional incoming edge into B->dest that
2676 we cannot discover as a jump threading path on this iteration.
2678 If we instead thread B first, then the edge into B->dest will have
2679 already been redirected before we process path A and path A will
2680 natually, with no further work, target the redirected path for B.
2682 An post-order is sufficient here. Compute the ordering first, then
2683 process the blocks. */
2684 if (!bitmap_empty_p (threaded_blocks
))
2686 int *postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
2687 unsigned int postorder_num
= post_order_compute (postorder
, false, false);
2688 for (unsigned int i
= 0; i
< postorder_num
; i
++)
2690 unsigned int indx
= postorder
[i
];
2691 if (bitmap_bit_p (threaded_blocks
, indx
))
2693 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, indx
);
2694 retval
|= thread_block (bb
, true);
2700 /* Then perform the threading through loop headers. We start with the
2701 innermost loop, so that the changes in cfg we perform won't affect
2702 further threading. */
2703 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2706 || !bitmap_bit_p (threaded_blocks
, loop
->header
->index
))
2709 retval
|= thread_through_loop_header (loop
, may_peel_loop_headers
);
2712 /* All jump threading paths should have been resolved at this
2713 point. Verify that is the case. */
2715 FOR_EACH_BB_FN (bb
, cfun
)
2719 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2720 gcc_assert (e
->aux
== NULL
);
2723 statistics_counter_event (cfun
, "Jumps threaded", m_num_threaded_edges
);
2725 free_original_copy_tables ();
2730 loops_state_set (LOOPS_NEED_FIXUP
);
2736 /* Register a jump threading opportunity. We queue up all the jump
2737 threading opportunities discovered by a pass and update the CFG
2738 and SSA form all at once.
2740 E is the edge we can thread, E2 is the new target edge, i.e., we
2741 are effectively recording that E->dest can be changed to E2->dest
2742 after fixing the SSA graph. */
2745 jump_thread_path_registry::register_jump_thread (vec
<jump_thread_edge
*> *path
)
2747 if (!dbg_cnt (registered_jump_thread
))
2753 /* First make sure there are no NULL outgoing edges on the jump threading
2754 path. That can happen for jumping to a constant address. */
2755 for (unsigned int i
= 0; i
< path
->length (); i
++)
2757 if ((*path
)[i
]->e
== NULL
)
2759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2762 "Found NULL edge in jump threading path. Cancelling jump thread:\n");
2763 dump_jump_thread_path (dump_file
, *path
, false);
2770 /* Only the FSM threader is allowed to thread across
2771 backedges in the CFG. */
2773 && (*path
)[0]->type
!= EDGE_FSM_THREAD
)
2774 gcc_assert (((*path
)[i
]->e
->flags
& EDGE_DFS_BACK
) == 0);
2777 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2778 dump_jump_thread_path (dump_file
, *path
, true);
2780 m_paths
.safe_push (path
);
2783 /* Return how many uses of T there are within BB, as long as there
2784 aren't any uses outside BB. If there are any uses outside BB,
2785 return -1 if there's at most one use within BB, or -2 if there is
2786 more than one use within BB. */
2789 uses_in_bb (tree t
, basic_block bb
)
2792 bool outside_bb
= false;
2794 imm_use_iterator iter
;
2795 use_operand_p use_p
;
2796 FOR_EACH_IMM_USE_FAST (use_p
, iter
, t
)
2798 if (is_gimple_debug (USE_STMT (use_p
)))
2801 if (gimple_bb (USE_STMT (use_p
)) != bb
)
2806 if (outside_bb
&& uses
> 1)
2816 /* Starting from the final control flow stmt in BB, assuming it will
2817 be removed, follow uses in to-be-removed stmts back to their defs
2818 and count how many defs are to become dead and be removed as
2822 estimate_threading_killed_stmts (basic_block bb
)
2824 int killed_stmts
= 0;
2825 hash_map
<tree
, int> ssa_remaining_uses
;
2826 auto_vec
<gimple
*, 4> dead_worklist
;
2828 /* If the block has only two predecessors, threading will turn phi
2829 dsts into either src, so count them as dead stmts. */
2830 bool drop_all_phis
= EDGE_COUNT (bb
->preds
) == 2;
2833 for (gphi_iterator gsi
= gsi_start_phis (bb
);
2834 !gsi_end_p (gsi
); gsi_next (&gsi
))
2836 gphi
*phi
= gsi
.phi ();
2837 tree dst
= gimple_phi_result (phi
);
2839 /* We don't count virtual PHIs as stmts in
2840 record_temporary_equivalences_from_phis. */
2841 if (virtual_operand_p (dst
))
2847 if (gsi_end_p (gsi_last_bb (bb
)))
2848 return killed_stmts
;
2850 gimple
*stmt
= gsi_stmt (gsi_last_bb (bb
));
2851 if (gimple_code (stmt
) != GIMPLE_COND
2852 && gimple_code (stmt
) != GIMPLE_GOTO
2853 && gimple_code (stmt
) != GIMPLE_SWITCH
)
2854 return killed_stmts
;
2856 /* The control statement is always dead. */
2858 dead_worklist
.quick_push (stmt
);
2859 while (!dead_worklist
.is_empty ())
2861 stmt
= dead_worklist
.pop ();
2864 use_operand_p use_p
;
2865 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_USE
)
2867 tree t
= USE_FROM_PTR (use_p
);
2868 gimple
*def
= SSA_NAME_DEF_STMT (t
);
2870 if (gimple_bb (def
) == bb
2871 && (gimple_code (def
) != GIMPLE_PHI
2873 && !gimple_has_side_effects (def
))
2875 int *usesp
= ssa_remaining_uses
.get (t
);
2881 uses
= uses_in_bb (t
, bb
);
2885 /* Don't bother recording the expected use count if we
2886 won't find any further uses within BB. */
2887 if (!usesp
&& (uses
< -1 || uses
> 1))
2889 usesp
= &ssa_remaining_uses
.get_or_insert (t
);
2904 ssa_remaining_uses
.remove (t
);
2905 if (gimple_code (def
) != GIMPLE_PHI
)
2906 dead_worklist
.safe_push (def
);
2913 fprintf (dump_file
, "threading bb %i kills %i stmts\n",
2914 bb
->index
, killed_stmts
);
2916 return killed_stmts
;