1 /* Induction variable canonicalization and loop peeling.
2 Copyright (C) 2004-2022 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 /* This pass detects the loops that iterate a constant number of times,
21 adds a canonical induction variable (step -1, tested against 0)
22 and replaces the exit test. This enables the less powerful rtl
23 level analysis to use this information.
24
25 This might spoil the code in some cases (by increasing register pressure).
26 Note that in the case the new variable is not needed, ivopts will get rid
27 of it, so it might only be a problem when there are no other linear induction
28 variables. In that case the created optimization possibilities are likely
29 to pay up.
30
31 We also perform
32 - complete unrolling (or peeling) when the loops is rolling few enough
33 times
34 - simple peeling (i.e. copying few initial iterations prior the loop)
35 when number of iteration estimate is known (typically by the profile
36 info). */
37
38 #include "config.h"
39 #include "system.h"
40 #include "coretypes.h"
41 #include "backend.h"
42 #include "tree.h"
43 #include "gimple.h"
44 #include "cfghooks.h"
45 #include "tree-pass.h"
46 #include "ssa.h"
47 #include "cgraph.h"
48 #include "gimple-pretty-print.h"
49 #include "fold-const.h"
50 #include "profile.h"
51 #include "gimple-fold.h"
52 #include "tree-eh.h"
53 #include "gimple-iterator.h"
54 #include "tree-cfg.h"
55 #include "tree-ssa-loop-manip.h"
56 #include "tree-ssa-loop-niter.h"
57 #include "tree-ssa-loop.h"
58 #include "tree-into-ssa.h"
59 #include "cfgloop.h"
60 #include "tree-chrec.h"
61 #include "tree-scalar-evolution.h"
62 #include "tree-inline.h"
63 #include "tree-cfgcleanup.h"
64 #include "builtins.h"
65 #include "tree-ssa-sccvn.h"
66 #include "dbgcnt.h"
67
68 /* Specifies types of loops that may be unrolled. */
69
70 enum unroll_level
71 {
72 UL_SINGLE_ITER, /* Only loops that exit immediately in the first
73 iteration. */
74 UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
75 of code size. */
76 UL_ALL /* All suitable loops. */
77 };
78
79 /* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
80 is the exit edge whose condition is replaced. The ssa versions of the new
81 IV before and after increment will be stored in VAR_BEFORE and VAR_AFTER
82 if they are not NULL. */
83
84 void
create_canonical_iv(class loop * loop,edge exit,tree niter,tree * var_before=NULL,tree * var_after=NULL)85 create_canonical_iv (class loop *loop, edge exit, tree niter,
86 tree *var_before = NULL, tree *var_after = NULL)
87 {
88 edge in;
89 tree type, var;
90 gcond *cond;
91 gimple_stmt_iterator incr_at;
92 enum tree_code cmp;
93
94 if (dump_file && (dump_flags & TDF_DETAILS))
95 {
96 fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
97 print_generic_expr (dump_file, niter, TDF_SLIM);
98 fprintf (dump_file, " iterations.\n");
99 }
100
101 cond = as_a <gcond *> (last_stmt (exit->src));
102 in = EDGE_SUCC (exit->src, 0);
103 if (in == exit)
104 in = EDGE_SUCC (exit->src, 1);
105
106 /* Note that we do not need to worry about overflows, since
107 type of niter is always unsigned and all comparisons are
108 just for equality/nonequality -- i.e. everything works
109 with a modulo arithmetics. */
110
111 type = TREE_TYPE (niter);
112 niter = fold_build2 (PLUS_EXPR, type,
113 niter,
114 build_int_cst (type, 1));
115 incr_at = gsi_last_bb (in->src);
116 create_iv (niter,
117 build_int_cst (type, -1),
118 NULL_TREE, loop,
119 &incr_at, false, var_before, &var);
120 if (var_after)
121 *var_after = var;
122
123 cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
124 gimple_cond_set_code (cond, cmp);
125 gimple_cond_set_lhs (cond, var);
126 gimple_cond_set_rhs (cond, build_int_cst (type, 0));
127 update_stmt (cond);
128 }
129
130 /* Describe size of loop as detected by tree_estimate_loop_size. */
131 struct loop_size
132 {
133 /* Number of instructions in the loop. */
134 int overall;
135
136 /* Number of instructions that will be likely optimized out in
137 peeled iterations of loop (i.e. computation based on induction
138 variable where induction variable starts at known constant.) */
139 int eliminated_by_peeling;
140
141 /* Same statistics for last iteration of loop: it is smaller because
142 instructions after exit are not executed. */
143 int last_iteration;
144 int last_iteration_eliminated_by_peeling;
145
146 /* If some IV computation will become constant. */
147 bool constant_iv;
148
149 /* Number of call stmts that are not a builtin and are pure or const
150 present on the hot path. */
151 int num_pure_calls_on_hot_path;
152 /* Number of call stmts that are not a builtin and are not pure nor const
153 present on the hot path. */
154 int num_non_pure_calls_on_hot_path;
155 /* Number of statements other than calls in the loop. */
156 int non_call_stmts_on_hot_path;
157 /* Number of branches seen on the hot path. */
158 int num_branches_on_hot_path;
159 };
160
161 /* Return true if OP in STMT will be constant after peeling LOOP. */
162
163 static bool
constant_after_peeling(tree op,gimple * stmt,class loop * loop)164 constant_after_peeling (tree op, gimple *stmt, class loop *loop)
165 {
166 if (CONSTANT_CLASS_P (op))
167 return true;
168
169 /* We can still fold accesses to constant arrays when index is known. */
170 if (TREE_CODE (op) != SSA_NAME)
171 {
172 tree base = op;
173
174 /* First make fast look if we see constant array inside. */
175 while (handled_component_p (base))
176 base = TREE_OPERAND (base, 0);
177 if ((DECL_P (base)
178 && ctor_for_folding (base) != error_mark_node)
179 || CONSTANT_CLASS_P (base))
180 {
181 /* If so, see if we understand all the indices. */
182 base = op;
183 while (handled_component_p (base))
184 {
185 if (TREE_CODE (base) == ARRAY_REF
186 && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
187 return false;
188 base = TREE_OPERAND (base, 0);
189 }
190 return true;
191 }
192 return false;
193 }
194
195 /* Induction variables are constants when defined in loop. */
196 if (loop_containing_stmt (stmt) != loop)
197 return false;
198 tree ev = analyze_scalar_evolution (loop, op);
199 if (chrec_contains_undetermined (ev)
200 || chrec_contains_symbols (ev))
201 return false;
202 return true;
203 }
204
205 /* Computes an estimated number of insns in LOOP.
206 EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
207 iteration of the loop.
208 EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
209 of loop.
210 Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
211 Stop estimating after UPPER_BOUND is met. Return true in this case. */
212
213 static bool
tree_estimate_loop_size(class loop * loop,edge exit,edge edge_to_cancel,struct loop_size * size,int upper_bound)214 tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
215 struct loop_size *size, int upper_bound)
216 {
217 basic_block *body = get_loop_body (loop);
218 gimple_stmt_iterator gsi;
219 unsigned int i;
220 bool after_exit;
221 auto_vec<basic_block> path = get_loop_hot_path (loop);
222
223 size->overall = 0;
224 size->eliminated_by_peeling = 0;
225 size->last_iteration = 0;
226 size->last_iteration_eliminated_by_peeling = 0;
227 size->num_pure_calls_on_hot_path = 0;
228 size->num_non_pure_calls_on_hot_path = 0;
229 size->non_call_stmts_on_hot_path = 0;
230 size->num_branches_on_hot_path = 0;
231 size->constant_iv = 0;
232
233 if (dump_file && (dump_flags & TDF_DETAILS))
234 fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
235 for (i = 0; i < loop->num_nodes; i++)
236 {
237 if (edge_to_cancel && body[i] != edge_to_cancel->src
238 && dominated_by_p (CDI_DOMINATORS, body[i], edge_to_cancel->src))
239 after_exit = true;
240 else
241 after_exit = false;
242 if (dump_file && (dump_flags & TDF_DETAILS))
243 fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index,
244 after_exit);
245
246 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
247 {
248 gimple *stmt = gsi_stmt (gsi);
249 int num = estimate_num_insns (stmt, &eni_size_weights);
250 bool likely_eliminated = false;
251 bool likely_eliminated_last = false;
252 bool likely_eliminated_peeled = false;
253
254 if (dump_file && (dump_flags & TDF_DETAILS))
255 {
256 fprintf (dump_file, " size: %3i ", num);
257 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0);
258 }
259
260 /* Look for reasons why we might optimize this stmt away. */
261
262 if (!gimple_has_side_effects (stmt))
263 {
264 /* Exit conditional. */
265 if (exit && body[i] == exit->src
266 && stmt == last_stmt (exit->src))
267 {
268 if (dump_file && (dump_flags & TDF_DETAILS))
269 fprintf (dump_file, " Exit condition will be eliminated "
270 "in peeled copies.\n");
271 likely_eliminated_peeled = true;
272 }
273 if (edge_to_cancel && body[i] == edge_to_cancel->src
274 && stmt == last_stmt (edge_to_cancel->src))
275 {
276 if (dump_file && (dump_flags & TDF_DETAILS))
277 fprintf (dump_file, " Exit condition will be eliminated "
278 "in last copy.\n");
279 likely_eliminated_last = true;
280 }
281 /* Sets of IV variables */
282 if (gimple_code (stmt) == GIMPLE_ASSIGN
283 && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
284 {
285 if (dump_file && (dump_flags & TDF_DETAILS))
286 fprintf (dump_file, " Induction variable computation will"
287 " be folded away.\n");
288 likely_eliminated = true;
289 }
290 /* Assignments of IV variables. */
291 else if (gimple_code (stmt) == GIMPLE_ASSIGN
292 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
293 && constant_after_peeling (gimple_assign_rhs1 (stmt),
294 stmt, loop)
295 && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
296 || constant_after_peeling (gimple_assign_rhs2 (stmt),
297 stmt, loop))
298 && gimple_assign_rhs_class (stmt) != GIMPLE_TERNARY_RHS)
299 {
300 size->constant_iv = true;
301 if (dump_file && (dump_flags & TDF_DETAILS))
302 fprintf (dump_file,
303 " Constant expression will be folded away.\n");
304 likely_eliminated = true;
305 }
306 /* Conditionals. */
307 else if ((gimple_code (stmt) == GIMPLE_COND
308 && constant_after_peeling (gimple_cond_lhs (stmt), stmt,
309 loop)
310 && constant_after_peeling (gimple_cond_rhs (stmt), stmt,
311 loop)
312 /* We don't simplify all constant compares so make sure
313 they are not both constant already. See PR70288. */
314 && (! is_gimple_min_invariant (gimple_cond_lhs (stmt))
315 || ! is_gimple_min_invariant
316 (gimple_cond_rhs (stmt))))
317 || (gimple_code (stmt) == GIMPLE_SWITCH
318 && constant_after_peeling (gimple_switch_index (
319 as_a <gswitch *>
320 (stmt)),
321 stmt, loop)
322 && ! is_gimple_min_invariant
323 (gimple_switch_index
324 (as_a <gswitch *> (stmt)))))
325 {
326 if (dump_file && (dump_flags & TDF_DETAILS))
327 fprintf (dump_file, " Constant conditional.\n");
328 likely_eliminated = true;
329 }
330 }
331
332 size->overall += num;
333 if (likely_eliminated || likely_eliminated_peeled)
334 size->eliminated_by_peeling += num;
335 if (!after_exit)
336 {
337 size->last_iteration += num;
338 if (likely_eliminated || likely_eliminated_last)
339 size->last_iteration_eliminated_by_peeling += num;
340 }
341 if ((size->overall * 3 / 2 - size->eliminated_by_peeling
342 - size->last_iteration_eliminated_by_peeling) > upper_bound)
343 {
344 free (body);
345 return true;
346 }
347 }
348 }
349 while (path.length ())
350 {
351 basic_block bb = path.pop ();
352 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
353 {
354 gimple *stmt = gsi_stmt (gsi);
355 if (gimple_code (stmt) == GIMPLE_CALL
356 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt)))
357 {
358 int flags = gimple_call_flags (stmt);
359 if (flags & (ECF_PURE | ECF_CONST))
360 size->num_pure_calls_on_hot_path++;
361 else
362 size->num_non_pure_calls_on_hot_path++;
363 size->num_branches_on_hot_path ++;
364 }
365 /* Count inexpensive calls as non-calls, because they will likely
366 expand inline. */
367 else if (gimple_code (stmt) != GIMPLE_DEBUG)
368 size->non_call_stmts_on_hot_path++;
369 if (((gimple_code (stmt) == GIMPLE_COND
370 && (!constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
371 || !constant_after_peeling (gimple_cond_rhs (stmt), stmt,
372 loop)))
373 || (gimple_code (stmt) == GIMPLE_SWITCH
374 && !constant_after_peeling (gimple_switch_index (
375 as_a <gswitch *> (stmt)),
376 stmt, loop)))
377 && (!exit || bb != exit->src))
378 size->num_branches_on_hot_path++;
379 }
380 }
381
382 if (dump_file && (dump_flags & TDF_DETAILS))
383 fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
384 size->eliminated_by_peeling, size->last_iteration,
385 size->last_iteration_eliminated_by_peeling);
386
387 free (body);
388 return false;
389 }
390
391 /* Estimate number of insns of completely unrolled loop.
392 It is (NUNROLL + 1) * size of loop body with taking into account
393 the fact that in last copy everything after exit conditional
394 is dead and that some instructions will be eliminated after
395 peeling.
396
397 Loop body is likely going to simplify further, this is difficult
398 to guess, we just decrease the result by 1/3. */
399
400 static unsigned HOST_WIDE_INT
estimated_unrolled_size(struct loop_size * size,unsigned HOST_WIDE_INT nunroll)401 estimated_unrolled_size (struct loop_size *size,
402 unsigned HOST_WIDE_INT nunroll)
403 {
404 HOST_WIDE_INT unr_insns = ((nunroll)
405 * (HOST_WIDE_INT) (size->overall
406 - size->eliminated_by_peeling));
407 if (!nunroll)
408 unr_insns = 0;
409 unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
410
411 unr_insns = unr_insns * 2 / 3;
412 if (unr_insns <= 0)
413 unr_insns = 1;
414
415 return unr_insns;
416 }
417
418 /* Loop LOOP is known to not loop. See if there is an edge in the loop
419 body that can be remove to make the loop to always exit and at
420 the same time it does not make any code potentially executed
421 during the last iteration dead.
422
423 After complete unrolling we still may get rid of the conditional
424 on the exit in the last copy even if we have no idea what it does.
425 This is quite common case for loops of form
426
427 int a[5];
428 for (i=0;i<b;i++)
429 a[i]=0;
430
431 Here we prove the loop to iterate 5 times but we do not know
432 it from induction variable.
433
434 For now we handle only simple case where there is exit condition
435 just before the latch block and the latch block contains no statements
436 with side effect that may otherwise terminate the execution of loop
437 (such as by EH or by terminating the program or longjmp).
438
439 In the general case we may want to cancel the paths leading to statements
440 loop-niter identified as having undefined effect in the last iteration.
441 The other cases are hopefully rare and will be cleaned up later. */
442
443 static edge
loop_edge_to_cancel(class loop * loop)444 loop_edge_to_cancel (class loop *loop)
445 {
446 unsigned i;
447 edge edge_to_cancel;
448 gimple_stmt_iterator gsi;
449
450 /* We want only one predecestor of the loop. */
451 if (EDGE_COUNT (loop->latch->preds) > 1)
452 return NULL;
453
454 auto_vec<edge> exits = get_loop_exit_edges (loop);
455
456 FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
457 {
458 /* Find the other edge than the loop exit
459 leaving the conditoinal. */
460 if (EDGE_COUNT (edge_to_cancel->src->succs) != 2)
461 continue;
462 if (EDGE_SUCC (edge_to_cancel->src, 0) == edge_to_cancel)
463 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 1);
464 else
465 edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 0);
466
467 /* We only can handle conditionals. */
468 if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
469 continue;
470
471 /* We should never have conditionals in the loop latch. */
472 gcc_assert (edge_to_cancel->dest != loop->header);
473
474 /* Check that it leads to loop latch. */
475 if (edge_to_cancel->dest != loop->latch)
476 continue;
477
478 /* Verify that the code in loop latch does nothing that may end program
479 execution without really reaching the exit. This may include
480 non-pure/const function calls, EH statements, volatile ASMs etc. */
481 for (gsi = gsi_start_bb (loop->latch); !gsi_end_p (gsi); gsi_next (&gsi))
482 if (gimple_has_side_effects (gsi_stmt (gsi)))
483 return NULL;
484 return edge_to_cancel;
485 }
486 return NULL;
487 }
488
489 /* Remove all tests for exits that are known to be taken after LOOP was
490 peeled NPEELED times. Put gcc_unreachable before every statement
491 known to not be executed. */
492
493 static bool
remove_exits_and_undefined_stmts(class loop * loop,unsigned int npeeled)494 remove_exits_and_undefined_stmts (class loop *loop, unsigned int npeeled)
495 {
496 class nb_iter_bound *elt;
497 bool changed = false;
498
499 for (elt = loop->bounds; elt; elt = elt->next)
500 {
501 /* If statement is known to be undefined after peeling, turn it
502 into unreachable (or trap when debugging experience is supposed
503 to be good). */
504 if (!elt->is_exit
505 && wi::ltu_p (elt->bound, npeeled))
506 {
507 gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
508 gcall *stmt = gimple_build_call
509 (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
510 gimple_set_location (stmt, gimple_location (elt->stmt));
511 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
512 split_block (gimple_bb (stmt), stmt);
513 changed = true;
514 if (dump_file && (dump_flags & TDF_DETAILS))
515 {
516 fprintf (dump_file, "Forced statement unreachable: ");
517 print_gimple_stmt (dump_file, elt->stmt, 0);
518 }
519 }
520 /* If we know the exit will be taken after peeling, update. */
521 else if (elt->is_exit
522 && wi::leu_p (elt->bound, npeeled))
523 {
524 basic_block bb = gimple_bb (elt->stmt);
525 edge exit_edge = EDGE_SUCC (bb, 0);
526
527 if (dump_file && (dump_flags & TDF_DETAILS))
528 {
529 fprintf (dump_file, "Forced exit to be taken: ");
530 print_gimple_stmt (dump_file, elt->stmt, 0);
531 }
532 if (!loop_exit_edge_p (loop, exit_edge))
533 exit_edge = EDGE_SUCC (bb, 1);
534 exit_edge->probability = profile_probability::always ();
535 gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
536 gcond *cond_stmt = as_a <gcond *> (elt->stmt);
537 if (exit_edge->flags & EDGE_TRUE_VALUE)
538 gimple_cond_make_true (cond_stmt);
539 else
540 gimple_cond_make_false (cond_stmt);
541 update_stmt (cond_stmt);
542 changed = true;
543 }
544 }
545 return changed;
546 }
547
548 /* Remove all exits that are known to be never taken because of the loop bound
549 discovered. */
550
551 static bool
remove_redundant_iv_tests(class loop * loop)552 remove_redundant_iv_tests (class loop *loop)
553 {
554 class nb_iter_bound *elt;
555 bool changed = false;
556
557 if (!loop->any_upper_bound)
558 return false;
559 for (elt = loop->bounds; elt; elt = elt->next)
560 {
561 /* Exit is pointless if it won't be taken before loop reaches
562 upper bound. */
563 if (elt->is_exit && loop->any_upper_bound
564 && wi::ltu_p (loop->nb_iterations_upper_bound, elt->bound))
565 {
566 basic_block bb = gimple_bb (elt->stmt);
567 edge exit_edge = EDGE_SUCC (bb, 0);
568 class tree_niter_desc niter;
569
570 if (!loop_exit_edge_p (loop, exit_edge))
571 exit_edge = EDGE_SUCC (bb, 1);
572
573 /* Only when we know the actual number of iterations, not
574 just a bound, we can remove the exit. */
575 if (!number_of_iterations_exit (loop, exit_edge,
576 &niter, false, false)
577 || !integer_onep (niter.assumptions)
578 || !integer_zerop (niter.may_be_zero)
579 || !niter.niter
580 || TREE_CODE (niter.niter) != INTEGER_CST
581 || !wi::ltu_p (loop->nb_iterations_upper_bound,
582 wi::to_widest (niter.niter)))
583 continue;
584
585 if (dump_file && (dump_flags & TDF_DETAILS))
586 {
587 fprintf (dump_file, "Removed pointless exit: ");
588 print_gimple_stmt (dump_file, elt->stmt, 0);
589 }
590 gcond *cond_stmt = as_a <gcond *> (elt->stmt);
591 if (exit_edge->flags & EDGE_TRUE_VALUE)
592 gimple_cond_make_false (cond_stmt);
593 else
594 gimple_cond_make_true (cond_stmt);
595 update_stmt (cond_stmt);
596 changed = true;
597 }
598 }
599 return changed;
600 }
601
602 /* Stores loops that will be unlooped and edges that will be removed
603 after we process whole loop tree. */
604 static vec<loop_p> loops_to_unloop;
605 static vec<int> loops_to_unloop_nunroll;
606 static vec<edge> edges_to_remove;
607 /* Stores loops that has been peeled. */
608 static bitmap peeled_loops;
609
610 /* Cancel all fully unrolled loops by putting __builtin_unreachable
611 on the latch edge.
612 We do it after all unrolling since unlooping moves basic blocks
613 across loop boundaries trashing loop closed SSA form as well
614 as SCEV info needed to be intact during unrolling.
615
616 IRRED_INVALIDATED is used to bookkeep if information about
617 irreducible regions may become invalid as a result
618 of the transformation.
619 LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
620 when we need to go into loop closed SSA form. */
621
622 static void
unloop_loops(bitmap loop_closed_ssa_invalidated,bool * irred_invalidated)623 unloop_loops (bitmap loop_closed_ssa_invalidated,
624 bool *irred_invalidated)
625 {
626 while (loops_to_unloop.length ())
627 {
628 class loop *loop = loops_to_unloop.pop ();
629 int n_unroll = loops_to_unloop_nunroll.pop ();
630 basic_block latch = loop->latch;
631 edge latch_edge = loop_latch_edge (loop);
632 int flags = latch_edge->flags;
633 location_t locus = latch_edge->goto_locus;
634 gcall *stmt;
635 gimple_stmt_iterator gsi;
636
637 remove_exits_and_undefined_stmts (loop, n_unroll);
638
639 /* Unloop destroys the latch edge. */
640 unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
641
642 /* Create new basic block for the latch edge destination and wire
643 it in. */
644 stmt = gimple_build_call (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
645 latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch), flags);
646 latch_edge->probability = profile_probability::never ();
647 latch_edge->flags |= flags;
648 latch_edge->goto_locus = locus;
649
650 add_bb_to_loop (latch_edge->dest, current_loops->tree_root);
651 latch_edge->dest->count = profile_count::zero ();
652 set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest, latch_edge->src);
653
654 gsi = gsi_start_bb (latch_edge->dest);
655 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
656 }
657 loops_to_unloop.release ();
658 loops_to_unloop_nunroll.release ();
659
660 /* Remove edges in peeled copies. Given remove_path removes dominated
661 regions we need to cope with removal of already removed paths. */
662 unsigned i;
663 edge e;
664 auto_vec<int, 20> src_bbs;
665 src_bbs.reserve_exact (edges_to_remove.length ());
666 FOR_EACH_VEC_ELT (edges_to_remove, i, e)
667 src_bbs.quick_push (e->src->index);
668 FOR_EACH_VEC_ELT (edges_to_remove, i, e)
669 if (BASIC_BLOCK_FOR_FN (cfun, src_bbs[i]))
670 {
671 bool ok = remove_path (e, irred_invalidated,
672 loop_closed_ssa_invalidated);
673 gcc_assert (ok);
674 }
675 edges_to_remove.release ();
676 }
677
678 /* Tries to unroll LOOP completely, i.e. NITER times.
679 UL determines which loops we are allowed to unroll.
680 EXIT is the exit of the loop that should be eliminated.
681 MAXITER specfy bound on number of iterations, -1 if it is
682 not known or too large for HOST_WIDE_INT. The location
683 LOCUS corresponding to the loop is used when emitting
684 a summary of the unroll to the dump file. */
685
686 static bool
try_unroll_loop_completely(class loop * loop,edge exit,tree niter,bool may_be_zero,enum unroll_level ul,HOST_WIDE_INT maxiter,dump_user_location_t locus,bool allow_peel)687 try_unroll_loop_completely (class loop *loop,
688 edge exit, tree niter, bool may_be_zero,
689 enum unroll_level ul,
690 HOST_WIDE_INT maxiter,
691 dump_user_location_t locus, bool allow_peel)
692 {
693 unsigned HOST_WIDE_INT n_unroll = 0;
694 bool n_unroll_found = false;
695 edge edge_to_cancel = NULL;
696
697 /* See if we proved number of iterations to be low constant.
698
699 EXIT is an edge that will be removed in all but last iteration of
700 the loop.
701
702 EDGE_TO_CACNEL is an edge that will be removed from the last iteration
703 of the unrolled sequence and is expected to make the final loop not
704 rolling.
705
706 If the number of execution of loop is determined by standard induction
707 variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
708 from the iv test. */
709 if (tree_fits_uhwi_p (niter))
710 {
711 n_unroll = tree_to_uhwi (niter);
712 n_unroll_found = true;
713 edge_to_cancel = EDGE_SUCC (exit->src, 0);
714 if (edge_to_cancel == exit)
715 edge_to_cancel = EDGE_SUCC (exit->src, 1);
716 }
717 /* We do not know the number of iterations and thus we cannot eliminate
718 the EXIT edge. */
719 else
720 exit = NULL;
721
722 /* See if we can improve our estimate by using recorded loop bounds. */
723 if ((maxiter == 0 || ul != UL_SINGLE_ITER)
724 && maxiter >= 0
725 && (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
726 {
727 n_unroll = maxiter;
728 n_unroll_found = true;
729 /* Loop terminates before the IV variable test, so we cannot
730 remove it in the last iteration. */
731 edge_to_cancel = NULL;
732 /* If we do not allow peeling and we iterate just allow cases
733 that do not grow code. */
734 if (!allow_peel && maxiter != 0)
735 ul = UL_NO_GROWTH;
736 }
737
738 if (!n_unroll_found)
739 return false;
740
741 if (!loop->unroll
742 && n_unroll > (unsigned) param_max_completely_peel_times)
743 {
744 if (dump_file && (dump_flags & TDF_DETAILS))
745 fprintf (dump_file, "Not unrolling loop %d "
746 "(--param max-completely-peel-times limit reached).\n",
747 loop->num);
748 return false;
749 }
750
751 if (!edge_to_cancel)
752 edge_to_cancel = loop_edge_to_cancel (loop);
753
754 if (n_unroll)
755 {
756 if (ul == UL_SINGLE_ITER)
757 return false;
758
759 if (loop->unroll)
760 {
761 /* If the unrolling factor is too large, bail out. */
762 if (n_unroll > (unsigned)loop->unroll)
763 {
764 if (dump_file && (dump_flags & TDF_DETAILS))
765 fprintf (dump_file,
766 "Not unrolling loop %d: "
767 "user didn't want it unrolled completely.\n",
768 loop->num);
769 return false;
770 }
771 }
772 else
773 {
774 struct loop_size size;
775 /* EXIT can be removed only if we are sure it passes first N_UNROLL
776 iterations. */
777 bool remove_exit = (exit && niter
778 && TREE_CODE (niter) == INTEGER_CST
779 && wi::leu_p (n_unroll, wi::to_widest (niter)));
780 bool large
781 = tree_estimate_loop_size
782 (loop, remove_exit ? exit : NULL, edge_to_cancel, &size,
783 param_max_completely_peeled_insns);
784 if (large)
785 {
786 if (dump_file && (dump_flags & TDF_DETAILS))
787 fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
788 loop->num);
789 return false;
790 }
791
792 unsigned HOST_WIDE_INT ninsns = size.overall;
793 unsigned HOST_WIDE_INT unr_insns
794 = estimated_unrolled_size (&size, n_unroll);
795 if (dump_file && (dump_flags & TDF_DETAILS))
796 {
797 fprintf (dump_file, " Loop size: %d\n", (int) ninsns);
798 fprintf (dump_file, " Estimated size after unrolling: %d\n",
799 (int) unr_insns);
800 }
801
802 /* If the code is going to shrink, we don't need to be extra
803 cautious on guessing if the unrolling is going to be
804 profitable. */
805 if (unr_insns
806 /* If there is IV variable that will become constant, we
807 save one instruction in the loop prologue we do not
808 account otherwise. */
809 <= ninsns + (size.constant_iv != false))
810 ;
811 /* We unroll only inner loops, because we do not consider it
812 profitable otheriwse. We still can cancel loopback edge
813 of not rolling loop; this is always a good idea. */
814 else if (ul == UL_NO_GROWTH)
815 {
816 if (dump_file && (dump_flags & TDF_DETAILS))
817 fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
818 loop->num);
819 return false;
820 }
821 /* Outer loops tend to be less interesting candidates for
822 complete unrolling unless we can do a lot of propagation
823 into the inner loop body. For now we disable outer loop
824 unrolling when the code would grow. */
825 else if (loop->inner)
826 {
827 if (dump_file && (dump_flags & TDF_DETAILS))
828 fprintf (dump_file, "Not unrolling loop %d: "
829 "it is not innermost and code would grow.\n",
830 loop->num);
831 return false;
832 }
833 /* If there is call on a hot path through the loop, then
834 there is most probably not much to optimize. */
835 else if (size.num_non_pure_calls_on_hot_path)
836 {
837 if (dump_file && (dump_flags & TDF_DETAILS))
838 fprintf (dump_file, "Not unrolling loop %d: "
839 "contains call and code would grow.\n",
840 loop->num);
841 return false;
842 }
843 /* If there is pure/const call in the function, then we can
844 still optimize the unrolled loop body if it contains some
845 other interesting code than the calls and code storing or
846 cumulating the return value. */
847 else if (size.num_pure_calls_on_hot_path
848 /* One IV increment, one test, one ivtmp store and
849 one useful stmt. That is about minimal loop
850 doing pure call. */
851 && (size.non_call_stmts_on_hot_path
852 <= 3 + size.num_pure_calls_on_hot_path))
853 {
854 if (dump_file && (dump_flags & TDF_DETAILS))
855 fprintf (dump_file, "Not unrolling loop %d: "
856 "contains just pure calls and code would grow.\n",
857 loop->num);
858 return false;
859 }
860 /* Complete unrolling is major win when control flow is
861 removed and one big basic block is created. If the loop
862 contains control flow the optimization may still be a win
863 because of eliminating the loop overhead but it also may
864 blow the branch predictor tables. Limit number of
865 branches on the hot path through the peeled sequence. */
866 else if (size.num_branches_on_hot_path * (int)n_unroll
867 > param_max_peel_branches)
868 {
869 if (dump_file && (dump_flags & TDF_DETAILS))
870 fprintf (dump_file, "Not unrolling loop %d: "
871 "number of branches on hot path in the unrolled "
872 "sequence reaches --param max-peel-branches limit.\n",
873 loop->num);
874 return false;
875 }
876 else if (unr_insns
877 > (unsigned) param_max_completely_peeled_insns)
878 {
879 if (dump_file && (dump_flags & TDF_DETAILS))
880 fprintf (dump_file, "Not unrolling loop %d: "
881 "number of insns in the unrolled sequence reaches "
882 "--param max-completely-peeled-insns limit.\n",
883 loop->num);
884 return false;
885 }
886 }
887
888 if (!dbg_cnt (gimple_unroll))
889 return false;
890
891 initialize_original_copy_tables ();
892 auto_sbitmap wont_exit (n_unroll + 1);
893 if (exit && niter
894 && TREE_CODE (niter) == INTEGER_CST
895 && wi::leu_p (n_unroll, wi::to_widest (niter)))
896 {
897 bitmap_ones (wont_exit);
898 if (wi::eq_p (wi::to_widest (niter), n_unroll)
899 || edge_to_cancel)
900 bitmap_clear_bit (wont_exit, 0);
901 }
902 else
903 {
904 exit = NULL;
905 bitmap_clear (wont_exit);
906 }
907 if (may_be_zero)
908 bitmap_clear_bit (wont_exit, 1);
909
910 if (!gimple_duplicate_loop_body_to_header_edge (
911 loop, loop_preheader_edge (loop), n_unroll, wont_exit, exit,
912 &edges_to_remove,
913 DLTHE_FLAG_UPDATE_FREQ | DLTHE_FLAG_COMPLETTE_PEEL))
914 {
915 free_original_copy_tables ();
916 if (dump_file && (dump_flags & TDF_DETAILS))
917 fprintf (dump_file, "Failed to duplicate the loop\n");
918 return false;
919 }
920
921 free_original_copy_tables ();
922 }
923
924 /* Remove the conditional from the last copy of the loop. */
925 if (edge_to_cancel)
926 {
927 gcond *cond = as_a <gcond *> (last_stmt (edge_to_cancel->src));
928 force_edge_cold (edge_to_cancel, true);
929 if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
930 gimple_cond_make_false (cond);
931 else
932 gimple_cond_make_true (cond);
933 update_stmt (cond);
934 /* Do not remove the path, as doing so may remove outer loop and
935 confuse bookkeeping code in tree_unroll_loops_completely. */
936 }
937
938 /* Store the loop for later unlooping and exit removal. */
939 loops_to_unloop.safe_push (loop);
940 loops_to_unloop_nunroll.safe_push (n_unroll);
941
942 if (dump_enabled_p ())
943 {
944 if (!n_unroll)
945 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
946 "loop turned into non-loop; it never loops\n");
947 else
948 {
949 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
950 "loop with %d iterations completely unrolled",
951 (int) n_unroll);
952 if (loop->header->count.initialized_p ())
953 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
954 " (header execution count %d)",
955 (int)loop->header->count.to_gcov_type ());
956 dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
957 }
958 }
959
960 if (dump_file && (dump_flags & TDF_DETAILS))
961 {
962 if (exit)
963 fprintf (dump_file, "Exit condition of peeled iterations was "
964 "eliminated.\n");
965 if (edge_to_cancel)
966 fprintf (dump_file, "Last iteration exit edge was proved true.\n");
967 else
968 fprintf (dump_file, "Latch of last iteration was marked by "
969 "__builtin_unreachable ().\n");
970 }
971
972 return true;
973 }
974
975 /* Return number of instructions after peeling. */
976 static unsigned HOST_WIDE_INT
estimated_peeled_sequence_size(struct loop_size * size,unsigned HOST_WIDE_INT npeel)977 estimated_peeled_sequence_size (struct loop_size *size,
978 unsigned HOST_WIDE_INT npeel)
979 {
980 return MAX (npeel * (HOST_WIDE_INT) (size->overall
981 - size->eliminated_by_peeling), 1);
982 }
983
984 /* If the loop is expected to iterate N times and is
985 small enough, duplicate the loop body N+1 times before
986 the loop itself. This way the hot path will never
987 enter the loop.
988 Parameters are the same as for try_unroll_loops_completely */
989
990 static bool
try_peel_loop(class loop * loop,edge exit,tree niter,bool may_be_zero,HOST_WIDE_INT maxiter)991 try_peel_loop (class loop *loop,
992 edge exit, tree niter, bool may_be_zero,
993 HOST_WIDE_INT maxiter)
994 {
995 HOST_WIDE_INT npeel;
996 struct loop_size size;
997 int peeled_size;
998
999 if (!flag_peel_loops
1000 || param_max_peel_times <= 0
1001 || !peeled_loops)
1002 return false;
1003
1004 if (bitmap_bit_p (peeled_loops, loop->num))
1005 {
1006 if (dump_file)
1007 fprintf (dump_file, "Not peeling: loop is already peeled\n");
1008 return false;
1009 }
1010
1011 /* We don't peel loops that will be unrolled as this can duplicate a
1012 loop more times than the user requested. */
1013 if (loop->unroll)
1014 {
1015 if (dump_file)
1016 fprintf (dump_file, "Not peeling: user didn't want it peeled.\n");
1017 return false;
1018 }
1019
1020 /* Peel only innermost loops.
1021 While the code is perfectly capable of peeling non-innermost loops,
1022 the heuristics would probably need some improvements. */
1023 if (loop->inner)
1024 {
1025 if (dump_file)
1026 fprintf (dump_file, "Not peeling: outer loop\n");
1027 return false;
1028 }
1029
1030 if (!optimize_loop_for_speed_p (loop))
1031 {
1032 if (dump_file)
1033 fprintf (dump_file, "Not peeling: cold loop\n");
1034 return false;
1035 }
1036
1037 /* Check if there is an estimate on the number of iterations. */
1038 npeel = estimated_loop_iterations_int (loop);
1039 if (npeel < 0)
1040 npeel = likely_max_loop_iterations_int (loop);
1041 if (npeel < 0)
1042 {
1043 if (dump_file)
1044 fprintf (dump_file, "Not peeling: number of iterations is not "
1045 "estimated\n");
1046 return false;
1047 }
1048 if (maxiter >= 0 && maxiter <= npeel)
1049 {
1050 if (dump_file)
1051 fprintf (dump_file, "Not peeling: upper bound is known so can "
1052 "unroll completely\n");
1053 return false;
1054 }
1055
1056 /* We want to peel estimated number of iterations + 1 (so we never
1057 enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1058 and be sure to avoid overflows. */
1059 if (npeel > param_max_peel_times - 1)
1060 {
1061 if (dump_file)
1062 fprintf (dump_file, "Not peeling: rolls too much "
1063 "(%i + 1 > --param max-peel-times)\n", (int) npeel);
1064 return false;
1065 }
1066 npeel++;
1067
1068 /* Check peeled loops size. */
1069 tree_estimate_loop_size (loop, exit, NULL, &size,
1070 param_max_peeled_insns);
1071 if ((peeled_size = estimated_peeled_sequence_size (&size, (int) npeel))
1072 > param_max_peeled_insns)
1073 {
1074 if (dump_file)
1075 fprintf (dump_file, "Not peeling: peeled sequence size is too large "
1076 "(%i insns > --param max-peel-insns)", peeled_size);
1077 return false;
1078 }
1079
1080 if (!dbg_cnt (gimple_unroll))
1081 return false;
1082
1083 /* Duplicate possibly eliminating the exits. */
1084 initialize_original_copy_tables ();
1085 auto_sbitmap wont_exit (npeel + 1);
1086 if (exit && niter
1087 && TREE_CODE (niter) == INTEGER_CST
1088 && wi::leu_p (npeel, wi::to_widest (niter)))
1089 {
1090 bitmap_ones (wont_exit);
1091 bitmap_clear_bit (wont_exit, 0);
1092 }
1093 else
1094 {
1095 exit = NULL;
1096 bitmap_clear (wont_exit);
1097 }
1098 if (may_be_zero)
1099 bitmap_clear_bit (wont_exit, 1);
1100 if (!gimple_duplicate_loop_body_to_header_edge (
1101 loop, loop_preheader_edge (loop), npeel, wont_exit, exit,
1102 &edges_to_remove, DLTHE_FLAG_UPDATE_FREQ))
1103 {
1104 free_original_copy_tables ();
1105 return false;
1106 }
1107 free_original_copy_tables ();
1108 if (dump_file && (dump_flags & TDF_DETAILS))
1109 {
1110 fprintf (dump_file, "Peeled loop %d, %i times.\n",
1111 loop->num, (int) npeel);
1112 }
1113 if (loop->any_estimate)
1114 {
1115 if (wi::ltu_p (npeel, loop->nb_iterations_estimate))
1116 loop->nb_iterations_estimate -= npeel;
1117 else
1118 loop->nb_iterations_estimate = 0;
1119 }
1120 if (loop->any_upper_bound)
1121 {
1122 if (wi::ltu_p (npeel, loop->nb_iterations_upper_bound))
1123 loop->nb_iterations_upper_bound -= npeel;
1124 else
1125 loop->nb_iterations_upper_bound = 0;
1126 }
1127 if (loop->any_likely_upper_bound)
1128 {
1129 if (wi::ltu_p (npeel, loop->nb_iterations_likely_upper_bound))
1130 loop->nb_iterations_likely_upper_bound -= npeel;
1131 else
1132 {
1133 loop->any_estimate = true;
1134 loop->nb_iterations_estimate = 0;
1135 loop->nb_iterations_likely_upper_bound = 0;
1136 }
1137 }
1138 profile_count entry_count = profile_count::zero ();
1139
1140 edge e;
1141 edge_iterator ei;
1142 FOR_EACH_EDGE (e, ei, loop->header->preds)
1143 if (e->src != loop->latch)
1144 {
1145 if (e->src->count.initialized_p ())
1146 entry_count += e->src->count;
1147 gcc_assert (!flow_bb_inside_loop_p (loop, e->src));
1148 }
1149 profile_probability p;
1150 p = entry_count.probability_in (loop->header->count);
1151 scale_loop_profile (loop, p, 0);
1152 bitmap_set_bit (peeled_loops, loop->num);
1153 return true;
1154 }
1155 /* Adds a canonical induction variable to LOOP if suitable.
1156 CREATE_IV is true if we may create a new iv. UL determines
1157 which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1158 to determine the number of iterations of a loop by direct evaluation.
1159 Returns true if cfg is changed. */
1160
1161 static bool
canonicalize_loop_induction_variables(class loop * loop,bool create_iv,enum unroll_level ul,bool try_eval,bool allow_peel)1162 canonicalize_loop_induction_variables (class loop *loop,
1163 bool create_iv, enum unroll_level ul,
1164 bool try_eval, bool allow_peel)
1165 {
1166 edge exit = NULL;
1167 tree niter;
1168 HOST_WIDE_INT maxiter;
1169 bool modified = false;
1170 dump_user_location_t locus;
1171 class tree_niter_desc niter_desc;
1172 bool may_be_zero = false;
1173
1174 /* For unrolling allow conditional constant or zero iterations, thus
1175 perform loop-header copying on-the-fly. */
1176 exit = single_exit (loop);
1177 niter = chrec_dont_know;
1178 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
1179 {
1180 niter = niter_desc.niter;
1181 may_be_zero
1182 = niter_desc.may_be_zero && !integer_zerop (niter_desc.may_be_zero);
1183 }
1184 if (TREE_CODE (niter) == INTEGER_CST)
1185 locus = last_stmt (exit->src);
1186 else
1187 {
1188 /* For non-constant niter fold may_be_zero into niter again. */
1189 if (may_be_zero)
1190 {
1191 if (COMPARISON_CLASS_P (niter_desc.may_be_zero))
1192 niter = fold_build3 (COND_EXPR, TREE_TYPE (niter),
1193 niter_desc.may_be_zero,
1194 build_int_cst (TREE_TYPE (niter), 0), niter);
1195 else
1196 niter = chrec_dont_know;
1197 may_be_zero = false;
1198 }
1199
1200 /* If the loop has more than one exit, try checking all of them
1201 for # of iterations determinable through scev. */
1202 if (!exit)
1203 niter = find_loop_niter (loop, &exit);
1204
1205 /* Finally if everything else fails, try brute force evaluation. */
1206 if (try_eval
1207 && (chrec_contains_undetermined (niter)
1208 || TREE_CODE (niter) != INTEGER_CST))
1209 niter = find_loop_niter_by_eval (loop, &exit);
1210
1211 if (exit)
1212 locus = last_stmt (exit->src);
1213
1214 if (TREE_CODE (niter) != INTEGER_CST)
1215 exit = NULL;
1216 }
1217
1218 /* We work exceptionally hard here to estimate the bound
1219 by find_loop_niter_by_eval. Be sure to keep it for future. */
1220 if (niter && TREE_CODE (niter) == INTEGER_CST)
1221 {
1222 auto_vec<edge> exits = get_loop_exit_edges (loop);
1223 record_niter_bound (loop, wi::to_widest (niter),
1224 exit == single_likely_exit (loop, exits), true);
1225 }
1226
1227 /* Force re-computation of loop bounds so we can remove redundant exits. */
1228 maxiter = max_loop_iterations_int (loop);
1229
1230 if (dump_file && (dump_flags & TDF_DETAILS)
1231 && TREE_CODE (niter) == INTEGER_CST)
1232 {
1233 fprintf (dump_file, "Loop %d iterates ", loop->num);
1234 print_generic_expr (dump_file, niter, TDF_SLIM);
1235 fprintf (dump_file, " times.\n");
1236 }
1237 if (dump_file && (dump_flags & TDF_DETAILS)
1238 && maxiter >= 0)
1239 {
1240 fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
1241 (int)maxiter);
1242 }
1243 if (dump_file && (dump_flags & TDF_DETAILS)
1244 && likely_max_loop_iterations_int (loop) >= 0)
1245 {
1246 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1247 loop->num, (int)likely_max_loop_iterations_int (loop));
1248 }
1249
1250 /* Remove exits that are known to be never taken based on loop bound.
1251 Needs to be called after compilation of max_loop_iterations_int that
1252 populates the loop bounds. */
1253 modified |= remove_redundant_iv_tests (loop);
1254
1255 if (try_unroll_loop_completely (loop, exit, niter, may_be_zero, ul,
1256 maxiter, locus, allow_peel))
1257 return true;
1258
1259 if (create_iv
1260 && niter && !chrec_contains_undetermined (niter)
1261 && exit && just_once_each_iteration_p (loop, exit->src))
1262 {
1263 tree iv_niter = niter;
1264 if (may_be_zero)
1265 {
1266 if (COMPARISON_CLASS_P (niter_desc.may_be_zero))
1267 iv_niter = fold_build3 (COND_EXPR, TREE_TYPE (iv_niter),
1268 niter_desc.may_be_zero,
1269 build_int_cst (TREE_TYPE (iv_niter), 0),
1270 iv_niter);
1271 else
1272 iv_niter = NULL_TREE;
1273 }
1274 if (iv_niter)
1275 create_canonical_iv (loop, exit, iv_niter);
1276 }
1277
1278 if (ul == UL_ALL)
1279 modified |= try_peel_loop (loop, exit, niter, may_be_zero, maxiter);
1280
1281 return modified;
1282 }
1283
1284 /* The main entry point of the pass. Adds canonical induction variables
1285 to the suitable loops. */
1286
1287 unsigned int
canonicalize_induction_variables(void)1288 canonicalize_induction_variables (void)
1289 {
1290 bool changed = false;
1291 bool irred_invalidated = false;
1292 bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1293
1294 estimate_numbers_of_iterations (cfun);
1295
1296 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1297 {
1298 changed |= canonicalize_loop_induction_variables (loop,
1299 true, UL_SINGLE_ITER,
1300 true, false);
1301 }
1302 gcc_assert (!need_ssa_update_p (cfun));
1303
1304 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1305 if (irred_invalidated
1306 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1307 mark_irreducible_loops ();
1308
1309 /* Clean up the information about numbers of iterations, since brute force
1310 evaluation could reveal new information. */
1311 free_numbers_of_iterations_estimates (cfun);
1312 scev_reset ();
1313
1314 if (!bitmap_empty_p (loop_closed_ssa_invalidated))
1315 {
1316 gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
1317 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1318 }
1319 BITMAP_FREE (loop_closed_ssa_invalidated);
1320
1321 if (changed)
1322 return TODO_cleanup_cfg;
1323 return 0;
1324 }
1325
1326 /* Process loops from innermost to outer, stopping at the innermost
1327 loop we unrolled. */
1328
1329 static bool
tree_unroll_loops_completely_1(bool may_increase_size,bool unroll_outer,bitmap father_bbs,class loop * loop)1330 tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
1331 bitmap father_bbs, class loop *loop)
1332 {
1333 class loop *loop_father;
1334 bool changed = false;
1335 class loop *inner;
1336 enum unroll_level ul;
1337 unsigned num = number_of_loops (cfun);
1338
1339 /* Process inner loops first. Don't walk loops added by the recursive
1340 calls because SSA form is not up-to-date. They can be handled in the
1341 next iteration. */
1342 bitmap child_father_bbs = NULL;
1343 for (inner = loop->inner; inner != NULL; inner = inner->next)
1344 if ((unsigned) inner->num < num)
1345 {
1346 if (!child_father_bbs)
1347 child_father_bbs = BITMAP_ALLOC (NULL);
1348 if (tree_unroll_loops_completely_1 (may_increase_size, unroll_outer,
1349 child_father_bbs, inner))
1350 {
1351 bitmap_ior_into (father_bbs, child_father_bbs);
1352 bitmap_clear (child_father_bbs);
1353 changed = true;
1354 }
1355 }
1356 if (child_father_bbs)
1357 BITMAP_FREE (child_father_bbs);
1358
1359 /* If we changed an inner loop we cannot process outer loops in this
1360 iteration because SSA form is not up-to-date. Continue with
1361 siblings of outer loops instead. */
1362 if (changed)
1363 {
1364 /* If we are recorded as father clear all other fathers that
1365 are necessarily covered already to avoid redundant work. */
1366 if (bitmap_bit_p (father_bbs, loop->header->index))
1367 {
1368 bitmap_clear (father_bbs);
1369 bitmap_set_bit (father_bbs, loop->header->index);
1370 }
1371 return true;
1372 }
1373
1374 /* Don't unroll #pragma omp simd loops until the vectorizer
1375 attempts to vectorize those. */
1376 if (loop->force_vectorize)
1377 return false;
1378
1379 /* Try to unroll this loop. */
1380 loop_father = loop_outer (loop);
1381 if (!loop_father)
1382 return false;
1383
1384 if (loop->unroll > 1)
1385 ul = UL_ALL;
1386 else if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
1387 /* Unroll outermost loops only if asked to do so or they do
1388 not cause code growth. */
1389 && (unroll_outer || loop_outer (loop_father)))
1390 ul = UL_ALL;
1391 else
1392 ul = UL_NO_GROWTH;
1393
1394 if (canonicalize_loop_induction_variables
1395 (loop, false, ul, !flag_tree_loop_ivcanon, unroll_outer))
1396 {
1397 /* If we'll continue unrolling, we need to propagate constants
1398 within the new basic blocks to fold away induction variable
1399 computations; otherwise, the size might blow up before the
1400 iteration is complete and the IR eventually cleaned up. */
1401 if (loop_outer (loop_father))
1402 {
1403 /* Once we process our father we will have processed
1404 the fathers of our children as well, so avoid doing
1405 redundant work and clear fathers we've gathered sofar. */
1406 bitmap_clear (father_bbs);
1407 bitmap_set_bit (father_bbs, loop_father->header->index);
1408 }
1409 else if (unroll_outer)
1410 /* Trigger scalar cleanup once any outermost loop gets unrolled. */
1411 cfun->pending_TODOs |= PENDING_TODO_force_next_scalar_cleanup;
1412
1413 return true;
1414 }
1415
1416 return false;
1417 }
1418
1419 /* Unroll LOOPS completely if they iterate just few times. Unless
1420 MAY_INCREASE_SIZE is true, perform the unrolling only if the
1421 size of the code does not increase. */
1422
1423 static unsigned int
tree_unroll_loops_completely(bool may_increase_size,bool unroll_outer)1424 tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
1425 {
1426 bitmap father_bbs = BITMAP_ALLOC (NULL);
1427 bool changed;
1428 int iteration = 0;
1429 bool irred_invalidated = false;
1430
1431 estimate_numbers_of_iterations (cfun);
1432
1433 do
1434 {
1435 changed = false;
1436 bitmap loop_closed_ssa_invalidated = NULL;
1437
1438 if (loops_state_satisfies_p (LOOP_CLOSED_SSA))
1439 loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1440
1441 free_numbers_of_iterations_estimates (cfun);
1442 estimate_numbers_of_iterations (cfun);
1443
1444 changed = tree_unroll_loops_completely_1 (may_increase_size,
1445 unroll_outer, father_bbs,
1446 current_loops->tree_root);
1447 if (changed)
1448 {
1449 unsigned i;
1450
1451 unloop_loops (loop_closed_ssa_invalidated, &irred_invalidated);
1452
1453 /* We cannot use TODO_update_ssa_no_phi because VOPS gets confused. */
1454 if (loop_closed_ssa_invalidated
1455 && !bitmap_empty_p (loop_closed_ssa_invalidated))
1456 rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
1457 TODO_update_ssa);
1458 else
1459 update_ssa (TODO_update_ssa);
1460
1461 /* father_bbs is a bitmap of loop father header BB indices.
1462 Translate that to what non-root loops these BBs belong to now. */
1463 bitmap_iterator bi;
1464 bitmap fathers = BITMAP_ALLOC (NULL);
1465 EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
1466 {
1467 basic_block unrolled_loop_bb = BASIC_BLOCK_FOR_FN (cfun, i);
1468 if (! unrolled_loop_bb)
1469 continue;
1470 if (loop_outer (unrolled_loop_bb->loop_father))
1471 bitmap_set_bit (fathers,
1472 unrolled_loop_bb->loop_father->num);
1473 }
1474 bitmap_clear (father_bbs);
1475 /* Propagate the constants within the new basic blocks. */
1476 EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
1477 {
1478 loop_p father = get_loop (cfun, i);
1479 bitmap exit_bbs = BITMAP_ALLOC (NULL);
1480 loop_exit *exit = father->exits->next;
1481 while (exit->e)
1482 {
1483 bitmap_set_bit (exit_bbs, exit->e->dest->index);
1484 exit = exit->next;
1485 }
1486 do_rpo_vn (cfun, loop_preheader_edge (father), exit_bbs);
1487 }
1488 BITMAP_FREE (fathers);
1489
1490 /* Clean up the information about numbers of iterations, since
1491 complete unrolling might have invalidated it. */
1492 scev_reset ();
1493
1494 /* This will take care of removing completely unrolled loops
1495 from the loop structures so we can continue unrolling now
1496 innermost loops. */
1497 if (cleanup_tree_cfg ())
1498 update_ssa (TODO_update_ssa_only_virtuals);
1499
1500 if (flag_checking && loops_state_satisfies_p (LOOP_CLOSED_SSA))
1501 verify_loop_closed_ssa (true);
1502 }
1503 if (loop_closed_ssa_invalidated)
1504 BITMAP_FREE (loop_closed_ssa_invalidated);
1505 }
1506 while (changed
1507 && ++iteration <= param_max_unroll_iterations);
1508
1509 BITMAP_FREE (father_bbs);
1510
1511 if (irred_invalidated
1512 && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1513 mark_irreducible_loops ();
1514
1515 return 0;
1516 }
1517
1518 /* Canonical induction variable creation pass. */
1519
1520 namespace {
1521
1522 const pass_data pass_data_iv_canon =
1523 {
1524 GIMPLE_PASS, /* type */
1525 "ivcanon", /* name */
1526 OPTGROUP_LOOP, /* optinfo_flags */
1527 TV_TREE_LOOP_IVCANON, /* tv_id */
1528 ( PROP_cfg | PROP_ssa ), /* properties_required */
1529 0, /* properties_provided */
1530 0, /* properties_destroyed */
1531 0, /* todo_flags_start */
1532 0, /* todo_flags_finish */
1533 };
1534
1535 class pass_iv_canon : public gimple_opt_pass
1536 {
1537 public:
pass_iv_canon(gcc::context * ctxt)1538 pass_iv_canon (gcc::context *ctxt)
1539 : gimple_opt_pass (pass_data_iv_canon, ctxt)
1540 {}
1541
1542 /* opt_pass methods: */
gate(function *)1543 virtual bool gate (function *) { return flag_tree_loop_ivcanon != 0; }
1544 virtual unsigned int execute (function *fun);
1545
1546 }; // class pass_iv_canon
1547
1548 unsigned int
execute(function * fun)1549 pass_iv_canon::execute (function *fun)
1550 {
1551 if (number_of_loops (fun) <= 1)
1552 return 0;
1553
1554 return canonicalize_induction_variables ();
1555 }
1556
1557 } // anon namespace
1558
1559 gimple_opt_pass *
make_pass_iv_canon(gcc::context * ctxt)1560 make_pass_iv_canon (gcc::context *ctxt)
1561 {
1562 return new pass_iv_canon (ctxt);
1563 }
1564
1565 /* Complete unrolling of loops. */
1566
1567 namespace {
1568
1569 const pass_data pass_data_complete_unroll =
1570 {
1571 GIMPLE_PASS, /* type */
1572 "cunroll", /* name */
1573 OPTGROUP_LOOP, /* optinfo_flags */
1574 TV_COMPLETE_UNROLL, /* tv_id */
1575 ( PROP_cfg | PROP_ssa ), /* properties_required */
1576 0, /* properties_provided */
1577 0, /* properties_destroyed */
1578 0, /* todo_flags_start */
1579 0, /* todo_flags_finish */
1580 };
1581
1582 class pass_complete_unroll : public gimple_opt_pass
1583 {
1584 public:
pass_complete_unroll(gcc::context * ctxt)1585 pass_complete_unroll (gcc::context *ctxt)
1586 : gimple_opt_pass (pass_data_complete_unroll, ctxt)
1587 {}
1588
1589 /* opt_pass methods: */
1590 virtual unsigned int execute (function *);
1591
1592 }; // class pass_complete_unroll
1593
1594 unsigned int
execute(function * fun)1595 pass_complete_unroll::execute (function *fun)
1596 {
1597 if (number_of_loops (fun) <= 1)
1598 return 0;
1599
1600 /* If we ever decide to run loop peeling more than once, we will need to
1601 track loops already peeled in loop structures themselves to avoid
1602 re-peeling the same loop multiple times. */
1603 if (flag_peel_loops)
1604 peeled_loops = BITMAP_ALLOC (NULL);
1605 unsigned int val = tree_unroll_loops_completely (flag_cunroll_grow_size,
1606 true);
1607 if (peeled_loops)
1608 {
1609 BITMAP_FREE (peeled_loops);
1610 peeled_loops = NULL;
1611 }
1612 return val;
1613 }
1614
1615 } // anon namespace
1616
1617 gimple_opt_pass *
make_pass_complete_unroll(gcc::context * ctxt)1618 make_pass_complete_unroll (gcc::context *ctxt)
1619 {
1620 return new pass_complete_unroll (ctxt);
1621 }
1622
1623 /* Complete unrolling of inner loops. */
1624
1625 namespace {
1626
1627 const pass_data pass_data_complete_unrolli =
1628 {
1629 GIMPLE_PASS, /* type */
1630 "cunrolli", /* name */
1631 OPTGROUP_LOOP, /* optinfo_flags */
1632 TV_COMPLETE_UNROLL, /* tv_id */
1633 ( PROP_cfg | PROP_ssa ), /* properties_required */
1634 0, /* properties_provided */
1635 0, /* properties_destroyed */
1636 0, /* todo_flags_start */
1637 0, /* todo_flags_finish */
1638 };
1639
1640 class pass_complete_unrolli : public gimple_opt_pass
1641 {
1642 public:
pass_complete_unrolli(gcc::context * ctxt)1643 pass_complete_unrolli (gcc::context *ctxt)
1644 : gimple_opt_pass (pass_data_complete_unrolli, ctxt)
1645 {}
1646
1647 /* opt_pass methods: */
gate(function *)1648 virtual bool gate (function *) { return optimize >= 2; }
1649 virtual unsigned int execute (function *);
1650
1651 }; // class pass_complete_unrolli
1652
1653 unsigned int
execute(function * fun)1654 pass_complete_unrolli::execute (function *fun)
1655 {
1656 unsigned ret = 0;
1657
1658 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1659 if (number_of_loops (fun) > 1)
1660 {
1661 scev_initialize ();
1662 ret = tree_unroll_loops_completely (optimize >= 3, false);
1663 scev_finalize ();
1664 }
1665 loop_optimizer_finalize ();
1666
1667 return ret;
1668 }
1669
1670 } // anon namespace
1671
1672 gimple_opt_pass *
make_pass_complete_unrolli(gcc::context * ctxt)1673 make_pass_complete_unrolli (gcc::context *ctxt)
1674 {
1675 return new pass_complete_unrolli (ctxt);
1676 }
1677
1678
1679