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