Line data Source code
1 : /* Simple data type for real numbers for the GNU compiler.
2 : Copyright (C) 2002-2026 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 0 : sreal::dump (FILE *file) const
66 : {
67 0 : fprintf (file, "(%" PRIi64 " * 2^%d)", (int64_t)m_sig, m_exp);
68 0 : }
69 :
70 : DEBUG_FUNCTION void
71 0 : debug (const sreal &ref)
72 : {
73 0 : ref.dump (stderr);
74 0 : }
75 :
76 : DEBUG_FUNCTION void
77 0 : debug (const sreal *ptr)
78 : {
79 0 : if (ptr)
80 0 : debug (*ptr);
81 : else
82 0 : fprintf (stderr, "<nil>\n");
83 0 : }
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 434600439 : sreal::shift_right (int s)
91 : {
92 434600439 : gcc_checking_assert (s > 0);
93 434600439 : 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 434600439 : gcc_checking_assert (m_exp + s <= SREAL_MAX_EXP);
98 :
99 434600439 : m_exp += s;
100 :
101 434600439 : m_sig += (int64_t) 1 << (s - 1);
102 434600439 : m_sig >>= s;
103 434600439 : }
104 :
105 : /* Return integer value of *this. */
106 :
107 : int64_t
108 21282101 : sreal::to_int () const
109 : {
110 21282101 : int64_t sign = SREAL_SIGN (m_sig);
111 :
112 21282101 : if (m_exp <= -SREAL_BITS)
113 : return 0;
114 18963118 : if (m_exp >= SREAL_PART_BITS)
115 0 : return sign * INTTYPE_MAXIMUM (int64_t);
116 18963118 : if (m_exp > 0)
117 96 : return sign * (SREAL_ABS ((int64_t)m_sig) << m_exp);
118 18963022 : if (m_exp < 0)
119 18963002 : return sign * (SREAL_ABS ((int64_t)m_sig) >> -m_exp);
120 20 : return m_sig;
121 : }
122 :
123 : /* Return nearest integer value of *this. */
124 :
125 : int64_t
126 32365038 : sreal::to_nearest_int () const
127 : {
128 32365038 : int64_t sign = SREAL_SIGN (m_sig);
129 :
130 32365038 : if (m_exp <= -SREAL_BITS)
131 : return 0;
132 28324422 : if (m_exp >= SREAL_PART_BITS)
133 2155 : return sign * INTTYPE_MAXIMUM (int64_t);
134 28322267 : if (m_exp > 0)
135 9332604 : return sign * (SREAL_ABS ((int64_t)m_sig) << m_exp);
136 18989663 : if (m_exp < 0)
137 16488140 : return sign * ((SREAL_ABS ((int64_t)m_sig) >> -m_exp)
138 16488140 : + ((SREAL_ABS (m_sig) >> (-m_exp - 1)) & 1));
139 2501523 : 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 10281585 : sreal::to_double () const
147 : {
148 10281585 : double val = m_sig;
149 10281585 : if (m_exp)
150 10281582 : val = ldexp (val, m_exp);
151 10281585 : return val;
152 : }
153 :
154 : /* Return *this + other. */
155 :
156 : sreal
157 671895942 : sreal::operator+ (const sreal &other) const
158 : {
159 671895942 : int dexp;
160 671895942 : sreal tmp;
161 671895942 : int64_t r_sig, r_exp;
162 :
163 671895942 : const sreal *a_p = this, *b_p = &other, *bb;
164 :
165 671895942 : if (a_p->m_exp < b_p->m_exp)
166 131266979 : std::swap (a_p, b_p);
167 :
168 671895942 : dexp = a_p->m_exp - b_p->m_exp;
169 671895942 : r_exp = a_p->m_exp;
170 671895942 : if (dexp > SREAL_BITS)
171 : {
172 166636220 : r_sig = a_p->m_sig;
173 :
174 166636220 : sreal r;
175 166636220 : r.m_sig = r_sig;
176 166636220 : r.m_exp = r_exp;
177 166636220 : return r;
178 : }
179 :
180 505259722 : if (dexp == 0)
181 : bb = b_p;
182 : else
183 : {
184 417636661 : tmp = *b_p;
185 417636661 : tmp.shift_right (dexp);
186 417636661 : bb = &tmp;
187 : }
188 :
189 505259722 : r_sig = a_p->m_sig + (int64_t)bb->m_sig;
190 505259722 : sreal r (r_sig, r_exp);
191 505259722 : return r;
192 : }
193 :
194 :
195 : /* Return *this - other. */
196 :
197 : sreal
198 62966846 : sreal::operator- (const sreal &other) const
199 : {
200 62966846 : int dexp;
201 62966846 : sreal tmp;
202 62966846 : int64_t r_sig, r_exp;
203 62966846 : const sreal *bb;
204 62966846 : const sreal *a_p = this, *b_p = &other;
205 :
206 62966846 : int64_t sign = 1;
207 62966846 : if (a_p->m_exp < b_p->m_exp)
208 : {
209 5590827 : sign = -1;
210 5590827 : std::swap (a_p, b_p);
211 : }
212 :
213 62966846 : dexp = a_p->m_exp - b_p->m_exp;
214 62966846 : r_exp = a_p->m_exp;
215 62966846 : if (dexp > SREAL_BITS)
216 : {
217 1066123 : r_sig = sign * a_p->m_sig;
218 :
219 1066123 : sreal r;
220 1066123 : r.m_sig = r_sig;
221 1066123 : r.m_exp = r_exp;
222 1066123 : return r;
223 : }
224 61900723 : if (dexp == 0)
225 : bb = b_p;
226 : else
227 : {
228 16963778 : tmp = *b_p;
229 16963778 : tmp.shift_right (dexp);
230 16963778 : bb = &tmp;
231 : }
232 :
233 61900723 : r_sig = sign * ((int64_t) a_p->m_sig - (int64_t)bb->m_sig);
234 61900723 : sreal r (r_sig, r_exp);
235 61900723 : return r;
236 : }
237 :
238 : /* Return *this * other. */
239 :
240 : sreal
241 612722229 : sreal::operator* (const sreal &other) const
242 : {
243 612722229 : sreal r;
244 612722229 : if (absu_hwi (m_sig) < SREAL_MIN_SIG
245 612722229 : || absu_hwi (other.m_sig) < SREAL_MIN_SIG)
246 : {
247 118240072 : r.m_sig = 0;
248 118240072 : r.m_exp = -SREAL_MAX_EXP;
249 : }
250 : else
251 494482157 : r.normalize (m_sig * (int64_t) other.m_sig, m_exp + other.m_exp);
252 :
253 612722229 : return r;
254 : }
255 :
256 : /* Return *this / other. */
257 :
258 : sreal
259 354752676 : sreal::operator/ (const sreal &other) const
260 : {
261 354752676 : gcc_checking_assert (other.m_sig != 0);
262 354752676 : sreal r (SREAL_SIGN (m_sig)
263 354752676 : * ((int64_t)SREAL_ABS (m_sig) << SREAL_PART_BITS) / other.m_sig,
264 694761380 : m_exp - other.m_exp - SREAL_PART_BITS);
265 354752676 : return r;
266 : }
267 :
268 : /* Stream sreal value to OB. */
269 :
270 : void
271 393821 : sreal::stream_out (struct output_block *ob)
272 : {
273 393821 : streamer_write_hwi (ob, m_sig);
274 393821 : streamer_write_hwi (ob, m_exp);
275 393821 : }
276 :
277 : /* Read sreal value from IB. */
278 :
279 : sreal
280 327777 : sreal::stream_in (class lto_input_block *ib)
281 : {
282 327777 : sreal val;
283 327777 : val.m_sig = streamer_read_hwi (ib);
284 327777 : val.m_exp = streamer_read_hwi (ib);
285 327777 : 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 4 : sreal_verify_basics (void)
298 : {
299 4 : sreal minimum = INT_MIN/2;
300 4 : sreal maximum = INT_MAX/2;
301 :
302 4 : sreal seven = 7;
303 4 : sreal minus_two = -2;
304 4 : sreal minus_nine = -9;
305 :
306 4 : ASSERT_EQ (INT_MIN/2, minimum.to_int ());
307 4 : ASSERT_EQ (INT_MAX/2, maximum.to_int ());
308 4 : ASSERT_EQ (INT_MIN/2, minimum.to_nearest_int ());
309 4 : ASSERT_EQ (INT_MAX/2, maximum.to_nearest_int ());
310 :
311 4 : ASSERT_FALSE (minus_two < minus_two);
312 4 : ASSERT_FALSE (seven < seven);
313 4 : ASSERT_TRUE (seven > minus_two);
314 4 : ASSERT_TRUE (minus_two < seven);
315 4 : ASSERT_TRUE (minus_two != seven);
316 8 : ASSERT_EQ (minus_two, -2);
317 8 : ASSERT_EQ (seven, 7);
318 8 : ASSERT_EQ ((seven << 10) >> 10, 7);
319 8 : ASSERT_EQ (seven + minus_nine, -2);
320 4 : }
321 :
322 : /* Helper function that performs basic arithmetics and comparison
323 : of given arguments A and B. */
324 :
325 : static void
326 324 : verify_arithmetics (int64_t a, int64_t b)
327 : {
328 324 : ASSERT_EQ (a, -(-(sreal (a))).to_int ());
329 324 : ASSERT_EQ (a < b, sreal (a) < sreal (b));
330 324 : ASSERT_EQ (a <= b, sreal (a) <= sreal (b));
331 648 : ASSERT_EQ (a == b, sreal (a) == sreal (b));
332 648 : ASSERT_EQ (a != b, sreal (a) != sreal (b));
333 324 : ASSERT_EQ (a > b, sreal (a) > sreal (b));
334 324 : ASSERT_EQ (a >= b, sreal (a) >= sreal (b));
335 324 : ASSERT_EQ (a + b, (sreal (a) + sreal (b)).to_int ());
336 324 : ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_int ());
337 324 : ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_int ());
338 324 : ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_int ());
339 324 : ASSERT_EQ (a + b, (sreal (a) + sreal (b)).to_nearest_int ());
340 324 : ASSERT_EQ (a - b, (sreal (a) - sreal (b)).to_nearest_int ());
341 324 : ASSERT_EQ (b + a, (sreal (b) + sreal (a)).to_nearest_int ());
342 324 : ASSERT_EQ (b - a, (sreal (b) - sreal (a)).to_nearest_int ());
343 324 : }
344 :
345 : /* Verify arithmetics for interesting numbers. */
346 :
347 : static void
348 4 : sreal_verify_arithmetics (void)
349 : {
350 4 : int values[] = {-14123413, -7777, -17, -10, -2, 0, 17, 139, 1234123};
351 4 : unsigned c = sizeof (values) / sizeof (int);
352 :
353 40 : for (unsigned i = 0; i < c; i++)
354 360 : for (unsigned j = 0; j < c; j++)
355 : {
356 324 : int a = values[i];
357 324 : int b = values[j];
358 :
359 324 : verify_arithmetics (a, b);
360 : }
361 4 : }
362 :
363 : /* Helper function that performs various shifting test of a given
364 : argument A. */
365 :
366 : static void
367 28 : verify_shifting (int64_t a)
368 : {
369 28 : sreal v = a;
370 :
371 476 : for (unsigned i = 0; i < 16; i++)
372 448 : ASSERT_EQ (a << i, (v << i).to_int());
373 :
374 28 : a = a << 16;
375 28 : v = v << 16;
376 :
377 476 : for (unsigned i = 0; i < 16; i++)
378 448 : ASSERT_EQ (a >> i, (v >> i).to_int());
379 28 : }
380 :
381 : /* Verify shifting for interesting numbers. */
382 :
383 : static void
384 4 : sreal_verify_shifting (void)
385 : {
386 4 : int values[] = {0, 17, 32, 139, 1024, 55555, 1234123};
387 4 : unsigned c = sizeof (values) / sizeof (int);
388 :
389 32 : for (unsigned i = 0; i < c; i++)
390 28 : verify_shifting (values[i]);
391 4 : }
392 :
393 : /* Verify division by (of) a negative value. */
394 :
395 : static void
396 4 : sreal_verify_negative_division (void)
397 : {
398 8 : ASSERT_EQ (sreal (1) / sreal (1), sreal (1));
399 8 : ASSERT_EQ (sreal (-1) / sreal (-1), sreal (1));
400 8 : ASSERT_EQ (sreal (-1234567) / sreal (-1234567), sreal (1));
401 8 : ASSERT_EQ (sreal (-1234567) / sreal (1234567), sreal (-1));
402 8 : ASSERT_EQ (sreal (1234567) / sreal (-1234567), sreal (-1));
403 4 : }
404 :
405 : static void
406 4 : sreal_verify_conversions (void)
407 : {
408 4 : ASSERT_EQ ((sreal (11) / sreal (3)).to_int (), 3);
409 4 : ASSERT_EQ ((sreal (11) / sreal (3)).to_nearest_int (), 4);
410 4 : ASSERT_EQ ((sreal (10) / sreal (3)).to_int (), 3);
411 4 : ASSERT_EQ ((sreal (10) / sreal (3)).to_nearest_int (), 3);
412 4 : ASSERT_EQ ((sreal (9) / sreal (3)).to_int (), 3);
413 4 : ASSERT_EQ ((sreal (9) / sreal (3)).to_nearest_int (), 3);
414 4 : ASSERT_EQ ((sreal (-11) / sreal (3)).to_int (), -3);
415 4 : ASSERT_EQ ((sreal (-11) / sreal (3)).to_nearest_int (), -4);
416 4 : ASSERT_EQ ((sreal (-10) / sreal (3)).to_int (), -3);
417 4 : ASSERT_EQ ((sreal (-10) / sreal (3)).to_nearest_int (), -3);
418 4 : ASSERT_EQ ((sreal (-3)).to_int (), -3);
419 4 : ASSERT_EQ ((sreal (-3)).to_nearest_int (), -3);
420 6512 : for (int i = -100000 ; i < 100000; i += 123)
421 10093908 : for (int j = -10000 ; j < 100000; j += 71)
422 10087400 : if (j != 0)
423 : {
424 10087400 : sreal sval = ((sreal)i) / (sreal)j;
425 10087400 : double val = (double)i / (double)j;
426 10087400 : ASSERT_EQ ((fabs (sval.to_double () - val) < 0.00001), true);
427 10087400 : ASSERT_EQ (sval.to_int (), (int)val);
428 10087400 : ASSERT_EQ (sval.to_nearest_int (), lround (val));
429 : }
430 4 : }
431 :
432 : /* Run all of the selftests within this file. */
433 :
434 4 : void sreal_cc_tests ()
435 : {
436 4 : sreal_verify_basics ();
437 4 : sreal_verify_arithmetics ();
438 4 : sreal_verify_shifting ();
439 4 : sreal_verify_negative_division ();
440 4 : sreal_verify_conversions ();
441 4 : }
442 :
443 : } // namespace selftest
444 : #endif /* CHECKING_P */
|
