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