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