gcc/poly-int.h

   1 /* Polynomial integer classes.
   2    Copyright (C) 2014-2022 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 self-comparison against C * is just a way of checking
 328    that C gives the right type.  */
 329 #define POLY_SET_COEFF(C, RES, I, VALUE) \
 330   ((void) (&(RES).coeffs[0] == (C *) (void *) &(RES).coeffs[0]), \
 331    wi::int_traits<C>::precision_type == wi::FLEXIBLE_PRECISION \
 332    ? (void) ((RES).coeffs[I] = VALUE) \
 333    : (void) ((RES).coeffs[I].~C (), new (&(RES).coeffs[I]) C (VALUE)))
 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 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 poly_int_pod<N, C>::operator = (const poly_int_pod<N, Ca> &a)
 390 {
 391   for (unsigned int i = 0; i < N; i++)
 392     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 poly_int_pod<N, C>::operator = (const Ca &a)
 400 {
 401   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   return *this;
 406 }
 407
 408 template<unsigned int N, typename C>
 409 template<typename Ca>
 410 inline poly_int_pod<N, C>&
 411 poly_int_pod<N, C>::operator += (const poly_int_pod<N, Ca> &a)
 412 {
 413   for (unsigned int i = 0; i < N; i++)
 414     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 poly_int_pod<N, C>::operator += (const Ca &a)
 422 {
 423   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 poly_int_pod<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
 431 {
 432   for (unsigned int i = 0; i < N; i++)
 433     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 poly_int_pod<N, C>::operator -= (const Ca &a)
 441 {
 442   this->coeffs[0] -= a;
 443   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 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 poly_int_pod<N, C>::is_constant (T *const_value) const
 485 {
 486   if (is_constant ())
 487     {
 488       *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 poly_int_pod<N, C>::to_constant () const
 503 {
 504   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 poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a,
 516                           unsigned int bitsize, signop sgn)
 517 {
 518   poly_int<N, C> r;
 519   for (unsigned int i = 0; i < N; i++)
 520     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 poly_int_pod<N, C>::from (const poly_int_pod<N, Ca> &a, signop sgn)
 531 {
 532   poly_int<N, C> r;
 533   for (unsigned int i = 0; i < N; i++)
 534     POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], sgn));
 535   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 poly_int_pod<N, C>::to_shwi (poly_int_pod<N, HOST_WIDE_INT> *r) const
 545 {
 546   for (unsigned int i = 0; i < N; i++)
 547     if (!wi::fits_shwi_p (this->coeffs[i]))
 548       return false;
 549   for (unsigned int i = 0; i < N; i++)
 550     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 poly_int_pod<N, C>::to_uhwi (poly_int_pod<N, unsigned HOST_WIDE_INT> *r) const
 562 {
 563   for (unsigned int i = 0; i < N; i++)
 564     if (!wi::fits_uhwi_p (this->coeffs[i]))
 565       return false;
 566   for (unsigned int i = 0; i < N; i++)
 567     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 poly_int_pod<N, C>::force_shwi () const
 577 {
 578   poly_int_pod<N, HOST_WIDE_INT> r;
 579   for (unsigned int i = 0; i < N; i++)
 580     r.coeffs[i] = this->coeffs[i].to_shwi ();
 581   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   for (unsigned int i = 0; i < N; i++)
 593     r.coeffs[i] = this->coeffs[i].to_uhwi ();
 594   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 poly_int_pod<N, C>::operator C () const
 603 {
 604   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   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 poly_int<N, C>::poly_int (const poly_int<N, Ca> &a)
 651 {
 652   for (unsigned int i = 0; i < N; i++)
 653     POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
 654 }
 655
 656 template<unsigned int N, typename C>
 657 template<typename Ca>
 658 inline
 659 poly_int<N, C>::poly_int (const poly_int_pod<N, Ca> &a)
 660 {
 661   for (unsigned int i = 0; i < N; i++)
 662     POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
 663 }
 664
 665 template<unsigned int N, typename C>
 666 template<typename C0>
 667 inline
 668 poly_int<N, C>::poly_int (const C0 &c0)
 669 {
 670   POLY_SET_COEFF (C, *this, 0, c0);
 671   for (unsigned int i = 1; i < N; i++)
 672     POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
 673 }
 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 poly_int<N, C>::operator = (const poly_int_pod<N, Ca> &a)
 691 {
 692   for (unsigned int i = 0; i < N; i++)
 693     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 poly_int<N, C>::operator = (const Ca &a)
 701 {
 702   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   return *this;
 707 }
 708
 709 template<unsigned int N, typename C>
 710 template<typename Ca>
 711 inline poly_int<N, C>&
 712 poly_int<N, C>::operator += (const poly_int_pod<N, Ca> &a)
 713 {
 714   for (unsigned int i = 0; i < N; i++)
 715     this->coeffs[i] += a.coeffs[i];
 716   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 poly_int<N, C>::operator += (const Ca &a)
 723 {
 724   this->coeffs[0] += a;
 725   return *this;
 726 }
 727
 728 template<unsigned int N, typename C>
 729 template<typename Ca>
 730 inline poly_int<N, C>&
 731 poly_int<N, C>::operator -= (const poly_int_pod<N, Ca> &a)
 732 {
 733   for (unsigned int i = 0; i < N; i++)
 734     this->coeffs[i] -= a.coeffs[i];
 735   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 poly_int<N, C>::operator -= (const Ca &a)
 742 {
 743   this->coeffs[0] -= a;
 744   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 poly_int<N, C>::operator *= (const Ca &a)
 751 {
 752   for (unsigned int i = 0; i < N; i++)
 753     this->coeffs[i] *= a;
 754   return *this;
 755 }
 756
 757 template<unsigned int N, typename C>
 758 inline poly_int<N, C>&
 759 poly_int<N, C>::operator <<= (unsigned int a)
 760 {
 761   for (unsigned int i = 0; i < N; i++)
 762     this->coeffs[i] <<= a;
 763   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 coeffs_in_range_p (const poly_int_pod<N, Ca> &a, const Cb &b, const Cc &c)
 778 {
 779   for (unsigned int i = 0; i < N; i++)
 780     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 shwi (const poly_int_pod<N, HOST_WIDE_INT> &a, unsigned int precision)
 791 {
 792   poly_int<N, hwi_with_prec> r;
 793   for (unsigned int i = 0; i < N; i++)
 794     POLY_SET_COEFF (hwi_with_prec, r, i, wi::shwi (a.coeffs[i], precision));
 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 uhwi (const poly_int_pod<N, unsigned HOST_WIDE_INT> &a, unsigned int precision)
 803 {
 804   poly_int<N, hwi_with_prec> r;
 805   for (unsigned int i = 0; i < N; i++)
 806     POLY_SET_COEFF (hwi_with_prec, r, i, wi::uhwi (a.coeffs[i], precision));
 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 sext (const poly_int_pod<N, Ca> &a, unsigned int precision)
 815 {
 816   typedef POLY_POLY_COEFF (Ca, Ca) C;
 817   poly_int<N, C> r;
 818   for (unsigned int i = 0; i < N; i++)
 819     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 zext (const poly_int_pod<N, Ca> &a, unsigned int precision)
 828 {
 829   typedef POLY_POLY_COEFF (Ca, Ca) C;
 830   poly_int<N, C> r;
 831   for (unsigned int i = 0; i < N; i++)
 832     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 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   poly_int<N, C> r;
 844   for (unsigned int i = 0; i < N; i++)
 845     POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) + b.coeffs[i]);
 846   return r;
 847 }
 848
 849 template<unsigned int N, typename Ca, typename Cb>
 850 inline POLY_CONST_RESULT (N, Ca, Cb)
 851 operator + (const poly_int_pod<N, Ca> &a, const Cb &b)
 852 {
 853   typedef POLY_CAST (Ca, Cb) NCa;
 854   typedef POLY_CONST_COEFF (Ca, Cb) C;
 855   poly_int<N, C> r;
 856   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 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   poly_int<N, C> r;
 870   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 add (const Ca &a, const poly_int_pod<N, Cb> &b)
 907 {
 908   typedef WI_BINARY_RESULT (Ca, Cb) C;
 909   poly_int<N, C> r;
 910   POLY_SET_COEFF (C, r, 0, wi::add (a, b.coeffs[0]));
 911   for (unsigned int i = 1; i < N; i++)
 912     POLY_SET_COEFF (C, r, i, wi::add (wi::ints_for<Ca>::zero (a),
 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 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   poly_int<N, C> r;
 924   POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b.coeffs[0], sgn, overflow));
 925   for (unsigned int i = 1; i < N; i++)
 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 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   poly_int<N, C> r;
 943   for (unsigned int i = 0; i < N; i++)
 944     POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) - b.coeffs[i]);
 945   return r;
 946 }
 947
 948 template<unsigned int N, typename Ca, typename Cb>
 949 inline POLY_CONST_RESULT (N, Ca, Cb)
 950 operator - (const poly_int_pod<N, Ca> &a, const Cb &b)
 951 {
 952   typedef POLY_CAST (Ca, Cb) NCa;
 953   typedef POLY_CONST_COEFF (Ca, Cb) C;
 954   poly_int<N, C> r;
 955   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 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   poly_int<N, C> r;
 969   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 sub (const Ca &a, const poly_int_pod<N, Cb> &b)
1006 {
1007   typedef WI_BINARY_RESULT (Ca, Cb) C;
1008   poly_int<N, C> r;
1009   POLY_SET_COEFF (C, r, 0, wi::sub (a, b.coeffs[0]));
1010   for (unsigned int i = 1; i < N; i++)
1011     POLY_SET_COEFF (C, r, i, wi::sub (wi::ints_for<Ca>::zero (a),
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 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   poly_int<N, C> r;
1042   for (unsigned int i = 0; i < N; i++)
1043     POLY_SET_COEFF (C, r, i, -NCa (a.coeffs[i]));
1044   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 neg (const poly_int_pod<N, Ca> &a, wi::overflow_type *overflow)
1064 {
1065   typedef WI_UNARY_RESULT (Ca) C;
1066   poly_int<N, C> r;
1067   POLY_SET_COEFF (C, r, 0, wi::neg (a.coeffs[0], overflow));
1068   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 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   poly_int<N, C> r;
1094   for (unsigned int i = 0; i < N; i++)
1095     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 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   poly_int<N, C> r;
1106   for (unsigned int i = 0; i < N; i++)
1107     POLY_SET_COEFF (C, r, i, NCa (a) * b.coeffs[i]);
1108   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 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   poly_int<N, C> r;
1161   for (unsigned int i = 0; i < N; i++)
1162     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 /* Poly version of sext_hwi, with the same interface.  */
1182
1183 template<unsigned int N, typename C>
1184 inline poly_int<N, HOST_WIDE_INT>
1185 sext_hwi (const poly_int<N, C> &a, unsigned int precision)
1186 {
1187   poly_int_pod<N, HOST_WIDE_INT> r;
1188   for (unsigned int i = 0; i < N; i++)
1189     r.coeffs[i] = sext_hwi (a.coeffs[i], precision);
1190   return r;
1191 }
1192
1193
1194 /* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative
1195    integer x.  */
1196
1197 template<typename Ca, typename Cb>
1198 inline bool
1199 maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1)
1200 {
1201   if (a1 != b1)
1202      /*      a0 + a1 * x == b0 + b1 * x
1203        ==> (a1 - b1) * x == b0 - a0
1204        ==>             x == (b0 - a0) / (a1 - b1)
1205
1206        We need to test whether that's a valid value of x.
1207        (b0 - a0) and (a1 - b1) must not have opposite signs
1208        and the result must be integral.  */
1209     return (a1 < b1
1210             ? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0
1211             : b0 >= a0 && (b0 - a0) % (a1 - b1) == 0);
1212   return a0 == b0;
1213 }
1214
1215 /* Return true if a0 + a1 * x might equal b for some nonnegative
1216    integer x.  */
1217
1218 template<typename Ca, typename Cb>
1219 inline bool
1220 maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b)
1221 {
1222   if (a1 != 0)
1223      /*      a0 + a1 * x == b
1224        ==>             x == (b - a0) / a1
1225
1226        We need to test whether that's a valid value of x.
1227        (b - a0) and a1 must not have opposite signs and the
1228        result must be integral.  */
1229     return (a1 < 0
1230             ? b <= a0 && (a0 - b) % a1 == 0
1231             : b >= a0 && (b - a0) % a1 == 0);
1232   return a0 == b;
1233 }
1234
1235 /* Return true if A might equal B for some indeterminate values.  */
1236
1237 template<unsigned int N, typename Ca, typename Cb>
1238 inline bool
1239 maybe_eq (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1240 {
1241   STATIC_ASSERT (N <= 2);
1242   if (N == 2)
1243     return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]);
1244   return a.coeffs[0] == b.coeffs[0];
1245 }
1246
1247 template<unsigned int N, typename Ca, typename Cb>
1248 inline typename if_nonpoly<Cb, bool>::type
1249 maybe_eq (const poly_int_pod<N, Ca> &a, const Cb &b)
1250 {
1251   STATIC_ASSERT (N <= 2);
1252   if (N == 2)
1253     return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b);
1254   return a.coeffs[0] == b;
1255 }
1256
1257 template<unsigned int N, typename Ca, typename Cb>
1258 inline typename if_nonpoly<Ca, bool>::type
1259 maybe_eq (const Ca &a, const poly_int_pod<N, Cb> &b)
1260 {
1261   STATIC_ASSERT (N <= 2);
1262   if (N == 2)
1263     return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a);
1264   return a == b.coeffs[0];
1265 }
1266
1267 template<typename Ca, typename Cb>
1268 inline typename if_nonpoly2<Ca, Cb, bool>::type
1269 maybe_eq (const Ca &a, const Cb &b)
1270 {
1271   return a == b;
1272 }
1273
1274 /* Return true if A might not equal B for some indeterminate values.  */
1275
1276 template<unsigned int N, typename Ca, typename Cb>
1277 inline bool
1278 maybe_ne (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1279 {
1280   if (N >= 2)
1281     for (unsigned int i = 1; i < N; i++)
1282       if (a.coeffs[i] != b.coeffs[i])
1283         return true;
1284   return a.coeffs[0] != b.coeffs[0];
1285 }
1286
1287 template<unsigned int N, typename Ca, typename Cb>
1288 inline typename if_nonpoly<Cb, bool>::type
1289 maybe_ne (const poly_int_pod<N, Ca> &a, const Cb &b)
1290 {
1291   if (N >= 2)
1292     for (unsigned int i = 1; i < N; i++)
1293       if (a.coeffs[i] != 0)
1294         return true;
1295   return a.coeffs[0] != b;
1296 }
1297
1298 template<unsigned int N, typename Ca, typename Cb>
1299 inline typename if_nonpoly<Ca, bool>::type
1300 maybe_ne (const Ca &a, const poly_int_pod<N, Cb> &b)
1301 {
1302   if (N >= 2)
1303     for (unsigned int i = 1; i < N; i++)
1304       if (b.coeffs[i] != 0)
1305         return true;
1306   return a != b.coeffs[0];
1307 }
1308
1309 template<typename Ca, typename Cb>
1310 inline typename if_nonpoly2<Ca, Cb, bool>::type
1311 maybe_ne (const Ca &a, const Cb &b)
1312 {
1313   return a != b;
1314 }
1315
1316 /* Return true if A is known to be equal to B.  */
1317 #define known_eq(A, B) (!maybe_ne (A, B))
1318
1319 /* Return true if A is known to be unequal to B.  */
1320 #define known_ne(A, B) (!maybe_eq (A, B))
1321
1322 /* Return true if A might be less than or equal to B for some
1323    indeterminate values.  */
1324
1325 template<unsigned int N, typename Ca, typename Cb>
1326 inline bool
1327 maybe_le (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1328 {
1329   if (N >= 2)
1330     for (unsigned int i = 1; i < N; i++)
1331       if (a.coeffs[i] < b.coeffs[i])
1332         return true;
1333   return a.coeffs[0] <= b.coeffs[0];
1334 }
1335
1336 template<unsigned int N, typename Ca, typename Cb>
1337 inline typename if_nonpoly<Cb, bool>::type
1338 maybe_le (const poly_int_pod<N, Ca> &a, const Cb &b)
1339 {
1340   if (N >= 2)
1341     for (unsigned int i = 1; i < N; i++)
1342       if (a.coeffs[i] < 0)
1343         return true;
1344   return a.coeffs[0] <= b;
1345 }
1346
1347 template<unsigned int N, typename Ca, typename Cb>
1348 inline typename if_nonpoly<Ca, bool>::type
1349 maybe_le (const Ca &a, const poly_int_pod<N, Cb> &b)
1350 {
1351   if (N >= 2)
1352     for (unsigned int i = 1; i < N; i++)
1353       if (b.coeffs[i] > 0)
1354         return true;
1355   return a <= b.coeffs[0];
1356 }
1357
1358 template<typename Ca, typename Cb>
1359 inline typename if_nonpoly2<Ca, Cb, bool>::type
1360 maybe_le (const Ca &a, const Cb &b)
1361 {
1362   return a <= b;
1363 }
1364
1365 /* Return true if A might be less than B for some indeterminate values.  */
1366
1367 template<unsigned int N, typename Ca, typename Cb>
1368 inline bool
1369 maybe_lt (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1370 {
1371   if (N >= 2)
1372     for (unsigned int i = 1; i < N; i++)
1373       if (a.coeffs[i] < b.coeffs[i])
1374         return true;
1375   return a.coeffs[0] < b.coeffs[0];
1376 }
1377
1378 template<unsigned int N, typename Ca, typename Cb>
1379 inline typename if_nonpoly<Cb, bool>::type
1380 maybe_lt (const poly_int_pod<N, Ca> &a, const Cb &b)
1381 {
1382   if (N >= 2)
1383     for (unsigned int i = 1; i < N; i++)
1384       if (a.coeffs[i] < 0)
1385         return true;
1386   return a.coeffs[0] < b;
1387 }
1388
1389 template<unsigned int N, typename Ca, typename Cb>
1390 inline typename if_nonpoly<Ca, bool>::type
1391 maybe_lt (const Ca &a, const poly_int_pod<N, Cb> &b)
1392 {
1393   if (N >= 2)
1394     for (unsigned int i = 1; i < N; i++)
1395       if (b.coeffs[i] > 0)
1396         return true;
1397   return a < b.coeffs[0];
1398 }
1399
1400 template<typename Ca, typename Cb>
1401 inline typename if_nonpoly2<Ca, Cb, bool>::type
1402 maybe_lt (const Ca &a, const Cb &b)
1403 {
1404   return a < b;
1405 }
1406
1407 /* Return true if A may be greater than or equal to B.  */
1408 #define maybe_ge(A, B) maybe_le (B, A)
1409
1410 /* Return true if A may be greater than B.  */
1411 #define maybe_gt(A, B) maybe_lt (B, A)
1412
1413 /* Return true if A is known to be less than or equal to B.  */
1414 #define known_le(A, B) (!maybe_gt (A, B))
1415
1416 /* Return true if A is known to be less than B.  */
1417 #define known_lt(A, B) (!maybe_ge (A, B))
1418
1419 /* Return true if A is known to be greater than B.  */
1420 #define known_gt(A, B) (!maybe_le (A, B))
1421
1422 /* Return true if A is known to be greater than or equal to B.  */
1423 #define known_ge(A, B) (!maybe_lt (A, B))
1424
1425 /* Return true if A and B are ordered by the partial ordering known_le.  */
1426
1427 template<typename T1, typename T2>
1428 inline bool
1429 ordered_p (const T1 &a, const T2 &b)
1430 {
1431   return ((poly_int_traits<T1>::num_coeffs == 1
1432            && poly_int_traits<T2>::num_coeffs == 1)
1433           || known_le (a, b)
1434           || known_le (b, a));
1435 }
1436
1437 /* Assert that A and B are known to be ordered and return the minimum
1438    of the two.
1439
1440    NOTE: When using this function, please add a comment above the call
1441    explaining why we know the values are ordered in that context.  */
1442
1443 template<unsigned int N, typename Ca, typename Cb>
1444 inline POLY_POLY_RESULT (N, Ca, Cb)
1445 ordered_min (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1446 {
1447   if (known_le (a, b))
1448     return a;
1449   else
1450     {
1451       if (N > 1)
1452         gcc_checking_assert (known_le (b, a));
1453       return b;
1454     }
1455 }
1456
1457 template<unsigned int N, typename Ca, typename Cb>
1458 inline CONST_POLY_RESULT (N, Ca, Cb)
1459 ordered_min (const Ca &a, const poly_int_pod<N, Cb> &b)
1460 {
1461   if (known_le (a, b))
1462     return a;
1463   else
1464     {
1465       if (N > 1)
1466         gcc_checking_assert (known_le (b, a));
1467       return b;
1468     }
1469 }
1470
1471 template<unsigned int N, typename Ca, typename Cb>
1472 inline POLY_CONST_RESULT (N, Ca, Cb)
1473 ordered_min (const poly_int_pod<N, Ca> &a, const Cb &b)
1474 {
1475   if (known_le (a, b))
1476     return a;
1477   else
1478     {
1479       if (N > 1)
1480         gcc_checking_assert (known_le (b, a));
1481       return b;
1482     }
1483 }
1484
1485 /* Assert that A and B are known to be ordered and return the maximum
1486    of the two.
1487
1488    NOTE: When using this function, please add a comment above the call
1489    explaining why we know the values are ordered in that context.  */
1490
1491 template<unsigned int N, typename Ca, typename Cb>
1492 inline POLY_POLY_RESULT (N, Ca, Cb)
1493 ordered_max (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1494 {
1495   if (known_le (a, b))
1496     return b;
1497   else
1498     {
1499       if (N > 1)
1500         gcc_checking_assert (known_le (b, a));
1501       return a;
1502     }
1503 }
1504
1505 template<unsigned int N, typename Ca, typename Cb>
1506 inline CONST_POLY_RESULT (N, Ca, Cb)
1507 ordered_max (const Ca &a, const poly_int_pod<N, Cb> &b)
1508 {
1509   if (known_le (a, b))
1510     return b;
1511   else
1512     {
1513       if (N > 1)
1514         gcc_checking_assert (known_le (b, a));
1515       return a;
1516     }
1517 }
1518
1519 template<unsigned int N, typename Ca, typename Cb>
1520 inline POLY_CONST_RESULT (N, Ca, Cb)
1521 ordered_max (const poly_int_pod<N, Ca> &a, const Cb &b)
1522 {
1523   if (known_le (a, b))
1524     return b;
1525   else
1526     {
1527       if (N > 1)
1528         gcc_checking_assert (known_le (b, a));
1529       return a;
1530     }
1531 }
1532
1533 /* Return a constant lower bound on the value of A, which is known
1534    to be nonnegative.  */
1535
1536 template<unsigned int N, typename Ca>
1537 inline Ca
1538 constant_lower_bound (const poly_int_pod<N, Ca> &a)
1539 {
1540   gcc_checking_assert (known_ge (a, POLY_INT_TYPE (Ca) (0)));
1541   return a.coeffs[0];
1542 }
1543
1544 /* Return the constant lower bound of A, given that it is no less than B.  */
1545
1546 template<unsigned int N, typename Ca, typename Cb>
1547 inline POLY_CONST_COEFF (Ca, Cb)
1548 constant_lower_bound_with_limit (const poly_int_pod<N, Ca> &a, const Cb &b)
1549 {
1550   if (known_ge (a, b))
1551     return a.coeffs[0];
1552   return b;
1553 }
1554
1555 /* Return the constant upper bound of A, given that it is no greater
1556    than B.  */
1557
1558 template<unsigned int N, typename Ca, typename Cb>
1559 inline POLY_CONST_COEFF (Ca, Cb)
1560 constant_upper_bound_with_limit (const poly_int_pod<N, Ca> &a, const Cb &b)
1561 {
1562   if (known_le (a, b))
1563     return a.coeffs[0];
1564   return b;
1565 }
1566
1567 /* Return a value that is known to be no greater than A and B.  This
1568    will be the greatest lower bound for some indeterminate values but
1569    not necessarily for all.  */
1570
1571 template<unsigned int N, typename Ca, typename Cb>
1572 inline POLY_CONST_RESULT (N, Ca, Cb)
1573 lower_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
1574 {
1575   typedef POLY_CAST (Ca, Cb) NCa;
1576   typedef POLY_CAST (Cb, Ca) NCb;
1577   typedef POLY_INT_TYPE (Cb) ICb;
1578   typedef POLY_CONST_COEFF (Ca, Cb) C;
1579
1580   poly_int<N, C> r;
1581   POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b)));
1582   if (N >= 2)
1583     for (unsigned int i = 1; i < N; i++)
1584       POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0)));
1585   return r;
1586 }
1587
1588 template<unsigned int N, typename Ca, typename Cb>
1589 inline CONST_POLY_RESULT (N, Ca, Cb)
1590 lower_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
1591 {
1592   return lower_bound (b, a);
1593 }
1594
1595 template<unsigned int N, typename Ca, typename Cb>
1596 inline POLY_POLY_RESULT (N, Ca, Cb)
1597 lower_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1598 {
1599   typedef POLY_CAST (Ca, Cb) NCa;
1600   typedef POLY_CAST (Cb, Ca) NCb;
1601   typedef POLY_POLY_COEFF (Ca, Cb) C;
1602
1603   poly_int<N, C> r;
1604   for (unsigned int i = 0; i < N; i++)
1605     POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1606   return r;
1607 }
1608
1609 template<typename Ca, typename Cb>
1610 inline CONST_CONST_RESULT (N, Ca, Cb)
1611 lower_bound (const Ca &a, const Cb &b)
1612 {
1613   return a < b ? a : b;
1614 }
1615
1616 /* Return a value that is known to be no less than A and B.  This will
1617    be the least upper bound for some indeterminate values but not
1618    necessarily for all.  */
1619
1620 template<unsigned int N, typename Ca, typename Cb>
1621 inline POLY_CONST_RESULT (N, Ca, Cb)
1622 upper_bound (const poly_int_pod<N, Ca> &a, const Cb &b)
1623 {
1624   typedef POLY_CAST (Ca, Cb) NCa;
1625   typedef POLY_CAST (Cb, Ca) NCb;
1626   typedef POLY_INT_TYPE (Cb) ICb;
1627   typedef POLY_CONST_COEFF (Ca, Cb) C;
1628
1629   poly_int<N, C> r;
1630   POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b)));
1631   if (N >= 2)
1632     for (unsigned int i = 1; i < N; i++)
1633       POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0)));
1634   return r;
1635 }
1636
1637 template<unsigned int N, typename Ca, typename Cb>
1638 inline CONST_POLY_RESULT (N, Ca, Cb)
1639 upper_bound (const Ca &a, const poly_int_pod<N, Cb> &b)
1640 {
1641   return upper_bound (b, a);
1642 }
1643
1644 template<unsigned int N, typename Ca, typename Cb>
1645 inline POLY_POLY_RESULT (N, Ca, Cb)
1646 upper_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
1647 {
1648   typedef POLY_CAST (Ca, Cb) NCa;
1649   typedef POLY_CAST (Cb, Ca) NCb;
1650   typedef POLY_POLY_COEFF (Ca, Cb) C;
1651
1652   poly_int<N, C> r;
1653   for (unsigned int i = 0; i < N; i++)
1654     POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1655   return r;
1656 }
1657
1658 /* Return the greatest common divisor of all nonzero coefficients, or zero
1659    if all coefficients are zero.  */
1660
1661 template<unsigned int N, typename Ca>
1662 inline POLY_BINARY_COEFF (Ca, Ca)
1663 coeff_gcd (const poly_int_pod<N, Ca> &a)
1664 {
1665   /* Find the first nonzero coefficient, stopping at 0 whatever happens.  */
1666   unsigned int i;
1667   for (i = N - 1; i > 0; --i)
1668     if (a.coeffs[i] != 0)
1669       break;
1670   typedef POLY_BINARY_COEFF (Ca, Ca) C;
1671   C r = a.coeffs[i];
1672   for (unsigned int j = 0; j < i; ++j)
1673     if (a.coeffs[j] != 0)
1674       r = gcd (r, C (a.coeffs[j]));
1675   return r;
1676 }
1677
1678 /* Return a value that is a multiple of both A and B.  This will be the
1679    least common multiple for some indeterminate values but necessarily
1680    for all.  */
1681
1682 template<unsigned int N, typename Ca, typename Cb>
1683 POLY_CONST_RESULT (N, Ca, Cb)
1684 common_multiple (const poly_int_pod<N, Ca> &a, Cb b)
1685 {
1686   POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a);
1687   return a * (least_common_multiple (xgcd, b) / xgcd);
1688 }
1689
1690 template<unsigned int N, typename Ca, typename Cb>
1691 inline CONST_POLY_RESULT (N, Ca, Cb)
1692 common_multiple (const Ca &a, const poly_int_pod<N, Cb> &b)
1693 {
1694   return common_multiple (b, a);
1695 }
1696
1697 /* Return a value that is a multiple of both A and B, asserting that
1698    such a value exists.  The result will be the least common multiple
1699    for some indeterminate values but necessarily for all.
1700
1701    NOTE: When using this function, please add a comment above the call
1702    explaining why we know the values have a common multiple (which might
1703    for example be because we know A / B is rational).  */
1704
1705 template<unsigned int N, typename Ca, typename Cb>
1706 POLY_POLY_RESULT (N, Ca, Cb)
1707 force_common_multiple (const poly_int_pod<N, Ca> &a,
1708                        const poly_int_pod<N, Cb> &b)
1709 {
1710   if (b.is_constant ())
1711     return common_multiple (a, b.coeffs[0]);
1712   if (a.is_constant ())
1713     return common_multiple (a.coeffs[0], b);
1714
1715   typedef POLY_CAST (Ca, Cb) NCa;
1716   typedef POLY_CAST (Cb, Ca) NCb;
1717   typedef POLY_BINARY_COEFF (Ca, Cb) C;
1718   typedef POLY_INT_TYPE (Ca) ICa;
1719
1720   for (unsigned int i = 1; i < N; ++i)
1721     if (a.coeffs[i] != ICa (0))
1722       {
1723         C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i]));
1724         C amul = lcm / a.coeffs[i];
1725         C bmul = lcm / b.coeffs[i];
1726         for (unsigned int j = 0; j < N; ++j)
1727           gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul);
1728         return a * amul;
1729       }
1730   gcc_unreachable ();
1731 }
1732
1733 /* Compare A and B for sorting purposes, returning -1 if A should come
1734    before B, 0 if A and B are identical, and 1 if A should come after B.
1735    This is a lexicographical compare of the coefficients in reverse order.
1736
1737    A consequence of this is that all constant sizes come before all
1738    non-constant ones, regardless of magnitude (since a size is never
1739    negative).  This is what most callers want.  For example, when laying
1740    data out on the stack, it's better to keep all the constant-sized
1741    data together so that it can be accessed as a constant offset from a
1742    single base.  */
1743
1744 template<unsigned int N, typename Ca, typename Cb>
1745 inline int
1746 compare_sizes_for_sort (const poly_int_pod<N, Ca> &a,
1747                         const poly_int_pod<N, Cb> &b)
1748 {
1749   for (unsigned int i = N; i-- > 0; )
1750     if (a.coeffs[i] != b.coeffs[i])
1751       return a.coeffs[i] < b.coeffs[i] ? -1 : 1;
1752   return 0;
1753 }
1754
1755 /* Return true if we can calculate VALUE & (ALIGN - 1) at compile time.  */
1756
1757 template<unsigned int N, typename Ca, typename Cb>
1758 inline bool
1759 can_align_p (const poly_int_pod<N, Ca> &value, Cb align)
1760 {
1761   for (unsigned int i = 1; i < N; i++)
1762     if ((value.coeffs[i] & (align - 1)) != 0)
1763       return false;
1764   return true;
1765 }
1766
1767 /* Return true if we can align VALUE up to the smallest multiple of
1768    ALIGN that is >= VALUE.  Store the aligned value in *ALIGNED if so.  */
1769
1770 template<unsigned int N, typename Ca, typename Cb>
1771 inline bool
1772 can_align_up (const poly_int_pod<N, Ca> &value, Cb align,
1773               poly_int_pod<N, Ca> *aligned)
1774 {
1775   if (!can_align_p (value, align))
1776     return false;
1777   *aligned = value + (-value.coeffs[0] & (align - 1));
1778   return true;
1779 }
1780
1781 /* Return true if we can align VALUE down to the largest multiple of
1782    ALIGN that is <= VALUE.  Store the aligned value in *ALIGNED if so.  */
1783
1784 template<unsigned int N, typename Ca, typename Cb>
1785 inline bool
1786 can_align_down (const poly_int_pod<N, Ca> &value, Cb align,
1787                 poly_int_pod<N, Ca> *aligned)
1788 {
1789   if (!can_align_p (value, align))
1790     return false;
1791   *aligned = value - (value.coeffs[0] & (align - 1));
1792   return true;
1793 }
1794
1795 /* Return true if we can align A and B up to the smallest multiples of
1796    ALIGN that are >= A and B respectively, and if doing so gives the
1797    same value.  */
1798
1799 template<unsigned int N, typename Ca, typename Cb, typename Cc>
1800 inline bool
1801 known_equal_after_align_up (const poly_int_pod<N, Ca> &a,
1802                             const poly_int_pod<N, Cb> &b,
1803                             Cc align)
1804 {
1805   poly_int<N, Ca> aligned_a;
1806   poly_int<N, Cb> aligned_b;
1807   return (can_align_up (a, align, &aligned_a)
1808           && can_align_up (b, align, &aligned_b)
1809           && known_eq (aligned_a, aligned_b));
1810 }
1811
1812 /* Return true if we can align A and B down to the largest multiples of
1813    ALIGN that are <= A and B respectively, and if doing so gives the
1814    same value.  */
1815
1816 template<unsigned int N, typename Ca, typename Cb, typename Cc>
1817 inline bool
1818 known_equal_after_align_down (const poly_int_pod<N, Ca> &a,
1819                               const poly_int_pod<N, Cb> &b,
1820                               Cc align)
1821 {
1822   poly_int<N, Ca> aligned_a;
1823   poly_int<N, Cb> aligned_b;
1824   return (can_align_down (a, align, &aligned_a)
1825           && can_align_down (b, align, &aligned_b)
1826           && known_eq (aligned_a, aligned_b));
1827 }
1828
1829 /* Assert that we can align VALUE to ALIGN at compile time and return
1830    the smallest multiple of ALIGN that is >= VALUE.
1831
1832    NOTE: When using this function, please add a comment above the call
1833    explaining why we know the non-constant coefficients must already
1834    be a multiple of ALIGN.  */
1835
1836 template<unsigned int N, typename Ca, typename Cb>
1837 inline poly_int<N, Ca>
1838 force_align_up (const poly_int_pod<N, Ca> &value, Cb align)
1839 {
1840   gcc_checking_assert (can_align_p (value, align));
1841   return value + (-value.coeffs[0] & (align - 1));
1842 }
1843
1844 /* Assert that we can align VALUE to ALIGN at compile time and return
1845    the largest multiple of ALIGN that is <= VALUE.
1846
1847    NOTE: When using this function, please add a comment above the call
1848    explaining why we know the non-constant coefficients must already
1849    be a multiple of ALIGN.  */
1850
1851 template<unsigned int N, typename Ca, typename Cb>
1852 inline poly_int<N, Ca>
1853 force_align_down (const poly_int_pod<N, Ca> &value, Cb align)
1854 {
1855   gcc_checking_assert (can_align_p (value, align));
1856   return value - (value.coeffs[0] & (align - 1));
1857 }
1858
1859 /* Return a value <= VALUE that is a multiple of ALIGN.  It will be the
1860    greatest such value for some indeterminate values but not necessarily
1861    for all.  */
1862
1863 template<unsigned int N, typename Ca, typename Cb>
1864 inline poly_int<N, Ca>
1865 aligned_lower_bound (const poly_int_pod<N, Ca> &value, Cb align)
1866 {
1867   poly_int<N, Ca> r;
1868   for (unsigned int i = 0; i < N; i++)
1869     /* This form copes correctly with more type combinations than
1870        value.coeffs[i] & -align would.  */
1871     POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1872                                - (value.coeffs[i] & (align - 1))));
1873   return r;
1874 }
1875
1876 /* Return a value >= VALUE that is a multiple of ALIGN.  It will be the
1877    least such value for some indeterminate values but not necessarily
1878    for all.  */
1879
1880 template<unsigned int N, typename Ca, typename Cb>
1881 inline poly_int<N, Ca>
1882 aligned_upper_bound (const poly_int_pod<N, Ca> &value, Cb align)
1883 {
1884   poly_int<N, Ca> r;
1885   for (unsigned int i = 0; i < N; i++)
1886     POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1887                                + (-value.coeffs[i] & (align - 1))));
1888   return r;
1889 }
1890
1891 /* Assert that we can align VALUE to ALIGN at compile time.  Align VALUE
1892    down to the largest multiple of ALIGN that is <= VALUE, then divide by
1893    ALIGN.
1894
1895    NOTE: When using this function, please add a comment above the call
1896    explaining why we know the non-constant coefficients must already
1897    be a multiple of ALIGN.  */
1898
1899 template<unsigned int N, typename Ca, typename Cb>
1900 inline poly_int<N, Ca>
1901 force_align_down_and_div (const poly_int_pod<N, Ca> &value, Cb align)
1902 {
1903   gcc_checking_assert (can_align_p (value, align));
1904
1905   poly_int<N, Ca> r;
1906   POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1907                               - (value.coeffs[0] & (align - 1)))
1908                              / align));
1909   if (N >= 2)
1910     for (unsigned int i = 1; i < N; i++)
1911       POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1912   return r;
1913 }
1914
1915 /* Assert that we can align VALUE to ALIGN at compile time.  Align VALUE
1916    up to the smallest multiple of ALIGN that is >= VALUE, then divide by
1917    ALIGN.
1918
1919    NOTE: When using this function, please add a comment above the call
1920    explaining why we know the non-constant coefficients must already
1921    be a multiple of ALIGN.  */
1922
1923 template<unsigned int N, typename Ca, typename Cb>
1924 inline poly_int<N, Ca>
1925 force_align_up_and_div (const poly_int_pod<N, Ca> &value, Cb align)
1926 {
1927   gcc_checking_assert (can_align_p (value, align));
1928
1929   poly_int<N, Ca> r;
1930   POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1931                               + (-value.coeffs[0] & (align - 1)))
1932                              / align));
1933   if (N >= 2)
1934     for (unsigned int i = 1; i < N; i++)
1935       POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1936   return r;
1937 }
1938
1939 /* Return true if we know at compile time the difference between VALUE
1940    and the equal or preceding multiple of ALIGN.  Store the value in
1941    *MISALIGN if so.  */
1942
1943 template<unsigned int N, typename Ca, typename Cb, typename Cm>
1944 inline bool
1945 known_misalignment (const poly_int_pod<N, Ca> &value, Cb align, Cm *misalign)
1946 {
1947   gcc_checking_assert (align != 0);
1948   if (!can_align_p (value, align))
1949     return false;
1950   *misalign = value.coeffs[0] & (align - 1);
1951   return true;
1952 }
1953
1954 /* Return X & (Y - 1), asserting that this value is known.  Please add
1955    an a comment above callers to this function to explain why the condition
1956    is known to hold.  */
1957
1958 template<unsigned int N, typename Ca, typename Cb>
1959 inline POLY_BINARY_COEFF (Ca, Ca)
1960 force_get_misalignment (const poly_int_pod<N, Ca> &a, Cb align)
1961 {
1962   gcc_checking_assert (can_align_p (a, align));
1963   return a.coeffs[0] & (align - 1);
1964 }
1965
1966 /* Return the maximum alignment that A is known to have.  Return 0
1967    if A is known to be zero.  */
1968
1969 template<unsigned int N, typename Ca>
1970 inline POLY_BINARY_COEFF (Ca, Ca)
1971 known_alignment (const poly_int_pod<N, Ca> &a)
1972 {
1973   typedef POLY_BINARY_COEFF (Ca, Ca) C;
1974   C r = a.coeffs[0];
1975   for (unsigned int i = 1; i < N; ++i)
1976     r |= a.coeffs[i];
1977   return r & -r;
1978 }
1979
1980 /* Return true if we can compute A | B at compile time, storing the
1981    result in RES if so.  */
1982
1983 template<unsigned int N, typename Ca, typename Cb, typename Cr>
1984 inline typename if_nonpoly<Cb, bool>::type
1985 can_ior_p (const poly_int_pod<N, Ca> &a, Cb b, Cr *result)
1986 {
1987   /* Coefficients 1 and above must be a multiple of something greater
1988      than B.  */
1989   typedef POLY_INT_TYPE (Ca) int_type;
1990   if (N >= 2)
1991     for (unsigned int i = 1; i < N; i++)
1992       if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0))
1993         return false;
1994   *result = a;
1995   result->coeffs[0] |= b;
1996   return true;
1997 }
1998
1999 /* Return true if A is a constant multiple of B, storing the
2000    multiple in *MULTIPLE if so.  */
2001
2002 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2003 inline typename if_nonpoly<Cb, bool>::type
2004 constant_multiple_p (const poly_int_pod<N, Ca> &a, Cb b, Cm *multiple)
2005 {
2006   typedef POLY_CAST (Ca, Cb) NCa;
2007   typedef POLY_CAST (Cb, Ca) NCb;
2008
2009   /* Do the modulus before the constant check, to catch divide by
2010      zero errors.  */
2011   if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
2012     return false;
2013   *multiple = NCa (a.coeffs[0]) / NCb (b);
2014   return true;
2015 }
2016
2017 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2018 inline typename if_nonpoly<Ca, bool>::type
2019 constant_multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
2020 {
2021   typedef POLY_CAST (Ca, Cb) NCa;
2022   typedef POLY_CAST (Cb, Ca) NCb;
2023   typedef POLY_INT_TYPE (Ca) int_type;
2024
2025   /* Do the modulus before the constant check, to catch divide by
2026      zero errors.  */
2027   if (NCa (a) % NCb (b.coeffs[0]) != 0
2028       || (a != int_type (0) && !b.is_constant ()))
2029     return false;
2030   *multiple = NCa (a) / NCb (b.coeffs[0]);
2031   return true;
2032 }
2033
2034 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2035 inline bool
2036 constant_multiple_p (const poly_int_pod<N, Ca> &a,
2037                      const poly_int_pod<N, Cb> &b, Cm *multiple)
2038 {
2039   typedef POLY_CAST (Ca, Cb) NCa;
2040   typedef POLY_CAST (Cb, Ca) NCb;
2041   typedef POLY_INT_TYPE (Ca) ICa;
2042   typedef POLY_INT_TYPE (Cb) ICb;
2043   typedef POLY_BINARY_COEFF (Ca, Cb) C;
2044
2045   if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
2046     return false;
2047
2048   C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2049   for (unsigned int i = 1; i < N; ++i)
2050     if (b.coeffs[i] == ICb (0)
2051         ? a.coeffs[i] != ICa (0)
2052         : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2053            || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2054       return false;
2055
2056   *multiple = r;
2057   return true;
2058 }
2059
2060 /* Return true if A is a constant multiple of B.  */
2061
2062 template<unsigned int N, typename Ca, typename Cb>
2063 inline typename if_nonpoly<Cb, bool>::type
2064 constant_multiple_p (const poly_int_pod<N, Ca> &a, Cb b)
2065 {
2066   typedef POLY_CAST (Ca, Cb) NCa;
2067   typedef POLY_CAST (Cb, Ca) NCb;
2068
2069   /* Do the modulus before the constant check, to catch divide by
2070      zero errors.  */
2071   if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
2072     return false;
2073   return true;
2074 }
2075
2076 template<unsigned int N, typename Ca, typename Cb>
2077 inline typename if_nonpoly<Ca, bool>::type
2078 constant_multiple_p (Ca a, const poly_int_pod<N, Cb> &b)
2079 {
2080   typedef POLY_CAST (Ca, Cb) NCa;
2081   typedef POLY_CAST (Cb, Ca) NCb;
2082   typedef POLY_INT_TYPE (Ca) int_type;
2083
2084   /* Do the modulus before the constant check, to catch divide by
2085      zero errors.  */
2086   if (NCa (a) % NCb (b.coeffs[0]) != 0
2087       || (a != int_type (0) && !b.is_constant ()))
2088     return false;
2089   return true;
2090 }
2091
2092 template<unsigned int N, typename Ca, typename Cb>
2093 inline bool
2094 constant_multiple_p (const poly_int_pod<N, Ca> &a,
2095                      const poly_int_pod<N, Cb> &b)
2096 {
2097   typedef POLY_CAST (Ca, Cb) NCa;
2098   typedef POLY_CAST (Cb, Ca) NCb;
2099   typedef POLY_INT_TYPE (Ca) ICa;
2100   typedef POLY_INT_TYPE (Cb) ICb;
2101   typedef POLY_BINARY_COEFF (Ca, Cb) C;
2102
2103   if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
2104     return false;
2105
2106   C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2107   for (unsigned int i = 1; i < N; ++i)
2108     if (b.coeffs[i] == ICb (0)
2109         ? a.coeffs[i] != ICa (0)
2110         : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2111            || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2112       return false;
2113   return true;
2114 }
2115
2116
2117 /* Return true if A is a multiple of B.  */
2118
2119 template<typename Ca, typename Cb>
2120 inline typename if_nonpoly2<Ca, Cb, bool>::type
2121 multiple_p (Ca a, Cb b)
2122 {
2123   return a % b == 0;
2124 }
2125
2126 /* Return true if A is a (polynomial) multiple of B.  */
2127
2128 template<unsigned int N, typename Ca, typename Cb>
2129 inline typename if_nonpoly<Cb, bool>::type
2130 multiple_p (const poly_int_pod<N, Ca> &a, Cb b)
2131 {
2132   for (unsigned int i = 0; i < N; ++i)
2133     if (a.coeffs[i] % b != 0)
2134       return false;
2135   return true;
2136 }
2137
2138 /* Return true if A is a (constant) multiple of B.  */
2139
2140 template<unsigned int N, typename Ca, typename Cb>
2141 inline typename if_nonpoly<Ca, bool>::type
2142 multiple_p (Ca a, const poly_int_pod<N, Cb> &b)
2143 {
2144   typedef POLY_INT_TYPE (Ca) int_type;
2145
2146   /* Do the modulus before the constant check, to catch divide by
2147      potential zeros.  */
2148   return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ());
2149 }
2150
2151 /* Return true if A is a (polynomial) multiple of B.  This handles cases
2152    where either B is constant or the multiple is constant.  */
2153
2154 template<unsigned int N, typename Ca, typename Cb>
2155 inline bool
2156 multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
2157 {
2158   if (b.is_constant ())
2159     return multiple_p (a, b.coeffs[0]);
2160   POLY_BINARY_COEFF (Ca, Ca) tmp;
2161   return constant_multiple_p (a, b, &tmp);
2162 }
2163
2164 /* Return true if A is a (constant) multiple of B, storing the
2165    multiple in *MULTIPLE if so.  */
2166
2167 template<typename Ca, typename Cb, typename Cm>
2168 inline typename if_nonpoly2<Ca, Cb, bool>::type
2169 multiple_p (Ca a, Cb b, Cm *multiple)
2170 {
2171   if (a % b != 0)
2172     return false;
2173   *multiple = a / b;
2174   return true;
2175 }
2176
2177 /* Return true if A is a (polynomial) multiple of B, storing the
2178    multiple in *MULTIPLE if so.  */
2179
2180 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2181 inline typename if_nonpoly<Cb, bool>::type
2182 multiple_p (const poly_int_pod<N, Ca> &a, Cb b, poly_int_pod<N, Cm> *multiple)
2183 {
2184   if (!multiple_p (a, b))
2185     return false;
2186   for (unsigned int i = 0; i < N; ++i)
2187     multiple->coeffs[i] = a.coeffs[i] / b;
2188   return true;
2189 }
2190
2191 /* Return true if B is a constant and A is a (constant) multiple of B,
2192    storing the multiple in *MULTIPLE if so.  */
2193
2194 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2195 inline typename if_nonpoly<Ca, bool>::type
2196 multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple)
2197 {
2198   typedef POLY_CAST (Ca, Cb) NCa;
2199
2200   /* Do the modulus before the constant check, to catch divide by
2201      potential zeros.  */
2202   if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ()))
2203     return false;
2204   *multiple = a / b.coeffs[0];
2205   return true;
2206 }
2207
2208 /* Return true if A is a (polynomial) multiple of B, storing the
2209    multiple in *MULTIPLE if so.  This handles cases where either
2210    B is constant or the multiple is constant.  */
2211
2212 template<unsigned int N, typename Ca, typename Cb, typename Cm>
2213 inline bool
2214 multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b,
2215             poly_int_pod<N, Cm> *multiple)
2216 {
2217   if (b.is_constant ())
2218     return multiple_p (a, b.coeffs[0], multiple);
2219   return constant_multiple_p (a, b, multiple);
2220 }
2221
2222 /* Return A / B, given that A is known to be a multiple of B.  */
2223
2224 template<unsigned int N, typename Ca, typename Cb>
2225 inline POLY_CONST_RESULT (N, Ca, Cb)
2226 exact_div (const poly_int_pod<N, Ca> &a, Cb b)
2227 {
2228   typedef POLY_CONST_COEFF (Ca, Cb) C;
2229   poly_int<N, C> r;
2230   for (unsigned int i = 0; i < N; i++)
2231     {
2232       gcc_checking_assert (a.coeffs[i] % b == 0);
2233       POLY_SET_COEFF (C, r, i, a.coeffs[i] / b);
2234     }
2235   return r;
2236 }
2237
2238 /* Return A / B, given that A is known to be a multiple of B.  */
2239
2240 template<unsigned int N, typename Ca, typename Cb>
2241 inline POLY_POLY_RESULT (N, Ca, Cb)
2242 exact_div (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b)
2243 {
2244   if (b.is_constant ())
2245     return exact_div (a, b.coeffs[0]);
2246
2247   typedef POLY_CAST (Ca, Cb) NCa;
2248   typedef POLY_CAST (Cb, Ca) NCb;
2249   typedef POLY_BINARY_COEFF (Ca, Cb) C;
2250   typedef POLY_INT_TYPE (Cb) int_type;
2251
2252   gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0);
2253   C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2254   for (unsigned int i = 1; i < N; ++i)
2255     gcc_checking_assert (b.coeffs[i] == int_type (0)
2256                          ? a.coeffs[i] == int_type (0)
2257                          : (a.coeffs[i] % b.coeffs[i] == 0
2258                             && NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r));
2259
2260   return r;
2261 }
2262
2263 /* Return true if there is some constant Q and polynomial r such that:
2264
2265      (1) a = b * Q + r
2266      (2) |b * Q| <= |a|
2267      (3) |r| < |b|
2268
2269    Store the value Q in *QUOTIENT if so.  */
2270
2271 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2272 inline typename if_nonpoly2<Cb, Cq, bool>::type
2273 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b, Cq *quotient)
2274 {
2275   typedef POLY_CAST (Ca, Cb) NCa;
2276   typedef POLY_CAST (Cb, Ca) NCb;
2277
2278   /* Do the division before the constant check, to catch divide by
2279      zero errors.  */
2280   Cq q = NCa (a.coeffs[0]) / NCb (b);
2281   if (!a.is_constant ())
2282     return false;
2283   *quotient = q;
2284   return true;
2285 }
2286
2287 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2288 inline typename if_nonpoly<Cq, bool>::type
2289 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
2290                  const poly_int_pod<N, Cb> &b,
2291                  Cq *quotient)
2292 {
2293   /* We can calculate Q from the case in which the indeterminates
2294      are zero.  */
2295   typedef POLY_CAST (Ca, Cb) NCa;
2296   typedef POLY_CAST (Cb, Ca) NCb;
2297   typedef POLY_INT_TYPE (Ca) ICa;
2298   typedef POLY_INT_TYPE (Cb) ICb;
2299   typedef POLY_BINARY_COEFF (Ca, Cb) C;
2300   C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2301
2302   /* Check the other coefficients and record whether the division is exact.
2303      The only difficult case is when it isn't.  If we require a and b to
2304      ordered wrt zero, there can be no two coefficients of the same value
2305      that have opposite signs.  This means that:
2306
2307          |a| = |a0| + |a1 * x1| + |a2 * x2| + ...
2308          |b| = |b0| + |b1 * x1| + |b2 * x2| + ...
2309
2310       The Q we've just calculated guarantees:
2311
2312          |b0 * Q| <= |a0|
2313          |a0 - b0 * Q| < |b0|
2314
2315       and so:
2316
2317          (2) |b * Q| <= |a|
2318
2319       is satisfied if:
2320
2321          |bi * xi * Q| <= |ai * xi|
2322
2323       for each i in [1, N].  This is trivially true when xi is zero.
2324       When it isn't we need:
2325
2326          (2') |bi * Q| <= |ai|
2327
2328       r is calculated as:
2329
2330          r = r0 + r1 * x1 + r2 * x2 + ...
2331          where ri = ai - bi * Q
2332
2333       Restricting to ordered a and b also guarantees that no two ris
2334       have opposite signs, so we have:
2335
2336          |r| = |r0| + |r1 * x1| + |r2 * x2| + ...
2337
2338       We know from the calculation of Q that |r0| < |b0|, so:
2339
2340          (3) |r| < |b|
2341
2342       is satisfied if:
2343
2344          (3') |ai - bi * Q| <= |bi|
2345
2346       for each i in [1, N].  */
2347   bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0;
2348   for (unsigned int i = 1; i < N; ++i)
2349     {
2350       if (b.coeffs[i] == ICb (0))
2351         {
2352           /* For bi == 0 we simply need: (3') |ai| == 0.  */
2353           if (a.coeffs[i] != ICa (0))
2354             return false;
2355         }
2356       else
2357         {
2358           if (q == 0)
2359             {
2360               /* For Q == 0 we simply need: (3') |ai| <= |bi|.  */
2361               if (a.coeffs[i] != ICa (0))
2362                 {
2363                   /* Use negative absolute to avoid overflow, i.e.
2364                      -|ai| >= -|bi|.  */
2365                   C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]);
2366                   C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]);
2367                   if (neg_abs_a < neg_abs_b)
2368                     return false;
2369                   rem_p = true;
2370                 }
2371             }
2372           else
2373             {
2374               /* Otherwise just check for the case in which ai / bi == Q.  */
2375               if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q)
2376                 return false;
2377               if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0)
2378                 rem_p = true;
2379             }
2380         }
2381     }
2382
2383   /* If the division isn't exact, require both values to be ordered wrt 0,
2384      so that we can guarantee conditions (2) and (3) for all indeterminate
2385      values.  */
2386   if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0))))
2387     return false;
2388
2389   *quotient = q;
2390   return true;
2391 }
2392
2393 /* Likewise, but also store r in *REMAINDER.  */
2394
2395 template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2396 inline typename if_nonpoly<Cq, bool>::type
2397 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
2398                  const poly_int_pod<N, Cb> &b,
2399                  Cq *quotient, Cr *remainder)
2400 {
2401   if (!can_div_trunc_p (a, b, quotient))
2402     return false;
2403   *remainder = a - *quotient * b;
2404   return true;
2405 }
2406
2407 /* Return true if there is some polynomial q and constant R such that:
2408
2409      (1) a = B * q + R
2410      (2) |B * q| <= |a|
2411      (3) |R| < |B|
2412
2413    Store the value q in *QUOTIENT if so.  */
2414
2415 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2416 inline typename if_nonpoly<Cb, bool>::type
2417 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
2418                  poly_int_pod<N, Cq> *quotient)
2419 {
2420   /* The remainder must be constant.  */
2421   for (unsigned int i = 1; i < N; ++i)
2422     if (a.coeffs[i] % b != 0)
2423       return false;
2424   for (unsigned int i = 0; i < N; ++i)
2425     quotient->coeffs[i] = a.coeffs[i] / b;
2426   return true;
2427 }
2428
2429 /* Likewise, but also store R in *REMAINDER.  */
2430
2431 template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2432 inline typename if_nonpoly<Cb, bool>::type
2433 can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b,
2434                  poly_int_pod<N, Cq> *quotient, Cr *remainder)
2435 {
2436   if (!can_div_trunc_p (a, b, quotient))
2437     return false;
2438   *remainder = a.coeffs[0] % b;
2439   return true;
2440 }
2441
2442 /* Return true if we can compute A / B at compile time, rounding towards zero.
2443    Store the result in QUOTIENT if so.
2444
2445    This handles cases in which either B is constant or the result is
2446    constant.  */
2447
2448 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2449 inline bool
2450 can_div_trunc_p (const poly_int_pod<N, Ca> &a,
2451                  const poly_int_pod<N, Cb> &b,
2452                  poly_int_pod<N, Cq> *quotient)
2453 {
2454   if (b.is_constant ())
2455     return can_div_trunc_p (a, b.coeffs[0], quotient);
2456   if (!can_div_trunc_p (a, b, &quotient->coeffs[0]))
2457     return false;
2458   for (unsigned int i = 1; i < N; ++i)
2459     quotient->coeffs[i] = 0;
2460   return true;
2461 }
2462
2463 /* Return true if there is some constant Q and polynomial r such that:
2464
2465      (1) a = b * Q + r
2466      (2) |a| <= |b * Q|
2467      (3) |r| < |b|
2468
2469    Store the value Q in *QUOTIENT if so.  */
2470
2471 template<unsigned int N, typename Ca, typename Cb, typename Cq>
2472 inline typename if_nonpoly<Cq, bool>::type
2473 can_div_away_from_zero_p (const poly_int_pod<N, Ca> &a,
2474                           const poly_int_pod<N, Cb> &b,
2475                           Cq *quotient)
2476 {
2477   if (!can_div_trunc_p (a, b, quotient))
2478     return false;
2479   if (maybe_ne (*quotient * b, a))
2480     *quotient += (*quotient < 0 ? -1 : 1);
2481   return true;
2482 }
2483
2484 /* Use print_dec to print VALUE to FILE, where SGN is the sign
2485    of the values.  */
2486
2487 template<unsigned int N, typename C>
2488 void
2489 print_dec (const poly_int_pod<N, C> &value, FILE *file, signop sgn)
2490 {
2491   if (value.is_constant ())
2492     print_dec (value.coeffs[0], file, sgn);
2493   else
2494     {
2495       fprintf (file, "[");
2496       for (unsigned int i = 0; i < N; ++i)
2497         {
2498           print_dec (value.coeffs[i], file, sgn);
2499           fputc (i == N - 1 ? ']' : ',', file);
2500         }
2501     }
2502 }
2503
2504 /* Likewise without the signop argument, for coefficients that have an
2505    inherent signedness.  */
2506
2507 template<unsigned int N, typename C>
2508 void
2509 print_dec (const poly_int_pod<N, C> &value, FILE *file)
2510 {
2511   STATIC_ASSERT (poly_coeff_traits<C>::signedness >= 0);
2512   print_dec (value, file,
2513              poly_coeff_traits<C>::signedness ? SIGNED : UNSIGNED);
2514 }
2515
2516 /* Use print_hex to print VALUE to FILE.  */
2517
2518 template<unsigned int N, typename C>
2519 void
2520 print_hex (const poly_int_pod<N, C> &value, FILE *file)
2521 {
2522   if (value.is_constant ())
2523     print_hex (value.coeffs[0], file);
2524   else
2525     {
2526       fprintf (file, "[");
2527       for (unsigned int i = 0; i < N; ++i)
2528         {
2529           print_hex (value.coeffs[i], file);
2530           fputc (i == N - 1 ? ']' : ',', file);
2531         }
2532     }
2533 }
2534
2535 /* Helper for calculating the distance between two points P1 and P2,
2536    in cases where known_le (P1, P2).  T1 and T2 are the types of the
2537    two positions, in either order.  The coefficients of P2 - P1 have
2538    type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2
2539    have C++ primitive type, otherwise P2 - P1 has its usual
2540    wide-int-based type.
2541
2542    The actual subtraction should look something like this:
2543
2544      typedef poly_span_traits<T1, T2> span_traits;
2545      span_traits::cast (P2) - span_traits::cast (P1)
2546
2547    Applying the cast before the subtraction avoids undefined overflow
2548    for signed T1 and T2.
2549
2550    The implementation of the cast tries to avoid unnecessary arithmetic
2551    or copying.  */
2552 template<typename T1, typename T2,
2553          typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2),
2554                                            unsigned HOST_WIDE_INT)>
2555 struct poly_span_traits
2556 {
2557   template<typename T>
2558   static const T &cast (const T &x) { return x; }
2559 };
2560
2561 template<typename T1, typename T2>
2562 struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT>
2563 {
2564   template<typename T>
2565   static typename if_nonpoly<T, unsigned HOST_WIDE_INT>::type
2566   cast (const T &x) { return x; }
2567
2568   template<unsigned int N, typename T>
2569   static poly_int<N, unsigned HOST_WIDE_INT>
2570   cast (const poly_int_pod<N, T> &x) { return x; }
2571 };
2572
2573 /* Return true if SIZE represents a known size, assuming that all-ones
2574    indicates an unknown size.  */
2575
2576 template<typename T>
2577 inline bool
2578 known_size_p (const T &a)
2579 {
2580   return maybe_ne (a, POLY_INT_TYPE (T) (-1));
2581 }
2582
2583 /* Return true if range [POS, POS + SIZE) might include VAL.
2584    SIZE can be the special value -1, in which case the range is
2585    open-ended.  */
2586
2587 template<typename T1, typename T2, typename T3>
2588 inline bool
2589 maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2590 {
2591   typedef poly_span_traits<T1, T2> start_span;
2592   typedef poly_span_traits<T3, T3> size_span;
2593   if (known_lt (val, pos))
2594     return false;
2595   if (!known_size_p (size))
2596     return true;
2597   if ((poly_int_traits<T1>::num_coeffs > 1
2598        || poly_int_traits<T2>::num_coeffs > 1)
2599       && maybe_lt (val, pos))
2600     /* In this case we don't know whether VAL >= POS is true at compile
2601        time, so we can't prove that VAL >= POS + SIZE.  */
2602     return true;
2603   return maybe_lt (start_span::cast (val) - start_span::cast (pos),
2604                    size_span::cast (size));
2605 }
2606
2607 /* Return true if range [POS, POS + SIZE) is known to include VAL.
2608    SIZE can be the special value -1, in which case the range is
2609    open-ended.  */
2610
2611 template<typename T1, typename T2, typename T3>
2612 inline bool
2613 known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2614 {
2615   typedef poly_span_traits<T1, T2> start_span;
2616   typedef poly_span_traits<T3, T3> size_span;
2617   return (known_size_p (size)
2618           && known_ge (val, pos)
2619           && known_lt (start_span::cast (val) - start_span::cast (pos),
2620                        size_span::cast (size)));
2621 }
2622
2623 /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2624    might overlap.  SIZE1 and/or SIZE2 can be the special value -1, in which
2625    case the range is open-ended.  */
2626
2627 template<typename T1, typename T2, typename T3, typename T4>
2628 inline bool
2629 ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1,
2630                         const T3 &pos2, const T4 &size2)
2631 {
2632   if (maybe_in_range_p (pos2, pos1, size1))
2633     return maybe_ne (size2, POLY_INT_TYPE (T4) (0));
2634   if (maybe_in_range_p (pos1, pos2, size2))
2635     return maybe_ne (size1, POLY_INT_TYPE (T2) (0));
2636   return false;
2637 }
2638
2639 /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2640    are known to overlap.  SIZE1 and/or SIZE2 can be the special value -1,
2641    in which case the range is open-ended.  */
2642
2643 template<typename T1, typename T2, typename T3, typename T4>
2644 inline bool
2645 ranges_known_overlap_p (const T1 &pos1, const T2 &size1,
2646                         const T3 &pos2, const T4 &size2)
2647 {
2648   typedef poly_span_traits<T1, T3> start_span;
2649   typedef poly_span_traits<T2, T2> size1_span;
2650   typedef poly_span_traits<T4, T4> size2_span;
2651   /* known_gt (POS1 + SIZE1, POS2)                         [infinite precision]
2652      --> known_gt (SIZE1, POS2 - POS1)                     [infinite precision]
2653      --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision]
2654                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative
2655      --> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))).
2656
2657      Using the saturating subtraction enforces that SIZE1 must be
2658      nonzero, since known_gt (0, x) is false for all nonnegative x.
2659      If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing
2660      indeterminate number I makes the unsaturated condition easier to
2661      satisfy, so using a saturated coefficient of zero tests the case in
2662      which the indeterminate is zero (the minimum value).  */
2663   return (known_size_p (size1)
2664           && known_size_p (size2)
2665           && known_lt (start_span::cast (pos2)
2666                        - start_span::cast (lower_bound (pos1, pos2)),
2667                        size1_span::cast (size1))
2668           && known_lt (start_span::cast (pos1)
2669                        - start_span::cast (lower_bound (pos1, pos2)),
2670                        size2_span::cast (size2)));
2671 }
2672
2673 /* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of
2674    [POS2, POS2 + SIZE2).  SIZE1 and/or SIZE2 can be the special value -1,
2675    in which case the range is open-ended.  */
2676
2677 template<typename T1, typename T2, typename T3, typename T4>
2678 inline bool
2679 known_subrange_p (const T1 &pos1, const T2 &size1,
2680                   const T3 &pos2, const T4 &size2)
2681 {
2682   typedef typename poly_int_traits<T2>::coeff_type C2;
2683   typedef poly_span_traits<T1, T3> start_span;
2684   typedef poly_span_traits<T2, T4> size_span;
2685   return (known_gt (size1, POLY_INT_TYPE (T2) (0))
2686           && (poly_coeff_traits<C2>::signedness > 0
2687               || known_size_p (size1))
2688           && known_size_p (size2)
2689           && known_ge (pos1, pos2)
2690           && known_le (size1, size2)
2691           && known_le (start_span::cast (pos1) - start_span::cast (pos2),
2692                        size_span::cast (size2) - size_span::cast (size1)));
2693 }
2694
2695 /* Return true if the endpoint of the range [POS, POS + SIZE) can be
2696    stored in a T, or if SIZE is the special value -1, which makes the
2697    range open-ended.  */
2698
2699 template<typename T>
2700 inline typename if_nonpoly<T, bool>::type
2701 endpoint_representable_p (const T &pos, const T &size)
2702 {
2703   return (!known_size_p (size)
2704           || pos <= poly_coeff_traits<T>::max_value - size);
2705 }
2706
2707 template<unsigned int N, typename C>
2708 inline bool
2709 endpoint_representable_p (const poly_int_pod<N, C> &pos,
2710                           const poly_int_pod<N, C> &size)
2711 {
2712   if (known_size_p (size))
2713     for (unsigned int i = 0; i < N; ++i)
2714       if (pos.coeffs[i] > poly_coeff_traits<C>::max_value - size.coeffs[i])
2715         return false;
2716   return true;
2717 }
2718
2719 template<unsigned int N, typename C>
2720 void
2721 gt_ggc_mx (poly_int_pod<N, C> *)
2722 {
2723 }
2724
2725 template<unsigned int N, typename C>
2726 void
2727 gt_pch_nx (poly_int_pod<N, C> *)
2728 {
2729 }
2730
2731 template<unsigned int N, typename C>
2732 void
2733 gt_pch_nx (poly_int_pod<N, C> *, gt_pointer_operator, void *)
2734 {
2735 }
2736
2737 #undef POLY_SET_COEFF
2738 #undef POLY_INT_TYPE
2739 #undef POLY_BINARY_COEFF
2740 #undef CONST_CONST_RESULT
2741 #undef POLY_CONST_RESULT
2742 #undef CONST_POLY_RESULT
2743 #undef POLY_POLY_RESULT
2744 #undef POLY_CONST_COEFF
2745 #undef CONST_POLY_COEFF
2746 #undef POLY_POLY_COEFF
2747
2748 #endif