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