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 53757929 : new_scev_info_str (basic_block instantiated_below, tree var)
320 : {
321 53757929 : struct scev_info_str *res;
322 :
323 53757929 : res = ggc_alloc<scev_info_str> ();
324 53757929 : res->name_version = SSA_NAME_VERSION (var);
325 53757929 : res->chrec = chrec_not_analyzed_yet;
326 53757929 : res->instantiated_below = instantiated_below->index;
327 :
328 53757929 : return res;
329 : }
330 :
331 : /* Computes a hash function for database element ELT. */
332 :
333 : hashval_t
334 1093847462 : scev_info_hasher::hash (scev_info_str *elt)
335 : {
336 1093847462 : return elt->name_version ^ elt->instantiated_below;
337 : }
338 :
339 : /* Compares database elements E1 and E2. */
340 :
341 : bool
342 1086425359 : scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
343 : {
344 1086425359 : return (elt1->name_version == elt2->name_version
345 1086425359 : && 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 210112061 : find_var_scev_info (basic_block instantiated_below, tree var)
353 : {
354 210112061 : struct scev_info_str *res;
355 210112061 : struct scev_info_str tmp;
356 :
357 210112061 : tmp.name_version = SSA_NAME_VERSION (var);
358 210112061 : tmp.instantiated_below = instantiated_below->index;
359 210112061 : scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
360 :
361 210112061 : if (!*slot)
362 53757929 : *slot = new_scev_info_str (instantiated_below, var);
363 210112061 : res = *slot;
364 :
365 210112061 : 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 132060464 : instantiate_cache_type () : map (NULL), entries (vNULL) {}
380 : ~instantiate_cache_type ();
381 129126444 : tree get (unsigned slot) { return entries[slot].chrec; }
382 99687630 : void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
383 : };
384 :
385 132060464 : instantiate_cache_type::~instantiate_cache_type ()
386 : {
387 132060464 : if (map != NULL)
388 : {
389 29396449 : htab_delete (map);
390 29396449 : entries.release ();
391 : }
392 132060464 : }
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 26909402 : 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 5456397 : compute_overall_effect_of_inner_loop (class loop *loop, tree evolution_fn)
449 : {
450 6360022 : bool val = false;
451 :
452 6360022 : if (evolution_fn == chrec_dont_know)
453 : return chrec_dont_know;
454 :
455 6225057 : else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
456 : {
457 2431219 : class loop *inner_loop = get_chrec_loop (evolution_fn);
458 :
459 2431219 : if (inner_loop == loop
460 2431219 : || flow_loop_nested_p (loop, inner_loop))
461 : {
462 2431219 : tree nb_iter = number_of_latch_executions (inner_loop);
463 :
464 2431219 : if (nb_iter == chrec_dont_know)
465 : return chrec_dont_know;
466 : else
467 : {
468 903625 : tree res;
469 :
470 : /* evolution_fn is the evolution function in LOOP. Get
471 : its value in the nb_iter-th iteration. */
472 903625 : res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
473 :
474 903625 : if (chrec_contains_symbols_defined_in_loop (res, loop->num))
475 60032 : res = instantiate_parameters (loop, res);
476 :
477 : /* Continue the computation until ending on a parent of LOOP. */
478 903625 : 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 3793838 : else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
487 : return evolution_fn;
488 :
489 : else
490 3019498 : return chrec_dont_know;
491 : }
492 :
493 : /* Associate CHREC to SCALAR. */
494 :
495 : static void
496 51123785 : set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
497 : {
498 51123785 : tree *scalar_info;
499 :
500 51123785 : if (TREE_CODE (scalar) != SSA_NAME)
501 : return;
502 :
503 51123785 : scalar_info = find_var_scev_info (instantiated_below, scalar);
504 :
505 51123785 : if (dump_file)
506 : {
507 84956 : 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 84956 : if (dump_flags & TDF_STATS)
519 7185 : nb_set_scev++;
520 : }
521 :
522 51123785 : *scalar_info = chrec;
523 : }
524 :
525 : /* Retrieve the chrec associated to SCALAR instantiated below
526 : INSTANTIATED_BELOW block. */
527 :
528 : static tree
529 197881342 : get_scalar_evolution (basic_block instantiated_below, tree scalar)
530 : {
531 197881342 : tree res;
532 :
533 197881342 : if (dump_file)
534 : {
535 696958 : 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 696958 : if (dump_flags & TDF_STATS)
543 51081 : nb_get_scev++;
544 : }
545 :
546 197881342 : if (VECTOR_TYPE_P (TREE_TYPE (scalar))
547 197881342 : || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
548 : /* For chrec_dont_know we keep the symbolic form. */
549 : res = scalar;
550 : else
551 197591301 : switch (TREE_CODE (scalar))
552 : {
553 161131010 : case SSA_NAME:
554 161131010 : if (SSA_NAME_IS_DEFAULT_DEF (scalar))
555 : res = scalar;
556 : else
557 158988276 : 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 197881342 : res = chrec_not_analyzed_yet;
568 : break;
569 : }
570 :
571 197881342 : 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 197881342 : 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 11093365 : scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_)
594 11093365 : : 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 11093365 : scev_dfs::get_ev (tree *ev_fn, tree arg)
620 : {
621 11093365 : *ev_fn = chrec_dont_know;
622 11093365 : 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 9012533 : scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
637 : {
638 9012533 : tree type, left, right;
639 9012533 : unsigned loop_nb = loop->num;
640 9012533 : class loop *chloop;
641 :
642 9012533 : switch (TREE_CODE (chrec_before))
643 : {
644 88290 : case POLYNOMIAL_CHREC:
645 88290 : chloop = get_chrec_loop (chrec_before);
646 88290 : if (chloop == loop
647 88290 : || flow_loop_nested_p (chloop, loop))
648 : {
649 88290 : unsigned var;
650 :
651 88290 : type = chrec_type (chrec_before);
652 :
653 : /* When there is no evolution part in this loop, build it. */
654 88290 : 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 88290 : var = CHREC_VARIABLE (chrec_before);
665 88290 : left = CHREC_LEFT (chrec_before);
666 88290 : right = CHREC_RIGHT (chrec_before);
667 : }
668 :
669 88290 : to_add = chrec_convert (type, to_add, at_stmt);
670 88290 : right = chrec_convert_rhs (type, right, at_stmt);
671 88290 : 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 58556 : if ((INTEGRAL_TYPE_P (type) && ! TYPE_OVERFLOW_WRAPS (type))
680 33172 : && TREE_CODE (right) == INTEGER_CST
681 90550 : && TREE_OVERFLOW (right))
682 5 : return chrec_dont_know;
683 88285 : 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 8924243 : default:
699 : /* These nodes do not depend on a loop. */
700 8924243 : if (chrec_before == chrec_dont_know)
701 : return chrec_dont_know;
702 :
703 8905013 : left = chrec_before;
704 8905013 : 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 8905013 : STRIP_NOPS (chrec_before);
714 8905013 : if (chrec_before == gimple_phi_result (loop_phi_node))
715 8904264 : left = fold_convert (TREE_TYPE (left), init_cond);
716 8905013 : 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 9012533 : scev_dfs::add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt)
856 : {
857 9012533 : tree res = NULL_TREE;
858 :
859 9012533 : 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 9012533 : if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
865 : /* This should not happen. */
866 0 : return chrec_dont_know;
867 :
868 9012533 : 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 9012533 : res = add_to_evolution_1 (chrec_before, to_add, at_stmt);
880 :
881 9012533 : 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 1101558 : 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 1101558 : t_bool res = t_false;
901 1101558 : tree evol;
902 :
903 1101558 : switch (code)
904 : {
905 1101558 : case POINTER_PLUS_EXPR:
906 1101558 : case PLUS_EXPR:
907 1101558 : if (TREE_CODE (rhs0) == SSA_NAME)
908 : {
909 1082296 : 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 1082296 : limit++;
918 :
919 1082296 : evol = *evolution_of_loop;
920 1082296 : res = follow_ssa_edge_expr (at_stmt, rhs0, &evol, limit);
921 1082296 : if (res == t_true)
922 393385 : *evolution_of_loop = add_to_evolution
923 393385 : (chrec_convert (type, evol, at_stmt), rhs1, at_stmt);
924 688911 : else if (res == t_false)
925 : {
926 668961 : res = follow_ssa_edge_expr
927 668961 : (at_stmt, rhs1, evolution_of_loop, limit);
928 668961 : if (res == t_true)
929 512578 : *evolution_of_loop = add_to_evolution
930 512578 : (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 19262 : else if (TREE_CODE (rhs1) == SSA_NAME)
940 : {
941 : /* Match an assignment under the form:
942 : "a = ... + c". */
943 7497 : res = follow_ssa_edge_expr (at_stmt, rhs1, evolution_of_loop, limit);
944 7497 : if (res == t_true)
945 6696 : *evolution_of_loop = add_to_evolution
946 6696 : (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 1101558 : return res;
962 : }
963 :
964 : /* Checks whether the I-th argument of a PHI comes from a backedge. */
965 :
966 : static bool
967 8934000 : backedge_phi_arg_p (gphi *phi, int i)
968 : {
969 8934000 : 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 8934000 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
975 56891 : 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 3682597 : 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 3682597 : tree branch = PHI_ARG_DEF (condition_phi, i);
991 3682597 : *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 3682597 : if (backedge_phi_arg_p (condition_phi, i))
996 : return t_false;
997 :
998 3674567 : if (TREE_CODE (branch) == SSA_NAME)
999 : {
1000 3424233 : *evolution_of_branch = init_cond;
1001 3424233 : return follow_ssa_edge_expr (condition_phi, branch,
1002 3424233 : 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 2329477 : scev_dfs::follow_ssa_edge_in_condition_phi (gphi *condition_phi,
1020 : tree *evolution_of_loop, int limit)
1021 : {
1022 2329477 : int i, n;
1023 2329477 : tree init = *evolution_of_loop;
1024 2329477 : tree evolution_of_branch;
1025 2329477 : t_bool res = follow_ssa_edge_in_condition_phi_branch (0, condition_phi,
1026 : &evolution_of_branch,
1027 : init, limit);
1028 2329477 : if (res == t_false || res == t_dont_know)
1029 : return res;
1030 :
1031 1325071 : *evolution_of_loop = evolution_of_branch;
1032 :
1033 1325071 : n = gimple_phi_num_args (condition_phi);
1034 1908492 : for (i = 1; i < n; i++)
1035 : {
1036 : /* Quickly give up when the evolution of one of the branches is
1037 : not known. */
1038 1501896 : 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 1353120 : res = follow_ssa_edge_in_condition_phi_branch (i, condition_phi,
1044 : &evolution_of_branch,
1045 : init, limit + i);
1046 1353120 : if (res == t_false || res == t_dont_know)
1047 : return res;
1048 :
1049 583421 : *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 287625 : scev_dfs::follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
1063 : tree *evolution_of_loop, int limit)
1064 : {
1065 287625 : class loop *loop = loop_containing_stmt (loop_phi_node);
1066 287625 : 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 287625 : if (ev == PHI_RESULT (loop_phi_node))
1071 : {
1072 111938 : t_bool res = t_false;
1073 111938 : int i, n = gimple_phi_num_args (loop_phi_node);
1074 :
1075 163539 : for (i = 0; i < n; i++)
1076 : {
1077 154675 : tree arg = PHI_ARG_DEF (loop_phi_node, i);
1078 154675 : basic_block bb;
1079 :
1080 : /* Follow the edges that exit the inner loop. */
1081 154675 : bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1082 154675 : if (!flow_bb_inside_loop_p (loop, bb))
1083 111938 : res = follow_ssa_edge_expr (loop_phi_node,
1084 : arg, evolution_of_loop, limit);
1085 154675 : if (res == t_true)
1086 : break;
1087 : }
1088 :
1089 : /* If the path crosses this loop-phi, give up. */
1090 111938 : if (res == t_true)
1091 103074 : *evolution_of_loop = chrec_dont_know;
1092 :
1093 : return res;
1094 : }
1095 :
1096 : /* Otherwise, compute the overall effect of the inner loop. */
1097 175687 : ev = compute_overall_effect_of_inner_loop (loop, ev);
1098 175687 : 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 25171768 : scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
1106 : tree *evolution_of_loop, int limit)
1107 : {
1108 25171768 : gphi *halting_phi = loop_phi_node;
1109 25171768 : enum tree_code code;
1110 25171768 : 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 25171768 : if (TREE_CODE (expr) == SSA_NAME)
1124 : {
1125 24983290 : gimple *def = SSA_NAME_DEF_STMT (expr);
1126 :
1127 24983290 : 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 24967045 : if (limit > param_scev_max_expr_complexity)
1132 : {
1133 7897 : *evolution_of_loop = chrec_dont_know;
1134 7897 : return t_dont_know;
1135 : }
1136 :
1137 24959148 : if (gphi *phi = dyn_cast <gphi *>(def))
1138 : {
1139 25919640 : 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 2329477 : return follow_ssa_edge_in_condition_phi (phi, evolution_of_loop,
1145 2329477 : 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 10630343 : if (phi == halting_phi)
1151 : {
1152 10101850 : *evolution_of_loop = expr;
1153 10101850 : 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 528493 : class loop *def_loop = loop_containing_stmt (def);
1160 528493 : if (def_loop == loop)
1161 : return t_false;
1162 :
1163 : /* Inner loop. */
1164 314090 : if (flow_loop_nested_p (loop, def_loop))
1165 287625 : return follow_ssa_edge_inner_loop_phi (phi, evolution_of_loop,
1166 287625 : 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 11999328 : if (!is_gimple_assign (def))
1176 : return t_false;
1177 :
1178 11884430 : code = gimple_assign_rhs_code (def);
1179 11884430 : switch (get_gimple_rhs_class (code))
1180 : {
1181 10255677 : case GIMPLE_BINARY_RHS:
1182 10255677 : rhs0 = gimple_assign_rhs1 (def);
1183 10255677 : rhs1 = gimple_assign_rhs2 (def);
1184 10255677 : break;
1185 1596471 : case GIMPLE_UNARY_RHS:
1186 1596471 : case GIMPLE_SINGLE_RHS:
1187 1596471 : rhs0 = gimple_assign_rhs1 (def);
1188 1596471 : break;
1189 : default:
1190 : return t_false;
1191 : }
1192 11852148 : type = TREE_TYPE (gimple_assign_lhs (def));
1193 11852148 : at_stmt = def;
1194 : }
1195 : else
1196 : {
1197 188478 : code = TREE_CODE (expr);
1198 188478 : 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 188478 : switch (code)
1202 : {
1203 11436 : CASE_CONVERT:
1204 11436 : rhs0 = TREE_OPERAND (expr, 0);
1205 11436 : break;
1206 25855 : case POINTER_PLUS_EXPR:
1207 25855 : case PLUS_EXPR:
1208 25855 : case MINUS_EXPR:
1209 25855 : rhs0 = TREE_OPERAND (expr, 0);
1210 25855 : rhs1 = TREE_OPERAND (expr, 1);
1211 25855 : STRIP_USELESS_TYPE_CONVERSION (rhs0);
1212 25855 : STRIP_USELESS_TYPE_CONVERSION (rhs1);
1213 25855 : break;
1214 : default:
1215 : rhs0 = expr;
1216 : }
1217 : }
1218 :
1219 12040626 : switch (code)
1220 : {
1221 369339 : CASE_CONVERT:
1222 369339 : {
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 369339 : if (!tree_nop_conversion_p (type, TREE_TYPE (rhs0)))
1227 : return t_false;
1228 244919 : t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
1229 : evolution_of_loop, limit);
1230 244919 : if (res == t_true)
1231 94728 : *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 2179 : case ADDR_EXPR:
1241 2179 : {
1242 : /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1243 2179 : 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 8600979 : case POINTER_PLUS_EXPR:
1252 8600979 : case PLUS_EXPR:
1253 : /* This case is under the form "rhs0 +- rhs1". */
1254 8600979 : if (TREE_CODE (rhs0) == SSA_NAME && TREE_CODE (rhs1) != SSA_NAME)
1255 : {
1256 : /* Match an assignment under the form:
1257 : "a = b +- ...". */
1258 7499421 : t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
1259 : evolution_of_loop, limit);
1260 7499421 : if (res == t_true)
1261 7283219 : *evolution_of_loop = add_to_evolution
1262 7283219 : (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 1101558 : return follow_ssa_edge_binary (at_stmt, type, rhs0, code, rhs1,
1268 1101558 : evolution_of_loop, limit);
1269 :
1270 :
1271 870021 : case MINUS_EXPR:
1272 : /* This case is under the form "rhs0 - rhs1". */
1273 870021 : if (TREE_CODE (rhs0) == SSA_NAME)
1274 : {
1275 : /* Match an assignment under the form:
1276 : "a = b +- ...". */
1277 863451 : t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
1278 : evolution_of_loop, limit);
1279 863451 : 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 1633310 : if (INTEGRAL_TYPE_P (type)
1284 811636 : && TYPE_OVERFLOW_UNDEFINED (type)
1285 886684 : && !expr_not_equal_to (rhs1,
1286 886684 : wi::to_wide (TYPE_MIN_VALUE (type))))
1287 : {
1288 39378 : tree utype = unsigned_type_for (type);
1289 39378 : tree to_add = chrec_convert_rhs (utype, rhs1);
1290 39378 : to_add = chrec_fold_multiply (utype, to_add,
1291 : build_int_cst_type (utype, -1));
1292 39378 : *evolution_of_loop
1293 39378 : = chrec_convert (utype, *evolution_of_loop, at_stmt);
1294 39378 : *evolution_of_loop = add_to_evolution (*evolution_of_loop,
1295 : to_add, at_stmt);
1296 39378 : *evolution_of_loop
1297 39378 : = chrec_convert (type, *evolution_of_loop, at_stmt);
1298 : }
1299 : else
1300 : {
1301 777277 : tree to_add = chrec_fold_multiply (type, rhs1,
1302 : build_minus_one_cst (type));
1303 777277 : *evolution_of_loop
1304 777277 : = add_to_evolution (chrec_convert (type, *evolution_of_loop,
1305 : at_stmt),
1306 : to_add, at_stmt);
1307 : }
1308 816655 : 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 5245795 : get_loop_exit_condition (const_edge exit_edge)
1338 : {
1339 5245795 : gcond *res = NULL;
1340 :
1341 5245795 : if (dump_file && (dump_flags & TDF_SCEV))
1342 2 : fprintf (dump_file, "(get_loop_exit_condition \n ");
1343 :
1344 5245795 : if (exit_edge)
1345 10491590 : res = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
1346 :
1347 5245795 : 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 5245795 : 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 1668430 : simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond)
1373 : {
1374 3336860 : aff_tree aff1, aff2;
1375 1668430 : tree ev, left, right, type, step_val;
1376 1668430 : hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
1377 :
1378 1668430 : ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1379 1668430 : 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 1658891 : if (CONVERT_EXPR_P (ev)
1387 9539 : && TREE_CODE (init_cond) == INTEGER_CST
1388 3515 : && TREE_CODE (TREE_OPERAND (ev, 0)) == POLYNOMIAL_CHREC
1389 3251 : && (TYPE_PRECISION (TREE_TYPE (ev))
1390 3251 : > TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (ev, 0))))
1391 1671514 : && (!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 1665346 : if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
1419 1623792 : return chrec_dont_know;
1420 :
1421 41554 : left = CHREC_LEFT (ev);
1422 41554 : right = CHREC_RIGHT (ev);
1423 41554 : type = TREE_TYPE (left);
1424 41554 : 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 41554 : if (operand_equal_p (left, step_val, 0))
1429 : {
1430 18938 : if (dump_file && (dump_flags & TDF_SCEV))
1431 1 : fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1432 :
1433 18938 : return build_polynomial_chrec (loop->num, init_cond, right);
1434 : }
1435 :
1436 : /* The affine code only deals with pointer and integer types. */
1437 22616 : if (!POINTER_TYPE_P (type)
1438 16939 : && !INTEGRAL_TYPE_P (type))
1439 13 : return chrec_dont_know;
1440 :
1441 : /* Try harder to check if they are equal. */
1442 22603 : tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1443 22603 : tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1444 22603 : free_affine_expand_cache (&peeled_chrec_map);
1445 22603 : aff_combination_scale (&aff2, -1);
1446 22603 : aff_combination_add (&aff1, &aff2);
1447 :
1448 : /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1449 : if "left" equals to "init + right". */
1450 22603 : if (aff_combination_zero_p (&aff1))
1451 : {
1452 14391 : if (dump_file && (dump_flags & TDF_SCEV))
1453 1 : fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1454 :
1455 14391 : return build_polynomial_chrec (loop->num, init_cond, right);
1456 : }
1457 8212 : return chrec_dont_know;
1458 1668430 : }
1459 :
1460 : /* Given a LOOP_PHI_NODE, this function determines the evolution
1461 : function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1462 :
1463 : static tree
1464 11209690 : analyze_evolution_in_loop (gphi *loop_phi_node,
1465 : tree init_cond)
1466 : {
1467 11209690 : int i, n = gimple_phi_num_args (loop_phi_node);
1468 11209690 : tree evolution_function = chrec_not_analyzed_yet;
1469 11209690 : class loop *loop = loop_containing_stmt (loop_phi_node);
1470 11209690 : basic_block bb;
1471 11209690 : static bool simplify_peeled_chrec_p = true;
1472 :
1473 11209690 : if (dump_file && (dump_flags & TDF_SCEV))
1474 : {
1475 3 : fprintf (dump_file, "(analyze_evolution_in_loop \n");
1476 3 : fprintf (dump_file, " (loop_phi_node = ");
1477 3 : print_gimple_stmt (dump_file, loop_phi_node, 0);
1478 3 : fprintf (dump_file, ")\n");
1479 : }
1480 :
1481 29510009 : for (i = 0; i < n; i++)
1482 : {
1483 21100663 : tree arg = PHI_ARG_DEF (loop_phi_node, i);
1484 21100663 : tree ev_fn = chrec_dont_know;
1485 21100663 : t_bool res;
1486 :
1487 : /* Select the edges that enter the loop body. */
1488 21100663 : bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1489 21100663 : if (!flow_bb_inside_loop_p (loop, bb))
1490 9890973 : continue;
1491 :
1492 11209690 : if (TREE_CODE (arg) == SSA_NAME)
1493 : {
1494 11093365 : bool val = false;
1495 :
1496 : /* Pass in the initial condition to the follow edge function. */
1497 11093365 : scev_dfs dfs (loop, loop_phi_node, init_cond);
1498 11093365 : res = dfs.get_ev (&ev_fn, arg);
1499 :
1500 : /* If ev_fn has no evolution in the inner loop, and the
1501 : init_cond is not equal to ev_fn, then we have an
1502 : ambiguity between two possible values, as we cannot know
1503 : the number of iterations at this point. */
1504 11093365 : if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1505 2703700 : && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1506 11093365 : && !operand_equal_p (init_cond, ev_fn, 0))
1507 0 : ev_fn = chrec_dont_know;
1508 : }
1509 : else
1510 : res = t_false;
1511 :
1512 : /* When it is impossible to go back on the same
1513 : loop_phi_node by following the ssa edges, the
1514 : evolution is represented by a peeled chrec, i.e. the
1515 : first iteration, EV_FN has the value INIT_COND, then
1516 : all the other iterations it has the value of ARG.
1517 : For the moment, PEELED_CHREC nodes are not built. */
1518 11093365 : if (res != t_true)
1519 : {
1520 2460960 : ev_fn = chrec_dont_know;
1521 : /* Try to recognize POLYNOMIAL_CHREC which appears in
1522 : the form of PEELED_CHREC, but guard the process with
1523 : a bool variable to keep the analyzer from infinite
1524 : recurrence for real PEELED_RECs. */
1525 2460960 : if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1526 : {
1527 1668430 : simplify_peeled_chrec_p = false;
1528 1668430 : ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1529 1668430 : simplify_peeled_chrec_p = true;
1530 : }
1531 : }
1532 :
1533 : /* When there are multiple back edges of the loop (which in fact never
1534 : happens currently, but nevertheless), merge their evolutions. */
1535 11209690 : evolution_function = chrec_merge (evolution_function, ev_fn);
1536 :
1537 11209690 : if (evolution_function == chrec_dont_know)
1538 : break;
1539 : }
1540 :
1541 11209690 : if (dump_file && (dump_flags & TDF_SCEV))
1542 : {
1543 3 : fprintf (dump_file, " (evolution_function = ");
1544 3 : print_generic_expr (dump_file, evolution_function);
1545 3 : fprintf (dump_file, "))\n");
1546 : }
1547 :
1548 11209690 : return evolution_function;
1549 : }
1550 :
1551 : /* Looks to see if VAR is a copy of a constant (via straightforward assignments
1552 : or degenerate phi's). If so, returns the constant; else, returns VAR. */
1553 :
1554 : static tree
1555 23101173 : follow_copies_to_constant (tree var)
1556 : {
1557 23101173 : tree res = var;
1558 23101173 : while (TREE_CODE (res) == SSA_NAME
1559 : /* We face not updated SSA form in multiple places and this walk
1560 : may end up in sibling loops so we have to guard it. */
1561 27935138 : && !name_registered_for_update_p (res))
1562 : {
1563 16350260 : gimple *def = SSA_NAME_DEF_STMT (res);
1564 16350260 : if (gphi *phi = dyn_cast <gphi *> (def))
1565 : {
1566 4111923 : if (tree rhs = degenerate_phi_result (phi))
1567 : res = rhs;
1568 : else
1569 : break;
1570 : }
1571 12238337 : else if (gimple_assign_single_p (def))
1572 : /* Will exit loop if not an SSA_NAME. */
1573 4587340 : res = gimple_assign_rhs1 (def);
1574 : else
1575 : break;
1576 : }
1577 23101173 : if (CONSTANT_CLASS_P (res))
1578 6847674 : return res;
1579 : return var;
1580 : }
1581 :
1582 : /* Given a loop-phi-node, return the initial conditions of the
1583 : variable on entry of the loop. When the CCP has propagated
1584 : constants into the loop-phi-node, the initial condition is
1585 : instantiated, otherwise the initial condition is kept symbolic.
1586 : This analyzer does not analyze the evolution outside the current
1587 : loop, and leaves this task to the on-demand tree reconstructor. */
1588 :
1589 : static tree
1590 11209690 : analyze_initial_condition (gphi *loop_phi_node)
1591 : {
1592 11209690 : int i, n;
1593 11209690 : tree init_cond = chrec_not_analyzed_yet;
1594 11209690 : class loop *loop = loop_containing_stmt (loop_phi_node);
1595 :
1596 11209690 : if (dump_file && (dump_flags & TDF_SCEV))
1597 : {
1598 3 : fprintf (dump_file, "(analyze_initial_condition \n");
1599 3 : fprintf (dump_file, " (loop_phi_node = \n");
1600 3 : print_gimple_stmt (dump_file, loop_phi_node, 0);
1601 3 : fprintf (dump_file, ")\n");
1602 : }
1603 :
1604 11209690 : n = gimple_phi_num_args (loop_phi_node);
1605 33629070 : for (i = 0; i < n; i++)
1606 : {
1607 22419380 : tree branch = PHI_ARG_DEF (loop_phi_node, i);
1608 22419380 : basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1609 :
1610 : /* When the branch is oriented to the loop's body, it does
1611 : not contribute to the initial condition. */
1612 22419380 : if (flow_bb_inside_loop_p (loop, bb))
1613 11209690 : continue;
1614 :
1615 11209690 : if (init_cond == chrec_not_analyzed_yet)
1616 : {
1617 11209690 : init_cond = branch;
1618 11209690 : continue;
1619 : }
1620 :
1621 0 : if (TREE_CODE (branch) == SSA_NAME)
1622 : {
1623 0 : init_cond = chrec_dont_know;
1624 0 : break;
1625 : }
1626 :
1627 0 : init_cond = chrec_merge (init_cond, branch);
1628 : }
1629 :
1630 : /* Ooops -- a loop without an entry??? */
1631 11209690 : if (init_cond == chrec_not_analyzed_yet)
1632 0 : init_cond = chrec_dont_know;
1633 :
1634 : /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1635 : to not miss important early loop unrollings. */
1636 11209690 : init_cond = follow_copies_to_constant (init_cond);
1637 :
1638 11209690 : if (dump_file && (dump_flags & TDF_SCEV))
1639 : {
1640 3 : fprintf (dump_file, " (init_cond = ");
1641 3 : print_generic_expr (dump_file, init_cond);
1642 3 : fprintf (dump_file, "))\n");
1643 : }
1644 :
1645 11209690 : return init_cond;
1646 : }
1647 :
1648 : /* Analyze the scalar evolution for LOOP_PHI_NODE. */
1649 :
1650 : static tree
1651 11209690 : interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
1652 : {
1653 11209690 : class loop *phi_loop = loop_containing_stmt (loop_phi_node);
1654 11209690 : tree init_cond;
1655 :
1656 11209690 : gcc_assert (phi_loop == loop);
1657 :
1658 : /* Otherwise really interpret the loop phi. */
1659 11209690 : init_cond = analyze_initial_condition (loop_phi_node);
1660 11209690 : return analyze_evolution_in_loop (loop_phi_node, init_cond);
1661 : }
1662 :
1663 : /* This function merges the branches of a condition-phi-node,
1664 : contained in the outermost loop, and whose arguments are already
1665 : analyzed. */
1666 :
1667 : static tree
1668 2739892 : interpret_condition_phi (class loop *loop, gphi *condition_phi)
1669 : {
1670 2739892 : int i, n = gimple_phi_num_args (condition_phi);
1671 2739892 : tree res = chrec_not_analyzed_yet;
1672 :
1673 5775451 : for (i = 0; i < n; i++)
1674 : {
1675 5251403 : tree branch_chrec;
1676 :
1677 5251403 : if (backedge_phi_arg_p (condition_phi, i))
1678 : {
1679 48861 : res = chrec_dont_know;
1680 48861 : break;
1681 : }
1682 :
1683 5202542 : branch_chrec = analyze_scalar_evolution
1684 5202542 : (loop, PHI_ARG_DEF (condition_phi, i));
1685 :
1686 5202542 : res = chrec_merge (res, branch_chrec);
1687 5202542 : if (res == chrec_dont_know)
1688 : break;
1689 : }
1690 :
1691 2739892 : return res;
1692 : }
1693 :
1694 : /* Interpret the operation RHS1 OP RHS2. If we didn't
1695 : analyze this node before, follow the definitions until ending
1696 : either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1697 : return path, this function propagates evolutions (ala constant copy
1698 : propagation). OPND1 is not a GIMPLE expression because we could
1699 : analyze the effect of an inner loop: see interpret_loop_phi. */
1700 :
1701 : static tree
1702 45943029 : interpret_rhs_expr (class loop *loop, gimple *at_stmt,
1703 : tree type, tree rhs1, enum tree_code code, tree rhs2)
1704 : {
1705 45943029 : tree res, chrec1, chrec2, ctype;
1706 45943029 : gimple *def;
1707 :
1708 45943029 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1709 : {
1710 11157565 : if (is_gimple_min_invariant (rhs1))
1711 2484301 : return chrec_convert (type, rhs1, at_stmt);
1712 :
1713 8673264 : if (code == SSA_NAME)
1714 117756 : return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1715 117756 : at_stmt);
1716 : }
1717 :
1718 43340972 : switch (code)
1719 : {
1720 352417 : case ADDR_EXPR:
1721 352417 : if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1722 352417 : || handled_component_p (TREE_OPERAND (rhs1, 0)))
1723 : {
1724 352307 : machine_mode mode;
1725 352307 : poly_int64 bitsize, bitpos;
1726 352307 : int unsignedp, reversep;
1727 352307 : int volatilep = 0;
1728 352307 : tree base, offset;
1729 352307 : tree chrec3;
1730 352307 : tree unitpos;
1731 :
1732 352307 : base = get_inner_reference (TREE_OPERAND (rhs1, 0),
1733 : &bitsize, &bitpos, &offset, &mode,
1734 : &unsignedp, &reversep, &volatilep);
1735 :
1736 352307 : if (TREE_CODE (base) == MEM_REF)
1737 : {
1738 270427 : rhs2 = TREE_OPERAND (base, 1);
1739 270427 : rhs1 = TREE_OPERAND (base, 0);
1740 :
1741 270427 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1742 270427 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1743 270427 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1744 270427 : chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1745 270427 : chrec1 = instantiate_parameters (loop, chrec1);
1746 270427 : chrec2 = instantiate_parameters (loop, chrec2);
1747 270427 : res = chrec_fold_plus (type, chrec1, chrec2);
1748 : }
1749 : else
1750 : {
1751 81880 : chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1752 81880 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1753 81880 : res = chrec1;
1754 : }
1755 :
1756 352307 : if (offset != NULL_TREE)
1757 : {
1758 153883 : chrec2 = analyze_scalar_evolution (loop, offset);
1759 153883 : chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1760 153883 : chrec2 = instantiate_parameters (loop, chrec2);
1761 153883 : res = chrec_fold_plus (type, res, chrec2);
1762 : }
1763 :
1764 352307 : if (maybe_ne (bitpos, 0))
1765 : {
1766 130860 : unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
1767 130860 : chrec3 = analyze_scalar_evolution (loop, unitpos);
1768 130860 : chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1769 130860 : chrec3 = instantiate_parameters (loop, chrec3);
1770 130860 : res = chrec_fold_plus (type, res, chrec3);
1771 : }
1772 : }
1773 : else
1774 110 : res = chrec_dont_know;
1775 : break;
1776 :
1777 3470569 : case POINTER_PLUS_EXPR:
1778 3470569 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1779 3470569 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1780 3470569 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1781 3470569 : chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1782 3470569 : chrec1 = instantiate_parameters (loop, chrec1);
1783 3470569 : chrec2 = instantiate_parameters (loop, chrec2);
1784 3470569 : res = chrec_fold_plus (type, chrec1, chrec2);
1785 3470569 : break;
1786 :
1787 141579 : case POINTER_DIFF_EXPR:
1788 141579 : {
1789 141579 : tree utype = unsigned_type_for (type);
1790 141579 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1791 141579 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1792 141579 : chrec1 = chrec_convert (utype, chrec1, at_stmt);
1793 141579 : chrec2 = chrec_convert (utype, chrec2, at_stmt);
1794 141579 : chrec1 = instantiate_parameters (loop, chrec1);
1795 141579 : chrec2 = instantiate_parameters (loop, chrec2);
1796 141579 : res = chrec_fold_minus (utype, chrec1, chrec2);
1797 141579 : res = chrec_convert (type, res, at_stmt);
1798 141579 : break;
1799 : }
1800 :
1801 12020766 : case PLUS_EXPR:
1802 12020766 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1803 12020766 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1804 12020766 : ctype = type;
1805 : /* When the stmt is conditionally executed re-write the CHREC
1806 : into a form that has well-defined behavior on overflow. */
1807 12020766 : if (at_stmt
1808 10798209 : && INTEGRAL_TYPE_P (type)
1809 10703448 : && ! TYPE_OVERFLOW_WRAPS (type)
1810 20172478 : && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1811 8151712 : gimple_bb (at_stmt)))
1812 757912 : ctype = unsigned_type_for (type);
1813 12020766 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1814 12020766 : chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1815 12020766 : chrec1 = instantiate_parameters (loop, chrec1);
1816 12020766 : chrec2 = instantiate_parameters (loop, chrec2);
1817 12020766 : res = chrec_fold_plus (ctype, chrec1, chrec2);
1818 12020766 : if (type != ctype)
1819 757912 : res = chrec_convert (type, res, at_stmt);
1820 : break;
1821 :
1822 1519826 : case MINUS_EXPR:
1823 1519826 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1824 1519826 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1825 1519826 : ctype = type;
1826 : /* When the stmt is conditionally executed re-write the CHREC
1827 : into a form that has well-defined behavior on overflow. */
1828 1519826 : if (at_stmt
1829 1444016 : && INTEGRAL_TYPE_P (type)
1830 1405984 : && ! TYPE_OVERFLOW_WRAPS (type)
1831 2066539 : && ! dominated_by_p (CDI_DOMINATORS,
1832 546713 : loop->latch, gimple_bb (at_stmt)))
1833 140647 : ctype = unsigned_type_for (type);
1834 1519826 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1835 1519826 : chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1836 1519826 : chrec1 = instantiate_parameters (loop, chrec1);
1837 1519826 : chrec2 = instantiate_parameters (loop, chrec2);
1838 1519826 : res = chrec_fold_minus (ctype, chrec1, chrec2);
1839 1519826 : if (type != ctype)
1840 140647 : res = chrec_convert (type, res, at_stmt);
1841 : break;
1842 :
1843 62715 : case NEGATE_EXPR:
1844 62715 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1845 62715 : ctype = type;
1846 : /* When the stmt is conditionally executed re-write the CHREC
1847 : into a form that has well-defined behavior on overflow. */
1848 62715 : if (at_stmt
1849 53964 : && INTEGRAL_TYPE_P (type)
1850 52032 : && ! TYPE_OVERFLOW_WRAPS (type)
1851 101056 : && ! dominated_by_p (CDI_DOMINATORS,
1852 38341 : loop->latch, gimple_bb (at_stmt)))
1853 6091 : ctype = unsigned_type_for (type);
1854 62715 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1855 : /* TYPE may be integer, real or complex, so use fold_convert. */
1856 62715 : chrec1 = instantiate_parameters (loop, chrec1);
1857 62715 : res = chrec_fold_multiply (ctype, chrec1,
1858 : fold_convert (ctype, integer_minus_one_node));
1859 62715 : if (type != ctype)
1860 6091 : res = chrec_convert (type, res, at_stmt);
1861 : break;
1862 :
1863 37889 : case BIT_NOT_EXPR:
1864 : /* Handle ~X as -1 - X. */
1865 37889 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1866 37889 : chrec1 = chrec_convert (type, chrec1, at_stmt);
1867 37889 : chrec1 = instantiate_parameters (loop, chrec1);
1868 37889 : res = chrec_fold_minus (type,
1869 : fold_convert (type, integer_minus_one_node),
1870 : chrec1);
1871 37889 : break;
1872 :
1873 6185635 : case MULT_EXPR:
1874 6185635 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1875 6185635 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1876 6185635 : ctype = type;
1877 : /* When the stmt is conditionally executed re-write the CHREC
1878 : into a form that has well-defined behavior on overflow. */
1879 6185635 : if (at_stmt
1880 4209795 : && INTEGRAL_TYPE_P (type)
1881 4086755 : && ! TYPE_OVERFLOW_WRAPS (type)
1882 8031699 : && ! dominated_by_p (CDI_DOMINATORS,
1883 1846064 : loop->latch, gimple_bb (at_stmt)))
1884 188860 : ctype = unsigned_type_for (type);
1885 6185635 : chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1886 6185635 : chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1887 6185635 : chrec1 = instantiate_parameters (loop, chrec1);
1888 6185635 : chrec2 = instantiate_parameters (loop, chrec2);
1889 6185635 : res = chrec_fold_multiply (ctype, chrec1, chrec2);
1890 6185635 : if (type != ctype)
1891 188860 : res = chrec_convert (type, res, at_stmt);
1892 : break;
1893 :
1894 160930 : case LSHIFT_EXPR:
1895 160930 : {
1896 : /* Handle A<<B as A * (1<<B). */
1897 160930 : tree uns = unsigned_type_for (type);
1898 160930 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1899 160930 : chrec2 = analyze_scalar_evolution (loop, rhs2);
1900 160930 : chrec1 = chrec_convert (uns, chrec1, at_stmt);
1901 160930 : chrec1 = instantiate_parameters (loop, chrec1);
1902 160930 : chrec2 = instantiate_parameters (loop, chrec2);
1903 :
1904 160930 : tree one = build_int_cst (uns, 1);
1905 160930 : chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1906 160930 : res = chrec_fold_multiply (uns, chrec1, chrec2);
1907 160930 : res = chrec_convert (type, res, at_stmt);
1908 : }
1909 160930 : break;
1910 :
1911 8876916 : CASE_CONVERT:
1912 : /* In case we have a truncation of a widened operation that in
1913 : the truncated type has undefined overflow behavior analyze
1914 : the operation done in an unsigned type of the same precision
1915 : as the final truncation. We cannot derive a scalar evolution
1916 : for the widened operation but for the truncated result. */
1917 8874103 : if (INTEGRAL_NB_TYPE_P (type)
1918 8541327 : && INTEGRAL_NB_TYPE_P (TREE_TYPE (rhs1))
1919 7856187 : && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1920 537574 : && TYPE_OVERFLOW_UNDEFINED (type)
1921 348259 : && TREE_CODE (rhs1) == SSA_NAME
1922 348093 : && (def = SSA_NAME_DEF_STMT (rhs1))
1923 348093 : && is_gimple_assign (def)
1924 197025 : && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1925 9019176 : && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1926 : {
1927 106471 : tree utype = unsigned_type_for (type);
1928 106471 : chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1929 : gimple_assign_rhs1 (def),
1930 : gimple_assign_rhs_code (def),
1931 : gimple_assign_rhs2 (def));
1932 : }
1933 : else
1934 8770445 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1935 8876916 : res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
1936 8876916 : break;
1937 :
1938 391711 : case BIT_AND_EXPR:
1939 : /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1940 : If A is SCEV and its value is in the range of representable set
1941 : of type unsigned short, the result expression is a (no-overflow)
1942 : SCEV. */
1943 391711 : res = chrec_dont_know;
1944 391711 : if (tree_fits_uhwi_p (rhs2))
1945 : {
1946 261982 : int precision;
1947 261982 : unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
1948 :
1949 261982 : val ++;
1950 : /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1951 : it's not the maximum value of a smaller type than rhs1. */
1952 261982 : if (val != 0
1953 201926 : && (precision = exact_log2 (val)) > 0
1954 463908 : && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
1955 : {
1956 201926 : tree utype = build_nonstandard_integer_type (precision, 1);
1957 :
1958 201926 : if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
1959 : {
1960 201926 : chrec1 = analyze_scalar_evolution (loop, rhs1);
1961 201926 : chrec1 = chrec_convert (utype, chrec1, at_stmt);
1962 201926 : res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
1963 : }
1964 : }
1965 : }
1966 : break;
1967 :
1968 10120019 : default:
1969 10120019 : res = chrec_dont_know;
1970 10120019 : break;
1971 : }
1972 :
1973 : return res;
1974 : }
1975 :
1976 : /* Interpret the expression EXPR. */
1977 :
1978 : static tree
1979 9297268 : interpret_expr (class loop *loop, gimple *at_stmt, tree expr)
1980 : {
1981 9297268 : enum tree_code code;
1982 9297268 : tree type = TREE_TYPE (expr), op0, op1;
1983 :
1984 9297268 : if (automatically_generated_chrec_p (expr))
1985 : return expr;
1986 :
1987 9292197 : if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1988 9291649 : || TREE_CODE (expr) == CALL_EXPR
1989 18583768 : || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1990 : return chrec_dont_know;
1991 :
1992 9220557 : extract_ops_from_tree (expr, &code, &op0, &op1);
1993 :
1994 9220557 : return interpret_rhs_expr (loop, at_stmt, type,
1995 9220557 : op0, code, op1);
1996 : }
1997 :
1998 : /* Interpret the rhs of the assignment STMT. */
1999 :
2000 : static tree
2001 36616001 : interpret_gimple_assign (class loop *loop, gimple *stmt)
2002 : {
2003 36616001 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2004 36616001 : enum tree_code code = gimple_assign_rhs_code (stmt);
2005 :
2006 36616001 : return interpret_rhs_expr (loop, stmt, type,
2007 : gimple_assign_rhs1 (stmt), code,
2008 36616001 : gimple_assign_rhs2 (stmt));
2009 : }
2010 :
2011 :
2012 :
2013 : /* This section contains all the entry points:
2014 : - number_of_iterations_in_loop,
2015 : - analyze_scalar_evolution,
2016 : - instantiate_parameters.
2017 : */
2018 :
2019 : /* Helper recursive function. */
2020 :
2021 : static tree
2022 76015589 : analyze_scalar_evolution_1 (class loop *loop, tree var)
2023 : {
2024 76015589 : gimple *def;
2025 76015589 : basic_block bb;
2026 76015589 : class loop *def_loop;
2027 76015589 : tree res;
2028 :
2029 76015589 : if (TREE_CODE (var) != SSA_NAME)
2030 9297268 : return interpret_expr (loop, NULL, var);
2031 :
2032 66718321 : def = SSA_NAME_DEF_STMT (var);
2033 66718321 : bb = gimple_bb (def);
2034 66718321 : def_loop = bb->loop_father;
2035 :
2036 66718321 : if (!flow_bb_inside_loop_p (loop, bb))
2037 : {
2038 : /* Keep symbolic form, but look through obvious copies for constants. */
2039 11891483 : res = follow_copies_to_constant (var);
2040 11891483 : goto set_and_end;
2041 : }
2042 :
2043 54826838 : if (loop != def_loop)
2044 : {
2045 3703053 : res = analyze_scalar_evolution_1 (def_loop, var);
2046 3703053 : class loop *loop_to_skip = superloop_at_depth (def_loop,
2047 3703053 : loop_depth (loop) + 1);
2048 3703053 : res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
2049 3703053 : if (chrec_contains_symbols_defined_in_loop (res, loop->num))
2050 289094 : res = analyze_scalar_evolution_1 (loop, res);
2051 3703053 : goto set_and_end;
2052 : }
2053 :
2054 51123785 : switch (gimple_code (def))
2055 : {
2056 36616001 : case GIMPLE_ASSIGN:
2057 36616001 : res = interpret_gimple_assign (loop, def);
2058 36616001 : break;
2059 :
2060 13949582 : case GIMPLE_PHI:
2061 27899164 : if (loop_phi_node_p (def))
2062 11209690 : res = interpret_loop_phi (loop, as_a <gphi *> (def));
2063 : else
2064 2739892 : res = interpret_condition_phi (loop, as_a <gphi *> (def));
2065 : break;
2066 :
2067 558202 : default:
2068 558202 : res = chrec_dont_know;
2069 558202 : break;
2070 : }
2071 :
2072 66718321 : set_and_end:
2073 :
2074 : /* Keep the symbolic form. */
2075 66718321 : if (res == chrec_dont_know)
2076 24698346 : res = var;
2077 :
2078 66718321 : if (loop == def_loop)
2079 51123785 : set_scalar_evolution (block_before_loop (loop), var, res);
2080 :
2081 : return res;
2082 : }
2083 :
2084 : /* Analyzes and returns the scalar evolution of the ssa_name VAR in
2085 : LOOP. LOOP is the loop in which the variable is used.
2086 :
2087 : Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2088 : pointer to the statement that uses this variable, in order to
2089 : determine the evolution function of the variable, use the following
2090 : calls:
2091 :
2092 : loop_p loop = loop_containing_stmt (stmt);
2093 : tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2094 : tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2095 : */
2096 :
2097 : tree
2098 198072462 : analyze_scalar_evolution (class loop *loop, tree var)
2099 : {
2100 198072462 : tree res;
2101 :
2102 : /* ??? Fix callers. */
2103 198072462 : if (! loop)
2104 : return var;
2105 :
2106 197881342 : if (dump_file && (dump_flags & TDF_SCEV))
2107 : {
2108 38 : fprintf (dump_file, "(analyze_scalar_evolution \n");
2109 38 : fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2110 38 : fprintf (dump_file, " (scalar = ");
2111 38 : print_generic_expr (dump_file, var);
2112 38 : fprintf (dump_file, ")\n");
2113 : }
2114 :
2115 197881342 : res = get_scalar_evolution (block_before_loop (loop), var);
2116 197881342 : if (res == chrec_not_analyzed_yet)
2117 : {
2118 : /* We'll recurse into instantiate_scev, avoid tearing down the
2119 : instantiate cache repeatedly and keep it live from here. */
2120 72023442 : bool destr = false;
2121 72023442 : if (!global_cache)
2122 : {
2123 42847724 : global_cache = new instantiate_cache_type;
2124 42847724 : destr = true;
2125 : }
2126 72023442 : res = analyze_scalar_evolution_1 (loop, var);
2127 72023442 : if (destr)
2128 : {
2129 42847724 : delete global_cache;
2130 42847724 : global_cache = NULL;
2131 : }
2132 : }
2133 :
2134 197881342 : if (dump_file && (dump_flags & TDF_SCEV))
2135 38 : fprintf (dump_file, ")\n");
2136 :
2137 : return res;
2138 : }
2139 :
2140 : /* If CHREC doesn't overflow, set the nonwrapping flag. */
2141 :
2142 10827447 : void record_nonwrapping_chrec (tree chrec)
2143 : {
2144 10827447 : CHREC_NOWRAP(chrec) = 1;
2145 :
2146 10827447 : if (dump_file && (dump_flags & TDF_SCEV))
2147 : {
2148 6 : fprintf (dump_file, "(record_nonwrapping_chrec: ");
2149 6 : print_generic_expr (dump_file, chrec);
2150 6 : fprintf (dump_file, ")\n");
2151 : }
2152 10827447 : }
2153 :
2154 : /* Return true if CHREC's nonwrapping flag is set. */
2155 :
2156 218784 : bool nonwrapping_chrec_p (tree chrec)
2157 : {
2158 218784 : if (!chrec || TREE_CODE(chrec) != POLYNOMIAL_CHREC)
2159 : return false;
2160 :
2161 218784 : return CHREC_NOWRAP(chrec);
2162 : }
2163 :
2164 : /* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2165 :
2166 : static tree
2167 81880 : analyze_scalar_evolution_for_address_of (class loop *loop, tree var)
2168 : {
2169 81880 : return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2170 : }
2171 :
2172 : /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2173 : WRTO_LOOP (which should be a superloop of USE_LOOP)
2174 :
2175 : FOLDED_CASTS is set to true if resolve_mixers used
2176 : chrec_convert_aggressive (TODO -- not really, we are way too conservative
2177 : at the moment in order to keep things simple).
2178 :
2179 : To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2180 : example:
2181 :
2182 : for (i = 0; i < 100; i++) -- loop 1
2183 : {
2184 : for (j = 0; j < 100; j++) -- loop 2
2185 : {
2186 : k1 = i;
2187 : k2 = j;
2188 :
2189 : use2 (k1, k2);
2190 :
2191 : for (t = 0; t < 100; t++) -- loop 3
2192 : use3 (k1, k2);
2193 :
2194 : }
2195 : use1 (k1, k2);
2196 : }
2197 :
2198 : Both k1 and k2 are invariants in loop3, thus
2199 : analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2200 : analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2201 :
2202 : As they are invariant, it does not matter whether we consider their
2203 : usage in loop 3 or loop 2, hence
2204 : analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2205 : analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2206 : analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2207 : analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2208 :
2209 : Similarly for their evolutions with respect to loop 1. The values of K2
2210 : in the use in loop 2 vary independently on loop 1, thus we cannot express
2211 : the evolution with respect to loop 1:
2212 : analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2213 : analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2214 : analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2215 : analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2216 :
2217 : The value of k2 in the use in loop 1 is known, though:
2218 : analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2219 : analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2220 : */
2221 :
2222 : static tree
2223 50826896 : analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop,
2224 : tree version, bool *folded_casts)
2225 : {
2226 50826896 : bool val = false;
2227 50826896 : tree ev = version, tmp;
2228 :
2229 : /* We cannot just do
2230 :
2231 : tmp = analyze_scalar_evolution (use_loop, version);
2232 : ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2233 :
2234 : as resolve_mixers would query the scalar evolution with respect to
2235 : wrto_loop. For example, in the situation described in the function
2236 : comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2237 : version = k2. Then
2238 :
2239 : analyze_scalar_evolution (use_loop, version) = k2
2240 :
2241 : and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2242 : k2 in loop 1 is 100, which is a wrong result, since we are interested
2243 : in the value in loop 3.
2244 :
2245 : Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2246 : each time checking that there is no evolution in the inner loop. */
2247 :
2248 50826896 : if (folded_casts)
2249 50826896 : *folded_casts = false;
2250 53362238 : while (1)
2251 : {
2252 52094567 : tmp = analyze_scalar_evolution (use_loop, ev);
2253 52094567 : ev = resolve_mixers (use_loop, tmp, folded_casts);
2254 :
2255 52094567 : if (use_loop == wrto_loop)
2256 : return ev;
2257 :
2258 : /* If the value of the use changes in the inner loop, we cannot express
2259 : its value in the outer loop (we might try to return interval chrec,
2260 : but we do not have a user for it anyway) */
2261 4412632 : if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2262 4412632 : || !val)
2263 3144961 : return chrec_dont_know;
2264 :
2265 1267671 : use_loop = loop_outer (use_loop);
2266 : }
2267 : }
2268 :
2269 :
2270 : /* Computes a hash function for database element ELT. */
2271 :
2272 : static inline hashval_t
2273 434290 : hash_idx_scev_info (const void *elt_)
2274 : {
2275 434290 : unsigned idx = ((size_t) elt_) - 2;
2276 434290 : return scev_info_hasher::hash (&global_cache->entries[idx]);
2277 : }
2278 :
2279 : /* Compares database elements E1 and E2. */
2280 :
2281 : static inline int
2282 32635190 : eq_idx_scev_info (const void *e1, const void *e2)
2283 : {
2284 32635190 : unsigned idx1 = ((size_t) e1) - 2;
2285 32635190 : return scev_info_hasher::equal (&global_cache->entries[idx1],
2286 32635190 : (const scev_info_str *) e2);
2287 : }
2288 :
2289 : /* Returns from CACHE the slot number of the cached chrec for NAME. */
2290 :
2291 : static unsigned
2292 64563222 : get_instantiated_value_entry (instantiate_cache_type &cache,
2293 : tree name, edge instantiate_below)
2294 : {
2295 64563222 : if (!cache.map)
2296 : {
2297 29396449 : cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
2298 29396449 : cache.entries.create (10);
2299 : }
2300 :
2301 64563222 : scev_info_str e;
2302 64563222 : e.name_version = SSA_NAME_VERSION (name);
2303 64563222 : e.instantiated_below = instantiate_below->dest->index;
2304 64563222 : void **slot = htab_find_slot_with_hash (cache.map, &e,
2305 : scev_info_hasher::hash (&e), INSERT);
2306 64563222 : if (!*slot)
2307 : {
2308 33263194 : e.chrec = chrec_not_analyzed_yet;
2309 33263194 : *slot = (void *)(size_t)(cache.entries.length () + 2);
2310 33263194 : cache.entries.safe_push (e);
2311 : }
2312 :
2313 64563222 : return ((size_t)*slot) - 2;
2314 : }
2315 :
2316 :
2317 : /* Return the closed_loop_phi node for VAR. If there is none, return
2318 : NULL_TREE. */
2319 :
2320 : static tree
2321 1763537 : loop_closed_phi_def (tree var)
2322 : {
2323 1763537 : class loop *loop;
2324 1763537 : edge exit;
2325 1763537 : gphi *phi;
2326 1763537 : gphi_iterator psi;
2327 :
2328 1763537 : if (var == NULL_TREE
2329 1763537 : || TREE_CODE (var) != SSA_NAME)
2330 : return NULL_TREE;
2331 :
2332 1763537 : loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2333 1763537 : exit = single_exit (loop);
2334 1763537 : if (!exit)
2335 : return NULL_TREE;
2336 :
2337 1472971 : for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2338 : {
2339 831745 : phi = psi.phi ();
2340 831745 : if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2341 220843 : return PHI_RESULT (phi);
2342 : }
2343 :
2344 : return NULL_TREE;
2345 : }
2346 :
2347 : static tree instantiate_scev_r (edge, class loop *, class loop *,
2348 : tree, bool *, int);
2349 :
2350 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2351 : and EVOLUTION_LOOP, that were left under a symbolic form.
2352 :
2353 : CHREC is an SSA_NAME to be instantiated.
2354 :
2355 : CACHE is the cache of already instantiated values.
2356 :
2357 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2358 : conversions that may wrap in signed/pointer type are folded, as long
2359 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2360 : then we don't do such fold.
2361 :
2362 : SIZE_EXPR is used for computing the size of the expression to be
2363 : instantiated, and to stop if it exceeds some limit. */
2364 :
2365 : static tree
2366 112735602 : instantiate_scev_name (edge instantiate_below,
2367 : class loop *evolution_loop, class loop *inner_loop,
2368 : tree chrec,
2369 : bool *fold_conversions,
2370 : int size_expr)
2371 : {
2372 112735602 : tree res;
2373 112735602 : class loop *def_loop;
2374 112735602 : basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2375 :
2376 : /* A parameter, nothing to do. */
2377 112735602 : if (!def_bb
2378 112735602 : || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
2379 : return chrec;
2380 :
2381 : /* We cache the value of instantiated variable to avoid exponential
2382 : time complexity due to reevaluations. We also store the convenient
2383 : value in the cache in order to prevent infinite recursion -- we do
2384 : not want to instantiate the SSA_NAME if it is in a mixer
2385 : structure. This is used for avoiding the instantiation of
2386 : recursively defined functions, such as:
2387 :
2388 : | a_2 -> {0, +, 1, +, a_2}_1 */
2389 :
2390 64563222 : unsigned si = get_instantiated_value_entry (*global_cache,
2391 : chrec, instantiate_below);
2392 64563222 : if (global_cache->get (si) != chrec_not_analyzed_yet)
2393 : return global_cache->get (si);
2394 :
2395 : /* On recursion return chrec_dont_know. */
2396 33263194 : global_cache->set (si, chrec_dont_know);
2397 :
2398 33263194 : def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2399 :
2400 33263194 : if (! dominated_by_p (CDI_DOMINATORS,
2401 33263194 : def_loop->header, instantiate_below->dest))
2402 : {
2403 184455 : gimple *def = SSA_NAME_DEF_STMT (chrec);
2404 184455 : if (gassign *ass = dyn_cast <gassign *> (def))
2405 : {
2406 139845 : switch (gimple_assign_rhs_class (ass))
2407 : {
2408 4248 : case GIMPLE_UNARY_RHS:
2409 4248 : {
2410 4248 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2411 : inner_loop, gimple_assign_rhs1 (ass),
2412 : fold_conversions, size_expr);
2413 4248 : if (op0 == chrec_dont_know)
2414 : return chrec_dont_know;
2415 1542 : res = fold_build1 (gimple_assign_rhs_code (ass),
2416 : TREE_TYPE (chrec), op0);
2417 1542 : break;
2418 : }
2419 50782 : case GIMPLE_BINARY_RHS:
2420 50782 : {
2421 50782 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2422 : inner_loop, gimple_assign_rhs1 (ass),
2423 : fold_conversions, size_expr);
2424 50782 : if (op0 == chrec_dont_know)
2425 : return chrec_dont_know;
2426 13086 : tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2427 : inner_loop, gimple_assign_rhs2 (ass),
2428 : fold_conversions, size_expr);
2429 6543 : if (op1 == chrec_dont_know)
2430 : return chrec_dont_know;
2431 2512 : res = fold_build2 (gimple_assign_rhs_code (ass),
2432 : TREE_TYPE (chrec), op0, op1);
2433 2512 : break;
2434 : }
2435 84815 : default:
2436 84815 : res = chrec_dont_know;
2437 : }
2438 : }
2439 : else
2440 44610 : res = chrec_dont_know;
2441 133479 : global_cache->set (si, res);
2442 133479 : return res;
2443 : }
2444 :
2445 : /* If the analysis yields a parametric chrec, instantiate the
2446 : result again. */
2447 33078739 : res = analyze_scalar_evolution (def_loop, chrec);
2448 :
2449 : /* Don't instantiate default definitions. */
2450 33078739 : if (TREE_CODE (res) == SSA_NAME
2451 33078739 : && SSA_NAME_IS_DEFAULT_DEF (res))
2452 : ;
2453 :
2454 : /* Don't instantiate loop-closed-ssa phi nodes. */
2455 33062365 : else if (TREE_CODE (res) == SSA_NAME
2456 97466836 : && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2457 32202610 : > loop_depth (def_loop))
2458 : {
2459 1783137 : if (res == chrec)
2460 1763537 : res = loop_closed_phi_def (chrec);
2461 : else
2462 : res = chrec;
2463 :
2464 : /* When there is no loop_closed_phi_def, it means that the
2465 : variable is not used after the loop: try to still compute the
2466 : value of the variable when exiting the loop. */
2467 1783137 : if (res == NULL_TREE)
2468 : {
2469 1542694 : loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2470 1542694 : res = analyze_scalar_evolution (loop, chrec);
2471 1542694 : res = compute_overall_effect_of_inner_loop (loop, res);
2472 1542694 : res = instantiate_scev_r (instantiate_below, evolution_loop,
2473 : inner_loop, res,
2474 : fold_conversions, size_expr);
2475 : }
2476 240443 : else if (dominated_by_p (CDI_DOMINATORS,
2477 240443 : gimple_bb (SSA_NAME_DEF_STMT (res)),
2478 240443 : instantiate_below->dest))
2479 240443 : res = chrec_dont_know;
2480 : }
2481 :
2482 31279228 : else if (res != chrec_dont_know)
2483 : {
2484 31279228 : if (inner_loop
2485 1245967 : && def_bb->loop_father != inner_loop
2486 31885999 : && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2487 : /* ??? We could try to compute the overall effect of the loop here. */
2488 321 : res = chrec_dont_know;
2489 : else
2490 31278907 : res = instantiate_scev_r (instantiate_below, evolution_loop,
2491 : inner_loop, res,
2492 : fold_conversions, size_expr);
2493 : }
2494 :
2495 : /* Store the correct value to the cache. */
2496 33078739 : global_cache->set (si, res);
2497 33078739 : return res;
2498 : }
2499 :
2500 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2501 : and EVOLUTION_LOOP, that were left under a symbolic form.
2502 :
2503 : CHREC is a polynomial chain of recurrence to be instantiated.
2504 :
2505 : CACHE is the cache of already instantiated values.
2506 :
2507 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2508 : conversions that may wrap in signed/pointer type are folded, as long
2509 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2510 : then we don't do such fold.
2511 :
2512 : SIZE_EXPR is used for computing the size of the expression to be
2513 : instantiated, and to stop if it exceeds some limit. */
2514 :
2515 : static tree
2516 61642219 : instantiate_scev_poly (edge instantiate_below,
2517 : class loop *evolution_loop, class loop *,
2518 : tree chrec, bool *fold_conversions, int size_expr)
2519 : {
2520 61642219 : tree op1;
2521 123284438 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2522 : get_chrec_loop (chrec),
2523 61642219 : CHREC_LEFT (chrec), fold_conversions,
2524 : size_expr);
2525 61642219 : if (op0 == chrec_dont_know)
2526 : return chrec_dont_know;
2527 :
2528 122850736 : op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2529 : get_chrec_loop (chrec),
2530 61425368 : CHREC_RIGHT (chrec), fold_conversions,
2531 : size_expr);
2532 61425368 : if (op1 == chrec_dont_know)
2533 : return chrec_dont_know;
2534 :
2535 60672196 : if (CHREC_LEFT (chrec) != op0
2536 60672196 : || CHREC_RIGHT (chrec) != op1)
2537 : {
2538 8042664 : op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2539 8042664 : chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2540 : }
2541 :
2542 : return chrec;
2543 : }
2544 :
2545 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2546 : and EVOLUTION_LOOP, that were left under a symbolic form.
2547 :
2548 : "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2549 :
2550 : CACHE is the cache of already instantiated values.
2551 :
2552 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2553 : conversions that may wrap in signed/pointer type are folded, as long
2554 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2555 : then we don't do such fold.
2556 :
2557 : SIZE_EXPR is used for computing the size of the expression to be
2558 : instantiated, and to stop if it exceeds some limit. */
2559 :
2560 : static tree
2561 24609326 : instantiate_scev_binary (edge instantiate_below,
2562 : class loop *evolution_loop, class loop *inner_loop,
2563 : tree chrec, enum tree_code code,
2564 : tree type, tree c0, tree c1,
2565 : bool *fold_conversions, int size_expr)
2566 : {
2567 24609326 : tree op1;
2568 24609326 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2569 : c0, fold_conversions, size_expr);
2570 24609326 : if (op0 == chrec_dont_know)
2571 : return chrec_dont_know;
2572 :
2573 : /* While we eventually compute the same op1 if c0 == c1 the process
2574 : of doing this is expensive so the following short-cut prevents
2575 : exponential compile-time behavior. */
2576 24268390 : if (c0 != c1)
2577 : {
2578 24247865 : op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2579 : c1, fold_conversions, size_expr);
2580 24247865 : if (op1 == chrec_dont_know)
2581 : return chrec_dont_know;
2582 : }
2583 : else
2584 : op1 = op0;
2585 :
2586 24198386 : if (c0 != op0
2587 24198386 : || c1 != op1)
2588 : {
2589 14048535 : op0 = chrec_convert (type, op0, NULL);
2590 14048535 : op1 = chrec_convert_rhs (type, op1, NULL);
2591 :
2592 14048535 : switch (code)
2593 : {
2594 8202028 : case POINTER_PLUS_EXPR:
2595 8202028 : case PLUS_EXPR:
2596 8202028 : return chrec_fold_plus (type, op0, op1);
2597 :
2598 894339 : case MINUS_EXPR:
2599 894339 : return chrec_fold_minus (type, op0, op1);
2600 :
2601 4952168 : case MULT_EXPR:
2602 4952168 : return chrec_fold_multiply (type, op0, op1);
2603 :
2604 0 : default:
2605 0 : gcc_unreachable ();
2606 : }
2607 : }
2608 :
2609 10149851 : return chrec ? chrec : fold_build2 (code, type, c0, c1);
2610 : }
2611 :
2612 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2613 : and EVOLUTION_LOOP, that were left under a symbolic form.
2614 :
2615 : "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2616 : instantiated.
2617 :
2618 : CACHE is the cache of already instantiated values.
2619 :
2620 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2621 : conversions that may wrap in signed/pointer type are folded, as long
2622 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2623 : then we don't do such fold.
2624 :
2625 : SIZE_EXPR is used for computing the size of the expression to be
2626 : instantiated, and to stop if it exceeds some limit. */
2627 :
2628 : static tree
2629 25558088 : instantiate_scev_convert (edge instantiate_below,
2630 : class loop *evolution_loop, class loop *inner_loop,
2631 : tree chrec, tree type, tree op,
2632 : bool *fold_conversions, int size_expr)
2633 : {
2634 25558088 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2635 : inner_loop, op,
2636 : fold_conversions, size_expr);
2637 :
2638 25558088 : if (op0 == chrec_dont_know)
2639 : return chrec_dont_know;
2640 :
2641 20309739 : if (fold_conversions)
2642 : {
2643 8009622 : tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2644 8009622 : if (tmp)
2645 : return tmp;
2646 :
2647 : /* If we used chrec_convert_aggressive, we can no longer assume that
2648 : signed chrecs do not overflow, as chrec_convert does, so avoid
2649 : calling it in that case. */
2650 7462098 : if (*fold_conversions)
2651 : {
2652 14118 : if (chrec && op0 == op)
2653 : return chrec;
2654 :
2655 14118 : return fold_convert (type, op0);
2656 : }
2657 : }
2658 :
2659 19748097 : return chrec_convert (type, op0, NULL);
2660 : }
2661 :
2662 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2663 : and EVOLUTION_LOOP, that were left under a symbolic form.
2664 :
2665 : CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2666 : Handle ~X as -1 - X.
2667 : Handle -X as -1 * X.
2668 :
2669 : CACHE is the cache of already instantiated values.
2670 :
2671 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2672 : conversions that may wrap in signed/pointer type are folded, as long
2673 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2674 : then we don't do such fold.
2675 :
2676 : SIZE_EXPR is used for computing the size of the expression to be
2677 : instantiated, and to stop if it exceeds some limit. */
2678 :
2679 : static tree
2680 289072 : instantiate_scev_not (edge instantiate_below,
2681 : class loop *evolution_loop, class loop *inner_loop,
2682 : tree chrec,
2683 : enum tree_code code, tree type, tree op,
2684 : bool *fold_conversions, int size_expr)
2685 : {
2686 289072 : tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2687 : inner_loop, op,
2688 : fold_conversions, size_expr);
2689 :
2690 289072 : if (op0 == chrec_dont_know)
2691 : return chrec_dont_know;
2692 :
2693 222267 : if (op != op0)
2694 : {
2695 155820 : op0 = chrec_convert (type, op0, NULL);
2696 :
2697 155820 : switch (code)
2698 : {
2699 2318 : case BIT_NOT_EXPR:
2700 2318 : return chrec_fold_minus
2701 2318 : (type, fold_convert (type, integer_minus_one_node), op0);
2702 :
2703 153502 : case NEGATE_EXPR:
2704 153502 : return chrec_fold_multiply
2705 153502 : (type, fold_convert (type, integer_minus_one_node), op0);
2706 :
2707 0 : default:
2708 0 : gcc_unreachable ();
2709 : }
2710 : }
2711 :
2712 66447 : return chrec ? chrec : fold_build1 (code, type, op0);
2713 : }
2714 :
2715 : /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2716 : and EVOLUTION_LOOP, that were left under a symbolic form.
2717 :
2718 : CHREC is the scalar evolution to instantiate.
2719 :
2720 : CACHE is the cache of already instantiated values.
2721 :
2722 : Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2723 : conversions that may wrap in signed/pointer type are folded, as long
2724 : as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2725 : then we don't do such fold.
2726 :
2727 : SIZE_EXPR is used for computing the size of the expression to be
2728 : instantiated, and to stop if it exceeds some limit. */
2729 :
2730 : static tree
2731 371367027 : instantiate_scev_r (edge instantiate_below,
2732 : class loop *evolution_loop, class loop *inner_loop,
2733 : tree chrec,
2734 : bool *fold_conversions, int size_expr)
2735 : {
2736 : /* Give up if the expression is larger than the MAX that we allow. */
2737 371367027 : if (size_expr++ > param_scev_max_expr_size)
2738 11 : return chrec_dont_know;
2739 :
2740 371367016 : if (chrec == NULL_TREE
2741 740810690 : || automatically_generated_chrec_p (chrec)
2742 740810679 : || is_gimple_min_invariant (chrec))
2743 : return chrec;
2744 :
2745 225554725 : switch (TREE_CODE (chrec))
2746 : {
2747 112735602 : case SSA_NAME:
2748 112735602 : return instantiate_scev_name (instantiate_below, evolution_loop,
2749 : inner_loop, chrec,
2750 112735602 : fold_conversions, size_expr);
2751 :
2752 61642219 : case POLYNOMIAL_CHREC:
2753 61642219 : return instantiate_scev_poly (instantiate_below, evolution_loop,
2754 : inner_loop, chrec,
2755 61642219 : fold_conversions, size_expr);
2756 :
2757 24609326 : case POINTER_PLUS_EXPR:
2758 24609326 : case PLUS_EXPR:
2759 24609326 : case MINUS_EXPR:
2760 24609326 : case MULT_EXPR:
2761 24609326 : return instantiate_scev_binary (instantiate_below, evolution_loop,
2762 : inner_loop, chrec,
2763 : TREE_CODE (chrec), chrec_type (chrec),
2764 24609326 : TREE_OPERAND (chrec, 0),
2765 24609326 : TREE_OPERAND (chrec, 1),
2766 24609326 : fold_conversions, size_expr);
2767 :
2768 25558088 : CASE_CONVERT:
2769 25558088 : return instantiate_scev_convert (instantiate_below, evolution_loop,
2770 : inner_loop, chrec,
2771 25558088 : TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
2772 25558088 : fold_conversions, size_expr);
2773 :
2774 289072 : case NEGATE_EXPR:
2775 289072 : case BIT_NOT_EXPR:
2776 289072 : return instantiate_scev_not (instantiate_below, evolution_loop,
2777 : inner_loop, chrec,
2778 289072 : TREE_CODE (chrec), TREE_TYPE (chrec),
2779 289072 : TREE_OPERAND (chrec, 0),
2780 289072 : fold_conversions, size_expr);
2781 :
2782 0 : case ADDR_EXPR:
2783 0 : if (is_gimple_min_invariant (chrec))
2784 : return chrec;
2785 : /* Fallthru. */
2786 0 : case SCEV_NOT_KNOWN:
2787 0 : return chrec_dont_know;
2788 :
2789 0 : case SCEV_KNOWN:
2790 0 : return chrec_known;
2791 :
2792 720418 : default:
2793 720418 : if (CONSTANT_CLASS_P (chrec))
2794 : return chrec;
2795 720418 : return chrec_dont_know;
2796 : }
2797 : }
2798 :
2799 : /* Analyze all the parameters of the chrec that were left under a
2800 : symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2801 : recursive instantiation of parameters: a parameter is a variable
2802 : that is defined in a basic block that dominates INSTANTIATE_BELOW or
2803 : a function parameter. */
2804 :
2805 : tree
2806 88617348 : instantiate_scev (edge instantiate_below, class loop *evolution_loop,
2807 : tree chrec)
2808 : {
2809 88617348 : tree res;
2810 :
2811 88617348 : if (dump_file && (dump_flags & TDF_SCEV))
2812 : {
2813 20 : fprintf (dump_file, "(instantiate_scev \n");
2814 20 : fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
2815 20 : instantiate_below->src->index, instantiate_below->dest->index);
2816 20 : if (evolution_loop)
2817 20 : fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2818 20 : fprintf (dump_file, " (chrec = ");
2819 20 : print_generic_expr (dump_file, chrec);
2820 20 : fprintf (dump_file, ")\n");
2821 : }
2822 :
2823 88617348 : bool destr = false;
2824 88617348 : if (!global_cache)
2825 : {
2826 37926847 : global_cache = new instantiate_cache_type;
2827 37926847 : destr = true;
2828 : }
2829 :
2830 88617348 : res = instantiate_scev_r (instantiate_below, evolution_loop,
2831 : NULL, chrec, NULL, 0);
2832 :
2833 88617348 : if (destr)
2834 : {
2835 37926847 : delete global_cache;
2836 37926847 : global_cache = NULL;
2837 : }
2838 :
2839 88617348 : if (dump_file && (dump_flags & TDF_SCEV))
2840 : {
2841 20 : fprintf (dump_file, " (res = ");
2842 20 : print_generic_expr (dump_file, res);
2843 20 : fprintf (dump_file, "))\n");
2844 : }
2845 :
2846 88617348 : return res;
2847 : }
2848 :
2849 : /* Similar to instantiate_parameters, but does not introduce the
2850 : evolutions in outer loops for LOOP invariants in CHREC, and does not
2851 : care about causing overflows, as long as they do not affect value
2852 : of an expression. */
2853 :
2854 : tree
2855 52094567 : resolve_mixers (class loop *loop, tree chrec, bool *folded_casts)
2856 : {
2857 52094567 : bool destr = false;
2858 52094567 : bool fold_conversions = false;
2859 52094567 : if (!global_cache)
2860 : {
2861 51285893 : global_cache = new instantiate_cache_type;
2862 51285893 : destr = true;
2863 : }
2864 :
2865 52094567 : tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
2866 : chrec, &fold_conversions, 0);
2867 :
2868 52094567 : if (folded_casts && !*folded_casts)
2869 52094567 : *folded_casts = fold_conversions;
2870 :
2871 52094567 : if (destr)
2872 : {
2873 51285893 : delete global_cache;
2874 51285893 : global_cache = NULL;
2875 : }
2876 :
2877 52094567 : return ret;
2878 : }
2879 :
2880 : /* Entry point for the analysis of the number of iterations pass.
2881 : This function tries to safely approximate the number of iterations
2882 : the loop will run. When this property is not decidable at compile
2883 : time, the result is chrec_dont_know. Otherwise the result is a
2884 : scalar or a symbolic parameter. When the number of iterations may
2885 : be equal to zero and the property cannot be determined at compile
2886 : time, the result is a COND_EXPR that represents in a symbolic form
2887 : the conditions under which the number of iterations is not zero.
2888 :
2889 : Example of analysis: suppose that the loop has an exit condition:
2890 :
2891 : "if (b > 49) goto end_loop;"
2892 :
2893 : and that in a previous analysis we have determined that the
2894 : variable 'b' has an evolution function:
2895 :
2896 : "EF = {23, +, 5}_2".
2897 :
2898 : When we evaluate the function at the point 5, i.e. the value of the
2899 : variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2900 : and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2901 : the loop body has been executed 6 times. */
2902 :
2903 : tree
2904 10204881 : number_of_latch_executions (class loop *loop)
2905 : {
2906 10204881 : edge exit;
2907 10204881 : class tree_niter_desc niter_desc;
2908 10204881 : tree may_be_zero;
2909 10204881 : tree res;
2910 :
2911 : /* Determine whether the number of iterations in loop has already
2912 : been computed. */
2913 10204881 : res = loop->nb_iterations;
2914 10204881 : if (res)
2915 : return res;
2916 :
2917 6984072 : may_be_zero = NULL_TREE;
2918 :
2919 6984072 : if (dump_file && (dump_flags & TDF_SCEV))
2920 2 : fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2921 :
2922 6984072 : res = chrec_dont_know;
2923 6984072 : exit = single_exit (loop);
2924 :
2925 6984072 : if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2926 : {
2927 3496617 : may_be_zero = niter_desc.may_be_zero;
2928 3496617 : res = niter_desc.niter;
2929 : }
2930 :
2931 6984072 : if (res == chrec_dont_know
2932 3496617 : || !may_be_zero
2933 10480689 : || integer_zerop (may_be_zero))
2934 : ;
2935 545818 : else if (integer_nonzerop (may_be_zero))
2936 29 : res = build_int_cst (TREE_TYPE (res), 0);
2937 :
2938 545789 : else if (COMPARISON_CLASS_P (may_be_zero))
2939 545789 : res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2940 : build_int_cst (TREE_TYPE (res), 0), res);
2941 : else
2942 0 : res = chrec_dont_know;
2943 :
2944 6984072 : if (dump_file && (dump_flags & TDF_SCEV))
2945 : {
2946 2 : fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2947 2 : print_generic_expr (dump_file, res);
2948 2 : fprintf (dump_file, "))\n");
2949 : }
2950 :
2951 6984072 : loop->nb_iterations = res;
2952 6984072 : return res;
2953 10204881 : }
2954 :
2955 :
2956 : /* Counters for the stats. */
2957 :
2958 : struct chrec_stats
2959 : {
2960 : unsigned nb_chrecs;
2961 : unsigned nb_affine;
2962 : unsigned nb_affine_multivar;
2963 : unsigned nb_higher_poly;
2964 : unsigned nb_chrec_dont_know;
2965 : unsigned nb_undetermined;
2966 : };
2967 :
2968 : /* Reset the counters. */
2969 :
2970 : static inline void
2971 0 : reset_chrecs_counters (struct chrec_stats *stats)
2972 : {
2973 0 : stats->nb_chrecs = 0;
2974 0 : stats->nb_affine = 0;
2975 0 : stats->nb_affine_multivar = 0;
2976 0 : stats->nb_higher_poly = 0;
2977 0 : stats->nb_chrec_dont_know = 0;
2978 0 : stats->nb_undetermined = 0;
2979 : }
2980 :
2981 : /* Dump the contents of a CHREC_STATS structure. */
2982 :
2983 : static void
2984 0 : dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2985 : {
2986 0 : fprintf (file, "\n(\n");
2987 0 : fprintf (file, "-----------------------------------------\n");
2988 0 : fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2989 0 : fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2990 0 : fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2991 : stats->nb_higher_poly);
2992 0 : fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2993 0 : fprintf (file, "-----------------------------------------\n");
2994 0 : fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2995 0 : fprintf (file, "%d\twith undetermined coefficients\n",
2996 : stats->nb_undetermined);
2997 0 : fprintf (file, "-----------------------------------------\n");
2998 0 : fprintf (file, "%d\tchrecs in the scev database\n",
2999 0 : (int) scalar_evolution_info->elements ());
3000 0 : fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3001 0 : fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3002 0 : fprintf (file, "-----------------------------------------\n");
3003 0 : fprintf (file, ")\n\n");
3004 0 : }
3005 :
3006 : /* Gather statistics about CHREC. */
3007 :
3008 : static void
3009 0 : gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3010 : {
3011 0 : if (dump_file && (dump_flags & TDF_STATS))
3012 : {
3013 0 : fprintf (dump_file, "(classify_chrec ");
3014 0 : print_generic_expr (dump_file, chrec);
3015 0 : fprintf (dump_file, "\n");
3016 : }
3017 :
3018 0 : stats->nb_chrecs++;
3019 :
3020 0 : if (chrec == NULL_TREE)
3021 : {
3022 0 : stats->nb_undetermined++;
3023 0 : return;
3024 : }
3025 :
3026 0 : switch (TREE_CODE (chrec))
3027 : {
3028 0 : case POLYNOMIAL_CHREC:
3029 0 : if (evolution_function_is_affine_p (chrec))
3030 : {
3031 0 : if (dump_file && (dump_flags & TDF_STATS))
3032 0 : fprintf (dump_file, " affine_univariate\n");
3033 0 : stats->nb_affine++;
3034 : }
3035 0 : else if (evolution_function_is_affine_multivariate_p (chrec, 0))
3036 : {
3037 0 : if (dump_file && (dump_flags & TDF_STATS))
3038 0 : fprintf (dump_file, " affine_multivariate\n");
3039 0 : stats->nb_affine_multivar++;
3040 : }
3041 : else
3042 : {
3043 0 : if (dump_file && (dump_flags & TDF_STATS))
3044 0 : fprintf (dump_file, " higher_degree_polynomial\n");
3045 0 : stats->nb_higher_poly++;
3046 : }
3047 :
3048 : break;
3049 :
3050 : default:
3051 : break;
3052 : }
3053 :
3054 0 : if (chrec_contains_undetermined (chrec))
3055 : {
3056 0 : if (dump_file && (dump_flags & TDF_STATS))
3057 0 : fprintf (dump_file, " undetermined\n");
3058 0 : stats->nb_undetermined++;
3059 : }
3060 :
3061 0 : if (dump_file && (dump_flags & TDF_STATS))
3062 0 : fprintf (dump_file, ")\n");
3063 : }
3064 :
3065 : /* Classify the chrecs of the whole database. */
3066 :
3067 : void
3068 0 : gather_stats_on_scev_database (void)
3069 : {
3070 0 : struct chrec_stats stats;
3071 :
3072 0 : if (!dump_file)
3073 0 : return;
3074 :
3075 0 : reset_chrecs_counters (&stats);
3076 :
3077 0 : hash_table<scev_info_hasher>::iterator iter;
3078 0 : scev_info_str *elt;
3079 0 : FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3080 : iter)
3081 0 : gather_chrec_stats (elt->chrec, &stats);
3082 :
3083 0 : dump_chrecs_stats (dump_file, &stats);
3084 : }
3085 :
3086 :
3087 : /* Initialize the analysis of scalar evolutions for LOOPS. */
3088 :
3089 : void
3090 15357553 : scev_initialize (void)
3091 : {
3092 15357553 : gcc_assert (! scev_initialized_p ()
3093 : && loops_state_satisfies_p (cfun, LOOPS_NORMAL));
3094 :
3095 15357553 : scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
3096 :
3097 55503201 : for (auto loop : loops_list (cfun, 0))
3098 9430542 : loop->nb_iterations = NULL_TREE;
3099 15357553 : }
3100 :
3101 : /* Return true if SCEV is initialized. */
3102 :
3103 : bool
3104 100168598 : scev_initialized_p (void)
3105 : {
3106 100168598 : return scalar_evolution_info != NULL;
3107 : }
3108 :
3109 : /* Cleans up the information cached by the scalar evolutions analysis
3110 : in the hash table. */
3111 :
3112 : void
3113 24549248 : scev_reset_htab (void)
3114 : {
3115 24549248 : if (!scalar_evolution_info)
3116 : return;
3117 :
3118 6306661 : scalar_evolution_info->empty ();
3119 : }
3120 :
3121 : /* Cleans up the information cached by the scalar evolutions analysis
3122 : in the hash table and in the loop->nb_iterations. */
3123 :
3124 : void
3125 13193079 : scev_reset (void)
3126 : {
3127 13193079 : scev_reset_htab ();
3128 :
3129 64555676 : for (auto loop : loops_list (cfun, 0))
3130 24976439 : loop->nb_iterations = NULL_TREE;
3131 13193079 : }
3132 :
3133 : /* Return true if the IV calculation in TYPE can overflow based on the knowledge
3134 : of the upper bound on the number of iterations of LOOP, the BASE and STEP
3135 : of IV.
3136 :
3137 : We do not use information whether TYPE can overflow so it is safe to
3138 : use this test even for derived IVs not computed every iteration or
3139 : hypothetical IVs to be inserted into code. */
3140 :
3141 : bool
3142 15336524 : iv_can_overflow_p (class loop *loop, tree type, tree base, tree step)
3143 : {
3144 15336524 : widest_int nit;
3145 15336524 : wide_int base_min, base_max, step_min, step_max, type_min, type_max;
3146 15336524 : signop sgn = TYPE_SIGN (type);
3147 15336524 : int_range_max r;
3148 :
3149 15336524 : if (integer_zerop (step))
3150 : return false;
3151 :
3152 30669537 : if (!INTEGRAL_TYPE_P (TREE_TYPE (base))
3153 28474900 : || !get_range_query (cfun)->range_of_expr (r, base)
3154 14237450 : || r.varying_p ()
3155 27946813 : || r.undefined_p ())
3156 : return true;
3157 :
3158 12608057 : base_min = r.lower_bound ();
3159 12608057 : base_max = r.upper_bound ();
3160 :
3161 25212716 : if (!INTEGRAL_TYPE_P (TREE_TYPE (step))
3162 25216114 : || !get_range_query (cfun)->range_of_expr (r, step)
3163 12608057 : || r.varying_p ()
3164 25137796 : || r.undefined_p ())
3165 : return true;
3166 :
3167 12529739 : step_min = r.lower_bound ();
3168 12529739 : step_max = r.upper_bound ();
3169 :
3170 12529739 : if (!get_max_loop_iterations (loop, &nit))
3171 : return true;
3172 :
3173 11855899 : type_min = wi::min_value (type);
3174 11855899 : type_max = wi::max_value (type);
3175 :
3176 : /* Just sanity check that we don't see values out of the range of the type.
3177 : In this case the arithmetics below would overflow. */
3178 11855899 : gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
3179 : && wi::le_p (base_max, type_max, sgn));
3180 :
3181 : /* Account the possible increment in the last ieration. */
3182 11855899 : wi::overflow_type overflow = wi::OVF_NONE;
3183 11855899 : nit = wi::add (nit, 1, SIGNED, &overflow);
3184 11855899 : if (overflow)
3185 : return true;
3186 :
3187 : /* NIT is typeless and can exceed the precision of the type. In this case
3188 : overflow is always possible, because we know STEP is non-zero. */
3189 11855899 : if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
3190 : return true;
3191 11625932 : wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
3192 :
3193 : /* If step can be positive, check that nit*step <= type_max-base.
3194 : This can be done by unsigned arithmetic and we only need to watch overflow
3195 : in the multiplication. The right hand side can always be represented in
3196 : the type. */
3197 11625932 : if (sgn == UNSIGNED || !wi::neg_p (step_max))
3198 : {
3199 11581773 : wi::overflow_type overflow = wi::OVF_NONE;
3200 11581773 : if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
3201 23163546 : type_max - base_max)
3202 23163546 : || overflow)
3203 5835580 : return true;
3204 : }
3205 : /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3206 5790352 : if (sgn == SIGNED && wi::neg_p (step_min))
3207 : {
3208 44446 : wi::overflow_type overflow, overflow2;
3209 44446 : overflow = overflow2 = wi::OVF_NONE;
3210 88892 : if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
3211 : nit2, UNSIGNED, &overflow),
3212 88892 : base_min - type_min)
3213 88892 : || overflow || overflow2)
3214 14772 : return true;
3215 : }
3216 :
3217 : return false;
3218 15336524 : }
3219 :
3220 : /* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3221 : function tries to derive condition under which it can be simplified
3222 : into "{(type)inner_base, (type)inner_step}_loop". The condition is
3223 : the maximum number that inner iv can iterate. */
3224 :
3225 : static tree
3226 38493 : derive_simple_iv_with_niters (tree ev, tree *niters)
3227 : {
3228 38493 : if (!CONVERT_EXPR_P (ev))
3229 : return ev;
3230 :
3231 38493 : tree inner_ev = TREE_OPERAND (ev, 0);
3232 38493 : if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
3233 : return ev;
3234 :
3235 38493 : tree init = CHREC_LEFT (inner_ev);
3236 38493 : tree step = CHREC_RIGHT (inner_ev);
3237 38493 : if (TREE_CODE (init) != INTEGER_CST
3238 38493 : || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3239 : return ev;
3240 :
3241 30130 : tree type = TREE_TYPE (ev);
3242 30130 : tree inner_type = TREE_TYPE (inner_ev);
3243 30130 : if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
3244 : return ev;
3245 :
3246 : /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3247 : folded only if inner iv won't overflow. We compute the maximum
3248 : number the inner iv can iterate before overflowing and return the
3249 : simplified affine iv. */
3250 30130 : tree delta;
3251 30130 : init = fold_convert (type, init);
3252 30130 : step = fold_convert (type, step);
3253 30130 : ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
3254 30130 : if (tree_int_cst_sign_bit (step))
3255 : {
3256 0 : tree bound = lower_bound_in_type (inner_type, inner_type);
3257 0 : delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
3258 0 : step = fold_build1 (NEGATE_EXPR, type, step);
3259 : }
3260 : else
3261 : {
3262 30130 : tree bound = upper_bound_in_type (inner_type, inner_type);
3263 30130 : delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
3264 : }
3265 30130 : *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
3266 30130 : return ev;
3267 : }
3268 :
3269 : /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3270 : respect to WRTO_LOOP and returns its base and step in IV if possible
3271 : (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3272 : and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3273 : invariant in LOOP. Otherwise we require it to be an integer constant.
3274 :
3275 : IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3276 : because it is computed in signed arithmetics). Consequently, adding an
3277 : induction variable
3278 :
3279 : for (i = IV->base; ; i += IV->step)
3280 :
3281 : is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3282 : false for the type of the induction variable, or you can prove that i does
3283 : not wrap by some other argument. Otherwise, this might introduce undefined
3284 : behavior, and
3285 :
3286 : i = iv->base;
3287 : for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3288 :
3289 : must be used instead.
3290 :
3291 : When IV_NITERS is not NULL, this function also checks case in which OP
3292 : is a conversion of an inner simple iv of below form:
3293 :
3294 : (outer_type){inner_base, inner_step}_loop.
3295 :
3296 : If type of inner iv has smaller precision than outer_type, it can't be
3297 : folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3298 : the inner iv could overflow/wrap. In this case, we derive a condition
3299 : under which the inner iv won't overflow/wrap and do the simplification.
3300 : The derived condition normally is the maximum number the inner iv can
3301 : iterate, and will be stored in IV_NITERS. This is useful in loop niter
3302 : analysis, to derive break conditions when a loop must terminate, when is
3303 : infinite. */
3304 :
3305 : bool
3306 52821546 : simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop,
3307 : tree op, affine_iv *iv, tree *iv_niters,
3308 : bool allow_nonconstant_step)
3309 : {
3310 52821546 : enum tree_code code;
3311 52821546 : tree type, ev, base, e;
3312 52821546 : wide_int extreme;
3313 52821546 : bool folded_casts;
3314 :
3315 52821546 : iv->base = NULL_TREE;
3316 52821546 : iv->step = NULL_TREE;
3317 52821546 : iv->no_overflow = false;
3318 :
3319 52821546 : type = TREE_TYPE (op);
3320 52821546 : if (!POINTER_TYPE_P (type)
3321 43491584 : && !INTEGRAL_TYPE_P (type))
3322 : return false;
3323 :
3324 50715368 : ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3325 : &folded_casts);
3326 50715368 : if (chrec_contains_undetermined (ev)
3327 50715368 : || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3328 : return false;
3329 :
3330 37601678 : if (tree_does_not_contain_chrecs (ev))
3331 : {
3332 16660595 : iv->base = ev;
3333 16660595 : tree ev_type = TREE_TYPE (ev);
3334 16660595 : if (POINTER_TYPE_P (ev_type))
3335 2730788 : ev_type = sizetype;
3336 :
3337 16660595 : iv->step = build_int_cst (ev_type, 0);
3338 16660595 : iv->no_overflow = true;
3339 16660595 : return true;
3340 : }
3341 :
3342 : /* If we can derive valid scalar evolution with assumptions. */
3343 20941083 : if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
3344 38493 : ev = derive_simple_iv_with_niters (ev, iv_niters);
3345 :
3346 20941083 : if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
3347 : return false;
3348 :
3349 20892818 : if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3350 : return false;
3351 :
3352 20892804 : iv->step = CHREC_RIGHT (ev);
3353 13414935 : if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3354 34046851 : || tree_contains_chrecs (iv->step, NULL))
3355 : return false;
3356 :
3357 20620500 : iv->base = CHREC_LEFT (ev);
3358 20620500 : if (tree_contains_chrecs (iv->base, NULL))
3359 : return false;
3360 :
3361 20620500 : iv->no_overflow = !folded_casts && nowrap_type_p (type);
3362 :
3363 20620500 : if (!iv->no_overflow
3364 20620500 : && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
3365 3900491 : iv->no_overflow = true;
3366 :
3367 : /* Try to simplify iv base:
3368 :
3369 : (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3370 : == (signed T)(unsigned T)base + step
3371 : == base + step
3372 :
3373 : If we can prove operation (base + step) doesn't overflow or underflow.
3374 : Specifically, we try to prove below conditions are satisfied:
3375 :
3376 : base <= UPPER_BOUND (type) - step ;;step > 0
3377 : base >= LOWER_BOUND (type) - step ;;step < 0
3378 :
3379 : This is done by proving the reverse conditions are false using loop's
3380 : initial conditions.
3381 :
3382 : The is necessary to make loop niter, or iv overflow analysis easier
3383 : for below example:
3384 :
3385 : int foo (int *a, signed char s, signed char l)
3386 : {
3387 : signed char i;
3388 : for (i = s; i < l; i++)
3389 : a[i] = 0;
3390 : return 0;
3391 : }
3392 :
3393 : Note variable I is firstly converted to type unsigned char, incremented,
3394 : then converted back to type signed char. */
3395 :
3396 20620500 : if (wrto_loop->num != use_loop->num)
3397 : return true;
3398 :
3399 20429323 : if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3400 : return true;
3401 :
3402 232109 : type = TREE_TYPE (iv->base);
3403 232109 : e = TREE_OPERAND (iv->base, 0);
3404 232109 : if (!tree_nop_conversion_p (type, TREE_TYPE (e))
3405 200719 : || TREE_CODE (e) != PLUS_EXPR
3406 111618 : || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3407 316930 : || !tree_int_cst_equal (iv->step,
3408 84821 : fold_convert (type, TREE_OPERAND (e, 1))))
3409 : return true;
3410 66590 : e = TREE_OPERAND (e, 0);
3411 66590 : if (!CONVERT_EXPR_P (e))
3412 : return true;
3413 36163 : base = TREE_OPERAND (e, 0);
3414 36163 : if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3415 : return true;
3416 :
3417 27292 : if (tree_int_cst_sign_bit (iv->step))
3418 : {
3419 7284 : code = LT_EXPR;
3420 7284 : extreme = wi::min_value (type);
3421 : }
3422 : else
3423 : {
3424 20008 : code = GT_EXPR;
3425 20008 : extreme = wi::max_value (type);
3426 : }
3427 27292 : wi::overflow_type overflow = wi::OVF_NONE;
3428 27292 : extreme = wi::sub (extreme, wi::to_wide (iv->step),
3429 54584 : TYPE_SIGN (type), &overflow);
3430 27292 : if (overflow)
3431 : return true;
3432 27268 : e = fold_build2 (code, boolean_type_node, base,
3433 : wide_int_to_tree (type, extreme));
3434 27268 : e = simplify_using_initial_conditions (use_loop, e);
3435 27268 : if (!integer_zerop (e))
3436 : return true;
3437 :
3438 13613 : if (POINTER_TYPE_P (TREE_TYPE (base)))
3439 : code = POINTER_PLUS_EXPR;
3440 : else
3441 : code = PLUS_EXPR;
3442 :
3443 13613 : iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3444 13613 : return true;
3445 52821546 : }
3446 :
3447 : /* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3448 : affine iv unconditionally. */
3449 :
3450 : bool
3451 21459066 : simple_iv (class loop *wrto_loop, class loop *use_loop, tree op,
3452 : affine_iv *iv, bool allow_nonconstant_step)
3453 : {
3454 21459066 : return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
3455 21459066 : NULL, allow_nonconstant_step);
3456 : }
3457 :
3458 : /* Finalize the scalar evolution analysis. */
3459 :
3460 : void
3461 15357554 : scev_finalize (void)
3462 : {
3463 15357554 : if (!scalar_evolution_info)
3464 : return;
3465 15357553 : scalar_evolution_info->empty ();
3466 15357553 : scalar_evolution_info = NULL;
3467 15357553 : free_numbers_of_iterations_estimates (cfun);
3468 : }
3469 :
3470 : /* Returns true if the expression EXPR is considered to be too expensive
3471 : for scev_const_prop. Sets *COND_OVERFLOW_P to true when the
3472 : expression might contain a sub-expression that is subject to undefined
3473 : overflow behavior and conditionally evaluated. */
3474 :
3475 : static bool
3476 11147267 : expression_expensive_p (tree expr, bool *cond_overflow_p,
3477 : hash_map<tree, uint64_t> &cache, uint64_t &cost)
3478 : {
3479 11147267 : enum tree_code code;
3480 :
3481 11147267 : if (is_gimple_val (expr))
3482 : return false;
3483 :
3484 4759025 : code = TREE_CODE (expr);
3485 4759025 : if (code == TRUNC_DIV_EXPR
3486 : || code == CEIL_DIV_EXPR
3487 : || code == FLOOR_DIV_EXPR
3488 : || code == ROUND_DIV_EXPR
3489 : || code == TRUNC_MOD_EXPR
3490 : || code == CEIL_MOD_EXPR
3491 : || code == FLOOR_MOD_EXPR
3492 4759025 : || code == ROUND_MOD_EXPR
3493 4759025 : || code == EXACT_DIV_EXPR)
3494 : {
3495 : /* Division by power of two is usually cheap, so we allow it.
3496 : Forbid anything else. */
3497 60098 : if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3498 : return true;
3499 : }
3500 :
3501 4748839 : bool visited_p;
3502 4748839 : uint64_t &local_cost = cache.get_or_insert (expr, &visited_p);
3503 4748839 : if (visited_p)
3504 : {
3505 350 : uint64_t tem = cost + local_cost;
3506 350 : if (tem < cost)
3507 : return true;
3508 350 : cost = tem;
3509 350 : return false;
3510 : }
3511 4748489 : local_cost = 1;
3512 :
3513 4748489 : uint64_t op_cost = 0;
3514 4748489 : if (code == CALL_EXPR)
3515 : {
3516 145 : tree arg;
3517 145 : call_expr_arg_iterator iter;
3518 : /* Even though is_inexpensive_builtin might say true, we will get a
3519 : library call for popcount when backend does not have an instruction
3520 : to do so. We consider this to be expensive and generate
3521 : __builtin_popcount only when backend defines it. */
3522 145 : optab optab;
3523 145 : combined_fn cfn = get_call_combined_fn (expr);
3524 145 : switch (cfn)
3525 : {
3526 36 : CASE_CFN_POPCOUNT:
3527 36 : optab = popcount_optab;
3528 36 : goto bitcount_call;
3529 85 : CASE_CFN_CLZ:
3530 85 : optab = clz_optab;
3531 85 : goto bitcount_call;
3532 : CASE_CFN_CTZ:
3533 : optab = ctz_optab;
3534 145 : bitcount_call:
3535 : /* Check if opcode for popcount is available in the mode required. */
3536 145 : if (optab_handler (optab,
3537 145 : TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0))))
3538 : == CODE_FOR_nothing)
3539 : {
3540 32 : machine_mode mode;
3541 32 : mode = TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0)));
3542 32 : scalar_int_mode int_mode;
3543 :
3544 : /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
3545 : double-word popcount by emitting two single-word popcount
3546 : instructions. */
3547 32 : if (is_a <scalar_int_mode> (mode, &int_mode)
3548 34 : && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
3549 2 : && (optab_handler (optab, word_mode)
3550 : != CODE_FOR_nothing))
3551 : break;
3552 : /* If popcount is available for a wider mode, we emulate the
3553 : operation for a narrow mode by first zero-extending the value
3554 : and then computing popcount in the wider mode. Analogue for
3555 : ctz. For clz we do the same except that we additionally have
3556 : to subtract the difference of the mode precisions from the
3557 : result. */
3558 30 : if (is_a <scalar_int_mode> (mode, &int_mode))
3559 : {
3560 30 : machine_mode wider_mode_iter;
3561 149 : FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
3562 119 : if (optab_handler (optab, wider_mode_iter)
3563 : != CODE_FOR_nothing)
3564 0 : goto check_call_args;
3565 : /* Operation ctz may be emulated via clz in expand_ctz. */
3566 30 : if (optab == ctz_optab)
3567 : {
3568 0 : FOR_EACH_WIDER_MODE_FROM (wider_mode_iter, mode)
3569 0 : if (optab_handler (clz_optab, wider_mode_iter)
3570 : != CODE_FOR_nothing)
3571 0 : goto check_call_args;
3572 : }
3573 : }
3574 145 : return true;
3575 : }
3576 : break;
3577 :
3578 0 : default:
3579 0 : if (cfn == CFN_LAST
3580 0 : || !is_inexpensive_builtin (get_callee_fndecl (expr)))
3581 : return true;
3582 : break;
3583 : }
3584 :
3585 115 : check_call_args:
3586 345 : FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
3587 115 : if (expression_expensive_p (arg, cond_overflow_p, cache, op_cost))
3588 : return true;
3589 115 : *cache.get (expr) += op_cost;
3590 115 : cost += op_cost + 1;
3591 115 : return false;
3592 : }
3593 :
3594 4748344 : if (code == COND_EXPR)
3595 : {
3596 2040 : if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
3597 : cache, op_cost)
3598 2040 : || (EXPR_P (TREE_OPERAND (expr, 1))
3599 2039 : && EXPR_P (TREE_OPERAND (expr, 2)))
3600 : /* If either branch has side effects or could trap. */
3601 2032 : || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1))
3602 2032 : || generic_expr_could_trap_p (TREE_OPERAND (expr, 1))
3603 2031 : || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))
3604 2031 : || generic_expr_could_trap_p (TREE_OPERAND (expr, 0))
3605 2031 : || expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
3606 : cache, op_cost)
3607 3971 : || expression_expensive_p (TREE_OPERAND (expr, 2), cond_overflow_p,
3608 : cache, op_cost))
3609 : return true;
3610 : /* Conservatively assume there's overflow for now. */
3611 1931 : *cond_overflow_p = true;
3612 1931 : *cache.get (expr) += op_cost;
3613 1931 : cost += op_cost + 1;
3614 1931 : return false;
3615 : }
3616 :
3617 4746304 : switch (TREE_CODE_CLASS (code))
3618 : {
3619 2472905 : case tcc_binary:
3620 2472905 : case tcc_comparison:
3621 2472905 : if (expression_expensive_p (TREE_OPERAND (expr, 1), cond_overflow_p,
3622 : cache, op_cost))
3623 : return true;
3624 :
3625 : /* Fallthru. */
3626 4743363 : case tcc_unary:
3627 4743363 : if (expression_expensive_p (TREE_OPERAND (expr, 0), cond_overflow_p,
3628 : cache, op_cost))
3629 : return true;
3630 4718375 : *cache.get (expr) += op_cost;
3631 4718375 : cost += op_cost + 1;
3632 4718375 : return false;
3633 :
3634 : default:
3635 : return true;
3636 : }
3637 : }
3638 :
3639 : bool
3640 3924882 : expression_expensive_p (tree expr, bool *cond_overflow_p)
3641 : {
3642 3924882 : hash_map<tree, uint64_t> cache;
3643 3924882 : uint64_t expanded_size = 0;
3644 3924882 : *cond_overflow_p = false;
3645 3924882 : return (expression_expensive_p (expr, cond_overflow_p, cache, expanded_size)
3646 : /* ??? Both the explicit unsharing and gimplification of expr will
3647 : expand shared trees to multiple copies.
3648 : Guard against exponential growth by counting the visits and
3649 : comparing against the number of original nodes. Allow a tiny
3650 : bit of duplication to catch some additional optimizations. */
3651 3935249 : || expanded_size > (cache.elements () + 1));
3652 3924882 : }
3653 :
3654 : /* Match.pd function to match bitwise inductive expression.
3655 : .i.e.
3656 : _2 = 1 << _1;
3657 : _3 = ~_2;
3658 : tmp_9 = _3 & tmp_12; */
3659 : extern bool gimple_bitwise_induction_p (tree, tree *, tree (*)(tree));
3660 :
3661 : /* Return the inductive expression of bitwise operation if possible,
3662 : otherwise returns DEF. */
3663 : static tree
3664 20819 : analyze_and_compute_bitwise_induction_effect (class loop* loop,
3665 : tree phidef,
3666 : unsigned HOST_WIDE_INT niter)
3667 : {
3668 20819 : tree match_op[3],inv, bitwise_scev;
3669 20819 : tree type = TREE_TYPE (phidef);
3670 20819 : gphi* header_phi = NULL;
3671 :
3672 : /* Match things like op2(MATCH_OP[2]), op1(MATCH_OP[1]), phidef(PHIDEF)
3673 :
3674 : op2 = PHI <phidef, inv>
3675 : _1 = (int) bit_17;
3676 : _3 = 1 << _1;
3677 : op1 = ~_3;
3678 : phidef = op1 & op2; */
3679 20819 : if (!gimple_bitwise_induction_p (phidef, &match_op[0], NULL)
3680 102 : || TREE_CODE (match_op[2]) != SSA_NAME
3681 102 : || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[2])))
3682 102 : || gimple_bb (header_phi) != loop->header
3683 20919 : || gimple_phi_num_args (header_phi) != 2)
3684 : return NULL_TREE;
3685 :
3686 100 : if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
3687 : return NULL_TREE;
3688 :
3689 100 : bitwise_scev = analyze_scalar_evolution (loop, match_op[1]);
3690 100 : bitwise_scev = instantiate_parameters (loop, bitwise_scev);
3691 :
3692 : /* Make sure bits is in range of type precision. */
3693 100 : if (TREE_CODE (bitwise_scev) != POLYNOMIAL_CHREC
3694 100 : || !INTEGRAL_TYPE_P (TREE_TYPE (bitwise_scev))
3695 100 : || !tree_fits_uhwi_p (CHREC_LEFT (bitwise_scev))
3696 100 : || tree_to_uhwi (CHREC_LEFT (bitwise_scev)) >= TYPE_PRECISION (type)
3697 200 : || !tree_fits_shwi_p (CHREC_RIGHT (bitwise_scev)))
3698 : return NULL_TREE;
3699 :
3700 100 : enum bit_op_kind
3701 : {
3702 : INDUCTION_BIT_CLEAR,
3703 : INDUCTION_BIT_IOR,
3704 : INDUCTION_BIT_XOR,
3705 : INDUCTION_BIT_RESET,
3706 : INDUCTION_ZERO,
3707 : INDUCTION_ALL
3708 : };
3709 :
3710 100 : enum bit_op_kind induction_kind;
3711 100 : enum tree_code code1
3712 100 : = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (phidef));
3713 100 : enum tree_code code2
3714 100 : = gimple_assign_rhs_code (SSA_NAME_DEF_STMT (match_op[0]));
3715 :
3716 : /* BIT_CLEAR: A &= ~(1 << bit)
3717 : BIT_RESET: A ^= (1 << bit).
3718 : BIT_IOR: A |= (1 << bit)
3719 : BIT_ZERO: A &= (1 << bit)
3720 : BIT_ALL: A |= ~(1 << bit)
3721 : BIT_XOR: A ^= ~(1 << bit).
3722 : bit is induction variable. */
3723 100 : switch (code1)
3724 : {
3725 27 : case BIT_AND_EXPR:
3726 27 : induction_kind = code2 == BIT_NOT_EXPR
3727 27 : ? INDUCTION_BIT_CLEAR
3728 : : INDUCTION_ZERO;
3729 : break;
3730 49 : case BIT_IOR_EXPR:
3731 49 : induction_kind = code2 == BIT_NOT_EXPR
3732 49 : ? INDUCTION_ALL
3733 : : INDUCTION_BIT_IOR;
3734 : break;
3735 12 : case BIT_XOR_EXPR:
3736 12 : induction_kind = code2 == BIT_NOT_EXPR
3737 12 : ? INDUCTION_BIT_XOR
3738 : : INDUCTION_BIT_RESET;
3739 : break;
3740 : /* A ^ ~(1 << bit) is equal to ~(A ^ (1 << bit)). */
3741 12 : case BIT_NOT_EXPR:
3742 12 : gcc_assert (code2 == BIT_XOR_EXPR);
3743 : induction_kind = INDUCTION_BIT_XOR;
3744 : break;
3745 0 : default:
3746 0 : gcc_unreachable ();
3747 : }
3748 :
3749 37 : if (induction_kind == INDUCTION_ZERO)
3750 12 : return build_zero_cst (type);
3751 88 : if (induction_kind == INDUCTION_ALL)
3752 12 : return build_all_ones_cst (type);
3753 :
3754 152 : wide_int bits = wi::zero (TYPE_PRECISION (type));
3755 76 : HOST_WIDE_INT bit_start = tree_to_shwi (CHREC_LEFT (bitwise_scev));
3756 76 : HOST_WIDE_INT step = tree_to_shwi (CHREC_RIGHT (bitwise_scev));
3757 76 : HOST_WIDE_INT bit_final = bit_start + step * niter;
3758 :
3759 : /* bit_start, bit_final in range of [0,TYPE_PRECISION)
3760 : implies all bits are set in range. */
3761 76 : if (bit_final >= TYPE_PRECISION (type)
3762 76 : || bit_final < 0)
3763 : return NULL_TREE;
3764 :
3765 : /* Loop tripcount should be niter + 1. */
3766 1296 : for (unsigned i = 0; i != niter + 1; i++)
3767 : {
3768 1220 : bits = wi::set_bit (bits, bit_start);
3769 1220 : bit_start += step;
3770 : }
3771 :
3772 76 : bool inverted = false;
3773 76 : switch (induction_kind)
3774 : {
3775 : case INDUCTION_BIT_CLEAR:
3776 : code1 = BIT_AND_EXPR;
3777 : inverted = true;
3778 : break;
3779 : case INDUCTION_BIT_IOR:
3780 : code1 = BIT_IOR_EXPR;
3781 : break;
3782 : case INDUCTION_BIT_RESET:
3783 : code1 = BIT_XOR_EXPR;
3784 : break;
3785 : /* A ^= ~(1 << bit) is special, when loop tripcount is even,
3786 : it's equal to A ^= bits, else A ^= ~bits. */
3787 12 : case INDUCTION_BIT_XOR:
3788 12 : code1 = BIT_XOR_EXPR;
3789 12 : if (niter % 2 == 0)
3790 : inverted = true;
3791 : break;
3792 : default:
3793 : gcc_unreachable ();
3794 : }
3795 :
3796 : if (inverted)
3797 19 : bits = wi::bit_not (bits);
3798 :
3799 76 : inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
3800 76 : return fold_build2 (code1, type, inv, wide_int_to_tree (type, bits));
3801 : }
3802 :
3803 : /* Match.pd function to match bitop with invariant expression
3804 : .i.e.
3805 : tmp_7 = _0 & _1; */
3806 : extern bool gimple_bitop_with_inv_p (tree, tree *, tree (*)(tree));
3807 :
3808 : /* Return the inductive expression of bitop with invariant if possible,
3809 : otherwise returns DEF. */
3810 : static tree
3811 75498 : analyze_and_compute_bitop_with_inv_effect (class loop* loop, tree phidef,
3812 : tree niter)
3813 : {
3814 75498 : tree match_op[2],inv;
3815 75498 : tree type = TREE_TYPE (phidef);
3816 75498 : gphi* header_phi = NULL;
3817 75498 : enum tree_code code;
3818 : /* match thing like op0 (match[0]), op1 (match[1]), phidef (PHIDEF)
3819 :
3820 : op1 = PHI <phidef, inv>
3821 : phidef = op0 & op1
3822 : if op0 is an invariant, it could change to
3823 : phidef = op0 & inv. */
3824 75498 : gimple *def;
3825 75498 : def = SSA_NAME_DEF_STMT (phidef);
3826 75498 : if (!(is_gimple_assign (def)
3827 28065 : && ((code = gimple_assign_rhs_code (def)), true)
3828 28065 : && (code == BIT_AND_EXPR || code == BIT_IOR_EXPR
3829 22347 : || code == BIT_XOR_EXPR)))
3830 : return NULL_TREE;
3831 :
3832 6476 : match_op[0] = gimple_assign_rhs1 (def);
3833 6476 : match_op[1] = gimple_assign_rhs2 (def);
3834 :
3835 6476 : if (expr_invariant_in_loop_p (loop, match_op[1]))
3836 239 : std::swap (match_op[0], match_op[1]);
3837 :
3838 6476 : if (TREE_CODE (match_op[1]) != SSA_NAME
3839 6476 : || !expr_invariant_in_loop_p (loop, match_op[0])
3840 337 : || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[1])))
3841 220 : || gimple_bb (header_phi) != loop->header
3842 6686 : || gimple_phi_num_args (header_phi) != 2)
3843 : return NULL_TREE;
3844 :
3845 210 : if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
3846 : return NULL_TREE;
3847 :
3848 205 : enum tree_code code1
3849 205 : = gimple_assign_rhs_code (def);
3850 :
3851 205 : if (code1 == BIT_XOR_EXPR)
3852 : {
3853 59 : tree niter_type = TREE_TYPE (niter);
3854 59 : tree one = build_one_cst (niter_type);
3855 59 : tree contributes = fold_build2 (BIT_XOR_EXPR, niter_type,
3856 : fold_build2 (BIT_AND_EXPR, niter_type,
3857 : niter, one),
3858 : one);
3859 : /* mask is all-ones when the invariant contributes, zero otherwise. */
3860 59 : tree mask = fold_build1 (NEGATE_EXPR, type,
3861 : fold_convert (type, contributes));
3862 59 : match_op[0] = fold_build2 (BIT_AND_EXPR, type, match_op[0], mask);
3863 : }
3864 :
3865 205 : inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
3866 205 : return fold_build2 (code1, type, inv, match_op[0]);
3867 : }
3868 :
3869 : /* Try to compute the final value of PHIDEF when PHIDEF is the result of a
3870 : loop-header PHI.
3871 :
3872 : This handles the nonzero-latch-count delayed-value form:
3873 :
3874 : y_phi = PHI <latch_arg (latch), init (preheader)>
3875 :
3876 : If the latch count is known to be nonzero, the final value is:
3877 :
3878 : latch_arg evaluated at iteration niter - 1
3879 :
3880 : Return NULL_TREE if the pattern does not apply. */
3881 : static tree
3882 42764 : compute_final_value_from_loop_phi_latch (class loop *loop,
3883 : class loop *ex_loop, gphi *header_phi, tree niter, bool* folded_casts)
3884 : {
3885 42764 : if (gimple_bb (header_phi) != loop->header
3886 45199 : || gimple_phi_num_args (header_phi) != 2)
3887 : return NULL_TREE;
3888 :
3889 : /* If niter is a symbolic value make sure it can never be zero, otherwise we
3890 : do a bad replacement. */
3891 2435 : if (!tree_expr_nonzero_p (niter))
3892 : return NULL_TREE;
3893 :
3894 1067 : tree latch_arg = PHI_ARG_DEF_FROM_EDGE (header_phi,
3895 : loop_latch_edge (loop));
3896 :
3897 1067 : tree ev = analyze_scalar_evolution_in_loop (ex_loop,
3898 : loop,
3899 : latch_arg,
3900 : folded_casts);
3901 1067 : if (ev == chrec_dont_know)
3902 : return NULL_TREE;
3903 :
3904 486 : bool invariant_p;
3905 486 : if (no_evolution_in_loop_p (ev, ex_loop->num, &invariant_p) && invariant_p)
3906 : return ev;
3907 14 : else if (TREE_CODE (ev) == POLYNOMIAL_CHREC
3908 14 : && get_chrec_loop (ev) == ex_loop)
3909 : {
3910 14 : tree niter_type = TREE_TYPE (niter);
3911 14 : tree prev_iter = fold_build2 (MINUS_EXPR,
3912 : niter_type,
3913 : niter,
3914 : build_one_cst (niter_type));
3915 :
3916 14 : tree res = chrec_apply (ex_loop->num, ev, prev_iter);
3917 14 : if (res == chrec_dont_know)
3918 : return NULL_TREE;
3919 :
3920 14 : if (chrec_contains_symbols_defined_in_loop (res, ex_loop->num))
3921 : {
3922 0 : res = instantiate_parameters (ex_loop, res);
3923 0 : if (res == chrec_dont_know)
3924 : return NULL_TREE;
3925 : }
3926 :
3927 14 : return res;
3928 : }
3929 : return NULL_TREE;
3930 : }
3931 :
3932 : /* Do final value replacement for LOOP, return true if we did anything. */
3933 :
3934 : bool
3935 695747 : final_value_replacement_loop (class loop *loop)
3936 : {
3937 : /* If we do not know exact number of iterations of the loop, we cannot
3938 : replace the final value. */
3939 695747 : edge exit = single_exit (loop);
3940 695747 : if (!exit)
3941 : return false;
3942 :
3943 462616 : class tree_niter_desc niter_desc;
3944 462616 : if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
3945 : return false;
3946 :
3947 348841 : tree niter = niter_desc.niter;
3948 348841 : if (niter == chrec_dont_know)
3949 : return false;
3950 :
3951 : /* Ensure that it is possible to insert new statements somewhere. */
3952 348841 : if (!single_pred_p (exit->dest))
3953 38249 : split_loop_exit_edge (exit);
3954 :
3955 : /* Set stmt insertion pointer. All stmts are inserted before this point. */
3956 :
3957 348841 : class loop *ex_loop
3958 697682 : = superloop_at_depth (loop,
3959 426391 : loop_depth (exit->dest->loop_father) + 1);
3960 :
3961 348841 : bool any = false;
3962 348841 : gphi_iterator psi;
3963 779556 : for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3964 : {
3965 430715 : gphi *phi = psi.phi ();
3966 430715 : tree rslt = PHI_RESULT (phi);
3967 430715 : tree phidef = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3968 430715 : tree def = phidef;
3969 860747 : if (virtual_operand_p (def))
3970 : {
3971 246312 : gsi_next (&psi);
3972 396652 : continue;
3973 : }
3974 :
3975 349330 : if (!POINTER_TYPE_P (TREE_TYPE (def))
3976 349171 : && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3977 : {
3978 73942 : gsi_next (&psi);
3979 73942 : continue;
3980 : }
3981 :
3982 110461 : bool folded_casts;
3983 110461 : def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3984 : &folded_casts);
3985 :
3986 110461 : tree bitinv_def, bit_def, phi_latch_final_value;
3987 110461 : unsigned HOST_WIDE_INT niter_num;
3988 :
3989 110461 : gphi *header_phi = TREE_CODE (phidef) == SSA_NAME
3990 110461 : ? dyn_cast<gphi*> (SSA_NAME_DEF_STMT (phidef))
3991 : : NULL;
3992 :
3993 110461 : if (def != chrec_dont_know)
3994 34963 : def = compute_overall_effect_of_inner_loop (ex_loop, def);
3995 :
3996 : /* Handle bitop with invariant induction expression.
3997 :
3998 : .i.e
3999 : for (int i =0 ;i < 32; i++)
4000 : tmp &= bit2;
4001 : if bit2 is an invariant in loop which could simple to
4002 : tmp &= bit2. */
4003 150996 : else if ((bitinv_def
4004 75498 : = analyze_and_compute_bitop_with_inv_effect (loop,
4005 : phidef, niter)))
4006 : def = bitinv_def;
4007 :
4008 : /* Handle bitwise induction expression.
4009 :
4010 : .i.e.
4011 : for (int i = 0; i != 64; i+=3)
4012 : res &= ~(1UL << i);
4013 :
4014 : RES can't be analyzed out by SCEV because it is not polynomially
4015 : expressible, but in fact final value of RES can be replaced by
4016 : RES & CONSTANT where CONSTANT all ones with bit {0,3,6,9,... ,63}
4017 : being cleared, similar for BIT_IOR_EXPR/BIT_XOR_EXPR. */
4018 75293 : else if (tree_fits_uhwi_p (niter)
4019 31386 : && (niter_num = tree_to_uhwi (niter)) != 0
4020 31371 : && niter_num < TYPE_PRECISION (TREE_TYPE (phidef))
4021 75293 : && (bit_def
4022 20819 : = analyze_and_compute_bitwise_induction_effect (loop,
4023 : phidef,
4024 : niter_num)))
4025 : def = bit_def;
4026 :
4027 75193 : else if (header_phi
4028 45239 : && integer_zerop (niter_desc.may_be_zero)
4029 75193 : && (phi_latch_final_value
4030 42764 : = compute_final_value_from_loop_phi_latch (loop,
4031 : ex_loop,
4032 : header_phi,
4033 : niter,
4034 : &folded_casts)))
4035 : def = phi_latch_final_value;
4036 :
4037 110461 : bool cond_overflow_p;
4038 110461 : if (!tree_does_not_contain_chrecs (def)
4039 35166 : || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
4040 : /* Moving the computation from the loop may prolong life range
4041 : of some ssa names, which may cause problems if they appear
4042 : on abnormal edges. */
4043 35166 : || contains_abnormal_ssa_name_p (def)
4044 : /* Do not emit expensive expressions. The rationale is that
4045 : when someone writes a code like
4046 :
4047 : while (n > 45) n -= 45;
4048 :
4049 : he probably knows that n is not large, and does not want it
4050 : to be turned into n %= 45. */
4051 145627 : || expression_expensive_p (def, &cond_overflow_p))
4052 : {
4053 76398 : if (dump_file && (dump_flags & TDF_DETAILS))
4054 : {
4055 60 : fprintf (dump_file, "not replacing:\n ");
4056 60 : print_gimple_stmt (dump_file, phi, 0);
4057 60 : fprintf (dump_file, "\n");
4058 : }
4059 76398 : gsi_next (&psi);
4060 76398 : continue;
4061 : }
4062 :
4063 : /* Eliminate the PHI node and replace it by a computation outside
4064 : the loop. */
4065 34063 : if (dump_file)
4066 : {
4067 148 : fprintf (dump_file, "\nfinal value replacement:\n ");
4068 148 : print_gimple_stmt (dump_file, phi, 0);
4069 148 : fprintf (dump_file, " with expr: ");
4070 148 : print_generic_expr (dump_file, def);
4071 148 : fprintf (dump_file, "\n");
4072 : }
4073 34063 : any = true;
4074 : /* ??? Here we'd like to have a unshare_expr that would assign
4075 : shared sub-trees to new temporary variables either gimplified
4076 : to a GIMPLE sequence or to a statement list (keeping this a
4077 : GENERIC interface). */
4078 34063 : def = unshare_expr (def);
4079 34063 : auto loc = gimple_phi_arg_location (phi, exit->dest_idx);
4080 :
4081 : /* Create the replacement statements. */
4082 34063 : gimple_seq stmts;
4083 34063 : def = force_gimple_operand (def, &stmts, false, NULL_TREE);
4084 :
4085 : /* Propagate constants immediately, but leave an unused initialization
4086 : around to avoid invalidating the SCEV cache. */
4087 41444 : if (CONSTANT_CLASS_P (def) && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rslt))
4088 7380 : replace_uses_by (rslt, def);
4089 :
4090 : /* Remove the old phi after the gimplification to make sure the
4091 : SSA name is defined by a statement so that fold_stmt during
4092 : the gimplification does not crash. */
4093 34063 : remove_phi_node (&psi, false);
4094 34063 : gassign *ass = gimple_build_assign (rslt, def);
4095 34063 : gimple_set_location (ass, loc);
4096 34063 : gimple_seq_add_stmt (&stmts, ass);
4097 :
4098 : /* If def's type has undefined overflow and there were folded
4099 : casts, rewrite all stmts added for def into arithmetics
4100 : with defined overflow behavior. */
4101 34063 : if ((folded_casts
4102 429 : && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
4103 726 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
4104 34492 : || cond_overflow_p)
4105 : {
4106 2197 : gimple_stmt_iterator gsi2;
4107 2197 : gsi2 = gsi_start (stmts);
4108 20321 : while (!gsi_end_p (gsi2))
4109 : {
4110 18124 : if (gimple_needing_rewrite_undefined (gsi_stmt (gsi2)))
4111 550 : rewrite_to_defined_unconditional (&gsi2);
4112 18124 : gsi_next (&gsi2);
4113 : }
4114 : }
4115 34063 : gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
4116 34063 : gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
4117 34063 : if (dump_file)
4118 : {
4119 148 : fprintf (dump_file, " final stmt:\n ");
4120 148 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (rslt), 0);
4121 148 : fprintf (dump_file, "\n");
4122 : }
4123 :
4124 : /* Re-fold immediate uses of the replaced def, but avoid
4125 : CFG manipulations from this function. For now only do
4126 : a single-level re-folding, not re-folding uses of
4127 : folded uses. */
4128 34063 : if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rslt))
4129 : {
4130 34062 : gimple *use_stmt;
4131 34062 : imm_use_iterator imm_iter;
4132 34062 : auto_vec<gimple *, 4> to_fold;
4133 68145 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, rslt)
4134 34083 : if (!stmt_can_throw_internal (cfun, use_stmt))
4135 34079 : to_fold.safe_push (use_stmt);
4136 : /* Delay folding until after the immediate use walk is completed
4137 : as we have an active ranger and that might walk immediate
4138 : uses of rslt again. See PR122502. */
4139 136265 : for (gimple *use_stmt : to_fold)
4140 : {
4141 34079 : gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
4142 34079 : if (fold_stmt (&gsi, follow_all_ssa_edges))
4143 1894 : update_stmt (gsi_stmt (gsi));
4144 : }
4145 34062 : }
4146 : }
4147 :
4148 : return any;
4149 695747 : }
4150 :
4151 : #include "gt-tree-scalar-evolution.h"
|
