Branch data Line data Source code
1 : : /* Functions to determine/estimate number of iterations of a loop.
2 : : Copyright (C) 2004-2025 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 : 52220494 : split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
73 : : {
74 : 52220494 : tree type = TREE_TYPE (expr);
75 : 52220494 : tree op0, op1;
76 : 52220494 : bool negate = false;
77 : :
78 : 52220494 : *var = expr;
79 : 52220494 : mpz_set_ui (offset, 0);
80 : :
81 : 52220494 : switch (TREE_CODE (expr))
82 : : {
83 : 7834 : case MINUS_EXPR:
84 : 7834 : negate = true;
85 : : /* Fallthru. */
86 : :
87 : 5260305 : case PLUS_EXPR:
88 : 5260305 : case POINTER_PLUS_EXPR:
89 : 5260305 : op0 = TREE_OPERAND (expr, 0);
90 : 5260305 : op1 = TREE_OPERAND (expr, 1);
91 : :
92 : 5260305 : if (TREE_CODE (op1) != INTEGER_CST)
93 : : break;
94 : :
95 : 5249196 : *var = op0;
96 : : /* Always sign extend the offset. */
97 : 5249196 : wi::to_mpz (wi::to_wide (op1), offset, SIGNED);
98 : 5249196 : if (negate)
99 : 33 : mpz_neg (offset, offset);
100 : : break;
101 : :
102 : 23690312 : case INTEGER_CST:
103 : 23690312 : *var = build_int_cst_type (type, 0);
104 : 23690312 : wi::to_mpz (wi::to_wide (expr), offset, TYPE_SIGN (type));
105 : 23690312 : break;
106 : :
107 : : default:
108 : : break;
109 : : }
110 : 52220494 : }
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 : 15949181 : 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 : 15949181 : tree varc0, varc1, ctype;
121 : 15949181 : mpz_t offc0, offc1;
122 : 15949181 : mpz_t mint, maxt, minc1, maxc1;
123 : 15949181 : bool no_wrap = nowrap_type_p (type);
124 : 15949181 : bool c0_ok, c1_ok;
125 : 15949181 : signop sgn = TYPE_SIGN (type);
126 : :
127 : 15949181 : switch (cmp)
128 : : {
129 : 7466215 : case LT_EXPR:
130 : 7466215 : case LE_EXPR:
131 : 7466215 : case GT_EXPR:
132 : 7466215 : case GE_EXPR:
133 : 7466215 : STRIP_SIGN_NOPS (c0);
134 : 7466215 : STRIP_SIGN_NOPS (c1);
135 : 7466215 : ctype = TREE_TYPE (c0);
136 : 7466215 : if (!useless_type_conversion_p (ctype, type))
137 : 13872360 : 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 : 3943410 : case NE_EXPR:
148 : : /* NE_EXPR comparisons do not contain much of useful information,
149 : : except for cases of comparing with bounds. */
150 : 3943410 : if (TREE_CODE (c1) != INTEGER_CST
151 : 3681766 : || !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 : 3681766 : ctype = TREE_TYPE (c0);
157 : 3681766 : if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
158 : : return;
159 : 2138437 : c0 = fold_convert (type, c0);
160 : 2138437 : c1 = fold_convert (type, c1);
161 : :
162 : 2138437 : if (operand_equal_p (var, c0, 0))
163 : : {
164 : : /* Case of comparing VAR with its below/up bounds. */
165 : 276714 : auto_mpz valc1;
166 : 276714 : wi::to_mpz (wi::to_wide (c1), valc1, TYPE_SIGN (type));
167 : 276714 : if (mpz_cmp (valc1, below) == 0)
168 : 125401 : cmp = GT_EXPR;
169 : 276714 : if (mpz_cmp (valc1, up) == 0)
170 : 45215 : cmp = LT_EXPR;
171 : 276714 : }
172 : : else
173 : : {
174 : : /* Case of comparing with the bounds of the type. */
175 : 1861723 : wide_int min = wi::min_value (type);
176 : 1861723 : wide_int max = wi::max_value (type);
177 : :
178 : 1861723 : if (wi::to_wide (c1) == min)
179 : 513840 : cmp = GT_EXPR;
180 : 1861723 : if (wi::to_wide (c1) == max)
181 : 17519 : cmp = LT_EXPR;
182 : 1861723 : }
183 : :
184 : : /* Quick return if no useful information. */
185 : 2138437 : if (cmp == NE_EXPR)
186 : : return;
187 : :
188 : : break;
189 : :
190 : : default:
191 : : return;
192 : : }
193 : :
194 : 7033117 : mpz_init (offc0);
195 : 7033117 : mpz_init (offc1);
196 : 7033117 : split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
197 : 7033117 : 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 : 7033117 : if (operand_equal_p (var, varc1, 0))
201 : : {
202 : 566110 : std::swap (varc0, varc1);
203 : 566110 : mpz_swap (offc0, offc1);
204 : 566110 : cmp = swap_tree_comparison (cmp);
205 : : }
206 : 6467007 : else if (!operand_equal_p (var, varc0, 0))
207 : : {
208 : 4956296 : mpz_clear (offc0);
209 : 4956296 : mpz_clear (offc1);
210 : 4956296 : return;
211 : : }
212 : :
213 : 2076821 : mpz_init (mint);
214 : 2076821 : mpz_init (maxt);
215 : 2076821 : get_type_static_bounds (type, mint, maxt);
216 : 2076821 : mpz_init (minc1);
217 : 2076821 : mpz_init (maxc1);
218 : 4153642 : int_range_max r (TREE_TYPE (varc1));
219 : : /* Setup range information for varc1. */
220 : 2076821 : if (integer_zerop (varc1))
221 : : {
222 : 1075400 : wi::to_mpz (0, minc1, TYPE_SIGN (type));
223 : 1075400 : wi::to_mpz (0, maxc1, TYPE_SIGN (type));
224 : : }
225 : 1001421 : else if (TREE_CODE (varc1) == SSA_NAME
226 : 944476 : && INTEGRAL_TYPE_P (type)
227 : 1888952 : && get_range_query (cfun)->range_of_expr (r, varc1)
228 : 944476 : && !r.undefined_p ()
229 : 1943879 : && !r.varying_p ())
230 : : {
231 : 778744 : gcc_assert (wi::le_p (r.lower_bound (), r.upper_bound (), sgn));
232 : 389372 : wi::to_mpz (r.lower_bound (), minc1, sgn);
233 : 389372 : wi::to_mpz (r.upper_bound (), maxc1, sgn);
234 : : }
235 : : else
236 : : {
237 : 612049 : mpz_set (minc1, mint);
238 : 612049 : 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 : 2076821 : mpz_add (minc1, minc1, offc1);
248 : 2076821 : mpz_add (maxc1, maxc1, offc1);
249 : 4153642 : c1_ok = (no_wrap
250 : 780667 : || mpz_sgn (offc1) == 0
251 : 131168 : || (mpz_sgn (offc1) < 0 && mpz_cmp (minc1, mint) >= 0)
252 : 2206530 : || (mpz_sgn (offc1) > 0 && mpz_cmp (maxc1, maxt) <= 0));
253 : 19459 : if (!c1_ok)
254 : 19459 : goto end;
255 : :
256 : 2057362 : if (mpz_cmp (minc1, mint) < 0)
257 : 6487 : mpz_set (minc1, mint);
258 : 2057362 : if (mpz_cmp (maxc1, maxt) > 0)
259 : 12888 : mpz_set (maxc1, maxt);
260 : :
261 : 2057362 : if (cmp == LT_EXPR)
262 : : {
263 : 322098 : cmp = LE_EXPR;
264 : 322098 : mpz_sub_ui (maxc1, maxc1, 1);
265 : : }
266 : 2057362 : if (cmp == GT_EXPR)
267 : : {
268 : 1106273 : cmp = GE_EXPR;
269 : 1106273 : 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 : 2057362 : mpz_sub (minc1, minc1, offc0);
311 : 2057362 : mpz_sub (maxc1, maxc1, offc0);
312 : 4114724 : c0_ok = (no_wrap
313 : 761208 : || mpz_sgn (offc0) == 0
314 : 38375 : || (cmp == LE_EXPR
315 : 23030 : && mpz_sgn (offc0) < 0 && mpz_cmp (maxc1, maxt) <= 0)
316 : 2094571 : || (cmp == GE_EXPR
317 : 15345 : && mpz_sgn (offc0) > 0 && mpz_cmp (minc1, mint) >= 0));
318 : 35369 : if (!c0_ok)
319 : 35369 : goto end;
320 : :
321 : 2021993 : if (cmp == LE_EXPR)
322 : : {
323 : 686139 : if (mpz_cmp (up, maxc1) > 0)
324 : 248826 : mpz_set (up, maxc1);
325 : : }
326 : : else
327 : : {
328 : 1335854 : if (mpz_cmp (below, minc1) < 0)
329 : 1086581 : mpz_set (below, minc1);
330 : : }
331 : :
332 : 249273 : end:
333 : 2076821 : mpz_clear (mint);
334 : 2076821 : mpz_clear (maxt);
335 : 2076821 : mpz_clear (minc1);
336 : 2076821 : mpz_clear (maxc1);
337 : 2076821 : mpz_clear (offc0);
338 : 2076821 : 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 : 24312478 : determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
346 : : mpz_t min, mpz_t max)
347 : : {
348 : 24312478 : int cnt = 0;
349 : 24312478 : mpz_t minm, maxm;
350 : 24312478 : basic_block bb;
351 : 24312478 : wide_int minv, maxv;
352 : 24312478 : enum value_range_kind rtype = VR_VARYING;
353 : :
354 : : /* If the expression is a constant, we know its value exactly. */
355 : 24312478 : if (integer_zerop (var))
356 : : {
357 : 17036945 : mpz_set (min, off);
358 : 17036945 : mpz_set (max, off);
359 : 17036945 : return;
360 : : }
361 : :
362 : 7275533 : get_type_static_bounds (type, min, max);
363 : :
364 : : /* See if we have some range info from VRP. */
365 : 7275533 : if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type))
366 : : {
367 : 4536379 : edge e = loop_preheader_edge (loop);
368 : 4536379 : signop sgn = TYPE_SIGN (type);
369 : 4536379 : gphi_iterator gsi;
370 : :
371 : : /* Either for VAR itself... */
372 : 4536379 : int_range_max var_range (TREE_TYPE (var));
373 : 9072758 : get_range_query (cfun)->range_of_expr (var_range, var);
374 : 4536379 : if (var_range.varying_p () || var_range.undefined_p ())
375 : : rtype = VR_VARYING;
376 : : else
377 : : rtype = VR_RANGE;
378 : 4536379 : if (!var_range.undefined_p ())
379 : : {
380 : 4521937 : minv = var_range.lower_bound ();
381 : 4521937 : 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 : 4536379 : int_range_max phi_range (TREE_TYPE (var));
387 : 17035421 : for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
388 : : {
389 : 12499044 : gphi *phi = gsi.phi ();
390 : 12499044 : if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
391 : 2595584 : && get_range_query (cfun)->range_of_expr (phi_range,
392 : : gimple_phi_result (phi))
393 : 1297792 : && !phi_range.varying_p ()
394 : 13238522 : && !phi_range.undefined_p ())
395 : : {
396 : 739478 : if (rtype != VR_RANGE)
397 : : {
398 : 293496 : rtype = VR_RANGE;
399 : 293496 : minv = phi_range.lower_bound ();
400 : 293496 : maxv = phi_range.upper_bound ();
401 : : }
402 : : else
403 : : {
404 : 445982 : minv = wi::max (minv, phi_range.lower_bound (), sgn);
405 : 445982 : 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 : 445982 : if (wi::gt_p (minv, maxv, sgn))
411 : : {
412 : 2 : int_range_max vr (TREE_TYPE (var));
413 : 4 : get_range_query (cfun)->range_of_expr (vr, var);
414 : 2 : if (vr.varying_p () || vr.undefined_p ())
415 : : rtype = VR_VARYING;
416 : : else
417 : : rtype = VR_RANGE;
418 : 2 : if (!vr.undefined_p ())
419 : : {
420 : 2 : minv = vr.lower_bound ();
421 : 2 : maxv = vr.upper_bound ();
422 : : }
423 : 2 : break;
424 : 2 : }
425 : : }
426 : : }
427 : : }
428 : 4536379 : mpz_init (minm);
429 : 4536379 : mpz_init (maxm);
430 : 4536379 : if (rtype != VR_RANGE)
431 : : {
432 : 2935766 : mpz_set (minm, min);
433 : 2935766 : mpz_set (maxm, max);
434 : : }
435 : : else
436 : : {
437 : 1600613 : gcc_assert (wi::le_p (minv, maxv, sgn));
438 : 1600613 : wi::to_mpz (minv, minm, sgn);
439 : 1600613 : 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 : 4536379 : for (bb = loop->header;
444 : 47149336 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
445 : 42612957 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
446 : : {
447 : 42612957 : edge e;
448 : 42612957 : tree c0, c1;
449 : 42612957 : enum tree_code cmp;
450 : :
451 : 42612957 : if (!single_pred_p (bb))
452 : 21447894 : continue;
453 : 21165063 : e = single_pred_edge (bb);
454 : :
455 : 21165063 : if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
456 : 5215882 : continue;
457 : :
458 : 31898362 : gcond *cond = as_a <gcond *> (*gsi_last_bb (e->src));
459 : 15949181 : c0 = gimple_cond_lhs (cond);
460 : 15949181 : cmp = gimple_cond_code (cond);
461 : 15949181 : c1 = gimple_cond_rhs (cond);
462 : :
463 : 15949181 : if (e->flags & EDGE_FALSE_VALUE)
464 : 8244432 : cmp = invert_tree_comparison (cmp, false);
465 : :
466 : 15949181 : refine_value_range_using_guard (type, var, c0, cmp, c1, minm, maxm);
467 : 15949181 : ++cnt;
468 : : }
469 : :
470 : 4536379 : mpz_add (minm, minm, off);
471 : 4536379 : 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 : 4536379 : if (nowrap_type_p (type)
478 : 1964761 : || mpz_sgn (off) == 0
479 : 457706 : || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0)
480 : 4912085 : || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0))
481 : : {
482 : 4395458 : mpz_set (min, minm);
483 : 4395458 : mpz_set (max, maxm);
484 : 4395458 : mpz_clear (minm);
485 : 4395458 : mpz_clear (maxm);
486 : 4395458 : return;
487 : : }
488 : 140921 : mpz_clear (minm);
489 : 140921 : mpz_clear (maxm);
490 : 4536379 : }
491 : :
492 : : /* If the computation may wrap, we know nothing about the value, except for
493 : : the range of the type. */
494 : 2880075 : 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 : 2406905 : if (mpz_sgn (off) < 0)
500 : 164783 : mpz_add (max, max, off);
501 : : else
502 : 2242122 : mpz_add (min, min, off);
503 : 24312478 : }
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 : 156933 : bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
510 : : bounds *bnds)
511 : : {
512 : 156933 : int rel = mpz_cmp (x, y);
513 : 156933 : 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 : 156933 : if (rel == 0)
530 : : {
531 : 862 : mpz_set_ui (bnds->below, 0);
532 : 862 : mpz_set_ui (bnds->up, 0);
533 : 862 : return;
534 : : }
535 : :
536 : 156071 : auto_mpz m;
537 : 156071 : wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), m, UNSIGNED);
538 : 156071 : mpz_add_ui (m, m, 1);
539 : 156071 : mpz_sub (bnds->up, x, y);
540 : 156071 : mpz_set (bnds->below, bnds->up);
541 : :
542 : 156071 : if (may_wrap)
543 : : {
544 : 138855 : if (rel > 0)
545 : 137692 : mpz_sub (bnds->below, bnds->below, m);
546 : : else
547 : 1163 : mpz_add (bnds->up, bnds->up, m);
548 : : }
549 : 156071 : }
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 : 18933571 : 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 : 18933571 : tree varc0, varc1, ctype;
562 : 18933571 : mpz_t offc0, offc1, loffx, loffy, bnd;
563 : 18933571 : bool lbound = false;
564 : 18933571 : bool no_wrap = nowrap_type_p (type);
565 : 18933571 : bool x_ok, y_ok;
566 : :
567 : 18933571 : switch (cmp)
568 : : {
569 : 7989281 : case LT_EXPR:
570 : 7989281 : case LE_EXPR:
571 : 7989281 : case GT_EXPR:
572 : 7989281 : case GE_EXPR:
573 : 7989281 : STRIP_SIGN_NOPS (c0);
574 : 7989281 : STRIP_SIGN_NOPS (c1);
575 : 7989281 : ctype = TREE_TYPE (c0);
576 : 7989281 : if (!useless_type_conversion_p (ctype, type))
577 : 12169613 : 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 : 5316463 : 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 : 5316463 : if (TREE_CODE (c1) != INTEGER_CST
591 : 4578176 : || !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 : 4101962 : ctype = TREE_TYPE (c0);
597 : 4101962 : if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
598 : : return;
599 : 2311406 : c0 = fold_convert (type, c0);
600 : 2311406 : c1 = fold_convert (type, c1);
601 : :
602 : 2311406 : if (TYPE_MIN_VALUE (type)
603 : 2311406 : && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
604 : : {
605 : : cmp = GT_EXPR;
606 : : break;
607 : : }
608 : 1659659 : if (TYPE_MAX_VALUE (type)
609 : 1659659 : && 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 : 6763958 : mpz_init (offc0);
621 : 6763958 : mpz_init (offc1);
622 : 6763958 : split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
623 : 6763958 : 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 : 6763958 : if (operand_equal_p (varx, varc1, 0))
630 : : {
631 : 931852 : std::swap (varc0, varc1);
632 : 931852 : mpz_swap (offc0, offc1);
633 : 931852 : cmp = swap_tree_comparison (cmp);
634 : : }
635 : :
636 : 6763958 : if (!operand_equal_p (varx, varc0, 0)
637 : 6763958 : || !operand_equal_p (vary, varc1, 0))
638 : 5032715 : goto end;
639 : :
640 : 1731243 : mpz_init_set (loffx, offx);
641 : 1731243 : mpz_init_set (loffy, offy);
642 : :
643 : 1731243 : if (cmp == GT_EXPR || cmp == GE_EXPR)
644 : : {
645 : 1653844 : std::swap (varx, vary);
646 : 1653844 : mpz_swap (offc0, offc1);
647 : 1653844 : mpz_swap (loffx, loffy);
648 : 1653844 : cmp = swap_tree_comparison (cmp);
649 : 1653844 : 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 : 1731243 : if (no_wrap)
669 : : {
670 : : x_ok = true;
671 : : y_ok = true;
672 : : }
673 : : else
674 : : {
675 : 610998 : x_ok = (integer_zerop (varx)
676 : 610998 : || mpz_cmp (loffx, offc0) >= 0);
677 : 610998 : y_ok = (integer_zerop (vary)
678 : 610998 : || mpz_cmp (loffy, offc1) <= 0);
679 : : }
680 : :
681 : 608244 : if (x_ok && y_ok)
682 : : {
683 : 1725115 : mpz_init (bnd);
684 : 1725115 : mpz_sub (bnd, loffx, loffy);
685 : 1725115 : mpz_add (bnd, bnd, offc1);
686 : 1725115 : mpz_sub (bnd, bnd, offc0);
687 : :
688 : 1725115 : if (cmp == LT_EXPR)
689 : 1411284 : mpz_sub_ui (bnd, bnd, 1);
690 : :
691 : 1725115 : if (lbound)
692 : : {
693 : 1648771 : mpz_neg (bnd, bnd);
694 : 1648771 : if (mpz_cmp (bnds->below, bnd) < 0)
695 : 742825 : mpz_set (bnds->below, bnd);
696 : : }
697 : : else
698 : : {
699 : 76344 : if (mpz_cmp (bnd, bnds->up) < 0)
700 : 15040 : mpz_set (bnds->up, bnd);
701 : : }
702 : 1725115 : mpz_clear (bnd);
703 : : }
704 : :
705 : 1731243 : mpz_clear (loffx);
706 : 1731243 : mpz_clear (loffy);
707 : 6763958 : end:
708 : 6763958 : mpz_clear (offc0);
709 : 6763958 : 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 : 12313172 : bound_difference (class loop *loop, tree x, tree y, bounds *bnds)
723 : : {
724 : 12313172 : tree type = TREE_TYPE (x);
725 : 12313172 : tree varx, vary;
726 : 12313172 : mpz_t offx, offy;
727 : 12313172 : int cnt = 0;
728 : 12313172 : edge e;
729 : 12313172 : basic_block bb;
730 : 12313172 : tree c0, c1;
731 : 12313172 : enum tree_code cmp;
732 : :
733 : : /* Get rid of unnecessary casts, but preserve the value of
734 : : the expressions. */
735 : 12313172 : STRIP_SIGN_NOPS (x);
736 : 12313172 : STRIP_SIGN_NOPS (y);
737 : :
738 : 12313172 : mpz_init (bnds->below);
739 : 12313172 : mpz_init (bnds->up);
740 : 12313172 : mpz_init (offx);
741 : 12313172 : mpz_init (offy);
742 : 12313172 : split_to_var_and_offset (x, &varx, offx);
743 : 12313172 : split_to_var_and_offset (y, &vary, offy);
744 : :
745 : 12313172 : if (!integer_zerop (varx)
746 : 12313172 : && 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 : 156933 : 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 : 12156239 : auto_mpz minx, maxx, miny, maxy;
758 : 12156239 : determine_value_range (loop, type, varx, offx, minx, maxx);
759 : 12156239 : determine_value_range (loop, type, vary, offy, miny, maxy);
760 : :
761 : 12156239 : mpz_sub (bnds->below, minx, maxy);
762 : 12156239 : mpz_sub (bnds->up, maxx, miny);
763 : 12156239 : }
764 : :
765 : : /* If both X and Y are constants, we cannot get any more precise. */
766 : 12313172 : if (integer_zerop (varx) && integer_zerop (vary))
767 : 6738087 : goto end;
768 : :
769 : : /* Now walk the dominators of the loop header and use the entry
770 : : guards to refine the estimates. */
771 : 5575085 : for (bb = loop->header;
772 : 55502128 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
773 : 49927043 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
774 : : {
775 : 49927043 : if (!single_pred_p (bb))
776 : 24034792 : continue;
777 : 25892251 : e = single_pred_edge (bb);
778 : :
779 : 25892251 : if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
780 : 6958680 : continue;
781 : :
782 : 37867142 : gcond *cond = as_a <gcond *> (*gsi_last_bb (e->src));
783 : 18933571 : c0 = gimple_cond_lhs (cond);
784 : 18933571 : cmp = gimple_cond_code (cond);
785 : 18933571 : c1 = gimple_cond_rhs (cond);
786 : :
787 : 18933571 : if (e->flags & EDGE_FALSE_VALUE)
788 : 10394123 : cmp = invert_tree_comparison (cmp, false);
789 : :
790 : 18933571 : refine_bounds_using_guard (type, varx, offx, vary, offy,
791 : : c0, cmp, c1, bnds);
792 : 18933571 : ++cnt;
793 : : }
794 : :
795 : 5575085 : end:
796 : 12313172 : mpz_clear (offx);
797 : 12313172 : mpz_clear (offy);
798 : 12313172 : }
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 : 1938561 : bounds_add (bounds *bnds, const widest_int &delta, tree type)
806 : : {
807 : 1938561 : mpz_t mdelta, max;
808 : :
809 : 1938561 : mpz_init (mdelta);
810 : 1938561 : wi::to_mpz (delta, mdelta, SIGNED);
811 : :
812 : 1938561 : mpz_init (max);
813 : 1938561 : wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
814 : :
815 : 1938561 : mpz_add (bnds->up, bnds->up, mdelta);
816 : 1938561 : mpz_add (bnds->below, bnds->below, mdelta);
817 : :
818 : 1938561 : if (mpz_cmp (bnds->up, max) > 0)
819 : 112722 : mpz_set (bnds->up, max);
820 : :
821 : 1938561 : mpz_neg (max, max);
822 : 1938561 : if (mpz_cmp (bnds->below, max) < 0)
823 : 7111 : mpz_set (bnds->below, max);
824 : :
825 : 1938561 : mpz_clear (mdelta);
826 : 1938561 : mpz_clear (max);
827 : 1938561 : }
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 : 2511121 : bounds_negate (bounds *bnds)
834 : : {
835 : 2511121 : mpz_t tmp;
836 : :
837 : 2511121 : mpz_init_set (tmp, bnds->up);
838 : 2511121 : mpz_neg (bnds->up, bnds->below);
839 : 2511121 : mpz_neg (bnds->below, tmp);
840 : 2511121 : mpz_clear (tmp);
841 : 2511121 : }
842 : :
843 : : /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
844 : :
845 : : static tree
846 : 149471 : inverse (tree x, tree mask)
847 : : {
848 : 149471 : tree type = TREE_TYPE (x);
849 : 149471 : tree rslt;
850 : 149471 : unsigned ctr = tree_floor_log2 (mask);
851 : :
852 : 149471 : if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
853 : : {
854 : 149411 : unsigned HOST_WIDE_INT ix;
855 : 149411 : unsigned HOST_WIDE_INT imask;
856 : 149411 : unsigned HOST_WIDE_INT irslt = 1;
857 : :
858 : 149411 : gcc_assert (cst_and_fits_in_hwi (x));
859 : 149411 : gcc_assert (cst_and_fits_in_hwi (mask));
860 : :
861 : 149411 : ix = int_cst_value (x);
862 : 149411 : imask = int_cst_value (mask);
863 : :
864 : 8412607 : for (; ctr; ctr--)
865 : : {
866 : 8113785 : irslt *= ix;
867 : 8113785 : ix *= ix;
868 : : }
869 : 149411 : irslt &= imask;
870 : :
871 : 149411 : 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 : 149471 : 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 : 7180483 : 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 : 7180483 : widest_int max;
908 : 7180483 : mpz_t d;
909 : 7180483 : tree type = TREE_TYPE (c);
910 : 14360966 : bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
911 : 7180483 : || mpz_sgn (bnds->below) >= 0);
912 : :
913 : 7180483 : if (integer_onep (s)
914 : 832441 : || (TREE_CODE (c) == INTEGER_CST
915 : 315697 : && TREE_CODE (s) == INTEGER_CST
916 : 1149153 : && wi::mod_trunc (wi::to_wide (c), wi::to_wide (s),
917 : 7811877 : TYPE_SIGN (type)) == 0)
918 : 7698242 : || (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 : 517759 : if (!no_overflow)
935 : : {
936 : 132988 : max = wi::mask <widest_int> (TYPE_PRECISION (type)
937 : 132988 : - wi::ctz (wi::to_wide (s)), false);
938 : 66494 : wi::to_mpz (max, bnd, UNSIGNED);
939 : 66494 : 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 : 7113989 : 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 : 7113989 : 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 : 6828873 : if (TREE_CODE (c) == INTEGER_CST)
953 : 5953160 : wi::to_mpz (wi::to_wide (c), bnd, UNSIGNED);
954 : 875713 : else if (bnds_u_valid)
955 : 696249 : mpz_set (bnd, bnds->up);
956 : : }
957 : :
958 : 7113989 : mpz_init (d);
959 : 7113989 : wi::to_mpz (wi::to_wide (s), d, UNSIGNED);
960 : 7113989 : mpz_fdiv_q (bnd, bnd, d);
961 : 7113989 : mpz_clear (d);
962 : 7180483 : }
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 : 7180483 : 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 : 7180483 : tree niter_type = unsigned_type_for (type);
978 : 7180483 : tree s, c, d, bits, assumption, tmp, bound;
979 : :
980 : 7180483 : niter->control = *iv;
981 : 7180483 : niter->bound = final;
982 : 7180483 : 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 : 7180483 : if (tree_int_cst_sign_bit (iv->step))
990 : : {
991 : 2511121 : s = fold_convert (niter_type,
992 : : fold_build1 (NEGATE_EXPR, type, iv->step));
993 : 2511121 : c = fold_build2 (MINUS_EXPR, niter_type,
994 : : fold_convert (niter_type, iv->base),
995 : : fold_convert (niter_type, final));
996 : 2511121 : bounds_negate (bnds);
997 : : }
998 : : else
999 : : {
1000 : 4669362 : s = fold_convert (niter_type, iv->step);
1001 : 4669362 : c = fold_build2 (MINUS_EXPR, niter_type,
1002 : : fold_convert (niter_type, final),
1003 : : fold_convert (niter_type, iv->base));
1004 : : }
1005 : :
1006 : 7180483 : auto_mpz max;
1007 : 7180483 : number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
1008 : : exit_must_be_taken);
1009 : 14360966 : niter->max = widest_int::from (wi::from_mpz (niter_type, max, false),
1010 : 14360966 : 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 : 7180483 : tree mtype = type;
1043 : 7180483 : if (POINTER_TYPE_P (type))
1044 : 611721 : mtype = niter_type;
1045 : 7180483 : if (!niter->control.no_overflow
1046 : 7180483 : && (integer_onep (s)
1047 : 198894 : || (multiple_of_p (mtype, fold_convert (mtype, iv->base),
1048 : 198894 : fold_convert (mtype, s), false)
1049 : 28381 : && multiple_of_p (mtype, fold_convert (mtype, final),
1050 : 28381 : fold_convert (mtype, s), false))))
1051 : : {
1052 : 2350241 : tree t, cond, relaxed_cond = boolean_false_node;
1053 : :
1054 : 2350241 : if (tree_int_cst_sign_bit (iv->step))
1055 : : {
1056 : 2271923 : cond = fold_build2 (GE_EXPR, boolean_type_node, iv->base, final);
1057 : 2271923 : if (TREE_CODE (type) == INTEGER_TYPE)
1058 : : {
1059 : : /* Only when base - step doesn't overflow. */
1060 : 2271923 : t = TYPE_MAX_VALUE (type);
1061 : 2271923 : t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1062 : 2271923 : t = fold_build2 (GE_EXPR, boolean_type_node, t, iv->base);
1063 : 2271923 : if (integer_nonzerop (t))
1064 : : {
1065 : 2089589 : t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1066 : 2089589 : relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node, t,
1067 : : final);
1068 : : }
1069 : : }
1070 : : }
1071 : : else
1072 : : {
1073 : 78318 : cond = fold_build2 (LE_EXPR, boolean_type_node, iv->base, final);
1074 : 78318 : if (TREE_CODE (type) == INTEGER_TYPE)
1075 : : {
1076 : : /* Only when base - step doesn't underflow. */
1077 : 78318 : t = TYPE_MIN_VALUE (type);
1078 : 78318 : t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1079 : 78318 : t = fold_build2 (LE_EXPR, boolean_type_node, t, iv->base);
1080 : 78318 : if (integer_nonzerop (t))
1081 : : {
1082 : 43869 : t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1083 : 43869 : relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node, t,
1084 : : final);
1085 : : }
1086 : : }
1087 : : }
1088 : :
1089 : 2350241 : t = simplify_using_initial_conditions (loop, cond);
1090 : 2350241 : if (!t || !integer_onep (t))
1091 : 60670 : t = simplify_using_initial_conditions (loop, relaxed_cond);
1092 : :
1093 : 2350241 : if (t && integer_onep (t))
1094 : : {
1095 : 2289817 : niter->control.no_overflow = true;
1096 : 2289817 : niter->niter = fold_build2 (EXACT_DIV_EXPR, niter_type, c, s);
1097 : 2289817 : 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 : 4890666 : bits = num_ending_zeros (s);
1105 : 14671998 : bound = build_low_bits_mask (niter_type,
1106 : 4890666 : (TYPE_PRECISION (niter_type)
1107 : 4890666 : - tree_to_uhwi (bits)));
1108 : :
1109 : 4890666 : d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
1110 : : build_int_cst (niter_type, 1), bits);
1111 : 4890666 : s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
1112 : :
1113 : 4890666 : 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 : 1835281 : assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
1118 : 1835281 : assumption = fold_build2 (EQ_EXPR, boolean_type_node,
1119 : : assumption, build_int_cst (niter_type, 0));
1120 : 1835281 : if (!integer_nonzerop (assumption))
1121 : 337961 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1122 : : niter->assumptions, assumption);
1123 : : }
1124 : :
1125 : 4890666 : c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
1126 : 4890666 : if (integer_onep (s))
1127 : : {
1128 : 4741195 : niter->niter = c;
1129 : : }
1130 : : else
1131 : : {
1132 : 149471 : tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
1133 : 149471 : niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
1134 : : }
1135 : : return true;
1136 : 7180483 : }
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 : 385601 : 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 : 385601 : tree niter_type = TREE_TYPE (step);
1155 : 385601 : tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
1156 : 385601 : tree tmod;
1157 : 385601 : tree assumption = boolean_true_node, bound, noloop;
1158 : 385601 : bool fv_comp_no_overflow;
1159 : 385601 : tree type1 = type;
1160 : 385601 : if (POINTER_TYPE_P (type))
1161 : 129856 : type1 = sizetype;
1162 : :
1163 : 385601 : if (TREE_CODE (mod) != INTEGER_CST)
1164 : : return false;
1165 : 34736 : if (integer_nonzerop (mod))
1166 : 15253 : mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
1167 : 34736 : tmod = fold_convert (type1, mod);
1168 : :
1169 : 34736 : auto_mpz mmod;
1170 : 34736 : wi::to_mpz (wi::to_wide (mod), mmod, UNSIGNED);
1171 : 34736 : 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 : 34736 : if (integer_zerop (mod) || POINTER_TYPE_P (type))
1181 : : fv_comp_no_overflow = true;
1182 : 14503 : else if (!exit_must_be_taken)
1183 : : fv_comp_no_overflow = false;
1184 : : else
1185 : 7499 : fv_comp_no_overflow =
1186 : 7499 : (iv0->no_overflow && integer_nonzerop (iv0->step))
1187 : 8397 : || (iv1->no_overflow && integer_nonzerop (iv1->step));
1188 : :
1189 : 34736 : 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 : 30334 : if (!fv_comp_no_overflow)
1195 : : {
1196 : 5444 : bound = fold_build2 (MINUS_EXPR, type1,
1197 : : TYPE_MAX_VALUE (type1), tmod);
1198 : 5444 : assumption = fold_build2 (LE_EXPR, boolean_type_node,
1199 : : iv1->base, bound);
1200 : 5444 : 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 : 4402 : if (!fv_comp_no_overflow)
1210 : : {
1211 : 1560 : bound = fold_build2 (PLUS_EXPR, type1,
1212 : : TYPE_MIN_VALUE (type1), tmod);
1213 : 1560 : assumption = fold_build2 (GE_EXPR, boolean_type_node,
1214 : : iv0->base, bound);
1215 : 1560 : if (integer_zerop (assumption))
1216 : : return false;
1217 : : }
1218 : : }
1219 : :
1220 : : /* IV0 < IV1 does not loop if IV0->base >= IV1->base. */
1221 : 34693 : if (mpz_cmp (mmod, bnds->below) < 0)
1222 : 22610 : noloop = boolean_false_node;
1223 : : else
1224 : 12083 : noloop = fold_build2 (GE_EXPR, boolean_type_node,
1225 : : iv0->base, iv1->base);
1226 : :
1227 : 34693 : if (!integer_nonzerop (assumption))
1228 : 262 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1229 : : niter->assumptions,
1230 : : assumption);
1231 : 34693 : if (!integer_zerop (noloop))
1232 : 3414 : niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1233 : : niter->may_be_zero,
1234 : : noloop);
1235 : 34693 : bounds_add (bnds, wi::to_widest (mod), type);
1236 : 34693 : *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
1237 : :
1238 : 34693 : return true;
1239 : 34736 : }
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 : 350908 : assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1248 : : class tree_niter_desc *niter, tree step)
1249 : : {
1250 : 350908 : tree bound, d, assumption, diff;
1251 : 350908 : tree niter_type = TREE_TYPE (step);
1252 : :
1253 : 350908 : if (integer_nonzerop (iv0->step))
1254 : : {
1255 : : /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1256 : 288259 : 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 : 48686 : if (TREE_CODE (iv0->base) == INTEGER_CST)
1264 : : {
1265 : 17469 : d = fold_build2 (MINUS_EXPR, niter_type,
1266 : : fold_convert (niter_type, TYPE_MAX_VALUE (type)),
1267 : : fold_convert (niter_type, iv0->base));
1268 : 17469 : diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
1269 : : }
1270 : : else
1271 : 31217 : diff = fold_build2 (MINUS_EXPR, niter_type, step,
1272 : : build_int_cst (niter_type, 1));
1273 : 48686 : bound = fold_build2 (MINUS_EXPR, type,
1274 : : TYPE_MAX_VALUE (type), fold_convert (type, diff));
1275 : 48686 : 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 : 62649 : if (iv1->no_overflow)
1282 : : return true;
1283 : :
1284 : 31742 : 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 : 31699 : diff = fold_build2 (MINUS_EXPR, niter_type, step,
1293 : : build_int_cst (niter_type, 1));
1294 : 31742 : bound = fold_build2 (PLUS_EXPR, type,
1295 : : TYPE_MIN_VALUE (type), fold_convert (type, diff));
1296 : 31742 : assumption = fold_build2 (GE_EXPR, boolean_type_node,
1297 : : iv0->base, bound);
1298 : : }
1299 : :
1300 : 80428 : if (integer_zerop (assumption))
1301 : : return false;
1302 : 80317 : if (!integer_nonzerop (assumption))
1303 : 57174 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1304 : : niter->assumptions, assumption);
1305 : :
1306 : 80317 : iv0->no_overflow = true;
1307 : 80317 : iv1->no_overflow = true;
1308 : 80317 : 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 : 350797 : assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1317 : : class tree_niter_desc *niter, bounds *bnds)
1318 : : {
1319 : 350797 : tree assumption = boolean_true_node, bound, diff;
1320 : 350797 : tree mbz, mbzl, mbzr, type1;
1321 : 350797 : bool rolls_p, no_overflow_p;
1322 : 350797 : widest_int dstep;
1323 : 350797 : 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 : 350797 : if (integer_nonzerop (iv0->step))
1348 : 288259 : dstep = wi::to_widest (iv0->step);
1349 : : else
1350 : : {
1351 : 62538 : dstep = wi::sext (wi::to_widest (iv1->step), TYPE_PRECISION (type));
1352 : 62538 : dstep = -dstep;
1353 : : }
1354 : :
1355 : 350797 : mpz_init (mstep);
1356 : 350797 : wi::to_mpz (dstep, mstep, UNSIGNED);
1357 : 350797 : mpz_neg (mstep, mstep);
1358 : 350797 : mpz_add_ui (mstep, mstep, 1);
1359 : :
1360 : 350797 : rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
1361 : :
1362 : 350797 : mpz_init (max);
1363 : 350797 : wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
1364 : 350797 : mpz_add (max, max, mstep);
1365 : 701594 : 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 : 350797 : || POINTER_TYPE_P (type));
1372 : 350797 : mpz_clear (mstep);
1373 : 350797 : mpz_clear (max);
1374 : :
1375 : 350797 : if (rolls_p && no_overflow_p)
1376 : 119796 : return;
1377 : :
1378 : 231001 : type1 = type;
1379 : 231001 : if (POINTER_TYPE_P (type))
1380 : 74720 : 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 : 231001 : if (integer_nonzerop (iv0->step))
1386 : : {
1387 : 188548 : 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 : 188548 : if (!POINTER_TYPE_P (type))
1394 : : {
1395 : 117958 : bound = fold_build2 (PLUS_EXPR, type1,
1396 : : TYPE_MIN_VALUE (type), diff);
1397 : 117958 : 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 : 188548 : mbzl = fold_build2 (MINUS_EXPR, type1,
1404 : : fold_convert (type1, iv0->base), diff);
1405 : 188548 : mbzr = fold_convert (type1, iv1->base);
1406 : : }
1407 : : else
1408 : : {
1409 : 42453 : diff = fold_build2 (PLUS_EXPR, type1,
1410 : : iv1->step, build_int_cst (type1, 1));
1411 : :
1412 : 42453 : if (!POINTER_TYPE_P (type))
1413 : : {
1414 : 38323 : bound = fold_build2 (PLUS_EXPR, type1,
1415 : : TYPE_MAX_VALUE (type), diff);
1416 : 38323 : assumption = fold_build2 (LE_EXPR, boolean_type_node,
1417 : : iv1->base, bound);
1418 : : }
1419 : :
1420 : 42453 : mbzl = fold_convert (type1, iv0->base);
1421 : 42453 : mbzr = fold_build2 (MINUS_EXPR, type1,
1422 : : fold_convert (type1, iv1->base), diff);
1423 : : }
1424 : :
1425 : 231001 : if (!integer_nonzerop (assumption))
1426 : 94232 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1427 : : niter->assumptions, assumption);
1428 : 231001 : if (!rolls_p)
1429 : : {
1430 : 214496 : mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1431 : 214496 : niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1432 : : niter->may_be_zero, mbz);
1433 : : }
1434 : 350797 : }
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 : 68031 : number_of_iterations_until_wrap (class loop *loop, tree type, affine_iv *iv0,
1442 : : affine_iv *iv1, class tree_niter_desc *niter)
1443 : : {
1444 : 68031 : tree niter_type = unsigned_type_for (type);
1445 : 68031 : tree step, num, assumptions, may_be_zero, span;
1446 : 68031 : wide_int high, low, max, min;
1447 : :
1448 : 68031 : may_be_zero = fold_build2 (LE_EXPR, boolean_type_node, iv1->base, iv0->base);
1449 : 68031 : if (integer_onep (may_be_zero))
1450 : : return false;
1451 : :
1452 : 67821 : int prec = TYPE_PRECISION (type);
1453 : 67821 : signop sgn = TYPE_SIGN (type);
1454 : 67821 : min = wi::min_value (prec, sgn);
1455 : 67821 : max = wi::max_value (prec, sgn);
1456 : :
1457 : : /* n < {base, C}. */
1458 : 67821 : if (integer_zerop (iv0->step) && !tree_int_cst_sign_bit (iv1->step))
1459 : : {
1460 : 42471 : step = iv1->step;
1461 : : /* MIN + C - 1 <= n. */
1462 : 42471 : tree last = wide_int_to_tree (type, min + wi::to_wide (step) - 1);
1463 : 42471 : assumptions = fold_build2 (LE_EXPR, boolean_type_node, last, iv0->base);
1464 : 42471 : if (integer_zerop (assumptions))
1465 : : return false;
1466 : :
1467 : 42471 : 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 : 42471 : if (sgn == UNSIGNED
1474 : 6546 : && integer_onep (step)
1475 : 968 : && TREE_CODE (iv1->base) == PLUS_EXPR
1476 : 43039 : && integer_onep (TREE_OPERAND (iv1->base, 1)))
1477 : : {
1478 : 427 : tree cond = fold_build2 (GE_EXPR, boolean_type_node,
1479 : : TREE_OPERAND (iv1->base, 0), iv0->base);
1480 : 427 : cond = simplify_using_initial_conditions (loop, cond);
1481 : 427 : 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 : 42471 : high = max;
1488 : 42471 : if (TREE_CODE (iv1->base) == INTEGER_CST)
1489 : 29623 : low = wi::to_wide (iv1->base) - 1;
1490 : 12848 : else if (TREE_CODE (iv0->base) == INTEGER_CST)
1491 : 5650 : low = wi::to_wide (iv0->base);
1492 : : else
1493 : 7198 : low = min;
1494 : : }
1495 : : /* {base, -C} < n. */
1496 : 25350 : else if (tree_int_cst_sign_bit (iv0->step) && integer_zerop (iv1->step))
1497 : : {
1498 : 25350 : step = fold_build1 (NEGATE_EXPR, TREE_TYPE (iv0->step), iv0->step);
1499 : : /* MAX - C + 1 >= n. */
1500 : 25350 : tree last = wide_int_to_tree (type, max - wi::to_wide (step) + 1);
1501 : 25350 : assumptions = fold_build2 (GE_EXPR, boolean_type_node, last, iv1->base);
1502 : 25350 : if (integer_zerop (assumptions))
1503 : : return false;
1504 : :
1505 : 25348 : num = fold_build2 (MINUS_EXPR, niter_type,
1506 : : fold_convert (niter_type, iv0->base),
1507 : : wide_int_to_tree (niter_type, min));
1508 : 25348 : low = min;
1509 : 25348 : if (TREE_CODE (iv0->base) == INTEGER_CST)
1510 : 1196 : high = wi::to_wide (iv0->base) + 1;
1511 : 24152 : else if (TREE_CODE (iv1->base) == INTEGER_CST)
1512 : 2342 : high = wi::to_wide (iv1->base);
1513 : : else
1514 : 21810 : high = max;
1515 : : }
1516 : : else
1517 : 0 : return false;
1518 : :
1519 : : /* (delta + step - 1) / step */
1520 : 67819 : step = fold_convert (niter_type, step);
1521 : 67819 : num = fold_build2 (PLUS_EXPR, niter_type, num, step);
1522 : 67819 : niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, num, step);
1523 : :
1524 : 67819 : widest_int delta, s;
1525 : 67819 : delta = widest_int::from (high, sgn) - widest_int::from (low, sgn);
1526 : 67819 : s = wi::to_widest (step);
1527 : 67819 : delta = delta + s - 1;
1528 : 67819 : niter->max = wi::udiv_floor (delta, s);
1529 : :
1530 : 67819 : niter->may_be_zero = may_be_zero;
1531 : :
1532 : 67819 : if (!integer_nonzerop (assumptions))
1533 : 10238 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1534 : : niter->assumptions, assumptions);
1535 : :
1536 : 67819 : 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 : 67819 : tree base_type = TREE_TYPE (niter->control.base);
1544 : 67819 : if (POINTER_TYPE_P (base_type))
1545 : : {
1546 : 7851 : tree utype = unsigned_type_for (base_type);
1547 : 7851 : niter->control.base
1548 : 7851 : = fold_build2 (MINUS_EXPR, utype,
1549 : : fold_convert (utype, niter->control.base),
1550 : : fold_convert (utype, niter->control.step));
1551 : 7851 : niter->control.base = fold_convert (base_type, niter->control.base);
1552 : : }
1553 : : else
1554 : 59968 : niter->control.base
1555 : 59968 : = fold_build2 (MINUS_EXPR, base_type, niter->control.base,
1556 : : niter->control.step);
1557 : :
1558 : 67819 : span = fold_build2 (MULT_EXPR, niter_type, niter->niter,
1559 : : fold_convert (niter_type, niter->control.step));
1560 : 67819 : niter->bound = fold_build2 (PLUS_EXPR, niter_type, span,
1561 : : fold_convert (niter_type, niter->control.base));
1562 : 67819 : niter->bound = fold_convert (type, niter->bound);
1563 : 67819 : niter->cmp = NE_EXPR;
1564 : :
1565 : 67819 : return true;
1566 : 135850 : }
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 : 5167382 : 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 : 5167382 : tree niter_type = unsigned_type_for (type);
1580 : 5167382 : tree delta, step, s;
1581 : 5167382 : mpz_t mstep, tmp;
1582 : :
1583 : 5167382 : if (integer_nonzerop (iv0->step))
1584 : : {
1585 : 4844886 : niter->control = *iv0;
1586 : 4844886 : niter->cmp = LT_EXPR;
1587 : 4844886 : niter->bound = iv1->base;
1588 : : }
1589 : : else
1590 : : {
1591 : 322496 : niter->control = *iv1;
1592 : 322496 : niter->cmp = GT_EXPR;
1593 : 322496 : niter->bound = iv0->base;
1594 : : }
1595 : :
1596 : : /* {base, -C} < n, or n < {base, C} */
1597 : 5167382 : if (tree_int_cst_sign_bit (iv0->step)
1598 : 5167382 : || (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step)))
1599 : 68031 : return number_of_iterations_until_wrap (loop, type, iv0, iv1, niter);
1600 : :
1601 : 5099351 : 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 : 9600294 : if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1607 : 5099351 : || (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 : 4713750 : if (mpz_sgn (bnds->below) < 0)
1624 : 1834987 : niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1625 : : iv1->base, iv0->base);
1626 : 4713750 : niter->niter = delta;
1627 : 9427500 : niter->max = widest_int::from (wi::from_mpz (niter_type, bnds->up, false),
1628 : 9427500 : TYPE_SIGN (niter_type));
1629 : 4713750 : niter->control.no_overflow = true;
1630 : 4713750 : return true;
1631 : : }
1632 : :
1633 : 385601 : if (integer_nonzerop (iv0->step))
1634 : 318593 : step = fold_convert (niter_type, iv0->step);
1635 : : else
1636 : 67008 : 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 : 385601 : if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1643 : : exit_must_be_taken, bnds))
1644 : : {
1645 : 34693 : affine_iv zps;
1646 : :
1647 : 34693 : zps.base = build_int_cst (niter_type, 0);
1648 : 34693 : zps.step = step;
1649 : : /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1650 : : zps does not overflow. */
1651 : 34693 : zps.no_overflow = true;
1652 : :
1653 : 34693 : 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 : 350908 : 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 : 350797 : assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1665 : :
1666 : 350797 : s = fold_build2 (MINUS_EXPR, niter_type,
1667 : : step, build_int_cst (niter_type, 1));
1668 : 350797 : delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1669 : 350797 : niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1670 : :
1671 : 350797 : mpz_init (mstep);
1672 : 350797 : mpz_init (tmp);
1673 : 350797 : wi::to_mpz (wi::to_wide (step), mstep, UNSIGNED);
1674 : 350797 : mpz_add (tmp, bnds->up, mstep);
1675 : 350797 : mpz_sub_ui (tmp, tmp, 1);
1676 : 350797 : mpz_fdiv_q (tmp, tmp, mstep);
1677 : 701594 : niter->max = widest_int::from (wi::from_mpz (niter_type, tmp, false),
1678 : 701594 : TYPE_SIGN (niter_type));
1679 : 350797 : mpz_clear (mstep);
1680 : 350797 : mpz_clear (tmp);
1681 : :
1682 : 350797 : 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 : 1903868 : 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 : 1903868 : tree assumption;
1698 : 1903868 : tree type1 = type;
1699 : 1903868 : if (POINTER_TYPE_P (type))
1700 : 7367 : 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 : 1903868 : if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1712 : : {
1713 : 605758 : if (integer_nonzerop (iv0->step))
1714 : 542204 : assumption = fold_build2 (NE_EXPR, boolean_type_node,
1715 : : iv1->base, TYPE_MAX_VALUE (type));
1716 : : else
1717 : 63554 : assumption = fold_build2 (NE_EXPR, boolean_type_node,
1718 : : iv0->base, TYPE_MIN_VALUE (type));
1719 : :
1720 : 605758 : if (integer_zerop (assumption))
1721 : : return false;
1722 : 605758 : if (!integer_nonzerop (assumption))
1723 : 227581 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1724 : : niter->assumptions, assumption);
1725 : : }
1726 : :
1727 : 1903868 : if (integer_nonzerop (iv0->step))
1728 : : {
1729 : 1807115 : if (POINTER_TYPE_P (type))
1730 : 1787 : iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1731 : : else
1732 : 1805328 : iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1733 : : build_int_cst (type1, 1));
1734 : : }
1735 : 96753 : else if (POINTER_TYPE_P (type))
1736 : 5580 : iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1737 : : else
1738 : 91173 : iv0->base = fold_build2 (MINUS_EXPR, type1,
1739 : : iv0->base, build_int_cst (type1, 1));
1740 : :
1741 : 1903868 : bounds_add (bnds, 1, type1);
1742 : :
1743 : 1903868 : return number_of_iterations_lt (loop, type, iv0, iv1, niter, exit_must_be_taken,
1744 : 1903868 : bnds);
1745 : : }
1746 : :
1747 : : /* Dumps description of affine induction variable IV to FILE. */
1748 : :
1749 : : static void
1750 : 81868 : dump_affine_iv (FILE *file, affine_iv *iv)
1751 : : {
1752 : 81868 : if (!integer_zerop (iv->step))
1753 : 40934 : fprintf (file, "[");
1754 : :
1755 : 81868 : print_generic_expr (file, iv->base, TDF_SLIM);
1756 : :
1757 : 81868 : if (!integer_zerop (iv->step))
1758 : : {
1759 : 40934 : fprintf (file, ", + , ");
1760 : 40934 : print_generic_expr (file, iv->step, TDF_SLIM);
1761 : 73220 : fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1762 : : }
1763 : 81868 : }
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 : 12538926 : 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 : 12538926 : bool exit_must_be_taken = false, ret;
1800 : 12538926 : 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 : 12538926 : if (!every_iteration
1808 : 68039 : && (!iv0->no_overflow || !iv1->no_overflow
1809 : 42121 : || 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 : 12491777 : niter->assumptions = boolean_true_node;
1818 : 12491777 : niter->may_be_zero = boolean_false_node;
1819 : 12491777 : niter->niter = NULL_TREE;
1820 : 12491777 : niter->max = 0;
1821 : 12491777 : niter->bound = NULL_TREE;
1822 : 12491777 : 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 : 12491777 : if (code == GE_EXPR || code == GT_EXPR
1827 : 12491777 : || (code == NE_EXPR && integer_zerop (iv0->step)))
1828 : : {
1829 : 2847505 : std::swap (iv0, iv1);
1830 : 2847505 : code = swap_tree_comparison (code);
1831 : : }
1832 : :
1833 : 12491777 : 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 : 798979 : iv0->no_overflow = true;
1841 : 798979 : 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 : 12491777 : if (only_exit)
1848 : : {
1849 : 8059622 : if (!integer_zerop (iv0->step) && iv0->no_overflow)
1850 : : exit_must_be_taken = true;
1851 : 2107530 : else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1852 : 6092752 : 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 : 12491777 : if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1870 : : {
1871 : 5357 : tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1872 : 5357 : 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 : 5357 : if (TREE_CODE (step) != INTEGER_CST
1878 : 5357 : || !iv0->no_overflow || !iv1->no_overflow)
1879 : : {
1880 : 991 : 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 : 4366 : else if (tree_int_cst_sign_bit (step) != tree_int_cst_sign_bit (iv0->step)
1888 : 8075 : || wi::gtu_p (wi::abs (wi::to_widest (step)),
1889 : 11784 : wi::abs (wi::to_widest (iv0->step))))
1890 : : {
1891 : 3036 : 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 : 766 : else if (code != NE_EXPR)
1900 : : return false;
1901 : : else
1902 : 665 : iv0->no_overflow = false;
1903 : : }
1904 : :
1905 : 3600 : iv0->step = step;
1906 : 3600 : iv1->step = build_int_cst (step_type, 0);
1907 : 3600 : 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 : 12490020 : 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 : 12396666 : tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
1918 : 12396666 : if (tem && integer_zerop (tem))
1919 : : {
1920 : 83494 : if (!every_iteration)
1921 : : return false;
1922 : 83399 : niter->niter = build_int_cst (unsigned_type_for (type), 0);
1923 : 83399 : niter->max = 0;
1924 : 83399 : 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 : 12313172 : bound_difference (loop, iv1->base, iv0->base, &bnds);
1930 : :
1931 : 12313172 : if (dump_file && (dump_flags & TDF_DETAILS))
1932 : : {
1933 : 40934 : fprintf (dump_file,
1934 : : "Analyzing # of iterations of loop %d\n", loop->num);
1935 : :
1936 : 40934 : fprintf (dump_file, " exit condition ");
1937 : 40934 : dump_affine_iv (dump_file, iv0);
1938 : 48938 : fprintf (dump_file, " %s ",
1939 : : code == NE_EXPR ? "!="
1940 : 8004 : : code == LT_EXPR ? "<"
1941 : : : "<=");
1942 : 40934 : dump_affine_iv (dump_file, iv1);
1943 : 40934 : fprintf (dump_file, "\n");
1944 : :
1945 : 40934 : fprintf (dump_file, " bounds on difference of bases: ");
1946 : 40934 : mpz_out_str (dump_file, 10, bnds.below);
1947 : 40934 : fprintf (dump_file, " ... ");
1948 : 40934 : mpz_out_str (dump_file, 10, bnds.up);
1949 : 40934 : fprintf (dump_file, "\n");
1950 : : }
1951 : :
1952 : 12313172 : switch (code)
1953 : : {
1954 : 7145790 : case NE_EXPR:
1955 : 7145790 : gcc_assert (integer_zerop (iv1->step));
1956 : 7145790 : ret = number_of_iterations_ne (loop, type, iv0, iv1->base, niter,
1957 : : exit_must_be_taken, &bnds);
1958 : 7145790 : break;
1959 : :
1960 : 3263514 : case LT_EXPR:
1961 : 3263514 : ret = number_of_iterations_lt (loop, type, iv0, iv1, niter,
1962 : : exit_must_be_taken, &bnds);
1963 : 3263514 : break;
1964 : :
1965 : 1903868 : case LE_EXPR:
1966 : 1903868 : ret = number_of_iterations_le (loop, type, iv0, iv1, niter,
1967 : : exit_must_be_taken, &bnds);
1968 : 1903868 : break;
1969 : :
1970 : 0 : default:
1971 : 0 : gcc_unreachable ();
1972 : : }
1973 : :
1974 : 12313172 : mpz_clear (bnds.up);
1975 : 12313172 : mpz_clear (bnds.below);
1976 : :
1977 : 12313172 : if (dump_file && (dump_flags & TDF_DETAILS))
1978 : : {
1979 : 40934 : if (ret)
1980 : : {
1981 : 40934 : fprintf (dump_file, " result:\n");
1982 : 40934 : if (!integer_nonzerop (niter->assumptions))
1983 : : {
1984 : 201 : fprintf (dump_file, " under assumptions ");
1985 : 201 : print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1986 : 201 : fprintf (dump_file, "\n");
1987 : : }
1988 : :
1989 : 40934 : if (!integer_zerop (niter->may_be_zero))
1990 : : {
1991 : 923 : fprintf (dump_file, " zero if ");
1992 : 923 : print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1993 : 923 : fprintf (dump_file, "\n");
1994 : : }
1995 : :
1996 : 40934 : fprintf (dump_file, " # of iterations ");
1997 : 40934 : print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1998 : 40934 : fprintf (dump_file, ", bounded by ");
1999 : 40934 : print_decu (niter->max, dump_file);
2000 : 40934 : 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 : 127254 : ssa_defined_by_minus_one_stmt_p (tree op, tree val)
2066 : : {
2067 : 127254 : gimple *stmt;
2068 : 127254 : return (TREE_CODE (op) == SSA_NAME
2069 : 81544 : && (stmt = SSA_NAME_DEF_STMT (op))
2070 : 81544 : && is_gimple_assign (stmt)
2071 : 70302 : && (gimple_assign_rhs_code (stmt) == PLUS_EXPR)
2072 : 7603 : && val == gimple_assign_rhs1 (stmt)
2073 : 128374 : && 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 : 3881816 : number_of_iterations_popcount (loop_p loop, edge exit,
2093 : : enum tree_code code,
2094 : : class tree_niter_desc *niter)
2095 : : {
2096 : 3881816 : bool modify_before_test = true;
2097 : 3881816 : HOST_WIDE_INT max;
2098 : :
2099 : : /* Check that condition for staying inside the loop is like
2100 : : if (iv != 0). */
2101 : 7763632 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
2102 : 3881816 : if (!cond_stmt
2103 : 3881816 : || code != NE_EXPR
2104 : 1805285 : || !integer_zerop (gimple_cond_rhs (cond_stmt))
2105 : 5174819 : || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME)
2106 : 2588813 : return false;
2107 : :
2108 : 1293003 : tree iv_2 = gimple_cond_lhs (cond_stmt);
2109 : 1293003 : 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 : 1293003 : if (gimple_code (iv_2_stmt) == GIMPLE_PHI
2114 : 394208 : && gimple_bb (iv_2_stmt) == loop->header
2115 : 287617 : && gimple_phi_num_args (iv_2_stmt) == 2
2116 : 1580620 : && (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 : 269798 : iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx);
2122 : 269798 : iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2123 : 269798 : modify_before_test = false;
2124 : : }
2125 : :
2126 : : /* Make sure iv_2_stmt is an and stmt (iv_2 = _1 & iv_1). */
2127 : 1293003 : if (!is_gimple_assign (iv_2_stmt)
2128 : 1293003 : || gimple_assign_rhs_code (iv_2_stmt) != BIT_AND_EXPR)
2129 : : return false;
2130 : :
2131 : 64036 : tree iv_1 = gimple_assign_rhs1 (iv_2_stmt);
2132 : 64036 : 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 : 64036 : if (ssa_defined_by_minus_one_stmt_p (iv_1, _1))
2138 : : std::swap (iv_1, _1);
2139 : 63218 : 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 : 8189 : build_cltz_expr (tree src, bool leading, bool define_at_zero)
2200 : : {
2201 : 8189 : tree fn;
2202 : 8189 : internal_fn ifn = leading ? IFN_CLZ : IFN_CTZ;
2203 : 8189 : bool use_ifn = false;
2204 : 8189 : int prec = TYPE_PRECISION (TREE_TYPE (src));
2205 : 8189 : int i_prec = TYPE_PRECISION (integer_type_node);
2206 : 8189 : int li_prec = TYPE_PRECISION (long_integer_type_node);
2207 : 8189 : int lli_prec = TYPE_PRECISION (long_long_integer_type_node);
2208 : :
2209 : 8189 : tree utype = unsigned_type_for (TREE_TYPE (src));
2210 : 8189 : src = fold_convert (utype, src);
2211 : :
2212 : 8189 : 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 : 4854 : tree call;
2227 : 4854 : if (use_ifn)
2228 : : {
2229 : 4854 : int val;
2230 : 4854 : int optab_defined_at_zero
2231 : : = (leading
2232 : 4854 : ? CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype), val)
2233 : 5620 : : CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype), val));
2234 : 4854 : tree arg2 = NULL_TREE;
2235 : 4854 : if (define_at_zero && optab_defined_at_zero == 2 && val == prec)
2236 : 0 : arg2 = build_int_cst (integer_type_node, val);
2237 : 4854 : call = build_call_expr_internal_loc (UNKNOWN_LOCATION, ifn,
2238 : : integer_type_node, arg2 ? 2 : 1,
2239 : : src, arg2);
2240 : 4854 : if (define_at_zero && arg2 == NULL_TREE)
2241 : : {
2242 : 4102 : tree is_zero = fold_build2 (NE_EXPR, boolean_type_node, src,
2243 : : build_zero_cst (TREE_TYPE (src)));
2244 : 4102 : 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 : 1051472 : is_lshift_by_1 (gassign *stmt)
2303 : : {
2304 : 1051472 : if (gimple_assign_rhs_code (stmt) == LSHIFT_EXPR
2305 : 1052769 : && integer_onep (gimple_assign_rhs2 (stmt)))
2306 : : return true;
2307 : 1050728 : if (gimple_assign_rhs_code (stmt) == MULT_EXPR
2308 : 1549 : && tree_fits_shwi_p (gimple_assign_rhs2 (stmt))
2309 : 1051943 : && 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 : 1050509 : is_rshift_by_1 (gassign *stmt)
2318 : : {
2319 : 1050509 : if (!TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (stmt))))
2320 : : return false;
2321 : 777205 : if (gimple_assign_rhs_code (stmt) == RSHIFT_EXPR
2322 : 796390 : && integer_onep (gimple_assign_rhs2 (stmt)))
2323 : : return true;
2324 : 1451426 : if (trunc_or_exact_div_p (gimple_assign_rhs_code (stmt))
2325 : 589 : && tree_fits_shwi_p (gimple_assign_rhs2 (stmt))
2326 : 768044 : && 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 : 1006 : shifted_range_nonzero_p (loop_p loop, tree src,
2339 : : bool left_shift, int num_ignored_bits)
2340 : : {
2341 : 1006 : int_range_max r (TREE_TYPE (src));
2342 : 1006 : gcc_assert (num_ignored_bits >= 0);
2343 : :
2344 : 1006 : if (get_range_query (cfun)->range_on_edge
2345 : 1006 : (r, loop_preheader_edge (loop), src)
2346 : 1006 : && !r.varying_p ()
2347 : 1405 : && !r.undefined_p ())
2348 : : {
2349 : 398 : 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 : 398 : if (!range_includes_zero_p (r))
2366 : : return true;
2367 : : }
2368 : :
2369 : : return false;
2370 : 1006 : }
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 : 6978926 : number_of_iterations_cltz (loop_p loop, edge exit,
2389 : : enum tree_code code,
2390 : : class tree_niter_desc *niter)
2391 : : {
2392 : 6978926 : bool modify_before_test = true;
2393 : 6978926 : HOST_WIDE_INT max;
2394 : 6978926 : int checked_bit;
2395 : 6978926 : tree iv_2;
2396 : :
2397 : : /* Check that condition for staying inside the loop is like
2398 : : if (iv == 0). */
2399 : 13957852 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
2400 : 6978926 : if (!cond_stmt
2401 : 6978926 : || (code != EQ_EXPR && code != GE_EXPR)
2402 : 3407484 : || !integer_zerop (gimple_cond_rhs (cond_stmt))
2403 : 1307795 : || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME)
2404 : 5671370 : return false;
2405 : :
2406 : 1307556 : if (code == EQ_EXPR)
2407 : : {
2408 : : /* Make sure we check a bitwise and with a suitable constant */
2409 : 1209530 : gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond_stmt));
2410 : 1209530 : if (!is_gimple_assign (and_stmt)
2411 : 736012 : || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR
2412 : 137381 : || !integer_pow2p (gimple_assign_rhs2 (and_stmt))
2413 : 1229196 : || TREE_CODE (gimple_assign_rhs1 (and_stmt)) != SSA_NAME)
2414 : 1189864 : return false;
2415 : :
2416 : 19666 : checked_bit = tree_log2 (gimple_assign_rhs2 (and_stmt));
2417 : :
2418 : 19666 : 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 : 98026 : iv_2 = gimple_cond_lhs (cond_stmt);
2426 : 98026 : tree test_value_type = TREE_TYPE (iv_2);
2427 : :
2428 : 98026 : if (TYPE_UNSIGNED (test_value_type))
2429 : : return false;
2430 : :
2431 : 98026 : gimple *test_value_stmt = SSA_NAME_DEF_STMT (iv_2);
2432 : :
2433 : 98026 : if (is_gimple_assign (test_value_stmt)
2434 : 98026 : && 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 : 5218 : iv_2 = gimple_assign_rhs1 (test_value_stmt);
2440 : 5218 : tree rhs_type = TREE_TYPE (iv_2);
2441 : 5218 : if (TREE_CODE (iv_2) != SSA_NAME
2442 : 5218 : || TREE_CODE (rhs_type) != INTEGER_TYPE
2443 : 10425 : || (TYPE_PRECISION (rhs_type)
2444 : 5207 : != TYPE_PRECISION (test_value_type)))
2445 : : return false;
2446 : : }
2447 : :
2448 : 97649 : checked_bit = TYPE_PRECISION (test_value_type) - 1;
2449 : : }
2450 : :
2451 : 117315 : 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 : 117315 : if (gimple_code (iv_2_stmt) == GIMPLE_PHI
2456 : 25644 : && gimple_bb (iv_2_stmt) == loop->header
2457 : 15171 : && gimple_phi_num_args (iv_2_stmt) == 2
2458 : 132486 : && (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 : 14978 : iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx);
2464 : 14978 : iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2465 : 14978 : 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 : 117315 : if (!is_gimple_assign (iv_2_stmt))
2471 : : return false;
2472 : 87165 : bool left_shift = false;
2473 : 173839 : if (!((left_shift = is_lshift_by_1 (as_a <gassign *> (iv_2_stmt)))
2474 : 86674 : || is_rshift_by_1 (as_a <gassign *> (iv_2_stmt))))
2475 : : return false;
2476 : :
2477 : 1042 : tree iv_1 = gimple_assign_rhs1 (iv_2_stmt);
2478 : :
2479 : : /* Check the recurrence. */
2480 : 1042 : gimple *phi = SSA_NAME_DEF_STMT (iv_1);
2481 : 1042 : if (gimple_code (phi) != GIMPLE_PHI
2482 : 1010 : || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
2483 : 2048 : || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)))
2484 : 36 : return false;
2485 : :
2486 : : /* We found a match. */
2487 : 1006 : tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
2488 : 1006 : int src_precision = TYPE_PRECISION (TREE_TYPE (src));
2489 : :
2490 : : /* Save the original SSA name before preprocessing for ranger queries. */
2491 : 1006 : tree unshifted_src = src;
2492 : :
2493 : : /* Apply any needed preprocessing to src. */
2494 : 1006 : int num_ignored_bits;
2495 : 1006 : if (left_shift)
2496 : 455 : num_ignored_bits = src_precision - checked_bit - 1;
2497 : : else
2498 : : num_ignored_bits = checked_bit;
2499 : :
2500 : 1006 : if (modify_before_test)
2501 : 411 : num_ignored_bits++;
2502 : :
2503 : 1006 : 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 : 1006 : tree expr = build_cltz_expr (src, left_shift, false);
2510 : :
2511 : 1006 : if (!expr)
2512 : : return false;
2513 : :
2514 : 1006 : max = src_precision - num_ignored_bits - 1;
2515 : :
2516 : 1006 : 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 : 1006 : tree assumptions;
2551 : 1006 : 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 : 779 : assumptions = fold_build2 (NE_EXPR, boolean_type_node, src,
2559 : : build_zero_cst (TREE_TYPE (src)));
2560 : 779 : assumptions = simplify_using_initial_conditions (loop, assumptions);
2561 : : }
2562 : :
2563 : 1006 : niter->assumptions = assumptions;
2564 : 1006 : niter->may_be_zero = boolean_false_node;
2565 : 1006 : niter->niter = simplify_using_initial_conditions (loop, expr);
2566 : :
2567 : 1006 : if (TREE_CODE (niter->niter) == INTEGER_CST)
2568 : 0 : niter->max = tree_to_uhwi (niter->niter);
2569 : : else
2570 : 1006 : niter->max = max;
2571 : :
2572 : 1006 : niter->bound = NULL_TREE;
2573 : 1006 : niter->cmp = ERROR_MARK;
2574 : :
2575 : 1006 : 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 : 3880779 : number_of_iterations_cltz_complement (loop_p loop, edge exit,
2594 : : enum tree_code code,
2595 : : class tree_niter_desc *niter)
2596 : : {
2597 : 3880779 : bool modify_before_test = true;
2598 : 3880779 : HOST_WIDE_INT max;
2599 : :
2600 : : /* Check that condition for staying inside the loop is like
2601 : : if (iv != 0). */
2602 : 7761558 : gcond *cond_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
2603 : 3880779 : if (!cond_stmt
2604 : 3880779 : || code != NE_EXPR
2605 : 1804415 : || !integer_zerop (gimple_cond_rhs (cond_stmt))
2606 : 5172912 : || TREE_CODE (gimple_cond_lhs (cond_stmt)) != SSA_NAME)
2607 : 2588646 : return false;
2608 : :
2609 : 1292133 : tree iv_2 = gimple_cond_lhs (cond_stmt);
2610 : 1292133 : 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 : 1292133 : if (gimple_code (iv_2_stmt) == GIMPLE_PHI
2615 : 393720 : && gimple_bb (iv_2_stmt) == loop->header
2616 : 287129 : && gimple_phi_num_args (iv_2_stmt) == 2
2617 : 1579262 : && (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 : 269310 : iv_2 = gimple_phi_arg_def (iv_2_stmt, loop_latch_edge (loop)->dest_idx);
2623 : 269310 : iv_2_stmt = SSA_NAME_DEF_STMT (iv_2);
2624 : 269310 : 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 : 1292133 : if (!is_gimple_assign (iv_2_stmt))
2630 : : return false;
2631 : 964307 : bool left_shift = false;
2632 : 1928142 : if (!((left_shift = is_lshift_by_1 (as_a <gassign *> (iv_2_stmt)))
2633 : 963835 : || is_rshift_by_1 (as_a <gassign *> (iv_2_stmt))))
2634 : : return false;
2635 : :
2636 : 9587 : tree iv_1 = gimple_assign_rhs1 (iv_2_stmt);
2637 : :
2638 : : /* Check the recurrence. */
2639 : 9587 : gimple *phi = SSA_NAME_DEF_STMT (iv_1);
2640 : 9587 : if (gimple_code (phi) != GIMPLE_PHI
2641 : 8891 : || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
2642 : 17342 : || (iv_2 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)))
2643 : 2404 : return false;
2644 : :
2645 : : /* We found a match. */
2646 : 7183 : tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
2647 : 7183 : int src_precision = TYPE_PRECISION (TREE_TYPE (src));
2648 : :
2649 : : /* Get the corresponding c[lt]z builtin. */
2650 : 7183 : tree expr = build_cltz_expr (src, !left_shift, true);
2651 : :
2652 : 7183 : if (!expr)
2653 : : return false;
2654 : :
2655 : 7183 : expr = fold_build2 (MINUS_EXPR, integer_type_node,
2656 : : build_int_cst (integer_type_node, src_precision),
2657 : : expr);
2658 : :
2659 : 7183 : max = src_precision;
2660 : :
2661 : 7183 : tree may_be_zero = boolean_false_node;
2662 : :
2663 : 7183 : if (modify_before_test)
2664 : : {
2665 : 5931 : expr = fold_build2 (MINUS_EXPR, integer_type_node, expr,
2666 : : integer_one_node);
2667 : 5931 : max = max - 1;
2668 : 5931 : may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
2669 : : build_zero_cst (TREE_TYPE (src)));
2670 : : }
2671 : :
2672 : 7183 : expr = fold_convert (unsigned_type_node, expr);
2673 : :
2674 : 7183 : niter->assumptions = boolean_true_node;
2675 : 7183 : niter->may_be_zero = simplify_using_initial_conditions (loop, may_be_zero);
2676 : 7183 : niter->niter = simplify_using_initial_conditions (loop, expr);
2677 : :
2678 : 7183 : if (TREE_CODE (niter->niter) == INTEGER_CST)
2679 : 65 : niter->max = tree_to_uhwi (niter->niter);
2680 : : else
2681 : 7118 : niter->max = max;
2682 : :
2683 : 7183 : niter->bound = NULL_TREE;
2684 : 7183 : niter->cmp = ERROR_MARK;
2685 : 7183 : 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 : 3881816 : number_of_iterations_bitcount (loop_p loop, edge exit,
2731 : : enum tree_code code,
2732 : : class tree_niter_desc *niter)
2733 : : {
2734 : 3881816 : return (number_of_iterations_popcount (loop, exit, code, niter)
2735 : 3880946 : || number_of_iterations_cltz (loop, exit, code, niter)
2736 : 7762595 : || 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 : 148277414 : simplify_replace_tree (tree expr, tree old, tree new_tree,
2746 : : tree (*valueize) (tree, void*), void *context,
2747 : : bool do_fold)
2748 : : {
2749 : 148277414 : unsigned i, n;
2750 : 148277414 : tree ret = NULL_TREE, e, se;
2751 : :
2752 : 148277414 : if (!expr)
2753 : : return NULL_TREE;
2754 : :
2755 : : /* Do not bother to replace constants. */
2756 : 31857575 : if (CONSTANT_CLASS_P (expr))
2757 : : return expr;
2758 : :
2759 : 24079532 : if (valueize)
2760 : : {
2761 : 268743 : if (TREE_CODE (expr) == SSA_NAME)
2762 : : {
2763 : 83292 : new_tree = valueize (expr, context);
2764 : 83292 : if (new_tree != expr)
2765 : : return new_tree;
2766 : : }
2767 : : }
2768 : 23810789 : else if (expr == old
2769 : 23810789 : || operand_equal_p (expr, old, 0))
2770 : 211279 : return unshare_expr (new_tree);
2771 : :
2772 : 23867766 : if (!EXPR_P (expr))
2773 : : return expr;
2774 : :
2775 : 12807791 : n = TREE_OPERAND_LENGTH (expr);
2776 : 35812805 : for (i = 0; i < n; i++)
2777 : : {
2778 : 23005014 : e = TREE_OPERAND (expr, i);
2779 : 23005014 : se = simplify_replace_tree (e, old, new_tree, valueize, context, do_fold);
2780 : 23005014 : if (e == se)
2781 : 22742760 : continue;
2782 : :
2783 : 262254 : if (!ret)
2784 : 261795 : ret = copy_node (expr);
2785 : :
2786 : 262254 : TREE_OPERAND (ret, i) = se;
2787 : : }
2788 : :
2789 : 12807791 : 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 : 115388082 : expand_simple_operations (tree expr, tree stop, hash_map<tree, tree> &cache)
2798 : : {
2799 : 115807058 : unsigned i, n;
2800 : 115807058 : tree ret = NULL_TREE, e, ee, e1;
2801 : 115807058 : enum tree_code code;
2802 : 115807058 : gimple *stmt;
2803 : :
2804 : 115807058 : if (expr == NULL_TREE)
2805 : : return expr;
2806 : :
2807 : 115807058 : if (is_gimple_min_invariant (expr))
2808 : : return expr;
2809 : :
2810 : 78804327 : code = TREE_CODE (expr);
2811 : 78804327 : if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
2812 : : {
2813 : 20127716 : n = TREE_OPERAND_LENGTH (expr);
2814 : 55723600 : for (i = 0; i < n; i++)
2815 : : {
2816 : 35595884 : e = TREE_OPERAND (expr, i);
2817 : 35595884 : if (!e)
2818 : 32272110 : 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 : 35581161 : bool existed_p;
2827 : 35581161 : tree &cee = cache.get_or_insert (e, &existed_p);
2828 : 35581161 : if (existed_p)
2829 : 149481 : ee = cee;
2830 : : else
2831 : : {
2832 : 35431680 : cee = e;
2833 : 35431680 : ee = expand_simple_operations (e, stop, cache);
2834 : 35431680 : if (ee != e)
2835 : 3322021 : *cache.get (e) = ee;
2836 : : }
2837 : 35581161 : if (e == ee)
2838 : 32257387 : continue;
2839 : :
2840 : 3323774 : if (!ret)
2841 : 3152479 : ret = copy_node (expr);
2842 : :
2843 : 3323774 : TREE_OPERAND (ret, i) = ee;
2844 : : }
2845 : :
2846 : 20127716 : if (!ret)
2847 : : return expr;
2848 : :
2849 : 3152479 : fold_defer_overflow_warnings ();
2850 : 3152479 : ret = fold (ret);
2851 : 3152479 : fold_undefer_and_ignore_overflow_warnings ();
2852 : 3152479 : return ret;
2853 : : }
2854 : :
2855 : : /* Stop if it's not ssa name or the one we don't want to expand. */
2856 : 58676611 : if (TREE_CODE (expr) != SSA_NAME || expr == stop)
2857 : : return expr;
2858 : :
2859 : 58491059 : stmt = SSA_NAME_DEF_STMT (expr);
2860 : 58491059 : if (gimple_code (stmt) == GIMPLE_PHI)
2861 : : {
2862 : 16118289 : basic_block src, dest;
2863 : :
2864 : 16118289 : if (gimple_phi_num_args (stmt) != 1)
2865 : : return expr;
2866 : 589903 : 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 : 589903 : dest = gimple_bb (stmt);
2871 : 589903 : src = single_pred (dest);
2872 : 589903 : if (TREE_CODE (e) == SSA_NAME
2873 : 588062 : && src->loop_father != dest->loop_father)
2874 : : return expr;
2875 : :
2876 : : return expand_simple_operations (e, stop, cache);
2877 : : }
2878 : 42372770 : 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 : 37121941 : ssa_op_iter iter;
2884 : 77053323 : FOR_EACH_SSA_TREE_OPERAND (e, stmt, iter, SSA_OP_USE)
2885 : 39932013 : if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e))
2886 : : return expr;
2887 : :
2888 : 37121310 : e = gimple_assign_rhs1 (stmt);
2889 : 37121310 : code = gimple_assign_rhs_code (stmt);
2890 : 37121310 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2891 : : {
2892 : 14580516 : if (is_gimple_min_invariant (e))
2893 : : return e;
2894 : :
2895 : 14544606 : if (code == SSA_NAME)
2896 : : return expand_simple_operations (e, stop, cache);
2897 : 14319194 : else if (code == ADDR_EXPR)
2898 : : {
2899 : 12198 : poly_int64 offset;
2900 : 12198 : tree base = get_addr_base_and_unit_offset (TREE_OPERAND (e, 0),
2901 : : &offset);
2902 : 12198 : if (base
2903 : 11578 : && TREE_CODE (base) == MEM_REF)
2904 : : {
2905 : 11578 : ee = expand_simple_operations (TREE_OPERAND (base, 0), stop,
2906 : : cache);
2907 : 11578 : 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 : 14307616 : return expr;
2915 : : }
2916 : :
2917 : 22540794 : switch (code)
2918 : : {
2919 : 5166144 : CASE_CONVERT:
2920 : : /* Casts are simple. */
2921 : 5166144 : ee = expand_simple_operations (e, stop, cache);
2922 : 5166144 : return fold_build1 (code, TREE_TYPE (expr), ee);
2923 : :
2924 : 12518845 : case PLUS_EXPR:
2925 : 12518845 : case MINUS_EXPR:
2926 : 12518845 : case MULT_EXPR:
2927 : 25037690 : if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr))
2928 : 25035122 : && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr)))
2929 : : return expr;
2930 : : /* Fallthru. */
2931 : 13198682 : case POINTER_PLUS_EXPR:
2932 : : /* And increments and decrements by a constant are simple. */
2933 : 13198682 : e1 = gimple_assign_rhs2 (stmt);
2934 : 13198682 : if (!is_gimple_min_invariant (e1))
2935 : : return expr;
2936 : :
2937 : 6679663 : ee = expand_simple_operations (e, stop, cache);
2938 : 6679663 : return fold_build2 (code, TREE_TYPE (expr), ee, e1);
2939 : :
2940 : : default:
2941 : : return expr;
2942 : : }
2943 : : }
2944 : :
2945 : : tree
2946 : 68099017 : expand_simple_operations (tree expr, tree stop)
2947 : : {
2948 : 68099017 : hash_map<tree, tree> cache;
2949 : 68099017 : return expand_simple_operations (expr, stop, cache);
2950 : 68099017 : }
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 : 8924386 : tree_simplify_using_condition_1 (tree cond, tree expr)
2957 : : {
2958 : 8924386 : bool changed;
2959 : 8924386 : tree e, e0, e1, e2, notcond;
2960 : 8924386 : enum tree_code code = TREE_CODE (expr);
2961 : :
2962 : 8924386 : if (code == INTEGER_CST)
2963 : : return expr;
2964 : :
2965 : 8914259 : if (code == TRUTH_OR_EXPR
2966 : 8914259 : || code == TRUTH_AND_EXPR
2967 : 8914259 : || code == COND_EXPR)
2968 : : {
2969 : 112235 : changed = false;
2970 : :
2971 : 112235 : e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
2972 : 112235 : if (TREE_OPERAND (expr, 0) != e0)
2973 : 2037 : changed = true;
2974 : :
2975 : 112235 : e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
2976 : 112235 : if (TREE_OPERAND (expr, 1) != e1)
2977 : 0 : changed = true;
2978 : :
2979 : 112235 : 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 : 112235 : if (changed)
2989 : : {
2990 : 2037 : if (code == COND_EXPR)
2991 : 1892 : expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
2992 : : else
2993 : 145 : expr = fold_build2 (code, boolean_type_node, e0, e1);
2994 : : }
2995 : :
2996 : 112235 : 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 : 8802024 : if (TREE_CODE (cond) == EQ_EXPR)
3003 : : {
3004 : 2048555 : e0 = TREE_OPERAND (cond, 0);
3005 : 2048555 : e1 = TREE_OPERAND (cond, 1);
3006 : :
3007 : : /* We know that e0 == e1. Check whether we cannot simplify expr
3008 : : using this fact. */
3009 : 2048555 : e = simplify_replace_tree (expr, e0, e1);
3010 : 2048555 : if (integer_zerop (e) || integer_nonzerop (e))
3011 : 2497 : return e;
3012 : :
3013 : 2046058 : e = simplify_replace_tree (expr, e1, e0);
3014 : 2046058 : if (integer_zerop (e) || integer_nonzerop (e))
3015 : 425 : return e;
3016 : : }
3017 : 8799102 : if (TREE_CODE (expr) == EQ_EXPR)
3018 : : {
3019 : 1202735 : e0 = TREE_OPERAND (expr, 0);
3020 : 1202735 : e1 = TREE_OPERAND (expr, 1);
3021 : :
3022 : : /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
3023 : 1202735 : e = simplify_replace_tree (cond, e0, e1);
3024 : 1202735 : if (integer_zerop (e))
3025 : : return e;
3026 : 1185141 : e = simplify_replace_tree (cond, e1, e0);
3027 : 1185141 : if (integer_zerop (e))
3028 : : return e;
3029 : : }
3030 : 8781508 : if (TREE_CODE (expr) == NE_EXPR)
3031 : : {
3032 : 1021191 : e0 = TREE_OPERAND (expr, 0);
3033 : 1021191 : e1 = TREE_OPERAND (expr, 1);
3034 : :
3035 : : /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
3036 : 1021191 : e = simplify_replace_tree (cond, e0, e1);
3037 : 1021191 : if (integer_zerop (e))
3038 : 11595 : return boolean_true_node;
3039 : 1009596 : e = simplify_replace_tree (cond, e1, e0);
3040 : 1009596 : if (integer_zerop (e))
3041 : 0 : return boolean_true_node;
3042 : : }
3043 : :
3044 : : /* Check whether COND ==> EXPR. */
3045 : 8769913 : notcond = invert_truthvalue (cond);
3046 : 8769913 : e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, expr);
3047 : 8769913 : if (e && integer_nonzerop (e))
3048 : : return e;
3049 : :
3050 : : /* Check whether COND ==> not EXPR. */
3051 : 8767649 : e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, expr);
3052 : 8767649 : 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 : 8687945 : tree_simplify_using_condition (tree cond, tree expr)
3067 : : {
3068 : 8687945 : cond = expand_simple_operations (cond);
3069 : :
3070 : 8687945 : 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 : 27309385 : simplify_using_initial_conditions (class loop *loop, tree expr)
3079 : : {
3080 : 27309385 : edge e;
3081 : 27309385 : basic_block bb;
3082 : 27309385 : tree cond, expanded, backup;
3083 : 27309385 : int cnt = 0;
3084 : :
3085 : 27309385 : if (TREE_CODE (expr) == INTEGER_CST)
3086 : : return expr;
3087 : :
3088 : 2928117 : value_range expr_range (TREE_TYPE (expr));
3089 : 2928117 : if (TREE_TYPE (expr) == boolean_type_node
3090 : 5838300 : && get_range_query (cfun)->range_on_edge (expr_range,
3091 : : loop_preheader_edge (loop),
3092 : : expr)
3093 : 2919150 : && !expr_range.undefined_p ()
3094 : 5847265 : && !expr_range.varying_p ())
3095 : 127303 : return expr_range.nonzero_p () ? boolean_true_node : boolean_false_node;
3096 : :
3097 : 2800814 : 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 : 2800814 : for (bb = loop->header;
3103 : 27437956 : bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
3104 : 24637142 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
3105 : : {
3106 : 24716075 : if (!single_pred_p (bb))
3107 : 12366842 : continue;
3108 : 12349233 : e = single_pred_edge (bb);
3109 : :
3110 : 12349233 : if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3111 : 3661288 : continue;
3112 : :
3113 : 17375890 : gcond *stmt = as_a <gcond *> (*gsi_last_bb (e->src));
3114 : 8687945 : cond = fold_build2 (gimple_cond_code (stmt),
3115 : : boolean_type_node,
3116 : : gimple_cond_lhs (stmt),
3117 : : gimple_cond_rhs (stmt));
3118 : 8687945 : if (e->flags & EDGE_FALSE_VALUE)
3119 : 4869306 : cond = invert_truthvalue (cond);
3120 : 8687945 : expanded = tree_simplify_using_condition (cond, expanded);
3121 : : /* Break if EXPR is simplified to const values. */
3122 : 8687945 : if (expanded
3123 : 8687945 : && (integer_zerop (expanded) || integer_nonzerop (expanded)))
3124 : 78933 : return expanded;
3125 : :
3126 : 8609012 : ++cnt;
3127 : : }
3128 : :
3129 : : /* Return the original expression if no simplification is done. */
3130 : 2721881 : return operand_equal_p (backup, expanded, 0) ? expr : expanded;
3131 : 2928117 : }
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 : 6199003 : simplify_using_outer_evolutions (class loop *loop, tree expr)
3139 : : {
3140 : 6199003 : enum tree_code code = TREE_CODE (expr);
3141 : 6199003 : bool changed;
3142 : 6199003 : tree e, e0, e1, e2;
3143 : :
3144 : 6199003 : if (is_gimple_min_invariant (expr))
3145 : : return expr;
3146 : :
3147 : 1393499 : if (code == TRUTH_OR_EXPR
3148 : 1393499 : || code == TRUTH_AND_EXPR
3149 : 1393499 : || code == COND_EXPR)
3150 : : {
3151 : 8507 : changed = false;
3152 : :
3153 : 8507 : e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
3154 : 8507 : if (TREE_OPERAND (expr, 0) != e0)
3155 : 0 : changed = true;
3156 : :
3157 : 8507 : e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
3158 : 8507 : if (TREE_OPERAND (expr, 1) != e1)
3159 : 0 : changed = true;
3160 : :
3161 : 8507 : 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 : 8507 : 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 : 8507 : return expr;
3179 : : }
3180 : :
3181 : 1384992 : e = instantiate_parameters (loop, expr);
3182 : 1384992 : 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 : 12945863 : loop_only_exit_p (const class loop *loop, basic_block *body, const_edge exit)
3192 : : {
3193 : 12945863 : gimple_stmt_iterator bsi;
3194 : 12945863 : unsigned i;
3195 : :
3196 : 12945863 : if (exit != single_exit (loop))
3197 : : return false;
3198 : :
3199 : 42522090 : for (i = 0; i < loop->num_nodes; i++)
3200 : 282506428 : for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
3201 : 215612014 : 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 : 24856385 : 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 : 24856385 : tree type;
3223 : 24856385 : tree op0, op1;
3224 : 24856385 : enum tree_code code;
3225 : 24856385 : affine_iv iv0, iv1;
3226 : 24856385 : bool safe;
3227 : :
3228 : : /* The condition at a fake exit (if it exists) does not control its
3229 : : execution. */
3230 : 24856385 : if (exit->flags & EDGE_FAKE)
3231 : : return false;
3232 : :
3233 : : /* Nothing to analyze if the loop is known to be infinite. */
3234 : 24855953 : if (loop_constraint_set_p (loop, LOOP_C_INFINITE))
3235 : : return false;
3236 : :
3237 : 24855953 : safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
3238 : :
3239 : 24855953 : if (every_iteration && !safe)
3240 : : return false;
3241 : :
3242 : 23599175 : niter->assumptions = boolean_false_node;
3243 : 23599175 : niter->control.base = NULL_TREE;
3244 : 23599175 : niter->control.step = NULL_TREE;
3245 : 23599175 : niter->control.no_overflow = false;
3246 : 52678691 : gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
3247 : 21050467 : if (!stmt)
3248 : : return false;
3249 : :
3250 : 21050467 : if (at_stmt)
3251 : 20399100 : *at_stmt = stmt;
3252 : :
3253 : : /* We want the condition for staying inside loop. */
3254 : 21050467 : code = gimple_cond_code (stmt);
3255 : 21050467 : if (exit->flags & EDGE_TRUE_VALUE)
3256 : 7796756 : code = invert_tree_comparison (code, false);
3257 : :
3258 : 21050467 : switch (code)
3259 : : {
3260 : 17952155 : case GT_EXPR:
3261 : 17952155 : case GE_EXPR:
3262 : 17952155 : case LT_EXPR:
3263 : 17952155 : case LE_EXPR:
3264 : 17952155 : case NE_EXPR:
3265 : 17952155 : break;
3266 : :
3267 : 3097980 : case EQ_EXPR:
3268 : 3097980 : return number_of_iterations_cltz (loop, exit, code, niter);
3269 : :
3270 : : default:
3271 : : return false;
3272 : : }
3273 : :
3274 : 17952155 : op0 = gimple_cond_lhs (stmt);
3275 : 17952155 : op1 = gimple_cond_rhs (stmt);
3276 : 17952155 : type = TREE_TYPE (op0);
3277 : :
3278 : 17952155 : if (TREE_CODE (type) != INTEGER_TYPE
3279 : 3060182 : && !POINTER_TYPE_P (type))
3280 : : return false;
3281 : :
3282 : 17117277 : tree iv0_niters = NULL_TREE;
3283 : 34234554 : if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
3284 : : op0, &iv0, safe ? &iv0_niters : NULL, false))
3285 : 3881816 : return number_of_iterations_bitcount (loop, exit, code, niter);
3286 : 13235461 : tree iv1_niters = NULL_TREE;
3287 : 26470922 : 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 : 12538926 : 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 : 12538926 : fold_defer_overflow_warnings ();
3297 : :
3298 : 12538926 : iv0.base = expand_simple_operations (iv0.base);
3299 : 12538926 : iv1.base = expand_simple_operations (iv1.base);
3300 : 12538926 : bool body_from_caller = true;
3301 : 12538926 : if (!body)
3302 : : {
3303 : 7435285 : body = get_loop_body (loop);
3304 : 7435285 : body_from_caller = false;
3305 : : }
3306 : 12538926 : bool only_exit_p = loop_only_exit_p (loop, body, exit);
3307 : 12538926 : if (!body_from_caller)
3308 : 7435285 : free (body);
3309 : 12538926 : if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
3310 : : only_exit_p, safe))
3311 : : {
3312 : 142678 : fold_undefer_and_ignore_overflow_warnings ();
3313 : 142678 : return false;
3314 : : }
3315 : :
3316 : : /* Incorporate additional assumption implied by control iv. */
3317 : 12396248 : tree iv_niters = iv0_niters ? iv0_niters : iv1_niters;
3318 : 12396248 : if (iv_niters)
3319 : : {
3320 : 28331 : tree assumption = fold_build2 (LE_EXPR, boolean_type_node, niter->niter,
3321 : : fold_convert (TREE_TYPE (niter->niter),
3322 : : iv_niters));
3323 : :
3324 : 28331 : if (!integer_nonzerop (assumption))
3325 : 25321 : niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
3326 : : niter->assumptions, assumption);
3327 : :
3328 : : /* Refine upper bound if possible. */
3329 : 28331 : if (TREE_CODE (iv_niters) == INTEGER_CST
3330 : 56662 : && niter->max > wi::to_widest (iv_niters))
3331 : 25184 : niter->max = wi::to_widest (iv_niters);
3332 : : }
3333 : :
3334 : : /* There is no assumptions if the loop is known to be finite. */
3335 : 12396248 : if (!integer_zerop (niter->assumptions)
3336 : 12396248 : && loop_constraint_set_p (loop, LOOP_C_FINITE))
3337 : 12181 : niter->assumptions = boolean_true_node;
3338 : :
3339 : 12396248 : if (optimize >= 3)
3340 : : {
3341 : 2060663 : niter->assumptions = simplify_using_outer_evolutions (loop,
3342 : : niter->assumptions);
3343 : 2060663 : niter->may_be_zero = simplify_using_outer_evolutions (loop,
3344 : : niter->may_be_zero);
3345 : 2060663 : niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
3346 : : }
3347 : :
3348 : 12396248 : niter->assumptions
3349 : 12396248 : = simplify_using_initial_conditions (loop,
3350 : : niter->assumptions);
3351 : 12396248 : niter->may_be_zero
3352 : 12396248 : = simplify_using_initial_conditions (loop,
3353 : : niter->may_be_zero);
3354 : :
3355 : 12396248 : fold_undefer_and_ignore_overflow_warnings ();
3356 : :
3357 : : /* If NITER has simplified into a constant, update MAX. */
3358 : 12396248 : if (TREE_CODE (niter->niter) == INTEGER_CST)
3359 : 7029953 : niter->max = wi::to_widest (niter->niter);
3360 : :
3361 : 12396248 : 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 : 24091583 : 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 : 24091583 : gcond *stmt;
3374 : 24091583 : if (!number_of_iterations_exit_assumptions (loop, exit, niter,
3375 : : &stmt, every_iteration, body))
3376 : : return false;
3377 : :
3378 : 12035319 : if (integer_nonzerop (niter->assumptions))
3379 : : return true;
3380 : :
3381 : 608809 : 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 : 781264 : find_loop_niter (class loop *loop, edge *exit)
3396 : : {
3397 : 781264 : unsigned i;
3398 : 781264 : auto_vec<edge> exits = get_loop_exit_edges (loop);
3399 : 781264 : edge ex;
3400 : 781264 : tree niter = NULL_TREE, aniter;
3401 : 781264 : class tree_niter_desc desc;
3402 : :
3403 : 781264 : *exit = NULL;
3404 : 3553810 : FOR_EACH_VEC_ELT (exits, i, ex)
3405 : : {
3406 : 2772546 : if (!number_of_iterations_exit (loop, ex, &desc, false))
3407 : 2261641 : continue;
3408 : :
3409 : 510905 : 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 : 510905 : if (!integer_zerop (desc.may_be_zero))
3419 : 58389 : continue;
3420 : :
3421 : 452516 : aniter = desc.niter;
3422 : :
3423 : 452516 : if (!niter)
3424 : : {
3425 : : /* Nothing recorded yet. */
3426 : 442953 : niter = aniter;
3427 : 442953 : *exit = ex;
3428 : 442953 : continue;
3429 : : }
3430 : :
3431 : : /* Prefer constants, the lower the better. */
3432 : 9563 : if (TREE_CODE (aniter) != INTEGER_CST)
3433 : 5203 : continue;
3434 : :
3435 : 4360 : if (TREE_CODE (niter) != INTEGER_CST)
3436 : : {
3437 : 1119 : niter = aniter;
3438 : 1119 : *exit = ex;
3439 : 1119 : continue;
3440 : : }
3441 : :
3442 : 3241 : if (tree_int_cst_lt (aniter, niter))
3443 : : {
3444 : 186 : niter = aniter;
3445 : 186 : *exit = ex;
3446 : 186 : continue;
3447 : : }
3448 : : }
3449 : :
3450 : 781264 : return niter ? niter : chrec_dont_know;
3451 : 781264 : }
3452 : :
3453 : : /* Return true if loop is known to have bounded number of iterations. */
3454 : :
3455 : : bool
3456 : 2970880 : finite_loop_p (class loop *loop)
3457 : : {
3458 : 2970880 : widest_int nit;
3459 : 2970880 : int flags;
3460 : :
3461 : 2970880 : if (loop->finite_p)
3462 : : {
3463 : 2190218 : unsigned i;
3464 : 2190218 : auto_vec<edge> exits = get_loop_exit_edges (loop);
3465 : 2190218 : edge ex;
3466 : :
3467 : : /* If the loop has a normal exit, we can assume it will terminate. */
3468 : 4399944 : FOR_EACH_VEC_ELT (exits, i, ex)
3469 : 2205075 : if (!(ex->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_FAKE)))
3470 : : {
3471 : 2185866 : if (dump_file)
3472 : 150 : 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 : 2185866 : return true;
3477 : : }
3478 : 2190218 : }
3479 : :
3480 : 785014 : flags = flags_from_decl_or_type (current_function_decl);
3481 : 785014 : if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
3482 : : {
3483 : 2258 : 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 : 2258 : loop->finite_p = true;
3489 : 2258 : return true;
3490 : : }
3491 : :
3492 : 782756 : if (loop->any_upper_bound
3493 : : /* Loop with no normal exit will not pass max_loop_iterations. */
3494 : 782756 : || (!loop->finite_p && max_loop_iterations (loop, &nit)))
3495 : : {
3496 : 399659 : 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 : 399659 : loop->finite_p = true;
3500 : 399659 : return true;
3501 : : }
3502 : :
3503 : : return false;
3504 : 2970880 : }
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 : 1968868 : chain_of_csts_start (class loop *loop, tree x)
3523 : : {
3524 : 2357443 : gimple *stmt = SSA_NAME_DEF_STMT (x);
3525 : 2357443 : tree use;
3526 : 2357443 : basic_block bb = gimple_bb (stmt);
3527 : 2357443 : enum tree_code code;
3528 : :
3529 : 2357443 : if (!bb
3530 : 2357443 : || !flow_bb_inside_loop_p (loop, bb))
3531 : 525712 : return NULL;
3532 : :
3533 : 1831731 : if (gimple_code (stmt) == GIMPLE_PHI)
3534 : : {
3535 : 738435 : if (bb == loop->header)
3536 : 673767 : return as_a <gphi *> (stmt);
3537 : :
3538 : : return NULL;
3539 : : }
3540 : :
3541 : 1093296 : if (gimple_code (stmt) != GIMPLE_ASSIGN
3542 : 2069595 : || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS)
3543 : : return NULL;
3544 : :
3545 : 976022 : code = gimple_assign_rhs_code (stmt);
3546 : 976022 : if (gimple_references_memory_p (stmt)
3547 : 525477 : || TREE_CODE_CLASS (code) == tcc_reference
3548 : 500068 : || (code == ADDR_EXPR
3549 : 507 : && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
3550 : 476461 : return NULL;
3551 : :
3552 : 499561 : use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
3553 : 499561 : 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 : 1782376 : get_base_for (class loop *loop, tree x)
3572 : : {
3573 : 1782376 : gphi *phi;
3574 : 1782376 : tree init, next;
3575 : :
3576 : 1782376 : if (is_gimple_min_invariant (x))
3577 : : return NULL;
3578 : :
3579 : 1782376 : phi = chain_of_csts_start (loop, x);
3580 : 1782376 : if (!phi)
3581 : : return NULL;
3582 : :
3583 : 503333 : init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
3584 : 503333 : next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3585 : :
3586 : 503333 : if (!is_gimple_min_invariant (init))
3587 : : return NULL;
3588 : :
3589 : 209334 : if (TREE_CODE (next) == SSA_NAME
3590 : 209334 : && 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 : 7452134 : get_val_for (tree x, tree base)
3607 : : {
3608 : 7466216 : gimple *stmt;
3609 : :
3610 : 7466216 : gcc_checking_assert (is_gimple_min_invariant (base));
3611 : :
3612 : 7466216 : if (!x)
3613 : : return base;
3614 : 5238504 : else if (is_gimple_min_invariant (x))
3615 : : return x;
3616 : :
3617 : 5215959 : stmt = SSA_NAME_DEF_STMT (x);
3618 : 5215959 : if (gimple_code (stmt) == GIMPLE_PHI)
3619 : : return base;
3620 : :
3621 : 2768229 : 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 : 2768229 : if (gimple_assign_ssa_name_copy_p (stmt))
3627 : 14082 : return get_val_for (gimple_assign_rhs1 (stmt), base);
3628 : 2754147 : else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
3629 : 2754147 : && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
3630 : 289341 : 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 : 2464806 : else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
3634 : : {
3635 : 2464806 : tree rhs1 = gimple_assign_rhs1 (stmt);
3636 : 2464806 : tree rhs2 = gimple_assign_rhs2 (stmt);
3637 : 2464806 : if (TREE_CODE (rhs1) == SSA_NAME)
3638 : 2403246 : 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 : 2464806 : 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 : 1765616 : loop_niter_by_eval (class loop *loop, edge exit)
3660 : : {
3661 : 1765616 : tree acnd;
3662 : 1765616 : tree op[2], val[2], next[2], aval[2];
3663 : 1765616 : gphi *phi;
3664 : 1765616 : unsigned i, j;
3665 : 1765616 : enum tree_code cmp;
3666 : :
3667 : 3531232 : gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (exit->src));
3668 : 1765616 : if (!cond)
3669 : 149294 : return chrec_dont_know;
3670 : :
3671 : 1616322 : cmp = gimple_cond_code (cond);
3672 : 1616322 : if (exit->flags & EDGE_TRUE_VALUE)
3673 : 580605 : cmp = invert_tree_comparison (cmp, false);
3674 : :
3675 : 1616322 : switch (cmp)
3676 : : {
3677 : 1616294 : case EQ_EXPR:
3678 : 1616294 : case NE_EXPR:
3679 : 1616294 : case GT_EXPR:
3680 : 1616294 : case GE_EXPR:
3681 : 1616294 : case LT_EXPR:
3682 : 1616294 : case LE_EXPR:
3683 : 1616294 : op[0] = gimple_cond_lhs (cond);
3684 : 1616294 : op[1] = gimple_cond_rhs (cond);
3685 : 1616294 : break;
3686 : :
3687 : 28 : default:
3688 : 28 : return chrec_dont_know;
3689 : : }
3690 : :
3691 : 1836084 : for (j = 0; j < 2; j++)
3692 : : {
3693 : 1809129 : if (is_gimple_min_invariant (op[j]))
3694 : : {
3695 : 26753 : val[j] = op[j];
3696 : 26753 : next[j] = NULL_TREE;
3697 : 26753 : op[j] = NULL_TREE;
3698 : : }
3699 : : else
3700 : : {
3701 : 1782376 : phi = get_base_for (loop, op[j]);
3702 : 1782376 : if (!phi)
3703 : : {
3704 : 1589339 : gassign *def;
3705 : 1589339 : if (j == 0
3706 : 1423459 : && (cmp == NE_EXPR || cmp == EQ_EXPR)
3707 : 808432 : && TREE_CODE (op[0]) == SSA_NAME
3708 : 808432 : && TREE_CODE (op[1]) == INTEGER_CST
3709 : 518182 : && (def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (op[0])))
3710 : 1871540 : && gimple_assign_rhs_code (def) == MEM_REF)
3711 : : {
3712 : 61663 : tree mem = gimple_assign_rhs1 (def);
3713 : 61663 : affine_iv iv;
3714 : 61663 : if (TYPE_MODE (TREE_TYPE (mem)) == TYPE_MODE (char_type_node)
3715 : 23486 : && simple_iv (loop, loop,
3716 : 23486 : TREE_OPERAND (mem, 0), &iv, false)
3717 : 16857 : && tree_fits_uhwi_p (TREE_OPERAND (mem, 1))
3718 : 78520 : && tree_fits_uhwi_p (iv.step))
3719 : : {
3720 : 16857 : tree str, off;
3721 : : /* iv.base can be &"Foo" but also (char *)&"Foo" + 1. */
3722 : 16857 : split_constant_offset (iv.base, &str, &off);
3723 : 16857 : STRIP_NOPS (str);
3724 : 16857 : if (TREE_CODE (str) == ADDR_EXPR
3725 : 2623 : && TREE_CODE (TREE_OPERAND (str, 0)) == STRING_CST
3726 : 17986 : && tree_fits_uhwi_p (off))
3727 : : {
3728 : 1129 : str = TREE_OPERAND (str, 0);
3729 : 1129 : unsigned i = 0;
3730 : 2258 : for (unsigned HOST_WIDE_INT idx
3731 : 1129 : = (tree_to_uhwi (TREE_OPERAND (mem, 1))
3732 : 1129 : + tree_to_uhwi (off));
3733 : 17990 : idx < (unsigned)TREE_STRING_LENGTH (str)
3734 : 8995 : && i < MAX_ITERATIONS_TO_TRACK;
3735 : 7866 : idx += tree_to_uhwi (iv.step), ++i)
3736 : : {
3737 : 8697 : int res = compare_tree_int
3738 : 8697 : (op[1], TREE_STRING_POINTER (str)[idx]);
3739 : 8697 : if ((cmp == NE_EXPR && res == 0)
3740 : 7885 : || (cmp == EQ_EXPR && res != 0))
3741 : 831 : return build_int_cst (unsigned_type_node, i);
3742 : : }
3743 : : }
3744 : : }
3745 : : }
3746 : 1588508 : return chrec_dont_know;
3747 : : }
3748 : 193037 : val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
3749 : 193037 : next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
3750 : : }
3751 : : }
3752 : :
3753 : : /* Don't issue signed overflow warnings. */
3754 : 26955 : fold_defer_overflow_warnings ();
3755 : :
3756 : 1215191 : for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
3757 : : {
3758 : 3561954 : for (j = 0; j < 2; j++)
3759 : 2374636 : aval[j] = get_val_for (op[j], val[j]);
3760 : :
3761 : 1187318 : acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
3762 : 1187318 : if (acnd && integer_zerop (acnd))
3763 : : {
3764 : 25282 : fold_undefer_and_ignore_overflow_warnings ();
3765 : 25282 : 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 : 25282 : return build_int_cst (unsigned_type_node, i);
3770 : : }
3771 : :
3772 : 3484666 : for (j = 0; j < 2; j++)
3773 : : {
3774 : 2323351 : aval[j] = val[j];
3775 : 2323351 : val[j] = get_val_for (next[j], val[j]);
3776 : 2323351 : if (!is_gimple_min_invariant (val[j]))
3777 : : {
3778 : 721 : fold_undefer_and_ignore_overflow_warnings ();
3779 : 721 : 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 : 1161315 : if (val[0] == aval[0] && val[1] == aval[1])
3787 : : break;
3788 : : }
3789 : :
3790 : 952 : fold_undefer_and_ignore_overflow_warnings ();
3791 : :
3792 : 952 : 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 : 799636 : find_loop_niter_by_eval (class loop *loop, edge *exit)
3804 : : {
3805 : 799636 : unsigned i;
3806 : 799636 : auto_vec<edge> exits = get_loop_exit_edges (loop);
3807 : 799636 : edge ex;
3808 : 799636 : tree niter = NULL_TREE, aniter;
3809 : :
3810 : 799636 : *exit = NULL;
3811 : :
3812 : : /* Loops with multiple exits are expensive to handle and less important. */
3813 : 799636 : if (!flag_expensive_optimizations
3814 : 819680 : && exits.length () > 1)
3815 : 4012 : return chrec_dont_know;
3816 : :
3817 : 2496934 : FOR_EACH_VEC_ELT (exits, i, ex)
3818 : : {
3819 : 1701310 : if (!just_once_each_iteration_p (loop, ex->src))
3820 : 506238 : continue;
3821 : :
3822 : 1195072 : aniter = loop_niter_by_eval (loop, ex);
3823 : 1195072 : if (chrec_contains_undetermined (aniter))
3824 : 1180827 : continue;
3825 : :
3826 : 14343 : if (niter
3827 : 14245 : && !tree_int_cst_lt (aniter, niter))
3828 : 98 : continue;
3829 : :
3830 : 14147 : niter = aniter;
3831 : 14147 : *exit = ex;
3832 : : }
3833 : :
3834 : 795624 : return niter ? niter : chrec_dont_know;
3835 : 799636 : }
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 : 11049535 : derive_constant_upper_bound (tree val)
3866 : : {
3867 : 11049535 : enum tree_code code;
3868 : 11049535 : tree op0, op1, op2;
3869 : :
3870 : 11049535 : extract_ops_from_tree (val, &code, &op0, &op1, &op2);
3871 : 11049535 : 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 : 11049814 : derive_constant_upper_bound_ops (tree type, tree op0,
3880 : : enum tree_code code, tree op1)
3881 : : {
3882 : 11049814 : tree subtype, maxt;
3883 : 11049814 : widest_int bnd, max, cst;
3884 : 11049814 : gimple *stmt;
3885 : :
3886 : 11049814 : if (INTEGRAL_TYPE_P (type))
3887 : 11049814 : maxt = TYPE_MAX_VALUE (type);
3888 : : else
3889 : 0 : maxt = upper_bound_in_type (type, type);
3890 : :
3891 : 11049814 : max = wi::to_widest (maxt);
3892 : :
3893 : 11049814 : switch (code)
3894 : : {
3895 : 10976412 : case INTEGER_CST:
3896 : 10976412 : return wi::to_widest (op0);
3897 : :
3898 : 1114 : CASE_CONVERT:
3899 : 1114 : subtype = TREE_TYPE (op0);
3900 : 1114 : if (!TYPE_UNSIGNED (subtype)
3901 : : /* If TYPE is also signed, the fact that VAL is nonnegative implies
3902 : : that OP0 is nonnegative. */
3903 : 835 : && TYPE_UNSIGNED (type)
3904 : 1949 : && !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 : 812 : 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 : 41938 : case PLUS_EXPR:
3924 : 41938 : case POINTER_PLUS_EXPR:
3925 : 41938 : case MINUS_EXPR:
3926 : 41938 : if (TREE_CODE (op1) != INTEGER_CST
3927 : 41938 : || !tree_expr_nonnegative_p (op0))
3928 : 41495 : 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 : 443 : cst = wi::sext (wi::to_widest (op1), TYPE_PRECISION (type));
3934 : 443 : if (code != MINUS_EXPR)
3935 : 443 : cst = -cst;
3936 : :
3937 : 443 : bnd = derive_constant_upper_bound (op0);
3938 : :
3939 : 443 : 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 : 414 : if (wi::ltu_p (bnd, cst))
3971 : 0 : return max;
3972 : :
3973 : 414 : if (TYPE_UNSIGNED (type))
3974 : : {
3975 : 414 : tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
3976 : : wide_int_to_tree (type, cst));
3977 : 414 : if (!tem || integer_nonzerop (tem))
3978 : 50 : return max;
3979 : : }
3980 : :
3981 : 364 : bnd -= cst;
3982 : : }
3983 : :
3984 : 364 : 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 : 479 : case SSA_NAME:
4002 : 479 : stmt = SSA_NAME_DEF_STMT (op0);
4003 : 479 : if (gimple_code (stmt) != GIMPLE_ASSIGN
4004 : 479 : || gimple_assign_lhs (stmt) != op0)
4005 : 200 : return max;
4006 : 279 : return derive_constant_upper_bound_assign (stmt);
4007 : :
4008 : 29864 : default:
4009 : 29864 : return max;
4010 : : }
4011 : 11049827 : }
4012 : :
4013 : : /* Emit a -Waggressive-loop-optimizations warning if needed. */
4014 : :
4015 : : static void
4016 : 10116441 : 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 : 10116441 : if (!loop->nb_iterations
4021 : 10116441 : || TREE_CODE (loop->nb_iterations) != INTEGER_CST
4022 : 4770959 : || !warn_aggressive_loop_optimizations
4023 : : /* To avoid warning multiple times for the same loop,
4024 : : only start warning when we preserve loops. */
4025 : 4770792 : || (cfun->curr_properties & PROP_loops) == 0
4026 : : /* Only warn once per loop. */
4027 : 4770792 : || loop->warned_aggressive_loop_optimizations
4028 : : /* Only warn if undefined behavior gives us lower estimate than the
4029 : : known constant bound. */
4030 : 4770203 : || wi::cmpu (i_bound, wi::to_widest (loop->nb_iterations)) >= 0
4031 : : /* And undefined behavior happens unconditionally. */
4032 : 10116486 : || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
4033 : 10116396 : return;
4034 : :
4035 : 45 : edge e = single_exit (loop);
4036 : 45 : if (e == NULL)
4037 : : return;
4038 : :
4039 : 45 : gimple *estmt = last_nondebug_stmt (e->src);
4040 : 45 : char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
4041 : 45 : unsigned len;
4042 : 45 : 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 : 45 : print_dec (i_bound, p, TYPE_SIGN (TREE_TYPE (loop->nb_iterations)));
4048 : 45 : auto_diagnostic_group d;
4049 : 45 : 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 : 45 : loop->warned_aggressive_loop_optimizations = true;
4053 : 45 : }
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 : 15731460 : 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 : 15731460 : widest_int delta;
4067 : :
4068 : 15731460 : if (dump_file && (dump_flags & TDF_DETAILS))
4069 : : {
4070 : 119378 : fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
4071 : 66194 : print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
4072 : 66814 : fprintf (dump_file, " is %sexecuted at most ",
4073 : : upper ? "" : "probably ");
4074 : 66194 : print_generic_expr (dump_file, bound, TDF_SLIM);
4075 : 66194 : fprintf (dump_file, " (bounded by ");
4076 : 66194 : print_decu (i_bound, dump_file);
4077 : 66194 : 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 : 15731460 : if (TREE_CODE (bound) != INTEGER_CST)
4083 : : realistic = false;
4084 : : else
4085 : 13889461 : gcc_checking_assert (i_bound == wi::to_widest (bound));
4086 : :
4087 : 15731460 : 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 : 15731447 : if (upper
4094 : 15216413 : && (is_exit
4095 : 10533743 : || loop->nb_iterations == NULL_TREE
4096 : 10533743 : || TREE_CODE (loop->nb_iterations) != INTEGER_CST))
4097 : : {
4098 : 10244766 : class nb_iter_bound *elt = ggc_alloc<nb_iter_bound> ();
4099 : :
4100 : 10244766 : elt->bound = bound_wide_int::from (i_bound, SIGNED);
4101 : 10244766 : elt->stmt = at_stmt;
4102 : 10244766 : elt->is_exit = is_exit;
4103 : 10244766 : elt->next = loop->bounds;
4104 : 10244766 : 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 : 15731447 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
4110 : 479772 : 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 : 15731447 : if (is_exit)
4117 : 4682672 : delta = 0;
4118 : : else
4119 : 11048775 : delta = 1;
4120 : 15731447 : widest_int new_i_bound = i_bound + delta;
4121 : :
4122 : : /* If an overflow occurred, ignore the result. */
4123 : 15731447 : if (wi::ltu_p (new_i_bound, delta))
4124 : 0 : return;
4125 : :
4126 : 15731447 : if (upper && !is_exit)
4127 : 10116441 : do_warn_aggressive_loop_optimizations (loop, new_i_bound, at_stmt);
4128 : 15731447 : record_niter_bound (loop, new_i_bound, realistic, upper);
4129 : 15731460 : }
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 : 4682670 : record_control_iv (class loop *loop, class tree_niter_desc *niter)
4136 : : {
4137 : 4682670 : struct control_iv *iv;
4138 : :
4139 : 4682670 : if (!niter->control.base || !niter->control.step)
4140 : : return;
4141 : :
4142 : 4645313 : if (!integer_onep (niter->assumptions) || !niter->control.no_overflow)
4143 : : return;
4144 : :
4145 : 4503588 : iv = ggc_alloc<control_iv> ();
4146 : 4503588 : iv->base = niter->control.base;
4147 : 4503588 : iv->step = niter->control.step;
4148 : 4503588 : iv->next = loop->control_ivs;
4149 : 4503588 : loop->control_ivs = iv;
4150 : :
4151 : 4503588 : 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 : 119863 : get_cst_init_from_scev (tree var, wide_int *init, bool is_min)
4164 : : {
4165 : 119863 : if (TREE_CODE (var) != SSA_NAME)
4166 : : return false;
4167 : :
4168 : 119863 : gimple *def_stmt = SSA_NAME_DEF_STMT (var);
4169 : 223116 : class loop *loop = loop_containing_stmt (def_stmt);
4170 : :
4171 : 107872 : if (loop == NULL)
4172 : : return false;
4173 : :
4174 : 107872 : affine_iv iv;
4175 : 107872 : if (!simple_iv (loop, loop, var, &iv, false))
4176 : : return false;
4177 : :
4178 : 5817 : if (!iv.no_overflow)
4179 : : return false;
4180 : :
4181 : 5781 : if (TREE_CODE (iv.base) != INTEGER_CST || TREE_CODE (iv.step) != INTEGER_CST)
4182 : : return false;
4183 : :
4184 : 4850 : if (is_min == tree_int_cst_sign_bit (iv.step))
4185 : : return false;
4186 : :
4187 : 4619 : *init = wi::to_wide (iv.base);
4188 : 4619 : 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 : 11048788 : record_nonwrapping_iv (class loop *loop, tree base, tree step, gimple *stmt,
4199 : : tree low, tree high, bool realistic, bool upper)
4200 : : {
4201 : 11048788 : tree niter_bound, extreme, delta;
4202 : 11048788 : tree type = TREE_TYPE (base), unsigned_type;
4203 : 11048788 : tree orig_base = base;
4204 : :
4205 : 11048788 : if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
4206 : 0 : return;
4207 : :
4208 : 11048788 : if (dump_file && (dump_flags & TDF_DETAILS))
4209 : : {
4210 : 53184 : fprintf (dump_file, "Induction variable (");
4211 : 53184 : print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
4212 : 53184 : fprintf (dump_file, ") ");
4213 : 53184 : print_generic_expr (dump_file, base, TDF_SLIM);
4214 : 53184 : fprintf (dump_file, " + ");
4215 : 53184 : print_generic_expr (dump_file, step, TDF_SLIM);
4216 : 53184 : fprintf (dump_file, " * iteration does not wrap in statement ");
4217 : 53184 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
4218 : 53184 : fprintf (dump_file, " in loop %d.\n", loop->num);
4219 : : }
4220 : :
4221 : 11048788 : unsigned_type = unsigned_type_for (type);
4222 : 11048788 : base = fold_convert (unsigned_type, base);
4223 : 11048788 : step = fold_convert (unsigned_type, step);
4224 : :
4225 : 11048788 : if (tree_int_cst_sign_bit (step))
4226 : : {
4227 : 348478 : wide_int max;
4228 : 348478 : value_range base_range (TREE_TYPE (orig_base));
4229 : 696956 : if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
4230 : 348478 : && !base_range.undefined_p ())
4231 : 348399 : max = wi::to_wide (base_range.ubound ());
4232 : 348478 : extreme = fold_convert (unsigned_type, low);
4233 : 348478 : if (TREE_CODE (orig_base) == SSA_NAME
4234 : 20083 : && TREE_CODE (high) == INTEGER_CST
4235 : 20083 : && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
4236 : 20005 : && ((!base_range.varying_p ()
4237 : 6757 : && !base_range.undefined_p ())
4238 : 13327 : || get_cst_init_from_scev (orig_base, &max, false))
4239 : 355156 : && wi::gts_p (wi::to_wide (high), max))
4240 : 1828 : base = wide_int_to_tree (unsigned_type, max);
4241 : 346650 : else if (TREE_CODE (base) != INTEGER_CST
4242 : 559486 : && dominated_by_p (CDI_DOMINATORS,
4243 : 212836 : loop->latch, gimple_bb (stmt)))
4244 : 211394 : base = fold_convert (unsigned_type, high);
4245 : 348478 : delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
4246 : 348478 : step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
4247 : 348479 : }
4248 : : else
4249 : : {
4250 : 10700310 : wide_int min;
4251 : 10700310 : value_range base_range (TREE_TYPE (orig_base));
4252 : 21400620 : if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
4253 : 10700310 : && !base_range.undefined_p ())
4254 : 10698032 : min = wi::to_wide (base_range.lbound ());
4255 : 10700310 : extreme = fold_convert (unsigned_type, high);
4256 : 10700310 : if (TREE_CODE (orig_base) == SSA_NAME
4257 : 852249 : && TREE_CODE (low) == INTEGER_CST
4258 : 852249 : && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
4259 : 262882 : && ((!base_range.varying_p ()
4260 : 158341 : && !base_range.undefined_p ())
4261 : 106536 : || get_cst_init_from_scev (orig_base, &min, true))
4262 : 10861275 : && wi::gts_p (min, wi::to_wide (low)))
4263 : 12424 : base = wide_int_to_tree (unsigned_type, min);
4264 : 10687886 : else if (TREE_CODE (base) != INTEGER_CST
4265 : 14067274 : && dominated_by_p (CDI_DOMINATORS,
4266 : 3379388 : loop->latch, gimple_bb (stmt)))
4267 : 3308452 : base = fold_convert (unsigned_type, low);
4268 : 10700310 : delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
4269 : 10700322 : }
4270 : :
4271 : : /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
4272 : : would get out of the range. */
4273 : 11048788 : niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
4274 : 11048788 : widest_int max = derive_constant_upper_bound (niter_bound);
4275 : 11048788 : record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
4276 : 11048788 : }
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 : 34905916 : idx_infer_loop_bounds (tree base, tree *idx, void *dta)
4291 : : {
4292 : 34905916 : struct ilb_data *data = (struct ilb_data *) dta;
4293 : 34905916 : tree ev, init, step;
4294 : 34905916 : tree low, high, type, next;
4295 : 34905916 : bool sign, upper = true, has_flexible_size = false;
4296 : 34905916 : class loop *loop = data->loop;
4297 : :
4298 : 34905916 : 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 : 9310573 : if (array_ref_flexible_size_p (base))
4304 : : {
4305 : 2153422 : has_flexible_size = true;
4306 : 2153422 : upper = false;
4307 : : }
4308 : :
4309 : 9310573 : class loop *dloop = loop_containing_stmt (data->stmt);
4310 : 9310573 : if (!dloop)
4311 : : return true;
4312 : :
4313 : 9310573 : ev = analyze_scalar_evolution (dloop, *idx);
4314 : 9310573 : ev = instantiate_parameters (loop, ev);
4315 : 9310573 : init = initial_condition (ev);
4316 : 9310573 : step = evolution_part_in_loop_num (ev, loop->num);
4317 : :
4318 : 9310573 : if (!init
4319 : 9310573 : || !step
4320 : 5546561 : || TREE_CODE (step) != INTEGER_CST
4321 : 4235156 : || integer_zerop (step)
4322 : 4235156 : || tree_contains_chrecs (init, NULL)
4323 : 13545729 : || chrec_contains_symbols_defined_in_loop (init, loop->num))
4324 : 5075417 : return true;
4325 : :
4326 : 4235156 : low = array_ref_low_bound (base);
4327 : 4235156 : high = array_ref_up_bound (base);
4328 : :
4329 : : /* The case of nonconstant bounds could be handled, but it would be
4330 : : complicated. */
4331 : 4235156 : if (TREE_CODE (low) != INTEGER_CST
4332 : 4235156 : || !high
4333 : 3529176 : || TREE_CODE (high) != INTEGER_CST)
4334 : : return true;
4335 : 3348258 : sign = tree_int_cst_sign_bit (step);
4336 : 3348258 : type = TREE_TYPE (step);
4337 : :
4338 : : /* The array that might have flexible size most likely extends
4339 : : beyond its bounds. */
4340 : 3348258 : if (has_flexible_size
4341 : 3348258 : && 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 : 3329436 : if (!int_fits_type_p (high, type)
4353 : 3329404 : || !int_fits_type_p (low, type))
4354 : : return true;
4355 : 3329404 : low = fold_convert (type, low);
4356 : 3329404 : high = fold_convert (type, high);
4357 : :
4358 : 3329404 : if (sign)
4359 : 56020 : next = fold_binary (PLUS_EXPR, type, low, step);
4360 : : else
4361 : 3273384 : next = fold_binary (PLUS_EXPR, type, high, step);
4362 : :
4363 : 3329404 : if (tree_int_cst_compare (low, next) <= 0
4364 : 3329404 : && 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 : 3329404 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)))
4370 : : {
4371 : 471570 : if (scev_probably_wraps_p (NULL_TREE,
4372 : 471570 : initial_condition_in_loop_num (ev, loop->num),
4373 : : step, data->stmt, loop, true))
4374 : 3329404 : upper = false;
4375 : : }
4376 : : else
4377 : 2857834 : record_nonwrapping_chrec (ev);
4378 : :
4379 : 3329404 : record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper);
4380 : 3329404 : 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 : 35929180 : infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref)
4389 : : {
4390 : 35929180 : struct ilb_data data;
4391 : :
4392 : 35929180 : data.loop = loop;
4393 : 35929180 : 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 : 255449254 : infer_loop_bounds_from_array (class loop *loop, gimple *stmt)
4403 : : {
4404 : 255449254 : if (is_gimple_assign (stmt))
4405 : : {
4406 : 103389671 : tree op0 = gimple_assign_lhs (stmt);
4407 : 103389671 : 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 : 103389671 : if (REFERENCE_CLASS_P (op0))
4412 : 13932613 : infer_loop_bounds_from_ref (loop, stmt, op0);
4413 : :
4414 : 103389671 : if (REFERENCE_CLASS_P (op1))
4415 : 21822549 : infer_loop_bounds_from_ref (loop, stmt, op1);
4416 : : }
4417 : 152059583 : else if (is_gimple_call (stmt))
4418 : : {
4419 : 7310424 : tree arg, lhs;
4420 : 7310424 : unsigned i, n = gimple_call_num_args (stmt);
4421 : :
4422 : 7310424 : lhs = gimple_call_lhs (stmt);
4423 : 7310424 : if (lhs && REFERENCE_CLASS_P (lhs))
4424 : 5109 : infer_loop_bounds_from_ref (loop, stmt, lhs);
4425 : :
4426 : 23739424 : for (i = 0; i < n; i++)
4427 : : {
4428 : 16429000 : arg = gimple_call_arg (stmt, i);
4429 : 16429000 : if (REFERENCE_CLASS_P (arg))
4430 : 168909 : infer_loop_bounds_from_ref (loop, stmt, arg);
4431 : : }
4432 : : }
4433 : 255449254 : }
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 : 129005557 : infer_loop_bounds_from_pointer_arith (class loop *loop, gimple *stmt)
4440 : : {
4441 : 129005557 : tree def, base, step, scev, type, low, high;
4442 : 129005557 : tree var, ptr;
4443 : :
4444 : 129005557 : if (!is_gimple_assign (stmt)
4445 : 129005557 : || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
4446 : : return;
4447 : :
4448 : 4677771 : def = gimple_assign_lhs (stmt);
4449 : 4677771 : if (TREE_CODE (def) != SSA_NAME)
4450 : : return;
4451 : :
4452 : 4677771 : type = TREE_TYPE (def);
4453 : 4677771 : if (!nowrap_type_p (type))
4454 : : return;
4455 : :
4456 : 4677771 : ptr = gimple_assign_rhs1 (stmt);
4457 : 4677771 : if (!expr_invariant_in_loop_p (loop, ptr))
4458 : : return;
4459 : :
4460 : 2545895 : var = gimple_assign_rhs2 (stmt);
4461 : 2545895 : if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
4462 : : return;
4463 : :
4464 : 2545895 : class loop *uloop = loop_containing_stmt (stmt);
4465 : 2545895 : scev = instantiate_parameters (loop, analyze_scalar_evolution (uloop, def));
4466 : 2545895 : if (chrec_contains_undetermined (scev))
4467 : : return;
4468 : :
4469 : 2101755 : base = initial_condition_in_loop_num (scev, loop->num);
4470 : 2101755 : step = evolution_part_in_loop_num (scev, loop->num);
4471 : :
4472 : 2101755 : if (!base || !step
4473 : 2053775 : || TREE_CODE (step) != INTEGER_CST
4474 : 1863054 : || tree_contains_chrecs (base, NULL)
4475 : 3964809 : || chrec_contains_symbols_defined_in_loop (base, loop->num))
4476 : 238701 : return;
4477 : :
4478 : 1863054 : low = lower_bound_in_type (type, type);
4479 : 1863054 : 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 : 1863054 : if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
4489 : 1863054 : low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
4490 : :
4491 : 1863054 : record_nonwrapping_chrec (scev);
4492 : 1863054 : 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 : 129005557 : infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
4500 : : {
4501 : 129005557 : tree def, base, step, scev, type, low, high;
4502 : :
4503 : 129005557 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
4504 : 123149227 : return;
4505 : :
4506 : 52968724 : def = gimple_assign_lhs (stmt);
4507 : :
4508 : 52968724 : if (TREE_CODE (def) != SSA_NAME)
4509 : : return;
4510 : :
4511 : 45424634 : type = TREE_TYPE (def);
4512 : 45424634 : if (!INTEGRAL_TYPE_P (type)
4513 : 45424634 : || !TYPE_OVERFLOW_UNDEFINED (type))
4514 : : return;
4515 : :
4516 : 15002475 : scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
4517 : 15002475 : if (chrec_contains_undetermined (scev))
4518 : : return;
4519 : :
4520 : 7307338 : base = initial_condition_in_loop_num (scev, loop->num);
4521 : 7307338 : step = evolution_part_in_loop_num (scev, loop->num);
4522 : :
4523 : 7307338 : if (!base || !step
4524 : 6500120 : || TREE_CODE (step) != INTEGER_CST
4525 : 5856330 : || tree_contains_chrecs (base, NULL)
4526 : 13163668 : || chrec_contains_symbols_defined_in_loop (base, loop->num))
4527 : 1451008 : return;
4528 : :
4529 : 5856330 : low = lower_bound_in_type (type, type);
4530 : 5856330 : high = upper_bound_in_type (type, type);
4531 : 5856330 : int_range_max r (TREE_TYPE (def));
4532 : 11712660 : get_range_query (cfun)->range_of_expr (r, def);
4533 : 5856330 : if (!r.varying_p () && !r.undefined_p ())
4534 : : {
4535 : 5372033 : low = wide_int_to_tree (type, r.lower_bound ());
4536 : 5372045 : high = wide_int_to_tree (type, r.upper_bound ());
4537 : : }
4538 : :
4539 : 5856330 : record_nonwrapping_chrec (scev);
4540 : 5856330 : record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
4541 : 5856330 : }
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 : 6536633 : infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs)
4554 : : {
4555 : 6536633 : unsigned i;
4556 : 6536633 : gimple_stmt_iterator bsi;
4557 : 6536633 : basic_block bb;
4558 : 6536633 : bool reliable;
4559 : :
4560 : 45152833 : for (i = 0; i < loop->num_nodes; i++)
4561 : : {
4562 : 38616200 : 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 : 38616200 : reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
4569 : :
4570 : 332681654 : for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4571 : : {
4572 : 255449254 : gimple *stmt = gsi_stmt (bsi);
4573 : :
4574 : 255449254 : infer_loop_bounds_from_array (loop, stmt);
4575 : :
4576 : 255449254 : if (reliable)
4577 : : {
4578 : 129005557 : infer_loop_bounds_from_signedness (loop, stmt);
4579 : 129005557 : infer_loop_bounds_from_pointer_arith (loop, stmt);
4580 : : }
4581 : : }
4582 : :
4583 : : }
4584 : 6536633 : }
4585 : :
4586 : : /* Compare wide ints, callback for qsort. */
4587 : :
4588 : : static int
4589 : 26682 : wide_int_cmp (const void *p1, const void *p2)
4590 : : {
4591 : 26682 : const bound_wide_int *d1 = (const bound_wide_int *) p1;
4592 : 26682 : const bound_wide_int *d2 = (const bound_wide_int *) p2;
4593 : 26682 : 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 : 6667 : bound_index (const vec<bound_wide_int> &bounds, const bound_wide_int &bound)
4601 : : {
4602 : 6667 : unsigned int end = bounds.length ();
4603 : : unsigned int begin = 0;
4604 : :
4605 : : /* Find a matching index by means of a binary search. */
4606 : 7607 : while (begin != end)
4607 : : {
4608 : 7607 : unsigned int middle = (begin + end) / 2;
4609 : 7607 : bound_wide_int index = bounds[middle];
4610 : :
4611 : 7607 : if (index == bound)
4612 : 6667 : return middle;
4613 : 940 : 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 : 6575041 : discover_iteration_bound_by_body_walk (class loop *loop)
4629 : : {
4630 : 6575041 : class nb_iter_bound *elt;
4631 : 6575041 : auto_vec<bound_wide_int> bounds;
4632 : 6575041 : vec<vec<basic_block> > queues = vNULL;
4633 : 6575041 : vec<basic_block> queue = vNULL;
4634 : 6575041 : ptrdiff_t queue_index;
4635 : 6575041 : ptrdiff_t latch_index = 0;
4636 : :
4637 : : /* Discover what bounds may interest us. */
4638 : 16819807 : for (elt = loop->bounds; elt; elt = elt->next)
4639 : : {
4640 : 10244766 : 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 : 10244766 : if (!elt->is_exit)
4645 : : {
4646 : 5562096 : bound += 1;
4647 : : /* If an overflow occurred, ignore the result. */
4648 : 5562096 : if (bound == 0)
4649 : 0 : continue;
4650 : : }
4651 : :
4652 : 10244766 : if (!loop->any_upper_bound
4653 : 10244766 : || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
4654 : 6667 : bounds.safe_push (bound);
4655 : : }
4656 : :
4657 : : /* Exit early if there is nothing to do. */
4658 : 6575041 : if (!bounds.exists ())
4659 : 6571372 : return;
4660 : :
4661 : 3669 : 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 : 3669 : 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 : 3669 : hash_map<basic_block, ptrdiff_t> bb_bounds;
4671 : 18287 : for (elt = loop->bounds; elt; elt = elt->next)
4672 : : {
4673 : 14618 : bound_wide_int bound = elt->bound;
4674 : 14618 : if (!elt->is_exit)
4675 : : {
4676 : 10458 : bound += 1;
4677 : : /* If an overflow occurred, ignore the result. */
4678 : 10458 : if (bound == 0)
4679 : 0 : continue;
4680 : : }
4681 : :
4682 : 14618 : if (!loop->any_upper_bound
4683 : 14618 : || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
4684 : : {
4685 : 6667 : ptrdiff_t index = bound_index (bounds, bound);
4686 : 6667 : ptrdiff_t *entry = bb_bounds.get (gimple_bb (elt->stmt));
4687 : 6667 : if (!entry)
4688 : 4744 : bb_bounds.put (gimple_bb (elt->stmt), index);
4689 : 1923 : else if ((ptrdiff_t)*entry > index)
4690 : 138 : *entry = index;
4691 : : }
4692 : : }
4693 : :
4694 : 3669 : 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 : 3669 : latch_index = -1;
4711 : :
4712 : : /* Start walk in loop header with index set to infinite bound. */
4713 : 3669 : queue_index = bounds.length ();
4714 : 3669 : queues.safe_grow_cleared (queue_index + 1, true);
4715 : 3669 : queue.safe_push (loop->header);
4716 : 3669 : queues[queue_index] = queue;
4717 : 3669 : block_priority.put (loop->header, queue_index);
4718 : :
4719 : 14005 : for (; queue_index >= 0; queue_index--)
4720 : : {
4721 : 10336 : if (latch_index < queue_index)
4722 : : {
4723 : 40735 : while (queues[queue_index].length ())
4724 : : {
4725 : 36684 : basic_block bb;
4726 : 36684 : ptrdiff_t bound_index = queue_index;
4727 : 36684 : edge e;
4728 : 36684 : edge_iterator ei;
4729 : :
4730 : 36684 : queue = queues[queue_index];
4731 : 36684 : bb = queue.pop ();
4732 : :
4733 : : /* OK, we later inserted the BB with lower priority, skip it. */
4734 : 36684 : if (*block_priority.get (bb) > queue_index)
4735 : 0 : continue;
4736 : :
4737 : : /* See if we can improve the bound. */
4738 : 36684 : ptrdiff_t *entry = bb_bounds.get (bb);
4739 : 36684 : if (entry && *entry < bound_index)
4740 : 4201 : bound_index = *entry;
4741 : :
4742 : : /* Insert succesors into the queue, watch for latch edge
4743 : : and record greatest index we saw. */
4744 : 93806 : FOR_EACH_EDGE (e, ei, bb->succs)
4745 : : {
4746 : 57122 : bool insert = false;
4747 : :
4748 : 57122 : if (loop_exit_edge_p (loop, e))
4749 : 10344 : continue;
4750 : :
4751 : 46778 : if (e == loop_latch_edge (loop)
4752 : 46778 : && latch_index < bound_index)
4753 : : latch_index = bound_index;
4754 : 43109 : else if (!(entry = block_priority.get (e->dest)))
4755 : : {
4756 : 34285 : insert = true;
4757 : 34285 : block_priority.put (e->dest, bound_index);
4758 : : }
4759 : 8824 : else if (*entry < bound_index)
4760 : : {
4761 : 162 : insert = true;
4762 : 162 : *entry = bound_index;
4763 : : }
4764 : :
4765 : 34447 : if (insert)
4766 : 34447 : queues[bound_index].safe_push (e->dest);
4767 : : }
4768 : : }
4769 : : }
4770 : 10336 : queues[queue_index].release ();
4771 : : }
4772 : :
4773 : 3669 : gcc_assert (latch_index >= 0);
4774 : 3669 : if ((unsigned)latch_index < bounds.length ())
4775 : : {
4776 : 264 : 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 : 264 : record_niter_bound (loop, widest_int::from (bounds[latch_index],
4783 : : SIGNED), false, true);
4784 : : }
4785 : :
4786 : 3669 : queues.release ();
4787 : 6575041 : }
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 : 6575041 : maybe_lower_iteration_bound (class loop *loop)
4795 : : {
4796 : 6575041 : hash_set<gimple *> *not_executed_last_iteration = NULL;
4797 : 6575041 : class nb_iter_bound *elt;
4798 : 6575041 : bool found_exit = false;
4799 : 6575041 : auto_vec<basic_block> queue;
4800 : 6575041 : 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 : 16819807 : for (elt = loop->bounds; elt; elt = elt->next)
4810 : : {
4811 : 10244766 : if (!elt->is_exit
4812 : 10244766 : && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound))
4813 : : {
4814 : 2170280 : if (!not_executed_last_iteration)
4815 : 1184445 : not_executed_last_iteration = new hash_set<gimple *>;
4816 : 2170280 : not_executed_last_iteration->add (elt->stmt);
4817 : : }
4818 : : }
4819 : 6575041 : if (!not_executed_last_iteration)
4820 : 5390596 : 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 : 1184445 : queue.safe_push (loop->header);
4828 : 1184445 : visited = BITMAP_ALLOC (NULL);
4829 : 1184445 : bitmap_set_bit (visited, loop->header->index);
4830 : 1184445 : found_exit = false;
4831 : :
4832 : 1287828 : do
4833 : : {
4834 : 1287828 : basic_block bb = queue.pop ();
4835 : 1287828 : gimple_stmt_iterator gsi;
4836 : 1287828 : bool stmt_found = false;
4837 : :
4838 : : /* Loop for possible exits and statements bounding the execution. */
4839 : 6968212 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4840 : : {
4841 : 4460817 : gimple *stmt = gsi_stmt (gsi);
4842 : 4460817 : if (not_executed_last_iteration->contains (stmt))
4843 : : {
4844 : : stmt_found = true;
4845 : 68261 : break;
4846 : : }
4847 : 4416550 : if (gimple_has_side_effects (stmt))
4848 : : {
4849 : : found_exit = true;
4850 : : break;
4851 : : }
4852 : : }
4853 : 1287828 : if (found_exit)
4854 : : break;
4855 : :
4856 : : /* If no bounding statement is found, continue the walk. */
4857 : 1263834 : if (!stmt_found)
4858 : : {
4859 : 1219567 : edge e;
4860 : 1219567 : edge_iterator ei;
4861 : :
4862 : 2081171 : FOR_EACH_EDGE (e, ei, bb->succs)
4863 : : {
4864 : 1983817 : if (loop_exit_edge_p (loop, e)
4865 : 862156 : || e == loop_latch_edge (loop)
4866 : : /* When exiting an inner loop, verify it is finite. */
4867 : 862140 : || (!flow_bb_inside_loop_p (bb->loop_father, e->dest)
4868 : 11095 : && !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 : 2845421 : || (bb->flags & BB_IRREDUCIBLE_LOOP))
4873 : : {
4874 : : found_exit = true;
4875 : : break;
4876 : : }
4877 : 861604 : if (bitmap_set_bit (visited, e->dest->index))
4878 : 832758 : queue.safe_push (e->dest);
4879 : : }
4880 : : }
4881 : : }
4882 : 1263834 : 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 : 1184445 : if (!found_exit)
4889 : : {
4890 : 38238 : 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 : 76476 : record_niter_bound (loop, widest_int::from (loop->nb_iterations_upper_bound,
4894 : 114714 : SIGNED) - 1,
4895 : : false, true);
4896 : : }
4897 : :
4898 : 1184445 : BITMAP_FREE (visited);
4899 : 1184445 : delete not_executed_last_iteration;
4900 : 6575041 : }
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 : 5059848 : get_upper_bound_based_on_builtin_expr_with_prob (gcond *cond)
4907 : : {
4908 : 5059848 : if (cond == NULL)
4909 : : return NULL_TREE;
4910 : :
4911 : 4903578 : tree lhs = gimple_cond_lhs (cond);
4912 : 4903578 : if (TREE_CODE (lhs) != SSA_NAME)
4913 : : return NULL_TREE;
4914 : :
4915 : 4903506 : gimple *stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
4916 : 5244754 : gcall *def = dyn_cast<gcall *> (stmt);
4917 : 184908 : if (def == NULL)
4918 : : return NULL_TREE;
4919 : :
4920 : 184908 : tree decl = gimple_call_fndecl (def);
4921 : 184908 : if (!decl
4922 : 157266 : || !fndecl_built_in_p (decl, BUILT_IN_EXPECT_WITH_PROBABILITY)
4923 : 184912 : || 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 : 26515231 : estimate_numbers_of_iterations (class loop *loop)
4956 : : {
4957 : 26515231 : tree niter, type;
4958 : 26515231 : unsigned i;
4959 : 26515231 : class tree_niter_desc niter_desc;
4960 : 26515231 : edge ex;
4961 : 26515231 : widest_int bound;
4962 : 26515231 : edge likely_exit;
4963 : :
4964 : : /* Give up if we already have tried to compute an estimation. */
4965 : 26515231 : if (loop->estimate_state != EST_NOT_COMPUTED)
4966 : 19940190 : return;
4967 : :
4968 : 6575041 : if (dump_file && (dump_flags & TDF_DETAILS))
4969 : 13091 : fprintf (dump_file, "Estimating # of iterations of loop %d\n", loop->num);
4970 : :
4971 : 6575041 : loop->estimate_state = EST_AVAILABLE;
4972 : :
4973 : 6575041 : sreal nit;
4974 : 6575041 : 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 : 6575041 : if (!loop->any_estimate
4988 : 4535776 : && expected_loop_iterations_by_profile (loop, &nit, &reliable)
4989 : 10222900 : && reliable)
4990 : : {
4991 : 11 : bound = nit.to_nearest_int ();
4992 : 11 : 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 : 6575041 : number_of_latch_executions (loop);
4999 : :
5000 : 6575041 : basic_block *body = get_loop_body (loop);
5001 : 6575041 : auto_vec<edge> exits = get_loop_exit_edges (loop, body);
5002 : 6575041 : likely_exit = single_likely_exit (loop, exits);
5003 : 18919942 : FOR_EACH_VEC_ELT (exits, i, ex)
5004 : : {
5005 : 12344901 : if (ex == likely_exit)
5006 : : {
5007 : 5059848 : gimple *stmt = *gsi_last_bb (ex->src);
5008 : 5059848 : if (stmt != NULL)
5009 : : {
5010 : 5059848 : gcond *cond = dyn_cast<gcond *> (stmt);
5011 : 5059848 : tree niter_bound
5012 : 5059848 : = get_upper_bound_based_on_builtin_expr_with_prob (cond);
5013 : 5059848 : 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 : 12344901 : if (!number_of_iterations_exit (loop, ex, &niter_desc,
5023 : : false, false, body))
5024 : 7662231 : continue;
5025 : :
5026 : 4682670 : niter = niter_desc.niter;
5027 : 4682670 : type = TREE_TYPE (niter);
5028 : 4682670 : if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
5029 : 723436 : niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
5030 : : build_int_cst (type, 0),
5031 : : niter);
5032 : 4682670 : record_estimate (loop, niter, niter_desc.max,
5033 : : last_nondebug_stmt (ex->src),
5034 : : true, ex == likely_exit, true);
5035 : 4682670 : record_control_iv (loop, &niter_desc);
5036 : : }
5037 : :
5038 : 6575041 : if (flag_aggressive_loop_optimizations)
5039 : 6536633 : infer_loop_bounds_from_undefined (loop, body);
5040 : 6575041 : free (body);
5041 : :
5042 : 6575041 : discover_iteration_bound_by_body_walk (loop);
5043 : :
5044 : 6575041 : 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 : 6575041 : if (loop->nb_iterations
5050 : 6575041 : && TREE_CODE (loop->nb_iterations) == INTEGER_CST
5051 : 13150082 : && (wi::min_precision (wi::to_widest (loop->nb_iterations), SIGNED)
5052 : 1970784 : <= bound_wide_int ().get_precision ()))
5053 : : {
5054 : 1970784 : loop->any_upper_bound = true;
5055 : 1970784 : loop->nb_iterations_upper_bound
5056 : 1970784 : = bound_wide_int::from (wi::to_widest (loop->nb_iterations), SIGNED);
5057 : : }
5058 : 26515231 : }
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 : 9185854 : 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 : 9185854 : if (scev_initialized_p ())
5071 : 9185854 : estimate_numbers_of_iterations (loop);
5072 : :
5073 : 9185854 : 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 : 8924990 : estimated_loop_iterations_int (class loop *loop)
5082 : : {
5083 : 8924990 : widest_int nit;
5084 : 8924990 : HOST_WIDE_INT hwi_nit;
5085 : :
5086 : 8924990 : if (!estimated_loop_iterations (loop, &nit))
5087 : : return -1;
5088 : :
5089 : 3833826 : if (!wi::fits_shwi_p (nit))
5090 : : return -1;
5091 : 3833820 : hwi_nit = nit.to_shwi ();
5092 : :
5093 : 3833820 : return hwi_nit < 0 ? -1 : hwi_nit;
5094 : 8924990 : }
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 : 8952771 : 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 : 8952771 : if (scev_initialized_p ())
5107 : 8938963 : estimate_numbers_of_iterations (loop);
5108 : :
5109 : 8952771 : 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 : 2274271 : max_loop_iterations_int (class loop *loop)
5118 : : {
5119 : 2274271 : widest_int nit;
5120 : 2274271 : HOST_WIDE_INT hwi_nit;
5121 : :
5122 : 2274271 : if (!max_loop_iterations (loop, &nit))
5123 : : return -1;
5124 : :
5125 : 1685038 : if (!wi::fits_shwi_p (nit))
5126 : : return -1;
5127 : 1606824 : hwi_nit = nit.to_shwi ();
5128 : :
5129 : 1606824 : return hwi_nit < 0 ? -1 : hwi_nit;
5130 : 2274271 : }
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 : 356635 : 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 : 356635 : if (scev_initialized_p ())
5142 : 356635 : estimate_numbers_of_iterations (loop);
5143 : :
5144 : 356635 : 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 : 104287 : likely_max_loop_iterations_int (class loop *loop)
5153 : : {
5154 : 104287 : widest_int nit;
5155 : 104287 : HOST_WIDE_INT hwi_nit;
5156 : :
5157 : 104287 : if (!likely_max_loop_iterations (loop, &nit))
5158 : : return -1;
5159 : :
5160 : 84006 : if (!wi::fits_shwi_p (nit))
5161 : : return -1;
5162 : 77277 : hwi_nit = nit.to_shwi ();
5163 : :
5164 : 77277 : return hwi_nit < 0 ? -1 : hwi_nit;
5165 : 104287 : }
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 : 8757096 : estimated_stmt_executions_int (class loop *loop)
5173 : : {
5174 : 8757096 : HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
5175 : 8757096 : HOST_WIDE_INT snit;
5176 : :
5177 : 8757096 : if (nit == -1)
5178 : : return -1;
5179 : :
5180 : 3770415 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
5181 : :
5182 : : /* If the computation overflows, return -1. */
5183 : 3770415 : 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 : 252348 : likely_max_stmt_executions (class loop *loop, widest_int *nit)
5211 : : {
5212 : 252348 : widest_int nit_minus_one;
5213 : :
5214 : 252348 : if (!likely_max_loop_iterations (loop, nit))
5215 : : return false;
5216 : :
5217 : 143737 : nit_minus_one = *nit;
5218 : :
5219 : 143737 : *nit += 1;
5220 : :
5221 : 143737 : return wi::gtu_p (*nit, nit_minus_one);
5222 : 252348 : }
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 : 260864 : estimated_stmt_executions (class loop *loop, widest_int *nit)
5230 : : {
5231 : 260864 : widest_int nit_minus_one;
5232 : :
5233 : 260864 : if (!estimated_loop_iterations (loop, nit))
5234 : : return false;
5235 : :
5236 : 7269 : nit_minus_one = *nit;
5237 : :
5238 : 7269 : *nit += 1;
5239 : :
5240 : 7269 : return wi::gtu_p (*nit, nit_minus_one);
5241 : 260864 : }
5242 : :
5243 : : /* Records estimates on numbers of iterations of loops. */
5244 : :
5245 : : void
5246 : 1228116 : estimate_numbers_of_iterations (function *fn)
5247 : : {
5248 : : /* We don't want to issue signed overflow warnings while getting
5249 : : loop iteration estimates. */
5250 : 1228116 : fold_defer_overflow_warnings ();
5251 : :
5252 : 7414492 : for (auto loop : loops_list (fn, 0))
5253 : 3730144 : estimate_numbers_of_iterations (loop);
5254 : :
5255 : 1228116 : fold_undefer_and_ignore_overflow_warnings ();
5256 : 1228116 : }
5257 : :
5258 : : /* Returns true if statement S1 dominates statement S2. */
5259 : :
5260 : : bool
5261 : 2300270 : stmt_dominates_stmt_p (gimple *s1, gimple *s2)
5262 : : {
5263 : 2300270 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
5264 : :
5265 : 2300270 : if (!bb1
5266 : 2300270 : || s1 == s2)
5267 : : return true;
5268 : :
5269 : 2292512 : if (bb1 == bb2)
5270 : : {
5271 : 852730 : gimple_stmt_iterator bsi;
5272 : :
5273 : 852730 : if (gimple_code (s2) == GIMPLE_PHI)
5274 : : return false;
5275 : :
5276 : 538804 : if (gimple_code (s1) == GIMPLE_PHI)
5277 : : return true;
5278 : :
5279 : 19352197 : for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
5280 : 18537060 : if (gsi_stmt (bsi) == s1)
5281 : : return true;
5282 : :
5283 : : return false;
5284 : : }
5285 : :
5286 : 1439782 : 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 : 2463435 : n_of_executions_at_most (gimple *stmt,
5304 : : class nb_iter_bound *niter_bound,
5305 : : tree niter)
5306 : : {
5307 : 2463435 : widest_int bound = widest_int::from (niter_bound->bound, SIGNED);
5308 : 2463435 : tree nit_type = TREE_TYPE (niter), e;
5309 : 2463435 : enum tree_code cmp;
5310 : :
5311 : 2463435 : 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 : 2463435 : 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 : 2300270 : if (niter_bound->is_exit)
5335 : : {
5336 : 867499 : if (stmt == niter_bound->stmt
5337 : 867499 : || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
5338 : 746882 : return false;
5339 : : cmp = GE_EXPR;
5340 : : }
5341 : : else
5342 : : {
5343 : 1432771 : if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
5344 : : {
5345 : 584414 : gimple_stmt_iterator bsi;
5346 : 584414 : if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
5347 : 246186 : || gimple_code (stmt) == GIMPLE_PHI
5348 : 768439 : || gimple_code (niter_bound->stmt) == GIMPLE_PHI)
5349 : 405622 : 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 : 7922220 : for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
5355 : 7738195 : gsi_next (&bsi))
5356 : 7738943 : if (gimple_has_side_effects (gsi_stmt (bsi)))
5357 : : return false;
5358 : 183277 : bound += 1;
5359 : 362069 : if (bound == 0
5360 : 183277 : || !wi::fits_to_tree_p (bound, nit_type))
5361 : 4485 : return false;
5362 : : }
5363 : : cmp = GT_EXPR;
5364 : : }
5365 : :
5366 : 1147766 : e = fold_binary (cmp, boolean_type_node,
5367 : : niter, wide_int_to_tree (nit_type, bound));
5368 : 1147766 : return e && integer_nonzerop (e);
5369 : 2463435 : }
5370 : :
5371 : : /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
5372 : :
5373 : : bool
5374 : 80773938 : nowrap_type_p (tree type)
5375 : : {
5376 : 11760176 : if (ANY_INTEGRAL_TYPE_P (type)
5377 : 80773938 : && TYPE_OVERFLOW_UNDEFINED (type))
5378 : : return true;
5379 : :
5380 : 41813332 : if (POINTER_TYPE_P (type))
5381 : 11760176 : 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 : 3565817 : loop_exits_before_overflow (tree base, tree step,
5391 : : gimple *at_stmt, class loop *loop)
5392 : : {
5393 : 3565817 : widest_int niter;
5394 : 3565817 : struct control_iv *civ;
5395 : 3565817 : class nb_iter_bound *bound;
5396 : 3565817 : tree e, delta, step_abs, unsigned_base;
5397 : 3565817 : tree type = TREE_TYPE (step);
5398 : 3565817 : tree unsigned_type, valid_niter;
5399 : :
5400 : : /* Don't issue signed overflow warnings. */
5401 : 3565817 : 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 : 3565817 : unsigned_type = unsigned_type_for (type);
5406 : 3565817 : unsigned_base = fold_convert (unsigned_type, base);
5407 : :
5408 : 3565817 : if (tree_int_cst_sign_bit (step))
5409 : : {
5410 : 598940 : tree extreme = fold_convert (unsigned_type,
5411 : : lower_bound_in_type (type, type));
5412 : 598940 : delta = fold_build2 (MINUS_EXPR, unsigned_type, unsigned_base, extreme);
5413 : 598940 : step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
5414 : : fold_convert (unsigned_type, step));
5415 : : }
5416 : : else
5417 : : {
5418 : 2966877 : tree extreme = fold_convert (unsigned_type,
5419 : : upper_bound_in_type (type, type));
5420 : 2966877 : delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, unsigned_base);
5421 : 2966877 : step_abs = fold_convert (unsigned_type, step);
5422 : : }
5423 : :
5424 : 3565817 : valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
5425 : :
5426 : 3565817 : estimate_numbers_of_iterations (loop);
5427 : :
5428 : 3565817 : if (max_loop_iterations (loop, &niter)
5429 : 2887797 : && wi::fits_to_tree_p (niter, TREE_TYPE (valid_niter))
5430 : 2708143 : && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
5431 : : wide_int_to_tree (TREE_TYPE (valid_niter),
5432 : : niter))) != NULL
5433 : 6187566 : && integer_nonzerop (e))
5434 : : {
5435 : 1085201 : fold_undefer_and_ignore_overflow_warnings ();
5436 : 1085201 : return true;
5437 : : }
5438 : 2480616 : if (at_stmt)
5439 : 3895364 : for (bound = loop->bounds; bound; bound = bound->next)
5440 : : {
5441 : 2463435 : if (n_of_executions_at_most (at_stmt, bound, valid_niter))
5442 : : {
5443 : 14410 : fold_undefer_and_ignore_overflow_warnings ();
5444 : 14410 : return true;
5445 : : }
5446 : : }
5447 : 2466206 : 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 : 2466206 : if (TREE_CODE (step) == INTEGER_CST)
5453 : : {
5454 : 3611344 : for (civ = loop->control_ivs; civ; civ = civ->next)
5455 : : {
5456 : 1347618 : enum tree_code code;
5457 : 1347618 : tree civ_type = TREE_TYPE (civ->step);
5458 : :
5459 : : /* Have to consider type difference because operand_equal_p ignores
5460 : : that for constants. */
5461 : 1347618 : if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type)
5462 : 1347618 : || element_precision (type) != element_precision (civ_type))
5463 : 765452 : continue;
5464 : :
5465 : : /* Only consider control IV with same step. */
5466 : 582166 : if (!operand_equal_p (step, civ->step, 0))
5467 : 207255 : continue;
5468 : :
5469 : : /* Done proving if this is a no-overflow control IV. */
5470 : 374911 : 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 : 254592 : tree expanded_base = expand_simple_operations (base);
5476 : 254592 : 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 : 220349 : if (POINTER_TYPE_P (TREE_TYPE (base)))
5494 : : code = POINTER_PLUS_EXPR;
5495 : : else
5496 : : code = PLUS_EXPR;
5497 : :
5498 : 220349 : tree stepped = fold_build2 (code, TREE_TYPE (base), base, step);
5499 : 220349 : tree expanded_stepped = fold_build2 (code, TREE_TYPE (base),
5500 : : expanded_base, step);
5501 : 220349 : if (operand_equal_p (stepped, civ->base, 0)
5502 : 220349 : || operand_equal_p (expanded_stepped, civ->base, 0))
5503 : : {
5504 : 58035 : tree extreme;
5505 : :
5506 : 58035 : if (tree_int_cst_sign_bit (step))
5507 : : {
5508 : 16817 : code = LT_EXPR;
5509 : 16817 : extreme = lower_bound_in_type (type, type);
5510 : : }
5511 : : else
5512 : : {
5513 : 41218 : code = GT_EXPR;
5514 : 41218 : extreme = upper_bound_in_type (type, type);
5515 : : }
5516 : 58035 : extreme = fold_build2 (MINUS_EXPR, type, extreme, step);
5517 : 58035 : e = fold_build2 (code, boolean_type_node, base, extreme);
5518 : 58035 : e = simplify_using_initial_conditions (loop, e);
5519 : 58035 : if (integer_zerop (e))
5520 : : return true;
5521 : : }
5522 : : }
5523 : : }
5524 : :
5525 : : return false;
5526 : 3565817 : }
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 : 355809 : scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
5584 : : {
5585 : 355809 : tree type;
5586 : 355809 : wide_int minv, maxv, diff, step_wi;
5587 : :
5588 : 355809 : 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 : 355809 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
5594 : 355809 : if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
5595 : 2773 : return false;
5596 : :
5597 : 353036 : int_range_max r (TREE_TYPE (var));
5598 : 706072 : get_range_query (cfun)->range_of_expr (r, var);
5599 : 353036 : 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 : 113737 : step_wi = wi::to_wide (step);
5610 : 113737 : type = TREE_TYPE (var);
5611 : 113737 : if (tree_int_cst_sign_bit (step))
5612 : : {
5613 : 10909 : diff = r.lower_bound () - wi::to_wide (lower_bound_in_type (type, type));
5614 : 10909 : step_wi = - step_wi;
5615 : : }
5616 : : else
5617 : 102828 : diff = wi::to_wide (upper_bound_in_type (type, type)) - r.upper_bound ();
5618 : :
5619 : 113737 : return (wi::geu_p (diff, step_wi));
5620 : 708845 : }
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 : 7878129 : 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 : 7878129 : if (chrec_contains_undetermined (base)
5657 : 7878129 : || chrec_contains_undetermined (step))
5658 : 0 : return true;
5659 : :
5660 : 7878129 : 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 : 7878129 : 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 : 4116798 : if (TREE_CODE (step) != INTEGER_CST)
5671 : : return true;
5672 : :
5673 : : /* Check if var can be proven not overflow with value range info. */
5674 : 357408 : if (var && TREE_CODE (var) == SSA_NAME
5675 : 4023564 : && scev_var_range_cant_overflow (var, step, loop))
5676 : : return false;
5677 : :
5678 : 3565817 : 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 : 2263726 : 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 : 57665538 : free_numbers_of_iterations_estimates (class loop *loop)
5695 : : {
5696 : 57665538 : struct control_iv *civ;
5697 : 57665538 : class nb_iter_bound *bound;
5698 : :
5699 : 57665538 : loop->nb_iterations = NULL;
5700 : 57665538 : loop->estimate_state = EST_NOT_COMPUTED;
5701 : 67633019 : for (bound = loop->bounds; bound;)
5702 : : {
5703 : 9967481 : class nb_iter_bound *next = bound->next;
5704 : 9967481 : ggc_free (bound);
5705 : 9967481 : bound = next;
5706 : : }
5707 : 57665538 : loop->bounds = NULL;
5708 : :
5709 : 62060320 : for (civ = loop->control_ivs; civ;)
5710 : : {
5711 : 4394782 : struct control_iv *next = civ->next;
5712 : 4394782 : ggc_free (civ);
5713 : 4394782 : civ = next;
5714 : : }
5715 : 57665538 : loop->control_ivs = NULL;
5716 : 57665538 : }
5717 : :
5718 : : /* Frees the information on upper bounds on numbers of iterations of loops. */
5719 : :
5720 : : void
5721 : 72595254 : free_numbers_of_iterations_estimates (function *fn)
5722 : : {
5723 : 274052126 : for (auto loop : loops_list (fn, 0))
5724 : 56266364 : free_numbers_of_iterations_estimates (loop);
5725 : 72595254 : }
5726 : :
5727 : : /* Substitute value VAL for ssa name NAME inside expressions held
5728 : : at LOOP. */
5729 : :
5730 : : void
5731 : 116606466 : substitute_in_loop_info (class loop *loop, tree name, tree val)
5732 : : {
5733 : 116606466 : loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
5734 : 116606466 : }
|
