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