wide-int.h source code [gcc/wide-int.h]

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

Browse the source code of gcc/wide-int.h