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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [tree-chrec.c] - Blame information for rev 38

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Chains of recurrences.
2
   Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3
   Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
/* This file implements operations on chains of recurrences.  Chains
22
   of recurrences are used for modeling evolution functions of scalar
23
   variables.
24
*/
25
 
26
#include "config.h"
27
#include "system.h"
28
#include "coretypes.h"
29
#include "tm.h"
30
#include "ggc.h"
31
#include "tree.h"
32
#include "real.h"
33
#include "diagnostic.h"
34
#include "cfgloop.h"
35
#include "tree-flow.h"
36
#include "tree-chrec.h"
37
#include "tree-pass.h"
38
#include "params.h"
39
#include "tree-scalar-evolution.h"
40
 
41
 
42
 
43
/* Extended folder for chrecs.  */
44
 
45
/* Determines whether CST is not a constant evolution.  */
46
 
47
static inline bool
48
is_not_constant_evolution (tree cst)
49
{
50
  return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
51
}
52
 
53
/* Fold CODE for a polynomial function and a constant.  */
54
 
55
static inline tree
56
chrec_fold_poly_cst (enum tree_code code,
57
                     tree type,
58
                     tree poly,
59
                     tree cst)
60
{
61
  gcc_assert (poly);
62
  gcc_assert (cst);
63
  gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
64
  gcc_assert (!is_not_constant_evolution (cst));
65
  gcc_assert (type == chrec_type (poly));
66
 
67
  switch (code)
68
    {
69
    case PLUS_EXPR:
70
      return build_polynomial_chrec
71
        (CHREC_VARIABLE (poly),
72
         chrec_fold_plus (type, CHREC_LEFT (poly), cst),
73
         CHREC_RIGHT (poly));
74
 
75
    case MINUS_EXPR:
76
      return build_polynomial_chrec
77
        (CHREC_VARIABLE (poly),
78
         chrec_fold_minus (type, CHREC_LEFT (poly), cst),
79
         CHREC_RIGHT (poly));
80
 
81
    case MULT_EXPR:
82
      return build_polynomial_chrec
83
        (CHREC_VARIABLE (poly),
84
         chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
85
         chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
86
 
87
    default:
88
      return chrec_dont_know;
89
    }
90
}
91
 
92
/* Fold the addition of two polynomial functions.  */
93
 
94
static inline tree
95
chrec_fold_plus_poly_poly (enum tree_code code,
96
                           tree type,
97
                           tree poly0,
98
                           tree poly1)
99
{
100
  tree left, right;
101
 
102
  gcc_assert (poly0);
103
  gcc_assert (poly1);
104
  gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
105
  gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
106
  gcc_assert (chrec_type (poly0) == chrec_type (poly1));
107
  gcc_assert (type == chrec_type (poly0));
108
 
109
  /*
110
    {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
111
    {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
112
    {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
113
  if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
114
    {
115
      if (code == PLUS_EXPR)
116
        return build_polynomial_chrec
117
          (CHREC_VARIABLE (poly1),
118
           chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
119
           CHREC_RIGHT (poly1));
120
      else
121
        return build_polynomial_chrec
122
          (CHREC_VARIABLE (poly1),
123
           chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
124
           chrec_fold_multiply (type, CHREC_RIGHT (poly1),
125
                                SCALAR_FLOAT_TYPE_P (type)
126
                                ? build_real (type, dconstm1)
127
                                : build_int_cst_type (type, -1)));
128
    }
129
 
130
  if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
131
    {
132
      if (code == PLUS_EXPR)
133
        return build_polynomial_chrec
134
          (CHREC_VARIABLE (poly0),
135
           chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
136
           CHREC_RIGHT (poly0));
137
      else
138
        return build_polynomial_chrec
139
          (CHREC_VARIABLE (poly0),
140
           chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
141
           CHREC_RIGHT (poly0));
142
    }
143
 
144
  if (code == PLUS_EXPR)
145
    {
146
      left = chrec_fold_plus
147
        (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
148
      right = chrec_fold_plus
149
        (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
150
    }
151
  else
152
    {
153
      left = chrec_fold_minus
154
        (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
155
      right = chrec_fold_minus
156
        (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
157
    }
158
 
159
  if (chrec_zerop (right))
160
    return left;
161
  else
162
    return build_polynomial_chrec
163
      (CHREC_VARIABLE (poly0), left, right);
164
}
165
 
166
 
167
 
168
/* Fold the multiplication of two polynomial functions.  */
169
 
170
static inline tree
171
chrec_fold_multiply_poly_poly (tree type,
172
                               tree poly0,
173
                               tree poly1)
174
{
175
  tree t0, t1, t2;
176
  int var;
177
 
178
  gcc_assert (poly0);
179
  gcc_assert (poly1);
180
  gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
181
  gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
182
  gcc_assert (chrec_type (poly0) == chrec_type (poly1));
183
  gcc_assert (type == chrec_type (poly0));
184
 
185
  /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
186
     {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
187
     {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
188
  if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
189
    /* poly0 is a constant wrt. poly1.  */
190
    return build_polynomial_chrec
191
      (CHREC_VARIABLE (poly1),
192
       chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
193
       CHREC_RIGHT (poly1));
194
 
195
  if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
196
    /* poly1 is a constant wrt. poly0.  */
197
    return build_polynomial_chrec
198
      (CHREC_VARIABLE (poly0),
199
       chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
200
       CHREC_RIGHT (poly0));
201
 
202
  /* poly0 and poly1 are two polynomials in the same variable,
203
     {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
204
 
205
  /* "a*c".  */
206
  t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
207
 
208
  /* "a*d + b*c + b*d".  */
209
  t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
210
  t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
211
                                                       CHREC_RIGHT (poly0),
212
                                                       CHREC_LEFT (poly1)));
213
  t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
214
                                                       CHREC_RIGHT (poly0),
215
                                                       CHREC_RIGHT (poly1)));
216
  /* "2*b*d".  */
217
  t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
218
  t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
219
                            ? build_real (type, dconst2)
220
                            : build_int_cst (type, 2), t2);
221
 
222
  var = CHREC_VARIABLE (poly0);
223
  return build_polynomial_chrec (var, t0,
224
                                 build_polynomial_chrec (var, t1, t2));
225
}
226
 
227
/* When the operands are automatically_generated_chrec_p, the fold has
228
   to respect the semantics of the operands.  */
229
 
230
static inline tree
231
chrec_fold_automatically_generated_operands (tree op0,
232
                                             tree op1)
233
{
234
  if (op0 == chrec_dont_know
235
      || op1 == chrec_dont_know)
236
    return chrec_dont_know;
237
 
238
  if (op0 == chrec_known
239
      || op1 == chrec_known)
240
    return chrec_known;
241
 
242
  if (op0 == chrec_not_analyzed_yet
243
      || op1 == chrec_not_analyzed_yet)
244
    return chrec_not_analyzed_yet;
245
 
246
  /* The default case produces a safe result.  */
247
  return chrec_dont_know;
248
}
249
 
250
/* Fold the addition of two chrecs.  */
251
 
252
static tree
253
chrec_fold_plus_1 (enum tree_code code, tree type,
254
                   tree op0, tree op1)
255
{
256
  if (automatically_generated_chrec_p (op0)
257
      || automatically_generated_chrec_p (op1))
258
    return chrec_fold_automatically_generated_operands (op0, op1);
259
 
260
  switch (TREE_CODE (op0))
261
    {
262
    case POLYNOMIAL_CHREC:
263
      switch (TREE_CODE (op1))
264
        {
265
        case POLYNOMIAL_CHREC:
266
          return chrec_fold_plus_poly_poly (code, type, op0, op1);
267
 
268
        default:
269
          if (code == PLUS_EXPR)
270
            return build_polynomial_chrec
271
              (CHREC_VARIABLE (op0),
272
               chrec_fold_plus (type, CHREC_LEFT (op0), op1),
273
               CHREC_RIGHT (op0));
274
          else
275
            return build_polynomial_chrec
276
              (CHREC_VARIABLE (op0),
277
               chrec_fold_minus (type, CHREC_LEFT (op0), op1),
278
               CHREC_RIGHT (op0));
279
        }
280
 
281
    default:
282
      switch (TREE_CODE (op1))
283
        {
284
        case POLYNOMIAL_CHREC:
285
          if (code == PLUS_EXPR)
286
            return build_polynomial_chrec
287
              (CHREC_VARIABLE (op1),
288
               chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
289
               CHREC_RIGHT (op1));
290
          else
291
            return build_polynomial_chrec
292
              (CHREC_VARIABLE (op1),
293
               chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
294
               chrec_fold_multiply (type, CHREC_RIGHT (op1),
295
                                    SCALAR_FLOAT_TYPE_P (type)
296
                                    ? build_real (type, dconstm1)
297
                                    : build_int_cst_type (type, -1)));
298
 
299
        default:
300
          {
301
            int size = 0;
302
            if ((tree_contains_chrecs (op0, &size)
303
                 || tree_contains_chrecs (op1, &size))
304
                && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
305
              return build2 (code, type, op0, op1);
306
            else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
307
              return fold_build2 (code, type,
308
                                  fold_convert (type, op0),
309
                                  fold_convert (type, op1));
310
            else
311
              return chrec_dont_know;
312
          }
313
        }
314
    }
315
}
316
 
317
/* Fold the addition of two chrecs.  */
318
 
319
tree
320
chrec_fold_plus (tree type,
321
                 tree op0,
322
                 tree op1)
323
{
324
  if (automatically_generated_chrec_p (op0)
325
      || automatically_generated_chrec_p (op1))
326
    return chrec_fold_automatically_generated_operands (op0, op1);
327
 
328
  if (integer_zerop (op0))
329
    return op1;
330
  if (integer_zerop (op1))
331
    return op0;
332
 
333
  return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
334
}
335
 
336
/* Fold the subtraction of two chrecs.  */
337
 
338
tree
339
chrec_fold_minus (tree type,
340
                  tree op0,
341
                  tree op1)
342
{
343
  if (automatically_generated_chrec_p (op0)
344
      || automatically_generated_chrec_p (op1))
345
    return chrec_fold_automatically_generated_operands (op0, op1);
346
 
347
  if (integer_zerop (op1))
348
    return op0;
349
 
350
  return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
351
}
352
 
353
/* Fold the multiplication of two chrecs.  */
354
 
355
tree
356
chrec_fold_multiply (tree type,
357
                     tree op0,
358
                     tree op1)
359
{
360
  if (automatically_generated_chrec_p (op0)
361
      || automatically_generated_chrec_p (op1))
362
    return chrec_fold_automatically_generated_operands (op0, op1);
363
 
364
  switch (TREE_CODE (op0))
365
    {
366
    case POLYNOMIAL_CHREC:
367
      switch (TREE_CODE (op1))
368
        {
369
        case POLYNOMIAL_CHREC:
370
          return chrec_fold_multiply_poly_poly (type, op0, op1);
371
 
372
        default:
373
          if (integer_onep (op1))
374
            return op0;
375
          if (integer_zerop (op1))
376
            return build_int_cst (type, 0);
377
 
378
          return build_polynomial_chrec
379
            (CHREC_VARIABLE (op0),
380
             chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
381
             chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
382
        }
383
 
384
    default:
385
      if (integer_onep (op0))
386
        return op1;
387
 
388
      if (integer_zerop (op0))
389
        return build_int_cst (type, 0);
390
 
391
      switch (TREE_CODE (op1))
392
        {
393
        case POLYNOMIAL_CHREC:
394
          return build_polynomial_chrec
395
            (CHREC_VARIABLE (op1),
396
             chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
397
             chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
398
 
399
        default:
400
          if (integer_onep (op1))
401
            return op0;
402
          if (integer_zerop (op1))
403
            return build_int_cst (type, 0);
404
          return fold_build2 (MULT_EXPR, type, op0, op1);
405
        }
406
    }
407
}
408
 
409
 
410
 
411
/* Operations.  */
412
 
413
/* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
414
   calculation overflows, otherwise return C(n,k) with type TYPE.  */
415
 
416
static tree
417
tree_fold_binomial (tree type, tree n, unsigned int k)
418
{
419
  unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
420
  HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
421
  unsigned int i;
422
  tree res;
423
 
424
  /* Handle the most frequent cases.  */
425
  if (k == 0)
426
    return build_int_cst (type, 1);
427
  if (k == 1)
428
    return fold_convert (type, n);
429
 
430
  /* Check that k <= n.  */
431
  if (TREE_INT_CST_HIGH (n) == 0
432
      && TREE_INT_CST_LOW (n) < k)
433
    return NULL_TREE;
434
 
435
  /* Numerator = n.  */
436
  lnum = TREE_INT_CST_LOW (n);
437
  hnum = TREE_INT_CST_HIGH (n);
438
 
439
  /* Denominator = 2.  */
440
  ldenom = 2;
441
  hdenom = 0;
442
 
443
  /* Index = Numerator-1.  */
444
  if (lnum == 0)
445
    {
446
      hidx = hnum - 1;
447
      lidx = ~ (unsigned HOST_WIDE_INT) 0;
448
    }
449
  else
450
    {
451
      hidx = hnum;
452
      lidx = lnum - 1;
453
    }
454
 
455
  /* Numerator = Numerator*Index = n*(n-1).  */
456
  if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
457
    return NULL_TREE;
458
 
459
  for (i = 3; i <= k; i++)
460
    {
461
      /* Index--.  */
462
      if (lidx == 0)
463
        {
464
          hidx--;
465
          lidx = ~ (unsigned HOST_WIDE_INT) 0;
466
        }
467
      else
468
        lidx--;
469
 
470
      /* Numerator *= Index.  */
471
      if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
472
        return NULL_TREE;
473
 
474
      /* Denominator *= i.  */
475
      mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
476
    }
477
 
478
  /* Result = Numerator / Denominator.  */
479
  div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
480
                        &lres, &hres, &ldum, &hdum);
481
 
482
  res = build_int_cst_wide (type, lres, hres);
483
  return int_fits_type_p (res, type) ? res : NULL_TREE;
484
}
485
 
486
/* Helper function.  Use the Newton's interpolating formula for
487
   evaluating the value of the evolution function.  */
488
 
489
static tree
490
chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
491
{
492
  tree arg0, arg1, binomial_n_k;
493
  tree type = TREE_TYPE (chrec);
494
 
495
  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
496
         && CHREC_VARIABLE (chrec) > var)
497
    chrec = CHREC_LEFT (chrec);
498
 
499
  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
500
      && CHREC_VARIABLE (chrec) == var)
501
    {
502
      arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
503
      if (arg0 == chrec_dont_know)
504
        return chrec_dont_know;
505
      binomial_n_k = tree_fold_binomial (type, n, k);
506
      if (!binomial_n_k)
507
        return chrec_dont_know;
508
      arg1 = fold_build2 (MULT_EXPR, type,
509
                          CHREC_LEFT (chrec), binomial_n_k);
510
      return chrec_fold_plus (type, arg0, arg1);
511
    }
512
 
513
  binomial_n_k = tree_fold_binomial (type, n, k);
514
  if (!binomial_n_k)
515
    return chrec_dont_know;
516
 
517
  return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
518
}
519
 
520
/* Evaluates "CHREC (X)" when the varying variable is VAR.
521
   Example:  Given the following parameters,
522
 
523
   var = 1
524
   chrec = {3, +, 4}_1
525
   x = 10
526
 
527
   The result is given by the Newton's interpolating formula:
528
   3 * \binom{10}{0} + 4 * \binom{10}{1}.
529
*/
530
 
531
tree
532
chrec_apply (unsigned var,
533
             tree chrec,
534
             tree x)
535
{
536
  tree type = chrec_type (chrec);
537
  tree res = chrec_dont_know;
538
 
539
  if (automatically_generated_chrec_p (chrec)
540
      || automatically_generated_chrec_p (x)
541
 
542
      /* When the symbols are defined in an outer loop, it is possible
543
         to symbolically compute the apply, since the symbols are
544
         constants with respect to the varying loop.  */
545
      || chrec_contains_symbols_defined_in_loop (chrec, var))
546
    return chrec_dont_know;
547
 
548
  if (dump_file && (dump_flags & TDF_DETAILS))
549
    fprintf (dump_file, "(chrec_apply \n");
550
 
551
  if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
552
    x = build_real_from_int_cst (type, x);
553
 
554
  if (evolution_function_is_affine_p (chrec))
555
    {
556
      /* "{a, +, b} (x)"  ->  "a + b*x".  */
557
      x = chrec_convert (type, x, NULL_TREE);
558
      res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
559
      if (!integer_zerop (CHREC_LEFT (chrec)))
560
        res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
561
    }
562
 
563
  else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
564
    res = chrec;
565
 
566
  else if (TREE_CODE (x) == INTEGER_CST
567
           && tree_int_cst_sgn (x) == 1)
568
    /* testsuite/.../ssa-chrec-38.c.  */
569
    res = chrec_evaluate (var, chrec, x, 0);
570
  else
571
    res = chrec_dont_know;
572
 
573
  if (dump_file && (dump_flags & TDF_DETAILS))
574
    {
575
      fprintf (dump_file, "  (varying_loop = %d\n", var);
576
      fprintf (dump_file, ")\n  (chrec = ");
577
      print_generic_expr (dump_file, chrec, 0);
578
      fprintf (dump_file, ")\n  (x = ");
579
      print_generic_expr (dump_file, x, 0);
580
      fprintf (dump_file, ")\n  (res = ");
581
      print_generic_expr (dump_file, res, 0);
582
      fprintf (dump_file, "))\n");
583
    }
584
 
585
  return res;
586
}
587
 
588
/* Replaces the initial condition in CHREC with INIT_COND.  */
589
 
590
tree
591
chrec_replace_initial_condition (tree chrec,
592
                                 tree init_cond)
593
{
594
  if (automatically_generated_chrec_p (chrec))
595
    return chrec;
596
 
597
  gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
598
 
599
  switch (TREE_CODE (chrec))
600
    {
601
    case POLYNOMIAL_CHREC:
602
      return build_polynomial_chrec
603
        (CHREC_VARIABLE (chrec),
604
         chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
605
         CHREC_RIGHT (chrec));
606
 
607
    default:
608
      return init_cond;
609
    }
610
}
611
 
612
/* Returns the initial condition of a given CHREC.  */
613
 
614
tree
615
initial_condition (tree chrec)
616
{
617
  if (automatically_generated_chrec_p (chrec))
618
    return chrec;
619
 
620
  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
621
    return initial_condition (CHREC_LEFT (chrec));
622
  else
623
    return chrec;
624
}
625
 
626
/* Returns a univariate function that represents the evolution in
627
   LOOP_NUM.  Mask the evolution of any other loop.  */
628
 
629
tree
630
hide_evolution_in_other_loops_than_loop (tree chrec,
631
                                         unsigned loop_num)
632
{
633
  if (automatically_generated_chrec_p (chrec))
634
    return chrec;
635
 
636
  switch (TREE_CODE (chrec))
637
    {
638
    case POLYNOMIAL_CHREC:
639
      if (CHREC_VARIABLE (chrec) == loop_num)
640
        return build_polynomial_chrec
641
          (loop_num,
642
           hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
643
                                                    loop_num),
644
           CHREC_RIGHT (chrec));
645
 
646
      else if (CHREC_VARIABLE (chrec) < loop_num)
647
        /* There is no evolution in this loop.  */
648
        return initial_condition (chrec);
649
 
650
      else
651
        return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
652
                                                        loop_num);
653
 
654
    default:
655
      return chrec;
656
    }
657
}
658
 
659
/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
660
   true, otherwise returns the initial condition in LOOP_NUM.  */
661
 
662
static tree
663
chrec_component_in_loop_num (tree chrec,
664
                             unsigned loop_num,
665
                             bool right)
666
{
667
  tree component;
668
 
669
  if (automatically_generated_chrec_p (chrec))
670
    return chrec;
671
 
672
  switch (TREE_CODE (chrec))
673
    {
674
    case POLYNOMIAL_CHREC:
675
      if (CHREC_VARIABLE (chrec) == loop_num)
676
        {
677
          if (right)
678
            component = CHREC_RIGHT (chrec);
679
          else
680
            component = CHREC_LEFT (chrec);
681
 
682
          if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
683
              || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
684
            return component;
685
 
686
          else
687
            return build_polynomial_chrec
688
              (loop_num,
689
               chrec_component_in_loop_num (CHREC_LEFT (chrec),
690
                                            loop_num,
691
                                            right),
692
               component);
693
        }
694
 
695
      else if (CHREC_VARIABLE (chrec) < loop_num)
696
        /* There is no evolution part in this loop.  */
697
        return NULL_TREE;
698
 
699
      else
700
        return chrec_component_in_loop_num (CHREC_LEFT (chrec),
701
                                            loop_num,
702
                                            right);
703
 
704
     default:
705
      if (right)
706
        return NULL_TREE;
707
      else
708
        return chrec;
709
    }
710
}
711
 
712
/* Returns the evolution part in LOOP_NUM.  Example: the call
713
   evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
714
   {1, +, 2}_1  */
715
 
716
tree
717
evolution_part_in_loop_num (tree chrec,
718
                            unsigned loop_num)
719
{
720
  return chrec_component_in_loop_num (chrec, loop_num, true);
721
}
722
 
723
/* Returns the initial condition in LOOP_NUM.  Example: the call
724
   initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
725
   {0, +, 1}_1  */
726
 
727
tree
728
initial_condition_in_loop_num (tree chrec,
729
                               unsigned loop_num)
730
{
731
  return chrec_component_in_loop_num (chrec, loop_num, false);
732
}
733
 
734
/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
735
   This function is essentially used for setting the evolution to
736
   chrec_dont_know, for example after having determined that it is
737
   impossible to say how many times a loop will execute.  */
738
 
739
tree
740
reset_evolution_in_loop (unsigned loop_num,
741
                         tree chrec,
742
                         tree new_evol)
743
{
744
  gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
745
 
746
  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
747
      && CHREC_VARIABLE (chrec) > loop_num)
748
    {
749
      tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
750
                                           new_evol);
751
      tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
752
                                            new_evol);
753
      return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
754
                     build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
755
                     left, right);
756
    }
757
 
758
  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
759
         && CHREC_VARIABLE (chrec) == loop_num)
760
    chrec = CHREC_LEFT (chrec);
761
 
762
  return build_polynomial_chrec (loop_num, chrec, new_evol);
763
}
764
 
765
/* Merges two evolution functions that were found by following two
766
   alternate paths of a conditional expression.  */
767
 
768
tree
769
chrec_merge (tree chrec1,
770
             tree chrec2)
771
{
772
  if (chrec1 == chrec_dont_know
773
      || chrec2 == chrec_dont_know)
774
    return chrec_dont_know;
775
 
776
  if (chrec1 == chrec_known
777
      || chrec2 == chrec_known)
778
    return chrec_known;
779
 
780
  if (chrec1 == chrec_not_analyzed_yet)
781
    return chrec2;
782
  if (chrec2 == chrec_not_analyzed_yet)
783
    return chrec1;
784
 
785
  if (eq_evolutions_p (chrec1, chrec2))
786
    return chrec1;
787
 
788
  return chrec_dont_know;
789
}
790
 
791
 
792
 
793
/* Observers.  */
794
 
795
/* Helper function for is_multivariate_chrec.  */
796
 
797
static bool
798
is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
799
{
800
  if (chrec == NULL_TREE)
801
    return false;
802
 
803
  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
804
    {
805
      if (CHREC_VARIABLE (chrec) != rec_var)
806
        return true;
807
      else
808
        return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
809
                || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
810
    }
811
  else
812
    return false;
813
}
814
 
815
/* Determine whether the given chrec is multivariate or not.  */
816
 
817
bool
818
is_multivariate_chrec (tree chrec)
819
{
820
  if (chrec == NULL_TREE)
821
    return false;
822
 
823
  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
824
    return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
825
                                       CHREC_VARIABLE (chrec))
826
            || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
827
                                          CHREC_VARIABLE (chrec)));
828
  else
829
    return false;
830
}
831
 
832
/* Determines whether the chrec contains symbolic names or not.  */
833
 
834
bool
835
chrec_contains_symbols (tree chrec)
836
{
837
  if (chrec == NULL_TREE)
838
    return false;
839
 
840
  if (TREE_CODE (chrec) == SSA_NAME
841
      || TREE_CODE (chrec) == VAR_DECL
842
      || TREE_CODE (chrec) == PARM_DECL
843
      || TREE_CODE (chrec) == FUNCTION_DECL
844
      || TREE_CODE (chrec) == LABEL_DECL
845
      || TREE_CODE (chrec) == RESULT_DECL
846
      || TREE_CODE (chrec) == FIELD_DECL)
847
    return true;
848
 
849
  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
850
    {
851
    case 3:
852
      if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
853
        return true;
854
 
855
    case 2:
856
      if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
857
        return true;
858
 
859
    case 1:
860
      if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
861
        return true;
862
 
863
    default:
864
      return false;
865
    }
866
}
867
 
868
/* Determines whether the chrec contains undetermined coefficients.  */
869
 
870
bool
871
chrec_contains_undetermined (tree chrec)
872
{
873
  if (chrec == chrec_dont_know
874
      || chrec == chrec_not_analyzed_yet
875
      || chrec == NULL_TREE)
876
    return true;
877
 
878
  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
879
    {
880
    case 3:
881
      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
882
        return true;
883
 
884
    case 2:
885
      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
886
        return true;
887
 
888
    case 1:
889
      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
890
        return true;
891
 
892
    default:
893
      return false;
894
    }
895
}
896
 
897
/* Determines whether the tree EXPR contains chrecs, and increment
898
   SIZE if it is not a NULL pointer by an estimation of the depth of
899
   the tree.  */
900
 
901
bool
902
tree_contains_chrecs (tree expr, int *size)
903
{
904
  if (expr == NULL_TREE)
905
    return false;
906
 
907
  if (size)
908
    (*size)++;
909
 
910
  if (tree_is_chrec (expr))
911
    return true;
912
 
913
  switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
914
    {
915
    case 3:
916
      if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
917
        return true;
918
 
919
    case 2:
920
      if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
921
        return true;
922
 
923
    case 1:
924
      if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
925
        return true;
926
 
927
    default:
928
      return false;
929
    }
930
}
931
 
932
/* Recursive helper function.  */
933
 
934
static bool
935
evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
936
{
937
  if (evolution_function_is_constant_p (chrec))
938
    return true;
939
 
940
  if (TREE_CODE (chrec) == SSA_NAME
941
      && expr_invariant_in_loop_p (current_loops->parray[loopnum],
942
                                   chrec))
943
    return true;
944
 
945
  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
946
    {
947
      if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
948
          || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
949
                                                     loopnum)
950
          || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
951
                                                     loopnum))
952
        return false;
953
      return true;
954
    }
955
 
956
  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
957
    {
958
    case 2:
959
      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
960
                                                  loopnum))
961
        return false;
962
 
963
    case 1:
964
      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
965
                                                  loopnum))
966
        return false;
967
      return true;
968
 
969
    default:
970
      return false;
971
    }
972
 
973
  return false;
974
}
975
 
976
/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
977
 
978
bool
979
evolution_function_is_invariant_p (tree chrec, int loopnum)
980
{
981
  if (evolution_function_is_constant_p (chrec))
982
    return true;
983
 
984
  if (current_loops != NULL)
985
    return evolution_function_is_invariant_rec_p (chrec, loopnum);
986
 
987
  return false;
988
}
989
 
990
/* Determine whether the given tree is an affine multivariate
991
   evolution.  */
992
 
993
bool
994
evolution_function_is_affine_multivariate_p (tree chrec)
995
{
996
  if (chrec == NULL_TREE)
997
    return false;
998
 
999
  switch (TREE_CODE (chrec))
1000
    {
1001
    case POLYNOMIAL_CHREC:
1002
      if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
1003
        {
1004
          if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
1005
            return true;
1006
          else
1007
            {
1008
              if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1009
                  && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1010
                     != CHREC_VARIABLE (chrec)
1011
                  && evolution_function_is_affine_multivariate_p
1012
                  (CHREC_RIGHT (chrec)))
1013
                return true;
1014
              else
1015
                return false;
1016
            }
1017
        }
1018
      else
1019
        {
1020
          if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
1021
              && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1022
              && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1023
              && evolution_function_is_affine_multivariate_p
1024
              (CHREC_LEFT (chrec)))
1025
            return true;
1026
          else
1027
            return false;
1028
        }
1029
 
1030
    default:
1031
      return false;
1032
    }
1033
}
1034
 
1035
/* Determine whether the given tree is a function in zero or one
1036
   variables.  */
1037
 
1038
bool
1039
evolution_function_is_univariate_p (tree chrec)
1040
{
1041
  if (chrec == NULL_TREE)
1042
    return true;
1043
 
1044
  switch (TREE_CODE (chrec))
1045
    {
1046
    case POLYNOMIAL_CHREC:
1047
      switch (TREE_CODE (CHREC_LEFT (chrec)))
1048
        {
1049
        case POLYNOMIAL_CHREC:
1050
          if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1051
            return false;
1052
          if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1053
            return false;
1054
          break;
1055
 
1056
        default:
1057
          break;
1058
        }
1059
 
1060
      switch (TREE_CODE (CHREC_RIGHT (chrec)))
1061
        {
1062
        case POLYNOMIAL_CHREC:
1063
          if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1064
            return false;
1065
          if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1066
            return false;
1067
          break;
1068
 
1069
        default:
1070
          break;
1071
        }
1072
 
1073
    default:
1074
      return true;
1075
    }
1076
}
1077
 
1078
/* Returns the number of variables of CHREC.  Example: the call
1079
   nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1080
 
1081
unsigned
1082
nb_vars_in_chrec (tree chrec)
1083
{
1084
  if (chrec == NULL_TREE)
1085
    return 0;
1086
 
1087
  switch (TREE_CODE (chrec))
1088
    {
1089
    case POLYNOMIAL_CHREC:
1090
      return 1 + nb_vars_in_chrec
1091
        (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1092
 
1093
    default:
1094
      return 0;
1095
    }
1096
}
1097
 
1098
/* Returns true if TYPE is a type in that we cannot directly perform
1099
   arithmetics, even though it is a scalar type.  */
1100
 
1101
static bool
1102
avoid_arithmetics_in_type_p (tree type)
1103
{
1104
  /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1105
     in the subtype, but a base type must be used, and the result then can
1106
     be casted to the subtype.  */
1107
  if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
1108
    return true;
1109
 
1110
  return false;
1111
}
1112
 
1113
static tree chrec_convert_1 (tree, tree, tree, bool);
1114
 
1115
/* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1116
   the scev corresponds to.  AT_STMT is the statement at that the scev is
1117
   evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1118
   the rules for overflow of the given language apply (e.g., that signed
1119
   arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1120
   tests, but also to enforce that the result follows them.  Returns true if the
1121
   conversion succeeded, false otherwise.  */
1122
 
1123
bool
1124
convert_affine_scev (struct loop *loop, tree type,
1125
                     tree *base, tree *step, tree at_stmt,
1126
                     bool use_overflow_semantics)
1127
{
1128
  tree ct = TREE_TYPE (*step);
1129
  bool enforce_overflow_semantics;
1130
  bool must_check_src_overflow, must_check_rslt_overflow;
1131
  tree new_base, new_step;
1132
 
1133
  /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1134
  if (avoid_arithmetics_in_type_p (type))
1135
    return false;
1136
 
1137
  /* In general,
1138
     (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1139
     but we must check some assumptions.
1140
 
1141
     1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1142
        of CT is smaller than the precision of TYPE.  For example, when we
1143
        cast unsigned char [254, +, 1] to unsigned, the values on left side
1144
        are 254, 255, 0, 1, ..., but those on the right side are
1145
        254, 255, 256, 257, ...
1146
     2) In case that we must also preserve the fact that signed ivs do not
1147
        overflow, we must additionally check that the new iv does not wrap.
1148
        For example, unsigned char [125, +, 1] casted to signed char could
1149
        become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1150
        which would confuse optimizers that assume that this does not
1151
        happen.  */
1152
  must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1153
 
1154
  enforce_overflow_semantics = (use_overflow_semantics
1155
                                && nowrap_type_p (type));
1156
  if (enforce_overflow_semantics)
1157
    {
1158
      /* We can avoid checking whether the result overflows in the following
1159
         cases:
1160
 
1161
         -- must_check_src_overflow is true, and the range of TYPE is superset
1162
            of the range of CT -- i.e., in all cases except if CT signed and
1163
            TYPE unsigned.
1164
         -- both CT and TYPE have the same precision and signedness, and we
1165
            verify instead that the source does not overflow (this may be
1166
            easier than verifying it for the result, as we may use the
1167
            information about the semantics of overflow in CT).  */
1168
      if (must_check_src_overflow)
1169
        {
1170
          if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1171
            must_check_rslt_overflow = true;
1172
          else
1173
            must_check_rslt_overflow = false;
1174
        }
1175
      else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1176
               && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1177
        {
1178
          must_check_rslt_overflow = false;
1179
          must_check_src_overflow = true;
1180
        }
1181
      else
1182
        must_check_rslt_overflow = true;
1183
    }
1184
  else
1185
    must_check_rslt_overflow = false;
1186
 
1187
  if (must_check_src_overflow
1188
      && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1189
                                use_overflow_semantics))
1190
    return false;
1191
 
1192
  new_base = chrec_convert_1 (type, *base, at_stmt,
1193
                              use_overflow_semantics);
1194
  /* The step must be sign extended, regardless of the signedness
1195
     of CT and TYPE.  This only needs to be handled specially when
1196
     CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1197
     (with values 100, 99, 98, ...) from becoming signed or unsigned
1198
     [100, +, 255] with values 100, 355, ...; the sign-extension is
1199
     performed by default when CT is signed.  */
1200
  new_step = *step;
1201
  if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1202
    new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1203
                                use_overflow_semantics);
1204
  new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
1205
 
1206
  if (automatically_generated_chrec_p (new_base)
1207
      || automatically_generated_chrec_p (new_step))
1208
    return false;
1209
 
1210
  if (must_check_rslt_overflow
1211
      /* Note that in this case we cannot use the fact that signed variables
1212
         do not overflow, as this is what we are verifying for the new iv.  */
1213
      && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1214
    return false;
1215
 
1216
  *base = new_base;
1217
  *step = new_step;
1218
  return true;
1219
}
1220
 
1221
 
1222
/* Convert CHREC to TYPE.  When the analyzer knows the context in
1223
   which the CHREC is built, it sets AT_STMT to the statement that
1224
   contains the definition of the analyzed variable, otherwise the
1225
   conversion is less accurate: the information is used for
1226
   determining a more accurate estimation of the number of iterations.
1227
   By default AT_STMT could be safely set to NULL_TREE.
1228
 
1229
   The following rule is always true: TREE_TYPE (chrec) ==
1230
   TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1231
   An example of what could happen when adding two chrecs and the type
1232
   of the CHREC_RIGHT is different than CHREC_LEFT is:
1233
 
1234
   {(uint) 0, +, (uchar) 10} +
1235
   {(uint) 0, +, (uchar) 250}
1236
 
1237
   that would produce a wrong result if CHREC_RIGHT is not (uint):
1238
 
1239
   {(uint) 0, +, (uchar) 4}
1240
 
1241
   instead of
1242
 
1243
   {(uint) 0, +, (uint) 260}
1244
*/
1245
 
1246
tree
1247
chrec_convert (tree type, tree chrec, tree at_stmt)
1248
{
1249
  return chrec_convert_1 (type, chrec, at_stmt, true);
1250
}
1251
 
1252
/* Convert CHREC to TYPE.  When the analyzer knows the context in
1253
   which the CHREC is built, it sets AT_STMT to the statement that
1254
   contains the definition of the analyzed variable, otherwise the
1255
   conversion is less accurate: the information is used for
1256
   determining a more accurate estimation of the number of iterations.
1257
   By default AT_STMT could be safely set to NULL_TREE.
1258
 
1259
   USE_OVERFLOW_SEMANTICS is true if this function should assume that
1260
   the rules for overflow of the given language apply (e.g., that signed
1261
   arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1262
   tests, but also to enforce that the result follows them.  */
1263
 
1264
static tree
1265
chrec_convert_1 (tree type, tree chrec, tree at_stmt,
1266
                 bool use_overflow_semantics)
1267
{
1268
  tree ct, res;
1269
  tree base, step;
1270
  struct loop *loop;
1271
 
1272
  if (automatically_generated_chrec_p (chrec))
1273
    return chrec;
1274
 
1275
  ct = chrec_type (chrec);
1276
  if (ct == type)
1277
    return chrec;
1278
 
1279
  if (!evolution_function_is_affine_p (chrec))
1280
    goto keep_cast;
1281
 
1282
  loop = current_loops->parray[CHREC_VARIABLE (chrec)];
1283
  base = CHREC_LEFT (chrec);
1284
  step = CHREC_RIGHT (chrec);
1285
 
1286
  if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1287
                           use_overflow_semantics))
1288
    return build_polynomial_chrec (loop->num, base, step);
1289
 
1290
  /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1291
keep_cast:
1292
  res = fold_convert (type, chrec);
1293
 
1294
  /* Don't propagate overflows.  */
1295
  if (CONSTANT_CLASS_P (res))
1296
    {
1297
      TREE_CONSTANT_OVERFLOW (res) = 0;
1298
      TREE_OVERFLOW (res) = 0;
1299
    }
1300
 
1301
  /* But reject constants that don't fit in their type after conversion.
1302
     This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1303
     natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1304
     and can cause problems later when computing niters of loops.  Note
1305
     that we don't do the check before converting because we don't want
1306
     to reject conversions of negative chrecs to unsigned types.  */
1307
  if (TREE_CODE (res) == INTEGER_CST
1308
      && TREE_CODE (type) == INTEGER_TYPE
1309
      && !int_fits_type_p (res, type))
1310
    res = chrec_dont_know;
1311
 
1312
  return res;
1313
}
1314
 
1315
/* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1316
   chrec if something else than what chrec_convert would do happens, NULL_TREE
1317
   otherwise.  */
1318
 
1319
tree
1320
chrec_convert_aggressive (tree type, tree chrec)
1321
{
1322
  tree inner_type, left, right, lc, rc;
1323
 
1324
  if (automatically_generated_chrec_p (chrec)
1325
      || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1326
    return NULL_TREE;
1327
 
1328
  inner_type = TREE_TYPE (chrec);
1329
  if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1330
    return NULL_TREE;
1331
 
1332
  /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1333
  if (avoid_arithmetics_in_type_p (type))
1334
    return NULL_TREE;
1335
 
1336
  left = CHREC_LEFT (chrec);
1337
  right = CHREC_RIGHT (chrec);
1338
  lc = chrec_convert_aggressive (type, left);
1339
  if (!lc)
1340
    lc = chrec_convert (type, left, NULL_TREE);
1341
  rc = chrec_convert_aggressive (type, right);
1342
  if (!rc)
1343
    rc = chrec_convert (type, right, NULL_TREE);
1344
 
1345
  return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1346
}
1347
 
1348
/* Returns true when CHREC0 == CHREC1.  */
1349
 
1350
bool
1351
eq_evolutions_p (tree chrec0,
1352
                 tree chrec1)
1353
{
1354
  if (chrec0 == NULL_TREE
1355
      || chrec1 == NULL_TREE
1356
      || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1357
    return false;
1358
 
1359
  if (chrec0 == chrec1)
1360
    return true;
1361
 
1362
  switch (TREE_CODE (chrec0))
1363
    {
1364
    case INTEGER_CST:
1365
      return operand_equal_p (chrec0, chrec1, 0);
1366
 
1367
    case POLYNOMIAL_CHREC:
1368
      return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1369
              && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1370
              && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1371
    default:
1372
      return false;
1373
    }
1374
}
1375
 
1376
/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1377
   EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1378
   which of these cases happens.  */
1379
 
1380
enum ev_direction
1381
scev_direction (tree chrec)
1382
{
1383
  tree step;
1384
 
1385
  if (!evolution_function_is_affine_p (chrec))
1386
    return EV_DIR_UNKNOWN;
1387
 
1388
  step = CHREC_RIGHT (chrec);
1389
  if (TREE_CODE (step) != INTEGER_CST)
1390
    return EV_DIR_UNKNOWN;
1391
 
1392
  if (tree_int_cst_sign_bit (step))
1393
    return EV_DIR_DECREASES;
1394
  else
1395
    return EV_DIR_GROWS;
1396
}

powered by: WebSVN 2.1.0

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