1	/* Chains of recurrences.
2	Copyright (C) 2003-2023 Free Software Foundation, Inc.
3	Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	/* 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
47	static inline tree
48	chrec_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 (chrec: poly0);
55	class loop *loop1 = get_chrec_loop (chrec: poly1);
56	tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (chrec: 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	left: chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
79	CHREC_RIGHT (poly1));
80	else
81	return build_polynomial_chrec
82	(CHREC_VARIABLE (poly1),
83	left: chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
84	right: 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	left: chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
96	CHREC_RIGHT (poly0));
97	else
98	return build_polynomial_chrec
99	(CHREC_VARIABLE (poly0),
100	left: 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 (chrec: 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
139	static inline tree
140	chrec_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 (chrec: poly0);
147	class loop *loop1 = get_chrec_loop (chrec: 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	left: 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	left: 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 (loop_num: var, left: t0,
202	right: build_polynomial_chrec (loop_num: var, left: t1, right: t2));
203	}
204
205	/* When the operands are automatically_generated_chrec_p, the fold has
206	to respect the semantics of the operands. */
207
208	static inline tree
209	chrec_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
230	static tree
231	chrec_fold_plus_1 (enum tree_code code, tree type,
232	tree op0, tree op1)
233	{
234	if (automatically_generated_chrec_p (chrec: op0)
235	|| automatically_generated_chrec_p (chrec: 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, poly0: op0, poly1: 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, type: optype,
262	op0: 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	left: chrec_fold_plus (type, CHREC_LEFT (op0), op1),
276	CHREC_RIGHT (op0));
277	else
278	return build_polynomial_chrec
279	(CHREC_VARIABLE (op0),
280	left: 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, type: optype,
295	TREE_OPERAND (op0, 0),
296	op1: 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	left: chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
315	CHREC_RIGHT (op1));
316	else
317	return build_polynomial_chrec
318	(CHREC_VARIABLE (op1),
319	left: chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
320	right: 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
356	tree
357	chrec_fold_plus (tree type,
358	tree op0,
359	tree op1)
360	{
361	enum tree_code code;
362	if (automatically_generated_chrec_p (chrec: op0)
363	|| automatically_generated_chrec_p (chrec: 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
381	tree
382	chrec_fold_minus (tree type,
383	tree op0,
384	tree op1)
385	{
386	if (automatically_generated_chrec_p (chrec: op0)
387	|| automatically_generated_chrec_p (chrec: 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 (code: MINUS_EXPR, type, op0, op1);
394	}
395
396	/* Fold the multiplication of two chrecs. */
397
398	tree
399	chrec_fold_multiply (tree type,
400	tree op0,
401	tree op1)
402	{
403	if (automatically_generated_chrec_p (chrec: op0)
404	|| automatically_generated_chrec_p (chrec: 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, poly0: op0, poly1: 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	left: chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
434	right: 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	left: chrec_fold_multiply (type, CHREC_LEFT (op1), op1: op0),
458	right: chrec_fold_multiply (type, CHREC_RIGHT (op1), 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
482	static tree
483	tree_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 (t: n);
495
496	/* Check that k <= n. */
497	if (wi::ltu_p (x: num, y: 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 (x: num, y: idx, overflow: &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 (x: num, y: idx, overflow: &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 (x: num, y: denom);
527	if (! wi::fits_to_tree_p (x: num, type))
528	return NULL_TREE;
529	return wide_int_to_tree (type, cst: 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
536	static tree
537	chrec_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, num: 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: k + 1);
558	if (arg1 == chrec_dont_know)
559	return chrec_dont_know;
560	binomial_n_k = tree_fold_binomial (type: 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 (type: ctype, op0: arg0, op1: arg1);
566	}
567
568	binomial_n_k = tree_fold_binomial (type: 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
587	tree
588	chrec_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 (chrec: 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 (stream: dump_file, format: "(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	tree chrecr = CHREC_RIGHT (chrec);
616	if (CHREC_VARIABLE (chrec) != var)
617	res = build_polynomial_chrec
618	(CHREC_VARIABLE (chrec),
619	left: chrec_apply (var, CHREC_LEFT (chrec), x),
620	right: chrec_apply (var, chrec: chrecr, x));
621
622	/* "{a, +, b} (x)" -> "a + b*x". */
623	else if (operand_equal_p (CHREC_LEFT (chrec), chrecr)
624	&& TREE_CODE (x) == PLUS_EXPR
625	&& integer_all_onesp (TREE_OPERAND (x, 1))
626	&& !POINTER_TYPE_P (type)
627	&& TYPE_PRECISION (TREE_TYPE (x))
628	>= TYPE_PRECISION (type))
629	{
630	/* We know the number of iterations can't be negative.
631	So {a, +, a} (x-1) -> "a*x". */
632	res = build_int_cst (TREE_TYPE (x), 1);
633	res = chrec_fold_plus (TREE_TYPE (x), op0: x, op1: res);
634	res = chrec_convert_rhs (type, res, NULL);
635	res = chrec_fold_multiply (type, op0: chrecr, op1: res);
636	}
637	else
638	{
639	res = chrec_convert_rhs (TREE_TYPE (chrecr), x, NULL);
640	res = chrec_fold_multiply (TREE_TYPE (chrecr), op0: chrecr, op1: res);
641	res = chrec_fold_plus (type, CHREC_LEFT (chrec), op1: res);
642	}
643	}
644	else if (TREE_CODE (x) == INTEGER_CST
645	&& tree_int_cst_sgn (x) == 1)
646	/* testsuite/.../ssa-chrec-38.c. */
647	res = chrec_convert (type, chrec_evaluate (var, chrec, n: x, k: 0), NULL);
648	else
649	res = chrec_dont_know;
650	break;
651
652	CASE_CONVERT:
653	res = chrec_convert (TREE_TYPE (chrec),
654	chrec_apply (var, TREE_OPERAND (chrec, 0), x),
655	NULL);
656	break;
657
658	default:
659	res = chrec;
660	break;
661	}
662
663	if (dump_file && (dump_flags & TDF_SCEV))
664	{
665	fprintf (stream: dump_file, format: " (varying_loop = %d", var);
666	fprintf (stream: dump_file, format: ")\n (chrec = ");
667	print_generic_expr (dump_file, chrec);
668	fprintf (stream: dump_file, format: ")\n (x = ");
669	print_generic_expr (dump_file, x);
670	fprintf (stream: dump_file, format: ")\n (res = ");
671	print_generic_expr (dump_file, res);
672	fprintf (stream: dump_file, format: "))\n");
673	}
674
675	return res;
676	}
677
678	/* For a given CHREC and an induction variable map IV_MAP that maps
679	(loop->num, expr) for every loop number of the current_loops an
680	expression, calls chrec_apply when the expression is not NULL. */
681
682	tree
683	chrec_apply_map (tree chrec, vec<tree> iv_map)
684	{
685	int i;
686	tree expr;
687
688	FOR_EACH_VEC_ELT (iv_map, i, expr)
689	if (expr)
690	chrec = chrec_apply (var: i, chrec, x: expr);
691
692	return chrec;
693	}
694
695	/* Replaces the initial condition in CHREC with INIT_COND. */
696
697	tree
698	chrec_replace_initial_condition (tree chrec,
699	tree init_cond)
700	{
701	if (automatically_generated_chrec_p (chrec))
702	return chrec;
703
704	gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
705
706	switch (TREE_CODE (chrec))
707	{
708	case POLYNOMIAL_CHREC:
709	return build_polynomial_chrec
710	(CHREC_VARIABLE (chrec),
711	left: chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
712	CHREC_RIGHT (chrec));
713
714	default:
715	return init_cond;
716	}
717	}
718
719	/* Returns the initial condition of a given CHREC. */
720
721	tree
722	initial_condition (tree chrec)
723	{
724	if (automatically_generated_chrec_p (chrec))
725	return chrec;
726
727	if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
728	return initial_condition (CHREC_LEFT (chrec));
729	else
730	return chrec;
731	}
732
733	/* Returns a univariate function that represents the evolution in
734	LOOP_NUM. Mask the evolution of any other loop. */
735
736	tree
737	hide_evolution_in_other_loops_than_loop (tree chrec,
738	unsigned loop_num)
739	{
740	class loop *loop = get_loop (cfun, num: loop_num), *chloop;
741	if (automatically_generated_chrec_p (chrec))
742	return chrec;
743
744	switch (TREE_CODE (chrec))
745	{
746	case POLYNOMIAL_CHREC:
747	chloop = get_chrec_loop (chrec);
748
749	if (chloop == loop)
750	return build_polynomial_chrec
751	(loop_num,
752	left: hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
753	loop_num),
754	CHREC_RIGHT (chrec));
755
756	else if (flow_loop_nested_p (chloop, loop))
757	/* There is no evolution in this loop. */
758	return initial_condition (chrec);
759
760	else if (flow_loop_nested_p (loop, chloop))
761	return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
762	loop_num);
763
764	else
765	return chrec_dont_know;
766
767	default:
768	return chrec;
769	}
770	}
771
772	/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
773	true, otherwise returns the initial condition in LOOP_NUM. */
774
775	static tree
776	chrec_component_in_loop_num (tree chrec,
777	unsigned loop_num,
778	bool right)
779	{
780	tree component;
781	class loop *loop = get_loop (cfun, num: loop_num), *chloop;
782
783	if (automatically_generated_chrec_p (chrec))
784	return chrec;
785
786	switch (TREE_CODE (chrec))
787	{
788	case POLYNOMIAL_CHREC:
789	chloop = get_chrec_loop (chrec);
790
791	if (chloop == loop)
792	{
793	if (right)
794	component = CHREC_RIGHT (chrec);
795	else
796	component = CHREC_LEFT (chrec);
797
798	if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
799	|| CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
800	return component;
801
802	else
803	return build_polynomial_chrec
804	(loop_num,
805	left: chrec_component_in_loop_num (CHREC_LEFT (chrec),
806	loop_num,
807	right),
808	right: component);
809	}
810
811	else if (flow_loop_nested_p (chloop, loop))
812	/* There is no evolution part in this loop. */
813	return NULL_TREE;
814
815	else
816	{
817	gcc_assert (flow_loop_nested_p (loop, chloop));
818	return chrec_component_in_loop_num (CHREC_LEFT (chrec),
819	loop_num,
820	right);
821	}
822
823	default:
824	if (right)
825	return NULL_TREE;
826	else
827	return chrec;
828	}
829	}
830
831	/* Returns the evolution part in LOOP_NUM. Example: the call
832	evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
833	{1, +, 2}_1 */
834
835	tree
836	evolution_part_in_loop_num (tree chrec,
837	unsigned loop_num)
838	{
839	return chrec_component_in_loop_num (chrec, loop_num, right: true);
840	}
841
842	/* Returns the initial condition in LOOP_NUM. Example: the call
843	initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
844	{0, +, 1}_1 */
845
846	tree
847	initial_condition_in_loop_num (tree chrec,
848	unsigned loop_num)
849	{
850	return chrec_component_in_loop_num (chrec, loop_num, right: false);
851	}
852
853	/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
854	This function is essentially used for setting the evolution to
855	chrec_dont_know, for example after having determined that it is
856	impossible to say how many times a loop will execute. */
857
858	tree
859	reset_evolution_in_loop (unsigned loop_num,
860	tree chrec,
861	tree new_evol)
862	{
863	class loop *loop = get_loop (cfun, num: loop_num);
864
865	if (POINTER_TYPE_P (chrec_type (chrec)))
866	gcc_assert (ptrofftype_p (chrec_type (new_evol)));
867	else
868	gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
869
870	if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
871	&& flow_loop_nested_p (loop, get_chrec_loop (chrec)))
872	{
873	tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
874	new_evol);
875	tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
876	new_evol);
877	return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
878	}
879
880	while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
881	&& CHREC_VARIABLE (chrec) == loop_num)
882	chrec = CHREC_LEFT (chrec);
883
884	return build_polynomial_chrec (loop_num, left: chrec, right: new_evol);
885	}
886
887	/* Merges two evolution functions that were found by following two
888	alternate paths of a conditional expression. */
889
890	tree
891	chrec_merge (tree chrec1,
892	tree chrec2)
893	{
894	if (chrec1 == chrec_dont_know
895	|| chrec2 == chrec_dont_know)
896	return chrec_dont_know;
897
898	if (chrec1 == chrec_known
899	|| chrec2 == chrec_known)
900	return chrec_known;
901
902	if (chrec1 == chrec_not_analyzed_yet)
903	return chrec2;
904	if (chrec2 == chrec_not_analyzed_yet)
905	return chrec1;
906
907	if (eq_evolutions_p (chrec1, chrec2))
908	return chrec1;
909
910	return chrec_dont_know;
911	}
912
913
914
915	/* Observers. */
916
917	/* Helper function for is_multivariate_chrec. */
918
919	static bool
920	is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
921	{
922	if (chrec == NULL_TREE)
923	return false;
924
925	if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
926	{
927	if (CHREC_VARIABLE (chrec) != rec_var)
928	return true;
929	else
930	return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
931	|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
932	}
933	else
934	return false;
935	}
936
937	/* Determine whether the given chrec is multivariate or not. */
938
939	bool
940	is_multivariate_chrec (const_tree chrec)
941	{
942	if (chrec == NULL_TREE)
943	return false;
944
945	if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
946	return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
947	CHREC_VARIABLE (chrec))
948	|| is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
949	CHREC_VARIABLE (chrec)));
950	else
951	return false;
952	}
953
954	/* Determines whether the chrec contains symbolic names or not. If LOOP isn't
955	NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
956
957	static bool
958	chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
959	class loop *loop)
960	{
961	int i, n;
962
963	if (chrec == NULL_TREE)
964	return false;
965
966	if (TREE_CODE (chrec) == SSA_NAME
967	|| VAR_P (chrec)
968	|| TREE_CODE (chrec) == POLY_INT_CST
969	|| TREE_CODE (chrec) == PARM_DECL
970	|| TREE_CODE (chrec) == FUNCTION_DECL
971	|| TREE_CODE (chrec) == LABEL_DECL
972	|| TREE_CODE (chrec) == RESULT_DECL
973	|| TREE_CODE (chrec) == FIELD_DECL)
974	return true;
975
976	if (loop != NULL
977	&& TREE_CODE (chrec) == POLYNOMIAL_CHREC
978	&& flow_loop_nested_p (get_chrec_loop (chrec), loop))
979	return true;
980
981	if (visited.add (k: chrec))
982	return false;
983
984	n = TREE_OPERAND_LENGTH (chrec);
985	for (i = 0; i < n; i++)
986	if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
987	return true;
988	return false;
989	}
990
991	/* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
992	CHREC contains any chrec which is invariant wrto the loop (nest), in other
993	words, chrec defined by outer loops of loop, so from LOOP's point of view,
994	the chrec is considered as a SYMBOL. */
995
996	bool
997	chrec_contains_symbols (const_tree chrec, class loop* loop)
998	{
999	hash_set<const_tree> visited;
1000	return chrec_contains_symbols (chrec, visited, loop);
1001	}
1002
1003	/* Return true when CHREC contains symbolic names defined in
1004	LOOP_NB. */
1005
1006	static bool
1007	chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1008	hash_set<const_tree> &visited)
1009	{
1010	int i, n;
1011
1012	if (chrec == NULL_TREE)
1013	return false;
1014
1015	if (is_gimple_min_invariant (chrec))
1016	return false;
1017
1018	if (TREE_CODE (chrec) == SSA_NAME)
1019	{
1020	gimple *def;
1021	loop_p def_loop, loop;
1022
1023	if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1024	return false;
1025
1026	def = SSA_NAME_DEF_STMT (chrec);
1027	def_loop = loop_containing_stmt (stmt: def);
1028	loop = get_loop (cfun, num: loop_nb);
1029
1030	if (def_loop == NULL)
1031	return false;
1032
1033	if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1034	return true;
1035
1036	return false;
1037	}
1038
1039	if (visited.add (k: chrec))
1040	return false;
1041
1042	n = TREE_OPERAND_LENGTH (chrec);
1043	for (i = 0; i < n; i++)
1044	if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1045	loop_nb, visited))
1046	return true;
1047	return false;
1048	}
1049
1050	/* Return true when CHREC contains symbolic names defined in
1051	LOOP_NB. */
1052
1053	bool
1054	chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1055	{
1056	hash_set<const_tree> visited;
1057	return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1058	}
1059
1060	/* Determines whether the chrec contains undetermined coefficients. */
1061
1062	static bool
1063	chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1064	{
1065	int i, n;
1066
1067	if (chrec == chrec_dont_know)
1068	return true;
1069
1070	if (chrec == NULL_TREE)
1071	return false;
1072
1073	if (visited.add (k: chrec))
1074	return false;
1075
1076	n = TREE_OPERAND_LENGTH (chrec);
1077	for (i = 0; i < n; i++)
1078	if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1079	return true;
1080	return false;
1081	}
1082
1083	bool
1084	chrec_contains_undetermined (const_tree chrec)
1085	{
1086	hash_set<const_tree> visited;
1087	return chrec_contains_undetermined (chrec, visited);
1088	}
1089
1090	/* Determines whether the tree EXPR contains chrecs, and increment
1091	SIZE if it is not a NULL pointer by an estimation of the depth of
1092	the tree. */
1093
1094	static bool
1095	tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1096	{
1097	int i, n;
1098
1099	if (expr == NULL_TREE)
1100	return false;
1101
1102	if (size)
1103	(*size)++;
1104
1105	if (tree_is_chrec (expr))
1106	return true;
1107
1108	if (visited.add (k: expr))
1109	return false;
1110
1111	n = TREE_OPERAND_LENGTH (expr);
1112	for (i = 0; i < n; i++)
1113	if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1114	return true;
1115	return false;
1116	}
1117
1118	bool
1119	tree_contains_chrecs (const_tree expr, int *size)
1120	{
1121	hash_set<const_tree> visited;
1122	return tree_contains_chrecs (expr, size, visited);
1123	}
1124
1125
1126	/* Recursive helper function. */
1127
1128	static bool
1129	evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1130	{
1131	if (evolution_function_is_constant_p (chrec))
1132	return true;
1133
1134	if (TREE_CODE (chrec) == SSA_NAME
1135	&& (loopnum == 0
1136	|| expr_invariant_in_loop_p (get_loop (cfun, num: loopnum), chrec)))
1137	return true;
1138
1139	if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
1140	{
1141	if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
1142	|| flow_loop_nested_p (get_loop (cfun, num: loopnum),
1143	get_chrec_loop (chrec))
1144	|| !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
1145	loopnum)
1146	|| !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
1147	loopnum))
1148	return false;
1149	return true;
1150	}
1151
1152	switch (TREE_OPERAND_LENGTH (chrec))
1153	{
1154	case 2:
1155	if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
1156	loopnum))
1157	return false;
1158	/* FALLTHRU */
1159
1160	case 1:
1161	if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
1162	loopnum))
1163	return false;
1164	return true;
1165
1166	default:
1167	return false;
1168	}
1169	}
1170
1171	/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1172
1173	bool
1174	evolution_function_is_invariant_p (tree chrec, int loopnum)
1175	{
1176	return evolution_function_is_invariant_rec_p (chrec, loopnum);
1177	}
1178
1179	/* Determine whether the given tree is an affine multivariate
1180	evolution. */
1181
1182	bool
1183	evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1184	{
1185	if (chrec == NULL_TREE)
1186	return false;
1187
1188	switch (TREE_CODE (chrec))
1189	{
1190	case POLYNOMIAL_CHREC:
1191	if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1192	{
1193	if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1194	return true;
1195	else
1196	{
1197	if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1198	&& CHREC_VARIABLE (CHREC_RIGHT (chrec))
1199	!= CHREC_VARIABLE (chrec)
1200	&& evolution_function_is_affine_multivariate_p
1201	(CHREC_RIGHT (chrec), loopnum))
1202	return true;
1203	else
1204	return false;
1205	}
1206	}
1207	else
1208	{
1209	if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1210	&& TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1211	&& CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1212	&& evolution_function_is_affine_multivariate_p
1213	(CHREC_LEFT (chrec), loopnum))
1214	return true;
1215	else
1216	return false;
1217	}
1218
1219	default:
1220	return false;
1221	}
1222	}
1223
1224	/* Determine whether the given tree is a function in zero or one
1225	variables with respect to loop specified by LOOPNUM. Note only positive
1226	LOOPNUM stands for a real loop. */
1227
1228	bool
1229	evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1230	{
1231	if (chrec == NULL_TREE)
1232	return true;
1233
1234	tree sub_chrec;
1235	switch (TREE_CODE (chrec))
1236	{
1237	case POLYNOMIAL_CHREC:
1238	switch (TREE_CODE (CHREC_LEFT (chrec)))
1239	{
1240	case POLYNOMIAL_CHREC:
1241	sub_chrec = CHREC_LEFT (chrec);
1242	if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1243	&& (loopnum <= 0
1244	|| CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1245	|| flow_loop_nested_p (get_loop (cfun, num: loopnum),
1246	get_chrec_loop (chrec: sub_chrec))))
1247	return false;
1248	if (!evolution_function_is_univariate_p (chrec: sub_chrec, loopnum))
1249	return false;
1250	break;
1251
1252	default:
1253	if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1254	return false;
1255	break;
1256	}
1257
1258	switch (TREE_CODE (CHREC_RIGHT (chrec)))
1259	{
1260	case POLYNOMIAL_CHREC:
1261	sub_chrec = CHREC_RIGHT (chrec);
1262	if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1263	&& (loopnum <= 0
1264	|| CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1265	|| flow_loop_nested_p (get_loop (cfun, num: loopnum),
1266	get_chrec_loop (chrec: sub_chrec))))
1267	return false;
1268	if (!evolution_function_is_univariate_p (chrec: sub_chrec, loopnum))
1269	return false;
1270	break;
1271
1272	default:
1273	if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1274	return false;
1275	break;
1276	}
1277	return true;
1278
1279	default:
1280	return true;
1281	}
1282	}
1283
1284	/* Returns the number of variables of CHREC. Example: the call
1285	nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1286
1287	unsigned
1288	nb_vars_in_chrec (tree chrec)
1289	{
1290	if (chrec == NULL_TREE)
1291	return 0;
1292
1293	switch (TREE_CODE (chrec))
1294	{
1295	case POLYNOMIAL_CHREC:
1296	return 1 + nb_vars_in_chrec
1297	(chrec: initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1298
1299	default:
1300	return 0;
1301	}
1302	}
1303
1304	/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1305	the scev corresponds to. AT_STMT is the statement at that the scev is
1306	evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1307	that the rules for overflow of the given language apply (e.g., that signed
1308	arithmetics in C does not overflow) -- i.e., to use them to avoid
1309	unnecessary tests, but also to enforce that the result follows them.
1310	FROM is the source variable converted if it's not NULL. Returns true if
1311	the conversion succeeded, false otherwise. */
1312
1313	bool
1314	convert_affine_scev (class loop *loop, tree type,
1315	tree *base, tree *step, gimple *at_stmt,
1316	bool use_overflow_semantics, tree from)
1317	{
1318	tree ct = TREE_TYPE (*step);
1319	bool enforce_overflow_semantics;
1320	bool must_check_src_overflow, must_check_rslt_overflow;
1321	tree new_base, new_step;
1322	tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1323
1324	/* In general,
1325	(TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1326	but we must check some assumptions.
1327
1328	1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1329	of CT is smaller than the precision of TYPE. For example, when we
1330	cast unsigned char [254, +, 1] to unsigned, the values on left side
1331	are 254, 255, 0, 1, ..., but those on the right side are
1332	254, 255, 256, 257, ...
1333	2) In case that we must also preserve the fact that signed ivs do not
1334	overflow, we must additionally check that the new iv does not wrap.
1335	For example, unsigned char [125, +, 1] casted to signed char could
1336	become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1337	which would confuse optimizers that assume that this does not
1338	happen. */
1339	must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
1340
1341	enforce_overflow_semantics = (use_overflow_semantics
1342	&& nowrap_type_p (type));
1343	if (enforce_overflow_semantics)
1344	{
1345	/* We can avoid checking whether the result overflows in the following
1346	cases:
1347
1348	-- must_check_src_overflow is true, and the range of TYPE is superset
1349	of the range of CT -- i.e., in all cases except if CT signed and
1350	TYPE unsigned.
1351	-- both CT and TYPE have the same precision and signedness, and we
1352	verify instead that the source does not overflow (this may be
1353	easier than verifying it for the result, as we may use the
1354	information about the semantics of overflow in CT). */
1355	if (must_check_src_overflow)
1356	{
1357	if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
1358	must_check_rslt_overflow = true;
1359	else
1360	must_check_rslt_overflow = false;
1361	}
1362	else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
1363	&& TYPE_PRECISION (ct) == TYPE_PRECISION (type))
1364	{
1365	must_check_rslt_overflow = false;
1366	must_check_src_overflow = true;
1367	}
1368	else
1369	must_check_rslt_overflow = true;
1370	}
1371	else
1372	must_check_rslt_overflow = false;
1373
1374	if (must_check_src_overflow
1375	&& scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1376	use_overflow_semantics))
1377	return false;
1378
1379	new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1380	/* The step must be sign extended, regardless of the signedness
1381	of CT and TYPE. This only needs to be handled specially when
1382	CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1383	(with values 100, 99, 98, ...) from becoming signed or unsigned
1384	[100, +, 255] with values 100, 355, ...; the sign-extension is
1385	performed by default when CT is signed. */
1386	new_step = *step;
1387	if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1388	{
1389	tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
1390	new_step = chrec_convert (signed_ct, new_step, at_stmt,
1391	use_overflow_semantics);
1392	}
1393	new_step = chrec_convert (step_type, new_step, at_stmt,
1394	use_overflow_semantics);
1395
1396	if (automatically_generated_chrec_p (chrec: new_base)
1397	|| automatically_generated_chrec_p (chrec: new_step))
1398	return false;
1399
1400	if (must_check_rslt_overflow
1401	/* Note that in this case we cannot use the fact that signed variables
1402	do not overflow, as this is what we are verifying for the new iv. */
1403	&& scev_probably_wraps_p (NULL_TREE, new_base, new_step,
1404	at_stmt, loop, false))
1405	return false;
1406
1407	*base = new_base;
1408	*step = new_step;
1409	return true;
1410	}
1411
1412
1413	/* Convert CHREC for the right hand side of a CHREC.
1414	The increment for a pointer type is always sizetype. */
1415
1416	tree
1417	chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1418	{
1419	if (POINTER_TYPE_P (type))
1420	type = sizetype;
1421
1422	return chrec_convert (type, chrec, at_stmt);
1423	}
1424
1425	/* Convert CHREC to TYPE. When the analyzer knows the context in
1426	which the CHREC is built, it sets AT_STMT to the statement that
1427	contains the definition of the analyzed variable, otherwise the
1428	conversion is less accurate: the information is used for
1429	determining a more accurate estimation of the number of iterations.
1430	By default AT_STMT could be safely set to NULL_TREE.
1431
1432	USE_OVERFLOW_SEMANTICS is true if this function should assume that
1433	the rules for overflow of the given language apply (e.g., that signed
1434	arithmetics in C does not overflow) -- i.e., to use them to avoid
1435	unnecessary tests, but also to enforce that the result follows them.
1436
1437	FROM is the source variable converted if it's not NULL. */
1438
1439	static tree
1440	chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1441	bool use_overflow_semantics, tree from)
1442	{
1443	tree ct, res;
1444	tree base, step;
1445	class loop *loop;
1446
1447	if (automatically_generated_chrec_p (chrec))
1448	return chrec;
1449
1450	ct = chrec_type (chrec);
1451	if (useless_type_conversion_p (type, ct))
1452	return chrec;
1453
1454	if (!evolution_function_is_affine_p (chrec))
1455	goto keep_cast;
1456
1457	loop = get_chrec_loop (chrec);
1458	base = CHREC_LEFT (chrec);
1459	step = CHREC_RIGHT (chrec);
1460
1461	if (convert_affine_scev (loop, type, base: &base, step: &step, at_stmt,
1462	use_overflow_semantics, from))
1463	return build_polynomial_chrec (loop_num: loop->num, left: base, right: step);
1464
1465	/* If we cannot propagate the cast inside the chrec, just keep the cast. */
1466	keep_cast:
1467	/* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1468	may be more expensive. We do want to perform this optimization here
1469	though for canonicalization reasons. */
1470	if (use_overflow_semantics
1471	&& (TREE_CODE (chrec) == PLUS_EXPR
1472	|| TREE_CODE (chrec) == MINUS_EXPR)
1473	&& TREE_CODE (type) == INTEGER_TYPE
1474	&& TREE_CODE (ct) == INTEGER_TYPE
1475	&& TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1476	&& TYPE_OVERFLOW_UNDEFINED (ct))
1477	res = fold_build2 (TREE_CODE (chrec), type,
1478	fold_convert (type, TREE_OPERAND (chrec, 0)),
1479	fold_convert (type, TREE_OPERAND (chrec, 1)));
1480	/* Similar perform the trick that (signed char)((int)x + 2) can be
1481	narrowed to (signed char)((unsigned char)x + 2). */
1482	else if (use_overflow_semantics
1483	&& TREE_CODE (chrec) == POLYNOMIAL_CHREC
1484	&& TREE_CODE (ct) == INTEGER_TYPE
1485	&& TREE_CODE (type) == INTEGER_TYPE
1486	&& TYPE_OVERFLOW_UNDEFINED (type)
1487	&& TYPE_PRECISION (type) < TYPE_PRECISION (ct))
1488	{
1489	tree utype = unsigned_type_for (type);
1490	res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
1491	fold_convert (utype,
1492	CHREC_LEFT (chrec)),
1493	fold_convert (utype,
1494	CHREC_RIGHT (chrec)));
1495	res = chrec_convert_1 (type, chrec: res, at_stmt, use_overflow_semantics, from);
1496	}
1497	else
1498	res = fold_convert (type, chrec);
1499
1500	/* Don't propagate overflows. */
1501	if (CONSTANT_CLASS_P (res))
1502	TREE_OVERFLOW (res) = 0;
1503
1504	/* But reject constants that don't fit in their type after conversion.
1505	This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1506	natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1507	and can cause problems later when computing niters of loops. Note
1508	that we don't do the check before converting because we don't want
1509	to reject conversions of negative chrecs to unsigned types. */
1510	if (TREE_CODE (res) == INTEGER_CST
1511	&& TREE_CODE (type) == INTEGER_TYPE
1512	&& !int_fits_type_p (res, type))
1513	res = chrec_dont_know;
1514
1515	return res;
1516	}
1517
1518	/* Convert CHREC to TYPE. When the analyzer knows the context in
1519	which the CHREC is built, it sets AT_STMT to the statement that
1520	contains the definition of the analyzed variable, otherwise the
1521	conversion is less accurate: the information is used for
1522	determining a more accurate estimation of the number of iterations.
1523	By default AT_STMT could be safely set to NULL_TREE.
1524
1525	The following rule is always true: TREE_TYPE (chrec) ==
1526	TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1527	An example of what could happen when adding two chrecs and the type
1528	of the CHREC_RIGHT is different than CHREC_LEFT is:
1529
1530	{(uint) 0, +, (uchar) 10} +
1531	{(uint) 0, +, (uchar) 250}
1532
1533	that would produce a wrong result if CHREC_RIGHT is not (uint):
1534
1535	{(uint) 0, +, (uchar) 4}
1536
1537	instead of
1538
1539	{(uint) 0, +, (uint) 260}
1540
1541	USE_OVERFLOW_SEMANTICS is true if this function should assume that
1542	the rules for overflow of the given language apply (e.g., that signed
1543	arithmetics in C does not overflow) -- i.e., to use them to avoid
1544	unnecessary tests, but also to enforce that the result follows them.
1545
1546	FROM is the source variable converted if it's not NULL. */
1547
1548	tree
1549	chrec_convert (tree type, tree chrec, gimple *at_stmt,
1550	bool use_overflow_semantics, tree from)
1551	{
1552	return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1553	}
1554
1555	/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1556	chrec if something else than what chrec_convert would do happens, NULL_TREE
1557	otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1558	if the result chrec may overflow. */
1559
1560	tree
1561	chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1562	{
1563	tree inner_type, left, right, lc, rc, rtype;
1564
1565	gcc_assert (fold_conversions != NULL);
1566
1567	if (automatically_generated_chrec_p (chrec)
1568	|| TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1569	return NULL_TREE;
1570
1571	inner_type = TREE_TYPE (chrec);
1572	if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1573	return NULL_TREE;
1574
1575	if (useless_type_conversion_p (type, inner_type))
1576	return NULL_TREE;
1577
1578	if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1579	{
1580	tree base, step;
1581	class loop *loop;
1582
1583	loop = get_chrec_loop (chrec);
1584	base = CHREC_LEFT (chrec);
1585	step = CHREC_RIGHT (chrec);
1586	if (convert_affine_scev (loop, type, base: &base, step: &step, NULL, use_overflow_semantics: true))
1587	return build_polynomial_chrec (loop_num: loop->num, left: base, right: step);
1588	}
1589	rtype = POINTER_TYPE_P (type) ? sizetype : type;
1590
1591	left = CHREC_LEFT (chrec);
1592	right = CHREC_RIGHT (chrec);
1593	lc = chrec_convert_aggressive (type, chrec: left, fold_conversions);
1594	if (!lc)
1595	lc = chrec_convert (type, chrec: left, NULL);
1596	rc = chrec_convert_aggressive (type: rtype, chrec: right, fold_conversions);
1597	if (!rc)
1598	rc = chrec_convert (type: rtype, chrec: right, NULL);
1599
1600	*fold_conversions = true;
1601
1602	return build_polynomial_chrec (CHREC_VARIABLE (chrec), left: lc, right: rc);
1603	}
1604
1605	/* Returns true when CHREC0 == CHREC1. */
1606
1607	bool
1608	eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1609	{
1610	if (chrec0 == NULL_TREE
1611	|| chrec1 == NULL_TREE
1612	|| TREE_CODE (chrec0) != TREE_CODE (chrec1))
1613	return false;
1614
1615	if (chrec0 == chrec1)
1616	return true;
1617
1618	if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
1619	return false;
1620
1621	switch (TREE_CODE (chrec0))
1622	{
1623	case POLYNOMIAL_CHREC:
1624	return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1625	&& eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1626	&& eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1627
1628	case PLUS_EXPR:
1629	case MULT_EXPR:
1630	case MINUS_EXPR:
1631	case POINTER_PLUS_EXPR:
1632	return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1633	TREE_OPERAND (chrec1, 0))
1634	&& eq_evolutions_p (TREE_OPERAND (chrec0, 1),
1635	TREE_OPERAND (chrec1, 1));
1636
1637	CASE_CONVERT:
1638	return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
1639	TREE_OPERAND (chrec1, 0));
1640
1641	default:
1642	return operand_equal_p (chrec0, chrec1, flags: 0);
1643	}
1644	}
1645
1646	/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1647	EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1648	which of these cases happens. */
1649
1650	enum ev_direction
1651	scev_direction (const_tree chrec)
1652	{
1653	const_tree step;
1654
1655	if (!evolution_function_is_affine_p (chrec))
1656	return EV_DIR_UNKNOWN;
1657
1658	step = CHREC_RIGHT (chrec);
1659	if (TREE_CODE (step) != INTEGER_CST)
1660	return EV_DIR_UNKNOWN;
1661
1662	if (tree_int_cst_sign_bit (step))
1663	return EV_DIR_DECREASES;
1664	else
1665	return EV_DIR_GROWS;
1666	}
1667
1668	/* Iterates over all the components of SCEV, and calls CBCK. */
1669
1670	void
1671	for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1672	{
1673	switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
1674	{
1675	case 3:
1676	for_each_scev_op (scev: &TREE_OPERAND (*scev, 2), cbck, data);
1677	/* FALLTHRU */
1678
1679	case 2:
1680	for_each_scev_op (scev: &TREE_OPERAND (*scev, 1), cbck, data);
1681	/* FALLTHRU */
1682
1683	case 1:
1684	for_each_scev_op (scev: &TREE_OPERAND (*scev, 0), cbck, data);
1685	/* FALLTHRU */
1686
1687	default:
1688	cbck (scev, data);
1689	break;
1690	}
1691	}
1692
1693	/* Returns true when the operation can be part of a linear
1694	expression. */
1695
1696	static inline bool
1697	operator_is_linear (tree scev)
1698	{
1699	switch (TREE_CODE (scev))
1700	{
1701	case INTEGER_CST:
1702	case POLYNOMIAL_CHREC:
1703	case PLUS_EXPR:
1704	case POINTER_PLUS_EXPR:
1705	case MULT_EXPR:
1706	case MINUS_EXPR:
1707	case NEGATE_EXPR:
1708	case SSA_NAME:
1709	case NON_LVALUE_EXPR:
1710	case BIT_NOT_EXPR:
1711	CASE_CONVERT:
1712	return true;
1713
1714	default:
1715	return false;
1716	}
1717	}
1718
1719	/* Return true when SCEV is a linear expression. Linear expressions
1720	can contain additions, substractions and multiplications.
1721	Multiplications are restricted to constant scaling: "cst * x". */
1722
1723	bool
1724	scev_is_linear_expression (tree scev)
1725	{
1726	if (evolution_function_is_constant_p (chrec: scev))
1727	return true;
1728
1729	if (scev == NULL
1730	|| !operator_is_linear (scev))
1731	return false;
1732
1733	if (TREE_CODE (scev) == MULT_EXPR)
1734	return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1735	&& tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1736
1737	if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1738	&& !evolution_function_is_affine_multivariate_p (chrec: scev, CHREC_VARIABLE (scev)))
1739	return false;
1740
1741	switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1742	{
1743	case 3:
1744	return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1745	&& scev_is_linear_expression (TREE_OPERAND (scev, 1))
1746	&& scev_is_linear_expression (TREE_OPERAND (scev, 2));
1747
1748	case 2:
1749	return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1750	&& scev_is_linear_expression (TREE_OPERAND (scev, 1));
1751
1752	case 1:
1753	return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1754
1755	case 0:
1756	return true;
1757
1758	default:
1759	return false;
1760	}
1761	}
1762
1763	/* Determines whether the expression CHREC contains only interger consts
1764	in the right parts. */
1765
1766	bool
1767	evolution_function_right_is_integer_cst (const_tree chrec)
1768	{
1769	if (chrec == NULL_TREE)
1770	return false;
1771
1772	switch (TREE_CODE (chrec))
1773	{
1774	case INTEGER_CST:
1775	return true;
1776
1777	case POLYNOMIAL_CHREC:
1778	return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
1779	&& (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
1780	|| evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
1781
1782	CASE_CONVERT:
1783	return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
1784
1785	default:
1786	return false;
1787	}
1788	}
1789