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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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