1 /* Operations with very long integers. -*- C++ -*-
2 Copyright (C) 2012-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
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).
29 The actual precision of a wide_int depends on the flavor. There
30 are three predefined flavors:
32 1) wide_int (the default). This flavor does the math in the
33 precision of its input arguments. It is assumed (and checked)
34 that the precisions of the operands and results are consistent.
35 This is the most efficient flavor. It is not possible to examine
36 bits above the precision that has been specified. Because of
37 this, the default flavor has semantics that are simple to
38 understand and in general model the underlying hardware that the
39 compiler is targetted for.
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.
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.
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.
56 2) offset_int. This is a fixed size representation that is
57 guaranteed to be large enough to compute any bit or byte sized
58 address calculation on the target. Currently the value is 64 + 4
59 bits rounded up to the next number even multiple of
60 HOST_BITS_PER_WIDE_INT (but this can be changed when the first
61 port needs more than 64 bits for the size of a pointer).
63 This flavor can be used for all address math on the target. In
64 this representation, the values are sign or zero extended based
65 on their input types to the internal precision. All math is done
66 in this precision and then the values are truncated to fit in the
67 result type. Unlike most gimple or rtl intermediate code, it is
68 not useful to perform the address arithmetic at the same
69 precision in which the operands are represented because there has
70 been no effort by the front ends to convert most addressing
71 arithmetic to canonical types.
73 3) widest_int. This representation is an approximation of
74 infinite precision math. However, it is not really infinite
75 precision math as in the GMP library. It is really finite
76 precision math where the precision is 4 times the size of the
77 largest integer that the target port can represent.
79 widest_int is supposed to be wider than any number that it needs to
80 store, meaning that there is always at least one leading sign bit.
81 All widest_int values are therefore signed.
83 There are several places in the GCC where this should/must be used:
85 * Code that does induction variable optimizations. This code
86 works with induction variables of many different types at the
87 same time. Because of this, it ends up doing many different
88 calculations where the operands are not compatible types. The
89 widest_int makes this easy, because it provides a field where
90 nothing is lost when converting from any variable,
92 * There are a small number of passes that currently use the
93 widest_int that should use the default. These should be
96 There are surprising features of offset_int and widest_int
97 that the users should be careful about:
99 1) Shifts and rotations are just weird. You have to specify a
100 precision in which the shift or rotate is to happen in. The bits
101 above this precision remain unchanged. While this is what you
102 want, it is clearly is non obvious.
104 2) Larger precision math sometimes does not produce the same
105 answer as would be expected for doing the math at the proper
106 precision. In particular, a multiply followed by a divide will
107 produce a different answer if the first product is larger than
108 what can be represented in the input precision.
110 The offset_int and the widest_int flavors are more expensive
111 than the default wide int, so in addition to the caveats with these
112 two, the default is the prefered representation.
114 All three flavors of wide_int are represented as a vector of
115 HOST_WIDE_INTs. The default and widest_int vectors contain enough elements
116 to hold a value of MAX_BITSIZE_MODE_ANY_INT bits. offset_int contains only
117 enough elements to hold ADDR_MAX_PRECISION bits. The values are stored
118 in the vector with the least significant HOST_BITS_PER_WIDE_INT bits
121 The default wide_int contains three fields: the vector (VAL),
122 the precision and a length (LEN). The length is the number of HWIs
123 needed to represent the value. widest_int and offset_int have a
124 constant precision that cannot be changed, so they only store the
127 Since most integers used in a compiler are small values, it is
128 generally profitable to use a representation of the value that is
129 as small as possible. LEN is used to indicate the number of
130 elements of the vector that are in use. The numbers are stored as
131 sign extended numbers as a means of compression. Leading
132 HOST_WIDE_INTs that contain strings of either -1 or 0 are removed
133 as long as they can be reconstructed from the top bit that is being
136 The precision and length of a wide_int are always greater than 0.
137 Any bits in a wide_int above the precision are sign-extended from the
138 most significant bit. For example, a 4-bit value 0x8 is represented as
139 VAL = { 0xf...fff8 }. However, as an optimization, we allow other integer
140 constants to be represented with undefined bits above the precision.
141 This allows INTEGER_CSTs to be pre-extended according to TYPE_SIGN,
142 so that the INTEGER_CST representation can be used both in TYPE_PRECISION
143 and in wider precisions.
145 There are constructors to create the various forms of wide_int from
146 trees, rtl and constants. For trees you can simply say:
151 However, a little more syntax is required for rtl constants since
152 they do have an explicit precision. To make an rtl into a
153 wide_int, you have to pair it with a mode. The canonical way to do
154 this is with std::make_pair as in:
157 wide_int x = std::make_pair (r, mode);
159 Similarly, a wide_int can only be constructed from a host value if
160 the target precision is given explicitly, such as in:
162 wide_int x = wi::shwi (c, prec); // sign-extend X if necessary
163 wide_int y = wi::uhwi (c, prec); // zero-extend X if necessary
165 However, offset_int and widest_int have an inherent precision and so
166 can be initialized directly from a host value:
168 offset_int x = (int) c; // sign-extend C
169 widest_int x = (unsigned int) c; // zero-extend C
171 It is also possible to do arithmetic directly on trees, rtxes and
172 constants. For example:
174 wi::add (t1, t2); // add equal-sized INTEGER_CSTs t1 and t2
175 wi::add (t1, 1); // add 1 to INTEGER_CST t1
176 wi::add (r1, r2); // add equal-sized rtx constants r1 and r2
177 wi::lshift (1, 100); // 1 << 100 as a widest_int
179 Many binary operations place restrictions on the combinations of inputs,
180 using the following rules:
182 - {tree, rtx, wide_int} op {tree, rtx, wide_int} -> wide_int
183 The inputs must be the same precision. The result is a wide_int
184 of the same precision
186 - {tree, rtx, wide_int} op (un)signed HOST_WIDE_INT -> wide_int
187 (un)signed HOST_WIDE_INT op {tree, rtx, wide_int} -> wide_int
188 The HOST_WIDE_INT is extended or truncated to the precision of
189 the other input. The result is a wide_int of the same precision
192 - (un)signed HOST_WIDE_INT op (un)signed HOST_WIDE_INT -> widest_int
193 The inputs are extended to widest_int precision and produce a
196 - offset_int op offset_int -> offset_int
197 offset_int op (un)signed HOST_WIDE_INT -> offset_int
198 (un)signed HOST_WIDE_INT op offset_int -> offset_int
200 - widest_int op widest_int -> widest_int
201 widest_int op (un)signed HOST_WIDE_INT -> widest_int
202 (un)signed HOST_WIDE_INT op widest_int -> widest_int
204 Other combinations like:
206 - widest_int op offset_int and
207 - wide_int op offset_int
209 are not allowed. The inputs should instead be extended or truncated
212 The inputs to comparison functions like wi::eq_p and wi::lts_p
213 follow the same compatibility rules, although their return types
214 are different. Unary functions on X produce the same result as
215 a binary operation X + X. Shift functions X op Y also produce
216 the same result as X + X; the precision of the shift amount Y
217 can be arbitrarily different from X. */
224 #include "insn-modes.h"
227 #define DEBUG_WIDE_INT
230 /* The MAX_BITSIZE_MODE_ANY_INT is automatically generated by a very
231 early examination of the target's mode file. The WIDE_INT_MAX_ELTS
232 can accomodate at least 1 more bit so that unsigned numbers of that
233 mode can be represented. Note that it is still possible to create
234 fixed_wide_ints that have precisions greater than
235 MAX_BITSIZE_MODE_ANY_INT. This can be useful when representing a
236 double-width multiplication result, for example. */
237 #define WIDE_INT_MAX_ELTS \
238 ((MAX_BITSIZE_MODE_ANY_INT + HOST_BITS_PER_WIDE_INT) / HOST_BITS_PER_WIDE_INT)
240 #define WIDE_INT_MAX_PRECISION (WIDE_INT_MAX_ELTS * HOST_BITS_PER_WIDE_INT)
242 /* This is the max size of any pointer on any machine. It does not
243 seem to be as easy to sniff this out of the machine description as
244 it is for MAX_BITSIZE_MODE_ANY_INT since targets may support
245 multiple address sizes and may have different address sizes for
246 different address spaces. However, currently the largest pointer
247 on any platform is 64 bits. When that changes, then it is likely
248 that a target hook should be defined so that targets can make this
249 value larger for those targets. */
250 #define ADDR_MAX_BITSIZE 64
252 /* This is the internal precision used when doing any address
253 arithmetic. The '4' is really 3 + 1. Three of the bits are for
254 the number of extra bits needed to do bit addresses and single bit is
255 allow everything to be signed without loosing any precision. Then
256 everything is rounded up to the next HWI for efficiency. */
257 #define ADDR_MAX_PRECISION \
258 ((ADDR_MAX_BITSIZE + 4 + HOST_BITS_PER_WIDE_INT - 1) & ~(HOST_BITS_PER_WIDE_INT - 1))
260 /* The number of HWIs needed to store an offset_int. */
261 #define OFFSET_INT_ELTS (ADDR_MAX_PRECISION / HOST_BITS_PER_WIDE_INT)
263 /* The type of result produced by a binary operation on types T1 and T2.
264 Defined purely for brevity. */
265 #define WI_BINARY_RESULT(T1, T2) \
266 typename wi::binary_traits <T1, T2>::result_type
268 /* The type of result produced by a unary operation on type T. */
269 #define WI_UNARY_RESULT(T) \
270 typename wi::unary_traits <T>::result_type
272 /* Define a variable RESULT to hold the result of a binary operation on
273 X and Y, which have types T1 and T2 respectively. Define VAR to
274 point to the blocks of RESULT. Once the user of the macro has
275 filled in VAR, it should call RESULT.set_len to set the number
276 of initialized blocks. */
277 #define WI_BINARY_RESULT_VAR(RESULT, VAL, T1, X, T2, Y) \
278 WI_BINARY_RESULT (T1, T2) RESULT = \
279 wi::int_traits <WI_BINARY_RESULT (T1, T2)>::get_binary_result (X, Y); \
280 HOST_WIDE_INT *VAL = RESULT.write_val ()
282 /* Similar for the result of a unary operation on X, which has type T. */
283 #define WI_UNARY_RESULT_VAR(RESULT, VAL, T, X) \
284 WI_UNARY_RESULT (T) RESULT = \
285 wi::int_traits <WI_UNARY_RESULT (T)>::get_binary_result (X, X); \
286 HOST_WIDE_INT *VAL = RESULT.write_val ()
288 template <typename T
> struct generic_wide_int
;
289 template <int N
> struct fixed_wide_int_storage
;
290 struct wide_int_storage
;
292 /* An N-bit integer. Until we can use typedef templates, use this instead. */
293 #define FIXED_WIDE_INT(N) \
294 generic_wide_int < fixed_wide_int_storage <N> >
296 typedef generic_wide_int
<wide_int_storage
> wide_int
;
297 typedef FIXED_WIDE_INT (ADDR_MAX_PRECISION
) offset_int
;
298 typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION
) widest_int
;
301 struct wide_int_ref_storage
;
303 typedef generic_wide_int
<wide_int_ref_storage
<false> > wide_int_ref
;
305 /* This can be used instead of wide_int_ref if the referenced value is
306 known to have type T. It carries across properties of T's representation,
307 such as whether excess upper bits in a HWI are defined, and can therefore
308 help avoid redundant work.
310 The macro could be replaced with a template typedef, once we're able
312 #define WIDE_INT_REF_FOR(T) \
314 <wide_int_ref_storage <wi::int_traits <T>::is_sign_extended> >
318 /* Classifies an integer based on its precision. */
319 enum precision_type
{
320 /* The integer has both a precision and defined signedness. This allows
321 the integer to be converted to any width, since we know whether to fill
322 any extra bits with zeros or signs. */
325 /* The integer has a variable precision but no defined signedness. */
328 /* The integer has a constant precision (known at GCC compile time)
329 but no defined signedness. */
333 /* This class, which has no default implementation, is expected to
334 provide the following members:
336 static const enum precision_type precision_type;
337 Classifies the type of T.
339 static const unsigned int precision;
340 Only defined if precision_type == CONST_PRECISION. Specifies the
341 precision of all integers of type T.
343 static const bool host_dependent_precision;
344 True if the precision of T depends (or can depend) on the host.
346 static unsigned int get_precision (const T &x)
347 Return the number of bits in X.
349 static wi::storage_ref *decompose (HOST_WIDE_INT *scratch,
350 unsigned int precision, const T &x)
351 Decompose X as a PRECISION-bit integer, returning the associated
352 wi::storage_ref. SCRATCH is available as scratch space if needed.
353 The routine should assert that PRECISION is acceptable. */
354 template <typename T
> struct int_traits
;
356 /* This class provides a single type, result_type, which specifies the
357 type of integer produced by a binary operation whose inputs have
358 types T1 and T2. The definition should be symmetric. */
359 template <typename T1
, typename T2
,
360 enum precision_type P1
= int_traits
<T1
>::precision_type
,
361 enum precision_type P2
= int_traits
<T2
>::precision_type
>
362 struct binary_traits
;
364 /* The result of a unary operation on T is the same as the result of
365 a binary operation on two values of type T. */
366 template <typename T
>
367 struct unary_traits
: public binary_traits
<T
, T
> {};
369 /* Specify the result type for each supported combination of binary
370 inputs. Note that CONST_PRECISION and VAR_PRECISION cannot be
371 mixed, in order to give stronger type checking. When both inputs
372 are CONST_PRECISION, they must have the same precision. */
374 template <typename T1
, typename T2
>
375 struct binary_traits
<T1
, T2
, FLEXIBLE_PRECISION
, FLEXIBLE_PRECISION
>
377 typedef widest_int result_type
;
381 template <typename T1
, typename T2
>
382 struct binary_traits
<T1
, T2
, FLEXIBLE_PRECISION
, VAR_PRECISION
>
384 typedef wide_int result_type
;
388 template <typename T1
, typename T2
>
389 struct binary_traits
<T1
, T2
, FLEXIBLE_PRECISION
, CONST_PRECISION
>
391 /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
392 so as not to confuse gengtype. */
393 typedef generic_wide_int
< fixed_wide_int_storage
394 <int_traits
<T2
>::precision
> > result_type
;
398 template <typename T1
, typename T2
>
399 struct binary_traits
<T1
, T2
, VAR_PRECISION
, FLEXIBLE_PRECISION
>
401 typedef wide_int result_type
;
405 template <typename T1
, typename T2
>
406 struct binary_traits
<T1
, T2
, CONST_PRECISION
, FLEXIBLE_PRECISION
>
408 /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
409 so as not to confuse gengtype. */
410 typedef generic_wide_int
< fixed_wide_int_storage
411 <int_traits
<T1
>::precision
> > result_type
;
415 template <typename T1
, typename T2
>
416 struct binary_traits
<T1
, T2
, CONST_PRECISION
, CONST_PRECISION
>
418 /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
419 so as not to confuse gengtype. */
420 STATIC_ASSERT (int_traits
<T1
>::precision
== int_traits
<T2
>::precision
);
421 typedef generic_wide_int
< fixed_wide_int_storage
422 <int_traits
<T1
>::precision
> > result_type
;
426 template <typename T1
, typename T2
>
427 struct binary_traits
<T1
, T2
, VAR_PRECISION
, VAR_PRECISION
>
429 typedef wide_int result_type
;
433 /* Public functions for querying and operating on integers. */
436 template <typename T
>
437 unsigned int get_precision (const T
&);
439 template <typename T1
, typename T2
>
440 unsigned int get_binary_precision (const T1
&, const T2
&);
442 template <typename T1
, typename T2
>
443 void copy (T1
&, const T2
&);
445 #define UNARY_PREDICATE \
446 template <typename T> bool
447 #define UNARY_FUNCTION \
448 template <typename T> WI_UNARY_RESULT (T)
449 #define BINARY_PREDICATE \
450 template <typename T1, typename T2> bool
451 #define BINARY_FUNCTION \
452 template <typename T1, typename T2> WI_BINARY_RESULT (T1, T2)
453 #define SHIFT_FUNCTION \
454 template <typename T1, typename T2> WI_UNARY_RESULT (T1)
456 UNARY_PREDICATE
fits_shwi_p (const T
&);
457 UNARY_PREDICATE
fits_uhwi_p (const T
&);
458 UNARY_PREDICATE
neg_p (const T
&, signop
= SIGNED
);
460 template <typename T
>
461 HOST_WIDE_INT
sign_mask (const T
&);
463 BINARY_PREDICATE
eq_p (const T1
&, const T2
&);
464 BINARY_PREDICATE
ne_p (const T1
&, const T2
&);
465 BINARY_PREDICATE
lt_p (const T1
&, const T2
&, signop
);
466 BINARY_PREDICATE
lts_p (const T1
&, const T2
&);
467 BINARY_PREDICATE
ltu_p (const T1
&, const T2
&);
468 BINARY_PREDICATE
le_p (const T1
&, const T2
&, signop
);
469 BINARY_PREDICATE
les_p (const T1
&, const T2
&);
470 BINARY_PREDICATE
leu_p (const T1
&, const T2
&);
471 BINARY_PREDICATE
gt_p (const T1
&, const T2
&, signop
);
472 BINARY_PREDICATE
gts_p (const T1
&, const T2
&);
473 BINARY_PREDICATE
gtu_p (const T1
&, const T2
&);
474 BINARY_PREDICATE
ge_p (const T1
&, const T2
&, signop
);
475 BINARY_PREDICATE
ges_p (const T1
&, const T2
&);
476 BINARY_PREDICATE
geu_p (const T1
&, const T2
&);
478 template <typename T1
, typename T2
>
479 int cmp (const T1
&, const T2
&, signop
);
481 template <typename T1
, typename T2
>
482 int cmps (const T1
&, const T2
&);
484 template <typename T1
, typename T2
>
485 int cmpu (const T1
&, const T2
&);
487 UNARY_FUNCTION
bit_not (const T
&);
488 UNARY_FUNCTION
neg (const T
&);
489 UNARY_FUNCTION
neg (const T
&, bool *);
490 UNARY_FUNCTION
abs (const T
&);
491 UNARY_FUNCTION
ext (const T
&, unsigned int, signop
);
492 UNARY_FUNCTION
sext (const T
&, unsigned int);
493 UNARY_FUNCTION
zext (const T
&, unsigned int);
494 UNARY_FUNCTION
set_bit (const T
&, unsigned int);
496 BINARY_FUNCTION
min (const T1
&, const T2
&, signop
);
497 BINARY_FUNCTION
smin (const T1
&, const T2
&);
498 BINARY_FUNCTION
umin (const T1
&, const T2
&);
499 BINARY_FUNCTION
max (const T1
&, const T2
&, signop
);
500 BINARY_FUNCTION
smax (const T1
&, const T2
&);
501 BINARY_FUNCTION
umax (const T1
&, const T2
&);
503 BINARY_FUNCTION
bit_and (const T1
&, const T2
&);
504 BINARY_FUNCTION
bit_and_not (const T1
&, const T2
&);
505 BINARY_FUNCTION
bit_or (const T1
&, const T2
&);
506 BINARY_FUNCTION
bit_or_not (const T1
&, const T2
&);
507 BINARY_FUNCTION
bit_xor (const T1
&, const T2
&);
508 BINARY_FUNCTION
add (const T1
&, const T2
&);
509 BINARY_FUNCTION
add (const T1
&, const T2
&, signop
, bool *);
510 BINARY_FUNCTION
sub (const T1
&, const T2
&);
511 BINARY_FUNCTION
sub (const T1
&, const T2
&, signop
, bool *);
512 BINARY_FUNCTION
mul (const T1
&, const T2
&);
513 BINARY_FUNCTION
mul (const T1
&, const T2
&, signop
, bool *);
514 BINARY_FUNCTION
smul (const T1
&, const T2
&, bool *);
515 BINARY_FUNCTION
umul (const T1
&, const T2
&, bool *);
516 BINARY_FUNCTION
mul_high (const T1
&, const T2
&, signop
);
517 BINARY_FUNCTION
div_trunc (const T1
&, const T2
&, signop
, bool * = 0);
518 BINARY_FUNCTION
sdiv_trunc (const T1
&, const T2
&);
519 BINARY_FUNCTION
udiv_trunc (const T1
&, const T2
&);
520 BINARY_FUNCTION
div_floor (const T1
&, const T2
&, signop
, bool * = 0);
521 BINARY_FUNCTION
udiv_floor (const T1
&, const T2
&);
522 BINARY_FUNCTION
sdiv_floor (const T1
&, const T2
&);
523 BINARY_FUNCTION
div_ceil (const T1
&, const T2
&, signop
, bool * = 0);
524 BINARY_FUNCTION
div_round (const T1
&, const T2
&, signop
, bool * = 0);
525 BINARY_FUNCTION
divmod_trunc (const T1
&, const T2
&, signop
,
526 WI_BINARY_RESULT (T1
, T2
) *);
527 BINARY_FUNCTION
mod_trunc (const T1
&, const T2
&, signop
, bool * = 0);
528 BINARY_FUNCTION
smod_trunc (const T1
&, const T2
&);
529 BINARY_FUNCTION
umod_trunc (const T1
&, const T2
&);
530 BINARY_FUNCTION
mod_floor (const T1
&, const T2
&, signop
, bool * = 0);
531 BINARY_FUNCTION
umod_floor (const T1
&, const T2
&);
532 BINARY_FUNCTION
mod_ceil (const T1
&, const T2
&, signop
, bool * = 0);
533 BINARY_FUNCTION
mod_round (const T1
&, const T2
&, signop
, bool * = 0);
535 template <typename T1
, typename T2
>
536 bool multiple_of_p (const T1
&, const T2
&, signop
,
537 WI_BINARY_RESULT (T1
, T2
) *);
539 SHIFT_FUNCTION
lshift (const T1
&, const T2
&);
540 SHIFT_FUNCTION
lrshift (const T1
&, const T2
&);
541 SHIFT_FUNCTION
arshift (const T1
&, const T2
&);
542 SHIFT_FUNCTION
rshift (const T1
&, const T2
&, signop sgn
);
543 SHIFT_FUNCTION
lrotate (const T1
&, const T2
&, unsigned int = 0);
544 SHIFT_FUNCTION
rrotate (const T1
&, const T2
&, unsigned int = 0);
546 #undef SHIFT_FUNCTION
547 #undef BINARY_PREDICATE
548 #undef BINARY_FUNCTION
549 #undef UNARY_PREDICATE
550 #undef UNARY_FUNCTION
552 bool only_sign_bit_p (const wide_int_ref
&, unsigned int);
553 bool only_sign_bit_p (const wide_int_ref
&);
554 int clz (const wide_int_ref
&);
555 int clrsb (const wide_int_ref
&);
556 int ctz (const wide_int_ref
&);
557 int exact_log2 (const wide_int_ref
&);
558 int floor_log2 (const wide_int_ref
&);
559 int ffs (const wide_int_ref
&);
560 int popcount (const wide_int_ref
&);
561 int parity (const wide_int_ref
&);
563 template <typename T
>
564 unsigned HOST_WIDE_INT
extract_uhwi (const T
&, unsigned int, unsigned int);
569 /* Contains the components of a decomposed integer for easy, direct
573 storage_ref (const HOST_WIDE_INT
*, unsigned int, unsigned int);
575 const HOST_WIDE_INT
*val
;
577 unsigned int precision
;
579 /* Provide enough trappings for this class to act as storage for
581 unsigned int get_len () const;
582 unsigned int get_precision () const;
583 const HOST_WIDE_INT
*get_val () const;
587 inline::wi::storage_ref::storage_ref (const HOST_WIDE_INT
*val_in
,
589 unsigned int precision_in
)
590 : val (val_in
), len (len_in
), precision (precision_in
)
595 wi::storage_ref::get_len () const
601 wi::storage_ref::get_precision () const
606 inline const HOST_WIDE_INT
*
607 wi::storage_ref::get_val () const
612 /* This class defines an integer type using the storage provided by the
613 template argument. The storage class must provide the following
616 unsigned int get_precision () const
617 Return the number of bits in the integer.
619 HOST_WIDE_INT *get_val () const
620 Return a pointer to the array of blocks that encodes the integer.
622 unsigned int get_len () const
623 Return the number of blocks in get_val (). If this is smaller
624 than the number of blocks implied by get_precision (), the
625 remaining blocks are sign extensions of block get_len () - 1.
627 Although not required by generic_wide_int itself, writable storage
628 classes can also provide the following functions:
630 HOST_WIDE_INT *write_val ()
631 Get a modifiable version of get_val ()
633 unsigned int set_len (unsigned int len)
634 Set the value returned by get_len () to LEN. */
635 template <typename storage
>
636 class GTY(()) generic_wide_int
: public storage
641 template <typename T
>
642 generic_wide_int (const T
&);
644 template <typename T
>
645 generic_wide_int (const T
&, unsigned int);
648 HOST_WIDE_INT
to_shwi (unsigned int) const;
649 HOST_WIDE_INT
to_shwi () const;
650 unsigned HOST_WIDE_INT
to_uhwi (unsigned int) const;
651 unsigned HOST_WIDE_INT
to_uhwi () const;
652 HOST_WIDE_INT
to_short_addr () const;
654 /* Public accessors for the interior of a wide int. */
655 HOST_WIDE_INT
sign_mask () const;
656 HOST_WIDE_INT
elt (unsigned int) const;
657 unsigned HOST_WIDE_INT
ulow () const;
658 unsigned HOST_WIDE_INT
uhigh () const;
659 HOST_WIDE_INT
slow () const;
660 HOST_WIDE_INT
shigh () const;
662 template <typename T
>
663 generic_wide_int
&operator = (const T
&);
665 #define BINARY_PREDICATE(OP, F) \
666 template <typename T> \
667 bool OP (const T &c) const { return wi::F (*this, c); }
669 #define UNARY_OPERATOR(OP, F) \
670 WI_UNARY_RESULT (generic_wide_int) OP () const { return wi::F (*this); }
672 #define BINARY_OPERATOR(OP, F) \
673 template <typename T> \
674 WI_BINARY_RESULT (generic_wide_int, T) \
675 OP (const T &c) const { return wi::F (*this, c); }
677 #define ASSIGNMENT_OPERATOR(OP, F) \
678 template <typename T> \
679 generic_wide_int &OP (const T &c) { return (*this = wi::F (*this, c)); }
681 #define INCDEC_OPERATOR(OP, DELTA) \
682 generic_wide_int &OP () { *this += DELTA; return *this; }
684 UNARY_OPERATOR (operator ~, bit_not
)
685 UNARY_OPERATOR (operator -, neg
)
686 BINARY_PREDICATE (operator ==, eq_p
)
687 BINARY_PREDICATE (operator !=, ne_p
)
688 BINARY_OPERATOR (operator &, bit_and
)
689 BINARY_OPERATOR (and_not
, bit_and_not
)
690 BINARY_OPERATOR (operator |, bit_or
)
691 BINARY_OPERATOR (or_not
, bit_or_not
)
692 BINARY_OPERATOR (operator ^, bit_xor
)
693 BINARY_OPERATOR (operator +, add
)
694 BINARY_OPERATOR (operator -, sub
)
695 BINARY_OPERATOR (operator *, mul
)
696 ASSIGNMENT_OPERATOR (operator &=, bit_and
)
697 ASSIGNMENT_OPERATOR (operator |=, bit_or
)
698 ASSIGNMENT_OPERATOR (operator ^=, bit_xor
)
699 ASSIGNMENT_OPERATOR (operator +=, add
)
700 ASSIGNMENT_OPERATOR (operator -=, sub
)
701 ASSIGNMENT_OPERATOR (operator *=, mul
)
702 INCDEC_OPERATOR (operator ++, 1)
703 INCDEC_OPERATOR (operator --, -1)
705 #undef BINARY_PREDICATE
706 #undef UNARY_OPERATOR
707 #undef BINARY_OPERATOR
708 #undef ASSIGNMENT_OPERATOR
709 #undef INCDEC_OPERATOR
711 char *dump (char *) const;
713 static const bool is_sign_extended
714 = wi::int_traits
<generic_wide_int
<storage
> >::is_sign_extended
;
717 template <typename storage
>
718 inline generic_wide_int
<storage
>::generic_wide_int () {}
720 template <typename storage
>
721 template <typename T
>
722 inline generic_wide_int
<storage
>::generic_wide_int (const T
&x
)
727 template <typename storage
>
728 template <typename T
>
729 inline generic_wide_int
<storage
>::generic_wide_int (const T
&x
,
730 unsigned int precision
)
731 : storage (x
, precision
)
735 /* Return THIS as a signed HOST_WIDE_INT, sign-extending from PRECISION.
736 If THIS does not fit in PRECISION, the information is lost. */
737 template <typename storage
>
739 generic_wide_int
<storage
>::to_shwi (unsigned int precision
) const
741 if (precision
< HOST_BITS_PER_WIDE_INT
)
742 return sext_hwi (this->get_val ()[0], precision
);
744 return this->get_val ()[0];
747 /* Return THIS as a signed HOST_WIDE_INT, in its natural precision. */
748 template <typename storage
>
750 generic_wide_int
<storage
>::to_shwi () const
752 if (is_sign_extended
)
753 return this->get_val ()[0];
755 return to_shwi (this->get_precision ());
758 /* Return THIS as an unsigned HOST_WIDE_INT, zero-extending from
759 PRECISION. If THIS does not fit in PRECISION, the information
761 template <typename storage
>
762 inline unsigned HOST_WIDE_INT
763 generic_wide_int
<storage
>::to_uhwi (unsigned int precision
) const
765 if (precision
< HOST_BITS_PER_WIDE_INT
)
766 return zext_hwi (this->get_val ()[0], precision
);
768 return this->get_val ()[0];
771 /* Return THIS as an signed HOST_WIDE_INT, in its natural precision. */
772 template <typename storage
>
773 inline unsigned HOST_WIDE_INT
774 generic_wide_int
<storage
>::to_uhwi () const
776 return to_uhwi (this->get_precision ());
779 /* TODO: The compiler is half converted from using HOST_WIDE_INT to
780 represent addresses to using offset_int to represent addresses.
781 We use to_short_addr at the interface from new code to old,
783 template <typename storage
>
785 generic_wide_int
<storage
>::to_short_addr () const
787 return this->get_val ()[0];
790 /* Return the implicit value of blocks above get_len (). */
791 template <typename storage
>
793 generic_wide_int
<storage
>::sign_mask () const
795 unsigned int len
= this->get_len ();
796 unsigned HOST_WIDE_INT high
= this->get_val ()[len
- 1];
797 if (!is_sign_extended
)
799 unsigned int precision
= this->get_precision ();
800 int excess
= len
* HOST_BITS_PER_WIDE_INT
- precision
;
804 return HOST_WIDE_INT (high
) < 0 ? -1 : 0;
807 /* Return the signed value of the least-significant explicitly-encoded
809 template <typename storage
>
811 generic_wide_int
<storage
>::slow () const
813 return this->get_val ()[0];
816 /* Return the signed value of the most-significant explicitly-encoded
818 template <typename storage
>
820 generic_wide_int
<storage
>::shigh () const
822 return this->get_val ()[this->get_len () - 1];
825 /* Return the unsigned value of the least-significant
826 explicitly-encoded block. */
827 template <typename storage
>
828 inline unsigned HOST_WIDE_INT
829 generic_wide_int
<storage
>::ulow () const
831 return this->get_val ()[0];
834 /* Return the unsigned value of the most-significant
835 explicitly-encoded block. */
836 template <typename storage
>
837 inline unsigned HOST_WIDE_INT
838 generic_wide_int
<storage
>::uhigh () const
840 return this->get_val ()[this->get_len () - 1];
843 /* Return block I, which might be implicitly or explicit encoded. */
844 template <typename storage
>
846 generic_wide_int
<storage
>::elt (unsigned int i
) const
848 if (i
>= this->get_len ())
851 return this->get_val ()[i
];
854 template <typename storage
>
855 template <typename T
>
856 generic_wide_int
<storage
> &
857 generic_wide_int
<storage
>::operator = (const T
&x
)
859 storage::operator = (x
);
866 template <typename storage
>
867 struct int_traits
< generic_wide_int
<storage
> >
868 : public wi::int_traits
<storage
>
870 static unsigned int get_precision (const generic_wide_int
<storage
> &);
871 static wi::storage_ref
decompose (HOST_WIDE_INT
*, unsigned int,
872 const generic_wide_int
<storage
> &);
876 template <typename storage
>
878 wi::int_traits
< generic_wide_int
<storage
> >::
879 get_precision (const generic_wide_int
<storage
> &x
)
881 return x
.get_precision ();
884 template <typename storage
>
885 inline wi::storage_ref
886 wi::int_traits
< generic_wide_int
<storage
> >::
887 decompose (HOST_WIDE_INT
*, unsigned int precision
,
888 const generic_wide_int
<storage
> &x
)
890 gcc_checking_assert (precision
== x
.get_precision ());
891 return wi::storage_ref (x
.get_val (), x
.get_len (), precision
);
894 /* Provide the storage for a wide_int_ref. This acts like a read-only
895 wide_int, with the optimization that VAL is normally a pointer to
896 another integer's storage, so that no array copy is needed. */
898 struct wide_int_ref_storage
: public wi::storage_ref
901 /* Scratch space that can be used when decomposing the original integer.
902 It must live as long as this object. */
903 HOST_WIDE_INT scratch
[2];
906 wide_int_ref_storage (const wi::storage_ref
&);
908 template <typename T
>
909 wide_int_ref_storage (const T
&);
911 template <typename T
>
912 wide_int_ref_storage (const T
&, unsigned int);
915 /* Create a reference from an existing reference. */
917 inline wide_int_ref_storage
<SE
>::
918 wide_int_ref_storage (const wi::storage_ref
&x
)
922 /* Create a reference to integer X in its natural precision. Note
923 that the natural precision is host-dependent for primitive
926 template <typename T
>
927 inline wide_int_ref_storage
<SE
>::wide_int_ref_storage (const T
&x
)
928 : storage_ref (wi::int_traits
<T
>::decompose (scratch
,
929 wi::get_precision (x
), x
))
933 /* Create a reference to integer X in precision PRECISION. */
935 template <typename T
>
936 inline wide_int_ref_storage
<SE
>::wide_int_ref_storage (const T
&x
,
937 unsigned int precision
)
938 : storage_ref (wi::int_traits
<T
>::decompose (scratch
, precision
, x
))
946 struct int_traits
<wide_int_ref_storage
<SE
> >
948 static const enum precision_type precision_type
= VAR_PRECISION
;
949 /* wi::storage_ref can be a reference to a primitive type,
950 so this is the conservatively-correct setting. */
951 static const bool host_dependent_precision
= true;
952 static const bool is_sign_extended
= SE
;
958 unsigned int force_to_size (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
959 unsigned int, unsigned int, unsigned int,
961 unsigned int from_array (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
962 unsigned int, unsigned int, bool = true);
965 /* The storage used by wide_int. */
966 class GTY(()) wide_int_storage
969 HOST_WIDE_INT val
[WIDE_INT_MAX_ELTS
];
971 unsigned int precision
;
975 template <typename T
>
976 wide_int_storage (const T
&);
978 /* The standard generic_wide_int storage methods. */
979 unsigned int get_precision () const;
980 const HOST_WIDE_INT
*get_val () const;
981 unsigned int get_len () const;
982 HOST_WIDE_INT
*write_val ();
983 void set_len (unsigned int, bool = false);
985 static wide_int
from (const wide_int_ref
&, unsigned int, signop
);
986 static wide_int
from_array (const HOST_WIDE_INT
*, unsigned int,
987 unsigned int, bool = true);
988 static wide_int
create (unsigned int);
990 /* FIXME: target-dependent, so should disappear. */
991 wide_int
bswap () const;
997 struct int_traits
<wide_int_storage
>
999 static const enum precision_type precision_type
= VAR_PRECISION
;
1000 /* Guaranteed by a static assert in the wide_int_storage constructor. */
1001 static const bool host_dependent_precision
= false;
1002 static const bool is_sign_extended
= true;
1003 template <typename T1
, typename T2
>
1004 static wide_int
get_binary_result (const T1
&, const T2
&);
1008 inline wide_int_storage::wide_int_storage () {}
1010 /* Initialize the storage from integer X, in its natural precision.
1011 Note that we do not allow integers with host-dependent precision
1012 to become wide_ints; wide_ints must always be logically independent
1014 template <typename T
>
1015 inline wide_int_storage::wide_int_storage (const T
&x
)
1017 STATIC_ASSERT (!wi::int_traits
<T
>::host_dependent_precision
);
1018 WIDE_INT_REF_FOR (T
) xi (x
);
1019 precision
= xi
.precision
;
1020 wi::copy (*this, xi
);
1024 wide_int_storage::get_precision () const
1029 inline const HOST_WIDE_INT
*
1030 wide_int_storage::get_val () const
1036 wide_int_storage::get_len () const
1041 inline HOST_WIDE_INT
*
1042 wide_int_storage::write_val ()
1048 wide_int_storage::set_len (unsigned int l
, bool is_sign_extended
)
1051 if (!is_sign_extended
&& len
* HOST_BITS_PER_WIDE_INT
> precision
)
1052 val
[len
- 1] = sext_hwi (val
[len
- 1],
1053 precision
% HOST_BITS_PER_WIDE_INT
);
1056 /* Treat X as having signedness SGN and convert it to a PRECISION-bit
1059 wide_int_storage::from (const wide_int_ref
&x
, unsigned int precision
,
1062 wide_int result
= wide_int::create (precision
);
1063 result
.set_len (wi::force_to_size (result
.write_val (), x
.val
, x
.len
,
1064 x
.precision
, precision
, sgn
));
1068 /* Create a wide_int from the explicit block encoding given by VAL and
1069 LEN. PRECISION is the precision of the integer. NEED_CANON_P is
1070 true if the encoding may have redundant trailing blocks. */
1072 wide_int_storage::from_array (const HOST_WIDE_INT
*val
, unsigned int len
,
1073 unsigned int precision
, bool need_canon_p
)
1075 wide_int result
= wide_int::create (precision
);
1076 result
.set_len (wi::from_array (result
.write_val (), val
, len
, precision
,
1081 /* Return an uninitialized wide_int with precision PRECISION. */
1083 wide_int_storage::create (unsigned int precision
)
1086 x
.precision
= precision
;
1090 template <typename T1
, typename T2
>
1092 wi::int_traits
<wide_int_storage
>::get_binary_result (const T1
&x
, const T2
&y
)
1094 /* This shouldn't be used for two flexible-precision inputs. */
1095 STATIC_ASSERT (wi::int_traits
<T1
>::precision_type
!= FLEXIBLE_PRECISION
1096 || wi::int_traits
<T2
>::precision_type
!= FLEXIBLE_PRECISION
);
1097 if (wi::int_traits
<T1
>::precision_type
== FLEXIBLE_PRECISION
)
1098 return wide_int::create (wi::get_precision (y
));
1100 return wide_int::create (wi::get_precision (x
));
1103 /* The storage used by FIXED_WIDE_INT (N). */
1105 class GTY(()) fixed_wide_int_storage
1108 HOST_WIDE_INT val
[(N
+ HOST_BITS_PER_WIDE_INT
+ 1) / HOST_BITS_PER_WIDE_INT
];
1112 fixed_wide_int_storage ();
1113 template <typename T
>
1114 fixed_wide_int_storage (const T
&);
1116 /* The standard generic_wide_int storage methods. */
1117 unsigned int get_precision () const;
1118 const HOST_WIDE_INT
*get_val () const;
1119 unsigned int get_len () const;
1120 HOST_WIDE_INT
*write_val ();
1121 void set_len (unsigned int, bool = false);
1123 static FIXED_WIDE_INT (N
) from (const wide_int_ref
&, signop
);
1124 static FIXED_WIDE_INT (N
) from_array (const HOST_WIDE_INT
*, unsigned int,
1132 struct int_traits
< fixed_wide_int_storage
<N
> >
1134 static const enum precision_type precision_type
= CONST_PRECISION
;
1135 static const bool host_dependent_precision
= false;
1136 static const bool is_sign_extended
= true;
1137 static const unsigned int precision
= N
;
1138 template <typename T1
, typename T2
>
1139 static FIXED_WIDE_INT (N
) get_binary_result (const T1
&, const T2
&);
1144 inline fixed_wide_int_storage
<N
>::fixed_wide_int_storage () {}
1146 /* Initialize the storage from integer X, in precision N. */
1148 template <typename T
>
1149 inline fixed_wide_int_storage
<N
>::fixed_wide_int_storage (const T
&x
)
1151 /* Check for type compatibility. We don't want to initialize a
1152 fixed-width integer from something like a wide_int. */
1153 WI_BINARY_RESULT (T
, FIXED_WIDE_INT (N
)) *assertion ATTRIBUTE_UNUSED
;
1154 wi::copy (*this, WIDE_INT_REF_FOR (T
) (x
, N
));
1159 fixed_wide_int_storage
<N
>::get_precision () const
1165 inline const HOST_WIDE_INT
*
1166 fixed_wide_int_storage
<N
>::get_val () const
1173 fixed_wide_int_storage
<N
>::get_len () const
1179 inline HOST_WIDE_INT
*
1180 fixed_wide_int_storage
<N
>::write_val ()
1187 fixed_wide_int_storage
<N
>::set_len (unsigned int l
, bool)
1190 /* There are no excess bits in val[len - 1]. */
1191 STATIC_ASSERT (N
% HOST_BITS_PER_WIDE_INT
== 0);
1194 /* Treat X as having signedness SGN and convert it to an N-bit number. */
1196 inline FIXED_WIDE_INT (N
)
1197 fixed_wide_int_storage
<N
>::from (const wide_int_ref
&x
, signop sgn
)
1199 FIXED_WIDE_INT (N
) result
;
1200 result
.set_len (wi::force_to_size (result
.write_val (), x
.val
, x
.len
,
1201 x
.precision
, N
, sgn
));
1205 /* Create a FIXED_WIDE_INT (N) from the explicit block encoding given by
1206 VAL and LEN. NEED_CANON_P is true if the encoding may have redundant
1209 inline FIXED_WIDE_INT (N
)
1210 fixed_wide_int_storage
<N
>::from_array (const HOST_WIDE_INT
*val
,
1214 FIXED_WIDE_INT (N
) result
;
1215 result
.set_len (wi::from_array (result
.write_val (), val
, len
,
1221 template <typename T1
, typename T2
>
1222 inline FIXED_WIDE_INT (N
)
1223 wi::int_traits
< fixed_wide_int_storage
<N
> >::
1224 get_binary_result (const T1
&, const T2
&)
1226 return FIXED_WIDE_INT (N
) ();
1229 /* A reference to one element of a trailing_wide_ints structure. */
1230 class trailing_wide_int_storage
1233 /* The precision of the integer, which is a fixed property of the
1234 parent trailing_wide_ints. */
1235 unsigned int m_precision
;
1237 /* A pointer to the length field. */
1238 unsigned char *m_len
;
1240 /* A pointer to the HWI array. There are enough elements to hold all
1241 values of precision M_PRECISION. */
1242 HOST_WIDE_INT
*m_val
;
1245 trailing_wide_int_storage (unsigned int, unsigned char *, HOST_WIDE_INT
*);
1247 /* The standard generic_wide_int storage methods. */
1248 unsigned int get_len () const;
1249 unsigned int get_precision () const;
1250 const HOST_WIDE_INT
*get_val () const;
1251 HOST_WIDE_INT
*write_val ();
1252 void set_len (unsigned int, bool = false);
1254 template <typename T
>
1255 trailing_wide_int_storage
&operator = (const T
&);
1258 typedef generic_wide_int
<trailing_wide_int_storage
> trailing_wide_int
;
1260 /* trailing_wide_int behaves like a wide_int. */
1264 struct int_traits
<trailing_wide_int_storage
>
1265 : public int_traits
<wide_int_storage
> {};
1268 /* An array of N wide_int-like objects that can be put at the end of
1269 a variable-sized structure. Use extra_size to calculate how many
1270 bytes beyond the sizeof need to be allocated. Use set_precision
1271 to initialize the structure. */
1273 class GTY(()) trailing_wide_ints
1276 /* The shared precision of each number. */
1277 unsigned short m_precision
;
1279 /* The shared maximum length of each number. */
1280 unsigned char m_max_len
;
1282 /* The current length of each number. */
1283 unsigned char m_len
[N
];
1285 /* The variable-length part of the structure, which always contains
1286 at least one HWI. Element I starts at index I * M_MAX_LEN. */
1287 HOST_WIDE_INT m_val
[1];
1290 void set_precision (unsigned int);
1291 trailing_wide_int
operator [] (unsigned int);
1292 static size_t extra_size (unsigned int);
1295 inline trailing_wide_int_storage::
1296 trailing_wide_int_storage (unsigned int precision
, unsigned char *len
,
1298 : m_precision (precision
), m_len (len
), m_val (val
)
1303 trailing_wide_int_storage::get_len () const
1309 trailing_wide_int_storage::get_precision () const
1314 inline const HOST_WIDE_INT
*
1315 trailing_wide_int_storage::get_val () const
1320 inline HOST_WIDE_INT
*
1321 trailing_wide_int_storage::write_val ()
1327 trailing_wide_int_storage::set_len (unsigned int len
, bool is_sign_extended
)
1330 if (!is_sign_extended
&& len
* HOST_BITS_PER_WIDE_INT
> m_precision
)
1331 m_val
[len
- 1] = sext_hwi (m_val
[len
- 1],
1332 m_precision
% HOST_BITS_PER_WIDE_INT
);
1335 template <typename T
>
1336 inline trailing_wide_int_storage
&
1337 trailing_wide_int_storage::operator = (const T
&x
)
1339 WIDE_INT_REF_FOR (T
) xi (x
, m_precision
);
1340 wi::copy (*this, xi
);
1344 /* Initialize the structure and record that all elements have precision
1348 trailing_wide_ints
<N
>::set_precision (unsigned int precision
)
1350 m_precision
= precision
;
1351 m_max_len
= ((precision
+ HOST_BITS_PER_WIDE_INT
- 1)
1352 / HOST_BITS_PER_WIDE_INT
);
1355 /* Return a reference to element INDEX. */
1357 inline trailing_wide_int
1358 trailing_wide_ints
<N
>::operator [] (unsigned int index
)
1360 return trailing_wide_int_storage (m_precision
, &m_len
[index
],
1361 &m_val
[index
* m_max_len
]);
1364 /* Return how many extra bytes need to be added to the end of the structure
1365 in order to handle N wide_ints of precision PRECISION. */
1368 trailing_wide_ints
<N
>::extra_size (unsigned int precision
)
1370 unsigned int max_len
= ((precision
+ HOST_BITS_PER_WIDE_INT
- 1)
1371 / HOST_BITS_PER_WIDE_INT
);
1372 return (N
* max_len
- 1) * sizeof (HOST_WIDE_INT
);
1375 /* This macro is used in structures that end with a trailing_wide_ints field
1376 called FIELD. It declares get_NAME() and set_NAME() methods to access
1377 element I of FIELD. */
1378 #define TRAILING_WIDE_INT_ACCESSOR(NAME, FIELD, I) \
1379 trailing_wide_int get_##NAME () { return FIELD[I]; } \
1380 template <typename T> void set_##NAME (const T &x) { FIELD[I] = x; }
1384 /* Implementation of int_traits for primitive integer types like "int". */
1385 template <typename T
, bool signed_p
>
1386 struct primitive_int_traits
1388 static const enum precision_type precision_type
= FLEXIBLE_PRECISION
;
1389 static const bool host_dependent_precision
= true;
1390 static const bool is_sign_extended
= true;
1391 static unsigned int get_precision (T
);
1392 static wi::storage_ref
decompose (HOST_WIDE_INT
*, unsigned int, T
);
1396 template <typename T
, bool signed_p
>
1398 wi::primitive_int_traits
<T
, signed_p
>::get_precision (T
)
1400 return sizeof (T
) * CHAR_BIT
;
1403 template <typename T
, bool signed_p
>
1404 inline wi::storage_ref
1405 wi::primitive_int_traits
<T
, signed_p
>::decompose (HOST_WIDE_INT
*scratch
,
1406 unsigned int precision
, T x
)
1409 if (signed_p
|| scratch
[0] >= 0 || precision
<= HOST_BITS_PER_WIDE_INT
)
1410 return wi::storage_ref (scratch
, 1, precision
);
1412 return wi::storage_ref (scratch
, 2, precision
);
1415 /* Allow primitive C types to be used in wi:: routines. */
1419 struct int_traits
<int>
1420 : public primitive_int_traits
<int, true> {};
1423 struct int_traits
<unsigned int>
1424 : public primitive_int_traits
<unsigned int, false> {};
1426 #if HOST_BITS_PER_INT != HOST_BITS_PER_WIDE_INT
1428 struct int_traits
<HOST_WIDE_INT
>
1429 : public primitive_int_traits
<HOST_WIDE_INT
, true> {};
1432 struct int_traits
<unsigned HOST_WIDE_INT
>
1433 : public primitive_int_traits
<unsigned HOST_WIDE_INT
, false> {};
1439 /* Stores HWI-sized integer VAL, treating it as having signedness SGN
1440 and precision PRECISION. */
1441 struct hwi_with_prec
1443 hwi_with_prec (HOST_WIDE_INT
, unsigned int, signop
);
1445 unsigned int precision
;
1449 hwi_with_prec
shwi (HOST_WIDE_INT
, unsigned int);
1450 hwi_with_prec
uhwi (unsigned HOST_WIDE_INT
, unsigned int);
1452 hwi_with_prec
minus_one (unsigned int);
1453 hwi_with_prec
zero (unsigned int);
1454 hwi_with_prec
one (unsigned int);
1455 hwi_with_prec
two (unsigned int);
1458 inline wi::hwi_with_prec::hwi_with_prec (HOST_WIDE_INT v
, unsigned int p
,
1460 : val (v
), precision (p
), sgn (s
)
1464 /* Return a signed integer that has value VAL and precision PRECISION. */
1465 inline wi::hwi_with_prec
1466 wi::shwi (HOST_WIDE_INT val
, unsigned int precision
)
1468 return hwi_with_prec (val
, precision
, SIGNED
);
1471 /* Return an unsigned integer that has value VAL and precision PRECISION. */
1472 inline wi::hwi_with_prec
1473 wi::uhwi (unsigned HOST_WIDE_INT val
, unsigned int precision
)
1475 return hwi_with_prec (val
, precision
, UNSIGNED
);
1478 /* Return a wide int of -1 with precision PRECISION. */
1479 inline wi::hwi_with_prec
1480 wi::minus_one (unsigned int precision
)
1482 return wi::shwi (-1, precision
);
1485 /* Return a wide int of 0 with precision PRECISION. */
1486 inline wi::hwi_with_prec
1487 wi::zero (unsigned int precision
)
1489 return wi::shwi (0, precision
);
1492 /* Return a wide int of 1 with precision PRECISION. */
1493 inline wi::hwi_with_prec
1494 wi::one (unsigned int precision
)
1496 return wi::shwi (1, precision
);
1499 /* Return a wide int of 2 with precision PRECISION. */
1500 inline wi::hwi_with_prec
1501 wi::two (unsigned int precision
)
1503 return wi::shwi (2, precision
);
1509 struct int_traits
<wi::hwi_with_prec
>
1511 static const enum precision_type precision_type
= VAR_PRECISION
;
1512 /* hwi_with_prec has an explicitly-given precision, rather than the
1513 precision of HOST_WIDE_INT. */
1514 static const bool host_dependent_precision
= false;
1515 static const bool is_sign_extended
= true;
1516 static unsigned int get_precision (const wi::hwi_with_prec
&);
1517 static wi::storage_ref
decompose (HOST_WIDE_INT
*, unsigned int,
1518 const wi::hwi_with_prec
&);
1523 wi::int_traits
<wi::hwi_with_prec
>::get_precision (const wi::hwi_with_prec
&x
)
1528 inline wi::storage_ref
1529 wi::int_traits
<wi::hwi_with_prec
>::
1530 decompose (HOST_WIDE_INT
*scratch
, unsigned int precision
,
1531 const wi::hwi_with_prec
&x
)
1533 gcc_checking_assert (precision
== x
.precision
);
1535 if (x
.sgn
== SIGNED
|| x
.val
>= 0 || precision
<= HOST_BITS_PER_WIDE_INT
)
1536 return wi::storage_ref (scratch
, 1, precision
);
1538 return wi::storage_ref (scratch
, 2, precision
);
1541 /* Private functions for handling large cases out of line. They take
1542 individual length and array parameters because that is cheaper for
1543 the inline caller than constructing an object on the stack and
1544 passing a reference to it. (Although many callers use wide_int_refs,
1545 we generally want those to be removed by SRA.) */
1548 bool eq_p_large (const HOST_WIDE_INT
*, unsigned int,
1549 const HOST_WIDE_INT
*, unsigned int, unsigned int);
1550 bool lts_p_large (const HOST_WIDE_INT
*, unsigned int, unsigned int,
1551 const HOST_WIDE_INT
*, unsigned int);
1552 bool ltu_p_large (const HOST_WIDE_INT
*, unsigned int, unsigned int,
1553 const HOST_WIDE_INT
*, unsigned int);
1554 int cmps_large (const HOST_WIDE_INT
*, unsigned int, unsigned int,
1555 const HOST_WIDE_INT
*, unsigned int);
1556 int cmpu_large (const HOST_WIDE_INT
*, unsigned int, unsigned int,
1557 const HOST_WIDE_INT
*, unsigned int);
1558 unsigned int sext_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1560 unsigned int, unsigned int);
1561 unsigned int zext_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1563 unsigned int, unsigned int);
1564 unsigned int set_bit_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1565 unsigned int, unsigned int, unsigned int);
1566 unsigned int lshift_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1567 unsigned int, unsigned int, unsigned int);
1568 unsigned int lrshift_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1569 unsigned int, unsigned int, unsigned int,
1571 unsigned int arshift_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1572 unsigned int, unsigned int, unsigned int,
1574 unsigned int and_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*, unsigned int,
1575 const HOST_WIDE_INT
*, unsigned int, unsigned int);
1576 unsigned int and_not_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1577 unsigned int, const HOST_WIDE_INT
*,
1578 unsigned int, unsigned int);
1579 unsigned int or_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*, unsigned int,
1580 const HOST_WIDE_INT
*, unsigned int, unsigned int);
1581 unsigned int or_not_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1582 unsigned int, const HOST_WIDE_INT
*,
1583 unsigned int, unsigned int);
1584 unsigned int xor_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*, unsigned int,
1585 const HOST_WIDE_INT
*, unsigned int, unsigned int);
1586 unsigned int add_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*, unsigned int,
1587 const HOST_WIDE_INT
*, unsigned int, unsigned int,
1589 unsigned int sub_large (HOST_WIDE_INT
*, const HOST_WIDE_INT
*, unsigned int,
1590 const HOST_WIDE_INT
*, unsigned int, unsigned int,
1592 unsigned int mul_internal (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1593 unsigned int, const HOST_WIDE_INT
*,
1594 unsigned int, unsigned int, signop
, bool *,
1596 unsigned int divmod_internal (HOST_WIDE_INT
*, unsigned int *,
1597 HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
1598 unsigned int, unsigned int,
1599 const HOST_WIDE_INT
*,
1600 unsigned int, unsigned int,
1604 /* Return the number of bits that integer X can hold. */
1605 template <typename T
>
1607 wi::get_precision (const T
&x
)
1609 return wi::int_traits
<T
>::get_precision (x
);
1612 /* Return the number of bits that the result of a binary operation can
1613 hold when the input operands are X and Y. */
1614 template <typename T1
, typename T2
>
1616 wi::get_binary_precision (const T1
&x
, const T2
&y
)
1618 return get_precision (wi::int_traits
<WI_BINARY_RESULT (T1
, T2
)>::
1619 get_binary_result (x
, y
));
1622 /* Copy the contents of Y to X, but keeping X's current precision. */
1623 template <typename T1
, typename T2
>
1625 wi::copy (T1
&x
, const T2
&y
)
1627 HOST_WIDE_INT
*xval
= x
.write_val ();
1628 const HOST_WIDE_INT
*yval
= y
.get_val ();
1629 unsigned int len
= y
.get_len ();
1634 x
.set_len (len
, y
.is_sign_extended
);
1637 /* Return true if X fits in a HOST_WIDE_INT with no loss of precision. */
1638 template <typename T
>
1640 wi::fits_shwi_p (const T
&x
)
1642 WIDE_INT_REF_FOR (T
) xi (x
);
1646 /* Return true if X fits in an unsigned HOST_WIDE_INT with no loss of
1648 template <typename T
>
1650 wi::fits_uhwi_p (const T
&x
)
1652 WIDE_INT_REF_FOR (T
) xi (x
);
1653 if (xi
.precision
<= HOST_BITS_PER_WIDE_INT
)
1656 return xi
.slow () >= 0;
1657 return xi
.len
== 2 && xi
.uhigh () == 0;
1660 /* Return true if X is negative based on the interpretation of SGN.
1661 For UNSIGNED, this is always false. */
1662 template <typename T
>
1664 wi::neg_p (const T
&x
, signop sgn
)
1666 WIDE_INT_REF_FOR (T
) xi (x
);
1667 if (sgn
== UNSIGNED
)
1669 return xi
.sign_mask () < 0;
1672 /* Return -1 if the top bit of X is set and 0 if the top bit is clear. */
1673 template <typename T
>
1674 inline HOST_WIDE_INT
1675 wi::sign_mask (const T
&x
)
1677 WIDE_INT_REF_FOR (T
) xi (x
);
1678 return xi
.sign_mask ();
1681 /* Return true if X == Y. X and Y must be binary-compatible. */
1682 template <typename T1
, typename T2
>
1684 wi::eq_p (const T1
&x
, const T2
&y
)
1686 unsigned int precision
= get_binary_precision (x
, y
);
1687 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
1688 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
1689 if (xi
.is_sign_extended
&& yi
.is_sign_extended
)
1691 /* This case reduces to array equality. */
1692 if (xi
.len
!= yi
.len
)
1696 if (xi
.val
[i
] != yi
.val
[i
])
1698 while (++i
!= xi
.len
);
1701 if (__builtin_expect (yi
.len
== 1, true))
1703 /* XI is only equal to YI if it too has a single HWI. */
1706 /* Excess bits in xi.val[0] will be signs or zeros, so comparisons
1707 with 0 are simple. */
1708 if (STATIC_CONSTANT_P (yi
.val
[0] == 0))
1709 return xi
.val
[0] == 0;
1710 /* Otherwise flush out any excess bits first. */
1711 unsigned HOST_WIDE_INT diff
= xi
.val
[0] ^ yi
.val
[0];
1712 int excess
= HOST_BITS_PER_WIDE_INT
- precision
;
1717 return eq_p_large (xi
.val
, xi
.len
, yi
.val
, yi
.len
, precision
);
1720 /* Return true if X != Y. X and Y must be binary-compatible. */
1721 template <typename T1
, typename T2
>
1723 wi::ne_p (const T1
&x
, const T2
&y
)
1725 return !eq_p (x
, y
);
1728 /* Return true if X < Y when both are treated as signed values. */
1729 template <typename T1
, typename T2
>
1731 wi::lts_p (const T1
&x
, const T2
&y
)
1733 unsigned int precision
= get_binary_precision (x
, y
);
1734 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
1735 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
1736 /* We optimize x < y, where y is 64 or fewer bits. */
1737 if (wi::fits_shwi_p (yi
))
1739 /* Make lts_p (x, 0) as efficient as wi::neg_p (x). */
1740 if (STATIC_CONSTANT_P (yi
.val
[0] == 0))
1742 /* If x fits directly into a shwi, we can compare directly. */
1743 if (wi::fits_shwi_p (xi
))
1744 return xi
.to_shwi () < yi
.to_shwi ();
1745 /* If x doesn't fit and is negative, then it must be more
1746 negative than any value in y, and hence smaller than y. */
1749 /* If x is positive, then it must be larger than any value in y,
1750 and hence greater than y. */
1753 /* Optimize the opposite case, if it can be detected at compile time. */
1754 if (STATIC_CONSTANT_P (xi
.len
== 1))
1755 /* If YI is negative it is lower than the least HWI.
1756 If YI is positive it is greater than the greatest HWI. */
1758 return lts_p_large (xi
.val
, xi
.len
, precision
, yi
.val
, yi
.len
);
1761 /* Return true if X < Y when both are treated as unsigned values. */
1762 template <typename T1
, typename T2
>
1764 wi::ltu_p (const T1
&x
, const T2
&y
)
1766 unsigned int precision
= get_binary_precision (x
, y
);
1767 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
1768 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
1769 /* Optimize comparisons with constants. */
1770 if (STATIC_CONSTANT_P (yi
.len
== 1 && yi
.val
[0] >= 0))
1771 return xi
.len
== 1 && xi
.to_uhwi () < (unsigned HOST_WIDE_INT
) yi
.val
[0];
1772 if (STATIC_CONSTANT_P (xi
.len
== 1 && xi
.val
[0] >= 0))
1773 return yi
.len
!= 1 || yi
.to_uhwi () > (unsigned HOST_WIDE_INT
) xi
.val
[0];
1774 /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
1775 for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
1776 values does not change the result. */
1777 if (__builtin_expect (xi
.len
+ yi
.len
== 2, true))
1779 unsigned HOST_WIDE_INT xl
= xi
.to_uhwi ();
1780 unsigned HOST_WIDE_INT yl
= yi
.to_uhwi ();
1783 return ltu_p_large (xi
.val
, xi
.len
, precision
, yi
.val
, yi
.len
);
1786 /* Return true if X < Y. Signedness of X and Y is indicated by SGN. */
1787 template <typename T1
, typename T2
>
1789 wi::lt_p (const T1
&x
, const T2
&y
, signop sgn
)
1792 return lts_p (x
, y
);
1794 return ltu_p (x
, y
);
1797 /* Return true if X <= Y when both are treated as signed values. */
1798 template <typename T1
, typename T2
>
1800 wi::les_p (const T1
&x
, const T2
&y
)
1802 return !lts_p (y
, x
);
1805 /* Return true if X <= Y when both are treated as unsigned values. */
1806 template <typename T1
, typename T2
>
1808 wi::leu_p (const T1
&x
, const T2
&y
)
1810 return !ltu_p (y
, x
);
1813 /* Return true if X <= Y. Signedness of X and Y is indicated by SGN. */
1814 template <typename T1
, typename T2
>
1816 wi::le_p (const T1
&x
, const T2
&y
, signop sgn
)
1819 return les_p (x
, y
);
1821 return leu_p (x
, y
);
1824 /* Return true if X > Y when both are treated as signed values. */
1825 template <typename T1
, typename T2
>
1827 wi::gts_p (const T1
&x
, const T2
&y
)
1829 return lts_p (y
, x
);
1832 /* Return true if X > Y when both are treated as unsigned values. */
1833 template <typename T1
, typename T2
>
1835 wi::gtu_p (const T1
&x
, const T2
&y
)
1837 return ltu_p (y
, x
);
1840 /* Return true if X > Y. Signedness of X and Y is indicated by SGN. */
1841 template <typename T1
, typename T2
>
1843 wi::gt_p (const T1
&x
, const T2
&y
, signop sgn
)
1846 return gts_p (x
, y
);
1848 return gtu_p (x
, y
);
1851 /* Return true if X >= Y when both are treated as signed values. */
1852 template <typename T1
, typename T2
>
1854 wi::ges_p (const T1
&x
, const T2
&y
)
1856 return !lts_p (x
, y
);
1859 /* Return true if X >= Y when both are treated as unsigned values. */
1860 template <typename T1
, typename T2
>
1862 wi::geu_p (const T1
&x
, const T2
&y
)
1864 return !ltu_p (x
, y
);
1867 /* Return true if X >= Y. Signedness of X and Y is indicated by SGN. */
1868 template <typename T1
, typename T2
>
1870 wi::ge_p (const T1
&x
, const T2
&y
, signop sgn
)
1873 return ges_p (x
, y
);
1875 return geu_p (x
, y
);
1878 /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
1879 as signed values. */
1880 template <typename T1
, typename T2
>
1882 wi::cmps (const T1
&x
, const T2
&y
)
1884 unsigned int precision
= get_binary_precision (x
, y
);
1885 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
1886 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
1887 if (wi::fits_shwi_p (yi
))
1889 /* Special case for comparisons with 0. */
1890 if (STATIC_CONSTANT_P (yi
.val
[0] == 0))
1891 return neg_p (xi
) ? -1 : !(xi
.len
== 1 && xi
.val
[0] == 0);
1892 /* If x fits into a signed HWI, we can compare directly. */
1893 if (wi::fits_shwi_p (xi
))
1895 HOST_WIDE_INT xl
= xi
.to_shwi ();
1896 HOST_WIDE_INT yl
= yi
.to_shwi ();
1897 return xl
< yl
? -1 : xl
> yl
;
1899 /* If x doesn't fit and is negative, then it must be more
1900 negative than any signed HWI, and hence smaller than y. */
1903 /* If x is positive, then it must be larger than any signed HWI,
1904 and hence greater than y. */
1907 /* Optimize the opposite case, if it can be detected at compile time. */
1908 if (STATIC_CONSTANT_P (xi
.len
== 1))
1909 /* If YI is negative it is lower than the least HWI.
1910 If YI is positive it is greater than the greatest HWI. */
1911 return neg_p (yi
) ? 1 : -1;
1912 return cmps_large (xi
.val
, xi
.len
, precision
, yi
.val
, yi
.len
);
1915 /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
1916 as unsigned values. */
1917 template <typename T1
, typename T2
>
1919 wi::cmpu (const T1
&x
, const T2
&y
)
1921 unsigned int precision
= get_binary_precision (x
, y
);
1922 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
1923 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
1924 /* Optimize comparisons with constants. */
1925 if (STATIC_CONSTANT_P (yi
.len
== 1 && yi
.val
[0] >= 0))
1927 /* If XI doesn't fit in a HWI then it must be larger than YI. */
1930 /* Otherwise compare directly. */
1931 unsigned HOST_WIDE_INT xl
= xi
.to_uhwi ();
1932 unsigned HOST_WIDE_INT yl
= yi
.val
[0];
1933 return xl
< yl
? -1 : xl
> yl
;
1935 if (STATIC_CONSTANT_P (xi
.len
== 1 && xi
.val
[0] >= 0))
1937 /* If YI doesn't fit in a HWI then it must be larger than XI. */
1940 /* Otherwise compare directly. */
1941 unsigned HOST_WIDE_INT xl
= xi
.val
[0];
1942 unsigned HOST_WIDE_INT yl
= yi
.to_uhwi ();
1943 return xl
< yl
? -1 : xl
> yl
;
1945 /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
1946 for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
1947 values does not change the result. */
1948 if (__builtin_expect (xi
.len
+ yi
.len
== 2, true))
1950 unsigned HOST_WIDE_INT xl
= xi
.to_uhwi ();
1951 unsigned HOST_WIDE_INT yl
= yi
.to_uhwi ();
1952 return xl
< yl
? -1 : xl
> yl
;
1954 return cmpu_large (xi
.val
, xi
.len
, precision
, yi
.val
, yi
.len
);
1957 /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Signedness of
1958 X and Y indicated by SGN. */
1959 template <typename T1
, typename T2
>
1961 wi::cmp (const T1
&x
, const T2
&y
, signop sgn
)
1970 template <typename T
>
1971 inline WI_UNARY_RESULT (T
)
1972 wi::bit_not (const T
&x
)
1974 WI_UNARY_RESULT_VAR (result
, val
, T
, x
);
1975 WIDE_INT_REF_FOR (T
) xi (x
, get_precision (result
));
1976 for (unsigned int i
= 0; i
< xi
.len
; ++i
)
1977 val
[i
] = ~xi
.val
[i
];
1978 result
.set_len (xi
.len
);
1983 template <typename T
>
1984 inline WI_UNARY_RESULT (T
)
1985 wi::neg (const T
&x
)
1990 /* Return -x. Indicate in *OVERFLOW if X is the minimum signed value. */
1991 template <typename T
>
1992 inline WI_UNARY_RESULT (T
)
1993 wi::neg (const T
&x
, bool *overflow
)
1995 *overflow
= only_sign_bit_p (x
);
1999 /* Return the absolute value of x. */
2000 template <typename T
>
2001 inline WI_UNARY_RESULT (T
)
2002 wi::abs (const T
&x
)
2004 return neg_p (x
) ? neg (x
) : WI_UNARY_RESULT (T
) (x
);
2007 /* Return the result of sign-extending the low OFFSET bits of X. */
2008 template <typename T
>
2009 inline WI_UNARY_RESULT (T
)
2010 wi::sext (const T
&x
, unsigned int offset
)
2012 WI_UNARY_RESULT_VAR (result
, val
, T
, x
);
2013 unsigned int precision
= get_precision (result
);
2014 WIDE_INT_REF_FOR (T
) xi (x
, precision
);
2016 if (offset
<= HOST_BITS_PER_WIDE_INT
)
2018 val
[0] = sext_hwi (xi
.ulow (), offset
);
2019 result
.set_len (1, true);
2022 result
.set_len (sext_large (val
, xi
.val
, xi
.len
, precision
, offset
));
2026 /* Return the result of zero-extending the low OFFSET bits of X. */
2027 template <typename T
>
2028 inline WI_UNARY_RESULT (T
)
2029 wi::zext (const T
&x
, unsigned int offset
)
2031 WI_UNARY_RESULT_VAR (result
, val
, T
, x
);
2032 unsigned int precision
= get_precision (result
);
2033 WIDE_INT_REF_FOR (T
) xi (x
, precision
);
2035 /* This is not just an optimization, it is actually required to
2036 maintain canonization. */
2037 if (offset
>= precision
)
2039 wi::copy (result
, xi
);
2043 /* In these cases we know that at least the top bit will be clear,
2044 so no sign extension is necessary. */
2045 if (offset
< HOST_BITS_PER_WIDE_INT
)
2047 val
[0] = zext_hwi (xi
.ulow (), offset
);
2048 result
.set_len (1, true);
2051 result
.set_len (zext_large (val
, xi
.val
, xi
.len
, precision
, offset
), true);
2055 /* Return the result of extending the low OFFSET bits of X according to
2057 template <typename T
>
2058 inline WI_UNARY_RESULT (T
)
2059 wi::ext (const T
&x
, unsigned int offset
, signop sgn
)
2061 return sgn
== SIGNED
? sext (x
, offset
) : zext (x
, offset
);
2064 /* Return an integer that represents X | (1 << bit). */
2065 template <typename T
>
2066 inline WI_UNARY_RESULT (T
)
2067 wi::set_bit (const T
&x
, unsigned int bit
)
2069 WI_UNARY_RESULT_VAR (result
, val
, T
, x
);
2070 unsigned int precision
= get_precision (result
);
2071 WIDE_INT_REF_FOR (T
) xi (x
, precision
);
2072 if (precision
<= HOST_BITS_PER_WIDE_INT
)
2074 val
[0] = xi
.ulow () | ((unsigned HOST_WIDE_INT
) 1 << bit
);
2078 result
.set_len (set_bit_large (val
, xi
.val
, xi
.len
, precision
, bit
));
2082 /* Return the mininum of X and Y, treating them both as having
2084 template <typename T1
, typename T2
>
2085 inline WI_BINARY_RESULT (T1
, T2
)
2086 wi::min (const T1
&x
, const T2
&y
, signop sgn
)
2088 WI_BINARY_RESULT_VAR (result
, val ATTRIBUTE_UNUSED
, T1
, x
, T2
, y
);
2089 unsigned int precision
= get_precision (result
);
2090 if (wi::le_p (x
, y
, sgn
))
2091 wi::copy (result
, WIDE_INT_REF_FOR (T1
) (x
, precision
));
2093 wi::copy (result
, WIDE_INT_REF_FOR (T2
) (y
, precision
));
2097 /* Return the minimum of X and Y, treating both as signed values. */
2098 template <typename T1
, typename T2
>
2099 inline WI_BINARY_RESULT (T1
, T2
)
2100 wi::smin (const T1
&x
, const T2
&y
)
2102 return min (x
, y
, SIGNED
);
2105 /* Return the minimum of X and Y, treating both as unsigned values. */
2106 template <typename T1
, typename T2
>
2107 inline WI_BINARY_RESULT (T1
, T2
)
2108 wi::umin (const T1
&x
, const T2
&y
)
2110 return min (x
, y
, UNSIGNED
);
2113 /* Return the maxinum of X and Y, treating them both as having
2115 template <typename T1
, typename T2
>
2116 inline WI_BINARY_RESULT (T1
, T2
)
2117 wi::max (const T1
&x
, const T2
&y
, signop sgn
)
2119 WI_BINARY_RESULT_VAR (result
, val ATTRIBUTE_UNUSED
, T1
, x
, T2
, y
);
2120 unsigned int precision
= get_precision (result
);
2121 if (wi::ge_p (x
, y
, sgn
))
2122 wi::copy (result
, WIDE_INT_REF_FOR (T1
) (x
, precision
));
2124 wi::copy (result
, WIDE_INT_REF_FOR (T2
) (y
, precision
));
2128 /* Return the maximum of X and Y, treating both as signed values. */
2129 template <typename T1
, typename T2
>
2130 inline WI_BINARY_RESULT (T1
, T2
)
2131 wi::smax (const T1
&x
, const T2
&y
)
2133 return max (x
, y
, SIGNED
);
2136 /* Return the maximum of X and Y, treating both as unsigned values. */
2137 template <typename T1
, typename T2
>
2138 inline WI_BINARY_RESULT (T1
, T2
)
2139 wi::umax (const T1
&x
, const T2
&y
)
2141 return max (x
, y
, UNSIGNED
);
2145 template <typename T1
, typename T2
>
2146 inline WI_BINARY_RESULT (T1
, T2
)
2147 wi::bit_and (const T1
&x
, const T2
&y
)
2149 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2150 unsigned int precision
= get_precision (result
);
2151 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2152 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2153 bool is_sign_extended
= xi
.is_sign_extended
&& yi
.is_sign_extended
;
2154 if (__builtin_expect (xi
.len
+ yi
.len
== 2, true))
2156 val
[0] = xi
.ulow () & yi
.ulow ();
2157 result
.set_len (1, is_sign_extended
);
2160 result
.set_len (and_large (val
, xi
.val
, xi
.len
, yi
.val
, yi
.len
,
2161 precision
), is_sign_extended
);
2165 /* Return X & ~Y. */
2166 template <typename T1
, typename T2
>
2167 inline WI_BINARY_RESULT (T1
, T2
)
2168 wi::bit_and_not (const T1
&x
, const T2
&y
)
2170 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2171 unsigned int precision
= get_precision (result
);
2172 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2173 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2174 bool is_sign_extended
= xi
.is_sign_extended
&& yi
.is_sign_extended
;
2175 if (__builtin_expect (xi
.len
+ yi
.len
== 2, true))
2177 val
[0] = xi
.ulow () & ~yi
.ulow ();
2178 result
.set_len (1, is_sign_extended
);
2181 result
.set_len (and_not_large (val
, xi
.val
, xi
.len
, yi
.val
, yi
.len
,
2182 precision
), is_sign_extended
);
2187 template <typename T1
, typename T2
>
2188 inline WI_BINARY_RESULT (T1
, T2
)
2189 wi::bit_or (const T1
&x
, const T2
&y
)
2191 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2192 unsigned int precision
= get_precision (result
);
2193 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2194 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2195 bool is_sign_extended
= xi
.is_sign_extended
&& yi
.is_sign_extended
;
2196 if (__builtin_expect (xi
.len
+ yi
.len
== 2, true))
2198 val
[0] = xi
.ulow () | yi
.ulow ();
2199 result
.set_len (1, is_sign_extended
);
2202 result
.set_len (or_large (val
, xi
.val
, xi
.len
,
2203 yi
.val
, yi
.len
, precision
), is_sign_extended
);
2207 /* Return X | ~Y. */
2208 template <typename T1
, typename T2
>
2209 inline WI_BINARY_RESULT (T1
, T2
)
2210 wi::bit_or_not (const T1
&x
, const T2
&y
)
2212 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2213 unsigned int precision
= get_precision (result
);
2214 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2215 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2216 bool is_sign_extended
= xi
.is_sign_extended
&& yi
.is_sign_extended
;
2217 if (__builtin_expect (xi
.len
+ yi
.len
== 2, true))
2219 val
[0] = xi
.ulow () | ~yi
.ulow ();
2220 result
.set_len (1, is_sign_extended
);
2223 result
.set_len (or_not_large (val
, xi
.val
, xi
.len
, yi
.val
, yi
.len
,
2224 precision
), is_sign_extended
);
2229 template <typename T1
, typename T2
>
2230 inline WI_BINARY_RESULT (T1
, T2
)
2231 wi::bit_xor (const T1
&x
, const T2
&y
)
2233 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2234 unsigned int precision
= get_precision (result
);
2235 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2236 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2237 bool is_sign_extended
= xi
.is_sign_extended
&& yi
.is_sign_extended
;
2238 if (__builtin_expect (xi
.len
+ yi
.len
== 2, true))
2240 val
[0] = xi
.ulow () ^ yi
.ulow ();
2241 result
.set_len (1, is_sign_extended
);
2244 result
.set_len (xor_large (val
, xi
.val
, xi
.len
,
2245 yi
.val
, yi
.len
, precision
), is_sign_extended
);
2250 template <typename T1
, typename T2
>
2251 inline WI_BINARY_RESULT (T1
, T2
)
2252 wi::add (const T1
&x
, const T2
&y
)
2254 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2255 unsigned int precision
= get_precision (result
);
2256 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2257 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2258 if (precision
<= HOST_BITS_PER_WIDE_INT
)
2260 val
[0] = xi
.ulow () + yi
.ulow ();
2263 /* If the precision is known at compile time to be greater than
2264 HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2265 knowing that (a) all bits in those HWIs are significant and
2266 (b) the result has room for at least two HWIs. This provides
2267 a fast path for things like offset_int and widest_int.
2269 The STATIC_CONSTANT_P test prevents this path from being
2270 used for wide_ints. wide_ints with precisions greater than
2271 HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2272 point handling them inline. */
2273 else if (STATIC_CONSTANT_P (precision
> HOST_BITS_PER_WIDE_INT
)
2274 && __builtin_expect (xi
.len
+ yi
.len
== 2, true))
2276 unsigned HOST_WIDE_INT xl
= xi
.ulow ();
2277 unsigned HOST_WIDE_INT yl
= yi
.ulow ();
2278 unsigned HOST_WIDE_INT resultl
= xl
+ yl
;
2280 val
[1] = (HOST_WIDE_INT
) resultl
< 0 ? 0 : -1;
2281 result
.set_len (1 + (((resultl
^ xl
) & (resultl
^ yl
))
2282 >> (HOST_BITS_PER_WIDE_INT
- 1)));
2285 result
.set_len (add_large (val
, xi
.val
, xi
.len
,
2286 yi
.val
, yi
.len
, precision
,
2291 /* Return X + Y. Treat X and Y as having the signednes given by SGN
2292 and indicate in *OVERFLOW whether the operation overflowed. */
2293 template <typename T1
, typename T2
>
2294 inline WI_BINARY_RESULT (T1
, T2
)
2295 wi::add (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2297 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2298 unsigned int precision
= get_precision (result
);
2299 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2300 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2301 if (precision
<= HOST_BITS_PER_WIDE_INT
)
2303 unsigned HOST_WIDE_INT xl
= xi
.ulow ();
2304 unsigned HOST_WIDE_INT yl
= yi
.ulow ();
2305 unsigned HOST_WIDE_INT resultl
= xl
+ yl
;
2307 *overflow
= (((resultl
^ xl
) & (resultl
^ yl
))
2308 >> (precision
- 1)) & 1;
2310 *overflow
= ((resultl
<< (HOST_BITS_PER_WIDE_INT
- precision
))
2311 < (xl
<< (HOST_BITS_PER_WIDE_INT
- precision
)));
2316 result
.set_len (add_large (val
, xi
.val
, xi
.len
,
2317 yi
.val
, yi
.len
, precision
,
2323 template <typename T1
, typename T2
>
2324 inline WI_BINARY_RESULT (T1
, T2
)
2325 wi::sub (const T1
&x
, const T2
&y
)
2327 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2328 unsigned int precision
= get_precision (result
);
2329 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2330 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2331 if (precision
<= HOST_BITS_PER_WIDE_INT
)
2333 val
[0] = xi
.ulow () - yi
.ulow ();
2336 /* If the precision is known at compile time to be greater than
2337 HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2338 knowing that (a) all bits in those HWIs are significant and
2339 (b) the result has room for at least two HWIs. This provides
2340 a fast path for things like offset_int and widest_int.
2342 The STATIC_CONSTANT_P test prevents this path from being
2343 used for wide_ints. wide_ints with precisions greater than
2344 HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2345 point handling them inline. */
2346 else if (STATIC_CONSTANT_P (precision
> HOST_BITS_PER_WIDE_INT
)
2347 && __builtin_expect (xi
.len
+ yi
.len
== 2, true))
2349 unsigned HOST_WIDE_INT xl
= xi
.ulow ();
2350 unsigned HOST_WIDE_INT yl
= yi
.ulow ();
2351 unsigned HOST_WIDE_INT resultl
= xl
- yl
;
2353 val
[1] = (HOST_WIDE_INT
) resultl
< 0 ? 0 : -1;
2354 result
.set_len (1 + (((resultl
^ xl
) & (xl
^ yl
))
2355 >> (HOST_BITS_PER_WIDE_INT
- 1)));
2358 result
.set_len (sub_large (val
, xi
.val
, xi
.len
,
2359 yi
.val
, yi
.len
, precision
,
2364 /* Return X - Y. Treat X and Y as having the signednes given by SGN
2365 and indicate in *OVERFLOW whether the operation overflowed. */
2366 template <typename T1
, typename T2
>
2367 inline WI_BINARY_RESULT (T1
, T2
)
2368 wi::sub (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2370 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2371 unsigned int precision
= get_precision (result
);
2372 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2373 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2374 if (precision
<= HOST_BITS_PER_WIDE_INT
)
2376 unsigned HOST_WIDE_INT xl
= xi
.ulow ();
2377 unsigned HOST_WIDE_INT yl
= yi
.ulow ();
2378 unsigned HOST_WIDE_INT resultl
= xl
- yl
;
2380 *overflow
= (((xl
^ yl
) & (resultl
^ xl
)) >> (precision
- 1)) & 1;
2382 *overflow
= ((resultl
<< (HOST_BITS_PER_WIDE_INT
- precision
))
2383 > (xl
<< (HOST_BITS_PER_WIDE_INT
- precision
)));
2388 result
.set_len (sub_large (val
, xi
.val
, xi
.len
,
2389 yi
.val
, yi
.len
, precision
,
2395 template <typename T1
, typename T2
>
2396 inline WI_BINARY_RESULT (T1
, T2
)
2397 wi::mul (const T1
&x
, const T2
&y
)
2399 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2400 unsigned int precision
= get_precision (result
);
2401 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2402 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2403 if (precision
<= HOST_BITS_PER_WIDE_INT
)
2405 val
[0] = xi
.ulow () * yi
.ulow ();
2409 result
.set_len (mul_internal (val
, xi
.val
, xi
.len
, yi
.val
, yi
.len
,
2410 precision
, UNSIGNED
, 0, false));
2414 /* Return X * Y. Treat X and Y as having the signednes given by SGN
2415 and indicate in *OVERFLOW whether the operation overflowed. */
2416 template <typename T1
, typename T2
>
2417 inline WI_BINARY_RESULT (T1
, T2
)
2418 wi::mul (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2420 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2421 unsigned int precision
= get_precision (result
);
2422 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2423 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2424 result
.set_len (mul_internal (val
, xi
.val
, xi
.len
,
2425 yi
.val
, yi
.len
, precision
,
2426 sgn
, overflow
, false));
2430 /* Return X * Y, treating both X and Y as signed values. Indicate in
2431 *OVERFLOW whether the operation overflowed. */
2432 template <typename T1
, typename T2
>
2433 inline WI_BINARY_RESULT (T1
, T2
)
2434 wi::smul (const T1
&x
, const T2
&y
, bool *overflow
)
2436 return mul (x
, y
, SIGNED
, overflow
);
2439 /* Return X * Y, treating both X and Y as unsigned values. Indicate in
2440 *OVERFLOW whether the operation overflowed. */
2441 template <typename T1
, typename T2
>
2442 inline WI_BINARY_RESULT (T1
, T2
)
2443 wi::umul (const T1
&x
, const T2
&y
, bool *overflow
)
2445 return mul (x
, y
, UNSIGNED
, overflow
);
2448 /* Perform a widening multiplication of X and Y, extending the values
2449 according to SGN, and return the high part of the result. */
2450 template <typename T1
, typename T2
>
2451 inline WI_BINARY_RESULT (T1
, T2
)
2452 wi::mul_high (const T1
&x
, const T2
&y
, signop sgn
)
2454 WI_BINARY_RESULT_VAR (result
, val
, T1
, x
, T2
, y
);
2455 unsigned int precision
= get_precision (result
);
2456 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2457 WIDE_INT_REF_FOR (T2
) yi (y
, precision
);
2458 result
.set_len (mul_internal (val
, xi
.val
, xi
.len
,
2459 yi
.val
, yi
.len
, precision
,
2464 /* Return X / Y, rouding towards 0. Treat X and Y as having the
2465 signedness given by SGN. Indicate in *OVERFLOW if the result
2467 template <typename T1
, typename T2
>
2468 inline WI_BINARY_RESULT (T1
, T2
)
2469 wi::div_trunc (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2471 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2472 unsigned int precision
= get_precision (quotient
);
2473 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2474 WIDE_INT_REF_FOR (T2
) yi (y
);
2476 quotient
.set_len (divmod_internal (quotient_val
, 0, 0, xi
.val
, xi
.len
,
2478 yi
.val
, yi
.len
, yi
.precision
,
2483 /* Return X / Y, rouding towards 0. Treat X and Y as signed values. */
2484 template <typename T1
, typename T2
>
2485 inline WI_BINARY_RESULT (T1
, T2
)
2486 wi::sdiv_trunc (const T1
&x
, const T2
&y
)
2488 return div_trunc (x
, y
, SIGNED
);
2491 /* Return X / Y, rouding towards 0. Treat X and Y as unsigned values. */
2492 template <typename T1
, typename T2
>
2493 inline WI_BINARY_RESULT (T1
, T2
)
2494 wi::udiv_trunc (const T1
&x
, const T2
&y
)
2496 return div_trunc (x
, y
, UNSIGNED
);
2499 /* Return X / Y, rouding towards -inf. Treat X and Y as having the
2500 signedness given by SGN. Indicate in *OVERFLOW if the result
2502 template <typename T1
, typename T2
>
2503 inline WI_BINARY_RESULT (T1
, T2
)
2504 wi::div_floor (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2506 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2507 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2508 unsigned int precision
= get_precision (quotient
);
2509 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2510 WIDE_INT_REF_FOR (T2
) yi (y
);
2512 unsigned int remainder_len
;
2513 quotient
.set_len (divmod_internal (quotient_val
,
2514 &remainder_len
, remainder_val
,
2515 xi
.val
, xi
.len
, precision
,
2516 yi
.val
, yi
.len
, yi
.precision
, sgn
,
2518 remainder
.set_len (remainder_len
);
2519 if (wi::neg_p (x
, sgn
) != wi::neg_p (y
, sgn
) && remainder
!= 0)
2520 return quotient
- 1;
2524 /* Return X / Y, rouding towards -inf. Treat X and Y as signed values. */
2525 template <typename T1
, typename T2
>
2526 inline WI_BINARY_RESULT (T1
, T2
)
2527 wi::sdiv_floor (const T1
&x
, const T2
&y
)
2529 return div_floor (x
, y
, SIGNED
);
2532 /* Return X / Y, rouding towards -inf. Treat X and Y as unsigned values. */
2533 /* ??? Why do we have both this and udiv_trunc. Aren't they the same? */
2534 template <typename T1
, typename T2
>
2535 inline WI_BINARY_RESULT (T1
, T2
)
2536 wi::udiv_floor (const T1
&x
, const T2
&y
)
2538 return div_floor (x
, y
, UNSIGNED
);
2541 /* Return X / Y, rouding towards +inf. Treat X and Y as having the
2542 signedness given by SGN. Indicate in *OVERFLOW if the result
2544 template <typename T1
, typename T2
>
2545 inline WI_BINARY_RESULT (T1
, T2
)
2546 wi::div_ceil (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2548 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2549 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2550 unsigned int precision
= get_precision (quotient
);
2551 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2552 WIDE_INT_REF_FOR (T2
) yi (y
);
2554 unsigned int remainder_len
;
2555 quotient
.set_len (divmod_internal (quotient_val
,
2556 &remainder_len
, remainder_val
,
2557 xi
.val
, xi
.len
, precision
,
2558 yi
.val
, yi
.len
, yi
.precision
, sgn
,
2560 remainder
.set_len (remainder_len
);
2561 if (wi::neg_p (x
, sgn
) == wi::neg_p (y
, sgn
) && remainder
!= 0)
2562 return quotient
+ 1;
2566 /* Return X / Y, rouding towards nearest with ties away from zero.
2567 Treat X and Y as having the signedness given by SGN. Indicate
2568 in *OVERFLOW if the result overflows. */
2569 template <typename T1
, typename T2
>
2570 inline WI_BINARY_RESULT (T1
, T2
)
2571 wi::div_round (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2573 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2574 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2575 unsigned int precision
= get_precision (quotient
);
2576 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2577 WIDE_INT_REF_FOR (T2
) yi (y
);
2579 unsigned int remainder_len
;
2580 quotient
.set_len (divmod_internal (quotient_val
,
2581 &remainder_len
, remainder_val
,
2582 xi
.val
, xi
.len
, precision
,
2583 yi
.val
, yi
.len
, yi
.precision
, sgn
,
2585 remainder
.set_len (remainder_len
);
2591 if (wi::ges_p (wi::abs (remainder
),
2592 wi::lrshift (wi::abs (y
), 1)))
2594 if (wi::neg_p (x
, sgn
) != wi::neg_p (y
, sgn
))
2595 return quotient
- 1;
2597 return quotient
+ 1;
2602 if (wi::geu_p (remainder
, wi::lrshift (y
, 1)))
2603 return quotient
+ 1;
2609 /* Return X / Y, rouding towards 0. Treat X and Y as having the
2610 signedness given by SGN. Store the remainder in *REMAINDER_PTR. */
2611 template <typename T1
, typename T2
>
2612 inline WI_BINARY_RESULT (T1
, T2
)
2613 wi::divmod_trunc (const T1
&x
, const T2
&y
, signop sgn
,
2614 WI_BINARY_RESULT (T1
, T2
) *remainder_ptr
)
2616 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2617 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2618 unsigned int precision
= get_precision (quotient
);
2619 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2620 WIDE_INT_REF_FOR (T2
) yi (y
);
2622 unsigned int remainder_len
;
2623 quotient
.set_len (divmod_internal (quotient_val
,
2624 &remainder_len
, remainder_val
,
2625 xi
.val
, xi
.len
, precision
,
2626 yi
.val
, yi
.len
, yi
.precision
, sgn
, 0));
2627 remainder
.set_len (remainder_len
);
2629 *remainder_ptr
= remainder
;
2633 /* Compute X / Y, rouding towards 0, and return the remainder.
2634 Treat X and Y as having the signedness given by SGN. Indicate
2635 in *OVERFLOW if the division overflows. */
2636 template <typename T1
, typename T2
>
2637 inline WI_BINARY_RESULT (T1
, T2
)
2638 wi::mod_trunc (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2640 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2641 unsigned int precision
= get_precision (remainder
);
2642 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2643 WIDE_INT_REF_FOR (T2
) yi (y
);
2645 unsigned int remainder_len
;
2646 divmod_internal (0, &remainder_len
, remainder_val
,
2647 xi
.val
, xi
.len
, precision
,
2648 yi
.val
, yi
.len
, yi
.precision
, sgn
, overflow
);
2649 remainder
.set_len (remainder_len
);
2654 /* Compute X / Y, rouding towards 0, and return the remainder.
2655 Treat X and Y as signed values. */
2656 template <typename T1
, typename T2
>
2657 inline WI_BINARY_RESULT (T1
, T2
)
2658 wi::smod_trunc (const T1
&x
, const T2
&y
)
2660 return mod_trunc (x
, y
, SIGNED
);
2663 /* Compute X / Y, rouding towards 0, and return the remainder.
2664 Treat X and Y as unsigned values. */
2665 template <typename T1
, typename T2
>
2666 inline WI_BINARY_RESULT (T1
, T2
)
2667 wi::umod_trunc (const T1
&x
, const T2
&y
)
2669 return mod_trunc (x
, y
, UNSIGNED
);
2672 /* Compute X / Y, rouding towards -inf, and return the remainder.
2673 Treat X and Y as having the signedness given by SGN. Indicate
2674 in *OVERFLOW if the division overflows. */
2675 template <typename T1
, typename T2
>
2676 inline WI_BINARY_RESULT (T1
, T2
)
2677 wi::mod_floor (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2679 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2680 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2681 unsigned int precision
= get_precision (quotient
);
2682 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2683 WIDE_INT_REF_FOR (T2
) yi (y
);
2685 unsigned int remainder_len
;
2686 quotient
.set_len (divmod_internal (quotient_val
,
2687 &remainder_len
, remainder_val
,
2688 xi
.val
, xi
.len
, precision
,
2689 yi
.val
, yi
.len
, yi
.precision
, sgn
,
2691 remainder
.set_len (remainder_len
);
2693 if (wi::neg_p (x
, sgn
) != wi::neg_p (y
, sgn
) && remainder
!= 0)
2694 return remainder
+ y
;
2698 /* Compute X / Y, rouding towards -inf, and return the remainder.
2699 Treat X and Y as unsigned values. */
2700 /* ??? Why do we have both this and umod_trunc. Aren't they the same? */
2701 template <typename T1
, typename T2
>
2702 inline WI_BINARY_RESULT (T1
, T2
)
2703 wi::umod_floor (const T1
&x
, const T2
&y
)
2705 return mod_floor (x
, y
, UNSIGNED
);
2708 /* Compute X / Y, rouding towards +inf, and return the remainder.
2709 Treat X and Y as having the signedness given by SGN. Indicate
2710 in *OVERFLOW if the division overflows. */
2711 template <typename T1
, typename T2
>
2712 inline WI_BINARY_RESULT (T1
, T2
)
2713 wi::mod_ceil (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2715 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2716 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2717 unsigned int precision
= get_precision (quotient
);
2718 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2719 WIDE_INT_REF_FOR (T2
) yi (y
);
2721 unsigned int remainder_len
;
2722 quotient
.set_len (divmod_internal (quotient_val
,
2723 &remainder_len
, remainder_val
,
2724 xi
.val
, xi
.len
, precision
,
2725 yi
.val
, yi
.len
, yi
.precision
, sgn
,
2727 remainder
.set_len (remainder_len
);
2729 if (wi::neg_p (x
, sgn
) == wi::neg_p (y
, sgn
) && remainder
!= 0)
2730 return remainder
- y
;
2734 /* Compute X / Y, rouding towards nearest with ties away from zero,
2735 and return the remainder. Treat X and Y as having the signedness
2736 given by SGN. Indicate in *OVERFLOW if the division overflows. */
2737 template <typename T1
, typename T2
>
2738 inline WI_BINARY_RESULT (T1
, T2
)
2739 wi::mod_round (const T1
&x
, const T2
&y
, signop sgn
, bool *overflow
)
2741 WI_BINARY_RESULT_VAR (quotient
, quotient_val
, T1
, x
, T2
, y
);
2742 WI_BINARY_RESULT_VAR (remainder
, remainder_val
, T1
, x
, T2
, y
);
2743 unsigned int precision
= get_precision (quotient
);
2744 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2745 WIDE_INT_REF_FOR (T2
) yi (y
);
2747 unsigned int remainder_len
;
2748 quotient
.set_len (divmod_internal (quotient_val
,
2749 &remainder_len
, remainder_val
,
2750 xi
.val
, xi
.len
, precision
,
2751 yi
.val
, yi
.len
, yi
.precision
, sgn
,
2753 remainder
.set_len (remainder_len
);
2759 if (wi::ges_p (wi::abs (remainder
),
2760 wi::lrshift (wi::abs (y
), 1)))
2762 if (wi::neg_p (x
, sgn
) != wi::neg_p (y
, sgn
))
2763 return remainder
+ y
;
2765 return remainder
- y
;
2770 if (wi::geu_p (remainder
, wi::lrshift (y
, 1)))
2771 return remainder
- y
;
2777 /* Return true if X is a multiple of Y, storing X / Y in *RES if so.
2778 Treat X and Y as having the signedness given by SGN. */
2779 template <typename T1
, typename T2
>
2781 wi::multiple_of_p (const T1
&x
, const T2
&y
, signop sgn
,
2782 WI_BINARY_RESULT (T1
, T2
) *res
)
2784 WI_BINARY_RESULT (T1
, T2
) remainder
;
2785 WI_BINARY_RESULT (T1
, T2
) quotient
2786 = divmod_trunc (x
, y
, sgn
, &remainder
);
2795 /* Return X << Y. Return 0 if Y is greater than or equal to
2796 the precision of X. */
2797 template <typename T1
, typename T2
>
2798 inline WI_UNARY_RESULT (T1
)
2799 wi::lshift (const T1
&x
, const T2
&y
)
2801 WI_UNARY_RESULT_VAR (result
, val
, T1
, x
);
2802 unsigned int precision
= get_precision (result
);
2803 WIDE_INT_REF_FOR (T1
) xi (x
, precision
);
2804 WIDE_INT_REF_FOR (T2
) yi (y
);
2805 /* Handle the simple cases quickly. */
2806 if (geu_p (yi
, precision
))
2813 unsigned int shift
= yi
.to_uhwi ();
2814 /* For fixed-precision integers like offset_int and widest_int,
2815 handle the case where the shift value is constant and the
2816 result is a single nonnegative HWI (meaning that we don't
2817 need to worry about val[1]). This is particularly common
2818 for converting a byte count to a bit count.
2820 For variable-precision integers like wide_int, handle HWI
2821 and sub-HWI integers inline. */
2822 if (STATIC_CONSTANT_P (xi
.precision
> HOST_BITS_PER_WIDE_INT
)
2823 ? (STATIC_CONSTANT_P (shift
< HOST_BITS_PER_WIDE_INT
- 1)
2825 && xi
.val
[0] <= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
)
2826 HOST_WIDE_INT_MAX
>> shift
))
2827 : precision
<= HOST_BITS_PER_WIDE_INT
)
2829 val
[0] = xi
.ulow () << shift
;
2833 result
.set_len (lshift_large (val
, xi
.val
, xi
.len
,
2839 /* Return X >> Y, using a logical shift. Return 0 if Y is greater than
2840 or equal to the precision of X. */
2841 template <typename T1
, typename T2
>
2842 inline WI_UNARY_RESULT (T1
)
2843 wi::lrshift (const T1
&x
, const T2
&y
)
2845 WI_UNARY_RESULT_VAR (result
, val
, T1
, x
);
2846 /* Do things in the precision of the input rather than the output,
2847 since the result can be no larger than that. */
2848 WIDE_INT_REF_FOR (T1
) xi (x
);
2849 WIDE_INT_REF_FOR (T2
) yi (y
);
2850 /* Handle the simple cases quickly. */
2851 if (geu_p (yi
, xi
.precision
))
2858 unsigned int shift
= yi
.to_uhwi ();
2859 /* For fixed-precision integers like offset_int and widest_int,
2860 handle the case where the shift value is constant and the
2861 shifted value is a single nonnegative HWI (meaning that all
2862 bits above the HWI are zero). This is particularly common
2863 for converting a bit count to a byte count.
2865 For variable-precision integers like wide_int, handle HWI
2866 and sub-HWI integers inline. */
2867 if (STATIC_CONSTANT_P (xi
.precision
> HOST_BITS_PER_WIDE_INT
)
2868 ? xi
.len
== 1 && xi
.val
[0] >= 0
2869 : xi
.precision
<= HOST_BITS_PER_WIDE_INT
)
2871 val
[0] = xi
.to_uhwi () >> shift
;
2875 result
.set_len (lrshift_large (val
, xi
.val
, xi
.len
, xi
.precision
,
2876 get_precision (result
), shift
));
2881 /* Return X >> Y, using an arithmetic shift. Return a sign mask if
2882 Y is greater than or equal to the precision of X. */
2883 template <typename T1
, typename T2
>
2884 inline WI_UNARY_RESULT (T1
)
2885 wi::arshift (const T1
&x
, const T2
&y
)
2887 WI_UNARY_RESULT_VAR (result
, val
, T1
, x
);
2888 /* Do things in the precision of the input rather than the output,
2889 since the result can be no larger than that. */
2890 WIDE_INT_REF_FOR (T1
) xi (x
);
2891 WIDE_INT_REF_FOR (T2
) yi (y
);
2892 /* Handle the simple cases quickly. */
2893 if (geu_p (yi
, xi
.precision
))
2895 val
[0] = sign_mask (x
);
2900 unsigned int shift
= yi
.to_uhwi ();
2901 if (xi
.precision
<= HOST_BITS_PER_WIDE_INT
)
2903 val
[0] = sext_hwi (xi
.ulow () >> shift
, xi
.precision
- shift
);
2904 result
.set_len (1, true);
2907 result
.set_len (arshift_large (val
, xi
.val
, xi
.len
, xi
.precision
,
2908 get_precision (result
), shift
));
2913 /* Return X >> Y, using an arithmetic shift if SGN is SIGNED and a
2914 logical shift otherwise. If BITSIZE is nonzero, only use the low
2915 BITSIZE bits of Y. */
2916 template <typename T1
, typename T2
>
2917 inline WI_UNARY_RESULT (T1
)
2918 wi::rshift (const T1
&x
, const T2
&y
, signop sgn
)
2920 if (sgn
== UNSIGNED
)
2921 return lrshift (x
, y
);
2923 return arshift (x
, y
);
2926 /* Return the result of rotating the low WIDTH bits of X left by Y
2927 bits and zero-extending the result. Use a full-width rotate if
2929 template <typename T1
, typename T2
>
2930 WI_UNARY_RESULT (T1
)
2931 wi::lrotate (const T1
&x
, const T2
&y
, unsigned int width
)
2933 unsigned int precision
= get_binary_precision (x
, x
);
2936 WI_UNARY_RESULT (T2
) ymod
= umod_trunc (y
, width
);
2937 WI_UNARY_RESULT (T1
) left
= wi::lshift (x
, ymod
);
2938 WI_UNARY_RESULT (T1
) right
= wi::lrshift (x
, wi::sub (width
, ymod
));
2939 if (width
!= precision
)
2940 return wi::zext (left
, width
) | wi::zext (right
, width
);
2941 return left
| right
;
2944 /* Return the result of rotating the low WIDTH bits of X right by Y
2945 bits and zero-extending the result. Use a full-width rotate if
2947 template <typename T1
, typename T2
>
2948 WI_UNARY_RESULT (T1
)
2949 wi::rrotate (const T1
&x
, const T2
&y
, unsigned int width
)
2951 unsigned int precision
= get_binary_precision (x
, x
);
2954 WI_UNARY_RESULT (T2
) ymod
= umod_trunc (y
, width
);
2955 WI_UNARY_RESULT (T1
) right
= wi::lrshift (x
, ymod
);
2956 WI_UNARY_RESULT (T1
) left
= wi::lshift (x
, wi::sub (width
, ymod
));
2957 if (width
!= precision
)
2958 return wi::zext (left
, width
) | wi::zext (right
, width
);
2959 return left
| right
;
2962 /* Return 0 if the number of 1s in X is even and 1 if the number of 1s
2965 wi::parity (const wide_int_ref
&x
)
2967 return popcount (x
) & 1;
2970 /* Extract WIDTH bits from X, starting at BITPOS. */
2971 template <typename T
>
2972 inline unsigned HOST_WIDE_INT
2973 wi::extract_uhwi (const T
&x
, unsigned int bitpos
,
2976 unsigned precision
= get_precision (x
);
2977 if (precision
< bitpos
+ width
)
2978 precision
= bitpos
+ width
;
2979 WIDE_INT_REF_FOR (T
) xi (x
, precision
);
2981 /* Handle this rare case after the above, so that we assert about
2982 bogus BITPOS values. */
2986 unsigned int start
= bitpos
/ HOST_BITS_PER_WIDE_INT
;
2987 unsigned int shift
= bitpos
% HOST_BITS_PER_WIDE_INT
;
2988 unsigned HOST_WIDE_INT res
= xi
.elt (start
);
2990 if (shift
+ width
> HOST_BITS_PER_WIDE_INT
)
2992 unsigned HOST_WIDE_INT upper
= xi
.elt (start
+ 1);
2993 res
|= upper
<< (-shift
% HOST_BITS_PER_WIDE_INT
);
2995 return zext_hwi (res
, width
);
2998 template<typename T
>
3000 gt_ggc_mx (generic_wide_int
<T
> *)
3004 template<typename T
>
3006 gt_pch_nx (generic_wide_int
<T
> *)
3010 template<typename T
>
3012 gt_pch_nx (generic_wide_int
<T
> *, void (*) (void *, void *), void *)
3018 gt_ggc_mx (trailing_wide_ints
<N
> *)
3024 gt_pch_nx (trailing_wide_ints
<N
> *)
3030 gt_pch_nx (trailing_wide_ints
<N
> *, void (*) (void *, void *), void *)
3036 /* Used for overloaded functions in which the only other acceptable
3037 scalar type is a pointer. It stops a plain 0 from being treated
3038 as a null pointer. */
3039 struct never_used1
{};
3040 struct never_used2
{};
3042 wide_int
min_value (unsigned int, signop
);
3043 wide_int
min_value (never_used1
*);
3044 wide_int
min_value (never_used2
*);
3045 wide_int
max_value (unsigned int, signop
);
3046 wide_int
max_value (never_used1
*);
3047 wide_int
max_value (never_used2
*);
3049 /* FIXME: this is target dependent, so should be elsewhere.
3050 It also seems to assume that CHAR_BIT == BITS_PER_UNIT. */
3051 wide_int
from_buffer (const unsigned char *, unsigned int);
3053 #ifndef GENERATOR_FILE
3054 void to_mpz (wide_int
, mpz_t
, signop
);
3057 wide_int
mask (unsigned int, bool, unsigned int);
3058 wide_int
shifted_mask (unsigned int, unsigned int, bool, unsigned int);
3059 wide_int
set_bit_in_zero (unsigned int, unsigned int);
3060 wide_int
insert (const wide_int
&x
, const wide_int
&y
, unsigned int,
3063 template <typename T
>
3064 T
mask (unsigned int, bool);
3066 template <typename T
>
3067 T
shifted_mask (unsigned int, unsigned int, bool);
3069 template <typename T
>
3070 T
set_bit_in_zero (unsigned int);
3072 unsigned int mask (HOST_WIDE_INT
*, unsigned int, bool, unsigned int);
3073 unsigned int shifted_mask (HOST_WIDE_INT
*, unsigned int, unsigned int,
3074 bool, unsigned int);
3075 unsigned int from_array (HOST_WIDE_INT
*, const HOST_WIDE_INT
*,
3076 unsigned int, unsigned int, bool);
3079 /* Return a PRECISION-bit integer in which the low WIDTH bits are set
3080 and the other bits are clear, or the inverse if NEGATE_P. */
3082 wi::mask (unsigned int width
, bool negate_p
, unsigned int precision
)
3084 wide_int result
= wide_int::create (precision
);
3085 result
.set_len (mask (result
.write_val (), width
, negate_p
, precision
));
3089 /* Return a PRECISION-bit integer in which the low START bits are clear,
3090 the next WIDTH bits are set, and the other bits are clear,
3091 or the inverse if NEGATE_P. */
3093 wi::shifted_mask (unsigned int start
, unsigned int width
, bool negate_p
,
3094 unsigned int precision
)
3096 wide_int result
= wide_int::create (precision
);
3097 result
.set_len (shifted_mask (result
.write_val (), start
, width
, negate_p
,
3102 /* Return a PRECISION-bit integer in which bit BIT is set and all the
3103 others are clear. */
3105 wi::set_bit_in_zero (unsigned int bit
, unsigned int precision
)
3107 return shifted_mask (bit
, 1, false, precision
);
3110 /* Return an integer of type T in which the low WIDTH bits are set
3111 and the other bits are clear, or the inverse if NEGATE_P. */
3112 template <typename T
>
3114 wi::mask (unsigned int width
, bool negate_p
)
3116 STATIC_ASSERT (wi::int_traits
<T
>::precision
);
3118 result
.set_len (mask (result
.write_val (), width
, negate_p
,
3119 wi::int_traits
<T
>::precision
));
3123 /* Return an integer of type T in which the low START bits are clear,
3124 the next WIDTH bits are set, and the other bits are clear, or the
3125 inverse if NEGATE_P. */
3126 template <typename T
>
3128 wi::shifted_mask (unsigned int start
, unsigned int width
, bool negate_p
)
3130 STATIC_ASSERT (wi::int_traits
<T
>::precision
);
3132 result
.set_len (shifted_mask (result
.write_val (), start
, width
,
3134 wi::int_traits
<T
>::precision
));
3138 /* Return an integer of type T in which bit BIT is set and all the
3139 others are clear. */
3140 template <typename T
>
3142 wi::set_bit_in_zero (unsigned int bit
)
3144 return shifted_mask
<T
> (bit
, 1, false);
3147 #endif /* WIDE_INT_H */