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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-scalar-evolution.c] - Blame information for rev 729

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

Line No. Rev Author Line
1 684 jeremybenn
/* Scalar evolution detector.
2
   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3
   Free Software Foundation, Inc.
4
   Contributed by Sebastian Pop <s.pop@laposte.net>
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
/*
23
   Description:
24
 
25
   This pass analyzes the evolution of scalar variables in loop
26
   structures.  The algorithm is based on the SSA representation,
27
   and on the loop hierarchy tree.  This algorithm is not based on
28
   the notion of versions of a variable, as it was the case for the
29
   previous implementations of the scalar evolution algorithm, but
30
   it assumes that each defined name is unique.
31
 
32
   The notation used in this file is called "chains of recurrences",
33
   and has been proposed by Eugene Zima, Robert Van Engelen, and
34
   others for describing induction variables in programs.  For example
35
   "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36
   when entering in the loop_1 and has a step 2 in this loop, in other
37
   words "for (b = 0; b < N; b+=2);".  Note that the coefficients of
38
   this chain of recurrence (or chrec [shrek]) can contain the name of
39
   other variables, in which case they are called parametric chrecs.
40
   For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41
   is the value of "a".  In most of the cases these parametric chrecs
42
   are fully instantiated before their use because symbolic names can
43
   hide some difficult cases such as self-references described later
44
   (see the Fibonacci example).
45
 
46
   A short sketch of the algorithm is:
47
 
48
   Given a scalar variable to be analyzed, follow the SSA edge to
49
   its definition:
50
 
51
   - When the definition is a GIMPLE_ASSIGN: if the right hand side
52
   (RHS) of the definition cannot be statically analyzed, the answer
53
   of the analyzer is: "don't know".
54
   Otherwise, for all the variables that are not yet analyzed in the
55
   RHS, try to determine their evolution, and finally try to
56
   evaluate the operation of the RHS that gives the evolution
57
   function of the analyzed variable.
58
 
59
   - When the definition is a condition-phi-node: determine the
60
   evolution function for all the branches of the phi node, and
61
   finally merge these evolutions (see chrec_merge).
62
 
63
   - When the definition is a loop-phi-node: determine its initial
64
   condition, that is the SSA edge defined in an outer loop, and
65
   keep it symbolic.  Then determine the SSA edges that are defined
66
   in the body of the loop.  Follow the inner edges until ending on
67
   another loop-phi-node of the same analyzed loop.  If the reached
68
   loop-phi-node is not the starting loop-phi-node, then we keep
69
   this definition under a symbolic form.  If the reached
70
   loop-phi-node is the same as the starting one, then we compute a
71
   symbolic stride on the return path.  The result is then the
72
   symbolic chrec {initial_condition, +, symbolic_stride}_loop.
73
 
74
   Examples:
75
 
76
   Example 1: Illustration of the basic algorithm.
77
 
78
   | a = 3
79
   | loop_1
80
   |   b = phi (a, c)
81
   |   c = b + 1
82
   |   if (c > 10) exit_loop
83
   | endloop
84
 
85
   Suppose that we want to know the number of iterations of the
86
   loop_1.  The exit_loop is controlled by a COND_EXPR (c > 10).  We
87
   ask the scalar evolution analyzer two questions: what's the
88
   scalar evolution (scev) of "c", and what's the scev of "10".  For
89
   "10" the answer is "10" since it is a scalar constant.  For the
90
   scalar variable "c", it follows the SSA edge to its definition,
91
   "c = b + 1", and then asks again what's the scev of "b".
92
   Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93
   c)", where the initial condition is "a", and the inner loop edge
94
   is "c".  The initial condition is kept under a symbolic form (it
95
   may be the case that the copy constant propagation has done its
96
   work and we end with the constant "3" as one of the edges of the
97
   loop-phi-node).  The update edge is followed to the end of the
98
   loop, and until reaching again the starting loop-phi-node: b -> c
99
   -> b.  At this point we have drawn a path from "b" to "b" from
100
   which we compute the stride in the loop: in this example it is
101
   "+1".  The resulting scev for "b" is "b -> {a, +, 1}_1".  Now
102
   that the scev for "b" is known, it is possible to compute the
103
   scev for "c", that is "c -> {a + 1, +, 1}_1".  In order to
104
   determine the number of iterations in the loop_1, we have to
105
   instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
106
   more analysis the scev {4, +, 1}_1, or in other words, this is
107
   the function "f (x) = x + 4", where x is the iteration count of
108
   the loop_1.  Now we have to solve the inequality "x + 4 > 10",
109
   and take the smallest iteration number for which the loop is
110
   exited: x = 7.  This loop runs from x = 0 to x = 7, and in total
111
   there are 8 iterations.  In terms of loop normalization, we have
112
   created a variable that is implicitly defined, "x" or just "_1",
113
   and all the other analyzed scalars of the loop are defined in
114
   function of this variable:
115
 
116
   a -> 3
117
   b -> {3, +, 1}_1
118
   c -> {4, +, 1}_1
119
 
120
   or in terms of a C program:
121
 
122
   | a = 3
123
   | for (x = 0; x <= 7; x++)
124
   |   {
125
   |     b = x + 3
126
   |     c = x + 4
127
   |   }
128
 
129
   Example 2a: Illustration of the algorithm on nested loops.
130
 
131
   | loop_1
132
   |   a = phi (1, b)
133
   |   c = a + 2
134
   |   loop_2  10 times
135
   |     b = phi (c, d)
136
   |     d = b + 3
137
   |   endloop
138
   | endloop
139
 
140
   For analyzing the scalar evolution of "a", the algorithm follows
141
   the SSA edge into the loop's body: "a -> b".  "b" is an inner
142
   loop-phi-node, and its analysis as in Example 1, gives:
143
 
144
   b -> {c, +, 3}_2
145
   d -> {c + 3, +, 3}_2
146
 
147
   Following the SSA edge for the initial condition, we end on "c = a
148
   + 2", and then on the starting loop-phi-node "a".  From this point,
149
   the loop stride is computed: back on "c = a + 2" we get a "+2" in
150
   the loop_1, then on the loop-phi-node "b" we compute the overall
151
   effect of the inner loop that is "b = c + 30", and we get a "+30"
152
   in the loop_1.  That means that the overall stride in loop_1 is
153
   equal to "+32", and the result is:
154
 
155
   a -> {1, +, 32}_1
156
   c -> {3, +, 32}_1
157
 
158
   Example 2b: Multivariate chains of recurrences.
159
 
160
   | loop_1
161
   |   k = phi (0, k + 1)
162
   |   loop_2  4 times
163
   |     j = phi (0, j + 1)
164
   |     loop_3 4 times
165
   |       i = phi (0, i + 1)
166
   |       A[j + k] = ...
167
   |     endloop
168
   |   endloop
169
   | endloop
170
 
171
   Analyzing the access function of array A with
172
   instantiate_parameters (loop_1, "j + k"), we obtain the
173
   instantiation and the analysis of the scalar variables "j" and "k"
174
   in loop_1.  This leads to the scalar evolution {4, +, 1}_1: the end
175
   value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
176
   {0, +, 1}_1.  To obtain the evolution function in loop_3 and
177
   instantiate the scalar variables up to loop_1, one has to use:
178
   instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
179
   The result of this call is {{0, +, 1}_1, +, 1}_2.
180
 
181
   Example 3: Higher degree polynomials.
182
 
183
   | loop_1
184
   |   a = phi (2, b)
185
   |   c = phi (5, d)
186
   |   b = a + 1
187
   |   d = c + a
188
   | endloop
189
 
190
   a -> {2, +, 1}_1
191
   b -> {3, +, 1}_1
192
   c -> {5, +, a}_1
193
   d -> {5 + a, +, a}_1
194
 
195
   instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
196
   instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
197
 
198
   Example 4: Lucas, Fibonacci, or mixers in general.
199
 
200
   | loop_1
201
   |   a = phi (1, b)
202
   |   c = phi (3, d)
203
   |   b = c
204
   |   d = c + a
205
   | endloop
206
 
207
   a -> (1, c)_1
208
   c -> {3, +, a}_1
209
 
210
   The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
211
   following semantics: during the first iteration of the loop_1, the
212
   variable contains the value 1, and then it contains the value "c".
213
   Note that this syntax is close to the syntax of the loop-phi-node:
214
   "a -> (1, c)_1" vs. "a = phi (1, c)".
215
 
216
   The symbolic chrec representation contains all the semantics of the
217
   original code.  What is more difficult is to use this information.
218
 
219
   Example 5: Flip-flops, or exchangers.
220
 
221
   | loop_1
222
   |   a = phi (1, b)
223
   |   c = phi (3, d)
224
   |   b = c
225
   |   d = a
226
   | endloop
227
 
228
   a -> (1, c)_1
229
   c -> (3, a)_1
230
 
231
   Based on these symbolic chrecs, it is possible to refine this
232
   information into the more precise PERIODIC_CHRECs:
233
 
234
   a -> |1, 3|_1
235
   c -> |3, 1|_1
236
 
237
   This transformation is not yet implemented.
238
 
239
   Further readings:
240
 
241
   You can find a more detailed description of the algorithm in:
242
   http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
243
   http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz.  But note that
244
   this is a preliminary report and some of the details of the
245
   algorithm have changed.  I'm working on a research report that
246
   updates the description of the algorithms to reflect the design
247
   choices used in this implementation.
248
 
249
   A set of slides show a high level overview of the algorithm and run
250
   an example through the scalar evolution analyzer:
251
   http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
252
 
253
   The slides that I have presented at the GCC Summit'04 are available
254
   at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
255
*/
256
 
257
#include "config.h"
258
#include "system.h"
259
#include "coretypes.h"
260
#include "gimple-pretty-print.h"
261
#include "tree-flow.h"
262
#include "cfgloop.h"
263
#include "tree-chrec.h"
264
#include "tree-scalar-evolution.h"
265
#include "tree-pass.h"
266
#include "params.h"
267
 
268
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
269
 
270
/* The cached information about an SSA name VAR, claiming that below
271
   basic block INSTANTIATED_BELOW, the value of VAR can be expressed
272
   as CHREC.  */
273
 
274
struct GTY(()) scev_info_str {
275
  basic_block instantiated_below;
276
  tree var;
277
  tree chrec;
278
};
279
 
280
/* Counters for the scev database.  */
281
static unsigned nb_set_scev = 0;
282
static unsigned nb_get_scev = 0;
283
 
284
/* The following trees are unique elements.  Thus the comparison of
285
   another element to these elements should be done on the pointer to
286
   these trees, and not on their value.  */
287
 
288
/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.  */
289
tree chrec_not_analyzed_yet;
290
 
291
/* Reserved to the cases where the analyzer has detected an
292
   undecidable property at compile time.  */
293
tree chrec_dont_know;
294
 
295
/* When the analyzer has detected that a property will never
296
   happen, then it qualifies it with chrec_known.  */
297
tree chrec_known;
298
 
299
static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
300
 
301
 
302
/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
303
 
304
static inline struct scev_info_str *
305
new_scev_info_str (basic_block instantiated_below, tree var)
306
{
307
  struct scev_info_str *res;
308
 
309
  res = ggc_alloc_scev_info_str ();
310
  res->var = var;
311
  res->chrec = chrec_not_analyzed_yet;
312
  res->instantiated_below = instantiated_below;
313
 
314
  return res;
315
}
316
 
317
/* Computes a hash function for database element ELT.  */
318
 
319
static hashval_t
320
hash_scev_info (const void *elt)
321
{
322
  return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
323
}
324
 
325
/* Compares database elements E1 and E2.  */
326
 
327
static int
328
eq_scev_info (const void *e1, const void *e2)
329
{
330
  const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
331
  const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
332
 
333
  return (elt1->var == elt2->var
334
          && elt1->instantiated_below == elt2->instantiated_below);
335
}
336
 
337
/* Deletes database element E.  */
338
 
339
static void
340
del_scev_info (void *e)
341
{
342
  ggc_free (e);
343
}
344
 
345
/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
346
   A first query on VAR returns chrec_not_analyzed_yet.  */
347
 
348
static tree *
349
find_var_scev_info (basic_block instantiated_below, tree var)
350
{
351
  struct scev_info_str *res;
352
  struct scev_info_str tmp;
353
  PTR *slot;
354
 
355
  tmp.var = var;
356
  tmp.instantiated_below = instantiated_below;
357
  slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
358
 
359
  if (!*slot)
360
    *slot = new_scev_info_str (instantiated_below, var);
361
  res = (struct scev_info_str *) *slot;
362
 
363
  return &res->chrec;
364
}
365
 
366
/* Return true when CHREC contains symbolic names defined in
367
   LOOP_NB.  */
368
 
369
bool
370
chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
371
{
372
  int i, n;
373
 
374
  if (chrec == NULL_TREE)
375
    return false;
376
 
377
  if (is_gimple_min_invariant (chrec))
378
    return false;
379
 
380
  if (TREE_CODE (chrec) == SSA_NAME)
381
    {
382
      gimple def;
383
      loop_p def_loop, loop;
384
 
385
      if (SSA_NAME_IS_DEFAULT_DEF (chrec))
386
        return false;
387
 
388
      def = SSA_NAME_DEF_STMT (chrec);
389
      def_loop = loop_containing_stmt (def);
390
      loop = get_loop (loop_nb);
391
 
392
      if (def_loop == NULL)
393
        return false;
394
 
395
      if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
396
        return true;
397
 
398
      return false;
399
    }
400
 
401
  n = TREE_OPERAND_LENGTH (chrec);
402
  for (i = 0; i < n; i++)
403
    if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
404
                                                loop_nb))
405
      return true;
406
  return false;
407
}
408
 
409
/* Return true when PHI is a loop-phi-node.  */
410
 
411
static bool
412
loop_phi_node_p (gimple phi)
413
{
414
  /* The implementation of this function is based on the following
415
     property: "all the loop-phi-nodes of a loop are contained in the
416
     loop's header basic block".  */
417
 
418
  return loop_containing_stmt (phi)->header == gimple_bb (phi);
419
}
420
 
421
/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
422
   In general, in the case of multivariate evolutions we want to get
423
   the evolution in different loops.  LOOP specifies the level for
424
   which to get the evolution.
425
 
426
   Example:
427
 
428
   | for (j = 0; j < 100; j++)
429
   |   {
430
   |     for (k = 0; k < 100; k++)
431
   |       {
432
   |         i = k + j;   - Here the value of i is a function of j, k.
433
   |       }
434
   |      ... = i         - Here the value of i is a function of j.
435
   |   }
436
   | ... = i              - Here the value of i is a scalar.
437
 
438
   Example:
439
 
440
   | i_0 = ...
441
   | loop_1 10 times
442
   |   i_1 = phi (i_0, i_2)
443
   |   i_2 = i_1 + 2
444
   | endloop
445
 
446
   This loop has the same effect as:
447
   LOOP_1 has the same effect as:
448
 
449
   | i_1 = i_0 + 20
450
 
451
   The overall effect of the loop, "i_0 + 20" in the previous example,
452
   is obtained by passing in the parameters: LOOP = 1,
453
   EVOLUTION_FN = {i_0, +, 2}_1.
454
*/
455
 
456
tree
457
compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
458
{
459
  bool val = false;
460
 
461
  if (evolution_fn == chrec_dont_know)
462
    return chrec_dont_know;
463
 
464
  else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
465
    {
466
      struct loop *inner_loop = get_chrec_loop (evolution_fn);
467
 
468
      if (inner_loop == loop
469
          || flow_loop_nested_p (loop, inner_loop))
470
        {
471
          tree nb_iter = number_of_latch_executions (inner_loop);
472
 
473
          if (nb_iter == chrec_dont_know)
474
            return chrec_dont_know;
475
          else
476
            {
477
              tree res;
478
 
479
              /* evolution_fn is the evolution function in LOOP.  Get
480
                 its value in the nb_iter-th iteration.  */
481
              res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
482
 
483
              if (chrec_contains_symbols_defined_in_loop (res, loop->num))
484
                res = instantiate_parameters (loop, res);
485
 
486
              /* Continue the computation until ending on a parent of LOOP.  */
487
              return compute_overall_effect_of_inner_loop (loop, res);
488
            }
489
        }
490
      else
491
        return evolution_fn;
492
     }
493
 
494
  /* If the evolution function is an invariant, there is nothing to do.  */
495
  else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
496
    return evolution_fn;
497
 
498
  else
499
    return chrec_dont_know;
500
}
501
 
502
/* Determine whether the CHREC is always positive/negative.  If the expression
503
   cannot be statically analyzed, return false, otherwise set the answer into
504
   VALUE.  */
505
 
506
bool
507
chrec_is_positive (tree chrec, bool *value)
508
{
509
  bool value0, value1, value2;
510
  tree end_value, nb_iter;
511
 
512
  switch (TREE_CODE (chrec))
513
    {
514
    case POLYNOMIAL_CHREC:
515
      if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
516
          || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
517
        return false;
518
 
519
      /* FIXME -- overflows.  */
520
      if (value0 == value1)
521
        {
522
          *value = value0;
523
          return true;
524
        }
525
 
526
      /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
527
         and the proof consists in showing that the sign never
528
         changes during the execution of the loop, from 0 to
529
         loop->nb_iterations.  */
530
      if (!evolution_function_is_affine_p (chrec))
531
        return false;
532
 
533
      nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
534
      if (chrec_contains_undetermined (nb_iter))
535
        return false;
536
 
537
#if 0
538
      /* TODO -- If the test is after the exit, we may decrease the number of
539
         iterations by one.  */
540
      if (after_exit)
541
        nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
542
#endif
543
 
544
      end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
545
 
546
      if (!chrec_is_positive (end_value, &value2))
547
        return false;
548
 
549
      *value = value0;
550
      return value0 == value1;
551
 
552
    case INTEGER_CST:
553
      *value = (tree_int_cst_sgn (chrec) == 1);
554
      return true;
555
 
556
    default:
557
      return false;
558
    }
559
}
560
 
561
/* Associate CHREC to SCALAR.  */
562
 
563
static void
564
set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
565
{
566
  tree *scalar_info;
567
 
568
  if (TREE_CODE (scalar) != SSA_NAME)
569
    return;
570
 
571
  scalar_info = find_var_scev_info (instantiated_below, scalar);
572
 
573
  if (dump_file)
574
    {
575
      if (dump_flags & TDF_SCEV)
576
        {
577
          fprintf (dump_file, "(set_scalar_evolution \n");
578
          fprintf (dump_file, "  instantiated_below = %d \n",
579
                   instantiated_below->index);
580
          fprintf (dump_file, "  (scalar = ");
581
          print_generic_expr (dump_file, scalar, 0);
582
          fprintf (dump_file, ")\n  (scalar_evolution = ");
583
          print_generic_expr (dump_file, chrec, 0);
584
          fprintf (dump_file, "))\n");
585
        }
586
      if (dump_flags & TDF_STATS)
587
        nb_set_scev++;
588
    }
589
 
590
  *scalar_info = chrec;
591
}
592
 
593
/* Retrieve the chrec associated to SCALAR instantiated below
594
   INSTANTIATED_BELOW block.  */
595
 
596
static tree
597
get_scalar_evolution (basic_block instantiated_below, tree scalar)
598
{
599
  tree res;
600
 
601
  if (dump_file)
602
    {
603
      if (dump_flags & TDF_SCEV)
604
        {
605
          fprintf (dump_file, "(get_scalar_evolution \n");
606
          fprintf (dump_file, "  (scalar = ");
607
          print_generic_expr (dump_file, scalar, 0);
608
          fprintf (dump_file, ")\n");
609
        }
610
      if (dump_flags & TDF_STATS)
611
        nb_get_scev++;
612
    }
613
 
614
  switch (TREE_CODE (scalar))
615
    {
616
    case SSA_NAME:
617
      res = *find_var_scev_info (instantiated_below, scalar);
618
      break;
619
 
620
    case REAL_CST:
621
    case FIXED_CST:
622
    case INTEGER_CST:
623
      res = scalar;
624
      break;
625
 
626
    default:
627
      res = chrec_not_analyzed_yet;
628
      break;
629
    }
630
 
631
  if (dump_file && (dump_flags & TDF_SCEV))
632
    {
633
      fprintf (dump_file, "  (scalar_evolution = ");
634
      print_generic_expr (dump_file, res, 0);
635
      fprintf (dump_file, "))\n");
636
    }
637
 
638
  return res;
639
}
640
 
641
/* Helper function for add_to_evolution.  Returns the evolution
642
   function for an assignment of the form "a = b + c", where "a" and
643
   "b" are on the strongly connected component.  CHREC_BEFORE is the
644
   information that we already have collected up to this point.
645
   TO_ADD is the evolution of "c".
646
 
647
   When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
648
   evolution the expression TO_ADD, otherwise construct an evolution
649
   part for this loop.  */
650
 
651
static tree
652
add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
653
                    gimple at_stmt)
654
{
655
  tree type, left, right;
656
  struct loop *loop = get_loop (loop_nb), *chloop;
657
 
658
  switch (TREE_CODE (chrec_before))
659
    {
660
    case POLYNOMIAL_CHREC:
661
      chloop = get_chrec_loop (chrec_before);
662
      if (chloop == loop
663
          || flow_loop_nested_p (chloop, loop))
664
        {
665
          unsigned var;
666
 
667
          type = chrec_type (chrec_before);
668
 
669
          /* When there is no evolution part in this loop, build it.  */
670
          if (chloop != loop)
671
            {
672
              var = loop_nb;
673
              left = chrec_before;
674
              right = SCALAR_FLOAT_TYPE_P (type)
675
                ? build_real (type, dconst0)
676
                : build_int_cst (type, 0);
677
            }
678
          else
679
            {
680
              var = CHREC_VARIABLE (chrec_before);
681
              left = CHREC_LEFT (chrec_before);
682
              right = CHREC_RIGHT (chrec_before);
683
            }
684
 
685
          to_add = chrec_convert (type, to_add, at_stmt);
686
          right = chrec_convert_rhs (type, right, at_stmt);
687
          right = chrec_fold_plus (chrec_type (right), right, to_add);
688
          return build_polynomial_chrec (var, left, right);
689
        }
690
      else
691
        {
692
          gcc_assert (flow_loop_nested_p (loop, chloop));
693
 
694
          /* Search the evolution in LOOP_NB.  */
695
          left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
696
                                     to_add, at_stmt);
697
          right = CHREC_RIGHT (chrec_before);
698
          right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
699
          return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
700
                                         left, right);
701
        }
702
 
703
    default:
704
      /* These nodes do not depend on a loop.  */
705
      if (chrec_before == chrec_dont_know)
706
        return chrec_dont_know;
707
 
708
      left = chrec_before;
709
      right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
710
      return build_polynomial_chrec (loop_nb, left, right);
711
    }
712
}
713
 
714
/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
715
   of LOOP_NB.
716
 
717
   Description (provided for completeness, for those who read code in
718
   a plane, and for my poor 62 bytes brain that would have forgotten
719
   all this in the next two or three months):
720
 
721
   The algorithm of translation of programs from the SSA representation
722
   into the chrecs syntax is based on a pattern matching.  After having
723
   reconstructed the overall tree expression for a loop, there are only
724
   two cases that can arise:
725
 
726
   1. a = loop-phi (init, a + expr)
727
   2. a = loop-phi (init, expr)
728
 
729
   where EXPR is either a scalar constant with respect to the analyzed
730
   loop (this is a degree 0 polynomial), or an expression containing
731
   other loop-phi definitions (these are higher degree polynomials).
732
 
733
   Examples:
734
 
735
   1.
736
   | init = ...
737
   | loop_1
738
   |   a = phi (init, a + 5)
739
   | endloop
740
 
741
   2.
742
   | inita = ...
743
   | initb = ...
744
   | loop_1
745
   |   a = phi (inita, 2 * b + 3)
746
   |   b = phi (initb, b + 1)
747
   | endloop
748
 
749
   For the first case, the semantics of the SSA representation is:
750
 
751
   | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
752
 
753
   that is, there is a loop index "x" that determines the scalar value
754
   of the variable during the loop execution.  During the first
755
   iteration, the value is that of the initial condition INIT, while
756
   during the subsequent iterations, it is the sum of the initial
757
   condition with the sum of all the values of EXPR from the initial
758
   iteration to the before last considered iteration.
759
 
760
   For the second case, the semantics of the SSA program is:
761
 
762
   | a (x) = init, if x = 0;
763
   |         expr (x - 1), otherwise.
764
 
765
   The second case corresponds to the PEELED_CHREC, whose syntax is
766
   close to the syntax of a loop-phi-node:
767
 
768
   | phi (init, expr)  vs.  (init, expr)_x
769
 
770
   The proof of the translation algorithm for the first case is a
771
   proof by structural induction based on the degree of EXPR.
772
 
773
   Degree 0:
774
   When EXPR is a constant with respect to the analyzed loop, or in
775
   other words when EXPR is a polynomial of degree 0, the evolution of
776
   the variable A in the loop is an affine function with an initial
777
   condition INIT, and a step EXPR.  In order to show this, we start
778
   from the semantics of the SSA representation:
779
 
780
   f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
781
 
782
   and since "expr (j)" is a constant with respect to "j",
783
 
784
   f (x) = init + x * expr
785
 
786
   Finally, based on the semantics of the pure sum chrecs, by
787
   identification we get the corresponding chrecs syntax:
788
 
789
   f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
790
   f (x) -> {init, +, expr}_x
791
 
792
   Higher degree:
793
   Suppose that EXPR is a polynomial of degree N with respect to the
794
   analyzed loop_x for which we have already determined that it is
795
   written under the chrecs syntax:
796
 
797
   | expr (x)  ->  {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
798
 
799
   We start from the semantics of the SSA program:
800
 
801
   | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
802
   |
803
   | f (x) = init + \sum_{j = 0}^{x - 1}
804
   |                (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
805
   |
806
   | f (x) = init + \sum_{j = 0}^{x - 1}
807
   |                \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
808
   |
809
   | f (x) = init + \sum_{k = 0}^{n - 1}
810
   |                (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
811
   |
812
   | f (x) = init + \sum_{k = 0}^{n - 1}
813
   |                (b_k * \binom{x}{k + 1})
814
   |
815
   | f (x) = init + b_0 * \binom{x}{1} + ...
816
   |              + b_{n-1} * \binom{x}{n}
817
   |
818
   | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
819
   |                             + b_{n-1} * \binom{x}{n}
820
   |
821
 
822
   And finally from the definition of the chrecs syntax, we identify:
823
   | f (x)  ->  {init, +, b_0, +, ..., +, b_{n-1}}_x
824
 
825
   This shows the mechanism that stands behind the add_to_evolution
826
   function.  An important point is that the use of symbolic
827
   parameters avoids the need of an analysis schedule.
828
 
829
   Example:
830
 
831
   | inita = ...
832
   | initb = ...
833
   | loop_1
834
   |   a = phi (inita, a + 2 + b)
835
   |   b = phi (initb, b + 1)
836
   | endloop
837
 
838
   When analyzing "a", the algorithm keeps "b" symbolically:
839
 
840
   | a  ->  {inita, +, 2 + b}_1
841
 
842
   Then, after instantiation, the analyzer ends on the evolution:
843
 
844
   | a  ->  {inita, +, 2 + initb, +, 1}_1
845
 
846
*/
847
 
848
static tree
849
add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
850
                  tree to_add, gimple at_stmt)
851
{
852
  tree type = chrec_type (to_add);
853
  tree res = NULL_TREE;
854
 
855
  if (to_add == NULL_TREE)
856
    return chrec_before;
857
 
858
  /* TO_ADD is either a scalar, or a parameter.  TO_ADD is not
859
     instantiated at this point.  */
860
  if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
861
    /* This should not happen.  */
862
    return chrec_dont_know;
863
 
864
  if (dump_file && (dump_flags & TDF_SCEV))
865
    {
866
      fprintf (dump_file, "(add_to_evolution \n");
867
      fprintf (dump_file, "  (loop_nb = %d)\n", loop_nb);
868
      fprintf (dump_file, "  (chrec_before = ");
869
      print_generic_expr (dump_file, chrec_before, 0);
870
      fprintf (dump_file, ")\n  (to_add = ");
871
      print_generic_expr (dump_file, to_add, 0);
872
      fprintf (dump_file, ")\n");
873
    }
874
 
875
  if (code == MINUS_EXPR)
876
    to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
877
                                  ? build_real (type, dconstm1)
878
                                  : build_int_cst_type (type, -1));
879
 
880
  res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
881
 
882
  if (dump_file && (dump_flags & TDF_SCEV))
883
    {
884
      fprintf (dump_file, "  (res = ");
885
      print_generic_expr (dump_file, res, 0);
886
      fprintf (dump_file, "))\n");
887
    }
888
 
889
  return res;
890
}
891
 
892
 
893
 
894
/* This section selects the loops that will be good candidates for the
895
   scalar evolution analysis.  For the moment, greedily select all the
896
   loop nests we could analyze.  */
897
 
898
/* For a loop with a single exit edge, return the COND_EXPR that
899
   guards the exit edge.  If the expression is too difficult to
900
   analyze, then give up.  */
901
 
902
gimple
903
get_loop_exit_condition (const struct loop *loop)
904
{
905
  gimple res = NULL;
906
  edge exit_edge = single_exit (loop);
907
 
908
  if (dump_file && (dump_flags & TDF_SCEV))
909
    fprintf (dump_file, "(get_loop_exit_condition \n  ");
910
 
911
  if (exit_edge)
912
    {
913
      gimple stmt;
914
 
915
      stmt = last_stmt (exit_edge->src);
916
      if (gimple_code (stmt) == GIMPLE_COND)
917
        res = stmt;
918
    }
919
 
920
  if (dump_file && (dump_flags & TDF_SCEV))
921
    {
922
      print_gimple_stmt (dump_file, res, 0, 0);
923
      fprintf (dump_file, ")\n");
924
    }
925
 
926
  return res;
927
}
928
 
929
/* Recursively determine and enqueue the exit conditions for a loop.  */
930
 
931
static void
932
get_exit_conditions_rec (struct loop *loop,
933
                         VEC(gimple,heap) **exit_conditions)
934
{
935
  if (!loop)
936
    return;
937
 
938
  /* Recurse on the inner loops, then on the next (sibling) loops.  */
939
  get_exit_conditions_rec (loop->inner, exit_conditions);
940
  get_exit_conditions_rec (loop->next, exit_conditions);
941
 
942
  if (single_exit (loop))
943
    {
944
      gimple loop_condition = get_loop_exit_condition (loop);
945
 
946
      if (loop_condition)
947
        VEC_safe_push (gimple, heap, *exit_conditions, loop_condition);
948
    }
949
}
950
 
951
/* Select the candidate loop nests for the analysis.  This function
952
   initializes the EXIT_CONDITIONS array.  */
953
 
954
static void
955
select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions)
956
{
957
  struct loop *function_body = current_loops->tree_root;
958
 
959
  get_exit_conditions_rec (function_body->inner, exit_conditions);
960
}
961
 
962
 
963
/* Depth first search algorithm.  */
964
 
965
typedef enum t_bool {
966
  t_false,
967
  t_true,
968
  t_dont_know
969
} t_bool;
970
 
971
 
972
static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
973
 
974
/* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
975
   Return true if the strongly connected component has been found.  */
976
 
977
static t_bool
978
follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
979
                        tree type, tree rhs0, enum tree_code code, tree rhs1,
980
                        gimple halting_phi, tree *evolution_of_loop, int limit)
981
{
982
  t_bool res = t_false;
983
  tree evol;
984
 
985
  switch (code)
986
    {
987
    case POINTER_PLUS_EXPR:
988
    case PLUS_EXPR:
989
      if (TREE_CODE (rhs0) == SSA_NAME)
990
        {
991
          if (TREE_CODE (rhs1) == SSA_NAME)
992
            {
993
              /* Match an assignment under the form:
994
                 "a = b + c".  */
995
 
996
              /* We want only assignments of form "name + name" contribute to
997
                 LIMIT, as the other cases do not necessarily contribute to
998
                 the complexity of the expression.  */
999
              limit++;
1000
 
1001
              evol = *evolution_of_loop;
1002
              res = follow_ssa_edge
1003
                (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
1004
 
1005
              if (res == t_true)
1006
                *evolution_of_loop = add_to_evolution
1007
                  (loop->num,
1008
                   chrec_convert (type, evol, at_stmt),
1009
                   code, rhs1, at_stmt);
1010
 
1011
              else if (res == t_false)
1012
                {
1013
                  res = follow_ssa_edge
1014
                    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1015
                     evolution_of_loop, limit);
1016
 
1017
                  if (res == t_true)
1018
                    *evolution_of_loop = add_to_evolution
1019
                      (loop->num,
1020
                       chrec_convert (type, *evolution_of_loop, at_stmt),
1021
                       code, rhs0, at_stmt);
1022
 
1023
                  else if (res == t_dont_know)
1024
                    *evolution_of_loop = chrec_dont_know;
1025
                }
1026
 
1027
              else if (res == t_dont_know)
1028
                *evolution_of_loop = chrec_dont_know;
1029
            }
1030
 
1031
          else
1032
            {
1033
              /* Match an assignment under the form:
1034
                 "a = b + ...".  */
1035
              res = follow_ssa_edge
1036
                (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1037
                 evolution_of_loop, limit);
1038
              if (res == t_true)
1039
                *evolution_of_loop = add_to_evolution
1040
                  (loop->num, chrec_convert (type, *evolution_of_loop,
1041
                                             at_stmt),
1042
                   code, rhs1, at_stmt);
1043
 
1044
              else if (res == t_dont_know)
1045
                *evolution_of_loop = chrec_dont_know;
1046
            }
1047
        }
1048
 
1049
      else if (TREE_CODE (rhs1) == SSA_NAME)
1050
        {
1051
          /* Match an assignment under the form:
1052
             "a = ... + c".  */
1053
          res = follow_ssa_edge
1054
            (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1055
             evolution_of_loop, limit);
1056
          if (res == t_true)
1057
            *evolution_of_loop = add_to_evolution
1058
              (loop->num, chrec_convert (type, *evolution_of_loop,
1059
                                         at_stmt),
1060
               code, rhs0, at_stmt);
1061
 
1062
          else if (res == t_dont_know)
1063
            *evolution_of_loop = chrec_dont_know;
1064
        }
1065
 
1066
      else
1067
        /* Otherwise, match an assignment under the form:
1068
           "a = ... + ...".  */
1069
        /* And there is nothing to do.  */
1070
        res = t_false;
1071
      break;
1072
 
1073
    case MINUS_EXPR:
1074
      /* This case is under the form "opnd0 = rhs0 - rhs1".  */
1075
      if (TREE_CODE (rhs0) == SSA_NAME)
1076
        {
1077
          /* Match an assignment under the form:
1078
             "a = b - ...".  */
1079
 
1080
          /* We want only assignments of form "name - name" contribute to
1081
             LIMIT, as the other cases do not necessarily contribute to
1082
             the complexity of the expression.  */
1083
          if (TREE_CODE (rhs1) == SSA_NAME)
1084
            limit++;
1085
 
1086
          res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1087
                                 evolution_of_loop, limit);
1088
          if (res == t_true)
1089
            *evolution_of_loop = add_to_evolution
1090
              (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1091
               MINUS_EXPR, rhs1, at_stmt);
1092
 
1093
          else if (res == t_dont_know)
1094
            *evolution_of_loop = chrec_dont_know;
1095
        }
1096
      else
1097
        /* Otherwise, match an assignment under the form:
1098
           "a = ... - ...".  */
1099
        /* And there is nothing to do.  */
1100
        res = t_false;
1101
      break;
1102
 
1103
    default:
1104
      res = t_false;
1105
    }
1106
 
1107
  return res;
1108
}
1109
 
1110
/* Follow the ssa edge into the expression EXPR.
1111
   Return true if the strongly connected component has been found.  */
1112
 
1113
static t_bool
1114
follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1115
                      gimple halting_phi, tree *evolution_of_loop, int limit)
1116
{
1117
  enum tree_code code = TREE_CODE (expr);
1118
  tree type = TREE_TYPE (expr), rhs0, rhs1;
1119
  t_bool res;
1120
 
1121
  /* The EXPR is one of the following cases:
1122
     - an SSA_NAME,
1123
     - an INTEGER_CST,
1124
     - a PLUS_EXPR,
1125
     - a POINTER_PLUS_EXPR,
1126
     - a MINUS_EXPR,
1127
     - an ASSERT_EXPR,
1128
     - other cases are not yet handled.  */
1129
 
1130
  switch (code)
1131
    {
1132
    CASE_CONVERT:
1133
      /* This assignment is under the form "a_1 = (cast) rhs.  */
1134
      res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1135
                                  halting_phi, evolution_of_loop, limit);
1136
      *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1137
      break;
1138
 
1139
    case INTEGER_CST:
1140
      /* This assignment is under the form "a_1 = 7".  */
1141
      res = t_false;
1142
      break;
1143
 
1144
    case SSA_NAME:
1145
      /* This assignment is under the form: "a_1 = b_2".  */
1146
      res = follow_ssa_edge
1147
        (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1148
      break;
1149
 
1150
    case POINTER_PLUS_EXPR:
1151
    case PLUS_EXPR:
1152
    case MINUS_EXPR:
1153
      /* This case is under the form "rhs0 +- rhs1".  */
1154
      rhs0 = TREE_OPERAND (expr, 0);
1155
      rhs1 = TREE_OPERAND (expr, 1);
1156
      type = TREE_TYPE (rhs0);
1157
      STRIP_USELESS_TYPE_CONVERSION (rhs0);
1158
      STRIP_USELESS_TYPE_CONVERSION (rhs1);
1159
      res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1160
                                    halting_phi, evolution_of_loop, limit);
1161
      break;
1162
 
1163
    case ADDR_EXPR:
1164
      /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
1165
      if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1166
        {
1167
          expr = TREE_OPERAND (expr, 0);
1168
          rhs0 = TREE_OPERAND (expr, 0);
1169
          rhs1 = TREE_OPERAND (expr, 1);
1170
          type = TREE_TYPE (rhs0);
1171
          STRIP_USELESS_TYPE_CONVERSION (rhs0);
1172
          STRIP_USELESS_TYPE_CONVERSION (rhs1);
1173
          res = follow_ssa_edge_binary (loop, at_stmt, type,
1174
                                        rhs0, POINTER_PLUS_EXPR, rhs1,
1175
                                        halting_phi, evolution_of_loop, limit);
1176
        }
1177
      else
1178
        res = t_false;
1179
      break;
1180
 
1181
    case ASSERT_EXPR:
1182
      /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1183
         It must be handled as a copy assignment of the form a_1 = a_2.  */
1184
      rhs0 = ASSERT_EXPR_VAR (expr);
1185
      if (TREE_CODE (rhs0) == SSA_NAME)
1186
        res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1187
                               halting_phi, evolution_of_loop, limit);
1188
      else
1189
        res = t_false;
1190
      break;
1191
 
1192
    default:
1193
      res = t_false;
1194
      break;
1195
    }
1196
 
1197
  return res;
1198
}
1199
 
1200
/* Follow the ssa edge into the right hand side of an assignment STMT.
1201
   Return true if the strongly connected component has been found.  */
1202
 
1203
static t_bool
1204
follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1205
                        gimple halting_phi, tree *evolution_of_loop, int limit)
1206
{
1207
  enum tree_code code = gimple_assign_rhs_code (stmt);
1208
  tree type = gimple_expr_type (stmt), rhs1, rhs2;
1209
  t_bool res;
1210
 
1211
  switch (code)
1212
    {
1213
    CASE_CONVERT:
1214
      /* This assignment is under the form "a_1 = (cast) rhs.  */
1215
      res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1216
                                  halting_phi, evolution_of_loop, limit);
1217
      *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1218
      break;
1219
 
1220
    case POINTER_PLUS_EXPR:
1221
    case PLUS_EXPR:
1222
    case MINUS_EXPR:
1223
      rhs1 = gimple_assign_rhs1 (stmt);
1224
      rhs2 = gimple_assign_rhs2 (stmt);
1225
      type = TREE_TYPE (rhs1);
1226
      res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1227
                                    halting_phi, evolution_of_loop, limit);
1228
      break;
1229
 
1230
    default:
1231
      if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1232
        res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1233
                                    halting_phi, evolution_of_loop, limit);
1234
      else
1235
        res = t_false;
1236
      break;
1237
    }
1238
 
1239
  return res;
1240
}
1241
 
1242
/* Checks whether the I-th argument of a PHI comes from a backedge.  */
1243
 
1244
static bool
1245
backedge_phi_arg_p (gimple phi, int i)
1246
{
1247
  const_edge e = gimple_phi_arg_edge (phi, i);
1248
 
1249
  /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1250
     about updating it anywhere, and this should work as well most of the
1251
     time.  */
1252
  if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1253
    return true;
1254
 
1255
  return false;
1256
}
1257
 
1258
/* Helper function for one branch of the condition-phi-node.  Return
1259
   true if the strongly connected component has been found following
1260
   this path.  */
1261
 
1262
static inline t_bool
1263
follow_ssa_edge_in_condition_phi_branch (int i,
1264
                                         struct loop *loop,
1265
                                         gimple condition_phi,
1266
                                         gimple halting_phi,
1267
                                         tree *evolution_of_branch,
1268
                                         tree init_cond, int limit)
1269
{
1270
  tree branch = PHI_ARG_DEF (condition_phi, i);
1271
  *evolution_of_branch = chrec_dont_know;
1272
 
1273
  /* Do not follow back edges (they must belong to an irreducible loop, which
1274
     we really do not want to worry about).  */
1275
  if (backedge_phi_arg_p (condition_phi, i))
1276
    return t_false;
1277
 
1278
  if (TREE_CODE (branch) == SSA_NAME)
1279
    {
1280
      *evolution_of_branch = init_cond;
1281
      return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1282
                              evolution_of_branch, limit);
1283
    }
1284
 
1285
  /* This case occurs when one of the condition branches sets
1286
     the variable to a constant: i.e. a phi-node like
1287
     "a_2 = PHI <a_7(5), 2(6)>;".
1288
 
1289
     FIXME:  This case have to be refined correctly:
1290
     in some cases it is possible to say something better than
1291
     chrec_dont_know, for example using a wrap-around notation.  */
1292
  return t_false;
1293
}
1294
 
1295
/* This function merges the branches of a condition-phi-node in a
1296
   loop.  */
1297
 
1298
static t_bool
1299
follow_ssa_edge_in_condition_phi (struct loop *loop,
1300
                                  gimple condition_phi,
1301
                                  gimple halting_phi,
1302
                                  tree *evolution_of_loop, int limit)
1303
{
1304
  int i, n;
1305
  tree init = *evolution_of_loop;
1306
  tree evolution_of_branch;
1307
  t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1308
                                                        halting_phi,
1309
                                                        &evolution_of_branch,
1310
                                                        init, limit);
1311
  if (res == t_false || res == t_dont_know)
1312
    return res;
1313
 
1314
  *evolution_of_loop = evolution_of_branch;
1315
 
1316
  n = gimple_phi_num_args (condition_phi);
1317
  for (i = 1; i < n; i++)
1318
    {
1319
      /* Quickly give up when the evolution of one of the branches is
1320
         not known.  */
1321
      if (*evolution_of_loop == chrec_dont_know)
1322
        return t_true;
1323
 
1324
      /* Increase the limit by the PHI argument number to avoid exponential
1325
         time and memory complexity.  */
1326
      res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1327
                                                     halting_phi,
1328
                                                     &evolution_of_branch,
1329
                                                     init, limit + i);
1330
      if (res == t_false || res == t_dont_know)
1331
        return res;
1332
 
1333
      *evolution_of_loop = chrec_merge (*evolution_of_loop,
1334
                                        evolution_of_branch);
1335
    }
1336
 
1337
  return t_true;
1338
}
1339
 
1340
/* Follow an SSA edge in an inner loop.  It computes the overall
1341
   effect of the loop, and following the symbolic initial conditions,
1342
   it follows the edges in the parent loop.  The inner loop is
1343
   considered as a single statement.  */
1344
 
1345
static t_bool
1346
follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1347
                                gimple loop_phi_node,
1348
                                gimple halting_phi,
1349
                                tree *evolution_of_loop, int limit)
1350
{
1351
  struct loop *loop = loop_containing_stmt (loop_phi_node);
1352
  tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1353
 
1354
  /* Sometimes, the inner loop is too difficult to analyze, and the
1355
     result of the analysis is a symbolic parameter.  */
1356
  if (ev == PHI_RESULT (loop_phi_node))
1357
    {
1358
      t_bool res = t_false;
1359
      int i, n = gimple_phi_num_args (loop_phi_node);
1360
 
1361
      for (i = 0; i < n; i++)
1362
        {
1363
          tree arg = PHI_ARG_DEF (loop_phi_node, i);
1364
          basic_block bb;
1365
 
1366
          /* Follow the edges that exit the inner loop.  */
1367
          bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1368
          if (!flow_bb_inside_loop_p (loop, bb))
1369
            res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1370
                                        arg, halting_phi,
1371
                                        evolution_of_loop, limit);
1372
          if (res == t_true)
1373
            break;
1374
        }
1375
 
1376
      /* If the path crosses this loop-phi, give up.  */
1377
      if (res == t_true)
1378
        *evolution_of_loop = chrec_dont_know;
1379
 
1380
      return res;
1381
    }
1382
 
1383
  /* Otherwise, compute the overall effect of the inner loop.  */
1384
  ev = compute_overall_effect_of_inner_loop (loop, ev);
1385
  return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1386
                               evolution_of_loop, limit);
1387
}
1388
 
1389
/* Follow an SSA edge from a loop-phi-node to itself, constructing a
1390
   path that is analyzed on the return walk.  */
1391
 
1392
static t_bool
1393
follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
1394
                 tree *evolution_of_loop, int limit)
1395
{
1396
  struct loop *def_loop;
1397
 
1398
  if (gimple_nop_p (def))
1399
    return t_false;
1400
 
1401
  /* Give up if the path is longer than the MAX that we allow.  */
1402
  if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1403
    return t_dont_know;
1404
 
1405
  def_loop = loop_containing_stmt (def);
1406
 
1407
  switch (gimple_code (def))
1408
    {
1409
    case GIMPLE_PHI:
1410
      if (!loop_phi_node_p (def))
1411
        /* DEF is a condition-phi-node.  Follow the branches, and
1412
           record their evolutions.  Finally, merge the collected
1413
           information and set the approximation to the main
1414
           variable.  */
1415
        return follow_ssa_edge_in_condition_phi
1416
          (loop, def, halting_phi, evolution_of_loop, limit);
1417
 
1418
      /* When the analyzed phi is the halting_phi, the
1419
         depth-first search is over: we have found a path from
1420
         the halting_phi to itself in the loop.  */
1421
      if (def == halting_phi)
1422
        return t_true;
1423
 
1424
      /* Otherwise, the evolution of the HALTING_PHI depends
1425
         on the evolution of another loop-phi-node, i.e. the
1426
         evolution function is a higher degree polynomial.  */
1427
      if (def_loop == loop)
1428
        return t_false;
1429
 
1430
      /* Inner loop.  */
1431
      if (flow_loop_nested_p (loop, def_loop))
1432
        return follow_ssa_edge_inner_loop_phi
1433
          (loop, def, halting_phi, evolution_of_loop, limit + 1);
1434
 
1435
      /* Outer loop.  */
1436
      return t_false;
1437
 
1438
    case GIMPLE_ASSIGN:
1439
      return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1440
                                     evolution_of_loop, limit);
1441
 
1442
    default:
1443
      /* At this level of abstraction, the program is just a set
1444
         of GIMPLE_ASSIGNs and PHI_NODEs.  In principle there is no
1445
         other node to be handled.  */
1446
      return t_false;
1447
    }
1448
}
1449
 
1450
 
1451
 
1452
/* Given a LOOP_PHI_NODE, this function determines the evolution
1453
   function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1454
 
1455
static tree
1456
analyze_evolution_in_loop (gimple loop_phi_node,
1457
                           tree init_cond)
1458
{
1459
  int i, n = gimple_phi_num_args (loop_phi_node);
1460
  tree evolution_function = chrec_not_analyzed_yet;
1461
  struct loop *loop = loop_containing_stmt (loop_phi_node);
1462
  basic_block bb;
1463
 
1464
  if (dump_file && (dump_flags & TDF_SCEV))
1465
    {
1466
      fprintf (dump_file, "(analyze_evolution_in_loop \n");
1467
      fprintf (dump_file, "  (loop_phi_node = ");
1468
      print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1469
      fprintf (dump_file, ")\n");
1470
    }
1471
 
1472
  for (i = 0; i < n; i++)
1473
    {
1474
      tree arg = PHI_ARG_DEF (loop_phi_node, i);
1475
      gimple ssa_chain;
1476
      tree ev_fn;
1477
      t_bool res;
1478
 
1479
      /* Select the edges that enter the loop body.  */
1480
      bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1481
      if (!flow_bb_inside_loop_p (loop, bb))
1482
        continue;
1483
 
1484
      if (TREE_CODE (arg) == SSA_NAME)
1485
        {
1486
          bool val = false;
1487
 
1488
          ssa_chain = SSA_NAME_DEF_STMT (arg);
1489
 
1490
          /* Pass in the initial condition to the follow edge function.  */
1491
          ev_fn = init_cond;
1492
          res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1493
 
1494
          /* If ev_fn has no evolution in the inner loop, and the
1495
             init_cond is not equal to ev_fn, then we have an
1496
             ambiguity between two possible values, as we cannot know
1497
             the number of iterations at this point.  */
1498
          if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1499
              && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1500
              && !operand_equal_p (init_cond, ev_fn, 0))
1501
            ev_fn = chrec_dont_know;
1502
        }
1503
      else
1504
        res = t_false;
1505
 
1506
      /* When it is impossible to go back on the same
1507
         loop_phi_node by following the ssa edges, the
1508
         evolution is represented by a peeled chrec, i.e. the
1509
         first iteration, EV_FN has the value INIT_COND, then
1510
         all the other iterations it has the value of ARG.
1511
         For the moment, PEELED_CHREC nodes are not built.  */
1512
      if (res != t_true)
1513
        ev_fn = chrec_dont_know;
1514
 
1515
      /* When there are multiple back edges of the loop (which in fact never
1516
         happens currently, but nevertheless), merge their evolutions.  */
1517
      evolution_function = chrec_merge (evolution_function, ev_fn);
1518
    }
1519
 
1520
  if (dump_file && (dump_flags & TDF_SCEV))
1521
    {
1522
      fprintf (dump_file, "  (evolution_function = ");
1523
      print_generic_expr (dump_file, evolution_function, 0);
1524
      fprintf (dump_file, "))\n");
1525
    }
1526
 
1527
  return evolution_function;
1528
}
1529
 
1530
/* Given a loop-phi-node, return the initial conditions of the
1531
   variable on entry of the loop.  When the CCP has propagated
1532
   constants into the loop-phi-node, the initial condition is
1533
   instantiated, otherwise the initial condition is kept symbolic.
1534
   This analyzer does not analyze the evolution outside the current
1535
   loop, and leaves this task to the on-demand tree reconstructor.  */
1536
 
1537
static tree
1538
analyze_initial_condition (gimple loop_phi_node)
1539
{
1540
  int i, n;
1541
  tree init_cond = chrec_not_analyzed_yet;
1542
  struct loop *loop = loop_containing_stmt (loop_phi_node);
1543
 
1544
  if (dump_file && (dump_flags & TDF_SCEV))
1545
    {
1546
      fprintf (dump_file, "(analyze_initial_condition \n");
1547
      fprintf (dump_file, "  (loop_phi_node = \n");
1548
      print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
1549
      fprintf (dump_file, ")\n");
1550
    }
1551
 
1552
  n = gimple_phi_num_args (loop_phi_node);
1553
  for (i = 0; i < n; i++)
1554
    {
1555
      tree branch = PHI_ARG_DEF (loop_phi_node, i);
1556
      basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1557
 
1558
      /* When the branch is oriented to the loop's body, it does
1559
         not contribute to the initial condition.  */
1560
      if (flow_bb_inside_loop_p (loop, bb))
1561
        continue;
1562
 
1563
      if (init_cond == chrec_not_analyzed_yet)
1564
        {
1565
          init_cond = branch;
1566
          continue;
1567
        }
1568
 
1569
      if (TREE_CODE (branch) == SSA_NAME)
1570
        {
1571
          init_cond = chrec_dont_know;
1572
          break;
1573
        }
1574
 
1575
      init_cond = chrec_merge (init_cond, branch);
1576
    }
1577
 
1578
  /* Ooops -- a loop without an entry???  */
1579
  if (init_cond == chrec_not_analyzed_yet)
1580
    init_cond = chrec_dont_know;
1581
 
1582
  /* During early loop unrolling we do not have fully constant propagated IL.
1583
     Handle degenerate PHIs here to not miss important unrollings.  */
1584
  if (TREE_CODE (init_cond) == SSA_NAME)
1585
    {
1586
      gimple def = SSA_NAME_DEF_STMT (init_cond);
1587
      tree res;
1588
      if (gimple_code (def) == GIMPLE_PHI
1589
          && (res = degenerate_phi_result (def)) != NULL_TREE
1590
          /* Only allow invariants here, otherwise we may break
1591
             loop-closed SSA form.  */
1592
          && is_gimple_min_invariant (res))
1593
        init_cond = res;
1594
    }
1595
 
1596
  if (dump_file && (dump_flags & TDF_SCEV))
1597
    {
1598
      fprintf (dump_file, "  (init_cond = ");
1599
      print_generic_expr (dump_file, init_cond, 0);
1600
      fprintf (dump_file, "))\n");
1601
    }
1602
 
1603
  return init_cond;
1604
}
1605
 
1606
/* Analyze the scalar evolution for LOOP_PHI_NODE.  */
1607
 
1608
static tree
1609
interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
1610
{
1611
  tree res;
1612
  struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1613
  tree init_cond;
1614
 
1615
  if (phi_loop != loop)
1616
    {
1617
      struct loop *subloop;
1618
      tree evolution_fn = analyze_scalar_evolution
1619
        (phi_loop, PHI_RESULT (loop_phi_node));
1620
 
1621
      /* Dive one level deeper.  */
1622
      subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1623
 
1624
      /* Interpret the subloop.  */
1625
      res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1626
      return res;
1627
    }
1628
 
1629
  /* Otherwise really interpret the loop phi.  */
1630
  init_cond = analyze_initial_condition (loop_phi_node);
1631
  res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1632
 
1633
  /* Verify we maintained the correct initial condition throughout
1634
     possible conversions in the SSA chain.  */
1635
  if (res != chrec_dont_know)
1636
    {
1637
      tree new_init = res;
1638
      if (CONVERT_EXPR_P (res)
1639
          && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1640
        new_init = fold_convert (TREE_TYPE (res),
1641
                                 CHREC_LEFT (TREE_OPERAND (res, 0)));
1642
      else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1643
        new_init = CHREC_LEFT (res);
1644
      STRIP_USELESS_TYPE_CONVERSION (new_init);
1645
      if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1646
          || !operand_equal_p (init_cond, new_init, 0))
1647
        return chrec_dont_know;
1648
    }
1649
 
1650
  return res;
1651
}
1652
 
1653
/* This function merges the branches of a condition-phi-node,
1654
   contained in the outermost loop, and whose arguments are already
1655
   analyzed.  */
1656
 
1657
static tree
1658
interpret_condition_phi (struct loop *loop, gimple condition_phi)
1659
{
1660
  int i, n = gimple_phi_num_args (condition_phi);
1661
  tree res = chrec_not_analyzed_yet;
1662
 
1663
  for (i = 0; i < n; i++)
1664
    {
1665
      tree branch_chrec;
1666
 
1667
      if (backedge_phi_arg_p (condition_phi, i))
1668
        {
1669
          res = chrec_dont_know;
1670
          break;
1671
        }
1672
 
1673
      branch_chrec = analyze_scalar_evolution
1674
        (loop, PHI_ARG_DEF (condition_phi, i));
1675
 
1676
      res = chrec_merge (res, branch_chrec);
1677
    }
1678
 
1679
  return res;
1680
}
1681
 
1682
/* Interpret the operation RHS1 OP RHS2.  If we didn't
1683
   analyze this node before, follow the definitions until ending
1684
   either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node.  On the
1685
   return path, this function propagates evolutions (ala constant copy
1686
   propagation).  OPND1 is not a GIMPLE expression because we could
1687
   analyze the effect of an inner loop: see interpret_loop_phi.  */
1688
 
1689
static tree
1690
interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1691
                    tree type, tree rhs1, enum tree_code code, tree rhs2)
1692
{
1693
  tree res, chrec1, chrec2;
1694
 
1695
  if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1696
    {
1697
      if (is_gimple_min_invariant (rhs1))
1698
        return chrec_convert (type, rhs1, at_stmt);
1699
 
1700
      if (code == SSA_NAME)
1701
        return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1702
                              at_stmt);
1703
 
1704
      if (code == ASSERT_EXPR)
1705
        {
1706
          rhs1 = ASSERT_EXPR_VAR (rhs1);
1707
          return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1708
                                at_stmt);
1709
        }
1710
    }
1711
 
1712
  switch (code)
1713
    {
1714
    case ADDR_EXPR:
1715
      /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  */
1716
      if (TREE_CODE (TREE_OPERAND (rhs1, 0)) != MEM_REF)
1717
        {
1718
          res = chrec_dont_know;
1719
          break;
1720
        }
1721
 
1722
      rhs2 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 1);
1723
      rhs1 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 0);
1724
      /* Fall through.  */
1725
 
1726
    case POINTER_PLUS_EXPR:
1727
      chrec1 = analyze_scalar_evolution (loop, rhs1);
1728
      chrec2 = analyze_scalar_evolution (loop, rhs2);
1729
      chrec1 = chrec_convert (type, chrec1, at_stmt);
1730
      chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1731
      res = chrec_fold_plus (type, chrec1, chrec2);
1732
      break;
1733
 
1734
    case PLUS_EXPR:
1735
      chrec1 = analyze_scalar_evolution (loop, rhs1);
1736
      chrec2 = analyze_scalar_evolution (loop, rhs2);
1737
      chrec1 = chrec_convert (type, chrec1, at_stmt);
1738
      chrec2 = chrec_convert (type, chrec2, at_stmt);
1739
      res = chrec_fold_plus (type, chrec1, chrec2);
1740
      break;
1741
 
1742
    case MINUS_EXPR:
1743
      chrec1 = analyze_scalar_evolution (loop, rhs1);
1744
      chrec2 = analyze_scalar_evolution (loop, rhs2);
1745
      chrec1 = chrec_convert (type, chrec1, at_stmt);
1746
      chrec2 = chrec_convert (type, chrec2, at_stmt);
1747
      res = chrec_fold_minus (type, chrec1, chrec2);
1748
      break;
1749
 
1750
    case NEGATE_EXPR:
1751
      chrec1 = analyze_scalar_evolution (loop, rhs1);
1752
      chrec1 = chrec_convert (type, chrec1, at_stmt);
1753
      /* TYPE may be integer, real or complex, so use fold_convert.  */
1754
      res = chrec_fold_multiply (type, chrec1,
1755
                                 fold_convert (type, integer_minus_one_node));
1756
      break;
1757
 
1758
    case BIT_NOT_EXPR:
1759
      /* Handle ~X as -1 - X.  */
1760
      chrec1 = analyze_scalar_evolution (loop, rhs1);
1761
      chrec1 = chrec_convert (type, chrec1, at_stmt);
1762
      res = chrec_fold_minus (type,
1763
                              fold_convert (type, integer_minus_one_node),
1764
                              chrec1);
1765
      break;
1766
 
1767
    case MULT_EXPR:
1768
      chrec1 = analyze_scalar_evolution (loop, rhs1);
1769
      chrec2 = analyze_scalar_evolution (loop, rhs2);
1770
      chrec1 = chrec_convert (type, chrec1, at_stmt);
1771
      chrec2 = chrec_convert (type, chrec2, at_stmt);
1772
      res = chrec_fold_multiply (type, chrec1, chrec2);
1773
      break;
1774
 
1775
    CASE_CONVERT:
1776
      chrec1 = analyze_scalar_evolution (loop, rhs1);
1777
      res = chrec_convert (type, chrec1, at_stmt);
1778
      break;
1779
 
1780
    default:
1781
      res = chrec_dont_know;
1782
      break;
1783
    }
1784
 
1785
  return res;
1786
}
1787
 
1788
/* Interpret the expression EXPR.  */
1789
 
1790
static tree
1791
interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1792
{
1793
  enum tree_code code;
1794
  tree type = TREE_TYPE (expr), op0, op1;
1795
 
1796
  if (automatically_generated_chrec_p (expr))
1797
    return expr;
1798
 
1799
  if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1800
      || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1801
    return chrec_dont_know;
1802
 
1803
  extract_ops_from_tree (expr, &code, &op0, &op1);
1804
 
1805
  return interpret_rhs_expr (loop, at_stmt, type,
1806
                             op0, code, op1);
1807
}
1808
 
1809
/* Interpret the rhs of the assignment STMT.  */
1810
 
1811
static tree
1812
interpret_gimple_assign (struct loop *loop, gimple stmt)
1813
{
1814
  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1815
  enum tree_code code = gimple_assign_rhs_code (stmt);
1816
 
1817
  return interpret_rhs_expr (loop, stmt, type,
1818
                             gimple_assign_rhs1 (stmt), code,
1819
                             gimple_assign_rhs2 (stmt));
1820
}
1821
 
1822
 
1823
 
1824
/* This section contains all the entry points:
1825
   - number_of_iterations_in_loop,
1826
   - analyze_scalar_evolution,
1827
   - instantiate_parameters.
1828
*/
1829
 
1830
/* Compute and return the evolution function in WRTO_LOOP, the nearest
1831
   common ancestor of DEF_LOOP and USE_LOOP.  */
1832
 
1833
static tree
1834
compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1835
                                  struct loop *def_loop,
1836
                                  tree ev)
1837
{
1838
  bool val;
1839
  tree res;
1840
 
1841
  if (def_loop == wrto_loop)
1842
    return ev;
1843
 
1844
  def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
1845
  res = compute_overall_effect_of_inner_loop (def_loop, ev);
1846
 
1847
  if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
1848
    return res;
1849
 
1850
  return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1851
}
1852
 
1853
/* Helper recursive function.  */
1854
 
1855
static tree
1856
analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1857
{
1858
  tree type = TREE_TYPE (var);
1859
  gimple def;
1860
  basic_block bb;
1861
  struct loop *def_loop;
1862
 
1863
  if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1864
    return chrec_dont_know;
1865
 
1866
  if (TREE_CODE (var) != SSA_NAME)
1867
    return interpret_expr (loop, NULL, var);
1868
 
1869
  def = SSA_NAME_DEF_STMT (var);
1870
  bb = gimple_bb (def);
1871
  def_loop = bb ? bb->loop_father : NULL;
1872
 
1873
  if (bb == NULL
1874
      || !flow_bb_inside_loop_p (loop, bb))
1875
    {
1876
      /* Keep the symbolic form.  */
1877
      res = var;
1878
      goto set_and_end;
1879
    }
1880
 
1881
  if (res != chrec_not_analyzed_yet)
1882
    {
1883
      if (loop != bb->loop_father)
1884
        res = compute_scalar_evolution_in_loop
1885
            (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1886
 
1887
      goto set_and_end;
1888
    }
1889
 
1890
  if (loop != def_loop)
1891
    {
1892
      res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1893
      res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1894
 
1895
      goto set_and_end;
1896
    }
1897
 
1898
  switch (gimple_code (def))
1899
    {
1900
    case GIMPLE_ASSIGN:
1901
      res = interpret_gimple_assign (loop, def);
1902
      break;
1903
 
1904
    case GIMPLE_PHI:
1905
      if (loop_phi_node_p (def))
1906
        res = interpret_loop_phi (loop, def);
1907
      else
1908
        res = interpret_condition_phi (loop, def);
1909
      break;
1910
 
1911
    default:
1912
      res = chrec_dont_know;
1913
      break;
1914
    }
1915
 
1916
 set_and_end:
1917
 
1918
  /* Keep the symbolic form.  */
1919
  if (res == chrec_dont_know)
1920
    res = var;
1921
 
1922
  if (loop == def_loop)
1923
    set_scalar_evolution (block_before_loop (loop), var, res);
1924
 
1925
  return res;
1926
}
1927
 
1928
/* Analyzes and returns the scalar evolution of the ssa_name VAR in
1929
   LOOP.  LOOP is the loop in which the variable is used.
1930
 
1931
   Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1932
   pointer to the statement that uses this variable, in order to
1933
   determine the evolution function of the variable, use the following
1934
   calls:
1935
 
1936
   loop_p loop = loop_containing_stmt (stmt);
1937
   tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
1938
   tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
1939
*/
1940
 
1941
tree
1942
analyze_scalar_evolution (struct loop *loop, tree var)
1943
{
1944
  tree res;
1945
 
1946
  if (dump_file && (dump_flags & TDF_SCEV))
1947
    {
1948
      fprintf (dump_file, "(analyze_scalar_evolution \n");
1949
      fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
1950
      fprintf (dump_file, "  (scalar = ");
1951
      print_generic_expr (dump_file, var, 0);
1952
      fprintf (dump_file, ")\n");
1953
    }
1954
 
1955
  res = get_scalar_evolution (block_before_loop (loop), var);
1956
  res = analyze_scalar_evolution_1 (loop, var, res);
1957
 
1958
  if (dump_file && (dump_flags & TDF_SCEV))
1959
    fprintf (dump_file, ")\n");
1960
 
1961
  return res;
1962
}
1963
 
1964
/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
1965
   WRTO_LOOP (which should be a superloop of USE_LOOP)
1966
 
1967
   FOLDED_CASTS is set to true if resolve_mixers used
1968
   chrec_convert_aggressive (TODO -- not really, we are way too conservative
1969
   at the moment in order to keep things simple).
1970
 
1971
   To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
1972
   example:
1973
 
1974
   for (i = 0; i < 100; i++)                    -- loop 1
1975
     {
1976
       for (j = 0; j < 100; j++)                -- loop 2
1977
         {
1978
           k1 = i;
1979
           k2 = j;
1980
 
1981
           use2 (k1, k2);
1982
 
1983
           for (t = 0; t < 100; t++)            -- loop 3
1984
             use3 (k1, k2);
1985
 
1986
         }
1987
       use1 (k1, k2);
1988
     }
1989
 
1990
   Both k1 and k2 are invariants in loop3, thus
1991
     analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
1992
     analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
1993
 
1994
   As they are invariant, it does not matter whether we consider their
1995
   usage in loop 3 or loop 2, hence
1996
     analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
1997
       analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
1998
     analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
1999
       analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2000
 
2001
   Similarly for their evolutions with respect to loop 1.  The values of K2
2002
   in the use in loop 2 vary independently on loop 1, thus we cannot express
2003
   the evolution with respect to loop 1:
2004
     analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2005
       analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2006
     analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2007
       analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2008
 
2009
   The value of k2 in the use in loop 1 is known, though:
2010
     analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2011
     analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2012
   */
2013
 
2014
static tree
2015
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2016
                                  tree version, bool *folded_casts)
2017
{
2018
  bool val = false;
2019
  tree ev = version, tmp;
2020
 
2021
  /* We cannot just do
2022
 
2023
     tmp = analyze_scalar_evolution (use_loop, version);
2024
     ev = resolve_mixers (wrto_loop, tmp);
2025
 
2026
     as resolve_mixers would query the scalar evolution with respect to
2027
     wrto_loop.  For example, in the situation described in the function
2028
     comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2029
     version = k2.  Then
2030
 
2031
     analyze_scalar_evolution (use_loop, version) = k2
2032
 
2033
     and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2034
     is 100, which is a wrong result, since we are interested in the
2035
     value in loop 3.
2036
 
2037
     Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2038
     each time checking that there is no evolution in the inner loop.  */
2039
 
2040
  if (folded_casts)
2041
    *folded_casts = false;
2042
  while (1)
2043
    {
2044
      tmp = analyze_scalar_evolution (use_loop, ev);
2045
      ev = resolve_mixers (use_loop, tmp);
2046
 
2047
      if (folded_casts && tmp != ev)
2048
        *folded_casts = true;
2049
 
2050
      if (use_loop == wrto_loop)
2051
        return ev;
2052
 
2053
      /* If the value of the use changes in the inner loop, we cannot express
2054
         its value in the outer loop (we might try to return interval chrec,
2055
         but we do not have a user for it anyway)  */
2056
      if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2057
          || !val)
2058
        return chrec_dont_know;
2059
 
2060
      use_loop = loop_outer (use_loop);
2061
    }
2062
}
2063
 
2064
/* Returns from CACHE the value for VERSION instantiated below
2065
   INSTANTIATED_BELOW block.  */
2066
 
2067
static tree
2068
get_instantiated_value (htab_t cache, basic_block instantiated_below,
2069
                        tree version)
2070
{
2071
  struct scev_info_str *info, pattern;
2072
 
2073
  pattern.var = version;
2074
  pattern.instantiated_below = instantiated_below;
2075
  info = (struct scev_info_str *) htab_find (cache, &pattern);
2076
 
2077
  if (info)
2078
    return info->chrec;
2079
  else
2080
    return NULL_TREE;
2081
}
2082
 
2083
/* Sets in CACHE the value of VERSION instantiated below basic block
2084
   INSTANTIATED_BELOW to VAL.  */
2085
 
2086
static void
2087
set_instantiated_value (htab_t cache, basic_block instantiated_below,
2088
                        tree version, tree val)
2089
{
2090
  struct scev_info_str *info, pattern;
2091
  PTR *slot;
2092
 
2093
  pattern.var = version;
2094
  pattern.instantiated_below = instantiated_below;
2095
  slot = htab_find_slot (cache, &pattern, INSERT);
2096
 
2097
  if (!*slot)
2098
    *slot = new_scev_info_str (instantiated_below, version);
2099
  info = (struct scev_info_str *) *slot;
2100
  info->chrec = val;
2101
}
2102
 
2103
/* Return the closed_loop_phi node for VAR.  If there is none, return
2104
   NULL_TREE.  */
2105
 
2106
static tree
2107
loop_closed_phi_def (tree var)
2108
{
2109
  struct loop *loop;
2110
  edge exit;
2111
  gimple phi;
2112
  gimple_stmt_iterator psi;
2113
 
2114
  if (var == NULL_TREE
2115
      || TREE_CODE (var) != SSA_NAME)
2116
    return NULL_TREE;
2117
 
2118
  loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2119
  exit = single_exit (loop);
2120
  if (!exit)
2121
    return NULL_TREE;
2122
 
2123
  for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2124
    {
2125
      phi = gsi_stmt (psi);
2126
      if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2127
        return PHI_RESULT (phi);
2128
    }
2129
 
2130
  return NULL_TREE;
2131
}
2132
 
2133
static tree instantiate_scev_r (basic_block, struct loop *, tree, bool,
2134
                                htab_t, int);
2135
 
2136
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2137
   and EVOLUTION_LOOP, that were left under a symbolic form.
2138
 
2139
   CHREC is an SSA_NAME to be instantiated.
2140
 
2141
   CACHE is the cache of already instantiated values.
2142
 
2143
   FOLD_CONVERSIONS should be set to true when the conversions that
2144
   may wrap in signed/pointer type are folded, as long as the value of
2145
   the chrec is preserved.
2146
 
2147
   SIZE_EXPR is used for computing the size of the expression to be
2148
   instantiated, and to stop if it exceeds some limit.  */
2149
 
2150
static tree
2151
instantiate_scev_name (basic_block instantiate_below,
2152
                       struct loop *evolution_loop, tree chrec,
2153
                       bool fold_conversions, htab_t cache, int size_expr)
2154
{
2155
  tree res;
2156
  struct loop *def_loop;
2157
  basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2158
 
2159
  /* A parameter (or loop invariant and we do not want to include
2160
     evolutions in outer loops), nothing to do.  */
2161
  if (!def_bb
2162
      || loop_depth (def_bb->loop_father) == 0
2163
      || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
2164
    return chrec;
2165
 
2166
  /* We cache the value of instantiated variable to avoid exponential
2167
     time complexity due to reevaluations.  We also store the convenient
2168
     value in the cache in order to prevent infinite recursion -- we do
2169
     not want to instantiate the SSA_NAME if it is in a mixer
2170
     structure.  This is used for avoiding the instantiation of
2171
     recursively defined functions, such as:
2172
 
2173
     | a_2 -> {0, +, 1, +, a_2}_1  */
2174
 
2175
  res = get_instantiated_value (cache, instantiate_below, chrec);
2176
  if (res)
2177
    return res;
2178
 
2179
  res = chrec_dont_know;
2180
  set_instantiated_value (cache, instantiate_below, chrec, res);
2181
 
2182
  def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2183
 
2184
  /* If the analysis yields a parametric chrec, instantiate the
2185
     result again.  */
2186
  res = analyze_scalar_evolution (def_loop, chrec);
2187
 
2188
  /* Don't instantiate default definitions.  */
2189
  if (TREE_CODE (res) == SSA_NAME
2190
      && SSA_NAME_IS_DEFAULT_DEF (res))
2191
    ;
2192
 
2193
  /* Don't instantiate loop-closed-ssa phi nodes.  */
2194
  else if (TREE_CODE (res) == SSA_NAME
2195
           && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2196
           > loop_depth (def_loop))
2197
    {
2198
      if (res == chrec)
2199
        res = loop_closed_phi_def (chrec);
2200
      else
2201
        res = chrec;
2202
 
2203
      /* When there is no loop_closed_phi_def, it means that the
2204
         variable is not used after the loop: try to still compute the
2205
         value of the variable when exiting the loop.  */
2206
      if (res == NULL_TREE)
2207
        {
2208
          loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2209
          res = analyze_scalar_evolution (loop, chrec);
2210
          res = compute_overall_effect_of_inner_loop (loop, res);
2211
          res = instantiate_scev_r (instantiate_below, evolution_loop, res,
2212
                                    fold_conversions, cache, size_expr);
2213
        }
2214
      else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
2215
                                gimple_bb (SSA_NAME_DEF_STMT (res))))
2216
        res = chrec_dont_know;
2217
    }
2218
 
2219
  else if (res != chrec_dont_know)
2220
    res = instantiate_scev_r (instantiate_below, evolution_loop, res,
2221
                              fold_conversions, cache, size_expr);
2222
 
2223
  /* Store the correct value to the cache.  */
2224
  set_instantiated_value (cache, instantiate_below, chrec, res);
2225
  return res;
2226
}
2227
 
2228
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2229
   and EVOLUTION_LOOP, that were left under a symbolic form.
2230
 
2231
   CHREC is a polynomial chain of recurrence to be instantiated.
2232
 
2233
   CACHE is the cache of already instantiated values.
2234
 
2235
   FOLD_CONVERSIONS should be set to true when the conversions that
2236
   may wrap in signed/pointer type are folded, as long as the value of
2237
   the chrec is preserved.
2238
 
2239
   SIZE_EXPR is used for computing the size of the expression to be
2240
   instantiated, and to stop if it exceeds some limit.  */
2241
 
2242
static tree
2243
instantiate_scev_poly (basic_block instantiate_below,
2244
                       struct loop *evolution_loop, tree chrec,
2245
                       bool fold_conversions, htab_t cache, int size_expr)
2246
{
2247
  tree op1;
2248
  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2249
                                 CHREC_LEFT (chrec), fold_conversions, cache,
2250
                                 size_expr);
2251
  if (op0 == chrec_dont_know)
2252
    return chrec_dont_know;
2253
 
2254
  op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2255
                            CHREC_RIGHT (chrec), fold_conversions, cache,
2256
                            size_expr);
2257
  if (op1 == chrec_dont_know)
2258
    return chrec_dont_know;
2259
 
2260
  if (CHREC_LEFT (chrec) != op0
2261
      || CHREC_RIGHT (chrec) != op1)
2262
    {
2263
      unsigned var = CHREC_VARIABLE (chrec);
2264
 
2265
      /* When the instantiated stride or base has an evolution in an
2266
         innermost loop, return chrec_dont_know, as this is not a
2267
         valid SCEV representation.  In the reduced testcase for
2268
         PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no
2269
         meaning.  */
2270
      if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var)
2271
          || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var))
2272
        return chrec_dont_know;
2273
 
2274
      op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2275
      chrec = build_polynomial_chrec (var, op0, op1);
2276
    }
2277
 
2278
  return chrec;
2279
}
2280
 
2281
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2282
   and EVOLUTION_LOOP, that were left under a symbolic form.
2283
 
2284
   "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2285
 
2286
   CACHE is the cache of already instantiated values.
2287
 
2288
   FOLD_CONVERSIONS should be set to true when the conversions that
2289
   may wrap in signed/pointer type are folded, as long as the value of
2290
   the chrec is preserved.
2291
 
2292
   SIZE_EXPR is used for computing the size of the expression to be
2293
   instantiated, and to stop if it exceeds some limit.  */
2294
 
2295
static tree
2296
instantiate_scev_binary (basic_block instantiate_below,
2297
                         struct loop *evolution_loop, tree chrec, enum tree_code code,
2298
                         tree type, tree c0, tree c1,
2299
                         bool fold_conversions, htab_t cache, int size_expr)
2300
{
2301
  tree op1;
2302
  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2303
                                 c0, fold_conversions, cache,
2304
                                 size_expr);
2305
  if (op0 == chrec_dont_know)
2306
    return chrec_dont_know;
2307
 
2308
  op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2309
                            c1, fold_conversions, cache,
2310
                            size_expr);
2311
  if (op1 == chrec_dont_know)
2312
    return chrec_dont_know;
2313
 
2314
  if (c0 != op0
2315
      || c1 != op1)
2316
    {
2317
      op0 = chrec_convert (type, op0, NULL);
2318
      op1 = chrec_convert_rhs (type, op1, NULL);
2319
 
2320
      switch (code)
2321
        {
2322
        case POINTER_PLUS_EXPR:
2323
        case PLUS_EXPR:
2324
          return chrec_fold_plus (type, op0, op1);
2325
 
2326
        case MINUS_EXPR:
2327
          return chrec_fold_minus (type, op0, op1);
2328
 
2329
        case MULT_EXPR:
2330
          return chrec_fold_multiply (type, op0, op1);
2331
 
2332
        default:
2333
          gcc_unreachable ();
2334
        }
2335
    }
2336
 
2337
  return chrec ? chrec : fold_build2 (code, type, c0, c1);
2338
}
2339
 
2340
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2341
   and EVOLUTION_LOOP, that were left under a symbolic form.
2342
 
2343
   "CHREC" is an array reference to be instantiated.
2344
 
2345
   CACHE is the cache of already instantiated values.
2346
 
2347
   FOLD_CONVERSIONS should be set to true when the conversions that
2348
   may wrap in signed/pointer type are folded, as long as the value of
2349
   the chrec is preserved.
2350
 
2351
   SIZE_EXPR is used for computing the size of the expression to be
2352
   instantiated, and to stop if it exceeds some limit.  */
2353
 
2354
static tree
2355
instantiate_array_ref (basic_block instantiate_below,
2356
                       struct loop *evolution_loop, tree chrec,
2357
                       bool fold_conversions, htab_t cache, int size_expr)
2358
{
2359
  tree res;
2360
  tree index = TREE_OPERAND (chrec, 1);
2361
  tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index,
2362
                                 fold_conversions, cache, size_expr);
2363
 
2364
  if (op1 == chrec_dont_know)
2365
    return chrec_dont_know;
2366
 
2367
  if (chrec && op1 == index)
2368
    return chrec;
2369
 
2370
  res = unshare_expr (chrec);
2371
  TREE_OPERAND (res, 1) = op1;
2372
  return res;
2373
}
2374
 
2375
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2376
   and EVOLUTION_LOOP, that were left under a symbolic form.
2377
 
2378
   "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2379
   instantiated.
2380
 
2381
   CACHE is the cache of already instantiated values.
2382
 
2383
   FOLD_CONVERSIONS should be set to true when the conversions that
2384
   may wrap in signed/pointer type are folded, as long as the value of
2385
   the chrec is preserved.
2386
 
2387
   SIZE_EXPR is used for computing the size of the expression to be
2388
   instantiated, and to stop if it exceeds some limit.  */
2389
 
2390
static tree
2391
instantiate_scev_convert (basic_block instantiate_below,
2392
                          struct loop *evolution_loop, tree chrec,
2393
                          tree type, tree op,
2394
                          bool fold_conversions, htab_t cache, int size_expr)
2395
{
2396
  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2397
                                 fold_conversions, cache, size_expr);
2398
 
2399
  if (op0 == chrec_dont_know)
2400
    return chrec_dont_know;
2401
 
2402
  if (fold_conversions)
2403
    {
2404
      tree tmp = chrec_convert_aggressive (type, op0);
2405
      if (tmp)
2406
        return tmp;
2407
    }
2408
 
2409
  if (chrec && op0 == op)
2410
    return chrec;
2411
 
2412
  /* If we used chrec_convert_aggressive, we can no longer assume that
2413
     signed chrecs do not overflow, as chrec_convert does, so avoid
2414
     calling it in that case.  */
2415
  if (fold_conversions)
2416
    return fold_convert (type, op0);
2417
 
2418
  return chrec_convert (type, op0, NULL);
2419
}
2420
 
2421
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2422
   and EVOLUTION_LOOP, that were left under a symbolic form.
2423
 
2424
   CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2425
   Handle ~X as -1 - X.
2426
   Handle -X as -1 * X.
2427
 
2428
   CACHE is the cache of already instantiated values.
2429
 
2430
   FOLD_CONVERSIONS should be set to true when the conversions that
2431
   may wrap in signed/pointer type are folded, as long as the value of
2432
   the chrec is preserved.
2433
 
2434
   SIZE_EXPR is used for computing the size of the expression to be
2435
   instantiated, and to stop if it exceeds some limit.  */
2436
 
2437
static tree
2438
instantiate_scev_not (basic_block instantiate_below,
2439
                      struct loop *evolution_loop, tree chrec,
2440
                      enum tree_code code, tree type, tree op,
2441
                      bool fold_conversions, htab_t cache, int size_expr)
2442
{
2443
  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op,
2444
                                 fold_conversions, cache, size_expr);
2445
 
2446
  if (op0 == chrec_dont_know)
2447
    return chrec_dont_know;
2448
 
2449
  if (op != op0)
2450
    {
2451
      op0 = chrec_convert (type, op0, NULL);
2452
 
2453
      switch (code)
2454
        {
2455
        case BIT_NOT_EXPR:
2456
          return chrec_fold_minus
2457
            (type, fold_convert (type, integer_minus_one_node), op0);
2458
 
2459
        case NEGATE_EXPR:
2460
          return chrec_fold_multiply
2461
            (type, fold_convert (type, integer_minus_one_node), op0);
2462
 
2463
        default:
2464
          gcc_unreachable ();
2465
        }
2466
    }
2467
 
2468
  return chrec ? chrec : fold_build1 (code, type, op0);
2469
}
2470
 
2471
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2472
   and EVOLUTION_LOOP, that were left under a symbolic form.
2473
 
2474
   CHREC is an expression with 3 operands to be instantiated.
2475
 
2476
   CACHE is the cache of already instantiated values.
2477
 
2478
   FOLD_CONVERSIONS should be set to true when the conversions that
2479
   may wrap in signed/pointer type are folded, as long as the value of
2480
   the chrec is preserved.
2481
 
2482
   SIZE_EXPR is used for computing the size of the expression to be
2483
   instantiated, and to stop if it exceeds some limit.  */
2484
 
2485
static tree
2486
instantiate_scev_3 (basic_block instantiate_below,
2487
                    struct loop *evolution_loop, tree chrec,
2488
                    bool fold_conversions, htab_t cache, int size_expr)
2489
{
2490
  tree op1, op2;
2491
  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2492
                                 TREE_OPERAND (chrec, 0),
2493
                                 fold_conversions, cache, size_expr);
2494
  if (op0 == chrec_dont_know)
2495
    return chrec_dont_know;
2496
 
2497
  op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2498
                            TREE_OPERAND (chrec, 1),
2499
                            fold_conversions, cache, size_expr);
2500
  if (op1 == chrec_dont_know)
2501
    return chrec_dont_know;
2502
 
2503
  op2 = instantiate_scev_r (instantiate_below, evolution_loop,
2504
                            TREE_OPERAND (chrec, 2),
2505
                            fold_conversions, cache, size_expr);
2506
  if (op2 == chrec_dont_know)
2507
    return chrec_dont_know;
2508
 
2509
  if (op0 == TREE_OPERAND (chrec, 0)
2510
      && op1 == TREE_OPERAND (chrec, 1)
2511
      && op2 == TREE_OPERAND (chrec, 2))
2512
    return chrec;
2513
 
2514
  return fold_build3 (TREE_CODE (chrec),
2515
                      TREE_TYPE (chrec), op0, op1, op2);
2516
}
2517
 
2518
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2519
   and EVOLUTION_LOOP, that were left under a symbolic form.
2520
 
2521
   CHREC is an expression with 2 operands to be instantiated.
2522
 
2523
   CACHE is the cache of already instantiated values.
2524
 
2525
   FOLD_CONVERSIONS should be set to true when the conversions that
2526
   may wrap in signed/pointer type are folded, as long as the value of
2527
   the chrec is preserved.
2528
 
2529
   SIZE_EXPR is used for computing the size of the expression to be
2530
   instantiated, and to stop if it exceeds some limit.  */
2531
 
2532
static tree
2533
instantiate_scev_2 (basic_block instantiate_below,
2534
                    struct loop *evolution_loop, tree chrec,
2535
                    bool fold_conversions, htab_t cache, int size_expr)
2536
{
2537
  tree op1;
2538
  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2539
                                 TREE_OPERAND (chrec, 0),
2540
                                 fold_conversions, cache, size_expr);
2541
  if (op0 == chrec_dont_know)
2542
    return chrec_dont_know;
2543
 
2544
  op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2545
                            TREE_OPERAND (chrec, 1),
2546
                            fold_conversions, cache, size_expr);
2547
  if (op1 == chrec_dont_know)
2548
    return chrec_dont_know;
2549
 
2550
  if (op0 == TREE_OPERAND (chrec, 0)
2551
      && op1 == TREE_OPERAND (chrec, 1))
2552
    return chrec;
2553
 
2554
  return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2555
}
2556
 
2557
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2558
   and EVOLUTION_LOOP, that were left under a symbolic form.
2559
 
2560
   CHREC is an expression with 2 operands to be instantiated.
2561
 
2562
   CACHE is the cache of already instantiated values.
2563
 
2564
   FOLD_CONVERSIONS should be set to true when the conversions that
2565
   may wrap in signed/pointer type are folded, as long as the value of
2566
   the chrec is preserved.
2567
 
2568
   SIZE_EXPR is used for computing the size of the expression to be
2569
   instantiated, and to stop if it exceeds some limit.  */
2570
 
2571
static tree
2572
instantiate_scev_1 (basic_block instantiate_below,
2573
                    struct loop *evolution_loop, tree chrec,
2574
                    bool fold_conversions, htab_t cache, int size_expr)
2575
{
2576
  tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2577
                                 TREE_OPERAND (chrec, 0),
2578
                                 fold_conversions, cache, size_expr);
2579
 
2580
  if (op0 == chrec_dont_know)
2581
    return chrec_dont_know;
2582
 
2583
  if (op0 == TREE_OPERAND (chrec, 0))
2584
    return chrec;
2585
 
2586
  return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2587
}
2588
 
2589
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2590
   and EVOLUTION_LOOP, that were left under a symbolic form.
2591
 
2592
   CHREC is the scalar evolution to instantiate.
2593
 
2594
   CACHE is the cache of already instantiated values.
2595
 
2596
   FOLD_CONVERSIONS should be set to true when the conversions that
2597
   may wrap in signed/pointer type are folded, as long as the value of
2598
   the chrec is preserved.
2599
 
2600
   SIZE_EXPR is used for computing the size of the expression to be
2601
   instantiated, and to stop if it exceeds some limit.  */
2602
 
2603
static tree
2604
instantiate_scev_r (basic_block instantiate_below,
2605
                    struct loop *evolution_loop, tree chrec,
2606
                    bool fold_conversions, htab_t cache, int size_expr)
2607
{
2608
  /* Give up if the expression is larger than the MAX that we allow.  */
2609
  if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2610
    return chrec_dont_know;
2611
 
2612
  if (chrec == NULL_TREE
2613
      || automatically_generated_chrec_p (chrec)
2614
      || is_gimple_min_invariant (chrec))
2615
    return chrec;
2616
 
2617
  switch (TREE_CODE (chrec))
2618
    {
2619
    case SSA_NAME:
2620
      return instantiate_scev_name (instantiate_below, evolution_loop, chrec,
2621
                                    fold_conversions, cache, size_expr);
2622
 
2623
    case POLYNOMIAL_CHREC:
2624
      return instantiate_scev_poly (instantiate_below, evolution_loop, chrec,
2625
                                    fold_conversions, cache, size_expr);
2626
 
2627
    case POINTER_PLUS_EXPR:
2628
    case PLUS_EXPR:
2629
    case MINUS_EXPR:
2630
    case MULT_EXPR:
2631
      return instantiate_scev_binary (instantiate_below, evolution_loop, chrec,
2632
                                      TREE_CODE (chrec), chrec_type (chrec),
2633
                                      TREE_OPERAND (chrec, 0),
2634
                                      TREE_OPERAND (chrec, 1),
2635
                                      fold_conversions, cache, size_expr);
2636
 
2637
    CASE_CONVERT:
2638
      return instantiate_scev_convert (instantiate_below, evolution_loop, chrec,
2639
                                       TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2640
                                       fold_conversions, cache, size_expr);
2641
 
2642
    case NEGATE_EXPR:
2643
    case BIT_NOT_EXPR:
2644
      return instantiate_scev_not (instantiate_below, evolution_loop, chrec,
2645
                                   TREE_CODE (chrec), TREE_TYPE (chrec),
2646
                                   TREE_OPERAND (chrec, 0),
2647
                                   fold_conversions, cache, size_expr);
2648
 
2649
    case ADDR_EXPR:
2650
    case SCEV_NOT_KNOWN:
2651
      return chrec_dont_know;
2652
 
2653
    case SCEV_KNOWN:
2654
      return chrec_known;
2655
 
2656
    case ARRAY_REF:
2657
      return instantiate_array_ref (instantiate_below, evolution_loop, chrec,
2658
                                    fold_conversions, cache, size_expr);
2659
 
2660
    default:
2661
      break;
2662
    }
2663
 
2664
  if (VL_EXP_CLASS_P (chrec))
2665
    return chrec_dont_know;
2666
 
2667
  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2668
    {
2669
    case 3:
2670
      return instantiate_scev_3 (instantiate_below, evolution_loop, chrec,
2671
                                 fold_conversions, cache, size_expr);
2672
 
2673
    case 2:
2674
      return instantiate_scev_2 (instantiate_below, evolution_loop, chrec,
2675
                                 fold_conversions, cache, size_expr);
2676
 
2677
    case 1:
2678
      return instantiate_scev_1 (instantiate_below, evolution_loop, chrec,
2679
                                 fold_conversions, cache, size_expr);
2680
 
2681
    case 0:
2682
      return chrec;
2683
 
2684
    default:
2685
      break;
2686
    }
2687
 
2688
  /* Too complicated to handle.  */
2689
  return chrec_dont_know;
2690
}
2691
 
2692
/* Analyze all the parameters of the chrec that were left under a
2693
   symbolic form.  INSTANTIATE_BELOW is the basic block that stops the
2694
   recursive instantiation of parameters: a parameter is a variable
2695
   that is defined in a basic block that dominates INSTANTIATE_BELOW or
2696
   a function parameter.  */
2697
 
2698
tree
2699
instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2700
                  tree chrec)
2701
{
2702
  tree res;
2703
  htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2704
 
2705
  if (dump_file && (dump_flags & TDF_SCEV))
2706
    {
2707
      fprintf (dump_file, "(instantiate_scev \n");
2708
      fprintf (dump_file, "  (instantiate_below = %d)\n", instantiate_below->index);
2709
      fprintf (dump_file, "  (evolution_loop = %d)\n", evolution_loop->num);
2710
      fprintf (dump_file, "  (chrec = ");
2711
      print_generic_expr (dump_file, chrec, 0);
2712
      fprintf (dump_file, ")\n");
2713
    }
2714
 
2715
  res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false,
2716
                            cache, 0);
2717
 
2718
  if (dump_file && (dump_flags & TDF_SCEV))
2719
    {
2720
      fprintf (dump_file, "  (res = ");
2721
      print_generic_expr (dump_file, res, 0);
2722
      fprintf (dump_file, "))\n");
2723
    }
2724
 
2725
  htab_delete (cache);
2726
 
2727
  return res;
2728
}
2729
 
2730
/* Similar to instantiate_parameters, but does not introduce the
2731
   evolutions in outer loops for LOOP invariants in CHREC, and does not
2732
   care about causing overflows, as long as they do not affect value
2733
   of an expression.  */
2734
 
2735
tree
2736
resolve_mixers (struct loop *loop, tree chrec)
2737
{
2738
  htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2739
  tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true,
2740
                                 cache, 0);
2741
  htab_delete (cache);
2742
  return ret;
2743
}
2744
 
2745
/* Entry point for the analysis of the number of iterations pass.
2746
   This function tries to safely approximate the number of iterations
2747
   the loop will run.  When this property is not decidable at compile
2748
   time, the result is chrec_dont_know.  Otherwise the result is a
2749
   scalar or a symbolic parameter.  When the number of iterations may
2750
   be equal to zero and the property cannot be determined at compile
2751
   time, the result is a COND_EXPR that represents in a symbolic form
2752
   the conditions under which the number of iterations is not zero.
2753
 
2754
   Example of analysis: suppose that the loop has an exit condition:
2755
 
2756
   "if (b > 49) goto end_loop;"
2757
 
2758
   and that in a previous analysis we have determined that the
2759
   variable 'b' has an evolution function:
2760
 
2761
   "EF = {23, +, 5}_2".
2762
 
2763
   When we evaluate the function at the point 5, i.e. the value of the
2764
   variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2765
   and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2766
   the loop body has been executed 6 times.  */
2767
 
2768
tree
2769
number_of_latch_executions (struct loop *loop)
2770
{
2771
  edge exit;
2772
  struct tree_niter_desc niter_desc;
2773
  tree may_be_zero;
2774
  tree res;
2775
 
2776
  /* Determine whether the number of iterations in loop has already
2777
     been computed.  */
2778
  res = loop->nb_iterations;
2779
  if (res)
2780
    return res;
2781
 
2782
  may_be_zero = NULL_TREE;
2783
 
2784
  if (dump_file && (dump_flags & TDF_SCEV))
2785
    fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2786
 
2787
  res = chrec_dont_know;
2788
  exit = single_exit (loop);
2789
 
2790
  if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2791
    {
2792
      may_be_zero = niter_desc.may_be_zero;
2793
      res = niter_desc.niter;
2794
    }
2795
 
2796
  if (res == chrec_dont_know
2797
      || !may_be_zero
2798
      || integer_zerop (may_be_zero))
2799
    ;
2800
  else if (integer_nonzerop (may_be_zero))
2801
    res = build_int_cst (TREE_TYPE (res), 0);
2802
 
2803
  else if (COMPARISON_CLASS_P (may_be_zero))
2804
    res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2805
                       build_int_cst (TREE_TYPE (res), 0), res);
2806
  else
2807
    res = chrec_dont_know;
2808
 
2809
  if (dump_file && (dump_flags & TDF_SCEV))
2810
    {
2811
      fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
2812
      print_generic_expr (dump_file, res, 0);
2813
      fprintf (dump_file, "))\n");
2814
    }
2815
 
2816
  loop->nb_iterations = res;
2817
  return res;
2818
}
2819
 
2820
/* Returns the number of executions of the exit condition of LOOP,
2821
   i.e., the number by one higher than number_of_latch_executions.
2822
   Note that unlike number_of_latch_executions, this number does
2823
   not necessarily fit in the unsigned variant of the type of
2824
   the control variable -- if the number of iterations is a constant,
2825
   we return chrec_dont_know if adding one to number_of_latch_executions
2826
   overflows; however, in case the number of iterations is symbolic
2827
   expression, the caller is responsible for dealing with this
2828
   the possible overflow.  */
2829
 
2830
tree
2831
number_of_exit_cond_executions (struct loop *loop)
2832
{
2833
  tree ret = number_of_latch_executions (loop);
2834
  tree type = chrec_type (ret);
2835
 
2836
  if (chrec_contains_undetermined (ret))
2837
    return ret;
2838
 
2839
  ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
2840
  if (TREE_CODE (ret) == INTEGER_CST
2841
      && TREE_OVERFLOW (ret))
2842
    return chrec_dont_know;
2843
 
2844
  return ret;
2845
}
2846
 
2847
/* One of the drivers for testing the scalar evolutions analysis.
2848
   This function computes the number of iterations for all the loops
2849
   from the EXIT_CONDITIONS array.  */
2850
 
2851
static void
2852
number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions)
2853
{
2854
  unsigned int i;
2855
  unsigned nb_chrec_dont_know_loops = 0;
2856
  unsigned nb_static_loops = 0;
2857
  gimple cond;
2858
 
2859
  FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
2860
    {
2861
      tree res = number_of_latch_executions (loop_containing_stmt (cond));
2862
      if (chrec_contains_undetermined (res))
2863
        nb_chrec_dont_know_loops++;
2864
      else
2865
        nb_static_loops++;
2866
    }
2867
 
2868
  if (dump_file)
2869
    {
2870
      fprintf (dump_file, "\n(\n");
2871
      fprintf (dump_file, "-----------------------------------------\n");
2872
      fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2873
      fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2874
      fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
2875
      fprintf (dump_file, "-----------------------------------------\n");
2876
      fprintf (dump_file, ")\n\n");
2877
 
2878
      print_loops (dump_file, 3);
2879
    }
2880
}
2881
 
2882
 
2883
 
2884
/* Counters for the stats.  */
2885
 
2886
struct chrec_stats
2887
{
2888
  unsigned nb_chrecs;
2889
  unsigned nb_affine;
2890
  unsigned nb_affine_multivar;
2891
  unsigned nb_higher_poly;
2892
  unsigned nb_chrec_dont_know;
2893
  unsigned nb_undetermined;
2894
};
2895
 
2896
/* Reset the counters.  */
2897
 
2898
static inline void
2899
reset_chrecs_counters (struct chrec_stats *stats)
2900
{
2901
  stats->nb_chrecs = 0;
2902
  stats->nb_affine = 0;
2903
  stats->nb_affine_multivar = 0;
2904
  stats->nb_higher_poly = 0;
2905
  stats->nb_chrec_dont_know = 0;
2906
  stats->nb_undetermined = 0;
2907
}
2908
 
2909
/* Dump the contents of a CHREC_STATS structure.  */
2910
 
2911
static void
2912
dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2913
{
2914
  fprintf (file, "\n(\n");
2915
  fprintf (file, "-----------------------------------------\n");
2916
  fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2917
  fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2918
  fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2919
           stats->nb_higher_poly);
2920
  fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2921
  fprintf (file, "-----------------------------------------\n");
2922
  fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2923
  fprintf (file, "%d\twith undetermined coefficients\n",
2924
           stats->nb_undetermined);
2925
  fprintf (file, "-----------------------------------------\n");
2926
  fprintf (file, "%d\tchrecs in the scev database\n",
2927
           (int) htab_elements (scalar_evolution_info));
2928
  fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2929
  fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2930
  fprintf (file, "-----------------------------------------\n");
2931
  fprintf (file, ")\n\n");
2932
}
2933
 
2934
/* Gather statistics about CHREC.  */
2935
 
2936
static void
2937
gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2938
{
2939
  if (dump_file && (dump_flags & TDF_STATS))
2940
    {
2941
      fprintf (dump_file, "(classify_chrec ");
2942
      print_generic_expr (dump_file, chrec, 0);
2943
      fprintf (dump_file, "\n");
2944
    }
2945
 
2946
  stats->nb_chrecs++;
2947
 
2948
  if (chrec == NULL_TREE)
2949
    {
2950
      stats->nb_undetermined++;
2951
      return;
2952
    }
2953
 
2954
  switch (TREE_CODE (chrec))
2955
    {
2956
    case POLYNOMIAL_CHREC:
2957
      if (evolution_function_is_affine_p (chrec))
2958
        {
2959
          if (dump_file && (dump_flags & TDF_STATS))
2960
            fprintf (dump_file, "  affine_univariate\n");
2961
          stats->nb_affine++;
2962
        }
2963
      else if (evolution_function_is_affine_multivariate_p (chrec, 0))
2964
        {
2965
          if (dump_file && (dump_flags & TDF_STATS))
2966
            fprintf (dump_file, "  affine_multivariate\n");
2967
          stats->nb_affine_multivar++;
2968
        }
2969
      else
2970
        {
2971
          if (dump_file && (dump_flags & TDF_STATS))
2972
            fprintf (dump_file, "  higher_degree_polynomial\n");
2973
          stats->nb_higher_poly++;
2974
        }
2975
 
2976
      break;
2977
 
2978
    default:
2979
      break;
2980
    }
2981
 
2982
  if (chrec_contains_undetermined (chrec))
2983
    {
2984
      if (dump_file && (dump_flags & TDF_STATS))
2985
        fprintf (dump_file, "  undetermined\n");
2986
      stats->nb_undetermined++;
2987
    }
2988
 
2989
  if (dump_file && (dump_flags & TDF_STATS))
2990
    fprintf (dump_file, ")\n");
2991
}
2992
 
2993
/* One of the drivers for testing the scalar evolutions analysis.
2994
   This function analyzes the scalar evolution of all the scalars
2995
   defined as loop phi nodes in one of the loops from the
2996
   EXIT_CONDITIONS array.
2997
 
2998
   TODO Optimization: A loop is in canonical form if it contains only
2999
   a single scalar loop phi node.  All the other scalars that have an
3000
   evolution in the loop are rewritten in function of this single
3001
   index.  This allows the parallelization of the loop.  */
3002
 
3003
static void
3004
analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions)
3005
{
3006
  unsigned int i;
3007
  struct chrec_stats stats;
3008
  gimple cond, phi;
3009
  gimple_stmt_iterator psi;
3010
 
3011
  reset_chrecs_counters (&stats);
3012
 
3013
  FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
3014
    {
3015
      struct loop *loop;
3016
      basic_block bb;
3017
      tree chrec;
3018
 
3019
      loop = loop_containing_stmt (cond);
3020
      bb = loop->header;
3021
 
3022
      for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3023
        {
3024
          phi = gsi_stmt (psi);
3025
          if (is_gimple_reg (PHI_RESULT (phi)))
3026
            {
3027
              chrec = instantiate_parameters
3028
                        (loop,
3029
                         analyze_scalar_evolution (loop, PHI_RESULT (phi)));
3030
 
3031
              if (dump_file && (dump_flags & TDF_STATS))
3032
                gather_chrec_stats (chrec, &stats);
3033
            }
3034
        }
3035
    }
3036
 
3037
  if (dump_file && (dump_flags & TDF_STATS))
3038
    dump_chrecs_stats (dump_file, &stats);
3039
}
3040
 
3041
/* Callback for htab_traverse, gathers information on chrecs in the
3042
   hashtable.  */
3043
 
3044
static int
3045
gather_stats_on_scev_database_1 (void **slot, void *stats)
3046
{
3047
  struct scev_info_str *entry = (struct scev_info_str *) *slot;
3048
 
3049
  gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
3050
 
3051
  return 1;
3052
}
3053
 
3054
/* Classify the chrecs of the whole database.  */
3055
 
3056
void
3057
gather_stats_on_scev_database (void)
3058
{
3059
  struct chrec_stats stats;
3060
 
3061
  if (!dump_file)
3062
    return;
3063
 
3064
  reset_chrecs_counters (&stats);
3065
 
3066
  htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
3067
                 &stats);
3068
 
3069
  dump_chrecs_stats (dump_file, &stats);
3070
}
3071
 
3072
 
3073
 
3074
/* Initializer.  */
3075
 
3076
static void
3077
initialize_scalar_evolutions_analyzer (void)
3078
{
3079
  /* The elements below are unique.  */
3080
  if (chrec_dont_know == NULL_TREE)
3081
    {
3082
      chrec_not_analyzed_yet = NULL_TREE;
3083
      chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3084
      chrec_known = make_node (SCEV_KNOWN);
3085
      TREE_TYPE (chrec_dont_know) = void_type_node;
3086
      TREE_TYPE (chrec_known) = void_type_node;
3087
    }
3088
}
3089
 
3090
/* Initialize the analysis of scalar evolutions for LOOPS.  */
3091
 
3092
void
3093
scev_initialize (void)
3094
{
3095
  loop_iterator li;
3096
  struct loop *loop;
3097
 
3098
 
3099
  scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info,
3100
                                           del_scev_info);
3101
 
3102
  initialize_scalar_evolutions_analyzer ();
3103
 
3104
  FOR_EACH_LOOP (li, loop, 0)
3105
    {
3106
      loop->nb_iterations = NULL_TREE;
3107
    }
3108
}
3109
 
3110
/* Cleans up the information cached by the scalar evolutions analysis
3111
   in the hash table.  */
3112
 
3113
void
3114
scev_reset_htab (void)
3115
{
3116
  if (!scalar_evolution_info)
3117
    return;
3118
 
3119
  htab_empty (scalar_evolution_info);
3120
}
3121
 
3122
/* Cleans up the information cached by the scalar evolutions analysis
3123
   in the hash table and in the loop->nb_iterations.  */
3124
 
3125
void
3126
scev_reset (void)
3127
{
3128
  loop_iterator li;
3129
  struct loop *loop;
3130
 
3131
  scev_reset_htab ();
3132
 
3133
  if (!current_loops)
3134
    return;
3135
 
3136
  FOR_EACH_LOOP (li, loop, 0)
3137
    {
3138
      loop->nb_iterations = NULL_TREE;
3139
    }
3140
}
3141
 
3142
/* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3143
   respect to WRTO_LOOP and returns its base and step in IV if possible
3144
   (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3145
   and WRTO_LOOP).  If ALLOW_NONCONSTANT_STEP is true, we want step to be
3146
   invariant in LOOP.  Otherwise we require it to be an integer constant.
3147
 
3148
   IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3149
   because it is computed in signed arithmetics).  Consequently, adding an
3150
   induction variable
3151
 
3152
   for (i = IV->base; ; i += IV->step)
3153
 
3154
   is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3155
   false for the type of the induction variable, or you can prove that i does
3156
   not wrap by some other argument.  Otherwise, this might introduce undefined
3157
   behavior, and
3158
 
3159
   for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3160
 
3161
   must be used instead.  */
3162
 
3163
bool
3164
simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3165
           affine_iv *iv, bool allow_nonconstant_step)
3166
{
3167
  tree type, ev;
3168
  bool folded_casts;
3169
 
3170
  iv->base = NULL_TREE;
3171
  iv->step = NULL_TREE;
3172
  iv->no_overflow = false;
3173
 
3174
  type = TREE_TYPE (op);
3175
  if (!POINTER_TYPE_P (type)
3176
      && !INTEGRAL_TYPE_P (type))
3177
    return false;
3178
 
3179
  ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3180
                                         &folded_casts);
3181
  if (chrec_contains_undetermined (ev)
3182
      || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3183
    return false;
3184
 
3185
  if (tree_does_not_contain_chrecs (ev))
3186
    {
3187
      iv->base = ev;
3188
      iv->step = build_int_cst (TREE_TYPE (ev), 0);
3189
      iv->no_overflow = true;
3190
      return true;
3191
    }
3192
 
3193
  if (TREE_CODE (ev) != POLYNOMIAL_CHREC
3194
      || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3195
    return false;
3196
 
3197
  iv->step = CHREC_RIGHT (ev);
3198
  if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3199
      || tree_contains_chrecs (iv->step, NULL))
3200
    return false;
3201
 
3202
  iv->base = CHREC_LEFT (ev);
3203
  if (tree_contains_chrecs (iv->base, NULL))
3204
    return false;
3205
 
3206
  iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
3207
 
3208
  return true;
3209
}
3210
 
3211
/* Runs the analysis of scalar evolutions.  */
3212
 
3213
void
3214
scev_analysis (void)
3215
{
3216
  VEC(gimple,heap) *exit_conditions;
3217
 
3218
  exit_conditions = VEC_alloc (gimple, heap, 37);
3219
  select_loops_exit_conditions (&exit_conditions);
3220
 
3221
  if (dump_file && (dump_flags & TDF_STATS))
3222
    analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
3223
 
3224
  number_of_iterations_for_all_loops (&exit_conditions);
3225
  VEC_free (gimple, heap, exit_conditions);
3226
}
3227
 
3228
/* Finalize the scalar evolution analysis.  */
3229
 
3230
void
3231
scev_finalize (void)
3232
{
3233
  if (!scalar_evolution_info)
3234
    return;
3235
  htab_delete (scalar_evolution_info);
3236
  scalar_evolution_info = NULL;
3237
}
3238
 
3239
/* Returns true if the expression EXPR is considered to be too expensive
3240
   for scev_const_prop.  */
3241
 
3242
bool
3243
expression_expensive_p (tree expr)
3244
{
3245
  enum tree_code code;
3246
 
3247
  if (is_gimple_val (expr))
3248
    return false;
3249
 
3250
  code = TREE_CODE (expr);
3251
  if (code == TRUNC_DIV_EXPR
3252
      || code == CEIL_DIV_EXPR
3253
      || code == FLOOR_DIV_EXPR
3254
      || code == ROUND_DIV_EXPR
3255
      || code == TRUNC_MOD_EXPR
3256
      || code == CEIL_MOD_EXPR
3257
      || code == FLOOR_MOD_EXPR
3258
      || code == ROUND_MOD_EXPR
3259
      || code == EXACT_DIV_EXPR)
3260
    {
3261
      /* Division by power of two is usually cheap, so we allow it.
3262
         Forbid anything else.  */
3263
      if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3264
        return true;
3265
    }
3266
 
3267
  switch (TREE_CODE_CLASS (code))
3268
    {
3269
    case tcc_binary:
3270
    case tcc_comparison:
3271
      if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3272
        return true;
3273
 
3274
      /* Fallthru.  */
3275
    case tcc_unary:
3276
      return expression_expensive_p (TREE_OPERAND (expr, 0));
3277
 
3278
    default:
3279
      return true;
3280
    }
3281
}
3282
 
3283
/* Replace ssa names for that scev can prove they are constant by the
3284
   appropriate constants.  Also perform final value replacement in loops,
3285
   in case the replacement expressions are cheap.
3286
 
3287
   We only consider SSA names defined by phi nodes; rest is left to the
3288
   ordinary constant propagation pass.  */
3289
 
3290
unsigned int
3291
scev_const_prop (void)
3292
{
3293
  basic_block bb;
3294
  tree name, type, ev;
3295
  gimple phi, ass;
3296
  struct loop *loop, *ex_loop;
3297
  bitmap ssa_names_to_remove = NULL;
3298
  unsigned i;
3299
  loop_iterator li;
3300
  gimple_stmt_iterator psi;
3301
 
3302
  if (number_of_loops () <= 1)
3303
    return 0;
3304
 
3305
  FOR_EACH_BB (bb)
3306
    {
3307
      loop = bb->loop_father;
3308
 
3309
      for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3310
        {
3311
          phi = gsi_stmt (psi);
3312
          name = PHI_RESULT (phi);
3313
 
3314
          if (!is_gimple_reg (name))
3315
            continue;
3316
 
3317
          type = TREE_TYPE (name);
3318
 
3319
          if (!POINTER_TYPE_P (type)
3320
              && !INTEGRAL_TYPE_P (type))
3321
            continue;
3322
 
3323
          ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3324
          if (!is_gimple_min_invariant (ev)
3325
              || !may_propagate_copy (name, ev))
3326
            continue;
3327
 
3328
          /* Replace the uses of the name.  */
3329
          if (name != ev)
3330
            replace_uses_by (name, ev);
3331
 
3332
          if (!ssa_names_to_remove)
3333
            ssa_names_to_remove = BITMAP_ALLOC (NULL);
3334
          bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3335
        }
3336
    }
3337
 
3338
  /* Remove the ssa names that were replaced by constants.  We do not
3339
     remove them directly in the previous cycle, since this
3340
     invalidates scev cache.  */
3341
  if (ssa_names_to_remove)
3342
    {
3343
      bitmap_iterator bi;
3344
 
3345
      EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3346
        {
3347
          gimple_stmt_iterator psi;
3348
          name = ssa_name (i);
3349
          phi = SSA_NAME_DEF_STMT (name);
3350
 
3351
          gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3352
          psi = gsi_for_stmt (phi);
3353
          remove_phi_node (&psi, true);
3354
        }
3355
 
3356
      BITMAP_FREE (ssa_names_to_remove);
3357
      scev_reset ();
3358
    }
3359
 
3360
  /* Now the regular final value replacement.  */
3361
  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
3362
    {
3363
      edge exit;
3364
      tree def, rslt, niter;
3365
      gimple_stmt_iterator bsi;
3366
 
3367
      /* If we do not know exact number of iterations of the loop, we cannot
3368
         replace the final value.  */
3369
      exit = single_exit (loop);
3370
      if (!exit)
3371
        continue;
3372
 
3373
      niter = number_of_latch_executions (loop);
3374
      if (niter == chrec_dont_know)
3375
        continue;
3376
 
3377
      /* Ensure that it is possible to insert new statements somewhere.  */
3378
      if (!single_pred_p (exit->dest))
3379
        split_loop_exit_edge (exit);
3380
      bsi = gsi_after_labels (exit->dest);
3381
 
3382
      ex_loop = superloop_at_depth (loop,
3383
                                    loop_depth (exit->dest->loop_father) + 1);
3384
 
3385
      for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3386
        {
3387
          phi = gsi_stmt (psi);
3388
          rslt = PHI_RESULT (phi);
3389
          def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3390
          if (!is_gimple_reg (def))
3391
            {
3392
              gsi_next (&psi);
3393
              continue;
3394
            }
3395
 
3396
          if (!POINTER_TYPE_P (TREE_TYPE (def))
3397
              && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3398
            {
3399
              gsi_next (&psi);
3400
              continue;
3401
            }
3402
 
3403
          def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
3404
          def = compute_overall_effect_of_inner_loop (ex_loop, def);
3405
          if (!tree_does_not_contain_chrecs (def)
3406
              || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3407
              /* Moving the computation from the loop may prolong life range
3408
                 of some ssa names, which may cause problems if they appear
3409
                 on abnormal edges.  */
3410
              || contains_abnormal_ssa_name_p (def)
3411
              /* Do not emit expensive expressions.  The rationale is that
3412
                 when someone writes a code like
3413
 
3414
                 while (n > 45) n -= 45;
3415
 
3416
                 he probably knows that n is not large, and does not want it
3417
                 to be turned into n %= 45.  */
3418
              || expression_expensive_p (def))
3419
            {
3420
              gsi_next (&psi);
3421
              continue;
3422
            }
3423
 
3424
          /* Eliminate the PHI node and replace it by a computation outside
3425
             the loop.  */
3426
          def = unshare_expr (def);
3427
          remove_phi_node (&psi, false);
3428
 
3429
          def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
3430
                                          true, GSI_SAME_STMT);
3431
          ass = gimple_build_assign (rslt, def);
3432
          gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
3433
        }
3434
    }
3435
  return 0;
3436
}
3437
 
3438
#include "gt-tree-scalar-evolution.h"

powered by: WebSVN 2.1.0

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