gcc/sreal.c

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