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