xref: /netbsd-src/external/gpl3/gcc/dist/gcc/tree-ssa-loop-ivcanon.cc (revision 0a3071956a3a9fdebdbf7f338cf2d439b45fc728)
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