1	/* Polynomial integer classes.
2	Copyright (C) 2014-2023 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it under
7	the terms of the GNU General Public License as published by the Free
8	Software Foundation; either version 3, or (at your option) any later
9	version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	/* This file provides a representation of sizes and offsets whose exact
21	values depend on certain runtime properties. The motivating example
22	is the Arm SVE ISA, in which the number of vector elements is only
23	known at runtime. See doc/poly-int.texi for more details.
24
25	Tests for poly-int.h are located in testsuite/gcc.dg/plugin,
26	since they are too expensive (in terms of binary size) to be
27	included as selftests. */
28
29	#ifndef HAVE_POLY_INT_H
30	#define HAVE_POLY_INT_H
31
32	template<unsigned int N, typename T> class poly_int;
33
34	/* poly_coeff_traiits<T> describes the properties of a poly_int
35	coefficient type T:
36
37	- poly_coeff_traits<T1>::rank is less than poly_coeff_traits<T2>::rank
38	if T1 can promote to T2. For C-like types the rank is:
39
40	(2 * number of bytes) + (unsigned ? 1 : 0)
41
42	wide_ints don't have a normal rank and so use a value of INT_MAX.
43	Any fixed-width integer should be promoted to wide_int if possible
44	and lead to an error otherwise.
45
46	- poly_coeff_traits<T>::int_type is the type to which an integer
47	literal should be cast before comparing it with T.
48
49	- poly_coeff_traits<T>::precision is the number of bits that T can hold.
50
51	- poly_coeff_traits<T>::signedness is:
52	0 if T is unsigned
53	1 if T is signed
54	-1 if T has no inherent sign (as for wide_int).
55
56	- poly_coeff_traits<T>::max_value, if defined, is the maximum value of T.
57
58	- poly_coeff_traits<T>::result is a type that can hold results of
59	operations on T. This is different from T itself in cases where T
60	is the result of an accessor like wi::to_offset.
61
62	- poly_coeff_traits<T>::init_cast<Arg>::type is the type to which
63	an argument of type Arg should be casted before being used to
64	initialize a coefficient of type T. */
65	template<typename T, wi::precision_type = wi::int_traits<T>::precision_type>
66	struct poly_coeff_traits;
67
68	template<typename T>
69	struct poly_coeff_traits<T, wi::FLEXIBLE_PRECISION>
70	{
71	typedef T result;
72	typedef T int_type;
73	static const int signedness = (T (0) >= T (-1));
74	static const int precision = sizeof (T) * CHAR_BIT;
75	static const T max_value = (signedness
76	? ((T (1) << (precision - 2))
77	+ ((T (1) << (precision - 2)) - 1))
78	: T (-1));
79	static const int rank = sizeof (T) * 2 + !signedness;
80
81	template<typename Arg>
82	struct init_cast { using type = T; };
83	};
84
85	template<typename T>
86	struct poly_coeff_traits<T, wi::VAR_PRECISION>
87	{
88	typedef T result;
89	typedef int int_type;
90	static const int signedness = -1;
91	static const int precision = WIDE_INT_MAX_PRECISION;
92	static const int rank = INT_MAX;
93
94	template<typename Arg>
95	struct init_cast { using type = const Arg &; };
96	};
97
98	template<typename T>
99	struct poly_coeff_traits<T, wi::INL_CONST_PRECISION>
100	{
101	typedef WI_UNARY_RESULT (T) result;
102	typedef int int_type;
103	/* These types are always signed. */
104	static const int signedness = 1;
105	static const int precision = wi::int_traits<T>::precision;
106	static const int rank = precision * 2 / CHAR_BIT;
107
108	template<typename Arg>
109	struct init_cast { using type = const Arg &; };
110	};
111
112	template<typename T>
113	struct poly_coeff_traits<T, wi::CONST_PRECISION>
114	{
115	typedef WI_UNARY_RESULT (T) result;
116	typedef int int_type;
117	/* These types are always signed. */
118	static const int signedness = 1;
119	static const int precision = wi::int_traits<T>::precision;
120	static const int rank = precision * 2 / CHAR_BIT;
121
122	template<typename Arg>
123	struct init_cast { using type = const Arg &; };
124	};
125
126	/* Information about a pair of coefficient types. */
127	template<typename T1, typename T2>
128	struct poly_coeff_pair_traits
129	{
130	/* True if T1 can represent all the values of T2.
131
132	Either:
133
134	- T1 should be a type with the same signedness as T2 and no less
135	precision. This allows things like int16_t -> int16_t and
136	uint32_t -> uint64_t.
137
138	- T1 should be signed, T2 should be unsigned, and T1 should be
139	wider than T2. This allows things like uint16_t -> int32_t.
140
141	This rules out cases in which T1 has less precision than T2 or where
142	the conversion would reinterpret the top bit. E.g. int16_t -> uint32_t
143	can be dangerous and should have an explicit cast if deliberate. */
144	static const bool lossless_p = (poly_coeff_traits<T1>::signedness
145	== poly_coeff_traits<T2>::signedness
146	? (poly_coeff_traits<T1>::precision
147	>= poly_coeff_traits<T2>::precision)
148	: (poly_coeff_traits<T1>::signedness == 1
149	&& poly_coeff_traits<T2>::signedness == 0
150	&& (poly_coeff_traits<T1>::precision
151	> poly_coeff_traits<T2>::precision)));
152
153	/* 0 if T1 op T2 should promote to HOST_WIDE_INT,
154	1 if T1 op T2 should promote to unsigned HOST_WIDE_INT,
155	2 if T1 op T2 should use wide-int rules. */
156	#define RANK(X) poly_coeff_traits<X>::rank
157	static const int result_kind
158	= ((RANK (T1) <= RANK (HOST_WIDE_INT)
159	&& RANK (T2) <= RANK (HOST_WIDE_INT))
160	? 0
161	: (RANK (T1) <= RANK (unsigned HOST_WIDE_INT)
162	&& RANK (T2) <= RANK (unsigned HOST_WIDE_INT))
163	? 1 : 2);
164	#undef RANK
165	};
166
167	/* SFINAE class that makes T3 available as "type" if T2 can represent all the
168	values in T1. */
169	template<typename T1, typename T2, typename T3,
170	bool lossless_p = poly_coeff_pair_traits<T1, T2>::lossless_p>
171	struct if_lossless;
172	template<typename T1, typename T2, typename T3>
173	struct if_lossless<T1, T2, T3, true>
174	{
175	typedef T3 type;
176	};
177
178	/* poly_int_traits<T> describes an integer type T that might be polynomial
179	or non-polynomial:
180
181	- poly_int_traits<T>::is_poly is true if T is a poly_int-based type
182	and false otherwise.
183
184	- poly_int_traits<T>::num_coeffs gives the number of coefficients in T
185	if T is a poly_int and 1 otherwise.
186
187	- poly_int_traits<T>::coeff_type gives the coefficent type of T if T
188	is a poly_int and T itself otherwise
189
190	- poly_int_traits<T>::int_type is a shorthand for
191	typename poly_coeff_traits<coeff_type>::int_type. */
192	template<typename T>
193	struct poly_int_traits
194	{
195	static const bool is_poly = false;
196	static const unsigned int num_coeffs = 1;
197	typedef T coeff_type;
198	typedef typename poly_coeff_traits<T>::int_type int_type;
199	};
200	template<unsigned int N, typename C>
201	struct poly_int_traits<poly_int<N, C> >
202	{
203	static const bool is_poly = true;
204	static const unsigned int num_coeffs = N;
205	typedef C coeff_type;
206	typedef typename poly_coeff_traits<C>::int_type int_type;
207	};
208
209	/* SFINAE class that makes T2 available as "type" if T1 is a non-polynomial
210	type. */
211	template<typename T1, typename T2 = T1,
212	bool is_poly = poly_int_traits<T1>::is_poly>
213	struct if_nonpoly {};
214	template<typename T1, typename T2>
215	struct if_nonpoly<T1, T2, false>
216	{
217	typedef T2 type;
218	};
219
220	/* SFINAE class that makes T3 available as "type" if both T1 and T2 are
221	non-polynomial types. */
222	template<typename T1, typename T2, typename T3,
223	bool is_poly1 = poly_int_traits<T1>::is_poly,
224	bool is_poly2 = poly_int_traits<T2>::is_poly>
225	struct if_nonpoly2 {};
226	template<typename T1, typename T2, typename T3>
227	struct if_nonpoly2<T1, T2, T3, false, false>
228	{
229	typedef T3 type;
230	};
231
232	/* SFINAE class that makes T2 available as "type" if T1 is a polynomial
233	type. */
234	template<typename T1, typename T2 = T1,
235	bool is_poly = poly_int_traits<T1>::is_poly>
236	struct if_poly {};
237	template<typename T1, typename T2>
238	struct if_poly<T1, T2, true>
239	{
240	typedef T2 type;
241	};
242
243	/* poly_result<T1, T2> describes the result of an operation on two
244	types T1 and T2, where at least one of the types is polynomial:
245
246	- poly_result<T1, T2>::type gives the result type for the operation.
247	The intention is to provide normal C-like rules for integer ranks,
248	except that everything smaller than HOST_WIDE_INT promotes to
249	HOST_WIDE_INT.
250
251	- poly_result<T1, T2>::cast is the type to which an operand of type
252	T1 should be cast before doing the operation, to ensure that
253	the operation is done at the right precision. Casting to
254	poly_result<T1, T2>::type would also work, but casting to this
255	type is more efficient. */
256	template<typename T1, typename T2 = T1,
257	int result_kind = poly_coeff_pair_traits<T1, T2>::result_kind>
258	struct poly_result;
259
260	/* Promote pair to HOST_WIDE_INT. */
261	template<typename T1, typename T2>
262	struct poly_result<T1, T2, 0>
263	{
264	typedef HOST_WIDE_INT type;
265	/* T1 and T2 are primitive types, so cast values to T before operating
266	on them. */
267	typedef type cast;
268	};
269
270	/* Promote pair to unsigned HOST_WIDE_INT. */
271	template<typename T1, typename T2>
272	struct poly_result<T1, T2, 1>
273	{
274	typedef unsigned HOST_WIDE_INT type;
275	/* T1 and T2 are primitive types, so cast values to T before operating
276	on them. */
277	typedef type cast;
278	};
279
280	/* Use normal wide-int rules. */
281	template<typename T1, typename T2>
282	struct poly_result<T1, T2, 2>
283	{
284	typedef WI_BINARY_RESULT (T1, T2) type;
285	/* Don't cast values before operating on them; leave the wi:: routines
286	to handle promotion as necessary. */
287	typedef const T1 &cast;
288	};
289
290	/* The coefficient type for the result of a binary operation on two
291	poly_ints, the first of which has coefficients of type C1 and the
292	second of which has coefficients of type C2. */
293	#define POLY_POLY_COEFF(C1, C2) typename poly_result<C1, C2>::type
294
295	/* Enforce that T2 is non-polynomial and provide the cofficient type of
296	the result of a binary operation in which the first operand is a
297	poly_int with coefficients of type C1 and the second operand is
298	a constant of type T2. */
299	#define POLY_CONST_COEFF(C1, T2) \
300	POLY_POLY_COEFF (C1, typename if_nonpoly<T2>::type)
301
302	/* Likewise in reverse. */
303	#define CONST_POLY_COEFF(T1, C2) \
304	POLY_POLY_COEFF (typename if_nonpoly<T1>::type, C2)
305
306	/* The result type for a binary operation on poly_int<N, C1> and
307	poly_int<N, C2>. */
308	#define POLY_POLY_RESULT(N, C1, C2) poly_int<N, POLY_POLY_COEFF (C1, C2)>
309
310	/* Enforce that T2 is non-polynomial and provide the result type
311	for a binary operation on poly_int<N, C1> and T2. */
312	#define POLY_CONST_RESULT(N, C1, T2) poly_int<N, POLY_CONST_COEFF (C1, T2)>
313
314	/* Enforce that T1 is non-polynomial and provide the result type
315	for a binary operation on T1 and poly_int<N, C2>. */
316	#define CONST_POLY_RESULT(N, T1, C2) poly_int<N, CONST_POLY_COEFF (T1, C2)>
317
318	/* Enforce that T1 and T2 are non-polynomial and provide the result type
319	for a binary operation on T1 and T2. */
320	#define CONST_CONST_RESULT(N, T1, T2) \
321	POLY_POLY_COEFF (typename if_nonpoly<T1>::type, \
322	typename if_nonpoly<T2>::type)
323
324	/* The type to which a coefficient of type C1 should be cast before
325	using it in a binary operation with a coefficient of type C2. */
326	#define POLY_CAST(C1, C2) typename poly_result<C1, C2>::cast
327
328	/* Provide the coefficient type for the result of T1 op T2, where T1
329	and T2 can be polynomial or non-polynomial. */
330	#define POLY_BINARY_COEFF(T1, T2) \
331	typename poly_result<typename poly_int_traits<T1>::coeff_type, \
332	typename poly_int_traits<T2>::coeff_type>::type
333
334	/* The type to which an integer constant should be cast before
335	comparing it with T. */
336	#define POLY_INT_TYPE(T) typename poly_int_traits<T>::int_type
337
338	/* RES is a poly_int result that has coefficients of type C and that
339	is being built up a coefficient at a time. Set coefficient number I
340	to VALUE in the most efficient way possible.
341
342	For primitive C it is better to assign directly, since it avoids
343	any further calls and so is more efficient when the compiler is
344	built at -O0. But for wide-int based C it is better to construct
345	the value in-place. This means that calls out to a wide-int.cc
346	routine can take the address of RES rather than the address of
347	a temporary.
348
349	The dummy self-comparison against C * is just a way of checking
350	that C gives the right type. */
351	#define POLY_SET_COEFF(C, RES, I, VALUE) \
352	((void) (&(RES).coeffs[0] == (C *) (void *) &(RES).coeffs[0]), \
353	wi::int_traits<C>::precision_type == wi::FLEXIBLE_PRECISION \
354	? (void) ((RES).coeffs[I] = VALUE) \
355	: (void) ((RES).coeffs[I].~C (), new (&(RES).coeffs[I]) C (VALUE)))
356
357	/* poly_int_full and poly_int_hungry are used internally within poly_int
358	for delegated initializers. poly_int_full indicates that a parameter
359	pack has enough elements to initialize every coefficient. poly_int_hungry
360	indicates that at least one extra zero must be added. */
361	struct poly_int_full {};
362	struct poly_int_hungry {};
363
364	/* poly_int_fullness<B>::type is poly_int_full when B is true and
365	poly_int_hungry when B is false. */
366	template<bool> struct poly_int_fullness;
367	template<> struct poly_int_fullness<false> { using type = poly_int_hungry; };
368	template<> struct poly_int_fullness<true> { using type = poly_int_full; };
369
370	/* A class containing polynomial integers. The polynomial has N coefficients
371	of type C, and N - 1 indeterminates. */
372	template<unsigned int N, typename C>
373	struct poly_int
374	{
375	public:
376	poly_int () = default;
377	poly_int (const poly_int &) = default;
378
379	template<typename Ca>
380	poly_int (const poly_int<N, Ca> &);
381
382	template<typename ...Cs>
383	constexpr poly_int (const Cs &...);
384
385	poly_int &operator = (const poly_int &) = default;
386
387	template<typename Ca>
388	poly_int &operator = (const poly_int<N, Ca> &);
389	template<typename Ca>
390	typename if_nonpoly<Ca, poly_int>::type &operator = (const Ca &);
391
392	template<typename Ca>
393	poly_int &operator += (const poly_int<N, Ca> &);
394	template<typename Ca>
395	typename if_nonpoly<Ca, poly_int>::type &operator += (const Ca &);
396
397	template<typename Ca>
398	poly_int &operator -= (const poly_int<N, Ca> &);
399	template<typename Ca>
400	typename if_nonpoly<Ca, poly_int>::type &operator -= (const Ca &);
401
402	template<typename Ca>
403	typename if_nonpoly<Ca, poly_int>::type &operator *= (const Ca &);
404
405	poly_int &operator <<= (unsigned int);
406
407	bool is_constant () const;
408
409	template<typename T>
410	typename if_lossless<T, C, bool>::type is_constant (T *) const;
411
412	C to_constant () const;
413
414	template<typename Ca>
415	static poly_int<N, C> from (const poly_int<N, Ca> &, unsigned int,
416	signop);
417	template<typename Ca>
418	static poly_int<N, C> from (const poly_int<N, Ca> &, signop);
419
420	bool to_shwi (poly_int<N, HOST_WIDE_INT> *) const;
421	bool to_uhwi (poly_int<N, unsigned HOST_WIDE_INT> *) const;
422	poly_int<N, HOST_WIDE_INT> force_shwi () const;
423	poly_int<N, unsigned HOST_WIDE_INT> force_uhwi () const;
424
425	#if POLY_INT_CONVERSION
426	operator C () const;
427	#endif
428
429	C coeffs[N];
430
431	private:
432	template<typename ...Cs>
433	constexpr poly_int (poly_int_full, const Cs &...);
434
435	template<typename C0, typename ...Cs>
436	constexpr poly_int (poly_int_hungry, const C0 &, const Cs &...);
437	};
438
439	template<unsigned int N, typename C>
440	template<typename Ca>
441	inline
442	poly_int<N, C>::poly_int (const poly_int<N, Ca> &a)
443	{
444	for (unsigned int i = 0; i < N; i++)
445	POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
446	}
447
448	template<unsigned int N, typename C>
449	template<typename ...Cs>
450	inline constexpr
451	poly_int<N, C>::poly_int (const Cs &... cs)
452	: poly_int (typename poly_int_fullness<sizeof... (Cs) >= N>::type (),
453	cs...) {}
454
455	/* Initialize with c0, cs..., and some trailing zeros. */
456	template<unsigned int N, typename C>
457	template<typename C0, typename ...Cs>
458	inline constexpr
459	poly_int<N, C>::poly_int (poly_int_hungry, const C0 &c0, const Cs &... cs)
460	: poly_int (c0, cs..., wi::ints_for<C>::zero (c0)) {}
461
462	/* Initialize with cs... directly, casting where necessary. */
463	template<unsigned int N, typename C>
464	template<typename ...Cs>
465	inline constexpr
466	poly_int<N, C>::poly_int (poly_int_full, const Cs &... cs)
467	: coeffs { (typename poly_coeff_traits<C>::
468	template init_cast<Cs>::type (cs))... } {}
469
470	template<unsigned int N, typename C>
471	template<typename Ca>
472	inline poly_int<N, C>&
473	poly_int<N, C>::operator = (const poly_int<N, Ca> &a)
474	{
475	for (unsigned int i = 0; i < N; i++)
476	POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
477	return *this;
478	}
479
480	template<unsigned int N, typename C>
481	template<typename Ca>
482	inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
483	poly_int<N, C>::operator = (const Ca &a)
484	{
485	POLY_SET_COEFF (C, *this, 0, a);
486	if (N >= 2)
487	for (unsigned int i = 1; i < N; i++)
488	POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
489	return *this;
490	}
491
492	template<unsigned int N, typename C>
493	template<typename Ca>
494	inline poly_int<N, C>&
495	poly_int<N, C>::operator += (const poly_int<N, Ca> &a)
496	{
497	for (unsigned int i = 0; i < N; i++)
498	this->coeffs[i] += a.coeffs[i];
499	return *this;
500	}
501
502	template<unsigned int N, typename C>
503	template<typename Ca>
504	inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
505	poly_int<N, C>::operator += (const Ca &a)
506	{
507	this->coeffs[0] += a;
508	return *this;
509	}
510
511	template<unsigned int N, typename C>
512	template<typename Ca>
513	inline poly_int<N, C>&
514	poly_int<N, C>::operator -= (const poly_int<N, Ca> &a)
515	{
516	for (unsigned int i = 0; i < N; i++)
517	this->coeffs[i] -= a.coeffs[i];
518	return *this;
519	}
520
521	template<unsigned int N, typename C>
522	template<typename Ca>
523	inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
524	poly_int<N, C>::operator -= (const Ca &a)
525	{
526	this->coeffs[0] -= a;
527	return *this;
528	}
529
530	template<unsigned int N, typename C>
531	template<typename Ca>
532	inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
533	poly_int<N, C>::operator *= (const Ca &a)
534	{
535	for (unsigned int i = 0; i < N; i++)
536	this->coeffs[i] *= a;
537	return *this;
538	}
539
540	template<unsigned int N, typename C>
541	inline poly_int<N, C>&
542	poly_int<N, C>::operator <<= (unsigned int a)
543	{
544	for (unsigned int i = 0; i < N; i++)
545	this->coeffs[i] <<= a;
546	return *this;
547	}
548
549	/* Return true if the polynomial value is a compile-time constant. */
550
551	template<unsigned int N, typename C>
552	inline bool
553	poly_int<N, C>::is_constant () const
554	{
555	if (N >= 2)
556	for (unsigned int i = 1; i < N; i++)
557	if (this->coeffs[i] != 0)
558	return false;
559	return true;
560	}
561
562	/* Return true if the polynomial value is a compile-time constant,
563	storing its value in CONST_VALUE if so. */
564
565	template<unsigned int N, typename C>
566	template<typename T>
567	inline typename if_lossless<T, C, bool>::type
568	poly_int<N, C>::is_constant (T *const_value) const
569	{
570	if (is_constant ())
571	{
572	*const_value = this->coeffs[0];
573	return true;
574	}
575	return false;
576	}
577
578	/* Return the value of a polynomial that is already known to be a
579	compile-time constant.
580
581	NOTE: When using this function, please add a comment above the call
582	explaining why we know the value is constant in that context. */
583
584	template<unsigned int N, typename C>
585	inline C
586	poly_int<N, C>::to_constant () const
587	{
588	gcc_checking_assert (is_constant ());
589	return this->coeffs[0];
590	}
591
592	/* Convert X to a wide_int-based polynomial in which each coefficient
593	has BITSIZE bits. If X's coefficients are smaller than BITSIZE,
594	extend them according to SGN. */
595
596	template<unsigned int N, typename C>
597	template<typename Ca>
598	inline poly_int<N, C>
599	poly_int<N, C>::from (const poly_int<N, Ca> &a, unsigned int bitsize,
600	signop sgn)
601	{
602	poly_int<N, C> r;
603	for (unsigned int i = 0; i < N; i++)
604	POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], bitsize, sgn));
605	return r;
606	}
607
608	/* Convert X to a fixed_wide_int-based polynomial, extending according
609	to SGN. */
610
611	template<unsigned int N, typename C>
612	template<typename Ca>
613	inline poly_int<N, C>
614	poly_int<N, C>::from (const poly_int<N, Ca> &a, signop sgn)
615	{
616	poly_int<N, C> r;
617	for (unsigned int i = 0; i < N; i++)
618	POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], sgn));
619	return r;
620	}
621
622	/* Return true if the coefficients of this generic_wide_int-based
623	polynomial can be represented as signed HOST_WIDE_INTs without loss
624	of precision. Store the HOST_WIDE_INT representation in *R if so. */
625
626	template<unsigned int N, typename C>
627	inline bool
628	poly_int<N, C>::to_shwi (poly_int<N, HOST_WIDE_INT> *r) const
629	{
630	for (unsigned int i = 0; i < N; i++)
631	if (!wi::fits_shwi_p (this->coeffs[i]))
632	return false;
633	for (unsigned int i = 0; i < N; i++)
634	r->coeffs[i] = this->coeffs[i].to_shwi ();
635	return true;
636	}
637
638	/* Return true if the coefficients of this generic_wide_int-based
639	polynomial can be represented as unsigned HOST_WIDE_INTs without
640	loss of precision. Store the unsigned HOST_WIDE_INT representation
641	in *R if so. */
642
643	template<unsigned int N, typename C>
644	inline bool
645	poly_int<N, C>::to_uhwi (poly_int<N, unsigned HOST_WIDE_INT> *r) const
646	{
647	for (unsigned int i = 0; i < N; i++)
648	if (!wi::fits_uhwi_p (this->coeffs[i]))
649	return false;
650	for (unsigned int i = 0; i < N; i++)
651	r->coeffs[i] = this->coeffs[i].to_uhwi ();
652	return true;
653	}
654
655	/* Force a generic_wide_int-based constant to HOST_WIDE_INT precision,
656	truncating if necessary. */
657
658	template<unsigned int N, typename C>
659	inline poly_int<N, HOST_WIDE_INT>
660	poly_int<N, C>::force_shwi () const
661	{
662	poly_int<N, HOST_WIDE_INT> r;
663	for (unsigned int i = 0; i < N; i++)
664	r.coeffs[i] = this->coeffs[i].to_shwi ();
665	return r;
666	}
667
668	/* Force a generic_wide_int-based constant to unsigned HOST_WIDE_INT precision,
669	truncating if necessary. */
670
671	template<unsigned int N, typename C>
672	inline poly_int<N, unsigned HOST_WIDE_INT>
673	poly_int<N, C>::force_uhwi () const
674	{
675	poly_int<N, unsigned HOST_WIDE_INT> r;
676	for (unsigned int i = 0; i < N; i++)
677	r.coeffs[i] = this->coeffs[i].to_uhwi ();
678	return r;
679	}
680
681	#if POLY_INT_CONVERSION
682	/* Provide a conversion operator to constants. */
683
684	template<unsigned int N, typename C>
685	inline
686	poly_int<N, C>::operator C () const
687	{
688	gcc_checking_assert (this->is_constant ());
689	return this->coeffs[0];
690	}
691	#endif
692
693	/* Return true if every coefficient of A is in the inclusive range [B, C]. */
694
695	template<typename Ca, typename Cb, typename Cc>
696	inline typename if_nonpoly<Ca, bool>::type
697	coeffs_in_range_p (const Ca &a, const Cb &b, const Cc &c)
698	{
699	return a >= b && a <= c;
700	}
701
702	template<unsigned int N, typename Ca, typename Cb, typename Cc>
703	inline typename if_nonpoly<Ca, bool>::type
704	coeffs_in_range_p (const poly_int<N, Ca> &a, const Cb &b, const Cc &c)
705	{
706	for (unsigned int i = 0; i < N; i++)
707	if (a.coeffs[i] < b || a.coeffs[i] > c)
708	return false;
709	return true;
710	}
711
712	namespace wi {
713	/* Poly version of wi::shwi, with the same interface. */
714
715	template<unsigned int N>
716	inline poly_int<N, hwi_with_prec>
717	shwi (const poly_int<N, HOST_WIDE_INT> &a, unsigned int precision)
718	{
719	poly_int<N, hwi_with_prec> r;
720	for (unsigned int i = 0; i < N; i++)
721	POLY_SET_COEFF (hwi_with_prec, r, i, wi::shwi (a.coeffs[i], precision));
722	return r;
723	}
724
725	/* Poly version of wi::uhwi, with the same interface. */
726
727	template<unsigned int N>
728	inline poly_int<N, hwi_with_prec>
729	uhwi (const poly_int<N, unsigned HOST_WIDE_INT> &a, unsigned int precision)
730	{
731	poly_int<N, hwi_with_prec> r;
732	for (unsigned int i = 0; i < N; i++)
733	POLY_SET_COEFF (hwi_with_prec, r, i, wi::uhwi (a.coeffs[i], precision));
734	return r;
735	}
736
737	/* Poly version of wi::sext, with the same interface. */
738
739	template<unsigned int N, typename Ca>
740	inline POLY_POLY_RESULT (N, Ca, Ca)
741	sext (const poly_int<N, Ca> &a, unsigned int precision)
742	{
743	typedef POLY_POLY_COEFF (Ca, Ca) C;
744	poly_int<N, C> r;
745	for (unsigned int i = 0; i < N; i++)
746	POLY_SET_COEFF (C, r, i, wi::sext (a.coeffs[i], precision));
747	return r;
748	}
749
750	/* Poly version of wi::zext, with the same interface. */
751
752	template<unsigned int N, typename Ca>
753	inline POLY_POLY_RESULT (N, Ca, Ca)
754	zext (const poly_int<N, Ca> &a, unsigned int precision)
755	{
756	typedef POLY_POLY_COEFF (Ca, Ca) C;
757	poly_int<N, C> r;
758	for (unsigned int i = 0; i < N; i++)
759	POLY_SET_COEFF (C, r, i, wi::zext (a.coeffs[i], precision));
760	return r;
761	}
762	}
763
764	template<unsigned int N, typename Ca, typename Cb>
765	inline POLY_POLY_RESULT (N, Ca, Cb)
766	operator + (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
767	{
768	typedef POLY_CAST (Ca, Cb) NCa;
769	typedef POLY_POLY_COEFF (Ca, Cb) C;
770	poly_int<N, C> r;
771	for (unsigned int i = 0; i < N; i++)
772	POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) + b.coeffs[i]);
773	return r;
774	}
775
776	template<unsigned int N, typename Ca, typename Cb>
777	inline POLY_CONST_RESULT (N, Ca, Cb)
778	operator + (const poly_int<N, Ca> &a, const Cb &b)
779	{
780	typedef POLY_CAST (Ca, Cb) NCa;
781	typedef POLY_CONST_COEFF (Ca, Cb) C;
782	poly_int<N, C> r;
783	POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) + b);
784	if (N >= 2)
785	for (unsigned int i = 1; i < N; i++)
786	POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
787	return r;
788	}
789
790	template<unsigned int N, typename Ca, typename Cb>
791	inline CONST_POLY_RESULT (N, Ca, Cb)
792	operator + (const Ca &a, const poly_int<N, Cb> &b)
793	{
794	typedef POLY_CAST (Cb, Ca) NCb;
795	typedef CONST_POLY_COEFF (Ca, Cb) C;
796	poly_int<N, C> r;
797	POLY_SET_COEFF (C, r, 0, a + NCb (b.coeffs[0]));
798	if (N >= 2)
799	for (unsigned int i = 1; i < N; i++)
800	POLY_SET_COEFF (C, r, i, NCb (b.coeffs[i]));
801	return r;
802	}
803
804	namespace wi {
805	/* Poly versions of wi::add, with the same interface. */
806
807	template<unsigned int N, typename Ca, typename Cb>
808	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
809	add (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
810	{
811	typedef WI_BINARY_RESULT (Ca, Cb) C;
812	poly_int<N, C> r;
813	for (unsigned int i = 0; i < N; i++)
814	POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i]));
815	return r;
816	}
817
818	template<unsigned int N, typename Ca, typename Cb>
819	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
820	add (const poly_int<N, Ca> &a, const Cb &b)
821	{
822	typedef WI_BINARY_RESULT (Ca, Cb) C;
823	poly_int<N, C> r;
824	POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b));
825	for (unsigned int i = 1; i < N; i++)
826	POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i],
827	wi::ints_for<Cb>::zero (b)));
828	return r;
829	}
830
831	template<unsigned int N, typename Ca, typename Cb>
832	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
833	add (const Ca &a, const poly_int<N, Cb> &b)
834	{
835	typedef WI_BINARY_RESULT (Ca, Cb) C;
836	poly_int<N, C> r;
837	POLY_SET_COEFF (C, r, 0, wi::add (a, b.coeffs[0]));
838	for (unsigned int i = 1; i < N; i++)
839	POLY_SET_COEFF (C, r, i, wi::add (wi::ints_for<Ca>::zero (a),
840	b.coeffs[i]));
841	return r;
842	}
843
844	template<unsigned int N, typename Ca, typename Cb>
845	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
846	add (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
847	signop sgn, wi::overflow_type *overflow)
848	{
849	typedef WI_BINARY_RESULT (Ca, Cb) C;
850	poly_int<N, C> r;
851	POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b.coeffs[0], sgn, overflow));
852	for (unsigned int i = 1; i < N; i++)
853	{
854	wi::overflow_type suboverflow;
855	POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i], sgn,
856	&suboverflow));
857	wi::accumulate_overflow (overflow&: *overflow, suboverflow);
858	}
859	return r;
860	}
861	}
862
863	template<unsigned int N, typename Ca, typename Cb>
864	inline POLY_POLY_RESULT (N, Ca, Cb)
865	operator - (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
866	{
867	typedef POLY_CAST (Ca, Cb) NCa;
868	typedef POLY_POLY_COEFF (Ca, Cb) C;
869	poly_int<N, C> r;
870	for (unsigned int i = 0; i < N; i++)
871	POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) - b.coeffs[i]);
872	return r;
873	}
874
875	template<unsigned int N, typename Ca, typename Cb>
876	inline POLY_CONST_RESULT (N, Ca, Cb)
877	operator - (const poly_int<N, Ca> &a, const Cb &b)
878	{
879	typedef POLY_CAST (Ca, Cb) NCa;
880	typedef POLY_CONST_COEFF (Ca, Cb) C;
881	poly_int<N, C> r;
882	POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) - b);
883	if (N >= 2)
884	for (unsigned int i = 1; i < N; i++)
885	POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
886	return r;
887	}
888
889	template<unsigned int N, typename Ca, typename Cb>
890	inline CONST_POLY_RESULT (N, Ca, Cb)
891	operator - (const Ca &a, const poly_int<N, Cb> &b)
892	{
893	typedef POLY_CAST (Cb, Ca) NCb;
894	typedef CONST_POLY_COEFF (Ca, Cb) C;
895	poly_int<N, C> r;
896	POLY_SET_COEFF (C, r, 0, a - NCb (b.coeffs[0]));
897	if (N >= 2)
898	for (unsigned int i = 1; i < N; i++)
899	POLY_SET_COEFF (C, r, i, -NCb (b.coeffs[i]));
900	return r;
901	}
902
903	namespace wi {
904	/* Poly versions of wi::sub, with the same interface. */
905
906	template<unsigned int N, typename Ca, typename Cb>
907	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
908	sub (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
909	{
910	typedef WI_BINARY_RESULT (Ca, Cb) C;
911	poly_int<N, C> r;
912	for (unsigned int i = 0; i < N; i++)
913	POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i]));
914	return r;
915	}
916
917	template<unsigned int N, typename Ca, typename Cb>
918	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
919	sub (const poly_int<N, Ca> &a, const Cb &b)
920	{
921	typedef WI_BINARY_RESULT (Ca, Cb) C;
922	poly_int<N, C> r;
923	POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b));
924	for (unsigned int i = 1; i < N; i++)
925	POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i],
926	wi::ints_for<Cb>::zero (b)));
927	return r;
928	}
929
930	template<unsigned int N, typename Ca, typename Cb>
931	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
932	sub (const Ca &a, const poly_int<N, Cb> &b)
933	{
934	typedef WI_BINARY_RESULT (Ca, Cb) C;
935	poly_int<N, C> r;
936	POLY_SET_COEFF (C, r, 0, wi::sub (a, b.coeffs[0]));
937	for (unsigned int i = 1; i < N; i++)
938	POLY_SET_COEFF (C, r, i, wi::sub (wi::ints_for<Ca>::zero (a),
939	b.coeffs[i]));
940	return r;
941	}
942
943	template<unsigned int N, typename Ca, typename Cb>
944	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
945	sub (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
946	signop sgn, wi::overflow_type *overflow)
947	{
948	typedef WI_BINARY_RESULT (Ca, Cb) C;
949	poly_int<N, C> r;
950	POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b.coeffs[0], sgn, overflow));
951	for (unsigned int i = 1; i < N; i++)
952	{
953	wi::overflow_type suboverflow;
954	POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i], sgn,
955	&suboverflow));
956	wi::accumulate_overflow (overflow&: *overflow, suboverflow);
957	}
958	return r;
959	}
960	}
961
962	template<unsigned int N, typename Ca>
963	inline POLY_POLY_RESULT (N, Ca, Ca)
964	operator - (const poly_int<N, Ca> &a)
965	{
966	typedef POLY_CAST (Ca, Ca) NCa;
967	typedef POLY_POLY_COEFF (Ca, Ca) C;
968	poly_int<N, C> r;
969	for (unsigned int i = 0; i < N; i++)
970	POLY_SET_COEFF (C, r, i, -NCa (a.coeffs[i]));
971	return r;
972	}
973
974	namespace wi {
975	/* Poly version of wi::neg, with the same interface. */
976
977	template<unsigned int N, typename Ca>
978	inline poly_int<N, WI_UNARY_RESULT (Ca)>
979	neg (const poly_int<N, Ca> &a)
980	{
981	typedef WI_UNARY_RESULT (Ca) C;
982	poly_int<N, C> r;
983	for (unsigned int i = 0; i < N; i++)
984	POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i]));
985	return r;
986	}
987
988	template<unsigned int N, typename Ca>
989	inline poly_int<N, WI_UNARY_RESULT (Ca)>
990	neg (const poly_int<N, Ca> &a, wi::overflow_type *overflow)
991	{
992	typedef WI_UNARY_RESULT (Ca) C;
993	poly_int<N, C> r;
994	POLY_SET_COEFF (C, r, 0, wi::neg (a.coeffs[0], overflow));
995	for (unsigned int i = 1; i < N; i++)
996	{
997	wi::overflow_type suboverflow;
998	POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i], &suboverflow));
999	wi::accumulate_overflow (overflow&: *overflow, suboverflow);
1000	}
1001	return r;
1002	}
1003	}
1004
1005	template<unsigned int N, typename Ca>
1006	inline POLY_POLY_RESULT (N, Ca, Ca)
1007	operator ~ (const poly_int<N, Ca> &a)
1008	{
1009	if (N >= 2)
1010	return -1 - a;
1011	return ~a.coeffs[0];
1012	}
1013
1014	template<unsigned int N, typename Ca, typename Cb>
1015	inline POLY_CONST_RESULT (N, Ca, Cb)
1016	operator * (const poly_int<N, Ca> &a, const Cb &b)
1017	{
1018	typedef POLY_CAST (Ca, Cb) NCa;
1019	typedef POLY_CONST_COEFF (Ca, Cb) C;
1020	poly_int<N, C> r;
1021	for (unsigned int i = 0; i < N; i++)
1022	POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) * b);
1023	return r;
1024	}
1025
1026	template<unsigned int N, typename Ca, typename Cb>
1027	inline CONST_POLY_RESULT (N, Ca, Cb)
1028	operator * (const Ca &a, const poly_int<N, Cb> &b)
1029	{
1030	typedef POLY_CAST (Ca, Cb) NCa;
1031	typedef CONST_POLY_COEFF (Ca, Cb) C;
1032	poly_int<N, C> r;
1033	for (unsigned int i = 0; i < N; i++)
1034	POLY_SET_COEFF (C, r, i, NCa (a) * b.coeffs[i]);
1035	return r;
1036	}
1037
1038	namespace wi {
1039	/* Poly versions of wi::mul, with the same interface. */
1040
1041	template<unsigned int N, typename Ca, typename Cb>
1042	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1043	mul (const poly_int<N, Ca> &a, const Cb &b)
1044	{
1045	typedef WI_BINARY_RESULT (Ca, Cb) C;
1046	poly_int<N, C> r;
1047	for (unsigned int i = 0; i < N; i++)
1048	POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b));
1049	return r;
1050	}
1051
1052	template<unsigned int N, typename Ca, typename Cb>
1053	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1054	mul (const Ca &a, const poly_int<N, Cb> &b)
1055	{
1056	typedef WI_BINARY_RESULT (Ca, Cb) C;
1057	poly_int<N, C> r;
1058	for (unsigned int i = 0; i < N; i++)
1059	POLY_SET_COEFF (C, r, i, wi::mul (a, b.coeffs[i]));
1060	return r;
1061	}
1062
1063	template<unsigned int N, typename Ca, typename Cb>
1064	inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1065	mul (const poly_int<N, Ca> &a, const Cb &b,
1066	signop sgn, wi::overflow_type *overflow)
1067	{
1068	typedef WI_BINARY_RESULT (Ca, Cb) C;
1069	poly_int<N, C> r;
1070	POLY_SET_COEFF (C, r, 0, wi::mul (a.coeffs[0], b, sgn, overflow));
1071	for (unsigned int i = 1; i < N; i++)
1072	{
1073	wi::overflow_type suboverflow;
1074	POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b, sgn, &suboverflow));
1075	wi::accumulate_overflow (overflow&: *overflow, suboverflow);
1076	}
1077	return r;
1078	}
1079	}
1080
1081	template<unsigned int N, typename Ca, typename Cb>
1082	inline POLY_POLY_RESULT (N, Ca, Ca)
1083	operator << (const poly_int<N, Ca> &a, const Cb &b)
1084	{
1085	typedef POLY_CAST (Ca, Ca) NCa;
1086	typedef POLY_POLY_COEFF (Ca, Ca) C;
1087	poly_int<N, C> r;
1088	for (unsigned int i = 0; i < N; i++)
1089	POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) << b);
1090	return r;
1091	}
1092
1093	namespace wi {
1094	/* Poly version of wi::lshift, with the same interface. */
1095
1096	template<unsigned int N, typename Ca, typename Cb>
1097	inline poly_int<N, WI_BINARY_RESULT (Ca, Ca)>
1098	lshift (const poly_int<N, Ca> &a, const Cb &b)
1099	{
1100	typedef WI_BINARY_RESULT (Ca, Ca) C;
1101	poly_int<N, C> r;
1102	for (unsigned int i = 0; i < N; i++)
1103	POLY_SET_COEFF (C, r, i, wi::lshift (a.coeffs[i], b));
1104	return r;
1105	}
1106	}
1107
1108	/* Poly version of sext_hwi, with the same interface. */
1109
1110	template<unsigned int N, typename C>
1111	inline poly_int<N, HOST_WIDE_INT>
1112	sext_hwi (const poly_int<N, C> &a, unsigned int precision)
1113	{
1114	poly_int<N, HOST_WIDE_INT> r;
1115	for (unsigned int i = 0; i < N; i++)
1116	r.coeffs[i] = sext_hwi (a.coeffs[i], precision);
1117	return r;
1118	}
1119
1120
1121	/* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative
1122	integer x. */
1123
1124	template<typename Ca, typename Cb>
1125	inline bool
1126	maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1)
1127	{
1128	if (a1 != b1)
1129	/* a0 + a1 * x == b0 + b1 * x
1130	==> (a1 - b1) * x == b0 - a0
1131	==> x == (b0 - a0) / (a1 - b1)
1132
1133	We need to test whether that's a valid value of x.
1134	(b0 - a0) and (a1 - b1) must not have opposite signs
1135	and the result must be integral. */
1136	return (a1 < b1
1137	? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0
1138	: b0 >= a0 && (b0 - a0) % (a1 - b1) == 0);
1139	return a0 == b0;
1140	}
1141
1142	/* Return true if a0 + a1 * x might equal b for some nonnegative
1143	integer x. */
1144
1145	template<typename Ca, typename Cb>
1146	inline bool
1147	maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b)
1148	{
1149	if (a1 != 0)
1150	/* a0 + a1 * x == b
1151	==> x == (b - a0) / a1
1152
1153	We need to test whether that's a valid value of x.
1154	(b - a0) and a1 must not have opposite signs and the
1155	result must be integral. */
1156	return (a1 < 0
1157	? b <= a0 && (a0 - b) % a1 == 0
1158	: b >= a0 && (b - a0) % a1 == 0);
1159	return a0 == b;
1160	}
1161
1162	/* Return true if A might equal B for some indeterminate values. */
1163
1164	template<unsigned int N, typename Ca, typename Cb>
1165	inline bool
1166	maybe_eq (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1167	{
1168	STATIC_ASSERT (N <= 2);
1169	if (N == 2)
1170	return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]);
1171	return a.coeffs[0] == b.coeffs[0];
1172	}
1173
1174	template<unsigned int N, typename Ca, typename Cb>
1175	inline typename if_nonpoly<Cb, bool>::type
1176	maybe_eq (const poly_int<N, Ca> &a, const Cb &b)
1177	{
1178	STATIC_ASSERT (N <= 2);
1179	if (N == 2)
1180	return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b);
1181	return a.coeffs[0] == b;
1182	}
1183
1184	template<unsigned int N, typename Ca, typename Cb>
1185	inline typename if_nonpoly<Ca, bool>::type
1186	maybe_eq (const Ca &a, const poly_int<N, Cb> &b)
1187	{
1188	STATIC_ASSERT (N <= 2);
1189	if (N == 2)
1190	return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a);
1191	return a == b.coeffs[0];
1192	}
1193
1194	template<typename Ca, typename Cb>
1195	inline typename if_nonpoly2<Ca, Cb, bool>::type
1196	maybe_eq (const Ca &a, const Cb &b)
1197	{
1198	return a == b;
1199	}
1200
1201	/* Return true if A might not equal B for some indeterminate values. */
1202
1203	template<unsigned int N, typename Ca, typename Cb>
1204	inline bool
1205	maybe_ne (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1206	{
1207	if (N >= 2)
1208	for (unsigned int i = 1; i < N; i++)
1209	if (a.coeffs[i] != b.coeffs[i])
1210	return true;
1211	return a.coeffs[0] != b.coeffs[0];
1212	}
1213
1214	template<unsigned int N, typename Ca, typename Cb>
1215	inline typename if_nonpoly<Cb, bool>::type
1216	maybe_ne (const poly_int<N, Ca> &a, const Cb &b)
1217	{
1218	if (N >= 2)
1219	for (unsigned int i = 1; i < N; i++)
1220	if (a.coeffs[i] != 0)
1221	return true;
1222	return a.coeffs[0] != b;
1223	}
1224
1225	template<unsigned int N, typename Ca, typename Cb>
1226	inline typename if_nonpoly<Ca, bool>::type
1227	maybe_ne (const Ca &a, const poly_int<N, Cb> &b)
1228	{
1229	if (N >= 2)
1230	for (unsigned int i = 1; i < N; i++)
1231	if (b.coeffs[i] != 0)
1232	return true;
1233	return a != b.coeffs[0];
1234	}
1235
1236	template<typename Ca, typename Cb>
1237	inline typename if_nonpoly2<Ca, Cb, bool>::type
1238	maybe_ne (const Ca &a, const Cb &b)
1239	{
1240	return a != b;
1241	}
1242
1243	/* Return true if A is known to be equal to B. */
1244	#define known_eq(A, B) (!maybe_ne (A, B))
1245
1246	/* Return true if A is known to be unequal to B. */
1247	#define known_ne(A, B) (!maybe_eq (A, B))
1248
1249	/* Return true if A might be less than or equal to B for some
1250	indeterminate values. */
1251
1252	template<unsigned int N, typename Ca, typename Cb>
1253	inline bool
1254	maybe_le (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1255	{
1256	if (N >= 2)
1257	for (unsigned int i = 1; i < N; i++)
1258	if (a.coeffs[i] < b.coeffs[i])
1259	return true;
1260	return a.coeffs[0] <= b.coeffs[0];
1261	}
1262
1263	template<unsigned int N, typename Ca, typename Cb>
1264	inline typename if_nonpoly<Cb, bool>::type
1265	maybe_le (const poly_int<N, Ca> &a, const Cb &b)
1266	{
1267	if (N >= 2)
1268	for (unsigned int i = 1; i < N; i++)
1269	if (a.coeffs[i] < 0)
1270	return true;
1271	return a.coeffs[0] <= b;
1272	}
1273
1274	template<unsigned int N, typename Ca, typename Cb>
1275	inline typename if_nonpoly<Ca, bool>::type
1276	maybe_le (const Ca &a, const poly_int<N, Cb> &b)
1277	{
1278	if (N >= 2)
1279	for (unsigned int i = 1; i < N; i++)
1280	if (b.coeffs[i] > 0)
1281	return true;
1282	return a <= b.coeffs[0];
1283	}
1284
1285	template<typename Ca, typename Cb>
1286	inline typename if_nonpoly2<Ca, Cb, bool>::type
1287	maybe_le (const Ca &a, const Cb &b)
1288	{
1289	return a <= b;
1290	}
1291
1292	/* Return true if A might be less than B for some indeterminate values. */
1293
1294	template<unsigned int N, typename Ca, typename Cb>
1295	inline bool
1296	maybe_lt (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1297	{
1298	if (N >= 2)
1299	for (unsigned int i = 1; i < N; i++)
1300	if (a.coeffs[i] < b.coeffs[i])
1301	return true;
1302	return a.coeffs[0] < b.coeffs[0];
1303	}
1304
1305	template<unsigned int N, typename Ca, typename Cb>
1306	inline typename if_nonpoly<Cb, bool>::type
1307	maybe_lt (const poly_int<N, Ca> &a, const Cb &b)
1308	{
1309	if (N >= 2)
1310	for (unsigned int i = 1; i < N; i++)
1311	if (a.coeffs[i] < 0)
1312	return true;
1313	return a.coeffs[0] < b;
1314	}
1315
1316	template<unsigned int N, typename Ca, typename Cb>
1317	inline typename if_nonpoly<Ca, bool>::type
1318	maybe_lt (const Ca &a, const poly_int<N, Cb> &b)
1319	{
1320	if (N >= 2)
1321	for (unsigned int i = 1; i < N; i++)
1322	if (b.coeffs[i] > 0)
1323	return true;
1324	return a < b.coeffs[0];
1325	}
1326
1327	template<typename Ca, typename Cb>
1328	inline typename if_nonpoly2<Ca, Cb, bool>::type
1329	maybe_lt (const Ca &a, const Cb &b)
1330	{
1331	return a < b;
1332	}
1333
1334	/* Return true if A may be greater than or equal to B. */
1335	#define maybe_ge(A, B) maybe_le (B, A)
1336
1337	/* Return true if A may be greater than B. */
1338	#define maybe_gt(A, B) maybe_lt (B, A)
1339
1340	/* Return true if A is known to be less than or equal to B. */
1341	#define known_le(A, B) (!maybe_gt (A, B))
1342
1343	/* Return true if A is known to be less than B. */
1344	#define known_lt(A, B) (!maybe_ge (A, B))
1345
1346	/* Return true if A is known to be greater than B. */
1347	#define known_gt(A, B) (!maybe_le (A, B))
1348
1349	/* Return true if A is known to be greater than or equal to B. */
1350	#define known_ge(A, B) (!maybe_lt (A, B))
1351
1352	/* Return true if A and B are ordered by the partial ordering known_le. */
1353
1354	template<typename T1, typename T2>
1355	inline bool
1356	ordered_p (const T1 &a, const T2 &b)
1357	{
1358	return ((poly_int_traits<T1>::num_coeffs == 1
1359	&& poly_int_traits<T2>::num_coeffs == 1)
1360	|| known_le (a, b)
1361	|| known_le (b, a));
1362	}
1363
1364	/* Assert that A and B are known to be ordered and return the minimum
1365	of the two.
1366
1367	NOTE: When using this function, please add a comment above the call
1368	explaining why we know the values are ordered in that context. */
1369
1370	template<unsigned int N, typename Ca, typename Cb>
1371	inline POLY_POLY_RESULT (N, Ca, Cb)
1372	ordered_min (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1373	{
1374	if (known_le (a, b))
1375	return a;
1376	else
1377	{
1378	if (N > 1)
1379	gcc_checking_assert (known_le (b, a));
1380	return b;
1381	}
1382	}
1383
1384	template<unsigned int N, typename Ca, typename Cb>
1385	inline CONST_POLY_RESULT (N, Ca, Cb)
1386	ordered_min (const Ca &a, const poly_int<N, Cb> &b)
1387	{
1388	if (known_le (a, b))
1389	return a;
1390	else
1391	{
1392	if (N > 1)
1393	gcc_checking_assert (known_le (b, a));
1394	return b;
1395	}
1396	}
1397
1398	template<unsigned int N, typename Ca, typename Cb>
1399	inline POLY_CONST_RESULT (N, Ca, Cb)
1400	ordered_min (const poly_int<N, Ca> &a, const Cb &b)
1401	{
1402	if (known_le (a, b))
1403	return a;
1404	else
1405	{
1406	if (N > 1)
1407	gcc_checking_assert (known_le (b, a));
1408	return b;
1409	}
1410	}
1411
1412	/* Assert that A and B are known to be ordered and return the maximum
1413	of the two.
1414
1415	NOTE: When using this function, please add a comment above the call
1416	explaining why we know the values are ordered in that context. */
1417
1418	template<unsigned int N, typename Ca, typename Cb>
1419	inline POLY_POLY_RESULT (N, Ca, Cb)
1420	ordered_max (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1421	{
1422	if (known_le (a, b))
1423	return b;
1424	else
1425	{
1426	if (N > 1)
1427	gcc_checking_assert (known_le (b, a));
1428	return a;
1429	}
1430	}
1431
1432	template<unsigned int N, typename Ca, typename Cb>
1433	inline CONST_POLY_RESULT (N, Ca, Cb)
1434	ordered_max (const Ca &a, const poly_int<N, Cb> &b)
1435	{
1436	if (known_le (a, b))
1437	return b;
1438	else
1439	{
1440	if (N > 1)
1441	gcc_checking_assert (known_le (b, a));
1442	return a;
1443	}
1444	}
1445
1446	template<unsigned int N, typename Ca, typename Cb>
1447	inline POLY_CONST_RESULT (N, Ca, Cb)
1448	ordered_max (const poly_int<N, Ca> &a, const Cb &b)
1449	{
1450	if (known_le (a, b))
1451	return b;
1452	else
1453	{
1454	if (N > 1)
1455	gcc_checking_assert (known_le (b, a));
1456	return a;
1457	}
1458	}
1459
1460	/* Return a constant lower bound on the value of A, which is known
1461	to be nonnegative. */
1462
1463	template<unsigned int N, typename Ca>
1464	inline Ca
1465	constant_lower_bound (const poly_int<N, Ca> &a)
1466	{
1467	gcc_checking_assert (known_ge (a, POLY_INT_TYPE (Ca) (0)));
1468	return a.coeffs[0];
1469	}
1470
1471	/* Return the constant lower bound of A, given that it is no less than B. */
1472
1473	template<unsigned int N, typename Ca, typename Cb>
1474	inline POLY_CONST_COEFF (Ca, Cb)
1475	constant_lower_bound_with_limit (const poly_int<N, Ca> &a, const Cb &b)
1476	{
1477	if (known_ge (a, b))
1478	return a.coeffs[0];
1479	return b;
1480	}
1481
1482	/* Return the constant upper bound of A, given that it is no greater
1483	than B. */
1484
1485	template<unsigned int N, typename Ca, typename Cb>
1486	inline POLY_CONST_COEFF (Ca, Cb)
1487	constant_upper_bound_with_limit (const poly_int<N, Ca> &a, const Cb &b)
1488	{
1489	if (known_le (a, b))
1490	return a.coeffs[0];
1491	return b;
1492	}
1493
1494	/* Return a value that is known to be no greater than A and B. This
1495	will be the greatest lower bound for some indeterminate values but
1496	not necessarily for all. */
1497
1498	template<unsigned int N, typename Ca, typename Cb>
1499	inline POLY_CONST_RESULT (N, Ca, Cb)
1500	lower_bound (const poly_int<N, Ca> &a, const Cb &b)
1501	{
1502	typedef POLY_CAST (Ca, Cb) NCa;
1503	typedef POLY_CAST (Cb, Ca) NCb;
1504	typedef POLY_INT_TYPE (Cb) ICb;
1505	typedef POLY_CONST_COEFF (Ca, Cb) C;
1506
1507	poly_int<N, C> r;
1508	POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b)));
1509	if (N >= 2)
1510	for (unsigned int i = 1; i < N; i++)
1511	POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0)));
1512	return r;
1513	}
1514
1515	template<unsigned int N, typename Ca, typename Cb>
1516	inline CONST_POLY_RESULT (N, Ca, Cb)
1517	lower_bound (const Ca &a, const poly_int<N, Cb> &b)
1518	{
1519	return lower_bound (b, a);
1520	}
1521
1522	template<unsigned int N, typename Ca, typename Cb>
1523	inline POLY_POLY_RESULT (N, Ca, Cb)
1524	lower_bound (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1525	{
1526	typedef POLY_CAST (Ca, Cb) NCa;
1527	typedef POLY_CAST (Cb, Ca) NCb;
1528	typedef POLY_POLY_COEFF (Ca, Cb) C;
1529
1530	poly_int<N, C> r;
1531	for (unsigned int i = 0; i < N; i++)
1532	POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1533	return r;
1534	}
1535
1536	template<typename Ca, typename Cb>
1537	inline CONST_CONST_RESULT (N, Ca, Cb)
1538	lower_bound (const Ca &a, const Cb &b)
1539	{
1540	return a < b ? a : b;
1541	}
1542
1543	/* Return a value that is known to be no less than A and B. This will
1544	be the least upper bound for some indeterminate values but not
1545	necessarily for all. */
1546
1547	template<unsigned int N, typename Ca, typename Cb>
1548	inline POLY_CONST_RESULT (N, Ca, Cb)
1549	upper_bound (const poly_int<N, Ca> &a, const Cb &b)
1550	{
1551	typedef POLY_CAST (Ca, Cb) NCa;
1552	typedef POLY_CAST (Cb, Ca) NCb;
1553	typedef POLY_INT_TYPE (Cb) ICb;
1554	typedef POLY_CONST_COEFF (Ca, Cb) C;
1555
1556	poly_int<N, C> r;
1557	POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b)));
1558	if (N >= 2)
1559	for (unsigned int i = 1; i < N; i++)
1560	POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0)));
1561	return r;
1562	}
1563
1564	template<unsigned int N, typename Ca, typename Cb>
1565	inline CONST_POLY_RESULT (N, Ca, Cb)
1566	upper_bound (const Ca &a, const poly_int<N, Cb> &b)
1567	{
1568	return upper_bound (b, a);
1569	}
1570
1571	template<unsigned int N, typename Ca, typename Cb>
1572	inline POLY_POLY_RESULT (N, Ca, Cb)
1573	upper_bound (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1574	{
1575	typedef POLY_CAST (Ca, Cb) NCa;
1576	typedef POLY_CAST (Cb, Ca) NCb;
1577	typedef POLY_POLY_COEFF (Ca, Cb) C;
1578
1579	poly_int<N, C> r;
1580	for (unsigned int i = 0; i < N; i++)
1581	POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1582	return r;
1583	}
1584
1585	/* Return the greatest common divisor of all nonzero coefficients, or zero
1586	if all coefficients are zero. */
1587
1588	template<unsigned int N, typename Ca>
1589	inline POLY_BINARY_COEFF (Ca, Ca)
1590	coeff_gcd (const poly_int<N, Ca> &a)
1591	{
1592	/* Find the first nonzero coefficient, stopping at 0 whatever happens. */
1593	unsigned int i;
1594	for (i = N - 1; i > 0; --i)
1595	if (a.coeffs[i] != 0)
1596	break;
1597	typedef POLY_BINARY_COEFF (Ca, Ca) C;
1598	C r = a.coeffs[i];
1599	for (unsigned int j = 0; j < i; ++j)
1600	if (a.coeffs[j] != 0)
1601	r = gcd (r, C (a.coeffs[j]));
1602	return r;
1603	}
1604
1605	/* Return a value that is a multiple of both A and B. This will be the
1606	least common multiple for some indeterminate values but necessarily
1607	for all. */
1608
1609	template<unsigned int N, typename Ca, typename Cb>
1610	POLY_CONST_RESULT (N, Ca, Cb)
1611	common_multiple (const poly_int<N, Ca> &a, Cb b)
1612	{
1613	POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a);
1614	return a * (least_common_multiple (xgcd, b) / xgcd);
1615	}
1616
1617	template<unsigned int N, typename Ca, typename Cb>
1618	inline CONST_POLY_RESULT (N, Ca, Cb)
1619	common_multiple (const Ca &a, const poly_int<N, Cb> &b)
1620	{
1621	return common_multiple (b, a);
1622	}
1623
1624	/* Return a value that is a multiple of both A and B, asserting that
1625	such a value exists. The result will be the least common multiple
1626	for some indeterminate values but necessarily for all.
1627
1628	NOTE: When using this function, please add a comment above the call
1629	explaining why we know the values have a common multiple (which might
1630	for example be because we know A / B is rational). */
1631
1632	template<unsigned int N, typename Ca, typename Cb>
1633	POLY_POLY_RESULT (N, Ca, Cb)
1634	force_common_multiple (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1635	{
1636	if (b.is_constant ())
1637	return common_multiple (a, b.coeffs[0]);
1638	if (a.is_constant ())
1639	return common_multiple (a.coeffs[0], b);
1640
1641	typedef POLY_CAST (Ca, Cb) NCa;
1642	typedef POLY_CAST (Cb, Ca) NCb;
1643	typedef POLY_BINARY_COEFF (Ca, Cb) C;
1644	typedef POLY_INT_TYPE (Ca) ICa;
1645
1646	for (unsigned int i = 1; i < N; ++i)
1647	if (a.coeffs[i] != ICa (0))
1648	{
1649	C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i]));
1650	C amul = lcm / a.coeffs[i];
1651	C bmul = lcm / b.coeffs[i];
1652	for (unsigned int j = 0; j < N; ++j)
1653	gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul);
1654	return a * amul;
1655	}
1656	gcc_unreachable ();
1657	}
1658
1659	/* Compare A and B for sorting purposes, returning -1 if A should come
1660	before B, 0 if A and B are identical, and 1 if A should come after B.
1661	This is a lexicographical compare of the coefficients in reverse order.
1662
1663	A consequence of this is that all constant sizes come before all
1664	non-constant ones, regardless of magnitude (since a size is never
1665	negative). This is what most callers want. For example, when laying
1666	data out on the stack, it's better to keep all the constant-sized
1667	data together so that it can be accessed as a constant offset from a
1668	single base. */
1669
1670	template<unsigned int N, typename Ca, typename Cb>
1671	inline int
1672	compare_sizes_for_sort (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1673	{
1674	for (unsigned int i = N; i-- > 0; )
1675	if (a.coeffs[i] != b.coeffs[i])
1676	return a.coeffs[i] < b.coeffs[i] ? -1 : 1;
1677	return 0;
1678	}
1679
1680	/* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */
1681
1682	template<unsigned int N, typename Ca, typename Cb>
1683	inline bool
1684	can_align_p (const poly_int<N, Ca> &value, Cb align)
1685	{
1686	for (unsigned int i = 1; i < N; i++)
1687	if ((value.coeffs[i] & (align - 1)) != 0)
1688	return false;
1689	return true;
1690	}
1691
1692	/* Return true if we can align VALUE up to the smallest multiple of
1693	ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */
1694
1695	template<unsigned int N, typename Ca, typename Cb>
1696	inline bool
1697	can_align_up (const poly_int<N, Ca> &value, Cb align,
1698	poly_int<N, Ca> *aligned)
1699	{
1700	if (!can_align_p (value, align))
1701	return false;
1702	*aligned = value + (-value.coeffs[0] & (align - 1));
1703	return true;
1704	}
1705
1706	/* Return true if we can align VALUE down to the largest multiple of
1707	ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */
1708
1709	template<unsigned int N, typename Ca, typename Cb>
1710	inline bool
1711	can_align_down (const poly_int<N, Ca> &value, Cb align,
1712	poly_int<N, Ca> *aligned)
1713	{
1714	if (!can_align_p (value, align))
1715	return false;
1716	*aligned = value - (value.coeffs[0] & (align - 1));
1717	return true;
1718	}
1719
1720	/* Return true if we can align A and B up to the smallest multiples of
1721	ALIGN that are >= A and B respectively, and if doing so gives the
1722	same value. */
1723
1724	template<unsigned int N, typename Ca, typename Cb, typename Cc>
1725	inline bool
1726	known_equal_after_align_up (const poly_int<N, Ca> &a,
1727	const poly_int<N, Cb> &b,
1728	Cc align)
1729	{
1730	poly_int<N, Ca> aligned_a;
1731	poly_int<N, Cb> aligned_b;
1732	return (can_align_up (a, align, &aligned_a)
1733	&& can_align_up (b, align, &aligned_b)
1734	&& known_eq (aligned_a, aligned_b));
1735	}
1736
1737	/* Return true if we can align A and B down to the largest multiples of
1738	ALIGN that are <= A and B respectively, and if doing so gives the
1739	same value. */
1740
1741	template<unsigned int N, typename Ca, typename Cb, typename Cc>
1742	inline bool
1743	known_equal_after_align_down (const poly_int<N, Ca> &a,
1744	const poly_int<N, Cb> &b,
1745	Cc align)
1746	{
1747	poly_int<N, Ca> aligned_a;
1748	poly_int<N, Cb> aligned_b;
1749	return (can_align_down (a, align, &aligned_a)
1750	&& can_align_down (b, align, &aligned_b)
1751	&& known_eq (aligned_a, aligned_b));
1752	}
1753
1754	/* Assert that we can align VALUE to ALIGN at compile time and return
1755	the smallest multiple of ALIGN that is >= VALUE.
1756
1757	NOTE: When using this function, please add a comment above the call
1758	explaining why we know the non-constant coefficients must already
1759	be a multiple of ALIGN. */
1760
1761	template<unsigned int N, typename Ca, typename Cb>
1762	inline poly_int<N, Ca>
1763	force_align_up (const poly_int<N, Ca> &value, Cb align)
1764	{
1765	gcc_checking_assert (can_align_p (value, align));
1766	return value + (-value.coeffs[0] & (align - 1));
1767	}
1768
1769	/* Assert that we can align VALUE to ALIGN at compile time and return
1770	the largest multiple of ALIGN that is <= VALUE.
1771
1772	NOTE: When using this function, please add a comment above the call
1773	explaining why we know the non-constant coefficients must already
1774	be a multiple of ALIGN. */
1775
1776	template<unsigned int N, typename Ca, typename Cb>
1777	inline poly_int<N, Ca>
1778	force_align_down (const poly_int<N, Ca> &value, Cb align)
1779	{
1780	gcc_checking_assert (can_align_p (value, align));
1781	return value - (value.coeffs[0] & (align - 1));
1782	}
1783
1784	/* Return a value <= VALUE that is a multiple of ALIGN. It will be the
1785	greatest such value for some indeterminate values but not necessarily
1786	for all. */
1787
1788	template<unsigned int N, typename Ca, typename Cb>
1789	inline poly_int<N, Ca>
1790	aligned_lower_bound (const poly_int<N, Ca> &value, Cb align)
1791	{
1792	poly_int<N, Ca> r;
1793	for (unsigned int i = 0; i < N; i++)
1794	/* This form copes correctly with more type combinations than
1795	value.coeffs[i] & -align would. */
1796	POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1797	- (value.coeffs[i] & (align - 1))));
1798	return r;
1799	}
1800
1801	/* Return a value >= VALUE that is a multiple of ALIGN. It will be the
1802	least such value for some indeterminate values but not necessarily
1803	for all. */
1804
1805	template<unsigned int N, typename Ca, typename Cb>
1806	inline poly_int<N, Ca>
1807	aligned_upper_bound (const poly_int<N, Ca> &value, Cb align)
1808	{
1809	poly_int<N, Ca> r;
1810	for (unsigned int i = 0; i < N; i++)
1811	POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1812	+ (-value.coeffs[i] & (align - 1))));
1813	return r;
1814	}
1815
1816	/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1817	down to the largest multiple of ALIGN that is <= VALUE, then divide by
1818	ALIGN.
1819
1820	NOTE: When using this function, please add a comment above the call
1821	explaining why we know the non-constant coefficients must already
1822	be a multiple of ALIGN. */
1823
1824	template<unsigned int N, typename Ca, typename Cb>
1825	inline poly_int<N, Ca>
1826	force_align_down_and_div (const poly_int<N, Ca> &value, Cb align)
1827	{
1828	gcc_checking_assert (can_align_p (value, align));
1829
1830	poly_int<N, Ca> r;
1831	POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1832	- (value.coeffs[0] & (align - 1)))
1833	/ align));
1834	if (N >= 2)
1835	for (unsigned int i = 1; i < N; i++)
1836	POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1837	return r;
1838	}
1839
1840	/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1841	up to the smallest multiple of ALIGN that is >= VALUE, then divide by
1842	ALIGN.
1843
1844	NOTE: When using this function, please add a comment above the call
1845	explaining why we know the non-constant coefficients must already
1846	be a multiple of ALIGN. */
1847
1848	template<unsigned int N, typename Ca, typename Cb>
1849	inline poly_int<N, Ca>
1850	force_align_up_and_div (const poly_int<N, Ca> &value, Cb align)
1851	{
1852	gcc_checking_assert (can_align_p (value, align));
1853
1854	poly_int<N, Ca> r;
1855	POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1856	+ (-value.coeffs[0] & (align - 1)))
1857	/ align));
1858	if (N >= 2)
1859	for (unsigned int i = 1; i < N; i++)
1860	POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1861	return r;
1862	}
1863
1864	/* Return true if we know at compile time the difference between VALUE
1865	and the equal or preceding multiple of ALIGN. Store the value in
1866	*MISALIGN if so. */
1867
1868	template<unsigned int N, typename Ca, typename Cb, typename Cm>
1869	inline bool
1870	known_misalignment (const poly_int<N, Ca> &value, Cb align, Cm *misalign)
1871	{
1872	gcc_checking_assert (align != 0);
1873	if (!can_align_p (value, align))
1874	return false;
1875	*misalign = value.coeffs[0] & (align - 1);
1876	return true;
1877	}
1878
1879	/* Return X & (Y - 1), asserting that this value is known. Please add
1880	an a comment above callers to this function to explain why the condition
1881	is known to hold. */
1882
1883	template<unsigned int N, typename Ca, typename Cb>
1884	inline POLY_BINARY_COEFF (Ca, Ca)
1885	force_get_misalignment (const poly_int<N, Ca> &a, Cb align)
1886	{
1887	gcc_checking_assert (can_align_p (a, align));
1888	return a.coeffs[0] & (align - 1);
1889	}
1890
1891	/* Return the maximum alignment that A is known to have. Return 0
1892	if A is known to be zero. */
1893
1894	template<unsigned int N, typename Ca>
1895	inline POLY_BINARY_COEFF (Ca, Ca)
1896	known_alignment (const poly_int<N, Ca> &a)
1897	{
1898	typedef POLY_BINARY_COEFF (Ca, Ca) C;
1899	C r = a.coeffs[0];
1900	for (unsigned int i = 1; i < N; ++i)
1901	r |= a.coeffs[i];
1902	return r & -r;
1903	}
1904
1905	/* Return true if we can compute A | B at compile time, storing the
1906	result in RES if so. */
1907
1908	template<unsigned int N, typename Ca, typename Cb, typename Cr>
1909	inline typename if_nonpoly<Cb, bool>::type
1910	can_ior_p (const poly_int<N, Ca> &a, Cb b, Cr *result)
1911	{
1912	/* Coefficients 1 and above must be a multiple of something greater
1913	than B. */
1914	typedef POLY_INT_TYPE (Ca) int_type;
1915	if (N >= 2)
1916	for (unsigned int i = 1; i < N; i++)
1917	if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0))
1918	return false;
1919	*result = a;
1920	result->coeffs[0] |= b;
1921	return true;
1922	}
1923
1924	/* Return true if A is a constant multiple of B, storing the
1925	multiple in *MULTIPLE if so. */
1926
1927	template<unsigned int N, typename Ca, typename Cb, typename Cm>
1928	inline typename if_nonpoly<Cb, bool>::type
1929	constant_multiple_p (const poly_int<N, Ca> &a, Cb b, Cm *multiple)
1930	{
1931	typedef POLY_CAST (Ca, Cb) NCa;
1932	typedef POLY_CAST (Cb, Ca) NCb;
1933
1934	/* Do the modulus before the constant check, to catch divide by
1935	zero errors. */
1936	if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
1937	return false;
1938	*multiple = NCa (a.coeffs[0]) / NCb (b);
1939	return true;
1940	}
1941
1942	template<unsigned int N, typename Ca, typename Cb, typename Cm>
1943	inline typename if_nonpoly<Ca, bool>::type
1944	constant_multiple_p (Ca a, const poly_int<N, Cb> &b, Cm *multiple)
1945	{
1946	typedef POLY_CAST (Ca, Cb) NCa;
1947	typedef POLY_CAST (Cb, Ca) NCb;
1948	typedef POLY_INT_TYPE (Ca) int_type;
1949
1950	/* Do the modulus before the constant check, to catch divide by
1951	zero errors. */
1952	if (NCa (a) % NCb (b.coeffs[0]) != 0
1953	|| (a != int_type (0) && !b.is_constant ()))
1954	return false;
1955	*multiple = NCa (a) / NCb (b.coeffs[0]);
1956	return true;
1957	}
1958
1959	template<unsigned int N, typename Ca, typename Cb, typename Cm>
1960	inline bool
1961	constant_multiple_p (const poly_int<N, Ca> &a,
1962	const poly_int<N, Cb> &b, Cm *multiple)
1963	{
1964	typedef POLY_CAST (Ca, Cb) NCa;
1965	typedef POLY_CAST (Cb, Ca) NCb;
1966	typedef POLY_INT_TYPE (Ca) ICa;
1967	typedef POLY_INT_TYPE (Cb) ICb;
1968	typedef POLY_BINARY_COEFF (Ca, Cb) C;
1969
1970	if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
1971	return false;
1972
1973	C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
1974	for (unsigned int i = 1; i < N; ++i)
1975	if (b.coeffs[i] == ICb (0)
1976	? a.coeffs[i] != ICa (0)
1977	: (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
1978	|| NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
1979	return false;
1980
1981	*multiple = r;
1982	return true;
1983	}
1984
1985	/* Return true if A is a constant multiple of B. */
1986
1987	template<unsigned int N, typename Ca, typename Cb>
1988	inline typename if_nonpoly<Cb, bool>::type
1989	constant_multiple_p (const poly_int<N, Ca> &a, Cb b)
1990	{
1991	typedef POLY_CAST (Ca, Cb) NCa;
1992	typedef POLY_CAST (Cb, Ca) NCb;
1993
1994	/* Do the modulus before the constant check, to catch divide by
1995	zero errors. */
1996	if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
1997	return false;
1998	return true;
1999	}
2000
2001	template<unsigned int N, typename Ca, typename Cb>
2002	inline typename if_nonpoly<Ca, bool>::type
2003	constant_multiple_p (Ca a, const poly_int<N, Cb> &b)
2004	{
2005	typedef POLY_CAST (Ca, Cb) NCa;
2006	typedef POLY_CAST (Cb, Ca) NCb;
2007	typedef POLY_INT_TYPE (Ca) int_type;
2008
2009	/* Do the modulus before the constant check, to catch divide by
2010	zero errors. */
2011	if (NCa (a) % NCb (b.coeffs[0]) != 0
2012	|| (a != int_type (0) && !b.is_constant ()))
2013	return false;
2014	return true;
2015	}
2016
2017	template<unsigned int N, typename Ca, typename Cb>
2018	inline bool
2019	constant_multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2020	{
2021	typedef POLY_CAST (Ca, Cb) NCa;
2022	typedef POLY_CAST (Cb, Ca) NCb;
2023	typedef POLY_INT_TYPE (Ca) ICa;
2024	typedef POLY_INT_TYPE (Cb) ICb;
2025	typedef POLY_BINARY_COEFF (Ca, Cb) C;
2026
2027	if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
2028	return false;
2029
2030	C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2031	for (unsigned int i = 1; i < N; ++i)
2032	if (b.coeffs[i] == ICb (0)
2033	? a.coeffs[i] != ICa (0)
2034	: (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2035	|| NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2036	return false;
2037	return true;
2038	}
2039
2040
2041	/* Return true if A is a multiple of B. */
2042
2043	template<typename Ca, typename Cb>
2044	inline typename if_nonpoly2<Ca, Cb, bool>::type
2045	multiple_p (Ca a, Cb b)
2046	{
2047	return a % b == 0;
2048	}
2049
2050	/* Return true if A is a (polynomial) multiple of B. */
2051
2052	template<unsigned int N, typename Ca, typename Cb>
2053	inline typename if_nonpoly<Cb, bool>::type
2054	multiple_p (const poly_int<N, Ca> &a, Cb b)
2055	{
2056	for (unsigned int i = 0; i < N; ++i)
2057	if (a.coeffs[i] % b != 0)
2058	return false;
2059	return true;
2060	}
2061
2062	/* Return true if A is a (constant) multiple of B. */
2063
2064	template<unsigned int N, typename Ca, typename Cb>
2065	inline typename if_nonpoly<Ca, bool>::type
2066	multiple_p (Ca a, const poly_int<N, Cb> &b)
2067	{
2068	typedef POLY_INT_TYPE (Ca) int_type;
2069
2070	/* Do the modulus before the constant check, to catch divide by
2071	potential zeros. */
2072	return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ());
2073	}
2074
2075	/* Return true if A is a (polynomial) multiple of B. This handles cases
2076	where either B is constant or the multiple is constant. */
2077
2078	template<unsigned int N, typename Ca, typename Cb>
2079	inline bool
2080	multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2081	{
2082	if (b.is_constant ())
2083	return multiple_p (a, b.coeffs[0]);
2084	POLY_BINARY_COEFF (Ca, Ca) tmp;
2085	return constant_multiple_p (a, b, &tmp);
2086	}
2087
2088	/* Return true if A is a (constant) multiple of B, storing the
2089	multiple in *MULTIPLE if so. */
2090
2091	template<typename Ca, typename Cb, typename Cm>
2092	inline typename if_nonpoly2<Ca, Cb, bool>::type
2093	multiple_p (Ca a, Cb b, Cm *multiple)
2094	{
2095	if (a % b != 0)
2096	return false;
2097	*multiple = a / b;
2098	return true;
2099	}
2100
2101	/* Return true if A is a (polynomial) multiple of B, storing the
2102	multiple in *MULTIPLE if so. */
2103
2104	template<unsigned int N, typename Ca, typename Cb, typename Cm>
2105	inline typename if_nonpoly<Cb, bool>::type
2106	multiple_p (const poly_int<N, Ca> &a, Cb b, poly_int<N, Cm> *multiple)
2107	{
2108	if (!multiple_p (a, b))
2109	return false;
2110	for (unsigned int i = 0; i < N; ++i)
2111	multiple->coeffs[i] = a.coeffs[i] / b;
2112	return true;
2113	}
2114
2115	/* Return true if B is a constant and A is a (constant) multiple of B,
2116	storing the multiple in *MULTIPLE if so. */
2117
2118	template<unsigned int N, typename Ca, typename Cb, typename Cm>
2119	inline typename if_nonpoly<Ca, bool>::type
2120	multiple_p (Ca a, const poly_int<N, Cb> &b, Cm *multiple)
2121	{
2122	typedef POLY_CAST (Ca, Cb) NCa;
2123
2124	/* Do the modulus before the constant check, to catch divide by
2125	potential zeros. */
2126	if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ()))
2127	return false;
2128	*multiple = a / b.coeffs[0];
2129	return true;
2130	}
2131
2132	/* Return true if A is a (polynomial) multiple of B, storing the
2133	multiple in *MULTIPLE if so. This handles cases where either
2134	B is constant or the multiple is constant. */
2135
2136	template<unsigned int N, typename Ca, typename Cb, typename Cm>
2137	inline bool
2138	multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2139	poly_int<N, Cm> *multiple)
2140	{
2141	if (b.is_constant ())
2142	return multiple_p (a, b.coeffs[0], multiple);
2143	return constant_multiple_p (a, b, multiple);
2144	}
2145
2146	/* Return A / B, given that A is known to be a multiple of B. */
2147
2148	template<unsigned int N, typename Ca, typename Cb>
2149	inline POLY_CONST_RESULT (N, Ca, Cb)
2150	exact_div (const poly_int<N, Ca> &a, Cb b)
2151	{
2152	typedef POLY_CONST_COEFF (Ca, Cb) C;
2153	poly_int<N, C> r;
2154	for (unsigned int i = 0; i < N; i++)
2155	{
2156	gcc_checking_assert (a.coeffs[i] % b == 0);
2157	POLY_SET_COEFF (C, r, i, a.coeffs[i] / b);
2158	}
2159	return r;
2160	}
2161
2162	/* Return A / B, given that A is known to be a multiple of B. */
2163
2164	template<unsigned int N, typename Ca, typename Cb>
2165	inline POLY_POLY_RESULT (N, Ca, Cb)
2166	exact_div (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2167	{
2168	if (b.is_constant ())
2169	return exact_div (a, b.coeffs[0]);
2170
2171	typedef POLY_CAST (Ca, Cb) NCa;
2172	typedef POLY_CAST (Cb, Ca) NCb;
2173	typedef POLY_BINARY_COEFF (Ca, Cb) C;
2174	typedef POLY_INT_TYPE (Cb) int_type;
2175
2176	gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0);
2177	C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2178	for (unsigned int i = 1; i < N; ++i)
2179	gcc_checking_assert (b.coeffs[i] == int_type (0)
2180	? a.coeffs[i] == int_type (0)
2181	: (a.coeffs[i] % b.coeffs[i] == 0
2182	&& NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r));
2183
2184	return r;
2185	}
2186
2187	/* Return true if there is some constant Q and polynomial r such that:
2188
2189	(1) a = b * Q + r
2190	(2) |b * Q| <= |a|
2191	(3) |r| < |b|
2192
2193	Store the value Q in *QUOTIENT if so. */
2194
2195	template<unsigned int N, typename Ca, typename Cb, typename Cq>
2196	inline typename if_nonpoly2<Cb, Cq, bool>::type
2197	can_div_trunc_p (const poly_int<N, Ca> &a, Cb b, Cq *quotient)
2198	{
2199	typedef POLY_CAST (Ca, Cb) NCa;
2200	typedef POLY_CAST (Cb, Ca) NCb;
2201
2202	/* Do the division before the constant check, to catch divide by
2203	zero errors. */
2204	Cq q = NCa (a.coeffs[0]) / NCb (b);
2205	if (!a.is_constant ())
2206	return false;
2207	*quotient = q;
2208	return true;
2209	}
2210
2211	template<unsigned int N, typename Ca, typename Cb, typename Cq>
2212	inline typename if_nonpoly<Cq, bool>::type
2213	can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2214	Cq *quotient)
2215	{
2216	/* We can calculate Q from the case in which the indeterminates
2217	are zero. */
2218	typedef POLY_CAST (Ca, Cb) NCa;
2219	typedef POLY_CAST (Cb, Ca) NCb;
2220	typedef POLY_INT_TYPE (Ca) ICa;
2221	typedef POLY_INT_TYPE (Cb) ICb;
2222	typedef POLY_BINARY_COEFF (Ca, Cb) C;
2223	C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2224
2225	/* Check the other coefficients and record whether the division is exact.
2226	The only difficult case is when it isn't. If we require a and b to
2227	ordered wrt zero, there can be no two coefficients of the same value
2228	that have opposite signs. This means that:
2229
2230	|a| = |a0| + |a1 * x1| + |a2 * x2| + ...
2231	|b| = |b0| + |b1 * x1| + |b2 * x2| + ...
2232
2233	The Q we've just calculated guarantees:
2234
2235	|b0 * Q| <= |a0|
2236	|a0 - b0 * Q| < |b0|
2237
2238	and so:
2239
2240	(2) |b * Q| <= |a|
2241
2242	is satisfied if:
2243
2244	|bi * xi * Q| <= |ai * xi|
2245
2246	for each i in [1, N]. This is trivially true when xi is zero.
2247	When it isn't we need:
2248
2249	(2') |bi * Q| <= |ai|
2250
2251	r is calculated as:
2252
2253	r = r0 + r1 * x1 + r2 * x2 + ...
2254	where ri = ai - bi * Q
2255
2256	Restricting to ordered a and b also guarantees that no two ris
2257	have opposite signs, so we have:
2258
2259	|r| = |r0| + |r1 * x1| + |r2 * x2| + ...
2260
2261	We know from the calculation of Q that |r0| < |b0|, so:
2262
2263	(3) |r| < |b|
2264
2265	is satisfied if:
2266
2267	(3') |ai - bi * Q| <= |bi|
2268
2269	for each i in [1, N]. */
2270	bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0;
2271	for (unsigned int i = 1; i < N; ++i)
2272	{
2273	if (b.coeffs[i] == ICb (0))
2274	{
2275	/* For bi == 0 we simply need: (3') |ai| == 0. */
2276	if (a.coeffs[i] != ICa (0))
2277	return false;
2278	}
2279	else
2280	{
2281	/* The only unconditional arithmetic that we can do on ai,
2282	bi and Q is ai / bi and ai % bi. (ai == minimum int and
2283	bi == -1 would be UB in the caller.) Anything else runs
2284	the risk of overflow. */
2285	auto qi = NCa (a.coeffs[i]) / NCb (b.coeffs[i]);
2286	auto ri = NCa (a.coeffs[i]) % NCb (b.coeffs[i]);
2287	/* (2') and (3') are satisfied when ai /[trunc] bi == q.
2288	So is the stricter condition |ai - bi * Q| < |bi|. */
2289	if (qi == q)
2290	rem_p |= (ri != 0);
2291	/* The only other case is when:
2292
2293	|bi * Q| + |bi| = |ai| (for (2'))
2294	and |ai - bi * Q| = |bi| (for (3'))
2295
2296	The first is equivalent to |bi|(|Q| + 1) == |ai|.
2297	The second requires ai == bi * (Q + 1) or ai == bi * (Q - 1). */
2298	else if (ri != 0)
2299	return false;
2300	else if (q <= 0 && qi < q && qi + 1 == q)
2301	;
2302	else if (q >= 0 && qi > q && qi - 1 == q)
2303	;
2304	else
2305	return false;
2306	}
2307	}
2308
2309	/* If the division isn't exact, require both values to be ordered wrt 0,
2310	so that we can guarantee conditions (2) and (3) for all indeterminate
2311	values. */
2312	if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0))))
2313	return false;
2314
2315	*quotient = q;
2316	return true;
2317	}
2318
2319	/* Likewise, but also store r in *REMAINDER. */
2320
2321	template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2322	inline typename if_nonpoly<Cq, bool>::type
2323	can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2324	Cq *quotient, Cr *remainder)
2325	{
2326	if (!can_div_trunc_p (a, b, quotient))
2327	return false;
2328	*remainder = a - *quotient * b;
2329	return true;
2330	}
2331
2332	/* Return true if there is some polynomial q and constant R such that:
2333
2334	(1) a = B * q + R
2335	(2) |B * q| <= |a|
2336	(3) |R| < |B|
2337
2338	Store the value q in *QUOTIENT if so. */
2339
2340	template<unsigned int N, typename Ca, typename Cb, typename Cq>
2341	inline typename if_nonpoly<Cb, bool>::type
2342	can_div_trunc_p (const poly_int<N, Ca> &a, Cb b,
2343	poly_int<N, Cq> *quotient)
2344	{
2345	/* The remainder must be constant. */
2346	for (unsigned int i = 1; i < N; ++i)
2347	if (a.coeffs[i] % b != 0)
2348	return false;
2349	for (unsigned int i = 0; i < N; ++i)
2350	quotient->coeffs[i] = a.coeffs[i] / b;
2351	return true;
2352	}
2353
2354	/* Likewise, but also store R in *REMAINDER. */
2355
2356	template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2357	inline typename if_nonpoly<Cb, bool>::type
2358	can_div_trunc_p (const poly_int<N, Ca> &a, Cb b,
2359	poly_int<N, Cq> *quotient, Cr *remainder)
2360	{
2361	if (!can_div_trunc_p (a, b, quotient))
2362	return false;
2363	*remainder = a.coeffs[0] % b;
2364	return true;
2365	}
2366
2367	/* Return true if we can compute A / B at compile time, rounding towards zero.
2368	Store the result in QUOTIENT if so.
2369
2370	This handles cases in which either B is constant or the result is
2371	constant. */
2372
2373	template<unsigned int N, typename Ca, typename Cb, typename Cq>
2374	inline bool
2375	can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2376	poly_int<N, Cq> *quotient)
2377	{
2378	if (b.is_constant ())
2379	return can_div_trunc_p (a, b.coeffs[0], quotient);
2380	if (!can_div_trunc_p (a, b, &quotient->coeffs[0]))
2381	return false;
2382	for (unsigned int i = 1; i < N; ++i)
2383	quotient->coeffs[i] = 0;
2384	return true;
2385	}
2386
2387	/* Return true if there is some constant Q and polynomial r such that:
2388
2389	(1) a = b * Q + r
2390	(2) |a| <= |b * Q|
2391	(3) |r| < |b|
2392
2393	Store the value Q in *QUOTIENT if so. */
2394
2395	template<unsigned int N, typename Ca, typename Cb, typename Cq>
2396	inline typename if_nonpoly<Cq, bool>::type
2397	can_div_away_from_zero_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2398	Cq *quotient)
2399	{
2400	if (!can_div_trunc_p (a, b, quotient))
2401	return false;
2402	if (maybe_ne (*quotient * b, a))
2403	*quotient += (*quotient < 0 ? -1 : 1);
2404	return true;
2405	}
2406
2407	/* Use print_dec to print VALUE to FILE, where SGN is the sign
2408	of the values. */
2409
2410	template<unsigned int N, typename C>
2411	void
2412	print_dec (const poly_int<N, C> &value, FILE *file, signop sgn)
2413	{
2414	if (value.is_constant ())
2415	print_dec (value.coeffs[0], file, sgn);
2416	else
2417	{
2418	fprintf (stream: file, format: "[");
2419	for (unsigned int i = 0; i < N; ++i)
2420	{
2421	print_dec (value.coeffs[i], file, sgn);
2422	fputc (c: i == N - 1 ? ']' : ',', stream: file);
2423	}
2424	}
2425	}
2426
2427	/* Likewise without the signop argument, for coefficients that have an
2428	inherent signedness. */
2429
2430	template<unsigned int N, typename C>
2431	void
2432	print_dec (const poly_int<N, C> &value, FILE *file)
2433	{
2434	STATIC_ASSERT (poly_coeff_traits<C>::signedness >= 0);
2435	print_dec (value, file,
2436	poly_coeff_traits<C>::signedness ? SIGNED : UNSIGNED);
2437	}
2438
2439	/* Use print_hex to print VALUE to FILE. */
2440
2441	template<unsigned int N, typename C>
2442	void
2443	print_hex (const poly_int<N, C> &value, FILE *file)
2444	{
2445	if (value.is_constant ())
2446	print_hex (value.coeffs[0], file);
2447	else
2448	{
2449	fprintf (stream: file, format: "[");
2450	for (unsigned int i = 0; i < N; ++i)
2451	{
2452	print_hex (value.coeffs[i], file);
2453	fputc (c: i == N - 1 ? ']' : ',', stream: file);
2454	}
2455	}
2456	}
2457
2458	/* Helper for calculating the distance between two points P1 and P2,
2459	in cases where known_le (P1, P2). T1 and T2 are the types of the
2460	two positions, in either order. The coefficients of P2 - P1 have
2461	type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2
2462	have C++ primitive type, otherwise P2 - P1 has its usual
2463	wide-int-based type.
2464
2465	The actual subtraction should look something like this:
2466
2467	typedef poly_span_traits<T1, T2> span_traits;
2468	span_traits::cast (P2) - span_traits::cast (P1)
2469
2470	Applying the cast before the subtraction avoids undefined overflow
2471	for signed T1 and T2.
2472
2473	The implementation of the cast tries to avoid unnecessary arithmetic
2474	or copying. */
2475	template<typename T1, typename T2,
2476	typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2),
2477	unsigned HOST_WIDE_INT)>
2478	struct poly_span_traits
2479	{
2480	template<typename T>
2481	static const T &cast (const T &x) { return x; }
2482	};
2483
2484	template<typename T1, typename T2>
2485	struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT>
2486	{
2487	template<typename T>
2488	static typename if_nonpoly<T, unsigned HOST_WIDE_INT>::type
2489	cast (const T &x) { return x; }
2490
2491	template<unsigned int N, typename T>
2492	static poly_int<N, unsigned HOST_WIDE_INT>
2493	cast (const poly_int<N, T> &x) { return x; }
2494	};
2495
2496	/* Return true if SIZE represents a known size, assuming that all-ones
2497	indicates an unknown size. */
2498
2499	template<typename T>
2500	inline bool
2501	known_size_p (const T &a)
2502	{
2503	return maybe_ne (a, POLY_INT_TYPE (T) (-1));
2504	}
2505
2506	/* Return true if range [POS, POS + SIZE) might include VAL.
2507	SIZE can be the special value -1, in which case the range is
2508	open-ended. */
2509
2510	template<typename T1, typename T2, typename T3>
2511	inline bool
2512	maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2513	{
2514	typedef poly_span_traits<T1, T2> start_span;
2515	typedef poly_span_traits<T3, T3> size_span;
2516	if (known_lt (val, pos))
2517	return false;
2518	if (!known_size_p (size))
2519	return true;
2520	if ((poly_int_traits<T1>::num_coeffs > 1
2521	|| poly_int_traits<T2>::num_coeffs > 1)
2522	&& maybe_lt (val, pos))
2523	/* In this case we don't know whether VAL >= POS is true at compile
2524	time, so we can't prove that VAL >= POS + SIZE. */
2525	return true;
2526	return maybe_lt (start_span::cast (val) - start_span::cast (pos),
2527	size_span::cast (size));
2528	}
2529
2530	/* Return true if range [POS, POS + SIZE) is known to include VAL.
2531	SIZE can be the special value -1, in which case the range is
2532	open-ended. */
2533
2534	template<typename T1, typename T2, typename T3>
2535	inline bool
2536	known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2537	{
2538	typedef poly_span_traits<T1, T2> start_span;
2539	typedef poly_span_traits<T3, T3> size_span;
2540	return (known_size_p (size)
2541	&& known_ge (val, pos)
2542	&& known_lt (start_span::cast (val) - start_span::cast (pos),
2543	size_span::cast (size)));
2544	}
2545
2546	/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2547	might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which
2548	case the range is open-ended. */
2549
2550	template<typename T1, typename T2, typename T3, typename T4>
2551	inline bool
2552	ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1,
2553	const T3 &pos2, const T4 &size2)
2554	{
2555	if (maybe_in_range_p (pos2, pos1, size1))
2556	return maybe_ne (size2, POLY_INT_TYPE (T4) (0));
2557	if (maybe_in_range_p (pos1, pos2, size2))
2558	return maybe_ne (size1, POLY_INT_TYPE (T2) (0));
2559	return false;
2560	}
2561
2562	/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2563	are known to overlap. SIZE1 and/or SIZE2 can be the special value -1,
2564	in which case the range is open-ended. */
2565
2566	template<typename T1, typename T2, typename T3, typename T4>
2567	inline bool
2568	ranges_known_overlap_p (const T1 &pos1, const T2 &size1,
2569	const T3 &pos2, const T4 &size2)
2570	{
2571	typedef poly_span_traits<T1, T3> start_span;
2572	typedef poly_span_traits<T2, T2> size1_span;
2573	typedef poly_span_traits<T4, T4> size2_span;
2574	/* known_gt (POS1 + SIZE1, POS2) [infinite precision]
2575	--> known_gt (SIZE1, POS2 - POS1) [infinite precision]
2576	--> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision]
2577	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative
2578	--> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))).
2579
2580	Using the saturating subtraction enforces that SIZE1 must be
2581	nonzero, since known_gt (0, x) is false for all nonnegative x.
2582	If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing
2583	indeterminate number I makes the unsaturated condition easier to
2584	satisfy, so using a saturated coefficient of zero tests the case in
2585	which the indeterminate is zero (the minimum value). */
2586	return (known_size_p (size1)
2587	&& known_size_p (size2)
2588	&& known_lt (start_span::cast (pos2)
2589	- start_span::cast (lower_bound (pos1, pos2)),
2590	size1_span::cast (size1))
2591	&& known_lt (start_span::cast (pos1)
2592	- start_span::cast (lower_bound (pos1, pos2)),
2593	size2_span::cast (size2)));
2594	}
2595
2596	/* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of
2597	[POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1,
2598	in which case the range is open-ended. */
2599
2600	template<typename T1, typename T2, typename T3, typename T4>
2601	inline bool
2602	known_subrange_p (const T1 &pos1, const T2 &size1,
2603	const T3 &pos2, const T4 &size2)
2604	{
2605	typedef typename poly_int_traits<T2>::coeff_type C2;
2606	typedef poly_span_traits<T1, T3> start_span;
2607	typedef poly_span_traits<T2, T4> size_span;
2608	return (known_gt (size1, POLY_INT_TYPE (T2) (0))
2609	&& (poly_coeff_traits<C2>::signedness > 0
2610	|| known_size_p (size1))
2611	&& known_size_p (size2)
2612	&& known_ge (pos1, pos2)
2613	&& known_le (size1, size2)
2614	&& known_le (start_span::cast (pos1) - start_span::cast (pos2),
2615	size_span::cast (size2) - size_span::cast (size1)));
2616	}
2617
2618	/* Return true if the endpoint of the range [POS, POS + SIZE) can be
2619	stored in a T, or if SIZE is the special value -1, which makes the
2620	range open-ended. */
2621
2622	template<typename T>
2623	inline typename if_nonpoly<T, bool>::type
2624	endpoint_representable_p (const T &pos, const T &size)
2625	{
2626	return (!known_size_p (size)
2627	|| pos <= poly_coeff_traits<T>::max_value - size);
2628	}
2629
2630	template<unsigned int N, typename C>
2631	inline bool
2632	endpoint_representable_p (const poly_int<N, C> &pos,
2633	const poly_int<N, C> &size)
2634	{
2635	if (known_size_p (size))
2636	for (unsigned int i = 0; i < N; ++i)
2637	if (pos.coeffs[i] > poly_coeff_traits<C>::max_value - size.coeffs[i])
2638	return false;
2639	return true;
2640	}
2641
2642	template<unsigned int N, typename C>
2643	void
2644	gt_ggc_mx (poly_int<N, C> *)
2645	{
2646	}
2647
2648	template<unsigned int N, typename C>
2649	void
2650	gt_pch_nx (poly_int<N, C> *)
2651	{
2652	}
2653
2654	template<unsigned int N, typename C>
2655	void
2656	gt_pch_nx (poly_int<N, C> *, gt_pointer_operator, void *)
2657	{
2658	}
2659
2660	#undef POLY_SET_COEFF
2661	#undef POLY_INT_TYPE
2662	#undef POLY_BINARY_COEFF
2663	#undef CONST_CONST_RESULT
2664	#undef POLY_CONST_RESULT
2665	#undef CONST_POLY_RESULT
2666	#undef POLY_POLY_RESULT
2667	#undef POLY_CONST_COEFF
2668	#undef CONST_POLY_COEFF
2669	#undef POLY_POLY_COEFF
2670
2671	#endif
2672