/* Polynomial integer classes. Copyright (C) 2014-2023 Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ /* This file provides a representation of sizes and offsets whose exact values depend on certain runtime properties. The motivating example is the Arm SVE ISA, in which the number of vector elements is only known at runtime. See doc/poly-int.texi for more details. Tests for poly-int.h are located in testsuite/gcc.dg/plugin, since they are too expensive (in terms of binary size) to be included as selftests. */ #ifndef HAVE_POLY_INT_H #define HAVE_POLY_INT_H template struct poly_int_pod; template class poly_int; /* poly_coeff_traiits describes the properties of a poly_int coefficient type T: - poly_coeff_traits::rank is less than poly_coeff_traits::rank if T1 can promote to T2. For C-like types the rank is: (2 * number of bytes) + (unsigned ? 1 : 0) wide_ints don't have a normal rank and so use a value of INT_MAX. Any fixed-width integer should be promoted to wide_int if possible and lead to an error otherwise. - poly_coeff_traits::int_type is the type to which an integer literal should be cast before comparing it with T. - poly_coeff_traits::precision is the number of bits that T can hold. - poly_coeff_traits::signedness is: 0 if T is unsigned 1 if T is signed -1 if T has no inherent sign (as for wide_int). - poly_coeff_traits::max_value, if defined, is the maximum value of T. - poly_coeff_traits::result is a type that can hold results of operations on T. This is different from T itself in cases where T is the result of an accessor like wi::to_offset. */ template::precision_type> struct poly_coeff_traits; template struct poly_coeff_traits { typedef T result; typedef T int_type; static const int signedness = (T (0) >= T (-1)); static const int precision = sizeof (T) * CHAR_BIT; static const T max_value = (signedness ? ((T (1) << (precision - 2)) + ((T (1) << (precision - 2)) - 1)) : T (-1)); static const int rank = sizeof (T) * 2 + !signedness; }; template struct poly_coeff_traits { typedef T result; typedef int int_type; static const int signedness = -1; static const int precision = WIDE_INT_MAX_PRECISION; static const int rank = INT_MAX; }; template struct poly_coeff_traits { typedef WI_UNARY_RESULT (T) result; typedef int int_type; /* These types are always signed. */ static const int signedness = 1; static const int precision = wi::int_traits::precision; static const int rank = precision * 2 / CHAR_BIT; }; /* Information about a pair of coefficient types. */ template struct poly_coeff_pair_traits { /* True if T1 can represent all the values of T2. Either: - T1 should be a type with the same signedness as T2 and no less precision. This allows things like int16_t -> int16_t and uint32_t -> uint64_t. - T1 should be signed, T2 should be unsigned, and T1 should be wider than T2. This allows things like uint16_t -> int32_t. This rules out cases in which T1 has less precision than T2 or where the conversion would reinterpret the top bit. E.g. int16_t -> uint32_t can be dangerous and should have an explicit cast if deliberate. */ static const bool lossless_p = (poly_coeff_traits::signedness == poly_coeff_traits::signedness ? (poly_coeff_traits::precision >= poly_coeff_traits::precision) : (poly_coeff_traits::signedness == 1 && poly_coeff_traits::signedness == 0 && (poly_coeff_traits::precision > poly_coeff_traits::precision))); /* 0 if T1 op T2 should promote to HOST_WIDE_INT, 1 if T1 op T2 should promote to unsigned HOST_WIDE_INT, 2 if T1 op T2 should use wide-int rules. */ #define RANK(X) poly_coeff_traits::rank static const int result_kind = ((RANK (T1) <= RANK (HOST_WIDE_INT) && RANK (T2) <= RANK (HOST_WIDE_INT)) ? 0 : (RANK (T1) <= RANK (unsigned HOST_WIDE_INT) && RANK (T2) <= RANK (unsigned HOST_WIDE_INT)) ? 1 : 2); #undef RANK }; /* SFINAE class that makes T3 available as "type" if T2 can represent all the values in T1. */ template::lossless_p> struct if_lossless; template struct if_lossless { typedef T3 type; }; /* poly_int_traits describes an integer type T that might be polynomial or non-polynomial: - poly_int_traits::is_poly is true if T is a poly_int-based type and false otherwise. - poly_int_traits::num_coeffs gives the number of coefficients in T if T is a poly_int and 1 otherwise. - poly_int_traits::coeff_type gives the coefficent type of T if T is a poly_int and T itself otherwise - poly_int_traits::int_type is a shorthand for typename poly_coeff_traits::int_type. */ template struct poly_int_traits { static const bool is_poly = false; static const unsigned int num_coeffs = 1; typedef T coeff_type; typedef typename poly_coeff_traits::int_type int_type; }; template struct poly_int_traits > { static const bool is_poly = true; static const unsigned int num_coeffs = N; typedef C coeff_type; typedef typename poly_coeff_traits::int_type int_type; }; template struct poly_int_traits > : poly_int_traits > { }; /* SFINAE class that makes T2 available as "type" if T1 is a non-polynomial type. */ template::is_poly> struct if_nonpoly {}; template struct if_nonpoly { typedef T2 type; }; /* SFINAE class that makes T3 available as "type" if both T1 and T2 are non-polynomial types. */ template::is_poly, bool is_poly2 = poly_int_traits::is_poly> struct if_nonpoly2 {}; template struct if_nonpoly2 { typedef T3 type; }; /* SFINAE class that makes T2 available as "type" if T1 is a polynomial type. */ template::is_poly> struct if_poly {}; template struct if_poly { typedef T2 type; }; /* poly_result describes the result of an operation on two types T1 and T2, where at least one of the types is polynomial: - poly_result::type gives the result type for the operation. The intention is to provide normal C-like rules for integer ranks, except that everything smaller than HOST_WIDE_INT promotes to HOST_WIDE_INT. - poly_result::cast is the type to which an operand of type T1 should be cast before doing the operation, to ensure that the operation is done at the right precision. Casting to poly_result::type would also work, but casting to this type is more efficient. */ template::result_kind> struct poly_result; /* Promote pair to HOST_WIDE_INT. */ template struct poly_result { typedef HOST_WIDE_INT type; /* T1 and T2 are primitive types, so cast values to T before operating on them. */ typedef type cast; }; /* Promote pair to unsigned HOST_WIDE_INT. */ template struct poly_result { typedef unsigned HOST_WIDE_INT type; /* T1 and T2 are primitive types, so cast values to T before operating on them. */ typedef type cast; }; /* Use normal wide-int rules. */ template struct poly_result { typedef WI_BINARY_RESULT (T1, T2) type; /* Don't cast values before operating on them; leave the wi:: routines to handle promotion as necessary. */ typedef const T1 &cast; }; /* The coefficient type for the result of a binary operation on two poly_ints, the first of which has coefficients of type C1 and the second of which has coefficients of type C2. */ #define POLY_POLY_COEFF(C1, C2) typename poly_result::type /* Enforce that T2 is non-polynomial and provide the cofficient type of the result of a binary operation in which the first operand is a poly_int with coefficients of type C1 and the second operand is a constant of type T2. */ #define POLY_CONST_COEFF(C1, T2) \ POLY_POLY_COEFF (C1, typename if_nonpoly::type) /* Likewise in reverse. */ #define CONST_POLY_COEFF(T1, C2) \ POLY_POLY_COEFF (typename if_nonpoly::type, C2) /* The result type for a binary operation on poly_int and poly_int. */ #define POLY_POLY_RESULT(N, C1, C2) poly_int /* Enforce that T2 is non-polynomial and provide the result type for a binary operation on poly_int and T2. */ #define POLY_CONST_RESULT(N, C1, T2) poly_int /* Enforce that T1 is non-polynomial and provide the result type for a binary operation on T1 and poly_int. */ #define CONST_POLY_RESULT(N, T1, C2) poly_int /* Enforce that T1 and T2 are non-polynomial and provide the result type for a binary operation on T1 and T2. */ #define CONST_CONST_RESULT(N, T1, T2) \ POLY_POLY_COEFF (typename if_nonpoly::type, \ typename if_nonpoly::type) /* The type to which a coefficient of type C1 should be cast before using it in a binary operation with a coefficient of type C2. */ #define POLY_CAST(C1, C2) typename poly_result::cast /* Provide the coefficient type for the result of T1 op T2, where T1 and T2 can be polynomial or non-polynomial. */ #define POLY_BINARY_COEFF(T1, T2) \ typename poly_result::coeff_type, \ typename poly_int_traits::coeff_type>::type /* The type to which an integer constant should be cast before comparing it with T. */ #define POLY_INT_TYPE(T) typename poly_int_traits::int_type /* RES is a poly_int result that has coefficients of type C and that is being built up a coefficient at a time. Set coefficient number I to VALUE in the most efficient way possible. For primitive C it is better to assign directly, since it avoids any further calls and so is more efficient when the compiler is built at -O0. But for wide-int based C it is better to construct the value in-place. This means that calls out to a wide-int.cc routine can take the address of RES rather than the address of a temporary. The dummy self-comparison against C * is just a way of checking that C gives the right type. */ #define POLY_SET_COEFF(C, RES, I, VALUE) \ ((void) (&(RES).coeffs[0] == (C *) (void *) &(RES).coeffs[0]), \ wi::int_traits::precision_type == wi::FLEXIBLE_PRECISION \ ? (void) ((RES).coeffs[I] = VALUE) \ : (void) ((RES).coeffs[I].~C (), new (&(RES).coeffs[I]) C (VALUE))) /* A base POD class for polynomial integers. The polynomial has N coefficients of type C. */ template struct poly_int_pod { public: template poly_int_pod &operator = (const poly_int_pod &); template typename if_nonpoly::type &operator = (const Ca &); template poly_int_pod &operator += (const poly_int_pod &); template typename if_nonpoly::type &operator += (const Ca &); template poly_int_pod &operator -= (const poly_int_pod &); template typename if_nonpoly::type &operator -= (const Ca &); template typename if_nonpoly::type &operator *= (const Ca &); poly_int_pod &operator <<= (unsigned int); bool is_constant () const; template typename if_lossless::type is_constant (T *) const; C to_constant () const; template static poly_int from (const poly_int_pod &, unsigned int, signop); template static poly_int from (const poly_int_pod &, signop); bool to_shwi (poly_int_pod *) const; bool to_uhwi (poly_int_pod *) const; poly_int force_shwi () const; poly_int force_uhwi () const; #if POLY_INT_CONVERSION operator C () const; #endif C coeffs[N]; }; template template inline poly_int_pod& poly_int_pod::operator = (const poly_int_pod &a) { for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, *this, i, a.coeffs[i]); return *this; } template template inline typename if_nonpoly >::type & poly_int_pod::operator = (const Ca &a) { POLY_SET_COEFF (C, *this, 0, a); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, *this, i, wi::ints_for::zero (this->coeffs[0])); return *this; } template template inline poly_int_pod& poly_int_pod::operator += (const poly_int_pod &a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] += a.coeffs[i]; return *this; } template template inline typename if_nonpoly >::type & poly_int_pod::operator += (const Ca &a) { this->coeffs[0] += a; return *this; } template template inline poly_int_pod& poly_int_pod::operator -= (const poly_int_pod &a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] -= a.coeffs[i]; return *this; } template template inline typename if_nonpoly >::type & poly_int_pod::operator -= (const Ca &a) { this->coeffs[0] -= a; return *this; } template template inline typename if_nonpoly >::type & poly_int_pod::operator *= (const Ca &a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] *= a; return *this; } template inline poly_int_pod& poly_int_pod::operator <<= (unsigned int a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] <<= a; return *this; } /* Return true if the polynomial value is a compile-time constant. */ template inline bool poly_int_pod::is_constant () const { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (this->coeffs[i] != 0) return false; return true; } /* Return true if the polynomial value is a compile-time constant, storing its value in CONST_VALUE if so. */ template template inline typename if_lossless::type poly_int_pod::is_constant (T *const_value) const { if (is_constant ()) { *const_value = this->coeffs[0]; return true; } return false; } /* Return the value of a polynomial that is already known to be a compile-time constant. NOTE: When using this function, please add a comment above the call explaining why we know the value is constant in that context. */ template inline C poly_int_pod::to_constant () const { gcc_checking_assert (is_constant ()); return this->coeffs[0]; } /* Convert X to a wide_int-based polynomial in which each coefficient has BITSIZE bits. If X's coefficients are smaller than BITSIZE, extend them according to SGN. */ template template inline poly_int poly_int_pod::from (const poly_int_pod &a, unsigned int bitsize, signop sgn) { poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], bitsize, sgn)); return r; } /* Convert X to a fixed_wide_int-based polynomial, extending according to SGN. */ template template inline poly_int poly_int_pod::from (const poly_int_pod &a, signop sgn) { poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], sgn)); return r; } /* Return true if the coefficients of this generic_wide_int-based polynomial can be represented as signed HOST_WIDE_INTs without loss of precision. Store the HOST_WIDE_INT representation in *R if so. */ template inline bool poly_int_pod::to_shwi (poly_int_pod *r) const { for (unsigned int i = 0; i < N; i++) if (!wi::fits_shwi_p (this->coeffs[i])) return false; for (unsigned int i = 0; i < N; i++) r->coeffs[i] = this->coeffs[i].to_shwi (); return true; } /* Return true if the coefficients of this generic_wide_int-based polynomial can be represented as unsigned HOST_WIDE_INTs without loss of precision. Store the unsigned HOST_WIDE_INT representation in *R if so. */ template inline bool poly_int_pod::to_uhwi (poly_int_pod *r) const { for (unsigned int i = 0; i < N; i++) if (!wi::fits_uhwi_p (this->coeffs[i])) return false; for (unsigned int i = 0; i < N; i++) r->coeffs[i] = this->coeffs[i].to_uhwi (); return true; } /* Force a generic_wide_int-based constant to HOST_WIDE_INT precision, truncating if necessary. */ template inline poly_int poly_int_pod::force_shwi () const { poly_int_pod r; for (unsigned int i = 0; i < N; i++) r.coeffs[i] = this->coeffs[i].to_shwi (); return r; } /* Force a generic_wide_int-based constant to unsigned HOST_WIDE_INT precision, truncating if necessary. */ template inline poly_int poly_int_pod::force_uhwi () const { poly_int_pod r; for (unsigned int i = 0; i < N; i++) r.coeffs[i] = this->coeffs[i].to_uhwi (); return r; } #if POLY_INT_CONVERSION /* Provide a conversion operator to constants. */ template inline poly_int_pod::operator C () const { gcc_checking_assert (this->is_constant ()); return this->coeffs[0]; } #endif /* The main class for polynomial integers. The class provides constructors that are necessarily missing from the POD base. */ template class poly_int : public poly_int_pod { public: poly_int () {} template poly_int (const poly_int &); template poly_int (const poly_int_pod &); template poly_int (const C0 &); template poly_int (const C0 &, const C1 &); template poly_int &operator = (const poly_int_pod &); template typename if_nonpoly::type &operator = (const Ca &); template poly_int &operator += (const poly_int_pod &); template typename if_nonpoly::type &operator += (const Ca &); template poly_int &operator -= (const poly_int_pod &); template typename if_nonpoly::type &operator -= (const Ca &); template typename if_nonpoly::type &operator *= (const Ca &); poly_int &operator <<= (unsigned int); }; template template inline poly_int::poly_int (const poly_int &a) { for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, *this, i, a.coeffs[i]); } template template inline poly_int::poly_int (const poly_int_pod &a) { for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, *this, i, a.coeffs[i]); } template template inline poly_int::poly_int (const C0 &c0) { POLY_SET_COEFF (C, *this, 0, c0); for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, *this, i, wi::ints_for::zero (this->coeffs[0])); } template template inline poly_int::poly_int (const C0 &c0, const C1 &c1) { STATIC_ASSERT (N >= 2); POLY_SET_COEFF (C, *this, 0, c0); POLY_SET_COEFF (C, *this, 1, c1); for (unsigned int i = 2; i < N; i++) POLY_SET_COEFF (C, *this, i, wi::ints_for::zero (this->coeffs[0])); } template template inline poly_int& poly_int::operator = (const poly_int_pod &a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] = a.coeffs[i]; return *this; } template template inline typename if_nonpoly >::type & poly_int::operator = (const Ca &a) { this->coeffs[0] = a; if (N >= 2) for (unsigned int i = 1; i < N; i++) this->coeffs[i] = wi::ints_for::zero (this->coeffs[0]); return *this; } template template inline poly_int& poly_int::operator += (const poly_int_pod &a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] += a.coeffs[i]; return *this; } template template inline typename if_nonpoly >::type & poly_int::operator += (const Ca &a) { this->coeffs[0] += a; return *this; } template template inline poly_int& poly_int::operator -= (const poly_int_pod &a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] -= a.coeffs[i]; return *this; } template template inline typename if_nonpoly >::type & poly_int::operator -= (const Ca &a) { this->coeffs[0] -= a; return *this; } template template inline typename if_nonpoly >::type & poly_int::operator *= (const Ca &a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] *= a; return *this; } template inline poly_int& poly_int::operator <<= (unsigned int a) { for (unsigned int i = 0; i < N; i++) this->coeffs[i] <<= a; return *this; } /* Return true if every coefficient of A is in the inclusive range [B, C]. */ template inline typename if_nonpoly::type coeffs_in_range_p (const Ca &a, const Cb &b, const Cc &c) { return a >= b && a <= c; } template inline typename if_nonpoly::type coeffs_in_range_p (const poly_int_pod &a, const Cb &b, const Cc &c) { for (unsigned int i = 0; i < N; i++) if (a.coeffs[i] < b || a.coeffs[i] > c) return false; return true; } namespace wi { /* Poly version of wi::shwi, with the same interface. */ template inline poly_int shwi (const poly_int_pod &a, unsigned int precision) { poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (hwi_with_prec, r, i, wi::shwi (a.coeffs[i], precision)); return r; } /* Poly version of wi::uhwi, with the same interface. */ template inline poly_int uhwi (const poly_int_pod &a, unsigned int precision) { poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (hwi_with_prec, r, i, wi::uhwi (a.coeffs[i], precision)); return r; } /* Poly version of wi::sext, with the same interface. */ template inline POLY_POLY_RESULT (N, Ca, Ca) sext (const poly_int_pod &a, unsigned int precision) { typedef POLY_POLY_COEFF (Ca, Ca) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::sext (a.coeffs[i], precision)); return r; } /* Poly version of wi::zext, with the same interface. */ template inline POLY_POLY_RESULT (N, Ca, Ca) zext (const poly_int_pod &a, unsigned int precision) { typedef POLY_POLY_COEFF (Ca, Ca) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::zext (a.coeffs[i], precision)); return r; } } template inline POLY_POLY_RESULT (N, Ca, Cb) operator + (const poly_int_pod &a, const poly_int_pod &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_POLY_COEFF (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) + b.coeffs[i]); return r; } template inline POLY_CONST_RESULT (N, Ca, Cb) operator + (const poly_int_pod &a, const Cb &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CONST_COEFF (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) + b); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i])); return r; } template inline CONST_POLY_RESULT (N, Ca, Cb) operator + (const Ca &a, const poly_int_pod &b) { typedef POLY_CAST (Cb, Ca) NCb; typedef CONST_POLY_COEFF (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, a + NCb (b.coeffs[0])); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, NCb (b.coeffs[i])); return r; } namespace wi { /* Poly versions of wi::add, with the same interface. */ template inline poly_int add (const poly_int_pod &a, const poly_int_pod &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i])); return r; } template inline poly_int add (const poly_int_pod &a, const Cb &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b)); for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], wi::ints_for::zero (b))); return r; } template inline poly_int add (const Ca &a, const poly_int_pod &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::add (a, b.coeffs[0])); for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, wi::add (wi::ints_for::zero (a), b.coeffs[i])); return r; } template inline poly_int add (const poly_int_pod &a, const poly_int_pod &b, signop sgn, wi::overflow_type *overflow) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b.coeffs[0], sgn, overflow)); for (unsigned int i = 1; i < N; i++) { wi::overflow_type suboverflow; POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i], sgn, &suboverflow)); wi::accumulate_overflow (*overflow, suboverflow); } return r; } } template inline POLY_POLY_RESULT (N, Ca, Cb) operator - (const poly_int_pod &a, const poly_int_pod &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_POLY_COEFF (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) - b.coeffs[i]); return r; } template inline POLY_CONST_RESULT (N, Ca, Cb) operator - (const poly_int_pod &a, const Cb &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CONST_COEFF (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) - b); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i])); return r; } template inline CONST_POLY_RESULT (N, Ca, Cb) operator - (const Ca &a, const poly_int_pod &b) { typedef POLY_CAST (Cb, Ca) NCb; typedef CONST_POLY_COEFF (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, a - NCb (b.coeffs[0])); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, -NCb (b.coeffs[i])); return r; } namespace wi { /* Poly versions of wi::sub, with the same interface. */ template inline poly_int sub (const poly_int_pod &a, const poly_int_pod &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i])); return r; } template inline poly_int sub (const poly_int_pod &a, const Cb &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b)); for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], wi::ints_for::zero (b))); return r; } template inline poly_int sub (const Ca &a, const poly_int_pod &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::sub (a, b.coeffs[0])); for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, wi::sub (wi::ints_for::zero (a), b.coeffs[i])); return r; } template inline poly_int sub (const poly_int_pod &a, const poly_int_pod &b, signop sgn, wi::overflow_type *overflow) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b.coeffs[0], sgn, overflow)); for (unsigned int i = 1; i < N; i++) { wi::overflow_type suboverflow; POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i], sgn, &suboverflow)); wi::accumulate_overflow (*overflow, suboverflow); } return r; } } template inline POLY_POLY_RESULT (N, Ca, Ca) operator - (const poly_int_pod &a) { typedef POLY_CAST (Ca, Ca) NCa; typedef POLY_POLY_COEFF (Ca, Ca) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, -NCa (a.coeffs[i])); return r; } namespace wi { /* Poly version of wi::neg, with the same interface. */ template inline poly_int neg (const poly_int_pod &a) { typedef WI_UNARY_RESULT (Ca) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i])); return r; } template inline poly_int neg (const poly_int_pod &a, wi::overflow_type *overflow) { typedef WI_UNARY_RESULT (Ca) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::neg (a.coeffs[0], overflow)); for (unsigned int i = 1; i < N; i++) { wi::overflow_type suboverflow; POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i], &suboverflow)); wi::accumulate_overflow (*overflow, suboverflow); } return r; } } template inline POLY_POLY_RESULT (N, Ca, Ca) operator ~ (const poly_int_pod &a) { if (N >= 2) return -1 - a; return ~a.coeffs[0]; } template inline POLY_CONST_RESULT (N, Ca, Cb) operator * (const poly_int_pod &a, const Cb &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CONST_COEFF (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) * b); return r; } template inline CONST_POLY_RESULT (N, Ca, Cb) operator * (const Ca &a, const poly_int_pod &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef CONST_POLY_COEFF (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, NCa (a) * b.coeffs[i]); return r; } namespace wi { /* Poly versions of wi::mul, with the same interface. */ template inline poly_int mul (const poly_int_pod &a, const Cb &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b)); return r; } template inline poly_int mul (const Ca &a, const poly_int_pod &b) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::mul (a, b.coeffs[i])); return r; } template inline poly_int mul (const poly_int_pod &a, const Cb &b, signop sgn, wi::overflow_type *overflow) { typedef WI_BINARY_RESULT (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, wi::mul (a.coeffs[0], b, sgn, overflow)); for (unsigned int i = 1; i < N; i++) { wi::overflow_type suboverflow; POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b, sgn, &suboverflow)); wi::accumulate_overflow (*overflow, suboverflow); } return r; } } template inline POLY_POLY_RESULT (N, Ca, Ca) operator << (const poly_int_pod &a, const Cb &b) { typedef POLY_CAST (Ca, Ca) NCa; typedef POLY_POLY_COEFF (Ca, Ca) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) << b); return r; } namespace wi { /* Poly version of wi::lshift, with the same interface. */ template inline poly_int lshift (const poly_int_pod &a, const Cb &b) { typedef WI_BINARY_RESULT (Ca, Ca) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, wi::lshift (a.coeffs[i], b)); return r; } } /* Poly version of sext_hwi, with the same interface. */ template inline poly_int sext_hwi (const poly_int &a, unsigned int precision) { poly_int_pod r; for (unsigned int i = 0; i < N; i++) r.coeffs[i] = sext_hwi (a.coeffs[i], precision); return r; } /* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative integer x. */ template inline bool maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1) { if (a1 != b1) /* a0 + a1 * x == b0 + b1 * x ==> (a1 - b1) * x == b0 - a0 ==> x == (b0 - a0) / (a1 - b1) We need to test whether that's a valid value of x. (b0 - a0) and (a1 - b1) must not have opposite signs and the result must be integral. */ return (a1 < b1 ? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0 : b0 >= a0 && (b0 - a0) % (a1 - b1) == 0); return a0 == b0; } /* Return true if a0 + a1 * x might equal b for some nonnegative integer x. */ template inline bool maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b) { if (a1 != 0) /* a0 + a1 * x == b ==> x == (b - a0) / a1 We need to test whether that's a valid value of x. (b - a0) and a1 must not have opposite signs and the result must be integral. */ return (a1 < 0 ? b <= a0 && (a0 - b) % a1 == 0 : b >= a0 && (b - a0) % a1 == 0); return a0 == b; } /* Return true if A might equal B for some indeterminate values. */ template inline bool maybe_eq (const poly_int_pod &a, const poly_int_pod &b) { STATIC_ASSERT (N <= 2); if (N == 2) return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]); return a.coeffs[0] == b.coeffs[0]; } template inline typename if_nonpoly::type maybe_eq (const poly_int_pod &a, const Cb &b) { STATIC_ASSERT (N <= 2); if (N == 2) return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b); return a.coeffs[0] == b; } template inline typename if_nonpoly::type maybe_eq (const Ca &a, const poly_int_pod &b) { STATIC_ASSERT (N <= 2); if (N == 2) return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a); return a == b.coeffs[0]; } template inline typename if_nonpoly2::type maybe_eq (const Ca &a, const Cb &b) { return a == b; } /* Return true if A might not equal B for some indeterminate values. */ template inline bool maybe_ne (const poly_int_pod &a, const poly_int_pod &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (a.coeffs[i] != b.coeffs[i]) return true; return a.coeffs[0] != b.coeffs[0]; } template inline typename if_nonpoly::type maybe_ne (const poly_int_pod &a, const Cb &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (a.coeffs[i] != 0) return true; return a.coeffs[0] != b; } template inline typename if_nonpoly::type maybe_ne (const Ca &a, const poly_int_pod &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (b.coeffs[i] != 0) return true; return a != b.coeffs[0]; } template inline typename if_nonpoly2::type maybe_ne (const Ca &a, const Cb &b) { return a != b; } /* Return true if A is known to be equal to B. */ #define known_eq(A, B) (!maybe_ne (A, B)) /* Return true if A is known to be unequal to B. */ #define known_ne(A, B) (!maybe_eq (A, B)) /* Return true if A might be less than or equal to B for some indeterminate values. */ template inline bool maybe_le (const poly_int_pod &a, const poly_int_pod &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (a.coeffs[i] < b.coeffs[i]) return true; return a.coeffs[0] <= b.coeffs[0]; } template inline typename if_nonpoly::type maybe_le (const poly_int_pod &a, const Cb &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (a.coeffs[i] < 0) return true; return a.coeffs[0] <= b; } template inline typename if_nonpoly::type maybe_le (const Ca &a, const poly_int_pod &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (b.coeffs[i] > 0) return true; return a <= b.coeffs[0]; } template inline typename if_nonpoly2::type maybe_le (const Ca &a, const Cb &b) { return a <= b; } /* Return true if A might be less than B for some indeterminate values. */ template inline bool maybe_lt (const poly_int_pod &a, const poly_int_pod &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (a.coeffs[i] < b.coeffs[i]) return true; return a.coeffs[0] < b.coeffs[0]; } template inline typename if_nonpoly::type maybe_lt (const poly_int_pod &a, const Cb &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (a.coeffs[i] < 0) return true; return a.coeffs[0] < b; } template inline typename if_nonpoly::type maybe_lt (const Ca &a, const poly_int_pod &b) { if (N >= 2) for (unsigned int i = 1; i < N; i++) if (b.coeffs[i] > 0) return true; return a < b.coeffs[0]; } template inline typename if_nonpoly2::type maybe_lt (const Ca &a, const Cb &b) { return a < b; } /* Return true if A may be greater than or equal to B. */ #define maybe_ge(A, B) maybe_le (B, A) /* Return true if A may be greater than B. */ #define maybe_gt(A, B) maybe_lt (B, A) /* Return true if A is known to be less than or equal to B. */ #define known_le(A, B) (!maybe_gt (A, B)) /* Return true if A is known to be less than B. */ #define known_lt(A, B) (!maybe_ge (A, B)) /* Return true if A is known to be greater than B. */ #define known_gt(A, B) (!maybe_le (A, B)) /* Return true if A is known to be greater than or equal to B. */ #define known_ge(A, B) (!maybe_lt (A, B)) /* Return true if A and B are ordered by the partial ordering known_le. */ template inline bool ordered_p (const T1 &a, const T2 &b) { return ((poly_int_traits::num_coeffs == 1 && poly_int_traits::num_coeffs == 1) || known_le (a, b) || known_le (b, a)); } /* Assert that A and B are known to be ordered and return the minimum of the two. NOTE: When using this function, please add a comment above the call explaining why we know the values are ordered in that context. */ template inline POLY_POLY_RESULT (N, Ca, Cb) ordered_min (const poly_int_pod &a, const poly_int_pod &b) { if (known_le (a, b)) return a; else { if (N > 1) gcc_checking_assert (known_le (b, a)); return b; } } template inline CONST_POLY_RESULT (N, Ca, Cb) ordered_min (const Ca &a, const poly_int_pod &b) { if (known_le (a, b)) return a; else { if (N > 1) gcc_checking_assert (known_le (b, a)); return b; } } template inline POLY_CONST_RESULT (N, Ca, Cb) ordered_min (const poly_int_pod &a, const Cb &b) { if (known_le (a, b)) return a; else { if (N > 1) gcc_checking_assert (known_le (b, a)); return b; } } /* Assert that A and B are known to be ordered and return the maximum of the two. NOTE: When using this function, please add a comment above the call explaining why we know the values are ordered in that context. */ template inline POLY_POLY_RESULT (N, Ca, Cb) ordered_max (const poly_int_pod &a, const poly_int_pod &b) { if (known_le (a, b)) return b; else { if (N > 1) gcc_checking_assert (known_le (b, a)); return a; } } template inline CONST_POLY_RESULT (N, Ca, Cb) ordered_max (const Ca &a, const poly_int_pod &b) { if (known_le (a, b)) return b; else { if (N > 1) gcc_checking_assert (known_le (b, a)); return a; } } template inline POLY_CONST_RESULT (N, Ca, Cb) ordered_max (const poly_int_pod &a, const Cb &b) { if (known_le (a, b)) return b; else { if (N > 1) gcc_checking_assert (known_le (b, a)); return a; } } /* Return a constant lower bound on the value of A, which is known to be nonnegative. */ template inline Ca constant_lower_bound (const poly_int_pod &a) { gcc_checking_assert (known_ge (a, POLY_INT_TYPE (Ca) (0))); return a.coeffs[0]; } /* Return the constant lower bound of A, given that it is no less than B. */ template inline POLY_CONST_COEFF (Ca, Cb) constant_lower_bound_with_limit (const poly_int_pod &a, const Cb &b) { if (known_ge (a, b)) return a.coeffs[0]; return b; } /* Return the constant upper bound of A, given that it is no greater than B. */ template inline POLY_CONST_COEFF (Ca, Cb) constant_upper_bound_with_limit (const poly_int_pod &a, const Cb &b) { if (known_le (a, b)) return a.coeffs[0]; return b; } /* Return a value that is known to be no greater than A and B. This will be the greatest lower bound for some indeterminate values but not necessarily for all. */ template inline POLY_CONST_RESULT (N, Ca, Cb) lower_bound (const poly_int_pod &a, const Cb &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_INT_TYPE (Cb) ICb; typedef POLY_CONST_COEFF (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b))); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0))); return r; } template inline CONST_POLY_RESULT (N, Ca, Cb) lower_bound (const Ca &a, const poly_int_pod &b) { return lower_bound (b, a); } template inline POLY_POLY_RESULT (N, Ca, Cb) lower_bound (const poly_int_pod &a, const poly_int_pod &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_POLY_COEFF (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i]))); return r; } template inline CONST_CONST_RESULT (N, Ca, Cb) lower_bound (const Ca &a, const Cb &b) { return a < b ? a : b; } /* Return a value that is known to be no less than A and B. This will be the least upper bound for some indeterminate values but not necessarily for all. */ template inline POLY_CONST_RESULT (N, Ca, Cb) upper_bound (const poly_int_pod &a, const Cb &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_INT_TYPE (Cb) ICb; typedef POLY_CONST_COEFF (Ca, Cb) C; poly_int r; POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b))); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0))); return r; } template inline CONST_POLY_RESULT (N, Ca, Cb) upper_bound (const Ca &a, const poly_int_pod &b) { return upper_bound (b, a); } template inline POLY_POLY_RESULT (N, Ca, Cb) upper_bound (const poly_int_pod &a, const poly_int_pod &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_POLY_COEFF (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i]))); return r; } /* Return the greatest common divisor of all nonzero coefficients, or zero if all coefficients are zero. */ template inline POLY_BINARY_COEFF (Ca, Ca) coeff_gcd (const poly_int_pod &a) { /* Find the first nonzero coefficient, stopping at 0 whatever happens. */ unsigned int i; for (i = N - 1; i > 0; --i) if (a.coeffs[i] != 0) break; typedef POLY_BINARY_COEFF (Ca, Ca) C; C r = a.coeffs[i]; for (unsigned int j = 0; j < i; ++j) if (a.coeffs[j] != 0) r = gcd (r, C (a.coeffs[j])); return r; } /* Return a value that is a multiple of both A and B. This will be the least common multiple for some indeterminate values but necessarily for all. */ template POLY_CONST_RESULT (N, Ca, Cb) common_multiple (const poly_int_pod &a, Cb b) { POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a); return a * (least_common_multiple (xgcd, b) / xgcd); } template inline CONST_POLY_RESULT (N, Ca, Cb) common_multiple (const Ca &a, const poly_int_pod &b) { return common_multiple (b, a); } /* Return a value that is a multiple of both A and B, asserting that such a value exists. The result will be the least common multiple for some indeterminate values but necessarily for all. NOTE: When using this function, please add a comment above the call explaining why we know the values have a common multiple (which might for example be because we know A / B is rational). */ template POLY_POLY_RESULT (N, Ca, Cb) force_common_multiple (const poly_int_pod &a, const poly_int_pod &b) { if (b.is_constant ()) return common_multiple (a, b.coeffs[0]); if (a.is_constant ()) return common_multiple (a.coeffs[0], b); typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_BINARY_COEFF (Ca, Cb) C; typedef POLY_INT_TYPE (Ca) ICa; for (unsigned int i = 1; i < N; ++i) if (a.coeffs[i] != ICa (0)) { C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i])); C amul = lcm / a.coeffs[i]; C bmul = lcm / b.coeffs[i]; for (unsigned int j = 0; j < N; ++j) gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul); return a * amul; } gcc_unreachable (); } /* Compare A and B for sorting purposes, returning -1 if A should come before B, 0 if A and B are identical, and 1 if A should come after B. This is a lexicographical compare of the coefficients in reverse order. A consequence of this is that all constant sizes come before all non-constant ones, regardless of magnitude (since a size is never negative). This is what most callers want. For example, when laying data out on the stack, it's better to keep all the constant-sized data together so that it can be accessed as a constant offset from a single base. */ template inline int compare_sizes_for_sort (const poly_int_pod &a, const poly_int_pod &b) { for (unsigned int i = N; i-- > 0; ) if (a.coeffs[i] != b.coeffs[i]) return a.coeffs[i] < b.coeffs[i] ? -1 : 1; return 0; } /* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */ template inline bool can_align_p (const poly_int_pod &value, Cb align) { for (unsigned int i = 1; i < N; i++) if ((value.coeffs[i] & (align - 1)) != 0) return false; return true; } /* Return true if we can align VALUE up to the smallest multiple of ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */ template inline bool can_align_up (const poly_int_pod &value, Cb align, poly_int_pod *aligned) { if (!can_align_p (value, align)) return false; *aligned = value + (-value.coeffs[0] & (align - 1)); return true; } /* Return true if we can align VALUE down to the largest multiple of ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */ template inline bool can_align_down (const poly_int_pod &value, Cb align, poly_int_pod *aligned) { if (!can_align_p (value, align)) return false; *aligned = value - (value.coeffs[0] & (align - 1)); return true; } /* Return true if we can align A and B up to the smallest multiples of ALIGN that are >= A and B respectively, and if doing so gives the same value. */ template inline bool known_equal_after_align_up (const poly_int_pod &a, const poly_int_pod &b, Cc align) { poly_int aligned_a; poly_int aligned_b; return (can_align_up (a, align, &aligned_a) && can_align_up (b, align, &aligned_b) && known_eq (aligned_a, aligned_b)); } /* Return true if we can align A and B down to the largest multiples of ALIGN that are <= A and B respectively, and if doing so gives the same value. */ template inline bool known_equal_after_align_down (const poly_int_pod &a, const poly_int_pod &b, Cc align) { poly_int aligned_a; poly_int aligned_b; return (can_align_down (a, align, &aligned_a) && can_align_down (b, align, &aligned_b) && known_eq (aligned_a, aligned_b)); } /* Assert that we can align VALUE to ALIGN at compile time and return the smallest multiple of ALIGN that is >= VALUE. NOTE: When using this function, please add a comment above the call explaining why we know the non-constant coefficients must already be a multiple of ALIGN. */ template inline poly_int force_align_up (const poly_int_pod &value, Cb align) { gcc_checking_assert (can_align_p (value, align)); return value + (-value.coeffs[0] & (align - 1)); } /* Assert that we can align VALUE to ALIGN at compile time and return the largest multiple of ALIGN that is <= VALUE. NOTE: When using this function, please add a comment above the call explaining why we know the non-constant coefficients must already be a multiple of ALIGN. */ template inline poly_int force_align_down (const poly_int_pod &value, Cb align) { gcc_checking_assert (can_align_p (value, align)); return value - (value.coeffs[0] & (align - 1)); } /* Return a value <= VALUE that is a multiple of ALIGN. It will be the greatest such value for some indeterminate values but not necessarily for all. */ template inline poly_int aligned_lower_bound (const poly_int_pod &value, Cb align) { poly_int r; for (unsigned int i = 0; i < N; i++) /* This form copes correctly with more type combinations than value.coeffs[i] & -align would. */ POLY_SET_COEFF (Ca, r, i, (value.coeffs[i] - (value.coeffs[i] & (align - 1)))); return r; } /* Return a value >= VALUE that is a multiple of ALIGN. It will be the least such value for some indeterminate values but not necessarily for all. */ template inline poly_int aligned_upper_bound (const poly_int_pod &value, Cb align) { poly_int r; for (unsigned int i = 0; i < N; i++) POLY_SET_COEFF (Ca, r, i, (value.coeffs[i] + (-value.coeffs[i] & (align - 1)))); return r; } /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE down to the largest multiple of ALIGN that is <= VALUE, then divide by ALIGN. NOTE: When using this function, please add a comment above the call explaining why we know the non-constant coefficients must already be a multiple of ALIGN. */ template inline poly_int force_align_down_and_div (const poly_int_pod &value, Cb align) { gcc_checking_assert (can_align_p (value, align)); poly_int r; POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0] - (value.coeffs[0] & (align - 1))) / align)); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align); return r; } /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE up to the smallest multiple of ALIGN that is >= VALUE, then divide by ALIGN. NOTE: When using this function, please add a comment above the call explaining why we know the non-constant coefficients must already be a multiple of ALIGN. */ template inline poly_int force_align_up_and_div (const poly_int_pod &value, Cb align) { gcc_checking_assert (can_align_p (value, align)); poly_int r; POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0] + (-value.coeffs[0] & (align - 1))) / align)); if (N >= 2) for (unsigned int i = 1; i < N; i++) POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align); return r; } /* Return true if we know at compile time the difference between VALUE and the equal or preceding multiple of ALIGN. Store the value in *MISALIGN if so. */ template inline bool known_misalignment (const poly_int_pod &value, Cb align, Cm *misalign) { gcc_checking_assert (align != 0); if (!can_align_p (value, align)) return false; *misalign = value.coeffs[0] & (align - 1); return true; } /* Return X & (Y - 1), asserting that this value is known. Please add an a comment above callers to this function to explain why the condition is known to hold. */ template inline POLY_BINARY_COEFF (Ca, Ca) force_get_misalignment (const poly_int_pod &a, Cb align) { gcc_checking_assert (can_align_p (a, align)); return a.coeffs[0] & (align - 1); } /* Return the maximum alignment that A is known to have. Return 0 if A is known to be zero. */ template inline POLY_BINARY_COEFF (Ca, Ca) known_alignment (const poly_int_pod &a) { typedef POLY_BINARY_COEFF (Ca, Ca) C; C r = a.coeffs[0]; for (unsigned int i = 1; i < N; ++i) r |= a.coeffs[i]; return r & -r; } /* Return true if we can compute A | B at compile time, storing the result in RES if so. */ template inline typename if_nonpoly::type can_ior_p (const poly_int_pod &a, Cb b, Cr *result) { /* Coefficients 1 and above must be a multiple of something greater than B. */ typedef POLY_INT_TYPE (Ca) int_type; if (N >= 2) for (unsigned int i = 1; i < N; i++) if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0)) return false; *result = a; result->coeffs[0] |= b; return true; } /* Return true if A is a constant multiple of B, storing the multiple in *MULTIPLE if so. */ template inline typename if_nonpoly::type constant_multiple_p (const poly_int_pod &a, Cb b, Cm *multiple) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; /* Do the modulus before the constant check, to catch divide by zero errors. */ if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ()) return false; *multiple = NCa (a.coeffs[0]) / NCb (b); return true; } template inline typename if_nonpoly::type constant_multiple_p (Ca a, const poly_int_pod &b, Cm *multiple) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_INT_TYPE (Ca) int_type; /* Do the modulus before the constant check, to catch divide by zero errors. */ if (NCa (a) % NCb (b.coeffs[0]) != 0 || (a != int_type (0) && !b.is_constant ())) return false; *multiple = NCa (a) / NCb (b.coeffs[0]); return true; } template inline bool constant_multiple_p (const poly_int_pod &a, const poly_int_pod &b, Cm *multiple) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_INT_TYPE (Ca) ICa; typedef POLY_INT_TYPE (Cb) ICb; typedef POLY_BINARY_COEFF (Ca, Cb) C; if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0) return false; C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]); for (unsigned int i = 1; i < N; ++i) if (b.coeffs[i] == ICb (0) ? a.coeffs[i] != ICa (0) : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r)) return false; *multiple = r; return true; } /* Return true if A is a constant multiple of B. */ template inline typename if_nonpoly::type constant_multiple_p (const poly_int_pod &a, Cb b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; /* Do the modulus before the constant check, to catch divide by zero errors. */ if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ()) return false; return true; } template inline typename if_nonpoly::type constant_multiple_p (Ca a, const poly_int_pod &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_INT_TYPE (Ca) int_type; /* Do the modulus before the constant check, to catch divide by zero errors. */ if (NCa (a) % NCb (b.coeffs[0]) != 0 || (a != int_type (0) && !b.is_constant ())) return false; return true; } template inline bool constant_multiple_p (const poly_int_pod &a, const poly_int_pod &b) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_INT_TYPE (Ca) ICa; typedef POLY_INT_TYPE (Cb) ICb; typedef POLY_BINARY_COEFF (Ca, Cb) C; if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0) return false; C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]); for (unsigned int i = 1; i < N; ++i) if (b.coeffs[i] == ICb (0) ? a.coeffs[i] != ICa (0) : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r)) return false; return true; } /* Return true if A is a multiple of B. */ template inline typename if_nonpoly2::type multiple_p (Ca a, Cb b) { return a % b == 0; } /* Return true if A is a (polynomial) multiple of B. */ template inline typename if_nonpoly::type multiple_p (const poly_int_pod &a, Cb b) { for (unsigned int i = 0; i < N; ++i) if (a.coeffs[i] % b != 0) return false; return true; } /* Return true if A is a (constant) multiple of B. */ template inline typename if_nonpoly::type multiple_p (Ca a, const poly_int_pod &b) { typedef POLY_INT_TYPE (Ca) int_type; /* Do the modulus before the constant check, to catch divide by potential zeros. */ return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ()); } /* Return true if A is a (polynomial) multiple of B. This handles cases where either B is constant or the multiple is constant. */ template inline bool multiple_p (const poly_int_pod &a, const poly_int_pod &b) { if (b.is_constant ()) return multiple_p (a, b.coeffs[0]); POLY_BINARY_COEFF (Ca, Ca) tmp; return constant_multiple_p (a, b, &tmp); } /* Return true if A is a (constant) multiple of B, storing the multiple in *MULTIPLE if so. */ template inline typename if_nonpoly2::type multiple_p (Ca a, Cb b, Cm *multiple) { if (a % b != 0) return false; *multiple = a / b; return true; } /* Return true if A is a (polynomial) multiple of B, storing the multiple in *MULTIPLE if so. */ template inline typename if_nonpoly::type multiple_p (const poly_int_pod &a, Cb b, poly_int_pod *multiple) { if (!multiple_p (a, b)) return false; for (unsigned int i = 0; i < N; ++i) multiple->coeffs[i] = a.coeffs[i] / b; return true; } /* Return true if B is a constant and A is a (constant) multiple of B, storing the multiple in *MULTIPLE if so. */ template inline typename if_nonpoly::type multiple_p (Ca a, const poly_int_pod &b, Cm *multiple) { typedef POLY_CAST (Ca, Cb) NCa; /* Do the modulus before the constant check, to catch divide by potential zeros. */ if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ())) return false; *multiple = a / b.coeffs[0]; return true; } /* Return true if A is a (polynomial) multiple of B, storing the multiple in *MULTIPLE if so. This handles cases where either B is constant or the multiple is constant. */ template inline bool multiple_p (const poly_int_pod &a, const poly_int_pod &b, poly_int_pod *multiple) { if (b.is_constant ()) return multiple_p (a, b.coeffs[0], multiple); return constant_multiple_p (a, b, multiple); } /* Return A / B, given that A is known to be a multiple of B. */ template inline POLY_CONST_RESULT (N, Ca, Cb) exact_div (const poly_int_pod &a, Cb b) { typedef POLY_CONST_COEFF (Ca, Cb) C; poly_int r; for (unsigned int i = 0; i < N; i++) { gcc_checking_assert (a.coeffs[i] % b == 0); POLY_SET_COEFF (C, r, i, a.coeffs[i] / b); } return r; } /* Return A / B, given that A is known to be a multiple of B. */ template inline POLY_POLY_RESULT (N, Ca, Cb) exact_div (const poly_int_pod &a, const poly_int_pod &b) { if (b.is_constant ()) return exact_div (a, b.coeffs[0]); typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_BINARY_COEFF (Ca, Cb) C; typedef POLY_INT_TYPE (Cb) int_type; gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0); C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]); for (unsigned int i = 1; i < N; ++i) gcc_checking_assert (b.coeffs[i] == int_type (0) ? a.coeffs[i] == int_type (0) : (a.coeffs[i] % b.coeffs[i] == 0 && NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r)); return r; } /* Return true if there is some constant Q and polynomial r such that: (1) a = b * Q + r (2) |b * Q| <= |a| (3) |r| < |b| Store the value Q in *QUOTIENT if so. */ template inline typename if_nonpoly2::type can_div_trunc_p (const poly_int_pod &a, Cb b, Cq *quotient) { typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; /* Do the division before the constant check, to catch divide by zero errors. */ Cq q = NCa (a.coeffs[0]) / NCb (b); if (!a.is_constant ()) return false; *quotient = q; return true; } template inline typename if_nonpoly::type can_div_trunc_p (const poly_int_pod &a, const poly_int_pod &b, Cq *quotient) { /* We can calculate Q from the case in which the indeterminates are zero. */ typedef POLY_CAST (Ca, Cb) NCa; typedef POLY_CAST (Cb, Ca) NCb; typedef POLY_INT_TYPE (Ca) ICa; typedef POLY_INT_TYPE (Cb) ICb; typedef POLY_BINARY_COEFF (Ca, Cb) C; C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]); /* Check the other coefficients and record whether the division is exact. The only difficult case is when it isn't. If we require a and b to ordered wrt zero, there can be no two coefficients of the same value that have opposite signs. This means that: |a| = |a0| + |a1 * x1| + |a2 * x2| + ... |b| = |b0| + |b1 * x1| + |b2 * x2| + ... The Q we've just calculated guarantees: |b0 * Q| <= |a0| |a0 - b0 * Q| < |b0| and so: (2) |b * Q| <= |a| is satisfied if: |bi * xi * Q| <= |ai * xi| for each i in [1, N]. This is trivially true when xi is zero. When it isn't we need: (2') |bi * Q| <= |ai| r is calculated as: r = r0 + r1 * x1 + r2 * x2 + ... where ri = ai - bi * Q Restricting to ordered a and b also guarantees that no two ris have opposite signs, so we have: |r| = |r0| + |r1 * x1| + |r2 * x2| + ... We know from the calculation of Q that |r0| < |b0|, so: (3) |r| < |b| is satisfied if: (3') |ai - bi * Q| <= |bi| for each i in [1, N]. */ bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0; for (unsigned int i = 1; i < N; ++i) { if (b.coeffs[i] == ICb (0)) { /* For bi == 0 we simply need: (3') |ai| == 0. */ if (a.coeffs[i] != ICa (0)) return false; } else { if (q == 0) { /* For Q == 0 we simply need: (3') |ai| <= |bi|. */ if (a.coeffs[i] != ICa (0)) { /* Use negative absolute to avoid overflow, i.e. -|ai| >= -|bi|. */ C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]); C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]); if (neg_abs_a < neg_abs_b) return false; rem_p = true; } } else { /* Otherwise just check for the case in which ai / bi == Q. */ if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q) return false; if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0) rem_p = true; } } } /* If the division isn't exact, require both values to be ordered wrt 0, so that we can guarantee conditions (2) and (3) for all indeterminate values. */ if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0)))) return false; *quotient = q; return true; } /* Likewise, but also store r in *REMAINDER. */ template inline typename if_nonpoly::type can_div_trunc_p (const poly_int_pod &a, const poly_int_pod &b, Cq *quotient, Cr *remainder) { if (!can_div_trunc_p (a, b, quotient)) return false; *remainder = a - *quotient * b; return true; } /* Return true if there is some polynomial q and constant R such that: (1) a = B * q + R (2) |B * q| <= |a| (3) |R| < |B| Store the value q in *QUOTIENT if so. */ template inline typename if_nonpoly::type can_div_trunc_p (const poly_int_pod &a, Cb b, poly_int_pod *quotient) { /* The remainder must be constant. */ for (unsigned int i = 1; i < N; ++i) if (a.coeffs[i] % b != 0) return false; for (unsigned int i = 0; i < N; ++i) quotient->coeffs[i] = a.coeffs[i] / b; return true; } /* Likewise, but also store R in *REMAINDER. */ template inline typename if_nonpoly::type can_div_trunc_p (const poly_int_pod &a, Cb b, poly_int_pod *quotient, Cr *remainder) { if (!can_div_trunc_p (a, b, quotient)) return false; *remainder = a.coeffs[0] % b; return true; } /* Return true if we can compute A / B at compile time, rounding towards zero. Store the result in QUOTIENT if so. This handles cases in which either B is constant or the result is constant. */ template inline bool can_div_trunc_p (const poly_int_pod &a, const poly_int_pod &b, poly_int_pod *quotient) { if (b.is_constant ()) return can_div_trunc_p (a, b.coeffs[0], quotient); if (!can_div_trunc_p (a, b, "ient->coeffs[0])) return false; for (unsigned int i = 1; i < N; ++i) quotient->coeffs[i] = 0; return true; } /* Return true if there is some constant Q and polynomial r such that: (1) a = b * Q + r (2) |a| <= |b * Q| (3) |r| < |b| Store the value Q in *QUOTIENT if so. */ template inline typename if_nonpoly::type can_div_away_from_zero_p (const poly_int_pod &a, const poly_int_pod &b, Cq *quotient) { if (!can_div_trunc_p (a, b, quotient)) return false; if (maybe_ne (*quotient * b, a)) *quotient += (*quotient < 0 ? -1 : 1); return true; } /* Use print_dec to print VALUE to FILE, where SGN is the sign of the values. */ template void print_dec (const poly_int_pod &value, FILE *file, signop sgn) { if (value.is_constant ()) print_dec (value.coeffs[0], file, sgn); else { fprintf (file, "["); for (unsigned int i = 0; i < N; ++i) { print_dec (value.coeffs[i], file, sgn); fputc (i == N - 1 ? ']' : ',', file); } } } /* Likewise without the signop argument, for coefficients that have an inherent signedness. */ template void print_dec (const poly_int_pod &value, FILE *file) { STATIC_ASSERT (poly_coeff_traits::signedness >= 0); print_dec (value, file, poly_coeff_traits::signedness ? SIGNED : UNSIGNED); } /* Use print_hex to print VALUE to FILE. */ template void print_hex (const poly_int_pod &value, FILE *file) { if (value.is_constant ()) print_hex (value.coeffs[0], file); else { fprintf (file, "["); for (unsigned int i = 0; i < N; ++i) { print_hex (value.coeffs[i], file); fputc (i == N - 1 ? ']' : ',', file); } } } /* Helper for calculating the distance between two points P1 and P2, in cases where known_le (P1, P2). T1 and T2 are the types of the two positions, in either order. The coefficients of P2 - P1 have type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2 have C++ primitive type, otherwise P2 - P1 has its usual wide-int-based type. The actual subtraction should look something like this: typedef poly_span_traits span_traits; span_traits::cast (P2) - span_traits::cast (P1) Applying the cast before the subtraction avoids undefined overflow for signed T1 and T2. The implementation of the cast tries to avoid unnecessary arithmetic or copying. */ template struct poly_span_traits { template static const T &cast (const T &x) { return x; } }; template struct poly_span_traits { template static typename if_nonpoly::type cast (const T &x) { return x; } template static poly_int cast (const poly_int_pod &x) { return x; } }; /* Return true if SIZE represents a known size, assuming that all-ones indicates an unknown size. */ template inline bool known_size_p (const T &a) { return maybe_ne (a, POLY_INT_TYPE (T) (-1)); } /* Return true if range [POS, POS + SIZE) might include VAL. SIZE can be the special value -1, in which case the range is open-ended. */ template inline bool maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size) { typedef poly_span_traits start_span; typedef poly_span_traits size_span; if (known_lt (val, pos)) return false; if (!known_size_p (size)) return true; if ((poly_int_traits::num_coeffs > 1 || poly_int_traits::num_coeffs > 1) && maybe_lt (val, pos)) /* In this case we don't know whether VAL >= POS is true at compile time, so we can't prove that VAL >= POS + SIZE. */ return true; return maybe_lt (start_span::cast (val) - start_span::cast (pos), size_span::cast (size)); } /* Return true if range [POS, POS + SIZE) is known to include VAL. SIZE can be the special value -1, in which case the range is open-ended. */ template inline bool known_in_range_p (const T1 &val, const T2 &pos, const T3 &size) { typedef poly_span_traits start_span; typedef poly_span_traits size_span; return (known_size_p (size) && known_ge (val, pos) && known_lt (start_span::cast (val) - start_span::cast (pos), size_span::cast (size))); } /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2) might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which case the range is open-ended. */ template inline bool ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1, const T3 &pos2, const T4 &size2) { if (maybe_in_range_p (pos2, pos1, size1)) return maybe_ne (size2, POLY_INT_TYPE (T4) (0)); if (maybe_in_range_p (pos1, pos2, size2)) return maybe_ne (size1, POLY_INT_TYPE (T2) (0)); return false; } /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2) are known to overlap. SIZE1 and/or SIZE2 can be the special value -1, in which case the range is open-ended. */ template inline bool ranges_known_overlap_p (const T1 &pos1, const T2 &size1, const T3 &pos2, const T4 &size2) { typedef poly_span_traits start_span; typedef poly_span_traits size1_span; typedef poly_span_traits size2_span; /* known_gt (POS1 + SIZE1, POS2) [infinite precision] --> known_gt (SIZE1, POS2 - POS1) [infinite precision] --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative --> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))). Using the saturating subtraction enforces that SIZE1 must be nonzero, since known_gt (0, x) is false for all nonnegative x. If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing indeterminate number I makes the unsaturated condition easier to satisfy, so using a saturated coefficient of zero tests the case in which the indeterminate is zero (the minimum value). */ return (known_size_p (size1) && known_size_p (size2) && known_lt (start_span::cast (pos2) - start_span::cast (lower_bound (pos1, pos2)), size1_span::cast (size1)) && known_lt (start_span::cast (pos1) - start_span::cast (lower_bound (pos1, pos2)), size2_span::cast (size2))); } /* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of [POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1, in which case the range is open-ended. */ template inline bool known_subrange_p (const T1 &pos1, const T2 &size1, const T3 &pos2, const T4 &size2) { typedef typename poly_int_traits::coeff_type C2; typedef poly_span_traits start_span; typedef poly_span_traits size_span; return (known_gt (size1, POLY_INT_TYPE (T2) (0)) && (poly_coeff_traits::signedness > 0 || known_size_p (size1)) && known_size_p (size2) && known_ge (pos1, pos2) && known_le (size1, size2) && known_le (start_span::cast (pos1) - start_span::cast (pos2), size_span::cast (size2) - size_span::cast (size1))); } /* Return true if the endpoint of the range [POS, POS + SIZE) can be stored in a T, or if SIZE is the special value -1, which makes the range open-ended. */ template inline typename if_nonpoly::type endpoint_representable_p (const T &pos, const T &size) { return (!known_size_p (size) || pos <= poly_coeff_traits::max_value - size); } template inline bool endpoint_representable_p (const poly_int_pod &pos, const poly_int_pod &size) { if (known_size_p (size)) for (unsigned int i = 0; i < N; ++i) if (pos.coeffs[i] > poly_coeff_traits::max_value - size.coeffs[i]) return false; return true; } template void gt_ggc_mx (poly_int_pod *) { } template void gt_pch_nx (poly_int_pod *) { } template void gt_pch_nx (poly_int_pod *, gt_pointer_operator, void *) { } #undef POLY_SET_COEFF #undef POLY_INT_TYPE #undef POLY_BINARY_COEFF #undef CONST_CONST_RESULT #undef POLY_CONST_RESULT #undef CONST_POLY_RESULT #undef POLY_POLY_RESULT #undef POLY_CONST_COEFF #undef CONST_POLY_COEFF #undef POLY_POLY_COEFF #endif