]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/tree-scalar-evolution.c
re PR fortran/90738 (gfortran.dg/pointer_array_10.f90 etc. FAIL)
[thirdparty/gcc.git] / gcc / tree-scalar-evolution.c
CommitLineData
e9eb809d 1/* Scalar evolution detector.
a5544970 2 Copyright (C) 2003-2019 Free Software Foundation, Inc.
e9eb809d
ZD
3 Contributed by Sebastian Pop <s.pop@laposte.net>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9dcd6f09 9Software Foundation; either version 3, or (at your option) any later
e9eb809d
ZD
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
9dcd6f09
NC
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
e9eb809d 20
b8698a0f
L
21/*
22 Description:
23
9baba81b
SP
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).
b8698a0f 44
9baba81b 45 A short sketch of the algorithm is:
b8698a0f 46
9baba81b
SP
47 Given a scalar variable to be analyzed, follow the SSA edge to
48 its definition:
b8698a0f 49
726a989a 50 - When the definition is a GIMPLE_ASSIGN: if the right hand side
9baba81b 51 (RHS) of the definition cannot be statically analyzed, the answer
b8698a0f 52 of the analyzer is: "don't know".
9baba81b
SP
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:
b8698a0f 74
9baba81b 75 Example 1: Illustration of the basic algorithm.
b8698a0f 76
9baba81b
SP
77 | a = 3
78 | loop_1
79 | b = phi (a, c)
80 | c = b + 1
81 | if (c > 10) exit_loop
82 | endloop
b8698a0f 83
9baba81b
SP
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
3f227a8c 104 instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
9baba81b
SP
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:
b8698a0f 114
9baba81b
SP
115 a -> 3
116 b -> {3, +, 1}_1
117 c -> {4, +, 1}_1
b8698a0f
L
118
119 or in terms of a C program:
120
9baba81b
SP
121 | a = 3
122 | for (x = 0; x <= 7; x++)
123 | {
124 | b = x + 3
125 | c = x + 4
126 | }
b8698a0f 127
3f227a8c 128 Example 2a: Illustration of the algorithm on nested loops.
b8698a0f 129
9baba81b
SP
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
b8698a0f 138
9baba81b
SP
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
b8698a0f
L
141 loop-phi-node, and its analysis as in Example 1, gives:
142
9baba81b
SP
143 b -> {c, +, 3}_2
144 d -> {c + 3, +, 3}_2
b8698a0f 145
9baba81b
SP
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
b8698a0f
L
152 equal to "+32", and the result is:
153
9baba81b
SP
154 a -> {1, +, 32}_1
155 c -> {3, +, 32}_1
3f227a8c
JS
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:
a213b219
SP
177 instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
178 The result of this call is {{0, +, 1}_1, +, 1}_2.
3f227a8c 179
9baba81b 180 Example 3: Higher degree polynomials.
b8698a0f 181
9baba81b
SP
182 | loop_1
183 | a = phi (2, b)
184 | c = phi (5, d)
185 | b = a + 1
186 | d = c + a
187 | endloop
b8698a0f 188
9baba81b
SP
189 a -> {2, +, 1}_1
190 b -> {3, +, 1}_1
191 c -> {5, +, a}_1
192 d -> {5 + a, +, a}_1
b8698a0f 193
3f227a8c
JS
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
b8698a0f 196
9baba81b 197 Example 4: Lucas, Fibonacci, or mixers in general.
b8698a0f 198
9baba81b
SP
199 | loop_1
200 | a = phi (1, b)
201 | c = phi (3, d)
202 | b = c
203 | d = c + a
204 | endloop
b8698a0f 205
9baba81b
SP
206 a -> (1, c)_1
207 c -> {3, +, a}_1
b8698a0f 208
9baba81b
SP
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)".
b8698a0f 214
9baba81b
SP
215 The symbolic chrec representation contains all the semantics of the
216 original code. What is more difficult is to use this information.
b8698a0f 217
9baba81b 218 Example 5: Flip-flops, or exchangers.
b8698a0f 219
9baba81b
SP
220 | loop_1
221 | a = phi (1, b)
222 | c = phi (3, d)
223 | b = c
224 | d = a
225 | endloop
b8698a0f 226
9baba81b
SP
227 a -> (1, c)_1
228 c -> (3, a)_1
b8698a0f 229
9baba81b 230 Based on these symbolic chrecs, it is possible to refine this
b8698a0f
L
231 information into the more precise PERIODIC_CHRECs:
232
9baba81b
SP
233 a -> |1, 3|_1
234 c -> |3, 1|_1
b8698a0f 235
9baba81b 236 This transformation is not yet implemented.
b8698a0f 237
9baba81b 238 Further readings:
b8698a0f 239
9baba81b
SP
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.
b8698a0f 247
9baba81b
SP
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
e9eb809d
ZD
256#include "config.h"
257#include "system.h"
258#include "coretypes.h"
c7131fb2 259#include "backend.h"
06a6b46a 260#include "target.h"
957060b5 261#include "rtl.h"
06a6b46a 262#include "optabs-query.h"
cf2d1b38 263#include "tree.h"
c7131fb2 264#include "gimple.h"
c7131fb2 265#include "ssa.h"
957060b5 266#include "gimple-pretty-print.h"
c7131fb2 267#include "fold-const.h"
45b0be94 268#include "gimplify.h"
5be5c238 269#include "gimple-iterator.h"
18f429e2 270#include "gimplify-me.h"
442b4905 271#include "tree-cfg.h"
e28030cf
AM
272#include "tree-ssa-loop-ivopts.h"
273#include "tree-ssa-loop-manip.h"
274#include "tree-ssa-loop-niter.h"
442b4905 275#include "tree-ssa-loop.h"
7a300452 276#include "tree-ssa.h"
e9eb809d
ZD
277#include "cfgloop.h"
278#include "tree-chrec.h"
b83b5507 279#include "tree-affine.h"
e9eb809d 280#include "tree-scalar-evolution.h"
7ee2468b 281#include "dumpfile.h"
c59dabbe 282#include "params.h"
744730a4 283#include "tree-ssa-propagate.h"
19e51b40 284#include "gimple-fold.h"
24545562 285#include "tree-into-ssa.h"
5126ae0c 286#include "builtins.h"
06a6b46a 287#include "case-cfn-macros.h"
9baba81b 288
fb1fe1f3 289static tree analyze_scalar_evolution_1 (struct loop *, tree);
bef28ced
JL
290static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
291 tree var);
9baba81b 292
a3cc13cc
RB
293/* The cached information about an SSA name with version NAME_VERSION,
294 claiming that below basic block with index INSTANTIATED_BELOW, the
295 value of the SSA name can be expressed as CHREC. */
9baba81b 296
907dadbd 297struct GTY((for_user)) scev_info_str {
a3cc13cc
RB
298 unsigned int name_version;
299 int instantiated_below;
9baba81b
SP
300 tree chrec;
301};
302
303/* Counters for the scev database. */
304static unsigned nb_set_scev = 0;
305static unsigned nb_get_scev = 0;
306
307/* The following trees are unique elements. Thus the comparison of
308 another element to these elements should be done on the pointer to
309 these trees, and not on their value. */
310
311/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
312tree chrec_not_analyzed_yet;
313
314/* Reserved to the cases where the analyzer has detected an
315 undecidable property at compile time. */
316tree chrec_dont_know;
317
318/* When the analyzer has detected that a property will never
319 happen, then it qualifies it with chrec_known. */
320tree chrec_known;
321
ca752f39 322struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
907dadbd
TS
323{
324 static hashval_t hash (scev_info_str *i);
325 static bool equal (const scev_info_str *a, const scev_info_str *b);
326};
327
328static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
9baba81b
SP
329
330\f
a213b219 331/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
9baba81b
SP
332
333static inline struct scev_info_str *
a213b219 334new_scev_info_str (basic_block instantiated_below, tree var)
9baba81b
SP
335{
336 struct scev_info_str *res;
b8698a0f 337
766090c2 338 res = ggc_alloc<scev_info_str> ();
a3cc13cc 339 res->name_version = SSA_NAME_VERSION (var);
9baba81b 340 res->chrec = chrec_not_analyzed_yet;
a3cc13cc 341 res->instantiated_below = instantiated_below->index;
a213b219 342
9baba81b
SP
343 return res;
344}
345
346/* Computes a hash function for database element ELT. */
347
907dadbd
TS
348hashval_t
349scev_info_hasher::hash (scev_info_str *elt)
9baba81b 350{
a3cc13cc 351 return elt->name_version ^ elt->instantiated_below;
9baba81b
SP
352}
353
354/* Compares database elements E1 and E2. */
355
907dadbd
TS
356bool
357scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
9baba81b 358{
a3cc13cc 359 return (elt1->name_version == elt2->name_version
a213b219 360 && elt1->instantiated_below == elt2->instantiated_below);
9baba81b
SP
361}
362
a213b219
SP
363/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
364 A first query on VAR returns chrec_not_analyzed_yet. */
9baba81b
SP
365
366static tree *
a213b219 367find_var_scev_info (basic_block instantiated_below, tree var)
9baba81b
SP
368{
369 struct scev_info_str *res;
370 struct scev_info_str tmp;
9baba81b 371
a3cc13cc
RB
372 tmp.name_version = SSA_NAME_VERSION (var);
373 tmp.instantiated_below = instantiated_below->index;
907dadbd 374 scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
9baba81b
SP
375
376 if (!*slot)
a213b219 377 *slot = new_scev_info_str (instantiated_below, var);
907dadbd 378 res = *slot;
9baba81b
SP
379
380 return &res->chrec;
381}
382
577d6588
RB
383
384/* Hashtable helpers for a temporary hash-table used when
385 analyzing a scalar evolution, instantiating a CHREC or
386 resolving mixers. */
387
388struct instantiate_cache_type
389{
390 htab_t map;
391 vec<scev_info_str> entries;
392
393 instantiate_cache_type () : map (NULL), entries (vNULL) {}
394 ~instantiate_cache_type ();
395 tree get (unsigned slot) { return entries[slot].chrec; }
396 void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; }
397};
398
399instantiate_cache_type::~instantiate_cache_type ()
400{
401 if (map != NULL)
402 {
403 htab_delete (map);
404 entries.release ();
405 }
406}
407
408/* Cache to avoid infinite recursion when instantiating an SSA name.
409 Live during the outermost analyze_scalar_evolution, instantiate_scev
410 or resolve_mixers call. */
411static instantiate_cache_type *global_cache;
412
413
9baba81b
SP
414/* Return true when CHREC contains symbolic names defined in
415 LOOP_NB. */
416
b8698a0f 417bool
ed7a4b4b 418chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
9baba81b 419{
5039610b
SL
420 int i, n;
421
9baba81b
SP
422 if (chrec == NULL_TREE)
423 return false;
424
ad6003f2 425 if (is_gimple_min_invariant (chrec))
9baba81b
SP
426 return false;
427
9baba81b
SP
428 if (TREE_CODE (chrec) == SSA_NAME)
429 {
355fe088 430 gimple *def;
492e5456
SP
431 loop_p def_loop, loop;
432
433 if (SSA_NAME_IS_DEFAULT_DEF (chrec))
434 return false;
435
436 def = SSA_NAME_DEF_STMT (chrec);
437 def_loop = loop_containing_stmt (def);
0fc822d0 438 loop = get_loop (cfun, loop_nb);
9baba81b
SP
439
440 if (def_loop == NULL)
441 return false;
442
443 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
444 return true;
445
446 return false;
447 }
448
5039610b
SL
449 n = TREE_OPERAND_LENGTH (chrec);
450 for (i = 0; i < n; i++)
b8698a0f 451 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
5039610b
SL
452 loop_nb))
453 return true;
454 return false;
9baba81b
SP
455}
456
457/* Return true when PHI is a loop-phi-node. */
458
459static bool
355fe088 460loop_phi_node_p (gimple *phi)
9baba81b
SP
461{
462 /* The implementation of this function is based on the following
463 property: "all the loop-phi-nodes of a loop are contained in the
464 loop's header basic block". */
465
726a989a 466 return loop_containing_stmt (phi)->header == gimple_bb (phi);
9baba81b
SP
467}
468
469/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
470 In general, in the case of multivariate evolutions we want to get
471 the evolution in different loops. LOOP specifies the level for
472 which to get the evolution.
b8698a0f 473
9baba81b 474 Example:
b8698a0f 475
9baba81b
SP
476 | for (j = 0; j < 100; j++)
477 | {
478 | for (k = 0; k < 100; k++)
479 | {
b8698a0f 480 | i = k + j; - Here the value of i is a function of j, k.
9baba81b 481 | }
b8698a0f 482 | ... = i - Here the value of i is a function of j.
9baba81b 483 | }
b8698a0f
L
484 | ... = i - Here the value of i is a scalar.
485
486 Example:
487
9baba81b
SP
488 | i_0 = ...
489 | loop_1 10 times
490 | i_1 = phi (i_0, i_2)
491 | i_2 = i_1 + 2
492 | endloop
b8698a0f 493
9baba81b
SP
494 This loop has the same effect as:
495 LOOP_1 has the same effect as:
b8698a0f 496
9baba81b 497 | i_1 = i_0 + 20
b8698a0f
L
498
499 The overall effect of the loop, "i_0 + 20" in the previous example,
500 is obtained by passing in the parameters: LOOP = 1,
9baba81b
SP
501 EVOLUTION_FN = {i_0, +, 2}_1.
502*/
b8698a0f 503
42e6eec5 504tree
9baba81b
SP
505compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
506{
507 bool val = false;
508
509 if (evolution_fn == chrec_dont_know)
510 return chrec_dont_know;
511
512 else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
513 {
677cc14d
ZD
514 struct loop *inner_loop = get_chrec_loop (evolution_fn);
515
516 if (inner_loop == loop
517 || flow_loop_nested_p (loop, inner_loop))
9baba81b 518 {
a14865db 519 tree nb_iter = number_of_latch_executions (inner_loop);
9baba81b
SP
520
521 if (nb_iter == chrec_dont_know)
522 return chrec_dont_know;
523 else
524 {
525 tree res;
526
9baba81b
SP
527 /* evolution_fn is the evolution function in LOOP. Get
528 its value in the nb_iter-th iteration. */
529 res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
42e6eec5
SP
530
531 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
532 res = instantiate_parameters (loop, res);
533
8c27b7d4 534 /* Continue the computation until ending on a parent of LOOP. */
9baba81b
SP
535 return compute_overall_effect_of_inner_loop (loop, res);
536 }
537 }
538 else
539 return evolution_fn;
540 }
b8698a0f 541
9baba81b
SP
542 /* If the evolution function is an invariant, there is nothing to do. */
543 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
544 return evolution_fn;
b8698a0f 545
9baba81b
SP
546 else
547 return chrec_dont_know;
548}
549
9baba81b
SP
550/* Associate CHREC to SCALAR. */
551
552static void
a213b219 553set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
9baba81b
SP
554{
555 tree *scalar_info;
b8698a0f 556
9baba81b
SP
557 if (TREE_CODE (scalar) != SSA_NAME)
558 return;
559
a213b219 560 scalar_info = find_var_scev_info (instantiated_below, scalar);
b8698a0f 561
9baba81b
SP
562 if (dump_file)
563 {
dfedbe40 564 if (dump_flags & TDF_SCEV)
9baba81b
SP
565 {
566 fprintf (dump_file, "(set_scalar_evolution \n");
a213b219
SP
567 fprintf (dump_file, " instantiated_below = %d \n",
568 instantiated_below->index);
9baba81b 569 fprintf (dump_file, " (scalar = ");
ef6cb4c7 570 print_generic_expr (dump_file, scalar);
9baba81b 571 fprintf (dump_file, ")\n (scalar_evolution = ");
ef6cb4c7 572 print_generic_expr (dump_file, chrec);
9baba81b
SP
573 fprintf (dump_file, "))\n");
574 }
575 if (dump_flags & TDF_STATS)
576 nb_set_scev++;
577 }
b8698a0f 578
9baba81b
SP
579 *scalar_info = chrec;
580}
581
a213b219
SP
582/* Retrieve the chrec associated to SCALAR instantiated below
583 INSTANTIATED_BELOW block. */
9baba81b
SP
584
585static tree
a213b219 586get_scalar_evolution (basic_block instantiated_below, tree scalar)
9baba81b
SP
587{
588 tree res;
b8698a0f 589
9baba81b
SP
590 if (dump_file)
591 {
dfedbe40 592 if (dump_flags & TDF_SCEV)
9baba81b
SP
593 {
594 fprintf (dump_file, "(get_scalar_evolution \n");
595 fprintf (dump_file, " (scalar = ");
ef6cb4c7 596 print_generic_expr (dump_file, scalar);
9baba81b
SP
597 fprintf (dump_file, ")\n");
598 }
599 if (dump_flags & TDF_STATS)
600 nb_get_scev++;
601 }
b8698a0f 602
5355943c
RB
603 if (VECTOR_TYPE_P (TREE_TYPE (scalar))
604 || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
605 /* For chrec_dont_know we keep the symbolic form. */
606 res = scalar;
607 else
608 switch (TREE_CODE (scalar))
609 {
610 case SSA_NAME:
611 if (SSA_NAME_IS_DEFAULT_DEF (scalar))
612 res = scalar;
613 else
614 res = *find_var_scev_info (instantiated_below, scalar);
615 break;
9baba81b 616
5355943c
RB
617 case REAL_CST:
618 case FIXED_CST:
619 case INTEGER_CST:
620 res = scalar;
621 break;
9baba81b 622
5355943c
RB
623 default:
624 res = chrec_not_analyzed_yet;
625 break;
626 }
b8698a0f 627
dfedbe40 628 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
629 {
630 fprintf (dump_file, " (scalar_evolution = ");
ef6cb4c7 631 print_generic_expr (dump_file, res);
9baba81b
SP
632 fprintf (dump_file, "))\n");
633 }
b8698a0f 634
9baba81b
SP
635 return res;
636}
637
638/* Helper function for add_to_evolution. Returns the evolution
639 function for an assignment of the form "a = b + c", where "a" and
640 "b" are on the strongly connected component. CHREC_BEFORE is the
641 information that we already have collected up to this point.
b8698a0f
L
642 TO_ADD is the evolution of "c".
643
9baba81b
SP
644 When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
645 evolution the expression TO_ADD, otherwise construct an evolution
646 part for this loop. */
647
648static tree
e2157b49 649add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
355fe088 650 gimple *at_stmt)
9baba81b 651{
e2157b49 652 tree type, left, right;
0fc822d0 653 struct loop *loop = get_loop (cfun, loop_nb), *chloop;
e2157b49 654
9baba81b
SP
655 switch (TREE_CODE (chrec_before))
656 {
657 case POLYNOMIAL_CHREC:
677cc14d
ZD
658 chloop = get_chrec_loop (chrec_before);
659 if (chloop == loop
660 || flow_loop_nested_p (chloop, loop))
9baba81b
SP
661 {
662 unsigned var;
e2157b49
SP
663
664 type = chrec_type (chrec_before);
b8698a0f 665
9baba81b 666 /* When there is no evolution part in this loop, build it. */
677cc14d 667 if (chloop != loop)
9baba81b
SP
668 {
669 var = loop_nb;
670 left = chrec_before;
7e0923cd
SP
671 right = SCALAR_FLOAT_TYPE_P (type)
672 ? build_real (type, dconst0)
673 : build_int_cst (type, 0);
9baba81b
SP
674 }
675 else
676 {
677 var = CHREC_VARIABLE (chrec_before);
678 left = CHREC_LEFT (chrec_before);
679 right = CHREC_RIGHT (chrec_before);
680 }
681
e2157b49 682 to_add = chrec_convert (type, to_add, at_stmt);
5be014d5
AP
683 right = chrec_convert_rhs (type, right, at_stmt);
684 right = chrec_fold_plus (chrec_type (right), right, to_add);
e2157b49 685 return build_polynomial_chrec (var, left, right);
9baba81b
SP
686 }
687 else
e2157b49 688 {
677cc14d
ZD
689 gcc_assert (flow_loop_nested_p (loop, chloop));
690
e2157b49
SP
691 /* Search the evolution in LOOP_NB. */
692 left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
693 to_add, at_stmt);
694 right = CHREC_RIGHT (chrec_before);
5be014d5 695 right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
e2157b49
SP
696 return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
697 left, right);
698 }
b8698a0f 699
9baba81b
SP
700 default:
701 /* These nodes do not depend on a loop. */
702 if (chrec_before == chrec_dont_know)
703 return chrec_dont_know;
e2157b49
SP
704
705 left = chrec_before;
5be014d5 706 right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
e2157b49 707 return build_polynomial_chrec (loop_nb, left, right);
9baba81b
SP
708 }
709}
710
711/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
b8698a0f
L
712 of LOOP_NB.
713
9baba81b
SP
714 Description (provided for completeness, for those who read code in
715 a plane, and for my poor 62 bytes brain that would have forgotten
716 all this in the next two or three months):
b8698a0f 717
9baba81b
SP
718 The algorithm of translation of programs from the SSA representation
719 into the chrecs syntax is based on a pattern matching. After having
720 reconstructed the overall tree expression for a loop, there are only
721 two cases that can arise:
b8698a0f 722
9baba81b
SP
723 1. a = loop-phi (init, a + expr)
724 2. a = loop-phi (init, expr)
b8698a0f 725
9baba81b
SP
726 where EXPR is either a scalar constant with respect to the analyzed
727 loop (this is a degree 0 polynomial), or an expression containing
728 other loop-phi definitions (these are higher degree polynomials).
b8698a0f 729
9baba81b 730 Examples:
b8698a0f
L
731
732 1.
9baba81b
SP
733 | init = ...
734 | loop_1
735 | a = phi (init, a + 5)
736 | endloop
b8698a0f
L
737
738 2.
9baba81b
SP
739 | inita = ...
740 | initb = ...
741 | loop_1
742 | a = phi (inita, 2 * b + 3)
743 | b = phi (initb, b + 1)
744 | endloop
b8698a0f
L
745
746 For the first case, the semantics of the SSA representation is:
747
9baba81b 748 | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
b8698a0f 749
9baba81b
SP
750 that is, there is a loop index "x" that determines the scalar value
751 of the variable during the loop execution. During the first
752 iteration, the value is that of the initial condition INIT, while
753 during the subsequent iterations, it is the sum of the initial
754 condition with the sum of all the values of EXPR from the initial
b8698a0f
L
755 iteration to the before last considered iteration.
756
9baba81b 757 For the second case, the semantics of the SSA program is:
b8698a0f 758
9baba81b
SP
759 | a (x) = init, if x = 0;
760 | expr (x - 1), otherwise.
b8698a0f 761
9baba81b 762 The second case corresponds to the PEELED_CHREC, whose syntax is
b8698a0f
L
763 close to the syntax of a loop-phi-node:
764
9baba81b 765 | phi (init, expr) vs. (init, expr)_x
b8698a0f 766
9baba81b 767 The proof of the translation algorithm for the first case is a
b8698a0f
L
768 proof by structural induction based on the degree of EXPR.
769
9baba81b
SP
770 Degree 0:
771 When EXPR is a constant with respect to the analyzed loop, or in
772 other words when EXPR is a polynomial of degree 0, the evolution of
773 the variable A in the loop is an affine function with an initial
774 condition INIT, and a step EXPR. In order to show this, we start
775 from the semantics of the SSA representation:
b8698a0f 776
9baba81b 777 f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
b8698a0f 778
9baba81b 779 and since "expr (j)" is a constant with respect to "j",
b8698a0f
L
780
781 f (x) = init + x * expr
782
9baba81b
SP
783 Finally, based on the semantics of the pure sum chrecs, by
784 identification we get the corresponding chrecs syntax:
b8698a0f
L
785
786 f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
9baba81b 787 f (x) -> {init, +, expr}_x
b8698a0f 788
9baba81b
SP
789 Higher degree:
790 Suppose that EXPR is a polynomial of degree N with respect to the
791 analyzed loop_x for which we have already determined that it is
792 written under the chrecs syntax:
b8698a0f 793
9baba81b 794 | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
b8698a0f 795
9baba81b 796 We start from the semantics of the SSA program:
b8698a0f 797
9baba81b
SP
798 | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
799 |
b8698a0f 800 | f (x) = init + \sum_{j = 0}^{x - 1}
9baba81b
SP
801 | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
802 |
b8698a0f
L
803 | f (x) = init + \sum_{j = 0}^{x - 1}
804 | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
9baba81b 805 |
b8698a0f
L
806 | f (x) = init + \sum_{k = 0}^{n - 1}
807 | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
9baba81b 808 |
b8698a0f
L
809 | f (x) = init + \sum_{k = 0}^{n - 1}
810 | (b_k * \binom{x}{k + 1})
9baba81b 811 |
b8698a0f
L
812 | f (x) = init + b_0 * \binom{x}{1} + ...
813 | + b_{n-1} * \binom{x}{n}
9baba81b 814 |
b8698a0f
L
815 | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
816 | + b_{n-1} * \binom{x}{n}
9baba81b 817 |
b8698a0f 818
9baba81b 819 And finally from the definition of the chrecs syntax, we identify:
b8698a0f
L
820 | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
821
9baba81b
SP
822 This shows the mechanism that stands behind the add_to_evolution
823 function. An important point is that the use of symbolic
824 parameters avoids the need of an analysis schedule.
b8698a0f 825
9baba81b 826 Example:
b8698a0f 827
9baba81b
SP
828 | inita = ...
829 | initb = ...
b8698a0f 830 | loop_1
9baba81b
SP
831 | a = phi (inita, a + 2 + b)
832 | b = phi (initb, b + 1)
833 | endloop
b8698a0f 834
9baba81b 835 When analyzing "a", the algorithm keeps "b" symbolically:
b8698a0f 836
9baba81b 837 | a -> {inita, +, 2 + b}_1
b8698a0f 838
9baba81b 839 Then, after instantiation, the analyzer ends on the evolution:
b8698a0f 840
9baba81b
SP
841 | a -> {inita, +, 2 + initb, +, 1}_1
842
843*/
844
b8698a0f 845static tree
e2157b49 846add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
355fe088 847 tree to_add, gimple *at_stmt)
9baba81b
SP
848{
849 tree type = chrec_type (to_add);
850 tree res = NULL_TREE;
b8698a0f 851
9baba81b
SP
852 if (to_add == NULL_TREE)
853 return chrec_before;
b8698a0f 854
9baba81b
SP
855 /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
856 instantiated at this point. */
857 if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
858 /* This should not happen. */
859 return chrec_dont_know;
b8698a0f 860
dfedbe40 861 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
862 {
863 fprintf (dump_file, "(add_to_evolution \n");
864 fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
865 fprintf (dump_file, " (chrec_before = ");
ef6cb4c7 866 print_generic_expr (dump_file, chrec_before);
9baba81b 867 fprintf (dump_file, ")\n (to_add = ");
ef6cb4c7 868 print_generic_expr (dump_file, to_add);
9baba81b
SP
869 fprintf (dump_file, ")\n");
870 }
871
872 if (code == MINUS_EXPR)
9d2b0e12
VR
873 to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
874 ? build_real (type, dconstm1)
875 : build_int_cst_type (type, -1));
9baba81b 876
e2157b49 877 res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
9baba81b 878
dfedbe40 879 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
880 {
881 fprintf (dump_file, " (res = ");
ef6cb4c7 882 print_generic_expr (dump_file, res);
9baba81b
SP
883 fprintf (dump_file, "))\n");
884 }
885
886 return res;
887}
888
9baba81b
SP
889\f
890
891/* This section selects the loops that will be good candidates for the
892 scalar evolution analysis. For the moment, greedily select all the
893 loop nests we could analyze. */
894
9baba81b
SP
895/* For a loop with a single exit edge, return the COND_EXPR that
896 guards the exit edge. If the expression is too difficult to
897 analyze, then give up. */
898
538dd0b7 899gcond *
22ea9ec0 900get_loop_exit_condition (const struct loop *loop)
9baba81b 901{
538dd0b7 902 gcond *res = NULL;
ac8f6c69 903 edge exit_edge = single_exit (loop);
b8698a0f 904
dfedbe40 905 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b 906 fprintf (dump_file, "(get_loop_exit_condition \n ");
b8698a0f 907
82b85a85 908 if (exit_edge)
9baba81b 909 {
355fe088 910 gimple *stmt;
b8698a0f 911
726a989a 912 stmt = last_stmt (exit_edge->src);
19d4e4d6 913 if (gcond *cond_stmt = safe_dyn_cast <gcond *> (stmt))
538dd0b7 914 res = cond_stmt;
9baba81b 915 }
b8698a0f 916
dfedbe40 917 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b 918 {
ef6cb4c7 919 print_gimple_stmt (dump_file, res, 0);
9baba81b
SP
920 fprintf (dump_file, ")\n");
921 }
b8698a0f 922
9baba81b
SP
923 return res;
924}
925
9baba81b
SP
926\f
927/* Depth first search algorithm. */
928
a79683d5 929enum t_bool {
c59dabbe
SP
930 t_false,
931 t_true,
932 t_dont_know
a79683d5 933};
c59dabbe
SP
934
935
355fe088 936static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *,
538dd0b7 937 tree *, int);
9baba81b 938
726a989a 939/* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
9baba81b
SP
940 Return true if the strongly connected component has been found. */
941
c59dabbe 942static t_bool
355fe088 943follow_ssa_edge_binary (struct loop *loop, gimple *at_stmt,
726a989a 944 tree type, tree rhs0, enum tree_code code, tree rhs1,
538dd0b7
DM
945 gphi *halting_phi, tree *evolution_of_loop,
946 int limit)
9baba81b 947{
c59dabbe 948 t_bool res = t_false;
b2a93c0a 949 tree evol;
726a989a 950
5be014d5 951 switch (code)
9baba81b 952 {
5be014d5 953 case POINTER_PLUS_EXPR:
9baba81b 954 case PLUS_EXPR:
9baba81b
SP
955 if (TREE_CODE (rhs0) == SSA_NAME)
956 {
957 if (TREE_CODE (rhs1) == SSA_NAME)
958 {
b8698a0f 959 /* Match an assignment under the form:
9baba81b 960 "a = b + c". */
b8698a0f 961
9e824336
ZD
962 /* We want only assignments of form "name + name" contribute to
963 LIMIT, as the other cases do not necessarily contribute to
964 the complexity of the expression. */
965 limit++;
966
b2a93c0a 967 evol = *evolution_of_loop;
b9b79ba4 968 evol = add_to_evolution
b8698a0f
L
969 (loop->num,
970 chrec_convert (type, evol, at_stmt),
5be014d5 971 code, rhs1, at_stmt);
b9b79ba4
RB
972 res = follow_ssa_edge
973 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
974 if (res == t_true)
975 *evolution_of_loop = evol;
c59dabbe 976 else if (res == t_false)
9baba81b 977 {
b9b79ba4
RB
978 *evolution_of_loop = add_to_evolution
979 (loop->num,
980 chrec_convert (type, *evolution_of_loop, at_stmt),
981 code, rhs0, at_stmt);
b8698a0f
L
982 res = follow_ssa_edge
983 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
c59dabbe 984 evolution_of_loop, limit);
c59dabbe 985 if (res == t_true)
b9b79ba4 986 ;
c59dabbe
SP
987 else if (res == t_dont_know)
988 *evolution_of_loop = chrec_dont_know;
9baba81b 989 }
c59dabbe
SP
990
991 else if (res == t_dont_know)
992 *evolution_of_loop = chrec_dont_know;
9baba81b 993 }
b8698a0f 994
9baba81b
SP
995 else
996 {
b8698a0f 997 /* Match an assignment under the form:
9baba81b 998 "a = b + ...". */
b9b79ba4
RB
999 *evolution_of_loop = add_to_evolution
1000 (loop->num, chrec_convert (type, *evolution_of_loop,
1001 at_stmt),
1002 code, rhs1, at_stmt);
b8698a0f
L
1003 res = follow_ssa_edge
1004 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
c59dabbe
SP
1005 evolution_of_loop, limit);
1006 if (res == t_true)
b9b79ba4 1007 ;
c59dabbe
SP
1008 else if (res == t_dont_know)
1009 *evolution_of_loop = chrec_dont_know;
9baba81b
SP
1010 }
1011 }
b8698a0f 1012
9baba81b
SP
1013 else if (TREE_CODE (rhs1) == SSA_NAME)
1014 {
b8698a0f 1015 /* Match an assignment under the form:
9baba81b 1016 "a = ... + c". */
b9b79ba4
RB
1017 *evolution_of_loop = add_to_evolution
1018 (loop->num, chrec_convert (type, *evolution_of_loop,
1019 at_stmt),
1020 code, rhs0, at_stmt);
b8698a0f
L
1021 res = follow_ssa_edge
1022 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
c59dabbe
SP
1023 evolution_of_loop, limit);
1024 if (res == t_true)
b9b79ba4 1025 ;
c59dabbe
SP
1026 else if (res == t_dont_know)
1027 *evolution_of_loop = chrec_dont_know;
9baba81b
SP
1028 }
1029
1030 else
b8698a0f 1031 /* Otherwise, match an assignment under the form:
9baba81b
SP
1032 "a = ... + ...". */
1033 /* And there is nothing to do. */
c59dabbe 1034 res = t_false;
9baba81b 1035 break;
b8698a0f 1036
9baba81b
SP
1037 case MINUS_EXPR:
1038 /* This case is under the form "opnd0 = rhs0 - rhs1". */
9baba81b 1039 if (TREE_CODE (rhs0) == SSA_NAME)
9baba81b 1040 {
b8698a0f 1041 /* Match an assignment under the form:
f8e9d512 1042 "a = b - ...". */
9e824336
ZD
1043
1044 /* We want only assignments of form "name - name" contribute to
1045 LIMIT, as the other cases do not necessarily contribute to
1046 the complexity of the expression. */
1047 if (TREE_CODE (rhs1) == SSA_NAME)
1048 limit++;
1049
b9b79ba4
RB
1050 *evolution_of_loop = add_to_evolution
1051 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1052 MINUS_EXPR, rhs1, at_stmt);
b8698a0f 1053 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
c59dabbe
SP
1054 evolution_of_loop, limit);
1055 if (res == t_true)
b9b79ba4 1056 ;
c59dabbe
SP
1057 else if (res == t_dont_know)
1058 *evolution_of_loop = chrec_dont_know;
9baba81b 1059 }
9baba81b 1060 else
b8698a0f 1061 /* Otherwise, match an assignment under the form:
9baba81b
SP
1062 "a = ... - ...". */
1063 /* And there is nothing to do. */
c59dabbe 1064 res = t_false;
9baba81b 1065 break;
726a989a
RB
1066
1067 default:
1068 res = t_false;
1069 }
1070
1071 return res;
1072}
b8698a0f 1073
726a989a
RB
1074/* Follow the ssa edge into the expression EXPR.
1075 Return true if the strongly connected component has been found. */
1076
1077static t_bool
355fe088 1078follow_ssa_edge_expr (struct loop *loop, gimple *at_stmt, tree expr,
538dd0b7
DM
1079 gphi *halting_phi, tree *evolution_of_loop,
1080 int limit)
726a989a 1081{
5aefc6a0
EB
1082 enum tree_code code = TREE_CODE (expr);
1083 tree type = TREE_TYPE (expr), rhs0, rhs1;
1084 t_bool res;
1085
726a989a 1086 /* The EXPR is one of the following cases:
b8698a0f 1087 - an SSA_NAME,
726a989a 1088 - an INTEGER_CST,
b8698a0f
L
1089 - a PLUS_EXPR,
1090 - a POINTER_PLUS_EXPR,
726a989a
RB
1091 - a MINUS_EXPR,
1092 - an ASSERT_EXPR,
1093 - other cases are not yet handled. */
5aefc6a0 1094
726a989a
RB
1095 switch (code)
1096 {
5aefc6a0 1097 CASE_CONVERT:
726a989a
RB
1098 /* This assignment is under the form "a_1 = (cast) rhs. */
1099 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1100 halting_phi, evolution_of_loop, limit);
1101 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
1102 break;
1103
1104 case INTEGER_CST:
1105 /* This assignment is under the form "a_1 = 7". */
1106 res = t_false;
1107 break;
5aefc6a0 1108
726a989a
RB
1109 case SSA_NAME:
1110 /* This assignment is under the form: "a_1 = b_2". */
b8698a0f 1111 res = follow_ssa_edge
726a989a
RB
1112 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1113 break;
5aefc6a0 1114
726a989a
RB
1115 case POINTER_PLUS_EXPR:
1116 case PLUS_EXPR:
1117 case MINUS_EXPR:
1118 /* This case is under the form "rhs0 +- rhs1". */
1119 rhs0 = TREE_OPERAND (expr, 0);
1120 rhs1 = TREE_OPERAND (expr, 1);
5aefc6a0
EB
1121 type = TREE_TYPE (rhs0);
1122 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1123 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1124 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1125 halting_phi, evolution_of_loop, limit);
1126 break;
726a989a 1127
70f34814
RG
1128 case ADDR_EXPR:
1129 /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
1130 if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
1131 {
1132 expr = TREE_OPERAND (expr, 0);
1133 rhs0 = TREE_OPERAND (expr, 0);
1134 rhs1 = TREE_OPERAND (expr, 1);
1135 type = TREE_TYPE (rhs0);
1136 STRIP_USELESS_TYPE_CONVERSION (rhs0);
1137 STRIP_USELESS_TYPE_CONVERSION (rhs1);
1138 res = follow_ssa_edge_binary (loop, at_stmt, type,
1139 rhs0, POINTER_PLUS_EXPR, rhs1,
1140 halting_phi, evolution_of_loop, limit);
1141 }
1142 else
1143 res = t_false;
1144 break;
1145
0bca51f0 1146 case ASSERT_EXPR:
5aefc6a0
EB
1147 /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1148 It must be handled as a copy assignment of the form a_1 = a_2. */
1149 rhs0 = ASSERT_EXPR_VAR (expr);
1150 if (TREE_CODE (rhs0) == SSA_NAME)
1151 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1152 halting_phi, evolution_of_loop, limit);
1153 else
1154 res = t_false;
1155 break;
0bca51f0 1156
9baba81b 1157 default:
c59dabbe 1158 res = t_false;
9baba81b
SP
1159 break;
1160 }
5aefc6a0 1161
9baba81b
SP
1162 return res;
1163}
1164
726a989a
RB
1165/* Follow the ssa edge into the right hand side of an assignment STMT.
1166 Return true if the strongly connected component has been found. */
1167
1168static t_bool
355fe088 1169follow_ssa_edge_in_rhs (struct loop *loop, gimple *stmt,
538dd0b7
DM
1170 gphi *halting_phi, tree *evolution_of_loop,
1171 int limit)
726a989a 1172{
726a989a 1173 enum tree_code code = gimple_assign_rhs_code (stmt);
5aefc6a0
EB
1174 tree type = gimple_expr_type (stmt), rhs1, rhs2;
1175 t_bool res;
726a989a 1176
5aefc6a0 1177 switch (code)
726a989a 1178 {
5aefc6a0
EB
1179 CASE_CONVERT:
1180 /* This assignment is under the form "a_1 = (cast) rhs. */
1181 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1182 halting_phi, evolution_of_loop, limit);
1183 *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
1184 break;
1185
1186 case POINTER_PLUS_EXPR:
1187 case PLUS_EXPR:
1188 case MINUS_EXPR:
1189 rhs1 = gimple_assign_rhs1 (stmt);
1190 rhs2 = gimple_assign_rhs2 (stmt);
1191 type = TREE_TYPE (rhs1);
1192 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
218d1c24 1193 halting_phi, evolution_of_loop, limit);
5aefc6a0 1194 break;
218d1c24 1195
726a989a 1196 default:
5aefc6a0
EB
1197 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1198 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1199 halting_phi, evolution_of_loop, limit);
1200 else
1201 res = t_false;
1202 break;
726a989a 1203 }
5aefc6a0
EB
1204
1205 return res;
726a989a
RB
1206}
1207
9baba81b
SP
1208/* Checks whether the I-th argument of a PHI comes from a backedge. */
1209
1210static bool
538dd0b7 1211backedge_phi_arg_p (gphi *phi, int i)
9baba81b 1212{
726a989a 1213 const_edge e = gimple_phi_arg_edge (phi, i);
9baba81b
SP
1214
1215 /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1216 about updating it anywhere, and this should work as well most of the
1217 time. */
1218 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1219 return true;
1220
1221 return false;
1222}
1223
1224/* Helper function for one branch of the condition-phi-node. Return
1225 true if the strongly connected component has been found following
1226 this path. */
1227
c59dabbe 1228static inline t_bool
9baba81b 1229follow_ssa_edge_in_condition_phi_branch (int i,
b8698a0f 1230 struct loop *loop,
538dd0b7
DM
1231 gphi *condition_phi,
1232 gphi *halting_phi,
9baba81b 1233 tree *evolution_of_branch,
c59dabbe 1234 tree init_cond, int limit)
9baba81b
SP
1235{
1236 tree branch = PHI_ARG_DEF (condition_phi, i);
1237 *evolution_of_branch = chrec_dont_know;
1238
1239 /* Do not follow back edges (they must belong to an irreducible loop, which
1240 we really do not want to worry about). */
1241 if (backedge_phi_arg_p (condition_phi, i))
c59dabbe 1242 return t_false;
9baba81b
SP
1243
1244 if (TREE_CODE (branch) == SSA_NAME)
1245 {
1246 *evolution_of_branch = init_cond;
b8698a0f 1247 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
c59dabbe 1248 evolution_of_branch, limit);
9baba81b
SP
1249 }
1250
b8698a0f 1251 /* This case occurs when one of the condition branches sets
89dbed81 1252 the variable to a constant: i.e. a phi-node like
b8698a0f
L
1253 "a_2 = PHI <a_7(5), 2(6)>;".
1254
1255 FIXME: This case have to be refined correctly:
9baba81b
SP
1256 in some cases it is possible to say something better than
1257 chrec_dont_know, for example using a wrap-around notation. */
c59dabbe 1258 return t_false;
9baba81b
SP
1259}
1260
1261/* This function merges the branches of a condition-phi-node in a
1262 loop. */
1263
c59dabbe 1264static t_bool
9baba81b 1265follow_ssa_edge_in_condition_phi (struct loop *loop,
538dd0b7
DM
1266 gphi *condition_phi,
1267 gphi *halting_phi,
c59dabbe 1268 tree *evolution_of_loop, int limit)
9baba81b 1269{
726a989a 1270 int i, n;
9baba81b
SP
1271 tree init = *evolution_of_loop;
1272 tree evolution_of_branch;
c59dabbe
SP
1273 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1274 halting_phi,
1275 &evolution_of_branch,
1276 init, limit);
1277 if (res == t_false || res == t_dont_know)
1278 return res;
9baba81b 1279
9baba81b
SP
1280 *evolution_of_loop = evolution_of_branch;
1281
726a989a 1282 n = gimple_phi_num_args (condition_phi);
726a989a 1283 for (i = 1; i < n; i++)
9baba81b 1284 {
e0afb98a
SP
1285 /* Quickly give up when the evolution of one of the branches is
1286 not known. */
1287 if (*evolution_of_loop == chrec_dont_know)
c59dabbe 1288 return t_true;
e0afb98a 1289
788d3075
RG
1290 /* Increase the limit by the PHI argument number to avoid exponential
1291 time and memory complexity. */
c59dabbe
SP
1292 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1293 halting_phi,
1294 &evolution_of_branch,
788d3075 1295 init, limit + i);
c59dabbe
SP
1296 if (res == t_false || res == t_dont_know)
1297 return res;
9baba81b
SP
1298
1299 *evolution_of_loop = chrec_merge (*evolution_of_loop,
1300 evolution_of_branch);
1301 }
b8698a0f 1302
c59dabbe 1303 return t_true;
9baba81b
SP
1304}
1305
1306/* Follow an SSA edge in an inner loop. It computes the overall
1307 effect of the loop, and following the symbolic initial conditions,
1308 it follows the edges in the parent loop. The inner loop is
1309 considered as a single statement. */
1310
c59dabbe 1311static t_bool
9baba81b 1312follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
538dd0b7
DM
1313 gphi *loop_phi_node,
1314 gphi *halting_phi,
c59dabbe 1315 tree *evolution_of_loop, int limit)
9baba81b
SP
1316{
1317 struct loop *loop = loop_containing_stmt (loop_phi_node);
1318 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1319
1320 /* Sometimes, the inner loop is too difficult to analyze, and the
1321 result of the analysis is a symbolic parameter. */
1322 if (ev == PHI_RESULT (loop_phi_node))
1323 {
c59dabbe 1324 t_bool res = t_false;
726a989a 1325 int i, n = gimple_phi_num_args (loop_phi_node);
9baba81b 1326
726a989a 1327 for (i = 0; i < n; i++)
9baba81b
SP
1328 {
1329 tree arg = PHI_ARG_DEF (loop_phi_node, i);
1330 basic_block bb;
1331
1332 /* Follow the edges that exit the inner loop. */
726a989a 1333 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
9baba81b 1334 if (!flow_bb_inside_loop_p (loop, bb))
726a989a
RB
1335 res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1336 arg, halting_phi,
1337 evolution_of_loop, limit);
c59dabbe
SP
1338 if (res == t_true)
1339 break;
9baba81b
SP
1340 }
1341
1342 /* If the path crosses this loop-phi, give up. */
c59dabbe 1343 if (res == t_true)
9baba81b
SP
1344 *evolution_of_loop = chrec_dont_know;
1345
1346 return res;
1347 }
1348
1349 /* Otherwise, compute the overall effect of the inner loop. */
1350 ev = compute_overall_effect_of_inner_loop (loop, ev);
726a989a
RB
1351 return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1352 evolution_of_loop, limit);
9baba81b
SP
1353}
1354
1355/* Follow an SSA edge from a loop-phi-node to itself, constructing a
1356 path that is analyzed on the return walk. */
1357
c59dabbe 1358static t_bool
355fe088 1359follow_ssa_edge (struct loop *loop, gimple *def, gphi *halting_phi,
c59dabbe 1360 tree *evolution_of_loop, int limit)
9baba81b
SP
1361{
1362 struct loop *def_loop;
b8698a0f 1363
726a989a 1364 if (gimple_nop_p (def))
c59dabbe 1365 return t_false;
b8698a0f 1366
c59dabbe 1367 /* Give up if the path is longer than the MAX that we allow. */
14dd9aab 1368 if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
c59dabbe 1369 return t_dont_know;
b8698a0f 1370
9baba81b 1371 def_loop = loop_containing_stmt (def);
b8698a0f 1372
726a989a 1373 switch (gimple_code (def))
9baba81b 1374 {
726a989a 1375 case GIMPLE_PHI:
9baba81b
SP
1376 if (!loop_phi_node_p (def))
1377 /* DEF is a condition-phi-node. Follow the branches, and
1378 record their evolutions. Finally, merge the collected
1379 information and set the approximation to the main
1380 variable. */
b8698a0f 1381 return follow_ssa_edge_in_condition_phi
538dd0b7
DM
1382 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1383 limit);
9baba81b
SP
1384
1385 /* When the analyzed phi is the halting_phi, the
1386 depth-first search is over: we have found a path from
1387 the halting_phi to itself in the loop. */
1388 if (def == halting_phi)
c59dabbe 1389 return t_true;
b8698a0f 1390
9baba81b 1391 /* Otherwise, the evolution of the HALTING_PHI depends
89dbed81 1392 on the evolution of another loop-phi-node, i.e. the
9baba81b
SP
1393 evolution function is a higher degree polynomial. */
1394 if (def_loop == loop)
c59dabbe 1395 return t_false;
b8698a0f 1396
9baba81b
SP
1397 /* Inner loop. */
1398 if (flow_loop_nested_p (loop, def_loop))
b8698a0f 1399 return follow_ssa_edge_inner_loop_phi
538dd0b7
DM
1400 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1401 limit + 1);
9baba81b
SP
1402
1403 /* Outer loop. */
c59dabbe 1404 return t_false;
9baba81b 1405
726a989a 1406 case GIMPLE_ASSIGN:
b8698a0f 1407 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
c59dabbe 1408 evolution_of_loop, limit);
b8698a0f 1409
9baba81b
SP
1410 default:
1411 /* At this level of abstraction, the program is just a set
726a989a 1412 of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
9baba81b 1413 other node to be handled. */
c59dabbe 1414 return t_false;
9baba81b
SP
1415 }
1416}
1417
1418\f
b83b5507
BC
1419/* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
1420 Handle below case and return the corresponding POLYNOMIAL_CHREC:
1421
1422 # i_17 = PHI <i_13(5), 0(3)>
1423 # _20 = PHI <_5(5), start_4(D)(3)>
1424 ...
1425 i_13 = i_17 + 1;
1426 _5 = start_4(D) + i_13;
1427
1428 Though variable _20 appears as a PEELED_CHREC in the form of
1429 (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1430
1431 See PR41488. */
1432
1433static tree
1434simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1435{
1436 aff_tree aff1, aff2;
1437 tree ev, left, right, type, step_val;
39c8aaa4 1438 hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
b83b5507
BC
1439
1440 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1441 if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
1442 return chrec_dont_know;
1443
1444 left = CHREC_LEFT (ev);
1445 right = CHREC_RIGHT (ev);
1446 type = TREE_TYPE (left);
1447 step_val = chrec_fold_plus (type, init_cond, right);
1448
1449 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1450 if "left" equals to "init + right". */
1451 if (operand_equal_p (left, step_val, 0))
1452 {
1453 if (dump_file && (dump_flags & TDF_SCEV))
1454 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1455
1456 return build_polynomial_chrec (loop->num, init_cond, right);
1457 }
1458
cd5091f1
RB
1459 /* The affine code only deals with pointer and integer types. */
1460 if (!POINTER_TYPE_P (type)
1461 && !INTEGRAL_TYPE_P (type))
1462 return chrec_dont_know;
1463
b83b5507
BC
1464 /* Try harder to check if they are equal. */
1465 tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1466 tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1467 free_affine_expand_cache (&peeled_chrec_map);
807e902e 1468 aff_combination_scale (&aff2, -1);
b83b5507
BC
1469 aff_combination_add (&aff1, &aff2);
1470
1471 /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
1472 if "left" equals to "init + right". */
1473 if (aff_combination_zero_p (&aff1))
1474 {
1475 if (dump_file && (dump_flags & TDF_SCEV))
1476 fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1477
1478 return build_polynomial_chrec (loop->num, init_cond, right);
1479 }
1480 return chrec_dont_know;
1481}
9baba81b
SP
1482
1483/* Given a LOOP_PHI_NODE, this function determines the evolution
1484 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1485
1486static tree
538dd0b7 1487analyze_evolution_in_loop (gphi *loop_phi_node,
9baba81b
SP
1488 tree init_cond)
1489{
726a989a 1490 int i, n = gimple_phi_num_args (loop_phi_node);
9baba81b
SP
1491 tree evolution_function = chrec_not_analyzed_yet;
1492 struct loop *loop = loop_containing_stmt (loop_phi_node);
1493 basic_block bb;
b83b5507 1494 static bool simplify_peeled_chrec_p = true;
b8698a0f 1495
dfedbe40 1496 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
1497 {
1498 fprintf (dump_file, "(analyze_evolution_in_loop \n");
1499 fprintf (dump_file, " (loop_phi_node = ");
ef6cb4c7 1500 print_gimple_stmt (dump_file, loop_phi_node, 0);
9baba81b
SP
1501 fprintf (dump_file, ")\n");
1502 }
b8698a0f 1503
726a989a 1504 for (i = 0; i < n; i++)
9baba81b
SP
1505 {
1506 tree arg = PHI_ARG_DEF (loop_phi_node, i);
355fe088 1507 gimple *ssa_chain;
726a989a 1508 tree ev_fn;
874caa00 1509 t_bool res;
9baba81b
SP
1510
1511 /* Select the edges that enter the loop body. */
726a989a 1512 bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
9baba81b
SP
1513 if (!flow_bb_inside_loop_p (loop, bb))
1514 continue;
f29deac9 1515
9baba81b
SP
1516 if (TREE_CODE (arg) == SSA_NAME)
1517 {
f29deac9
SP
1518 bool val = false;
1519
9baba81b
SP
1520 ssa_chain = SSA_NAME_DEF_STMT (arg);
1521
1522 /* Pass in the initial condition to the follow edge function. */
1523 ev_fn = init_cond;
c59dabbe 1524 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
f29deac9
SP
1525
1526 /* If ev_fn has no evolution in the inner loop, and the
1527 init_cond is not equal to ev_fn, then we have an
1528 ambiguity between two possible values, as we cannot know
1529 the number of iterations at this point. */
1530 if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1531 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1532 && !operand_equal_p (init_cond, ev_fn, 0))
1533 ev_fn = chrec_dont_know;
9baba81b
SP
1534 }
1535 else
874caa00 1536 res = t_false;
f29deac9 1537
9baba81b
SP
1538 /* When it is impossible to go back on the same
1539 loop_phi_node by following the ssa edges, the
89dbed81 1540 evolution is represented by a peeled chrec, i.e. the
9baba81b 1541 first iteration, EV_FN has the value INIT_COND, then
b8698a0f 1542 all the other iterations it has the value of ARG.
9baba81b 1543 For the moment, PEELED_CHREC nodes are not built. */
874caa00 1544 if (res != t_true)
b83b5507
BC
1545 {
1546 ev_fn = chrec_dont_know;
1547 /* Try to recognize POLYNOMIAL_CHREC which appears in
1548 the form of PEELED_CHREC, but guard the process with
1549 a bool variable to keep the analyzer from infinite
1550 recurrence for real PEELED_RECs. */
1551 if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1552 {
1553 simplify_peeled_chrec_p = false;
1554 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1555 simplify_peeled_chrec_p = true;
1556 }
1557 }
b8698a0f 1558
9baba81b 1559 /* When there are multiple back edges of the loop (which in fact never
8c27b7d4 1560 happens currently, but nevertheless), merge their evolutions. */
9baba81b 1561 evolution_function = chrec_merge (evolution_function, ev_fn);
e21401b6
RB
1562
1563 if (evolution_function == chrec_dont_know)
1564 break;
9baba81b 1565 }
b8698a0f 1566
dfedbe40 1567 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
1568 {
1569 fprintf (dump_file, " (evolution_function = ");
ef6cb4c7 1570 print_generic_expr (dump_file, evolution_function);
9baba81b
SP
1571 fprintf (dump_file, "))\n");
1572 }
b8698a0f 1573
9baba81b
SP
1574 return evolution_function;
1575}
1576
806f2c1b
AL
1577/* Looks to see if VAR is a copy of a constant (via straightforward assignments
1578 or degenerate phi's). If so, returns the constant; else, returns VAR. */
1579
1580static tree
1581follow_copies_to_constant (tree var)
1582{
1583 tree res = var;
24545562
RB
1584 while (TREE_CODE (res) == SSA_NAME
1585 /* We face not updated SSA form in multiple places and this walk
1586 may end up in sibling loops so we have to guard it. */
1587 && !name_registered_for_update_p (res))
806f2c1b
AL
1588 {
1589 gimple *def = SSA_NAME_DEF_STMT (res);
1590 if (gphi *phi = dyn_cast <gphi *> (def))
1591 {
1592 if (tree rhs = degenerate_phi_result (phi))
1593 res = rhs;
1594 else
1595 break;
1596 }
1597 else if (gimple_assign_single_p (def))
1598 /* Will exit loop if not an SSA_NAME. */
1599 res = gimple_assign_rhs1 (def);
1600 else
1601 break;
1602 }
1603 if (CONSTANT_CLASS_P (res))
1604 return res;
1605 return var;
1606}
1607
9baba81b
SP
1608/* Given a loop-phi-node, return the initial conditions of the
1609 variable on entry of the loop. When the CCP has propagated
1610 constants into the loop-phi-node, the initial condition is
1611 instantiated, otherwise the initial condition is kept symbolic.
1612 This analyzer does not analyze the evolution outside the current
1613 loop, and leaves this task to the on-demand tree reconstructor. */
1614
b8698a0f 1615static tree
538dd0b7 1616analyze_initial_condition (gphi *loop_phi_node)
9baba81b 1617{
726a989a 1618 int i, n;
9baba81b 1619 tree init_cond = chrec_not_analyzed_yet;
726a989a 1620 struct loop *loop = loop_containing_stmt (loop_phi_node);
b8698a0f 1621
dfedbe40 1622 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
1623 {
1624 fprintf (dump_file, "(analyze_initial_condition \n");
1625 fprintf (dump_file, " (loop_phi_node = \n");
ef6cb4c7 1626 print_gimple_stmt (dump_file, loop_phi_node, 0);
9baba81b
SP
1627 fprintf (dump_file, ")\n");
1628 }
b8698a0f 1629
726a989a
RB
1630 n = gimple_phi_num_args (loop_phi_node);
1631 for (i = 0; i < n; i++)
9baba81b
SP
1632 {
1633 tree branch = PHI_ARG_DEF (loop_phi_node, i);
726a989a 1634 basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
b8698a0f 1635
9baba81b
SP
1636 /* When the branch is oriented to the loop's body, it does
1637 not contribute to the initial condition. */
1638 if (flow_bb_inside_loop_p (loop, bb))
1639 continue;
1640
1641 if (init_cond == chrec_not_analyzed_yet)
1642 {
1643 init_cond = branch;
1644 continue;
1645 }
1646
1647 if (TREE_CODE (branch) == SSA_NAME)
1648 {
1649 init_cond = chrec_dont_know;
1650 break;
1651 }
1652
1653 init_cond = chrec_merge (init_cond, branch);
1654 }
1655
1656 /* Ooops -- a loop without an entry??? */
1657 if (init_cond == chrec_not_analyzed_yet)
1658 init_cond = chrec_dont_know;
1659
806f2c1b
AL
1660 /* We may not have fully constant propagated IL. Handle degenerate PHIs here
1661 to not miss important early loop unrollings. */
1662 init_cond = follow_copies_to_constant (init_cond);
bf1cbdc6 1663
dfedbe40 1664 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
1665 {
1666 fprintf (dump_file, " (init_cond = ");
ef6cb4c7 1667 print_generic_expr (dump_file, init_cond);
9baba81b
SP
1668 fprintf (dump_file, "))\n");
1669 }
b8698a0f 1670
9baba81b
SP
1671 return init_cond;
1672}
1673
1674/* Analyze the scalar evolution for LOOP_PHI_NODE. */
1675
b8698a0f 1676static tree
538dd0b7 1677interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
9baba81b
SP
1678{
1679 tree res;
1680 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1681 tree init_cond;
b8698a0f 1682
5355943c 1683 gcc_assert (phi_loop == loop);
9baba81b
SP
1684
1685 /* Otherwise really interpret the loop phi. */
1686 init_cond = analyze_initial_condition (loop_phi_node);
1687 res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1688
73c865fa
RG
1689 /* Verify we maintained the correct initial condition throughout
1690 possible conversions in the SSA chain. */
1691 if (res != chrec_dont_know)
1692 {
1693 tree new_init = res;
1694 if (CONVERT_EXPR_P (res)
1695 && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
1696 new_init = fold_convert (TREE_TYPE (res),
1697 CHREC_LEFT (TREE_OPERAND (res, 0)));
1698 else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1699 new_init = CHREC_LEFT (res);
1700 STRIP_USELESS_TYPE_CONVERSION (new_init);
eb723fa3
RG
1701 if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1702 || !operand_equal_p (init_cond, new_init, 0))
73c865fa
RG
1703 return chrec_dont_know;
1704 }
1705
9baba81b
SP
1706 return res;
1707}
1708
1709/* This function merges the branches of a condition-phi-node,
1710 contained in the outermost loop, and whose arguments are already
1711 analyzed. */
1712
1713static tree
538dd0b7 1714interpret_condition_phi (struct loop *loop, gphi *condition_phi)
9baba81b 1715{
726a989a 1716 int i, n = gimple_phi_num_args (condition_phi);
9baba81b 1717 tree res = chrec_not_analyzed_yet;
b8698a0f 1718
726a989a 1719 for (i = 0; i < n; i++)
9baba81b
SP
1720 {
1721 tree branch_chrec;
b8698a0f 1722
9baba81b
SP
1723 if (backedge_phi_arg_p (condition_phi, i))
1724 {
1725 res = chrec_dont_know;
1726 break;
1727 }
1728
1729 branch_chrec = analyze_scalar_evolution
1730 (loop, PHI_ARG_DEF (condition_phi, i));
b8698a0f 1731
9baba81b 1732 res = chrec_merge (res, branch_chrec);
e21401b6
RB
1733 if (res == chrec_dont_know)
1734 break;
9baba81b
SP
1735 }
1736
1737 return res;
1738}
1739
726a989a 1740/* Interpret the operation RHS1 OP RHS2. If we didn't
29836d07 1741 analyze this node before, follow the definitions until ending
726a989a 1742 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
9baba81b
SP
1743 return path, this function propagates evolutions (ala constant copy
1744 propagation). OPND1 is not a GIMPLE expression because we could
1745 analyze the effect of an inner loop: see interpret_loop_phi. */
1746
1747static tree
355fe088 1748interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
726a989a 1749 tree type, tree rhs1, enum tree_code code, tree rhs2)
9baba81b 1750{
f802a424 1751 tree res, chrec1, chrec2, ctype;
355fe088 1752 gimple *def;
726a989a
RB
1753
1754 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1755 {
1756 if (is_gimple_min_invariant (rhs1))
1757 return chrec_convert (type, rhs1, at_stmt);
1758
1759 if (code == SSA_NAME)
1760 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1761 at_stmt);
1e8552eb 1762
726a989a
RB
1763 if (code == ASSERT_EXPR)
1764 {
1765 rhs1 = ASSERT_EXPR_VAR (rhs1);
1766 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1767 at_stmt);
1768 }
726a989a 1769 }
1e8552eb 1770
726a989a 1771 switch (code)
9baba81b 1772 {
6a02a719 1773 case ADDR_EXPR:
bef28ced
JL
1774 if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF
1775 || handled_component_p (TREE_OPERAND (rhs1, 0)))
1776 {
ef4bddc2 1777 machine_mode mode;
f37fac2b 1778 poly_int64 bitsize, bitpos;
ee45a32d 1779 int unsignedp, reversep;
bef28ced
JL
1780 int volatilep = 0;
1781 tree base, offset;
1782 tree chrec3;
1783 tree unitpos;
1784
1785 base = get_inner_reference (TREE_OPERAND (rhs1, 0),
ee45a32d 1786 &bitsize, &bitpos, &offset, &mode,
25b75a48 1787 &unsignedp, &reversep, &volatilep);
bef28ced
JL
1788
1789 if (TREE_CODE (base) == MEM_REF)
1790 {
1791 rhs2 = TREE_OPERAND (base, 1);
1792 rhs1 = TREE_OPERAND (base, 0);
1793
1794 chrec1 = analyze_scalar_evolution (loop, rhs1);
1795 chrec2 = analyze_scalar_evolution (loop, rhs2);
1796 chrec1 = chrec_convert (type, chrec1, at_stmt);
1797 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
0547c9b6
RB
1798 chrec1 = instantiate_parameters (loop, chrec1);
1799 chrec2 = instantiate_parameters (loop, chrec2);
bef28ced
JL
1800 res = chrec_fold_plus (type, chrec1, chrec2);
1801 }
1802 else
1803 {
1804 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1805 chrec1 = chrec_convert (type, chrec1, at_stmt);
1806 res = chrec1;
1807 }
6a02a719 1808
bef28ced
JL
1809 if (offset != NULL_TREE)
1810 {
1811 chrec2 = analyze_scalar_evolution (loop, offset);
1812 chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
0547c9b6 1813 chrec2 = instantiate_parameters (loop, chrec2);
bef28ced
JL
1814 res = chrec_fold_plus (type, res, chrec2);
1815 }
1816
f37fac2b 1817 if (maybe_ne (bitpos, 0))
bef28ced 1818 {
f37fac2b 1819 unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
bef28ced
JL
1820 chrec3 = analyze_scalar_evolution (loop, unitpos);
1821 chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
0547c9b6 1822 chrec3 = instantiate_parameters (loop, chrec3);
bef28ced
JL
1823 res = chrec_fold_plus (type, res, chrec3);
1824 }
1825 }
1826 else
1827 res = chrec_dont_know;
1828 break;
6a02a719 1829
5be014d5 1830 case POINTER_PLUS_EXPR:
726a989a
RB
1831 chrec1 = analyze_scalar_evolution (loop, rhs1);
1832 chrec2 = analyze_scalar_evolution (loop, rhs2);
1833 chrec1 = chrec_convert (type, chrec1, at_stmt);
0d82a1c8 1834 chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
0547c9b6
RB
1835 chrec1 = instantiate_parameters (loop, chrec1);
1836 chrec2 = instantiate_parameters (loop, chrec2);
726a989a 1837 res = chrec_fold_plus (type, chrec1, chrec2);
5be014d5
AP
1838 break;
1839
9baba81b 1840 case PLUS_EXPR:
726a989a
RB
1841 chrec1 = analyze_scalar_evolution (loop, rhs1);
1842 chrec2 = analyze_scalar_evolution (loop, rhs2);
f802a424
RB
1843 ctype = type;
1844 /* When the stmt is conditionally executed re-write the CHREC
1845 into a form that has well-defined behavior on overflow. */
1846 if (at_stmt
1847 && INTEGRAL_TYPE_P (type)
1848 && ! TYPE_OVERFLOW_WRAPS (type)
1849 && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1850 gimple_bb (at_stmt)))
1851 ctype = unsigned_type_for (type);
1852 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1853 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
0547c9b6
RB
1854 chrec1 = instantiate_parameters (loop, chrec1);
1855 chrec2 = instantiate_parameters (loop, chrec2);
f802a424
RB
1856 res = chrec_fold_plus (ctype, chrec1, chrec2);
1857 if (type != ctype)
1858 res = chrec_convert (type, res, at_stmt);
9baba81b 1859 break;
b8698a0f 1860
9baba81b 1861 case MINUS_EXPR:
726a989a
RB
1862 chrec1 = analyze_scalar_evolution (loop, rhs1);
1863 chrec2 = analyze_scalar_evolution (loop, rhs2);
f802a424
RB
1864 ctype = type;
1865 /* When the stmt is conditionally executed re-write the CHREC
1866 into a form that has well-defined behavior on overflow. */
1867 if (at_stmt
1868 && INTEGRAL_TYPE_P (type)
1869 && ! TYPE_OVERFLOW_WRAPS (type)
1870 && ! dominated_by_p (CDI_DOMINATORS,
1871 loop->latch, gimple_bb (at_stmt)))
1872 ctype = unsigned_type_for (type);
1873 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1874 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
0547c9b6
RB
1875 chrec1 = instantiate_parameters (loop, chrec1);
1876 chrec2 = instantiate_parameters (loop, chrec2);
f802a424
RB
1877 res = chrec_fold_minus (ctype, chrec1, chrec2);
1878 if (type != ctype)
1879 res = chrec_convert (type, res, at_stmt);
9baba81b
SP
1880 break;
1881
1882 case NEGATE_EXPR:
726a989a 1883 chrec1 = analyze_scalar_evolution (loop, rhs1);
f802a424
RB
1884 ctype = type;
1885 /* When the stmt is conditionally executed re-write the CHREC
1886 into a form that has well-defined behavior on overflow. */
1887 if (at_stmt
1888 && INTEGRAL_TYPE_P (type)
1889 && ! TYPE_OVERFLOW_WRAPS (type)
1890 && ! dominated_by_p (CDI_DOMINATORS,
1891 loop->latch, gimple_bb (at_stmt)))
1892 ctype = unsigned_type_for (type);
1893 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
9a75ede0 1894 /* TYPE may be integer, real or complex, so use fold_convert. */
0547c9b6 1895 chrec1 = instantiate_parameters (loop, chrec1);
f802a424
RB
1896 res = chrec_fold_multiply (ctype, chrec1,
1897 fold_convert (ctype, integer_minus_one_node));
1898 if (type != ctype)
1899 res = chrec_convert (type, res, at_stmt);
9baba81b
SP
1900 break;
1901
418df9d7
JJ
1902 case BIT_NOT_EXPR:
1903 /* Handle ~X as -1 - X. */
1904 chrec1 = analyze_scalar_evolution (loop, rhs1);
1905 chrec1 = chrec_convert (type, chrec1, at_stmt);
0547c9b6 1906 chrec1 = instantiate_parameters (loop, chrec1);
418df9d7
JJ
1907 res = chrec_fold_minus (type,
1908 fold_convert (type, integer_minus_one_node),
1909 chrec1);
1910 break;
1911
9baba81b 1912 case MULT_EXPR:
726a989a
RB
1913 chrec1 = analyze_scalar_evolution (loop, rhs1);
1914 chrec2 = analyze_scalar_evolution (loop, rhs2);
f802a424
RB
1915 ctype = type;
1916 /* When the stmt is conditionally executed re-write the CHREC
1917 into a form that has well-defined behavior on overflow. */
1918 if (at_stmt
1919 && INTEGRAL_TYPE_P (type)
1920 && ! TYPE_OVERFLOW_WRAPS (type)
1921 && ! dominated_by_p (CDI_DOMINATORS,
1922 loop->latch, gimple_bb (at_stmt)))
1923 ctype = unsigned_type_for (type);
1924 chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1925 chrec2 = chrec_convert (ctype, chrec2, at_stmt);
0547c9b6
RB
1926 chrec1 = instantiate_parameters (loop, chrec1);
1927 chrec2 = instantiate_parameters (loop, chrec2);
f802a424
RB
1928 res = chrec_fold_multiply (ctype, chrec1, chrec2);
1929 if (type != ctype)
1930 res = chrec_convert (type, res, at_stmt);
0bca51f0 1931 break;
b8698a0f 1932
60f2d2f3
AL
1933 case LSHIFT_EXPR:
1934 {
1935 /* Handle A<<B as A * (1<<B). */
1936 tree uns = unsigned_type_for (type);
1937 chrec1 = analyze_scalar_evolution (loop, rhs1);
1938 chrec2 = analyze_scalar_evolution (loop, rhs2);
1939 chrec1 = chrec_convert (uns, chrec1, at_stmt);
1940 chrec1 = instantiate_parameters (loop, chrec1);
1941 chrec2 = instantiate_parameters (loop, chrec2);
1942
1943 tree one = build_int_cst (uns, 1);
1944 chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1945 res = chrec_fold_multiply (uns, chrec1, chrec2);
1946 res = chrec_convert (type, res, at_stmt);
1947 }
1948 break;
1949
1043771b 1950 CASE_CONVERT:
195b4c50
RG
1951 /* In case we have a truncation of a widened operation that in
1952 the truncated type has undefined overflow behavior analyze
1953 the operation done in an unsigned type of the same precision
1954 as the final truncation. We cannot derive a scalar evolution
1955 for the widened operation but for the truncated result. */
1956 if (TREE_CODE (type) == INTEGER_TYPE
1957 && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1958 && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1959 && TYPE_OVERFLOW_UNDEFINED (type)
1960 && TREE_CODE (rhs1) == SSA_NAME
1961 && (def = SSA_NAME_DEF_STMT (rhs1))
1962 && is_gimple_assign (def)
1963 && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1964 && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1965 {
1966 tree utype = unsigned_type_for (type);
1967 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1968 gimple_assign_rhs1 (def),
1969 gimple_assign_rhs_code (def),
1970 gimple_assign_rhs2 (def));
1971 }
1972 else
1973 chrec1 = analyze_scalar_evolution (loop, rhs1);
b24d9420 1974 res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
9baba81b 1975 break;
e6d62b46
BC
1976
1977 case BIT_AND_EXPR:
1978 /* Given int variable A, handle A&0xffff as (int)(unsigned short)A.
1979 If A is SCEV and its value is in the range of representable set
1980 of type unsigned short, the result expression is a (no-overflow)
1981 SCEV. */
1982 res = chrec_dont_know;
1983 if (tree_fits_uhwi_p (rhs2))
1984 {
1985 int precision;
1986 unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
1987
1988 val ++;
1989 /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or
1990 it's not the maximum value of a smaller type than rhs1. */
1991 if (val != 0
1992 && (precision = exact_log2 (val)) > 0
1993 && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
1994 {
1995 tree utype = build_nonstandard_integer_type (precision, 1);
1996
1997 if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
1998 {
1999 chrec1 = analyze_scalar_evolution (loop, rhs1);
2000 chrec1 = chrec_convert (utype, chrec1, at_stmt);
2001 res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
2002 }
2003 }
2004 }
2005 break;
b8698a0f 2006
9baba81b
SP
2007 default:
2008 res = chrec_dont_know;
2009 break;
2010 }
b8698a0f 2011
9baba81b
SP
2012 return res;
2013}
2014
726a989a
RB
2015/* Interpret the expression EXPR. */
2016
2017static tree
355fe088 2018interpret_expr (struct loop *loop, gimple *at_stmt, tree expr)
726a989a
RB
2019{
2020 enum tree_code code;
2021 tree type = TREE_TYPE (expr), op0, op1;
2022
2023 if (automatically_generated_chrec_p (expr))
2024 return expr;
2025
4e71066d 2026 if (TREE_CODE (expr) == POLYNOMIAL_CHREC
5126ae0c 2027 || TREE_CODE (expr) == CALL_EXPR
4e71066d 2028 || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
726a989a
RB
2029 return chrec_dont_know;
2030
2031 extract_ops_from_tree (expr, &code, &op0, &op1);
2032
2033 return interpret_rhs_expr (loop, at_stmt, type,
2034 op0, code, op1);
2035}
2036
2037/* Interpret the rhs of the assignment STMT. */
2038
2039static tree
355fe088 2040interpret_gimple_assign (struct loop *loop, gimple *stmt)
726a989a
RB
2041{
2042 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2043 enum tree_code code = gimple_assign_rhs_code (stmt);
2044
2045 return interpret_rhs_expr (loop, stmt, type,
2046 gimple_assign_rhs1 (stmt), code,
2047 gimple_assign_rhs2 (stmt));
2048}
2049
9baba81b
SP
2050\f
2051
b8698a0f 2052/* This section contains all the entry points:
9baba81b
SP
2053 - number_of_iterations_in_loop,
2054 - analyze_scalar_evolution,
2055 - instantiate_parameters.
2056*/
2057
9baba81b
SP
2058/* Helper recursive function. */
2059
2060static tree
fb1fe1f3 2061analyze_scalar_evolution_1 (struct loop *loop, tree var)
9baba81b 2062{
355fe088 2063 gimple *def;
9baba81b
SP
2064 basic_block bb;
2065 struct loop *def_loop;
fb1fe1f3 2066 tree res;
9baba81b 2067
9baba81b 2068 if (TREE_CODE (var) != SSA_NAME)
726a989a 2069 return interpret_expr (loop, NULL, var);
9baba81b
SP
2070
2071 def = SSA_NAME_DEF_STMT (var);
726a989a 2072 bb = gimple_bb (def);
5355943c 2073 def_loop = bb->loop_father;
9baba81b 2074
5355943c 2075 if (!flow_bb_inside_loop_p (loop, bb))
9baba81b 2076 {
806f2c1b
AL
2077 /* Keep symbolic form, but look through obvious copies for constants. */
2078 res = follow_copies_to_constant (var);
9baba81b
SP
2079 goto set_and_end;
2080 }
2081
9baba81b
SP
2082 if (loop != def_loop)
2083 {
fb1fe1f3 2084 res = analyze_scalar_evolution_1 (def_loop, var);
5355943c
RB
2085 struct loop *loop_to_skip = superloop_at_depth (def_loop,
2086 loop_depth (loop) + 1);
2087 res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
2088 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
2089 res = analyze_scalar_evolution_1 (loop, res);
9baba81b
SP
2090 goto set_and_end;
2091 }
2092
726a989a 2093 switch (gimple_code (def))
9baba81b 2094 {
726a989a
RB
2095 case GIMPLE_ASSIGN:
2096 res = interpret_gimple_assign (loop, def);
9baba81b
SP
2097 break;
2098
726a989a 2099 case GIMPLE_PHI:
9baba81b 2100 if (loop_phi_node_p (def))
538dd0b7 2101 res = interpret_loop_phi (loop, as_a <gphi *> (def));
9baba81b 2102 else
538dd0b7 2103 res = interpret_condition_phi (loop, as_a <gphi *> (def));
9baba81b
SP
2104 break;
2105
2106 default:
2107 res = chrec_dont_know;
2108 break;
2109 }
2110
2111 set_and_end:
2112
2113 /* Keep the symbolic form. */
2114 if (res == chrec_dont_know)
2115 res = var;
2116
2117 if (loop == def_loop)
a213b219 2118 set_scalar_evolution (block_before_loop (loop), var, res);
9baba81b
SP
2119
2120 return res;
2121}
2122
52bdd655
SP
2123/* Analyzes and returns the scalar evolution of the ssa_name VAR in
2124 LOOP. LOOP is the loop in which the variable is used.
b8698a0f 2125
9baba81b
SP
2126 Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2127 pointer to the statement that uses this variable, in order to
2128 determine the evolution function of the variable, use the following
2129 calls:
b8698a0f 2130
52bdd655
SP
2131 loop_p loop = loop_containing_stmt (stmt);
2132 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
3f227a8c 2133 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
9baba81b
SP
2134*/
2135
b8698a0f 2136tree
9baba81b
SP
2137analyze_scalar_evolution (struct loop *loop, tree var)
2138{
2139 tree res;
2140
a68f286c
RB
2141 /* ??? Fix callers. */
2142 if (! loop)
2143 return var;
2144
dfedbe40 2145 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
2146 {
2147 fprintf (dump_file, "(analyze_scalar_evolution \n");
2148 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2149 fprintf (dump_file, " (scalar = ");
ef6cb4c7 2150 print_generic_expr (dump_file, var);
9baba81b
SP
2151 fprintf (dump_file, ")\n");
2152 }
2153
a213b219 2154 res = get_scalar_evolution (block_before_loop (loop), var);
fb1fe1f3 2155 if (res == chrec_not_analyzed_yet)
577d6588
RB
2156 {
2157 /* We'll recurse into instantiate_scev, avoid tearing down the
2158 instantiate cache repeatedly and keep it live from here. */
2159 bool destr = false;
2160 if (!global_cache)
2161 {
2162 global_cache = new instantiate_cache_type;
2163 destr = true;
2164 }
2165 res = analyze_scalar_evolution_1 (loop, var);
2166 if (destr)
2167 {
2168 delete global_cache;
2169 global_cache = NULL;
2170 }
2171 }
9baba81b 2172
dfedbe40 2173 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
2174 fprintf (dump_file, ")\n");
2175
2176 return res;
2177}
2178
bef28ced
JL
2179/* Analyzes and returns the scalar evolution of VAR address in LOOP. */
2180
2181static tree
2182analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2183{
2184 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2185}
2186
9baba81b 2187/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
f017bf5e 2188 WRTO_LOOP (which should be a superloop of USE_LOOP)
a6f778b2
ZD
2189
2190 FOLDED_CASTS is set to true if resolve_mixers used
2191 chrec_convert_aggressive (TODO -- not really, we are way too conservative
b8698a0f
L
2192 at the moment in order to keep things simple).
2193
f017bf5e
ZD
2194 To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2195 example:
2196
2197 for (i = 0; i < 100; i++) -- loop 1
2198 {
2199 for (j = 0; j < 100; j++) -- loop 2
2200 {
2201 k1 = i;
2202 k2 = j;
2203
2204 use2 (k1, k2);
2205
2206 for (t = 0; t < 100; t++) -- loop 3
2207 use3 (k1, k2);
2208
2209 }
2210 use1 (k1, k2);
2211 }
2212
2213 Both k1 and k2 are invariants in loop3, thus
2214 analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2215 analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2216
2217 As they are invariant, it does not matter whether we consider their
2218 usage in loop 3 or loop 2, hence
2219 analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2220 analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2221 analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2222 analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2223
2224 Similarly for their evolutions with respect to loop 1. The values of K2
2225 in the use in loop 2 vary independently on loop 1, thus we cannot express
2226 the evolution with respect to loop 1:
2227 analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2228 analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2229 analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2230 analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2231
2232 The value of k2 in the use in loop 1 is known, though:
2233 analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2234 analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2235 */
9baba81b
SP
2236
2237static tree
2238analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
a6f778b2 2239 tree version, bool *folded_casts)
9baba81b
SP
2240{
2241 bool val = false;
a6f778b2 2242 tree ev = version, tmp;
9baba81b 2243
b8698a0f 2244 /* We cannot just do
f017bf5e
ZD
2245
2246 tmp = analyze_scalar_evolution (use_loop, version);
c70ed622 2247 ev = resolve_mixers (wrto_loop, tmp, folded_casts);
f017bf5e
ZD
2248
2249 as resolve_mixers would query the scalar evolution with respect to
2250 wrto_loop. For example, in the situation described in the function
2251 comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2252 version = k2. Then
2253
2254 analyze_scalar_evolution (use_loop, version) = k2
2255
c70ed622
BC
2256 and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2257 k2 in loop 1 is 100, which is a wrong result, since we are interested
2258 in the value in loop 3.
f017bf5e
ZD
2259
2260 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2261 each time checking that there is no evolution in the inner loop. */
2262
a6f778b2
ZD
2263 if (folded_casts)
2264 *folded_casts = false;
9baba81b
SP
2265 while (1)
2266 {
a6f778b2 2267 tmp = analyze_scalar_evolution (use_loop, ev);
c70ed622 2268 ev = resolve_mixers (use_loop, tmp, folded_casts);
9baba81b
SP
2269
2270 if (use_loop == wrto_loop)
2271 return ev;
2272
2273 /* If the value of the use changes in the inner loop, we cannot express
2274 its value in the outer loop (we might try to return interval chrec,
2275 but we do not have a user for it anyway) */
2276 if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2277 || !val)
2278 return chrec_dont_know;
2279
9ba025a2 2280 use_loop = loop_outer (use_loop);
9baba81b
SP
2281 }
2282}
2283
eb0bc7af 2284
a3cc13cc
RB
2285/* Computes a hash function for database element ELT. */
2286
2287static inline hashval_t
2288hash_idx_scev_info (const void *elt_)
2289{
2290 unsigned idx = ((size_t) elt_) - 2;
907dadbd 2291 return scev_info_hasher::hash (&global_cache->entries[idx]);
a3cc13cc
RB
2292}
2293
2294/* Compares database elements E1 and E2. */
2295
2296static inline int
2297eq_idx_scev_info (const void *e1, const void *e2)
2298{
2299 unsigned idx1 = ((size_t) e1) - 2;
907dadbd
TS
2300 return scev_info_hasher::equal (&global_cache->entries[idx1],
2301 (const scev_info_str *) e2);
a3cc13cc
RB
2302}
2303
0547c9b6 2304/* Returns from CACHE the slot number of the cached chrec for NAME. */
fdd43ac4 2305
0547c9b6 2306static unsigned
a3cc13cc 2307get_instantiated_value_entry (instantiate_cache_type &cache,
a68f286c 2308 tree name, edge instantiate_below)
fdd43ac4 2309{
0547c9b6 2310 if (!cache.map)
fdd43ac4 2311 {
a3cc13cc 2312 cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL);
fdd43ac4
RB
2313 cache.entries.create (10);
2314 }
b8698a0f 2315
a3cc13cc
RB
2316 scev_info_str e;
2317 e.name_version = SSA_NAME_VERSION (name);
a68f286c 2318 e.instantiated_below = instantiate_below->dest->index;
a3cc13cc 2319 void **slot = htab_find_slot_with_hash (cache.map, &e,
907dadbd 2320 scev_info_hasher::hash (&e), INSERT);
a3cc13cc 2321 if (!*slot)
fdd43ac4
RB
2322 {
2323 e.chrec = chrec_not_analyzed_yet;
a3cc13cc 2324 *slot = (void *)(size_t)(cache.entries.length () + 2);
fdd43ac4 2325 cache.entries.safe_push (e);
fdd43ac4
RB
2326 }
2327
a3cc13cc 2328 return ((size_t)*slot) - 2;
eb0bc7af
ZD
2329}
2330
0547c9b6 2331
18aed06a
SP
2332/* Return the closed_loop_phi node for VAR. If there is none, return
2333 NULL_TREE. */
2334
2335static tree
2336loop_closed_phi_def (tree var)
2337{
2338 struct loop *loop;
2339 edge exit;
538dd0b7
DM
2340 gphi *phi;
2341 gphi_iterator psi;
18aed06a
SP
2342
2343 if (var == NULL_TREE
2344 || TREE_CODE (var) != SSA_NAME)
2345 return NULL_TREE;
2346
2347 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
ac8f6c69 2348 exit = single_exit (loop);
18aed06a
SP
2349 if (!exit)
2350 return NULL_TREE;
2351
726a989a
RB
2352 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2353 {
538dd0b7 2354 phi = psi.phi ();
726a989a
RB
2355 if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2356 return PHI_RESULT (phi);
2357 }
18aed06a
SP
2358
2359 return NULL_TREE;
2360}
2361
a68f286c 2362static tree instantiate_scev_r (edge, struct loop *, struct loop *,
c70ed622 2363 tree, bool *, int);
320f5a78
SP
2364
2365/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2366 and EVOLUTION_LOOP, that were left under a symbolic form.
2367
2495a183 2368 CHREC is an SSA_NAME to be instantiated.
320f5a78
SP
2369
2370 CACHE is the cache of already instantiated values.
2371
c70ed622
BC
2372 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2373 conversions that may wrap in signed/pointer type are folded, as long
2374 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2375 then we don't do such fold.
320f5a78
SP
2376
2377 SIZE_EXPR is used for computing the size of the expression to be
2378 instantiated, and to stop if it exceeds some limit. */
2379
2380static tree
a68f286c 2381instantiate_scev_name (edge instantiate_below,
8b679c9b
RB
2382 struct loop *evolution_loop, struct loop *inner_loop,
2383 tree chrec,
c70ed622 2384 bool *fold_conversions,
4a8fb1a1 2385 int size_expr)
320f5a78 2386{
2495a183
SP
2387 tree res;
2388 struct loop *def_loop;
2389 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
20179b0d 2390
92900aec 2391 /* A parameter, nothing to do. */
2495a183 2392 if (!def_bb
92900aec 2393 || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
2495a183 2394 return chrec;
20179b0d 2395
2495a183
SP
2396 /* We cache the value of instantiated variable to avoid exponential
2397 time complexity due to reevaluations. We also store the convenient
2398 value in the cache in order to prevent infinite recursion -- we do
2399 not want to instantiate the SSA_NAME if it is in a mixer
2400 structure. This is used for avoiding the instantiation of
2401 recursively defined functions, such as:
320f5a78 2402
2495a183 2403 | a_2 -> {0, +, 1, +, a_2}_1 */
20179b0d 2404
a3cc13cc
RB
2405 unsigned si = get_instantiated_value_entry (*global_cache,
2406 chrec, instantiate_below);
0547c9b6
RB
2407 if (global_cache->get (si) != chrec_not_analyzed_yet)
2408 return global_cache->get (si);
20179b0d 2409
fdd43ac4 2410 /* On recursion return chrec_dont_know. */
0547c9b6 2411 global_cache->set (si, chrec_dont_know);
320f5a78 2412
2495a183
SP
2413 def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2414
a68f286c
RB
2415 if (! dominated_by_p (CDI_DOMINATORS,
2416 def_loop->header, instantiate_below->dest))
2417 {
2418 gimple *def = SSA_NAME_DEF_STMT (chrec);
2419 if (gassign *ass = dyn_cast <gassign *> (def))
2420 {
2421 switch (gimple_assign_rhs_class (ass))
2422 {
2423 case GIMPLE_UNARY_RHS:
2424 {
2425 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2426 inner_loop, gimple_assign_rhs1 (ass),
2427 fold_conversions, size_expr);
2428 if (op0 == chrec_dont_know)
2429 return chrec_dont_know;
2430 res = fold_build1 (gimple_assign_rhs_code (ass),
2431 TREE_TYPE (chrec), op0);
2432 break;
2433 }
2434 case GIMPLE_BINARY_RHS:
2435 {
2436 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2437 inner_loop, gimple_assign_rhs1 (ass),
2438 fold_conversions, size_expr);
2439 if (op0 == chrec_dont_know)
2440 return chrec_dont_know;
2441 tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2442 inner_loop, gimple_assign_rhs2 (ass),
2443 fold_conversions, size_expr);
2444 if (op1 == chrec_dont_know)
2445 return chrec_dont_know;
2446 res = fold_build2 (gimple_assign_rhs_code (ass),
2447 TREE_TYPE (chrec), op0, op1);
2448 break;
2449 }
2450 default:
2451 res = chrec_dont_know;
2452 }
2453 }
2454 else
2455 res = chrec_dont_know;
2456 global_cache->set (si, res);
2457 return res;
2458 }
2459
320f5a78
SP
2460 /* If the analysis yields a parametric chrec, instantiate the
2461 result again. */
2462 res = analyze_scalar_evolution (def_loop, chrec);
2463
2847388e 2464 /* Don't instantiate default definitions. */
320f5a78 2465 if (TREE_CODE (res) == SSA_NAME
2847388e
SP
2466 && SSA_NAME_IS_DEFAULT_DEF (res))
2467 ;
2468
2469 /* Don't instantiate loop-closed-ssa phi nodes. */
2470 else if (TREE_CODE (res) == SSA_NAME
2471 && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2472 > loop_depth (def_loop))
320f5a78
SP
2473 {
2474 if (res == chrec)
2475 res = loop_closed_phi_def (chrec);
2476 else
2477 res = chrec;
2478
7472eb13
SP
2479 /* When there is no loop_closed_phi_def, it means that the
2480 variable is not used after the loop: try to still compute the
2481 value of the variable when exiting the loop. */
2482 if (res == NULL_TREE)
2483 {
2484 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2485 res = analyze_scalar_evolution (loop, chrec);
2486 res = compute_overall_effect_of_inner_loop (loop, res);
8b679c9b
RB
2487 res = instantiate_scev_r (instantiate_below, evolution_loop,
2488 inner_loop, res,
0547c9b6 2489 fold_conversions, size_expr);
7472eb13 2490 }
a68f286c
RB
2491 else if (dominated_by_p (CDI_DOMINATORS,
2492 gimple_bb (SSA_NAME_DEF_STMT (res)),
2493 instantiate_below->dest))
320f5a78
SP
2494 res = chrec_dont_know;
2495 }
2496
2497 else if (res != chrec_dont_know)
8b679c9b
RB
2498 {
2499 if (inner_loop
63fdb7be 2500 && def_bb->loop_father != inner_loop
8b679c9b
RB
2501 && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2502 /* ??? We could try to compute the overall effect of the loop here. */
2503 res = chrec_dont_know;
2504 else
2505 res = instantiate_scev_r (instantiate_below, evolution_loop,
2506 inner_loop, res,
0547c9b6 2507 fold_conversions, size_expr);
8b679c9b 2508 }
320f5a78
SP
2509
2510 /* Store the correct value to the cache. */
0547c9b6 2511 global_cache->set (si, res);
320f5a78 2512 return res;
320f5a78
SP
2513}
2514
ec6636eb
SP
2515/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2516 and EVOLUTION_LOOP, that were left under a symbolic form.
2517
2518 CHREC is a polynomial chain of recurrence to be instantiated.
2519
2520 CACHE is the cache of already instantiated values.
2521
c70ed622
BC
2522 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2523 conversions that may wrap in signed/pointer type are folded, as long
2524 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2525 then we don't do such fold.
ec6636eb
SP
2526
2527 SIZE_EXPR is used for computing the size of the expression to be
2528 instantiated, and to stop if it exceeds some limit. */
2529
2530static tree
a68f286c 2531instantiate_scev_poly (edge instantiate_below,
8b679c9b 2532 struct loop *evolution_loop, struct loop *,
c70ed622 2533 tree chrec, bool *fold_conversions, int size_expr)
ec6636eb
SP
2534{
2535 tree op1;
9e5dc77f 2536 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
8b679c9b 2537 get_chrec_loop (chrec),
0547c9b6 2538 CHREC_LEFT (chrec), fold_conversions,
ec6636eb
SP
2539 size_expr);
2540 if (op0 == chrec_dont_know)
2541 return chrec_dont_know;
2542
9e5dc77f 2543 op1 = instantiate_scev_r (instantiate_below, evolution_loop,
8b679c9b 2544 get_chrec_loop (chrec),
0547c9b6 2545 CHREC_RIGHT (chrec), fold_conversions,
ec6636eb
SP
2546 size_expr);
2547 if (op1 == chrec_dont_know)
2548 return chrec_dont_know;
2549
2550 if (CHREC_LEFT (chrec) != op0
2551 || CHREC_RIGHT (chrec) != op1)
2552 {
2553 op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
8b679c9b 2554 chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
ec6636eb 2555 }
4bf4e169 2556
ec6636eb
SP
2557 return chrec;
2558}
2559
15fda317
SP
2560/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2561 and EVOLUTION_LOOP, that were left under a symbolic form.
2562
ffa34f4b 2563 "C0 CODE C1" is a binary expression of type TYPE to be instantiated.
15fda317
SP
2564
2565 CACHE is the cache of already instantiated values.
2566
c70ed622
BC
2567 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2568 conversions that may wrap in signed/pointer type are folded, as long
2569 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2570 then we don't do such fold.
15fda317
SP
2571
2572 SIZE_EXPR is used for computing the size of the expression to be
2573 instantiated, and to stop if it exceeds some limit. */
2574
2575static tree
a68f286c 2576instantiate_scev_binary (edge instantiate_below,
8b679c9b
RB
2577 struct loop *evolution_loop, struct loop *inner_loop,
2578 tree chrec, enum tree_code code,
ffa34f4b 2579 tree type, tree c0, tree c1,
c70ed622 2580 bool *fold_conversions, int size_expr)
15fda317
SP
2581{
2582 tree op1;
8b679c9b 2583 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
0547c9b6 2584 c0, fold_conversions, size_expr);
15fda317
SP
2585 if (op0 == chrec_dont_know)
2586 return chrec_dont_know;
2587
577d6588
RB
2588 /* While we eventually compute the same op1 if c0 == c1 the process
2589 of doing this is expensive so the following short-cut prevents
2590 exponential compile-time behavior. */
2591 if (c0 != c1)
2592 {
2593 op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2594 c1, fold_conversions, size_expr);
2595 if (op1 == chrec_dont_know)
2596 return chrec_dont_know;
2597 }
2598 else
2599 op1 = op0;
15fda317 2600
ffa34f4b
SP
2601 if (c0 != op0
2602 || c1 != op1)
15fda317 2603 {
15fda317
SP
2604 op0 = chrec_convert (type, op0, NULL);
2605 op1 = chrec_convert_rhs (type, op1, NULL);
2606
ffa34f4b 2607 switch (code)
15fda317
SP
2608 {
2609 case POINTER_PLUS_EXPR:
2610 case PLUS_EXPR:
2611 return chrec_fold_plus (type, op0, op1);
2612
2613 case MINUS_EXPR:
2614 return chrec_fold_minus (type, op0, op1);
2615
2616 case MULT_EXPR:
2617 return chrec_fold_multiply (type, op0, op1);
2618
2619 default:
2620 gcc_unreachable ();
2621 }
2622 }
2623
ffa34f4b 2624 return chrec ? chrec : fold_build2 (code, type, c0, c1);
15fda317
SP
2625}
2626
a213b219 2627/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
9c382ce9
SP
2628 and EVOLUTION_LOOP, that were left under a symbolic form.
2629
2630 "CHREC" that stands for a convert expression "(TYPE) OP" is to be
2631 instantiated.
2632
2633 CACHE is the cache of already instantiated values.
2634
c70ed622
BC
2635 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2636 conversions that may wrap in signed/pointer type are folded, as long
2637 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2638 then we don't do such fold.
9c382ce9
SP
2639
2640 SIZE_EXPR is used for computing the size of the expression to be
2641 instantiated, and to stop if it exceeds some limit. */
2642
2643static tree
a68f286c 2644instantiate_scev_convert (edge instantiate_below,
8b679c9b 2645 struct loop *evolution_loop, struct loop *inner_loop,
0547c9b6 2646 tree chrec, tree type, tree op,
c70ed622 2647 bool *fold_conversions, int size_expr)
9c382ce9 2648{
8b679c9b
RB
2649 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2650 inner_loop, op,
0547c9b6 2651 fold_conversions, size_expr);
9c382ce9
SP
2652
2653 if (op0 == chrec_dont_know)
2654 return chrec_dont_know;
2655
2656 if (fold_conversions)
2657 {
c70ed622 2658 tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
9c382ce9
SP
2659 if (tmp)
2660 return tmp;
9c382ce9 2661
c70ed622
BC
2662 /* If we used chrec_convert_aggressive, we can no longer assume that
2663 signed chrecs do not overflow, as chrec_convert does, so avoid
2664 calling it in that case. */
2665 if (*fold_conversions)
2666 {
2667 if (chrec && op0 == op)
2668 return chrec;
9c382ce9 2669
c70ed622
BC
2670 return fold_convert (type, op0);
2671 }
2672 }
9c382ce9
SP
2673
2674 return chrec_convert (type, op0, NULL);
2675}
2676
7ec0665d
SP
2677/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2678 and EVOLUTION_LOOP, that were left under a symbolic form.
2679
4b9d48a1 2680 CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
7ec0665d 2681 Handle ~X as -1 - X.
4b9d48a1 2682 Handle -X as -1 * X.
7ec0665d
SP
2683
2684 CACHE is the cache of already instantiated values.
2685
c70ed622
BC
2686 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2687 conversions that may wrap in signed/pointer type are folded, as long
2688 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2689 then we don't do such fold.
7ec0665d
SP
2690
2691 SIZE_EXPR is used for computing the size of the expression to be
2692 instantiated, and to stop if it exceeds some limit. */
2693
2694static tree
a68f286c 2695instantiate_scev_not (edge instantiate_below,
8b679c9b
RB
2696 struct loop *evolution_loop, struct loop *inner_loop,
2697 tree chrec,
20179b0d 2698 enum tree_code code, tree type, tree op,
c70ed622 2699 bool *fold_conversions, int size_expr)
7ec0665d 2700{
8b679c9b
RB
2701 tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2702 inner_loop, op,
0547c9b6 2703 fold_conversions, size_expr);
20179b0d 2704
7ec0665d
SP
2705 if (op0 == chrec_dont_know)
2706 return chrec_dont_know;
2707
20179b0d 2708 if (op != op0)
7ec0665d
SP
2709 {
2710 op0 = chrec_convert (type, op0, NULL);
4b9d48a1 2711
20179b0d 2712 switch (code)
4b9d48a1
SP
2713 {
2714 case BIT_NOT_EXPR:
2715 return chrec_fold_minus
2716 (type, fold_convert (type, integer_minus_one_node), op0);
2717
2718 case NEGATE_EXPR:
2719 return chrec_fold_multiply
2720 (type, fold_convert (type, integer_minus_one_node), op0);
2721
2722 default:
2723 gcc_unreachable ();
2724 }
7ec0665d 2725 }
4b9d48a1 2726
20179b0d 2727 return chrec ? chrec : fold_build1 (code, type, op0);
7ec0665d
SP
2728}
2729
9e5dc77f
SP
2730/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
2731 and EVOLUTION_LOOP, that were left under a symbolic form.
2732
2733 CHREC is the scalar evolution to instantiate.
2734
2735 CACHE is the cache of already instantiated values.
2282a0e6 2736
c70ed622
BC
2737 Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2738 conversions that may wrap in signed/pointer type are folded, as long
2739 as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2740 then we don't do such fold.
9e5dc77f
SP
2741
2742 SIZE_EXPR is used for computing the size of the expression to be
2743 instantiated, and to stop if it exceeds some limit. */
2744
2745static tree
a68f286c 2746instantiate_scev_r (edge instantiate_below,
8b679c9b
RB
2747 struct loop *evolution_loop, struct loop *inner_loop,
2748 tree chrec,
c70ed622 2749 bool *fold_conversions, int size_expr)
9e5dc77f 2750{
47ae9e4c
SP
2751 /* Give up if the expression is larger than the MAX that we allow. */
2752 if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2753 return chrec_dont_know;
2754
81fada9a
JJ
2755 if (chrec == NULL_TREE
2756 || automatically_generated_chrec_p (chrec)
d7770457 2757 || is_gimple_min_invariant (chrec))
9baba81b
SP
2758 return chrec;
2759
2760 switch (TREE_CODE (chrec))
2761 {
2762 case SSA_NAME:
8b679c9b
RB
2763 return instantiate_scev_name (instantiate_below, evolution_loop,
2764 inner_loop, chrec,
0547c9b6 2765 fold_conversions, size_expr);
9baba81b
SP
2766
2767 case POLYNOMIAL_CHREC:
8b679c9b
RB
2768 return instantiate_scev_poly (instantiate_below, evolution_loop,
2769 inner_loop, chrec,
0547c9b6 2770 fold_conversions, size_expr);
9baba81b 2771
5be014d5 2772 case POINTER_PLUS_EXPR:
9baba81b 2773 case PLUS_EXPR:
9baba81b 2774 case MINUS_EXPR:
9baba81b 2775 case MULT_EXPR:
8b679c9b
RB
2776 return instantiate_scev_binary (instantiate_below, evolution_loop,
2777 inner_loop, chrec,
ffa34f4b
SP
2778 TREE_CODE (chrec), chrec_type (chrec),
2779 TREE_OPERAND (chrec, 0),
2780 TREE_OPERAND (chrec, 1),
0547c9b6 2781 fold_conversions, size_expr);
9baba81b 2782
1043771b 2783 CASE_CONVERT:
8b679c9b
RB
2784 return instantiate_scev_convert (instantiate_below, evolution_loop,
2785 inner_loop, chrec,
9c382ce9 2786 TREE_TYPE (chrec), TREE_OPERAND (chrec, 0),
0547c9b6 2787 fold_conversions, size_expr);
9baba81b 2788
4b9d48a1 2789 case NEGATE_EXPR:
418df9d7 2790 case BIT_NOT_EXPR:
8b679c9b
RB
2791 return instantiate_scev_not (instantiate_below, evolution_loop,
2792 inner_loop, chrec,
20179b0d
SP
2793 TREE_CODE (chrec), TREE_TYPE (chrec),
2794 TREE_OPERAND (chrec, 0),
0547c9b6 2795 fold_conversions, size_expr);
418df9d7 2796
4c7d6755 2797 case ADDR_EXPR:
a68f286c
RB
2798 if (is_gimple_min_invariant (chrec))
2799 return chrec;
2800 /* Fallthru. */
9baba81b
SP
2801 case SCEV_NOT_KNOWN:
2802 return chrec_dont_know;
2803
2804 case SCEV_KNOWN:
2805 return chrec_known;
15fda317 2806
9baba81b 2807 default:
a68f286c
RB
2808 if (CONSTANT_CLASS_P (chrec))
2809 return chrec;
2810 return chrec_dont_know;
9baba81b 2811 }
9baba81b 2812}
e9eb809d
ZD
2813
2814/* Analyze all the parameters of the chrec that were left under a
a213b219
SP
2815 symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2816 recursive instantiation of parameters: a parameter is a variable
2817 that is defined in a basic block that dominates INSTANTIATE_BELOW or
2818 a function parameter. */
e9eb809d
ZD
2819
2820tree
a68f286c 2821instantiate_scev (edge instantiate_below, struct loop *evolution_loop,
3f227a8c 2822 tree chrec)
e9eb809d 2823{
9baba81b
SP
2824 tree res;
2825
dfedbe40 2826 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b 2827 {
3f227a8c 2828 fprintf (dump_file, "(instantiate_scev \n");
a68f286c
RB
2829 fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
2830 instantiate_below->src->index, instantiate_below->dest->index);
2831 if (evolution_loop)
2832 fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
9baba81b 2833 fprintf (dump_file, " (chrec = ");
ef6cb4c7 2834 print_generic_expr (dump_file, chrec);
9baba81b
SP
2835 fprintf (dump_file, ")\n");
2836 }
b8698a0f 2837
0547c9b6
RB
2838 bool destr = false;
2839 if (!global_cache)
2840 {
2841 global_cache = new instantiate_cache_type;
2842 destr = true;
2843 }
2844
8b679c9b 2845 res = instantiate_scev_r (instantiate_below, evolution_loop,
c70ed622 2846 NULL, chrec, NULL, 0);
0547c9b6
RB
2847
2848 if (destr)
2849 {
2850 delete global_cache;
2851 global_cache = NULL;
2852 }
9baba81b 2853
dfedbe40 2854 if (dump_file && (dump_flags & TDF_SCEV))
9baba81b
SP
2855 {
2856 fprintf (dump_file, " (res = ");
ef6cb4c7 2857 print_generic_expr (dump_file, res);
9baba81b
SP
2858 fprintf (dump_file, "))\n");
2859 }
eb0bc7af 2860
9baba81b
SP
2861 return res;
2862}
2863
2864/* Similar to instantiate_parameters, but does not introduce the
2282a0e6
ZD
2865 evolutions in outer loops for LOOP invariants in CHREC, and does not
2866 care about causing overflows, as long as they do not affect value
2867 of an expression. */
9baba81b 2868
3cb960c7 2869tree
c70ed622 2870resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts)
9baba81b 2871{
0547c9b6 2872 bool destr = false;
c70ed622 2873 bool fold_conversions = false;
0547c9b6
RB
2874 if (!global_cache)
2875 {
2876 global_cache = new instantiate_cache_type;
2877 destr = true;
2878 }
2879
a68f286c 2880 tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
c70ed622
BC
2881 chrec, &fold_conversions, 0);
2882
2883 if (folded_casts && !*folded_casts)
2884 *folded_casts = fold_conversions;
0547c9b6
RB
2885
2886 if (destr)
2887 {
2888 delete global_cache;
2889 global_cache = NULL;
2890 }
2891
eb0bc7af 2892 return ret;
9baba81b
SP
2893}
2894
b8698a0f 2895/* Entry point for the analysis of the number of iterations pass.
9baba81b
SP
2896 This function tries to safely approximate the number of iterations
2897 the loop will run. When this property is not decidable at compile
0a74c758
SP
2898 time, the result is chrec_dont_know. Otherwise the result is a
2899 scalar or a symbolic parameter. When the number of iterations may
2900 be equal to zero and the property cannot be determined at compile
2901 time, the result is a COND_EXPR that represents in a symbolic form
2902 the conditions under which the number of iterations is not zero.
b8698a0f 2903
9baba81b 2904 Example of analysis: suppose that the loop has an exit condition:
b8698a0f 2905
9baba81b 2906 "if (b > 49) goto end_loop;"
b8698a0f 2907
9baba81b
SP
2908 and that in a previous analysis we have determined that the
2909 variable 'b' has an evolution function:
b8698a0f
L
2910
2911 "EF = {23, +, 5}_2".
2912
9baba81b
SP
2913 When we evaluate the function at the point 5, i.e. the value of the
2914 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2915 and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2916 the loop body has been executed 6 times. */
2917
b8698a0f 2918tree
a14865db 2919number_of_latch_executions (struct loop *loop)
9baba81b 2920{
9baba81b
SP
2921 edge exit;
2922 struct tree_niter_desc niter_desc;
0a74c758
SP
2923 tree may_be_zero;
2924 tree res;
9baba81b 2925
0a74c758 2926 /* Determine whether the number of iterations in loop has already
9baba81b
SP
2927 been computed. */
2928 res = loop->nb_iterations;
2929 if (res)
2930 return res;
0a74c758
SP
2931
2932 may_be_zero = NULL_TREE;
9baba81b 2933
dfedbe40 2934 if (dump_file && (dump_flags & TDF_SCEV))
0a74c758 2935 fprintf (dump_file, "(number_of_iterations_in_loop = \n");
b8698a0f 2936
0a74c758 2937 res = chrec_dont_know;
ac8f6c69 2938 exit = single_exit (loop);
9baba81b 2939
0a74c758
SP
2940 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2941 {
2942 may_be_zero = niter_desc.may_be_zero;
2943 res = niter_desc.niter;
2944 }
2945
2946 if (res == chrec_dont_know
2947 || !may_be_zero
2948 || integer_zerop (may_be_zero))
2949 ;
2950 else if (integer_nonzerop (may_be_zero))
2951 res = build_int_cst (TREE_TYPE (res), 0);
9baba81b 2952
0a74c758
SP
2953 else if (COMPARISON_CLASS_P (may_be_zero))
2954 res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2955 build_int_cst (TREE_TYPE (res), 0), res);
9baba81b
SP
2956 else
2957 res = chrec_dont_know;
2958
dfedbe40 2959 if (dump_file && (dump_flags & TDF_SCEV))
0a74c758
SP
2960 {
2961 fprintf (dump_file, " (set_nb_iterations_in_loop = ");
ef6cb4c7 2962 print_generic_expr (dump_file, res);
0a74c758
SP
2963 fprintf (dump_file, "))\n");
2964 }
2965
2966 loop->nb_iterations = res;
2967 return res;
9baba81b 2968}
9baba81b
SP
2969\f
2970
2971/* Counters for the stats. */
2972
b8698a0f 2973struct chrec_stats
9baba81b
SP
2974{
2975 unsigned nb_chrecs;
2976 unsigned nb_affine;
2977 unsigned nb_affine_multivar;
2978 unsigned nb_higher_poly;
2979 unsigned nb_chrec_dont_know;
2980 unsigned nb_undetermined;
2981};
2982
2983/* Reset the counters. */
2984
2985static inline void
2986reset_chrecs_counters (struct chrec_stats *stats)
2987{
2988 stats->nb_chrecs = 0;
2989 stats->nb_affine = 0;
2990 stats->nb_affine_multivar = 0;
2991 stats->nb_higher_poly = 0;
2992 stats->nb_chrec_dont_know = 0;
2993 stats->nb_undetermined = 0;
2994}
2995
2996/* Dump the contents of a CHREC_STATS structure. */
2997
2998static void
2999dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
3000{
3001 fprintf (file, "\n(\n");
3002 fprintf (file, "-----------------------------------------\n");
3003 fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
3004 fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
b8698a0f 3005 fprintf (file, "%d\tdegree greater than 2 polynomials\n",
9baba81b
SP
3006 stats->nb_higher_poly);
3007 fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
3008 fprintf (file, "-----------------------------------------\n");
3009 fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
b8698a0f 3010 fprintf (file, "%d\twith undetermined coefficients\n",
9baba81b
SP
3011 stats->nb_undetermined);
3012 fprintf (file, "-----------------------------------------\n");
b8698a0f 3013 fprintf (file, "%d\tchrecs in the scev database\n",
907dadbd 3014 (int) scalar_evolution_info->elements ());
9baba81b
SP
3015 fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
3016 fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
3017 fprintf (file, "-----------------------------------------\n");
3018 fprintf (file, ")\n\n");
3019}
3020
3021/* Gather statistics about CHREC. */
3022
3023static void
3024gather_chrec_stats (tree chrec, struct chrec_stats *stats)
3025{
3026 if (dump_file && (dump_flags & TDF_STATS))
3027 {
3028 fprintf (dump_file, "(classify_chrec ");
ef6cb4c7 3029 print_generic_expr (dump_file, chrec);
9baba81b
SP
3030 fprintf (dump_file, "\n");
3031 }
b8698a0f 3032
9baba81b 3033 stats->nb_chrecs++;
b8698a0f 3034
9baba81b
SP
3035 if (chrec == NULL_TREE)
3036 {
3037 stats->nb_undetermined++;
3038 return;
3039 }
b8698a0f 3040
9baba81b
SP
3041 switch (TREE_CODE (chrec))
3042 {
3043 case POLYNOMIAL_CHREC:
3044 if (evolution_function_is_affine_p (chrec))
3045 {
3046 if (dump_file && (dump_flags & TDF_STATS))
3047 fprintf (dump_file, " affine_univariate\n");
3048 stats->nb_affine++;
3049 }
a50411de 3050 else if (evolution_function_is_affine_multivariate_p (chrec, 0))
9baba81b
SP
3051 {
3052 if (dump_file && (dump_flags & TDF_STATS))
3053 fprintf (dump_file, " affine_multivariate\n");
3054 stats->nb_affine_multivar++;
3055 }
3056 else
3057 {
3058 if (dump_file && (dump_flags & TDF_STATS))
3059 fprintf (dump_file, " higher_degree_polynomial\n");
3060 stats->nb_higher_poly++;
3061 }
b8698a0f 3062
9baba81b
SP
3063 break;
3064
3065 default:
3066 break;
3067 }
b8698a0f 3068
9baba81b
SP
3069 if (chrec_contains_undetermined (chrec))
3070 {
3071 if (dump_file && (dump_flags & TDF_STATS))
3072 fprintf (dump_file, " undetermined\n");
3073 stats->nb_undetermined++;
3074 }
b8698a0f 3075
9baba81b
SP
3076 if (dump_file && (dump_flags & TDF_STATS))
3077 fprintf (dump_file, ")\n");
3078}
3079
9baba81b
SP
3080/* Classify the chrecs of the whole database. */
3081
b8698a0f 3082void
9baba81b
SP
3083gather_stats_on_scev_database (void)
3084{
3085 struct chrec_stats stats;
b8698a0f 3086
9baba81b
SP
3087 if (!dump_file)
3088 return;
b8698a0f 3089
9baba81b 3090 reset_chrecs_counters (&stats);
b8698a0f 3091
907dadbd
TS
3092 hash_table<scev_info_hasher>::iterator iter;
3093 scev_info_str *elt;
3094 FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *,
3095 iter)
3096 gather_chrec_stats (elt->chrec, &stats);
9baba81b
SP
3097
3098 dump_chrecs_stats (dump_file, &stats);
3099}
3100
3101\f
3102
3103/* Initializer. */
3104
3105static void
3106initialize_scalar_evolutions_analyzer (void)
3107{
3108 /* The elements below are unique. */
3109 if (chrec_dont_know == NULL_TREE)
3110 {
3111 chrec_not_analyzed_yet = NULL_TREE;
3112 chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3113 chrec_known = make_node (SCEV_KNOWN);
d5ab5675
ZD
3114 TREE_TYPE (chrec_dont_know) = void_type_node;
3115 TREE_TYPE (chrec_known) = void_type_node;
9baba81b
SP
3116 }
3117}
3118
3119/* Initialize the analysis of scalar evolutions for LOOPS. */
3120
3121void
d73be268 3122scev_initialize (void)
9baba81b 3123{
42fd6772 3124 struct loop *loop;
9baba81b 3125
fb1fe1f3
RB
3126 gcc_assert (! scev_initialized_p ());
3127
907dadbd 3128 scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100);
b8698a0f 3129
9baba81b
SP
3130 initialize_scalar_evolutions_analyzer ();
3131
f0bd40b1 3132 FOR_EACH_LOOP (loop, 0)
42fd6772
ZD
3133 {
3134 loop->nb_iterations = NULL_TREE;
3135 }
9baba81b
SP
3136}
3137
e3a8f1fa
JH
3138/* Return true if SCEV is initialized. */
3139
3140bool
3141scev_initialized_p (void)
3142{
3143 return scalar_evolution_info != NULL;
3144}
3145
a7bf45de
SP
3146/* Cleans up the information cached by the scalar evolutions analysis
3147 in the hash table. */
3148
3149void
3150scev_reset_htab (void)
3151{
3152 if (!scalar_evolution_info)
3153 return;
3154
907dadbd 3155 scalar_evolution_info->empty ();
a7bf45de
SP
3156}
3157
3158/* Cleans up the information cached by the scalar evolutions analysis
3159 in the hash table and in the loop->nb_iterations. */
9baba81b
SP
3160
3161void
3162scev_reset (void)
3163{
9baba81b
SP
3164 struct loop *loop;
3165
a7bf45de
SP
3166 scev_reset_htab ();
3167
f0bd40b1 3168 FOR_EACH_LOOP (loop, 0)
9baba81b 3169 {
42fd6772 3170 loop->nb_iterations = NULL_TREE;
9baba81b 3171 }
e9eb809d
ZD
3172}
3173
1e3d54b4
JH
3174/* Return true if the IV calculation in TYPE can overflow based on the knowledge
3175 of the upper bound on the number of iterations of LOOP, the BASE and STEP
3176 of IV.
3177
3178 We do not use information whether TYPE can overflow so it is safe to
3179 use this test even for derived IVs not computed every iteration or
3180 hypotetical IVs to be inserted into code. */
3181
019d6598 3182bool
1e3d54b4
JH
3183iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
3184{
3185 widest_int nit;
3186 wide_int base_min, base_max, step_min, step_max, type_min, type_max;
3187 signop sgn = TYPE_SIGN (type);
3188
3189 if (integer_zerop (step))
3190 return false;
3191
3192 if (TREE_CODE (base) == INTEGER_CST)
8e6cdc90 3193 base_min = base_max = wi::to_wide (base);
1e3d54b4
JH
3194 else if (TREE_CODE (base) == SSA_NAME
3195 && INTEGRAL_TYPE_P (TREE_TYPE (base))
3196 && get_range_info (base, &base_min, &base_max) == VR_RANGE)
3197 ;
3198 else
3199 return true;
3200
3201 if (TREE_CODE (step) == INTEGER_CST)
8e6cdc90 3202 step_min = step_max = wi::to_wide (step);
1e3d54b4
JH
3203 else if (TREE_CODE (step) == SSA_NAME
3204 && INTEGRAL_TYPE_P (TREE_TYPE (step))
3205 && get_range_info (step, &step_min, &step_max) == VR_RANGE)
3206 ;
3207 else
3208 return true;
3209
3210 if (!get_max_loop_iterations (loop, &nit))
3211 return true;
3212
3213 type_min = wi::min_value (type);
3214 type_max = wi::max_value (type);
3215
3216 /* Just sanity check that we don't see values out of the range of the type.
3217 In this case the arithmetics bellow would overflow. */
3218 gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
3219 && wi::le_p (base_max, type_max, sgn));
3220
3221 /* Account the possible increment in the last ieration. */
4a669ac3 3222 wi::overflow_type overflow = wi::OVF_NONE;
1e3d54b4
JH
3223 nit = wi::add (nit, 1, SIGNED, &overflow);
3224 if (overflow)
3225 return true;
3226
3227 /* NIT is typeless and can exceed the precision of the type. In this case
3228 overflow is always possible, because we know STEP is non-zero. */
3229 if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
3230 return true;
3231 wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
3232
3233 /* If step can be positive, check that nit*step <= type_max-base.
3234 This can be done by unsigned arithmetic and we only need to watch overflow
3235 in the multiplication. The right hand side can always be represented in
3236 the type. */
3237 if (sgn == UNSIGNED || !wi::neg_p (step_max))
3238 {
4a669ac3 3239 wi::overflow_type overflow = wi::OVF_NONE;
1e3d54b4
JH
3240 if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
3241 type_max - base_max)
3242 || overflow)
3243 return true;
3244 }
3245 /* If step can be negative, check that nit*(-step) <= base_min-type_min. */
3246 if (sgn == SIGNED && wi::neg_p (step_min))
3247 {
4a669ac3
AH
3248 wi::overflow_type overflow, overflow2;
3249 overflow = overflow2 = wi::OVF_NONE;
1e3d54b4
JH
3250 if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
3251 nit2, UNSIGNED, &overflow),
3252 base_min - type_min)
3253 || overflow || overflow2)
3254 return true;
3255 }
3256
3257 return false;
3258}
3259
43aabfcf
BC
3260/* Given EV with form of "(type) {inner_base, inner_step}_loop", this
3261 function tries to derive condition under which it can be simplified
3262 into "{(type)inner_base, (type)inner_step}_loop". The condition is
3263 the maximum number that inner iv can iterate. */
3264
3265static tree
3266derive_simple_iv_with_niters (tree ev, tree *niters)
3267{
3268 if (!CONVERT_EXPR_P (ev))
3269 return ev;
3270
3271 tree inner_ev = TREE_OPERAND (ev, 0);
3272 if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
3273 return ev;
3274
3275 tree init = CHREC_LEFT (inner_ev);
3276 tree step = CHREC_RIGHT (inner_ev);
3277 if (TREE_CODE (init) != INTEGER_CST
3278 || TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3279 return ev;
3280
3281 tree type = TREE_TYPE (ev);
3282 tree inner_type = TREE_TYPE (inner_ev);
3283 if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
3284 return ev;
3285
3286 /* Type conversion in "(type) {inner_base, inner_step}_loop" can be
3287 folded only if inner iv won't overflow. We compute the maximum
3288 number the inner iv can iterate before overflowing and return the
3289 simplified affine iv. */
3290 tree delta;
3291 init = fold_convert (type, init);
3292 step = fold_convert (type, step);
3293 ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
3294 if (tree_int_cst_sign_bit (step))
3295 {
3296 tree bound = lower_bound_in_type (inner_type, inner_type);
3297 delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
3298 step = fold_build1 (NEGATE_EXPR, type, step);
3299 }
3300 else
3301 {
3302 tree bound = upper_bound_in_type (inner_type, inner_type);
3303 delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
3304 }
3305 *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
3306 return ev;
3307}
3308
f017bf5e
ZD
3309/* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
3310 respect to WRTO_LOOP and returns its base and step in IV if possible
3311 (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3312 and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3313 invariant in LOOP. Otherwise we require it to be an integer constant.
b8698a0f 3314
f017bf5e
ZD
3315 IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3316 because it is computed in signed arithmetics). Consequently, adding an
3317 induction variable
b8698a0f 3318
f017bf5e
ZD
3319 for (i = IV->base; ; i += IV->step)
3320
3321 is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3322 false for the type of the induction variable, or you can prove that i does
3323 not wrap by some other argument. Otherwise, this might introduce undefined
3324 behavior, and
b8698a0f 3325
43aabfcf
BC
3326 i = iv->base;
3327 for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3328
3329 must be used instead.
3330
3331 When IV_NITERS is not NULL, this function also checks case in which OP
3332 is a conversion of an inner simple iv of below form:
3333
3334 (outer_type){inner_base, inner_step}_loop.
f017bf5e 3335
43aabfcf
BC
3336 If type of inner iv has smaller precision than outer_type, it can't be
3337 folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3338 the inner iv could overflow/wrap. In this case, we derive a condition
3339 under which the inner iv won't overflow/wrap and do the simplification.
3340 The derived condition normally is the maximum number the inner iv can
3341 iterate, and will be stored in IV_NITERS. This is useful in loop niter
3342 analysis, to derive break conditions when a loop must terminate, when is
3343 infinite. */
e9eb809d
ZD
3344
3345bool
43aabfcf
BC
3346simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop,
3347 tree op, affine_iv *iv, tree *iv_niters,
3348 bool allow_nonconstant_step)
e9eb809d 3349{
f3c5f3a3 3350 enum tree_code code;
8aa46dd2 3351 tree type, ev, base, e;
f3c5f3a3 3352 wide_int extreme;
4a669ac3 3353 bool folded_casts;
9baba81b 3354
a6f778b2
ZD
3355 iv->base = NULL_TREE;
3356 iv->step = NULL_TREE;
3357 iv->no_overflow = false;
9baba81b
SP
3358
3359 type = TREE_TYPE (op);
1ee0d660
EB
3360 if (!POINTER_TYPE_P (type)
3361 && !INTEGRAL_TYPE_P (type))
9baba81b
SP
3362 return false;
3363
f017bf5e 3364 ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
a6f778b2 3365 &folded_casts);
f017bf5e
ZD
3366 if (chrec_contains_undetermined (ev)
3367 || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
9baba81b
SP
3368 return false;
3369
f017bf5e 3370 if (tree_does_not_contain_chrecs (ev))
9baba81b 3371 {
a6f778b2 3372 iv->base = ev;
6e42ce54 3373 iv->step = build_int_cst (TREE_TYPE (ev), 0);
a6f778b2 3374 iv->no_overflow = true;
9baba81b
SP
3375 return true;
3376 }
3377
43aabfcf
BC
3378 /* If we can derive valid scalar evolution with assumptions. */
3379 if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
3380 ev = derive_simple_iv_with_niters (ev, iv_niters);
3381
3382 if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
3383 return false;
3384
3385 if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
9baba81b
SP
3386 return false;
3387
a6f778b2 3388 iv->step = CHREC_RIGHT (ev);
f017bf5e
ZD
3389 if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3390 || tree_contains_chrecs (iv->step, NULL))
9baba81b 3391 return false;
9be872b7 3392
a6f778b2 3393 iv->base = CHREC_LEFT (ev);
f017bf5e 3394 if (tree_contains_chrecs (iv->base, NULL))
9baba81b
SP
3395 return false;
3396
1210573b 3397 iv->no_overflow = !folded_casts && nowrap_type_p (type);
eeef0e45 3398
1e3d54b4
JH
3399 if (!iv->no_overflow
3400 && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
3401 iv->no_overflow = true;
3402
f3c5f3a3
BC
3403 /* Try to simplify iv base:
3404
3405 (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3406 == (signed T)(unsigned T)base + step
3407 == base + step
3408
3409 If we can prove operation (base + step) doesn't overflow or underflow.
3410 Specifically, we try to prove below conditions are satisfied:
3411
3412 base <= UPPER_BOUND (type) - step ;;step > 0
3413 base >= LOWER_BOUND (type) - step ;;step < 0
3414
3415 This is done by proving the reverse conditions are false using loop's
3416 initial conditions.
3417
3418 The is necessary to make loop niter, or iv overflow analysis easier
3419 for below example:
3420
3421 int foo (int *a, signed char s, signed char l)
3422 {
3423 signed char i;
3424 for (i = s; i < l; i++)
3425 a[i] = 0;
3426 return 0;
3427 }
3428
3429 Note variable I is firstly converted to type unsigned char, incremented,
3430 then converted back to type signed char. */
3431
3432 if (wrto_loop->num != use_loop->num)
3433 return true;
3434
3435 if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST)
3436 return true;
3437
3438 type = TREE_TYPE (iv->base);
3439 e = TREE_OPERAND (iv->base, 0);
3440 if (TREE_CODE (e) != PLUS_EXPR
3441 || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
3442 || !tree_int_cst_equal (iv->step,
3443 fold_convert (type, TREE_OPERAND (e, 1))))
3444 return true;
3445 e = TREE_OPERAND (e, 0);
3446 if (!CONVERT_EXPR_P (e))
3447 return true;
3448 base = TREE_OPERAND (e, 0);
3449 if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3450 return true;
3451
3452 if (tree_int_cst_sign_bit (iv->step))
3453 {
3454 code = LT_EXPR;
3455 extreme = wi::min_value (type);
3456 }
3457 else
3458 {
3459 code = GT_EXPR;
3460 extreme = wi::max_value (type);
3461 }
4a669ac3 3462 wi::overflow_type overflow = wi::OVF_NONE;
8e6cdc90
RS
3463 extreme = wi::sub (extreme, wi::to_wide (iv->step),
3464 TYPE_SIGN (type), &overflow);
f3c5f3a3
BC
3465 if (overflow)
3466 return true;
3467 e = fold_build2 (code, boolean_type_node, base,
3468 wide_int_to_tree (type, extreme));
8aa46dd2 3469 e = simplify_using_initial_conditions (use_loop, e);
f3c5f3a3
BC
3470 if (!integer_zerop (e))
3471 return true;
3472
3473 if (POINTER_TYPE_P (TREE_TYPE (base)))
3474 code = POINTER_PLUS_EXPR;
3475 else
3476 code = PLUS_EXPR;
3477
3478 iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
9baba81b
SP
3479 return true;
3480}
3481
43aabfcf
BC
3482/* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple
3483 affine iv unconditionally. */
3484
3485bool
3486simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3487 affine_iv *iv, bool allow_nonconstant_step)
3488{
3489 return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
3490 NULL, allow_nonconstant_step);
3491}
3492
9baba81b
SP
3493/* Finalize the scalar evolution analysis. */
3494
3495void
3496scev_finalize (void)
3497{
d51157de
ZD
3498 if (!scalar_evolution_info)
3499 return;
907dadbd 3500 scalar_evolution_info->empty ();
c7b852c8 3501 scalar_evolution_info = NULL;
01f1c24e 3502 free_numbers_of_iterations_estimates (cfun);
9baba81b
SP
3503}
3504
771f882e
ZD
3505/* Returns true if the expression EXPR is considered to be too expensive
3506 for scev_const_prop. */
3507
3508bool
3509expression_expensive_p (tree expr)
3510{
3511 enum tree_code code;
3512
3513 if (is_gimple_val (expr))
3514 return false;
3515
3516 code = TREE_CODE (expr);
3517 if (code == TRUNC_DIV_EXPR
3518 || code == CEIL_DIV_EXPR
3519 || code == FLOOR_DIV_EXPR
3520 || code == ROUND_DIV_EXPR
3521 || code == TRUNC_MOD_EXPR
3522 || code == CEIL_MOD_EXPR
3523 || code == FLOOR_MOD_EXPR
3524 || code == ROUND_MOD_EXPR
3525 || code == EXACT_DIV_EXPR)
3526 {
3527 /* Division by power of two is usually cheap, so we allow it.
3528 Forbid anything else. */
3529 if (!integer_pow2p (TREE_OPERAND (expr, 1)))
3530 return true;
3531 }
3532
5126ae0c
KV
3533 if (code == CALL_EXPR)
3534 {
3535 tree arg;
3536 call_expr_arg_iterator iter;
06a6b46a
KV
3537 /* Even though is_inexpensive_builtin might say true, we will get a
3538 library call for popcount when backend does not have an instruction
3539 to do so. We consider this to be expenseive and generate
3540 __builtin_popcount only when backend defines it. */
3541 combined_fn cfn = get_call_combined_fn (expr);
3542 switch (cfn)
3543 {
3544 CASE_CFN_POPCOUNT:
3545 /* Check if opcode for popcount is available in the mode required. */
3546 if (optab_handler (popcount_optab,
3547 TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0))))
3548 == CODE_FOR_nothing)
3549 {
3550 machine_mode mode;
3551 mode = TYPE_MODE (TREE_TYPE (CALL_EXPR_ARG (expr, 0)));
3552 scalar_int_mode int_mode;
3553
3554 /* If the mode is of 2 * UNITS_PER_WORD size, we can handle
3555 double-word popcount by emitting two single-word popcount
3556 instructions. */
3557 if (is_a <scalar_int_mode> (mode, &int_mode)
3558 && GET_MODE_SIZE (int_mode) == 2 * UNITS_PER_WORD
3559 && (optab_handler (popcount_optab, word_mode)
3560 != CODE_FOR_nothing))
3561 break;
3562 return true;
3563 }
3564 default:
3565 break;
3566 }
5126ae0c
KV
3567
3568 if (!is_inexpensive_builtin (get_callee_fndecl (expr)))
3569 return true;
3570 FOR_EACH_CALL_EXPR_ARG (arg, iter, expr)
3571 if (expression_expensive_p (arg))
3572 return true;
3573 return false;
3574 }
3575
3f6f3319
KV
3576 if (code == COND_EXPR)
3577 return (expression_expensive_p (TREE_OPERAND (expr, 0))
3578 || (EXPR_P (TREE_OPERAND (expr, 1))
3579 && EXPR_P (TREE_OPERAND (expr, 2)))
3580 /* If either branch has side effects or could trap. */
3581 || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 1))
3582 || generic_expr_could_trap_p (TREE_OPERAND (expr, 1))
3583 || TREE_SIDE_EFFECTS (TREE_OPERAND (expr, 0))
3584 || generic_expr_could_trap_p (TREE_OPERAND (expr, 0))
3585 || expression_expensive_p (TREE_OPERAND (expr, 1))
3586 || expression_expensive_p (TREE_OPERAND (expr, 2)));
3587
771f882e
ZD
3588 switch (TREE_CODE_CLASS (code))
3589 {
3590 case tcc_binary:
3591 case tcc_comparison:
3592 if (expression_expensive_p (TREE_OPERAND (expr, 1)))
3593 return true;
3594
3595 /* Fallthru. */
3596 case tcc_unary:
3597 return expression_expensive_p (TREE_OPERAND (expr, 0));
3598
3599 default:
3600 return true;
3601 }
3602}
3603
4cc31a3c 3604/* Do final value replacement for LOOP, return true if we did anything. */
f993a853 3605
4cc31a3c 3606bool
f993a853
TV
3607final_value_replacement_loop (struct loop *loop)
3608{
3609 /* If we do not know exact number of iterations of the loop, we cannot
3610 replace the final value. */
3611 edge exit = single_exit (loop);
3612 if (!exit)
4cc31a3c 3613 return false;
f993a853
TV
3614
3615 tree niter = number_of_latch_executions (loop);
3616 if (niter == chrec_dont_know)
4cc31a3c 3617 return false;
f993a853
TV
3618
3619 /* Ensure that it is possible to insert new statements somewhere. */
3620 if (!single_pred_p (exit->dest))
3621 split_loop_exit_edge (exit);
3622
3623 /* Set stmt insertion pointer. All stmts are inserted before this point. */
3624 gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
3625
3626 struct loop *ex_loop
3627 = superloop_at_depth (loop,
3628 loop_depth (exit->dest->loop_father) + 1);
3629
4cc31a3c 3630 bool any = false;
f993a853
TV
3631 gphi_iterator psi;
3632 for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3633 {
3634 gphi *phi = psi.phi ();
3635 tree rslt = PHI_RESULT (phi);
3636 tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3637 if (virtual_operand_p (def))
3638 {
3639 gsi_next (&psi);
3640 continue;
3641 }
3642
3643 if (!POINTER_TYPE_P (TREE_TYPE (def))
3644 && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3645 {
3646 gsi_next (&psi);
3647 continue;
3648 }
3649
3650 bool folded_casts;
3651 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3652 &folded_casts);
3653 def = compute_overall_effect_of_inner_loop (ex_loop, def);
3654 if (!tree_does_not_contain_chrecs (def)
3655 || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3656 /* Moving the computation from the loop may prolong life range
3657 of some ssa names, which may cause problems if they appear
3658 on abnormal edges. */
3659 || contains_abnormal_ssa_name_p (def)
3660 /* Do not emit expensive expressions. The rationale is that
3661 when someone writes a code like
3662
3663 while (n > 45) n -= 45;
3664
3665 he probably knows that n is not large, and does not want it
3666 to be turned into n %= 45. */
3667 || expression_expensive_p (def))
3668 {
3669 if (dump_file && (dump_flags & TDF_DETAILS))
3670 {
3671 fprintf (dump_file, "not replacing:\n ");
ef6cb4c7 3672 print_gimple_stmt (dump_file, phi, 0);
f993a853
TV
3673 fprintf (dump_file, "\n");
3674 }
3675 gsi_next (&psi);
3676 continue;
3677 }
3678
3679 /* Eliminate the PHI node and replace it by a computation outside
3680 the loop. */
3681 if (dump_file)
3682 {
3683 fprintf (dump_file, "\nfinal value replacement:\n ");
ef6cb4c7 3684 print_gimple_stmt (dump_file, phi, 0);
47a5f7dd
AM
3685 fprintf (dump_file, " with expr: ");
3686 print_generic_expr (dump_file, def);
f993a853 3687 }
4cc31a3c 3688 any = true;
f993a853
TV
3689 def = unshare_expr (def);
3690 remove_phi_node (&psi, false);
3691
3692 /* If def's type has undefined overflow and there were folded
3693 casts, rewrite all stmts added for def into arithmetics
3694 with defined overflow behavior. */
3695 if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3696 && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3697 {
3698 gimple_seq stmts;
3699 gimple_stmt_iterator gsi2;
3700 def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3701 gsi2 = gsi_start (stmts);
3702 while (!gsi_end_p (gsi2))
3703 {
3704 gimple *stmt = gsi_stmt (gsi2);
3705 gimple_stmt_iterator gsi3 = gsi2;
3706 gsi_next (&gsi2);
3707 gsi_remove (&gsi3, false);
3708 if (is_gimple_assign (stmt)
3709 && arith_code_with_undefined_signed_overflow
3710 (gimple_assign_rhs_code (stmt)))
3711 gsi_insert_seq_before (&gsi,
3712 rewrite_to_defined_overflow (stmt),
3713 GSI_SAME_STMT);
3714 else
3715 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3716 }
3717 }
3718 else
3719 def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3720 true, GSI_SAME_STMT);
3721
3722 gassign *ass = gimple_build_assign (rslt, def);
3723 gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3724 if (dump_file)
3725 {
47a5f7dd 3726 fprintf (dump_file, "\n final stmt:\n ");
ef6cb4c7 3727 print_gimple_stmt (dump_file, ass, 0);
f993a853
TV
3728 fprintf (dump_file, "\n");
3729 }
3730 }
925196ed 3731
4cc31a3c 3732 return any;
684aaf29 3733}
9e2f83a5
ZD
3734
3735#include "gt-tree-scalar-evolution.h"