1/* Loop unswitching.
2 Copyright (C) 2004-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "tree.h"
25#include "gimple.h"
26#include "tree-pass.h"
27#include "ssa.h"
28#include "fold-const.h"
29#include "gimplify.h"
30#include "tree-cfg.h"
31#include "tree-ssa.h"
32#include "tree-ssa-loop-niter.h"
33#include "tree-ssa-loop.h"
34#include "tree-into-ssa.h"
35#include "cfgloop.h"
36#include "tree-inline.h"
37#include "gimple-iterator.h"
38#include "cfghooks.h"
39#include "tree-ssa-loop-manip.h"
40#include "tree-vectorizer.h"
41#include "tree-pretty-print.h"
42#include "gimple-range.h"
43#include "dbgcnt.h"
44#include "cfganal.h"
45
46/* This file implements the loop unswitching, i.e. transformation of loops like
47
48 while (A)
49 {
50 if (inv)
51 B;
52
53 X;
54
55 if (!inv)
56 C;
57 }
58
59 where inv is the loop invariant, into
60
61 if (inv)
62 {
63 while (A)
64 {
65 B;
66 X;
67 }
68 }
69 else
70 {
71 while (A)
72 {
73 X;
74 C;
75 }
76 }
77
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
80 shape. */
81
82/* Loop unswitching algorithm for innermost loops works in the following steps:
83
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
100 of the cloned loop.
101 7) The process is repeated until we reach a growth threshold or all
102 unswitching opportunities are taken. */
103
104/* A tuple that holds a GENERIC condition and value range for an unswitching
105 predicate. */
106
107struct unswitch_predicate
108{
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)
114 {
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 ();
121 count = e->count ();
122 num = predicates->length ();
123 predicates->safe_push (obj: this);
124 }
125
126 /* CTOR for a GIMPLE condition statement. */
127 unswitch_predicate (gcond *stmt)
128 : switch_p (false)
129 {
130 basic_block bb = gimple_bb (g: stmt);
131 if (EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE)
132 edge_index = 0;
133 else
134 edge_index = 1;
135 lhs = gimple_cond_lhs (gs: stmt);
136 tree rhs = gimple_cond_rhs (gs: stmt);
137 enum tree_code code = gimple_cond_code (gs: 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)))
141 {
142 auto range_op = range_op_handler (code);
143 int_range<2> rhs_range (TREE_TYPE (rhs));
144 if (CONSTANT_CLASS_P (rhs))
145 {
146 wide_int w = wi::to_wide (t: rhs);
147 rhs_range.set (TREE_TYPE (rhs), w, w);
148 }
149 if (!range_op.op1_range (r&: true_range, TREE_TYPE (lhs),
150 lhs: range_true (), op2: rhs_range)
151 || !range_op.op1_range (r&: false_range, TREE_TYPE (lhs),
152 lhs: range_false (), op2: rhs_range))
153 {
154 true_range.set_varying (TREE_TYPE (lhs));
155 false_range.set_varying (TREE_TYPE (lhs));
156 }
157 }
158 num = predicates->length ();
159 predicates->safe_push (obj: this);
160 }
161
162 /* Copy ranges for purpose of usage in predicate path. */
163
164 inline void
165 copy_merged_ranges ()
166 {
167 merged_true_range = true_range;
168 merged_false_range = false_range;
169 }
170
171 /* GENERIC unswitching expression testing LHS against CONSTANT. */
172 tree condition;
173
174 /* LHS of the expression. */
175 tree lhs;
176
177 /* Initial ranges (when the expression is true/false) for the expression. */
178 int_range_max true_range = {}, false_range = {};
179
180 /* Modified range that is part of a predicate path. */
181 int_range_max merged_true_range = {}, merged_false_range = {};
182
183 /* Index of the edge the predicate belongs to in the successor vector. */
184 int edge_index;
185
186 /* The profile count of this predicate. */
187 profile_count count;
188
189 /* Whether the predicate was created from a switch statement. */
190 bool switch_p;
191
192 /* The number of the predicate in the predicates vector below. */
193 unsigned num;
194
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;
198};
199
200vec<unswitch_predicate *> *unswitch_predicate::predicates;
201
202/* Ranger instance used in the pass. */
203static gimple_ranger *ranger = NULL;
204
205/* Cache storage for unswitch_predicate belonging to a basic block. */
206static vec<vec<unswitch_predicate *>> *bb_predicates;
207
208/* The type represents a predicate path leading to a basic block. */
209typedef vec<std::pair<unswitch_predicate *, bool>> predicate_vector;
210
211static class loop *tree_unswitch_loop (class loop *, edge, tree);
212static 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,
217 basic_block = NULL);
218static void
219find_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);
224static bool tree_unswitch_outer_loop (class loop *);
225static edge find_loop_guard (class loop *, vec<gimple *>&);
226static bool empty_bb_without_guard_p (class loop *, basic_block,
227 vec<gimple *>&);
228static bool used_outside_loop_p (class loop *, tree, vec<gimple *>&);
229static void hoist_guard (class loop *, edge);
230static bool check_exit_phi (class loop *);
231static tree get_vop_from_header (class loop *);
232static void clean_up_after_unswitching (int);
233
234/* Return vector of predicates that belong to a basic block. */
235
236static vec<unswitch_predicate *> &
237get_predicates_for_bb (basic_block bb)
238{
239 gimple *last = last_nondebug_stmt (bb);
240 return (*bb_predicates)[last == NULL ? 0 : gimple_uid (g: last)];
241}
242
243/* Save predicates that belong to a basic block. */
244
245static void
246set_predicates_for_bb (basic_block bb, vec<unswitch_predicate *> predicates)
247{
248 gimple_set_uid (g: last_nondebug_stmt (bb), uid: bb_predicates->length ());
249 bb_predicates->safe_push (obj: predicates);
250}
251
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. */
255
256static unsigned
257init_loop_unswitch_info (class loop *&loop, unswitch_predicate *&hottest,
258 basic_block &hottest_bb)
259{
260 unsigned total_insns = 0;
261
262 basic_block *bbs = get_loop_body (loop);
263
264 /* Unswitch only nests with no sibling loops. */
265 class loop *outer_loop = loop;
266 unsigned max_depth = param_max_unswitch_depth;
267 while (loop_outer (loop: outer_loop)->num != 0
268 && !loop_outer (loop: outer_loop)->inner->next
269 && --max_depth != 0)
270 outer_loop = loop_outer (loop: outer_loop);
271 hottest = NULL;
272 hottest_bb = NULL;
273 /* Find all unswitching candidates in the innermost loop. */
274 for (unsigned i = 0; i != loop->num_nodes; i++)
275 {
276 /* Find a bb to unswitch on. */
277 vec<unswitch_predicate *> candidates;
278 candidates.create (nelems: 1);
279 find_unswitching_predicates_for_bb (bb: bbs[i], loop, outer_loop, candidates,
280 hottest, hottest_bb);
281 if (!candidates.is_empty ())
282 set_predicates_for_bb (bb: bbs[i], predicates: candidates);
283 else
284 {
285 candidates.release ();
286 gimple *last = last_nondebug_stmt (bbs[i]);
287 if (last != NULL)
288 gimple_set_uid (g: last, uid: 0);
289 }
290 }
291
292 if (outer_loop != loop)
293 {
294 free (ptr: bbs);
295 bbs = get_loop_body (outer_loop);
296 }
297
298 /* Calculate instruction count. */
299 for (unsigned i = 0; i < outer_loop->num_nodes; i++)
300 {
301 unsigned insns = 0;
302 for (gimple_stmt_iterator gsi = gsi_start_bb (bb: bbs[i]); !gsi_end_p (i: gsi);
303 gsi_next (i: &gsi))
304 insns += estimate_num_insns (gsi_stmt (i: gsi), &eni_size_weights);
305 /* No predicates to unswitch on in the outer loops. */
306 if (!flow_bb_inside_loop_p (loop, bbs[i]))
307 {
308 gimple *last = last_nondebug_stmt (bbs[i]);
309 if (last != NULL)
310 gimple_set_uid (g: last, uid: 0);
311 }
312
313 bbs[i]->aux = (void *)(uintptr_t)insns;
314 total_insns += insns;
315 }
316
317 free (ptr: bbs);
318
319 loop = outer_loop;
320 return total_insns;
321}
322
323/* Main entry point. Perform loop unswitching on all suitable loops. */
324
325unsigned int
326tree_ssa_unswitch_loops (function *fun)
327{
328 bool changed_unswitch = false;
329 bool changed_hoist = false;
330 auto_edge_flag ignored_edge_flag (fun);
331
332 ranger = enable_ranger (m: fun);
333
334 /* Go through all loops starting from innermost, hoisting guards. */
335 for (auto loop : loops_list (fun, LI_FROM_INNERMOST))
336 {
337 if (loop->inner)
338 changed_hoist |= tree_unswitch_outer_loop (loop);
339 }
340
341 /* Go through innermost loops, unswitching on invariant predicates
342 within those. */
343 for (auto loop : loops_list (fun, LI_ONLY_INNERMOST))
344 {
345 /* Perform initial tests if unswitch is eligible. */
346 dump_user_location_t loc = find_loop_location (loop);
347
348 /* Do not unswitch in cold regions. */
349 if (optimize_loop_for_size_p (loop))
350 {
351 if (dump_enabled_p ())
352 dump_printf_loc (MSG_NOTE, loc,
353 "Not unswitching cold loops\n");
354 continue;
355 }
356
357 /* If the loop is not expected to iterate, there is no need
358 for unswitching. */
359 HOST_WIDE_INT iterations = estimated_loop_iterations_int (loop);
360 if (iterations < 0)
361 iterations = likely_max_loop_iterations_int (loop);
362 if (iterations >= 0 && iterations <= 1)
363 {
364 if (dump_enabled_p ())
365 dump_printf_loc (MSG_NOTE, loc,
366 "Not unswitching, loop is not expected"
367 " to iterate\n");
368 continue;
369 }
370
371 bb_predicates = new vec<vec<unswitch_predicate *>> ();
372 bb_predicates->safe_push (obj: vec<unswitch_predicate *> ());
373 unswitch_predicate::predicates = new vec<unswitch_predicate *> ();
374
375 /* Unswitch loop. */
376 unswitch_predicate *hottest;
377 basic_block hottest_bb;
378 unsigned int loop_size = init_loop_unswitch_info (loop, hottest,
379 hottest_bb);
380 unsigned int budget = loop_size + param_max_unswitch_insns;
381
382 predicate_vector predicate_path;
383 predicate_path.create (nelems: 8);
384 auto_bitmap handled;
385 changed_unswitch |= tree_unswitch_single_loop (loop, loc, predicate_path,
386 loop_size, budget,
387 ignored_edge_flag, handled,
388 hottest, hottest_bb);
389 predicate_path.release ();
390
391 for (auto predlist : bb_predicates)
392 predlist.release ();
393 bb_predicates->release ();
394 delete bb_predicates;
395 bb_predicates = NULL;
396
397 for (auto pred : unswitch_predicate::predicates)
398 delete pred;
399 unswitch_predicate::predicates->release ();
400 delete unswitch_predicate::predicates;
401 unswitch_predicate::predicates = NULL;
402 }
403
404 disable_ranger (fun);
405 clear_aux_for_blocks ();
406
407 if (changed_unswitch)
408 clean_up_after_unswitching (ignored_edge_flag);
409
410 if (changed_unswitch || changed_hoist)
411 return TODO_cleanup_cfg;
412
413 return 0;
414}
415
416/* Return TRUE if an SSA_NAME maybe undefined and is therefore
417 unsuitable for unswitching. STMT is the statement we are
418 considering for unswitching and LOOP is the loop it appears in. */
419
420static bool
421is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
422{
423 /* The loop header is the only block we can trivially determine that
424 will always be executed. If the comparison is in the loop
425 header, we know it's OK to unswitch on it. */
426 if (gimple_bb (g: stmt) == loop->header)
427 return false;
428
429 auto_bitmap visited_ssa;
430 auto_vec<tree> worklist;
431 worklist.safe_push (obj: name);
432 bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
433 while (!worklist.is_empty ())
434 {
435 tree t = worklist.pop ();
436
437 /* If it's obviously undefined, avoid further computations. */
438 if (ssa_undefined_value_p (t, true))
439 return true;
440
441 if (ssa_defined_default_def_p (t))
442 continue;
443
444 gimple *def = SSA_NAME_DEF_STMT (t);
445
446 /* Check that all the PHI args are fully defined. */
447 if (gphi *phi = dyn_cast <gphi *> (p: def))
448 {
449 for (unsigned i = 0; i < gimple_phi_num_args (gs: phi); ++i)
450 {
451 tree t = gimple_phi_arg_def (gs: phi, index: i);
452 /* If an SSA has already been seen, it may be a loop,
453 but we can continue and ignore this use. Otherwise,
454 add the SSA_NAME to the queue and visit it later. */
455 if (TREE_CODE (t) == SSA_NAME
456 && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
457 worklist.safe_push (obj: t);
458 }
459 continue;
460 }
461
462 /* Uses in stmts always executed when the region header executes
463 are fine. */
464 if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (g: def)))
465 continue;
466
467 /* Handle calls and memory loads conservatively. */
468 if (!is_gimple_assign (gs: def)
469 || (gimple_assign_single_p (gs: def)
470 && gimple_vuse (g: def)))
471 return true;
472
473 /* Check that any SSA names used to define NAME are also fully
474 defined. */
475 use_operand_p use_p;
476 ssa_op_iter iter;
477 FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
478 {
479 tree t = USE_FROM_PTR (use_p);
480 /* If an SSA has already been seen, it may be a loop,
481 but we can continue and ignore this use. Otherwise,
482 add the SSA_NAME to the queue and visit it later. */
483 if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
484 worklist.safe_push (obj: t);
485 }
486 }
487 return false;
488}
489
490/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
491 basic blocks (for what it means see comments below).
492 All candidates all filled to the provided vector CANDIDATES.
493 OUTER_LOOP is updated to the innermost loop all found candidates are
494 invariant in. */
495
496static void
497find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
498 class loop *&outer_loop,
499 vec<unswitch_predicate *> &candidates,
500 unswitch_predicate *&hottest,
501 basic_block &hottest_bb)
502{
503 gimple *last, *def;
504 tree use;
505 basic_block def_bb;
506 ssa_op_iter iter;
507
508 /* BB must end in a simple conditional jump. */
509 last = *gsi_last_bb (bb);
510 if (!last)
511 return;
512
513 if (gcond *stmt = safe_dyn_cast <gcond *> (p: last))
514 {
515 /* To keep the things simple, we do not directly remove the conditions,
516 but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
517 loop where we would unswitch again on such a condition. */
518 if (gimple_cond_true_p (gs: stmt) || gimple_cond_false_p (gs: stmt))
519 return;
520
521 /* At least the LHS needs to be symbolic. */
522 if (TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME)
523 return;
524
525 /* Condition must be invariant. */
526 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
527 {
528 def = SSA_NAME_DEF_STMT (use);
529 def_bb = gimple_bb (g: def);
530 if (def_bb
531 && flow_bb_inside_loop_p (loop, def_bb))
532 return;
533 /* Unswitching on undefined values would introduce undefined
534 behavior that the original program might never exercise. */
535 if (is_maybe_undefined (name: use, stmt, loop))
536 return;
537 }
538 /* Narrow OUTER_LOOP. */
539 if (outer_loop != loop)
540 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
541 {
542 def = SSA_NAME_DEF_STMT (use);
543 def_bb = gimple_bb (g: def);
544 while (outer_loop != loop
545 && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb))
546 || is_maybe_undefined (name: use, stmt, loop: outer_loop)))
547 outer_loop = superloop_at_depth (loop,
548 loop_depth (loop: outer_loop) + 1);
549 }
550
551 unswitch_predicate *predicate = new unswitch_predicate (stmt);
552 candidates.safe_push (obj: predicate);
553 /* If we unswitch on this predicate we isolate both paths, so
554 pick the highest count for updating of the hottest predicate
555 to unswitch on first. */
556 if (!hottest || predicate->count > hottest->count)
557 {
558 hottest = predicate;
559 hottest_bb = bb;
560 }
561 }
562 else if (gswitch *stmt = safe_dyn_cast <gswitch *> (p: last))
563 {
564 unsigned nlabels = gimple_switch_num_labels (gs: stmt);
565 tree idx = gimple_switch_index (gs: stmt);
566 tree idx_type = TREE_TYPE (idx);
567 if (!gimple_range_ssa_p (exp: idx) || nlabels < 1)
568 return;
569 /* Index must be invariant. */
570 def = SSA_NAME_DEF_STMT (idx);
571 def_bb = gimple_bb (g: def);
572 if (def_bb
573 && flow_bb_inside_loop_p (loop, def_bb))
574 return;
575 /* Unswitching on undefined values would introduce undefined
576 behavior that the original program might never exercise. */
577 if (is_maybe_undefined (name: idx, stmt, loop))
578 return;
579 /* Narrow OUTER_LOOP. */
580 while (outer_loop != loop
581 && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb))
582 || is_maybe_undefined (name: idx, stmt, loop: outer_loop)))
583 outer_loop = superloop_at_depth (loop,
584 loop_depth (loop: outer_loop) + 1);
585
586 /* Build compound expression for all outgoing edges of the switch. */
587 auto_vec<tree, 16> preds;
588 auto_vec<int_range_max> edge_range;
589 preds.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), exact: true);
590 edge_range.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), exact: true);
591 edge e;
592 edge_iterator ei;
593 unsigned edge_index = 0;
594 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
595 e->aux = (void *)(uintptr_t)edge_index++;
596 for (unsigned i = 1; i < gimple_switch_num_labels (gs: stmt); ++i)
597 {
598 tree lab = gimple_switch_label (gs: stmt, index: i);
599 tree cmp;
600 int_range<2> lab_range;
601 tree low = fold_convert (idx_type, CASE_LOW (lab));
602 if (CASE_HIGH (lab) != NULL_TREE)
603 {
604 tree high = fold_convert (idx_type, CASE_HIGH (lab));
605 tree cmp1 = fold_build2 (GE_EXPR, boolean_type_node, idx, low);
606 tree cmp2 = fold_build2 (LE_EXPR, boolean_type_node, idx, high);
607 cmp = fold_build2 (BIT_AND_EXPR, boolean_type_node, cmp1, cmp2);
608 lab_range.set (type: idx_type, wi::to_wide (t: low), wi::to_wide (t: high));
609 }
610 else
611 {
612 cmp = fold_build2 (EQ_EXPR, boolean_type_node, idx, low);
613 wide_int w = wi::to_wide (t: low);
614 lab_range.set (type: idx_type, w, w);
615 }
616
617 /* Combine the expression with the existing one. */
618 basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
619 e = find_edge (gimple_bb (g: stmt), dest);
620 tree &expr = preds[(uintptr_t)e->aux];
621 if (expr == NULL_TREE)
622 expr = cmp;
623 else
624 expr = fold_build2 (BIT_IOR_EXPR, boolean_type_node, expr, cmp);
625 edge_range[(uintptr_t)e->aux].union_ (lab_range);
626 }
627
628 /* Now register the predicates. */
629 for (edge_index = 0; edge_index < preds.length (); ++edge_index)
630 {
631 edge e = EDGE_SUCC (gimple_bb (stmt), edge_index);
632 e->aux = NULL;
633 if (preds[edge_index] != NULL_TREE)
634 {
635 unswitch_predicate *predicate
636 = new unswitch_predicate (preds[edge_index], idx,
637 edge_index, e,
638 edge_range[edge_index]);
639 candidates.safe_push (obj: predicate);
640 if (!hottest || predicate->count > hottest->count)
641 {
642 hottest = predicate;
643 hottest_bb = bb;
644 }
645 }
646 }
647 }
648}
649
650/* Merge ranges for the last item of PREDICATE_PATH with a predicate
651 that shared the same LHS. */
652
653static void
654merge_last (predicate_vector &predicate_path)
655{
656 unswitch_predicate *last_predicate = predicate_path.last ().first;
657
658 for (int i = predicate_path.length () - 2; i >= 0; i--)
659 {
660 unswitch_predicate *predicate = predicate_path[i].first;
661 bool true_edge = predicate_path[i].second;
662
663 if (operand_equal_p (predicate->lhs, last_predicate->lhs, flags: 0))
664 {
665 irange &other = (true_edge ? predicate->merged_true_range
666 : predicate->merged_false_range);
667 last_predicate->merged_true_range.intersect (other);
668 last_predicate->merged_false_range.intersect (other);
669 return;
670 }
671 }
672}
673
674/* Add PREDICATE to PREDICATE_PATH on TRUE_EDGE. */
675
676static void
677add_predicate_to_path (predicate_vector &predicate_path,
678 unswitch_predicate *predicate, bool true_edge)
679{
680 predicate->copy_merged_ranges ();
681 predicate_path.safe_push (obj: std::make_pair (x&: predicate, y&: true_edge));
682 merge_last (predicate_path);
683}
684
685static bool
686find_range_for_lhs (predicate_vector &predicate_path, tree lhs,
687 int_range_max &range)
688{
689 for (int i = predicate_path.length () - 1; i >= 0; i--)
690 {
691 unswitch_predicate *predicate = predicate_path[i].first;
692 bool true_edge = predicate_path[i].second;
693
694 if (operand_equal_p (predicate->lhs, lhs, flags: 0))
695 {
696 range = (true_edge ? predicate->merged_true_range
697 : predicate->merged_false_range);
698 return !range.undefined_p ();
699 }
700 }
701
702 return false;
703}
704
705/* Simplifies STMT using the predicate we unswitched on which is the last
706 in PREDICATE_PATH. For switch statements add newly unreachable edges
707 to IGNORED_EDGES (but do not set IGNORED_EDGE_FLAG on them). */
708
709static tree
710evaluate_control_stmt_using_entry_checks (gimple *stmt,
711 predicate_vector &predicate_path,
712 int ignored_edge_flag,
713 hash_set<edge> *ignored_edges)
714{
715 unswitch_predicate *last_predicate = predicate_path.last ().first;
716 bool true_edge = predicate_path.last ().second;
717
718 if (gcond *cond = dyn_cast<gcond *> (p: stmt))
719 {
720 tree lhs = gimple_cond_lhs (gs: cond);
721 if (!operand_equal_p (lhs, last_predicate->lhs))
722 return NULL_TREE;
723 /* Try a symbolic match which works for floating point and fully
724 symbolic conditions. */
725 if (gimple_cond_code (gs: cond) == TREE_CODE (last_predicate->condition)
726 && operand_equal_p (gimple_cond_rhs (gs: cond),
727 TREE_OPERAND (last_predicate->condition, 1)))
728 return true_edge ? boolean_true_node : boolean_false_node;
729 /* Else try ranger if it supports LHS. */
730 else if (irange::supports_p (TREE_TYPE (lhs)))
731 {
732 int_range<2> r;
733 int_range_max path_range;
734
735 if (find_range_for_lhs (predicate_path, lhs, range&: path_range)
736 && fold_range (r, s: cond, r1&: path_range)
737 && r.singleton_p ())
738 return r.zero_p () ? boolean_false_node : boolean_true_node;
739 }
740 }
741 else if (gswitch *swtch = dyn_cast<gswitch *> (p: stmt))
742 {
743 unsigned nlabels = gimple_switch_num_labels (gs: swtch);
744
745 tree idx = gimple_switch_index (gs: swtch);
746
747 /* Already folded switch. */
748 if (TREE_CONSTANT (idx))
749 return NULL_TREE;
750
751 int_range_max path_range;
752 if (!find_range_for_lhs (predicate_path, lhs: idx, range&: path_range))
753 return NULL_TREE;
754
755 tree result = NULL_TREE;
756 edge single_edge = NULL;
757 for (unsigned i = 0; i < nlabels; ++i)
758 {
759 tree lab = gimple_switch_label (gs: swtch, index: i);
760 basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
761 edge e = find_edge (gimple_bb (g: stmt), dest);
762 if (e->flags & ignored_edge_flag)
763 continue;
764
765 int_range_max r;
766 if (!ranger->gori ().outgoing_edge_range_p (r, e, name: idx,
767 q&: *get_global_range_query ()))
768 continue;
769 r.intersect (path_range);
770 if (r.undefined_p ())
771 ignored_edges->add (k: e);
772 else
773 {
774 if (!single_edge)
775 {
776 single_edge = e;
777 result = CASE_LOW (lab);
778 }
779 else if (single_edge != e)
780 result = NULL;
781 }
782 }
783
784 /* Only one edge from the switch is alive. */
785 if (single_edge && result)
786 return result;
787 }
788
789 return NULL_TREE;
790}
791
792/* Simplify LOOP based on PREDICATE_PATH where dead edges are properly
793 marked. */
794
795static bool
796simplify_loop_version (class loop *loop, predicate_vector &predicate_path,
797 int ignored_edge_flag, bitmap handled)
798{
799 bool changed = false;
800 basic_block *bbs = get_loop_body (loop);
801
802 hash_set<edge> ignored_edges;
803 for (unsigned i = 0; i != loop->num_nodes; i++)
804 {
805 vec<unswitch_predicate *> &predicates = get_predicates_for_bb (bb: bbs[i]);
806 if (predicates.is_empty ())
807 continue;
808
809 gimple *stmt = *gsi_last_bb (bb: bbs[i]);
810 tree folded = evaluate_control_stmt_using_entry_checks (stmt,
811 predicate_path,
812 ignored_edge_flag,
813 ignored_edges: &ignored_edges);
814
815 if (gcond *cond = dyn_cast<gcond *> (p: stmt))
816 {
817 if (folded)
818 {
819 /* Remove path. */
820 if (integer_nonzerop (folded))
821 gimple_cond_set_condition_from_tree (cond, boolean_true_node);
822 else
823 gimple_cond_set_condition_from_tree (cond, boolean_false_node);
824
825 gcc_assert (predicates.length () == 1);
826 bitmap_set_bit (handled, predicates[0]->num);
827
828 update_stmt (s: cond);
829 changed = true;
830 }
831 }
832 else if (gswitch *swtch = dyn_cast<gswitch *> (p: stmt))
833 {
834 edge e;
835 edge_iterator ei;
836 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
837 if (ignored_edges.contains (k: e))
838 e->flags |= ignored_edge_flag;
839
840 for (unsigned j = 0; j < predicates.length (); j++)
841 {
842 edge e = EDGE_SUCC (bbs[i], predicates[j]->edge_index);
843 if (ignored_edges.contains (k: e))
844 bitmap_set_bit (handled, predicates[j]->num);
845 }
846
847 if (folded)
848 {
849 gimple_switch_set_index (gs: swtch, index: folded);
850 update_stmt (s: swtch);
851 changed = true;
852 }
853 }
854 }
855
856 free (ptr: bbs);
857 return changed;
858}
859
860/* Evaluate reachable blocks in LOOP and call VISIT on them, aborting the
861 DFS walk if VISIT returns true. When PREDICATE_PATH is specified then
862 take into account that when computing reachability, otherwise just
863 look at the simplified state and IGNORED_EDGE_FLAG. */
864
865template <typename VisitOp>
866static void
867evaluate_bbs (class loop *loop, predicate_vector *predicate_path,
868 int ignored_edge_flag, VisitOp visit)
869{
870 auto_bb_flag reachable_flag (cfun);
871 auto_vec<basic_block, 10> worklist (loop->num_nodes);
872 auto_vec<basic_block, 10> reachable (loop->num_nodes);
873 hash_set<edge> ignored_edges;
874
875 loop->header->flags |= reachable_flag;
876 worklist.quick_push (obj: loop->header);
877 reachable.safe_push (obj: loop->header);
878
879 while (!worklist.is_empty ())
880 {
881 edge e;
882 edge_iterator ei;
883 int flags = ignored_edge_flag;
884 basic_block bb = worklist.pop ();
885
886 if (visit (bb))
887 break;
888
889 gimple *last = *gsi_last_bb (bb);
890 if (gcond *cond = safe_dyn_cast <gcond *> (p: last))
891 {
892 if (gimple_cond_true_p (gs: cond))
893 flags = EDGE_FALSE_VALUE;
894 else if (gimple_cond_false_p (gs: cond))
895 flags = EDGE_TRUE_VALUE;
896 else if (predicate_path)
897 {
898 tree res;
899 if (!get_predicates_for_bb (bb).is_empty ()
900 && (res = evaluate_control_stmt_using_entry_checks
901 (stmt: cond, predicate_path&: *predicate_path, ignored_edge_flag,
902 ignored_edges: &ignored_edges)))
903 flags = (integer_nonzerop (res)
904 ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE);
905 }
906 }
907 else if (gswitch *swtch = safe_dyn_cast<gswitch *> (p: last))
908 if (predicate_path
909 && !get_predicates_for_bb (bb).is_empty ())
910 evaluate_control_stmt_using_entry_checks (stmt: swtch, predicate_path&: *predicate_path,
911 ignored_edge_flag,
912 ignored_edges: &ignored_edges);
913
914 /* Note that for the moment we do not account reachable conditions
915 which are simplified to take a known edge as zero size nor
916 are we accounting for the required addition of the versioning
917 condition. Those should cancel out conservatively. */
918
919 FOR_EACH_EDGE (e, ei, bb->succs)
920 {
921 basic_block dest = e->dest;
922
923 if (flow_bb_inside_loop_p (loop, dest)
924 && !(dest->flags & reachable_flag)
925 && !(e->flags & flags)
926 && !ignored_edges.contains (k: e))
927 {
928 dest->flags |= reachable_flag;
929 worklist.safe_push (obj: dest);
930 reachable.safe_push (obj: dest);
931 }
932 }
933 }
934
935 /* Clear the flag from basic blocks. */
936 while (!reachable.is_empty ())
937 reachable.pop ()->flags &= ~reachable_flag;
938}
939
940/* Evaluate how many instruction will we have if we unswitch LOOP (with BBS)
941 based on PREDICATE predicate (using PREDICATE_PATH). Store the
942 result in TRUE_SIZE and FALSE_SIZE. */
943
944static void
945evaluate_loop_insns_for_predicate (class loop *loop,
946 predicate_vector &predicate_path,
947 unswitch_predicate *predicate,
948 int ignored_edge_flag,
949 unsigned *true_size, unsigned *false_size)
950{
951 unsigned size = 0;
952 auto sum_size = [&](basic_block bb) -> bool
953 { size += (uintptr_t)bb->aux; return false; };
954
955 add_predicate_to_path (predicate_path, predicate, true_edge: true);
956 evaluate_bbs (loop, predicate_path: &predicate_path, ignored_edge_flag, visit: sum_size);
957 predicate_path.pop ();
958 unsigned true_loop_cost = size;
959
960 size = 0;
961 add_predicate_to_path (predicate_path, predicate, true_edge: false);
962 evaluate_bbs (loop, predicate_path: &predicate_path, ignored_edge_flag, visit: sum_size);
963 predicate_path.pop ();
964 unsigned false_loop_cost = size;
965
966 *true_size = true_loop_cost;
967 *false_size = false_loop_cost;
968}
969
970/* Unswitch single LOOP. PREDICATE_PATH contains so far used predicates
971 for unswitching. BUDGET is number of instruction for which we can increase
972 the loop and is updated when unswitching occurs. If HOTTEST is not
973 NULL then pick this candidate as the one to unswitch on. */
974
975static bool
976tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc,
977 predicate_vector &predicate_path,
978 unsigned loop_size, unsigned &budget,
979 int ignored_edge_flag, bitmap handled,
980 unswitch_predicate *hottest, basic_block hottest_bb)
981{
982 class loop *nloop;
983 bool changed = false;
984 unswitch_predicate *predicate = NULL;
985 basic_block predicate_bb = NULL;
986 unsigned true_size = 0, false_size = 0;
987
988 auto check_predicates = [&](basic_block bb) -> bool
989 {
990 for (auto pred : get_predicates_for_bb (bb))
991 {
992 if (bitmap_bit_p (handled, pred->num))
993 continue;
994
995 evaluate_loop_insns_for_predicate (loop, predicate_path,
996 predicate: pred, ignored_edge_flag,
997 true_size: &true_size, false_size: &false_size);
998
999 /* We'll get LOOP replaced with a simplified version according
1000 to PRED estimated to TRUE_SIZE and a copy simplified
1001 according to the inverted PRED estimated to FALSE_SIZE. */
1002 if (true_size + false_size < budget + loop_size)
1003 {
1004 predicate = pred;
1005 predicate_bb = bb;
1006
1007 /* There are cases where true_size and false_size add up to
1008 less than the original loop_size. We do not want to
1009 grow the remaining budget because of that. */
1010 if (true_size + false_size > loop_size)
1011 budget -= (true_size + false_size - loop_size);
1012
1013 /* FIXME: right now we select first candidate, but we can
1014 choose the cheapest or hottest one. */
1015 return true;
1016 }
1017 else if (dump_enabled_p ())
1018 dump_printf_loc (MSG_NOTE, loc,
1019 "not unswitching condition, cost too big "
1020 "(%u insns copied to %u and %u)\n", loop_size,
1021 true_size, false_size);
1022 }
1023 return false;
1024 };
1025
1026 if (hottest)
1027 {
1028 predicate = hottest;
1029 predicate_bb = hottest_bb;
1030 }
1031 else
1032 /* Check predicates of reachable blocks. */
1033 evaluate_bbs (loop, NULL, ignored_edge_flag, visit: check_predicates);
1034
1035 if (predicate != NULL)
1036 {
1037 if (!dbg_cnt (index: loop_unswitch))
1038 goto exit;
1039
1040 if (dump_enabled_p ())
1041 {
1042 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
1043 "unswitching %sloop %d on %qs with condition: %T\n",
1044 loop->inner ? "outer " : "",
1045 loop->num, predicate->switch_p ? "switch" : "if",
1046 predicate->condition);
1047 dump_printf_loc (MSG_NOTE, loc,
1048 "optimized sizes estimated to %u (true) "
1049 "and %u (false) from original size %u\n",
1050 true_size, false_size, loop_size);
1051 }
1052
1053 bitmap_set_bit (handled, predicate->num);
1054 initialize_original_copy_tables ();
1055 /* Unswitch the loop on this condition. */
1056 nloop = tree_unswitch_loop (loop, EDGE_SUCC (predicate_bb,
1057 predicate->edge_index),
1058 predicate->condition);
1059 if (!nloop)
1060 {
1061 free_original_copy_tables ();
1062 goto exit;
1063 }
1064
1065 /* Copy BB costs. */
1066 basic_block *bbs2 = get_loop_body (nloop);
1067 for (unsigned i = 0; i < nloop->num_nodes; i++)
1068 bbs2[i]->aux = get_bb_original (bbs2[i])->aux;
1069 free (ptr: bbs2);
1070
1071 free_original_copy_tables ();
1072
1073 /* Update the SSA form after unswitching. */
1074 update_ssa (TODO_update_ssa_no_phi);
1075
1076 /* Invoke itself on modified loops. */
1077 bitmap handled_copy = BITMAP_ALLOC (NULL);
1078 bitmap_copy (handled_copy, handled);
1079 add_predicate_to_path (predicate_path, predicate, true_edge: false);
1080 changed |= simplify_loop_version (loop: nloop, predicate_path,
1081 ignored_edge_flag, handled: handled_copy);
1082 tree_unswitch_single_loop (loop: nloop, loc, predicate_path,
1083 loop_size: false_size, budget,
1084 ignored_edge_flag, handled: handled_copy);
1085 predicate_path.pop ();
1086 BITMAP_FREE (handled_copy);
1087
1088 /* FIXME: After unwinding above we have to reset all ->handled
1089 flags as otherwise we fail to realize unswitching opportunities
1090 in the below recursion. See gcc.dg/loop-unswitch-16.c */
1091 add_predicate_to_path (predicate_path, predicate, true_edge: true);
1092 changed |= simplify_loop_version (loop, predicate_path,
1093 ignored_edge_flag, handled);
1094 tree_unswitch_single_loop (loop, loc, predicate_path,
1095 loop_size: true_size, budget,
1096 ignored_edge_flag, handled);
1097 predicate_path.pop ();
1098 changed = true;
1099 }
1100
1101exit:
1102 return changed;
1103}
1104
1105/* Unswitch a LOOP w.r. to given EDGE_TRUE. We only support unswitching of
1106 innermost loops. COND is the condition determining which loop is entered;
1107 the new loop is entered if COND is true. Returns NULL if impossible, new
1108 loop otherwise. */
1109
1110static class loop *
1111tree_unswitch_loop (class loop *loop, edge edge_true, tree cond)
1112{
1113 /* Some sanity checking. */
1114 gcc_assert (flow_bb_inside_loop_p (loop, edge_true->src));
1115 gcc_assert (EDGE_COUNT (edge_true->src->succs) >= 2);
1116
1117 profile_probability prob_true = edge_true->probability;
1118 return loop_version (loop, unshare_expr (cond),
1119 NULL, prob_true,
1120 prob_true.invert (),
1121 prob_true, prob_true.invert (),
1122 false);
1123}
1124
1125/* Unswitch outer loops by hoisting invariant guard on
1126 inner loop without code duplication. */
1127static bool
1128tree_unswitch_outer_loop (class loop *loop)
1129{
1130 edge exit, guard;
1131 HOST_WIDE_INT iterations;
1132
1133 gcc_assert (loop->inner);
1134 if (loop->inner->next)
1135 return false;
1136 /* Accept loops with single exit only which is not from inner loop. */
1137 exit = single_exit (loop);
1138 if (!exit || exit->src->loop_father != loop)
1139 return false;
1140 /* Check that phi argument of exit edge is not defined inside loop. */
1141 if (!check_exit_phi (loop))
1142 return false;
1143 /* If the loop is not expected to iterate, there is no need
1144 for unswitching. */
1145 iterations = estimated_loop_iterations_int (loop);
1146 if (iterations < 0)
1147 iterations = likely_max_loop_iterations_int (loop);
1148 if (iterations >= 0 && iterations <= 1)
1149 {
1150 if (dump_enabled_p ())
1151 dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop),
1152 "Not unswitching, loop is not expected"
1153 " to iterate\n");
1154 return false;
1155 }
1156
1157 bool changed = false;
1158 auto_vec<gimple *> dbg_to_reset;
1159 while ((guard = find_loop_guard (loop, dbg_to_reset)))
1160 {
1161 hoist_guard (loop, guard);
1162 for (gimple *debug_stmt : dbg_to_reset)
1163 {
1164 gimple_debug_bind_reset_value (dbg: debug_stmt);
1165 update_stmt (s: debug_stmt);
1166 }
1167 dbg_to_reset.truncate (size: 0);
1168 changed = true;
1169 }
1170 return changed;
1171}
1172
1173/* Checks if the body of the LOOP is within an invariant guard. If this
1174 is the case, returns the edge that jumps over the real body of the loop,
1175 otherwise returns NULL. */
1176
1177static edge
1178find_loop_guard (class loop *loop, vec<gimple *> &dbg_to_reset)
1179{
1180 basic_block header = loop->header;
1181 edge guard_edge, te, fe;
1182 basic_block *body = NULL;
1183 unsigned i;
1184 tree use;
1185 ssa_op_iter iter;
1186
1187 /* We check for the following situation:
1188
1189 while (1)
1190 {
1191 [header]]
1192 loop_phi_nodes;
1193 something1;
1194 if (cond1)
1195 body;
1196 nvar = phi(orig, bvar) ... for all variables changed in body;
1197 [guard_end]
1198 something2;
1199 if (cond2)
1200 break;
1201 something3;
1202 }
1203
1204 where:
1205
1206 1) cond1 is loop invariant
1207 2) If cond1 is false, then the loop is essentially empty; i.e.,
1208 a) nothing in something1, something2 and something3 has side
1209 effects
1210 b) anything defined in something1, something2 and something3
1211 is not used outside of the loop. */
1212
1213 gcond *cond;
1214 do
1215 {
1216 basic_block next = NULL;
1217 if (single_succ_p (bb: header))
1218 next = single_succ (bb: header);
1219 else
1220 {
1221 cond = safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb: header));
1222 if (! cond)
1223 return NULL;
1224 extract_true_false_edges_from_block (header, &te, &fe);
1225 /* Make sure to skip earlier hoisted guards that are left
1226 in place as if (true). */
1227 if (gimple_cond_true_p (gs: cond))
1228 next = te->dest;
1229 else if (gimple_cond_false_p (gs: cond))
1230 next = fe->dest;
1231 else
1232 break;
1233 }
1234 /* Never traverse a backedge. */
1235 if (header->loop_father->header == next)
1236 return NULL;
1237 header = next;
1238 }
1239 while (1);
1240 if (!flow_bb_inside_loop_p (loop, te->dest)
1241 || !flow_bb_inside_loop_p (loop, fe->dest))
1242 return NULL;
1243
1244 if (just_once_each_iteration_p (loop, te->dest)
1245 || (single_succ_p (bb: te->dest)
1246 && just_once_each_iteration_p (loop, single_succ (bb: te->dest))))
1247 {
1248 if (just_once_each_iteration_p (loop, fe->dest))
1249 return NULL;
1250 guard_edge = te;
1251 }
1252 else if (just_once_each_iteration_p (loop, fe->dest)
1253 || (single_succ_p (bb: fe->dest)
1254 && just_once_each_iteration_p (loop, single_succ (bb: fe->dest))))
1255 guard_edge = fe;
1256 else
1257 return NULL;
1258
1259 dump_user_location_t loc = find_loop_location (loop);
1260
1261 /* Guard edge must skip inner loop. */
1262 if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
1263 guard_edge == fe ? te->dest : fe->dest))
1264 {
1265 if (dump_enabled_p ())
1266 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1267 "Guard edge %d --> %d is not around the loop!\n",
1268 guard_edge->src->index, guard_edge->dest->index);
1269 return NULL;
1270 }
1271 if (guard_edge->dest == loop->latch)
1272 {
1273 if (dump_enabled_p ())
1274 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1275 "Guard edge destination is loop latch.\n");
1276 return NULL;
1277 }
1278
1279 if (dump_enabled_p ())
1280 dump_printf_loc (MSG_NOTE, loc,
1281 "Considering guard %d -> %d in loop %d\n",
1282 guard_edge->src->index, guard_edge->dest->index,
1283 loop->num);
1284 /* Check if condition operands do not have definitions inside loop since
1285 any bb copying is not performed. */
1286 FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
1287 {
1288 gimple *def = SSA_NAME_DEF_STMT (use);
1289 basic_block def_bb = gimple_bb (g: def);
1290 if (def_bb
1291 && flow_bb_inside_loop_p (loop, def_bb))
1292 {
1293 if (dump_enabled_p ())
1294 dump_printf_loc (MSG_NOTE, loc, "guard operands have definitions"
1295 " inside loop\n");
1296 return NULL;
1297 }
1298 }
1299
1300 body = get_loop_body (loop);
1301 for (i = 0; i < loop->num_nodes; i++)
1302 {
1303 basic_block bb = body[i];
1304 if (bb->loop_father != loop)
1305 continue;
1306 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1307 {
1308 if (dump_enabled_p ())
1309 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1310 "Block %d is marked as irreducible in loop\n",
1311 bb->index);
1312 guard_edge = NULL;
1313 goto end;
1314 }
1315 if (!empty_bb_without_guard_p (loop, bb, dbg_to_reset))
1316 {
1317 if (dump_enabled_p ())
1318 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1319 "Block %d has side effects\n", bb->index);
1320 guard_edge = NULL;
1321 goto end;
1322 }
1323 }
1324
1325 if (dump_enabled_p ())
1326 dump_printf_loc (MSG_NOTE, loc,
1327 "suitable to hoist\n");
1328end:
1329 if (body)
1330 free (ptr: body);
1331 return guard_edge;
1332}
1333
1334/* Returns true if
1335 1) no statement in BB has side effects
1336 2) assuming that edge GUARD is always taken, all definitions in BB
1337 are noy used outside of the loop.
1338 KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
1339 PROCESSED is a set of ssa names for that we already tested whether they
1340 are invariant or not. Uses in debug stmts outside of the loop are
1341 pushed to DBG_TO_RESET. */
1342
1343static bool
1344empty_bb_without_guard_p (class loop *loop, basic_block bb,
1345 vec<gimple *> &dbg_to_reset)
1346{
1347 basic_block exit_bb = single_exit (loop)->src;
1348 bool may_be_used_outside = (bb == exit_bb
1349 || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
1350 tree name;
1351 ssa_op_iter op_iter;
1352
1353 /* Phi nodes do not have side effects, but their results might be used
1354 outside of the loop. */
1355 if (may_be_used_outside)
1356 {
1357 for (gphi_iterator gsi = gsi_start_phis (bb);
1358 !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1359 {
1360 gphi *phi = gsi.phi ();
1361 name = PHI_RESULT (phi);
1362 if (virtual_operand_p (op: name))
1363 continue;
1364
1365 if (used_outside_loop_p (loop, name, dbg_to_reset))
1366 return false;
1367 }
1368 }
1369
1370 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1371 !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1372 {
1373 gimple *stmt = gsi_stmt (i: gsi);
1374 if (is_gimple_debug (gs: stmt))
1375 continue;
1376
1377 if (gimple_has_side_effects (stmt))
1378 return false;
1379
1380 if (gimple_vdef(g: stmt))
1381 return false;
1382
1383 FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
1384 {
1385 if (may_be_used_outside
1386 && used_outside_loop_p (loop, name, dbg_to_reset))
1387 return false;
1388 }
1389 }
1390 return true;
1391}
1392
1393/* Return true if NAME is used outside of LOOP. Pushes debug stmts that
1394 have such uses to DBG_TO_RESET but do not consider such uses. */
1395
1396static bool
1397used_outside_loop_p (class loop *loop, tree name, vec<gimple *> &dbg_to_reset)
1398{
1399 imm_use_iterator it;
1400 use_operand_p use;
1401
1402 FOR_EACH_IMM_USE_FAST (use, it, name)
1403 {
1404 gimple *stmt = USE_STMT (use);
1405 if (!flow_bb_inside_loop_p (loop, gimple_bb (g: stmt)))
1406 {
1407 if (!is_gimple_debug (gs: stmt))
1408 return true;
1409 dbg_to_reset.safe_push (obj: stmt);
1410 }
1411 }
1412
1413 return false;
1414}
1415
1416/* Return argument for loop preheader edge in header virtual phi if any. */
1417
1418static tree
1419get_vop_from_header (class loop *loop)
1420{
1421 for (gphi_iterator gsi = gsi_start_phis (loop->header);
1422 !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1423 {
1424 gphi *phi = gsi.phi ();
1425 if (!virtual_operand_p (op: gimple_phi_result (gs: phi)))
1426 continue;
1427 return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1428 }
1429 return NULL_TREE;
1430}
1431
1432/* Move the check of GUARD outside of LOOP. */
1433
1434static void
1435hoist_guard (class loop *loop, edge guard)
1436{
1437 edge exit = single_exit (loop);
1438 edge preh = loop_preheader_edge (loop);
1439 basic_block pre_header = preh->src;
1440 basic_block bb;
1441 edge te, fe, e, new_edge;
1442 gimple *stmt;
1443 basic_block guard_bb = guard->src;
1444 edge not_guard;
1445 gimple_stmt_iterator gsi;
1446 int flags = 0;
1447 bool fix_dom_of_exit;
1448 gcond *cond_stmt, *new_cond_stmt;
1449
1450 bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
1451 fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
1452 gsi = gsi_last_bb (bb: guard_bb);
1453 stmt = gsi_stmt (i: gsi);
1454 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
1455 cond_stmt = as_a <gcond *> (p: stmt);
1456 extract_true_false_edges_from_block (guard_bb, &te, &fe);
1457 /* Insert guard to PRE_HEADER. */
1458 gsi = gsi_last_bb (bb: pre_header);
1459 /* Create copy of COND_STMT. */
1460 new_cond_stmt = gimple_build_cond (gimple_cond_code (gs: cond_stmt),
1461 gimple_cond_lhs (gs: cond_stmt),
1462 gimple_cond_rhs (gs: 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. */
1466 if (guard == te)
1467 gimple_cond_make_false (gs: cond_stmt);
1468 else
1469 gimple_cond_make_true (gs: cond_stmt);
1470 update_stmt (s: cond_stmt);
1471 /* Create new loop pre-header. */
1472 e = split_block (pre_header, last_nondebug_stmt (pre_header));
1473
1474 dump_user_location_t loc = find_loop_location (loop);
1475
1476 if (dump_enabled_p ())
1477 {
1478 char buffer[64];
1479 guard->probability.dump (buffer);
1480
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);
1486 }
1487
1488 gcc_assert (loop_preheader_edge (loop)->src == e->dest);
1489
1490 if (guard == fe)
1491 {
1492 e->flags = EDGE_TRUE_VALUE;
1493 flags |= EDGE_FALSE_VALUE;
1494 not_guard = te;
1495 }
1496 else
1497 {
1498 e->flags = EDGE_FALSE_VALUE;
1499 flags |= EDGE_TRUE_VALUE;
1500 not_guard = fe;
1501 }
1502 new_edge = make_edge (pre_header, exit->dest, flags);
1503
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 (num: pre_header->count,
1509 den: guard->src->count)
1510 : guard->count ().apply_probability (prob: new_edge->probability);
1511
1512 if (skip_count > e->count ())
1513 {
1514 fprintf (stream: dump_file, format: " Capping count; expect profile inconsistency\n");
1515 skip_count = e->count ();
1516 }
1517 if (dump_enabled_p ())
1518 {
1519 char buffer[64];
1520 new_edge->probability.dump (buffer);
1521
1522 dump_printf_loc (MSG_NOTE, loc,
1523 "Estimated probability of skipping loop is %s\n",
1524 buffer);
1525 }
1526
1527 /* Update profile after the transform:
1528
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 ();
1533
1534 /* ... now update profile to represent that original guard will be optimized
1535 away ... */
1536 guard->probability = profile_probability::never ();
1537 not_guard->probability = profile_probability::always ();
1538
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);
1542
1543 for (unsigned int i = 0; i < loop->num_nodes; i++)
1544 {
1545 basic_block bb = body[i];
1546 if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
1547 {
1548 if (dump_enabled_p ())
1549 dump_printf_loc (MSG_NOTE, loc,
1550 "Scaling nonguarded BBs in loop: %i\n",
1551 bb->index);
1552 if (e->probability.initialized_p ())
1553 scale_bbs_frequencies (&bb, 1, e->probability);
1554 }
1555 }
1556
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. */
1560 bb = exit->dest;
1561 for (gphi_iterator gsi = gsi_start_phis (bb);
1562 !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1563 {
1564 gphi *phi = gsi.phi ();
1565 tree arg;
1566 if (virtual_operand_p (op: gimple_phi_result (gs: phi)))
1567 {
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);
1573 }
1574 else
1575 {
1576 /* Use exit edge argument. */
1577 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1578 add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
1579 }
1580 }
1581
1582 if (dump_enabled_p ())
1583 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
1584 "Guard hoisted\n");
1585
1586 free (ptr: body);
1587}
1588
1589/* Return true if phi argument for exit edge can be used
1590 for edge around loop. */
1591
1592static bool
1593check_exit_phi (class loop *loop)
1594{
1595 edge exit = single_exit (loop);
1596 basic_block pre_header = loop_preheader_edge (loop)->src;
1597
1598 for (gphi_iterator gsi = gsi_start_phis (exit->dest);
1599 !gsi_end_p (i: gsi); gsi_next (i: &gsi))
1600 {
1601 gphi *phi = gsi.phi ();
1602 tree arg;
1603 gimple *def;
1604 basic_block def_bb;
1605 if (virtual_operand_p (op: gimple_phi_result (gs: phi)))
1606 continue;
1607 arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1608 if (TREE_CODE (arg) != SSA_NAME)
1609 continue;
1610 def = SSA_NAME_DEF_STMT (arg);
1611 if (!def)
1612 continue;
1613 def_bb = gimple_bb (g: def);
1614 if (!def_bb)
1615 continue;
1616 if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
1617 /* Definition inside loop! */
1618 return false;
1619 /* Check loop closed phi invariant. */
1620 if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
1621 return false;
1622 }
1623 return true;
1624}
1625
1626/* Remove all dead cases from switches that are unswitched. */
1627
1628static void
1629clean_up_after_unswitching (int ignored_edge_flag)
1630{
1631 basic_block bb;
1632 edge e;
1633 edge_iterator ei;
1634 bool removed_edge = false;
1635
1636 FOR_EACH_BB_FN (bb, cfun)
1637 {
1638 gswitch *stmt= safe_dyn_cast <gswitch *> (p: *gsi_last_bb (bb));
1639 if (stmt && !CONSTANT_CLASS_P (gimple_switch_index (stmt)))
1640 {
1641 unsigned nlabels = gimple_switch_num_labels (gs: stmt);
1642 unsigned index = 1;
1643 tree lab = gimple_switch_default_label (gs: stmt);
1644 edge default_e = find_edge (gimple_bb (g: stmt),
1645 label_to_block (cfun, CASE_LABEL (lab)));
1646 for (unsigned i = 1; i < nlabels; ++i)
1647 {
1648 tree lab = gimple_switch_label (gs: stmt, index: i);
1649 basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
1650 edge e = find_edge (gimple_bb (g: stmt), dest);
1651 if (e == NULL)
1652 ; /* The edge is already removed. */
1653 else if (e->flags & ignored_edge_flag)
1654 {
1655 /* We may not remove the default label so we also have
1656 to preserve its edge. But we can remove the
1657 non-default CASE sharing the edge. */
1658 if (e != default_e)
1659 {
1660 remove_edge (e);
1661 removed_edge = true;
1662 }
1663 }
1664 else
1665 {
1666 gimple_switch_set_label (gs: stmt, index, label: lab);
1667 ++index;
1668 }
1669 }
1670
1671 if (index != nlabels)
1672 gimple_switch_set_num_labels (g: stmt, nlabels: index);
1673 }
1674
1675 /* Clean up the ignored_edge_flag from edges. */
1676 FOR_EACH_EDGE (e, ei, bb->succs)
1677 e->flags &= ~ignored_edge_flag;
1678 }
1679
1680 /* If we removed an edge we possibly have to recompute dominators. */
1681 if (removed_edge)
1682 free_dominance_info (CDI_DOMINATORS);
1683}
1684
1685/* Loop unswitching pass. */
1686
1687namespace {
1688
1689const pass_data pass_data_tree_unswitch =
1690{
1691 .type: GIMPLE_PASS, /* type */
1692 .name: "unswitch", /* name */
1693 .optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */
1694 .tv_id: TV_TREE_LOOP_UNSWITCH, /* tv_id */
1695 PROP_cfg, /* properties_required */
1696 .properties_provided: 0, /* properties_provided */
1697 .properties_destroyed: 0, /* properties_destroyed */
1698 .todo_flags_start: 0, /* todo_flags_start */
1699 .todo_flags_finish: 0, /* todo_flags_finish */
1700};
1701
1702class pass_tree_unswitch : public gimple_opt_pass
1703{
1704public:
1705 pass_tree_unswitch (gcc::context *ctxt)
1706 : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
1707 {}
1708
1709 /* opt_pass methods: */
1710 bool gate (function *) final override { return flag_unswitch_loops != 0; }
1711 unsigned int execute (function *) final override;
1712
1713}; // class pass_tree_unswitch
1714
1715unsigned int
1716pass_tree_unswitch::execute (function *fun)
1717{
1718 if (number_of_loops (fn: fun) <= 1)
1719 return 0;
1720
1721 return tree_ssa_unswitch_loops (fun);
1722}
1723
1724} // anon namespace
1725
1726gimple_opt_pass *
1727make_pass_tree_unswitch (gcc::context *ctxt)
1728{
1729 return new pass_tree_unswitch (ctxt);
1730}
1731
1732
1733

source code of gcc/tree-ssa-loop-unswitch.cc