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