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