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