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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

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