OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-ssa-loop-niter.c] - Blame information for rev 816

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Functions to determine/estimate number of iterations of a loop.
2
   Copyright (C) 2004, 2005, 2006, 2007 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 "tm.h"
24
#include "tree.h"
25
#include "rtl.h"
26
#include "tm_p.h"
27
#include "hard-reg-set.h"
28
#include "basic-block.h"
29
#include "output.h"
30
#include "diagnostic.h"
31
#include "intl.h"
32
#include "tree-flow.h"
33
#include "tree-dump.h"
34
#include "cfgloop.h"
35
#include "tree-pass.h"
36
#include "ggc.h"
37
#include "tree-chrec.h"
38
#include "tree-scalar-evolution.h"
39
#include "tree-data-ref.h"
40
#include "params.h"
41
#include "flags.h"
42
#include "toplev.h"
43
#include "tree-inline.h"
44
 
45
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
46
 
47
 
48
/*
49
 
50
   Analysis of number of iterations of an affine exit test.
51
 
52
*/
53
 
54
/* Returns true if ARG is either NULL_TREE or constant zero.  Unlike
55
   integer_zerop, it does not care about overflow flags.  */
56
 
57
bool
58
zero_p (tree arg)
59
{
60
  if (!arg)
61
    return true;
62
 
63
  if (TREE_CODE (arg) != INTEGER_CST)
64
    return false;
65
 
66
  return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
67
}
68
 
69
/* Returns true if ARG a nonzero constant.  Unlike integer_nonzerop, it does
70
   not care about overflow flags.  */
71
 
72
static bool
73
nonzero_p (tree arg)
74
{
75
  if (!arg)
76
    return false;
77
 
78
  if (TREE_CODE (arg) != INTEGER_CST)
79
    return false;
80
 
81
  return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
82
}
83
 
84
/* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
85
 
86
static tree
87
inverse (tree x, tree mask)
88
{
89
  tree type = TREE_TYPE (x);
90
  tree rslt;
91
  unsigned ctr = tree_floor_log2 (mask);
92
 
93
  if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
94
    {
95
      unsigned HOST_WIDE_INT ix;
96
      unsigned HOST_WIDE_INT imask;
97
      unsigned HOST_WIDE_INT irslt = 1;
98
 
99
      gcc_assert (cst_and_fits_in_hwi (x));
100
      gcc_assert (cst_and_fits_in_hwi (mask));
101
 
102
      ix = int_cst_value (x);
103
      imask = int_cst_value (mask);
104
 
105
      for (; ctr; ctr--)
106
        {
107
          irslt *= ix;
108
          ix *= ix;
109
        }
110
      irslt &= imask;
111
 
112
      rslt = build_int_cst_type (type, irslt);
113
    }
114
  else
115
    {
116
      rslt = build_int_cst (type, 1);
117
      for (; ctr; ctr--)
118
        {
119
          rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
120
          x = int_const_binop (MULT_EXPR, x, x, 0);
121
        }
122
      rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
123
    }
124
 
125
  return rslt;
126
}
127
 
128
/* Determines number of iterations of loop whose ending condition
129
   is IV <> FINAL.  TYPE is the type of the iv.  The number of
130
   iterations is stored to NITER.  NEVER_INFINITE is true if
131
   we know that the exit must be taken eventually, i.e., that the IV
132
   ever reaches the value FINAL (we derived this earlier, and possibly set
133
   NITER->assumptions to make sure this is the case).  */
134
 
135
static bool
136
number_of_iterations_ne (tree type, affine_iv *iv, tree final,
137
                         struct tree_niter_desc *niter, bool never_infinite)
138
{
139
  tree niter_type = unsigned_type_for (type);
140
  tree s, c, d, bits, assumption, tmp, bound;
141
 
142
  niter->control = *iv;
143
  niter->bound = final;
144
  niter->cmp = NE_EXPR;
145
 
146
  /* Rearrange the terms so that we get inequality s * i <> c, with s
147
     positive.  Also cast everything to the unsigned type.  */
148
  if (tree_int_cst_sign_bit (iv->step))
149
    {
150
      s = fold_convert (niter_type,
151
                        fold_build1 (NEGATE_EXPR, type, iv->step));
152
      c = fold_build2 (MINUS_EXPR, niter_type,
153
                       fold_convert (niter_type, iv->base),
154
                       fold_convert (niter_type, final));
155
    }
156
  else
157
    {
158
      s = fold_convert (niter_type, iv->step);
159
      c = fold_build2 (MINUS_EXPR, niter_type,
160
                       fold_convert (niter_type, final),
161
                       fold_convert (niter_type, iv->base));
162
    }
163
 
164
  /* First the trivial cases -- when the step is 1.  */
165
  if (integer_onep (s))
166
    {
167
      niter->niter = c;
168
      return true;
169
    }
170
 
171
  /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
172
     is infinite.  Otherwise, the number of iterations is
173
     (inverse(s/d) * (c/d)) mod (size of mode/d).  */
174
  bits = num_ending_zeros (s);
175
  bound = build_low_bits_mask (niter_type,
176
                               (TYPE_PRECISION (niter_type)
177
                                - tree_low_cst (bits, 1)));
178
 
179
  d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
180
                               build_int_cst (niter_type, 1), bits);
181
  s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
182
 
183
  if (!never_infinite)
184
    {
185
      /* If we cannot assume that the loop is not infinite, record the
186
         assumptions for divisibility of c.  */
187
      assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
188
      assumption = fold_build2 (EQ_EXPR, boolean_type_node,
189
                                assumption, build_int_cst (niter_type, 0));
190
      if (!nonzero_p (assumption))
191
        niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
192
                                          niter->assumptions, assumption);
193
    }
194
 
195
  c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
196
  tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
197
  niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
198
  return true;
199
}
200
 
201
/* Checks whether we can determine the final value of the control variable
202
   of the loop with ending condition IV0 < IV1 (computed in TYPE).
203
   DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
204
   of the step.  The assumptions necessary to ensure that the computation
205
   of the final value does not overflow are recorded in NITER.  If we
206
   find the final value, we adjust DELTA and return TRUE.  Otherwise
207
   we return false.  */
208
 
209
static bool
210
number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
211
                               struct tree_niter_desc *niter,
212
                               tree *delta, tree step)
213
{
214
  tree niter_type = TREE_TYPE (step);
215
  tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
216
  tree tmod;
217
  tree assumption = boolean_true_node, bound, noloop;
218
 
219
  if (TREE_CODE (mod) != INTEGER_CST)
220
    return false;
221
  if (nonzero_p (mod))
222
    mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
223
  tmod = fold_convert (type, mod);
224
 
225
  if (nonzero_p (iv0->step))
226
    {
227
      /* The final value of the iv is iv1->base + MOD, assuming that this
228
         computation does not overflow, and that
229
         iv0->base <= iv1->base + MOD.  */
230
      if (!iv1->no_overflow && !zero_p (mod))
231
        {
232
          bound = fold_build2 (MINUS_EXPR, type,
233
                               TYPE_MAX_VALUE (type), tmod);
234
          assumption = fold_build2 (LE_EXPR, boolean_type_node,
235
                                    iv1->base, bound);
236
          if (zero_p (assumption))
237
            return false;
238
        }
239
      noloop = fold_build2 (GT_EXPR, boolean_type_node,
240
                            iv0->base,
241
                            fold_build2 (PLUS_EXPR, type,
242
                                         iv1->base, tmod));
243
    }
244
  else
245
    {
246
      /* The final value of the iv is iv0->base - MOD, assuming that this
247
         computation does not overflow, and that
248
         iv0->base - MOD <= iv1->base. */
249
      if (!iv0->no_overflow && !zero_p (mod))
250
        {
251
          bound = fold_build2 (PLUS_EXPR, type,
252
                               TYPE_MIN_VALUE (type), tmod);
253
          assumption = fold_build2 (GE_EXPR, boolean_type_node,
254
                                    iv0->base, bound);
255
          if (zero_p (assumption))
256
            return false;
257
        }
258
      noloop = fold_build2 (GT_EXPR, boolean_type_node,
259
                            fold_build2 (MINUS_EXPR, type,
260
                                         iv0->base, tmod),
261
                            iv1->base);
262
    }
263
 
264
  if (!nonzero_p (assumption))
265
    niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
266
                                      niter->assumptions,
267
                                      assumption);
268
  if (!zero_p (noloop))
269
    niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
270
                                      niter->may_be_zero,
271
                                      noloop);
272
  *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
273
  return true;
274
}
275
 
276
/* Add assertions to NITER that ensure that the control variable of the loop
277
   with ending condition IV0 < IV1 does not overflow.  Types of IV0 and IV1
278
   are TYPE.  Returns false if we can prove that there is an overflow, true
279
   otherwise.  STEP is the absolute value of the step.  */
280
 
281
static bool
282
assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
283
                       struct tree_niter_desc *niter, tree step)
284
{
285
  tree bound, d, assumption, diff;
286
  tree niter_type = TREE_TYPE (step);
287
 
288
  if (nonzero_p (iv0->step))
289
    {
290
      /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
291
      if (iv0->no_overflow)
292
        return true;
293
 
294
      /* If iv0->base is a constant, we can determine the last value before
295
         overflow precisely; otherwise we conservatively assume
296
         MAX - STEP + 1.  */
297
 
298
      if (TREE_CODE (iv0->base) == INTEGER_CST)
299
        {
300
          d = fold_build2 (MINUS_EXPR, niter_type,
301
                           fold_convert (niter_type, TYPE_MAX_VALUE (type)),
302
                           fold_convert (niter_type, iv0->base));
303
          diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
304
        }
305
      else
306
        diff = fold_build2 (MINUS_EXPR, niter_type, step,
307
                            build_int_cst (niter_type, 1));
308
      bound = fold_build2 (MINUS_EXPR, type,
309
                           TYPE_MAX_VALUE (type), fold_convert (type, diff));
310
      assumption = fold_build2 (LE_EXPR, boolean_type_node,
311
                                iv1->base, bound);
312
    }
313
  else
314
    {
315
      /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
316
      if (iv1->no_overflow)
317
        return true;
318
 
319
      if (TREE_CODE (iv1->base) == INTEGER_CST)
320
        {
321
          d = fold_build2 (MINUS_EXPR, niter_type,
322
                           fold_convert (niter_type, iv1->base),
323
                           fold_convert (niter_type, TYPE_MIN_VALUE (type)));
324
          diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
325
        }
326
      else
327
        diff = fold_build2 (MINUS_EXPR, niter_type, step,
328
                            build_int_cst (niter_type, 1));
329
      bound = fold_build2 (PLUS_EXPR, type,
330
                           TYPE_MIN_VALUE (type), fold_convert (type, diff));
331
      assumption = fold_build2 (GE_EXPR, boolean_type_node,
332
                                iv0->base, bound);
333
    }
334
 
335
  if (zero_p (assumption))
336
    return false;
337
  if (!nonzero_p (assumption))
338
    niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
339
                                      niter->assumptions, assumption);
340
 
341
  iv0->no_overflow = true;
342
  iv1->no_overflow = true;
343
  return true;
344
}
345
 
346
/* Add an assumption to NITER that a loop whose ending condition
347
   is IV0 < IV1 rolls.  TYPE is the type of the control iv.  */
348
 
349
static void
350
assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
351
                      struct tree_niter_desc *niter)
352
{
353
  tree assumption = boolean_true_node, bound, diff;
354
  tree mbz, mbzl, mbzr;
355
 
356
  if (nonzero_p (iv0->step))
357
    {
358
      diff = fold_build2 (MINUS_EXPR, type,
359
                          iv0->step, build_int_cst (type, 1));
360
 
361
      /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
362
 
363
         pointers.  */
364
      if (!POINTER_TYPE_P (type))
365
        {
366
          bound = fold_build2 (PLUS_EXPR, type,
367
                               TYPE_MIN_VALUE (type), diff);
368
          assumption = fold_build2 (GE_EXPR, boolean_type_node,
369
                                    iv0->base, bound);
370
        }
371
 
372
      /* And then we can compute iv0->base - diff, and compare it with
373
         iv1->base.  */
374
      mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
375
      mbzr = iv1->base;
376
    }
377
  else
378
    {
379
      diff = fold_build2 (PLUS_EXPR, type,
380
                          iv1->step, build_int_cst (type, 1));
381
 
382
      if (!POINTER_TYPE_P (type))
383
        {
384
          bound = fold_build2 (PLUS_EXPR, type,
385
                               TYPE_MAX_VALUE (type), diff);
386
          assumption = fold_build2 (LE_EXPR, boolean_type_node,
387
                                    iv1->base, bound);
388
        }
389
 
390
      mbzl = iv0->base;
391
      mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
392
    }
393
 
394
  mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
395
 
396
  if (!nonzero_p (assumption))
397
    niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
398
                                      niter->assumptions, assumption);
399
  if (!zero_p (mbz))
400
    niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
401
                                      niter->may_be_zero, mbz);
402
}
403
 
404
/* Determines number of iterations of loop whose ending condition
405
   is IV0 < IV1.  TYPE is the type of the iv.  The number of
406
   iterations is stored to NITER.  */
407
 
408
static bool
409
number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
410
                         struct tree_niter_desc *niter,
411
                         bool never_infinite ATTRIBUTE_UNUSED)
412
{
413
  tree niter_type = unsigned_type_for (type);
414
  tree delta, step, s;
415
 
416
  if (nonzero_p (iv0->step))
417
    {
418
      niter->control = *iv0;
419
      niter->cmp = LT_EXPR;
420
      niter->bound = iv1->base;
421
    }
422
  else
423
    {
424
      niter->control = *iv1;
425
      niter->cmp = GT_EXPR;
426
      niter->bound = iv0->base;
427
    }
428
 
429
  delta = fold_build2 (MINUS_EXPR, niter_type,
430
                       fold_convert (niter_type, iv1->base),
431
                       fold_convert (niter_type, iv0->base));
432
 
433
  /* First handle the special case that the step is +-1.  */
434
  if ((iv0->step && integer_onep (iv0->step)
435
       && zero_p (iv1->step))
436
      || (iv1->step && integer_all_onesp (iv1->step)
437
          && zero_p (iv0->step)))
438
    {
439
      /* for (i = iv0->base; i < iv1->base; i++)
440
 
441
         or
442
 
443
         for (i = iv1->base; i > iv0->base; i--).
444
 
445
         In both cases # of iterations is iv1->base - iv0->base, assuming that
446
         iv1->base >= iv0->base.  */
447
      niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
448
                                        iv1->base, iv0->base);
449
      niter->niter = delta;
450
      return true;
451
    }
452
 
453
  if (nonzero_p (iv0->step))
454
    step = fold_convert (niter_type, iv0->step);
455
  else
456
    step = fold_convert (niter_type,
457
                         fold_build1 (NEGATE_EXPR, type, iv1->step));
458
 
459
  /* If we can determine the final value of the control iv exactly, we can
460
     transform the condition to != comparison.  In particular, this will be
461
     the case if DELTA is constant.  */
462
  if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
463
    {
464
      affine_iv zps;
465
 
466
      zps.base = build_int_cst (niter_type, 0);
467
      zps.step = step;
468
      /* number_of_iterations_lt_to_ne will add assumptions that ensure that
469
         zps does not overflow.  */
470
      zps.no_overflow = true;
471
 
472
      return number_of_iterations_ne (type, &zps, delta, niter, true);
473
    }
474
 
475
  /* Make sure that the control iv does not overflow.  */
476
  if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
477
    return false;
478
 
479
  /* We determine the number of iterations as (delta + step - 1) / step.  For
480
     this to work, we must know that iv1->base >= iv0->base - step + 1,
481
     otherwise the loop does not roll.  */
482
  assert_loop_rolls_lt (type, iv0, iv1, niter);
483
 
484
  s = fold_build2 (MINUS_EXPR, niter_type,
485
                   step, build_int_cst (niter_type, 1));
486
  delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
487
  niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
488
  return true;
489
}
490
 
491
/* Determines number of iterations of loop whose ending condition
492
   is IV0 <= IV1.  TYPE is the type of the iv.  The number of
493
   iterations is stored to NITER.  NEVER_INFINITE is true if
494
   we know that this condition must eventually become false (we derived this
495
   earlier, and possibly set NITER->assumptions to make sure this
496
   is the case).  */
497
 
498
static bool
499
number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
500
                         struct tree_niter_desc *niter, bool never_infinite)
501
{
502
  tree assumption;
503
 
504
  /* Say that IV0 is the control variable.  Then IV0 <= IV1 iff
505
     IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
506
     value of the type.  This we must know anyway, since if it is
507
     equal to this value, the loop rolls forever.  */
508
 
509
  if (!never_infinite)
510
    {
511
      if (nonzero_p (iv0->step))
512
        assumption = fold_build2 (NE_EXPR, boolean_type_node,
513
                                  iv1->base, TYPE_MAX_VALUE (type));
514
      else
515
        assumption = fold_build2 (NE_EXPR, boolean_type_node,
516
                                  iv0->base, TYPE_MIN_VALUE (type));
517
 
518
      if (zero_p (assumption))
519
        return false;
520
      if (!nonzero_p (assumption))
521
        niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
522
                                          niter->assumptions, assumption);
523
    }
524
 
525
  if (nonzero_p (iv0->step))
526
    iv1->base = fold_build2 (PLUS_EXPR, type,
527
                             iv1->base, build_int_cst (type, 1));
528
  else
529
    iv0->base = fold_build2 (MINUS_EXPR, type,
530
                             iv0->base, build_int_cst (type, 1));
531
  return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
532
}
533
 
534
/* Determine the number of iterations according to condition (for staying
535
   inside loop) which compares two induction variables using comparison
536
   operator CODE.  The induction variable on left side of the comparison
537
   is IV0, the right-hand side is IV1.  Both induction variables must have
538
   type TYPE, which must be an integer or pointer type.  The steps of the
539
   ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
540
 
541
   ONLY_EXIT is true if we are sure this is the only way the loop could be
542
   exited (including possibly non-returning function calls, exceptions, etc.)
543
   -- in this case we can use the information whether the control induction
544
   variables can overflow or not in a more efficient way.
545
 
546
   The results (number of iterations and assumptions as described in
547
   comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
548
   Returns false if it fails to determine number of iterations, true if it
549
   was determined (possibly with some assumptions).  */
550
 
551
static bool
552
number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
553
                           affine_iv *iv1, struct tree_niter_desc *niter,
554
                           bool only_exit)
555
{
556
  bool never_infinite;
557
 
558
  /* The meaning of these assumptions is this:
559
     if !assumptions
560
       then the rest of information does not have to be valid
561
     if may_be_zero then the loop does not roll, even if
562
       niter != 0.  */
563
  niter->assumptions = boolean_true_node;
564
  niter->may_be_zero = boolean_false_node;
565
  niter->niter = NULL_TREE;
566
  niter->additional_info = boolean_true_node;
567
 
568
  niter->bound = NULL_TREE;
569
  niter->cmp = ERROR_MARK;
570
 
571
  /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
572
     the control variable is on lhs.  */
573
  if (code == GE_EXPR || code == GT_EXPR
574
      || (code == NE_EXPR && zero_p (iv0->step)))
575
    {
576
      SWAP (iv0, iv1);
577
      code = swap_tree_comparison (code);
578
    }
579
 
580
  if (!only_exit)
581
    {
582
      /* If this is not the only possible exit from the loop, the information
583
         that the induction variables cannot overflow as derived from
584
         signedness analysis cannot be relied upon.  We use them e.g. in the
585
         following way:  given loop for (i = 0; i <= n; i++), if i is
586
         signed, it cannot overflow, thus this loop is equivalent to
587
         for (i = 0; i < n + 1; i++);  however, if n == MAX, but the loop
588
         is exited in some other way before i overflows, this transformation
589
         is incorrect (the new loop exits immediately).  */
590
      iv0->no_overflow = false;
591
      iv1->no_overflow = false;
592
    }
593
 
594
  if (POINTER_TYPE_P (type))
595
    {
596
      /* Comparison of pointers is undefined unless both iv0 and iv1 point
597
         to the same object.  If they do, the control variable cannot wrap
598
         (as wrap around the bounds of memory will never return a pointer
599
         that would be guaranteed to point to the same object, even if we
600
         avoid undefined behavior by casting to size_t and back).  The
601
         restrictions on pointer arithmetics and comparisons of pointers
602
         ensure that using the no-overflow assumptions is correct in this
603
         case even if ONLY_EXIT is false.  */
604
      iv0->no_overflow = true;
605
      iv1->no_overflow = true;
606
    }
607
 
608
  /* If the control induction variable does not overflow, the loop obviously
609
     cannot be infinite.  */
610
  if (!zero_p (iv0->step) && iv0->no_overflow)
611
    never_infinite = true;
612
  else if (!zero_p (iv1->step) && iv1->no_overflow)
613
    never_infinite = true;
614
  else
615
    never_infinite = false;
616
 
617
  /* We can handle the case when neither of the sides of the comparison is
618
     invariant, provided that the test is NE_EXPR.  This rarely occurs in
619
     practice, but it is simple enough to manage.  */
620
  if (!zero_p (iv0->step) && !zero_p (iv1->step))
621
    {
622
      if (code != NE_EXPR)
623
        return false;
624
 
625
      iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
626
                                           iv0->step, iv1->step);
627
      iv0->no_overflow = false;
628
      iv1->step = NULL_TREE;
629
      iv1->no_overflow = true;
630
    }
631
 
632
  /* If the result of the comparison is a constant,  the loop is weird.  More
633
     precise handling would be possible, but the situation is not common enough
634
     to waste time on it.  */
635
  if (zero_p (iv0->step) && zero_p (iv1->step))
636
    return false;
637
 
638
  /* Ignore loops of while (i-- < 10) type.  */
639
  if (code != NE_EXPR)
640
    {
641
      if (iv0->step && tree_int_cst_sign_bit (iv0->step))
642
        return false;
643
 
644
      if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
645
        return false;
646
    }
647
 
648
  /* If the loop exits immediately, there is nothing to do.  */
649
  if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
650
    {
651
      niter->niter = build_int_cst (unsigned_type_for (type), 0);
652
      return true;
653
    }
654
 
655
  /* OK, now we know we have a senseful loop.  Handle several cases, depending
656
     on what comparison operator is used.  */
657
  switch (code)
658
    {
659
    case NE_EXPR:
660
      gcc_assert (zero_p (iv1->step));
661
      return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
662
    case LT_EXPR:
663
      return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
664
    case LE_EXPR:
665
      return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
666
    default:
667
      gcc_unreachable ();
668
    }
669
}
670
 
671
/* Substitute NEW for OLD in EXPR and fold the result.  */
672
 
673
static tree
674
simplify_replace_tree (tree expr, tree old, tree new)
675
{
676
  unsigned i, n;
677
  tree ret = NULL_TREE, e, se;
678
 
679
  if (!expr)
680
    return NULL_TREE;
681
 
682
  if (expr == old
683
      || operand_equal_p (expr, old, 0))
684
    return unshare_expr (new);
685
 
686
  if (!EXPR_P (expr))
687
    return expr;
688
 
689
  n = TREE_CODE_LENGTH (TREE_CODE (expr));
690
  for (i = 0; i < n; i++)
691
    {
692
      e = TREE_OPERAND (expr, i);
693
      se = simplify_replace_tree (e, old, new);
694
      if (e == se)
695
        continue;
696
 
697
      if (!ret)
698
        ret = copy_node (expr);
699
 
700
      TREE_OPERAND (ret, i) = se;
701
    }
702
 
703
  return (ret ? fold (ret) : expr);
704
}
705
 
706
/* Expand definitions of ssa names in EXPR as long as they are simple
707
   enough, and return the new expression.  */
708
 
709
tree
710
expand_simple_operations (tree expr)
711
{
712
  unsigned i, n;
713
  tree ret = NULL_TREE, e, ee, stmt;
714
  enum tree_code code;
715
 
716
  if (expr == NULL_TREE)
717
    return expr;
718
 
719
  if (is_gimple_min_invariant (expr))
720
    return expr;
721
 
722
  code = TREE_CODE (expr);
723
  if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
724
    {
725
      n = TREE_CODE_LENGTH (code);
726
      for (i = 0; i < n; i++)
727
        {
728
          e = TREE_OPERAND (expr, i);
729
          ee = expand_simple_operations (e);
730
          if (e == ee)
731
            continue;
732
 
733
          if (!ret)
734
            ret = copy_node (expr);
735
 
736
          TREE_OPERAND (ret, i) = ee;
737
        }
738
 
739
      if (!ret)
740
        return expr;
741
 
742
      fold_defer_overflow_warnings ();
743
      ret = fold (ret);
744
      fold_undefer_and_ignore_overflow_warnings ();
745
      return ret;
746
    }
747
 
748
  if (TREE_CODE (expr) != SSA_NAME)
749
    return expr;
750
 
751
  stmt = SSA_NAME_DEF_STMT (expr);
752
  if (TREE_CODE (stmt) != MODIFY_EXPR)
753
    return expr;
754
 
755
  e = TREE_OPERAND (stmt, 1);
756
  if (/* Casts are simple.  */
757
      TREE_CODE (e) != NOP_EXPR
758
      && TREE_CODE (e) != CONVERT_EXPR
759
      /* Copies are simple.  */
760
      && TREE_CODE (e) != SSA_NAME
761
      /* Assignments of invariants are simple.  */
762
      && !is_gimple_min_invariant (e)
763
      /* And increments and decrements by a constant are simple.  */
764
      && !((TREE_CODE (e) == PLUS_EXPR
765
            || TREE_CODE (e) == MINUS_EXPR)
766
           && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
767
    return expr;
768
 
769
  return expand_simple_operations (e);
770
}
771
 
772
/* Tries to simplify EXPR using the condition COND.  Returns the simplified
773
   expression (or EXPR unchanged, if no simplification was possible).  */
774
 
775
static tree
776
tree_simplify_using_condition_1 (tree cond, tree expr)
777
{
778
  bool changed;
779
  tree e, te, e0, e1, e2, notcond;
780
  enum tree_code code = TREE_CODE (expr);
781
 
782
  if (code == INTEGER_CST)
783
    return expr;
784
 
785
  if (code == TRUTH_OR_EXPR
786
      || code == TRUTH_AND_EXPR
787
      || code == COND_EXPR)
788
    {
789
      changed = false;
790
 
791
      e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
792
      if (TREE_OPERAND (expr, 0) != e0)
793
        changed = true;
794
 
795
      e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
796
      if (TREE_OPERAND (expr, 1) != e1)
797
        changed = true;
798
 
799
      if (code == COND_EXPR)
800
        {
801
          e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
802
          if (TREE_OPERAND (expr, 2) != e2)
803
            changed = true;
804
        }
805
      else
806
        e2 = NULL_TREE;
807
 
808
      if (changed)
809
        {
810
          if (code == COND_EXPR)
811
            expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
812
          else
813
            expr = fold_build2 (code, boolean_type_node, e0, e1);
814
        }
815
 
816
      return expr;
817
    }
818
 
819
  /* In case COND is equality, we may be able to simplify EXPR by copy/constant
820
     propagation, and vice versa.  Fold does not handle this, since it is
821
     considered too expensive.  */
822
  if (TREE_CODE (cond) == EQ_EXPR)
823
    {
824
      e0 = TREE_OPERAND (cond, 0);
825
      e1 = TREE_OPERAND (cond, 1);
826
 
827
      /* We know that e0 == e1.  Check whether we cannot simplify expr
828
         using this fact.  */
829
      e = simplify_replace_tree (expr, e0, e1);
830
      if (zero_p (e) || nonzero_p (e))
831
        return e;
832
 
833
      e = simplify_replace_tree (expr, e1, e0);
834
      if (zero_p (e) || nonzero_p (e))
835
        return e;
836
    }
837
  if (TREE_CODE (expr) == EQ_EXPR)
838
    {
839
      e0 = TREE_OPERAND (expr, 0);
840
      e1 = TREE_OPERAND (expr, 1);
841
 
842
      /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true.  */
843
      e = simplify_replace_tree (cond, e0, e1);
844
      if (zero_p (e))
845
        return e;
846
      e = simplify_replace_tree (cond, e1, e0);
847
      if (zero_p (e))
848
        return e;
849
    }
850
  if (TREE_CODE (expr) == NE_EXPR)
851
    {
852
      e0 = TREE_OPERAND (expr, 0);
853
      e1 = TREE_OPERAND (expr, 1);
854
 
855
      /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true.  */
856
      e = simplify_replace_tree (cond, e0, e1);
857
      if (zero_p (e))
858
        return boolean_true_node;
859
      e = simplify_replace_tree (cond, e1, e0);
860
      if (zero_p (e))
861
        return boolean_true_node;
862
    }
863
 
864
  te = expand_simple_operations (expr);
865
 
866
  /* Check whether COND ==> EXPR.  */
867
  notcond = invert_truthvalue (cond);
868
  e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
869
  if (nonzero_p (e))
870
    return e;
871
 
872
  /* Check whether COND ==> not EXPR.  */
873
  e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
874
  if (e && zero_p (e))
875
    return e;
876
 
877
  return expr;
878
}
879
 
880
/* Tries to simplify EXPR using the condition COND.  Returns the simplified
881
   expression (or EXPR unchanged, if no simplification was possible).
882
   Wrapper around tree_simplify_using_condition_1 that ensures that chains
883
   of simple operations in definitions of ssa names in COND are expanded,
884
   so that things like casts or incrementing the value of the bound before
885
   the loop do not cause us to fail.  */
886
 
887
static tree
888
tree_simplify_using_condition (tree cond, tree expr)
889
{
890
  cond = expand_simple_operations (cond);
891
 
892
  return tree_simplify_using_condition_1 (cond, expr);
893
}
894
 
895
/* The maximum number of dominator BBs we search for conditions
896
   of loop header copies we use for simplifying a conditional
897
   expression.  */
898
#define MAX_DOMINATORS_TO_WALK 8
899
 
900
/* Tries to simplify EXPR using the conditions on entry to LOOP.
901
   Record the conditions used for simplification to CONDS_USED.
902
   Returns the simplified expression (or EXPR unchanged, if no
903
   simplification was possible).*/
904
 
905
static tree
906
simplify_using_initial_conditions (struct loop *loop, tree expr,
907
                                   tree *conds_used)
908
{
909
  edge e;
910
  basic_block bb;
911
  tree exp, cond;
912
  int cnt = 0;
913
 
914
  if (TREE_CODE (expr) == INTEGER_CST)
915
    return expr;
916
 
917
  /* Limit walking the dominators to avoid quadraticness in
918
     the number of BBs times the number of loops in degenerate
919
     cases.  */
920
  for (bb = loop->header;
921
       bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
922
       bb = get_immediate_dominator (CDI_DOMINATORS, bb))
923
    {
924
      if (!single_pred_p (bb))
925
        continue;
926
      e = single_pred_edge (bb);
927
 
928
      if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
929
        continue;
930
 
931
      cond = COND_EXPR_COND (last_stmt (e->src));
932
      if (e->flags & EDGE_FALSE_VALUE)
933
        cond = invert_truthvalue (cond);
934
      exp = tree_simplify_using_condition (cond, expr);
935
 
936
      if (exp != expr)
937
        *conds_used = fold_build2 (TRUTH_AND_EXPR,
938
                                   boolean_type_node,
939
                                   *conds_used,
940
                                   cond);
941
 
942
      expr = exp;
943
      ++cnt;
944
    }
945
 
946
  return expr;
947
}
948
 
949
/* Tries to simplify EXPR using the evolutions of the loop invariants
950
   in the superloops of LOOP.  Returns the simplified expression
951
   (or EXPR unchanged, if no simplification was possible).  */
952
 
953
static tree
954
simplify_using_outer_evolutions (struct loop *loop, tree expr)
955
{
956
  enum tree_code code = TREE_CODE (expr);
957
  bool changed;
958
  tree e, e0, e1, e2;
959
 
960
  if (is_gimple_min_invariant (expr))
961
    return expr;
962
 
963
  if (code == TRUTH_OR_EXPR
964
      || code == TRUTH_AND_EXPR
965
      || code == COND_EXPR)
966
    {
967
      changed = false;
968
 
969
      e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
970
      if (TREE_OPERAND (expr, 0) != e0)
971
        changed = true;
972
 
973
      e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
974
      if (TREE_OPERAND (expr, 1) != e1)
975
        changed = true;
976
 
977
      if (code == COND_EXPR)
978
        {
979
          e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
980
          if (TREE_OPERAND (expr, 2) != e2)
981
            changed = true;
982
        }
983
      else
984
        e2 = NULL_TREE;
985
 
986
      if (changed)
987
        {
988
          if (code == COND_EXPR)
989
            expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
990
          else
991
            expr = fold_build2 (code, boolean_type_node, e0, e1);
992
        }
993
 
994
      return expr;
995
    }
996
 
997
  e = instantiate_parameters (loop, expr);
998
  if (is_gimple_min_invariant (e))
999
    return e;
1000
 
1001
  return expr;
1002
}
1003
 
1004
/* Returns true if EXIT is the only possible exit from LOOP.  */
1005
 
1006
static bool
1007
loop_only_exit_p (struct loop *loop, edge exit)
1008
{
1009
  basic_block *body;
1010
  block_stmt_iterator bsi;
1011
  unsigned i;
1012
  tree call;
1013
 
1014
  if (exit != loop->single_exit)
1015
    return false;
1016
 
1017
  body = get_loop_body (loop);
1018
  for (i = 0; i < loop->num_nodes; i++)
1019
    {
1020
      for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
1021
        {
1022
          call = get_call_expr_in (bsi_stmt (bsi));
1023
          if (call && TREE_SIDE_EFFECTS (call))
1024
            {
1025
              free (body);
1026
              return false;
1027
            }
1028
        }
1029
    }
1030
 
1031
  free (body);
1032
  return true;
1033
}
1034
 
1035
/* Stores description of number of iterations of LOOP derived from
1036
   EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
1037
   useful information could be derived (and fields of NITER has
1038
   meaning described in comments at struct tree_niter_desc
1039
   declaration), false otherwise.  If WARN is true and
1040
   -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1041
   potentially unsafe assumptions.  */
1042
 
1043
bool
1044
number_of_iterations_exit (struct loop *loop, edge exit,
1045
                           struct tree_niter_desc *niter,
1046
                           bool warn)
1047
{
1048
  tree stmt, cond, type;
1049
  tree op0, op1;
1050
  enum tree_code code;
1051
  affine_iv iv0, iv1;
1052
 
1053
  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1054
    return false;
1055
 
1056
  niter->assumptions = boolean_false_node;
1057
  stmt = last_stmt (exit->src);
1058
  if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1059
    return false;
1060
 
1061
  /* We want the condition for staying inside loop.  */
1062
  cond = COND_EXPR_COND (stmt);
1063
  if (exit->flags & EDGE_TRUE_VALUE)
1064
    cond = invert_truthvalue (cond);
1065
 
1066
  code = TREE_CODE (cond);
1067
  switch (code)
1068
    {
1069
    case GT_EXPR:
1070
    case GE_EXPR:
1071
    case NE_EXPR:
1072
    case LT_EXPR:
1073
    case LE_EXPR:
1074
      break;
1075
 
1076
    default:
1077
      return false;
1078
    }
1079
 
1080
  op0 = TREE_OPERAND (cond, 0);
1081
  op1 = TREE_OPERAND (cond, 1);
1082
  type = TREE_TYPE (op0);
1083
 
1084
  if (TREE_CODE (type) != INTEGER_TYPE
1085
      && !POINTER_TYPE_P (type))
1086
    return false;
1087
 
1088
  if (!simple_iv (loop, stmt, op0, &iv0, false))
1089
    return false;
1090
  if (!simple_iv (loop, stmt, op1, &iv1, false))
1091
    return false;
1092
 
1093
  /* We don't want to see undefined signed overflow warnings while
1094
     computing the nmber of iterations.  */
1095
  fold_defer_overflow_warnings ();
1096
 
1097
  iv0.base = expand_simple_operations (iv0.base);
1098
  iv1.base = expand_simple_operations (iv1.base);
1099
  if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter,
1100
                                  loop_only_exit_p (loop, exit)))
1101
    {
1102
      fold_undefer_and_ignore_overflow_warnings ();
1103
      return false;
1104
    }
1105
 
1106
  if (optimize >= 3)
1107
    {
1108
      niter->assumptions = simplify_using_outer_evolutions (loop,
1109
                                                            niter->assumptions);
1110
      niter->may_be_zero = simplify_using_outer_evolutions (loop,
1111
                                                            niter->may_be_zero);
1112
      niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1113
    }
1114
 
1115
  niter->additional_info = boolean_true_node;
1116
  niter->assumptions
1117
          = simplify_using_initial_conditions (loop,
1118
                                               niter->assumptions,
1119
                                               &niter->additional_info);
1120
  niter->may_be_zero
1121
          = simplify_using_initial_conditions (loop,
1122
                                               niter->may_be_zero,
1123
                                               &niter->additional_info);
1124
 
1125
  fold_undefer_and_ignore_overflow_warnings ();
1126
 
1127
  if (integer_onep (niter->assumptions))
1128
    return true;
1129
 
1130
  /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1131
     But if we can prove that there is overflow or some other source of weird
1132
     behavior, ignore the loop even with -funsafe-loop-optimizations.  */
1133
  if (integer_zerop (niter->assumptions))
1134
    return false;
1135
 
1136
  if (flag_unsafe_loop_optimizations)
1137
    niter->assumptions = boolean_true_node;
1138
 
1139
  if (warn)
1140
    {
1141
      const char *wording;
1142
      location_t loc = EXPR_LOCATION (stmt);
1143
 
1144
      /* We can provide a more specific warning if one of the operator is
1145
         constant and the other advances by +1 or -1.  */
1146
      if (!zero_p (iv1.step)
1147
          ? (zero_p (iv0.step)
1148
             && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1149
          : (iv0.step
1150
             && (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
1151
        wording =
1152
          flag_unsafe_loop_optimizations
1153
          ? N_("assuming that the loop is not infinite")
1154
          : N_("cannot optimize possibly infinite loops");
1155
      else
1156
        wording =
1157
          flag_unsafe_loop_optimizations
1158
          ? N_("assuming that the loop counter does not overflow")
1159
          : N_("cannot optimize loop, the loop counter may overflow");
1160
 
1161
      if (LOCATION_LINE (loc) > 0)
1162
        warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
1163
      else
1164
        warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1165
    }
1166
 
1167
  return flag_unsafe_loop_optimizations;
1168
}
1169
 
1170
/* Try to determine the number of iterations of LOOP.  If we succeed,
1171
   expression giving number of iterations is returned and *EXIT is
1172
   set to the edge from that the information is obtained.  Otherwise
1173
   chrec_dont_know is returned.  */
1174
 
1175
tree
1176
find_loop_niter (struct loop *loop, edge *exit)
1177
{
1178
  unsigned n_exits, i;
1179
  edge *exits = get_loop_exit_edges (loop, &n_exits);
1180
  edge ex;
1181
  tree niter = NULL_TREE, aniter;
1182
  struct tree_niter_desc desc;
1183
 
1184
  *exit = NULL;
1185
  for (i = 0; i < n_exits; i++)
1186
    {
1187
      ex = exits[i];
1188
      if (!just_once_each_iteration_p (loop, ex->src))
1189
        continue;
1190
 
1191
      if (!number_of_iterations_exit (loop, ex, &desc, false))
1192
        continue;
1193
 
1194
      if (nonzero_p (desc.may_be_zero))
1195
        {
1196
          /* We exit in the first iteration through this exit.
1197
             We won't find anything better.  */
1198
          niter = build_int_cst (unsigned_type_node, 0);
1199
          *exit = ex;
1200
          break;
1201
        }
1202
 
1203
      if (!zero_p (desc.may_be_zero))
1204
        continue;
1205
 
1206
      aniter = desc.niter;
1207
 
1208
      if (!niter)
1209
        {
1210
          /* Nothing recorded yet.  */
1211
          niter = aniter;
1212
          *exit = ex;
1213
          continue;
1214
        }
1215
 
1216
      /* Prefer constants, the lower the better.  */
1217
      if (TREE_CODE (aniter) != INTEGER_CST)
1218
        continue;
1219
 
1220
      if (TREE_CODE (niter) != INTEGER_CST)
1221
        {
1222
          niter = aniter;
1223
          *exit = ex;
1224
          continue;
1225
        }
1226
 
1227
      if (tree_int_cst_lt (aniter, niter))
1228
        {
1229
          niter = aniter;
1230
          *exit = ex;
1231
          continue;
1232
        }
1233
    }
1234
  free (exits);
1235
 
1236
  return niter ? niter : chrec_dont_know;
1237
}
1238
 
1239
/*
1240
 
1241
   Analysis of a number of iterations of a loop by a brute-force evaluation.
1242
 
1243
*/
1244
 
1245
/* Bound on the number of iterations we try to evaluate.  */
1246
 
1247
#define MAX_ITERATIONS_TO_TRACK \
1248
  ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1249
 
1250
/* Returns the loop phi node of LOOP such that ssa name X is derived from its
1251
   result by a chain of operations such that all but exactly one of their
1252
   operands are constants.  */
1253
 
1254
static tree
1255
chain_of_csts_start (struct loop *loop, tree x)
1256
{
1257
  tree stmt = SSA_NAME_DEF_STMT (x);
1258
  tree use;
1259
  basic_block bb = bb_for_stmt (stmt);
1260
 
1261
  if (!bb
1262
      || !flow_bb_inside_loop_p (loop, bb))
1263
    return NULL_TREE;
1264
 
1265
  if (TREE_CODE (stmt) == PHI_NODE)
1266
    {
1267
      if (bb == loop->header)
1268
        return stmt;
1269
 
1270
      return NULL_TREE;
1271
    }
1272
 
1273
  if (TREE_CODE (stmt) != MODIFY_EXPR)
1274
    return NULL_TREE;
1275
 
1276
  if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1277
    return NULL_TREE;
1278
  if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
1279
    return NULL_TREE;
1280
 
1281
  use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1282
  if (use == NULL_USE_OPERAND_P)
1283
    return NULL_TREE;
1284
 
1285
  return chain_of_csts_start (loop, use);
1286
}
1287
 
1288
/* Determines whether the expression X is derived from a result of a phi node
1289
   in header of LOOP such that
1290
 
1291
   * the derivation of X consists only from operations with constants
1292
   * the initial value of the phi node is constant
1293
   * the value of the phi node in the next iteration can be derived from the
1294
     value in the current iteration by a chain of operations with constants.
1295
 
1296
   If such phi node exists, it is returned.  If X is a constant, X is returned
1297
   unchanged.  Otherwise NULL_TREE is returned.  */
1298
 
1299
static tree
1300
get_base_for (struct loop *loop, tree x)
1301
{
1302
  tree phi, init, next;
1303
 
1304
  if (is_gimple_min_invariant (x))
1305
    return x;
1306
 
1307
  phi = chain_of_csts_start (loop, x);
1308
  if (!phi)
1309
    return NULL_TREE;
1310
 
1311
  init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1312
  next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1313
 
1314
  if (TREE_CODE (next) != SSA_NAME)
1315
    return NULL_TREE;
1316
 
1317
  if (!is_gimple_min_invariant (init))
1318
    return NULL_TREE;
1319
 
1320
  if (chain_of_csts_start (loop, next) != phi)
1321
    return NULL_TREE;
1322
 
1323
  return phi;
1324
}
1325
 
1326
/* Given an expression X, then
1327
 
1328
   * if X is NULL_TREE, we return the constant BASE.
1329
   * otherwise X is a SSA name, whose value in the considered loop is derived
1330
     by a chain of operations with constant from a result of a phi node in
1331
     the header of the loop.  Then we return value of X when the value of the
1332
     result of this phi node is given by the constant BASE.  */
1333
 
1334
static tree
1335
get_val_for (tree x, tree base)
1336
{
1337
  tree stmt, nx, val;
1338
  use_operand_p op;
1339
  ssa_op_iter iter;
1340
 
1341
  gcc_assert (is_gimple_min_invariant (base));
1342
 
1343
  if (!x)
1344
    return base;
1345
 
1346
  stmt = SSA_NAME_DEF_STMT (x);
1347
  if (TREE_CODE (stmt) == PHI_NODE)
1348
    return base;
1349
 
1350
  FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
1351
    {
1352
      nx = USE_FROM_PTR (op);
1353
      val = get_val_for (nx, base);
1354
      SET_USE (op, val);
1355
      val = fold (TREE_OPERAND (stmt, 1));
1356
      SET_USE (op, nx);
1357
      /* only iterate loop once.  */
1358
      return val;
1359
    }
1360
 
1361
  /* Should never reach here.  */
1362
  gcc_unreachable();
1363
}
1364
 
1365
/* Tries to count the number of iterations of LOOP till it exits by EXIT
1366
   by brute force -- i.e. by determining the value of the operands of the
1367
   condition at EXIT in first few iterations of the loop (assuming that
1368
   these values are constant) and determining the first one in that the
1369
   condition is not satisfied.  Returns the constant giving the number
1370
   of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
1371
 
1372
tree
1373
loop_niter_by_eval (struct loop *loop, edge exit)
1374
{
1375
  tree cond, cnd, acnd;
1376
  tree op[2], val[2], next[2], aval[2], phi[2];
1377
  unsigned i, j;
1378
  enum tree_code cmp;
1379
 
1380
  cond = last_stmt (exit->src);
1381
  if (!cond || TREE_CODE (cond) != COND_EXPR)
1382
    return chrec_dont_know;
1383
 
1384
  cnd = COND_EXPR_COND (cond);
1385
  if (exit->flags & EDGE_TRUE_VALUE)
1386
    cnd = invert_truthvalue (cnd);
1387
 
1388
  cmp = TREE_CODE (cnd);
1389
  switch (cmp)
1390
    {
1391
    case EQ_EXPR:
1392
    case NE_EXPR:
1393
    case GT_EXPR:
1394
    case GE_EXPR:
1395
    case LT_EXPR:
1396
    case LE_EXPR:
1397
      for (j = 0; j < 2; j++)
1398
        op[j] = TREE_OPERAND (cnd, j);
1399
      break;
1400
 
1401
    default:
1402
      return chrec_dont_know;
1403
    }
1404
 
1405
  for (j = 0; j < 2; j++)
1406
    {
1407
      phi[j] = get_base_for (loop, op[j]);
1408
      if (!phi[j])
1409
        return chrec_dont_know;
1410
    }
1411
 
1412
  for (j = 0; j < 2; j++)
1413
    {
1414
      if (TREE_CODE (phi[j]) == PHI_NODE)
1415
        {
1416
          val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1417
          next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1418
        }
1419
      else
1420
        {
1421
          val[j] = phi[j];
1422
          next[j] = NULL_TREE;
1423
          op[j] = NULL_TREE;
1424
        }
1425
    }
1426
 
1427
  /* Don't issue signed overflow warnings.  */
1428
  fold_defer_overflow_warnings ();
1429
 
1430
  for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1431
    {
1432
      for (j = 0; j < 2; j++)
1433
        aval[j] = get_val_for (op[j], val[j]);
1434
 
1435
      acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
1436
      if (acnd && zero_p (acnd))
1437
        {
1438
          fold_undefer_and_ignore_overflow_warnings ();
1439
          if (dump_file && (dump_flags & TDF_DETAILS))
1440
            fprintf (dump_file,
1441
                     "Proved that loop %d iterates %d times using brute force.\n",
1442
                     loop->num, i);
1443
          return build_int_cst (unsigned_type_node, i);
1444
        }
1445
 
1446
      for (j = 0; j < 2; j++)
1447
        {
1448
          val[j] = get_val_for (next[j], val[j]);
1449
          if (!is_gimple_min_invariant (val[j]))
1450
            {
1451
              fold_undefer_and_ignore_overflow_warnings ();
1452
              return chrec_dont_know;
1453
            }
1454
        }
1455
    }
1456
 
1457
  fold_undefer_and_ignore_overflow_warnings ();
1458
 
1459
  return chrec_dont_know;
1460
}
1461
 
1462
/* Finds the exit of the LOOP by that the loop exits after a constant
1463
   number of iterations and stores the exit edge to *EXIT.  The constant
1464
   giving the number of iterations of LOOP is returned.  The number of
1465
   iterations is determined using loop_niter_by_eval (i.e. by brute force
1466
   evaluation).  If we are unable to find the exit for that loop_niter_by_eval
1467
   determines the number of iterations, chrec_dont_know is returned.  */
1468
 
1469
tree
1470
find_loop_niter_by_eval (struct loop *loop, edge *exit)
1471
{
1472
  unsigned n_exits, i;
1473
  edge *exits = get_loop_exit_edges (loop, &n_exits);
1474
  edge ex;
1475
  tree niter = NULL_TREE, aniter;
1476
 
1477
  *exit = NULL;
1478
  for (i = 0; i < n_exits; i++)
1479
    {
1480
      ex = exits[i];
1481
      if (!just_once_each_iteration_p (loop, ex->src))
1482
        continue;
1483
 
1484
      aniter = loop_niter_by_eval (loop, ex);
1485
      if (chrec_contains_undetermined (aniter))
1486
        continue;
1487
 
1488
      if (niter
1489
          && !tree_int_cst_lt (aniter, niter))
1490
        continue;
1491
 
1492
      niter = aniter;
1493
      *exit = ex;
1494
    }
1495
  free (exits);
1496
 
1497
  return niter ? niter : chrec_dont_know;
1498
}
1499
 
1500
/*
1501
 
1502
   Analysis of upper bounds on number of iterations of a loop.
1503
 
1504
*/
1505
 
1506
/* Returns true if we can prove that COND ==> VAL >= 0.  */
1507
 
1508
static bool
1509
implies_nonnegative_p (tree cond, tree val)
1510
{
1511
  tree type = TREE_TYPE (val);
1512
  tree compare;
1513
 
1514
  if (tree_expr_nonnegative_p (val))
1515
    return true;
1516
 
1517
  if (nonzero_p (cond))
1518
    return false;
1519
 
1520
  compare = fold_build2 (GE_EXPR,
1521
                         boolean_type_node, val, build_int_cst (type, 0));
1522
  compare = tree_simplify_using_condition_1 (cond, compare);
1523
 
1524
  return nonzero_p (compare);
1525
}
1526
 
1527
/* Returns true if we can prove that COND ==> A >= B.  */
1528
 
1529
static bool
1530
implies_ge_p (tree cond, tree a, tree b)
1531
{
1532
  tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b);
1533
 
1534
  if (nonzero_p (compare))
1535
    return true;
1536
 
1537
  if (nonzero_p (cond))
1538
    return false;
1539
 
1540
  compare = tree_simplify_using_condition_1 (cond, compare);
1541
 
1542
  return nonzero_p (compare);
1543
}
1544
 
1545
/* Returns a constant upper bound on the value of expression VAL.  VAL
1546
   is considered to be unsigned.  If its type is signed, its value must
1547
   be nonnegative.
1548
 
1549
   The condition ADDITIONAL must be satisfied (for example, if VAL is
1550
   "(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that
1551
   VAL is at most (unsigned) MAX_INT).  */
1552
 
1553
static double_int
1554
derive_constant_upper_bound (tree val, tree additional)
1555
{
1556
  tree type = TREE_TYPE (val);
1557
  tree op0, op1, subtype, maxt;
1558
  double_int bnd, max, mmax, cst;
1559
 
1560
  if (INTEGRAL_TYPE_P (type))
1561
    maxt = TYPE_MAX_VALUE (type);
1562
  else
1563
    maxt = upper_bound_in_type (type, type);
1564
 
1565
  max = tree_to_double_int (maxt);
1566
 
1567
  switch (TREE_CODE (val))
1568
    {
1569
    case INTEGER_CST:
1570
      return tree_to_double_int (val);
1571
 
1572
    case NOP_EXPR:
1573
    case CONVERT_EXPR:
1574
      op0 = TREE_OPERAND (val, 0);
1575
      subtype = TREE_TYPE (op0);
1576
      if (!TYPE_UNSIGNED (subtype)
1577
          /* If TYPE is also signed, the fact that VAL is nonnegative implies
1578
             that OP0 is nonnegative.  */
1579
          && TYPE_UNSIGNED (type)
1580
          && !implies_nonnegative_p (additional, op0))
1581
        {
1582
          /* If we cannot prove that the casted expression is nonnegative,
1583
             we cannot establish more useful upper bound than the precision
1584
             of the type gives us.  */
1585
          return max;
1586
        }
1587
 
1588
      /* We now know that op0 is an nonnegative value.  Try deriving an upper
1589
         bound for it.  */
1590
      bnd = derive_constant_upper_bound (op0, additional);
1591
 
1592
      /* If the bound does not fit in TYPE, max. value of TYPE could be
1593
         attained.  */
1594
      if (double_int_ucmp (max, bnd) < 0)
1595
        return max;
1596
 
1597
      return bnd;
1598
 
1599
    case PLUS_EXPR:
1600
    case MINUS_EXPR:
1601
      op0 = TREE_OPERAND (val, 0);
1602
      op1 = TREE_OPERAND (val, 1);
1603
 
1604
      if (TREE_CODE (op1) != INTEGER_CST
1605
          || !implies_nonnegative_p (additional, op0))
1606
        return max;
1607
 
1608
      /* Canonicalize to OP0 - CST.  Consider CST to be signed, in order to
1609
         choose the most logical way how to treat this constant regardless
1610
         of the signedness of the type.  */
1611
      cst = tree_to_double_int (op1);
1612
      cst = double_int_sext (cst, TYPE_PRECISION (type));
1613
      if (TREE_CODE (val) == PLUS_EXPR)
1614
        cst = double_int_neg (cst);
1615
 
1616
      bnd = derive_constant_upper_bound (op0, additional);
1617
 
1618
      if (double_int_negative_p (cst))
1619
        {
1620
          cst = double_int_neg (cst);
1621
          /* Avoid CST == 0x80000...  */
1622
          if (double_int_negative_p (cst))
1623
            return max;;
1624
 
1625
          /* OP0 + CST.  We need to check that
1626
             BND <= MAX (type) - CST.  */
1627
 
1628
          mmax = double_int_add (max, double_int_neg (cst));
1629
          if (double_int_ucmp (bnd, mmax) > 0)
1630
            return max;
1631
 
1632
          return double_int_add (bnd, cst);
1633
        }
1634
      else
1635
        {
1636
          /* OP0 - CST, where CST >= 0.
1637
 
1638
             If TYPE is signed, we have already verified that OP0 >= 0, and we
1639
             know that the result is nonnegative.  This implies that
1640
             VAL <= BND - CST.
1641
 
1642
             If TYPE is unsigned, we must additionally know that OP0 >= CST,
1643
             otherwise the operation underflows.
1644
           */
1645
 
1646
          /* This should only happen if the type is unsigned; however, for
1647
             programs that use overflowing signed arithmetics even with
1648
             -fno-wrapv, this condition may also be true for signed values.  */
1649
          if (double_int_ucmp (bnd, cst) < 0)
1650
            return max;
1651
 
1652
          if (TYPE_UNSIGNED (type)
1653
              && !implies_ge_p (additional,
1654
                                op0, double_int_to_tree (type, cst)))
1655
            return max;
1656
 
1657
          bnd = double_int_add (bnd, double_int_neg (cst));
1658
        }
1659
 
1660
      return bnd;
1661
 
1662
    case FLOOR_DIV_EXPR:
1663
    case EXACT_DIV_EXPR:
1664
      op0 = TREE_OPERAND (val, 0);
1665
      op1 = TREE_OPERAND (val, 1);
1666
      if (TREE_CODE (op1) != INTEGER_CST
1667
          || tree_int_cst_sign_bit (op1))
1668
        return max;
1669
 
1670
      bnd = derive_constant_upper_bound (op0, additional);
1671
      return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
1672
 
1673
    default:
1674
      return max;
1675
    }
1676
}
1677
 
1678
/* Records that AT_STMT is executed at most BOUND times in LOOP.  The
1679
   additional condition ADDITIONAL is recorded with the bound.  */
1680
 
1681
void
1682
record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1683
{
1684
  struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1685
  double_int i_bound = derive_constant_upper_bound (bound, additional);
1686
  tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)),
1687
                                     i_bound);
1688
 
1689
  if (dump_file && (dump_flags & TDF_DETAILS))
1690
    {
1691
      fprintf (dump_file, "Statements after ");
1692
      print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1693
      fprintf (dump_file, " are executed at most ");
1694
      print_generic_expr (dump_file, bound, TDF_SLIM);
1695
      fprintf (dump_file, " (bounded by ");
1696
      print_generic_expr (dump_file, c_bound, TDF_SLIM);
1697
      fprintf (dump_file, ") times in loop %d.\n", loop->num);
1698
    }
1699
 
1700
  elt->bound = c_bound;
1701
  elt->at_stmt = at_stmt;
1702
  elt->next = loop->bounds;
1703
  loop->bounds = elt;
1704
}
1705
 
1706
/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
1707
   approximation of the number of iterations for LOOP.  */
1708
 
1709
static void
1710
compute_estimated_nb_iterations (struct loop *loop)
1711
{
1712
  struct nb_iter_bound *bound;
1713
 
1714
  for (bound = loop->bounds; bound; bound = bound->next)
1715
    {
1716
      if (TREE_CODE (bound->bound) != INTEGER_CST)
1717
        continue;
1718
 
1719
      /* Update only when there is no previous estimation, or when the current
1720
         estimation is smaller.  */
1721
      if (chrec_contains_undetermined (loop->estimated_nb_iterations)
1722
          || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))
1723
        loop->estimated_nb_iterations = bound->bound;
1724
    }
1725
}
1726
 
1727
/* The following analyzers are extracting informations on the bounds
1728
   of LOOP from the following undefined behaviors:
1729
 
1730
   - data references should not access elements over the statically
1731
     allocated size,
1732
 
1733
   - signed variables should not overflow when flag_wrapv is not set.
1734
*/
1735
 
1736
static void
1737
infer_loop_bounds_from_undefined (struct loop *loop)
1738
{
1739
  unsigned i;
1740
  basic_block bb, *bbs;
1741
  block_stmt_iterator bsi;
1742
 
1743
  bbs = get_loop_body (loop);
1744
 
1745
  for (i = 0; i < loop->num_nodes; i++)
1746
    {
1747
      bb = bbs[i];
1748
 
1749
      /* If BB is not executed in each iteration of the loop, we cannot
1750
         use the operations in it to infer reliable upper bound on the
1751
         # of iterations of the loop.  */
1752
      if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1753
        continue;
1754
 
1755
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1756
        {
1757
          tree stmt = bsi_stmt (bsi);
1758
 
1759
          switch (TREE_CODE (stmt))
1760
            {
1761
            case MODIFY_EXPR:
1762
              {
1763
                tree op0 = TREE_OPERAND (stmt, 0);
1764
                tree op1 = TREE_OPERAND (stmt, 1);
1765
 
1766
                /* For each array access, analyze its access function
1767
                   and record a bound on the loop iteration domain.  */
1768
                if (TREE_CODE (op1) == ARRAY_REF
1769
                    && !array_ref_contains_indirect_ref (op1))
1770
                  estimate_iters_using_array (stmt, op1);
1771
 
1772
                if (TREE_CODE (op0) == ARRAY_REF
1773
                    && !array_ref_contains_indirect_ref (op0))
1774
                  estimate_iters_using_array (stmt, op0);
1775
 
1776
                /* For each signed type variable in LOOP, analyze its
1777
                   scalar evolution and record a bound of the loop
1778
                   based on the type's ranges.  */
1779
                else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
1780
                  {
1781
                    tree init, step, diff, estimation;
1782
                    tree scev = instantiate_parameters
1783
                      (loop, analyze_scalar_evolution (loop, op0));
1784
                    tree type = chrec_type (scev);
1785
 
1786
                    if (chrec_contains_undetermined (scev)
1787
                        || TYPE_OVERFLOW_WRAPS (type))
1788
                      break;
1789
 
1790
                    init = initial_condition_in_loop_num (scev, loop->num);
1791
                    step = evolution_part_in_loop_num (scev, loop->num);
1792
 
1793
                    if (init == NULL_TREE
1794
                        || step == NULL_TREE
1795
                        || TREE_CODE (init) != INTEGER_CST
1796
                        || TREE_CODE (step) != INTEGER_CST
1797
                        || TYPE_MIN_VALUE (type) == NULL_TREE
1798
                        || TYPE_MAX_VALUE (type) == NULL_TREE)
1799
                      break;
1800
 
1801
                    if (integer_nonzerop (step))
1802
                      {
1803
                        tree utype;
1804
 
1805
                        if (tree_int_cst_lt (step, integer_zero_node))
1806
                          diff = fold_build2 (MINUS_EXPR, type, init,
1807
                                              TYPE_MIN_VALUE (type));
1808
                        else
1809
                          diff = fold_build2 (MINUS_EXPR, type,
1810
                                              TYPE_MAX_VALUE (type), init);
1811
 
1812
                        utype = unsigned_type_for (type);
1813
                        estimation = fold_build2 (CEIL_DIV_EXPR, type, diff,
1814
                                                  step);
1815
                        record_estimate (loop,
1816
                                         fold_convert (utype, estimation),
1817
                                         boolean_true_node, stmt);
1818
                      }
1819
                  }
1820
 
1821
                break;
1822
              }
1823
 
1824
            case CALL_EXPR:
1825
              {
1826
                tree args;
1827
 
1828
                for (args = TREE_OPERAND (stmt, 1); args;
1829
                     args = TREE_CHAIN (args))
1830
                  if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
1831
                      && !array_ref_contains_indirect_ref (TREE_VALUE (args)))
1832
                    estimate_iters_using_array (stmt, TREE_VALUE (args));
1833
 
1834
                break;
1835
              }
1836
 
1837
            default:
1838
              break;
1839
            }
1840
        }
1841
    }
1842
 
1843
  compute_estimated_nb_iterations (loop);
1844
  free (bbs);
1845
}
1846
 
1847
/* Records estimates on numbers of iterations of LOOP.  */
1848
 
1849
static void
1850
estimate_numbers_of_iterations_loop (struct loop *loop)
1851
{
1852
  edge *exits;
1853
  tree niter, type;
1854
  unsigned i, n_exits;
1855
  struct tree_niter_desc niter_desc;
1856
 
1857
  /* Give up if we already have tried to compute an estimation.  */
1858
  if (loop->estimated_nb_iterations == chrec_dont_know
1859
      /* Or when we already have an estimation.  */
1860
      || (loop->estimated_nb_iterations != NULL_TREE
1861
          && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
1862
    return;
1863
  else
1864
    loop->estimated_nb_iterations = chrec_dont_know;
1865
 
1866
  exits = get_loop_exit_edges (loop, &n_exits);
1867
  for (i = 0; i < n_exits; i++)
1868
    {
1869
      if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
1870
        continue;
1871
 
1872
      niter = niter_desc.niter;
1873
      type = TREE_TYPE (niter);
1874
      if (!zero_p (niter_desc.may_be_zero)
1875
          && !nonzero_p (niter_desc.may_be_zero))
1876
        niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1877
                        build_int_cst (type, 0),
1878
                        niter);
1879
      record_estimate (loop, niter,
1880
                       niter_desc.additional_info,
1881
                       last_stmt (exits[i]->src));
1882
    }
1883
  free (exits);
1884
 
1885
  if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1886
    infer_loop_bounds_from_undefined (loop);
1887
}
1888
 
1889
/* Records estimates on numbers of iterations of LOOPS.  */
1890
 
1891
void
1892
estimate_numbers_of_iterations (struct loops *loops)
1893
{
1894
  unsigned i;
1895
  struct loop *loop;
1896
 
1897
  /* We don't want to issue signed overflow warnings while getting
1898
     loop iteration estimates.  */
1899
  fold_defer_overflow_warnings ();
1900
 
1901
  for (i = 1; i < loops->num; i++)
1902
    {
1903
      loop = loops->parray[i];
1904
      if (loop)
1905
        estimate_numbers_of_iterations_loop (loop);
1906
    }
1907
 
1908
  fold_undefer_and_ignore_overflow_warnings ();
1909
}
1910
 
1911
/* Returns true if statement S1 dominates statement S2.  */
1912
 
1913
static bool
1914
stmt_dominates_stmt_p (tree s1, tree s2)
1915
{
1916
  basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
1917
 
1918
  if (!bb1
1919
      || s1 == s2)
1920
    return true;
1921
 
1922
  if (bb1 == bb2)
1923
    {
1924
      block_stmt_iterator bsi;
1925
 
1926
      for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
1927
        if (bsi_stmt (bsi) == s1)
1928
          return true;
1929
 
1930
      return false;
1931
    }
1932
 
1933
  return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
1934
}
1935
 
1936
/* Returns true when we can prove that the number of executions of
1937
   STMT in the loop is at most NITER, according to the fact
1938
   that the statement NITER_BOUND->at_stmt is executed at most
1939
   NITER_BOUND->bound times.  */
1940
 
1941
static bool
1942
n_of_executions_at_most (tree stmt,
1943
                         struct nb_iter_bound *niter_bound,
1944
                         tree niter)
1945
{
1946
  tree cond;
1947
  tree bound = niter_bound->bound;
1948
  tree bound_type = TREE_TYPE (bound);
1949
  tree nit_type = TREE_TYPE (niter);
1950
  enum tree_code cmp;
1951
 
1952
  gcc_assert (TYPE_UNSIGNED (bound_type)
1953
              && TYPE_UNSIGNED (nit_type)
1954
              && is_gimple_min_invariant (bound));
1955
  if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type))
1956
    bound = fold_convert (nit_type, bound);
1957
  else
1958
    niter = fold_convert (bound_type, niter);
1959
 
1960
  /* After the statement niter_bound->at_stmt we know that anything is
1961
     executed at most BOUND times.  */
1962
  if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt))
1963
    cmp = GE_EXPR;
1964
  /* Before the statement niter_bound->at_stmt we know that anything
1965
     is executed at most BOUND + 1 times.  */
1966
  else
1967
    cmp = GT_EXPR;
1968
 
1969
  cond = fold_binary (cmp, boolean_type_node, niter, bound);
1970
  return nonzero_p (cond);
1971
}
1972
 
1973
/* Returns true if the arithmetics in TYPE can be assumed not to wrap.  */
1974
 
1975
bool
1976
nowrap_type_p (tree type)
1977
{
1978
  if (INTEGRAL_TYPE_P (type)
1979
      && TYPE_OVERFLOW_UNDEFINED (type))
1980
    return true;
1981
 
1982
  if (POINTER_TYPE_P (type))
1983
    return true;
1984
 
1985
  return false;
1986
}
1987
 
1988
/* Return false only when the induction variable BASE + STEP * I is
1989
   known to not overflow: i.e. when the number of iterations is small
1990
   enough with respect to the step and initial condition in order to
1991
   keep the evolution confined in TYPEs bounds.  Return true when the
1992
   iv is known to overflow or when the property is not computable.
1993
 
1994
   USE_OVERFLOW_SEMANTICS is true if this function should assume that
1995
   the rules for overflow of the given language apply (e.g., that signed
1996
   arithmetics in C does not overflow).  */
1997
 
1998
bool
1999
scev_probably_wraps_p (tree base, tree step,
2000
                       tree at_stmt, struct loop *loop,
2001
                       bool use_overflow_semantics)
2002
{
2003
  struct nb_iter_bound *bound;
2004
  tree delta, step_abs;
2005
  tree unsigned_type, valid_niter;
2006
  tree type = TREE_TYPE (step);
2007
 
2008
  /* FIXME: We really need something like
2009
     http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
2010
 
2011
     We used to test for the following situation that frequently appears
2012
     during address arithmetics:
2013
 
2014
       D.1621_13 = (long unsigned intD.4) D.1620_12;
2015
       D.1622_14 = D.1621_13 * 8;
2016
       D.1623_15 = (doubleD.29 *) D.1622_14;
2017
 
2018
     And derived that the sequence corresponding to D_14
2019
     can be proved to not wrap because it is used for computing a
2020
     memory access; however, this is not really the case -- for example,
2021
     if D_12 = (unsigned char) [254,+,1], then D_14 has values
2022
     2032, 2040, 0, 8, ..., but the code is still legal.  */
2023
 
2024
  if (chrec_contains_undetermined (base)
2025
      || chrec_contains_undetermined (step)
2026
      || TREE_CODE (step) != INTEGER_CST)
2027
    return true;
2028
 
2029
  if (zero_p (step))
2030
    return false;
2031
 
2032
  /* If we can use the fact that signed and pointer arithmetics does not
2033
     wrap, we are done.  */
2034
  if (use_overflow_semantics && nowrap_type_p (type))
2035
    return false;
2036
 
2037
  /* Don't issue signed overflow warnings.  */
2038
  fold_defer_overflow_warnings ();
2039
 
2040
  /* Otherwise, compute the number of iterations before we reach the
2041
     bound of the type, and verify that the loop is exited before this
2042
     occurs.  */
2043
  unsigned_type = unsigned_type_for (type);
2044
  base = fold_convert (unsigned_type, base);
2045
 
2046
  if (tree_int_cst_sign_bit (step))
2047
    {
2048
      tree extreme = fold_convert (unsigned_type,
2049
                                   lower_bound_in_type (type, type));
2050
      delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2051
      step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
2052
                              fold_convert (unsigned_type, step));
2053
    }
2054
  else
2055
    {
2056
      tree extreme = fold_convert (unsigned_type,
2057
                                   upper_bound_in_type (type, type));
2058
      delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2059
      step_abs = fold_convert (unsigned_type, step);
2060
    }
2061
 
2062
  valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
2063
 
2064
  estimate_numbers_of_iterations_loop (loop);
2065
  for (bound = loop->bounds; bound; bound = bound->next)
2066
    {
2067
      if (n_of_executions_at_most (at_stmt, bound, valid_niter))
2068
        {
2069
          fold_undefer_and_ignore_overflow_warnings ();
2070
          return false;
2071
        }
2072
    }
2073
 
2074
  fold_undefer_and_ignore_overflow_warnings ();
2075
 
2076
  /* At this point we still don't have a proof that the iv does not
2077
     overflow: give up.  */
2078
  return true;
2079
}
2080
 
2081
/* Frees the information on upper bounds on numbers of iterations of LOOP.  */
2082
 
2083
void
2084
free_numbers_of_iterations_estimates_loop (struct loop *loop)
2085
{
2086
  struct nb_iter_bound *bound, *next;
2087
 
2088
  loop->nb_iterations = NULL;
2089
  loop->estimated_nb_iterations = NULL;
2090
  for (bound = loop->bounds; bound; bound = next)
2091
    {
2092
      next = bound->next;
2093
      free (bound);
2094
    }
2095
 
2096
  loop->bounds = NULL;
2097
}
2098
 
2099
/* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
2100
 
2101
void
2102
free_numbers_of_iterations_estimates (struct loops *loops)
2103
{
2104
  unsigned i;
2105
  struct loop *loop;
2106
 
2107
  for (i = 1; i < loops->num; i++)
2108
    {
2109
      loop = loops->parray[i];
2110
      if (loop)
2111
        free_numbers_of_iterations_estimates_loop (loop);
2112
    }
2113
}
2114
 
2115
/* Substitute value VAL for ssa name NAME inside expressions held
2116
   at LOOP.  */
2117
 
2118
void
2119
substitute_in_loop_info (struct loop *loop, tree name, tree val)
2120
{
2121
  loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
2122
  loop->estimated_nb_iterations
2123
          = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
2124
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.