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"
45 #include "tree-pretty-print.h"
48 // Path registry for the backwards threader. After all paths have been
49 // registered with register_path(), thread_through_all_blocks() is called
52 class back_threader_registry
55 bool register_path (const vec
<basic_block
> &, edge taken
);
56 bool thread_through_all_blocks (bool may_peel_loop_headers
);
58 back_jt_path_registry m_lowlevel_registry
;
61 // Class to abstract the profitability code for the backwards threader.
63 class back_threader_profitability
66 back_threader_profitability (bool speed_p
)
69 bool profitable_path_p (const vec
<basic_block
> &, tree name
, edge taken
,
70 bool *irreducible_loop
= NULL
);
78 back_threader (bool speed_p
, bool resolve
);
79 void maybe_thread_block (basic_block bb
);
80 bool thread_through_all_blocks (bool may_peel_loop_headers
);
82 void find_paths (basic_block bb
, tree name
);
83 edge
maybe_register_path ();
84 bool find_paths_to_names (basic_block bb
, bitmap imports
);
85 bool resolve_def (tree name
, bitmap interesting
, vec
<tree
> &worklist
);
86 bool resolve_phi (gphi
*phi
, bitmap imports
);
87 edge
find_taken_edge (const vec
<basic_block
> &path
);
88 edge
find_taken_edge_cond (const vec
<basic_block
> &path
, gcond
*);
89 edge
find_taken_edge_switch (const vec
<basic_block
> &path
, gswitch
*);
90 virtual void debug ();
91 virtual void dump (FILE *out
);
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.
104 auto_bitmap m_imports
;
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
;
112 // Set to TRUE if unknown SSA names along a path should be resolved
113 // with the ranger. Otherwise, unknown SSA names are assumed to be
114 // VARYING. Setting to true is more precise but slower.
118 // Used to differentiate unreachable edges, so we may stop the search
119 // in a the given direction.
120 const edge
back_threader::UNREACHABLE_EDGE
= (edge
) -1;
122 back_threader::back_threader (bool speed_p
, bool resolve
)
123 : m_profit (speed_p
),
124 m_solver (m_ranger
, resolve
)
130 // Register the current path for jump threading if it's profitable to
133 // Return the known taken edge out of the path, even if the path was
134 // not registered, or NULL if the taken edge could not be determined.
137 back_threader::maybe_register_path ()
139 edge taken_edge
= find_taken_edge (m_path
);
141 if (taken_edge
&& taken_edge
!= UNREACHABLE_EDGE
)
143 bool irreducible
= false;
145 = m_profit
.profitable_path_p (m_path
, m_name
, taken_edge
, &irreducible
);
149 m_registry
.register_path (m_path
, taken_edge
);
152 vect_free_loop_info_assumptions (m_path
[0]->loop_father
);
158 // Return the known taken edge out of a path. If the path can be
159 // determined to be unreachable, return UNREACHABLE_EDGE. If no
160 // outgoing edge can be calculated, return NULL.
163 back_threader::find_taken_edge (const vec
<basic_block
> &path
)
165 gcc_checking_assert (path
.length () > 1);
166 switch (gimple_code (m_last_stmt
))
169 return find_taken_edge_cond (path
, as_a
<gcond
*> (m_last_stmt
));
172 return find_taken_edge_switch (path
, as_a
<gswitch
*> (m_last_stmt
));
179 // Same as find_taken_edge, but for paths ending in a switch.
182 back_threader::find_taken_edge_switch (const vec
<basic_block
> &path
,
185 tree name
= gimple_switch_index (sw
);
188 m_solver
.compute_ranges (path
, m_imports
);
189 m_solver
.range_of_expr (r
, name
, sw
);
191 if (r
.undefined_p ())
192 return UNREACHABLE_EDGE
;
198 if (r
.singleton_p (&val
))
199 return ::find_taken_edge (gimple_bb (sw
), val
);
204 // Same as find_taken_edge, but for paths ending in a GIMPLE_COND.
207 back_threader::find_taken_edge_cond (const vec
<basic_block
> &path
,
212 m_solver
.compute_ranges (path
, m_imports
);
213 m_solver
.range_of_stmt (r
, cond
);
215 if (m_solver
.unreachable_path_p ())
216 return UNREACHABLE_EDGE
;
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 // FIXME: We currently stop looking if we find a threadable path
279 // through a PHI. This is pessimistic, as there can be multiple
280 // paths that can resolve the path. For example:
282 // x_5 = PHI <10(4), 20(5), ...>
285 tree arg
= gimple_phi_arg_def (phi
, i
);
286 if (TREE_CODE (arg
) == SSA_NAME
)
288 unsigned v
= SSA_NAME_VERSION (arg
);
290 // Avoid loops as in: x_5 = PHI <x_5(2), ...>.
291 if (bitmap_bit_p (interesting
, v
))
294 bitmap_set_bit (interesting
, v
);
295 bitmap_set_bit (m_imports
, v
);
297 // When resolving unknowns, see if the incoming SSA can be
298 // resolved on entry without having to keep looking back.
299 bool keep_looking
= true;
302 m_path
.safe_push (e
->src
);
303 if (maybe_register_path ())
305 keep_looking
= false;
306 m_visited_bbs
.add (e
->src
);
311 done
|= find_paths_to_names (e
->src
, interesting
);
313 bitmap_clear_bit (interesting
, v
);
315 else if (TREE_CODE (arg
) == INTEGER_CST
)
317 m_path
.safe_push (e
->src
);
318 edge taken_edge
= maybe_register_path ();
319 if (taken_edge
&& taken_edge
!= UNREACHABLE_EDGE
)
327 // If the definition of NAME causes the final conditional of the
328 // current path to be constant, register the path, and return TRUE.
331 back_threader::resolve_def (tree name
, bitmap interesting
, vec
<tree
> &worklist
)
333 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
336 if (is_a
<gphi
*> (def_stmt
)
337 && resolve_phi (as_a
<gphi
*> (def_stmt
), interesting
))
340 // Defer copies of SSAs by adding the source to the worklist.
341 if (gimple_assign_single_p (def_stmt
)
342 && TREE_CODE (gimple_assign_rhs1 (def_stmt
)) == SSA_NAME
)
344 tree rhs
= gimple_assign_rhs1 (def_stmt
);
345 bitmap_set_bit (m_imports
, SSA_NAME_VERSION (rhs
));
346 bitmap_set_bit (interesting
, SSA_NAME_VERSION (rhs
));
347 worklist
.safe_push (rhs
);
352 // Find jump threading paths to any of the SSA names in the
353 // INTERESTING bitmap, and register any such paths.
355 // Return TRUE if no further processing past this block is necessary.
356 // This is because we've either registered a path, or because there is
357 // nothing of interesting beyond this block.
359 // BB is the current path being processed.
362 back_threader::find_paths_to_names (basic_block bb
, bitmap interesting
)
364 if (m_visited_bbs
.add (bb
))
367 m_path
.safe_push (bb
);
369 if (m_path
.length () > 1
370 && !m_profit
.profitable_path_p (m_path
, m_name
, NULL
))
373 m_visited_bbs
.remove (bb
);
377 // Try to resolve the path with nothing but ranger knowledge.
378 if (m_resolve
&& m_path
.length () > 1 && maybe_register_path ())
381 m_visited_bbs
.remove (bb
);
385 auto_bitmap processed
;
389 // We use a worklist instead of iterating through the bitmap,
390 // because we may add new items in-flight.
391 auto_vec
<tree
> worklist (bitmap_count_bits (interesting
));
392 populate_worklist (worklist
, interesting
);
393 while (!worklist
.is_empty ())
395 tree name
= worklist
.pop ();
396 unsigned i
= SSA_NAME_VERSION (name
);
397 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
399 // Process any names defined in this block.
402 bitmap_set_bit (processed
, i
);
404 if (resolve_def (name
, interesting
, worklist
))
410 // Examine blocks that define or export an interesting SSA,
411 // since they may compute a range which resolve this path.
413 || bitmap_bit_p (m_ranger
.gori ().exports (bb
), i
))
414 && m_path
.length () > 1)
416 if (maybe_register_path ())
424 // If there are interesting names not yet processed, keep looking.
425 bitmap_and_compl_into (interesting
, processed
);
426 if (!bitmap_empty_p (interesting
))
430 FOR_EACH_EDGE (e
, iter
, bb
->preds
)
431 if ((e
->flags
& EDGE_ABNORMAL
) == 0)
432 done
|= find_paths_to_names (e
->src
, interesting
);
437 EXECUTE_IF_SET_IN_BITMAP (processed
, 0, i
, bi
)
438 bitmap_set_bit (interesting
, i
);
441 m_visited_bbs
.remove (bb
);
445 // Search backwards from BB looking for paths where the final
446 // conditional out of BB can be determined. NAME is the LHS of the
447 // final conditional. Register such paths for jump threading.
450 back_threader::find_paths (basic_block bb
, tree name
)
452 gimple
*stmt
= last_stmt (bb
);
454 || (gimple_code (stmt
) != GIMPLE_COND
455 && gimple_code (stmt
) != GIMPLE_SWITCH
))
458 if (EDGE_COUNT (bb
->succs
) > 1
459 || single_succ_to_potentially_threadable_block (bb
))
462 m_visited_bbs
.empty ();
465 bitmap_clear (m_imports
);
467 auto_bitmap interesting
;
468 bitmap_copy (m_imports
, m_ranger
.gori ().imports (bb
));
469 bitmap_copy (interesting
, m_imports
);
470 find_paths_to_names (bb
, interesting
);
474 // Simple helper to get the last statement from BB, which is assumed
475 // to be a control statement. Return NULL if the last statement is
476 // not a control statement.
479 get_gimple_control_stmt (basic_block bb
)
481 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
486 gimple
*stmt
= gsi_stmt (gsi
);
487 enum gimple_code code
= gimple_code (stmt
);
488 if (code
== GIMPLE_COND
|| code
== GIMPLE_SWITCH
|| code
== GIMPLE_GOTO
)
493 // Search backwards from BB looking for paths where the final
494 // conditional maybe threaded to a successor block. Record such paths
495 // for jump threading.
498 back_threader::maybe_thread_block (basic_block bb
)
500 gimple
*stmt
= get_gimple_control_stmt (bb
);
504 enum gimple_code code
= gimple_code (stmt
);
506 if (code
== GIMPLE_SWITCH
)
507 name
= gimple_switch_index (as_a
<gswitch
*> (stmt
));
508 else if (code
== GIMPLE_COND
)
509 name
= gimple_cond_lhs (stmt
);
510 else if (code
== GIMPLE_GOTO
)
511 name
= gimple_goto_dest (stmt
);
515 find_paths (bb
, name
);
518 // Perform the actual jump threading for the all queued paths.
521 back_threader::thread_through_all_blocks (bool may_peel_loop_headers
)
523 return m_registry
.thread_through_all_blocks (may_peel_loop_headers
);
526 // Dump a sequence of BBs through the CFG.
529 dump_path (FILE *dump_file
, const vec
<basic_block
> &path
)
531 for (size_t i
= 0; i
< path
.length (); ++i
)
533 fprintf (dump_file
, "BB%d", path
[i
]->index
);
534 if (i
+ 1 < path
.length ())
535 fprintf (dump_file
, " <- ");
537 fprintf (dump_file
, "\n");
541 debug (const vec
<basic_block
> &path
)
543 dump_path (stderr
, path
);
547 back_threader::dump (FILE *out
)
550 fprintf (out
, "\nCandidates for pre-computation:\n");
551 fprintf (out
, "===================================\n");
556 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
558 tree name
= ssa_name (i
);
559 print_generic_expr (out
, name
, TDF_NONE
);
565 back_threader::debug ()
571 back_threader_registry::thread_through_all_blocks (bool may_peel_loop_headers
)
573 return m_lowlevel_registry
.thread_through_all_blocks (may_peel_loop_headers
);
576 /* Examine jump threading path PATH and return TRUE if it is profitable to
577 thread it, otherwise return FALSE.
579 NAME is the SSA_NAME of the variable we found to have a constant
580 value on PATH. If unknown, SSA_NAME is NULL.
582 If the taken edge out of the path is known ahead of time it is passed in
583 TAKEN_EDGE, otherwise it is NULL.
585 CREATES_IRREDUCIBLE_LOOP, if non-null is set to TRUE if threading this path
586 would create an irreducible loop.
588 ?? It seems we should be able to loosen some of the restrictions in
589 this function after loop optimizations have run. */
592 back_threader_profitability::profitable_path_p (const vec
<basic_block
> &m_path
,
595 bool *creates_irreducible_loop
)
597 gcc_checking_assert (!m_path
.is_empty ());
599 /* We can an empty path here (excluding the DEF block) when the
600 statement that makes a conditional generate a compile-time
601 constant result is in the same block as the conditional.
603 That's not really a jump threading opportunity, but instead is
604 simple cprop & simplification. We could handle it here if we
605 wanted by wiring up all the incoming edges. If we run this
606 early in IPA, that might be worth doing. For now we just
608 if (m_path
.length () <= 1)
611 if (m_path
.length () > (unsigned) param_max_fsm_thread_length
)
613 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
614 fprintf (dump_file
, " FAIL: Jump-thread path not considered: "
615 "the number of basic blocks on the path "
616 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
621 gimple_stmt_iterator gsi
;
622 loop_p loop
= m_path
[0]->loop_father
;
623 bool path_crosses_loops
= false;
624 bool threaded_through_latch
= false;
625 bool multiway_branch_in_path
= false;
626 bool threaded_multiway_branch
= false;
627 bool contains_hot_bb
= false;
629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
630 fprintf (dump_file
, "Checking profitability of path (backwards): ");
632 /* Count the number of instructions on the path: as these instructions
633 will have to be duplicated, we will not record the path if there
634 are too many instructions on the path. Also check that all the
635 blocks in the path belong to a single loop. */
636 for (unsigned j
= 0; j
< m_path
.length (); j
++)
638 basic_block bb
= m_path
[j
];
640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
641 fprintf (dump_file
, " bb:%i", bb
->index
);
642 /* Remember, blocks in the path are stored in opposite order
643 in the PATH array. The last entry in the array represents
644 the block with an outgoing edge that we will redirect to the
645 jump threading path. Thus we don't care about that block's
646 loop father, nor how many statements are in that block because
647 it will not be copied or whether or not it ends in a multiway
649 if (j
< m_path
.length () - 1)
651 int orig_n_insns
= n_insns
;
652 if (bb
->loop_father
!= loop
)
654 path_crosses_loops
= true;
656 // Dump rest of blocks.
657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
658 for (j
++; j
< m_path
.length (); j
++)
661 fprintf (dump_file
, " bb:%i", bb
->index
);
666 /* PHIs in the path will create degenerate PHIS in the
667 copied path which will then get propagated away, so
668 looking at just the duplicate path the PHIs would
671 But those PHIs, because they're assignments to objects
672 typically with lives that exist outside the thread path,
673 will tend to generate PHIs (or at least new PHI arguments)
674 at points where we leave the thread path and rejoin
675 the original blocks. So we do want to account for them.
677 We ignore virtual PHIs. We also ignore cases where BB
678 has a single incoming edge. That's the most common
679 degenerate PHI we'll see here. Finally we ignore PHIs
680 that are associated with the value we're tracking as
681 that object likely dies. */
682 if (EDGE_COUNT (bb
->succs
) > 1 && EDGE_COUNT (bb
->preds
) > 1)
684 for (gphi_iterator gsip
= gsi_start_phis (bb
);
688 gphi
*phi
= gsip
.phi ();
689 tree dst
= gimple_phi_result (phi
);
691 /* Note that if both NAME and DST are anonymous
692 SSA_NAMEs, then we do not have enough information
693 to consider them associated. */
696 && TREE_CODE (name
) == SSA_NAME
697 && (SSA_NAME_VAR (dst
) != SSA_NAME_VAR (name
)
698 || !SSA_NAME_VAR (dst
))
699 && !virtual_operand_p (dst
))
704 if (!contains_hot_bb
&& m_speed_p
)
705 contains_hot_bb
|= optimize_bb_for_speed_p (bb
);
706 for (gsi
= gsi_after_labels (bb
);
708 gsi_next_nondebug (&gsi
))
710 /* Do not allow OpenACC loop markers and __builtin_constant_p on
711 threading paths. The latter is disallowed, because an
712 expression might be constant on two threading paths, and
713 become non-constant (i.e.: phi) when they merge. */
714 gimple
*stmt
= gsi_stmt (gsi
);
715 if (gimple_call_internal_p (stmt
, IFN_UNIQUE
)
716 || gimple_call_builtin_p (stmt
, BUILT_IN_CONSTANT_P
))
718 /* Do not count empty statements and labels. */
719 if (gimple_code (stmt
) != GIMPLE_NOP
720 && !(gimple_code (stmt
) == GIMPLE_ASSIGN
721 && gimple_assign_rhs_code (stmt
) == ASSERT_EXPR
)
722 && !is_gimple_debug (stmt
))
723 n_insns
+= estimate_num_insns (stmt
, &eni_size_weights
);
725 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
726 fprintf (dump_file
, " (%i insns)", n_insns
-orig_n_insns
);
728 /* We do not look at the block with the threaded branch
729 in this loop. So if any block with a last statement that
730 is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
731 multiway branch on our path.
733 The block in PATH[0] is special, it's the block were we're
734 going to be able to eliminate its branch. */
735 gimple
*last
= last_stmt (bb
);
736 if (last
&& (gimple_code (last
) == GIMPLE_SWITCH
737 || gimple_code (last
) == GIMPLE_GOTO
))
740 threaded_multiway_branch
= true;
742 multiway_branch_in_path
= true;
746 /* Note if we thread through the latch, we will want to include
747 the last entry in the array when determining if we thread
748 through the loop latch. */
749 if (loop
->latch
== bb
)
751 threaded_through_latch
= true;
752 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
753 fprintf (dump_file
, " (latch)");
757 gimple
*stmt
= get_gimple_control_stmt (m_path
[0]);
760 /* We are going to remove the control statement at the end of the
761 last block in the threading path. So don't count it against our
764 int stmt_insns
= estimate_num_insns (stmt
, &eni_size_weights
);
765 n_insns
-= stmt_insns
;
767 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
768 fprintf (dump_file
, "\n Control statement insns: %i\n"
769 " Overall: %i insns\n",
770 stmt_insns
, n_insns
);
772 if (creates_irreducible_loop
)
774 /* If this path threaded through the loop latch back into the
775 same loop and the destination does not dominate the loop
776 latch, then this thread would create an irreducible loop. */
777 *creates_irreducible_loop
= false;
779 && threaded_through_latch
780 && loop
== taken_edge
->dest
->loop_father
781 && (determine_bb_domination_status (loop
, taken_edge
->dest
)
782 == DOMST_NONDOMINATING
))
783 *creates_irreducible_loop
= true;
786 if (path_crosses_loops
)
788 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
789 fprintf (dump_file
, " FAIL: Jump-thread path not considered: "
790 "the path crosses loops.\n");
794 /* Threading is profitable if the path duplicated is hot but also
795 in a case we separate cold path from hot path and permit optimization
796 of the hot path later. Be on the agressive side here. In some testcases,
797 as in PR 78407 this leads to noticeable improvements. */
799 && ((taken_edge
&& optimize_edge_for_speed_p (taken_edge
))
802 if (n_insns
>= param_max_fsm_thread_path_insns
)
804 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
805 fprintf (dump_file
, " FAIL: Jump-thread path not considered: "
806 "the number of instructions on the path "
807 "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
811 else if (!m_speed_p
&& n_insns
> 1)
813 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
814 fprintf (dump_file
, " FAIL: Jump-thread path not considered: "
815 "duplication of %i insns is needed and optimizing for size.\n",
820 /* We avoid creating irreducible inner loops unless we thread through
821 a multiway branch, in which case we have deemed it worth losing
822 other loop optimizations later.
824 We also consider it worth creating an irreducible inner loop if
825 the number of copied statement is low relative to the length of
826 the path -- in that case there's little the traditional loop
827 optimizer would have done anyway, so an irreducible loop is not
829 if (!threaded_multiway_branch
830 && creates_irreducible_loop
831 && *creates_irreducible_loop
832 && (n_insns
* (unsigned) param_fsm_scale_path_stmts
833 > (m_path
.length () *
834 (unsigned) param_fsm_scale_path_blocks
)))
837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
839 " FAIL: Would create irreducible loop without threading "
840 "multiway branch.\n");
844 /* The generic copier used by the backthreader does not re-use an
845 existing threading path to reduce code duplication. So for that
846 case, drastically reduce the number of statements we are allowed
848 if (!(threaded_through_latch
&& threaded_multiway_branch
)
849 && (n_insns
* param_fsm_scale_path_stmts
850 >= param_max_jump_thread_duplication_stmts
))
852 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
854 " FAIL: Did not thread around loop and would copy too "
855 "many statements.\n");
859 /* When there is a multi-way branch on the path, then threading can
860 explode the CFG due to duplicating the edges for that multi-way
861 branch. So like above, only allow a multi-way branch on the path
862 if we actually thread a multi-way branch. */
863 if (!threaded_multiway_branch
&& multiway_branch_in_path
)
865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
867 " FAIL: Thread through multiway branch without threading "
868 "a multiway branch.\n");
872 /* Threading through an empty latch would cause code to be added to
873 the latch. This could alter the loop form sufficiently to cause
874 loop optimizations to fail. Disable these threads until after
875 loop optimizations have run. */
876 if ((threaded_through_latch
877 || (taken_edge
&& taken_edge
->dest
== loop
->latch
))
878 && !(cfun
->curr_properties
& PROP_loop_opts_done
)
879 && empty_block_p (loop
->latch
))
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
883 " FAIL: Thread through latch before loop opts would create non-empty latch\n");
890 /* The current path PATH is a vector of blocks forming a jump threading
891 path in reverse order. TAKEN_EDGE is the edge taken from path[0].
893 Convert the current path into the form used by register_jump_thread and
896 Return TRUE if successful or FALSE otherwise. */
899 back_threader_registry::register_path (const vec
<basic_block
> &m_path
,
902 vec
<jump_thread_edge
*> *jump_thread_path
903 = m_lowlevel_registry
.allocate_thread_path ();
905 // The generic copier ignores the edge type. We can build the
906 // thread edges with any type.
907 for (unsigned int j
= 0; j
+ 1 < m_path
.length (); j
++)
909 basic_block bb1
= m_path
[m_path
.length () - j
- 1];
910 basic_block bb2
= m_path
[m_path
.length () - j
- 2];
912 edge e
= find_edge (bb1
, bb2
);
914 m_lowlevel_registry
.push_edge (jump_thread_path
, e
, EDGE_COPY_SRC_BLOCK
);
917 m_lowlevel_registry
.push_edge (jump_thread_path
,
918 taken_edge
, EDGE_NO_COPY_SRC_BLOCK
);
919 m_lowlevel_registry
.register_jump_thread (jump_thread_path
);
923 // Try to thread blocks in FUN. RESOLVE is TRUE when fully resolving
924 // unknown SSAs. SPEED is TRUE when optimizing for speed.
926 // Return TRUE if any jump thread paths were registered.
929 try_thread_blocks (function
*fun
, bool resolve
, bool speed
)
931 back_threader
threader (speed
, resolve
);
933 FOR_EACH_BB_FN (bb
, fun
)
935 if (EDGE_COUNT (bb
->succs
) > 1)
936 threader
.maybe_thread_block (bb
);
938 return threader
.thread_through_all_blocks (/*peel_loop_headers=*/true);
942 do_early_thread_jumps (function
*fun
, bool resolve
)
944 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
946 try_thread_blocks (fun
, resolve
, /*speed=*/false);
948 loop_optimizer_finalize ();
953 do_thread_jumps (function
*fun
, bool resolve
)
955 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
957 bool changed
= try_thread_blocks (fun
, resolve
, /*speed=*/true);
959 loop_optimizer_finalize ();
961 return changed
? TODO_cleanup_cfg
: 0;
966 const pass_data pass_data_early_thread_jumps
=
971 TV_TREE_SSA_THREAD_JUMPS
,
972 ( PROP_cfg
| PROP_ssa
),
976 ( TODO_cleanup_cfg
| TODO_update_ssa
),
979 const pass_data pass_data_thread_jumps
=
984 TV_TREE_SSA_THREAD_JUMPS
,
985 ( PROP_cfg
| PROP_ssa
),
992 const pass_data pass_data_thread_jumps_full
=
997 TV_TREE_SSA_THREAD_JUMPS
,
998 ( PROP_cfg
| PROP_ssa
),
1005 // Early jump threading pass optimizing for size.
1006 class pass_early_thread_jumps
: public gimple_opt_pass
1009 pass_early_thread_jumps (gcc::context
*ctxt
)
1010 : gimple_opt_pass (pass_data_early_thread_jumps
, ctxt
)
1013 opt_pass
* clone () override
1015 return new pass_early_thread_jumps (m_ctxt
);
1017 bool gate (function
*) override
1019 return flag_thread_jumps
;
1021 unsigned int execute (function
*fun
) override
1023 return do_early_thread_jumps (fun
, /*resolve=*/false);
1027 // Jump threading pass without resolving of unknown SSAs.
1028 class pass_thread_jumps
: public gimple_opt_pass
1031 pass_thread_jumps (gcc::context
*ctxt
)
1032 : gimple_opt_pass (pass_data_thread_jumps
, ctxt
)
1034 opt_pass
* clone (void) override
1036 return new pass_thread_jumps (m_ctxt
);
1038 bool gate (function
*) override
1040 return flag_thread_jumps
&& flag_expensive_optimizations
;
1042 unsigned int execute (function
*fun
) override
1044 return do_thread_jumps (fun
, /*resolve=*/false);
1048 // Jump threading pass that fully resolves unknown SSAs.
1049 class pass_thread_jumps_full
: public gimple_opt_pass
1052 pass_thread_jumps_full (gcc::context
*ctxt
)
1053 : gimple_opt_pass (pass_data_thread_jumps_full
, ctxt
)
1055 opt_pass
* clone (void) override
1057 return new pass_thread_jumps_full (m_ctxt
);
1059 bool gate (function
*) override
1061 return flag_thread_jumps
&& flag_expensive_optimizations
;
1063 unsigned int execute (function
*fun
) override
1065 return do_thread_jumps (fun
, /*resolve=*/true);
1072 make_pass_thread_jumps (gcc::context
*ctxt
)
1074 return new pass_thread_jumps (ctxt
);
1078 make_pass_thread_jumps_full (gcc::context
*ctxt
)
1080 return new pass_thread_jumps_full (ctxt
);
1084 make_pass_early_thread_jumps (gcc::context
*ctxt
)
1086 return new pass_early_thread_jumps (ctxt
);