re PR c++/66690 (error: use of ‘X’ before deduction of ‘auto’)
[official-gcc.git] / gcc / wide-int.h
blob61d9aab2a83d31eb1ea1c373104679138f991d9f
1 /* Operations with very long integers. -*- C++ -*-
2 Copyright (C) 2012-2017 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
9 later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
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/>. */
20 #ifndef WIDE_INT_H
21 #define WIDE_INT_H
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-precision integer that can hold
57 any address offset, measured in either bits or bytes, with at
58 least one extra sign bit. At the moment the maximum address
59 size GCC supports is 64 bits. With 8-bit bytes and an extra
60 sign bit, offset_int therefore needs to have at least 68 bits
61 of precision. We round this up to 128 bits for efficiency.
62 Values of type T are converted to this precision by sign- or
63 zero-extending them based on the signedness of T.
65 The extra sign bit means that offset_int is effectively a signed
66 128-bit integer, i.e. it behaves like int128_t.
68 Since the values are logically signed, there is no need to
69 distinguish between signed and unsigned operations. Sign-sensitive
70 comparison operators <, <=, > and >= are therefore supported.
71 Shift operators << and >> are also supported, with >> being
72 an _arithmetic_ right shift.
74 [ Note that, even though offset_int is effectively int128_t,
75 it can still be useful to use unsigned comparisons like
76 wi::leu_p (a, b) as a more efficient short-hand for
77 "a >= 0 && a <= b". ]
79 3) widest_int. This representation is an approximation of
80 infinite precision math. However, it is not really infinite
81 precision math as in the GMP library. It is really finite
82 precision math where the precision is 4 times the size of the
83 largest integer that the target port can represent.
85 Like offset_int, widest_int is wider than all the values that
86 it needs to represent, so the integers are logically signed.
87 Sign-sensitive comparison operators <, <=, > and >= are supported,
88 as are << and >>.
90 There are several places in the GCC where this should/must be used:
92 * Code that does induction variable optimizations. This code
93 works with induction variables of many different types at the
94 same time. Because of this, it ends up doing many different
95 calculations where the operands are not compatible types. The
96 widest_int makes this easy, because it provides a field where
97 nothing is lost when converting from any variable,
99 * There are a small number of passes that currently use the
100 widest_int that should use the default. These should be
101 changed.
103 There are surprising features of offset_int and widest_int
104 that the users should be careful about:
106 1) Shifts and rotations are just weird. You have to specify a
107 precision in which the shift or rotate is to happen in. The bits
108 above this precision are zeroed. While this is what you
109 want, it is clearly non obvious.
111 2) Larger precision math sometimes does not produce the same
112 answer as would be expected for doing the math at the proper
113 precision. In particular, a multiply followed by a divide will
114 produce a different answer if the first product is larger than
115 what can be represented in the input precision.
117 The offset_int and the widest_int flavors are more expensive
118 than the default wide int, so in addition to the caveats with these
119 two, the default is the prefered representation.
121 All three flavors of wide_int are represented as a vector of
122 HOST_WIDE_INTs. The default and widest_int vectors contain enough elements
123 to hold a value of MAX_BITSIZE_MODE_ANY_INT bits. offset_int contains only
124 enough elements to hold ADDR_MAX_PRECISION bits. The values are stored
125 in the vector with the least significant HOST_BITS_PER_WIDE_INT bits
126 in element 0.
128 The default wide_int contains three fields: the vector (VAL),
129 the precision and a length (LEN). The length is the number of HWIs
130 needed to represent the value. widest_int and offset_int have a
131 constant precision that cannot be changed, so they only store the
132 VAL and LEN fields.
134 Since most integers used in a compiler are small values, it is
135 generally profitable to use a representation of the value that is
136 as small as possible. LEN is used to indicate the number of
137 elements of the vector that are in use. The numbers are stored as
138 sign extended numbers as a means of compression. Leading
139 HOST_WIDE_INTs that contain strings of either -1 or 0 are removed
140 as long as they can be reconstructed from the top bit that is being
141 represented.
143 The precision and length of a wide_int are always greater than 0.
144 Any bits in a wide_int above the precision are sign-extended from the
145 most significant bit. For example, a 4-bit value 0x8 is represented as
146 VAL = { 0xf...fff8 }. However, as an optimization, we allow other integer
147 constants to be represented with undefined bits above the precision.
148 This allows INTEGER_CSTs to be pre-extended according to TYPE_SIGN,
149 so that the INTEGER_CST representation can be used both in TYPE_PRECISION
150 and in wider precisions.
152 There are constructors to create the various forms of wide_int from
153 trees, rtl and constants. For trees you can simply say:
155 tree t = ...;
156 wide_int x = t;
158 However, a little more syntax is required for rtl constants since
159 they do not have an explicit precision. To make an rtl into a
160 wide_int, you have to pair it with a mode. The canonical way to do
161 this is with rtx_mode_t as in:
163 rtx r = ...
164 wide_int x = rtx_mode_t (r, mode);
166 Similarly, a wide_int can only be constructed from a host value if
167 the target precision is given explicitly, such as in:
169 wide_int x = wi::shwi (c, prec); // sign-extend C if necessary
170 wide_int y = wi::uhwi (c, prec); // zero-extend C if necessary
172 However, offset_int and widest_int have an inherent precision and so
173 can be initialized directly from a host value:
175 offset_int x = (int) c; // sign-extend C
176 widest_int x = (unsigned int) c; // zero-extend C
178 It is also possible to do arithmetic directly on trees, rtxes and
179 constants. For example:
181 wi::add (t1, t2); // add equal-sized INTEGER_CSTs t1 and t2
182 wi::add (t1, 1); // add 1 to INTEGER_CST t1
183 wi::add (r1, r2); // add equal-sized rtx constants r1 and r2
184 wi::lshift (1, 100); // 1 << 100 as a widest_int
186 Many binary operations place restrictions on the combinations of inputs,
187 using the following rules:
189 - {tree, rtx, wide_int} op {tree, rtx, wide_int} -> wide_int
190 The inputs must be the same precision. The result is a wide_int
191 of the same precision
193 - {tree, rtx, wide_int} op (un)signed HOST_WIDE_INT -> wide_int
194 (un)signed HOST_WIDE_INT op {tree, rtx, wide_int} -> wide_int
195 The HOST_WIDE_INT is extended or truncated to the precision of
196 the other input. The result is a wide_int of the same precision
197 as that input.
199 - (un)signed HOST_WIDE_INT op (un)signed HOST_WIDE_INT -> widest_int
200 The inputs are extended to widest_int precision and produce a
201 widest_int result.
203 - offset_int op offset_int -> offset_int
204 offset_int op (un)signed HOST_WIDE_INT -> offset_int
205 (un)signed HOST_WIDE_INT op offset_int -> offset_int
207 - widest_int op widest_int -> widest_int
208 widest_int op (un)signed HOST_WIDE_INT -> widest_int
209 (un)signed HOST_WIDE_INT op widest_int -> widest_int
211 Other combinations like:
213 - widest_int op offset_int and
214 - wide_int op offset_int
216 are not allowed. The inputs should instead be extended or truncated
217 so that they match.
219 The inputs to comparison functions like wi::eq_p and wi::lts_p
220 follow the same compatibility rules, although their return types
221 are different. Unary functions on X produce the same result as
222 a binary operation X + X. Shift functions X op Y also produce
223 the same result as X + X; the precision of the shift amount Y
224 can be arbitrarily different from X. */
226 /* The MAX_BITSIZE_MODE_ANY_INT is automatically generated by a very
227 early examination of the target's mode file. The WIDE_INT_MAX_ELTS
228 can accomodate at least 1 more bit so that unsigned numbers of that
229 mode can be represented as a signed value. Note that it is still
230 possible to create fixed_wide_ints that have precisions greater than
231 MAX_BITSIZE_MODE_ANY_INT. This can be useful when representing a
232 double-width multiplication result, for example. */
233 #define WIDE_INT_MAX_ELTS \
234 ((MAX_BITSIZE_MODE_ANY_INT + HOST_BITS_PER_WIDE_INT) / HOST_BITS_PER_WIDE_INT)
236 #define WIDE_INT_MAX_PRECISION (WIDE_INT_MAX_ELTS * HOST_BITS_PER_WIDE_INT)
238 /* This is the max size of any pointer on any machine. It does not
239 seem to be as easy to sniff this out of the machine description as
240 it is for MAX_BITSIZE_MODE_ANY_INT since targets may support
241 multiple address sizes and may have different address sizes for
242 different address spaces. However, currently the largest pointer
243 on any platform is 64 bits. When that changes, then it is likely
244 that a target hook should be defined so that targets can make this
245 value larger for those targets. */
246 #define ADDR_MAX_BITSIZE 64
248 /* This is the internal precision used when doing any address
249 arithmetic. The '4' is really 3 + 1. Three of the bits are for
250 the number of extra bits needed to do bit addresses and the other bit
251 is to allow everything to be signed without loosing any precision.
252 Then everything is rounded up to the next HWI for efficiency. */
253 #define ADDR_MAX_PRECISION \
254 ((ADDR_MAX_BITSIZE + 4 + HOST_BITS_PER_WIDE_INT - 1) \
255 & ~(HOST_BITS_PER_WIDE_INT - 1))
257 /* The number of HWIs needed to store an offset_int. */
258 #define OFFSET_INT_ELTS (ADDR_MAX_PRECISION / HOST_BITS_PER_WIDE_INT)
260 /* The type of result produced by a binary operation on types T1 and T2.
261 Defined purely for brevity. */
262 #define WI_BINARY_RESULT(T1, T2) \
263 typename wi::binary_traits <T1, T2>::result_type
265 /* The type of result produced by T1 << T2. Leads to substitution failure
266 if the operation isn't supported. Defined purely for brevity. */
267 #define WI_SIGNED_SHIFT_RESULT(T1, T2) \
268 typename wi::binary_traits <T1, T2>::signed_shift_result_type
270 /* The type of result produced by a signed binary predicate on types T1 and T2.
271 This is bool if signed comparisons make sense for T1 and T2 and leads to
272 substitution failure otherwise. */
273 #define WI_SIGNED_BINARY_PREDICATE_RESULT(T1, T2) \
274 typename wi::binary_traits <T1, T2>::signed_predicate_result
276 /* The type of result produced by a unary operation on type T. */
277 #define WI_UNARY_RESULT(T) \
278 typename wi::unary_traits <T>::result_type
280 /* Define a variable RESULT to hold the result of a binary operation on
281 X and Y, which have types T1 and T2 respectively. Define VAL to
282 point to the blocks of RESULT. Once the user of the macro has
283 filled in VAL, it should call RESULT.set_len to set the number
284 of initialized blocks. */
285 #define WI_BINARY_RESULT_VAR(RESULT, VAL, T1, X, T2, Y) \
286 WI_BINARY_RESULT (T1, T2) RESULT = \
287 wi::int_traits <WI_BINARY_RESULT (T1, T2)>::get_binary_result (X, Y); \
288 HOST_WIDE_INT *VAL = RESULT.write_val ()
290 /* Similar for the result of a unary operation on X, which has type T. */
291 #define WI_UNARY_RESULT_VAR(RESULT, VAL, T, X) \
292 WI_UNARY_RESULT (T) RESULT = \
293 wi::int_traits <WI_UNARY_RESULT (T)>::get_binary_result (X, X); \
294 HOST_WIDE_INT *VAL = RESULT.write_val ()
296 template <typename T> class generic_wide_int;
297 template <int N> class fixed_wide_int_storage;
298 class wide_int_storage;
300 /* An N-bit integer. Until we can use typedef templates, use this instead. */
301 #define FIXED_WIDE_INT(N) \
302 generic_wide_int < fixed_wide_int_storage <N> >
304 typedef generic_wide_int <wide_int_storage> wide_int;
305 typedef FIXED_WIDE_INT (ADDR_MAX_PRECISION) offset_int;
306 typedef FIXED_WIDE_INT (WIDE_INT_MAX_PRECISION) widest_int;
308 template <bool SE>
309 struct wide_int_ref_storage;
311 typedef generic_wide_int <wide_int_ref_storage <false> > wide_int_ref;
313 /* This can be used instead of wide_int_ref if the referenced value is
314 known to have type T. It carries across properties of T's representation,
315 such as whether excess upper bits in a HWI are defined, and can therefore
316 help avoid redundant work.
318 The macro could be replaced with a template typedef, once we're able
319 to use those. */
320 #define WIDE_INT_REF_FOR(T) \
321 generic_wide_int \
322 <wide_int_ref_storage <wi::int_traits <T>::is_sign_extended> >
324 namespace wi
326 /* Classifies an integer based on its precision. */
327 enum precision_type {
328 /* The integer has both a precision and defined signedness. This allows
329 the integer to be converted to any width, since we know whether to fill
330 any extra bits with zeros or signs. */
331 FLEXIBLE_PRECISION,
333 /* The integer has a variable precision but no defined signedness. */
334 VAR_PRECISION,
336 /* The integer has a constant precision (known at GCC compile time)
337 and is signed. */
338 CONST_PRECISION
341 /* This class, which has no default implementation, is expected to
342 provide the following members:
344 static const enum precision_type precision_type;
345 Classifies the type of T.
347 static const unsigned int precision;
348 Only defined if precision_type == CONST_PRECISION. Specifies the
349 precision of all integers of type T.
351 static const bool host_dependent_precision;
352 True if the precision of T depends (or can depend) on the host.
354 static unsigned int get_precision (const T &x)
355 Return the number of bits in X.
357 static wi::storage_ref *decompose (HOST_WIDE_INT *scratch,
358 unsigned int precision, const T &x)
359 Decompose X as a PRECISION-bit integer, returning the associated
360 wi::storage_ref. SCRATCH is available as scratch space if needed.
361 The routine should assert that PRECISION is acceptable. */
362 template <typename T> struct int_traits;
364 /* This class provides a single type, result_type, which specifies the
365 type of integer produced by a binary operation whose inputs have
366 types T1 and T2. The definition should be symmetric. */
367 template <typename T1, typename T2,
368 enum precision_type P1 = int_traits <T1>::precision_type,
369 enum precision_type P2 = int_traits <T2>::precision_type>
370 struct binary_traits;
372 /* The result of a unary operation on T is the same as the result of
373 a binary operation on two values of type T. */
374 template <typename T>
375 struct unary_traits : public binary_traits <T, T> {};
377 /* Specify the result type for each supported combination of binary
378 inputs. Note that CONST_PRECISION and VAR_PRECISION cannot be
379 mixed, in order to give stronger type checking. When both inputs
380 are CONST_PRECISION, they must have the same precision. */
381 template <typename T1, typename T2>
382 struct binary_traits <T1, T2, FLEXIBLE_PRECISION, FLEXIBLE_PRECISION>
384 typedef widest_int result_type;
387 template <typename T1, typename T2>
388 struct binary_traits <T1, T2, FLEXIBLE_PRECISION, VAR_PRECISION>
390 typedef wide_int result_type;
393 template <typename T1, typename T2>
394 struct binary_traits <T1, T2, FLEXIBLE_PRECISION, CONST_PRECISION>
396 /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
397 so as not to confuse gengtype. */
398 typedef generic_wide_int < fixed_wide_int_storage
399 <int_traits <T2>::precision> > result_type;
400 typedef bool signed_predicate_result;
403 template <typename T1, typename T2>
404 struct binary_traits <T1, T2, VAR_PRECISION, FLEXIBLE_PRECISION>
406 typedef wide_int result_type;
409 template <typename T1, typename T2>
410 struct binary_traits <T1, T2, CONST_PRECISION, FLEXIBLE_PRECISION>
412 /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
413 so as not to confuse gengtype. */
414 typedef generic_wide_int < fixed_wide_int_storage
415 <int_traits <T1>::precision> > result_type;
416 typedef result_type signed_shift_result_type;
417 typedef bool signed_predicate_result;
420 template <typename T1, typename T2>
421 struct binary_traits <T1, T2, CONST_PRECISION, CONST_PRECISION>
423 /* Spelled out explicitly (rather than through FIXED_WIDE_INT)
424 so as not to confuse gengtype. */
425 STATIC_ASSERT (int_traits <T1>::precision == int_traits <T2>::precision);
426 typedef generic_wide_int < fixed_wide_int_storage
427 <int_traits <T1>::precision> > result_type;
428 typedef result_type signed_shift_result_type;
429 typedef bool signed_predicate_result;
432 template <typename T1, typename T2>
433 struct binary_traits <T1, T2, VAR_PRECISION, VAR_PRECISION>
435 typedef wide_int result_type;
439 /* Public functions for querying and operating on integers. */
440 namespace wi
442 template <typename T>
443 unsigned int get_precision (const T &);
445 template <typename T1, typename T2>
446 unsigned int get_binary_precision (const T1 &, const T2 &);
448 template <typename T1, typename T2>
449 void copy (T1 &, const T2 &);
451 #define UNARY_PREDICATE \
452 template <typename T> bool
453 #define UNARY_FUNCTION \
454 template <typename T> WI_UNARY_RESULT (T)
455 #define BINARY_PREDICATE \
456 template <typename T1, typename T2> bool
457 #define BINARY_FUNCTION \
458 template <typename T1, typename T2> WI_BINARY_RESULT (T1, T2)
459 #define SHIFT_FUNCTION \
460 template <typename T1, typename T2> WI_UNARY_RESULT (T1)
462 UNARY_PREDICATE fits_shwi_p (const T &);
463 UNARY_PREDICATE fits_uhwi_p (const T &);
464 UNARY_PREDICATE neg_p (const T &, signop = SIGNED);
466 template <typename T>
467 HOST_WIDE_INT sign_mask (const T &);
469 BINARY_PREDICATE eq_p (const T1 &, const T2 &);
470 BINARY_PREDICATE ne_p (const T1 &, const T2 &);
471 BINARY_PREDICATE lt_p (const T1 &, const T2 &, signop);
472 BINARY_PREDICATE lts_p (const T1 &, const T2 &);
473 BINARY_PREDICATE ltu_p (const T1 &, const T2 &);
474 BINARY_PREDICATE le_p (const T1 &, const T2 &, signop);
475 BINARY_PREDICATE les_p (const T1 &, const T2 &);
476 BINARY_PREDICATE leu_p (const T1 &, const T2 &);
477 BINARY_PREDICATE gt_p (const T1 &, const T2 &, signop);
478 BINARY_PREDICATE gts_p (const T1 &, const T2 &);
479 BINARY_PREDICATE gtu_p (const T1 &, const T2 &);
480 BINARY_PREDICATE ge_p (const T1 &, const T2 &, signop);
481 BINARY_PREDICATE ges_p (const T1 &, const T2 &);
482 BINARY_PREDICATE geu_p (const T1 &, const T2 &);
484 template <typename T1, typename T2>
485 int cmp (const T1 &, const T2 &, signop);
487 template <typename T1, typename T2>
488 int cmps (const T1 &, const T2 &);
490 template <typename T1, typename T2>
491 int cmpu (const T1 &, const T2 &);
493 UNARY_FUNCTION bit_not (const T &);
494 UNARY_FUNCTION neg (const T &);
495 UNARY_FUNCTION neg (const T &, bool *);
496 UNARY_FUNCTION abs (const T &);
497 UNARY_FUNCTION ext (const T &, unsigned int, signop);
498 UNARY_FUNCTION sext (const T &, unsigned int);
499 UNARY_FUNCTION zext (const T &, unsigned int);
500 UNARY_FUNCTION set_bit (const T &, unsigned int);
502 BINARY_FUNCTION min (const T1 &, const T2 &, signop);
503 BINARY_FUNCTION smin (const T1 &, const T2 &);
504 BINARY_FUNCTION umin (const T1 &, const T2 &);
505 BINARY_FUNCTION max (const T1 &, const T2 &, signop);
506 BINARY_FUNCTION smax (const T1 &, const T2 &);
507 BINARY_FUNCTION umax (const T1 &, const T2 &);
509 BINARY_FUNCTION bit_and (const T1 &, const T2 &);
510 BINARY_FUNCTION bit_and_not (const T1 &, const T2 &);
511 BINARY_FUNCTION bit_or (const T1 &, const T2 &);
512 BINARY_FUNCTION bit_or_not (const T1 &, const T2 &);
513 BINARY_FUNCTION bit_xor (const T1 &, const T2 &);
514 BINARY_FUNCTION add (const T1 &, const T2 &);
515 BINARY_FUNCTION add (const T1 &, const T2 &, signop, bool *);
516 BINARY_FUNCTION sub (const T1 &, const T2 &);
517 BINARY_FUNCTION sub (const T1 &, const T2 &, signop, bool *);
518 BINARY_FUNCTION mul (const T1 &, const T2 &);
519 BINARY_FUNCTION mul (const T1 &, const T2 &, signop, bool *);
520 BINARY_FUNCTION smul (const T1 &, const T2 &, bool *);
521 BINARY_FUNCTION umul (const T1 &, const T2 &, bool *);
522 BINARY_FUNCTION mul_high (const T1 &, const T2 &, signop);
523 BINARY_FUNCTION div_trunc (const T1 &, const T2 &, signop, bool * = 0);
524 BINARY_FUNCTION sdiv_trunc (const T1 &, const T2 &);
525 BINARY_FUNCTION udiv_trunc (const T1 &, const T2 &);
526 BINARY_FUNCTION div_floor (const T1 &, const T2 &, signop, bool * = 0);
527 BINARY_FUNCTION udiv_floor (const T1 &, const T2 &);
528 BINARY_FUNCTION sdiv_floor (const T1 &, const T2 &);
529 BINARY_FUNCTION div_ceil (const T1 &, const T2 &, signop, bool * = 0);
530 BINARY_FUNCTION div_round (const T1 &, const T2 &, signop, bool * = 0);
531 BINARY_FUNCTION divmod_trunc (const T1 &, const T2 &, signop,
532 WI_BINARY_RESULT (T1, T2) *);
533 BINARY_FUNCTION gcd (const T1 &, const T2 &, signop = UNSIGNED);
534 BINARY_FUNCTION mod_trunc (const T1 &, const T2 &, signop, bool * = 0);
535 BINARY_FUNCTION smod_trunc (const T1 &, const T2 &);
536 BINARY_FUNCTION umod_trunc (const T1 &, const T2 &);
537 BINARY_FUNCTION mod_floor (const T1 &, const T2 &, signop, bool * = 0);
538 BINARY_FUNCTION umod_floor (const T1 &, const T2 &);
539 BINARY_FUNCTION mod_ceil (const T1 &, const T2 &, signop, bool * = 0);
540 BINARY_FUNCTION mod_round (const T1 &, const T2 &, signop, bool * = 0);
542 template <typename T1, typename T2>
543 bool multiple_of_p (const T1 &, const T2 &, signop);
545 template <typename T1, typename T2>
546 bool multiple_of_p (const T1 &, const T2 &, signop,
547 WI_BINARY_RESULT (T1, T2) *);
549 SHIFT_FUNCTION lshift (const T1 &, const T2 &);
550 SHIFT_FUNCTION lrshift (const T1 &, const T2 &);
551 SHIFT_FUNCTION arshift (const T1 &, const T2 &);
552 SHIFT_FUNCTION rshift (const T1 &, const T2 &, signop sgn);
553 SHIFT_FUNCTION lrotate (const T1 &, const T2 &, unsigned int = 0);
554 SHIFT_FUNCTION rrotate (const T1 &, const T2 &, unsigned int = 0);
556 #undef SHIFT_FUNCTION
557 #undef BINARY_PREDICATE
558 #undef BINARY_FUNCTION
559 #undef UNARY_PREDICATE
560 #undef UNARY_FUNCTION
562 bool only_sign_bit_p (const wide_int_ref &, unsigned int);
563 bool only_sign_bit_p (const wide_int_ref &);
564 int clz (const wide_int_ref &);
565 int clrsb (const wide_int_ref &);
566 int ctz (const wide_int_ref &);
567 int exact_log2 (const wide_int_ref &);
568 int floor_log2 (const wide_int_ref &);
569 int ffs (const wide_int_ref &);
570 int popcount (const wide_int_ref &);
571 int parity (const wide_int_ref &);
573 template <typename T>
574 unsigned HOST_WIDE_INT extract_uhwi (const T &, unsigned int, unsigned int);
576 template <typename T>
577 unsigned int min_precision (const T &, signop);
580 namespace wi
582 /* Contains the components of a decomposed integer for easy, direct
583 access. */
584 struct storage_ref
586 storage_ref (const HOST_WIDE_INT *, unsigned int, unsigned int);
588 const HOST_WIDE_INT *val;
589 unsigned int len;
590 unsigned int precision;
592 /* Provide enough trappings for this class to act as storage for
593 generic_wide_int. */
594 unsigned int get_len () const;
595 unsigned int get_precision () const;
596 const HOST_WIDE_INT *get_val () const;
600 inline::wi::storage_ref::storage_ref (const HOST_WIDE_INT *val_in,
601 unsigned int len_in,
602 unsigned int precision_in)
603 : val (val_in), len (len_in), precision (precision_in)
607 inline unsigned int
608 wi::storage_ref::get_len () const
610 return len;
613 inline unsigned int
614 wi::storage_ref::get_precision () const
616 return precision;
619 inline const HOST_WIDE_INT *
620 wi::storage_ref::get_val () const
622 return val;
625 /* This class defines an integer type using the storage provided by the
626 template argument. The storage class must provide the following
627 functions:
629 unsigned int get_precision () const
630 Return the number of bits in the integer.
632 HOST_WIDE_INT *get_val () const
633 Return a pointer to the array of blocks that encodes the integer.
635 unsigned int get_len () const
636 Return the number of blocks in get_val (). If this is smaller
637 than the number of blocks implied by get_precision (), the
638 remaining blocks are sign extensions of block get_len () - 1.
640 Although not required by generic_wide_int itself, writable storage
641 classes can also provide the following functions:
643 HOST_WIDE_INT *write_val ()
644 Get a modifiable version of get_val ()
646 unsigned int set_len (unsigned int len)
647 Set the value returned by get_len () to LEN. */
648 template <typename storage>
649 class GTY(()) generic_wide_int : public storage
651 public:
652 generic_wide_int ();
654 template <typename T>
655 generic_wide_int (const T &);
657 template <typename T>
658 generic_wide_int (const T &, unsigned int);
660 /* Conversions. */
661 HOST_WIDE_INT to_shwi (unsigned int) const;
662 HOST_WIDE_INT to_shwi () const;
663 unsigned HOST_WIDE_INT to_uhwi (unsigned int) const;
664 unsigned HOST_WIDE_INT to_uhwi () const;
665 HOST_WIDE_INT to_short_addr () const;
667 /* Public accessors for the interior of a wide int. */
668 HOST_WIDE_INT sign_mask () const;
669 HOST_WIDE_INT elt (unsigned int) const;
670 unsigned HOST_WIDE_INT ulow () const;
671 unsigned HOST_WIDE_INT uhigh () const;
672 HOST_WIDE_INT slow () const;
673 HOST_WIDE_INT shigh () const;
675 template <typename T>
676 generic_wide_int &operator = (const T &);
678 #define BINARY_PREDICATE(OP, F) \
679 template <typename T> \
680 bool OP (const T &c) const { return wi::F (*this, c); }
682 #define UNARY_OPERATOR(OP, F) \
683 WI_UNARY_RESULT (generic_wide_int) OP () const { return wi::F (*this); }
685 #define BINARY_OPERATOR(OP, F) \
686 template <typename T> \
687 WI_BINARY_RESULT (generic_wide_int, T) \
688 OP (const T &c) const { return wi::F (*this, c); }
690 #define ASSIGNMENT_OPERATOR(OP, F) \
691 template <typename T> \
692 generic_wide_int &OP (const T &c) { return (*this = wi::F (*this, c)); }
694 /* Restrict these to cases where the shift operator is defined. */
695 #define SHIFT_ASSIGNMENT_OPERATOR(OP, OP2) \
696 template <typename T> \
697 generic_wide_int &OP (const T &c) { return (*this = *this OP2 c); }
699 #define INCDEC_OPERATOR(OP, DELTA) \
700 generic_wide_int &OP () { *this += DELTA; return *this; }
702 UNARY_OPERATOR (operator ~, bit_not)
703 UNARY_OPERATOR (operator -, neg)
704 BINARY_PREDICATE (operator ==, eq_p)
705 BINARY_PREDICATE (operator !=, ne_p)
706 BINARY_OPERATOR (operator &, bit_and)
707 BINARY_OPERATOR (and_not, bit_and_not)
708 BINARY_OPERATOR (operator |, bit_or)
709 BINARY_OPERATOR (or_not, bit_or_not)
710 BINARY_OPERATOR (operator ^, bit_xor)
711 BINARY_OPERATOR (operator +, add)
712 BINARY_OPERATOR (operator -, sub)
713 BINARY_OPERATOR (operator *, mul)
714 ASSIGNMENT_OPERATOR (operator &=, bit_and)
715 ASSIGNMENT_OPERATOR (operator |=, bit_or)
716 ASSIGNMENT_OPERATOR (operator ^=, bit_xor)
717 ASSIGNMENT_OPERATOR (operator +=, add)
718 ASSIGNMENT_OPERATOR (operator -=, sub)
719 ASSIGNMENT_OPERATOR (operator *=, mul)
720 SHIFT_ASSIGNMENT_OPERATOR (operator <<=, <<)
721 SHIFT_ASSIGNMENT_OPERATOR (operator >>=, >>)
722 INCDEC_OPERATOR (operator ++, 1)
723 INCDEC_OPERATOR (operator --, -1)
725 #undef BINARY_PREDICATE
726 #undef UNARY_OPERATOR
727 #undef BINARY_OPERATOR
728 #undef SHIFT_ASSIGNMENT_OPERATOR
729 #undef ASSIGNMENT_OPERATOR
730 #undef INCDEC_OPERATOR
732 /* Debugging functions. */
733 void dump () const;
735 static const bool is_sign_extended
736 = wi::int_traits <generic_wide_int <storage> >::is_sign_extended;
739 template <typename storage>
740 inline generic_wide_int <storage>::generic_wide_int () {}
742 template <typename storage>
743 template <typename T>
744 inline generic_wide_int <storage>::generic_wide_int (const T &x)
745 : storage (x)
749 template <typename storage>
750 template <typename T>
751 inline generic_wide_int <storage>::generic_wide_int (const T &x,
752 unsigned int precision)
753 : storage (x, precision)
757 /* Return THIS as a signed HOST_WIDE_INT, sign-extending from PRECISION.
758 If THIS does not fit in PRECISION, the information is lost. */
759 template <typename storage>
760 inline HOST_WIDE_INT
761 generic_wide_int <storage>::to_shwi (unsigned int precision) const
763 if (precision < HOST_BITS_PER_WIDE_INT)
764 return sext_hwi (this->get_val ()[0], precision);
765 else
766 return this->get_val ()[0];
769 /* Return THIS as a signed HOST_WIDE_INT, in its natural precision. */
770 template <typename storage>
771 inline HOST_WIDE_INT
772 generic_wide_int <storage>::to_shwi () const
774 if (is_sign_extended)
775 return this->get_val ()[0];
776 else
777 return to_shwi (this->get_precision ());
780 /* Return THIS as an unsigned HOST_WIDE_INT, zero-extending from
781 PRECISION. If THIS does not fit in PRECISION, the information
782 is lost. */
783 template <typename storage>
784 inline unsigned HOST_WIDE_INT
785 generic_wide_int <storage>::to_uhwi (unsigned int precision) const
787 if (precision < HOST_BITS_PER_WIDE_INT)
788 return zext_hwi (this->get_val ()[0], precision);
789 else
790 return this->get_val ()[0];
793 /* Return THIS as an signed HOST_WIDE_INT, in its natural precision. */
794 template <typename storage>
795 inline unsigned HOST_WIDE_INT
796 generic_wide_int <storage>::to_uhwi () const
798 return to_uhwi (this->get_precision ());
801 /* TODO: The compiler is half converted from using HOST_WIDE_INT to
802 represent addresses to using offset_int to represent addresses.
803 We use to_short_addr at the interface from new code to old,
804 unconverted code. */
805 template <typename storage>
806 inline HOST_WIDE_INT
807 generic_wide_int <storage>::to_short_addr () const
809 return this->get_val ()[0];
812 /* Return the implicit value of blocks above get_len (). */
813 template <typename storage>
814 inline HOST_WIDE_INT
815 generic_wide_int <storage>::sign_mask () const
817 unsigned int len = this->get_len ();
818 unsigned HOST_WIDE_INT high = this->get_val ()[len - 1];
819 if (!is_sign_extended)
821 unsigned int precision = this->get_precision ();
822 int excess = len * HOST_BITS_PER_WIDE_INT - precision;
823 if (excess > 0)
824 high <<= excess;
826 return (HOST_WIDE_INT) (high) < 0 ? -1 : 0;
829 /* Return the signed value of the least-significant explicitly-encoded
830 block. */
831 template <typename storage>
832 inline HOST_WIDE_INT
833 generic_wide_int <storage>::slow () const
835 return this->get_val ()[0];
838 /* Return the signed value of the most-significant explicitly-encoded
839 block. */
840 template <typename storage>
841 inline HOST_WIDE_INT
842 generic_wide_int <storage>::shigh () const
844 return this->get_val ()[this->get_len () - 1];
847 /* Return the unsigned value of the least-significant
848 explicitly-encoded block. */
849 template <typename storage>
850 inline unsigned HOST_WIDE_INT
851 generic_wide_int <storage>::ulow () const
853 return this->get_val ()[0];
856 /* Return the unsigned value of the most-significant
857 explicitly-encoded block. */
858 template <typename storage>
859 inline unsigned HOST_WIDE_INT
860 generic_wide_int <storage>::uhigh () const
862 return this->get_val ()[this->get_len () - 1];
865 /* Return block I, which might be implicitly or explicit encoded. */
866 template <typename storage>
867 inline HOST_WIDE_INT
868 generic_wide_int <storage>::elt (unsigned int i) const
870 if (i >= this->get_len ())
871 return sign_mask ();
872 else
873 return this->get_val ()[i];
876 template <typename storage>
877 template <typename T>
878 inline generic_wide_int <storage> &
879 generic_wide_int <storage>::operator = (const T &x)
881 storage::operator = (x);
882 return *this;
885 /* Dump the contents of the integer to stderr, for debugging. */
886 template <typename storage>
887 void
888 generic_wide_int <storage>::dump () const
890 unsigned int len = this->get_len ();
891 const HOST_WIDE_INT *val = this->get_val ();
892 unsigned int precision = this->get_precision ();
893 fprintf (stderr, "[");
894 if (len * HOST_BITS_PER_WIDE_INT < precision)
895 fprintf (stderr, "...,");
896 for (unsigned int i = 0; i < len - 1; ++i)
897 fprintf (stderr, HOST_WIDE_INT_PRINT_HEX ",", val[len - 1 - i]);
898 fprintf (stderr, HOST_WIDE_INT_PRINT_HEX "], precision = %d\n",
899 val[0], precision);
902 namespace wi
904 template <typename storage>
905 struct int_traits < generic_wide_int <storage> >
906 : public wi::int_traits <storage>
908 static unsigned int get_precision (const generic_wide_int <storage> &);
909 static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int,
910 const generic_wide_int <storage> &);
914 template <typename storage>
915 inline unsigned int
916 wi::int_traits < generic_wide_int <storage> >::
917 get_precision (const generic_wide_int <storage> &x)
919 return x.get_precision ();
922 template <typename storage>
923 inline wi::storage_ref
924 wi::int_traits < generic_wide_int <storage> >::
925 decompose (HOST_WIDE_INT *, unsigned int precision,
926 const generic_wide_int <storage> &x)
928 gcc_checking_assert (precision == x.get_precision ());
929 return wi::storage_ref (x.get_val (), x.get_len (), precision);
932 /* Provide the storage for a wide_int_ref. This acts like a read-only
933 wide_int, with the optimization that VAL is normally a pointer to
934 another integer's storage, so that no array copy is needed. */
935 template <bool SE>
936 struct wide_int_ref_storage : public wi::storage_ref
938 private:
939 /* Scratch space that can be used when decomposing the original integer.
940 It must live as long as this object. */
941 HOST_WIDE_INT scratch[2];
943 public:
944 wide_int_ref_storage (const wi::storage_ref &);
946 template <typename T>
947 wide_int_ref_storage (const T &);
949 template <typename T>
950 wide_int_ref_storage (const T &, unsigned int);
953 /* Create a reference from an existing reference. */
954 template <bool SE>
955 inline wide_int_ref_storage <SE>::
956 wide_int_ref_storage (const wi::storage_ref &x)
957 : storage_ref (x)
960 /* Create a reference to integer X in its natural precision. Note
961 that the natural precision is host-dependent for primitive
962 types. */
963 template <bool SE>
964 template <typename T>
965 inline wide_int_ref_storage <SE>::wide_int_ref_storage (const T &x)
966 : storage_ref (wi::int_traits <T>::decompose (scratch,
967 wi::get_precision (x), x))
971 /* Create a reference to integer X in precision PRECISION. */
972 template <bool SE>
973 template <typename T>
974 inline wide_int_ref_storage <SE>::wide_int_ref_storage (const T &x,
975 unsigned int precision)
976 : storage_ref (wi::int_traits <T>::decompose (scratch, precision, x))
980 namespace wi
982 template <bool SE>
983 struct int_traits <wide_int_ref_storage <SE> >
985 static const enum precision_type precision_type = VAR_PRECISION;
986 /* wi::storage_ref can be a reference to a primitive type,
987 so this is the conservatively-correct setting. */
988 static const bool host_dependent_precision = true;
989 static const bool is_sign_extended = SE;
993 namespace wi
995 unsigned int force_to_size (HOST_WIDE_INT *, const HOST_WIDE_INT *,
996 unsigned int, unsigned int, unsigned int,
997 signop sgn);
998 unsigned int from_array (HOST_WIDE_INT *, const HOST_WIDE_INT *,
999 unsigned int, unsigned int, bool = true);
1002 /* The storage used by wide_int. */
1003 class GTY(()) wide_int_storage
1005 private:
1006 HOST_WIDE_INT val[WIDE_INT_MAX_ELTS];
1007 unsigned int len;
1008 unsigned int precision;
1010 public:
1011 wide_int_storage ();
1012 template <typename T>
1013 wide_int_storage (const T &);
1015 /* The standard generic_wide_int storage methods. */
1016 unsigned int get_precision () const;
1017 const HOST_WIDE_INT *get_val () const;
1018 unsigned int get_len () const;
1019 HOST_WIDE_INT *write_val ();
1020 void set_len (unsigned int, bool = false);
1022 template <typename T>
1023 wide_int_storage &operator = (const T &);
1025 static wide_int from (const wide_int_ref &, unsigned int, signop);
1026 static wide_int from_array (const HOST_WIDE_INT *, unsigned int,
1027 unsigned int, bool = true);
1028 static wide_int create (unsigned int);
1030 /* FIXME: target-dependent, so should disappear. */
1031 wide_int bswap () const;
1034 namespace wi
1036 template <>
1037 struct int_traits <wide_int_storage>
1039 static const enum precision_type precision_type = VAR_PRECISION;
1040 /* Guaranteed by a static assert in the wide_int_storage constructor. */
1041 static const bool host_dependent_precision = false;
1042 static const bool is_sign_extended = true;
1043 template <typename T1, typename T2>
1044 static wide_int get_binary_result (const T1 &, const T2 &);
1048 inline wide_int_storage::wide_int_storage () {}
1050 /* Initialize the storage from integer X, in its natural precision.
1051 Note that we do not allow integers with host-dependent precision
1052 to become wide_ints; wide_ints must always be logically independent
1053 of the host. */
1054 template <typename T>
1055 inline wide_int_storage::wide_int_storage (const T &x)
1057 { STATIC_ASSERT (!wi::int_traits<T>::host_dependent_precision); }
1058 { STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::CONST_PRECISION); }
1059 WIDE_INT_REF_FOR (T) xi (x);
1060 precision = xi.precision;
1061 wi::copy (*this, xi);
1064 template <typename T>
1065 inline wide_int_storage&
1066 wide_int_storage::operator = (const T &x)
1068 { STATIC_ASSERT (!wi::int_traits<T>::host_dependent_precision); }
1069 { STATIC_ASSERT (wi::int_traits<T>::precision_type != wi::CONST_PRECISION); }
1070 WIDE_INT_REF_FOR (T) xi (x);
1071 precision = xi.precision;
1072 wi::copy (*this, xi);
1073 return *this;
1076 inline unsigned int
1077 wide_int_storage::get_precision () const
1079 return precision;
1082 inline const HOST_WIDE_INT *
1083 wide_int_storage::get_val () const
1085 return val;
1088 inline unsigned int
1089 wide_int_storage::get_len () const
1091 return len;
1094 inline HOST_WIDE_INT *
1095 wide_int_storage::write_val ()
1097 return val;
1100 inline void
1101 wide_int_storage::set_len (unsigned int l, bool is_sign_extended)
1103 len = l;
1104 if (!is_sign_extended && len * HOST_BITS_PER_WIDE_INT > precision)
1105 val[len - 1] = sext_hwi (val[len - 1],
1106 precision % HOST_BITS_PER_WIDE_INT);
1109 /* Treat X as having signedness SGN and convert it to a PRECISION-bit
1110 number. */
1111 inline wide_int
1112 wide_int_storage::from (const wide_int_ref &x, unsigned int precision,
1113 signop sgn)
1115 wide_int result = wide_int::create (precision);
1116 result.set_len (wi::force_to_size (result.write_val (), x.val, x.len,
1117 x.precision, precision, sgn));
1118 return result;
1121 /* Create a wide_int from the explicit block encoding given by VAL and
1122 LEN. PRECISION is the precision of the integer. NEED_CANON_P is
1123 true if the encoding may have redundant trailing blocks. */
1124 inline wide_int
1125 wide_int_storage::from_array (const HOST_WIDE_INT *val, unsigned int len,
1126 unsigned int precision, bool need_canon_p)
1128 wide_int result = wide_int::create (precision);
1129 result.set_len (wi::from_array (result.write_val (), val, len, precision,
1130 need_canon_p));
1131 return result;
1134 /* Return an uninitialized wide_int with precision PRECISION. */
1135 inline wide_int
1136 wide_int_storage::create (unsigned int precision)
1138 wide_int x;
1139 x.precision = precision;
1140 return x;
1143 template <typename T1, typename T2>
1144 inline wide_int
1145 wi::int_traits <wide_int_storage>::get_binary_result (const T1 &x, const T2 &y)
1147 /* This shouldn't be used for two flexible-precision inputs. */
1148 STATIC_ASSERT (wi::int_traits <T1>::precision_type != FLEXIBLE_PRECISION
1149 || wi::int_traits <T2>::precision_type != FLEXIBLE_PRECISION);
1150 if (wi::int_traits <T1>::precision_type == FLEXIBLE_PRECISION)
1151 return wide_int::create (wi::get_precision (y));
1152 else
1153 return wide_int::create (wi::get_precision (x));
1156 /* The storage used by FIXED_WIDE_INT (N). */
1157 template <int N>
1158 class GTY(()) fixed_wide_int_storage
1160 private:
1161 HOST_WIDE_INT val[(N + HOST_BITS_PER_WIDE_INT + 1) / HOST_BITS_PER_WIDE_INT];
1162 unsigned int len;
1164 public:
1165 fixed_wide_int_storage ();
1166 template <typename T>
1167 fixed_wide_int_storage (const T &);
1169 /* The standard generic_wide_int storage methods. */
1170 unsigned int get_precision () const;
1171 const HOST_WIDE_INT *get_val () const;
1172 unsigned int get_len () const;
1173 HOST_WIDE_INT *write_val ();
1174 void set_len (unsigned int, bool = false);
1176 static FIXED_WIDE_INT (N) from (const wide_int_ref &, signop);
1177 static FIXED_WIDE_INT (N) from_array (const HOST_WIDE_INT *, unsigned int,
1178 bool = true);
1181 namespace wi
1183 template <int N>
1184 struct int_traits < fixed_wide_int_storage <N> >
1186 static const enum precision_type precision_type = CONST_PRECISION;
1187 static const bool host_dependent_precision = false;
1188 static const bool is_sign_extended = true;
1189 static const unsigned int precision = N;
1190 template <typename T1, typename T2>
1191 static FIXED_WIDE_INT (N) get_binary_result (const T1 &, const T2 &);
1195 template <int N>
1196 inline fixed_wide_int_storage <N>::fixed_wide_int_storage () {}
1198 /* Initialize the storage from integer X, in precision N. */
1199 template <int N>
1200 template <typename T>
1201 inline fixed_wide_int_storage <N>::fixed_wide_int_storage (const T &x)
1203 /* Check for type compatibility. We don't want to initialize a
1204 fixed-width integer from something like a wide_int. */
1205 WI_BINARY_RESULT (T, FIXED_WIDE_INT (N)) *assertion ATTRIBUTE_UNUSED;
1206 wi::copy (*this, WIDE_INT_REF_FOR (T) (x, N));
1209 template <int N>
1210 inline unsigned int
1211 fixed_wide_int_storage <N>::get_precision () const
1213 return N;
1216 template <int N>
1217 inline const HOST_WIDE_INT *
1218 fixed_wide_int_storage <N>::get_val () const
1220 return val;
1223 template <int N>
1224 inline unsigned int
1225 fixed_wide_int_storage <N>::get_len () const
1227 return len;
1230 template <int N>
1231 inline HOST_WIDE_INT *
1232 fixed_wide_int_storage <N>::write_val ()
1234 return val;
1237 template <int N>
1238 inline void
1239 fixed_wide_int_storage <N>::set_len (unsigned int l, bool)
1241 len = l;
1242 /* There are no excess bits in val[len - 1]. */
1243 STATIC_ASSERT (N % HOST_BITS_PER_WIDE_INT == 0);
1246 /* Treat X as having signedness SGN and convert it to an N-bit number. */
1247 template <int N>
1248 inline FIXED_WIDE_INT (N)
1249 fixed_wide_int_storage <N>::from (const wide_int_ref &x, signop sgn)
1251 FIXED_WIDE_INT (N) result;
1252 result.set_len (wi::force_to_size (result.write_val (), x.val, x.len,
1253 x.precision, N, sgn));
1254 return result;
1257 /* Create a FIXED_WIDE_INT (N) from the explicit block encoding given by
1258 VAL and LEN. NEED_CANON_P is true if the encoding may have redundant
1259 trailing blocks. */
1260 template <int N>
1261 inline FIXED_WIDE_INT (N)
1262 fixed_wide_int_storage <N>::from_array (const HOST_WIDE_INT *val,
1263 unsigned int len,
1264 bool need_canon_p)
1266 FIXED_WIDE_INT (N) result;
1267 result.set_len (wi::from_array (result.write_val (), val, len,
1268 N, need_canon_p));
1269 return result;
1272 template <int N>
1273 template <typename T1, typename T2>
1274 inline FIXED_WIDE_INT (N)
1275 wi::int_traits < fixed_wide_int_storage <N> >::
1276 get_binary_result (const T1 &, const T2 &)
1278 return FIXED_WIDE_INT (N) ();
1281 /* A reference to one element of a trailing_wide_ints structure. */
1282 class trailing_wide_int_storage
1284 private:
1285 /* The precision of the integer, which is a fixed property of the
1286 parent trailing_wide_ints. */
1287 unsigned int m_precision;
1289 /* A pointer to the length field. */
1290 unsigned char *m_len;
1292 /* A pointer to the HWI array. There are enough elements to hold all
1293 values of precision M_PRECISION. */
1294 HOST_WIDE_INT *m_val;
1296 public:
1297 trailing_wide_int_storage (unsigned int, unsigned char *, HOST_WIDE_INT *);
1299 /* The standard generic_wide_int storage methods. */
1300 unsigned int get_len () const;
1301 unsigned int get_precision () const;
1302 const HOST_WIDE_INT *get_val () const;
1303 HOST_WIDE_INT *write_val ();
1304 void set_len (unsigned int, bool = false);
1306 template <typename T>
1307 trailing_wide_int_storage &operator = (const T &);
1310 typedef generic_wide_int <trailing_wide_int_storage> trailing_wide_int;
1312 /* trailing_wide_int behaves like a wide_int. */
1313 namespace wi
1315 template <>
1316 struct int_traits <trailing_wide_int_storage>
1317 : public int_traits <wide_int_storage> {};
1320 /* An array of N wide_int-like objects that can be put at the end of
1321 a variable-sized structure. Use extra_size to calculate how many
1322 bytes beyond the sizeof need to be allocated. Use set_precision
1323 to initialize the structure. */
1324 template <int N>
1325 class GTY(()) trailing_wide_ints
1327 private:
1328 /* The shared precision of each number. */
1329 unsigned short m_precision;
1331 /* The shared maximum length of each number. */
1332 unsigned char m_max_len;
1334 /* The current length of each number. */
1335 unsigned char m_len[N];
1337 /* The variable-length part of the structure, which always contains
1338 at least one HWI. Element I starts at index I * M_MAX_LEN. */
1339 HOST_WIDE_INT m_val[1];
1341 public:
1342 void set_precision (unsigned int);
1343 trailing_wide_int operator [] (unsigned int);
1344 static size_t extra_size (unsigned int);
1347 inline trailing_wide_int_storage::
1348 trailing_wide_int_storage (unsigned int precision, unsigned char *len,
1349 HOST_WIDE_INT *val)
1350 : m_precision (precision), m_len (len), m_val (val)
1354 inline unsigned int
1355 trailing_wide_int_storage::get_len () const
1357 return *m_len;
1360 inline unsigned int
1361 trailing_wide_int_storage::get_precision () const
1363 return m_precision;
1366 inline const HOST_WIDE_INT *
1367 trailing_wide_int_storage::get_val () const
1369 return m_val;
1372 inline HOST_WIDE_INT *
1373 trailing_wide_int_storage::write_val ()
1375 return m_val;
1378 inline void
1379 trailing_wide_int_storage::set_len (unsigned int len, bool is_sign_extended)
1381 *m_len = len;
1382 if (!is_sign_extended && len * HOST_BITS_PER_WIDE_INT > m_precision)
1383 m_val[len - 1] = sext_hwi (m_val[len - 1],
1384 m_precision % HOST_BITS_PER_WIDE_INT);
1387 template <typename T>
1388 inline trailing_wide_int_storage &
1389 trailing_wide_int_storage::operator = (const T &x)
1391 WIDE_INT_REF_FOR (T) xi (x, m_precision);
1392 wi::copy (*this, xi);
1393 return *this;
1396 /* Initialize the structure and record that all elements have precision
1397 PRECISION. */
1398 template <int N>
1399 inline void
1400 trailing_wide_ints <N>::set_precision (unsigned int precision)
1402 m_precision = precision;
1403 m_max_len = ((precision + HOST_BITS_PER_WIDE_INT - 1)
1404 / HOST_BITS_PER_WIDE_INT);
1407 /* Return a reference to element INDEX. */
1408 template <int N>
1409 inline trailing_wide_int
1410 trailing_wide_ints <N>::operator [] (unsigned int index)
1412 return trailing_wide_int_storage (m_precision, &m_len[index],
1413 &m_val[index * m_max_len]);
1416 /* Return how many extra bytes need to be added to the end of the structure
1417 in order to handle N wide_ints of precision PRECISION. */
1418 template <int N>
1419 inline size_t
1420 trailing_wide_ints <N>::extra_size (unsigned int precision)
1422 unsigned int max_len = ((precision + HOST_BITS_PER_WIDE_INT - 1)
1423 / HOST_BITS_PER_WIDE_INT);
1424 return (N * max_len - 1) * sizeof (HOST_WIDE_INT);
1427 /* This macro is used in structures that end with a trailing_wide_ints field
1428 called FIELD. It declares get_NAME() and set_NAME() methods to access
1429 element I of FIELD. */
1430 #define TRAILING_WIDE_INT_ACCESSOR(NAME, FIELD, I) \
1431 trailing_wide_int get_##NAME () { return FIELD[I]; } \
1432 template <typename T> void set_##NAME (const T &x) { FIELD[I] = x; }
1434 namespace wi
1436 /* Implementation of int_traits for primitive integer types like "int". */
1437 template <typename T, bool signed_p>
1438 struct primitive_int_traits
1440 static const enum precision_type precision_type = FLEXIBLE_PRECISION;
1441 static const bool host_dependent_precision = true;
1442 static const bool is_sign_extended = true;
1443 static unsigned int get_precision (T);
1444 static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int, T);
1448 template <typename T, bool signed_p>
1449 inline unsigned int
1450 wi::primitive_int_traits <T, signed_p>::get_precision (T)
1452 return sizeof (T) * CHAR_BIT;
1455 template <typename T, bool signed_p>
1456 inline wi::storage_ref
1457 wi::primitive_int_traits <T, signed_p>::decompose (HOST_WIDE_INT *scratch,
1458 unsigned int precision, T x)
1460 scratch[0] = x;
1461 if (signed_p || scratch[0] >= 0 || precision <= HOST_BITS_PER_WIDE_INT)
1462 return wi::storage_ref (scratch, 1, precision);
1463 scratch[1] = 0;
1464 return wi::storage_ref (scratch, 2, precision);
1467 /* Allow primitive C types to be used in wi:: routines. */
1468 namespace wi
1470 template <>
1471 struct int_traits <unsigned char>
1472 : public primitive_int_traits <unsigned char, false> {};
1474 template <>
1475 struct int_traits <unsigned short>
1476 : public primitive_int_traits <unsigned short, false> {};
1478 template <>
1479 struct int_traits <int>
1480 : public primitive_int_traits <int, true> {};
1482 template <>
1483 struct int_traits <unsigned int>
1484 : public primitive_int_traits <unsigned int, false> {};
1486 template <>
1487 struct int_traits <long>
1488 : public primitive_int_traits <long, true> {};
1490 template <>
1491 struct int_traits <unsigned long>
1492 : public primitive_int_traits <unsigned long, false> {};
1494 #if defined HAVE_LONG_LONG
1495 template <>
1496 struct int_traits <long long>
1497 : public primitive_int_traits <long long, true> {};
1499 template <>
1500 struct int_traits <unsigned long long>
1501 : public primitive_int_traits <unsigned long long, false> {};
1502 #endif
1505 namespace wi
1507 /* Stores HWI-sized integer VAL, treating it as having signedness SGN
1508 and precision PRECISION. */
1509 struct hwi_with_prec
1511 hwi_with_prec (HOST_WIDE_INT, unsigned int, signop);
1512 HOST_WIDE_INT val;
1513 unsigned int precision;
1514 signop sgn;
1517 hwi_with_prec shwi (HOST_WIDE_INT, unsigned int);
1518 hwi_with_prec uhwi (unsigned HOST_WIDE_INT, unsigned int);
1520 hwi_with_prec minus_one (unsigned int);
1521 hwi_with_prec zero (unsigned int);
1522 hwi_with_prec one (unsigned int);
1523 hwi_with_prec two (unsigned int);
1526 inline wi::hwi_with_prec::hwi_with_prec (HOST_WIDE_INT v, unsigned int p,
1527 signop s)
1528 : precision (p), sgn (s)
1530 if (precision < HOST_BITS_PER_WIDE_INT)
1531 val = sext_hwi (v, precision);
1532 else
1533 val = v;
1536 /* Return a signed integer that has value VAL and precision PRECISION. */
1537 inline wi::hwi_with_prec
1538 wi::shwi (HOST_WIDE_INT val, unsigned int precision)
1540 return hwi_with_prec (val, precision, SIGNED);
1543 /* Return an unsigned integer that has value VAL and precision PRECISION. */
1544 inline wi::hwi_with_prec
1545 wi::uhwi (unsigned HOST_WIDE_INT val, unsigned int precision)
1547 return hwi_with_prec (val, precision, UNSIGNED);
1550 /* Return a wide int of -1 with precision PRECISION. */
1551 inline wi::hwi_with_prec
1552 wi::minus_one (unsigned int precision)
1554 return wi::shwi (-1, precision);
1557 /* Return a wide int of 0 with precision PRECISION. */
1558 inline wi::hwi_with_prec
1559 wi::zero (unsigned int precision)
1561 return wi::shwi (0, precision);
1564 /* Return a wide int of 1 with precision PRECISION. */
1565 inline wi::hwi_with_prec
1566 wi::one (unsigned int precision)
1568 return wi::shwi (1, precision);
1571 /* Return a wide int of 2 with precision PRECISION. */
1572 inline wi::hwi_with_prec
1573 wi::two (unsigned int precision)
1575 return wi::shwi (2, precision);
1578 namespace wi
1580 template <>
1581 struct int_traits <wi::hwi_with_prec>
1583 static const enum precision_type precision_type = VAR_PRECISION;
1584 /* hwi_with_prec has an explicitly-given precision, rather than the
1585 precision of HOST_WIDE_INT. */
1586 static const bool host_dependent_precision = false;
1587 static const bool is_sign_extended = true;
1588 static unsigned int get_precision (const wi::hwi_with_prec &);
1589 static wi::storage_ref decompose (HOST_WIDE_INT *, unsigned int,
1590 const wi::hwi_with_prec &);
1594 inline unsigned int
1595 wi::int_traits <wi::hwi_with_prec>::get_precision (const wi::hwi_with_prec &x)
1597 return x.precision;
1600 inline wi::storage_ref
1601 wi::int_traits <wi::hwi_with_prec>::
1602 decompose (HOST_WIDE_INT *scratch, unsigned int precision,
1603 const wi::hwi_with_prec &x)
1605 gcc_checking_assert (precision == x.precision);
1606 scratch[0] = x.val;
1607 if (x.sgn == SIGNED || x.val >= 0 || precision <= HOST_BITS_PER_WIDE_INT)
1608 return wi::storage_ref (scratch, 1, precision);
1609 scratch[1] = 0;
1610 return wi::storage_ref (scratch, 2, precision);
1613 /* Private functions for handling large cases out of line. They take
1614 individual length and array parameters because that is cheaper for
1615 the inline caller than constructing an object on the stack and
1616 passing a reference to it. (Although many callers use wide_int_refs,
1617 we generally want those to be removed by SRA.) */
1618 namespace wi
1620 bool eq_p_large (const HOST_WIDE_INT *, unsigned int,
1621 const HOST_WIDE_INT *, unsigned int, unsigned int);
1622 bool lts_p_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
1623 const HOST_WIDE_INT *, unsigned int);
1624 bool ltu_p_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
1625 const HOST_WIDE_INT *, unsigned int);
1626 int cmps_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
1627 const HOST_WIDE_INT *, unsigned int);
1628 int cmpu_large (const HOST_WIDE_INT *, unsigned int, unsigned int,
1629 const HOST_WIDE_INT *, unsigned int);
1630 unsigned int sext_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1631 unsigned int,
1632 unsigned int, unsigned int);
1633 unsigned int zext_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1634 unsigned int,
1635 unsigned int, unsigned int);
1636 unsigned int set_bit_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1637 unsigned int, unsigned int, unsigned int);
1638 unsigned int lshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1639 unsigned int, unsigned int, unsigned int);
1640 unsigned int lrshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1641 unsigned int, unsigned int, unsigned int,
1642 unsigned int);
1643 unsigned int arshift_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1644 unsigned int, unsigned int, unsigned int,
1645 unsigned int);
1646 unsigned int and_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
1647 const HOST_WIDE_INT *, unsigned int, unsigned int);
1648 unsigned int and_not_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1649 unsigned int, const HOST_WIDE_INT *,
1650 unsigned int, unsigned int);
1651 unsigned int or_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
1652 const HOST_WIDE_INT *, unsigned int, unsigned int);
1653 unsigned int or_not_large (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1654 unsigned int, const HOST_WIDE_INT *,
1655 unsigned int, unsigned int);
1656 unsigned int xor_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
1657 const HOST_WIDE_INT *, unsigned int, unsigned int);
1658 unsigned int add_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
1659 const HOST_WIDE_INT *, unsigned int, unsigned int,
1660 signop, bool *);
1661 unsigned int sub_large (HOST_WIDE_INT *, const HOST_WIDE_INT *, unsigned int,
1662 const HOST_WIDE_INT *, unsigned int, unsigned int,
1663 signop, bool *);
1664 unsigned int mul_internal (HOST_WIDE_INT *, const HOST_WIDE_INT *,
1665 unsigned int, const HOST_WIDE_INT *,
1666 unsigned int, unsigned int, signop, bool *,
1667 bool);
1668 unsigned int divmod_internal (HOST_WIDE_INT *, unsigned int *,
1669 HOST_WIDE_INT *, const HOST_WIDE_INT *,
1670 unsigned int, unsigned int,
1671 const HOST_WIDE_INT *,
1672 unsigned int, unsigned int,
1673 signop, bool *);
1676 /* Return the number of bits that integer X can hold. */
1677 template <typename T>
1678 inline unsigned int
1679 wi::get_precision (const T &x)
1681 return wi::int_traits <T>::get_precision (x);
1684 /* Return the number of bits that the result of a binary operation can
1685 hold when the input operands are X and Y. */
1686 template <typename T1, typename T2>
1687 inline unsigned int
1688 wi::get_binary_precision (const T1 &x, const T2 &y)
1690 return get_precision (wi::int_traits <WI_BINARY_RESULT (T1, T2)>::
1691 get_binary_result (x, y));
1694 /* Copy the contents of Y to X, but keeping X's current precision. */
1695 template <typename T1, typename T2>
1696 inline void
1697 wi::copy (T1 &x, const T2 &y)
1699 HOST_WIDE_INT *xval = x.write_val ();
1700 const HOST_WIDE_INT *yval = y.get_val ();
1701 unsigned int len = y.get_len ();
1702 unsigned int i = 0;
1704 xval[i] = yval[i];
1705 while (++i < len);
1706 x.set_len (len, y.is_sign_extended);
1709 /* Return true if X fits in a HOST_WIDE_INT with no loss of precision. */
1710 template <typename T>
1711 inline bool
1712 wi::fits_shwi_p (const T &x)
1714 WIDE_INT_REF_FOR (T) xi (x);
1715 return xi.len == 1;
1718 /* Return true if X fits in an unsigned HOST_WIDE_INT with no loss of
1719 precision. */
1720 template <typename T>
1721 inline bool
1722 wi::fits_uhwi_p (const T &x)
1724 WIDE_INT_REF_FOR (T) xi (x);
1725 if (xi.precision <= HOST_BITS_PER_WIDE_INT)
1726 return true;
1727 if (xi.len == 1)
1728 return xi.slow () >= 0;
1729 return xi.len == 2 && xi.uhigh () == 0;
1732 /* Return true if X is negative based on the interpretation of SGN.
1733 For UNSIGNED, this is always false. */
1734 template <typename T>
1735 inline bool
1736 wi::neg_p (const T &x, signop sgn)
1738 WIDE_INT_REF_FOR (T) xi (x);
1739 if (sgn == UNSIGNED)
1740 return false;
1741 return xi.sign_mask () < 0;
1744 /* Return -1 if the top bit of X is set and 0 if the top bit is clear. */
1745 template <typename T>
1746 inline HOST_WIDE_INT
1747 wi::sign_mask (const T &x)
1749 WIDE_INT_REF_FOR (T) xi (x);
1750 return xi.sign_mask ();
1753 /* Return true if X == Y. X and Y must be binary-compatible. */
1754 template <typename T1, typename T2>
1755 inline bool
1756 wi::eq_p (const T1 &x, const T2 &y)
1758 unsigned int precision = get_binary_precision (x, y);
1759 WIDE_INT_REF_FOR (T1) xi (x, precision);
1760 WIDE_INT_REF_FOR (T2) yi (y, precision);
1761 if (xi.is_sign_extended && yi.is_sign_extended)
1763 /* This case reduces to array equality. */
1764 if (xi.len != yi.len)
1765 return false;
1766 unsigned int i = 0;
1768 if (xi.val[i] != yi.val[i])
1769 return false;
1770 while (++i != xi.len);
1771 return true;
1773 if (__builtin_expect (yi.len == 1, true))
1775 /* XI is only equal to YI if it too has a single HWI. */
1776 if (xi.len != 1)
1777 return false;
1778 /* Excess bits in xi.val[0] will be signs or zeros, so comparisons
1779 with 0 are simple. */
1780 if (STATIC_CONSTANT_P (yi.val[0] == 0))
1781 return xi.val[0] == 0;
1782 /* Otherwise flush out any excess bits first. */
1783 unsigned HOST_WIDE_INT diff = xi.val[0] ^ yi.val[0];
1784 int excess = HOST_BITS_PER_WIDE_INT - precision;
1785 if (excess > 0)
1786 diff <<= excess;
1787 return diff == 0;
1789 return eq_p_large (xi.val, xi.len, yi.val, yi.len, precision);
1792 /* Return true if X != Y. X and Y must be binary-compatible. */
1793 template <typename T1, typename T2>
1794 inline bool
1795 wi::ne_p (const T1 &x, const T2 &y)
1797 return !eq_p (x, y);
1800 /* Return true if X < Y when both are treated as signed values. */
1801 template <typename T1, typename T2>
1802 inline bool
1803 wi::lts_p (const T1 &x, const T2 &y)
1805 unsigned int precision = get_binary_precision (x, y);
1806 WIDE_INT_REF_FOR (T1) xi (x, precision);
1807 WIDE_INT_REF_FOR (T2) yi (y, precision);
1808 /* We optimize x < y, where y is 64 or fewer bits. */
1809 if (wi::fits_shwi_p (yi))
1811 /* Make lts_p (x, 0) as efficient as wi::neg_p (x). */
1812 if (STATIC_CONSTANT_P (yi.val[0] == 0))
1813 return neg_p (xi);
1814 /* If x fits directly into a shwi, we can compare directly. */
1815 if (wi::fits_shwi_p (xi))
1816 return xi.to_shwi () < yi.to_shwi ();
1817 /* If x doesn't fit and is negative, then it must be more
1818 negative than any value in y, and hence smaller than y. */
1819 if (neg_p (xi))
1820 return true;
1821 /* If x is positive, then it must be larger than any value in y,
1822 and hence greater than y. */
1823 return false;
1825 /* Optimize the opposite case, if it can be detected at compile time. */
1826 if (STATIC_CONSTANT_P (xi.len == 1))
1827 /* If YI is negative it is lower than the least HWI.
1828 If YI is positive it is greater than the greatest HWI. */
1829 return !neg_p (yi);
1830 return lts_p_large (xi.val, xi.len, precision, yi.val, yi.len);
1833 /* Return true if X < Y when both are treated as unsigned values. */
1834 template <typename T1, typename T2>
1835 inline bool
1836 wi::ltu_p (const T1 &x, const T2 &y)
1838 unsigned int precision = get_binary_precision (x, y);
1839 WIDE_INT_REF_FOR (T1) xi (x, precision);
1840 WIDE_INT_REF_FOR (T2) yi (y, precision);
1841 /* Optimize comparisons with constants. */
1842 if (STATIC_CONSTANT_P (yi.len == 1 && yi.val[0] >= 0))
1843 return xi.len == 1 && xi.to_uhwi () < (unsigned HOST_WIDE_INT) yi.val[0];
1844 if (STATIC_CONSTANT_P (xi.len == 1 && xi.val[0] >= 0))
1845 return yi.len != 1 || yi.to_uhwi () > (unsigned HOST_WIDE_INT) xi.val[0];
1846 /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
1847 for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
1848 values does not change the result. */
1849 if (__builtin_expect (xi.len + yi.len == 2, true))
1851 unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
1852 unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
1853 return xl < yl;
1855 return ltu_p_large (xi.val, xi.len, precision, yi.val, yi.len);
1858 /* Return true if X < Y. Signedness of X and Y is indicated by SGN. */
1859 template <typename T1, typename T2>
1860 inline bool
1861 wi::lt_p (const T1 &x, const T2 &y, signop sgn)
1863 if (sgn == SIGNED)
1864 return lts_p (x, y);
1865 else
1866 return ltu_p (x, y);
1869 /* Return true if X <= Y when both are treated as signed values. */
1870 template <typename T1, typename T2>
1871 inline bool
1872 wi::les_p (const T1 &x, const T2 &y)
1874 return !lts_p (y, x);
1877 /* Return true if X <= Y when both are treated as unsigned values. */
1878 template <typename T1, typename T2>
1879 inline bool
1880 wi::leu_p (const T1 &x, const T2 &y)
1882 return !ltu_p (y, x);
1885 /* Return true if X <= Y. Signedness of X and Y is indicated by SGN. */
1886 template <typename T1, typename T2>
1887 inline bool
1888 wi::le_p (const T1 &x, const T2 &y, signop sgn)
1890 if (sgn == SIGNED)
1891 return les_p (x, y);
1892 else
1893 return leu_p (x, y);
1896 /* Return true if X > Y when both are treated as signed values. */
1897 template <typename T1, typename T2>
1898 inline bool
1899 wi::gts_p (const T1 &x, const T2 &y)
1901 return lts_p (y, x);
1904 /* Return true if X > Y when both are treated as unsigned values. */
1905 template <typename T1, typename T2>
1906 inline bool
1907 wi::gtu_p (const T1 &x, const T2 &y)
1909 return ltu_p (y, x);
1912 /* Return true if X > Y. Signedness of X and Y is indicated by SGN. */
1913 template <typename T1, typename T2>
1914 inline bool
1915 wi::gt_p (const T1 &x, const T2 &y, signop sgn)
1917 if (sgn == SIGNED)
1918 return gts_p (x, y);
1919 else
1920 return gtu_p (x, y);
1923 /* Return true if X >= Y when both are treated as signed values. */
1924 template <typename T1, typename T2>
1925 inline bool
1926 wi::ges_p (const T1 &x, const T2 &y)
1928 return !lts_p (x, y);
1931 /* Return true if X >= Y when both are treated as unsigned values. */
1932 template <typename T1, typename T2>
1933 inline bool
1934 wi::geu_p (const T1 &x, const T2 &y)
1936 return !ltu_p (x, y);
1939 /* Return true if X >= Y. Signedness of X and Y is indicated by SGN. */
1940 template <typename T1, typename T2>
1941 inline bool
1942 wi::ge_p (const T1 &x, const T2 &y, signop sgn)
1944 if (sgn == SIGNED)
1945 return ges_p (x, y);
1946 else
1947 return geu_p (x, y);
1950 /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
1951 as signed values. */
1952 template <typename T1, typename T2>
1953 inline int
1954 wi::cmps (const T1 &x, const T2 &y)
1956 unsigned int precision = get_binary_precision (x, y);
1957 WIDE_INT_REF_FOR (T1) xi (x, precision);
1958 WIDE_INT_REF_FOR (T2) yi (y, precision);
1959 if (wi::fits_shwi_p (yi))
1961 /* Special case for comparisons with 0. */
1962 if (STATIC_CONSTANT_P (yi.val[0] == 0))
1963 return neg_p (xi) ? -1 : !(xi.len == 1 && xi.val[0] == 0);
1964 /* If x fits into a signed HWI, we can compare directly. */
1965 if (wi::fits_shwi_p (xi))
1967 HOST_WIDE_INT xl = xi.to_shwi ();
1968 HOST_WIDE_INT yl = yi.to_shwi ();
1969 return xl < yl ? -1 : xl > yl;
1971 /* If x doesn't fit and is negative, then it must be more
1972 negative than any signed HWI, and hence smaller than y. */
1973 if (neg_p (xi))
1974 return -1;
1975 /* If x is positive, then it must be larger than any signed HWI,
1976 and hence greater than y. */
1977 return 1;
1979 /* Optimize the opposite case, if it can be detected at compile time. */
1980 if (STATIC_CONSTANT_P (xi.len == 1))
1981 /* If YI is negative it is lower than the least HWI.
1982 If YI is positive it is greater than the greatest HWI. */
1983 return neg_p (yi) ? 1 : -1;
1984 return cmps_large (xi.val, xi.len, precision, yi.val, yi.len);
1987 /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Treat both X and Y
1988 as unsigned values. */
1989 template <typename T1, typename T2>
1990 inline int
1991 wi::cmpu (const T1 &x, const T2 &y)
1993 unsigned int precision = get_binary_precision (x, y);
1994 WIDE_INT_REF_FOR (T1) xi (x, precision);
1995 WIDE_INT_REF_FOR (T2) yi (y, precision);
1996 /* Optimize comparisons with constants. */
1997 if (STATIC_CONSTANT_P (yi.len == 1 && yi.val[0] >= 0))
1999 /* If XI doesn't fit in a HWI then it must be larger than YI. */
2000 if (xi.len != 1)
2001 return 1;
2002 /* Otherwise compare directly. */
2003 unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2004 unsigned HOST_WIDE_INT yl = yi.val[0];
2005 return xl < yl ? -1 : xl > yl;
2007 if (STATIC_CONSTANT_P (xi.len == 1 && xi.val[0] >= 0))
2009 /* If YI doesn't fit in a HWI then it must be larger than XI. */
2010 if (yi.len != 1)
2011 return -1;
2012 /* Otherwise compare directly. */
2013 unsigned HOST_WIDE_INT xl = xi.val[0];
2014 unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2015 return xl < yl ? -1 : xl > yl;
2017 /* Optimize the case of two HWIs. The HWIs are implicitly sign-extended
2018 for precisions greater than HOST_BITS_WIDE_INT, but sign-extending both
2019 values does not change the result. */
2020 if (__builtin_expect (xi.len + yi.len == 2, true))
2022 unsigned HOST_WIDE_INT xl = xi.to_uhwi ();
2023 unsigned HOST_WIDE_INT yl = yi.to_uhwi ();
2024 return xl < yl ? -1 : xl > yl;
2026 return cmpu_large (xi.val, xi.len, precision, yi.val, yi.len);
2029 /* Return -1 if X < Y, 0 if X == Y and 1 if X > Y. Signedness of
2030 X and Y indicated by SGN. */
2031 template <typename T1, typename T2>
2032 inline int
2033 wi::cmp (const T1 &x, const T2 &y, signop sgn)
2035 if (sgn == SIGNED)
2036 return cmps (x, y);
2037 else
2038 return cmpu (x, y);
2041 /* Return ~x. */
2042 template <typename T>
2043 inline WI_UNARY_RESULT (T)
2044 wi::bit_not (const T &x)
2046 WI_UNARY_RESULT_VAR (result, val, T, x);
2047 WIDE_INT_REF_FOR (T) xi (x, get_precision (result));
2048 for (unsigned int i = 0; i < xi.len; ++i)
2049 val[i] = ~xi.val[i];
2050 result.set_len (xi.len);
2051 return result;
2054 /* Return -x. */
2055 template <typename T>
2056 inline WI_UNARY_RESULT (T)
2057 wi::neg (const T &x)
2059 return sub (0, x);
2062 /* Return -x. Indicate in *OVERFLOW if X is the minimum signed value. */
2063 template <typename T>
2064 inline WI_UNARY_RESULT (T)
2065 wi::neg (const T &x, bool *overflow)
2067 *overflow = only_sign_bit_p (x);
2068 return sub (0, x);
2071 /* Return the absolute value of x. */
2072 template <typename T>
2073 inline WI_UNARY_RESULT (T)
2074 wi::abs (const T &x)
2076 return neg_p (x) ? neg (x) : WI_UNARY_RESULT (T) (x);
2079 /* Return the result of sign-extending the low OFFSET bits of X. */
2080 template <typename T>
2081 inline WI_UNARY_RESULT (T)
2082 wi::sext (const T &x, unsigned int offset)
2084 WI_UNARY_RESULT_VAR (result, val, T, x);
2085 unsigned int precision = get_precision (result);
2086 WIDE_INT_REF_FOR (T) xi (x, precision);
2088 if (offset <= HOST_BITS_PER_WIDE_INT)
2090 val[0] = sext_hwi (xi.ulow (), offset);
2091 result.set_len (1, true);
2093 else
2094 result.set_len (sext_large (val, xi.val, xi.len, precision, offset));
2095 return result;
2098 /* Return the result of zero-extending the low OFFSET bits of X. */
2099 template <typename T>
2100 inline WI_UNARY_RESULT (T)
2101 wi::zext (const T &x, unsigned int offset)
2103 WI_UNARY_RESULT_VAR (result, val, T, x);
2104 unsigned int precision = get_precision (result);
2105 WIDE_INT_REF_FOR (T) xi (x, precision);
2107 /* This is not just an optimization, it is actually required to
2108 maintain canonization. */
2109 if (offset >= precision)
2111 wi::copy (result, xi);
2112 return result;
2115 /* In these cases we know that at least the top bit will be clear,
2116 so no sign extension is necessary. */
2117 if (offset < HOST_BITS_PER_WIDE_INT)
2119 val[0] = zext_hwi (xi.ulow (), offset);
2120 result.set_len (1, true);
2122 else
2123 result.set_len (zext_large (val, xi.val, xi.len, precision, offset), true);
2124 return result;
2127 /* Return the result of extending the low OFFSET bits of X according to
2128 signedness SGN. */
2129 template <typename T>
2130 inline WI_UNARY_RESULT (T)
2131 wi::ext (const T &x, unsigned int offset, signop sgn)
2133 return sgn == SIGNED ? sext (x, offset) : zext (x, offset);
2136 /* Return an integer that represents X | (1 << bit). */
2137 template <typename T>
2138 inline WI_UNARY_RESULT (T)
2139 wi::set_bit (const T &x, unsigned int bit)
2141 WI_UNARY_RESULT_VAR (result, val, T, x);
2142 unsigned int precision = get_precision (result);
2143 WIDE_INT_REF_FOR (T) xi (x, precision);
2144 if (precision <= HOST_BITS_PER_WIDE_INT)
2146 val[0] = xi.ulow () | (HOST_WIDE_INT_1U << bit);
2147 result.set_len (1);
2149 else
2150 result.set_len (set_bit_large (val, xi.val, xi.len, precision, bit));
2151 return result;
2154 /* Return the mininum of X and Y, treating them both as having
2155 signedness SGN. */
2156 template <typename T1, typename T2>
2157 inline WI_BINARY_RESULT (T1, T2)
2158 wi::min (const T1 &x, const T2 &y, signop sgn)
2160 WI_BINARY_RESULT_VAR (result, val ATTRIBUTE_UNUSED, T1, x, T2, y);
2161 unsigned int precision = get_precision (result);
2162 if (wi::le_p (x, y, sgn))
2163 wi::copy (result, WIDE_INT_REF_FOR (T1) (x, precision));
2164 else
2165 wi::copy (result, WIDE_INT_REF_FOR (T2) (y, precision));
2166 return result;
2169 /* Return the minimum of X and Y, treating both as signed values. */
2170 template <typename T1, typename T2>
2171 inline WI_BINARY_RESULT (T1, T2)
2172 wi::smin (const T1 &x, const T2 &y)
2174 return wi::min (x, y, SIGNED);
2177 /* Return the minimum of X and Y, treating both as unsigned values. */
2178 template <typename T1, typename T2>
2179 inline WI_BINARY_RESULT (T1, T2)
2180 wi::umin (const T1 &x, const T2 &y)
2182 return wi::min (x, y, UNSIGNED);
2185 /* Return the maxinum of X and Y, treating them both as having
2186 signedness SGN. */
2187 template <typename T1, typename T2>
2188 inline WI_BINARY_RESULT (T1, T2)
2189 wi::max (const T1 &x, const T2 &y, signop sgn)
2191 WI_BINARY_RESULT_VAR (result, val ATTRIBUTE_UNUSED, T1, x, T2, y);
2192 unsigned int precision = get_precision (result);
2193 if (wi::ge_p (x, y, sgn))
2194 wi::copy (result, WIDE_INT_REF_FOR (T1) (x, precision));
2195 else
2196 wi::copy (result, WIDE_INT_REF_FOR (T2) (y, precision));
2197 return result;
2200 /* Return the maximum of X and Y, treating both as signed values. */
2201 template <typename T1, typename T2>
2202 inline WI_BINARY_RESULT (T1, T2)
2203 wi::smax (const T1 &x, const T2 &y)
2205 return wi::max (x, y, SIGNED);
2208 /* Return the maximum of X and Y, treating both as unsigned values. */
2209 template <typename T1, typename T2>
2210 inline WI_BINARY_RESULT (T1, T2)
2211 wi::umax (const T1 &x, const T2 &y)
2213 return wi::max (x, y, UNSIGNED);
2216 /* Return X & Y. */
2217 template <typename T1, typename T2>
2218 inline WI_BINARY_RESULT (T1, T2)
2219 wi::bit_and (const T1 &x, const T2 &y)
2221 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2222 unsigned int precision = get_precision (result);
2223 WIDE_INT_REF_FOR (T1) xi (x, precision);
2224 WIDE_INT_REF_FOR (T2) yi (y, precision);
2225 bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2226 if (__builtin_expect (xi.len + yi.len == 2, true))
2228 val[0] = xi.ulow () & yi.ulow ();
2229 result.set_len (1, is_sign_extended);
2231 else
2232 result.set_len (and_large (val, xi.val, xi.len, yi.val, yi.len,
2233 precision), is_sign_extended);
2234 return result;
2237 /* Return X & ~Y. */
2238 template <typename T1, typename T2>
2239 inline WI_BINARY_RESULT (T1, T2)
2240 wi::bit_and_not (const T1 &x, const T2 &y)
2242 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2243 unsigned int precision = get_precision (result);
2244 WIDE_INT_REF_FOR (T1) xi (x, precision);
2245 WIDE_INT_REF_FOR (T2) yi (y, precision);
2246 bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2247 if (__builtin_expect (xi.len + yi.len == 2, true))
2249 val[0] = xi.ulow () & ~yi.ulow ();
2250 result.set_len (1, is_sign_extended);
2252 else
2253 result.set_len (and_not_large (val, xi.val, xi.len, yi.val, yi.len,
2254 precision), is_sign_extended);
2255 return result;
2258 /* Return X | Y. */
2259 template <typename T1, typename T2>
2260 inline WI_BINARY_RESULT (T1, T2)
2261 wi::bit_or (const T1 &x, const T2 &y)
2263 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2264 unsigned int precision = get_precision (result);
2265 WIDE_INT_REF_FOR (T1) xi (x, precision);
2266 WIDE_INT_REF_FOR (T2) yi (y, precision);
2267 bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2268 if (__builtin_expect (xi.len + yi.len == 2, true))
2270 val[0] = xi.ulow () | yi.ulow ();
2271 result.set_len (1, is_sign_extended);
2273 else
2274 result.set_len (or_large (val, xi.val, xi.len,
2275 yi.val, yi.len, precision), is_sign_extended);
2276 return result;
2279 /* Return X | ~Y. */
2280 template <typename T1, typename T2>
2281 inline WI_BINARY_RESULT (T1, T2)
2282 wi::bit_or_not (const T1 &x, const T2 &y)
2284 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2285 unsigned int precision = get_precision (result);
2286 WIDE_INT_REF_FOR (T1) xi (x, precision);
2287 WIDE_INT_REF_FOR (T2) yi (y, precision);
2288 bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2289 if (__builtin_expect (xi.len + yi.len == 2, true))
2291 val[0] = xi.ulow () | ~yi.ulow ();
2292 result.set_len (1, is_sign_extended);
2294 else
2295 result.set_len (or_not_large (val, xi.val, xi.len, yi.val, yi.len,
2296 precision), is_sign_extended);
2297 return result;
2300 /* Return X ^ Y. */
2301 template <typename T1, typename T2>
2302 inline WI_BINARY_RESULT (T1, T2)
2303 wi::bit_xor (const T1 &x, const T2 &y)
2305 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2306 unsigned int precision = get_precision (result);
2307 WIDE_INT_REF_FOR (T1) xi (x, precision);
2308 WIDE_INT_REF_FOR (T2) yi (y, precision);
2309 bool is_sign_extended = xi.is_sign_extended && yi.is_sign_extended;
2310 if (__builtin_expect (xi.len + yi.len == 2, true))
2312 val[0] = xi.ulow () ^ yi.ulow ();
2313 result.set_len (1, is_sign_extended);
2315 else
2316 result.set_len (xor_large (val, xi.val, xi.len,
2317 yi.val, yi.len, precision), is_sign_extended);
2318 return result;
2321 /* Return X + Y. */
2322 template <typename T1, typename T2>
2323 inline WI_BINARY_RESULT (T1, T2)
2324 wi::add (const T1 &x, const T2 &y)
2326 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2327 unsigned int precision = get_precision (result);
2328 WIDE_INT_REF_FOR (T1) xi (x, precision);
2329 WIDE_INT_REF_FOR (T2) yi (y, precision);
2330 if (precision <= HOST_BITS_PER_WIDE_INT)
2332 val[0] = xi.ulow () + yi.ulow ();
2333 result.set_len (1);
2335 /* If the precision is known at compile time to be greater than
2336 HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2337 knowing that (a) all bits in those HWIs are significant and
2338 (b) the result has room for at least two HWIs. This provides
2339 a fast path for things like offset_int and widest_int.
2341 The STATIC_CONSTANT_P test prevents this path from being
2342 used for wide_ints. wide_ints with precisions greater than
2343 HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2344 point handling them inline. */
2345 else if (STATIC_CONSTANT_P (precision > HOST_BITS_PER_WIDE_INT)
2346 && __builtin_expect (xi.len + yi.len == 2, true))
2348 unsigned HOST_WIDE_INT xl = xi.ulow ();
2349 unsigned HOST_WIDE_INT yl = yi.ulow ();
2350 unsigned HOST_WIDE_INT resultl = xl + yl;
2351 val[0] = resultl;
2352 val[1] = (HOST_WIDE_INT) resultl < 0 ? 0 : -1;
2353 result.set_len (1 + (((resultl ^ xl) & (resultl ^ yl))
2354 >> (HOST_BITS_PER_WIDE_INT - 1)));
2356 else
2357 result.set_len (add_large (val, xi.val, xi.len,
2358 yi.val, yi.len, precision,
2359 UNSIGNED, 0));
2360 return result;
2363 /* Return X + Y. Treat X and Y as having the signednes given by SGN
2364 and indicate in *OVERFLOW whether the operation overflowed. */
2365 template <typename T1, typename T2>
2366 inline WI_BINARY_RESULT (T1, T2)
2367 wi::add (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2369 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2370 unsigned int precision = get_precision (result);
2371 WIDE_INT_REF_FOR (T1) xi (x, precision);
2372 WIDE_INT_REF_FOR (T2) yi (y, precision);
2373 if (precision <= HOST_BITS_PER_WIDE_INT)
2375 unsigned HOST_WIDE_INT xl = xi.ulow ();
2376 unsigned HOST_WIDE_INT yl = yi.ulow ();
2377 unsigned HOST_WIDE_INT resultl = xl + yl;
2378 if (sgn == SIGNED)
2379 *overflow = (((resultl ^ xl) & (resultl ^ yl))
2380 >> (precision - 1)) & 1;
2381 else
2382 *overflow = ((resultl << (HOST_BITS_PER_WIDE_INT - precision))
2383 < (xl << (HOST_BITS_PER_WIDE_INT - precision)));
2384 val[0] = resultl;
2385 result.set_len (1);
2387 else
2388 result.set_len (add_large (val, xi.val, xi.len,
2389 yi.val, yi.len, precision,
2390 sgn, overflow));
2391 return result;
2394 /* Return X - Y. */
2395 template <typename T1, typename T2>
2396 inline WI_BINARY_RESULT (T1, T2)
2397 wi::sub (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 ();
2406 result.set_len (1);
2408 /* If the precision is known at compile time to be greater than
2409 HOST_BITS_PER_WIDE_INT, we can optimize the single-HWI case
2410 knowing that (a) all bits in those HWIs are significant and
2411 (b) the result has room for at least two HWIs. This provides
2412 a fast path for things like offset_int and widest_int.
2414 The STATIC_CONSTANT_P test prevents this path from being
2415 used for wide_ints. wide_ints with precisions greater than
2416 HOST_BITS_PER_WIDE_INT are relatively rare and there's not much
2417 point handling them inline. */
2418 else if (STATIC_CONSTANT_P (precision > HOST_BITS_PER_WIDE_INT)
2419 && __builtin_expect (xi.len + yi.len == 2, true))
2421 unsigned HOST_WIDE_INT xl = xi.ulow ();
2422 unsigned HOST_WIDE_INT yl = yi.ulow ();
2423 unsigned HOST_WIDE_INT resultl = xl - yl;
2424 val[0] = resultl;
2425 val[1] = (HOST_WIDE_INT) resultl < 0 ? 0 : -1;
2426 result.set_len (1 + (((resultl ^ xl) & (xl ^ yl))
2427 >> (HOST_BITS_PER_WIDE_INT - 1)));
2429 else
2430 result.set_len (sub_large (val, xi.val, xi.len,
2431 yi.val, yi.len, precision,
2432 UNSIGNED, 0));
2433 return result;
2436 /* Return X - Y. Treat X and Y as having the signednes given by SGN
2437 and indicate in *OVERFLOW whether the operation overflowed. */
2438 template <typename T1, typename T2>
2439 inline WI_BINARY_RESULT (T1, T2)
2440 wi::sub (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2442 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2443 unsigned int precision = get_precision (result);
2444 WIDE_INT_REF_FOR (T1) xi (x, precision);
2445 WIDE_INT_REF_FOR (T2) yi (y, precision);
2446 if (precision <= HOST_BITS_PER_WIDE_INT)
2448 unsigned HOST_WIDE_INT xl = xi.ulow ();
2449 unsigned HOST_WIDE_INT yl = yi.ulow ();
2450 unsigned HOST_WIDE_INT resultl = xl - yl;
2451 if (sgn == SIGNED)
2452 *overflow = (((xl ^ yl) & (resultl ^ xl)) >> (precision - 1)) & 1;
2453 else
2454 *overflow = ((resultl << (HOST_BITS_PER_WIDE_INT - precision))
2455 > (xl << (HOST_BITS_PER_WIDE_INT - precision)));
2456 val[0] = resultl;
2457 result.set_len (1);
2459 else
2460 result.set_len (sub_large (val, xi.val, xi.len,
2461 yi.val, yi.len, precision,
2462 sgn, overflow));
2463 return result;
2466 /* Return X * Y. */
2467 template <typename T1, typename T2>
2468 inline WI_BINARY_RESULT (T1, T2)
2469 wi::mul (const T1 &x, const T2 &y)
2471 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2472 unsigned int precision = get_precision (result);
2473 WIDE_INT_REF_FOR (T1) xi (x, precision);
2474 WIDE_INT_REF_FOR (T2) yi (y, precision);
2475 if (precision <= HOST_BITS_PER_WIDE_INT)
2477 val[0] = xi.ulow () * yi.ulow ();
2478 result.set_len (1);
2480 else
2481 result.set_len (mul_internal (val, xi.val, xi.len, yi.val, yi.len,
2482 precision, UNSIGNED, 0, false));
2483 return result;
2486 /* Return X * Y. Treat X and Y as having the signednes given by SGN
2487 and indicate in *OVERFLOW whether the operation overflowed. */
2488 template <typename T1, typename T2>
2489 inline WI_BINARY_RESULT (T1, T2)
2490 wi::mul (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2492 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2493 unsigned int precision = get_precision (result);
2494 WIDE_INT_REF_FOR (T1) xi (x, precision);
2495 WIDE_INT_REF_FOR (T2) yi (y, precision);
2496 result.set_len (mul_internal (val, xi.val, xi.len,
2497 yi.val, yi.len, precision,
2498 sgn, overflow, false));
2499 return result;
2502 /* Return X * Y, treating both X and Y as signed values. Indicate in
2503 *OVERFLOW whether the operation overflowed. */
2504 template <typename T1, typename T2>
2505 inline WI_BINARY_RESULT (T1, T2)
2506 wi::smul (const T1 &x, const T2 &y, bool *overflow)
2508 return mul (x, y, SIGNED, overflow);
2511 /* Return X * Y, treating both X and Y as unsigned values. Indicate in
2512 *OVERFLOW whether the operation overflowed. */
2513 template <typename T1, typename T2>
2514 inline WI_BINARY_RESULT (T1, T2)
2515 wi::umul (const T1 &x, const T2 &y, bool *overflow)
2517 return mul (x, y, UNSIGNED, overflow);
2520 /* Perform a widening multiplication of X and Y, extending the values
2521 according to SGN, and return the high part of the result. */
2522 template <typename T1, typename T2>
2523 inline WI_BINARY_RESULT (T1, T2)
2524 wi::mul_high (const T1 &x, const T2 &y, signop sgn)
2526 WI_BINARY_RESULT_VAR (result, val, T1, x, T2, y);
2527 unsigned int precision = get_precision (result);
2528 WIDE_INT_REF_FOR (T1) xi (x, precision);
2529 WIDE_INT_REF_FOR (T2) yi (y, precision);
2530 result.set_len (mul_internal (val, xi.val, xi.len,
2531 yi.val, yi.len, precision,
2532 sgn, 0, true));
2533 return result;
2536 /* Return X / Y, rouding towards 0. Treat X and Y as having the
2537 signedness given by SGN. Indicate in *OVERFLOW if the result
2538 overflows. */
2539 template <typename T1, typename T2>
2540 inline WI_BINARY_RESULT (T1, T2)
2541 wi::div_trunc (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2543 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2544 unsigned int precision = get_precision (quotient);
2545 WIDE_INT_REF_FOR (T1) xi (x, precision);
2546 WIDE_INT_REF_FOR (T2) yi (y);
2548 quotient.set_len (divmod_internal (quotient_val, 0, 0, xi.val, xi.len,
2549 precision,
2550 yi.val, yi.len, yi.precision,
2551 sgn, overflow));
2552 return quotient;
2555 /* Return X / Y, rouding towards 0. Treat X and Y as signed values. */
2556 template <typename T1, typename T2>
2557 inline WI_BINARY_RESULT (T1, T2)
2558 wi::sdiv_trunc (const T1 &x, const T2 &y)
2560 return div_trunc (x, y, SIGNED);
2563 /* Return X / Y, rouding towards 0. Treat X and Y as unsigned values. */
2564 template <typename T1, typename T2>
2565 inline WI_BINARY_RESULT (T1, T2)
2566 wi::udiv_trunc (const T1 &x, const T2 &y)
2568 return div_trunc (x, y, UNSIGNED);
2571 /* Return X / Y, rouding towards -inf. Treat X and Y as having the
2572 signedness given by SGN. Indicate in *OVERFLOW if the result
2573 overflows. */
2574 template <typename T1, typename T2>
2575 inline WI_BINARY_RESULT (T1, T2)
2576 wi::div_floor (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2578 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2579 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2580 unsigned int precision = get_precision (quotient);
2581 WIDE_INT_REF_FOR (T1) xi (x, precision);
2582 WIDE_INT_REF_FOR (T2) yi (y);
2584 unsigned int remainder_len;
2585 quotient.set_len (divmod_internal (quotient_val,
2586 &remainder_len, remainder_val,
2587 xi.val, xi.len, precision,
2588 yi.val, yi.len, yi.precision, sgn,
2589 overflow));
2590 remainder.set_len (remainder_len);
2591 if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn) && remainder != 0)
2592 return quotient - 1;
2593 return quotient;
2596 /* Return X / Y, rouding towards -inf. Treat X and Y as signed values. */
2597 template <typename T1, typename T2>
2598 inline WI_BINARY_RESULT (T1, T2)
2599 wi::sdiv_floor (const T1 &x, const T2 &y)
2601 return div_floor (x, y, SIGNED);
2604 /* Return X / Y, rouding towards -inf. Treat X and Y as unsigned values. */
2605 /* ??? Why do we have both this and udiv_trunc. Aren't they the same? */
2606 template <typename T1, typename T2>
2607 inline WI_BINARY_RESULT (T1, T2)
2608 wi::udiv_floor (const T1 &x, const T2 &y)
2610 return div_floor (x, y, UNSIGNED);
2613 /* Return X / Y, rouding towards +inf. Treat X and Y as having the
2614 signedness given by SGN. Indicate in *OVERFLOW if the result
2615 overflows. */
2616 template <typename T1, typename T2>
2617 inline WI_BINARY_RESULT (T1, T2)
2618 wi::div_ceil (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2620 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2621 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2622 unsigned int precision = get_precision (quotient);
2623 WIDE_INT_REF_FOR (T1) xi (x, precision);
2624 WIDE_INT_REF_FOR (T2) yi (y);
2626 unsigned int remainder_len;
2627 quotient.set_len (divmod_internal (quotient_val,
2628 &remainder_len, remainder_val,
2629 xi.val, xi.len, precision,
2630 yi.val, yi.len, yi.precision, sgn,
2631 overflow));
2632 remainder.set_len (remainder_len);
2633 if (wi::neg_p (x, sgn) == wi::neg_p (y, sgn) && remainder != 0)
2634 return quotient + 1;
2635 return quotient;
2638 /* Return X / Y, rouding towards nearest with ties away from zero.
2639 Treat X and Y as having the signedness given by SGN. Indicate
2640 in *OVERFLOW if the result overflows. */
2641 template <typename T1, typename T2>
2642 inline WI_BINARY_RESULT (T1, T2)
2643 wi::div_round (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2645 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2646 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2647 unsigned int precision = get_precision (quotient);
2648 WIDE_INT_REF_FOR (T1) xi (x, precision);
2649 WIDE_INT_REF_FOR (T2) yi (y);
2651 unsigned int remainder_len;
2652 quotient.set_len (divmod_internal (quotient_val,
2653 &remainder_len, remainder_val,
2654 xi.val, xi.len, precision,
2655 yi.val, yi.len, yi.precision, sgn,
2656 overflow));
2657 remainder.set_len (remainder_len);
2659 if (remainder != 0)
2661 if (sgn == SIGNED)
2663 WI_BINARY_RESULT (T1, T2) abs_remainder = wi::abs (remainder);
2664 if (wi::geu_p (abs_remainder, wi::sub (wi::abs (y), abs_remainder)))
2666 if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn))
2667 return quotient - 1;
2668 else
2669 return quotient + 1;
2672 else
2674 if (wi::geu_p (remainder, wi::sub (y, remainder)))
2675 return quotient + 1;
2678 return quotient;
2681 /* Return X / Y, rouding towards 0. Treat X and Y as having the
2682 signedness given by SGN. Store the remainder in *REMAINDER_PTR. */
2683 template <typename T1, typename T2>
2684 inline WI_BINARY_RESULT (T1, T2)
2685 wi::divmod_trunc (const T1 &x, const T2 &y, signop sgn,
2686 WI_BINARY_RESULT (T1, T2) *remainder_ptr)
2688 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2689 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2690 unsigned int precision = get_precision (quotient);
2691 WIDE_INT_REF_FOR (T1) xi (x, precision);
2692 WIDE_INT_REF_FOR (T2) yi (y);
2694 unsigned int remainder_len;
2695 quotient.set_len (divmod_internal (quotient_val,
2696 &remainder_len, remainder_val,
2697 xi.val, xi.len, precision,
2698 yi.val, yi.len, yi.precision, sgn, 0));
2699 remainder.set_len (remainder_len);
2701 *remainder_ptr = remainder;
2702 return quotient;
2705 /* Compute the greatest common divisor of two numbers A and B using
2706 Euclid's algorithm. */
2707 template <typename T1, typename T2>
2708 inline WI_BINARY_RESULT (T1, T2)
2709 wi::gcd (const T1 &a, const T2 &b, signop sgn)
2711 T1 x, y, z;
2713 x = wi::abs (a);
2714 y = wi::abs (b);
2716 while (gt_p (x, 0, sgn))
2718 z = mod_trunc (y, x, sgn);
2719 y = x;
2720 x = z;
2723 return y;
2726 /* Compute X / Y, rouding towards 0, and return the remainder.
2727 Treat X and Y as having the signedness given by SGN. Indicate
2728 in *OVERFLOW if the division overflows. */
2729 template <typename T1, typename T2>
2730 inline WI_BINARY_RESULT (T1, T2)
2731 wi::mod_trunc (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2733 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2734 unsigned int precision = get_precision (remainder);
2735 WIDE_INT_REF_FOR (T1) xi (x, precision);
2736 WIDE_INT_REF_FOR (T2) yi (y);
2738 unsigned int remainder_len;
2739 divmod_internal (0, &remainder_len, remainder_val,
2740 xi.val, xi.len, precision,
2741 yi.val, yi.len, yi.precision, sgn, overflow);
2742 remainder.set_len (remainder_len);
2744 return remainder;
2747 /* Compute X / Y, rouding towards 0, and return the remainder.
2748 Treat X and Y as signed values. */
2749 template <typename T1, typename T2>
2750 inline WI_BINARY_RESULT (T1, T2)
2751 wi::smod_trunc (const T1 &x, const T2 &y)
2753 return mod_trunc (x, y, SIGNED);
2756 /* Compute X / Y, rouding towards 0, and return the remainder.
2757 Treat X and Y as unsigned values. */
2758 template <typename T1, typename T2>
2759 inline WI_BINARY_RESULT (T1, T2)
2760 wi::umod_trunc (const T1 &x, const T2 &y)
2762 return mod_trunc (x, y, UNSIGNED);
2765 /* Compute X / Y, rouding towards -inf, and return the remainder.
2766 Treat X and Y as having the signedness given by SGN. Indicate
2767 in *OVERFLOW if the division overflows. */
2768 template <typename T1, typename T2>
2769 inline WI_BINARY_RESULT (T1, T2)
2770 wi::mod_floor (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2772 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2773 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2774 unsigned int precision = get_precision (quotient);
2775 WIDE_INT_REF_FOR (T1) xi (x, precision);
2776 WIDE_INT_REF_FOR (T2) yi (y);
2778 unsigned int remainder_len;
2779 quotient.set_len (divmod_internal (quotient_val,
2780 &remainder_len, remainder_val,
2781 xi.val, xi.len, precision,
2782 yi.val, yi.len, yi.precision, sgn,
2783 overflow));
2784 remainder.set_len (remainder_len);
2786 if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn) && remainder != 0)
2787 return remainder + y;
2788 return remainder;
2791 /* Compute X / Y, rouding towards -inf, and return the remainder.
2792 Treat X and Y as unsigned values. */
2793 /* ??? Why do we have both this and umod_trunc. Aren't they the same? */
2794 template <typename T1, typename T2>
2795 inline WI_BINARY_RESULT (T1, T2)
2796 wi::umod_floor (const T1 &x, const T2 &y)
2798 return mod_floor (x, y, UNSIGNED);
2801 /* Compute X / Y, rouding towards +inf, and return the remainder.
2802 Treat X and Y as having the signedness given by SGN. Indicate
2803 in *OVERFLOW if the division overflows. */
2804 template <typename T1, typename T2>
2805 inline WI_BINARY_RESULT (T1, T2)
2806 wi::mod_ceil (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2808 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2809 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2810 unsigned int precision = get_precision (quotient);
2811 WIDE_INT_REF_FOR (T1) xi (x, precision);
2812 WIDE_INT_REF_FOR (T2) yi (y);
2814 unsigned int remainder_len;
2815 quotient.set_len (divmod_internal (quotient_val,
2816 &remainder_len, remainder_val,
2817 xi.val, xi.len, precision,
2818 yi.val, yi.len, yi.precision, sgn,
2819 overflow));
2820 remainder.set_len (remainder_len);
2822 if (wi::neg_p (x, sgn) == wi::neg_p (y, sgn) && remainder != 0)
2823 return remainder - y;
2824 return remainder;
2827 /* Compute X / Y, rouding towards nearest with ties away from zero,
2828 and return the remainder. Treat X and Y as having the signedness
2829 given by SGN. Indicate in *OVERFLOW if the division overflows. */
2830 template <typename T1, typename T2>
2831 inline WI_BINARY_RESULT (T1, T2)
2832 wi::mod_round (const T1 &x, const T2 &y, signop sgn, bool *overflow)
2834 WI_BINARY_RESULT_VAR (quotient, quotient_val, T1, x, T2, y);
2835 WI_BINARY_RESULT_VAR (remainder, remainder_val, T1, x, T2, y);
2836 unsigned int precision = get_precision (quotient);
2837 WIDE_INT_REF_FOR (T1) xi (x, precision);
2838 WIDE_INT_REF_FOR (T2) yi (y);
2840 unsigned int remainder_len;
2841 quotient.set_len (divmod_internal (quotient_val,
2842 &remainder_len, remainder_val,
2843 xi.val, xi.len, precision,
2844 yi.val, yi.len, yi.precision, sgn,
2845 overflow));
2846 remainder.set_len (remainder_len);
2848 if (remainder != 0)
2850 if (sgn == SIGNED)
2852 WI_BINARY_RESULT (T1, T2) abs_remainder = wi::abs (remainder);
2853 if (wi::geu_p (abs_remainder, wi::sub (wi::abs (y), abs_remainder)))
2855 if (wi::neg_p (x, sgn) != wi::neg_p (y, sgn))
2856 return remainder + y;
2857 else
2858 return remainder - y;
2861 else
2863 if (wi::geu_p (remainder, wi::sub (y, remainder)))
2864 return remainder - y;
2867 return remainder;
2870 /* Return true if X is a multiple of Y. Treat X and Y as having the
2871 signedness given by SGN. */
2872 template <typename T1, typename T2>
2873 inline bool
2874 wi::multiple_of_p (const T1 &x, const T2 &y, signop sgn)
2876 return wi::mod_trunc (x, y, sgn) == 0;
2879 /* Return true if X is a multiple of Y, storing X / Y in *RES if so.
2880 Treat X and Y as having the signedness given by SGN. */
2881 template <typename T1, typename T2>
2882 inline bool
2883 wi::multiple_of_p (const T1 &x, const T2 &y, signop sgn,
2884 WI_BINARY_RESULT (T1, T2) *res)
2886 WI_BINARY_RESULT (T1, T2) remainder;
2887 WI_BINARY_RESULT (T1, T2) quotient
2888 = divmod_trunc (x, y, sgn, &remainder);
2889 if (remainder == 0)
2891 *res = quotient;
2892 return true;
2894 return false;
2897 /* Return X << Y. Return 0 if Y is greater than or equal to
2898 the precision of X. */
2899 template <typename T1, typename T2>
2900 inline WI_UNARY_RESULT (T1)
2901 wi::lshift (const T1 &x, const T2 &y)
2903 WI_UNARY_RESULT_VAR (result, val, T1, x);
2904 unsigned int precision = get_precision (result);
2905 WIDE_INT_REF_FOR (T1) xi (x, precision);
2906 WIDE_INT_REF_FOR (T2) yi (y);
2907 /* Handle the simple cases quickly. */
2908 if (geu_p (yi, precision))
2910 val[0] = 0;
2911 result.set_len (1);
2913 else
2915 unsigned int shift = yi.to_uhwi ();
2916 /* For fixed-precision integers like offset_int and widest_int,
2917 handle the case where the shift value is constant and the
2918 result is a single nonnegative HWI (meaning that we don't
2919 need to worry about val[1]). This is particularly common
2920 for converting a byte count to a bit count.
2922 For variable-precision integers like wide_int, handle HWI
2923 and sub-HWI integers inline. */
2924 if (STATIC_CONSTANT_P (xi.precision > HOST_BITS_PER_WIDE_INT)
2925 ? (STATIC_CONSTANT_P (shift < HOST_BITS_PER_WIDE_INT - 1)
2926 && xi.len == 1
2927 && xi.val[0] <= (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT)
2928 HOST_WIDE_INT_MAX >> shift))
2929 : precision <= HOST_BITS_PER_WIDE_INT)
2931 val[0] = xi.ulow () << shift;
2932 result.set_len (1);
2934 else
2935 result.set_len (lshift_large (val, xi.val, xi.len,
2936 precision, shift));
2938 return result;
2941 /* Return X >> Y, using a logical shift. Return 0 if Y is greater than
2942 or equal to the precision of X. */
2943 template <typename T1, typename T2>
2944 inline WI_UNARY_RESULT (T1)
2945 wi::lrshift (const T1 &x, const T2 &y)
2947 WI_UNARY_RESULT_VAR (result, val, T1, x);
2948 /* Do things in the precision of the input rather than the output,
2949 since the result can be no larger than that. */
2950 WIDE_INT_REF_FOR (T1) xi (x);
2951 WIDE_INT_REF_FOR (T2) yi (y);
2952 /* Handle the simple cases quickly. */
2953 if (geu_p (yi, xi.precision))
2955 val[0] = 0;
2956 result.set_len (1);
2958 else
2960 unsigned int shift = yi.to_uhwi ();
2961 /* For fixed-precision integers like offset_int and widest_int,
2962 handle the case where the shift value is constant and the
2963 shifted value is a single nonnegative HWI (meaning that all
2964 bits above the HWI are zero). This is particularly common
2965 for converting a bit count to a byte count.
2967 For variable-precision integers like wide_int, handle HWI
2968 and sub-HWI integers inline. */
2969 if (STATIC_CONSTANT_P (xi.precision > HOST_BITS_PER_WIDE_INT)
2970 ? (shift < HOST_BITS_PER_WIDE_INT
2971 && xi.len == 1
2972 && xi.val[0] >= 0)
2973 : xi.precision <= HOST_BITS_PER_WIDE_INT)
2975 val[0] = xi.to_uhwi () >> shift;
2976 result.set_len (1);
2978 else
2979 result.set_len (lrshift_large (val, xi.val, xi.len, xi.precision,
2980 get_precision (result), shift));
2982 return result;
2985 /* Return X >> Y, using an arithmetic shift. Return a sign mask if
2986 Y is greater than or equal to the precision of X. */
2987 template <typename T1, typename T2>
2988 inline WI_UNARY_RESULT (T1)
2989 wi::arshift (const T1 &x, const T2 &y)
2991 WI_UNARY_RESULT_VAR (result, val, T1, x);
2992 /* Do things in the precision of the input rather than the output,
2993 since the result can be no larger than that. */
2994 WIDE_INT_REF_FOR (T1) xi (x);
2995 WIDE_INT_REF_FOR (T2) yi (y);
2996 /* Handle the simple cases quickly. */
2997 if (geu_p (yi, xi.precision))
2999 val[0] = sign_mask (x);
3000 result.set_len (1);
3002 else
3004 unsigned int shift = yi.to_uhwi ();
3005 if (xi.precision <= HOST_BITS_PER_WIDE_INT)
3007 val[0] = sext_hwi (xi.ulow () >> shift, xi.precision - shift);
3008 result.set_len (1, true);
3010 else
3011 result.set_len (arshift_large (val, xi.val, xi.len, xi.precision,
3012 get_precision (result), shift));
3014 return result;
3017 /* Return X >> Y, using an arithmetic shift if SGN is SIGNED and a
3018 logical shift otherwise. */
3019 template <typename T1, typename T2>
3020 inline WI_UNARY_RESULT (T1)
3021 wi::rshift (const T1 &x, const T2 &y, signop sgn)
3023 if (sgn == UNSIGNED)
3024 return lrshift (x, y);
3025 else
3026 return arshift (x, y);
3029 /* Return the result of rotating the low WIDTH bits of X left by Y
3030 bits and zero-extending the result. Use a full-width rotate if
3031 WIDTH is zero. */
3032 template <typename T1, typename T2>
3033 WI_UNARY_RESULT (T1)
3034 wi::lrotate (const T1 &x, const T2 &y, unsigned int width)
3036 unsigned int precision = get_binary_precision (x, x);
3037 if (width == 0)
3038 width = precision;
3039 WI_UNARY_RESULT (T2) ymod = umod_trunc (y, width);
3040 WI_UNARY_RESULT (T1) left = wi::lshift (x, ymod);
3041 WI_UNARY_RESULT (T1) right = wi::lrshift (x, wi::sub (width, ymod));
3042 if (width != precision)
3043 return wi::zext (left, width) | wi::zext (right, width);
3044 return left | right;
3047 /* Return the result of rotating the low WIDTH bits of X right by Y
3048 bits and zero-extending the result. Use a full-width rotate if
3049 WIDTH is zero. */
3050 template <typename T1, typename T2>
3051 WI_UNARY_RESULT (T1)
3052 wi::rrotate (const T1 &x, const T2 &y, unsigned int width)
3054 unsigned int precision = get_binary_precision (x, x);
3055 if (width == 0)
3056 width = precision;
3057 WI_UNARY_RESULT (T2) ymod = umod_trunc (y, width);
3058 WI_UNARY_RESULT (T1) right = wi::lrshift (x, ymod);
3059 WI_UNARY_RESULT (T1) left = wi::lshift (x, wi::sub (width, ymod));
3060 if (width != precision)
3061 return wi::zext (left, width) | wi::zext (right, width);
3062 return left | right;
3065 /* Return 0 if the number of 1s in X is even and 1 if the number of 1s
3066 is odd. */
3067 inline int
3068 wi::parity (const wide_int_ref &x)
3070 return popcount (x) & 1;
3073 /* Extract WIDTH bits from X, starting at BITPOS. */
3074 template <typename T>
3075 inline unsigned HOST_WIDE_INT
3076 wi::extract_uhwi (const T &x, unsigned int bitpos, unsigned int width)
3078 unsigned precision = get_precision (x);
3079 if (precision < bitpos + width)
3080 precision = bitpos + width;
3081 WIDE_INT_REF_FOR (T) xi (x, precision);
3083 /* Handle this rare case after the above, so that we assert about
3084 bogus BITPOS values. */
3085 if (width == 0)
3086 return 0;
3088 unsigned int start = bitpos / HOST_BITS_PER_WIDE_INT;
3089 unsigned int shift = bitpos % HOST_BITS_PER_WIDE_INT;
3090 unsigned HOST_WIDE_INT res = xi.elt (start);
3091 res >>= shift;
3092 if (shift + width > HOST_BITS_PER_WIDE_INT)
3094 unsigned HOST_WIDE_INT upper = xi.elt (start + 1);
3095 res |= upper << (-shift % HOST_BITS_PER_WIDE_INT);
3097 return zext_hwi (res, width);
3100 /* Return the minimum precision needed to store X with sign SGN. */
3101 template <typename T>
3102 inline unsigned int
3103 wi::min_precision (const T &x, signop sgn)
3105 if (sgn == SIGNED)
3106 return get_precision (x) - clrsb (x);
3107 else
3108 return get_precision (x) - clz (x);
3111 #define SIGNED_BINARY_PREDICATE(OP, F) \
3112 template <typename T1, typename T2> \
3113 inline WI_SIGNED_BINARY_PREDICATE_RESULT (T1, T2) \
3114 OP (const T1 &x, const T2 &y) \
3116 return wi::F (x, y); \
3119 SIGNED_BINARY_PREDICATE (operator <, lts_p)
3120 SIGNED_BINARY_PREDICATE (operator <=, les_p)
3121 SIGNED_BINARY_PREDICATE (operator >, gts_p)
3122 SIGNED_BINARY_PREDICATE (operator >=, ges_p)
3124 #undef SIGNED_BINARY_PREDICATE
3126 template <typename T1, typename T2>
3127 inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3128 operator << (const T1 &x, const T2 &y)
3130 return wi::lshift (x, y);
3133 template <typename T1, typename T2>
3134 inline WI_SIGNED_SHIFT_RESULT (T1, T2)
3135 operator >> (const T1 &x, const T2 &y)
3137 return wi::arshift (x, y);
3140 template<typename T>
3141 void
3142 gt_ggc_mx (generic_wide_int <T> *)
3146 template<typename T>
3147 void
3148 gt_pch_nx (generic_wide_int <T> *)
3152 template<typename T>
3153 void
3154 gt_pch_nx (generic_wide_int <T> *, void (*) (void *, void *), void *)
3158 template<int N>
3159 void
3160 gt_ggc_mx (trailing_wide_ints <N> *)
3164 template<int N>
3165 void
3166 gt_pch_nx (trailing_wide_ints <N> *)
3170 template<int N>
3171 void
3172 gt_pch_nx (trailing_wide_ints <N> *, void (*) (void *, void *), void *)
3176 namespace wi
3178 /* Used for overloaded functions in which the only other acceptable
3179 scalar type is a pointer. It stops a plain 0 from being treated
3180 as a null pointer. */
3181 struct never_used1 {};
3182 struct never_used2 {};
3184 wide_int min_value (unsigned int, signop);
3185 wide_int min_value (never_used1 *);
3186 wide_int min_value (never_used2 *);
3187 wide_int max_value (unsigned int, signop);
3188 wide_int max_value (never_used1 *);
3189 wide_int max_value (never_used2 *);
3191 /* FIXME: this is target dependent, so should be elsewhere.
3192 It also seems to assume that CHAR_BIT == BITS_PER_UNIT. */
3193 wide_int from_buffer (const unsigned char *, unsigned int);
3195 #ifndef GENERATOR_FILE
3196 void to_mpz (const wide_int_ref &, mpz_t, signop);
3197 #endif
3199 wide_int mask (unsigned int, bool, unsigned int);
3200 wide_int shifted_mask (unsigned int, unsigned int, bool, unsigned int);
3201 wide_int set_bit_in_zero (unsigned int, unsigned int);
3202 wide_int insert (const wide_int &x, const wide_int &y, unsigned int,
3203 unsigned int);
3205 template <typename T>
3206 T mask (unsigned int, bool);
3208 template <typename T>
3209 T shifted_mask (unsigned int, unsigned int, bool);
3211 template <typename T>
3212 T set_bit_in_zero (unsigned int);
3214 unsigned int mask (HOST_WIDE_INT *, unsigned int, bool, unsigned int);
3215 unsigned int shifted_mask (HOST_WIDE_INT *, unsigned int, unsigned int,
3216 bool, unsigned int);
3217 unsigned int from_array (HOST_WIDE_INT *, const HOST_WIDE_INT *,
3218 unsigned int, unsigned int, bool);
3221 /* Return a PRECISION-bit integer in which the low WIDTH bits are set
3222 and the other bits are clear, or the inverse if NEGATE_P. */
3223 inline wide_int
3224 wi::mask (unsigned int width, bool negate_p, unsigned int precision)
3226 wide_int result = wide_int::create (precision);
3227 result.set_len (mask (result.write_val (), width, negate_p, precision));
3228 return result;
3231 /* Return a PRECISION-bit integer in which the low START bits are clear,
3232 the next WIDTH bits are set, and the other bits are clear,
3233 or the inverse if NEGATE_P. */
3234 inline wide_int
3235 wi::shifted_mask (unsigned int start, unsigned int width, bool negate_p,
3236 unsigned int precision)
3238 wide_int result = wide_int::create (precision);
3239 result.set_len (shifted_mask (result.write_val (), start, width, negate_p,
3240 precision));
3241 return result;
3244 /* Return a PRECISION-bit integer in which bit BIT is set and all the
3245 others are clear. */
3246 inline wide_int
3247 wi::set_bit_in_zero (unsigned int bit, unsigned int precision)
3249 return shifted_mask (bit, 1, false, precision);
3252 /* Return an integer of type T in which the low WIDTH bits are set
3253 and the other bits are clear, or the inverse if NEGATE_P. */
3254 template <typename T>
3255 inline T
3256 wi::mask (unsigned int width, bool negate_p)
3258 STATIC_ASSERT (wi::int_traits<T>::precision);
3259 T result;
3260 result.set_len (mask (result.write_val (), width, negate_p,
3261 wi::int_traits <T>::precision));
3262 return result;
3265 /* Return an integer of type T in which the low START bits are clear,
3266 the next WIDTH bits are set, and the other bits are clear, or the
3267 inverse if NEGATE_P. */
3268 template <typename T>
3269 inline T
3270 wi::shifted_mask (unsigned int start, unsigned int width, bool negate_p)
3272 STATIC_ASSERT (wi::int_traits<T>::precision);
3273 T result;
3274 result.set_len (shifted_mask (result.write_val (), start, width,
3275 negate_p,
3276 wi::int_traits <T>::precision));
3277 return result;
3280 /* Return an integer of type T in which bit BIT is set and all the
3281 others are clear. */
3282 template <typename T>
3283 inline T
3284 wi::set_bit_in_zero (unsigned int bit)
3286 return shifted_mask <T> (bit, 1, false);
3289 #endif /* WIDE_INT_H */