1 /* Polynomial integer classes.
2 Copyright (C) 2014-2022 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
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.
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. */
29 #ifndef HAVE_POLY_INT_H
30 #define HAVE_POLY_INT_H
32 template<unsigned int N, typename T> struct poly_int_pod;
33 template<unsigned int N, typename T> class poly_int;
35 /* poly_coeff_traiits<T> describes the properties of a poly_int
38 - poly_coeff_traits<T1>::rank is less than poly_coeff_traits<T2>::rank
39 if T1 can promote to T2. For C-like types the rank is:
41 (2 * number of bytes) + (unsigned ? 1 : 0)
43 wide_ints don't have a normal rank and so use a value of INT_MAX.
44 Any fixed-width integer should be promoted to wide_int if possible
45 and lead to an error otherwise.
47 - poly_coeff_traits<T>::int_type is the type to which an integer
48 literal should be cast before comparing it with T.
50 - poly_coeff_traits<T>::precision is the number of bits that T can hold.
52 - poly_coeff_traits<T>::signedness is:
55 -1 if T has no inherent sign (as for wide_int).
57 - poly_coeff_traits<T>::max_value, if defined, is the maximum value of T.
59 - poly_coeff_traits<T>::result is a type that can hold results of
60 operations on T. This is different from T itself in cases where T
61 is the result of an accessor like wi::to_offset. */
62 template<typename T, wi::precision_type = wi::int_traits<T>::precision_type>
63 struct poly_coeff_traits;
66 struct poly_coeff_traits<T, wi::FLEXIBLE_PRECISION>
70 static const int signedness = (T (0) >= T (-1));
71 static const int precision = sizeof (T) * CHAR_BIT;
72 static const T max_value = (signedness
73 ? ((T (1) << (precision - 2))
74 + ((T (1) << (precision - 2)) - 1))
76 static const int rank = sizeof (T) * 2 + !signedness;
80 struct poly_coeff_traits<T, wi::VAR_PRECISION>
84 static const int signedness = -1;
85 static const int precision = WIDE_INT_MAX_PRECISION;
86 static const int rank = INT_MAX;
90 struct poly_coeff_traits<T, wi::CONST_PRECISION>
92 typedef WI_UNARY_RESULT (T) result;
94 /* These types are always signed. */
95 static const int signedness = 1;
96 static const int precision = wi::int_traits<T>::precision;
97 static const int rank = precision * 2 / CHAR_BIT;
100 /* Information about a pair of coefficient types. */
101 template<typename T1, typename T2>
102 struct poly_coeff_pair_traits
104 /* True if T1 can represent all the values of T2.
108 - T1 should be a type with the same signedness as T2 and no less
109 precision. This allows things like int16_t -> int16_t and
110 uint32_t -> uint64_t.
112 - T1 should be signed, T2 should be unsigned, and T1 should be
113 wider than T2. This allows things like uint16_t -> int32_t.
115 This rules out cases in which T1 has less precision than T2 or where
116 the conversion would reinterpret the top bit. E.g. int16_t -> uint32_t
117 can be dangerous and should have an explicit cast if deliberate. */
118 static const bool lossless_p = (poly_coeff_traits<T1>::signedness
119 == poly_coeff_traits<T2>::signedness
120 ? (poly_coeff_traits<T1>::precision
121 >= poly_coeff_traits<T2>::precision)
122 : (poly_coeff_traits<T1>::signedness == 1
123 && poly_coeff_traits<T2>::signedness == 0
124 && (poly_coeff_traits<T1>::precision
125 > poly_coeff_traits<T2>::precision)));
127 /* 0 if T1 op T2 should promote to HOST_WIDE_INT,
128 1 if T1 op T2 should promote to unsigned HOST_WIDE_INT,
129 2 if T1 op T2 should use wide-int rules. */
130 #define RANK(X) poly_coeff_traits<X>::rank
131 static const int result_kind
132 = ((RANK (T1) <= RANK (HOST_WIDE_INT)
133 && RANK (T2) <= RANK (HOST_WIDE_INT))
135 : (RANK (T1) <= RANK (unsigned HOST_WIDE_INT)
136 && RANK (T2) <= RANK (unsigned HOST_WIDE_INT))
141 /* SFINAE class that makes T3 available as "type" if T2 can represent all the
143 template<typename T1, typename T2, typename T3,
144 bool lossless_p = poly_coeff_pair_traits<T1, T2>::lossless_p>
146 template<typename T1, typename T2, typename T3>
147 struct if_lossless<T1, T2, T3, true>
152 /* poly_int_traits<T> describes an integer type T that might be polynomial
155 - poly_int_traits<T>::is_poly is true if T is a poly_int-based type
158 - poly_int_traits<T>::num_coeffs gives the number of coefficients in T
159 if T is a poly_int and 1 otherwise.
161 - poly_int_traits<T>::coeff_type gives the coefficent type of T if T
162 is a poly_int and T itself otherwise
164 - poly_int_traits<T>::int_type is a shorthand for
165 typename poly_coeff_traits<coeff_type>::int_type. */
167 struct poly_int_traits
169 static const bool is_poly = false;
170 static const unsigned int num_coeffs = 1;
171 typedef T coeff_type;
172 typedef typename poly_coeff_traits<T>::int_type int_type;
174 template<unsigned int N, typename C>
175 struct poly_int_traits<poly_int_pod<N, C> >
177 static const bool is_poly = true;
178 static const unsigned int num_coeffs = N;
179 typedef C coeff_type;
180 typedef typename poly_coeff_traits<C>::int_type int_type;
182 template<unsigned int N, typename C>
183 struct poly_int_traits<poly_int<N, C> > : poly_int_traits<poly_int_pod<N, C> >
187 /* SFINAE class that makes T2 available as "type" if T1 is a non-polynomial
189 template<typename T1, typename T2 = T1,
190 bool is_poly = poly_int_traits<T1>::is_poly>
191 struct if_nonpoly {};
192 template<typename T1, typename T2>
193 struct if_nonpoly<T1, T2, false>
198 /* SFINAE class that makes T3 available as "type" if both T1 and T2 are
199 non-polynomial types. */
200 template<typename T1, typename T2, typename T3,
201 bool is_poly1 = poly_int_traits<T1>::is_poly,
202 bool is_poly2 = poly_int_traits<T2>::is_poly>
203 struct if_nonpoly2 {};
204 template<typename T1, typename T2, typename T3>
205 struct if_nonpoly2<T1, T2, T3, false, false>
210 /* SFINAE class that makes T2 available as "type" if T1 is a polynomial
212 template<typename T1, typename T2 = T1,
213 bool is_poly = poly_int_traits<T1>::is_poly>
215 template<typename T1, typename T2>
216 struct if_poly<T1, T2, true>
221 /* poly_result<T1, T2> describes the result of an operation on two
222 types T1 and T2, where at least one of the types is polynomial:
224 - poly_result<T1, T2>::type gives the result type for the operation.
225 The intention is to provide normal C-like rules for integer ranks,
226 except that everything smaller than HOST_WIDE_INT promotes to
229 - poly_result<T1, T2>::cast is the type to which an operand of type
230 T1 should be cast before doing the operation, to ensure that
231 the operation is done at the right precision. Casting to
232 poly_result<T1, T2>::type would also work, but casting to this
233 type is more efficient. */
234 template<typename T1, typename T2 = T1,
235 int result_kind = poly_coeff_pair_traits<T1, T2>::result_kind>
238 /* Promote pair to HOST_WIDE_INT. */
239 template<typename T1, typename T2>
240 struct poly_result<T1, T2, 0>
242 typedef HOST_WIDE_INT type;
243 /* T1 and T2 are primitive types, so cast values to T before operating
248 /* Promote pair to unsigned HOST_WIDE_INT. */
249 template<typename T1, typename T2>
250 struct poly_result<T1, T2, 1>
252 typedef unsigned HOST_WIDE_INT type;
253 /* T1 and T2 are primitive types, so cast values to T before operating
258 /* Use normal wide-int rules. */
259 template<typename T1, typename T2>
260 struct poly_result<T1, T2, 2>
262 typedef WI_BINARY_RESULT (T1, T2) type;
263 /* Don't cast values before operating on them; leave the wi:: routines
264 to handle promotion as necessary. */
265 typedef const T1 &cast;
268 /* The coefficient type for the result of a binary operation on two
269 poly_ints, the first of which has coefficients of type C1 and the
270 second of which has coefficients of type C2. */
271 #define POLY_POLY_COEFF(C1, C2) typename poly_result<C1, C2>::type
273 /* Enforce that T2 is non-polynomial and provide the cofficient type of
274 the result of a binary operation in which the first operand is a
275 poly_int with coefficients of type C1 and the second operand is
276 a constant of type T2. */
277 #define POLY_CONST_COEFF(C1, T2) \
278 POLY_POLY_COEFF (C1, typename if_nonpoly<T2>::type)
280 /* Likewise in reverse. */
281 #define CONST_POLY_COEFF(T1, C2) \
282 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, C2)
284 /* The result type for a binary operation on poly_int<N, C1> and
286 #define POLY_POLY_RESULT(N, C1, C2) poly_int<N, POLY_POLY_COEFF (C1, C2)>
288 /* Enforce that T2 is non-polynomial and provide the result type
289 for a binary operation on poly_int<N, C1> and T2. */
290 #define POLY_CONST_RESULT(N, C1, T2) poly_int<N, POLY_CONST_COEFF (C1, T2)>
292 /* Enforce that T1 is non-polynomial and provide the result type
293 for a binary operation on T1 and poly_int<N, C2>. */
294 #define CONST_POLY_RESULT(N, T1, C2) poly_int<N, CONST_POLY_COEFF (T1, C2)>
296 /* Enforce that T1 and T2 are non-polynomial and provide the result type
297 for a binary operation on T1 and T2. */
298 #define CONST_CONST_RESULT(N, T1, T2) \
299 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, \
300 typename if_nonpoly<T2>::type)
302 /* The type to which a coefficient of type C1 should be cast before
303 using it in a binary operation with a coefficient of type C2. */
304 #define POLY_CAST(C1, C2) typename poly_result<C1, C2>::cast
306 /* Provide the coefficient type for the result of T1 op T2, where T1
307 and T2 can be polynomial or non-polynomial. */
308 #define POLY_BINARY_COEFF(T1, T2) \
309 typename poly_result<typename poly_int_traits<T1>::coeff_type, \
310 typename poly_int_traits<T2>::coeff_type>::type
312 /* The type to which an integer constant should be cast before
313 comparing it with T. */
314 #define POLY_INT_TYPE(T) typename poly_int_traits<T>::int_type
316 /* RES is a poly_int result that has coefficients of type C and that
317 is being built up a coefficient at a time. Set coefficient number I
318 to VALUE in the most efficient way possible.
320 For primitive C it is better to assign directly, since it avoids
321 any further calls and so is more efficient when the compiler is
322 built at -O0. But for wide-int based C it is better to construct
323 the value in-place. This means that calls out to a wide-int.cc
324 routine can take the address of RES rather than the address of
327 The dummy self-comparison against C * is just a way of checking
328 that C gives the right type. */
329 #define POLY_SET_COEFF(C, RES, I, VALUE) \
330 ((void) (&(RES).coeffs[0] == (C *) (void *) &(RES).coeffs[0]), \
331 wi::int_traits<C>::precision_type == wi::FLEXIBLE_PRECISION \
332 ? (void) ((RES).coeffs[I] = VALUE) \
333 : (void) ((RES).coeffs[I].~C (), new (&(RES).coeffs[I]) C (VALUE)))
335 /* A base POD class for polynomial integers. The polynomial has N
336 coefficients of type C. */
337 template<unsigned int N, typename C>
341 template<typename Ca>
342 poly_int_pod &operator = (const poly_int_pod<N, Ca> &);
343 template<typename Ca>
344 typename if_nonpoly<Ca, poly_int_pod>::type &operator = (const Ca &);
346 template<typename Ca>
347 poly_int_pod &operator += (const poly_int_pod<N, Ca> &);
348 template<typename Ca>
349 typename if_nonpoly<Ca, poly_int_pod>::type &operator += (const Ca &);
351 template<typename Ca>
352 poly_int_pod &operator -= (const poly_int_pod<N, Ca> &);
353 template<typename Ca>
354 typename if_nonpoly<Ca, poly_int_pod>::type &operator -= (const Ca &);
356 template<typename Ca>
357 typename if_nonpoly<Ca, poly_int_pod>::type &operator *= (const Ca &);
359 poly_int_pod &operator <<= (unsigned int);
361 bool is_constant () const;
364 typename if_lossless<T, C, bool>::type is_constant (T *) const;
366 C to_constant () const;
368 template<typename Ca>
369 static poly_int<N, C> from (const poly_int_pod<N, Ca> &, unsigned int,
371 template<typename Ca>
372 static poly_int<N, C> from (const poly_int_pod<N, Ca> &, signop);
374 bool to_shwi (poly_int_pod<N, HOST_WIDE_INT> *) const;
375 bool to_uhwi (poly_int_pod<N, unsigned HOST_WIDE_INT> *) const;
376 poly_int<N, HOST_WIDE_INT> force_shwi () const;
377 poly_int<N, unsigned HOST_WIDE_INT> force_uhwi () const;
379 #if POLY_INT_CONVERSION
386 template<unsigned int N, typename C>
387 template<typename Ca>
388 inline poly_int_pod<N, C>&
389 poly_int_pod<N, C>::operator = (const poly_int_pod<N, Ca> &a)
391 for (unsigned int i = 0; i < N; i++)
392 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
396 template<unsigned int N, typename C>
397 template<typename Ca>
398 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
399 poly_int_pod<N, C>::operator = (const Ca &a)
401 POLY_SET_COEFF (C, *this, 0, a);
403 for (unsigned int i = 1; i < N; i++)
404 POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
408 template<unsigned int N, typename C>
409 template<typename Ca>
410 inline poly_int_pod<N, C>&
411 poly_int_pod<N, C>::operator += (const poly_int_pod<N, Ca> &a)
413 for (unsigned int i = 0; i < N; i++)
414 this->coeffs[i] += a.coeffs[i];
418 template<unsigned int N, typename C>
419 template<typename Ca>
420 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
421 poly_int_pod<N, C>::operator += (const Ca &a)
423 this->coeffs[0] += a;
427 template<unsigned int N, typename C>
428 template<typename Ca>
429 inline poly_int_pod<N, C>&
430 poly_int_pod<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
432 for (unsigned int i = 0; i < N; i++)
433 this->coeffs[i] -= a.coeffs[i];
437 template<unsigned int N, typename C>
438 template<typename Ca>
439 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
440 poly_int_pod<N, C>::operator -= (const Ca &a)
442 this->coeffs[0] -= a;
446 template<unsigned int N, typename C>
447 template<typename Ca>
448 inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type &
449 poly_int_pod<N, C>::operator *= (const Ca &a)
451 for (unsigned int i = 0; i < N; i++)
452 this->coeffs[i] *= a;
456 template<unsigned int N, typename C>
457 inline poly_int_pod<N, C>&
458 poly_int_pod<N, C>::operator <<= (unsigned int a)
460 for (unsigned int i = 0; i < N; i++)
461 this->coeffs[i] <<= a;
465 /* Return true if the polynomial value is a compile-time constant. */
467 template<unsigned int N, typename C>
469 poly_int_pod<N, C>::is_constant () const
472 for (unsigned int i = 1; i < N; i++)
473 if (this->coeffs[i] != 0)
478 /* Return true if the polynomial value is a compile-time constant,
479 storing its value in CONST_VALUE if so. */
481 template<unsigned int N, typename C>
483 inline typename if_lossless<T, C, bool>::type
484 poly_int_pod<N, C>::is_constant (T *const_value) const
488 *const_value = this->coeffs[0];
494 /* Return the value of a polynomial that is already known to be a
495 compile-time constant.
497 NOTE: When using this function, please add a comment above the call
498 explaining why we know the value is constant in that context. */
500 template<unsigned int N, typename C>
502 poly_int_pod<N, C>::to_constant () const
504 gcc_checking_assert (is_constant ());
505 return this->coeffs[0];
508 /* Convert X to a wide_int-based polynomial in which each coefficient
509 has BITSIZE bits. If X's coefficients are smaller than BITSIZE,
510 extend them according to SGN. */
512 template<unsigned int N, typename C>
513 template<typename Ca>
514 inline poly_int<N, C>
515 poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a,
516 unsigned int bitsize, signop sgn)
519 for (unsigned int i = 0; i < N; i++)
520 POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], bitsize, sgn));
524 /* Convert X to a fixed_wide_int-based polynomial, extending according
527 template<unsigned int N, typename C>
528 template<typename Ca>
529 inline poly_int<N, C>
530 poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a, signop sgn)
533 for (unsigned int i = 0; i < N; i++)
534 POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], sgn));
538 /* Return true if the coefficients of this generic_wide_int-based
539 polynomial can be represented as signed HOST_WIDE_INTs without loss
540 of precision. Store the HOST_WIDE_INT representation in *R if so. */
542 template<unsigned int N, typename C>
544 poly_int_pod<N, C>::to_shwi (poly_int_pod<N, HOST_WIDE_INT> *r) const
546 for (unsigned int i = 0; i < N; i++)
547 if (!wi::fits_shwi_p (this->coeffs[i]))
549 for (unsigned int i = 0; i < N; i++)
550 r->coeffs[i] = this->coeffs[i].to_shwi ();
554 /* Return true if the coefficients of this generic_wide_int-based
555 polynomial can be represented as unsigned HOST_WIDE_INTs without
556 loss of precision. Store the unsigned HOST_WIDE_INT representation
559 template<unsigned int N, typename C>
561 poly_int_pod<N, C>::to_uhwi (poly_int_pod<N, unsigned HOST_WIDE_INT> *r) const
563 for (unsigned int i = 0; i < N; i++)
564 if (!wi::fits_uhwi_p (this->coeffs[i]))
566 for (unsigned int i = 0; i < N; i++)
567 r->coeffs[i] = this->coeffs[i].to_uhwi ();
571 /* Force a generic_wide_int-based constant to HOST_WIDE_INT precision,
572 truncating if necessary. */
574 template<unsigned int N, typename C>
575 inline poly_int<N, HOST_WIDE_INT>
576 poly_int_pod<N, C>::force_shwi () const
578 poly_int_pod<N, HOST_WIDE_INT> r;
579 for (unsigned int i = 0; i < N; i++)
580 r.coeffs[i] = this->coeffs[i].to_shwi ();
584 /* Force a generic_wide_int-based constant to unsigned HOST_WIDE_INT precision,
585 truncating if necessary. */
587 template<unsigned int N, typename C>
588 inline poly_int<N, unsigned HOST_WIDE_INT>
589 poly_int_pod<N, C>::force_uhwi () const
591 poly_int_pod<N, unsigned HOST_WIDE_INT> r;
592 for (unsigned int i = 0; i < N; i++)
593 r.coeffs[i] = this->coeffs[i].to_uhwi ();
597 #if POLY_INT_CONVERSION
598 /* Provide a conversion operator to constants. */
600 template<unsigned int N, typename C>
602 poly_int_pod<N, C>::operator C () const
604 gcc_checking_assert (this->is_constant ());
605 return this->coeffs[0];
609 /* The main class for polynomial integers. The class provides
610 constructors that are necessarily missing from the POD base. */
611 template<unsigned int N, typename C>
612 class poly_int : public poly_int_pod<N, C>
617 template<typename Ca>
618 poly_int (const poly_int<N, Ca> &);
619 template<typename Ca>
620 poly_int (const poly_int_pod<N, Ca> &);
621 template<typename C0>
622 poly_int (const C0 &);
623 template<typename C0, typename C1>
624 poly_int (const C0 &, const C1 &);
626 template<typename Ca>
627 poly_int &operator = (const poly_int_pod<N, Ca> &);
628 template<typename Ca>
629 typename if_nonpoly<Ca, poly_int>::type &operator = (const Ca &);
631 template<typename Ca>
632 poly_int &operator += (const poly_int_pod<N, Ca> &);
633 template<typename Ca>
634 typename if_nonpoly<Ca, poly_int>::type &operator += (const Ca &);
636 template<typename Ca>
637 poly_int &operator -= (const poly_int_pod<N, Ca> &);
638 template<typename Ca>
639 typename if_nonpoly<Ca, poly_int>::type &operator -= (const Ca &);
641 template<typename Ca>
642 typename if_nonpoly<Ca, poly_int>::type &operator *= (const Ca &);
644 poly_int &operator <<= (unsigned int);
647 template<unsigned int N, typename C>
648 template<typename Ca>
650 poly_int<N, C>::poly_int (const poly_int<N, Ca> &a)
652 for (unsigned int i = 0; i < N; i++)
653 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
656 template<unsigned int N, typename C>
657 template<typename Ca>
659 poly_int<N, C>::poly_int (const poly_int_pod<N, Ca> &a)
661 for (unsigned int i = 0; i < N; i++)
662 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
665 template<unsigned int N, typename C>
666 template<typename C0>
668 poly_int<N, C>::poly_int (const C0 &c0)
670 POLY_SET_COEFF (C, *this, 0, c0);
671 for (unsigned int i = 1; i < N; i++)
672 POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
675 template<unsigned int N, typename C>
676 template<typename C0, typename C1>
678 poly_int<N, C>::poly_int (const C0 &c0, const C1 &c1)
680 STATIC_ASSERT (N >= 2);
681 POLY_SET_COEFF (C, *this, 0, c0);
682 POLY_SET_COEFF (C, *this, 1, c1);
683 for (unsigned int i = 2; i < N; i++)
684 POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
687 template<unsigned int N, typename C>
688 template<typename Ca>
689 inline poly_int<N, C>&
690 poly_int<N, C>::operator = (const poly_int_pod<N, Ca> &a)
692 for (unsigned int i = 0; i < N; i++)
693 this->coeffs[i] = a.coeffs[i];
697 template<unsigned int N, typename C>
698 template<typename Ca>
699 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
700 poly_int<N, C>::operator = (const Ca &a)
704 for (unsigned int i = 1; i < N; i++)
705 this->coeffs[i] = wi::ints_for<C>::zero (this->coeffs[0]);
709 template<unsigned int N, typename C>
710 template<typename Ca>
711 inline poly_int<N, C>&
712 poly_int<N, C>::operator += (const poly_int_pod<N, Ca> &a)
714 for (unsigned int i = 0; i < N; i++)
715 this->coeffs[i] += a.coeffs[i];
719 template<unsigned int N, typename C>
720 template<typename Ca>
721 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
722 poly_int<N, C>::operator += (const Ca &a)
724 this->coeffs[0] += a;
728 template<unsigned int N, typename C>
729 template<typename Ca>
730 inline poly_int<N, C>&
731 poly_int<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
733 for (unsigned int i = 0; i < N; i++)
734 this->coeffs[i] -= a.coeffs[i];
738 template<unsigned int N, typename C>
739 template<typename Ca>
740 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
741 poly_int<N, C>::operator -= (const Ca &a)
743 this->coeffs[0] -= a;
747 template<unsigned int N, typename C>
748 template<typename Ca>
749 inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
750 poly_int<N, C>::operator *= (const Ca &a)
752 for (unsigned int i = 0; i < N; i++)
753 this->coeffs[i] *= a;
757 template<unsigned int N, typename C>
758 inline poly_int<N, C>&
759 poly_int<N, C>::operator <<= (unsigned int a)
761 for (unsigned int i = 0; i < N; i++)
762 this->coeffs[i] <<= a;
766 /* Return true if every coefficient of A is in the inclusive range [B, C]. */
768 template<typename Ca, typename Cb, typename Cc>
769 inline typename if_nonpoly<Ca, bool>::type
770 coeffs_in_range_p (const Ca &a, const Cb &b, const Cc &c)
772 return a >= b && a <= c;
775 template<unsigned int N, typename Ca, typename Cb, typename Cc>
776 inline typename if_nonpoly<Ca, bool>::type
777 coeffs_in_range_p (const poly_int_pod<N, Ca> &a, const Cb &b, const Cc &c)
779 for (unsigned int i = 0; i < N; i++)
780 if (a.coeffs[i] < b || a.coeffs[i] > c)
786 /* Poly version of wi::shwi, with the same interface. */
788 template<unsigned int N>
789 inline poly_int<N, hwi_with_prec>
790 shwi (const poly_int_pod<N, HOST_WIDE_INT> &a, unsigned int precision)
792 poly_int<N, hwi_with_prec> r;
793 for (unsigned int i = 0; i < N; i++)
794 POLY_SET_COEFF (hwi_with_prec, r, i, wi::shwi (a.coeffs[i], precision));
798 /* Poly version of wi::uhwi, with the same interface. */
800 template<unsigned int N>
801 inline poly_int<N, hwi_with_prec>
802 uhwi (const poly_int_pod<N, unsigned HOST_WIDE_INT> &a, unsigned int precision)
804 poly_int<N, hwi_with_prec> r;
805 for (unsigned int i = 0; i < N; i++)
806 POLY_SET_COEFF (hwi_with_prec, r, i, wi::uhwi (a.coeffs[i], precision));
810 /* Poly version of wi::sext, with the same interface. */
812 template<unsigned int N, typename Ca>
813 inline POLY_POLY_RESULT (N, Ca, Ca)
814 sext (const poly_int_pod<N, Ca> &a, unsigned int precision)
816 typedef POLY_POLY_COEFF (Ca, Ca) C;
818 for (unsigned int i = 0; i < N; i++)
819 POLY_SET_COEFF (C, r, i, wi::sext (a.coeffs[i], precision));
823 /* Poly version of wi::zext, with the same interface. */
825 template<unsigned int N, typename Ca>
826 inline POLY_POLY_RESULT (N, Ca, Ca)
827 zext (const poly_int_pod<N, Ca> &a, unsigned int precision)
829 typedef POLY_POLY_COEFF (Ca, Ca) C;
831 for (unsigned int i = 0; i < N; i++)
832 POLY_SET_COEFF (C, r, i, wi::zext (a.coeffs[i], precision));
837 template<unsigned int N, typename Ca, typename Cb>
838 inline POLY_POLY_RESULT (N, Ca, Cb)
839 operator + (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
841 typedef POLY_CAST (Ca, Cb) NCa;
842 typedef POLY_POLY_COEFF (Ca, Cb) C;
844 for (unsigned int i = 0; i < N; i++)
845 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) + b.coeffs[i]);
849 template<unsigned int N, typename Ca, typename Cb>
850 inline POLY_CONST_RESULT (N, Ca, Cb)
851 operator + (const poly_int_pod<N, Ca> &a, const Cb &b)
853 typedef POLY_CAST (Ca, Cb) NCa;
854 typedef POLY_CONST_COEFF (Ca, Cb) C;
856 POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) + b);
858 for (unsigned int i = 1; i < N; i++)
859 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
863 template<unsigned int N, typename Ca, typename Cb>
864 inline CONST_POLY_RESULT (N, Ca, Cb)
865 operator + (const Ca &a, const poly_int_pod<N, Cb> &b)
867 typedef POLY_CAST (Cb, Ca) NCb;
868 typedef CONST_POLY_COEFF (Ca, Cb) C;
870 POLY_SET_COEFF (C, r, 0, a + NCb (b.coeffs[0]));
872 for (unsigned int i = 1; i < N; i++)
873 POLY_SET_COEFF (C, r, i, NCb (b.coeffs[i]));
878 /* Poly versions of wi::add, with the same interface. */
880 template<unsigned int N, typename Ca, typename Cb>
881 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
882 add (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
884 typedef WI_BINARY_RESULT (Ca, Cb) C;
886 for (unsigned int i = 0; i < N; i++)
887 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i]));
891 template<unsigned int N, typename Ca, typename Cb>
892 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
893 add (const poly_int_pod<N, Ca> &a, const Cb &b)
895 typedef WI_BINARY_RESULT (Ca, Cb) C;
897 POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b));
898 for (unsigned int i = 1; i < N; i++)
899 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i],
900 wi::ints_for<Cb>::zero (b)));
904 template<unsigned int N, typename Ca, typename Cb>
905 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
906 add (const Ca &a, const poly_int_pod<N, Cb> &b)
908 typedef WI_BINARY_RESULT (Ca, Cb) C;
910 POLY_SET_COEFF (C, r, 0, wi::add (a, b.coeffs[0]));
911 for (unsigned int i = 1; i < N; i++)
912 POLY_SET_COEFF (C, r, i, wi::add (wi::ints_for<Ca>::zero (a),
917 template<unsigned int N, typename Ca, typename Cb>
918 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
919 add (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
920 signop sgn, wi::overflow_type *overflow)
922 typedef WI_BINARY_RESULT (Ca, Cb) C;
924 POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b.coeffs[0], sgn, overflow));
925 for (unsigned int i = 1; i < N; i++)
927 wi::overflow_type suboverflow;
928 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i], sgn,
930 wi::accumulate_overflow (*overflow, suboverflow);
936 template<unsigned int N, typename Ca, typename Cb>
937 inline POLY_POLY_RESULT (N, Ca, Cb)
938 operator - (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
940 typedef POLY_CAST (Ca, Cb) NCa;
941 typedef POLY_POLY_COEFF (Ca, Cb) C;
943 for (unsigned int i = 0; i < N; i++)
944 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) - b.coeffs[i]);
948 template<unsigned int N, typename Ca, typename Cb>
949 inline POLY_CONST_RESULT (N, Ca, Cb)
950 operator - (const poly_int_pod<N, Ca> &a, const Cb &b)
952 typedef POLY_CAST (Ca, Cb) NCa;
953 typedef POLY_CONST_COEFF (Ca, Cb) C;
955 POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) - b);
957 for (unsigned int i = 1; i < N; i++)
958 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
962 template<unsigned int N, typename Ca, typename Cb>
963 inline CONST_POLY_RESULT (N, Ca, Cb)
964 operator - (const Ca &a, const poly_int_pod<N, Cb> &b)
966 typedef POLY_CAST (Cb, Ca) NCb;
967 typedef CONST_POLY_COEFF (Ca, Cb) C;
969 POLY_SET_COEFF (C, r, 0, a - NCb (b.coeffs[0]));
971 for (unsigned int i = 1; i < N; i++)
972 POLY_SET_COEFF (C, r, i, -NCb (b.coeffs[i]));
977 /* Poly versions of wi::sub, with the same interface. */
979 template<unsigned int N, typename Ca, typename Cb>
980 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
981 sub (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
983 typedef WI_BINARY_RESULT (Ca, Cb) C;
985 for (unsigned int i = 0; i < N; i++)
986 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i]));
990 template<unsigned int N, typename Ca, typename Cb>
991 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
992 sub (const poly_int_pod<N, Ca> &a, const Cb &b)
994 typedef WI_BINARY_RESULT (Ca, Cb) C;
996 POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b));
997 for (unsigned int i = 1; i < N; i++)
998 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i],
999 wi::ints_for<Cb>::zero (b)));
1003 template<unsigned int N, typename Ca, typename Cb>
1004 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1005 sub (const Ca &a, const poly_int_pod<N, Cb> &b)
1007 typedef WI_BINARY_RESULT (Ca, Cb) C;
1009 POLY_SET_COEFF (C, r, 0, wi::sub (a, b.coeffs[0]));
1010 for (unsigned int i = 1; i < N; i++)
1011 POLY_SET_COEFF (C, r, i, wi::sub (wi::ints_for<Ca>::zero (a),
1016 template<unsigned int N, typename Ca, typename Cb>
1017 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1018 sub (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
1019 signop sgn, wi::overflow_type *overflow)
1021 typedef WI_BINARY_RESULT (Ca, Cb) C;
1023 POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b.coeffs[0], sgn, overflow));
1024 for (unsigned int i = 1; i < N; i++)
1026 wi::overflow_type suboverflow;
1027 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i], sgn,
1029 wi::accumulate_overflow (*overflow, suboverflow);
1035 template<unsigned int N, typename Ca>
1036 inline POLY_POLY_RESULT (N, Ca, Ca)
1037 operator - (const poly_int_pod<N, Ca> &a)
1039 typedef POLY_CAST (Ca, Ca) NCa;
1040 typedef POLY_POLY_COEFF (Ca, Ca) C;
1042 for (unsigned int i = 0; i < N; i++)
1043 POLY_SET_COEFF (C, r, i, -NCa (a.coeffs[i]));
1048 /* Poly version of wi::neg, with the same interface. */
1050 template<unsigned int N, typename Ca>
1051 inline poly_int<N, WI_UNARY_RESULT (Ca)>
1052 neg (const poly_int_pod<N, Ca> &a)
1054 typedef WI_UNARY_RESULT (Ca) C;
1056 for (unsigned int i = 0; i < N; i++)
1057 POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i]));
1061 template<unsigned int N, typename Ca>
1062 inline poly_int<N, WI_UNARY_RESULT (Ca)>
1063 neg (const poly_int_pod<N, Ca> &a, wi::overflow_type *overflow)
1065 typedef WI_UNARY_RESULT (Ca) C;
1067 POLY_SET_COEFF (C, r, 0, wi::neg (a.coeffs[0], overflow));
1068 for (unsigned int i = 1; i < N; i++)
1070 wi::overflow_type suboverflow;
1071 POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i], &suboverflow));
1072 wi::accumulate_overflow (*overflow, suboverflow);
1078 template<unsigned int N, typename Ca>
1079 inline POLY_POLY_RESULT (N, Ca, Ca)
1080 operator ~ (const poly_int_pod<N, Ca> &a)
1084 return ~a.coeffs[0];
1087 template<unsigned int N, typename Ca, typename Cb>
1088 inline POLY_CONST_RESULT (N, Ca, Cb)
1089 operator * (const poly_int_pod<N, Ca> &a, const Cb &b)
1091 typedef POLY_CAST (Ca, Cb) NCa;
1092 typedef POLY_CONST_COEFF (Ca, Cb) C;
1094 for (unsigned int i = 0; i < N; i++)
1095 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) * b);
1099 template<unsigned int N, typename Ca, typename Cb>
1100 inline CONST_POLY_RESULT (N, Ca, Cb)
1101 operator * (const Ca &a, const poly_int_pod<N, Cb> &b)
1103 typedef POLY_CAST (Ca, Cb) NCa;
1104 typedef CONST_POLY_COEFF (Ca, Cb) C;
1106 for (unsigned int i = 0; i < N; i++)
1107 POLY_SET_COEFF (C, r, i, NCa (a) * b.coeffs[i]);
1112 /* Poly versions of wi::mul, with the same interface. */
1114 template<unsigned int N, typename Ca, typename Cb>
1115 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1116 mul (const poly_int_pod<N, Ca> &a, const Cb &b)
1118 typedef WI_BINARY_RESULT (Ca, Cb) C;
1120 for (unsigned int i = 0; i < N; i++)
1121 POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b));
1125 template<unsigned int N, typename Ca, typename Cb>
1126 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1127 mul (const Ca &a, const poly_int_pod<N, Cb> &b)
1129 typedef WI_BINARY_RESULT (Ca, Cb) C;
1131 for (unsigned int i = 0; i < N; i++)
1132 POLY_SET_COEFF (C, r, i, wi::mul (a, b.coeffs[i]));
1136 template<unsigned int N, typename Ca, typename Cb>
1137 inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1138 mul (const poly_int_pod<N, Ca> &a, const Cb &b,
1139 signop sgn, wi::overflow_type *overflow)
1141 typedef WI_BINARY_RESULT (Ca, Cb) C;
1143 POLY_SET_COEFF (C, r, 0, wi::mul (a.coeffs[0], b, sgn, overflow));
1144 for (unsigned int i = 1; i < N; i++)
1146 wi::overflow_type suboverflow;
1147 POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b, sgn, &suboverflow));
1148 wi::accumulate_overflow (*overflow, suboverflow);
1154 template<unsigned int N, typename Ca, typename Cb>
1155 inline POLY_POLY_RESULT (N, Ca, Ca)
1156 operator << (const poly_int_pod<N, Ca> &a, const Cb &b)
1158 typedef POLY_CAST (Ca, Ca) NCa;
1159 typedef POLY_POLY_COEFF (Ca, Ca) C;
1161 for (unsigned int i = 0; i < N; i++)
1162 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) << b);
1167 /* Poly version of wi::lshift, with the same interface. */
1169 template<unsigned int N, typename Ca, typename Cb>
1170 inline poly_int<N, WI_BINARY_RESULT (Ca, Ca)>
1171 lshift (const poly_int_pod<N, Ca> &a, const Cb &b)
1173 typedef WI_BINARY_RESULT (Ca, Ca) C;
1175 for (unsigned int i = 0; i < N; i++)
1176 POLY_SET_COEFF (C, r, i, wi::lshift (a.coeffs[i], b));
1181 /* Poly version of sext_hwi, with the same interface. */
1183 template<unsigned int N, typename C>
1184 inline poly_int<N, HOST_WIDE_INT>
1185 sext_hwi (const poly_int<N, C> &a, unsigned int precision)
1187 poly_int_pod<N, HOST_WIDE_INT> r;
1188 for (unsigned int i = 0; i < N; i++)
1189 r.coeffs[i] = sext_hwi (a.coeffs[i], precision);
1194 /* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative
1197 template<typename Ca, typename Cb>
1199 maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1)
1202 /* a0 + a1 * x == b0 + b1 * x
1203 ==> (a1 - b1) * x == b0 - a0
1204 ==> x == (b0 - a0) / (a1 - b1)
1206 We need to test whether that's a valid value of x.
1207 (b0 - a0) and (a1 - b1) must not have opposite signs
1208 and the result must be integral. */
1210 ? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0
1211 : b0 >= a0 && (b0 - a0) % (a1 - b1) == 0);
1215 /* Return true if a0 + a1 * x might equal b for some nonnegative
1218 template<typename Ca, typename Cb>
1220 maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b)
1224 ==> x == (b - a0) / a1
1226 We need to test whether that's a valid value of x.
1227 (b - a0) and a1 must not have opposite signs and the
1228 result must be integral. */
1230 ? b <= a0 && (a0 - b) % a1 == 0
1231 : b >= a0 && (b - a0) % a1 == 0);
1235 /* Return true if A might equal B for some indeterminate values. */
1237 template<unsigned int N, typename Ca, typename Cb>
1239 maybe_eq (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1241 STATIC_ASSERT (N <= 2);
1243 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]);
1244 return a.coeffs[0] == b.coeffs[0];
1247 template<unsigned int N, typename Ca, typename Cb>
1248 inline typename if_nonpoly<Cb, bool>::type
1249 maybe_eq (const poly_int_pod<N, Ca> &a, const Cb &b)
1251 STATIC_ASSERT (N <= 2);
1253 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b);
1254 return a.coeffs[0] == b;
1257 template<unsigned int N, typename Ca, typename Cb>
1258 inline typename if_nonpoly<Ca, bool>::type
1259 maybe_eq (const Ca &a, const poly_int_pod<N, Cb> &b)
1261 STATIC_ASSERT (N <= 2);
1263 return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a);
1264 return a == b.coeffs[0];
1267 template<typename Ca, typename Cb>
1268 inline typename if_nonpoly2<Ca, Cb, bool>::type
1269 maybe_eq (const Ca &a, const Cb &b)
1274 /* Return true if A might not equal B for some indeterminate values. */
1276 template<unsigned int N, typename Ca, typename Cb>
1278 maybe_ne (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1281 for (unsigned int i = 1; i < N; i++)
1282 if (a.coeffs[i] != b.coeffs[i])
1284 return a.coeffs[0] != b.coeffs[0];
1287 template<unsigned int N, typename Ca, typename Cb>
1288 inline typename if_nonpoly<Cb, bool>::type
1289 maybe_ne (const poly_int_pod<N, Ca> &a, const Cb &b)
1292 for (unsigned int i = 1; i < N; i++)
1293 if (a.coeffs[i] != 0)
1295 return a.coeffs[0] != b;
1298 template<unsigned int N, typename Ca, typename Cb>
1299 inline typename if_nonpoly<Ca, bool>::type
1300 maybe_ne (const Ca &a, const poly_int_pod<N, Cb> &b)
1303 for (unsigned int i = 1; i < N; i++)
1304 if (b.coeffs[i] != 0)
1306 return a != b.coeffs[0];
1309 template<typename Ca, typename Cb>
1310 inline typename if_nonpoly2<Ca, Cb, bool>::type
1311 maybe_ne (const Ca &a, const Cb &b)
1316 /* Return true if A is known to be equal to B. */
1317 #define known_eq(A, B) (!maybe_ne (A, B))
1319 /* Return true if A is known to be unequal to B. */
1320 #define known_ne(A, B) (!maybe_eq (A, B))
1322 /* Return true if A might be less than or equal to B for some
1323 indeterminate values. */
1325 template<unsigned int N, typename Ca, typename Cb>
1327 maybe_le (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1330 for (unsigned int i = 1; i < N; i++)
1331 if (a.coeffs[i] < b.coeffs[i])
1333 return a.coeffs[0] <= b.coeffs[0];
1336 template<unsigned int N, typename Ca, typename Cb>
1337 inline typename if_nonpoly<Cb, bool>::type
1338 maybe_le (const poly_int_pod<N, Ca> &a, const Cb &b)
1341 for (unsigned int i = 1; i < N; i++)
1342 if (a.coeffs[i] < 0)
1344 return a.coeffs[0] <= b;
1347 template<unsigned int N, typename Ca, typename Cb>
1348 inline typename if_nonpoly<Ca, bool>::type
1349 maybe_le (const Ca &a, const poly_int_pod<N, Cb> &b)
1352 for (unsigned int i = 1; i < N; i++)
1353 if (b.coeffs[i] > 0)
1355 return a <= b.coeffs[0];
1358 template<typename Ca, typename Cb>
1359 inline typename if_nonpoly2<Ca, Cb, bool>::type
1360 maybe_le (const Ca &a, const Cb &b)
1365 /* Return true if A might be less than B for some indeterminate values. */
1367 template<unsigned int N, typename Ca, typename Cb>
1369 maybe_lt (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1372 for (unsigned int i = 1; i < N; i++)
1373 if (a.coeffs[i] < b.coeffs[i])
1375 return a.coeffs[0] < b.coeffs[0];
1378 template<unsigned int N, typename Ca, typename Cb>
1379 inline typename if_nonpoly<Cb, bool>::type
1380 maybe_lt (const poly_int_pod<N, Ca> &a, const Cb &b)
1383 for (unsigned int i = 1; i < N; i++)
1384 if (a.coeffs[i] < 0)
1386 return a.coeffs[0] < b;
1389 template<unsigned int N, typename Ca, typename Cb>
1390 inline typename if_nonpoly<Ca, bool>::type
1391 maybe_lt (const Ca &a, const poly_int_pod<N, Cb> &b)
1394 for (unsigned int i = 1; i < N; i++)
1395 if (b.coeffs[i] > 0)
1397 return a < b.coeffs[0];
1400 template<typename Ca, typename Cb>
1401 inline typename if_nonpoly2<Ca, Cb, bool>::type
1402 maybe_lt (const Ca &a, const Cb &b)
1407 /* Return true if A may be greater than or equal to B. */
1408 #define maybe_ge(A, B) maybe_le (B, A)
1410 /* Return true if A may be greater than B. */
1411 #define maybe_gt(A, B) maybe_lt (B, A)
1413 /* Return true if A is known to be less than or equal to B. */
1414 #define known_le(A, B) (!maybe_gt (A, B))
1416 /* Return true if A is known to be less than B. */
1417 #define known_lt(A, B) (!maybe_ge (A, B))
1419 /* Return true if A is known to be greater than B. */
1420 #define known_gt(A, B) (!maybe_le (A, B))
1422 /* Return true if A is known to be greater than or equal to B. */
1423 #define known_ge(A, B) (!maybe_lt (A, B))
1425 /* Return true if A and B are ordered by the partial ordering known_le. */
1427 template<typename T1, typename T2>
1429 ordered_p (const T1 &a, const T2 &b)
1431 return ((poly_int_traits<T1>::num_coeffs == 1
1432 && poly_int_traits<T2>::num_coeffs == 1)
1434 || known_le (b, a));
1437 /* Assert that A and B are known to be ordered and return the minimum
1440 NOTE: When using this function, please add a comment above the call
1441 explaining why we know the values are ordered in that context. */
1443 template<unsigned int N, typename Ca, typename Cb>
1444 inline POLY_POLY_RESULT (N, Ca, Cb)
1445 ordered_min (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1447 if (known_le (a, b))
1452 gcc_checking_assert (known_le (b, a));
1457 template<unsigned int N, typename Ca, typename Cb>
1458 inline CONST_POLY_RESULT (N, Ca, Cb)
1459 ordered_min (const Ca &a, const poly_int_pod<N, Cb> &b)
1461 if (known_le (a, b))
1466 gcc_checking_assert (known_le (b, a));
1471 template<unsigned int N, typename Ca, typename Cb>
1472 inline POLY_CONST_RESULT (N, Ca, Cb)
1473 ordered_min (const poly_int_pod<N, Ca> &a, const Cb &b)
1475 if (known_le (a, b))
1480 gcc_checking_assert (known_le (b, a));
1485 /* Assert that A and B are known to be ordered and return the maximum
1488 NOTE: When using this function, please add a comment above the call
1489 explaining why we know the values are ordered in that context. */
1491 template<unsigned int N, typename Ca, typename Cb>
1492 inline POLY_POLY_RESULT (N, Ca, Cb)
1493 ordered_max (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1495 if (known_le (a, b))
1500 gcc_checking_assert (known_le (b, a));
1505 template<unsigned int N, typename Ca, typename Cb>
1506 inline CONST_POLY_RESULT (N, Ca, Cb)
1507 ordered_max (const Ca &a, const poly_int_pod<N, Cb> &b)
1509 if (known_le (a, b))
1514 gcc_checking_assert (known_le (b, a));
1519 template<unsigned int N, typename Ca, typename Cb>
1520 inline POLY_CONST_RESULT (N, Ca, Cb)
1521 ordered_max (const poly_int_pod<N, Ca> &a, const Cb &b)
1523 if (known_le (a, b))
1528 gcc_checking_assert (known_le (b, a));
1533 /* Return a constant lower bound on the value of A, which is known
1534 to be nonnegative. */
1536 template<unsigned int N, typename Ca>
1538 constant_lower_bound (const poly_int_pod<N, Ca> &a)
1540 gcc_checking_assert (known_ge (a, POLY_INT_TYPE (Ca) (0)));
1544 /* Return the constant lower bound of A, given that it is no less than B. */
1546 template<unsigned int N, typename Ca, typename Cb>
1547 inline POLY_CONST_COEFF (Ca, Cb)
1548 constant_lower_bound_with_limit (const poly_int_pod<N, Ca> &a, const Cb &b)
1550 if (known_ge (a, b))
1555 /* Return the constant upper bound of A, given that it is no greater
1558 template<unsigned int N, typename Ca, typename Cb>
1559 inline POLY_CONST_COEFF (Ca, Cb)
1560 constant_upper_bound_with_limit (const poly_int_pod<N, Ca> &a, const Cb &b)
1562 if (known_le (a, b))
1567 /* Return a value that is known to be no greater than A and B. This
1568 will be the greatest lower bound for some indeterminate values but
1569 not necessarily for all. */
1571 template<unsigned int N, typename Ca, typename Cb>
1572 inline POLY_CONST_RESULT (N, Ca, Cb)
1573 lower_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
1575 typedef POLY_CAST (Ca, Cb) NCa;
1576 typedef POLY_CAST (Cb, Ca) NCb;
1577 typedef POLY_INT_TYPE (Cb) ICb;
1578 typedef POLY_CONST_COEFF (Ca, Cb) C;
1581 POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b)));
1583 for (unsigned int i = 1; i < N; i++)
1584 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0)));
1588 template<unsigned int N, typename Ca, typename Cb>
1589 inline CONST_POLY_RESULT (N, Ca, Cb)
1590 lower_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
1592 return lower_bound (b, a);
1595 template<unsigned int N, typename Ca, typename Cb>
1596 inline POLY_POLY_RESULT (N, Ca, Cb)
1597 lower_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1599 typedef POLY_CAST (Ca, Cb) NCa;
1600 typedef POLY_CAST (Cb, Ca) NCb;
1601 typedef POLY_POLY_COEFF (Ca, Cb) C;
1604 for (unsigned int i = 0; i < N; i++)
1605 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1609 template<typename Ca, typename Cb>
1610 inline CONST_CONST_RESULT (N, Ca, Cb)
1611 lower_bound (const Ca &a, const Cb &b)
1613 return a < b ? a : b;
1616 /* Return a value that is known to be no less than A and B. This will
1617 be the least upper bound for some indeterminate values but not
1618 necessarily for all. */
1620 template<unsigned int N, typename Ca, typename Cb>
1621 inline POLY_CONST_RESULT (N, Ca, Cb)
1622 upper_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
1624 typedef POLY_CAST (Ca, Cb) NCa;
1625 typedef POLY_CAST (Cb, Ca) NCb;
1626 typedef POLY_INT_TYPE (Cb) ICb;
1627 typedef POLY_CONST_COEFF (Ca, Cb) C;
1630 POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b)));
1632 for (unsigned int i = 1; i < N; i++)
1633 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0)));
1637 template<unsigned int N, typename Ca, typename Cb>
1638 inline CONST_POLY_RESULT (N, Ca, Cb)
1639 upper_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
1641 return upper_bound (b, a);
1644 template<unsigned int N, typename Ca, typename Cb>
1645 inline POLY_POLY_RESULT (N, Ca, Cb)
1646 upper_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1648 typedef POLY_CAST (Ca, Cb) NCa;
1649 typedef POLY_CAST (Cb, Ca) NCb;
1650 typedef POLY_POLY_COEFF (Ca, Cb) C;
1653 for (unsigned int i = 0; i < N; i++)
1654 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1658 /* Return the greatest common divisor of all nonzero coefficients, or zero
1659 if all coefficients are zero. */
1661 template<unsigned int N, typename Ca>
1662 inline POLY_BINARY_COEFF (Ca, Ca)
1663 coeff_gcd (const poly_int_pod<N, Ca> &a)
1665 /* Find the first nonzero coefficient, stopping at 0 whatever happens. */
1667 for (i = N - 1; i > 0; --i)
1668 if (a.coeffs[i] != 0)
1670 typedef POLY_BINARY_COEFF (Ca, Ca) C;
1672 for (unsigned int j = 0; j < i; ++j)
1673 if (a.coeffs[j] != 0)
1674 r = gcd (r, C (a.coeffs[j]));
1678 /* Return a value that is a multiple of both A and B. This will be the
1679 least common multiple for some indeterminate values but necessarily
1682 template<unsigned int N, typename Ca, typename Cb>
1683 POLY_CONST_RESULT (N, Ca, Cb)
1684 common_multiple (const poly_int_pod<N, Ca> &a, Cb b)
1686 POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a);
1687 return a * (least_common_multiple (xgcd, b) / xgcd);
1690 template<unsigned int N, typename Ca, typename Cb>
1691 inline CONST_POLY_RESULT (N, Ca, Cb)
1692 common_multiple (const Ca &a, const poly_int_pod<N, Cb> &b)
1694 return common_multiple (b, a);
1697 /* Return a value that is a multiple of both A and B, asserting that
1698 such a value exists. The result will be the least common multiple
1699 for some indeterminate values but necessarily for all.
1701 NOTE: When using this function, please add a comment above the call
1702 explaining why we know the values have a common multiple (which might
1703 for example be because we know A / B is rational). */
1705 template<unsigned int N, typename Ca, typename Cb>
1706 POLY_POLY_RESULT (N, Ca, Cb)
1707 force_common_multiple (const poly_int_pod<N, Ca> &a,
1708 const poly_int_pod<N, Cb> &b)
1710 if (b.is_constant ())
1711 return common_multiple (a, b.coeffs[0]);
1712 if (a.is_constant ())
1713 return common_multiple (a.coeffs[0], b);
1715 typedef POLY_CAST (Ca, Cb) NCa;
1716 typedef POLY_CAST (Cb, Ca) NCb;
1717 typedef POLY_BINARY_COEFF (Ca, Cb) C;
1718 typedef POLY_INT_TYPE (Ca) ICa;
1720 for (unsigned int i = 1; i < N; ++i)
1721 if (a.coeffs[i] != ICa (0))
1723 C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i]));
1724 C amul = lcm / a.coeffs[i];
1725 C bmul = lcm / b.coeffs[i];
1726 for (unsigned int j = 0; j < N; ++j)
1727 gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul);
1733 /* Compare A and B for sorting purposes, returning -1 if A should come
1734 before B, 0 if A and B are identical, and 1 if A should come after B.
1735 This is a lexicographical compare of the coefficients in reverse order.
1737 A consequence of this is that all constant sizes come before all
1738 non-constant ones, regardless of magnitude (since a size is never
1739 negative). This is what most callers want. For example, when laying
1740 data out on the stack, it's better to keep all the constant-sized
1741 data together so that it can be accessed as a constant offset from a
1744 template<unsigned int N, typename Ca, typename Cb>
1746 compare_sizes_for_sort (const poly_int_pod<N, Ca> &a,
1747 const poly_int_pod<N, Cb> &b)
1749 for (unsigned int i = N; i-- > 0; )
1750 if (a.coeffs[i] != b.coeffs[i])
1751 return a.coeffs[i] < b.coeffs[i] ? -1 : 1;
1755 /* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */
1757 template<unsigned int N, typename Ca, typename Cb>
1759 can_align_p (const poly_int_pod<N, Ca> &value, Cb align)
1761 for (unsigned int i = 1; i < N; i++)
1762 if ((value.coeffs[i] & (align - 1)) != 0)
1767 /* Return true if we can align VALUE up to the smallest multiple of
1768 ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */
1770 template<unsigned int N, typename Ca, typename Cb>
1772 can_align_up (const poly_int_pod<N, Ca> &value, Cb align,
1773 poly_int_pod<N, Ca> *aligned)
1775 if (!can_align_p (value, align))
1777 *aligned = value + (-value.coeffs[0] & (align - 1));
1781 /* Return true if we can align VALUE down to the largest multiple of
1782 ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */
1784 template<unsigned int N, typename Ca, typename Cb>
1786 can_align_down (const poly_int_pod<N, Ca> &value, Cb align,
1787 poly_int_pod<N, Ca> *aligned)
1789 if (!can_align_p (value, align))
1791 *aligned = value - (value.coeffs[0] & (align - 1));
1795 /* Return true if we can align A and B up to the smallest multiples of
1796 ALIGN that are >= A and B respectively, and if doing so gives the
1799 template<unsigned int N, typename Ca, typename Cb, typename Cc>
1801 known_equal_after_align_up (const poly_int_pod<N, Ca> &a,
1802 const poly_int_pod<N, Cb> &b,
1805 poly_int<N, Ca> aligned_a;
1806 poly_int<N, Cb> aligned_b;
1807 return (can_align_up (a, align, &aligned_a)
1808 && can_align_up (b, align, &aligned_b)
1809 && known_eq (aligned_a, aligned_b));
1812 /* Return true if we can align A and B down to the largest multiples of
1813 ALIGN that are <= A and B respectively, and if doing so gives the
1816 template<unsigned int N, typename Ca, typename Cb, typename Cc>
1818 known_equal_after_align_down (const poly_int_pod<N, Ca> &a,
1819 const poly_int_pod<N, Cb> &b,
1822 poly_int<N, Ca> aligned_a;
1823 poly_int<N, Cb> aligned_b;
1824 return (can_align_down (a, align, &aligned_a)
1825 && can_align_down (b, align, &aligned_b)
1826 && known_eq (aligned_a, aligned_b));
1829 /* Assert that we can align VALUE to ALIGN at compile time and return
1830 the smallest multiple of ALIGN that is >= VALUE.
1832 NOTE: When using this function, please add a comment above the call
1833 explaining why we know the non-constant coefficients must already
1834 be a multiple of ALIGN. */
1836 template<unsigned int N, typename Ca, typename Cb>
1837 inline poly_int<N, Ca>
1838 force_align_up (const poly_int_pod<N, Ca> &value, Cb align)
1840 gcc_checking_assert (can_align_p (value, align));
1841 return value + (-value.coeffs[0] & (align - 1));
1844 /* Assert that we can align VALUE to ALIGN at compile time and return
1845 the largest multiple of ALIGN that is <= VALUE.
1847 NOTE: When using this function, please add a comment above the call
1848 explaining why we know the non-constant coefficients must already
1849 be a multiple of ALIGN. */
1851 template<unsigned int N, typename Ca, typename Cb>
1852 inline poly_int<N, Ca>
1853 force_align_down (const poly_int_pod<N, Ca> &value, Cb align)
1855 gcc_checking_assert (can_align_p (value, align));
1856 return value - (value.coeffs[0] & (align - 1));
1859 /* Return a value <= VALUE that is a multiple of ALIGN. It will be the
1860 greatest such value for some indeterminate values but not necessarily
1863 template<unsigned int N, typename Ca, typename Cb>
1864 inline poly_int<N, Ca>
1865 aligned_lower_bound (const poly_int_pod<N, Ca> &value, Cb align)
1868 for (unsigned int i = 0; i < N; i++)
1869 /* This form copes correctly with more type combinations than
1870 value.coeffs[i] & -align would. */
1871 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1872 - (value.coeffs[i] & (align - 1))));
1876 /* Return a value >= VALUE that is a multiple of ALIGN. It will be the
1877 least such value for some indeterminate values but not necessarily
1880 template<unsigned int N, typename Ca, typename Cb>
1881 inline poly_int<N, Ca>
1882 aligned_upper_bound (const poly_int_pod<N, Ca> &value, Cb align)
1885 for (unsigned int i = 0; i < N; i++)
1886 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1887 + (-value.coeffs[i] & (align - 1))));
1891 /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1892 down to the largest multiple of ALIGN that is <= VALUE, then divide by
1895 NOTE: When using this function, please add a comment above the call
1896 explaining why we know the non-constant coefficients must already
1897 be a multiple of ALIGN. */
1899 template<unsigned int N, typename Ca, typename Cb>
1900 inline poly_int<N, Ca>
1901 force_align_down_and_div (const poly_int_pod<N, Ca> &value, Cb align)
1903 gcc_checking_assert (can_align_p (value, align));
1906 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1907 - (value.coeffs[0] & (align - 1)))
1910 for (unsigned int i = 1; i < N; i++)
1911 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1915 /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1916 up to the smallest multiple of ALIGN that is >= VALUE, then divide by
1919 NOTE: When using this function, please add a comment above the call
1920 explaining why we know the non-constant coefficients must already
1921 be a multiple of ALIGN. */
1923 template<unsigned int N, typename Ca, typename Cb>
1924 inline poly_int<N, Ca>
1925 force_align_up_and_div (const poly_int_pod<N, Ca> &value, Cb align)
1927 gcc_checking_assert (can_align_p (value, align));
1930 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1931 + (-value.coeffs[0] & (align - 1)))
1934 for (unsigned int i = 1; i < N; i++)
1935 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1939 /* Return true if we know at compile time the difference between VALUE
1940 and the equal or preceding multiple of ALIGN. Store the value in
1943 template<unsigned int N, typename Ca, typename Cb, typename Cm>
1945 known_misalignment (const poly_int_pod<N, Ca> &value, Cb align, Cm *misalign)
1947 gcc_checking_assert (align != 0);
1948 if (!can_align_p (value, align))
1950 *misalign = value.coeffs[0] & (align - 1);
1954 /* Return X & (Y - 1), asserting that this value is known. Please add
1955 an a comment above callers to this function to explain why the condition
1956 is known to hold. */
1958 template<unsigned int N, typename Ca, typename Cb>
1959 inline POLY_BINARY_COEFF (Ca, Ca)
1960 force_get_misalignment (const poly_int_pod<N, Ca> &a, Cb align)
1962 gcc_checking_assert (can_align_p (a, align));
1963 return a.coeffs[0] & (align - 1);
1966 /* Return the maximum alignment that A is known to have. Return 0
1967 if A is known to be zero. */
1969 template<unsigned int N, typename Ca>
1970 inline POLY_BINARY_COEFF (Ca, Ca)
1971 known_alignment (const poly_int_pod<N, Ca> &a)
1973 typedef POLY_BINARY_COEFF (Ca, Ca) C;
1975 for (unsigned int i = 1; i < N; ++i)
1980 /* Return true if we can compute A | B at compile time, storing the
1981 result in RES if so. */
1983 template<unsigned int N, typename Ca, typename Cb, typename Cr>
1984 inline typename if_nonpoly<Cb, bool>::type
1985 can_ior_p (const poly_int_pod<N, Ca> &a, Cb b, Cr *result)
1987 /* Coefficients 1 and above must be a multiple of something greater
1989 typedef POLY_INT_TYPE (Ca) int_type;
1991 for (unsigned int i = 1; i < N; i++)
1992 if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0))
1995 result->coeffs[0] |= b;
1999 /* Return true if A is a constant multiple of B, storing the
2000 multiple in *MULTIPLE if so. */
2002 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2003 inline typename if_nonpoly<Cb, bool>::type
2004 constant_multiple_p (const poly_int_pod<N, Ca> &a, Cb b, Cm *multiple)
2006 typedef POLY_CAST (Ca, Cb) NCa;
2007 typedef POLY_CAST (Cb, Ca) NCb;
2009 /* Do the modulus before the constant check, to catch divide by
2011 if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
2013 *multiple = NCa (a.coeffs[0]) / NCb (b);
2017 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2018 inline typename if_nonpoly<Ca, bool>::type
2019 constant_multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
2021 typedef POLY_CAST (Ca, Cb) NCa;
2022 typedef POLY_CAST (Cb, Ca) NCb;
2023 typedef POLY_INT_TYPE (Ca) int_type;
2025 /* Do the modulus before the constant check, to catch divide by
2027 if (NCa (a) % NCb (b.coeffs[0]) != 0
2028 || (a != int_type (0) && !b.is_constant ()))
2030 *multiple = NCa (a) / NCb (b.coeffs[0]);
2034 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2036 constant_multiple_p (const poly_int_pod<N, Ca> &a,
2037 const poly_int_pod<N, Cb> &b, Cm *multiple)
2039 typedef POLY_CAST (Ca, Cb) NCa;
2040 typedef POLY_CAST (Cb, Ca) NCb;
2041 typedef POLY_INT_TYPE (Ca) ICa;
2042 typedef POLY_INT_TYPE (Cb) ICb;
2043 typedef POLY_BINARY_COEFF (Ca, Cb) C;
2045 if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
2048 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2049 for (unsigned int i = 1; i < N; ++i)
2050 if (b.coeffs[i] == ICb (0)
2051 ? a.coeffs[i] != ICa (0)
2052 : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2053 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2060 /* Return true if A is a constant multiple of B. */
2062 template<unsigned int N, typename Ca, typename Cb>
2063 inline typename if_nonpoly<Cb, bool>::type
2064 constant_multiple_p (const poly_int_pod<N, Ca> &a, Cb b)
2066 typedef POLY_CAST (Ca, Cb) NCa;
2067 typedef POLY_CAST (Cb, Ca) NCb;
2069 /* Do the modulus before the constant check, to catch divide by
2071 if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
2076 template<unsigned int N, typename Ca, typename Cb>
2077 inline typename if_nonpoly<Ca, bool>::type
2078 constant_multiple_p (Ca a, const poly_int_pod<N, Cb> &b)
2080 typedef POLY_CAST (Ca, Cb) NCa;
2081 typedef POLY_CAST (Cb, Ca) NCb;
2082 typedef POLY_INT_TYPE (Ca) int_type;
2084 /* Do the modulus before the constant check, to catch divide by
2086 if (NCa (a) % NCb (b.coeffs[0]) != 0
2087 || (a != int_type (0) && !b.is_constant ()))
2092 template<unsigned int N, typename Ca, typename Cb>
2094 constant_multiple_p (const poly_int_pod<N, Ca> &a,
2095 const poly_int_pod<N, Cb> &b)
2097 typedef POLY_CAST (Ca, Cb) NCa;
2098 typedef POLY_CAST (Cb, Ca) NCb;
2099 typedef POLY_INT_TYPE (Ca) ICa;
2100 typedef POLY_INT_TYPE (Cb) ICb;
2101 typedef POLY_BINARY_COEFF (Ca, Cb) C;
2103 if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
2106 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2107 for (unsigned int i = 1; i < N; ++i)
2108 if (b.coeffs[i] == ICb (0)
2109 ? a.coeffs[i] != ICa (0)
2110 : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2111 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2117 /* Return true if A is a multiple of B. */
2119 template<typename Ca, typename Cb>
2120 inline typename if_nonpoly2<Ca, Cb, bool>::type
2121 multiple_p (Ca a, Cb b)
2126 /* Return true if A is a (polynomial) multiple of B. */
2128 template<unsigned int N, typename Ca, typename Cb>
2129 inline typename if_nonpoly<Cb, bool>::type
2130 multiple_p (const poly_int_pod<N, Ca> &a, Cb b)
2132 for (unsigned int i = 0; i < N; ++i)
2133 if (a.coeffs[i] % b != 0)
2138 /* Return true if A is a (constant) multiple of B. */
2140 template<unsigned int N, typename Ca, typename Cb>
2141 inline typename if_nonpoly<Ca, bool>::type
2142 multiple_p (Ca a, const poly_int_pod<N, Cb> &b)
2144 typedef POLY_INT_TYPE (Ca) int_type;
2146 /* Do the modulus before the constant check, to catch divide by
2148 return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ());
2151 /* Return true if A is a (polynomial) multiple of B. This handles cases
2152 where either B is constant or the multiple is constant. */
2154 template<unsigned int N, typename Ca, typename Cb>
2156 multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
2158 if (b.is_constant ())
2159 return multiple_p (a, b.coeffs[0]);
2160 POLY_BINARY_COEFF (Ca, Ca) tmp;
2161 return constant_multiple_p (a, b, &tmp);
2164 /* Return true if A is a (constant) multiple of B, storing the
2165 multiple in *MULTIPLE if so. */
2167 template<typename Ca, typename Cb, typename Cm>
2168 inline typename if_nonpoly2<Ca, Cb, bool>::type
2169 multiple_p (Ca a, Cb b, Cm *multiple)
2177 /* Return true if A is a (polynomial) multiple of B, storing the
2178 multiple in *MULTIPLE if so. */
2180 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2181 inline typename if_nonpoly<Cb, bool>::type
2182 multiple_p (const poly_int_pod<N, Ca> &a, Cb b, poly_int_pod<N, Cm> *multiple)
2184 if (!multiple_p (a, b))
2186 for (unsigned int i = 0; i < N; ++i)
2187 multiple->coeffs[i] = a.coeffs[i] / b;
2191 /* Return true if B is a constant and A is a (constant) multiple of B,
2192 storing the multiple in *MULTIPLE if so. */
2194 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2195 inline typename if_nonpoly<Ca, bool>::type
2196 multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
2198 typedef POLY_CAST (Ca, Cb) NCa;
2200 /* Do the modulus before the constant check, to catch divide by
2202 if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ()))
2204 *multiple = a / b.coeffs[0];
2208 /* Return true if A is a (polynomial) multiple of B, storing the
2209 multiple in *MULTIPLE if so. This handles cases where either
2210 B is constant or the multiple is constant. */
2212 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2214 multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
2215 poly_int_pod<N, Cm> *multiple)
2217 if (b.is_constant ())
2218 return multiple_p (a, b.coeffs[0], multiple);
2219 return constant_multiple_p (a, b, multiple);
2222 /* Return A / B, given that A is known to be a multiple of B. */
2224 template<unsigned int N, typename Ca, typename Cb>
2225 inline POLY_CONST_RESULT (N, Ca, Cb)
2226 exact_div (const poly_int_pod<N, Ca> &a, Cb b)
2228 typedef POLY_CONST_COEFF (Ca, Cb) C;
2230 for (unsigned int i = 0; i < N; i++)
2232 gcc_checking_assert (a.coeffs[i] % b == 0);
2233 POLY_SET_COEFF (C, r, i, a.coeffs[i] / b);
2238 /* Return A / B, given that A is known to be a multiple of B. */
2240 template<unsigned int N, typename Ca, typename Cb>
2241 inline POLY_POLY_RESULT (N, Ca, Cb)
2242 exact_div (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
2244 if (b.is_constant ())
2245 return exact_div (a, b.coeffs[0]);
2247 typedef POLY_CAST (Ca, Cb) NCa;
2248 typedef POLY_CAST (Cb, Ca) NCb;
2249 typedef POLY_BINARY_COEFF (Ca, Cb) C;
2250 typedef POLY_INT_TYPE (Cb) int_type;
2252 gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0);
2253 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2254 for (unsigned int i = 1; i < N; ++i)
2255 gcc_checking_assert (b.coeffs[i] == int_type (0)
2256 ? a.coeffs[i] == int_type (0)
2257 : (a.coeffs[i] % b.coeffs[i] == 0
2258 && NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r));
2263 /* Return true if there is some constant Q and polynomial r such that:
2269 Store the value Q in *QUOTIENT if so. */
2271 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2272 inline typename if_nonpoly2<Cb, Cq, bool>::type
2273 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b, Cq *quotient)
2275 typedef POLY_CAST (Ca, Cb) NCa;
2276 typedef POLY_CAST (Cb, Ca) NCb;
2278 /* Do the division before the constant check, to catch divide by
2280 Cq q = NCa (a.coeffs[0]) / NCb (b);
2281 if (!a.is_constant ())
2287 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2288 inline typename if_nonpoly<Cq, bool>::type
2289 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
2290 const poly_int_pod<N, Cb> &b,
2293 /* We can calculate Q from the case in which the indeterminates
2295 typedef POLY_CAST (Ca, Cb) NCa;
2296 typedef POLY_CAST (Cb, Ca) NCb;
2297 typedef POLY_INT_TYPE (Ca) ICa;
2298 typedef POLY_INT_TYPE (Cb) ICb;
2299 typedef POLY_BINARY_COEFF (Ca, Cb) C;
2300 C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2302 /* Check the other coefficients and record whether the division is exact.
2303 The only difficult case is when it isn't. If we require a and b to
2304 ordered wrt zero, there can be no two coefficients of the same value
2305 that have opposite signs. This means that:
2307 |a| = |a0| + |a1 * x1| + |a2 * x2| + ...
2308 |b| = |b0| + |b1 * x1| + |b2 * x2| + ...
2310 The Q we've just calculated guarantees:
2313 |a0 - b0 * Q| < |b0|
2321 |bi * xi * Q| <= |ai * xi|
2323 for each i in [1, N]. This is trivially true when xi is zero.
2324 When it isn't we need:
2326 (2') |bi * Q| <= |ai|
2330 r = r0 + r1 * x1 + r2 * x2 + ...
2331 where ri = ai - bi * Q
2333 Restricting to ordered a and b also guarantees that no two ris
2334 have opposite signs, so we have:
2336 |r| = |r0| + |r1 * x1| + |r2 * x2| + ...
2338 We know from the calculation of Q that |r0| < |b0|, so:
2344 (3') |ai - bi * Q| <= |bi|
2346 for each i in [1, N]. */
2347 bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0;
2348 for (unsigned int i = 1; i < N; ++i)
2350 if (b.coeffs[i] == ICb (0))
2352 /* For bi == 0 we simply need: (3') |ai| == 0. */
2353 if (a.coeffs[i] != ICa (0))
2360 /* For Q == 0 we simply need: (3') |ai| <= |bi|. */
2361 if (a.coeffs[i] != ICa (0))
2363 /* Use negative absolute to avoid overflow, i.e.
2365 C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]);
2366 C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]);
2367 if (neg_abs_a < neg_abs_b)
2374 /* Otherwise just check for the case in which ai / bi == Q. */
2375 if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q)
2377 if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0)
2383 /* If the division isn't exact, require both values to be ordered wrt 0,
2384 so that we can guarantee conditions (2) and (3) for all indeterminate
2386 if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0))))
2393 /* Likewise, but also store r in *REMAINDER. */
2395 template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2396 inline typename if_nonpoly<Cq, bool>::type
2397 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
2398 const poly_int_pod<N, Cb> &b,
2399 Cq *quotient, Cr *remainder)
2401 if (!can_div_trunc_p (a, b, quotient))
2403 *remainder = a - *quotient * b;
2407 /* Return true if there is some polynomial q and constant R such that:
2413 Store the value q in *QUOTIENT if so. */
2415 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2416 inline typename if_nonpoly<Cb, bool>::type
2417 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
2418 poly_int_pod<N, Cq> *quotient)
2420 /* The remainder must be constant. */
2421 for (unsigned int i = 1; i < N; ++i)
2422 if (a.coeffs[i] % b != 0)
2424 for (unsigned int i = 0; i < N; ++i)
2425 quotient->coeffs[i] = a.coeffs[i] / b;
2429 /* Likewise, but also store R in *REMAINDER. */
2431 template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2432 inline typename if_nonpoly<Cb, bool>::type
2433 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
2434 poly_int_pod<N, Cq> *quotient, Cr *remainder)
2436 if (!can_div_trunc_p (a, b, quotient))
2438 *remainder = a.coeffs[0] % b;
2442 /* Return true if we can compute A / B at compile time, rounding towards zero.
2443 Store the result in QUOTIENT if so.
2445 This handles cases in which either B is constant or the result is
2448 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2450 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
2451 const poly_int_pod<N, Cb> &b,
2452 poly_int_pod<N, Cq> *quotient)
2454 if (b.is_constant ())
2455 return can_div_trunc_p (a, b.coeffs[0], quotient);
2456 if (!can_div_trunc_p (a, b, "ient->coeffs[0]))
2458 for (unsigned int i = 1; i < N; ++i)
2459 quotient->coeffs[i] = 0;
2463 /* Return true if there is some constant Q and polynomial r such that:
2469 Store the value Q in *QUOTIENT if so. */
2471 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2472 inline typename if_nonpoly<Cq, bool>::type
2473 can_div_away_from_zero_p (const poly_int_pod<N, Ca> &a,
2474 const poly_int_pod<N, Cb> &b,
2477 if (!can_div_trunc_p (a, b, quotient))
2479 if (maybe_ne (*quotient * b, a))
2480 *quotient += (*quotient < 0 ? -1 : 1);
2484 /* Use print_dec to print VALUE to FILE, where SGN is the sign
2487 template<unsigned int N, typename C>
2489 print_dec (const poly_int_pod<N, C> &value, FILE *file, signop sgn)
2491 if (value.is_constant ())
2492 print_dec (value.coeffs[0], file, sgn);
2495 fprintf (file, "[");
2496 for (unsigned int i = 0; i < N; ++i)
2498 print_dec (value.coeffs[i], file, sgn);
2499 fputc (i == N - 1 ? ']' : ',', file);
2504 /* Likewise without the signop argument, for coefficients that have an
2505 inherent signedness. */
2507 template<unsigned int N, typename C>
2509 print_dec (const poly_int_pod<N, C> &value, FILE *file)
2511 STATIC_ASSERT (poly_coeff_traits<C>::signedness >= 0);
2512 print_dec (value, file,
2513 poly_coeff_traits<C>::signedness ? SIGNED : UNSIGNED);
2516 /* Use print_hex to print VALUE to FILE. */
2518 template<unsigned int N, typename C>
2520 print_hex (const poly_int_pod<N, C> &value, FILE *file)
2522 if (value.is_constant ())
2523 print_hex (value.coeffs[0], file);
2526 fprintf (file, "[");
2527 for (unsigned int i = 0; i < N; ++i)
2529 print_hex (value.coeffs[i], file);
2530 fputc (i == N - 1 ? ']' : ',', file);
2535 /* Helper for calculating the distance between two points P1 and P2,
2536 in cases where known_le (P1, P2). T1 and T2 are the types of the
2537 two positions, in either order. The coefficients of P2 - P1 have
2538 type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2
2539 have C++ primitive type, otherwise P2 - P1 has its usual
2540 wide-int-based type.
2542 The actual subtraction should look something like this:
2544 typedef poly_span_traits<T1, T2> span_traits;
2545 span_traits::cast (P2) - span_traits::cast (P1)
2547 Applying the cast before the subtraction avoids undefined overflow
2548 for signed T1 and T2.
2550 The implementation of the cast tries to avoid unnecessary arithmetic
2552 template<typename T1, typename T2,
2553 typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2),
2554 unsigned HOST_WIDE_INT)>
2555 struct poly_span_traits
2557 template<typename T>
2558 static const T &cast (const T &x) { return x; }
2561 template<typename T1, typename T2>
2562 struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT>
2564 template<typename T>
2565 static typename if_nonpoly<T, unsigned HOST_WIDE_INT>::type
2566 cast (const T &x) { return x; }
2568 template<unsigned int N, typename T>
2569 static poly_int<N, unsigned HOST_WIDE_INT>
2570 cast (const poly_int_pod<N, T> &x) { return x; }
2573 /* Return true if SIZE represents a known size, assuming that all-ones
2574 indicates an unknown size. */
2576 template<typename T>
2578 known_size_p (const T &a)
2580 return maybe_ne (a, POLY_INT_TYPE (T) (-1));
2583 /* Return true if range [POS, POS + SIZE) might include VAL.
2584 SIZE can be the special value -1, in which case the range is
2587 template<typename T1, typename T2, typename T3>
2589 maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2591 typedef poly_span_traits<T1, T2> start_span;
2592 typedef poly_span_traits<T3, T3> size_span;
2593 if (known_lt (val, pos))
2595 if (!known_size_p (size))
2597 if ((poly_int_traits<T1>::num_coeffs > 1
2598 || poly_int_traits<T2>::num_coeffs > 1)
2599 && maybe_lt (val, pos))
2600 /* In this case we don't know whether VAL >= POS is true at compile
2601 time, so we can't prove that VAL >= POS + SIZE. */
2603 return maybe_lt (start_span::cast (val) - start_span::cast (pos),
2604 size_span::cast (size));
2607 /* Return true if range [POS, POS + SIZE) is known to include VAL.
2608 SIZE can be the special value -1, in which case the range is
2611 template<typename T1, typename T2, typename T3>
2613 known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2615 typedef poly_span_traits<T1, T2> start_span;
2616 typedef poly_span_traits<T3, T3> size_span;
2617 return (known_size_p (size)
2618 && known_ge (val, pos)
2619 && known_lt (start_span::cast (val) - start_span::cast (pos),
2620 size_span::cast (size)));
2623 /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2624 might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which
2625 case the range is open-ended. */
2627 template<typename T1, typename T2, typename T3, typename T4>
2629 ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1,
2630 const T3 &pos2, const T4 &size2)
2632 if (maybe_in_range_p (pos2, pos1, size1))
2633 return maybe_ne (size2, POLY_INT_TYPE (T4) (0));
2634 if (maybe_in_range_p (pos1, pos2, size2))
2635 return maybe_ne (size1, POLY_INT_TYPE (T2) (0));
2639 /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2640 are known to overlap. SIZE1 and/or SIZE2 can be the special value -1,
2641 in which case the range is open-ended. */
2643 template<typename T1, typename T2, typename T3, typename T4>
2645 ranges_known_overlap_p (const T1 &pos1, const T2 &size1,
2646 const T3 &pos2, const T4 &size2)
2648 typedef poly_span_traits<T1, T3> start_span;
2649 typedef poly_span_traits<T2, T2> size1_span;
2650 typedef poly_span_traits<T4, T4> size2_span;
2651 /* known_gt (POS1 + SIZE1, POS2) [infinite precision]
2652 --> known_gt (SIZE1, POS2 - POS1) [infinite precision]
2653 --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision]
2654 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative
2655 --> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))).
2657 Using the saturating subtraction enforces that SIZE1 must be
2658 nonzero, since known_gt (0, x) is false for all nonnegative x.
2659 If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing
2660 indeterminate number I makes the unsaturated condition easier to
2661 satisfy, so using a saturated coefficient of zero tests the case in
2662 which the indeterminate is zero (the minimum value). */
2663 return (known_size_p (size1)
2664 && known_size_p (size2)
2665 && known_lt (start_span::cast (pos2)
2666 - start_span::cast (lower_bound (pos1, pos2)),
2667 size1_span::cast (size1))
2668 && known_lt (start_span::cast (pos1)
2669 - start_span::cast (lower_bound (pos1, pos2)),
2670 size2_span::cast (size2)));
2673 /* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of
2674 [POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1,
2675 in which case the range is open-ended. */
2677 template<typename T1, typename T2, typename T3, typename T4>
2679 known_subrange_p (const T1 &pos1, const T2 &size1,
2680 const T3 &pos2, const T4 &size2)
2682 typedef typename poly_int_traits<T2>::coeff_type C2;
2683 typedef poly_span_traits<T1, T3> start_span;
2684 typedef poly_span_traits<T2, T4> size_span;
2685 return (known_gt (size1, POLY_INT_TYPE (T2) (0))
2686 && (poly_coeff_traits<C2>::signedness > 0
2687 || known_size_p (size1))
2688 && known_size_p (size2)
2689 && known_ge (pos1, pos2)
2690 && known_le (size1, size2)
2691 && known_le (start_span::cast (pos1) - start_span::cast (pos2),
2692 size_span::cast (size2) - size_span::cast (size1)));
2695 /* Return true if the endpoint of the range [POS, POS + SIZE) can be
2696 stored in a T, or if SIZE is the special value -1, which makes the
2697 range open-ended. */
2699 template<typename T>
2700 inline typename if_nonpoly<T, bool>::type
2701 endpoint_representable_p (const T &pos, const T &size)
2703 return (!known_size_p (size)
2704 || pos <= poly_coeff_traits<T>::max_value - size);
2707 template<unsigned int N, typename C>
2709 endpoint_representable_p (const poly_int_pod<N, C> &pos,
2710 const poly_int_pod<N, C> &size)
2712 if (known_size_p (size))
2713 for (unsigned int i = 0; i < N; ++i)
2714 if (pos.coeffs[i] > poly_coeff_traits<C>::max_value - size.coeffs[i])
2719 template<unsigned int N, typename C>
2721 gt_ggc_mx (poly_int_pod<N, C> *)
2725 template<unsigned int N, typename C>
2727 gt_pch_nx (poly_int_pod<N, C> *)
2731 template<unsigned int N, typename C>
2733 gt_pch_nx (poly_int_pod<N, C> *, gt_pointer_operator, void *)
2737 #undef POLY_SET_COEFF
2738 #undef POLY_INT_TYPE
2739 #undef POLY_BINARY_COEFF
2740 #undef CONST_CONST_RESULT
2741 #undef POLY_CONST_RESULT
2742 #undef CONST_POLY_RESULT
2743 #undef POLY_POLY_RESULT
2744 #undef POLY_CONST_COEFF
2745 #undef CONST_POLY_COEFF
2746 #undef POLY_POLY_COEFF