gcc/sreal.cc

   1 /* Simple data type for real numbers for the GNU compiler.
   2    Copyright (C) 2002-2023 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 under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 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 /* This library supports real numbers;
  21    inf and nan are NOT supported.
  22    It is written to be simple and fast.
  23
  24    Value of sreal is
  25         x = sig * 2 ^ exp
  26    where
  27         sig = significant
  28           (for < 64-bit machines sig = sig_lo + sig_hi * 2 ^ SREAL_PART_BITS)
  29         exp = exponent
  30
  31    One uint64_t is used for the significant.
  32    Only a half of significant bits is used (in normalized sreals) so that we do
  33    not have problems with overflow, for example when c->sig = a->sig * b->sig.
  34    So the precision is 32-bit.
  35
  36    Invariant: The numbers are normalized before and after each call of sreal_*.
  37
  38    Normalized sreals:
  39    All numbers (except zero) meet following conditions:
  40          SREAL_MIN_SIG <= sig && sig <= SREAL_MAX_SIG
  41         -SREAL_MAX_EXP <= exp && exp <= SREAL_MAX_EXP
  42
  43    If the number would be too large, it is set to upper bounds of these
  44    conditions.
  45
  46    If the number is zero or would be too small it meets following conditions:
  47         sig == 0 && exp == -SREAL_MAX_EXP
  48 */
  49
  50 #include "config.h"
  51 #include "system.h"
  52 #include <math.h>
  53 #include "coretypes.h"
  54 #include "sreal.h"
  55 #include "selftest.h"
  56 #include "backend.h"
  57 #include "tree.h"
  58 #include "gimple.h"
  59 #include "cgraph.h"
  60 #include "data-streamer.h"
  61
  62 /* Print the content of struct sreal.  */
  63
  64 void
  65 sreal::dump (FILE *file) const
  66 {
  67   fprintf (file, "(%" PRIi64 " * 2^%d)", (int64_t)m_sig, m_exp);
  68 }
  69
  70 DEBUG_FUNCTION void
  71 debug (const sreal &ref)
  72 {
  73   ref.dump (stderr);
  74 }
  75
  76 DEBUG_FUNCTION void
  77 debug (const sreal *ptr)
  78 {
  79   if (ptr)
  80     debug (*ptr);
  81   else
  82     fprintf (stderr, "<nil>\n");
  83 }
  84
  85 /* Shift this right by S bits.  Needed: 0 < S <= SREAL_BITS.
  86    When the most significant bit shifted out is 1, add 1 to this (rounding).
  87    */
  88
  89 void
  90 sreal::shift_right (int s)
  91 {
  92   gcc_checking_assert (s > 0);
  93   gcc_checking_assert (s <= SREAL_BITS);
  94   /* Exponent should never be so large because shift_right is used only by
  95      sreal_add and sreal_sub ant thus the number cannot be shifted out from
  96      exponent range.  */
  97   gcc_checking_assert (m_exp + s <= SREAL_MAX_EXP);
  98
  99   m_exp += s;
 100
 101   m_sig += (int64_t) 1 << (s - 1);
 102   m_sig >>= s;
 103 }
 104
 105 /* Return integer value of *this.  */
 106
 107 int64_t
 108 sreal::to_int () const
 109 {
 110   int64_t sign = SREAL_SIGN (m_sig);
 111
 112   if (m_exp <= -SREAL_BITS)
 113     return 0;
 114   if (m_exp >= SREAL_PART_BITS)
 115     return sign * INTTYPE_MAXIMUM (int64_t);
 116   if (m_exp > 0)
 117     return sign * (SREAL_ABS ((int64_t)m_sig) << m_exp);
 118   if (m_exp < 0)
 119     return sign * (SREAL_ABS ((int64_t)m_sig) >> -m_exp);
 120   return m_sig;
 121 }
 122
 123 /* Return nearest integer value of *this.  */
 124
 125 int64_t
 126 sreal::to_nearest_int () const
 127 {
 128   int64_t sign = SREAL_SIGN (m_sig);
 129
 130   if (m_exp <= -SREAL_BITS)
 131     return 0;
 132   if (m_exp >= SREAL_PART_BITS)
 133     return sign * INTTYPE_MAXIMUM (int64_t);
 134   if (m_exp > 0)
 135     return sign * (SREAL_ABS ((int64_t)m_sig) << m_exp);
 136   if (m_exp < 0)
 137     return sign * ((SREAL_ABS ((int64_t)m_sig) >> -m_exp)
 138                    + ((SREAL_ABS (m_sig) >> (-m_exp - 1)) & 1));
 139   return m_sig;
 140 }
 141
 142 /* Return value of *this as double.
 143    This should be used for debug output only.  */
 144
 145 double
 146 sreal::to_double () const
 147 {
 148   double val = m_sig;
 149   if (m_exp)
 150     val = ldexp (val, m_exp);
 151   return val;
 152 }
 153
 154 /* Return *this + other.  */
 155
 156 sreal
 157 sreal::operator+ (const sreal &other) const
 158 {
 159   int dexp;
 160   sreal tmp;
 161   int64_t r_sig, r_exp;
 162
 163   const sreal *a_p = this, *b_p = &other, *bb;
 164
 165   if (a_p->m_exp < b_p->m_exp)
 166     std::swap (a_p, b_p);
 167
 168   dexp = a_p->m_exp - b_p->m_exp;
 169   r_exp = a_p->m_exp;
 170   if (dexp > SREAL_BITS)
 171     {
 172       r_sig = a_p->m_sig;
 173
 174       sreal r;
 175       r.m_sig = r_sig;
 176       r.m_exp = r_exp;
 177       return r;
 178     }
 179
 180   if (dexp == 0)
 181     bb = b_p;
 182   else
 183     {
 184       tmp = *b_p;
 185       tmp.shift_right (dexp);
 186       bb = &tmp;
 187     }
 188
 189   r_sig = a_p->m_sig + (int64_t)bb->m_sig;
 190   sreal r (r_sig, r_exp);
 191   return r;
 192 }
 193
 194
 195 /* Return *this - other.  */
 196
 197 sreal
 198 sreal::operator- (const sreal &other) const
 199 {
 200   int dexp;
 201   sreal tmp;
 202   int64_t r_sig, r_exp;
 203   const sreal *bb;
 204   const sreal *a_p = this, *b_p = &other;
 205
 206   int64_t sign = 1;
 207   if (a_p->m_exp < b_p->m_exp)
 208     {
 209       sign = -1;
 210       std::swap (a_p, b_p);
 211     }
 212
 213   dexp = a_p->m_exp - b_p->m_exp;
 214   r_exp = a_p->m_exp;
 215   if (dexp > SREAL_BITS)
 216     {
 217       r_sig = sign * a_p->m_sig;
 218
 219       sreal r;
 220       r.m_sig = r_sig;
 221       r.m_exp = r_exp;
 222       return r;
 223     }
 224   if (dexp == 0)
 225     bb = b_p;
 226   else
 227     {
 228       tmp = *b_p;
 229       tmp.shift_right (dexp);
 230       bb = &tmp;
 231     }
 232
 233   r_sig = sign * ((int64_t) a_p->m_sig - (int64_t)bb->m_sig);
 234   sreal r (r_sig, r_exp);
 235   return r;
 236 }
 237
 238 /* Return *this * other.  */
 239
 240 sreal
 241 sreal::operator* (const sreal &other) const
 242 {
 243   sreal r;
 244   if (absu_hwi (m_sig) < SREAL_MIN_SIG
 245       || absu_hwi (other.m_sig) < SREAL_MIN_SIG)
 246     {
 247       r.m_sig = 0;
 248       r.m_exp = -SREAL_MAX_EXP;
 249     }
 250   else
 251     r.normalize (m_sig * (int64_t) other.m_sig, m_exp + other.m_exp);
 252
 253   return r;
 254 }
 255
 256 /* Return *this / other.  */
 257
 258 sreal
 259 sreal::operator/ (const sreal &other) const
 260 {
 261   gcc_checking_assert (other.m_sig != 0);
 262   sreal r (SREAL_SIGN (m_sig)
 263            * ((int64_t)SREAL_ABS (m_sig) << SREAL_PART_BITS) / other.m_sig,
 264            m_exp - other.m_exp - SREAL_PART_BITS);
 265   return r;
 266 }
 267
 268 /* Stream sreal value to OB.  */
 269
 270 void
 271 sreal::stream_out (struct output_block *ob)
 272 {
 273   streamer_write_hwi (ob, m_sig);
 274   streamer_write_hwi (ob, m_exp);
 275 }
 276
 277 /* Read sreal value from IB.  */
 278
 279 sreal
 280 sreal::stream_in (class lto_input_block *ib)
 281 {
 282   sreal val;
 283   val.m_sig = streamer_read_hwi (ib);
 284   val.m_exp = streamer_read_hwi (ib);
 285   return val;
 286 }
 287
 288 #if CHECKING_P
 289
 290 namespace selftest {
 291
 292 /* Selftests for sreals.  */
 293
 294 /* Verify basic sreal operations.  */
 295
 296 static void
 297 sreal_verify_basics (void)
 298 {
 299   sreal minimum = INT_MIN/2;
 300   sreal maximum = INT_MAX/2;
 301
 302   sreal seven = 7;
 303   sreal minus_two = -2;
 304   sreal minus_nine = -9;
 305
 306   ASSERT_EQ (INT_MIN/2, minimum.to_int ());
 307   ASSERT_EQ (INT_MAX/2, maximum.to_int ());
 308   ASSERT_EQ (INT_MIN/2, minimum.to_nearest_int ());
 309   ASSERT_EQ (INT_MAX/2, maximum.to_nearest_int ());
 310
 311   ASSERT_FALSE (minus_two < minus_two);
 312   ASSERT_FALSE (seven < seven);
 313   ASSERT_TRUE (seven > minus_two);
 314   ASSERT_TRUE (minus_two < seven);
 315   ASSERT_TRUE (minus_two != seven);
 316   ASSERT_EQ (minus_two, -2);
 317   ASSERT_EQ (seven, 7);
 318   ASSERT_EQ ((seven << 10) >> 10, 7);
 319   ASSERT_EQ (seven + minus_nine, -2);
 320 }
 321
 322 /* Helper function that performs basic arithmetics and comparison
 323    of given arguments A and B.  */
 324
 325 static void
 326 verify_arithmetics (int64_t a, int64_t b)
 327 {
 328   ASSERT_EQ (a, -(-(sreal (a))).to_int ());
 329   ASSERT_EQ (a < b, sreal (a) < sreal (b));
 330   ASSERT_EQ (a <= b, sreal (a) <= sreal (b));
 331   ASSERT_EQ (a == b, sreal (a) == sreal (b));
 332   ASSERT_EQ (a != b, sreal (a) != sreal (b));
 333   ASSERT_EQ (a > b, sreal (a) > sreal (b));
 334   ASSERT_EQ (a >= b, sreal (a) >= sreal (b));
 335   ASSERT_EQ (a + b, (sreal (a) + sreal (b)).to_int ());
 336   ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_int ());
 337   ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_int ());
 338   ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_int ());
 339   ASSERT_EQ (a + b, (sreal (a) + sreal (b)).to_nearest_int ());
 340   ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_nearest_int ());
 341   ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_nearest_int ());
 342   ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_nearest_int ());
 343 }
 344
 345 /* Verify arithmetics for interesting numbers.  */
 346
 347 static void
 348 sreal_verify_arithmetics (void)
 349 {
 350   int values[] = {-14123413, -7777, -17, -10, -2, 0, 17, 139, 1234123};
 351   unsigned c = sizeof (values) / sizeof (int);
 352
 353   for (unsigned i = 0; i < c; i++)
 354     for (unsigned j = 0; j < c; j++)
 355       {
 356         int a = values[i];
 357         int b = values[j];
 358
 359         verify_arithmetics (a, b);
 360       }
 361 }
 362
 363 /* Helper function that performs various shifting test of a given
 364    argument A.  */
 365
 366 static void
 367 verify_shifting (int64_t a)
 368 {
 369   sreal v = a;
 370
 371   for (unsigned i = 0; i < 16; i++)
 372     ASSERT_EQ (a << i, (v << i).to_int());
 373
 374   a = a << 16;
 375   v = v << 16;
 376
 377   for (unsigned i = 0; i < 16; i++)
 378     ASSERT_EQ (a >> i, (v >> i).to_int());
 379 }
 380
 381 /* Verify shifting for interesting numbers.  */
 382
 383 static void
 384 sreal_verify_shifting (void)
 385 {
 386   int values[] = {0, 17, 32, 139, 1024, 55555, 1234123};
 387   unsigned c = sizeof (values) / sizeof (int);
 388
 389   for (unsigned i = 0; i < c; i++)
 390     verify_shifting (values[i]);
 391 }
 392
 393 /* Verify division by (of) a negative value.  */
 394
 395 static void
 396 sreal_verify_negative_division (void)
 397 {
 398   ASSERT_EQ (sreal (1) / sreal (1), sreal (1));
 399   ASSERT_EQ (sreal (-1) / sreal (-1), sreal (1));
 400   ASSERT_EQ (sreal (-1234567) / sreal (-1234567), sreal (1));
 401   ASSERT_EQ (sreal (-1234567) / sreal (1234567), sreal (-1));
 402   ASSERT_EQ (sreal (1234567) / sreal (-1234567), sreal (-1));
 403 }
 404
 405 static void
 406 sreal_verify_conversions (void)
 407 {
 408   ASSERT_EQ ((sreal (11) / sreal (3)).to_int (), 3);
 409   ASSERT_EQ ((sreal (11) / sreal (3)).to_nearest_int (), 4);
 410   ASSERT_EQ ((sreal (10) / sreal (3)).to_int (), 3);
 411   ASSERT_EQ ((sreal (10) / sreal (3)).to_nearest_int (), 3);
 412   ASSERT_EQ ((sreal (9) / sreal (3)).to_int (), 3);
 413   ASSERT_EQ ((sreal (9) / sreal (3)).to_nearest_int (), 3);
 414   ASSERT_EQ ((sreal (-11) / sreal (3)).to_int (), -3);
 415   ASSERT_EQ ((sreal (-11) / sreal (3)).to_nearest_int (), -4);
 416   ASSERT_EQ ((sreal (-10) / sreal (3)).to_int (), -3);
 417   ASSERT_EQ ((sreal (-10) / sreal (3)).to_nearest_int (), -3);
 418   ASSERT_EQ ((sreal (-3)).to_int (), -3);
 419   ASSERT_EQ ((sreal (-3)).to_nearest_int (), -3);
 420   for (int i = -100000 ; i < 100000; i += 123)
 421     for (int j = -10000 ; j < 100000; j += 71)
 422       if (j != 0)
 423         {
 424           sreal sval = ((sreal)i) / (sreal)j;
 425           double val = (double)i / (double)j;
 426           ASSERT_EQ ((fabs (sval.to_double () - val) < 0.00001), true);
 427           ASSERT_EQ (sval.to_int (), (int)val);
 428           ASSERT_EQ (sval.to_nearest_int (), lround (val));
 429         }
 430 }
 431
 432 /* Run all of the selftests within this file.  */
 433
 434 void sreal_cc_tests ()
 435 {
 436   sreal_verify_basics ();
 437   sreal_verify_arithmetics ();
 438   sreal_verify_shifting ();
 439   sreal_verify_negative_division ();
 440   sreal_verify_conversions ();
 441 }
 442
 443 } // namespace selftest
 444 #endif /* CHECKING_P */