Line data Source code
1 : /* Polynomial integer classes.
2 : Copyright (C) 2014-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : /* This file provides a representation of sizes and offsets whose exact
21 : values depend on certain runtime properties. The motivating example
22 : is the Arm SVE ISA, in which the number of vector elements is only
23 : known at runtime. See doc/poly-int.texi for more details.
24 :
25 : Tests for poly-int.h are located in testsuite/gcc.dg/plugin,
26 : since they are too expensive (in terms of binary size) to be
27 : included as selftests. */
28 :
29 : #ifndef HAVE_POLY_INT_H
30 : #define HAVE_POLY_INT_H
31 :
32 : template<unsigned int N, typename T> 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. */
65 : template<typename T, wi::precision_type = wi::int_traits<T>::precision_type>
66 : struct poly_coeff_traits;
67 :
68 : template<typename T>
69 : struct 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 :
85 : template<typename T>
86 : struct 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 :
98 : template<typename T>
99 : struct 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 :
112 : template<typename T>
113 : struct 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. */
127 : template<typename T1, typename T2>
128 : struct poly_coeff_pair_traits
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. */
144 : static const bool lossless_p = (poly_coeff_traits<T1>::signedness
145 : == poly_coeff_traits<T2>::signedness
146 : ? (poly_coeff_traits<T1>::precision
147 : >= poly_coeff_traits<T2>::precision)
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. */
169 : template<typename T1, typename T2, typename T3,
170 : bool lossless_p = poly_coeff_pair_traits<T1, T2>::lossless_p>
171 : struct if_lossless;
172 : template<typename T1, typename T2, typename T3>
173 : struct 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. */
192 : template<typename T>
193 : struct poly_int_traits
194 : {
195 : static const bool is_poly = false;
196 : static const unsigned int num_coeffs = 1;
197 : typedef T coeff_type;
198 : typedef typename poly_coeff_traits<T>::int_type int_type;
199 : };
200 : template<unsigned int N, typename C>
201 : struct poly_int_traits<poly_int<N, C> >
202 : {
203 : static const bool is_poly = true;
204 : static const unsigned int num_coeffs = N;
205 : typedef C coeff_type;
206 : typedef typename poly_coeff_traits<C>::int_type int_type;
207 : };
208 :
209 : /* SFINAE class that makes T2 available as "type" if T1 is a non-polynomial
210 : type. */
211 : template<typename T1, typename T2 = T1,
212 : bool is_poly = poly_int_traits<T1>::is_poly>
213 : struct if_nonpoly {};
214 : template<typename T1, typename T2>
215 : struct 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. */
222 : template<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>
225 : struct if_nonpoly2 {};
226 : template<typename T1, typename T2, typename T3>
227 : struct 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. */
234 : template<typename T1, typename T2 = T1,
235 : bool is_poly = poly_int_traits<T1>::is_poly>
236 : struct if_poly {};
237 : template<typename T1, typename T2>
238 : struct 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. */
256 : template<typename T1, typename T2 = T1,
257 : int result_kind = poly_coeff_pair_traits<T1, T2>::result_kind>
258 : struct poly_result;
259 :
260 : /* Promote pair to HOST_WIDE_INT. */
261 : template<typename T1, typename T2>
262 : struct 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. */
271 : template<typename T1, typename T2>
272 : struct 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. */
281 : template<typename T1, typename T2>
282 : struct 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 : /* Number of bits needed to represent maximum value of
358 : NUM_POLY_INT_COEFFS defined by any target. */
359 : #define MAX_NUM_POLY_INT_COEFFS_BITS 2
360 :
361 : /* poly_int_full and poly_int_hungry are used internally within poly_int
362 : for delegated initializers. poly_int_full indicates that a parameter
363 : pack has enough elements to initialize every coefficient. poly_int_hungry
364 : indicates that at least one extra zero must be added. */
365 : struct poly_int_full {};
366 : struct poly_int_hungry {};
367 :
368 : /* poly_int_fullness<B>::type is poly_int_full when B is true and
369 : poly_int_hungry when B is false. */
370 : template<bool> struct poly_int_fullness;
371 : template<> struct poly_int_fullness<false> { using type = poly_int_hungry; };
372 : template<> struct poly_int_fullness<true> { using type = poly_int_full; };
373 :
374 : /* A class containing polynomial integers. The polynomial has N coefficients
375 : of type C, and N - 1 indeterminates. */
376 : template<unsigned int N, typename C>
377 : class poly_int
378 : {
379 : public:
380 13829301641 : poly_int () = default;
381 689468 : poly_int (const poly_int &) = default;
382 :
383 : template<typename Ca>
384 : poly_int (const poly_int<N, Ca> &);
385 :
386 : template<typename ...Cs>
387 : constexpr poly_int (const Cs &...);
388 :
389 492180636 : poly_int &operator = (const poly_int &) = default;
390 :
391 : template<typename Ca>
392 : poly_int &operator = (const poly_int<N, Ca> &);
393 : template<typename Ca>
394 : typename if_nonpoly<Ca, poly_int>::type &operator = (const Ca &);
395 :
396 : template<typename Ca>
397 : poly_int &operator += (const poly_int<N, Ca> &);
398 : template<typename Ca>
399 : typename if_nonpoly<Ca, poly_int>::type &operator += (const Ca &);
400 :
401 : template<typename Ca>
402 : poly_int &operator -= (const poly_int<N, Ca> &);
403 : template<typename Ca>
404 : typename if_nonpoly<Ca, poly_int>::type &operator -= (const Ca &);
405 :
406 : template<typename Ca>
407 : typename if_nonpoly<Ca, poly_int>::type &operator *= (const Ca &);
408 :
409 : poly_int &operator <<= (unsigned int);
410 :
411 : bool is_constant () const;
412 :
413 : template<typename T>
414 : typename if_lossless<T, C, bool>::type is_constant (T *) const;
415 :
416 : C to_constant () const;
417 :
418 : template<typename Ca>
419 : static poly_int<N, C> from (const poly_int<N, Ca> &, unsigned int,
420 : signop);
421 : template<typename Ca>
422 : static poly_int<N, C> from (const poly_int<N, Ca> &, signop);
423 :
424 : bool to_shwi (poly_int<N, HOST_WIDE_INT> *) const;
425 : bool to_uhwi (poly_int<N, unsigned HOST_WIDE_INT> *) const;
426 : poly_int<N, HOST_WIDE_INT> force_shwi () const;
427 : poly_int<N, unsigned HOST_WIDE_INT> force_uhwi () const;
428 :
429 : #if POLY_INT_CONVERSION
430 : operator C () const;
431 : #endif
432 :
433 : C coeffs[N];
434 :
435 : private:
436 : template<typename ...Cs>
437 : constexpr poly_int (poly_int_full, const Cs &...);
438 :
439 : template<typename C0, typename ...Cs>
440 : constexpr poly_int (poly_int_hungry, const C0 &, const Cs &...);
441 : };
442 :
443 : template<unsigned int N, typename C>
444 : template<typename Ca>
445 : inline
446 41483703972 : poly_int<N, C>::poly_int (const poly_int<N, Ca> &a)
447 : {
448 52652780968 : for (unsigned int i = 0; i < N; i++)
449 16741644680 : POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
450 10193169218 : }
451 :
452 : template<unsigned int N, typename C>
453 : template<typename ...Cs>
454 : inline constexpr
455 26839709731 : poly_int<N, C>::poly_int (const Cs &... cs)
456 : : poly_int (typename poly_int_fullness<sizeof... (Cs) >= N>::type (),
457 22104292679 : cs...) {}
458 :
459 : /* Initialize with c0, cs..., and some trailing zeros. */
460 : template<unsigned int N, typename C>
461 : template<typename C0, typename ...Cs>
462 : inline constexpr
463 : poly_int<N, C>::poly_int (poly_int_hungry, const C0 &c0, const Cs &... cs)
464 : : poly_int (c0, cs..., wi::ints_for<C>::zero (c0)) {}
465 :
466 : /* Initialize with cs... directly, casting where necessary. */
467 : template<unsigned int N, typename C>
468 : template<typename ...Cs>
469 : inline constexpr
470 16177626017 : poly_int<N, C>::poly_int (poly_int_full, const Cs &... cs)
471 15222012311 : : coeffs { (typename poly_coeff_traits<C>::
472 5312913119 : template init_cast<Cs>::type (cs))... } {}
473 :
474 : template<unsigned int N, typename C>
475 : template<typename Ca>
476 : inline poly_int<N, C>&
477 3495725664 : poly_int<N, C>::operator = (const poly_int<N, Ca> &a)
478 : {
479 7081733969 : for (unsigned int i = 0; i < N; i++)
480 3755707255 : POLY_SET_COEFF (C, *this, i, a.coeffs[i]);
481 5506420 : return *this;
482 : }
483 :
484 : template<unsigned int N, typename C>
485 : template<typename Ca>
486 : inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
487 8911263192 : poly_int<N, C>::operator = (const Ca &a)
488 : {
489 9799538936 : POLY_SET_COEFF (C, *this, 0, a);
490 : if (N >= 2)
491 : for (unsigned int i = 1; i < N; i++)
492 : POLY_SET_COEFF (C, *this, i, wi::ints_for<C>::zero (this->coeffs[0]));
493 1719234654 : return *this;
494 : }
495 :
496 : template<unsigned int N, typename C>
497 : template<typename Ca>
498 : inline poly_int<N, C>&
499 4948217039 : poly_int<N, C>::operator += (const poly_int<N, Ca> &a)
500 : {
501 6004746109 : for (unsigned int i = 0; i < N; i++)
502 5960099109 : this->coeffs[i] += a.coeffs[i];
503 10358 : return *this;
504 : }
505 :
506 : template<unsigned int N, typename C>
507 : template<typename Ca>
508 : inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
509 2379110375 : poly_int<N, C>::operator += (const Ca &a)
510 : {
511 2373647288 : this->coeffs[0] += a;
512 73099 : return *this;
513 : }
514 :
515 : template<unsigned int N, typename C>
516 : template<typename Ca>
517 : inline poly_int<N, C>&
518 39179227 : poly_int<N, C>::operator -= (const poly_int<N, Ca> &a)
519 : {
520 1387991387 : for (unsigned int i = 0; i < N; i++)
521 1430046060 : this->coeffs[i] -= a.coeffs[i];
522 : return *this;
523 : }
524 :
525 : template<unsigned int N, typename C>
526 : template<typename Ca>
527 : inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
528 33657454 : poly_int<N, C>::operator -= (const Ca &a)
529 : {
530 27758725 : this->coeffs[0] -= a;
531 7847303 : return *this;
532 : }
533 :
534 : template<unsigned int N, typename C>
535 : template<typename Ca>
536 : inline typename if_nonpoly<Ca, poly_int<N, C> >::type &
537 706584374 : poly_int<N, C>::operator *= (const Ca &a)
538 : {
539 704964150 : for (unsigned int i = 0; i < N; i++)
540 704964150 : this->coeffs[i] *= a;
541 : return *this;
542 : }
543 :
544 : template<unsigned int N, typename C>
545 : inline poly_int<N, C>&
546 1292636351 : poly_int<N, C>::operator <<= (unsigned int a)
547 : {
548 1292636351 : for (unsigned int i = 0; i < N; i++)
549 1292636351 : this->coeffs[i] <<= a;
550 : return *this;
551 : }
552 :
553 : /* Return true if the polynomial value is a compile-time constant. */
554 :
555 : template<unsigned int N, typename C>
556 : inline bool
557 : poly_int<N, C>::is_constant () const
558 : {
559 : if (N >= 2)
560 : for (unsigned int i = 1; i < N; i++)
561 : if (this->coeffs[i] != 0)
562 : return false;
563 : return true;
564 : }
565 :
566 : /* Return true if the polynomial value is a compile-time constant,
567 : storing its value in CONST_VALUE if so. */
568 :
569 : template<unsigned int N, typename C>
570 : template<typename T>
571 : inline typename if_lossless<T, C, bool>::type
572 746418670 : poly_int<N, C>::is_constant (T *const_value) const
573 : {
574 : if (is_constant ())
575 : {
576 877389684 : *const_value = this->coeffs[0];
577 : return true;
578 : }
579 : return false;
580 : }
581 :
582 : /* Return the value of a polynomial that is already known to be a
583 : compile-time constant.
584 :
585 : NOTE: When using this function, please add a comment above the call
586 : explaining why we know the value is constant in that context. */
587 :
588 : template<unsigned int N, typename C>
589 : inline C
590 93000413 : poly_int<N, C>::to_constant () const
591 : {
592 : gcc_checking_assert (is_constant ());
593 91116546 : return this->coeffs[0];
594 : }
595 :
596 : /* Convert X to a wide_int-based polynomial in which each coefficient
597 : has BITSIZE bits. If X's coefficients are smaller than BITSIZE,
598 : extend them according to SGN. */
599 :
600 : template<unsigned int N, typename C>
601 : template<typename Ca>
602 : inline poly_int<N, C>
603 1316378 : poly_int<N, C>::from (const poly_int<N, Ca> &a, unsigned int bitsize,
604 : signop sgn)
605 : {
606 2632756 : poly_int<N, C> r;
607 2632756 : for (unsigned int i = 0; i < N; i++)
608 1316378 : POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], bitsize, sgn));
609 1316378 : return r;
610 : }
611 :
612 : /* Convert X to a fixed_wide_int-based polynomial, extending according
613 : to SGN. */
614 :
615 : template<unsigned int N, typename C>
616 : template<typename Ca>
617 : inline poly_int<N, C>
618 1260749316 : poly_int<N, C>::from (const poly_int<N, Ca> &a, signop sgn)
619 : {
620 1260749316 : poly_int<N, C> r;
621 2521498632 : for (unsigned int i = 0; i < N; i++)
622 1260749316 : POLY_SET_COEFF (C, r, i, C::from (a.coeffs[i], sgn));
623 1260749316 : return r;
624 : }
625 :
626 : /* Return true if the coefficients of this generic_wide_int-based
627 : polynomial can be represented as signed HOST_WIDE_INTs without loss
628 : of precision. Store the HOST_WIDE_INT representation in *R if so. */
629 :
630 : template<unsigned int N, typename C>
631 : inline bool
632 11666020419 : poly_int<N, C>::to_shwi (poly_int<N, HOST_WIDE_INT> *r) const
633 : {
634 23332022043 : for (unsigned int i = 0; i < N; i++)
635 11666020419 : if (!wi::fits_shwi_p (this->coeffs[i]))
636 : return false;
637 23332003248 : for (unsigned int i = 0; i < N; i++)
638 11666001624 : r->coeffs[i] = this->coeffs[i].to_shwi ();
639 : return true;
640 : }
641 :
642 : /* Return true if the coefficients of this generic_wide_int-based
643 : polynomial can be represented as unsigned HOST_WIDE_INTs without
644 : loss of precision. Store the unsigned HOST_WIDE_INT representation
645 : in *R if so. */
646 :
647 : template<unsigned int N, typename C>
648 : inline bool
649 18898 : poly_int<N, C>::to_uhwi (poly_int<N, unsigned HOST_WIDE_INT> *r) const
650 : {
651 37794 : for (unsigned int i = 0; i < N; i++)
652 18898 : if (!wi::fits_uhwi_p (this->coeffs[i]))
653 : return false;
654 37792 : for (unsigned int i = 0; i < N; i++)
655 18896 : r->coeffs[i] = this->coeffs[i].to_uhwi ();
656 : return true;
657 : }
658 :
659 : /* Force a generic_wide_int-based constant to HOST_WIDE_INT precision,
660 : truncating if necessary. */
661 :
662 : template<unsigned int N, typename C>
663 : inline poly_int<N, HOST_WIDE_INT>
664 31215875 : poly_int<N, C>::force_shwi () const
665 : {
666 : poly_int<N, HOST_WIDE_INT> r;
667 131764065 : for (unsigned int i = 0; i < N; i++)
668 132692708 : r.coeffs[i] = this->coeffs[i].to_shwi ();
669 871620 : return r;
670 : }
671 :
672 : /* Force a generic_wide_int-based constant to unsigned HOST_WIDE_INT precision,
673 : truncating if necessary. */
674 :
675 : template<unsigned int N, typename C>
676 : inline poly_int<N, unsigned HOST_WIDE_INT>
677 702 : poly_int<N, C>::force_uhwi () const
678 : {
679 : poly_int<N, unsigned HOST_WIDE_INT> r;
680 1404 : for (unsigned int i = 0; i < N; i++)
681 702 : r.coeffs[i] = this->coeffs[i].to_uhwi ();
682 702 : return r;
683 : }
684 :
685 : #if POLY_INT_CONVERSION
686 : /* Provide a conversion operator to constants. */
687 :
688 : template<unsigned int N, typename C>
689 : inline
690 81512542 : poly_int<N, C>::operator C () const
691 : {
692 : gcc_checking_assert (this->is_constant ());
693 81486646 : return this->coeffs[0];
694 : }
695 : #endif
696 :
697 : /* Return true if every coefficient of A is in the inclusive range [B, C]. */
698 :
699 : template<typename Ca, typename Cb, typename Cc>
700 : inline typename if_nonpoly<Ca, bool>::type
701 : coeffs_in_range_p (const Ca &a, const Cb &b, const Cc &c)
702 : {
703 : return a >= b && a <= c;
704 : }
705 :
706 : template<unsigned int N, typename Ca, typename Cb, typename Cc>
707 : inline typename if_nonpoly<Ca, bool>::type
708 3933112 : coeffs_in_range_p (const poly_int<N, Ca> &a, const Cb &b, const Cc &c)
709 : {
710 37320727 : for (unsigned int i = 0; i < N; i++)
711 37320727 : if (a.coeffs[i] < b || a.coeffs[i] > c)
712 : return false;
713 : return true;
714 : }
715 :
716 : namespace wi {
717 : /* Poly version of wi::shwi, with the same interface. */
718 :
719 : template<unsigned int N>
720 : inline poly_int<N, hwi_with_prec>
721 7675423460 : shwi (const poly_int<N, HOST_WIDE_INT> &a, unsigned int precision)
722 : {
723 7675423460 : poly_int<N, hwi_with_prec> r;
724 15350846920 : for (unsigned int i = 0; i < N; i++)
725 7675423460 : POLY_SET_COEFF (hwi_with_prec, r, i, wi::shwi (a.coeffs[i], precision));
726 7675423460 : return r;
727 : }
728 :
729 : /* Poly version of wi::uhwi, with the same interface. */
730 :
731 : template<unsigned int N>
732 : inline poly_int<N, hwi_with_prec>
733 9398429 : uhwi (const poly_int<N, unsigned HOST_WIDE_INT> &a, unsigned int precision)
734 : {
735 9398429 : poly_int<N, hwi_with_prec> r;
736 18796858 : for (unsigned int i = 0; i < N; i++)
737 9398429 : POLY_SET_COEFF (hwi_with_prec, r, i, wi::uhwi (a.coeffs[i], precision));
738 9398429 : return r;
739 : }
740 :
741 : /* Poly version of wi::sext, with the same interface. */
742 :
743 : template<unsigned int N, typename Ca>
744 : inline POLY_POLY_RESULT (N, Ca, Ca)
745 821372940 : sext (const poly_int<N, Ca> &a, unsigned int precision)
746 : {
747 : typedef POLY_POLY_COEFF (Ca, Ca) C;
748 1331829469 : poly_int<N, C> r;
749 1978006031 : for (unsigned int i = 0; i < N; i++)
750 1467549502 : POLY_SET_COEFF (C, r, i, wi::sext (a.coeffs[i], precision));
751 510456529 : return r;
752 : }
753 :
754 : /* Poly version of wi::zext, with the same interface. */
755 :
756 : template<unsigned int N, typename Ca>
757 : inline POLY_POLY_RESULT (N, Ca, Ca)
758 2771263817 : zext (const poly_int<N, Ca> &a, unsigned int precision)
759 : {
760 : typedef POLY_POLY_COEFF (Ca, Ca) C;
761 5542527483 : poly_int<N, C> r;
762 5542527483 : for (unsigned int i = 0; i < N; i++)
763 2771263817 : POLY_SET_COEFF (C, r, i, wi::zext (a.coeffs[i], precision));
764 2771263666 : return r;
765 : }
766 : }
767 :
768 : template<unsigned int N, typename Ca, typename Cb>
769 : inline POLY_POLY_RESULT (N, Ca, Cb)
770 2046668825 : operator + (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
771 : {
772 : typedef POLY_CAST (Ca, Cb) NCa;
773 : typedef POLY_POLY_COEFF (Ca, Cb) C;
774 775828077 : poly_int<N, C> r;
775 2330148022 : for (unsigned int i = 0; i < N; i++)
776 1697423169 : POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) + b.coeffs[i]);
777 92858122 : return r;
778 : }
779 :
780 : template<unsigned int N, typename Ca, typename Cb>
781 : inline POLY_CONST_RESULT (N, Ca, Cb)
782 770719018 : operator + (const poly_int<N, Ca> &a, const Cb &b)
783 : {
784 : typedef POLY_CAST (Ca, Cb) NCa;
785 : typedef POLY_CONST_COEFF (Ca, Cb) C;
786 213889067 : poly_int<N, C> r;
787 494830695 : POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) + b);
788 : if (N >= 2)
789 : for (unsigned int i = 1; i < N; i++)
790 : POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
791 : return r;
792 : }
793 :
794 : template<unsigned int N, typename Ca, typename Cb>
795 : inline CONST_POLY_RESULT (N, Ca, Cb)
796 7614893 : operator + (const Ca &a, const poly_int<N, Cb> &b)
797 : {
798 : typedef POLY_CAST (Cb, Ca) NCb;
799 : typedef CONST_POLY_COEFF (Ca, Cb) C;
800 : poly_int<N, C> r;
801 7614893 : POLY_SET_COEFF (C, r, 0, a + NCb (b.coeffs[0]));
802 : if (N >= 2)
803 : for (unsigned int i = 1; i < N; i++)
804 : POLY_SET_COEFF (C, r, i, NCb (b.coeffs[i]));
805 : return r;
806 : }
807 :
808 : namespace wi {
809 : /* Poly versions of wi::add, with the same interface. */
810 :
811 : template<unsigned int N, typename Ca, typename Cb>
812 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
813 : add (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
814 : {
815 : typedef WI_BINARY_RESULT (Ca, Cb) C;
816 : poly_int<N, C> r;
817 : for (unsigned int i = 0; i < N; i++)
818 : POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i]));
819 : return r;
820 : }
821 :
822 : template<unsigned int N, typename Ca, typename Cb>
823 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
824 : add (const poly_int<N, Ca> &a, const Cb &b)
825 : {
826 : typedef WI_BINARY_RESULT (Ca, Cb) C;
827 : poly_int<N, C> r;
828 : POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b));
829 : for (unsigned int i = 1; i < N; i++)
830 : POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i],
831 : wi::ints_for<Cb>::zero (b)));
832 : return r;
833 : }
834 :
835 : template<unsigned int N, typename Ca, typename Cb>
836 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
837 494418264 : add (const Ca &a, const poly_int<N, Cb> &b)
838 : {
839 : typedef WI_BINARY_RESULT (Ca, Cb) C;
840 494418264 : poly_int<N, C> r;
841 494418264 : POLY_SET_COEFF (C, r, 0, wi::add (a, b.coeffs[0]));
842 494418264 : for (unsigned int i = 1; i < N; i++)
843 : POLY_SET_COEFF (C, r, i, wi::add (wi::ints_for<Ca>::zero (a),
844 : b.coeffs[i]));
845 : return r;
846 : }
847 :
848 : template<unsigned int N, typename Ca, typename Cb>
849 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
850 4140 : add (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
851 : signop sgn, wi::overflow_type *overflow)
852 : {
853 : typedef WI_BINARY_RESULT (Ca, Cb) C;
854 4140 : poly_int<N, C> r;
855 4140 : POLY_SET_COEFF (C, r, 0, wi::add (a.coeffs[0], b.coeffs[0], sgn, overflow));
856 4140 : for (unsigned int i = 1; i < N; i++)
857 : {
858 : wi::overflow_type suboverflow;
859 : POLY_SET_COEFF (C, r, i, wi::add (a.coeffs[i], b.coeffs[i], sgn,
860 : &suboverflow));
861 : wi::accumulate_overflow (*overflow, suboverflow);
862 : }
863 : return r;
864 : }
865 : }
866 :
867 : template<unsigned int N, typename Ca, typename Cb>
868 : inline POLY_POLY_RESULT (N, Ca, Cb)
869 1906365558 : operator - (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
870 : {
871 : typedef POLY_CAST (Ca, Cb) NCa;
872 : typedef POLY_POLY_COEFF (Ca, Cb) C;
873 942323102 : poly_int<N, C> r;
874 2978082101 : for (unsigned int i = 0; i < N; i++)
875 2284438342 : POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) - b.coeffs[i]);
876 17326430 : return r;
877 : }
878 :
879 : template<unsigned int N, typename Ca, typename Cb>
880 : inline POLY_CONST_RESULT (N, Ca, Cb)
881 423818229 : operator - (const poly_int<N, Ca> &a, const Cb &b)
882 : {
883 : typedef POLY_CAST (Ca, Cb) NCa;
884 : typedef POLY_CONST_COEFF (Ca, Cb) C;
885 5290333 : poly_int<N, C> r;
886 426247285 : POLY_SET_COEFF (C, r, 0, NCa (a.coeffs[0]) - b);
887 : if (N >= 2)
888 : for (unsigned int i = 1; i < N; i++)
889 : POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]));
890 : return r;
891 : }
892 :
893 : template<unsigned int N, typename Ca, typename Cb>
894 : inline CONST_POLY_RESULT (N, Ca, Cb)
895 155842293 : operator - (const Ca &a, const poly_int<N, Cb> &b)
896 : {
897 : typedef POLY_CAST (Cb, Ca) NCb;
898 : typedef CONST_POLY_COEFF (Ca, Cb) C;
899 126585325 : poly_int<N, C> r;
900 155816906 : POLY_SET_COEFF (C, r, 0, a - NCb (b.coeffs[0]));
901 : if (N >= 2)
902 : for (unsigned int i = 1; i < N; i++)
903 : POLY_SET_COEFF (C, r, i, -NCb (b.coeffs[i]));
904 : return r;
905 : }
906 :
907 : namespace wi {
908 : /* Poly versions of wi::sub, with the same interface. */
909 :
910 : template<unsigned int N, typename Ca, typename Cb>
911 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
912 : sub (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
913 : {
914 : typedef WI_BINARY_RESULT (Ca, Cb) C;
915 : poly_int<N, C> r;
916 : for (unsigned int i = 0; i < N; i++)
917 : POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i]));
918 : return r;
919 : }
920 :
921 : template<unsigned int N, typename Ca, typename Cb>
922 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
923 : sub (const poly_int<N, Ca> &a, const Cb &b)
924 : {
925 : typedef WI_BINARY_RESULT (Ca, Cb) C;
926 : poly_int<N, C> r;
927 : POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b));
928 : for (unsigned int i = 1; i < N; i++)
929 : POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i],
930 : wi::ints_for<Cb>::zero (b)));
931 : return r;
932 : }
933 :
934 : template<unsigned int N, typename Ca, typename Cb>
935 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
936 64880 : sub (const Ca &a, const poly_int<N, Cb> &b)
937 : {
938 : typedef WI_BINARY_RESULT (Ca, Cb) C;
939 64880 : poly_int<N, C> r;
940 64880 : POLY_SET_COEFF (C, r, 0, wi::sub (a, b.coeffs[0]));
941 64880 : for (unsigned int i = 1; i < N; i++)
942 : POLY_SET_COEFF (C, r, i, wi::sub (wi::ints_for<Ca>::zero (a),
943 : b.coeffs[i]));
944 : return r;
945 : }
946 :
947 : template<unsigned int N, typename Ca, typename Cb>
948 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
949 : sub (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
950 : signop sgn, wi::overflow_type *overflow)
951 : {
952 : typedef WI_BINARY_RESULT (Ca, Cb) C;
953 : poly_int<N, C> r;
954 : POLY_SET_COEFF (C, r, 0, wi::sub (a.coeffs[0], b.coeffs[0], sgn, overflow));
955 : for (unsigned int i = 1; i < N; i++)
956 : {
957 : wi::overflow_type suboverflow;
958 : POLY_SET_COEFF (C, r, i, wi::sub (a.coeffs[i], b.coeffs[i], sgn,
959 : &suboverflow));
960 : wi::accumulate_overflow (*overflow, suboverflow);
961 : }
962 : return r;
963 : }
964 : }
965 :
966 : template<unsigned int N, typename Ca>
967 : inline POLY_POLY_RESULT (N, Ca, Ca)
968 525882481 : operator - (const poly_int<N, Ca> &a)
969 : {
970 : typedef POLY_CAST (Ca, Ca) NCa;
971 : typedef POLY_POLY_COEFF (Ca, Ca) C;
972 22354098 : poly_int<N, C> r;
973 625886601 : for (unsigned int i = 0; i < N; i++)
974 147022120 : POLY_SET_COEFF (C, r, i, -NCa (a.coeffs[i]));
975 35324417 : return r;
976 : }
977 :
978 : namespace wi {
979 : /* Poly version of wi::neg, with the same interface. */
980 :
981 : template<unsigned int N, typename Ca>
982 : inline poly_int<N, WI_UNARY_RESULT (Ca)>
983 : neg (const poly_int<N, Ca> &a)
984 : {
985 : typedef WI_UNARY_RESULT (Ca) C;
986 : poly_int<N, C> r;
987 : for (unsigned int i = 0; i < N; i++)
988 : POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i]));
989 : return r;
990 : }
991 :
992 : template<unsigned int N, typename Ca>
993 : inline poly_int<N, WI_UNARY_RESULT (Ca)>
994 30310459 : neg (const poly_int<N, Ca> &a, wi::overflow_type *overflow)
995 : {
996 : typedef WI_UNARY_RESULT (Ca) C;
997 30310459 : poly_int<N, C> r;
998 30310459 : POLY_SET_COEFF (C, r, 0, wi::neg (a.coeffs[0], overflow));
999 30310459 : for (unsigned int i = 1; i < N; i++)
1000 : {
1001 : wi::overflow_type suboverflow;
1002 : POLY_SET_COEFF (C, r, i, wi::neg (a.coeffs[i], &suboverflow));
1003 : wi::accumulate_overflow (*overflow, suboverflow);
1004 : }
1005 : return r;
1006 : }
1007 : }
1008 :
1009 : template<unsigned int N, typename Ca>
1010 : inline POLY_POLY_RESULT (N, Ca, Ca)
1011 : operator ~ (const poly_int<N, Ca> &a)
1012 : {
1013 : if (N >= 2)
1014 : return -1 - a;
1015 : return ~a.coeffs[0];
1016 : }
1017 :
1018 : template<unsigned int N, typename Ca, typename Cb>
1019 : inline POLY_CONST_RESULT (N, Ca, Cb)
1020 14815159873 : operator * (const poly_int<N, Ca> &a, const Cb &b)
1021 : {
1022 : typedef POLY_CAST (Ca, Cb) NCa;
1023 : typedef POLY_CONST_COEFF (Ca, Cb) C;
1024 132107284 : poly_int<N, C> r;
1025 15001157711 : for (unsigned int i = 0; i < N; i++)
1026 14777453074 : POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) * b);
1027 10358 : return r;
1028 : }
1029 :
1030 : template<unsigned int N, typename Ca, typename Cb>
1031 : inline CONST_POLY_RESULT (N, Ca, Cb)
1032 250601116 : operator * (const Ca &a, const poly_int<N, Cb> &b)
1033 : {
1034 : typedef POLY_CAST (Ca, Cb) NCa;
1035 : typedef CONST_POLY_COEFF (Ca, Cb) C;
1036 65684258 : poly_int<N, C> r;
1037 506999783 : for (unsigned int i = 0; i < N; i++)
1038 335465408 : POLY_SET_COEFF (C, r, i, NCa (a) * b.coeffs[i]);
1039 168793738 : return r;
1040 : }
1041 :
1042 : namespace wi {
1043 : /* Poly versions of wi::mul, with the same interface. */
1044 :
1045 : template<unsigned int N, typename Ca, typename Cb>
1046 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1047 : mul (const poly_int<N, Ca> &a, const Cb &b)
1048 : {
1049 : typedef WI_BINARY_RESULT (Ca, Cb) C;
1050 : poly_int<N, C> r;
1051 : for (unsigned int i = 0; i < N; i++)
1052 : POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b));
1053 : return r;
1054 : }
1055 :
1056 : template<unsigned int N, typename Ca, typename Cb>
1057 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1058 115 : mul (const Ca &a, const poly_int<N, Cb> &b)
1059 : {
1060 : typedef WI_BINARY_RESULT (Ca, Cb) C;
1061 230 : poly_int<N, C> r;
1062 230 : for (unsigned int i = 0; i < N; i++)
1063 115 : POLY_SET_COEFF (C, r, i, wi::mul (a, b.coeffs[i]));
1064 115 : return r;
1065 : }
1066 :
1067 : template<unsigned int N, typename Ca, typename Cb>
1068 : inline poly_int<N, WI_BINARY_RESULT (Ca, Cb)>
1069 : mul (const poly_int<N, Ca> &a, const Cb &b,
1070 : signop sgn, wi::overflow_type *overflow)
1071 : {
1072 : typedef WI_BINARY_RESULT (Ca, Cb) C;
1073 : poly_int<N, C> r;
1074 : POLY_SET_COEFF (C, r, 0, wi::mul (a.coeffs[0], b, sgn, overflow));
1075 : for (unsigned int i = 1; i < N; i++)
1076 : {
1077 : wi::overflow_type suboverflow;
1078 : POLY_SET_COEFF (C, r, i, wi::mul (a.coeffs[i], b, sgn, &suboverflow));
1079 : wi::accumulate_overflow (*overflow, suboverflow);
1080 : }
1081 : return r;
1082 : }
1083 : }
1084 :
1085 : template<unsigned int N, typename Ca, typename Cb>
1086 : inline POLY_POLY_RESULT (N, Ca, Ca)
1087 2343465439 : operator << (const poly_int<N, Ca> &a, const Cb &b)
1088 : {
1089 : typedef POLY_CAST (Ca, Ca) NCa;
1090 : typedef POLY_POLY_COEFF (Ca, Ca) C;
1091 2702411783 : poly_int<N, C> r;
1092 4683994704 : for (unsigned int i = 0; i < N; i++)
1093 2674959752 : POLY_SET_COEFF (C, r, i, NCa (a.coeffs[i]) << b);
1094 : return r;
1095 : }
1096 :
1097 : namespace wi {
1098 : /* Poly version of wi::lshift, with the same interface. */
1099 :
1100 : template<unsigned int N, typename Ca, typename Cb>
1101 : inline poly_int<N, WI_BINARY_RESULT (Ca, Ca)>
1102 : lshift (const poly_int<N, Ca> &a, const Cb &b)
1103 : {
1104 : typedef WI_BINARY_RESULT (Ca, Ca) C;
1105 : poly_int<N, C> r;
1106 : for (unsigned int i = 0; i < N; i++)
1107 : POLY_SET_COEFF (C, r, i, wi::lshift (a.coeffs[i], b));
1108 : return r;
1109 : }
1110 : }
1111 :
1112 : /* Poly version of sext_hwi, with the same interface. */
1113 :
1114 : template<unsigned int N, typename C>
1115 : inline poly_int<N, HOST_WIDE_INT>
1116 : sext_hwi (const poly_int<N, C> &a, unsigned int precision)
1117 : {
1118 : poly_int<N, HOST_WIDE_INT> r;
1119 : for (unsigned int i = 0; i < N; i++)
1120 : r.coeffs[i] = sext_hwi (a.coeffs[i], precision);
1121 : return r;
1122 : }
1123 :
1124 :
1125 : /* Return true if a0 + a1 * x might equal b0 + b1 * x for some nonnegative
1126 : integer x. */
1127 :
1128 : template<typename Ca, typename Cb>
1129 : inline bool
1130 : maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b0, const Cb &b1)
1131 : {
1132 : if (a1 != b1)
1133 : /* a0 + a1 * x == b0 + b1 * x
1134 : ==> (a1 - b1) * x == b0 - a0
1135 : ==> x == (b0 - a0) / (a1 - b1)
1136 :
1137 : We need to test whether that's a valid value of x.
1138 : (b0 - a0) and (a1 - b1) must not have opposite signs
1139 : and the result must be integral. */
1140 : return (a1 < b1
1141 : ? b0 <= a0 && (a0 - b0) % (b1 - a1) == 0
1142 : : b0 >= a0 && (b0 - a0) % (a1 - b1) == 0);
1143 : return a0 == b0;
1144 : }
1145 :
1146 : /* Return true if a0 + a1 * x might equal b for some nonnegative
1147 : integer x. */
1148 :
1149 : template<typename Ca, typename Cb>
1150 : inline bool
1151 : maybe_eq_2 (const Ca &a0, const Ca &a1, const Cb &b)
1152 : {
1153 : if (a1 != 0)
1154 : /* a0 + a1 * x == b
1155 : ==> x == (b - a0) / a1
1156 :
1157 : We need to test whether that's a valid value of x.
1158 : (b - a0) and a1 must not have opposite signs and the
1159 : result must be integral. */
1160 : return (a1 < 0
1161 : ? b <= a0 && (a0 - b) % a1 == 0
1162 : : b >= a0 && (b - a0) % a1 == 0);
1163 : return a0 == b;
1164 : }
1165 :
1166 : /* Return true if A might equal B for some indeterminate values. */
1167 :
1168 : template<unsigned int N, typename Ca, typename Cb>
1169 : inline bool
1170 12746614 : maybe_eq (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1171 : {
1172 : STATIC_ASSERT (N <= 2);
1173 : if (N == 2)
1174 : return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b.coeffs[0], b.coeffs[1]);
1175 12746614 : return a.coeffs[0] == b.coeffs[0];
1176 : }
1177 :
1178 : template<unsigned int N, typename Ca, typename Cb>
1179 : inline typename if_nonpoly<Cb, bool>::type
1180 24614005 : maybe_eq (const poly_int<N, Ca> &a, const Cb &b)
1181 : {
1182 : STATIC_ASSERT (N <= 2);
1183 : if (N == 2)
1184 : return maybe_eq_2 (a.coeffs[0], a.coeffs[1], b);
1185 23614636 : return a.coeffs[0] == b;
1186 : }
1187 :
1188 : template<unsigned int N, typename Ca, typename Cb>
1189 : inline typename if_nonpoly<Ca, bool>::type
1190 : maybe_eq (const Ca &a, const poly_int<N, Cb> &b)
1191 : {
1192 : STATIC_ASSERT (N <= 2);
1193 : if (N == 2)
1194 : return maybe_eq_2 (b.coeffs[0], b.coeffs[1], a);
1195 : return a == b.coeffs[0];
1196 : }
1197 :
1198 : template<typename Ca, typename Cb>
1199 : inline typename if_nonpoly2<Ca, Cb, bool>::type
1200 : maybe_eq (const Ca &a, const Cb &b)
1201 : {
1202 : return a == b;
1203 : }
1204 :
1205 : /* Return true if A might not equal B for some indeterminate values. */
1206 :
1207 : template<unsigned int N, typename Ca, typename Cb>
1208 : inline bool
1209 7366595522 : maybe_ne (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1210 : {
1211 : if (N >= 2)
1212 : for (unsigned int i = 1; i < N; i++)
1213 : if (a.coeffs[i] != b.coeffs[i])
1214 : return true;
1215 7279477761 : return a.coeffs[0] != b.coeffs[0];
1216 : }
1217 :
1218 : template<unsigned int N, typename Ca, typename Cb>
1219 : inline typename if_nonpoly<Cb, bool>::type
1220 13294963813 : maybe_ne (const poly_int<N, Ca> &a, const Cb &b)
1221 : {
1222 : if (N >= 2)
1223 : for (unsigned int i = 1; i < N; i++)
1224 : if (a.coeffs[i] != 0)
1225 : return true;
1226 11487292097 : return a.coeffs[0] != b;
1227 : }
1228 :
1229 : template<unsigned int N, typename Ca, typename Cb>
1230 : inline typename if_nonpoly<Ca, bool>::type
1231 107527318 : maybe_ne (const Ca &a, const poly_int<N, Cb> &b)
1232 : {
1233 : if (N >= 2)
1234 : for (unsigned int i = 1; i < N; i++)
1235 : if (b.coeffs[i] != 0)
1236 : return true;
1237 107457439 : return a != b.coeffs[0];
1238 : }
1239 :
1240 : template<typename Ca, typename Cb>
1241 : inline typename if_nonpoly2<Ca, Cb, bool>::type
1242 257738750 : maybe_ne (const Ca &a, const Cb &b)
1243 : {
1244 257738750 : return a != b;
1245 : }
1246 :
1247 : /* Return true if A is known to be equal to B. */
1248 : #define known_eq(A, B) (!maybe_ne (A, B))
1249 :
1250 : /* Return true if A is known to be unequal to B. */
1251 : #define known_ne(A, B) (!maybe_eq (A, B))
1252 :
1253 : /* Return true if A might be less than or equal to B for some
1254 : indeterminate values. */
1255 :
1256 : template<unsigned int N, typename Ca, typename Cb>
1257 : inline bool
1258 1347642311 : maybe_le (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1259 : {
1260 : if (N >= 2)
1261 : for (unsigned int i = 1; i < N; i++)
1262 : if (a.coeffs[i] < b.coeffs[i])
1263 : return true;
1264 676373815 : return a.coeffs[0] <= b.coeffs[0];
1265 : }
1266 :
1267 : template<unsigned int N, typename Ca, typename Cb>
1268 : inline typename if_nonpoly<Cb, bool>::type
1269 295637319 : maybe_le (const poly_int<N, Ca> &a, const Cb &b)
1270 : {
1271 : if (N >= 2)
1272 : for (unsigned int i = 1; i < N; i++)
1273 : if (a.coeffs[i] < 0)
1274 : return true;
1275 189436138 : return a.coeffs[0] <= b;
1276 : }
1277 :
1278 : template<unsigned int N, typename Ca, typename Cb>
1279 : inline typename if_nonpoly<Ca, bool>::type
1280 99348764 : maybe_le (const Ca &a, const poly_int<N, Cb> &b)
1281 : {
1282 : if (N >= 2)
1283 : for (unsigned int i = 1; i < N; i++)
1284 : if (b.coeffs[i] > 0)
1285 : return true;
1286 99176180 : return a <= b.coeffs[0];
1287 : }
1288 :
1289 : template<typename Ca, typename Cb>
1290 : inline typename if_nonpoly2<Ca, Cb, bool>::type
1291 3433377 : maybe_le (const Ca &a, const Cb &b)
1292 : {
1293 3433377 : return a <= b;
1294 : }
1295 :
1296 : /* Return true if A might be less than B for some indeterminate values. */
1297 :
1298 : template<unsigned int N, typename Ca, typename Cb>
1299 : inline bool
1300 2044291252 : maybe_lt (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1301 : {
1302 : if (N >= 2)
1303 : for (unsigned int i = 1; i < N; i++)
1304 : if (a.coeffs[i] < b.coeffs[i])
1305 : return true;
1306 2515263100 : return a.coeffs[0] < b.coeffs[0];
1307 : }
1308 :
1309 : template<unsigned int N, typename Ca, typename Cb>
1310 : inline typename if_nonpoly<Cb, bool>::type
1311 12861538387 : maybe_lt (const poly_int<N, Ca> &a, const Cb &b)
1312 : {
1313 : if (N >= 2)
1314 : for (unsigned int i = 1; i < N; i++)
1315 : if (a.coeffs[i] < 0)
1316 : return true;
1317 12860926883 : return a.coeffs[0] < b;
1318 : }
1319 :
1320 : template<unsigned int N, typename Ca, typename Cb>
1321 : inline typename if_nonpoly<Ca, bool>::type
1322 323477593 : maybe_lt (const Ca &a, const poly_int<N, Cb> &b)
1323 : {
1324 : if (N >= 2)
1325 : for (unsigned int i = 1; i < N; i++)
1326 : if (b.coeffs[i] > 0)
1327 : return true;
1328 322904084 : return a < b.coeffs[0];
1329 : }
1330 :
1331 : template<typename Ca, typename Cb>
1332 : inline typename if_nonpoly2<Ca, Cb, bool>::type
1333 559604 : maybe_lt (const Ca &a, const Cb &b)
1334 : {
1335 559604 : return a < b;
1336 : }
1337 :
1338 : /* Return true if A may be greater than or equal to B. */
1339 : #define maybe_ge(A, B) maybe_le (B, A)
1340 :
1341 : /* Return true if A may be greater than B. */
1342 : #define maybe_gt(A, B) maybe_lt (B, A)
1343 :
1344 : /* Return true if A is known to be less than or equal to B. */
1345 : #define known_le(A, B) (!maybe_gt (A, B))
1346 :
1347 : /* Return true if A is known to be less than B. */
1348 : #define known_lt(A, B) (!maybe_ge (A, B))
1349 :
1350 : /* Return true if A is known to be greater than B. */
1351 : #define known_gt(A, B) (!maybe_le (A, B))
1352 :
1353 : /* Return true if A is known to be greater than or equal to B. */
1354 : #define known_ge(A, B) (!maybe_lt (A, B))
1355 :
1356 : /* Return true if A and B are ordered by the partial ordering known_le. */
1357 :
1358 : template<typename T1, typename T2>
1359 : inline bool
1360 : ordered_p (const T1 &a, const T2 &b)
1361 : {
1362 : return ((poly_int_traits<T1>::num_coeffs == 1
1363 : && poly_int_traits<T2>::num_coeffs == 1)
1364 : || known_le (a, b)
1365 : || known_le (b, a));
1366 : }
1367 :
1368 : /* Assert that A and B are known to be ordered and return the minimum
1369 : of the two.
1370 :
1371 : NOTE: When using this function, please add a comment above the call
1372 : explaining why we know the values are ordered in that context. */
1373 :
1374 : template<unsigned int N, typename Ca, typename Cb>
1375 : inline POLY_POLY_RESULT (N, Ca, Cb)
1376 13999685 : ordered_min (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1377 : {
1378 13999685 : if (known_le (a, b))
1379 : return a;
1380 : else
1381 : {
1382 : if (N > 1)
1383 : gcc_checking_assert (known_le (b, a));
1384 : return b;
1385 : }
1386 : }
1387 :
1388 : template<unsigned int N, typename Ca, typename Cb>
1389 : inline CONST_POLY_RESULT (N, Ca, Cb)
1390 : ordered_min (const Ca &a, const poly_int<N, Cb> &b)
1391 : {
1392 : if (known_le (a, b))
1393 : return a;
1394 : else
1395 : {
1396 : if (N > 1)
1397 : gcc_checking_assert (known_le (b, a));
1398 : return b;
1399 : }
1400 : }
1401 :
1402 : template<unsigned int N, typename Ca, typename Cb>
1403 : inline POLY_CONST_RESULT (N, Ca, Cb)
1404 : ordered_min (const poly_int<N, Ca> &a, const Cb &b)
1405 : {
1406 : if (known_le (a, b))
1407 : return a;
1408 : else
1409 : {
1410 : if (N > 1)
1411 : gcc_checking_assert (known_le (b, a));
1412 : return b;
1413 : }
1414 : }
1415 :
1416 : /* Assert that A and B are known to be ordered and return the maximum
1417 : of the two.
1418 :
1419 : NOTE: When using this function, please add a comment above the call
1420 : explaining why we know the values are ordered in that context. */
1421 :
1422 : template<unsigned int N, typename Ca, typename Cb>
1423 : inline POLY_POLY_RESULT (N, Ca, Cb)
1424 103588 : ordered_max (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1425 : {
1426 103588 : if (known_le (a, b))
1427 : return b;
1428 : else
1429 : {
1430 : if (N > 1)
1431 : gcc_checking_assert (known_le (b, a));
1432 : return a;
1433 : }
1434 : }
1435 :
1436 : template<unsigned int N, typename Ca, typename Cb>
1437 : inline CONST_POLY_RESULT (N, Ca, Cb)
1438 321935 : ordered_max (const Ca &a, const poly_int<N, Cb> &b)
1439 : {
1440 321935 : if (known_le (a, b))
1441 320293 : return b;
1442 : else
1443 : {
1444 : if (N > 1)
1445 : gcc_checking_assert (known_le (b, a));
1446 1642 : return a;
1447 : }
1448 : }
1449 :
1450 : template<unsigned int N, typename Ca, typename Cb>
1451 : inline POLY_CONST_RESULT (N, Ca, Cb)
1452 83755 : ordered_max (const poly_int<N, Ca> &a, const Cb &b)
1453 : {
1454 83755 : if (known_le (a, b))
1455 : return b;
1456 : else
1457 : {
1458 : if (N > 1)
1459 : gcc_checking_assert (known_le (b, a));
1460 : return a;
1461 : }
1462 : }
1463 :
1464 : /* Return a constant lower bound on the value of A, which is known
1465 : to be nonnegative. */
1466 :
1467 : template<unsigned int N, typename Ca>
1468 : inline Ca
1469 43157106 : constant_lower_bound (const poly_int<N, Ca> &a)
1470 : {
1471 3826595 : gcc_checking_assert (known_ge (a, POLY_INT_TYPE (Ca) (0)));
1472 40807272 : return a.coeffs[0];
1473 : }
1474 :
1475 : /* Return the constant lower bound of A, given that it is no less than B. */
1476 :
1477 : template<unsigned int N, typename Ca, typename Cb>
1478 : inline POLY_CONST_COEFF (Ca, Cb)
1479 : constant_lower_bound_with_limit (const poly_int<N, Ca> &a, const Cb &b)
1480 : {
1481 : if (known_ge (a, b))
1482 : return a.coeffs[0];
1483 : return b;
1484 : }
1485 :
1486 : /* Return the constant upper bound of A, given that it is no greater
1487 : than B. */
1488 :
1489 : template<unsigned int N, typename Ca, typename Cb>
1490 : inline POLY_CONST_COEFF (Ca, Cb)
1491 : constant_upper_bound_with_limit (const poly_int<N, Ca> &a, const Cb &b)
1492 : {
1493 : if (known_le (a, b))
1494 : return a.coeffs[0];
1495 : return b;
1496 : }
1497 :
1498 : /* Return a value that is known to be no greater than A and B. This
1499 : will be the greatest lower bound for some indeterminate values but
1500 : not necessarily for all. */
1501 :
1502 : template<unsigned int N, typename Ca, typename Cb>
1503 : inline POLY_CONST_RESULT (N, Ca, Cb)
1504 24 : lower_bound (const poly_int<N, Ca> &a, const Cb &b)
1505 : {
1506 : typedef POLY_CAST (Ca, Cb) NCa;
1507 : typedef POLY_CAST (Cb, Ca) NCb;
1508 : typedef POLY_INT_TYPE (Cb) ICb;
1509 : typedef POLY_CONST_COEFF (Ca, Cb) C;
1510 :
1511 : poly_int<N, C> r;
1512 24 : POLY_SET_COEFF (C, r, 0, MIN (NCa (a.coeffs[0]), NCb (b)));
1513 : if (N >= 2)
1514 : for (unsigned int i = 1; i < N; i++)
1515 : POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), ICb (0)));
1516 : return r;
1517 : }
1518 :
1519 : template<unsigned int N, typename Ca, typename Cb>
1520 : inline CONST_POLY_RESULT (N, Ca, Cb)
1521 : lower_bound (const Ca &a, const poly_int<N, Cb> &b)
1522 : {
1523 : return lower_bound (b, a);
1524 : }
1525 :
1526 : template<unsigned int N, typename Ca, typename Cb>
1527 : inline POLY_POLY_RESULT (N, Ca, Cb)
1528 8042 : lower_bound (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1529 : {
1530 : typedef POLY_CAST (Ca, Cb) NCa;
1531 : typedef POLY_CAST (Cb, Ca) NCb;
1532 : typedef POLY_POLY_COEFF (Ca, Cb) C;
1533 :
1534 8042 : poly_int<N, C> r;
1535 124938 : for (unsigned int i = 0; i < N; i++)
1536 78259 : POLY_SET_COEFF (C, r, i, MIN (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1537 8042 : return r;
1538 : }
1539 :
1540 : template<typename Ca, typename Cb>
1541 : inline CONST_CONST_RESULT (N, Ca, Cb)
1542 1298200 : lower_bound (const Ca &a, const Cb &b)
1543 : {
1544 1298200 : return a < b ? a : b;
1545 : }
1546 :
1547 : /* Return a value that is known to be no less than A and B. This will
1548 : be the least upper bound for some indeterminate values but not
1549 : necessarily for all. */
1550 :
1551 : template<unsigned int N, typename Ca, typename Cb>
1552 : inline POLY_CONST_RESULT (N, Ca, Cb)
1553 7429866 : upper_bound (const poly_int<N, Ca> &a, const Cb &b)
1554 : {
1555 : typedef POLY_CAST (Ca, Cb) NCa;
1556 : typedef POLY_CAST (Cb, Ca) NCb;
1557 : typedef POLY_INT_TYPE (Cb) ICb;
1558 : typedef POLY_CONST_COEFF (Ca, Cb) C;
1559 :
1560 : poly_int<N, C> r;
1561 7429866 : POLY_SET_COEFF (C, r, 0, MAX (NCa (a.coeffs[0]), NCb (b)));
1562 : if (N >= 2)
1563 : for (unsigned int i = 1; i < N; i++)
1564 : POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), ICb (0)));
1565 : return r;
1566 : }
1567 :
1568 : template<unsigned int N, typename Ca, typename Cb>
1569 : inline CONST_POLY_RESULT (N, Ca, Cb)
1570 : upper_bound (const Ca &a, const poly_int<N, Cb> &b)
1571 : {
1572 : return upper_bound (b, a);
1573 : }
1574 :
1575 : template<unsigned int N, typename Ca, typename Cb>
1576 : inline POLY_POLY_RESULT (N, Ca, Cb)
1577 7485501 : upper_bound (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1578 : {
1579 : typedef POLY_CAST (Ca, Cb) NCa;
1580 : typedef POLY_CAST (Cb, Ca) NCb;
1581 : typedef POLY_POLY_COEFF (Ca, Cb) C;
1582 :
1583 : poly_int<N, C> r;
1584 591195132 : for (unsigned int i = 0; i < N; i++)
1585 360409118 : POLY_SET_COEFF (C, r, i, MAX (NCa (a.coeffs[i]), NCb (b.coeffs[i])));
1586 : return r;
1587 : }
1588 :
1589 : /* Return the greatest common divisor of all nonzero coefficients, or zero
1590 : if all coefficients are zero. */
1591 :
1592 : template<unsigned int N, typename Ca>
1593 : inline POLY_BINARY_COEFF (Ca, Ca)
1594 14454683 : coeff_gcd (const poly_int<N, Ca> &a)
1595 : {
1596 : /* Find the first nonzero coefficient, stopping at 0 whatever happens. */
1597 : unsigned int i;
1598 14454683 : for (i = N - 1; i > 0; --i)
1599 : if (a.coeffs[i] != 0)
1600 : break;
1601 : typedef POLY_BINARY_COEFF (Ca, Ca) C;
1602 14454683 : C r = a.coeffs[i];
1603 : for (unsigned int j = 0; j < i; ++j)
1604 : if (a.coeffs[j] != 0)
1605 : r = gcd (r, C (a.coeffs[j]));
1606 : return r;
1607 : }
1608 :
1609 : /* Return a value that is a multiple of both A and B. This will be the
1610 : least common multiple for some indeterminate values but necessarily
1611 : for all. */
1612 :
1613 : template<unsigned int N, typename Ca, typename Cb>
1614 : POLY_CONST_RESULT (N, Ca, Cb)
1615 14454683 : common_multiple (const poly_int<N, Ca> &a, Cb b)
1616 : {
1617 14454683 : POLY_BINARY_COEFF (Ca, Ca) xgcd = coeff_gcd (a);
1618 14454683 : return a * (least_common_multiple (xgcd, b) / xgcd);
1619 : }
1620 :
1621 : template<unsigned int N, typename Ca, typename Cb>
1622 : inline CONST_POLY_RESULT (N, Ca, Cb)
1623 : common_multiple (const Ca &a, const poly_int<N, Cb> &b)
1624 : {
1625 : return common_multiple (b, a);
1626 : }
1627 :
1628 : /* Return a value that is a multiple of both A and B, asserting that
1629 : such a value exists. The result will be the least common multiple
1630 : for some indeterminate values but necessarily for all.
1631 :
1632 : NOTE: When using this function, please add a comment above the call
1633 : explaining why we know the values have a common multiple (which might
1634 : for example be because we know A / B is rational). */
1635 :
1636 : template<unsigned int N, typename Ca, typename Cb>
1637 : POLY_POLY_RESULT (N, Ca, Cb)
1638 10787694 : force_common_multiple (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1639 : {
1640 : if (b.is_constant ())
1641 10787694 : return common_multiple (a, b.coeffs[0]);
1642 : if (a.is_constant ())
1643 : return common_multiple (a.coeffs[0], b);
1644 :
1645 : typedef POLY_CAST (Ca, Cb) NCa;
1646 : typedef POLY_CAST (Cb, Ca) NCb;
1647 : typedef POLY_BINARY_COEFF (Ca, Cb) C;
1648 : typedef POLY_INT_TYPE (Ca) ICa;
1649 :
1650 : for (unsigned int i = 1; i < N; ++i)
1651 : if (a.coeffs[i] != ICa (0))
1652 : {
1653 : C lcm = least_common_multiple (NCa (a.coeffs[i]), NCb (b.coeffs[i]));
1654 : C amul = lcm / a.coeffs[i];
1655 : C bmul = lcm / b.coeffs[i];
1656 : for (unsigned int j = 0; j < N; ++j)
1657 : gcc_checking_assert (a.coeffs[j] * amul == b.coeffs[j] * bmul);
1658 : return a * amul;
1659 : }
1660 : gcc_unreachable ();
1661 : }
1662 :
1663 : /* Compare A and B for sorting purposes, returning -1 if A should come
1664 : before B, 0 if A and B are identical, and 1 if A should come after B.
1665 : This is a lexicographical compare of the coefficients in reverse order.
1666 :
1667 : A consequence of this is that all constant sizes come before all
1668 : non-constant ones, regardless of magnitude (since a size is never
1669 : negative). This is what most callers want. For example, when laying
1670 : data out on the stack, it's better to keep all the constant-sized
1671 : data together so that it can be accessed as a constant offset from a
1672 : single base. */
1673 :
1674 : template<unsigned int N, typename Ca, typename Cb>
1675 : inline int
1676 11310099 : compare_sizes_for_sort (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
1677 : {
1678 20715804 : for (unsigned int i = N; i-- > 0; )
1679 30499024 : if (a.coeffs[i] != b.coeffs[i])
1680 12734642 : return a.coeffs[i] < b.coeffs[i] ? -1 : 1;
1681 : return 0;
1682 : }
1683 :
1684 : /* Return true if we can calculate VALUE & (ALIGN - 1) at compile time. */
1685 :
1686 : template<unsigned int N, typename Ca, typename Cb>
1687 : inline bool
1688 : can_align_p (const poly_int<N, Ca> &value, Cb align)
1689 : {
1690 : for (unsigned int i = 1; i < N; i++)
1691 : if ((value.coeffs[i] & (align - 1)) != 0)
1692 : return false;
1693 : return true;
1694 : }
1695 :
1696 : /* Return true if we can align VALUE up to the smallest multiple of
1697 : ALIGN that is >= VALUE. Store the aligned value in *ALIGNED if so. */
1698 :
1699 : template<unsigned int N, typename Ca, typename Cb>
1700 : inline bool
1701 244066 : can_align_up (const poly_int<N, Ca> &value, Cb align,
1702 : poly_int<N, Ca> *aligned)
1703 : {
1704 : if (!can_align_p (value, align))
1705 : return false;
1706 244066 : *aligned = value + (-value.coeffs[0] & (align - 1));
1707 : return true;
1708 : }
1709 :
1710 : /* Return true if we can align VALUE down to the largest multiple of
1711 : ALIGN that is <= VALUE. Store the aligned value in *ALIGNED if so. */
1712 :
1713 : template<unsigned int N, typename Ca, typename Cb>
1714 : inline bool
1715 : can_align_down (const poly_int<N, Ca> &value, Cb align,
1716 : poly_int<N, Ca> *aligned)
1717 : {
1718 : if (!can_align_p (value, align))
1719 : return false;
1720 1423548 : *aligned = value - (value.coeffs[0] & (align - 1));
1721 : return true;
1722 : }
1723 :
1724 : /* Return true if we can align A and B up to the smallest multiples of
1725 : ALIGN that are >= A and B respectively, and if doing so gives the
1726 : same value. */
1727 :
1728 : template<unsigned int N, typename Ca, typename Cb, typename Cc>
1729 : inline bool
1730 244066 : known_equal_after_align_up (const poly_int<N, Ca> &a,
1731 : const poly_int<N, Cb> &b,
1732 : Cc align)
1733 : {
1734 : poly_int<N, Ca> aligned_a;
1735 : poly_int<N, Cb> aligned_b;
1736 244066 : return (can_align_up (a, align, &aligned_a)
1737 244066 : && can_align_up (b, align, &aligned_b)
1738 244066 : && known_eq (aligned_a, aligned_b));
1739 : }
1740 :
1741 : /* Return true if we can align A and B down to the largest multiples of
1742 : ALIGN that are <= A and B respectively, and if doing so gives the
1743 : same value. */
1744 :
1745 : template<unsigned int N, typename Ca, typename Cb, typename Cc>
1746 : inline bool
1747 1423548 : known_equal_after_align_down (const poly_int<N, Ca> &a,
1748 : const poly_int<N, Cb> &b,
1749 : Cc align)
1750 : {
1751 : poly_int<N, Ca> aligned_a;
1752 : poly_int<N, Cb> aligned_b;
1753 1423548 : return (can_align_down (a, align, &aligned_a)
1754 1423548 : && can_align_down (b, align, &aligned_b)
1755 1423548 : && known_eq (aligned_a, aligned_b));
1756 : }
1757 :
1758 : /* Assert that we can align VALUE to ALIGN at compile time and return
1759 : the smallest multiple of ALIGN that is >= VALUE.
1760 :
1761 : NOTE: When using this function, please add a comment above the call
1762 : explaining why we know the non-constant coefficients must already
1763 : be a multiple of ALIGN. */
1764 :
1765 : template<unsigned int N, typename Ca, typename Cb>
1766 : inline poly_int<N, Ca>
1767 7322631 : force_align_up (const poly_int<N, Ca> &value, Cb align)
1768 : {
1769 : gcc_checking_assert (can_align_p (value, align));
1770 7322631 : return value + (-value.coeffs[0] & (align - 1));
1771 : }
1772 :
1773 : /* Assert that we can align VALUE to ALIGN at compile time and return
1774 : the largest multiple of ALIGN that is <= VALUE.
1775 :
1776 : NOTE: When using this function, please add a comment above the call
1777 : explaining why we know the non-constant coefficients must already
1778 : be a multiple of ALIGN. */
1779 :
1780 : template<unsigned int N, typename Ca, typename Cb>
1781 : inline poly_int<N, Ca>
1782 5459863 : force_align_down (const poly_int<N, Ca> &value, Cb align)
1783 : {
1784 : gcc_checking_assert (can_align_p (value, align));
1785 5459863 : return value - (value.coeffs[0] & (align - 1));
1786 : }
1787 :
1788 : /* Return a value <= VALUE that is a multiple of ALIGN. It will be the
1789 : greatest such value for some indeterminate values but not necessarily
1790 : for all. */
1791 :
1792 : template<unsigned int N, typename Ca, typename Cb>
1793 : inline poly_int<N, Ca>
1794 238999161 : aligned_lower_bound (const poly_int<N, Ca> &value, Cb align)
1795 : {
1796 : poly_int<N, Ca> r;
1797 238999161 : for (unsigned int i = 0; i < N; i++)
1798 : /* This form copes correctly with more type combinations than
1799 : value.coeffs[i] & -align would. */
1800 238999161 : POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1801 : - (value.coeffs[i] & (align - 1))));
1802 : return r;
1803 : }
1804 :
1805 : /* Return a value >= VALUE that is a multiple of ALIGN. It will be the
1806 : least such value for some indeterminate values but not necessarily
1807 : for all. */
1808 :
1809 : template<unsigned int N, typename Ca, typename Cb>
1810 : inline poly_int<N, Ca>
1811 240899556 : aligned_upper_bound (const poly_int<N, Ca> &value, Cb align)
1812 : {
1813 : poly_int<N, Ca> r;
1814 240899556 : for (unsigned int i = 0; i < N; i++)
1815 240889672 : POLY_SET_COEFF (Ca, r, i, (value.coeffs[i]
1816 : + (-value.coeffs[i] & (align - 1))));
1817 9884 : return r;
1818 : }
1819 :
1820 : /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1821 : down to the largest multiple of ALIGN that is <= VALUE, then divide by
1822 : ALIGN.
1823 :
1824 : NOTE: When using this function, please add a comment above the call
1825 : explaining why we know the non-constant coefficients must already
1826 : be a multiple of ALIGN. */
1827 :
1828 : template<unsigned int N, typename Ca, typename Cb>
1829 : inline poly_int<N, Ca>
1830 15307419 : force_align_down_and_div (const poly_int<N, Ca> &value, Cb align)
1831 : {
1832 : gcc_checking_assert (can_align_p (value, align));
1833 :
1834 4658 : poly_int<N, Ca> r;
1835 15307419 : POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1836 : - (value.coeffs[0] & (align - 1)))
1837 : / align));
1838 : if (N >= 2)
1839 : for (unsigned int i = 1; i < N; i++)
1840 : POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1841 4658 : return r;
1842 : }
1843 :
1844 : /* Assert that we can align VALUE to ALIGN at compile time. Align VALUE
1845 : up to the smallest multiple of ALIGN that is >= VALUE, then divide by
1846 : ALIGN.
1847 :
1848 : NOTE: When using this function, please add a comment above the call
1849 : explaining why we know the non-constant coefficients must already
1850 : be a multiple of ALIGN. */
1851 :
1852 : template<unsigned int N, typename Ca, typename Cb>
1853 : inline poly_int<N, Ca>
1854 5558040 : force_align_up_and_div (const poly_int<N, Ca> &value, Cb align)
1855 : {
1856 : gcc_checking_assert (can_align_p (value, align));
1857 :
1858 : poly_int<N, Ca> r;
1859 5558040 : POLY_SET_COEFF (Ca, r, 0, ((value.coeffs[0]
1860 : + (-value.coeffs[0] & (align - 1)))
1861 : / align));
1862 : if (N >= 2)
1863 : for (unsigned int i = 1; i < N; i++)
1864 : POLY_SET_COEFF (Ca, r, i, value.coeffs[i] / align);
1865 : return r;
1866 : }
1867 :
1868 : /* Return true if we know at compile time the difference between VALUE
1869 : and the equal or preceding multiple of ALIGN. Store the value in
1870 : *MISALIGN if so. */
1871 :
1872 : template<unsigned int N, typename Ca, typename Cb, typename Cm>
1873 : inline bool
1874 20909995 : known_misalignment (const poly_int<N, Ca> &value, Cb align, Cm *misalign)
1875 : {
1876 20909995 : gcc_checking_assert (align != 0);
1877 : if (!can_align_p (value, align))
1878 : return false;
1879 20909995 : *misalign = value.coeffs[0] & (align - 1);
1880 : return true;
1881 : }
1882 :
1883 : /* Return X & (Y - 1), asserting that this value is known. Please add
1884 : an a comment above callers to this function to explain why the condition
1885 : is known to hold. */
1886 :
1887 : template<unsigned int N, typename Ca, typename Cb>
1888 : inline POLY_BINARY_COEFF (Ca, Ca)
1889 1345684 : force_get_misalignment (const poly_int<N, Ca> &a, Cb align)
1890 : {
1891 : gcc_checking_assert (can_align_p (a, align));
1892 1345684 : return a.coeffs[0] & (align - 1);
1893 : }
1894 :
1895 : /* Return the maximum alignment that A is known to have. Return 0
1896 : if A is known to be zero. */
1897 :
1898 : template<unsigned int N, typename Ca>
1899 : inline POLY_BINARY_COEFF (Ca, Ca)
1900 51844592 : known_alignment (const poly_int<N, Ca> &a)
1901 : {
1902 : typedef POLY_BINARY_COEFF (Ca, Ca) C;
1903 4467167 : C r = a.coeffs[0];
1904 : for (unsigned int i = 1; i < N; ++i)
1905 : r |= a.coeffs[i];
1906 160517729 : return r & -r;
1907 : }
1908 :
1909 : /* Return true if we can compute A & B at compile time, storing the
1910 : result in RES if so. */
1911 :
1912 : template<unsigned int N, typename Ca, typename Cb, typename Cr>
1913 : inline typename if_nonpoly<Cb, bool>::type
1914 : can_and_p (const poly_int<N, Ca> &a, Cb b, Cr *result)
1915 : {
1916 : /* Coefficients 1 and above must be a multiple of something greater
1917 : than ~B. */
1918 : typedef POLY_INT_TYPE (Ca) int_type;
1919 : if (N >= 2)
1920 : for (unsigned int i = 1; i < N; i++)
1921 : if ((-(a.coeffs[i] & -a.coeffs[i]) & ~b) != int_type (0))
1922 : return false;
1923 : *result = a;
1924 : result->coeffs[0] &= b;
1925 : return true;
1926 : }
1927 :
1928 : /* Return true if we can compute A | B at compile time, storing the
1929 : result in RES if so. */
1930 :
1931 : template<unsigned int N, typename Ca, typename Cb, typename Cr>
1932 : inline typename if_nonpoly<Cb, bool>::type
1933 0 : can_ior_p (const poly_int<N, Ca> &a, Cb b, Cr *result)
1934 : {
1935 : /* Coefficients 1 and above must be a multiple of something greater
1936 : than B. */
1937 : typedef POLY_INT_TYPE (Ca) int_type;
1938 : if (N >= 2)
1939 : for (unsigned int i = 1; i < N; i++)
1940 : if ((-(a.coeffs[i] & -a.coeffs[i]) & b) != int_type (0))
1941 : return false;
1942 : *result = a;
1943 0 : result->coeffs[0] |= b;
1944 : return true;
1945 : }
1946 :
1947 : /* Return true if A is a constant multiple of B, storing the
1948 : multiple in *MULTIPLE if so. */
1949 :
1950 : template<unsigned int N, typename Ca, typename Cb, typename Cm>
1951 : inline typename if_nonpoly<Cb, bool>::type
1952 150645 : constant_multiple_p (const poly_int<N, Ca> &a, Cb b, Cm *multiple)
1953 : {
1954 : typedef POLY_CAST (Ca, Cb) NCa;
1955 : typedef POLY_CAST (Cb, Ca) NCb;
1956 :
1957 : /* Do the modulus before the constant check, to catch divide by
1958 : zero errors. */
1959 150645 : if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
1960 : return false;
1961 150645 : *multiple = NCa (a.coeffs[0]) / NCb (b);
1962 117071 : return true;
1963 : }
1964 :
1965 : template<unsigned int N, typename Ca, typename Cb, typename Cm>
1966 : inline typename if_nonpoly<Ca, bool>::type
1967 : constant_multiple_p (Ca a, const poly_int<N, Cb> &b, Cm *multiple)
1968 : {
1969 : typedef POLY_CAST (Ca, Cb) NCa;
1970 : typedef POLY_CAST (Cb, Ca) NCb;
1971 : typedef POLY_INT_TYPE (Ca) int_type;
1972 :
1973 : /* Do the modulus before the constant check, to catch divide by
1974 : zero errors. */
1975 : if (NCa (a) % NCb (b.coeffs[0]) != 0
1976 : || (a != int_type (0) && !b.is_constant ()))
1977 : return false;
1978 : *multiple = NCa (a) / NCb (b.coeffs[0]);
1979 : return true;
1980 : }
1981 :
1982 : template<unsigned int N, typename Ca, typename Cb, typename Cm>
1983 : inline bool
1984 116355476 : constant_multiple_p (const poly_int<N, Ca> &a,
1985 : const poly_int<N, Cb> &b, Cm *multiple)
1986 : {
1987 : typedef POLY_CAST (Ca, Cb) NCa;
1988 : typedef POLY_CAST (Cb, Ca) NCb;
1989 : typedef POLY_INT_TYPE (Ca) ICa;
1990 : typedef POLY_INT_TYPE (Cb) ICb;
1991 : typedef POLY_BINARY_COEFF (Ca, Cb) C;
1992 :
1993 116355476 : if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
1994 : return false;
1995 :
1996 115880132 : C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
1997 39632817 : for (unsigned int i = 1; i < N; ++i)
1998 : if (b.coeffs[i] == ICb (0)
1999 : ? a.coeffs[i] != ICa (0)
2000 : : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2001 : || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2002 : return false;
2003 :
2004 52873022 : *multiple = r;
2005 39632817 : return true;
2006 : }
2007 :
2008 : /* Return true if A is a constant multiple of B. */
2009 :
2010 : template<unsigned int N, typename Ca, typename Cb>
2011 : inline typename if_nonpoly<Cb, bool>::type
2012 22083 : constant_multiple_p (const poly_int<N, Ca> &a, Cb b)
2013 : {
2014 : typedef POLY_CAST (Ca, Cb) NCa;
2015 : typedef POLY_CAST (Cb, Ca) NCb;
2016 :
2017 : /* Do the modulus before the constant check, to catch divide by
2018 : zero errors. */
2019 22083 : if (NCa (a.coeffs[0]) % NCb (b) != 0 || !a.is_constant ())
2020 : return false;
2021 : return true;
2022 : }
2023 :
2024 : template<unsigned int N, typename Ca, typename Cb>
2025 : inline typename if_nonpoly<Ca, bool>::type
2026 : constant_multiple_p (Ca a, const poly_int<N, Cb> &b)
2027 : {
2028 : typedef POLY_CAST (Ca, Cb) NCa;
2029 : typedef POLY_CAST (Cb, Ca) NCb;
2030 : typedef POLY_INT_TYPE (Ca) int_type;
2031 :
2032 : /* Do the modulus before the constant check, to catch divide by
2033 : zero errors. */
2034 : if (NCa (a) % NCb (b.coeffs[0]) != 0
2035 : || (a != int_type (0) && !b.is_constant ()))
2036 : return false;
2037 : return true;
2038 : }
2039 :
2040 : template<unsigned int N, typename Ca, typename Cb>
2041 : inline bool
2042 30352830 : constant_multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2043 : {
2044 : typedef POLY_CAST (Ca, Cb) NCa;
2045 : typedef POLY_CAST (Cb, Ca) NCb;
2046 : typedef POLY_INT_TYPE (Ca) ICa;
2047 : typedef POLY_INT_TYPE (Cb) ICb;
2048 : typedef POLY_BINARY_COEFF (Ca, Cb) C;
2049 :
2050 30352830 : if (NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0)
2051 : return false;
2052 :
2053 : C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2054 : for (unsigned int i = 1; i < N; ++i)
2055 : if (b.coeffs[i] == ICb (0)
2056 : ? a.coeffs[i] != ICa (0)
2057 : : (NCa (a.coeffs[i]) % NCb (b.coeffs[i]) != 0
2058 : || NCa (a.coeffs[i]) / NCb (b.coeffs[i]) != r))
2059 : return false;
2060 : return true;
2061 : }
2062 :
2063 :
2064 : /* Return true if A is a multiple of B. */
2065 :
2066 : template<typename Ca, typename Cb>
2067 : inline typename if_nonpoly2<Ca, Cb, bool>::type
2068 1839879 : multiple_p (Ca a, Cb b)
2069 : {
2070 1839879 : return a % b == 0;
2071 : }
2072 :
2073 : /* Return true if A is a (polynomial) multiple of B. */
2074 :
2075 : template<unsigned int N, typename Ca, typename Cb>
2076 : inline typename if_nonpoly<Cb, bool>::type
2077 416223291 : multiple_p (const poly_int<N, Ca> &a, Cb b)
2078 : {
2079 607598260 : for (unsigned int i = 0; i < N; ++i)
2080 332654859 : if (a.coeffs[i] % b != 0)
2081 : return false;
2082 : return true;
2083 : }
2084 :
2085 : /* Return true if A is a (constant) multiple of B. */
2086 :
2087 : template<unsigned int N, typename Ca, typename Cb>
2088 : inline typename if_nonpoly<Ca, bool>::type
2089 23137282 : multiple_p (Ca a, const poly_int<N, Cb> &b)
2090 : {
2091 : typedef POLY_INT_TYPE (Ca) int_type;
2092 :
2093 : /* Do the modulus before the constant check, to catch divide by
2094 : potential zeros. */
2095 23137282 : return a % b.coeffs[0] == 0 && (a == int_type (0) || b.is_constant ());
2096 : }
2097 :
2098 : /* Return true if A is a (polynomial) multiple of B. This handles cases
2099 : where either B is constant or the multiple is constant. */
2100 :
2101 : template<unsigned int N, typename Ca, typename Cb>
2102 : inline bool
2103 124860378 : multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2104 : {
2105 : if (b.is_constant ())
2106 127829860 : return multiple_p (a, b.coeffs[0]);
2107 : POLY_BINARY_COEFF (Ca, Ca) tmp;
2108 : return constant_multiple_p (a, b, &tmp);
2109 : }
2110 :
2111 : /* Return true if A is a (constant) multiple of B, storing the
2112 : multiple in *MULTIPLE if so. */
2113 :
2114 : template<typename Ca, typename Cb, typename Cm>
2115 : inline typename if_nonpoly2<Ca, Cb, bool>::type
2116 2 : multiple_p (Ca a, Cb b, Cm *multiple)
2117 : {
2118 2 : if (a % b != 0)
2119 : return false;
2120 2 : *multiple = a / b;
2121 : return true;
2122 : }
2123 :
2124 : /* Return true if A is a (polynomial) multiple of B, storing the
2125 : multiple in *MULTIPLE if so. */
2126 :
2127 : template<unsigned int N, typename Ca, typename Cb, typename Cm>
2128 : inline typename if_nonpoly<Cb, bool>::type
2129 130197066 : multiple_p (const poly_int<N, Ca> &a, Cb b, poly_int<N, Cm> *multiple)
2130 : {
2131 110258849 : if (!multiple_p (a, b))
2132 : return false;
2133 149856005 : for (unsigned int i = 0; i < N; ++i)
2134 124219513 : multiple->coeffs[i] = a.coeffs[i] / b;
2135 : return true;
2136 : }
2137 :
2138 : /* Return true if B is a constant and A is a (constant) multiple of B,
2139 : storing the multiple in *MULTIPLE if so. */
2140 :
2141 : template<unsigned int N, typename Ca, typename Cb, typename Cm>
2142 : inline typename if_nonpoly<Ca, bool>::type
2143 42111 : multiple_p (Ca a, const poly_int<N, Cb> &b, Cm *multiple)
2144 : {
2145 : typedef POLY_CAST (Ca, Cb) NCa;
2146 :
2147 : /* Do the modulus before the constant check, to catch divide by
2148 : potential zeros. */
2149 22740 : if (a % b.coeffs[0] != 0 || (NCa (a) != 0 && !b.is_constant ()))
2150 : return false;
2151 19371 : *multiple = a / b.coeffs[0];
2152 : return true;
2153 : }
2154 :
2155 : /* Return true if A is a (polynomial) multiple of B, storing the
2156 : multiple in *MULTIPLE if so. This handles cases where either
2157 : B is constant or the multiple is constant. */
2158 :
2159 : template<unsigned int N, typename Ca, typename Cb, typename Cm>
2160 : inline bool
2161 16361087 : multiple_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2162 : poly_int<N, Cm> *multiple)
2163 : {
2164 : if (b.is_constant ())
2165 16361087 : return multiple_p (a, b.coeffs[0], multiple);
2166 : return constant_multiple_p (a, b, multiple);
2167 : }
2168 :
2169 : /* Return A / B, given that A is known to be a multiple of B. */
2170 :
2171 : template<unsigned int N, typename Ca, typename Cb>
2172 : inline POLY_CONST_RESULT (N, Ca, Cb)
2173 66617878 : exact_div (const poly_int<N, Ca> &a, Cb b)
2174 : {
2175 : typedef POLY_CONST_COEFF (Ca, Cb) C;
2176 : poly_int<N, C> r;
2177 133235756 : for (unsigned int i = 0; i < N; i++)
2178 : {
2179 66617878 : gcc_checking_assert (a.coeffs[i] % b == 0);
2180 66617878 : POLY_SET_COEFF (C, r, i, a.coeffs[i] / b);
2181 : }
2182 66617878 : return r;
2183 : }
2184 :
2185 : /* Return A / B, given that A is known to be a multiple of B. */
2186 :
2187 : template<unsigned int N, typename Ca, typename Cb>
2188 : inline POLY_POLY_RESULT (N, Ca, Cb)
2189 11483654 : exact_div (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b)
2190 : {
2191 : if (b.is_constant ())
2192 11353869 : return exact_div (a, b.coeffs[0]);
2193 :
2194 : typedef POLY_CAST (Ca, Cb) NCa;
2195 : typedef POLY_CAST (Cb, Ca) NCb;
2196 : typedef POLY_BINARY_COEFF (Ca, Cb) C;
2197 : typedef POLY_INT_TYPE (Cb) int_type;
2198 :
2199 : gcc_checking_assert (a.coeffs[0] % b.coeffs[0] == 0);
2200 : C r = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2201 : for (unsigned int i = 1; i < N; ++i)
2202 : gcc_checking_assert (b.coeffs[i] == int_type (0)
2203 : ? a.coeffs[i] == int_type (0)
2204 : : (a.coeffs[i] % b.coeffs[i] == 0
2205 : && NCa (a.coeffs[i]) / NCb (b.coeffs[i]) == r));
2206 :
2207 : return r;
2208 : }
2209 :
2210 : /* Return true if there is some constant Q and polynomial r such that:
2211 :
2212 : (1) a = b * Q + r
2213 : (2) |b * Q| <= |a|
2214 : (3) |r| < |b|
2215 :
2216 : Store the value Q in *QUOTIENT if so. */
2217 :
2218 : template<unsigned int N, typename Ca, typename Cb, typename Cq>
2219 : inline typename if_nonpoly2<Cb, Cq, bool>::type
2220 1018892 : can_div_trunc_p (const poly_int<N, Ca> &a, Cb b, Cq *quotient)
2221 : {
2222 : typedef POLY_CAST (Ca, Cb) NCa;
2223 : typedef POLY_CAST (Cb, Ca) NCb;
2224 :
2225 : /* Do the division before the constant check, to catch divide by
2226 : zero errors. */
2227 1018892 : Cq q = NCa (a.coeffs[0]) / NCb (b);
2228 : if (!a.is_constant ())
2229 : return false;
2230 1018892 : *quotient = q;
2231 : return true;
2232 : }
2233 :
2234 : template<unsigned int N, typename Ca, typename Cb, typename Cq>
2235 : inline typename if_nonpoly<Cq, bool>::type
2236 71421638 : can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2237 : Cq *quotient)
2238 : {
2239 : /* We can calculate Q from the case in which the indeterminates
2240 : are zero. */
2241 : typedef POLY_CAST (Ca, Cb) NCa;
2242 : typedef POLY_CAST (Cb, Ca) NCb;
2243 : typedef POLY_INT_TYPE (Ca) ICa;
2244 : typedef POLY_INT_TYPE (Cb) ICb;
2245 : typedef POLY_BINARY_COEFF (Ca, Cb) C;
2246 121618627 : C q = NCa (a.coeffs[0]) / NCb (b.coeffs[0]);
2247 :
2248 : /* Check the other coefficients and record whether the division is exact.
2249 : The only difficult case is when it isn't. If we require a and b to
2250 : ordered wrt zero, there can be no two coefficients of the same value
2251 : that have opposite signs. This means that:
2252 :
2253 : |a| = |a0| + |a1 * x1| + |a2 * x2| + ...
2254 : |b| = |b0| + |b1 * x1| + |b2 * x2| + ...
2255 :
2256 : The Q we've just calculated guarantees:
2257 :
2258 : |b0 * Q| <= |a0|
2259 : |a0 - b0 * Q| < |b0|
2260 :
2261 : and so:
2262 :
2263 : (2) |b * Q| <= |a|
2264 :
2265 : is satisfied if:
2266 :
2267 : |bi * xi * Q| <= |ai * xi|
2268 :
2269 : for each i in [1, N]. This is trivially true when xi is zero.
2270 : When it isn't we need:
2271 :
2272 : (2') |bi * Q| <= |ai|
2273 :
2274 : r is calculated as:
2275 :
2276 : r = r0 + r1 * x1 + r2 * x2 + ...
2277 : where ri = ai - bi * Q
2278 :
2279 : Restricting to ordered a and b also guarantees that no two ris
2280 : have opposite signs, so we have:
2281 :
2282 : |r| = |r0| + |r1 * x1| + |r2 * x2| + ...
2283 :
2284 : We know from the calculation of Q that |r0| < |b0|, so:
2285 :
2286 : (3) |r| < |b|
2287 :
2288 : is satisfied if:
2289 :
2290 : (3') |ai - bi * Q| <= |bi|
2291 :
2292 : for each i in [1, N]. */
2293 121618627 : bool rem_p = NCa (a.coeffs[0]) % NCb (b.coeffs[0]) != 0;
2294 : for (unsigned int i = 1; i < N; ++i)
2295 : {
2296 : if (b.coeffs[i] == ICb (0))
2297 : {
2298 : /* For bi == 0 we simply need: (3') |ai| == 0. */
2299 : if (a.coeffs[i] != ICa (0))
2300 : return false;
2301 : }
2302 : else
2303 : {
2304 : /* The only unconditional arithmetic that we can do on ai,
2305 : bi and Q is ai / bi and ai % bi. (ai == minimum int and
2306 : bi == -1 would be UB in the caller.) Anything else runs
2307 : the risk of overflow. */
2308 : auto qi = NCa (a.coeffs[i]) / NCb (b.coeffs[i]);
2309 : auto ri = NCa (a.coeffs[i]) % NCb (b.coeffs[i]);
2310 : /* (2') and (3') are satisfied when ai /[trunc] bi == q.
2311 : So is the stricter condition |ai - bi * Q| < |bi|. */
2312 : if (qi == q)
2313 : rem_p |= (ri != 0);
2314 : /* The only other case is when:
2315 :
2316 : |bi * Q| + |bi| = |ai| (for (2'))
2317 : and |ai - bi * Q| = |bi| (for (3'))
2318 :
2319 : The first is equivalent to |bi|(|Q| + 1) == |ai|.
2320 : The second requires ai == bi * (Q + 1) or ai == bi * (Q - 1). */
2321 : else if (ri != 0)
2322 : return false;
2323 : else if (q <= 0 && qi < q && qi + 1 == q)
2324 : ;
2325 : else if (q >= 0 && qi > q && qi - 1 == q)
2326 : ;
2327 : else
2328 : return false;
2329 : }
2330 : }
2331 :
2332 : /* If the division isn't exact, require both values to be ordered wrt 0,
2333 : so that we can guarantee conditions (2) and (3) for all indeterminate
2334 : values. */
2335 : if (rem_p && (!ordered_p (a, ICa (0)) || !ordered_p (b, ICb (0))))
2336 : return false;
2337 :
2338 121110504 : *quotient = q;
2339 : return true;
2340 : }
2341 :
2342 : /* Likewise, but also store r in *REMAINDER. */
2343 :
2344 : template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2345 : inline typename if_nonpoly<Cq, bool>::type
2346 14763579 : can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2347 : Cq *quotient, Cr *remainder)
2348 : {
2349 64960568 : if (!can_div_trunc_p (a, b, quotient))
2350 : return false;
2351 64960568 : *remainder = a - *quotient * b;
2352 : return true;
2353 : }
2354 :
2355 : /* Return true if there is some polynomial q and constant R such that:
2356 :
2357 : (1) a = B * q + R
2358 : (2) |B * q| <= |a|
2359 : (3) |R| < |B|
2360 :
2361 : Store the value q in *QUOTIENT if so. */
2362 :
2363 : template<unsigned int N, typename Ca, typename Cb, typename Cq>
2364 : inline typename if_nonpoly<Cb, bool>::type
2365 705697 : can_div_trunc_p (const poly_int<N, Ca> &a, Cb b,
2366 : poly_int<N, Cq> *quotient)
2367 : {
2368 : /* The remainder must be constant. */
2369 705697 : for (unsigned int i = 1; i < N; ++i)
2370 : if (a.coeffs[i] % b != 0)
2371 : return false;
2372 705697 : for (unsigned int i = 0; i < N; ++i)
2373 705697 : quotient->coeffs[i] = a.coeffs[i] / b;
2374 : return true;
2375 : }
2376 :
2377 : /* Likewise, but also store R in *REMAINDER. */
2378 :
2379 : template<unsigned int N, typename Ca, typename Cb, typename Cq, typename Cr>
2380 : inline typename if_nonpoly<Cb, bool>::type
2381 275150 : can_div_trunc_p (const poly_int<N, Ca> &a, Cb b,
2382 : poly_int<N, Cq> *quotient, Cr *remainder)
2383 : {
2384 275150 : if (!can_div_trunc_p (a, b, quotient))
2385 : return false;
2386 275150 : *remainder = a.coeffs[0] % b;
2387 : return true;
2388 : }
2389 :
2390 : /* Return true if we can compute A / B at compile time, rounding towards zero.
2391 : Store the result in QUOTIENT if so.
2392 :
2393 : This handles cases in which either B is constant or the result is
2394 : constant. */
2395 :
2396 : template<unsigned int N, typename Ca, typename Cb, typename Cq>
2397 : inline bool
2398 300864 : can_div_trunc_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2399 : poly_int<N, Cq> *quotient)
2400 : {
2401 : if (b.is_constant ())
2402 300864 : return can_div_trunc_p (a, b.coeffs[0], quotient);
2403 : if (!can_div_trunc_p (a, b, "ient->coeffs[0]))
2404 : return false;
2405 : for (unsigned int i = 1; i < N; ++i)
2406 : quotient->coeffs[i] = 0;
2407 : return true;
2408 : }
2409 :
2410 : /* Return true if there is some constant Q and polynomial r such that:
2411 :
2412 : (1) a = b * Q + r
2413 : (2) |a| <= |b * Q|
2414 : (3) |r| < |b|
2415 :
2416 : Store the value Q in *QUOTIENT if so. */
2417 :
2418 : template<unsigned int N, typename Ca, typename Cb, typename Cq>
2419 : inline typename if_nonpoly<Cq, bool>::type
2420 56657940 : can_div_away_from_zero_p (const poly_int<N, Ca> &a, const poly_int<N, Cb> &b,
2421 : Cq *quotient)
2422 : {
2423 56657940 : if (!can_div_trunc_p (a, b, quotient))
2424 : return false;
2425 44404016 : if (maybe_ne (*quotient * b, a))
2426 29729546 : *quotient += (*quotient < 0 ? -1 : 1);
2427 : return true;
2428 : }
2429 :
2430 : /* Use print_dec to print VALUE to FILE, where SGN is the sign
2431 : of the values. */
2432 :
2433 : template<unsigned int N, typename C>
2434 : void
2435 3143 : print_dec (const poly_int<N, C> &value, FILE *file, signop sgn)
2436 : {
2437 : if (value.is_constant ())
2438 3143 : print_dec (value.coeffs[0], file, sgn);
2439 : else
2440 : {
2441 : fprintf (file, "[");
2442 : for (unsigned int i = 0; i < N; ++i)
2443 : {
2444 : print_dec (value.coeffs[i], file, sgn);
2445 : fputc (i == N - 1 ? ']' : ',', file);
2446 : }
2447 : }
2448 3143 : }
2449 :
2450 : /* Likewise without the signop argument, for coefficients that have an
2451 : inherent signedness. */
2452 :
2453 : template<unsigned int N, typename C>
2454 : void
2455 1585 : print_dec (const poly_int<N, C> &value, FILE *file)
2456 : {
2457 : STATIC_ASSERT (poly_coeff_traits<C>::signedness >= 0);
2458 1585 : print_dec (value, file,
2459 : poly_coeff_traits<C>::signedness ? SIGNED : UNSIGNED);
2460 : }
2461 :
2462 : /* Use print_hex to print VALUE to FILE. */
2463 :
2464 : template<unsigned int N, typename C>
2465 : void
2466 168238 : print_hex (const poly_int<N, C> &value, FILE *file)
2467 : {
2468 : if (value.is_constant ())
2469 168238 : print_hex (value.coeffs[0], file);
2470 : else
2471 : {
2472 : fprintf (file, "[");
2473 : for (unsigned int i = 0; i < N; ++i)
2474 : {
2475 : print_hex (value.coeffs[i], file);
2476 : fputc (i == N - 1 ? ']' : ',', file);
2477 : }
2478 : }
2479 168238 : }
2480 :
2481 : /* Helper for calculating the distance between two points P1 and P2,
2482 : in cases where known_le (P1, P2). T1 and T2 are the types of the
2483 : two positions, in either order. The coefficients of P2 - P1 have
2484 : type unsigned HOST_WIDE_INT if the coefficients of both T1 and T2
2485 : have C++ primitive type, otherwise P2 - P1 has its usual
2486 : wide-int-based type.
2487 :
2488 : The actual subtraction should look something like this:
2489 :
2490 : typedef poly_span_traits<T1, T2> span_traits;
2491 : span_traits::cast (P2) - span_traits::cast (P1)
2492 :
2493 : Applying the cast before the subtraction avoids undefined overflow
2494 : for signed T1 and T2.
2495 :
2496 : The implementation of the cast tries to avoid unnecessary arithmetic
2497 : or copying. */
2498 : template<typename T1, typename T2,
2499 : typename Res = POLY_BINARY_COEFF (POLY_BINARY_COEFF (T1, T2),
2500 : unsigned HOST_WIDE_INT)>
2501 : struct poly_span_traits
2502 : {
2503 : template<typename T>
2504 : static const T &cast (const T &x) { return x; }
2505 : };
2506 :
2507 : template<typename T1, typename T2>
2508 : struct poly_span_traits<T1, T2, unsigned HOST_WIDE_INT>
2509 : {
2510 : template<typename T>
2511 : static typename if_nonpoly<T, unsigned HOST_WIDE_INT>::type
2512 6078304 : cast (const T &x) { return x; }
2513 :
2514 : template<unsigned int N, typename T>
2515 : static poly_int<N, unsigned HOST_WIDE_INT>
2516 464006277 : cast (const poly_int<N, T> &x) { return x; }
2517 : };
2518 :
2519 : /* Return true if SIZE represents a known size, assuming that all-ones
2520 : indicates an unknown size. */
2521 :
2522 : template<typename T>
2523 : inline bool
2524 9651970406 : known_size_p (const T &a)
2525 : {
2526 5780592436 : return maybe_ne (a, POLY_INT_TYPE (T) (-1));
2527 : }
2528 :
2529 : /* Return true if range [POS, POS + SIZE) might include VAL.
2530 : SIZE can be the special value -1, in which case the range is
2531 : open-ended. */
2532 :
2533 : template<typename T1, typename T2, typename T3>
2534 : inline bool
2535 952799583 : maybe_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2536 : {
2537 : typedef poly_span_traits<T1, T2> start_span;
2538 : typedef poly_span_traits<T3, T3> size_span;
2539 952762053 : if (known_lt (val, pos))
2540 : return false;
2541 590214474 : if (!known_size_p (size))
2542 : return true;
2543 : if ((poly_int_traits<T1>::num_coeffs > 1
2544 : || poly_int_traits<T2>::num_coeffs > 1)
2545 : && maybe_lt (val, pos))
2546 : /* In this case we don't know whether VAL >= POS is true at compile
2547 : time, so we can't prove that VAL >= POS + SIZE. */
2548 : return true;
2549 401251232 : return maybe_lt (start_span::cast (val) - start_span::cast (pos),
2550 521154042 : size_span::cast (size));
2551 : }
2552 :
2553 : /* Return true if range [POS, POS + SIZE) is known to include VAL.
2554 : SIZE can be the special value -1, in which case the range is
2555 : open-ended. */
2556 :
2557 : template<typename T1, typename T2, typename T3>
2558 : inline bool
2559 13786379 : known_in_range_p (const T1 &val, const T2 &pos, const T3 &size)
2560 : {
2561 : typedef poly_span_traits<T1, T2> start_span;
2562 : typedef poly_span_traits<T3, T3> size_span;
2563 13786379 : return (known_size_p (size)
2564 13786379 : && known_ge (val, pos)
2565 26451923 : && known_lt (start_span::cast (val) - start_span::cast (pos),
2566 : size_span::cast (size)));
2567 : }
2568 :
2569 : /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2570 : might overlap. SIZE1 and/or SIZE2 can be the special value -1, in which
2571 : case the range is open-ended. */
2572 :
2573 : template<typename T1, typename T2, typename T3, typename T4>
2574 : inline bool
2575 590211794 : ranges_maybe_overlap_p (const T1 &pos1, const T2 &size1,
2576 : const T3 &pos2, const T4 &size2)
2577 : {
2578 589842267 : if (maybe_in_range_p (pos2, pos1, size1))
2579 227623448 : return maybe_ne (size2, POLY_INT_TYPE (T4) (0));
2580 314578464 : if (maybe_in_range_p (pos1, pos2, size2))
2581 67256223 : return maybe_ne (size1, POLY_INT_TYPE (T2) (0));
2582 : return false;
2583 : }
2584 :
2585 : /* Return true if the two ranges [POS1, POS1 + SIZE1) and [POS2, POS2 + SIZE2)
2586 : are known to overlap. SIZE1 and/or SIZE2 can be the special value -1,
2587 : in which case the range is open-ended. */
2588 :
2589 : template<typename T1, typename T2, typename T3, typename T4>
2590 : inline bool
2591 1423263 : ranges_known_overlap_p (const T1 &pos1, const T2 &size1,
2592 : const T3 &pos2, const T4 &size2)
2593 : {
2594 : typedef poly_span_traits<T1, T3> start_span;
2595 : typedef poly_span_traits<T2, T2> size1_span;
2596 : typedef poly_span_traits<T4, T4> size2_span;
2597 : /* known_gt (POS1 + SIZE1, POS2) [infinite precision]
2598 : --> known_gt (SIZE1, POS2 - POS1) [infinite precision]
2599 : --> known_gt (SIZE1, POS2 - lower_bound (POS1, POS2)) [infinite precision]
2600 : ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ always nonnegative
2601 : --> known_gt (SIZE1, span1::cast (POS2 - lower_bound (POS1, POS2))).
2602 :
2603 : Using the saturating subtraction enforces that SIZE1 must be
2604 : nonzero, since known_gt (0, x) is false for all nonnegative x.
2605 : If POS2.coeff[I] < POS1.coeff[I] for some I > 0, increasing
2606 : indeterminate number I makes the unsaturated condition easier to
2607 : satisfy, so using a saturated coefficient of zero tests the case in
2608 : which the indeterminate is zero (the minimum value). */
2609 1423263 : return (known_size_p (size1)
2610 1337017 : && known_size_p (size2)
2611 1337013 : && known_lt (start_span::cast (pos2)
2612 : - start_span::cast (lower_bound (pos1, pos2)),
2613 : size1_span::cast (size1))
2614 2575567 : && known_lt (start_span::cast (pos1)
2615 : - start_span::cast (lower_bound (pos1, pos2)),
2616 1423263 : size2_span::cast (size2)));
2617 : }
2618 :
2619 : /* Return true if range [POS1, POS1 + SIZE1) is known to be a subrange of
2620 : [POS2, POS2 + SIZE2). SIZE1 and/or SIZE2 can be the special value -1,
2621 : in which case the range is open-ended. */
2622 :
2623 : template<typename T1, typename T2, typename T3, typename T4>
2624 : inline bool
2625 273326812 : known_subrange_p (const T1 &pos1, const T2 &size1,
2626 : const T3 &pos2, const T4 &size2)
2627 : {
2628 : typedef typename poly_int_traits<T2>::coeff_type C2;
2629 : typedef poly_span_traits<T1, T3> start_span;
2630 : typedef poly_span_traits<T2, T4> size_span;
2631 273326812 : return (known_gt (size1, POLY_INT_TYPE (T2) (0))
2632 12800 : && (poly_coeff_traits<C2>::signedness > 0
2633 12800 : || known_size_p (size1))
2634 273260861 : && known_size_p (size2)
2635 272532935 : && known_ge (pos1, pos2)
2636 75841438 : && known_le (size1, size2)
2637 335817170 : && known_le (start_span::cast (pos1) - start_span::cast (pos2),
2638 273326812 : size_span::cast (size2) - size_span::cast (size1)));
2639 : }
2640 :
2641 : /* Return true if the endpoint of the range [POS, POS + SIZE) can be
2642 : stored in a T, or if SIZE is the special value -1, which makes the
2643 : range open-ended. */
2644 :
2645 : template<typename T>
2646 : inline typename if_nonpoly<T, bool>::type
2647 : endpoint_representable_p (const T &pos, const T &size)
2648 : {
2649 : return (!known_size_p (size)
2650 : || pos <= poly_coeff_traits<T>::max_value - size);
2651 : }
2652 :
2653 : template<unsigned int N, typename C>
2654 : inline bool
2655 6142430472 : endpoint_representable_p (const poly_int<N, C> &pos,
2656 : const poly_int<N, C> &size)
2657 : {
2658 3078806449 : if (known_size_p (size))
2659 6142430260 : for (unsigned int i = 0; i < N; ++i)
2660 6142430472 : if (pos.coeffs[i] > poly_coeff_traits<C>::max_value - size.coeffs[i])
2661 : return false;
2662 : return true;
2663 : }
2664 :
2665 : template<unsigned int N, typename C>
2666 : void
2667 : gt_ggc_mx (poly_int<N, C> *)
2668 : {
2669 : }
2670 :
2671 : template<unsigned int N, typename C>
2672 : void
2673 : gt_pch_nx (poly_int<N, C> *)
2674 : {
2675 : }
2676 :
2677 : template<unsigned int N, typename C>
2678 : void
2679 : gt_pch_nx (poly_int<N, C> *, gt_pointer_operator, void *)
2680 : {
2681 : }
2682 :
2683 : #undef POLY_SET_COEFF
2684 : #undef POLY_INT_TYPE
2685 : #undef POLY_BINARY_COEFF
2686 : #undef CONST_CONST_RESULT
2687 : #undef POLY_CONST_RESULT
2688 : #undef CONST_POLY_RESULT
2689 : #undef POLY_POLY_RESULT
2690 : #undef POLY_CONST_COEFF
2691 : #undef CONST_POLY_COEFF
2692 : #undef POLY_POLY_COEFF
2693 :
2694 : #endif
|
