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 = safe_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 /* The affine code only deals with pointer and integer types. */
1425 if (!POINTER_TYPE_P (type)
1426 && !INTEGRAL_TYPE_P (type))
1427 return chrec_dont_know;
1428
1429 /* Try harder to check if they are equal. */
1430 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1431 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1432 free_affine_expand_cache (&peeled_chrec_map);
1433 aff_combination_scale (&aff2, -1);
1434 aff_combination_add (&aff1, &aff2);
1435
1436 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1437 if "left" equals to "init + right". */
1438 if (aff_combination_zero_p (&aff1))
1439 {
1440 if (dump_file && (dump_flags & TDF_SCEV))
1441 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1442
1443 return build_polynomial_chrec (loop->num, init_cond, right);
1444 }
1445 return chrec_dont_know;
1446 }
1447
1448 /* Given a LOOP_PHI_NODE, this function determines the evolution
1449 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1450
1451 static tree
analyze_evolution_in_loop(gphi * loop_phi_node,tree init_cond)1452 analyze_evolution_in_loop (gphi *loop_phi_node,
1453 tree init_cond)
1454 {
1455 int i, n = gimple_phi_num_args (loop_phi_node);
1456 tree evolution_function = chrec_not_analyzed_yet;
1457 struct loop *loop = loop_containing_stmt (loop_phi_node);
1458 basic_block bb;
1459 static bool simplify_peeled_chrec_p = true;
1460
1461 if (dump_file && (dump_flags & TDF_SCEV))
1462 {
1463 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1464 fprintf (dump_file, " (loop_phi_node = ");
1465 print_gimple_stmt (dump_file, loop_phi_node, 0);
1466 fprintf (dump_file, ")\n");
1467 }
1468
1469 for (i = 0; i < n; i++)
1470 {
1471 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1472 gimple *ssa_chain;
1473 tree ev_fn;
1474 t_bool res;
1475
1476 /* Select the edges that enter the loop body. */
1477 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1478 if (!flow_bb_inside_loop_p (loop, bb))
1479 continue;
1480
1481 if (TREE_CODE (arg) == SSA_NAME)
1482 {
1483 bool val = false;
1484
1485 ssa_chain = SSA_NAME_DEF_STMT (arg);
1486
1487 /* Pass in the initial condition to the follow edge function. */
1488 ev_fn = init_cond;
1489 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1490
1491 /* If ev_fn has no evolution in the inner loop, and the
1492 init_cond is not equal to ev_fn, then we have an
1493 ambiguity between two possible values, as we cannot know
1494 the number of iterations at this point. */
1495 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1496 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1497 && !operand_equal_p (init_cond, ev_fn, 0))
1498 ev_fn = chrec_dont_know;
1499 }
1500 else
1501 res = t_false;
1502
1503 /* When it is impossible to go back on the same
1504 loop_phi_node by following the ssa edges, the
1505 evolution is represented by a peeled chrec, i.e. the
1506 first iteration, EV_FN has the value INIT_COND, then
1507 all the other iterations it has the value of ARG.
1508 For the moment, PEELED_CHREC nodes are not built. */
1509 if (res != t_true)
1510 {
1511 ev_fn = chrec_dont_know;
1512 /* Try to recognize POLYNOMIAL_CHREC which appears in
1513 the form of PEELED_CHREC, but guard the process with
1514 a bool variable to keep the analyzer from infinite
1515 recurrence for real PEELED_RECs. */
1516 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1517 {
1518 simplify_peeled_chrec_p = false;
1519 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1520 simplify_peeled_chrec_p = true;
1521 }
1522 }
1523
1524 /* When there are multiple back edges of the loop (which in fact never
1525 happens currently, but nevertheless), merge their evolutions. */
1526 evolution_function = chrec_merge (evolution_function, ev_fn);
1527
1528 if (evolution_function == chrec_dont_know)
1529 break;
1530 }
1531
1532 if (dump_file && (dump_flags & TDF_SCEV))
1533 {
1534 fprintf (dump_file, " (evolution_function = ");
1535 print_generic_expr (dump_file, evolution_function);
1536 fprintf (dump_file, "))\n");
1537 }
1538
1539 return evolution_function;
1540 }
1541
1542 /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1543 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1544
1545 static tree
follow_copies_to_constant(tree var)1546 follow_copies_to_constant (tree var)
1547 {
1548 tree res = var;
1549 while (TREE_CODE (res) == SSA_NAME
1550 /* We face not updated SSA form in multiple places and this walk
1551 may end up in sibling loops so we have to guard it. */
1552 && !name_registered_for_update_p (res))
1553 {
1554 gimple *def = SSA_NAME_DEF_STMT (res);
1555 if (gphi *phi = dyn_cast <gphi *> (def))
1556 {
1557 if (tree rhs = degenerate_phi_result (phi))
1558 res = rhs;
1559 else
1560 break;
1561 }
1562 else if (gimple_assign_single_p (def))
1563 /* Will exit loop if not an SSA_NAME. */
1564 res = gimple_assign_rhs1 (def);
1565 else
1566 break;
1567 }
1568 if (CONSTANT_CLASS_P (res))
1569 return res;
1570 return var;
1571 }
1572
1573 /* Given a loop-phi-node, return the initial conditions of the
1574 variable on entry of the loop. When the CCP has propagated
1575 constants into the loop-phi-node, the initial condition is
1576 instantiated, otherwise the initial condition is kept symbolic.
1577 This analyzer does not analyze the evolution outside the current
1578 loop, and leaves this task to the on-demand tree reconstructor. */
1579
1580 static tree
analyze_initial_condition(gphi * loop_phi_node)1581 analyze_initial_condition (gphi *loop_phi_node)
1582 {
1583 int i, n;
1584 tree init_cond = chrec_not_analyzed_yet;
1585 struct loop *loop = loop_containing_stmt (loop_phi_node);
1586
1587 if (dump_file && (dump_flags & TDF_SCEV))
1588 {
1589 fprintf (dump_file, "(analyze_initial_condition \n");
1590 fprintf (dump_file, " (loop_phi_node = \n");
1591 print_gimple_stmt (dump_file, loop_phi_node, 0);
1592 fprintf (dump_file, ")\n");
1593 }
1594
1595 n = gimple_phi_num_args (loop_phi_node);
1596 for (i = 0; i < n; i++)
1597 {
1598 tree branch = PHI_ARG_DEF (loop_phi_node, i);
1599 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1600
1601 /* When the branch is oriented to the loop's body, it does
1602 not contribute to the initial condition. */
1603 if (flow_bb_inside_loop_p (loop, bb))
1604 continue;
1605
1606 if (init_cond == chrec_not_analyzed_yet)
1607 {
1608 init_cond = branch;
1609 continue;
1610 }
1611
1612 if (TREE_CODE (branch) == SSA_NAME)
1613 {
1614 init_cond = chrec_dont_know;
1615 break;
1616 }
1617
1618 init_cond = chrec_merge (init_cond, branch);
1619 }
1620
1621 /* Ooops -- a loop without an entry??? */
1622 if (init_cond == chrec_not_analyzed_yet)
1623 init_cond = chrec_dont_know;
1624
1625 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1626 to not miss important early loop unrollings. */
1627 init_cond = follow_copies_to_constant (init_cond);
1628
1629 if (dump_file && (dump_flags & TDF_SCEV))
1630 {
1631 fprintf (dump_file, " (init_cond = ");
1632 print_generic_expr (dump_file, init_cond);
1633 fprintf (dump_file, "))\n");
1634 }
1635
1636 return init_cond;
1637 }
1638
1639 /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1640
1641 static tree
interpret_loop_phi(struct loop * loop,gphi * loop_phi_node)1642 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1643 {
1644 tree res;
1645 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1646 tree init_cond;
1647
1648 gcc_assert (phi_loop == loop);
1649
1650 /* Otherwise really interpret the loop phi. */
1651 init_cond = analyze_initial_condition (loop_phi_node);
1652 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1653
1654 /* Verify we maintained the correct initial condition throughout
1655 possible conversions in the SSA chain. */
1656 if (res != chrec_dont_know)
1657 {
1658 tree new_init = res;
1659 if (CONVERT_EXPR_P (res)
1660 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1661 new_init = fold_convert (TREE_TYPE (res),
1662 CHREC_LEFT (TREE_OPERAND (res, 0)));
1663 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1664 new_init = CHREC_LEFT (res);
1665 STRIP_USELESS_TYPE_CONVERSION (new_init);
1666 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1667 || !operand_equal_p (init_cond, new_init, 0))
1668 return chrec_dont_know;
1669 }
1670
1671 return res;
1672 }
1673
1674 /* This function merges the branches of a condition-phi-node,
1675 contained in the outermost loop, and whose arguments are already
1676 analyzed. */
1677
1678 static tree
interpret_condition_phi(struct loop * loop,gphi * condition_phi)1679 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1680 {
1681 int i, n = gimple_phi_num_args (condition_phi);
1682 tree res = chrec_not_analyzed_yet;
1683
1684 for (i = 0; i < n; i++)
1685 {
1686 tree branch_chrec;
1687
1688 if (backedge_phi_arg_p (condition_phi, i))
1689 {
1690 res = chrec_dont_know;
1691 break;
1692 }
1693
1694 branch_chrec = analyze_scalar_evolution
1695 (loop, PHI_ARG_DEF (condition_phi, i));
1696
1697 res = chrec_merge (res, branch_chrec);
1698 if (res == chrec_dont_know)
1699 break;
1700 }
1701
1702 return res;
1703 }
1704
1705 /* Interpret the operation RHS1 OP RHS2. If we didn't
1706 analyze this node before, follow the definitions until ending
1707 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1708 return path, this function propagates evolutions (ala constant copy
1709 propagation). OPND1 is not a GIMPLE expression because we could
1710 analyze the effect of an inner loop: see interpret_loop_phi. */
1711
1712 static tree
interpret_rhs_expr(struct loop * loop,gimple * at_stmt,tree type,tree rhs1,enum tree_code code,tree rhs2)1713 interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
1714 tree type, tree rhs1, enum tree_code code, tree rhs2)
1715 {
1716 tree res, chrec1, chrec2, ctype;
1717 gimple *def;
1718
1719 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1720 {
1721 if (is_gimple_min_invariant (rhs1))
1722 return chrec_convert (type, rhs1, at_stmt);
1723
1724 if (code == SSA_NAME)
1725 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1726 at_stmt);
1727
1728 if (code == ASSERT_EXPR)
1729 {
1730 rhs1 = ASSERT_EXPR_VAR (rhs1);
1731 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1732 at_stmt);
1733 }
1734 }
1735
1736 switch (code)
1737 {
1738 case ADDR_EXPR:
1739 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1740 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1741 {
1742 machine_mode mode;
1743 poly_int64 bitsize, bitpos;
1744 int unsignedp, reversep;
1745 int volatilep = 0;
1746 tree base, offset;
1747 tree chrec3;
1748 tree unitpos;
1749
1750 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1751 &bitsize, &bitpos, &offset, &mode,
1752 &unsignedp, &reversep, &volatilep);
1753
1754 if (TREE_CODE (base) == MEM_REF)
1755 {
1756 rhs2 = TREE_OPERAND (base, 1);
1757 rhs1 = TREE_OPERAND (base, 0);
1758
1759 chrec1 = analyze_scalar_evolution (loop, rhs1);
1760 chrec2 = analyze_scalar_evolution (loop, rhs2);
1761 chrec1 = chrec_convert (type, chrec1, at_stmt);
1762 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1763 chrec1 = instantiate_parameters (loop, chrec1);
1764 chrec2 = instantiate_parameters (loop, chrec2);
1765 res = chrec_fold_plus (type, chrec1, chrec2);
1766 }
1767 else
1768 {
1769 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1770 chrec1 = chrec_convert (type, chrec1, at_stmt);
1771 res = chrec1;
1772 }
1773
1774 if (offset != NULL_TREE)
1775 {
1776 chrec2 = analyze_scalar_evolution (loop, offset);
1777 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1778 chrec2 = instantiate_parameters (loop, chrec2);
1779 res = chrec_fold_plus (type, res, chrec2);
1780 }
1781
1782 if (maybe_ne (bitpos, 0))
1783 {
1784 unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
1785 chrec3 = analyze_scalar_evolution (loop, unitpos);
1786 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1787 chrec3 = instantiate_parameters (loop, chrec3);
1788 res = chrec_fold_plus (type, res, chrec3);
1789 }
1790 }
1791 else
1792 res = chrec_dont_know;
1793 break;
1794
1795 case POINTER_PLUS_EXPR:
1796 chrec1 = analyze_scalar_evolution (loop, rhs1);
1797 chrec2 = analyze_scalar_evolution (loop, rhs2);
1798 chrec1 = chrec_convert (type, chrec1, at_stmt);
1799 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1800 chrec1 = instantiate_parameters (loop, chrec1);
1801 chrec2 = instantiate_parameters (loop, chrec2);
1802 res = chrec_fold_plus (type, chrec1, chrec2);
1803 break;
1804
1805 case PLUS_EXPR:
1806 chrec1 = analyze_scalar_evolution (loop, rhs1);
1807 chrec2 = analyze_scalar_evolution (loop, rhs2);
1808 ctype = type;
1809 /* When the stmt is conditionally executed re-write the CHREC
1810 into a form that has well-defined behavior on overflow. */
1811 if (at_stmt
1812 && INTEGRAL_TYPE_P (type)
1813 && ! TYPE_OVERFLOW_WRAPS (type)
1814 && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1815 gimple_bb (at_stmt)))
1816 ctype = unsigned_type_for (type);
1817 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1818 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1819 chrec1 = instantiate_parameters (loop, chrec1);
1820 chrec2 = instantiate_parameters (loop, chrec2);
1821 res = chrec_fold_plus (ctype, chrec1, chrec2);
1822 if (type != ctype)
1823 res = chrec_convert (type, res, at_stmt);
1824 break;
1825
1826 case MINUS_EXPR:
1827 chrec1 = analyze_scalar_evolution (loop, rhs1);
1828 chrec2 = analyze_scalar_evolution (loop, rhs2);
1829 ctype = type;
1830 /* When the stmt is conditionally executed re-write the CHREC
1831 into a form that has well-defined behavior on overflow. */
1832 if (at_stmt
1833 && INTEGRAL_TYPE_P (type)
1834 && ! TYPE_OVERFLOW_WRAPS (type)
1835 && ! dominated_by_p (CDI_DOMINATORS,
1836 loop->latch, gimple_bb (at_stmt)))
1837 ctype = unsigned_type_for (type);
1838 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1839 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1840 chrec1 = instantiate_parameters (loop, chrec1);
1841 chrec2 = instantiate_parameters (loop, chrec2);
1842 res = chrec_fold_minus (ctype, chrec1, chrec2);
1843 if (type != ctype)
1844 res = chrec_convert (type, res, at_stmt);
1845 break;
1846
1847 case NEGATE_EXPR:
1848 chrec1 = analyze_scalar_evolution (loop, rhs1);
1849 ctype = type;
1850 /* When the stmt is conditionally executed re-write the CHREC
1851 into a form that has well-defined behavior on overflow. */
1852 if (at_stmt
1853 && INTEGRAL_TYPE_P (type)
1854 && ! TYPE_OVERFLOW_WRAPS (type)
1855 && ! dominated_by_p (CDI_DOMINATORS,
1856 loop->latch, gimple_bb (at_stmt)))
1857 ctype = unsigned_type_for (type);
1858 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1859 /* TYPE may be integer, real or complex, so use fold_convert. */
1860 chrec1 = instantiate_parameters (loop, chrec1);
1861 res = chrec_fold_multiply (ctype, chrec1,
1862 fold_convert (ctype, integer_minus_one_node));
1863 if (type != ctype)
1864 res = chrec_convert (type, res, at_stmt);
1865 break;
1866
1867 case BIT_NOT_EXPR:
1868 /* Handle ~X as -1 - X. */
1869 chrec1 = analyze_scalar_evolution (loop, rhs1);
1870 chrec1 = chrec_convert (type, chrec1, at_stmt);
1871 chrec1 = instantiate_parameters (loop, chrec1);
1872 res = chrec_fold_minus (type,
1873 fold_convert (type, integer_minus_one_node),
1874 chrec1);
1875 break;
1876
1877 case MULT_EXPR:
1878 chrec1 = analyze_scalar_evolution (loop, rhs1);
1879 chrec2 = analyze_scalar_evolution (loop, rhs2);
1880 ctype = type;
1881 /* When the stmt is conditionally executed re-write the CHREC
1882 into a form that has well-defined behavior on overflow. */
1883 if (at_stmt
1884 && INTEGRAL_TYPE_P (type)
1885 && ! TYPE_OVERFLOW_WRAPS (type)
1886 && ! dominated_by_p (CDI_DOMINATORS,
1887 loop->latch, gimple_bb (at_stmt)))
1888 ctype = unsigned_type_for (type);
1889 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1890 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1891 chrec1 = instantiate_parameters (loop, chrec1);
1892 chrec2 = instantiate_parameters (loop, chrec2);
1893 res = chrec_fold_multiply (ctype, chrec1, chrec2);
1894 if (type != ctype)
1895 res = chrec_convert (type, res, at_stmt);
1896 break;
1897
1898 case LSHIFT_EXPR:
1899 {
1900 /* Handle A<<B as A * (1<<B). */
1901 tree uns = unsigned_type_for (type);
1902 chrec1 = analyze_scalar_evolution (loop, rhs1);
1903 chrec2 = analyze_scalar_evolution (loop, rhs2);
1904 chrec1 = chrec_convert (uns, chrec1, at_stmt);
1905 chrec1 = instantiate_parameters (loop, chrec1);
1906 chrec2 = instantiate_parameters (loop, chrec2);
1907
1908 tree one = build_int_cst (uns, 1);
1909 chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1910 res = chrec_fold_multiply (uns, chrec1, chrec2);
1911 res = chrec_convert (type, res, at_stmt);
1912 }
1913 break;
1914
1915 CASE_CONVERT:
1916 /* In case we have a truncation of a widened operation that in
1917 the truncated type has undefined overflow behavior analyze
1918 the operation done in an unsigned type of the same precision
1919 as the final truncation. We cannot derive a scalar evolution
1920 for the widened operation but for the truncated result. */
1921 if (TREE_CODE (type) == INTEGER_TYPE
1922 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1923 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1924 && TYPE_OVERFLOW_UNDEFINED (type)
1925 && TREE_CODE (rhs1) == SSA_NAME
1926 && (def = SSA_NAME_DEF_STMT (rhs1))
1927 && is_gimple_assign (def)
1928 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1929 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1930 {
1931 tree utype = unsigned_type_for (type);
1932 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1933 gimple_assign_rhs1 (def),
1934 gimple_assign_rhs_code (def),
1935 gimple_assign_rhs2 (def));
1936 }
1937 else
1938 chrec1 = analyze_scalar_evolution (loop, rhs1);
1939 res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
1940 break;
1941
1942 case BIT_AND_EXPR:
1943 /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1944 If A is SCEV and its value is in the range of representable set
1945 of type unsigned short, the result expression is a (no-overflow)
1946 SCEV. */
1947 res = chrec_dont_know;
1948 if (tree_fits_uhwi_p (rhs2))
1949 {
1950 int precision;
1951 unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
1952
1953 val ++;
1954 /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1955 it's not the maximum value of a smaller type than rhs1. */
1956 if (val != 0
1957 && (precision = exact_log2 (val)) > 0
1958 && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
1959 {
1960 tree utype = build_nonstandard_integer_type (precision, 1);
1961
1962 if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
1963 {
1964 chrec1 = analyze_scalar_evolution (loop, rhs1);
1965 chrec1 = chrec_convert (utype, chrec1, at_stmt);
1966 res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
1967 }
1968 }
1969 }
1970 break;
1971
1972 default:
1973 res = chrec_dont_know;
1974 break;
1975 }
1976
1977 return res;
1978 }
1979
1980 /* Interpret the expression EXPR. */
1981
1982 static tree
interpret_expr(struct loop * loop,gimple * at_stmt,tree expr)1983 interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
1984 {
1985 enum tree_code code;
1986 tree type = TREE_TYPE (expr), op0, op1;
1987
1988 if (automatically_generated_chrec_p (expr))
1989 return expr;
1990
1991 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1992 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1993 return chrec_dont_know;
1994
1995 extract_ops_from_tree (expr, &code, &op0, &op1);
1996
1997 return interpret_rhs_expr (loop, at_stmt, type,
1998 op0, code, op1);
1999 }
2000
2001 /* Interpret the rhs of the assignment STMT. */
2002
2003 static tree
interpret_gimple_assign(struct loop * loop,gimple * stmt)2004 interpret_gimple_assign (struct loop *loop, gimple *stmt)
2005 {
2006 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2007 enum tree_code code = gimple_assign_rhs_code (stmt);
2008
2009 return interpret_rhs_expr (loop, stmt, type,
2010 gimple_assign_rhs1 (stmt), code,
2011 gimple_assign_rhs2 (stmt));
2012 }
2013
2014
2015
2016 /* This section contains all the entry points:
2017 - number_of_iterations_in_loop,
2018 - analyze_scalar_evolution,
2019 - instantiate_parameters.
2020 */
2021
2022 /* Helper recursive function. */
2023
2024 static tree
analyze_scalar_evolution_1(struct loop * loop,tree var)2025 analyze_scalar_evolution_1 (struct loop *loop, tree var)
2026 {
2027 gimple *def;
2028 basic_block bb;
2029 struct loop *def_loop;
2030 tree res;
2031
2032 if (TREE_CODE (var) != SSA_NAME)
2033 return interpret_expr (loop, NULL, var);
2034
2035 def = SSA_NAME_DEF_STMT (var);
2036 bb = gimple_bb (def);
2037 def_loop = bb->loop_father;
2038
2039 if (!flow_bb_inside_loop_p (loop, bb))
2040 {
2041 /* Keep symbolic form, but look through obvious copies for constants. */
2042 res = follow_copies_to_constant (var);
2043 goto set_and_end;
2044 }
2045
2046 if (loop != def_loop)
2047 {
2048 res = analyze_scalar_evolution_1 (def_loop, var);
2049 struct loop *loop_to_skip = superloop_at_depth (def_loop,
2050 loop_depth (loop) + 1);
2051 res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
2052 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
2053 res = analyze_scalar_evolution_1 (loop, res);
2054 goto set_and_end;
2055 }
2056
2057 switch (gimple_code (def))
2058 {
2059 case GIMPLE_ASSIGN:
2060 res = interpret_gimple_assign (loop, def);
2061 break;
2062
2063 case GIMPLE_PHI:
2064 if (loop_phi_node_p (def))
2065 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2066 else
2067 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2068 break;
2069
2070 default:
2071 res = chrec_dont_know;
2072 break;
2073 }
2074
2075 set_and_end:
2076
2077 /* Keep the symbolic form. */
2078 if (res == chrec_dont_know)
2079 res = var;
2080
2081 if (loop == def_loop)
2082 set_scalar_evolution (block_before_loop (loop), var, res);
2083
2084 return res;
2085 }
2086
2087 /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2088 LOOP. LOOP is the loop in which the variable is used.
2089
2090 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2091 pointer to the statement that uses this variable, in order to
2092 determine the evolution function of the variable, use the following
2093 calls:
2094
2095 loop_p loop = loop_containing_stmt (stmt);
2096 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2097 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2098 */
2099
2100 tree
analyze_scalar_evolution(struct loop * loop,tree var)2101 analyze_scalar_evolution (struct loop *loop, tree var)
2102 {
2103 tree res;
2104
2105 /* ??? Fix callers. */
2106 if (! loop)
2107 return var;
2108
2109 if (dump_file && (dump_flags & TDF_SCEV))
2110 {
2111 fprintf (dump_file, "(analyze_scalar_evolution \n");
2112 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2113 fprintf (dump_file, " (scalar = ");
2114 print_generic_expr (dump_file, var);
2115 fprintf (dump_file, ")\n");
2116 }
2117
2118 res = get_scalar_evolution (block_before_loop (loop), var);
2119 if (res == chrec_not_analyzed_yet)
2120 res = analyze_scalar_evolution_1 (loop, var);
2121
2122 if (dump_file && (dump_flags & TDF_SCEV))
2123 fprintf (dump_file, ")\n");
2124
2125 return res;
2126 }
2127
2128 /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2129
2130 static tree
analyze_scalar_evolution_for_address_of(struct loop * loop,tree var)2131 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2132 {
2133 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2134 }
2135
2136 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2137 WRTO_LOOP (which should be a superloop of USE_LOOP)
2138
2139 FOLDED_CASTS is set to true if resolve_mixers used
2140 chrec_convert_aggressive (TODO -- not really, we are way too conservative
2141 at the moment in order to keep things simple).
2142
2143 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2144 example:
2145
2146 for (i = 0; i < 100; i++) -- loop 1
2147 {
2148 for (j = 0; j < 100; j++) -- loop 2
2149 {
2150 k1 = i;
2151 k2 = j;
2152
2153 use2 (k1, k2);
2154
2155 for (t = 0; t < 100; t++) -- loop 3
2156 use3 (k1, k2);
2157
2158 }
2159 use1 (k1, k2);
2160 }
2161
2162 Both k1 and k2 are invariants in loop3, thus
2163 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2164 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2165
2166 As they are invariant, it does not matter whether we consider their
2167 usage in loop 3 or loop 2, hence
2168 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2169 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2170 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2171 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2172
2173 Similarly for their evolutions with respect to loop 1. The values of K2
2174 in the use in loop 2 vary independently on loop 1, thus we cannot express
2175 the evolution with respect to loop 1:
2176 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2177 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2178 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2179 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2180
2181 The value of k2 in the use in loop 1 is known, though:
2182 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2183 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2184 */
2185
2186 static tree
analyze_scalar_evolution_in_loop(struct loop * wrto_loop,struct loop * use_loop,tree version,bool * folded_casts)2187 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2188 tree version, bool *folded_casts)
2189 {
2190 bool val = false;
2191 tree ev = version, tmp;
2192
2193 /* We cannot just do
2194
2195 tmp = analyze_scalar_evolution (use_loop, version);
2196 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2197
2198 as resolve_mixers would query the scalar evolution with respect to
2199 wrto_loop. For example, in the situation described in the function
2200 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2201 version = k2. Then
2202
2203 analyze_scalar_evolution (use_loop, version) = k2
2204
2205 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2206 k2 in loop 1 is 100, which is a wrong result, since we are interested
2207 in the value in loop 3.
2208
2209 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2210 each time checking that there is no evolution in the inner loop. */
2211
2212 if (folded_casts)
2213 *folded_casts = false;
2214 while (1)
2215 {
2216 tmp = analyze_scalar_evolution (use_loop, ev);
2217 ev = resolve_mixers (use_loop, tmp, folded_casts);
2218
2219 if (use_loop == wrto_loop)
2220 return ev;
2221
2222 /* If the value of the use changes in the inner loop, we cannot express
2223 its value in the outer loop (we might try to return interval chrec,
2224 but we do not have a user for it anyway) */
2225 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2226 || !val)
2227 return chrec_dont_know;
2228
2229 use_loop = loop_outer (use_loop);
2230 }
2231 }
2232
2233
2234 /* Hashtable helpers for a temporary hash-table used when
2235 instantiating a CHREC or resolving mixers. For this use
2236 instantiated_below is always the same. */
2237
2238 struct instantiate_cache_type
2239 {
2240 htab_t map;
2241 vec<scev_info_str> entries;
2242
instantiate_cache_typeinstantiate_cache_type2243 instantiate_cache_type () : map (NULL), entries (vNULL) {}
2244 ~instantiate_cache_type ();
getinstantiate_cache_type2245 tree get (unsigned slot) { return entries[slot].chrec; }
setinstantiate_cache_type2246 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
2247 };
2248
~instantiate_cache_type()2249 instantiate_cache_type::~instantiate_cache_type ()
2250 {
2251 if (map != NULL)
2252 {
2253 htab_delete (map);
2254 entries.release ();
2255 }
2256 }
2257
2258 /* Cache to avoid infinite recursion when instantiating an SSA name.
2259 Live during the outermost instantiate_scev or resolve_mixers call. */
2260 static instantiate_cache_type *global_cache;
2261
2262 /* Computes a hash function for database element ELT. */
2263
2264 static inline hashval_t
hash_idx_scev_info(const void * elt_)2265 hash_idx_scev_info (const void *elt_)
2266 {
2267 unsigned idx = ((size_t) elt_) - 2;
2268 return scev_info_hasher::hash (&global_cache->entries[idx]);
2269 }
2270
2271 /* Compares database elements E1 and E2. */
2272
2273 static inline int
eq_idx_scev_info(const void * e1,const void * e2)2274 eq_idx_scev_info (const void *e1, const void *e2)
2275 {
2276 unsigned idx1 = ((size_t) e1) - 2;
2277 return scev_info_hasher::equal (&global_cache->entries[idx1],
2278 (const scev_info_str *) e2);
2279 }
2280
2281 /* Returns from CACHE the slot number of the cached chrec for NAME. */
2282
2283 static unsigned
get_instantiated_value_entry(instantiate_cache_type & cache,tree name,edge instantiate_below)2284 get_instantiated_value_entry (instantiate_cache_type &cache,
2285 tree name, edge instantiate_below)
2286 {
2287 if (!cache.map)
2288 {
2289 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2290 cache.entries.create (10);
2291 }
2292
2293 scev_info_str e;
2294 e.name_version = SSA_NAME_VERSION (name);
2295 e.instantiated_below = instantiate_below->dest->index;
2296 void **slot = htab_find_slot_with_hash (cache.map, &e,
2297 scev_info_hasher::hash (&e), INSERT);
2298 if (!*slot)
2299 {
2300 e.chrec = chrec_not_analyzed_yet;
2301 *slot = (void *)(size_t)(cache.entries.length () + 2);
2302 cache.entries.safe_push (e);
2303 }
2304
2305 return ((size_t)*slot) - 2;
2306 }
2307
2308
2309 /* Return the closed_loop_phi node for VAR. If there is none, return
2310 NULL_TREE. */
2311
2312 static tree
loop_closed_phi_def(tree var)2313 loop_closed_phi_def (tree var)
2314 {
2315 struct loop *loop;
2316 edge exit;
2317 gphi *phi;
2318 gphi_iterator psi;
2319
2320 if (var == NULL_TREE
2321 || TREE_CODE (var) != SSA_NAME)
2322 return NULL_TREE;
2323
2324 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2325 exit = single_exit (loop);
2326 if (!exit)
2327 return NULL_TREE;
2328
2329 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2330 {
2331 phi = psi.phi ();
2332 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2333 return PHI_RESULT (phi);
2334 }
2335
2336 return NULL_TREE;
2337 }
2338
2339 static tree instantiate_scev_r (edge, struct loop *, struct loop *,
2340 tree, bool *, int);
2341
2342 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2343 and EVOLUTION_LOOP, that were left under a symbolic form.
2344
2345 CHREC is an SSA_NAME to be instantiated.
2346
2347 CACHE is the cache of already instantiated values.
2348
2349 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2350 conversions that may wrap in signed/pointer type are folded, as long
2351 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2352 then we don't do such fold.
2353
2354 SIZE_EXPR is used for computing the size of the expression to be
2355 instantiated, and to stop if it exceeds some limit. */
2356
2357 static tree
instantiate_scev_name(edge instantiate_below,struct loop * evolution_loop,struct loop * inner_loop,tree chrec,bool * fold_conversions,int size_expr)2358 instantiate_scev_name (edge instantiate_below,
2359 struct loop *evolution_loop, struct loop *inner_loop,
2360 tree chrec,
2361 bool *fold_conversions,
2362 int size_expr)
2363 {
2364 tree res;
2365 struct loop *def_loop;
2366 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2367
2368 /* A parameter, nothing to do. */
2369 if (!def_bb
2370 || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
2371 return chrec;
2372
2373 /* We cache the value of instantiated variable to avoid exponential
2374 time complexity due to reevaluations. We also store the convenient
2375 value in the cache in order to prevent infinite recursion -- we do
2376 not want to instantiate the SSA_NAME if it is in a mixer
2377 structure. This is used for avoiding the instantiation of
2378 recursively defined functions, such as:
2379
2380 | a_2 -> {0, +, 1, +, a_2}_1 */
2381
2382 unsigned si = get_instantiated_value_entry (*global_cache,
2383 chrec, instantiate_below);
2384 if (global_cache->get (si) != chrec_not_analyzed_yet)
2385 return global_cache->get (si);
2386
2387 /* On recursion return chrec_dont_know. */
2388 global_cache->set (si, chrec_dont_know);
2389
2390 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2391
2392 if (! dominated_by_p (CDI_DOMINATORS,
2393 def_loop->header, instantiate_below->dest))
2394 {
2395 gimple *def = SSA_NAME_DEF_STMT (chrec);
2396 if (gassign *ass = dyn_cast <gassign *> (def))
2397 {
2398 switch (gimple_assign_rhs_class (ass))
2399 {
2400 case GIMPLE_UNARY_RHS:
2401 {
2402 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2403 inner_loop, gimple_assign_rhs1 (ass),
2404 fold_conversions, size_expr);
2405 if (op0 == chrec_dont_know)
2406 return chrec_dont_know;
2407 res = fold_build1 (gimple_assign_rhs_code (ass),
2408 TREE_TYPE (chrec), op0);
2409 break;
2410 }
2411 case GIMPLE_BINARY_RHS:
2412 {
2413 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2414 inner_loop, gimple_assign_rhs1 (ass),
2415 fold_conversions, size_expr);
2416 if (op0 == chrec_dont_know)
2417 return chrec_dont_know;
2418 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2419 inner_loop, gimple_assign_rhs2 (ass),
2420 fold_conversions, size_expr);
2421 if (op1 == chrec_dont_know)
2422 return chrec_dont_know;
2423 res = fold_build2 (gimple_assign_rhs_code (ass),
2424 TREE_TYPE (chrec), op0, op1);
2425 break;
2426 }
2427 default:
2428 res = chrec_dont_know;
2429 }
2430 }
2431 else
2432 res = chrec_dont_know;
2433 global_cache->set (si, res);
2434 return res;
2435 }
2436
2437 /* If the analysis yields a parametric chrec, instantiate the
2438 result again. */
2439 res = analyze_scalar_evolution (def_loop, chrec);
2440
2441 /* Don't instantiate default definitions. */
2442 if (TREE_CODE (res) == SSA_NAME
2443 && SSA_NAME_IS_DEFAULT_DEF (res))
2444 ;
2445
2446 /* Don't instantiate loop-closed-ssa phi nodes. */
2447 else if (TREE_CODE (res) == SSA_NAME
2448 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2449 > loop_depth (def_loop))
2450 {
2451 if (res == chrec)
2452 res = loop_closed_phi_def (chrec);
2453 else
2454 res = chrec;
2455
2456 /* When there is no loop_closed_phi_def, it means that the
2457 variable is not used after the loop: try to still compute the
2458 value of the variable when exiting the loop. */
2459 if (res == NULL_TREE)
2460 {
2461 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2462 res = analyze_scalar_evolution (loop, chrec);
2463 res = compute_overall_effect_of_inner_loop (loop, res);
2464 res = instantiate_scev_r (instantiate_below, evolution_loop,
2465 inner_loop, res,
2466 fold_conversions, size_expr);
2467 }
2468 else if (dominated_by_p (CDI_DOMINATORS,
2469 gimple_bb (SSA_NAME_DEF_STMT (res)),
2470 instantiate_below->dest))
2471 res = chrec_dont_know;
2472 }
2473
2474 else if (res != chrec_dont_know)
2475 {
2476 if (inner_loop
2477 && def_bb->loop_father != inner_loop
2478 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2479 /* ??? We could try to compute the overall effect of the loop here. */
2480 res = chrec_dont_know;
2481 else
2482 res = instantiate_scev_r (instantiate_below, evolution_loop,
2483 inner_loop, res,
2484 fold_conversions, size_expr);
2485 }
2486
2487 /* Store the correct value to the cache. */
2488 global_cache->set (si, res);
2489 return res;
2490 }
2491
2492 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2493 and EVOLUTION_LOOP, that were left under a symbolic form.
2494
2495 CHREC is a polynomial chain of recurrence to be instantiated.
2496
2497 CACHE is the cache of already instantiated values.
2498
2499 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2500 conversions that may wrap in signed/pointer type are folded, as long
2501 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2502 then we don't do such fold.
2503
2504 SIZE_EXPR is used for computing the size of the expression to be
2505 instantiated, and to stop if it exceeds some limit. */
2506
2507 static tree
instantiate_scev_poly(edge instantiate_below,struct loop * evolution_loop,struct loop *,tree chrec,bool * fold_conversions,int size_expr)2508 instantiate_scev_poly (edge instantiate_below,
2509 struct loop *evolution_loop, struct loop *,
2510 tree chrec, bool *fold_conversions, int size_expr)
2511 {
2512 tree op1;
2513 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2514 get_chrec_loop (chrec),
2515 CHREC_LEFT (chrec), fold_conversions,
2516 size_expr);
2517 if (op0 == chrec_dont_know)
2518 return chrec_dont_know;
2519
2520 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2521 get_chrec_loop (chrec),
2522 CHREC_RIGHT (chrec), fold_conversions,
2523 size_expr);
2524 if (op1 == chrec_dont_know)
2525 return chrec_dont_know;
2526
2527 if (CHREC_LEFT (chrec) != op0
2528 || CHREC_RIGHT (chrec) != op1)
2529 {
2530 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2531 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2532 }
2533
2534 return chrec;
2535 }
2536
2537 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2538 and EVOLUTION_LOOP, that were left under a symbolic form.
2539
2540 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2541
2542 CACHE is the cache of already instantiated values.
2543
2544 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2545 conversions that may wrap in signed/pointer type are folded, as long
2546 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2547 then we don't do such fold.
2548
2549 SIZE_EXPR is used for computing the size of the expression to be
2550 instantiated, and to stop if it exceeds some limit. */
2551
2552 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)2553 instantiate_scev_binary (edge instantiate_below,
2554 struct loop *evolution_loop, struct loop *inner_loop,
2555 tree chrec, enum tree_code code,
2556 tree type, tree c0, tree c1,
2557 bool *fold_conversions, int size_expr)
2558 {
2559 tree op1;
2560 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2561 c0, fold_conversions, size_expr);
2562 if (op0 == chrec_dont_know)
2563 return chrec_dont_know;
2564
2565 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2566 c1, fold_conversions, size_expr);
2567 if (op1 == chrec_dont_know)
2568 return chrec_dont_know;
2569
2570 if (c0 != op0
2571 || c1 != op1)
2572 {
2573 op0 = chrec_convert (type, op0, NULL);
2574 op1 = chrec_convert_rhs (type, op1, NULL);
2575
2576 switch (code)
2577 {
2578 case POINTER_PLUS_EXPR:
2579 case PLUS_EXPR:
2580 return chrec_fold_plus (type, op0, op1);
2581
2582 case MINUS_EXPR:
2583 return chrec_fold_minus (type, op0, op1);
2584
2585 case MULT_EXPR:
2586 return chrec_fold_multiply (type, op0, op1);
2587
2588 default:
2589 gcc_unreachable ();
2590 }
2591 }
2592
2593 return chrec ? chrec : fold_build2 (code, type, c0, c1);
2594 }
2595
2596 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2597 and EVOLUTION_LOOP, that were left under a symbolic form.
2598
2599 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2600 instantiated.
2601
2602 CACHE is the cache of already instantiated values.
2603
2604 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2605 conversions that may wrap in signed/pointer type are folded, as long
2606 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2607 then we don't do such fold.
2608
2609 SIZE_EXPR is used for computing the size of the expression to be
2610 instantiated, and to stop if it exceeds some limit. */
2611
2612 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)2613 instantiate_scev_convert (edge instantiate_below,
2614 struct loop *evolution_loop, struct loop *inner_loop,
2615 tree chrec, tree type, tree op,
2616 bool *fold_conversions, int size_expr)
2617 {
2618 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2619 inner_loop, op,
2620 fold_conversions, size_expr);
2621
2622 if (op0 == chrec_dont_know)
2623 return chrec_dont_know;
2624
2625 if (fold_conversions)
2626 {
2627 tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2628 if (tmp)
2629 return tmp;
2630
2631 /* If we used chrec_convert_aggressive, we can no longer assume that
2632 signed chrecs do not overflow, as chrec_convert does, so avoid
2633 calling it in that case. */
2634 if (*fold_conversions)
2635 {
2636 if (chrec && op0 == op)
2637 return chrec;
2638
2639 return fold_convert (type, op0);
2640 }
2641 }
2642
2643 return chrec_convert (type, op0, NULL);
2644 }
2645
2646 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2647 and EVOLUTION_LOOP, that were left under a symbolic form.
2648
2649 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2650 Handle ~X as -1 - X.
2651 Handle -X as -1 * X.
2652
2653 CACHE is the cache of already instantiated values.
2654
2655 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2656 conversions that may wrap in signed/pointer type are folded, as long
2657 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2658 then we don't do such fold.
2659
2660 SIZE_EXPR is used for computing the size of the expression to be
2661 instantiated, and to stop if it exceeds some limit. */
2662
2663 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)2664 instantiate_scev_not (edge instantiate_below,
2665 struct loop *evolution_loop, struct loop *inner_loop,
2666 tree chrec,
2667 enum tree_code code, tree type, tree op,
2668 bool *fold_conversions, int size_expr)
2669 {
2670 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2671 inner_loop, op,
2672 fold_conversions, size_expr);
2673
2674 if (op0 == chrec_dont_know)
2675 return chrec_dont_know;
2676
2677 if (op != op0)
2678 {
2679 op0 = chrec_convert (type, op0, NULL);
2680
2681 switch (code)
2682 {
2683 case BIT_NOT_EXPR:
2684 return chrec_fold_minus
2685 (type, fold_convert (type, integer_minus_one_node), op0);
2686
2687 case NEGATE_EXPR:
2688 return chrec_fold_multiply
2689 (type, fold_convert (type, integer_minus_one_node), op0);
2690
2691 default:
2692 gcc_unreachable ();
2693 }
2694 }
2695
2696 return chrec ? chrec : fold_build1 (code, type, op0);
2697 }
2698
2699 /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2700 and EVOLUTION_LOOP, that were left under a symbolic form.
2701
2702 CHREC is the scalar evolution to instantiate.
2703
2704 CACHE is the cache of already instantiated values.
2705
2706 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2707 conversions that may wrap in signed/pointer type are folded, as long
2708 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2709 then we don't do such fold.
2710
2711 SIZE_EXPR is used for computing the size of the expression to be
2712 instantiated, and to stop if it exceeds some limit. */
2713
2714 static tree
instantiate_scev_r(edge instantiate_below,struct loop * evolution_loop,struct loop * inner_loop,tree chrec,bool * fold_conversions,int size_expr)2715 instantiate_scev_r (edge instantiate_below,
2716 struct loop *evolution_loop, struct loop *inner_loop,
2717 tree chrec,
2718 bool *fold_conversions, int size_expr)
2719 {
2720 /* Give up if the expression is larger than the MAX that we allow. */
2721 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2722 return chrec_dont_know;
2723
2724 if (chrec == NULL_TREE
2725 || automatically_generated_chrec_p (chrec)
2726 || is_gimple_min_invariant (chrec))
2727 return chrec;
2728
2729 switch (TREE_CODE (chrec))
2730 {
2731 case SSA_NAME:
2732 return instantiate_scev_name (instantiate_below, evolution_loop,
2733 inner_loop, chrec,
2734 fold_conversions, size_expr);
2735
2736 case POLYNOMIAL_CHREC:
2737 return instantiate_scev_poly (instantiate_below, evolution_loop,
2738 inner_loop, chrec,
2739 fold_conversions, size_expr);
2740
2741 case POINTER_PLUS_EXPR:
2742 case PLUS_EXPR:
2743 case MINUS_EXPR:
2744 case MULT_EXPR:
2745 return instantiate_scev_binary (instantiate_below, evolution_loop,
2746 inner_loop, chrec,
2747 TREE_CODE (chrec), chrec_type (chrec),
2748 TREE_OPERAND (chrec, 0),
2749 TREE_OPERAND (chrec, 1),
2750 fold_conversions, size_expr);
2751
2752 CASE_CONVERT:
2753 return instantiate_scev_convert (instantiate_below, evolution_loop,
2754 inner_loop, chrec,
2755 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2756 fold_conversions, size_expr);
2757
2758 case NEGATE_EXPR:
2759 case BIT_NOT_EXPR:
2760 return instantiate_scev_not (instantiate_below, evolution_loop,
2761 inner_loop, chrec,
2762 TREE_CODE (chrec), TREE_TYPE (chrec),
2763 TREE_OPERAND (chrec, 0),
2764 fold_conversions, size_expr);
2765
2766 case ADDR_EXPR:
2767 if (is_gimple_min_invariant (chrec))
2768 return chrec;
2769 /* Fallthru. */
2770 case SCEV_NOT_KNOWN:
2771 return chrec_dont_know;
2772
2773 case SCEV_KNOWN:
2774 return chrec_known;
2775
2776 default:
2777 if (CONSTANT_CLASS_P (chrec))
2778 return chrec;
2779 return chrec_dont_know;
2780 }
2781 }
2782
2783 /* Analyze all the parameters of the chrec that were left under a
2784 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2785 recursive instantiation of parameters: a parameter is a variable
2786 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2787 a function parameter. */
2788
2789 tree
instantiate_scev(edge instantiate_below,struct loop * evolution_loop,tree chrec)2790 instantiate_scev (edge instantiate_below, struct loop *evolution_loop,
2791 tree chrec)
2792 {
2793 tree res;
2794
2795 if (dump_file && (dump_flags & TDF_SCEV))
2796 {
2797 fprintf (dump_file, "(instantiate_scev \n");
2798 fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
2799 instantiate_below->src->index, instantiate_below->dest->index);
2800 if (evolution_loop)
2801 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2802 fprintf (dump_file, " (chrec = ");
2803 print_generic_expr (dump_file, chrec);
2804 fprintf (dump_file, ")\n");
2805 }
2806
2807 bool destr = false;
2808 if (!global_cache)
2809 {
2810 global_cache = new instantiate_cache_type;
2811 destr = true;
2812 }
2813
2814 res = instantiate_scev_r (instantiate_below, evolution_loop,
2815 NULL, chrec, NULL, 0);
2816
2817 if (destr)
2818 {
2819 delete global_cache;
2820 global_cache = NULL;
2821 }
2822
2823 if (dump_file && (dump_flags & TDF_SCEV))
2824 {
2825 fprintf (dump_file, " (res = ");
2826 print_generic_expr (dump_file, res);
2827 fprintf (dump_file, "))\n");
2828 }
2829
2830 return res;
2831 }
2832
2833 /* Similar to instantiate_parameters, but does not introduce the
2834 evolutions in outer loops for LOOP invariants in CHREC, and does not
2835 care about causing overflows, as long as they do not affect value
2836 of an expression. */
2837
2838 tree
resolve_mixers(struct loop * loop,tree chrec,bool * folded_casts)2839 resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
2840 {
2841 bool destr = false;
2842 bool fold_conversions = false;
2843 if (!global_cache)
2844 {
2845 global_cache = new instantiate_cache_type;
2846 destr = true;
2847 }
2848
2849 tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
2850 chrec, &fold_conversions, 0);
2851
2852 if (folded_casts && !*folded_casts)
2853 *folded_casts = fold_conversions;
2854
2855 if (destr)
2856 {
2857 delete global_cache;
2858 global_cache = NULL;
2859 }
2860
2861 return ret;
2862 }
2863
2864 /* Entry point for the analysis of the number of iterations pass.
2865 This function tries to safely approximate the number of iterations
2866 the loop will run. When this property is not decidable at compile
2867 time, the result is chrec_dont_know. Otherwise the result is a
2868 scalar or a symbolic parameter. When the number of iterations may
2869 be equal to zero and the property cannot be determined at compile
2870 time, the result is a COND_EXPR that represents in a symbolic form
2871 the conditions under which the number of iterations is not zero.
2872
2873 Example of analysis: suppose that the loop has an exit condition:
2874
2875 "if (b > 49) goto end_loop;"
2876
2877 and that in a previous analysis we have determined that the
2878 variable 'b' has an evolution function:
2879
2880 "EF = {23, +, 5}_2".
2881
2882 When we evaluate the function at the point 5, i.e. the value of the
2883 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2884 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2885 the loop body has been executed 6 times. */
2886
2887 tree
number_of_latch_executions(struct loop * loop)2888 number_of_latch_executions (struct loop *loop)
2889 {
2890 edge exit;
2891 struct tree_niter_desc niter_desc;
2892 tree may_be_zero;
2893 tree res;
2894
2895 /* Determine whether the number of iterations in loop has already
2896 been computed. */
2897 res = loop->nb_iterations;
2898 if (res)
2899 return res;
2900
2901 may_be_zero = NULL_TREE;
2902
2903 if (dump_file && (dump_flags & TDF_SCEV))
2904 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2905
2906 res = chrec_dont_know;
2907 exit = single_exit (loop);
2908
2909 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2910 {
2911 may_be_zero = niter_desc.may_be_zero;
2912 res = niter_desc.niter;
2913 }
2914
2915 if (res == chrec_dont_know
2916 || !may_be_zero
2917 || integer_zerop (may_be_zero))
2918 ;
2919 else if (integer_nonzerop (may_be_zero))
2920 res = build_int_cst (TREE_TYPE (res), 0);
2921
2922 else if (COMPARISON_CLASS_P (may_be_zero))
2923 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2924 build_int_cst (TREE_TYPE (res), 0), res);
2925 else
2926 res = chrec_dont_know;
2927
2928 if (dump_file && (dump_flags & TDF_SCEV))
2929 {
2930 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2931 print_generic_expr (dump_file, res);
2932 fprintf (dump_file, "))\n");
2933 }
2934
2935 loop->nb_iterations = res;
2936 return res;
2937 }
2938
2939
2940 /* Counters for the stats. */
2941
2942 struct chrec_stats
2943 {
2944 unsigned nb_chrecs;
2945 unsigned nb_affine;
2946 unsigned nb_affine_multivar;
2947 unsigned nb_higher_poly;
2948 unsigned nb_chrec_dont_know;
2949 unsigned nb_undetermined;
2950 };
2951
2952 /* Reset the counters. */
2953
2954 static inline void
reset_chrecs_counters(struct chrec_stats * stats)2955 reset_chrecs_counters (struct chrec_stats *stats)
2956 {
2957 stats->nb_chrecs = 0;
2958 stats->nb_affine = 0;
2959 stats->nb_affine_multivar = 0;
2960 stats->nb_higher_poly = 0;
2961 stats->nb_chrec_dont_know = 0;
2962 stats->nb_undetermined = 0;
2963 }
2964
2965 /* Dump the contents of a CHREC_STATS structure. */
2966
2967 static void
dump_chrecs_stats(FILE * file,struct chrec_stats * stats)2968 dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2969 {
2970 fprintf (file, "\n(\n");
2971 fprintf (file, "-----------------------------------------\n");
2972 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2973 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2974 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2975 stats->nb_higher_poly);
2976 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2977 fprintf (file, "-----------------------------------------\n");
2978 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2979 fprintf (file, "%d\twith undetermined coefficients\n",
2980 stats->nb_undetermined);
2981 fprintf (file, "-----------------------------------------\n");
2982 fprintf (file, "%d\tchrecs in the scev database\n",
2983 (int) scalar_evolution_info->elements ());
2984 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2985 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2986 fprintf (file, "-----------------------------------------\n");
2987 fprintf (file, ")\n\n");
2988 }
2989
2990 /* Gather statistics about CHREC. */
2991
2992 static void
gather_chrec_stats(tree chrec,struct chrec_stats * stats)2993 gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2994 {
2995 if (dump_file && (dump_flags & TDF_STATS))
2996 {
2997 fprintf (dump_file, "(classify_chrec ");
2998 print_generic_expr (dump_file, chrec);
2999 fprintf (dump_file, "\n");
3000 }
3001
3002 stats->nb_chrecs++;
3003
3004 if (chrec == NULL_TREE)
3005 {
3006 stats->nb_undetermined++;
3007 return;
3008 }
3009
3010 switch (TREE_CODE (chrec))
3011 {
3012 case POLYNOMIAL_CHREC:
3013 if (evolution_function_is_affine_p (chrec))
3014 {
3015 if (dump_file && (dump_flags & TDF_STATS))
3016 fprintf (dump_file, " affine_univariate\n");
3017 stats->nb_affine++;
3018 }
3019 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3020 {
3021 if (dump_file && (dump_flags & TDF_STATS))
3022 fprintf (dump_file, " affine_multivariate\n");
3023 stats->nb_affine_multivar++;
3024 }
3025 else
3026 {
3027 if (dump_file && (dump_flags & TDF_STATS))
3028 fprintf (dump_file, " higher_degree_polynomial\n");
3029 stats->nb_higher_poly++;
3030 }
3031
3032 break;
3033
3034 default:
3035 break;
3036 }
3037
3038 if (chrec_contains_undetermined (chrec))
3039 {
3040 if (dump_file && (dump_flags & TDF_STATS))
3041 fprintf (dump_file, " undetermined\n");
3042 stats->nb_undetermined++;
3043 }
3044
3045 if (dump_file && (dump_flags & TDF_STATS))
3046 fprintf (dump_file, ")\n");
3047 }
3048
3049 /* Classify the chrecs of the whole database. */
3050
3051 void
gather_stats_on_scev_database(void)3052 gather_stats_on_scev_database (void)
3053 {
3054 struct chrec_stats stats;
3055
3056 if (!dump_file)
3057 return;
3058
3059 reset_chrecs_counters (&stats);
3060
3061 hash_table<scev_info_hasher>::iterator iter;
3062 scev_info_str *elt;
3063 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3064 iter)
3065 gather_chrec_stats (elt->chrec, &stats);
3066
3067 dump_chrecs_stats (dump_file, &stats);
3068 }
3069
3070
3071
3072 /* Initializer. */
3073
3074 static void
initialize_scalar_evolutions_analyzer(void)3075 initialize_scalar_evolutions_analyzer (void)
3076 {
3077 /* The elements below are unique. */
3078 if (chrec_dont_know == NULL_TREE)
3079 {
3080 chrec_not_analyzed_yet = NULL_TREE;
3081 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3082 chrec_known = make_node (SCEV_KNOWN);
3083 TREE_TYPE (chrec_dont_know) = void_type_node;
3084 TREE_TYPE (chrec_known) = void_type_node;
3085 }
3086 }
3087
3088 /* Initialize the analysis of scalar evolutions for LOOPS. */
3089
3090 void
scev_initialize(void)3091 scev_initialize (void)
3092 {
3093 struct loop *loop;
3094
3095 gcc_assert (! scev_initialized_p ());
3096
3097 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3098
3099 initialize_scalar_evolutions_analyzer ();
3100
3101 FOR_EACH_LOOP (loop, 0)
3102 {
3103 loop->nb_iterations = NULL_TREE;
3104 }
3105 }
3106
3107 /* Return true if SCEV is initialized. */
3108
3109 bool
scev_initialized_p(void)3110 scev_initialized_p (void)
3111 {
3112 return scalar_evolution_info != NULL;
3113 }
3114
3115 /* Cleans up the information cached by the scalar evolutions analysis
3116 in the hash table. */
3117
3118 void
scev_reset_htab(void)3119 scev_reset_htab (void)
3120 {
3121 if (!scalar_evolution_info)
3122 return;
3123
3124 scalar_evolution_info->empty ();
3125 }
3126
3127 /* Cleans up the information cached by the scalar evolutions analysis
3128 in the hash table and in the loop->nb_iterations. */
3129
3130 void
scev_reset(void)3131 scev_reset (void)
3132 {
3133 struct loop *loop;
3134
3135 scev_reset_htab ();
3136
3137 FOR_EACH_LOOP (loop, 0)
3138 {
3139 loop->nb_iterations = NULL_TREE;
3140 }
3141 }
3142
3143 /* Return true if the IV calculation in TYPE can overflow based on the knowledge
3144 of the upper bound on the number of iterations of LOOP, the BASE and STEP
3145 of IV.
3146
3147 We do not use information whether TYPE can overflow so it is safe to
3148 use this test even for derived IVs not computed every iteration or
3149 hypotetical IVs to be inserted into code. */
3150
3151 bool
iv_can_overflow_p(struct loop * loop,tree type,tree base,tree step)3152 iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
3153 {
3154 widest_int nit;
3155 wide_int base_min, base_max, step_min, step_max, type_min, type_max;
3156 signop sgn = TYPE_SIGN (type);
3157
3158 if (integer_zerop (step))
3159 return false;
3160
3161 if (TREE_CODE (base) == INTEGER_CST)
3162 base_min = base_max = wi::to_wide (base);
3163 else if (TREE_CODE (base) == SSA_NAME
3164 && INTEGRAL_TYPE_P (TREE_TYPE (base))
3165 && get_range_info (base, &base_min, &base_max) == VR_RANGE)
3166 ;
3167 else
3168 return true;
3169
3170 if (TREE_CODE (step) == INTEGER_CST)
3171 step_min = step_max = wi::to_wide (step);
3172 else if (TREE_CODE (step) == SSA_NAME
3173 && INTEGRAL_TYPE_P (TREE_TYPE (step))
3174 && get_range_info (step, &step_min, &step_max) == VR_RANGE)
3175 ;
3176 else
3177 return true;
3178
3179 if (!get_max_loop_iterations (loop, &nit))
3180 return true;
3181
3182 type_min = wi::min_value (type);
3183 type_max = wi::max_value (type);
3184
3185 /* Just sanity check that we don't see values out of the range of the type.
3186 In this case the arithmetics bellow would overflow. */
3187 gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
3188 && wi::le_p (base_max, type_max, sgn));
3189
3190 /* Account the possible increment in the last ieration. */
3191 bool overflow = false;
3192 nit = wi::add (nit, 1, SIGNED, &overflow);
3193 if (overflow)
3194 return true;
3195
3196 /* NIT is typeless and can exceed the precision of the type. In this case
3197 overflow is always possible, because we know STEP is non-zero. */
3198 if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
3199 return true;
3200 wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
3201
3202 /* If step can be positive, check that nit*step <= type_max-base.
3203 This can be done by unsigned arithmetic and we only need to watch overflow
3204 in the multiplication. The right hand side can always be represented in
3205 the type. */
3206 if (sgn == UNSIGNED || !wi::neg_p (step_max))
3207 {
3208 bool overflow = false;
3209 if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
3210 type_max - base_max)
3211 || overflow)
3212 return true;
3213 }
3214 /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3215 if (sgn == SIGNED && wi::neg_p (step_min))
3216 {
3217 bool overflow = false, overflow2 = false;
3218 if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
3219 nit2, UNSIGNED, &overflow),
3220 base_min - type_min)
3221 || overflow || overflow2)
3222 return true;
3223 }
3224
3225 return false;
3226 }
3227
3228 /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3229 function tries to derive condition under which it can be simplified
3230 into "{(type)inner_base, (type)inner_step}_loop". The condition is
3231 the maximum number that inner iv can iterate. */
3232
3233 static tree
derive_simple_iv_with_niters(tree ev,tree * niters)3234 derive_simple_iv_with_niters (tree ev, tree *niters)
3235 {
3236 if (!CONVERT_EXPR_P (ev))
3237 return ev;
3238
3239 tree inner_ev = TREE_OPERAND (ev, 0);
3240 if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
3241 return ev;
3242
3243 tree init = CHREC_LEFT (inner_ev);
3244 tree step = CHREC_RIGHT (inner_ev);
3245 if (TREE_CODE (init) != INTEGER_CST
3246 || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3247 return ev;
3248
3249 tree type = TREE_TYPE (ev);
3250 tree inner_type = TREE_TYPE (inner_ev);
3251 if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
3252 return ev;
3253
3254 /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3255 folded only if inner iv won't overflow. We compute the maximum
3256 number the inner iv can iterate before overflowing and return the
3257 simplified affine iv. */
3258 tree delta;
3259 init = fold_convert (type, init);
3260 step = fold_convert (type, step);
3261 ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
3262 if (tree_int_cst_sign_bit (step))
3263 {
3264 tree bound = lower_bound_in_type (inner_type, inner_type);
3265 delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
3266 step = fold_build1 (NEGATE_EXPR, type, step);
3267 }
3268 else
3269 {
3270 tree bound = upper_bound_in_type (inner_type, inner_type);
3271 delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
3272 }
3273 *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
3274 return ev;
3275 }
3276
3277 /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3278 respect to WRTO_LOOP and returns its base and step in IV if possible
3279 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3280 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3281 invariant in LOOP. Otherwise we require it to be an integer constant.
3282
3283 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3284 because it is computed in signed arithmetics). Consequently, adding an
3285 induction variable
3286
3287 for (i = IV->base; ; i += IV->step)
3288
3289 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3290 false for the type of the induction variable, or you can prove that i does
3291 not wrap by some other argument. Otherwise, this might introduce undefined
3292 behavior, and
3293
3294 i = iv->base;
3295 for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3296
3297 must be used instead.
3298
3299 When IV_NITERS is not NULL, this function also checks case in which OP
3300 is a conversion of an inner simple iv of below form:
3301
3302 (outer_type){inner_base, inner_step}_loop.
3303
3304 If type of inner iv has smaller precision than outer_type, it can't be
3305 folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3306 the inner iv could overflow/wrap. In this case, we derive a condition
3307 under which the inner iv won't overflow/wrap and do the simplification.
3308 The derived condition normally is the maximum number the inner iv can
3309 iterate, and will be stored in IV_NITERS. This is useful in loop niter
3310 analysis, to derive break conditions when a loop must terminate, when is
3311 infinite. */
3312
3313 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)3314 simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop,
3315 tree op, affine_iv *iv, tree *iv_niters,
3316 bool allow_nonconstant_step)
3317 {
3318 enum tree_code code;
3319 tree type, ev, base, e;
3320 wide_int extreme;
3321 bool folded_casts, overflow;
3322
3323 iv->base = NULL_TREE;
3324 iv->step = NULL_TREE;
3325 iv->no_overflow = false;
3326
3327 type = TREE_TYPE (op);
3328 if (!POINTER_TYPE_P (type)
3329 && !INTEGRAL_TYPE_P (type))
3330 return false;
3331
3332 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3333 &folded_casts);
3334 if (chrec_contains_undetermined (ev)
3335 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3336 return false;
3337
3338 if (tree_does_not_contain_chrecs (ev))
3339 {
3340 iv->base = ev;
3341 iv->step = build_int_cst (TREE_TYPE (ev), 0);
3342 iv->no_overflow = true;
3343 return true;
3344 }
3345
3346 /* If we can derive valid scalar evolution with assumptions. */
3347 if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
3348 ev = derive_simple_iv_with_niters (ev, iv_niters);
3349
3350 if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
3351 return false;
3352
3353 if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3354 return false;
3355
3356 iv->step = CHREC_RIGHT (ev);
3357 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3358 || tree_contains_chrecs (iv->step, NULL))
3359 return false;
3360
3361 iv->base = CHREC_LEFT (ev);
3362 if (tree_contains_chrecs (iv->base, NULL))
3363 return false;
3364
3365 iv->no_overflow = !folded_casts && nowrap_type_p (type);
3366
3367 if (!iv->no_overflow
3368 && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
3369 iv->no_overflow = true;
3370
3371 /* Try to simplify iv base:
3372
3373 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3374 == (signed T)(unsigned T)base + step
3375 == base + step
3376
3377 If we can prove operation (base + step) doesn't overflow or underflow.
3378 Specifically, we try to prove below conditions are satisfied:
3379
3380 base <= UPPER_BOUND (type) - step ;;step > 0
3381 base >= LOWER_BOUND (type) - step ;;step < 0
3382
3383 This is done by proving the reverse conditions are false using loop's
3384 initial conditions.
3385
3386 The is necessary to make loop niter, or iv overflow analysis easier
3387 for below example:
3388
3389 int foo (int *a, signed char s, signed char l)
3390 {
3391 signed char i;
3392 for (i = s; i < l; i++)
3393 a[i] = 0;
3394 return 0;
3395 }
3396
3397 Note variable I is firstly converted to type unsigned char, incremented,
3398 then converted back to type signed char. */
3399
3400 if (wrto_loop->num != use_loop->num)
3401 return true;
3402
3403 if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3404 return true;
3405
3406 type = TREE_TYPE (iv->base);
3407 e = TREE_OPERAND (iv->base, 0);
3408 if (TREE_CODE (e) != PLUS_EXPR
3409 || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3410 || !tree_int_cst_equal (iv->step,
3411 fold_convert (type, TREE_OPERAND (e, 1))))
3412 return true;
3413 e = TREE_OPERAND (e, 0);
3414 if (!CONVERT_EXPR_P (e))
3415 return true;
3416 base = TREE_OPERAND (e, 0);
3417 if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3418 return true;
3419
3420 if (tree_int_cst_sign_bit (iv->step))
3421 {
3422 code = LT_EXPR;
3423 extreme = wi::min_value (type);
3424 }
3425 else
3426 {
3427 code = GT_EXPR;
3428 extreme = wi::max_value (type);
3429 }
3430 overflow = false;
3431 extreme = wi::sub (extreme, wi::to_wide (iv->step),
3432 TYPE_SIGN (type), &overflow);
3433 if (overflow)
3434 return true;
3435 e = fold_build2 (code, boolean_type_node, base,
3436 wide_int_to_tree (type, extreme));
3437 e = simplify_using_initial_conditions (use_loop, e);
3438 if (!integer_zerop (e))
3439 return true;
3440
3441 if (POINTER_TYPE_P (TREE_TYPE (base)))
3442 code = POINTER_PLUS_EXPR;
3443 else
3444 code = PLUS_EXPR;
3445
3446 iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3447 return true;
3448 }
3449
3450 /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3451 affine iv unconditionally. */
3452
3453 bool
simple_iv(struct loop * wrto_loop,struct loop * use_loop,tree op,affine_iv * iv,bool allow_nonconstant_step)3454 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3455 affine_iv *iv, bool allow_nonconstant_step)
3456 {
3457 return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
3458 NULL, allow_nonconstant_step);
3459 }
3460
3461 /* Finalize the scalar evolution analysis. */
3462
3463 void
scev_finalize(void)3464 scev_finalize (void)
3465 {
3466 if (!scalar_evolution_info)
3467 return;
3468 scalar_evolution_info->empty ();
3469 scalar_evolution_info = NULL;
3470 free_numbers_of_iterations_estimates (cfun);
3471 }
3472
3473 /* Returns true if the expression EXPR is considered to be too expensive
3474 for scev_const_prop. */
3475
3476 bool
expression_expensive_p(tree expr)3477 expression_expensive_p (tree expr)
3478 {
3479 enum tree_code code;
3480
3481 if (is_gimple_val (expr))
3482 return false;
3483
3484 code = TREE_CODE (expr);
3485 if (code == TRUNC_DIV_EXPR
3486 || code == CEIL_DIV_EXPR
3487 || code == FLOOR_DIV_EXPR
3488 || code == ROUND_DIV_EXPR
3489 || code == TRUNC_MOD_EXPR
3490 || code == CEIL_MOD_EXPR
3491 || code == FLOOR_MOD_EXPR
3492 || code == ROUND_MOD_EXPR
3493 || code == EXACT_DIV_EXPR)
3494 {
3495 /* Division by power of two is usually cheap, so we allow it.
3496 Forbid anything else. */
3497 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3498 return true;
3499 }
3500
3501 switch (TREE_CODE_CLASS (code))
3502 {
3503 case tcc_binary:
3504 case tcc_comparison:
3505 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3506 return true;
3507
3508 /* Fallthru. */
3509 case tcc_unary:
3510 return expression_expensive_p (TREE_OPERAND (expr, 0));
3511
3512 default:
3513 return true;
3514 }
3515 }
3516
3517 /* Do final value replacement for LOOP. */
3518
3519 void
final_value_replacement_loop(struct loop * loop)3520 final_value_replacement_loop (struct loop *loop)
3521 {
3522 /* If we do not know exact number of iterations of the loop, we cannot
3523 replace the final value. */
3524 edge exit = single_exit (loop);
3525 if (!exit)
3526 return;
3527
3528 tree niter = number_of_latch_executions (loop);
3529 if (niter == chrec_dont_know)
3530 return;
3531
3532 /* Ensure that it is possible to insert new statements somewhere. */
3533 if (!single_pred_p (exit->dest))
3534 split_loop_exit_edge (exit);
3535
3536 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3537 gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
3538
3539 struct loop *ex_loop
3540 = superloop_at_depth (loop,
3541 loop_depth (exit->dest->loop_father) + 1);
3542
3543 gphi_iterator psi;
3544 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3545 {
3546 gphi *phi = psi.phi ();
3547 tree rslt = PHI_RESULT (phi);
3548 tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3549 if (virtual_operand_p (def))
3550 {
3551 gsi_next (&psi);
3552 continue;
3553 }
3554
3555 if (!POINTER_TYPE_P (TREE_TYPE (def))
3556 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3557 {
3558 gsi_next (&psi);
3559 continue;
3560 }
3561
3562 bool folded_casts;
3563 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3564 &folded_casts);
3565 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3566 if (!tree_does_not_contain_chrecs (def)
3567 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3568 /* Moving the computation from the loop may prolong life range
3569 of some ssa names, which may cause problems if they appear
3570 on abnormal edges. */
3571 || contains_abnormal_ssa_name_p (def)
3572 /* Do not emit expensive expressions. The rationale is that
3573 when someone writes a code like
3574
3575 while (n > 45) n -= 45;
3576
3577 he probably knows that n is not large, and does not want it
3578 to be turned into n %= 45. */
3579 || expression_expensive_p (def))
3580 {
3581 if (dump_file && (dump_flags & TDF_DETAILS))
3582 {
3583 fprintf (dump_file, "not replacing:\n ");
3584 print_gimple_stmt (dump_file, phi, 0);
3585 fprintf (dump_file, "\n");
3586 }
3587 gsi_next (&psi);
3588 continue;
3589 }
3590
3591 /* Eliminate the PHI node and replace it by a computation outside
3592 the loop. */
3593 if (dump_file)
3594 {
3595 fprintf (dump_file, "\nfinal value replacement:\n ");
3596 print_gimple_stmt (dump_file, phi, 0);
3597 fprintf (dump_file, " with\n ");
3598 }
3599 def = unshare_expr (def);
3600 remove_phi_node (&psi, false);
3601
3602 /* If def's type has undefined overflow and there were folded
3603 casts, rewrite all stmts added for def into arithmetics
3604 with defined overflow behavior. */
3605 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3606 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3607 {
3608 gimple_seq stmts;
3609 gimple_stmt_iterator gsi2;
3610 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3611 gsi2 = gsi_start (stmts);
3612 while (!gsi_end_p (gsi2))
3613 {
3614 gimple *stmt = gsi_stmt (gsi2);
3615 gimple_stmt_iterator gsi3 = gsi2;
3616 gsi_next (&gsi2);
3617 gsi_remove (&gsi3, false);
3618 if (is_gimple_assign (stmt)
3619 && arith_code_with_undefined_signed_overflow
3620 (gimple_assign_rhs_code (stmt)))
3621 gsi_insert_seq_before (&gsi,
3622 rewrite_to_defined_overflow (stmt),
3623 GSI_SAME_STMT);
3624 else
3625 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3626 }
3627 }
3628 else
3629 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3630 true, GSI_SAME_STMT);
3631
3632 gassign *ass = gimple_build_assign (rslt, def);
3633 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3634 if (dump_file)
3635 {
3636 print_gimple_stmt (dump_file, ass, 0);
3637 fprintf (dump_file, "\n");
3638 }
3639 }
3640 }
3641
3642 /* Replace ssa names for that scev can prove they are constant by the
3643 appropriate constants. Also perform final value replacement in loops,
3644 in case the replacement expressions are cheap.
3645
3646 We only consider SSA names defined by phi nodes; rest is left to the
3647 ordinary constant propagation pass. */
3648
3649 unsigned int
scev_const_prop(void)3650 scev_const_prop (void)
3651 {
3652 basic_block bb;
3653 tree name, type, ev;
3654 gphi *phi;
3655 struct loop *loop;
3656 bitmap ssa_names_to_remove = NULL;
3657 unsigned i;
3658 gphi_iterator psi;
3659
3660 if (number_of_loops (cfun) <= 1)
3661 return 0;
3662
3663 FOR_EACH_BB_FN (bb, cfun)
3664 {
3665 loop = bb->loop_father;
3666
3667 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3668 {
3669 phi = psi.phi ();
3670 name = PHI_RESULT (phi);
3671
3672 if (virtual_operand_p (name))
3673 continue;
3674
3675 type = TREE_TYPE (name);
3676
3677 if (!POINTER_TYPE_P (type)
3678 && !INTEGRAL_TYPE_P (type))
3679 continue;
3680
3681 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
3682 NULL);
3683 if (!is_gimple_min_invariant (ev)
3684 || !may_propagate_copy (name, ev))
3685 continue;
3686
3687 /* Replace the uses of the name. */
3688 if (name != ev)
3689 {
3690 if (dump_file && (dump_flags & TDF_DETAILS))
3691 {
3692 fprintf (dump_file, "Replacing uses of: ");
3693 print_generic_expr (dump_file, name);
3694 fprintf (dump_file, " with: ");
3695 print_generic_expr (dump_file, ev);
3696 fprintf (dump_file, "\n");
3697 }
3698 replace_uses_by (name, ev);
3699 }
3700
3701 if (!ssa_names_to_remove)
3702 ssa_names_to_remove = BITMAP_ALLOC (NULL);
3703 bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3704 }
3705 }
3706
3707 /* Remove the ssa names that were replaced by constants. We do not
3708 remove them directly in the previous cycle, since this
3709 invalidates scev cache. */
3710 if (ssa_names_to_remove)
3711 {
3712 bitmap_iterator bi;
3713
3714 EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
3715 {
3716 gimple_stmt_iterator psi;
3717 name = ssa_name (i);
3718 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3719
3720 gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3721 psi = gsi_for_stmt (phi);
3722 remove_phi_node (&psi, true);
3723 }
3724
3725 BITMAP_FREE (ssa_names_to_remove);
3726 scev_reset ();
3727 }
3728
3729 /* Now the regular final value replacement. */
3730 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3731 final_value_replacement_loop (loop);
3732
3733 return 0;
3734 }
3735
3736 #include "gt-tree-scalar-evolution.h"
3737