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