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