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