1169689Skan/* Scalar evolution detector.
2169689Skan   Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3169689Skan   Contributed by Sebastian Pop <s.pop@laposte.net>
4169689Skan
5169689SkanThis file is part of GCC.
6169689Skan
7169689SkanGCC is free software; you can redistribute it and/or modify it under
8169689Skanthe terms of the GNU General Public License as published by the Free
9169689SkanSoftware Foundation; either version 2, or (at your option) any later
10169689Skanversion.
11169689Skan
12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY
13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or
14169689SkanFITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15169689Skanfor more details.
16169689Skan
17169689SkanYou should have received a copy of the GNU General Public License
18169689Skanalong with GCC; see the file COPYING.  If not, write to the Free
19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20169689Skan02110-1301, USA.  */
21169689Skan
22169689Skan/*
23169689Skan   Description:
24169689Skan
25169689Skan   This pass analyzes the evolution of scalar variables in loop
26169689Skan   structures.  The algorithm is based on the SSA representation,
27169689Skan   and on the loop hierarchy tree.  This algorithm is not based on
28169689Skan   the notion of versions of a variable, as it was the case for the
29169689Skan   previous implementations of the scalar evolution algorithm, but
30169689Skan   it assumes that each defined name is unique.
31169689Skan
32169689Skan   The notation used in this file is called "chains of recurrences",
33169689Skan   and has been proposed by Eugene Zima, Robert Van Engelen, and
34169689Skan   others for describing induction variables in programs.  For example
35169689Skan   "b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
36169689Skan   when entering in the loop_1 and has a step 2 in this loop, in other
37169689Skan   words "for (b = 0; b < N; b+=2);".  Note that the coefficients of
38169689Skan   this chain of recurrence (or chrec [shrek]) can contain the name of
39169689Skan   other variables, in which case they are called parametric chrecs.
40169689Skan   For example, "b -> {a, +, 2}_1" means that the initial value of "b"
41169689Skan   is the value of "a".  In most of the cases these parametric chrecs
42169689Skan   are fully instantiated before their use because symbolic names can
43169689Skan   hide some difficult cases such as self-references described later
44169689Skan   (see the Fibonacci example).
45169689Skan
46169689Skan   A short sketch of the algorithm is:
47169689Skan
48169689Skan   Given a scalar variable to be analyzed, follow the SSA edge to
49169689Skan   its definition:
50169689Skan
51169689Skan   - When the definition is a MODIFY_EXPR: if the right hand side
52169689Skan   (RHS) of the definition cannot be statically analyzed, the answer
53169689Skan   of the analyzer is: "don't know".
54169689Skan   Otherwise, for all the variables that are not yet analyzed in the
55169689Skan   RHS, try to determine their evolution, and finally try to
56169689Skan   evaluate the operation of the RHS that gives the evolution
57169689Skan   function of the analyzed variable.
58169689Skan
59169689Skan   - When the definition is a condition-phi-node: determine the
60169689Skan   evolution function for all the branches of the phi node, and
61169689Skan   finally merge these evolutions (see chrec_merge).
62169689Skan
63169689Skan   - When the definition is a loop-phi-node: determine its initial
64169689Skan   condition, that is the SSA edge defined in an outer loop, and
65169689Skan   keep it symbolic.  Then determine the SSA edges that are defined
66169689Skan   in the body of the loop.  Follow the inner edges until ending on
67169689Skan   another loop-phi-node of the same analyzed loop.  If the reached
68169689Skan   loop-phi-node is not the starting loop-phi-node, then we keep
69169689Skan   this definition under a symbolic form.  If the reached
70169689Skan   loop-phi-node is the same as the starting one, then we compute a
71169689Skan   symbolic stride on the return path.  The result is then the
72169689Skan   symbolic chrec {initial_condition, +, symbolic_stride}_loop.
73169689Skan
74169689Skan   Examples:
75169689Skan
76169689Skan   Example 1: Illustration of the basic algorithm.
77169689Skan
78169689Skan   | a = 3
79169689Skan   | loop_1
80169689Skan   |   b = phi (a, c)
81169689Skan   |   c = b + 1
82169689Skan   |   if (c > 10) exit_loop
83169689Skan   | endloop
84169689Skan
85169689Skan   Suppose that we want to know the number of iterations of the
86169689Skan   loop_1.  The exit_loop is controlled by a COND_EXPR (c > 10).  We
87169689Skan   ask the scalar evolution analyzer two questions: what's the
88169689Skan   scalar evolution (scev) of "c", and what's the scev of "10".  For
89169689Skan   "10" the answer is "10" since it is a scalar constant.  For the
90169689Skan   scalar variable "c", it follows the SSA edge to its definition,
91169689Skan   "c = b + 1", and then asks again what's the scev of "b".
92169689Skan   Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93169689Skan   c)", where the initial condition is "a", and the inner loop edge
94169689Skan   is "c".  The initial condition is kept under a symbolic form (it
95169689Skan   may be the case that the copy constant propagation has done its
96169689Skan   work and we end with the constant "3" as one of the edges of the
97169689Skan   loop-phi-node).  The update edge is followed to the end of the
98169689Skan   loop, and until reaching again the starting loop-phi-node: b -> c
99169689Skan   -> b.  At this point we have drawn a path from "b" to "b" from
100169689Skan   which we compute the stride in the loop: in this example it is
101169689Skan   "+1".  The resulting scev for "b" is "b -> {a, +, 1}_1".  Now
102169689Skan   that the scev for "b" is known, it is possible to compute the
103169689Skan   scev for "c", that is "c -> {a + 1, +, 1}_1".  In order to
104169689Skan   determine the number of iterations in the loop_1, we have to
105169689Skan   instantiate_parameters ({a + 1, +, 1}_1), that gives after some
106169689Skan   more analysis the scev {4, +, 1}_1, or in other words, this is
107169689Skan   the function "f (x) = x + 4", where x is the iteration count of
108169689Skan   the loop_1.  Now we have to solve the inequality "x + 4 > 10",
109169689Skan   and take the smallest iteration number for which the loop is
110169689Skan   exited: x = 7.  This loop runs from x = 0 to x = 7, and in total
111169689Skan   there are 8 iterations.  In terms of loop normalization, we have
112169689Skan   created a variable that is implicitly defined, "x" or just "_1",
113169689Skan   and all the other analyzed scalars of the loop are defined in
114169689Skan   function of this variable:
115169689Skan
116169689Skan   a -> 3
117169689Skan   b -> {3, +, 1}_1
118169689Skan   c -> {4, +, 1}_1
119169689Skan
120169689Skan   or in terms of a C program:
121169689Skan
122169689Skan   | a = 3
123169689Skan   | for (x = 0; x <= 7; x++)
124169689Skan   |   {
125169689Skan   |     b = x + 3
126169689Skan   |     c = x + 4
127169689Skan   |   }
128169689Skan
129169689Skan   Example 2: Illustration of the algorithm on nested loops.
130169689Skan
131169689Skan   | loop_1
132169689Skan   |   a = phi (1, b)
133169689Skan   |   c = a + 2
134169689Skan   |   loop_2  10 times
135169689Skan   |     b = phi (c, d)
136169689Skan   |     d = b + 3
137169689Skan   |   endloop
138169689Skan   | endloop
139169689Skan
140169689Skan   For analyzing the scalar evolution of "a", the algorithm follows
141169689Skan   the SSA edge into the loop's body: "a -> b".  "b" is an inner
142169689Skan   loop-phi-node, and its analysis as in Example 1, gives:
143169689Skan
144169689Skan   b -> {c, +, 3}_2
145169689Skan   d -> {c + 3, +, 3}_2
146169689Skan
147169689Skan   Following the SSA edge for the initial condition, we end on "c = a
148169689Skan   + 2", and then on the starting loop-phi-node "a".  From this point,
149169689Skan   the loop stride is computed: back on "c = a + 2" we get a "+2" in
150169689Skan   the loop_1, then on the loop-phi-node "b" we compute the overall
151169689Skan   effect of the inner loop that is "b = c + 30", and we get a "+30"
152169689Skan   in the loop_1.  That means that the overall stride in loop_1 is
153169689Skan   equal to "+32", and the result is:
154169689Skan
155169689Skan   a -> {1, +, 32}_1
156169689Skan   c -> {3, +, 32}_1
157169689Skan
158169689Skan   Example 3: Higher degree polynomials.
159169689Skan
160169689Skan   | loop_1
161169689Skan   |   a = phi (2, b)
162169689Skan   |   c = phi (5, d)
163169689Skan   |   b = a + 1
164169689Skan   |   d = c + a
165169689Skan   | endloop
166169689Skan
167169689Skan   a -> {2, +, 1}_1
168169689Skan   b -> {3, +, 1}_1
169169689Skan   c -> {5, +, a}_1
170169689Skan   d -> {5 + a, +, a}_1
171169689Skan
172169689Skan   instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
173169689Skan   instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
174169689Skan
175169689Skan   Example 4: Lucas, Fibonacci, or mixers in general.
176169689Skan
177169689Skan   | loop_1
178169689Skan   |   a = phi (1, b)
179169689Skan   |   c = phi (3, d)
180169689Skan   |   b = c
181169689Skan   |   d = c + a
182169689Skan   | endloop
183169689Skan
184169689Skan   a -> (1, c)_1
185169689Skan   c -> {3, +, a}_1
186169689Skan
187169689Skan   The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
188169689Skan   following semantics: during the first iteration of the loop_1, the
189169689Skan   variable contains the value 1, and then it contains the value "c".
190169689Skan   Note that this syntax is close to the syntax of the loop-phi-node:
191169689Skan   "a -> (1, c)_1" vs. "a = phi (1, c)".
192169689Skan
193169689Skan   The symbolic chrec representation contains all the semantics of the
194169689Skan   original code.  What is more difficult is to use this information.
195169689Skan
196169689Skan   Example 5: Flip-flops, or exchangers.
197169689Skan
198169689Skan   | loop_1
199169689Skan   |   a = phi (1, b)
200169689Skan   |   c = phi (3, d)
201169689Skan   |   b = c
202169689Skan   |   d = a
203169689Skan   | endloop
204169689Skan
205169689Skan   a -> (1, c)_1
206169689Skan   c -> (3, a)_1
207169689Skan
208169689Skan   Based on these symbolic chrecs, it is possible to refine this
209169689Skan   information into the more precise PERIODIC_CHRECs:
210169689Skan
211169689Skan   a -> |1, 3|_1
212169689Skan   c -> |3, 1|_1
213169689Skan
214169689Skan   This transformation is not yet implemented.
215169689Skan
216169689Skan   Further readings:
217169689Skan
218169689Skan   You can find a more detailed description of the algorithm in:
219169689Skan   http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
220169689Skan   http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz.  But note that
221169689Skan   this is a preliminary report and some of the details of the
222169689Skan   algorithm have changed.  I'm working on a research report that
223169689Skan   updates the description of the algorithms to reflect the design
224169689Skan   choices used in this implementation.
225169689Skan
226169689Skan   A set of slides show a high level overview of the algorithm and run
227169689Skan   an example through the scalar evolution analyzer:
228169689Skan   http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
229169689Skan
230169689Skan   The slides that I have presented at the GCC Summit'04 are available
231169689Skan   at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
232169689Skan*/
233169689Skan
234169689Skan#include "config.h"
235169689Skan#include "system.h"
236169689Skan#include "coretypes.h"
237169689Skan#include "tm.h"
238169689Skan#include "ggc.h"
239169689Skan#include "tree.h"
240169689Skan#include "real.h"
241169689Skan
242169689Skan/* These RTL headers are needed for basic-block.h.  */
243169689Skan#include "rtl.h"
244169689Skan#include "basic-block.h"
245169689Skan#include "diagnostic.h"
246169689Skan#include "tree-flow.h"
247169689Skan#include "tree-dump.h"
248169689Skan#include "timevar.h"
249169689Skan#include "cfgloop.h"
250169689Skan#include "tree-chrec.h"
251169689Skan#include "tree-scalar-evolution.h"
252169689Skan#include "tree-pass.h"
253169689Skan#include "flags.h"
254169689Skan#include "params.h"
255169689Skan
256169689Skanstatic tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
257169689Skanstatic tree resolve_mixers (struct loop *, tree);
258169689Skan
259169689Skan/* The cached information about a ssa name VAR, claiming that inside LOOP,
260169689Skan   the value of VAR can be expressed as CHREC.  */
261169689Skan
262169689Skanstruct scev_info_str
263169689Skan{
264169689Skan  tree var;
265169689Skan  tree chrec;
266169689Skan};
267169689Skan
268169689Skan/* Counters for the scev database.  */
269169689Skanstatic unsigned nb_set_scev = 0;
270169689Skanstatic unsigned nb_get_scev = 0;
271169689Skan
272169689Skan/* The following trees are unique elements.  Thus the comparison of
273169689Skan   another element to these elements should be done on the pointer to
274169689Skan   these trees, and not on their value.  */
275169689Skan
276169689Skan/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.  */
277169689Skantree chrec_not_analyzed_yet;
278169689Skan
279169689Skan/* Reserved to the cases where the analyzer has detected an
280169689Skan   undecidable property at compile time.  */
281169689Skantree chrec_dont_know;
282169689Skan
283169689Skan/* When the analyzer has detected that a property will never
284169689Skan   happen, then it qualifies it with chrec_known.  */
285169689Skantree chrec_known;
286169689Skan
287169689Skanstatic bitmap already_instantiated;
288169689Skan
289169689Skanstatic htab_t scalar_evolution_info;
290169689Skan
291169689Skan
292169689Skan/* Constructs a new SCEV_INFO_STR structure.  */
293169689Skan
294169689Skanstatic inline struct scev_info_str *
295169689Skannew_scev_info_str (tree var)
296169689Skan{
297169689Skan  struct scev_info_str *res;
298169689Skan
299169689Skan  res = XNEW (struct scev_info_str);
300169689Skan  res->var = var;
301169689Skan  res->chrec = chrec_not_analyzed_yet;
302169689Skan
303169689Skan  return res;
304169689Skan}
305169689Skan
306169689Skan/* Computes a hash function for database element ELT.  */
307169689Skan
308169689Skanstatic hashval_t
309169689Skanhash_scev_info (const void *elt)
310169689Skan{
311169689Skan  return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
312169689Skan}
313169689Skan
314169689Skan/* Compares database elements E1 and E2.  */
315169689Skan
316169689Skanstatic int
317169689Skaneq_scev_info (const void *e1, const void *e2)
318169689Skan{
319169689Skan  const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
320169689Skan  const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
321169689Skan
322169689Skan  return elt1->var == elt2->var;
323169689Skan}
324169689Skan
325169689Skan/* Deletes database element E.  */
326169689Skan
327169689Skanstatic void
328169689Skandel_scev_info (void *e)
329169689Skan{
330169689Skan  free (e);
331169689Skan}
332169689Skan
333169689Skan/* Get the index corresponding to VAR in the current LOOP.  If
334169689Skan   it's the first time we ask for this VAR, then we return
335169689Skan   chrec_not_analyzed_yet for this VAR and return its index.  */
336169689Skan
337169689Skanstatic tree *
338169689Skanfind_var_scev_info (tree var)
339169689Skan{
340169689Skan  struct scev_info_str *res;
341169689Skan  struct scev_info_str tmp;
342169689Skan  PTR *slot;
343169689Skan
344169689Skan  tmp.var = var;
345169689Skan  slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
346169689Skan
347169689Skan  if (!*slot)
348169689Skan    *slot = new_scev_info_str (var);
349169689Skan  res = (struct scev_info_str *) *slot;
350169689Skan
351169689Skan  return &res->chrec;
352169689Skan}
353169689Skan
354169689Skan/* Return true when CHREC contains symbolic names defined in
355169689Skan   LOOP_NB.  */
356169689Skan
357169689Skanbool
358169689Skanchrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
359169689Skan{
360169689Skan  if (chrec == NULL_TREE)
361169689Skan    return false;
362169689Skan
363169689Skan  if (TREE_INVARIANT (chrec))
364169689Skan    return false;
365169689Skan
366169689Skan  if (TREE_CODE (chrec) == VAR_DECL
367169689Skan      || TREE_CODE (chrec) == PARM_DECL
368169689Skan      || TREE_CODE (chrec) == FUNCTION_DECL
369169689Skan      || TREE_CODE (chrec) == LABEL_DECL
370169689Skan      || TREE_CODE (chrec) == RESULT_DECL
371169689Skan      || TREE_CODE (chrec) == FIELD_DECL)
372169689Skan    return true;
373169689Skan
374169689Skan  if (TREE_CODE (chrec) == SSA_NAME)
375169689Skan    {
376169689Skan      tree def = SSA_NAME_DEF_STMT (chrec);
377169689Skan      struct loop *def_loop = loop_containing_stmt (def);
378169689Skan      struct loop *loop = current_loops->parray[loop_nb];
379169689Skan
380169689Skan      if (def_loop == NULL)
381169689Skan	return false;
382169689Skan
383169689Skan      if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
384169689Skan	return true;
385169689Skan
386169689Skan      return false;
387169689Skan    }
388169689Skan
389169689Skan  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
390169689Skan    {
391169689Skan    case 3:
392169689Skan      if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
393169689Skan						  loop_nb))
394169689Skan	return true;
395169689Skan
396169689Skan    case 2:
397169689Skan      if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
398169689Skan						  loop_nb))
399169689Skan	return true;
400169689Skan
401169689Skan    case 1:
402169689Skan      if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
403169689Skan						  loop_nb))
404169689Skan	return true;
405169689Skan
406169689Skan    default:
407169689Skan      return false;
408169689Skan    }
409169689Skan}
410169689Skan
411169689Skan/* Return true when PHI is a loop-phi-node.  */
412169689Skan
413169689Skanstatic bool
414169689Skanloop_phi_node_p (tree phi)
415169689Skan{
416169689Skan  /* The implementation of this function is based on the following
417169689Skan     property: "all the loop-phi-nodes of a loop are contained in the
418169689Skan     loop's header basic block".  */
419169689Skan
420169689Skan  return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
421169689Skan}
422169689Skan
423169689Skan/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
424169689Skan   In general, in the case of multivariate evolutions we want to get
425169689Skan   the evolution in different loops.  LOOP specifies the level for
426169689Skan   which to get the evolution.
427169689Skan
428169689Skan   Example:
429169689Skan
430169689Skan   | for (j = 0; j < 100; j++)
431169689Skan   |   {
432169689Skan   |     for (k = 0; k < 100; k++)
433169689Skan   |       {
434169689Skan   |         i = k + j;   - Here the value of i is a function of j, k.
435169689Skan   |       }
436169689Skan   |      ... = i         - Here the value of i is a function of j.
437169689Skan   |   }
438169689Skan   | ... = i              - Here the value of i is a scalar.
439169689Skan
440169689Skan   Example:
441169689Skan
442169689Skan   | i_0 = ...
443169689Skan   | loop_1 10 times
444169689Skan   |   i_1 = phi (i_0, i_2)
445169689Skan   |   i_2 = i_1 + 2
446169689Skan   | endloop
447169689Skan
448169689Skan   This loop has the same effect as:
449169689Skan   LOOP_1 has the same effect as:
450169689Skan
451169689Skan   | i_1 = i_0 + 20
452169689Skan
453169689Skan   The overall effect of the loop, "i_0 + 20" in the previous example,
454169689Skan   is obtained by passing in the parameters: LOOP = 1,
455169689Skan   EVOLUTION_FN = {i_0, +, 2}_1.
456169689Skan*/
457169689Skan
458169689Skanstatic tree
459169689Skancompute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
460169689Skan{
461169689Skan  bool val = false;
462169689Skan
463169689Skan  if (evolution_fn == chrec_dont_know)
464169689Skan    return chrec_dont_know;
465169689Skan
466169689Skan  else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
467169689Skan    {
468169689Skan      if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
469169689Skan	{
470169689Skan	  struct loop *inner_loop =
471169689Skan	    current_loops->parray[CHREC_VARIABLE (evolution_fn)];
472169689Skan	  tree nb_iter = number_of_iterations_in_loop (inner_loop);
473169689Skan
474169689Skan	  if (nb_iter == chrec_dont_know)
475169689Skan	    return chrec_dont_know;
476169689Skan	  else
477169689Skan	    {
478169689Skan	      tree res;
479169689Skan	      tree type = chrec_type (nb_iter);
480169689Skan
481169689Skan	      /* Number of iterations is off by one (the ssa name we
482169689Skan		 analyze must be defined before the exit).  */
483169689Skan	      nb_iter = chrec_fold_minus (type, nb_iter,
484169689Skan					  build_int_cst (type, 1));
485169689Skan
486169689Skan	      /* evolution_fn is the evolution function in LOOP.  Get
487169689Skan		 its value in the nb_iter-th iteration.  */
488169689Skan	      res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
489169689Skan
490169689Skan	      /* Continue the computation until ending on a parent of LOOP.  */
491169689Skan	      return compute_overall_effect_of_inner_loop (loop, res);
492169689Skan	    }
493169689Skan	}
494169689Skan      else
495169689Skan	return evolution_fn;
496169689Skan     }
497169689Skan
498169689Skan  /* If the evolution function is an invariant, there is nothing to do.  */
499169689Skan  else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
500169689Skan    return evolution_fn;
501169689Skan
502169689Skan  else
503169689Skan    return chrec_dont_know;
504169689Skan}
505169689Skan
506169689Skan/* Determine whether the CHREC is always positive/negative.  If the expression
507169689Skan   cannot be statically analyzed, return false, otherwise set the answer into
508169689Skan   VALUE.  */
509169689Skan
510169689Skanbool
511169689Skanchrec_is_positive (tree chrec, bool *value)
512169689Skan{
513169689Skan  bool value0, value1, value2;
514169689Skan  tree type, end_value, nb_iter;
515169689Skan
516169689Skan  switch (TREE_CODE (chrec))
517169689Skan    {
518169689Skan    case POLYNOMIAL_CHREC:
519169689Skan      if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
520169689Skan	  || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
521169689Skan	return false;
522169689Skan
523169689Skan      /* FIXME -- overflows.  */
524169689Skan      if (value0 == value1)
525169689Skan	{
526169689Skan	  *value = value0;
527169689Skan	  return true;
528169689Skan	}
529169689Skan
530169689Skan      /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
531169689Skan	 and the proof consists in showing that the sign never
532169689Skan	 changes during the execution of the loop, from 0 to
533169689Skan	 loop->nb_iterations.  */
534169689Skan      if (!evolution_function_is_affine_p (chrec))
535169689Skan	return false;
536169689Skan
537169689Skan      nb_iter = number_of_iterations_in_loop
538169689Skan	(current_loops->parray[CHREC_VARIABLE (chrec)]);
539169689Skan
540169689Skan      if (chrec_contains_undetermined (nb_iter))
541169689Skan	return false;
542169689Skan
543169689Skan      type = chrec_type (nb_iter);
544169689Skan      nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
545169689Skan
546169689Skan#if 0
547169689Skan      /* TODO -- If the test is after the exit, we may decrease the number of
548169689Skan	 iterations by one.  */
549169689Skan      if (after_exit)
550169689Skan	nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
551169689Skan#endif
552169689Skan
553169689Skan      end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
554169689Skan
555169689Skan      if (!chrec_is_positive (end_value, &value2))
556169689Skan	return false;
557169689Skan
558169689Skan      *value = value0;
559169689Skan      return value0 == value1;
560169689Skan
561169689Skan    case INTEGER_CST:
562169689Skan      *value = (tree_int_cst_sgn (chrec) == 1);
563169689Skan      return true;
564169689Skan
565169689Skan    default:
566169689Skan      return false;
567169689Skan    }
568169689Skan}
569169689Skan
570169689Skan/* Associate CHREC to SCALAR.  */
571169689Skan
572169689Skanstatic void
573169689Skanset_scalar_evolution (tree scalar, tree chrec)
574169689Skan{
575169689Skan  tree *scalar_info;
576169689Skan
577169689Skan  if (TREE_CODE (scalar) != SSA_NAME)
578169689Skan    return;
579169689Skan
580169689Skan  scalar_info = find_var_scev_info (scalar);
581169689Skan
582169689Skan  if (dump_file)
583169689Skan    {
584169689Skan      if (dump_flags & TDF_DETAILS)
585169689Skan	{
586169689Skan	  fprintf (dump_file, "(set_scalar_evolution \n");
587169689Skan	  fprintf (dump_file, "  (scalar = ");
588169689Skan	  print_generic_expr (dump_file, scalar, 0);
589169689Skan	  fprintf (dump_file, ")\n  (scalar_evolution = ");
590169689Skan	  print_generic_expr (dump_file, chrec, 0);
591169689Skan	  fprintf (dump_file, "))\n");
592169689Skan	}
593169689Skan      if (dump_flags & TDF_STATS)
594169689Skan	nb_set_scev++;
595169689Skan    }
596169689Skan
597169689Skan  *scalar_info = chrec;
598169689Skan}
599169689Skan
600169689Skan/* Retrieve the chrec associated to SCALAR in the LOOP.  */
601169689Skan
602169689Skanstatic tree
603169689Skanget_scalar_evolution (tree scalar)
604169689Skan{
605169689Skan  tree res;
606169689Skan
607169689Skan  if (dump_file)
608169689Skan    {
609169689Skan      if (dump_flags & TDF_DETAILS)
610169689Skan	{
611169689Skan	  fprintf (dump_file, "(get_scalar_evolution \n");
612169689Skan	  fprintf (dump_file, "  (scalar = ");
613169689Skan	  print_generic_expr (dump_file, scalar, 0);
614169689Skan	  fprintf (dump_file, ")\n");
615169689Skan	}
616169689Skan      if (dump_flags & TDF_STATS)
617169689Skan	nb_get_scev++;
618169689Skan    }
619169689Skan
620169689Skan  switch (TREE_CODE (scalar))
621169689Skan    {
622169689Skan    case SSA_NAME:
623169689Skan      res = *find_var_scev_info (scalar);
624169689Skan      break;
625169689Skan
626169689Skan    case REAL_CST:
627169689Skan    case INTEGER_CST:
628169689Skan      res = scalar;
629169689Skan      break;
630169689Skan
631169689Skan    default:
632169689Skan      res = chrec_not_analyzed_yet;
633169689Skan      break;
634169689Skan    }
635169689Skan
636169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
637169689Skan    {
638169689Skan      fprintf (dump_file, "  (scalar_evolution = ");
639169689Skan      print_generic_expr (dump_file, res, 0);
640169689Skan      fprintf (dump_file, "))\n");
641169689Skan    }
642169689Skan
643169689Skan  return res;
644169689Skan}
645169689Skan
646169689Skan/* Helper function for add_to_evolution.  Returns the evolution
647169689Skan   function for an assignment of the form "a = b + c", where "a" and
648169689Skan   "b" are on the strongly connected component.  CHREC_BEFORE is the
649169689Skan   information that we already have collected up to this point.
650169689Skan   TO_ADD is the evolution of "c".
651169689Skan
652169689Skan   When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
653169689Skan   evolution the expression TO_ADD, otherwise construct an evolution
654169689Skan   part for this loop.  */
655169689Skan
656169689Skanstatic tree
657169689Skanadd_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
658169689Skan		    tree at_stmt)
659169689Skan{
660169689Skan  tree type, left, right;
661169689Skan
662169689Skan  switch (TREE_CODE (chrec_before))
663169689Skan    {
664169689Skan    case POLYNOMIAL_CHREC:
665169689Skan      if (CHREC_VARIABLE (chrec_before) <= loop_nb)
666169689Skan	{
667169689Skan	  unsigned var;
668169689Skan
669169689Skan	  type = chrec_type (chrec_before);
670169689Skan
671169689Skan	  /* When there is no evolution part in this loop, build it.  */
672169689Skan	  if (CHREC_VARIABLE (chrec_before) < loop_nb)
673169689Skan	    {
674169689Skan	      var = loop_nb;
675169689Skan	      left = chrec_before;
676169689Skan	      right = SCALAR_FLOAT_TYPE_P (type)
677169689Skan		? build_real (type, dconst0)
678169689Skan		: build_int_cst (type, 0);
679169689Skan	    }
680169689Skan	  else
681169689Skan	    {
682169689Skan	      var = CHREC_VARIABLE (chrec_before);
683169689Skan	      left = CHREC_LEFT (chrec_before);
684169689Skan	      right = CHREC_RIGHT (chrec_before);
685169689Skan	    }
686169689Skan
687169689Skan	  to_add = chrec_convert (type, to_add, at_stmt);
688169689Skan	  right = chrec_convert (type, right, at_stmt);
689169689Skan	  right = chrec_fold_plus (type, right, to_add);
690169689Skan	  return build_polynomial_chrec (var, left, right);
691169689Skan	}
692169689Skan      else
693169689Skan	{
694169689Skan	  /* Search the evolution in LOOP_NB.  */
695169689Skan	  left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
696169689Skan				     to_add, at_stmt);
697169689Skan	  right = CHREC_RIGHT (chrec_before);
698169689Skan	  right = chrec_convert (chrec_type (left), right, at_stmt);
699169689Skan	  return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
700169689Skan					 left, right);
701169689Skan	}
702169689Skan
703169689Skan    default:
704169689Skan      /* These nodes do not depend on a loop.  */
705169689Skan      if (chrec_before == chrec_dont_know)
706169689Skan	return chrec_dont_know;
707169689Skan
708169689Skan      left = chrec_before;
709169689Skan      right = chrec_convert (chrec_type (left), to_add, at_stmt);
710169689Skan      return build_polynomial_chrec (loop_nb, left, right);
711169689Skan    }
712169689Skan}
713169689Skan
714169689Skan/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
715169689Skan   of LOOP_NB.
716169689Skan
717169689Skan   Description (provided for completeness, for those who read code in
718169689Skan   a plane, and for my poor 62 bytes brain that would have forgotten
719169689Skan   all this in the next two or three months):
720169689Skan
721169689Skan   The algorithm of translation of programs from the SSA representation
722169689Skan   into the chrecs syntax is based on a pattern matching.  After having
723169689Skan   reconstructed the overall tree expression for a loop, there are only
724169689Skan   two cases that can arise:
725169689Skan
726169689Skan   1. a = loop-phi (init, a + expr)
727169689Skan   2. a = loop-phi (init, expr)
728169689Skan
729169689Skan   where EXPR is either a scalar constant with respect to the analyzed
730169689Skan   loop (this is a degree 0 polynomial), or an expression containing
731169689Skan   other loop-phi definitions (these are higher degree polynomials).
732169689Skan
733169689Skan   Examples:
734169689Skan
735169689Skan   1.
736169689Skan   | init = ...
737169689Skan   | loop_1
738169689Skan   |   a = phi (init, a + 5)
739169689Skan   | endloop
740169689Skan
741169689Skan   2.
742169689Skan   | inita = ...
743169689Skan   | initb = ...
744169689Skan   | loop_1
745169689Skan   |   a = phi (inita, 2 * b + 3)
746169689Skan   |   b = phi (initb, b + 1)
747169689Skan   | endloop
748169689Skan
749169689Skan   For the first case, the semantics of the SSA representation is:
750169689Skan
751169689Skan   | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
752169689Skan
753169689Skan   that is, there is a loop index "x" that determines the scalar value
754169689Skan   of the variable during the loop execution.  During the first
755169689Skan   iteration, the value is that of the initial condition INIT, while
756169689Skan   during the subsequent iterations, it is the sum of the initial
757169689Skan   condition with the sum of all the values of EXPR from the initial
758169689Skan   iteration to the before last considered iteration.
759169689Skan
760169689Skan   For the second case, the semantics of the SSA program is:
761169689Skan
762169689Skan   | a (x) = init, if x = 0;
763169689Skan   |         expr (x - 1), otherwise.
764169689Skan
765169689Skan   The second case corresponds to the PEELED_CHREC, whose syntax is
766169689Skan   close to the syntax of a loop-phi-node:
767169689Skan
768169689Skan   | phi (init, expr)  vs.  (init, expr)_x
769169689Skan
770169689Skan   The proof of the translation algorithm for the first case is a
771169689Skan   proof by structural induction based on the degree of EXPR.
772169689Skan
773169689Skan   Degree 0:
774169689Skan   When EXPR is a constant with respect to the analyzed loop, or in
775169689Skan   other words when EXPR is a polynomial of degree 0, the evolution of
776169689Skan   the variable A in the loop is an affine function with an initial
777169689Skan   condition INIT, and a step EXPR.  In order to show this, we start
778169689Skan   from the semantics of the SSA representation:
779169689Skan
780169689Skan   f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
781169689Skan
782169689Skan   and since "expr (j)" is a constant with respect to "j",
783169689Skan
784169689Skan   f (x) = init + x * expr
785169689Skan
786169689Skan   Finally, based on the semantics of the pure sum chrecs, by
787169689Skan   identification we get the corresponding chrecs syntax:
788169689Skan
789169689Skan   f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
790169689Skan   f (x) -> {init, +, expr}_x
791169689Skan
792169689Skan   Higher degree:
793169689Skan   Suppose that EXPR is a polynomial of degree N with respect to the
794169689Skan   analyzed loop_x for which we have already determined that it is
795169689Skan   written under the chrecs syntax:
796169689Skan
797169689Skan   | expr (x)  ->  {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
798169689Skan
799169689Skan   We start from the semantics of the SSA program:
800169689Skan
801169689Skan   | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
802169689Skan   |
803169689Skan   | f (x) = init + \sum_{j = 0}^{x - 1}
804169689Skan   |                (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
805169689Skan   |
806169689Skan   | f (x) = init + \sum_{j = 0}^{x - 1}
807169689Skan   |                \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
808169689Skan   |
809169689Skan   | f (x) = init + \sum_{k = 0}^{n - 1}
810169689Skan   |                (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
811169689Skan   |
812169689Skan   | f (x) = init + \sum_{k = 0}^{n - 1}
813169689Skan   |                (b_k * \binom{x}{k + 1})
814169689Skan   |
815169689Skan   | f (x) = init + b_0 * \binom{x}{1} + ...
816169689Skan   |              + b_{n-1} * \binom{x}{n}
817169689Skan   |
818169689Skan   | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
819169689Skan   |                             + b_{n-1} * \binom{x}{n}
820169689Skan   |
821169689Skan
822169689Skan   And finally from the definition of the chrecs syntax, we identify:
823169689Skan   | f (x)  ->  {init, +, b_0, +, ..., +, b_{n-1}}_x
824169689Skan
825169689Skan   This shows the mechanism that stands behind the add_to_evolution
826169689Skan   function.  An important point is that the use of symbolic
827169689Skan   parameters avoids the need of an analysis schedule.
828169689Skan
829169689Skan   Example:
830169689Skan
831169689Skan   | inita = ...
832169689Skan   | initb = ...
833169689Skan   | loop_1
834169689Skan   |   a = phi (inita, a + 2 + b)
835169689Skan   |   b = phi (initb, b + 1)
836169689Skan   | endloop
837169689Skan
838169689Skan   When analyzing "a", the algorithm keeps "b" symbolically:
839169689Skan
840169689Skan   | a  ->  {inita, +, 2 + b}_1
841169689Skan
842169689Skan   Then, after instantiation, the analyzer ends on the evolution:
843169689Skan
844169689Skan   | a  ->  {inita, +, 2 + initb, +, 1}_1
845169689Skan
846169689Skan*/
847169689Skan
848169689Skanstatic tree
849169689Skanadd_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
850169689Skan		  tree to_add, tree at_stmt)
851169689Skan{
852169689Skan  tree type = chrec_type (to_add);
853169689Skan  tree res = NULL_TREE;
854169689Skan
855169689Skan  if (to_add == NULL_TREE)
856169689Skan    return chrec_before;
857169689Skan
858169689Skan  /* TO_ADD is either a scalar, or a parameter.  TO_ADD is not
859169689Skan     instantiated at this point.  */
860169689Skan  if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
861169689Skan    /* This should not happen.  */
862169689Skan    return chrec_dont_know;
863169689Skan
864169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
865169689Skan    {
866169689Skan      fprintf (dump_file, "(add_to_evolution \n");
867169689Skan      fprintf (dump_file, "  (loop_nb = %d)\n", loop_nb);
868169689Skan      fprintf (dump_file, "  (chrec_before = ");
869169689Skan      print_generic_expr (dump_file, chrec_before, 0);
870169689Skan      fprintf (dump_file, ")\n  (to_add = ");
871169689Skan      print_generic_expr (dump_file, to_add, 0);
872169689Skan      fprintf (dump_file, ")\n");
873169689Skan    }
874169689Skan
875169689Skan  if (code == MINUS_EXPR)
876169689Skan    to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
877169689Skan				  ? build_real (type, dconstm1)
878169689Skan				  : build_int_cst_type (type, -1));
879169689Skan
880169689Skan  res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
881169689Skan
882169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
883169689Skan    {
884169689Skan      fprintf (dump_file, "  (res = ");
885169689Skan      print_generic_expr (dump_file, res, 0);
886169689Skan      fprintf (dump_file, "))\n");
887169689Skan    }
888169689Skan
889169689Skan  return res;
890169689Skan}
891169689Skan
892169689Skan/* Helper function.  */
893169689Skan
894169689Skanstatic inline tree
895169689Skanset_nb_iterations_in_loop (struct loop *loop,
896169689Skan			   tree res)
897169689Skan{
898169689Skan  tree type = chrec_type (res);
899169689Skan
900169689Skan  res = chrec_fold_plus (type, res, build_int_cst (type, 1));
901169689Skan
902169689Skan  /* FIXME HWI: However we want to store one iteration less than the
903169689Skan     count of the loop in order to be compatible with the other
904169689Skan     nb_iter computations in loop-iv.  This also allows the
905169689Skan     representation of nb_iters that are equal to MAX_INT.  */
906169689Skan  if (TREE_CODE (res) == INTEGER_CST
907169689Skan      && (TREE_INT_CST_LOW (res) == 0
908169689Skan	  || TREE_OVERFLOW (res)))
909169689Skan    res = chrec_dont_know;
910169689Skan
911169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
912169689Skan    {
913169689Skan      fprintf (dump_file, "  (set_nb_iterations_in_loop = ");
914169689Skan      print_generic_expr (dump_file, res, 0);
915169689Skan      fprintf (dump_file, "))\n");
916169689Skan    }
917169689Skan
918169689Skan  loop->nb_iterations = res;
919169689Skan  return res;
920169689Skan}
921169689Skan
922169689Skan
923169689Skan
924169689Skan/* This section selects the loops that will be good candidates for the
925169689Skan   scalar evolution analysis.  For the moment, greedily select all the
926169689Skan   loop nests we could analyze.  */
927169689Skan
928169689Skan/* Return true when it is possible to analyze the condition expression
929169689Skan   EXPR.  */
930169689Skan
931169689Skanstatic bool
932169689Skananalyzable_condition (tree expr)
933169689Skan{
934169689Skan  tree condition;
935169689Skan
936169689Skan  if (TREE_CODE (expr) != COND_EXPR)
937169689Skan    return false;
938169689Skan
939169689Skan  condition = TREE_OPERAND (expr, 0);
940169689Skan
941169689Skan  switch (TREE_CODE (condition))
942169689Skan    {
943169689Skan    case SSA_NAME:
944169689Skan      return true;
945169689Skan
946169689Skan    case LT_EXPR:
947169689Skan    case LE_EXPR:
948169689Skan    case GT_EXPR:
949169689Skan    case GE_EXPR:
950169689Skan    case EQ_EXPR:
951169689Skan    case NE_EXPR:
952169689Skan      return true;
953169689Skan
954169689Skan    default:
955169689Skan      return false;
956169689Skan    }
957169689Skan
958169689Skan  return false;
959169689Skan}
960169689Skan
961169689Skan/* For a loop with a single exit edge, return the COND_EXPR that
962169689Skan   guards the exit edge.  If the expression is too difficult to
963169689Skan   analyze, then give up.  */
964169689Skan
965169689Skantree
966169689Skanget_loop_exit_condition (struct loop *loop)
967169689Skan{
968169689Skan  tree res = NULL_TREE;
969169689Skan  edge exit_edge = loop->single_exit;
970169689Skan
971169689Skan
972169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
973169689Skan    fprintf (dump_file, "(get_loop_exit_condition \n  ");
974169689Skan
975169689Skan  if (exit_edge)
976169689Skan    {
977169689Skan      tree expr;
978169689Skan
979169689Skan      expr = last_stmt (exit_edge->src);
980169689Skan      if (analyzable_condition (expr))
981169689Skan	res = expr;
982169689Skan    }
983169689Skan
984169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
985169689Skan    {
986169689Skan      print_generic_expr (dump_file, res, 0);
987169689Skan      fprintf (dump_file, ")\n");
988169689Skan    }
989169689Skan
990169689Skan  return res;
991169689Skan}
992169689Skan
993169689Skan/* Recursively determine and enqueue the exit conditions for a loop.  */
994169689Skan
995169689Skanstatic void
996169689Skanget_exit_conditions_rec (struct loop *loop,
997169689Skan			 VEC(tree,heap) **exit_conditions)
998169689Skan{
999169689Skan  if (!loop)
1000169689Skan    return;
1001169689Skan
1002169689Skan  /* Recurse on the inner loops, then on the next (sibling) loops.  */
1003169689Skan  get_exit_conditions_rec (loop->inner, exit_conditions);
1004169689Skan  get_exit_conditions_rec (loop->next, exit_conditions);
1005169689Skan
1006169689Skan  if (loop->single_exit)
1007169689Skan    {
1008169689Skan      tree loop_condition = get_loop_exit_condition (loop);
1009169689Skan
1010169689Skan      if (loop_condition)
1011169689Skan	VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
1012169689Skan    }
1013169689Skan}
1014169689Skan
1015169689Skan/* Select the candidate loop nests for the analysis.  This function
1016169689Skan   initializes the EXIT_CONDITIONS array.  */
1017169689Skan
1018169689Skanstatic void
1019169689Skanselect_loops_exit_conditions (struct loops *loops,
1020169689Skan			      VEC(tree,heap) **exit_conditions)
1021169689Skan{
1022169689Skan  struct loop *function_body = loops->parray[0];
1023169689Skan
1024169689Skan  get_exit_conditions_rec (function_body->inner, exit_conditions);
1025169689Skan}
1026169689Skan
1027169689Skan
1028169689Skan/* Depth first search algorithm.  */
1029169689Skan
1030169689Skantypedef enum t_bool {
1031169689Skan  t_false,
1032169689Skan  t_true,
1033169689Skan  t_dont_know
1034169689Skan} t_bool;
1035169689Skan
1036169689Skan
1037169689Skanstatic t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1038169689Skan
1039169689Skan/* Follow the ssa edge into the right hand side RHS of an assignment.
1040169689Skan   Return true if the strongly connected component has been found.  */
1041169689Skan
1042169689Skanstatic t_bool
1043169689Skanfollow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1044169689Skan			tree halting_phi, tree *evolution_of_loop, int limit)
1045169689Skan{
1046169689Skan  t_bool res = t_false;
1047169689Skan  tree rhs0, rhs1;
1048169689Skan  tree type_rhs = TREE_TYPE (rhs);
1049169689Skan  tree evol;
1050169689Skan
1051169689Skan  /* The RHS is one of the following cases:
1052169689Skan     - an SSA_NAME,
1053169689Skan     - an INTEGER_CST,
1054169689Skan     - a PLUS_EXPR,
1055169689Skan     - a MINUS_EXPR,
1056169689Skan     - an ASSERT_EXPR,
1057169689Skan     - other cases are not yet handled.  */
1058169689Skan  switch (TREE_CODE (rhs))
1059169689Skan    {
1060169689Skan    case NOP_EXPR:
1061169689Skan      /* This assignment is under the form "a_1 = (cast) rhs.  */
1062169689Skan      res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1063169689Skan				    halting_phi, evolution_of_loop, limit);
1064169689Skan      *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
1065169689Skan					  *evolution_of_loop, at_stmt);
1066169689Skan      break;
1067169689Skan
1068169689Skan    case INTEGER_CST:
1069169689Skan      /* This assignment is under the form "a_1 = 7".  */
1070169689Skan      res = t_false;
1071169689Skan      break;
1072169689Skan
1073169689Skan    case SSA_NAME:
1074169689Skan      /* This assignment is under the form: "a_1 = b_2".  */
1075169689Skan      res = follow_ssa_edge
1076169689Skan	(loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1077169689Skan      break;
1078169689Skan
1079169689Skan    case PLUS_EXPR:
1080169689Skan      /* This case is under the form "rhs0 + rhs1".  */
1081169689Skan      rhs0 = TREE_OPERAND (rhs, 0);
1082169689Skan      rhs1 = TREE_OPERAND (rhs, 1);
1083169689Skan      STRIP_TYPE_NOPS (rhs0);
1084169689Skan      STRIP_TYPE_NOPS (rhs1);
1085169689Skan
1086169689Skan      if (TREE_CODE (rhs0) == SSA_NAME)
1087169689Skan	{
1088169689Skan	  if (TREE_CODE (rhs1) == SSA_NAME)
1089169689Skan	    {
1090169689Skan	      /* Match an assignment under the form:
1091169689Skan		 "a = b + c".  */
1092169689Skan	      evol = *evolution_of_loop;
1093169689Skan	      res = follow_ssa_edge
1094169689Skan		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1095169689Skan		 &evol, limit);
1096169689Skan
1097169689Skan	      if (res == t_true)
1098169689Skan		*evolution_of_loop = add_to_evolution
1099169689Skan		  (loop->num,
1100169689Skan		   chrec_convert (type_rhs, evol, at_stmt),
1101169689Skan		   PLUS_EXPR, rhs1, at_stmt);
1102169689Skan
1103169689Skan	      else if (res == t_false)
1104169689Skan		{
1105169689Skan		  res = follow_ssa_edge
1106169689Skan		    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1107169689Skan		     evolution_of_loop, limit);
1108169689Skan
1109169689Skan		  if (res == t_true)
1110169689Skan		    *evolution_of_loop = add_to_evolution
1111169689Skan		      (loop->num,
1112169689Skan		       chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1113169689Skan		       PLUS_EXPR, rhs0, at_stmt);
1114169689Skan
1115169689Skan		  else if (res == t_dont_know)
1116169689Skan		    *evolution_of_loop = chrec_dont_know;
1117169689Skan		}
1118169689Skan
1119169689Skan	      else if (res == t_dont_know)
1120169689Skan		*evolution_of_loop = chrec_dont_know;
1121169689Skan	    }
1122169689Skan
1123169689Skan	  else
1124169689Skan	    {
1125169689Skan	      /* Match an assignment under the form:
1126169689Skan		 "a = b + ...".  */
1127169689Skan	      res = follow_ssa_edge
1128169689Skan		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1129169689Skan		 evolution_of_loop, limit);
1130169689Skan	      if (res == t_true)
1131169689Skan		*evolution_of_loop = add_to_evolution
1132169689Skan		  (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1133169689Skan					     at_stmt),
1134169689Skan		   PLUS_EXPR, rhs1, at_stmt);
1135169689Skan
1136169689Skan	      else if (res == t_dont_know)
1137169689Skan		*evolution_of_loop = chrec_dont_know;
1138169689Skan	    }
1139169689Skan	}
1140169689Skan
1141169689Skan      else if (TREE_CODE (rhs1) == SSA_NAME)
1142169689Skan	{
1143169689Skan	  /* Match an assignment under the form:
1144169689Skan	     "a = ... + c".  */
1145169689Skan	  res = follow_ssa_edge
1146169689Skan	    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1147169689Skan	     evolution_of_loop, limit);
1148169689Skan	  if (res == t_true)
1149169689Skan	    *evolution_of_loop = add_to_evolution
1150169689Skan	      (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1151169689Skan					 at_stmt),
1152169689Skan	       PLUS_EXPR, rhs0, at_stmt);
1153169689Skan
1154169689Skan	  else if (res == t_dont_know)
1155169689Skan	    *evolution_of_loop = chrec_dont_know;
1156169689Skan	}
1157169689Skan
1158169689Skan      else
1159169689Skan	/* Otherwise, match an assignment under the form:
1160169689Skan	   "a = ... + ...".  */
1161169689Skan	/* And there is nothing to do.  */
1162169689Skan	res = t_false;
1163169689Skan
1164169689Skan      break;
1165169689Skan
1166169689Skan    case MINUS_EXPR:
1167169689Skan      /* This case is under the form "opnd0 = rhs0 - rhs1".  */
1168169689Skan      rhs0 = TREE_OPERAND (rhs, 0);
1169169689Skan      rhs1 = TREE_OPERAND (rhs, 1);
1170169689Skan      STRIP_TYPE_NOPS (rhs0);
1171169689Skan      STRIP_TYPE_NOPS (rhs1);
1172169689Skan
1173169689Skan      if (TREE_CODE (rhs0) == SSA_NAME)
1174169689Skan	{
1175169689Skan	  /* Match an assignment under the form:
1176169689Skan	     "a = b - ...".  */
1177169689Skan	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1178169689Skan				 evolution_of_loop, limit);
1179169689Skan	  if (res == t_true)
1180169689Skan	    *evolution_of_loop = add_to_evolution
1181169689Skan	      (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1182169689Skan	       MINUS_EXPR, rhs1, at_stmt);
1183169689Skan
1184169689Skan	  else if (res == t_dont_know)
1185169689Skan	    *evolution_of_loop = chrec_dont_know;
1186169689Skan	}
1187169689Skan      else
1188169689Skan	/* Otherwise, match an assignment under the form:
1189169689Skan	   "a = ... - ...".  */
1190169689Skan	/* And there is nothing to do.  */
1191169689Skan	res = t_false;
1192169689Skan
1193169689Skan      break;
1194169689Skan
1195169689Skan    case ASSERT_EXPR:
1196169689Skan      {
1197169689Skan	/* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
1198169689Skan	   It must be handled as a copy assignment of the form a_1 = a_2.  */
1199169689Skan	tree op0 = ASSERT_EXPR_VAR (rhs);
1200169689Skan	if (TREE_CODE (op0) == SSA_NAME)
1201169689Skan	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1202169689Skan				 halting_phi, evolution_of_loop, limit);
1203169689Skan	else
1204169689Skan	  res = t_false;
1205169689Skan	break;
1206169689Skan      }
1207169689Skan
1208169689Skan
1209169689Skan    default:
1210169689Skan      res = t_false;
1211169689Skan      break;
1212169689Skan    }
1213169689Skan
1214169689Skan  return res;
1215169689Skan}
1216169689Skan
1217169689Skan/* Checks whether the I-th argument of a PHI comes from a backedge.  */
1218169689Skan
1219169689Skanstatic bool
1220169689Skanbackedge_phi_arg_p (tree phi, int i)
1221169689Skan{
1222169689Skan  edge e = PHI_ARG_EDGE (phi, i);
1223169689Skan
1224169689Skan  /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
1225169689Skan     about updating it anywhere, and this should work as well most of the
1226169689Skan     time.  */
1227169689Skan  if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1228169689Skan    return true;
1229169689Skan
1230169689Skan  return false;
1231169689Skan}
1232169689Skan
1233169689Skan/* Helper function for one branch of the condition-phi-node.  Return
1234169689Skan   true if the strongly connected component has been found following
1235169689Skan   this path.  */
1236169689Skan
1237169689Skanstatic inline t_bool
1238169689Skanfollow_ssa_edge_in_condition_phi_branch (int i,
1239169689Skan					 struct loop *loop,
1240169689Skan					 tree condition_phi,
1241169689Skan					 tree halting_phi,
1242169689Skan					 tree *evolution_of_branch,
1243169689Skan					 tree init_cond, int limit)
1244169689Skan{
1245169689Skan  tree branch = PHI_ARG_DEF (condition_phi, i);
1246169689Skan  *evolution_of_branch = chrec_dont_know;
1247169689Skan
1248169689Skan  /* Do not follow back edges (they must belong to an irreducible loop, which
1249169689Skan     we really do not want to worry about).  */
1250169689Skan  if (backedge_phi_arg_p (condition_phi, i))
1251169689Skan    return t_false;
1252169689Skan
1253169689Skan  if (TREE_CODE (branch) == SSA_NAME)
1254169689Skan    {
1255169689Skan      *evolution_of_branch = init_cond;
1256169689Skan      return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1257169689Skan			      evolution_of_branch, limit);
1258169689Skan    }
1259169689Skan
1260169689Skan  /* This case occurs when one of the condition branches sets
1261169689Skan     the variable to a constant: i.e. a phi-node like
1262169689Skan     "a_2 = PHI <a_7(5), 2(6)>;".
1263169689Skan
1264169689Skan     FIXME:  This case have to be refined correctly:
1265169689Skan     in some cases it is possible to say something better than
1266169689Skan     chrec_dont_know, for example using a wrap-around notation.  */
1267169689Skan  return t_false;
1268169689Skan}
1269169689Skan
1270169689Skan/* This function merges the branches of a condition-phi-node in a
1271169689Skan   loop.  */
1272169689Skan
1273169689Skanstatic t_bool
1274169689Skanfollow_ssa_edge_in_condition_phi (struct loop *loop,
1275169689Skan				  tree condition_phi,
1276169689Skan				  tree halting_phi,
1277169689Skan				  tree *evolution_of_loop, int limit)
1278169689Skan{
1279169689Skan  int i;
1280169689Skan  tree init = *evolution_of_loop;
1281169689Skan  tree evolution_of_branch;
1282169689Skan  t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1283169689Skan							halting_phi,
1284169689Skan							&evolution_of_branch,
1285169689Skan							init, limit);
1286169689Skan  if (res == t_false || res == t_dont_know)
1287169689Skan    return res;
1288169689Skan
1289169689Skan  *evolution_of_loop = evolution_of_branch;
1290169689Skan
1291169689Skan  for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
1292169689Skan    {
1293169689Skan      /* Quickly give up when the evolution of one of the branches is
1294169689Skan	 not known.  */
1295169689Skan      if (*evolution_of_loop == chrec_dont_know)
1296169689Skan	return t_true;
1297169689Skan
1298169689Skan      res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1299169689Skan						     halting_phi,
1300169689Skan						     &evolution_of_branch,
1301169689Skan						     init, limit);
1302169689Skan      if (res == t_false || res == t_dont_know)
1303169689Skan	return res;
1304169689Skan
1305169689Skan      *evolution_of_loop = chrec_merge (*evolution_of_loop,
1306169689Skan					evolution_of_branch);
1307169689Skan    }
1308169689Skan
1309169689Skan  return t_true;
1310169689Skan}
1311169689Skan
1312169689Skan/* Follow an SSA edge in an inner loop.  It computes the overall
1313169689Skan   effect of the loop, and following the symbolic initial conditions,
1314169689Skan   it follows the edges in the parent loop.  The inner loop is
1315169689Skan   considered as a single statement.  */
1316169689Skan
1317169689Skanstatic t_bool
1318169689Skanfollow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1319169689Skan				tree loop_phi_node,
1320169689Skan				tree halting_phi,
1321169689Skan				tree *evolution_of_loop, int limit)
1322169689Skan{
1323169689Skan  struct loop *loop = loop_containing_stmt (loop_phi_node);
1324169689Skan  tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1325169689Skan
1326169689Skan  /* Sometimes, the inner loop is too difficult to analyze, and the
1327169689Skan     result of the analysis is a symbolic parameter.  */
1328169689Skan  if (ev == PHI_RESULT (loop_phi_node))
1329169689Skan    {
1330169689Skan      t_bool res = t_false;
1331169689Skan      int i;
1332169689Skan
1333169689Skan      for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1334169689Skan	{
1335169689Skan	  tree arg = PHI_ARG_DEF (loop_phi_node, i);
1336169689Skan	  basic_block bb;
1337169689Skan
1338169689Skan	  /* Follow the edges that exit the inner loop.  */
1339169689Skan	  bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1340169689Skan	  if (!flow_bb_inside_loop_p (loop, bb))
1341169689Skan	    res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
1342169689Skan					  arg, halting_phi,
1343169689Skan					  evolution_of_loop, limit);
1344169689Skan	  if (res == t_true)
1345169689Skan	    break;
1346169689Skan	}
1347169689Skan
1348169689Skan      /* If the path crosses this loop-phi, give up.  */
1349169689Skan      if (res == t_true)
1350169689Skan	*evolution_of_loop = chrec_dont_know;
1351169689Skan
1352169689Skan      return res;
1353169689Skan    }
1354169689Skan
1355169689Skan  /* Otherwise, compute the overall effect of the inner loop.  */
1356169689Skan  ev = compute_overall_effect_of_inner_loop (loop, ev);
1357169689Skan  return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
1358169689Skan				 evolution_of_loop, limit);
1359169689Skan}
1360169689Skan
1361169689Skan/* Follow an SSA edge from a loop-phi-node to itself, constructing a
1362169689Skan   path that is analyzed on the return walk.  */
1363169689Skan
1364169689Skanstatic t_bool
1365169689Skanfollow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1366169689Skan		 tree *evolution_of_loop, int limit)
1367169689Skan{
1368169689Skan  struct loop *def_loop;
1369169689Skan
1370169689Skan  if (TREE_CODE (def) == NOP_EXPR)
1371169689Skan    return t_false;
1372169689Skan
1373169689Skan  /* Give up if the path is longer than the MAX that we allow.  */
1374169689Skan  if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
1375169689Skan    return t_dont_know;
1376169689Skan
1377169689Skan  def_loop = loop_containing_stmt (def);
1378169689Skan
1379169689Skan  switch (TREE_CODE (def))
1380169689Skan    {
1381169689Skan    case PHI_NODE:
1382169689Skan      if (!loop_phi_node_p (def))
1383169689Skan	/* DEF is a condition-phi-node.  Follow the branches, and
1384169689Skan	   record their evolutions.  Finally, merge the collected
1385169689Skan	   information and set the approximation to the main
1386169689Skan	   variable.  */
1387169689Skan	return follow_ssa_edge_in_condition_phi
1388169689Skan	  (loop, def, halting_phi, evolution_of_loop, limit);
1389169689Skan
1390169689Skan      /* When the analyzed phi is the halting_phi, the
1391169689Skan	 depth-first search is over: we have found a path from
1392169689Skan	 the halting_phi to itself in the loop.  */
1393169689Skan      if (def == halting_phi)
1394169689Skan	return t_true;
1395169689Skan
1396169689Skan      /* Otherwise, the evolution of the HALTING_PHI depends
1397169689Skan	 on the evolution of another loop-phi-node, i.e. the
1398169689Skan	 evolution function is a higher degree polynomial.  */
1399169689Skan      if (def_loop == loop)
1400169689Skan	return t_false;
1401169689Skan
1402169689Skan      /* Inner loop.  */
1403169689Skan      if (flow_loop_nested_p (loop, def_loop))
1404169689Skan	return follow_ssa_edge_inner_loop_phi
1405169689Skan	  (loop, def, halting_phi, evolution_of_loop, limit);
1406169689Skan
1407169689Skan      /* Outer loop.  */
1408169689Skan      return t_false;
1409169689Skan
1410169689Skan    case MODIFY_EXPR:
1411169689Skan      return follow_ssa_edge_in_rhs (loop, def,
1412169689Skan				     TREE_OPERAND (def, 1),
1413169689Skan				     halting_phi,
1414169689Skan				     evolution_of_loop, limit);
1415169689Skan
1416169689Skan    default:
1417169689Skan      /* At this level of abstraction, the program is just a set
1418169689Skan	 of MODIFY_EXPRs and PHI_NODEs.  In principle there is no
1419169689Skan	 other node to be handled.  */
1420169689Skan      return t_false;
1421169689Skan    }
1422169689Skan}
1423169689Skan
1424169689Skan
1425169689Skan
1426169689Skan/* Given a LOOP_PHI_NODE, this function determines the evolution
1427169689Skan   function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1428169689Skan
1429169689Skanstatic tree
1430169689Skananalyze_evolution_in_loop (tree loop_phi_node,
1431169689Skan			   tree init_cond)
1432169689Skan{
1433169689Skan  int i;
1434169689Skan  tree evolution_function = chrec_not_analyzed_yet;
1435169689Skan  struct loop *loop = loop_containing_stmt (loop_phi_node);
1436169689Skan  basic_block bb;
1437169689Skan
1438169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1439169689Skan    {
1440169689Skan      fprintf (dump_file, "(analyze_evolution_in_loop \n");
1441169689Skan      fprintf (dump_file, "  (loop_phi_node = ");
1442169689Skan      print_generic_expr (dump_file, loop_phi_node, 0);
1443169689Skan      fprintf (dump_file, ")\n");
1444169689Skan    }
1445169689Skan
1446169689Skan  for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1447169689Skan    {
1448169689Skan      tree arg = PHI_ARG_DEF (loop_phi_node, i);
1449169689Skan      tree ssa_chain, ev_fn;
1450169689Skan      t_bool res;
1451169689Skan
1452169689Skan      /* Select the edges that enter the loop body.  */
1453169689Skan      bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1454169689Skan      if (!flow_bb_inside_loop_p (loop, bb))
1455169689Skan	continue;
1456169689Skan
1457169689Skan      if (TREE_CODE (arg) == SSA_NAME)
1458169689Skan	{
1459169689Skan	  ssa_chain = SSA_NAME_DEF_STMT (arg);
1460169689Skan
1461169689Skan	  /* Pass in the initial condition to the follow edge function.  */
1462169689Skan	  ev_fn = init_cond;
1463169689Skan	  res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1464169689Skan	}
1465169689Skan      else
1466169689Skan	res = t_false;
1467169689Skan
1468169689Skan      /* When it is impossible to go back on the same
1469169689Skan	 loop_phi_node by following the ssa edges, the
1470169689Skan	 evolution is represented by a peeled chrec, i.e. the
1471169689Skan	 first iteration, EV_FN has the value INIT_COND, then
1472169689Skan	 all the other iterations it has the value of ARG.
1473169689Skan	 For the moment, PEELED_CHREC nodes are not built.  */
1474169689Skan      if (res != t_true)
1475169689Skan	ev_fn = chrec_dont_know;
1476169689Skan
1477169689Skan      /* When there are multiple back edges of the loop (which in fact never
1478169689Skan	 happens currently, but nevertheless), merge their evolutions.  */
1479169689Skan      evolution_function = chrec_merge (evolution_function, ev_fn);
1480169689Skan    }
1481169689Skan
1482169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1483169689Skan    {
1484169689Skan      fprintf (dump_file, "  (evolution_function = ");
1485169689Skan      print_generic_expr (dump_file, evolution_function, 0);
1486169689Skan      fprintf (dump_file, "))\n");
1487169689Skan    }
1488169689Skan
1489169689Skan  return evolution_function;
1490169689Skan}
1491169689Skan
1492169689Skan/* Given a loop-phi-node, return the initial conditions of the
1493169689Skan   variable on entry of the loop.  When the CCP has propagated
1494169689Skan   constants into the loop-phi-node, the initial condition is
1495169689Skan   instantiated, otherwise the initial condition is kept symbolic.
1496169689Skan   This analyzer does not analyze the evolution outside the current
1497169689Skan   loop, and leaves this task to the on-demand tree reconstructor.  */
1498169689Skan
1499169689Skanstatic tree
1500169689Skananalyze_initial_condition (tree loop_phi_node)
1501169689Skan{
1502169689Skan  int i;
1503169689Skan  tree init_cond = chrec_not_analyzed_yet;
1504169689Skan  struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1505169689Skan
1506169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1507169689Skan    {
1508169689Skan      fprintf (dump_file, "(analyze_initial_condition \n");
1509169689Skan      fprintf (dump_file, "  (loop_phi_node = \n");
1510169689Skan      print_generic_expr (dump_file, loop_phi_node, 0);
1511169689Skan      fprintf (dump_file, ")\n");
1512169689Skan    }
1513169689Skan
1514169689Skan  for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
1515169689Skan    {
1516169689Skan      tree branch = PHI_ARG_DEF (loop_phi_node, i);
1517169689Skan      basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
1518169689Skan
1519169689Skan      /* When the branch is oriented to the loop's body, it does
1520169689Skan     	 not contribute to the initial condition.  */
1521169689Skan      if (flow_bb_inside_loop_p (loop, bb))
1522169689Skan       	continue;
1523169689Skan
1524169689Skan      if (init_cond == chrec_not_analyzed_yet)
1525169689Skan	{
1526169689Skan	  init_cond = branch;
1527169689Skan	  continue;
1528169689Skan	}
1529169689Skan
1530169689Skan      if (TREE_CODE (branch) == SSA_NAME)
1531169689Skan	{
1532169689Skan	  init_cond = chrec_dont_know;
1533169689Skan      	  break;
1534169689Skan	}
1535169689Skan
1536169689Skan      init_cond = chrec_merge (init_cond, branch);
1537169689Skan    }
1538169689Skan
1539169689Skan  /* Ooops -- a loop without an entry???  */
1540169689Skan  if (init_cond == chrec_not_analyzed_yet)
1541169689Skan    init_cond = chrec_dont_know;
1542169689Skan
1543169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
1544169689Skan    {
1545169689Skan      fprintf (dump_file, "  (init_cond = ");
1546169689Skan      print_generic_expr (dump_file, init_cond, 0);
1547169689Skan      fprintf (dump_file, "))\n");
1548169689Skan    }
1549169689Skan
1550169689Skan  return init_cond;
1551169689Skan}
1552169689Skan
1553169689Skan/* Analyze the scalar evolution for LOOP_PHI_NODE.  */
1554169689Skan
1555169689Skanstatic tree
1556169689Skaninterpret_loop_phi (struct loop *loop, tree loop_phi_node)
1557169689Skan{
1558169689Skan  tree res;
1559169689Skan  struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1560169689Skan  tree init_cond;
1561169689Skan
1562169689Skan  if (phi_loop != loop)
1563169689Skan    {
1564169689Skan      struct loop *subloop;
1565169689Skan      tree evolution_fn = analyze_scalar_evolution
1566169689Skan	(phi_loop, PHI_RESULT (loop_phi_node));
1567169689Skan
1568169689Skan      /* Dive one level deeper.  */
1569169689Skan      subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1570169689Skan
1571169689Skan      /* Interpret the subloop.  */
1572169689Skan      res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
1573169689Skan      return res;
1574169689Skan    }
1575169689Skan
1576169689Skan  /* Otherwise really interpret the loop phi.  */
1577169689Skan  init_cond = analyze_initial_condition (loop_phi_node);
1578169689Skan  res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1579169689Skan
1580169689Skan  return res;
1581169689Skan}
1582169689Skan
1583169689Skan/* This function merges the branches of a condition-phi-node,
1584169689Skan   contained in the outermost loop, and whose arguments are already
1585169689Skan   analyzed.  */
1586169689Skan
1587169689Skanstatic tree
1588169689Skaninterpret_condition_phi (struct loop *loop, tree condition_phi)
1589169689Skan{
1590169689Skan  int i;
1591169689Skan  tree res = chrec_not_analyzed_yet;
1592169689Skan
1593169689Skan  for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
1594169689Skan    {
1595169689Skan      tree branch_chrec;
1596169689Skan
1597169689Skan      if (backedge_phi_arg_p (condition_phi, i))
1598169689Skan	{
1599169689Skan	  res = chrec_dont_know;
1600169689Skan	  break;
1601169689Skan	}
1602169689Skan
1603169689Skan      branch_chrec = analyze_scalar_evolution
1604169689Skan	(loop, PHI_ARG_DEF (condition_phi, i));
1605169689Skan
1606169689Skan      res = chrec_merge (res, branch_chrec);
1607169689Skan    }
1608169689Skan
1609169689Skan  return res;
1610169689Skan}
1611169689Skan
1612169689Skan/* Interpret the right hand side of a modify_expr OPND1.  If we didn't
1613169689Skan   analyze this node before, follow the definitions until ending
1614169689Skan   either on an analyzed modify_expr, or on a loop-phi-node.  On the
1615169689Skan   return path, this function propagates evolutions (ala constant copy
1616169689Skan   propagation).  OPND1 is not a GIMPLE expression because we could
1617169689Skan   analyze the effect of an inner loop: see interpret_loop_phi.  */
1618169689Skan
1619169689Skanstatic tree
1620169689Skaninterpret_rhs_modify_expr (struct loop *loop, tree at_stmt,
1621169689Skan			   tree opnd1, tree type)
1622169689Skan{
1623169689Skan  tree res, opnd10, opnd11, chrec10, chrec11;
1624169689Skan
1625169689Skan  if (is_gimple_min_invariant (opnd1))
1626169689Skan    return chrec_convert (type, opnd1, at_stmt);
1627169689Skan
1628169689Skan  switch (TREE_CODE (opnd1))
1629169689Skan    {
1630169689Skan    case PLUS_EXPR:
1631169689Skan      opnd10 = TREE_OPERAND (opnd1, 0);
1632169689Skan      opnd11 = TREE_OPERAND (opnd1, 1);
1633169689Skan      chrec10 = analyze_scalar_evolution (loop, opnd10);
1634169689Skan      chrec11 = analyze_scalar_evolution (loop, opnd11);
1635169689Skan      chrec10 = chrec_convert (type, chrec10, at_stmt);
1636169689Skan      chrec11 = chrec_convert (type, chrec11, at_stmt);
1637169689Skan      res = chrec_fold_plus (type, chrec10, chrec11);
1638169689Skan      break;
1639169689Skan
1640169689Skan    case MINUS_EXPR:
1641169689Skan      opnd10 = TREE_OPERAND (opnd1, 0);
1642169689Skan      opnd11 = TREE_OPERAND (opnd1, 1);
1643169689Skan      chrec10 = analyze_scalar_evolution (loop, opnd10);
1644169689Skan      chrec11 = analyze_scalar_evolution (loop, opnd11);
1645169689Skan      chrec10 = chrec_convert (type, chrec10, at_stmt);
1646169689Skan      chrec11 = chrec_convert (type, chrec11, at_stmt);
1647169689Skan      res = chrec_fold_minus (type, chrec10, chrec11);
1648169689Skan      break;
1649169689Skan
1650169689Skan    case NEGATE_EXPR:
1651169689Skan      opnd10 = TREE_OPERAND (opnd1, 0);
1652169689Skan      chrec10 = analyze_scalar_evolution (loop, opnd10);
1653169689Skan      chrec10 = chrec_convert (type, chrec10, at_stmt);
1654169689Skan      /* TYPE may be integer, real or complex, so use fold_convert.  */
1655169689Skan      res = chrec_fold_multiply (type, chrec10,
1656169689Skan				 fold_convert (type, integer_minus_one_node));
1657169689Skan      break;
1658169689Skan
1659169689Skan    case MULT_EXPR:
1660169689Skan      opnd10 = TREE_OPERAND (opnd1, 0);
1661169689Skan      opnd11 = TREE_OPERAND (opnd1, 1);
1662169689Skan      chrec10 = analyze_scalar_evolution (loop, opnd10);
1663169689Skan      chrec11 = analyze_scalar_evolution (loop, opnd11);
1664169689Skan      chrec10 = chrec_convert (type, chrec10, at_stmt);
1665169689Skan      chrec11 = chrec_convert (type, chrec11, at_stmt);
1666169689Skan      res = chrec_fold_multiply (type, chrec10, chrec11);
1667169689Skan      break;
1668169689Skan
1669169689Skan    case SSA_NAME:
1670169689Skan      res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1671169689Skan			   at_stmt);
1672169689Skan      break;
1673169689Skan
1674169689Skan    case ASSERT_EXPR:
1675169689Skan      opnd10 = ASSERT_EXPR_VAR (opnd1);
1676169689Skan      res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1677169689Skan			   at_stmt);
1678169689Skan      break;
1679169689Skan
1680169689Skan    case NOP_EXPR:
1681169689Skan    case CONVERT_EXPR:
1682169689Skan      opnd10 = TREE_OPERAND (opnd1, 0);
1683169689Skan      chrec10 = analyze_scalar_evolution (loop, opnd10);
1684169689Skan      res = chrec_convert (type, chrec10, at_stmt);
1685169689Skan      break;
1686169689Skan
1687169689Skan    default:
1688169689Skan      res = chrec_dont_know;
1689169689Skan      break;
1690169689Skan    }
1691169689Skan
1692169689Skan  return res;
1693169689Skan}
1694169689Skan
1695169689Skan
1696169689Skan
1697169689Skan/* This section contains all the entry points:
1698169689Skan   - number_of_iterations_in_loop,
1699169689Skan   - analyze_scalar_evolution,
1700169689Skan   - instantiate_parameters.
1701169689Skan*/
1702169689Skan
1703169689Skan/* Compute and return the evolution function in WRTO_LOOP, the nearest
1704169689Skan   common ancestor of DEF_LOOP and USE_LOOP.  */
1705169689Skan
1706169689Skanstatic tree
1707169689Skancompute_scalar_evolution_in_loop (struct loop *wrto_loop,
1708169689Skan				  struct loop *def_loop,
1709169689Skan				  tree ev)
1710169689Skan{
1711169689Skan  tree res;
1712169689Skan  if (def_loop == wrto_loop)
1713169689Skan    return ev;
1714169689Skan
1715169689Skan  def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
1716169689Skan  res = compute_overall_effect_of_inner_loop (def_loop, ev);
1717169689Skan
1718169689Skan  return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
1719169689Skan}
1720169689Skan
1721169689Skan/* Folds EXPR, if it is a cast to pointer, assuming that the created
1722169689Skan   polynomial_chrec does not wrap.  */
1723169689Skan
1724169689Skanstatic tree
1725169689Skanfold_used_pointer_cast (tree expr)
1726169689Skan{
1727169689Skan  tree op;
1728169689Skan  tree type, inner_type;
1729169689Skan
1730169689Skan  if (TREE_CODE (expr) != NOP_EXPR && TREE_CODE (expr) != CONVERT_EXPR)
1731169689Skan    return expr;
1732169689Skan
1733169689Skan  op = TREE_OPERAND (expr, 0);
1734169689Skan  if (TREE_CODE (op) != POLYNOMIAL_CHREC)
1735169689Skan    return expr;
1736169689Skan
1737169689Skan  type = TREE_TYPE (expr);
1738169689Skan  inner_type = TREE_TYPE (op);
1739169689Skan
1740169689Skan  if (!INTEGRAL_TYPE_P (inner_type)
1741169689Skan      || TYPE_PRECISION (inner_type) != TYPE_PRECISION (type))
1742169689Skan    return expr;
1743169689Skan
1744169689Skan  return build_polynomial_chrec (CHREC_VARIABLE (op),
1745169689Skan		chrec_convert (type, CHREC_LEFT (op), NULL_TREE),
1746169689Skan		chrec_convert (type, CHREC_RIGHT (op), NULL_TREE));
1747169689Skan}
1748169689Skan
1749169689Skan/* Returns true if EXPR is an expression corresponding to offset of pointer
1750169689Skan   in p + offset.  */
1751169689Skan
1752169689Skanstatic bool
1753169689Skanpointer_offset_p (tree expr)
1754169689Skan{
1755169689Skan  if (TREE_CODE (expr) == INTEGER_CST)
1756169689Skan    return true;
1757169689Skan
1758169689Skan  if ((TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1759169689Skan      && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))))
1760169689Skan    return true;
1761169689Skan
1762169689Skan  return false;
1763169689Skan}
1764169689Skan
1765169689Skan/* EXPR is a scalar evolution of a pointer that is dereferenced or used in
1766169689Skan   comparison.  This means that it must point to a part of some object in
1767169689Skan   memory, which enables us to argue about overflows and possibly simplify
1768169689Skan   the EXPR.  AT_STMT is the statement in which this conversion has to be
1769169689Skan   performed.  Returns the simplified value.
1770169689Skan
1771169689Skan   Currently, for
1772169689Skan
1773169689Skan   int i, n;
1774169689Skan   int *p;
1775169689Skan
1776169689Skan   for (i = -n; i < n; i++)
1777169689Skan     *(p + i) = ...;
1778169689Skan
1779169689Skan   We generate the following code (assuming that size of int and size_t is
1780169689Skan   4 bytes):
1781169689Skan
1782169689Skan   for (i = -n; i < n; i++)
1783169689Skan     {
1784169689Skan       size_t tmp1, tmp2;
1785169689Skan       int *tmp3, *tmp4;
1786169689Skan
1787169689Skan       tmp1 = (size_t) i;	(1)
1788169689Skan       tmp2 = 4 * tmp1;		(2)
1789169689Skan       tmp3 = (int *) tmp2;	(3)
1790169689Skan       tmp4 = p + tmp3;		(4)
1791169689Skan
1792169689Skan       *tmp4 = ...;
1793169689Skan     }
1794169689Skan
1795169689Skan   We in general assume that pointer arithmetics does not overflow (since its
1796169689Skan   behavior is undefined in that case).  One of the problems is that our
1797169689Skan   translation does not capture this property very well -- (int *) is
1798169689Skan   considered unsigned, hence the computation in (4) does overflow if i is
1799169689Skan   negative.
1800169689Skan
1801169689Skan   This impreciseness creates complications in scev analysis.  The scalar
1802169689Skan   evolution of i is [-n, +, 1].  Since int and size_t have the same precision
1803169689Skan   (in this example), and size_t is unsigned (so we do not care about
1804169689Skan   overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1]
1805169689Skan   and scev of tmp2 is [4 * (size_t) -n, +, 4].  With tmp3, we run into
1806169689Skan   problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several
1807169689Skan   places assume that this is not the case for scevs with pointer type, we
1808169689Skan   cannot use this scev for tmp3; hence, its scev is
1809169689Skan   (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is
1810169689Skan   p + (int *) [(4 * (size_t) -n), +, 4].  Most of the optimizers are unable to
1811169689Skan   work with scevs of this shape.
1812169689Skan
1813169689Skan   However, since tmp4 is dereferenced, all its values must belong to a single
1814169689Skan   object, and taking into account that the precision of int * and size_t is
1815169689Skan   the same, it is impossible for its scev to wrap.  Hence, we can derive that
1816169689Skan   its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers
1817169689Skan   can work with.
1818169689Skan
1819169689Skan   ??? Maybe we should use different representation for pointer arithmetics,
1820169689Skan   however that is a long-term project with a lot of potential for creating
1821169689Skan   bugs.  */
1822169689Skan
1823169689Skanstatic tree
1824169689Skanfold_used_pointer (tree expr, tree at_stmt)
1825169689Skan{
1826169689Skan  tree op0, op1, new0, new1;
1827169689Skan  enum tree_code code = TREE_CODE (expr);
1828169689Skan
1829169689Skan  if (code == PLUS_EXPR
1830169689Skan      || code == MINUS_EXPR)
1831169689Skan    {
1832169689Skan      op0 = TREE_OPERAND (expr, 0);
1833169689Skan      op1 = TREE_OPERAND (expr, 1);
1834169689Skan
1835169689Skan      if (pointer_offset_p (op1))
1836169689Skan	{
1837169689Skan	  new0 = fold_used_pointer (op0, at_stmt);
1838169689Skan	  new1 = fold_used_pointer_cast (op1);
1839169689Skan	}
1840169689Skan      else if (code == PLUS_EXPR && pointer_offset_p (op0))
1841169689Skan	{
1842169689Skan	  new0 = fold_used_pointer_cast (op0);
1843169689Skan	  new1 = fold_used_pointer (op1, at_stmt);
1844169689Skan	}
1845169689Skan      else
1846169689Skan	return expr;
1847169689Skan
1848169689Skan      if (new0 == op0 && new1 == op1)
1849169689Skan	return expr;
1850169689Skan
1851169689Skan      new0 = chrec_convert (TREE_TYPE (expr), new0, at_stmt);
1852169689Skan      new1 = chrec_convert (TREE_TYPE (expr), new1, at_stmt);
1853169689Skan
1854169689Skan      if (code == PLUS_EXPR)
1855169689Skan	expr = chrec_fold_plus (TREE_TYPE (expr), new0, new1);
1856169689Skan      else
1857169689Skan	expr = chrec_fold_minus (TREE_TYPE (expr), new0, new1);
1858169689Skan
1859169689Skan      return expr;
1860169689Skan    }
1861169689Skan  else
1862169689Skan    return fold_used_pointer_cast (expr);
1863169689Skan}
1864169689Skan
1865169689Skan/* Returns true if PTR is dereferenced, or used in comparison.  */
1866169689Skan
1867169689Skanstatic bool
1868169689Skanpointer_used_p (tree ptr)
1869169689Skan{
1870169689Skan  use_operand_p use_p;
1871169689Skan  imm_use_iterator imm_iter;
1872169689Skan  tree stmt, rhs;
1873169689Skan  struct ptr_info_def *pi = get_ptr_info (ptr);
1874169689Skan  var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
1875169689Skan
1876169689Skan  /* Check whether the pointer has a memory tag; if it does, it is
1877169689Skan     (or at least used to be) dereferenced.  */
1878169689Skan  if ((pi != NULL && pi->name_mem_tag != NULL)
1879169689Skan      || v_ann->symbol_mem_tag)
1880169689Skan    return true;
1881169689Skan
1882169689Skan  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ptr)
1883169689Skan    {
1884169689Skan      stmt = USE_STMT (use_p);
1885169689Skan      if (TREE_CODE (stmt) == COND_EXPR)
1886169689Skan	return true;
1887169689Skan
1888169689Skan      if (TREE_CODE (stmt) != MODIFY_EXPR)
1889169689Skan	continue;
1890169689Skan
1891169689Skan      rhs = TREE_OPERAND (stmt, 1);
1892169689Skan      if (!COMPARISON_CLASS_P (rhs))
1893169689Skan	continue;
1894169689Skan
1895169689Skan      if (TREE_OPERAND (stmt, 0) == ptr
1896169689Skan	  || TREE_OPERAND (stmt, 1) == ptr)
1897169689Skan	return true;
1898169689Skan    }
1899169689Skan
1900169689Skan  return false;
1901169689Skan}
1902169689Skan
1903169689Skan/* Helper recursive function.  */
1904169689Skan
1905169689Skanstatic tree
1906169689Skananalyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1907169689Skan{
1908169689Skan  tree def, type = TREE_TYPE (var);
1909169689Skan  basic_block bb;
1910169689Skan  struct loop *def_loop;
1911169689Skan
1912169689Skan  if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1913169689Skan    return chrec_dont_know;
1914169689Skan
1915169689Skan  if (TREE_CODE (var) != SSA_NAME)
1916169689Skan    return interpret_rhs_modify_expr (loop, NULL_TREE, var, type);
1917169689Skan
1918169689Skan  def = SSA_NAME_DEF_STMT (var);
1919169689Skan  bb = bb_for_stmt (def);
1920169689Skan  def_loop = bb ? bb->loop_father : NULL;
1921169689Skan
1922169689Skan  if (bb == NULL
1923169689Skan      || !flow_bb_inside_loop_p (loop, bb))
1924169689Skan    {
1925169689Skan      /* Keep the symbolic form.  */
1926169689Skan      res = var;
1927169689Skan      goto set_and_end;
1928169689Skan    }
1929169689Skan
1930169689Skan  if (res != chrec_not_analyzed_yet)
1931169689Skan    {
1932169689Skan      if (loop != bb->loop_father)
1933169689Skan	res = compute_scalar_evolution_in_loop
1934169689Skan	    (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1935169689Skan
1936169689Skan      goto set_and_end;
1937169689Skan    }
1938169689Skan
1939169689Skan  if (loop != def_loop)
1940169689Skan    {
1941169689Skan      res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
1942169689Skan      res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1943169689Skan
1944169689Skan      goto set_and_end;
1945169689Skan    }
1946169689Skan
1947169689Skan  switch (TREE_CODE (def))
1948169689Skan    {
1949169689Skan    case MODIFY_EXPR:
1950169689Skan      res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type);
1951169689Skan
1952169689Skan      if (POINTER_TYPE_P (type)
1953169689Skan	  && !automatically_generated_chrec_p (res)
1954169689Skan	  && pointer_used_p (var))
1955169689Skan	res = fold_used_pointer (res, def);
1956169689Skan      break;
1957169689Skan
1958169689Skan    case PHI_NODE:
1959169689Skan      if (loop_phi_node_p (def))
1960169689Skan	res = interpret_loop_phi (loop, def);
1961169689Skan      else
1962169689Skan	res = interpret_condition_phi (loop, def);
1963169689Skan      break;
1964169689Skan
1965169689Skan    default:
1966169689Skan      res = chrec_dont_know;
1967169689Skan      break;
1968169689Skan    }
1969169689Skan
1970169689Skan set_and_end:
1971169689Skan
1972169689Skan  /* Keep the symbolic form.  */
1973169689Skan  if (res == chrec_dont_know)
1974169689Skan    res = var;
1975169689Skan
1976169689Skan  if (loop == def_loop)
1977169689Skan    set_scalar_evolution (var, res);
1978169689Skan
1979169689Skan  return res;
1980169689Skan}
1981169689Skan
1982169689Skan/* Entry point for the scalar evolution analyzer.
1983169689Skan   Analyzes and returns the scalar evolution of the ssa_name VAR.
1984169689Skan   LOOP_NB is the identifier number of the loop in which the variable
1985169689Skan   is used.
1986169689Skan
1987169689Skan   Example of use: having a pointer VAR to a SSA_NAME node, STMT a
1988169689Skan   pointer to the statement that uses this variable, in order to
1989169689Skan   determine the evolution function of the variable, use the following
1990169689Skan   calls:
1991169689Skan
1992169689Skan   unsigned loop_nb = loop_containing_stmt (stmt)->num;
1993169689Skan   tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
1994169689Skan   tree chrec_instantiated = instantiate_parameters
1995169689Skan   (loop_nb, chrec_with_symbols);
1996169689Skan*/
1997169689Skan
1998169689Skantree
1999169689Skananalyze_scalar_evolution (struct loop *loop, tree var)
2000169689Skan{
2001169689Skan  tree res;
2002169689Skan
2003169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
2004169689Skan    {
2005169689Skan      fprintf (dump_file, "(analyze_scalar_evolution \n");
2006169689Skan      fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2007169689Skan      fprintf (dump_file, "  (scalar = ");
2008169689Skan      print_generic_expr (dump_file, var, 0);
2009169689Skan      fprintf (dump_file, ")\n");
2010169689Skan    }
2011169689Skan
2012169689Skan  res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
2013169689Skan
2014169689Skan  if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
2015169689Skan    res = var;
2016169689Skan
2017169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
2018169689Skan    fprintf (dump_file, ")\n");
2019169689Skan
2020169689Skan  return res;
2021169689Skan}
2022169689Skan
2023169689Skan/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
2024169689Skan   WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
2025169689Skan   of VERSION).
2026169689Skan
2027169689Skan   FOLDED_CASTS is set to true if resolve_mixers used
2028169689Skan   chrec_convert_aggressive (TODO -- not really, we are way too conservative
2029169689Skan   at the moment in order to keep things simple).  */
2030169689Skan
2031169689Skanstatic tree
2032169689Skananalyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2033169689Skan				  tree version, bool *folded_casts)
2034169689Skan{
2035169689Skan  bool val = false;
2036169689Skan  tree ev = version, tmp;
2037169689Skan
2038169689Skan  if (folded_casts)
2039169689Skan    *folded_casts = false;
2040169689Skan  while (1)
2041169689Skan    {
2042169689Skan      tmp = analyze_scalar_evolution (use_loop, ev);
2043169689Skan      ev = resolve_mixers (use_loop, tmp);
2044169689Skan
2045169689Skan      if (folded_casts && tmp != ev)
2046169689Skan	*folded_casts = true;
2047169689Skan
2048169689Skan      if (use_loop == wrto_loop)
2049169689Skan	return ev;
2050169689Skan
2051169689Skan      /* If the value of the use changes in the inner loop, we cannot express
2052169689Skan	 its value in the outer loop (we might try to return interval chrec,
2053169689Skan	 but we do not have a user for it anyway)  */
2054169689Skan      if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2055169689Skan	  || !val)
2056169689Skan	return chrec_dont_know;
2057169689Skan
2058169689Skan      use_loop = use_loop->outer;
2059169689Skan    }
2060169689Skan}
2061169689Skan
2062169689Skan/* Returns instantiated value for VERSION in CACHE.  */
2063169689Skan
2064169689Skanstatic tree
2065169689Skanget_instantiated_value (htab_t cache, tree version)
2066169689Skan{
2067169689Skan  struct scev_info_str *info, pattern;
2068169689Skan
2069169689Skan  pattern.var = version;
2070169689Skan  info = (struct scev_info_str *) htab_find (cache, &pattern);
2071169689Skan
2072169689Skan  if (info)
2073169689Skan    return info->chrec;
2074169689Skan  else
2075169689Skan    return NULL_TREE;
2076169689Skan}
2077169689Skan
2078169689Skan/* Sets instantiated value for VERSION to VAL in CACHE.  */
2079169689Skan
2080169689Skanstatic void
2081169689Skanset_instantiated_value (htab_t cache, tree version, tree val)
2082169689Skan{
2083169689Skan  struct scev_info_str *info, pattern;
2084169689Skan  PTR *slot;
2085169689Skan
2086169689Skan  pattern.var = version;
2087169689Skan  slot = htab_find_slot (cache, &pattern, INSERT);
2088169689Skan
2089169689Skan  if (!*slot)
2090169689Skan    *slot = new_scev_info_str (version);
2091169689Skan  info = (struct scev_info_str *) *slot;
2092169689Skan  info->chrec = val;
2093169689Skan}
2094169689Skan
2095169689Skan/* Return the closed_loop_phi node for VAR.  If there is none, return
2096169689Skan   NULL_TREE.  */
2097169689Skan
2098169689Skanstatic tree
2099169689Skanloop_closed_phi_def (tree var)
2100169689Skan{
2101169689Skan  struct loop *loop;
2102169689Skan  edge exit;
2103169689Skan  tree phi;
2104169689Skan
2105169689Skan  if (var == NULL_TREE
2106169689Skan      || TREE_CODE (var) != SSA_NAME)
2107169689Skan    return NULL_TREE;
2108169689Skan
2109169689Skan  loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2110169689Skan  exit = loop->single_exit;
2111169689Skan  if (!exit)
2112169689Skan    return NULL_TREE;
2113169689Skan
2114169689Skan  for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
2115169689Skan    if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2116169689Skan      return PHI_RESULT (phi);
2117169689Skan
2118169689Skan  return NULL_TREE;
2119169689Skan}
2120169689Skan
2121169689Skan/* Analyze all the parameters of the chrec that were left under a symbolic form,
2122169689Skan   with respect to LOOP.  CHREC is the chrec to instantiate.  CACHE is the cache
2123169689Skan   of already instantiated values.  FLAGS modify the way chrecs are
2124169689Skan   instantiated.  SIZE_EXPR is used for computing the size of the expression to
2125169689Skan   be instantiated, and to stop if it exceeds some limit.  */
2126169689Skan
2127169689Skan/* Values for FLAGS.  */
2128169689Skanenum
2129169689Skan{
2130169689Skan  INSERT_SUPERLOOP_CHRECS = 1,  /* Loop invariants are replaced with chrecs
2131169689Skan				   in outer loops.  */
2132169689Skan  FOLD_CONVERSIONS = 2		/* The conversions that may wrap in
2133169689Skan				   signed/pointer type are folded, as long as the
2134169689Skan				   value of the chrec is preserved.  */
2135169689Skan};
2136169689Skan
2137169689Skanstatic tree
2138169689Skaninstantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
2139169689Skan			  int size_expr)
2140169689Skan{
2141169689Skan  tree res, op0, op1, op2;
2142169689Skan  basic_block def_bb;
2143169689Skan  struct loop *def_loop;
2144169689Skan  tree type = chrec_type (chrec);
2145169689Skan
2146169689Skan  /* Give up if the expression is larger than the MAX that we allow.  */
2147169689Skan  if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2148169689Skan    return chrec_dont_know;
2149169689Skan
2150169689Skan  if (automatically_generated_chrec_p (chrec)
2151169689Skan      || is_gimple_min_invariant (chrec))
2152169689Skan    return chrec;
2153169689Skan
2154169689Skan  switch (TREE_CODE (chrec))
2155169689Skan    {
2156169689Skan    case SSA_NAME:
2157169689Skan      def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
2158169689Skan
2159169689Skan      /* A parameter (or loop invariant and we do not want to include
2160169689Skan	 evolutions in outer loops), nothing to do.  */
2161169689Skan      if (!def_bb
2162169689Skan	  || (!(flags & INSERT_SUPERLOOP_CHRECS)
2163169689Skan	      && !flow_bb_inside_loop_p (loop, def_bb)))
2164169689Skan	return chrec;
2165169689Skan
2166169689Skan      /* We cache the value of instantiated variable to avoid exponential
2167169689Skan	 time complexity due to reevaluations.  We also store the convenient
2168169689Skan	 value in the cache in order to prevent infinite recursion -- we do
2169169689Skan	 not want to instantiate the SSA_NAME if it is in a mixer
2170169689Skan	 structure.  This is used for avoiding the instantiation of
2171169689Skan	 recursively defined functions, such as:
2172169689Skan
2173169689Skan	 | a_2 -> {0, +, 1, +, a_2}_1  */
2174169689Skan
2175169689Skan      res = get_instantiated_value (cache, chrec);
2176169689Skan      if (res)
2177169689Skan	return res;
2178169689Skan
2179169689Skan      /* Store the convenient value for chrec in the structure.  If it
2180169689Skan	 is defined outside of the loop, we may just leave it in symbolic
2181169689Skan	 form, otherwise we need to admit that we do not know its behavior
2182169689Skan	 inside the loop.  */
2183169689Skan      res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
2184169689Skan      set_instantiated_value (cache, chrec, res);
2185169689Skan
2186169689Skan      /* To make things even more complicated, instantiate_parameters_1
2187169689Skan	 calls analyze_scalar_evolution that may call # of iterations
2188169689Skan	 analysis that may in turn call instantiate_parameters_1 again.
2189169689Skan	 To prevent the infinite recursion, keep also the bitmap of
2190169689Skan	 ssa names that are being instantiated globally.  */
2191169689Skan      if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
2192169689Skan	return res;
2193169689Skan
2194169689Skan      def_loop = find_common_loop (loop, def_bb->loop_father);
2195169689Skan
2196169689Skan      /* If the analysis yields a parametric chrec, instantiate the
2197169689Skan	 result again.  */
2198169689Skan      bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2199169689Skan      res = analyze_scalar_evolution (def_loop, chrec);
2200169689Skan
2201169689Skan      /* Don't instantiate loop-closed-ssa phi nodes.  */
2202169689Skan      if (TREE_CODE (res) == SSA_NAME
2203169689Skan	  && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
2204169689Skan	      || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth
2205169689Skan		  > def_loop->depth)))
2206169689Skan	{
2207169689Skan	  if (res == chrec)
2208169689Skan	    res = loop_closed_phi_def (chrec);
2209169689Skan	  else
2210169689Skan	    res = chrec;
2211169689Skan
2212169689Skan	  if (res == NULL_TREE)
2213169689Skan	    res = chrec_dont_know;
2214169689Skan	}
2215169689Skan
2216169689Skan      else if (res != chrec_dont_know)
2217169689Skan	res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2218169689Skan
2219169689Skan      bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
2220169689Skan
2221169689Skan      /* Store the correct value to the cache.  */
2222169689Skan      set_instantiated_value (cache, chrec, res);
2223169689Skan      return res;
2224169689Skan
2225169689Skan    case POLYNOMIAL_CHREC:
2226169689Skan      op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2227169689Skan				      flags, cache, size_expr);
2228169689Skan      if (op0 == chrec_dont_know)
2229169689Skan	return chrec_dont_know;
2230169689Skan
2231169689Skan      op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2232169689Skan				      flags, cache, size_expr);
2233169689Skan      if (op1 == chrec_dont_know)
2234169689Skan	return chrec_dont_know;
2235169689Skan
2236169689Skan      if (CHREC_LEFT (chrec) != op0
2237169689Skan	  || CHREC_RIGHT (chrec) != op1)
2238169689Skan	{
2239169689Skan	  op1 = chrec_convert (chrec_type (op0), op1, NULL_TREE);
2240169689Skan	  chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2241169689Skan	}
2242169689Skan      return chrec;
2243169689Skan
2244169689Skan    case PLUS_EXPR:
2245169689Skan      op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2246169689Skan				      flags, cache, size_expr);
2247169689Skan      if (op0 == chrec_dont_know)
2248169689Skan	return chrec_dont_know;
2249169689Skan
2250169689Skan      op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2251169689Skan				      flags, cache, size_expr);
2252169689Skan      if (op1 == chrec_dont_know)
2253169689Skan	return chrec_dont_know;
2254169689Skan
2255169689Skan      if (TREE_OPERAND (chrec, 0) != op0
2256169689Skan	  || TREE_OPERAND (chrec, 1) != op1)
2257169689Skan	{
2258169689Skan	  op0 = chrec_convert (type, op0, NULL_TREE);
2259169689Skan	  op1 = chrec_convert (type, op1, NULL_TREE);
2260169689Skan	  chrec = chrec_fold_plus (type, op0, op1);
2261169689Skan	}
2262169689Skan      return chrec;
2263169689Skan
2264169689Skan    case MINUS_EXPR:
2265169689Skan      op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2266169689Skan				      flags, cache, size_expr);
2267169689Skan      if (op0 == chrec_dont_know)
2268169689Skan	return chrec_dont_know;
2269169689Skan
2270169689Skan      op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2271169689Skan				      flags, cache, size_expr);
2272169689Skan      if (op1 == chrec_dont_know)
2273169689Skan	return chrec_dont_know;
2274169689Skan
2275169689Skan      if (TREE_OPERAND (chrec, 0) != op0
2276169689Skan	  || TREE_OPERAND (chrec, 1) != op1)
2277169689Skan	{
2278169689Skan	  op0 = chrec_convert (type, op0, NULL_TREE);
2279169689Skan	  op1 = chrec_convert (type, op1, NULL_TREE);
2280169689Skan	  chrec = chrec_fold_minus (type, op0, op1);
2281169689Skan	}
2282169689Skan      return chrec;
2283169689Skan
2284169689Skan    case MULT_EXPR:
2285169689Skan      op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2286169689Skan				      flags, cache, size_expr);
2287169689Skan      if (op0 == chrec_dont_know)
2288169689Skan	return chrec_dont_know;
2289169689Skan
2290169689Skan      op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2291169689Skan				      flags, cache, size_expr);
2292169689Skan      if (op1 == chrec_dont_know)
2293169689Skan	return chrec_dont_know;
2294169689Skan
2295169689Skan      if (TREE_OPERAND (chrec, 0) != op0
2296169689Skan	  || TREE_OPERAND (chrec, 1) != op1)
2297169689Skan	{
2298169689Skan	  op0 = chrec_convert (type, op0, NULL_TREE);
2299169689Skan	  op1 = chrec_convert (type, op1, NULL_TREE);
2300169689Skan	  chrec = chrec_fold_multiply (type, op0, op1);
2301169689Skan	}
2302169689Skan      return chrec;
2303169689Skan
2304169689Skan    case NOP_EXPR:
2305169689Skan    case CONVERT_EXPR:
2306169689Skan    case NON_LVALUE_EXPR:
2307169689Skan      op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2308169689Skan				      flags, cache, size_expr);
2309169689Skan      if (op0 == chrec_dont_know)
2310169689Skan        return chrec_dont_know;
2311169689Skan
2312169689Skan      if (flags & FOLD_CONVERSIONS)
2313169689Skan	{
2314169689Skan	  tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
2315169689Skan	  if (tmp)
2316169689Skan	    return tmp;
2317169689Skan	}
2318169689Skan
2319169689Skan      if (op0 == TREE_OPERAND (chrec, 0))
2320169689Skan	return chrec;
2321169689Skan
2322169689Skan      /* If we used chrec_convert_aggressive, we can no longer assume that
2323169689Skan	 signed chrecs do not overflow, as chrec_convert does, so avoid
2324169689Skan         calling it in that case.  */
2325169689Skan      if (flags & FOLD_CONVERSIONS)
2326169689Skan	return fold_convert (TREE_TYPE (chrec), op0);
2327169689Skan
2328169689Skan      return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
2329169689Skan
2330169689Skan    case SCEV_NOT_KNOWN:
2331169689Skan      return chrec_dont_know;
2332169689Skan
2333169689Skan    case SCEV_KNOWN:
2334169689Skan      return chrec_known;
2335169689Skan
2336169689Skan    default:
2337169689Skan      break;
2338169689Skan    }
2339169689Skan
2340169689Skan  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
2341169689Skan    {
2342169689Skan    case 3:
2343169689Skan      op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2344169689Skan				      flags, cache, size_expr);
2345169689Skan      if (op0 == chrec_dont_know)
2346169689Skan	return chrec_dont_know;
2347169689Skan
2348169689Skan      op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2349169689Skan				      flags, cache, size_expr);
2350169689Skan      if (op1 == chrec_dont_know)
2351169689Skan	return chrec_dont_know;
2352169689Skan
2353169689Skan      op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2354169689Skan				      flags, cache, size_expr);
2355169689Skan      if (op2 == chrec_dont_know)
2356169689Skan        return chrec_dont_know;
2357169689Skan
2358169689Skan      if (op0 == TREE_OPERAND (chrec, 0)
2359169689Skan	  && op1 == TREE_OPERAND (chrec, 1)
2360169689Skan	  && op2 == TREE_OPERAND (chrec, 2))
2361169689Skan	return chrec;
2362169689Skan
2363169689Skan      return fold_build3 (TREE_CODE (chrec),
2364169689Skan			  TREE_TYPE (chrec), op0, op1, op2);
2365169689Skan
2366169689Skan    case 2:
2367169689Skan      op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2368169689Skan				      flags, cache, size_expr);
2369169689Skan      if (op0 == chrec_dont_know)
2370169689Skan	return chrec_dont_know;
2371169689Skan
2372169689Skan      op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2373169689Skan				      flags, cache, size_expr);
2374169689Skan      if (op1 == chrec_dont_know)
2375169689Skan        return chrec_dont_know;
2376169689Skan
2377169689Skan      if (op0 == TREE_OPERAND (chrec, 0)
2378169689Skan	  && op1 == TREE_OPERAND (chrec, 1))
2379169689Skan	return chrec;
2380169689Skan      return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
2381169689Skan
2382169689Skan    case 1:
2383169689Skan      op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2384169689Skan				      flags, cache, size_expr);
2385169689Skan      if (op0 == chrec_dont_know)
2386169689Skan        return chrec_dont_know;
2387169689Skan      if (op0 == TREE_OPERAND (chrec, 0))
2388169689Skan	return chrec;
2389169689Skan      return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
2390169689Skan
2391169689Skan    case 0:
2392169689Skan      return chrec;
2393169689Skan
2394169689Skan    default:
2395169689Skan      break;
2396169689Skan    }
2397169689Skan
2398169689Skan  /* Too complicated to handle.  */
2399169689Skan  return chrec_dont_know;
2400169689Skan}
2401169689Skan
2402169689Skan/* Analyze all the parameters of the chrec that were left under a
2403169689Skan   symbolic form.  LOOP is the loop in which symbolic names have to
2404169689Skan   be analyzed and instantiated.  */
2405169689Skan
2406169689Skantree
2407169689Skaninstantiate_parameters (struct loop *loop,
2408169689Skan			tree chrec)
2409169689Skan{
2410169689Skan  tree res;
2411169689Skan  htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2412169689Skan
2413169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
2414169689Skan    {
2415169689Skan      fprintf (dump_file, "(instantiate_parameters \n");
2416169689Skan      fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2417169689Skan      fprintf (dump_file, "  (chrec = ");
2418169689Skan      print_generic_expr (dump_file, chrec, 0);
2419169689Skan      fprintf (dump_file, ")\n");
2420169689Skan    }
2421169689Skan
2422169689Skan  res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2423169689Skan				  0);
2424169689Skan
2425169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
2426169689Skan    {
2427169689Skan      fprintf (dump_file, "  (res = ");
2428169689Skan      print_generic_expr (dump_file, res, 0);
2429169689Skan      fprintf (dump_file, "))\n");
2430169689Skan    }
2431169689Skan
2432169689Skan  htab_delete (cache);
2433169689Skan
2434169689Skan  return res;
2435169689Skan}
2436169689Skan
2437169689Skan/* Similar to instantiate_parameters, but does not introduce the
2438169689Skan   evolutions in outer loops for LOOP invariants in CHREC, and does not
2439169689Skan   care about causing overflows, as long as they do not affect value
2440169689Skan   of an expression.  */
2441169689Skan
2442169689Skanstatic tree
2443169689Skanresolve_mixers (struct loop *loop, tree chrec)
2444169689Skan{
2445169689Skan  htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
2446169689Skan  tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2447169689Skan  htab_delete (cache);
2448169689Skan  return ret;
2449169689Skan}
2450169689Skan
2451169689Skan/* Entry point for the analysis of the number of iterations pass.
2452169689Skan   This function tries to safely approximate the number of iterations
2453169689Skan   the loop will run.  When this property is not decidable at compile
2454169689Skan   time, the result is chrec_dont_know.  Otherwise the result is
2455169689Skan   a scalar or a symbolic parameter.
2456169689Skan
2457169689Skan   Example of analysis: suppose that the loop has an exit condition:
2458169689Skan
2459169689Skan   "if (b > 49) goto end_loop;"
2460169689Skan
2461169689Skan   and that in a previous analysis we have determined that the
2462169689Skan   variable 'b' has an evolution function:
2463169689Skan
2464169689Skan   "EF = {23, +, 5}_2".
2465169689Skan
2466169689Skan   When we evaluate the function at the point 5, i.e. the value of the
2467169689Skan   variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2468169689Skan   and EF (6) = 53.  In this case the value of 'b' on exit is '53' and
2469169689Skan   the loop body has been executed 6 times.  */
2470169689Skan
2471169689Skantree
2472169689Skannumber_of_iterations_in_loop (struct loop *loop)
2473169689Skan{
2474169689Skan  tree res, type;
2475169689Skan  edge exit;
2476169689Skan  struct tree_niter_desc niter_desc;
2477169689Skan
2478169689Skan  /* Determine whether the number_of_iterations_in_loop has already
2479169689Skan     been computed.  */
2480169689Skan  res = loop->nb_iterations;
2481169689Skan  if (res)
2482169689Skan    return res;
2483169689Skan  res = chrec_dont_know;
2484169689Skan
2485169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
2486169689Skan    fprintf (dump_file, "(number_of_iterations_in_loop\n");
2487169689Skan
2488169689Skan  exit = loop->single_exit;
2489169689Skan  if (!exit)
2490169689Skan    goto end;
2491169689Skan
2492169689Skan  if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2493169689Skan    goto end;
2494169689Skan
2495169689Skan  type = TREE_TYPE (niter_desc.niter);
2496169689Skan  if (integer_nonzerop (niter_desc.may_be_zero))
2497169689Skan    res = build_int_cst (type, 0);
2498169689Skan  else if (integer_zerop (niter_desc.may_be_zero))
2499169689Skan    res = niter_desc.niter;
2500169689Skan  else
2501169689Skan    res = chrec_dont_know;
2502169689Skan
2503169689Skanend:
2504169689Skan  return set_nb_iterations_in_loop (loop, res);
2505169689Skan}
2506169689Skan
2507169689Skan/* One of the drivers for testing the scalar evolutions analysis.
2508169689Skan   This function computes the number of iterations for all the loops
2509169689Skan   from the EXIT_CONDITIONS array.  */
2510169689Skan
2511169689Skanstatic void
2512169689Skannumber_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
2513169689Skan{
2514169689Skan  unsigned int i;
2515169689Skan  unsigned nb_chrec_dont_know_loops = 0;
2516169689Skan  unsigned nb_static_loops = 0;
2517169689Skan  tree cond;
2518169689Skan
2519169689Skan  for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2520169689Skan    {
2521169689Skan      tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
2522169689Skan      if (chrec_contains_undetermined (res))
2523169689Skan	nb_chrec_dont_know_loops++;
2524169689Skan      else
2525169689Skan	nb_static_loops++;
2526169689Skan    }
2527169689Skan
2528169689Skan  if (dump_file)
2529169689Skan    {
2530169689Skan      fprintf (dump_file, "\n(\n");
2531169689Skan      fprintf (dump_file, "-----------------------------------------\n");
2532169689Skan      fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
2533169689Skan      fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
2534169689Skan      fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
2535169689Skan      fprintf (dump_file, "-----------------------------------------\n");
2536169689Skan      fprintf (dump_file, ")\n\n");
2537169689Skan
2538169689Skan      print_loop_ir (dump_file);
2539169689Skan    }
2540169689Skan}
2541169689Skan
2542169689Skan
2543169689Skan
2544169689Skan/* Counters for the stats.  */
2545169689Skan
2546169689Skanstruct chrec_stats
2547169689Skan{
2548169689Skan  unsigned nb_chrecs;
2549169689Skan  unsigned nb_affine;
2550169689Skan  unsigned nb_affine_multivar;
2551169689Skan  unsigned nb_higher_poly;
2552169689Skan  unsigned nb_chrec_dont_know;
2553169689Skan  unsigned nb_undetermined;
2554169689Skan};
2555169689Skan
2556169689Skan/* Reset the counters.  */
2557169689Skan
2558169689Skanstatic inline void
2559169689Skanreset_chrecs_counters (struct chrec_stats *stats)
2560169689Skan{
2561169689Skan  stats->nb_chrecs = 0;
2562169689Skan  stats->nb_affine = 0;
2563169689Skan  stats->nb_affine_multivar = 0;
2564169689Skan  stats->nb_higher_poly = 0;
2565169689Skan  stats->nb_chrec_dont_know = 0;
2566169689Skan  stats->nb_undetermined = 0;
2567169689Skan}
2568169689Skan
2569169689Skan/* Dump the contents of a CHREC_STATS structure.  */
2570169689Skan
2571169689Skanstatic void
2572169689Skandump_chrecs_stats (FILE *file, struct chrec_stats *stats)
2573169689Skan{
2574169689Skan  fprintf (file, "\n(\n");
2575169689Skan  fprintf (file, "-----------------------------------------\n");
2576169689Skan  fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2577169689Skan  fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2578169689Skan  fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2579169689Skan	   stats->nb_higher_poly);
2580169689Skan  fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2581169689Skan  fprintf (file, "-----------------------------------------\n");
2582169689Skan  fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2583169689Skan  fprintf (file, "%d\twith undetermined coefficients\n",
2584169689Skan	   stats->nb_undetermined);
2585169689Skan  fprintf (file, "-----------------------------------------\n");
2586169689Skan  fprintf (file, "%d\tchrecs in the scev database\n",
2587169689Skan	   (int) htab_elements (scalar_evolution_info));
2588169689Skan  fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2589169689Skan  fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2590169689Skan  fprintf (file, "-----------------------------------------\n");
2591169689Skan  fprintf (file, ")\n\n");
2592169689Skan}
2593169689Skan
2594169689Skan/* Gather statistics about CHREC.  */
2595169689Skan
2596169689Skanstatic void
2597169689Skangather_chrec_stats (tree chrec, struct chrec_stats *stats)
2598169689Skan{
2599169689Skan  if (dump_file && (dump_flags & TDF_STATS))
2600169689Skan    {
2601169689Skan      fprintf (dump_file, "(classify_chrec ");
2602169689Skan      print_generic_expr (dump_file, chrec, 0);
2603169689Skan      fprintf (dump_file, "\n");
2604169689Skan    }
2605169689Skan
2606169689Skan  stats->nb_chrecs++;
2607169689Skan
2608169689Skan  if (chrec == NULL_TREE)
2609169689Skan    {
2610169689Skan      stats->nb_undetermined++;
2611169689Skan      return;
2612169689Skan    }
2613169689Skan
2614169689Skan  switch (TREE_CODE (chrec))
2615169689Skan    {
2616169689Skan    case POLYNOMIAL_CHREC:
2617169689Skan      if (evolution_function_is_affine_p (chrec))
2618169689Skan	{
2619169689Skan	  if (dump_file && (dump_flags & TDF_STATS))
2620169689Skan	    fprintf (dump_file, "  affine_univariate\n");
2621169689Skan	  stats->nb_affine++;
2622169689Skan	}
2623169689Skan      else if (evolution_function_is_affine_multivariate_p (chrec))
2624169689Skan	{
2625169689Skan	  if (dump_file && (dump_flags & TDF_STATS))
2626169689Skan	    fprintf (dump_file, "  affine_multivariate\n");
2627169689Skan	  stats->nb_affine_multivar++;
2628169689Skan	}
2629169689Skan      else
2630169689Skan	{
2631169689Skan	  if (dump_file && (dump_flags & TDF_STATS))
2632169689Skan	    fprintf (dump_file, "  higher_degree_polynomial\n");
2633169689Skan	  stats->nb_higher_poly++;
2634169689Skan	}
2635169689Skan
2636169689Skan      break;
2637169689Skan
2638169689Skan    default:
2639169689Skan      break;
2640169689Skan    }
2641169689Skan
2642169689Skan  if (chrec_contains_undetermined (chrec))
2643169689Skan    {
2644169689Skan      if (dump_file && (dump_flags & TDF_STATS))
2645169689Skan	fprintf (dump_file, "  undetermined\n");
2646169689Skan      stats->nb_undetermined++;
2647169689Skan    }
2648169689Skan
2649169689Skan  if (dump_file && (dump_flags & TDF_STATS))
2650169689Skan    fprintf (dump_file, ")\n");
2651169689Skan}
2652169689Skan
2653169689Skan/* One of the drivers for testing the scalar evolutions analysis.
2654169689Skan   This function analyzes the scalar evolution of all the scalars
2655169689Skan   defined as loop phi nodes in one of the loops from the
2656169689Skan   EXIT_CONDITIONS array.
2657169689Skan
2658169689Skan   TODO Optimization: A loop is in canonical form if it contains only
2659169689Skan   a single scalar loop phi node.  All the other scalars that have an
2660169689Skan   evolution in the loop are rewritten in function of this single
2661169689Skan   index.  This allows the parallelization of the loop.  */
2662169689Skan
2663169689Skanstatic void
2664169689Skananalyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
2665169689Skan{
2666169689Skan  unsigned int i;
2667169689Skan  struct chrec_stats stats;
2668169689Skan  tree cond;
2669169689Skan
2670169689Skan  reset_chrecs_counters (&stats);
2671169689Skan
2672169689Skan  for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
2673169689Skan    {
2674169689Skan      struct loop *loop;
2675169689Skan      basic_block bb;
2676169689Skan      tree phi, chrec;
2677169689Skan
2678169689Skan      loop = loop_containing_stmt (cond);
2679169689Skan      bb = loop->header;
2680169689Skan
2681169689Skan      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2682169689Skan	if (is_gimple_reg (PHI_RESULT (phi)))
2683169689Skan	  {
2684169689Skan	    chrec = instantiate_parameters
2685169689Skan	      (loop,
2686169689Skan	       analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2687169689Skan
2688169689Skan	    if (dump_file && (dump_flags & TDF_STATS))
2689169689Skan	      gather_chrec_stats (chrec, &stats);
2690169689Skan	  }
2691169689Skan    }
2692169689Skan
2693169689Skan  if (dump_file && (dump_flags & TDF_STATS))
2694169689Skan    dump_chrecs_stats (dump_file, &stats);
2695169689Skan}
2696169689Skan
2697169689Skan/* Callback for htab_traverse, gathers information on chrecs in the
2698169689Skan   hashtable.  */
2699169689Skan
2700169689Skanstatic int
2701169689Skangather_stats_on_scev_database_1 (void **slot, void *stats)
2702169689Skan{
2703169689Skan  struct scev_info_str *entry = (struct scev_info_str *) *slot;
2704169689Skan
2705169689Skan  gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
2706169689Skan
2707169689Skan  return 1;
2708169689Skan}
2709169689Skan
2710169689Skan/* Classify the chrecs of the whole database.  */
2711169689Skan
2712169689Skanvoid
2713169689Skangather_stats_on_scev_database (void)
2714169689Skan{
2715169689Skan  struct chrec_stats stats;
2716169689Skan
2717169689Skan  if (!dump_file)
2718169689Skan    return;
2719169689Skan
2720169689Skan  reset_chrecs_counters (&stats);
2721169689Skan
2722169689Skan  htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
2723169689Skan		 &stats);
2724169689Skan
2725169689Skan  dump_chrecs_stats (dump_file, &stats);
2726169689Skan}
2727169689Skan
2728169689Skan
2729169689Skan
2730169689Skan/* Initializer.  */
2731169689Skan
2732169689Skanstatic void
2733169689Skaninitialize_scalar_evolutions_analyzer (void)
2734169689Skan{
2735169689Skan  /* The elements below are unique.  */
2736169689Skan  if (chrec_dont_know == NULL_TREE)
2737169689Skan    {
2738169689Skan      chrec_not_analyzed_yet = NULL_TREE;
2739169689Skan      chrec_dont_know = make_node (SCEV_NOT_KNOWN);
2740169689Skan      chrec_known = make_node (SCEV_KNOWN);
2741169689Skan      TREE_TYPE (chrec_dont_know) = void_type_node;
2742169689Skan      TREE_TYPE (chrec_known) = void_type_node;
2743169689Skan    }
2744169689Skan}
2745169689Skan
2746169689Skan/* Initialize the analysis of scalar evolutions for LOOPS.  */
2747169689Skan
2748169689Skanvoid
2749169689Skanscev_initialize (struct loops *loops)
2750169689Skan{
2751169689Skan  unsigned i;
2752169689Skan  current_loops = loops;
2753169689Skan
2754169689Skan  scalar_evolution_info = htab_create (100, hash_scev_info,
2755169689Skan				       eq_scev_info, del_scev_info);
2756169689Skan  already_instantiated = BITMAP_ALLOC (NULL);
2757169689Skan
2758169689Skan  initialize_scalar_evolutions_analyzer ();
2759169689Skan
2760169689Skan  for (i = 1; i < loops->num; i++)
2761169689Skan    if (loops->parray[i])
2762169689Skan      loops->parray[i]->nb_iterations = NULL_TREE;
2763169689Skan}
2764169689Skan
2765169689Skan/* Cleans up the information cached by the scalar evolutions analysis.  */
2766169689Skan
2767169689Skanvoid
2768169689Skanscev_reset (void)
2769169689Skan{
2770169689Skan  unsigned i;
2771169689Skan  struct loop *loop;
2772169689Skan
2773169689Skan  if (!scalar_evolution_info || !current_loops)
2774169689Skan    return;
2775169689Skan
2776169689Skan  htab_empty (scalar_evolution_info);
2777169689Skan  for (i = 1; i < current_loops->num; i++)
2778169689Skan    {
2779169689Skan      loop = current_loops->parray[i];
2780169689Skan      if (loop)
2781169689Skan	loop->nb_iterations = NULL_TREE;
2782169689Skan    }
2783169689Skan}
2784169689Skan
2785169689Skan/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
2786169689Skan   its base and step in IV if possible.  If ALLOW_NONCONSTANT_STEP is true, we
2787169689Skan   want step to be invariant in LOOP.  Otherwise we require it to be an
2788169689Skan   integer constant.  IV->no_overflow is set to true if we are sure the iv cannot
2789169689Skan   overflow (e.g.  because it is computed in signed arithmetics).  */
2790169689Skan
2791169689Skanbool
2792169689Skansimple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2793169689Skan	   bool allow_nonconstant_step)
2794169689Skan{
2795169689Skan  basic_block bb = bb_for_stmt (stmt);
2796169689Skan  tree type, ev;
2797169689Skan  bool folded_casts;
2798169689Skan
2799169689Skan  iv->base = NULL_TREE;
2800169689Skan  iv->step = NULL_TREE;
2801169689Skan  iv->no_overflow = false;
2802169689Skan
2803169689Skan  type = TREE_TYPE (op);
2804169689Skan  if (TREE_CODE (type) != INTEGER_TYPE
2805169689Skan      && TREE_CODE (type) != POINTER_TYPE)
2806169689Skan    return false;
2807169689Skan
2808169689Skan  ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2809169689Skan					 &folded_casts);
2810169689Skan  if (chrec_contains_undetermined (ev))
2811169689Skan    return false;
2812169689Skan
2813169689Skan  if (tree_does_not_contain_chrecs (ev)
2814169689Skan      && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2815169689Skan    {
2816169689Skan      iv->base = ev;
2817169689Skan      iv->no_overflow = true;
2818169689Skan      return true;
2819169689Skan    }
2820169689Skan
2821169689Skan  if (TREE_CODE (ev) != POLYNOMIAL_CHREC
2822169689Skan      || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2823169689Skan    return false;
2824169689Skan
2825169689Skan  iv->step = CHREC_RIGHT (ev);
2826169689Skan  if (allow_nonconstant_step)
2827169689Skan    {
2828169689Skan      if (tree_contains_chrecs (iv->step, NULL)
2829169689Skan	  || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2830169689Skan	return false;
2831169689Skan    }
2832169689Skan  else if (TREE_CODE (iv->step) != INTEGER_CST)
2833169689Skan    return false;
2834169689Skan
2835169689Skan  iv->base = CHREC_LEFT (ev);
2836169689Skan  if (tree_contains_chrecs (iv->base, NULL)
2837169689Skan      || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2838169689Skan    return false;
2839169689Skan
2840169689Skan  iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
2841169689Skan
2842169689Skan  return true;
2843169689Skan}
2844169689Skan
2845169689Skan/* Runs the analysis of scalar evolutions.  */
2846169689Skan
2847169689Skanvoid
2848169689Skanscev_analysis (void)
2849169689Skan{
2850169689Skan  VEC(tree,heap) *exit_conditions;
2851169689Skan
2852169689Skan  exit_conditions = VEC_alloc (tree, heap, 37);
2853169689Skan  select_loops_exit_conditions (current_loops, &exit_conditions);
2854169689Skan
2855169689Skan  if (dump_file && (dump_flags & TDF_STATS))
2856169689Skan    analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
2857169689Skan
2858169689Skan  number_of_iterations_for_all_loops (&exit_conditions);
2859169689Skan  VEC_free (tree, heap, exit_conditions);
2860169689Skan}
2861169689Skan
2862169689Skan/* Finalize the scalar evolution analysis.  */
2863169689Skan
2864169689Skanvoid
2865169689Skanscev_finalize (void)
2866169689Skan{
2867169689Skan  htab_delete (scalar_evolution_info);
2868169689Skan  BITMAP_FREE (already_instantiated);
2869169689Skan}
2870169689Skan
2871169689Skan/* Returns true if EXPR looks expensive.  */
2872169689Skan
2873169689Skanstatic bool
2874169689Skanexpression_expensive_p (tree expr)
2875169689Skan{
2876169689Skan  return force_expr_to_var_cost (expr) >= target_spill_cost;
2877169689Skan}
2878169689Skan
2879169689Skan/* Replace ssa names for that scev can prove they are constant by the
2880169689Skan   appropriate constants.  Also perform final value replacement in loops,
2881169689Skan   in case the replacement expressions are cheap.
2882169689Skan
2883169689Skan   We only consider SSA names defined by phi nodes; rest is left to the
2884169689Skan   ordinary constant propagation pass.  */
2885169689Skan
2886169689Skanunsigned int
2887169689Skanscev_const_prop (void)
2888169689Skan{
2889169689Skan  basic_block bb;
2890169689Skan  tree name, phi, next_phi, type, ev;
2891169689Skan  struct loop *loop, *ex_loop;
2892169689Skan  bitmap ssa_names_to_remove = NULL;
2893169689Skan  unsigned i;
2894169689Skan
2895169689Skan  if (!current_loops)
2896169689Skan    return 0;
2897169689Skan
2898169689Skan  FOR_EACH_BB (bb)
2899169689Skan    {
2900169689Skan      loop = bb->loop_father;
2901169689Skan
2902169689Skan      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2903169689Skan	{
2904169689Skan	  name = PHI_RESULT (phi);
2905169689Skan
2906169689Skan	  if (!is_gimple_reg (name))
2907169689Skan	    continue;
2908169689Skan
2909169689Skan	  type = TREE_TYPE (name);
2910169689Skan
2911169689Skan	  if (!POINTER_TYPE_P (type)
2912169689Skan	      && !INTEGRAL_TYPE_P (type))
2913169689Skan	    continue;
2914169689Skan
2915169689Skan	  ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2916169689Skan	  if (!is_gimple_min_invariant (ev)
2917169689Skan	      || !may_propagate_copy (name, ev))
2918169689Skan	    continue;
2919169689Skan
2920169689Skan	  /* Replace the uses of the name.  */
2921169689Skan	  if (name != ev)
2922169689Skan	    replace_uses_by (name, ev);
2923169689Skan
2924169689Skan	  if (!ssa_names_to_remove)
2925169689Skan	    ssa_names_to_remove = BITMAP_ALLOC (NULL);
2926169689Skan	  bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
2927169689Skan	}
2928169689Skan    }
2929169689Skan
2930169689Skan  /* Remove the ssa names that were replaced by constants.  We do not remove them
2931169689Skan     directly in the previous cycle, since this invalidates scev cache.  */
2932169689Skan  if (ssa_names_to_remove)
2933169689Skan    {
2934169689Skan      bitmap_iterator bi;
2935169689Skan      unsigned i;
2936169689Skan
2937169689Skan      EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
2938169689Skan	{
2939169689Skan	  name = ssa_name (i);
2940169689Skan	  phi = SSA_NAME_DEF_STMT (name);
2941169689Skan
2942169689Skan	  gcc_assert (TREE_CODE (phi) == PHI_NODE);
2943169689Skan	  remove_phi_node (phi, NULL);
2944169689Skan	}
2945169689Skan
2946169689Skan      BITMAP_FREE (ssa_names_to_remove);
2947169689Skan      scev_reset ();
2948169689Skan    }
2949169689Skan
2950169689Skan  /* Now the regular final value replacement.  */
2951169689Skan  for (i = current_loops->num - 1; i > 0; i--)
2952169689Skan    {
2953169689Skan      edge exit;
2954169689Skan      tree def, rslt, ass, niter;
2955169689Skan      block_stmt_iterator bsi;
2956169689Skan
2957169689Skan      loop = current_loops->parray[i];
2958169689Skan      if (!loop)
2959169689Skan	continue;
2960169689Skan
2961169689Skan      /* If we do not know exact number of iterations of the loop, we cannot
2962169689Skan	 replace the final value.  */
2963169689Skan      exit = loop->single_exit;
2964169689Skan      if (!exit)
2965169689Skan	continue;
2966169689Skan
2967169689Skan      niter = number_of_iterations_in_loop (loop);
2968169689Skan      if (niter == chrec_dont_know
2969169689Skan	  /* If computing the number of iterations is expensive, it may be
2970169689Skan	     better not to introduce computations involving it.  */
2971169689Skan	  || expression_expensive_p (niter))
2972169689Skan	continue;
2973169689Skan
2974169689Skan      /* Ensure that it is possible to insert new statements somewhere.  */
2975169689Skan      if (!single_pred_p (exit->dest))
2976169689Skan	split_loop_exit_edge (exit);
2977169689Skan      tree_block_label (exit->dest);
2978169689Skan      bsi = bsi_after_labels (exit->dest);
2979169689Skan
2980169689Skan      ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1);
2981169689Skan
2982169689Skan      for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
2983169689Skan	{
2984169689Skan	  next_phi = PHI_CHAIN (phi);
2985169689Skan	  rslt = PHI_RESULT (phi);
2986169689Skan	  def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2987169689Skan	  if (!is_gimple_reg (def))
2988169689Skan	    continue;
2989169689Skan
2990169689Skan	  if (!POINTER_TYPE_P (TREE_TYPE (def))
2991169689Skan	      && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
2992169689Skan	    continue;
2993169689Skan
2994169689Skan	  def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
2995169689Skan	  def = compute_overall_effect_of_inner_loop (ex_loop, def);
2996169689Skan	  if (!tree_does_not_contain_chrecs (def)
2997169689Skan	      || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
2998169689Skan	      /* Moving the computation from the loop may prolong life range
2999169689Skan		 of some ssa names, which may cause problems if they appear
3000169689Skan		 on abnormal edges.  */
3001169689Skan	      || contains_abnormal_ssa_name_p (def))
3002169689Skan	    continue;
3003169689Skan
3004169689Skan	  /* Eliminate the phi node and replace it by a computation outside
3005169689Skan	     the loop.  */
3006169689Skan	  def = unshare_expr (def);
3007169689Skan	  SET_PHI_RESULT (phi, NULL_TREE);
3008169689Skan	  remove_phi_node (phi, NULL_TREE);
3009169689Skan
3010169689Skan	  ass = build2 (MODIFY_EXPR, void_type_node, rslt, NULL_TREE);
3011169689Skan	  SSA_NAME_DEF_STMT (rslt) = ass;
3012169689Skan	  {
3013169689Skan	    block_stmt_iterator dest = bsi;
3014169689Skan	    bsi_insert_before (&dest, ass, BSI_NEW_STMT);
3015169689Skan	    def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE);
3016169689Skan	  }
3017169689Skan	  TREE_OPERAND (ass, 1) = def;
3018169689Skan	  update_stmt (ass);
3019169689Skan	}
3020169689Skan    }
3021169689Skan  return 0;
3022169689Skan}
3023