Line data Source code
1 : /* Functions to determine/estimate number of iterations of a loop.
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it
7 : under the terms of the GNU General Public License as published by the
8 : Free Software Foundation; either version 3, or (at your option) any
9 : later version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT
12 : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #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 "gimple-iterator.h"
36 : #include "tree-cfg.h"
37 : #include "tree-ssa-loop-ivopts.h"
38 : #include "tree-ssa-loop-niter.h"
39 : #include "tree-ssa-loop.h"
40 : #include "cfgloop.h"
41 : #include "tree-chrec.h"
42 : #include "tree-scalar-evolution.h"
43 : #include "tree-data-ref.h"
44 : #include "tree-dfa.h"
45 : #include "internal-fn.h"
46 : #include "gimple-range.h"
47 : #include "sreal.h"
48 :
49 :
50 : /*
51 :
52 : Analysis of number of iterations of an affine exit test.
53 :
54 : */
55 :
56 : /* Bounds on some value, BELOW <= X <= UP. */
57 :
58 : struct bounds
59 : {
60 : mpz_t below, up;
61 : };
62 :
63 : /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
64 :
65 : static void
66 58689938 : split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
67 : {
68 58689938 : tree type = TREE_TYPE (expr);
69 58689938 : tree op0, op1;
70 58689938 : bool negate = false;
71 :
72 58689938 : *var = expr;
73 58689938 : mpz_set_ui (offset, 0);
74 :
75 58689938 : switch (TREE_CODE (expr))
76 : {
77 8027 : case MINUS_EXPR:
78 8027 : negate = true;
79 : /* Fallthru. */
80 :
81 6000721 : case PLUS_EXPR:
82 6000721 : case POINTER_PLUS_EXPR:
83 6000721 : op0 = TREE_OPERAND (expr, 0);
84 6000721 : op1 = TREE_OPERAND (expr, 1);
85 :
86 6000721 : if (TREE_CODE (op1) != INTEGER_CST)
87 : break;
88 :
89 5989218 : *var = op0;
90 : /* Always sign extend the offset. */
91 5989218 : wi::to_mpz (wi::to_wide (op1), offset, SIGNED);
92 5989218 : if (negate)
93 34 : mpz_neg (offset, offset);
94 : break;
95 :
96 26094071 : case INTEGER_CST:
97 26094071 : *var = build_int_cst_type (type, 0);
98 26094071 : wi::to_mpz (wi::to_wide (expr), offset, TYPE_SIGN (type));
99 26094071 : break;
100 :
101 : default:
102 : break;
103 : }
104 58689938 : }
105 :
106 : /* From condition C0 CMP C1 derives information regarding the value range
107 : of VAR, which is of TYPE. Results are stored in to BELOW and UP. */
108 :
109 : static void
110 21252111 : refine_value_range_using_guard (tree type, tree var,
111 : tree c0, enum tree_code cmp, tree c1,
112 : mpz_t below, mpz_t up)
113 : {
114 21252111 : tree varc0, varc1, ctype;
115 21252111 : mpz_t offc0, offc1;
116 21252111 : mpz_t mint, maxt, minc1, maxc1;
117 21252111 : bool no_wrap = nowrap_type_p (type);
118 21252111 : bool c0_ok, c1_ok;
119 21252111 : signop sgn = TYPE_SIGN (type);
120 :
121 21252111 : switch (cmp)
122 : {
123 9947683 : case LT_EXPR:
124 9947683 : case LE_EXPR:
125 9947683 : case GT_EXPR:
126 9947683 : case GE_EXPR:
127 9947683 : STRIP_SIGN_NOPS (c0);
128 9947683 : STRIP_SIGN_NOPS (c1);
129 9947683 : ctype = TREE_TYPE (c0);
130 9947683 : if (!useless_type_conversion_p (ctype, type))
131 18261635 : return;
132 :
133 : break;
134 :
135 : case EQ_EXPR:
136 : /* We could derive quite precise information from EQ_EXPR, however,
137 : such a guard is unlikely to appear, so we do not bother with
138 : handling it. */
139 : return;
140 :
141 5239109 : case NE_EXPR:
142 : /* NE_EXPR comparisons do not contain much of useful information,
143 : except for cases of comparing with bounds. */
144 5239109 : if (TREE_CODE (c1) != INTEGER_CST
145 4916202 : || !INTEGRAL_TYPE_P (type))
146 : return;
147 :
148 : /* Ensure that the condition speaks about an expression in the same
149 : type as X and Y. */
150 4916202 : ctype = TREE_TYPE (c0);
151 4916202 : if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
152 : return;
153 2953677 : c0 = fold_convert (type, c0);
154 2953677 : c1 = fold_convert (type, c1);
155 :
156 2953677 : if (operand_equal_p (var, c0, 0))
157 : {
158 : /* Case of comparing VAR with its below/up bounds. */
159 311423 : auto_mpz valc1;
160 311423 : wi::to_mpz (wi::to_wide (c1), valc1, TYPE_SIGN (type));
161 311423 : if (mpz_cmp (valc1, below) == 0)
162 94567 : cmp = GT_EXPR;
163 311423 : if (mpz_cmp (valc1, up) == 0)
164 49078 : cmp = LT_EXPR;
165 311423 : }
166 : else
167 : {
168 : /* Case of comparing with the bounds of the type. */
169 2642254 : wide_int min = wi::min_value (type);
170 2642254 : wide_int max = wi::max_value (type);
171 :
172 2642254 : if (wi::to_wide (c1) == min)
173 749300 : cmp = GT_EXPR;
174 2642254 : if (wi::to_wide (c1) == max)
175 32060 : cmp = LT_EXPR;
176 2642254 : }
177 :
178 : /* Quick return if no useful information. */
179 2953677 : if (cmp == NE_EXPR)
180 : return;
181 :
182 : break;
183 :
184 : default:
185 : return;
186 : }
187 :
188 9144840 : mpz_init (offc0);
189 9144840 : mpz_init (offc1);
190 9144840 : split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
191 9144840 : split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
192 :
193 : /* We are only interested in comparisons of expressions based on VAR. */
194 9144840 : if (operand_equal_p (var, varc1, 0))
195 : {
196 859505 : std::swap (varc0, varc1);
197 859505 : mpz_swap (offc0, offc1);
198 859505 : cmp = swap_tree_comparison (cmp);
199 : }
200 8285335 : else if (!operand_equal_p (var, varc0, 0))
201 : {
202 6154364 : mpz_clear (offc0);
203 6154364 : mpz_clear (offc1);
204 6154364 : return;
205 : }
206 :
207 2990476 : mpz_init (mint);
208 2990476 : mpz_init (maxt);
209 2990476 : get_type_static_bounds (type, mint, maxt);
210 2990476 : mpz_init (minc1);
211 2990476 : mpz_init (maxc1);
212 5980952 : int_range_max r (TREE_TYPE (varc1));
213 : /* Setup range information for varc1. */
214 2990476 : if (integer_zerop (varc1))
215 : {
216 1462790 : wi::to_mpz (0, minc1, TYPE_SIGN (type));
217 1462790 : wi::to_mpz (0, maxc1, TYPE_SIGN (type));
218 : }
219 1527686 : else if (TREE_CODE (varc1) == SSA_NAME
220 1430763 : && INTEGRAL_TYPE_P (type)
221 2861526 : && get_range_query (cfun)->range_of_expr (r, varc1)
222 1430763 : && !r.undefined_p ()
223 2955733 : && !r.varying_p ())
224 : {
225 1515336 : gcc_assert (wi::le_p (r.lower_bound (), r.upper_bound (), sgn));
226 757668 : wi::to_mpz (r.lower_bound (), minc1, sgn);
227 757668 : wi::to_mpz (r.upper_bound (), maxc1, sgn);
228 : }
229 : else
230 : {
231 770018 : mpz_set (minc1, mint);
232 770018 : mpz_set (maxc1, maxt);
233 : }
234 :
235 : /* Compute valid range information for varc1 + offc1. Note nothing
236 : useful can be derived if it overflows or underflows. Overflow or
237 : underflow could happen when:
238 :
239 : offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
240 : offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */
241 2990476 : mpz_add (minc1, minc1, offc1);
242 2990476 : mpz_add (maxc1, maxc1, offc1);
243 5980952 : c1_ok = (no_wrap
244 830293 : || mpz_sgn (offc1) == 0
245 132928 : || (mpz_sgn (offc1) < 0 && mpz_cmp (minc1, mint) >= 0)
246 3122055 : || (mpz_sgn (offc1) > 0 && mpz_cmp (maxc1, maxt) <= 0));
247 30141 : if (!c1_ok)
248 30141 : goto end;
249 :
250 2960335 : if (mpz_cmp (minc1, mint) < 0)
251 29551 : mpz_set (minc1, mint);
252 2960335 : if (mpz_cmp (maxc1, maxt) > 0)
253 17405 : mpz_set (maxc1, maxt);
254 :
255 2960335 : if (cmp == LT_EXPR)
256 : {
257 420989 : cmp = LE_EXPR;
258 420989 : mpz_sub_ui (maxc1, maxc1, 1);
259 : }
260 2960335 : if (cmp == GT_EXPR)
261 : {
262 1516021 : cmp = GE_EXPR;
263 1516021 : mpz_add_ui (minc1, minc1, 1);
264 : }
265 :
266 : /* Compute range information for varc0. If there is no overflow,
267 : the condition implied that
268 :
269 : (varc0) cmp (varc1 + offc1 - offc0)
270 :
271 : We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
272 : or the below bound if cmp is GE_EXPR.
273 :
274 : To prove there is no overflow/underflow, we need to check below
275 : four cases:
276 : 1) cmp == LE_EXPR && offc0 > 0
277 :
278 : (varc0 + offc0) doesn't overflow
279 : && (varc1 + offc1 - offc0) doesn't underflow
280 :
281 : 2) cmp == LE_EXPR && offc0 < 0
282 :
283 : (varc0 + offc0) doesn't underflow
284 : && (varc1 + offc1 - offc0) doesn't overfloe
285 :
286 : In this case, (varc0 + offc0) will never underflow if we can
287 : prove (varc1 + offc1 - offc0) doesn't overflow.
288 :
289 : 3) cmp == GE_EXPR && offc0 < 0
290 :
291 : (varc0 + offc0) doesn't underflow
292 : && (varc1 + offc1 - offc0) doesn't overflow
293 :
294 : 4) cmp == GE_EXPR && offc0 > 0
295 :
296 : (varc0 + offc0) doesn't overflow
297 : && (varc1 + offc1 - offc0) doesn't underflow
298 :
299 : In this case, (varc0 + offc0) will never overflow if we can
300 : prove (varc1 + offc1 - offc0) doesn't underflow.
301 :
302 : Note we only handle case 2 and 4 in below code. */
303 :
304 2960335 : mpz_sub (minc1, minc1, offc0);
305 2960335 : mpz_sub (maxc1, maxc1, offc0);
306 5920670 : c0_ok = (no_wrap
307 800152 : || mpz_sgn (offc0) == 0
308 52066 : || (cmp == LE_EXPR
309 34194 : && mpz_sgn (offc0) < 0 && mpz_cmp (maxc1, maxt) <= 0)
310 3009587 : || (cmp == GE_EXPR
311 17872 : && mpz_sgn (offc0) > 0 && mpz_cmp (minc1, mint) >= 0));
312 46856 : if (!c0_ok)
313 46856 : goto end;
314 :
315 2913479 : if (cmp == LE_EXPR)
316 : {
317 1113204 : if (mpz_cmp (up, maxc1) > 0)
318 347521 : mpz_set (up, maxc1);
319 : }
320 : else
321 : {
322 1800275 : if (mpz_cmp (below, minc1) < 0)
323 1086190 : mpz_set (below, minc1);
324 : }
325 :
326 714085 : end:
327 2990476 : mpz_clear (mint);
328 2990476 : mpz_clear (maxt);
329 2990476 : mpz_clear (minc1);
330 2990476 : mpz_clear (maxc1);
331 2990476 : mpz_clear (offc0);
332 2990476 : mpz_clear (offc1);
333 : }
334 :
335 : /* Stores estimates of the minimum and maximum values of the expression
336 : VAR + OFF in TYPE to MIN and MAX. The estimates are valid on entry
337 : to LOOP, i.e. on the loop preheader edge. */
338 :
339 : static void
340 25765732 : determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
341 : mpz_t min, mpz_t max)
342 : {
343 25765732 : int cnt = 0;
344 25765732 : mpz_t minm, maxm;
345 25765732 : basic_block bb;
346 25765732 : wide_int minv, maxv;
347 25765732 : enum value_range_kind rtype = VR_VARYING;
348 :
349 : /* If the expression is a constant, we know its value exactly. */
350 25765732 : if (integer_zerop (var))
351 : {
352 18195350 : mpz_set (min, off);
353 18195350 : mpz_set (max, off);
354 18195350 : return;
355 : }
356 :
357 7570382 : get_type_static_bounds (type, min, max);
358 :
359 : /* See if we have some range info from VRP. */
360 7570382 : if (INTEGRAL_TYPE_P (type))
361 : {
362 6078905 : edge e = loop_preheader_edge (loop);
363 6078905 : signop sgn = TYPE_SIGN (type);
364 6078905 : gphi_iterator gsi;
365 :
366 : /* Either for VAR itself... */
367 6078905 : int_range_max var_range (TREE_TYPE (var));
368 12157810 : get_range_query (cfun)->range_on_edge (var_range, e, var);
369 6078905 : if (var_range.varying_p () || var_range.undefined_p ())
370 : rtype = VR_VARYING;
371 : else
372 : rtype = VR_RANGE;
373 6078905 : if (!var_range.undefined_p ())
374 : {
375 6062346 : minv = var_range.lower_bound ();
376 6062414 : maxv = var_range.upper_bound ();
377 : }
378 :
379 : /* Or for PHI results in loop->header where VAR is used as
380 : PHI argument from the loop preheader edge. */
381 6078905 : int_range_max phi_range (TREE_TYPE (var));
382 22419276 : for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
383 : {
384 16340388 : gphi *phi = gsi.phi ();
385 16340388 : if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
386 2674820 : && get_range_query (cfun)->range_on_edge (phi_range,
387 : e, gimple_phi_result (phi))
388 1337410 : && !phi_range.varying_p ()
389 17096045 : && !phi_range.undefined_p ())
390 : {
391 755653 : if (rtype != VR_RANGE)
392 : {
393 245762 : rtype = VR_RANGE;
394 245762 : minv = phi_range.lower_bound ();
395 245777 : maxv = phi_range.upper_bound ();
396 : }
397 : else
398 : {
399 509893 : minv = wi::max (minv, phi_range.lower_bound (), sgn);
400 509893 : maxv = wi::min (maxv, phi_range.upper_bound (), sgn);
401 : /* If the PHI result range are inconsistent with
402 : the VAR range, give up on looking at the PHI
403 : results. This can happen if VR_UNDEFINED is
404 : involved. */
405 509891 : if (wi::gt_p (minv, maxv, sgn))
406 : {
407 17 : int_range_max vr (TREE_TYPE (var));
408 34 : get_range_query (cfun)->range_on_edge (vr, e, var);
409 17 : if (vr.varying_p () || vr.undefined_p ())
410 : rtype = VR_VARYING;
411 : else
412 : rtype = VR_RANGE;
413 17 : if (!vr.undefined_p ())
414 : {
415 17 : minv = vr.lower_bound ();
416 17 : maxv = vr.upper_bound ();
417 : }
418 17 : break;
419 17 : }
420 : }
421 : }
422 : }
423 6078905 : mpz_init (minm);
424 6078905 : mpz_init (maxm);
425 6078905 : if (rtype != VR_RANGE)
426 : {
427 2977986 : mpz_set (minm, min);
428 2977986 : mpz_set (maxm, max);
429 : }
430 : else
431 : {
432 3100919 : gcc_assert (wi::le_p (minv, maxv, sgn));
433 3100919 : wi::to_mpz (minv, minm, sgn);
434 3100919 : wi::to_mpz (maxv, maxm, sgn);
435 : }
436 : /* Now walk the dominators of the loop header and use the entry
437 : guards to refine the estimates. */
438 6078905 : for (bb = loop->header;
439 61509988 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
440 61509988 : && cnt < param_max_niter_dominators_walk;
441 55431083 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
442 : {
443 55431083 : edge e;
444 55431083 : tree c0, c1;
445 55431083 : enum tree_code cmp;
446 :
447 55431083 : if (!single_pred_p (bb))
448 27603687 : continue;
449 27827396 : e = single_pred_edge (bb);
450 :
451 27827396 : if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
452 6575285 : continue;
453 :
454 42504222 : gcond *cond = as_a <gcond *> (*gsi_last_bb (e->src));
455 21252111 : c0 = gimple_cond_lhs (cond);
456 21252111 : cmp = gimple_cond_code (cond);
457 21252111 : c1 = gimple_cond_rhs (cond);
458 :
459 21252111 : if (e->flags & EDGE_FALSE_VALUE)
460 11387037 : cmp = invert_tree_comparison (cmp, false);
461 :
462 21252111 : refine_value_range_using_guard (type, var, c0, cmp, c1, minm, maxm);
463 21252111 : ++cnt;
464 : }
465 :
466 6078905 : mpz_add (minm, minm, off);
467 6078905 : mpz_add (maxm, maxm, off);
468 : /* If the computation may not wrap or off is zero, then this
469 : is always fine. If off is negative and minv + off isn't
470 : smaller than type's minimum, or off is positive and
471 : maxv + off isn't bigger than type's maximum, use the more
472 : precise range too. */
473 6078905 : if (nowrap_type_p (type)
474 2358127 : || mpz_sgn (off) == 0
475 601319 : || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0)
476 6594354 : || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0))
477 : {
478 5870720 : mpz_set (min, minm);
479 5870720 : mpz_set (max, maxm);
480 5870720 : mpz_clear (minm);
481 5870720 : mpz_clear (maxm);
482 5870720 : return;
483 : }
484 208185 : mpz_clear (minm);
485 208185 : mpz_clear (maxm);
486 6078905 : }
487 :
488 : /* If the computation may wrap, we know nothing about the value, except for
489 : the range of the type. */
490 1699662 : if (!nowrap_type_p (type))
491 : return;
492 :
493 : /* Since the addition of OFF does not wrap, if OFF is positive, then we may
494 : add it to MIN, otherwise to MAX. */
495 1491365 : if (mpz_sgn (off) < 0)
496 22480 : mpz_add (max, max, off);
497 : else
498 1468885 : mpz_add (min, min, off);
499 25765800 : }
500 :
501 : /* Stores the bounds on the difference of the values of the expressions
502 : (var + X) and (var + Y), computed in TYPE, to BNDS. */
503 :
504 : static void
505 173139 : bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
506 : bounds *bnds)
507 : {
508 173139 : int rel = mpz_cmp (x, y);
509 173139 : bool may_wrap = !nowrap_type_p (type);
510 :
511 : /* If X == Y, then the expressions are always equal.
512 : If X > Y, there are the following possibilities:
513 : a) neither of var + X and var + Y overflow or underflow, or both of
514 : them do. Then their difference is X - Y.
515 : b) var + X overflows, and var + Y does not. Then the values of the
516 : expressions are var + X - M and var + Y, where M is the range of
517 : the type, and their difference is X - Y - M.
518 : c) var + Y underflows and var + X does not. Their difference again
519 : is M - X + Y.
520 : Therefore, if the arithmetics in type does not overflow, then the
521 : bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
522 : Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
523 : (X - Y, X - Y + M). */
524 :
525 173139 : if (rel == 0)
526 : {
527 640 : mpz_set_ui (bnds->below, 0);
528 640 : mpz_set_ui (bnds->up, 0);
529 640 : return;
530 : }
531 :
532 172499 : auto_mpz m;
533 172499 : wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), m, UNSIGNED);
534 172499 : mpz_add_ui (m, m, 1);
535 172499 : mpz_sub (bnds->up, x, y);
536 172499 : mpz_set (bnds->below, bnds->up);
537 :
538 172499 : if (may_wrap)
539 : {
540 147536 : if (rel > 0)
541 146084 : mpz_sub (bnds->below, bnds->below, m);
542 : else
543 1452 : mpz_add (bnds->up, bnds->up, m);
544 : }
545 172499 : }
546 :
547 : /* From condition C0 CMP C1 derives information regarding the
548 : difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
549 : and stores it to BNDS. */
550 :
551 : static void
552 20056575 : refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
553 : tree vary, mpz_t offy,
554 : tree c0, enum tree_code cmp, tree c1,
555 : bounds *bnds)
556 : {
557 20056575 : tree varc0, varc1, ctype;
558 20056575 : mpz_t offc0, offc1, loffx, loffy, bnd;
559 20056575 : bool lbound = false;
560 20056575 : bool no_wrap = nowrap_type_p (type);
561 20056575 : bool x_ok, y_ok;
562 :
563 20056575 : switch (cmp)
564 : {
565 8518114 : case LT_EXPR:
566 8518114 : case LE_EXPR:
567 8518114 : case GT_EXPR:
568 8518114 : case GE_EXPR:
569 8518114 : STRIP_SIGN_NOPS (c0);
570 8518114 : STRIP_SIGN_NOPS (c1);
571 8518114 : ctype = TREE_TYPE (c0);
572 8518114 : if (!useless_type_conversion_p (ctype, type))
573 12912451 : return;
574 :
575 : break;
576 :
577 : case EQ_EXPR:
578 : /* We could derive quite precise information from EQ_EXPR, however, such
579 : a guard is unlikely to appear, so we do not bother with handling
580 : it. */
581 : return;
582 :
583 5550680 : case NE_EXPR:
584 : /* NE_EXPR comparisons do not contain much of useful information, except for
585 : special case of comparing with the bounds of the type. */
586 5550680 : if (TREE_CODE (c1) != INTEGER_CST
587 4819975 : || !INTEGRAL_TYPE_P (type))
588 : return;
589 :
590 : /* Ensure that the condition speaks about an expression in the same type
591 : as X and Y. */
592 4250494 : ctype = TREE_TYPE (c0);
593 4250494 : if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
594 : return;
595 2419561 : c0 = fold_convert (type, c0);
596 2419561 : c1 = fold_convert (type, c1);
597 :
598 2419561 : if (TYPE_MIN_VALUE (type)
599 2419561 : && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
600 : {
601 : cmp = GT_EXPR;
602 : break;
603 : }
604 1729338 : if (TYPE_MAX_VALUE (type)
605 1729338 : && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
606 : {
607 : cmp = LT_EXPR;
608 : break;
609 : }
610 :
611 : return;
612 : default:
613 : return;
614 : }
615 :
616 7144124 : mpz_init (offc0);
617 7144124 : mpz_init (offc1);
618 7144124 : split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
619 7144124 : split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
620 :
621 : /* We are only interested in comparisons of expressions based on VARX and
622 : VARY. TODO -- we might also be able to derive some bounds from
623 : expressions containing just one of the variables. */
624 :
625 7144124 : if (operand_equal_p (varx, varc1, 0))
626 : {
627 950312 : std::swap (varc0, varc1);
628 950312 : mpz_swap (offc0, offc1);
629 950312 : cmp = swap_tree_comparison (cmp);
630 : }
631 :
632 7144124 : if (!operand_equal_p (varx, varc0, 0)
633 7144124 : || !operand_equal_p (vary, varc1, 0))
634 5302207 : goto end;
635 :
636 1841917 : mpz_init_set (loffx, offx);
637 1841917 : mpz_init_set (loffy, offy);
638 :
639 1841917 : if (cmp == GT_EXPR || cmp == GE_EXPR)
640 : {
641 1756419 : std::swap (varx, vary);
642 1756419 : mpz_swap (offc0, offc1);
643 1756419 : mpz_swap (loffx, loffy);
644 1756419 : cmp = swap_tree_comparison (cmp);
645 1756419 : lbound = true;
646 : }
647 :
648 : /* If there is no overflow, the condition implies that
649 :
650 : (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
651 :
652 : The overflows and underflows may complicate things a bit; each
653 : overflow decreases the appropriate offset by M, and underflow
654 : increases it by M. The above inequality would not necessarily be
655 : true if
656 :
657 : -- VARX + OFFX underflows and VARX + OFFC0 does not, or
658 : VARX + OFFC0 overflows, but VARX + OFFX does not.
659 : This may only happen if OFFX < OFFC0.
660 : -- VARY + OFFY overflows and VARY + OFFC1 does not, or
661 : VARY + OFFC1 underflows and VARY + OFFY does not.
662 : This may only happen if OFFY > OFFC1. */
663 :
664 1841917 : if (no_wrap)
665 : {
666 : x_ok = true;
667 : y_ok = true;
668 : }
669 : else
670 : {
671 610161 : x_ok = (integer_zerop (varx)
672 610161 : || mpz_cmp (loffx, offc0) >= 0);
673 610161 : y_ok = (integer_zerop (vary)
674 610161 : || mpz_cmp (loffy, offc1) <= 0);
675 : }
676 :
677 607445 : if (x_ok && y_ok)
678 : {
679 1835233 : mpz_init (bnd);
680 1835233 : mpz_sub (bnd, loffx, loffy);
681 1835233 : mpz_add (bnd, bnd, offc1);
682 1835233 : mpz_sub (bnd, bnd, offc0);
683 :
684 1835233 : if (cmp == LT_EXPR)
685 1486562 : mpz_sub_ui (bnd, bnd, 1);
686 :
687 1835233 : if (lbound)
688 : {
689 1751010 : mpz_neg (bnd, bnd);
690 1751010 : if (mpz_cmp (bnds->below, bnd) < 0)
691 464707 : mpz_set (bnds->below, bnd);
692 : }
693 : else
694 : {
695 84223 : if (mpz_cmp (bnd, bnds->up) < 0)
696 4175 : mpz_set (bnds->up, bnd);
697 : }
698 1835233 : mpz_clear (bnd);
699 : }
700 :
701 1841917 : mpz_clear (loffx);
702 1841917 : mpz_clear (loffy);
703 7144124 : end:
704 7144124 : mpz_clear (offc0);
705 7144124 : mpz_clear (offc1);
706 : }
707 :
708 : /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
709 : The subtraction is considered to be performed in arbitrary precision,
710 : without overflows.
711 :
712 : We do not attempt to be too clever regarding the value ranges of X and
713 : Y; most of the time, they are just integers or ssa names offsetted by
714 : integer. However, we try to use the information contained in the
715 : comparisons before the loop (usually created by loop header copying). */
716 :
717 : static void
718 13056005 : bound_difference (class loop *loop, tree x, tree y, bounds *bnds)
719 : {
720 13056005 : tree type = TREE_TYPE (x);
721 13056005 : tree varx, vary;
722 13056005 : mpz_t offx, offy;
723 13056005 : int cnt = 0;
724 13056005 : edge e;
725 13056005 : basic_block bb;
726 13056005 : tree c0, c1;
727 13056005 : enum tree_code cmp;
728 :
729 : /* Get rid of unnecessary casts, but preserve the value of
730 : the expressions. */
731 13056005 : STRIP_SIGN_NOPS (x);
732 13056005 : STRIP_SIGN_NOPS (y);
733 :
734 13056005 : mpz_init (bnds->below);
735 13056005 : mpz_init (bnds->up);
736 13056005 : mpz_init (offx);
737 13056005 : mpz_init (offy);
738 13056005 : split_to_var_and_offset (x, &varx, offx);
739 13056005 : split_to_var_and_offset (y, &vary, offy);
740 :
741 13056005 : if (!integer_zerop (varx)
742 13056005 : && operand_equal_p (varx, vary, 0))
743 : {
744 : /* Special case VARX == VARY -- we just need to compare the
745 : offsets. The matters are a bit more complicated in the
746 : case addition of offsets may wrap. */
747 173139 : bound_difference_of_offsetted_base (type, offx, offy, bnds);
748 : }
749 : else
750 : {
751 : /* Otherwise, use the value ranges to determine the initial
752 : estimates on below and up. */
753 12882866 : auto_mpz minx, maxx, miny, maxy;
754 12882866 : determine_value_range (loop, type, varx, offx, minx, maxx);
755 12882866 : determine_value_range (loop, type, vary, offy, miny, maxy);
756 :
757 12882866 : mpz_sub (bnds->below, minx, maxy);
758 12882866 : mpz_sub (bnds->up, maxx, miny);
759 12882866 : }
760 :
761 : /* If both X and Y are constants, we cannot get any more precise. */
762 13056005 : if (integer_zerop (varx) && integer_zerop (vary))
763 7216551 : goto end;
764 :
765 : /* Now walk the dominators of the loop header and use the entry
766 : guards to refine the estimates. */
767 5839454 : for (bb = loop->header;
768 57884496 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
769 57884496 : && cnt < param_max_niter_dominators_walk;
770 52045042 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
771 : {
772 52045042 : if (!single_pred_p (bb))
773 24979098 : continue;
774 27065944 : e = single_pred_edge (bb);
775 :
776 27065944 : if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
777 7009369 : continue;
778 :
779 40113150 : gcond *cond = as_a <gcond *> (*gsi_last_bb (e->src));
780 20056575 : c0 = gimple_cond_lhs (cond);
781 20056575 : cmp = gimple_cond_code (cond);
782 20056575 : c1 = gimple_cond_rhs (cond);
783 :
784 20056575 : if (e->flags & EDGE_FALSE_VALUE)
785 11082964 : cmp = invert_tree_comparison (cmp, false);
786 :
787 20056575 : refine_bounds_using_guard (type, varx, offx, vary, offy,
788 : c0, cmp, c1, bnds);
789 20056575 : ++cnt;
790 : }
791 :
792 5839454 : end:
793 13056005 : mpz_clear (offx);
794 13056005 : mpz_clear (offy);
795 13056005 : }
796 :
797 : /* Update the bounds in BNDS that restrict the value of X to the bounds
798 : that restrict the value of X + DELTA. X can be obtained as a
799 : difference of two values in TYPE. */
800 :
801 : static void
802 2118892 : bounds_add (bounds *bnds, const widest_int &delta, tree type)
803 : {
804 2118892 : mpz_t mdelta, max;
805 :
806 2118892 : mpz_init (mdelta);
807 2118892 : wi::to_mpz (delta, mdelta, SIGNED);
808 :
809 2118892 : mpz_init (max);
810 2118892 : wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
811 :
812 2118892 : mpz_add (bnds->up, bnds->up, mdelta);
813 2118892 : mpz_add (bnds->below, bnds->below, mdelta);
814 :
815 2118892 : if (mpz_cmp (bnds->up, max) > 0)
816 121680 : mpz_set (bnds->up, max);
817 :
818 2118892 : mpz_neg (max, max);
819 2118892 : if (mpz_cmp (bnds->below, max) < 0)
820 9485 : mpz_set (bnds->below, max);
821 :
822 2118892 : mpz_clear (mdelta);
823 2118892 : mpz_clear (max);
824 2118892 : }
825 :
826 : /* Update the bounds in BNDS that restrict the value of X to the bounds
827 : that restrict the value of -X. */
828 :
829 : static void
830 2580295 : bounds_negate (bounds *bnds)
831 : {
832 2580295 : mpz_t tmp;
833 :
834 2580295 : mpz_init_set (tmp, bnds->up);
835 2580295 : mpz_neg (bnds->up, bnds->below);
836 2580295 : mpz_neg (bnds->below, tmp);
837 2580295 : mpz_clear (tmp);
838 2580295 : }
839 :
840 : /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
841 :
842 : static tree
843 176048 : inverse (tree x, tree mask)
844 : {
845 176048 : tree type = TREE_TYPE (x);
846 176048 : tree rslt;
847 176048 : unsigned ctr = tree_floor_log2 (mask);
848 :
849 176048 : if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
850 : {
851 176032 : unsigned HOST_WIDE_INT ix;
852 176032 : unsigned HOST_WIDE_INT imask;
853 176032 : unsigned HOST_WIDE_INT irslt = 1;
854 :
855 176032 : gcc_assert (cst_and_fits_in_hwi (x));
856 176032 : gcc_assert (cst_and_fits_in_hwi (mask));
857 :
858 176032 : ix = int_cst_value (x);
859 176032 : imask = int_cst_value (mask);
860 :
861 10016315 : for (; ctr; ctr--)
862 : {
863 9664251 : irslt *= ix;
864 9664251 : ix *= ix;
865 : }
866 176032 : irslt &= imask;
867 :
868 176032 : rslt = build_int_cst_type (type, irslt);
869 : }
870 : else
871 : {
872 16 : rslt = build_int_cst (type, 1);
873 2048 : for (; ctr; ctr--)
874 : {
875 2032 : rslt = int_const_binop (MULT_EXPR, rslt, x);
876 2032 : x = int_const_binop (MULT_EXPR, x, x);
877 : }
878 16 : rslt = int_const_binop (BIT_AND_EXPR, rslt, mask);
879 : }
880 :
881 176048 : return rslt;
882 : }
883 :
884 : /* Derives the upper bound BND on the number of executions of loop with exit
885 : condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
886 : the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
887 : that the loop ends through this exit, i.e., the induction variable ever
888 : reaches the value of C.
889 :
890 : The value C is equal to final - base, where final and base are the final and
891 : initial value of the actual induction variable in the analysed loop. BNDS
892 : bounds the value of this difference when computed in signed type with
893 : unbounded range, while the computation of C is performed in an unsigned
894 : type with the range matching the range of the type of the induction variable.
895 : In particular, BNDS.up contains an upper bound on C in the following cases:
896 : -- if the iv must reach its final value without overflow, i.e., if
897 : NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
898 : -- if final >= base, which we know to hold when BNDS.below >= 0. */
899 :
900 : static void
901 7613032 : number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
902 : bounds *bnds, bool exit_must_be_taken)
903 : {
904 7613032 : widest_int max;
905 7613032 : mpz_t d;
906 7613032 : tree type = TREE_TYPE (c);
907 15226064 : bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
908 7613032 : || mpz_sgn (bnds->below) >= 0);
909 :
910 7613032 : if (integer_onep (s)
911 874119 : || (TREE_CODE (c) == INTEGER_CST
912 341672 : && TREE_CODE (s) == INTEGER_CST
913 1216508 : && wi::mod_trunc (wi::to_wide (c), wi::to_wide (s),
914 8296376 : TYPE_SIGN (type)) == 0)
915 8146196 : || (TYPE_OVERFLOW_UNDEFINED (type)
916 0 : && multiple_of_p (type, c, s)))
917 : {
918 : /* If C is an exact multiple of S, then its value will be reached before
919 : the induction variable overflows (unless the loop is exited in some
920 : other way before). Note that the actual induction variable in the
921 : loop (which ranges from base to final instead of from 0 to C) may
922 : overflow, in which case BNDS.up will not be giving a correct upper
923 : bound on C; thus, BNDS_U_VALID had to be computed in advance. */
924 : no_overflow = true;
925 : exit_must_be_taken = true;
926 : }
927 :
928 : /* If the induction variable can overflow, the number of iterations is at
929 : most the period of the control variable (or infinite, but in that case
930 : the whole # of iterations analysis will fail). */
931 533164 : if (!no_overflow)
932 : {
933 126530 : max = wi::mask <widest_int> (TYPE_PRECISION (type)
934 126530 : - wi::ctz (wi::to_wide (s)), false);
935 63265 : wi::to_mpz (max, bnd, UNSIGNED);
936 63265 : return;
937 : }
938 :
939 : /* Now we know that the induction variable does not overflow, so the loop
940 : iterates at most (range of type / S) times. */
941 7549767 : wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), bnd, UNSIGNED);
942 :
943 : /* If the induction variable is guaranteed to reach the value of C before
944 : overflow, ... */
945 7549767 : if (exit_must_be_taken)
946 : {
947 : /* ... then we can strengthen this to C / S, and possibly we can use
948 : the upper bound on C given by BNDS. */
949 7299587 : if (TREE_CODE (c) == INTEGER_CST)
950 6389468 : wi::to_mpz (wi::to_wide (c), bnd, UNSIGNED);
951 910119 : else if (bnds_u_valid)
952 758643 : mpz_set (bnd, bnds->up);
953 : }
954 :
955 7549767 : mpz_init (d);
956 7549767 : wi::to_mpz (wi::to_wide (s), d, UNSIGNED);
957 7549767 : mpz_fdiv_q (bnd, bnd, d);
958 7549767 : mpz_clear (d);
959 7613032 : }
960 :
961 : /* Determines number of iterations of loop whose ending condition
962 : is IV <> FINAL. TYPE is the type of the iv. The number of
963 : iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
964 : we know that the exit must be taken eventually, i.e., that the IV
965 : ever reaches the value FINAL (we derived this earlier, and possibly set
966 : NITER->assumptions to make sure this is the case). BNDS contains the
967 : bounds on the difference FINAL - IV->base. */
968 :
969 : static bool
970 7613032 : number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv,
971 : tree final, class tree_niter_desc *niter,
972 : bool exit_must_be_taken, bounds *bnds)
973 : {
974 7613032 : tree niter_type = unsigned_type_for (type);
975 7613032 : tree s, c, d, bits, assumption, tmp, bound;
976 :
977 7613032 : niter->control = *iv;
978 7613032 : niter->bound = final;
979 7613032 : niter->cmp = NE_EXPR;
980 :
981 : /* Rearrange the terms so that we get inequality S * i <> C, with S
982 : positive. Also cast everything to the unsigned type. If IV does
983 : not overflow, BNDS bounds the value of C. Also, this is the
984 : case if the computation |FINAL - IV->base| does not overflow, i.e.,
985 : if BNDS->below in the result is nonnegative. */
986 7613032 : if (tree_int_cst_sign_bit (iv->step))
987 : {
988 2580295 : s = fold_build1 (NEGATE_EXPR, niter_type,
989 : fold_convert (niter_type, iv->step));
990 2580295 : c = fold_build2 (MINUS_EXPR, niter_type,
991 : fold_convert (niter_type, iv->base),
992 : fold_convert (niter_type, final));
993 2580295 : bounds_negate (bnds);
994 : }
995 : else
996 : {
997 5032737 : s = fold_convert (niter_type, iv->step);
998 5032737 : c = fold_build2 (MINUS_EXPR, niter_type,
999 : fold_convert (niter_type, final),
1000 : fold_convert (niter_type, iv->base));
1001 : }
1002 :
1003 7613032 : auto_mpz max;
1004 7613032 : number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
1005 : exit_must_be_taken);
1006 15226064 : niter->max = widest_int::from (wi::from_mpz (niter_type, max, false),
1007 15226064 : TYPE_SIGN (niter_type));
1008 :
1009 : /* Compute no-overflow information for the control iv. This can be
1010 : proven when below two conditions are satisfied:
1011 :
1012 : 1) IV evaluates toward FINAL at beginning, i.e:
1013 : base <= FINAL ; step > 0
1014 : base >= FINAL ; step < 0
1015 :
1016 : 2) |FINAL - base| is an exact multiple of step.
1017 :
1018 : Unfortunately, it's hard to prove above conditions after pass loop-ch
1019 : because loop with exit condition (IV != FINAL) usually will be guarded
1020 : by initial-condition (IV.base - IV.step != FINAL). In this case, we
1021 : can alternatively try to prove below conditions:
1022 :
1023 : 1') IV evaluates toward FINAL at beginning, i.e:
1024 : new_base = base - step < FINAL ; step > 0
1025 : && base - step doesn't underflow
1026 : new_base = base - step > FINAL ; step < 0
1027 : && base - step doesn't overflow
1028 :
1029 : Please refer to PR34114 as an example of loop-ch's impact.
1030 :
1031 : Note, for NE_EXPR, base equals to FINAL is a special case, in
1032 : which the loop exits immediately, and the iv does not overflow.
1033 :
1034 : Also note, we prove condition 2) by checking base and final separately
1035 : along with condition 1) or 1'). Since we ensure the difference
1036 : computation of c does not wrap with cond below and the adjusted s
1037 : will fit a signed type as well as an unsigned we can safely do
1038 : this using the type of the IV if it is not pointer typed. */
1039 7613032 : tree mtype = type;
1040 7613032 : if (POINTER_TYPE_P (type))
1041 614428 : mtype = niter_type;
1042 7613032 : if (!niter->control.no_overflow
1043 7613032 : && (integer_onep (s)
1044 207587 : || (multiple_of_p (mtype, fold_convert (mtype, iv->base),
1045 207587 : fold_convert (mtype, s), false)
1046 31342 : && multiple_of_p (mtype, fold_convert (mtype, final),
1047 31342 : fold_convert (mtype, s), false))))
1048 : {
1049 2432579 : tree t, cond, relaxed_cond = boolean_false_node;
1050 :
1051 2432579 : if (tree_int_cst_sign_bit (iv->step))
1052 : {
1053 2329528 : cond = fold_build2 (GE_EXPR, boolean_type_node, iv->base, final);
1054 2329528 : if (INTEGRAL_NB_TYPE_P (type))
1055 : {
1056 : /* Only when base - step doesn't overflow. */
1057 2329528 : t = TYPE_MAX_VALUE (type);
1058 2329528 : t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1059 2329528 : t = fold_build2 (GE_EXPR, boolean_type_node, t, iv->base);
1060 2329528 : if (integer_nonzerop (t))
1061 : {
1062 2170449 : t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1063 2170449 : relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node, t,
1064 : final);
1065 : }
1066 : }
1067 : }
1068 : else
1069 : {
1070 103051 : cond = fold_build2 (LE_EXPR, boolean_type_node, iv->base, final);
1071 103051 : if (INTEGRAL_NB_TYPE_P (type))
1072 : {
1073 : /* Only when base - step doesn't underflow. */
1074 103051 : t = TYPE_MIN_VALUE (type);
1075 103051 : t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1076 103051 : t = fold_build2 (LE_EXPR, boolean_type_node, t, iv->base);
1077 103051 : if (integer_nonzerop (t))
1078 : {
1079 63542 : t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1080 63542 : relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node, t,
1081 : final);
1082 : }
1083 : }
1084 : }
1085 :
1086 2432579 : t = simplify_using_initial_conditions (loop, cond);
1087 2432579 : if (!t || !integer_onep (t))
1088 65180 : t = simplify_using_initial_conditions (loop, relaxed_cond);
1089 :
1090 2432579 : if (t && integer_onep (t))
1091 : {
1092 2367909 : niter->control.no_overflow = true;
1093 2367909 : niter->niter = fold_build2 (EXACT_DIV_EXPR, niter_type, c, s);
1094 2367909 : return true;
1095 : }
1096 : }
1097 :
1098 : /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
1099 : is infinite. Otherwise, the number of iterations is
1100 : (inverse(s/d) * (c/d)) mod (size of mode/d). */
1101 5245123 : bits = num_ending_zeros (s);
1102 15735369 : bound = build_low_bits_mask (niter_type,
1103 5245123 : (TYPE_PRECISION (niter_type)
1104 5245123 : - tree_to_uhwi (bits)));
1105 :
1106 5245123 : d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
1107 : build_int_cst (niter_type, 1), bits);
1108 5245123 : s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
1109 :
1110 5245123 : if (!exit_must_be_taken)
1111 : {
1112 : /* If we cannot assume that the exit is taken eventually, record the
1113 : assumptions for divisibility of c. */
1114 1905884 : assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
1115 1905884 : assumption = fold_build2 (EQ_EXPR, boolean_type_node,
1116 : assumption, build_int_cst (niter_type, 0));
1117 1905884 : if (!integer_nonzerop (assumption))
1118 298512 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1119 : niter->assumptions, assumption);
1120 : }
1121 :
1122 5245123 : c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
1123 5245123 : if (integer_onep (s))
1124 : {
1125 5069075 : niter->niter = c;
1126 : }
1127 : else
1128 : {
1129 176048 : tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
1130 176048 : niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
1131 : }
1132 : return true;
1133 7613032 : }
1134 :
1135 : /* Checks whether we can determine the final value of the control variable
1136 : of the loop with ending condition IV0 < IV1 (computed in TYPE).
1137 : DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1138 : of the step. The assumptions necessary to ensure that the computation
1139 : of the final value does not overflow are recorded in NITER. If we
1140 : find the final value, we adjust DELTA and return TRUE. Otherwise
1141 : we return false. BNDS bounds the value of IV1->base - IV0->base,
1142 : and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
1143 : true if we know that the exit must be taken eventually. */
1144 :
1145 : static bool
1146 385180 : number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
1147 : class tree_niter_desc *niter,
1148 : tree *delta, tree step,
1149 : bool exit_must_be_taken, bounds *bnds)
1150 : {
1151 385180 : tree niter_type = TREE_TYPE (step);
1152 385180 : tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
1153 385180 : tree tmod;
1154 385180 : tree assumption = boolean_true_node, bound, noloop;
1155 385180 : bool fv_comp_no_overflow;
1156 385180 : tree type1 = type;
1157 385180 : if (POINTER_TYPE_P (type))
1158 127584 : type1 = sizetype;
1159 :
1160 385180 : if (TREE_CODE (mod) != INTEGER_CST)
1161 : return false;
1162 36346 : if (integer_nonzerop (mod))
1163 16560 : mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
1164 36346 : tmod = fold_convert (type1, mod);
1165 :
1166 36346 : auto_mpz mmod;
1167 36346 : wi::to_mpz (wi::to_wide (mod), mmod, UNSIGNED);
1168 36346 : mpz_neg (mmod, mmod);
1169 :
1170 : /* If the induction variable does not overflow and the exit is taken,
1171 : then the computation of the final value does not overflow. This is
1172 : also obviously the case if the new final value is equal to the
1173 : current one. Finally, we postulate this for pointer type variables,
1174 : as the code cannot rely on the object to that the pointer points being
1175 : placed at the end of the address space (and more pragmatically,
1176 : TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
1177 36346 : if (integer_zerop (mod) || POINTER_TYPE_P (type))
1178 : fv_comp_no_overflow = true;
1179 15846 : else if (!exit_must_be_taken)
1180 : fv_comp_no_overflow = false;
1181 : else
1182 7846 : fv_comp_no_overflow =
1183 7846 : (iv0->no_overflow && integer_nonzerop (iv0->step))
1184 8774 : || (iv1->no_overflow && integer_nonzerop (iv1->step));
1185 :
1186 36346 : if (integer_nonzerop (iv0->step))
1187 : {
1188 : /* The final value of the iv is iv1->base + MOD, assuming that this
1189 : computation does not overflow, and that
1190 : iv0->base <= iv1->base + MOD. */
1191 31545 : if (!fv_comp_no_overflow)
1192 : {
1193 5979 : bound = fold_build2 (MINUS_EXPR, type1,
1194 : TYPE_MAX_VALUE (type1), tmod);
1195 5979 : assumption = fold_build2 (LE_EXPR, boolean_type_node,
1196 : iv1->base, bound);
1197 5979 : if (integer_zerop (assumption))
1198 : return false;
1199 : }
1200 : }
1201 : else
1202 : {
1203 : /* The final value of the iv is iv0->base - MOD, assuming that this
1204 : computation does not overflow, and that
1205 : iv0->base - MOD <= iv1->base. */
1206 4801 : if (!fv_comp_no_overflow)
1207 : {
1208 2021 : bound = fold_build2 (PLUS_EXPR, type1,
1209 : TYPE_MIN_VALUE (type1), tmod);
1210 2021 : assumption = fold_build2 (GE_EXPR, boolean_type_node,
1211 : iv0->base, bound);
1212 2021 : if (integer_zerop (assumption))
1213 : return false;
1214 : }
1215 : }
1216 :
1217 : /* IV0 < IV1 does not loop if IV0->base >= IV1->base. */
1218 36290 : if (fv_comp_no_overflow && mpz_cmp (mmod, bnds->below) < 0)
1219 17221 : noloop = boolean_false_node;
1220 : else
1221 19069 : noloop = fold_build2 (GE_EXPR, boolean_type_node,
1222 : iv0->base, iv1->base);
1223 :
1224 36290 : if (!integer_nonzerop (assumption))
1225 434 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1226 : niter->assumptions,
1227 : assumption);
1228 36290 : if (!integer_zerop (noloop))
1229 3714 : niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1230 : niter->may_be_zero,
1231 : noloop);
1232 36290 : bounds_add (bnds, wi::to_widest (mod), type);
1233 36290 : *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
1234 :
1235 36290 : return true;
1236 36346 : }
1237 :
1238 : /* Add assertions to NITER that ensure that the control variable of the loop
1239 : with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
1240 : are TYPE. Returns false if we can prove that there is an overflow, true
1241 : otherwise. STEP is the absolute value of the step. */
1242 :
1243 : static bool
1244 348890 : assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1245 : class tree_niter_desc *niter, tree step)
1246 : {
1247 348890 : tree bound, d, assumption, diff;
1248 348890 : tree niter_type = TREE_TYPE (step);
1249 :
1250 348890 : if (integer_nonzerop (iv0->step))
1251 : {
1252 : /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1253 286148 : if (iv0->no_overflow)
1254 : return true;
1255 :
1256 : /* If iv0->base is a constant, we can determine the last value before
1257 : overflow precisely; otherwise we conservatively assume
1258 : MAX - STEP + 1. */
1259 :
1260 46617 : if (TREE_CODE (iv0->base) == INTEGER_CST)
1261 : {
1262 15802 : d = fold_build2 (MINUS_EXPR, niter_type,
1263 : fold_convert (niter_type, TYPE_MAX_VALUE (type)),
1264 : fold_convert (niter_type, iv0->base));
1265 15802 : diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
1266 : }
1267 : else
1268 30815 : diff = fold_build2 (MINUS_EXPR, niter_type, step,
1269 : build_int_cst (niter_type, 1));
1270 46617 : bound = fold_build2 (MINUS_EXPR, type,
1271 : TYPE_MAX_VALUE (type), fold_convert (type, diff));
1272 46617 : assumption = fold_build2 (LE_EXPR, boolean_type_node,
1273 : iv1->base, bound);
1274 : }
1275 : else
1276 : {
1277 : /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1278 62742 : if (iv1->no_overflow)
1279 : return true;
1280 :
1281 31443 : if (TREE_CODE (iv1->base) == INTEGER_CST)
1282 : {
1283 56 : d = fold_build2 (MINUS_EXPR, niter_type,
1284 : fold_convert (niter_type, iv1->base),
1285 : fold_convert (niter_type, TYPE_MIN_VALUE (type)));
1286 56 : diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
1287 : }
1288 : else
1289 31387 : diff = fold_build2 (MINUS_EXPR, niter_type, step,
1290 : build_int_cst (niter_type, 1));
1291 31443 : bound = fold_build2 (PLUS_EXPR, type,
1292 : TYPE_MIN_VALUE (type), fold_convert (type, diff));
1293 31443 : assumption = fold_build2 (GE_EXPR, boolean_type_node,
1294 : iv0->base, bound);
1295 : }
1296 :
1297 78060 : if (integer_zerop (assumption))
1298 : return false;
1299 77994 : if (!integer_nonzerop (assumption))
1300 55751 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1301 : niter->assumptions, assumption);
1302 :
1303 77994 : iv0->no_overflow = true;
1304 77994 : iv1->no_overflow = true;
1305 77994 : return true;
1306 : }
1307 :
1308 : /* Add an assumption to NITER that a loop whose ending condition
1309 : is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
1310 : bounds the value of IV1->base - IV0->base. */
1311 :
1312 : static void
1313 348824 : assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1314 : class tree_niter_desc *niter, bounds *bnds)
1315 : {
1316 348824 : tree assumption = boolean_true_node, bound, diff;
1317 348824 : tree mbz, mbzl, mbzr, type1;
1318 348824 : bool rolls_p, no_overflow_p;
1319 348824 : widest_int dstep;
1320 348824 : mpz_t mstep, max;
1321 :
1322 : /* We are going to compute the number of iterations as
1323 : (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1324 : variant of TYPE. This formula only works if
1325 :
1326 : -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1327 :
1328 : (where MAX is the maximum value of the unsigned variant of TYPE, and
1329 : the computations in this formula are performed in full precision,
1330 : i.e., without overflows).
1331 :
1332 : Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1333 : we have a condition of the form iv0->base - step < iv1->base before the loop,
1334 : and for loops iv0->base < iv1->base - step * i the condition
1335 : iv0->base < iv1->base + step, due to loop header copying, which enable us
1336 : to prove the lower bound.
1337 :
1338 : The upper bound is more complicated. Unless the expressions for initial
1339 : and final value themselves contain enough information, we usually cannot
1340 : derive it from the context. */
1341 :
1342 : /* First check whether the answer does not follow from the bounds we gathered
1343 : before. */
1344 348824 : if (integer_nonzerop (iv0->step))
1345 286146 : dstep = wi::to_widest (iv0->step);
1346 : else
1347 : {
1348 62678 : dstep = wi::sext (wi::to_widest (iv1->step), TYPE_PRECISION (type));
1349 62678 : dstep = -dstep;
1350 : }
1351 :
1352 348824 : mpz_init (mstep);
1353 348824 : wi::to_mpz (dstep, mstep, UNSIGNED);
1354 348824 : mpz_neg (mstep, mstep);
1355 348824 : mpz_add_ui (mstep, mstep, 1);
1356 :
1357 348824 : rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
1358 :
1359 348824 : mpz_init (max);
1360 348824 : wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
1361 348824 : mpz_add (max, max, mstep);
1362 697648 : no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
1363 : /* For pointers, only values lying inside a single object
1364 : can be compared or manipulated by pointer arithmetics.
1365 : Gcc in general does not allow or handle objects larger
1366 : than half of the address space, hence the upper bound
1367 : is satisfied for pointers. */
1368 348824 : || POINTER_TYPE_P (type));
1369 348824 : mpz_clear (mstep);
1370 348824 : mpz_clear (max);
1371 :
1372 348824 : if (rolls_p && no_overflow_p)
1373 128172 : return;
1374 :
1375 220652 : type1 = type;
1376 220652 : if (POINTER_TYPE_P (type))
1377 68191 : type1 = sizetype;
1378 :
1379 : /* Now the hard part; we must formulate the assumption(s) as expressions, and
1380 : we must be careful not to introduce overflow. */
1381 :
1382 220652 : if (integer_nonzerop (iv0->step))
1383 : {
1384 179230 : diff = fold_build2 (MINUS_EXPR, type1,
1385 : iv0->step, build_int_cst (type1, 1));
1386 :
1387 : /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1388 : 0 address never belongs to any object, we can assume this for
1389 : pointers. */
1390 179230 : if (!POINTER_TYPE_P (type))
1391 : {
1392 115044 : bound = fold_build2 (PLUS_EXPR, type1,
1393 : TYPE_MIN_VALUE (type), diff);
1394 115044 : assumption = fold_build2 (GE_EXPR, boolean_type_node,
1395 : iv0->base, bound);
1396 : }
1397 :
1398 : /* And then we can compute iv0->base - diff, and compare it with
1399 : iv1->base. */
1400 179230 : mbzl = fold_build2 (MINUS_EXPR, type1,
1401 : fold_convert (type1, iv0->base), diff);
1402 179230 : mbzr = fold_convert (type1, iv1->base);
1403 : }
1404 : else
1405 : {
1406 41422 : diff = fold_build2 (PLUS_EXPR, type1,
1407 : iv1->step, build_int_cst (type1, 1));
1408 :
1409 41422 : if (!POINTER_TYPE_P (type))
1410 : {
1411 37417 : bound = fold_build2 (PLUS_EXPR, type1,
1412 : TYPE_MAX_VALUE (type), diff);
1413 37417 : assumption = fold_build2 (LE_EXPR, boolean_type_node,
1414 : iv1->base, bound);
1415 : }
1416 :
1417 41422 : mbzl = fold_convert (type1, iv0->base);
1418 41422 : mbzr = fold_build2 (MINUS_EXPR, type1,
1419 : fold_convert (type1, iv1->base), diff);
1420 : }
1421 :
1422 220652 : if (!integer_nonzerop (assumption))
1423 93625 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1424 : niter->assumptions, assumption);
1425 220652 : if (!rolls_p)
1426 : {
1427 203851 : mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1428 203851 : niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1429 : niter->may_be_zero, mbz);
1430 : }
1431 348824 : }
1432 :
1433 : /* Determines number of iterations of loop whose ending condition
1434 : is IV0 < IV1 which likes: {base, -C} < n, or n < {base, C}.
1435 : The number of iterations is stored to NITER. */
1436 :
1437 : static bool
1438 66654 : number_of_iterations_until_wrap (class loop *loop, tree type, affine_iv *iv0,
1439 : affine_iv *iv1, class tree_niter_desc *niter)
1440 : {
1441 66654 : tree niter_type = unsigned_type_for (type);
1442 66654 : tree step, num, assumptions, may_be_zero, span;
1443 66654 : wide_int high, low, max, min;
1444 :
1445 66654 : may_be_zero = fold_build2 (LE_EXPR, boolean_type_node, iv1->base, iv0->base);
1446 66654 : if (integer_onep (may_be_zero))
1447 : return false;
1448 :
1449 66440 : int prec = TYPE_PRECISION (type);
1450 66440 : signop sgn = TYPE_SIGN (type);
1451 66440 : min = wi::min_value (prec, sgn);
1452 66440 : max = wi::max_value (prec, sgn);
1453 :
1454 : /* n < {base, C}. */
1455 66440 : if (integer_zerop (iv0->step) && !tree_int_cst_sign_bit (iv1->step))
1456 : {
1457 : /* MIN + C - 1 <= n. */
1458 41536 : tree last = wide_int_to_tree (type, min + wi::to_wide (iv1->step) - 1);
1459 41536 : assumptions = fold_build2 (LE_EXPR, boolean_type_node, last, iv0->base);
1460 41536 : if (integer_zerop (assumptions))
1461 : return false;
1462 :
1463 41534 : step = fold_convert (niter_type, iv1->step);
1464 41534 : num = fold_build2 (MINUS_EXPR, niter_type,
1465 : wide_int_to_tree (niter_type, max),
1466 : fold_convert (niter_type, iv1->base));
1467 :
1468 : /* When base has the form iv + 1, if we know iv >= n, then iv + 1 < n
1469 : only when iv + 1 overflows, i.e. when iv == TYPE_VALUE_MAX. */
1470 41534 : if (sgn == UNSIGNED
1471 6248 : && integer_onep (step)
1472 1081 : && TREE_CODE (iv1->base) == PLUS_EXPR
1473 42211 : && integer_onep (TREE_OPERAND (iv1->base, 1)))
1474 : {
1475 471 : tree cond = fold_build2 (GE_EXPR, boolean_type_node,
1476 : TREE_OPERAND (iv1->base, 0), iv0->base);
1477 471 : cond = simplify_using_initial_conditions (loop, cond);
1478 471 : if (integer_onep (cond))
1479 31 : may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node,
1480 : TREE_OPERAND (iv1->base, 0),
1481 : TYPE_MAX_VALUE (type));
1482 : }
1483 :
1484 41534 : high = max;
1485 41534 : if (TREE_CODE (iv1->base) == INTEGER_CST)
1486 28760 : low = wi::to_wide (iv1->base) - 1;
1487 12774 : else if (TREE_CODE (iv0->base) == INTEGER_CST)
1488 6260 : low = wi::to_wide (iv0->base);
1489 : else
1490 6514 : low = min;
1491 : }
1492 : /* {base, -C} < n. */
1493 24904 : else if (tree_int_cst_sign_bit (iv0->step) && integer_zerop (iv1->step))
1494 : {
1495 : /* MAX + (-C) + 1 >= n. */
1496 24904 : tree last = wide_int_to_tree (type, max + wi::to_wide (iv0->step) + 1);
1497 24904 : assumptions = fold_build2 (GE_EXPR, boolean_type_node, last, iv1->base);
1498 24904 : if (integer_zerop (assumptions))
1499 : return false;
1500 :
1501 24902 : step = fold_build1 (NEGATE_EXPR, niter_type,
1502 : fold_convert (niter_type, iv0->step));
1503 24902 : num = fold_build2 (MINUS_EXPR, niter_type,
1504 : fold_convert (niter_type, iv0->base),
1505 : wide_int_to_tree (niter_type, min));
1506 24902 : low = min;
1507 24902 : if (TREE_CODE (iv0->base) == INTEGER_CST)
1508 1320 : high = wi::to_wide (iv0->base) + 1;
1509 23582 : else if (TREE_CODE (iv1->base) == INTEGER_CST)
1510 2326 : high = wi::to_wide (iv1->base);
1511 : else
1512 21256 : high = max;
1513 : }
1514 : else
1515 : return false;
1516 :
1517 : /* (delta + step - 1) / step */
1518 66436 : num = fold_build2 (PLUS_EXPR, niter_type, num, step);
1519 66436 : niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, num, step);
1520 :
1521 66436 : widest_int delta, s;
1522 66436 : delta = widest_int::from (high, sgn) - widest_int::from (low, sgn);
1523 66436 : s = wi::to_widest (step);
1524 66436 : delta = delta + s - 1;
1525 66436 : niter->max = wi::udiv_floor (delta, s);
1526 :
1527 66436 : niter->may_be_zero = may_be_zero;
1528 :
1529 66436 : if (!integer_nonzerop (assumptions))
1530 8786 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1531 : niter->assumptions, assumptions);
1532 :
1533 66436 : niter->control.no_overflow = false;
1534 :
1535 : /* Update bound and exit condition as:
1536 : bound = niter * STEP + (IVbase - STEP).
1537 : { IVbase - STEP, +, STEP } != bound
1538 : Here, biasing IVbase by 1 step makes 'bound' be the value before wrap.
1539 : */
1540 66436 : tree base_type = TREE_TYPE (niter->control.base);
1541 66436 : if (POINTER_TYPE_P (base_type))
1542 : {
1543 6126 : tree utype = unsigned_type_for (base_type);
1544 6126 : niter->control.base
1545 6126 : = fold_build2 (MINUS_EXPR, utype,
1546 : fold_convert (utype, niter->control.base),
1547 : fold_convert (utype, niter->control.step));
1548 6126 : niter->control.base = fold_convert (base_type, niter->control.base);
1549 : }
1550 : else
1551 60310 : niter->control.base
1552 60310 : = fold_build2 (MINUS_EXPR, base_type, niter->control.base,
1553 : niter->control.step);
1554 :
1555 66436 : span = fold_build2 (MULT_EXPR, niter_type, niter->niter,
1556 : fold_convert (niter_type, niter->control.step));
1557 66436 : niter->bound = fold_build2 (PLUS_EXPR, niter_type, span,
1558 : fold_convert (niter_type, niter->control.base));
1559 66436 : niter->bound = fold_convert (type, niter->bound);
1560 66436 : niter->cmp = NE_EXPR;
1561 :
1562 66436 : return true;
1563 66654 : }
1564 :
1565 : /* Determines number of iterations of loop whose ending condition
1566 : is IV0 < IV1. TYPE is the type of the iv. The number of
1567 : iterations is stored to NITER. BNDS bounds the difference
1568 : IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1569 : that the exit must be taken eventually. */
1570 :
1571 : static bool
1572 5479245 : number_of_iterations_lt (class loop *loop, tree type, affine_iv *iv0,
1573 : affine_iv *iv1, class tree_niter_desc *niter,
1574 : bool exit_must_be_taken, bounds *bnds)
1575 : {
1576 5479245 : tree niter_type = unsigned_type_for (type);
1577 5479245 : tree delta, step, s;
1578 5479245 : mpz_t mstep, tmp;
1579 :
1580 5479245 : if (integer_nonzerop (iv0->step))
1581 : {
1582 5144707 : niter->control = *iv0;
1583 5144707 : niter->cmp = LT_EXPR;
1584 5144707 : niter->bound = iv1->base;
1585 : }
1586 : else
1587 : {
1588 334538 : niter->control = *iv1;
1589 334538 : niter->cmp = GT_EXPR;
1590 334538 : niter->bound = iv0->base;
1591 : }
1592 :
1593 : /* {base, -C} < n, or n < {base, C} */
1594 5479245 : if (tree_int_cst_sign_bit (iv0->step)
1595 5479245 : || (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step)))
1596 66654 : return number_of_iterations_until_wrap (loop, type, iv0, iv1, niter);
1597 :
1598 5412591 : delta = fold_build2 (MINUS_EXPR, niter_type,
1599 : fold_convert (niter_type, iv1->base),
1600 : fold_convert (niter_type, iv0->base));
1601 :
1602 : /* First handle the special case that the step is +-1. */
1603 10214701 : if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1604 5412591 : || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1605 : {
1606 : /* for (i = iv0->base; i < iv1->base; i++)
1607 :
1608 : or
1609 :
1610 : for (i = iv1->base; i > iv0->base; i--).
1611 :
1612 : In both cases # of iterations is iv1->base - iv0->base, assuming that
1613 : iv1->base >= iv0->base.
1614 :
1615 : First try to derive a lower bound on the value of
1616 : iv1->base - iv0->base, computed in full precision. If the difference
1617 : is nonnegative, we are done, otherwise we must record the
1618 : condition. */
1619 :
1620 5027411 : if (mpz_sgn (bnds->below) < 0)
1621 1878254 : niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1622 : iv1->base, iv0->base);
1623 5027411 : niter->niter = delta;
1624 10054822 : niter->max = widest_int::from (wi::from_mpz (niter_type, bnds->up, false),
1625 10054822 : TYPE_SIGN (niter_type));
1626 5027411 : niter->control.no_overflow = true;
1627 5027411 : return true;
1628 : }
1629 :
1630 385180 : if (integer_nonzerop (iv0->step))
1631 317693 : step = fold_convert (niter_type, iv0->step);
1632 : else
1633 67487 : step = fold_build1 (NEGATE_EXPR, niter_type,
1634 : fold_convert (niter_type, iv1->step));
1635 :
1636 : /* If we can determine the final value of the control iv exactly, we can
1637 : transform the condition to != comparison. In particular, this will be
1638 : the case if DELTA is constant. */
1639 385180 : if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1640 : exit_must_be_taken, bnds))
1641 : {
1642 36290 : affine_iv zps;
1643 :
1644 36290 : zps.base = build_int_cst (niter_type, 0);
1645 36290 : zps.step = step;
1646 : /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1647 : zps does not overflow. */
1648 36290 : zps.no_overflow = true;
1649 :
1650 36290 : return number_of_iterations_ne (loop, type, &zps,
1651 : delta, niter, true, bnds);
1652 : }
1653 :
1654 : /* Make sure that the control iv does not overflow. */
1655 348890 : if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1656 : return false;
1657 :
1658 : /* We determine the number of iterations as (delta + step - 1) / step. For
1659 : this to work, we must know that iv1->base >= iv0->base - step + 1,
1660 : otherwise the loop does not roll. */
1661 348824 : assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1662 :
1663 348824 : s = fold_build2 (MINUS_EXPR, niter_type,
1664 : step, build_int_cst (niter_type, 1));
1665 348824 : delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1666 348824 : niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1667 :
1668 348824 : mpz_init (mstep);
1669 348824 : mpz_init (tmp);
1670 348824 : wi::to_mpz (wi::to_wide (step), mstep, UNSIGNED);
1671 348824 : mpz_add (tmp, bnds->up, mstep);
1672 348824 : mpz_sub_ui (tmp, tmp, 1);
1673 348824 : mpz_fdiv_q (tmp, tmp, mstep);
1674 697648 : niter->max = widest_int::from (wi::from_mpz (niter_type, tmp, false),
1675 697648 : TYPE_SIGN (niter_type));
1676 348824 : mpz_clear (mstep);
1677 348824 : mpz_clear (tmp);
1678 :
1679 348824 : return true;
1680 : }
1681 :
1682 : /* Determines number of iterations of loop whose ending condition
1683 : is IV0 <= IV1. TYPE is the type of the iv. The number of
1684 : iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1685 : we know that this condition must eventually become false (we derived this
1686 : earlier, and possibly set NITER->assumptions to make sure this
1687 : is the case). BNDS bounds the difference IV1->base - IV0->base. */
1688 :
1689 : static bool
1690 2082620 : number_of_iterations_le (class loop *loop, tree type, affine_iv *iv0,
1691 : affine_iv *iv1, class tree_niter_desc *niter,
1692 : bool exit_must_be_taken, bounds *bnds)
1693 : {
1694 2082620 : tree assumption;
1695 2082620 : tree type1 = type;
1696 2082620 : if (POINTER_TYPE_P (type))
1697 6163 : type1 = sizetype;
1698 :
1699 : /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1700 : IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1701 : value of the type. This we must know anyway, since if it is
1702 : equal to this value, the loop rolls forever. We do not check
1703 : this condition for pointer type ivs, as the code cannot rely on
1704 : the object to that the pointer points being placed at the end of
1705 : the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1706 : not defined for pointers). */
1707 :
1708 2082620 : if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1709 : {
1710 648270 : if (integer_nonzerop (iv0->step))
1711 584321 : assumption = fold_build2 (NE_EXPR, boolean_type_node,
1712 : iv1->base, TYPE_MAX_VALUE (type));
1713 : else
1714 63949 : assumption = fold_build2 (NE_EXPR, boolean_type_node,
1715 : iv0->base, TYPE_MIN_VALUE (type));
1716 :
1717 648270 : if (integer_zerop (assumption))
1718 : return false;
1719 648252 : if (!integer_nonzerop (assumption))
1720 254833 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1721 : niter->assumptions, assumption);
1722 : }
1723 :
1724 2082602 : if (integer_nonzerop (iv0->step))
1725 : {
1726 1985865 : if (POINTER_TYPE_P (type))
1727 1238 : iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1728 : else
1729 1984627 : iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1730 : build_int_cst (type1, 1));
1731 : }
1732 96737 : else if (POINTER_TYPE_P (type))
1733 4925 : iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1734 : else
1735 91812 : iv0->base = fold_build2 (MINUS_EXPR, type1,
1736 : iv0->base, build_int_cst (type1, 1));
1737 :
1738 2082602 : bounds_add (bnds, 1, type1);
1739 :
1740 2082602 : return number_of_iterations_lt (loop, type, iv0, iv1, niter, exit_must_be_taken,
1741 2082602 : bnds);
1742 : }
1743 :
1744 : /* Dumps description of affine induction variable IV to FILE. */
1745 :
1746 : static void
1747 93862 : dump_affine_iv (FILE *file, affine_iv *iv)
1748 : {
1749 93862 : if (!integer_zerop (iv->step))
1750 46931 : fprintf (file, "[");
1751 :
1752 93862 : print_generic_expr (file, iv->base, TDF_SLIM);
1753 :
1754 93862 : if (!integer_zerop (iv->step))
1755 : {
1756 46931 : fprintf (file, ", + , ");
1757 46931 : print_generic_expr (file, iv->step, TDF_SLIM);
1758 83587 : fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1759 : }
1760 93862 : }
1761 :
1762 : DEBUG_FUNCTION void
1763 0 : debug (affine_iv *iv)
1764 : {
1765 0 : dump_affine_iv (stderr, iv);
1766 0 : fputc ('\n', stderr);
1767 0 : }
1768 :
1769 : /* Determine the number of iterations according to condition (for staying
1770 : inside loop) which compares two induction variables using comparison
1771 : operator CODE. The induction variable on left side of the comparison
1772 : is IV0, the right-hand side is IV1. Both induction variables must have
1773 : type TYPE, which must be an integer or pointer type. The steps of the
1774 : ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1775 :
1776 : LOOP is the loop whose number of iterations we are determining.
1777 :
1778 : ONLY_EXIT is true if we are sure this is the only way the loop could be
1779 : exited (including possibly non-returning function calls, exceptions, etc.)
1780 : -- in this case we can use the information whether the control induction
1781 : variables can overflow or not in a more efficient way.
1782 :
1783 : if EVERY_ITERATION is true, we know the test is executed on every iteration.
1784 :
1785 : The results (number of iterations and assumptions as described in
1786 : comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1787 : Returns false if it fails to determine number of iterations, true if it
1788 : was determined (possibly with some assumptions). */
1789 :
1790 : static bool
1791 13292124 : number_of_iterations_cond (class loop *loop,
1792 : tree type, affine_iv *iv0, enum tree_code code,
1793 : affine_iv *iv1, class tree_niter_desc *niter,
1794 : bool only_exit, bool every_iteration)
1795 : {
1796 13292124 : bool exit_must_be_taken = false, ret;
1797 13292124 : bounds bnds;
1798 :
1799 : /* If the test is not executed every iteration, wrapping may make the test
1800 : to pass again.
1801 : TODO: the overflow case can be still used as unreliable estimate of upper
1802 : bound. But we have no API to pass it down to number of iterations code
1803 : and, at present, it will not use it anyway. */
1804 13292124 : if (!every_iteration
1805 66672 : && (!iv0->no_overflow || !iv1->no_overflow
1806 44513 : || code == NE_EXPR || code == EQ_EXPR))
1807 : return false;
1808 :
1809 : /* The meaning of these assumptions is this:
1810 : if !assumptions
1811 : then the rest of information does not have to be valid
1812 : if may_be_zero then the loop does not roll, even if
1813 : niter != 0. */
1814 13246223 : niter->assumptions = boolean_true_node;
1815 13246223 : niter->may_be_zero = boolean_false_node;
1816 13246223 : niter->niter = NULL_TREE;
1817 13246223 : niter->max = 0;
1818 13246223 : niter->bound = NULL_TREE;
1819 13246223 : niter->cmp = ERROR_MARK;
1820 :
1821 : /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1822 : the control variable is on lhs. */
1823 13246223 : if (code == GE_EXPR || code == GT_EXPR
1824 13246223 : || (code == NE_EXPR && integer_zerop (iv0->step)))
1825 : {
1826 3095874 : std::swap (iv0, iv1);
1827 3095874 : code = swap_tree_comparison (code);
1828 : }
1829 :
1830 13246223 : if (POINTER_TYPE_P (type))
1831 : {
1832 : /* Comparison of pointers is undefined unless both iv0 and iv1 point
1833 : to the same object. If they do, the control variable cannot wrap
1834 : (as wrap around the bounds of memory will never return a pointer
1835 : that would be guaranteed to point to the same object, even if we
1836 : avoid undefined behavior by casting to size_t and back). */
1837 797162 : iv0->no_overflow = true;
1838 797162 : iv1->no_overflow = true;
1839 : }
1840 :
1841 : /* If the control induction variable does not overflow and the only exit
1842 : from the loop is the one that we analyze, we know it must be taken
1843 : eventually. */
1844 13246223 : if (only_exit)
1845 : {
1846 8657709 : if (!integer_zerop (iv0->step) && iv0->no_overflow)
1847 : exit_must_be_taken = true;
1848 2181338 : else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1849 6636959 : exit_must_be_taken = true;
1850 : }
1851 :
1852 : /* We can handle cases which neither of the sides of the comparison is
1853 : invariant:
1854 :
1855 : {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1856 : as if:
1857 : {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1858 :
1859 : provided that either below condition is satisfied:
1860 :
1861 : a) the test is NE_EXPR;
1862 : b) iv0 and iv1 do not overflow and iv0.step - iv1.step is of
1863 : the same sign and of less or equal magnitude than iv0.step
1864 :
1865 : This rarely occurs in practice, but it is simple enough to manage. */
1866 13246223 : if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1867 : {
1868 5540 : tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1869 5540 : tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
1870 : iv0->step, iv1->step);
1871 :
1872 : /* For code other than NE_EXPR we have to ensure moving the evolution
1873 : of IV1 to that of IV0 does not introduce overflow. */
1874 5540 : if (TREE_CODE (step) != INTEGER_CST
1875 5540 : || !iv0->no_overflow || !iv1->no_overflow)
1876 : {
1877 1279 : if (code != NE_EXPR)
1878 : return false;
1879 0 : iv0->no_overflow = false;
1880 : }
1881 : /* If the new step of IV0 has changed sign or is of greater
1882 : magnitude then we do not know whether IV0 does overflow
1883 : and thus the transform is not valid for code other than NE_EXPR. */
1884 4261 : else if (tree_int_cst_sign_bit (step) != tree_int_cst_sign_bit (iv0->step)
1885 7926 : || wi::gtu_p (wi::abs (wi::to_widest (step)),
1886 11591 : wi::abs (wi::to_widest (iv0->step))))
1887 : {
1888 2988 : if (POINTER_TYPE_P (type) && code != NE_EXPR)
1889 : /* For relational pointer compares we have further guarantees
1890 : that the pointers always point to the same object (or one
1891 : after it) and that objects do not cross the zero page. So
1892 : not only is the transform always valid for relational
1893 : pointer compares, we also know the resulting IV does not
1894 : overflow. */
1895 : ;
1896 813 : else if (code != NE_EXPR)
1897 : return false;
1898 : else
1899 450 : iv0->no_overflow = false;
1900 : }
1901 :
1902 3448 : iv0->step = step;
1903 3448 : iv1->step = build_int_cst (step_type, 0);
1904 3448 : iv1->no_overflow = true;
1905 : }
1906 :
1907 : /* If the result of the comparison is a constant, the loop is weird. More
1908 : precise handling would be possible, but the situation is not common enough
1909 : to waste time on it. */
1910 13244131 : if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1911 : return false;
1912 :
1913 : /* If the loop exits immediately, there is nothing to do. */
1914 13145669 : tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
1915 13145669 : if (tem && integer_zerop (tem))
1916 : {
1917 89664 : if (!every_iteration)
1918 : return false;
1919 89601 : niter->niter = build_int_cst (unsigned_type_for (type), 0);
1920 89601 : niter->max = 0;
1921 89601 : return true;
1922 : }
1923 :
1924 : /* OK, now we know we have a senseful loop. Handle several cases, depending
1925 : on what comparison operator is used. */
1926 13056005 : bound_difference (loop, iv1->base, iv0->base, &bnds);
1927 :
1928 13056005 : if (dump_file && (dump_flags & TDF_DETAILS))
1929 : {
1930 46931 : fprintf (dump_file,
1931 : "Analyzing # of iterations of loop %d\n", loop->num);
1932 :
1933 46931 : fprintf (dump_file, " exit condition ");
1934 46931 : dump_affine_iv (dump_file, iv0);
1935 56424 : fprintf (dump_file, " %s ",
1936 : code == NE_EXPR ? "!="
1937 9493 : : code == LT_EXPR ? "<"
1938 : : "<=");
1939 46931 : dump_affine_iv (dump_file, iv1);
1940 46931 : fprintf (dump_file, "\n");
1941 :
1942 46931 : fprintf (dump_file, " bounds on difference of bases: ");
1943 46931 : mpz_out_str (dump_file, 10, bnds.below);
1944 46931 : fprintf (dump_file, " ... ");
1945 46931 : mpz_out_str (dump_file, 10, bnds.up);
1946 46931 : fprintf (dump_file, "\n");
1947 : }
1948 :
1949 13056005 : switch (code)
1950 : {
1951 7576742 : case NE_EXPR:
1952 7576742 : gcc_assert (integer_zerop (iv1->step));
1953 7576742 : ret = number_of_iterations_ne (loop, type, iv0, iv1->base, niter,
1954 : exit_must_be_taken, &bnds);
1955 7576742 : break;
1956 :
1957 3396643 : case LT_EXPR:
1958 3396643 : ret = number_of_iterations_lt (loop, type, iv0, iv1, niter,
1959 : exit_must_be_taken, &bnds);
1960 3396643 : break;
1961 :
1962 2082620 : case LE_EXPR:
1963 2082620 : ret = number_of_iterations_le (loop, type, iv0, iv1, niter,
1964 : exit_must_be_taken, &bnds);
1965 2082620 : break;
1966 :
1967 0 : default:
1968 0 : gcc_unreachable ();
1969 : }
1970 :
1971 13056005 : mpz_clear (bnds.up);
1972 13056005 : mpz_clear (bnds.below);
1973 :
1974 13056005 : if (dump_file && (dump_flags & TDF_DETAILS))
1975 : {
1976 46931 : if (ret)
1977 : {
1978 46931 : fprintf (dump_file, " result:\n");
1979 46931 : if (!integer_nonzerop (niter->assumptions))
1980 : {
1981 303 : fprintf (dump_file, " under assumptions ");
1982 303 : print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1983 303 : fprintf (dump_file, "\n");
1984 : }
1985 :
1986 46931 : if (!integer_zerop (niter->may_be_zero))
1987 : {
1988 715 : fprintf (dump_file, " zero if ");
1989 715 : print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1990 715 : fprintf (dump_file, "\n");
1991 : }
1992 :
1993 46931 : fprintf (dump_file, " # of iterations ");
1994 46931 : print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1995 46931 : fprintf (dump_file, ", bounded by ");
1996 46931 : print_decu (niter->max, dump_file);
1997 46931 : fprintf (dump_file, "\n");
1998 : }
1999 : else
2000 0 : fprintf (dump_file, " failed\n\n");
2001 : }
2002 : return ret;
2003 : }
2004 :
2005 : /* Return an expression that computes the popcount of src. */
2006 :
2007 : static tree
2008 3587 : build_popcount_expr (tree src)
2009 : {
2010 3587 : tree fn;
2011 3587 : bool use_ifn = false;
2012 3587 : int prec = TYPE_PRECISION (TREE_TYPE (src));
2013 3587 : int i_prec = TYPE_PRECISION (integer_type_node);
2014 3587 : int li_prec = TYPE_PRECISION (long_integer_type_node);
2015 3587 : int lli_prec = TYPE_PRECISION (long_long_integer_type_node);
2016 :
2017 3587 : tree utype = unsigned_type_for (TREE_TYPE (src));
2018 3587 : src = fold_convert (utype, src);
2019 :
2020 3587 : if (direct_internal_fn_supported_p (IFN_POPCOUNT, utype, OPTIMIZE_FOR_BOTH))
2021 : use_ifn = true;
2022 3536 : else if (prec <= i_prec)
2023 3460 : fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
2024 76 : else if (prec == li_prec)
2025 59 : fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL);
2026 17 : else if (prec == lli_prec || prec == 2 * lli_prec)
2027 17 : fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL);
2028 : else
2029 : return NULL_TREE;
2030 :
2031 3587 : tree call;
2032 3536 : if (use_ifn)
2033 51 : call = build_call_expr_internal_loc (UNKNOWN_LOCATION, IFN_POPCOUNT,
2034 : integer_type_node, 1, src);
2035 3536 : else if (prec == 2 * lli_prec)
2036 : {
2037 17 : tree src1 = fold_convert (long_long_unsigned_type_node,
2038 : fold_build2 (RSHIFT_EXPR, TREE_TYPE (src),
2039 : unshare_expr (src),
2040 : build_int_cst (integer_type_node,
2041 : lli_prec)));
2042 17 : tree src2 = fold_convert (long_long_unsigned_type_node, src);
2043 17 : tree call1 = build_call_expr (fn, 1, src1);
2044 17 : tree call2 = build_call_expr (fn, 1, src2);
2045 17 : call = fold_build2 (PLUS_EXPR, integer_type_node, call1, call2);
2046 : }
2047 : else
2048 : {
2049 3519 : if (prec < i_prec)
2050 293 : src = fold_convert (unsigned_type_node, src);
2051 :
2052 3519 : call = build_call_expr (fn, 1, src);
2053 : }
2054 :
2055 : return call;
2056 : }
2057 :
2058 : /* Utility function to check if OP is defined by a stmt
2059 : that is a val - 1. */
2060 :
2061 : static bool
2062 137844 : ssa_defined_by_minus_one_stmt_p (tree op, tree val)
2063 : {
2064 137844 : gimple *stmt;
2065 137844 : return (TREE_CODE (op) == SSA_NAME
2066 89231 : && (stmt = SSA_NAME_DEF_STMT (op))
2067 89231 : && is_gimple_assign (stmt)
2068 76289 : && (gimple_assign_rhs_code (stmt) == PLUS_EXPR)
2069 10471 : && val == gimple_assign_rhs1 (stmt)
2070 141886 : && integer_minus_onep (gimple_assign_rhs2 (stmt)));
2071 : }
2072 :
2073 : /* See comment below for number_of_iterations_bitcount.
2074 : For popcount, we have:
2075 :
2076 : modify:
2077 : _1 = iv_1 + -1
2078 : iv_2 = iv_1 & _1
2079 :
2080 : test:
2081 : if (iv != 0)
2082 :
2083 : modification count:
2084 : popcount (src)
2085 :
2086 : */
2087 :
2088 : static bool
2089 3898607 : number_of_iterations_popcount (loop_p loop, const_edge exit,
2090 : enum tree_code code,
2091 : class tree_niter_desc *niter)
2092 : {
2093 3898607 : bool modify_before_test = true;
2094 3898607 : HOST_WIDE_INT max;
2095 :
2096 : /* Check that condition for staying inside the loop is like
2097 : if (iv != 0). */
2098 7797214 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
2099 3898607 : if (!cond_stmt
2100 3898607 : || code != NE_EXPR
2101 1935426 : || !integer_zerop (gimple_cond_rhs (cond_stmt))
2102 5279368 : || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME)
2103 : return false;
2104 :
2105 1380761 : tree iv_2 = gimple_cond_lhs (cond_stmt);
2106 1380761 : gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2107 1380761 : gimple *test_phi = NULL;
2108 :
2109 : /* If the test comes before the iv modification, then these will actually be
2110 : iv_1 and a phi node. */
2111 1380761 : if (gimple_code (iv_2_stmt) == GIMPLE_PHI
2112 393327 : && gimple_bb (iv_2_stmt) == loop->header
2113 298915 : && gimple_phi_num_args (iv_2_stmt) == 2
2114 1679676 : && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt,
2115 : loop_latch_edge (loop)->dest_idx))
2116 : == SSA_NAME))
2117 : {
2118 : /* iv_2 is actually one of the inputs to the phi. */
2119 275892 : test_phi = iv_2_stmt;
2120 275892 : iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx);
2121 275892 : iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2122 275892 : modify_before_test = false;
2123 : }
2124 :
2125 : /* Make sure iv_2_stmt is an and stmt (iv_2 = _1 & iv_1). */
2126 1380761 : if (!is_gimple_assign (iv_2_stmt)
2127 1380761 : || gimple_assign_rhs_code (iv_2_stmt) != BIT_AND_EXPR)
2128 : return false;
2129 :
2130 69973 : tree iv_1 = gimple_assign_rhs1 (iv_2_stmt);
2131 69973 : tree _1 = gimple_assign_rhs2 (iv_2_stmt);
2132 :
2133 : /* Check that _1 is defined by (_1 = iv_1 + -1).
2134 : Also make sure that _1 is the same in and_stmt and _1 defining stmt.
2135 : Also canonicalize if _1 and _b11 are reversed. */
2136 69973 : if (ssa_defined_by_minus_one_stmt_p (iv_1, _1))
2137 : std::swap (iv_1, _1);
2138 67871 : else if (ssa_defined_by_minus_one_stmt_p (_1, iv_1))
2139 : ;
2140 : else
2141 : return false;
2142 :
2143 : /* Check the recurrence. A test before the modification must test the
2144 : PHI of the recurrence. */
2145 3811 : gimple *phi = SSA_NAME_DEF_STMT (iv_1);
2146 3811 : if (gimple_code (phi) != GIMPLE_PHI
2147 3811 : || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
2148 3792 : || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))
2149 7603 : || (test_phi && phi != test_phi))
2150 : return false;
2151 :
2152 : /* We found a match. */
2153 3587 : tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
2154 3587 : int src_precision = TYPE_PRECISION (TREE_TYPE (src));
2155 :
2156 : /* Get the corresponding popcount builtin. */
2157 3587 : tree expr = build_popcount_expr (src);
2158 :
2159 3587 : if (!expr)
2160 : return false;
2161 :
2162 3587 : max = src_precision;
2163 :
2164 3587 : tree may_be_zero = boolean_false_node;
2165 :
2166 3587 : if (modify_before_test)
2167 : {
2168 1735 : expr = fold_build2 (MINUS_EXPR, integer_type_node, expr,
2169 : integer_one_node);
2170 1735 : max = max - 1;
2171 1735 : may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
2172 : build_zero_cst (TREE_TYPE (src)));
2173 : }
2174 :
2175 3587 : expr = fold_convert (unsigned_type_node, expr);
2176 :
2177 3587 : niter->assumptions = boolean_true_node;
2178 3587 : niter->may_be_zero = simplify_using_initial_conditions (loop, may_be_zero);
2179 3587 : niter->niter = simplify_using_initial_conditions(loop, expr);
2180 :
2181 3587 : if (TREE_CODE (niter->niter) == INTEGER_CST)
2182 411 : niter->max = tree_to_uhwi (niter->niter);
2183 : else
2184 3176 : niter->max = max;
2185 :
2186 3587 : niter->bound = NULL_TREE;
2187 3587 : niter->cmp = ERROR_MARK;
2188 3587 : return true;
2189 : }
2190 :
2191 : /* Return an expression that counts the leading/trailing zeroes of src.
2192 :
2193 : If define_at_zero is true, then the built expression will be defined to
2194 : return the precision of src when src == 0 (using the second argument of
2195 : the internal function or a conditional expression).
2196 : Otherwise, the result for src == 0 is undefined. */
2197 :
2198 : static tree
2199 10037 : build_cltz_expr (tree src, bool leading, bool define_at_zero)
2200 : {
2201 10037 : tree fn;
2202 10037 : internal_fn ifn = leading ? IFN_CLZ : IFN_CTZ;
2203 10037 : bool use_ifn = false;
2204 10037 : int prec = TYPE_PRECISION (TREE_TYPE (src));
2205 10037 : int i_prec = TYPE_PRECISION (integer_type_node);
2206 10037 : int li_prec = TYPE_PRECISION (long_integer_type_node);
2207 10037 : int lli_prec = TYPE_PRECISION (long_long_integer_type_node);
2208 :
2209 10037 : tree utype = unsigned_type_for (TREE_TYPE (src));
2210 10037 : src = fold_convert (utype, src);
2211 :
2212 10037 : if (direct_internal_fn_supported_p (ifn, utype, OPTIMIZE_FOR_BOTH))
2213 : use_ifn = true;
2214 3522 : else if (prec <= i_prec)
2215 1728 : fn = leading ? builtin_decl_implicit (BUILT_IN_CLZ)
2216 13559 : : builtin_decl_implicit (BUILT_IN_CTZ);
2217 1794 : else if (prec == li_prec)
2218 0 : fn = leading ? builtin_decl_implicit (BUILT_IN_CLZL)
2219 13559 : : builtin_decl_implicit (BUILT_IN_CTZL);
2220 1794 : else if (prec == lli_prec || prec == 2 * lli_prec)
2221 1794 : fn = leading ? builtin_decl_implicit (BUILT_IN_CLZLL)
2222 13559 : : builtin_decl_implicit (BUILT_IN_CTZLL);
2223 : else
2224 : return NULL_TREE;
2225 :
2226 10037 : tree call;
2227 3522 : if (use_ifn)
2228 : {
2229 6515 : tree arg2 = (define_at_zero
2230 6515 : ? build_int_cst (integer_type_node, prec) : NULL_TREE);
2231 10152 : call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn,
2232 : integer_type_node, arg2 ? 2 : 1,
2233 : src, arg2);
2234 : }
2235 3522 : else if (fn == NULL_TREE)
2236 : return NULL_TREE;
2237 3522 : else if (prec == 2 * lli_prec)
2238 : {
2239 844 : tree src1 = fold_convert (long_long_unsigned_type_node,
2240 : fold_build2 (RSHIFT_EXPR, TREE_TYPE (src),
2241 : unshare_expr (src),
2242 : build_int_cst (integer_type_node,
2243 : lli_prec)));
2244 844 : tree src2 = fold_convert (long_long_unsigned_type_node, src);
2245 : /* We count the zeroes in src1, and add the number in src2 when src1
2246 : is 0. */
2247 844 : if (!leading)
2248 0 : std::swap (src1, src2);
2249 844 : tree call1 = build_call_expr (fn, 1, src1);
2250 844 : tree call2 = build_call_expr (fn, 1, src2);
2251 844 : if (define_at_zero)
2252 : {
2253 250 : tree is_zero2 = fold_build2 (NE_EXPR, boolean_type_node, src2,
2254 : build_zero_cst (TREE_TYPE (src2)));
2255 250 : call2 = fold_build3 (COND_EXPR, integer_type_node, is_zero2, call2,
2256 : build_int_cst (integer_type_node, lli_prec));
2257 : }
2258 844 : tree is_zero1 = fold_build2 (NE_EXPR, boolean_type_node, src1,
2259 : build_zero_cst (TREE_TYPE (src1)));
2260 844 : call = fold_build3 (COND_EXPR, integer_type_node, is_zero1, call1,
2261 : fold_build2 (PLUS_EXPR, integer_type_node, call2,
2262 : build_int_cst (integer_type_node,
2263 : lli_prec)));
2264 : }
2265 : else
2266 : {
2267 2678 : if (prec < i_prec)
2268 1728 : src = fold_convert (unsigned_type_node, src);
2269 :
2270 2678 : call = build_call_expr (fn, 1, src);
2271 2678 : if (leading && prec < i_prec)
2272 1547 : call = fold_build2 (MINUS_EXPR, integer_type_node, call,
2273 : build_int_cst (integer_type_node, i_prec - prec));
2274 2678 : if (define_at_zero)
2275 : {
2276 : /* SRC can be a shift, so do not share it with the call. */
2277 938 : tree is_zero = fold_build2 (NE_EXPR, boolean_type_node,
2278 : unshare_expr (src),
2279 : build_zero_cst (TREE_TYPE (src)));
2280 938 : call = fold_build3 (COND_EXPR, integer_type_node, is_zero, call,
2281 : build_int_cst (integer_type_node, prec));
2282 : }
2283 : }
2284 :
2285 : return call;
2286 : }
2287 :
2288 : /* Returns true if STMT is equivalent to x << 1. */
2289 :
2290 : static bool
2291 1169448 : is_lshift_by_1 (gassign *stmt)
2292 : {
2293 1169448 : if (gimple_assign_rhs_code (stmt) == LSHIFT_EXPR
2294 1170907 : && integer_onep (gimple_assign_rhs2 (stmt)))
2295 : return true;
2296 1168561 : if (gimple_assign_rhs_code (stmt) == MULT_EXPR
2297 1338 : && tree_fits_shwi_p (gimple_assign_rhs2 (stmt))
2298 1169581 : && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)
2299 227 : return true;
2300 : return false;
2301 : }
2302 :
2303 : /* Returns true if STMT is equivalent to x >> 1. */
2304 :
2305 : static bool
2306 1168334 : is_rshift_by_1 (gassign *stmt)
2307 : {
2308 1168334 : if (gimple_assign_rhs_code (stmt) == RSHIFT_EXPR
2309 1192508 : && integer_onep (gimple_assign_rhs2 (stmt)))
2310 : return true;
2311 2095246 : if (trunc_or_exact_div_p (gimple_assign_rhs_code (stmt))
2312 1296 : && tree_fits_shwi_p (gimple_assign_rhs2 (stmt))
2313 1156767 : && tree_to_shwi (gimple_assign_rhs2 (stmt)) == 2)
2314 102 : return true;
2315 : return false;
2316 : }
2317 :
2318 : /* Helper for number_of_iterations_cltz that uses ranger to determine
2319 : if SRC's range, shifted left (when LEFT_SHIFT is true) or right
2320 : by NUM_IGNORED_BITS, is guaranteed to be != 0 on LOOP's preheader
2321 : edge.
2322 : Return true if so or false otherwise. */
2323 :
2324 : static bool
2325 1321 : shifted_range_nonzero_p (loop_p loop, tree src,
2326 : bool left_shift, int num_ignored_bits)
2327 : {
2328 1321 : int_range_max r (TREE_TYPE (src));
2329 1321 : gcc_assert (num_ignored_bits >= 0);
2330 :
2331 1321 : if (get_range_query (cfun)->range_on_edge
2332 1321 : (r, loop_preheader_edge (loop), src)
2333 1321 : && !r.varying_p ()
2334 2070 : && !r.undefined_p ())
2335 : {
2336 745 : if (num_ignored_bits)
2337 : {
2338 689 : range_op_handler op (left_shift ? LSHIFT_EXPR : RSHIFT_EXPR);
2339 443 : int_range_max shifted_range (TREE_TYPE (src));
2340 443 : wide_int shift_count = wi::shwi (num_ignored_bits,
2341 443 : TYPE_PRECISION (TREE_TYPE
2342 443 : (src)));
2343 443 : int_range_max shift_amount
2344 443 : (TREE_TYPE (src), shift_count, shift_count);
2345 :
2346 443 : if (op.fold_range (shifted_range, TREE_TYPE (src), r,
2347 : shift_amount))
2348 443 : r = shifted_range;
2349 443 : }
2350 :
2351 : /* If the range does not contain zero we are good. */
2352 745 : if (!range_includes_zero_p (r))
2353 498 : return true;
2354 : }
2355 :
2356 : return false;
2357 1321 : }
2358 :
2359 :
2360 : /* See comment below for number_of_iterations_bitcount.
2361 : For c[lt]z, we have:
2362 :
2363 : modify:
2364 : iv_2 = iv_1 << 1 OR iv_1 >> 1
2365 :
2366 : test:
2367 : if (iv & 1 << (prec-1)) OR (iv & 1)
2368 :
2369 : modification count:
2370 : src precision - c[lt]z (src)
2371 :
2372 : */
2373 :
2374 : static bool
2375 7174417 : number_of_iterations_cltz (loop_p loop, const_edge exit,
2376 : enum tree_code code,
2377 : class tree_niter_desc *niter)
2378 : {
2379 7174417 : bool modify_before_test = true;
2380 7174417 : HOST_WIDE_INT max;
2381 7174417 : int checked_bit;
2382 7174417 : tree iv_2;
2383 :
2384 : /* Check that condition for staying inside the loop is like
2385 : if (iv == 0). */
2386 14348834 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
2387 7174417 : if (!cond_stmt
2388 7174417 : || (code != EQ_EXPR && code != GE_EXPR)
2389 3594966 : || !integer_zerop (gimple_cond_rhs (cond_stmt))
2390 1367880 : || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME)
2391 : return false;
2392 :
2393 1367837 : if (code == EQ_EXPR)
2394 : {
2395 : /* Make sure we check a bitwise and with a suitable constant */
2396 1228851 : gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond_stmt));
2397 1228851 : if (!is_gimple_assign (and_stmt)
2398 758039 : || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR
2399 141807 : || !integer_pow2p (gimple_assign_rhs2 (and_stmt))
2400 1248570 : || TREE_CODE (gimple_assign_rhs1 (and_stmt)) != SSA_NAME)
2401 : return false;
2402 :
2403 19719 : checked_bit = tree_log2 (gimple_assign_rhs2 (and_stmt));
2404 :
2405 19719 : iv_2 = gimple_assign_rhs1 (and_stmt);
2406 : }
2407 : else
2408 : {
2409 : /* We have a GE_EXPR - a signed comparison with zero is equivalent to
2410 : testing the leading bit, so check for this pattern too. */
2411 :
2412 138986 : iv_2 = gimple_cond_lhs (cond_stmt);
2413 138986 : tree test_value_type = TREE_TYPE (iv_2);
2414 :
2415 138986 : if (TYPE_UNSIGNED (test_value_type))
2416 : return false;
2417 :
2418 138986 : gimple *test_value_stmt = SSA_NAME_DEF_STMT (iv_2);
2419 :
2420 138986 : if (is_gimple_assign (test_value_stmt)
2421 138986 : && gimple_assign_rhs_code (test_value_stmt) == NOP_EXPR)
2422 : {
2423 : /* If the test value comes from a NOP_EXPR, then we need to unwrap
2424 : this. We conservatively require that both types have the same
2425 : precision. */
2426 5408 : iv_2 = gimple_assign_rhs1 (test_value_stmt);
2427 5408 : tree rhs_type = TREE_TYPE (iv_2);
2428 5408 : if (TREE_CODE (iv_2) != SSA_NAME
2429 5408 : || !INTEGRAL_NB_TYPE_P (rhs_type)
2430 10805 : || (TYPE_PRECISION (rhs_type)
2431 5397 : != TYPE_PRECISION (test_value_type)))
2432 : return false;
2433 : }
2434 :
2435 138573 : checked_bit = TYPE_PRECISION (test_value_type) - 1;
2436 : }
2437 :
2438 158292 : gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2439 158292 : gimple *test_phi = NULL;
2440 :
2441 : /* If the test comes before the iv modification, then these will actually be
2442 : iv_1 and a phi node. */
2443 158292 : if (gimple_code (iv_2_stmt) == GIMPLE_PHI
2444 25978 : && gimple_bb (iv_2_stmt) == loop->header
2445 14949 : && gimple_phi_num_args (iv_2_stmt) == 2
2446 173241 : && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt,
2447 : loop_latch_edge (loop)->dest_idx))
2448 : == SSA_NAME))
2449 : {
2450 : /* iv_2 is actually one of the inputs to the phi. */
2451 14850 : test_phi = iv_2_stmt;
2452 14850 : iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx);
2453 14850 : iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2454 14850 : modify_before_test = false;
2455 : }
2456 :
2457 : /* Make sure iv_2_stmt is a logical shift by one stmt:
2458 : iv_2 = iv_1 {<<|>>} 1 */
2459 158292 : if (!is_gimple_assign (iv_2_stmt))
2460 : return false;
2461 128577 : bool left_shift = false;
2462 256645 : if (!((left_shift = is_lshift_by_1 (as_a <gassign *> (iv_2_stmt)))
2463 128068 : || is_rshift_by_1 (as_a <gassign *> (iv_2_stmt))))
2464 : return false;
2465 :
2466 2243 : tree iv_1 = gimple_assign_rhs1 (iv_2_stmt);
2467 :
2468 : /* Check the recurrence. A test before the modification must test the
2469 : PHI of the recurrence. */
2470 2243 : gimple *phi = SSA_NAME_DEF_STMT (iv_1);
2471 2243 : if (gimple_code (phi) != GIMPLE_PHI
2472 2180 : || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
2473 2174 : || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))
2474 4417 : || (test_phi && phi != test_phi))
2475 : return false;
2476 :
2477 : /* We found a match. */
2478 1969 : tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
2479 :
2480 : /* If the type is signed, verify via Ranger on the preheader edge
2481 : that the initial value entering the loop is non-negative. */
2482 1969 : if (!TYPE_UNSIGNED (TREE_TYPE (src)))
2483 : {
2484 1037 : int_range_max r (TREE_TYPE (src));
2485 1037 : edge e = loop_preheader_edge (loop);
2486 2074 : if (!get_range_query (cfun)->range_on_edge (r, e, src)
2487 1037 : || r.undefined_p ()
2488 2074 : || !r.nonnegative_p ())
2489 648 : return false;
2490 1037 : }
2491 :
2492 1321 : int src_precision = TYPE_PRECISION (TREE_TYPE (src));
2493 :
2494 : /* Save the original SSA name before preprocessing for ranger queries. */
2495 1321 : tree unshifted_src = src;
2496 :
2497 : /* Apply any needed preprocessing to src. */
2498 1321 : int num_ignored_bits;
2499 1321 : if (left_shift)
2500 382 : num_ignored_bits = src_precision - checked_bit - 1;
2501 : else
2502 : num_ignored_bits = checked_bit;
2503 :
2504 1321 : if (modify_before_test)
2505 575 : num_ignored_bits++;
2506 :
2507 1321 : if (num_ignored_bits != 0)
2508 1245 : src = fold_build2 (left_shift ? LSHIFT_EXPR : RSHIFT_EXPR,
2509 : TREE_TYPE (src), src,
2510 : build_int_cst (integer_type_node, num_ignored_bits));
2511 :
2512 : /* Get the corresponding c[lt]z builtin. */
2513 1321 : tree expr = build_cltz_expr (src, left_shift, false);
2514 :
2515 1321 : if (!expr)
2516 : return false;
2517 :
2518 1321 : max = src_precision - num_ignored_bits - 1;
2519 :
2520 1321 : expr = fold_convert (unsigned_type_node, expr);
2521 :
2522 : /* If the copy-header (ch) pass peeled one iteration we're shifting
2523 : SRC by preprocessing it above.
2524 :
2525 : A loop like
2526 : if (bits)
2527 : {
2528 : while (!(bits & 1))
2529 : {
2530 : bits >>= 1;
2531 : cnt += 1;
2532 : }
2533 : return cnt;
2534 : }
2535 : ch (roughly) transforms into:
2536 : if (bits)
2537 : {
2538 : if (!(bits & 1)
2539 : {
2540 : do
2541 : {
2542 : bits >>= 1;
2543 : cnt += 1;
2544 : } while (!(bits & 1));
2545 : }
2546 : else
2547 : cnt = 1;
2548 : return cnt;
2549 : }
2550 :
2551 : Then, our preprocessed SRC (that is used for c[tl]z computation)
2552 : will be bits >> 1, and the assumption is bits >> 1 != 0. */
2553 :
2554 1321 : tree assumptions;
2555 1321 : if (shifted_range_nonzero_p (loop, unshifted_src,
2556 : left_shift, num_ignored_bits))
2557 498 : assumptions = boolean_true_node;
2558 : else
2559 : {
2560 : /* If ranger couldn't prove the assumption, try
2561 : simplify_using_initial_conditions. */
2562 823 : assumptions = fold_build2 (NE_EXPR, boolean_type_node, src,
2563 : build_zero_cst (TREE_TYPE (src)));
2564 823 : assumptions = simplify_using_initial_conditions (loop, assumptions);
2565 : }
2566 :
2567 1321 : niter->assumptions = assumptions;
2568 1321 : niter->may_be_zero = boolean_false_node;
2569 1321 : niter->niter = simplify_using_initial_conditions (loop, expr);
2570 :
2571 1321 : if (TREE_CODE (niter->niter) == INTEGER_CST)
2572 100 : niter->max = tree_to_uhwi (niter->niter);
2573 : else
2574 1221 : niter->max = max;
2575 :
2576 1321 : niter->bound = NULL_TREE;
2577 1321 : niter->cmp = ERROR_MARK;
2578 :
2579 1321 : return true;
2580 : }
2581 :
2582 : /* See comment below for number_of_iterations_bitcount.
2583 : For c[lt]z complement, we have:
2584 :
2585 : modify:
2586 : iv_2 = iv_1 >> 1 OR iv_1 << 1
2587 :
2588 : test:
2589 : if (iv != 0)
2590 :
2591 : modification count:
2592 : src precision - c[lt]z (src)
2593 :
2594 : */
2595 :
2596 : static bool
2597 3894941 : number_of_iterations_cltz_complement (loop_p loop, const_edge exit,
2598 : enum tree_code code,
2599 : class tree_niter_desc *niter)
2600 : {
2601 3894941 : bool modify_before_test = true;
2602 3894941 : HOST_WIDE_INT max;
2603 :
2604 : /* Check that condition for staying inside the loop is like
2605 : if (iv != 0). */
2606 7789882 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
2607 3894941 : if (!cond_stmt
2608 3894941 : || code != NE_EXPR
2609 1931839 : || !integer_zerop (gimple_cond_rhs (cond_stmt))
2610 5272115 : || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME)
2611 : return false;
2612 :
2613 1377174 : tree iv_2 = gimple_cond_lhs (cond_stmt);
2614 1377174 : gimple *iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2615 1377174 : gimple *test_phi = NULL;
2616 :
2617 : /* If the test comes before the iv modification, then these will actually be
2618 : iv_1 and a phi node. */
2619 1377174 : if (gimple_code (iv_2_stmt) == GIMPLE_PHI
2620 391475 : && gimple_bb (iv_2_stmt) == loop->header
2621 297063 : && gimple_phi_num_args (iv_2_stmt) == 2
2622 1674237 : && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt,
2623 : loop_latch_edge (loop)->dest_idx))
2624 : == SSA_NAME))
2625 : {
2626 : /* iv_2 is actually one of the inputs to the phi. */
2627 274040 : test_phi = iv_2_stmt;
2628 274040 : iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx);
2629 274040 : iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2630 274040 : modify_before_test = false;
2631 : }
2632 :
2633 : /* Make sure iv_2_stmt is a logical shift by one stmt:
2634 : iv_2 = iv_1 {>>|<<} 1 */
2635 1377174 : if (!is_gimple_assign (iv_2_stmt))
2636 : return false;
2637 1040871 : bool left_shift = false;
2638 2081137 : if (!((left_shift = is_lshift_by_1 (as_a <gassign *> (iv_2_stmt)))
2639 1040266 : || is_rshift_by_1 (as_a <gassign *> (iv_2_stmt))))
2640 : return false;
2641 :
2642 11538 : tree iv_1 = gimple_assign_rhs1 (iv_2_stmt);
2643 :
2644 : /* Check the recurrence. A test before the modification must test the
2645 : PHI of the recurrence. */
2646 11538 : gimple *phi = SSA_NAME_DEF_STMT (iv_1);
2647 11538 : if (gimple_code (phi) != GIMPLE_PHI
2648 10793 : || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
2649 9620 : || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))
2650 20905 : || (test_phi && phi != test_phi))
2651 : return false;
2652 :
2653 : /* We found a match. */
2654 9162 : tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
2655 :
2656 : /* If the type is signed, verify via Ranger on the preheader edge
2657 : that the initial value entering the loop is non-negative. */
2658 9162 : if (!TYPE_UNSIGNED (TREE_TYPE (src)))
2659 : {
2660 920 : int_range_max r (TREE_TYPE (src));
2661 920 : edge e = loop_preheader_edge (loop);
2662 1840 : if (!get_range_query (cfun)->range_on_edge (r, e, src)
2663 920 : || r.undefined_p ()
2664 1840 : || !r.nonnegative_p ())
2665 446 : return false;
2666 920 : }
2667 :
2668 8716 : int src_precision = TYPE_PRECISION (TREE_TYPE (src));
2669 :
2670 8716 : tree src_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
2671 : build_zero_cst (TREE_TYPE (src)));
2672 8716 : bool src_nonzero
2673 8716 : = integer_zerop (simplify_using_initial_conditions (loop, src_zero));
2674 :
2675 : /* If the IV is modified before the test, the first value tested is SRC
2676 : shifted by one. If SRC can be zero, count the zeros of that value
2677 : instead of subtracting one from the count of SRC. Then the result is
2678 : also right for a zero SRC. */
2679 8716 : tree count_src = src;
2680 8716 : if (modify_before_test && !src_nonzero)
2681 : {
2682 3252 : tree utype = unsigned_type_for (TREE_TYPE (src));
2683 6487 : count_src = fold_build2 (left_shift ? LSHIFT_EXPR : RSHIFT_EXPR, utype,
2684 : fold_convert (utype, src), integer_one_node);
2685 : }
2686 :
2687 : /* Get the corresponding c[lt]z builtin. It needs a value at zero only
2688 : if its argument can be zero. */
2689 8716 : tree expr = build_cltz_expr (count_src, !left_shift, !src_nonzero);
2690 :
2691 8716 : if (!expr)
2692 : return false;
2693 :
2694 8716 : expr = fold_build2 (MINUS_EXPR, integer_type_node,
2695 : build_int_cst (integer_type_node, src_precision),
2696 : expr);
2697 :
2698 8716 : max = src_precision;
2699 :
2700 8716 : if (modify_before_test)
2701 : {
2702 7008 : if (src_nonzero)
2703 3756 : expr = fold_build2 (MINUS_EXPR, integer_type_node, expr,
2704 : integer_one_node);
2705 7008 : max = max - 1;
2706 : }
2707 :
2708 8716 : expr = fold_convert (unsigned_type_node, expr);
2709 :
2710 8716 : niter->assumptions = boolean_true_node;
2711 8716 : niter->may_be_zero = boolean_false_node;
2712 8716 : niter->niter = simplify_using_initial_conditions (loop, expr);
2713 :
2714 8716 : if (TREE_CODE (niter->niter) == INTEGER_CST)
2715 69 : niter->max = tree_to_uhwi (niter->niter);
2716 : else
2717 8647 : niter->max = max;
2718 :
2719 8716 : niter->bound = NULL_TREE;
2720 8716 : niter->cmp = ERROR_MARK;
2721 8716 : return true;
2722 : }
2723 :
2724 : /* See if LOOP contains a bit counting idiom. The idiom consists of two parts:
2725 : 1. A modification to the induction variabler;.
2726 : 2. A test to determine whether or not to exit the loop.
2727 :
2728 : These can come in either order - i.e.:
2729 :
2730 : <bb 3>
2731 : iv_1 = PHI <src(2), iv_2(4)>
2732 : if (test (iv_1))
2733 : goto <bb 4>
2734 : else
2735 : goto <bb 5>
2736 :
2737 : <bb 4>
2738 : iv_2 = modify (iv_1)
2739 : goto <bb 3>
2740 :
2741 : OR
2742 :
2743 : <bb 3>
2744 : iv_1 = PHI <src(2), iv_2(4)>
2745 : iv_2 = modify (iv_1)
2746 :
2747 : <bb 4>
2748 : if (test (iv_2))
2749 : goto <bb 3>
2750 : else
2751 : goto <bb 5>
2752 :
2753 : The second form can be generated by copying the loop header out of the loop.
2754 :
2755 : In the first case, the number of latch executions will be equal to the
2756 : number of induction variable modifications required before the test fails.
2757 :
2758 : In the second case (modify_before_test), if we assume that the number of
2759 : modifications required before the test fails is nonzero, then the number of
2760 : latch executions will be one less than this number.
2761 :
2762 : If we recognise the pattern, then we update niter accordingly, and return
2763 : true. */
2764 :
2765 : static bool
2766 3898607 : number_of_iterations_bitcount (loop_p loop, const_edge exit,
2767 : enum tree_code code,
2768 : class tree_niter_desc *niter)
2769 : {
2770 3898607 : return (number_of_iterations_popcount (loop, exit, code, niter)
2771 3895020 : || number_of_iterations_cltz (loop, exit, code, niter)
2772 7793548 : || number_of_iterations_cltz_complement (loop, exit, code, niter));
2773 : }
2774 :
2775 : /* Substitute NEW_TREE for OLD in EXPR and fold the result.
2776 : If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
2777 : all SSA names are replaced with the result of calling the VALUEIZE
2778 : function with the SSA name as argument. */
2779 :
2780 : tree
2781 159842529 : simplify_replace_tree (tree expr, tree old, tree new_tree,
2782 : tree (*valueize) (tree, void*), void *context,
2783 : bool do_fold)
2784 : {
2785 159842529 : unsigned i, n;
2786 159842529 : tree ret = NULL_TREE, e, se;
2787 :
2788 159842529 : if (!expr)
2789 : return NULL_TREE;
2790 :
2791 : /* Do not bother to replace constants. */
2792 32024336 : if (CONSTANT_CLASS_P (expr))
2793 : return expr;
2794 :
2795 24216670 : if (valueize)
2796 : {
2797 265752 : if (TREE_CODE (expr) == SSA_NAME)
2798 : {
2799 81527 : new_tree = valueize (expr, context);
2800 81527 : if (new_tree != expr)
2801 : return new_tree;
2802 : }
2803 : }
2804 23950918 : else if (expr == old
2805 23950918 : || operand_equal_p (expr, old, 0))
2806 213175 : return unshare_expr (new_tree);
2807 :
2808 24002872 : if (!EXPR_P (expr))
2809 : return expr;
2810 :
2811 12861676 : n = TREE_OPERAND_LENGTH (expr);
2812 36045038 : for (i = 0; i < n; i++)
2813 : {
2814 23183362 : e = TREE_OPERAND (expr, i);
2815 23183362 : se = simplify_replace_tree (e, old, new_tree, valueize, context, do_fold);
2816 23183362 : if (e == se)
2817 22909177 : continue;
2818 :
2819 274185 : if (!ret)
2820 273763 : ret = copy_node (expr);
2821 :
2822 274185 : TREE_OPERAND (ret, i) = se;
2823 : }
2824 :
2825 12861676 : return (ret ? (do_fold ? fold (ret) : ret) : expr);
2826 : }
2827 :
2828 : /* Expand definitions of ssa names in EXPR as long as they are simple
2829 : enough, and return the new expression. If STOP is specified, stop
2830 : expanding if EXPR equals to it. */
2831 :
2832 : static tree
2833 125270402 : expand_simple_operations (tree expr, tree stop, hash_map<tree, tree> &cache)
2834 : {
2835 125582715 : unsigned i, n;
2836 125582715 : tree ret = NULL_TREE, e, ee, e1;
2837 125582715 : enum tree_code code;
2838 125582715 : gimple *stmt;
2839 :
2840 125582715 : if (expr == NULL_TREE)
2841 : return expr;
2842 :
2843 125582715 : if (is_gimple_min_invariant (expr))
2844 : return expr;
2845 :
2846 85844942 : code = TREE_CODE (expr);
2847 85844942 : if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2848 : {
2849 20704119 : n = TREE_OPERAND_LENGTH (expr);
2850 57221995 : for (i = 0; i < n; i++)
2851 : {
2852 36517876 : e = TREE_OPERAND (expr, i);
2853 36517876 : if (!e)
2854 33099130 : continue;
2855 : /* SCEV analysis feeds us with a proper expression
2856 : graph matching the SSA graph. Avoid turning it
2857 : into a tree here, thus handle tree sharing
2858 : properly.
2859 : ??? The SSA walk below still turns the SSA graph
2860 : into a tree but until we find a testcase do not
2861 : introduce additional tree sharing here. */
2862 36497405 : bool existed_p;
2863 36497405 : tree &cee = cache.get_or_insert (e, &existed_p);
2864 36497405 : if (existed_p)
2865 146677 : ee = cee;
2866 : else
2867 : {
2868 36350728 : cee = e;
2869 36350728 : ee = expand_simple_operations (e, stop, cache);
2870 36350728 : if (ee != e)
2871 3417190 : *cache.get (e) = ee;
2872 : }
2873 36497405 : if (e == ee)
2874 33078659 : continue;
2875 :
2876 3418746 : if (!ret)
2877 3245013 : ret = copy_node (expr);
2878 :
2879 3418746 : TREE_OPERAND (ret, i) = ee;
2880 : }
2881 :
2882 20704119 : if (!ret)
2883 : return expr;
2884 :
2885 3245013 : ret = fold (ret);
2886 3245013 : return ret;
2887 : }
2888 :
2889 : /* Stop if it's not ssa name or the one we don't want to expand. */
2890 65140823 : if (TREE_CODE (expr) != SSA_NAME || expr == stop)
2891 : return expr;
2892 :
2893 64942598 : stmt = SSA_NAME_DEF_STMT (expr);
2894 64942598 : if (gimple_code (stmt) == GIMPLE_PHI)
2895 : {
2896 17316277 : basic_block src, dest;
2897 :
2898 17316277 : if (gimple_phi_num_args (stmt) != 1)
2899 : return expr;
2900 439880 : e = PHI_ARG_DEF (stmt, 0);
2901 :
2902 : /* Avoid propagating through loop exit phi nodes, which
2903 : could break loop-closed SSA form restrictions. */
2904 439880 : dest = gimple_bb (stmt);
2905 439880 : src = single_pred (dest);
2906 439880 : if (TREE_CODE (e) == SSA_NAME
2907 436450 : && src->loop_father != dest->loop_father)
2908 : return expr;
2909 :
2910 : return expand_simple_operations (e, stop, cache);
2911 : }
2912 47626321 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
2913 : return expr;
2914 :
2915 : /* Avoid expanding to expressions that contain SSA names that need
2916 : to take part in abnormal coalescing. */
2917 42037625 : ssa_op_iter iter;
2918 87544814 : FOR_EACH_SSA_TREE_OPERAND (e, stmt, iter, SSA_OP_USE)
2919 45507783 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e))
2920 : return expr;
2921 :
2922 42037031 : e = gimple_assign_rhs1 (stmt);
2923 42037031 : code = gimple_assign_rhs_code (stmt);
2924 42037031 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2925 : {
2926 16507033 : if (is_gimple_min_invariant (e))
2927 : return e;
2928 :
2929 16502309 : if (code == SSA_NAME)
2930 : return expand_simple_operations (e, stop, cache);
2931 16280572 : else if (code == ADDR_EXPR)
2932 : {
2933 17499 : poly_int64 offset;
2934 17499 : tree base = get_addr_base_and_unit_offset (TREE_OPERAND (e, 0),
2935 : &offset);
2936 17499 : if (base
2937 17031 : && TREE_CODE (base) == MEM_REF)
2938 : {
2939 17031 : ee = expand_simple_operations (TREE_OPERAND (base, 0), stop,
2940 : cache);
2941 17031 : return fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (expr), ee,
2942 : wide_int_to_tree (sizetype,
2943 : mem_ref_offset (base)
2944 : + offset));
2945 : }
2946 : }
2947 :
2948 : return expr;
2949 : }
2950 :
2951 25529998 : switch (code)
2952 : {
2953 6431123 : CASE_CONVERT:
2954 : /* Casts are simple. */
2955 6431123 : ee = expand_simple_operations (e, stop, cache);
2956 6431123 : return fold_build1 (code, TREE_TYPE (expr), ee);
2957 :
2958 13914358 : case PLUS_EXPR:
2959 13914358 : case MINUS_EXPR:
2960 13914358 : case MULT_EXPR:
2961 27828716 : if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr))
2962 27826004 : && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr)))
2963 : return expr;
2964 : /* Fallthru. */
2965 14619949 : case POINTER_PLUS_EXPR:
2966 : /* And increments and decrements by a constant are simple. */
2967 14619949 : e1 = gimple_assign_rhs2 (stmt);
2968 14619949 : if (!is_gimple_min_invariant (e1))
2969 : return expr;
2970 :
2971 7508157 : ee = expand_simple_operations (e, stop, cache);
2972 7508157 : return fold_build2 (code, TREE_TYPE (expr), ee, e1);
2973 :
2974 : default:
2975 : return expr;
2976 : }
2977 : }
2978 :
2979 : tree
2980 74963363 : expand_simple_operations (tree expr, tree stop)
2981 : {
2982 74963363 : hash_map<tree, tree> cache;
2983 74963363 : return expand_simple_operations (expr, stop, cache);
2984 74963363 : }
2985 :
2986 : /* Tries to simplify EXPR using the condition COND. Returns the simplified
2987 : expression (or EXPR unchanged, if no simplification was possible). */
2988 :
2989 : static tree
2990 9107104 : tree_simplify_using_condition_1 (tree cond, tree expr)
2991 : {
2992 9107104 : bool changed;
2993 9107104 : tree e, e0, e1, e2, notcond;
2994 9107104 : enum tree_code code = TREE_CODE (expr);
2995 :
2996 9107104 : if (code == INTEGER_CST)
2997 : return expr;
2998 :
2999 9104939 : if (code == TRUTH_OR_EXPR
3000 9104939 : || code == TRUTH_AND_EXPR
3001 9104939 : || code == COND_EXPR)
3002 : {
3003 105518 : changed = false;
3004 :
3005 105518 : e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
3006 105518 : if (TREE_OPERAND (expr, 0) != e0)
3007 137 : changed = true;
3008 :
3009 105518 : e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
3010 105518 : if (TREE_OPERAND (expr, 1) != e1)
3011 4 : changed = true;
3012 :
3013 105518 : if (code == COND_EXPR)
3014 : {
3015 4152 : e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
3016 4152 : if (TREE_OPERAND (expr, 2) != e2)
3017 : changed = true;
3018 : }
3019 : else
3020 : e2 = NULL_TREE;
3021 :
3022 105518 : if (changed)
3023 : {
3024 141 : if (code == COND_EXPR)
3025 0 : expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
3026 : else
3027 141 : expr = fold_build2 (code, boolean_type_node, e0, e1);
3028 : }
3029 :
3030 : return expr;
3031 : }
3032 :
3033 : /* In case COND is equality, we may be able to simplify EXPR by copy/constant
3034 : propagation, and vice versa. Fold does not handle this, since it is
3035 : considered too expensive. */
3036 8999421 : if (TREE_CODE (cond) == EQ_EXPR)
3037 : {
3038 2151712 : e0 = TREE_OPERAND (cond, 0);
3039 2151712 : e1 = TREE_OPERAND (cond, 1);
3040 :
3041 : /* We know that e0 == e1. Check whether we cannot simplify expr
3042 : using this fact. */
3043 2151712 : e = simplify_replace_tree (expr, e0, e1);
3044 2151712 : if (integer_zerop (e) || integer_nonzerop (e))
3045 : return e;
3046 :
3047 2150102 : e = simplify_replace_tree (expr, e1, e0);
3048 2150102 : if (integer_zerop (e) || integer_nonzerop (e))
3049 : return e;
3050 : }
3051 8997479 : if (TREE_CODE (expr) == EQ_EXPR)
3052 : {
3053 1076205 : e0 = TREE_OPERAND (expr, 0);
3054 1076205 : e1 = TREE_OPERAND (expr, 1);
3055 :
3056 : /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
3057 1076205 : e = simplify_replace_tree (cond, e0, e1);
3058 1076205 : if (integer_zerop (e))
3059 : return e;
3060 1063611 : e = simplify_replace_tree (cond, e1, e0);
3061 1063611 : if (integer_zerop (e))
3062 : return e;
3063 : }
3064 8984885 : if (TREE_CODE (expr) == NE_EXPR)
3065 : {
3066 1075818 : e0 = TREE_OPERAND (expr, 0);
3067 1075818 : e1 = TREE_OPERAND (expr, 1);
3068 :
3069 : /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
3070 1075818 : e = simplify_replace_tree (cond, e0, e1);
3071 1075818 : if (integer_zerop (e))
3072 11271 : return boolean_true_node;
3073 1064547 : e = simplify_replace_tree (cond, e1, e0);
3074 1064547 : if (integer_zerop (e))
3075 0 : return boolean_true_node;
3076 : }
3077 :
3078 : /* Check whether COND ==> EXPR. */
3079 8973614 : notcond = invert_truthvalue (cond);
3080 8973614 : e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, expr);
3081 8973614 : if (e && integer_nonzerop (e))
3082 : return e;
3083 :
3084 : /* Check whether COND ==> not EXPR. */
3085 8971244 : e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, expr);
3086 8971244 : if (e && integer_zerop (e))
3087 39050 : return e;
3088 :
3089 : return expr;
3090 : }
3091 :
3092 : /* Tries to simplify EXPR using the condition COND. Returns the simplified
3093 : expression (or EXPR unchanged, if no simplification was possible).
3094 : Wrapper around tree_simplify_using_condition_1 that ensures that chains
3095 : of simple operations in definitions of ssa names in COND are expanded,
3096 : so that things like casts or incrementing the value of the bound before
3097 : the loop do not cause us to fail. */
3098 :
3099 : static tree
3100 8891916 : tree_simplify_using_condition (tree cond, tree expr)
3101 : {
3102 8891916 : cond = expand_simple_operations (cond);
3103 :
3104 8891916 : return tree_simplify_using_condition_1 (cond, expr);
3105 : }
3106 :
3107 : /* Tries to simplify EXPR using the conditions on entry to LOOP.
3108 : Returns the simplified expression (or EXPR unchanged, if no
3109 : simplification was possible). */
3110 :
3111 : tree
3112 28897540 : simplify_using_initial_conditions (class loop *loop, tree expr)
3113 : {
3114 28897540 : edge e;
3115 28897540 : basic_block bb;
3116 28897540 : tree cond, expanded, backup;
3117 28897540 : int cnt = 0;
3118 :
3119 28897540 : if (TREE_CODE (expr) == INTEGER_CST)
3120 : return expr;
3121 :
3122 2964347 : value_range expr_range (TREE_TYPE (expr));
3123 2964347 : tree val;
3124 2964347 : if (TREE_TYPE (expr) == boolean_type_node
3125 5902606 : && get_range_query (cfun)->range_on_edge (expr_range,
3126 : loop_preheader_edge (loop),
3127 : expr)
3128 5915650 : && expr_range.singleton_p (&val))
3129 92763 : return val;
3130 :
3131 2871584 : backup = expanded = expand_simple_operations (expr);
3132 :
3133 : /* Limit walking the dominators to avoid quadraticness in
3134 : the number of BBs times the number of loops in degenerate
3135 : cases. */
3136 2871584 : for (bb = loop->header;
3137 27883030 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
3138 27883030 : && cnt < param_max_niter_dominators_walk;
3139 25011446 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
3140 : {
3141 25078561 : if (!single_pred_p (bb))
3142 12617281 : continue;
3143 12461280 : e = single_pred_edge (bb);
3144 :
3145 12461280 : if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3146 3569364 : continue;
3147 :
3148 17783832 : gcond *stmt = as_a <gcond *> (*gsi_last_bb (e->src));
3149 8891916 : cond = fold_build2 (gimple_cond_code (stmt),
3150 : boolean_type_node,
3151 : gimple_cond_lhs (stmt),
3152 : gimple_cond_rhs (stmt));
3153 8891916 : if (e->flags & EDGE_FALSE_VALUE)
3154 4991372 : cond = invert_truthvalue (cond);
3155 8891916 : expanded = tree_simplify_using_condition (cond, expanded);
3156 : /* Break if EXPR is simplified to const values. */
3157 8891916 : if (expanded
3158 8891916 : && (integer_zerop (expanded) || integer_nonzerop (expanded)))
3159 : return expanded;
3160 :
3161 8824801 : ++cnt;
3162 : }
3163 :
3164 : /* Return the original expression if no simplification is done. */
3165 2804469 : return operand_equal_p (backup, expanded, 0) ? expr : expanded;
3166 2964347 : }
3167 :
3168 : /* Tries to simplify EXPR using the evolutions of the loop invariants
3169 : in the superloops of LOOP. Returns the simplified expression
3170 : (or EXPR unchanged, if no simplification was possible). */
3171 :
3172 : static tree
3173 6796516 : simplify_using_outer_evolutions (class loop *loop, tree expr)
3174 : {
3175 6796516 : enum tree_code code = TREE_CODE (expr);
3176 6796516 : bool changed;
3177 6796516 : tree e, e0, e1, e2;
3178 :
3179 6796516 : if (is_gimple_min_invariant (expr))
3180 : return expr;
3181 :
3182 1552414 : if (code == TRUTH_OR_EXPR
3183 1552414 : || code == TRUTH_AND_EXPR
3184 1552414 : || code == COND_EXPR)
3185 : {
3186 9146 : changed = false;
3187 :
3188 9146 : e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
3189 9146 : if (TREE_OPERAND (expr, 0) != e0)
3190 0 : changed = true;
3191 :
3192 9146 : e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
3193 9146 : if (TREE_OPERAND (expr, 1) != e1)
3194 0 : changed = true;
3195 :
3196 9146 : if (code == COND_EXPR)
3197 : {
3198 0 : e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
3199 0 : if (TREE_OPERAND (expr, 2) != e2)
3200 : changed = true;
3201 : }
3202 : else
3203 : e2 = NULL_TREE;
3204 :
3205 9146 : if (changed)
3206 : {
3207 0 : if (code == COND_EXPR)
3208 0 : expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
3209 : else
3210 0 : expr = fold_build2 (code, boolean_type_node, e0, e1);
3211 : }
3212 :
3213 : return expr;
3214 : }
3215 :
3216 1543268 : e = instantiate_parameters (loop, expr);
3217 1543268 : if (is_gimple_min_invariant (e))
3218 0 : return e;
3219 :
3220 : return expr;
3221 : }
3222 :
3223 : /* Returns true if EXIT is the only possible exit from LOOP. */
3224 :
3225 : bool
3226 13708966 : loop_only_exit_p (const class loop *loop, basic_block *body, const_edge exit)
3227 : {
3228 13708966 : gimple_stmt_iterator bsi;
3229 13708966 : unsigned i;
3230 :
3231 13708966 : if (exit != single_exit (loop))
3232 : return false;
3233 :
3234 45517032 : for (i = 0; i < loop->num_nodes; i++)
3235 306324041 : for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
3236 234747148 : if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
3237 : return false;
3238 :
3239 : return true;
3240 : }
3241 :
3242 : /* Stores description of number of iterations of LOOP derived from
3243 : EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
3244 : information could be derived (and fields of NITER have meaning described
3245 : in comments at class tree_niter_desc declaration), false otherwise.
3246 : When EVERY_ITERATION is true, only tests that are known to be executed
3247 : every iteration are considered (i.e. only test that alone bounds the loop).
3248 : If AT_STMT is not NULL, this function stores LOOP's condition statement in
3249 : it when returning true. */
3250 :
3251 : bool
3252 25088857 : number_of_iterations_exit_assumptions (class loop *loop, const_edge exit,
3253 : class tree_niter_desc *niter,
3254 : gcond **at_stmt, bool every_iteration,
3255 : basic_block *body)
3256 : {
3257 25088857 : tree type;
3258 25088857 : tree op0, op1;
3259 25088857 : enum tree_code code;
3260 25088857 : affine_iv iv0, iv1;
3261 25088857 : bool safe;
3262 :
3263 : /* The condition at a fake exit (if it exists) does not control its
3264 : execution. */
3265 25088857 : if (exit->flags & EDGE_FAKE)
3266 : return false;
3267 :
3268 : /* Nothing to analyze if the loop is known to be infinite. */
3269 25088411 : if (loop_constraint_set_p (loop, LOOP_C_INFINITE))
3270 : return false;
3271 :
3272 25088411 : safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
3273 :
3274 25088411 : if (every_iteration && !safe)
3275 : return false;
3276 :
3277 23953743 : niter->assumptions = boolean_false_node;
3278 23953743 : niter->control.base = NULL_TREE;
3279 23953743 : niter->control.step = NULL_TREE;
3280 23953743 : niter->control.no_overflow = false;
3281 47907486 : gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
3282 21932319 : if (!stmt)
3283 : return false;
3284 :
3285 21932319 : if (at_stmt)
3286 21273292 : *at_stmt = stmt;
3287 :
3288 : /* We want the condition for staying inside loop. */
3289 21932319 : code = gimple_cond_code (stmt);
3290 21932319 : if (exit->flags & EDGE_TRUE_VALUE)
3291 8228433 : code = invert_tree_comparison (code, false);
3292 :
3293 21932319 : switch (code)
3294 : {
3295 18652565 : case GT_EXPR:
3296 18652565 : case GE_EXPR:
3297 18652565 : case LT_EXPR:
3298 18652565 : case LE_EXPR:
3299 18652565 : case NE_EXPR:
3300 18652565 : break;
3301 :
3302 3279397 : case EQ_EXPR:
3303 3279397 : return number_of_iterations_cltz (loop, exit, code, niter);
3304 :
3305 : default:
3306 : return false;
3307 : }
3308 :
3309 18652565 : op0 = gimple_cond_lhs (stmt);
3310 18652565 : op1 = gimple_cond_rhs (stmt);
3311 18652565 : type = TREE_TYPE (op0);
3312 :
3313 18652565 : if (!INTEGRAL_NB_TYPE_P (type)
3314 : && !POINTER_TYPE_P (type))
3315 : return false;
3316 :
3317 17885191 : tree iv0_niters = NULL_TREE;
3318 35770382 : if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
3319 : op0, &iv0, safe ? &iv0_niters : NULL, false))
3320 3898607 : return number_of_iterations_bitcount (loop, exit, code, niter);
3321 13986584 : tree iv1_niters = NULL_TREE;
3322 27973168 : if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
3323 : op1, &iv1, safe ? &iv1_niters : NULL, false))
3324 : return false;
3325 : /* Give up on complicated case. */
3326 13292124 : if (iv0_niters && iv1_niters)
3327 : return false;
3328 :
3329 13292124 : iv0.base = expand_simple_operations (iv0.base);
3330 13292124 : iv1.base = expand_simple_operations (iv1.base);
3331 13292124 : bool body_from_caller = true;
3332 13292124 : if (!body)
3333 : {
3334 7993189 : body = get_loop_body (loop);
3335 7993189 : body_from_caller = false;
3336 : }
3337 13292124 : bool only_exit_p = loop_only_exit_p (loop, body, exit);
3338 13292124 : if (!body_from_caller)
3339 7993189 : free (body);
3340 13292124 : if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
3341 : only_exit_p, safe))
3342 : {
3343 : return false;
3344 : }
3345 :
3346 : /* Incorporate additional assumption implied by control iv. */
3347 13145304 : tree iv_niters = iv0_niters ? iv0_niters : iv1_niters;
3348 13145304 : if (iv_niters)
3349 : {
3350 25845 : tree assumption = fold_build2 (LE_EXPR, boolean_type_node, niter->niter,
3351 : fold_convert (TREE_TYPE (niter->niter),
3352 : iv_niters));
3353 :
3354 25845 : if (!integer_nonzerop (assumption))
3355 25634 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
3356 : niter->assumptions, assumption);
3357 :
3358 : /* Refine upper bound if possible. */
3359 25845 : if (TREE_CODE (iv_niters) == INTEGER_CST
3360 51690 : && niter->max > wi::to_widest (iv_niters))
3361 22595 : niter->max = wi::to_widest (iv_niters);
3362 : }
3363 :
3364 : /* There is no assumptions if the loop is known to be finite. */
3365 13145304 : if (!integer_zerop (niter->assumptions)
3366 13145304 : && loop_constraint_set_p (loop, LOOP_C_FINITE))
3367 12454 : niter->assumptions = boolean_true_node;
3368 :
3369 13145304 : if (optimize >= 3)
3370 : {
3371 2259408 : niter->assumptions = simplify_using_outer_evolutions (loop,
3372 : niter->assumptions);
3373 2259408 : niter->may_be_zero = simplify_using_outer_evolutions (loop,
3374 : niter->may_be_zero);
3375 2259408 : niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
3376 : }
3377 :
3378 13145304 : niter->assumptions
3379 13145304 : = simplify_using_initial_conditions (loop,
3380 : niter->assumptions);
3381 13145304 : niter->may_be_zero
3382 13145304 : = simplify_using_initial_conditions (loop,
3383 : niter->may_be_zero);
3384 :
3385 : /* If NITER has simplified into a constant, update MAX. */
3386 13145304 : if (TREE_CODE (niter->niter) == INTEGER_CST)
3387 7534552 : niter->max = wi::to_widest (niter->niter);
3388 :
3389 13145304 : return (!integer_zerop (niter->assumptions));
3390 : }
3391 :
3392 : /* Like number_of_iterations_exit_assumptions, but return TRUE only if
3393 : the niter information holds unconditionally. */
3394 :
3395 : bool
3396 24332897 : number_of_iterations_exit (class loop *loop, const_edge exit,
3397 : class tree_niter_desc *niter,
3398 : bool warn, bool every_iteration,
3399 : basic_block *body)
3400 : {
3401 24332897 : gcond *stmt;
3402 24332897 : if (!number_of_iterations_exit_assumptions (loop, exit, niter,
3403 : &stmt, every_iteration, body))
3404 : return false;
3405 :
3406 12784057 : if (integer_nonzerop (niter->assumptions))
3407 : return true;
3408 :
3409 588949 : if (warn && dump_enabled_p ())
3410 4 : dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
3411 : "missed loop optimization: niters analysis ends up "
3412 : "with assumptions.\n");
3413 :
3414 : return false;
3415 : }
3416 :
3417 : /* Try to determine the number of iterations of LOOP. If we succeed,
3418 : expression giving number of iterations is returned and *EXIT is
3419 : set to the edge from that the information is obtained. Otherwise
3420 : chrec_dont_know is returned. */
3421 :
3422 : tree
3423 789148 : find_loop_niter (class loop *loop, edge *exit)
3424 : {
3425 789148 : unsigned i;
3426 789148 : auto_vec<edge> exits = get_loop_exit_edges (loop);
3427 789148 : edge ex;
3428 789148 : tree niter = NULL_TREE, aniter;
3429 789148 : class tree_niter_desc desc;
3430 :
3431 789148 : *exit = NULL;
3432 3431951 : FOR_EACH_VEC_ELT (exits, i, ex)
3433 : {
3434 2642803 : if (!number_of_iterations_exit (loop, ex, &desc, false))
3435 2111814 : continue;
3436 :
3437 530989 : if (integer_nonzerop (desc.may_be_zero))
3438 : {
3439 : /* We exit in the first iteration through this exit.
3440 : We won't find anything better. */
3441 0 : niter = build_int_cst (unsigned_type_node, 0);
3442 0 : *exit = ex;
3443 0 : break;
3444 : }
3445 :
3446 530989 : if (!integer_zerop (desc.may_be_zero))
3447 57416 : continue;
3448 :
3449 473573 : aniter = desc.niter;
3450 :
3451 473573 : if (!niter)
3452 : {
3453 : /* Nothing recorded yet. */
3454 463985 : niter = aniter;
3455 463985 : *exit = ex;
3456 463985 : continue;
3457 : }
3458 :
3459 : /* Prefer constants, the lower the better. */
3460 9588 : if (TREE_CODE (aniter) != INTEGER_CST)
3461 5425 : continue;
3462 :
3463 4163 : if (TREE_CODE (niter) != INTEGER_CST)
3464 : {
3465 1022 : niter = aniter;
3466 1022 : *exit = ex;
3467 1022 : continue;
3468 : }
3469 :
3470 3141 : if (tree_int_cst_lt (aniter, niter))
3471 : {
3472 256 : niter = aniter;
3473 256 : *exit = ex;
3474 256 : continue;
3475 : }
3476 : }
3477 :
3478 789148 : return niter ? niter : chrec_dont_know;
3479 789148 : }
3480 :
3481 : /* Return true if loop is known to have bounded number of iterations. */
3482 :
3483 : bool
3484 3053237 : finite_loop_p (class loop *loop)
3485 : {
3486 3053237 : widest_int nit;
3487 3053237 : int flags;
3488 :
3489 3053237 : if (loop->finite_p)
3490 : {
3491 2265449 : unsigned i;
3492 2265449 : auto_vec<edge> exits = get_loop_exit_edges (loop);
3493 2265449 : edge ex;
3494 :
3495 : /* If the loop has a normal exit, we can assume it will terminate. */
3496 4544185 : FOR_EACH_VEC_ELT (exits, i, ex)
3497 2273926 : if (!(ex->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_FAKE)))
3498 : {
3499 2260976 : if (dump_file)
3500 180 : fprintf (dump_file, "Assume loop %i to be finite: it has an exit "
3501 : "and -ffinite-loops is on or loop was "
3502 : "previously finite.\n",
3503 : loop->num);
3504 2260976 : return true;
3505 : }
3506 2265449 : }
3507 :
3508 792261 : flags = flags_from_decl_or_type (current_function_decl);
3509 792261 : if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
3510 : {
3511 2743 : if (dump_file && (dump_flags & TDF_DETAILS))
3512 0 : fprintf (dump_file,
3513 : "Found loop %i to be finite: it is within "
3514 : "pure or const function.\n",
3515 : loop->num);
3516 2743 : loop->finite_p = true;
3517 2743 : return true;
3518 : }
3519 :
3520 789518 : if (loop->any_upper_bound
3521 : /* Loop with no normal exit will not pass max_loop_iterations. */
3522 789518 : || (!loop->finite_p && max_loop_iterations (loop, &nit)))
3523 : {
3524 419230 : if (dump_file && (dump_flags & TDF_DETAILS))
3525 31 : fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n",
3526 : loop->num);
3527 419230 : loop->finite_p = true;
3528 419230 : return true;
3529 : }
3530 :
3531 : return false;
3532 3053237 : }
3533 :
3534 : /*
3535 :
3536 : Analysis of a number of iterations of a loop by a brute-force evaluation.
3537 :
3538 : */
3539 :
3540 : /* Bound on the number of iterations we try to evaluate. */
3541 :
3542 : #define MAX_ITERATIONS_TO_TRACK \
3543 : ((unsigned) param_max_iterations_to_track)
3544 :
3545 : /* Returns the loop phi node of LOOP such that ssa name X is derived from its
3546 : result by a chain of operations such that all but exactly one of their
3547 : operands are constants. */
3548 :
3549 : static gphi *
3550 1996569 : chain_of_csts_start (class loop *loop, tree x)
3551 : {
3552 2391111 : gimple *stmt = SSA_NAME_DEF_STMT (x);
3553 2391111 : tree use;
3554 2391111 : basic_block bb = gimple_bb (stmt);
3555 2391111 : enum tree_code code;
3556 :
3557 2391111 : if (!bb
3558 2391111 : || !flow_bb_inside_loop_p (loop, bb))
3559 : return NULL;
3560 :
3561 1841579 : if (gimple_code (stmt) == GIMPLE_PHI)
3562 : {
3563 727777 : if (bb == loop->header)
3564 666720 : return as_a <gphi *> (stmt);
3565 :
3566 : return NULL;
3567 : }
3568 :
3569 1113802 : if (gimple_code (stmt) != GIMPLE_ASSIGN
3570 2105703 : || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS)
3571 : return NULL;
3572 :
3573 991629 : code = gimple_assign_rhs_code (stmt);
3574 991629 : if (gimple_references_memory_p (stmt)
3575 534273 : || TREE_CODE_CLASS (code) == tcc_reference
3576 508585 : || (code == ADDR_EXPR
3577 547 : && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
3578 : return NULL;
3579 :
3580 508038 : use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
3581 508038 : if (use == NULL_TREE)
3582 : return NULL;
3583 :
3584 : return chain_of_csts_start (loop, use);
3585 : }
3586 :
3587 : /* Determines whether the expression X is derived from a result of a phi node
3588 : in header of LOOP such that
3589 :
3590 : * the derivation of X consists only from operations with constants
3591 : * the initial value of the phi node is constant
3592 : * the value of the phi node in the next iteration can be derived from the
3593 : value in the current iteration by a chain of operations with constants,
3594 : or is also a constant
3595 :
3596 : If such phi node exists, it is returned, otherwise NULL is returned. */
3597 :
3598 : static gphi *
3599 1806192 : get_base_for (class loop *loop, tree x)
3600 : {
3601 1806192 : gphi *phi;
3602 1806192 : tree init, next;
3603 :
3604 1806192 : if (is_gimple_min_invariant (x))
3605 : return NULL;
3606 :
3607 1806192 : phi = chain_of_csts_start (loop, x);
3608 1806192 : if (!phi)
3609 : return NULL;
3610 :
3611 492886 : init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
3612 492886 : next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3613 :
3614 492886 : if (!is_gimple_min_invariant (init))
3615 : return NULL;
3616 :
3617 216229 : if (TREE_CODE (next) == SSA_NAME
3618 216229 : && chain_of_csts_start (loop, next) != phi)
3619 16579 : return NULL;
3620 :
3621 : return phi;
3622 : }
3623 :
3624 : /* Given an expression X, then
3625 :
3626 : * if X is NULL_TREE, we return the constant BASE.
3627 : * if X is a constant, we return the constant X.
3628 : * otherwise X is a SSA name, whose value in the considered loop is derived
3629 : by a chain of operations with constant from a result of a phi node in
3630 : the header of the loop. Then we return value of X when the value of the
3631 : result of this phi node is given by the constant BASE. */
3632 :
3633 : static tree
3634 7504046 : get_val_for (tree x, tree base)
3635 : {
3636 7511443 : gimple *stmt;
3637 :
3638 7511443 : gcc_checking_assert (is_gimple_min_invariant (base));
3639 :
3640 7511443 : if (!x)
3641 : return base;
3642 5254916 : else if (is_gimple_min_invariant (x))
3643 : return x;
3644 :
3645 5229326 : stmt = SSA_NAME_DEF_STMT (x);
3646 5229326 : if (gimple_code (stmt) == GIMPLE_PHI)
3647 : return base;
3648 :
3649 2778503 : gcc_checking_assert (is_gimple_assign (stmt));
3650 :
3651 : /* STMT must be either an assignment of a single SSA name or an
3652 : expression involving an SSA name and a constant. Try to fold that
3653 : expression using the value for the SSA name. */
3654 2778503 : if (gimple_assign_ssa_name_copy_p (stmt))
3655 7397 : return get_val_for (gimple_assign_rhs1 (stmt), base);
3656 2771106 : else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
3657 2771106 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
3658 286932 : return fold_build1 (gimple_assign_rhs_code (stmt),
3659 : TREE_TYPE (gimple_assign_lhs (stmt)),
3660 : get_val_for (gimple_assign_rhs1 (stmt), base));
3661 2484174 : else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
3662 : {
3663 2484174 : tree rhs1 = gimple_assign_rhs1 (stmt);
3664 2484174 : tree rhs2 = gimple_assign_rhs2 (stmt);
3665 2484174 : if (TREE_CODE (rhs1) == SSA_NAME)
3666 2421564 : rhs1 = get_val_for (rhs1, base);
3667 62610 : else if (TREE_CODE (rhs2) == SSA_NAME)
3668 62610 : rhs2 = get_val_for (rhs2, base);
3669 : else
3670 0 : gcc_unreachable ();
3671 2484174 : return fold_build2 (gimple_assign_rhs_code (stmt),
3672 : TREE_TYPE (gimple_assign_lhs (stmt)), rhs1, rhs2);
3673 : }
3674 : else
3675 0 : gcc_unreachable ();
3676 : }
3677 :
3678 :
3679 : /* Tries to count the number of iterations of LOOP till it exits by EXIT
3680 : by brute force -- i.e. by determining the value of the operands of the
3681 : condition at EXIT in first few iterations of the loop (assuming that
3682 : these values are constant) and determining the first one in that the
3683 : condition is not satisfied. Returns the constant giving the number
3684 : of the iterations of LOOP if successful, chrec_dont_know otherwise. */
3685 :
3686 : tree
3687 1764580 : loop_niter_by_eval (class loop *loop, edge exit)
3688 : {
3689 1764580 : tree acnd;
3690 1764580 : tree op[2], val[2], next[2], aval[2];
3691 1764580 : gphi *phi;
3692 1764580 : unsigned i, j;
3693 1764580 : enum tree_code cmp;
3694 :
3695 3529160 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
3696 1764580 : if (!cond)
3697 128458 : return chrec_dont_know;
3698 :
3699 1636122 : cmp = gimple_cond_code (cond);
3700 1636122 : if (exit->flags & EDGE_TRUE_VALUE)
3701 592286 : cmp = invert_tree_comparison (cmp, false);
3702 :
3703 1636122 : switch (cmp)
3704 : {
3705 1636093 : case EQ_EXPR:
3706 1636093 : case NE_EXPR:
3707 1636093 : case GT_EXPR:
3708 1636093 : case GE_EXPR:
3709 1636093 : case LT_EXPR:
3710 1636093 : case LE_EXPR:
3711 1636093 : op[0] = gimple_cond_lhs (cond);
3712 1636093 : op[1] = gimple_cond_rhs (cond);
3713 1636093 : break;
3714 :
3715 29 : default:
3716 29 : return chrec_dont_know;
3717 : }
3718 :
3719 1865079 : for (j = 0; j < 2; j++)
3720 : {
3721 1835528 : if (is_gimple_min_invariant (op[j]))
3722 : {
3723 29336 : val[j] = op[j];
3724 29336 : next[j] = NULL_TREE;
3725 29336 : op[j] = NULL_TREE;
3726 : }
3727 : else
3728 : {
3729 1806192 : phi = get_base_for (loop, op[j]);
3730 1806192 : if (!phi)
3731 : {
3732 1606542 : gassign *def;
3733 1606542 : if (j == 0
3734 1436658 : && (cmp == NE_EXPR || cmp == EQ_EXPR)
3735 832534 : && TREE_CODE (op[0]) == SSA_NAME
3736 832534 : && TREE_CODE (op[1]) == INTEGER_CST
3737 528626 : && (def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op[0])))
3738 1897172 : && gimple_assign_rhs_code (def) == MEM_REF)
3739 : {
3740 60858 : tree mem = gimple_assign_rhs1 (def);
3741 60858 : affine_iv iv;
3742 60858 : if (TYPE_MODE (TREE_TYPE (mem)) == TYPE_MODE (char_type_node)
3743 : && CHAR_TYPE_SIZE == 8
3744 23512 : && simple_iv (loop, loop,
3745 23512 : TREE_OPERAND (mem, 0), &iv, false)
3746 17120 : && tree_fits_uhwi_p (TREE_OPERAND (mem, 1))
3747 77978 : && tree_fits_uhwi_p (iv.step))
3748 : {
3749 17120 : tree str, off;
3750 : /* iv.base can be &"Foo" but also (char *)&"Foo" + 1. */
3751 17120 : split_constant_offset (iv.base, &str, &off);
3752 17120 : STRIP_NOPS (str);
3753 17120 : if (TREE_CODE (str) == ADDR_EXPR
3754 3256 : && TREE_CODE (TREE_OPERAND (str, 0)) == STRING_CST
3755 18886 : && tree_fits_uhwi_p (off))
3756 : {
3757 1766 : str = TREE_OPERAND (str, 0);
3758 1766 : unsigned i = 0;
3759 1766 : uint8_t op1 = TREE_INT_CST_LOW (op[1]);
3760 1766 : for (unsigned HOST_WIDE_INT idx
3761 1766 : = (tree_to_uhwi (TREE_OPERAND (mem, 1))
3762 1766 : + tree_to_uhwi (off));
3763 26076 : idx < (unsigned)TREE_STRING_LENGTH (str)
3764 13038 : && i < MAX_ITERATIONS_TO_TRACK;
3765 11272 : idx += tree_to_uhwi (iv.step), ++i)
3766 : {
3767 12212 : uint8_t c = TREE_STRING_POINTER (str)[idx];
3768 12212 : if ((cmp == NE_EXPR && op1 == c)
3769 11306 : || (cmp == EQ_EXPR && op1 != c))
3770 940 : return build_int_cst (unsigned_type_node, i);
3771 : }
3772 : }
3773 : }
3774 : }
3775 1605602 : return chrec_dont_know;
3776 : }
3777 199650 : val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
3778 199650 : next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3779 : }
3780 : }
3781 :
3782 1198280 : for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
3783 : {
3784 3592092 : for (j = 0; j < 2; j++)
3785 2394728 : aval[j] = get_val_for (op[j], val[j]);
3786 :
3787 1197364 : acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
3788 1197364 : if (acnd && integer_zerop (acnd))
3789 : {
3790 27906 : if (dump_file && (dump_flags & TDF_DETAILS))
3791 3 : fprintf (dump_file,
3792 : "Proved that loop %d iterates %d times using brute force.\n",
3793 : loop->num, i);
3794 27906 : return build_int_cst (unsigned_type_node, i);
3795 : }
3796 :
3797 3506966 : for (j = 0; j < 2; j++)
3798 : {
3799 2338212 : aval[j] = val[j];
3800 2338212 : val[j] = get_val_for (next[j], val[j]);
3801 2338212 : if (!is_gimple_min_invariant (val[j]))
3802 704 : return chrec_dont_know;
3803 : }
3804 :
3805 : /* If the next iteration would use the same base values
3806 : as the current one, there is no point looping further,
3807 : all following iterations will be the same as this one. */
3808 1168754 : if (val[0] == aval[0] && val[1] == aval[1])
3809 : break;
3810 : }
3811 :
3812 941 : return chrec_dont_know;
3813 : }
3814 :
3815 : /* Finds the exit of the LOOP by that the loop exits after a constant
3816 : number of iterations and stores the exit edge to *EXIT. The constant
3817 : giving the number of iterations of LOOP is returned. The number of
3818 : iterations is determined using loop_niter_by_eval (i.e. by brute force
3819 : evaluation). If we are unable to find the exit for that loop_niter_by_eval
3820 : determines the number of iterations, chrec_dont_know is returned. */
3821 :
3822 : tree
3823 810329 : find_loop_niter_by_eval (class loop *loop, edge *exit)
3824 : {
3825 810329 : unsigned i;
3826 810329 : auto_vec<edge> exits = get_loop_exit_edges (loop);
3827 810329 : edge ex;
3828 810329 : tree niter = NULL_TREE, aniter;
3829 :
3830 810329 : *exit = NULL;
3831 :
3832 : /* Loops with multiple exits are expensive to handle and less important. */
3833 810329 : if (!flag_expensive_optimizations
3834 831303 : && exits.length () > 1)
3835 4316 : return chrec_dont_know;
3836 :
3837 2437234 : FOR_EACH_VEC_ELT (exits, i, ex)
3838 : {
3839 1631221 : if (!just_once_each_iteration_p (loop, ex->src))
3840 445337 : continue;
3841 :
3842 1185884 : aniter = loop_niter_by_eval (loop, ex);
3843 1185884 : if (chrec_contains_undetermined (aniter))
3844 1170227 : continue;
3845 :
3846 15706 : if (niter
3847 15657 : && !tree_int_cst_lt (aniter, niter))
3848 49 : continue;
3849 :
3850 15608 : niter = aniter;
3851 15608 : *exit = ex;
3852 : }
3853 :
3854 806013 : return niter ? niter : chrec_dont_know;
3855 810329 : }
3856 :
3857 : /*
3858 :
3859 : Analysis of upper bounds on number of iterations of a loop.
3860 :
3861 : */
3862 :
3863 : static widest_int derive_constant_upper_bound_ops (tree, tree,
3864 : enum tree_code, tree);
3865 :
3866 : /* Returns a constant upper bound on the value of the right-hand side of
3867 : an assignment statement STMT. */
3868 :
3869 : static widest_int
3870 332 : derive_constant_upper_bound_assign (gimple *stmt)
3871 : {
3872 332 : enum tree_code code = gimple_assign_rhs_code (stmt);
3873 332 : tree op0 = gimple_assign_rhs1 (stmt);
3874 332 : tree op1 = gimple_assign_rhs2 (stmt);
3875 :
3876 332 : return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
3877 332 : op0, code, op1);
3878 : }
3879 :
3880 : /* Returns a constant upper bound on the value of expression VAL. VAL
3881 : is considered to be unsigned. If its type is signed, its value must
3882 : be nonnegative. */
3883 :
3884 : static widest_int
3885 11508105 : derive_constant_upper_bound (tree val)
3886 : {
3887 11508105 : enum tree_code code;
3888 11508105 : tree op0, op1, op2;
3889 :
3890 11508105 : extract_ops_from_tree (val, &code, &op0, &op1, &op2);
3891 11508105 : return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
3892 : }
3893 :
3894 : /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3895 : whose type is TYPE. The expression is considered to be unsigned. If
3896 : its type is signed, its value must be nonnegative. */
3897 :
3898 : static widest_int
3899 11508437 : derive_constant_upper_bound_ops (tree type, tree op0,
3900 : enum tree_code code, tree op1)
3901 : {
3902 11508437 : tree subtype, maxt;
3903 11508437 : widest_int bnd, max, cst;
3904 11508437 : gimple *stmt;
3905 :
3906 11508437 : if (INTEGRAL_TYPE_P (type))
3907 11508437 : maxt = TYPE_MAX_VALUE (type);
3908 : else
3909 0 : maxt = upper_bound_in_type (type, type);
3910 :
3911 11508437 : max = wi::to_widest (maxt);
3912 :
3913 11508437 : switch (code)
3914 : {
3915 11442622 : case INTEGER_CST:
3916 11442622 : return wi::to_widest (op0);
3917 :
3918 1017 : CASE_CONVERT:
3919 1017 : subtype = TREE_TYPE (op0);
3920 1017 : if (!TYPE_UNSIGNED (subtype)
3921 : /* If TYPE is also signed, the fact that VAL is nonnegative implies
3922 : that OP0 is nonnegative. */
3923 738 : && TYPE_UNSIGNED (type)
3924 1755 : && !tree_expr_nonnegative_p (op0))
3925 : {
3926 : /* If we cannot prove that the casted expression is nonnegative,
3927 : we cannot establish more useful upper bound than the precision
3928 : of the type gives us. */
3929 650 : return max;
3930 : }
3931 :
3932 : /* We now know that op0 is an nonnegative value. Try deriving an upper
3933 : bound for it. */
3934 367 : bnd = derive_constant_upper_bound (op0);
3935 :
3936 : /* If the bound does not fit in TYPE, max. value of TYPE could be
3937 : attained. */
3938 367 : if (wi::ltu_p (max, bnd))
3939 0 : return max;
3940 :
3941 367 : return bnd;
3942 :
3943 35158 : case PLUS_EXPR:
3944 35158 : case POINTER_PLUS_EXPR:
3945 35158 : case MINUS_EXPR:
3946 35158 : if (TREE_CODE (op1) != INTEGER_CST
3947 35158 : || !tree_expr_nonnegative_p (op0))
3948 34723 : return max;
3949 :
3950 : /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3951 : choose the most logical way how to treat this constant regardless
3952 : of the signedness of the type. */
3953 435 : cst = wi::sext (wi::to_widest (op1), TYPE_PRECISION (type));
3954 435 : if (code != MINUS_EXPR)
3955 435 : cst = -cst;
3956 :
3957 435 : bnd = derive_constant_upper_bound (op0);
3958 :
3959 435 : if (wi::neg_p (cst))
3960 : {
3961 28 : cst = -cst;
3962 : /* Avoid CST == 0x80000... */
3963 28 : if (wi::neg_p (cst))
3964 0 : return max;
3965 :
3966 : /* OP0 + CST. We need to check that
3967 : BND <= MAX (type) - CST. */
3968 :
3969 28 : widest_int mmax = max - cst;
3970 28 : if (wi::leu_p (bnd, mmax))
3971 0 : return max;
3972 :
3973 28 : return bnd + cst;
3974 28 : }
3975 : else
3976 : {
3977 : /* OP0 - CST, where CST >= 0.
3978 :
3979 : If TYPE is signed, we have already verified that OP0 >= 0, and we
3980 : know that the result is nonnegative. This implies that
3981 : VAL <= BND - CST.
3982 :
3983 : If TYPE is unsigned, we must additionally know that OP0 >= CST,
3984 : otherwise the operation underflows.
3985 : */
3986 :
3987 : /* This should only happen if the type is unsigned; however, for
3988 : buggy programs that use overflowing signed arithmetics even with
3989 : -fno-wrapv, this condition may also be true for signed values. */
3990 407 : if (wi::ltu_p (bnd, cst))
3991 0 : return max;
3992 :
3993 407 : if (TYPE_UNSIGNED (type))
3994 : {
3995 402 : tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
3996 : wide_int_to_tree (type, cst));
3997 402 : if (!tem || integer_nonzerop (tem))
3998 50 : return max;
3999 : }
4000 :
4001 357 : bnd -= cst;
4002 : }
4003 :
4004 357 : return bnd;
4005 :
4006 0 : case FLOOR_DIV_EXPR:
4007 0 : case EXACT_DIV_EXPR:
4008 0 : if (TREE_CODE (op1) != INTEGER_CST
4009 0 : || tree_int_cst_sign_bit (op1))
4010 0 : return max;
4011 :
4012 0 : bnd = derive_constant_upper_bound (op0);
4013 0 : return wi::udiv_floor (bnd, wi::to_widest (op1));
4014 :
4015 7 : case BIT_AND_EXPR:
4016 7 : if (TREE_CODE (op1) != INTEGER_CST
4017 7 : || tree_int_cst_sign_bit (op1))
4018 0 : return max;
4019 7 : return wi::to_widest (op1);
4020 :
4021 543 : case SSA_NAME:
4022 543 : stmt = SSA_NAME_DEF_STMT (op0);
4023 543 : if (gimple_code (stmt) != GIMPLE_ASSIGN
4024 543 : || gimple_assign_lhs (stmt) != op0)
4025 211 : return max;
4026 332 : return derive_constant_upper_bound_assign (stmt);
4027 :
4028 29090 : default:
4029 29090 : return max;
4030 : }
4031 11508450 : }
4032 :
4033 : /* Emit a -Waggressive-loop-optimizations warning if needed. */
4034 :
4035 : static void
4036 10559783 : do_warn_aggressive_loop_optimizations (class loop *loop,
4037 : widest_int i_bound, gimple *stmt)
4038 : {
4039 : /* Don't warn if the loop doesn't have known constant bound. */
4040 10559783 : if (!loop->nb_iterations
4041 10559783 : || TREE_CODE (loop->nb_iterations) != INTEGER_CST
4042 4936967 : || !warn_aggressive_loop_optimizations
4043 : /* To avoid warning multiple times for the same loop,
4044 : only start warning when we preserve loops. */
4045 4936799 : || (cfun->curr_properties & PROP_loops) == 0
4046 : /* Only warn once per loop. */
4047 4936799 : || loop->warned_aggressive_loop_optimizations
4048 : /* Only warn if undefined behavior gives us lower estimate than the
4049 : known constant bound. */
4050 10559783 : || wi::cmpu (i_bound, wi::to_widest (loop->nb_iterations)) >= 0
4051 : /* And undefined behavior happens unconditionally. */
4052 10559838 : || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
4053 10559728 : return;
4054 :
4055 55 : edge e = single_exit (loop);
4056 55 : if (e == NULL)
4057 : return;
4058 :
4059 55 : gimple *estmt = last_nondebug_stmt (e->src);
4060 55 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
4061 55 : unsigned len;
4062 55 : if (print_dec_buf_size (i_bound, TYPE_SIGN (TREE_TYPE (loop->nb_iterations)),
4063 : &len))
4064 0 : p = XALLOCAVEC (char, len);
4065 : else
4066 : p = buf;
4067 55 : print_dec (i_bound, p, TYPE_SIGN (TREE_TYPE (loop->nb_iterations)));
4068 55 : auto_diagnostic_group d;
4069 55 : if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
4070 : "iteration %s invokes undefined behavior", p))
4071 9 : inform (gimple_location (estmt), "within this loop");
4072 55 : loop->warned_aggressive_loop_optimizations = true;
4073 55 : }
4074 :
4075 : /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
4076 : is true if the loop is exited immediately after STMT, and this exit
4077 : is taken at last when the STMT is executed BOUND + 1 times.
4078 : REALISTIC is true if BOUND is expected to be close to the real number
4079 : of iterations. UPPER is true if we are sure the loop iterates at most
4080 : BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
4081 :
4082 : static void
4083 16404127 : record_estimate (class loop *loop, tree bound, const widest_int &i_bound,
4084 : gimple *at_stmt, bool is_exit, bool realistic, bool upper)
4085 : {
4086 16404127 : widest_int delta;
4087 :
4088 16404127 : if (dump_file && (dump_flags & TDF_DETAILS))
4089 : {
4090 137599 : fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
4091 76611 : print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
4092 77349 : fprintf (dump_file, " is %sexecuted at most ",
4093 : upper ? "" : "probably ");
4094 76611 : print_generic_expr (dump_file, bound, TDF_SLIM);
4095 76611 : fprintf (dump_file, " (bounded by ");
4096 76611 : print_decu (i_bound, dump_file);
4097 76611 : fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
4098 : }
4099 :
4100 : /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
4101 : real number of iterations. */
4102 16404127 : if (TREE_CODE (bound) != INTEGER_CST)
4103 : realistic = false;
4104 : else
4105 14486528 : gcc_checking_assert (i_bound == wi::to_widest (bound));
4106 :
4107 16404127 : if (wi::min_precision (i_bound, SIGNED) > bound_wide_int ().get_precision ())
4108 : return;
4109 :
4110 : /* If we have a guaranteed upper bound, record it in the appropriate
4111 : list, unless this is an !is_exit bound (i.e. undefined behavior in
4112 : at_stmt) in a loop with known constant number of iterations. */
4113 16404100 : if (upper
4114 15858099 : && (is_exit
4115 10961289 : || loop->nb_iterations == NULL_TREE
4116 10961289 : || TREE_CODE (loop->nb_iterations) != INTEGER_CST))
4117 : {
4118 10721769 : class nb_iter_bound *elt = ggc_alloc<nb_iter_bound> ();
4119 :
4120 10721769 : elt->bound = bound_wide_int::from (i_bound, SIGNED);
4121 10721769 : elt->stmt = at_stmt;
4122 10721769 : elt->is_exit = is_exit;
4123 10721769 : elt->next = loop->bounds;
4124 10721769 : loop->bounds = elt;
4125 : }
4126 :
4127 : /* If statement is executed on every path to the loop latch, we can directly
4128 : infer the upper bound on the # of iterations of the loop. */
4129 16404100 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
4130 473269 : upper = false;
4131 :
4132 : /* Update the number of iteration estimates according to the bound.
4133 : If at_stmt is an exit then the loop latch is executed at most BOUND times,
4134 : otherwise it can be executed BOUND + 1 times. We will lower the estimate
4135 : later if such statement must be executed on last iteration */
4136 16404100 : if (is_exit)
4137 4896816 : delta = 0;
4138 : else
4139 11507284 : delta = 1;
4140 16404100 : widest_int new_i_bound = i_bound + delta;
4141 :
4142 : /* If an overflow occurred, ignore the result. */
4143 16404100 : if (wi::ltu_p (new_i_bound, delta))
4144 0 : return;
4145 :
4146 16404100 : if (upper && !is_exit)
4147 10559783 : do_warn_aggressive_loop_optimizations (loop, new_i_bound, at_stmt);
4148 16404100 : record_niter_bound (loop, new_i_bound, realistic, upper);
4149 16404127 : }
4150 :
4151 : /* Records the control iv analyzed in NITER for LOOP if the iv is valid
4152 : and doesn't overflow. */
4153 :
4154 : static void
4155 4896824 : record_control_iv (class loop *loop, class tree_niter_desc *niter)
4156 : {
4157 4896824 : struct control_iv *iv;
4158 :
4159 4896824 : if (!niter->control.base || !niter->control.step)
4160 : return;
4161 :
4162 4855657 : if (!integer_onep (niter->assumptions) || !niter->control.no_overflow)
4163 : return;
4164 :
4165 4703059 : iv = ggc_alloc<control_iv> ();
4166 4703059 : iv->base = niter->control.base;
4167 4703059 : iv->step = niter->control.step;
4168 4703059 : iv->next = loop->control_ivs;
4169 4703059 : loop->control_ivs = iv;
4170 :
4171 4703059 : return;
4172 : }
4173 :
4174 : /* This function returns TRUE if below conditions are satisfied:
4175 : 1) VAR is SSA variable.
4176 : 2) VAR is an IV:{base, step} in its defining loop.
4177 : 3) IV doesn't overflow.
4178 : 4) Both base and step are integer constants.
4179 : 5) Base is the MIN/MAX value depends on IS_MIN.
4180 : Store value of base to INIT correspondingly. */
4181 :
4182 : static bool
4183 123238 : get_cst_init_from_scev (tree var, wide_int *init, bool is_min)
4184 : {
4185 123238 : if (TREE_CODE (var) != SSA_NAME)
4186 : return false;
4187 :
4188 123238 : gimple *def_stmt = SSA_NAME_DEF_STMT (var);
4189 123238 : class loop *loop = loop_containing_stmt (def_stmt);
4190 :
4191 110720 : if (loop == NULL)
4192 : return false;
4193 :
4194 110720 : affine_iv iv;
4195 110720 : if (!simple_iv (loop, loop, var, &iv, false))
4196 : return false;
4197 :
4198 6253 : if (!iv.no_overflow)
4199 : return false;
4200 :
4201 6198 : if (TREE_CODE (iv.base) != INTEGER_CST || TREE_CODE (iv.step) != INTEGER_CST)
4202 : return false;
4203 :
4204 4955 : if (is_min == tree_int_cst_sign_bit (iv.step))
4205 : return false;
4206 :
4207 4722 : *init = wi::to_wide (iv.base);
4208 4722 : return true;
4209 : }
4210 :
4211 : /* Record the estimate on number of iterations of LOOP based on the fact that
4212 : the induction variable BASE + STEP * i evaluated in STMT does not wrap and
4213 : its values belong to the range <LOW, HIGH>. REALISTIC is true if the
4214 : estimated number of iterations is expected to be close to the real one.
4215 : UPPER is true if we are sure the induction variable does not wrap. */
4216 :
4217 : static void
4218 11507297 : record_nonwrapping_iv (class loop *loop, tree base, tree step, gimple *stmt,
4219 : tree low, tree high, bool realistic, bool upper)
4220 : {
4221 11507297 : tree niter_bound, extreme, delta;
4222 11507297 : tree type = TREE_TYPE (base), unsigned_type;
4223 11507297 : tree orig_base = base;
4224 :
4225 11507297 : if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
4226 0 : return;
4227 :
4228 11507297 : if (dump_file && (dump_flags & TDF_DETAILS))
4229 : {
4230 60988 : fprintf (dump_file, "Induction variable (");
4231 60988 : print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
4232 60988 : fprintf (dump_file, ") ");
4233 60988 : print_generic_expr (dump_file, base, TDF_SLIM);
4234 60988 : fprintf (dump_file, " + ");
4235 60988 : print_generic_expr (dump_file, step, TDF_SLIM);
4236 60988 : fprintf (dump_file, " * iteration does not wrap in statement ");
4237 60988 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
4238 60988 : fprintf (dump_file, " in loop %d.\n", loop->num);
4239 : }
4240 :
4241 11507297 : unsigned_type = unsigned_type_for (type);
4242 11507297 : base = fold_convert (unsigned_type, base);
4243 11507297 : step = fold_convert (unsigned_type, step);
4244 :
4245 11507297 : if (tree_int_cst_sign_bit (step))
4246 : {
4247 357544 : wide_int max;
4248 357544 : value_range base_range (TREE_TYPE (orig_base));
4249 715088 : if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
4250 357544 : && !base_range.undefined_p ())
4251 357465 : max = wi::to_wide (base_range.ubound ());
4252 357544 : extreme = fold_convert (unsigned_type, low);
4253 357544 : if (TREE_CODE (orig_base) == SSA_NAME
4254 20092 : && TREE_CODE (high) == INTEGER_CST
4255 20092 : && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
4256 20018 : && ((!base_range.varying_p ()
4257 6870 : && !base_range.undefined_p ())
4258 13227 : || get_cst_init_from_scev (orig_base, &max, false))
4259 364335 : && wi::gts_p (wi::to_wide (high), max))
4260 2229 : base = wide_int_to_tree (unsigned_type, max);
4261 355315 : else if (TREE_CODE (base) != INTEGER_CST
4262 570163 : && dominated_by_p (CDI_DOMINATORS,
4263 214848 : loop->latch, gimple_bb (stmt)))
4264 212945 : base = fold_convert (unsigned_type, high);
4265 357544 : delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
4266 357544 : step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
4267 357545 : }
4268 : else
4269 : {
4270 11149753 : wide_int min;
4271 11149753 : value_range base_range (TREE_TYPE (orig_base));
4272 22299506 : if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
4273 11149753 : && !base_range.undefined_p ())
4274 11147497 : min = wi::to_wide (base_range.lbound ());
4275 11149753 : extreme = fold_convert (unsigned_type, high);
4276 11149753 : if (TREE_CODE (orig_base) == SSA_NAME
4277 878071 : && TREE_CODE (low) == INTEGER_CST
4278 878071 : && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
4279 260706 : && ((!base_range.varying_p ()
4280 152691 : && !base_range.undefined_p ())
4281 110011 : || get_cst_init_from_scev (orig_base, &min, true))
4282 11305170 : && wi::gts_p (min, wi::to_wide (low)))
4283 12534 : base = wide_int_to_tree (unsigned_type, min);
4284 11137219 : else if (TREE_CODE (base) != INTEGER_CST
4285 14594251 : && dominated_by_p (CDI_DOMINATORS,
4286 3457032 : loop->latch, gimple_bb (stmt)))
4287 3394254 : base = fold_convert (unsigned_type, low);
4288 11149753 : delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
4289 11149765 : }
4290 :
4291 : /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
4292 : would get out of the range. */
4293 11507297 : niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
4294 11507297 : widest_int max = derive_constant_upper_bound (niter_bound);
4295 11507297 : record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
4296 11507297 : }
4297 :
4298 : /* Determine information about number of iterations a LOOP from the index
4299 : IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
4300 : guaranteed to be executed in every iteration of LOOP. Callback for
4301 : for_each_index. */
4302 :
4303 : struct ilb_data
4304 : {
4305 : class loop *loop;
4306 : gimple *stmt;
4307 : };
4308 :
4309 : static bool
4310 37010340 : idx_infer_loop_bounds (tree base, tree *idx, void *dta)
4311 : {
4312 37010340 : struct ilb_data *data = (struct ilb_data *) dta;
4313 37010340 : tree ev, init, step;
4314 37010340 : tree low, high, type, next;
4315 37010340 : bool sign, upper = true, has_flexible_size = false;
4316 37010340 : class loop *loop = data->loop;
4317 :
4318 37010340 : if (TREE_CODE (base) != ARRAY_REF)
4319 : return true;
4320 :
4321 : /* For arrays that might have flexible sizes, it is not guaranteed that they
4322 : do not really extend over their declared size. */
4323 10208209 : if (array_ref_flexible_size_p (base))
4324 : {
4325 2407532 : has_flexible_size = true;
4326 2407532 : upper = false;
4327 : }
4328 :
4329 10208209 : class loop *dloop = loop_containing_stmt (data->stmt);
4330 10208209 : if (!dloop)
4331 : return true;
4332 :
4333 10208209 : ev = analyze_scalar_evolution (dloop, *idx);
4334 10208209 : ev = instantiate_parameters (loop, ev);
4335 10208209 : init = initial_condition (ev);
4336 10208209 : step = evolution_part_in_loop_num (ev, loop->num);
4337 :
4338 10208209 : if (!init
4339 10208209 : || !step
4340 5780261 : || TREE_CODE (step) != INTEGER_CST
4341 4418673 : || integer_zerop (step)
4342 4418673 : || tree_contains_chrecs (init, NULL)
4343 14626882 : || chrec_contains_symbols_defined_in_loop (init, loop->num))
4344 : return true;
4345 :
4346 4418673 : low = array_ref_low_bound (base);
4347 4418673 : high = array_ref_up_bound (base);
4348 :
4349 : /* The case of nonconstant bounds could be handled, but it would be
4350 : complicated. */
4351 4418673 : if (TREE_CODE (low) != INTEGER_CST
4352 4418673 : || !high
4353 3694330 : || TREE_CODE (high) != INTEGER_CST)
4354 : return true;
4355 3482045 : sign = tree_int_cst_sign_bit (step);
4356 3482045 : type = TREE_TYPE (step);
4357 :
4358 : /* The array that might have flexible size most likely extends
4359 : beyond its bounds. */
4360 3482045 : if (has_flexible_size
4361 3482045 : && operand_equal_p (low, high, 0))
4362 : return true;
4363 :
4364 : /* In case the relevant bound of the array does not fit in type, or
4365 : it does, but bound + step (in type) still belongs into the range of the
4366 : array, the index may wrap and still stay within the range of the array
4367 : (consider e.g. if the array is indexed by the full range of
4368 : unsigned char).
4369 :
4370 : To make things simpler, we require both bounds to fit into type, although
4371 : there are cases where this would not be strictly necessary. */
4372 3463650 : if (!int_fits_type_p (high, type)
4373 3463618 : || !int_fits_type_p (low, type))
4374 : return true;
4375 3463618 : low = fold_convert (type, low);
4376 3463618 : high = fold_convert (type, high);
4377 :
4378 3463618 : if (sign)
4379 63764 : next = fold_binary (PLUS_EXPR, type, low, step);
4380 : else
4381 3399854 : next = fold_binary (PLUS_EXPR, type, high, step);
4382 :
4383 3463618 : if (tree_int_cst_compare (low, next) <= 0
4384 3463618 : && tree_int_cst_compare (next, high) <= 0)
4385 : return true;
4386 :
4387 : /* If access is not executed on every iteration, we must ensure that overflow
4388 : may not make the access valid later. */
4389 3463618 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)))
4390 : {
4391 465707 : if (scev_probably_wraps_p (NULL_TREE,
4392 465707 : initial_condition_in_loop_num (ev, loop->num),
4393 : step, data->stmt, loop, true))
4394 3463618 : upper = false;
4395 : }
4396 : else
4397 2997911 : record_nonwrapping_chrec (ev);
4398 :
4399 3463618 : record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper);
4400 3463618 : return true;
4401 : }
4402 :
4403 : /* Determine information about number of iterations a LOOP from the bounds
4404 : of arrays in the data reference REF accessed in STMT. RELIABLE is true if
4405 : STMT is guaranteed to be executed in every iteration of LOOP.*/
4406 :
4407 : static void
4408 37872382 : infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref)
4409 : {
4410 37872382 : struct ilb_data data;
4411 :
4412 37872382 : data.loop = loop;
4413 37872382 : data.stmt = stmt;
4414 0 : for_each_index (&ref, idx_infer_loop_bounds, &data);
4415 0 : }
4416 :
4417 : /* Determine information about number of iterations of a LOOP from the way
4418 : arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
4419 : executed in every iteration of LOOP. */
4420 :
4421 : static void
4422 276754956 : infer_loop_bounds_from_array (class loop *loop, gimple *stmt)
4423 : {
4424 276754956 : if (is_gimple_assign (stmt))
4425 : {
4426 107123704 : tree op0 = gimple_assign_lhs (stmt);
4427 107123704 : tree op1 = gimple_assign_rhs1 (stmt);
4428 :
4429 : /* For each memory access, analyze its access function
4430 : and record a bound on the loop iteration domain. */
4431 107123704 : if (REFERENCE_CLASS_P (op0))
4432 15096374 : infer_loop_bounds_from_ref (loop, stmt, op0);
4433 :
4434 107123704 : if (REFERENCE_CLASS_P (op1))
4435 22601099 : infer_loop_bounds_from_ref (loop, stmt, op1);
4436 : }
4437 169631252 : else if (is_gimple_call (stmt))
4438 : {
4439 7530753 : tree arg, lhs;
4440 7530753 : unsigned i, n = gimple_call_num_args (stmt);
4441 :
4442 7530753 : lhs = gimple_call_lhs (stmt);
4443 7530753 : if (lhs && REFERENCE_CLASS_P (lhs))
4444 5044 : infer_loop_bounds_from_ref (loop, stmt, lhs);
4445 :
4446 24406254 : for (i = 0; i < n; i++)
4447 : {
4448 16875501 : arg = gimple_call_arg (stmt, i);
4449 16875501 : if (REFERENCE_CLASS_P (arg))
4450 169865 : infer_loop_bounds_from_ref (loop, stmt, arg);
4451 : }
4452 : }
4453 276754956 : }
4454 :
4455 : /* Determine information about number of iterations of a LOOP from the fact
4456 : that pointer arithmetics in STMT does not overflow. */
4457 :
4458 : static void
4459 136473902 : infer_loop_bounds_from_pointer_arith (class loop *loop, gimple *stmt)
4460 : {
4461 136473902 : tree def, base, step, scev, type, low, high;
4462 136473902 : tree var, ptr;
4463 :
4464 136473902 : if (!is_gimple_assign (stmt)
4465 136473902 : || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
4466 : return;
4467 :
4468 4741945 : def = gimple_assign_lhs (stmt);
4469 4741945 : if (TREE_CODE (def) != SSA_NAME)
4470 : return;
4471 :
4472 4741945 : type = TREE_TYPE (def);
4473 4741945 : if (!nowrap_type_p (type))
4474 : return;
4475 :
4476 4741608 : ptr = gimple_assign_rhs1 (stmt);
4477 4741608 : if (!expr_invariant_in_loop_p (loop, ptr))
4478 : return;
4479 :
4480 2605428 : var = gimple_assign_rhs2 (stmt);
4481 2605428 : if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
4482 : return;
4483 :
4484 2605428 : class loop *uloop = loop_containing_stmt (stmt);
4485 2605428 : scev = instantiate_parameters (loop, analyze_scalar_evolution (uloop, def));
4486 2605428 : if (chrec_contains_undetermined (scev))
4487 : return;
4488 :
4489 2151167 : base = initial_condition_in_loop_num (scev, loop->num);
4490 2151167 : step = evolution_part_in_loop_num (scev, loop->num);
4491 :
4492 2151167 : if (!base || !step
4493 2102412 : || TREE_CODE (step) != INTEGER_CST
4494 1913324 : || tree_contains_chrecs (base, NULL)
4495 4064491 : || chrec_contains_symbols_defined_in_loop (base, loop->num))
4496 : return;
4497 :
4498 1913324 : low = lower_bound_in_type (type, type);
4499 1913324 : high = upper_bound_in_type (type, type);
4500 :
4501 : /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
4502 : produce a NULL pointer. The contrary would mean NULL points to an object,
4503 : while NULL is supposed to compare unequal with the address of all objects.
4504 : Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
4505 : NULL pointer since that would mean wrapping, which we assume here not to
4506 : happen. So, we can exclude NULL from the valid range of pointer
4507 : arithmetic. */
4508 1913324 : if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
4509 1913312 : low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
4510 :
4511 1913324 : record_nonwrapping_chrec (scev);
4512 1913324 : record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
4513 : }
4514 :
4515 : /* Determine information about number of iterations of a LOOP from the fact
4516 : that signed arithmetics in STMT does not overflow. */
4517 :
4518 : static void
4519 136473902 : infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
4520 : {
4521 136473902 : tree def, base, step, scev, type, low, high;
4522 :
4523 136473902 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
4524 130343547 : return;
4525 :
4526 54175783 : def = gimple_assign_lhs (stmt);
4527 :
4528 54175783 : if (TREE_CODE (def) != SSA_NAME)
4529 : return;
4530 :
4531 46178923 : type = TREE_TYPE (def);
4532 46178923 : if (!INTEGRAL_TYPE_P (type)
4533 46178923 : || !TYPE_OVERFLOW_UNDEFINED (type))
4534 : return;
4535 :
4536 15633523 : scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
4537 15633523 : if (chrec_contains_undetermined (scev))
4538 : return;
4539 :
4540 7633772 : base = initial_condition_in_loop_num (scev, loop->num);
4541 7633772 : step = evolution_part_in_loop_num (scev, loop->num);
4542 :
4543 7633772 : if (!base || !step
4544 6794822 : || TREE_CODE (step) != INTEGER_CST
4545 6130355 : || tree_contains_chrecs (base, NULL)
4546 13764127 : || chrec_contains_symbols_defined_in_loop (base, loop->num))
4547 : return;
4548 :
4549 6130355 : low = lower_bound_in_type (type, type);
4550 6130355 : high = upper_bound_in_type (type, type);
4551 6130355 : int_range_max r (TREE_TYPE (def));
4552 12260710 : get_range_query (cfun)->range_of_expr (r, def);
4553 6130355 : if (!r.varying_p () && !r.undefined_p ())
4554 : {
4555 5626133 : low = wide_int_to_tree (type, r.lower_bound ());
4556 5626145 : high = wide_int_to_tree (type, r.upper_bound ());
4557 : }
4558 :
4559 6130355 : record_nonwrapping_chrec (scev);
4560 6130355 : record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
4561 6130355 : }
4562 :
4563 : /* The following analyzers are extracting information on the bounds
4564 : of LOOP from the following undefined behaviors:
4565 :
4566 : - data references should not access elements over the statically
4567 : allocated size,
4568 :
4569 : - signed variables should not overflow when flag_wrapv is not set.
4570 : */
4571 :
4572 : static void
4573 6696792 : infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs)
4574 : {
4575 6696792 : unsigned i;
4576 6696792 : gimple_stmt_iterator bsi;
4577 6696792 : basic_block bb;
4578 6696792 : bool reliable;
4579 :
4580 46047208 : for (i = 0; i < loop->num_nodes; i++)
4581 : {
4582 39350416 : bb = bbs[i];
4583 :
4584 : /* If BB is not executed in each iteration of the loop, we cannot
4585 : use the operations in it to infer reliable upper bound on the
4586 : # of iterations of the loop. However, we can use it as a guess.
4587 : Reliable guesses come only from array bounds. */
4588 39350416 : reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
4589 :
4590 355455788 : for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4591 : {
4592 276754956 : gimple *stmt = gsi_stmt (bsi);
4593 :
4594 276754956 : infer_loop_bounds_from_array (loop, stmt);
4595 :
4596 276754956 : if (reliable)
4597 : {
4598 136473902 : infer_loop_bounds_from_signedness (loop, stmt);
4599 136473902 : infer_loop_bounds_from_pointer_arith (loop, stmt);
4600 : }
4601 : }
4602 :
4603 : }
4604 6696792 : }
4605 :
4606 : /* Compare wide ints, callback for qsort. */
4607 :
4608 : static int
4609 28184 : wide_int_cmp (const void *p1, const void *p2)
4610 : {
4611 28184 : const bound_wide_int *d1 = (const bound_wide_int *) p1;
4612 28184 : const bound_wide_int *d2 = (const bound_wide_int *) p2;
4613 28184 : return wi::cmpu (*d1, *d2);
4614 : }
4615 :
4616 : /* Return index of BOUND in BOUNDS array sorted in increasing order.
4617 : Lookup by binary search. */
4618 :
4619 : static int
4620 6865 : bound_index (const vec<bound_wide_int> &bounds, const bound_wide_int &bound)
4621 : {
4622 6865 : unsigned int end = bounds.length ();
4623 6865 : unsigned int begin = 0;
4624 :
4625 : /* Find a matching index by means of a binary search. */
4626 7793 : while (begin != end)
4627 : {
4628 7793 : unsigned int middle = (begin + end) / 2;
4629 7793 : bound_wide_int index = bounds[middle];
4630 :
4631 7793 : if (index == bound)
4632 6865 : return middle;
4633 928 : else if (wi::ltu_p (index, bound))
4634 236 : begin = middle + 1;
4635 : else
4636 : end = middle;
4637 : }
4638 0 : gcc_unreachable ();
4639 : }
4640 :
4641 : /* We recorded loop bounds only for statements dominating loop latch (and thus
4642 : executed each loop iteration). If there are any bounds on statements not
4643 : dominating the loop latch we can improve the estimate by walking the loop
4644 : body and seeing if every path from loop header to loop latch contains
4645 : some bounded statement. */
4646 :
4647 : static void
4648 6738784 : discover_iteration_bound_by_body_walk (class loop *loop)
4649 : {
4650 6738784 : class nb_iter_bound *elt;
4651 6738784 : auto_vec<bound_wide_int> bounds;
4652 6738784 : vec<vec<basic_block> > queues = vNULL;
4653 6738784 : vec<basic_block> queue = vNULL;
4654 6738784 : ptrdiff_t queue_index;
4655 6738784 : ptrdiff_t latch_index = 0;
4656 :
4657 : /* Discover what bounds may interest us. */
4658 17460553 : for (elt = loop->bounds; elt; elt = elt->next)
4659 : {
4660 10721769 : bound_wide_int bound = elt->bound;
4661 :
4662 : /* Exit terminates loop at given iteration, while non-exits produce undefined
4663 : effect on the next iteration. */
4664 10721769 : if (!elt->is_exit)
4665 : {
4666 5824959 : bound += 1;
4667 : /* If an overflow occurred, ignore the result. */
4668 5824959 : if (bound == 0)
4669 0 : continue;
4670 : }
4671 :
4672 10721769 : if (!loop->any_upper_bound
4673 10721769 : || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
4674 6865 : bounds.safe_push (bound);
4675 : }
4676 :
4677 : /* Exit early if there is nothing to do. */
4678 6738784 : if (!bounds.exists ())
4679 6734901 : return;
4680 :
4681 3883 : if (dump_file && (dump_flags & TDF_DETAILS))
4682 16 : fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n");
4683 :
4684 : /* Sort the bounds in decreasing order. */
4685 3883 : bounds.qsort (wide_int_cmp);
4686 :
4687 : /* For every basic block record the lowest bound that is guaranteed to
4688 : terminate the loop. */
4689 :
4690 3883 : hash_map<basic_block, ptrdiff_t> bb_bounds;
4691 19429 : for (elt = loop->bounds; elt; elt = elt->next)
4692 : {
4693 15546 : bound_wide_int bound = elt->bound;
4694 15546 : if (!elt->is_exit)
4695 : {
4696 11134 : bound += 1;
4697 : /* If an overflow occurred, ignore the result. */
4698 11134 : if (bound == 0)
4699 0 : continue;
4700 : }
4701 :
4702 15546 : if (!loop->any_upper_bound
4703 15546 : || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
4704 : {
4705 6865 : ptrdiff_t index = bound_index (bounds, bound);
4706 6865 : ptrdiff_t *entry = bb_bounds.get (gimple_bb (elt->stmt));
4707 6865 : if (!entry)
4708 4863 : bb_bounds.put (gimple_bb (elt->stmt), index);
4709 2002 : else if ((ptrdiff_t)*entry > index)
4710 110 : *entry = index;
4711 : }
4712 : }
4713 :
4714 3883 : hash_map<basic_block, ptrdiff_t> block_priority;
4715 :
4716 : /* Perform shortest path discovery loop->header ... loop->latch.
4717 :
4718 : The "distance" is given by the smallest loop bound of basic block
4719 : present in the path and we look for path with largest smallest bound
4720 : on it.
4721 :
4722 : To avoid the need for fibonacci heap on double ints we simply compress
4723 : double ints into indexes to BOUNDS array and then represent the queue
4724 : as arrays of queues for every index.
4725 : Index of BOUNDS.length() means that the execution of given BB has
4726 : no bounds determined.
4727 :
4728 : VISITED is a pointer map translating basic block into smallest index
4729 : it was inserted into the priority queue with. */
4730 3883 : latch_index = -1;
4731 :
4732 : /* Start walk in loop header with index set to infinite bound. */
4733 3883 : queue_index = bounds.length ();
4734 3883 : queues.safe_grow_cleared (queue_index + 1, true);
4735 3883 : queue.safe_push (loop->header);
4736 3883 : queues[queue_index] = queue;
4737 3883 : block_priority.put (loop->header, queue_index);
4738 :
4739 18514 : for (; queue_index >= 0; queue_index--)
4740 : {
4741 10748 : if (latch_index < queue_index)
4742 : {
4743 42806 : while (queues[queue_index].length ())
4744 : {
4745 38746 : basic_block bb;
4746 38746 : ptrdiff_t bound_index = queue_index;
4747 38746 : edge e;
4748 38746 : edge_iterator ei;
4749 :
4750 38746 : queue = queues[queue_index];
4751 38746 : bb = queue.pop ();
4752 :
4753 : /* OK, we later inserted the BB with lower priority, skip it. */
4754 38746 : if (*block_priority.get (bb) > queue_index)
4755 0 : continue;
4756 :
4757 : /* See if we can improve the bound. */
4758 38746 : ptrdiff_t *entry = bb_bounds.get (bb);
4759 38746 : if (entry && *entry < bound_index)
4760 4316 : bound_index = *entry;
4761 :
4762 : /* Insert successors into the queue, watch for latch edge
4763 : and record greatest index we saw. */
4764 98827 : FOR_EACH_EDGE (e, ei, bb->succs)
4765 : {
4766 60081 : bool insert = false;
4767 :
4768 60081 : if (loop_exit_edge_p (loop, e))
4769 10590 : continue;
4770 :
4771 49491 : if (e == loop_latch_edge (loop)
4772 49491 : && latch_index < bound_index)
4773 : latch_index = bound_index;
4774 45608 : else if (!(entry = block_priority.get (e->dest)))
4775 : {
4776 36421 : insert = true;
4777 36421 : block_priority.put (e->dest, bound_index);
4778 : }
4779 9187 : else if (*entry < bound_index)
4780 : {
4781 146 : insert = true;
4782 146 : *entry = bound_index;
4783 : }
4784 :
4785 36567 : if (insert)
4786 36567 : queues[bound_index].safe_push (e->dest);
4787 : }
4788 : }
4789 : }
4790 10748 : queues[queue_index].release ();
4791 : }
4792 :
4793 3883 : gcc_assert (latch_index >= 0);
4794 3883 : if ((unsigned)latch_index < bounds.length ())
4795 : {
4796 95 : if (dump_file && (dump_flags & TDF_DETAILS))
4797 : {
4798 0 : fprintf (dump_file, "Found better loop bound ");
4799 0 : print_decu (bounds[latch_index], dump_file);
4800 0 : fprintf (dump_file, "\n");
4801 : }
4802 95 : record_niter_bound (loop, widest_int::from (bounds[latch_index],
4803 : SIGNED), false, true);
4804 : }
4805 :
4806 3883 : queues.release ();
4807 6738784 : }
4808 :
4809 : /* See if every path cross the loop goes through a statement that is known
4810 : to not execute at the last iteration. In that case we can decrease iteration
4811 : count by 1. */
4812 :
4813 : static void
4814 6738784 : maybe_lower_iteration_bound (class loop *loop)
4815 : {
4816 6738784 : hash_set<gimple *> *not_executed_last_iteration = NULL;
4817 6738784 : class nb_iter_bound *elt;
4818 6738784 : bool found_exit = false;
4819 6738784 : auto_vec<basic_block> queue;
4820 6738784 : bitmap visited;
4821 :
4822 : /* Collect all statements with interesting (i.e. lower than
4823 : nb_iterations_upper_bound) bound on them.
4824 :
4825 : TODO: Due to the way record_estimate choose estimates to store, the bounds
4826 : will be always nb_iterations_upper_bound-1. We can change this to record
4827 : also statements not dominating the loop latch and update the walk below
4828 : to the shortest path algorithm. */
4829 17460553 : for (elt = loop->bounds; elt; elt = elt->next)
4830 : {
4831 10721769 : if (!elt->is_exit
4832 10721769 : && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound))
4833 : {
4834 2243339 : if (!not_executed_last_iteration)
4835 1225357 : not_executed_last_iteration = new hash_set<gimple *>;
4836 2243339 : not_executed_last_iteration->add (elt->stmt);
4837 : }
4838 : }
4839 6738784 : if (!not_executed_last_iteration)
4840 5513427 : return;
4841 :
4842 : /* Start DFS walk in the loop header and see if we can reach the
4843 : loop latch or any of the exits (including statements with side
4844 : effects that may terminate the loop otherwise) without visiting
4845 : any of the statements known to have undefined effect on the last
4846 : iteration. */
4847 1225357 : queue.safe_push (loop->header);
4848 1225357 : visited = BITMAP_ALLOC (NULL);
4849 1225357 : bitmap_set_bit (visited, loop->header->index);
4850 1225357 : found_exit = false;
4851 :
4852 1320254 : do
4853 : {
4854 1320254 : basic_block bb = queue.pop ();
4855 1320254 : gimple_stmt_iterator gsi;
4856 1320254 : bool stmt_found = false;
4857 :
4858 : /* Loop for possible exits and statements bounding the execution. */
4859 7033507 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4860 : {
4861 4458336 : gimple *stmt = gsi_stmt (gsi);
4862 4458336 : if (not_executed_last_iteration->contains (stmt))
4863 : {
4864 : stmt_found = true;
4865 65337 : break;
4866 : }
4867 4416575 : if (gimple_has_side_effects (stmt))
4868 : {
4869 : found_exit = true;
4870 : break;
4871 : }
4872 : }
4873 1320254 : if (found_exit)
4874 : break;
4875 :
4876 : /* If no bounding statement is found, continue the walk. */
4877 1296678 : if (!stmt_found)
4878 : {
4879 1254917 : edge e;
4880 1254917 : edge_iterator ei;
4881 :
4882 2112120 : FOR_EACH_EDGE (e, ei, bb->succs)
4883 : {
4884 2022681 : if (loop_exit_edge_p (loop, e)
4885 857880 : || e == loop_latch_edge (loop)
4886 : /* When exiting an inner loop, verify it is finite. */
4887 857845 : || (!flow_bb_inside_loop_p (bb->loop_father, e->dest)
4888 9925 : && !finite_loop_p (bb->loop_father))
4889 : /* When we enter an irreducible region and the entry
4890 : does not contain a bounding stmt assume it might be
4891 : infinite. */
4892 2879884 : || (bb->flags & BB_IRREDUCIBLE_LOOP))
4893 : {
4894 : found_exit = true;
4895 : break;
4896 : }
4897 857203 : if (bitmap_set_bit (visited, e->dest->index))
4898 831986 : queue.safe_push (e->dest);
4899 : }
4900 : }
4901 : }
4902 1296678 : while (queue.length () && !found_exit);
4903 :
4904 : /* If every path through the loop reach bounding statement before exit,
4905 : then we know the last iteration of the loop will have undefined effect
4906 : and we can decrease number of iterations. */
4907 :
4908 1225357 : if (!found_exit)
4909 : {
4910 36303 : if (dump_file && (dump_flags & TDF_DETAILS))
4911 68 : fprintf (dump_file, "Reducing loop iteration estimate by 1; "
4912 : "undefined statement must be executed at the last iteration.\n");
4913 72606 : record_niter_bound (loop, widest_int::from (loop->nb_iterations_upper_bound,
4914 108909 : SIGNED) - 1,
4915 : false, true);
4916 : }
4917 :
4918 1225357 : BITMAP_FREE (visited);
4919 1225357 : delete not_executed_last_iteration;
4920 6738784 : }
4921 :
4922 : /* Get expected upper bound for number of loop iterations for
4923 : BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND. */
4924 :
4925 : static tree
4926 5225243 : get_upper_bound_based_on_builtin_expr_with_prob (gcond *cond)
4927 : {
4928 5225243 : if (cond == NULL)
4929 : return NULL_TREE;
4930 :
4931 5067473 : tree lhs = gimple_cond_lhs (cond);
4932 5067473 : if (TREE_CODE (lhs) != SSA_NAME)
4933 : return NULL_TREE;
4934 :
4935 5067286 : gimple *stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
4936 5067286 : gcall *def = dyn_cast<gcall *> (stmt);
4937 189620 : if (def == NULL)
4938 : return NULL_TREE;
4939 :
4940 189620 : tree decl = gimple_call_fndecl (def);
4941 189620 : if (!decl
4942 161106 : || !fndecl_built_in_p (decl, BUILT_IN_EXPECT_WITH_PROBABILITY)
4943 189628 : || gimple_call_num_args (stmt) != 3)
4944 : return NULL_TREE;
4945 :
4946 8 : tree c = gimple_call_arg (def, 1);
4947 8 : tree condt = TREE_TYPE (lhs);
4948 8 : tree res = fold_build2 (gimple_cond_code (cond),
4949 : condt, c,
4950 : gimple_cond_rhs (cond));
4951 8 : if (TREE_CODE (res) != INTEGER_CST)
4952 : return NULL_TREE;
4953 :
4954 :
4955 8 : tree prob = gimple_call_arg (def, 2);
4956 8 : tree t = TREE_TYPE (prob);
4957 8 : tree one
4958 16 : = build_real_from_int_cst (t,
4959 8 : integer_one_node);
4960 8 : if (integer_zerop (res))
4961 4 : prob = fold_build2 (MINUS_EXPR, t, one, prob);
4962 8 : tree r = fold_build2 (RDIV_EXPR, t, one, prob);
4963 8 : if (TREE_CODE (r) != REAL_CST)
4964 : return NULL_TREE;
4965 :
4966 6 : HOST_WIDE_INT probi
4967 6 : = real_to_integer (TREE_REAL_CST_PTR (r));
4968 6 : return build_int_cst (condt, probi);
4969 : }
4970 :
4971 : /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4972 : is true also use estimates derived from undefined behavior. */
4973 :
4974 : void
4975 26685237 : estimate_numbers_of_iterations (class loop *loop)
4976 : {
4977 26685237 : tree niter, type;
4978 26685237 : unsigned i;
4979 26685237 : class tree_niter_desc niter_desc;
4980 26685237 : edge ex;
4981 26685237 : widest_int bound;
4982 26685237 : edge likely_exit;
4983 :
4984 : /* Give up if we already have tried to compute an estimation. */
4985 26685237 : if (loop->estimate_state != EST_NOT_COMPUTED)
4986 19946453 : return;
4987 :
4988 6738784 : if (dump_file && (dump_flags & TDF_DETAILS))
4989 15732 : fprintf (dump_file, "Estimating # of iterations of loop %d\n", loop->num);
4990 :
4991 6738784 : loop->estimate_state = EST_AVAILABLE;
4992 :
4993 6738784 : sreal nit;
4994 6738784 : bool reliable;
4995 :
4996 : /* If we have a measured profile, use it to estimate the number of
4997 : iterations. Normally this is recorded by branch_prob right after
4998 : reading the profile. In case we however found a new loop, record the
4999 : information here.
5000 :
5001 : Explicitly check for profile status so we do not report
5002 : wrong prediction hitrates for guessed loop iterations heuristics.
5003 : Do not recompute already recorded bounds - we ought to be better on
5004 : updating iteration bounds than updating profile in general and thus
5005 : recomputing iteration bounds later in the compilation process will just
5006 : introduce random roundoff errors. */
5007 6738784 : if (!loop->any_estimate
5008 4605328 : && expected_loop_iterations_by_profile (loop, &nit, &reliable)
5009 10433644 : && reliable)
5010 : {
5011 19 : bound = nit.to_nearest_int ();
5012 19 : record_niter_bound (loop, bound, true, false);
5013 : }
5014 :
5015 : /* Ensure that loop->nb_iterations is computed if possible. If it turns out
5016 : to be constant, we avoid undefined behavior implied bounds and instead
5017 : diagnose those loops with -Waggressive-loop-optimizations. */
5018 6738784 : number_of_latch_executions (loop);
5019 :
5020 6738784 : basic_block *body = get_loop_body (loop);
5021 6738784 : auto_vec<edge> exits = get_loop_exit_edges (loop, body);
5022 6738784 : likely_exit = single_likely_exit (loop, exits);
5023 25607588 : FOR_EACH_VEC_ELT (exits, i, ex)
5024 : {
5025 12130020 : if (ex == likely_exit)
5026 : {
5027 5225243 : gimple *stmt = *gsi_last_bb (ex->src);
5028 5225243 : if (stmt != NULL)
5029 : {
5030 5225243 : gcond *cond = dyn_cast<gcond *> (stmt);
5031 5225243 : tree niter_bound
5032 5225243 : = get_upper_bound_based_on_builtin_expr_with_prob (cond);
5033 5225243 : if (niter_bound != NULL_TREE)
5034 : {
5035 6 : widest_int max = derive_constant_upper_bound (niter_bound);
5036 6 : record_estimate (loop, niter_bound, max, cond,
5037 : true, true, false);
5038 6 : }
5039 : }
5040 : }
5041 :
5042 12130020 : if (!number_of_iterations_exit (loop, ex, &niter_desc,
5043 : false, false, body))
5044 7233196 : continue;
5045 :
5046 4896824 : niter = niter_desc.niter;
5047 4896824 : type = TREE_TYPE (niter);
5048 4896824 : if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
5049 756354 : niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
5050 : build_int_cst (type, 0),
5051 : niter);
5052 4896824 : record_estimate (loop, niter, niter_desc.max,
5053 : last_nondebug_stmt (ex->src),
5054 : true, ex == likely_exit, true);
5055 4896824 : record_control_iv (loop, &niter_desc);
5056 : }
5057 :
5058 6738784 : if (flag_aggressive_loop_optimizations)
5059 6696792 : infer_loop_bounds_from_undefined (loop, body);
5060 6738784 : free (body);
5061 :
5062 6738784 : discover_iteration_bound_by_body_walk (loop);
5063 :
5064 6738784 : maybe_lower_iteration_bound (loop);
5065 :
5066 : /* If we know the exact number of iterations of this loop, try to
5067 : not break code with undefined behavior by not recording smaller
5068 : maximum number of iterations. */
5069 6738784 : if (loop->nb_iterations
5070 6738784 : && TREE_CODE (loop->nb_iterations) == INTEGER_CST
5071 13477568 : && (wi::min_precision (wi::to_widest (loop->nb_iterations), SIGNED)
5072 2056246 : <= bound_wide_int ().get_precision ()))
5073 : {
5074 2056246 : loop->any_upper_bound = true;
5075 2056246 : loop->nb_iterations_upper_bound
5076 2056246 : = bound_wide_int::from (wi::to_widest (loop->nb_iterations), SIGNED);
5077 : }
5078 26685251 : }
5079 :
5080 : /* Sets NIT to the estimated number of executions of the latch of the
5081 : LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
5082 : large as the number of iterations. If we have no reliable estimate,
5083 : the function returns false, otherwise returns true. */
5084 :
5085 : bool
5086 9399897 : estimated_loop_iterations (class loop *loop, widest_int *nit)
5087 : {
5088 : /* When SCEV information is available, try to update loop iterations
5089 : estimate. Otherwise just return whatever we recorded earlier. */
5090 9399897 : if (scev_initialized_p ())
5091 9399897 : estimate_numbers_of_iterations (loop);
5092 :
5093 9399897 : return (get_estimated_loop_iterations (loop, nit));
5094 : }
5095 :
5096 : /* Similar to estimated_loop_iterations, but returns the estimate only
5097 : if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
5098 : on the number of iterations of LOOP could not be derived, returns -1. */
5099 :
5100 : HOST_WIDE_INT
5101 9130972 : estimated_loop_iterations_int (class loop *loop)
5102 : {
5103 9130972 : widest_int nit;
5104 9130972 : HOST_WIDE_INT hwi_nit;
5105 :
5106 9130972 : if (!estimated_loop_iterations (loop, &nit))
5107 : return -1;
5108 :
5109 4024798 : if (!wi::fits_shwi_p (nit))
5110 : return -1;
5111 4024792 : hwi_nit = nit.to_shwi ();
5112 :
5113 4024792 : return hwi_nit < 0 ? -1 : hwi_nit;
5114 9130972 : }
5115 :
5116 :
5117 : /* Sets NIT to an upper bound for the maximum number of executions of the
5118 : latch of the LOOP. If we have no reliable estimate, the function returns
5119 : false, otherwise returns true. */
5120 :
5121 : bool
5122 8877805 : max_loop_iterations (class loop *loop, widest_int *nit)
5123 : {
5124 : /* When SCEV information is available, try to update loop iterations
5125 : estimate. Otherwise just return whatever we recorded earlier. */
5126 8877805 : if (scev_initialized_p ())
5127 8869841 : estimate_numbers_of_iterations (loop);
5128 :
5129 8877805 : return get_max_loop_iterations (loop, nit);
5130 : }
5131 :
5132 : /* Similar to max_loop_iterations, but returns the estimate only
5133 : if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
5134 : on the number of iterations of LOOP could not be derived, returns -1. */
5135 :
5136 : HOST_WIDE_INT
5137 2330422 : max_loop_iterations_int (class loop *loop)
5138 : {
5139 2330422 : widest_int nit;
5140 2330422 : HOST_WIDE_INT hwi_nit;
5141 :
5142 2330422 : if (!max_loop_iterations (loop, &nit))
5143 : return -1;
5144 :
5145 1763517 : if (!wi::fits_shwi_p (nit))
5146 : return -1;
5147 1689092 : hwi_nit = nit.to_shwi ();
5148 :
5149 1689092 : return hwi_nit < 0 ? -1 : hwi_nit;
5150 2330422 : }
5151 :
5152 : /* Sets NIT to an likely upper bound for the maximum number of executions of the
5153 : latch of the LOOP. If we have no reliable estimate, the function returns
5154 : false, otherwise returns true. */
5155 :
5156 : bool
5157 373166 : likely_max_loop_iterations (class loop *loop, widest_int *nit)
5158 : {
5159 : /* When SCEV information is available, try to update loop iterations
5160 : estimate. Otherwise just return whatever we recorded earlier. */
5161 373166 : if (scev_initialized_p ())
5162 373166 : estimate_numbers_of_iterations (loop);
5163 :
5164 373166 : return get_likely_max_loop_iterations (loop, nit);
5165 : }
5166 :
5167 : /* Similar to max_loop_iterations, but returns the estimate only
5168 : if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
5169 : on the number of iterations of LOOP could not be derived, returns -1. */
5170 :
5171 : HOST_WIDE_INT
5172 111332 : likely_max_loop_iterations_int (class loop *loop)
5173 : {
5174 111332 : widest_int nit;
5175 111332 : HOST_WIDE_INT hwi_nit;
5176 :
5177 111332 : if (!likely_max_loop_iterations (loop, &nit))
5178 : return -1;
5179 :
5180 90760 : if (!wi::fits_shwi_p (nit))
5181 : return -1;
5182 83011 : hwi_nit = nit.to_shwi ();
5183 :
5184 83011 : return hwi_nit < 0 ? -1 : hwi_nit;
5185 111332 : }
5186 :
5187 : /* Returns an estimate for the number of executions of statements
5188 : in the LOOP. For statements before the loop exit, this exceeds
5189 : the number of execution of the latch by one. */
5190 :
5191 : HOST_WIDE_INT
5192 8953271 : estimated_stmt_executions_int (class loop *loop)
5193 : {
5194 8953271 : HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
5195 8953271 : HOST_WIDE_INT snit;
5196 :
5197 8953271 : if (nit == -1)
5198 : return -1;
5199 :
5200 3958585 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
5201 :
5202 : /* If the computation overflows, return -1. */
5203 3958585 : return snit < 0 ? -1 : snit;
5204 : }
5205 :
5206 : /* Sets NIT to the maximum number of executions of the latch of the
5207 : LOOP, plus one. If we have no reliable estimate, the function returns
5208 : false, otherwise returns true. */
5209 :
5210 : bool
5211 154 : max_stmt_executions (class loop *loop, widest_int *nit)
5212 : {
5213 154 : widest_int nit_minus_one;
5214 :
5215 154 : if (!max_loop_iterations (loop, nit))
5216 : return false;
5217 :
5218 154 : nit_minus_one = *nit;
5219 :
5220 154 : *nit += 1;
5221 :
5222 154 : return wi::gtu_p (*nit, nit_minus_one);
5223 154 : }
5224 :
5225 : /* Sets NIT to the estimated maximum number of executions of the latch of the
5226 : LOOP, plus one. If we have no likely estimate, the function returns
5227 : false, otherwise returns true. */
5228 :
5229 : bool
5230 261834 : likely_max_stmt_executions (class loop *loop, widest_int *nit)
5231 : {
5232 261834 : widest_int nit_minus_one;
5233 :
5234 261834 : if (!likely_max_loop_iterations (loop, nit))
5235 : return false;
5236 :
5237 149017 : nit_minus_one = *nit;
5238 :
5239 149017 : *nit += 1;
5240 :
5241 149017 : return wi::gtu_p (*nit, nit_minus_one);
5242 261834 : }
5243 :
5244 : /* Sets NIT to the estimated number of executions of the latch of the
5245 : LOOP, plus one. If we have no reliable estimate, the function returns
5246 : false, otherwise returns true. */
5247 :
5248 : bool
5249 268925 : estimated_stmt_executions (class loop *loop, widest_int *nit)
5250 : {
5251 268925 : widest_int nit_minus_one;
5252 :
5253 268925 : if (!estimated_loop_iterations (loop, nit))
5254 : return false;
5255 :
5256 5812 : nit_minus_one = *nit;
5257 :
5258 5812 : *nit += 1;
5259 :
5260 5812 : return wi::gtu_p (*nit, nit_minus_one);
5261 268925 : }
5262 :
5263 : /* Records estimates on numbers of iterations of loops. */
5264 :
5265 : void
5266 1260739 : estimate_numbers_of_iterations (function *fn)
5267 : {
5268 7603704 : for (auto loop : loops_list (fn, 0))
5269 3821487 : estimate_numbers_of_iterations (loop);
5270 1260739 : }
5271 :
5272 : /* Returns true if statement S1 dominates statement S2. */
5273 :
5274 : bool
5275 2280648 : stmt_dominates_stmt_p (gimple *s1, gimple *s2)
5276 : {
5277 2280648 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
5278 :
5279 2280648 : if (!bb1
5280 2280648 : || s1 == s2)
5281 : return true;
5282 :
5283 2271674 : if (bb1 == bb2)
5284 : {
5285 940674 : gimple_stmt_iterator bsi;
5286 :
5287 940674 : if (gimple_code (s2) == GIMPLE_PHI)
5288 : return false;
5289 :
5290 555251 : if (gimple_code (s1) == GIMPLE_PHI)
5291 : return true;
5292 :
5293 20393115 : for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
5294 19546550 : if (gsi_stmt (bsi) == s1)
5295 : return true;
5296 :
5297 : return false;
5298 : }
5299 :
5300 1331000 : return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
5301 : }
5302 :
5303 : /* Returns true when we can prove that the number of executions of
5304 : STMT in the loop is at most NITER, according to the bound on
5305 : the number of executions of the statement NITER_BOUND->stmt recorded in
5306 : NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
5307 :
5308 : ??? This code can become quite a CPU hog - we can have many bounds,
5309 : and large basic block forcing stmt_dominates_stmt_p to be queried
5310 : many times on a large basic blocks, so the whole thing is O(n^2)
5311 : for scev_probably_wraps_p invocation (that can be done n times).
5312 :
5313 : It would make more sense (and give better answers) to remember BB
5314 : bounds computed by discover_iteration_bound_by_body_walk. */
5315 :
5316 : static bool
5317 2456150 : n_of_executions_at_most (gimple *stmt,
5318 : class nb_iter_bound *niter_bound,
5319 : tree niter)
5320 : {
5321 2456150 : widest_int bound = widest_int::from (niter_bound->bound, SIGNED);
5322 2456150 : tree nit_type = TREE_TYPE (niter), e;
5323 2456150 : enum tree_code cmp;
5324 :
5325 2456150 : gcc_assert (TYPE_UNSIGNED (nit_type));
5326 :
5327 : /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
5328 : the number of iterations is small. */
5329 2456150 : if (!wi::fits_to_tree_p (bound, nit_type))
5330 : return false;
5331 :
5332 : /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
5333 : times. This means that:
5334 :
5335 : -- if NITER_BOUND->is_exit is true, then everything after
5336 : it at most NITER_BOUND->bound times.
5337 :
5338 : -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
5339 : is executed, then NITER_BOUND->stmt is executed as well in the same
5340 : iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
5341 :
5342 : If we can determine that NITER_BOUND->stmt is always executed
5343 : after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
5344 : We conclude that if both statements belong to the same
5345 : basic block and STMT is before NITER_BOUND->stmt and there are no
5346 : statements with side effects in between. */
5347 :
5348 2280648 : if (niter_bound->is_exit)
5349 : {
5350 796993 : if (stmt == niter_bound->stmt
5351 796993 : || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
5352 : return false;
5353 : cmp = GE_EXPR;
5354 : }
5355 : else
5356 : {
5357 1483655 : if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
5358 : {
5359 636699 : gimple_stmt_iterator bsi;
5360 636699 : if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
5361 326535 : || gimple_code (stmt) == GIMPLE_PHI
5362 827011 : || gimple_code (niter_bound->stmt) == GIMPLE_PHI)
5363 452066 : return false;
5364 :
5365 : /* By stmt_dominates_stmt_p we already know that STMT appears
5366 : before NITER_BOUND->STMT. Still need to test that the loop
5367 : cannot be terinated by a side effect in between. */
5368 8404991 : for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
5369 8214679 : gsi_next (&bsi))
5370 8215580 : if (gimple_has_side_effects (gsi_stmt (bsi)))
5371 : return false;
5372 189411 : bound += 1;
5373 378822 : if (bound == 0
5374 189411 : || !wi::fits_to_tree_p (bound, nit_type))
5375 : return false;
5376 : }
5377 : cmp = GT_EXPR;
5378 : }
5379 :
5380 1160581 : e = fold_binary (cmp, boolean_type_node,
5381 : niter, wide_int_to_tree (nit_type, bound));
5382 1160581 : return e && integer_nonzerop (e);
5383 2456150 : }
5384 :
5385 : /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
5386 :
5387 : bool
5388 89182922 : nowrap_type_p (tree type)
5389 : {
5390 12206375 : if ((ANY_INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))
5391 101389293 : && TYPE_OVERFLOW_UNDEFINED (type))
5392 57033437 : return true;
5393 :
5394 : return false;
5395 : }
5396 :
5397 : /* Return an upper bound on the number of times the affine IV {BASE, +, STEP}
5398 : of type TYPE can step while staying within TYPE's range. */
5399 :
5400 : tree
5401 3514599 : get_niter_type_bound (tree type, tree base, tree step)
5402 : {
5403 3514599 : tree unsigned_type = unsigned_type_for (type);
5404 3514599 : tree unsigned_base = fold_convert (unsigned_type, base);
5405 3514599 : tree delta, step_abs;
5406 :
5407 3514599 : if (tree_int_cst_sign_bit (step))
5408 : {
5409 506683 : tree extreme = fold_convert (unsigned_type,
5410 : lower_bound_in_type (type, type));
5411 506683 : delta = fold_build2 (MINUS_EXPR, unsigned_type, unsigned_base, extreme);
5412 506683 : step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
5413 : fold_convert (unsigned_type, step));
5414 : }
5415 : else
5416 : {
5417 3007916 : tree extreme = fold_convert (unsigned_type,
5418 : upper_bound_in_type (type, type));
5419 3007916 : delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, unsigned_base);
5420 3007916 : step_abs = fold_convert (unsigned_type, step);
5421 : }
5422 :
5423 3514599 : return fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
5424 : }
5425 :
5426 : /* Return true if we can prove LOOP is exited before evolution of induction
5427 : variable {BASE, STEP} overflows with respect to its type bound. */
5428 :
5429 : static bool
5430 3477928 : loop_exits_before_overflow (tree base, tree step,
5431 : gimple *at_stmt, class loop *loop)
5432 : {
5433 3477928 : widest_int niter;
5434 3477928 : struct control_iv *civ;
5435 3477928 : class nb_iter_bound *bound;
5436 3477928 : tree e;
5437 3477928 : tree type = TREE_TYPE (step);
5438 3477928 : tree valid_niter;
5439 :
5440 : /* Compute the number of iterations before we reach the bound of the
5441 : type, and verify that the loop is exited before this occurs. */
5442 3477928 : valid_niter = get_niter_type_bound (type, base, step);
5443 :
5444 3477928 : estimate_numbers_of_iterations (loop);
5445 :
5446 3477928 : if (max_loop_iterations (loop, &niter)
5447 2959754 : && wi::fits_to_tree_p (niter, TREE_TYPE (valid_niter))
5448 2752757 : && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
5449 : wide_int_to_tree (TREE_TYPE (valid_niter),
5450 : niter))) != NULL
5451 6149947 : && integer_nonzerop (e))
5452 1198063 : return true;
5453 2279865 : if (at_stmt)
5454 3694918 : for (bound = loop->bounds; bound; bound = bound->next)
5455 : {
5456 2456150 : if (n_of_executions_at_most (at_stmt, bound, valid_niter))
5457 : return true;
5458 : }
5459 :
5460 : /* Try to prove loop is exited before {base, step} overflows with the
5461 : help of analyzed loop control IV. This is done only for IVs with
5462 : constant step because otherwise we don't have the information. */
5463 2270019 : if (TREE_CODE (step) == INTEGER_CST)
5464 : {
5465 3452169 : for (civ = loop->control_ivs; civ; civ = civ->next)
5466 : {
5467 1344703 : enum tree_code code;
5468 1344703 : tree civ_type = TREE_TYPE (civ->step);
5469 :
5470 : /* Have to consider type difference because operand_equal_p ignores
5471 : that for constants. */
5472 1344703 : if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type)
5473 1344703 : || element_precision (type) != element_precision (civ_type))
5474 802330 : continue;
5475 :
5476 : /* Only consider control IV with same step. */
5477 542373 : if (!operand_equal_p (step, civ->step, 0))
5478 215662 : continue;
5479 :
5480 : /* Done proving if this is a no-overflow control IV. */
5481 326711 : if (operand_equal_p (base, civ->base, 0))
5482 : return true;
5483 :
5484 : /* Control IV is recorded after expanding simple operations,
5485 : Here we expand base and compare it too. */
5486 235265 : tree expanded_base = expand_simple_operations (base);
5487 235265 : if (operand_equal_p (expanded_base, civ->base, 0))
5488 : return true;
5489 :
5490 : /* If this is a before stepping control IV, in other words, we have
5491 :
5492 : {civ_base, step} = {base + step, step}
5493 :
5494 : Because civ {base + step, step} doesn't overflow during loop
5495 : iterations, {base, step} will not overflow if we can prove the
5496 : operation "base + step" does not overflow. Specifically, we try
5497 : to prove below conditions are satisfied:
5498 :
5499 : base <= UPPER_BOUND (type) - step ;;step > 0
5500 : base >= LOWER_BOUND (type) - step ;;step < 0
5501 :
5502 : by proving the reverse conditions are false using loop's initial
5503 : condition. */
5504 206001 : if (POINTER_TYPE_P (TREE_TYPE (base)))
5505 : code = POINTER_PLUS_EXPR;
5506 : else
5507 : code = PLUS_EXPR;
5508 :
5509 206001 : tree stepped = fold_build2 (code, TREE_TYPE (base), base, step);
5510 206001 : tree expanded_stepped = fold_build2 (code, TREE_TYPE (base),
5511 : expanded_base, step);
5512 206001 : if (operand_equal_p (stepped, civ->base, 0)
5513 206001 : || operand_equal_p (expanded_stepped, civ->base, 0))
5514 : {
5515 54811 : tree extreme;
5516 :
5517 54811 : if (tree_int_cst_sign_bit (step))
5518 : {
5519 14013 : code = LT_EXPR;
5520 14013 : extreme = lower_bound_in_type (type, type);
5521 : }
5522 : else
5523 : {
5524 40798 : code = GT_EXPR;
5525 40798 : extreme = upper_bound_in_type (type, type);
5526 : }
5527 54811 : extreme = fold_build2 (MINUS_EXPR, type, extreme, step);
5528 54811 : e = fold_build2 (code, boolean_type_node, base, extreme);
5529 54811 : e = simplify_using_initial_conditions (loop, e);
5530 54811 : if (integer_zerop (e))
5531 : return true;
5532 : }
5533 : }
5534 : }
5535 :
5536 : return false;
5537 3477928 : }
5538 :
5539 : /* VAR is scev variable whose evolution part is constant STEP, this function
5540 : proves that VAR can't overflow by using value range info. If VAR's value
5541 : range is [MIN, MAX], it can be proven by:
5542 : MAX + step doesn't overflow ; if step > 0
5543 : or
5544 : MIN + step doesn't underflow ; if step < 0.
5545 :
5546 : We can only do this if var is computed in every loop iteration, i.e, var's
5547 : definition has to dominate loop latch. Consider below example:
5548 :
5549 : {
5550 : unsigned int i;
5551 :
5552 : <bb 3>:
5553 :
5554 : <bb 4>:
5555 : # RANGE [0, 4294967294] NONZERO 65535
5556 : # i_21 = PHI <0(3), i_18(9)>
5557 : if (i_21 != 0)
5558 : goto <bb 6>;
5559 : else
5560 : goto <bb 8>;
5561 :
5562 : <bb 6>:
5563 : # RANGE [0, 65533] NONZERO 65535
5564 : _6 = i_21 + 4294967295;
5565 : # RANGE [0, 65533] NONZERO 65535
5566 : _7 = (long unsigned int) _6;
5567 : # RANGE [0, 524264] NONZERO 524280
5568 : _8 = _7 * 8;
5569 : # PT = nonlocal escaped
5570 : _9 = a_14 + _8;
5571 : *_9 = 0;
5572 :
5573 : <bb 8>:
5574 : # RANGE [1, 65535] NONZERO 65535
5575 : i_18 = i_21 + 1;
5576 : if (i_18 >= 65535)
5577 : goto <bb 10>;
5578 : else
5579 : goto <bb 9>;
5580 :
5581 : <bb 9>:
5582 : goto <bb 4>;
5583 :
5584 : <bb 10>:
5585 : return;
5586 : }
5587 :
5588 : VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
5589 : can't use _6 to prove no-overflow for _7. In fact, var _7 takes value
5590 : sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
5591 : (4294967295, 4294967296, ...). */
5592 :
5593 : static bool
5594 348790 : scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
5595 : {
5596 348790 : tree type;
5597 348790 : wide_int minv, maxv, diff, step_wi;
5598 :
5599 348790 : if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var)))
5600 : return false;
5601 :
5602 : /* Check if VAR evaluates in every loop iteration. It's not the case
5603 : if VAR is default definition or does not dominate loop's latch. */
5604 348790 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5605 348790 : if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
5606 : return false;
5607 :
5608 346336 : int_range_max r (TREE_TYPE (var));
5609 692672 : get_range_query (cfun)->range_of_expr (r, var);
5610 346336 : if (r.varying_p () || r.undefined_p ())
5611 : return false;
5612 :
5613 : /* VAR is a scev whose evolution part is STEP and value range info
5614 : is [MIN, MAX], we can prove its no-overflowness by conditions:
5615 :
5616 : type_MAX - MAX >= step ; if step > 0
5617 : MIN - type_MIN >= |step| ; if step < 0.
5618 :
5619 : Or VAR must take value outside of value range, which is not true. */
5620 138038 : step_wi = wi::to_wide (step);
5621 138038 : type = TREE_TYPE (var);
5622 138038 : if (tree_int_cst_sign_bit (step))
5623 : {
5624 7563 : diff = r.lower_bound () - wi::to_wide (lower_bound_in_type (type, type));
5625 7563 : step_wi = - step_wi;
5626 : }
5627 : else
5628 130475 : diff = wi::to_wide (upper_bound_in_type (type, type)) - r.upper_bound ();
5629 :
5630 138038 : return (wi::geu_p (diff, step_wi));
5631 695126 : }
5632 :
5633 : /* Return false only when the induction variable BASE + STEP * I is
5634 : known to not overflow: i.e. when the number of iterations is small
5635 : enough with respect to the step and initial condition in order to
5636 : keep the evolution confined in TYPEs bounds. Return true when the
5637 : iv is known to overflow or when the property is not computable.
5638 :
5639 : USE_OVERFLOW_SEMANTICS is true if this function should assume that
5640 : the rules for overflow of the given language apply (e.g., that signed
5641 : arithmetics in C does not overflow).
5642 :
5643 : If VAR is a ssa variable, this function also returns false if VAR can
5644 : be proven not overflow with value range info.
5645 :
5646 : If NOWRAP_BOUND is nonzero and we can't prove it differently, get
5647 : STEP's type bound, build a bound MIN (NOWRAP_BOUND, STEP_TYPE_BOUND)
5648 : and store it in NOWRAP_BOUND. */
5649 :
5650 : bool
5651 8157956 : scev_probably_wraps_p (tree var, tree base, tree step,
5652 : gimple *at_stmt, class loop *loop,
5653 : bool use_overflow_semantics, tree *nowrap_bound)
5654 : {
5655 : /* FIXME: We really need something like
5656 : http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
5657 :
5658 : We used to test for the following situation that frequently appears
5659 : during address arithmetics:
5660 :
5661 : D.1621_13 = (long unsigned intD.4) D.1620_12;
5662 : D.1622_14 = D.1621_13 * 8;
5663 : D.1623_15 = (doubleD.29 *) D.1622_14;
5664 :
5665 : And derived that the sequence corresponding to D_14
5666 : can be proved to not wrap because it is used for computing a
5667 : memory access; however, this is not really the case -- for example,
5668 : if D_12 = (unsigned char) [254,+,1], then D_14 has values
5669 : 2032, 2040, 0, 8, ..., but the code is still legal. */
5670 :
5671 8157956 : if (chrec_contains_undetermined (base)
5672 8157956 : || chrec_contains_undetermined (step))
5673 : return true;
5674 :
5675 8157956 : if (integer_zerop (step))
5676 : return false;
5677 :
5678 : /* If we can use the fact that signed and pointer arithmetics does not
5679 : wrap, we are done. */
5680 8157956 : if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
5681 : return false;
5682 :
5683 : /* To be able to use estimates on number of iterations of the loop,
5684 : we must have an upper bound on the absolute value of the step. */
5685 4266696 : if (TREE_CODE (step) != INTEGER_CST)
5686 : return true;
5687 :
5688 : /* Check if var can be proven not overflow with value range info. */
5689 363050 : if (var && TREE_CODE (var) == SSA_NAME
5690 3952643 : && scev_var_range_cant_overflow (var, step, loop))
5691 : return false;
5692 :
5693 3477928 : if (loop_exits_before_overflow (base, step, at_stmt, loop))
5694 : return false;
5695 :
5696 : /* Check the nonwrapping flag, which may be set by niter analysis (e.g., the
5697 : above loop exits before overflow). */
5698 2107466 : if (var && nonwrapping_chrec_p (analyze_scalar_evolution (loop, var)))
5699 : return false;
5700 :
5701 : /* If we can use a bound to guarantee no wrapping, save it. */
5702 2104072 : if (nowrap_bound)
5703 : {
5704 6197 : tree b = get_niter_type_bound (TREE_TYPE (step), base, step);
5705 6197 : scev_combine_nowrap_bounds (nowrap_bound, b);
5706 6197 : return false;
5707 : }
5708 :
5709 : /* At this point we still don't have a proof that the iv does not
5710 : overflow: give up. */
5711 : return true;
5712 : }
5713 :
5714 : /* Frees the information on upper bounds on numbers of iterations of LOOP. */
5715 :
5716 : void
5717 62492175 : free_numbers_of_iterations_estimates (class loop *loop)
5718 : {
5719 62492175 : struct control_iv *civ;
5720 62492175 : class nb_iter_bound *bound;
5721 :
5722 62492175 : loop->nb_iterations = NULL;
5723 62492175 : loop->estimate_state = EST_NOT_COMPUTED;
5724 72904438 : for (bound = loop->bounds; bound;)
5725 : {
5726 10412263 : class nb_iter_bound *next = bound->next;
5727 10412263 : ggc_free (bound);
5728 10412263 : bound = next;
5729 : }
5730 62492175 : loop->bounds = NULL;
5731 :
5732 67073057 : for (civ = loop->control_ivs; civ;)
5733 : {
5734 4580882 : struct control_iv *next = civ->next;
5735 4580882 : ggc_free (civ);
5736 4580882 : civ = next;
5737 : }
5738 62492175 : loop->control_ivs = NULL;
5739 62492175 : }
5740 :
5741 : /* Frees the information on upper bounds on numbers of iterations of loops. */
5742 :
5743 : void
5744 80396450 : free_numbers_of_iterations_estimates (function *fn)
5745 : {
5746 303055469 : for (auto loop : loops_list (fn, 0))
5747 61866119 : free_numbers_of_iterations_estimates (loop);
5748 80396450 : }
5749 :
5750 : /* Substitute value VAL for ssa name NAME inside expressions held
5751 : at LOOP. */
5752 :
5753 : void
5754 127917064 : substitute_in_loop_info (class loop *loop, tree name, tree val)
5755 : {
5756 127917064 : loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
5757 127917064 : }
|