LCOV - code coverage report
Current view: top level - gcc - poly-int.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 402 406 99.0 %
Date: 2020-04-04 11:58:09 Functions: 61 64 95.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.