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

source code of gcc/wide-int.h