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