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