2 Copyright (C) 2004-2022 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
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"
26 #include "tree-pass.h"
28 #include "fold-const.h"
32 #include "tree-ssa-loop-niter.h"
33 #include "tree-ssa-loop.h"
34 #include "tree-into-ssa.h"
36 #include "tree-inline.h"
37 #include "gimple-iterator.h"
39 #include "tree-ssa-loop-manip.h"
40 #include "tree-vectorizer.h"
41 #include "tree-pretty-print.h"
42 #include "gimple-range.h"
46 /* This file implements the loop unswitching, i.e. transformation of loops like
59 where inv is the loop invariant, into
78 Inv is considered invariant iff the values it compares are both invariant;
79 tree-ssa-loop-im.cc ensures that all the suitable conditions are in this
82 /* Loop unswitching algorithm for innermost loops works in the following steps:
84 1) Number of instructions is estimated for each BB that belongs to a loop.
85 2) Unswitching candidates are found for gcond and gswitch statements
86 (note that an unswitching predicate for a gswitch actually corresponds
87 to a non-default edge so it can contain multiple cases).
88 3) The so called unswitch predicates are stored in a cache where the
89 gimple_uid of the last stmt in a basic-block is an index to the cache.
90 4) We consider one by one the unswitching candidates and calculate BBs that
91 will be reachable in the unswitch version.
92 5) A selected predicate is chosen and we simplify the CFG (dead edges) in
93 both versions of the loop. We utilize both Ranger for condition
94 simplification and also symbol equivalence. The folded if conditions
95 are replaced with true/false values, while for gswitch we mark the
96 corresponding edges with a pass-defined unreachable flag.
97 6) Every time we unswitch a loop, we save unswitch_predicate to a vector
98 together with information if true or false edge was taken. Doing that
99 we have a so called PREDICATE_PATH that is utilized for simplification
101 7) The process is repeated until we reach a growth threshold or all
102 unswitching opportunities are taken. */
104 /* A tuple that holds a GENERIC condition and value range for an unswitching
107 struct unswitch_predicate
109 /* CTOR for a switch edge predicate. */
110 unswitch_predicate (tree cond, tree lhs_, int edge_index_, edge e,
111 const int_range_max& edge_range)
112 : condition (cond), lhs (lhs_),
113 true_range (edge_range), edge_index (edge_index_), switch_p (true)
115 gcc_assert (!(e->flags & (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE))
116 && irange::supports_p (TREE_TYPE (lhs)));
117 false_range = true_range;
118 if (!false_range.varying_p ()
119 && !false_range.undefined_p ())
120 false_range.invert ();
122 num = predicates->length ();
123 predicates->safe_push (this);
126 /* CTOR for a GIMPLE condition statement. */
127 unswitch_predicate (gcond *stmt)
130 basic_block bb = gimple_bb (stmt);
131 if (EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE)
135 lhs = gimple_cond_lhs (stmt);
136 tree rhs = gimple_cond_rhs (stmt);
137 enum tree_code code = gimple_cond_code (stmt);
138 condition = build2 (code, boolean_type_node, lhs, rhs);
139 count = EDGE_SUCC (bb, 0)->count ().max (EDGE_SUCC (bb, 1)->count ());
140 if (irange::supports_p (TREE_TYPE (lhs)))
142 auto range_op = range_op_handler (code, TREE_TYPE (lhs));
143 int_range<2> rhs_range (TREE_TYPE (rhs));
144 if (CONSTANT_CLASS_P (rhs))
145 rhs_range.set (rhs, rhs);
146 if (!range_op.op1_range (true_range, TREE_TYPE (lhs),
147 int_range<2> (boolean_true_node,
148 boolean_true_node), rhs_range)
149 || !range_op.op1_range (false_range, TREE_TYPE (lhs),
150 int_range<2> (boolean_false_node,
154 true_range.set_varying (TREE_TYPE (lhs));
155 false_range.set_varying (TREE_TYPE (lhs));
158 num = predicates->length ();
159 predicates->safe_push (this);
162 /* Copy ranges for purpose of usage in predicate path. */
165 copy_merged_ranges ()
167 merged_true_range = true_range;
168 merged_false_range = false_range;
171 /* GENERIC unswitching expression testing LHS against CONSTANT. */
174 /* LHS of the expression. */
177 /* Initial ranges (when the expression is true/false) for the expression. */
178 int_range_max true_range = {}, false_range = {};
180 /* Modified range that is part of a predicate path. */
181 int_range_max merged_true_range = {}, merged_false_range = {};
183 /* Index of the edge the predicate belongs to in the successor vector. */
186 /* The profile count of this predicate. */
189 /* Whether the predicate was created from a switch statement. */
192 /* The number of the predicate in the predicates vector below. */
195 /* Vector of all used predicates, used for assigning a unique id that
196 can be used for bitmap operations. */
197 static vec<unswitch_predicate *> *predicates;
200 vec<unswitch_predicate *> *unswitch_predicate::predicates;
202 /* Ranger instance used in the pass. */
203 static gimple_ranger *ranger = NULL;
205 /* Cache storage for unswitch_predicate belonging to a basic block. */
206 static vec<vec<unswitch_predicate *>> *bb_predicates;
208 /* The type represents a predicate path leading to a basic block. */
209 typedef vec<std::pair<unswitch_predicate *, bool>> predicate_vector;
211 static class loop *tree_unswitch_loop (class loop *, edge, tree);
212 static bool tree_unswitch_single_loop (class loop *, dump_user_location_t,
213 predicate_vector &predicate_path,
214 unsigned loop_size, unsigned &budget,
215 int ignored_edge_flag, bitmap,
216 unswitch_predicate * = NULL,
219 find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
220 class loop *&outer_loop,
221 vec<unswitch_predicate *> &candidates,
222 unswitch_predicate *&hottest,
223 basic_block &hottest_bb);
224 static bool tree_unswitch_outer_loop (class loop *);
225 static edge find_loop_guard (class loop *, vec<gimple *>&);
226 static bool empty_bb_without_guard_p (class loop *, basic_block,
228 static bool used_outside_loop_p (class loop *, tree, vec<gimple *>&);
229 static void hoist_guard (class loop *, edge);
230 static bool check_exit_phi (class loop *);
231 static tree get_vop_from_header (class loop *);
232 static void clean_up_after_unswitching (int);
234 /* Return vector of predicates that belong to a basic block. */
236 static vec<unswitch_predicate *> &
237 get_predicates_for_bb (basic_block bb)
239 gimple *last = last_stmt (bb);
240 return (*bb_predicates)[last == NULL ? 0 : gimple_uid (last)];
243 /* Save predicates that belong to a basic block. */
246 set_predicates_for_bb (basic_block bb, vec<unswitch_predicate *> predicates)
248 gimple_set_uid (last_stmt (bb), bb_predicates->length ());
249 bb_predicates->safe_push (predicates);
252 /* Initialize LOOP information reused during the unswitching pass.
253 Return total number of instructions in the loop. Adjusts LOOP to
254 the outermost loop all candidates are invariant in. */
257 init_loop_unswitch_info (class loop *&loop, unswitch_predicate *&hottest,
258 basic_block &hottest_bb)
260 unsigned total_insns = 0;
262 basic_block *bbs = get_loop_body (loop);
264 /* Unswitch only nests with no sibling loops. */
265 class loop *outer_loop = loop;
266 while (loop_outer (outer_loop)->num != 0
267 && !loop_outer (outer_loop)->inner->next)
268 outer_loop = loop_outer (outer_loop);
271 /* Find all unswitching candidates in the innermost loop. */
272 for (unsigned i = 0; i != loop->num_nodes; i++)
274 /* Find a bb to unswitch on. */
275 vec<unswitch_predicate *> candidates;
276 candidates.create (1);
277 find_unswitching_predicates_for_bb (bbs[i], loop, outer_loop, candidates,
278 hottest, hottest_bb);
279 if (!candidates.is_empty ())
280 set_predicates_for_bb (bbs[i], candidates);
283 candidates.release ();
284 gimple *last = last_stmt (bbs[i]);
286 gimple_set_uid (last, 0);
290 if (outer_loop != loop)
293 bbs = get_loop_body (outer_loop);
296 /* Calculate instruction count. */
297 for (unsigned i = 0; i < outer_loop->num_nodes; i++)
300 for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
302 insns += estimate_num_insns (gsi_stmt (gsi), &eni_size_weights);
303 /* No predicates to unswitch on in the outer loops. */
304 if (!flow_bb_inside_loop_p (loop, bbs[i]))
306 gimple *last = last_stmt (bbs[i]);
308 gimple_set_uid (last, 0);
311 bbs[i]->aux = (void *)(uintptr_t)insns;
312 total_insns += insns;
321 /* Main entry point. Perform loop unswitching on all suitable loops. */
324 tree_ssa_unswitch_loops (function *fun)
326 bool changed_unswitch = false;
327 bool changed_hoist = false;
328 auto_edge_flag ignored_edge_flag (fun);
330 ranger = enable_ranger (fun);
332 /* Go through all loops starting from innermost, hoisting guards. */
333 for (auto loop : loops_list (fun, LI_FROM_INNERMOST))
336 changed_hoist |= tree_unswitch_outer_loop (loop);
339 /* Go through innermost loops, unswitching on invariant predicates
341 for (auto loop : loops_list (fun, LI_ONLY_INNERMOST))
343 /* Perform initial tests if unswitch is eligible. */
344 dump_user_location_t loc = find_loop_location (loop);
346 /* Do not unswitch in cold regions. */
347 if (optimize_loop_for_size_p (loop))
349 if (dump_enabled_p ())
350 dump_printf_loc (MSG_NOTE, loc,
351 "Not unswitching cold loops\n");
355 /* If the loop is not expected to iterate, there is no need
357 HOST_WIDE_INT iterations = estimated_loop_iterations_int (loop);
359 iterations = likely_max_loop_iterations_int (loop);
360 if (iterations >= 0 && iterations <= 1)
362 if (dump_enabled_p ())
363 dump_printf_loc (MSG_NOTE, loc,
364 "Not unswitching, loop is not expected"
369 bb_predicates = new vec<vec<unswitch_predicate *>> ();
370 bb_predicates->safe_push (vec<unswitch_predicate *> ());
371 unswitch_predicate::predicates = new vec<unswitch_predicate *> ();
374 unswitch_predicate *hottest;
375 basic_block hottest_bb;
376 unsigned int loop_size = init_loop_unswitch_info (loop, hottest,
378 unsigned int budget = loop_size + param_max_unswitch_insns;
380 predicate_vector predicate_path;
381 predicate_path.create (8);
383 changed_unswitch |= tree_unswitch_single_loop (loop, loc, predicate_path,
385 ignored_edge_flag, handled,
386 hottest, hottest_bb);
387 predicate_path.release ();
389 for (auto predlist : bb_predicates)
391 bb_predicates->release ();
392 delete bb_predicates;
393 bb_predicates = NULL;
395 for (auto pred : unswitch_predicate::predicates)
397 unswitch_predicate::predicates->release ();
398 delete unswitch_predicate::predicates;
399 unswitch_predicate::predicates = NULL;
402 disable_ranger (fun);
403 clear_aux_for_blocks ();
405 if (changed_unswitch)
406 clean_up_after_unswitching (ignored_edge_flag);
408 if (changed_unswitch || changed_hoist)
409 return TODO_cleanup_cfg;
414 /* Return TRUE if an SSA_NAME maybe undefined and is therefore
415 unsuitable for unswitching. STMT is the statement we are
416 considering for unswitching and LOOP is the loop it appears in. */
419 is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
421 /* The loop header is the only block we can trivially determine that
422 will always be executed. If the comparison is in the loop
423 header, we know it's OK to unswitch on it. */
424 if (gimple_bb (stmt) == loop->header)
427 auto_bitmap visited_ssa;
428 auto_vec<tree> worklist;
429 worklist.safe_push (name);
430 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
431 while (!worklist.is_empty ())
433 tree t = worklist.pop ();
435 /* If it's obviously undefined, avoid further computations. */
436 if (ssa_undefined_value_p (t, true))
439 if (ssa_defined_default_def_p (t))
442 gimple *def = SSA_NAME_DEF_STMT (t);
444 /* Check that all the PHI args are fully defined. */
445 if (gphi *phi = dyn_cast <gphi *> (def))
447 for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
449 tree t = gimple_phi_arg_def (phi, i);
450 /* If an SSA has already been seen, it may be a loop,
451 but we can continue and ignore this use. Otherwise,
452 add the SSA_NAME to the queue and visit it later. */
453 if (TREE_CODE (t) == SSA_NAME
454 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
455 worklist.safe_push (t);
460 /* Uses in stmts always executed when the region header executes
462 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def)))
465 /* Handle calls and memory loads conservatively. */
466 if (!is_gimple_assign (def)
467 || (gimple_assign_single_p (def)
468 && gimple_vuse (def)))
471 /* Check that any SSA names used to define NAME are also fully
475 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
477 tree t = USE_FROM_PTR (use_p);
478 /* If an SSA has already been seen, it may be a loop,
479 but we can continue and ignore this use. Otherwise,
480 add the SSA_NAME to the queue and visit it later. */
481 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
482 worklist.safe_push (t);
488 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
489 basic blocks (for what it means see comments below).
490 All candidates all filled to the provided vector CANDIDATES.
491 OUTER_LOOP is updated to the innermost loop all found candidates are
495 find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
496 class loop *&outer_loop,
497 vec<unswitch_predicate *> &candidates,
498 unswitch_predicate *&hottest,
499 basic_block &hottest_bb)
506 /* BB must end in a simple conditional jump. */
507 last = last_stmt (bb);
511 if (gcond *stmt = safe_dyn_cast <gcond *> (last))
513 /* To keep the things simple, we do not directly remove the conditions,
514 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
515 loop where we would unswitch again on such a condition. */
516 if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
519 /* At least the LHS needs to be symbolic. */
520 if (TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME)
523 /* Condition must be invariant. */
524 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
526 def = SSA_NAME_DEF_STMT (use);
527 def_bb = gimple_bb (def);
529 && flow_bb_inside_loop_p (loop, def_bb))
531 /* Unswitching on undefined values would introduce undefined
532 behavior that the original program might never exercise. */
533 if (is_maybe_undefined (use, stmt, loop))
536 /* Narrow OUTER_LOOP. */
537 if (outer_loop != loop)
538 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
540 def = SSA_NAME_DEF_STMT (use);
541 def_bb = gimple_bb (def);
542 while (outer_loop != loop
543 && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb))
544 || is_maybe_undefined (use, stmt, outer_loop)))
545 outer_loop = superloop_at_depth (loop,
546 loop_depth (outer_loop) + 1);
549 unswitch_predicate *predicate = new unswitch_predicate (stmt);
550 candidates.safe_push (predicate);
551 /* If we unswitch on this predicate we isolate both paths, so
552 pick the highest count for updating of the hottest predicate
553 to unswitch on first. */
554 if (!hottest || predicate->count > hottest->count)
560 else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
562 unsigned nlabels = gimple_switch_num_labels (stmt);
563 tree idx = gimple_switch_index (stmt);
564 tree idx_type = TREE_TYPE (idx);
565 if (!gimple_range_ssa_p (idx) || nlabels < 1)
567 /* Index must be invariant. */
568 def = SSA_NAME_DEF_STMT (idx);
569 def_bb = gimple_bb (def);
571 && flow_bb_inside_loop_p (loop, def_bb))
573 /* Unswitching on undefined values would introduce undefined
574 behavior that the original program might never exercise. */
575 if (is_maybe_undefined (idx, stmt, loop))
577 /* Narrow OUTER_LOOP. */
578 while (outer_loop != loop
579 && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb))
580 || is_maybe_undefined (idx, stmt, outer_loop)))
581 outer_loop = superloop_at_depth (loop,
582 loop_depth (outer_loop) + 1);
584 /* Build compound expression for all outgoing edges of the switch. */
585 auto_vec<tree, 16> preds;
586 auto_vec<int_range_max> edge_range;
587 preds.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), true);
588 edge_range.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), true);
591 unsigned edge_index = 0;
592 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
593 e->aux = (void *)(uintptr_t)edge_index++;
594 for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i)
596 tree lab = gimple_switch_label (stmt, i);
598 int_range<2> lab_range;
599 tree low = fold_convert (idx_type, CASE_LOW (lab));
600 if (CASE_HIGH (lab) != NULL_TREE)
602 tree high = fold_convert (idx_type, CASE_HIGH (lab));
603 tree cmp1 = fold_build2 (GE_EXPR, boolean_type_node, idx, low);
604 tree cmp2 = fold_build2 (LE_EXPR, boolean_type_node, idx, high);
605 cmp = fold_build2 (BIT_AND_EXPR, boolean_type_node, cmp1, cmp2);
606 lab_range.set (low, high);
610 cmp = fold_build2 (EQ_EXPR, boolean_type_node, idx, low);
611 lab_range.set (low, low);
614 /* Combine the expression with the existing one. */
615 basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
616 e = find_edge (gimple_bb (stmt), dest);
617 tree &expr = preds[(uintptr_t)e->aux];
618 if (expr == NULL_TREE)
621 expr = fold_build2 (BIT_IOR_EXPR, boolean_type_node, expr, cmp);
622 edge_range[(uintptr_t)e->aux].union_ (lab_range);
625 /* Now register the predicates. */
626 for (edge_index = 0; edge_index < preds.length (); ++edge_index)
628 edge e = EDGE_SUCC (gimple_bb (stmt), edge_index);
630 if (preds[edge_index] != NULL_TREE)
632 unswitch_predicate *predicate
633 = new unswitch_predicate (preds[edge_index], idx,
635 edge_range[edge_index]);
636 candidates.safe_push (predicate);
637 if (!hottest || predicate->count > hottest->count)
647 /* Merge ranges for the last item of PREDICATE_PATH with a predicate
648 that shared the same LHS. */
651 merge_last (predicate_vector &predicate_path)
653 unswitch_predicate *last_predicate = predicate_path.last ().first;
655 for (int i = predicate_path.length () - 2; i >= 0; i--)
657 unswitch_predicate *predicate = predicate_path[i].first;
658 bool true_edge = predicate_path[i].second;
660 if (operand_equal_p (predicate->lhs, last_predicate->lhs, 0))
662 irange &other = (true_edge ? predicate->merged_true_range
663 : predicate->merged_false_range);
664 last_predicate->merged_true_range.intersect (other);
665 last_predicate->merged_false_range.intersect (other);
671 /* Add PREDICATE to PREDICATE_PATH on TRUE_EDGE. */
674 add_predicate_to_path (predicate_vector &predicate_path,
675 unswitch_predicate *predicate, bool true_edge)
677 predicate->copy_merged_ranges ();
678 predicate_path.safe_push (std::make_pair (predicate, true_edge));
679 merge_last (predicate_path);
683 find_range_for_lhs (predicate_vector &predicate_path, tree lhs,
684 int_range_max &range)
686 for (int i = predicate_path.length () - 1; i >= 0; i--)
688 unswitch_predicate *predicate = predicate_path[i].first;
689 bool true_edge = predicate_path[i].second;
691 if (operand_equal_p (predicate->lhs, lhs, 0))
693 range = (true_edge ? predicate->merged_true_range
694 : predicate->merged_false_range);
695 return !range.undefined_p ();
702 /* Simplifies STMT using the predicate we unswitched on which is the last
703 in PREDICATE_PATH. For switch statements add newly unreachable edges
704 to IGNORED_EDGES (but do not set IGNORED_EDGE_FLAG on them). */
707 evaluate_control_stmt_using_entry_checks (gimple *stmt,
708 predicate_vector &predicate_path,
709 int ignored_edge_flag,
710 hash_set<edge> *ignored_edges)
712 unswitch_predicate *last_predicate = predicate_path.last ().first;
713 bool true_edge = predicate_path.last ().second;
715 if (gcond *cond = dyn_cast<gcond *> (stmt))
717 tree lhs = gimple_cond_lhs (cond);
718 if (!operand_equal_p (lhs, last_predicate->lhs))
720 /* Try a symbolic match which works for floating point and fully
721 symbolic conditions. */
722 if (gimple_cond_code (cond) == TREE_CODE (last_predicate->condition)
723 && operand_equal_p (gimple_cond_rhs (cond),
724 TREE_OPERAND (last_predicate->condition, 1)))
725 return true_edge ? boolean_true_node : boolean_false_node;
726 /* Else try ranger if it supports LHS. */
727 else if (irange::supports_p (TREE_TYPE (lhs)))
730 int_range_max path_range;
732 if (find_range_for_lhs (predicate_path, lhs, path_range)
733 && fold_range (r, cond, path_range)
735 return r.zero_p () ? boolean_false_node : boolean_true_node;
738 else if (gswitch *swtch = dyn_cast<gswitch *> (stmt))
740 unsigned nlabels = gimple_switch_num_labels (swtch);
742 tree idx = gimple_switch_index (swtch);
744 /* Already folded switch. */
745 if (TREE_CONSTANT (idx))
748 int_range_max path_range;
749 if (!find_range_for_lhs (predicate_path, idx, path_range))
752 tree result = NULL_TREE;
753 edge single_edge = NULL;
754 for (unsigned i = 0; i < nlabels; ++i)
756 tree lab = gimple_switch_label (swtch, i);
757 basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
758 edge e = find_edge (gimple_bb (stmt), dest);
759 if (e->flags & ignored_edge_flag)
763 if (!ranger->gori ().outgoing_edge_range_p (r, e, idx,
764 *get_global_range_query ()))
766 r.intersect (path_range);
767 if (r.undefined_p ())
768 ignored_edges->add (e);
774 result = CASE_LOW (lab);
776 else if (single_edge != e)
781 /* Only one edge from the switch is alive. */
782 if (single_edge && result)
789 /* Simplify LOOP based on PREDICATE_PATH where dead edges are properly
793 simplify_loop_version (class loop *loop, predicate_vector &predicate_path,
794 int ignored_edge_flag, bitmap handled)
796 bool changed = false;
797 basic_block *bbs = get_loop_body (loop);
799 hash_set<edge> ignored_edges;
800 for (unsigned i = 0; i != loop->num_nodes; i++)
802 vec<unswitch_predicate *> &predicates = get_predicates_for_bb (bbs[i]);
803 if (predicates.is_empty ())
806 gimple *stmt = last_stmt (bbs[i]);
807 tree folded = evaluate_control_stmt_using_entry_checks (stmt,
812 if (gcond *cond = dyn_cast<gcond *> (stmt))
817 if (integer_nonzerop (folded))
818 gimple_cond_set_condition_from_tree (cond, boolean_true_node);
820 gimple_cond_set_condition_from_tree (cond, boolean_false_node);
822 gcc_assert (predicates.length () == 1);
823 bitmap_set_bit (handled, predicates[0]->num);
829 else if (gswitch *swtch = dyn_cast<gswitch *> (stmt))
833 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
834 if (ignored_edges.contains (e))
835 e->flags |= ignored_edge_flag;
837 for (unsigned j = 0; j < predicates.length (); j++)
839 edge e = EDGE_SUCC (bbs[i], predicates[j]->edge_index);
840 if (ignored_edges.contains (e))
841 bitmap_set_bit (handled, predicates[j]->num);
846 gimple_switch_set_index (swtch, folded);
857 /* Evaluate reachable blocks in LOOP and call VISIT on them, aborting the
858 DFS walk if VISIT returns true. When PREDICATE_PATH is specified then
859 take into account that when computing reachability, otherwise just
860 look at the simplified state and IGNORED_EDGE_FLAG. */
862 template <typename VisitOp>
864 evaluate_bbs (class loop *loop, predicate_vector *predicate_path,
865 int ignored_edge_flag, VisitOp visit)
867 auto_bb_flag reachable_flag (cfun);
868 auto_vec<basic_block, 10> worklist (loop->num_nodes);
869 auto_vec<basic_block, 10> reachable (loop->num_nodes);
870 hash_set<edge> ignored_edges;
872 loop->header->flags |= reachable_flag;
873 worklist.quick_push (loop->header);
874 reachable.safe_push (loop->header);
876 while (!worklist.is_empty ())
880 int flags = ignored_edge_flag;
881 basic_block bb = worklist.pop ();
886 gimple *last = last_stmt (bb);
887 if (gcond *cond = safe_dyn_cast <gcond *> (last))
889 if (gimple_cond_true_p (cond))
890 flags = EDGE_FALSE_VALUE;
891 else if (gimple_cond_false_p (cond))
892 flags = EDGE_TRUE_VALUE;
893 else if (predicate_path)
896 if (!get_predicates_for_bb (bb).is_empty ()
897 && (res = evaluate_control_stmt_using_entry_checks
898 (cond, *predicate_path, ignored_edge_flag,
900 flags = (integer_nonzerop (res)
901 ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE);
904 else if (gswitch *swtch = safe_dyn_cast<gswitch *> (last))
906 && !get_predicates_for_bb (bb).is_empty ())
907 evaluate_control_stmt_using_entry_checks (swtch, *predicate_path,
911 /* Note that for the moment we do not account reachable conditions
912 which are simplified to take a known edge as zero size nor
913 are we accounting for the required addition of the versioning
914 condition. Those should cancel out conservatively. */
916 FOR_EACH_EDGE (e, ei, bb->succs)
918 basic_block dest = e->dest;
920 if (flow_bb_inside_loop_p (loop, dest)
921 && !(dest->flags & reachable_flag)
922 && !(e->flags & flags)
923 && !ignored_edges.contains (e))
925 dest->flags |= reachable_flag;
926 worklist.safe_push (dest);
927 reachable.safe_push (dest);
932 /* Clear the flag from basic blocks. */
933 while (!reachable.is_empty ())
934 reachable.pop ()->flags &= ~reachable_flag;
937 /* Evaluate how many instruction will we have if we unswitch LOOP (with BBS)
938 based on PREDICATE predicate (using PREDICATE_PATH). Store the
939 result in TRUE_SIZE and FALSE_SIZE. */
942 evaluate_loop_insns_for_predicate (class loop *loop,
943 predicate_vector &predicate_path,
944 unswitch_predicate *predicate,
945 int ignored_edge_flag,
946 unsigned *true_size, unsigned *false_size)
949 auto sum_size = [&](basic_block bb) -> bool
950 { size += (uintptr_t)bb->aux; return false; };
952 add_predicate_to_path (predicate_path, predicate, true);
953 evaluate_bbs (loop, &predicate_path, ignored_edge_flag, sum_size);
954 predicate_path.pop ();
955 unsigned true_loop_cost = size;
958 add_predicate_to_path (predicate_path, predicate, false);
959 evaluate_bbs (loop, &predicate_path, ignored_edge_flag, sum_size);
960 predicate_path.pop ();
961 unsigned false_loop_cost = size;
963 *true_size = true_loop_cost;
964 *false_size = false_loop_cost;
967 /* Unswitch single LOOP. PREDICATE_PATH contains so far used predicates
968 for unswitching. BUDGET is number of instruction for which we can increase
969 the loop and is updated when unswitching occurs. If HOTTEST is not
970 NULL then pick this candidate as the one to unswitch on. */
973 tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc,
974 predicate_vector &predicate_path,
975 unsigned loop_size, unsigned &budget,
976 int ignored_edge_flag, bitmap handled,
977 unswitch_predicate *hottest, basic_block hottest_bb)
980 bool changed = false;
981 unswitch_predicate *predicate = NULL;
982 basic_block predicate_bb = NULL;
983 unsigned true_size = 0, false_size = 0;
985 auto check_predicates = [&](basic_block bb) -> bool
987 for (auto pred : get_predicates_for_bb (bb))
989 if (bitmap_bit_p (handled, pred->num))
992 evaluate_loop_insns_for_predicate (loop, predicate_path,
993 pred, ignored_edge_flag,
994 &true_size, &false_size);
996 /* We'll get LOOP replaced with a simplified version according
997 to PRED estimated to TRUE_SIZE and a copy simplified
998 according to the inverted PRED estimated to FALSE_SIZE. */
999 if (true_size + false_size < budget + loop_size)
1004 /* There are cases where true_size and false_size add up to
1005 less than the original loop_size. We do not want to
1006 grow the remaining budget because of that. */
1007 if (true_size + false_size > loop_size)
1008 budget -= (true_size + false_size - loop_size);
1010 /* FIXME: right now we select first candidate, but we can
1011 choose the cheapest or hottest one. */
1014 else if (dump_enabled_p ())
1015 dump_printf_loc (MSG_NOTE, loc,
1016 "not unswitching condition, cost too big "
1017 "(%u insns copied to %u and %u)\n", loop_size,
1018 true_size, false_size);
1025 predicate = hottest;
1026 predicate_bb = hottest_bb;
1029 /* Check predicates of reachable blocks. */
1030 evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates);
1032 if (predicate != NULL)
1034 if (!dbg_cnt (loop_unswitch))
1037 if (dump_enabled_p ())
1039 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
1040 "unswitching %sloop %d on %qs with condition: %T\n",
1041 loop->inner ? "outer " : "",
1042 loop->num, predicate->switch_p ? "switch" : "if",
1043 predicate->condition);
1044 dump_printf_loc (MSG_NOTE, loc,
1045 "optimized sizes estimated to %u (true) "
1046 "and %u (false) from original size %u\n",
1047 true_size, false_size, loop_size);
1050 bitmap_set_bit (handled, predicate->num);
1051 initialize_original_copy_tables ();
1052 /* Unswitch the loop on this condition. */
1053 nloop = tree_unswitch_loop (loop, EDGE_SUCC (predicate_bb,
1054 predicate->edge_index),
1055 predicate->condition);
1058 free_original_copy_tables ();
1062 /* Copy BB costs. */
1063 basic_block *bbs2 = get_loop_body (nloop);
1064 for (unsigned i = 0; i < nloop->num_nodes; i++)
1065 bbs2[i]->aux = get_bb_original (bbs2[i])->aux;
1068 free_original_copy_tables ();
1070 /* Update the SSA form after unswitching. */
1071 update_ssa (TODO_update_ssa_no_phi);
1073 /* Invoke itself on modified loops. */
1074 bitmap handled_copy = BITMAP_ALLOC (NULL);
1075 bitmap_copy (handled_copy, handled);
1076 add_predicate_to_path (predicate_path, predicate, false);
1077 changed |= simplify_loop_version (nloop, predicate_path,
1078 ignored_edge_flag, handled_copy);
1079 tree_unswitch_single_loop (nloop, loc, predicate_path,
1081 ignored_edge_flag, handled_copy);
1082 predicate_path.pop ();
1083 BITMAP_FREE (handled_copy);
1085 /* FIXME: After unwinding above we have to reset all ->handled
1086 flags as otherwise we fail to realize unswitching opportunities
1087 in the below recursion. See gcc.dg/loop-unswitch-16.c */
1088 add_predicate_to_path (predicate_path, predicate, true);
1089 changed |= simplify_loop_version (loop, predicate_path,
1090 ignored_edge_flag, handled);
1091 tree_unswitch_single_loop (loop, loc, predicate_path,
1093 ignored_edge_flag, handled);
1094 predicate_path.pop ();
1102 /* Unswitch a LOOP w.r. to given EDGE_TRUE. We only support unswitching of
1103 innermost loops. COND is the condition determining which loop is entered;
1104 the new loop is entered if COND is true. Returns NULL if impossible, new
1108 tree_unswitch_loop (class loop *loop, edge edge_true, tree cond)
1110 /* Some sanity checking. */
1111 gcc_assert (flow_bb_inside_loop_p (loop, edge_true->src));
1112 gcc_assert (EDGE_COUNT (edge_true->src->succs) >= 2);
1114 profile_probability prob_true = edge_true->probability;
1115 return loop_version (loop, unshare_expr (cond),
1117 prob_true.invert (),
1118 prob_true, prob_true.invert (),
1122 /* Unswitch outer loops by hoisting invariant guard on
1123 inner loop without code duplication. */
1125 tree_unswitch_outer_loop (class loop *loop)
1128 HOST_WIDE_INT iterations;
1130 gcc_assert (loop->inner);
1131 if (loop->inner->next)
1133 /* Accept loops with single exit only which is not from inner loop. */
1134 exit = single_exit (loop);
1135 if (!exit || exit->src->loop_father != loop)
1137 /* Check that phi argument of exit edge is not defined inside loop. */
1138 if (!check_exit_phi (loop))
1140 /* If the loop is not expected to iterate, there is no need
1142 iterations = estimated_loop_iterations_int (loop);
1144 iterations = likely_max_loop_iterations_int (loop);
1145 if (iterations >= 0 && iterations <= 1)
1147 if (dump_enabled_p ())
1148 dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop),
1149 "Not unswitching, loop is not expected"
1154 bool changed = false;
1155 auto_vec<gimple *> dbg_to_reset;
1156 while ((guard = find_loop_guard (loop, dbg_to_reset)))
1158 hoist_guard (loop, guard);
1159 for (gimple *debug_stmt : dbg_to_reset)
1161 gimple_debug_bind_reset_value (debug_stmt);
1162 update_stmt (debug_stmt);
1164 dbg_to_reset.truncate (0);
1170 /* Checks if the body of the LOOP is within an invariant guard. If this
1171 is the case, returns the edge that jumps over the real body of the loop,
1172 otherwise returns NULL. */
1175 find_loop_guard (class loop *loop, vec<gimple *> &dbg_to_reset)
1177 basic_block header = loop->header;
1178 edge guard_edge, te, fe;
1179 basic_block *body = NULL;
1184 /* We check for the following situation:
1193 nvar = phi(orig, bvar) ... for all variables changed in body;
1203 1) cond1 is loop invariant
1204 2) If cond1 is false, then the loop is essentially empty; i.e.,
1205 a) nothing in something1, something2 and something3 has side
1207 b) anything defined in something1, something2 and something3
1208 is not used outside of the loop. */
1213 basic_block next = NULL;
1214 if (single_succ_p (header))
1215 next = single_succ (header);
1218 cond = safe_dyn_cast <gcond *> (last_stmt (header));
1221 extract_true_false_edges_from_block (header, &te, &fe);
1222 /* Make sure to skip earlier hoisted guards that are left
1223 in place as if (true). */
1224 if (gimple_cond_true_p (cond))
1226 else if (gimple_cond_false_p (cond))
1231 /* Never traverse a backedge. */
1232 if (header->loop_father->header == next)
1237 if (!flow_bb_inside_loop_p (loop, te->dest)
1238 || !flow_bb_inside_loop_p (loop, fe->dest))
1241 if (just_once_each_iteration_p (loop, te->dest)
1242 || (single_succ_p (te->dest)
1243 && just_once_each_iteration_p (loop, single_succ (te->dest))))
1245 if (just_once_each_iteration_p (loop, fe->dest))
1249 else if (just_once_each_iteration_p (loop, fe->dest)
1250 || (single_succ_p (fe->dest)
1251 && just_once_each_iteration_p (loop, single_succ (fe->dest))))
1256 dump_user_location_t loc = find_loop_location (loop);
1258 /* Guard edge must skip inner loop. */
1259 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
1260 guard_edge == fe ? te->dest : fe->dest))
1262 if (dump_enabled_p ())
1263 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1264 "Guard edge %d --> %d is not around the loop!\n",
1265 guard_edge->src->index, guard_edge->dest->index);
1268 if (guard_edge->dest == loop->latch)
1270 if (dump_enabled_p ())
1271 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1272 "Guard edge destination is loop latch.\n");
1276 if (dump_enabled_p ())
1277 dump_printf_loc (MSG_NOTE, loc,
1278 "Considering guard %d -> %d in loop %d\n",
1279 guard_edge->src->index, guard_edge->dest->index,
1281 /* Check if condition operands do not have definitions inside loop since
1282 any bb copying is not performed. */
1283 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
1285 gimple *def = SSA_NAME_DEF_STMT (use);
1286 basic_block def_bb = gimple_bb (def);
1288 && flow_bb_inside_loop_p (loop, def_bb))
1290 if (dump_enabled_p ())
1291 dump_printf_loc (MSG_NOTE, loc, "guard operands have definitions"
1297 body = get_loop_body (loop);
1298 for (i = 0; i < loop->num_nodes; i++)
1300 basic_block bb = body[i];
1301 if (bb->loop_father != loop)
1303 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1305 if (dump_enabled_p ())
1306 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1307 "Block %d is marked as irreducible in loop\n",
1312 if (!empty_bb_without_guard_p (loop, bb, dbg_to_reset))
1314 if (dump_enabled_p ())
1315 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1316 "Block %d has side effects\n", bb->index);
1322 if (dump_enabled_p ())
1323 dump_printf_loc (MSG_NOTE, loc,
1324 "suitable to hoist\n");
1332 1) no statement in BB has side effects
1333 2) assuming that edge GUARD is always taken, all definitions in BB
1334 are noy used outside of the loop.
1335 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
1336 PROCESSED is a set of ssa names for that we already tested whether they
1337 are invariant or not. Uses in debug stmts outside of the loop are
1338 pushed to DBG_TO_RESET. */
1341 empty_bb_without_guard_p (class loop *loop, basic_block bb,
1342 vec<gimple *> &dbg_to_reset)
1344 basic_block exit_bb = single_exit (loop)->src;
1345 bool may_be_used_outside = (bb == exit_bb
1346 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
1348 ssa_op_iter op_iter;
1350 /* Phi nodes do not have side effects, but their results might be used
1351 outside of the loop. */
1352 if (may_be_used_outside)
1354 for (gphi_iterator gsi = gsi_start_phis (bb);
1355 !gsi_end_p (gsi); gsi_next (&gsi))
1357 gphi *phi = gsi.phi ();
1358 name = PHI_RESULT (phi);
1359 if (virtual_operand_p (name))
1362 if (used_outside_loop_p (loop, name, dbg_to_reset))
1367 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1368 !gsi_end_p (gsi); gsi_next (&gsi))
1370 gimple *stmt = gsi_stmt (gsi);
1371 if (is_gimple_debug (stmt))
1374 if (gimple_has_side_effects (stmt))
1377 if (gimple_vdef(stmt))
1380 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
1382 if (may_be_used_outside
1383 && used_outside_loop_p (loop, name, dbg_to_reset))
1390 /* Return true if NAME is used outside of LOOP. Pushes debug stmts that
1391 have such uses to DBG_TO_RESET but do not consider such uses. */
1394 used_outside_loop_p (class loop *loop, tree name, vec<gimple *> &dbg_to_reset)
1396 imm_use_iterator it;
1399 FOR_EACH_IMM_USE_FAST (use, it, name)
1401 gimple *stmt = USE_STMT (use);
1402 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1404 if (!is_gimple_debug (stmt))
1406 dbg_to_reset.safe_push (stmt);
1413 /* Return argument for loop preheader edge in header virtual phi if any. */
1416 get_vop_from_header (class loop *loop)
1418 for (gphi_iterator gsi = gsi_start_phis (loop->header);
1419 !gsi_end_p (gsi); gsi_next (&gsi))
1421 gphi *phi = gsi.phi ();
1422 if (!virtual_operand_p (gimple_phi_result (phi)))
1424 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1429 /* Move the check of GUARD outside of LOOP. */
1432 hoist_guard (class loop *loop, edge guard)
1434 edge exit = single_exit (loop);
1435 edge preh = loop_preheader_edge (loop);
1436 basic_block pre_header = preh->src;
1438 edge te, fe, e, new_edge;
1440 basic_block guard_bb = guard->src;
1442 gimple_stmt_iterator gsi;
1444 bool fix_dom_of_exit;
1445 gcond *cond_stmt, *new_cond_stmt;
1447 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
1448 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
1449 gsi = gsi_last_bb (guard_bb);
1450 stmt = gsi_stmt (gsi);
1451 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
1452 cond_stmt = as_a <gcond *> (stmt);
1453 extract_true_false_edges_from_block (guard_bb, &te, &fe);
1454 /* Insert guard to PRE_HEADER. */
1455 if (!empty_block_p (pre_header))
1456 gsi = gsi_last_bb (pre_header);
1458 gsi = gsi_start_bb (pre_header);
1459 /* Create copy of COND_STMT. */
1460 new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
1461 gimple_cond_lhs (cond_stmt),
1462 gimple_cond_rhs (cond_stmt),
1463 NULL_TREE, NULL_TREE);
1464 gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
1465 /* Convert COND_STMT to true/false conditional. */
1467 gimple_cond_make_false (cond_stmt);
1469 gimple_cond_make_true (cond_stmt);
1470 update_stmt (cond_stmt);
1471 /* Create new loop pre-header. */
1472 e = split_block (pre_header, last_stmt (pre_header));
1474 dump_user_location_t loc = find_loop_location (loop);
1476 if (dump_enabled_p ())
1479 guard->probability.dump (buffer);
1481 dump_printf_loc (MSG_NOTE, loc,
1482 "Moving guard %i->%i (prob %s) to bb %i, "
1483 "new preheader is %i\n",
1484 guard->src->index, guard->dest->index,
1485 buffer, e->src->index, e->dest->index);
1488 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
1492 e->flags = EDGE_TRUE_VALUE;
1493 flags |= EDGE_FALSE_VALUE;
1498 e->flags = EDGE_FALSE_VALUE;
1499 flags |= EDGE_TRUE_VALUE;
1502 new_edge = make_edge (pre_header, exit->dest, flags);
1504 /* Determine the probability that we skip the loop. Assume that loop has
1505 same average number of iterations regardless outcome of guard. */
1506 new_edge->probability = guard->probability;
1507 profile_count skip_count = guard->src->count.nonzero_p ()
1508 ? guard->count ().apply_scale (pre_header->count,
1510 : guard->count ().apply_probability (new_edge->probability);
1512 if (skip_count > e->count ())
1514 fprintf (dump_file, " Capping count; expect profile inconsistency\n");
1515 skip_count = e->count ();
1517 if (dump_enabled_p ())
1520 new_edge->probability.dump (buffer);
1522 dump_printf_loc (MSG_NOTE, loc,
1523 "Estimated probability of skipping loop is %s\n",
1527 /* Update profile after the transform:
1529 First decrease count of path from newly hoisted loop guard
1530 to loop header... */
1531 e->probability = new_edge->probability.invert ();
1532 e->dest->count = e->count ();
1534 /* ... now update profile to represent that original guard will be optimized
1536 guard->probability = profile_probability::never ();
1537 not_guard->probability = profile_probability::always ();
1539 /* ... finally scale everything in the loop except for guarded basic blocks
1540 where profile does not change. */
1541 basic_block *body = get_loop_body (loop);
1543 for (unsigned int i = 0; i < loop->num_nodes; i++)
1545 basic_block bb = body[i];
1546 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
1548 if (dump_enabled_p ())
1549 dump_printf_loc (MSG_NOTE, loc,
1550 "Scaling nonguarded BBs in loop: %i\n",
1552 if (e->probability.initialized_p ())
1553 scale_bbs_frequencies (&bb, 1, e->probability);
1557 if (fix_dom_of_exit)
1558 set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
1559 /* Add NEW_ADGE argument for all phi in post-header block. */
1561 for (gphi_iterator gsi = gsi_start_phis (bb);
1562 !gsi_end_p (gsi); gsi_next (&gsi))
1564 gphi *phi = gsi.phi ();
1566 if (virtual_operand_p (gimple_phi_result (phi)))
1568 arg = get_vop_from_header (loop);
1569 if (arg == NULL_TREE)
1570 /* Use exit edge argument. */
1571 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1572 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
1576 /* Use exit edge argument. */
1577 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1578 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
1582 if (dump_enabled_p ())
1583 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
1589 /* Return true if phi argument for exit edge can be used
1590 for edge around loop. */
1593 check_exit_phi (class loop *loop)
1595 edge exit = single_exit (loop);
1596 basic_block pre_header = loop_preheader_edge (loop)->src;
1598 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
1599 !gsi_end_p (gsi); gsi_next (&gsi))
1601 gphi *phi = gsi.phi ();
1605 if (virtual_operand_p (gimple_phi_result (phi)))
1607 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1608 if (TREE_CODE (arg) != SSA_NAME)
1610 def = SSA_NAME_DEF_STMT (arg);
1613 def_bb = gimple_bb (def);
1616 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
1617 /* Definition inside loop! */
1619 /* Check loop closed phi invariant. */
1620 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
1626 /* Remove all dead cases from switches that are unswitched. */
1629 clean_up_after_unswitching (int ignored_edge_flag)
1635 FOR_EACH_BB_FN (bb, cfun)
1637 gswitch *stmt= safe_dyn_cast <gswitch *> (last_stmt (bb));
1638 if (stmt && !CONSTANT_CLASS_P (gimple_switch_index (stmt)))
1640 unsigned nlabels = gimple_switch_num_labels (stmt);
1642 tree lab = gimple_switch_default_label (stmt);
1643 edge default_e = find_edge (gimple_bb (stmt),
1644 label_to_block (cfun, CASE_LABEL (lab)));
1645 for (unsigned i = 1; i < nlabels; ++i)
1647 tree lab = gimple_switch_label (stmt, i);
1648 basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
1649 edge e = find_edge (gimple_bb (stmt), dest);
1651 ; /* The edge is already removed. */
1652 else if (e->flags & ignored_edge_flag)
1654 /* We may not remove the default label so we also have
1655 to preserve its edge. But we can remove the
1656 non-default CASE sharing the edge. */
1662 gimple_switch_set_label (stmt, index, lab);
1667 if (index != nlabels)
1668 gimple_switch_set_num_labels (stmt, index);
1671 /* Clean up the ignored_edge_flag from edges. */
1672 FOR_EACH_EDGE (e, ei, bb->succs)
1673 e->flags &= ~ignored_edge_flag;
1677 /* Loop unswitching pass. */
1681 const pass_data pass_data_tree_unswitch =
1683 GIMPLE_PASS, /* type */
1684 "unswitch", /* name */
1685 OPTGROUP_LOOP, /* optinfo_flags */
1686 TV_TREE_LOOP_UNSWITCH, /* tv_id */
1687 PROP_cfg, /* properties_required */
1688 0, /* properties_provided */
1689 0, /* properties_destroyed */
1690 0, /* todo_flags_start */
1691 0, /* todo_flags_finish */
1694 class pass_tree_unswitch : public gimple_opt_pass
1697 pass_tree_unswitch (gcc::context *ctxt)
1698 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
1701 /* opt_pass methods: */
1702 bool gate (function *) final override { return flag_unswitch_loops != 0; }
1703 unsigned int execute (function *) final override;
1705 }; // class pass_tree_unswitch
1708 pass_tree_unswitch::execute (function *fun)
1710 if (number_of_loops (fun) <= 1)
1713 return tree_ssa_unswitch_loops (fun);
1719 make_pass_tree_unswitch (gcc::context *ctxt)
1721 return new pass_tree_unswitch (ctxt);