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