1169689Skan/* Chains of recurrences.
2169689Skan   Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
3169689Skan   Contributed by Sebastian Pop <pop@cri.ensmp.fr>
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/* This file implements operations on chains of recurrences.  Chains
23169689Skan   of recurrences are used for modeling evolution functions of scalar
24169689Skan   variables.
25169689Skan*/
26169689Skan
27169689Skan#include "config.h"
28169689Skan#include "system.h"
29169689Skan#include "coretypes.h"
30169689Skan#include "tm.h"
31169689Skan#include "ggc.h"
32169689Skan#include "tree.h"
33169689Skan#include "real.h"
34169689Skan#include "diagnostic.h"
35169689Skan#include "cfgloop.h"
36169689Skan#include "tree-flow.h"
37169689Skan#include "tree-chrec.h"
38169689Skan#include "tree-pass.h"
39169689Skan#include "params.h"
40169689Skan#include "tree-scalar-evolution.h"
41169689Skan
42169689Skan
43169689Skan
44169689Skan/* Extended folder for chrecs.  */
45169689Skan
46169689Skan/* Determines whether CST is not a constant evolution.  */
47169689Skan
48169689Skanstatic inline bool
49169689Skanis_not_constant_evolution (tree cst)
50169689Skan{
51169689Skan  return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
52169689Skan}
53169689Skan
54169689Skan/* Fold CODE for a polynomial function and a constant.  */
55169689Skan
56169689Skanstatic inline tree
57169689Skanchrec_fold_poly_cst (enum tree_code code,
58169689Skan		     tree type,
59169689Skan		     tree poly,
60169689Skan		     tree cst)
61169689Skan{
62169689Skan  gcc_assert (poly);
63169689Skan  gcc_assert (cst);
64169689Skan  gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
65169689Skan  gcc_assert (!is_not_constant_evolution (cst));
66169689Skan  gcc_assert (type == chrec_type (poly));
67169689Skan
68169689Skan  switch (code)
69169689Skan    {
70169689Skan    case PLUS_EXPR:
71169689Skan      return build_polynomial_chrec
72169689Skan	(CHREC_VARIABLE (poly),
73169689Skan	 chrec_fold_plus (type, CHREC_LEFT (poly), cst),
74169689Skan	 CHREC_RIGHT (poly));
75169689Skan
76169689Skan    case MINUS_EXPR:
77169689Skan      return build_polynomial_chrec
78169689Skan	(CHREC_VARIABLE (poly),
79169689Skan	 chrec_fold_minus (type, CHREC_LEFT (poly), cst),
80169689Skan	 CHREC_RIGHT (poly));
81169689Skan
82169689Skan    case MULT_EXPR:
83169689Skan      return build_polynomial_chrec
84169689Skan	(CHREC_VARIABLE (poly),
85169689Skan	 chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
86169689Skan	 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
87169689Skan
88169689Skan    default:
89169689Skan      return chrec_dont_know;
90169689Skan    }
91169689Skan}
92169689Skan
93169689Skan/* Fold the addition of two polynomial functions.  */
94169689Skan
95169689Skanstatic inline tree
96169689Skanchrec_fold_plus_poly_poly (enum tree_code code,
97169689Skan			   tree type,
98169689Skan			   tree poly0,
99169689Skan			   tree poly1)
100169689Skan{
101169689Skan  tree left, right;
102169689Skan
103169689Skan  gcc_assert (poly0);
104169689Skan  gcc_assert (poly1);
105169689Skan  gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
106169689Skan  gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
107169689Skan  gcc_assert (chrec_type (poly0) == chrec_type (poly1));
108169689Skan  gcc_assert (type == chrec_type (poly0));
109169689Skan
110169689Skan  /*
111169689Skan    {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
112169689Skan    {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
113169689Skan    {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
114169689Skan  if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
115169689Skan    {
116169689Skan      if (code == PLUS_EXPR)
117169689Skan	return build_polynomial_chrec
118169689Skan	  (CHREC_VARIABLE (poly1),
119169689Skan	   chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
120169689Skan	   CHREC_RIGHT (poly1));
121169689Skan      else
122169689Skan	return build_polynomial_chrec
123169689Skan	  (CHREC_VARIABLE (poly1),
124169689Skan	   chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
125169689Skan	   chrec_fold_multiply (type, CHREC_RIGHT (poly1),
126169689Skan				SCALAR_FLOAT_TYPE_P (type)
127169689Skan				? build_real (type, dconstm1)
128169689Skan				: build_int_cst_type (type, -1)));
129169689Skan    }
130169689Skan
131169689Skan  if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
132169689Skan    {
133169689Skan      if (code == PLUS_EXPR)
134169689Skan	return build_polynomial_chrec
135169689Skan	  (CHREC_VARIABLE (poly0),
136169689Skan	   chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
137169689Skan	   CHREC_RIGHT (poly0));
138169689Skan      else
139169689Skan	return build_polynomial_chrec
140169689Skan	  (CHREC_VARIABLE (poly0),
141169689Skan	   chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
142169689Skan	   CHREC_RIGHT (poly0));
143169689Skan    }
144169689Skan
145169689Skan  if (code == PLUS_EXPR)
146169689Skan    {
147169689Skan      left = chrec_fold_plus
148169689Skan	(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
149169689Skan      right = chrec_fold_plus
150169689Skan	(type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
151169689Skan    }
152169689Skan  else
153169689Skan    {
154169689Skan      left = chrec_fold_minus
155169689Skan	(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
156169689Skan      right = chrec_fold_minus
157169689Skan	(type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
158169689Skan    }
159169689Skan
160169689Skan  if (chrec_zerop (right))
161169689Skan    return left;
162169689Skan  else
163169689Skan    return build_polynomial_chrec
164169689Skan      (CHREC_VARIABLE (poly0), left, right);
165169689Skan}
166169689Skan
167169689Skan
168169689Skan
169169689Skan/* Fold the multiplication of two polynomial functions.  */
170169689Skan
171169689Skanstatic inline tree
172169689Skanchrec_fold_multiply_poly_poly (tree type,
173169689Skan			       tree poly0,
174169689Skan			       tree poly1)
175169689Skan{
176169689Skan  tree t0, t1, t2;
177169689Skan  int var;
178169689Skan
179169689Skan  gcc_assert (poly0);
180169689Skan  gcc_assert (poly1);
181169689Skan  gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
182169689Skan  gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
183169689Skan  gcc_assert (chrec_type (poly0) == chrec_type (poly1));
184169689Skan  gcc_assert (type == chrec_type (poly0));
185169689Skan
186169689Skan  /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
187169689Skan     {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
188169689Skan     {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
189169689Skan  if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
190169689Skan    /* poly0 is a constant wrt. poly1.  */
191169689Skan    return build_polynomial_chrec
192169689Skan      (CHREC_VARIABLE (poly1),
193169689Skan       chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
194169689Skan       CHREC_RIGHT (poly1));
195169689Skan
196169689Skan  if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
197169689Skan    /* poly1 is a constant wrt. poly0.  */
198169689Skan    return build_polynomial_chrec
199169689Skan      (CHREC_VARIABLE (poly0),
200169689Skan       chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
201169689Skan       CHREC_RIGHT (poly0));
202169689Skan
203169689Skan  /* poly0 and poly1 are two polynomials in the same variable,
204169689Skan     {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
205169689Skan
206169689Skan  /* "a*c".  */
207169689Skan  t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
208169689Skan
209169689Skan  /* "a*d + b*c + b*d".  */
210169689Skan  t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
211169689Skan  t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
212169689Skan						       CHREC_RIGHT (poly0),
213169689Skan						       CHREC_LEFT (poly1)));
214169689Skan  t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
215169689Skan						       CHREC_RIGHT (poly0),
216169689Skan						       CHREC_RIGHT (poly1)));
217169689Skan  /* "2*b*d".  */
218169689Skan  t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
219169689Skan  t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
220169689Skan			    ? build_real (type, dconst2)
221169689Skan			    : build_int_cst (type, 2), t2);
222169689Skan
223169689Skan  var = CHREC_VARIABLE (poly0);
224169689Skan  return build_polynomial_chrec (var, t0,
225169689Skan				 build_polynomial_chrec (var, t1, t2));
226169689Skan}
227169689Skan
228169689Skan/* When the operands are automatically_generated_chrec_p, the fold has
229169689Skan   to respect the semantics of the operands.  */
230169689Skan
231169689Skanstatic inline tree
232169689Skanchrec_fold_automatically_generated_operands (tree op0,
233169689Skan					     tree op1)
234169689Skan{
235169689Skan  if (op0 == chrec_dont_know
236169689Skan      || op1 == chrec_dont_know)
237169689Skan    return chrec_dont_know;
238169689Skan
239169689Skan  if (op0 == chrec_known
240169689Skan      || op1 == chrec_known)
241169689Skan    return chrec_known;
242169689Skan
243169689Skan  if (op0 == chrec_not_analyzed_yet
244169689Skan      || op1 == chrec_not_analyzed_yet)
245169689Skan    return chrec_not_analyzed_yet;
246169689Skan
247169689Skan  /* The default case produces a safe result.  */
248169689Skan  return chrec_dont_know;
249169689Skan}
250169689Skan
251169689Skan/* Fold the addition of two chrecs.  */
252169689Skan
253169689Skanstatic tree
254169689Skanchrec_fold_plus_1 (enum tree_code code, tree type,
255169689Skan		   tree op0, tree op1)
256169689Skan{
257169689Skan  if (automatically_generated_chrec_p (op0)
258169689Skan      || automatically_generated_chrec_p (op1))
259169689Skan    return chrec_fold_automatically_generated_operands (op0, op1);
260169689Skan
261169689Skan  switch (TREE_CODE (op0))
262169689Skan    {
263169689Skan    case POLYNOMIAL_CHREC:
264169689Skan      switch (TREE_CODE (op1))
265169689Skan	{
266169689Skan	case POLYNOMIAL_CHREC:
267169689Skan	  return chrec_fold_plus_poly_poly (code, type, op0, op1);
268169689Skan
269169689Skan	default:
270169689Skan	  if (code == PLUS_EXPR)
271169689Skan	    return build_polynomial_chrec
272169689Skan	      (CHREC_VARIABLE (op0),
273169689Skan	       chrec_fold_plus (type, CHREC_LEFT (op0), op1),
274169689Skan	       CHREC_RIGHT (op0));
275169689Skan	  else
276169689Skan	    return build_polynomial_chrec
277169689Skan	      (CHREC_VARIABLE (op0),
278169689Skan	       chrec_fold_minus (type, CHREC_LEFT (op0), op1),
279169689Skan	       CHREC_RIGHT (op0));
280169689Skan	}
281169689Skan
282169689Skan    default:
283169689Skan      switch (TREE_CODE (op1))
284169689Skan	{
285169689Skan	case POLYNOMIAL_CHREC:
286169689Skan	  if (code == PLUS_EXPR)
287169689Skan	    return build_polynomial_chrec
288169689Skan	      (CHREC_VARIABLE (op1),
289169689Skan	       chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
290169689Skan	       CHREC_RIGHT (op1));
291169689Skan	  else
292169689Skan	    return build_polynomial_chrec
293169689Skan	      (CHREC_VARIABLE (op1),
294169689Skan	       chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
295169689Skan	       chrec_fold_multiply (type, CHREC_RIGHT (op1),
296169689Skan				    SCALAR_FLOAT_TYPE_P (type)
297169689Skan				    ? build_real (type, dconstm1)
298169689Skan				    : build_int_cst_type (type, -1)));
299169689Skan
300169689Skan	default:
301169689Skan	  {
302169689Skan	    int size = 0;
303169689Skan	    if ((tree_contains_chrecs (op0, &size)
304169689Skan		 || tree_contains_chrecs (op1, &size))
305169689Skan		&& size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
306169689Skan	      return build2 (code, type, op0, op1);
307169689Skan	    else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
308169689Skan	      return fold_build2 (code, type,
309169689Skan				  fold_convert (type, op0),
310169689Skan				  fold_convert (type, op1));
311169689Skan	    else
312169689Skan	      return chrec_dont_know;
313169689Skan	  }
314169689Skan	}
315169689Skan    }
316169689Skan}
317169689Skan
318169689Skan/* Fold the addition of two chrecs.  */
319169689Skan
320169689Skantree
321169689Skanchrec_fold_plus (tree type,
322169689Skan		 tree op0,
323169689Skan		 tree op1)
324169689Skan{
325169689Skan  if (automatically_generated_chrec_p (op0)
326169689Skan      || automatically_generated_chrec_p (op1))
327169689Skan    return chrec_fold_automatically_generated_operands (op0, op1);
328169689Skan
329169689Skan  if (integer_zerop (op0))
330169689Skan    return op1;
331169689Skan  if (integer_zerop (op1))
332169689Skan    return op0;
333169689Skan
334169689Skan  return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
335169689Skan}
336169689Skan
337169689Skan/* Fold the subtraction of two chrecs.  */
338169689Skan
339169689Skantree
340169689Skanchrec_fold_minus (tree type,
341169689Skan		  tree op0,
342169689Skan		  tree op1)
343169689Skan{
344169689Skan  if (automatically_generated_chrec_p (op0)
345169689Skan      || automatically_generated_chrec_p (op1))
346169689Skan    return chrec_fold_automatically_generated_operands (op0, op1);
347169689Skan
348169689Skan  if (integer_zerop (op1))
349169689Skan    return op0;
350169689Skan
351169689Skan  return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
352169689Skan}
353169689Skan
354169689Skan/* Fold the multiplication of two chrecs.  */
355169689Skan
356169689Skantree
357169689Skanchrec_fold_multiply (tree type,
358169689Skan		     tree op0,
359169689Skan		     tree op1)
360169689Skan{
361169689Skan  if (automatically_generated_chrec_p (op0)
362169689Skan      || automatically_generated_chrec_p (op1))
363169689Skan    return chrec_fold_automatically_generated_operands (op0, op1);
364169689Skan
365169689Skan  switch (TREE_CODE (op0))
366169689Skan    {
367169689Skan    case POLYNOMIAL_CHREC:
368169689Skan      switch (TREE_CODE (op1))
369169689Skan	{
370169689Skan	case POLYNOMIAL_CHREC:
371169689Skan	  return chrec_fold_multiply_poly_poly (type, op0, op1);
372169689Skan
373169689Skan	default:
374169689Skan	  if (integer_onep (op1))
375169689Skan	    return op0;
376169689Skan	  if (integer_zerop (op1))
377169689Skan	    return build_int_cst (type, 0);
378169689Skan
379169689Skan	  return build_polynomial_chrec
380169689Skan	    (CHREC_VARIABLE (op0),
381169689Skan	     chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
382169689Skan	     chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
383169689Skan	}
384169689Skan
385169689Skan    default:
386169689Skan      if (integer_onep (op0))
387169689Skan	return op1;
388169689Skan
389169689Skan      if (integer_zerop (op0))
390169689Skan    	return build_int_cst (type, 0);
391169689Skan
392169689Skan      switch (TREE_CODE (op1))
393169689Skan	{
394169689Skan	case POLYNOMIAL_CHREC:
395169689Skan	  return build_polynomial_chrec
396169689Skan	    (CHREC_VARIABLE (op1),
397169689Skan	     chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
398169689Skan	     chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
399169689Skan
400169689Skan	default:
401169689Skan	  if (integer_onep (op1))
402169689Skan	    return op0;
403169689Skan	  if (integer_zerop (op1))
404169689Skan	    return build_int_cst (type, 0);
405169689Skan	  return fold_build2 (MULT_EXPR, type, op0, op1);
406169689Skan	}
407169689Skan    }
408169689Skan}
409169689Skan
410169689Skan
411169689Skan
412169689Skan/* Operations.  */
413169689Skan
414169689Skan/* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
415169689Skan   calculation overflows, otherwise return C(n,k) with type TYPE.  */
416169689Skan
417169689Skanstatic tree
418169689Skantree_fold_binomial (tree type, tree n, unsigned int k)
419169689Skan{
420169689Skan  unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
421169689Skan  HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
422169689Skan  unsigned int i;
423169689Skan  tree res;
424169689Skan
425169689Skan  /* Handle the most frequent cases.  */
426169689Skan  if (k == 0)
427169689Skan    return build_int_cst (type, 1);
428169689Skan  if (k == 1)
429169689Skan    return fold_convert (type, n);
430169689Skan
431169689Skan  /* Check that k <= n.  */
432169689Skan  if (TREE_INT_CST_HIGH (n) == 0
433169689Skan      && TREE_INT_CST_LOW (n) < k)
434169689Skan    return NULL_TREE;
435169689Skan
436169689Skan  /* Numerator = n.  */
437169689Skan  lnum = TREE_INT_CST_LOW (n);
438169689Skan  hnum = TREE_INT_CST_HIGH (n);
439169689Skan
440169689Skan  /* Denominator = 2.  */
441169689Skan  ldenom = 2;
442169689Skan  hdenom = 0;
443169689Skan
444169689Skan  /* Index = Numerator-1.  */
445169689Skan  if (lnum == 0)
446169689Skan    {
447169689Skan      hidx = hnum - 1;
448169689Skan      lidx = ~ (unsigned HOST_WIDE_INT) 0;
449169689Skan    }
450169689Skan  else
451169689Skan    {
452169689Skan      hidx = hnum;
453169689Skan      lidx = lnum - 1;
454169689Skan    }
455169689Skan
456169689Skan  /* Numerator = Numerator*Index = n*(n-1).  */
457169689Skan  if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
458169689Skan    return NULL_TREE;
459169689Skan
460169689Skan  for (i = 3; i <= k; i++)
461169689Skan    {
462169689Skan      /* Index--.  */
463169689Skan      if (lidx == 0)
464169689Skan	{
465169689Skan	  hidx--;
466169689Skan	  lidx = ~ (unsigned HOST_WIDE_INT) 0;
467169689Skan	}
468169689Skan      else
469169689Skan        lidx--;
470169689Skan
471169689Skan      /* Numerator *= Index.  */
472169689Skan      if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum))
473169689Skan	return NULL_TREE;
474169689Skan
475169689Skan      /* Denominator *= i.  */
476169689Skan      mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom);
477169689Skan    }
478169689Skan
479169689Skan  /* Result = Numerator / Denominator.  */
480169689Skan  div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom,
481169689Skan			&lres, &hres, &ldum, &hdum);
482169689Skan
483169689Skan  res = build_int_cst_wide (type, lres, hres);
484169689Skan  return int_fits_type_p (res, type) ? res : NULL_TREE;
485169689Skan}
486169689Skan
487169689Skan/* Helper function.  Use the Newton's interpolating formula for
488169689Skan   evaluating the value of the evolution function.  */
489169689Skan
490169689Skanstatic tree
491169689Skanchrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
492169689Skan{
493169689Skan  tree arg0, arg1, binomial_n_k;
494169689Skan  tree type = TREE_TYPE (chrec);
495169689Skan
496169689Skan  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
497169689Skan	 && CHREC_VARIABLE (chrec) > var)
498169689Skan    chrec = CHREC_LEFT (chrec);
499169689Skan
500169689Skan  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
501169689Skan      && CHREC_VARIABLE (chrec) == var)
502169689Skan    {
503169689Skan      arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
504169689Skan      if (arg0 == chrec_dont_know)
505169689Skan	return chrec_dont_know;
506169689Skan      binomial_n_k = tree_fold_binomial (type, n, k);
507169689Skan      if (!binomial_n_k)
508169689Skan	return chrec_dont_know;
509169689Skan      arg1 = fold_build2 (MULT_EXPR, type,
510169689Skan			  CHREC_LEFT (chrec), binomial_n_k);
511169689Skan      return chrec_fold_plus (type, arg0, arg1);
512169689Skan    }
513169689Skan
514169689Skan  binomial_n_k = tree_fold_binomial (type, n, k);
515169689Skan  if (!binomial_n_k)
516169689Skan    return chrec_dont_know;
517169689Skan
518169689Skan  return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
519169689Skan}
520169689Skan
521169689Skan/* Evaluates "CHREC (X)" when the varying variable is VAR.
522169689Skan   Example:  Given the following parameters,
523169689Skan
524169689Skan   var = 1
525169689Skan   chrec = {3, +, 4}_1
526169689Skan   x = 10
527169689Skan
528169689Skan   The result is given by the Newton's interpolating formula:
529169689Skan   3 * \binom{10}{0} + 4 * \binom{10}{1}.
530169689Skan*/
531169689Skan
532169689Skantree
533169689Skanchrec_apply (unsigned var,
534169689Skan	     tree chrec,
535169689Skan	     tree x)
536169689Skan{
537169689Skan  tree type = chrec_type (chrec);
538169689Skan  tree res = chrec_dont_know;
539169689Skan
540169689Skan  if (automatically_generated_chrec_p (chrec)
541169689Skan      || automatically_generated_chrec_p (x)
542169689Skan
543169689Skan      /* When the symbols are defined in an outer loop, it is possible
544169689Skan	 to symbolically compute the apply, since the symbols are
545169689Skan	 constants with respect to the varying loop.  */
546169689Skan      || chrec_contains_symbols_defined_in_loop (chrec, var))
547169689Skan    return chrec_dont_know;
548169689Skan
549169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
550169689Skan    fprintf (dump_file, "(chrec_apply \n");
551169689Skan
552169689Skan  if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
553169689Skan    x = build_real_from_int_cst (type, x);
554169689Skan
555169689Skan  if (evolution_function_is_affine_p (chrec))
556169689Skan    {
557169689Skan      /* "{a, +, b} (x)"  ->  "a + b*x".  */
558169689Skan      x = chrec_convert (type, x, NULL_TREE);
559169689Skan      res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
560169689Skan      if (!integer_zerop (CHREC_LEFT (chrec)))
561169689Skan	res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
562169689Skan    }
563169689Skan
564169689Skan  else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
565169689Skan    res = chrec;
566169689Skan
567169689Skan  else if (TREE_CODE (x) == INTEGER_CST
568169689Skan	   && tree_int_cst_sgn (x) == 1)
569169689Skan    /* testsuite/.../ssa-chrec-38.c.  */
570169689Skan    res = chrec_evaluate (var, chrec, x, 0);
571169689Skan  else
572169689Skan    res = chrec_dont_know;
573169689Skan
574169689Skan  if (dump_file && (dump_flags & TDF_DETAILS))
575169689Skan    {
576169689Skan      fprintf (dump_file, "  (varying_loop = %d\n", var);
577169689Skan      fprintf (dump_file, ")\n  (chrec = ");
578169689Skan      print_generic_expr (dump_file, chrec, 0);
579169689Skan      fprintf (dump_file, ")\n  (x = ");
580169689Skan      print_generic_expr (dump_file, x, 0);
581169689Skan      fprintf (dump_file, ")\n  (res = ");
582169689Skan      print_generic_expr (dump_file, res, 0);
583169689Skan      fprintf (dump_file, "))\n");
584169689Skan    }
585169689Skan
586169689Skan  return res;
587169689Skan}
588169689Skan
589169689Skan/* Replaces the initial condition in CHREC with INIT_COND.  */
590169689Skan
591169689Skantree
592169689Skanchrec_replace_initial_condition (tree chrec,
593169689Skan				 tree init_cond)
594169689Skan{
595169689Skan  if (automatically_generated_chrec_p (chrec))
596169689Skan    return chrec;
597169689Skan
598169689Skan  gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
599169689Skan
600169689Skan  switch (TREE_CODE (chrec))
601169689Skan    {
602169689Skan    case POLYNOMIAL_CHREC:
603169689Skan      return build_polynomial_chrec
604169689Skan	(CHREC_VARIABLE (chrec),
605169689Skan	 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
606169689Skan	 CHREC_RIGHT (chrec));
607169689Skan
608169689Skan    default:
609169689Skan      return init_cond;
610169689Skan    }
611169689Skan}
612169689Skan
613169689Skan/* Returns the initial condition of a given CHREC.  */
614169689Skan
615169689Skantree
616169689Skaninitial_condition (tree chrec)
617169689Skan{
618169689Skan  if (automatically_generated_chrec_p (chrec))
619169689Skan    return chrec;
620169689Skan
621169689Skan  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
622169689Skan    return initial_condition (CHREC_LEFT (chrec));
623169689Skan  else
624169689Skan    return chrec;
625169689Skan}
626169689Skan
627169689Skan/* Returns a univariate function that represents the evolution in
628169689Skan   LOOP_NUM.  Mask the evolution of any other loop.  */
629169689Skan
630169689Skantree
631169689Skanhide_evolution_in_other_loops_than_loop (tree chrec,
632169689Skan					 unsigned loop_num)
633169689Skan{
634169689Skan  if (automatically_generated_chrec_p (chrec))
635169689Skan    return chrec;
636169689Skan
637169689Skan  switch (TREE_CODE (chrec))
638169689Skan    {
639169689Skan    case POLYNOMIAL_CHREC:
640169689Skan      if (CHREC_VARIABLE (chrec) == loop_num)
641169689Skan	return build_polynomial_chrec
642169689Skan	  (loop_num,
643169689Skan	   hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
644169689Skan						    loop_num),
645169689Skan	   CHREC_RIGHT (chrec));
646169689Skan
647169689Skan      else if (CHREC_VARIABLE (chrec) < loop_num)
648169689Skan	/* There is no evolution in this loop.  */
649169689Skan	return initial_condition (chrec);
650169689Skan
651169689Skan      else
652169689Skan	return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
653169689Skan							loop_num);
654169689Skan
655169689Skan    default:
656169689Skan      return chrec;
657169689Skan    }
658169689Skan}
659169689Skan
660169689Skan/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
661169689Skan   true, otherwise returns the initial condition in LOOP_NUM.  */
662169689Skan
663169689Skanstatic tree
664169689Skanchrec_component_in_loop_num (tree chrec,
665169689Skan			     unsigned loop_num,
666169689Skan			     bool right)
667169689Skan{
668169689Skan  tree component;
669169689Skan
670169689Skan  if (automatically_generated_chrec_p (chrec))
671169689Skan    return chrec;
672169689Skan
673169689Skan  switch (TREE_CODE (chrec))
674169689Skan    {
675169689Skan    case POLYNOMIAL_CHREC:
676169689Skan      if (CHREC_VARIABLE (chrec) == loop_num)
677169689Skan	{
678169689Skan	  if (right)
679169689Skan	    component = CHREC_RIGHT (chrec);
680169689Skan	  else
681169689Skan	    component = CHREC_LEFT (chrec);
682169689Skan
683169689Skan	  if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
684169689Skan	      || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
685169689Skan	    return component;
686169689Skan
687169689Skan	  else
688169689Skan	    return build_polynomial_chrec
689169689Skan	      (loop_num,
690169689Skan	       chrec_component_in_loop_num (CHREC_LEFT (chrec),
691169689Skan					    loop_num,
692169689Skan					    right),
693169689Skan	       component);
694169689Skan	}
695169689Skan
696169689Skan      else if (CHREC_VARIABLE (chrec) < loop_num)
697169689Skan	/* There is no evolution part in this loop.  */
698169689Skan	return NULL_TREE;
699169689Skan
700169689Skan      else
701169689Skan	return chrec_component_in_loop_num (CHREC_LEFT (chrec),
702169689Skan					    loop_num,
703169689Skan					    right);
704169689Skan
705169689Skan     default:
706169689Skan      if (right)
707169689Skan	return NULL_TREE;
708169689Skan      else
709169689Skan	return chrec;
710169689Skan    }
711169689Skan}
712169689Skan
713169689Skan/* Returns the evolution part in LOOP_NUM.  Example: the call
714169689Skan   evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
715169689Skan   {1, +, 2}_1  */
716169689Skan
717169689Skantree
718169689Skanevolution_part_in_loop_num (tree chrec,
719169689Skan			    unsigned loop_num)
720169689Skan{
721169689Skan  return chrec_component_in_loop_num (chrec, loop_num, true);
722169689Skan}
723169689Skan
724169689Skan/* Returns the initial condition in LOOP_NUM.  Example: the call
725169689Skan   initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
726169689Skan   {0, +, 1}_1  */
727169689Skan
728169689Skantree
729169689Skaninitial_condition_in_loop_num (tree chrec,
730169689Skan			       unsigned loop_num)
731169689Skan{
732169689Skan  return chrec_component_in_loop_num (chrec, loop_num, false);
733169689Skan}
734169689Skan
735169689Skan/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
736169689Skan   This function is essentially used for setting the evolution to
737169689Skan   chrec_dont_know, for example after having determined that it is
738169689Skan   impossible to say how many times a loop will execute.  */
739169689Skan
740169689Skantree
741169689Skanreset_evolution_in_loop (unsigned loop_num,
742169689Skan			 tree chrec,
743169689Skan			 tree new_evol)
744169689Skan{
745169689Skan  gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
746169689Skan
747169689Skan  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
748169689Skan      && CHREC_VARIABLE (chrec) > loop_num)
749169689Skan    {
750169689Skan      tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
751169689Skan					   new_evol);
752169689Skan      tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
753169689Skan					    new_evol);
754169689Skan      return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
755169689Skan		     build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
756169689Skan		     left, right);
757169689Skan    }
758169689Skan
759169689Skan  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
760169689Skan	 && CHREC_VARIABLE (chrec) == loop_num)
761169689Skan    chrec = CHREC_LEFT (chrec);
762169689Skan
763169689Skan  return build_polynomial_chrec (loop_num, chrec, new_evol);
764169689Skan}
765169689Skan
766169689Skan/* Merges two evolution functions that were found by following two
767169689Skan   alternate paths of a conditional expression.  */
768169689Skan
769169689Skantree
770169689Skanchrec_merge (tree chrec1,
771169689Skan	     tree chrec2)
772169689Skan{
773169689Skan  if (chrec1 == chrec_dont_know
774169689Skan      || chrec2 == chrec_dont_know)
775169689Skan    return chrec_dont_know;
776169689Skan
777169689Skan  if (chrec1 == chrec_known
778169689Skan      || chrec2 == chrec_known)
779169689Skan    return chrec_known;
780169689Skan
781169689Skan  if (chrec1 == chrec_not_analyzed_yet)
782169689Skan    return chrec2;
783169689Skan  if (chrec2 == chrec_not_analyzed_yet)
784169689Skan    return chrec1;
785169689Skan
786169689Skan  if (eq_evolutions_p (chrec1, chrec2))
787169689Skan    return chrec1;
788169689Skan
789169689Skan  return chrec_dont_know;
790169689Skan}
791169689Skan
792169689Skan
793169689Skan
794169689Skan/* Observers.  */
795169689Skan
796169689Skan/* Helper function for is_multivariate_chrec.  */
797169689Skan
798169689Skanstatic bool
799169689Skanis_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
800169689Skan{
801169689Skan  if (chrec == NULL_TREE)
802169689Skan    return false;
803169689Skan
804169689Skan  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
805169689Skan    {
806169689Skan      if (CHREC_VARIABLE (chrec) != rec_var)
807169689Skan	return true;
808169689Skan      else
809169689Skan	return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
810169689Skan		|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
811169689Skan    }
812169689Skan  else
813169689Skan    return false;
814169689Skan}
815169689Skan
816169689Skan/* Determine whether the given chrec is multivariate or not.  */
817169689Skan
818169689Skanbool
819169689Skanis_multivariate_chrec (tree chrec)
820169689Skan{
821169689Skan  if (chrec == NULL_TREE)
822169689Skan    return false;
823169689Skan
824169689Skan  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
825169689Skan    return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
826169689Skan				       CHREC_VARIABLE (chrec))
827169689Skan	    || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
828169689Skan					  CHREC_VARIABLE (chrec)));
829169689Skan  else
830169689Skan    return false;
831169689Skan}
832169689Skan
833169689Skan/* Determines whether the chrec contains symbolic names or not.  */
834169689Skan
835169689Skanbool
836169689Skanchrec_contains_symbols (tree chrec)
837169689Skan{
838169689Skan  if (chrec == NULL_TREE)
839169689Skan    return false;
840169689Skan
841169689Skan  if (TREE_CODE (chrec) == SSA_NAME
842169689Skan      || TREE_CODE (chrec) == VAR_DECL
843169689Skan      || TREE_CODE (chrec) == PARM_DECL
844169689Skan      || TREE_CODE (chrec) == FUNCTION_DECL
845169689Skan      || TREE_CODE (chrec) == LABEL_DECL
846169689Skan      || TREE_CODE (chrec) == RESULT_DECL
847169689Skan      || TREE_CODE (chrec) == FIELD_DECL)
848169689Skan    return true;
849169689Skan
850169689Skan  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
851169689Skan    {
852169689Skan    case 3:
853169689Skan      if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
854169689Skan	return true;
855169689Skan
856169689Skan    case 2:
857169689Skan      if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
858169689Skan	return true;
859169689Skan
860169689Skan    case 1:
861169689Skan      if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
862169689Skan	return true;
863169689Skan
864169689Skan    default:
865169689Skan      return false;
866169689Skan    }
867169689Skan}
868169689Skan
869169689Skan/* Determines whether the chrec contains undetermined coefficients.  */
870169689Skan
871169689Skanbool
872169689Skanchrec_contains_undetermined (tree chrec)
873169689Skan{
874169689Skan  if (chrec == chrec_dont_know
875169689Skan      || chrec == chrec_not_analyzed_yet
876169689Skan      || chrec == NULL_TREE)
877169689Skan    return true;
878169689Skan
879169689Skan  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
880169689Skan    {
881169689Skan    case 3:
882169689Skan      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
883169689Skan	return true;
884169689Skan
885169689Skan    case 2:
886169689Skan      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
887169689Skan	return true;
888169689Skan
889169689Skan    case 1:
890169689Skan      if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
891169689Skan	return true;
892169689Skan
893169689Skan    default:
894169689Skan      return false;
895169689Skan    }
896169689Skan}
897169689Skan
898169689Skan/* Determines whether the tree EXPR contains chrecs, and increment
899169689Skan   SIZE if it is not a NULL pointer by an estimation of the depth of
900169689Skan   the tree.  */
901169689Skan
902169689Skanbool
903169689Skantree_contains_chrecs (tree expr, int *size)
904169689Skan{
905169689Skan  if (expr == NULL_TREE)
906169689Skan    return false;
907169689Skan
908169689Skan  if (size)
909169689Skan    (*size)++;
910169689Skan
911169689Skan  if (tree_is_chrec (expr))
912169689Skan    return true;
913169689Skan
914169689Skan  switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
915169689Skan    {
916169689Skan    case 3:
917169689Skan      if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
918169689Skan	return true;
919169689Skan
920169689Skan    case 2:
921169689Skan      if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
922169689Skan	return true;
923169689Skan
924169689Skan    case 1:
925169689Skan      if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
926169689Skan	return true;
927169689Skan
928169689Skan    default:
929169689Skan      return false;
930169689Skan    }
931169689Skan}
932169689Skan
933169689Skan/* Recursive helper function.  */
934169689Skan
935169689Skanstatic bool
936169689Skanevolution_function_is_invariant_rec_p (tree chrec, int loopnum)
937169689Skan{
938169689Skan  if (evolution_function_is_constant_p (chrec))
939169689Skan    return true;
940169689Skan
941169689Skan  if (TREE_CODE (chrec) == SSA_NAME
942169689Skan      && expr_invariant_in_loop_p (current_loops->parray[loopnum],
943169689Skan				   chrec))
944169689Skan    return true;
945169689Skan
946169689Skan  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
947169689Skan    {
948169689Skan      if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
949169689Skan	  || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
950169689Skan						     loopnum)
951169689Skan	  || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
952169689Skan						     loopnum))
953169689Skan	return false;
954169689Skan      return true;
955169689Skan    }
956169689Skan
957169689Skan  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
958169689Skan    {
959169689Skan    case 2:
960169689Skan      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
961169689Skan						  loopnum))
962169689Skan	return false;
963169689Skan
964169689Skan    case 1:
965169689Skan      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
966169689Skan						  loopnum))
967169689Skan	return false;
968169689Skan      return true;
969169689Skan
970169689Skan    default:
971169689Skan      return false;
972169689Skan    }
973169689Skan
974169689Skan  return false;
975169689Skan}
976169689Skan
977169689Skan/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
978169689Skan
979169689Skanbool
980169689Skanevolution_function_is_invariant_p (tree chrec, int loopnum)
981169689Skan{
982169689Skan  if (evolution_function_is_constant_p (chrec))
983169689Skan    return true;
984169689Skan
985169689Skan  if (current_loops != NULL)
986169689Skan    return evolution_function_is_invariant_rec_p (chrec, loopnum);
987169689Skan
988169689Skan  return false;
989169689Skan}
990169689Skan
991169689Skan/* Determine whether the given tree is an affine multivariate
992169689Skan   evolution.  */
993169689Skan
994169689Skanbool
995169689Skanevolution_function_is_affine_multivariate_p (tree chrec)
996169689Skan{
997169689Skan  if (chrec == NULL_TREE)
998169689Skan    return false;
999169689Skan
1000169689Skan  switch (TREE_CODE (chrec))
1001169689Skan    {
1002169689Skan    case POLYNOMIAL_CHREC:
1003169689Skan      if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
1004169689Skan	{
1005169689Skan	  if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
1006169689Skan	    return true;
1007169689Skan	  else
1008169689Skan	    {
1009169689Skan	      if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1010169689Skan		  && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1011169689Skan		     != CHREC_VARIABLE (chrec)
1012169689Skan		  && evolution_function_is_affine_multivariate_p
1013169689Skan		  (CHREC_RIGHT (chrec)))
1014169689Skan		return true;
1015169689Skan	      else
1016169689Skan		return false;
1017169689Skan	    }
1018169689Skan	}
1019169689Skan      else
1020169689Skan	{
1021169689Skan	  if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
1022169689Skan	      && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1023169689Skan	      && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1024169689Skan	      && evolution_function_is_affine_multivariate_p
1025169689Skan	      (CHREC_LEFT (chrec)))
1026169689Skan	    return true;
1027169689Skan	  else
1028169689Skan	    return false;
1029169689Skan	}
1030169689Skan
1031169689Skan    default:
1032169689Skan      return false;
1033169689Skan    }
1034169689Skan}
1035169689Skan
1036169689Skan/* Determine whether the given tree is a function in zero or one
1037169689Skan   variables.  */
1038169689Skan
1039169689Skanbool
1040169689Skanevolution_function_is_univariate_p (tree chrec)
1041169689Skan{
1042169689Skan  if (chrec == NULL_TREE)
1043169689Skan    return true;
1044169689Skan
1045169689Skan  switch (TREE_CODE (chrec))
1046169689Skan    {
1047169689Skan    case POLYNOMIAL_CHREC:
1048169689Skan      switch (TREE_CODE (CHREC_LEFT (chrec)))
1049169689Skan	{
1050169689Skan	case POLYNOMIAL_CHREC:
1051169689Skan	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1052169689Skan	    return false;
1053169689Skan	  if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1054169689Skan	    return false;
1055169689Skan	  break;
1056169689Skan
1057169689Skan	default:
1058169689Skan	  break;
1059169689Skan	}
1060169689Skan
1061169689Skan      switch (TREE_CODE (CHREC_RIGHT (chrec)))
1062169689Skan	{
1063169689Skan	case POLYNOMIAL_CHREC:
1064169689Skan	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1065169689Skan	    return false;
1066169689Skan	  if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1067169689Skan	    return false;
1068169689Skan	  break;
1069169689Skan
1070169689Skan	default:
1071169689Skan	  break;
1072169689Skan	}
1073169689Skan
1074169689Skan    default:
1075169689Skan      return true;
1076169689Skan    }
1077169689Skan}
1078169689Skan
1079169689Skan/* Returns the number of variables of CHREC.  Example: the call
1080169689Skan   nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1081169689Skan
1082169689Skanunsigned
1083169689Skannb_vars_in_chrec (tree chrec)
1084169689Skan{
1085169689Skan  if (chrec == NULL_TREE)
1086169689Skan    return 0;
1087169689Skan
1088169689Skan  switch (TREE_CODE (chrec))
1089169689Skan    {
1090169689Skan    case POLYNOMIAL_CHREC:
1091169689Skan      return 1 + nb_vars_in_chrec
1092169689Skan	(initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1093169689Skan
1094169689Skan    default:
1095169689Skan      return 0;
1096169689Skan    }
1097169689Skan}
1098169689Skan
1099169689Skan/* Returns true if TYPE is a type in that we cannot directly perform
1100169689Skan   arithmetics, even though it is a scalar type.  */
1101169689Skan
1102169689Skanstatic bool
1103169689Skanavoid_arithmetics_in_type_p (tree type)
1104169689Skan{
1105169689Skan  /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1106169689Skan     in the subtype, but a base type must be used, and the result then can
1107169689Skan     be casted to the subtype.  */
1108169689Skan  if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
1109169689Skan    return true;
1110169689Skan
1111169689Skan  return false;
1112169689Skan}
1113169689Skan
1114169689Skanstatic tree chrec_convert_1 (tree, tree, tree, bool);
1115169689Skan
1116169689Skan/* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1117169689Skan   the scev corresponds to.  AT_STMT is the statement at that the scev is
1118169689Skan   evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
1119169689Skan   the rules for overflow of the given language apply (e.g., that signed
1120169689Skan   arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1121169689Skan   tests, but also to enforce that the result follows them.  Returns true if the
1122169689Skan   conversion succeeded, false otherwise.  */
1123169689Skan
1124169689Skanbool
1125169689Skanconvert_affine_scev (struct loop *loop, tree type,
1126169689Skan		     tree *base, tree *step, tree at_stmt,
1127169689Skan		     bool use_overflow_semantics)
1128169689Skan{
1129169689Skan  tree ct = TREE_TYPE (*step);
1130169689Skan  bool enforce_overflow_semantics;
1131169689Skan  bool must_check_src_overflow, must_check_rslt_overflow;
1132169689Skan  tree new_base, new_step;
1133169689Skan
1134169689Skan  /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1135169689Skan  if (avoid_arithmetics_in_type_p (type))
1136169689Skan    return false;
1137169689Skan
1138169689Skan  /* In general,
1139169689Skan     (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1140169689Skan     but we must check some assumptions.
1141169689Skan
1142169689Skan     1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1143169689Skan        of CT is smaller than the precision of TYPE.  For example, when we
1144169689Skan	cast unsigned char [254, +, 1] to unsigned, the values on left side
1145169689Skan	are 254, 255, 0, 1, ..., but those on the right side are
1146169689Skan	254, 255, 256, 257, ...
1147169689Skan     2) In case that we must also preserve the fact that signed ivs do not
1148169689Skan        overflow, we must additionally check that the new iv does not wrap.
1149169689Skan	For example, unsigned char [125, +, 1] casted to signed char could
1150169689Skan	become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1151169689Skan	which would confuse optimizers that assume that this does not
1152169689Skan	happen.  */
1153169689Skan  must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1154169689Skan
1155169689Skan  enforce_overflow_semantics = (use_overflow_semantics
1156169689Skan				&& nowrap_type_p (type));
1157169689Skan  if (enforce_overflow_semantics)
1158169689Skan    {
1159169689Skan      /* We can avoid checking whether the result overflows in the following
1160169689Skan	 cases:
1161169689Skan
1162169689Skan	 -- must_check_src_overflow is true, and the range of TYPE is superset
1163169689Skan	    of the range of CT -- i.e., in all cases except if CT signed and
1164169689Skan	    TYPE unsigned.
1165169689Skan         -- both CT and TYPE have the same precision and signedness, and we
1166169689Skan	    verify instead that the source does not overflow (this may be
1167169689Skan	    easier than verifying it for the result, as we may use the
1168169689Skan	    information about the semantics of overflow in CT).  */
1169169689Skan      if (must_check_src_overflow)
1170169689Skan	{
1171169689Skan	  if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1172169689Skan	    must_check_rslt_overflow = true;
1173169689Skan	  else
1174169689Skan	    must_check_rslt_overflow = false;
1175169689Skan	}
1176169689Skan      else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1177169689Skan	       && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1178169689Skan	{
1179169689Skan	  must_check_rslt_overflow = false;
1180169689Skan	  must_check_src_overflow = true;
1181169689Skan	}
1182169689Skan      else
1183169689Skan	must_check_rslt_overflow = true;
1184169689Skan    }
1185169689Skan  else
1186169689Skan    must_check_rslt_overflow = false;
1187169689Skan
1188169689Skan  if (must_check_src_overflow
1189169689Skan      && scev_probably_wraps_p (*base, *step, at_stmt, loop,
1190169689Skan				use_overflow_semantics))
1191169689Skan    return false;
1192169689Skan
1193169689Skan  new_base = chrec_convert_1 (type, *base, at_stmt,
1194169689Skan			      use_overflow_semantics);
1195169689Skan  /* The step must be sign extended, regardless of the signedness
1196169689Skan     of CT and TYPE.  This only needs to be handled specially when
1197169689Skan     CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1198169689Skan     (with values 100, 99, 98, ...) from becoming signed or unsigned
1199169689Skan     [100, +, 255] with values 100, 355, ...; the sign-extension is
1200169689Skan     performed by default when CT is signed.  */
1201169689Skan  new_step = *step;
1202169689Skan  if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1203169689Skan    new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1204169689Skan				use_overflow_semantics);
1205169689Skan  new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
1206169689Skan
1207169689Skan  if (automatically_generated_chrec_p (new_base)
1208169689Skan      || automatically_generated_chrec_p (new_step))
1209169689Skan    return false;
1210169689Skan
1211169689Skan  if (must_check_rslt_overflow
1212169689Skan      /* Note that in this case we cannot use the fact that signed variables
1213169689Skan	 do not overflow, as this is what we are verifying for the new iv.  */
1214169689Skan      && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
1215169689Skan    return false;
1216169689Skan
1217169689Skan  *base = new_base;
1218169689Skan  *step = new_step;
1219169689Skan  return true;
1220169689Skan}
1221169689Skan
1222169689Skan
1223169689Skan/* Convert CHREC to TYPE.  When the analyzer knows the context in
1224169689Skan   which the CHREC is built, it sets AT_STMT to the statement that
1225169689Skan   contains the definition of the analyzed variable, otherwise the
1226169689Skan   conversion is less accurate: the information is used for
1227169689Skan   determining a more accurate estimation of the number of iterations.
1228169689Skan   By default AT_STMT could be safely set to NULL_TREE.
1229169689Skan
1230169689Skan   The following rule is always true: TREE_TYPE (chrec) ==
1231169689Skan   TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1232169689Skan   An example of what could happen when adding two chrecs and the type
1233169689Skan   of the CHREC_RIGHT is different than CHREC_LEFT is:
1234169689Skan
1235169689Skan   {(uint) 0, +, (uchar) 10} +
1236169689Skan   {(uint) 0, +, (uchar) 250}
1237169689Skan
1238169689Skan   that would produce a wrong result if CHREC_RIGHT is not (uint):
1239169689Skan
1240169689Skan   {(uint) 0, +, (uchar) 4}
1241169689Skan
1242169689Skan   instead of
1243169689Skan
1244169689Skan   {(uint) 0, +, (uint) 260}
1245169689Skan*/
1246169689Skan
1247169689Skantree
1248169689Skanchrec_convert (tree type, tree chrec, tree at_stmt)
1249169689Skan{
1250169689Skan  return chrec_convert_1 (type, chrec, at_stmt, true);
1251169689Skan}
1252169689Skan
1253169689Skan/* Convert CHREC to TYPE.  When the analyzer knows the context in
1254169689Skan   which the CHREC is built, it sets AT_STMT to the statement that
1255169689Skan   contains the definition of the analyzed variable, otherwise the
1256169689Skan   conversion is less accurate: the information is used for
1257169689Skan   determining a more accurate estimation of the number of iterations.
1258169689Skan   By default AT_STMT could be safely set to NULL_TREE.
1259169689Skan
1260169689Skan   USE_OVERFLOW_SEMANTICS is true if this function should assume that
1261169689Skan   the rules for overflow of the given language apply (e.g., that signed
1262169689Skan   arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1263169689Skan   tests, but also to enforce that the result follows them.  */
1264169689Skan
1265169689Skanstatic tree
1266169689Skanchrec_convert_1 (tree type, tree chrec, tree at_stmt,
1267169689Skan		 bool use_overflow_semantics)
1268169689Skan{
1269169689Skan  tree ct, res;
1270169689Skan  tree base, step;
1271169689Skan  struct loop *loop;
1272169689Skan
1273169689Skan  if (automatically_generated_chrec_p (chrec))
1274169689Skan    return chrec;
1275169689Skan
1276169689Skan  ct = chrec_type (chrec);
1277169689Skan  if (ct == type)
1278169689Skan    return chrec;
1279169689Skan
1280169689Skan  if (!evolution_function_is_affine_p (chrec))
1281169689Skan    goto keep_cast;
1282169689Skan
1283169689Skan  loop = current_loops->parray[CHREC_VARIABLE (chrec)];
1284169689Skan  base = CHREC_LEFT (chrec);
1285169689Skan  step = CHREC_RIGHT (chrec);
1286169689Skan
1287169689Skan  if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1288169689Skan			   use_overflow_semantics))
1289169689Skan    return build_polynomial_chrec (loop->num, base, step);
1290169689Skan
1291169689Skan  /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1292169689Skankeep_cast:
1293169689Skan  res = fold_convert (type, chrec);
1294169689Skan
1295169689Skan  /* Don't propagate overflows.  */
1296169689Skan  if (CONSTANT_CLASS_P (res))
1297169689Skan    {
1298169689Skan      TREE_CONSTANT_OVERFLOW (res) = 0;
1299169689Skan      TREE_OVERFLOW (res) = 0;
1300169689Skan    }
1301169689Skan
1302169689Skan  /* But reject constants that don't fit in their type after conversion.
1303169689Skan     This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1304169689Skan     natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1305169689Skan     and can cause problems later when computing niters of loops.  Note
1306169689Skan     that we don't do the check before converting because we don't want
1307169689Skan     to reject conversions of negative chrecs to unsigned types.  */
1308169689Skan  if (TREE_CODE (res) == INTEGER_CST
1309169689Skan      && TREE_CODE (type) == INTEGER_TYPE
1310169689Skan      && !int_fits_type_p (res, type))
1311169689Skan    res = chrec_dont_know;
1312169689Skan
1313169689Skan  return res;
1314169689Skan}
1315169689Skan
1316169689Skan/* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1317169689Skan   chrec if something else than what chrec_convert would do happens, NULL_TREE
1318169689Skan   otherwise.  */
1319169689Skan
1320169689Skantree
1321169689Skanchrec_convert_aggressive (tree type, tree chrec)
1322169689Skan{
1323169689Skan  tree inner_type, left, right, lc, rc;
1324169689Skan
1325169689Skan  if (automatically_generated_chrec_p (chrec)
1326169689Skan      || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1327169689Skan    return NULL_TREE;
1328169689Skan
1329169689Skan  inner_type = TREE_TYPE (chrec);
1330169689Skan  if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1331169689Skan    return NULL_TREE;
1332169689Skan
1333169689Skan  /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
1334169689Skan  if (avoid_arithmetics_in_type_p (type))
1335169689Skan    return NULL_TREE;
1336169689Skan
1337169689Skan  left = CHREC_LEFT (chrec);
1338169689Skan  right = CHREC_RIGHT (chrec);
1339169689Skan  lc = chrec_convert_aggressive (type, left);
1340169689Skan  if (!lc)
1341169689Skan    lc = chrec_convert (type, left, NULL_TREE);
1342169689Skan  rc = chrec_convert_aggressive (type, right);
1343169689Skan  if (!rc)
1344169689Skan    rc = chrec_convert (type, right, NULL_TREE);
1345169689Skan
1346169689Skan  return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1347169689Skan}
1348169689Skan
1349169689Skan/* Returns true when CHREC0 == CHREC1.  */
1350169689Skan
1351169689Skanbool
1352169689Skaneq_evolutions_p (tree chrec0,
1353169689Skan		 tree chrec1)
1354169689Skan{
1355169689Skan  if (chrec0 == NULL_TREE
1356169689Skan      || chrec1 == NULL_TREE
1357169689Skan      || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1358169689Skan    return false;
1359169689Skan
1360169689Skan  if (chrec0 == chrec1)
1361169689Skan    return true;
1362169689Skan
1363169689Skan  switch (TREE_CODE (chrec0))
1364169689Skan    {
1365169689Skan    case INTEGER_CST:
1366169689Skan      return operand_equal_p (chrec0, chrec1, 0);
1367169689Skan
1368169689Skan    case POLYNOMIAL_CHREC:
1369169689Skan      return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1370169689Skan	      && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1371169689Skan	      && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1372169689Skan    default:
1373169689Skan      return false;
1374169689Skan    }
1375169689Skan}
1376169689Skan
1377169689Skan/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1378169689Skan   EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1379169689Skan   which of these cases happens.  */
1380169689Skan
1381169689Skanenum ev_direction
1382169689Skanscev_direction (tree chrec)
1383169689Skan{
1384169689Skan  tree step;
1385169689Skan
1386169689Skan  if (!evolution_function_is_affine_p (chrec))
1387169689Skan    return EV_DIR_UNKNOWN;
1388169689Skan
1389169689Skan  step = CHREC_RIGHT (chrec);
1390169689Skan  if (TREE_CODE (step) != INTEGER_CST)
1391169689Skan    return EV_DIR_UNKNOWN;
1392169689Skan
1393169689Skan  if (tree_int_cst_sign_bit (step))
1394169689Skan    return EV_DIR_DECREASES;
1395169689Skan  else
1396169689Skan    return EV_DIR_GROWS;
1397169689Skan}
1398