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 targeted 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 preferred 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 >25210*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 >10084*10^7 : wi::storage_ref::get_len () const
733 : {
734 70977485387 : return len;
735 : }
736 :
737 : inline unsigned int
738 78821177428 : wi::storage_ref::get_precision () const
739 : {
740 41890096941 : return precision;
741 : }
742 :
743 : inline const HOST_WIDE_INT *
744 >18382*10^7 : wi::storage_ref::get_val () const
745 : {
746 >17614*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 >19712*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 209541461 : ASSIGNMENT_OPERATOR (operator &=, bit_and)
818 105328794 : ASSIGNMENT_OPERATOR (operator |=, bit_or)
819 68806861 : ASSIGNMENT_OPERATOR (operator ^=, bit_xor)
820 8083487249 : ASSIGNMENT_OPERATOR (operator +=, add)
821 1407423384 : ASSIGNMENT_OPERATOR (operator -=, sub)
822 717264078 : ASSIGNMENT_OPERATOR (operator *=, mul)
823 1370063731 : ASSIGNMENT_OPERATOR (operator <<=, lshift)
824 : SHIFT_ASSIGNMENT_OPERATOR (operator >>=, >>)
825 180073 : INCDEC_OPERATOR (operator ++, 1)
826 40574 : 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 >17457*10^7 : inline generic_wide_int <storage>::generic_wide_int () {}
843 :
844 : template <typename storage>
845 : template <typename T>
846 >16829*10^7 : inline generic_wide_int <storage>::generic_wide_int (const T &x)
847 64647252411 : : storage (x)
848 : {
849 368 : }
850 :
851 : template <typename storage>
852 : template <typename T>
853 >29597*10^7 : inline generic_wide_int <storage>::generic_wide_int (const T &x,
854 : unsigned int precision)
855 >38578*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 175671856 : generic_wide_int <storage>::to_shwi (unsigned int precision) const
864 : {
865 175671856 : if (precision < HOST_BITS_PER_WIDE_INT)
866 30001758 : return sext_hwi (this->get_val ()[0], precision);
867 : else
868 145670098 : 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 28139583065 : generic_wide_int <storage>::to_shwi () const
875 : {
876 : if (is_sign_extended)
877 17531104937 : return this->get_val ()[0];
878 : else
879 109485474 : 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 36185697718 : generic_wide_int <storage>::to_uhwi (unsigned int precision) const
888 : {
889 36176924438 : if (precision < HOST_BITS_PER_WIDE_INT)
890 17744702648 : return zext_hwi (this->get_val ()[0], precision);
891 : else
892 18440743462 : 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 36185697418 : generic_wide_int <storage>::to_uhwi () const
899 : {
900 19375337067 : 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 4345410 : generic_wide_int <storage>::to_short_addr () const
910 : {
911 4345410 : 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 10159195527 : generic_wide_int <storage>::sign_mask () const
918 : {
919 10159195527 : unsigned int len = this->get_len ();
920 10142221286 : gcc_assert (len > 0);
921 :
922 10176169768 : unsigned HOST_WIDE_INT high = this->get_val ()[len - 1];
923 : if (!is_sign_extended)
924 : {
925 1706316335 : unsigned int precision = this->get_precision ();
926 1706316335 : int excess = len * HOST_BITS_PER_WIDE_INT - precision;
927 1706316335 : if (excess > 0)
928 727675291 : high <<= excess;
929 : }
930 10159195527 : 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 8067776430 : generic_wide_int <storage>::slow () const
938 : {
939 8067776430 : 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 48596082831 : generic_wide_int <storage>::ulow () const
956 : {
957 41838171945 : 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 829059298 : generic_wide_int <storage>::uhigh () const
965 : {
966 817202657 : 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 1985082174 : generic_wide_int <storage>::elt (unsigned int i) const
973 : {
974 1985082174 : if (i >= this->get_len ())
975 5498824 : return sign_mask ();
976 : else
977 1979583350 : 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 118126240 : generic_wide_int <storage>::sext_elt (unsigned int i) const
985 : {
986 118126240 : 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 18552555865 : generic_wide_int <storage>::operator = (const T &x)
1001 : {
1002 16936790265 : storage::operator = (x);
1003 82808165 : 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 >13902*10^7 : wi::int_traits < generic_wide_int <storage> >::
1038 : get_precision (const generic_wide_int <storage> &x)
1039 : {
1040 >17244*10^7 : return x.get_precision ();
1041 : }
1042 :
1043 : template <typename storage>
1044 : inline wi::storage_ref
1045 >27349*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 >10826*10^7 : gcc_checking_assert (precision == x.get_precision ());
1050 >44940*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 19331119337 : inline wide_int_ref_storage <SE, HDP>::
1079 : wide_int_ref_storage (const wi::storage_ref &x)
1080 19331119337 : : 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 84856066660 : inline wide_int_ref_storage <SE, HDP>::wide_int_ref_storage (const T &x)
1089 82425178540 : : storage_ref (wi::int_traits <T>::decompose (scratch,
1090 : wi::get_precision (x), x))
1091 : {
1092 1362098872 : }
1093 :
1094 : /* Create a reference to integer X in precision PRECISION. */
1095 : template <bool SE, bool HDP>
1096 : template <typename T>
1097 >29597*10^7 : inline wide_int_ref_storage <SE, HDP>::
1098 : wide_int_ref_storage (const T &x, unsigned int precision)
1099 >17255*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 96838013508 : 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 16279427405 : 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 27886910791 : WIDE_INT_REF_FOR (T) xi (x);
1190 16279427405 : precision = xi.precision;
1191 16279427405 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1192 186619 : u.valp = XNEWVEC (HOST_WIDE_INT, CEIL (precision, HOST_BITS_PER_WIDE_INT));
1193 16279427405 : wi::copy (*this, xi);
1194 16279427405 : }
1195 :
1196 45495809155 : inline wide_int_storage::wide_int_storage (const wide_int_storage &x)
1197 : {
1198 45495809155 : memcpy (this, &x, sizeof (wide_int_storage));
1199 45495809155 : if (UNLIKELY (x.precision > WIDE_INT_MAX_INL_PRECISION))
1200 : {
1201 7077078 : u.valp = XNEWVEC (HOST_WIDE_INT, CEIL (precision, HOST_BITS_PER_WIDE_INT));
1202 7077078 : memcpy (u.valp, x.u.valp, len * sizeof (HOST_WIDE_INT));
1203 : }
1204 45495809155 : }
1205 :
1206 >19321*10^7 : inline wide_int_storage::~wide_int_storage ()
1207 : {
1208 >16064*10^7 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1209 12947579 : XDELETEVEC (u.valp);
1210 : }
1211 :
1212 : inline wide_int_storage&
1213 29538426752 : wide_int_storage::operator = (const wide_int_storage &x)
1214 : {
1215 29538426752 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1216 : {
1217 319836 : if (this == &x)
1218 : return *this;
1219 319836 : XDELETEVEC (u.valp);
1220 : }
1221 29538426752 : memcpy (this, &x, sizeof (wide_int_storage));
1222 29538426752 : if (UNLIKELY (x.precision > WIDE_INT_MAX_INL_PRECISION))
1223 : {
1224 2426143 : u.valp = XNEWVEC (HOST_WIDE_INT, CEIL (x.precision, HOST_BITS_PER_WIDE_INT));
1225 2426143 : 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 15373306448 : 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 30688689000 : WIDE_INT_REF_FOR (T) xi (x);
1238 15373306448 : if (UNLIKELY (precision != xi.precision))
1239 : {
1240 13565282340 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1241 6 : XDELETEVEC (u.valp);
1242 13565282340 : precision = xi.precision;
1243 13565282340 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1244 1396674 : u.valp = XNEWVEC (HOST_WIDE_INT,
1245 : CEIL (precision, HOST_BITS_PER_WIDE_INT));
1246 : }
1247 15373306448 : wi::copy (*this, xi);
1248 15373306448 : return *this;
1249 : }
1250 :
1251 : inline unsigned int
1252 >31298*10^7 : wide_int_storage::get_precision () const
1253 : {
1254 >19893*10^7 : return precision;
1255 : }
1256 :
1257 : inline const HOST_WIDE_INT *
1258 >17195*10^7 : wide_int_storage::get_val () const
1259 : {
1260 >17195*10^7 : return UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION) ? u.valp : u.val;
1261 : }
1262 :
1263 : inline unsigned int
1264 >17312*10^7 : wide_int_storage::get_len () const
1265 : {
1266 >17312*10^7 : return len;
1267 : }
1268 :
1269 : inline HOST_WIDE_INT *
1270 99653250067 : wide_int_storage::write_val (unsigned int)
1271 : {
1272 98843853236 : return UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION) ? u.valp : u.val;
1273 : }
1274 :
1275 : inline void
1276 86762393288 : wide_int_storage::set_len (unsigned int l, bool is_sign_extended)
1277 : {
1278 86762393288 : len = l;
1279 59717334603 : if (!is_sign_extended && len * HOST_BITS_PER_WIDE_INT > precision)
1280 : {
1281 10184307138 : HOST_WIDE_INT &v = write_val (len)[len - 1];
1282 10184307138 : v = sext_hwi (v, precision % HOST_BITS_PER_WIDE_INT);
1283 : }
1284 58523084331 : }
1285 :
1286 : /* Treat X as having signedness SGN and convert it to a PRECISION-bit
1287 : number. */
1288 : inline wide_int
1289 15068249996 : wide_int_storage::from (const wide_int_ref &x, unsigned int precision,
1290 : signop sgn)
1291 : {
1292 30136499992 : wide_int result = wide_int::create (precision);
1293 15068249996 : result.set_len (wi::force_to_size (result.write_val (x.len), x.val, x.len,
1294 15068249996 : x.precision, precision, sgn));
1295 15068249996 : 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 2862520 : wide_int_storage::from_array (const HOST_WIDE_INT *val, unsigned int len,
1303 : unsigned int precision, bool need_canon_p)
1304 : {
1305 5725040 : wide_int result = wide_int::create (precision);
1306 2862520 : result.set_len (wi::from_array (result.write_val (len), val, len, precision,
1307 : need_canon_p));
1308 2862520 : return result;
1309 : }
1310 :
1311 : /* Return an uninitialized wide_int with precision PRECISION. */
1312 : inline wide_int
1313 55109658561 : wide_int_storage::create (unsigned int precision)
1314 : {
1315 55109658561 : wide_int x;
1316 55109658561 : x.precision = precision;
1317 17974473721 : if (UNLIKELY (precision > WIDE_INT_MAX_INL_PRECISION))
1318 3437335 : x.u.valp = XNEWVEC (HOST_WIDE_INT,
1319 : CEIL (precision, HOST_BITS_PER_WIDE_INT));
1320 17974473721 : return x;
1321 : }
1322 :
1323 : template <typename T1, typename T2>
1324 : inline wide_int
1325 33933642566 : 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 156474068 : return wide_int::create (wi::get_precision (y));
1332 : else
1333 67710811064 : return wide_int::create (wi::get_precision (x));
1334 : }
1335 :
1336 : template <typename T1, typename T2>
1337 : inline unsigned int
1338 76233094948 : 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 217235324 : return wi::get_precision (y);
1346 : else
1347 76015859624 : 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 12922399344 : 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 23812367063 : wi::copy (*this, WIDE_INT_REF_FOR (T) (x, N));
1401 12922399344 : }
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 36391345826 : fixed_wide_int_storage <N>::get_val () const
1413 : {
1414 36391345826 : return val;
1415 : }
1416 :
1417 : template <int N>
1418 : inline unsigned int
1419 36391345826 : fixed_wide_int_storage <N>::get_len () const
1420 : {
1421 36391345674 : return len;
1422 : }
1423 :
1424 : template <int N>
1425 : inline HOST_WIDE_INT *
1426 32492133662 : fixed_wide_int_storage <N>::write_val (unsigned int)
1427 : {
1428 12922558388 : return val;
1429 : }
1430 :
1431 : template <int N>
1432 : inline void
1433 32492133658 : fixed_wide_int_storage <N>::set_len (unsigned int l, bool)
1434 : {
1435 31487701692 : len = l;
1436 : /* There are no excess bits in val[len - 1]. */
1437 : STATIC_ASSERT (N % HOST_BITS_PER_WIDE_INT == 0);
1438 : }
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 1519411830 : fixed_wide_int_storage <N>::from (const wide_int_ref &x, signop sgn)
1444 : {
1445 : FIXED_WIDE_INT (N) result;
1446 3008007215 : result.set_len (wi::force_to_size (result.write_val (x.len), x.val, x.len,
1447 1519411830 : x.precision, N, sgn));
1448 1488595385 : 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 18050232945 : wi::int_traits < fixed_wide_int_storage <N> >::
1470 : get_binary_result (const T1 &, const T2 &)
1471 : {
1472 : 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 8155561114 : 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 871016214 : 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 1293057618 : wi::copy (*this, WIDE_INT_REF_FOR (T) (x, N));
1549 871016214 : }
1550 :
1551 : template <int N>
1552 : inline
1553 680467489 : widest_int_storage <N>::widest_int_storage (const widest_int_storage &x)
1554 : {
1555 680467489 : memcpy (this, &x, sizeof (widest_int_storage));
1556 680467489 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1557 : {
1558 131520 : u.valp = XNEWVEC (HOST_WIDE_INT, len);
1559 131520 : memcpy (u.valp, x.u.valp, len * sizeof (HOST_WIDE_INT));
1560 : }
1561 680467489 : }
1562 :
1563 : template <int N>
1564 13707772370 : inline widest_int_storage <N>::~widest_int_storage ()
1565 : {
1566 8875804435 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1567 2278689 : XDELETEVEC (u.valp);
1568 : }
1569 :
1570 : template <int N>
1571 : inline widest_int_storage <N>&
1572 3703215700 : widest_int_storage <N>::operator = (const widest_int_storage &x)
1573 : {
1574 3703215700 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1575 : {
1576 365390 : if (this == &x)
1577 : return *this;
1578 365390 : XDELETEVEC (u.valp);
1579 : }
1580 3703215700 : memcpy (this, &x, sizeof (widest_int_storage));
1581 3703215700 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1582 : {
1583 892272 : u.valp = XNEWVEC (HOST_WIDE_INT, len);
1584 892272 : 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 3052212990 : 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 3052212990 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1598 337 : XDELETEVEC (u.valp);
1599 3052212990 : len = 0;
1600 6082858103 : wi::copy (*this, WIDE_INT_REF_FOR (T) (x, N));
1601 3052212990 : 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 15953093379 : widest_int_storage <N>::get_val () const
1614 : {
1615 15953093379 : return UNLIKELY (len > WIDE_INT_MAX_INL_ELTS) ? u.valp : u.val;
1616 : }
1617 :
1618 : template <int N>
1619 : inline unsigned int
1620 15832868595 : widest_int_storage <N>::get_len () const
1621 : {
1622 15832868595 : return len;
1623 : }
1624 :
1625 : template <int N>
1626 : inline HOST_WIDE_INT *
1627 20341591935 : widest_int_storage <N>::write_val (unsigned int l)
1628 : {
1629 13880328401 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS))
1630 0 : XDELETEVEC (u.valp);
1631 13880328467 : len = l;
1632 13880328401 : if (UNLIKELY (l > WIDE_INT_MAX_INL_ELTS))
1633 : {
1634 2071050 : u.valp = XNEWVEC (HOST_WIDE_INT, l);
1635 2071050 : return u.valp;
1636 : }
1637 13878257351 : else if (CHECKING_P && l < WIDE_INT_MAX_INL_ELTS)
1638 14271926324 : u.val[l] = HOST_WIDE_INT_UC (0xbaaaaaaddeadbeef);
1639 13878257351 : return u.val;
1640 : }
1641 :
1642 : template <int N>
1643 : inline void
1644 9956786536 : widest_int_storage <N>::set_len (unsigned int l, bool)
1645 : {
1646 9956786536 : gcc_checking_assert (l <= len);
1647 9956786536 : if (UNLIKELY (len > WIDE_INT_MAX_INL_ELTS)
1648 2068567 : && l <= WIDE_INT_MAX_INL_ELTS)
1649 : {
1650 450207 : HOST_WIDE_INT *valp = u.valp;
1651 450207 : memcpy (u.val, valp, l * sizeof (u.val[0]));
1652 450207 : XDELETEVEC (valp);
1653 450207 : }
1654 9956336329 : else if (len && len < WIDE_INT_MAX_INL_ELTS)
1655 9954599442 : gcc_checking_assert ((unsigned HOST_WIDE_INT) u.val[len]
1656 : == HOST_WIDE_INT_UC (0xbaaaaaaddeadbeef));
1657 9956786536 : len = l;
1658 : /* There are no excess bits in val[len - 1]. */
1659 : STATIC_ASSERT (N % HOST_BITS_PER_WIDE_INT == 0);
1660 9956786536 : }
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 3272878225 : widest_int_storage <N>::from (const wide_int_ref &x, signop sgn)
1666 : {
1667 3272878225 : WIDEST_INT (N) result;
1668 3272878225 : unsigned int exp_len = x.len;
1669 3272878225 : unsigned int prec = result.get_precision ();
1670 3272878225 : if (sgn == UNSIGNED && prec > x.precision && x.val[x.len - 1] < 0)
1671 588091891 : exp_len = CEIL (x.precision, HOST_BITS_PER_WIDE_INT) + 1;
1672 3272878225 : result.set_len (wi::force_to_size (result.write_val (exp_len), x.val, x.len,
1673 3272878225 : x.precision, prec, sgn));
1674 3272878225 : 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 198263433 : widest_int_storage <N>::from_array (const HOST_WIDE_INT *val,
1683 : unsigned int len,
1684 : bool need_canon_p)
1685 : {
1686 198263433 : WIDEST_INT (N) result;
1687 198263433 : result.set_len (wi::from_array (result.write_val (len), val, len,
1688 : result.get_precision (), need_canon_p));
1689 198263433 : return result;
1690 : }
1691 :
1692 : template <int N>
1693 : template <typename T1, typename T2>
1694 : inline WIDEST_INT (N)
1695 6461263468 : wi::int_traits < widest_int_storage <N> >::
1696 : get_binary_result (const T1 &, const T2 &)
1697 : {
1698 6461263468 : 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 : unsigned int get_precision () const { return m_precision; }
1781 10104324 : 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 5158552506 : inline trailing_wide_int_storage::
1791 : trailing_wide_int_storage (unsigned int precision, unsigned short *len,
1792 : HOST_WIDE_INT *val)
1793 3868628663 : : m_precision (precision), m_len (len), m_val (val)
1794 : {
1795 : }
1796 :
1797 : inline unsigned int
1798 5145733598 : trailing_wide_int_storage::get_len () const
1799 : {
1800 5145733598 : return *m_len;
1801 : }
1802 :
1803 : inline unsigned int
1804 10291467196 : trailing_wide_int_storage::get_precision () const
1805 : {
1806 5145733598 : return m_precision;
1807 : }
1808 :
1809 : inline const HOST_WIDE_INT *
1810 5145733598 : trailing_wide_int_storage::get_val () const
1811 : {
1812 5145733598 : return m_val;
1813 : }
1814 :
1815 : inline HOST_WIDE_INT *
1816 12818908 : trailing_wide_int_storage::write_val (unsigned int)
1817 : {
1818 12818908 : return m_val;
1819 : }
1820 :
1821 : inline void
1822 12818908 : trailing_wide_int_storage::set_len (unsigned int len, bool is_sign_extended)
1823 : {
1824 12818908 : *m_len = len;
1825 12818908 : if (!is_sign_extended && len * HOST_BITS_PER_WIDE_INT > m_precision)
1826 : m_val[len - 1] = sext_hwi (m_val[len - 1],
1827 : m_precision % HOST_BITS_PER_WIDE_INT);
1828 : }
1829 :
1830 : template <typename T>
1831 : inline trailing_wide_int_storage &
1832 12818908 : trailing_wide_int_storage::operator = (const T &x)
1833 : {
1834 12818908 : WIDE_INT_REF_FOR (T) xi (x, m_precision);
1835 12818908 : wi::copy (*this, xi);
1836 12818908 : 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 122230183 : trailing_wide_ints <N>::set_precision (unsigned int precision,
1844 : unsigned int num_elements)
1845 : {
1846 122230183 : gcc_checking_assert (num_elements <= N);
1847 122230183 : m_num_elements = num_elements;
1848 122230183 : m_precision = precision;
1849 122230183 : m_max_len = WIDE_INT_MAX_HWIS (precision);
1850 122230183 : }
1851 :
1852 : /* Return a reference to element INDEX. */
1853 : template <int N>
1854 : inline trailing_wide_int
1855 12818908 : trailing_wide_ints <N>::operator [] (unsigned int index)
1856 : {
1857 12818908 : return trailing_wide_int_storage (m_precision, &m_len[index],
1858 12818908 : &m_val[index * m_max_len]);
1859 : }
1860 :
1861 : template <int N>
1862 : inline typename trailing_wide_ints <N>::const_reference
1863 103870491 : trailing_wide_ints <N>::operator [] (unsigned int index) const
1864 : {
1865 103870491 : return wi::storage_ref (&m_val[index * m_max_len],
1866 56035939 : 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 5474942 : trailing_wide_ints <N>::extra_size (unsigned int precision,
1876 : unsigned int num_elements)
1877 : {
1878 5474942 : unsigned int max_len = WIDE_INT_MAX_HWIS (precision);
1879 5474942 : gcc_checking_assert (num_elements <= N);
1880 5474942 : 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 78831996516 : wi::primitive_int_traits <T, signed_p>::decompose (HOST_WIDE_INT *scratch,
1915 : unsigned int precision, T x)
1916 : {
1917 78831996516 : scratch[0] = x;
1918 146158230 : if (signed_p || scratch[0] >= 0 || precision <= HOST_BITS_PER_WIDE_INT)
1919 49808428328 : return wi::storage_ref (scratch, 1, precision);
1920 2632824 : scratch[1] = 0;
1921 2632824 : 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 : template <>
1952 : struct int_traits <long long>
1953 : : public primitive_int_traits <long long, true> {};
1954 :
1955 : template <>
1956 : struct int_traits <unsigned long long>
1957 : : public primitive_int_traits <unsigned long long, false> {};
1958 : }
1959 :
1960 : namespace wi
1961 : {
1962 : /* Stores HWI-sized integer VAL, treating it as having signedness SGN
1963 : and precision PRECISION. */
1964 : class hwi_with_prec
1965 : {
1966 : public:
1967 : hwi_with_prec () {}
1968 : hwi_with_prec (HOST_WIDE_INT, unsigned int, signop);
1969 : HOST_WIDE_INT val;
1970 : unsigned int precision;
1971 : signop sgn;
1972 : };
1973 :
1974 : hwi_with_prec shwi (HOST_WIDE_INT, unsigned int);
1975 : hwi_with_prec uhwi (unsigned HOST_WIDE_INT, unsigned int);
1976 :
1977 : hwi_with_prec minus_one (unsigned int);
1978 : hwi_with_prec zero (unsigned int);
1979 : hwi_with_prec one (unsigned int);
1980 : hwi_with_prec two (unsigned int);
1981 : }
1982 :
1983 29455251848 : inline wi::hwi_with_prec::hwi_with_prec (HOST_WIDE_INT v, unsigned int p,
1984 : signop s)
1985 : : precision (p), sgn (s)
1986 : {
1987 29455251848 : if (precision < HOST_BITS_PER_WIDE_INT)
1988 13949755699 : val = sext_hwi (v, precision);
1989 : else
1990 : val = v;
1991 : }
1992 :
1993 : /* Return a signed integer that has value VAL and precision PRECISION. */
1994 : inline wi::hwi_with_prec
1995 24948660938 : wi::shwi (HOST_WIDE_INT val, unsigned int precision)
1996 : {
1997 24948660938 : return hwi_with_prec (val, precision, SIGNED);
1998 : }
1999 :
2000 : /* Return an unsigned integer that has value VAL and precision PRECISION. */
2001 : inline wi::hwi_with_prec
2002 4506590910 : wi::uhwi (unsigned HOST_WIDE_INT val, unsigned int precision)
2003 : {
2004 4506472383 : return hwi_with_prec (val, precision, UNSIGNED);
2005 : }
2006 :
2007 : /* Return a wide int of -1 with precision PRECISION. */
2008 : inline wi::hwi_with_prec
2009 4522481849 : wi::minus_one (unsigned int precision)
2010 : {
2011 4522481849 : return wi::shwi (-1, precision);
2012 : }
2013 :
2014 : /* Return a wide int of 0 with precision PRECISION. */
2015 : inline wi::hwi_with_prec
2016 6101457747 : wi::zero (unsigned int precision)
2017 : {
2018 6101457747 : return wi::shwi (0, precision);
2019 : }
2020 :
2021 : /* Return a wide int of 1 with precision PRECISION. */
2022 : inline wi::hwi_with_prec
2023 1616296796 : wi::one (unsigned int precision)
2024 : {
2025 1616296796 : return wi::shwi (1, precision);
2026 : }
2027 :
2028 : /* Return a wide int of 2 with precision PRECISION. */
2029 : inline wi::hwi_with_prec
2030 : wi::two (unsigned int precision)
2031 : {
2032 : return wi::shwi (2, precision);
2033 : }
2034 :
2035 : namespace wi
2036 : {
2037 : /* ints_for<T>::zero (X) returns a zero that, when assigned to a T,
2038 : gives that T the same precision as X. */
2039 : template<typename T, precision_type = int_traits<T>::precision_type>
2040 : struct ints_for
2041 : {
2042 : static int zero (const T &) { return 0; }
2043 : };
2044 :
2045 : template<typename T>
2046 : struct ints_for<T, VAR_PRECISION>
2047 : {
2048 : static hwi_with_prec zero (const T &);
2049 : };
2050 : }
2051 :
2052 : template<typename T>
2053 : inline wi::hwi_with_prec
2054 : wi::ints_for<T, wi::VAR_PRECISION>::zero (const T &x)
2055 : {
2056 : return wi::zero (wi::get_precision (x));
2057 : }
2058 :
2059 : namespace wi
2060 : {
2061 : template <>
2062 : struct int_traits <wi::hwi_with_prec>
2063 : {
2064 : static const enum precision_type precision_type = VAR_PRECISION;
2065 : /* hwi_with_prec has an explicitly-given precision, rather than the
2066 : precision of HOST_WIDE_INT. */
2067 : static const bool host_dependent_precision = false;
2068 : static const bool is_sign_extended = true;
2069 : static const bool needs_write_val_arg = false;
2070 : static unsigned int get_precision (const wi::hwi_with_prec &);
2071 : static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int,
2072 : const wi::hwi_with_prec &);
2073 : };
2074 : }
2075 :
2076 : inline unsigned int
2077 29431662237 : wi::int_traits <wi::hwi_with_prec>::get_precision (const wi::hwi_with_prec &x)
2078 : {
2079 29431662237 : return x.precision;
2080 : }
2081 :
2082 : inline wi::storage_ref
2083 29455255666 : wi::int_traits <wi::hwi_with_prec>::
2084 : decompose (HOST_WIDE_INT *scratch, unsigned int precision,
2085 : const wi::hwi_with_prec &x)
2086 : {
2087 29455255666 : gcc_checking_assert (precision == x.precision);
2088 29455255666 : scratch[0] = x.val;
2089 29455255666 : if (x.sgn == SIGNED || x.val >= 0 || precision <= HOST_BITS_PER_WIDE_INT)
2090 29455199490 : return wi::storage_ref (scratch, 1, precision);
2091 56176 : scratch[1] = 0;
2092 56176 : return wi::storage_ref (scratch, 2, precision);
2093 : }
2094 :
2095 : /* Private functions for handling large cases out of line. They take
2096 : individual length and array parameters because that is cheaper for
2097 : the inline caller than constructing an object on the stack and
2098 : passing a reference to it. (Although many callers use wide_int_refs,
2099 : we generally want those to be removed by SRA.) */
2100 : namespace wi
2101 : {
2102 : bool eq_p_large (const HOST_WIDE_INT *, unsigned int,
2103 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2104 : bool lts_p_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2105 : const HOST_WIDE_INT *, unsigned int);
2106 : bool ltu_p_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2107 : const HOST_WIDE_INT *, unsigned int);
2108 : int cmps_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2109 : const HOST_WIDE_INT *, unsigned int);
2110 : int cmpu_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
2111 : const HOST_WIDE_INT *, unsigned int);
2112 : unsigned int sext_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2113 : unsigned int, unsigned int, unsigned int);
2114 : unsigned int zext_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2115 : unsigned int, unsigned int, unsigned int);
2116 : unsigned int set_bit_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2117 : unsigned int, unsigned int, unsigned int);
2118 : unsigned int bswap_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2119 : unsigned int, unsigned int);
2120 : unsigned int bitreverse_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2121 : unsigned int, unsigned int);
2122 :
2123 : unsigned int lshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2124 : unsigned int, unsigned int, unsigned int);
2125 : unsigned int lrshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2126 : unsigned int, unsigned int, unsigned int,
2127 : unsigned int);
2128 : unsigned int arshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2129 : unsigned int, unsigned int, unsigned int,
2130 : unsigned int);
2131 : unsigned int and_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2132 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2133 : unsigned int and_not_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2134 : unsigned int, const HOST_WIDE_INT *,
2135 : unsigned int, unsigned int);
2136 : unsigned int or_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2137 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2138 : unsigned int or_not_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2139 : unsigned int, const HOST_WIDE_INT *,
2140 : unsigned int, unsigned int);
2141 : unsigned int xor_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2142 : const HOST_WIDE_INT *, unsigned int, unsigned int);
2143 : unsigned int add_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2144 : const HOST_WIDE_INT *, unsigned int, unsigned int,
2145 : signop, overflow_type *);
2146 : unsigned int sub_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
2147 : const HOST_WIDE_INT *, unsigned int, unsigned int,
2148 : signop, overflow_type *);
2149 : unsigned int mul_internal (HOST_WIDE_INT *, const HOST_WIDE_INT *,
2150 : unsigned int, const HOST_WIDE_INT *,
2151 : unsigned int, unsigned int, signop,
2152 : overflow_type *, bool);
2153 : unsigned int divmod_internal (HOST_WIDE_INT *, unsigned int *,
2154 : HOST_WIDE_INT *, const HOST_WIDE_INT *,
2155 : unsigned int, unsigned int,
2156 : const HOST_WIDE_INT *,
2157 : unsigned int, unsigned int,
2158 : signop, overflow_type *);
2159 : }
2160 :
2161 : /* Return the number of bits that integer X can hold. */
2162 : template <typename T>
2163 : inline unsigned int
2164 70084828102 : wi::get_precision (const T &x)
2165 : {
2166 50183905511 : return wi::int_traits <T>::get_precision (x);
2167 : }
2168 :
2169 : /* Return the number of bits that the result of a binary operation can
2170 : hold when the input operands are X and Y. */
2171 : template <typename T1, typename T2>
2172 : inline unsigned int
2173 76233094948 : wi::get_binary_precision (const T1 &x, const T2 &y)
2174 : {
2175 : using res_traits = wi::int_traits <WI_BINARY_RESULT (T1, T2)>;
2176 76233094948 : return res_traits::get_binary_precision (x, y);
2177 : }
2178 :
2179 : /* Copy the contents of Y to X, but keeping X's current precision. */
2180 : template <typename T1, typename T2>
2181 : inline void
2182 51218199259 : wi::copy (T1 &x, const T2 &y)
2183 : {
2184 51218199259 : unsigned int len = y.get_len ();
2185 51218199259 : if (len > 0)
2186 : {
2187 51218199259 : HOST_WIDE_INT *xval = x.write_val (len);
2188 51218199259 : const HOST_WIDE_INT *yval = y.get_val ();
2189 51218199259 : unsigned int i = 0;
2190 : do
2191 51381310363 : xval[i] = yval[i];
2192 51381310363 : while (++i < len);
2193 : }
2194 : /* For widest_int write_val is called with an exact value, not
2195 : upper bound for len, so nothing is needed further. */
2196 : if (!wi::int_traits <T1>::needs_write_val_arg)
2197 47294661664 : x.set_len (len, y.is_sign_extended);
2198 51218199259 : }
2199 :
2200 : /* Return true if X fits in a HOST_WIDE_INT with no loss of precision. */
2201 : template <typename T>
2202 : inline bool
2203 40085737822 : wi::fits_shwi_p (const T &x)
2204 : {
2205 29981563788 : WIDE_INT_REF_FOR (T) xi (x);
2206 15612984517 : return xi.len == 1;
2207 : }
2208 :
2209 : /* Return true if X fits in an unsigned HOST_WIDE_INT with no loss of
2210 : precision. */
2211 : template <typename T>
2212 : inline bool
2213 8336525619 : wi::fits_uhwi_p (const T &x)
2214 : {
2215 8336525619 : WIDE_INT_REF_FOR (T) xi (x);
2216 8336525619 : if (xi.precision <= HOST_BITS_PER_WIDE_INT)
2217 : return true;
2218 8086382669 : if (xi.len == 1)
2219 8067776430 : return xi.slow () >= 0;
2220 18606239 : return xi.len == 2 && xi.uhigh () == 0;
2221 : }
2222 :
2223 : /* Return true if X is negative based on the interpretation of SGN.
2224 : For UNSIGNED, this is always false. */
2225 : template <typename T>
2226 : inline bool
2227 9379847010 : wi::neg_p (const T &x, signop sgn)
2228 : {
2229 9379847010 : WIDE_INT_REF_FOR (T) xi (x);
2230 9379847010 : if (sgn == UNSIGNED)
2231 : return false;
2232 8792587347 : return xi.sign_mask () < 0;
2233 : }
2234 :
2235 : /* Return -1 if the top bit of X is set and 0 if the top bit is clear. */
2236 : template <typename T>
2237 : inline HOST_WIDE_INT
2238 1421 : wi::sign_mask (const T &x)
2239 : {
2240 1421 : WIDE_INT_REF_FOR (T) xi (x);
2241 1421 : return xi.sign_mask ();
2242 : }
2243 :
2244 : /* Return true if X == Y. X and Y must be binary-compatible. */
2245 : template <typename T1, typename T2>
2246 : inline bool
2247 62186012561 : wi::eq_p (const T1 &x, const T2 &y)
2248 : {
2249 62186012561 : unsigned int precision = get_binary_precision (x, y);
2250 62186012561 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2251 62186012561 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2252 : if (xi.is_sign_extended && yi.is_sign_extended)
2253 : {
2254 : /* This case reduces to array equality. */
2255 47056688596 : if (xi.len != yi.len)
2256 : return false;
2257 : unsigned int i = 0;
2258 : do
2259 47025990974 : if (xi.val[i] != yi.val[i])
2260 10005437586 : return false;
2261 37647422972 : while (++i != xi.len);
2262 : return true;
2263 : }
2264 4079958068 : if (LIKELY (yi.len == 1))
2265 : {
2266 : /* XI is only equal to YI if it too has a single HWI. */
2267 15126961606 : if (xi.len != 1)
2268 : return false;
2269 : /* Excess bits in xi.val[0] will be signs or zeros, so comparisons
2270 : with 0 are simple. */
2271 15114410022 : if (STATIC_CONSTANT_P (yi.val[0] == 0))
2272 10861744286 : return xi.val[0] == 0;
2273 : /* Otherwise flush out any excess bits first. */
2274 4252665736 : unsigned HOST_WIDE_INT diff = xi.val[0] ^ yi.val[0];
2275 4252665736 : int excess = HOST_BITS_PER_WIDE_INT - precision;
2276 4252665736 : if (excess > 0)
2277 766639486 : diff <<= excess;
2278 4252665736 : return diff == 0;
2279 : }
2280 2358012 : return eq_p_large (xi.val, xi.len, yi.val, yi.len, precision);
2281 : }
2282 :
2283 : /* Return true if X != Y. X and Y must be binary-compatible. */
2284 : template <typename T1, typename T2>
2285 : inline bool
2286 10105840813 : wi::ne_p (const T1 &x, const T2 &y)
2287 : {
2288 8961785115 : return !eq_p (x, y);
2289 : }
2290 :
2291 : /* Return true if X < Y when both are treated as signed values. */
2292 : template <typename T1, typename T2>
2293 : inline bool
2294 9116591736 : wi::lts_p (const T1 &x, const T2 &y)
2295 : {
2296 9116591736 : unsigned int precision = get_binary_precision (x, y);
2297 9116591736 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2298 9116591736 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2299 : /* We optimize x < y, where y is 64 or fewer bits. */
2300 9116591736 : if (wi::fits_shwi_p (yi))
2301 : {
2302 : /* Make lts_p (x, 0) as efficient as wi::neg_p (x). */
2303 9027389854 : if (STATIC_CONSTANT_P (yi.val[0] == 0))
2304 350996852 : return neg_p (xi);
2305 : /* If x fits directly into a shwi, we can compare directly. */
2306 8676393002 : if (wi::fits_shwi_p (xi))
2307 8496880669 : return xi.to_shwi () < yi.to_shwi ();
2308 : /* If x doesn't fit and is negative, then it must be more
2309 : negative than any value in y, and hence smaller than y. */
2310 179512333 : if (neg_p (xi))
2311 : return true;
2312 : /* If x is positive, then it must be larger than any value in y,
2313 : and hence greater than y. */
2314 : return false;
2315 : }
2316 : /* Optimize the opposite case, if it can be detected at compile time. */
2317 33114807 : if (STATIC_CONSTANT_P (xi.len == 1))
2318 : /* If YI is negative it is lower than the least HWI.
2319 : If YI is positive it is greater than the greatest HWI. */
2320 56087075 : return !neg_p (yi);
2321 33114807 : return lts_p_large (xi.val, xi.len, precision, yi.val, yi.len);
2322 : }
2323 :
2324 : /* Return true if X < Y when both are treated as unsigned values. */
2325 : template <typename T1, typename T2>
2326 : inline bool
2327 9819356144 : wi::ltu_p (const T1 &x, const T2 &y)
2328 : {
2329 9819356144 : unsigned int precision = get_binary_precision (x, y);
2330 9819356144 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2331 9819356144 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2332 : /* Optimize comparisons with constants. */
2333 5947327878 : if (STATIC_CONSTANT_P (yi.len == 1 && yi.val[0] >= 0))
2334 9719770854 : return xi.len == 1 && xi.to_uhwi () < (unsigned HOST_WIDE_INT) yi.val[0];
2335 5972353670 : if (STATIC_CONSTANT_P (xi.len == 1 && xi.val[0] >= 0))
2336 46081388 : return yi.len != 1 || yi.to_uhwi () > (unsigned HOST_WIDE_INT) xi.val[0];
2337 : /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
2338 : for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
2339 : values does not change the result. */
2340 4936422129 : if (LIKELY (xi.len + yi.len == 2))
2341 : {
2342 4884721792 : unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2343 4884721792 : unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2344 4884721792 : return xl < yl;
2345 : }
2346 51700337 : return ltu_p_large (xi.val, xi.len, precision, yi.val, yi.len);
2347 : }
2348 :
2349 : /* Return true if X < Y. Signedness of X and Y is indicated by SGN. */
2350 : template <typename T1, typename T2>
2351 : inline bool
2352 4399442188 : wi::lt_p (const T1 &x, const T2 &y, signop sgn)
2353 : {
2354 4398703283 : if (sgn == SIGNED)
2355 2511937191 : return lts_p (x, y);
2356 : else
2357 1887504997 : return ltu_p (x, y);
2358 : }
2359 :
2360 : /* Return true if X <= Y when both are treated as signed values. */
2361 : template <typename T1, typename T2>
2362 : inline bool
2363 1977469811 : wi::les_p (const T1 &x, const T2 &y)
2364 : {
2365 1930831351 : return !lts_p (y, x);
2366 : }
2367 :
2368 : /* Return true if X <= Y when both are treated as unsigned values. */
2369 : template <typename T1, typename T2>
2370 : inline bool
2371 1153551155 : wi::leu_p (const T1 &x, const T2 &y)
2372 : {
2373 1152388192 : return !ltu_p (y, x);
2374 : }
2375 :
2376 : /* Return true if X <= Y. Signedness of X and Y is indicated by SGN. */
2377 : template <typename T1, typename T2>
2378 : inline bool
2379 1866424155 : wi::le_p (const T1 &x, const T2 &y, signop sgn)
2380 : {
2381 1856647719 : if (sgn == SIGNED)
2382 892215418 : return les_p (x, y);
2383 : else
2384 974208737 : return leu_p (x, y);
2385 : }
2386 :
2387 : /* Return true if X > Y when both are treated as signed values. */
2388 : template <typename T1, typename T2>
2389 : inline bool
2390 886217991 : wi::gts_p (const T1 &x, const T2 &y)
2391 : {
2392 327164113 : return lts_p (y, x);
2393 : }
2394 :
2395 : /* Return true if X > Y when both are treated as unsigned values. */
2396 : template <typename T1, typename T2>
2397 : inline bool
2398 431911930 : wi::gtu_p (const T1 &x, const T2 &y)
2399 : {
2400 255761560 : return ltu_p (y, x);
2401 : }
2402 :
2403 : /* Return true if X > Y. Signedness of X and Y is indicated by SGN. */
2404 : template <typename T1, typename T2>
2405 : inline bool
2406 392555038 : wi::gt_p (const T1 &x, const T2 &y, signop sgn)
2407 : {
2408 650788206 : if (sgn == SIGNED)
2409 325203307 : return gts_p (x, y);
2410 : else
2411 409110888 : return gtu_p (x, y);
2412 : }
2413 :
2414 : /* Return true if X >= Y when both are treated as signed values. */
2415 : template <typename T1, typename T2>
2416 : inline bool
2417 1022110780 : wi::ges_p (const T1 &x, const T2 &y)
2418 : {
2419 926093078 : return !lts_p (x, y);
2420 : }
2421 :
2422 : /* Return true if X >= Y when both are treated as unsigned values. */
2423 : template <typename T1, typename T2>
2424 : inline bool
2425 6213558633 : wi::geu_p (const T1 &x, const T2 &y)
2426 : {
2427 5880804019 : return !ltu_p (x, y);
2428 : }
2429 :
2430 : /* Return true if X >= Y. Signedness of X and Y is indicated by SGN. */
2431 : template <typename T1, typename T2>
2432 : inline bool
2433 1707695541 : wi::ge_p (const T1 &x, const T2 &y, signop sgn)
2434 : {
2435 1705250511 : if (sgn == SIGNED)
2436 767564885 : return ges_p (x, y);
2437 : else
2438 940130657 : return geu_p (x, y);
2439 : }
2440 :
2441 : /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
2442 : as signed values. */
2443 : template <typename T1, typename T2>
2444 : inline int
2445 4263301611 : wi::cmps (const T1 &x, const T2 &y)
2446 : {
2447 4263301611 : unsigned int precision = get_binary_precision (x, y);
2448 4263301611 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2449 4263301611 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2450 4263301611 : if (wi::fits_shwi_p (yi))
2451 : {
2452 : /* Special case for comparisons with 0. */
2453 4259850982 : if (STATIC_CONSTANT_P (yi.val[0] == 0))
2454 0 : return neg_p (xi) ? -1 : !(xi.len == 1 && xi.val[0] == 0);
2455 : /* If x fits into a signed HWI, we can compare directly. */
2456 4259850982 : if (wi::fits_shwi_p (xi))
2457 : {
2458 4258171705 : HOST_WIDE_INT xl = xi.to_shwi ();
2459 4258171705 : HOST_WIDE_INT yl = yi.to_shwi ();
2460 4258171705 : return xl < yl ? -1 : xl > yl;
2461 : }
2462 : /* If x doesn't fit and is negative, then it must be more
2463 : negative than any signed HWI, and hence smaller than y. */
2464 1679277 : if (neg_p (xi))
2465 : return -1;
2466 : /* If x is positive, then it must be larger than any signed HWI,
2467 : and hence greater than y. */
2468 : return 1;
2469 : }
2470 : /* Optimize the opposite case, if it can be detected at compile time. */
2471 3450629 : if (STATIC_CONSTANT_P (xi.len == 1))
2472 : /* If YI is negative it is lower than the least HWI.
2473 : If YI is positive it is greater than the greatest HWI. */
2474 0 : return neg_p (yi) ? 1 : -1;
2475 3450629 : return cmps_large (xi.val, xi.len, precision, yi.val, yi.len);
2476 : }
2477 :
2478 : /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
2479 : as unsigned values. */
2480 : template <typename T1, typename T2>
2481 : inline int
2482 4034107084 : wi::cmpu (const T1 &x, const T2 &y)
2483 : {
2484 4034107084 : unsigned int precision = get_binary_precision (x, y);
2485 4034107084 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2486 4034107084 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2487 : /* Optimize comparisons with constants. */
2488 5279440901 : if (STATIC_CONSTANT_P (yi.len == 1 && yi.val[0] >= 0))
2489 : {
2490 : /* If XI doesn't fit in a HWI then it must be larger than YI. */
2491 0 : if (xi.len != 1)
2492 : return 1;
2493 : /* Otherwise compare directly. */
2494 0 : unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2495 0 : unsigned HOST_WIDE_INT yl = yi.val[0];
2496 0 : return xl < yl ? -1 : xl > yl;
2497 : }
2498 4813432786 : if (STATIC_CONSTANT_P (xi.len == 1 && xi.val[0] >= 0))
2499 : {
2500 : /* If YI doesn't fit in a HWI then it must be larger than XI. */
2501 0 : if (yi.len != 1)
2502 : return -1;
2503 : /* Otherwise compare directly. */
2504 0 : unsigned HOST_WIDE_INT xl = xi.val[0];
2505 0 : unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2506 0 : return xl < yl ? -1 : xl > yl;
2507 : }
2508 : /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
2509 : for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
2510 : values does not change the result. */
2511 4034107084 : if (LIKELY (xi.len + yi.len == 2))
2512 : {
2513 4017110162 : unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2514 4017110162 : unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2515 4017110162 : return xl < yl ? -1 : xl > yl;
2516 : }
2517 16996922 : return cmpu_large (xi.val, xi.len, precision, yi.val, yi.len);
2518 : }
2519 :
2520 : /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Signedness of
2521 : X and Y indicated by SGN. */
2522 : template <typename T1, typename T2>
2523 : inline int
2524 8056329269 : wi::cmp (const T1 &x, const T2 &y, signop sgn)
2525 : {
2526 8056329269 : if (sgn == SIGNED)
2527 4027511637 : return cmps (x, y);
2528 : else
2529 4028817632 : return cmpu (x, y);
2530 : }
2531 :
2532 : /* Return ~x. */
2533 : template <typename T>
2534 : inline WI_UNARY_RESULT (T)
2535 2606146163 : wi::bit_not (const T &x)
2536 : {
2537 2606146163 : WI_UNARY_RESULT_VAR (result, val, T, x);
2538 2606146163 : WIDE_INT_REF_FOR (T) xi (x, get_precision (result));
2539 : if (result.needs_write_val_arg)
2540 1121333 : val = result.write_val (xi.len);
2541 5222642667 : for (unsigned int i = 0; i < xi.len; ++i)
2542 2616496504 : val[i] = ~xi.val[i];
2543 2606146163 : result.set_len (xi.len);
2544 2606146163 : return result;
2545 : }
2546 :
2547 : /* Return -x. */
2548 : template <typename T>
2549 : inline WI_UNARY_RESULT (T)
2550 61850439 : wi::neg (const T &x)
2551 : {
2552 49864793 : return sub (0, x);
2553 : }
2554 :
2555 : /* Return -x. Indicate in *OVERFLOW if performing the negation would
2556 : cause an overflow. */
2557 : template <typename T>
2558 : inline WI_UNARY_RESULT (T)
2559 31182280 : wi::neg (const T &x, overflow_type *overflow)
2560 : {
2561 31182280 : *overflow = only_sign_bit_p (x) ? OVF_OVERFLOW : OVF_NONE;
2562 31182280 : return sub (0, x);
2563 : }
2564 :
2565 : /* Return the absolute value of x. */
2566 : template <typename T>
2567 : inline WI_UNARY_RESULT (T)
2568 120803280 : wi::abs (const T &x)
2569 : {
2570 123822164 : return neg_p (x) ? neg (x) : WI_UNARY_RESULT (T) (x);
2571 : }
2572 :
2573 : /* Return the result of sign-extending the low OFFSET bits of X. */
2574 : template <typename T>
2575 : inline WI_UNARY_RESULT (T)
2576 2697904323 : wi::sext (const T &x, unsigned int offset)
2577 : {
2578 2697904323 : WI_UNARY_RESULT_VAR (result, val, T, x);
2579 2697904323 : unsigned int precision = get_precision (result);
2580 2697904323 : WIDE_INT_REF_FOR (T) xi (x, precision);
2581 :
2582 : if (result.needs_write_val_arg)
2583 1384737062 : val = result.write_val (MAX (xi.len,
2584 : CEIL (offset, HOST_BITS_PER_WIDE_INT)));
2585 2697904323 : if (offset <= HOST_BITS_PER_WIDE_INT)
2586 : {
2587 2692023584 : val[0] = sext_hwi (xi.ulow (), offset);
2588 2692023584 : result.set_len (1, true);
2589 : }
2590 : else
2591 5880739 : result.set_len (sext_large (val, xi.val, xi.len, precision, offset));
2592 2697904323 : return result;
2593 : }
2594 :
2595 : /* Return the result of zero-extending the low OFFSET bits of X. */
2596 : template <typename T>
2597 : inline WI_UNARY_RESULT (T)
2598 3382314521 : wi::zext (const T &x, unsigned int offset)
2599 : {
2600 3382314521 : WI_UNARY_RESULT_VAR (result, val, T, x);
2601 3382314521 : unsigned int precision = get_precision (result);
2602 3382314521 : WIDE_INT_REF_FOR (T) xi (x, precision);
2603 :
2604 : /* This is not just an optimization, it is actually required to
2605 : maintain canonization. */
2606 3382314521 : if (offset >= precision)
2607 : {
2608 2375731412 : wi::copy (result, xi);
2609 2375731412 : return result;
2610 : }
2611 :
2612 : if (result.needs_write_val_arg)
2613 531531960 : val = result.write_val (MAX (xi.len,
2614 : offset / HOST_BITS_PER_WIDE_INT + 1));
2615 : /* In these cases we know that at least the top bit will be clear,
2616 : so no sign extension is necessary. */
2617 1006583109 : if (offset < HOST_BITS_PER_WIDE_INT)
2618 : {
2619 215409045 : val[0] = zext_hwi (xi.ulow (), offset);
2620 215409045 : result.set_len (1, true);
2621 : }
2622 : else
2623 791174064 : result.set_len (zext_large (val, xi.val, xi.len, precision, offset), true);
2624 : return result;
2625 : }
2626 :
2627 : /* Return the result of extending the low OFFSET bits of X according to
2628 : signedness SGN. */
2629 : template <typename T>
2630 : inline WI_UNARY_RESULT (T)
2631 993383950 : wi::ext (const T &x, unsigned int offset, signop sgn)
2632 : {
2633 993383950 : return sgn == SIGNED ? sext (x, offset) : zext (x, offset);
2634 : }
2635 :
2636 : /* Return an integer that represents X | (1 << bit). */
2637 : template <typename T>
2638 : inline WI_UNARY_RESULT (T)
2639 294462 : wi::set_bit (const T &x, unsigned int bit)
2640 : {
2641 294462 : WI_UNARY_RESULT_VAR (result, val, T, x);
2642 294462 : unsigned int precision = get_precision (result);
2643 294462 : WIDE_INT_REF_FOR (T) xi (x, precision);
2644 : if (result.needs_write_val_arg)
2645 : val = result.write_val (MAX (xi.len,
2646 : bit / HOST_BITS_PER_WIDE_INT + 1));
2647 294462 : if (precision <= HOST_BITS_PER_WIDE_INT)
2648 : {
2649 294374 : val[0] = xi.ulow () | (HOST_WIDE_INT_1U << bit);
2650 294374 : result.set_len (1);
2651 : }
2652 : else
2653 88 : result.set_len (set_bit_large (val, xi.val, xi.len, precision, bit));
2654 294462 : return result;
2655 : }
2656 :
2657 : /* Byte swap the integer X.
2658 : ??? This always swaps 8-bit octets, regardless of BITS_PER_UNIT.
2659 : This function requires X's precision to be a multiple of 8 bits,
2660 : so care needs to be taken for targets where BITS_PER_UNIT != 8. */
2661 : template <typename T>
2662 : inline WI_UNARY_RESULT (T)
2663 7595 : wi::bswap (const T &x)
2664 : {
2665 7595 : WI_UNARY_RESULT_VAR (result, val, T, x);
2666 7595 : unsigned int precision = get_precision (result);
2667 7595 : WIDE_INT_REF_FOR (T) xi (x, precision);
2668 : static_assert (!result.needs_write_val_arg,
2669 : "bswap on widest_int makes no sense");
2670 7595 : result.set_len (bswap_large (val, xi.val, xi.len, precision));
2671 7595 : return result;
2672 : }
2673 :
2674 : /* Bitreverse the integer X. */
2675 : template <typename T>
2676 : inline WI_UNARY_RESULT (T)
2677 213 : wi::bitreverse (const T &x)
2678 : {
2679 213 : WI_UNARY_RESULT_VAR (result, val, T, x);
2680 213 : unsigned int precision = get_precision (result);
2681 213 : WIDE_INT_REF_FOR (T) xi (x, precision);
2682 : static_assert (!result.needs_write_val_arg,
2683 : "bitreverse on widest_int makes no sense");
2684 213 : result.set_len (bitreverse_large (val, xi.val, xi.len, precision));
2685 213 : return result;
2686 : }
2687 :
2688 : /* Return the minimum of X and Y, treating them both as having
2689 : signedness SGN. */
2690 : template <typename T1, typename T2>
2691 : inline WI_BINARY_RESULT (T1, T2)
2692 118703367 : wi::min (const T1 &x, const T2 &y, signop sgn)
2693 : {
2694 118703367 : WI_BINARY_RESULT_VAR (result, val ATTRIBUTE_UNUSED, T1, x, T2, y);
2695 118703367 : unsigned int precision = get_precision (result);
2696 118703367 : if (wi::le_p (x, y, sgn))
2697 115039098 : wi::copy (result, WIDE_INT_REF_FOR (T1) (x, precision));
2698 : else
2699 3664269 : wi::copy (result, WIDE_INT_REF_FOR (T2) (y, precision));
2700 118703367 : return result;
2701 : }
2702 :
2703 : /* Return the minimum of X and Y, treating both as signed values. */
2704 : template <typename T1, typename T2>
2705 : inline WI_BINARY_RESULT (T1, T2)
2706 201811 : wi::smin (const T1 &x, const T2 &y)
2707 : {
2708 201811 : return wi::min (x, y, SIGNED);
2709 : }
2710 :
2711 : /* Return the minimum of X and Y, treating both as unsigned values. */
2712 : template <typename T1, typename T2>
2713 : inline WI_BINARY_RESULT (T1, T2)
2714 15840 : wi::umin (const T1 &x, const T2 &y)
2715 : {
2716 15840 : return wi::min (x, y, UNSIGNED);
2717 : }
2718 :
2719 : /* Return the maximum of X and Y, treating them both as having
2720 : signedness SGN. */
2721 : template <typename T1, typename T2>
2722 : inline WI_BINARY_RESULT (T1, T2)
2723 212583171 : wi::max (const T1 &x, const T2 &y, signop sgn)
2724 : {
2725 212583171 : WI_BINARY_RESULT_VAR (result, val ATTRIBUTE_UNUSED, T1, x, T2, y);
2726 212583171 : unsigned int precision = get_precision (result);
2727 212583171 : if (wi::ge_p (x, y, sgn))
2728 152190295 : wi::copy (result, WIDE_INT_REF_FOR (T1) (x, precision));
2729 : else
2730 60392876 : wi::copy (result, WIDE_INT_REF_FOR (T2) (y, precision));
2731 212583171 : return result;
2732 : }
2733 :
2734 : /* Return the maximum of X and Y, treating both as signed values. */
2735 : template <typename T1, typename T2>
2736 : inline WI_BINARY_RESULT (T1, T2)
2737 1483271 : wi::smax (const T1 &x, const T2 &y)
2738 : {
2739 1470726 : return wi::max (x, y, SIGNED);
2740 : }
2741 :
2742 : /* Return the maximum of X and Y, treating both as unsigned values. */
2743 : template <typename T1, typename T2>
2744 : inline WI_BINARY_RESULT (T1, T2)
2745 118334 : wi::umax (const T1 &x, const T2 &y)
2746 : {
2747 118334 : return wi::max (x, y, UNSIGNED);
2748 : }
2749 :
2750 : /* Return X & Y. */
2751 : template <typename T1, typename T2>
2752 : inline WI_BINARY_RESULT (T1, T2)
2753 18217153275 : wi::bit_and (const T1 &x, const T2 &y)
2754 : {
2755 18217153275 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2756 18217153275 : unsigned int precision = get_precision (result);
2757 18217153275 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2758 18217153275 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2759 18217153275 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2760 : if (result.needs_write_val_arg)
2761 79051313 : val = result.write_val (MAX (xi.len, yi.len));
2762 18217153275 : if (LIKELY (xi.len + yi.len == 2))
2763 : {
2764 18171497127 : val[0] = xi.ulow () & yi.ulow ();
2765 18171497127 : result.set_len (1, is_sign_extended);
2766 : }
2767 : else
2768 45656148 : result.set_len (and_large (val, xi.val, xi.len, yi.val, yi.len,
2769 : precision), is_sign_extended);
2770 18217153275 : return result;
2771 : }
2772 :
2773 : /* Return X & ~Y. */
2774 : template <typename T1, typename T2>
2775 : inline WI_BINARY_RESULT (T1, T2)
2776 1503760254 : wi::bit_and_not (const T1 &x, const T2 &y)
2777 : {
2778 1503760254 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2779 1503760254 : unsigned int precision = get_precision (result);
2780 1503760254 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2781 1503760254 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2782 1503760254 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2783 : if (result.needs_write_val_arg)
2784 869182251 : val = result.write_val (MAX (xi.len, yi.len));
2785 1503760254 : if (LIKELY (xi.len + yi.len == 2))
2786 : {
2787 1401089980 : val[0] = xi.ulow () & ~yi.ulow ();
2788 1401089980 : result.set_len (1, is_sign_extended);
2789 : }
2790 : else
2791 102670274 : result.set_len (and_not_large (val, xi.val, xi.len, yi.val, yi.len,
2792 : precision), is_sign_extended);
2793 1503760254 : return result;
2794 : }
2795 :
2796 : /* Return X | Y. */
2797 : template <typename T1, typename T2>
2798 : inline WI_BINARY_RESULT (T1, T2)
2799 4244937455 : wi::bit_or (const T1 &x, const T2 &y)
2800 : {
2801 4244937455 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2802 4244937455 : unsigned int precision = get_precision (result);
2803 4244937455 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2804 4244937455 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2805 4244937455 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2806 : if (result.needs_write_val_arg)
2807 1403737076 : val = result.write_val (MAX (xi.len, yi.len));
2808 4244937455 : if (LIKELY (xi.len + yi.len == 2))
2809 : {
2810 4037986064 : val[0] = xi.ulow () | yi.ulow ();
2811 4037986064 : result.set_len (1, is_sign_extended);
2812 : }
2813 : else
2814 206951391 : result.set_len (or_large (val, xi.val, xi.len,
2815 : yi.val, yi.len, precision), is_sign_extended);
2816 4244937455 : return result;
2817 : }
2818 :
2819 : /* Return X | ~Y. */
2820 : template <typename T1, typename T2>
2821 : inline WI_BINARY_RESULT (T1, T2)
2822 : wi::bit_or_not (const T1 &x, const T2 &y)
2823 : {
2824 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2825 : unsigned int precision = get_precision (result);
2826 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2827 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2828 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2829 : if (result.needs_write_val_arg)
2830 : val = result.write_val (MAX (xi.len, yi.len));
2831 : if (LIKELY (xi.len + yi.len == 2))
2832 : {
2833 : val[0] = xi.ulow () | ~yi.ulow ();
2834 : result.set_len (1, is_sign_extended);
2835 : }
2836 : else
2837 : result.set_len (or_not_large (val, xi.val, xi.len, yi.val, yi.len,
2838 : precision), is_sign_extended);
2839 : return result;
2840 : }
2841 :
2842 : /* Return X ^ Y. */
2843 : template <typename T1, typename T2>
2844 : inline WI_BINARY_RESULT (T1, T2)
2845 3011217881 : wi::bit_xor (const T1 &x, const T2 &y)
2846 : {
2847 3011217881 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2848 3011217881 : unsigned int precision = get_precision (result);
2849 3011217881 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2850 3011217881 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2851 3011217881 : bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2852 : if (result.needs_write_val_arg)
2853 481820933 : val = result.write_val (MAX (xi.len, yi.len));
2854 3011217881 : if (LIKELY (xi.len + yi.len == 2))
2855 : {
2856 2965102836 : val[0] = xi.ulow () ^ yi.ulow ();
2857 2965102836 : result.set_len (1, is_sign_extended);
2858 : }
2859 : else
2860 46115045 : result.set_len (xor_large (val, xi.val, xi.len,
2861 : yi.val, yi.len, precision), is_sign_extended);
2862 3011217881 : return result;
2863 : }
2864 :
2865 : /* Return X + Y. */
2866 : template <typename T1, typename T2>
2867 : inline WI_BINARY_RESULT (T1, T2)
2868 10716335841 : wi::add (const T1 &x, const T2 &y)
2869 : {
2870 10716335841 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2871 10716335841 : unsigned int precision = get_precision (result);
2872 10716335841 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2873 10716335841 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2874 : if (result.needs_write_val_arg)
2875 841550873 : val = result.write_val (MAX (xi.len, yi.len) + 1);
2876 703810675 : if (precision <= HOST_BITS_PER_WIDE_INT)
2877 : {
2878 699298682 : val[0] = xi.ulow () + yi.ulow ();
2879 699298682 : result.set_len (1);
2880 : }
2881 : /* If the precision is known at compile time to be greater than
2882 : HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2883 : knowing that (a) all bits in those HWIs are significant and
2884 : (b) the result has room for at least two HWIs. This provides
2885 : a fast path for things like offset_int and widest_int.
2886 :
2887 : The STATIC_CONSTANT_P test prevents this path from being
2888 : used for wide_ints. wide_ints with precisions greater than
2889 : HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2890 : point handling them inline. */
2891 : else if (STATIC_CONSTANT_P (precision > HOST_BITS_PER_WIDE_INT)
2892 10017037159 : && LIKELY (xi.len + yi.len == 2))
2893 : {
2894 9937401202 : unsigned HOST_WIDE_INT xl = xi.ulow ();
2895 9937401202 : unsigned HOST_WIDE_INT yl = yi.ulow ();
2896 9937401202 : unsigned HOST_WIDE_INT resultl = xl + yl;
2897 9937401202 : val[0] = resultl;
2898 9937401202 : val[1] = (HOST_WIDE_INT) resultl < 0 ? 0 : -1;
2899 9937401202 : result.set_len (1 + (((resultl ^ xl) & (resultl ^ yl))
2900 9937401202 : >> (HOST_BITS_PER_WIDE_INT - 1)));
2901 9937401202 : }
2902 : else
2903 79635957 : result.set_len (add_large (val, xi.val, xi.len,
2904 : yi.val, yi.len, precision,
2905 : UNSIGNED, 0));
2906 10716335841 : return result;
2907 : }
2908 :
2909 : /* Return X + Y. Treat X and Y as having the signednes given by SGN
2910 : and indicate in *OVERFLOW whether the operation overflowed. */
2911 : template <typename T1, typename T2>
2912 : inline WI_BINARY_RESULT (T1, T2)
2913 699373297 : wi::add (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
2914 : {
2915 699373297 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2916 699373297 : unsigned int precision = get_precision (result);
2917 699373297 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2918 699373297 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2919 : if (result.needs_write_val_arg)
2920 19202169 : val = result.write_val (MAX (xi.len, yi.len) + 1);
2921 680171128 : if (precision <= HOST_BITS_PER_WIDE_INT)
2922 : {
2923 639051765 : unsigned HOST_WIDE_INT xl = xi.ulow ();
2924 639051765 : unsigned HOST_WIDE_INT yl = yi.ulow ();
2925 639051765 : unsigned HOST_WIDE_INT resultl = xl + yl;
2926 639051765 : if (sgn == SIGNED)
2927 : {
2928 227754682 : if ((((resultl ^ xl) & (resultl ^ yl))
2929 227754682 : >> (precision - 1)) & 1)
2930 : {
2931 20827350 : if (xl > resultl)
2932 6733440 : *overflow = OVF_UNDERFLOW;
2933 14093910 : else if (xl < resultl)
2934 14093910 : *overflow = OVF_OVERFLOW;
2935 : else
2936 0 : *overflow = OVF_NONE;
2937 : }
2938 : else
2939 206927332 : *overflow = OVF_NONE;
2940 : }
2941 : else
2942 411297083 : *overflow = ((resultl << (HOST_BITS_PER_WIDE_INT - precision))
2943 411297083 : < (xl << (HOST_BITS_PER_WIDE_INT - precision)))
2944 411297083 : ? OVF_OVERFLOW : OVF_NONE;
2945 639051765 : val[0] = resultl;
2946 639051765 : result.set_len (1);
2947 : }
2948 : else
2949 60321532 : result.set_len (add_large (val, xi.val, xi.len,
2950 : yi.val, yi.len, precision,
2951 : sgn, overflow));
2952 699373297 : return result;
2953 : }
2954 :
2955 : /* Return X - Y. */
2956 : template <typename T1, typename T2>
2957 : inline WI_BINARY_RESULT (T1, T2)
2958 3339452009 : wi::sub (const T1 &x, const T2 &y)
2959 : {
2960 3339452009 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2961 3339452009 : unsigned int precision = get_precision (result);
2962 3339452009 : WIDE_INT_REF_FOR (T1) xi (x, precision);
2963 3339452009 : WIDE_INT_REF_FOR (T2) yi (y, precision);
2964 : if (result.needs_write_val_arg)
2965 502160497 : val = result.write_val (MAX (xi.len, yi.len) + 1);
2966 353417862 : if (precision <= HOST_BITS_PER_WIDE_INT)
2967 : {
2968 350862743 : val[0] = xi.ulow () - yi.ulow ();
2969 350862743 : result.set_len (1);
2970 : }
2971 : /* If the precision is known at compile time to be greater than
2972 : HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2973 : knowing that (a) all bits in those HWIs are significant and
2974 : (b) the result has room for at least two HWIs. This provides
2975 : a fast path for things like offset_int and widest_int.
2976 :
2977 : The STATIC_CONSTANT_P test prevents this path from being
2978 : used for wide_ints. wide_ints with precisions greater than
2979 : HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2980 : point handling them inline. */
2981 : else if (STATIC_CONSTANT_P (precision > HOST_BITS_PER_WIDE_INT)
2982 2988589266 : && LIKELY (xi.len + yi.len == 2))
2983 : {
2984 2914980509 : unsigned HOST_WIDE_INT xl = xi.ulow ();
2985 2914980509 : unsigned HOST_WIDE_INT yl = yi.ulow ();
2986 2914980509 : unsigned HOST_WIDE_INT resultl = xl - yl;
2987 2914980509 : val[0] = resultl;
2988 2914980509 : val[1] = (HOST_WIDE_INT) resultl < 0 ? 0 : -1;
2989 2914980509 : result.set_len (1 + (((resultl ^ xl) & (xl ^ yl))
2990 2914980509 : >> (HOST_BITS_PER_WIDE_INT - 1)));
2991 2914980509 : }
2992 : else
2993 73608757 : result.set_len (sub_large (val, xi.val, xi.len,
2994 : yi.val, yi.len, precision,
2995 : UNSIGNED, 0));
2996 3339452009 : return result;
2997 : }
2998 :
2999 : /* Return X - Y. Treat X and Y as having the signednes given by SGN
3000 : and indicate in *OVERFLOW whether the operation overflowed. */
3001 : template <typename T1, typename T2>
3002 : inline WI_BINARY_RESULT (T1, T2)
3003 330249032 : wi::sub (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3004 : {
3005 330249032 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3006 330249032 : unsigned int precision = get_precision (result);
3007 330249032 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3008 330249032 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3009 : if (result.needs_write_val_arg)
3010 5516 : val = result.write_val (MAX (xi.len, yi.len) + 1);
3011 330243516 : if (precision <= HOST_BITS_PER_WIDE_INT)
3012 : {
3013 328737620 : unsigned HOST_WIDE_INT xl = xi.ulow ();
3014 328737620 : unsigned HOST_WIDE_INT yl = yi.ulow ();
3015 328737620 : unsigned HOST_WIDE_INT resultl = xl - yl;
3016 328737620 : if (sgn == SIGNED)
3017 : {
3018 170154382 : if ((((xl ^ yl) & (resultl ^ xl)) >> (precision - 1)) & 1)
3019 : {
3020 15252231 : if (xl > yl)
3021 8340844 : *overflow = OVF_UNDERFLOW;
3022 6911387 : else if (xl < yl)
3023 6911387 : *overflow = OVF_OVERFLOW;
3024 : else
3025 0 : *overflow = OVF_NONE;
3026 : }
3027 : else
3028 154902151 : *overflow = OVF_NONE;
3029 : }
3030 : else
3031 158583238 : *overflow = ((resultl << (HOST_BITS_PER_WIDE_INT - precision))
3032 158583238 : > (xl << (HOST_BITS_PER_WIDE_INT - precision)))
3033 158583238 : ? OVF_UNDERFLOW : OVF_NONE;
3034 328737620 : val[0] = resultl;
3035 328737620 : result.set_len (1);
3036 : }
3037 : else
3038 1511412 : result.set_len (sub_large (val, xi.val, xi.len,
3039 : yi.val, yi.len, precision,
3040 : sgn, overflow));
3041 330249032 : return result;
3042 : }
3043 :
3044 : /* Return X * Y. */
3045 : template <typename T1, typename T2>
3046 : inline WI_BINARY_RESULT (T1, T2)
3047 1134268977 : wi::mul (const T1 &x, const T2 &y)
3048 : {
3049 1134268977 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3050 1134268977 : unsigned int precision = get_precision (result);
3051 1134268977 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3052 1134268977 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3053 : if (result.needs_write_val_arg)
3054 178306605 : val = result.write_val (xi.len + yi.len + 2);
3055 1488226 : if (precision <= HOST_BITS_PER_WIDE_INT)
3056 : {
3057 1291924 : val[0] = xi.ulow () * yi.ulow ();
3058 1291924 : result.set_len (1);
3059 : }
3060 : else
3061 1132977053 : result.set_len (mul_internal (val, xi.val, xi.len, yi.val, yi.len,
3062 : precision, UNSIGNED, 0, false));
3063 1134268977 : return result;
3064 : }
3065 :
3066 : /* Return X * Y. Treat X and Y as having the signednes given by SGN
3067 : and indicate in *OVERFLOW whether the operation overflowed. */
3068 : template <typename T1, typename T2>
3069 : inline WI_BINARY_RESULT (T1, T2)
3070 481741536 : wi::mul (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3071 : {
3072 481741536 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3073 481741536 : unsigned int precision = get_precision (result);
3074 481741536 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3075 481741536 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3076 : if (result.needs_write_val_arg)
3077 3514361 : val = result.write_val (xi.len + yi.len + 2);
3078 481741536 : result.set_len (mul_internal (val, xi.val, xi.len,
3079 : yi.val, yi.len, precision,
3080 : sgn, overflow, false));
3081 481741536 : return result;
3082 : }
3083 :
3084 : /* Return X * Y, treating both X and Y as signed values. Indicate in
3085 : *OVERFLOW whether the operation overflowed. */
3086 : template <typename T1, typename T2>
3087 : inline WI_BINARY_RESULT (T1, T2)
3088 3952 : wi::smul (const T1 &x, const T2 &y, overflow_type *overflow)
3089 : {
3090 3952 : return mul (x, y, SIGNED, overflow);
3091 : }
3092 :
3093 : /* Return X * Y, treating both X and Y as unsigned values. Indicate in
3094 : *OVERFLOW if the result overflows. */
3095 : template <typename T1, typename T2>
3096 : inline WI_BINARY_RESULT (T1, T2)
3097 3588377 : wi::umul (const T1 &x, const T2 &y, overflow_type *overflow)
3098 : {
3099 3588377 : return mul (x, y, UNSIGNED, overflow);
3100 : }
3101 :
3102 : /* Perform a widening multiplication of X and Y, extending the values
3103 : according to SGN, and return the high part of the result. */
3104 : template <typename T1, typename T2>
3105 : inline WI_BINARY_RESULT (T1, T2)
3106 5786 : wi::mul_high (const T1 &x, const T2 &y, signop sgn)
3107 : {
3108 5786 : WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
3109 5786 : unsigned int precision = get_precision (result);
3110 5786 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3111 5786 : WIDE_INT_REF_FOR (T2) yi (y, precision);
3112 : static_assert (!result.needs_write_val_arg,
3113 : "mul_high on widest_int doesn't make sense");
3114 5786 : result.set_len (mul_internal (val, xi.val, xi.len,
3115 : yi.val, yi.len, precision,
3116 : sgn, 0, true));
3117 5786 : return result;
3118 : }
3119 :
3120 : /* Return X / Y, rounding towards 0. Treat X and Y as having the
3121 : signedness given by SGN. Indicate in *OVERFLOW if the result
3122 : overflows. */
3123 : template <typename T1, typename T2>
3124 : inline WI_BINARY_RESULT (T1, T2)
3125 397672655 : wi::div_trunc (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3126 : {
3127 397672655 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3128 397672655 : unsigned int precision = get_precision (quotient);
3129 397672655 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3130 397672655 : WIDE_INT_REF_FOR (T2) yi (y);
3131 :
3132 : if (quotient.needs_write_val_arg)
3133 29644524 : quotient_val = quotient.write_val ((sgn == UNSIGNED
3134 374438 : && xi.val[xi.len - 1] < 0)
3135 : ? CEIL (precision,
3136 : HOST_BITS_PER_WIDE_INT) + 1
3137 14822262 : : xi.len + 1);
3138 397672655 : quotient.set_len (divmod_internal (quotient_val, 0, 0, xi.val, xi.len,
3139 : precision,
3140 : yi.val, yi.len, yi.precision,
3141 : sgn, overflow));
3142 397672655 : return quotient;
3143 : }
3144 :
3145 : /* Return X / Y, rounding towards 0. Treat X and Y as signed values. */
3146 : template <typename T1, typename T2>
3147 : inline WI_BINARY_RESULT (T1, T2)
3148 16333774 : wi::sdiv_trunc (const T1 &x, const T2 &y)
3149 : {
3150 16228830 : return div_trunc (x, y, SIGNED);
3151 : }
3152 :
3153 : /* Return X / Y, rounding towards 0. Treat X and Y as unsigned values. */
3154 : template <typename T1, typename T2>
3155 : inline WI_BINARY_RESULT (T1, T2)
3156 2454506 : wi::udiv_trunc (const T1 &x, const T2 &y)
3157 : {
3158 2454506 : return div_trunc (x, y, UNSIGNED);
3159 : }
3160 :
3161 : /* Return X / Y, rounding towards -inf. Treat X and Y as having the
3162 : signedness given by SGN. Indicate in *OVERFLOW if the result
3163 : overflows. */
3164 : template <typename T1, typename T2>
3165 : inline WI_BINARY_RESULT (T1, T2)
3166 84360703 : wi::div_floor (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3167 : {
3168 84360716 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3169 84360716 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3170 84360703 : unsigned int precision = get_precision (quotient);
3171 84360703 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3172 84360703 : WIDE_INT_REF_FOR (T2) yi (y);
3173 :
3174 : unsigned int remainder_len;
3175 : if (quotient.needs_write_val_arg)
3176 : {
3177 : unsigned int est_len;
3178 252581 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3179 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3180 : else
3181 252581 : est_len = xi.len + 1;
3182 252581 : quotient_val = quotient.write_val (est_len);
3183 252581 : remainder_val = remainder.write_val (est_len);
3184 : }
3185 84360703 : quotient.set_len (divmod_internal (quotient_val,
3186 : &remainder_len, remainder_val,
3187 : xi.val, xi.len, precision,
3188 : yi.val, yi.len, yi.precision, sgn,
3189 : overflow));
3190 84360703 : remainder.set_len (remainder_len);
3191 84360703 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn) && remainder != 0)
3192 30459 : return quotient - 1;
3193 84330244 : return quotient;
3194 81781004 : }
3195 :
3196 : /* Return X / Y, rounding towards -inf. Treat X and Y as signed values. */
3197 : template <typename T1, typename T2>
3198 : inline WI_BINARY_RESULT (T1, T2)
3199 103860 : wi::sdiv_floor (const T1 &x, const T2 &y)
3200 : {
3201 103860 : return div_floor (x, y, SIGNED);
3202 : }
3203 :
3204 : /* Return X / Y, rounding towards -inf. Treat X and Y as unsigned values. */
3205 : /* ??? Why do we have both this and udiv_trunc. Aren't they the same? */
3206 : template <typename T1, typename T2>
3207 : inline WI_BINARY_RESULT (T1, T2)
3208 2646135 : wi::udiv_floor (const T1 &x, const T2 &y)
3209 : {
3210 2646135 : return div_floor (x, y, UNSIGNED);
3211 : }
3212 :
3213 : /* Return X / Y, rounding towards +inf. Treat X and Y as having the
3214 : signedness given by SGN. Indicate in *OVERFLOW if the result
3215 : overflows. */
3216 : template <typename T1, typename T2>
3217 : inline WI_BINARY_RESULT (T1, T2)
3218 88246067 : wi::div_ceil (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3219 : {
3220 88246067 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3221 88246067 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3222 88246067 : unsigned int precision = get_precision (quotient);
3223 88246067 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3224 88246067 : WIDE_INT_REF_FOR (T2) yi (y);
3225 :
3226 : unsigned int remainder_len;
3227 : if (quotient.needs_write_val_arg)
3228 : {
3229 : unsigned int est_len;
3230 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3231 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3232 : else
3233 : est_len = xi.len + 1;
3234 : quotient_val = quotient.write_val (est_len);
3235 : remainder_val = remainder.write_val (est_len);
3236 : }
3237 88246067 : quotient.set_len (divmod_internal (quotient_val,
3238 : &remainder_len, remainder_val,
3239 : xi.val, xi.len, precision,
3240 : yi.val, yi.len, yi.precision, sgn,
3241 : overflow));
3242 88246067 : remainder.set_len (remainder_len);
3243 88246067 : if (wi::neg_p (x, sgn) == wi::neg_p (y, sgn) && remainder != 0)
3244 1179286 : return quotient + 1;
3245 87066781 : return quotient;
3246 88242384 : }
3247 :
3248 : /* Return X / Y, rounding towards +inf. Treat X and Y as unsigned values. */
3249 : template <typename T1, typename T2>
3250 : inline WI_BINARY_RESULT (T1, T2)
3251 3683 : wi::udiv_ceil (const T1 &x, const T2 &y)
3252 : {
3253 3683 : return div_ceil (x, y, UNSIGNED);
3254 : }
3255 :
3256 : /* Return X / Y, rounding towards nearest with ties away from zero.
3257 : Treat X and Y as having the signedness given by SGN. Indicate
3258 : in *OVERFLOW if the result overflows. */
3259 : template <typename T1, typename T2>
3260 : inline WI_BINARY_RESULT (T1, T2)
3261 288 : wi::div_round (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3262 : {
3263 288 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3264 288 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3265 288 : unsigned int precision = get_precision (quotient);
3266 288 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3267 288 : WIDE_INT_REF_FOR (T2) yi (y);
3268 :
3269 : unsigned int remainder_len;
3270 : if (quotient.needs_write_val_arg)
3271 : {
3272 : unsigned int est_len;
3273 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3274 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3275 : else
3276 : est_len = xi.len + 1;
3277 : quotient_val = quotient.write_val (est_len);
3278 : remainder_val = remainder.write_val (est_len);
3279 : }
3280 288 : quotient.set_len (divmod_internal (quotient_val,
3281 : &remainder_len, remainder_val,
3282 : xi.val, xi.len, precision,
3283 : yi.val, yi.len, yi.precision, sgn,
3284 : overflow));
3285 288 : remainder.set_len (remainder_len);
3286 :
3287 576 : if (remainder != 0)
3288 : {
3289 208 : if (sgn == SIGNED)
3290 : {
3291 112 : WI_BINARY_RESULT (T1, T2) abs_remainder = wi::abs (remainder);
3292 112 : if (wi::geu_p (abs_remainder, wi::sub (wi::abs (y), abs_remainder)))
3293 : {
3294 64 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn))
3295 0 : return quotient - 1;
3296 : else
3297 64 : return quotient + 1;
3298 : }
3299 112 : }
3300 : else
3301 : {
3302 96 : if (wi::geu_p (remainder, wi::sub (y, remainder)))
3303 64 : return quotient + 1;
3304 : }
3305 : }
3306 160 : return quotient;
3307 288 : }
3308 :
3309 : /* Return X / Y, rounding towards 0. Treat X and Y as having the
3310 : signedness given by SGN. Store the remainder in *REMAINDER_PTR. */
3311 : template <typename T1, typename T2>
3312 : inline WI_BINARY_RESULT (T1, T2)
3313 413970 : wi::divmod_trunc (const T1 &x, const T2 &y, signop sgn,
3314 : WI_BINARY_RESULT (T1, T2) *remainder_ptr)
3315 : {
3316 413970 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3317 413970 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3318 413970 : unsigned int precision = get_precision (quotient);
3319 413970 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3320 413970 : WIDE_INT_REF_FOR (T2) yi (y);
3321 :
3322 : unsigned int remainder_len;
3323 : if (quotient.needs_write_val_arg)
3324 : {
3325 : unsigned int est_len;
3326 95357 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3327 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3328 : else
3329 95357 : est_len = xi.len + 1;
3330 95357 : quotient_val = quotient.write_val (est_len);
3331 95357 : remainder_val = remainder.write_val (est_len);
3332 : }
3333 413970 : quotient.set_len (divmod_internal (quotient_val,
3334 : &remainder_len, remainder_val,
3335 : xi.val, xi.len, precision,
3336 : yi.val, yi.len, yi.precision, sgn, 0));
3337 413970 : remainder.set_len (remainder_len);
3338 :
3339 413970 : *remainder_ptr = remainder;
3340 413970 : return quotient;
3341 112211 : }
3342 :
3343 : /* Compute the greatest common divisor of two numbers A and B using
3344 : Euclid's algorithm. */
3345 : template <typename T1, typename T2>
3346 : inline WI_BINARY_RESULT (T1, T2)
3347 3840 : wi::gcd (const T1 &a, const T2 &b, signop sgn)
3348 : {
3349 3840 : T1 x, y, z;
3350 :
3351 3840 : x = wi::abs (a);
3352 3840 : y = wi::abs (b);
3353 :
3354 15836 : while (gt_p (x, 0, sgn))
3355 : {
3356 11996 : z = mod_trunc (y, x, sgn);
3357 11996 : y = x;
3358 11996 : x = z;
3359 : }
3360 :
3361 3840 : return y;
3362 3840 : }
3363 :
3364 : /* Compute X / Y, rounding towards 0, and return the remainder.
3365 : Treat X and Y as having the signedness given by SGN. Indicate
3366 : in *OVERFLOW if the division overflows. */
3367 : template <typename T1, typename T2>
3368 : inline WI_BINARY_RESULT (T1, T2)
3369 32175781 : wi::mod_trunc (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3370 : {
3371 32175781 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3372 32175781 : unsigned int precision = get_precision (remainder);
3373 32175781 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3374 32175781 : WIDE_INT_REF_FOR (T2) yi (y);
3375 :
3376 : unsigned int remainder_len;
3377 : if (remainder.needs_write_val_arg)
3378 33514122 : remainder_val = remainder.write_val ((sgn == UNSIGNED
3379 110256 : && xi.val[xi.len - 1] < 0)
3380 : ? CEIL (precision,
3381 : HOST_BITS_PER_WIDE_INT) + 1
3382 16757061 : : xi.len + 1);
3383 32175781 : divmod_internal (0, &remainder_len, remainder_val,
3384 : xi.val, xi.len, precision,
3385 : yi.val, yi.len, yi.precision, sgn, overflow);
3386 32175781 : remainder.set_len (remainder_len);
3387 :
3388 32175781 : return remainder;
3389 : }
3390 :
3391 : /* Compute X / Y, rounding towards 0, and return the remainder.
3392 : Treat X and Y as signed values. */
3393 : template <typename T1, typename T2>
3394 : inline WI_BINARY_RESULT (T1, T2)
3395 18389865 : wi::smod_trunc (const T1 &x, const T2 &y)
3396 : {
3397 18389865 : return mod_trunc (x, y, SIGNED);
3398 : }
3399 :
3400 : /* Compute X / Y, rounding towards 0, and return the remainder.
3401 : Treat X and Y as unsigned values. */
3402 : template <typename T1, typename T2>
3403 : inline WI_BINARY_RESULT (T1, T2)
3404 6272128 : wi::umod_trunc (const T1 &x, const T2 &y)
3405 : {
3406 6272128 : return mod_trunc (x, y, UNSIGNED);
3407 : }
3408 :
3409 : /* Compute X / Y, rounding towards -inf, and return the remainder.
3410 : Treat X and Y as having the signedness given by SGN. Indicate
3411 : in *OVERFLOW if the division overflows. */
3412 : template <typename T1, typename T2>
3413 : inline WI_BINARY_RESULT (T1, T2)
3414 69561646 : wi::mod_floor (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3415 : {
3416 69561650 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3417 69561650 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3418 69561646 : unsigned int precision = get_precision (quotient);
3419 69561646 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3420 69561646 : WIDE_INT_REF_FOR (T2) yi (y);
3421 :
3422 : unsigned int remainder_len;
3423 : if (quotient.needs_write_val_arg)
3424 : {
3425 : unsigned int est_len;
3426 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3427 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3428 : else
3429 : est_len = xi.len + 1;
3430 : quotient_val = quotient.write_val (est_len);
3431 : remainder_val = remainder.write_val (est_len);
3432 : }
3433 69561646 : quotient.set_len (divmod_internal (quotient_val,
3434 : &remainder_len, remainder_val,
3435 : xi.val, xi.len, precision,
3436 : yi.val, yi.len, yi.precision, sgn,
3437 : overflow));
3438 69561646 : remainder.set_len (remainder_len);
3439 :
3440 69561646 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn) && remainder != 0)
3441 1305 : return remainder + y;
3442 69560341 : return remainder;
3443 69509179 : }
3444 :
3445 : /* Compute X / Y, rounding towards -inf, and return the remainder.
3446 : Treat X and Y as unsigned values. */
3447 : /* ??? Why do we have both this and umod_trunc. Aren't they the same? */
3448 : template <typename T1, typename T2>
3449 : inline WI_BINARY_RESULT (T1, T2)
3450 52467 : wi::umod_floor (const T1 &x, const T2 &y)
3451 : {
3452 52467 : return mod_floor (x, y, UNSIGNED);
3453 : }
3454 :
3455 : /* Compute X / Y, rounding towards +inf, and return the remainder.
3456 : Treat X and Y as having the signedness given by SGN. Indicate
3457 : in *OVERFLOW if the division overflows. */
3458 : template <typename T1, typename T2>
3459 : inline WI_BINARY_RESULT (T1, T2)
3460 178 : wi::mod_ceil (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3461 : {
3462 178 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3463 178 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3464 178 : unsigned int precision = get_precision (quotient);
3465 178 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3466 178 : WIDE_INT_REF_FOR (T2) yi (y);
3467 :
3468 : unsigned int remainder_len;
3469 : if (quotient.needs_write_val_arg)
3470 : {
3471 : unsigned int est_len;
3472 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3473 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3474 : else
3475 : est_len = xi.len + 1;
3476 : quotient_val = quotient.write_val (est_len);
3477 : remainder_val = remainder.write_val (est_len);
3478 : }
3479 178 : quotient.set_len (divmod_internal (quotient_val,
3480 : &remainder_len, remainder_val,
3481 : xi.val, xi.len, precision,
3482 : yi.val, yi.len, yi.precision, sgn,
3483 : overflow));
3484 178 : remainder.set_len (remainder_len);
3485 :
3486 178 : if (wi::neg_p (x, sgn) == wi::neg_p (y, sgn) && remainder != 0)
3487 70 : return remainder - y;
3488 108 : return remainder;
3489 178 : }
3490 :
3491 : /* Compute X / Y, rounding towards nearest with ties away from zero,
3492 : and return the remainder. Treat X and Y as having the signedness
3493 : given by SGN. Indicate in *OVERFLOW if the division overflows. */
3494 : template <typename T1, typename T2>
3495 : inline WI_BINARY_RESULT (T1, T2)
3496 0 : wi::mod_round (const T1 &x, const T2 &y, signop sgn, overflow_type *overflow)
3497 : {
3498 0 : WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
3499 0 : WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
3500 0 : unsigned int precision = get_precision (quotient);
3501 0 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3502 0 : WIDE_INT_REF_FOR (T2) yi (y);
3503 :
3504 : unsigned int remainder_len;
3505 : if (quotient.needs_write_val_arg)
3506 : {
3507 : unsigned int est_len;
3508 : if (sgn == UNSIGNED && xi.val[xi.len - 1] < 0)
3509 : est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
3510 : else
3511 : est_len = xi.len + 1;
3512 : quotient_val = quotient.write_val (est_len);
3513 : remainder_val = remainder.write_val (est_len);
3514 : }
3515 0 : quotient.set_len (divmod_internal (quotient_val,
3516 : &remainder_len, remainder_val,
3517 : xi.val, xi.len, precision,
3518 : yi.val, yi.len, yi.precision, sgn,
3519 : overflow));
3520 0 : remainder.set_len (remainder_len);
3521 :
3522 0 : if (remainder != 0)
3523 : {
3524 0 : if (sgn == SIGNED)
3525 : {
3526 0 : WI_BINARY_RESULT (T1, T2) abs_remainder = wi::abs (remainder);
3527 0 : if (wi::geu_p (abs_remainder, wi::sub (wi::abs (y), abs_remainder)))
3528 : {
3529 0 : if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn))
3530 0 : return remainder + y;
3531 : else
3532 0 : return remainder - y;
3533 : }
3534 0 : }
3535 : else
3536 : {
3537 0 : if (wi::geu_p (remainder, wi::sub (y, remainder)))
3538 0 : return remainder - y;
3539 : }
3540 : }
3541 0 : return remainder;
3542 0 : }
3543 :
3544 : /* Return true if X is a multiple of Y. Treat X and Y as having the
3545 : signedness given by SGN. */
3546 : template <typename T1, typename T2>
3547 : inline bool
3548 4549646 : wi::multiple_of_p (const T1 &x, const T2 &y, signop sgn)
3549 : {
3550 8950020 : return wi::mod_trunc (x, y, sgn) == 0;
3551 : }
3552 :
3553 : /* Return true if X is a multiple of Y, storing X / Y in *RES if so.
3554 : Treat X and Y as having the signedness given by SGN. */
3555 : template <typename T1, typename T2>
3556 : inline bool
3557 394412 : wi::multiple_of_p (const T1 &x, const T2 &y, signop sgn,
3558 : WI_BINARY_RESULT (T1, T2) *res)
3559 : {
3560 394412 : WI_BINARY_RESULT (T1, T2) remainder;
3561 394412 : WI_BINARY_RESULT (T1, T2) quotient
3562 301759 : = divmod_trunc (x, y, sgn, &remainder);
3563 394412 : if (remainder == 0)
3564 : {
3565 355084 : *res = quotient;
3566 355084 : return true;
3567 : }
3568 : return false;
3569 92653 : }
3570 :
3571 : /* Return X << Y. Return 0 if Y is greater than or equal to
3572 : the precision of X. */
3573 : template <typename T1, typename T2>
3574 : inline WI_UNARY_RESULT (T1)
3575 4620100697 : wi::lshift (const T1 &x, const T2 &y)
3576 : {
3577 4620100697 : WI_UNARY_RESULT_VAR (result, val, T1, x);
3578 4620100697 : unsigned int precision = get_precision (result);
3579 4620100697 : WIDE_INT_REF_FOR (T1) xi (x, precision);
3580 4620100697 : WIDE_INT_REF_FOR (T2) yi (y);
3581 : /* Handle the simple cases quickly. */
3582 4620100697 : if (geu_p (yi, precision))
3583 : {
3584 : if (result.needs_write_val_arg)
3585 0 : val = result.write_val (1);
3586 3147675 : val[0] = 0;
3587 3147675 : result.set_len (1);
3588 : }
3589 : else
3590 : {
3591 4616953022 : unsigned int shift = yi.to_uhwi ();
3592 : if (result.needs_write_val_arg)
3593 116587078 : val = result.write_val (xi.len + shift / HOST_BITS_PER_WIDE_INT + 1);
3594 : /* For fixed-precision integers like offset_int and widest_int,
3595 : handle the case where the shift value is constant and the
3596 : result is a single nonnegative HWI (meaning that we don't
3597 : need to worry about val[1]). This is particularly common
3598 : for converting a byte count to a bit count.
3599 :
3600 : For variable-precision integers like wide_int, handle HWI
3601 : and sub-HWI integers inline. */
3602 4557752532 : if (STATIC_CONSTANT_P (xi.precision > HOST_BITS_PER_WIDE_INT)
3603 7107939403 : ? (STATIC_CONSTANT_P (shift < HOST_BITS_PER_WIDE_INT - 1)
3604 2490986381 : && xi.len == 1
3605 6797120229 : && IN_RANGE (xi.val[0], 0, HOST_WIDE_INT_MAX >> shift))
3606 : : precision <= HOST_BITS_PER_WIDE_INT)
3607 : {
3608 2738188568 : val[0] = xi.ulow () << shift;
3609 2738188568 : result.set_len (1);
3610 : }
3611 : else
3612 1878764454 : result.set_len (lshift_large (val, xi.val, xi.len,
3613 : precision, shift));
3614 : }
3615 4620100697 : return result;
3616 : }
3617 :
3618 : /* Return X >> Y, using a logical shift. Return 0 if Y is greater than
3619 : or equal to the precision of X. */
3620 : template <typename T1, typename T2>
3621 : inline WI_UNARY_RESULT (T1)
3622 39570381 : wi::lrshift (const T1 &x, const T2 &y)
3623 : {
3624 39570381 : WI_UNARY_RESULT_VAR (result, val, T1, x);
3625 : /* Do things in the precision of the input rather than the output,
3626 : since the result can be no larger than that. */
3627 39570381 : WIDE_INT_REF_FOR (T1) xi (x);
3628 39570381 : WIDE_INT_REF_FOR (T2) yi (y);
3629 : /* Handle the simple cases quickly. */
3630 39570381 : if (geu_p (yi, xi.precision))
3631 : {
3632 : if (result.needs_write_val_arg)
3633 66 : val = result.write_val (1);
3634 757940 : val[0] = 0;
3635 757940 : result.set_len (1);
3636 : }
3637 : else
3638 : {
3639 38812441 : unsigned int shift = yi.to_uhwi ();
3640 : if (result.needs_write_val_arg)
3641 : {
3642 9981664 : unsigned int est_len = xi.len;
3643 9981664 : if (xi.val[xi.len - 1] < 0 && shift)
3644 : /* Logical right shift of sign-extended value might need a very
3645 : large precision e.g. for widest_int. */
3646 0 : est_len = CEIL (xi.precision - shift, HOST_BITS_PER_WIDE_INT) + 1;
3647 9981664 : val = result.write_val (est_len);
3648 : }
3649 : /* For fixed-precision integers like offset_int and widest_int,
3650 : handle the case where the shift value is constant and the
3651 : shifted value is a single nonnegative HWI (meaning that all
3652 : bits above the HWI are zero). This is particularly common
3653 : for converting a bit count to a byte count.
3654 :
3655 : For variable-precision integers like wide_int, handle HWI
3656 : and sub-HWI integers inline. */
3657 38812441 : if (STATIC_CONSTANT_P (xi.precision > HOST_BITS_PER_WIDE_INT)
3658 38812441 : ? (shift < HOST_BITS_PER_WIDE_INT
3659 10540730 : && xi.len == 1
3660 19268213 : && xi.val[0] >= 0)
3661 : : xi.precision <= HOST_BITS_PER_WIDE_INT)
3662 : {
3663 35122882 : val[0] = xi.to_uhwi () >> shift;
3664 35122882 : result.set_len (1);
3665 : }
3666 : else
3667 3689559 : result.set_len (lrshift_large (val, xi.val, xi.len, xi.precision,
3668 : get_precision (result), shift));
3669 : }
3670 39570381 : return result;
3671 : }
3672 :
3673 : /* Return X >> Y, using an arithmetic shift. Return a sign mask if
3674 : Y is greater than or equal to the precision of X. */
3675 : template <typename T1, typename T2>
3676 : inline WI_UNARY_RESULT (T1)
3677 177290149 : wi::arshift (const T1 &x, const T2 &y)
3678 : {
3679 177290149 : WI_UNARY_RESULT_VAR (result, val, T1, x);
3680 : /* Do things in the precision of the input rather than the output,
3681 : since the result can be no larger than that. */
3682 177290149 : WIDE_INT_REF_FOR (T1) xi (x);
3683 177290149 : WIDE_INT_REF_FOR (T2) yi (y);
3684 : if (result.needs_write_val_arg)
3685 6537059 : val = result.write_val (xi.len);
3686 : /* Handle the simple cases quickly. */
3687 177290149 : if (geu_p (yi, xi.precision))
3688 : {
3689 229 : val[0] = sign_mask (x);
3690 229 : result.set_len (1);
3691 : }
3692 : else
3693 : {
3694 177289920 : unsigned int shift = yi.to_uhwi ();
3695 177289920 : if (xi.precision <= HOST_BITS_PER_WIDE_INT)
3696 : {
3697 8304813 : val[0] = sext_hwi (xi.ulow () >> shift, xi.precision - shift);
3698 8304813 : result.set_len (1, true);
3699 : }
3700 : else
3701 168985107 : result.set_len (arshift_large (val, xi.val, xi.len, xi.precision,
3702 : get_precision (result), shift));
3703 : }
3704 177290149 : return result;
3705 : }
3706 :
3707 : /* Return X >> Y, using an arithmetic shift if SGN is SIGNED and a
3708 : logical shift otherwise. */
3709 : template <typename T1, typename T2>
3710 : inline WI_UNARY_RESULT (T1)
3711 48031577 : wi::rshift (const T1 &x, const T2 &y, signop sgn)
3712 : {
3713 48027618 : if (sgn == UNSIGNED)
3714 33216667 : return lrshift (x, y);
3715 : else
3716 14814910 : return arshift (x, y);
3717 : }
3718 :
3719 : /* Return the result of rotating the low WIDTH bits of X left by Y
3720 : bits and zero-extending the result. Use a full-width rotate if
3721 : WIDTH is zero. */
3722 : template <typename T1, typename T2>
3723 : WI_UNARY_RESULT (T1)
3724 50954 : wi::lrotate (const T1 &x, const T2 &y, unsigned int width)
3725 : {
3726 50954 : unsigned int precision = get_binary_precision (x, x);
3727 50954 : if (width == 0)
3728 10548 : width = precision;
3729 50954 : WI_UNARY_RESULT (T2) ymod = umod_trunc (y, width);
3730 50954 : WI_UNARY_RESULT (T1) left = wi::lshift (x, ymod);
3731 50954 : WI_UNARY_RESULT (T1) right
3732 101908 : = wi::lrshift (width != precision ? wi::zext (x, width) : x,
3733 50954 : wi::sub (width, ymod));
3734 50954 : if (width != precision)
3735 80812 : return wi::zext (left, width) | right;
3736 10548 : return left | right;
3737 50954 : }
3738 :
3739 : /* Return the result of rotating the low WIDTH bits of X right by Y
3740 : bits and zero-extending the result. Use a full-width rotate if
3741 : WIDTH is zero. */
3742 : template <typename T1, typename T2>
3743 : WI_UNARY_RESULT (T1)
3744 92265 : wi::rrotate (const T1 &x, const T2 &y, unsigned int width)
3745 : {
3746 92265 : unsigned int precision = get_binary_precision (x, x);
3747 92265 : if (width == 0)
3748 22501 : width = precision;
3749 92265 : WI_UNARY_RESULT (T2) ymod = umod_trunc (y, width);
3750 92265 : WI_UNARY_RESULT (T1) right
3751 92265 : = wi::lrshift (width != precision ? wi::zext (x, width) : x, ymod);
3752 92265 : WI_UNARY_RESULT (T1) left = wi::lshift (x, wi::sub (width, ymod));
3753 92265 : if (width != precision)
3754 139528 : return wi::zext (left, width) | right;
3755 22501 : return left | right;
3756 92265 : }
3757 :
3758 : /* Return 0 if the number of 1s in X is even and 1 if the number of 1s
3759 : is odd. */
3760 : inline int
3761 690 : wi::parity (const wide_int_ref &x)
3762 : {
3763 690 : return popcount (x) & 1;
3764 : }
3765 :
3766 : /* Extract WIDTH bits from X, starting at BITPOS. */
3767 : template <typename T>
3768 : inline unsigned HOST_WIDE_INT
3769 259767457 : wi::extract_uhwi (const T &x, unsigned int bitpos, unsigned int width)
3770 : {
3771 259767457 : unsigned precision = get_precision (x);
3772 259767457 : if (precision < bitpos + width)
3773 : precision = bitpos + width;
3774 259767457 : WIDE_INT_REF_FOR (T) xi (x, precision);
3775 :
3776 : /* Handle this rare case after the above, so that we assert about
3777 : bogus BITPOS values. */
3778 259767457 : if (width == 0)
3779 : return 0;
3780 :
3781 259716381 : unsigned int start = bitpos / HOST_BITS_PER_WIDE_INT;
3782 259716381 : unsigned int shift = bitpos % HOST_BITS_PER_WIDE_INT;
3783 259716381 : unsigned HOST_WIDE_INT res = xi.elt (start);
3784 259716381 : res >>= shift;
3785 259716381 : if (shift + width > HOST_BITS_PER_WIDE_INT)
3786 : {
3787 376424 : unsigned HOST_WIDE_INT upper = xi.elt (start + 1);
3788 376424 : res |= upper << (-shift % HOST_BITS_PER_WIDE_INT);
3789 : }
3790 259716381 : return zext_hwi (res, width);
3791 : }
3792 :
3793 : /* Return the minimum precision needed to store X with sign SGN. */
3794 : template <typename T>
3795 : inline unsigned int
3796 59366937 : wi::min_precision (const T &x, signop sgn)
3797 : {
3798 59366937 : if (sgn == SIGNED)
3799 39781147 : return get_precision (x) - clrsb (x);
3800 : else
3801 19585790 : return get_precision (x) - clz (x);
3802 : }
3803 :
3804 : #define SIGNED_BINARY_PREDICATE(OP, F) \
3805 : template <typename T1, typename T2> \
3806 : inline WI_SIGNED_BINARY_PREDICATE_RESULT (T1, T2) \
3807 : OP (const T1 &x, const T2 &y) \
3808 : { \
3809 : return wi::F (x, y); \
3810 : }
3811 :
3812 2687449521 : SIGNED_BINARY_PREDICATE (operator <, lts_p)
3813 1084512413 : SIGNED_BINARY_PREDICATE (operator <=, les_p)
3814 388845279 : SIGNED_BINARY_PREDICATE (operator >, gts_p)
3815 248659494 : SIGNED_BINARY_PREDICATE (operator >=, ges_p)
3816 :
3817 : #undef SIGNED_BINARY_PREDICATE
3818 :
3819 : #define UNARY_OPERATOR(OP, F) \
3820 : template<typename T> \
3821 : WI_UNARY_RESULT (generic_wide_int<T>) \
3822 : OP (const generic_wide_int<T> &x) \
3823 : { \
3824 : return wi::F (x); \
3825 : }
3826 :
3827 : #define BINARY_PREDICATE(OP, F) \
3828 : template<typename T1, typename T2> \
3829 : WI_BINARY_PREDICATE_RESULT (T1, T2) \
3830 : OP (const T1 &x, const T2 &y) \
3831 : { \
3832 : return wi::F (x, y); \
3833 : }
3834 :
3835 : #define BINARY_OPERATOR(OP, F) \
3836 : template<typename T1, typename T2> \
3837 : WI_BINARY_OPERATOR_RESULT (T1, T2) \
3838 : OP (const T1 &x, const T2 &y) \
3839 : { \
3840 : return wi::F (x, y); \
3841 : }
3842 :
3843 : #define SHIFT_OPERATOR(OP, F) \
3844 : template<typename T1, typename T2> \
3845 : WI_BINARY_OPERATOR_RESULT (T1, T1) \
3846 : OP (const T1 &x, const T2 &y) \
3847 : { \
3848 : return wi::F (x, y); \
3849 : }
3850 :
3851 2601571855 : UNARY_OPERATOR (operator ~, bit_not)
3852 56606561 : UNARY_OPERATOR (operator -, neg)
3853 49327533100 : BINARY_PREDICATE (operator ==, eq_p)
3854 9500079703 : BINARY_PREDICATE (operator !=, ne_p)
3855 5059306766 : BINARY_OPERATOR (operator &, bit_and)
3856 3519821102 : BINARY_OPERATOR (operator |, bit_or)
3857 2942254142 : BINARY_OPERATOR (operator ^, bit_xor)
3858 2071848201 : BINARY_OPERATOR (operator +, add)
3859 1425393256 : BINARY_OPERATOR (operator -, sub)
3860 376846340 : BINARY_OPERATOR (operator *, mul)
3861 3170683594 : SHIFT_OPERATOR (operator <<, lshift)
3862 :
3863 : #undef UNARY_OPERATOR
3864 : #undef BINARY_PREDICATE
3865 : #undef BINARY_OPERATOR
3866 : #undef SHIFT_OPERATOR
3867 :
3868 : template <typename T1, typename T2>
3869 : inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3870 162363530 : operator >> (const T1 &x, const T2 &y)
3871 : {
3872 162363530 : return wi::arshift (x, y);
3873 : }
3874 :
3875 : template <typename T1, typename T2>
3876 : inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3877 14485907 : operator / (const T1 &x, const T2 &y)
3878 : {
3879 14485907 : return wi::sdiv_trunc (x, y);
3880 : }
3881 :
3882 : template <typename T1, typename T2>
3883 : inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3884 18389438 : operator % (const T1 &x, const T2 &y)
3885 : {
3886 18389438 : return wi::smod_trunc (x, y);
3887 : }
3888 :
3889 : void gt_ggc_mx (generic_wide_int <wide_int_storage> *) = delete;
3890 : void gt_pch_nx (generic_wide_int <wide_int_storage> *) = delete;
3891 : void gt_pch_nx (generic_wide_int <wide_int_storage> *,
3892 : gt_pointer_operator, void *) = delete;
3893 :
3894 : template<int N>
3895 : void
3896 : gt_ggc_mx (generic_wide_int <fixed_wide_int_storage <N> > *)
3897 : {
3898 : }
3899 :
3900 : template<int N>
3901 : void
3902 : gt_pch_nx (generic_wide_int <fixed_wide_int_storage <N> > *)
3903 : {
3904 : }
3905 :
3906 : template<int N>
3907 : void
3908 : gt_pch_nx (generic_wide_int <fixed_wide_int_storage <N> > *,
3909 : gt_pointer_operator, void *)
3910 : {
3911 : }
3912 :
3913 : template<int N>
3914 : void gt_ggc_mx (generic_wide_int <widest_int_storage <N> > *) = delete;
3915 :
3916 : template<int N>
3917 : void gt_pch_nx (generic_wide_int <widest_int_storage <N> > *) = delete;
3918 :
3919 : template<int N>
3920 : void gt_pch_nx (generic_wide_int <widest_int_storage <N> > *,
3921 : gt_pointer_operator, void *) = delete;
3922 :
3923 : template<int N>
3924 : void
3925 : gt_ggc_mx (trailing_wide_ints <N> *)
3926 : {
3927 : }
3928 :
3929 : template<int N>
3930 : void
3931 : gt_pch_nx (trailing_wide_ints <N> *)
3932 : {
3933 : }
3934 :
3935 : template<int N>
3936 : void
3937 : gt_pch_nx (trailing_wide_ints <N> *, gt_pointer_operator, void *)
3938 : {
3939 : }
3940 :
3941 : namespace wi
3942 : {
3943 : /* Used for overloaded functions in which the only other acceptable
3944 : scalar type is a pointer. It stops a plain 0 from being treated
3945 : as a null pointer. */
3946 : struct never_used1 {};
3947 : struct never_used2 {};
3948 :
3949 : wide_int min_value (unsigned int, signop);
3950 : wide_int min_value (never_used1 *);
3951 : wide_int min_value (never_used2 *);
3952 : wide_int max_value (unsigned int, signop);
3953 : wide_int max_value (never_used1 *);
3954 : wide_int max_value (never_used2 *);
3955 :
3956 : /* FIXME: this is target dependent, so should be elsewhere.
3957 : It also seems to assume that CHAR_BIT == BITS_PER_UNIT. */
3958 : wide_int from_buffer (const unsigned char *, unsigned int);
3959 :
3960 : #ifndef GENERATOR_FILE
3961 : void to_mpz (const wide_int_ref &, mpz_t, signop);
3962 : #endif
3963 :
3964 : wide_int mask (unsigned int, bool, unsigned int);
3965 : wide_int shifted_mask (unsigned int, unsigned int, bool, unsigned int);
3966 : wide_int set_bit_in_zero (unsigned int, unsigned int);
3967 : wide_int insert (const wide_int &x, const wide_int &y, unsigned int,
3968 : unsigned int);
3969 : wide_int round_down_for_mask (const wide_int &, const wide_int &);
3970 : wide_int round_up_for_mask (const wide_int &, const wide_int &);
3971 :
3972 : wide_int mod_inv (const wide_int &a, const wide_int &b);
3973 :
3974 : template <typename T>
3975 : T mask (unsigned int, bool);
3976 :
3977 : template <typename T>
3978 : T shifted_mask (unsigned int, unsigned int, bool);
3979 :
3980 : template <typename T>
3981 : T set_bit_in_zero (unsigned int);
3982 :
3983 : unsigned int mask (HOST_WIDE_INT *, unsigned int, bool, unsigned int);
3984 : unsigned int shifted_mask (HOST_WIDE_INT *, unsigned int, unsigned int,
3985 : bool, unsigned int);
3986 : unsigned int from_array (HOST_WIDE_INT *, const HOST_WIDE_INT *,
3987 : unsigned int, unsigned int, bool);
3988 :
3989 : wide_int bit_repeat (const wide_int_ref &, unsigned int);
3990 : wide_int clmul (const wide_int_ref &, const wide_int_ref &, unsigned int);
3991 : }
3992 :
3993 : /* Return a PRECISION-bit integer in which the low WIDTH bits are set
3994 : and the other bits are clear, or the inverse if NEGATE_P. */
3995 : inline wide_int
3996 2882635601 : wi::mask (unsigned int width, bool negate_p, unsigned int precision)
3997 : {
3998 2882635601 : wide_int result = wide_int::create (precision);
3999 5765271202 : result.set_len (mask (result.write_val (0), width, negate_p, precision));
4000 2882635601 : return result;
4001 : }
4002 :
4003 : /* Return a PRECISION-bit integer in which the low START bits are clear,
4004 : the next WIDTH bits are set, and the other bits are clear,
4005 : or the inverse if NEGATE_P. */
4006 : inline wide_int
4007 3203777466 : wi::shifted_mask (unsigned int start, unsigned int width, bool negate_p,
4008 : unsigned int precision)
4009 : {
4010 3203777466 : wide_int result = wide_int::create (precision);
4011 6407554932 : result.set_len (shifted_mask (result.write_val (0), start, width, negate_p,
4012 : precision));
4013 3203777466 : return result;
4014 : }
4015 :
4016 : /* Return a PRECISION-bit integer in which bit BIT is set and all the
4017 : others are clear. */
4018 : inline wide_int
4019 3202326931 : wi::set_bit_in_zero (unsigned int bit, unsigned int precision)
4020 : {
4021 3202326859 : return shifted_mask (bit, 1, false, precision);
4022 : }
4023 :
4024 : /* Return an integer of type T in which the low WIDTH bits are set
4025 : and the other bits are clear, or the inverse if NEGATE_P. */
4026 : template <typename T>
4027 : inline T
4028 23989143 : wi::mask (unsigned int width, bool negate_p)
4029 : {
4030 : STATIC_ASSERT (wi::int_traits<T>::precision);
4031 23989143 : T result;
4032 23989143 : result.set_len (mask (result.write_val (width / HOST_BITS_PER_WIDE_INT + 1),
4033 : width, negate_p, wi::int_traits <T>::precision));
4034 23989143 : return result;
4035 : }
4036 :
4037 : /* Return an integer of type T in which the low START bits are clear,
4038 : the next WIDTH bits are set, and the other bits are clear, or the
4039 : inverse if NEGATE_P. */
4040 : template <typename T>
4041 : inline T
4042 442259 : wi::shifted_mask (unsigned int start, unsigned int width, bool negate_p)
4043 : {
4044 : STATIC_ASSERT (wi::int_traits<T>::precision);
4045 352720 : T result;
4046 442259 : unsigned int prec = wi::int_traits <T>::precision;
4047 442259 : unsigned int est_len
4048 : = result.needs_write_val_arg
4049 352720 : ? ((start + (width > prec - start ? prec - start : width))
4050 352720 : / HOST_BITS_PER_WIDE_INT + 1) : 0;
4051 528772 : result.set_len (shifted_mask (result.write_val (est_len), start, width,
4052 : negate_p, prec));
4053 352720 : return result;
4054 : }
4055 :
4056 : /* Return an integer of type T in which bit BIT is set and all the
4057 : others are clear. */
4058 : template <typename T>
4059 : inline T
4060 86513 : wi::set_bit_in_zero (unsigned int bit)
4061 : {
4062 86513 : return shifted_mask <T> (bit, 1, false);
4063 : }
4064 :
4065 : /* Accumulate a set of overflows into OVERFLOW. */
4066 :
4067 : inline void
4068 : wi::accumulate_overflow (wi::overflow_type &overflow,
4069 : wi::overflow_type suboverflow)
4070 : {
4071 : if (!suboverflow)
4072 : return;
4073 : if (!overflow)
4074 : overflow = suboverflow;
4075 : else if (overflow != suboverflow)
4076 : overflow = wi::OVF_UNKNOWN;
4077 : }
4078 :
4079 : #endif /* WIDE_INT_H */
|