Line data Source code
1 : /* Scalar evolution detector.
2 : Copyright (C) 2003-2026 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 "target.h"
261 : #include "rtl.h"
262 : #include "optabs-query.h"
263 : #include "tree.h"
264 : #include "gimple.h"
265 : #include "ssa.h"
266 : #include "gimple-pretty-print.h"
267 : #include "fold-const.h"
268 : #include "gimplify.h"
269 : #include "gimple-iterator.h"
270 : #include "gimplify-me.h"
271 : #include "tree-cfg.h"
272 : #include "tree-ssa-loop-ivopts.h"
273 : #include "tree-ssa-loop-manip.h"
274 : #include "tree-ssa-loop-niter.h"
275 : #include "tree-ssa-loop.h"
276 : #include "tree-ssa.h"
277 : #include "cfgloop.h"
278 : #include "tree-chrec.h"
279 : #include "tree-affine.h"
280 : #include "tree-scalar-evolution.h"
281 : #include "dumpfile.h"
282 : #include "tree-ssa-propagate.h"
283 : #include "gimple-fold.h"
284 : #include "tree-into-ssa.h"
285 : #include "builtins.h"
286 : #include "case-cfn-macros.h"
287 : #include "tree-eh.h"
288 :
289 : static tree analyze_scalar_evolution_1 (class loop *, tree);
290 : static tree analyze_scalar_evolution_for_address_of (class loop *loop,
291 : tree var);
292 :
293 : /* The cached information about an SSA name with version NAME_VERSION,
294 : claiming that below basic block with index INSTANTIATED_BELOW, the
295 : value of the SSA name can be expressed as CHREC. */
296 :
297 : struct GTY((for_user)) scev_info_str {
298 : unsigned int name_version;
299 : int instantiated_below;
300 : tree chrec;
301 : };
302 :
303 : /* Counters for the scev database. */
304 : static unsigned nb_set_scev = 0;
305 : static unsigned nb_get_scev = 0;
306 :
307 : struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
308 : {
309 : static hashval_t hash (scev_info_str *i);
310 : static bool equal (const scev_info_str *a, const scev_info_str *b);
311 : };
312 :
313 : static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
314 :
315 :
316 : /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
317 :
318 : static inline struct scev_info_str *
319 53789456 : new_scev_info_str (basic_block instantiated_below, tree var)
320 : {
321 53789456 : struct scev_info_str *res;
322 :
323 53789456 : res = ggc_alloc<scev_info_str> ();
324 53789456 : res->name_version = SSA_NAME_VERSION (var);
325 53789456 : res->chrec = chrec_not_analyzed_yet;
326 53789456 : res->instantiated_below = instantiated_below->index;
327 :
328 53789456 : return res;
329 : }
330 :
331 : /* Computes a hash function for database element ELT. */
332 :
333 : hashval_t
334 1087102668 : scev_info_hasher::hash (scev_info_str *elt)
335 : {
336 1087102668 : return elt->name_version ^ elt->instantiated_below;
337 : }
338 :
339 : /* Compares database elements E1 and E2. */
340 :
341 : bool
342 1079318520 : scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
343 : {
344 1079318520 : return (elt1->name_version == elt2->name_version
345 1079318520 : && elt1->instantiated_below == elt2->instantiated_below);
346 : }
347 :
348 : /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
349 : A first query on VAR returns chrec_not_analyzed_yet. */
350 :
351 : static tree *
352 209196451 : find_var_scev_info (basic_block instantiated_below, tree var)
353 : {
354 209196451 : struct scev_info_str *res;
355 209196451 : struct scev_info_str tmp;
356 :
357 209196451 : tmp.name_version = SSA_NAME_VERSION (var);
358 209196451 : tmp.instantiated_below = instantiated_below->index;
359 209196451 : scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
360 :
361 209196451 : if (!*slot)
362 53789456 : *slot = new_scev_info_str (instantiated_below, var);
363 209196451 : res = *slot;
364 :
365 209196451 : return &res->chrec;
366 : }
367 :
368 :
369 : /* Hashtable helpers for a temporary hash-table used when
370 : analyzing a scalar evolution, instantiating a CHREC or
371 : resolving mixers. */
372 :
373 : class instantiate_cache_type
374 : {
375 : public:
376 : htab_t map;
377 : vec<scev_info_str> entries;
378 :
379 131371399 : instantiate_cache_type () : map (NULL), entries (vNULL) {}
380 : ~instantiate_cache_type ();
381 128276416 : tree get (unsigned slot) { return entries[slot].chrec; }
382 99031123 : void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
383 : };
384 :
385 131371399 : instantiate_cache_type::~instantiate_cache_type ()
386 : {
387 131371399 : if (map != NULL)
388 : {
389 29197519 : htab_delete (map);
390 29197519 : entries.release ();
391 : }
392 131371399 : }
393 :
394 : /* Cache to avoid infinite recursion when instantiating an SSA name.
395 : Live during the outermost analyze_scalar_evolution, instantiate_scev
396 : or resolve_mixers call. */
397 : static instantiate_cache_type *global_cache;
398 :
399 :
400 : /* Return true when PHI is a loop-phi-node. */
401 :
402 : static bool
403 26967960 : loop_phi_node_p (gimple *phi)
404 : {
405 : /* The implementation of this function is based on the following
406 : property: "all the loop-phi-nodes of a loop are contained in the
407 : loop's header basic block". */
408 :
409 0 : return loop_containing_stmt (phi)->header == gimple_bb (phi);
410 : }
411 :
412 : /* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
413 : In general, in the case of multivariate evolutions we want to get
414 : the evolution in different loops. LOOP specifies the level for
415 : which to get the evolution.
416 :
417 : Example:
418 :
419 : | for (j = 0; j < 100; j++)
420 : | {
421 : | for (k = 0; k < 100; k++)
422 : | {
423 : | i = k + j; - Here the value of i is a function of j, k.
424 : | }
425 : | ... = i - Here the value of i is a function of j.
426 : | }
427 : | ... = i - Here the value of i is a scalar.
428 :
429 : Example:
430 :
431 : | i_0 = ...
432 : | loop_1 10 times
433 : | i_1 = phi (i_0, i_2)
434 : | i_2 = i_1 + 2
435 : | endloop
436 :
437 : This loop has the same effect as:
438 : LOOP_1 has the same effect as:
439 :
440 : | i_1 = i_0 + 20
441 :
442 : The overall effect of the loop, "i_0 + 20" in the previous example,
443 : is obtained by passing in the parameters: LOOP = 1,
444 : EVOLUTION_FN = {i_0, +, 2}_1.
445 : */
446 :
447 : tree
448 5472484 : compute_overall_effect_of_inner_loop (class loop *loop, tree evolution_fn)
449 : {
450 6373243 : bool val = false;
451 :
452 6373243 : if (evolution_fn == chrec_dont_know)
453 : return chrec_dont_know;
454 :
455 6238846 : else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
456 : {
457 2430452 : class loop *inner_loop = get_chrec_loop (evolution_fn);
458 :
459 2430452 : if (inner_loop == loop
460 2430452 : || flow_loop_nested_p (loop, inner_loop))
461 : {
462 2430452 : tree nb_iter = number_of_latch_executions (inner_loop);
463 :
464 2430452 : if (nb_iter == chrec_dont_know)
465 : return chrec_dont_know;
466 : else
467 : {
468 900759 : tree res;
469 :
470 : /* evolution_fn is the evolution function in LOOP. Get
471 : its value in the nb_iter-th iteration. */
472 900759 : res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
473 :
474 900759 : if (chrec_contains_symbols_defined_in_loop (res, loop->num))
475 60055 : res = instantiate_parameters (loop, res);
476 :
477 : /* Continue the computation until ending on a parent of LOOP. */
478 900759 : return compute_overall_effect_of_inner_loop (loop, res);
479 : }
480 : }
481 : else
482 : return evolution_fn;
483 : }
484 :
485 : /* If the evolution function is an invariant, there is nothing to do. */
486 3808394 : else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
487 : return evolution_fn;
488 :
489 : else
490 3036569 : return chrec_dont_know;
491 : }
492 :
493 : /* Associate CHREC to SCALAR. */
494 :
495 : static void
496 51148321 : set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
497 : {
498 51148321 : tree *scalar_info;
499 :
500 51148321 : if (TREE_CODE (scalar) != SSA_NAME)
501 : return;
502 :
503 51148321 : scalar_info = find_var_scev_info (instantiated_below, scalar);
504 :
505 51148321 : if (dump_file)
506 : {
507 85674 : if (dump_flags & TDF_SCEV)
508 : {
509 11 : fprintf (dump_file, "(set_scalar_evolution \n");
510 11 : fprintf (dump_file, " instantiated_below = %d \n",
511 : instantiated_below->index);
512 11 : fprintf (dump_file, " (scalar = ");
513 11 : print_generic_expr (dump_file, scalar);
514 11 : fprintf (dump_file, ")\n (scalar_evolution = ");
515 11 : print_generic_expr (dump_file, chrec);
516 11 : fprintf (dump_file, "))\n");
517 : }
518 85674 : if (dump_flags & TDF_STATS)
519 7193 : nb_set_scev++;
520 : }
521 :
522 51148321 : *scalar_info = chrec;
523 : }
524 :
525 : /* Retrieve the chrec associated to SCALAR instantiated below
526 : INSTANTIATED_BELOW block. */
527 :
528 : static tree
529 196820822 : get_scalar_evolution (basic_block instantiated_below, tree scalar)
530 : {
531 196820822 : tree res;
532 :
533 196820822 : if (dump_file)
534 : {
535 700271 : if (dump_flags & TDF_SCEV)
536 : {
537 38 : fprintf (dump_file, "(get_scalar_evolution \n");
538 38 : fprintf (dump_file, " (scalar = ");
539 38 : print_generic_expr (dump_file, scalar);
540 38 : fprintf (dump_file, ")\n");
541 : }
542 700271 : if (dump_flags & TDF_STATS)
543 51089 : nb_get_scev++;
544 : }
545 :
546 196820822 : if (VECTOR_TYPE_P (TREE_TYPE (scalar))
547 196820822 : || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
548 : /* For chrec_dont_know we keep the symbolic form. */
549 : res = scalar;
550 : else
551 196531372 : switch (TREE_CODE (scalar))
552 : {
553 160200051 : case SSA_NAME:
554 160200051 : if (SSA_NAME_IS_DEFAULT_DEF (scalar))
555 : res = scalar;
556 : else
557 158048130 : res = *find_var_scev_info (instantiated_below, scalar);
558 : break;
559 :
560 : case REAL_CST:
561 : case FIXED_CST:
562 : case INTEGER_CST:
563 : res = scalar;
564 : break;
565 :
566 : default:
567 196820822 : res = chrec_not_analyzed_yet;
568 : break;
569 : }
570 :
571 196820822 : if (dump_file && (dump_flags & TDF_SCEV))
572 : {
573 38 : fprintf (dump_file, " (scalar_evolution = ");
574 38 : print_generic_expr (dump_file, res);
575 38 : fprintf (dump_file, "))\n");
576 : }
577 :
578 196820822 : return res;
579 : }
580 :
581 :
582 : /* Depth first search algorithm. */
583 :
584 : enum t_bool {
585 : t_false,
586 : t_true,
587 : t_dont_know
588 : };
589 :
590 : class scev_dfs
591 : {
592 : public:
593 11126120 : scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_)
594 11126120 : : loop (loop_), loop_phi_node (phi_), init_cond (init_cond_) {}
595 : t_bool get_ev (tree *, tree);
596 :
597 : private:
598 : t_bool follow_ssa_edge_expr (gimple *, tree, tree *, int);
599 : t_bool follow_ssa_edge_binary (gimple *at_stmt,
600 : tree type, tree rhs0, enum tree_code code,
601 : tree rhs1, tree *evolution_of_loop, int limit);
602 : t_bool follow_ssa_edge_in_condition_phi_branch (int i,
603 : gphi *condition_phi,
604 : tree *evolution_of_branch,
605 : tree init_cond, int limit);
606 : t_bool follow_ssa_edge_in_condition_phi (gphi *condition_phi,
607 : tree *evolution_of_loop, int limit);
608 : t_bool follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
609 : tree *evolution_of_loop, int limit);
610 : tree add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt);
611 : tree add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt);
612 :
613 : class loop *loop;
614 : gphi *loop_phi_node;
615 : tree init_cond;
616 : };
617 :
618 : t_bool
619 11126120 : scev_dfs::get_ev (tree *ev_fn, tree arg)
620 : {
621 11126120 : *ev_fn = chrec_dont_know;
622 11126120 : return follow_ssa_edge_expr (loop_phi_node, arg, ev_fn, 0);
623 : }
624 :
625 : /* Helper function for add_to_evolution. Returns the evolution
626 : function for an assignment of the form "a = b + c", where "a" and
627 : "b" are on the strongly connected component. CHREC_BEFORE is the
628 : information that we already have collected up to this point.
629 : TO_ADD is the evolution of "c".
630 :
631 : When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
632 : evolution the expression TO_ADD, otherwise construct an evolution
633 : part for this loop. */
634 :
635 : tree
636 9054904 : scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
637 : {
638 9054904 : tree type, left, right;
639 9054904 : unsigned loop_nb = loop->num;
640 9054904 : class loop *chloop;
641 :
642 9054904 : switch (TREE_CODE (chrec_before))
643 : {
644 88373 : case POLYNOMIAL_CHREC:
645 88373 : chloop = get_chrec_loop (chrec_before);
646 88373 : if (chloop == loop
647 88373 : || flow_loop_nested_p (chloop, loop))
648 : {
649 88373 : unsigned var;
650 :
651 88373 : type = chrec_type (chrec_before);
652 :
653 : /* When there is no evolution part in this loop, build it. */
654 88373 : if (chloop != loop)
655 : {
656 0 : var = loop_nb;
657 0 : left = chrec_before;
658 0 : right = SCALAR_FLOAT_TYPE_P (type)
659 0 : ? build_real (type, dconst0)
660 0 : : build_int_cst (type, 0);
661 : }
662 : else
663 : {
664 88373 : var = CHREC_VARIABLE (chrec_before);
665 88373 : left = CHREC_LEFT (chrec_before);
666 88373 : right = CHREC_RIGHT (chrec_before);
667 : }
668 :
669 88373 : to_add = chrec_convert (type, to_add, at_stmt);
670 88373 : right = chrec_convert_rhs (type, right, at_stmt);
671 88373 : right = chrec_fold_plus (chrec_type (right), right, to_add);
672 : /* When we have an evolution in a non-wrapping type and
673 : in the process of accumulating CHREC_RIGHT there was
674 : overflow this indicates in the association that happened
675 : in building the CHREC clearly involved UB. Avoid this.
676 : In building a CHREC we basically turn (a + INCR1) + INCR2
677 : into a + (INCR1 + INCR2) which is not always valid.
678 : Note this check only catches few invalid cases. */
679 58600 : if ((INTEGRAL_TYPE_P (type) && ! TYPE_OVERFLOW_WRAPS (type))
680 33241 : && TREE_CODE (right) == INTEGER_CST
681 90637 : && TREE_OVERFLOW (right))
682 5 : return chrec_dont_know;
683 88368 : return build_polynomial_chrec (var, left, right);
684 : }
685 : else
686 : {
687 0 : gcc_assert (flow_loop_nested_p (loop, chloop));
688 :
689 : /* Search the evolution in LOOP_NB. */
690 0 : left = add_to_evolution_1 (CHREC_LEFT (chrec_before),
691 : to_add, at_stmt);
692 0 : right = CHREC_RIGHT (chrec_before);
693 0 : right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
694 0 : return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
695 0 : left, right);
696 : }
697 :
698 8966531 : default:
699 : /* These nodes do not depend on a loop. */
700 8966531 : if (chrec_before == chrec_dont_know)
701 : return chrec_dont_know;
702 :
703 8947195 : left = chrec_before;
704 8947195 : right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
705 : /* When we add the first evolution we need to replace the symbolic
706 : evolution we've put in when the DFS reached the loop PHI node
707 : with the initial value. There's only a limited cases of
708 : extra operations on top of that symbol allowed, namely
709 : sign-conversions we can look through. For other cases we leave
710 : the symbolic initial condition which causes build_polynomial_chrec
711 : to return chrec_dont_know. See PR42512, PR66375 and PR107176 for
712 : cases we mishandled before. */
713 8947195 : STRIP_NOPS (chrec_before);
714 8947195 : if (chrec_before == gimple_phi_result (loop_phi_node))
715 8946436 : left = fold_convert (TREE_TYPE (left), init_cond);
716 8947195 : return build_polynomial_chrec (loop_nb, left, right);
717 : }
718 : }
719 :
720 : /* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
721 : of LOOP_NB.
722 :
723 : Description (provided for completeness, for those who read code in
724 : a plane, and for my poor 62 bytes brain that would have forgotten
725 : all this in the next two or three months):
726 :
727 : The algorithm of translation of programs from the SSA representation
728 : into the chrecs syntax is based on a pattern matching. After having
729 : reconstructed the overall tree expression for a loop, there are only
730 : two cases that can arise:
731 :
732 : 1. a = loop-phi (init, a + expr)
733 : 2. a = loop-phi (init, expr)
734 :
735 : where EXPR is either a scalar constant with respect to the analyzed
736 : loop (this is a degree 0 polynomial), or an expression containing
737 : other loop-phi definitions (these are higher degree polynomials).
738 :
739 : Examples:
740 :
741 : 1.
742 : | init = ...
743 : | loop_1
744 : | a = phi (init, a + 5)
745 : | endloop
746 :
747 : 2.
748 : | inita = ...
749 : | initb = ...
750 : | loop_1
751 : | a = phi (inita, 2 * b + 3)
752 : | b = phi (initb, b + 1)
753 : | endloop
754 :
755 : For the first case, the semantics of the SSA representation is:
756 :
757 : | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
758 :
759 : that is, there is a loop index "x" that determines the scalar value
760 : of the variable during the loop execution. During the first
761 : iteration, the value is that of the initial condition INIT, while
762 : during the subsequent iterations, it is the sum of the initial
763 : condition with the sum of all the values of EXPR from the initial
764 : iteration to the before last considered iteration.
765 :
766 : For the second case, the semantics of the SSA program is:
767 :
768 : | a (x) = init, if x = 0;
769 : | expr (x - 1), otherwise.
770 :
771 : The second case corresponds to the PEELED_CHREC, whose syntax is
772 : close to the syntax of a loop-phi-node:
773 :
774 : | phi (init, expr) vs. (init, expr)_x
775 :
776 : The proof of the translation algorithm for the first case is a
777 : proof by structural induction based on the degree of EXPR.
778 :
779 : Degree 0:
780 : When EXPR is a constant with respect to the analyzed loop, or in
781 : other words when EXPR is a polynomial of degree 0, the evolution of
782 : the variable A in the loop is an affine function with an initial
783 : condition INIT, and a step EXPR. In order to show this, we start
784 : from the semantics of the SSA representation:
785 :
786 : f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
787 :
788 : and since "expr (j)" is a constant with respect to "j",
789 :
790 : f (x) = init + x * expr
791 :
792 : Finally, based on the semantics of the pure sum chrecs, by
793 : identification we get the corresponding chrecs syntax:
794 :
795 : f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
796 : f (x) -> {init, +, expr}_x
797 :
798 : Higher degree:
799 : Suppose that EXPR is a polynomial of degree N with respect to the
800 : analyzed loop_x for which we have already determined that it is
801 : written under the chrecs syntax:
802 :
803 : | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
804 :
805 : We start from the semantics of the SSA program:
806 :
807 : | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
808 : |
809 : | f (x) = init + \sum_{j = 0}^{x - 1}
810 : | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
811 : |
812 : | f (x) = init + \sum_{j = 0}^{x - 1}
813 : | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
814 : |
815 : | f (x) = init + \sum_{k = 0}^{n - 1}
816 : | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
817 : |
818 : | f (x) = init + \sum_{k = 0}^{n - 1}
819 : | (b_k * \binom{x}{k + 1})
820 : |
821 : | f (x) = init + b_0 * \binom{x}{1} + ...
822 : | + b_{n-1} * \binom{x}{n}
823 : |
824 : | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
825 : | + b_{n-1} * \binom{x}{n}
826 : |
827 :
828 : And finally from the definition of the chrecs syntax, we identify:
829 : | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
830 :
831 : This shows the mechanism that stands behind the add_to_evolution
832 : function. An important point is that the use of symbolic
833 : parameters avoids the need of an analysis schedule.
834 :
835 : Example:
836 :
837 : | inita = ...
838 : | initb = ...
839 : | loop_1
840 : | a = phi (inita, a + 2 + b)
841 : | b = phi (initb, b + 1)
842 : | endloop
843 :
844 : When analyzing "a", the algorithm keeps "b" symbolically:
845 :
846 : | a -> {inita, +, 2 + b}_1
847 :
848 : Then, after instantiation, the analyzer ends on the evolution:
849 :
850 : | a -> {inita, +, 2 + initb, +, 1}_1
851 :
852 : */
853 :
854 : tree
855 9054904 : scev_dfs::add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt)
856 : {
857 9054904 : tree res = NULL_TREE;
858 :
859 9054904 : if (to_add == NULL_TREE)
860 : return chrec_before;
861 :
862 : /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
863 : instantiated at this point. */
864 9054904 : if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
865 : /* This should not happen. */
866 0 : return chrec_dont_know;
867 :
868 9054904 : if (dump_file && (dump_flags & TDF_SCEV))
869 : {
870 1 : fprintf (dump_file, "(add_to_evolution \n");
871 1 : fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
872 1 : fprintf (dump_file, " (chrec_before = ");
873 1 : print_generic_expr (dump_file, chrec_before);
874 1 : fprintf (dump_file, ")\n (to_add = ");
875 1 : print_generic_expr (dump_file, to_add);
876 1 : fprintf (dump_file, ")\n");
877 : }
878 :
879 9054904 : res = add_to_evolution_1 (chrec_before, to_add, at_stmt);
880 :
881 9054904 : if (dump_file && (dump_flags & TDF_SCEV))
882 : {
883 1 : fprintf (dump_file, " (res = ");
884 1 : print_generic_expr (dump_file, res);
885 1 : fprintf (dump_file, "))\n");
886 : }
887 :
888 : return res;
889 : }
890 :
891 :
892 : /* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
893 : Return true if the strongly connected component has been found. */
894 :
895 : t_bool
896 1108290 : scev_dfs::follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0,
897 : enum tree_code code, tree rhs1,
898 : tree *evolution_of_loop, int limit)
899 : {
900 1108290 : t_bool res = t_false;
901 1108290 : tree evol;
902 :
903 1108290 : switch (code)
904 : {
905 1108290 : case POINTER_PLUS_EXPR:
906 1108290 : case PLUS_EXPR:
907 1108290 : if (TREE_CODE (rhs0) == SSA_NAME)
908 : {
909 1089109 : if (TREE_CODE (rhs1) == SSA_NAME)
910 : {
911 : /* Match an assignment under the form:
912 : "a = b + c". */
913 :
914 : /* We want only assignments of form "name + name" contribute to
915 : LIMIT, as the other cases do not necessarily contribute to
916 : the complexity of the expression. */
917 1089109 : limit++;
918 :
919 1089109 : evol = *evolution_of_loop;
920 1089109 : res = follow_ssa_edge_expr (at_stmt, rhs0, &evol, limit);
921 1089109 : if (res == t_true)
922 397924 : *evolution_of_loop = add_to_evolution
923 397924 : (chrec_convert (type, evol, at_stmt), rhs1, at_stmt);
924 691185 : else if (res == t_false)
925 : {
926 670828 : res = follow_ssa_edge_expr
927 670828 : (at_stmt, rhs1, evolution_of_loop, limit);
928 670828 : if (res == t_true)
929 516816 : *evolution_of_loop = add_to_evolution
930 516816 : (chrec_convert (type, *evolution_of_loop, at_stmt),
931 : rhs0, at_stmt);
932 : }
933 : }
934 :
935 : else
936 0 : gcc_unreachable (); /* Handled in caller. */
937 : }
938 :
939 19181 : else if (TREE_CODE (rhs1) == SSA_NAME)
940 : {
941 : /* Match an assignment under the form:
942 : "a = ... + c". */
943 7428 : res = follow_ssa_edge_expr (at_stmt, rhs1, evolution_of_loop, limit);
944 7428 : if (res == t_true)
945 6673 : *evolution_of_loop = add_to_evolution
946 6673 : (chrec_convert (type, *evolution_of_loop, at_stmt),
947 : rhs0, at_stmt);
948 : }
949 :
950 : else
951 : /* Otherwise, match an assignment under the form:
952 : "a = ... + ...". */
953 : /* And there is nothing to do. */
954 : res = t_false;
955 : break;
956 :
957 : default:
958 : res = t_false;
959 : }
960 :
961 1108290 : return res;
962 : }
963 :
964 : /* Checks whether the I-th argument of a PHI comes from a backedge. */
965 :
966 : static bool
967 8901429 : backedge_phi_arg_p (gphi *phi, int i)
968 : {
969 8901429 : const_edge e = gimple_phi_arg_edge (phi, i);
970 :
971 : /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
972 : about updating it anywhere, and this should work as well most of the
973 : time. */
974 8901429 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
975 57435 : return true;
976 :
977 : return false;
978 : }
979 :
980 : /* Helper function for one branch of the condition-phi-node. Return
981 : true if the strongly connected component has been found following
982 : this path. */
983 :
984 : t_bool
985 3681908 : scev_dfs::follow_ssa_edge_in_condition_phi_branch (int i,
986 : gphi *condition_phi,
987 : tree *evolution_of_branch,
988 : tree init_cond, int limit)
989 : {
990 3681908 : tree branch = PHI_ARG_DEF (condition_phi, i);
991 3681908 : *evolution_of_branch = chrec_dont_know;
992 :
993 : /* Do not follow back edges (they must belong to an irreducible loop, which
994 : we really do not want to worry about). */
995 3681908 : if (backedge_phi_arg_p (condition_phi, i))
996 : return t_false;
997 :
998 3673548 : if (TREE_CODE (branch) == SSA_NAME)
999 : {
1000 3424245 : *evolution_of_branch = init_cond;
1001 3424245 : return follow_ssa_edge_expr (condition_phi, branch,
1002 3424245 : evolution_of_branch, limit);
1003 : }
1004 :
1005 : /* This case occurs when one of the condition branches sets
1006 : the variable to a constant: i.e. a phi-node like
1007 : "a_2 = PHI <a_7(5), 2(6)>;".
1008 :
1009 : FIXME: This case have to be refined correctly:
1010 : in some cases it is possible to say something better than
1011 : chrec_dont_know, for example using a wrap-around notation. */
1012 : return t_false;
1013 : }
1014 :
1015 : /* This function merges the branches of a condition-phi-node in a
1016 : loop. */
1017 :
1018 : t_bool
1019 2332661 : scev_dfs::follow_ssa_edge_in_condition_phi (gphi *condition_phi,
1020 : tree *evolution_of_loop, int limit)
1021 : {
1022 2332661 : int i, n;
1023 2332661 : tree init = *evolution_of_loop;
1024 2332661 : tree evolution_of_branch;
1025 2332661 : t_bool res = follow_ssa_edge_in_condition_phi_branch (0, condition_phi,
1026 : &evolution_of_branch,
1027 : init, limit);
1028 2332661 : if (res == t_false || res == t_dont_know)
1029 : return res;
1030 :
1031 1327331 : *evolution_of_loop = evolution_of_branch;
1032 :
1033 1327331 : n = gimple_phi_num_args (condition_phi);
1034 1907964 : for (i = 1; i < n; i++)
1035 : {
1036 : /* Quickly give up when the evolution of one of the branches is
1037 : not known. */
1038 1498413 : if (*evolution_of_loop == chrec_dont_know)
1039 : return t_true;
1040 :
1041 : /* Increase the limit by the PHI argument number to avoid exponential
1042 : time and memory complexity. */
1043 1349247 : res = follow_ssa_edge_in_condition_phi_branch (i, condition_phi,
1044 : &evolution_of_branch,
1045 : init, limit + i);
1046 1349247 : if (res == t_false || res == t_dont_know)
1047 : return res;
1048 :
1049 580633 : *evolution_of_loop = chrec_merge (*evolution_of_loop,
1050 : evolution_of_branch);
1051 : }
1052 :
1053 : return t_true;
1054 : }
1055 :
1056 : /* Follow an SSA edge in an inner loop. It computes the overall
1057 : effect of the loop, and following the symbolic initial conditions,
1058 : it follows the edges in the parent loop. The inner loop is
1059 : considered as a single statement. */
1060 :
1061 : t_bool
1062 288816 : scev_dfs::follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
1063 : tree *evolution_of_loop, int limit)
1064 : {
1065 288816 : class loop *loop = loop_containing_stmt (loop_phi_node);
1066 288816 : tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1067 :
1068 : /* Sometimes, the inner loop is too difficult to analyze, and the
1069 : result of the analysis is a symbolic parameter. */
1070 288816 : if (ev == PHI_RESULT (loop_phi_node))
1071 : {
1072 112143 : t_bool res = t_false;
1073 112143 : int i, n = gimple_phi_num_args (loop_phi_node);
1074 :
1075 164101 : for (i = 0; i < n; i++)
1076 : {
1077 155015 : tree arg = PHI_ARG_DEF (loop_phi_node, i);
1078 155015 : basic_block bb;
1079 :
1080 : /* Follow the edges that exit the inner loop. */
1081 155015 : bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1082 155015 : if (!flow_bb_inside_loop_p (loop, bb))
1083 112143 : res = follow_ssa_edge_expr (loop_phi_node,
1084 : arg, evolution_of_loop, limit);
1085 155015 : if (res == t_true)
1086 : break;
1087 : }
1088 :
1089 : /* If the path crosses this loop-phi, give up. */
1090 112143 : if (res == t_true)
1091 103057 : *evolution_of_loop = chrec_dont_know;
1092 :
1093 : return res;
1094 : }
1095 :
1096 : /* Otherwise, compute the overall effect of the inner loop. */
1097 176673 : ev = compute_overall_effect_of_inner_loop (loop, ev);
1098 176673 : return follow_ssa_edge_expr (loop_phi_node, ev, evolution_of_loop, limit);
1099 : }
1100 :
1101 : /* Follow the ssa edge into the expression EXPR.
1102 : Return true if the strongly connected component has been found. */
1103 :
1104 : t_bool
1105 25243578 : scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
1106 : tree *evolution_of_loop, int limit)
1107 : {
1108 25243578 : gphi *halting_phi = loop_phi_node;
1109 25243578 : enum tree_code code;
1110 25243578 : tree type, rhs0, rhs1 = NULL_TREE;
1111 :
1112 : /* The EXPR is one of the following cases:
1113 : - an SSA_NAME,
1114 : - an INTEGER_CST,
1115 : - a PLUS_EXPR,
1116 : - a POINTER_PLUS_EXPR,
1117 : - a MINUS_EXPR,
1118 : - other cases are not yet handled. */
1119 :
1120 : /* For SSA_NAME look at the definition statement, handling
1121 : PHI nodes and otherwise expand appropriately for the expression
1122 : handling below. */
1123 25243578 : if (TREE_CODE (expr) == SSA_NAME)
1124 : {
1125 25054156 : gimple *def = SSA_NAME_DEF_STMT (expr);
1126 :
1127 25054156 : if (gimple_nop_p (def))
1128 : return t_false;
1129 :
1130 : /* Give up if the path is longer than the MAX that we allow. */
1131 25037900 : if (limit > param_scev_max_expr_complexity)
1132 : {
1133 7180 : *evolution_of_loop = chrec_dont_know;
1134 7180 : return t_dont_know;
1135 : }
1136 :
1137 25030720 : if (gphi *phi = dyn_cast <gphi *>(def))
1138 : {
1139 26012526 : if (!loop_phi_node_p (phi))
1140 : /* DEF is a condition-phi-node. Follow the branches, and
1141 : record their evolutions. Finally, merge the collected
1142 : information and set the approximation to the main
1143 : variable. */
1144 2332661 : return follow_ssa_edge_in_condition_phi (phi, evolution_of_loop,
1145 2332661 : limit);
1146 :
1147 : /* When the analyzed phi is the halting_phi, the
1148 : depth-first search is over: we have found a path from
1149 : the halting_phi to itself in the loop. */
1150 10673602 : if (phi == halting_phi)
1151 : {
1152 10142580 : *evolution_of_loop = expr;
1153 10142580 : return t_true;
1154 : }
1155 :
1156 : /* Otherwise, the evolution of the HALTING_PHI depends
1157 : on the evolution of another loop-phi-node, i.e. the
1158 : evolution function is a higher degree polynomial. */
1159 531022 : class loop *def_loop = loop_containing_stmt (def);
1160 531022 : if (def_loop == loop)
1161 : return t_false;
1162 :
1163 : /* Inner loop. */
1164 315224 : if (flow_loop_nested_p (loop, def_loop))
1165 288816 : return follow_ssa_edge_inner_loop_phi (phi, evolution_of_loop,
1166 288816 : limit + 1);
1167 :
1168 : /* Outer loop. */
1169 : return t_false;
1170 : }
1171 :
1172 : /* At this level of abstraction, the program is just a set
1173 : of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1174 : other def to be handled. */
1175 12024457 : if (!is_gimple_assign (def))
1176 : return t_false;
1177 :
1178 11911311 : code = gimple_assign_rhs_code (def);
1179 11911311 : switch (get_gimple_rhs_class (code))
1180 : {
1181 10294169 : case GIMPLE_BINARY_RHS:
1182 10294169 : rhs0 = gimple_assign_rhs1 (def);
1183 10294169 : rhs1 = gimple_assign_rhs2 (def);
1184 10294169 : break;
1185 1584915 : case GIMPLE_UNARY_RHS:
1186 1584915 : case GIMPLE_SINGLE_RHS:
1187 1584915 : rhs0 = gimple_assign_rhs1 (def);
1188 1584915 : break;
1189 : default:
1190 : return t_false;
1191 : }
1192 11879084 : type = TREE_TYPE (gimple_assign_lhs (def));
1193 11879084 : at_stmt = def;
1194 : }
1195 : else
1196 : {
1197 189422 : code = TREE_CODE (expr);
1198 189422 : type = TREE_TYPE (expr);
1199 : /* Via follow_ssa_edge_inner_loop_phi we arrive here with the
1200 : GENERIC scalar evolution of the inner loop. */
1201 189422 : switch (code)
1202 : {
1203 11422 : CASE_CONVERT:
1204 11422 : rhs0 = TREE_OPERAND (expr, 0);
1205 11422 : break;
1206 25817 : case POINTER_PLUS_EXPR:
1207 25817 : case PLUS_EXPR:
1208 25817 : case MINUS_EXPR:
1209 25817 : rhs0 = TREE_OPERAND (expr, 0);
1210 25817 : rhs1 = TREE_OPERAND (expr, 1);
1211 25817 : STRIP_USELESS_TYPE_CONVERSION (rhs0);
1212 25817 : STRIP_USELESS_TYPE_CONVERSION (rhs1);
1213 25817 : break;
1214 : default:
1215 : rhs0 = expr;
1216 : }
1217 : }
1218 :
1219 12068506 : switch (code)
1220 : {
1221 365697 : CASE_CONVERT:
1222 365697 : {
1223 : /* This assignment is under the form "a_1 = (cast) rhs. We cannot
1224 : validate any precision altering conversion during the SCC
1225 : analysis, so don't even try. */
1226 365697 : if (!tree_nop_conversion_p (type, TREE_TYPE (rhs0)))
1227 : return t_false;
1228 241675 : t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
1229 : evolution_of_loop, limit);
1230 241675 : if (res == t_true)
1231 93210 : *evolution_of_loop = chrec_convert (type, *evolution_of_loop,
1232 : at_stmt);
1233 : return res;
1234 : }
1235 :
1236 : case INTEGER_CST:
1237 : /* This assignment is under the form "a_1 = 7". */
1238 : return t_false;
1239 :
1240 2174 : case ADDR_EXPR:
1241 2174 : {
1242 : /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1243 2174 : if (TREE_CODE (TREE_OPERAND (rhs0, 0)) != MEM_REF)
1244 : return t_false;
1245 1 : tree mem = TREE_OPERAND (rhs0, 0);
1246 1 : rhs0 = TREE_OPERAND (mem, 0);
1247 1 : rhs1 = TREE_OPERAND (mem, 1);
1248 1 : code = POINTER_PLUS_EXPR;
1249 : }
1250 : /* Fallthru. */
1251 8631280 : case POINTER_PLUS_EXPR:
1252 8631280 : case PLUS_EXPR:
1253 : /* This case is under the form "rhs0 +- rhs1". */
1254 8631280 : if (TREE_CODE (rhs0) == SSA_NAME && TREE_CODE (rhs1) != SSA_NAME)
1255 : {
1256 : /* Match an assignment under the form:
1257 : "a = b +- ...". */
1258 7522990 : t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
1259 : evolution_of_loop, limit);
1260 7522990 : if (res == t_true)
1261 7307454 : *evolution_of_loop = add_to_evolution
1262 7307454 : (chrec_convert (type, *evolution_of_loop, at_stmt),
1263 : rhs1, at_stmt);
1264 : return res;
1265 : }
1266 : /* Else search for the SCC in both rhs0 and rhs1. */
1267 1108290 : return follow_ssa_edge_binary (at_stmt, type, rhs0, code, rhs1,
1268 1108290 : evolution_of_loop, limit);
1269 :
1270 :
1271 878810 : case MINUS_EXPR:
1272 : /* This case is under the form "rhs0 - rhs1". */
1273 878810 : if (TREE_CODE (rhs0) == SSA_NAME)
1274 : {
1275 : /* Match an assignment under the form:
1276 : "a = b +- ...". */
1277 872367 : t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
1278 : evolution_of_loop, limit);
1279 872367 : if (res != t_true)
1280 : return res;
1281 : /* We have to avoid negating INT_MIN given that a) invokes UB,
1282 : b) results in a wrong scev_direction. See PR126171. */
1283 1652074 : if (INTEGRAL_TYPE_P (type)
1284 821021 : && TYPE_OVERFLOW_UNDEFINED (type)
1285 903498 : && !expr_not_equal_to (rhs1,
1286 903498 : wi::to_wide (TYPE_MIN_VALUE (type))))
1287 : {
1288 46891 : tree utype = unsigned_type_for (type);
1289 46891 : tree to_add = chrec_convert_rhs (utype, rhs1);
1290 46891 : to_add = chrec_fold_multiply (utype, to_add,
1291 : build_int_cst_type (utype, -1));
1292 46891 : *evolution_of_loop
1293 46891 : = chrec_convert (utype, *evolution_of_loop, at_stmt);
1294 46891 : *evolution_of_loop = add_to_evolution (*evolution_of_loop,
1295 : to_add, at_stmt);
1296 46891 : *evolution_of_loop
1297 46891 : = chrec_convert (type, *evolution_of_loop, at_stmt);
1298 : }
1299 : else
1300 : {
1301 779146 : tree to_add = chrec_fold_multiply (type, rhs1,
1302 : build_minus_one_cst (type));
1303 779146 : *evolution_of_loop
1304 779146 : = add_to_evolution (chrec_convert (type, *evolution_of_loop,
1305 : at_stmt),
1306 : to_add, at_stmt);
1307 : }
1308 826037 : return res;
1309 : }
1310 : /* There is nothing to do. */
1311 : return t_false;
1312 :
1313 : default:
1314 : return t_false;
1315 : }
1316 : }
1317 :
1318 :
1319 : /* This section selects the loops that will be good candidates for the
1320 : scalar evolution analysis. For the moment, greedily select all the
1321 : loop nests we could analyze. */
1322 :
1323 : /* For a loop with a single exit edge, return the COND_EXPR that
1324 : guards the exit edge. If the expression is too difficult to
1325 : analyze, then give up. */
1326 :
1327 : gcond *
1328 234 : get_loop_exit_condition (const class loop *loop)
1329 : {
1330 234 : return get_loop_exit_condition (single_exit (loop));
1331 : }
1332 :
1333 : /* If the statement just before the EXIT_EDGE contains a condition then
1334 : return the condition, otherwise NULL. */
1335 :
1336 : gcond *
1337 5259409 : get_loop_exit_condition (const_edge exit_edge)
1338 : {
1339 5259409 : gcond *res = NULL;
1340 :
1341 5259409 : if (dump_file && (dump_flags & TDF_SCEV))
1342 2 : fprintf (dump_file, "(get_loop_exit_condition \n ");
1343 :
1344 5259409 : if (exit_edge)
1345 10518818 : res = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
1346 :
1347 5259409 : if (dump_file && (dump_flags & TDF_SCEV))
1348 : {
1349 2 : print_gimple_stmt (dump_file, res, 0);
1350 2 : fprintf (dump_file, ")\n");
1351 : }
1352 :
1353 5259409 : return res;
1354 : }
1355 :
1356 :
1357 : /* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1358 : Handle below case and return the corresponding POLYNOMIAL_CHREC:
1359 :
1360 : # i_17 = PHI <i_13(5), 0(3)>
1361 : # _20 = PHI <_5(5), start_4(D)(3)>
1362 : ...
1363 : i_13 = i_17 + 1;
1364 : _5 = start_4(D) + i_13;
1365 :
1366 : Though variable _20 appears as a PEELED_CHREC in the form of
1367 : (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1368 :
1369 : See PR41488. */
1370 :
1371 : static tree
1372 1656090 : simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond)
1373 : {
1374 3312180 : aff_tree aff1, aff2;
1375 1656090 : tree ev, left, right, type, step_val;
1376 1656090 : hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
1377 :
1378 1656090 : ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1379 1656090 : if (ev == NULL_TREE)
1380 0 : return chrec_dont_know;
1381 :
1382 : /* Support the case where we can derive the original CHREC from the
1383 : peeled one if that's a converted other IV. This can be done
1384 : when the original unpeeled converted IV does not overflow and
1385 : has the same initial value. */
1386 1645286 : if (CONVERT_EXPR_P (ev)
1387 10804 : && TREE_CODE (init_cond) == INTEGER_CST
1388 3514 : && TREE_CODE (TREE_OPERAND (ev, 0)) == POLYNOMIAL_CHREC
1389 3250 : && (TYPE_PRECISION (TREE_TYPE (ev))
1390 3250 : > TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (ev, 0))))
1391 1659174 : && (!TYPE_UNSIGNED (TREE_TYPE (ev))
1392 3078 : || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (ev, 0)))))
1393 : {
1394 3084 : left = CHREC_LEFT (TREE_OPERAND (ev, 0));
1395 3084 : right = CHREC_RIGHT (TREE_OPERAND (ev, 0));
1396 3084 : tree left_before = chrec_fold_minus (TREE_TYPE (TREE_OPERAND (ev, 0)),
1397 : left, right);
1398 3084 : if (TREE_CODE (left_before) == INTEGER_CST
1399 3083 : && wi::to_widest (init_cond) == wi::to_widest (left_before)
1400 6167 : && !scev_probably_wraps_p (NULL_TREE, left_before, right, NULL,
1401 : loop, false))
1402 : {
1403 161 : tree tp = TREE_TYPE (right);
1404 :
1405 : /* We need a sign-extension to make things like
1406 : u8(6, 4, 2) => i32(6, 4, 2), instead of i32(6, 260, 514). */
1407 161 : if (TYPE_UNSIGNED (tp))
1408 161 : right = fold_convert (signed_type_for (tp), right);
1409 :
1410 161 : return build_polynomial_chrec (loop->num, init_cond,
1411 161 : chrec_convert (TREE_TYPE (ev),
1412 : right, NULL,
1413 161 : false, NULL_TREE));
1414 : }
1415 2923 : return chrec_dont_know;
1416 : }
1417 :
1418 1653006 : if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
1419 1612089 : return chrec_dont_know;
1420 :
1421 40917 : left = CHREC_LEFT (ev);
1422 40917 : right = CHREC_RIGHT (ev);
1423 40917 : type = TREE_TYPE (left);
1424 40917 : step_val = chrec_fold_plus (type, init_cond, right);
1425 :
1426 : /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1427 : if "left" equals to "init + right". */
1428 40917 : if (operand_equal_p (left, step_val, 0)
1429 40917 : && ((!POINTER_TYPE_P (type) && !INTEGRAL_TYPE_P (type))
1430 19038 : || TYPE_OVERFLOW_WRAPS (type)
1431 : /* When overflow in the type doesn't wrap, make sure the
1432 : resulting CHREC does not either. */
1433 3566 : || !scev_probably_wraps_p (NULL_TREE, init_cond, right, NULL,
1434 : loop, false)))
1435 : {
1436 17287 : if (dump_file && (dump_flags & TDF_SCEV))
1437 1 : fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1438 :
1439 17287 : return build_polynomial_chrec (loop->num, init_cond, right);
1440 : }
1441 :
1442 : /* The affine code only deals with pointer and integer types. */
1443 23630 : if (!POINTER_TYPE_P (type)
1444 17872 : && !INTEGRAL_TYPE_P (type))
1445 13 : return chrec_dont_know;
1446 :
1447 : /* Try harder to check if they are equal. */
1448 23617 : tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1449 23617 : tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1450 23617 : free_affine_expand_cache (&peeled_chrec_map);
1451 23617 : aff_combination_scale (&aff2, -1);
1452 23617 : aff_combination_add (&aff1, &aff2);
1453 :
1454 : /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1455 : if "left" equals to "init + right". */
1456 23617 : if (aff_combination_zero_p (&aff1)
1457 23617 : && ((!POINTER_TYPE_P (type) && !INTEGRAL_TYPE_P (type))
1458 15980 : || TYPE_OVERFLOW_WRAPS (type)
1459 : /* When overflow in the type doesn't wrap, make sure the
1460 : resulting CHREC does not either. */
1461 11627 : || !scev_probably_wraps_p (NULL_TREE, init_cond, right, NULL,
1462 : loop, false)))
1463 : {
1464 4394 : if (dump_file && (dump_flags & TDF_SCEV))
1465 1 : fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1466 :
1467 4394 : return build_polynomial_chrec (loop->num, init_cond, right);
1468 : }
1469 19223 : return chrec_dont_know;
1470 1656090 : }
1471 :
1472 : /* Given a LOOP_PHI_NODE, this function determines the evolution
1473 : function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1474 :
1475 : static tree
1476 11234254 : analyze_evolution_in_loop (gphi *loop_phi_node,
1477 : tree init_cond)
1478 : {
1479 11234254 : int i, n = gimple_phi_num_args (loop_phi_node);
1480 11234254 : tree evolution_function = chrec_not_analyzed_yet;
1481 11234254 : class loop *loop = loop_containing_stmt (loop_phi_node);
1482 11234254 : basic_block bb;
1483 11234254 : static bool simplify_peeled_chrec_p = true;
1484 :
1485 11234254 : if (dump_file && (dump_flags & TDF_SCEV))
1486 : {
1487 3 : fprintf (dump_file, "(analyze_evolution_in_loop \n");
1488 3 : fprintf (dump_file, " (loop_phi_node = ");
1489 3 : print_gimple_stmt (dump_file, loop_phi_node, 0);
1490 3 : fprintf (dump_file, ")\n");
1491 : }
1492 :
1493 29572674 : for (i = 0; i < n; i++)
1494 : {
1495 21133211 : tree arg = PHI_ARG_DEF (loop_phi_node, i);
1496 21133211 : tree ev_fn = chrec_dont_know;
1497 21133211 : t_bool res;
1498 :
1499 : /* Select the edges that enter the loop body. */
1500 21133211 : bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1501 21133211 : if (!flow_bb_inside_loop_p (loop, bb))
1502 9898957 : continue;
1503 :
1504 11234254 : if (TREE_CODE (arg) == SSA_NAME)
1505 : {
1506 11126120 : bool val = false;
1507 :
1508 : /* Pass in the initial condition to the follow edge function. */
1509 11126120 : scev_dfs dfs (loop, loop_phi_node, init_cond);
1510 11126120 : res = dfs.get_ev (&ev_fn, arg);
1511 :
1512 : /* If ev_fn has no evolution in the inner loop, and the
1513 : init_cond is not equal to ev_fn, then we have an
1514 : ambiguity between two possible values, as we cannot know
1515 : the number of iterations at this point. */
1516 11126120 : if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1517 2701720 : && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1518 11126120 : && !operand_equal_p (init_cond, ev_fn, 0))
1519 0 : ev_fn = chrec_dont_know;
1520 : }
1521 : else
1522 : res = t_false;
1523 :
1524 : /* When it is impossible to go back on the same
1525 : loop_phi_node by following the ssa edges, the
1526 : evolution is represented by a peeled chrec, i.e. the
1527 : first iteration, EV_FN has the value INIT_COND, then
1528 : all the other iterations it has the value of ARG.
1529 : For the moment, PEELED_CHREC nodes are not built. */
1530 11126120 : if (res != t_true)
1531 : {
1532 2440921 : ev_fn = chrec_dont_know;
1533 : /* Try to recognize POLYNOMIAL_CHREC which appears in
1534 : the form of PEELED_CHREC, but guard the process with
1535 : a bool variable to keep the analyzer from infinite
1536 : recurrence for real PEELED_RECs. */
1537 2440921 : if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1538 : {
1539 1656090 : simplify_peeled_chrec_p = false;
1540 1656090 : ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1541 1656090 : simplify_peeled_chrec_p = true;
1542 : }
1543 : }
1544 :
1545 : /* When there are multiple back edges of the loop (which in fact never
1546 : happens currently, but nevertheless), merge their evolutions. */
1547 11234254 : evolution_function = chrec_merge (evolution_function, ev_fn);
1548 :
1549 11234254 : if (evolution_function == chrec_dont_know)
1550 : break;
1551 : }
1552 :
1553 11234254 : if (dump_file && (dump_flags & TDF_SCEV))
1554 : {
1555 3 : fprintf (dump_file, " (evolution_function = ");
1556 3 : print_generic_expr (dump_file, evolution_function);
1557 3 : fprintf (dump_file, "))\n");
1558 : }
1559 :
1560 11234254 : return evolution_function;
1561 : }
1562 :
1563 : /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1564 : or degenerate phi's). If so, returns the constant; else, returns VAR. */
1565 :
1566 : static tree
1567 23119197 : follow_copies_to_constant (tree var)
1568 : {
1569 23119197 : tree res = var;
1570 23119197 : while (TREE_CODE (res) == SSA_NAME
1571 : /* We face not updated SSA form in multiple places and this walk
1572 : may end up in sibling loops so we have to guard it. */
1573 27960303 : && !name_registered_for_update_p (res))
1574 : {
1575 16375213 : gimple *def = SSA_NAME_DEF_STMT (res);
1576 16375213 : if (gphi *phi = dyn_cast <gphi *> (def))
1577 : {
1578 4112299 : if (tree rhs = degenerate_phi_result (phi))
1579 : res = rhs;
1580 : else
1581 : break;
1582 : }
1583 12262914 : else if (gimple_assign_single_p (def))
1584 : /* Will exit loop if not an SSA_NAME. */
1585 4592292 : res = gimple_assign_rhs1 (def);
1586 : else
1587 : break;
1588 : }
1589 23119197 : if (CONSTANT_CLASS_P (res))
1590 6847658 : return res;
1591 : return var;
1592 : }
1593 :
1594 : /* Given a loop-phi-node, return the initial conditions of the
1595 : variable on entry of the loop. When the CCP has propagated
1596 : constants into the loop-phi-node, the initial condition is
1597 : instantiated, otherwise the initial condition is kept symbolic.
1598 : This analyzer does not analyze the evolution outside the current
1599 : loop, and leaves this task to the on-demand tree reconstructor. */
1600 :
1601 : static tree
1602 11234254 : analyze_initial_condition (gphi *loop_phi_node)
1603 : {
1604 11234254 : int i, n;
1605 11234254 : tree init_cond = chrec_not_analyzed_yet;
1606 11234254 : class loop *loop = loop_containing_stmt (loop_phi_node);
1607 :
1608 11234254 : if (dump_file && (dump_flags & TDF_SCEV))
1609 : {
1610 3 : fprintf (dump_file, "(analyze_initial_condition \n");
1611 3 : fprintf (dump_file, " (loop_phi_node = \n");
1612 3 : print_gimple_stmt (dump_file, loop_phi_node, 0);
1613 3 : fprintf (dump_file, ")\n");
1614 : }
1615 :
1616 11234254 : n = gimple_phi_num_args (loop_phi_node);
1617 33702762 : for (i = 0; i < n; i++)
1618 : {
1619 22468508 : tree branch = PHI_ARG_DEF (loop_phi_node, i);
1620 22468508 : basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1621 :
1622 : /* When the branch is oriented to the loop's body, it does
1623 : not contribute to the initial condition. */
1624 22468508 : if (flow_bb_inside_loop_p (loop, bb))
1625 11234254 : continue;
1626 :
1627 11234254 : if (init_cond == chrec_not_analyzed_yet)
1628 : {
1629 11234254 : init_cond = branch;
1630 11234254 : continue;
1631 : }
1632 :
1633 0 : if (TREE_CODE (branch) == SSA_NAME)
1634 : {
1635 0 : init_cond = chrec_dont_know;
1636 0 : break;
1637 : }
1638 :
1639 0 : init_cond = chrec_merge (init_cond, branch);
1640 : }
1641 :
1642 : /* Ooops -- a loop without an entry??? */
1643 11234254 : if (init_cond == chrec_not_analyzed_yet)
1644 0 : init_cond = chrec_dont_know;
1645 :
1646 : /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1647 : to not miss important early loop unrollings. */
1648 11234254 : init_cond = follow_copies_to_constant (init_cond);
1649 :
1650 11234254 : if (dump_file && (dump_flags & TDF_SCEV))
1651 : {
1652 3 : fprintf (dump_file, " (init_cond = ");
1653 3 : print_generic_expr (dump_file, init_cond);
1654 3 : fprintf (dump_file, "))\n");
1655 : }
1656 :
1657 11234254 : return init_cond;
1658 : }
1659 :
1660 : /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1661 :
1662 : static tree
1663 11234254 : interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
1664 : {
1665 11234254 : class loop *phi_loop = loop_containing_stmt (loop_phi_node);
1666 11234254 : tree init_cond;
1667 :
1668 11234254 : gcc_assert (phi_loop == loop);
1669 :
1670 : /* Otherwise really interpret the loop phi. */
1671 11234254 : init_cond = analyze_initial_condition (loop_phi_node);
1672 11234254 : return analyze_evolution_in_loop (loop_phi_node, init_cond);
1673 : }
1674 :
1675 : /* This function merges the branches of a condition-phi-node,
1676 : contained in the outermost loop, and whose arguments are already
1677 : analyzed. */
1678 :
1679 : static tree
1680 2727443 : interpret_condition_phi (class loop *loop, gphi *condition_phi)
1681 : {
1682 2727443 : int i, n = gimple_phi_num_args (condition_phi);
1683 2727443 : tree res = chrec_not_analyzed_yet;
1684 :
1685 5752999 : for (i = 0; i < n; i++)
1686 : {
1687 5219521 : tree branch_chrec;
1688 :
1689 5219521 : if (backedge_phi_arg_p (condition_phi, i))
1690 : {
1691 49075 : res = chrec_dont_know;
1692 49075 : break;
1693 : }
1694 :
1695 5170446 : branch_chrec = analyze_scalar_evolution
1696 5170446 : (loop, PHI_ARG_DEF (condition_phi, i));
1697 :
1698 5170446 : res = chrec_merge (res, branch_chrec);
1699 5170446 : if (res == chrec_dont_know)
1700 : break;
1701 : }
1702 :
1703 2727443 : return res;
1704 : }
1705 :
1706 : /* Interpret the operation RHS1 OP RHS2. If we didn't
1707 : analyze this node before, follow the definitions until ending
1708 : either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1709 : return path, this function propagates evolutions (ala constant copy
1710 : propagation). OPND1 is not a GIMPLE expression because we could
1711 : analyze the effect of an inner loop: see interpret_loop_phi. */
1712 :
1713 : static tree
1714 45817938 : interpret_rhs_expr (class loop *loop, gimple *at_stmt,
1715 : tree type, tree rhs1, enum tree_code code, tree rhs2)
1716 : {
1717 45817938 : tree res, chrec1, chrec2, ctype;
1718 45817938 : gimple *def;
1719 :
1720 45817938 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1721 : {
1722 11145768 : if (is_gimple_min_invariant (rhs1))
1723 2468838 : return chrec_convert (type, rhs1, at_stmt);
1724 :
1725 8676930 : if (code == SSA_NAME)
1726 118251 : return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1727 118251 : at_stmt);
1728 : }
1729 :
1730 43230849 : switch (code)
1731 : {
1732 352522 : case ADDR_EXPR:
1733 352522 : if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1734 352522 : || handled_component_p (TREE_OPERAND (rhs1, 0)))
1735 : {
1736 352412 : machine_mode mode;
1737 352412 : poly_int64 bitsize, bitpos;
1738 352412 : int unsignedp, reversep;
1739 352412 : int volatilep = 0;
1740 352412 : tree base, offset;
1741 352412 : tree chrec3;
1742 352412 : tree unitpos;
1743 :
1744 352412 : base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1745 : &bitsize, &bitpos, &offset, &mode,
1746 : &unsignedp, &reversep, &volatilep);
1747 :
1748 352412 : if (TREE_CODE (base) == MEM_REF)
1749 : {
1750 270372 : rhs2 = TREE_OPERAND (base, 1);
1751 270372 : rhs1 = TREE_OPERAND (base, 0);
1752 :
1753 270372 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1754 270372 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1755 270372 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1756 270372 : chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1757 270372 : chrec1 = instantiate_parameters (loop, chrec1);
1758 270372 : chrec2 = instantiate_parameters (loop, chrec2);
1759 270372 : res = chrec_fold_plus (type, chrec1, chrec2);
1760 : }
1761 : else
1762 : {
1763 82040 : chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1764 82040 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1765 82040 : res = chrec1;
1766 : }
1767 :
1768 352412 : if (offset != NULL_TREE)
1769 : {
1770 154470 : chrec2 = analyze_scalar_evolution (loop, offset);
1771 154470 : chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1772 154470 : chrec2 = instantiate_parameters (loop, chrec2);
1773 154470 : res = chrec_fold_plus (type, res, chrec2);
1774 : }
1775 :
1776 352412 : if (maybe_ne (bitpos, 0))
1777 : {
1778 130886 : unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
1779 130886 : chrec3 = analyze_scalar_evolution (loop, unitpos);
1780 130886 : chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1781 130886 : chrec3 = instantiate_parameters (loop, chrec3);
1782 130886 : res = chrec_fold_plus (type, res, chrec3);
1783 : }
1784 : }
1785 : else
1786 110 : res = chrec_dont_know;
1787 : break;
1788 :
1789 3479756 : case POINTER_PLUS_EXPR:
1790 3479756 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1791 3479756 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1792 3479756 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1793 3479756 : chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1794 3479756 : chrec1 = instantiate_parameters (loop, chrec1);
1795 3479756 : chrec2 = instantiate_parameters (loop, chrec2);
1796 3479756 : res = chrec_fold_plus (type, chrec1, chrec2);
1797 3479756 : break;
1798 :
1799 141443 : case POINTER_DIFF_EXPR:
1800 141443 : {
1801 141443 : tree utype = unsigned_type_for (type);
1802 141443 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1803 141443 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1804 141443 : chrec1 = chrec_convert (utype, chrec1, at_stmt);
1805 141443 : chrec2 = chrec_convert (utype, chrec2, at_stmt);
1806 141443 : chrec1 = instantiate_parameters (loop, chrec1);
1807 141443 : chrec2 = instantiate_parameters (loop, chrec2);
1808 141443 : res = chrec_fold_minus (utype, chrec1, chrec2);
1809 141443 : res = chrec_convert (type, res, at_stmt);
1810 141443 : break;
1811 : }
1812 :
1813 11999422 : case PLUS_EXPR:
1814 11999422 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1815 11999422 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1816 11999422 : ctype = type;
1817 : /* When the stmt is conditionally executed re-write the CHREC
1818 : into a form that has well-defined behavior on overflow. */
1819 11999422 : if (at_stmt
1820 10808712 : && INTEGRAL_TYPE_P (type)
1821 10714731 : && ! TYPE_OVERFLOW_WRAPS (type)
1822 20165976 : && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1823 8166554 : gimple_bb (at_stmt)))
1824 756530 : ctype = unsigned_type_for (type);
1825 11999422 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1826 11999422 : chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1827 11999422 : chrec1 = instantiate_parameters (loop, chrec1);
1828 11999422 : chrec2 = instantiate_parameters (loop, chrec2);
1829 11999422 : res = chrec_fold_plus (ctype, chrec1, chrec2);
1830 11999422 : if (type != ctype)
1831 756530 : res = chrec_convert (type, res, at_stmt);
1832 : break;
1833 :
1834 1515946 : case MINUS_EXPR:
1835 1515946 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1836 1515946 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1837 1515946 : ctype = type;
1838 : /* When the stmt is conditionally executed re-write the CHREC
1839 : into a form that has well-defined behavior on overflow. */
1840 1515946 : if (at_stmt
1841 1441167 : && INTEGRAL_TYPE_P (type)
1842 1403321 : && ! TYPE_OVERFLOW_WRAPS (type)
1843 2059241 : && ! dominated_by_p (CDI_DOMINATORS,
1844 543295 : loop->latch, gimple_bb (at_stmt)))
1845 140938 : ctype = unsigned_type_for (type);
1846 1515946 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1847 1515946 : chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1848 1515946 : chrec1 = instantiate_parameters (loop, chrec1);
1849 1515946 : chrec2 = instantiate_parameters (loop, chrec2);
1850 1515946 : res = chrec_fold_minus (ctype, chrec1, chrec2);
1851 1515946 : if (type != ctype)
1852 140938 : res = chrec_convert (type, res, at_stmt);
1853 : break;
1854 :
1855 61737 : case NEGATE_EXPR:
1856 61737 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1857 61737 : ctype = type;
1858 : /* When the stmt is conditionally executed re-write the CHREC
1859 : into a form that has well-defined behavior on overflow. */
1860 61737 : if (at_stmt
1861 54552 : && INTEGRAL_TYPE_P (type)
1862 52602 : && ! TYPE_OVERFLOW_WRAPS (type)
1863 100961 : && ! dominated_by_p (CDI_DOMINATORS,
1864 39224 : loop->latch, gimple_bb (at_stmt)))
1865 5837 : ctype = unsigned_type_for (type);
1866 61737 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1867 : /* TYPE may be integer, real or complex, so use fold_convert. */
1868 61737 : chrec1 = instantiate_parameters (loop, chrec1);
1869 61737 : res = chrec_fold_multiply (ctype, chrec1,
1870 : fold_convert (ctype, integer_minus_one_node));
1871 61737 : if (type != ctype)
1872 5837 : res = chrec_convert (type, res, at_stmt);
1873 : break;
1874 :
1875 38356 : case BIT_NOT_EXPR:
1876 : /* Handle ~X as -1 - X. */
1877 38356 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1878 38356 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1879 38356 : chrec1 = instantiate_parameters (loop, chrec1);
1880 38356 : res = chrec_fold_minus (type,
1881 : fold_convert (type, integer_minus_one_node),
1882 : chrec1);
1883 38356 : break;
1884 :
1885 6171339 : case MULT_EXPR:
1886 6171339 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1887 6171339 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1888 6171339 : ctype = type;
1889 : /* When the stmt is conditionally executed re-write the CHREC
1890 : into a form that has well-defined behavior on overflow. */
1891 6171339 : if (at_stmt
1892 4211604 : && INTEGRAL_TYPE_P (type)
1893 4089864 : && ! TYPE_OVERFLOW_WRAPS (type)
1894 8021416 : && ! dominated_by_p (CDI_DOMINATORS,
1895 1850077 : loop->latch, gimple_bb (at_stmt)))
1896 189174 : ctype = unsigned_type_for (type);
1897 6171339 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1898 6171339 : chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1899 6171339 : chrec1 = instantiate_parameters (loop, chrec1);
1900 6171339 : chrec2 = instantiate_parameters (loop, chrec2);
1901 6171339 : res = chrec_fold_multiply (ctype, chrec1, chrec2);
1902 6171339 : if (type != ctype)
1903 189174 : res = chrec_convert (type, res, at_stmt);
1904 : break;
1905 :
1906 160537 : case LSHIFT_EXPR:
1907 160537 : {
1908 : /* Handle A<<B as A * (1<<B). */
1909 160537 : tree uns = unsigned_type_for (type);
1910 160537 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1911 160537 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1912 160537 : chrec1 = chrec_convert (uns, chrec1, at_stmt);
1913 160537 : chrec1 = instantiate_parameters (loop, chrec1);
1914 160537 : chrec2 = instantiate_parameters (loop, chrec2);
1915 :
1916 160537 : tree one = build_int_cst (uns, 1);
1917 160537 : chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1918 160537 : res = chrec_fold_multiply (uns, chrec1, chrec2);
1919 160537 : res = chrec_convert (type, res, at_stmt);
1920 : }
1921 160537 : break;
1922 :
1923 8792436 : CASE_CONVERT:
1924 : /* In case we have a truncation of a widened operation that in
1925 : the truncated type has undefined overflow behavior analyze
1926 : the operation done in an unsigned type of the same precision
1927 : as the final truncation. We cannot derive a scalar evolution
1928 : for the widened operation but for the truncated result. */
1929 8789623 : if (INTEGRAL_NB_TYPE_P (type)
1930 8462869 : && INTEGRAL_NB_TYPE_P (TREE_TYPE (rhs1))
1931 7818676 : && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1932 532368 : && TYPE_OVERFLOW_UNDEFINED (type)
1933 347141 : && TREE_CODE (rhs1) == SSA_NAME
1934 347005 : && (def = SSA_NAME_DEF_STMT (rhs1))
1935 347005 : && is_gimple_assign (def)
1936 197530 : && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1937 8934884 : && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1938 : {
1939 106452 : tree utype = unsigned_type_for (type);
1940 106452 : chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1941 : gimple_assign_rhs1 (def),
1942 : gimple_assign_rhs_code (def),
1943 : gimple_assign_rhs2 (def));
1944 : }
1945 : else
1946 8685984 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1947 8792436 : res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
1948 8792436 : break;
1949 :
1950 392468 : case BIT_AND_EXPR:
1951 : /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1952 : If A is SCEV and its value is in the range of representable set
1953 : of type unsigned short, the result expression is a (no-overflow)
1954 : SCEV. */
1955 392468 : res = chrec_dont_know;
1956 392468 : if (tree_fits_uhwi_p (rhs2))
1957 : {
1958 262801 : int precision;
1959 262801 : unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
1960 :
1961 262801 : val ++;
1962 : /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1963 : it's not the maximum value of a smaller type than rhs1. */
1964 262801 : if (val != 0
1965 202527 : && (precision = exact_log2 (val)) > 0
1966 465328 : && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
1967 : {
1968 202527 : tree utype = build_nonstandard_integer_type (precision, 1);
1969 :
1970 202527 : if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
1971 : {
1972 202527 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1973 202527 : chrec1 = chrec_convert (utype, chrec1, at_stmt);
1974 202527 : res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
1975 : }
1976 : }
1977 : }
1978 : break;
1979 :
1980 10124887 : default:
1981 10124887 : res = chrec_dont_know;
1982 10124887 : break;
1983 : }
1984 :
1985 : return res;
1986 : }
1987 :
1988 : /* Interpret the expression EXPR. */
1989 :
1990 : static tree
1991 9162613 : interpret_expr (class loop *loop, gimple *at_stmt, tree expr)
1992 : {
1993 9162613 : enum tree_code code;
1994 9162613 : tree type = TREE_TYPE (expr), op0, op1;
1995 :
1996 9162613 : if (automatically_generated_chrec_p (expr))
1997 : return expr;
1998 :
1999 9157532 : if (TREE_CODE (expr) == POLYNOMIAL_CHREC
2000 9156962 : || TREE_CODE (expr) == CALL_EXPR
2001 18314408 : || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
2002 : return chrec_dont_know;
2003 :
2004 9085910 : extract_ops_from_tree (expr, &code, &op0, &op1);
2005 :
2006 9085910 : return interpret_rhs_expr (loop, at_stmt, type,
2007 9085910 : op0, code, op1);
2008 : }
2009 :
2010 : /* Interpret the rhs of the assignment STMT. */
2011 :
2012 : static tree
2013 36625576 : interpret_gimple_assign (class loop *loop, gimple *stmt)
2014 : {
2015 36625576 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2016 36625576 : enum tree_code code = gimple_assign_rhs_code (stmt);
2017 :
2018 36625576 : return interpret_rhs_expr (loop, stmt, type,
2019 : gimple_assign_rhs1 (stmt), code,
2020 36625576 : gimple_assign_rhs2 (stmt));
2021 : }
2022 :
2023 :
2024 :
2025 : /* This section contains all the entry points:
2026 : - number_of_iterations_in_loop,
2027 : - analyze_scalar_evolution,
2028 : - instantiate_parameters.
2029 : */
2030 :
2031 : /* Helper recursive function. */
2032 :
2033 : static tree
2034 75907523 : analyze_scalar_evolution_1 (class loop *loop, tree var)
2035 : {
2036 75907523 : gimple *def;
2037 75907523 : basic_block bb;
2038 75907523 : class loop *def_loop;
2039 75907523 : tree res;
2040 :
2041 75907523 : if (TREE_CODE (var) != SSA_NAME)
2042 9162613 : return interpret_expr (loop, NULL, var);
2043 :
2044 66744910 : def = SSA_NAME_DEF_STMT (var);
2045 66744910 : bb = gimple_bb (def);
2046 66744910 : def_loop = bb->loop_father;
2047 :
2048 66744910 : if (!flow_bb_inside_loop_p (loop, bb))
2049 : {
2050 : /* Keep symbolic form, but look through obvious copies for constants. */
2051 11884943 : res = follow_copies_to_constant (var);
2052 11884943 : goto set_and_end;
2053 : }
2054 :
2055 54859967 : if (loop != def_loop)
2056 : {
2057 3711646 : res = analyze_scalar_evolution_1 (def_loop, var);
2058 3711646 : class loop *loop_to_skip = superloop_at_depth (def_loop,
2059 3711646 : loop_depth (loop) + 1);
2060 3711646 : res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
2061 3711646 : if (chrec_contains_symbols_defined_in_loop (res, loop->num))
2062 288797 : res = analyze_scalar_evolution_1 (loop, res);
2063 3711646 : goto set_and_end;
2064 : }
2065 :
2066 51148321 : switch (gimple_code (def))
2067 : {
2068 36625576 : case GIMPLE_ASSIGN:
2069 36625576 : res = interpret_gimple_assign (loop, def);
2070 36625576 : break;
2071 :
2072 13961697 : case GIMPLE_PHI:
2073 27923394 : if (loop_phi_node_p (def))
2074 11234254 : res = interpret_loop_phi (loop, as_a <gphi *> (def));
2075 : else
2076 2727443 : res = interpret_condition_phi (loop, as_a <gphi *> (def));
2077 : break;
2078 :
2079 561048 : default:
2080 561048 : res = chrec_dont_know;
2081 561048 : break;
2082 : }
2083 :
2084 66744910 : set_and_end:
2085 :
2086 : /* Keep the symbolic form. */
2087 66744910 : if (res == chrec_dont_know)
2088 24682469 : res = var;
2089 :
2090 66744910 : if (loop == def_loop)
2091 51148321 : set_scalar_evolution (block_before_loop (loop), var, res);
2092 :
2093 : return res;
2094 : }
2095 :
2096 : /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2097 : LOOP. LOOP is the loop in which the variable is used.
2098 :
2099 : Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2100 : pointer to the statement that uses this variable, in order to
2101 : determine the evolution function of the variable, use the following
2102 : calls:
2103 :
2104 : loop_p loop = loop_containing_stmt (stmt);
2105 : tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2106 : tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2107 : */
2108 :
2109 : tree
2110 197012234 : analyze_scalar_evolution (class loop *loop, tree var)
2111 : {
2112 197012234 : tree res;
2113 :
2114 : /* ??? Fix callers. */
2115 197012234 : if (! loop)
2116 : return var;
2117 :
2118 196820822 : if (dump_file && (dump_flags & TDF_SCEV))
2119 : {
2120 38 : fprintf (dump_file, "(analyze_scalar_evolution \n");
2121 38 : fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2122 38 : fprintf (dump_file, " (scalar = ");
2123 38 : print_generic_expr (dump_file, var);
2124 38 : fprintf (dump_file, ")\n");
2125 : }
2126 :
2127 196820822 : res = get_scalar_evolution (block_before_loop (loop), var);
2128 196820822 : if (res == chrec_not_analyzed_yet)
2129 : {
2130 : /* We'll recurse into instantiate_scev, avoid tearing down the
2131 : instantiate cache repeatedly and keep it live from here. */
2132 71907080 : bool destr = false;
2133 71907080 : if (!global_cache)
2134 : {
2135 42861775 : global_cache = new instantiate_cache_type;
2136 42861775 : destr = true;
2137 : }
2138 71907080 : res = analyze_scalar_evolution_1 (loop, var);
2139 71907080 : if (destr)
2140 : {
2141 42861775 : delete global_cache;
2142 42861775 : global_cache = NULL;
2143 : }
2144 : }
2145 :
2146 196820822 : if (dump_file && (dump_flags & TDF_SCEV))
2147 38 : fprintf (dump_file, ")\n");
2148 :
2149 : return res;
2150 : }
2151 :
2152 : /* If CHREC doesn't overflow, set the nonwrapping flag. */
2153 :
2154 10849241 : void record_nonwrapping_chrec (tree chrec)
2155 : {
2156 10849241 : CHREC_NOWRAP(chrec) = 1;
2157 :
2158 10849241 : if (dump_file && (dump_flags & TDF_SCEV))
2159 : {
2160 6 : fprintf (dump_file, "(record_nonwrapping_chrec: ");
2161 6 : print_generic_expr (dump_file, chrec);
2162 6 : fprintf (dump_file, ")\n");
2163 : }
2164 10849241 : }
2165 :
2166 : /* Return true if CHREC's nonwrapping flag is set. */
2167 :
2168 216107 : bool nonwrapping_chrec_p (tree chrec)
2169 : {
2170 216107 : if (!chrec || TREE_CODE(chrec) != POLYNOMIAL_CHREC)
2171 : return false;
2172 :
2173 216107 : return CHREC_NOWRAP(chrec);
2174 : }
2175 :
2176 : /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2177 :
2178 : static tree
2179 82040 : analyze_scalar_evolution_for_address_of (class loop *loop, tree var)
2180 : {
2181 82040 : return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2182 : }
2183 :
2184 : /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2185 : WRTO_LOOP (which should be a superloop of USE_LOOP)
2186 :
2187 : FOLDED_CASTS is set to true if resolve_mixers used
2188 : chrec_convert_aggressive (TODO -- not really, we are way too conservative
2189 : at the moment in order to keep things simple).
2190 :
2191 : To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2192 : example:
2193 :
2194 : for (i = 0; i < 100; i++) -- loop 1
2195 : {
2196 : for (j = 0; j < 100; j++) -- loop 2
2197 : {
2198 : k1 = i;
2199 : k2 = j;
2200 :
2201 : use2 (k1, k2);
2202 :
2203 : for (t = 0; t < 100; t++) -- loop 3
2204 : use3 (k1, k2);
2205 :
2206 : }
2207 : use1 (k1, k2);
2208 : }
2209 :
2210 : Both k1 and k2 are invariants in loop3, thus
2211 : analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2212 : analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2213 :
2214 : As they are invariant, it does not matter whether we consider their
2215 : usage in loop 3 or loop 2, hence
2216 : analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2217 : analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2218 : analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2219 : analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2220 :
2221 : Similarly for their evolutions with respect to loop 1. The values of K2
2222 : in the use in loop 2 vary independently on loop 1, thus we cannot express
2223 : the evolution with respect to loop 1:
2224 : analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2225 : analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2226 : analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2227 : analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2228 :
2229 : The value of k2 in the use in loop 1 is known, though:
2230 : analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2231 : analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2232 : */
2233 :
2234 : static tree
2235 50898216 : analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop,
2236 : tree version, bool *folded_casts)
2237 : {
2238 50898216 : bool val = false;
2239 50898216 : tree ev = version, tmp;
2240 :
2241 : /* We cannot just do
2242 :
2243 : tmp = analyze_scalar_evolution (use_loop, version);
2244 : ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2245 :
2246 : as resolve_mixers would query the scalar evolution with respect to
2247 : wrto_loop. For example, in the situation described in the function
2248 : comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2249 : version = k2. Then
2250 :
2251 : analyze_scalar_evolution (use_loop, version) = k2
2252 :
2253 : and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2254 : k2 in loop 1 is 100, which is a wrong result, since we are interested
2255 : in the value in loop 3.
2256 :
2257 : Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2258 : each time checking that there is no evolution in the inner loop. */
2259 :
2260 50898216 : if (folded_casts)
2261 50898216 : *folded_casts = false;
2262 53340204 : while (1)
2263 : {
2264 52119210 : tmp = analyze_scalar_evolution (use_loop, ev);
2265 52119210 : ev = resolve_mixers (use_loop, tmp, folded_casts);
2266 :
2267 52119210 : if (use_loop == wrto_loop)
2268 : return ev;
2269 :
2270 : /* If the value of the use changes in the inner loop, we cannot express
2271 : its value in the outer loop (we might try to return interval chrec,
2272 : but we do not have a user for it anyway) */
2273 4332027 : if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2274 4332027 : || !val)
2275 3111033 : return chrec_dont_know;
2276 :
2277 1220994 : use_loop = loop_outer (use_loop);
2278 : }
2279 : }
2280 :
2281 :
2282 : /* Computes a hash function for database element ELT. */
2283 :
2284 : static inline hashval_t
2285 437870 : hash_idx_scev_info (const void *elt_)
2286 : {
2287 437870 : unsigned idx = ((size_t) elt_) - 2;
2288 437870 : return scev_info_hasher::hash (&global_cache->entries[idx]);
2289 : }
2290 :
2291 : /* Compares database elements E1 and E2. */
2292 :
2293 : static inline int
2294 32434486 : eq_idx_scev_info (const void *e1, const void *e2)
2295 : {
2296 32434486 : unsigned idx1 = ((size_t) e1) - 2;
2297 32434486 : return scev_info_hasher::equal (&global_cache->entries[idx1],
2298 32434486 : (const scev_info_str *) e2);
2299 : }
2300 :
2301 : /* Returns from CACHE the slot number of the cached chrec for NAME. */
2302 :
2303 : static unsigned
2304 64138208 : get_instantiated_value_entry (instantiate_cache_type &cache,
2305 : tree name, edge instantiate_below)
2306 : {
2307 64138208 : if (!cache.map)
2308 : {
2309 29197519 : cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2310 29197519 : cache.entries.create (10);
2311 : }
2312 :
2313 64138208 : scev_info_str e;
2314 64138208 : e.name_version = SSA_NAME_VERSION (name);
2315 64138208 : e.instantiated_below = instantiate_below->dest->index;
2316 64138208 : void **slot = htab_find_slot_with_hash (cache.map, &e,
2317 : scev_info_hasher::hash (&e), INSERT);
2318 64138208 : if (!*slot)
2319 : {
2320 33044369 : e.chrec = chrec_not_analyzed_yet;
2321 33044369 : *slot = (void *)(size_t)(cache.entries.length () + 2);
2322 33044369 : cache.entries.safe_push (e);
2323 : }
2324 :
2325 64138208 : return ((size_t)*slot) - 2;
2326 : }
2327 :
2328 :
2329 : /* Return the closed_loop_phi node for VAR. If there is none, return
2330 : NULL_TREE. */
2331 :
2332 : static tree
2333 1768245 : loop_closed_phi_def (tree var)
2334 : {
2335 1768245 : class loop *loop;
2336 1768245 : edge exit;
2337 1768245 : gphi *phi;
2338 1768245 : gphi_iterator psi;
2339 :
2340 1768245 : if (var == NULL_TREE
2341 1768245 : || TREE_CODE (var) != SSA_NAME)
2342 : return NULL_TREE;
2343 :
2344 1768245 : loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2345 1768245 : exit = single_exit (loop);
2346 1768245 : if (!exit)
2347 : return NULL_TREE;
2348 :
2349 1463812 : for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2350 : {
2351 824534 : phi = psi.phi ();
2352 824534 : if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2353 219200 : return PHI_RESULT (phi);
2354 : }
2355 :
2356 : return NULL_TREE;
2357 : }
2358 :
2359 : static tree instantiate_scev_r (edge, class loop *, class loop *,
2360 : tree, bool *, int);
2361 :
2362 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2363 : and EVOLUTION_LOOP, that were left under a symbolic form.
2364 :
2365 : CHREC is an SSA_NAME to be instantiated.
2366 :
2367 : CACHE is the cache of already instantiated values.
2368 :
2369 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2370 : conversions that may wrap in signed/pointer type are folded, as long
2371 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2372 : then we don't do such fold.
2373 :
2374 : SIZE_EXPR is used for computing the size of the expression to be
2375 : instantiated, and to stop if it exceeds some limit. */
2376 :
2377 : static tree
2378 112069497 : instantiate_scev_name (edge instantiate_below,
2379 : class loop *evolution_loop, class loop *inner_loop,
2380 : tree chrec,
2381 : bool *fold_conversions,
2382 : int size_expr)
2383 : {
2384 112069497 : tree res;
2385 112069497 : class loop *def_loop;
2386 112069497 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2387 :
2388 : /* A parameter, nothing to do. */
2389 112069497 : if (!def_bb
2390 112069497 : || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
2391 : return chrec;
2392 :
2393 : /* We cache the value of instantiated variable to avoid exponential
2394 : time complexity due to reevaluations. We also store the convenient
2395 : value in the cache in order to prevent infinite recursion -- we do
2396 : not want to instantiate the SSA_NAME if it is in a mixer
2397 : structure. This is used for avoiding the instantiation of
2398 : recursively defined functions, such as:
2399 :
2400 : | a_2 -> {0, +, 1, +, a_2}_1 */
2401 :
2402 64138208 : unsigned si = get_instantiated_value_entry (*global_cache,
2403 : chrec, instantiate_below);
2404 64138208 : if (global_cache->get (si) != chrec_not_analyzed_yet)
2405 : return global_cache->get (si);
2406 :
2407 : /* On recursion return chrec_dont_know. */
2408 33044369 : global_cache->set (si, chrec_dont_know);
2409 :
2410 33044369 : def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2411 :
2412 33044369 : if (! dominated_by_p (CDI_DOMINATORS,
2413 33044369 : def_loop->header, instantiate_below->dest))
2414 : {
2415 184793 : gimple *def = SSA_NAME_DEF_STMT (chrec);
2416 184793 : if (gassign *ass = dyn_cast <gassign *> (def))
2417 : {
2418 140121 : switch (gimple_assign_rhs_class (ass))
2419 : {
2420 4186 : case GIMPLE_UNARY_RHS:
2421 4186 : {
2422 4186 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2423 : inner_loop, gimple_assign_rhs1 (ass),
2424 : fold_conversions, size_expr);
2425 4186 : if (op0 == chrec_dont_know)
2426 : return chrec_dont_know;
2427 1508 : res = fold_build1 (gimple_assign_rhs_code (ass),
2428 : TREE_TYPE (chrec), op0);
2429 1508 : break;
2430 : }
2431 50825 : case GIMPLE_BINARY_RHS:
2432 50825 : {
2433 50825 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2434 : inner_loop, gimple_assign_rhs1 (ass),
2435 : fold_conversions, size_expr);
2436 50825 : if (op0 == chrec_dont_know)
2437 : return chrec_dont_know;
2438 13054 : tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2439 : inner_loop, gimple_assign_rhs2 (ass),
2440 : fold_conversions, size_expr);
2441 6527 : if (op1 == chrec_dont_know)
2442 : return chrec_dont_know;
2443 2511 : res = fold_build2 (gimple_assign_rhs_code (ass),
2444 : TREE_TYPE (chrec), op0, op1);
2445 2511 : break;
2446 : }
2447 85110 : default:
2448 85110 : res = chrec_dont_know;
2449 : }
2450 : }
2451 : else
2452 44672 : res = chrec_dont_know;
2453 133801 : global_cache->set (si, res);
2454 133801 : return res;
2455 : }
2456 :
2457 : /* If the analysis yields a parametric chrec, instantiate the
2458 : result again. */
2459 32859576 : res = analyze_scalar_evolution (def_loop, chrec);
2460 :
2461 : /* Don't instantiate default definitions. */
2462 32859576 : if (TREE_CODE (res) == SSA_NAME
2463 32859576 : && SSA_NAME_IS_DEFAULT_DEF (res))
2464 : ;
2465 :
2466 : /* Don't instantiate loop-closed-ssa phi nodes. */
2467 32843192 : else if (TREE_CODE (res) == SSA_NAME
2468 96825533 : && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2469 31991545 : > loop_depth (def_loop))
2470 : {
2471 1787638 : if (res == chrec)
2472 1768245 : res = loop_closed_phi_def (chrec);
2473 : else
2474 : res = chrec;
2475 :
2476 : /* When there is no loop_closed_phi_def, it means that the
2477 : variable is not used after the loop: try to still compute the
2478 : value of the variable when exiting the loop. */
2479 1787638 : if (res == NULL_TREE)
2480 : {
2481 1549045 : loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2482 1549045 : res = analyze_scalar_evolution (loop, chrec);
2483 1549045 : res = compute_overall_effect_of_inner_loop (loop, res);
2484 1549045 : res = instantiate_scev_r (instantiate_below, evolution_loop,
2485 : inner_loop, res,
2486 : fold_conversions, size_expr);
2487 : }
2488 238593 : else if (dominated_by_p (CDI_DOMINATORS,
2489 238593 : gimple_bb (SSA_NAME_DEF_STMT (res)),
2490 238593 : instantiate_below->dest))
2491 238593 : res = chrec_dont_know;
2492 : }
2493 :
2494 31055554 : else if (res != chrec_dont_know)
2495 : {
2496 31055554 : if (inner_loop
2497 1168465 : && def_bb->loop_father != inner_loop
2498 31662546 : && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2499 : /* ??? We could try to compute the overall effect of the loop here. */
2500 319 : res = chrec_dont_know;
2501 : else
2502 31055235 : res = instantiate_scev_r (instantiate_below, evolution_loop,
2503 : inner_loop, res,
2504 : fold_conversions, size_expr);
2505 : }
2506 :
2507 : /* Store the correct value to the cache. */
2508 32859576 : global_cache->set (si, res);
2509 32859576 : return res;
2510 : }
2511 :
2512 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2513 : and EVOLUTION_LOOP, that were left under a symbolic form.
2514 :
2515 : CHREC is a polynomial chain of recurrence to be instantiated.
2516 :
2517 : CACHE is the cache of already instantiated values.
2518 :
2519 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2520 : conversions that may wrap in signed/pointer type are folded, as long
2521 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2522 : then we don't do such fold.
2523 :
2524 : SIZE_EXPR is used for computing the size of the expression to be
2525 : instantiated, and to stop if it exceeds some limit. */
2526 :
2527 : static tree
2528 61056175 : instantiate_scev_poly (edge instantiate_below,
2529 : class loop *evolution_loop, class loop *,
2530 : tree chrec, bool *fold_conversions, int size_expr)
2531 : {
2532 61056175 : tree op1;
2533 122112350 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2534 : get_chrec_loop (chrec),
2535 61056175 : CHREC_LEFT (chrec), fold_conversions,
2536 : size_expr);
2537 61056175 : if (op0 == chrec_dont_know)
2538 : return chrec_dont_know;
2539 :
2540 121675432 : op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2541 : get_chrec_loop (chrec),
2542 60837716 : CHREC_RIGHT (chrec), fold_conversions,
2543 : size_expr);
2544 60837716 : if (op1 == chrec_dont_know)
2545 : return chrec_dont_know;
2546 :
2547 60159240 : if (CHREC_LEFT (chrec) != op0
2548 60159240 : || CHREC_RIGHT (chrec) != op1)
2549 : {
2550 7989970 : op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2551 7989970 : chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2552 : }
2553 :
2554 : return chrec;
2555 : }
2556 :
2557 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2558 : and EVOLUTION_LOOP, that were left under a symbolic form.
2559 :
2560 : "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2561 :
2562 : CACHE is the cache of already instantiated values.
2563 :
2564 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2565 : conversions that may wrap in signed/pointer type are folded, as long
2566 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2567 : then we don't do such fold.
2568 :
2569 : SIZE_EXPR is used for computing the size of the expression to be
2570 : instantiated, and to stop if it exceeds some limit. */
2571 :
2572 : static tree
2573 24434530 : instantiate_scev_binary (edge instantiate_below,
2574 : class loop *evolution_loop, class loop *inner_loop,
2575 : tree chrec, enum tree_code code,
2576 : tree type, tree c0, tree c1,
2577 : bool *fold_conversions, int size_expr)
2578 : {
2579 24434530 : tree op1;
2580 24434530 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2581 : c0, fold_conversions, size_expr);
2582 24434530 : if (op0 == chrec_dont_know)
2583 : return chrec_dont_know;
2584 :
2585 : /* While we eventually compute the same op1 if c0 == c1 the process
2586 : of doing this is expensive so the following short-cut prevents
2587 : exponential compile-time behavior. */
2588 24095462 : if (c0 != c1)
2589 : {
2590 24075075 : op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2591 : c1, fold_conversions, size_expr);
2592 24075075 : if (op1 == chrec_dont_know)
2593 : return chrec_dont_know;
2594 : }
2595 : else
2596 : op1 = op0;
2597 :
2598 24025575 : if (c0 != op0
2599 24025575 : || c1 != op1)
2600 : {
2601 13900810 : op0 = chrec_convert (type, op0, NULL);
2602 13900810 : op1 = chrec_convert_rhs (type, op1, NULL);
2603 :
2604 13900810 : switch (code)
2605 : {
2606 8120513 : case POINTER_PLUS_EXPR:
2607 8120513 : case PLUS_EXPR:
2608 8120513 : return chrec_fold_plus (type, op0, op1);
2609 :
2610 892008 : case MINUS_EXPR:
2611 892008 : return chrec_fold_minus (type, op0, op1);
2612 :
2613 4888289 : case MULT_EXPR:
2614 4888289 : return chrec_fold_multiply (type, op0, op1);
2615 :
2616 0 : default:
2617 0 : gcc_unreachable ();
2618 : }
2619 : }
2620 :
2621 10124765 : return chrec ? chrec : fold_build2 (code, type, c0, c1);
2622 : }
2623 :
2624 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2625 : and EVOLUTION_LOOP, that were left under a symbolic form.
2626 :
2627 : "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2628 : instantiated.
2629 :
2630 : CACHE is the cache of already instantiated values.
2631 :
2632 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2633 : conversions that may wrap in signed/pointer type are folded, as long
2634 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2635 : then we don't do such fold.
2636 :
2637 : SIZE_EXPR is used for computing the size of the expression to be
2638 : instantiated, and to stop if it exceeds some limit. */
2639 :
2640 : static tree
2641 25300447 : instantiate_scev_convert (edge instantiate_below,
2642 : class loop *evolution_loop, class loop *inner_loop,
2643 : tree chrec, tree type, tree op,
2644 : bool *fold_conversions, int size_expr)
2645 : {
2646 25300447 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2647 : inner_loop, op,
2648 : fold_conversions, size_expr);
2649 :
2650 25300447 : if (op0 == chrec_dont_know)
2651 : return chrec_dont_know;
2652 :
2653 20057142 : if (fold_conversions)
2654 : {
2655 7864987 : tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2656 7864987 : if (tmp)
2657 : return tmp;
2658 :
2659 : /* If we used chrec_convert_aggressive, we can no longer assume that
2660 : signed chrecs do not overflow, as chrec_convert does, so avoid
2661 : calling it in that case. */
2662 7321903 : if (*fold_conversions)
2663 : {
2664 14041 : if (chrec && op0 == op)
2665 : return chrec;
2666 :
2667 14041 : return fold_convert (type, op0);
2668 : }
2669 : }
2670 :
2671 19500017 : return chrec_convert (type, op0, NULL);
2672 : }
2673 :
2674 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2675 : and EVOLUTION_LOOP, that were left under a symbolic form.
2676 :
2677 : CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2678 : Handle ~X as -1 - X.
2679 : Handle -X as -1 * X.
2680 :
2681 : CACHE is the cache of already instantiated values.
2682 :
2683 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2684 : conversions that may wrap in signed/pointer type are folded, as long
2685 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2686 : then we don't do such fold.
2687 :
2688 : SIZE_EXPR is used for computing the size of the expression to be
2689 : instantiated, and to stop if it exceeds some limit. */
2690 :
2691 : static tree
2692 285627 : instantiate_scev_not (edge instantiate_below,
2693 : class loop *evolution_loop, class loop *inner_loop,
2694 : tree chrec,
2695 : enum tree_code code, tree type, tree op,
2696 : bool *fold_conversions, int size_expr)
2697 : {
2698 285627 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2699 : inner_loop, op,
2700 : fold_conversions, size_expr);
2701 :
2702 285627 : if (op0 == chrec_dont_know)
2703 : return chrec_dont_know;
2704 :
2705 221073 : if (op != op0)
2706 : {
2707 155177 : op0 = chrec_convert (type, op0, NULL);
2708 :
2709 155177 : switch (code)
2710 : {
2711 2248 : case BIT_NOT_EXPR:
2712 2248 : return chrec_fold_minus
2713 2248 : (type, fold_convert (type, integer_minus_one_node), op0);
2714 :
2715 152929 : case NEGATE_EXPR:
2716 152929 : return chrec_fold_multiply
2717 152929 : (type, fold_convert (type, integer_minus_one_node), op0);
2718 :
2719 0 : default:
2720 0 : gcc_unreachable ();
2721 : }
2722 : }
2723 :
2724 65896 : return chrec ? chrec : fold_build1 (code, type, op0);
2725 : }
2726 :
2727 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2728 : and EVOLUTION_LOOP, that were left under a symbolic form.
2729 :
2730 : CHREC is the scalar evolution to instantiate.
2731 :
2732 : CACHE is the cache of already instantiated values.
2733 :
2734 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2735 : conversions that may wrap in signed/pointer type are folded, as long
2736 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2737 : then we don't do such fold.
2738 :
2739 : SIZE_EXPR is used for computing the size of the expression to be
2740 : instantiated, and to stop if it exceeds some limit. */
2741 :
2742 : static tree
2743 368614867 : instantiate_scev_r (edge instantiate_below,
2744 : class loop *evolution_loop, class loop *inner_loop,
2745 : tree chrec,
2746 : bool *fold_conversions, int size_expr)
2747 : {
2748 : /* Give up if the expression is larger than the MAX that we allow. */
2749 368614867 : if (size_expr++ > param_scev_max_expr_size)
2750 11 : return chrec_dont_know;
2751 :
2752 368614856 : if (chrec == NULL_TREE
2753 735313720 : || automatically_generated_chrec_p (chrec)
2754 735313709 : || is_gimple_min_invariant (chrec))
2755 : return chrec;
2756 :
2757 223869363 : switch (TREE_CODE (chrec))
2758 : {
2759 112069497 : case SSA_NAME:
2760 112069497 : return instantiate_scev_name (instantiate_below, evolution_loop,
2761 : inner_loop, chrec,
2762 112069497 : fold_conversions, size_expr);
2763 :
2764 61056175 : case POLYNOMIAL_CHREC:
2765 61056175 : return instantiate_scev_poly (instantiate_below, evolution_loop,
2766 : inner_loop, chrec,
2767 61056175 : fold_conversions, size_expr);
2768 :
2769 24434530 : case POINTER_PLUS_EXPR:
2770 24434530 : case PLUS_EXPR:
2771 24434530 : case MINUS_EXPR:
2772 24434530 : case MULT_EXPR:
2773 24434530 : return instantiate_scev_binary (instantiate_below, evolution_loop,
2774 : inner_loop, chrec,
2775 : TREE_CODE (chrec), chrec_type (chrec),
2776 24434530 : TREE_OPERAND (chrec, 0),
2777 24434530 : TREE_OPERAND (chrec, 1),
2778 24434530 : fold_conversions, size_expr);
2779 :
2780 25300447 : CASE_CONVERT:
2781 25300447 : return instantiate_scev_convert (instantiate_below, evolution_loop,
2782 : inner_loop, chrec,
2783 25300447 : TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2784 25300447 : fold_conversions, size_expr);
2785 :
2786 285627 : case NEGATE_EXPR:
2787 285627 : case BIT_NOT_EXPR:
2788 285627 : return instantiate_scev_not (instantiate_below, evolution_loop,
2789 : inner_loop, chrec,
2790 285627 : TREE_CODE (chrec), TREE_TYPE (chrec),
2791 285627 : TREE_OPERAND (chrec, 0),
2792 285627 : fold_conversions, size_expr);
2793 :
2794 0 : case ADDR_EXPR:
2795 0 : if (is_gimple_min_invariant (chrec))
2796 : return chrec;
2797 : /* Fallthru. */
2798 0 : case SCEV_NOT_KNOWN:
2799 0 : return chrec_dont_know;
2800 :
2801 0 : case SCEV_KNOWN:
2802 0 : return chrec_known;
2803 :
2804 723087 : default:
2805 723087 : if (CONSTANT_CLASS_P (chrec))
2806 : return chrec;
2807 723087 : return chrec_dont_know;
2808 : }
2809 : }
2810 :
2811 : /* Analyze all the parameters of the chrec that were left under a
2812 : symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2813 : recursive instantiation of parameters: a parameter is a variable
2814 : that is defined in a basic block that dominates INSTANTIATE_BELOW or
2815 : a function parameter. */
2816 :
2817 : tree
2818 87840269 : instantiate_scev (edge instantiate_below, class loop *evolution_loop,
2819 : tree chrec)
2820 : {
2821 87840269 : tree res;
2822 :
2823 87840269 : if (dump_file && (dump_flags & TDF_SCEV))
2824 : {
2825 20 : fprintf (dump_file, "(instantiate_scev \n");
2826 20 : fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
2827 20 : instantiate_below->src->index, instantiate_below->dest->index);
2828 20 : if (evolution_loop)
2829 20 : fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2830 20 : fprintf (dump_file, " (chrec = ");
2831 20 : print_generic_expr (dump_file, chrec);
2832 20 : fprintf (dump_file, ")\n");
2833 : }
2834 :
2835 87840269 : bool destr = false;
2836 87840269 : if (!global_cache)
2837 : {
2838 37217838 : global_cache = new instantiate_cache_type;
2839 37217838 : destr = true;
2840 : }
2841 :
2842 87840269 : res = instantiate_scev_r (instantiate_below, evolution_loop,
2843 : NULL, chrec, NULL, 0);
2844 :
2845 87840269 : if (destr)
2846 : {
2847 37217838 : delete global_cache;
2848 37217838 : global_cache = NULL;
2849 : }
2850 :
2851 87840269 : if (dump_file && (dump_flags & TDF_SCEV))
2852 : {
2853 20 : fprintf (dump_file, " (res = ");
2854 20 : print_generic_expr (dump_file, res);
2855 20 : fprintf (dump_file, "))\n");
2856 : }
2857 :
2858 87840269 : return res;
2859 : }
2860 :
2861 : /* Similar to instantiate_parameters, but does not introduce the
2862 : evolutions in outer loops for LOOP invariants in CHREC, and does not
2863 : care about causing overflows, as long as they do not affect value
2864 : of an expression. */
2865 :
2866 : tree
2867 52119210 : resolve_mixers (class loop *loop, tree chrec, bool *folded_casts)
2868 : {
2869 52119210 : bool destr = false;
2870 52119210 : bool fold_conversions = false;
2871 52119210 : if (!global_cache)
2872 : {
2873 51291786 : global_cache = new instantiate_cache_type;
2874 51291786 : destr = true;
2875 : }
2876 :
2877 52119210 : tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
2878 : chrec, &fold_conversions, 0);
2879 :
2880 52119210 : if (folded_casts && !*folded_casts)
2881 52119210 : *folded_casts = fold_conversions;
2882 :
2883 52119210 : if (destr)
2884 : {
2885 51291786 : delete global_cache;
2886 51291786 : global_cache = NULL;
2887 : }
2888 :
2889 52119210 : return ret;
2890 : }
2891 :
2892 : /* Entry point for the analysis of the number of iterations pass.
2893 : This function tries to safely approximate the number of iterations
2894 : the loop will run. When this property is not decidable at compile
2895 : time, the result is chrec_dont_know. Otherwise the result is a
2896 : scalar or a symbolic parameter. When the number of iterations may
2897 : be equal to zero and the property cannot be determined at compile
2898 : time, the result is a COND_EXPR that represents in a symbolic form
2899 : the conditions under which the number of iterations is not zero.
2900 :
2901 : Example of analysis: suppose that the loop has an exit condition:
2902 :
2903 : "if (b > 49) goto end_loop;"
2904 :
2905 : and that in a previous analysis we have determined that the
2906 : variable 'b' has an evolution function:
2907 :
2908 : "EF = {23, +, 5}_2".
2909 :
2910 : When we evaluate the function at the point 5, i.e. the value of the
2911 : variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2912 : and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2913 : the loop body has been executed 6 times. */
2914 :
2915 : tree
2916 10214829 : number_of_latch_executions (class loop *loop)
2917 : {
2918 10214829 : edge exit;
2919 10214829 : class tree_niter_desc niter_desc;
2920 10214829 : tree may_be_zero;
2921 10214829 : tree res;
2922 :
2923 : /* Determine whether the number of iterations in loop has already
2924 : been computed. */
2925 10214829 : res = loop->nb_iterations;
2926 10214829 : if (res)
2927 : return res;
2928 :
2929 6993482 : may_be_zero = NULL_TREE;
2930 :
2931 6993482 : if (dump_file && (dump_flags & TDF_SCEV))
2932 2 : fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2933 :
2934 6993482 : res = chrec_dont_know;
2935 6993482 : exit = single_exit (loop);
2936 :
2937 6993482 : if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2938 : {
2939 3502485 : may_be_zero = niter_desc.may_be_zero;
2940 3502485 : res = niter_desc.niter;
2941 : }
2942 :
2943 6993482 : if (res == chrec_dont_know
2944 3502485 : || !may_be_zero
2945 10495967 : || integer_zerop (may_be_zero))
2946 : ;
2947 547160 : else if (integer_nonzerop (may_be_zero))
2948 29 : res = build_int_cst (TREE_TYPE (res), 0);
2949 :
2950 547131 : else if (COMPARISON_CLASS_P (may_be_zero))
2951 547131 : res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2952 : build_int_cst (TREE_TYPE (res), 0), res);
2953 : else
2954 0 : res = chrec_dont_know;
2955 :
2956 6993482 : if (dump_file && (dump_flags & TDF_SCEV))
2957 : {
2958 2 : fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2959 2 : print_generic_expr (dump_file, res);
2960 2 : fprintf (dump_file, "))\n");
2961 : }
2962 :
2963 6993482 : loop->nb_iterations = res;
2964 6993482 : return res;
2965 10214829 : }
2966 :
2967 :
2968 : /* Counters for the stats. */
2969 :
2970 : struct chrec_stats
2971 : {
2972 : unsigned nb_chrecs;
2973 : unsigned nb_affine;
2974 : unsigned nb_affine_multivar;
2975 : unsigned nb_higher_poly;
2976 : unsigned nb_chrec_dont_know;
2977 : unsigned nb_undetermined;
2978 : };
2979 :
2980 : /* Reset the counters. */
2981 :
2982 : static inline void
2983 0 : reset_chrecs_counters (struct chrec_stats *stats)
2984 : {
2985 0 : stats->nb_chrecs = 0;
2986 0 : stats->nb_affine = 0;
2987 0 : stats->nb_affine_multivar = 0;
2988 0 : stats->nb_higher_poly = 0;
2989 0 : stats->nb_chrec_dont_know = 0;
2990 0 : stats->nb_undetermined = 0;
2991 : }
2992 :
2993 : /* Dump the contents of a CHREC_STATS structure. */
2994 :
2995 : static void
2996 0 : dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2997 : {
2998 0 : fprintf (file, "\n(\n");
2999 0 : fprintf (file, "-----------------------------------------\n");
3000 0 : fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3001 0 : fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
3002 0 : fprintf (file, "%d\tdegree greater than 2 polynomials\n",
3003 : stats->nb_higher_poly);
3004 0 : fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3005 0 : fprintf (file, "-----------------------------------------\n");
3006 0 : fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
3007 0 : fprintf (file, "%d\twith undetermined coefficients\n",
3008 : stats->nb_undetermined);
3009 0 : fprintf (file, "-----------------------------------------\n");
3010 0 : fprintf (file, "%d\tchrecs in the scev database\n",
3011 0 : (int) scalar_evolution_info->elements ());
3012 0 : fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3013 0 : fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3014 0 : fprintf (file, "-----------------------------------------\n");
3015 0 : fprintf (file, ")\n\n");
3016 0 : }
3017 :
3018 : /* Gather statistics about CHREC. */
3019 :
3020 : static void
3021 0 : gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3022 : {
3023 0 : if (dump_file && (dump_flags & TDF_STATS))
3024 : {
3025 0 : fprintf (dump_file, "(classify_chrec ");
3026 0 : print_generic_expr (dump_file, chrec);
3027 0 : fprintf (dump_file, "\n");
3028 : }
3029 :
3030 0 : stats->nb_chrecs++;
3031 :
3032 0 : if (chrec == NULL_TREE)
3033 : {
3034 0 : stats->nb_undetermined++;
3035 0 : return;
3036 : }
3037 :
3038 0 : switch (TREE_CODE (chrec))
3039 : {
3040 0 : case POLYNOMIAL_CHREC:
3041 0 : if (evolution_function_is_affine_p (chrec))
3042 : {
3043 0 : if (dump_file && (dump_flags & TDF_STATS))
3044 0 : fprintf (dump_file, " affine_univariate\n");
3045 0 : stats->nb_affine++;
3046 : }
3047 0 : else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3048 : {
3049 0 : if (dump_file && (dump_flags & TDF_STATS))
3050 0 : fprintf (dump_file, " affine_multivariate\n");
3051 0 : stats->nb_affine_multivar++;
3052 : }
3053 : else
3054 : {
3055 0 : if (dump_file && (dump_flags & TDF_STATS))
3056 0 : fprintf (dump_file, " higher_degree_polynomial\n");
3057 0 : stats->nb_higher_poly++;
3058 : }
3059 :
3060 : break;
3061 :
3062 : default:
3063 : break;
3064 : }
3065 :
3066 0 : if (chrec_contains_undetermined (chrec))
3067 : {
3068 0 : if (dump_file && (dump_flags & TDF_STATS))
3069 0 : fprintf (dump_file, " undetermined\n");
3070 0 : stats->nb_undetermined++;
3071 : }
3072 :
3073 0 : if (dump_file && (dump_flags & TDF_STATS))
3074 0 : fprintf (dump_file, ")\n");
3075 : }
3076 :
3077 : /* Classify the chrecs of the whole database. */
3078 :
3079 : void
3080 0 : gather_stats_on_scev_database (void)
3081 : {
3082 0 : struct chrec_stats stats;
3083 :
3084 0 : if (!dump_file)
3085 0 : return;
3086 :
3087 0 : reset_chrecs_counters (&stats);
3088 :
3089 0 : hash_table<scev_info_hasher>::iterator iter;
3090 0 : scev_info_str *elt;
3091 0 : FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3092 : iter)
3093 0 : gather_chrec_stats (elt->chrec, &stats);
3094 :
3095 0 : dump_chrecs_stats (dump_file, &stats);
3096 : }
3097 :
3098 :
3099 : /* Initialize the analysis of scalar evolutions for LOOPS. */
3100 :
3101 : void
3102 15804606 : scev_initialize (void)
3103 : {
3104 15804606 : gcc_assert (! scev_initialized_p ()
3105 : && loops_state_satisfies_p (cfun, LOOPS_NORMAL));
3106 :
3107 15804606 : scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3108 :
3109 57906380 : for (auto loop : loops_list (cfun, 0))
3110 10492562 : loop->nb_iterations = NULL_TREE;
3111 15804606 : }
3112 :
3113 : /* Return true if SCEV is initialized. */
3114 :
3115 : bool
3116 100119412 : scev_initialized_p (void)
3117 : {
3118 100119412 : return scalar_evolution_info != NULL;
3119 : }
3120 :
3121 : /* Cleans up the information cached by the scalar evolutions analysis
3122 : in the hash table. */
3123 :
3124 : void
3125 24598630 : scev_reset_htab (void)
3126 : {
3127 24598630 : if (!scalar_evolution_info)
3128 : return;
3129 :
3130 6305703 : scalar_evolution_info->empty ();
3131 : }
3132 :
3133 : /* Cleans up the information cached by the scalar evolutions analysis
3134 : in the hash table and in the loop->nb_iterations. */
3135 :
3136 : void
3137 13228817 : scev_reset (void)
3138 : {
3139 13228817 : scev_reset_htab ();
3140 :
3141 64664034 : for (auto loop : loops_list (cfun, 0))
3142 24977583 : loop->nb_iterations = NULL_TREE;
3143 13228817 : }
3144 :
3145 : /* Return true if the IV calculation in TYPE can overflow based on the knowledge
3146 : of the upper bound on the number of iterations of LOOP, the BASE and STEP
3147 : of IV.
3148 :
3149 : We do not use information whether TYPE can overflow so it is safe to
3150 : use this test even for derived IVs not computed every iteration or
3151 : hypothetical IVs to be inserted into code. */
3152 :
3153 : bool
3154 15347587 : iv_can_overflow_p (class loop *loop, tree type, tree base, tree step)
3155 : {
3156 15347587 : widest_int nit;
3157 15347587 : wide_int base_min, base_max, step_min, step_max, type_min, type_max;
3158 15347587 : signop sgn = TYPE_SIGN (type);
3159 15347587 : int_range_max r;
3160 :
3161 15347587 : if (integer_zerop (step))
3162 : return false;
3163 :
3164 30691663 : if (!INTEGRAL_TYPE_P (TREE_TYPE (base))
3165 28502026 : || !get_range_query (cfun)->range_of_expr (r, base)
3166 14251013 : || r.varying_p ()
3167 27968868 : || r.undefined_p ())
3168 : return true;
3169 :
3170 12619060 : base_min = r.lower_bound ();
3171 12619060 : base_max = r.upper_bound ();
3172 :
3173 25234722 : if (!INTEGRAL_TYPE_P (TREE_TYPE (step))
3174 25238120 : || !get_range_query (cfun)->range_of_expr (r, step)
3175 12619060 : || r.varying_p ()
3176 25159263 : || r.undefined_p ())
3177 : return true;
3178 :
3179 12540203 : step_min = r.lower_bound ();
3180 12540203 : step_max = r.upper_bound ();
3181 :
3182 12540203 : if (!get_max_loop_iterations (loop, &nit))
3183 : return true;
3184 :
3185 11865371 : type_min = wi::min_value (type);
3186 11865371 : type_max = wi::max_value (type);
3187 :
3188 : /* Just sanity check that we don't see values out of the range of the type.
3189 : In this case the arithmetics below would overflow. */
3190 11865371 : gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
3191 : && wi::le_p (base_max, type_max, sgn));
3192 :
3193 : /* Account the possible increment in the last ieration. */
3194 11865371 : wi::overflow_type overflow = wi::OVF_NONE;
3195 11865371 : nit = wi::add (nit, 1, SIGNED, &overflow);
3196 11865371 : if (overflow)
3197 : return true;
3198 :
3199 : /* NIT is typeless and can exceed the precision of the type. In this case
3200 : overflow is always possible, because we know STEP is non-zero. */
3201 11865371 : if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
3202 : return true;
3203 11635580 : wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
3204 :
3205 : /* If step can be positive, check that nit*step <= type_max-base.
3206 : This can be done by unsigned arithmetic and we only need to watch overflow
3207 : in the multiplication. The right hand side can always be represented in
3208 : the type. */
3209 11635580 : if (sgn == UNSIGNED || !wi::neg_p (step_max))
3210 : {
3211 11590512 : wi::overflow_type overflow = wi::OVF_NONE;
3212 11590512 : if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
3213 23181024 : type_max - base_max)
3214 23181024 : || overflow)
3215 5833788 : return true;
3216 : }
3217 : /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3218 5801792 : if (sgn == SIGNED && wi::neg_p (step_min))
3219 : {
3220 45355 : wi::overflow_type overflow, overflow2;
3221 45355 : overflow = overflow2 = wi::OVF_NONE;
3222 90710 : if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
3223 : nit2, UNSIGNED, &overflow),
3224 90710 : base_min - type_min)
3225 90710 : || overflow || overflow2)
3226 15089 : return true;
3227 : }
3228 :
3229 : return false;
3230 15347587 : }
3231 :
3232 : /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3233 : function tries to derive condition under which it can be simplified
3234 : into "{(type)inner_base, (type)inner_step}_loop". The condition is
3235 : the maximum number that inner iv can iterate. */
3236 :
3237 : static tree
3238 38887 : derive_simple_iv_with_niters (tree ev, tree *niters)
3239 : {
3240 38887 : if (!CONVERT_EXPR_P (ev))
3241 : return ev;
3242 :
3243 38887 : tree inner_ev = TREE_OPERAND (ev, 0);
3244 38887 : if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
3245 : return ev;
3246 :
3247 38887 : tree init = CHREC_LEFT (inner_ev);
3248 38887 : tree step = CHREC_RIGHT (inner_ev);
3249 38887 : if (TREE_CODE (init) != INTEGER_CST
3250 38887 : || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3251 : return ev;
3252 :
3253 30484 : tree type = TREE_TYPE (ev);
3254 30484 : tree inner_type = TREE_TYPE (inner_ev);
3255 30484 : if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
3256 : return ev;
3257 :
3258 : /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3259 : folded only if inner iv won't overflow. We compute the maximum
3260 : number the inner iv can iterate before overflowing and return the
3261 : simplified affine iv. */
3262 30484 : tree delta;
3263 30484 : init = fold_convert (type, init);
3264 30484 : step = fold_convert (type, step);
3265 30484 : ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
3266 30484 : if (tree_int_cst_sign_bit (step))
3267 : {
3268 0 : tree bound = lower_bound_in_type (inner_type, inner_type);
3269 0 : delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
3270 0 : step = fold_build1 (NEGATE_EXPR, type, step);
3271 : }
3272 : else
3273 : {
3274 30484 : tree bound = upper_bound_in_type (inner_type, inner_type);
3275 30484 : delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
3276 : }
3277 30484 : *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
3278 30484 : return ev;
3279 : }
3280 :
3281 : /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3282 : respect to WRTO_LOOP and returns its base and step in IV if possible
3283 : (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3284 : and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3285 : invariant in LOOP. Otherwise we require it to be an integer constant.
3286 :
3287 : IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3288 : because it is computed in signed arithmetics). Consequently, adding an
3289 : induction variable
3290 :
3291 : for (i = IV->base; ; i += IV->step)
3292 :
3293 : is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3294 : false for the type of the induction variable, or you can prove that i does
3295 : not wrap by some other argument. Otherwise, this might introduce undefined
3296 : behavior, and
3297 :
3298 : i = iv->base;
3299 : for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3300 :
3301 : must be used instead.
3302 :
3303 : When IV_NITERS is not NULL, this function also checks case in which OP
3304 : is a conversion of an inner simple iv of below form:
3305 :
3306 : (outer_type){inner_base, inner_step}_loop.
3307 :
3308 : If type of inner iv has smaller precision than outer_type, it can't be
3309 : folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3310 : the inner iv could overflow/wrap. In this case, we derive a condition
3311 : under which the inner iv won't overflow/wrap and do the simplification.
3312 : The derived condition normally is the maximum number the inner iv can
3313 : iterate, and will be stored in IV_NITERS. This is useful in loop niter
3314 : analysis, to derive break conditions when a loop must terminate, when is
3315 : infinite. */
3316 :
3317 : bool
3318 52894937 : simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop,
3319 : tree op, affine_iv *iv, tree *iv_niters,
3320 : bool allow_nonconstant_step)
3321 : {
3322 52894937 : enum tree_code code;
3323 52894937 : tree type, ev, base, e;
3324 52894937 : wide_int extreme;
3325 52894937 : bool folded_casts;
3326 :
3327 52894937 : iv->base = NULL_TREE;
3328 52894937 : iv->step = NULL_TREE;
3329 52894937 : iv->no_overflow = false;
3330 :
3331 52894937 : type = TREE_TYPE (op);
3332 52894937 : if (!POINTER_TYPE_P (type)
3333 43566257 : && !INTEGRAL_TYPE_P (type))
3334 : return false;
3335 :
3336 50786556 : ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3337 : &folded_casts);
3338 50786556 : if (chrec_contains_undetermined (ev)
3339 50786556 : || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3340 : return false;
3341 :
3342 37679739 : if (tree_does_not_contain_chrecs (ev))
3343 : {
3344 16713473 : iv->base = ev;
3345 16713473 : tree ev_type = TREE_TYPE (ev);
3346 16713473 : if (POINTER_TYPE_P (ev_type))
3347 2728335 : ev_type = sizetype;
3348 :
3349 16713473 : iv->step = build_int_cst (ev_type, 0);
3350 16713473 : iv->no_overflow = true;
3351 16713473 : return true;
3352 : }
3353 :
3354 : /* If we can derive valid scalar evolution with assumptions. */
3355 20966266 : if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
3356 38887 : ev = derive_simple_iv_with_niters (ev, iv_niters);
3357 :
3358 20966266 : if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
3359 : return false;
3360 :
3361 20917893 : if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3362 : return false;
3363 :
3364 20917879 : iv->step = CHREC_RIGHT (ev);
3365 13439990 : if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3366 34097200 : || tree_contains_chrecs (iv->step, NULL))
3367 : return false;
3368 :
3369 20645790 : iv->base = CHREC_LEFT (ev);
3370 20645790 : if (tree_contains_chrecs (iv->base, NULL))
3371 : return false;
3372 :
3373 20645790 : iv->no_overflow = !folded_casts && nowrap_type_p (type);
3374 :
3375 20645790 : if (!iv->no_overflow
3376 20645790 : && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
3377 3907810 : iv->no_overflow = true;
3378 :
3379 : /* Try to simplify iv base:
3380 :
3381 : (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3382 : == (signed T)(unsigned T)base + step
3383 : == base + step
3384 :
3385 : If we can prove operation (base + step) doesn't overflow or underflow.
3386 : Specifically, we try to prove below conditions are satisfied:
3387 :
3388 : base <= UPPER_BOUND (type) - step ;;step > 0
3389 : base >= LOWER_BOUND (type) - step ;;step < 0
3390 :
3391 : This is done by proving the reverse conditions are false using loop's
3392 : initial conditions.
3393 :
3394 : The is necessary to make loop niter, or iv overflow analysis easier
3395 : for below example:
3396 :
3397 : int foo (int *a, signed char s, signed char l)
3398 : {
3399 : signed char i;
3400 : for (i = s; i < l; i++)
3401 : a[i] = 0;
3402 : return 0;
3403 : }
3404 :
3405 : Note variable I is firstly converted to type unsigned char, incremented,
3406 : then converted back to type signed char. */
3407 :
3408 20645790 : if (wrto_loop->num != use_loop->num)
3409 : return true;
3410 :
3411 20463123 : if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3412 : return true;
3413 :
3414 231412 : type = TREE_TYPE (iv->base);
3415 231412 : e = TREE_OPERAND (iv->base, 0);
3416 231412 : if (!tree_nop_conversion_p (type, TREE_TYPE (e))
3417 200095 : || TREE_CODE (e) != PLUS_EXPR
3418 110316 : || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3419 314946 : || !tree_int_cst_equal (iv->step,
3420 83534 : fold_convert (type, TREE_OPERAND (e, 1))))
3421 : return true;
3422 65996 : e = TREE_OPERAND (e, 0);
3423 65996 : if (!CONVERT_EXPR_P (e))
3424 : return true;
3425 35834 : base = TREE_OPERAND (e, 0);
3426 35834 : if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3427 : return true;
3428 :
3429 27192 : if (tree_int_cst_sign_bit (iv->step))
3430 : {
3431 7037 : code = LT_EXPR;
3432 7037 : extreme = wi::min_value (type);
3433 : }
3434 : else
3435 : {
3436 20155 : code = GT_EXPR;
3437 20155 : extreme = wi::max_value (type);
3438 : }
3439 27192 : wi::overflow_type overflow = wi::OVF_NONE;
3440 27192 : extreme = wi::sub (extreme, wi::to_wide (iv->step),
3441 54384 : TYPE_SIGN (type), &overflow);
3442 27192 : if (overflow)
3443 : return true;
3444 27168 : e = fold_build2 (code, boolean_type_node, base,
3445 : wide_int_to_tree (type, extreme));
3446 27168 : e = simplify_using_initial_conditions (use_loop, e);
3447 27168 : if (!integer_zerop (e))
3448 : return true;
3449 :
3450 13137 : if (POINTER_TYPE_P (TREE_TYPE (base)))
3451 : code = POINTER_PLUS_EXPR;
3452 : else
3453 : code = PLUS_EXPR;
3454 :
3455 13137 : iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3456 13137 : return true;
3457 52894937 : }
3458 :
3459 : /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3460 : affine iv unconditionally. */
3461 :
3462 : bool
3463 21459243 : simple_iv (class loop *wrto_loop, class loop *use_loop, tree op,
3464 : affine_iv *iv, bool allow_nonconstant_step)
3465 : {
3466 21459243 : return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
3467 21459243 : NULL, allow_nonconstant_step);
3468 : }
3469 :
3470 : /* Finalize the scalar evolution analysis. */
3471 :
3472 : void
3473 15804607 : scev_finalize (void)
3474 : {
3475 15804607 : if (!scalar_evolution_info)
3476 : return;
3477 15804606 : scalar_evolution_info->empty ();
3478 15804606 : scalar_evolution_info = NULL;
3479 15804606 : free_numbers_of_iterations_estimates (cfun);
3480 : }
3481 :
3482 : /* Returns true if the expression EXPR is considered to be too expensive
3483 : for scev_const_prop. Sets *COND_OVERFLOW_P to true when the
3484 : expression might contain a sub-expression that is subject to undefined
3485 : overflow behavior and conditionally evaluated. */
3486 :
3487 : static bool
3488 9772520 : expression_expensive_p (tree expr, bool *cond_overflow_p,
3489 : hash_map<tree, uint64_t> &cache, uint64_t &cost)
3490 : {
3491 9772520 : enum tree_code code;
3492 :
3493 9772520 : if (is_gimple_val (expr))
3494 : return false;
3495 :
3496 3999994 : code = TREE_CODE (expr);
3497 3999994 : if (code == TRUNC_DIV_EXPR
3498 : || code == CEIL_DIV_EXPR
3499 : || code == FLOOR_DIV_EXPR
3500 : || code == ROUND_DIV_EXPR
3501 : || code == TRUNC_MOD_EXPR
3502 : || code == CEIL_MOD_EXPR
3503 : || code == FLOOR_MOD_EXPR
3504 3999994 : || code == ROUND_MOD_EXPR
3505 3999994 : || code == EXACT_DIV_EXPR)
3506 : {
3507 : /* Division by power of two is usually cheap, so we allow it.
3508 : Forbid anything else. */
3509 51002 : if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3510 : return true;
3511 : }
3512 :
3513 3992079 : bool visited_p;
3514 3992079 : uint64_t &local_cost = cache.get_or_insert (expr, &visited_p);
3515 3992079 : if (visited_p)
3516 : {
3517 350 : uint64_t tem = cost + local_cost;
3518 350 : if (tem < cost)
3519 : return true;
3520 350 : cost = tem;
3521 350 : return false;
3522 : }
3523 3991729 : local_cost = 1;
3524 :
3525 3991729 : uint64_t op_cost = 0;
3526 3991729 : if (code == CALL_EXPR)
3527 : {
3528 148 : tree arg;
3529 148 : call_expr_arg_iterator iter;
3530 : /* Even though is_inexpensive_builtin might say true, we will get a
3531 : library call for popcount when backend does not have an instruction
3532 : to do so. We consider this to be expensive and generate
3533 : __builtin_popcount only when backend defines it. */
3534 148 : optab optab;
3535 148 : combined_fn cfn = get_call_combined_fn (expr);
3536 148 : switch (cfn)
3537 : {
3538 36 : CASE_CFN_POPCOUNT:
3539 36 : optab = popcount_optab;
3540 36 : goto bitcount_call;
3541 86 : CASE_CFN_CLZ:
3542 86 : optab = clz_optab;
3543 86 : goto bitcount_call;
3544 : CASE_CFN_CTZ:
3545 : optab = ctz_optab;
3546 148 : bitcount_call:
3547 : /* Check if opcode for popcount is available in the mode required. */
3548 148 : if (optab_handler (optab,
3549 148 : TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0))))
3550 : == CODE_FOR_nothing)
3551 : {
3552 32 : machine_mode mode;
3553 32 : mode = TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0)));
3554 32 : scalar_int_mode int_mode;
3555 :
3556 : /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
3557 : double-word popcount by emitting two single-word popcount
3558 : instructions. */
3559 32 : if (is_a <scalar_int_mode> (mode, &int_mode)
3560 34 : && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
3561 2 : && (optab_handler (optab, word_mode)
3562 : != CODE_FOR_nothing))
3563 : break;
3564 : /* If popcount is available for a wider mode, we emulate the
3565 : operation for a narrow mode by first zero-extending the value
3566 : and then computing popcount in the wider mode. Analogue for
3567 : ctz. For clz we do the same except that we additionally have
3568 : to subtract the difference of the mode precisions from the
3569 : result. */
3570 30 : if (is_a <scalar_int_mode> (mode, &int_mode))
3571 : {
3572 30 : machine_mode wider_mode_iter;
3573 149 : FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
3574 119 : if (optab_handler (optab, wider_mode_iter)
3575 : != CODE_FOR_nothing)
3576 0 : goto check_call_args;
3577 : /* Operation ctz may be emulated via clz in expand_ctz. */
3578 30 : if (optab == ctz_optab)
3579 : {
3580 0 : FOR_EACH_WIDER_MODE_FROM (wider_mode_iter, mode)
3581 0 : if (optab_handler (clz_optab, wider_mode_iter)
3582 : != CODE_FOR_nothing)
3583 0 : goto check_call_args;
3584 : }
3585 : }
3586 148 : return true;
3587 : }
3588 : break;
3589 :
3590 0 : default:
3591 0 : if (cfn == CFN_LAST
3592 0 : || !is_inexpensive_builtin (get_callee_fndecl (expr)))
3593 : return true;
3594 : break;
3595 : }
3596 :
3597 118 : check_call_args:
3598 354 : FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
3599 118 : if (expression_expensive_p (arg, cond_overflow_p, cache, op_cost))
3600 : return true;
3601 118 : *cache.get (expr) += op_cost;
3602 118 : cost += op_cost + 1;
3603 118 : return false;
3604 : }
3605 :
3606 3991581 : if (code == COND_EXPR)
3607 : {
3608 2054 : if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
3609 : cache, op_cost)
3610 2054 : || (EXPR_P (TREE_OPERAND (expr, 1))
3611 2053 : && EXPR_P (TREE_OPERAND (expr, 2)))
3612 : /* If either branch has side effects or could trap. */
3613 2046 : || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1))
3614 2046 : || generic_expr_could_trap_p (TREE_OPERAND (expr, 1))
3615 2045 : || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))
3616 2045 : || generic_expr_could_trap_p (TREE_OPERAND (expr, 0))
3617 2045 : || expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
3618 : cache, op_cost)
3619 3999 : || expression_expensive_p (TREE_OPERAND (expr, 2), cond_overflow_p,
3620 : cache, op_cost))
3621 : return true;
3622 : /* Conservatively assume there's overflow for now. */
3623 1945 : *cond_overflow_p = true;
3624 1945 : *cache.get (expr) += op_cost;
3625 1945 : cost += op_cost + 1;
3626 1945 : return false;
3627 : }
3628 :
3629 3989527 : switch (TREE_CODE_CLASS (code))
3630 : {
3631 2088144 : case tcc_binary:
3632 2088144 : case tcc_comparison:
3633 2088144 : if (expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
3634 : cache, op_cost))
3635 : return true;
3636 :
3637 : /* Fallthru. */
3638 3987108 : case tcc_unary:
3639 3987108 : if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
3640 : cache, op_cost))
3641 : return true;
3642 3966675 : *cache.get (expr) += op_cost;
3643 3966675 : cost += op_cost + 1;
3644 3966675 : return false;
3645 :
3646 : default:
3647 : return true;
3648 : }
3649 : }
3650 :
3651 : bool
3652 3691106 : expression_expensive_p (tree expr, bool *cond_overflow_p)
3653 : {
3654 3691106 : hash_map<tree, uint64_t> cache;
3655 3691106 : uint64_t expanded_size = 0;
3656 3691106 : *cond_overflow_p = false;
3657 3691106 : return (expression_expensive_p (expr, cond_overflow_p, cache, expanded_size)
3658 : /* ??? Both the explicit unsharing and gimplification of expr will
3659 : expand shared trees to multiple copies.
3660 : Guard against exponential growth by counting the visits and
3661 : comparing against the number of original nodes. Allow a tiny
3662 : bit of duplication to catch some additional optimizations. */
3663 3699202 : || expanded_size > (cache.elements () + 1));
3664 3691106 : }
3665 :
3666 : /* Match.pd function to match bitwise inductive expression.
3667 : .i.e.
3668 : _2 = 1 << _1;
3669 : _3 = ~_2;
3670 : tmp_9 = _3 & tmp_12; */
3671 : extern bool gimple_bitwise_induction_p (tree, tree *, tree (*)(tree));
3672 :
3673 : /* Return the inductive expression of bitwise operation if possible,
3674 : otherwise returns DEF. */
3675 : static tree
3676 20781 : analyze_and_compute_bitwise_induction_effect (class loop* loop,
3677 : tree phidef,
3678 : unsigned HOST_WIDE_INT niter)
3679 : {
3680 20781 : tree match_op[3],inv, bitwise_scev;
3681 20781 : tree type = TREE_TYPE (phidef);
3682 20781 : gphi* header_phi = NULL;
3683 :
3684 : /* Match things like op2(MATCH_OP[2]), op1(MATCH_OP[1]), phidef(PHIDEF)
3685 :
3686 : op2 = PHI <phidef, inv>
3687 : _1 = (int) bit_17;
3688 : _3 = 1 << _1;
3689 : op1 = ~_3;
3690 : phidef = op1 & op2; */
3691 20781 : if (!gimple_bitwise_induction_p (phidef, &match_op[0], NULL)
3692 100 : || TREE_CODE (match_op[2]) != SSA_NAME
3693 100 : || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[2])))
3694 100 : || gimple_bb (header_phi) != loop->header
3695 20881 : || gimple_phi_num_args (header_phi) != 2)
3696 : return NULL_TREE;
3697 :
3698 100 : if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
3699 : return NULL_TREE;
3700 :
3701 100 : bitwise_scev = analyze_scalar_evolution (loop, match_op[1]);
3702 100 : bitwise_scev = instantiate_parameters (loop, bitwise_scev);
3703 :
3704 : /* Make sure bits is in range of type precision. */
3705 100 : if (TREE_CODE (bitwise_scev) != POLYNOMIAL_CHREC
3706 100 : || !INTEGRAL_TYPE_P (TREE_TYPE (bitwise_scev))
3707 100 : || !tree_fits_uhwi_p (CHREC_LEFT (bitwise_scev))
3708 100 : || tree_to_uhwi (CHREC_LEFT (bitwise_scev)) >= TYPE_PRECISION (type)
3709 200 : || !tree_fits_shwi_p (CHREC_RIGHT (bitwise_scev)))
3710 : return NULL_TREE;
3711 :
3712 100 : enum bit_op_kind
3713 : {
3714 : INDUCTION_BIT_CLEAR,
3715 : INDUCTION_BIT_IOR,
3716 : INDUCTION_BIT_XOR,
3717 : INDUCTION_BIT_RESET,
3718 : INDUCTION_ZERO,
3719 : INDUCTION_ALL
3720 : };
3721 :
3722 100 : enum bit_op_kind induction_kind;
3723 100 : enum tree_code code1
3724 100 : = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (phidef));
3725 100 : enum tree_code code2
3726 100 : = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (match_op[0]));
3727 :
3728 : /* BIT_CLEAR: A &= ~(1 << bit)
3729 : BIT_RESET: A ^= (1 << bit).
3730 : BIT_IOR: A |= (1 << bit)
3731 : BIT_ZERO: A &= (1 << bit)
3732 : BIT_ALL: A |= ~(1 << bit)
3733 : BIT_XOR: A ^= ~(1 << bit).
3734 : bit is induction variable. */
3735 100 : switch (code1)
3736 : {
3737 27 : case BIT_AND_EXPR:
3738 27 : induction_kind = code2 == BIT_NOT_EXPR
3739 27 : ? INDUCTION_BIT_CLEAR
3740 : : INDUCTION_ZERO;
3741 : break;
3742 49 : case BIT_IOR_EXPR:
3743 49 : induction_kind = code2 == BIT_NOT_EXPR
3744 49 : ? INDUCTION_ALL
3745 : : INDUCTION_BIT_IOR;
3746 : break;
3747 12 : case BIT_XOR_EXPR:
3748 12 : induction_kind = code2 == BIT_NOT_EXPR
3749 12 : ? INDUCTION_BIT_XOR
3750 : : INDUCTION_BIT_RESET;
3751 : break;
3752 : /* A ^ ~(1 << bit) is equal to ~(A ^ (1 << bit)). */
3753 12 : case BIT_NOT_EXPR:
3754 12 : gcc_assert (code2 == BIT_XOR_EXPR);
3755 : induction_kind = INDUCTION_BIT_XOR;
3756 : break;
3757 0 : default:
3758 0 : gcc_unreachable ();
3759 : }
3760 :
3761 37 : if (induction_kind == INDUCTION_ZERO)
3762 12 : return build_zero_cst (type);
3763 88 : if (induction_kind == INDUCTION_ALL)
3764 12 : return build_all_ones_cst (type);
3765 :
3766 152 : wide_int bits = wi::zero (TYPE_PRECISION (type));
3767 76 : HOST_WIDE_INT bit_start = tree_to_shwi (CHREC_LEFT (bitwise_scev));
3768 76 : HOST_WIDE_INT step = tree_to_shwi (CHREC_RIGHT (bitwise_scev));
3769 76 : HOST_WIDE_INT bit_final = bit_start + step * niter;
3770 :
3771 : /* bit_start, bit_final in range of [0,TYPE_PRECISION)
3772 : implies all bits are set in range. */
3773 76 : if (bit_final >= TYPE_PRECISION (type)
3774 76 : || bit_final < 0)
3775 : return NULL_TREE;
3776 :
3777 : /* Loop tripcount should be niter + 1. */
3778 1296 : for (unsigned i = 0; i != niter + 1; i++)
3779 : {
3780 1220 : bits = wi::set_bit (bits, bit_start);
3781 1220 : bit_start += step;
3782 : }
3783 :
3784 76 : bool inverted = false;
3785 76 : switch (induction_kind)
3786 : {
3787 : case INDUCTION_BIT_CLEAR:
3788 : code1 = BIT_AND_EXPR;
3789 : inverted = true;
3790 : break;
3791 : case INDUCTION_BIT_IOR:
3792 : code1 = BIT_IOR_EXPR;
3793 : break;
3794 : case INDUCTION_BIT_RESET:
3795 : code1 = BIT_XOR_EXPR;
3796 : break;
3797 : /* A ^= ~(1 << bit) is special, when loop tripcount is even,
3798 : it's equal to A ^= bits, else A ^= ~bits. */
3799 12 : case INDUCTION_BIT_XOR:
3800 12 : code1 = BIT_XOR_EXPR;
3801 12 : if (niter % 2 == 0)
3802 : inverted = true;
3803 : break;
3804 : default:
3805 : gcc_unreachable ();
3806 : }
3807 :
3808 : if (inverted)
3809 19 : bits = wi::bit_not (bits);
3810 :
3811 76 : inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
3812 76 : return fold_build2 (code1, type, inv, wide_int_to_tree (type, bits));
3813 : }
3814 :
3815 : /* Match.pd function to match bitop with invariant expression
3816 : .i.e.
3817 : tmp_7 = _0 & _1; */
3818 : extern bool gimple_bitop_with_inv_p (tree, tree *, tree (*)(tree));
3819 :
3820 : /* Return the inductive expression of bitop with invariant if possible,
3821 : otherwise returns DEF. */
3822 : static tree
3823 69244 : analyze_and_compute_bitop_with_inv_effect (class loop* loop, tree phidef,
3824 : tree niter)
3825 : {
3826 69244 : tree match_op[2],inv;
3827 69244 : tree type = TREE_TYPE (phidef);
3828 69244 : gphi* header_phi = NULL;
3829 69244 : enum tree_code code;
3830 : /* match thing like op0 (match[0]), op1 (match[1]), phidef (PHIDEF)
3831 :
3832 : op1 = PHI <phidef, inv>
3833 : phidef = op0 & op1
3834 : if op0 is an invariant, it could change to
3835 : phidef = op0 & inv. */
3836 69244 : gimple *def;
3837 69244 : def = SSA_NAME_DEF_STMT (phidef);
3838 69244 : if (!(is_gimple_assign (def)
3839 24396 : && ((code = gimple_assign_rhs_code (def)), true)
3840 24396 : && (code == BIT_AND_EXPR || code == BIT_IOR_EXPR
3841 21923 : || code == BIT_XOR_EXPR)))
3842 : return NULL_TREE;
3843 :
3844 3231 : match_op[0] = gimple_assign_rhs1 (def);
3845 3231 : match_op[1] = gimple_assign_rhs2 (def);
3846 :
3847 3231 : if (expr_invariant_in_loop_p (loop, match_op[1]))
3848 241 : std::swap (match_op[0], match_op[1]);
3849 :
3850 3231 : if (TREE_CODE (match_op[1]) != SSA_NAME
3851 3231 : || !expr_invariant_in_loop_p (loop, match_op[0])
3852 355 : || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[1])))
3853 228 : || gimple_bb (header_phi) != loop->header
3854 3451 : || gimple_phi_num_args (header_phi) != 2)
3855 : return NULL_TREE;
3856 :
3857 220 : if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
3858 : return NULL_TREE;
3859 :
3860 215 : enum tree_code code1
3861 215 : = gimple_assign_rhs_code (def);
3862 :
3863 215 : if (code1 == BIT_XOR_EXPR)
3864 : {
3865 61 : tree niter_type = TREE_TYPE (niter);
3866 61 : tree one = build_one_cst (niter_type);
3867 61 : tree contributes = fold_build2 (BIT_XOR_EXPR, niter_type,
3868 : fold_build2 (BIT_AND_EXPR, niter_type,
3869 : niter, one),
3870 : one);
3871 : /* mask is all-ones when the invariant contributes, zero otherwise. */
3872 61 : tree mask = fold_build1 (NEGATE_EXPR, type,
3873 : fold_convert (type, contributes));
3874 61 : match_op[0] = fold_build2 (BIT_AND_EXPR, type, match_op[0], mask);
3875 : }
3876 :
3877 215 : inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
3878 215 : return fold_build2 (code1, type, inv, match_op[0]);
3879 : }
3880 :
3881 : /* Try to compute the final value of PHIDEF when PHIDEF is the result of a
3882 : loop-header PHI.
3883 :
3884 : This handles the nonzero-latch-count delayed-value form:
3885 :
3886 : y_phi = PHI <latch_arg (latch), init (preheader)>
3887 :
3888 : If the latch count is known to be nonzero, the final value is:
3889 :
3890 : latch_arg evaluated at iteration niter - 1
3891 :
3892 : Return NULL_TREE if the pattern does not apply. */
3893 : static tree
3894 42790 : compute_final_value_from_loop_phi_latch (class loop *loop,
3895 : class loop *ex_loop, gphi *header_phi, tree niter, bool* folded_casts)
3896 : {
3897 42790 : if (gimple_bb (header_phi) != loop->header
3898 45224 : || gimple_phi_num_args (header_phi) != 2)
3899 : return NULL_TREE;
3900 :
3901 : /* If niter is a symbolic value make sure it can never be zero, otherwise we
3902 : do a bad replacement. */
3903 2434 : if (!tree_expr_nonzero_p (niter))
3904 : return NULL_TREE;
3905 :
3906 1067 : tree latch_arg = PHI_ARG_DEF_FROM_EDGE (header_phi,
3907 : loop_latch_edge (loop));
3908 :
3909 1067 : tree ev = analyze_scalar_evolution_in_loop (ex_loop,
3910 : loop,
3911 : latch_arg,
3912 : folded_casts);
3913 1067 : if (ev == chrec_dont_know)
3914 : return NULL_TREE;
3915 :
3916 490 : bool invariant_p;
3917 490 : if (no_evolution_in_loop_p (ev, ex_loop->num, &invariant_p) && invariant_p)
3918 : return ev;
3919 14 : else if (TREE_CODE (ev) == POLYNOMIAL_CHREC
3920 14 : && get_chrec_loop (ev) == ex_loop)
3921 : {
3922 14 : tree niter_type = TREE_TYPE (niter);
3923 14 : tree prev_iter = fold_build2 (MINUS_EXPR,
3924 : niter_type,
3925 : niter,
3926 : build_one_cst (niter_type));
3927 :
3928 14 : tree res = chrec_apply (ex_loop->num, ev, prev_iter);
3929 14 : if (res == chrec_dont_know)
3930 : return NULL_TREE;
3931 :
3932 14 : if (chrec_contains_symbols_defined_in_loop (res, ex_loop->num))
3933 : {
3934 0 : res = instantiate_parameters (ex_loop, res);
3935 0 : if (res == chrec_dont_know)
3936 : return NULL_TREE;
3937 : }
3938 :
3939 14 : return res;
3940 : }
3941 : return NULL_TREE;
3942 : }
3943 :
3944 : /* Do final value replacement for LOOP, return true if we did anything. */
3945 :
3946 : bool
3947 696715 : final_value_replacement_loop (class loop *loop)
3948 : {
3949 : /* If we do not know exact number of iterations of the loop, we cannot
3950 : replace the final value. */
3951 696715 : edge exit = single_exit (loop);
3952 696715 : if (!exit)
3953 : return false;
3954 :
3955 463158 : class tree_niter_desc niter_desc;
3956 463158 : if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
3957 : return false;
3958 :
3959 349449 : tree niter = niter_desc.niter;
3960 349449 : if (niter == chrec_dont_know)
3961 : return false;
3962 :
3963 : /* Ensure that it is possible to insert new statements somewhere. */
3964 349449 : if (!single_pred_p (exit->dest))
3965 38868 : split_loop_exit_edge (exit);
3966 :
3967 : /* Set stmt insertion pointer. All stmts are inserted before this point. */
3968 :
3969 349449 : class loop *ex_loop
3970 698898 : = superloop_at_depth (loop,
3971 427177 : loop_depth (exit->dest->loop_father) + 1);
3972 :
3973 349449 : bool any = false;
3974 349449 : gphi_iterator psi;
3975 780867 : for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3976 : {
3977 431418 : gphi *phi = psi.phi ();
3978 431418 : tree rslt = PHI_RESULT (phi);
3979 431418 : tree phidef = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3980 431418 : tree def = phidef;
3981 862144 : if (virtual_operand_p (def))
3982 : {
3983 246765 : gsi_next (&psi);
3984 397198 : continue;
3985 : }
3986 :
3987 349921 : if (!POINTER_TYPE_P (TREE_TYPE (def))
3988 349764 : && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3989 : {
3990 74060 : gsi_next (&psi);
3991 74060 : continue;
3992 : }
3993 :
3994 110593 : bool folded_casts;
3995 110593 : def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3996 : &folded_casts);
3997 :
3998 110593 : tree bitinv_def, bit_def, phi_latch_final_value;
3999 110593 : unsigned HOST_WIDE_INT niter_num;
4000 :
4001 110593 : gphi *header_phi = TREE_CODE (phidef) == SSA_NAME
4002 110593 : ? dyn_cast<gphi*> (SSA_NAME_DEF_STMT (phidef))
4003 : : NULL;
4004 :
4005 110593 : if (def != chrec_dont_know)
4006 35120 : def = compute_overall_effect_of_inner_loop (ex_loop, def);
4007 :
4008 : /* Handle bitop with invariant induction expression.
4009 :
4010 : .i.e
4011 : for (int i =0 ;i < 32; i++)
4012 : tmp &= bit2;
4013 : if bit2 is an invariant in loop which could simple to
4014 : tmp &= bit2. */
4015 75473 : else if (integer_zerop (niter_desc.may_be_zero)
4016 75473 : && (bitinv_def
4017 69244 : = analyze_and_compute_bitop_with_inv_effect (loop,
4018 : phidef,
4019 : niter)))
4020 : def = bitinv_def;
4021 :
4022 : /* Handle bitwise induction expression.
4023 :
4024 : .i.e.
4025 : for (int i = 0; i != 64; i+=3)
4026 : res &= ~(1UL << i);
4027 :
4028 : RES can't be analyzed out by SCEV because it is not polynomially
4029 : expressible, but in fact final value of RES can be replaced by
4030 : RES & CONSTANT where CONSTANT all ones with bit {0,3,6,9,... ,63}
4031 : being cleared, similar for BIT_IOR_EXPR/BIT_XOR_EXPR. */
4032 75258 : else if (tree_fits_uhwi_p (niter)
4033 31350 : && (niter_num = tree_to_uhwi (niter)) != 0
4034 31335 : && niter_num < TYPE_PRECISION (TREE_TYPE (phidef))
4035 75258 : && (bit_def
4036 20781 : = analyze_and_compute_bitwise_induction_effect (loop,
4037 : phidef,
4038 : niter_num)))
4039 : def = bit_def;
4040 :
4041 75158 : else if (header_phi
4042 45262 : && integer_zerop (niter_desc.may_be_zero)
4043 75158 : && (phi_latch_final_value
4044 42790 : = compute_final_value_from_loop_phi_latch (loop,
4045 : ex_loop,
4046 : header_phi,
4047 : niter,
4048 : &folded_casts)))
4049 : def = phi_latch_final_value;
4050 :
4051 110593 : bool cond_overflow_p;
4052 110593 : if (!tree_does_not_contain_chrecs (def)
4053 35323 : || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
4054 : /* Moving the computation from the loop may prolong life range
4055 : of some ssa names, which may cause problems if they appear
4056 : on abnormal edges. */
4057 35323 : || contains_abnormal_ssa_name_p (def)
4058 : /* Do not emit expensive expressions. The rationale is that
4059 : when someone writes a code like
4060 :
4061 : while (n > 45) n -= 45;
4062 :
4063 : he probably knows that n is not large, and does not want it
4064 : to be turned into n %= 45. */
4065 145916 : || expression_expensive_p (def, &cond_overflow_p))
4066 : {
4067 76373 : if (dump_file && (dump_flags & TDF_DETAILS))
4068 : {
4069 60 : fprintf (dump_file, "not replacing:\n ");
4070 60 : print_gimple_stmt (dump_file, phi, 0);
4071 60 : fprintf (dump_file, "\n");
4072 : }
4073 76373 : gsi_next (&psi);
4074 76373 : continue;
4075 : }
4076 :
4077 : /* Eliminate the PHI node and replace it by a computation outside
4078 : the loop. */
4079 34220 : if (dump_file)
4080 : {
4081 148 : fprintf (dump_file, "\nfinal value replacement:\n ");
4082 148 : print_gimple_stmt (dump_file, phi, 0);
4083 148 : fprintf (dump_file, " with expr: ");
4084 148 : print_generic_expr (dump_file, def);
4085 148 : fprintf (dump_file, "\n");
4086 : }
4087 34220 : any = true;
4088 : /* ??? Here we'd like to have a unshare_expr that would assign
4089 : shared sub-trees to new temporary variables either gimplified
4090 : to a GIMPLE sequence or to a statement list (keeping this a
4091 : GENERIC interface). */
4092 34220 : def = unshare_expr (def);
4093 34220 : auto loc = gimple_phi_arg_location (phi, exit->dest_idx);
4094 :
4095 : /* Create the replacement statements. */
4096 34220 : gimple_seq stmts;
4097 34220 : def = force_gimple_operand (def, &stmts, false, NULL_TREE);
4098 :
4099 : /* Propagate constants immediately, but leave an unused initialization
4100 : around to avoid invalidating the SCEV cache. */
4101 41635 : if (CONSTANT_CLASS_P (def) && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rslt))
4102 7414 : replace_uses_by (rslt, def);
4103 :
4104 : /* Remove the old phi after the gimplification to make sure the
4105 : SSA name is defined by a statement so that fold_stmt during
4106 : the gimplification does not crash. */
4107 34220 : remove_phi_node (&psi, false);
4108 34220 : gassign *ass = gimple_build_assign (rslt, def);
4109 34220 : gimple_set_location (ass, loc);
4110 34220 : gimple_seq_add_stmt (&stmts, ass);
4111 :
4112 : /* If def's type has undefined overflow and there were folded
4113 : casts, rewrite all stmts added for def into arithmetics
4114 : with defined overflow behavior. */
4115 34220 : if ((folded_casts
4116 429 : && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
4117 726 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
4118 34649 : || cond_overflow_p)
4119 : {
4120 2211 : gimple_stmt_iterator gsi2;
4121 2211 : gsi2 = gsi_start (stmts);
4122 20414 : while (!gsi_end_p (gsi2))
4123 : {
4124 18203 : if (gimple_needing_rewrite_undefined (gsi_stmt (gsi2)))
4125 550 : rewrite_to_defined_unconditional (&gsi2);
4126 18203 : gsi_next (&gsi2);
4127 : }
4128 : }
4129 34220 : gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
4130 34220 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
4131 34220 : if (dump_file)
4132 : {
4133 148 : fprintf (dump_file, " final stmt:\n ");
4134 148 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (rslt), 0);
4135 148 : fprintf (dump_file, "\n");
4136 : }
4137 :
4138 : /* Re-fold immediate uses of the replaced def, but avoid
4139 : CFG manipulations from this function. For now only do
4140 : a single-level re-folding, not re-folding uses of
4141 : folded uses. */
4142 34220 : if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rslt))
4143 : {
4144 34219 : gimple *use_stmt;
4145 34219 : imm_use_iterator imm_iter;
4146 34219 : auto_vec<gimple *, 4> to_fold;
4147 68442 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, rslt)
4148 34223 : if (!stmt_can_throw_internal (cfun, use_stmt))
4149 34219 : to_fold.safe_push (use_stmt);
4150 : /* Delay folding until after the immediate use walk is completed
4151 : as we have an active ranger and that might walk immediate
4152 : uses of rslt again. See PR122502. */
4153 136876 : for (gimple *use_stmt : to_fold)
4154 : {
4155 34219 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
4156 34219 : if (fold_stmt (&gsi, follow_all_ssa_edges))
4157 1905 : update_stmt (gsi_stmt (gsi));
4158 : }
4159 34219 : }
4160 : }
4161 :
4162 : return any;
4163 696715 : }
4164 :
4165 : #include "gt-tree-scalar-evolution.h"
|
