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