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