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