GCC Middle and Back End API Reference
poly-int.h
Go to the documentation of this file.
1/* Polynomial integer classes.
2 Copyright (C) 2014-2024 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> class poly_int;
33
34/* poly_coeff_traiits<T> describes the properties of a poly_int
35 coefficient type T:
36
37 - poly_coeff_traits<T1>::rank is less than poly_coeff_traits<T2>::rank
38 if T1 can promote to T2. For C-like types the rank is:
39
40 (2 * number of bytes) + (unsigned ? 1 : 0)
41
42 wide_ints don't have a normal rank and so use a value of INT_MAX.
43 Any fixed-width integer should be promoted to wide_int if possible
44 and lead to an error otherwise.
45
46 - poly_coeff_traits<T>::int_type is the type to which an integer
47 literal should be cast before comparing it with T.
48
49 - poly_coeff_traits<T>::precision is the number of bits that T can hold.
50
51 - poly_coeff_traits<T>::signedness is:
52 0 if T is unsigned
53 1 if T is signed
54 -1 if T has no inherent sign (as for wide_int).
55
56 - poly_coeff_traits<T>::max_value, if defined, is the maximum value of T.
57
58 - poly_coeff_traits<T>::result is a type that can hold results of
59 operations on T. This is different from T itself in cases where T
60 is the result of an accessor like wi::to_offset.
61
62 - poly_coeff_traits<T>::init_cast<Arg>::type is the type to which
63 an argument of type Arg should be casted before being used to
64 initialize a coefficient of type T. */
65template<typename T, wi::precision_type = wi::int_traits<T>::precision_type>
67
68template<typename T>
69struct poly_coeff_traits<T, wi::FLEXIBLE_PRECISION>
70{
71 typedef T result;
72 typedef T int_type;
73 static const int signedness = (T (0) >= T (-1));
74 static const int precision = sizeof (T) * CHAR_BIT;
75 static const T max_value = (signedness
76 ? ((T (1) << (precision - 2))
77 + ((T (1) << (precision - 2)) - 1))
78 : T (-1));
79 static const int rank = sizeof (T) * 2 + !signedness;
80
81 template<typename Arg>
82 struct init_cast { using type = T; };
83};
84
85template<typename T>
86struct poly_coeff_traits<T, wi::VAR_PRECISION>
87{
88 typedef T result;
89 typedef int int_type;
90 static const int signedness = -1;
91 static const int precision = WIDE_INT_MAX_PRECISION;
92 static const int rank = INT_MAX;
93
94 template<typename Arg>
95 struct init_cast { using type = const Arg &; };
96};
97
98template<typename T>
99struct poly_coeff_traits<T, wi::INL_CONST_PRECISION>
100{
101 typedef WI_UNARY_RESULT (T) result;
102 typedef int int_type;
103 /* These types are always signed. */
104 static const int signedness = 1;
105 static const int precision = wi::int_traits<T>::precision;
106 static const int rank = precision * 2 / CHAR_BIT;
107
108 template<typename Arg>
109 struct init_cast { using type = const Arg &; };
110};
111
112template<typename T>
113struct poly_coeff_traits<T, wi::CONST_PRECISION>
114{
115 typedef WI_UNARY_RESULT (T) result;
116 typedef int int_type;
117 /* These types are always signed. */
118 static const int signedness = 1;
119 static const int precision = wi::int_traits<T>::precision;
120 static const int rank = precision * 2 / CHAR_BIT;
121
122 template<typename Arg>
123 struct init_cast { using type = const Arg &; };
124};
125
126/* Information about a pair of coefficient types. */
127template<typename T1, typename T2>
129{
130 /* True if T1 can represent all the values of T2.
131
132 Either:
133
134 - T1 should be a type with the same signedness as T2 and no less
135 precision. This allows things like int16_t -> int16_t and
136 uint32_t -> uint64_t.
137
138 - T1 should be signed, T2 should be unsigned, and T1 should be
139 wider than T2. This allows things like uint16_t -> int32_t.
140
141 This rules out cases in which T1 has less precision than T2 or where
142 the conversion would reinterpret the top bit. E.g. int16_t -> uint32_t
143 can be dangerous and should have an explicit cast if deliberate. */
148 : (poly_coeff_traits<T1>::signedness == 1
149 && poly_coeff_traits<T2>::signedness == 0
150 && (poly_coeff_traits<T1>::precision
151 > poly_coeff_traits<T2>::precision)));
152
153 /* 0 if T1 op T2 should promote to HOST_WIDE_INT,
154 1 if T1 op T2 should promote to unsigned HOST_WIDE_INT,
155 2 if T1 op T2 should use wide-int rules. */
156#define RANK(X) poly_coeff_traits<X>::rank
157 static const int result_kind
158 = ((RANK (T1) <= RANK (HOST_WIDE_INT)
159 && RANK (T2) <= RANK (HOST_WIDE_INT))
160 ? 0
161 : (RANK (T1) <= RANK (unsigned HOST_WIDE_INT)
162 && RANK (T2) <= RANK (unsigned HOST_WIDE_INT))
163 ? 1 : 2);
164#undef RANK
165};
166
167/* SFINAE class that makes T3 available as "type" if T2 can represent all the
168 values in T1. */
169template<typename T1, typename T2, typename T3,
172template<typename T1, typename T2, typename T3>
173struct if_lossless<T1, T2, T3, true>
174{
175 typedef T3 type;
176};
177
178/* poly_int_traits<T> describes an integer type T that might be polynomial
179 or non-polynomial:
180
181 - poly_int_traits<T>::is_poly is true if T is a poly_int-based type
182 and false otherwise.
183
184 - poly_int_traits<T>::num_coeffs gives the number of coefficients in T
185 if T is a poly_int and 1 otherwise.
186
187 - poly_int_traits<T>::coeff_type gives the coefficent type of T if T
188 is a poly_int and T itself otherwise
189
190 - poly_int_traits<T>::int_type is a shorthand for
191 typename poly_coeff_traits<coeff_type>::int_type. */
192template<typename T>
194{
195 static const bool is_poly = false;
196 static const unsigned int num_coeffs = 1;
197 typedef T coeff_type;
199};
200template<unsigned int N, typename C>
202{
203 static const bool is_poly = true;
204 static const unsigned int num_coeffs = N;
205 typedef C coeff_type;
207};
208
209/* SFINAE class that makes T2 available as "type" if T1 is a non-polynomial
210 type. */
211template<typename T1, typename T2 = T1,
212 bool is_poly = poly_int_traits<T1>::is_poly>
213struct if_nonpoly {};
214template<typename T1, typename T2>
215struct if_nonpoly<T1, T2, false>
216{
217 typedef T2 type;
218};
219
220/* SFINAE class that makes T3 available as "type" if both T1 and T2 are
221 non-polynomial types. */
222template<typename T1, typename T2, typename T3,
223 bool is_poly1 = poly_int_traits<T1>::is_poly,
224 bool is_poly2 = poly_int_traits<T2>::is_poly>
225struct if_nonpoly2 {};
226template<typename T1, typename T2, typename T3>
227struct if_nonpoly2<T1, T2, T3, false, false>
228{
229 typedef T3 type;
230};
231
232/* SFINAE class that makes T2 available as "type" if T1 is a polynomial
233 type. */
234template<typename T1, typename T2 = T1,
235 bool is_poly = poly_int_traits<T1>::is_poly>
236struct if_poly {};
237template<typename T1, typename T2>
238struct if_poly<T1, T2, true>
239{
240 typedef T2 type;
241};
242
243/* poly_result<T1, T2> describes the result of an operation on two
244 types T1 and T2, where at least one of the types is polynomial:
245
246 - poly_result<T1, T2>::type gives the result type for the operation.
247 The intention is to provide normal C-like rules for integer ranks,
248 except that everything smaller than HOST_WIDE_INT promotes to
249 HOST_WIDE_INT.
250
251 - poly_result<T1, T2>::cast is the type to which an operand of type
252 T1 should be cast before doing the operation, to ensure that
253 the operation is done at the right precision. Casting to
254 poly_result<T1, T2>::type would also work, but casting to this
255 type is more efficient. */
256template<typename T1, typename T2 = T1,
259
260/* Promote pair to HOST_WIDE_INT. */
261template<typename T1, typename T2>
262struct poly_result<T1, T2, 0>
263{
264 typedef HOST_WIDE_INT type;
265 /* T1 and T2 are primitive types, so cast values to T before operating
266 on them. */
267 typedef type cast;
268};
269
270/* Promote pair to unsigned HOST_WIDE_INT. */
271template<typename T1, typename T2>
272struct poly_result<T1, T2, 1>
273{
274 typedef unsigned HOST_WIDE_INT type;
275 /* T1 and T2 are primitive types, so cast values to T before operating
276 on them. */
277 typedef type cast;
278};
279
280/* Use normal wide-int rules. */
281template<typename T1, typename T2>
282struct poly_result<T1, T2, 2>
283{
284 typedef WI_BINARY_RESULT (T1, T2) type;
285 /* Don't cast values before operating on them; leave the wi:: routines
286 to handle promotion as necessary. */
287 typedef const T1 &cast;
288};
289
290/* The coefficient type for the result of a binary operation on two
291 poly_ints, the first of which has coefficients of type C1 and the
292 second of which has coefficients of type C2. */
293#define POLY_POLY_COEFF(C1, C2) typename poly_result<C1, C2>::type
294
295/* Enforce that T2 is non-polynomial and provide the cofficient type of
296 the result of a binary operation in which the first operand is a
297 poly_int with coefficients of type C1 and the second operand is
298 a constant of type T2. */
299#define POLY_CONST_COEFF(C1, T2) \
300 POLY_POLY_COEFF (C1, typename if_nonpoly<T2>::type)
301
302/* Likewise in reverse. */
303#define CONST_POLY_COEFF(T1, C2) \
304 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, C2)
305
306/* The result type for a binary operation on poly_int<N, C1> and
307 poly_int<N, C2>. */
308#define POLY_POLY_RESULT(N, C1, C2) poly_int<N, POLY_POLY_COEFF (C1, C2)>
309
310/* Enforce that T2 is non-polynomial and provide the result type
311 for a binary operation on poly_int<N, C1> and T2. */
312#define POLY_CONST_RESULT(N, C1, T2) poly_int<N, POLY_CONST_COEFF (C1, T2)>
313
314/* Enforce that T1 is non-polynomial and provide the result type
315 for a binary operation on T1 and poly_int<N, C2>. */
316#define CONST_POLY_RESULT(N, T1, C2) poly_int<N, CONST_POLY_COEFF (T1, C2)>
317
318/* Enforce that T1 and T2 are non-polynomial and provide the result type
319 for a binary operation on T1 and T2. */
320#define CONST_CONST_RESULT(N, T1, T2) \
321 POLY_POLY_COEFF (typename if_nonpoly<T1>::type, \
322 typename if_nonpoly<T2>::type)
323
324/* The type to which a coefficient of type C1 should be cast before
325 using it in a binary operation with a coefficient of type C2. */
326#define POLY_CAST(C1, C2) typename poly_result<C1, C2>::cast
327
328/* Provide the coefficient type for the result of T1 op T2, where T1
329 and T2 can be polynomial or non-polynomial. */
330#define POLY_BINARY_COEFF(T1, T2) \
331 typename poly_result<typename poly_int_traits<T1>::coeff_type, \
332 typename poly_int_traits<T2>::coeff_type>::type
333
334/* The type to which an integer constant should be cast before
335 comparing it with T. */
336#define POLY_INT_TYPE(T) typename poly_int_traits<T>::int_type
337
338/* RES is a poly_int result that has coefficients of type C and that
339 is being built up a coefficient at a time. Set coefficient number I
340 to VALUE in the most efficient way possible.
341
342 For primitive C it is better to assign directly, since it avoids
343 any further calls and so is more efficient when the compiler is
344 built at -O0. But for wide-int based C it is better to construct
345 the value in-place. This means that calls out to a wide-int.cc
346 routine can take the address of RES rather than the address of
347 a temporary.
348
349 The dummy self-comparison against C * is just a way of checking
350 that C gives the right type. */
351#define POLY_SET_COEFF(C, RES, I, VALUE) \
352 ((void) (&(RES).coeffs[0] == (C *) (void *) &(RES).coeffs[0]), \
353 wi::int_traits<C>::precision_type == wi::FLEXIBLE_PRECISION \
354 ? (void) ((RES).coeffs[I] = VALUE) \
355 : (void) ((RES).coeffs[I].~C (), new (&(RES).coeffs[I]) C (VALUE)))
356
357/* poly_int_full and poly_int_hungry are used internally within poly_int
358 for delegated initializers. poly_int_full indicates that a parameter
359 pack has enough elements to initialize every coefficient. poly_int_hungry
360 indicates that at least one extra zero must be added. */
363
364/* poly_int_fullness<B>::type is poly_int_full when B is true and
365 poly_int_hungry when B is false. */
366template<bool> struct poly_int_fullness;
367template<> struct poly_int_fullness<false> { using type = poly_int_hungry; };
368template<> struct poly_int_fullness<true> { using type = poly_int_full; };
369
370/* A class containing polynomial integers. The polynomial has N coefficients
371 of type C, and N - 1 indeterminates. */
372template<unsigned int N, typename C>
374{
375public:
376 poly_int () = default;
377 poly_int (const poly_int &) = default;
378
379 template<typename Ca>
381
382 template<typename ...Cs>
383 constexpr poly_int (const Cs &...);
384
385 poly_int &operator = (const poly_int &) = default;
386
387 template<typename Ca>
389 template<typename Ca>
391
392 template<typename Ca>
394 template<typename Ca>
396
397 template<typename Ca>
399 template<typename Ca>
401
402 template<typename Ca>
404
405 poly_int &operator <<= (unsigned int);
406
407 bool is_constant () const;
408
409 template<typename T>
411
412 C to_constant () const;
413
414 template<typename Ca>
415 static poly_int<N, C> from (const poly_int<N, Ca> &, unsigned int,
416 signop);
417 template<typename Ca>
419
424
425#if POLY_INT_CONVERSION
426 operator C () const;
427#endif
428
430
431private:
432 template<typename ...Cs>
433 constexpr poly_int (poly_int_full, const Cs &...);
434
435 template<typename C0, typename ...Cs>
436 constexpr poly_int (poly_int_hungry, const C0 &, const Cs &...);
437};
438
439template<unsigned int N, typename C>
440template<typename Ca>
441inline
443{
444 for (unsigned int i = 0; i < N; i++)
445 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
446}
447
448template<unsigned int N, typename C>
449template<typename ...Cs>
450inline constexpr
451poly_int<N, C>::poly_int (const Cs &... cs)
452 : poly_int (typename poly_int_fullness<sizeof... (Cs) >= N>::type (),
453 cs...) {}
454
455/* Initialize with c0, cs..., and some trailing zeros. */
456template<unsigned int N, typename C>
457template<typename C0, typename ...Cs>
458inline constexpr
459poly_int<N, C>::poly_int (poly_int_hungry, const C0 &c0, const Cs &... cs)
460 : poly_int (c0, cs..., wi::ints_for<C>::zero (c0)) {}
461
462/* Initialize with cs... directly, casting where necessary. */
463template<unsigned int N, typename C>
464template<typename ...Cs>
465inline constexpr
467 : coeffs { (typename poly_coeff_traits<C>::
468 template init_cast<Cs>::type (cs))... } {}
469
470template<unsigned int N, typename C>
471template<typename Ca>
472inline poly_int<N, C>&
474{
475 for (unsigned int i = 0; i < N; i++)
476 POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
477 return *this;
478}
479
480template<unsigned int N, typename C>
481template<typename Ca>
482inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
484{
485 POLY_SET_COEFF (C, *this, 0, a);
486 if (N >= 2)
487 for (unsigned int i = 1; i < N; i++)
488 POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
489 return *this;
490}
491
492template<unsigned int N, typename C>
493template<typename Ca>
494inline poly_int<N, C>&
496{
497 for (unsigned int i = 0; i < N; i++)
498 this->coeffs[i] += a.coeffs[i];
499 return *this;
500}
501
502template<unsigned int N, typename C>
503template<typename Ca>
504inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
506{
507 this->coeffs[0] += a;
508 return *this;
509}
510
511template<unsigned int N, typename C>
512template<typename Ca>
513inline poly_int<N, C>&
515{
516 for (unsigned int i = 0; i < N; i++)
517 this->coeffs[i] -= a.coeffs[i];
518 return *this;
519}
520
521template<unsigned int N, typename C>
522template<typename Ca>
523inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
525{
526 this->coeffs[0] -= a;
527 return *this;
528}
529
530template<unsigned int N, typename C>
531template<typename Ca>
532inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
534{
535 for (unsigned int i = 0; i < N; i++)
536 this->coeffs[i] *= a;
537 return *this;
538}
539
540template<unsigned int N, typename C>
541inline poly_int<N, C>&
543{
544 for (unsigned int i = 0; i < N; i++)
545 this->coeffs[i] <<= a;
546 return *this;
547}
548
549/* Return true if the polynomial value is a compile-time constant. */
550
551template<unsigned int N, typename C>
552inline bool
554{
555 if (N >= 2)
556 for (unsigned int i = 1; i < N; i++)
557 if (this->coeffs[i] != 0)
558 return false;
559 return true;
560}
561
562/* Return true if the polynomial value is a compile-time constant,
563 storing its value in CONST_VALUE if so. */
564
565template<unsigned int N, typename C>
566template<typename T>
567inline typename if_lossless<T, C, bool>::type
568poly_int<N, C>::is_constant (T *const_value) const
569{
570 if (is_constant ())
571 {
572 *const_value = this->coeffs[0];
573 return true;
574 }
575 return false;
576}
577
578/* Return the value of a polynomial that is already known to be a
579 compile-time constant.
580
581 NOTE: When using this function, please add a comment above the call
582 explaining why we know the value is constant in that context. */
583
584template<unsigned int N, typename C>
585inline C
587{
588 gcc_checking_assert (is_constant ());
589 return this->coeffs[0];
590}
591
592/* Convert X to a wide_int-based polynomial in which each coefficient
593 has BITSIZE bits. If X's coefficients are smaller than BITSIZE,
594 extend them according to SGN. */
595
596template<unsigned int N, typename C>
597template<typename Ca>
598inline poly_int<N, C>
599poly_int<N, C>::from (const poly_int<N, Ca> &a, unsigned int bitsize,
600 signop sgn)
601{
603 for (unsigned int i = 0; i < N; i++)
604 POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], bitsize, sgn));
605 return r;
606}
607
608/* Convert X to a fixed_wide_int-based polynomial, extending according
609 to SGN. */
610
611template<unsigned int N, typename C>
612template<typename Ca>
613inline poly_int<N, C>
615{
617 for (unsigned int i = 0; i < N; i++)
618 POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], sgn));
619 return r;
620}
621
622/* Return true if the coefficients of this generic_wide_int-based
623 polynomial can be represented as signed HOST_WIDE_INTs without loss
624 of precision. Store the HOST_WIDE_INT representation in *R if so. */
625
626template<unsigned int N, typename C>
627inline bool
629{
630 for (unsigned int i = 0; i < N; i++)
631 if (!wi::fits_shwi_p (this->coeffs[i]))
632 return false;
633 for (unsigned int i = 0; i < N; i++)
634 r->coeffs[i] = this->coeffs[i].to_shwi ();
635 return true;
636}
637
638/* Return true if the coefficients of this generic_wide_int-based
639 polynomial can be represented as unsigned HOST_WIDE_INTs without
640 loss of precision. Store the unsigned HOST_WIDE_INT representation
641 in *R if so. */
642
643template<unsigned int N, typename C>
644inline bool
646{
647 for (unsigned int i = 0; i < N; i++)
648 if (!wi::fits_uhwi_p (this->coeffs[i]))
649 return false;
650 for (unsigned int i = 0; i < N; i++)
651 r->coeffs[i] = this->coeffs[i].to_uhwi ();
652 return true;
653}
654
655/* Force a generic_wide_int-based constant to HOST_WIDE_INT precision,
656 truncating if necessary. */
657
658template<unsigned int N, typename C>
661{
663 for (unsigned int i = 0; i < N; i++)
664 r.coeffs[i] = this->coeffs[i].to_shwi ();
665 return r;
666}
667
668/* Force a generic_wide_int-based constant to unsigned HOST_WIDE_INT precision,
669 truncating if necessary. */
670
671template<unsigned int N, typename C>
674{
676 for (unsigned int i = 0; i < N; i++)
677 r.coeffs[i] = this->coeffs[i].to_uhwi ();
678 return r;
679}
680
681#if POLY_INT_CONVERSION
682/* Provide a conversion operator to constants. */
683
684template<unsigned int N, typename C>
685inline
687{
688 gcc_checking_assert (this->is_constant ());
689 return this->coeffs[0];
690}
691#endif
692
693/* Return true if every coefficient of A is in the inclusive range [B, C]. */
694
695template<typename Ca, typename Cb, typename Cc>
696inline typename if_nonpoly<Ca, bool>::type
697coeffs_in_range_p (const Ca &a, const Cb &b, const Cc &c)
698{
699 return a >= b && a <= c;
700}
701
702template<unsigned int N, typename Ca, typename Cb, typename Cc>
703inline typename if_nonpoly<Ca, bool>::type
704coeffs_in_range_p (const poly_int<N, Ca> &a, const Cb &b, const Cc &c)
705{
706 for (unsigned int i = 0; i < N; i++)
707 if (a.coeffs[i] < b || a.coeffs[i] > c)
708 return false;
709 return true;
710}
711
712namespace wi {
713/* Poly version of wi::shwi, with the same interface. */
714
715template<unsigned int N>
718{
720 for (unsigned int i = 0; i < N; i++)
722 return r;
723}
724
725/* Poly version of wi::uhwi, with the same interface. */
726
727template<unsigned int N>
730{
732 for (unsigned int i = 0; i < N; i++)
734 return r;
735}
736
737/* Poly version of wi::sext, with the same interface. */
738
739template<unsigned int N, typename Ca>
740inline POLY_POLY_RESULT (N, Ca, Ca)
741sext (const poly_int<N, Ca> &a, unsigned int precision)
742{
743 typedef POLY_POLY_COEFF (Ca, Ca) C;
745 for (unsigned int i = 0; i < N; i++)
746 POLY_SET_COEFF (C, r, i, wi::sext (a.coeffs[i], precision));
747 return r;
748}
749
750/* Poly version of wi::zext, with the same interface. */
751
752template<unsigned int N, typename Ca>
753inline POLY_POLY_RESULT (N, Ca, Ca)
754zext (const poly_int<N, Ca> &a, unsigned int precision)
755{
756 typedef POLY_POLY_COEFF (Ca, Ca) C;
758 for (unsigned int i = 0; i < N; i++)
759 POLY_SET_COEFF (C, r, i, wi::zext (a.coeffs[i], precision));
760 return r;
761}
762}
763
764template<unsigned int N, typename Ca, typename Cb>
765inline POLY_POLY_RESULT (N, Ca, Cb)
766operator + (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
767{
768 typedef POLY_CAST (Ca, Cb) NCa;
769 typedef POLY_POLY_COEFF (Ca, Cb) C;
771 for (unsigned int i = 0; i < N; i++)
772 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) + b.coeffs[i]);
773 return r;
774}
775
776template<unsigned int N, typename Ca, typename Cb>
777inline POLY_CONST_RESULT (N, Ca, Cb)
778operator + (const poly_int<N, Ca> &a, const Cb &b)
779{
780 typedef POLY_CAST (Ca, Cb) NCa;
781 typedef POLY_CONST_COEFF (Ca, Cb) C;
783 POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) + b);
784 if (N >= 2)
785 for (unsigned int i = 1; i < N; i++)
786 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
787 return r;
788}
789
790template<unsigned int N, typename Ca, typename Cb>
791inline CONST_POLY_RESULT (N, Ca, Cb)
792operator + (const Ca &a, const poly_int<N, Cb> &b)
793{
794 typedef POLY_CAST (Cb, Ca) NCb;
795 typedef CONST_POLY_COEFF (Ca, Cb) C;
797 POLY_SET_COEFF (C, r, 0, a + NCb (b.coeffs[0]));
798 if (N >= 2)
799 for (unsigned int i = 1; i < N; i++)
800 POLY_SET_COEFF (C, r, i, NCb (b.coeffs[i]));
801 return r;
802}
803
804namespace wi {
805/* Poly versions of wi::add, with the same interface. */
806
807template<unsigned int N, typename Ca, typename Cb>
808inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
809add (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
810{
811 typedef WI_BINARY_RESULT (Ca, Cb) C;
813 for (unsigned int i = 0; i < N; i++)
814 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i]));
815 return r;
816}
817
818template<unsigned int N, typename Ca, typename Cb>
819inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
820add (const poly_int<N, Ca> &a, const Cb &b)
821{
822 typedef WI_BINARY_RESULT (Ca, Cb) C;
824 POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b));
825 for (unsigned int i = 1; i < N; i++)
826 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i],
828 return r;
829}
830
831template<unsigned int N, typename Ca, typename Cb>
832inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
833add (const Ca &a, const poly_int<N, Cb> &b)
834{
835 typedef WI_BINARY_RESULT (Ca, Cb) C;
837 POLY_SET_COEFF (C, r, 0, wi::add (a, b.coeffs[0]));
838 for (unsigned int i = 1; i < N; i++)
840 b.coeffs[i]));
841 return r;
842}
843
844template<unsigned int N, typename Ca, typename Cb>
845inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
846add (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
847 signop sgn, wi::overflow_type *overflow)
848{
849 typedef WI_BINARY_RESULT (Ca, Cb) C;
851 POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b.coeffs[0], sgn, overflow));
852 for (unsigned int i = 1; i < N; i++)
853 {
854 wi::overflow_type suboverflow;
855 POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i], sgn,
856 &suboverflow));
857 wi::accumulate_overflow (*overflow, suboverflow);
858 }
859 return r;
860}
861}
862
863template<unsigned int N, typename Ca, typename Cb>
864inline POLY_POLY_RESULT (N, Ca, Cb)
866{
867 typedef POLY_CAST (Ca, Cb) NCa;
868 typedef POLY_POLY_COEFF (Ca, Cb) C;
870 for (unsigned int i = 0; i < N; i++)
871 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) - b.coeffs[i]);
872 return r;
873}
874
875template<unsigned int N, typename Ca, typename Cb>
876inline POLY_CONST_RESULT (N, Ca, Cb)
877operator - (const poly_int<N, Ca> &a, const Cb &b)
878{
879 typedef POLY_CAST (Ca, Cb) NCa;
880 typedef POLY_CONST_COEFF (Ca, Cb) C;
882 POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) - b);
883 if (N >= 2)
884 for (unsigned int i = 1; i < N; i++)
885 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
886 return r;
887}
888
889template<unsigned int N, typename Ca, typename Cb>
890inline CONST_POLY_RESULT (N, Ca, Cb)
891operator - (const Ca &a, const poly_int<N, Cb> &b)
892{
893 typedef POLY_CAST (Cb, Ca) NCb;
894 typedef CONST_POLY_COEFF (Ca, Cb) C;
896 POLY_SET_COEFF (C, r, 0, a - NCb (b.coeffs[0]));
897 if (N >= 2)
898 for (unsigned int i = 1; i < N; i++)
899 POLY_SET_COEFF (C, r, i, -NCb (b.coeffs[i]));
900 return r;
901}
902
903namespace wi {
904/* Poly versions of wi::sub, with the same interface. */
905
906template<unsigned int N, typename Ca, typename Cb>
907inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
908sub (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
909{
910 typedef WI_BINARY_RESULT (Ca, Cb) C;
912 for (unsigned int i = 0; i < N; i++)
913 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], 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)>
919sub (const poly_int<N, Ca> &a, const Cb &b)
920{
921 typedef WI_BINARY_RESULT (Ca, Cb) C;
923 POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b));
924 for (unsigned int i = 1; i < N; i++)
925 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i],
927 return r;
928}
929
930template<unsigned int N, typename Ca, typename Cb>
931inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
932sub (const Ca &a, const poly_int<N, Cb> &b)
933{
934 typedef WI_BINARY_RESULT (Ca, Cb) C;
936 POLY_SET_COEFF (C, r, 0, wi::sub (a, b.coeffs[0]));
937 for (unsigned int i = 1; i < N; i++)
939 b.coeffs[i]));
940 return r;
941}
942
943template<unsigned int N, typename Ca, typename Cb>
944inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
945sub (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
946 signop sgn, wi::overflow_type *overflow)
947{
948 typedef WI_BINARY_RESULT (Ca, Cb) C;
950 POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b.coeffs[0], sgn, overflow));
951 for (unsigned int i = 1; i < N; i++)
952 {
953 wi::overflow_type suboverflow;
954 POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i], sgn,
955 &suboverflow));
956 wi::accumulate_overflow (*overflow, suboverflow);
957 }
958 return r;
959}
960}
961
962template<unsigned int N, typename Ca>
963inline POLY_POLY_RESULT (N, Ca, Ca)
965{
966 typedef POLY_CAST (Ca, Ca) NCa;
967 typedef POLY_POLY_COEFF (Ca, Ca) C;
969 for (unsigned int i = 0; i < N; i++)
970 POLY_SET_COEFF (C, r, i, -NCa (a.coeffs[i]));
971 return r;
972}
973
974namespace wi {
975/* Poly version of wi::neg, with the same interface. */
976
977template<unsigned int N, typename Ca>
978inline poly_int<N, WI_UNARY_RESULT (Ca)>
979neg (const poly_int<N, Ca> &a)
980{
981 typedef WI_UNARY_RESULT (Ca) C;
983 for (unsigned int i = 0; i < N; i++)
984 POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i]));
985 return r;
986}
987
988template<unsigned int N, typename Ca>
989inline poly_int<N, WI_UNARY_RESULT (Ca)>
990neg (const poly_int<N, Ca> &a, wi::overflow_type *overflow)
991{
992 typedef WI_UNARY_RESULT (Ca) C;
994 POLY_SET_COEFF (C, r, 0, wi::neg (a.coeffs[0], overflow));
995 for (unsigned int i = 1; i < N; i++)
996 {
997 wi::overflow_type suboverflow;
998 POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i], &suboverflow));
999 wi::accumulate_overflow (*overflow, suboverflow);
1000 }
1001 return r;
1002}
1003}
1004
1005template<unsigned int N, typename Ca>
1006inline POLY_POLY_RESULT (N, Ca, Ca)
1008{
1009 if (N >= 2)
1010 return -1 - a;
1011 return ~a.coeffs[0];
1012}
1013
1014template<unsigned int N, typename Ca, typename Cb>
1015inline POLY_CONST_RESULT (N, Ca, Cb)
1016operator * (const poly_int<N, Ca> &a, const Cb &b)
1017{
1018 typedef POLY_CAST (Ca, Cb) NCa;
1019 typedef POLY_CONST_COEFF (Ca, Cb) C;
1021 for (unsigned int i = 0; i < N; i++)
1022 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) * b);
1023 return r;
1024}
1025
1026template<unsigned int N, typename Ca, typename Cb>
1027inline CONST_POLY_RESULT (N, Ca, Cb)
1028operator * (const Ca &a, const poly_int<N, Cb> &b)
1029{
1030 typedef POLY_CAST (Ca, Cb) NCa;
1031 typedef CONST_POLY_COEFF (Ca, Cb) C;
1033 for (unsigned int i = 0; i < N; i++)
1034 POLY_SET_COEFF (C, r, i, NCa (a) * b.coeffs[i]);
1035 return r;
1036}
1037
1038namespace wi {
1039/* Poly versions of wi::mul, with the same interface. */
1040
1041template<unsigned int N, typename Ca, typename Cb>
1042inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1043mul (const poly_int<N, Ca> &a, const Cb &b)
1044{
1045 typedef WI_BINARY_RESULT (Ca, Cb) C;
1047 for (unsigned int i = 0; i < N; i++)
1048 POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b));
1049 return r;
1050}
1051
1052template<unsigned int N, typename Ca, typename Cb>
1053inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1054mul (const Ca &a, const poly_int<N, Cb> &b)
1055{
1056 typedef WI_BINARY_RESULT (Ca, Cb) C;
1058 for (unsigned int i = 0; i < N; i++)
1059 POLY_SET_COEFF (C, r, i, wi::mul (a, b.coeffs[i]));
1060 return r;
1061}
1062
1063template<unsigned int N, typename Ca, typename Cb>
1064inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1065mul (const poly_int<N, Ca> &a, const Cb &b,
1066 signop sgn, wi::overflow_type *overflow)
1067{
1068 typedef WI_BINARY_RESULT (Ca, Cb) C;
1070 POLY_SET_COEFF (C, r, 0, wi::mul (a.coeffs[0], b, sgn, overflow));
1071 for (unsigned int i = 1; i < N; i++)
1072 {
1073 wi::overflow_type suboverflow;
1074 POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b, sgn, &suboverflow));
1075 wi::accumulate_overflow (*overflow, suboverflow);
1076 }
1077 return r;
1078}
1079}
1080
1081template<unsigned int N, typename Ca, typename Cb>
1082inline POLY_POLY_RESULT (N, Ca, Ca)
1083operator << (const poly_int<N, Ca> &a, const Cb &b)
1084{
1085 typedef POLY_CAST (Ca, Ca) NCa;
1086 typedef POLY_POLY_COEFF (Ca, Ca) C;
1088 for (unsigned int i = 0; i < N; i++)
1089 POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) << b);
1090 return r;
1091}
1092
1093namespace wi {
1094/* Poly version of wi::lshift, with the same interface. */
1095
1096template<unsigned int N, typename Ca, typename Cb>
1097inline poly_int<N, WI_BINARY_RESULT (Ca, Ca)>
1098lshift (const poly_int<N, Ca> &a, const Cb &b)
1099{
1100 typedef WI_BINARY_RESULT (Ca, Ca) C;
1102 for (unsigned int i = 0; i < N; i++)
1103 POLY_SET_COEFF (C, r, i, wi::lshift (a.coeffs[i], b));
1104 return r;
1105}
1106}
1107
1108/* Poly version of sext_hwi, with the same interface. */
1109
1110template<unsigned int N, typename C>
1112sext_hwi (const poly_int<N, C> &a, unsigned int precision)
1113{
1115 for (unsigned int i = 0; i < N; i++)
1116 r.coeffs[i] = sext_hwi (a.coeffs[i], precision);
1117 return r;
1118}
1119
1120
1121/* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative
1122 integer x. */
1123
1124template<typename Ca, typename Cb>
1125inline bool
1126maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1)
1127{
1128 if (a1 != b1)
1129 /* a0 + a1 * x == b0 + b1 * x
1130 ==> (a1 - b1) * x == b0 - a0
1131 ==> x == (b0 - a0) / (a1 - b1)
1132
1133 We need to test whether that's a valid value of x.
1134 (b0 - a0) and (a1 - b1) must not have opposite signs
1135 and the result must be integral. */
1136 return (a1 < b1
1137 ? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0
1138 : b0 >= a0 && (b0 - a0) % (a1 - b1) == 0);
1139 return a0 == b0;
1140}
1141
1142/* Return true if a0 + a1 * x might equal b for some nonnegative
1143 integer x. */
1144
1145template<typename Ca, typename Cb>
1146inline bool
1147maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b)
1148{
1149 if (a1 != 0)
1150 /* a0 + a1 * x == b
1151 ==> x == (b - a0) / a1
1152
1153 We need to test whether that's a valid value of x.
1154 (b - a0) and a1 must not have opposite signs and the
1155 result must be integral. */
1156 return (a1 < 0
1157 ? b <= a0 && (a0 - b) % a1 == 0
1158 : b >= a0 && (b - a0) % a1 == 0);
1159 return a0 == b;
1160}
1161
1162/* Return true if A might equal B for some indeterminate values. */
1163
1164template<unsigned int N, typename Ca, typename Cb>
1165inline bool
1166maybe_eq (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1167{
1168 STATIC_ASSERT (N <= 2);
1169 if (N == 2)
1170 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]);
1171 return a.coeffs[0] == b.coeffs[0];
1172}
1173
1174template<unsigned int N, typename Ca, typename Cb>
1175inline typename if_nonpoly<Cb, bool>::type
1176maybe_eq (const poly_int<N, Ca> &a, const Cb &b)
1177{
1178 STATIC_ASSERT (N <= 2);
1179 if (N == 2)
1180 return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b);
1181 return a.coeffs[0] == b;
1182}
1183
1184template<unsigned int N, typename Ca, typename Cb>
1185inline typename if_nonpoly<Ca, bool>::type
1186maybe_eq (const Ca &a, const poly_int<N, Cb> &b)
1187{
1188 STATIC_ASSERT (N <= 2);
1189 if (N == 2)
1190 return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a);
1191 return a == b.coeffs[0];
1192}
1193
1194template<typename Ca, typename Cb>
1195inline typename if_nonpoly2<Ca, Cb, bool>::type
1196maybe_eq (const Ca &a, const Cb &b)
1197{
1198 return a == b;
1199}
1200
1201/* Return true if A might not equal B for some indeterminate values. */
1202
1203template<unsigned int N, typename Ca, typename Cb>
1204inline bool
1205maybe_ne (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1206{
1207 if (N >= 2)
1208 for (unsigned int i = 1; i < N; i++)
1209 if (a.coeffs[i] != b.coeffs[i])
1210 return true;
1211 return a.coeffs[0] != b.coeffs[0];
1212}
1213
1214template<unsigned int N, typename Ca, typename Cb>
1215inline typename if_nonpoly<Cb, bool>::type
1216maybe_ne (const poly_int<N, Ca> &a, const Cb &b)
1217{
1218 if (N >= 2)
1219 for (unsigned int i = 1; i < N; i++)
1220 if (a.coeffs[i] != 0)
1221 return true;
1222 return a.coeffs[0] != b;
1223}
1224
1225template<unsigned int N, typename Ca, typename Cb>
1226inline typename if_nonpoly<Ca, bool>::type
1227maybe_ne (const Ca &a, const poly_int<N, Cb> &b)
1228{
1229 if (N >= 2)
1230 for (unsigned int i = 1; i < N; i++)
1231 if (b.coeffs[i] != 0)
1232 return true;
1233 return a != b.coeffs[0];
1234}
1235
1236template<typename Ca, typename Cb>
1237inline typename if_nonpoly2<Ca, Cb, bool>::type
1238maybe_ne (const Ca &a, const Cb &b)
1239{
1240 return a != b;
1241}
1242
1243/* Return true if A is known to be equal to B. */
1244#define known_eq(A, B) (!maybe_ne (A, B))
1245
1246/* Return true if A is known to be unequal to B. */
1247#define known_ne(A, B) (!maybe_eq (A, B))
1248
1249/* Return true if A might be less than or equal to B for some
1250 indeterminate values. */
1251
1252template<unsigned int N, typename Ca, typename Cb>
1253inline bool
1254maybe_le (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1255{
1256 if (N >= 2)
1257 for (unsigned int i = 1; i < N; i++)
1258 if (a.coeffs[i] < b.coeffs[i])
1259 return true;
1260 return a.coeffs[0] <= b.coeffs[0];
1261}
1262
1263template<unsigned int N, typename Ca, typename Cb>
1264inline typename if_nonpoly<Cb, bool>::type
1265maybe_le (const poly_int<N, Ca> &a, const Cb &b)
1266{
1267 if (N >= 2)
1268 for (unsigned int i = 1; i < N; i++)
1269 if (a.coeffs[i] < 0)
1270 return true;
1271 return a.coeffs[0] <= b;
1272}
1273
1274template<unsigned int N, typename Ca, typename Cb>
1275inline typename if_nonpoly<Ca, bool>::type
1276maybe_le (const Ca &a, const poly_int<N, Cb> &b)
1277{
1278 if (N >= 2)
1279 for (unsigned int i = 1; i < N; i++)
1280 if (b.coeffs[i] > 0)
1281 return true;
1282 return a <= b.coeffs[0];
1283}
1284
1285template<typename Ca, typename Cb>
1286inline typename if_nonpoly2<Ca, Cb, bool>::type
1287maybe_le (const Ca &a, const Cb &b)
1288{
1289 return a <= b;
1290}
1291
1292/* Return true if A might be less than B for some indeterminate values. */
1293
1294template<unsigned int N, typename Ca, typename Cb>
1295inline bool
1296maybe_lt (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1297{
1298 if (N >= 2)
1299 for (unsigned int i = 1; i < N; i++)
1300 if (a.coeffs[i] < b.coeffs[i])
1301 return true;
1302 return a.coeffs[0] < b.coeffs[0];
1303}
1304
1305template<unsigned int N, typename Ca, typename Cb>
1306inline typename if_nonpoly<Cb, bool>::type
1307maybe_lt (const poly_int<N, Ca> &a, const Cb &b)
1308{
1309 if (N >= 2)
1310 for (unsigned int i = 1; i < N; i++)
1311 if (a.coeffs[i] < 0)
1312 return true;
1313 return a.coeffs[0] < b;
1314}
1315
1316template<unsigned int N, typename Ca, typename Cb>
1317inline typename if_nonpoly<Ca, bool>::type
1318maybe_lt (const Ca &a, const poly_int<N, Cb> &b)
1319{
1320 if (N >= 2)
1321 for (unsigned int i = 1; i < N; i++)
1322 if (b.coeffs[i] > 0)
1323 return true;
1324 return a < b.coeffs[0];
1325}
1326
1327template<typename Ca, typename Cb>
1328inline typename if_nonpoly2<Ca, Cb, bool>::type
1329maybe_lt (const Ca &a, const Cb &b)
1330{
1331 return a < b;
1332}
1333
1334/* Return true if A may be greater than or equal to B. */
1335#define maybe_ge(A, B) maybe_le (B, A)
1336
1337/* Return true if A may be greater than B. */
1338#define maybe_gt(A, B) maybe_lt (B, A)
1339
1340/* Return true if A is known to be less than or equal to B. */
1341#define known_le(A, B) (!maybe_gt (A, B))
1342
1343/* Return true if A is known to be less than B. */
1344#define known_lt(A, B) (!maybe_ge (A, B))
1345
1346/* Return true if A is known to be greater than B. */
1347#define known_gt(A, B) (!maybe_le (A, B))
1348
1349/* Return true if A is known to be greater than or equal to B. */
1350#define known_ge(A, B) (!maybe_lt (A, B))
1351
1352/* Return true if A and B are ordered by the partial ordering known_le. */
1353
1354template<typename T1, typename T2>
1355inline bool
1356ordered_p (const T1 &a, const T2 &b)
1357{
1360 || known_le (a, b)
1361 || known_le (b, a));
1362}
1363
1364/* Assert that A and B are known to be ordered and return the minimum
1365 of the two.
1366
1367 NOTE: When using this function, please add a comment above the call
1368 explaining why we know the values are ordered in that context. */
1369
1370template<unsigned int N, typename Ca, typename Cb>
1371inline POLY_POLY_RESULT (N, Ca, Cb)
1372ordered_min (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1373{
1374 if (known_le (a, b))
1375 return a;
1376 else
1377 {
1378 if (N > 1)
1380 return b;
1381 }
1382}
1383
1384template<unsigned int N, typename Ca, typename Cb>
1385inline CONST_POLY_RESULT (N, Ca, Cb)
1386ordered_min (const Ca &a, const poly_int<N, Cb> &b)
1387{
1388 if (known_le (a, b))
1389 return a;
1390 else
1391 {
1392 if (N > 1)
1394 return b;
1395 }
1396}
1397
1398template<unsigned int N, typename Ca, typename Cb>
1399inline POLY_CONST_RESULT (N, Ca, Cb)
1400ordered_min (const poly_int<N, Ca> &a, const Cb &b)
1401{
1402 if (known_le (a, b))
1403 return a;
1404 else
1405 {
1406 if (N > 1)
1408 return b;
1409 }
1410}
1411
1412/* Assert that A and B are known to be ordered and return the maximum
1413 of the two.
1414
1415 NOTE: When using this function, please add a comment above the call
1416 explaining why we know the values are ordered in that context. */
1417
1418template<unsigned int N, typename Ca, typename Cb>
1419inline POLY_POLY_RESULT (N, Ca, Cb)
1420ordered_max (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1421{
1422 if (known_le (a, b))
1423 return b;
1424 else
1425 {
1426 if (N > 1)
1428 return a;
1429 }
1430}
1431
1432template<unsigned int N, typename Ca, typename Cb>
1433inline CONST_POLY_RESULT (N, Ca, Cb)
1434ordered_max (const Ca &a, const poly_int<N, Cb> &b)
1435{
1436 if (known_le (a, b))
1437 return b;
1438 else
1439 {
1440 if (N > 1)
1442 return a;
1443 }
1444}
1445
1446template<unsigned int N, typename Ca, typename Cb>
1447inline POLY_CONST_RESULT (N, Ca, Cb)
1448ordered_max (const poly_int<N, Ca> &a, const Cb &b)
1449{
1450 if (known_le (a, b))
1451 return b;
1452 else
1453 {
1454 if (N > 1)
1456 return a;
1457 }
1458}
1459
1460/* Return a constant lower bound on the value of A, which is known
1461 to be nonnegative. */
1462
1463template<unsigned int N, typename Ca>
1464inline Ca
1465constant_lower_bound (const poly_int<N, Ca> &a)
1466{
1468 return a.coeffs[0];
1469}
1470
1471/* Return the constant lower bound of A, given that it is no less than B. */
1472
1473template<unsigned int N, typename Ca, typename Cb>
1474inline POLY_CONST_COEFF (Ca, Cb)
1475constant_lower_bound_with_limit (const poly_int<N, Ca> &a, const Cb &b)
1476{
1477 if (known_ge (a, b))
1478 return a.coeffs[0];
1479 return b;
1480}
1481
1482/* Return the constant upper bound of A, given that it is no greater
1483 than B. */
1484
1485template<unsigned int N, typename Ca, typename Cb>
1486inline POLY_CONST_COEFF (Ca, Cb)
1487constant_upper_bound_with_limit (const poly_int<N, Ca> &a, const Cb &b)
1488{
1489 if (known_le (a, b))
1490 return a.coeffs[0];
1491 return b;
1492}
1493
1494/* Return a value that is known to be no greater than A and B. This
1495 will be the greatest lower bound for some indeterminate values but
1496 not necessarily for all. */
1497
1498template<unsigned int N, typename Ca, typename Cb>
1499inline POLY_CONST_RESULT (N, Ca, Cb)
1500lower_bound (const poly_int<N, Ca> &a, const Cb &b)
1501{
1502 typedef POLY_CAST (Ca, Cb) NCa;
1503 typedef POLY_CAST (Cb, Ca) NCb;
1504 typedef POLY_INT_TYPE (Cb) ICb;
1505 typedef POLY_CONST_COEFF (Ca, Cb) C;
1506
1508 POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b)));
1509 if (N >= 2)
1510 for (unsigned int i = 1; i < N; i++)
1511 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0)));
1512 return r;
1513}
1514
1515template<unsigned int N, typename Ca, typename Cb>
1516inline CONST_POLY_RESULT (N, Ca, Cb)
1517lower_bound (const Ca &a, const poly_int<N, Cb> &b)
1518{
1519 return lower_bound (b, a);
1520}
1521
1522template<unsigned int N, typename Ca, typename Cb>
1523inline POLY_POLY_RESULT (N, Ca, Cb)
1524lower_bound (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1525{
1526 typedef POLY_CAST (Ca, Cb) NCa;
1527 typedef POLY_CAST (Cb, Ca) NCb;
1528 typedef POLY_POLY_COEFF (Ca, Cb) C;
1529
1531 for (unsigned int i = 0; i < N; i++)
1532 POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1533 return r;
1534}
1535
1536template<typename Ca, typename Cb>
1537inline CONST_CONST_RESULT (N, Ca, Cb)
1538lower_bound (const Ca &a, const Cb &b)
1539{
1540 return a < b ? a : b;
1541}
1542
1543/* Return a value that is known to be no less than A and B. This will
1544 be the least upper bound for some indeterminate values but not
1545 necessarily for all. */
1546
1547template<unsigned int N, typename Ca, typename Cb>
1548inline POLY_CONST_RESULT (N, Ca, Cb)
1549upper_bound (const poly_int<N, Ca> &a, const Cb &b)
1550{
1551 typedef POLY_CAST (Ca, Cb) NCa;
1552 typedef POLY_CAST (Cb, Ca) NCb;
1553 typedef POLY_INT_TYPE (Cb) ICb;
1554 typedef POLY_CONST_COEFF (Ca, Cb) C;
1555
1557 POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b)));
1558 if (N >= 2)
1559 for (unsigned int i = 1; i < N; i++)
1560 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0)));
1561 return r;
1562}
1563
1564template<unsigned int N, typename Ca, typename Cb>
1565inline CONST_POLY_RESULT (N, Ca, Cb)
1566upper_bound (const Ca &a, const poly_int<N, Cb> &b)
1567{
1568 return upper_bound (b, a);
1569}
1570
1571template<unsigned int N, typename Ca, typename Cb>
1572inline POLY_POLY_RESULT (N, Ca, Cb)
1573upper_bound (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1574{
1575 typedef POLY_CAST (Ca, Cb) NCa;
1576 typedef POLY_CAST (Cb, Ca) NCb;
1577 typedef POLY_POLY_COEFF (Ca, Cb) C;
1578
1580 for (unsigned int i = 0; i < N; i++)
1581 POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1582 return r;
1583}
1584
1585/* Return the greatest common divisor of all nonzero coefficients, or zero
1586 if all coefficients are zero. */
1587
1588template<unsigned int N, typename Ca>
1589inline POLY_BINARY_COEFF (Ca, Ca)
1590coeff_gcd (const poly_int<N, Ca> &a)
1591{
1592 /* Find the first nonzero coefficient, stopping at 0 whatever happens. */
1593 unsigned int i;
1594 for (i = N - 1; i > 0; --i)
1595 if (a.coeffs[i] != 0)
1596 break;
1597 typedef POLY_BINARY_COEFF (Ca, Ca) C;
1598 C r = a.coeffs[i];
1599 for (unsigned int j = 0; j < i; ++j)
1600 if (a.coeffs[j] != 0)
1601 r = gcd (r, C (a.coeffs[j]));
1602 return r;
1603}
1604
1605/* Return a value that is a multiple of both A and B. This will be the
1606 least common multiple for some indeterminate values but necessarily
1607 for all. */
1608
1609template<unsigned int N, typename Ca, typename Cb>
1610POLY_CONST_RESULT (N, Ca, Cb)
1611common_multiple (const poly_int<N, Ca> &a, Cb b)
1612{
1613 POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a);
1614 return a * (least_common_multiple (xgcd, b) / xgcd);
1615}
1616
1617template<unsigned int N, typename Ca, typename Cb>
1618inline CONST_POLY_RESULT (N, Ca, Cb)
1619common_multiple (const Ca &a, const poly_int<N, Cb> &b)
1620{
1621 return common_multiple (b, a);
1622}
1623
1624/* Return a value that is a multiple of both A and B, asserting that
1625 such a value exists. The result will be the least common multiple
1626 for some indeterminate values but necessarily for all.
1627
1628 NOTE: When using this function, please add a comment above the call
1629 explaining why we know the values have a common multiple (which might
1630 for example be because we know A / B is rational). */
1631
1632template<unsigned int N, typename Ca, typename Cb>
1633POLY_POLY_RESULT (N, Ca, Cb)
1634force_common_multiple (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1635{
1636 if (b.is_constant ())
1637 return common_multiple (a, b.coeffs[0]);
1638 if (a.is_constant ())
1639 return common_multiple (a.coeffs[0], b);
1640
1641 typedef POLY_CAST (Ca, Cb) NCa;
1642 typedef POLY_CAST (Cb, Ca) NCb;
1643 typedef POLY_BINARY_COEFF (Ca, Cb) C;
1644 typedef POLY_INT_TYPE (Ca) ICa;
1645
1646 for (unsigned int i = 1; i < N; ++i)
1647 if (a.coeffs[i] != ICa (0))
1648 {
1649 C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i]));
1650 C amul = lcm / a.coeffs[i];
1651 C bmul = lcm / b.coeffs[i];
1652 for (unsigned int j = 0; j < N; ++j)
1653 gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul);
1654 return a * amul;
1655 }
1656 gcc_unreachable ();
1657}
1658
1659/* Compare A and B for sorting purposes, returning -1 if A should come
1660 before B, 0 if A and B are identical, and 1 if A should come after B.
1661 This is a lexicographical compare of the coefficients in reverse order.
1662
1663 A consequence of this is that all constant sizes come before all
1664 non-constant ones, regardless of magnitude (since a size is never
1665 negative). This is what most callers want. For example, when laying
1666 data out on the stack, it's better to keep all the constant-sized
1667 data together so that it can be accessed as a constant offset from a
1668 single base. */
1669
1670template<unsigned int N, typename Ca, typename Cb>
1671inline int
1672compare_sizes_for_sort (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1673{
1674 for (unsigned int i = N; i-- > 0; )
1675 if (a.coeffs[i] != b.coeffs[i])
1676 return a.coeffs[i] < b.coeffs[i] ? -1 : 1;
1677 return 0;
1678}
1679
1680/* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */
1681
1682template<unsigned int N, typename Ca, typename Cb>
1683inline bool
1684can_align_p (const poly_int<N, Ca> &value, Cb align)
1685{
1686 for (unsigned int i = 1; i < N; i++)
1687 if ((value.coeffs[i] & (align - 1)) != 0)
1688 return false;
1689 return true;
1690}
1691
1692/* Return true if we can align VALUE up to the smallest multiple of
1693 ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */
1694
1695template<unsigned int N, typename Ca, typename Cb>
1696inline bool
1697can_align_up (const poly_int<N, Ca> &value, Cb align,
1698 poly_int<N, Ca> *aligned)
1699{
1700 if (!can_align_p (value, align))
1701 return false;
1702 *aligned = value + (-value.coeffs[0] & (align - 1));
1703 return true;
1704}
1705
1706/* Return true if we can align VALUE down to the largest multiple of
1707 ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */
1708
1709template<unsigned int N, typename Ca, typename Cb>
1710inline bool
1711can_align_down (const poly_int<N, Ca> &value, Cb align,
1712 poly_int<N, Ca> *aligned)
1713{
1714 if (!can_align_p (value, align))
1715 return false;
1716 *aligned = value - (value.coeffs[0] & (align - 1));
1717 return true;
1718}
1719
1720/* Return true if we can align A and B up to the smallest multiples of
1721 ALIGN that are >= A and B respectively, and if doing so gives the
1722 same value. */
1723
1724template<unsigned int N, typename Ca, typename Cb, typename Cc>
1725inline bool
1726known_equal_after_align_up (const poly_int<N, Ca> &a,
1727 const poly_int<N, Cb> &b,
1728 Cc align)
1729{
1730 poly_int<N, Ca> aligned_a;
1731 poly_int<N, Cb> aligned_b;
1732 return (can_align_up (a, align, &aligned_a)
1733 && can_align_up (b, align, &aligned_b)
1734 && known_eq (aligned_a, aligned_b));
1735}
1736
1737/* Return true if we can align A and B down to the largest multiples of
1738 ALIGN that are <= A and B respectively, and if doing so gives the
1739 same value. */
1740
1741template<unsigned int N, typename Ca, typename Cb, typename Cc>
1742inline bool
1743known_equal_after_align_down (const poly_int<N, Ca> &a,
1744 const poly_int<N, Cb> &b,
1745 Cc align)
1746{
1747 poly_int<N, Ca> aligned_a;
1748 poly_int<N, Cb> aligned_b;
1749 return (can_align_down (a, align, &aligned_a)
1750 && can_align_down (b, align, &aligned_b)
1751 && known_eq (aligned_a, aligned_b));
1752}
1753
1754/* Assert that we can align VALUE to ALIGN at compile time and return
1755 the smallest multiple of ALIGN that is >= VALUE.
1756
1757 NOTE: When using this function, please add a comment above the call
1758 explaining why we know the non-constant coefficients must already
1759 be a multiple of ALIGN. */
1760
1761template<unsigned int N, typename Ca, typename Cb>
1762inline poly_int<N, Ca>
1763force_align_up (const poly_int<N, Ca> &value, Cb align)
1764{
1765 gcc_checking_assert (can_align_p (value, align));
1766 return value + (-value.coeffs[0] & (align - 1));
1767}
1768
1769/* Assert that we can align VALUE to ALIGN at compile time and return
1770 the largest multiple of ALIGN that is <= VALUE.
1771
1772 NOTE: When using this function, please add a comment above the call
1773 explaining why we know the non-constant coefficients must already
1774 be a multiple of ALIGN. */
1775
1776template<unsigned int N, typename Ca, typename Cb>
1777inline poly_int<N, Ca>
1778force_align_down (const poly_int<N, Ca> &value, Cb align)
1779{
1780 gcc_checking_assert (can_align_p (value, align));
1781 return value - (value.coeffs[0] & (align - 1));
1782}
1783
1784/* Return a value <= VALUE that is a multiple of ALIGN. It will be the
1785 greatest such value for some indeterminate values but not necessarily
1786 for all. */
1787
1788template<unsigned int N, typename Ca, typename Cb>
1789inline poly_int<N, Ca>
1790aligned_lower_bound (const poly_int<N, Ca> &value, Cb align)
1791{
1793 for (unsigned int i = 0; i < N; i++)
1794 /* This form copes correctly with more type combinations than
1795 value.coeffs[i] & -align would. */
1796 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1797 - (value.coeffs[i] & (align - 1))));
1798 return r;
1799}
1800
1801/* Return a value >= VALUE that is a multiple of ALIGN. It will be the
1802 least such value for some indeterminate values but not necessarily
1803 for all. */
1804
1805template<unsigned int N, typename Ca, typename Cb>
1806inline poly_int<N, Ca>
1807aligned_upper_bound (const poly_int<N, Ca> &value, Cb align)
1808{
1810 for (unsigned int i = 0; i < N; i++)
1811 POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1812 + (-value.coeffs[i] & (align - 1))));
1813 return r;
1814}
1815
1816/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1817 down to the largest multiple of ALIGN that is <= VALUE, then divide by
1818 ALIGN.
1819
1820 NOTE: When using this function, please add a comment above the call
1821 explaining why we know the non-constant coefficients must already
1822 be a multiple of ALIGN. */
1823
1824template<unsigned int N, typename Ca, typename Cb>
1825inline poly_int<N, Ca>
1826force_align_down_and_div (const poly_int<N, Ca> &value, Cb align)
1827{
1828 gcc_checking_assert (can_align_p (value, align));
1829
1831 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1832 - (value.coeffs[0] & (align - 1)))
1833 / align));
1834 if (N >= 2)
1835 for (unsigned int i = 1; i < N; i++)
1836 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1837 return r;
1838}
1839
1840/* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1841 up to the smallest multiple of ALIGN that is >= VALUE, then divide by
1842 ALIGN.
1843
1844 NOTE: When using this function, please add a comment above the call
1845 explaining why we know the non-constant coefficients must already
1846 be a multiple of ALIGN. */
1847
1848template<unsigned int N, typename Ca, typename Cb>
1849inline poly_int<N, Ca>
1850force_align_up_and_div (const poly_int<N, Ca> &value, Cb align)
1851{
1852 gcc_checking_assert (can_align_p (value, align));
1853
1855 POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1856 + (-value.coeffs[0] & (align - 1)))
1857 / align));
1858 if (N >= 2)
1859 for (unsigned int i = 1; i < N; i++)
1860 POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1861 return r;
1862}
1863
1864/* Return true if we know at compile time the difference between VALUE
1865 and the equal or preceding multiple of ALIGN. Store the value in
1866 *MISALIGN if so. */
1867
1868template<unsigned int N, typename Ca, typename Cb, typename Cm>
1869inline bool
1870known_misalignment (const poly_int<N, Ca> &value, Cb align, Cm *misalign)
1871{
1872 gcc_checking_assert (align != 0);
1873 if (!can_align_p (value, align))
1874 return false;
1875 *misalign = value.coeffs[0] & (align - 1);
1876 return true;
1877}
1878
1879/* Return X & (Y - 1), asserting that this value is known. Please add
1880 an a comment above callers to this function to explain why the condition
1881 is known to hold. */
1882
1883template<unsigned int N, typename Ca, typename Cb>
1884inline POLY_BINARY_COEFF (Ca, Ca)
1885force_get_misalignment (const poly_int<N, Ca> &a, Cb align)
1886{
1887 gcc_checking_assert (can_align_p (a, align));
1888 return a.coeffs[0] & (align - 1);
1889}
1890
1891/* Return the maximum alignment that A is known to have. Return 0
1892 if A is known to be zero. */
1893
1894template<unsigned int N, typename Ca>
1895inline POLY_BINARY_COEFF (Ca, Ca)
1896known_alignment (const poly_int<N, Ca> &a)
1897{
1898 typedef POLY_BINARY_COEFF (Ca, Ca) C;
1899 C r = a.coeffs[0];
1900 for (unsigned int i = 1; i < N; ++i)
1901 r |= a.coeffs[i];
1902 return r & -r;
1903}
1904
1905/* Return true if we can compute A | B at compile time, storing the
1906 result in RES if so. */
1907
1908template<unsigned int N, typename Ca, typename Cb, typename Cr>
1909inline typename if_nonpoly<Cb, bool>::type
1910can_ior_p (const poly_int<N, Ca> &a, Cb b, Cr *result)
1911{
1912 /* Coefficients 1 and above must be a multiple of something greater
1913 than B. */
1914 typedef POLY_INT_TYPE (Ca) int_type;
1915 if (N >= 2)
1916 for (unsigned int i = 1; i < N; i++)
1917 if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0))
1918 return false;
1919 *result = a;
1920 result->coeffs[0] |= b;
1921 return true;
1922}
1923
1924/* Return true if A is a constant multiple of B, storing the
1925 multiple in *MULTIPLE if so. */
1926
1927template<unsigned int N, typename Ca, typename Cb, typename Cm>
1928inline typename if_nonpoly<Cb, bool>::type
1929constant_multiple_p (const poly_int<N, Ca> &a, Cb b, Cm *multiple)
1930{
1931 typedef POLY_CAST (Ca, Cb) NCa;
1932 typedef POLY_CAST (Cb, Ca) NCb;
1933
1934 /* Do the modulus before the constant check, to catch divide by
1935 zero errors. */
1936 if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
1937 return false;
1938 *multiple = NCa (a.coeffs[0]) / NCb (b);
1939 return true;
1940}
1941
1942template<unsigned int N, typename Ca, typename Cb, typename Cm>
1943inline typename if_nonpoly<Ca, bool>::type
1944constant_multiple_p (Ca a, const poly_int<N, Cb> &b, Cm *multiple)
1945{
1946 typedef POLY_CAST (Ca, Cb) NCa;
1947 typedef POLY_CAST (Cb, Ca) NCb;
1948 typedef POLY_INT_TYPE (Ca) int_type;
1949
1950 /* Do the modulus before the constant check, to catch divide by
1951 zero errors. */
1952 if (NCa (a) % NCb (b.coeffs[0]) != 0
1953 || (a != int_type (0) && !b.is_constant ()))
1954 return false;
1955 *multiple = NCa (a) / NCb (b.coeffs[0]);
1956 return true;
1957}
1958
1959template<unsigned int N, typename Ca, typename Cb, typename Cm>
1960inline bool
1961constant_multiple_p (const poly_int<N, Ca> &a,
1962 const poly_int<N, Cb> &b, Cm *multiple)
1963{
1964 typedef POLY_CAST (Ca, Cb) NCa;
1965 typedef POLY_CAST (Cb, Ca) NCb;
1966 typedef POLY_INT_TYPE (Ca) ICa;
1967 typedef POLY_INT_TYPE (Cb) ICb;
1968 typedef POLY_BINARY_COEFF (Ca, Cb) C;
1969
1970 if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
1971 return false;
1972
1973 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
1974 for (unsigned int i = 1; i < N; ++i)
1975 if (b.coeffs[i] == ICb (0)
1976 ? a.coeffs[i] != ICa (0)
1977 : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
1978 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
1979 return false;
1980
1981 *multiple = r;
1982 return true;
1983}
1984
1985/* Return true if A is a constant multiple of B. */
1986
1987template<unsigned int N, typename Ca, typename Cb>
1988inline typename if_nonpoly<Cb, bool>::type
1989constant_multiple_p (const poly_int<N, Ca> &a, Cb b)
1990{
1991 typedef POLY_CAST (Ca, Cb) NCa;
1992 typedef POLY_CAST (Cb, Ca) NCb;
1993
1994 /* Do the modulus before the constant check, to catch divide by
1995 zero errors. */
1996 if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
1997 return false;
1998 return true;
1999}
2000
2001template<unsigned int N, typename Ca, typename Cb>
2002inline typename if_nonpoly<Ca, bool>::type
2003constant_multiple_p (Ca a, const poly_int<N, Cb> &b)
2004{
2005 typedef POLY_CAST (Ca, Cb) NCa;
2006 typedef POLY_CAST (Cb, Ca) NCb;
2007 typedef POLY_INT_TYPE (Ca) int_type;
2008
2009 /* Do the modulus before the constant check, to catch divide by
2010 zero errors. */
2011 if (NCa (a) % NCb (b.coeffs[0]) != 0
2012 || (a != int_type (0) && !b.is_constant ()))
2013 return false;
2014 return true;
2015}
2016
2017template<unsigned int N, typename Ca, typename Cb>
2018inline bool
2019constant_multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2020{
2021 typedef POLY_CAST (Ca, Cb) NCa;
2022 typedef POLY_CAST (Cb, Ca) NCb;
2023 typedef POLY_INT_TYPE (Ca) ICa;
2024 typedef POLY_INT_TYPE (Cb) ICb;
2025 typedef POLY_BINARY_COEFF (Ca, Cb) C;
2026
2027 if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
2028 return false;
2029
2030 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2031 for (unsigned int i = 1; i < N; ++i)
2032 if (b.coeffs[i] == ICb (0)
2033 ? a.coeffs[i] != ICa (0)
2034 : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2035 || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2036 return false;
2037 return true;
2038}
2039
2040
2041/* Return true if A is a multiple of B. */
2042
2043template<typename Ca, typename Cb>
2044inline typename if_nonpoly2<Ca, Cb, bool>::type
2045multiple_p (Ca a, Cb b)
2046{
2047 return a % b == 0;
2048}
2049
2050/* Return true if A is a (polynomial) multiple of B. */
2051
2052template<unsigned int N, typename Ca, typename Cb>
2053inline typename if_nonpoly<Cb, bool>::type
2054multiple_p (const poly_int<N, Ca> &a, Cb b)
2055{
2056 for (unsigned int i = 0; i < N; ++i)
2057 if (a.coeffs[i] % b != 0)
2058 return false;
2059 return true;
2060}
2061
2062/* Return true if A is a (constant) multiple of B. */
2063
2064template<unsigned int N, typename Ca, typename Cb>
2065inline typename if_nonpoly<Ca, bool>::type
2066multiple_p (Ca a, const poly_int<N, Cb> &b)
2067{
2068 typedef POLY_INT_TYPE (Ca) int_type;
2069
2070 /* Do the modulus before the constant check, to catch divide by
2071 potential zeros. */
2072 return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ());
2073}
2074
2075/* Return true if A is a (polynomial) multiple of B. This handles cases
2076 where either B is constant or the multiple is constant. */
2077
2078template<unsigned int N, typename Ca, typename Cb>
2079inline bool
2080multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2081{
2082 if (b.is_constant ())
2083 return multiple_p (a, b.coeffs[0]);
2084 POLY_BINARY_COEFF (Ca, Ca) tmp;
2085 return constant_multiple_p (a, b, &tmp);
2086}
2087
2088/* Return true if A is a (constant) multiple of B, storing the
2089 multiple in *MULTIPLE if so. */
2090
2091template<typename Ca, typename Cb, typename Cm>
2092inline typename if_nonpoly2<Ca, Cb, bool>::type
2093multiple_p (Ca a, Cb b, Cm *multiple)
2094{
2095 if (a % b != 0)
2096 return false;
2097 *multiple = a / b;
2098 return true;
2099}
2100
2101/* Return true if A is a (polynomial) multiple of B, storing the
2102 multiple in *MULTIPLE if so. */
2103
2104template<unsigned int N, typename Ca, typename Cb, typename Cm>
2105inline typename if_nonpoly<Cb, bool>::type
2106multiple_p (const poly_int<N, Ca> &a, Cb b, poly_int<N, Cm> *multiple)
2107{
2108 if (!multiple_p (a, b))
2109 return false;
2110 for (unsigned int i = 0; i < N; ++i)
2111 multiple->coeffs[i] = a.coeffs[i] / b;
2112 return true;
2113}
2114
2115/* Return true if B is a constant and A is a (constant) multiple of B,
2116 storing the multiple in *MULTIPLE if so. */
2117
2118template<unsigned int N, typename Ca, typename Cb, typename Cm>
2119inline typename if_nonpoly<Ca, bool>::type
2120multiple_p (Ca a, const poly_int<N, Cb> &b, Cm *multiple)
2121{
2122 typedef POLY_CAST (Ca, Cb) NCa;
2123
2124 /* Do the modulus before the constant check, to catch divide by
2125 potential zeros. */
2126 if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ()))
2127 return false;
2128 *multiple = a / b.coeffs[0];
2129 return true;
2130}
2131
2132/* Return true if A is a (polynomial) multiple of B, storing the
2133 multiple in *MULTIPLE if so. This handles cases where either
2134 B is constant or the multiple is constant. */
2135
2136template<unsigned int N, typename Ca, typename Cb, typename Cm>
2137inline bool
2138multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2139 poly_int<N, Cm> *multiple)
2140{
2141 if (b.is_constant ())
2142 return multiple_p (a, b.coeffs[0], multiple);
2143 return constant_multiple_p (a, b, multiple);
2144}
2145
2146/* Return A / B, given that A is known to be a multiple of B. */
2147
2148template<unsigned int N, typename Ca, typename Cb>
2149inline POLY_CONST_RESULT (N, Ca, Cb)
2150exact_div (const poly_int<N, Ca> &a, Cb b)
2151{
2152 typedef POLY_CONST_COEFF (Ca, Cb) C;
2154 for (unsigned int i = 0; i < N; i++)
2155 {
2156 gcc_checking_assert (a.coeffs[i] % b == 0);
2157 POLY_SET_COEFF (C, r, i, a.coeffs[i] / b);
2158 }
2159 return r;
2160}
2161
2162/* Return A / B, given that A is known to be a multiple of B. */
2163
2164template<unsigned int N, typename Ca, typename Cb>
2165inline POLY_POLY_RESULT (N, Ca, Cb)
2166exact_div (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2167{
2168 if (b.is_constant ())
2169 return exact_div (a, b.coeffs[0]);
2170
2171 typedef POLY_CAST (Ca, Cb) NCa;
2172 typedef POLY_CAST (Cb, Ca) NCb;
2173 typedef POLY_BINARY_COEFF (Ca, Cb) C;
2174 typedef POLY_INT_TYPE (Cb) int_type;
2175
2176 gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0);
2177 C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2178 for (unsigned int i = 1; i < N; ++i)
2179 gcc_checking_assert (b.coeffs[i] == int_type (0)
2180 ? a.coeffs[i] == int_type (0)
2181 : (a.coeffs[i] % b.coeffs[i] == 0
2182 && NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r));
2183
2184 return r;
2185}
2186
2187/* Return true if there is some constant Q and polynomial r such that:
2188
2189 (1) a = b * Q + r
2190 (2) |b * Q| <= |a|
2191 (3) |r| < |b|
2192
2193 Store the value Q in *QUOTIENT if so. */
2194
2195template<unsigned int N, typename Ca, typename Cb, typename Cq>
2196inline typename if_nonpoly2<Cb, Cq, bool>::type
2197can_div_trunc_p (const poly_int<N, Ca> &a, Cb b, Cq *quotient)
2198{
2199 typedef POLY_CAST (Ca, Cb) NCa;
2200 typedef POLY_CAST (Cb, Ca) NCb;
2201
2202 /* Do the division before the constant check, to catch divide by
2203 zero errors. */
2204 Cq q = NCa (a.coeffs[0]) / NCb (b);
2205 if (!a.is_constant ())
2206 return false;
2207 *quotient = q;
2208 return true;
2209}
2210
2211template<unsigned int N, typename Ca, typename Cb, typename Cq>
2212inline typename if_nonpoly<Cq, bool>::type
2213can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2214 Cq *quotient)
2215{
2216 /* We can calculate Q from the case in which the indeterminates
2217 are zero. */
2218 typedef POLY_CAST (Ca, Cb) NCa;
2219 typedef POLY_CAST (Cb, Ca) NCb;
2220 typedef POLY_INT_TYPE (Ca) ICa;
2221 typedef POLY_INT_TYPE (Cb) ICb;
2222 typedef POLY_BINARY_COEFF (Ca, Cb) C;
2223 C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2224
2225 /* Check the other coefficients and record whether the division is exact.
2226 The only difficult case is when it isn't. If we require a and b to
2227 ordered wrt zero, there can be no two coefficients of the same value
2228 that have opposite signs. This means that:
2229
2230 |a| = |a0| + |a1 * x1| + |a2 * x2| + ...
2231 |b| = |b0| + |b1 * x1| + |b2 * x2| + ...
2232
2233 The Q we've just calculated guarantees:
2234
2235 |b0 * Q| <= |a0|
2236 |a0 - b0 * Q| < |b0|
2237
2238 and so:
2239
2240 (2) |b * Q| <= |a|
2241
2242 is satisfied if:
2243
2244 |bi * xi * Q| <= |ai * xi|
2245
2246 for each i in [1, N]. This is trivially true when xi is zero.
2247 When it isn't we need:
2248
2249 (2') |bi * Q| <= |ai|
2250
2251 r is calculated as:
2252
2253 r = r0 + r1 * x1 + r2 * x2 + ...
2254 where ri = ai - bi * Q
2255
2256 Restricting to ordered a and b also guarantees that no two ris
2257 have opposite signs, so we have:
2258
2259 |r| = |r0| + |r1 * x1| + |r2 * x2| + ...
2260
2261 We know from the calculation of Q that |r0| < |b0|, so:
2262
2263 (3) |r| < |b|
2264
2265 is satisfied if:
2266
2267 (3') |ai - bi * Q| <= |bi|
2268
2269 for each i in [1, N]. */
2270 bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0;
2271 for (unsigned int i = 1; i < N; ++i)
2272 {
2273 if (b.coeffs[i] == ICb (0))
2274 {
2275 /* For bi == 0 we simply need: (3') |ai| == 0. */
2276 if (a.coeffs[i] != ICa (0))
2277 return false;
2278 }
2279 else
2280 {
2281 /* The only unconditional arithmetic that we can do on ai,
2282 bi and Q is ai / bi and ai % bi. (ai == minimum int and
2283 bi == -1 would be UB in the caller.) Anything else runs
2284 the risk of overflow. */
2285 auto qi = NCa (a.coeffs[i]) / NCb (b.coeffs[i]);
2286 auto ri = NCa (a.coeffs[i]) % NCb (b.coeffs[i]);
2287 /* (2') and (3') are satisfied when ai /[trunc] bi == q.
2288 So is the stricter condition |ai - bi * Q| < |bi|. */
2289 if (qi == q)
2290 rem_p |= (ri != 0);
2291 /* The only other case is when:
2292
2293 |bi * Q| + |bi| = |ai| (for (2'))
2294 and |ai - bi * Q| = |bi| (for (3'))
2295
2296 The first is equivalent to |bi|(|Q| + 1) == |ai|.
2297 The second requires ai == bi * (Q + 1) or ai == bi * (Q - 1). */
2298 else if (ri != 0)
2299 return false;
2300 else if (q <= 0 && qi < q && qi + 1 == q)
2301 ;
2302 else if (q >= 0 && qi > q && qi - 1 == q)
2303 ;
2304 else
2305 return false;
2306 }
2307 }
2308
2309 /* If the division isn't exact, require both values to be ordered wrt 0,
2310 so that we can guarantee conditions (2) and (3) for all indeterminate
2311 values. */
2312 if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0))))
2313 return false;
2314
2315 *quotient = q;
2316 return true;
2317}
2318
2319/* Likewise, but also store r in *REMAINDER. */
2320
2321template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2322inline typename if_nonpoly<Cq, bool>::type
2323can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2324 Cq *quotient, Cr *remainder)
2325{
2326 if (!can_div_trunc_p (a, b, quotient))
2327 return false;
2328 *remainder = a - *quotient * b;
2329 return true;
2330}
2331
2332/* Return true if there is some polynomial q and constant R such that:
2333
2334 (1) a = B * q + R
2335 (2) |B * q| <= |a|
2336 (3) |R| < |B|
2337
2338 Store the value q in *QUOTIENT if so. */
2339
2340template<unsigned int N, typename Ca, typename Cb, typename Cq>
2341inline typename if_nonpoly<Cb, bool>::type
2342can_div_trunc_p (const poly_int<N, Ca> &a, Cb b,
2343 poly_int<N, Cq> *quotient)
2344{
2345 /* The remainder must be constant. */
2346 for (unsigned int i = 1; i < N; ++i)
2347 if (a.coeffs[i] % b != 0)
2348 return false;
2349 for (unsigned int i = 0; i < N; ++i)
2350 quotient->coeffs[i] = a.coeffs[i] / b;
2351 return true;
2352}
2353
2354/* Likewise, but also store R in *REMAINDER. */
2355
2356template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2357inline typename if_nonpoly<Cb, bool>::type
2358can_div_trunc_p (const poly_int<N, Ca> &a, Cb b,
2359 poly_int<N, Cq> *quotient, Cr *remainder)
2360{
2361 if (!can_div_trunc_p (a, b, quotient))
2362 return false;
2363 *remainder = a.coeffs[0] % b;
2364 return true;
2365}
2366
2367/* Return true if we can compute A / B at compile time, rounding towards zero.
2368 Store the result in QUOTIENT if so.
2369
2370 This handles cases in which either B is constant or the result is
2371 constant. */
2372
2373template<unsigned int N, typename Ca, typename Cb, typename Cq>
2374inline bool
2375can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2376 poly_int<N, Cq> *quotient)
2377{
2378 if (b.is_constant ())
2379 return can_div_trunc_p (a, b.coeffs[0], quotient);
2380 if (!can_div_trunc_p (a, b, &quotient->coeffs[0]))
2381 return false;
2382 for (unsigned int i = 1; i < N; ++i)
2383 quotient->coeffs[i] = 0;
2384 return true;
2385}
2386
2387/* Return true if there is some constant Q and polynomial r such that:
2388
2389 (1) a = b * Q + r
2390 (2) |a| <= |b * Q|
2391 (3) |r| < |b|
2392
2393 Store the value Q in *QUOTIENT if so. */
2394
2395template<unsigned int N, typename Ca, typename Cb, typename Cq>
2396inline typename if_nonpoly<Cq, bool>::type
2397can_div_away_from_zero_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2398 Cq *quotient)
2399{
2400 if (!can_div_trunc_p (a, b, quotient))
2401 return false;
2402 if (maybe_ne (*quotient * b, a))
2403 *quotient += (*quotient < 0 ? -1 : 1);
2404 return true;
2405}
2406
2407/* Use print_dec to print VALUE to FILE, where SGN is the sign
2408 of the values. */
2409
2410template<unsigned int N, typename C>
2411void
2412print_dec (const poly_int<N, C> &value, FILE *file, signop sgn)
2413{
2414 if (value.is_constant ())
2415 print_dec (value.coeffs[0], file, sgn);
2416 else
2417 {
2418 fprintf (file, "[");
2419 for (unsigned int i = 0; i < N; ++i)
2420 {
2421 print_dec (value.coeffs[i], file, sgn);
2422 fputc (i == N - 1 ? ']' : ',', file);
2423 }
2424 }
2425}
2426
2427/* Likewise without the signop argument, for coefficients that have an
2428 inherent signedness. */
2429
2430template<unsigned int N, typename C>
2431void
2432print_dec (const poly_int<N, C> &value, FILE *file)
2433{
2435 print_dec (value, file,
2437}
2438
2439/* Use print_hex to print VALUE to FILE. */
2440
2441template<unsigned int N, typename C>
2442void
2443print_hex (const poly_int<N, C> &value, FILE *file)
2444{
2445 if (value.is_constant ())
2446 print_hex (value.coeffs[0], file);
2447 else
2448 {
2449 fprintf (file, "[");
2450 for (unsigned int i = 0; i < N; ++i)
2451 {
2452 print_hex (value.coeffs[i], file);
2453 fputc (i == N - 1 ? ']' : ',', file);
2454 }
2455 }
2456}
2457
2458/* Helper for calculating the distance between two points P1 and P2,
2459 in cases where known_le (P1, P2). T1 and T2 are the types of the
2460 two positions, in either order. The coefficients of P2 - P1 have
2461 type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2
2462 have C++ primitive type, otherwise P2 - P1 has its usual
2463 wide-int-based type.
2464
2465 The actual subtraction should look something like this:
2466
2467 typedef poly_span_traits<T1, T2> span_traits;
2468 span_traits::cast (P2) - span_traits::cast (P1)
2469
2470 Applying the cast before the subtraction avoids undefined overflow
2471 for signed T1 and T2.
2472
2473 The implementation of the cast tries to avoid unnecessary arithmetic
2474 or copying. */
2475template<typename T1, typename T2,
2476 typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2),
2477 unsigned HOST_WIDE_INT)>
2478struct poly_span_traits
2479{
2480 template<typename T>
2481 static const T &cast (const T &x) { return x; }
2482};
2483
2484template<typename T1, typename T2>
2485struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT>
2486{
2487 template<typename T>
2489 cast (const T &x) { return x; }
2490
2491 template<unsigned int N, typename T>
2493 cast (const poly_int<N, T> &x) { return x; }
2494};
2495
2496/* Return true if SIZE represents a known size, assuming that all-ones
2497 indicates an unknown size. */
2498
2499template<typename T>
2500inline bool
2501known_size_p (const T &a)
2502{
2503 return maybe_ne (a, POLY_INT_TYPE (T) (-1));
2504}
2505
2506/* Return true if range [POS, POS + SIZE) might include VAL.
2507 SIZE can be the special value -1, in which case the range is
2508 open-ended. */
2509
2510template<typename T1, typename T2, typename T3>
2511inline bool
2512maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2513{
2514 typedef poly_span_traits<T1, T2> start_span;
2515 typedef poly_span_traits<T3, T3> size_span;
2516 if (known_lt (val, pos))
2517 return false;
2518 if (!known_size_p (size))
2519 return true;
2522 && maybe_lt (val, pos))
2523 /* In this case we don't know whether VAL >= POS is true at compile
2524 time, so we can't prove that VAL >= POS + SIZE. */
2525 return true;
2526 return maybe_lt (start_span::cast (val) - start_span::cast (pos),
2527 size_span::cast (size));
2528}
2529
2530/* Return true if range [POS, POS + SIZE) is known to include VAL.
2531 SIZE can be the special value -1, in which case the range is
2532 open-ended. */
2533
2534template<typename T1, typename T2, typename T3>
2535inline bool
2536known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2537{
2538 typedef poly_span_traits<T1, T2> start_span;
2539 typedef poly_span_traits<T3, T3> size_span;
2540 return (known_size_p (size)
2541 && known_ge (val, pos)
2542 && known_lt (start_span::cast (val) - start_span::cast (pos),
2543 size_span::cast (size)));
2544}
2545
2546/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2547 might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which
2548 case the range is open-ended. */
2549
2550template<typename T1, typename T2, typename T3, typename T4>
2551inline bool
2552ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1,
2553 const T3 &pos2, const T4 &size2)
2554{
2555 if (maybe_in_range_p (pos2, pos1, size1))
2556 return maybe_ne (size2, POLY_INT_TYPE (T4) (0));
2557 if (maybe_in_range_p (pos1, pos2, size2))
2558 return maybe_ne (size1, POLY_INT_TYPE (T2) (0));
2559 return false;
2560}
2561
2562/* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2563 are known to overlap. SIZE1 and/or SIZE2 can be the special value -1,
2564 in which case the range is open-ended. */
2565
2566template<typename T1, typename T2, typename T3, typename T4>
2567inline bool
2568ranges_known_overlap_p (const T1 &pos1, const T2 &size1,
2569 const T3 &pos2, const T4 &size2)
2570{
2571 typedef poly_span_traits<T1, T3> start_span;
2572 typedef poly_span_traits<T2, T2> size1_span;
2573 typedef poly_span_traits<T4, T4> size2_span;
2574 /* known_gt (POS1 + SIZE1, POS2) [infinite precision]
2575 --> known_gt (SIZE1, POS2 - POS1) [infinite precision]
2576 --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision]
2577 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative
2578 --> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))).
2579
2580 Using the saturating subtraction enforces that SIZE1 must be
2581 nonzero, since known_gt (0, x) is false for all nonnegative x.
2582 If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing
2583 indeterminate number I makes the unsaturated condition easier to
2584 satisfy, so using a saturated coefficient of zero tests the case in
2585 which the indeterminate is zero (the minimum value). */
2586 return (known_size_p (size1)
2587 && known_size_p (size2)
2588 && known_lt (start_span::cast (pos2)
2589 - start_span::cast (lower_bound (pos1, pos2)),
2590 size1_span::cast (size1))
2591 && known_lt (start_span::cast (pos1)
2592 - start_span::cast (lower_bound (pos1, pos2)),
2593 size2_span::cast (size2)));
2594}
2595
2596/* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of
2597 [POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1,
2598 in which case the range is open-ended. */
2599
2600template<typename T1, typename T2, typename T3, typename T4>
2601inline bool
2602known_subrange_p (const T1 &pos1, const T2 &size1,
2603 const T3 &pos2, const T4 &size2)
2604{
2605 typedef typename poly_int_traits<T2>::coeff_type C2;
2606 typedef poly_span_traits<T1, T3> start_span;
2607 typedef poly_span_traits<T2, T4> size_span;
2608 return (known_gt (size1, POLY_INT_TYPE (T2) (0))
2610 || known_size_p (size1))
2611 && known_size_p (size2)
2612 && known_ge (pos1, pos2)
2613 && known_le (size1, size2)
2614 && known_le (start_span::cast (pos1) - start_span::cast (pos2),
2615 size_span::cast (size2) - size_span::cast (size1)));
2616}
2617
2618/* Return true if the endpoint of the range [POS, POS + SIZE) can be
2619 stored in a T, or if SIZE is the special value -1, which makes the
2620 range open-ended. */
2621
2622template<typename T>
2623inline typename if_nonpoly<T, bool>::type
2624endpoint_representable_p (const T &pos, const T &size)
2625{
2626 return (!known_size_p (size)
2627 || pos <= poly_coeff_traits<T>::max_value - size);
2628}
2629
2630template<unsigned int N, typename C>
2631inline bool
2632endpoint_representable_p (const poly_int<N, C> &pos,
2633 const poly_int<N, C> &size)
2634{
2635 if (known_size_p (size))
2636 for (unsigned int i = 0; i < N; ++i)
2637 if (pos.coeffs[i] > poly_coeff_traits<C>::max_value - size.coeffs[i])
2638 return false;
2639 return true;
2640}
2641
2642template<unsigned int N, typename C>
2643void
2645{
2646}
2647
2648template<unsigned int N, typename C>
2649void
2651{
2652}
2653
2654template<unsigned int N, typename C>
2655void
2657{
2658}
2659
2660#undef POLY_SET_COEFF
2661#undef POLY_INT_TYPE
2662#undef POLY_BINARY_COEFF
2663#undef CONST_CONST_RESULT
2664#undef POLY_CONST_RESULT
2665#undef CONST_POLY_RESULT
2666#undef POLY_POLY_RESULT
2667#undef POLY_CONST_COEFF
2668#undef CONST_POLY_COEFF
2669#undef POLY_POLY_COEFF
2670
2671#endif
Definition poly-int.h:374
C to_constant() const
Definition poly-int.h:586
poly_int< N, unsigned HOST_WIDE_INT > force_uhwi() const
Definition poly-int.h:673
bool to_shwi(poly_int< N, HOST_WIDE_INT > *) const
Definition poly-int.h:628
poly_int< N, HOST_WIDE_INT > force_shwi() const
Definition poly-int.h:660
bool is_constant() const
Definition poly-int.h:553
static poly_int< N, C > from(const poly_int< N, Ca > &, signop)
Definition poly-int.h:614
constexpr poly_int(poly_int_hungry, const C0 &, const Cs &...)
poly_int & operator+=(const poly_int< N, Ca > &)
if_lossless< T, C, bool >::type is_constant(T *) const
Definition poly-int.h:568
if_nonpoly< Ca, poly_int >::type & operator*=(const Ca &)
Definition poly-int.h:533
C coeffs[N]
Definition poly-int.h:429
poly_int & operator<<=(unsigned int)
Definition poly-int.h:542
bool to_uhwi(poly_int< N, unsigned HOST_WIDE_INT > *) const
Definition poly-int.h:645
poly_int & operator-=(const poly_int< N, Ca > &)
poly_int(const poly_int< N, Ca > &)
Definition poly-int.h:442
constexpr poly_int(poly_int_full, const Cs &...)
poly_int()=default
poly_int(const poly_int &)=default
constexpr poly_int(const Cs &...)
static poly_int< N, C > from(const poly_int< N, Ca > &, unsigned int, signop)
Definition poly-int.h:599
poly_int & operator=(const poly_int &)=default
Definition wide-int.h:1967
void(* gt_pointer_operator)(void *, void *, void *)
Definition coretypes.h:465
dump_flags_t operator~(dump_flags_t flags)
Definition dumpfile.h:226
#define CHAR_BIT
Definition genautomata.cc:120
static type_p type(options_p *optsp, bool nested)
Definition gengtype-parse.cc:883
static struct token T
Definition gengtype-parse.cc:45
#define N
Definition gensupport.cc:202
void gt_ggc_mx(const char *&x)
Definition ggc-page.cc:1518
void gt_pch_nx(const char *)
Definition ggc.h:341
#define INT_MAX
Definition glimits.h:85
HOST_WIDE_INT gcd(HOST_WIDE_INT a, HOST_WIDE_INT b)
Definition hwint.cc:132
HOST_WIDE_INT least_common_multiple(HOST_WIDE_INT a, HOST_WIDE_INT b)
Definition hwint.cc:187
HOST_WIDE_INT sext_hwi(HOST_WIDE_INT src, unsigned int prec)
Definition hwint.h:299
Definition double-int.h:439
poly_int< N, hwi_with_prec > uhwi(const poly_int< N, unsigned HOST_WIDE_INT > &a, unsigned int precision)
Definition poly-int.h:729
poly_int< N, C > r
Definition poly-int.h:744
UNARY_PREDICATE fits_shwi_p(const T &)
UNARY_FUNCTION zext(const T &, unsigned int)
BINARY_FUNCTION sub(const T1 &, const T2 &)
UNARY_FUNCTION neg(const T &)
Ca unsigned int precision
Definition poly-int.h:742
static void accumulate_overflow(overflow_type &, overflow_type)
Definition wide-int.h:4064
Ca & a
Definition poly-int.h:741
UNARY_PREDICATE fits_uhwi_p(const T &)
BINARY_FUNCTION mul(const T1 &, const T2 &)
UNARY_FUNCTION sext(const T &, unsigned int)
SHIFT_FUNCTION lshift(const T1 &, const T2 &)
BINARY_FUNCTION add(const T1 &, const T2 &)
i
Definition poly-int.h:746
overflow_type
Definition wide-int.h:377
poly_int< N, hwi_with_prec > shwi(const poly_int< N, HOST_WIDE_INT > &a, unsigned int precision)
Definition poly-int.h:717
#define known_eq(A, B)
#define POLY_CONST_COEFF(C1, T2)
Definition poly-int.h:299
#define known_ge(A, B)
#define CONST_POLY_COEFF(T1, C2)
Definition poly-int.h:303
#define POLY_SET_COEFF(C, RES, I, VALUE)
Definition poly-int.h:351
#define POLY_POLY_RESULT(N, C1, C2)
Definition poly-int.h:308
poly_int< N, C > r
Definition poly-int.h:770
#define POLY_CAST(C1, C2)
Definition poly-int.h:326
NCa(a.coeffs[i])+b.coeffs[i])
#define POLY_INT_TYPE(T)
Definition poly-int.h:336
i
Definition poly-int.h:772
#define POLY_BINARY_COEFF(T1, T2)
Definition poly-int.h:330
#define POLY_CONST_RESULT(N, C1, T2)
Definition poly-int.h:312
#define known_le(A, B)
#define CONST_CONST_RESULT(N, T1, T2)
Definition poly-int.h:320
#define known_lt(A, B)
#define RANK(X)
Definition poly-int.h:156
#define POLY_POLY_COEFF(C1, C2)
Definition poly-int.h:293
if_nonpoly< Ca, bool >::type coeffs_in_range_p(const Ca &a, const Cb &b, const Cc &c)
Definition poly-int.h:697
#define known_gt(A, B)
Ca const poly_int< N, Cb > & b
Definition poly-int.h:767
Ca & a
Definition poly-int.h:766
#define CONST_POLY_RESULT(N, T1, C2)
Definition poly-int.h:316
fputc('\n', stderr)
signop
Definition signop.h:28
@ UNSIGNED
Definition signop.h:30
@ SIGNED
Definition signop.h:29
sreal operator<<(const sreal &a, int exp)
Definition sreal.h:187
T3 type
Definition poly-int.h:175
Definition poly-int.h:171
T3 type
Definition poly-int.h:229
Definition poly-int.h:225
T2 type
Definition poly-int.h:217
Definition poly-int.h:213
T2 type
Definition poly-int.h:240
Definition poly-int.h:236
Definition poly-int.h:129
static const int result_kind
Definition poly-int.h:158
static const bool lossless_p
Definition poly-int.h:144
int int_type
Definition poly-int.h:116
int int_type
Definition poly-int.h:89
Definition poly-int.h:66
Definition poly-int.h:361
Definition poly-int.h:366
Definition poly-int.h:362
poly_coeff_traits< C >::int_type int_type
Definition poly-int.h:206
C coeff_type
Definition poly-int.h:205
Definition poly-int.h:194
T coeff_type
Definition poly-int.h:197
static const bool is_poly
Definition poly-int.h:195
poly_coeff_traits< T >::int_type int_type
Definition poly-int.h:198
static const unsigned int num_coeffs
Definition poly-int.h:196
HOST_WIDE_INT type
Definition poly-int.h:264
type cast
Definition poly-int.h:267
type cast
Definition poly-int.h:277
unsigned HOST_WIDE_INT type
Definition poly-int.h:274
const T1 & cast
Definition poly-int.h:287
typedef WI_BINARY_RESULT(T1, T2) type
Definition poly-int.h:258
Definition gengtype.h:252
Definition wide-int.h:427
Definition wide-int.h:2043
#define gcc_unreachable()
Definition system.h:848
#define true
Definition system.h:894
#define false
Definition system.h:895
#define MIN(X, Y)
Definition system.h:392
#define STATIC_ASSERT(X)
Definition system.h:871
#define gcc_checking_assert(EXPR)
Definition system.h:828
#define MAX(X, Y)
Definition system.h:393
comp_cost operator+(comp_cost cost1, comp_cost cost2)
Definition tree-ssa-loop-ivopts.cc:269
comp_cost operator-(comp_cost cost1, comp_cost cost2)
Definition tree-ssa-loop-ivopts.cc:282
void print_hex(const wide_int_ref &val, char *buf)
Definition wide-int-print.cc:141
void print_dec(const wide_int_ref &wi, char *buf, signop sgn)
Definition wide-int-print.cc:34
#define WI_BINARY_RESULT(T1, T2)
Definition wide-int.h:289
#define WI_UNARY_RESULT(T)
Definition wide-int.h:315
#define WIDE_INT_MAX_PRECISION
Definition wide-int.h:253