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