1/* Chains of recurrences.
2   Copyright (C) 2003-2020 Free Software Foundation, Inc.
3   Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21/* This file implements operations on chains of recurrences.  Chains
22   of recurrences are used for modeling evolution functions of scalar
23   variables.
24*/
25
26#include "config.h"
27#include "system.h"
28#include "coretypes.h"
29#include "backend.h"
30#include "tree.h"
31#include "gimple-expr.h"
32#include "tree-pretty-print.h"
33#include "fold-const.h"
34#include "cfgloop.h"
35#include "tree-ssa-loop-ivopts.h"
36#include "tree-ssa-loop-niter.h"
37#include "tree-chrec.h"
38#include "gimple.h"
39#include "tree-ssa-loop.h"
40#include "dumpfile.h"
41#include "tree-scalar-evolution.h"
42
43/* Extended folder for chrecs.  */
44
45/* Fold the addition of two polynomial functions.  */
46
47static inline tree
48chrec_fold_plus_poly_poly (enum tree_code code,
49			   tree type,
50			   tree poly0,
51			   tree poly1)
52{
53  tree left, right;
54  class loop *loop0 = get_chrec_loop (poly0);
55  class loop *loop1 = get_chrec_loop (poly1);
56  tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
57
58  gcc_assert (poly0);
59  gcc_assert (poly1);
60  gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
61  gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
62  if (POINTER_TYPE_P (chrec_type (poly0)))
63    gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
64			 && useless_type_conversion_p (type, chrec_type (poly0)));
65  else
66    gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
67			 && useless_type_conversion_p (type, chrec_type (poly1)));
68
69  /*
70    {a, +, b}_1 + {c, +, d}_2  ->  {{a, +, b}_1 + c, +, d}_2,
71    {a, +, b}_2 + {c, +, d}_1  ->  {{c, +, d}_1 + a, +, b}_2,
72    {a, +, b}_x + {c, +, d}_x  ->  {a+c, +, b+d}_x.  */
73  if (flow_loop_nested_p (loop0, loop1))
74    {
75      if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
76	return build_polynomial_chrec
77	  (CHREC_VARIABLE (poly1),
78	   chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
79	   CHREC_RIGHT (poly1));
80      else
81	return build_polynomial_chrec
82	  (CHREC_VARIABLE (poly1),
83	   chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
84	   chrec_fold_multiply (type, CHREC_RIGHT (poly1),
85				SCALAR_FLOAT_TYPE_P (type)
86				? build_real (type, dconstm1)
87				: build_int_cst_type (type, -1)));
88    }
89
90  if (flow_loop_nested_p (loop1, loop0))
91    {
92      if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
93	return build_polynomial_chrec
94	  (CHREC_VARIABLE (poly0),
95	   chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
96	   CHREC_RIGHT (poly0));
97      else
98	return build_polynomial_chrec
99	  (CHREC_VARIABLE (poly0),
100	   chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
101	   CHREC_RIGHT (poly0));
102    }
103
104  /* This function should never be called for chrecs of loops that
105     do not belong to the same loop nest.  */
106  if (loop0 != loop1)
107    {
108      /* It still can happen if we are not in loop-closed SSA form.  */
109      gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
110      return chrec_dont_know;
111    }
112
113  if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
114    {
115      left = chrec_fold_plus
116	(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
117      right = chrec_fold_plus
118	(rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
119    }
120  else
121    {
122      left = chrec_fold_minus
123	(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
124      right = chrec_fold_minus
125	(type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
126    }
127
128  if (chrec_zerop (right))
129    return left;
130  else
131    return build_polynomial_chrec
132      (CHREC_VARIABLE (poly0), left, right);
133}
134
135
136
137/* Fold the multiplication of two polynomial functions.  */
138
139static inline tree
140chrec_fold_multiply_poly_poly (tree type,
141			       tree poly0,
142			       tree poly1)
143{
144  tree t0, t1, t2;
145  int var;
146  class loop *loop0 = get_chrec_loop (poly0);
147  class loop *loop1 = get_chrec_loop (poly1);
148
149  gcc_assert (poly0);
150  gcc_assert (poly1);
151  gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
152  gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
153  gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
154		       && useless_type_conversion_p (type, chrec_type (poly1)));
155
156  /* {a, +, b}_1 * {c, +, d}_2  ->  {c*{a, +, b}_1, +, d}_2,
157     {a, +, b}_2 * {c, +, d}_1  ->  {a*{c, +, d}_1, +, b}_2,
158     {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
159  if (flow_loop_nested_p (loop0, loop1))
160    /* poly0 is a constant wrt. poly1.  */
161    return build_polynomial_chrec
162      (CHREC_VARIABLE (poly1),
163       chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
164       CHREC_RIGHT (poly1));
165
166  if (flow_loop_nested_p (loop1, loop0))
167    /* poly1 is a constant wrt. poly0.  */
168    return build_polynomial_chrec
169      (CHREC_VARIABLE (poly0),
170       chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
171       CHREC_RIGHT (poly0));
172
173  if (loop0 != loop1)
174    {
175      /* It still can happen if we are not in loop-closed SSA form.  */
176      gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
177      return chrec_dont_know;
178    }
179
180  /* poly0 and poly1 are two polynomials in the same variable,
181     {a, +, b}_x * {c, +, d}_x  ->  {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x.  */
182
183  /* "a*c".  */
184  t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
185
186  /* "a*d + b*c".  */
187  t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
188  t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
189						       CHREC_RIGHT (poly0),
190						       CHREC_LEFT (poly1)));
191  /* "b*d".  */
192  t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
193  /* "a*d + b*c + b*d".  */
194  t1 = chrec_fold_plus (type, t1, t2);
195  /* "2*b*d".  */
196  t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
197			    ? build_real (type, dconst2)
198			    : build_int_cst (type, 2), t2);
199
200  var = CHREC_VARIABLE (poly0);
201  return build_polynomial_chrec (var, t0,
202				 build_polynomial_chrec (var, t1, t2));
203}
204
205/* When the operands are automatically_generated_chrec_p, the fold has
206   to respect the semantics of the operands.  */
207
208static inline tree
209chrec_fold_automatically_generated_operands (tree op0,
210					     tree op1)
211{
212  if (op0 == chrec_dont_know
213      || op1 == chrec_dont_know)
214    return chrec_dont_know;
215
216  if (op0 == chrec_known
217      || op1 == chrec_known)
218    return chrec_known;
219
220  if (op0 == chrec_not_analyzed_yet
221      || op1 == chrec_not_analyzed_yet)
222    return chrec_not_analyzed_yet;
223
224  /* The default case produces a safe result.  */
225  return chrec_dont_know;
226}
227
228/* Fold the addition of two chrecs.  */
229
230static tree
231chrec_fold_plus_1 (enum tree_code code, tree type,
232		   tree op0, tree op1)
233{
234  if (automatically_generated_chrec_p (op0)
235      || automatically_generated_chrec_p (op1))
236    return chrec_fold_automatically_generated_operands (op0, op1);
237
238  switch (TREE_CODE (op0))
239    {
240    case POLYNOMIAL_CHREC:
241      gcc_checking_assert
242	(!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
243      switch (TREE_CODE (op1))
244	{
245	case POLYNOMIAL_CHREC:
246	  gcc_checking_assert
247	    (!chrec_contains_symbols_defined_in_loop (op1,
248						      CHREC_VARIABLE (op1)));
249	  return chrec_fold_plus_poly_poly (code, type, op0, op1);
250
251	CASE_CONVERT:
252	  {
253	    /* We can strip sign-conversions to signed by performing the
254	       operation in unsigned.  */
255	    tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
256	    if (INTEGRAL_TYPE_P (type)
257		&& INTEGRAL_TYPE_P (optype)
258		&& tree_nop_conversion_p (type, optype)
259		&& TYPE_UNSIGNED (optype))
260	      return chrec_convert (type,
261				    chrec_fold_plus_1 (code, optype,
262						       chrec_convert (optype,
263								      op0, NULL),
264						       TREE_OPERAND (op1, 0)),
265				    NULL);
266	    if (tree_contains_chrecs (op1, NULL))
267	      return chrec_dont_know;
268	  }
269	  /* FALLTHRU */
270
271	default:
272	  if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
273	    return build_polynomial_chrec
274	      (CHREC_VARIABLE (op0),
275	       chrec_fold_plus (type, CHREC_LEFT (op0), op1),
276	       CHREC_RIGHT (op0));
277	  else
278	    return build_polynomial_chrec
279	      (CHREC_VARIABLE (op0),
280	       chrec_fold_minus (type, CHREC_LEFT (op0), op1),
281	       CHREC_RIGHT (op0));
282	}
283
284    CASE_CONVERT:
285      {
286	/* We can strip sign-conversions to signed by performing the
287	   operation in unsigned.  */
288	tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
289	if (INTEGRAL_TYPE_P (type)
290	    && INTEGRAL_TYPE_P (optype)
291	    && tree_nop_conversion_p (type, optype)
292	    && TYPE_UNSIGNED (optype))
293	  return chrec_convert (type,
294				chrec_fold_plus_1 (code, optype,
295						   TREE_OPERAND (op0, 0),
296						   chrec_convert (optype,
297								  op1, NULL)),
298				NULL);
299	if (tree_contains_chrecs (op0, NULL))
300	  return chrec_dont_know;
301      }
302      /* FALLTHRU */
303
304    default:
305      switch (TREE_CODE (op1))
306	{
307	case POLYNOMIAL_CHREC:
308	  gcc_checking_assert
309	    (!chrec_contains_symbols_defined_in_loop (op1,
310						      CHREC_VARIABLE (op1)));
311	  if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
312	    return build_polynomial_chrec
313	      (CHREC_VARIABLE (op1),
314	       chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
315	       CHREC_RIGHT (op1));
316	  else
317	    return build_polynomial_chrec
318	      (CHREC_VARIABLE (op1),
319	       chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
320	       chrec_fold_multiply (type, CHREC_RIGHT (op1),
321				    SCALAR_FLOAT_TYPE_P (type)
322				    ? build_real (type, dconstm1)
323				    : build_int_cst_type (type, -1)));
324
325	CASE_CONVERT:
326	  if (tree_contains_chrecs (op1, NULL))
327	    return chrec_dont_know;
328	  /* FALLTHRU */
329
330	default:
331	  {
332	    int size = 0;
333	    if ((tree_contains_chrecs (op0, &size)
334		 || tree_contains_chrecs (op1, &size))
335		&& size < param_scev_max_expr_size)
336	      return build2 (code, type, op0, op1);
337	    else if (size < param_scev_max_expr_size)
338	      {
339		if (code == POINTER_PLUS_EXPR)
340		  return fold_build_pointer_plus (fold_convert (type, op0),
341						  op1);
342		else
343		  return fold_build2 (code, type,
344				      fold_convert (type, op0),
345				      fold_convert (type, op1));
346	      }
347	    else
348	      return chrec_dont_know;
349	  }
350	}
351    }
352}
353
354/* Fold the addition of two chrecs.  */
355
356tree
357chrec_fold_plus (tree type,
358		 tree op0,
359		 tree op1)
360{
361  enum tree_code code;
362  if (automatically_generated_chrec_p (op0)
363      || automatically_generated_chrec_p (op1))
364    return chrec_fold_automatically_generated_operands (op0, op1);
365
366  if (integer_zerop (op0))
367    return chrec_convert (type, op1, NULL);
368  if (integer_zerop (op1))
369    return chrec_convert (type, op0, NULL);
370
371  if (POINTER_TYPE_P (type))
372    code = POINTER_PLUS_EXPR;
373  else
374    code = PLUS_EXPR;
375
376  return chrec_fold_plus_1 (code, type, op0, op1);
377}
378
379/* Fold the subtraction of two chrecs.  */
380
381tree
382chrec_fold_minus (tree type,
383		  tree op0,
384		  tree op1)
385{
386  if (automatically_generated_chrec_p (op0)
387      || automatically_generated_chrec_p (op1))
388    return chrec_fold_automatically_generated_operands (op0, op1);
389
390  if (integer_zerop (op1))
391    return op0;
392
393  return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
394}
395
396/* Fold the multiplication of two chrecs.  */
397
398tree
399chrec_fold_multiply (tree type,
400		     tree op0,
401		     tree op1)
402{
403  if (automatically_generated_chrec_p (op0)
404      || automatically_generated_chrec_p (op1))
405    return chrec_fold_automatically_generated_operands (op0, op1);
406
407  switch (TREE_CODE (op0))
408    {
409    case POLYNOMIAL_CHREC:
410      gcc_checking_assert
411	(!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
412      switch (TREE_CODE (op1))
413	{
414	case POLYNOMIAL_CHREC:
415	  gcc_checking_assert
416	    (!chrec_contains_symbols_defined_in_loop (op1,
417						      CHREC_VARIABLE (op1)));
418	  return chrec_fold_multiply_poly_poly (type, op0, op1);
419
420	CASE_CONVERT:
421	  if (tree_contains_chrecs (op1, NULL))
422	    return chrec_dont_know;
423	  /* FALLTHRU */
424
425	default:
426	  if (integer_onep (op1))
427	    return op0;
428	  if (integer_zerop (op1))
429	    return build_int_cst (type, 0);
430
431	  return build_polynomial_chrec
432	    (CHREC_VARIABLE (op0),
433	     chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
434	     chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
435	}
436
437    CASE_CONVERT:
438      if (tree_contains_chrecs (op0, NULL))
439	return chrec_dont_know;
440      /* FALLTHRU */
441
442    default:
443      if (integer_onep (op0))
444	return op1;
445
446      if (integer_zerop (op0))
447    	return build_int_cst (type, 0);
448
449      switch (TREE_CODE (op1))
450	{
451	case POLYNOMIAL_CHREC:
452	  gcc_checking_assert
453	    (!chrec_contains_symbols_defined_in_loop (op1,
454						      CHREC_VARIABLE (op1)));
455	  return build_polynomial_chrec
456	    (CHREC_VARIABLE (op1),
457	     chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
458	     chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
459
460	CASE_CONVERT:
461	  if (tree_contains_chrecs (op1, NULL))
462	    return chrec_dont_know;
463	  /* FALLTHRU */
464
465	default:
466	  if (integer_onep (op1))
467	    return op0;
468	  if (integer_zerop (op1))
469	    return build_int_cst (type, 0);
470	  return fold_build2 (MULT_EXPR, type, op0, op1);
471	}
472    }
473}
474
475
476
477/* Operations.  */
478
479/* Evaluate the binomial coefficient.  Return NULL_TREE if the intermediate
480   calculation overflows, otherwise return C(n,k) with type TYPE.  */
481
482static tree
483tree_fold_binomial (tree type, tree n, unsigned int k)
484{
485  wi::overflow_type overflow;
486  unsigned int i;
487
488  /* Handle the most frequent cases.  */
489  if (k == 0)
490    return build_int_cst (type, 1);
491  if (k == 1)
492    return fold_convert (type, n);
493
494  widest_int num = wi::to_widest (n);
495
496  /* Check that k <= n.  */
497  if (wi::ltu_p (num, k))
498    return NULL_TREE;
499
500  /* Denominator = 2.  */
501  widest_int denom = 2;
502
503  /* Index = Numerator-1.  */
504  widest_int idx = num - 1;
505
506  /* Numerator = Numerator*Index = n*(n-1).  */
507  num = wi::smul (num, idx, &overflow);
508  if (overflow)
509    return NULL_TREE;
510
511  for (i = 3; i <= k; i++)
512    {
513      /* Index--.  */
514      --idx;
515
516      /* Numerator *= Index.  */
517      num = wi::smul (num, idx, &overflow);
518      if (overflow)
519	return NULL_TREE;
520
521      /* Denominator *= i.  */
522      denom *= i;
523    }
524
525  /* Result = Numerator / Denominator.  */
526  num = wi::udiv_trunc (num, denom);
527  if (! wi::fits_to_tree_p (num, type))
528    return NULL_TREE;
529  return wide_int_to_tree (type, num);
530}
531
532/* Helper function.  Use the Newton's interpolating formula for
533   evaluating the value of the evolution function.
534   The result may be in an unsigned type of CHREC.  */
535
536static tree
537chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
538{
539  tree arg0, arg1, binomial_n_k;
540  tree type = TREE_TYPE (chrec);
541  class loop *var_loop = get_loop (cfun, var);
542
543  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
544	 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
545    chrec = CHREC_LEFT (chrec);
546
547  /* The formula associates the expression and thus we have to make
548     sure to not introduce undefined overflow.  */
549  tree ctype = type;
550  if (INTEGRAL_TYPE_P (type)
551      && ! TYPE_OVERFLOW_WRAPS (type))
552    ctype = unsigned_type_for (type);
553
554  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
555      && CHREC_VARIABLE (chrec) == var)
556    {
557      arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
558      if (arg1 == chrec_dont_know)
559	return chrec_dont_know;
560      binomial_n_k = tree_fold_binomial (ctype, n, k);
561      if (!binomial_n_k)
562	return chrec_dont_know;
563      tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
564      arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
565      return chrec_fold_plus (ctype, arg0, arg1);
566    }
567
568  binomial_n_k = tree_fold_binomial (ctype, n, k);
569  if (!binomial_n_k)
570    return chrec_dont_know;
571
572  return fold_build2 (MULT_EXPR, ctype,
573		      chrec_convert (ctype, chrec, NULL), binomial_n_k);
574}
575
576/* Evaluates "CHREC (X)" when the varying variable is VAR.
577   Example:  Given the following parameters,
578
579   var = 1
580   chrec = {3, +, 4}_1
581   x = 10
582
583   The result is given by the Newton's interpolating formula:
584   3 * \binom{10}{0} + 4 * \binom{10}{1}.
585*/
586
587tree
588chrec_apply (unsigned var,
589	     tree chrec,
590	     tree x)
591{
592  tree type = chrec_type (chrec);
593  tree res = chrec_dont_know;
594
595  if (automatically_generated_chrec_p (chrec)
596      || automatically_generated_chrec_p (x)
597
598      /* When the symbols are defined in an outer loop, it is possible
599	 to symbolically compute the apply, since the symbols are
600	 constants with respect to the varying loop.  */
601      || chrec_contains_symbols_defined_in_loop (chrec, var))
602    return chrec_dont_know;
603
604  if (dump_file && (dump_flags & TDF_SCEV))
605    fprintf (dump_file, "(chrec_apply \n");
606
607  if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
608    x = build_real_from_int_cst (type, x);
609
610  switch (TREE_CODE (chrec))
611    {
612    case POLYNOMIAL_CHREC:
613      if (evolution_function_is_affine_p (chrec))
614	{
615	  if (CHREC_VARIABLE (chrec) != var)
616	    return build_polynomial_chrec
617	      (CHREC_VARIABLE (chrec),
618	       chrec_apply (var, CHREC_LEFT (chrec), x),
619	       chrec_apply (var, CHREC_RIGHT (chrec), x));
620
621	  /* "{a, +, b} (x)"  ->  "a + b*x".  */
622	  x = chrec_convert_rhs (type, x, NULL);
623	  res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
624	  res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
625	}
626      else if (TREE_CODE (x) == INTEGER_CST
627	       && tree_int_cst_sgn (x) == 1)
628	/* testsuite/.../ssa-chrec-38.c.  */
629	res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
630      else
631	res = chrec_dont_know;
632      break;
633
634    CASE_CONVERT:
635      res = chrec_convert (TREE_TYPE (chrec),
636			   chrec_apply (var, TREE_OPERAND (chrec, 0), x),
637			   NULL);
638      break;
639
640    default:
641      res = chrec;
642      break;
643    }
644
645  if (dump_file && (dump_flags & TDF_SCEV))
646    {
647      fprintf (dump_file, "  (varying_loop = %d\n", var);
648      fprintf (dump_file, ")\n  (chrec = ");
649      print_generic_expr (dump_file, chrec);
650      fprintf (dump_file, ")\n  (x = ");
651      print_generic_expr (dump_file, x);
652      fprintf (dump_file, ")\n  (res = ");
653      print_generic_expr (dump_file, res);
654      fprintf (dump_file, "))\n");
655    }
656
657  return res;
658}
659
660/* For a given CHREC and an induction variable map IV_MAP that maps
661   (loop->num, expr) for every loop number of the current_loops an
662   expression, calls chrec_apply when the expression is not NULL.  */
663
664tree
665chrec_apply_map (tree chrec, vec<tree> iv_map)
666{
667  int i;
668  tree expr;
669
670  FOR_EACH_VEC_ELT (iv_map, i, expr)
671    if (expr)
672      chrec = chrec_apply (i, chrec, expr);
673
674  return chrec;
675}
676
677/* Replaces the initial condition in CHREC with INIT_COND.  */
678
679tree
680chrec_replace_initial_condition (tree chrec,
681				 tree init_cond)
682{
683  if (automatically_generated_chrec_p (chrec))
684    return chrec;
685
686  gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
687
688  switch (TREE_CODE (chrec))
689    {
690    case POLYNOMIAL_CHREC:
691      return build_polynomial_chrec
692	(CHREC_VARIABLE (chrec),
693	 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
694	 CHREC_RIGHT (chrec));
695
696    default:
697      return init_cond;
698    }
699}
700
701/* Returns the initial condition of a given CHREC.  */
702
703tree
704initial_condition (tree chrec)
705{
706  if (automatically_generated_chrec_p (chrec))
707    return chrec;
708
709  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
710    return initial_condition (CHREC_LEFT (chrec));
711  else
712    return chrec;
713}
714
715/* Returns a univariate function that represents the evolution in
716   LOOP_NUM.  Mask the evolution of any other loop.  */
717
718tree
719hide_evolution_in_other_loops_than_loop (tree chrec,
720					 unsigned loop_num)
721{
722  class loop *loop = get_loop (cfun, loop_num), *chloop;
723  if (automatically_generated_chrec_p (chrec))
724    return chrec;
725
726  switch (TREE_CODE (chrec))
727    {
728    case POLYNOMIAL_CHREC:
729      chloop = get_chrec_loop (chrec);
730
731      if (chloop == loop)
732	return build_polynomial_chrec
733	  (loop_num,
734	   hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
735						    loop_num),
736	   CHREC_RIGHT (chrec));
737
738      else if (flow_loop_nested_p (chloop, loop))
739	/* There is no evolution in this loop.  */
740	return initial_condition (chrec);
741
742      else if (flow_loop_nested_p (loop, chloop))
743	return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
744							loop_num);
745
746      else
747	return chrec_dont_know;
748
749    default:
750      return chrec;
751    }
752}
753
754/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
755   true, otherwise returns the initial condition in LOOP_NUM.  */
756
757static tree
758chrec_component_in_loop_num (tree chrec,
759			     unsigned loop_num,
760			     bool right)
761{
762  tree component;
763  class loop *loop = get_loop (cfun, loop_num), *chloop;
764
765  if (automatically_generated_chrec_p (chrec))
766    return chrec;
767
768  switch (TREE_CODE (chrec))
769    {
770    case POLYNOMIAL_CHREC:
771      chloop = get_chrec_loop (chrec);
772
773      if (chloop == loop)
774	{
775	  if (right)
776	    component = CHREC_RIGHT (chrec);
777	  else
778	    component = CHREC_LEFT (chrec);
779
780	  if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
781	      || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
782	    return component;
783
784	  else
785	    return build_polynomial_chrec
786	      (loop_num,
787	       chrec_component_in_loop_num (CHREC_LEFT (chrec),
788					    loop_num,
789					    right),
790	       component);
791	}
792
793      else if (flow_loop_nested_p (chloop, loop))
794	/* There is no evolution part in this loop.  */
795	return NULL_TREE;
796
797      else
798	{
799	  gcc_assert (flow_loop_nested_p (loop, chloop));
800	  return chrec_component_in_loop_num (CHREC_LEFT (chrec),
801					      loop_num,
802					      right);
803	}
804
805     default:
806      if (right)
807	return NULL_TREE;
808      else
809	return chrec;
810    }
811}
812
813/* Returns the evolution part in LOOP_NUM.  Example: the call
814   evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
815   {1, +, 2}_1  */
816
817tree
818evolution_part_in_loop_num (tree chrec,
819			    unsigned loop_num)
820{
821  return chrec_component_in_loop_num (chrec, loop_num, true);
822}
823
824/* Returns the initial condition in LOOP_NUM.  Example: the call
825   initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
826   {0, +, 1}_1  */
827
828tree
829initial_condition_in_loop_num (tree chrec,
830			       unsigned loop_num)
831{
832  return chrec_component_in_loop_num (chrec, loop_num, false);
833}
834
835/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
836   This function is essentially used for setting the evolution to
837   chrec_dont_know, for example after having determined that it is
838   impossible to say how many times a loop will execute.  */
839
840tree
841reset_evolution_in_loop (unsigned loop_num,
842			 tree chrec,
843			 tree new_evol)
844{
845  class loop *loop = get_loop (cfun, loop_num);
846
847  if (POINTER_TYPE_P (chrec_type (chrec)))
848    gcc_assert (ptrofftype_p (chrec_type (new_evol)));
849  else
850    gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
851
852  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
853      && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
854    {
855      tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
856					   new_evol);
857      tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
858					    new_evol);
859      return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
860    }
861
862  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
863	 && CHREC_VARIABLE (chrec) == loop_num)
864    chrec = CHREC_LEFT (chrec);
865
866  return build_polynomial_chrec (loop_num, chrec, new_evol);
867}
868
869/* Merges two evolution functions that were found by following two
870   alternate paths of a conditional expression.  */
871
872tree
873chrec_merge (tree chrec1,
874	     tree chrec2)
875{
876  if (chrec1 == chrec_dont_know
877      || chrec2 == chrec_dont_know)
878    return chrec_dont_know;
879
880  if (chrec1 == chrec_known
881      || chrec2 == chrec_known)
882    return chrec_known;
883
884  if (chrec1 == chrec_not_analyzed_yet)
885    return chrec2;
886  if (chrec2 == chrec_not_analyzed_yet)
887    return chrec1;
888
889  if (eq_evolutions_p (chrec1, chrec2))
890    return chrec1;
891
892  return chrec_dont_know;
893}
894
895
896
897/* Observers.  */
898
899/* Helper function for is_multivariate_chrec.  */
900
901static bool
902is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
903{
904  if (chrec == NULL_TREE)
905    return false;
906
907  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
908    {
909      if (CHREC_VARIABLE (chrec) != rec_var)
910	return true;
911      else
912	return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
913		|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
914    }
915  else
916    return false;
917}
918
919/* Determine whether the given chrec is multivariate or not.  */
920
921bool
922is_multivariate_chrec (const_tree chrec)
923{
924  if (chrec == NULL_TREE)
925    return false;
926
927  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
928    return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
929				       CHREC_VARIABLE (chrec))
930	    || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
931					  CHREC_VARIABLE (chrec)));
932  else
933    return false;
934}
935
936/* Determines whether the chrec contains symbolic names or not.  If LOOP isn't
937   NULL, we also consider chrec wrto outer loops of LOOP as symbol.  */
938
939static bool
940chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
941			class loop *loop)
942{
943  int i, n;
944
945  if (chrec == NULL_TREE)
946    return false;
947
948  if (TREE_CODE (chrec) == SSA_NAME
949      || VAR_P (chrec)
950      || TREE_CODE (chrec) == POLY_INT_CST
951      || TREE_CODE (chrec) == PARM_DECL
952      || TREE_CODE (chrec) == FUNCTION_DECL
953      || TREE_CODE (chrec) == LABEL_DECL
954      || TREE_CODE (chrec) == RESULT_DECL
955      || TREE_CODE (chrec) == FIELD_DECL)
956    return true;
957
958  if (loop != NULL
959      && TREE_CODE (chrec) == POLYNOMIAL_CHREC
960      && flow_loop_nested_p (get_chrec_loop (chrec), loop))
961    return true;
962
963  if (visited.add (chrec))
964    return false;
965
966  n = TREE_OPERAND_LENGTH (chrec);
967  for (i = 0; i < n; i++)
968    if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
969      return true;
970  return false;
971}
972
973/* Return true if CHREC contains any symbols.  If LOOP is not NULL, check if
974   CHREC contains any chrec which is invariant wrto the loop (nest), in other
975   words, chrec defined by outer loops of loop, so from LOOP's point of view,
976   the chrec is considered as a SYMBOL.  */
977
978bool
979chrec_contains_symbols (const_tree chrec, class loop* loop)
980{
981  hash_set<const_tree> visited;
982  return chrec_contains_symbols (chrec, visited, loop);
983}
984
985/* Return true when CHREC contains symbolic names defined in
986   LOOP_NB.  */
987
988static bool
989chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
990					hash_set<const_tree> &visited)
991{
992  int i, n;
993
994  if (chrec == NULL_TREE)
995    return false;
996
997  if (is_gimple_min_invariant (chrec))
998    return false;
999
1000  if (TREE_CODE (chrec) == SSA_NAME)
1001    {
1002      gimple *def;
1003      loop_p def_loop, loop;
1004
1005      if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1006	return false;
1007
1008      def = SSA_NAME_DEF_STMT (chrec);
1009      def_loop = loop_containing_stmt (def);
1010      loop = get_loop (cfun, loop_nb);
1011
1012      if (def_loop == NULL)
1013	return false;
1014
1015      if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1016	return true;
1017
1018      return false;
1019    }
1020
1021  if (visited.add (chrec))
1022    return false;
1023
1024  n = TREE_OPERAND_LENGTH (chrec);
1025  for (i = 0; i < n; i++)
1026    if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1027						loop_nb, visited))
1028      return true;
1029  return false;
1030}
1031
1032/* Return true when CHREC contains symbolic names defined in
1033   LOOP_NB.  */
1034
1035bool
1036chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1037{
1038  hash_set<const_tree> visited;
1039  return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1040}
1041
1042/* Determines whether the chrec contains undetermined coefficients.  */
1043
1044static bool
1045chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1046{
1047  int i, n;
1048
1049  if (chrec == chrec_dont_know)
1050    return true;
1051
1052  if (chrec == NULL_TREE)
1053    return false;
1054
1055  if (visited.add (chrec))
1056    return false;
1057
1058  n = TREE_OPERAND_LENGTH (chrec);
1059  for (i = 0; i < n; i++)
1060    if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1061      return true;
1062  return false;
1063}
1064
1065bool
1066chrec_contains_undetermined (const_tree chrec)
1067{
1068  hash_set<const_tree> visited;
1069  return chrec_contains_undetermined (chrec, visited);
1070}
1071
1072/* Determines whether the tree EXPR contains chrecs, and increment
1073   SIZE if it is not a NULL pointer by an estimation of the depth of
1074   the tree.  */
1075
1076static bool
1077tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1078{
1079  int i, n;
1080
1081  if (expr == NULL_TREE)
1082    return false;
1083
1084  if (size)
1085    (*size)++;
1086
1087  if (tree_is_chrec (expr))
1088    return true;
1089
1090  if (visited.add (expr))
1091    return false;
1092
1093  n = TREE_OPERAND_LENGTH (expr);
1094  for (i = 0; i < n; i++)
1095    if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1096      return true;
1097  return false;
1098}
1099
1100bool
1101tree_contains_chrecs (const_tree expr, int *size)
1102{
1103  hash_set<const_tree> visited;
1104  return tree_contains_chrecs (expr, size, visited);
1105}
1106
1107
1108/* Recursive helper function.  */
1109
1110static bool
1111evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1112{
1113  if (evolution_function_is_constant_p (chrec))
1114    return true;
1115
1116  if (TREE_CODE (chrec) == SSA_NAME
1117      && (loopnum == 0
1118	  || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
1119    return true;
1120
1121  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1122    {
1123      if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1124	  || flow_loop_nested_p (get_loop (cfun, loopnum),
1125				 get_chrec_loop (chrec))
1126	  || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1127						     loopnum)
1128	  || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1129						     loopnum))
1130	return false;
1131      return true;
1132    }
1133
1134  switch (TREE_OPERAND_LENGTH (chrec))
1135    {
1136    case 2:
1137      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1138						  loopnum))
1139	return false;
1140      /* FALLTHRU */
1141
1142    case 1:
1143      if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1144						  loopnum))
1145	return false;
1146      return true;
1147
1148    default:
1149      return false;
1150    }
1151
1152  return false;
1153}
1154
1155/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1156
1157bool
1158evolution_function_is_invariant_p (tree chrec, int loopnum)
1159{
1160  return evolution_function_is_invariant_rec_p (chrec, loopnum);
1161}
1162
1163/* Determine whether the given tree is an affine multivariate
1164   evolution.  */
1165
1166bool
1167evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1168{
1169  if (chrec == NULL_TREE)
1170    return false;
1171
1172  switch (TREE_CODE (chrec))
1173    {
1174    case POLYNOMIAL_CHREC:
1175      if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1176	{
1177	  if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1178	    return true;
1179	  else
1180	    {
1181	      if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1182		  && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1183		     != CHREC_VARIABLE (chrec)
1184		  && evolution_function_is_affine_multivariate_p
1185		  (CHREC_RIGHT (chrec), loopnum))
1186		return true;
1187	      else
1188		return false;
1189	    }
1190	}
1191      else
1192	{
1193	  if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1194	      && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1195	      && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1196	      && evolution_function_is_affine_multivariate_p
1197	      (CHREC_LEFT (chrec), loopnum))
1198	    return true;
1199	  else
1200	    return false;
1201	}
1202
1203    default:
1204      return false;
1205    }
1206}
1207
1208/* Determine whether the given tree is a function in zero or one
1209   variables with respect to loop specified by LOOPNUM.  Note only positive
1210   LOOPNUM stands for a real loop.  */
1211
1212bool
1213evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1214{
1215  if (chrec == NULL_TREE)
1216    return true;
1217
1218  tree sub_chrec;
1219  switch (TREE_CODE (chrec))
1220    {
1221    case POLYNOMIAL_CHREC:
1222      switch (TREE_CODE (CHREC_LEFT (chrec)))
1223	{
1224	case POLYNOMIAL_CHREC:
1225	  sub_chrec = CHREC_LEFT (chrec);
1226	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1227	      && (loopnum <= 0
1228		  || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1229		  || flow_loop_nested_p (get_loop (cfun, loopnum),
1230					 get_chrec_loop (sub_chrec))))
1231	    return false;
1232	  if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1233	    return false;
1234	  break;
1235
1236	default:
1237	  if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1238	    return false;
1239	  break;
1240	}
1241
1242      switch (TREE_CODE (CHREC_RIGHT (chrec)))
1243	{
1244	case POLYNOMIAL_CHREC:
1245	  sub_chrec = CHREC_RIGHT (chrec);
1246	  if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1247	      && (loopnum <= 0
1248		  || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1249		  || flow_loop_nested_p (get_loop (cfun, loopnum),
1250					 get_chrec_loop (sub_chrec))))
1251	    return false;
1252	  if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1253	    return false;
1254	  break;
1255
1256	default:
1257	  if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1258	    return false;
1259	  break;
1260	}
1261      return true;
1262
1263    default:
1264      return true;
1265    }
1266}
1267
1268/* Returns the number of variables of CHREC.  Example: the call
1269   nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
1270
1271unsigned
1272nb_vars_in_chrec (tree chrec)
1273{
1274  if (chrec == NULL_TREE)
1275    return 0;
1276
1277  switch (TREE_CODE (chrec))
1278    {
1279    case POLYNOMIAL_CHREC:
1280      return 1 + nb_vars_in_chrec
1281	(initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1282
1283    default:
1284      return 0;
1285    }
1286}
1287
1288/* Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
1289   the scev corresponds to.  AT_STMT is the statement at that the scev is
1290   evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume
1291   that the rules for overflow of the given language apply (e.g., that signed
1292   arithmetics in C does not overflow) -- i.e., to use them to avoid
1293   unnecessary tests, but also to enforce that the result follows them.
1294   FROM is the source variable converted if it's not NULL.  Returns true if
1295   the conversion succeeded, false otherwise.  */
1296
1297bool
1298convert_affine_scev (class loop *loop, tree type,
1299		     tree *base, tree *step, gimple *at_stmt,
1300		     bool use_overflow_semantics, tree from)
1301{
1302  tree ct = TREE_TYPE (*step);
1303  bool enforce_overflow_semantics;
1304  bool must_check_src_overflow, must_check_rslt_overflow;
1305  tree new_base, new_step;
1306  tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1307
1308  /* In general,
1309     (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1310     but we must check some assumptions.
1311
1312     1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1313        of CT is smaller than the precision of TYPE.  For example, when we
1314	cast unsigned char [254, +, 1] to unsigned, the values on left side
1315	are 254, 255, 0, 1, ..., but those on the right side are
1316	254, 255, 256, 257, ...
1317     2) In case that we must also preserve the fact that signed ivs do not
1318        overflow, we must additionally check that the new iv does not wrap.
1319	For example, unsigned char [125, +, 1] casted to signed char could
1320	become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1321	which would confuse optimizers that assume that this does not
1322	happen.  */
1323  must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1324
1325  enforce_overflow_semantics = (use_overflow_semantics
1326				&& nowrap_type_p (type));
1327  if (enforce_overflow_semantics)
1328    {
1329      /* We can avoid checking whether the result overflows in the following
1330	 cases:
1331
1332	 -- must_check_src_overflow is true, and the range of TYPE is superset
1333	    of the range of CT -- i.e., in all cases except if CT signed and
1334	    TYPE unsigned.
1335         -- both CT and TYPE have the same precision and signedness, and we
1336	    verify instead that the source does not overflow (this may be
1337	    easier than verifying it for the result, as we may use the
1338	    information about the semantics of overflow in CT).  */
1339      if (must_check_src_overflow)
1340	{
1341	  if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1342	    must_check_rslt_overflow = true;
1343	  else
1344	    must_check_rslt_overflow = false;
1345	}
1346      else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1347	       && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1348	{
1349	  must_check_rslt_overflow = false;
1350	  must_check_src_overflow = true;
1351	}
1352      else
1353	must_check_rslt_overflow = true;
1354    }
1355  else
1356    must_check_rslt_overflow = false;
1357
1358  if (must_check_src_overflow
1359      && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1360				use_overflow_semantics))
1361    return false;
1362
1363  new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1364  /* The step must be sign extended, regardless of the signedness
1365     of CT and TYPE.  This only needs to be handled specially when
1366     CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1367     (with values 100, 99, 98, ...) from becoming signed or unsigned
1368     [100, +, 255] with values 100, 355, ...; the sign-extension is
1369     performed by default when CT is signed.  */
1370  new_step = *step;
1371  if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1372    {
1373      tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1374      new_step = chrec_convert (signed_ct, new_step, at_stmt,
1375                                use_overflow_semantics);
1376    }
1377  new_step = chrec_convert (step_type, new_step, at_stmt,
1378			    use_overflow_semantics);
1379
1380  if (automatically_generated_chrec_p (new_base)
1381      || automatically_generated_chrec_p (new_step))
1382    return false;
1383
1384  if (must_check_rslt_overflow
1385      /* Note that in this case we cannot use the fact that signed variables
1386	 do not overflow, as this is what we are verifying for the new iv.  */
1387      && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1388				at_stmt, loop, false))
1389    return false;
1390
1391  *base = new_base;
1392  *step = new_step;
1393  return true;
1394}
1395
1396
1397/* Convert CHREC for the right hand side of a CHREC.
1398   The increment for a pointer type is always sizetype.  */
1399
1400tree
1401chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1402{
1403  if (POINTER_TYPE_P (type))
1404    type = sizetype;
1405
1406  return chrec_convert (type, chrec, at_stmt);
1407}
1408
1409/* Convert CHREC to TYPE.  When the analyzer knows the context in
1410   which the CHREC is built, it sets AT_STMT to the statement that
1411   contains the definition of the analyzed variable, otherwise the
1412   conversion is less accurate: the information is used for
1413   determining a more accurate estimation of the number of iterations.
1414   By default AT_STMT could be safely set to NULL_TREE.
1415
1416   USE_OVERFLOW_SEMANTICS is true if this function should assume that
1417   the rules for overflow of the given language apply (e.g., that signed
1418   arithmetics in C does not overflow) -- i.e., to use them to avoid
1419   unnecessary tests, but also to enforce that the result follows them.
1420
1421   FROM is the source variable converted if it's not NULL.  */
1422
1423static tree
1424chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1425		 bool use_overflow_semantics, tree from)
1426{
1427  tree ct, res;
1428  tree base, step;
1429  class loop *loop;
1430
1431  if (automatically_generated_chrec_p (chrec))
1432    return chrec;
1433
1434  ct = chrec_type (chrec);
1435  if (useless_type_conversion_p (type, ct))
1436    return chrec;
1437
1438  if (!evolution_function_is_affine_p (chrec))
1439    goto keep_cast;
1440
1441  loop = get_chrec_loop (chrec);
1442  base = CHREC_LEFT (chrec);
1443  step = CHREC_RIGHT (chrec);
1444
1445  if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1446			   use_overflow_semantics, from))
1447    return build_polynomial_chrec (loop->num, base, step);
1448
1449  /* If we cannot propagate the cast inside the chrec, just keep the cast.  */
1450keep_cast:
1451  /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1452     may be more expensive.  We do want to perform this optimization here
1453     though for canonicalization reasons.  */
1454  if (use_overflow_semantics
1455      && (TREE_CODE (chrec) == PLUS_EXPR
1456	  || TREE_CODE (chrec) == MINUS_EXPR)
1457      && TREE_CODE (type) == INTEGER_TYPE
1458      && TREE_CODE (ct) == INTEGER_TYPE
1459      && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1460      && TYPE_OVERFLOW_UNDEFINED (ct))
1461    res = fold_build2 (TREE_CODE (chrec), type,
1462		       fold_convert (type, TREE_OPERAND (chrec, 0)),
1463		       fold_convert (type, TREE_OPERAND (chrec, 1)));
1464  /* Similar perform the trick that (signed char)((int)x + 2) can be
1465     narrowed to (signed char)((unsigned char)x + 2).  */
1466  else if (use_overflow_semantics
1467	   && TREE_CODE (chrec) == POLYNOMIAL_CHREC
1468	   && TREE_CODE (ct) == INTEGER_TYPE
1469	   && TREE_CODE (type) == INTEGER_TYPE
1470	   && TYPE_OVERFLOW_UNDEFINED (type)
1471	   && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1472    {
1473      tree utype = unsigned_type_for (type);
1474      res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1475				    fold_convert (utype,
1476						  CHREC_LEFT (chrec)),
1477				    fold_convert (utype,
1478						  CHREC_RIGHT (chrec)));
1479      res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1480    }
1481  else
1482    res = fold_convert (type, chrec);
1483
1484  /* Don't propagate overflows.  */
1485  if (CONSTANT_CLASS_P (res))
1486    TREE_OVERFLOW (res) = 0;
1487
1488  /* But reject constants that don't fit in their type after conversion.
1489     This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1490     natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1491     and can cause problems later when computing niters of loops.  Note
1492     that we don't do the check before converting because we don't want
1493     to reject conversions of negative chrecs to unsigned types.  */
1494  if (TREE_CODE (res) == INTEGER_CST
1495      && TREE_CODE (type) == INTEGER_TYPE
1496      && !int_fits_type_p (res, type))
1497    res = chrec_dont_know;
1498
1499  return res;
1500}
1501
1502/* Convert CHREC to TYPE.  When the analyzer knows the context in
1503   which the CHREC is built, it sets AT_STMT to the statement that
1504   contains the definition of the analyzed variable, otherwise the
1505   conversion is less accurate: the information is used for
1506   determining a more accurate estimation of the number of iterations.
1507   By default AT_STMT could be safely set to NULL_TREE.
1508
1509   The following rule is always true: TREE_TYPE (chrec) ==
1510   TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1511   An example of what could happen when adding two chrecs and the type
1512   of the CHREC_RIGHT is different than CHREC_LEFT is:
1513
1514   {(uint) 0, +, (uchar) 10} +
1515   {(uint) 0, +, (uchar) 250}
1516
1517   that would produce a wrong result if CHREC_RIGHT is not (uint):
1518
1519   {(uint) 0, +, (uchar) 4}
1520
1521   instead of
1522
1523   {(uint) 0, +, (uint) 260}
1524
1525   USE_OVERFLOW_SEMANTICS is true if this function should assume that
1526   the rules for overflow of the given language apply (e.g., that signed
1527   arithmetics in C does not overflow) -- i.e., to use them to avoid
1528   unnecessary tests, but also to enforce that the result follows them.
1529
1530   FROM is the source variable converted if it's not NULL.  */
1531
1532tree
1533chrec_convert (tree type, tree chrec, gimple *at_stmt,
1534	       bool use_overflow_semantics, tree from)
1535{
1536  return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1537}
1538
1539/* Convert CHREC to TYPE, without regard to signed overflows.  Returns the new
1540   chrec if something else than what chrec_convert would do happens, NULL_TREE
1541   otherwise.  This function set TRUE to variable pointed by FOLD_CONVERSIONS
1542   if the result chrec may overflow.  */
1543
1544tree
1545chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1546{
1547  tree inner_type, left, right, lc, rc, rtype;
1548
1549  gcc_assert (fold_conversions != NULL);
1550
1551  if (automatically_generated_chrec_p (chrec)
1552      || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1553    return NULL_TREE;
1554
1555  inner_type = TREE_TYPE (chrec);
1556  if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1557    return NULL_TREE;
1558
1559  if (useless_type_conversion_p (type, inner_type))
1560    return NULL_TREE;
1561
1562  if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1563    {
1564      tree base, step;
1565      class loop *loop;
1566
1567      loop = get_chrec_loop (chrec);
1568      base = CHREC_LEFT (chrec);
1569      step = CHREC_RIGHT (chrec);
1570      if (convert_affine_scev (loop, type, &base, &step, NULL, true))
1571	return build_polynomial_chrec (loop->num, base, step);
1572    }
1573  rtype = POINTER_TYPE_P (type) ? sizetype : type;
1574
1575  left = CHREC_LEFT (chrec);
1576  right = CHREC_RIGHT (chrec);
1577  lc = chrec_convert_aggressive (type, left, fold_conversions);
1578  if (!lc)
1579    lc = chrec_convert (type, left, NULL);
1580  rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1581  if (!rc)
1582    rc = chrec_convert (rtype, right, NULL);
1583
1584  *fold_conversions = true;
1585
1586  return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1587}
1588
1589/* Returns true when CHREC0 == CHREC1.  */
1590
1591bool
1592eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1593{
1594  if (chrec0 == NULL_TREE
1595      || chrec1 == NULL_TREE
1596      || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1597    return false;
1598
1599  if (chrec0 == chrec1)
1600    return true;
1601
1602  if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1603    return false;
1604
1605  switch (TREE_CODE (chrec0))
1606    {
1607    case POLYNOMIAL_CHREC:
1608      return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1609	      && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1610	      && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1611
1612    case PLUS_EXPR:
1613    case MULT_EXPR:
1614    case MINUS_EXPR:
1615    case POINTER_PLUS_EXPR:
1616      return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1617			      TREE_OPERAND (chrec1, 0))
1618	  && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1619			      TREE_OPERAND (chrec1, 1));
1620
1621    CASE_CONVERT:
1622      return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1623			      TREE_OPERAND (chrec1, 0));
1624
1625    default:
1626      return operand_equal_p (chrec0, chrec1, 0);
1627    }
1628}
1629
1630/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1631   EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1632   which of these cases happens.  */
1633
1634enum ev_direction
1635scev_direction (const_tree chrec)
1636{
1637  const_tree step;
1638
1639  if (!evolution_function_is_affine_p (chrec))
1640    return EV_DIR_UNKNOWN;
1641
1642  step = CHREC_RIGHT (chrec);
1643  if (TREE_CODE (step) != INTEGER_CST)
1644    return EV_DIR_UNKNOWN;
1645
1646  if (tree_int_cst_sign_bit (step))
1647    return EV_DIR_DECREASES;
1648  else
1649    return EV_DIR_GROWS;
1650}
1651
1652/* Iterates over all the components of SCEV, and calls CBCK.  */
1653
1654void
1655for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1656{
1657  switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1658    {
1659    case 3:
1660      for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1661      /* FALLTHRU */
1662
1663    case 2:
1664      for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1665      /* FALLTHRU */
1666
1667    case 1:
1668      for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1669      /* FALLTHRU */
1670
1671    default:
1672      cbck (scev, data);
1673      break;
1674    }
1675}
1676
1677/* Returns true when the operation can be part of a linear
1678   expression.  */
1679
1680static inline bool
1681operator_is_linear (tree scev)
1682{
1683  switch (TREE_CODE (scev))
1684    {
1685    case INTEGER_CST:
1686    case POLYNOMIAL_CHREC:
1687    case PLUS_EXPR:
1688    case POINTER_PLUS_EXPR:
1689    case MULT_EXPR:
1690    case MINUS_EXPR:
1691    case NEGATE_EXPR:
1692    case SSA_NAME:
1693    case NON_LVALUE_EXPR:
1694    case BIT_NOT_EXPR:
1695    CASE_CONVERT:
1696      return true;
1697
1698    default:
1699      return false;
1700    }
1701}
1702
1703/* Return true when SCEV is a linear expression.  Linear expressions
1704   can contain additions, substractions and multiplications.
1705   Multiplications are restricted to constant scaling: "cst * x".  */
1706
1707bool
1708scev_is_linear_expression (tree scev)
1709{
1710  if (evolution_function_is_constant_p (scev))
1711    return true;
1712
1713  if (scev == NULL
1714      || !operator_is_linear (scev))
1715    return false;
1716
1717  if (TREE_CODE (scev) == MULT_EXPR)
1718    return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1719	     && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1720
1721  if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1722      && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1723    return false;
1724
1725  switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1726    {
1727    case 3:
1728      return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1729	&& scev_is_linear_expression (TREE_OPERAND (scev, 1))
1730	&& scev_is_linear_expression (TREE_OPERAND (scev, 2));
1731
1732    case 2:
1733      return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1734	&& scev_is_linear_expression (TREE_OPERAND (scev, 1));
1735
1736    case 1:
1737      return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1738
1739    case 0:
1740      return true;
1741
1742    default:
1743      return false;
1744    }
1745}
1746
1747/* Determines whether the expression CHREC contains only interger consts
1748   in the right parts.  */
1749
1750bool
1751evolution_function_right_is_integer_cst (const_tree chrec)
1752{
1753  if (chrec == NULL_TREE)
1754    return false;
1755
1756  switch (TREE_CODE (chrec))
1757    {
1758    case INTEGER_CST:
1759      return true;
1760
1761    case POLYNOMIAL_CHREC:
1762      return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1763	&& (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1764	    || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1765
1766    CASE_CONVERT:
1767      return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1768
1769    default:
1770      return false;
1771    }
1772}
1773