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