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