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