Line data Source code
1 : /* Operations with very long integers. -*- C++ -*-
2 : Copyright (C) 2012-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it
7 : under the terms of the GNU General Public License as published by the
8 : Free Software Foundation; either version 3, or (at your option) any
9 : later version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT
12 : ANY 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 : #ifndef WIDE_INT_H
21 : #define WIDE_INT_H
22 :
23 : /* wide-int.[cc|h] implements a class that efficiently performs
24 : mathematical operations on finite precision integers. wide_ints
25 : are designed to be transient - they are not for long term storage
26 : of values. There is tight integration between wide_ints and the
27 : other longer storage GCC representations (rtl and tree).
28 :
29 : The actual precision of a wide_int depends on the flavor. There
30 : are three predefined flavors:
31 :
32 : 1) wide_int (the default). This flavor does the math in the
33 : precision of its input arguments. It is assumed (and checked)
34 : that the precisions of the operands and results are consistent.
35 : This is the most efficient flavor. It is not possible to examine
36 : bits above the precision that has been specified. Because of
37 : this, the default flavor has semantics that are simple to
38 : understand and in general model the underlying hardware that the
39 : compiler is targetted for.
40 :
41 : This flavor must be used at the RTL level of gcc because there
42 : is, in general, not enough information in the RTL representation
43 : to extend a value beyond the precision specified in the mode.
44 :
45 : This flavor should also be used at the TREE and GIMPLE levels of
46 : the compiler except for the circumstances described in the
47 : descriptions of the other two flavors.
48 :
49 : The default wide_int representation does not contain any
50 : information inherent about signedness of the represented value,
51 : so it can be used to represent both signed and unsigned numbers.
52 : For operations where the results depend on signedness (full width
53 : multiply, division, shifts, comparisons, and operations that need
54 : overflow detected), the signedness must be specified separately.
55 :
56 : For precisions up to WIDE_INT_MAX_INL_PRECISION, it uses an inline
57 : buffer in the type, for larger precisions up to WIDEST_INT_MAX_PRECISION
58 : it uses a pointer to heap allocated buffer.
59 :
60 : 2) offset_int. This is a fixed-precision integer that can hold
61 : any address offset, measured in either bits or bytes, with at
62 : least one extra sign bit. At the moment the maximum address
63 : size GCC supports is 64 bits. With 8-bit bytes and an extra
64 : sign bit, offset_int therefore needs to have at least 68 bits
65 : of precision. We round this up to 128 bits for efficiency.
66 : Values of type T are converted to this precision by sign- or
67 : zero-extending them based on the signedness of T.
68 :
69 : The extra sign bit means that offset_int is effectively a signed
70 : 128-bit integer, i.e. it behaves like int128_t.
71 :
72 : Since the values are logically signed, there is no need to
73 : distinguish between signed and unsigned operations. Sign-sensitive
74 : comparison operators <, <=, > and >= are therefore supported.
75 : Shift operators << and >> are also supported, with >> being
76 : an _arithmetic_ right shift.
77 :
78 : [ Note that, even though offset_int is effectively int128_t,
79 : it can still be useful to use unsigned comparisons like
80 : wi::leu_p (a, b) as a more efficient short-hand for
81 : "a >= 0 && a <= b". ]
82 :
83 : 3) widest_int. This representation is an approximation of
84 : infinite precision math. However, it is not really infinite
85 : precision math as in the GMP library. It is really finite
86 : precision math where the precision is WIDEST_INT_MAX_PRECISION.
87 :
88 : Like offset_int, widest_int is wider than all the values that
89 : it needs to represent, so the integers are logically signed.
90 : Sign-sensitive comparison operators <, <=, > and >= are supported,
91 : as are << and >>.
92 :
93 : There are several places in the GCC where this should/must be used:
94 :
95 : * Code that does induction variable optimizations. This code
96 : works with induction variables of many different types at the
97 : same time. Because of this, it ends up doing many different
98 : calculations where the operands are not compatible types. The
99 : widest_int makes this easy, because it provides a field where
100 : nothing is lost when converting from any variable,
101 :
102 : * There are a small number of passes that currently use the
103 : widest_int that should use the default. These should be
104 : changed.
105 :
106 : There are surprising features of offset_int and widest_int
107 : that the users should be careful about:
108 :
109 : 1) Shifts and rotations are just weird. You have to specify a
110 : precision in which the shift or rotate is to happen in. The bits
111 : above this precision are zeroed. While this is what you
112 : want, it is clearly non obvious.
113 :
114 : 2) Larger precision math sometimes does not produce the same
115 : answer as would be expected for doing the math at the proper
116 : precision. In particular, a multiply followed by a divide will
117 : produce a different answer if the first product is larger than
118 : what can be represented in the input precision.
119 :
120 : The offset_int and the widest_int flavors are more expensive
121 : than the default wide int, so in addition to the caveats with these
122 : two, the default is the prefered representation.
123 :
124 : All three flavors of wide_int are represented as a vector of
125 : HOST_WIDE_INTs. The default and widest_int vectors contain enough elements
126 : to hold a value of MAX_BITSIZE_MODE_ANY_INT bits. offset_int contains only
127 : enough elements to hold ADDR_MAX_PRECISION bits. The values are stored
128 : in the vector with the least significant HOST_BITS_PER_WIDE_INT bits
129 : in element 0.
130 :
131 : The default wide_int contains three fields: the vector (VAL),
132 : the precision and a length (LEN). The length is the number of HWIs
133 : needed to represent the value. widest_int and offset_int have a
134 : constant precision that cannot be changed, so they only store the
135 : VAL and LEN fields.
136 :
137 : Since most integers used in a compiler are small values, it is
138 : generally profitable to use a representation of the value that is
139 : as small as possible. LEN is used to indicate the number of
140 : elements of the vector that are in use. The numbers are stored as
141 : sign extended numbers as a means of compression. Leading
142 : HOST_WIDE_INTs that contain strings of either -1 or 0 are removed
143 : as long as they can be reconstructed from the top bit that is being
144 : represented.
145 :
146 : The precision and length of a wide_int are always greater than 0.
147 : Any bits in a wide_int above the precision are sign-extended from the
148 : most significant bit. For example, a 4-bit value 0x8 is represented as
149 : VAL = { 0xf...fff8 }. However, as an optimization, we allow other integer
150 : constants to be represented with undefined bits above the precision.
151 : This allows INTEGER_CSTs to be pre-extended according to TYPE_SIGN,
152 : so that the INTEGER_CST representation can be used both in TYPE_PRECISION
153 : and in wider precisions.
154 :
155 : There are constructors to create the various forms of wide_int from
156 : trees, rtl and constants. For trees the options are:
157 :
158 : tree t = ...;
159 : wi::to_wide (t) // Treat T as a wide_int
160 : wi::to_offset (t) // Treat T as an offset_int
161 : wi::to_widest (t) // Treat T as a widest_int
162 :
163 : All three are light-weight accessors that should have no overhead
164 : in release builds. If it is useful for readability reasons to
165 : store the result in a temporary variable, the preferred method is:
166 :
167 : wi::tree_to_wide_ref twide = wi::to_wide (t);
168 : wi::tree_to_offset_ref toffset = wi::to_offset (t);
169 : wi::tree_to_widest_ref twidest = wi::to_widest (t);
170 :
171 : To make an rtx into a wide_int, you have to pair it with a mode.
172 : The canonical way to do this is with rtx_mode_t as in:
173 :
174 : rtx r = ...
175 : wide_int x = rtx_mode_t (r, mode);
176 :
177 : Similarly, a wide_int can only be constructed from a host value if
178 : the target precision is given explicitly, such as in:
179 :
180 : wide_int x = wi::shwi (c, prec); // sign-extend C if necessary
181 : wide_int y = wi::uhwi (c, prec); // zero-extend C if necessary
182 :
183 : However, offset_int and widest_int have an inherent precision and so
184 : can be initialized directly from a host value:
185 :
186 : offset_int x = (int) c; // sign-extend C
187 : widest_int x = (unsigned int) c; // zero-extend C
188 :
189 : It is also possible to do arithmetic directly on rtx_mode_ts and
190 : constants. For example:
191 :
192 : wi::add (r1, r2); // add equal-sized rtx_mode_ts r1 and r2
193 : wi::add (r1, 1); // add 1 to rtx_mode_t r1
194 : wi::lshift (1, 100); // 1 << 100 as a widest_int
195 :
196 : Many binary operations place restrictions on the combinations of inputs,
197 : using the following rules:
198 :
199 : - {rtx, wide_int} op {rtx, wide_int} -> wide_int
200 : The inputs must be the same precision. The result is a wide_int
201 : of the same precision
202 :
203 : - {rtx, wide_int} op (un)signed HOST_WIDE_INT -> wide_int
204 : (un)signed HOST_WIDE_INT op {rtx, wide_int} -> wide_int
205 : The HOST_WIDE_INT is extended or truncated to the precision of
206 : the other input. The result is a wide_int of the same precision
207 : as that input.
208 :
209 : - (un)signed HOST_WIDE_INT op (un)signed HOST_WIDE_INT -> widest_int
210 : The inputs are extended to widest_int precision and produce a
211 : widest_int result.
212 :
213 : - offset_int op offset_int -> offset_int
214 : offset_int op (un)signed HOST_WIDE_INT -> offset_int
215 : (un)signed HOST_WIDE_INT op offset_int -> offset_int
216 :
217 : - widest_int op widest_int -> widest_int
218 : widest_int op (un)signed HOST_WIDE_INT -> widest_int
219 : (un)signed HOST_WIDE_INT op widest_int -> widest_int
220 :
221 : Other combinations like:
222 :
223 : - widest_int op offset_int and
224 : - wide_int op offset_int
225 :
226 : are not allowed. The inputs should instead be extended or truncated
227 : so that they match.
228 :
229 : The inputs to comparison functions like wi::eq_p and wi::lts_p
230 : follow the same compatibility rules, although their return types
231 : are different. Unary functions on X produce the same result as
232 : a binary operation X + X. Shift functions X op Y also produce
233 : the same result as X + X; the precision of the shift amount Y
234 : can be arbitrarily different from X. */
235 :
236 : /* The MAX_BITSIZE_MODE_ANY_INT is automatically generated by a very
237 : early examination of the target's mode file. The WIDE_INT_MAX_INL_ELTS
238 : can accommodate at least 1 more bit so that unsigned numbers of that
239 : mode can be represented as a signed value. Note that it is still
240 : possible to create fixed_wide_ints that have precisions greater than
241 : MAX_BITSIZE_MODE_ANY_INT. This can be useful when representing a
242 : double-width multiplication result, for example. */
243 : #define WIDE_INT_MAX_INL_ELTS \
244 : ((MAX_BITSIZE_MODE_ANY_INT + HOST_BITS_PER_WIDE_INT) \
245 : / HOST_BITS_PER_WIDE_INT)
246 :
247 : #define WIDE_INT_MAX_INL_PRECISION \
248 : (WIDE_INT_MAX_INL_ELTS * HOST_BITS_PER_WIDE_INT)
249 :
250 : /* Precision of wide_int and largest _BitInt precision + 1 we can
251 : support. */
252 : #define WIDE_INT_MAX_ELTS 1024
253 : #define WIDE_INT_MAX_PRECISION (WIDE_INT_MAX_ELTS * HOST_BITS_PER_WIDE_INT)
254 :
255 : /* Precision of widest_int. */
256 : #define WIDEST_INT_MAX_ELTS 2048
257 : #define WIDEST_INT_MAX_PRECISION (WIDEST_INT_MAX_ELTS * HOST_BITS_PER_WIDE_INT)
258 :
259 : STATIC_ASSERT (WIDE_INT_MAX_INL_ELTS < WIDE_INT_MAX_ELTS);
260 :
261 : /* This is the max size of any pointer on any machine. It does not
262 : seem to be as easy to sniff this out of the machine description as
263 : it is for MAX_BITSIZE_MODE_ANY_INT since targets may support
264 : multiple address sizes and may have different address sizes for
265 : different address spaces. However, currently the largest pointer
266 : on any platform is 64 bits. When that changes, then it is likely
267 : that a target hook should be defined so that targets can make this
268 : value larger for those targets. */
269 : #define ADDR_MAX_BITSIZE 64
270 :
271 : /* This is the internal precision used when doing any address
272 : arithmetic. The '4' is really 3 + 1. Three of the bits are for
273 : the number of extra bits needed to do bit addresses and the other bit
274 : is to allow everything to be signed without loosing any precision.
275 : Then everything is rounded up to the next HWI for efficiency. */
276 : #define ADDR_MAX_PRECISION \
277 : ((ADDR_MAX_BITSIZE + 4 + HOST_BITS_PER_WIDE_INT - 1) \
278 : & ~(HOST_BITS_PER_WIDE_INT - 1))
279 :
280 : /* The number of HWIs needed to store an offset_int. */
281 : #define OFFSET_INT_ELTS (ADDR_MAX_PRECISION / HOST_BITS_PER_WIDE_INT)
282 :
283 : /* The max number of HWIs needed to store a wide_int of PRECISION. */
284 : #define WIDE_INT_MAX_HWIS(PRECISION) \
285 : ((PRECISION + HOST_BITS_PER_WIDE_INT - 1) / HOST_BITS_PER_WIDE_INT)
286 :
287 : /* The type of result produced by a binary operation on types T1 and T2.
288 : Defined purely for brevity. */
289 : #define WI_BINARY_RESULT(T1, T2) \
290 : typename wi::binary_traits <T1, T2>::result_type
291 :
292 : /* Likewise for binary operators, which excludes the case in which neither
293 : T1 nor T2 is a wide-int-based type. */
294 : #define WI_BINARY_OPERATOR_RESULT(T1, T2) \
295 : typename wi::binary_traits <T1, T2>::operator_result
296 :
297 : /* The type of result produced by T1 << T2. Leads to substitution failure
298 : if the operation isn't supported. Defined purely for brevity. */
299 : #define WI_SIGNED_SHIFT_RESULT(T1, T2) \
300 : typename wi::binary_traits <T1, T2>::signed_shift_result_type
301 :
302 : /* The type of result produced by a sign-agnostic binary predicate on
303 : types T1 and T2. This is bool if wide-int operations make sense for
304 : T1 and T2 and leads to substitution failure otherwise. */
305 : #define WI_BINARY_PREDICATE_RESULT(T1, T2) \
306 : typename wi::binary_traits <T1, T2>::predicate_result
307 :
308 : /* The type of result produced by a signed binary predicate on types T1 and T2.
309 : This is bool if signed comparisons make sense for T1 and T2 and leads to
310 : substitution failure otherwise. */
311 : #define WI_SIGNED_BINARY_PREDICATE_RESULT(T1, T2) \
312 : typename wi::binary_traits <T1, T2>::signed_predicate_result
313 :
314 : /* The type of result produced by a unary operation on type T. */
315 : #define WI_UNARY_RESULT(T) \
316 : typename wi::binary_traits <T, T>::result_type
317 :
318 : /* Define a variable RESULT to hold the result of a binary operation on
319 : X and Y, which have types T1 and T2 respectively. Define VAL to
320 : point to the blocks of RESULT. Once the user of the macro has
321 : filled in VAL, it should call RESULT.set_len to set the number
322 : of initialized blocks. */
323 : #define WI_BINARY_RESULT_VAR(RESULT, VAL, T1, X, T2, Y) \
324 : WI_BINARY_RESULT (T1, T2) RESULT = \
325 : wi::int_traits <WI_BINARY_RESULT (T1, T2)>::get_binary_result (X, Y); \
326 : HOST_WIDE_INT *VAL = RESULT.write_val (0)
327 :
328 : /* Similar for the result of a unary operation on X, which has type T. */
329 : #define WI_UNARY_RESULT_VAR(RESULT, VAL, T, X) \
330 : WI_UNARY_RESULT (T) RESULT = \
331 : wi::int_traits <WI_UNARY_RESULT (T)>::get_binary_result (X, X); \
332 : HOST_WIDE_INT *VAL = RESULT.write_val (0)
333 :
334 : template <typename T> class generic_wide_int;
335 : template <int N> class fixed_wide_int_storage;
336 : class wide_int_storage;
337 : template <int N> class widest_int_storage;
338 :
339 : /* An N-bit integer. Until we can use typedef templates, use this instead. */
340 : #define FIXED_WIDE_INT(N) \
341 : generic_wide_int < fixed_wide_int_storage <N> >
342 :
343 : typedef generic_wide_int <wide_int_storage> wide_int;
344 : typedef FIXED_WIDE_INT (ADDR_MAX_PRECISION) offset_int;
345 : typedef generic_wide_int <widest_int_storage <WIDEST_INT_MAX_PRECISION> > widest_int;
346 : typedef generic_wide_int <widest_int_storage <WIDEST_INT_MAX_PRECISION * 2> > widest2_int;
347 :
348 : /* wi::storage_ref can be a reference to a primitive type,
349 : so this is the conservatively-correct setting. */
350 : template <bool SE, bool HDP = true>
351 : class wide_int_ref_storage;
352 :
353 : typedef generic_wide_int <wide_int_ref_storage <false> > wide_int_ref;
354 :
355 : /* This can be used instead of wide_int_ref if the referenced value is
356 : known to have type T. It carries across properties of T's representation,
357 : such as whether excess upper bits in a HWI are defined, and can therefore
358 : help avoid redundant work.
359 :
360 : The macro could be replaced with a template typedef, once we're able
361 : to use those. */
362 : #define WIDE_INT_REF_FOR(T) \
363 : generic_wide_int \
364 : <wide_int_ref_storage <wi::int_traits <T>::is_sign_extended, \
365 : wi::int_traits <T>::host_dependent_precision> >
366 :
367 : namespace wi
368 : {
369 : /* Operations that calculate overflow do so even for
370 : TYPE_OVERFLOW_WRAPS types. For example, adding 1 to +MAX_INT in
371 : an unsigned int is 0 and does not overflow in C/C++, but wi::add
372 : will set the overflow argument in case it's needed for further
373 : analysis.
374 :
375 : For operations that require overflow, these are the different
376 : types of overflow. */
377 : enum overflow_type {
378 : OVF_NONE = 0,
379 : OVF_UNDERFLOW = -1,
380 : OVF_OVERFLOW = 1,
381 : /* There was an overflow, but we are unsure whether it was an
382 : overflow or an underflow. */
383 : OVF_UNKNOWN = 2
384 : };
385 :
386 : /* Classifies an integer based on its precision. */
387 : enum precision_type {
388 : /* The integer has both a precision and defined signedness. This allows
389 : the integer to be converted to any width, since we know whether to fill
390 : any extra bits with zeros or signs. */
391 : FLEXIBLE_PRECISION,
392 :
393 : /* The integer has a variable precision but no defined signedness. */
394 : VAR_PRECISION,
395 :
396 : /* The integer has a constant precision (known at GCC compile time),
397 : is signed and all elements are in inline buffer. */
398 : INL_CONST_PRECISION,
399 :
400 : /* Like INL_CONST_PRECISION, but elements can be heap allocated for
401 : larger lengths. */
402 : CONST_PRECISION
403 : };
404 :
405 : /* This class, which has no default implementation, is expected to
406 : provide the following members:
407 :
408 : static const enum precision_type precision_type;
409 : Classifies the type of T.
410 :
411 : static const unsigned int precision;
412 : Only defined if precision_type == INL_CONST_PRECISION or
413 : precision_type == CONST_PRECISION. Specifies the
414 : precision of all integers of type T.
415 :
416 : static const bool host_dependent_precision;
417 : True if the precision of T depends (or can depend) on the host.
418 :
419 : static unsigned int get_precision (const T &x)
420 : Return the number of bits in X.
421 :
422 : static wi::storage_ref *decompose (HOST_WIDE_INT *scratch,
423 : unsigned int precision, const T &x)
424 : Decompose X as a PRECISION-bit integer, returning the associated
425 : wi::storage_ref. SCRATCH is available as scratch space if needed.
426 : The routine should assert that PRECISION is acceptable. */
427 : template <typename T> struct int_traits;
428 :
429 : /* This class provides a single type, result_type, which specifies the
430 : type of integer produced by a binary operation whose inputs have
431 : types T1 and T2. The definition should be symmetric. */
432 : template <typename T1, typename T2,
433 : enum precision_type P1 = int_traits <T1>::precision_type,
434 : enum precision_type P2 = int_traits <T2>::precision_type>
435 : struct binary_traits;
436 :
437 : /* Specify the result type for each supported combination of binary
438 : inputs. Note that INL_CONST_PRECISION, CONST_PRECISION and
439 : VAR_PRECISION cannot be mixed, in order to give stronger type
440 : checking. When both inputs are INL_CONST_PRECISION or both are
441 : CONST_PRECISION, they must have the same precision. */
442 : template <typename T1, typename T2>
443 : struct binary_traits <T1, T2, FLEXIBLE_PRECISION, FLEXIBLE_PRECISION>
444 : {
445 : typedef widest_int result_type;
446 : /* Don't define operators for this combination. */
447 : };
448 :
449 : template <typename T1, typename T2>
450 : struct binary_traits <T1, T2, FLEXIBLE_PRECISION, VAR_PRECISION>
451 : {
452 : typedef wide_int result_type;
453 : typedef result_type operator_result;
454 : typedef bool predicate_result;
455 : };
456 :
457 : template <typename T1, typename T2>
458 : struct binary_traits <T1, T2, FLEXIBLE_PRECISION, INL_CONST_PRECISION>
459 : {
460 : /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
461 : so as not to confuse gengtype. */
462 : typedef generic_wide_int < fixed_wide_int_storage
463 : <int_traits <T2>::precision> > result_type;
464 : typedef result_type operator_result;
465 : typedef bool predicate_result;
466 : typedef result_type signed_shift_result_type;
467 : typedef bool signed_predicate_result;
468 : };
469 :
470 : template <typename T1, typename T2>
471 : struct binary_traits <T1, T2, FLEXIBLE_PRECISION, CONST_PRECISION>
472 : {
473 : typedef generic_wide_int < widest_int_storage
474 : <int_traits <T2>::precision> > result_type;
475 : typedef result_type operator_result;
476 : typedef bool predicate_result;
477 : typedef result_type signed_shift_result_type;
478 : typedef bool signed_predicate_result;
479 : };
480 :
481 : template <typename T1, typename T2>
482 : struct binary_traits <T1, T2, VAR_PRECISION, FLEXIBLE_PRECISION>
483 : {
484 : typedef wide_int result_type;
485 : typedef result_type operator_result;
486 : typedef bool predicate_result;
487 : };
488 :
489 : template <typename T1, typename T2>
490 : struct binary_traits <T1, T2, INL_CONST_PRECISION, FLEXIBLE_PRECISION>
491 : {
492 : /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
493 : so as not to confuse gengtype. */
494 : typedef generic_wide_int < fixed_wide_int_storage
495 : <int_traits <T1>::precision> > result_type;
496 : typedef result_type operator_result;
497 : typedef bool predicate_result;
498 : typedef result_type signed_shift_result_type;
499 : typedef bool signed_predicate_result;
500 : };
501 :
502 : template <typename T1, typename T2>
503 : struct binary_traits <T1, T2, CONST_PRECISION, FLEXIBLE_PRECISION>
504 : {
505 : typedef generic_wide_int < widest_int_storage
506 : <int_traits <T1>::precision> > result_type;
507 : typedef result_type operator_result;
508 : typedef bool predicate_result;
509 : typedef result_type signed_shift_result_type;
510 : typedef bool signed_predicate_result;
511 : };
512 :
513 : template <typename T1, typename T2>
514 : struct binary_traits <T1, T2, INL_CONST_PRECISION, INL_CONST_PRECISION>
515 : {
516 : STATIC_ASSERT (int_traits <T1>::precision == int_traits <T2>::precision);
517 : /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
518 : so as not to confuse gengtype. */
519 : typedef generic_wide_int < fixed_wide_int_storage
520 : <int_traits <T1>::precision> > result_type;
521 : typedef result_type operator_result;
522 : typedef bool predicate_result;
523 : typedef result_type signed_shift_result_type;
524 : typedef bool signed_predicate_result;
525 : };
526 :
527 : template <typename T1, typename T2>
528 : struct binary_traits <T1, T2, CONST_PRECISION, CONST_PRECISION>
529 : {
530 : STATIC_ASSERT (int_traits <T1>::precision == int_traits <T2>::precision);
531 : typedef generic_wide_int < widest_int_storage
532 : <int_traits <T1>::precision> > result_type;
533 : typedef result_type operator_result;
534 : typedef bool predicate_result;
535 : typedef result_type signed_shift_result_type;
536 : typedef bool signed_predicate_result;
537 : };
538 :
539 : template <typename T1, typename T2>
540 : struct binary_traits <T1, T2, VAR_PRECISION, VAR_PRECISION>
541 : {
542 : typedef wide_int result_type;
543 : typedef result_type operator_result;
544 : typedef bool predicate_result;
545 : };
546 : }
547 :
548 : /* Public functions for querying and operating on integers. */
549 : namespace wi
550 : {
551 : template <typename T>
552 : unsigned int get_precision (const T &);
553 :
554 : template <typename T1, typename T2>
555 : unsigned int get_binary_precision (const T1 &, const T2 &);
556 :
557 : template <typename T1, typename T2>
558 : void copy (T1 &, const T2 &);
559 :
560 : #define UNARY_PREDICATE \
561 : template <typename T> bool
562 : #define UNARY_FUNCTION \
563 : template <typename T> WI_UNARY_RESULT (T)
564 : #define BINARY_PREDICATE \
565 : template <typename T1, typename T2> bool
566 : #define BINARY_FUNCTION \
567 : template <typename T1, typename T2> WI_BINARY_RESULT (T1, T2)
568 : #define SHIFT_FUNCTION \
569 : template <typename T1, typename T2> WI_UNARY_RESULT (T1)
570 :
571 : UNARY_PREDICATE fits_shwi_p (const T &);
572 : UNARY_PREDICATE fits_uhwi_p (const T &);
573 : UNARY_PREDICATE neg_p (const T &, signop = SIGNED);
574 :
575 : template <typename T>
576 : HOST_WIDE_INT sign_mask (const T &);
577 :
578 : BINARY_PREDICATE eq_p (const T1 &, const T2 &);
579 : BINARY_PREDICATE ne_p (const T1 &, const T2 &);
580 : BINARY_PREDICATE lt_p (const T1 &, const T2 &, signop);
581 : BINARY_PREDICATE lts_p (const T1 &, const T2 &);
582 : BINARY_PREDICATE ltu_p (const T1 &, const T2 &);
583 : BINARY_PREDICATE le_p (const T1 &, const T2 &, signop);
584 : BINARY_PREDICATE les_p (const T1 &, const T2 &);
585 : BINARY_PREDICATE leu_p (const T1 &, const T2 &);
586 : BINARY_PREDICATE gt_p (const T1 &, const T2 &, signop);
587 : BINARY_PREDICATE gts_p (const T1 &, const T2 &);
588 : BINARY_PREDICATE gtu_p (const T1 &, const T2 &);
589 : BINARY_PREDICATE ge_p (const T1 &, const T2 &, signop);
590 : BINARY_PREDICATE ges_p (const T1 &, const T2 &);
591 : BINARY_PREDICATE geu_p (const T1 &, const T2 &);
592 :
593 : template <typename T1, typename T2>
594 : int cmp (const T1 &, const T2 &, signop);
595 :
596 : template <typename T1, typename T2>
597 : int cmps (const T1 &, const T2 &);
598 :
599 : template <typename T1, typename T2>
600 : int cmpu (const T1 &, const T2 &);
601 :
602 : UNARY_FUNCTION bit_not (const T &);
603 : UNARY_FUNCTION neg (const T &);
604 : UNARY_FUNCTION neg (const T &, overflow_type *);
605 : UNARY_FUNCTION abs (const T &);
606 : UNARY_FUNCTION ext (const T &, unsigned int, signop);
607 : UNARY_FUNCTION sext (const T &, unsigned int);
608 : UNARY_FUNCTION zext (const T &, unsigned int);
609 : UNARY_FUNCTION set_bit (const T &, unsigned int);
610 : UNARY_FUNCTION bswap (const T &);
611 : UNARY_FUNCTION bitreverse (const T &);
612 :
613 : BINARY_FUNCTION min (const T1 &, const T2 &, signop);
614 : BINARY_FUNCTION smin (const T1 &, const T2 &);
615 : BINARY_FUNCTION umin (const T1 &, const T2 &);
616 : BINARY_FUNCTION max (const T1 &, const T2 &, signop);
617 : BINARY_FUNCTION smax (const T1 &, const T2 &);
618 : BINARY_FUNCTION umax (const T1 &, const T2 &);
619 :
620 : BINARY_FUNCTION bit_and (const T1 &, const T2 &);
621 : BINARY_FUNCTION bit_and_not (const T1 &, const T2 &);
622 : BINARY_FUNCTION bit_or (const T1 &, const T2 &);
623 : BINARY_FUNCTION bit_or_not (const T1 &, const T2 &);
624 : BINARY_FUNCTION bit_xor (const T1 &, const T2 &);
625 : BINARY_FUNCTION add (const T1 &, const T2 &);
626 : BINARY_FUNCTION add (const T1 &, const T2 &, signop, overflow_type *);
627 : BINARY_FUNCTION sub (const T1 &, const T2 &);
628 : BINARY_FUNCTION sub (const T1 &, const T2 &, signop, overflow_type *);
629 : BINARY_FUNCTION mul (const T1 &, const T2 &);
630 : BINARY_FUNCTION mul (const T1 &, const T2 &, signop, overflow_type *);
631 : BINARY_FUNCTION smul (const T1 &, const T2 &, overflow_type *);
632 : BINARY_FUNCTION umul (const T1 &, const T2 &, overflow_type *);
633 : BINARY_FUNCTION mul_high (const T1 &, const T2 &, signop);
634 : BINARY_FUNCTION div_trunc (const T1 &, const T2 &, signop,
635 : overflow_type * = 0);
636 : BINARY_FUNCTION sdiv_trunc (const T1 &, const T2 &);
637 : BINARY_FUNCTION udiv_trunc (const T1 &, const T2 &);
638 : BINARY_FUNCTION div_floor (const T1 &, const T2 &, signop,
639 : overflow_type * = 0);
640 : BINARY_FUNCTION udiv_floor (const T1 &, const T2 &);
641 : BINARY_FUNCTION sdiv_floor (const T1 &, const T2 &);
642 : BINARY_FUNCTION div_ceil (const T1 &, const T2 &, signop,
643 : overflow_type * = 0);
644 : BINARY_FUNCTION udiv_ceil (const T1 &, const T2 &);
645 : BINARY_FUNCTION div_round (const T1 &, const T2 &, signop,
646 : overflow_type * = 0);
647 : BINARY_FUNCTION divmod_trunc (const T1 &, const T2 &, signop,
648 : WI_BINARY_RESULT (T1, T2) *);
649 : BINARY_FUNCTION gcd (const T1 &, const T2 &, signop = UNSIGNED);
650 : BINARY_FUNCTION mod_trunc (const T1 &, const T2 &, signop,
651 : overflow_type * = 0);
652 : BINARY_FUNCTION smod_trunc (const T1 &, const T2 &);
653 : BINARY_FUNCTION umod_trunc (const T1 &, const T2 &);
654 : BINARY_FUNCTION mod_floor (const T1 &, const T2 &, signop,
655 : overflow_type * = 0);
656 : BINARY_FUNCTION umod_floor (const T1 &, const T2 &);
657 : BINARY_FUNCTION mod_ceil (const T1 &, const T2 &, signop,
658 : overflow_type * = 0);
659 : BINARY_FUNCTION mod_round (const T1 &, const T2 &, signop,
660 : overflow_type * = 0);
661 :
662 : template <typename T1, typename T2>
663 : bool multiple_of_p (const T1 &, const T2 &, signop);
664 :
665 : template <typename T1, typename T2>
666 : bool multiple_of_p (const T1 &, const T2 &, signop,
667 : WI_BINARY_RESULT (T1, T2) *);
668 :
669 : SHIFT_FUNCTION lshift (const T1 &, const T2 &);
670 : SHIFT_FUNCTION lrshift (const T1 &, const T2 &);
671 : SHIFT_FUNCTION arshift (const T1 &, const T2 &);
672 : SHIFT_FUNCTION rshift (const T1 &, const T2 &, signop sgn);
673 : SHIFT_FUNCTION lrotate (const T1 &, const T2 &, unsigned int = 0);
674 : SHIFT_FUNCTION rrotate (const T1 &, const T2 &, unsigned int = 0);
675 :
676 : #undef SHIFT_FUNCTION
677 : #undef BINARY_PREDICATE
678 : #undef BINARY_FUNCTION
679 : #undef UNARY_PREDICATE
680 : #undef UNARY_FUNCTION
681 :
682 : bool only_sign_bit_p (const wide_int_ref &, unsigned int);
683 : bool only_sign_bit_p (const wide_int_ref &);
684 : int clz (const wide_int_ref &);
685 : int clrsb (const wide_int_ref &);
686 : int ctz (const wide_int_ref &);
687 : int exact_log2 (const wide_int_ref &);
688 : int floor_log2 (const wide_int_ref &);
689 : int ffs (const wide_int_ref &);
690 : int popcount (const wide_int_ref &);
691 : int parity (const wide_int_ref &);
692 :
693 : template <typename T>
694 : unsigned HOST_WIDE_INT extract_uhwi (const T &, unsigned int, unsigned int);
695 :
696 : template <typename T>
697 : unsigned int min_precision (const T &, signop);
698 :
699 : static inline void accumulate_overflow (overflow_type &, overflow_type);
700 : }
701 :
702 : namespace wi
703 : {
704 : /* Contains the components of a decomposed integer for easy, direct
705 : access. */
706 : class storage_ref
707 : {
708 : public:
709 : storage_ref () {}
710 : storage_ref (const HOST_WIDE_INT *, unsigned int, unsigned int);
711 :
712 : const HOST_WIDE_INT *val;
713 : unsigned int len;
714 : unsigned int precision;
715 :
716 : /* Provide enough trappings for this class to act as storage for
717 : generic_wide_int. */
718 : unsigned int get_len () const;
719 : unsigned int get_precision () const;
720 : const HOST_WIDE_INT *get_val () const;
721 : };
722 : }
723 :
724 >21987*10^7 : inline::wi::storage_ref::storage_ref (const HOST_WIDE_INT *val_in,
725 : unsigned int len_in,
726 : unsigned int precision_in)
727 : : val (val_in), len (len_in), precision (precision_in)
728 : {
729 : }
730 :
731 : inline unsigned int
732 93876739458 : wi::storage_ref::get_len () const
733 : {
734 62428486154 : return len;
735 : }
736 :
737 : inline unsigned int
738 74544743685 : wi::storage_ref::get_precision () const
739 : {
740 38165951004 : return precision;
741 : }
742 :
743 : inline const HOST_WIDE_INT *
744 >16392*10^7 : wi::storage_ref::get_val () const
745 : {
746 >15662*10^7 : return val;
747 : }
748 :
749 : /* This class defines an integer type using the storage provided by the
750 : template argument. The storage class must provide the following
751 : functions:
752 :
753 : unsigned int get_precision () const
754 : Return the number of bits in the integer.
755 :
756 : HOST_WIDE_INT *get_val () const
757 : Return a pointer to the array of blocks that encodes the integer.
758 :
759 : unsigned int get_len () const
760 : Return the number of blocks in get_val (). If this is smaller
761 : than the number of blocks implied by get_precision (), the
762 : remaining blocks are sign extensions of block get_len () - 1.
763 :
764 : Although not required by generic_wide_int itself, writable storage
765 : classes can also provide the following functions:
766 :
767 : HOST_WIDE_INT *write_val (unsigned int)
768 : Get a modifiable version of get_val (). The argument should be
769 : upper estimation for LEN (ignored by all storages but
770 : widest_int_storage).
771 :
772 : unsigned int set_len (unsigned int len)
773 : Set the value returned by get_len () to LEN. */
774 : template <typename storage>
775 >16638*10^7 : class GTY(()) generic_wide_int : public storage
776 : {
777 : public:
778 : generic_wide_int ();
779 :
780 : template <typename T>
781 : generic_wide_int (const T &);
782 :
783 : template <typename T>
784 : generic_wide_int (const T &, unsigned int);
785 :
786 : /* Conversions. */
787 : HOST_WIDE_INT to_shwi (unsigned int) const;
788 : HOST_WIDE_INT to_shwi () const;
789 : unsigned HOST_WIDE_INT to_uhwi (unsigned int) const;
790 : unsigned HOST_WIDE_INT to_uhwi () const;
791 : HOST_WIDE_INT to_short_addr () const;
792 :
793 : /* Public accessors for the interior of a wide int. */
794 : HOST_WIDE_INT sign_mask () const;
795 : HOST_WIDE_INT elt (unsigned int) const;
796 : HOST_WIDE_INT sext_elt (unsigned int) const;
797 : unsigned HOST_WIDE_INT ulow () const;
798 : unsigned HOST_WIDE_INT uhigh () const;
799 : HOST_WIDE_INT slow () const;
800 : HOST_WIDE_INT shigh () const;
801 :
802 : template <typename T>
803 : generic_wide_int &operator = (const T &);
804 :
805 : #define ASSIGNMENT_OPERATOR(OP, F) \
806 : template <typename T> \
807 : generic_wide_int &OP (const T &c) { return (*this = wi::F (*this, c)); }
808 :
809 : /* Restrict these to cases where the shift operator is defined. */
810 : #define SHIFT_ASSIGNMENT_OPERATOR(OP, OP2) \
811 : template <typename T> \
812 : generic_wide_int &OP (const T &c) { return (*this = *this OP2 c); }
813 :
814 : #define INCDEC_OPERATOR(OP, DELTA) \
815 : generic_wide_int &OP () { *this += DELTA; return *this; }
816 :
817 170237659 : ASSIGNMENT_OPERATOR (operator &=, bit_and)
818 95383182 : ASSIGNMENT_OPERATOR (operator |=, bit_or)
819 64610952 : ASSIGNMENT_OPERATOR (operator ^=, bit_xor)
820 7809619746 : ASSIGNMENT_OPERATOR (operator +=, add)
821 1403641799 : ASSIGNMENT_OPERATOR (operator -=, sub)
822 746099109 : ASSIGNMENT_OPERATOR (operator *=, mul)
823 1333114870 : ASSIGNMENT_OPERATOR (operator <<=, lshift)
824 : SHIFT_ASSIGNMENT_OPERATOR (operator >>=, >>)
825 271568 : INCDEC_OPERATOR (operator ++, 1)
826 35951 : INCDEC_OPERATOR (operator --, -1)
827 :
828 : #undef SHIFT_ASSIGNMENT_OPERATOR
829 : #undef ASSIGNMENT_OPERATOR
830 : #undef INCDEC_OPERATOR
831 :
832 : /* Debugging functions. */
833 : void dump () const;
834 :
835 : static const bool is_sign_extended
836 : = wi::int_traits <generic_wide_int <storage> >::is_sign_extended;
837 : static const bool needs_write_val_arg
838 : = wi::int_traits <generic_wide_int <storage> >::needs_write_val_arg;
839 : };
840 :
841 : template <typename storage>
842 >15362*10^7 : inline generic_wide_int <storage>::generic_wide_int () {}
843 :
844 : template <typename storage>
845 : template <typename T>
846 >15729*10^7 : inline generic_wide_int <storage>::generic_wide_int (const T &x)
847 60582653457 : : storage (x)
848 : {
849 96435860 : }
850 :
851 : template <typename storage>
852 : template <typename T>
853 >26009*10^7 : inline generic_wide_int <storage>::generic_wide_int (const T &x,
854 : unsigned int precision)
855 >33946*10^7 : : storage (x, precision)
856 : {
857 : }
858 :
859 : /* Return THIS as a signed HOST_WIDE_INT, sign-extending from PRECISION.
860 : If THIS does not fit in PRECISION, the information is lost. */
861 : template <typename storage>
862 : inline HOST_WIDE_INT
863 157057925 : generic_wide_int <storage>::to_shwi (unsigned int precision) const
864 : {
865 157057925 : if (precision < HOST_BITS_PER_WIDE_INT)
866 26277045 : return sext_hwi (this->get_val ()[0], precision);
867 : else
868 130780880 : return this->get_val ()[0];
869 : }
870 :
871 : /* Return THIS as a signed HOST_WIDE_INT, in its natural precision. */
872 : template <typename storage>
873 : inline HOST_WIDE_INT
874 25927466528 : generic_wide_int <storage>::to_shwi () const
875 : {
876 : if (is_sign_extended)
877 17315138161 : return this->get_val ()[0];
878 : else
879 98989643 : return to_shwi (this->get_precision ());
880 : }
881 :
882 : /* Return THIS as an unsigned HOST_WIDE_INT, zero-extending from
883 : PRECISION. If THIS does not fit in PRECISION, the information
884 : is lost. */
885 : template <typename storage>
886 : inline unsigned HOST_WIDE_INT
887 33200550298 : generic_wide_int <storage>::to_uhwi (unsigned int precision) const
888 : {
889 33195948654 : if (precision < HOST_BITS_PER_WIDE_INT)
890 16464292249 : return zext_hwi (this->get_val ()[0], precision);
891 : else
892 16735998346 : return this->get_val ()[0];
893 : }
894 :
895 : /* Return THIS as an signed HOST_WIDE_INT, in its natural precision. */
896 : template <typename storage>
897 : inline unsigned HOST_WIDE_INT
898 33200550264 : generic_wide_int <storage>::to_uhwi () const
899 : {
900 17679797486 : return to_uhwi (this->get_precision ());
901 : }
902 :
903 : /* TODO: The compiler is half converted from using HOST_WIDE_INT to
904 : represent addresses to using offset_int to represent addresses.
905 : We use to_short_addr at the interface from new code to old,
906 : unconverted code. */
907 : template <typename storage>
908 : inline HOST_WIDE_INT
909 4258438 : generic_wide_int <storage>::to_short_addr () const
910 : {
911 4258438 : return this->get_val ()[0];
912 : }
913 :
914 : /* Return the implicit value of blocks above get_len (). */
915 : template <typename storage>
916 : inline HOST_WIDE_INT
917 9825946909 : generic_wide_int <storage>::sign_mask () const
918 : {
919 9825946909 : unsigned int len = this->get_len ();
920 9810924182 : gcc_assert (len > 0);
921 :
922 9840969636 : unsigned HOST_WIDE_INT high = this->get_val ()[len - 1];
923 : if (!is_sign_extended)
924 : {
925 1465432453 : unsigned int precision = this->get_precision ();
926 1465432453 : int excess = len * HOST_BITS_PER_WIDE_INT - precision;
927 1465432453 : if (excess > 0)
928 662926423 : high <<= excess;
929 : }
930 9825946909 : return (HOST_WIDE_INT) (high) < 0 ? -1 : 0;
931 : }
932 :
933 : /* Return the signed value of the least-significant explicitly-encoded
934 : block. */
935 : template <typename storage>
936 : inline HOST_WIDE_INT
937 8015445789 : generic_wide_int <storage>::slow () const
938 : {
939 8015445789 : return this->get_val ()[0];
940 : }
941 :
942 : /* Return the signed value of the most-significant explicitly-encoded
943 : block. */
944 : template <typename storage>
945 : inline HOST_WIDE_INT
946 : generic_wide_int <storage>::shigh () const
947 : {
948 : return this->get_val ()[this->get_len () - 1];
949 : }
950 :
951 : /* Return the unsigned value of the least-significant
952 : explicitly-encoded block. */
953 : template <typename storage>
954 : inline unsigned HOST_WIDE_INT
955 41031976664 : generic_wide_int <storage>::ulow () const
956 : {
957 34734098070 : return this->get_val ()[0];
958 : }
959 :
960 : /* Return the unsigned value of the most-significant
961 : explicitly-encoded block. */
962 : template <typename storage>
963 : inline unsigned HOST_WIDE_INT
964 734720350 : generic_wide_int <storage>::uhigh () const
965 : {
966 723183367 : return this->get_val ()[this->get_len () - 1];
967 : }
968 :
969 : /* Return block I, which might be implicitly or explicit encoded. */
970 : template <typename storage>
971 : inline HOST_WIDE_INT
972 2015117618 : generic_wide_int <storage>::elt (unsigned int i) const
973 : {
974 2015117618 : if (i >= this->get_len ())
975 5149570 : return sign_mask ();
976 : else
977 2009968048 : return this->get_val ()[i];
978 : }
979 :
980 : /* Like elt, but sign-extend beyond the upper bit, instead of returning
981 : the raw encoding. */
982 : template <typename storage>
983 : inline HOST_WIDE_INT
984 273030825 : generic_wide_int <storage>::sext_elt (unsigned int i) const
985 : {
986 273030825 : HOST_WIDE_INT elt_i = elt (i);
987 : if (!is_sign_extended)
988 : {
989 0 : unsigned int precision = this->get_precision ();
990 0 : unsigned int lsb = i * HOST_BITS_PER_WIDE_INT;
991 0 : if (precision - lsb < HOST_BITS_PER_WIDE_INT)
992 0 : elt_i = sext_hwi (elt_i, precision - lsb);
993 : }
994 0 : return elt_i;
995 : }
996 :
997 : template <typename storage>
998 : template <typename T>
999 : inline generic_wide_int <storage> &
1000 14519743668 : generic_wide_int <storage>::operator = (const T &x)
1001 : {
1002 12958702881 : storage::operator = (x);
1003 86412862 : return *this;
1004 : }
1005 :
1006 : /* Dump the contents of the integer to stderr, for debugging. */
1007 : template <typename storage>
1008 : void
1009 0 : generic_wide_int <storage>::dump () const
1010 : {
1011 0 : unsigned int len = this->get_len ();
1012 0 : const HOST_WIDE_INT *val = this->get_val ();
1013 0 : unsigned int precision = this->get_precision ();
1014 0 : fprintf (stderr, "[");
1015 0 : if (len * HOST_BITS_PER_WIDE_INT < precision)
1016 0 : fprintf (stderr, "...,");
1017 0 : for (unsigned int i = 0; i < len - 1; ++i)
1018 0 : fprintf (stderr, HOST_WIDE_INT_PRINT_HEX ",", val[len - 1 - i]);
1019 0 : fprintf (stderr, HOST_WIDE_INT_PRINT_HEX "], precision = %d\n",
1020 : val[0], precision);
1021 0 : }
1022 :
1023 : namespace wi
1024 : {
1025 : template <typename storage>
1026 : struct int_traits < generic_wide_int <storage> >
1027 : : public wi::int_traits <storage>
1028 : {
1029 : static unsigned int get_precision (const generic_wide_int <storage> &);
1030 : static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int,
1031 : const generic_wide_int <storage> &);
1032 : };
1033 : }
1034 :
1035 : template <typename storage>
1036 : inline unsigned int
1037 >12037*10^7 : wi::int_traits < generic_wide_int <storage> >::
1038 : get_precision (const generic_wide_int <storage> &x)
1039 : {
1040 >14907*10^7 : return x.get_precision ();
1041 : }
1042 :
1043 : template <typename storage>
1044 : inline wi::storage_ref
1045 >24340*10^7 : wi::int_traits < generic_wide_int <storage> >::
1046 : decompose (HOST_WIDE_INT *, unsigned int precision,
1047 : const generic_wide_int <storage> &x)
1048 : {
1049 >10552*10^7 : gcc_checking_assert (precision == x.get_precision ());
1050 >39110*10^7 : return wi::storage_ref (x.get_val (), x.get_len (), precision);
1051 : }
1052 :
1053 : /* Provide the storage for a wide_int_ref. This acts like a read-only
1054 : wide_int, with the optimization that VAL is normally a pointer to
1055 : another integer's storage, so that no array copy is needed. */
1056 : template <bool SE, bool HDP>
1057 : class wide_int_ref_storage : public wi::storage_ref
1058 : {
1059 : private:
1060 : /* Scratch space that can be used when decomposing the original integer.
1061 : It must live as long as this object. */
1062 : HOST_WIDE_INT scratch[2];
1063 :
1064 : public:
1065 : wide_int_ref_storage () {}
1066 :
1067 : wide_int_ref_storage (const wi::storage_ref &);
1068 :
1069 : template <typename T>
1070 : wide_int_ref_storage (const T &);
1071 :
1072 : template <typename T>
1073 : wide_int_ref_storage (const T &, unsigned int);
1074 : };
1075 :
1076 : /* Create a reference from an existing reference. */
1077 : template <bool SE, bool HDP>
1078 19286040529 : inline wide_int_ref_storage <SE, HDP>::
1079 : wide_int_ref_storage (const wi::storage_ref &x)
1080 19286040529 : : storage_ref (x)
1081 : {}
1082 :
1083 : /* Create a reference to integer X in its natural precision. Note
1084 : that the natural precision is host-dependent for primitive
1085 : types. */
1086 : template <bool SE, bool HDP>
1087 : template <typename T>
1088 77552594210 : inline wide_int_ref_storage <SE, HDP>::wide_int_ref_storage (const T &x)
1089 75590635087 : : storage_ref (wi::int_traits <T>::decompose (scratch,
1090 : wi::get_precision (x), x))
1091 : {
1092 1294753297 : }
1093 :
1094 : /* Create a reference to integer X in precision PRECISION. */
1095 : template <bool SE, bool HDP>
1096 : template <typename T>
1097 >26009*10^7 : inline wide_int_ref_storage <SE, HDP>::
1098 : wide_int_ref_storage (const T &x, unsigned int precision)
1099 >15186*10^7 : : storage_ref (wi::int_traits <T>::decompose (scratch, precision, x))
1100 : {
1101 : }
1102 :
1103 : namespace wi
1104 : {
1105 : template <bool SE, bool HDP>
1106 : struct int_traits <wide_int_ref_storage <SE, HDP> >
1107 : {
1108 : static const enum precision_type precision_type = VAR_PRECISION;
1109 : static const bool host_dependent_precision = HDP;
1110 : static const bool is_sign_extended = SE;
1111 : static const bool needs_write_val_arg = false;
1112 : };
1113 : }
1114 :
1115 : namespace wi
1116 : {
1117 : unsigned int force_to_size (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1118 : unsigned int, unsigned int, unsigned int,
1119 : signop sgn);
1120 : unsigned int from_array (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1121 : unsigned int, unsigned int, bool = true);
1122 : }
1123 :
1124 : /* The storage used by wide_int. */
1125 : class GTY(()) wide_int_storage
1126 : {
1127 : private:
1128 : union
1129 : {
1130 : HOST_WIDE_INT val[WIDE_INT_MAX_INL_ELTS];
1131 : HOST_WIDE_INT *valp;
1132 : } GTY((skip)) u;
1133 : unsigned int len;
1134 : unsigned int precision;
1135 :
1136 : public:
1137 : wide_int_storage ();
1138 : template <typename T>
1139 : wide_int_storage (const T &);
1140 : wide_int_storage (const wide_int_storage &);
1141 : ~wide_int_storage ();
1142 :
1143 : /* The standard generic_wide_int storage methods. */
1144 : unsigned int get_precision () const;
1145 : const HOST_WIDE_INT *get_val () const;
1146 : unsigned int get_len () const;
1147 : HOST_WIDE_INT *write_val (unsigned int);
1148 : void set_len (unsigned int, bool = false);
1149 :
1150 : wide_int_storage &operator = (const wide_int_storage &);
1151 : template <typename T>
1152 : wide_int_storage &operator = (const T &);
1153 :
1154 : static wide_int from (const wide_int_ref &, unsigned int, signop);
1155 : static wide_int from_array (const HOST_WIDE_INT *, unsigned int,
1156 : unsigned int, bool = true);
1157 : static wide_int create (unsigned int);
1158 : };
1159 :
1160 : namespace wi
1161 : {
1162 : template <>
1163 : struct int_traits <wide_int_storage>
1164 : {
1165 : static const enum precision_type precision_type = VAR_PRECISION;
1166 : /* Guaranteed by a static assert in the wide_int_storage constructor. */
1167 : static const bool host_dependent_precision = false;
1168 : static const bool is_sign_extended = true;
1169 : static const bool needs_write_val_arg = false;
1170 : template <typename T1, typename T2>
1171 : static wide_int get_binary_result (const T1 &, const T2 &);
1172 : template <typename T1, typename T2>
1173 : static unsigned int get_binary_precision (const T1 &, const T2 &);
1174 : };
1175 : }
1176 :
1177 81787132322 : inline wide_int_storage::wide_int_storage () : precision (0) {}
1178 :
1179 : /* Initialize the storage from integer X, in its natural precision.
1180 : Note that we do not allow integers with host-dependent precision
1181 : to become wide_ints; wide_ints must always be logically independent
1182 : of the host. */
1183 : template <typename T>
1184 14728317497 : inline wide_int_storage::wide_int_storage (const T &x)
1185 : {
1186 : STATIC_ASSERT (!wi::int_traits<T>::host_dependent_precision);
1187 : STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::CONST_PRECISION);
1188 : STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::INL_CONST_PRECISION);
1189 14728317497 : WIDE_INT_REF_FOR (T) xi (x);
1190 14728317497 : precision = xi.precision;
1191 14728317497 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1192 40985 : u.valp = XNEWVEC (HOST_WIDE_INT, CEIL (precision, HOST_BITS_PER_WIDE_INT));
1193 14728317497 : wi::copy (*this, xi);
1194 14728317497 : }
1195 :
1196 37065427141 : inline wide_int_storage::wide_int_storage (const wide_int_storage &x)
1197 : {
1198 37065427141 : memcpy (this, &x, sizeof (wide_int_storage));
1199 37065427141 : if (UNLIKELY (x.precision > WIDE_INT_MAX_INL_PRECISION))
1200 : {
1201 139927 : u.valp = XNEWVEC (HOST_WIDE_INT, CEIL (precision, HOST_BITS_PER_WIDE_INT));
1202 139927 : memcpy (u.valp, x.u.valp, len * sizeof (HOST_WIDE_INT));
1203 : }
1204 37065427141 : }
1205 :
1206 >16524*10^7 : inline wide_int_storage::~wide_int_storage ()
1207 : {
1208 >13745*10^7 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1209 367825 : XDELETEVEC (u.valp);
1210 : }
1211 :
1212 : inline wide_int_storage&
1213 25521644648 : wide_int_storage::operator = (const wide_int_storage &x)
1214 : {
1215 25521644648 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1216 : {
1217 23681 : if (this == &x)
1218 : return *this;
1219 23681 : XDELETEVEC (u.valp);
1220 : }
1221 25521644648 : memcpy (this, &x, sizeof (wide_int_storage));
1222 25521644648 : if (UNLIKELY (x.precision > WIDE_INT_MAX_INL_PRECISION))
1223 : {
1224 106348 : u.valp = XNEWVEC (HOST_WIDE_INT, CEIL (x.precision, HOST_BITS_PER_WIDE_INT));
1225 106348 : memcpy (u.valp, x.u.valp, len * sizeof (HOST_WIDE_INT));
1226 : }
1227 : return *this;
1228 : }
1229 :
1230 : template <typename T>
1231 : inline wide_int_storage&
1232 11483254390 : wide_int_storage::operator = (const T &x)
1233 : {
1234 : STATIC_ASSERT (!wi::int_traits<T>::host_dependent_precision);
1235 : STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::CONST_PRECISION);
1236 : STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::INL_CONST_PRECISION);
1237 11483254390 : WIDE_INT_REF_FOR (T) xi (x);
1238 11483254390 : if (UNLIKELY (precision != xi.precision))
1239 : {
1240 10556025473 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1241 6 : XDELETEVEC (u.valp);
1242 10556025473 : precision = xi.precision;
1243 10556025473 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1244 61243 : u.valp = XNEWVEC (HOST_WIDE_INT,
1245 : CEIL (precision, HOST_BITS_PER_WIDE_INT));
1246 : }
1247 11483254390 : wi::copy (*this, xi);
1248 11483254390 : return *this;
1249 : }
1250 :
1251 : inline unsigned int
1252 >26416*10^7 : wide_int_storage::get_precision () const
1253 : {
1254 >16882*10^7 : return precision;
1255 : }
1256 :
1257 : inline const HOST_WIDE_INT *
1258 >14552*10^7 : wide_int_storage::get_val () const
1259 : {
1260 >14552*10^7 : return UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION) ? u.valp : u.val;
1261 : }
1262 :
1263 : inline unsigned int
1264 >14659*10^7 : wide_int_storage::get_len () const
1265 : {
1266 >14659*10^7 : return len;
1267 : }
1268 :
1269 : inline HOST_WIDE_INT *
1270 88212603358 : wide_int_storage::write_val (unsigned int)
1271 : {
1272 87429349904 : return UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION) ? u.valp : u.val;
1273 : }
1274 :
1275 : inline void
1276 75710952191 : wide_int_storage::set_len (unsigned int l, bool is_sign_extended)
1277 : {
1278 75710952191 : len = l;
1279 75710952191 : if (!is_sign_extended && len * HOST_BITS_PER_WIDE_INT > precision)
1280 : {
1281 9835379887 : HOST_WIDE_INT &v = write_val (len)[len - 1];
1282 9835379887 : v = sext_hwi (v, precision % HOST_BITS_PER_WIDE_INT);
1283 : }
1284 75710952191 : }
1285 :
1286 : /* Treat X as having signedness SGN and convert it to a PRECISION-bit
1287 : number. */
1288 : inline wide_int
1289 15242734993 : wide_int_storage::from (const wide_int_ref &x, unsigned int precision,
1290 : signop sgn)
1291 : {
1292 30485469986 : wide_int result = wide_int::create (precision);
1293 15242734993 : result.set_len (wi::force_to_size (result.write_val (x.len), x.val, x.len,
1294 15242734993 : x.precision, precision, sgn));
1295 15242734993 : return result;
1296 : }
1297 :
1298 : /* Create a wide_int from the explicit block encoding given by VAL and
1299 : LEN. PRECISION is the precision of the integer. NEED_CANON_P is
1300 : true if the encoding may have redundant trailing blocks. */
1301 : inline wide_int
1302 2771562 : wide_int_storage::from_array (const HOST_WIDE_INT *val, unsigned int len,
1303 : unsigned int precision, bool need_canon_p)
1304 : {
1305 5543124 : wide_int result = wide_int::create (precision);
1306 2771562 : result.set_len (wi::from_array (result.write_val (len), val, len, precision,
1307 : need_canon_p));
1308 2771562 : return result;
1309 : }
1310 :
1311 : /* Return an uninitialized wide_int with precision PRECISION. */
1312 : inline wide_int
1313 49499379430 : wide_int_storage::create (unsigned int precision)
1314 : {
1315 49499379430 : wide_int x;
1316 49499379430 : x.precision = precision;
1317 17737956765 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1318 132015 : x.u.valp = XNEWVEC (HOST_WIDE_INT,
1319 : CEIL (precision, HOST_BITS_PER_WIDE_INT));
1320 17737956765 : return x;
1321 : }
1322 :
1323 : template <typename T1, typename T2>
1324 : inline wide_int
1325 29234688828 : wi::int_traits <wide_int_storage>::get_binary_result (const T1 &x, const T2 &y)
1326 : {
1327 : /* This shouldn't be used for two flexible-precision inputs. */
1328 : STATIC_ASSERT (wi::int_traits <T1>::precision_type != FLEXIBLE_PRECISION
1329 : || wi::int_traits <T2>::precision_type != FLEXIBLE_PRECISION);
1330 : if (wi::int_traits <T1>::precision_type == FLEXIBLE_PRECISION)
1331 145693160 : return wide_int::create (wi::get_precision (y));
1332 : else
1333 58323684496 : return wide_int::create (wi::get_precision (x));
1334 : }
1335 :
1336 : template <typename T1, typename T2>
1337 : inline unsigned int
1338 63987778909 : wi::int_traits <wide_int_storage>::get_binary_precision (const T1 &x,
1339 : const T2 &y)
1340 : {
1341 : /* This shouldn't be used for two flexible-precision inputs. */
1342 : STATIC_ASSERT (wi::int_traits <T1>::precision_type != FLEXIBLE_PRECISION
1343 : || wi::int_traits <T2>::precision_type != FLEXIBLE_PRECISION);
1344 : if (wi::int_traits <T1>::precision_type == FLEXIBLE_PRECISION)
1345 191295633 : return wi::get_precision (y);
1346 : else
1347 63796483276 : return wi::get_precision (x);
1348 : }
1349 :
1350 : /* The storage used by FIXED_WIDE_INT (N). */
1351 : template <int N>
1352 : class GTY(()) fixed_wide_int_storage
1353 : {
1354 : private:
1355 : HOST_WIDE_INT val[WIDE_INT_MAX_HWIS (N)];
1356 : unsigned int len;
1357 :
1358 : public:
1359 : fixed_wide_int_storage () = default;
1360 : template <typename T>
1361 : fixed_wide_int_storage (const T &);
1362 :
1363 : /* The standard generic_wide_int storage methods. */
1364 : unsigned int get_precision () const;
1365 : const HOST_WIDE_INT *get_val () const;
1366 : unsigned int get_len () const;
1367 : HOST_WIDE_INT *write_val (unsigned int);
1368 : void set_len (unsigned int, bool = false);
1369 :
1370 : static FIXED_WIDE_INT (N) from (const wide_int_ref &, signop);
1371 : static FIXED_WIDE_INT (N) from_array (const HOST_WIDE_INT *, unsigned int,
1372 : bool = true);
1373 : };
1374 :
1375 : namespace wi
1376 : {
1377 : template <int N>
1378 : struct int_traits < fixed_wide_int_storage <N> >
1379 : {
1380 : static const enum precision_type precision_type = INL_CONST_PRECISION;
1381 : static const bool host_dependent_precision = false;
1382 : static const bool is_sign_extended = true;
1383 : static const bool needs_write_val_arg = false;
1384 : static const unsigned int precision = N;
1385 : template <typename T1, typename T2>
1386 : static FIXED_WIDE_INT (N) get_binary_result (const T1 &, const T2 &);
1387 : template <typename T1, typename T2>
1388 : static unsigned int get_binary_precision (const T1 &, const T2 &);
1389 : };
1390 : }
1391 :
1392 : /* Initialize the storage from integer X, in precision N. */
1393 : template <int N>
1394 : template <typename T>
1395 12381276738 : inline fixed_wide_int_storage <N>::fixed_wide_int_storage (const T &x)
1396 : {
1397 : /* Check for type compatibility. We don't want to initialize a
1398 : fixed-width integer from something like a wide_int. */
1399 : WI_BINARY_RESULT (T, FIXED_WIDE_INT (N)) *assertion ATTRIBUTE_UNUSED;
1400 22733881394 : wi::copy (*this, WIDE_INT_REF_FOR (T) (x, N));
1401 12381276738 : }
1402 :
1403 : template <int N>
1404 : inline unsigned int
1405 : fixed_wide_int_storage <N>::get_precision () const
1406 : {
1407 : return N;
1408 : }
1409 :
1410 : template <int N>
1411 : inline const HOST_WIDE_INT *
1412 36400679885 : fixed_wide_int_storage <N>::get_val () const
1413 : {
1414 35858559624 : return val;
1415 : }
1416 :
1417 : template <int N>
1418 : inline unsigned int
1419 36576484421 : fixed_wide_int_storage <N>::get_len () const
1420 : {
1421 36034364016 : return len;
1422 : }
1423 :
1424 : template <int N>
1425 : inline HOST_WIDE_INT *
1426 31553096433 : fixed_wide_int_storage <N>::write_val (unsigned int)
1427 : {
1428 12381594850 : return val;
1429 : }
1430 :
1431 : template <int N>
1432 : inline void
1433 31553096429 : fixed_wide_int_storage <N>::set_len (unsigned int l, bool)
1434 : {
1435 31553096429 : len = l;
1436 : /* There are no excess bits in val[len - 1]. */
1437 : STATIC_ASSERT (N % HOST_BITS_PER_WIDE_INT == 0);
1438 16743880022 : }
1439 :
1440 : /* Treat X as having signedness SGN and convert it to an N-bit number. */
1441 : template <int N>
1442 : inline FIXED_WIDE_INT (N)
1443 1436782518 : fixed_wide_int_storage <N>::from (const wide_int_ref &x, signop sgn)
1444 : {
1445 1436782518 : FIXED_WIDE_INT (N) result;
1446 2843806945 : result.set_len (wi::force_to_size (result.write_val (x.len), x.val, x.len,
1447 1436782518 : x.precision, N, sgn));
1448 1407024427 : return result;
1449 : }
1450 :
1451 : /* Create a FIXED_WIDE_INT (N) from the explicit block encoding given by
1452 : VAL and LEN. NEED_CANON_P is true if the encoding may have redundant
1453 : trailing blocks. */
1454 : template <int N>
1455 : inline FIXED_WIDE_INT (N)
1456 : fixed_wide_int_storage <N>::from_array (const HOST_WIDE_INT *val,
1457 : unsigned int len,
1458 : bool need_canon_p)
1459 : {
1460 : FIXED_WIDE_INT (N) result;
1461 : result.set_len (wi::from_array (result.write_val (len), val, len,
1462 : N, need_canon_p));
1463 : return result;
1464 : }
1465 :
1466 : template <int N>
1467 : template <typename T1, typename T2>
1468 : inline FIXED_WIDE_INT (N)
1469 17734950009 : wi::int_traits < fixed_wide_int_storage <N> >::
1470 : get_binary_result (const T1 &, const T2 &)
1471 : {
1472 17734950009 : return FIXED_WIDE_INT (N) ();
1473 : }
1474 :
1475 : template <int N>
1476 : template <typename T1, typename T2>
1477 : inline unsigned int
1478 : wi::int_traits < fixed_wide_int_storage <N> >::
1479 : get_binary_precision (const T1 &, const T2 &)
1480 : {
1481 : return N;
1482 : }
1483 :
1484 : #define WIDEST_INT(N) generic_wide_int < widest_int_storage <N> >
1485 :
1486 : /* The storage used by widest_int. */
1487 : template <int N>
1488 : class GTY(()) widest_int_storage
1489 : {
1490 : private:
1491 : union
1492 : {
1493 : HOST_WIDE_INT val[WIDE_INT_MAX_INL_ELTS];
1494 : HOST_WIDE_INT *valp;
1495 : } GTY((skip)) u;
1496 : unsigned int len;
1497 :
1498 : public:
1499 : widest_int_storage ();
1500 : widest_int_storage (const widest_int_storage &);
1501 : template <typename T>
1502 : widest_int_storage (const T &);
1503 : ~widest_int_storage ();
1504 : widest_int_storage &operator = (const widest_int_storage &);
1505 : template <typename T>
1506 : inline widest_int_storage& operator = (const T &);
1507 :
1508 : /* The standard generic_wide_int storage methods. */
1509 : unsigned int get_precision () const;
1510 : const HOST_WIDE_INT *get_val () const;
1511 : unsigned int get_len () const;
1512 : HOST_WIDE_INT *write_val (unsigned int);
1513 : void set_len (unsigned int, bool = false);
1514 :
1515 : static WIDEST_INT (N) from (const wide_int_ref &, signop);
1516 : static WIDEST_INT (N) from_array (const HOST_WIDE_INT *, unsigned int,
1517 : bool = true);
1518 : };
1519 :
1520 : namespace wi
1521 : {
1522 : template <int N>
1523 : struct int_traits < widest_int_storage <N> >
1524 : {
1525 : static const enum precision_type precision_type = CONST_PRECISION;
1526 : static const bool host_dependent_precision = false;
1527 : static const bool is_sign_extended = true;
1528 : static const bool needs_write_val_arg = true;
1529 : static const unsigned int precision = N;
1530 : template <typename T1, typename T2>
1531 : static WIDEST_INT (N) get_binary_result (const T1 &, const T2 &);
1532 : template <typename T1, typename T2>
1533 : static unsigned int get_binary_precision (const T1 &, const T2 &);
1534 : };
1535 : }
1536 :
1537 : template <int N>
1538 8958649804 : inline widest_int_storage <N>::widest_int_storage () : len (0) {}
1539 :
1540 : /* Initialize the storage from integer X, in precision N. */
1541 : template <int N>
1542 : template <typename T>
1543 782226962 : inline widest_int_storage <N>::widest_int_storage (const T &x) : len (0)
1544 : {
1545 : /* Check for type compatibility. We don't want to initialize a
1546 : widest integer from something like a wide_int. */
1547 : WI_BINARY_RESULT (T, WIDEST_INT (N)) *assertion ATTRIBUTE_UNUSED;
1548 1123731267 : wi::copy (*this, WIDE_INT_REF_FOR (T) (x, N));
1549 782226962 : }
1550 :
1551 : template <int N>
1552 : inline
1553 1193000822 : widest_int_storage <N>::widest_int_storage (const widest_int_storage &x)
1554 : {
1555 1193000822 : memcpy (this, &x, sizeof (widest_int_storage));
1556 1193000822 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1557 : {
1558 1686 : u.valp = XNEWVEC (HOST_WIDE_INT, len);
1559 1686 : memcpy (u.valp, x.u.valp, len * sizeof (HOST_WIDE_INT));
1560 : }
1561 1193000822 : }
1562 :
1563 : template <int N>
1564 12854587803 : inline widest_int_storage <N>::~widest_int_storage ()
1565 : {
1566 8228629860 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1567 59042 : XDELETEVEC (u.valp);
1568 : }
1569 :
1570 : template <int N>
1571 : inline widest_int_storage <N>&
1572 3403897622 : widest_int_storage <N>::operator = (const widest_int_storage &x)
1573 : {
1574 3403897622 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1575 : {
1576 36829 : if (this == &x)
1577 : return *this;
1578 36829 : XDELETEVEC (u.valp);
1579 : }
1580 3403897622 : memcpy (this, &x, sizeof (widest_int_storage));
1581 3403897622 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1582 : {
1583 42874 : u.valp = XNEWVEC (HOST_WIDE_INT, len);
1584 42874 : memcpy (u.valp, x.u.valp, len * sizeof (HOST_WIDE_INT));
1585 : }
1586 : return *this;
1587 : }
1588 :
1589 : template <int N>
1590 : template <typename T>
1591 : inline widest_int_storage <N>&
1592 2755680432 : widest_int_storage <N>::operator = (const T &x)
1593 : {
1594 : /* Check for type compatibility. We don't want to assign a
1595 : widest integer from something like a wide_int. */
1596 : WI_BINARY_RESULT (T, WIDEST_INT (N)) *assertion ATTRIBUTE_UNUSED;
1597 2755680432 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1598 303 : XDELETEVEC (u.valp);
1599 2755680432 : len = 0;
1600 5490697453 : wi::copy (*this, WIDE_INT_REF_FOR (T) (x, N));
1601 2755680432 : return *this;
1602 : }
1603 :
1604 : template <int N>
1605 : inline unsigned int
1606 : widest_int_storage <N>::get_precision () const
1607 : {
1608 : return N;
1609 : }
1610 :
1611 : template <int N>
1612 : inline const HOST_WIDE_INT *
1613 14367657732 : widest_int_storage <N>::get_val () const
1614 : {
1615 14367657732 : return UNLIKELY (len > WIDE_INT_MAX_INL_ELTS) ? u.valp : u.val;
1616 : }
1617 :
1618 : template <int N>
1619 : inline unsigned int
1620 14246376734 : widest_int_storage <N>::get_len () const
1621 : {
1622 14246376734 : return len;
1623 : }
1624 :
1625 : template <int N>
1626 : inline HOST_WIDE_INT *
1627 18164949351 : widest_int_storage <N>::write_val (unsigned int l)
1628 : {
1629 12347954805 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1630 0 : XDELETEVEC (u.valp);
1631 12347954871 : len = l;
1632 12347954805 : if (UNLIKELY (l > WIDE_INT_MAX_INL_ELTS))
1633 : {
1634 110292 : u.valp = XNEWVEC (HOST_WIDE_INT, l);
1635 110292 : return u.valp;
1636 : }
1637 12347844513 : else if (CHECKING_P && l < WIDE_INT_MAX_INL_ELTS)
1638 12653229800 : u.val[l] = HOST_WIDE_INT_UC (0xbaaaaaaddeadbeef);
1639 12347844513 : return u.val;
1640 : }
1641 :
1642 : template <int N>
1643 : inline void
1644 8809745639 : widest_int_storage <N>::set_len (unsigned int l, bool)
1645 : {
1646 8809745639 : gcc_checking_assert (l <= len);
1647 8809745639 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS)
1648 108562 : && l <= WIDE_INT_MAX_INL_ELTS)
1649 : {
1650 58459 : HOST_WIDE_INT *valp = u.valp;
1651 58459 : memcpy (u.val, valp, l * sizeof (u.val[0]));
1652 58459 : XDELETEVEC (valp);
1653 58459 : }
1654 8809687180 : else if (len && len < WIDE_INT_MAX_INL_ELTS)
1655 8809525775 : gcc_checking_assert ((unsigned HOST_WIDE_INT) u.val[len]
1656 : == HOST_WIDE_INT_UC (0xbaaaaaaddeadbeef));
1657 8809745639 : len = l;
1658 : /* There are no excess bits in val[len - 1]. */
1659 : STATIC_ASSERT (N % HOST_BITS_PER_WIDE_INT == 0);
1660 8809745639 : }
1661 :
1662 : /* Treat X as having signedness SGN and convert it to an N-bit number. */
1663 : template <int N>
1664 : inline WIDEST_INT (N)
1665 2782373138 : widest_int_storage <N>::from (const wide_int_ref &x, signop sgn)
1666 : {
1667 2782373138 : WIDEST_INT (N) result;
1668 2782373138 : unsigned int exp_len = x.len;
1669 2782373138 : unsigned int prec = result.get_precision ();
1670 2782373138 : if (sgn == UNSIGNED && prec > x.precision && x.val[x.len - 1] < 0)
1671 506705251 : exp_len = CEIL (x.precision, HOST_BITS_PER_WIDE_INT) + 1;
1672 2782373138 : result.set_len (wi::force_to_size (result.write_val (exp_len), x.val, x.len,
1673 2782373138 : x.precision, prec, sgn));
1674 2782373138 : return result;
1675 : }
1676 :
1677 : /* Create a WIDEST_INT (N) from the explicit block encoding given by
1678 : VAL and LEN. NEED_CANON_P is true if the encoding may have redundant
1679 : trailing blocks. */
1680 : template <int N>
1681 : inline WIDEST_INT (N)
1682 187631660 : widest_int_storage <N>::from_array (const HOST_WIDE_INT *val,
1683 : unsigned int len,
1684 : bool need_canon_p)
1685 : {
1686 187631660 : WIDEST_INT (N) result;
1687 187631660 : result.set_len (wi::from_array (result.write_val (len), val, len,
1688 : result.get_precision (), need_canon_p));
1689 187631660 : return result;
1690 : }
1691 :
1692 : template <int N>
1693 : template <typename T1, typename T2>
1694 : inline WIDEST_INT (N)
1695 5816994480 : wi::int_traits < widest_int_storage <N> >::
1696 : get_binary_result (const T1 &, const T2 &)
1697 : {
1698 5816994480 : return WIDEST_INT (N) ();
1699 : }
1700 :
1701 : template <int N>
1702 : template <typename T1, typename T2>
1703 : inline unsigned int
1704 : wi::int_traits < widest_int_storage <N> >::
1705 : get_binary_precision (const T1 &, const T2 &)
1706 : {
1707 : return N;
1708 : }
1709 :
1710 : /* A reference to one element of a trailing_wide_ints structure. */
1711 : class trailing_wide_int_storage
1712 : {
1713 : private:
1714 : /* The precision of the integer, which is a fixed property of the
1715 : parent trailing_wide_ints. */
1716 : unsigned int m_precision;
1717 :
1718 : /* A pointer to the length field. */
1719 : unsigned short *m_len;
1720 :
1721 : /* A pointer to the HWI array. There are enough elements to hold all
1722 : values of precision M_PRECISION. */
1723 : HOST_WIDE_INT *m_val;
1724 :
1725 : public:
1726 : trailing_wide_int_storage (unsigned int, unsigned short *, HOST_WIDE_INT *);
1727 :
1728 : /* The standard generic_wide_int storage methods. */
1729 : unsigned int get_len () const;
1730 : unsigned int get_precision () const;
1731 : const HOST_WIDE_INT *get_val () const;
1732 : HOST_WIDE_INT *write_val (unsigned int);
1733 : void set_len (unsigned int, bool = false);
1734 :
1735 : template <typename T>
1736 : trailing_wide_int_storage &operator = (const T &);
1737 : };
1738 :
1739 : typedef generic_wide_int <trailing_wide_int_storage> trailing_wide_int;
1740 :
1741 : /* trailing_wide_int behaves like a wide_int. */
1742 : namespace wi
1743 : {
1744 : template <>
1745 : struct int_traits <trailing_wide_int_storage>
1746 : : public int_traits <wide_int_storage> {};
1747 : }
1748 :
1749 : /* A variable-length array of wide_int-like objects that can be put
1750 : at the end of a variable-sized structure. The number of objects is
1751 : at most N and can be set at runtime by using set_precision().
1752 :
1753 : Use extra_size to calculate how many bytes beyond the
1754 : sizeof need to be allocated. Use set_precision to initialize the
1755 : structure. */
1756 : template <int N>
1757 : struct GTY((user)) trailing_wide_ints
1758 : {
1759 : private:
1760 : /* The shared precision of each number. */
1761 : unsigned short m_precision;
1762 :
1763 : /* The shared maximum length of each number. */
1764 : unsigned short m_max_len;
1765 :
1766 : /* The number of elements. */
1767 : unsigned char m_num_elements;
1768 :
1769 : /* The current length of each number. */
1770 : unsigned short m_len[N];
1771 :
1772 : /* The variable-length part of the structure, which always contains
1773 : at least one HWI. Element I starts at index I * M_MAX_LEN. */
1774 : HOST_WIDE_INT m_val[1];
1775 :
1776 : public:
1777 : typedef WIDE_INT_REF_FOR (trailing_wide_int_storage) const_reference;
1778 :
1779 : void set_precision (unsigned int precision, unsigned int num_elements = N);
1780 161361838 : unsigned int get_precision () const { return m_precision; }
1781 : unsigned int num_elements () const { return m_num_elements; }
1782 : trailing_wide_int operator [] (unsigned int);
1783 : const_reference operator [] (unsigned int) const;
1784 : static size_t extra_size (unsigned int precision,
1785 : unsigned int num_elements = N);
1786 : size_t extra_size () const { return extra_size (m_precision,
1787 : m_num_elements); }
1788 : };
1789 :
1790 4593716180 : inline trailing_wide_int_storage::
1791 : trailing_wide_int_storage (unsigned int precision, unsigned short *len,
1792 : HOST_WIDE_INT *val)
1793 3326096370 : : m_precision (precision), m_len (len), m_val (val)
1794 : {
1795 : }
1796 :
1797 : inline unsigned int
1798 4429781336 : trailing_wide_int_storage::get_len () const
1799 : {
1800 4429781336 : return *m_len;
1801 : }
1802 :
1803 : inline unsigned int
1804 8859562672 : trailing_wide_int_storage::get_precision () const
1805 : {
1806 4429781336 : return m_precision;
1807 : }
1808 :
1809 : inline const HOST_WIDE_INT *
1810 4429781336 : trailing_wide_int_storage::get_val () const
1811 : {
1812 4429781336 : return m_val;
1813 : }
1814 :
1815 : inline HOST_WIDE_INT *
1816 163934844 : trailing_wide_int_storage::write_val (unsigned int)
1817 : {
1818 163934844 : return m_val;
1819 : }
1820 :
1821 : inline void
1822 163934844 : trailing_wide_int_storage::set_len (unsigned int len, bool is_sign_extended)
1823 : {
1824 163934844 : *m_len = len;
1825 163934844 : if (!is_sign_extended && len * HOST_BITS_PER_WIDE_INT > m_precision)
1826 0 : m_val[len - 1] = sext_hwi (m_val[len - 1],
1827 : m_precision % HOST_BITS_PER_WIDE_INT);
1828 163934844 : }
1829 :
1830 : template <typename T>
1831 : inline trailing_wide_int_storage &
1832 163934844 : trailing_wide_int_storage::operator = (const T &x)
1833 : {
1834 163934844 : WIDE_INT_REF_FOR (T) xi (x, m_precision);
1835 163934844 : wi::copy (*this, xi);
1836 163934844 : return *this;
1837 : }
1838 :
1839 : /* Initialize the structure and record that all elements have precision
1840 : PRECISION. NUM_ELEMENTS can be no more than N. */
1841 : template <int N>
1842 : inline void
1843 95044186 : trailing_wide_ints <N>::set_precision (unsigned int precision,
1844 : unsigned int num_elements)
1845 : {
1846 : gcc_checking_assert (num_elements <= N);
1847 95044186 : m_num_elements = num_elements;
1848 95044186 : m_precision = precision;
1849 95044186 : m_max_len = WIDE_INT_MAX_HWIS (precision);
1850 95044186 : }
1851 :
1852 : /* Return a reference to element INDEX. */
1853 : template <int N>
1854 : inline trailing_wide_int
1855 163934844 : trailing_wide_ints <N>::operator [] (unsigned int index)
1856 : {
1857 163934844 : return trailing_wide_int_storage (m_precision, &m_len[index],
1858 163934844 : &m_val[index * m_max_len]);
1859 : }
1860 :
1861 : template <int N>
1862 : inline typename trailing_wide_ints <N>::const_reference
1863 617303804 : trailing_wide_ints <N>::operator [] (unsigned int index) const
1864 : {
1865 617303804 : return wi::storage_ref (&m_val[index * m_max_len],
1866 462977853 : m_len[index], m_precision);
1867 : }
1868 :
1869 : /* Return how many extra bytes need to be added to the end of the
1870 : structure in order to handle NUM_ELEMENTS wide_ints of precision
1871 : PRECISION. NUM_ELEMENTS is the number of elements, and defaults
1872 : to N. */
1873 : template <int N>
1874 : inline size_t
1875 85233707 : trailing_wide_ints <N>::extra_size (unsigned int precision,
1876 : unsigned int num_elements)
1877 : {
1878 85233707 : unsigned int max_len = WIDE_INT_MAX_HWIS (precision);
1879 : gcc_checking_assert (num_elements <= N);
1880 85233707 : return (num_elements * max_len - 1) * sizeof (HOST_WIDE_INT);
1881 : }
1882 :
1883 : /* This macro is used in structures that end with a trailing_wide_ints field
1884 : called FIELD. It declares get_NAME() and set_NAME() methods to access
1885 : element I of FIELD. */
1886 : #define TRAILING_WIDE_INT_ACCESSOR(NAME, FIELD, I) \
1887 : trailing_wide_int get_##NAME () { return FIELD[I]; } \
1888 : template <typename T> void set_##NAME (const T &x) { FIELD[I] = x; }
1889 :
1890 : namespace wi
1891 : {
1892 : /* Implementation of int_traits for primitive integer types like "int". */
1893 : template <typename T, bool signed_p>
1894 : struct primitive_int_traits
1895 : {
1896 : static const enum precision_type precision_type = FLEXIBLE_PRECISION;
1897 : static const bool host_dependent_precision = true;
1898 : static const bool is_sign_extended = true;
1899 : static const bool needs_write_val_arg = false;
1900 : static unsigned int get_precision (T);
1901 : static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int, T);
1902 : };
1903 : }
1904 :
1905 : template <typename T, bool signed_p>
1906 : inline unsigned int
1907 : wi::primitive_int_traits <T, signed_p>::get_precision (T)
1908 : {
1909 : return sizeof (T) * CHAR_BIT;
1910 : }
1911 :
1912 : template <typename T, bool signed_p>
1913 : inline wi::storage_ref
1914 70463091914 : wi::primitive_int_traits <T, signed_p>::decompose (HOST_WIDE_INT *scratch,
1915 : unsigned int precision, T x)
1916 : {
1917 70463091914 : scratch[0] = x;
1918 144517966 : if (signed_p || scratch[0] >= 0 || precision <= HOST_BITS_PER_WIDE_INT)
1919 41924495704 : return wi::storage_ref (scratch, 1, precision);
1920 2609636 : scratch[1] = 0;
1921 2609636 : return wi::storage_ref (scratch, 2, precision);
1922 : }
1923 :
1924 : /* Allow primitive C types to be used in wi:: routines. */
1925 : namespace wi
1926 : {
1927 : template <>
1928 : struct int_traits <unsigned char>
1929 : : public primitive_int_traits <unsigned char, false> {};
1930 :
1931 : template <>
1932 : struct int_traits <unsigned short>
1933 : : public primitive_int_traits <unsigned short, false> {};
1934 :
1935 : template <>
1936 : struct int_traits <int>
1937 : : public primitive_int_traits <int, true> {};
1938 :
1939 : template <>
1940 : struct int_traits <unsigned int>
1941 : : public primitive_int_traits <unsigned int, false> {};
1942 :
1943 : template <>
1944 : struct int_traits <long>
1945 : : public primitive_int_traits <long, true> {};
1946 :
1947 : template <>
1948 : struct int_traits <unsigned long>
1949 : : public primitive_int_traits <unsigned long, false> {};
1950 :
1951 : #if defined HAVE_LONG_LONG
1952 : template <>
1953 : struct int_traits <long long>
1954 : : public primitive_int_traits <long long, true> {};
1955 :
1956 : template <>
1957 : struct int_traits <unsigned long long>
1958 : : public primitive_int_traits <unsigned long long, false> {};
1959 : #endif
1960 : }
1961 :
1962 : namespace wi
1963 : {
1964 : /* Stores HWI-sized integer VAL, treating it as having signedness SGN
1965 : and precision PRECISION. */
1966 : class hwi_with_prec
1967 : {
1968 : public:
1969 : hwi_with_prec () {}
1970 : hwi_with_prec (HOST_WIDE_INT, unsigned int, signop);
1971 : HOST_WIDE_INT val;
1972 : unsigned int precision;
1973 : signop sgn;
1974 : };
1975 :
1976 : hwi_with_prec shwi (HOST_WIDE_INT, unsigned int);
1977 : hwi_with_prec uhwi (unsigned HOST_WIDE_INT, unsigned int);
1978 :
1979 : hwi_with_prec minus_one (unsigned int);
1980 : hwi_with_prec zero (unsigned int);
1981 : hwi_with_prec one (unsigned int);
1982 : hwi_with_prec two (unsigned int);
1983 : }
1984 :
1985 24564397088 : inline wi::hwi_with_prec::hwi_with_prec (HOST_WIDE_INT v, unsigned int p,
1986 : signop s)
1987 : : precision (p), sgn (s)
1988 : {
1989 24564397088 : if (precision < HOST_BITS_PER_WIDE_INT)
1990 12692545105 : val = sext_hwi (v, precision);
1991 : else
1992 : val = v;
1993 : }
1994 :
1995 : /* Return a signed integer that has value VAL and precision PRECISION. */
1996 : inline wi::hwi_with_prec
1997 20760387170 : wi::shwi (HOST_WIDE_INT val, unsigned int precision)
1998 : {
1999 20760387170 : return hwi_with_prec (val, precision, SIGNED);
2000 : }
2001 :
2002 : /* Return an unsigned integer that has value VAL and precision PRECISION. */
2003 : inline wi::hwi_with_prec
2004 3804009918 : wi::uhwi (unsigned HOST_WIDE_INT val, unsigned int precision)
2005 : {
2006 3803901561 : return hwi_with_prec (val, precision, UNSIGNED);
2007 : }
2008 :
2009 : /* Return a wide int of -1 with precision PRECISION. */
2010 : inline wi::hwi_with_prec
2011 3232474517 : wi::minus_one (unsigned int precision)
2012 : {
2013 3232474517 : return wi::shwi (-1, precision);
2014 : }
2015 :
2016 : /* Return a wide int of 0 with precision PRECISION. */
2017 : inline wi::hwi_with_prec
2018 4463086022 : wi::zero (unsigned int precision)
2019 : {
2020 4463086022 : return wi::shwi (0, precision);
2021 : }
2022 :
2023 : /* Return a wide int of 1 with precision PRECISION. */
2024 : inline wi::hwi_with_prec
2025 1164504701 : wi::one (unsigned int precision)
2026 : {
2027 1164504701 : return wi::shwi (1, precision);
2028 : }
2029 :
2030 : /* Return a wide int of 2 with precision PRECISION. */
2031 : inline wi::hwi_with_prec
2032 : wi::two (unsigned int precision)
2033 : {
2034 : return wi::shwi (2, precision);
2035 : }
2036 :
2037 : namespace wi
2038 : {
2039 : /* ints_for<T>::zero (X) returns a zero that, when asssigned to a T,
2040 : gives that T the same precision as X. */
2041 : template<typename T, precision_type = int_traits<T>::precision_type>
2042 : struct ints_for
2043 : {
2044 : static int zero (const T &) { return 0; }
2045 : };
2046 :
2047 : template<typename T>
2048 : struct ints_for<T, VAR_PRECISION>
2049 : {
2050 : static hwi_with_prec zero (const T &);
2051 : };
2052 : }
2053 :
2054 : template<typename T>
2055 : inline wi::hwi_with_prec
2056 : wi::ints_for<T, wi::VAR_PRECISION>::zero (const T &x)
2057 : {
2058 : return wi::zero (wi::get_precision (x));
2059 : }
2060 :
2061 : namespace wi
2062 : {
2063 : template <>
2064 : struct int_traits <wi::hwi_with_prec>
2065 : {
2066 : static const enum precision_type precision_type = VAR_PRECISION;
2067 : /* hwi_with_prec has an explicitly-given precision, rather than the
2068 : precision of HOST_WIDE_INT. */
2069 : static const bool host_dependent_precision = false;
2070 : static const bool is_sign_extended = true;
2071 : static const bool needs_write_val_arg = false;
2072 : static unsigned int get_precision (const wi::hwi_with_prec &);
2073 : static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int,
2074 : const wi::hwi_with_prec &);
2075 : };
2076 : }
2077 :
2078 : inline unsigned int
2079 24534177261 : wi::int_traits <wi::hwi_with_prec>::get_precision (const wi::hwi_with_prec &x)
2080 : {
2081 24534177261 : return x.precision;
2082 : }
2083 :
2084 : inline wi::storage_ref
2085 24564396656 : wi::int_traits <wi::hwi_with_prec>::
2086 : decompose (HOST_WIDE_INT *scratch, unsigned int precision,
2087 : const wi::hwi_with_prec &x)
2088 : {
2089 24564396656 : gcc_checking_assert (precision == x.precision);
2090 24564396656 : scratch[0] = x.val;
2091 24564396656 : if (x.sgn == SIGNED || x.val >= 0 || precision <= HOST_BITS_PER_WIDE_INT)
2092 24564355056 : return wi::storage_ref (scratch, 1, precision);
2093 41600 : scratch[1] = 0;
2094 41600 : return wi::storage_ref (scratch, 2, precision);
2095 : }
2096 :
2097 : /* Private functions for handling large cases out of line. They take
2098 : individual length and array parameters because that is cheaper for
2099 : the inline caller than constructing an object on the stack and
2100 : passing a reference to it. (Although many callers use wide_int_refs,
2101 : we generally want those to be removed by SRA.) */
2102 : namespace wi
2103 : {
2104 : bool eq_p_large (const HOST_WIDE_INT *, unsigned int,
2105 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2106 : bool lts_p_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2107 : const HOST_WIDE_INT *, unsigned int);
2108 : bool ltu_p_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2109 : const HOST_WIDE_INT *, unsigned int);
2110 : int cmps_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2111 : const HOST_WIDE_INT *, unsigned int);
2112 : int cmpu_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2113 : const HOST_WIDE_INT *, unsigned int);
2114 : unsigned int sext_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2115 : unsigned int, unsigned int, unsigned int);
2116 : unsigned int zext_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2117 : unsigned int, unsigned int, unsigned int);
2118 : unsigned int set_bit_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2119 : unsigned int, unsigned int, unsigned int);
2120 : unsigned int bswap_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2121 : unsigned int, unsigned int);
2122 : unsigned int bitreverse_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2123 : unsigned int, unsigned int);
2124 :
2125 : unsigned int lshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2126 : unsigned int, unsigned int, unsigned int);
2127 : unsigned int lrshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2128 : unsigned int, unsigned int, unsigned int,
2129 : unsigned int);
2130 : unsigned int arshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2131 : unsigned int, unsigned int, unsigned int,
2132 : unsigned int);
2133 : unsigned int and_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2134 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2135 : unsigned int and_not_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2136 : unsigned int, const HOST_WIDE_INT *,
2137 : unsigned int, unsigned int);
2138 : unsigned int or_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2139 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2140 : unsigned int or_not_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2141 : unsigned int, const HOST_WIDE_INT *,
2142 : unsigned int, unsigned int);
2143 : unsigned int xor_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2144 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2145 : unsigned int add_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2146 : const HOST_WIDE_INT *, unsigned int, unsigned int,
2147 : signop, overflow_type *);
2148 : unsigned int sub_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2149 : const HOST_WIDE_INT *, unsigned int, unsigned int,
2150 : signop, overflow_type *);
2151 : unsigned int mul_internal (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2152 : unsigned int, const HOST_WIDE_INT *,
2153 : unsigned int, unsigned int, signop,
2154 : overflow_type *, bool);
2155 : unsigned int divmod_internal (HOST_WIDE_INT *, unsigned int *,
2156 : HOST_WIDE_INT *, const HOST_WIDE_INT *,
2157 : unsigned int, unsigned int,
2158 : const HOST_WIDE_INT *,
2159 : unsigned int, unsigned int,
2160 : signop, overflow_type *);
2161 : }
2162 :
2163 : /* Return the number of bits that integer X can hold. */
2164 : template <typename T>
2165 : inline unsigned int
2166 75974590328 : wi::get_precision (const T &x)
2167 : {
2168 43565021278 : return wi::int_traits <T>::get_precision (x);
2169 : }
2170 :
2171 : /* Return the number of bits that the result of a binary operation can
2172 : hold when the input operands are X and Y. */
2173 : template <typename T1, typename T2>
2174 : inline unsigned int
2175 63987778909 : wi::get_binary_precision (const T1 &x, const T2 &y)
2176 : {
2177 : using res_traits = wi::int_traits <WI_BINARY_RESULT (T1, T2)>;
2178 63987778909 : return res_traits::get_binary_precision (x, y);
2179 : }
2180 :
2181 : /* Copy the contents of Y to X, but keeping X's current precision. */
2182 : template <typename T1, typename T2>
2183 : inline void
2184 44961578641 : wi::copy (T1 &x, const T2 &y)
2185 : {
2186 44961578641 : unsigned int len = y.get_len ();
2187 44961578641 : HOST_WIDE_INT *xval = x.write_val (len);
2188 44961578641 : const HOST_WIDE_INT *yval = y.get_val ();
2189 44961578641 : unsigned int i = 0;
2190 : do
2191 44988676010 : xval[i] = yval[i];
2192 44988676010 : while (++i < len);
2193 : /* For widest_int write_val is called with an exact value, not
2194 : upper bound for len, so nothing is needed further. */
2195 : if (!wi::int_traits <T1>::needs_write_val_arg)
2196 41423373735 : x.set_len (len, y.is_sign_extended);
2197 44961578641 : }
2198 :
2199 : /* Return true if X fits in a HOST_WIDE_INT with no loss of precision. */
2200 : template <typename T>
2201 : inline bool
2202 27819543217 : wi::fits_shwi_p (const T &x)
2203 : {
2204 28647233529 : WIDE_INT_REF_FOR (T) xi (x);
2205 15195829652 : return xi.len == 1;
2206 : }
2207 :
2208 : /* Return true if X fits in an unsigned HOST_WIDE_INT with no loss of
2209 : precision. */
2210 : template <typename T>
2211 : inline bool
2212 8282876331 : wi::fits_uhwi_p (const T &x)
2213 : {
2214 8282876331 : WIDE_INT_REF_FOR (T) xi (x);
2215 8282876331 : if (xi.precision <= HOST_BITS_PER_WIDE_INT)
2216 : return true;
2217 8036326039 : if (xi.len == 1)
2218 8015445225 : return xi.slow () >= 0;
2219 20880814 : return xi.len == 2 && xi.uhigh () == 0;
2220 : }
2221 :
2222 : /* Return true if X is negative based on the interpretation of SGN.
2223 : For UNSIGNED, this is always false. */
2224 : template <typename T>
2225 : inline bool
2226 9268586930 : wi::neg_p (const T &x, signop sgn)
2227 : {
2228 9268586930 : WIDE_INT_REF_FOR (T) xi (x);
2229 9268586930 : if (sgn == UNSIGNED)
2230 : return false;
2231 8664656675 : return xi.sign_mask () < 0;
2232 : }
2233 :
2234 : /* Return -1 if the top bit of X is set and 0 if the top bit is clear. */
2235 : template <typename T>
2236 : inline HOST_WIDE_INT
2237 1493 : wi::sign_mask (const T &x)
2238 : {
2239 1493 : WIDE_INT_REF_FOR (T) xi (x);
2240 1493 : return xi.sign_mask ();
2241 : }
2242 :
2243 : /* Return true if X == Y. X and Y must be binary-compatible. */
2244 : template <typename T1, typename T2>
2245 : inline bool
2246 53472181030 : wi::eq_p (const T1 &x, const T2 &y)
2247 : {
2248 53472181030 : unsigned int precision = get_binary_precision (x, y);
2249 53472181030 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2250 53472181030 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2251 : if (xi.is_sign_extended && yi.is_sign_extended)
2252 : {
2253 : /* This case reduces to array equality. */
2254 38814499875 : if (xi.len != yi.len)
2255 : return false;
2256 : unsigned int i = 0;
2257 : do
2258 38746850882 : if (xi.val[i] != yi.val[i])
2259 8246889687 : return false;
2260 30729484440 : while (++i != xi.len);
2261 : return true;
2262 : }
2263 3858944744 : if (LIKELY (yi.len == 1))
2264 : {
2265 : /* XI is only equal to YI if it too has a single HWI. */
2266 14655078102 : if (xi.len != 1)
2267 : return false;
2268 : /* Excess bits in xi.val[0] will be signs or zeros, so comparisons
2269 : with 0 are simple. */
2270 14643199572 : if (STATIC_CONSTANT_P (yi.val[0] == 0))
2271 10637036238 : return xi.val[0] == 0;
2272 : /* Otherwise flush out any excess bits first. */
2273 4006163334 : unsigned HOST_WIDE_INT diff = xi.val[0] ^ yi.val[0];
2274 4006163334 : int excess = HOST_BITS_PER_WIDE_INT - precision;
2275 4006163334 : if (excess > 0)
2276 581123145 : diff <<= excess;
2277 4006163334 : return diff == 0;
2278 : }
2279 2598874 : return eq_p_large (xi.val, xi.len, yi.val, yi.len, precision);
2280 : }
2281 :
2282 : /* Return true if X != Y. X and Y must be binary-compatible. */
2283 : template <typename T1, typename T2>
2284 : inline bool
2285 9473359100 : wi::ne_p (const T1 &x, const T2 &y)
2286 : {
2287 8512764359 : return !eq_p (x, y);
2288 : }
2289 :
2290 : /* Return true if X < Y when both are treated as signed values. */
2291 : template <typename T1, typename T2>
2292 : inline bool
2293 7854423835 : wi::lts_p (const T1 &x, const T2 &y)
2294 : {
2295 7854423835 : unsigned int precision = get_binary_precision (x, y);
2296 7854423835 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2297 7854423835 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2298 : /* We optimize x < y, where y is 64 or fewer bits. */
2299 7854423835 : if (wi::fits_shwi_p (yi))
2300 : {
2301 : /* Make lts_p (x, 0) as efficient as wi::neg_p (x). */
2302 7784401408 : if (STATIC_CONSTANT_P (yi.val[0] == 0))
2303 328282504 : return neg_p (xi);
2304 : /* If x fits directly into a shwi, we can compare directly. */
2305 7456118904 : if (wi::fits_shwi_p (xi))
2306 7286986783 : return xi.to_shwi () < yi.to_shwi ();
2307 : /* If x doesn't fit and is negative, then it must be more
2308 : negative than any value in y, and hence smaller than y. */
2309 169132121 : if (neg_p (xi))
2310 : return true;
2311 : /* If x is positive, then it must be larger than any value in y,
2312 : and hence greater than y. */
2313 : return false;
2314 : }
2315 : /* Optimize the opposite case, if it can be detected at compile time. */
2316 27857880 : if (STATIC_CONSTANT_P (xi.len == 1))
2317 : /* If YI is negative it is lower than the least HWI.
2318 : If YI is positive it is greater than the greatest HWI. */
2319 42164547 : return !neg_p (yi);
2320 27857880 : return lts_p_large (xi.val, xi.len, precision, yi.val, yi.len);
2321 : }
2322 :
2323 : /* Return true if X < Y when both are treated as unsigned values. */
2324 : template <typename T1, typename T2>
2325 : inline bool
2326 8907084902 : wi::ltu_p (const T1 &x, const T2 &y)
2327 : {
2328 8907084902 : unsigned int precision = get_binary_precision (x, y);
2329 8907084902 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2330 8907084902 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2331 : /* Optimize comparisons with constants. */
2332 5048688896 : if (STATIC_CONSTANT_P (yi.len == 1 && yi.val[0] >= 0))
2333 9332209262 : return xi.len == 1 && xi.to_uhwi () < (unsigned HOST_WIDE_INT) yi.val[0];
2334 5082017367 : if (STATIC_CONSTANT_P (xi.len == 1 && xi.val[0] >= 0))
2335 32334184 : return yi.len != 1 || yi.to_uhwi () > (unsigned HOST_WIDE_INT) xi.val[0];
2336 : /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
2337 : for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
2338 : values does not change the result. */
2339 4224805692 : if (LIKELY (xi.len + yi.len == 2))
2340 : {
2341 4182966011 : unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2342 4182966011 : unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2343 4182966011 : return xl < yl;
2344 : }
2345 41839681 : return ltu_p_large (xi.val, xi.len, precision, yi.val, yi.len);
2346 : }
2347 :
2348 : /* Return true if X < Y. Signedness of X and Y is indicated by SGN. */
2349 : template <typename T1, typename T2>
2350 : inline bool
2351 3458985346 : wi::lt_p (const T1 &x, const T2 &y, signop sgn)
2352 : {
2353 3458496254 : if (sgn == SIGNED)
2354 1883058303 : return lts_p (x, y);
2355 : else
2356 1575927043 : return ltu_p (x, y);
2357 : }
2358 :
2359 : /* Return true if X <= Y when both are treated as signed values. */
2360 : template <typename T1, typename T2>
2361 : inline bool
2362 1788424451 : wi::les_p (const T1 &x, const T2 &y)
2363 : {
2364 1742159137 : return !lts_p (y, x);
2365 : }
2366 :
2367 : /* Return true if X <= Y when both are treated as unsigned values. */
2368 : template <typename T1, typename T2>
2369 : inline bool
2370 991046713 : wi::leu_p (const T1 &x, const T2 &y)
2371 : {
2372 990269917 : return !ltu_p (y, x);
2373 : }
2374 :
2375 : /* Return true if X <= Y. Signedness of X and Y is indicated by SGN. */
2376 : template <typename T1, typename T2>
2377 : inline bool
2378 1502764440 : wi::le_p (const T1 &x, const T2 &y, signop sgn)
2379 : {
2380 1500258047 : if (sgn == SIGNED)
2381 682121430 : return les_p (x, y);
2382 : else
2383 820643010 : return leu_p (x, y);
2384 : }
2385 :
2386 : /* Return true if X > Y when both are treated as signed values. */
2387 : template <typename T1, typename T2>
2388 : inline bool
2389 696770658 : wi::gts_p (const T1 &x, const T2 &y)
2390 : {
2391 251045774 : return lts_p (y, x);
2392 : }
2393 :
2394 : /* Return true if X > Y when both are treated as unsigned values. */
2395 : template <typename T1, typename T2>
2396 : inline bool
2397 356549888 : wi::gtu_p (const T1 &x, const T2 &y)
2398 : {
2399 204058275 : return ltu_p (y, x);
2400 : }
2401 :
2402 : /* Return true if X > Y. Signedness of X and Y is indicated by SGN. */
2403 : template <typename T1, typename T2>
2404 : inline bool
2405 323690300 : wi::gt_p (const T1 &x, const T2 &y, signop sgn)
2406 : {
2407 543415054 : if (sgn == SIGNED)
2408 263229938 : return gts_p (x, y);
2409 : else
2410 341959848 : return gtu_p (x, y);
2411 : }
2412 :
2413 : /* Return true if X >= Y when both are treated as signed values. */
2414 : template <typename T1, typename T2>
2415 : inline bool
2416 736818321 : wi::ges_p (const T1 &x, const T2 &y)
2417 : {
2418 664422477 : return !lts_p (x, y);
2419 : }
2420 :
2421 : /* Return true if X >= Y when both are treated as unsigned values. */
2422 : template <typename T1, typename T2>
2423 : inline bool
2424 5864340136 : wi::geu_p (const T1 &x, const T2 &y)
2425 : {
2426 5742270769 : return !ltu_p (x, y);
2427 : }
2428 :
2429 : /* Return true if X >= Y. Signedness of X and Y is indicated by SGN. */
2430 : template <typename T1, typename T2>
2431 : inline bool
2432 1383081558 : wi::ge_p (const T1 &x, const T2 &y, signop sgn)
2433 : {
2434 1382177859 : if (sgn == SIGNED)
2435 573015276 : return ges_p (x, y);
2436 : else
2437 810066282 : return geu_p (x, y);
2438 : }
2439 :
2440 : /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
2441 : as signed values. */
2442 : template <typename T1, typename T2>
2443 : inline int
2444 3398224410 : wi::cmps (const T1 &x, const T2 &y)
2445 : {
2446 3398224410 : unsigned int precision = get_binary_precision (x, y);
2447 3398224410 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2448 3398224410 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2449 3398224410 : if (wi::fits_shwi_p (yi))
2450 : {
2451 : /* Special case for comparisons with 0. */
2452 3395676342 : if (STATIC_CONSTANT_P (yi.val[0] == 0))
2453 0 : return neg_p (xi) ? -1 : !(xi.len == 1 && xi.val[0] == 0);
2454 : /* If x fits into a signed HWI, we can compare directly. */
2455 3395676342 : if (wi::fits_shwi_p (xi))
2456 : {
2457 3394908313 : HOST_WIDE_INT xl = xi.to_shwi ();
2458 3394908313 : HOST_WIDE_INT yl = yi.to_shwi ();
2459 3394908313 : return xl < yl ? -1 : xl > yl;
2460 : }
2461 : /* If x doesn't fit and is negative, then it must be more
2462 : negative than any signed HWI, and hence smaller than y. */
2463 768029 : if (neg_p (xi))
2464 : return -1;
2465 : /* If x is positive, then it must be larger than any signed HWI,
2466 : and hence greater than y. */
2467 : return 1;
2468 : }
2469 : /* Optimize the opposite case, if it can be detected at compile time. */
2470 2548068 : if (STATIC_CONSTANT_P (xi.len == 1))
2471 : /* If YI is negative it is lower than the least HWI.
2472 : If YI is positive it is greater than the greatest HWI. */
2473 0 : return neg_p (yi) ? 1 : -1;
2474 2548068 : return cmps_large (xi.val, xi.len, precision, yi.val, yi.len);
2475 : }
2476 :
2477 : /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
2478 : as unsigned values. */
2479 : template <typename T1, typename T2>
2480 : inline int
2481 3411601125 : wi::cmpu (const T1 &x, const T2 &y)
2482 : {
2483 3411601125 : unsigned int precision = get_binary_precision (x, y);
2484 3411601125 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2485 3411601125 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2486 : /* Optimize comparisons with constants. */
2487 4429389261 : if (STATIC_CONSTANT_P (yi.len == 1 && yi.val[0] >= 0))
2488 : {
2489 : /* If XI doesn't fit in a HWI then it must be larger than YI. */
2490 0 : if (xi.len != 1)
2491 : return 1;
2492 : /* Otherwise compare directly. */
2493 0 : unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2494 0 : unsigned HOST_WIDE_INT yl = yi.val[0];
2495 0 : return xl < yl ? -1 : xl > yl;
2496 : }
2497 4061331920 : if (STATIC_CONSTANT_P (xi.len == 1 && xi.val[0] >= 0))
2498 : {
2499 : /* If YI doesn't fit in a HWI then it must be larger than XI. */
2500 0 : if (yi.len != 1)
2501 : return -1;
2502 : /* Otherwise compare directly. */
2503 0 : unsigned HOST_WIDE_INT xl = xi.val[0];
2504 0 : unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2505 0 : return xl < yl ? -1 : xl > yl;
2506 : }
2507 : /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
2508 : for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
2509 : values does not change the result. */
2510 3411601125 : if (LIKELY (xi.len + yi.len == 2))
2511 : {
2512 3401681901 : unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2513 3401681901 : unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2514 3401681901 : return xl < yl ? -1 : xl > yl;
2515 : }
2516 9919224 : return cmpu_large (xi.val, xi.len, precision, yi.val, yi.len);
2517 : }
2518 :
2519 : /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Signedness of
2520 : X and Y indicated by SGN. */
2521 : template <typename T1, typename T2>
2522 : inline int
2523 6586975477 : wi::cmp (const T1 &x, const T2 &y, signop sgn)
2524 : {
2525 6586973863 : if (sgn == SIGNED)
2526 3180945046 : return cmps (x, y);
2527 : else
2528 3406030431 : return cmpu (x, y);
2529 : }
2530 :
2531 : /* Return ~x. */
2532 : template <typename T>
2533 : inline WI_UNARY_RESULT (T)
2534 2184809292 : wi::bit_not (const T &x)
2535 : {
2536 2184809292 : WI_UNARY_RESULT_VAR (result, val, T, x);
2537 2184809292 : WIDE_INT_REF_FOR (T) xi (x, get_precision (result));
2538 : if (result.needs_write_val_arg)
2539 1095294 : val = result.write_val (xi.len);
2540 4374166865 : for (unsigned int i = 0; i < xi.len; ++i)
2541 2189357573 : val[i] = ~xi.val[i];
2542 2184809292 : result.set_len (xi.len);
2543 2184809292 : return result;
2544 : }
2545 :
2546 : /* Return -x. */
2547 : template <typename T>
2548 : inline WI_UNARY_RESULT (T)
2549 57427202 : wi::neg (const T &x)
2550 : {
2551 45211969 : return sub (0, x);
2552 : }
2553 :
2554 : /* Return -x. Indicate in *OVERFLOW if performing the negation would
2555 : cause an overflow. */
2556 : template <typename T>
2557 : inline WI_UNARY_RESULT (T)
2558 30357557 : wi::neg (const T &x, overflow_type *overflow)
2559 : {
2560 30357557 : *overflow = only_sign_bit_p (x) ? OVF_OVERFLOW : OVF_NONE;
2561 30357557 : return sub (0, x);
2562 : }
2563 :
2564 : /* Return the absolute value of x. */
2565 : template <typename T>
2566 : inline WI_UNARY_RESULT (T)
2567 97579020 : wi::abs (const T &x)
2568 : {
2569 99479316 : return neg_p (x) ? neg (x) : WI_UNARY_RESULT (T) (x);
2570 : }
2571 :
2572 : /* Return the result of sign-extending the low OFFSET bits of X. */
2573 : template <typename T>
2574 : inline WI_UNARY_RESULT (T)
2575 2559580746 : wi::sext (const T &x, unsigned int offset)
2576 : {
2577 2559580746 : WI_UNARY_RESULT_VAR (result, val, T, x);
2578 2559580746 : unsigned int precision = get_precision (result);
2579 2559580746 : WIDE_INT_REF_FOR (T) xi (x, precision);
2580 :
2581 : if (result.needs_write_val_arg)
2582 1247757123 : val = result.write_val (MAX (xi.len,
2583 : CEIL (offset, HOST_BITS_PER_WIDE_INT)));
2584 2559580746 : if (offset <= HOST_BITS_PER_WIDE_INT)
2585 : {
2586 2554661103 : val[0] = sext_hwi (xi.ulow (), offset);
2587 2554661103 : result.set_len (1, true);
2588 : }
2589 : else
2590 4919643 : result.set_len (sext_large (val, xi.val, xi.len, precision, offset));
2591 2559580746 : return result;
2592 : }
2593 :
2594 : /* Return the result of zero-extending the low OFFSET bits of X. */
2595 : template <typename T>
2596 : inline WI_UNARY_RESULT (T)
2597 3367081542 : wi::zext (const T &x, unsigned int offset)
2598 : {
2599 3367081542 : WI_UNARY_RESULT_VAR (result, val, T, x);
2600 3367081542 : unsigned int precision = get_precision (result);
2601 3367081542 : WIDE_INT_REF_FOR (T) xi (x, precision);
2602 :
2603 : /* This is not just an optimization, it is actually required to
2604 : maintain canonization. */
2605 3367081542 : if (offset >= precision)
2606 : {
2607 2385275255 : wi::copy (result, xi);
2608 2385275255 : return result;
2609 : }
2610 :
2611 : if (result.needs_write_val_arg)
2612 472059184 : val = result.write_val (MAX (xi.len,
2613 : offset / HOST_BITS_PER_WIDE_INT + 1));
2614 : /* In these cases we know that at least the top bit will be clear,
2615 : so no sign extension is necessary. */
2616 981806287 : if (offset < HOST_BITS_PER_WIDE_INT)
2617 : {
2618 202641244 : val[0] = zext_hwi (xi.ulow (), offset);
2619 202641244 : result.set_len (1, true);
2620 : }
2621 : else
2622 779165043 : result.set_len (zext_large (val, xi.val, xi.len, precision, offset), true);
2623 : return result;
2624 : }
2625 :
2626 : /* Return the result of extending the low OFFSET bits of X according to
2627 : signedness SGN. */
2628 : template <typename T>
2629 : inline WI_UNARY_RESULT (T)
2630 863122540 : wi::ext (const T &x, unsigned int offset, signop sgn)
2631 : {
2632 863122540 : return sgn == SIGNED ? sext (x, offset) : zext (x, offset);
2633 : }
2634 :
2635 : /* Return an integer that represents X | (1 << bit). */
2636 : template <typename T>
2637 : inline WI_UNARY_RESULT (T)
2638 44992 : wi::set_bit (const T &x, unsigned int bit)
2639 : {
2640 44992 : WI_UNARY_RESULT_VAR (result, val, T, x);
2641 44992 : unsigned int precision = get_precision (result);
2642 44992 : WIDE_INT_REF_FOR (T) xi (x, precision);
2643 : if (result.needs_write_val_arg)
2644 : val = result.write_val (MAX (xi.len,
2645 : bit / HOST_BITS_PER_WIDE_INT + 1));
2646 44992 : if (precision <= HOST_BITS_PER_WIDE_INT)
2647 : {
2648 44892 : val[0] = xi.ulow () | (HOST_WIDE_INT_1U << bit);
2649 44892 : result.set_len (1);
2650 : }
2651 : else
2652 100 : result.set_len (set_bit_large (val, xi.val, xi.len, precision, bit));
2653 44992 : return result;
2654 : }
2655 :
2656 : /* Byte swap the integer X.
2657 : ??? This always swaps 8-bit octets, regardless of BITS_PER_UNIT.
2658 : This function requires X's precision to be a multiple of 16 bits,
2659 : so care needs to be taken for targets where BITS_PER_UNIT != 8. */
2660 : template <typename T>
2661 : inline WI_UNARY_RESULT (T)
2662 7680 : wi::bswap (const T &x)
2663 : {
2664 7680 : WI_UNARY_RESULT_VAR (result, val, T, x);
2665 7680 : unsigned int precision = get_precision (result);
2666 7680 : WIDE_INT_REF_FOR (T) xi (x, precision);
2667 : static_assert (!result.needs_write_val_arg,
2668 : "bswap on widest_int makes no sense");
2669 7680 : result.set_len (bswap_large (val, xi.val, xi.len, precision));
2670 7680 : return result;
2671 : }
2672 :
2673 : /* Bitreverse the integer X. */
2674 : template <typename T>
2675 : inline WI_UNARY_RESULT (T)
2676 0 : wi::bitreverse (const T &x)
2677 : {
2678 0 : WI_UNARY_RESULT_VAR (result, val, T, x);
2679 0 : unsigned int precision = get_precision (result);
2680 0 : WIDE_INT_REF_FOR (T) xi (x, precision);
2681 : static_assert (!result.needs_write_val_arg,
2682 : "bitreverse on widest_int makes no sense");
2683 0 : result.set_len (bitreverse_large (val, xi.val, xi.len, precision));
2684 0 : return result;
2685 : }
2686 :
2687 : /* Return the mininum of X and Y, treating them both as having
2688 : signedness SGN. */
2689 : template <typename T1, typename T2>
2690 : inline WI_BINARY_RESULT (T1, T2)
2691 90345759 : wi::min (const T1 &x, const T2 &y, signop sgn)
2692 : {
2693 90345759 : WI_BINARY_RESULT_VAR (result, val ATTRIBUTE_UNUSED, T1, x, T2, y);
2694 90345759 : unsigned int precision = get_precision (result);
2695 90345759 : if (wi::le_p (x, y, sgn))
2696 87207439 : wi::copy (result, WIDE_INT_REF_FOR (T1) (x, precision));
2697 : else
2698 3138320 : wi::copy (result, WIDE_INT_REF_FOR (T2) (y, precision));
2699 90345759 : return result;
2700 : }
2701 :
2702 : /* Return the minimum of X and Y, treating both as signed values. */
2703 : template <typename T1, typename T2>
2704 : inline WI_BINARY_RESULT (T1, T2)
2705 192568 : wi::smin (const T1 &x, const T2 &y)
2706 : {
2707 192568 : return wi::min (x, y, SIGNED);
2708 : }
2709 :
2710 : /* Return the minimum of X and Y, treating both as unsigned values. */
2711 : template <typename T1, typename T2>
2712 : inline WI_BINARY_RESULT (T1, T2)
2713 16057 : wi::umin (const T1 &x, const T2 &y)
2714 : {
2715 16057 : return wi::min (x, y, UNSIGNED);
2716 : }
2717 :
2718 : /* Return the maxinum of X and Y, treating them both as having
2719 : signedness SGN. */
2720 : template <typename T1, typename T2>
2721 : inline WI_BINARY_RESULT (T1, T2)
2722 191266764 : wi::max (const T1 &x, const T2 &y, signop sgn)
2723 : {
2724 191266764 : WI_BINARY_RESULT_VAR (result, val ATTRIBUTE_UNUSED, T1, x, T2, y);
2725 191266764 : unsigned int precision = get_precision (result);
2726 191266764 : if (wi::ge_p (x, y, sgn))
2727 134124175 : wi::copy (result, WIDE_INT_REF_FOR (T1) (x, precision));
2728 : else
2729 57142589 : wi::copy (result, WIDE_INT_REF_FOR (T2) (y, precision));
2730 191266764 : return result;
2731 : }
2732 :
2733 : /* Return the maximum of X and Y, treating both as signed values. */
2734 : template <typename T1, typename T2>
2735 : inline WI_BINARY_RESULT (T1, T2)
2736 1193985 : wi::smax (const T1 &x, const T2 &y)
2737 : {
2738 1181834 : return wi::max (x, y, SIGNED);
2739 : }
2740 :
2741 : /* Return the maximum of X and Y, treating both as unsigned values. */
2742 : template <typename T1, typename T2>
2743 : inline WI_BINARY_RESULT (T1, T2)
2744 278070 : wi::umax (const T1 &x, const T2 &y)
2745 : {
2746 278070 : return wi::max (x, y, UNSIGNED);
2747 : }
2748 :
2749 : /* Return X & Y. */
2750 : template <typename T1, typename T2>
2751 : inline WI_BINARY_RESULT (T1, T2)
2752 15137043368 : wi::bit_and (const T1 &x, const T2 &y)
2753 : {
2754 15137043368 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2755 15137043368 : unsigned int precision = get_precision (result);
2756 15137043368 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2757 15137043368 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2758 15137043368 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2759 : if (result.needs_write_val_arg)
2760 76138177 : val = result.write_val (MAX (xi.len, yi.len));
2761 15137043368 : if (LIKELY (xi.len + yi.len == 2))
2762 : {
2763 15111605241 : val[0] = xi.ulow () & yi.ulow ();
2764 15111605241 : result.set_len (1, is_sign_extended);
2765 : }
2766 : else
2767 25438127 : result.set_len (and_large (val, xi.val, xi.len, yi.val, yi.len,
2768 : precision), is_sign_extended);
2769 15137043368 : return result;
2770 : }
2771 :
2772 : /* Return X & ~Y. */
2773 : template <typename T1, typename T2>
2774 : inline WI_BINARY_RESULT (T1, T2)
2775 1413063825 : wi::bit_and_not (const T1 &x, const T2 &y)
2776 : {
2777 1413063825 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2778 1413063825 : unsigned int precision = get_precision (result);
2779 1413063825 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2780 1413063825 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2781 1413063825 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2782 : if (result.needs_write_val_arg)
2783 804945850 : val = result.write_val (MAX (xi.len, yi.len));
2784 1413063825 : if (LIKELY (xi.len + yi.len == 2))
2785 : {
2786 1320619372 : val[0] = xi.ulow () & ~yi.ulow ();
2787 1320619372 : result.set_len (1, is_sign_extended);
2788 : }
2789 : else
2790 92444453 : result.set_len (and_not_large (val, xi.val, xi.len, yi.val, yi.len,
2791 : precision), is_sign_extended);
2792 1413063825 : return result;
2793 : }
2794 :
2795 : /* Return X | Y. */
2796 : template <typename T1, typename T2>
2797 : inline WI_BINARY_RESULT (T1, T2)
2798 3645821893 : wi::bit_or (const T1 &x, const T2 &y)
2799 : {
2800 3645821893 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2801 3645821893 : unsigned int precision = get_precision (result);
2802 3645821893 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2803 3645821893 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2804 3645821893 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2805 : if (result.needs_write_val_arg)
2806 1281429460 : val = result.write_val (MAX (xi.len, yi.len));
2807 3645821893 : if (LIKELY (xi.len + yi.len == 2))
2808 : {
2809 3468779080 : val[0] = xi.ulow () | yi.ulow ();
2810 3468779080 : result.set_len (1, is_sign_extended);
2811 : }
2812 : else
2813 177042813 : result.set_len (or_large (val, xi.val, xi.len,
2814 : yi.val, yi.len, precision), is_sign_extended);
2815 3645821893 : return result;
2816 : }
2817 :
2818 : /* Return X | ~Y. */
2819 : template <typename T1, typename T2>
2820 : inline WI_BINARY_RESULT (T1, T2)
2821 : wi::bit_or_not (const T1 &x, const T2 &y)
2822 : {
2823 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2824 : unsigned int precision = get_precision (result);
2825 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2826 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2827 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2828 : if (result.needs_write_val_arg)
2829 : val = result.write_val (MAX (xi.len, yi.len));
2830 : if (LIKELY (xi.len + yi.len == 2))
2831 : {
2832 : val[0] = xi.ulow () | ~yi.ulow ();
2833 : result.set_len (1, is_sign_extended);
2834 : }
2835 : else
2836 : result.set_len (or_not_large (val, xi.val, xi.len, yi.val, yi.len,
2837 : precision), is_sign_extended);
2838 : return result;
2839 : }
2840 :
2841 : /* Return X ^ Y. */
2842 : template <typename T1, typename T2>
2843 : inline WI_BINARY_RESULT (T1, T2)
2844 2566383522 : wi::bit_xor (const T1 &x, const T2 &y)
2845 : {
2846 2566383522 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2847 2566383522 : unsigned int precision = get_precision (result);
2848 2566383522 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2849 2566383522 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2850 2566383522 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2851 : if (result.needs_write_val_arg)
2852 447089882 : val = result.write_val (MAX (xi.len, yi.len));
2853 2566383522 : if (LIKELY (xi.len + yi.len == 2))
2854 : {
2855 2531953599 : val[0] = xi.ulow () ^ yi.ulow ();
2856 2531953599 : result.set_len (1, is_sign_extended);
2857 : }
2858 : else
2859 34429923 : result.set_len (xor_large (val, xi.val, xi.len,
2860 : yi.val, yi.len, precision), is_sign_extended);
2861 2566383522 : return result;
2862 : }
2863 :
2864 : /* Return X + Y. */
2865 : template <typename T1, typename T2>
2866 : inline WI_BINARY_RESULT (T1, T2)
2867 10302043869 : wi::add (const T1 &x, const T2 &y)
2868 : {
2869 10302043869 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2870 10302043869 : unsigned int precision = get_precision (result);
2871 10302043869 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2872 10302043869 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2873 : if (result.needs_write_val_arg)
2874 751644337 : val = result.write_val (MAX (xi.len, yi.len) + 1);
2875 665302174 : if (precision <= HOST_BITS_PER_WIDE_INT)
2876 : {
2877 660695997 : val[0] = xi.ulow () + yi.ulow ();
2878 660695997 : result.set_len (1);
2879 : }
2880 : /* If the precision is known at compile time to be greater than
2881 : HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2882 : knowing that (a) all bits in those HWIs are significant and
2883 : (b) the result has room for at least two HWIs. This provides
2884 : a fast path for things like offset_int and widest_int.
2885 :
2886 : The STATIC_CONSTANT_P test prevents this path from being
2887 : used for wide_ints. wide_ints with precisions greater than
2888 : HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2889 : point handling them inline. */
2890 : else if (STATIC_CONSTANT_P (precision > HOST_BITS_PER_WIDE_INT)
2891 9641347872 : && LIKELY (xi.len + yi.len == 2))
2892 : {
2893 9568281837 : unsigned HOST_WIDE_INT xl = xi.ulow ();
2894 9568281837 : unsigned HOST_WIDE_INT yl = yi.ulow ();
2895 9568281837 : unsigned HOST_WIDE_INT resultl = xl + yl;
2896 9568281837 : val[0] = resultl;
2897 9568281837 : val[1] = (HOST_WIDE_INT) resultl < 0 ? 0 : -1;
2898 9568281837 : result.set_len (1 + (((resultl ^ xl) & (resultl ^ yl))
2899 9568281837 : >> (HOST_BITS_PER_WIDE_INT - 1)));
2900 687799397 : }
2901 : else
2902 73066035 : result.set_len (add_large (val, xi.val, xi.len,
2903 : yi.val, yi.len, precision,
2904 : UNSIGNED, 0));
2905 10302043869 : return result;
2906 : }
2907 :
2908 : /* Return X + Y. Treat X and Y as having the signednes given by SGN
2909 : and indicate in *OVERFLOW whether the operation overflowed. */
2910 : template <typename T1, typename T2>
2911 : inline WI_BINARY_RESULT (T1, T2)
2912 614007774 : wi::add (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
2913 : {
2914 614007774 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2915 614007774 : unsigned int precision = get_precision (result);
2916 614007774 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2917 614007774 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2918 : if (result.needs_write_val_arg)
2919 18411396 : val = result.write_val (MAX (xi.len, yi.len) + 1);
2920 595596378 : if (precision <= HOST_BITS_PER_WIDE_INT)
2921 : {
2922 556436610 : unsigned HOST_WIDE_INT xl = xi.ulow ();
2923 556436610 : unsigned HOST_WIDE_INT yl = yi.ulow ();
2924 556436610 : unsigned HOST_WIDE_INT resultl = xl + yl;
2925 556436610 : if (sgn == SIGNED)
2926 : {
2927 189635370 : if ((((resultl ^ xl) & (resultl ^ yl))
2928 189635370 : >> (precision - 1)) & 1)
2929 : {
2930 17970891 : if (xl > resultl)
2931 5598346 : *overflow = OVF_UNDERFLOW;
2932 12372545 : else if (xl < resultl)
2933 12372545 : *overflow = OVF_OVERFLOW;
2934 : else
2935 0 : *overflow = OVF_NONE;
2936 : }
2937 : else
2938 171664479 : *overflow = OVF_NONE;
2939 : }
2940 : else
2941 366801240 : *overflow = ((resultl << (HOST_BITS_PER_WIDE_INT - precision))
2942 366801240 : < (xl << (HOST_BITS_PER_WIDE_INT - precision)))
2943 366801240 : ? OVF_OVERFLOW : OVF_NONE;
2944 556436610 : val[0] = resultl;
2945 556436610 : result.set_len (1);
2946 : }
2947 : else
2948 57571164 : result.set_len (add_large (val, xi.val, xi.len,
2949 : yi.val, yi.len, precision,
2950 : sgn, overflow));
2951 614007774 : return result;
2952 : }
2953 :
2954 : /* Return X - Y. */
2955 : template <typename T1, typename T2>
2956 : inline WI_BINARY_RESULT (T1, T2)
2957 3262799545 : wi::sub (const T1 &x, const T2 &y)
2958 : {
2959 3262799545 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2960 3262799545 : unsigned int precision = get_precision (result);
2961 3262799545 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2962 3262799545 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2963 : if (result.needs_write_val_arg)
2964 382383577 : val = result.write_val (MAX (xi.len, yi.len) + 1);
2965 310738133 : if (precision <= HOST_BITS_PER_WIDE_INT)
2966 : {
2967 308448385 : val[0] = xi.ulow () - yi.ulow ();
2968 308448385 : result.set_len (1);
2969 : }
2970 : /* If the precision is known at compile time to be greater than
2971 : HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2972 : knowing that (a) all bits in those HWIs are significant and
2973 : (b) the result has room for at least two HWIs. This provides
2974 : a fast path for things like offset_int and widest_int.
2975 :
2976 : The STATIC_CONSTANT_P test prevents this path from being
2977 : used for wide_ints. wide_ints with precisions greater than
2978 : HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2979 : point handling them inline. */
2980 : else if (STATIC_CONSTANT_P (precision > HOST_BITS_PER_WIDE_INT)
2981 2954351160 : && LIKELY (xi.len + yi.len == 2))
2982 : {
2983 2898326641 : unsigned HOST_WIDE_INT xl = xi.ulow ();
2984 2898326641 : unsigned HOST_WIDE_INT yl = yi.ulow ();
2985 2898326641 : unsigned HOST_WIDE_INT resultl = xl - yl;
2986 2898326641 : val[0] = resultl;
2987 2898326641 : val[1] = (HOST_WIDE_INT) resultl < 0 ? 0 : -1;
2988 2898326641 : result.set_len (1 + (((resultl ^ xl) & (xl ^ yl))
2989 2898326641 : >> (HOST_BITS_PER_WIDE_INT - 1)));
2990 330725378 : }
2991 : else
2992 56024519 : result.set_len (sub_large (val, xi.val, xi.len,
2993 : yi.val, yi.len, precision,
2994 : UNSIGNED, 0));
2995 3262799545 : return result;
2996 : }
2997 :
2998 : /* Return X - Y. Treat X and Y as having the signednes given by SGN
2999 : and indicate in *OVERFLOW whether the operation overflowed. */
3000 : template <typename T1, typename T2>
3001 : inline WI_BINARY_RESULT (T1, T2)
3002 242570677 : wi::sub (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3003 : {
3004 242570677 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3005 242570677 : unsigned int precision = get_precision (result);
3006 242570677 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3007 242570677 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3008 : if (result.needs_write_val_arg)
3009 4916 : val = result.write_val (MAX (xi.len, yi.len) + 1);
3010 242565761 : if (precision <= HOST_BITS_PER_WIDE_INT)
3011 : {
3012 241479659 : unsigned HOST_WIDE_INT xl = xi.ulow ();
3013 241479659 : unsigned HOST_WIDE_INT yl = yi.ulow ();
3014 241479659 : unsigned HOST_WIDE_INT resultl = xl - yl;
3015 241479659 : if (sgn == SIGNED)
3016 : {
3017 118567147 : if ((((xl ^ yl) & (resultl ^ xl)) >> (precision - 1)) & 1)
3018 : {
3019 7396589 : if (xl > yl)
3020 3903428 : *overflow = OVF_UNDERFLOW;
3021 3493161 : else if (xl < yl)
3022 3493161 : *overflow = OVF_OVERFLOW;
3023 : else
3024 0 : *overflow = OVF_NONE;
3025 : }
3026 : else
3027 111170558 : *overflow = OVF_NONE;
3028 : }
3029 : else
3030 122912512 : *overflow = ((resultl << (HOST_BITS_PER_WIDE_INT - precision))
3031 122912512 : > (xl << (HOST_BITS_PER_WIDE_INT - precision)))
3032 122912512 : ? OVF_UNDERFLOW : OVF_NONE;
3033 241479659 : val[0] = resultl;
3034 241479659 : result.set_len (1);
3035 : }
3036 : else
3037 1091018 : result.set_len (sub_large (val, xi.val, xi.len,
3038 : yi.val, yi.len, precision,
3039 : sgn, overflow));
3040 242570677 : return result;
3041 : }
3042 :
3043 : /* Return X * Y. */
3044 : template <typename T1, typename T2>
3045 : inline WI_BINARY_RESULT (T1, T2)
3046 1154262895 : wi::mul (const T1 &x, const T2 &y)
3047 : {
3048 1154262895 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3049 1154262895 : unsigned int precision = get_precision (result);
3050 1154262895 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3051 1154262895 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3052 : if (result.needs_write_val_arg)
3053 176061033 : val = result.write_val (xi.len + yi.len + 2);
3054 1280043 : if (precision <= HOST_BITS_PER_WIDE_INT)
3055 : {
3056 1090199 : val[0] = xi.ulow () * yi.ulow ();
3057 1090199 : result.set_len (1);
3058 : }
3059 : else
3060 1153172696 : result.set_len (mul_internal (val, xi.val, xi.len, yi.val, yi.len,
3061 : precision, UNSIGNED, 0, false));
3062 1154262895 : return result;
3063 : }
3064 :
3065 : /* Return X * Y. Treat X and Y as having the signednes given by SGN
3066 : and indicate in *OVERFLOW whether the operation overflowed. */
3067 : template <typename T1, typename T2>
3068 : inline WI_BINARY_RESULT (T1, T2)
3069 465318327 : wi::mul (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3070 : {
3071 465318327 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3072 465318327 : unsigned int precision = get_precision (result);
3073 465318327 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3074 465318327 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3075 : if (result.needs_write_val_arg)
3076 3483569 : val = result.write_val (xi.len + yi.len + 2);
3077 465318327 : result.set_len (mul_internal (val, xi.val, xi.len,
3078 : yi.val, yi.len, precision,
3079 : sgn, overflow, false));
3080 465318327 : return result;
3081 : }
3082 :
3083 : /* Return X * Y, treating both X and Y as signed values. Indicate in
3084 : *OVERFLOW whether the operation overflowed. */
3085 : template <typename T1, typename T2>
3086 : inline WI_BINARY_RESULT (T1, T2)
3087 3916 : wi::smul (const T1 &x, const T2 &y, overflow_type *overflow)
3088 : {
3089 3916 : return mul (x, y, SIGNED, overflow);
3090 : }
3091 :
3092 : /* Return X * Y, treating both X and Y as unsigned values. Indicate in
3093 : *OVERFLOW if the result overflows. */
3094 : template <typename T1, typename T2>
3095 : inline WI_BINARY_RESULT (T1, T2)
3096 3375746 : wi::umul (const T1 &x, const T2 &y, overflow_type *overflow)
3097 : {
3098 3375746 : return mul (x, y, UNSIGNED, overflow);
3099 : }
3100 :
3101 : /* Perform a widening multiplication of X and Y, extending the values
3102 : according to SGN, and return the high part of the result. */
3103 : template <typename T1, typename T2>
3104 : inline WI_BINARY_RESULT (T1, T2)
3105 5296 : wi::mul_high (const T1 &x, const T2 &y, signop sgn)
3106 : {
3107 5296 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3108 5296 : unsigned int precision = get_precision (result);
3109 5296 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3110 5296 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3111 : static_assert (!result.needs_write_val_arg,
3112 : "mul_high on widest_int doesn't make sense");
3113 5296 : result.set_len (mul_internal (val, xi.val, xi.len,
3114 : yi.val, yi.len, precision,
3115 : sgn, 0, true));
3116 5296 : return result;
3117 : }
3118 :
3119 : /* Return X / Y, rouding towards 0. Treat X and Y as having the
3120 : signedness given by SGN. Indicate in *OVERFLOW if the result
3121 : overflows. */
3122 : template <typename T1, typename T2>
3123 : inline WI_BINARY_RESULT (T1, T2)
3124 410387242 : wi::div_trunc (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3125 : {
3126 410387242 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3127 410387242 : unsigned int precision = get_precision (quotient);
3128 410387242 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3129 410387242 : WIDE_INT_REF_FOR (T2) yi (y);
3130 :
3131 : if (quotient.needs_write_val_arg)
3132 29671356 : quotient_val = quotient.write_val ((sgn == UNSIGNED
3133 387457 : && xi.val[xi.len - 1] < 0)
3134 : ? CEIL (precision,
3135 : HOST_BITS_PER_WIDE_INT) + 1
3136 14835678 : : xi.len + 1);
3137 410387242 : quotient.set_len (divmod_internal (quotient_val, 0, 0, xi.val, xi.len,
3138 : precision,
3139 : yi.val, yi.len, yi.precision,
3140 : sgn, overflow));
3141 410387242 : return quotient;
3142 : }
3143 :
3144 : /* Return X / Y, rouding towards 0. Treat X and Y as signed values. */
3145 : template <typename T1, typename T2>
3146 : inline WI_BINARY_RESULT (T1, T2)
3147 15120592 : wi::sdiv_trunc (const T1 &x, const T2 &y)
3148 : {
3149 15089323 : return div_trunc (x, y, SIGNED);
3150 : }
3151 :
3152 : /* Return X / Y, rouding towards 0. Treat X and Y as unsigned values. */
3153 : template <typename T1, typename T2>
3154 : inline WI_BINARY_RESULT (T1, T2)
3155 2422497 : wi::udiv_trunc (const T1 &x, const T2 &y)
3156 : {
3157 2422497 : return div_trunc (x, y, UNSIGNED);
3158 : }
3159 :
3160 : /* Return X / Y, rouding towards -inf. Treat X and Y as having the
3161 : signedness given by SGN. Indicate in *OVERFLOW if the result
3162 : overflows. */
3163 : template <typename T1, typename T2>
3164 : inline WI_BINARY_RESULT (T1, T2)
3165 87101672 : wi::div_floor (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3166 : {
3167 87101685 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3168 87101672 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3169 87101672 : unsigned int precision = get_precision (quotient);
3170 87101672 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3171 87101672 : WIDE_INT_REF_FOR (T2) yi (y);
3172 :
3173 : unsigned int remainder_len;
3174 : if (quotient.needs_write_val_arg)
3175 : {
3176 : unsigned int est_len;
3177 242444 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3178 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3179 : else
3180 242444 : est_len = xi.len + 1;
3181 242444 : quotient_val = quotient.write_val (est_len);
3182 242444 : remainder_val = remainder.write_val (est_len);
3183 : }
3184 87101672 : quotient.set_len (divmod_internal (quotient_val,
3185 : &remainder_len, remainder_val,
3186 : xi.val, xi.len, precision,
3187 : yi.val, yi.len, yi.precision, sgn,
3188 : overflow));
3189 87101672 : remainder.set_len (remainder_len);
3190 87101672 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn) && remainder != 0)
3191 28078 : return quotient - 1;
3192 87073594 : return quotient;
3193 84701657 : }
3194 :
3195 : /* Return X / Y, rouding towards -inf. Treat X and Y as signed values. */
3196 : template <typename T1, typename T2>
3197 : inline WI_BINARY_RESULT (T1, T2)
3198 101614 : wi::sdiv_floor (const T1 &x, const T2 &y)
3199 : {
3200 101614 : return div_floor (x, y, SIGNED);
3201 : }
3202 :
3203 : /* Return X / Y, rouding towards -inf. Treat X and Y as unsigned values. */
3204 : /* ??? Why do we have both this and udiv_trunc. Aren't they the same? */
3205 : template <typename T1, typename T2>
3206 : inline WI_BINARY_RESULT (T1, T2)
3207 2466581 : wi::udiv_floor (const T1 &x, const T2 &y)
3208 : {
3209 2466581 : return div_floor (x, y, UNSIGNED);
3210 : }
3211 :
3212 : /* Return X / Y, rouding towards +inf. Treat X and Y as having the
3213 : signedness given by SGN. Indicate in *OVERFLOW if the result
3214 : overflows. */
3215 : template <typename T1, typename T2>
3216 : inline WI_BINARY_RESULT (T1, T2)
3217 93887949 : wi::div_ceil (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3218 : {
3219 93887949 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3220 93887949 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3221 93887949 : unsigned int precision = get_precision (quotient);
3222 93887949 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3223 93887949 : WIDE_INT_REF_FOR (T2) yi (y);
3224 :
3225 : unsigned int remainder_len;
3226 : if (quotient.needs_write_val_arg)
3227 : {
3228 : unsigned int est_len;
3229 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3230 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3231 : else
3232 : est_len = xi.len + 1;
3233 : quotient_val = quotient.write_val (est_len);
3234 : remainder_val = remainder.write_val (est_len);
3235 : }
3236 93887949 : quotient.set_len (divmod_internal (quotient_val,
3237 : &remainder_len, remainder_val,
3238 : xi.val, xi.len, precision,
3239 : yi.val, yi.len, yi.precision, sgn,
3240 : overflow));
3241 93887949 : remainder.set_len (remainder_len);
3242 93887949 : if (wi::neg_p (x, sgn) == wi::neg_p (y, sgn) && remainder != 0)
3243 1132802 : return quotient + 1;
3244 92755147 : return quotient;
3245 93884440 : }
3246 :
3247 : /* Return X / Y, rouding towards +inf. Treat X and Y as unsigned values. */
3248 : template <typename T1, typename T2>
3249 : inline WI_BINARY_RESULT (T1, T2)
3250 3509 : wi::udiv_ceil (const T1 &x, const T2 &y)
3251 : {
3252 3509 : return div_ceil (x, y, UNSIGNED);
3253 : }
3254 :
3255 : /* Return X / Y, rouding towards nearest with ties away from zero.
3256 : Treat X and Y as having the signedness given by SGN. Indicate
3257 : in *OVERFLOW if the result overflows. */
3258 : template <typename T1, typename T2>
3259 : inline WI_BINARY_RESULT (T1, T2)
3260 288 : wi::div_round (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3261 : {
3262 288 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3263 288 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3264 288 : unsigned int precision = get_precision (quotient);
3265 288 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3266 288 : WIDE_INT_REF_FOR (T2) yi (y);
3267 :
3268 : unsigned int remainder_len;
3269 : if (quotient.needs_write_val_arg)
3270 : {
3271 : unsigned int est_len;
3272 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3273 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3274 : else
3275 : est_len = xi.len + 1;
3276 : quotient_val = quotient.write_val (est_len);
3277 : remainder_val = remainder.write_val (est_len);
3278 : }
3279 288 : quotient.set_len (divmod_internal (quotient_val,
3280 : &remainder_len, remainder_val,
3281 : xi.val, xi.len, precision,
3282 : yi.val, yi.len, yi.precision, sgn,
3283 : overflow));
3284 288 : remainder.set_len (remainder_len);
3285 :
3286 576 : if (remainder != 0)
3287 : {
3288 208 : if (sgn == SIGNED)
3289 : {
3290 112 : WI_BINARY_RESULT (T1, T2) abs_remainder = wi::abs (remainder);
3291 112 : if (wi::geu_p (abs_remainder, wi::sub (wi::abs (y), abs_remainder)))
3292 : {
3293 64 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn))
3294 0 : return quotient - 1;
3295 : else
3296 64 : return quotient + 1;
3297 : }
3298 112 : }
3299 : else
3300 : {
3301 96 : if (wi::geu_p (remainder, wi::sub (y, remainder)))
3302 64 : return quotient + 1;
3303 : }
3304 : }
3305 160 : return quotient;
3306 288 : }
3307 :
3308 : /* Return X / Y, rouding towards 0. Treat X and Y as having the
3309 : signedness given by SGN. Store the remainder in *REMAINDER_PTR. */
3310 : template <typename T1, typename T2>
3311 : inline WI_BINARY_RESULT (T1, T2)
3312 431003 : wi::divmod_trunc (const T1 &x, const T2 &y, signop sgn,
3313 : WI_BINARY_RESULT (T1, T2) *remainder_ptr)
3314 : {
3315 451508 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3316 431003 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3317 431003 : unsigned int precision = get_precision (quotient);
3318 431003 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3319 431003 : WIDE_INT_REF_FOR (T2) yi (y);
3320 :
3321 : unsigned int remainder_len;
3322 : if (quotient.needs_write_val_arg)
3323 : {
3324 : unsigned int est_len;
3325 104851 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3326 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3327 : else
3328 104851 : est_len = xi.len + 1;
3329 104851 : quotient_val = quotient.write_val (est_len);
3330 104851 : remainder_val = remainder.write_val (est_len);
3331 : }
3332 431003 : quotient.set_len (divmod_internal (quotient_val,
3333 : &remainder_len, remainder_val,
3334 : xi.val, xi.len, precision,
3335 : yi.val, yi.len, yi.precision, sgn, 0));
3336 431003 : remainder.set_len (remainder_len);
3337 :
3338 431003 : *remainder_ptr = remainder;
3339 431003 : return quotient;
3340 125356 : }
3341 :
3342 : /* Compute the greatest common divisor of two numbers A and B using
3343 : Euclid's algorithm. */
3344 : template <typename T1, typename T2>
3345 : inline WI_BINARY_RESULT (T1, T2)
3346 4889 : wi::gcd (const T1 &a, const T2 &b, signop sgn)
3347 : {
3348 4889 : T1 x, y, z;
3349 :
3350 4889 : x = wi::abs (a);
3351 4889 : y = wi::abs (b);
3352 :
3353 19451 : while (gt_p (x, 0, sgn))
3354 : {
3355 14562 : z = mod_trunc (y, x, sgn);
3356 14562 : y = x;
3357 14562 : x = z;
3358 : }
3359 :
3360 4889 : return y;
3361 4889 : }
3362 :
3363 : /* Compute X / Y, rouding towards 0, and return the remainder.
3364 : Treat X and Y as having the signedness given by SGN. Indicate
3365 : in *OVERFLOW if the division overflows. */
3366 : template <typename T1, typename T2>
3367 : inline WI_BINARY_RESULT (T1, T2)
3368 31080345 : wi::mod_trunc (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3369 : {
3370 31080345 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3371 31080345 : unsigned int precision = get_precision (remainder);
3372 31080345 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3373 31080345 : WIDE_INT_REF_FOR (T2) yi (y);
3374 :
3375 : unsigned int remainder_len;
3376 : if (remainder.needs_write_val_arg)
3377 33309982 : remainder_val = remainder.write_val ((sgn == UNSIGNED
3378 107852 : && xi.val[xi.len - 1] < 0)
3379 : ? CEIL (precision,
3380 : HOST_BITS_PER_WIDE_INT) + 1
3381 16654991 : : xi.len + 1);
3382 31080345 : divmod_internal (0, &remainder_len, remainder_val,
3383 : xi.val, xi.len, precision,
3384 : yi.val, yi.len, yi.precision, sgn, overflow);
3385 31080345 : remainder.set_len (remainder_len);
3386 :
3387 31080345 : return remainder;
3388 : }
3389 :
3390 : /* Compute X / Y, rouding towards 0, and return the remainder.
3391 : Treat X and Y as signed values. */
3392 : template <typename T1, typename T2>
3393 : inline WI_BINARY_RESULT (T1, T2)
3394 17771872 : wi::smod_trunc (const T1 &x, const T2 &y)
3395 : {
3396 17771872 : return mod_trunc (x, y, SIGNED);
3397 : }
3398 :
3399 : /* Compute X / Y, rouding towards 0, and return the remainder.
3400 : Treat X and Y as unsigned values. */
3401 : template <typename T1, typename T2>
3402 : inline WI_BINARY_RESULT (T1, T2)
3403 6069260 : wi::umod_trunc (const T1 &x, const T2 &y)
3404 : {
3405 6069260 : return mod_trunc (x, y, UNSIGNED);
3406 : }
3407 :
3408 : /* Compute X / Y, rouding towards -inf, and return the remainder.
3409 : Treat X and Y as having the signedness given by SGN. Indicate
3410 : in *OVERFLOW if the division overflows. */
3411 : template <typename T1, typename T2>
3412 : inline WI_BINARY_RESULT (T1, T2)
3413 72824184 : wi::mod_floor (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3414 : {
3415 72824184 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3416 72824184 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3417 72824184 : unsigned int precision = get_precision (quotient);
3418 72824184 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3419 72824184 : WIDE_INT_REF_FOR (T2) yi (y);
3420 :
3421 : unsigned int remainder_len;
3422 : if (quotient.needs_write_val_arg)
3423 : {
3424 : unsigned int est_len;
3425 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3426 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3427 : else
3428 : est_len = xi.len + 1;
3429 : quotient_val = quotient.write_val (est_len);
3430 : remainder_val = remainder.write_val (est_len);
3431 : }
3432 72824184 : quotient.set_len (divmod_internal (quotient_val,
3433 : &remainder_len, remainder_val,
3434 : xi.val, xi.len, precision,
3435 : yi.val, yi.len, yi.precision, sgn,
3436 : overflow));
3437 72824184 : remainder.set_len (remainder_len);
3438 :
3439 72824184 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn) && remainder != 0)
3440 1317 : return remainder + y;
3441 72822867 : return remainder;
3442 72773917 : }
3443 :
3444 : /* Compute X / Y, rouding towards -inf, and return the remainder.
3445 : Treat X and Y as unsigned values. */
3446 : /* ??? Why do we have both this and umod_trunc. Aren't they the same? */
3447 : template <typename T1, typename T2>
3448 : inline WI_BINARY_RESULT (T1, T2)
3449 50267 : wi::umod_floor (const T1 &x, const T2 &y)
3450 : {
3451 50267 : return mod_floor (x, y, UNSIGNED);
3452 : }
3453 :
3454 : /* Compute X / Y, rouding towards +inf, and return the remainder.
3455 : Treat X and Y as having the signedness given by SGN. Indicate
3456 : in *OVERFLOW if the division overflows. */
3457 : template <typename T1, typename T2>
3458 : inline WI_BINARY_RESULT (T1, T2)
3459 178 : wi::mod_ceil (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3460 : {
3461 178 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3462 178 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3463 178 : unsigned int precision = get_precision (quotient);
3464 178 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3465 178 : WIDE_INT_REF_FOR (T2) yi (y);
3466 :
3467 : unsigned int remainder_len;
3468 : if (quotient.needs_write_val_arg)
3469 : {
3470 : unsigned int est_len;
3471 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3472 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3473 : else
3474 : est_len = xi.len + 1;
3475 : quotient_val = quotient.write_val (est_len);
3476 : remainder_val = remainder.write_val (est_len);
3477 : }
3478 178 : quotient.set_len (divmod_internal (quotient_val,
3479 : &remainder_len, remainder_val,
3480 : xi.val, xi.len, precision,
3481 : yi.val, yi.len, yi.precision, sgn,
3482 : overflow));
3483 178 : remainder.set_len (remainder_len);
3484 :
3485 178 : if (wi::neg_p (x, sgn) == wi::neg_p (y, sgn) && remainder != 0)
3486 70 : return remainder - y;
3487 108 : return remainder;
3488 178 : }
3489 :
3490 : /* Compute X / Y, rouding towards nearest with ties away from zero,
3491 : and return the remainder. Treat X and Y as having the signedness
3492 : given by SGN. Indicate in *OVERFLOW if the division overflows. */
3493 : template <typename T1, typename T2>
3494 : inline WI_BINARY_RESULT (T1, T2)
3495 0 : wi::mod_round (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3496 : {
3497 0 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3498 0 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3499 0 : unsigned int precision = get_precision (quotient);
3500 0 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3501 0 : WIDE_INT_REF_FOR (T2) yi (y);
3502 :
3503 : unsigned int remainder_len;
3504 : if (quotient.needs_write_val_arg)
3505 : {
3506 : unsigned int est_len;
3507 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3508 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3509 : else
3510 : est_len = xi.len + 1;
3511 : quotient_val = quotient.write_val (est_len);
3512 : remainder_val = remainder.write_val (est_len);
3513 : }
3514 0 : quotient.set_len (divmod_internal (quotient_val,
3515 : &remainder_len, remainder_val,
3516 : xi.val, xi.len, precision,
3517 : yi.val, yi.len, yi.precision, sgn,
3518 : overflow));
3519 0 : remainder.set_len (remainder_len);
3520 :
3521 0 : if (remainder != 0)
3522 : {
3523 0 : if (sgn == SIGNED)
3524 : {
3525 0 : WI_BINARY_RESULT (T1, T2) abs_remainder = wi::abs (remainder);
3526 0 : if (wi::geu_p (abs_remainder, wi::sub (wi::abs (y), abs_remainder)))
3527 : {
3528 0 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn))
3529 0 : return remainder + y;
3530 : else
3531 0 : return remainder - y;
3532 : }
3533 0 : }
3534 : else
3535 : {
3536 0 : if (wi::geu_p (remainder, wi::sub (y, remainder)))
3537 0 : return remainder - y;
3538 : }
3539 : }
3540 0 : return remainder;
3541 0 : }
3542 :
3543 : /* Return true if X is a multiple of Y. Treat X and Y as having the
3544 : signedness given by SGN. */
3545 : template <typename T1, typename T2>
3546 : inline bool
3547 4521243 : wi::multiple_of_p (const T1 &x, const T2 &y, signop sgn)
3548 : {
3549 8897913 : return wi::mod_trunc (x, y, sgn) == 0;
3550 : }
3551 :
3552 : /* Return true if X is a multiple of Y, storing X / Y in *RES if so.
3553 : Treat X and Y as having the signedness given by SGN. */
3554 : template <typename T1, typename T2>
3555 : inline bool
3556 407812 : wi::multiple_of_p (const T1 &x, const T2 &y, signop sgn,
3557 : WI_BINARY_RESULT (T1, T2) *res)
3558 : {
3559 407812 : WI_BINARY_RESULT (T1, T2) remainder;
3560 102165 : WI_BINARY_RESULT (T1, T2) quotient
3561 305647 : = divmod_trunc (x, y, sgn, &remainder);
3562 407812 : if (remainder == 0)
3563 : {
3564 365582 : *res = quotient;
3565 365582 : return true;
3566 : }
3567 : return false;
3568 102165 : }
3569 :
3570 : /* Return X << Y. Return 0 if Y is greater than or equal to
3571 : the precision of X. */
3572 : template <typename T1, typename T2>
3573 : inline WI_UNARY_RESULT (T1)
3574 4442585855 : wi::lshift (const T1 &x, const T2 &y)
3575 : {
3576 4442585855 : WI_UNARY_RESULT_VAR (result, val, T1, x);
3577 4442585855 : unsigned int precision = get_precision (result);
3578 4442585855 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3579 4442585855 : WIDE_INT_REF_FOR (T2) yi (y);
3580 : /* Handle the simple cases quickly. */
3581 4442585855 : if (geu_p (yi, precision))
3582 : {
3583 : if (result.needs_write_val_arg)
3584 0 : val = result.write_val (1);
3585 2910670 : val[0] = 0;
3586 2910670 : result.set_len (1);
3587 : }
3588 : else
3589 : {
3590 4439675185 : unsigned int shift = yi.to_uhwi ();
3591 : if (result.needs_write_val_arg)
3592 108769195 : val = result.write_val (xi.len + shift / HOST_BITS_PER_WIDE_INT + 1);
3593 : /* For fixed-precision integers like offset_int and widest_int,
3594 : handle the case where the shift value is constant and the
3595 : result is a single nonnegative HWI (meaning that we don't
3596 : need to worry about val[1]). This is particularly common
3597 : for converting a byte count to a bit count.
3598 :
3599 : For variable-precision integers like wide_int, handle HWI
3600 : and sub-HWI integers inline. */
3601 212344975 : if (STATIC_CONSTANT_P (xi.precision > HOST_BITS_PER_WIDE_INT)
3602 4439675185 : ? (STATIC_CONSTANT_P (shift < HOST_BITS_PER_WIDE_INT - 1)
3603 0 : && xi.len == 1
3604 0 : && IN_RANGE (xi.val[0], 0, HOST_WIDE_INT_MAX >> shift))
3605 : : precision <= HOST_BITS_PER_WIDE_INT)
3606 : {
3607 209050524 : val[0] = xi.ulow () << shift;
3608 209050524 : result.set_len (1);
3609 : }
3610 : else
3611 4230624661 : result.set_len (lshift_large (val, xi.val, xi.len,
3612 : precision, shift));
3613 : }
3614 4442585855 : return result;
3615 : }
3616 :
3617 : /* Return X >> Y, using a logical shift. Return 0 if Y is greater than
3618 : or equal to the precision of X. */
3619 : template <typename T1, typename T2>
3620 : inline WI_UNARY_RESULT (T1)
3621 37136541 : wi::lrshift (const T1 &x, const T2 &y)
3622 : {
3623 62426413 : WI_UNARY_RESULT_VAR (result, val, T1, x);
3624 : /* Do things in the precision of the input rather than the output,
3625 : since the result can be no larger than that. */
3626 37136541 : WIDE_INT_REF_FOR (T1) xi (x);
3627 37136541 : WIDE_INT_REF_FOR (T2) yi (y);
3628 : /* Handle the simple cases quickly. */
3629 37136541 : if (geu_p (yi, xi.precision))
3630 : {
3631 : if (result.needs_write_val_arg)
3632 66 : val = result.write_val (1);
3633 2737315 : val[0] = 0;
3634 2737315 : result.set_len (1);
3635 : }
3636 : else
3637 : {
3638 34399226 : unsigned int shift = yi.to_uhwi ();
3639 : if (result.needs_write_val_arg)
3640 : {
3641 8122854 : unsigned int est_len = xi.len;
3642 8122854 : if (xi.val[xi.len - 1] < 0 && shift)
3643 : /* Logical right shift of sign-extended value might need a very
3644 : large precision e.g. for widest_int. */
3645 0 : est_len = CEIL (xi.precision - shift, HOST_BITS_PER_WIDE_INT) + 1;
3646 8122854 : val = result.write_val (est_len);
3647 : }
3648 : /* For fixed-precision integers like offset_int and widest_int,
3649 : handle the case where the shift value is constant and the
3650 : shifted value is a single nonnegative HWI (meaning that all
3651 : bits above the HWI are zero). This is particularly common
3652 : for converting a bit count to a byte count.
3653 :
3654 : For variable-precision integers like wide_int, handle HWI
3655 : and sub-HWI integers inline. */
3656 34399226 : if (STATIC_CONSTANT_P (xi.precision > HOST_BITS_PER_WIDE_INT)
3657 34399226 : ? (shift < HOST_BITS_PER_WIDE_INT
3658 0 : && xi.len == 1
3659 0 : && xi.val[0] >= 0)
3660 : : xi.precision <= HOST_BITS_PER_WIDE_INT)
3661 : {
3662 24754517 : val[0] = xi.to_uhwi () >> shift;
3663 24754517 : result.set_len (1);
3664 : }
3665 : else
3666 9644709 : result.set_len (lrshift_large (val, xi.val, xi.len, xi.precision,
3667 : get_precision (result), shift));
3668 : }
3669 37136541 : return result;
3670 : }
3671 :
3672 : /* Return X >> Y, using an arithmetic shift. Return a sign mask if
3673 : Y is greater than or equal to the precision of X. */
3674 : template <typename T1, typename T2>
3675 : inline WI_UNARY_RESULT (T1)
3676 163601753 : wi::arshift (const T1 &x, const T2 &y)
3677 : {
3678 168852580 : WI_UNARY_RESULT_VAR (result, val, T1, x);
3679 : /* Do things in the precision of the input rather than the output,
3680 : since the result can be no larger than that. */
3681 163601753 : WIDE_INT_REF_FOR (T1) xi (x);
3682 163601753 : WIDE_INT_REF_FOR (T2) yi (y);
3683 : if (result.needs_write_val_arg)
3684 5463091 : val = result.write_val (xi.len);
3685 : /* Handle the simple cases quickly. */
3686 163601753 : if (geu_p (yi, xi.precision))
3687 : {
3688 227 : val[0] = sign_mask (x);
3689 227 : result.set_len (1);
3690 : }
3691 : else
3692 : {
3693 163601526 : unsigned int shift = yi.to_uhwi ();
3694 163601526 : if (xi.precision <= HOST_BITS_PER_WIDE_INT)
3695 : {
3696 5182031 : val[0] = sext_hwi (xi.ulow () >> shift, xi.precision - shift);
3697 5182031 : result.set_len (1, true);
3698 : }
3699 : else
3700 158419495 : result.set_len (arshift_large (val, xi.val, xi.len, xi.precision,
3701 : get_precision (result), shift));
3702 : }
3703 163601753 : return result;
3704 : }
3705 :
3706 : /* Return X >> Y, using an arithmetic shift if SGN is SIGNED and a
3707 : logical shift otherwise. */
3708 : template <typename T1, typename T2>
3709 : inline WI_UNARY_RESULT (T1)
3710 39769508 : wi::rshift (const T1 &x, const T2 &y, signop sgn)
3711 : {
3712 39765359 : if (sgn == UNSIGNED)
3713 29140725 : return lrshift (x, y);
3714 : else
3715 10628783 : return arshift (x, y);
3716 : }
3717 :
3718 : /* Return the result of rotating the low WIDTH bits of X left by Y
3719 : bits and zero-extending the result. Use a full-width rotate if
3720 : WIDTH is zero. */
3721 : template <typename T1, typename T2>
3722 : WI_UNARY_RESULT (T1)
3723 51978 : wi::lrotate (const T1 &x, const T2 &y, unsigned int width)
3724 : {
3725 51978 : unsigned int precision = get_binary_precision (x, x);
3726 51978 : if (width == 0)
3727 11756 : width = precision;
3728 51978 : WI_UNARY_RESULT (T2) ymod = umod_trunc (y, width);
3729 51978 : WI_UNARY_RESULT (T1) left = wi::lshift (x, ymod);
3730 51978 : WI_UNARY_RESULT (T1) right
3731 103956 : = wi::lrshift (width != precision ? wi::zext (x, width) : x,
3732 51978 : wi::sub (width, ymod));
3733 51978 : if (width != precision)
3734 80444 : return wi::zext (left, width) | right;
3735 11756 : return left | right;
3736 51978 : }
3737 :
3738 : /* Return the result of rotating the low WIDTH bits of X right by Y
3739 : bits and zero-extending the result. Use a full-width rotate if
3740 : WIDTH is zero. */
3741 : template <typename T1, typename T2>
3742 : WI_UNARY_RESULT (T1)
3743 92135 : wi::rrotate (const T1 &x, const T2 &y, unsigned int width)
3744 : {
3745 92135 : unsigned int precision = get_binary_precision (x, x);
3746 92135 : if (width == 0)
3747 24509 : width = precision;
3748 92135 : WI_UNARY_RESULT (T2) ymod = umod_trunc (y, width);
3749 92135 : WI_UNARY_RESULT (T1) right
3750 92135 : = wi::lrshift (width != precision ? wi::zext (x, width) : x, ymod);
3751 92135 : WI_UNARY_RESULT (T1) left = wi::lshift (x, wi::sub (width, ymod));
3752 92135 : if (width != precision)
3753 135252 : return wi::zext (left, width) | right;
3754 24509 : return left | right;
3755 92135 : }
3756 :
3757 : /* Return 0 if the number of 1s in X is even and 1 if the number of 1s
3758 : is odd. */
3759 : inline int
3760 545 : wi::parity (const wide_int_ref &x)
3761 : {
3762 545 : return popcount (x) & 1;
3763 : }
3764 :
3765 : /* Extract WIDTH bits from X, starting at BITPOS. */
3766 : template <typename T>
3767 : inline unsigned HOST_WIDE_INT
3768 242164800 : wi::extract_uhwi (const T &x, unsigned int bitpos, unsigned int width)
3769 : {
3770 242164800 : unsigned precision = get_precision (x);
3771 242164800 : if (precision < bitpos + width)
3772 : precision = bitpos + width;
3773 242164800 : WIDE_INT_REF_FOR (T) xi (x, precision);
3774 :
3775 : /* Handle this rare case after the above, so that we assert about
3776 : bogus BITPOS values. */
3777 242164800 : if (width == 0)
3778 : return 0;
3779 :
3780 242119987 : unsigned int start = bitpos / HOST_BITS_PER_WIDE_INT;
3781 242119987 : unsigned int shift = bitpos % HOST_BITS_PER_WIDE_INT;
3782 242119987 : unsigned HOST_WIDE_INT res = xi.elt (start);
3783 242119987 : res >>= shift;
3784 242119987 : if (shift + width > HOST_BITS_PER_WIDE_INT)
3785 : {
3786 337418 : unsigned HOST_WIDE_INT upper = xi.elt (start + 1);
3787 337418 : res |= upper << (-shift % HOST_BITS_PER_WIDE_INT);
3788 : }
3789 242119987 : return zext_hwi (res, width);
3790 : }
3791 :
3792 : /* Return the minimum precision needed to store X with sign SGN. */
3793 : template <typename T>
3794 : inline unsigned int
3795 56043600 : wi::min_precision (const T &x, signop sgn)
3796 : {
3797 56043600 : if (sgn == SIGNED)
3798 37734162 : return get_precision (x) - clrsb (x);
3799 : else
3800 18309438 : return get_precision (x) - clz (x);
3801 : }
3802 :
3803 : #define SIGNED_BINARY_PREDICATE(OP, F) \
3804 : template <typename T1, typename T2> \
3805 : inline WI_SIGNED_BINARY_PREDICATE_RESULT (T1, T2) \
3806 : OP (const T1 &x, const T2 &y) \
3807 : { \
3808 : return wi::F (x, y); \
3809 : }
3810 :
3811 2720380345 : SIGNED_BINARY_PREDICATE (operator <, lts_p)
3812 1105710181 : SIGNED_BINARY_PREDICATE (operator <=, les_p)
3813 284223394 : SIGNED_BINARY_PREDICATE (operator >, gts_p)
3814 157681805 : SIGNED_BINARY_PREDICATE (operator >=, ges_p)
3815 :
3816 : #undef SIGNED_BINARY_PREDICATE
3817 :
3818 : #define UNARY_OPERATOR(OP, F) \
3819 : template<typename T> \
3820 : WI_UNARY_RESULT (generic_wide_int<T>) \
3821 : OP (const generic_wide_int<T> &x) \
3822 : { \
3823 : return wi::F (x); \
3824 : }
3825 :
3826 : #define BINARY_PREDICATE(OP, F) \
3827 : template<typename T1, typename T2> \
3828 : WI_BINARY_PREDICATE_RESULT (T1, T2) \
3829 : OP (const T1 &x, const T2 &y) \
3830 : { \
3831 : return wi::F (x, y); \
3832 : }
3833 :
3834 : #define BINARY_OPERATOR(OP, F) \
3835 : template<typename T1, typename T2> \
3836 : WI_BINARY_OPERATOR_RESULT (T1, T2) \
3837 : OP (const T1 &x, const T2 &y) \
3838 : { \
3839 : return wi::F (x, y); \
3840 : }
3841 :
3842 : #define SHIFT_OPERATOR(OP, F) \
3843 : template<typename T1, typename T2> \
3844 : WI_BINARY_OPERATOR_RESULT (T1, T1) \
3845 : OP (const T1 &x, const T2 &y) \
3846 : { \
3847 : return wi::F (x, y); \
3848 : }
3849 :
3850 2180436316 : UNARY_OPERATOR (operator ~, bit_not)
3851 53352932 : UNARY_OPERATOR (operator -, neg)
3852 41549905915 : BINARY_PREDICATE (operator ==, eq_p)
3853 9017676587 : BINARY_PREDICATE (operator !=, ne_p)
3854 4541896780 : BINARY_OPERATOR (operator &, bit_and)
3855 2975234524 : BINARY_OPERATOR (operator |, bit_or)
3856 2501614912 : BINARY_OPERATOR (operator ^, bit_xor)
3857 1952545384 : BINARY_OPERATOR (operator +, add)
3858 1444694436 : BINARY_OPERATOR (operator -, sub)
3859 372081588 : BINARY_OPERATOR (operator *, mul)
3860 3032431868 : SHIFT_OPERATOR (operator <<, lshift)
3861 :
3862 : #undef UNARY_OPERATOR
3863 : #undef BINARY_PREDICATE
3864 : #undef BINARY_OPERATOR
3865 : #undef SHIFT_OPERATOR
3866 :
3867 : template <typename T1, typename T2>
3868 : inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3869 152886672 : operator >> (const T1 &x, const T2 &y)
3870 : {
3871 152886672 : return wi::arshift (x, y);
3872 : }
3873 :
3874 : template <typename T1, typename T2>
3875 : inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3876 14509173 : operator / (const T1 &x, const T2 &y)
3877 : {
3878 14509173 : return wi::sdiv_trunc (x, y);
3879 : }
3880 :
3881 : template <typename T1, typename T2>
3882 : inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3883 17771466 : operator % (const T1 &x, const T2 &y)
3884 : {
3885 17771466 : return wi::smod_trunc (x, y);
3886 : }
3887 :
3888 : void gt_ggc_mx (generic_wide_int <wide_int_storage> *) = delete;
3889 : void gt_pch_nx (generic_wide_int <wide_int_storage> *) = delete;
3890 : void gt_pch_nx (generic_wide_int <wide_int_storage> *,
3891 : gt_pointer_operator, void *) = delete;
3892 :
3893 : template<int N>
3894 : void
3895 : gt_ggc_mx (generic_wide_int <fixed_wide_int_storage <N> > *)
3896 : {
3897 : }
3898 :
3899 : template<int N>
3900 : void
3901 : gt_pch_nx (generic_wide_int <fixed_wide_int_storage <N> > *)
3902 : {
3903 : }
3904 :
3905 : template<int N>
3906 : void
3907 : gt_pch_nx (generic_wide_int <fixed_wide_int_storage <N> > *,
3908 : gt_pointer_operator, void *)
3909 : {
3910 : }
3911 :
3912 : template<int N>
3913 : void gt_ggc_mx (generic_wide_int <widest_int_storage <N> > *) = delete;
3914 :
3915 : template<int N>
3916 : void gt_pch_nx (generic_wide_int <widest_int_storage <N> > *) = delete;
3917 :
3918 : template<int N>
3919 : void gt_pch_nx (generic_wide_int <widest_int_storage <N> > *,
3920 : gt_pointer_operator, void *) = delete;
3921 :
3922 : template<int N>
3923 : void
3924 : gt_ggc_mx (trailing_wide_ints <N> *)
3925 : {
3926 : }
3927 :
3928 : template<int N>
3929 : void
3930 : gt_pch_nx (trailing_wide_ints <N> *)
3931 : {
3932 : }
3933 :
3934 : template<int N>
3935 : void
3936 : gt_pch_nx (trailing_wide_ints <N> *, gt_pointer_operator, void *)
3937 : {
3938 : }
3939 :
3940 : namespace wi
3941 : {
3942 : /* Used for overloaded functions in which the only other acceptable
3943 : scalar type is a pointer. It stops a plain 0 from being treated
3944 : as a null pointer. */
3945 : struct never_used1 {};
3946 : struct never_used2 {};
3947 :
3948 : wide_int min_value (unsigned int, signop);
3949 : wide_int min_value (never_used1 *);
3950 : wide_int min_value (never_used2 *);
3951 : wide_int max_value (unsigned int, signop);
3952 : wide_int max_value (never_used1 *);
3953 : wide_int max_value (never_used2 *);
3954 :
3955 : /* FIXME: this is target dependent, so should be elsewhere.
3956 : It also seems to assume that CHAR_BIT == BITS_PER_UNIT. */
3957 : wide_int from_buffer (const unsigned char *, unsigned int);
3958 :
3959 : #ifndef GENERATOR_FILE
3960 : void to_mpz (const wide_int_ref &, mpz_t, signop);
3961 : #endif
3962 :
3963 : wide_int mask (unsigned int, bool, unsigned int);
3964 : wide_int shifted_mask (unsigned int, unsigned int, bool, unsigned int);
3965 : wide_int set_bit_in_zero (unsigned int, unsigned int);
3966 : wide_int insert (const wide_int &x, const wide_int &y, unsigned int,
3967 : unsigned int);
3968 : wide_int round_down_for_mask (const wide_int &, const wide_int &);
3969 : wide_int round_up_for_mask (const wide_int &, const wide_int &);
3970 :
3971 : wide_int mod_inv (const wide_int &a, const wide_int &b);
3972 :
3973 : template <typename T>
3974 : T mask (unsigned int, bool);
3975 :
3976 : template <typename T>
3977 : T shifted_mask (unsigned int, unsigned int, bool);
3978 :
3979 : template <typename T>
3980 : T set_bit_in_zero (unsigned int);
3981 :
3982 : unsigned int mask (HOST_WIDE_INT *, unsigned int, bool, unsigned int);
3983 : unsigned int shifted_mask (HOST_WIDE_INT *, unsigned int, unsigned int,
3984 : bool, unsigned int);
3985 : unsigned int from_array (HOST_WIDE_INT *, const HOST_WIDE_INT *,
3986 : unsigned int, unsigned int, bool);
3987 : }
3988 :
3989 : /* Return a PRECISION-bit integer in which the low WIDTH bits are set
3990 : and the other bits are clear, or the inverse if NEGATE_P. */
3991 : inline wide_int
3992 2392779186 : wi::mask (unsigned int width, bool negate_p, unsigned int precision)
3993 : {
3994 2392779186 : wide_int result = wide_int::create (precision);
3995 4785558372 : result.set_len (mask (result.write_val (0), width, negate_p, precision));
3996 2392779186 : return result;
3997 : }
3998 :
3999 : /* Return a PRECISION-bit integer in which the low START bits are clear,
4000 : the next WIDTH bits are set, and the other bits are clear,
4001 : or the inverse if NEGATE_P. */
4002 : inline wide_int
4003 2608556243 : wi::shifted_mask (unsigned int start, unsigned int width, bool negate_p,
4004 : unsigned int precision)
4005 : {
4006 2608556243 : wide_int result = wide_int::create (precision);
4007 5217112486 : result.set_len (shifted_mask (result.write_val (0), start, width, negate_p,
4008 : precision));
4009 2608556243 : return result;
4010 : }
4011 :
4012 : /* Return a PRECISION-bit integer in which bit BIT is set and all the
4013 : others are clear. */
4014 : inline wide_int
4015 2606967130 : wi::set_bit_in_zero (unsigned int bit, unsigned int precision)
4016 : {
4017 2606967058 : return shifted_mask (bit, 1, false, precision);
4018 : }
4019 :
4020 : /* Return an integer of type T in which the low WIDTH bits are set
4021 : and the other bits are clear, or the inverse if NEGATE_P. */
4022 : template <typename T>
4023 : inline T
4024 22344935 : wi::mask (unsigned int width, bool negate_p)
4025 : {
4026 : STATIC_ASSERT (wi::int_traits<T>::precision);
4027 22344935 : T result;
4028 22344935 : result.set_len (mask (result.write_val (width / HOST_BITS_PER_WIDE_INT + 1),
4029 : width, negate_p, wi::int_traits <T>::precision));
4030 22344935 : return result;
4031 : }
4032 :
4033 : /* Return an integer of type T in which the low START bits are clear,
4034 : the next WIDTH bits are set, and the other bits are clear, or the
4035 : inverse if NEGATE_P. */
4036 : template <typename T>
4037 : inline T
4038 438807 : wi::shifted_mask (unsigned int start, unsigned int width, bool negate_p)
4039 : {
4040 : STATIC_ASSERT (wi::int_traits<T>::precision);
4041 438807 : T result;
4042 438807 : unsigned int prec = wi::int_traits <T>::precision;
4043 438807 : unsigned int est_len
4044 : = result.needs_write_val_arg
4045 351643 : ? ((start + (width > prec - start ? prec - start : width))
4046 351643 : / HOST_BITS_PER_WIDE_INT + 1) : 0;
4047 522971 : result.set_len (shifted_mask (result.write_val (est_len), start, width,
4048 : negate_p, prec));
4049 351643 : return result;
4050 : }
4051 :
4052 : /* Return an integer of type T in which bit BIT is set and all the
4053 : others are clear. */
4054 : template <typename T>
4055 : inline T
4056 84164 : wi::set_bit_in_zero (unsigned int bit)
4057 : {
4058 84164 : return shifted_mask <T> (bit, 1, false);
4059 : }
4060 :
4061 : /* Accumulate a set of overflows into OVERFLOW. */
4062 :
4063 : inline void
4064 : wi::accumulate_overflow (wi::overflow_type &overflow,
4065 : wi::overflow_type suboverflow)
4066 : {
4067 : if (!suboverflow)
4068 : return;
4069 : if (!overflow)
4070 : overflow = suboverflow;
4071 : else if (overflow != suboverflow)
4072 : overflow = wi::OVF_UNKNOWN;
4073 : }
4074 :
4075 : #endif /* WIDE_INT_H */
|
