xref: /netbsd-src/external/gpl3/gcc.old/dist/gcc/tree-ssa-loop-niter.c (revision 8feb0f0b7eaff0608f8350bbfa3098827b4bb91b)
1 /* Functions to determine/estimate number of iterations of a loop.
2    Copyright (C) 2004-2020 Free Software Foundation, Inc.
3 
4 This file is part of GCC.
5 
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
10 
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15 
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19 
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "tree-pass.h"
28 #include "ssa.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "stor-layout.h"
32 #include "fold-const.h"
33 #include "calls.h"
34 #include "intl.h"
35 #include "gimplify.h"
36 #include "gimple-iterator.h"
37 #include "tree-cfg.h"
38 #include "tree-ssa-loop-ivopts.h"
39 #include "tree-ssa-loop-niter.h"
40 #include "tree-ssa-loop.h"
41 #include "cfgloop.h"
42 #include "tree-chrec.h"
43 #include "tree-scalar-evolution.h"
44 #include "tree-dfa.h"
45 
46 
47 /* The maximum number of dominator BBs we search for conditions
48    of loop header copies we use for simplifying a conditional
49    expression.  */
50 #define MAX_DOMINATORS_TO_WALK 8
51 
52 /*
53 
54    Analysis of number of iterations of an affine exit test.
55 
56 */
57 
58 /* Bounds on some value, BELOW <= X <= UP.  */
59 
60 struct bounds
61 {
62   mpz_t below, up;
63 };
64 
65 static bool number_of_iterations_popcount (loop_p loop, edge exit,
66 					   enum tree_code code,
67 					   class tree_niter_desc *niter);
68 
69 
70 /* Splits expression EXPR to a variable part VAR and constant OFFSET.  */
71 
72 static void
split_to_var_and_offset(tree expr,tree * var,mpz_t offset)73 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
74 {
75   tree type = TREE_TYPE (expr);
76   tree op0, op1;
77   bool negate = false;
78 
79   *var = expr;
80   mpz_set_ui (offset, 0);
81 
82   switch (TREE_CODE (expr))
83     {
84     case MINUS_EXPR:
85       negate = true;
86       /* Fallthru.  */
87 
88     case PLUS_EXPR:
89     case POINTER_PLUS_EXPR:
90       op0 = TREE_OPERAND (expr, 0);
91       op1 = TREE_OPERAND (expr, 1);
92 
93       if (TREE_CODE (op1) != INTEGER_CST)
94 	break;
95 
96       *var = op0;
97       /* Always sign extend the offset.  */
98       wi::to_mpz (wi::to_wide (op1), offset, SIGNED);
99       if (negate)
100 	mpz_neg (offset, offset);
101       break;
102 
103     case INTEGER_CST:
104       *var = build_int_cst_type (type, 0);
105       wi::to_mpz (wi::to_wide (expr), offset, TYPE_SIGN (type));
106       break;
107 
108     default:
109       break;
110     }
111 }
112 
113 /* From condition C0 CMP C1 derives information regarding the value range
114    of VAR, which is of TYPE.  Results are stored in to BELOW and UP.  */
115 
116 static void
refine_value_range_using_guard(tree type,tree var,tree c0,enum tree_code cmp,tree c1,mpz_t below,mpz_t up)117 refine_value_range_using_guard (tree type, tree var,
118 				tree c0, enum tree_code cmp, tree c1,
119 				mpz_t below, mpz_t up)
120 {
121   tree varc0, varc1, ctype;
122   mpz_t offc0, offc1;
123   mpz_t mint, maxt, minc1, maxc1;
124   wide_int minv, maxv;
125   bool no_wrap = nowrap_type_p (type);
126   bool c0_ok, c1_ok;
127   signop sgn = TYPE_SIGN (type);
128 
129   switch (cmp)
130     {
131     case LT_EXPR:
132     case LE_EXPR:
133     case GT_EXPR:
134     case GE_EXPR:
135       STRIP_SIGN_NOPS (c0);
136       STRIP_SIGN_NOPS (c1);
137       ctype = TREE_TYPE (c0);
138       if (!useless_type_conversion_p (ctype, type))
139 	return;
140 
141       break;
142 
143     case EQ_EXPR:
144       /* We could derive quite precise information from EQ_EXPR, however,
145 	 such a guard is unlikely to appear, so we do not bother with
146 	 handling it.  */
147       return;
148 
149     case NE_EXPR:
150       /* NE_EXPR comparisons do not contain much of useful information,
151 	 except for cases of comparing with bounds.  */
152       if (TREE_CODE (c1) != INTEGER_CST
153 	  || !INTEGRAL_TYPE_P (type))
154 	return;
155 
156       /* Ensure that the condition speaks about an expression in the same
157 	 type as X and Y.  */
158       ctype = TREE_TYPE (c0);
159       if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
160 	return;
161       c0 = fold_convert (type, c0);
162       c1 = fold_convert (type, c1);
163 
164       if (operand_equal_p (var, c0, 0))
165 	{
166 	  mpz_t valc1;
167 
168 	  /* Case of comparing VAR with its below/up bounds.  */
169 	  mpz_init (valc1);
170 	  wi::to_mpz (wi::to_wide (c1), valc1, TYPE_SIGN (type));
171 	  if (mpz_cmp (valc1, below) == 0)
172 	    cmp = GT_EXPR;
173 	  if (mpz_cmp (valc1, up) == 0)
174 	    cmp = LT_EXPR;
175 
176 	  mpz_clear (valc1);
177 	}
178       else
179 	{
180 	  /* Case of comparing with the bounds of the type.  */
181 	  wide_int min = wi::min_value (type);
182 	  wide_int max = wi::max_value (type);
183 
184 	  if (wi::to_wide (c1) == min)
185 	    cmp = GT_EXPR;
186 	  if (wi::to_wide (c1) == max)
187 	    cmp = LT_EXPR;
188 	}
189 
190       /* Quick return if no useful information.  */
191       if (cmp == NE_EXPR)
192 	return;
193 
194       break;
195 
196     default:
197       return;
198     }
199 
200   mpz_init (offc0);
201   mpz_init (offc1);
202   split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
203   split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
204 
205   /* We are only interested in comparisons of expressions based on VAR.  */
206   if (operand_equal_p (var, varc1, 0))
207     {
208       std::swap (varc0, varc1);
209       mpz_swap (offc0, offc1);
210       cmp = swap_tree_comparison (cmp);
211     }
212   else if (!operand_equal_p (var, varc0, 0))
213     {
214       mpz_clear (offc0);
215       mpz_clear (offc1);
216       return;
217     }
218 
219   mpz_init (mint);
220   mpz_init (maxt);
221   get_type_static_bounds (type, mint, maxt);
222   mpz_init (minc1);
223   mpz_init (maxc1);
224   /* Setup range information for varc1.  */
225   if (integer_zerop (varc1))
226     {
227       wi::to_mpz (0, minc1, TYPE_SIGN (type));
228       wi::to_mpz (0, maxc1, TYPE_SIGN (type));
229     }
230   else if (TREE_CODE (varc1) == SSA_NAME
231 	   && INTEGRAL_TYPE_P (type)
232 	   && get_range_info (varc1, &minv, &maxv) == VR_RANGE)
233     {
234       gcc_assert (wi::le_p (minv, maxv, sgn));
235       wi::to_mpz (minv, minc1, sgn);
236       wi::to_mpz (maxv, maxc1, sgn);
237     }
238   else
239     {
240       mpz_set (minc1, mint);
241       mpz_set (maxc1, maxt);
242     }
243 
244   /* Compute valid range information for varc1 + offc1.  Note nothing
245      useful can be derived if it overflows or underflows.  Overflow or
246      underflow could happen when:
247 
248        offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
249        offc1 < 0 && varc1 + offc1 < MIN_VAL (type).  */
250   mpz_add (minc1, minc1, offc1);
251   mpz_add (maxc1, maxc1, offc1);
252   c1_ok = (no_wrap
253 	   || mpz_sgn (offc1) == 0
254 	   || (mpz_sgn (offc1) < 0 && mpz_cmp (minc1, mint) >= 0)
255 	   || (mpz_sgn (offc1) > 0 && mpz_cmp (maxc1, maxt) <= 0));
256   if (!c1_ok)
257     goto end;
258 
259   if (mpz_cmp (minc1, mint) < 0)
260     mpz_set (minc1, mint);
261   if (mpz_cmp (maxc1, maxt) > 0)
262     mpz_set (maxc1, maxt);
263 
264   if (cmp == LT_EXPR)
265     {
266       cmp = LE_EXPR;
267       mpz_sub_ui (maxc1, maxc1, 1);
268     }
269   if (cmp == GT_EXPR)
270     {
271       cmp = GE_EXPR;
272       mpz_add_ui (minc1, minc1, 1);
273     }
274 
275   /* Compute range information for varc0.  If there is no overflow,
276      the condition implied that
277 
278        (varc0) cmp (varc1 + offc1 - offc0)
279 
280      We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
281      or the below bound if cmp is GE_EXPR.
282 
283      To prove there is no overflow/underflow, we need to check below
284      four cases:
285        1) cmp == LE_EXPR && offc0 > 0
286 
287 	    (varc0 + offc0) doesn't overflow
288 	    && (varc1 + offc1 - offc0) doesn't underflow
289 
290        2) cmp == LE_EXPR && offc0 < 0
291 
292 	    (varc0 + offc0) doesn't underflow
293 	    && (varc1 + offc1 - offc0) doesn't overfloe
294 
295 	  In this case, (varc0 + offc0) will never underflow if we can
296 	  prove (varc1 + offc1 - offc0) doesn't overflow.
297 
298        3) cmp == GE_EXPR && offc0 < 0
299 
300 	    (varc0 + offc0) doesn't underflow
301 	    && (varc1 + offc1 - offc0) doesn't overflow
302 
303        4) cmp == GE_EXPR && offc0 > 0
304 
305 	    (varc0 + offc0) doesn't overflow
306 	    && (varc1 + offc1 - offc0) doesn't underflow
307 
308 	  In this case, (varc0 + offc0) will never overflow if we can
309 	  prove (varc1 + offc1 - offc0) doesn't underflow.
310 
311      Note we only handle case 2 and 4 in below code.  */
312 
313   mpz_sub (minc1, minc1, offc0);
314   mpz_sub (maxc1, maxc1, offc0);
315   c0_ok = (no_wrap
316 	   || mpz_sgn (offc0) == 0
317 	   || (cmp == LE_EXPR
318 	       && mpz_sgn (offc0) < 0 && mpz_cmp (maxc1, maxt) <= 0)
319 	   || (cmp == GE_EXPR
320 	       && mpz_sgn (offc0) > 0 && mpz_cmp (minc1, mint) >= 0));
321   if (!c0_ok)
322     goto end;
323 
324   if (cmp == LE_EXPR)
325     {
326       if (mpz_cmp (up, maxc1) > 0)
327 	mpz_set (up, maxc1);
328     }
329   else
330     {
331       if (mpz_cmp (below, minc1) < 0)
332 	mpz_set (below, minc1);
333     }
334 
335 end:
336   mpz_clear (mint);
337   mpz_clear (maxt);
338   mpz_clear (minc1);
339   mpz_clear (maxc1);
340   mpz_clear (offc0);
341   mpz_clear (offc1);
342 }
343 
344 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
345    in TYPE to MIN and MAX.  */
346 
347 static void
determine_value_range(class loop * loop,tree type,tree var,mpz_t off,mpz_t min,mpz_t max)348 determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
349 		       mpz_t min, mpz_t max)
350 {
351   int cnt = 0;
352   mpz_t minm, maxm;
353   basic_block bb;
354   wide_int minv, maxv;
355   enum value_range_kind rtype = VR_VARYING;
356 
357   /* If the expression is a constant, we know its value exactly.  */
358   if (integer_zerop (var))
359     {
360       mpz_set (min, off);
361       mpz_set (max, off);
362       return;
363     }
364 
365   get_type_static_bounds (type, min, max);
366 
367   /* See if we have some range info from VRP.  */
368   if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type))
369     {
370       edge e = loop_preheader_edge (loop);
371       signop sgn = TYPE_SIGN (type);
372       gphi_iterator gsi;
373 
374       /* Either for VAR itself...  */
375       rtype = get_range_info (var, &minv, &maxv);
376       /* Or for PHI results in loop->header where VAR is used as
377 	 PHI argument from the loop preheader edge.  */
378       for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
379 	{
380 	  gphi *phi = gsi.phi ();
381 	  wide_int minc, maxc;
382 	  if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
383 	      && (get_range_info (gimple_phi_result (phi), &minc, &maxc)
384 		  == VR_RANGE))
385 	    {
386 	      if (rtype != VR_RANGE)
387 		{
388 		  rtype = VR_RANGE;
389 		  minv = minc;
390 		  maxv = maxc;
391 		}
392 	      else
393 		{
394 		  minv = wi::max (minv, minc, sgn);
395 		  maxv = wi::min (maxv, maxc, sgn);
396 		  /* If the PHI result range are inconsistent with
397 		     the VAR range, give up on looking at the PHI
398 		     results.  This can happen if VR_UNDEFINED is
399 		     involved.  */
400 		  if (wi::gt_p (minv, maxv, sgn))
401 		    {
402 		      rtype = get_range_info (var, &minv, &maxv);
403 		      break;
404 		    }
405 		}
406 	    }
407 	}
408       mpz_init (minm);
409       mpz_init (maxm);
410       if (rtype != VR_RANGE)
411 	{
412 	  mpz_set (minm, min);
413 	  mpz_set (maxm, max);
414 	}
415       else
416 	{
417 	  gcc_assert (wi::le_p (minv, maxv, sgn));
418 	  wi::to_mpz (minv, minm, sgn);
419 	  wi::to_mpz (maxv, maxm, sgn);
420 	}
421       /* Now walk the dominators of the loop header and use the entry
422 	 guards to refine the estimates.  */
423       for (bb = loop->header;
424 	   bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
425 	   bb = get_immediate_dominator (CDI_DOMINATORS, bb))
426 	{
427 	  edge e;
428 	  tree c0, c1;
429 	  gimple *cond;
430 	  enum tree_code cmp;
431 
432 	  if (!single_pred_p (bb))
433 	    continue;
434 	  e = single_pred_edge (bb);
435 
436 	  if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
437 	    continue;
438 
439 	  cond = last_stmt (e->src);
440 	  c0 = gimple_cond_lhs (cond);
441 	  cmp = gimple_cond_code (cond);
442 	  c1 = gimple_cond_rhs (cond);
443 
444 	  if (e->flags & EDGE_FALSE_VALUE)
445 	    cmp = invert_tree_comparison (cmp, false);
446 
447 	  refine_value_range_using_guard (type, var, c0, cmp, c1, minm, maxm);
448 	  ++cnt;
449 	}
450 
451       mpz_add (minm, minm, off);
452       mpz_add (maxm, maxm, off);
453       /* If the computation may not wrap or off is zero, then this
454 	 is always fine.  If off is negative and minv + off isn't
455 	 smaller than type's minimum, or off is positive and
456 	 maxv + off isn't bigger than type's maximum, use the more
457 	 precise range too.  */
458       if (nowrap_type_p (type)
459 	  || mpz_sgn (off) == 0
460 	  || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0)
461 	  || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0))
462 	{
463 	  mpz_set (min, minm);
464 	  mpz_set (max, maxm);
465 	  mpz_clear (minm);
466 	  mpz_clear (maxm);
467 	  return;
468 	}
469       mpz_clear (minm);
470       mpz_clear (maxm);
471     }
472 
473   /* If the computation may wrap, we know nothing about the value, except for
474      the range of the type.  */
475   if (!nowrap_type_p (type))
476     return;
477 
478   /* Since the addition of OFF does not wrap, if OFF is positive, then we may
479      add it to MIN, otherwise to MAX.  */
480   if (mpz_sgn (off) < 0)
481     mpz_add (max, max, off);
482   else
483     mpz_add (min, min, off);
484 }
485 
486 /* Stores the bounds on the difference of the values of the expressions
487    (var + X) and (var + Y), computed in TYPE, to BNDS.  */
488 
489 static void
bound_difference_of_offsetted_base(tree type,mpz_t x,mpz_t y,bounds * bnds)490 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
491 				    bounds *bnds)
492 {
493   int rel = mpz_cmp (x, y);
494   bool may_wrap = !nowrap_type_p (type);
495   mpz_t m;
496 
497   /* If X == Y, then the expressions are always equal.
498      If X > Y, there are the following possibilities:
499        a) neither of var + X and var + Y overflow or underflow, or both of
500 	  them do.  Then their difference is X - Y.
501        b) var + X overflows, and var + Y does not.  Then the values of the
502 	  expressions are var + X - M and var + Y, where M is the range of
503 	  the type, and their difference is X - Y - M.
504        c) var + Y underflows and var + X does not.  Their difference again
505 	  is M - X + Y.
506        Therefore, if the arithmetics in type does not overflow, then the
507        bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
508      Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
509      (X - Y, X - Y + M).  */
510 
511   if (rel == 0)
512     {
513       mpz_set_ui (bnds->below, 0);
514       mpz_set_ui (bnds->up, 0);
515       return;
516     }
517 
518   mpz_init (m);
519   wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), m, UNSIGNED);
520   mpz_add_ui (m, m, 1);
521   mpz_sub (bnds->up, x, y);
522   mpz_set (bnds->below, bnds->up);
523 
524   if (may_wrap)
525     {
526       if (rel > 0)
527 	mpz_sub (bnds->below, bnds->below, m);
528       else
529 	mpz_add (bnds->up, bnds->up, m);
530     }
531 
532   mpz_clear (m);
533 }
534 
535 /* From condition C0 CMP C1 derives information regarding the
536    difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
537    and stores it to BNDS.  */
538 
539 static void
refine_bounds_using_guard(tree type,tree varx,mpz_t offx,tree vary,mpz_t offy,tree c0,enum tree_code cmp,tree c1,bounds * bnds)540 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
541 			   tree vary, mpz_t offy,
542 			   tree c0, enum tree_code cmp, tree c1,
543 			   bounds *bnds)
544 {
545   tree varc0, varc1, ctype;
546   mpz_t offc0, offc1, loffx, loffy, bnd;
547   bool lbound = false;
548   bool no_wrap = nowrap_type_p (type);
549   bool x_ok, y_ok;
550 
551   switch (cmp)
552     {
553     case LT_EXPR:
554     case LE_EXPR:
555     case GT_EXPR:
556     case GE_EXPR:
557       STRIP_SIGN_NOPS (c0);
558       STRIP_SIGN_NOPS (c1);
559       ctype = TREE_TYPE (c0);
560       if (!useless_type_conversion_p (ctype, type))
561 	return;
562 
563       break;
564 
565     case EQ_EXPR:
566       /* We could derive quite precise information from EQ_EXPR, however, such
567 	 a guard is unlikely to appear, so we do not bother with handling
568 	 it.  */
569       return;
570 
571     case NE_EXPR:
572       /* NE_EXPR comparisons do not contain much of useful information, except for
573 	 special case of comparing with the bounds of the type.  */
574       if (TREE_CODE (c1) != INTEGER_CST
575 	  || !INTEGRAL_TYPE_P (type))
576 	return;
577 
578       /* Ensure that the condition speaks about an expression in the same type
579 	 as X and Y.  */
580       ctype = TREE_TYPE (c0);
581       if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
582 	return;
583       c0 = fold_convert (type, c0);
584       c1 = fold_convert (type, c1);
585 
586       if (TYPE_MIN_VALUE (type)
587 	  && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
588 	{
589 	  cmp = GT_EXPR;
590 	  break;
591 	}
592       if (TYPE_MAX_VALUE (type)
593 	  && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
594 	{
595 	  cmp = LT_EXPR;
596 	  break;
597 	}
598 
599       return;
600     default:
601       return;
602     }
603 
604   mpz_init (offc0);
605   mpz_init (offc1);
606   split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
607   split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
608 
609   /* We are only interested in comparisons of expressions based on VARX and
610      VARY.  TODO -- we might also be able to derive some bounds from
611      expressions containing just one of the variables.  */
612 
613   if (operand_equal_p (varx, varc1, 0))
614     {
615       std::swap (varc0, varc1);
616       mpz_swap (offc0, offc1);
617       cmp = swap_tree_comparison (cmp);
618     }
619 
620   if (!operand_equal_p (varx, varc0, 0)
621       || !operand_equal_p (vary, varc1, 0))
622     goto end;
623 
624   mpz_init_set (loffx, offx);
625   mpz_init_set (loffy, offy);
626 
627   if (cmp == GT_EXPR || cmp == GE_EXPR)
628     {
629       std::swap (varx, vary);
630       mpz_swap (offc0, offc1);
631       mpz_swap (loffx, loffy);
632       cmp = swap_tree_comparison (cmp);
633       lbound = true;
634     }
635 
636   /* If there is no overflow, the condition implies that
637 
638      (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
639 
640      The overflows and underflows may complicate things a bit; each
641      overflow decreases the appropriate offset by M, and underflow
642      increases it by M.  The above inequality would not necessarily be
643      true if
644 
645      -- VARX + OFFX underflows and VARX + OFFC0 does not, or
646 	VARX + OFFC0 overflows, but VARX + OFFX does not.
647 	This may only happen if OFFX < OFFC0.
648      -- VARY + OFFY overflows and VARY + OFFC1 does not, or
649 	VARY + OFFC1 underflows and VARY + OFFY does not.
650 	This may only happen if OFFY > OFFC1.  */
651 
652   if (no_wrap)
653     {
654       x_ok = true;
655       y_ok = true;
656     }
657   else
658     {
659       x_ok = (integer_zerop (varx)
660 	      || mpz_cmp (loffx, offc0) >= 0);
661       y_ok = (integer_zerop (vary)
662 	      || mpz_cmp (loffy, offc1) <= 0);
663     }
664 
665   if (x_ok && y_ok)
666     {
667       mpz_init (bnd);
668       mpz_sub (bnd, loffx, loffy);
669       mpz_add (bnd, bnd, offc1);
670       mpz_sub (bnd, bnd, offc0);
671 
672       if (cmp == LT_EXPR)
673 	mpz_sub_ui (bnd, bnd, 1);
674 
675       if (lbound)
676 	{
677 	  mpz_neg (bnd, bnd);
678 	  if (mpz_cmp (bnds->below, bnd) < 0)
679 	    mpz_set (bnds->below, bnd);
680 	}
681       else
682 	{
683 	  if (mpz_cmp (bnd, bnds->up) < 0)
684 	    mpz_set (bnds->up, bnd);
685 	}
686       mpz_clear (bnd);
687     }
688 
689   mpz_clear (loffx);
690   mpz_clear (loffy);
691 end:
692   mpz_clear (offc0);
693   mpz_clear (offc1);
694 }
695 
696 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
697    The subtraction is considered to be performed in arbitrary precision,
698    without overflows.
699 
700    We do not attempt to be too clever regarding the value ranges of X and
701    Y; most of the time, they are just integers or ssa names offsetted by
702    integer.  However, we try to use the information contained in the
703    comparisons before the loop (usually created by loop header copying).  */
704 
705 static void
bound_difference(class loop * loop,tree x,tree y,bounds * bnds)706 bound_difference (class loop *loop, tree x, tree y, bounds *bnds)
707 {
708   tree type = TREE_TYPE (x);
709   tree varx, vary;
710   mpz_t offx, offy;
711   mpz_t minx, maxx, miny, maxy;
712   int cnt = 0;
713   edge e;
714   basic_block bb;
715   tree c0, c1;
716   gimple *cond;
717   enum tree_code cmp;
718 
719   /* Get rid of unnecessary casts, but preserve the value of
720      the expressions.  */
721   STRIP_SIGN_NOPS (x);
722   STRIP_SIGN_NOPS (y);
723 
724   mpz_init (bnds->below);
725   mpz_init (bnds->up);
726   mpz_init (offx);
727   mpz_init (offy);
728   split_to_var_and_offset (x, &varx, offx);
729   split_to_var_and_offset (y, &vary, offy);
730 
731   if (!integer_zerop (varx)
732       && operand_equal_p (varx, vary, 0))
733     {
734       /* Special case VARX == VARY -- we just need to compare the
735          offsets.  The matters are a bit more complicated in the
736 	 case addition of offsets may wrap.  */
737       bound_difference_of_offsetted_base (type, offx, offy, bnds);
738     }
739   else
740     {
741       /* Otherwise, use the value ranges to determine the initial
742 	 estimates on below and up.  */
743       mpz_init (minx);
744       mpz_init (maxx);
745       mpz_init (miny);
746       mpz_init (maxy);
747       determine_value_range (loop, type, varx, offx, minx, maxx);
748       determine_value_range (loop, type, vary, offy, miny, maxy);
749 
750       mpz_sub (bnds->below, minx, maxy);
751       mpz_sub (bnds->up, maxx, miny);
752       mpz_clear (minx);
753       mpz_clear (maxx);
754       mpz_clear (miny);
755       mpz_clear (maxy);
756     }
757 
758   /* If both X and Y are constants, we cannot get any more precise.  */
759   if (integer_zerop (varx) && integer_zerop (vary))
760     goto end;
761 
762   /* Now walk the dominators of the loop header and use the entry
763      guards to refine the estimates.  */
764   for (bb = loop->header;
765        bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
766        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
767     {
768       if (!single_pred_p (bb))
769 	continue;
770       e = single_pred_edge (bb);
771 
772       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
773 	continue;
774 
775       cond = last_stmt (e->src);
776       c0 = gimple_cond_lhs (cond);
777       cmp = gimple_cond_code (cond);
778       c1 = gimple_cond_rhs (cond);
779 
780       if (e->flags & EDGE_FALSE_VALUE)
781 	cmp = invert_tree_comparison (cmp, false);
782 
783       refine_bounds_using_guard (type, varx, offx, vary, offy,
784 				 c0, cmp, c1, bnds);
785       ++cnt;
786     }
787 
788 end:
789   mpz_clear (offx);
790   mpz_clear (offy);
791 }
792 
793 /* Update the bounds in BNDS that restrict the value of X to the bounds
794    that restrict the value of X + DELTA.  X can be obtained as a
795    difference of two values in TYPE.  */
796 
797 static void
bounds_add(bounds * bnds,const widest_int & delta,tree type)798 bounds_add (bounds *bnds, const widest_int &delta, tree type)
799 {
800   mpz_t mdelta, max;
801 
802   mpz_init (mdelta);
803   wi::to_mpz (delta, mdelta, SIGNED);
804 
805   mpz_init (max);
806   wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
807 
808   mpz_add (bnds->up, bnds->up, mdelta);
809   mpz_add (bnds->below, bnds->below, mdelta);
810 
811   if (mpz_cmp (bnds->up, max) > 0)
812     mpz_set (bnds->up, max);
813 
814   mpz_neg (max, max);
815   if (mpz_cmp (bnds->below, max) < 0)
816     mpz_set (bnds->below, max);
817 
818   mpz_clear (mdelta);
819   mpz_clear (max);
820 }
821 
822 /* Update the bounds in BNDS that restrict the value of X to the bounds
823    that restrict the value of -X.  */
824 
825 static void
bounds_negate(bounds * bnds)826 bounds_negate (bounds *bnds)
827 {
828   mpz_t tmp;
829 
830   mpz_init_set (tmp, bnds->up);
831   mpz_neg (bnds->up, bnds->below);
832   mpz_neg (bnds->below, tmp);
833   mpz_clear (tmp);
834 }
835 
836 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
837 
838 static tree
inverse(tree x,tree mask)839 inverse (tree x, tree mask)
840 {
841   tree type = TREE_TYPE (x);
842   tree rslt;
843   unsigned ctr = tree_floor_log2 (mask);
844 
845   if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
846     {
847       unsigned HOST_WIDE_INT ix;
848       unsigned HOST_WIDE_INT imask;
849       unsigned HOST_WIDE_INT irslt = 1;
850 
851       gcc_assert (cst_and_fits_in_hwi (x));
852       gcc_assert (cst_and_fits_in_hwi (mask));
853 
854       ix = int_cst_value (x);
855       imask = int_cst_value (mask);
856 
857       for (; ctr; ctr--)
858 	{
859 	  irslt *= ix;
860 	  ix *= ix;
861 	}
862       irslt &= imask;
863 
864       rslt = build_int_cst_type (type, irslt);
865     }
866   else
867     {
868       rslt = build_int_cst (type, 1);
869       for (; ctr; ctr--)
870 	{
871 	  rslt = int_const_binop (MULT_EXPR, rslt, x);
872 	  x = int_const_binop (MULT_EXPR, x, x);
873 	}
874       rslt = int_const_binop (BIT_AND_EXPR, rslt, mask);
875     }
876 
877   return rslt;
878 }
879 
880 /* Derives the upper bound BND on the number of executions of loop with exit
881    condition S * i <> C.  If NO_OVERFLOW is true, then the control variable of
882    the loop does not overflow.  EXIT_MUST_BE_TAKEN is true if we are guaranteed
883    that the loop ends through this exit, i.e., the induction variable ever
884    reaches the value of C.
885 
886    The value C is equal to final - base, where final and base are the final and
887    initial value of the actual induction variable in the analysed loop.  BNDS
888    bounds the value of this difference when computed in signed type with
889    unbounded range, while the computation of C is performed in an unsigned
890    type with the range matching the range of the type of the induction variable.
891    In particular, BNDS.up contains an upper bound on C in the following cases:
892    -- if the iv must reach its final value without overflow, i.e., if
893       NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
894    -- if final >= base, which we know to hold when BNDS.below >= 0.  */
895 
896 static void
number_of_iterations_ne_max(mpz_t bnd,bool no_overflow,tree c,tree s,bounds * bnds,bool exit_must_be_taken)897 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
898 			     bounds *bnds, bool exit_must_be_taken)
899 {
900   widest_int max;
901   mpz_t d;
902   tree type = TREE_TYPE (c);
903   bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
904 		       || mpz_sgn (bnds->below) >= 0);
905 
906   if (integer_onep (s)
907       || (TREE_CODE (c) == INTEGER_CST
908 	  && TREE_CODE (s) == INTEGER_CST
909 	  && wi::mod_trunc (wi::to_wide (c), wi::to_wide (s),
910 			    TYPE_SIGN (type)) == 0)
911       || (TYPE_OVERFLOW_UNDEFINED (type)
912 	  && multiple_of_p (type, c, s)))
913     {
914       /* If C is an exact multiple of S, then its value will be reached before
915 	 the induction variable overflows (unless the loop is exited in some
916 	 other way before).  Note that the actual induction variable in the
917 	 loop (which ranges from base to final instead of from 0 to C) may
918 	 overflow, in which case BNDS.up will not be giving a correct upper
919 	 bound on C; thus, BNDS_U_VALID had to be computed in advance.  */
920       no_overflow = true;
921       exit_must_be_taken = true;
922     }
923 
924   /* If the induction variable can overflow, the number of iterations is at
925      most the period of the control variable (or infinite, but in that case
926      the whole # of iterations analysis will fail).  */
927   if (!no_overflow)
928     {
929       max = wi::mask <widest_int> (TYPE_PRECISION (type)
930 				   - wi::ctz (wi::to_wide (s)), false);
931       wi::to_mpz (max, bnd, UNSIGNED);
932       return;
933     }
934 
935   /* Now we know that the induction variable does not overflow, so the loop
936      iterates at most (range of type / S) times.  */
937   wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), bnd, UNSIGNED);
938 
939   /* If the induction variable is guaranteed to reach the value of C before
940      overflow, ... */
941   if (exit_must_be_taken)
942     {
943       /* ... then we can strengthen this to C / S, and possibly we can use
944 	 the upper bound on C given by BNDS.  */
945       if (TREE_CODE (c) == INTEGER_CST)
946 	wi::to_mpz (wi::to_wide (c), bnd, UNSIGNED);
947       else if (bnds_u_valid)
948 	mpz_set (bnd, bnds->up);
949     }
950 
951   mpz_init (d);
952   wi::to_mpz (wi::to_wide (s), d, UNSIGNED);
953   mpz_fdiv_q (bnd, bnd, d);
954   mpz_clear (d);
955 }
956 
957 /* Determines number of iterations of loop whose ending condition
958    is IV <> FINAL.  TYPE is the type of the iv.  The number of
959    iterations is stored to NITER.  EXIT_MUST_BE_TAKEN is true if
960    we know that the exit must be taken eventually, i.e., that the IV
961    ever reaches the value FINAL (we derived this earlier, and possibly set
962    NITER->assumptions to make sure this is the case).  BNDS contains the
963    bounds on the difference FINAL - IV->base.  */
964 
965 static bool
number_of_iterations_ne(class loop * loop,tree type,affine_iv * iv,tree final,class tree_niter_desc * niter,bool exit_must_be_taken,bounds * bnds)966 number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv,
967 			 tree final, class tree_niter_desc *niter,
968 			 bool exit_must_be_taken, bounds *bnds)
969 {
970   tree niter_type = unsigned_type_for (type);
971   tree s, c, d, bits, assumption, tmp, bound;
972   mpz_t max;
973 
974   niter->control = *iv;
975   niter->bound = final;
976   niter->cmp = NE_EXPR;
977 
978   /* Rearrange the terms so that we get inequality S * i <> C, with S
979      positive.  Also cast everything to the unsigned type.  If IV does
980      not overflow, BNDS bounds the value of C.  Also, this is the
981      case if the computation |FINAL - IV->base| does not overflow, i.e.,
982      if BNDS->below in the result is nonnegative.  */
983   if (tree_int_cst_sign_bit (iv->step))
984     {
985       s = fold_convert (niter_type,
986 			fold_build1 (NEGATE_EXPR, type, iv->step));
987       c = fold_build2 (MINUS_EXPR, niter_type,
988 		       fold_convert (niter_type, iv->base),
989 		       fold_convert (niter_type, final));
990       bounds_negate (bnds);
991     }
992   else
993     {
994       s = fold_convert (niter_type, iv->step);
995       c = fold_build2 (MINUS_EXPR, niter_type,
996 		       fold_convert (niter_type, final),
997 		       fold_convert (niter_type, iv->base));
998     }
999 
1000   mpz_init (max);
1001   number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
1002 			       exit_must_be_taken);
1003   niter->max = widest_int::from (wi::from_mpz (niter_type, max, false),
1004 				 TYPE_SIGN (niter_type));
1005   mpz_clear (max);
1006 
1007   /* Compute no-overflow information for the control iv.  This can be
1008      proven when below two conditions are satisfied:
1009 
1010        1) IV evaluates toward FINAL at beginning, i.e:
1011 	    base <= FINAL ; step > 0
1012 	    base >= FINAL ; step < 0
1013 
1014        2) |FINAL - base| is an exact multiple of step.
1015 
1016      Unfortunately, it's hard to prove above conditions after pass loop-ch
1017      because loop with exit condition (IV != FINAL) usually will be guarded
1018      by initial-condition (IV.base - IV.step != FINAL).  In this case, we
1019      can alternatively try to prove below conditions:
1020 
1021        1') IV evaluates toward FINAL at beginning, i.e:
1022 	    new_base = base - step < FINAL ; step > 0
1023 					     && base - step doesn't underflow
1024 	    new_base = base - step > FINAL ; step < 0
1025 					     && base - step doesn't overflow
1026 
1027        2') |FINAL - new_base| is an exact multiple of step.
1028 
1029      Please refer to PR34114 as an example of loop-ch's impact, also refer
1030      to PR72817 as an example why condition 2') is necessary.
1031 
1032      Note, for NE_EXPR, base equals to FINAL is a special case, in
1033      which the loop exits immediately, and the iv does not overflow.  */
1034   if (!niter->control.no_overflow
1035       && (integer_onep (s) || multiple_of_p (type, c, s)))
1036     {
1037       tree t, cond, new_c, relaxed_cond = boolean_false_node;
1038 
1039       if (tree_int_cst_sign_bit (iv->step))
1040 	{
1041 	  cond = fold_build2 (GE_EXPR, boolean_type_node, iv->base, final);
1042 	  if (TREE_CODE (type) == INTEGER_TYPE)
1043 	    {
1044 	      /* Only when base - step doesn't overflow.  */
1045 	      t = TYPE_MAX_VALUE (type);
1046 	      t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1047 	      t = fold_build2 (GE_EXPR, boolean_type_node, t, iv->base);
1048 	      if (integer_nonzerop (t))
1049 		{
1050 		  t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1051 		  new_c = fold_build2 (MINUS_EXPR, niter_type,
1052 				       fold_convert (niter_type, t),
1053 				       fold_convert (niter_type, final));
1054 		  if (multiple_of_p (type, new_c, s))
1055 		    relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node,
1056 						t, final);
1057 		}
1058 	    }
1059 	}
1060       else
1061 	{
1062 	  cond = fold_build2 (LE_EXPR, boolean_type_node, iv->base, final);
1063 	  if (TREE_CODE (type) == INTEGER_TYPE)
1064 	    {
1065 	      /* Only when base - step doesn't underflow.  */
1066 	      t = TYPE_MIN_VALUE (type);
1067 	      t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1068 	      t = fold_build2 (LE_EXPR, boolean_type_node, t, iv->base);
1069 	      if (integer_nonzerop (t))
1070 		{
1071 		  t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1072 		  new_c = fold_build2 (MINUS_EXPR, niter_type,
1073 				       fold_convert (niter_type, final),
1074 				       fold_convert (niter_type, t));
1075 		  if (multiple_of_p (type, new_c, s))
1076 		    relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node,
1077 						t, final);
1078 		}
1079 	    }
1080 	}
1081 
1082       t = simplify_using_initial_conditions (loop, cond);
1083       if (!t || !integer_onep (t))
1084 	t = simplify_using_initial_conditions (loop, relaxed_cond);
1085 
1086       if (t && integer_onep (t))
1087 	niter->control.no_overflow = true;
1088     }
1089 
1090   /* First the trivial cases -- when the step is 1.  */
1091   if (integer_onep (s))
1092     {
1093       niter->niter = c;
1094       return true;
1095     }
1096   if (niter->control.no_overflow && multiple_of_p (type, c, s))
1097     {
1098       niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, c, s);
1099       return true;
1100     }
1101 
1102   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
1103      is infinite.  Otherwise, the number of iterations is
1104      (inverse(s/d) * (c/d)) mod (size of mode/d).  */
1105   bits = num_ending_zeros (s);
1106   bound = build_low_bits_mask (niter_type,
1107 			       (TYPE_PRECISION (niter_type)
1108 				- tree_to_uhwi (bits)));
1109 
1110   d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
1111 			       build_int_cst (niter_type, 1), bits);
1112   s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
1113 
1114   if (!exit_must_be_taken)
1115     {
1116       /* If we cannot assume that the exit is taken eventually, record the
1117 	 assumptions for divisibility of c.  */
1118       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
1119       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
1120 				assumption, build_int_cst (niter_type, 0));
1121       if (!integer_nonzerop (assumption))
1122 	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1123 					  niter->assumptions, assumption);
1124     }
1125 
1126   c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
1127   if (integer_onep (s))
1128     {
1129       niter->niter = c;
1130     }
1131   else
1132     {
1133       tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
1134       niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
1135     }
1136   return true;
1137 }
1138 
1139 /* Checks whether we can determine the final value of the control variable
1140    of the loop with ending condition IV0 < IV1 (computed in TYPE).
1141    DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1142    of the step.  The assumptions necessary to ensure that the computation
1143    of the final value does not overflow are recorded in NITER.  If we
1144    find the final value, we adjust DELTA and return TRUE.  Otherwise
1145    we return false.  BNDS bounds the value of IV1->base - IV0->base,
1146    and will be updated by the same amount as DELTA.  EXIT_MUST_BE_TAKEN is
1147    true if we know that the exit must be taken eventually.  */
1148 
1149 static bool
number_of_iterations_lt_to_ne(tree type,affine_iv * iv0,affine_iv * iv1,class tree_niter_desc * niter,tree * delta,tree step,bool exit_must_be_taken,bounds * bnds)1150 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
1151 			       class tree_niter_desc *niter,
1152 			       tree *delta, tree step,
1153 			       bool exit_must_be_taken, bounds *bnds)
1154 {
1155   tree niter_type = TREE_TYPE (step);
1156   tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
1157   tree tmod;
1158   mpz_t mmod;
1159   tree assumption = boolean_true_node, bound, noloop;
1160   bool ret = false, fv_comp_no_overflow;
1161   tree type1 = type;
1162   if (POINTER_TYPE_P (type))
1163     type1 = sizetype;
1164 
1165   if (TREE_CODE (mod) != INTEGER_CST)
1166     return false;
1167   if (integer_nonzerop (mod))
1168     mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
1169   tmod = fold_convert (type1, mod);
1170 
1171   mpz_init (mmod);
1172   wi::to_mpz (wi::to_wide (mod), mmod, UNSIGNED);
1173   mpz_neg (mmod, mmod);
1174 
1175   /* If the induction variable does not overflow and the exit is taken,
1176      then the computation of the final value does not overflow.  This is
1177      also obviously the case if the new final value is equal to the
1178      current one.  Finally, we postulate this for pointer type variables,
1179      as the code cannot rely on the object to that the pointer points being
1180      placed at the end of the address space (and more pragmatically,
1181      TYPE_{MIN,MAX}_VALUE is not defined for pointers).  */
1182   if (integer_zerop (mod) || POINTER_TYPE_P (type))
1183     fv_comp_no_overflow = true;
1184   else if (!exit_must_be_taken)
1185     fv_comp_no_overflow = false;
1186   else
1187     fv_comp_no_overflow =
1188 	    (iv0->no_overflow && integer_nonzerop (iv0->step))
1189 	    || (iv1->no_overflow && integer_nonzerop (iv1->step));
1190 
1191   if (integer_nonzerop (iv0->step))
1192     {
1193       /* The final value of the iv is iv1->base + MOD, assuming that this
1194 	 computation does not overflow, and that
1195 	 iv0->base <= iv1->base + MOD.  */
1196       if (!fv_comp_no_overflow)
1197 	{
1198 	  bound = fold_build2 (MINUS_EXPR, type1,
1199 			       TYPE_MAX_VALUE (type1), tmod);
1200 	  assumption = fold_build2 (LE_EXPR, boolean_type_node,
1201 				    iv1->base, bound);
1202 	  if (integer_zerop (assumption))
1203 	    goto end;
1204 	}
1205       if (mpz_cmp (mmod, bnds->below) < 0)
1206 	noloop = boolean_false_node;
1207       else if (POINTER_TYPE_P (type))
1208 	noloop = fold_build2 (GT_EXPR, boolean_type_node,
1209 			      iv0->base,
1210 			      fold_build_pointer_plus (iv1->base, tmod));
1211       else
1212 	noloop = fold_build2 (GT_EXPR, boolean_type_node,
1213 			      iv0->base,
1214 			      fold_build2 (PLUS_EXPR, type1,
1215 					   iv1->base, tmod));
1216     }
1217   else
1218     {
1219       /* The final value of the iv is iv0->base - MOD, assuming that this
1220 	 computation does not overflow, and that
1221 	 iv0->base - MOD <= iv1->base. */
1222       if (!fv_comp_no_overflow)
1223 	{
1224 	  bound = fold_build2 (PLUS_EXPR, type1,
1225 			       TYPE_MIN_VALUE (type1), tmod);
1226 	  assumption = fold_build2 (GE_EXPR, boolean_type_node,
1227 				    iv0->base, bound);
1228 	  if (integer_zerop (assumption))
1229 	    goto end;
1230 	}
1231       if (mpz_cmp (mmod, bnds->below) < 0)
1232 	noloop = boolean_false_node;
1233       else if (POINTER_TYPE_P (type))
1234 	noloop = fold_build2 (GT_EXPR, boolean_type_node,
1235 			      fold_build_pointer_plus (iv0->base,
1236 						       fold_build1 (NEGATE_EXPR,
1237 								    type1, tmod)),
1238 			      iv1->base);
1239       else
1240 	noloop = fold_build2 (GT_EXPR, boolean_type_node,
1241 			      fold_build2 (MINUS_EXPR, type1,
1242 					   iv0->base, tmod),
1243 			      iv1->base);
1244     }
1245 
1246   if (!integer_nonzerop (assumption))
1247     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1248 				      niter->assumptions,
1249 				      assumption);
1250   if (!integer_zerop (noloop))
1251     niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1252 				      niter->may_be_zero,
1253 				      noloop);
1254   bounds_add (bnds, wi::to_widest (mod), type);
1255   *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
1256 
1257   ret = true;
1258 end:
1259   mpz_clear (mmod);
1260   return ret;
1261 }
1262 
1263 /* Add assertions to NITER that ensure that the control variable of the loop
1264    with ending condition IV0 < IV1 does not overflow.  Types of IV0 and IV1
1265    are TYPE.  Returns false if we can prove that there is an overflow, true
1266    otherwise.  STEP is the absolute value of the step.  */
1267 
1268 static bool
assert_no_overflow_lt(tree type,affine_iv * iv0,affine_iv * iv1,class tree_niter_desc * niter,tree step)1269 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1270 		       class tree_niter_desc *niter, tree step)
1271 {
1272   tree bound, d, assumption, diff;
1273   tree niter_type = TREE_TYPE (step);
1274 
1275   if (integer_nonzerop (iv0->step))
1276     {
1277       /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1278       if (iv0->no_overflow)
1279 	return true;
1280 
1281       /* If iv0->base is a constant, we can determine the last value before
1282 	 overflow precisely; otherwise we conservatively assume
1283 	 MAX - STEP + 1.  */
1284 
1285       if (TREE_CODE (iv0->base) == INTEGER_CST)
1286 	{
1287 	  d = fold_build2 (MINUS_EXPR, niter_type,
1288 			   fold_convert (niter_type, TYPE_MAX_VALUE (type)),
1289 			   fold_convert (niter_type, iv0->base));
1290 	  diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
1291 	}
1292       else
1293 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
1294 			    build_int_cst (niter_type, 1));
1295       bound = fold_build2 (MINUS_EXPR, type,
1296 			   TYPE_MAX_VALUE (type), fold_convert (type, diff));
1297       assumption = fold_build2 (LE_EXPR, boolean_type_node,
1298 				iv1->base, bound);
1299     }
1300   else
1301     {
1302       /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1303       if (iv1->no_overflow)
1304 	return true;
1305 
1306       if (TREE_CODE (iv1->base) == INTEGER_CST)
1307 	{
1308 	  d = fold_build2 (MINUS_EXPR, niter_type,
1309 			   fold_convert (niter_type, iv1->base),
1310 			   fold_convert (niter_type, TYPE_MIN_VALUE (type)));
1311 	  diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
1312 	}
1313       else
1314 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
1315 			    build_int_cst (niter_type, 1));
1316       bound = fold_build2 (PLUS_EXPR, type,
1317 			   TYPE_MIN_VALUE (type), fold_convert (type, diff));
1318       assumption = fold_build2 (GE_EXPR, boolean_type_node,
1319 				iv0->base, bound);
1320     }
1321 
1322   if (integer_zerop (assumption))
1323     return false;
1324   if (!integer_nonzerop (assumption))
1325     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1326 				      niter->assumptions, assumption);
1327 
1328   iv0->no_overflow = true;
1329   iv1->no_overflow = true;
1330   return true;
1331 }
1332 
1333 /* Add an assumption to NITER that a loop whose ending condition
1334    is IV0 < IV1 rolls.  TYPE is the type of the control iv.  BNDS
1335    bounds the value of IV1->base - IV0->base.  */
1336 
1337 static void
assert_loop_rolls_lt(tree type,affine_iv * iv0,affine_iv * iv1,class tree_niter_desc * niter,bounds * bnds)1338 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1339 		      class tree_niter_desc *niter, bounds *bnds)
1340 {
1341   tree assumption = boolean_true_node, bound, diff;
1342   tree mbz, mbzl, mbzr, type1;
1343   bool rolls_p, no_overflow_p;
1344   widest_int dstep;
1345   mpz_t mstep, max;
1346 
1347   /* We are going to compute the number of iterations as
1348      (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1349      variant of TYPE.  This formula only works if
1350 
1351      -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1352 
1353      (where MAX is the maximum value of the unsigned variant of TYPE, and
1354      the computations in this formula are performed in full precision,
1355      i.e., without overflows).
1356 
1357      Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1358      we have a condition of the form iv0->base - step < iv1->base before the loop,
1359      and for loops iv0->base < iv1->base - step * i the condition
1360      iv0->base < iv1->base + step, due to loop header copying, which enable us
1361      to prove the lower bound.
1362 
1363      The upper bound is more complicated.  Unless the expressions for initial
1364      and final value themselves contain enough information, we usually cannot
1365      derive it from the context.  */
1366 
1367   /* First check whether the answer does not follow from the bounds we gathered
1368      before.  */
1369   if (integer_nonzerop (iv0->step))
1370     dstep = wi::to_widest (iv0->step);
1371   else
1372     {
1373       dstep = wi::sext (wi::to_widest (iv1->step), TYPE_PRECISION (type));
1374       dstep = -dstep;
1375     }
1376 
1377   mpz_init (mstep);
1378   wi::to_mpz (dstep, mstep, UNSIGNED);
1379   mpz_neg (mstep, mstep);
1380   mpz_add_ui (mstep, mstep, 1);
1381 
1382   rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
1383 
1384   mpz_init (max);
1385   wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
1386   mpz_add (max, max, mstep);
1387   no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
1388 		   /* For pointers, only values lying inside a single object
1389 		      can be compared or manipulated by pointer arithmetics.
1390 		      Gcc in general does not allow or handle objects larger
1391 		      than half of the address space, hence the upper bound
1392 		      is satisfied for pointers.  */
1393 		   || POINTER_TYPE_P (type));
1394   mpz_clear (mstep);
1395   mpz_clear (max);
1396 
1397   if (rolls_p && no_overflow_p)
1398     return;
1399 
1400   type1 = type;
1401   if (POINTER_TYPE_P (type))
1402     type1 = sizetype;
1403 
1404   /* Now the hard part; we must formulate the assumption(s) as expressions, and
1405      we must be careful not to introduce overflow.  */
1406 
1407   if (integer_nonzerop (iv0->step))
1408     {
1409       diff = fold_build2 (MINUS_EXPR, type1,
1410 			  iv0->step, build_int_cst (type1, 1));
1411 
1412       /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
1413 	 0 address never belongs to any object, we can assume this for
1414 	 pointers.  */
1415       if (!POINTER_TYPE_P (type))
1416 	{
1417 	  bound = fold_build2 (PLUS_EXPR, type1,
1418 			       TYPE_MIN_VALUE (type), diff);
1419 	  assumption = fold_build2 (GE_EXPR, boolean_type_node,
1420 				    iv0->base, bound);
1421 	}
1422 
1423       /* And then we can compute iv0->base - diff, and compare it with
1424 	 iv1->base.  */
1425       mbzl = fold_build2 (MINUS_EXPR, type1,
1426 			  fold_convert (type1, iv0->base), diff);
1427       mbzr = fold_convert (type1, iv1->base);
1428     }
1429   else
1430     {
1431       diff = fold_build2 (PLUS_EXPR, type1,
1432 			  iv1->step, build_int_cst (type1, 1));
1433 
1434       if (!POINTER_TYPE_P (type))
1435 	{
1436 	  bound = fold_build2 (PLUS_EXPR, type1,
1437 			       TYPE_MAX_VALUE (type), diff);
1438 	  assumption = fold_build2 (LE_EXPR, boolean_type_node,
1439 				    iv1->base, bound);
1440 	}
1441 
1442       mbzl = fold_convert (type1, iv0->base);
1443       mbzr = fold_build2 (MINUS_EXPR, type1,
1444 			  fold_convert (type1, iv1->base), diff);
1445     }
1446 
1447   if (!integer_nonzerop (assumption))
1448     niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1449 				      niter->assumptions, assumption);
1450   if (!rolls_p)
1451     {
1452       mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1453       niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1454 					niter->may_be_zero, mbz);
1455     }
1456 }
1457 
1458 /* Determines number of iterations of loop whose ending condition
1459    is IV0 < IV1.  TYPE is the type of the iv.  The number of
1460    iterations is stored to NITER.  BNDS bounds the difference
1461    IV1->base - IV0->base.  EXIT_MUST_BE_TAKEN is true if we know
1462    that the exit must be taken eventually.  */
1463 
1464 static bool
number_of_iterations_lt(class loop * loop,tree type,affine_iv * iv0,affine_iv * iv1,class tree_niter_desc * niter,bool exit_must_be_taken,bounds * bnds)1465 number_of_iterations_lt (class loop *loop, tree type, affine_iv *iv0,
1466 			 affine_iv *iv1, class tree_niter_desc *niter,
1467 			 bool exit_must_be_taken, bounds *bnds)
1468 {
1469   tree niter_type = unsigned_type_for (type);
1470   tree delta, step, s;
1471   mpz_t mstep, tmp;
1472 
1473   if (integer_nonzerop (iv0->step))
1474     {
1475       niter->control = *iv0;
1476       niter->cmp = LT_EXPR;
1477       niter->bound = iv1->base;
1478     }
1479   else
1480     {
1481       niter->control = *iv1;
1482       niter->cmp = GT_EXPR;
1483       niter->bound = iv0->base;
1484     }
1485 
1486   delta = fold_build2 (MINUS_EXPR, niter_type,
1487 		       fold_convert (niter_type, iv1->base),
1488 		       fold_convert (niter_type, iv0->base));
1489 
1490   /* First handle the special case that the step is +-1.  */
1491   if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1492       || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1493     {
1494       /* for (i = iv0->base; i < iv1->base; i++)
1495 
1496 	 or
1497 
1498 	 for (i = iv1->base; i > iv0->base; i--).
1499 
1500 	 In both cases # of iterations is iv1->base - iv0->base, assuming that
1501 	 iv1->base >= iv0->base.
1502 
1503          First try to derive a lower bound on the value of
1504 	 iv1->base - iv0->base, computed in full precision.  If the difference
1505 	 is nonnegative, we are done, otherwise we must record the
1506 	 condition.  */
1507 
1508       if (mpz_sgn (bnds->below) < 0)
1509 	niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1510 					  iv1->base, iv0->base);
1511       niter->niter = delta;
1512       niter->max = widest_int::from (wi::from_mpz (niter_type, bnds->up, false),
1513 				     TYPE_SIGN (niter_type));
1514       niter->control.no_overflow = true;
1515       return true;
1516     }
1517 
1518   if (integer_nonzerop (iv0->step))
1519     step = fold_convert (niter_type, iv0->step);
1520   else
1521     step = fold_convert (niter_type,
1522 			 fold_build1 (NEGATE_EXPR, type, iv1->step));
1523 
1524   /* If we can determine the final value of the control iv exactly, we can
1525      transform the condition to != comparison.  In particular, this will be
1526      the case if DELTA is constant.  */
1527   if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1528 				     exit_must_be_taken, bnds))
1529     {
1530       affine_iv zps;
1531 
1532       zps.base = build_int_cst (niter_type, 0);
1533       zps.step = step;
1534       /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1535 	 zps does not overflow.  */
1536       zps.no_overflow = true;
1537 
1538       return number_of_iterations_ne (loop, type, &zps,
1539 				      delta, niter, true, bnds);
1540     }
1541 
1542   /* Make sure that the control iv does not overflow.  */
1543   if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1544     return false;
1545 
1546   /* We determine the number of iterations as (delta + step - 1) / step.  For
1547      this to work, we must know that iv1->base >= iv0->base - step + 1,
1548      otherwise the loop does not roll.  */
1549   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1550 
1551   s = fold_build2 (MINUS_EXPR, niter_type,
1552 		   step, build_int_cst (niter_type, 1));
1553   delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1554   niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1555 
1556   mpz_init (mstep);
1557   mpz_init (tmp);
1558   wi::to_mpz (wi::to_wide (step), mstep, UNSIGNED);
1559   mpz_add (tmp, bnds->up, mstep);
1560   mpz_sub_ui (tmp, tmp, 1);
1561   mpz_fdiv_q (tmp, tmp, mstep);
1562   niter->max = widest_int::from (wi::from_mpz (niter_type, tmp, false),
1563 				 TYPE_SIGN (niter_type));
1564   mpz_clear (mstep);
1565   mpz_clear (tmp);
1566 
1567   return true;
1568 }
1569 
1570 /* Determines number of iterations of loop whose ending condition
1571    is IV0 <= IV1.  TYPE is the type of the iv.  The number of
1572    iterations is stored to NITER.  EXIT_MUST_BE_TAKEN is true if
1573    we know that this condition must eventually become false (we derived this
1574    earlier, and possibly set NITER->assumptions to make sure this
1575    is the case).  BNDS bounds the difference IV1->base - IV0->base.  */
1576 
1577 static bool
number_of_iterations_le(class loop * loop,tree type,affine_iv * iv0,affine_iv * iv1,class tree_niter_desc * niter,bool exit_must_be_taken,bounds * bnds)1578 number_of_iterations_le (class loop *loop, tree type, affine_iv *iv0,
1579 			 affine_iv *iv1, class tree_niter_desc *niter,
1580 			 bool exit_must_be_taken, bounds *bnds)
1581 {
1582   tree assumption;
1583   tree type1 = type;
1584   if (POINTER_TYPE_P (type))
1585     type1 = sizetype;
1586 
1587   /* Say that IV0 is the control variable.  Then IV0 <= IV1 iff
1588      IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1589      value of the type.  This we must know anyway, since if it is
1590      equal to this value, the loop rolls forever.  We do not check
1591      this condition for pointer type ivs, as the code cannot rely on
1592      the object to that the pointer points being placed at the end of
1593      the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1594      not defined for pointers).  */
1595 
1596   if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1597     {
1598       if (integer_nonzerop (iv0->step))
1599 	assumption = fold_build2 (NE_EXPR, boolean_type_node,
1600 				  iv1->base, TYPE_MAX_VALUE (type));
1601       else
1602 	assumption = fold_build2 (NE_EXPR, boolean_type_node,
1603 				  iv0->base, TYPE_MIN_VALUE (type));
1604 
1605       if (integer_zerop (assumption))
1606 	return false;
1607       if (!integer_nonzerop (assumption))
1608 	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1609 					  niter->assumptions, assumption);
1610     }
1611 
1612   if (integer_nonzerop (iv0->step))
1613     {
1614       if (POINTER_TYPE_P (type))
1615 	iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1616       else
1617 	iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1618 				 build_int_cst (type1, 1));
1619     }
1620   else if (POINTER_TYPE_P (type))
1621     iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1622   else
1623     iv0->base = fold_build2 (MINUS_EXPR, type1,
1624 			     iv0->base, build_int_cst (type1, 1));
1625 
1626   bounds_add (bnds, 1, type1);
1627 
1628   return number_of_iterations_lt (loop, type, iv0, iv1, niter, exit_must_be_taken,
1629 				  bnds);
1630 }
1631 
1632 /* Dumps description of affine induction variable IV to FILE.  */
1633 
1634 static void
dump_affine_iv(FILE * file,affine_iv * iv)1635 dump_affine_iv (FILE *file, affine_iv *iv)
1636 {
1637   if (!integer_zerop (iv->step))
1638     fprintf (file, "[");
1639 
1640   print_generic_expr (dump_file, iv->base, TDF_SLIM);
1641 
1642   if (!integer_zerop (iv->step))
1643     {
1644       fprintf (file, ", + , ");
1645       print_generic_expr (dump_file, iv->step, TDF_SLIM);
1646       fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1647     }
1648 }
1649 
1650 /* Given exit condition IV0 CODE IV1 in TYPE, this function adjusts
1651    the condition for loop-until-wrap cases.  For example:
1652      (unsigned){8, -1}_loop < 10        => {0, 1} != 9
1653      10 < (unsigned){0, max - 7}_loop   => {0, 1} != 8
1654    Return true if condition is successfully adjusted.  */
1655 
1656 static bool
adjust_cond_for_loop_until_wrap(tree type,affine_iv * iv0,tree_code * code,affine_iv * iv1)1657 adjust_cond_for_loop_until_wrap (tree type, affine_iv *iv0, tree_code *code,
1658 				 affine_iv *iv1)
1659 {
1660   /* Only support simple cases for the moment.  */
1661   if (TREE_CODE (iv0->base) != INTEGER_CST
1662       || TREE_CODE (iv1->base) != INTEGER_CST)
1663     return false;
1664 
1665   tree niter_type = unsigned_type_for (type), high, low;
1666   /* Case: i-- < 10.  */
1667   if (integer_zerop (iv1->step))
1668     {
1669       /* TODO: Should handle case in which abs(step) != 1.  */
1670       if (!integer_minus_onep (iv0->step))
1671 	return false;
1672       /* Give up on infinite loop.  */
1673       if (*code == LE_EXPR
1674 	  && tree_int_cst_equal (iv1->base, TYPE_MAX_VALUE (type)))
1675 	return false;
1676       high = fold_build2 (PLUS_EXPR, niter_type,
1677 			  fold_convert (niter_type, iv0->base),
1678 			  build_int_cst (niter_type, 1));
1679       low = fold_convert (niter_type, TYPE_MIN_VALUE (type));
1680     }
1681   else if (integer_zerop (iv0->step))
1682     {
1683       /* TODO: Should handle case in which abs(step) != 1.  */
1684       if (!integer_onep (iv1->step))
1685 	return false;
1686       /* Give up on infinite loop.  */
1687       if (*code == LE_EXPR
1688 	  && tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)))
1689 	return false;
1690       high = fold_convert (niter_type, TYPE_MAX_VALUE (type));
1691       low = fold_build2 (MINUS_EXPR, niter_type,
1692 			 fold_convert (niter_type, iv1->base),
1693 			 build_int_cst (niter_type, 1));
1694     }
1695   else
1696     gcc_unreachable ();
1697 
1698   iv0->base = low;
1699   iv0->step = fold_convert (niter_type, integer_one_node);
1700   iv1->base = high;
1701   iv1->step = build_int_cst (niter_type, 0);
1702   *code = NE_EXPR;
1703   return true;
1704 }
1705 
1706 /* Determine the number of iterations according to condition (for staying
1707    inside loop) which compares two induction variables using comparison
1708    operator CODE.  The induction variable on left side of the comparison
1709    is IV0, the right-hand side is IV1.  Both induction variables must have
1710    type TYPE, which must be an integer or pointer type.  The steps of the
1711    ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1712 
1713    LOOP is the loop whose number of iterations we are determining.
1714 
1715    ONLY_EXIT is true if we are sure this is the only way the loop could be
1716    exited (including possibly non-returning function calls, exceptions, etc.)
1717    -- in this case we can use the information whether the control induction
1718    variables can overflow or not in a more efficient way.
1719 
1720    if EVERY_ITERATION is true, we know the test is executed on every iteration.
1721 
1722    The results (number of iterations and assumptions as described in
1723    comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1724    Returns false if it fails to determine number of iterations, true if it
1725    was determined (possibly with some assumptions).  */
1726 
1727 static bool
number_of_iterations_cond(class loop * loop,tree type,affine_iv * iv0,enum tree_code code,affine_iv * iv1,class tree_niter_desc * niter,bool only_exit,bool every_iteration)1728 number_of_iterations_cond (class loop *loop,
1729 			   tree type, affine_iv *iv0, enum tree_code code,
1730 			   affine_iv *iv1, class tree_niter_desc *niter,
1731 			   bool only_exit, bool every_iteration)
1732 {
1733   bool exit_must_be_taken = false, ret;
1734   bounds bnds;
1735 
1736   /* If the test is not executed every iteration, wrapping may make the test
1737      to pass again.
1738      TODO: the overflow case can be still used as unreliable estimate of upper
1739      bound.  But we have no API to pass it down to number of iterations code
1740      and, at present, it will not use it anyway.  */
1741   if (!every_iteration
1742       && (!iv0->no_overflow || !iv1->no_overflow
1743 	  || code == NE_EXPR || code == EQ_EXPR))
1744     return false;
1745 
1746   /* The meaning of these assumptions is this:
1747      if !assumptions
1748        then the rest of information does not have to be valid
1749      if may_be_zero then the loop does not roll, even if
1750        niter != 0.  */
1751   niter->assumptions = boolean_true_node;
1752   niter->may_be_zero = boolean_false_node;
1753   niter->niter = NULL_TREE;
1754   niter->max = 0;
1755   niter->bound = NULL_TREE;
1756   niter->cmp = ERROR_MARK;
1757 
1758   /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1759      the control variable is on lhs.  */
1760   if (code == GE_EXPR || code == GT_EXPR
1761       || (code == NE_EXPR && integer_zerop (iv0->step)))
1762     {
1763       std::swap (iv0, iv1);
1764       code = swap_tree_comparison (code);
1765     }
1766 
1767   if (POINTER_TYPE_P (type))
1768     {
1769       /* Comparison of pointers is undefined unless both iv0 and iv1 point
1770 	 to the same object.  If they do, the control variable cannot wrap
1771 	 (as wrap around the bounds of memory will never return a pointer
1772 	 that would be guaranteed to point to the same object, even if we
1773 	 avoid undefined behavior by casting to size_t and back).  */
1774       iv0->no_overflow = true;
1775       iv1->no_overflow = true;
1776     }
1777 
1778   /* If the control induction variable does not overflow and the only exit
1779      from the loop is the one that we analyze, we know it must be taken
1780      eventually.  */
1781   if (only_exit)
1782     {
1783       if (!integer_zerop (iv0->step) && iv0->no_overflow)
1784 	exit_must_be_taken = true;
1785       else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1786 	exit_must_be_taken = true;
1787     }
1788 
1789   /* We can handle cases which neither of the sides of the comparison is
1790      invariant:
1791 
1792        {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1793      as if:
1794        {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1795 
1796      provided that either below condition is satisfied:
1797 
1798        a) the test is NE_EXPR;
1799        b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
1800 
1801      This rarely occurs in practice, but it is simple enough to manage.  */
1802   if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1803     {
1804       tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1805       tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
1806 					   iv0->step, iv1->step);
1807 
1808       /* No need to check sign of the new step since below code takes care
1809 	 of this well.  */
1810       if (code != NE_EXPR
1811 	  && (TREE_CODE (step) != INTEGER_CST
1812 	      || !iv0->no_overflow || !iv1->no_overflow))
1813 	return false;
1814 
1815       iv0->step = step;
1816       if (!POINTER_TYPE_P (type))
1817 	iv0->no_overflow = false;
1818 
1819       iv1->step = build_int_cst (step_type, 0);
1820       iv1->no_overflow = true;
1821     }
1822 
1823   /* If the result of the comparison is a constant,  the loop is weird.  More
1824      precise handling would be possible, but the situation is not common enough
1825      to waste time on it.  */
1826   if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1827     return false;
1828 
1829   /* If the loop exits immediately, there is nothing to do.  */
1830   tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
1831   if (tem && integer_zerop (tem))
1832     {
1833       if (!every_iteration)
1834 	return false;
1835       niter->niter = build_int_cst (unsigned_type_for (type), 0);
1836       niter->max = 0;
1837       return true;
1838     }
1839 
1840   /* Handle special case loops: while (i-- < 10) and while (10 < i++) by
1841      adjusting iv0, iv1 and code.  */
1842   if (code != NE_EXPR
1843       && (tree_int_cst_sign_bit (iv0->step)
1844 	  || (!integer_zerop (iv1->step)
1845 	      && !tree_int_cst_sign_bit (iv1->step)))
1846       && !adjust_cond_for_loop_until_wrap (type, iv0, &code, iv1))
1847     return false;
1848 
1849   /* OK, now we know we have a senseful loop.  Handle several cases, depending
1850      on what comparison operator is used.  */
1851   bound_difference (loop, iv1->base, iv0->base, &bnds);
1852 
1853   if (dump_file && (dump_flags & TDF_DETAILS))
1854     {
1855       fprintf (dump_file,
1856 	       "Analyzing # of iterations of loop %d\n", loop->num);
1857 
1858       fprintf (dump_file, "  exit condition ");
1859       dump_affine_iv (dump_file, iv0);
1860       fprintf (dump_file, " %s ",
1861 	       code == NE_EXPR ? "!="
1862 	       : code == LT_EXPR ? "<"
1863 	       : "<=");
1864       dump_affine_iv (dump_file, iv1);
1865       fprintf (dump_file, "\n");
1866 
1867       fprintf (dump_file, "  bounds on difference of bases: ");
1868       mpz_out_str (dump_file, 10, bnds.below);
1869       fprintf (dump_file, " ... ");
1870       mpz_out_str (dump_file, 10, bnds.up);
1871       fprintf (dump_file, "\n");
1872     }
1873 
1874   switch (code)
1875     {
1876     case NE_EXPR:
1877       gcc_assert (integer_zerop (iv1->step));
1878       ret = number_of_iterations_ne (loop, type, iv0, iv1->base, niter,
1879 				     exit_must_be_taken, &bnds);
1880       break;
1881 
1882     case LT_EXPR:
1883       ret = number_of_iterations_lt (loop, type, iv0, iv1, niter,
1884 				     exit_must_be_taken, &bnds);
1885       break;
1886 
1887     case LE_EXPR:
1888       ret = number_of_iterations_le (loop, type, iv0, iv1, niter,
1889 				     exit_must_be_taken, &bnds);
1890       break;
1891 
1892     default:
1893       gcc_unreachable ();
1894     }
1895 
1896   mpz_clear (bnds.up);
1897   mpz_clear (bnds.below);
1898 
1899   if (dump_file && (dump_flags & TDF_DETAILS))
1900     {
1901       if (ret)
1902 	{
1903 	  fprintf (dump_file, "  result:\n");
1904 	  if (!integer_nonzerop (niter->assumptions))
1905 	    {
1906 	      fprintf (dump_file, "    under assumptions ");
1907 	      print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1908 	      fprintf (dump_file, "\n");
1909 	    }
1910 
1911 	  if (!integer_zerop (niter->may_be_zero))
1912 	    {
1913 	      fprintf (dump_file, "    zero if ");
1914 	      print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1915 	      fprintf (dump_file, "\n");
1916 	    }
1917 
1918 	  fprintf (dump_file, "    # of iterations ");
1919 	  print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1920 	  fprintf (dump_file, ", bounded by ");
1921 	  print_decu (niter->max, dump_file);
1922 	  fprintf (dump_file, "\n");
1923 	}
1924       else
1925 	fprintf (dump_file, "  failed\n\n");
1926     }
1927   return ret;
1928 }
1929 
1930 /* Substitute NEW_TREE for OLD in EXPR and fold the result.
1931    If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
1932    all SSA names are replaced with the result of calling the VALUEIZE
1933    function with the SSA name as argument.  */
1934 
1935 tree
simplify_replace_tree(tree expr,tree old,tree new_tree,tree (* valueize)(tree,void *),void * context,bool do_fold)1936 simplify_replace_tree (tree expr, tree old, tree new_tree,
1937 		       tree (*valueize) (tree, void*), void *context,
1938 		       bool do_fold)
1939 {
1940   unsigned i, n;
1941   tree ret = NULL_TREE, e, se;
1942 
1943   if (!expr)
1944     return NULL_TREE;
1945 
1946   /* Do not bother to replace constants.  */
1947   if (CONSTANT_CLASS_P (expr))
1948     return expr;
1949 
1950   if (valueize)
1951     {
1952       if (TREE_CODE (expr) == SSA_NAME)
1953 	{
1954 	  new_tree = valueize (expr, context);
1955 	  if (new_tree != expr)
1956 	    return new_tree;
1957 	}
1958     }
1959   else if (expr == old
1960 	   || operand_equal_p (expr, old, 0))
1961     return unshare_expr (new_tree);
1962 
1963   if (!EXPR_P (expr))
1964     return expr;
1965 
1966   n = TREE_OPERAND_LENGTH (expr);
1967   for (i = 0; i < n; i++)
1968     {
1969       e = TREE_OPERAND (expr, i);
1970       se = simplify_replace_tree (e, old, new_tree, valueize, context, do_fold);
1971       if (e == se)
1972 	continue;
1973 
1974       if (!ret)
1975 	ret = copy_node (expr);
1976 
1977       TREE_OPERAND (ret, i) = se;
1978     }
1979 
1980   return (ret ? (do_fold ? fold (ret) : ret) : expr);
1981 }
1982 
1983 /* Expand definitions of ssa names in EXPR as long as they are simple
1984    enough, and return the new expression.  If STOP is specified, stop
1985    expanding if EXPR equals to it.  */
1986 
1987 static tree
expand_simple_operations(tree expr,tree stop,hash_map<tree,tree> & cache)1988 expand_simple_operations (tree expr, tree stop, hash_map<tree, tree> &cache)
1989 {
1990   unsigned i, n;
1991   tree ret = NULL_TREE, e, ee, e1;
1992   enum tree_code code;
1993   gimple *stmt;
1994 
1995   if (expr == NULL_TREE)
1996     return expr;
1997 
1998   if (is_gimple_min_invariant (expr))
1999     return expr;
2000 
2001   code = TREE_CODE (expr);
2002   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2003     {
2004       n = TREE_OPERAND_LENGTH (expr);
2005       for (i = 0; i < n; i++)
2006 	{
2007 	  e = TREE_OPERAND (expr, i);
2008 	  /* SCEV analysis feeds us with a proper expression
2009 	     graph matching the SSA graph.  Avoid turning it
2010 	     into a tree here, thus handle tree sharing
2011 	     properly.
2012 	     ???  The SSA walk below still turns the SSA graph
2013 	     into a tree but until we find a testcase do not
2014 	     introduce additional tree sharing here.  */
2015 	  bool existed_p;
2016 	  tree &cee = cache.get_or_insert (e, &existed_p);
2017 	  if (existed_p)
2018 	    ee = cee;
2019 	  else
2020 	    {
2021 	      cee = e;
2022 	      ee = expand_simple_operations (e, stop, cache);
2023 	      if (ee != e)
2024 		*cache.get (e) = ee;
2025 	    }
2026 	  if (e == ee)
2027 	    continue;
2028 
2029 	  if (!ret)
2030 	    ret = copy_node (expr);
2031 
2032 	  TREE_OPERAND (ret, i) = ee;
2033 	}
2034 
2035       if (!ret)
2036 	return expr;
2037 
2038       fold_defer_overflow_warnings ();
2039       ret = fold (ret);
2040       fold_undefer_and_ignore_overflow_warnings ();
2041       return ret;
2042     }
2043 
2044   /* Stop if it's not ssa name or the one we don't want to expand.  */
2045   if (TREE_CODE (expr) != SSA_NAME || expr == stop)
2046     return expr;
2047 
2048   stmt = SSA_NAME_DEF_STMT (expr);
2049   if (gimple_code (stmt) == GIMPLE_PHI)
2050     {
2051       basic_block src, dest;
2052 
2053       if (gimple_phi_num_args (stmt) != 1)
2054 	return expr;
2055       e = PHI_ARG_DEF (stmt, 0);
2056 
2057       /* Avoid propagating through loop exit phi nodes, which
2058 	 could break loop-closed SSA form restrictions.  */
2059       dest = gimple_bb (stmt);
2060       src = single_pred (dest);
2061       if (TREE_CODE (e) == SSA_NAME
2062 	  && src->loop_father != dest->loop_father)
2063 	return expr;
2064 
2065       return expand_simple_operations (e, stop, cache);
2066     }
2067   if (gimple_code (stmt) != GIMPLE_ASSIGN)
2068     return expr;
2069 
2070   /* Avoid expanding to expressions that contain SSA names that need
2071      to take part in abnormal coalescing.  */
2072   ssa_op_iter iter;
2073   FOR_EACH_SSA_TREE_OPERAND (e, stmt, iter, SSA_OP_USE)
2074     if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e))
2075       return expr;
2076 
2077   e = gimple_assign_rhs1 (stmt);
2078   code = gimple_assign_rhs_code (stmt);
2079   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2080     {
2081       if (is_gimple_min_invariant (e))
2082 	return e;
2083 
2084       if (code == SSA_NAME)
2085 	return expand_simple_operations (e, stop, cache);
2086       else if (code == ADDR_EXPR)
2087 	{
2088 	  poly_int64 offset;
2089 	  tree base = get_addr_base_and_unit_offset (TREE_OPERAND (e, 0),
2090 						     &offset);
2091 	  if (base
2092 	      && TREE_CODE (base) == MEM_REF)
2093 	    {
2094 	      ee = expand_simple_operations (TREE_OPERAND (base, 0), stop,
2095 					     cache);
2096 	      return fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (expr), ee,
2097 				  wide_int_to_tree (sizetype,
2098 						    mem_ref_offset (base)
2099 						    + offset));
2100 	    }
2101 	}
2102 
2103       return expr;
2104     }
2105 
2106   switch (code)
2107     {
2108     CASE_CONVERT:
2109       /* Casts are simple.  */
2110       ee = expand_simple_operations (e, stop, cache);
2111       return fold_build1 (code, TREE_TYPE (expr), ee);
2112 
2113     case PLUS_EXPR:
2114     case MINUS_EXPR:
2115       if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr))
2116 	  && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr)))
2117 	return expr;
2118       /* Fallthru.  */
2119     case POINTER_PLUS_EXPR:
2120       /* And increments and decrements by a constant are simple.  */
2121       e1 = gimple_assign_rhs2 (stmt);
2122       if (!is_gimple_min_invariant (e1))
2123 	return expr;
2124 
2125       ee = expand_simple_operations (e, stop, cache);
2126       return fold_build2 (code, TREE_TYPE (expr), ee, e1);
2127 
2128     default:
2129       return expr;
2130     }
2131 }
2132 
2133 tree
expand_simple_operations(tree expr,tree stop)2134 expand_simple_operations (tree expr, tree stop)
2135 {
2136   hash_map<tree, tree> cache;
2137   return expand_simple_operations (expr, stop, cache);
2138 }
2139 
2140 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
2141    expression (or EXPR unchanged, if no simplification was possible).  */
2142 
2143 static tree
tree_simplify_using_condition_1(tree cond,tree expr)2144 tree_simplify_using_condition_1 (tree cond, tree expr)
2145 {
2146   bool changed;
2147   tree e, e0, e1, e2, notcond;
2148   enum tree_code code = TREE_CODE (expr);
2149 
2150   if (code == INTEGER_CST)
2151     return expr;
2152 
2153   if (code == TRUTH_OR_EXPR
2154       || code == TRUTH_AND_EXPR
2155       || code == COND_EXPR)
2156     {
2157       changed = false;
2158 
2159       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
2160       if (TREE_OPERAND (expr, 0) != e0)
2161 	changed = true;
2162 
2163       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
2164       if (TREE_OPERAND (expr, 1) != e1)
2165 	changed = true;
2166 
2167       if (code == COND_EXPR)
2168 	{
2169 	  e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
2170 	  if (TREE_OPERAND (expr, 2) != e2)
2171 	    changed = true;
2172 	}
2173       else
2174 	e2 = NULL_TREE;
2175 
2176       if (changed)
2177 	{
2178 	  if (code == COND_EXPR)
2179 	    expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
2180 	  else
2181 	    expr = fold_build2 (code, boolean_type_node, e0, e1);
2182 	}
2183 
2184       return expr;
2185     }
2186 
2187   /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2188      propagation, and vice versa.  Fold does not handle this, since it is
2189      considered too expensive.  */
2190   if (TREE_CODE (cond) == EQ_EXPR)
2191     {
2192       e0 = TREE_OPERAND (cond, 0);
2193       e1 = TREE_OPERAND (cond, 1);
2194 
2195       /* We know that e0 == e1.  Check whether we cannot simplify expr
2196 	 using this fact.  */
2197       e = simplify_replace_tree (expr, e0, e1);
2198       if (integer_zerop (e) || integer_nonzerop (e))
2199 	return e;
2200 
2201       e = simplify_replace_tree (expr, e1, e0);
2202       if (integer_zerop (e) || integer_nonzerop (e))
2203 	return e;
2204     }
2205   if (TREE_CODE (expr) == EQ_EXPR)
2206     {
2207       e0 = TREE_OPERAND (expr, 0);
2208       e1 = TREE_OPERAND (expr, 1);
2209 
2210       /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
2211       e = simplify_replace_tree (cond, e0, e1);
2212       if (integer_zerop (e))
2213 	return e;
2214       e = simplify_replace_tree (cond, e1, e0);
2215       if (integer_zerop (e))
2216 	return e;
2217     }
2218   if (TREE_CODE (expr) == NE_EXPR)
2219     {
2220       e0 = TREE_OPERAND (expr, 0);
2221       e1 = TREE_OPERAND (expr, 1);
2222 
2223       /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
2224       e = simplify_replace_tree (cond, e0, e1);
2225       if (integer_zerop (e))
2226 	return boolean_true_node;
2227       e = simplify_replace_tree (cond, e1, e0);
2228       if (integer_zerop (e))
2229 	return boolean_true_node;
2230     }
2231 
2232   /* Check whether COND ==> EXPR.  */
2233   notcond = invert_truthvalue (cond);
2234   e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, expr);
2235   if (e && integer_nonzerop (e))
2236     return e;
2237 
2238   /* Check whether COND ==> not EXPR.  */
2239   e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, expr);
2240   if (e && integer_zerop (e))
2241     return e;
2242 
2243   return expr;
2244 }
2245 
2246 /* Tries to simplify EXPR using the condition COND.  Returns the simplified
2247    expression (or EXPR unchanged, if no simplification was possible).
2248    Wrapper around tree_simplify_using_condition_1 that ensures that chains
2249    of simple operations in definitions of ssa names in COND are expanded,
2250    so that things like casts or incrementing the value of the bound before
2251    the loop do not cause us to fail.  */
2252 
2253 static tree
tree_simplify_using_condition(tree cond,tree expr)2254 tree_simplify_using_condition (tree cond, tree expr)
2255 {
2256   cond = expand_simple_operations (cond);
2257 
2258   return tree_simplify_using_condition_1 (cond, expr);
2259 }
2260 
2261 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2262    Returns the simplified expression (or EXPR unchanged, if no
2263    simplification was possible).  */
2264 
2265 tree
simplify_using_initial_conditions(class loop * loop,tree expr)2266 simplify_using_initial_conditions (class loop *loop, tree expr)
2267 {
2268   edge e;
2269   basic_block bb;
2270   gimple *stmt;
2271   tree cond, expanded, backup;
2272   int cnt = 0;
2273 
2274   if (TREE_CODE (expr) == INTEGER_CST)
2275     return expr;
2276 
2277   backup = expanded = expand_simple_operations (expr);
2278 
2279   /* Limit walking the dominators to avoid quadraticness in
2280      the number of BBs times the number of loops in degenerate
2281      cases.  */
2282   for (bb = loop->header;
2283        bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
2284        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
2285     {
2286       if (!single_pred_p (bb))
2287 	continue;
2288       e = single_pred_edge (bb);
2289 
2290       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
2291 	continue;
2292 
2293       stmt = last_stmt (e->src);
2294       cond = fold_build2 (gimple_cond_code (stmt),
2295 			  boolean_type_node,
2296 			  gimple_cond_lhs (stmt),
2297 			  gimple_cond_rhs (stmt));
2298       if (e->flags & EDGE_FALSE_VALUE)
2299 	cond = invert_truthvalue (cond);
2300       expanded = tree_simplify_using_condition (cond, expanded);
2301       /* Break if EXPR is simplified to const values.  */
2302       if (expanded
2303 	  && (integer_zerop (expanded) || integer_nonzerop (expanded)))
2304 	return expanded;
2305 
2306       ++cnt;
2307     }
2308 
2309   /* Return the original expression if no simplification is done.  */
2310   return operand_equal_p (backup, expanded, 0) ? expr : expanded;
2311 }
2312 
2313 /* Tries to simplify EXPR using the evolutions of the loop invariants
2314    in the superloops of LOOP.  Returns the simplified expression
2315    (or EXPR unchanged, if no simplification was possible).  */
2316 
2317 static tree
simplify_using_outer_evolutions(class loop * loop,tree expr)2318 simplify_using_outer_evolutions (class loop *loop, tree expr)
2319 {
2320   enum tree_code code = TREE_CODE (expr);
2321   bool changed;
2322   tree e, e0, e1, e2;
2323 
2324   if (is_gimple_min_invariant (expr))
2325     return expr;
2326 
2327   if (code == TRUTH_OR_EXPR
2328       || code == TRUTH_AND_EXPR
2329       || code == COND_EXPR)
2330     {
2331       changed = false;
2332 
2333       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
2334       if (TREE_OPERAND (expr, 0) != e0)
2335 	changed = true;
2336 
2337       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
2338       if (TREE_OPERAND (expr, 1) != e1)
2339 	changed = true;
2340 
2341       if (code == COND_EXPR)
2342 	{
2343 	  e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
2344 	  if (TREE_OPERAND (expr, 2) != e2)
2345 	    changed = true;
2346 	}
2347       else
2348 	e2 = NULL_TREE;
2349 
2350       if (changed)
2351 	{
2352 	  if (code == COND_EXPR)
2353 	    expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
2354 	  else
2355 	    expr = fold_build2 (code, boolean_type_node, e0, e1);
2356 	}
2357 
2358       return expr;
2359     }
2360 
2361   e = instantiate_parameters (loop, expr);
2362   if (is_gimple_min_invariant (e))
2363     return e;
2364 
2365   return expr;
2366 }
2367 
2368 /* Returns true if EXIT is the only possible exit from LOOP.  */
2369 
2370 bool
loop_only_exit_p(const class loop * loop,basic_block * body,const_edge exit)2371 loop_only_exit_p (const class loop *loop, basic_block *body, const_edge exit)
2372 {
2373   gimple_stmt_iterator bsi;
2374   unsigned i;
2375 
2376   if (exit != single_exit (loop))
2377     return false;
2378 
2379   for (i = 0; i < loop->num_nodes; i++)
2380     for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
2381       if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
2382 	return false;
2383 
2384   return true;
2385 }
2386 
2387 /* Stores description of number of iterations of LOOP derived from
2388    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some useful
2389    information could be derived (and fields of NITER have meaning described
2390    in comments at class tree_niter_desc declaration), false otherwise.
2391    When EVERY_ITERATION is true, only tests that are known to be executed
2392    every iteration are considered (i.e. only test that alone bounds the loop).
2393    If AT_STMT is not NULL, this function stores LOOP's condition statement in
2394    it when returning true.  */
2395 
2396 bool
number_of_iterations_exit_assumptions(class loop * loop,edge exit,class tree_niter_desc * niter,gcond ** at_stmt,bool every_iteration,basic_block * body)2397 number_of_iterations_exit_assumptions (class loop *loop, edge exit,
2398 				       class tree_niter_desc *niter,
2399 				       gcond **at_stmt, bool every_iteration,
2400 				       basic_block *body)
2401 {
2402   gimple *last;
2403   gcond *stmt;
2404   tree type;
2405   tree op0, op1;
2406   enum tree_code code;
2407   affine_iv iv0, iv1;
2408   bool safe;
2409 
2410   /* The condition at a fake exit (if it exists) does not control its
2411      execution.  */
2412   if (exit->flags & EDGE_FAKE)
2413     return false;
2414 
2415   /* Nothing to analyze if the loop is known to be infinite.  */
2416   if (loop_constraint_set_p (loop, LOOP_C_INFINITE))
2417     return false;
2418 
2419   safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
2420 
2421   if (every_iteration && !safe)
2422     return false;
2423 
2424   niter->assumptions = boolean_false_node;
2425   niter->control.base = NULL_TREE;
2426   niter->control.step = NULL_TREE;
2427   niter->control.no_overflow = false;
2428   last = last_stmt (exit->src);
2429   if (!last)
2430     return false;
2431   stmt = dyn_cast <gcond *> (last);
2432   if (!stmt)
2433     return false;
2434 
2435   /* We want the condition for staying inside loop.  */
2436   code = gimple_cond_code (stmt);
2437   if (exit->flags & EDGE_TRUE_VALUE)
2438     code = invert_tree_comparison (code, false);
2439 
2440   switch (code)
2441     {
2442     case GT_EXPR:
2443     case GE_EXPR:
2444     case LT_EXPR:
2445     case LE_EXPR:
2446     case NE_EXPR:
2447       break;
2448 
2449     default:
2450       return false;
2451     }
2452 
2453   op0 = gimple_cond_lhs (stmt);
2454   op1 = gimple_cond_rhs (stmt);
2455   type = TREE_TYPE (op0);
2456 
2457   if (TREE_CODE (type) != INTEGER_TYPE
2458       && !POINTER_TYPE_P (type))
2459     return false;
2460 
2461   tree iv0_niters = NULL_TREE;
2462   if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
2463 			      op0, &iv0, safe ? &iv0_niters : NULL, false))
2464     return number_of_iterations_popcount (loop, exit, code, niter);
2465   tree iv1_niters = NULL_TREE;
2466   if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
2467 			      op1, &iv1, safe ? &iv1_niters : NULL, false))
2468     return false;
2469   /* Give up on complicated case.  */
2470   if (iv0_niters && iv1_niters)
2471     return false;
2472 
2473   /* We don't want to see undefined signed overflow warnings while
2474      computing the number of iterations.  */
2475   fold_defer_overflow_warnings ();
2476 
2477   iv0.base = expand_simple_operations (iv0.base);
2478   iv1.base = expand_simple_operations (iv1.base);
2479   bool body_from_caller = true;
2480   if (!body)
2481     {
2482       body = get_loop_body (loop);
2483       body_from_caller = false;
2484     }
2485   bool only_exit_p = loop_only_exit_p (loop, body, exit);
2486   if (!body_from_caller)
2487     free (body);
2488   if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
2489 				  only_exit_p, safe))
2490     {
2491       fold_undefer_and_ignore_overflow_warnings ();
2492       return false;
2493     }
2494 
2495   /* Incorporate additional assumption implied by control iv.  */
2496   tree iv_niters = iv0_niters ? iv0_niters : iv1_niters;
2497   if (iv_niters)
2498     {
2499       tree assumption = fold_build2 (LE_EXPR, boolean_type_node, niter->niter,
2500 				     fold_convert (TREE_TYPE (niter->niter),
2501 						   iv_niters));
2502 
2503       if (!integer_nonzerop (assumption))
2504 	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2505 					  niter->assumptions, assumption);
2506 
2507       /* Refine upper bound if possible.  */
2508       if (TREE_CODE (iv_niters) == INTEGER_CST
2509 	  && niter->max > wi::to_widest (iv_niters))
2510 	niter->max = wi::to_widest (iv_niters);
2511     }
2512 
2513   /* There is no assumptions if the loop is known to be finite.  */
2514   if (!integer_zerop (niter->assumptions)
2515       && loop_constraint_set_p (loop, LOOP_C_FINITE))
2516     niter->assumptions = boolean_true_node;
2517 
2518   if (optimize >= 3)
2519     {
2520       niter->assumptions = simplify_using_outer_evolutions (loop,
2521 							    niter->assumptions);
2522       niter->may_be_zero = simplify_using_outer_evolutions (loop,
2523 							    niter->may_be_zero);
2524       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
2525     }
2526 
2527   niter->assumptions
2528 	  = simplify_using_initial_conditions (loop,
2529 					       niter->assumptions);
2530   niter->may_be_zero
2531 	  = simplify_using_initial_conditions (loop,
2532 					       niter->may_be_zero);
2533 
2534   fold_undefer_and_ignore_overflow_warnings ();
2535 
2536   /* If NITER has simplified into a constant, update MAX.  */
2537   if (TREE_CODE (niter->niter) == INTEGER_CST)
2538     niter->max = wi::to_widest (niter->niter);
2539 
2540   if (at_stmt)
2541     *at_stmt = stmt;
2542 
2543   return (!integer_zerop (niter->assumptions));
2544 }
2545 
2546 
2547 /* Utility function to check if OP is defined by a stmt
2548    that is a val - 1.  */
2549 
2550 static bool
ssa_defined_by_minus_one_stmt_p(tree op,tree val)2551 ssa_defined_by_minus_one_stmt_p (tree op, tree val)
2552 {
2553   gimple *stmt;
2554   return (TREE_CODE (op) == SSA_NAME
2555 	  && (stmt = SSA_NAME_DEF_STMT (op))
2556 	  && is_gimple_assign (stmt)
2557 	  && (gimple_assign_rhs_code (stmt) == PLUS_EXPR)
2558 	  && val == gimple_assign_rhs1 (stmt)
2559 	  && integer_minus_onep (gimple_assign_rhs2 (stmt)));
2560 }
2561 
2562 
2563 /* See if LOOP is a popcout implementation, determine NITER for the loop
2564 
2565    We match:
2566    <bb 2>
2567    goto <bb 4>
2568 
2569    <bb 3>
2570    _1 = b_11 + -1
2571    b_6 = _1 & b_11
2572 
2573    <bb 4>
2574    b_11 = PHI <b_5(D)(2), b_6(3)>
2575 
2576    exit block
2577    if (b_11 != 0)
2578 	goto <bb 3>
2579    else
2580 	goto <bb 5>
2581 
2582    OR we match copy-header version:
2583    if (b_5 != 0)
2584 	goto <bb 3>
2585    else
2586 	goto <bb 4>
2587 
2588    <bb 3>
2589    b_11 = PHI <b_5(2), b_6(3)>
2590    _1 = b_11 + -1
2591    b_6 = _1 & b_11
2592 
2593    exit block
2594    if (b_6 != 0)
2595 	goto <bb 3>
2596    else
2597 	goto <bb 4>
2598 
2599    If popcount pattern, update NITER accordingly.
2600    i.e., set NITER to  __builtin_popcount (b)
2601    return true if we did, false otherwise.
2602 
2603  */
2604 
2605 static bool
number_of_iterations_popcount(loop_p loop,edge exit,enum tree_code code,class tree_niter_desc * niter)2606 number_of_iterations_popcount (loop_p loop, edge exit,
2607 			       enum tree_code code,
2608 			       class tree_niter_desc *niter)
2609 {
2610   bool adjust = true;
2611   tree iter;
2612   HOST_WIDE_INT max;
2613   adjust = true;
2614   tree fn = NULL_TREE;
2615 
2616   /* Check loop terminating branch is like
2617      if (b != 0).  */
2618   gimple *stmt = last_stmt (exit->src);
2619   if (!stmt
2620       || gimple_code (stmt) != GIMPLE_COND
2621       || code != NE_EXPR
2622       || !integer_zerop (gimple_cond_rhs (stmt))
2623       || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME)
2624     return false;
2625 
2626   gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2627 
2628   /* Depending on copy-header is performed, feeding PHI stmts might be in
2629      the loop header or loop latch, handle this.  */
2630   if (gimple_code (and_stmt) == GIMPLE_PHI
2631       && gimple_bb (and_stmt) == loop->header
2632       && gimple_phi_num_args (and_stmt) == 2
2633       && (TREE_CODE (gimple_phi_arg_def (and_stmt,
2634 					 loop_latch_edge (loop)->dest_idx))
2635 	  == SSA_NAME))
2636     {
2637       /* SSA used in exit condition is defined by PHI stmt
2638 	b_11 = PHI <b_5(D)(2), b_6(3)>
2639 	from the PHI stmt, get the and_stmt
2640 	b_6 = _1 & b_11.  */
2641       tree t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx);
2642       and_stmt = SSA_NAME_DEF_STMT (t);
2643       adjust = false;
2644     }
2645 
2646   /* Make sure it is indeed an and stmt (b_6 = _1 & b_11).  */
2647   if (!is_gimple_assign (and_stmt)
2648       || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR)
2649     return false;
2650 
2651   tree b_11 = gimple_assign_rhs1 (and_stmt);
2652   tree _1 = gimple_assign_rhs2 (and_stmt);
2653 
2654   /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1).
2655      Also make sure that b_11 is the same in and_stmt and _1 defining stmt.
2656      Also canonicalize if _1 and _b11 are revrsed.  */
2657   if (ssa_defined_by_minus_one_stmt_p (b_11, _1))
2658     std::swap (b_11, _1);
2659   else if (ssa_defined_by_minus_one_stmt_p (_1, b_11))
2660     ;
2661   else
2662     return false;
2663   /* Check the recurrence:
2664    ... = PHI <b_5(2), b_6(3)>.  */
2665   gimple *phi = SSA_NAME_DEF_STMT (b_11);
2666   if (gimple_code (phi) != GIMPLE_PHI
2667       || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
2668       || (gimple_assign_lhs (and_stmt)
2669 	  != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)))
2670     return false;
2671 
2672   /* We found a match. Get the corresponding popcount builtin.  */
2673   tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
2674   if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION (integer_type_node))
2675     fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
2676   else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION
2677 	   (long_integer_type_node))
2678     fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL);
2679   else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION
2680 	   (long_long_integer_type_node))
2681     fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL);
2682 
2683   /* ??? Support promoting char/short to int.  */
2684   if (!fn)
2685     return false;
2686 
2687   /* Update NITER params accordingly  */
2688   tree utype = unsigned_type_for (TREE_TYPE (src));
2689   src = fold_convert (utype, src);
2690   tree call = fold_convert (utype, build_call_expr (fn, 1, src));
2691   if (adjust)
2692     iter = fold_build2 (MINUS_EXPR, utype,
2693 			call,
2694 			build_int_cst (utype, 1));
2695   else
2696     iter = call;
2697 
2698   if (TREE_CODE (call) == INTEGER_CST)
2699     max = tree_to_uhwi (call);
2700   else
2701     max = TYPE_PRECISION (TREE_TYPE (src));
2702   if (adjust)
2703     max = max - 1;
2704 
2705   niter->niter = iter;
2706   niter->assumptions = boolean_true_node;
2707 
2708   if (adjust)
2709     {
2710       tree may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
2711 				      build_zero_cst
2712 				      (TREE_TYPE (src)));
2713       niter->may_be_zero =
2714 	simplify_using_initial_conditions (loop, may_be_zero);
2715     }
2716   else
2717     niter->may_be_zero = boolean_false_node;
2718 
2719   niter->max = max;
2720   niter->bound = NULL_TREE;
2721   niter->cmp = ERROR_MARK;
2722   return true;
2723 }
2724 
2725 
2726 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
2727    the niter information holds unconditionally.  */
2728 
2729 bool
number_of_iterations_exit(class loop * loop,edge exit,class tree_niter_desc * niter,bool warn,bool every_iteration,basic_block * body)2730 number_of_iterations_exit (class loop *loop, edge exit,
2731 			   class tree_niter_desc *niter,
2732 			   bool warn, bool every_iteration,
2733 			   basic_block *body)
2734 {
2735   gcond *stmt;
2736   if (!number_of_iterations_exit_assumptions (loop, exit, niter,
2737 					      &stmt, every_iteration, body))
2738     return false;
2739 
2740   if (integer_nonzerop (niter->assumptions))
2741     return true;
2742 
2743   if (warn && dump_enabled_p ())
2744     dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
2745 		     "missed loop optimization: niters analysis ends up "
2746 		     "with assumptions.\n");
2747 
2748   return false;
2749 }
2750 
2751 /* Try to determine the number of iterations of LOOP.  If we succeed,
2752    expression giving number of iterations is returned and *EXIT is
2753    set to the edge from that the information is obtained.  Otherwise
2754    chrec_dont_know is returned.  */
2755 
2756 tree
find_loop_niter(class loop * loop,edge * exit)2757 find_loop_niter (class loop *loop, edge *exit)
2758 {
2759   unsigned i;
2760   vec<edge> exits = get_loop_exit_edges (loop);
2761   edge ex;
2762   tree niter = NULL_TREE, aniter;
2763   class tree_niter_desc desc;
2764 
2765   *exit = NULL;
2766   FOR_EACH_VEC_ELT (exits, i, ex)
2767     {
2768       if (!number_of_iterations_exit (loop, ex, &desc, false))
2769 	continue;
2770 
2771       if (integer_nonzerop (desc.may_be_zero))
2772 	{
2773 	  /* We exit in the first iteration through this exit.
2774 	     We won't find anything better.  */
2775 	  niter = build_int_cst (unsigned_type_node, 0);
2776 	  *exit = ex;
2777 	  break;
2778 	}
2779 
2780       if (!integer_zerop (desc.may_be_zero))
2781 	continue;
2782 
2783       aniter = desc.niter;
2784 
2785       if (!niter)
2786 	{
2787 	  /* Nothing recorded yet.  */
2788 	  niter = aniter;
2789 	  *exit = ex;
2790 	  continue;
2791 	}
2792 
2793       /* Prefer constants, the lower the better.  */
2794       if (TREE_CODE (aniter) != INTEGER_CST)
2795 	continue;
2796 
2797       if (TREE_CODE (niter) != INTEGER_CST)
2798 	{
2799 	  niter = aniter;
2800 	  *exit = ex;
2801 	  continue;
2802 	}
2803 
2804       if (tree_int_cst_lt (aniter, niter))
2805 	{
2806 	  niter = aniter;
2807 	  *exit = ex;
2808 	  continue;
2809 	}
2810     }
2811   exits.release ();
2812 
2813   return niter ? niter : chrec_dont_know;
2814 }
2815 
2816 /* Return true if loop is known to have bounded number of iterations.  */
2817 
2818 bool
finite_loop_p(class loop * loop)2819 finite_loop_p (class loop *loop)
2820 {
2821   widest_int nit;
2822   int flags;
2823 
2824   flags = flags_from_decl_or_type (current_function_decl);
2825   if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
2826     {
2827       if (dump_file && (dump_flags & TDF_DETAILS))
2828 	fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2829 		 loop->num);
2830       return true;
2831     }
2832 
2833   if (loop->any_upper_bound
2834       || max_loop_iterations (loop, &nit))
2835     {
2836       if (dump_file && (dump_flags & TDF_DETAILS))
2837 	fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n",
2838 		 loop->num);
2839       return true;
2840     }
2841 
2842   if (loop->finite_p)
2843     {
2844       unsigned i;
2845       vec<edge> exits = get_loop_exit_edges (loop);
2846       edge ex;
2847 
2848       /* If the loop has a normal exit, we can assume it will terminate.  */
2849       FOR_EACH_VEC_ELT (exits, i, ex)
2850 	if (!(ex->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_FAKE)))
2851 	  {
2852 	    exits.release ();
2853 	    if (dump_file)
2854 	      fprintf (dump_file, "Assume loop %i to be finite: it has an exit "
2855 		       "and -ffinite-loops is on.\n", loop->num);
2856 	    return true;
2857 	  }
2858 
2859       exits.release ();
2860     }
2861 
2862   return false;
2863 }
2864 
2865 /*
2866 
2867    Analysis of a number of iterations of a loop by a brute-force evaluation.
2868 
2869 */
2870 
2871 /* Bound on the number of iterations we try to evaluate.  */
2872 
2873 #define MAX_ITERATIONS_TO_TRACK \
2874   ((unsigned) param_max_iterations_to_track)
2875 
2876 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2877    result by a chain of operations such that all but exactly one of their
2878    operands are constants.  */
2879 
2880 static gphi *
chain_of_csts_start(class loop * loop,tree x)2881 chain_of_csts_start (class loop *loop, tree x)
2882 {
2883   gimple *stmt = SSA_NAME_DEF_STMT (x);
2884   tree use;
2885   basic_block bb = gimple_bb (stmt);
2886   enum tree_code code;
2887 
2888   if (!bb
2889       || !flow_bb_inside_loop_p (loop, bb))
2890     return NULL;
2891 
2892   if (gimple_code (stmt) == GIMPLE_PHI)
2893     {
2894       if (bb == loop->header)
2895 	return as_a <gphi *> (stmt);
2896 
2897       return NULL;
2898     }
2899 
2900   if (gimple_code (stmt) != GIMPLE_ASSIGN
2901       || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS)
2902     return NULL;
2903 
2904   code = gimple_assign_rhs_code (stmt);
2905   if (gimple_references_memory_p (stmt)
2906       || TREE_CODE_CLASS (code) == tcc_reference
2907       || (code == ADDR_EXPR
2908 	  && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2909     return NULL;
2910 
2911   use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2912   if (use == NULL_TREE)
2913     return NULL;
2914 
2915   return chain_of_csts_start (loop, use);
2916 }
2917 
2918 /* Determines whether the expression X is derived from a result of a phi node
2919    in header of LOOP such that
2920 
2921    * the derivation of X consists only from operations with constants
2922    * the initial value of the phi node is constant
2923    * the value of the phi node in the next iteration can be derived from the
2924      value in the current iteration by a chain of operations with constants,
2925      or is also a constant
2926 
2927    If such phi node exists, it is returned, otherwise NULL is returned.  */
2928 
2929 static gphi *
get_base_for(class loop * loop,tree x)2930 get_base_for (class loop *loop, tree x)
2931 {
2932   gphi *phi;
2933   tree init, next;
2934 
2935   if (is_gimple_min_invariant (x))
2936     return NULL;
2937 
2938   phi = chain_of_csts_start (loop, x);
2939   if (!phi)
2940     return NULL;
2941 
2942   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2943   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2944 
2945   if (!is_gimple_min_invariant (init))
2946     return NULL;
2947 
2948   if (TREE_CODE (next) == SSA_NAME
2949       && chain_of_csts_start (loop, next) != phi)
2950     return NULL;
2951 
2952   return phi;
2953 }
2954 
2955 /* Given an expression X, then
2956 
2957    * if X is NULL_TREE, we return the constant BASE.
2958    * if X is a constant, we return the constant X.
2959    * otherwise X is a SSA name, whose value in the considered loop is derived
2960      by a chain of operations with constant from a result of a phi node in
2961      the header of the loop.  Then we return value of X when the value of the
2962      result of this phi node is given by the constant BASE.  */
2963 
2964 static tree
get_val_for(tree x,tree base)2965 get_val_for (tree x, tree base)
2966 {
2967   gimple *stmt;
2968 
2969   gcc_checking_assert (is_gimple_min_invariant (base));
2970 
2971   if (!x)
2972     return base;
2973   else if (is_gimple_min_invariant (x))
2974     return x;
2975 
2976   stmt = SSA_NAME_DEF_STMT (x);
2977   if (gimple_code (stmt) == GIMPLE_PHI)
2978     return base;
2979 
2980   gcc_checking_assert (is_gimple_assign (stmt));
2981 
2982   /* STMT must be either an assignment of a single SSA name or an
2983      expression involving an SSA name and a constant.  Try to fold that
2984      expression using the value for the SSA name.  */
2985   if (gimple_assign_ssa_name_copy_p (stmt))
2986     return get_val_for (gimple_assign_rhs1 (stmt), base);
2987   else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2988 	   && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2989     return fold_build1 (gimple_assign_rhs_code (stmt),
2990 			gimple_expr_type (stmt),
2991 			get_val_for (gimple_assign_rhs1 (stmt), base));
2992   else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2993     {
2994       tree rhs1 = gimple_assign_rhs1 (stmt);
2995       tree rhs2 = gimple_assign_rhs2 (stmt);
2996       if (TREE_CODE (rhs1) == SSA_NAME)
2997 	rhs1 = get_val_for (rhs1, base);
2998       else if (TREE_CODE (rhs2) == SSA_NAME)
2999 	rhs2 = get_val_for (rhs2, base);
3000       else
3001 	gcc_unreachable ();
3002       return fold_build2 (gimple_assign_rhs_code (stmt),
3003 			  gimple_expr_type (stmt), rhs1, rhs2);
3004     }
3005   else
3006     gcc_unreachable ();
3007 }
3008 
3009 
3010 /* Tries to count the number of iterations of LOOP till it exits by EXIT
3011    by brute force -- i.e. by determining the value of the operands of the
3012    condition at EXIT in first few iterations of the loop (assuming that
3013    these values are constant) and determining the first one in that the
3014    condition is not satisfied.  Returns the constant giving the number
3015    of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
3016 
3017 tree
loop_niter_by_eval(class loop * loop,edge exit)3018 loop_niter_by_eval (class loop *loop, edge exit)
3019 {
3020   tree acnd;
3021   tree op[2], val[2], next[2], aval[2];
3022   gphi *phi;
3023   gimple *cond;
3024   unsigned i, j;
3025   enum tree_code cmp;
3026 
3027   cond = last_stmt (exit->src);
3028   if (!cond || gimple_code (cond) != GIMPLE_COND)
3029     return chrec_dont_know;
3030 
3031   cmp = gimple_cond_code (cond);
3032   if (exit->flags & EDGE_TRUE_VALUE)
3033     cmp = invert_tree_comparison (cmp, false);
3034 
3035   switch (cmp)
3036     {
3037     case EQ_EXPR:
3038     case NE_EXPR:
3039     case GT_EXPR:
3040     case GE_EXPR:
3041     case LT_EXPR:
3042     case LE_EXPR:
3043       op[0] = gimple_cond_lhs (cond);
3044       op[1] = gimple_cond_rhs (cond);
3045       break;
3046 
3047     default:
3048       return chrec_dont_know;
3049     }
3050 
3051   for (j = 0; j < 2; j++)
3052     {
3053       if (is_gimple_min_invariant (op[j]))
3054 	{
3055 	  val[j] = op[j];
3056 	  next[j] = NULL_TREE;
3057 	  op[j] = NULL_TREE;
3058 	}
3059       else
3060 	{
3061 	  phi = get_base_for (loop, op[j]);
3062 	  if (!phi)
3063 	    return chrec_dont_know;
3064 	  val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
3065 	  next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3066 	}
3067     }
3068 
3069   /* Don't issue signed overflow warnings.  */
3070   fold_defer_overflow_warnings ();
3071 
3072   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
3073     {
3074       for (j = 0; j < 2; j++)
3075 	aval[j] = get_val_for (op[j], val[j]);
3076 
3077       acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
3078       if (acnd && integer_zerop (acnd))
3079 	{
3080 	  fold_undefer_and_ignore_overflow_warnings ();
3081 	  if (dump_file && (dump_flags & TDF_DETAILS))
3082 	    fprintf (dump_file,
3083 		     "Proved that loop %d iterates %d times using brute force.\n",
3084 		     loop->num, i);
3085 	  return build_int_cst (unsigned_type_node, i);
3086 	}
3087 
3088       for (j = 0; j < 2; j++)
3089 	{
3090 	  aval[j] = val[j];
3091 	  val[j] = get_val_for (next[j], val[j]);
3092 	  if (!is_gimple_min_invariant (val[j]))
3093 	    {
3094 	      fold_undefer_and_ignore_overflow_warnings ();
3095 	      return chrec_dont_know;
3096 	    }
3097 	}
3098 
3099       /* If the next iteration would use the same base values
3100 	 as the current one, there is no point looping further,
3101 	 all following iterations will be the same as this one.  */
3102       if (val[0] == aval[0] && val[1] == aval[1])
3103 	break;
3104     }
3105 
3106   fold_undefer_and_ignore_overflow_warnings ();
3107 
3108   return chrec_dont_know;
3109 }
3110 
3111 /* Finds the exit of the LOOP by that the loop exits after a constant
3112    number of iterations and stores the exit edge to *EXIT.  The constant
3113    giving the number of iterations of LOOP is returned.  The number of
3114    iterations is determined using loop_niter_by_eval (i.e. by brute force
3115    evaluation).  If we are unable to find the exit for that loop_niter_by_eval
3116    determines the number of iterations, chrec_dont_know is returned.  */
3117 
3118 tree
find_loop_niter_by_eval(class loop * loop,edge * exit)3119 find_loop_niter_by_eval (class loop *loop, edge *exit)
3120 {
3121   unsigned i;
3122   vec<edge> exits = get_loop_exit_edges (loop);
3123   edge ex;
3124   tree niter = NULL_TREE, aniter;
3125 
3126   *exit = NULL;
3127 
3128   /* Loops with multiple exits are expensive to handle and less important.  */
3129   if (!flag_expensive_optimizations
3130       && exits.length () > 1)
3131     {
3132       exits.release ();
3133       return chrec_dont_know;
3134     }
3135 
3136   FOR_EACH_VEC_ELT (exits, i, ex)
3137     {
3138       if (!just_once_each_iteration_p (loop, ex->src))
3139 	continue;
3140 
3141       aniter = loop_niter_by_eval (loop, ex);
3142       if (chrec_contains_undetermined (aniter))
3143 	continue;
3144 
3145       if (niter
3146 	  && !tree_int_cst_lt (aniter, niter))
3147 	continue;
3148 
3149       niter = aniter;
3150       *exit = ex;
3151     }
3152   exits.release ();
3153 
3154   return niter ? niter : chrec_dont_know;
3155 }
3156 
3157 /*
3158 
3159    Analysis of upper bounds on number of iterations of a loop.
3160 
3161 */
3162 
3163 static widest_int derive_constant_upper_bound_ops (tree, tree,
3164 						   enum tree_code, tree);
3165 
3166 /* Returns a constant upper bound on the value of the right-hand side of
3167    an assignment statement STMT.  */
3168 
3169 static widest_int
derive_constant_upper_bound_assign(gimple * stmt)3170 derive_constant_upper_bound_assign (gimple *stmt)
3171 {
3172   enum tree_code code = gimple_assign_rhs_code (stmt);
3173   tree op0 = gimple_assign_rhs1 (stmt);
3174   tree op1 = gimple_assign_rhs2 (stmt);
3175 
3176   return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
3177 					  op0, code, op1);
3178 }
3179 
3180 /* Returns a constant upper bound on the value of expression VAL.  VAL
3181    is considered to be unsigned.  If its type is signed, its value must
3182    be nonnegative.  */
3183 
3184 static widest_int
derive_constant_upper_bound(tree val)3185 derive_constant_upper_bound (tree val)
3186 {
3187   enum tree_code code;
3188   tree op0, op1, op2;
3189 
3190   extract_ops_from_tree (val, &code, &op0, &op1, &op2);
3191   return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
3192 }
3193 
3194 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3195    whose type is TYPE.  The expression is considered to be unsigned.  If
3196    its type is signed, its value must be nonnegative.  */
3197 
3198 static widest_int
derive_constant_upper_bound_ops(tree type,tree op0,enum tree_code code,tree op1)3199 derive_constant_upper_bound_ops (tree type, tree op0,
3200 				 enum tree_code code, tree op1)
3201 {
3202   tree subtype, maxt;
3203   widest_int bnd, max, cst;
3204   gimple *stmt;
3205 
3206   if (INTEGRAL_TYPE_P (type))
3207     maxt = TYPE_MAX_VALUE (type);
3208   else
3209     maxt = upper_bound_in_type (type, type);
3210 
3211   max = wi::to_widest (maxt);
3212 
3213   switch (code)
3214     {
3215     case INTEGER_CST:
3216       return wi::to_widest (op0);
3217 
3218     CASE_CONVERT:
3219       subtype = TREE_TYPE (op0);
3220       if (!TYPE_UNSIGNED (subtype)
3221 	  /* If TYPE is also signed, the fact that VAL is nonnegative implies
3222 	     that OP0 is nonnegative.  */
3223 	  && TYPE_UNSIGNED (type)
3224 	  && !tree_expr_nonnegative_p (op0))
3225 	{
3226 	  /* If we cannot prove that the casted expression is nonnegative,
3227 	     we cannot establish more useful upper bound than the precision
3228 	     of the type gives us.  */
3229 	  return max;
3230 	}
3231 
3232       /* We now know that op0 is an nonnegative value.  Try deriving an upper
3233 	 bound for it.  */
3234       bnd = derive_constant_upper_bound (op0);
3235 
3236       /* If the bound does not fit in TYPE, max. value of TYPE could be
3237 	 attained.  */
3238       if (wi::ltu_p (max, bnd))
3239 	return max;
3240 
3241       return bnd;
3242 
3243     case PLUS_EXPR:
3244     case POINTER_PLUS_EXPR:
3245     case MINUS_EXPR:
3246       if (TREE_CODE (op1) != INTEGER_CST
3247 	  || !tree_expr_nonnegative_p (op0))
3248 	return max;
3249 
3250       /* Canonicalize to OP0 - CST.  Consider CST to be signed, in order to
3251 	 choose the most logical way how to treat this constant regardless
3252 	 of the signedness of the type.  */
3253       cst = wi::sext (wi::to_widest (op1), TYPE_PRECISION (type));
3254       if (code != MINUS_EXPR)
3255 	cst = -cst;
3256 
3257       bnd = derive_constant_upper_bound (op0);
3258 
3259       if (wi::neg_p (cst))
3260 	{
3261 	  cst = -cst;
3262 	  /* Avoid CST == 0x80000...  */
3263 	  if (wi::neg_p (cst))
3264 	    return max;
3265 
3266 	  /* OP0 + CST.  We need to check that
3267 	     BND <= MAX (type) - CST.  */
3268 
3269 	  widest_int mmax = max - cst;
3270 	  if (wi::leu_p (bnd, mmax))
3271 	    return max;
3272 
3273 	  return bnd + cst;
3274 	}
3275       else
3276 	{
3277 	  /* OP0 - CST, where CST >= 0.
3278 
3279 	     If TYPE is signed, we have already verified that OP0 >= 0, and we
3280 	     know that the result is nonnegative.  This implies that
3281 	     VAL <= BND - CST.
3282 
3283 	     If TYPE is unsigned, we must additionally know that OP0 >= CST,
3284 	     otherwise the operation underflows.
3285 	   */
3286 
3287 	  /* This should only happen if the type is unsigned; however, for
3288 	     buggy programs that use overflowing signed arithmetics even with
3289 	     -fno-wrapv, this condition may also be true for signed values.  */
3290 	  if (wi::ltu_p (bnd, cst))
3291 	    return max;
3292 
3293 	  if (TYPE_UNSIGNED (type))
3294 	    {
3295 	      tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
3296 				      wide_int_to_tree (type, cst));
3297 	      if (!tem || integer_nonzerop (tem))
3298 		return max;
3299 	    }
3300 
3301 	  bnd -= cst;
3302 	}
3303 
3304       return bnd;
3305 
3306     case FLOOR_DIV_EXPR:
3307     case EXACT_DIV_EXPR:
3308       if (TREE_CODE (op1) != INTEGER_CST
3309 	  || tree_int_cst_sign_bit (op1))
3310 	return max;
3311 
3312       bnd = derive_constant_upper_bound (op0);
3313       return wi::udiv_floor (bnd, wi::to_widest (op1));
3314 
3315     case BIT_AND_EXPR:
3316       if (TREE_CODE (op1) != INTEGER_CST
3317 	  || tree_int_cst_sign_bit (op1))
3318 	return max;
3319       return wi::to_widest (op1);
3320 
3321     case SSA_NAME:
3322       stmt = SSA_NAME_DEF_STMT (op0);
3323       if (gimple_code (stmt) != GIMPLE_ASSIGN
3324 	  || gimple_assign_lhs (stmt) != op0)
3325 	return max;
3326       return derive_constant_upper_bound_assign (stmt);
3327 
3328     default:
3329       return max;
3330     }
3331 }
3332 
3333 /* Emit a -Waggressive-loop-optimizations warning if needed.  */
3334 
3335 static void
do_warn_aggressive_loop_optimizations(class loop * loop,widest_int i_bound,gimple * stmt)3336 do_warn_aggressive_loop_optimizations (class loop *loop,
3337 				       widest_int i_bound, gimple *stmt)
3338 {
3339   /* Don't warn if the loop doesn't have known constant bound.  */
3340   if (!loop->nb_iterations
3341       || TREE_CODE (loop->nb_iterations) != INTEGER_CST
3342       || !warn_aggressive_loop_optimizations
3343       /* To avoid warning multiple times for the same loop,
3344 	 only start warning when we preserve loops.  */
3345       || (cfun->curr_properties & PROP_loops) == 0
3346       /* Only warn once per loop.  */
3347       || loop->warned_aggressive_loop_optimizations
3348       /* Only warn if undefined behavior gives us lower estimate than the
3349 	 known constant bound.  */
3350       || wi::cmpu (i_bound, wi::to_widest (loop->nb_iterations)) >= 0
3351       /* And undefined behavior happens unconditionally.  */
3352       || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
3353     return;
3354 
3355   edge e = single_exit (loop);
3356   if (e == NULL)
3357     return;
3358 
3359   gimple *estmt = last_stmt (e->src);
3360   char buf[WIDE_INT_PRINT_BUFFER_SIZE];
3361   print_dec (i_bound, buf, TYPE_UNSIGNED (TREE_TYPE (loop->nb_iterations))
3362 	     ? UNSIGNED : SIGNED);
3363   auto_diagnostic_group d;
3364   if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
3365 		  "iteration %s invokes undefined behavior", buf))
3366     inform (gimple_location (estmt), "within this loop");
3367   loop->warned_aggressive_loop_optimizations = true;
3368 }
3369 
3370 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
3371    is true if the loop is exited immediately after STMT, and this exit
3372    is taken at last when the STMT is executed BOUND + 1 times.
3373    REALISTIC is true if BOUND is expected to be close to the real number
3374    of iterations.  UPPER is true if we are sure the loop iterates at most
3375    BOUND times.  I_BOUND is a widest_int upper estimate on BOUND.  */
3376 
3377 static void
record_estimate(class loop * loop,tree bound,const widest_int & i_bound,gimple * at_stmt,bool is_exit,bool realistic,bool upper)3378 record_estimate (class loop *loop, tree bound, const widest_int &i_bound,
3379 		 gimple *at_stmt, bool is_exit, bool realistic, bool upper)
3380 {
3381   widest_int delta;
3382 
3383   if (dump_file && (dump_flags & TDF_DETAILS))
3384     {
3385       fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
3386       print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
3387       fprintf (dump_file, " is %sexecuted at most ",
3388 	       upper ? "" : "probably ");
3389       print_generic_expr (dump_file, bound, TDF_SLIM);
3390       fprintf (dump_file, " (bounded by ");
3391       print_decu (i_bound, dump_file);
3392       fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
3393     }
3394 
3395   /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3396      real number of iterations.  */
3397   if (TREE_CODE (bound) != INTEGER_CST)
3398     realistic = false;
3399   else
3400     gcc_checking_assert (i_bound == wi::to_widest (bound));
3401 
3402   /* If we have a guaranteed upper bound, record it in the appropriate
3403      list, unless this is an !is_exit bound (i.e. undefined behavior in
3404      at_stmt) in a loop with known constant number of iterations.  */
3405   if (upper
3406       && (is_exit
3407 	  || loop->nb_iterations == NULL_TREE
3408 	  || TREE_CODE (loop->nb_iterations) != INTEGER_CST))
3409     {
3410       class nb_iter_bound *elt = ggc_alloc<nb_iter_bound> ();
3411 
3412       elt->bound = i_bound;
3413       elt->stmt = at_stmt;
3414       elt->is_exit = is_exit;
3415       elt->next = loop->bounds;
3416       loop->bounds = elt;
3417     }
3418 
3419   /* If statement is executed on every path to the loop latch, we can directly
3420      infer the upper bound on the # of iterations of the loop.  */
3421   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
3422     upper = false;
3423 
3424   /* Update the number of iteration estimates according to the bound.
3425      If at_stmt is an exit then the loop latch is executed at most BOUND times,
3426      otherwise it can be executed BOUND + 1 times.  We will lower the estimate
3427      later if such statement must be executed on last iteration  */
3428   if (is_exit)
3429     delta = 0;
3430   else
3431     delta = 1;
3432   widest_int new_i_bound = i_bound + delta;
3433 
3434   /* If an overflow occurred, ignore the result.  */
3435   if (wi::ltu_p (new_i_bound, delta))
3436     return;
3437 
3438   if (upper && !is_exit)
3439     do_warn_aggressive_loop_optimizations (loop, new_i_bound, at_stmt);
3440   record_niter_bound (loop, new_i_bound, realistic, upper);
3441 }
3442 
3443 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3444    and doesn't overflow.  */
3445 
3446 static void
record_control_iv(class loop * loop,class tree_niter_desc * niter)3447 record_control_iv (class loop *loop, class tree_niter_desc *niter)
3448 {
3449   struct control_iv *iv;
3450 
3451   if (!niter->control.base || !niter->control.step)
3452     return;
3453 
3454   if (!integer_onep (niter->assumptions) || !niter->control.no_overflow)
3455     return;
3456 
3457   iv = ggc_alloc<control_iv> ();
3458   iv->base = niter->control.base;
3459   iv->step = niter->control.step;
3460   iv->next = loop->control_ivs;
3461   loop->control_ivs = iv;
3462 
3463   return;
3464 }
3465 
3466 /* This function returns TRUE if below conditions are satisfied:
3467      1) VAR is SSA variable.
3468      2) VAR is an IV:{base, step} in its defining loop.
3469      3) IV doesn't overflow.
3470      4) Both base and step are integer constants.
3471      5) Base is the MIN/MAX value depends on IS_MIN.
3472    Store value of base to INIT correspondingly.  */
3473 
3474 static bool
get_cst_init_from_scev(tree var,wide_int * init,bool is_min)3475 get_cst_init_from_scev (tree var, wide_int *init, bool is_min)
3476 {
3477   if (TREE_CODE (var) != SSA_NAME)
3478     return false;
3479 
3480   gimple *def_stmt = SSA_NAME_DEF_STMT (var);
3481   class loop *loop = loop_containing_stmt (def_stmt);
3482 
3483   if (loop == NULL)
3484     return false;
3485 
3486   affine_iv iv;
3487   if (!simple_iv (loop, loop, var, &iv, false))
3488     return false;
3489 
3490   if (!iv.no_overflow)
3491     return false;
3492 
3493   if (TREE_CODE (iv.base) != INTEGER_CST || TREE_CODE (iv.step) != INTEGER_CST)
3494     return false;
3495 
3496   if (is_min == tree_int_cst_sign_bit (iv.step))
3497     return false;
3498 
3499   *init = wi::to_wide (iv.base);
3500   return true;
3501 }
3502 
3503 /* Record the estimate on number of iterations of LOOP based on the fact that
3504    the induction variable BASE + STEP * i evaluated in STMT does not wrap and
3505    its values belong to the range <LOW, HIGH>.  REALISTIC is true if the
3506    estimated number of iterations is expected to be close to the real one.
3507    UPPER is true if we are sure the induction variable does not wrap.  */
3508 
3509 static void
record_nonwrapping_iv(class loop * loop,tree base,tree step,gimple * stmt,tree low,tree high,bool realistic,bool upper)3510 record_nonwrapping_iv (class loop *loop, tree base, tree step, gimple *stmt,
3511 		       tree low, tree high, bool realistic, bool upper)
3512 {
3513   tree niter_bound, extreme, delta;
3514   tree type = TREE_TYPE (base), unsigned_type;
3515   tree orig_base = base;
3516 
3517   if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3518     return;
3519 
3520   if (dump_file && (dump_flags & TDF_DETAILS))
3521     {
3522       fprintf (dump_file, "Induction variable (");
3523       print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
3524       fprintf (dump_file, ") ");
3525       print_generic_expr (dump_file, base, TDF_SLIM);
3526       fprintf (dump_file, " + ");
3527       print_generic_expr (dump_file, step, TDF_SLIM);
3528       fprintf (dump_file, " * iteration does not wrap in statement ");
3529       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3530       fprintf (dump_file, " in loop %d.\n", loop->num);
3531     }
3532 
3533   unsigned_type = unsigned_type_for (type);
3534   base = fold_convert (unsigned_type, base);
3535   step = fold_convert (unsigned_type, step);
3536 
3537   if (tree_int_cst_sign_bit (step))
3538     {
3539       wide_int min, max;
3540       extreme = fold_convert (unsigned_type, low);
3541       if (TREE_CODE (orig_base) == SSA_NAME
3542 	  && TREE_CODE (high) == INTEGER_CST
3543 	  && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
3544 	  && (get_range_info (orig_base, &min, &max) == VR_RANGE
3545 	      || get_cst_init_from_scev (orig_base, &max, false))
3546 	  && wi::gts_p (wi::to_wide (high), max))
3547 	base = wide_int_to_tree (unsigned_type, max);
3548       else if (TREE_CODE (base) != INTEGER_CST
3549 	       && dominated_by_p (CDI_DOMINATORS,
3550 				  loop->latch, gimple_bb (stmt)))
3551 	base = fold_convert (unsigned_type, high);
3552       delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3553       step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
3554     }
3555   else
3556     {
3557       wide_int min, max;
3558       extreme = fold_convert (unsigned_type, high);
3559       if (TREE_CODE (orig_base) == SSA_NAME
3560 	  && TREE_CODE (low) == INTEGER_CST
3561 	  && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
3562 	  && (get_range_info (orig_base, &min, &max) == VR_RANGE
3563 	      || get_cst_init_from_scev (orig_base, &min, true))
3564 	  && wi::gts_p (min, wi::to_wide (low)))
3565 	base = wide_int_to_tree (unsigned_type, min);
3566       else if (TREE_CODE (base) != INTEGER_CST
3567 	       && dominated_by_p (CDI_DOMINATORS,
3568 				  loop->latch, gimple_bb (stmt)))
3569 	base = fold_convert (unsigned_type, low);
3570       delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3571     }
3572 
3573   /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
3574      would get out of the range.  */
3575   niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
3576   widest_int max = derive_constant_upper_bound (niter_bound);
3577   record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
3578 }
3579 
3580 /* Determine information about number of iterations a LOOP from the index
3581    IDX of a data reference accessed in STMT.  RELIABLE is true if STMT is
3582    guaranteed to be executed in every iteration of LOOP.  Callback for
3583    for_each_index.  */
3584 
3585 struct ilb_data
3586 {
3587   class loop *loop;
3588   gimple *stmt;
3589 };
3590 
3591 static bool
idx_infer_loop_bounds(tree base,tree * idx,void * dta)3592 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
3593 {
3594   struct ilb_data *data = (struct ilb_data *) dta;
3595   tree ev, init, step;
3596   tree low, high, type, next;
3597   bool sign, upper = true, at_end = false;
3598   class loop *loop = data->loop;
3599 
3600   if (TREE_CODE (base) != ARRAY_REF)
3601     return true;
3602 
3603   /* For arrays at the end of the structure, we are not guaranteed that they
3604      do not really extend over their declared size.  However, for arrays of
3605      size greater than one, this is unlikely to be intended.  */
3606   if (array_at_struct_end_p (base))
3607     {
3608       at_end = true;
3609       upper = false;
3610     }
3611 
3612   class loop *dloop = loop_containing_stmt (data->stmt);
3613   if (!dloop)
3614     return true;
3615 
3616   ev = analyze_scalar_evolution (dloop, *idx);
3617   ev = instantiate_parameters (loop, ev);
3618   init = initial_condition (ev);
3619   step = evolution_part_in_loop_num (ev, loop->num);
3620 
3621   if (!init
3622       || !step
3623       || TREE_CODE (step) != INTEGER_CST
3624       || integer_zerop (step)
3625       || tree_contains_chrecs (init, NULL)
3626       || chrec_contains_symbols_defined_in_loop (init, loop->num))
3627     return true;
3628 
3629   low = array_ref_low_bound (base);
3630   high = array_ref_up_bound (base);
3631 
3632   /* The case of nonconstant bounds could be handled, but it would be
3633      complicated.  */
3634   if (TREE_CODE (low) != INTEGER_CST
3635       || !high
3636       || TREE_CODE (high) != INTEGER_CST)
3637     return true;
3638   sign = tree_int_cst_sign_bit (step);
3639   type = TREE_TYPE (step);
3640 
3641   /* The array of length 1 at the end of a structure most likely extends
3642      beyond its bounds.  */
3643   if (at_end
3644       && operand_equal_p (low, high, 0))
3645     return true;
3646 
3647   /* In case the relevant bound of the array does not fit in type, or
3648      it does, but bound + step (in type) still belongs into the range of the
3649      array, the index may wrap and still stay within the range of the array
3650      (consider e.g. if the array is indexed by the full range of
3651      unsigned char).
3652 
3653      To make things simpler, we require both bounds to fit into type, although
3654      there are cases where this would not be strictly necessary.  */
3655   if (!int_fits_type_p (high, type)
3656       || !int_fits_type_p (low, type))
3657     return true;
3658   low = fold_convert (type, low);
3659   high = fold_convert (type, high);
3660 
3661   if (sign)
3662     next = fold_binary (PLUS_EXPR, type, low, step);
3663   else
3664     next = fold_binary (PLUS_EXPR, type, high, step);
3665 
3666   if (tree_int_cst_compare (low, next) <= 0
3667       && tree_int_cst_compare (next, high) <= 0)
3668     return true;
3669 
3670   /* If access is not executed on every iteration, we must ensure that overlow
3671      may not make the access valid later.  */
3672   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
3673       && scev_probably_wraps_p (NULL_TREE,
3674 				initial_condition_in_loop_num (ev, loop->num),
3675 				step, data->stmt, loop, true))
3676     upper = false;
3677 
3678   record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper);
3679   return true;
3680 }
3681 
3682 /* Determine information about number of iterations a LOOP from the bounds
3683    of arrays in the data reference REF accessed in STMT.  RELIABLE is true if
3684    STMT is guaranteed to be executed in every iteration of LOOP.*/
3685 
3686 static void
infer_loop_bounds_from_ref(class loop * loop,gimple * stmt,tree ref)3687 infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref)
3688 {
3689   struct ilb_data data;
3690 
3691   data.loop = loop;
3692   data.stmt = stmt;
3693   for_each_index (&ref, idx_infer_loop_bounds, &data);
3694 }
3695 
3696 /* Determine information about number of iterations of a LOOP from the way
3697    arrays are used in STMT.  RELIABLE is true if STMT is guaranteed to be
3698    executed in every iteration of LOOP.  */
3699 
3700 static void
infer_loop_bounds_from_array(class loop * loop,gimple * stmt)3701 infer_loop_bounds_from_array (class loop *loop, gimple *stmt)
3702 {
3703   if (is_gimple_assign (stmt))
3704     {
3705       tree op0 = gimple_assign_lhs (stmt);
3706       tree op1 = gimple_assign_rhs1 (stmt);
3707 
3708       /* For each memory access, analyze its access function
3709 	 and record a bound on the loop iteration domain.  */
3710       if (REFERENCE_CLASS_P (op0))
3711 	infer_loop_bounds_from_ref (loop, stmt, op0);
3712 
3713       if (REFERENCE_CLASS_P (op1))
3714 	infer_loop_bounds_from_ref (loop, stmt, op1);
3715     }
3716   else if (is_gimple_call (stmt))
3717     {
3718       tree arg, lhs;
3719       unsigned i, n = gimple_call_num_args (stmt);
3720 
3721       lhs = gimple_call_lhs (stmt);
3722       if (lhs && REFERENCE_CLASS_P (lhs))
3723 	infer_loop_bounds_from_ref (loop, stmt, lhs);
3724 
3725       for (i = 0; i < n; i++)
3726 	{
3727 	  arg = gimple_call_arg (stmt, i);
3728 	  if (REFERENCE_CLASS_P (arg))
3729 	    infer_loop_bounds_from_ref (loop, stmt, arg);
3730 	}
3731     }
3732 }
3733 
3734 /* Determine information about number of iterations of a LOOP from the fact
3735    that pointer arithmetics in STMT does not overflow.  */
3736 
3737 static void
infer_loop_bounds_from_pointer_arith(class loop * loop,gimple * stmt)3738 infer_loop_bounds_from_pointer_arith (class loop *loop, gimple *stmt)
3739 {
3740   tree def, base, step, scev, type, low, high;
3741   tree var, ptr;
3742 
3743   if (!is_gimple_assign (stmt)
3744       || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
3745     return;
3746 
3747   def = gimple_assign_lhs (stmt);
3748   if (TREE_CODE (def) != SSA_NAME)
3749     return;
3750 
3751   type = TREE_TYPE (def);
3752   if (!nowrap_type_p (type))
3753     return;
3754 
3755   ptr = gimple_assign_rhs1 (stmt);
3756   if (!expr_invariant_in_loop_p (loop, ptr))
3757     return;
3758 
3759   var = gimple_assign_rhs2 (stmt);
3760   if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
3761     return;
3762 
3763   class loop *uloop = loop_containing_stmt (stmt);
3764   scev = instantiate_parameters (loop, analyze_scalar_evolution (uloop, def));
3765   if (chrec_contains_undetermined (scev))
3766     return;
3767 
3768   base = initial_condition_in_loop_num (scev, loop->num);
3769   step = evolution_part_in_loop_num (scev, loop->num);
3770 
3771   if (!base || !step
3772       || TREE_CODE (step) != INTEGER_CST
3773       || tree_contains_chrecs (base, NULL)
3774       || chrec_contains_symbols_defined_in_loop (base, loop->num))
3775     return;
3776 
3777   low = lower_bound_in_type (type, type);
3778   high = upper_bound_in_type (type, type);
3779 
3780   /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
3781      produce a NULL pointer.  The contrary would mean NULL points to an object,
3782      while NULL is supposed to compare unequal with the address of all objects.
3783      Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
3784      NULL pointer since that would mean wrapping, which we assume here not to
3785      happen.  So, we can exclude NULL from the valid range of pointer
3786      arithmetic.  */
3787   if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
3788     low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
3789 
3790   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
3791 }
3792 
3793 /* Determine information about number of iterations of a LOOP from the fact
3794    that signed arithmetics in STMT does not overflow.  */
3795 
3796 static void
infer_loop_bounds_from_signedness(class loop * loop,gimple * stmt)3797 infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
3798 {
3799   tree def, base, step, scev, type, low, high;
3800 
3801   if (gimple_code (stmt) != GIMPLE_ASSIGN)
3802     return;
3803 
3804   def = gimple_assign_lhs (stmt);
3805 
3806   if (TREE_CODE (def) != SSA_NAME)
3807     return;
3808 
3809   type = TREE_TYPE (def);
3810   if (!INTEGRAL_TYPE_P (type)
3811       || !TYPE_OVERFLOW_UNDEFINED (type))
3812     return;
3813 
3814   scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
3815   if (chrec_contains_undetermined (scev))
3816     return;
3817 
3818   base = initial_condition_in_loop_num (scev, loop->num);
3819   step = evolution_part_in_loop_num (scev, loop->num);
3820 
3821   if (!base || !step
3822       || TREE_CODE (step) != INTEGER_CST
3823       || tree_contains_chrecs (base, NULL)
3824       || chrec_contains_symbols_defined_in_loop (base, loop->num))
3825     return;
3826 
3827   low = lower_bound_in_type (type, type);
3828   high = upper_bound_in_type (type, type);
3829   wide_int minv, maxv;
3830   if (get_range_info (def, &minv, &maxv) == VR_RANGE)
3831     {
3832       low = wide_int_to_tree (type, minv);
3833       high = wide_int_to_tree (type, maxv);
3834     }
3835 
3836   record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
3837 }
3838 
3839 /* The following analyzers are extracting informations on the bounds
3840    of LOOP from the following undefined behaviors:
3841 
3842    - data references should not access elements over the statically
3843      allocated size,
3844 
3845    - signed variables should not overflow when flag_wrapv is not set.
3846 */
3847 
3848 static void
infer_loop_bounds_from_undefined(class loop * loop,basic_block * bbs)3849 infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs)
3850 {
3851   unsigned i;
3852   gimple_stmt_iterator bsi;
3853   basic_block bb;
3854   bool reliable;
3855 
3856   for (i = 0; i < loop->num_nodes; i++)
3857     {
3858       bb = bbs[i];
3859 
3860       /* If BB is not executed in each iteration of the loop, we cannot
3861 	 use the operations in it to infer reliable upper bound on the
3862 	 # of iterations of the loop.  However, we can use it as a guess.
3863 	 Reliable guesses come only from array bounds.  */
3864       reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
3865 
3866       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3867 	{
3868 	  gimple *stmt = gsi_stmt (bsi);
3869 
3870 	  infer_loop_bounds_from_array (loop, stmt);
3871 
3872 	  if (reliable)
3873             {
3874               infer_loop_bounds_from_signedness (loop, stmt);
3875               infer_loop_bounds_from_pointer_arith (loop, stmt);
3876             }
3877   	}
3878 
3879     }
3880 }
3881 
3882 /* Compare wide ints, callback for qsort.  */
3883 
3884 static int
wide_int_cmp(const void * p1,const void * p2)3885 wide_int_cmp (const void *p1, const void *p2)
3886 {
3887   const widest_int *d1 = (const widest_int *) p1;
3888   const widest_int *d2 = (const widest_int *) p2;
3889   return wi::cmpu (*d1, *d2);
3890 }
3891 
3892 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3893    Lookup by binary search.  */
3894 
3895 static int
bound_index(vec<widest_int> bounds,const widest_int & bound)3896 bound_index (vec<widest_int> bounds, const widest_int &bound)
3897 {
3898   unsigned int end = bounds.length ();
3899   unsigned int begin = 0;
3900 
3901   /* Find a matching index by means of a binary search.  */
3902   while (begin != end)
3903     {
3904       unsigned int middle = (begin + end) / 2;
3905       widest_int index = bounds[middle];
3906 
3907       if (index == bound)
3908 	return middle;
3909       else if (wi::ltu_p (index, bound))
3910 	begin = middle + 1;
3911       else
3912 	end = middle;
3913     }
3914   gcc_unreachable ();
3915 }
3916 
3917 /* We recorded loop bounds only for statements dominating loop latch (and thus
3918    executed each loop iteration).  If there are any bounds on statements not
3919    dominating the loop latch we can improve the estimate by walking the loop
3920    body and seeing if every path from loop header to loop latch contains
3921    some bounded statement.  */
3922 
3923 static void
discover_iteration_bound_by_body_walk(class loop * loop)3924 discover_iteration_bound_by_body_walk (class loop *loop)
3925 {
3926   class nb_iter_bound *elt;
3927   auto_vec<widest_int> bounds;
3928   vec<vec<basic_block> > queues = vNULL;
3929   vec<basic_block> queue = vNULL;
3930   ptrdiff_t queue_index;
3931   ptrdiff_t latch_index = 0;
3932 
3933   /* Discover what bounds may interest us.  */
3934   for (elt = loop->bounds; elt; elt = elt->next)
3935     {
3936       widest_int bound = elt->bound;
3937 
3938       /* Exit terminates loop at given iteration, while non-exits produce undefined
3939 	 effect on the next iteration.  */
3940       if (!elt->is_exit)
3941 	{
3942 	  bound += 1;
3943 	  /* If an overflow occurred, ignore the result.  */
3944 	  if (bound == 0)
3945 	    continue;
3946 	}
3947 
3948       if (!loop->any_upper_bound
3949 	  || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
3950         bounds.safe_push (bound);
3951     }
3952 
3953   /* Exit early if there is nothing to do.  */
3954   if (!bounds.exists ())
3955     return;
3956 
3957   if (dump_file && (dump_flags & TDF_DETAILS))
3958     fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n");
3959 
3960   /* Sort the bounds in decreasing order.  */
3961   bounds.qsort (wide_int_cmp);
3962 
3963   /* For every basic block record the lowest bound that is guaranteed to
3964      terminate the loop.  */
3965 
3966   hash_map<basic_block, ptrdiff_t> bb_bounds;
3967   for (elt = loop->bounds; elt; elt = elt->next)
3968     {
3969       widest_int bound = elt->bound;
3970       if (!elt->is_exit)
3971 	{
3972 	  bound += 1;
3973 	  /* If an overflow occurred, ignore the result.  */
3974 	  if (bound == 0)
3975 	    continue;
3976 	}
3977 
3978       if (!loop->any_upper_bound
3979 	  || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
3980 	{
3981 	  ptrdiff_t index = bound_index (bounds, bound);
3982 	  ptrdiff_t *entry = bb_bounds.get (gimple_bb (elt->stmt));
3983 	  if (!entry)
3984 	    bb_bounds.put (gimple_bb (elt->stmt), index);
3985 	  else if ((ptrdiff_t)*entry > index)
3986 	    *entry = index;
3987 	}
3988     }
3989 
3990   hash_map<basic_block, ptrdiff_t> block_priority;
3991 
3992   /* Perform shortest path discovery loop->header ... loop->latch.
3993 
3994      The "distance" is given by the smallest loop bound of basic block
3995      present in the path and we look for path with largest smallest bound
3996      on it.
3997 
3998      To avoid the need for fibonacci heap on double ints we simply compress
3999      double ints into indexes to BOUNDS array and then represent the queue
4000      as arrays of queues for every index.
4001      Index of BOUNDS.length() means that the execution of given BB has
4002      no bounds determined.
4003 
4004      VISITED is a pointer map translating basic block into smallest index
4005      it was inserted into the priority queue with.  */
4006   latch_index = -1;
4007 
4008   /* Start walk in loop header with index set to infinite bound.  */
4009   queue_index = bounds.length ();
4010   queues.safe_grow_cleared (queue_index + 1);
4011   queue.safe_push (loop->header);
4012   queues[queue_index] = queue;
4013   block_priority.put (loop->header, queue_index);
4014 
4015   for (; queue_index >= 0; queue_index--)
4016     {
4017       if (latch_index < queue_index)
4018 	{
4019 	  while (queues[queue_index].length ())
4020 	    {
4021 	      basic_block bb;
4022 	      ptrdiff_t bound_index = queue_index;
4023               edge e;
4024               edge_iterator ei;
4025 
4026 	      queue = queues[queue_index];
4027 	      bb = queue.pop ();
4028 
4029 	      /* OK, we later inserted the BB with lower priority, skip it.  */
4030 	      if (*block_priority.get (bb) > queue_index)
4031 		continue;
4032 
4033 	      /* See if we can improve the bound.  */
4034 	      ptrdiff_t *entry = bb_bounds.get (bb);
4035 	      if (entry && *entry < bound_index)
4036 		bound_index = *entry;
4037 
4038 	      /* Insert succesors into the queue, watch for latch edge
4039 		 and record greatest index we saw.  */
4040 	      FOR_EACH_EDGE (e, ei, bb->succs)
4041 		{
4042 		  bool insert = false;
4043 
4044 		  if (loop_exit_edge_p (loop, e))
4045 		    continue;
4046 
4047 		  if (e == loop_latch_edge (loop)
4048 		      && latch_index < bound_index)
4049 		    latch_index = bound_index;
4050 		  else if (!(entry = block_priority.get (e->dest)))
4051 		    {
4052 		      insert = true;
4053 		      block_priority.put (e->dest, bound_index);
4054 		    }
4055 		  else if (*entry < bound_index)
4056 		    {
4057 		      insert = true;
4058 		      *entry = bound_index;
4059 		    }
4060 
4061 		  if (insert)
4062 		    queues[bound_index].safe_push (e->dest);
4063 		}
4064 	    }
4065 	}
4066       queues[queue_index].release ();
4067     }
4068 
4069   gcc_assert (latch_index >= 0);
4070   if ((unsigned)latch_index < bounds.length ())
4071     {
4072       if (dump_file && (dump_flags & TDF_DETAILS))
4073 	{
4074 	  fprintf (dump_file, "Found better loop bound ");
4075 	  print_decu (bounds[latch_index], dump_file);
4076 	  fprintf (dump_file, "\n");
4077 	}
4078       record_niter_bound (loop, bounds[latch_index], false, true);
4079     }
4080 
4081   queues.release ();
4082 }
4083 
4084 /* See if every path cross the loop goes through a statement that is known
4085    to not execute at the last iteration. In that case we can decrese iteration
4086    count by 1.  */
4087 
4088 static void
maybe_lower_iteration_bound(class loop * loop)4089 maybe_lower_iteration_bound (class loop *loop)
4090 {
4091   hash_set<gimple *> *not_executed_last_iteration = NULL;
4092   class nb_iter_bound *elt;
4093   bool found_exit = false;
4094   auto_vec<basic_block> queue;
4095   bitmap visited;
4096 
4097   /* Collect all statements with interesting (i.e. lower than
4098      nb_iterations_upper_bound) bound on them.
4099 
4100      TODO: Due to the way record_estimate choose estimates to store, the bounds
4101      will be always nb_iterations_upper_bound-1.  We can change this to record
4102      also statements not dominating the loop latch and update the walk bellow
4103      to the shortest path algorithm.  */
4104   for (elt = loop->bounds; elt; elt = elt->next)
4105     {
4106       if (!elt->is_exit
4107 	  && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound))
4108 	{
4109 	  if (!not_executed_last_iteration)
4110 	    not_executed_last_iteration = new hash_set<gimple *>;
4111 	  not_executed_last_iteration->add (elt->stmt);
4112 	}
4113     }
4114   if (!not_executed_last_iteration)
4115     return;
4116 
4117   /* Start DFS walk in the loop header and see if we can reach the
4118      loop latch or any of the exits (including statements with side
4119      effects that may terminate the loop otherwise) without visiting
4120      any of the statements known to have undefined effect on the last
4121      iteration.  */
4122   queue.safe_push (loop->header);
4123   visited = BITMAP_ALLOC (NULL);
4124   bitmap_set_bit (visited, loop->header->index);
4125   found_exit = false;
4126 
4127   do
4128     {
4129       basic_block bb = queue.pop ();
4130       gimple_stmt_iterator gsi;
4131       bool stmt_found = false;
4132 
4133       /* Loop for possible exits and statements bounding the execution.  */
4134       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4135 	{
4136 	  gimple *stmt = gsi_stmt (gsi);
4137 	  if (not_executed_last_iteration->contains (stmt))
4138 	    {
4139 	      stmt_found = true;
4140 	      break;
4141 	    }
4142 	  if (gimple_has_side_effects (stmt))
4143 	    {
4144 	      found_exit = true;
4145 	      break;
4146 	    }
4147 	}
4148       if (found_exit)
4149 	break;
4150 
4151       /* If no bounding statement is found, continue the walk.  */
4152       if (!stmt_found)
4153 	{
4154           edge e;
4155           edge_iterator ei;
4156 
4157           FOR_EACH_EDGE (e, ei, bb->succs)
4158 	    {
4159 	      if (loop_exit_edge_p (loop, e)
4160 		  || e == loop_latch_edge (loop))
4161 		{
4162 		  found_exit = true;
4163 		  break;
4164 		}
4165 	      if (bitmap_set_bit (visited, e->dest->index))
4166 		queue.safe_push (e->dest);
4167 	    }
4168 	}
4169     }
4170   while (queue.length () && !found_exit);
4171 
4172   /* If every path through the loop reach bounding statement before exit,
4173      then we know the last iteration of the loop will have undefined effect
4174      and we can decrease number of iterations.  */
4175 
4176   if (!found_exit)
4177     {
4178       if (dump_file && (dump_flags & TDF_DETAILS))
4179 	fprintf (dump_file, "Reducing loop iteration estimate by 1; "
4180 		 "undefined statement must be executed at the last iteration.\n");
4181       record_niter_bound (loop, loop->nb_iterations_upper_bound - 1,
4182 			  false, true);
4183     }
4184 
4185   BITMAP_FREE (visited);
4186   delete not_executed_last_iteration;
4187 }
4188 
4189 /* Get expected upper bound for number of loop iterations for
4190    BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND.  */
4191 
4192 static tree
get_upper_bound_based_on_builtin_expr_with_prob(gcond * cond)4193 get_upper_bound_based_on_builtin_expr_with_prob (gcond *cond)
4194 {
4195   if (cond == NULL)
4196     return NULL_TREE;
4197 
4198   tree lhs = gimple_cond_lhs (cond);
4199   if (TREE_CODE (lhs) != SSA_NAME)
4200     return NULL_TREE;
4201 
4202   gimple *stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
4203   gcall *def = dyn_cast<gcall *> (stmt);
4204   if (def == NULL)
4205     return NULL_TREE;
4206 
4207   tree decl = gimple_call_fndecl (def);
4208   if (!decl
4209       || !fndecl_built_in_p (decl, BUILT_IN_EXPECT_WITH_PROBABILITY)
4210       || gimple_call_num_args (stmt) != 3)
4211     return NULL_TREE;
4212 
4213   tree c = gimple_call_arg (def, 1);
4214   tree condt = TREE_TYPE (lhs);
4215   tree res = fold_build2 (gimple_cond_code (cond),
4216 			  condt, c,
4217 			  gimple_cond_rhs (cond));
4218   if (TREE_CODE (res) != INTEGER_CST)
4219     return NULL_TREE;
4220 
4221 
4222   tree prob = gimple_call_arg (def, 2);
4223   tree t = TREE_TYPE (prob);
4224   tree one
4225     = build_real_from_int_cst (t,
4226 			       integer_one_node);
4227   if (integer_zerop (res))
4228     prob = fold_build2 (MINUS_EXPR, t, one, prob);
4229   tree r = fold_build2 (RDIV_EXPR, t, one, prob);
4230   if (TREE_CODE (r) != REAL_CST)
4231     return NULL_TREE;
4232 
4233   HOST_WIDE_INT probi
4234     = real_to_integer (TREE_REAL_CST_PTR (r));
4235   return build_int_cst (condt, probi);
4236 }
4237 
4238 /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
4239    is true also use estimates derived from undefined behavior.  */
4240 
4241 void
estimate_numbers_of_iterations(class loop * loop)4242 estimate_numbers_of_iterations (class loop *loop)
4243 {
4244   vec<edge> exits;
4245   tree niter, type;
4246   unsigned i;
4247   class tree_niter_desc niter_desc;
4248   edge ex;
4249   widest_int bound;
4250   edge likely_exit;
4251 
4252   /* Give up if we already have tried to compute an estimation.  */
4253   if (loop->estimate_state != EST_NOT_COMPUTED)
4254     return;
4255 
4256   loop->estimate_state = EST_AVAILABLE;
4257 
4258   /* If we have a measured profile, use it to estimate the number of
4259      iterations.  Normally this is recorded by branch_prob right after
4260      reading the profile.  In case we however found a new loop, record the
4261      information here.
4262 
4263      Explicitly check for profile status so we do not report
4264      wrong prediction hitrates for guessed loop iterations heuristics.
4265      Do not recompute already recorded bounds - we ought to be better on
4266      updating iteration bounds than updating profile in general and thus
4267      recomputing iteration bounds later in the compilation process will just
4268      introduce random roundoff errors.  */
4269   if (!loop->any_estimate
4270       && loop->header->count.reliable_p ())
4271     {
4272       gcov_type nit = expected_loop_iterations_unbounded (loop);
4273       bound = gcov_type_to_wide_int (nit);
4274       record_niter_bound (loop, bound, true, false);
4275     }
4276 
4277   /* Ensure that loop->nb_iterations is computed if possible.  If it turns out
4278      to be constant, we avoid undefined behavior implied bounds and instead
4279      diagnose those loops with -Waggressive-loop-optimizations.  */
4280   number_of_latch_executions (loop);
4281 
4282   basic_block *body = get_loop_body (loop);
4283   exits = get_loop_exit_edges (loop, body);
4284   likely_exit = single_likely_exit (loop, exits);
4285   FOR_EACH_VEC_ELT (exits, i, ex)
4286     {
4287       if (ex == likely_exit)
4288 	{
4289 	  gimple *stmt = last_stmt (ex->src);
4290 	  if (stmt != NULL)
4291 	    {
4292 	      gcond *cond = dyn_cast<gcond *> (stmt);
4293 	      tree niter_bound
4294 		= get_upper_bound_based_on_builtin_expr_with_prob (cond);
4295 	      if (niter_bound != NULL_TREE)
4296 		{
4297 		  widest_int max = derive_constant_upper_bound (niter_bound);
4298 		  record_estimate (loop, niter_bound, max, cond,
4299 				   true, true, false);
4300 		}
4301 	    }
4302 	}
4303 
4304       if (!number_of_iterations_exit (loop, ex, &niter_desc,
4305 				      false, false, body))
4306 	continue;
4307 
4308       niter = niter_desc.niter;
4309       type = TREE_TYPE (niter);
4310       if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
4311 	niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
4312 			build_int_cst (type, 0),
4313 			niter);
4314       record_estimate (loop, niter, niter_desc.max,
4315 		       last_stmt (ex->src),
4316 		       true, ex == likely_exit, true);
4317       record_control_iv (loop, &niter_desc);
4318     }
4319   exits.release ();
4320 
4321   if (flag_aggressive_loop_optimizations)
4322     infer_loop_bounds_from_undefined (loop, body);
4323 
4324   discover_iteration_bound_by_body_walk (loop);
4325 
4326   maybe_lower_iteration_bound (loop);
4327 
4328   /* If we know the exact number of iterations of this loop, try to
4329      not break code with undefined behavior by not recording smaller
4330      maximum number of iterations.  */
4331   if (loop->nb_iterations
4332       && TREE_CODE (loop->nb_iterations) == INTEGER_CST)
4333     {
4334       loop->any_upper_bound = true;
4335       loop->nb_iterations_upper_bound = wi::to_widest (loop->nb_iterations);
4336     }
4337 }
4338 
4339 /* Sets NIT to the estimated number of executions of the latch of the
4340    LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
4341    large as the number of iterations.  If we have no reliable estimate,
4342    the function returns false, otherwise returns true.  */
4343 
4344 bool
estimated_loop_iterations(class loop * loop,widest_int * nit)4345 estimated_loop_iterations (class loop *loop, widest_int *nit)
4346 {
4347   /* When SCEV information is available, try to update loop iterations
4348      estimate.  Otherwise just return whatever we recorded earlier.  */
4349   if (scev_initialized_p ())
4350     estimate_numbers_of_iterations (loop);
4351 
4352   return (get_estimated_loop_iterations (loop, nit));
4353 }
4354 
4355 /* Similar to estimated_loop_iterations, but returns the estimate only
4356    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
4357    on the number of iterations of LOOP could not be derived, returns -1.  */
4358 
4359 HOST_WIDE_INT
estimated_loop_iterations_int(class loop * loop)4360 estimated_loop_iterations_int (class loop *loop)
4361 {
4362   widest_int nit;
4363   HOST_WIDE_INT hwi_nit;
4364 
4365   if (!estimated_loop_iterations (loop, &nit))
4366     return -1;
4367 
4368   if (!wi::fits_shwi_p (nit))
4369     return -1;
4370   hwi_nit = nit.to_shwi ();
4371 
4372   return hwi_nit < 0 ? -1 : hwi_nit;
4373 }
4374 
4375 
4376 /* Sets NIT to an upper bound for the maximum number of executions of the
4377    latch of the LOOP.  If we have no reliable estimate, the function returns
4378    false, otherwise returns true.  */
4379 
4380 bool
max_loop_iterations(class loop * loop,widest_int * nit)4381 max_loop_iterations (class loop *loop, widest_int *nit)
4382 {
4383   /* When SCEV information is available, try to update loop iterations
4384      estimate.  Otherwise just return whatever we recorded earlier.  */
4385   if (scev_initialized_p ())
4386     estimate_numbers_of_iterations (loop);
4387 
4388   return get_max_loop_iterations (loop, nit);
4389 }
4390 
4391 /* Similar to max_loop_iterations, but returns the estimate only
4392    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
4393    on the number of iterations of LOOP could not be derived, returns -1.  */
4394 
4395 HOST_WIDE_INT
max_loop_iterations_int(class loop * loop)4396 max_loop_iterations_int (class loop *loop)
4397 {
4398   widest_int nit;
4399   HOST_WIDE_INT hwi_nit;
4400 
4401   if (!max_loop_iterations (loop, &nit))
4402     return -1;
4403 
4404   if (!wi::fits_shwi_p (nit))
4405     return -1;
4406   hwi_nit = nit.to_shwi ();
4407 
4408   return hwi_nit < 0 ? -1 : hwi_nit;
4409 }
4410 
4411 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4412    latch of the LOOP.  If we have no reliable estimate, the function returns
4413    false, otherwise returns true.  */
4414 
4415 bool
likely_max_loop_iterations(class loop * loop,widest_int * nit)4416 likely_max_loop_iterations (class loop *loop, widest_int *nit)
4417 {
4418   /* When SCEV information is available, try to update loop iterations
4419      estimate.  Otherwise just return whatever we recorded earlier.  */
4420   if (scev_initialized_p ())
4421     estimate_numbers_of_iterations (loop);
4422 
4423   return get_likely_max_loop_iterations (loop, nit);
4424 }
4425 
4426 /* Similar to max_loop_iterations, but returns the estimate only
4427    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
4428    on the number of iterations of LOOP could not be derived, returns -1.  */
4429 
4430 HOST_WIDE_INT
likely_max_loop_iterations_int(class loop * loop)4431 likely_max_loop_iterations_int (class loop *loop)
4432 {
4433   widest_int nit;
4434   HOST_WIDE_INT hwi_nit;
4435 
4436   if (!likely_max_loop_iterations (loop, &nit))
4437     return -1;
4438 
4439   if (!wi::fits_shwi_p (nit))
4440     return -1;
4441   hwi_nit = nit.to_shwi ();
4442 
4443   return hwi_nit < 0 ? -1 : hwi_nit;
4444 }
4445 
4446 /* Returns an estimate for the number of executions of statements
4447    in the LOOP.  For statements before the loop exit, this exceeds
4448    the number of execution of the latch by one.  */
4449 
4450 HOST_WIDE_INT
estimated_stmt_executions_int(class loop * loop)4451 estimated_stmt_executions_int (class loop *loop)
4452 {
4453   HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
4454   HOST_WIDE_INT snit;
4455 
4456   if (nit == -1)
4457     return -1;
4458 
4459   snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
4460 
4461   /* If the computation overflows, return -1.  */
4462   return snit < 0 ? -1 : snit;
4463 }
4464 
4465 /* Sets NIT to the maximum number of executions of the latch of the
4466    LOOP, plus one.  If we have no reliable estimate, the function returns
4467    false, otherwise returns true.  */
4468 
4469 bool
max_stmt_executions(class loop * loop,widest_int * nit)4470 max_stmt_executions (class loop *loop, widest_int *nit)
4471 {
4472   widest_int nit_minus_one;
4473 
4474   if (!max_loop_iterations (loop, nit))
4475     return false;
4476 
4477   nit_minus_one = *nit;
4478 
4479   *nit += 1;
4480 
4481   return wi::gtu_p (*nit, nit_minus_one);
4482 }
4483 
4484 /* Sets NIT to the estimated maximum number of executions of the latch of the
4485    LOOP, plus one.  If we have no likely estimate, the function returns
4486    false, otherwise returns true.  */
4487 
4488 bool
likely_max_stmt_executions(class loop * loop,widest_int * nit)4489 likely_max_stmt_executions (class loop *loop, widest_int *nit)
4490 {
4491   widest_int nit_minus_one;
4492 
4493   if (!likely_max_loop_iterations (loop, nit))
4494     return false;
4495 
4496   nit_minus_one = *nit;
4497 
4498   *nit += 1;
4499 
4500   return wi::gtu_p (*nit, nit_minus_one);
4501 }
4502 
4503 /* Sets NIT to the estimated number of executions of the latch of the
4504    LOOP, plus one.  If we have no reliable estimate, the function returns
4505    false, otherwise returns true.  */
4506 
4507 bool
estimated_stmt_executions(class loop * loop,widest_int * nit)4508 estimated_stmt_executions (class loop *loop, widest_int *nit)
4509 {
4510   widest_int nit_minus_one;
4511 
4512   if (!estimated_loop_iterations (loop, nit))
4513     return false;
4514 
4515   nit_minus_one = *nit;
4516 
4517   *nit += 1;
4518 
4519   return wi::gtu_p (*nit, nit_minus_one);
4520 }
4521 
4522 /* Records estimates on numbers of iterations of loops.  */
4523 
4524 void
estimate_numbers_of_iterations(function * fn)4525 estimate_numbers_of_iterations (function *fn)
4526 {
4527   class loop *loop;
4528 
4529   /* We don't want to issue signed overflow warnings while getting
4530      loop iteration estimates.  */
4531   fold_defer_overflow_warnings ();
4532 
4533   FOR_EACH_LOOP_FN (fn, loop, 0)
4534     estimate_numbers_of_iterations (loop);
4535 
4536   fold_undefer_and_ignore_overflow_warnings ();
4537 }
4538 
4539 /* Returns true if statement S1 dominates statement S2.  */
4540 
4541 bool
stmt_dominates_stmt_p(gimple * s1,gimple * s2)4542 stmt_dominates_stmt_p (gimple *s1, gimple *s2)
4543 {
4544   basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
4545 
4546   if (!bb1
4547       || s1 == s2)
4548     return true;
4549 
4550   if (bb1 == bb2)
4551     {
4552       gimple_stmt_iterator bsi;
4553 
4554       if (gimple_code (s2) == GIMPLE_PHI)
4555 	return false;
4556 
4557       if (gimple_code (s1) == GIMPLE_PHI)
4558 	return true;
4559 
4560       for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
4561 	if (gsi_stmt (bsi) == s1)
4562 	  return true;
4563 
4564       return false;
4565     }
4566 
4567   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
4568 }
4569 
4570 /* Returns true when we can prove that the number of executions of
4571    STMT in the loop is at most NITER, according to the bound on
4572    the number of executions of the statement NITER_BOUND->stmt recorded in
4573    NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
4574 
4575    ??? This code can become quite a CPU hog - we can have many bounds,
4576    and large basic block forcing stmt_dominates_stmt_p to be queried
4577    many times on a large basic blocks, so the whole thing is O(n^2)
4578    for scev_probably_wraps_p invocation (that can be done n times).
4579 
4580    It would make more sense (and give better answers) to remember BB
4581    bounds computed by discover_iteration_bound_by_body_walk.  */
4582 
4583 static bool
n_of_executions_at_most(gimple * stmt,class nb_iter_bound * niter_bound,tree niter)4584 n_of_executions_at_most (gimple *stmt,
4585 			 class nb_iter_bound *niter_bound,
4586 			 tree niter)
4587 {
4588   widest_int bound = niter_bound->bound;
4589   tree nit_type = TREE_TYPE (niter), e;
4590   enum tree_code cmp;
4591 
4592   gcc_assert (TYPE_UNSIGNED (nit_type));
4593 
4594   /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
4595      the number of iterations is small.  */
4596   if (!wi::fits_to_tree_p (bound, nit_type))
4597     return false;
4598 
4599   /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
4600      times.  This means that:
4601 
4602      -- if NITER_BOUND->is_exit is true, then everything after
4603 	it at most NITER_BOUND->bound times.
4604 
4605      -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
4606 	is executed, then NITER_BOUND->stmt is executed as well in the same
4607 	iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
4608 
4609 	If we can determine that NITER_BOUND->stmt is always executed
4610 	after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
4611 	We conclude that if both statements belong to the same
4612 	basic block and STMT is before NITER_BOUND->stmt and there are no
4613 	statements with side effects in between.  */
4614 
4615   if (niter_bound->is_exit)
4616     {
4617       if (stmt == niter_bound->stmt
4618 	  || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
4619 	return false;
4620       cmp = GE_EXPR;
4621     }
4622   else
4623     {
4624       if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
4625 	{
4626           gimple_stmt_iterator bsi;
4627 	  if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
4628 	      || gimple_code (stmt) == GIMPLE_PHI
4629 	      || gimple_code (niter_bound->stmt) == GIMPLE_PHI)
4630 	    return false;
4631 
4632 	  /* By stmt_dominates_stmt_p we already know that STMT appears
4633 	     before NITER_BOUND->STMT.  Still need to test that the loop
4634 	     cannot be terinated by a side effect in between.  */
4635 	  for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
4636 	       gsi_next (&bsi))
4637 	    if (gimple_has_side_effects (gsi_stmt (bsi)))
4638 	       return false;
4639 	  bound += 1;
4640 	  if (bound == 0
4641 	      || !wi::fits_to_tree_p (bound, nit_type))
4642 	    return false;
4643 	}
4644       cmp = GT_EXPR;
4645     }
4646 
4647   e = fold_binary (cmp, boolean_type_node,
4648 		   niter, wide_int_to_tree (nit_type, bound));
4649   return e && integer_nonzerop (e);
4650 }
4651 
4652 /* Returns true if the arithmetics in TYPE can be assumed not to wrap.  */
4653 
4654 bool
nowrap_type_p(tree type)4655 nowrap_type_p (tree type)
4656 {
4657   if (ANY_INTEGRAL_TYPE_P (type)
4658       && TYPE_OVERFLOW_UNDEFINED (type))
4659     return true;
4660 
4661   if (POINTER_TYPE_P (type))
4662     return true;
4663 
4664   return false;
4665 }
4666 
4667 /* Return true if we can prove LOOP is exited before evolution of induction
4668    variable {BASE, STEP} overflows with respect to its type bound.  */
4669 
4670 static bool
loop_exits_before_overflow(tree base,tree step,gimple * at_stmt,class loop * loop)4671 loop_exits_before_overflow (tree base, tree step,
4672 			    gimple *at_stmt, class loop *loop)
4673 {
4674   widest_int niter;
4675   struct control_iv *civ;
4676   class nb_iter_bound *bound;
4677   tree e, delta, step_abs, unsigned_base;
4678   tree type = TREE_TYPE (step);
4679   tree unsigned_type, valid_niter;
4680 
4681   /* Don't issue signed overflow warnings.  */
4682   fold_defer_overflow_warnings ();
4683 
4684   /* Compute the number of iterations before we reach the bound of the
4685      type, and verify that the loop is exited before this occurs.  */
4686   unsigned_type = unsigned_type_for (type);
4687   unsigned_base = fold_convert (unsigned_type, base);
4688 
4689   if (tree_int_cst_sign_bit (step))
4690     {
4691       tree extreme = fold_convert (unsigned_type,
4692 				   lower_bound_in_type (type, type));
4693       delta = fold_build2 (MINUS_EXPR, unsigned_type, unsigned_base, extreme);
4694       step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
4695 			      fold_convert (unsigned_type, step));
4696     }
4697   else
4698     {
4699       tree extreme = fold_convert (unsigned_type,
4700 				   upper_bound_in_type (type, type));
4701       delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, unsigned_base);
4702       step_abs = fold_convert (unsigned_type, step);
4703     }
4704 
4705   valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
4706 
4707   estimate_numbers_of_iterations (loop);
4708 
4709   if (max_loop_iterations (loop, &niter)
4710       && wi::fits_to_tree_p (niter, TREE_TYPE (valid_niter))
4711       && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
4712 			   wide_int_to_tree (TREE_TYPE (valid_niter),
4713 					     niter))) != NULL
4714       && integer_nonzerop (e))
4715     {
4716       fold_undefer_and_ignore_overflow_warnings ();
4717       return true;
4718     }
4719   if (at_stmt)
4720     for (bound = loop->bounds; bound; bound = bound->next)
4721       {
4722 	if (n_of_executions_at_most (at_stmt, bound, valid_niter))
4723 	  {
4724 	    fold_undefer_and_ignore_overflow_warnings ();
4725 	    return true;
4726 	  }
4727       }
4728   fold_undefer_and_ignore_overflow_warnings ();
4729 
4730   /* Try to prove loop is exited before {base, step} overflows with the
4731      help of analyzed loop control IV.  This is done only for IVs with
4732      constant step because otherwise we don't have the information.  */
4733   if (TREE_CODE (step) == INTEGER_CST)
4734     {
4735       for (civ = loop->control_ivs; civ; civ = civ->next)
4736 	{
4737 	  enum tree_code code;
4738 	  tree civ_type = TREE_TYPE (civ->step);
4739 
4740 	  /* Have to consider type difference because operand_equal_p ignores
4741 	     that for constants.  */
4742 	  if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type)
4743 	      || element_precision (type) != element_precision (civ_type))
4744 	    continue;
4745 
4746 	  /* Only consider control IV with same step.  */
4747 	  if (!operand_equal_p (step, civ->step, 0))
4748 	    continue;
4749 
4750 	  /* Done proving if this is a no-overflow control IV.  */
4751 	  if (operand_equal_p (base, civ->base, 0))
4752 	    return true;
4753 
4754 	  /* Control IV is recorded after expanding simple operations,
4755 	     Here we expand base and compare it too.  */
4756 	  tree expanded_base = expand_simple_operations (base);
4757 	  if (operand_equal_p (expanded_base, civ->base, 0))
4758 	    return true;
4759 
4760 	  /* If this is a before stepping control IV, in other words, we have
4761 
4762 	       {civ_base, step} = {base + step, step}
4763 
4764 	     Because civ {base + step, step} doesn't overflow during loop
4765 	     iterations, {base, step} will not overflow if we can prove the
4766 	     operation "base + step" does not overflow.  Specifically, we try
4767 	     to prove below conditions are satisfied:
4768 
4769 	       base <= UPPER_BOUND (type) - step  ;;step > 0
4770 	       base >= LOWER_BOUND (type) - step  ;;step < 0
4771 
4772 	     by proving the reverse conditions are false using loop's initial
4773 	     condition.  */
4774 	  if (POINTER_TYPE_P (TREE_TYPE (base)))
4775 	    code = POINTER_PLUS_EXPR;
4776 	  else
4777 	    code = PLUS_EXPR;
4778 
4779 	  tree stepped = fold_build2 (code, TREE_TYPE (base), base, step);
4780 	  tree expanded_stepped = fold_build2 (code, TREE_TYPE (base),
4781 					       expanded_base, step);
4782 	  if (operand_equal_p (stepped, civ->base, 0)
4783 	      || operand_equal_p (expanded_stepped, civ->base, 0))
4784 	    {
4785 	      tree extreme;
4786 
4787 	      if (tree_int_cst_sign_bit (step))
4788 		{
4789 		  code = LT_EXPR;
4790 		  extreme = lower_bound_in_type (type, type);
4791 		}
4792 	      else
4793 		{
4794 		  code = GT_EXPR;
4795 		  extreme = upper_bound_in_type (type, type);
4796 		}
4797 	      extreme = fold_build2 (MINUS_EXPR, type, extreme, step);
4798 	      e = fold_build2 (code, boolean_type_node, base, extreme);
4799 	      e = simplify_using_initial_conditions (loop, e);
4800 	      if (integer_zerop (e))
4801 		return true;
4802 	    }
4803         }
4804     }
4805 
4806   return false;
4807 }
4808 
4809 /* VAR is scev variable whose evolution part is constant STEP, this function
4810    proves that VAR can't overflow by using value range info.  If VAR's value
4811    range is [MIN, MAX], it can be proven by:
4812      MAX + step doesn't overflow    ; if step > 0
4813    or
4814      MIN + step doesn't underflow   ; if step < 0.
4815 
4816    We can only do this if var is computed in every loop iteration, i.e, var's
4817    definition has to dominate loop latch.  Consider below example:
4818 
4819      {
4820        unsigned int i;
4821 
4822        <bb 3>:
4823 
4824        <bb 4>:
4825        # RANGE [0, 4294967294] NONZERO 65535
4826        # i_21 = PHI <0(3), i_18(9)>
4827        if (i_21 != 0)
4828 	 goto <bb 6>;
4829        else
4830 	 goto <bb 8>;
4831 
4832        <bb 6>:
4833        # RANGE [0, 65533] NONZERO 65535
4834        _6 = i_21 + 4294967295;
4835        # RANGE [0, 65533] NONZERO 65535
4836        _7 = (long unsigned int) _6;
4837        # RANGE [0, 524264] NONZERO 524280
4838        _8 = _7 * 8;
4839        # PT = nonlocal escaped
4840        _9 = a_14 + _8;
4841        *_9 = 0;
4842 
4843        <bb 8>:
4844        # RANGE [1, 65535] NONZERO 65535
4845        i_18 = i_21 + 1;
4846        if (i_18 >= 65535)
4847 	 goto <bb 10>;
4848        else
4849 	 goto <bb 9>;
4850 
4851        <bb 9>:
4852        goto <bb 4>;
4853 
4854        <bb 10>:
4855        return;
4856      }
4857 
4858    VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
4859    can't use _6 to prove no-overlfow for _7.  In fact, var _7 takes value
4860    sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
4861    (4294967295, 4294967296, ...).  */
4862 
4863 static bool
scev_var_range_cant_overflow(tree var,tree step,class loop * loop)4864 scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
4865 {
4866   tree type;
4867   wide_int minv, maxv, diff, step_wi;
4868   enum value_range_kind rtype;
4869 
4870   if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var)))
4871     return false;
4872 
4873   /* Check if VAR evaluates in every loop iteration.  It's not the case
4874      if VAR is default definition or does not dominate loop's latch.  */
4875   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
4876   if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
4877     return false;
4878 
4879   rtype = get_range_info (var, &minv, &maxv);
4880   if (rtype != VR_RANGE)
4881     return false;
4882 
4883   /* VAR is a scev whose evolution part is STEP and value range info
4884      is [MIN, MAX], we can prove its no-overflowness by conditions:
4885 
4886        type_MAX - MAX >= step   ; if step > 0
4887        MIN - type_MIN >= |step| ; if step < 0.
4888 
4889      Or VAR must take value outside of value range, which is not true.  */
4890   step_wi = wi::to_wide (step);
4891   type = TREE_TYPE (var);
4892   if (tree_int_cst_sign_bit (step))
4893     {
4894       diff = minv - wi::to_wide (lower_bound_in_type (type, type));
4895       step_wi = - step_wi;
4896     }
4897   else
4898     diff = wi::to_wide (upper_bound_in_type (type, type)) - maxv;
4899 
4900   return (wi::geu_p (diff, step_wi));
4901 }
4902 
4903 /* Return false only when the induction variable BASE + STEP * I is
4904    known to not overflow: i.e. when the number of iterations is small
4905    enough with respect to the step and initial condition in order to
4906    keep the evolution confined in TYPEs bounds.  Return true when the
4907    iv is known to overflow or when the property is not computable.
4908 
4909    USE_OVERFLOW_SEMANTICS is true if this function should assume that
4910    the rules for overflow of the given language apply (e.g., that signed
4911    arithmetics in C does not overflow).
4912 
4913    If VAR is a ssa variable, this function also returns false if VAR can
4914    be proven not overflow with value range info.  */
4915 
4916 bool
scev_probably_wraps_p(tree var,tree base,tree step,gimple * at_stmt,class loop * loop,bool use_overflow_semantics)4917 scev_probably_wraps_p (tree var, tree base, tree step,
4918 		       gimple *at_stmt, class loop *loop,
4919 		       bool use_overflow_semantics)
4920 {
4921   /* FIXME: We really need something like
4922      http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
4923 
4924      We used to test for the following situation that frequently appears
4925      during address arithmetics:
4926 
4927        D.1621_13 = (long unsigned intD.4) D.1620_12;
4928        D.1622_14 = D.1621_13 * 8;
4929        D.1623_15 = (doubleD.29 *) D.1622_14;
4930 
4931      And derived that the sequence corresponding to D_14
4932      can be proved to not wrap because it is used for computing a
4933      memory access; however, this is not really the case -- for example,
4934      if D_12 = (unsigned char) [254,+,1], then D_14 has values
4935      2032, 2040, 0, 8, ..., but the code is still legal.  */
4936 
4937   if (chrec_contains_undetermined (base)
4938       || chrec_contains_undetermined (step))
4939     return true;
4940 
4941   if (integer_zerop (step))
4942     return false;
4943 
4944   /* If we can use the fact that signed and pointer arithmetics does not
4945      wrap, we are done.  */
4946   if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
4947     return false;
4948 
4949   /* To be able to use estimates on number of iterations of the loop,
4950      we must have an upper bound on the absolute value of the step.  */
4951   if (TREE_CODE (step) != INTEGER_CST)
4952     return true;
4953 
4954   /* Check if var can be proven not overflow with value range info.  */
4955   if (var && TREE_CODE (var) == SSA_NAME
4956       && scev_var_range_cant_overflow (var, step, loop))
4957     return false;
4958 
4959   if (loop_exits_before_overflow (base, step, at_stmt, loop))
4960     return false;
4961 
4962   /* At this point we still don't have a proof that the iv does not
4963      overflow: give up.  */
4964   return true;
4965 }
4966 
4967 /* Frees the information on upper bounds on numbers of iterations of LOOP.  */
4968 
4969 void
free_numbers_of_iterations_estimates(class loop * loop)4970 free_numbers_of_iterations_estimates (class loop *loop)
4971 {
4972   struct control_iv *civ;
4973   class nb_iter_bound *bound;
4974 
4975   loop->nb_iterations = NULL;
4976   loop->estimate_state = EST_NOT_COMPUTED;
4977   for (bound = loop->bounds; bound;)
4978     {
4979       class nb_iter_bound *next = bound->next;
4980       ggc_free (bound);
4981       bound = next;
4982     }
4983   loop->bounds = NULL;
4984 
4985   for (civ = loop->control_ivs; civ;)
4986     {
4987       struct control_iv *next = civ->next;
4988       ggc_free (civ);
4989       civ = next;
4990     }
4991   loop->control_ivs = NULL;
4992 }
4993 
4994 /* Frees the information on upper bounds on numbers of iterations of loops.  */
4995 
4996 void
free_numbers_of_iterations_estimates(function * fn)4997 free_numbers_of_iterations_estimates (function *fn)
4998 {
4999   class loop *loop;
5000 
5001   FOR_EACH_LOOP_FN (fn, loop, 0)
5002     free_numbers_of_iterations_estimates (loop);
5003 }
5004 
5005 /* Substitute value VAL for ssa name NAME inside expressions held
5006    at LOOP.  */
5007 
5008 void
substitute_in_loop_info(class loop * loop,tree name,tree val)5009 substitute_in_loop_info (class loop *loop, tree name, tree val)
5010 {
5011   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
5012 }
5013