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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-scalar-evolution.c] - Blame information for rev 841

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

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

powered by: WebSVN 2.1.0

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