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