1/* Polynomial integer classes. 2 Copyright (C) 2014-2020 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 32template<unsigned int N, typename T> struct poly_int_pod; 33template<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. */ 62template<typename T, wi::precision_type = wi::int_traits<T>::precision_type> 63struct poly_coeff_traits; 64 65template<typename T> 66struct 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 79template<typename T> 80struct 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 89template<typename T> 90struct 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. */ 101template<typename T1, typename T2> 102struct 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. */ 143template<typename T1, typename T2, typename T3, 144 bool lossless_p = poly_coeff_pair_traits<T1, T2>::lossless_p> 145struct if_lossless; 146template<typename T1, typename T2, typename T3> 147struct 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. */ 166template<typename T> 167struct 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}; 174template<unsigned int N, typename C> 175struct 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}; 182template<unsigned int N, typename C> 183struct 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. */ 189template<typename T1, typename T2 = T1, 190 bool is_poly = poly_int_traits<T1>::is_poly> 191struct if_nonpoly {}; 192template<typename T1, typename T2> 193struct 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. */ 200template<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> 203struct if_nonpoly2 {}; 204template<typename T1, typename T2, typename T3> 205struct 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. */ 212template<typename T1, typename T2 = T1, 213 bool is_poly = poly_int_traits<T1>::is_poly> 214struct if_poly {}; 215template<typename T1, typename T2> 216struct 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. */ 234template<typename T1, typename T2 = T1, 235 int result_kind = poly_coeff_pair_traits<T1, T2>::result_kind> 236struct poly_result; 237 238/* Promote pair to HOST_WIDE_INT. */ 239template<typename T1, typename T2> 240struct 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. */ 249template<typename T1, typename T2> 250struct 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. */ 259template<typename T1, typename T2> 260struct poly_result<T1, T2, 2> 261{ 262 typedef WI_BINARY_RESULT (T1, T2) type; 263 /* Don't cast values before operating on them; leave the wi:: routines 264 to handle promotion as necessary. */ 265 typedef const T1 &cast; 266}; 267 268/* The coefficient type for the result of a binary operation on two 269 poly_ints, the first of which has coefficients of type C1 and the 270 second of which has coefficients of type C2. */ 271#define POLY_POLY_COEFF(C1, C2) typename poly_result<C1, C2>::type 272 273/* Enforce that T2 is non-polynomial and provide the cofficient type of 274 the result of a binary operation in which the first operand is a 275 poly_int with coefficients of type C1 and the second operand is 276 a constant of type T2. */ 277#define POLY_CONST_COEFF(C1, T2) \ 278 POLY_POLY_COEFF (C1, typename if_nonpoly<T2>::type) 279 280/* Likewise in reverse. */ 281#define CONST_POLY_COEFF(T1, C2) \ 282 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, C2) 283 284/* The result type for a binary operation on poly_int<N, C1> and 285 poly_int<N, C2>. */ 286#define POLY_POLY_RESULT(N, C1, C2) poly_int<N, POLY_POLY_COEFF (C1, C2)> 287 288/* Enforce that T2 is non-polynomial and provide the result type 289 for a binary operation on poly_int<N, C1> and T2. */ 290#define POLY_CONST_RESULT(N, C1, T2) poly_int<N, POLY_CONST_COEFF (C1, T2)> 291 292/* Enforce that T1 is non-polynomial and provide the result type 293 for a binary operation on T1 and poly_int<N, C2>. */ 294#define CONST_POLY_RESULT(N, T1, C2) poly_int<N, CONST_POLY_COEFF (T1, C2)> 295 296/* Enforce that T1 and T2 are non-polynomial and provide the result type 297 for a binary operation on T1 and T2. */ 298#define CONST_CONST_RESULT(N, T1, T2) \ 299 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, \ 300 typename if_nonpoly<T2>::type) 301 302/* The type to which a coefficient of type C1 should be cast before 303 using it in a binary operation with a coefficient of type C2. */ 304#define POLY_CAST(C1, C2) typename poly_result<C1, C2>::cast 305 306/* Provide the coefficient type for the result of T1 op T2, where T1 307 and T2 can be polynomial or non-polynomial. */ 308#define POLY_BINARY_COEFF(T1, T2) \ 309 typename poly_result<typename poly_int_traits<T1>::coeff_type, \ 310 typename poly_int_traits<T2>::coeff_type>::type 311 312/* The type to which an integer constant should be cast before 313 comparing it with T. */ 314#define POLY_INT_TYPE(T) typename poly_int_traits<T>::int_type 315 316/* RES is a poly_int result that has coefficients of type C and that 317 is being built up a coefficient at a time. Set coefficient number I 318 to VALUE in the most efficient way possible. 319 320 For primitive C it is better to assign directly, since it avoids 321 any further calls and so is more efficient when the compiler is 322 built at -O0. But for wide-int based C it is better to construct 323 the value in-place. This means that calls out to a wide-int.cc 324 routine can take the address of RES rather than the address of 325 a temporary. 326 327 The dummy comparison against a null C * is just a way of checking 328 that C gives the right type. */ 329#define POLY_SET_COEFF(C, RES, I, VALUE) \ 330 ((void) (&(RES).coeffs[0] == (C *) 0), \ 331 wi::int_traits<C>::precision_type == wi::FLEXIBLE_PRECISION \ 332 ? (void) ((RES).coeffs[I] = VALUE) \ 333 : (void) ((RES).coeffs[I].~C (), new (&(RES).coeffs[I]) C (VALUE))) 334 335/* A base POD class for polynomial integers. The polynomial has N 336 coefficients of type C. */ 337template<unsigned int N, typename C> 338struct poly_int_pod 339{ 340public: 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 386template<unsigned int N, typename C> 387template<typename Ca> 388inline poly_int_pod<N, C>& 389poly_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 396template<unsigned int N, typename C> 397template<typename Ca> 398inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type & 399poly_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 408template<unsigned int N, typename C> 409template<typename Ca> 410inline poly_int_pod<N, C>& 411poly_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 418template<unsigned int N, typename C> 419template<typename Ca> 420inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type & 421poly_int_pod<N, C>::operator += (const Ca &a) 422{ 423 this->coeffs[0] += a; 424 return *this; 425} 426 427template<unsigned int N, typename C> 428template<typename Ca> 429inline poly_int_pod<N, C>& 430poly_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 437template<unsigned int N, typename C> 438template<typename Ca> 439inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type & 440poly_int_pod<N, C>::operator -= (const Ca &a) 441{ 442 this->coeffs[0] -= a; 443 return *this; 444} 445 446template<unsigned int N, typename C> 447template<typename Ca> 448inline typename if_nonpoly<Ca, poly_int_pod<N, C> >::type & 449poly_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 456template<unsigned int N, typename C> 457inline poly_int_pod<N, C>& 458poly_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 467template<unsigned int N, typename C> 468inline bool 469poly_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 481template<unsigned int N, typename C> 482template<typename T> 483inline typename if_lossless<T, C, bool>::type 484poly_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 500template<unsigned int N, typename C> 501inline C 502poly_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 512template<unsigned int N, typename C> 513template<typename Ca> 514inline poly_int<N, C> 515poly_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 527template<unsigned int N, typename C> 528template<typename Ca> 529inline poly_int<N, C> 530poly_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 542template<unsigned int N, typename C> 543inline bool 544poly_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 559template<unsigned int N, typename C> 560inline bool 561poly_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 574template<unsigned int N, typename C> 575inline poly_int<N, HOST_WIDE_INT> 576poly_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 587template<unsigned int N, typename C> 588inline poly_int<N, unsigned HOST_WIDE_INT> 589poly_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 600template<unsigned int N, typename C> 601inline 602poly_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. */ 611template<unsigned int N, typename C> 612class poly_int : public poly_int_pod<N, C> 613{ 614public: 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 647template<unsigned int N, typename C> 648template<typename Ca> 649inline 650poly_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 656template<unsigned int N, typename C> 657template<typename Ca> 658inline 659poly_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 665template<unsigned int N, typename C> 666template<typename C0> 667inline 668poly_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 675template<unsigned int N, typename C> 676template<typename C0, typename C1> 677inline 678poly_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 687template<unsigned int N, typename C> 688template<typename Ca> 689inline poly_int<N, C>& 690poly_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 697template<unsigned int N, typename C> 698template<typename Ca> 699inline typename if_nonpoly<Ca, poly_int<N, C> >::type & 700poly_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 709template<unsigned int N, typename C> 710template<typename Ca> 711inline poly_int<N, C>& 712poly_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 719template<unsigned int N, typename C> 720template<typename Ca> 721inline typename if_nonpoly<Ca, poly_int<N, C> >::type & 722poly_int<N, C>::operator += (const Ca &a) 723{ 724 this->coeffs[0] += a; 725 return *this; 726} 727 728template<unsigned int N, typename C> 729template<typename Ca> 730inline poly_int<N, C>& 731poly_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 738template<unsigned int N, typename C> 739template<typename Ca> 740inline typename if_nonpoly<Ca, poly_int<N, C> >::type & 741poly_int<N, C>::operator -= (const Ca &a) 742{ 743 this->coeffs[0] -= a; 744 return *this; 745} 746 747template<unsigned int N, typename C> 748template<typename Ca> 749inline typename if_nonpoly<Ca, poly_int<N, C> >::type & 750poly_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 757template<unsigned int N, typename C> 758inline poly_int<N, C>& 759poly_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 768template<typename Ca, typename Cb, typename Cc> 769inline typename if_nonpoly<Ca, bool>::type 770coeffs_in_range_p (const Ca &a, const Cb &b, const Cc &c) 771{ 772 return a >= b && a <= c; 773} 774 775template<unsigned int N, typename Ca, typename Cb, typename Cc> 776inline typename if_nonpoly<Ca, bool>::type 777coeffs_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 785namespace wi { 786/* Poly version of wi::shwi, with the same interface. */ 787 788template<unsigned int N> 789inline poly_int<N, hwi_with_prec> 790shwi (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 800template<unsigned int N> 801inline poly_int<N, hwi_with_prec> 802uhwi (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 812template<unsigned int N, typename Ca> 813inline POLY_POLY_RESULT (N, Ca, Ca) 814sext (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 825template<unsigned int N, typename Ca> 826inline POLY_POLY_RESULT (N, Ca, Ca) 827zext (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 837template<unsigned int N, typename Ca, typename Cb> 838inline POLY_POLY_RESULT (N, Ca, Cb) 839operator + (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 849template<unsigned int N, typename Ca, typename Cb> 850inline POLY_CONST_RESULT (N, Ca, Cb) 851operator + (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 863template<unsigned int N, typename Ca, typename Cb> 864inline CONST_POLY_RESULT (N, Ca, Cb) 865operator + (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 877namespace wi { 878/* Poly versions of wi::add, with the same interface. */ 879 880template<unsigned int N, typename Ca, typename Cb> 881inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 882add (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 891template<unsigned int N, typename Ca, typename Cb> 892inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 893add (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 904template<unsigned int N, typename Ca, typename Cb> 905inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 906add (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 917template<unsigned int N, typename Ca, typename Cb> 918inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 919add (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 936template<unsigned int N, typename Ca, typename Cb> 937inline POLY_POLY_RESULT (N, Ca, Cb) 938operator - (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 948template<unsigned int N, typename Ca, typename Cb> 949inline POLY_CONST_RESULT (N, Ca, Cb) 950operator - (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 962template<unsigned int N, typename Ca, typename Cb> 963inline CONST_POLY_RESULT (N, Ca, Cb) 964operator - (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 976namespace wi { 977/* Poly versions of wi::sub, with the same interface. */ 978 979template<unsigned int N, typename Ca, typename Cb> 980inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 981sub (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 990template<unsigned int N, typename Ca, typename Cb> 991inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 992sub (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 1003template<unsigned int N, typename Ca, typename Cb> 1004inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 1005sub (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 1016template<unsigned int N, typename Ca, typename Cb> 1017inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 1018sub (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 1035template<unsigned int N, typename Ca> 1036inline POLY_POLY_RESULT (N, Ca, Ca) 1037operator - (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 1047namespace wi { 1048/* Poly version of wi::neg, with the same interface. */ 1049 1050template<unsigned int N, typename Ca> 1051inline poly_int<N, WI_UNARY_RESULT (Ca)> 1052neg (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 1061template<unsigned int N, typename Ca> 1062inline poly_int<N, WI_UNARY_RESULT (Ca)> 1063neg (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 1078template<unsigned int N, typename Ca> 1079inline POLY_POLY_RESULT (N, Ca, Ca) 1080operator ~ (const poly_int_pod<N, Ca> &a) 1081{ 1082 if (N >= 2) 1083 return -1 - a; 1084 return ~a.coeffs[0]; 1085} 1086 1087template<unsigned int N, typename Ca, typename Cb> 1088inline POLY_CONST_RESULT (N, Ca, Cb) 1089operator * (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 1099template<unsigned int N, typename Ca, typename Cb> 1100inline CONST_POLY_RESULT (N, Ca, Cb) 1101operator * (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 1111namespace wi { 1112/* Poly versions of wi::mul, with the same interface. */ 1113 1114template<unsigned int N, typename Ca, typename Cb> 1115inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 1116mul (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 1125template<unsigned int N, typename Ca, typename Cb> 1126inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 1127mul (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 1136template<unsigned int N, typename Ca, typename Cb> 1137inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)> 1138mul (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 1154template<unsigned int N, typename Ca, typename Cb> 1155inline POLY_POLY_RESULT (N, Ca, Ca) 1156operator << (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 1166namespace wi { 1167/* Poly version of wi::lshift, with the same interface. */ 1168 1169template<unsigned int N, typename Ca, typename Cb> 1170inline poly_int<N, WI_BINARY_RESULT (Ca, Ca)> 1171lshift (const poly_int_pod<N, Ca> &a, const Cb &b) 1172{ 1173 typedef WI_BINARY_RESULT (Ca, Ca) C; 1174 poly_int<N, C> r; 1175 for (unsigned int i = 0; i < N; i++) 1176 POLY_SET_COEFF (C, r, i, wi::lshift (a.coeffs[i], b)); 1177 return r; 1178} 1179} 1180 1181/* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative 1182 integer x. */ 1183 1184template<typename Ca, typename Cb> 1185inline bool 1186maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1) 1187{ 1188 if (a1 != b1) 1189 /* a0 + a1 * x == b0 + b1 * x 1190 ==> (a1 - b1) * x == b0 - a0 1191 ==> x == (b0 - a0) / (a1 - b1) 1192 1193 We need to test whether that's a valid value of x. 1194 (b0 - a0) and (a1 - b1) must not have opposite signs 1195 and the result must be integral. */ 1196 return (a1 < b1 1197 ? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0 1198 : b0 >= a0 && (b0 - a0) % (a1 - b1) == 0); 1199 return a0 == b0; 1200} 1201 1202/* Return true if a0 + a1 * x might equal b for some nonnegative 1203 integer x. */ 1204 1205template<typename Ca, typename Cb> 1206inline bool 1207maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b) 1208{ 1209 if (a1 != 0) 1210 /* a0 + a1 * x == b 1211 ==> x == (b - a0) / a1 1212 1213 We need to test whether that's a valid value of x. 1214 (b - a0) and a1 must not have opposite signs and the 1215 result must be integral. */ 1216 return (a1 < 0 1217 ? b <= a0 && (a0 - b) % a1 == 0 1218 : b >= a0 && (b - a0) % a1 == 0); 1219 return a0 == b; 1220} 1221 1222/* Return true if A might equal B for some indeterminate values. */ 1223 1224template<unsigned int N, typename Ca, typename Cb> 1225inline bool 1226maybe_eq (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1227{ 1228 STATIC_ASSERT (N <= 2); 1229 if (N == 2) 1230 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]); 1231 return a.coeffs[0] == b.coeffs[0]; 1232} 1233 1234template<unsigned int N, typename Ca, typename Cb> 1235inline typename if_nonpoly<Cb, bool>::type 1236maybe_eq (const poly_int_pod<N, Ca> &a, const Cb &b) 1237{ 1238 STATIC_ASSERT (N <= 2); 1239 if (N == 2) 1240 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b); 1241 return a.coeffs[0] == b; 1242} 1243 1244template<unsigned int N, typename Ca, typename Cb> 1245inline typename if_nonpoly<Ca, bool>::type 1246maybe_eq (const Ca &a, const poly_int_pod<N, Cb> &b) 1247{ 1248 STATIC_ASSERT (N <= 2); 1249 if (N == 2) 1250 return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a); 1251 return a == b.coeffs[0]; 1252} 1253 1254template<typename Ca, typename Cb> 1255inline typename if_nonpoly2<Ca, Cb, bool>::type 1256maybe_eq (const Ca &a, const Cb &b) 1257{ 1258 return a == b; 1259} 1260 1261/* Return true if A might not equal B for some indeterminate values. */ 1262 1263template<unsigned int N, typename Ca, typename Cb> 1264inline bool 1265maybe_ne (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1266{ 1267 if (N >= 2) 1268 for (unsigned int i = 1; i < N; i++) 1269 if (a.coeffs[i] != b.coeffs[i]) 1270 return true; 1271 return a.coeffs[0] != b.coeffs[0]; 1272} 1273 1274template<unsigned int N, typename Ca, typename Cb> 1275inline typename if_nonpoly<Cb, bool>::type 1276maybe_ne (const poly_int_pod<N, Ca> &a, const Cb &b) 1277{ 1278 if (N >= 2) 1279 for (unsigned int i = 1; i < N; i++) 1280 if (a.coeffs[i] != 0) 1281 return true; 1282 return a.coeffs[0] != b; 1283} 1284 1285template<unsigned int N, typename Ca, typename Cb> 1286inline typename if_nonpoly<Ca, bool>::type 1287maybe_ne (const Ca &a, const poly_int_pod<N, Cb> &b) 1288{ 1289 if (N >= 2) 1290 for (unsigned int i = 1; i < N; i++) 1291 if (b.coeffs[i] != 0) 1292 return true; 1293 return a != b.coeffs[0]; 1294} 1295 1296template<typename Ca, typename Cb> 1297inline typename if_nonpoly2<Ca, Cb, bool>::type 1298maybe_ne (const Ca &a, const Cb &b) 1299{ 1300 return a != b; 1301} 1302 1303/* Return true if A is known to be equal to B. */ 1304#define known_eq(A, B) (!maybe_ne (A, B)) 1305 1306/* Return true if A is known to be unequal to B. */ 1307#define known_ne(A, B) (!maybe_eq (A, B)) 1308 1309/* Return true if A might be less than or equal to B for some 1310 indeterminate values. */ 1311 1312template<unsigned int N, typename Ca, typename Cb> 1313inline bool 1314maybe_le (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1315{ 1316 if (N >= 2) 1317 for (unsigned int i = 1; i < N; i++) 1318 if (a.coeffs[i] < b.coeffs[i]) 1319 return true; 1320 return a.coeffs[0] <= b.coeffs[0]; 1321} 1322 1323template<unsigned int N, typename Ca, typename Cb> 1324inline typename if_nonpoly<Cb, bool>::type 1325maybe_le (const poly_int_pod<N, Ca> &a, const Cb &b) 1326{ 1327 if (N >= 2) 1328 for (unsigned int i = 1; i < N; i++) 1329 if (a.coeffs[i] < 0) 1330 return true; 1331 return a.coeffs[0] <= b; 1332} 1333 1334template<unsigned int N, typename Ca, typename Cb> 1335inline typename if_nonpoly<Ca, bool>::type 1336maybe_le (const Ca &a, const poly_int_pod<N, Cb> &b) 1337{ 1338 if (N >= 2) 1339 for (unsigned int i = 1; i < N; i++) 1340 if (b.coeffs[i] > 0) 1341 return true; 1342 return a <= b.coeffs[0]; 1343} 1344 1345template<typename Ca, typename Cb> 1346inline typename if_nonpoly2<Ca, Cb, bool>::type 1347maybe_le (const Ca &a, const Cb &b) 1348{ 1349 return a <= b; 1350} 1351 1352/* Return true if A might be less than B for some indeterminate values. */ 1353 1354template<unsigned int N, typename Ca, typename Cb> 1355inline bool 1356maybe_lt (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1357{ 1358 if (N >= 2) 1359 for (unsigned int i = 1; i < N; i++) 1360 if (a.coeffs[i] < b.coeffs[i]) 1361 return true; 1362 return a.coeffs[0] < b.coeffs[0]; 1363} 1364 1365template<unsigned int N, typename Ca, typename Cb> 1366inline typename if_nonpoly<Cb, bool>::type 1367maybe_lt (const poly_int_pod<N, Ca> &a, const Cb &b) 1368{ 1369 if (N >= 2) 1370 for (unsigned int i = 1; i < N; i++) 1371 if (a.coeffs[i] < 0) 1372 return true; 1373 return a.coeffs[0] < b; 1374} 1375 1376template<unsigned int N, typename Ca, typename Cb> 1377inline typename if_nonpoly<Ca, bool>::type 1378maybe_lt (const Ca &a, const poly_int_pod<N, Cb> &b) 1379{ 1380 if (N >= 2) 1381 for (unsigned int i = 1; i < N; i++) 1382 if (b.coeffs[i] > 0) 1383 return true; 1384 return a < b.coeffs[0]; 1385} 1386 1387template<typename Ca, typename Cb> 1388inline typename if_nonpoly2<Ca, Cb, bool>::type 1389maybe_lt (const Ca &a, const Cb &b) 1390{ 1391 return a < b; 1392} 1393 1394/* Return true if A may be greater than or equal to B. */ 1395#define maybe_ge(A, B) maybe_le (B, A) 1396 1397/* Return true if A may be greater than B. */ 1398#define maybe_gt(A, B) maybe_lt (B, A) 1399 1400/* Return true if A is known to be less than or equal to B. */ 1401#define known_le(A, B) (!maybe_gt (A, B)) 1402 1403/* Return true if A is known to be less than B. */ 1404#define known_lt(A, B) (!maybe_ge (A, B)) 1405 1406/* Return true if A is known to be greater than B. */ 1407#define known_gt(A, B) (!maybe_le (A, B)) 1408 1409/* Return true if A is known to be greater than or equal to B. */ 1410#define known_ge(A, B) (!maybe_lt (A, B)) 1411 1412/* Return true if A and B are ordered by the partial ordering known_le. */ 1413 1414template<typename T1, typename T2> 1415inline bool 1416ordered_p (const T1 &a, const T2 &b) 1417{ 1418 return ((poly_int_traits<T1>::num_coeffs == 1 1419 && poly_int_traits<T2>::num_coeffs == 1) 1420 || known_le (a, b) 1421 || known_le (b, a)); 1422} 1423 1424/* Assert that A and B are known to be ordered and return the minimum 1425 of the two. 1426 1427 NOTE: When using this function, please add a comment above the call 1428 explaining why we know the values are ordered in that context. */ 1429 1430template<unsigned int N, typename Ca, typename Cb> 1431inline POLY_POLY_RESULT (N, Ca, Cb) 1432ordered_min (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1433{ 1434 if (known_le (a, b)) 1435 return a; 1436 else 1437 { 1438 if (N > 1) 1439 gcc_checking_assert (known_le (b, a)); 1440 return b; 1441 } 1442} 1443 1444template<unsigned int N, typename Ca, typename Cb> 1445inline CONST_POLY_RESULT (N, Ca, Cb) 1446ordered_min (const Ca &a, const poly_int_pod<N, Cb> &b) 1447{ 1448 if (known_le (a, b)) 1449 return a; 1450 else 1451 { 1452 if (N > 1) 1453 gcc_checking_assert (known_le (b, a)); 1454 return b; 1455 } 1456} 1457 1458template<unsigned int N, typename Ca, typename Cb> 1459inline POLY_CONST_RESULT (N, Ca, Cb) 1460ordered_min (const poly_int_pod<N, Ca> &a, const Cb &b) 1461{ 1462 if (known_le (a, b)) 1463 return a; 1464 else 1465 { 1466 if (N > 1) 1467 gcc_checking_assert (known_le (b, a)); 1468 return b; 1469 } 1470} 1471 1472/* Assert that A and B are known to be ordered and return the maximum 1473 of the two. 1474 1475 NOTE: When using this function, please add a comment above the call 1476 explaining why we know the values are ordered in that context. */ 1477 1478template<unsigned int N, typename Ca, typename Cb> 1479inline POLY_POLY_RESULT (N, Ca, Cb) 1480ordered_max (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1481{ 1482 if (known_le (a, b)) 1483 return b; 1484 else 1485 { 1486 if (N > 1) 1487 gcc_checking_assert (known_le (b, a)); 1488 return a; 1489 } 1490} 1491 1492template<unsigned int N, typename Ca, typename Cb> 1493inline CONST_POLY_RESULT (N, Ca, Cb) 1494ordered_max (const Ca &a, const poly_int_pod<N, Cb> &b) 1495{ 1496 if (known_le (a, b)) 1497 return b; 1498 else 1499 { 1500 if (N > 1) 1501 gcc_checking_assert (known_le (b, a)); 1502 return a; 1503 } 1504} 1505 1506template<unsigned int N, typename Ca, typename Cb> 1507inline POLY_CONST_RESULT (N, Ca, Cb) 1508ordered_max (const poly_int_pod<N, Ca> &a, const Cb &b) 1509{ 1510 if (known_le (a, b)) 1511 return b; 1512 else 1513 { 1514 if (N > 1) 1515 gcc_checking_assert (known_le (b, a)); 1516 return a; 1517 } 1518} 1519 1520/* Return a constant lower bound on the value of A, which is known 1521 to be nonnegative. */ 1522 1523template<unsigned int N, typename Ca> 1524inline Ca 1525constant_lower_bound (const poly_int_pod<N, Ca> &a) 1526{ 1527 gcc_checking_assert (known_ge (a, POLY_INT_TYPE (Ca) (0))); 1528 return a.coeffs[0]; 1529} 1530 1531/* Return the constant lower bound of A, given that it is no less than B. */ 1532 1533template<unsigned int N, typename Ca, typename Cb> 1534inline POLY_CONST_COEFF (Ca, Cb) 1535constant_lower_bound_with_limit (const poly_int_pod<N, Ca> &a, const Cb &b) 1536{ 1537 if (known_ge (a, b)) 1538 return a.coeffs[0]; 1539 return b; 1540} 1541 1542/* Return the constant upper bound of A, given that it is no greater 1543 than B. */ 1544 1545template<unsigned int N, typename Ca, typename Cb> 1546inline POLY_CONST_COEFF (Ca, Cb) 1547constant_upper_bound_with_limit (const poly_int_pod<N, Ca> &a, const Cb &b) 1548{ 1549 if (known_le (a, b)) 1550 return a.coeffs[0]; 1551 return b; 1552} 1553 1554/* Return a value that is known to be no greater than A and B. This 1555 will be the greatest lower bound for some indeterminate values but 1556 not necessarily for all. */ 1557 1558template<unsigned int N, typename Ca, typename Cb> 1559inline POLY_CONST_RESULT (N, Ca, Cb) 1560lower_bound (const poly_int_pod<N, Ca> &a, const Cb &b) 1561{ 1562 typedef POLY_CAST (Ca, Cb) NCa; 1563 typedef POLY_CAST (Cb, Ca) NCb; 1564 typedef POLY_INT_TYPE (Cb) ICb; 1565 typedef POLY_CONST_COEFF (Ca, Cb) C; 1566 1567 poly_int<N, C> r; 1568 POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b))); 1569 if (N >= 2) 1570 for (unsigned int i = 1; i < N; i++) 1571 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0))); 1572 return r; 1573} 1574 1575template<unsigned int N, typename Ca, typename Cb> 1576inline CONST_POLY_RESULT (N, Ca, Cb) 1577lower_bound (const Ca &a, const poly_int_pod<N, Cb> &b) 1578{ 1579 return lower_bound (b, a); 1580} 1581 1582template<unsigned int N, typename Ca, typename Cb> 1583inline POLY_POLY_RESULT (N, Ca, Cb) 1584lower_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1585{ 1586 typedef POLY_CAST (Ca, Cb) NCa; 1587 typedef POLY_CAST (Cb, Ca) NCb; 1588 typedef POLY_POLY_COEFF (Ca, Cb) C; 1589 1590 poly_int<N, C> r; 1591 for (unsigned int i = 0; i < N; i++) 1592 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i]))); 1593 return r; 1594} 1595 1596template<typename Ca, typename Cb> 1597inline CONST_CONST_RESULT (N, Ca, Cb) 1598lower_bound (const Ca &a, const Cb &b) 1599{ 1600 return a < b ? a : b; 1601} 1602 1603/* Return a value that is known to be no less than A and B. This will 1604 be the least upper bound for some indeterminate values but not 1605 necessarily for all. */ 1606 1607template<unsigned int N, typename Ca, typename Cb> 1608inline POLY_CONST_RESULT (N, Ca, Cb) 1609upper_bound (const poly_int_pod<N, Ca> &a, const Cb &b) 1610{ 1611 typedef POLY_CAST (Ca, Cb) NCa; 1612 typedef POLY_CAST (Cb, Ca) NCb; 1613 typedef POLY_INT_TYPE (Cb) ICb; 1614 typedef POLY_CONST_COEFF (Ca, Cb) C; 1615 1616 poly_int<N, C> r; 1617 POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b))); 1618 if (N >= 2) 1619 for (unsigned int i = 1; i < N; i++) 1620 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0))); 1621 return r; 1622} 1623 1624template<unsigned int N, typename Ca, typename Cb> 1625inline CONST_POLY_RESULT (N, Ca, Cb) 1626upper_bound (const Ca &a, const poly_int_pod<N, Cb> &b) 1627{ 1628 return upper_bound (b, a); 1629} 1630 1631template<unsigned int N, typename Ca, typename Cb> 1632inline POLY_POLY_RESULT (N, Ca, Cb) 1633upper_bound (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 1634{ 1635 typedef POLY_CAST (Ca, Cb) NCa; 1636 typedef POLY_CAST (Cb, Ca) NCb; 1637 typedef POLY_POLY_COEFF (Ca, Cb) C; 1638 1639 poly_int<N, C> r; 1640 for (unsigned int i = 0; i < N; i++) 1641 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i]))); 1642 return r; 1643} 1644 1645/* Return the greatest common divisor of all nonzero coefficients, or zero 1646 if all coefficients are zero. */ 1647 1648template<unsigned int N, typename Ca> 1649inline POLY_BINARY_COEFF (Ca, Ca) 1650coeff_gcd (const poly_int_pod<N, Ca> &a) 1651{ 1652 /* Find the first nonzero coefficient, stopping at 0 whatever happens. */ 1653 unsigned int i; 1654 for (i = N - 1; i > 0; --i) 1655 if (a.coeffs[i] != 0) 1656 break; 1657 typedef POLY_BINARY_COEFF (Ca, Ca) C; 1658 C r = a.coeffs[i]; 1659 for (unsigned int j = 0; j < i; ++j) 1660 if (a.coeffs[j] != 0) 1661 r = gcd (r, C (a.coeffs[j])); 1662 return r; 1663} 1664 1665/* Return a value that is a multiple of both A and B. This will be the 1666 least common multiple for some indeterminate values but necessarily 1667 for all. */ 1668 1669template<unsigned int N, typename Ca, typename Cb> 1670POLY_CONST_RESULT (N, Ca, Cb) 1671common_multiple (const poly_int_pod<N, Ca> &a, Cb b) 1672{ 1673 POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a); 1674 return a * (least_common_multiple (xgcd, b) / xgcd); 1675} 1676 1677template<unsigned int N, typename Ca, typename Cb> 1678inline CONST_POLY_RESULT (N, Ca, Cb) 1679common_multiple (const Ca &a, const poly_int_pod<N, Cb> &b) 1680{ 1681 return common_multiple (b, a); 1682} 1683 1684/* Return a value that is a multiple of both A and B, asserting that 1685 such a value exists. The result will be the least common multiple 1686 for some indeterminate values but necessarily for all. 1687 1688 NOTE: When using this function, please add a comment above the call 1689 explaining why we know the values have a common multiple (which might 1690 for example be because we know A / B is rational). */ 1691 1692template<unsigned int N, typename Ca, typename Cb> 1693POLY_POLY_RESULT (N, Ca, Cb) 1694force_common_multiple (const poly_int_pod<N, Ca> &a, 1695 const poly_int_pod<N, Cb> &b) 1696{ 1697 if (b.is_constant ()) 1698 return common_multiple (a, b.coeffs[0]); 1699 if (a.is_constant ()) 1700 return common_multiple (a.coeffs[0], b); 1701 1702 typedef POLY_CAST (Ca, Cb) NCa; 1703 typedef POLY_CAST (Cb, Ca) NCb; 1704 typedef POLY_BINARY_COEFF (Ca, Cb) C; 1705 typedef POLY_INT_TYPE (Ca) ICa; 1706 1707 for (unsigned int i = 1; i < N; ++i) 1708 if (a.coeffs[i] != ICa (0)) 1709 { 1710 C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i])); 1711 C amul = lcm / a.coeffs[i]; 1712 C bmul = lcm / b.coeffs[i]; 1713 for (unsigned int j = 0; j < N; ++j) 1714 gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul); 1715 return a * amul; 1716 } 1717 gcc_unreachable (); 1718} 1719 1720/* Compare A and B for sorting purposes, returning -1 if A should come 1721 before B, 0 if A and B are identical, and 1 if A should come after B. 1722 This is a lexicographical compare of the coefficients in reverse order. 1723 1724 A consequence of this is that all constant sizes come before all 1725 non-constant ones, regardless of magnitude (since a size is never 1726 negative). This is what most callers want. For example, when laying 1727 data out on the stack, it's better to keep all the constant-sized 1728 data together so that it can be accessed as a constant offset from a 1729 single base. */ 1730 1731template<unsigned int N, typename Ca, typename Cb> 1732inline int 1733compare_sizes_for_sort (const poly_int_pod<N, Ca> &a, 1734 const poly_int_pod<N, Cb> &b) 1735{ 1736 for (unsigned int i = N; i-- > 0; ) 1737 if (a.coeffs[i] != b.coeffs[i]) 1738 return a.coeffs[i] < b.coeffs[i] ? -1 : 1; 1739 return 0; 1740} 1741 1742/* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */ 1743 1744template<unsigned int N, typename Ca, typename Cb> 1745inline bool 1746can_align_p (const poly_int_pod<N, Ca> &value, Cb align) 1747{ 1748 for (unsigned int i = 1; i < N; i++) 1749 if ((value.coeffs[i] & (align - 1)) != 0) 1750 return false; 1751 return true; 1752} 1753 1754/* Return true if we can align VALUE up to the smallest multiple of 1755 ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */ 1756 1757template<unsigned int N, typename Ca, typename Cb> 1758inline bool 1759can_align_up (const poly_int_pod<N, Ca> &value, Cb align, 1760 poly_int_pod<N, Ca> *aligned) 1761{ 1762 if (!can_align_p (value, align)) 1763 return false; 1764 *aligned = value + (-value.coeffs[0] & (align - 1)); 1765 return true; 1766} 1767 1768/* Return true if we can align VALUE down to the largest multiple of 1769 ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */ 1770 1771template<unsigned int N, typename Ca, typename Cb> 1772inline bool 1773can_align_down (const poly_int_pod<N, Ca> &value, Cb align, 1774 poly_int_pod<N, Ca> *aligned) 1775{ 1776 if (!can_align_p (value, align)) 1777 return false; 1778 *aligned = value - (value.coeffs[0] & (align - 1)); 1779 return true; 1780} 1781 1782/* Return true if we can align A and B up to the smallest multiples of 1783 ALIGN that are >= A and B respectively, and if doing so gives the 1784 same value. */ 1785 1786template<unsigned int N, typename Ca, typename Cb, typename Cc> 1787inline bool 1788known_equal_after_align_up (const poly_int_pod<N, Ca> &a, 1789 const poly_int_pod<N, Cb> &b, 1790 Cc align) 1791{ 1792 poly_int<N, Ca> aligned_a; 1793 poly_int<N, Cb> aligned_b; 1794 return (can_align_up (a, align, &aligned_a) 1795 && can_align_up (b, align, &aligned_b) 1796 && known_eq (aligned_a, aligned_b)); 1797} 1798 1799/* Return true if we can align A and B down to the largest multiples of 1800 ALIGN that are <= A and B respectively, and if doing so gives the 1801 same value. */ 1802 1803template<unsigned int N, typename Ca, typename Cb, typename Cc> 1804inline bool 1805known_equal_after_align_down (const poly_int_pod<N, Ca> &a, 1806 const poly_int_pod<N, Cb> &b, 1807 Cc align) 1808{ 1809 poly_int<N, Ca> aligned_a; 1810 poly_int<N, Cb> aligned_b; 1811 return (can_align_down (a, align, &aligned_a) 1812 && can_align_down (b, align, &aligned_b) 1813 && known_eq (aligned_a, aligned_b)); 1814} 1815 1816/* Assert that we can align VALUE to ALIGN at compile time and return 1817 the smallest multiple of ALIGN that is >= VALUE. 1818 1819 NOTE: When using this function, please add a comment above the call 1820 explaining why we know the non-constant coefficients must already 1821 be a multiple of ALIGN. */ 1822 1823template<unsigned int N, typename Ca, typename Cb> 1824inline poly_int<N, Ca> 1825force_align_up (const poly_int_pod<N, Ca> &value, Cb align) 1826{ 1827 gcc_checking_assert (can_align_p (value, align)); 1828 return value + (-value.coeffs[0] & (align - 1)); 1829} 1830 1831/* Assert that we can align VALUE to ALIGN at compile time and return 1832 the largest multiple of ALIGN that is <= VALUE. 1833 1834 NOTE: When using this function, please add a comment above the call 1835 explaining why we know the non-constant coefficients must already 1836 be a multiple of ALIGN. */ 1837 1838template<unsigned int N, typename Ca, typename Cb> 1839inline poly_int<N, Ca> 1840force_align_down (const poly_int_pod<N, Ca> &value, Cb align) 1841{ 1842 gcc_checking_assert (can_align_p (value, align)); 1843 return value - (value.coeffs[0] & (align - 1)); 1844} 1845 1846/* Return a value <= VALUE that is a multiple of ALIGN. It will be the 1847 greatest such value for some indeterminate values but not necessarily 1848 for all. */ 1849 1850template<unsigned int N, typename Ca, typename Cb> 1851inline poly_int<N, Ca> 1852aligned_lower_bound (const poly_int_pod<N, Ca> &value, Cb align) 1853{ 1854 poly_int<N, Ca> r; 1855 for (unsigned int i = 0; i < N; i++) 1856 /* This form copes correctly with more type combinations than 1857 value.coeffs[i] & -align would. */ 1858 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i] 1859 - (value.coeffs[i] & (align - 1)))); 1860 return r; 1861} 1862 1863/* Return a value >= VALUE that is a multiple of ALIGN. It will be the 1864 least such value for some indeterminate values but not necessarily 1865 for all. */ 1866 1867template<unsigned int N, typename Ca, typename Cb> 1868inline poly_int<N, Ca> 1869aligned_upper_bound (const poly_int_pod<N, Ca> &value, Cb align) 1870{ 1871 poly_int<N, Ca> r; 1872 for (unsigned int i = 0; i < N; i++) 1873 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i] 1874 + (-value.coeffs[i] & (align - 1)))); 1875 return r; 1876} 1877 1878/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE 1879 down to the largest multiple of ALIGN that is <= VALUE, then divide by 1880 ALIGN. 1881 1882 NOTE: When using this function, please add a comment above the call 1883 explaining why we know the non-constant coefficients must already 1884 be a multiple of ALIGN. */ 1885 1886template<unsigned int N, typename Ca, typename Cb> 1887inline poly_int<N, Ca> 1888force_align_down_and_div (const poly_int_pod<N, Ca> &value, Cb align) 1889{ 1890 gcc_checking_assert (can_align_p (value, align)); 1891 1892 poly_int<N, Ca> r; 1893 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0] 1894 - (value.coeffs[0] & (align - 1))) 1895 / align)); 1896 if (N >= 2) 1897 for (unsigned int i = 1; i < N; i++) 1898 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align); 1899 return r; 1900} 1901 1902/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE 1903 up to the smallest multiple of ALIGN that is >= VALUE, then divide by 1904 ALIGN. 1905 1906 NOTE: When using this function, please add a comment above the call 1907 explaining why we know the non-constant coefficients must already 1908 be a multiple of ALIGN. */ 1909 1910template<unsigned int N, typename Ca, typename Cb> 1911inline poly_int<N, Ca> 1912force_align_up_and_div (const poly_int_pod<N, Ca> &value, Cb align) 1913{ 1914 gcc_checking_assert (can_align_p (value, align)); 1915 1916 poly_int<N, Ca> r; 1917 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0] 1918 + (-value.coeffs[0] & (align - 1))) 1919 / align)); 1920 if (N >= 2) 1921 for (unsigned int i = 1; i < N; i++) 1922 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align); 1923 return r; 1924} 1925 1926/* Return true if we know at compile time the difference between VALUE 1927 and the equal or preceding multiple of ALIGN. Store the value in 1928 *MISALIGN if so. */ 1929 1930template<unsigned int N, typename Ca, typename Cb, typename Cm> 1931inline bool 1932known_misalignment (const poly_int_pod<N, Ca> &value, Cb align, Cm *misalign) 1933{ 1934 gcc_checking_assert (align != 0); 1935 if (!can_align_p (value, align)) 1936 return false; 1937 *misalign = value.coeffs[0] & (align - 1); 1938 return true; 1939} 1940 1941/* Return X & (Y - 1), asserting that this value is known. Please add 1942 an a comment above callers to this function to explain why the condition 1943 is known to hold. */ 1944 1945template<unsigned int N, typename Ca, typename Cb> 1946inline POLY_BINARY_COEFF (Ca, Ca) 1947force_get_misalignment (const poly_int_pod<N, Ca> &a, Cb align) 1948{ 1949 gcc_checking_assert (can_align_p (a, align)); 1950 return a.coeffs[0] & (align - 1); 1951} 1952 1953/* Return the maximum alignment that A is known to have. Return 0 1954 if A is known to be zero. */ 1955 1956template<unsigned int N, typename Ca> 1957inline POLY_BINARY_COEFF (Ca, Ca) 1958known_alignment (const poly_int_pod<N, Ca> &a) 1959{ 1960 typedef POLY_BINARY_COEFF (Ca, Ca) C; 1961 C r = a.coeffs[0]; 1962 for (unsigned int i = 1; i < N; ++i) 1963 r |= a.coeffs[i]; 1964 return r & -r; 1965} 1966 1967/* Return true if we can compute A | B at compile time, storing the 1968 result in RES if so. */ 1969 1970template<unsigned int N, typename Ca, typename Cb, typename Cr> 1971inline typename if_nonpoly<Cb, bool>::type 1972can_ior_p (const poly_int_pod<N, Ca> &a, Cb b, Cr *result) 1973{ 1974 /* Coefficients 1 and above must be a multiple of something greater 1975 than B. */ 1976 typedef POLY_INT_TYPE (Ca) int_type; 1977 if (N >= 2) 1978 for (unsigned int i = 1; i < N; i++) 1979 if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0)) 1980 return false; 1981 *result = a; 1982 result->coeffs[0] |= b; 1983 return true; 1984} 1985 1986/* Return true if A is a constant multiple of B, storing the 1987 multiple in *MULTIPLE if so. */ 1988 1989template<unsigned int N, typename Ca, typename Cb, typename Cm> 1990inline typename if_nonpoly<Cb, bool>::type 1991constant_multiple_p (const poly_int_pod<N, Ca> &a, Cb b, Cm *multiple) 1992{ 1993 typedef POLY_CAST (Ca, Cb) NCa; 1994 typedef POLY_CAST (Cb, Ca) NCb; 1995 1996 /* Do the modulus before the constant check, to catch divide by 1997 zero errors. */ 1998 if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ()) 1999 return false; 2000 *multiple = NCa (a.coeffs[0]) / NCb (b); 2001 return true; 2002} 2003 2004template<unsigned int N, typename Ca, typename Cb, typename Cm> 2005inline typename if_nonpoly<Ca, bool>::type 2006constant_multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple) 2007{ 2008 typedef POLY_CAST (Ca, Cb) NCa; 2009 typedef POLY_CAST (Cb, Ca) NCb; 2010 typedef POLY_INT_TYPE (Ca) int_type; 2011 2012 /* Do the modulus before the constant check, to catch divide by 2013 zero errors. */ 2014 if (NCa (a) % NCb (b.coeffs[0]) != 0 2015 || (a != int_type (0) && !b.is_constant ())) 2016 return false; 2017 *multiple = NCa (a) / NCb (b.coeffs[0]); 2018 return true; 2019} 2020 2021template<unsigned int N, typename Ca, typename Cb, typename Cm> 2022inline bool 2023constant_multiple_p (const poly_int_pod<N, Ca> &a, 2024 const poly_int_pod<N, Cb> &b, Cm *multiple) 2025{ 2026 typedef POLY_CAST (Ca, Cb) NCa; 2027 typedef POLY_CAST (Cb, Ca) NCb; 2028 typedef POLY_INT_TYPE (Ca) ICa; 2029 typedef POLY_INT_TYPE (Cb) ICb; 2030 typedef POLY_BINARY_COEFF (Ca, Cb) C; 2031 2032 if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0) 2033 return false; 2034 2035 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]); 2036 for (unsigned int i = 1; i < N; ++i) 2037 if (b.coeffs[i] == ICb (0) 2038 ? a.coeffs[i] != ICa (0) 2039 : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0 2040 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r)) 2041 return false; 2042 2043 *multiple = r; 2044 return true; 2045} 2046 2047/* Return true if A is a multiple of B. */ 2048 2049template<typename Ca, typename Cb> 2050inline typename if_nonpoly2<Ca, Cb, bool>::type 2051multiple_p (Ca a, Cb b) 2052{ 2053 return a % b == 0; 2054} 2055 2056/* Return true if A is a (polynomial) multiple of B. */ 2057 2058template<unsigned int N, typename Ca, typename Cb> 2059inline typename if_nonpoly<Cb, bool>::type 2060multiple_p (const poly_int_pod<N, Ca> &a, Cb b) 2061{ 2062 for (unsigned int i = 0; i < N; ++i) 2063 if (a.coeffs[i] % b != 0) 2064 return false; 2065 return true; 2066} 2067 2068/* Return true if A is a (constant) multiple of B. */ 2069 2070template<unsigned int N, typename Ca, typename Cb> 2071inline typename if_nonpoly<Ca, bool>::type 2072multiple_p (Ca a, const poly_int_pod<N, Cb> &b) 2073{ 2074 typedef POLY_INT_TYPE (Ca) int_type; 2075 2076 /* Do the modulus before the constant check, to catch divide by 2077 potential zeros. */ 2078 return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ()); 2079} 2080 2081/* Return true if A is a (polynomial) multiple of B. This handles cases 2082 where either B is constant or the multiple is constant. */ 2083 2084template<unsigned int N, typename Ca, typename Cb> 2085inline bool 2086multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 2087{ 2088 if (b.is_constant ()) 2089 return multiple_p (a, b.coeffs[0]); 2090 POLY_BINARY_COEFF (Ca, Ca) tmp; 2091 return constant_multiple_p (a, b, &tmp); 2092} 2093 2094/* Return true if A is a (constant) multiple of B, storing the 2095 multiple in *MULTIPLE if so. */ 2096 2097template<typename Ca, typename Cb, typename Cm> 2098inline typename if_nonpoly2<Ca, Cb, bool>::type 2099multiple_p (Ca a, Cb b, Cm *multiple) 2100{ 2101 if (a % b != 0) 2102 return false; 2103 *multiple = a / b; 2104 return true; 2105} 2106 2107/* Return true if A is a (polynomial) multiple of B, storing the 2108 multiple in *MULTIPLE if so. */ 2109 2110template<unsigned int N, typename Ca, typename Cb, typename Cm> 2111inline typename if_nonpoly<Cb, bool>::type 2112multiple_p (const poly_int_pod<N, Ca> &a, Cb b, poly_int_pod<N, Cm> *multiple) 2113{ 2114 if (!multiple_p (a, b)) 2115 return false; 2116 for (unsigned int i = 0; i < N; ++i) 2117 multiple->coeffs[i] = a.coeffs[i] / b; 2118 return true; 2119} 2120 2121/* Return true if B is a constant and A is a (constant) multiple of B, 2122 storing the multiple in *MULTIPLE if so. */ 2123 2124template<unsigned int N, typename Ca, typename Cb, typename Cm> 2125inline typename if_nonpoly<Ca, bool>::type 2126multiple_p (Ca a, const poly_int_pod<N, Cb> &b, Cm *multiple) 2127{ 2128 typedef POLY_CAST (Ca, Cb) NCa; 2129 2130 /* Do the modulus before the constant check, to catch divide by 2131 potential zeros. */ 2132 if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ())) 2133 return false; 2134 *multiple = a / b.coeffs[0]; 2135 return true; 2136} 2137 2138/* Return true if A is a (polynomial) multiple of B, storing the 2139 multiple in *MULTIPLE if so. This handles cases where either 2140 B is constant or the multiple is constant. */ 2141 2142template<unsigned int N, typename Ca, typename Cb, typename Cm> 2143inline bool 2144multiple_p (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b, 2145 poly_int_pod<N, Cm> *multiple) 2146{ 2147 if (b.is_constant ()) 2148 return multiple_p (a, b.coeffs[0], multiple); 2149 return constant_multiple_p (a, b, multiple); 2150} 2151 2152/* Return A / B, given that A is known to be a multiple of B. */ 2153 2154template<unsigned int N, typename Ca, typename Cb> 2155inline POLY_CONST_RESULT (N, Ca, Cb) 2156exact_div (const poly_int_pod<N, Ca> &a, Cb b) 2157{ 2158 typedef POLY_CONST_COEFF (Ca, Cb) C; 2159 poly_int<N, C> r; 2160 for (unsigned int i = 0; i < N; i++) 2161 { 2162 gcc_checking_assert (a.coeffs[i] % b == 0); 2163 POLY_SET_COEFF (C, r, i, a.coeffs[i] / b); 2164 } 2165 return r; 2166} 2167 2168/* Return A / B, given that A is known to be a multiple of B. */ 2169 2170template<unsigned int N, typename Ca, typename Cb> 2171inline POLY_POLY_RESULT (N, Ca, Cb) 2172exact_div (const poly_int_pod<N, Ca> &a, const poly_int_pod<N, Cb> &b) 2173{ 2174 if (b.is_constant ()) 2175 return exact_div (a, b.coeffs[0]); 2176 2177 typedef POLY_CAST (Ca, Cb) NCa; 2178 typedef POLY_CAST (Cb, Ca) NCb; 2179 typedef POLY_BINARY_COEFF (Ca, Cb) C; 2180 typedef POLY_INT_TYPE (Cb) int_type; 2181 2182 gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0); 2183 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]); 2184 for (unsigned int i = 1; i < N; ++i) 2185 gcc_checking_assert (b.coeffs[i] == int_type (0) 2186 ? a.coeffs[i] == int_type (0) 2187 : (a.coeffs[i] % b.coeffs[i] == 0 2188 && NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r)); 2189 2190 return r; 2191} 2192 2193/* Return true if there is some constant Q and polynomial r such that: 2194 2195 (1) a = b * Q + r 2196 (2) |b * Q| <= |a| 2197 (3) |r| < |b| 2198 2199 Store the value Q in *QUOTIENT if so. */ 2200 2201template<unsigned int N, typename Ca, typename Cb, typename Cq> 2202inline typename if_nonpoly2<Cb, Cq, bool>::type 2203can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b, Cq *quotient) 2204{ 2205 typedef POLY_CAST (Ca, Cb) NCa; 2206 typedef POLY_CAST (Cb, Ca) NCb; 2207 2208 /* Do the division before the constant check, to catch divide by 2209 zero errors. */ 2210 Cq q = NCa (a.coeffs[0]) / NCb (b); 2211 if (!a.is_constant ()) 2212 return false; 2213 *quotient = q; 2214 return true; 2215} 2216 2217template<unsigned int N, typename Ca, typename Cb, typename Cq> 2218inline typename if_nonpoly<Cq, bool>::type 2219can_div_trunc_p (const poly_int_pod<N, Ca> &a, 2220 const poly_int_pod<N, Cb> &b, 2221 Cq *quotient) 2222{ 2223 /* We can calculate Q from the case in which the indeterminates 2224 are zero. */ 2225 typedef POLY_CAST (Ca, Cb) NCa; 2226 typedef POLY_CAST (Cb, Ca) NCb; 2227 typedef POLY_INT_TYPE (Ca) ICa; 2228 typedef POLY_INT_TYPE (Cb) ICb; 2229 typedef POLY_BINARY_COEFF (Ca, Cb) C; 2230 C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]); 2231 2232 /* Check the other coefficients and record whether the division is exact. 2233 The only difficult case is when it isn't. If we require a and b to 2234 ordered wrt zero, there can be no two coefficients of the same value 2235 that have opposite signs. This means that: 2236 2237 |a| = |a0| + |a1 * x1| + |a2 * x2| + ... 2238 |b| = |b0| + |b1 * x1| + |b2 * x2| + ... 2239 2240 The Q we've just calculated guarantees: 2241 2242 |b0 * Q| <= |a0| 2243 |a0 - b0 * Q| < |b0| 2244 2245 and so: 2246 2247 (2) |b * Q| <= |a| 2248 2249 is satisfied if: 2250 2251 |bi * xi * Q| <= |ai * xi| 2252 2253 for each i in [1, N]. This is trivially true when xi is zero. 2254 When it isn't we need: 2255 2256 (2') |bi * Q| <= |ai| 2257 2258 r is calculated as: 2259 2260 r = r0 + r1 * x1 + r2 * x2 + ... 2261 where ri = ai - bi * Q 2262 2263 Restricting to ordered a and b also guarantees that no two ris 2264 have opposite signs, so we have: 2265 2266 |r| = |r0| + |r1 * x1| + |r2 * x2| + ... 2267 2268 We know from the calculation of Q that |r0| < |b0|, so: 2269 2270 (3) |r| < |b| 2271 2272 is satisfied if: 2273 2274 (3') |ai - bi * Q| <= |bi| 2275 2276 for each i in [1, N]. */ 2277 bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0; 2278 for (unsigned int i = 1; i < N; ++i) 2279 { 2280 if (b.coeffs[i] == ICb (0)) 2281 { 2282 /* For bi == 0 we simply need: (3') |ai| == 0. */ 2283 if (a.coeffs[i] != ICa (0)) 2284 return false; 2285 } 2286 else 2287 { 2288 if (q == 0) 2289 { 2290 /* For Q == 0 we simply need: (3') |ai| <= |bi|. */ 2291 if (a.coeffs[i] != ICa (0)) 2292 { 2293 /* Use negative absolute to avoid overflow, i.e. 2294 -|ai| >= -|bi|. */ 2295 C neg_abs_a = (a.coeffs[i] < 0 ? a.coeffs[i] : -a.coeffs[i]); 2296 C neg_abs_b = (b.coeffs[i] < 0 ? b.coeffs[i] : -b.coeffs[i]); 2297 if (neg_abs_a < neg_abs_b) 2298 return false; 2299 rem_p = true; 2300 } 2301 } 2302 else 2303 { 2304 /* Otherwise just check for the case in which ai / bi == Q. */ 2305 if (NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != q) 2306 return false; 2307 if (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0) 2308 rem_p = true; 2309 } 2310 } 2311 } 2312 2313 /* If the division isn't exact, require both values to be ordered wrt 0, 2314 so that we can guarantee conditions (2) and (3) for all indeterminate 2315 values. */ 2316 if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0)))) 2317 return false; 2318 2319 *quotient = q; 2320 return true; 2321} 2322 2323/* Likewise, but also store r in *REMAINDER. */ 2324 2325template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr> 2326inline typename if_nonpoly<Cq, bool>::type 2327can_div_trunc_p (const poly_int_pod<N, Ca> &a, 2328 const poly_int_pod<N, Cb> &b, 2329 Cq *quotient, Cr *remainder) 2330{ 2331 if (!can_div_trunc_p (a, b, quotient)) 2332 return false; 2333 *remainder = a - *quotient * b; 2334 return true; 2335} 2336 2337/* Return true if there is some polynomial q and constant R such that: 2338 2339 (1) a = B * q + R 2340 (2) |B * q| <= |a| 2341 (3) |R| < |B| 2342 2343 Store the value q in *QUOTIENT if so. */ 2344 2345template<unsigned int N, typename Ca, typename Cb, typename Cq> 2346inline typename if_nonpoly<Cb, bool>::type 2347can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b, 2348 poly_int_pod<N, Cq> *quotient) 2349{ 2350 /* The remainder must be constant. */ 2351 for (unsigned int i = 1; i < N; ++i) 2352 if (a.coeffs[i] % b != 0) 2353 return false; 2354 for (unsigned int i = 0; i < N; ++i) 2355 quotient->coeffs[i] = a.coeffs[i] / b; 2356 return true; 2357} 2358 2359/* Likewise, but also store R in *REMAINDER. */ 2360 2361template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr> 2362inline typename if_nonpoly<Cb, bool>::type 2363can_div_trunc_p (const poly_int_pod<N, Ca> &a, Cb b, 2364 poly_int_pod<N, Cq> *quotient, Cr *remainder) 2365{ 2366 if (!can_div_trunc_p (a, b, quotient)) 2367 return false; 2368 *remainder = a.coeffs[0] % b; 2369 return true; 2370} 2371 2372/* Return true if we can compute A / B at compile time, rounding towards zero. 2373 Store the result in QUOTIENT if so. 2374 2375 This handles cases in which either B is constant or the result is 2376 constant. */ 2377 2378template<unsigned int N, typename Ca, typename Cb, typename Cq> 2379inline bool 2380can_div_trunc_p (const poly_int_pod<N, Ca> &a, 2381 const poly_int_pod<N, Cb> &b, 2382 poly_int_pod<N, Cq> *quotient) 2383{ 2384 if (b.is_constant ()) 2385 return can_div_trunc_p (a, b.coeffs[0], quotient); 2386 if (!can_div_trunc_p (a, b, "ient->coeffs[0])) 2387 return false; 2388 for (unsigned int i = 1; i < N; ++i) 2389 quotient->coeffs[i] = 0; 2390 return true; 2391} 2392 2393/* Return true if there is some constant Q and polynomial r such that: 2394 2395 (1) a = b * Q + r 2396 (2) |a| <= |b * Q| 2397 (3) |r| < |b| 2398 2399 Store the value Q in *QUOTIENT if so. */ 2400 2401template<unsigned int N, typename Ca, typename Cb, typename Cq> 2402inline typename if_nonpoly<Cq, bool>::type 2403can_div_away_from_zero_p (const poly_int_pod<N, Ca> &a, 2404 const poly_int_pod<N, Cb> &b, 2405 Cq *quotient) 2406{ 2407 if (!can_div_trunc_p (a, b, quotient)) 2408 return false; 2409 if (maybe_ne (*quotient * b, a)) 2410 *quotient += (*quotient < 0 ? -1 : 1); 2411 return true; 2412} 2413 2414/* Use print_dec to print VALUE to FILE, where SGN is the sign 2415 of the values. */ 2416 2417template<unsigned int N, typename C> 2418void 2419print_dec (const poly_int_pod<N, C> &value, FILE *file, signop sgn) 2420{ 2421 if (value.is_constant ()) 2422 print_dec (value.coeffs[0], file, sgn); 2423 else 2424 { 2425 fprintf (file, "["); 2426 for (unsigned int i = 0; i < N; ++i) 2427 { 2428 print_dec (value.coeffs[i], file, sgn); 2429 fputc (i == N - 1 ? ']' : ',', file); 2430 } 2431 } 2432} 2433 2434/* Likewise without the signop argument, for coefficients that have an 2435 inherent signedness. */ 2436 2437template<unsigned int N, typename C> 2438void 2439print_dec (const poly_int_pod<N, C> &value, FILE *file) 2440{ 2441 STATIC_ASSERT (poly_coeff_traits<C>::signedness >= 0); 2442 print_dec (value, file, 2443 poly_coeff_traits<C>::signedness ? SIGNED : UNSIGNED); 2444} 2445 2446/* Use print_hex to print VALUE to FILE. */ 2447 2448template<unsigned int N, typename C> 2449void 2450print_hex (const poly_int_pod<N, C> &value, FILE *file) 2451{ 2452 if (value.is_constant ()) 2453 print_hex (value.coeffs[0], file); 2454 else 2455 { 2456 fprintf (file, "["); 2457 for (unsigned int i = 0; i < N; ++i) 2458 { 2459 print_hex (value.coeffs[i], file); 2460 fputc (i == N - 1 ? ']' : ',', file); 2461 } 2462 } 2463} 2464 2465/* Helper for calculating the distance between two points P1 and P2, 2466 in cases where known_le (P1, P2). T1 and T2 are the types of the 2467 two positions, in either order. The coefficients of P2 - P1 have 2468 type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2 2469 have C++ primitive type, otherwise P2 - P1 has its usual 2470 wide-int-based type. 2471 2472 The actual subtraction should look something like this: 2473 2474 typedef poly_span_traits<T1, T2> span_traits; 2475 span_traits::cast (P2) - span_traits::cast (P1) 2476 2477 Applying the cast before the subtraction avoids undefined overflow 2478 for signed T1 and T2. 2479 2480 The implementation of the cast tries to avoid unnecessary arithmetic 2481 or copying. */ 2482template<typename T1, typename T2, 2483 typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2), 2484 unsigned HOST_WIDE_INT)> 2485struct poly_span_traits 2486{ 2487 template<typename T> 2488 static const T &cast (const T &x) { return x; } 2489}; 2490 2491template<typename T1, typename T2> 2492struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT> 2493{ 2494 template<typename T> 2495 static typename if_nonpoly<T, unsigned HOST_WIDE_INT>::type 2496 cast (const T &x) { return x; } 2497 2498 template<unsigned int N, typename T> 2499 static poly_int<N, unsigned HOST_WIDE_INT> 2500 cast (const poly_int_pod<N, T> &x) { return x; } 2501}; 2502 2503/* Return true if SIZE represents a known size, assuming that all-ones 2504 indicates an unknown size. */ 2505 2506template<typename T> 2507inline bool 2508known_size_p (const T &a) 2509{ 2510 return maybe_ne (a, POLY_INT_TYPE (T) (-1)); 2511} 2512 2513/* Return true if range [POS, POS + SIZE) might include VAL. 2514 SIZE can be the special value -1, in which case the range is 2515 open-ended. */ 2516 2517template<typename T1, typename T2, typename T3> 2518inline bool 2519maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size) 2520{ 2521 typedef poly_span_traits<T1, T2> start_span; 2522 typedef poly_span_traits<T3, T3> size_span; 2523 if (known_lt (val, pos)) 2524 return false; 2525 if (!known_size_p (size)) 2526 return true; 2527 if ((poly_int_traits<T1>::num_coeffs > 1 2528 || poly_int_traits<T2>::num_coeffs > 1) 2529 && maybe_lt (val, pos)) 2530 /* In this case we don't know whether VAL >= POS is true at compile 2531 time, so we can't prove that VAL >= POS + SIZE. */ 2532 return true; 2533 return maybe_lt (start_span::cast (val) - start_span::cast (pos), 2534 size_span::cast (size)); 2535} 2536 2537/* Return true if range [POS, POS + SIZE) is known to include VAL. 2538 SIZE can be the special value -1, in which case the range is 2539 open-ended. */ 2540 2541template<typename T1, typename T2, typename T3> 2542inline bool 2543known_in_range_p (const T1 &val, const T2 &pos, const T3 &size) 2544{ 2545 typedef poly_span_traits<T1, T2> start_span; 2546 typedef poly_span_traits<T3, T3> size_span; 2547 return (known_size_p (size) 2548 && known_ge (val, pos) 2549 && known_lt (start_span::cast (val) - start_span::cast (pos), 2550 size_span::cast (size))); 2551} 2552 2553/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2) 2554 might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which 2555 case the range is open-ended. */ 2556 2557template<typename T1, typename T2, typename T3, typename T4> 2558inline bool 2559ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1, 2560 const T3 &pos2, const T4 &size2) 2561{ 2562 if (maybe_in_range_p (pos2, pos1, size1)) 2563 return maybe_ne (size2, POLY_INT_TYPE (T4) (0)); 2564 if (maybe_in_range_p (pos1, pos2, size2)) 2565 return maybe_ne (size1, POLY_INT_TYPE (T2) (0)); 2566 return false; 2567} 2568 2569/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2) 2570 are known to overlap. SIZE1 and/or SIZE2 can be the special value -1, 2571 in which case the range is open-ended. */ 2572 2573template<typename T1, typename T2, typename T3, typename T4> 2574inline bool 2575ranges_known_overlap_p (const T1 &pos1, const T2 &size1, 2576 const T3 &pos2, const T4 &size2) 2577{ 2578 typedef poly_span_traits<T1, T3> start_span; 2579 typedef poly_span_traits<T2, T2> size1_span; 2580 typedef poly_span_traits<T4, T4> size2_span; 2581 /* known_gt (POS1 + SIZE1, POS2) [infinite precision] 2582 --> known_gt (SIZE1, POS2 - POS1) [infinite precision] 2583 --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision] 2584 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative 2585 --> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))). 2586 2587 Using the saturating subtraction enforces that SIZE1 must be 2588 nonzero, since known_gt (0, x) is false for all nonnegative x. 2589 If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing 2590 indeterminate number I makes the unsaturated condition easier to 2591 satisfy, so using a saturated coefficient of zero tests the case in 2592 which the indeterminate is zero (the minimum value). */ 2593 return (known_size_p (size1) 2594 && known_size_p (size2) 2595 && known_lt (start_span::cast (pos2) 2596 - start_span::cast (lower_bound (pos1, pos2)), 2597 size1_span::cast (size1)) 2598 && known_lt (start_span::cast (pos1) 2599 - start_span::cast (lower_bound (pos1, pos2)), 2600 size2_span::cast (size2))); 2601} 2602 2603/* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of 2604 [POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1, 2605 in which case the range is open-ended. */ 2606 2607template<typename T1, typename T2, typename T3, typename T4> 2608inline bool 2609known_subrange_p (const T1 &pos1, const T2 &size1, 2610 const T3 &pos2, const T4 &size2) 2611{ 2612 typedef typename poly_int_traits<T2>::coeff_type C2; 2613 typedef poly_span_traits<T1, T3> start_span; 2614 typedef poly_span_traits<T2, T4> size_span; 2615 return (known_gt (size1, POLY_INT_TYPE (T2) (0)) 2616 && (poly_coeff_traits<C2>::signedness > 0 2617 || known_size_p (size1)) 2618 && known_size_p (size2) 2619 && known_ge (pos1, pos2) 2620 && known_le (size1, size2) 2621 && known_le (start_span::cast (pos1) - start_span::cast (pos2), 2622 size_span::cast (size2) - size_span::cast (size1))); 2623} 2624 2625/* Return true if the endpoint of the range [POS, POS + SIZE) can be 2626 stored in a T, or if SIZE is the special value -1, which makes the 2627 range open-ended. */ 2628 2629template<typename T> 2630inline typename if_nonpoly<T, bool>::type 2631endpoint_representable_p (const T &pos, const T &size) 2632{ 2633 return (!known_size_p (size) 2634 || pos <= poly_coeff_traits<T>::max_value - size); 2635} 2636 2637template<unsigned int N, typename C> 2638inline bool 2639endpoint_representable_p (const poly_int_pod<N, C> &pos, 2640 const poly_int_pod<N, C> &size) 2641{ 2642 if (known_size_p (size)) 2643 for (unsigned int i = 0; i < N; ++i) 2644 if (pos.coeffs[i] > poly_coeff_traits<C>::max_value - size.coeffs[i]) 2645 return false; 2646 return true; 2647} 2648 2649template<unsigned int N, typename C> 2650void 2651gt_ggc_mx (poly_int_pod<N, C> *) 2652{ 2653} 2654 2655template<unsigned int N, typename C> 2656void 2657gt_pch_nx (poly_int_pod<N, C> *) 2658{ 2659} 2660 2661template<unsigned int N, typename C> 2662void 2663gt_pch_nx (poly_int_pod<N, C> *, void (*) (void *, void *), void *) 2664{ 2665} 2666 2667#undef POLY_SET_COEFF 2668#undef POLY_INT_TYPE 2669#undef POLY_BINARY_COEFF 2670#undef CONST_CONST_RESULT 2671#undef POLY_CONST_RESULT 2672#undef CONST_POLY_RESULT 2673#undef POLY_POLY_RESULT 2674#undef POLY_CONST_COEFF 2675#undef CONST_POLY_COEFF 2676#undef POLY_POLY_COEFF 2677 2678#endif 2679