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