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