2 Copyright (C) 2005-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 "fold-const.h"
29 #include "gimple-iterator.h"
31 #include "tree-ssa-threadupdate.h"
32 #include "tree-ssa-loop.h"
34 #include "tree-pass.h"
35 #include "gimple-ssa.h"
36 #include "tree-phinodes.h"
37 #include "tree-inline.h"
38 #include "tree-vectorizer.h"
39 #include "value-range.h"
40 #include "gimple-range.h"
41 #include "tree-ssa-threadedge.h"
42 #include "gimple-range-path.h"
44 #include "tree-cfgcleanup.h"
46 // Path registry for the backwards threader. After all paths have been
47 // registered with register_path(), thread_through_all_blocks() is called
50 class back_threader_registry
53 back_threader_registry (int max_allowable_paths
);
54 bool register_path (const vec
<basic_block
> &, edge taken
);
55 bool thread_through_all_blocks ();
57 jump_thread_path_registry m_lowlevel_registry
;
58 const int m_max_allowable_paths
;
62 // Class to abstract the profitability code for the backwards threader.
64 class back_threader_profitability
67 back_threader_profitability (bool speed_p
)
70 bool profitable_path_p (const vec
<basic_block
> &, tree name
, edge taken
,
71 bool *irreducible_loop
= NULL
);
79 back_threader (bool speed_p
);
81 void maybe_thread_block (basic_block bb
);
82 bool thread_through_all_blocks ();
84 void find_paths (basic_block bb
, tree name
);
85 void maybe_register_path (edge taken_edge
);
86 bool find_paths_to_names (basic_block bb
, bitmap imports
);
87 bool resolve_def (tree name
, bitmap interesting
, vec
<tree
> &worklist
);
88 bool resolve_phi (gphi
*phi
, bitmap imports
);
89 edge
find_taken_edge (const vec
<basic_block
> &path
);
90 edge
find_taken_edge_cond (const vec
<basic_block
> &path
, gcond
*);
91 edge
find_taken_edge_switch (const vec
<basic_block
> &path
, gswitch
*);
93 back_threader_registry m_registry
;
94 back_threader_profitability m_profit
;
95 gimple_ranger m_ranger
;
96 path_range_query m_solver
;
98 // Current path being analyzed.
99 auto_vec
<basic_block
> m_path
;
100 // Hash to mark visited BBs while analyzing a path.
101 hash_set
<basic_block
> m_visited_bbs
;
102 // The set of SSA names, any of which could potentially change the
103 // value of the final conditional in a path.
105 // The last statement in the path.
107 // This is a bit of a wart. It's used to pass the LHS SSA name to
108 // the profitability engine.
110 // Marker to differentiate unreachable edges.
111 static const edge UNREACHABLE_EDGE
;
114 // Used to differentiate unreachable edges, so we may stop the search
115 // in a the given direction.
116 const edge
back_threader::UNREACHABLE_EDGE
= (edge
) -1;
118 back_threader::back_threader (bool speed_p
)
119 : m_registry (param_max_fsm_thread_paths
),
124 m_imports
= BITMAP_ALLOC (NULL
);
127 back_threader::~back_threader ()
130 BITMAP_FREE (m_imports
);
133 // Register the current path for jump threading if it's profitable to
134 // do so. TAKEN_EDGE is the known edge out of the path.
137 back_threader::maybe_register_path (edge taken_edge
)
139 bool irreducible
= false;
141 = m_profit
.profitable_path_p (m_path
, m_name
, taken_edge
, &irreducible
);
145 m_registry
.register_path (m_path
, taken_edge
);
148 vect_free_loop_info_assumptions (m_path
[0]->loop_father
);
152 // Return the known taken edge out of a path. If the path can be
153 // determined to be unreachable, return UNREACHABLE_EDGE. If no
154 // outgoing edge can be calculated, return NULL.
157 back_threader::find_taken_edge (const vec
<basic_block
> &path
)
159 gcc_checking_assert (path
.length () > 1);
160 switch (gimple_code (m_last_stmt
))
163 return find_taken_edge_cond (path
, as_a
<gcond
*> (m_last_stmt
));
166 return find_taken_edge_switch (path
, as_a
<gswitch
*> (m_last_stmt
));
173 // Same as find_taken_edge, but for paths ending in a switch.
176 back_threader::find_taken_edge_switch (const vec
<basic_block
> &path
,
179 tree name
= gimple_switch_index (sw
);
182 m_solver
.precompute_ranges (path
, m_imports
);
183 m_solver
.range_of_expr (r
, name
, sw
);
185 if (r
.undefined_p ())
186 return UNREACHABLE_EDGE
;
192 if (r
.singleton_p (&val
))
193 return ::find_taken_edge (gimple_bb (sw
), val
);
198 // Same as find_taken_edge, but for paths ending in a GIMPLE_COND.
201 back_threader::find_taken_edge_cond (const vec
<basic_block
> &path
,
204 m_solver
.precompute_ranges (path
, m_imports
);
206 // Check if either operand is unreachable since this knowledge could
207 // help the caller cut down the search space.
209 m_solver
.range_of_expr (r
, gimple_cond_lhs (cond
));
210 if (r
.undefined_p ())
211 return UNREACHABLE_EDGE
;
212 m_solver
.range_of_expr (r
, gimple_cond_rhs (cond
));
213 if (r
.undefined_p ())
214 return UNREACHABLE_EDGE
;
216 m_solver
.range_of_stmt (r
, cond
);
218 int_range
<2> true_range (boolean_true_node
, boolean_true_node
);
219 int_range
<2> false_range (boolean_false_node
, boolean_false_node
);
221 if (r
== true_range
|| r
== false_range
)
223 edge e_true
, e_false
;
224 basic_block bb
= gimple_bb (cond
);
225 extract_true_false_edges_from_block (bb
, &e_true
, &e_false
);
226 return r
== true_range
? e_true
: e_false
;
231 // Populate a vector of trees from a bitmap.
234 populate_worklist (vec
<tree
> &worklist
, bitmap bits
)
239 EXECUTE_IF_SET_IN_BITMAP (bits
, 0, i
, bi
)
241 tree name
= ssa_name (i
);
242 worklist
.quick_push (name
);
246 // If taking any of the incoming edges to a PHI causes the final
247 // conditional of the current path to be constant, register the
248 // path(s), and return TRUE.
251 back_threader::resolve_phi (gphi
*phi
, bitmap interesting
)
253 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi
)))
257 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
259 edge e
= gimple_phi_arg_edge (phi
, i
);
261 // This is like path_crosses_loops in profitable_path_p but more
262 // restrictive, since profitable_path_p allows threading the
263 // first block because it would be redirected anyhow.
265 // If we loosened the restriction and used profitable_path_p()
266 // here instead, we would peel off the first iterations of loops
267 // in places like tree-ssa/pr14341.c.
268 bool profitable_p
= m_path
[0]->loop_father
== e
->src
->loop_father
;
271 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 " FAIL: path through PHI in bb%d (incoming bb:%d) crosses loop\n",
274 e
->dest
->index
, e
->src
->index
);
278 tree arg
= gimple_phi_arg_def (phi
, i
);
279 if (TREE_CODE (arg
) == SSA_NAME
)
281 unsigned v
= SSA_NAME_VERSION (arg
);
283 // Avoid loops as in: x_5 = PHI <x_5(2), ...>.
284 if (bitmap_bit_p (interesting
, v
))
287 bitmap_set_bit (interesting
, v
);
288 bitmap_set_bit (m_imports
, v
);
289 done
|= find_paths_to_names (e
->src
, interesting
);
290 bitmap_clear_bit (interesting
, v
);
292 else if (TREE_CODE (arg
) == INTEGER_CST
)
294 m_path
.safe_push (e
->src
);
295 edge taken_edge
= find_taken_edge (m_path
);
296 if (taken_edge
&& taken_edge
!= UNREACHABLE_EDGE
)
298 maybe_register_path (taken_edge
);
307 // If the definition of NAME causes the final conditional of the
308 // current path to be constant, register the path, and return TRUE.
311 back_threader::resolve_def (tree name
, bitmap interesting
, vec
<tree
> &worklist
)
313 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
316 if (is_a
<gphi
*> (def_stmt
)
317 && resolve_phi (as_a
<gphi
*> (def_stmt
), interesting
))
320 // Defer copies of SSAs by adding the source to the worklist.
321 if (gimple_assign_single_p (def_stmt
)
322 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
324 tree rhs
= gimple_assign_rhs1 (def_stmt
);
325 bitmap_set_bit (m_imports
, SSA_NAME_VERSION (rhs
));
326 bitmap_set_bit (interesting
, SSA_NAME_VERSION (rhs
));
327 worklist
.safe_push (rhs
);
332 // Find jump threading paths to any of the SSA names in the
333 // INTERESTING bitmap, and register any such paths.
335 // Return TRUE if no further processing past this block is necessary.
336 // This is because we've either registered a path, or because there is
337 // nothing of interesting beyond this block.
339 // BB is the current path being processed.
342 back_threader::find_paths_to_names (basic_block bb
, bitmap interesting
)
344 if (m_visited_bbs
.add (bb
))
347 m_path
.safe_push (bb
);
349 if (m_path
.length () > 1
350 && !m_profit
.profitable_path_p (m_path
, m_name
, NULL
))
353 m_visited_bbs
.remove (bb
);
357 auto_bitmap processed
;
361 // We use a worklist instead of iterating through the bitmap,
362 // because we may add new items in-flight.
363 auto_vec
<tree
> worklist (bitmap_count_bits (interesting
));
364 populate_worklist (worklist
, interesting
);
365 while (!worklist
.is_empty ())
367 tree name
= worklist
.pop ();
368 unsigned i
= SSA_NAME_VERSION (name
);
369 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
371 // Process any names defined in this block.
374 bitmap_set_bit (processed
, i
);
376 if (resolve_def (name
, interesting
, worklist
))
382 // Examine blocks that define or export an interesting SSA,
383 // since they may compute a range which resolve this path.
385 || bitmap_bit_p (m_ranger
.gori ().exports (bb
), i
))
386 && m_path
.length () > 1)
388 edge taken_edge
= find_taken_edge (m_path
);
391 if (taken_edge
!= UNREACHABLE_EDGE
)
392 maybe_register_path (taken_edge
);
400 // If there are interesting names not yet processed, keep looking.
401 bitmap_and_compl_into (interesting
, processed
);
402 if (!bitmap_empty_p (interesting
))
406 FOR_EACH_EDGE (e
, iter
, bb
->preds
)
407 if ((e
->flags
& EDGE_ABNORMAL
) == 0)
408 done
|= find_paths_to_names (e
->src
, interesting
);
413 EXECUTE_IF_SET_IN_BITMAP (processed
, 0, i
, bi
)
414 bitmap_set_bit (interesting
, i
);
417 m_visited_bbs
.remove (bb
);
421 // Search backwards from BB looking for paths where the final
422 // conditional out of BB can be determined. NAME is the LHS of the
423 // final conditional. Register such paths for jump threading.
426 back_threader::find_paths (basic_block bb
, tree name
)
428 gimple
*stmt
= last_stmt (bb
);
430 || (gimple_code (stmt
) != GIMPLE_COND
431 && gimple_code (stmt
) != GIMPLE_SWITCH
))
434 if (EDGE_COUNT (bb
->succs
) > 1
435 || single_succ_to_potentially_threadable_block (bb
))
438 m_visited_bbs
.empty ();
441 bitmap_clear (m_imports
);
443 auto_bitmap interesting
;
444 bitmap_copy (m_imports
, m_ranger
.gori ().imports (bb
));
445 bitmap_copy (interesting
, m_imports
);
446 find_paths_to_names (bb
, interesting
);
450 // Simple helper to get the last statement from BB, which is assumed
451 // to be a control statement. Return NULL if the last statement is
452 // not a control statement.
455 get_gimple_control_stmt (basic_block bb
)
457 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
462 gimple
*stmt
= gsi_stmt (gsi
);
463 enum gimple_code code
= gimple_code (stmt
);
464 if (code
== GIMPLE_COND
|| code
== GIMPLE_SWITCH
|| code
== GIMPLE_GOTO
)
469 // Search backwards from BB looking for paths where the final
470 // conditional maybe threaded to a successor block. Record such paths
471 // for jump threading.
474 back_threader::maybe_thread_block (basic_block bb
)
476 gimple
*stmt
= get_gimple_control_stmt (bb
);
480 enum gimple_code code
= gimple_code (stmt
);
482 if (code
== GIMPLE_SWITCH
)
483 name
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
484 else if (code
== GIMPLE_COND
)
485 name
= gimple_cond_lhs (stmt
);
486 else if (code
== GIMPLE_GOTO
)
487 name
= gimple_goto_dest (stmt
);
491 find_paths (bb
, name
);
494 // Perform the actual jump threading for the all queued paths.
497 back_threader::thread_through_all_blocks ()
499 return m_registry
.thread_through_all_blocks ();
502 // Dump a sequence of BBs through the CFG.
505 dump_path (FILE *dump_file
, const vec
<basic_block
> &path
)
507 for (size_t i
= 0; i
< path
.length (); ++i
)
509 fprintf (dump_file
, "BB%d", path
[i
]->index
);
510 if (i
+ 1 < path
.length ())
511 fprintf (dump_file
, " <- ");
513 fprintf (dump_file
, "\n");
517 debug (const vec
<basic_block
> &path
)
519 dump_path (stderr
, path
);
522 back_threader_registry::back_threader_registry (int max_allowable_paths
)
523 : m_max_allowable_paths (max_allowable_paths
)
525 m_threaded_paths
= 0;
529 back_threader_registry::thread_through_all_blocks ()
531 return m_lowlevel_registry
.thread_through_all_blocks (true);
534 /* Examine jump threading path PATH and return TRUE if it is profitable to
535 thread it, otherwise return FALSE.
537 NAME is the SSA_NAME of the variable we found to have a constant
538 value on PATH. If unknown, SSA_NAME is NULL.
540 If the taken edge out of the path is known ahead of time it is passed in
541 TAKEN_EDGE, otherwise it is NULL.
543 CREATES_IRREDUCIBLE_LOOP, if non-null is set to TRUE if threading this path
544 would create an irreducible loop. */
547 back_threader_profitability::profitable_path_p (const vec
<basic_block
> &m_path
,
550 bool *creates_irreducible_loop
)
552 gcc_checking_assert (!m_path
.is_empty ());
554 /* We can an empty path here (excluding the DEF block) when the
555 statement that makes a conditional generate a compile-time
556 constant result is in the same block as the conditional.
558 That's not really a jump threading opportunity, but instead is
559 simple cprop & simplification. We could handle it here if we
560 wanted by wiring up all the incoming edges. If we run this
561 early in IPA, that might be worth doing. For now we just
563 if (m_path
.length () <= 1)
566 if (m_path
.length () > (unsigned) param_max_fsm_thread_length
)
568 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
569 fprintf (dump_file
, " FAIL: FSM jump-thread path not considered: "
570 "the number of basic blocks on the path "
571 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
576 gimple_stmt_iterator gsi
;
577 loop_p loop
= m_path
[0]->loop_father
;
578 bool path_crosses_loops
= false;
579 bool threaded_through_latch
= false;
580 bool multiway_branch_in_path
= false;
581 bool threaded_multiway_branch
= false;
582 bool contains_hot_bb
= false;
584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
585 fprintf (dump_file
, "Checking profitability of path (backwards): ");
587 /* Count the number of instructions on the path: as these instructions
588 will have to be duplicated, we will not record the path if there
589 are too many instructions on the path. Also check that all the
590 blocks in the path belong to a single loop. */
591 for (unsigned j
= 0; j
< m_path
.length (); j
++)
593 basic_block bb
= m_path
[j
];
595 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
596 fprintf (dump_file
, " bb:%i", bb
->index
);
597 /* Remember, blocks in the path are stored in opposite order
598 in the PATH array. The last entry in the array represents
599 the block with an outgoing edge that we will redirect to the
600 jump threading path. Thus we don't care about that block's
601 loop father, nor how many statements are in that block because
602 it will not be copied or whether or not it ends in a multiway
604 if (j
< m_path
.length () - 1)
606 int orig_n_insns
= n_insns
;
607 if (bb
->loop_father
!= loop
)
609 path_crosses_loops
= true;
613 /* PHIs in the path will create degenerate PHIS in the
614 copied path which will then get propagated away, so
615 looking at just the duplicate path the PHIs would
618 But those PHIs, because they're assignments to objects
619 typically with lives that exist outside the thread path,
620 will tend to generate PHIs (or at least new PHI arguments)
621 at points where we leave the thread path and rejoin
622 the original blocks. So we do want to account for them.
624 We ignore virtual PHIs. We also ignore cases where BB
625 has a single incoming edge. That's the most common
626 degenerate PHI we'll see here. Finally we ignore PHIs
627 that are associated with the value we're tracking as
628 that object likely dies. */
629 if (EDGE_COUNT (bb
->succs
) > 1 && EDGE_COUNT (bb
->preds
) > 1)
631 for (gphi_iterator gsip
= gsi_start_phis (bb
);
635 gphi
*phi
= gsip
.phi ();
636 tree dst
= gimple_phi_result (phi
);
638 /* Note that if both NAME and DST are anonymous
639 SSA_NAMEs, then we do not have enough information
640 to consider them associated. */
643 && TREE_CODE (name
) == SSA_NAME
644 && (SSA_NAME_VAR (dst
) != SSA_NAME_VAR (name
)
645 || !SSA_NAME_VAR (dst
))
646 && !virtual_operand_p (dst
))
651 if (!contains_hot_bb
&& m_speed_p
)
652 contains_hot_bb
|= optimize_bb_for_speed_p (bb
);
653 for (gsi
= gsi_after_labels (bb
);
655 gsi_next_nondebug (&gsi
))
657 /* Do not allow OpenACC loop markers and __builtin_constant_p on
658 threading paths. The latter is disallowed, because an
659 expression might be constant on two threading paths, and
660 become non-constant (i.e.: phi) when they merge. */
661 gimple
*stmt
= gsi_stmt (gsi
);
662 if (gimple_call_internal_p (stmt
, IFN_UNIQUE
)
663 || gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
))
665 /* Do not count empty statements and labels. */
666 if (gimple_code (stmt
) != GIMPLE_NOP
667 && !(gimple_code (stmt
) == GIMPLE_ASSIGN
668 && gimple_assign_rhs_code (stmt
) == ASSERT_EXPR
)
669 && !is_gimple_debug (stmt
))
670 n_insns
+= estimate_num_insns (stmt
, &eni_size_weights
);
672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
673 fprintf (dump_file
, " (%i insns)", n_insns
-orig_n_insns
);
675 /* We do not look at the block with the threaded branch
676 in this loop. So if any block with a last statement that
677 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
678 multiway branch on our path.
680 The block in PATH[0] is special, it's the block were we're
681 going to be able to eliminate its branch. */
682 gimple
*last
= last_stmt (bb
);
683 if (last
&& (gimple_code (last
) == GIMPLE_SWITCH
684 || gimple_code (last
) == GIMPLE_GOTO
))
687 threaded_multiway_branch
= true;
689 multiway_branch_in_path
= true;
693 /* Note if we thread through the latch, we will want to include
694 the last entry in the array when determining if we thread
695 through the loop latch. */
696 if (loop
->latch
== bb
)
697 threaded_through_latch
= true;
700 gimple
*stmt
= get_gimple_control_stmt (m_path
[0]);
703 /* We are going to remove the control statement at the end of the
704 last block in the threading path. So don't count it against our
707 int stmt_insns
= estimate_num_insns (stmt
, &eni_size_weights
);
708 n_insns
-= stmt_insns
;
710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
711 fprintf (dump_file
, "\n Control statement insns: %i\n"
712 " Overall: %i insns\n",
713 stmt_insns
, n_insns
);
715 if (creates_irreducible_loop
)
717 /* If this path threaded through the loop latch back into the
718 same loop and the destination does not dominate the loop
719 latch, then this thread would create an irreducible loop. */
720 *creates_irreducible_loop
= false;
722 && threaded_through_latch
723 && loop
== taken_edge
->dest
->loop_father
724 && (determine_bb_domination_status (loop
, taken_edge
->dest
)
725 == DOMST_NONDOMINATING
))
726 *creates_irreducible_loop
= true;
729 if (path_crosses_loops
)
731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
732 fprintf (dump_file
, " FAIL: FSM jump-thread path not considered: "
733 "the path crosses loops.\n");
737 /* Threading is profitable if the path duplicated is hot but also
738 in a case we separate cold path from hot path and permit optimization
739 of the hot path later. Be on the agressive side here. In some testcases,
740 as in PR 78407 this leads to noticeable improvements. */
742 && ((taken_edge
&& optimize_edge_for_speed_p (taken_edge
))
745 if (n_insns
>= param_max_fsm_thread_path_insns
)
747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
748 fprintf (dump_file
, " FAIL: FSM jump-thread path not considered: "
749 "the number of instructions on the path "
750 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
754 else if (!m_speed_p
&& n_insns
> 1)
756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
757 fprintf (dump_file
, " FAIL: FSM jump-thread path not considered: "
758 "duplication of %i insns is needed and optimizing for size.\n",
763 /* We avoid creating irreducible inner loops unless we thread through
764 a multiway branch, in which case we have deemed it worth losing
765 other loop optimizations later.
767 We also consider it worth creating an irreducible inner loop if
768 the number of copied statement is low relative to the length of
769 the path -- in that case there's little the traditional loop
770 optimizer would have done anyway, so an irreducible loop is not
772 if (!threaded_multiway_branch
773 && creates_irreducible_loop
774 && *creates_irreducible_loop
775 && (n_insns
* (unsigned) param_fsm_scale_path_stmts
776 > (m_path
.length () *
777 (unsigned) param_fsm_scale_path_blocks
)))
780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
782 " FAIL: FSM would create irreducible loop without threading "
783 "multiway branch.\n");
787 /* If this path does not thread through the loop latch, then we are
788 using the FSM threader to find old style jump threads. This
789 is good, except the FSM threader does not re-use an existing
790 threading path to reduce code duplication.
792 So for that case, drastically reduce the number of statements
793 we are allowed to copy. */
794 if (!(threaded_through_latch
&& threaded_multiway_branch
)
795 && (n_insns
* param_fsm_scale_path_stmts
796 >= param_max_jump_thread_duplication_stmts
))
798 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
800 " FAIL: FSM did not thread around loop and would copy too "
801 "many statements.\n");
805 /* When there is a multi-way branch on the path, then threading can
806 explode the CFG due to duplicating the edges for that multi-way
807 branch. So like above, only allow a multi-way branch on the path
808 if we actually thread a multi-way branch. */
809 if (!threaded_multiway_branch
&& multiway_branch_in_path
)
811 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
813 " FAIL: FSM Thread through multiway branch without threading "
814 "a multiway branch.\n");
820 /* The current path PATH is a vector of blocks forming a jump threading
821 path in reverse order. TAKEN_EDGE is the edge taken from path[0].
823 Convert the current path into the form used by register_jump_thread and
826 Return TRUE if successful or FALSE otherwise. */
829 back_threader_registry::register_path (const vec
<basic_block
> &m_path
,
832 if (m_threaded_paths
> m_max_allowable_paths
)
834 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
835 fprintf (dump_file
, " FAIL: FSM jump-thread path not considered: "
836 "the number of previously recorded FSM paths to "
837 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
841 vec
<jump_thread_edge
*> *jump_thread_path
842 = m_lowlevel_registry
.allocate_thread_path ();
844 /* Record the edges between the blocks in PATH. */
845 for (unsigned int j
= 0; j
+ 1 < m_path
.length (); j
++)
847 basic_block bb1
= m_path
[m_path
.length () - j
- 1];
848 basic_block bb2
= m_path
[m_path
.length () - j
- 2];
850 edge e
= find_edge (bb1
, bb2
);
853 = m_lowlevel_registry
.allocate_thread_edge (e
, EDGE_FSM_THREAD
);
854 jump_thread_path
->safe_push (x
);
857 /* Add the edge taken when the control variable has value ARG. */
859 = m_lowlevel_registry
.allocate_thread_edge (taken_edge
,
860 EDGE_NO_COPY_SRC_BLOCK
);
861 jump_thread_path
->safe_push (x
);
863 if (m_lowlevel_registry
.register_jump_thread (jump_thread_path
))
870 const pass_data pass_data_thread_jumps
=
875 TV_TREE_SSA_THREAD_JUMPS
,
876 ( PROP_cfg
| PROP_ssa
),
883 class pass_thread_jumps
: public gimple_opt_pass
886 pass_thread_jumps (gcc::context
*ctxt
)
887 : gimple_opt_pass (pass_data_thread_jumps
, ctxt
)
890 opt_pass
* clone (void) { return new pass_thread_jumps (m_ctxt
); }
891 virtual bool gate (function
*);
892 virtual unsigned int execute (function
*);
896 pass_thread_jumps::gate (function
*fun ATTRIBUTE_UNUSED
)
898 return flag_expensive_optimizations
;
901 // Try to thread blocks in FUN. Return TRUE if any jump thread paths were
905 try_thread_blocks (function
*fun
)
907 /* Try to thread each block with more than one successor. */
908 back_threader
threader (/*speed_p=*/true);
910 FOR_EACH_BB_FN (bb
, fun
)
912 if (EDGE_COUNT (bb
->succs
) > 1)
913 threader
.maybe_thread_block (bb
);
915 return threader
.thread_through_all_blocks ();
919 pass_thread_jumps::execute (function
*fun
)
921 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
923 bool changed
= try_thread_blocks (fun
);
925 loop_optimizer_finalize ();
927 return changed
? TODO_cleanup_cfg
: 0;
933 make_pass_thread_jumps (gcc::context
*ctxt
)
935 return new pass_thread_jumps (ctxt
);
940 const pass_data pass_data_early_thread_jumps
=
945 TV_TREE_SSA_THREAD_JUMPS
,
946 ( PROP_cfg
| PROP_ssa
),
950 ( TODO_cleanup_cfg
| TODO_update_ssa
),
953 class pass_early_thread_jumps
: public gimple_opt_pass
956 pass_early_thread_jumps (gcc::context
*ctxt
)
957 : gimple_opt_pass (pass_data_early_thread_jumps
, ctxt
)
960 opt_pass
* clone (void) { return new pass_early_thread_jumps (m_ctxt
); }
961 virtual bool gate (function
*);
962 virtual unsigned int execute (function
*);
966 pass_early_thread_jumps::gate (function
*fun ATTRIBUTE_UNUSED
)
972 pass_early_thread_jumps::execute (function
*fun
)
974 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
976 /* Try to thread each block with more than one successor. */
977 back_threader
threader (/*speed_p=*/false);
979 FOR_EACH_BB_FN (bb
, fun
)
981 if (EDGE_COUNT (bb
->succs
) > 1)
982 threader
.maybe_thread_block (bb
);
984 threader
.thread_through_all_blocks ();
986 loop_optimizer_finalize ();
993 make_pass_early_thread_jumps (gcc::context
*ctxt
)
995 return new pass_early_thread_jumps (ctxt
);