2 Copyright (C) 2005-2022 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"
45 #include "tree-pretty-print.h"
49 // Path registry for the backwards threader. After all paths have been
50 // registered with register_path(), thread_through_all_blocks() is called
53 class back_threader_registry
: public back_jt_path_registry
56 bool register_path (const vec
<basic_block
> &, edge taken
);
59 // Class to abstract the profitability code for the backwards threader.
61 class back_threader_profitability
64 back_threader_profitability (bool speed_p
)
67 bool profitable_path_p (const vec
<basic_block
> &, tree name
, edge taken
,
68 bool *irreducible_loop
= NULL
);
73 // Back threader flags.
75 // Generate fast code at the expense of code size.
77 // Resolve unknown SSAs on entry to a threading path. If set, use the
78 // ranger. If not, assume all ranges on entry to a path are VARYING.
84 back_threader (function
*fun
, unsigned flags
, bool first
);
86 unsigned thread_blocks ();
88 void maybe_thread_block (basic_block bb
);
89 void find_paths (basic_block bb
, tree name
);
90 bool debug_counter ();
91 edge
maybe_register_path ();
92 void maybe_register_path_dump (edge taken_edge
);
93 void find_paths_to_names (basic_block bb
, bitmap imports
);
94 void resolve_phi (gphi
*phi
, bitmap imports
);
95 edge
find_taken_edge (const vec
<basic_block
> &path
);
96 edge
find_taken_edge_cond (const vec
<basic_block
> &path
, gcond
*);
97 edge
find_taken_edge_switch (const vec
<basic_block
> &path
, gswitch
*);
98 virtual void debug ();
99 virtual void dump (FILE *out
);
101 back_threader_registry m_registry
;
102 back_threader_profitability m_profit
;
103 path_range_query
*m_solver
;
105 // Current path being analyzed.
106 auto_vec
<basic_block
> m_path
;
107 // Hash to mark visited BBs while analyzing a path.
108 hash_set
<basic_block
> m_visited_bbs
;
109 // The set of SSA names, any of which could potentially change the
110 // value of the final conditional in a path.
111 auto_bitmap m_imports
;
112 // The last statement in the path.
114 // This is a bit of a wart. It's used to pass the LHS SSA name to
115 // the profitability engine.
117 // Marker to differentiate unreachable edges.
118 static const edge UNREACHABLE_EDGE
;
119 // Set to TRUE if unknown SSA names along a path should be resolved
120 // with the ranger. Otherwise, unknown SSA names are assumed to be
121 // VARYING. Setting to true is more precise but slower.
124 // Set to TRUE for the first of each thread[12] pass or the first of
125 // each threadfull[12] pass. This is used to differentiate between
126 // the different threading passes so we can set up debug counters.
130 // Used to differentiate unreachable edges, so we may stop the search
131 // in a the given direction.
132 const edge
back_threader::UNREACHABLE_EDGE
= (edge
) -1;
134 back_threader::back_threader (function
*fun
, unsigned flags
, bool first
)
135 : m_profit (flags
& BT_SPEED
),
138 if (flags
& BT_SPEED
)
139 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
141 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
145 m_solver
= new path_range_query (flags
& BT_RESOLVE
);
149 back_threader::~back_threader ()
153 loop_optimizer_finalize ();
156 // A wrapper for the various debug counters for the threading passes.
157 // Returns TRUE if it's OK to register the current threading
161 back_threader::debug_counter ()
163 // The ethread pass is mostly harmless ;-).
164 if ((m_flags
& BT_SPEED
) == 0)
167 if (m_flags
& BT_RESOLVE
)
169 if (m_first
&& !dbg_cnt (back_threadfull1
))
172 if (!m_first
&& !dbg_cnt (back_threadfull2
))
177 if (m_first
&& !dbg_cnt (back_thread1
))
180 if (!m_first
&& !dbg_cnt (back_thread2
))
187 dump_path (FILE *dump_file
, const vec
<basic_block
> &path
)
189 for (unsigned i
= path
.length (); i
> 0; --i
)
191 basic_block bb
= path
[i
- 1];
192 fprintf (dump_file
, "%d", bb
->index
);
194 fprintf (dump_file
, "->");
198 // Dump details of an attempt to register a path.
201 back_threader::maybe_register_path_dump (edge taken
)
203 if (m_path
.is_empty ())
206 fprintf (dump_file
, "path: ");
207 dump_path (dump_file
, m_path
);
208 fprintf (dump_file
, "->");
210 if (taken
== UNREACHABLE_EDGE
)
211 fprintf (dump_file
, "xx REJECTED (unreachable)\n");
213 fprintf (dump_file
, "%d SUCCESS\n", taken
->dest
->index
);
215 fprintf (dump_file
, "xx REJECTED\n");
218 // If an outgoing edge can be determined out of the current path,
219 // register it for jump threading and return the taken edge.
221 // Return NULL if it is unprofitable to thread this path, or the
222 // outgoing edge is unknown. Return UNREACHABLE_EDGE if the path is
226 back_threader::maybe_register_path ()
228 edge taken_edge
= find_taken_edge (m_path
);
230 if (taken_edge
&& taken_edge
!= UNREACHABLE_EDGE
)
232 if (m_visited_bbs
.contains (taken_edge
->dest
))
234 // Avoid circular paths by indicating there is nothing to
235 // see in this direction.
236 taken_edge
= UNREACHABLE_EDGE
;
240 bool irreducible
= false;
241 if (m_profit
.profitable_path_p (m_path
, m_name
, taken_edge
,
245 m_registry
.register_path (m_path
, taken_edge
);
248 vect_free_loop_info_assumptions (m_path
[0]->loop_father
);
255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
256 maybe_register_path_dump (taken_edge
);
261 // Return the known taken edge out of a path. If the path can be
262 // determined to be unreachable, return UNREACHABLE_EDGE. If no
263 // outgoing edge can be calculated, return NULL.
266 back_threader::find_taken_edge (const vec
<basic_block
> &path
)
268 gcc_checking_assert (path
.length () > 1);
269 switch (gimple_code (m_last_stmt
))
272 return find_taken_edge_cond (path
, as_a
<gcond
*> (m_last_stmt
));
275 return find_taken_edge_switch (path
, as_a
<gswitch
*> (m_last_stmt
));
282 // Same as find_taken_edge, but for paths ending in a switch.
285 back_threader::find_taken_edge_switch (const vec
<basic_block
> &path
,
288 tree name
= gimple_switch_index (sw
);
291 m_solver
->compute_ranges (path
, m_imports
);
292 m_solver
->range_of_expr (r
, name
, sw
);
294 if (r
.undefined_p ())
295 return UNREACHABLE_EDGE
;
300 tree label
= find_case_label_range (sw
, &r
);
304 return find_edge (gimple_bb (sw
), label_to_block (cfun
, CASE_LABEL (label
)));
307 // Same as find_taken_edge, but for paths ending in a GIMPLE_COND.
310 back_threader::find_taken_edge_cond (const vec
<basic_block
> &path
,
315 m_solver
->compute_ranges (path
, m_imports
);
316 m_solver
->range_of_stmt (r
, cond
);
318 if (m_solver
->unreachable_path_p ())
319 return UNREACHABLE_EDGE
;
321 int_range
<2> true_range (boolean_true_node
, boolean_true_node
);
322 int_range
<2> false_range (boolean_false_node
, boolean_false_node
);
324 if (r
== true_range
|| r
== false_range
)
326 edge e_true
, e_false
;
327 basic_block bb
= gimple_bb (cond
);
328 extract_true_false_edges_from_block (bb
, &e_true
, &e_false
);
329 return r
== true_range
? e_true
: e_false
;
334 // Populate a vector of trees from a bitmap.
337 populate_worklist (vec
<tree
> &worklist
, bitmap bits
)
342 EXECUTE_IF_SET_IN_BITMAP (bits
, 0, i
, bi
)
344 tree name
= ssa_name (i
);
345 worklist
.quick_push (name
);
349 // Find jump threading paths that go through a PHI.
352 back_threader::resolve_phi (gphi
*phi
, bitmap interesting
)
354 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi
)))
357 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
359 edge e
= gimple_phi_arg_edge (phi
, i
);
361 // This is like path_crosses_loops in profitable_path_p but more
362 // restrictive to avoid peeling off loop iterations (see
363 // tree-ssa/pr14341.c for an example).
364 bool profitable_p
= m_path
[0]->loop_father
== e
->src
->loop_father
;
367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
370 " FAIL: path through PHI in bb%d (incoming bb:%d) crosses loop\n",
371 e
->dest
->index
, e
->src
->index
);
372 fprintf (dump_file
, "path: %d->", e
->src
->index
);
373 dump_path (dump_file
, m_path
);
374 fprintf (dump_file
, "->xx REJECTED\n");
379 tree arg
= gimple_phi_arg_def (phi
, i
);
382 if (TREE_CODE (arg
) == SSA_NAME
383 && !bitmap_bit_p (interesting
, SSA_NAME_VERSION (arg
)))
385 // Record that ARG is interesting when searching down this path.
386 v
= SSA_NAME_VERSION (arg
);
387 gcc_checking_assert (v
!= 0);
388 bitmap_set_bit (interesting
, v
);
389 bitmap_set_bit (m_imports
, v
);
392 find_paths_to_names (e
->src
, interesting
);
395 bitmap_clear_bit (interesting
, v
);
399 // Find jump threading paths to any of the SSA names in the
400 // INTERESTING bitmap, and register any such paths.
402 // BB is the current path being processed.
405 back_threader::find_paths_to_names (basic_block bb
, bitmap interesting
)
407 if (m_visited_bbs
.add (bb
))
410 m_path
.safe_push (bb
);
412 // Try to resolve the path without looking back.
413 if (m_path
.length () > 1
414 && (!m_profit
.profitable_path_p (m_path
, m_name
, NULL
)
415 || maybe_register_path ()))
418 m_visited_bbs
.remove (bb
);
422 auto_bitmap processed
;
424 // We use a worklist instead of iterating through the bitmap,
425 // because we may add new items in-flight.
426 auto_vec
<tree
> worklist (bitmap_count_bits (interesting
));
427 populate_worklist (worklist
, interesting
);
428 while (!worklist
.is_empty ())
430 tree name
= worklist
.pop ();
431 unsigned i
= SSA_NAME_VERSION (name
);
432 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
433 basic_block def_bb
= gimple_bb (def_stmt
);
435 // Process any PHIs defined in this block.
437 && bitmap_set_bit (processed
, i
)
438 && gimple_code (def_stmt
) == GIMPLE_PHI
)
440 resolve_phi (as_a
<gphi
*> (def_stmt
), interesting
);
445 // If there are interesting names not yet processed, keep looking.
448 bitmap_and_compl_into (interesting
, processed
);
449 if (!bitmap_empty_p (interesting
))
453 FOR_EACH_EDGE (e
, iter
, bb
->preds
)
454 if ((e
->flags
& EDGE_ABNORMAL
) == 0)
455 find_paths_to_names (e
->src
, interesting
);
459 // Reset things to their original state.
460 bitmap_ior_into (interesting
, processed
);
462 m_visited_bbs
.remove (bb
);
465 // Search backwards from BB looking for paths where the final
466 // conditional out of BB can be determined. NAME is the LHS of the
467 // final conditional. Register such paths for jump threading.
470 back_threader::find_paths (basic_block bb
, tree name
)
472 gimple
*stmt
= last_stmt (bb
);
474 || (gimple_code (stmt
) != GIMPLE_COND
475 && gimple_code (stmt
) != GIMPLE_SWITCH
))
478 if (EDGE_COUNT (bb
->succs
) > 1
479 || single_succ_to_potentially_threadable_block (bb
))
482 m_visited_bbs
.empty ();
485 m_solver
->compute_imports (m_imports
, bb
);
487 auto_bitmap interesting
;
488 bitmap_copy (interesting
, m_imports
);
489 find_paths_to_names (bb
, interesting
);
493 // Simple helper to get the last statement from BB, which is assumed
494 // to be a control statement. Return NULL if the last statement is
495 // not a control statement.
498 get_gimple_control_stmt (basic_block bb
)
500 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
505 gimple
*stmt
= gsi_stmt (gsi
);
506 enum gimple_code code
= gimple_code (stmt
);
507 if (code
== GIMPLE_COND
|| code
== GIMPLE_SWITCH
|| code
== GIMPLE_GOTO
)
512 // Search backwards from BB looking for paths where the final
513 // conditional maybe threaded to a successor block. Record such paths
514 // for jump threading.
517 back_threader::maybe_thread_block (basic_block bb
)
519 gimple
*stmt
= get_gimple_control_stmt (bb
);
523 enum gimple_code code
= gimple_code (stmt
);
525 if (code
== GIMPLE_SWITCH
)
526 name
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
527 else if (code
== GIMPLE_COND
)
528 name
= gimple_cond_lhs (stmt
);
529 else if (code
== GIMPLE_GOTO
)
530 name
= gimple_goto_dest (stmt
);
534 find_paths (bb
, name
);
538 debug (const vec
<basic_block
> &path
)
540 dump_path (stderr
, path
);
541 fputc ('\n', stderr
);
545 back_threader::dump (FILE *out
)
547 m_solver
->dump (out
);
548 fprintf (out
, "\nCandidates for pre-computation:\n");
549 fprintf (out
, "===================================\n");
554 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
556 tree name
= ssa_name (i
);
557 print_generic_expr (out
, name
, TDF_NONE
);
563 back_threader::debug ()
568 /* Examine jump threading path PATH and return TRUE if it is profitable to
569 thread it, otherwise return FALSE.
571 NAME is the SSA_NAME of the variable we found to have a constant
572 value on PATH. If unknown, SSA_NAME is NULL.
574 If the taken edge out of the path is known ahead of time it is passed in
575 TAKEN_EDGE, otherwise it is NULL.
577 CREATES_IRREDUCIBLE_LOOP, if non-null is set to TRUE if threading this path
578 would create an irreducible loop.
580 ?? It seems we should be able to loosen some of the restrictions in
581 this function after loop optimizations have run. */
584 back_threader_profitability::profitable_path_p (const vec
<basic_block
> &m_path
,
587 bool *creates_irreducible_loop
)
589 gcc_checking_assert (!m_path
.is_empty ());
591 /* We can an empty path here (excluding the DEF block) when the
592 statement that makes a conditional generate a compile-time
593 constant result is in the same block as the conditional.
595 That's not really a jump threading opportunity, but instead is
596 simple cprop & simplification. We could handle it here if we
597 wanted by wiring up all the incoming edges. If we run this
598 early in IPA, that might be worth doing. For now we just
600 if (m_path
.length () <= 1)
603 if (m_path
.length () > (unsigned) param_max_fsm_thread_length
)
605 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
606 fprintf (dump_file
, " FAIL: Jump-thread path not considered: "
607 "the number of basic blocks on the path "
608 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
613 gimple_stmt_iterator gsi
;
614 loop_p loop
= m_path
[0]->loop_father
;
615 bool threaded_through_latch
= false;
616 bool multiway_branch_in_path
= false;
617 bool threaded_multiway_branch
= false;
618 bool contains_hot_bb
= false;
620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
621 fprintf (dump_file
, "Checking profitability of path (backwards): ");
623 /* Count the number of instructions on the path: as these instructions
624 will have to be duplicated, we will not record the path if there
625 are too many instructions on the path. Also check that all the
626 blocks in the path belong to a single loop. */
627 for (unsigned j
= 0; j
< m_path
.length (); j
++)
629 basic_block bb
= m_path
[j
];
631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
632 fprintf (dump_file
, " bb:%i", bb
->index
);
633 /* Remember, blocks in the path are stored in opposite order in
634 the PATH array. The last entry in the array represents the
635 block with an outgoing edge that we will redirect to the jump
636 threading path. Thus we don't care how many statements are
637 in that block because it will not be copied or whether or not
638 it ends in a multiway branch. */
639 if (j
< m_path
.length () - 1)
641 int orig_n_insns
= n_insns
;
642 /* PHIs in the path will create degenerate PHIS in the
643 copied path which will then get propagated away, so
644 looking at just the duplicate path the PHIs would
647 But those PHIs, because they're assignments to objects
648 typically with lives that exist outside the thread path,
649 will tend to generate PHIs (or at least new PHI arguments)
650 at points where we leave the thread path and rejoin
651 the original blocks. So we do want to account for them.
653 We ignore virtual PHIs. We also ignore cases where BB
654 has a single incoming edge. That's the most common
655 degenerate PHI we'll see here. Finally we ignore PHIs
656 that are associated with the value we're tracking as
657 that object likely dies. */
658 if (EDGE_COUNT (bb
->succs
) > 1 && EDGE_COUNT (bb
->preds
) > 1)
660 for (gphi_iterator gsip
= gsi_start_phis (bb
);
664 gphi
*phi
= gsip
.phi ();
665 tree dst
= gimple_phi_result (phi
);
667 /* Note that if both NAME and DST are anonymous
668 SSA_NAMEs, then we do not have enough information
669 to consider them associated. */
672 && TREE_CODE (name
) == SSA_NAME
673 && (SSA_NAME_VAR (dst
) != SSA_NAME_VAR (name
)
674 || !SSA_NAME_VAR (dst
))
675 && !virtual_operand_p (dst
))
680 if (!contains_hot_bb
&& m_speed_p
)
681 contains_hot_bb
|= optimize_bb_for_speed_p (bb
);
682 for (gsi
= gsi_after_labels (bb
);
684 gsi_next_nondebug (&gsi
))
686 /* Do not allow OpenACC loop markers and __builtin_constant_p on
687 threading paths. The latter is disallowed, because an
688 expression might be constant on two threading paths, and
689 become non-constant (i.e.: phi) when they merge. */
690 gimple
*stmt
= gsi_stmt (gsi
);
691 if (gimple_call_internal_p (stmt
, IFN_UNIQUE
)
692 || gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
))
694 /* Do not count empty statements and labels. */
695 if (gimple_code (stmt
) != GIMPLE_NOP
696 && !is_gimple_debug (stmt
))
697 n_insns
+= estimate_num_insns (stmt
, &eni_size_weights
);
699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
700 fprintf (dump_file
, " (%i insns)", n_insns
-orig_n_insns
);
702 /* We do not look at the block with the threaded branch
703 in this loop. So if any block with a last statement that
704 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
705 multiway branch on our path.
707 The block in PATH[0] is special, it's the block were we're
708 going to be able to eliminate its branch. */
709 gimple
*last
= last_stmt (bb
);
710 if (last
&& (gimple_code (last
) == GIMPLE_SWITCH
711 || gimple_code (last
) == GIMPLE_GOTO
))
714 threaded_multiway_branch
= true;
716 multiway_branch_in_path
= true;
720 /* Note if we thread through the latch, we will want to include
721 the last entry in the array when determining if we thread
722 through the loop latch. */
723 if (loop
->latch
== bb
)
725 threaded_through_latch
= true;
726 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
727 fprintf (dump_file
, " (latch)");
731 gimple
*stmt
= get_gimple_control_stmt (m_path
[0]);
734 /* We are going to remove the control statement at the end of the
735 last block in the threading path. So don't count it against our
738 int stmt_insns
= estimate_num_insns (stmt
, &eni_size_weights
);
739 n_insns
-= stmt_insns
;
741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
742 fprintf (dump_file
, "\n Control statement insns: %i\n"
743 " Overall: %i insns\n",
744 stmt_insns
, n_insns
);
746 if (creates_irreducible_loop
)
748 /* If this path threaded through the loop latch back into the
749 same loop and the destination does not dominate the loop
750 latch, then this thread would create an irreducible loop. */
751 *creates_irreducible_loop
= false;
753 && threaded_through_latch
754 && loop
== taken_edge
->dest
->loop_father
755 && (determine_bb_domination_status (loop
, taken_edge
->dest
)
756 == DOMST_NONDOMINATING
))
757 *creates_irreducible_loop
= true;
760 /* Threading is profitable if the path duplicated is hot but also
761 in a case we separate cold path from hot path and permit optimization
762 of the hot path later. Be on the agressive side here. In some testcases,
763 as in PR 78407 this leads to noticeable improvements. */
765 && ((taken_edge
&& optimize_edge_for_speed_p (taken_edge
))
768 if (n_insns
>= param_max_fsm_thread_path_insns
)
770 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
771 fprintf (dump_file
, " FAIL: Jump-thread path not considered: "
772 "the number of instructions on the path "
773 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
777 else if (!m_speed_p
&& n_insns
> 1)
779 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
780 fprintf (dump_file
, " FAIL: Jump-thread path not considered: "
781 "duplication of %i insns is needed and optimizing for size.\n",
786 /* We avoid creating irreducible inner loops unless we thread through
787 a multiway branch, in which case we have deemed it worth losing
788 other loop optimizations later.
790 We also consider it worth creating an irreducible inner loop if
791 the number of copied statement is low relative to the length of
792 the path -- in that case there's little the traditional loop
793 optimizer would have done anyway, so an irreducible loop is not
795 if (!threaded_multiway_branch
796 && creates_irreducible_loop
797 && *creates_irreducible_loop
798 && (n_insns
* (unsigned) param_fsm_scale_path_stmts
799 > (m_path
.length () *
800 (unsigned) param_fsm_scale_path_blocks
)))
803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
805 " FAIL: Would create irreducible loop without threading "
806 "multiway branch.\n");
810 /* The generic copier used by the backthreader does not re-use an
811 existing threading path to reduce code duplication. So for that
812 case, drastically reduce the number of statements we are allowed
814 if (!(threaded_through_latch
&& threaded_multiway_branch
)
815 && (n_insns
* param_fsm_scale_path_stmts
816 >= param_max_jump_thread_duplication_stmts
))
818 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
820 " FAIL: Did not thread around loop and would copy too "
821 "many statements.\n");
825 /* When there is a multi-way branch on the path, then threading can
826 explode the CFG due to duplicating the edges for that multi-way
827 branch. So like above, only allow a multi-way branch on the path
828 if we actually thread a multi-way branch. */
829 if (!threaded_multiway_branch
&& multiway_branch_in_path
)
831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
833 " FAIL: Thread through multiway branch without threading "
834 "a multiway branch.\n");
838 /* Threading through an empty latch would cause code to be added to
839 the latch. This could alter the loop form sufficiently to cause
840 loop optimizations to fail. Disable these threads until after
841 loop optimizations have run. */
842 if ((threaded_through_latch
843 || (taken_edge
&& taken_edge
->dest
== loop
->latch
))
844 && !(cfun
->curr_properties
& PROP_loop_opts_done
)
845 && empty_block_p (loop
->latch
))
847 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
849 " FAIL: Thread through latch before loop opts would create non-empty latch\n");
856 /* The current path PATH is a vector of blocks forming a jump threading
857 path in reverse order. TAKEN_EDGE is the edge taken from path[0].
859 Convert the current path into the form used by register_jump_thread and
862 Return TRUE if successful or FALSE otherwise. */
865 back_threader_registry::register_path (const vec
<basic_block
> &m_path
,
868 vec
<jump_thread_edge
*> *jump_thread_path
= allocate_thread_path ();
870 // The generic copier ignores the edge type. We can build the
871 // thread edges with any type.
872 for (unsigned int j
= 0; j
+ 1 < m_path
.length (); j
++)
874 basic_block bb1
= m_path
[m_path
.length () - j
- 1];
875 basic_block bb2
= m_path
[m_path
.length () - j
- 2];
877 edge e
= find_edge (bb1
, bb2
);
879 push_edge (jump_thread_path
, e
, EDGE_COPY_SRC_BLOCK
);
882 push_edge (jump_thread_path
, taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
883 register_jump_thread (jump_thread_path
);
887 // Thread all suitable paths in the current function.
889 // Return TODO_flags.
892 back_threader::thread_blocks ()
895 FOR_EACH_BB_FN (bb
, m_fun
)
896 if (EDGE_COUNT (bb
->succs
) > 1)
897 maybe_thread_block (bb
);
899 bool changed
= m_registry
.thread_through_all_blocks (true);
901 if (m_flags
& BT_SPEED
)
902 return changed
? TODO_cleanup_cfg
: 0;
909 const pass_data pass_data_early_thread_jumps
=
914 TV_TREE_SSA_THREAD_JUMPS
,
915 ( PROP_cfg
| PROP_ssa
),
919 ( TODO_cleanup_cfg
| TODO_update_ssa
),
922 const pass_data pass_data_thread_jumps
=
927 TV_TREE_SSA_THREAD_JUMPS
,
928 ( PROP_cfg
| PROP_ssa
),
935 const pass_data pass_data_thread_jumps_full
=
940 TV_TREE_SSA_THREAD_JUMPS
,
941 ( PROP_cfg
| PROP_ssa
),
948 // Early jump threading pass optimizing for size.
949 class pass_early_thread_jumps
: public gimple_opt_pass
952 pass_early_thread_jumps (gcc::context
*ctxt
)
953 : gimple_opt_pass (pass_data_early_thread_jumps
, ctxt
)
956 opt_pass
* clone () override
958 return new pass_early_thread_jumps (m_ctxt
);
960 void set_pass_param (unsigned int, bool param
) override
964 bool gate (function
*) override
966 return flag_thread_jumps
;
968 unsigned int execute (function
*fun
) override
970 back_threader
threader (fun
, BT_NONE
, m_first
);
971 return threader
.thread_blocks ();
977 // Jump threading pass without resolving of unknown SSAs.
978 class pass_thread_jumps
: public gimple_opt_pass
981 pass_thread_jumps (gcc::context
*ctxt
)
982 : gimple_opt_pass (pass_data_thread_jumps
, ctxt
)
984 opt_pass
* clone (void) override
986 return new pass_thread_jumps (m_ctxt
);
988 void set_pass_param (unsigned int, bool param
) override
992 bool gate (function
*) override
994 return flag_thread_jumps
&& flag_expensive_optimizations
;
996 unsigned int execute (function
*fun
) override
998 back_threader
threader (fun
, BT_SPEED
, m_first
);
999 return threader
.thread_blocks ();
1005 // Jump threading pass that fully resolves unknown SSAs.
1006 class pass_thread_jumps_full
: public gimple_opt_pass
1009 pass_thread_jumps_full (gcc::context
*ctxt
)
1010 : gimple_opt_pass (pass_data_thread_jumps_full
, ctxt
)
1012 opt_pass
* clone (void) override
1014 return new pass_thread_jumps_full (m_ctxt
);
1016 void set_pass_param (unsigned int, bool param
) override
1020 bool gate (function
*) override
1022 return flag_thread_jumps
&& flag_expensive_optimizations
;
1024 unsigned int execute (function
*fun
) override
1026 back_threader
threader (fun
, BT_SPEED
| BT_RESOLVE
, m_first
);
1027 return threader
.thread_blocks ();
1036 make_pass_thread_jumps (gcc::context
*ctxt
)
1038 return new pass_thread_jumps (ctxt
);
1042 make_pass_thread_jumps_full (gcc::context
*ctxt
)
1044 return new pass_thread_jumps_full (ctxt
);
1048 make_pass_early_thread_jumps (gcc::context
*ctxt
)
1050 return new pass_early_thread_jumps (ctxt
);