Mercurial > hg > CbC > CbC_gcc

comparison gcc/poly-int.h @ 132:d34655255c78

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