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