gcc/sreal.c

   1 /* Simple data type for real numbers for the GNU compiler.
   2    Copyright (C) 2002-2019 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it 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 m_sig >> -m_exp;
 120   return m_sig;
 121 }
 122
 123 /* Return value of *this as double.
 124    This should be used for debug output only.  */
 125
 126 double
 127 sreal::to_double () const
 128 {
 129   double val = m_sig;
 130   if (m_exp)
 131     val = ldexp (val, m_exp);
 132   return val;
 133 }
 134
 135 /* Return *this + other.  */
 136
 137 sreal
 138 sreal::operator+ (const sreal &other) const
 139 {
 140   int dexp;
 141   sreal tmp;
 142   int64_t r_sig, r_exp;
 143
 144   const sreal *a_p = this, *b_p = &other, *bb;
 145
 146   if (a_p->m_exp < b_p->m_exp)
 147     std::swap (a_p, b_p);
 148
 149   dexp = a_p->m_exp - b_p->m_exp;
 150   r_exp = a_p->m_exp;
 151   if (dexp > SREAL_BITS)
 152     {
 153       r_sig = a_p->m_sig;
 154
 155       sreal r;
 156       r.m_sig = r_sig;
 157       r.m_exp = r_exp;
 158       return r;
 159     }
 160
 161   if (dexp == 0)
 162     bb = b_p;
 163   else
 164     {
 165       tmp = *b_p;
 166       tmp.shift_right (dexp);
 167       bb = &tmp;
 168     }
 169
 170   r_sig = a_p->m_sig + (int64_t)bb->m_sig;
 171   sreal r (r_sig, r_exp);
 172   return r;
 173 }
 174
 175
 176 /* Return *this - other.  */
 177
 178 sreal
 179 sreal::operator- (const sreal &other) const
 180 {
 181   int dexp;
 182   sreal tmp;
 183   int64_t r_sig, r_exp;
 184   const sreal *bb;
 185   const sreal *a_p = this, *b_p = &other;
 186
 187   int64_t sign = 1;
 188   if (a_p->m_exp < b_p->m_exp)
 189     {
 190       sign = -1;
 191       std::swap (a_p, b_p);
 192     }
 193
 194   dexp = a_p->m_exp - b_p->m_exp;
 195   r_exp = a_p->m_exp;
 196   if (dexp > SREAL_BITS)
 197     {
 198       r_sig = sign * a_p->m_sig;
 199
 200       sreal r;
 201       r.m_sig = r_sig;
 202       r.m_exp = r_exp;
 203       return r;
 204     }
 205   if (dexp == 0)
 206     bb = b_p;
 207   else
 208     {
 209       tmp = *b_p;
 210       tmp.shift_right (dexp);
 211       bb = &tmp;
 212     }
 213
 214   r_sig = sign * ((int64_t) a_p->m_sig - (int64_t)bb->m_sig);
 215   sreal r (r_sig, r_exp);
 216   return r;
 217 }
 218
 219 /* Return *this * other.  */
 220
 221 sreal
 222 sreal::operator* (const sreal &other) const
 223 {
 224   sreal r;
 225   if (absu_hwi (m_sig) < SREAL_MIN_SIG
 226       || absu_hwi (other.m_sig) < SREAL_MIN_SIG)
 227     {
 228       r.m_sig = 0;
 229       r.m_exp = -SREAL_MAX_EXP;
 230     }
 231   else
 232     r.normalize (m_sig * (int64_t) other.m_sig, m_exp + other.m_exp);
 233
 234   return r;
 235 }
 236
 237 /* Return *this / other.  */
 238
 239 sreal
 240 sreal::operator/ (const sreal &other) const
 241 {
 242   gcc_checking_assert (other.m_sig != 0);
 243   sreal r (SREAL_SIGN (m_sig)
 244            * ((int64_t)SREAL_ABS (m_sig) << SREAL_PART_BITS) / other.m_sig,
 245            m_exp - other.m_exp - SREAL_PART_BITS);
 246   return r;
 247 }
 248
 249 /* Stream sreal value to OB.  */
 250
 251 void
 252 sreal::stream_out (struct output_block *ob)
 253 {
 254   streamer_write_hwi (ob, m_sig);
 255   streamer_write_hwi (ob, m_exp);
 256 }
 257
 258 /* Read sreal value from IB.  */
 259
 260 sreal
 261 sreal::stream_in (class lto_input_block *ib)
 262 {
 263   sreal val;
 264   val.m_sig = streamer_read_hwi (ib);
 265   val.m_exp = streamer_read_hwi (ib);
 266   return val;
 267 }
 268
 269 #if CHECKING_P
 270
 271 namespace selftest {
 272
 273 /* Selftests for sreals.  */
 274
 275 /* Verify basic sreal operations.  */
 276
 277 static void
 278 sreal_verify_basics (void)
 279 {
 280   sreal minimum = INT_MIN/2;
 281   sreal maximum = INT_MAX/2;
 282
 283   sreal seven = 7;
 284   sreal minus_two = -2;
 285   sreal minus_nine = -9;
 286
 287   ASSERT_EQ (INT_MIN/2, minimum.to_int ());
 288   ASSERT_EQ (INT_MAX/2, maximum.to_int ());
 289
 290   ASSERT_FALSE (minus_two < minus_two);
 291   ASSERT_FALSE (seven < seven);
 292   ASSERT_TRUE (seven > minus_two);
 293   ASSERT_TRUE (minus_two < seven);
 294   ASSERT_TRUE (minus_two != seven);
 295   ASSERT_EQ (minus_two, -2);
 296   ASSERT_EQ (seven, 7);
 297   ASSERT_EQ ((seven << 10) >> 10, 7);
 298   ASSERT_EQ (seven + minus_nine, -2);
 299 }
 300
 301 /* Helper function that performs basic arithmetics and comparison
 302    of given arguments A and B.  */
 303
 304 static void
 305 verify_aritmetics (int64_t a, int64_t b)
 306 {
 307   ASSERT_EQ (a, -(-(sreal (a))).to_int ());
 308   ASSERT_EQ (a < b, sreal (a) < sreal (b));
 309   ASSERT_EQ (a <= b, sreal (a) <= sreal (b));
 310   ASSERT_EQ (a == b, sreal (a) == sreal (b));
 311   ASSERT_EQ (a != b, sreal (a) != sreal (b));
 312   ASSERT_EQ (a > b, sreal (a) > sreal (b));
 313   ASSERT_EQ (a >= b, sreal (a) >= sreal (b));
 314   ASSERT_EQ (a + b, (sreal (a) + sreal (b)).to_int ());
 315   ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_int ());
 316   ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_int ());
 317   ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_int ());
 318 }
 319
 320 /* Verify arithmetics for interesting numbers.  */
 321
 322 static void
 323 sreal_verify_arithmetics (void)
 324 {
 325   int values[] = {-14123413, -7777, -17, -10, -2, 0, 17, 139, 1234123};
 326   unsigned c = sizeof (values) / sizeof (int);
 327
 328   for (unsigned i = 0; i < c; i++)
 329     for (unsigned j = 0; j < c; j++)
 330       {
 331         int a = values[i];
 332         int b = values[j];
 333
 334         verify_aritmetics (a, b);
 335       }
 336 }
 337
 338 /* Helper function that performs various shifting test of a given
 339    argument A.  */
 340
 341 static void
 342 verify_shifting (int64_t a)
 343 {
 344   sreal v = a;
 345
 346   for (unsigned i = 0; i < 16; i++)
 347     ASSERT_EQ (a << i, (v << i).to_int());
 348
 349   a = a << 16;
 350   v = v << 16;
 351
 352   for (unsigned i = 0; i < 16; i++)
 353     ASSERT_EQ (a >> i, (v >> i).to_int());
 354 }
 355
 356 /* Verify shifting for interesting numbers.  */
 357
 358 static void
 359 sreal_verify_shifting (void)
 360 {
 361   int values[] = {0, 17, 32, 139, 1024, 55555, 1234123};
 362   unsigned c = sizeof (values) / sizeof (int);
 363
 364   for (unsigned i = 0; i < c; i++)
 365     verify_shifting (values[i]);
 366 }
 367
 368 /* Verify division by (of) a negative value.  */
 369
 370 static void
 371 sreal_verify_negative_division (void)
 372 {
 373   ASSERT_EQ (sreal (1) / sreal (1), sreal (1));
 374   ASSERT_EQ (sreal (-1) / sreal (-1), sreal (1));
 375   ASSERT_EQ (sreal (-1234567) / sreal (-1234567), sreal (1));
 376   ASSERT_EQ (sreal (-1234567) / sreal (1234567), sreal (-1));
 377   ASSERT_EQ (sreal (1234567) / sreal (-1234567), sreal (-1));
 378 }
 379
 380 /* Run all of the selftests within this file.  */
 381
 382 void sreal_c_tests ()
 383 {
 384   sreal_verify_basics ();
 385   sreal_verify_arithmetics ();
 386   sreal_verify_shifting ();
 387   sreal_verify_negative_division ();
 388 }
 389
 390 } // namespace selftest
 391 #endif /* CHECKING_P */